Re: register allocation: basic blocks, liveness and next use

kphillips <kevin.phillips83@yahoo.com> 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 temporaries 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 temporaries 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
temporary 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
temporaries. 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 temporaries' 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.

Return to the comp.compilers page.
Search the comp.compilers archives again.