dillon1000/react
Commit
Browse files Initial pass at dead code elimination
This is a first pass at DCE without having read any literate on the subject, so
lemme know if there's a better approach. That said the algorithm is:
* Keep a `Set<Identifier>` of identifiers that are used (and whose constructing
logic cannot be removed).
* Do a first RPO iteration of all block's phis. Any phi operand that
participates in a loop is preemptively marked as "used" even if it isn't
strictly used somewhere. This step is necessary bc these operands may otherwise
not be used.
* Do a second post-order iteration of all blocks, including iterating first
their terminals, then reverse iteration of instructions, then their phis. Mark
the operands of each as used as we encounter them, and prune instructions whose
lvalue is never used.
For now I was conservative about which types of instructions can be pruned. For
example, call instructions are never pruned, even if the result of the call is
never used.
However one catch is that we currently prune instructions that cause values to
become frozen. We had planned to add runtime calls (in dev) to freeze values for
runtime enforcement, and if we want to do that we can always add these
instructions back (or replace them with explicit freeze calls).
There are a few potential next steps but we should discuss whether they're worth
it:
* Use fixpoint iteration to find exactly which operands are actually used. This
would allow us to to prune cases such as `let x = 0; while (...) { x += 1 }` eg
where there's a phi but the result is never used. Such cases should be rare in
practice though.
* Eliminate more types of instructions, eg eliminate function calls that don't
have any mutable arguments.Changed paths41 files
First-parent comparisoncompiler/forget/src/CompilerPipeline.ts ModifiedM compiler/forget/src/Optimization/ConstantPropagation.ts ModifiedA compiler/forget/src/Optimization/DeadCodeElimination.ts AddedM compiler/forget/src/Optimization/index.ts ModifiedM compiler/forget/src/__tests__/fixtures/hir/_bug_expression-with-assignment.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/call.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/capturing-function-within-block.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/concise-arrow-expr.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/constant-propagation-for.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/constant-propagation-while.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/constant-propagation.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/constructor.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/dependencies-outputs.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/error.while-with-assignment-in-test.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/for-logical.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/hooks-freeze-possibly-mutable-arguments.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/issue852.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/method-call-computed.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/method-call-fn-call.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/method-call.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/object-computed-access-assignment.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/object-properties.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/reassignment-conditional.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/reassignment.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/reverse-postorder.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/sequence-expression.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/simple-alias.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/ssa-call-jsx.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/ssa-for-trivial-update.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/ssa-multiple-phis.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/ssa-objectexpression-phi.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/ssa-reassign.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/ssa-return.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/ssa-throw.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/ssa-while-no-reassign.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/switch-with-fallthrough.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/switch.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/ternary-expression.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/type-test-field-store.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/type-test-polymorphic.expect.md ModifiedM compiler/forget/src/__tests__/fixtures/hir/unconditional-break-label.expect.md ModifiedPatch
Files changed
Rendering syntax-highlighted changes…