[LLVMdev] IR Liveness Analysis?

[Andrew Trick]

> On Jul 16, 2014, at 2:51 PM, Philip Reames <listmail at philipreames.com> wrote:
> 
> Is anyone aware of an existing framework for asking liveness questions about SSA values in the IR?  I'm looking for something more precise than the trivial definition provided by SSA itself.  I can write something myself (and will if need be), but it seemed like a generic enough problem that I was surprised I couldn't find something already in tree.  Anyone know of something I've missed?
> 
> The problem I'm trying to solve is identifying pointers which might be live at a garbage collection safepoint.  This in the context of transforming the IR to insert a statepoint intrinsic to explicitly represent a possible object relocation.  We've been using a very straigh forward and, due to implementation simplicity, expensive estimation based on simple reachability*.  This suffices for correctness, but is not ideal from a performance perspective.  (To put it mildly.)
> 
> * For those curious, you can find the current implement by searching for "isLiveAtSafepoint" in https://github.com/AzulSystems/llvm-late-safepoint-placement/blob/master/lib/Transforms/Scalar/SafepointPlacementPass.cpp. It's a trivial reachability algorithm with special cases for inbound values into a phi and uses that are encountered along paths which contain the original definition.  We rerun the search once per potentially live value.  As you might imagine, that's a bit expensive.  :)
> 
> Philip

FWIW, "Computing Liveness Sets for SSA" by Boissinot is my favorite paper on liveness:
http://hal.inria.fr/docs/00/58/53/03/PDF/RR-7503.pdf

They describe a nice 2-pass data flow algorithm. I'm not aware that anyone has implemented this for LLVM. It works well if you can represent liveness as a bitset, but you'll probably be stuck with a DenseMap of pointer values which would not be efficient.

LLVM's own LiveVariables is a path-exploration that computes a set of blocks for each variable. You could actually add pointers to the safepoints as you go this way and don't need to store any liveness results. You just need a set of visited blocks as you traverse. The easiest thing to do is probably to port this from Machine IR to LLVM IR.

-Andy