[LLVMdev] Trace Use-Def chain

[tarun agrawal]

Hi,

I need to get all the basic blocks that are there, in the path from definition of an instruction to use of that instruction.


Regards
Tarun

[tarun agrawal]

HI

I know it is a very simple question not worth asking here but I am really struggling pls help me out..

[John Criswell]

On 5/3/11 4:08 PM, tarun agrawal wrote:

HI

I know it is a very simple question not worth asking here but I am really struggling pls help me out..

This is a question worth asking; it's just that not everyone can answer all the time.
:)

If all you want to do is to follow the SSA def-use chain within a single function, then this is very easy.  All you have to do is use the use_iterator of the Instruction object to iterate through its def-use chain.  For all uses that are instructions, use the getParent() method to find the basic block containing the instruction.  That's it.

This approach won't work in two cases:

1) If you want to trace def/use through memory.  Memory is not in SSA form, and so you have to use extra analysis to track from which store the result of a load originates.

2) If you want to track def/use inter-procedurally through function arguments and return values.  If you don't care about tracking through memory, this is a fairly easy inter-procedural analysis to do, and we have some code internally at University of Illinois that does it.  If you need it, I can talk to Vikram and see if we can give you a copy.

For more information on how to iterate through def-use chains, see the LLVM Programmer's Manual:
http://llvm.org/docs/ProgrammersManual.html#iterate_chains

-- John T.

On Tue, May 3, 2011 at 10:10 PM, tarun agrawal <ta...@cse.iitb.ac.in> wrote:

Hi,

I need to get all the basic blocks that are there, in the path from definition of an instruction to use of that instruction.


Regards
Tarun

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[John Criswell]

Dear Tarun,

It just occurred to me that this may or may not be what you are asking about.  This only finds basic blocks along the def-use chain of an instruction; it does not find all basic blocks along all paths between two instructions.  I don't know of an algorithm off-hand for the latter, but if you understand how to iterate over def-use chains and the control-flow graph, then writing up an algorithm for the latter should be pretty easy.

-- John T.

[tarun agrawal]

Thanks John,

I know how to iterate through def-use chains and I also have realized the need for an algorithm to do the work. But the algorithm I am able to figure out is not linear in time. It wold be a great help  if someone suggest me a way to get all basic-block along all path between two instruction.

[John Criswell]

On 5/4/11 1:37 AM, tarun agrawal wrote:

Thanks John,

I know how to iterate through def-use chains and I also have realized the need for an algorithm to do the work. But the algorithm I am able to figure out is not linear in time. It wold be a great help  if someone suggest me a way to get all basic-block along all path between two instruction.

I don't know of an algorithm off-hand.  I suspect that this is the point where you'll need to sit down with a compiler or graph theory textbook and either find an algorithm or develop one on your own.

One thing that might help would be to think if using dominator and post-dominator information could speed up the process.  I'm not sure if it would lead to a faster algorithm, but if I had to develop such an algorithm, that's where I'd start.

Also, non-linear algorithms are fine on small inputs.  You only need to find a better algorithm if your analysis is taking too long to complete or a professor/adviser/boss is telling you it has to be better.
:)

-- John T.

[Andrew Trick]

On May 3, 2011, at 11:37 PM, tarun agrawal wrote:

Thanks John,

I know how to iterate through def-use chains and I also have realized the need for an algorithm to do the work. But the algorithm I am able to figure out is not linear in time. It wold be a great help  if someone suggest me a way to get all basic-block along all path between two instruction.

I may be too late responding to be helpful. But this should be easy to do in linear time (disregarding the set lookup time) by maintaining a set of visited blocks and pushing each predecessor block that has not yet been visited on the worklist. Stop pushing predecessors when you reach the def's block. When the worklist is empty, you have all blocks in the set.

-Andy