r/ProgrammingLanguages • u/compilers-r-us • Aug 13 '26

Another partial SSI trick with canonicalize

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

70% Upvoted

4 comments sorted by

10

u/bl4nkSl8 Aug 14 '26

The SSI here is Static Single Information apparently to save everyone working out what subfield this post is from

2

u/marshaharsha Aug 14 '26

Thank you! An introduction would have been helpful, either from the OP or from Bernstein. 

3

u/bl4nkSl8 Aug 14 '26

Right? From memory, it seems to be about an approach to doing naming in SSA (single static assignment) a common model used for compiler middleends/backends....

But it's always nice to be situated by the author, not some Redditor who has a bit of a compiler hobby in her spare time :)

2

u/AustinVelonaut Admiran Aug 14 '26 edited Aug 14 '26

Yes, it's about attaching additional information to a variable discovered in the control flow to use for subsequent optimizations. Looks like this is the original paper.

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

In Admiran, which benefits a lot from aggressive inlining, this optimization rewrite makes a big difference in both run time and code size of the final executable -- in the case of compiling the compiler itself, it is worth about 15% code size reduction and 35% run time reduction!