[LLVMdev] standard Data Flow Analysis available in LLVM?

[David A. Greene]

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