VapourSynth-llvmexpr
Loading...
Searching...
No Matches
ConstPropPass.cpp
Go to the documentation of this file.
1
19
20#include "ConstPropPass.hpp"
21#include "../../frontend/Tokenizer.hpp"
22#include "../framework/AnalysisError.hpp"
23#include "../framework/AnalysisManager.hpp"
24#include "BlockAnalysisPass.hpp"
25
26#include <algorithm>
27#include <cmath>
28#include <format>
29#include <numbers>
30
31namespace analysis {
32
33ConstPropPass::Result ConstPropPass::run(const std::vector<Token>& tokens,
34 AnalysisManager& am) {
35 using ConstStack = std::vector<std::optional<double>>;
36
37 // Depend on BlockAnalysisPass for CFG structure
38 const auto& block_result = am.getResult<BlockAnalysisPass>();
39 const auto& cfg_blocks = block_result.cfg_blocks;
40
41 Result result;
42
43 // Initialize const stack states in results
44 result.const_stack_in.resize(cfg_blocks.size());
45 result.const_stack_out.resize(cfg_blocks.size());
46
47 if (!cfg_blocks.empty()) {
48 result.const_stack_in[0] = ConstStack{};
49 }
50
51 bool changed = true;
52 while (changed) {
53 changed = false;
54 for (size_t i = 0; i < cfg_blocks.size(); ++i) {
55 // IN[i] = Merge of OUT[p] for all predecessors p
56 ConstStack new_in;
57 if (i > 0 && !cfg_blocks[i].predecessors.empty()) {
58 new_in = result.const_stack_out[cfg_blocks[i].predecessors[0]];
59 for (size_t j = 1; j < cfg_blocks[i].predecessors.size(); ++j) {
60 int p_idx = cfg_blocks[i].predecessors[j];
61 const auto& other_stack = result.const_stack_out[p_idx];
62
63 if (new_in.size() != other_stack.size()) {
64 throw AnalysisError(
65 std::format("Stack depth mismatch during constant "
66 "propagation at block {}: {} vs {}",
67 i, new_in.size(), other_stack.size()));
68 }
69
70 // Merge: if values differ, mark as non-constant
71 for (size_t k = 0; k < new_in.size(); ++k) {
72 if (new_in[k] != other_stack[k]) {
73 new_in[k] = std::nullopt;
74 }
75 }
76 }
77 } else {
78 new_in = ConstStack{};
79 }
80
81 if (new_in != result.const_stack_in[i]) {
82 result.const_stack_in[i] = new_in;
83 }
84
85 // Transfer function: OUT[i] = F(IN[i])
86 ConstStack current_stack = result.const_stack_in[i];
87 for (int j = cfg_blocks[i].start_token_idx;
88 j < cfg_blocks[i].end_token_idx; ++j) {
89 const auto& token = tokens[j];
90 const auto behavior = get_token_behavior(token);
91
92 if (current_stack.size() <
93 static_cast<size_t>(behavior.arity)) {
94 for (size_t k = 0; k < static_cast<size_t>(behavior.arity) -
95 current_stack.size();
96 ++k) {
97 current_stack.insert(current_stack.begin(),
98 std::nullopt);
99 }
100 }
101
102 std::vector<std::optional<double>> args;
103 for (int k = 0; k < behavior.arity; ++k) {
104 args.push_back(current_stack.back());
105 current_stack.pop_back();
106 }
107 std::ranges::reverse(args);
108
109 auto all_const = [&](const auto& a) { return a.has_value(); };
110 bool can_compute = std::ranges::all_of(args, all_const);
111
112 auto push_result = [&](std::optional<double> res) {
113 current_stack.push_back(res);
114 };
115
116 auto push_n = [&](int n, std::optional<double> val) {
117 for (int k = 0; k < n; ++k) {
118 current_stack.push_back(val);
119 }
120 };
121
122 // Evaluate constant expressions
123 switch (token.type) {
124 case TokenType::Number:
125 push_result(
126 std::get<TokenPayloadNumber>(token.payload).value);
127 break;
128 case TokenType::ConstantPi:
129 push_result(std::numbers::pi_v<double>);
130 break;
131
132 case TokenType::Add:
133 push_result(can_compute ? std::optional(args[0].value() +
134 args[1].value())
135 : std::nullopt);
136 break;
137 case TokenType::Sub:
138 push_result(can_compute ? std::optional(args[0].value() -
139 args[1].value())
140 : std::nullopt);
141 break;
142 case TokenType::Mul:
143 push_result(can_compute ? std::optional(args[0].value() *
144 args[1].value())
145 : std::nullopt);
146 break;
147 case TokenType::Div:
148 push_result(can_compute ? std::optional(args[0].value() /
149 args[1].value())
150 : std::nullopt);
151 break;
152 case TokenType::Mod:
153 push_result(can_compute
154 ? std::optional(std::fmod(args[0].value(),
155 args[1].value()))
156 : std::nullopt);
157 break;
158
159 case TokenType::Gt:
160 push_result(
161 can_compute
162 ? std::optional(
163 args[0].value() > args[1].value() ? 1.0 : 0.0)
164 : std::nullopt);
165 break;
166 case TokenType::Lt:
167 push_result(
168 can_compute
169 ? std::optional(
170 args[0].value() < args[1].value() ? 1.0 : 0.0)
171 : std::nullopt);
172 break;
173 case TokenType::Eq:
174 push_result(
175 can_compute
176 ? std::optional(args[0].value() == args[1].value()
177 ? 1.0
178 : 0.0)
179 : std::nullopt);
180 break;
181 case TokenType::Ge:
182 push_result(
183 can_compute
184 ? std::optional(args[0].value() >= args[1].value()
185 ? 1.0
186 : 0.0)
187 : std::nullopt);
188 break;
189 case TokenType::Le:
190 push_result(
191 can_compute
192 ? std::optional(args[0].value() <= args[1].value()
193 ? 1.0
194 : 0.0)
195 : std::nullopt);
196 break;
197
198 // Logical operators
199 case TokenType::And:
200 push_result(can_compute
201 ? std::optional((args[0].value() > 0 &&
202 args[1].value() > 0)
203 ? 1.0
204 : 0.0)
205 : std::nullopt);
206 break;
207 case TokenType::Or:
208 push_result(can_compute
209 ? std::optional((args[0].value() > 0 ||
210 args[1].value() > 0)
211 ? 1.0
212 : 0.0)
213 : std::nullopt);
214 break;
215 case TokenType::Xor:
216 push_result(can_compute
217 ? std::optional(((args[0].value() > 0) !=
218 (args[1].value() > 0))
219 ? 1.0
220 : 0.0)
221 : std::nullopt);
222 break;
223 case TokenType::Not:
224 push_result(
225 can_compute
226 ? std::optional(args[0].value() > 0 ? 0.0 : 1.0)
227 : std::nullopt);
228 break;
229
230 case TokenType::Pow:
231 push_result(can_compute
232 ? std::optional(std::pow(args[0].value(),
233 args[1].value()))
234 : std::nullopt);
235 break;
236 case TokenType::Sqrt:
237 push_result(can_compute
238 ? std::optional(std::sqrt(args[0].value()))
239 : std::nullopt);
240 break;
241
242 case TokenType::Exp:
243 push_result(can_compute
244 ? std::optional(std::exp(args[0].value()))
245 : std::nullopt);
246 break;
247 case TokenType::Exp2:
248 push_result(can_compute
249 ? std::optional(std::exp2(args[0].value()))
250 : std::nullopt);
251 break;
252 case TokenType::Log:
253 push_result(can_compute
254 ? std::optional(std::log(args[0].value()))
255 : std::nullopt);
256 break;
257 case TokenType::Log2:
258 push_result(can_compute
259 ? std::optional(std::log2(args[0].value()))
260 : std::nullopt);
261 break;
262 case TokenType::Log10:
263 push_result(can_compute
264 ? std::optional(std::log10(args[0].value()))
265 : std::nullopt);
266 break;
267
268 case TokenType::Sin:
269 push_result(can_compute
270 ? std::optional(std::sin(args[0].value()))
271 : std::nullopt);
272 break;
273 case TokenType::Cos:
274 push_result(can_compute
275 ? std::optional(std::cos(args[0].value()))
276 : std::nullopt);
277 break;
278 case TokenType::Tan:
279 push_result(can_compute
280 ? std::optional(std::tan(args[0].value()))
281 : std::nullopt);
282 break;
283 case TokenType::Asin:
284 push_result(can_compute
285 ? std::optional(std::asin(args[0].value()))
286 : std::nullopt);
287 break;
288 case TokenType::Acos:
289 push_result(can_compute
290 ? std::optional(std::acos(args[0].value()))
291 : std::nullopt);
292 break;
293 case TokenType::Atan:
294 push_result(can_compute
295 ? std::optional(std::atan(args[0].value()))
296 : std::nullopt);
297 break;
298 case TokenType::Atan2:
299 push_result(can_compute
300 ? std::optional(std::atan2(args[0].value(),
301 args[1].value()))
302 : std::nullopt);
303 break;
304
305 case TokenType::Sinh:
306 push_result(can_compute
307 ? std::optional(std::sinh(args[0].value()))
308 : std::nullopt);
309 break;
310 case TokenType::Cosh:
311 push_result(can_compute
312 ? std::optional(std::cosh(args[0].value()))
313 : std::nullopt);
314 break;
315 case TokenType::Tanh:
316 push_result(can_compute
317 ? std::optional(std::tanh(args[0].value()))
318 : std::nullopt);
319 break;
320
321 case TokenType::Floor:
322 push_result(can_compute
323 ? std::optional(std::floor(args[0].value()))
324 : std::nullopt);
325 break;
326 case TokenType::Ceil:
327 push_result(can_compute
328 ? std::optional(std::ceil(args[0].value()))
329 : std::nullopt);
330 break;
331 case TokenType::Round:
332 push_result(can_compute
333 ? std::optional(std::round(args[0].value()))
334 : std::nullopt);
335 break;
336 case TokenType::Trunc:
337 push_result(can_compute
338 ? std::optional(std::trunc(args[0].value()))
339 : std::nullopt);
340 break;
341
342 case TokenType::Abs:
343 push_result(can_compute
344 ? std::optional(std::abs(args[0].value()))
345 : std::nullopt);
346 break;
347 case TokenType::Neg:
348 push_result(can_compute ? std::optional(-args[0].value())
349 : std::nullopt);
350 break;
351 case TokenType::Sgn:
352 push_result(can_compute ? std::optional([&]() -> double {
353 double val = args[0].value();
354 if (val < 0) {
355 return -1.0;
356 }
357 if (val > 0) {
358 return 1.0;
359 }
360 return 0.0;
361 }())
362 : std::nullopt);
363 break;
364 case TokenType::Copysign:
365 push_result(can_compute
366 ? std::optional(std::copysign(
367 args[0].value(), args[1].value()))
368 : std::nullopt);
369 break;
370 case TokenType::Fma:
371 push_result(can_compute
372 ? std::optional(std::fma(args[0].value(),
373 args[1].value(),
374 args[2].value()))
375 : std::nullopt);
376 break;
377
378 case TokenType::Max:
379 push_result(can_compute
380 ? std::optional(std::max(args[0].value(),
381 args[1].value()))
382 : std::nullopt);
383 break;
384 case TokenType::Min:
385 push_result(can_compute
386 ? std::optional(std::min(args[0].value(),
387 args[1].value()))
388 : std::nullopt);
389 break;
390 case TokenType::Clamp:
391 push_result(can_compute
392 ? std::optional(std::clamp(args[0].value(),
393 args[1].value(),
394 args[2].value()))
395 : std::nullopt);
396 break;
397
398 case TokenType::Ternary:
399 push_result(can_compute
400 ? std::optional(args[0].value() > 0
401 ? args[1].value()
402 : args[2].value())
403 : std::nullopt);
404 break;
405
406 case TokenType::Bitand:
407 push_result(can_compute
408 ? std::optional(static_cast<double>(
409 static_cast<int64_t>(
410 std::nearbyint(args[0].value())) &
411 static_cast<int64_t>(
412 std::nearbyint(args[1].value()))))
413 : std::nullopt);
414 break;
415 case TokenType::Bitor:
416 push_result(can_compute
417 ? std::optional(static_cast<double>(
418 static_cast<int64_t>(
419 std::nearbyint(args[0].value())) |
420 static_cast<int64_t>(
421 std::nearbyint(args[1].value()))))
422 : std::nullopt);
423 break;
424 case TokenType::Bitxor:
425 push_result(can_compute
426 ? std::optional(static_cast<double>(
427 static_cast<int64_t>(
428 std::nearbyint(args[0].value())) ^
429 static_cast<int64_t>(
430 std::nearbyint(args[1].value()))))
431 : std::nullopt);
432 break;
433 case TokenType::Bitnot:
434 push_result(can_compute
435 ? std::optional(static_cast<double>(
436 ~static_cast<int64_t>(
437 std::nearbyint(args[0].value()))))
438 : std::nullopt);
439 break;
440
441 default:
442 push_n(behavior.arity + behavior.stack_effect,
443 std::nullopt);
444 break;
445 }
446 }
447
448 if (current_stack != result.const_stack_out[i]) {
449 result.const_stack_out[i] = current_stack;
450 changed = true;
451 }
452 }
453 }
454
455 return result;
456}
457
458} // namespace analysis
get_token_behavior
TokenBehavior get_token_behavior(const Token &token)
Definition Tokenizer.cpp:1054
analysis::ConstPropPass::run
Result run(const std::vector< Token > &tokens, AnalysisManager &am) override
Definition ConstPropPass.cpp:33
analysis::ConstPropResult::const_stack_out
std::vector< std::vector< std::optional< double > > > const_stack_out
Definition ConstPropPass.hpp:32
analysis::ConstPropResult::const_stack_in
std::vector< std::vector< std::optional< double > > > const_stack_in
Definition ConstPropPass.hpp:31