[LLVMdev] Computing live values

[Chris Lattner]

On Thu, 12 May 2005, Vladimir Prus wrote:
> I'm afraid checking liveness at a different basic block is exactly what I
> want. Here's a full context. I have an interval in a CFG, suppose that
> interval has no loops -- so it's just a non-looping single entry region.
>
>         1
>        / \
>       /   \
>      2     3
>     / \   /
>    /   \ /
>         4
>         |
>
> I want to add some "gate block" that will check certain condition and either
> execute all basic blocks in the interval, or bypass them all:
>
>         [gate]
>         /   |
>        1    |
>       /     |
>      2      |
>      \      |
>       3     |
>        \    |
>         4   |
>          \  |
>          [merge]
>
> For each value computed inside interval and used outside of interval, I add
> phi nodes at the 'merge' block like this:
>
>   tmp.xxx = phi int [ undef, %gate], [ %whatever, %4]

Ok.  This seems like it could be done with a simple extension of the 
little loop I gave, which checks to see if the using parent is in the 
interval or not.

> Finding all values computed inside interval is easy -- just a scan over all
> basic blocks. Finding all values used outside is easy too -- just scan over
> all uses with a check if parent basic block is in interval.

Yup.

> However, I'm not happy with the fact that I repeat those scans for all 1-order
> intervals, then for 2-order interval and so on. If I have a set of live vars
> for each basic block, then I can compute all vars live after interval my
> merging sets of live vars for each exit block, which is much more elegant.
> And substracting the set of values live at entry block, I get the set of
> values for which I need phi nodes.

Ok.

> I probably can get the desired effect by converting all values into allocas,
> doing my transform and then running mem2reg but that seems like real overkill.

This is really the approach I would suggest.  However, if you really want 
to do this, I would suggest taking a look at 
lib/CodeGen/LiveVariables.cpp.  The "virtual registers" in the backend are 
in SSA form, so this implements a simple sparse SSA live-variable analysis 
algorithm.  You can't use the code but perhaps the algorithm 
implementation will help.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.cs.uiuc.edu/