Computing live values

Say I want to find all LLVM Value*-es that a live on exit from a basic block.
What's the best way?

- The 'LiveRange', 'LiveVariables' and 'LiveIntervals' classes seem to be tied
to register allocation.
- The ./lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.h file seem to provide
what I need, but it's no a public header.

- Volodya

This is overkill. I would suggest 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()) return true;
   return false;
}

-Chris

Good point. :slight_smile: 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;
}

This assumes that it is okay to treat phi uses in successor blocks as uses outside of the block, which, again, depends on the application.

-Chris

Say I want to find all LLVM Value*-es that a live on exit from a basic block.
What's the best way?

- The 'LiveRange', 'LiveVariables' and 'LiveIntervals' classes seem to be tied
to register allocation.
- The ./lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.h file seem to provide
what I need, but it's no a public header.

This is overkill. I would suggest 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()) return true;
   return false;
}

Is this really going to work? What if the value is used in a loop and it
is used by a phi-node in the same block it is defined?

Good point. :slight_smile: 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.

--Vikram

> Good point. :slight_smile: 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

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