Common subexpression elimination

[seizethedave]

Just to track the progress of the various subtasks. This is an elimination pass done right before code gen.

• [x] Basic CSE of expressions & statements.
• [x] Go thru all statements and apply CSE, if necessary.
  • [x] SForEach
  • [x] SIf
    • [x] should only hoist a declaration before the SIf if both branches of the statement contain the expr. (But this is complicated since the expr can also appear after the SIf.) Going to bandage this in second pass. (see below.)
• [x] Handle types. When a handle is modified, invalidate all handle instances of the same type.
  • [x] though, reassigning a handle var should only affect that var itself.
• [x] Make sure ELambda is working properly. (seems like it is.)
• [ ] Make sure ordered variable dependencies are emitted correctly. (waiting for inspiration on ways to test this.)
• [x] Fix excess temps generated from deeply nested compound expressions.
• [x] Do fixed point application of CSE process to handle cases that require multiple CSE passes.
• [x] Second pass which moves vars/temp vars to the last possible point where they can be safely computed. (Including conditionals.) This will fix the suboptimal locations CSE picks to install temp vars, and will fix SIf.
• [x] Finally, invoke elimination & second pass from main.py. Do some high level testing.

Expression localizing pass notes

• Visit a tree.
• Encounter a var binding (ELet or SDecl).
  • Move it down an SSeq until it can't legally move farther.
  • Move it into an Exp until it cannot legally move farther.
  • For SIf's, move it into the branch that uses the expression. If both branches use it, leave it before the SIf.

Assume that where the ELet or SDecl is encountered is sufficiently high in the tree that all references to it can use it.

[Calvin-L]

Common subexpression elimination seems to work and can now be enabled in main.py using the --cse flag.

Thanks for all your hard work on this, David!