[LLVMdev] Computing live values

[Vladimir Prus]

On Thursday 12 May 2005 04:56, Vikram Adve wrote:

> > Good point. :)  If PHI nodes matter (depends on your application), it
> > would turn into something like this:
> >
> > bool LiveOutsideOfBlock(Instruction *I) {
> >   for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI
> > != E; ++UI)
> >        if (cast<Instruction>(*UI))->getParent() != I->getParent() ||
> >            isa<PHINode>(*UI))
> >          return true;
> >     return false;
> > }
>
> I think this only works if you are checking if an instruction is live
> at the end of it's own basic block, not any other basic block.  To
> check liveness at an arbitrary basic block (arbitrary except it must be
> dominated by the block containing the instruction), you cannot use SSA
> or dominance properties.  You need a liveness analysis, such as "Live
> Variables" dataflow analysis.

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]

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.

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. 

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.

- Volodya