Writing a dataflow analysis

Hi

I have just taken a look at the LLVM-compiler and i am trying to write a pass
which analyses the dataflow and sideeffects.

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...

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

Thanks for any directions or hints
ST

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