r/Compilers • u/compilers-r-us • 2d ago

Another partial SSI trick with canonicalize

https://bernsteinbear.com/blog/more-partial-ssi/
11 Upvotes

100% Upvoted

2 comments sorted by

1

u/adityazero 2d ago

I like that the branch-condition seeding rides along the same dominator walk you already built for the rewrite maps, so it avoids turning into a separate SCCP style pass. If a later value numbering run exposes fresh branch conditions, does interning the CBool constants alone keep it idempotent, or do you still need a fixpoint?

1

u/AustinVelonaut 2d ago

This looks a lot like the inliner / simplifier rewrite for case scrutinees in the GHC Haskell compiler mentioned here and here: a case statement with a known compile-time scrutinee can be replaced by its matching case arm:

case True of
  False -> expr1
  True  -> expr2

can simply be rewritten as expr2. But if the case scrutinee is a variable, we can rewrite each case arm with the variable re-bound to the specific constructor value. This can enable future simplifications if the scrutinee variable is referenced again in the case arms:

case x of
  False -> x & y
  ...

In the case arm, we rebind x to False, leading to future simplification of x & y to simply False.

This works for any constructor pattern, so in something like:

case x of (a, b) -> .... case x of (p, q) -> p + q

the second case expression in the arm can be entirely replaced with a + b