Joel led a discussion of the 3 (or 5) Phases/Problems we need to deal with.
- Structure Analysis
- The goal of this phase is to annotate the CFG to create a mapping
from merge points in the CFG back to the the branch that split apart
the paths that are now merging back together. These annotations can
be used to identify when two merging paths were created by a branch
that was controlled by a runtime-constant. We need this information in
the BTA pass to make the meet operation more precise.
- Previous work in BTA has been expressed in terms of AST's, so
this pre-processing phase was not required (with AST's identifying the
merges corresponding to branches that are controlled by
runtime-constants is a trivial problem).
- Ignoring loops, it seems fairly likely that this could be
computed by looking at a control dependence graph or a dominator tree
or some similiar data structure. Loops might be more complicated.
I believe that Joel is working on the details of an algorithm for next
week.
- This pass could also verify that it actually makes sense to fully
unroll loops that have been flagged by the user.
- Binding Time Analysis (BTA)
- The goal is to identify all the variables (source and compiler
induced temporaries) that are runtime-constants. We start with the
set of variables that the user has marked as runtime-constants, and
try to show that additional variables are runtime-constants as a
result of the current set of runtime-constants.
- This can be expressed as a dataflow problem that looks more or
less like standard constant prop.
- Based on the results of BTA, we create set-up code and templates.
- Apply all the standard compiler optimizations.
- We may need to do some tweaking to make sure that things don't
get screwed up by later optimizations. In paritcular, we need to
insert optimization barriers to prevent templates and set-up code from
being intermingled with each other and with other (normal) code.
- Stitching
- This is the only one of these phases that actually happens at
runtime (dynamic compilation time). Basically, we just exectute the
setup code, which stamps out a template and splices it in and then away we go.