[LLVMdev] Computing live values

[Vikram Adve]

On May 11, 2005, at 3:03 PM, Chris Lattner wrote:

> On Wed, 11 May 2005, Alkis Evlogimenos wrote:
>> On Wed, 2005-05-11 at 13:17 -0500, Chris Lattner wrote:
>>> On Wed, 11 May 2005, Vladimir Prus wrote:
>>>> 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. :)  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


> 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
>
> -- 
> http://nondot.org/sabre/
> http://llvm.cs.uiuc.edu/
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://mail.cs.uiuc.edu/mailman/listinfo/llvmdev