Partial static single information form

In compilers, static single information form (SSI) is a common extension to static single assignment form (SSA). It was introduced by C. Scott Ananian in 1999 in his MS thesis (PDF) 1. SSI extends your existing SSA intermediate representation by discovering facts from your existing program and reifying them as path-dependent/flow-sensitive IR nodes. That might sound complicated, but at least the basic idea is pretty natural. I talk a little bit about it in What I talk about when I talk about IRs and I’ll rehash here in more depth, starting with some motivating examples. Consider this admittedly contrived example: v0: Integer = ... if v0 > 0: # ... v1: PositiveInteger = AbsoluteValue v0 # ... We should be able to learn from the comparison that in some branches in the IR, v0 is positive. In that region, we can add a new IR instruction v2 that attaches that knowledge right in the instruction’s type field (yay, sparseness!) and then rewrite uses of v0 to now use v2. v0: Integer = ... if…