main
ts 626 lines 19 KB
Raw
1 /**
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 */
7
8 import {isValidIdentifier} from '@babel/types';
9 import {CompilerError} from '../CompilerError';
10 import {
11 GeneratedSource,
12 GotoVariant,
13 HIRFunction,
14 IdentifierId,
15 Instruction,
16 InstructionValue,
17 LoadGlobal,
18 Phi,
19 Place,
20 Primitive,
21 assertConsistentIdentifiers,
22 assertTerminalSuccessorsExist,
23 makePropertyLiteral,
24 markInstructionIds,
25 markPredecessors,
26 mergeConsecutiveBlocks,
27 reversePostorderBlocks,
28 } from '../HIR';
29 import {
30 removeDeadDoWhileStatements,
31 removeUnnecessaryTryCatch,
32 removeUnreachableForUpdates,
33 } from '../HIR/HIRBuilder';
34 import {eliminateRedundantPhi} from '../SSA';
35
36 /*
37 * Applies constant propagation/folding to the given function. The approach is
38 * [Sparse Conditional Constant Propagation](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation):
39 * we use abstract interpretation to record known constant values for identifiers,
40 * with lack of a value indicating that the identifier does not have a
41 * known constant value.
42 *
43 * Instructions which can be compile-time evaluated *and* whose operands are known constants
44 * are replaced with the resulting constant value. For example a BinaryExpression
45 * where the left value is known to be `1` and the right value is known to be `2`
46 * can be replaced with a `Constant 3` instruction.
47 *
48 * This pass also exploits the use of SSA form, tracking the constant values of
49 * local variables. For example, in `let x = 4; let y = x + 1` we know that
50 * `x = 4` in the binary expression and can replace the binary expression with
51 * `Constant 5`.
52 *
53 * This pass also visits conditionals (currently only IfTerminal) and can prune
54 * unreachable branches when the condition is a known truthy/falsey constant. The
55 * pass uses fixpoint iteration, looping until no additional updates can be
56 * performed. This allows the compiler to find cases where once one conditional is pruned,
57 * other values become constant, allowing subsequent conditionals to be pruned and so on.
58 */
59 export function constantPropagation(fn: HIRFunction): void {
60 const constants: Constants = new Map();
61 constantPropagationImpl(fn, constants);
62 }
63
64 function constantPropagationImpl(fn: HIRFunction, constants: Constants): void {
65 while (true) {
66 const haveTerminalsChanged = applyConstantPropagation(fn, constants);
67 if (!haveTerminalsChanged) {
68 break;
69 }
70 /*
71 * If terminals have changed then blocks may have become newly unreachable.
72 * Re-run minification of the graph (incl reordering instruction ids)
73 */
74 reversePostorderBlocks(fn.body);
75 removeUnreachableForUpdates(fn.body);
76 removeDeadDoWhileStatements(fn.body);
77 removeUnnecessaryTryCatch(fn.body);
78 markInstructionIds(fn.body);
79 markPredecessors(fn.body);
80
81 // Now that predecessors are updated, prune phi operands that can never be reached
82 for (const [, block] of fn.body.blocks) {
83 for (const phi of block.phis) {
84 for (const [predecessor] of phi.operands) {
85 if (!block.preds.has(predecessor)) {
86 phi.operands.delete(predecessor);
87 }
88 }
89 }
90 }
91 /*
92 * By removing some phi operands, there may be phis that were not previously
93 * redundant but now are
94 */
95 eliminateRedundantPhi(fn);
96 /*
97 * Finally, merge together any blocks that are now guaranteed to execute
98 * consecutively
99 */
100 mergeConsecutiveBlocks(fn);
101
102 assertConsistentIdentifiers(fn);
103 assertTerminalSuccessorsExist(fn);
104 }
105 }
106
107 function applyConstantPropagation(
108 fn: HIRFunction,
109 constants: Constants,
110 ): boolean {
111 let hasChanges = false;
112 for (const [, block] of fn.body.blocks) {
113 /*
114 * Initialize phi values if all operands have the same known constant value.
115 * Note that this analysis uses a single-pass only, so it will never fill in
116 * phi values for blocks that have a back-edge.
117 */
118 for (const phi of block.phis) {
119 let value = evaluatePhi(phi, constants);
120 if (value !== null) {
121 constants.set(phi.place.identifier.id, value);
122 }
123 }
124
125 for (let i = 0; i < block.instructions.length; i++) {
126 if (block.kind === 'sequence' && i === block.instructions.length - 1) {
127 /*
128 * evaluating the last value of a value block can break order of evaluation,
129 * skip these instructions
130 */
131 continue;
132 }
133 const instr = block.instructions[i]!;
134 const value = evaluateInstruction(constants, instr);
135 if (value !== null) {
136 constants.set(instr.lvalue.identifier.id, value);
137 }
138 }
139
140 const terminal = block.terminal;
141 switch (terminal.kind) {
142 case 'if': {
143 const testValue = read(constants, terminal.test);
144 if (testValue !== null && testValue.kind === 'Primitive') {
145 hasChanges = true;
146 const targetBlockId = testValue.value
147 ? terminal.consequent
148 : terminal.alternate;
149 block.terminal = {
150 kind: 'goto',
151 variant: GotoVariant.Break,
152 block: targetBlockId,
153 id: terminal.id,
154 loc: terminal.loc,
155 };
156 }
157 break;
158 }
159 default: {
160 // no-op
161 }
162 }
163 }
164
165 return hasChanges;
166 }
167
168 function evaluatePhi(phi: Phi, constants: Constants): Constant | null {
169 let value: Constant | null = null;
170 for (const [, operand] of phi.operands) {
171 const operandValue = constants.get(operand.identifier.id) ?? null;
172 // did not find a constant, can't constant propogate
173 if (operandValue === null) {
174 return null;
175 }
176
177 /*
178 * first iteration of the loop, let's store the operand and continue
179 * looping.
180 */
181 if (value === null) {
182 value = operandValue;
183 continue;
184 }
185
186 // found different kinds of constants, can't constant propogate
187 if (operandValue.kind !== value.kind) {
188 return null;
189 }
190
191 switch (operandValue.kind) {
192 case 'Primitive': {
193 CompilerError.invariant(value.kind === 'Primitive', {
194 reason: 'value kind expected to be Primitive',
195 loc: GeneratedSource,
196 });
197
198 // different constant values, can't constant propogate
199 if (operandValue.value !== value.value) {
200 return null;
201 }
202 break;
203 }
204 case 'LoadGlobal': {
205 CompilerError.invariant(value.kind === 'LoadGlobal', {
206 reason: 'value kind expected to be LoadGlobal',
207 loc: GeneratedSource,
208 });
209
210 // different global values, can't constant propogate
211 if (operandValue.binding.name !== value.binding.name) {
212 return null;
213 }
214 break;
215 }
216 default:
217 return null;
218 }
219 }
220
221 return value;
222 }
223
224 function evaluateInstruction(
225 constants: Constants,
226 instr: Instruction,
227 ): Constant | null {
228 const value = instr.value;
229 switch (value.kind) {
230 case 'Primitive': {
231 return value;
232 }
233 case 'LoadGlobal': {
234 return value;
235 }
236 case 'ComputedLoad': {
237 const property = read(constants, value.property);
238 if (
239 property !== null &&
240 property.kind === 'Primitive' &&
241 ((typeof property.value === 'string' &&
242 isValidIdentifier(property.value)) ||
243 typeof property.value === 'number')
244 ) {
245 const nextValue: InstructionValue = {
246 kind: 'PropertyLoad',
247 loc: value.loc,
248 property: makePropertyLiteral(property.value),
249 object: value.object,
250 };
251 instr.value = nextValue;
252 }
253 return null;
254 }
255 case 'ComputedStore': {
256 const property = read(constants, value.property);
257 if (
258 property !== null &&
259 property.kind === 'Primitive' &&
260 ((typeof property.value === 'string' &&
261 isValidIdentifier(property.value)) ||
262 typeof property.value === 'number')
263 ) {
264 const nextValue: InstructionValue = {
265 kind: 'PropertyStore',
266 loc: value.loc,
267 property: makePropertyLiteral(property.value),
268 object: value.object,
269 value: value.value,
270 };
271 instr.value = nextValue;
272 }
273 return null;
274 }
275 case 'PostfixUpdate': {
276 const previous = read(constants, value.value);
277 if (
278 previous !== null &&
279 previous.kind === 'Primitive' &&
280 typeof previous.value === 'number'
281 ) {
282 const next =
283 value.operation === '++' ? previous.value + 1 : previous.value - 1;
284 // Store the updated value
285 constants.set(value.lvalue.identifier.id, {
286 kind: 'Primitive',
287 value: next,
288 loc: value.loc,
289 });
290 // But return the value prior to the update
291 return previous;
292 }
293 return null;
294 }
295 case 'PrefixUpdate': {
296 const previous = read(constants, value.value);
297 if (
298 previous !== null &&
299 previous.kind === 'Primitive' &&
300 typeof previous.value === 'number'
301 ) {
302 const next: Primitive = {
303 kind: 'Primitive',
304 value:
305 value.operation === '++' ? previous.value + 1 : previous.value - 1,
306 loc: value.loc,
307 };
308 // Store and return the updated value
309 constants.set(value.lvalue.identifier.id, next);
310 return next;
311 }
312 return null;
313 }
314 case 'UnaryExpression': {
315 switch (value.operator) {
316 case '!': {
317 const operand = read(constants, value.value);
318 if (operand !== null && operand.kind === 'Primitive') {
319 const result: Primitive = {
320 kind: 'Primitive',
321 value: !operand.value,
322 loc: value.loc,
323 };
324 instr.value = result;
325 return result;
326 }
327 return null;
328 }
329 case '-': {
330 const operand = read(constants, value.value);
331 if (
332 operand !== null &&
333 operand.kind === 'Primitive' &&
334 typeof operand.value === 'number'
335 ) {
336 const result: Primitive = {
337 kind: 'Primitive',
338 value: operand.value * -1,
339 loc: value.loc,
340 };
341 instr.value = result;
342 return result;
343 }
344 return null;
345 }
346 default:
347 return null;
348 }
349 }
350 case 'BinaryExpression': {
351 const lhsValue = read(constants, value.left);
352 const rhsValue = read(constants, value.right);
353 if (
354 lhsValue !== null &&
355 rhsValue !== null &&
356 lhsValue.kind === 'Primitive' &&
357 rhsValue.kind === 'Primitive'
358 ) {
359 const lhs = lhsValue.value;
360 const rhs = rhsValue.value;
361 let result: Primitive | null = null;
362 switch (value.operator) {
363 case '+': {
364 if (typeof lhs === 'number' && typeof rhs === 'number') {
365 result = {kind: 'Primitive', value: lhs + rhs, loc: value.loc};
366 } else if (typeof lhs === 'string' && typeof rhs === 'string') {
367 result = {kind: 'Primitive', value: lhs + rhs, loc: value.loc};
368 }
369 break;
370 }
371 case '-': {
372 if (typeof lhs === 'number' && typeof rhs === 'number') {
373 result = {kind: 'Primitive', value: lhs - rhs, loc: value.loc};
374 }
375 break;
376 }
377 case '*': {
378 if (typeof lhs === 'number' && typeof rhs === 'number') {
379 result = {kind: 'Primitive', value: lhs * rhs, loc: value.loc};
380 }
381 break;
382 }
383 case '/': {
384 if (typeof lhs === 'number' && typeof rhs === 'number') {
385 result = {kind: 'Primitive', value: lhs / rhs, loc: value.loc};
386 }
387 break;
388 }
389 case '|': {
390 if (typeof lhs === 'number' && typeof rhs === 'number') {
391 result = {kind: 'Primitive', value: lhs | rhs, loc: value.loc};
392 }
393 break;
394 }
395 case '&': {
396 if (typeof lhs === 'number' && typeof rhs === 'number') {
397 result = {kind: 'Primitive', value: lhs & rhs, loc: value.loc};
398 }
399 break;
400 }
401 case '^': {
402 if (typeof lhs === 'number' && typeof rhs === 'number') {
403 result = {kind: 'Primitive', value: lhs ^ rhs, loc: value.loc};
404 }
405 break;
406 }
407 case '<<': {
408 if (typeof lhs === 'number' && typeof rhs === 'number') {
409 result = {kind: 'Primitive', value: lhs << rhs, loc: value.loc};
410 }
411 break;
412 }
413 case '>>': {
414 if (typeof lhs === 'number' && typeof rhs === 'number') {
415 result = {kind: 'Primitive', value: lhs >> rhs, loc: value.loc};
416 }
417 break;
418 }
419 case '>>>': {
420 if (typeof lhs === 'number' && typeof rhs === 'number') {
421 result = {
422 kind: 'Primitive',
423 value: lhs >>> rhs,
424 loc: value.loc,
425 };
426 }
427 break;
428 }
429 case '%': {
430 if (typeof lhs === 'number' && typeof rhs === 'number') {
431 result = {kind: 'Primitive', value: lhs % rhs, loc: value.loc};
432 }
433 break;
434 }
435 case '**': {
436 if (typeof lhs === 'number' && typeof rhs === 'number') {
437 result = {kind: 'Primitive', value: lhs ** rhs, loc: value.loc};
438 }
439 break;
440 }
441 case '<': {
442 if (typeof lhs === 'number' && typeof rhs === 'number') {
443 result = {kind: 'Primitive', value: lhs < rhs, loc: value.loc};
444 }
445 break;
446 }
447 case '<=': {
448 if (typeof lhs === 'number' && typeof rhs === 'number') {
449 result = {kind: 'Primitive', value: lhs <= rhs, loc: value.loc};
450 }
451 break;
452 }
453 case '>': {
454 if (typeof lhs === 'number' && typeof rhs === 'number') {
455 result = {kind: 'Primitive', value: lhs > rhs, loc: value.loc};
456 }
457 break;
458 }
459 case '>=': {
460 if (typeof lhs === 'number' && typeof rhs === 'number') {
461 result = {kind: 'Primitive', value: lhs >= rhs, loc: value.loc};
462 }
463 break;
464 }
465 case '==': {
466 result = {kind: 'Primitive', value: lhs == rhs, loc: value.loc};
467 break;
468 }
469 case '===': {
470 result = {kind: 'Primitive', value: lhs === rhs, loc: value.loc};
471 break;
472 }
473 case '!=': {
474 result = {kind: 'Primitive', value: lhs != rhs, loc: value.loc};
475 break;
476 }
477 case '!==': {
478 result = {kind: 'Primitive', value: lhs !== rhs, loc: value.loc};
479 break;
480 }
481 default: {
482 break;
483 }
484 }
485 if (result !== null) {
486 instr.value = result;
487 return result;
488 }
489 }
490 return null;
491 }
492 case 'PropertyLoad': {
493 const objectValue = read(constants, value.object);
494 if (objectValue !== null) {
495 if (
496 objectValue.kind === 'Primitive' &&
497 typeof objectValue.value === 'string' &&
498 value.property === 'length'
499 ) {
500 const result: InstructionValue = {
501 kind: 'Primitive',
502 value: objectValue.value.length,
503 loc: value.loc,
504 };
505 instr.value = result;
506 return result;
507 }
508 }
509 return null;
510 }
511 case 'TemplateLiteral': {
512 if (value.subexprs.length === 0) {
513 const result: InstructionValue = {
514 kind: 'Primitive',
515 value: value.quasis.map(q => q.cooked).join(''),
516 loc: value.loc,
517 };
518 instr.value = result;
519 return result;
520 }
521
522 if (value.subexprs.length !== value.quasis.length - 1) {
523 return null;
524 }
525
526 if (value.quasis.some(q => q.cooked === undefined)) {
527 return null;
528 }
529
530 let quasiIndex = 0;
531 let resultString = value.quasis[quasiIndex].cooked as string;
532 ++quasiIndex;
533
534 for (const subExpr of value.subexprs) {
535 const subExprValue = read(constants, subExpr);
536 if (!subExprValue || subExprValue.kind !== 'Primitive') {
537 return null;
538 }
539
540 const expressionValue = subExprValue.value;
541 if (
542 typeof expressionValue !== 'number' &&
543 typeof expressionValue !== 'string' &&
544 typeof expressionValue !== 'boolean' &&
545 !(typeof expressionValue === 'object' && expressionValue === null)
546 ) {
547 // value is not supported (function, object) or invalid (symbol), or something else
548 return null;
549 }
550
551 const suffix = value.quasis[quasiIndex].cooked;
552 ++quasiIndex;
553
554 if (suffix === undefined) {
555 return null;
556 }
557
558 /*
559 * Spec states that concat calls ToString(argument) internally on its parameters
560 * -> we don't have to implement ToString(argument) ourselves and just use the engine implementation
561 * Refs:
562 * - https://tc39.es/ecma262/2024/#sec-tostring
563 * - https://tc39.es/ecma262/2024/#sec-string.prototype.concat
564 * - https://tc39.es/ecma262/2024/#sec-template-literals-runtime-semantics-evaluation
565 */
566 resultString = resultString.concat(expressionValue as string, suffix);
567 }
568
569 const result: InstructionValue = {
570 kind: 'Primitive',
571 value: resultString,
572 loc: value.loc,
573 };
574
575 instr.value = result;
576 return result;
577 }
578 case 'LoadLocal': {
579 const placeValue = read(constants, value.place);
580 if (placeValue !== null) {
581 instr.value = placeValue;
582 }
583 return placeValue;
584 }
585 case 'StoreLocal': {
586 const placeValue = read(constants, value.value);
587 if (placeValue !== null) {
588 constants.set(value.lvalue.place.identifier.id, placeValue);
589 }
590 return placeValue;
591 }
592 case 'ObjectMethod':
593 case 'FunctionExpression': {
594 constantPropagationImpl(value.loweredFunc.func, constants);
595 return null;
596 }
597 case 'StartMemoize': {
598 if (value.deps != null) {
599 for (const dep of value.deps) {
600 if (dep.root.kind === 'NamedLocal') {
601 const placeValue = read(constants, dep.root.value);
602 if (placeValue != null && placeValue.kind === 'Primitive') {
603 dep.root.constant = true;
604 }
605 }
606 }
607 }
608 return null;
609 }
610 default: {
611 // TODO: handle more cases
612 return null;
613 }
614 }
615 }
616
617 /*
618 * Recursively read the value of a place: if it is a constant place, attempt to read
619 * from that place until reaching a primitive or finding a value that is unset.
620 */
621 function read(constants: Constants, place: Place): Constant | null {
622 return constants.get(place.identifier.id) ?? null;
623 }
624
625 type Constant = Primitive | LoadGlobal;
626 type Constants = Map<IdentifierId, Constant>;