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