kphillips <kevin.phillips83@[EMAIL PROTECTED]
> writes:
> ...
> I've just implemented register allocation by splitting three address
> code instructions into basic blocks, and computing liveness and next
> use for each block. I'm assuming that all variables are live at the
> end of the block, and all tem****aries dead, and move backwards.
>
> This technique works well, except for the following scenario.
> [expression containing procedure calls as subexpressions]
> ...
> Am I missing something here?...
Because the lifetime of each of your tem****aries is contained within a
single expression, and because an expression is usually contained
within a single basic block, you are expecting the lifetime of each
tem****ary to be contained within a single basic block. But sometimes
an expression can contain control flow, and hence be divided across
multiple basic blocks, resulting in multi-block lifetimes for
tem****aries. You found one case of this. Another case arises if you
have conditional (if-then-else) expressions, such as the ternary ?:
operator in C-family languages, or short-circuit boolean operators,
such as the && and || operators in C-family langauges.
If your language has only procedure calls as intra-expression control
flow, and if the only reason you are breaking the code into basic
blocks is for your local register allocation, then the simplest
solution would be to treat procedure calls as block boundaries. The
blocks won't be basic blocks any more -- but they probably will be
what you want.
But if you are going to accommodate other control flow within
expressions (such as from ?:, &&, ||), then I think that you are going
to have to make some more major change in the structure of your
compiler. Off the top of my head, here are some options that seem
plausible:
(0) Bite the bullet and do global analysis -- but I know you are
setting that option aside.
(1) Transform the source program (for example, by AST rewriting prior
to translation to a three-address code) so as to not have any
control flow within an expression. This would entail introducing
extra variables and breaking statements containing complex
expressions into multiple statements.
(2) Rather than breaking the three-address code into blocks based only
on information within the three-address code (such as the control
flow instructions or the non-procedure-call control flow
instructions), break the three-address code into blocks at
boundaries that correspond to the source-level statements. That
way,q tem****aries' lifetimes will be contained within blocks. (The
blocks will again not be basic blocks.) This may require some
restructuring of your compiler if the information about
source-level statements is gone before you do the breaking into
blocks.
|
