llvm dev - Mar 2011 - [LLVMdev] standard Data Flow Analysis available in LLVM?

I am working on implementing an algorithm that needs one of the standard 
Data Flow Analysis as its precondition (VeryBusyExpression to be precise).
Thus I take a look into LLVM (2.8) and check their availability.

I do expect to see all of the following standard ones:
- Reaching Definition (RD)
- Live Variable (LV)
- Available Expression (AE)
- Very Busy Expression (VBE)

To my surprise, I didn't find any. The only one that is kind of close to 
what I am looking for is: lib/Analysis/LiveValue.cpp

I wonder what happens with all the standard DataFlow Analysis Passes? Do 
they ever exist?

I know LLVM is based on SSA, which may utilize algorithms that bypassing 
the standard Data Flows.

I am asking for suggestions if I do need these DataFlow ones, assuming I 
don't have to write them myself.

Thank you very much

Chuck

Chuck Zhao <czhao at eecg.toronto.edu> writes:
> I am working on implementing an algorithm that needs one of the standard 
> Data Flow Analysis as its precondition (VeryBusyExpression to be precise).
> Thus I take a look into LLVM (2.8) and check their availability.
>
> I do expect to see all of the following standard ones:
> - Reaching Definition (RD)
LLVM uses SSA.  You don't need reaching definitions.
> - Live Variable (LV)
Ditto (at least not the traditional kind).  The one in codegen is for
after out-of-ssa conversion.  And the codegen one's not live value
analysis, it's live interval analysis, which is slightly different.
> - Available Expression (AE)
There is a global value numbering pass, which is similar to CSE and
needs an analysis analogous to AE.
> - Very Busy Expression (VBE)
I don't think anyone's looked at this.
> I am asking for suggestions if I do need these DataFlow ones, assuming I 
> don't have to write them myself.
A lot of stuff kind of happens "behind the scenes" in places like
instcombine and DAG construction.  DAG construction in particular does
CSE on-the-fly, which is probably why no one has written a separate pass
to do it.  It relies on properties of the DAG IR to determine when
expressions are equivalent.

You can look at SparsePropagation for a somewhat generic dataflow
solver.

                                   -Dave