[LLVMdev] Writing a dataflow analysis

[Chris Lattner]

On Tue, 5 Jul 2005, Silken Tiger wrote:
> I have just taken a look at the LLVM-compiler and i am trying to write a pass
> which analyses the dataflow and sideeffects.

ok

> So far i have written my own pass which works and i can traverse the blocks,
> functions and instructions. Currently i am using the "runOnFunction" function
> and iterate over the functions and blocks. But this seems to be not optimal
> since the instructions itself seem to be organized as a tree...

Sure, make sure to take a look at these two docs, they might be helpful:

http://llvm.cs.uiuc.edu/docs/WritingAnLLVMPass.html
http://llvm.cs.uiuc.edu/docs/ProgrammersManual.html#common

> I suspect there is a more sensible way to get the dataflow start and 
> endpoints out of the structure?

If you're looking at operating on "expression trees", I would recommend 
considering single-use instructions as an interior part of an expression 
tree.

For example, if you have:

X = (A+B)+C;

In LLVM, you'll get the equivalent of this:

T = A+B
X = T+C

To get the original "tree" back, just notice that the 'T' instruction only 
has a single using instruction.  This allows you to follow the use-def and 
def-use chains up and down the tree.

-Chris

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