[LLVMdev] Pool Allocation and DSA

[John Criswell]

Patrick Alexander Simmons wrote:
> I don't really have a specific question, but, as I've been looking 
> through pool allocation and the DS graphs extensively, I wanted to 
> verify that my understanding of the representations used is correct.  
> Therefore, I'm summarizing my understanding below (which, if it's 
> correct, may hopefully be helpful to others).  I would appreciate if 
> someone who understands pool allocation well would comment on whether 
> I'm right in my understanding.
>
> After pool allocation runs, each Function is associated with a DS 
> graph.  Each node in a Function's DS graph falls into one of the 
> following categories:
>
> 1.  The node corresponds to a global pool.
> 2.  The node corresponds to a pool created by the Function.
> 3.  The node corresponds to a formal parameter passed to the function 
> (and is the result of conservatively folding all possible actual 
> parameters that may be passed to the function).
> 4.  The node corresponds to a pool parameter passed to the Function.
> 5.  The node is not in categories 1-4, in which case it must be pointed 
> to by some other pool which either is in categories 1-4 or is pointed to 
> by some other node, for which the same condition must hold.  That is to 
> say, all nodes in the graph must be reachable by following the edges of 
> the nodes in categories 1-4.
>   
I don't believe this is correct, or, at the very least, you are using 
confusing terminology.

First, DSA and Pool Allocation are two completely different things.  DSA 
is a points-to analysis.  It creates a graph (one per function + 1 
global graph for global variables) where each node represents a set of 
memory objects and the edges represent pointers within one memory object 
that point to another memory object (i.e. if node A points to node B, 
that means a field in one of the objects in node A points to an object 
in node B).  The DSGraph also contains a ScalarMap which maps LLVM 
Values to nodes in the graph (these nodes are called DSNodes).  DSA is 
somewhat special because it attempts to disambiguate different linked 
data structures within programs (hence the name Data Structure Analysis, 
or DSA).

Automatic Pool Allocation (APA) is a transform that is built on top of 
DSA.  It uses the points-to graphs computed by DSA to group allocations 
into various pools.  The original idea was to place nodes of the same 
pointer-based data structure into the same pool to get better cache 
locality.  The pools that Automatic Pool Allocation creates can either 
be global variables or local alloca'ed memory, depending upon how long 
the pool must be alive, what heuristics Automatic Pool Allocation is 
using, and whether the DSA results are context sensitive or 
insensitive.  When a pool is created based on context sensitive results, 
it is stack allocated and passed around as an argument to functions.

However, Automatic Pool Allocation has another use beyond improving 
performance.  It turns out that if you allocate memory based on the 
points-to analysis results, you can speed up run-time checks for memory 
safety.  This leads to SAFECode: a transform built on top of Automatic 
Pool Allocation that adds additional information to each pool to 
implement fast run-time checks.

Transforms like SAFECode need to know the mapping between the pointers 
in a program and the pool in which those pointers were assigned (more 
accurately, the pool in which the memory objects pointed to by those 
pointers were allocated).  The easiest way to do this was to have 
SAFECode query Automatic Pool Allocation.  This is, therefore, the 
purpose of getPool(): it allows other LLVM passes to ask Automatic Pool 
Allocation what pool a particular LLVM Value lives in.  The pool is 
returned as an LLVM Value *.  Depending on whether the pool is global, 
stack allocated, or passed into the function determines whether it is an 
LLVM GlobalVariable *, LLVM AllocaInst *, or LLVM Argument *.

-- John T.

> I'm guessing that the "getPool()" function in 
> llvm-poolalloc/include/poolalloc/PoolAllocate.h will return NULL if the 
> DSNode is in categories 3 or 5, will return a pointer to the Instruction 
> that created the pool for category 2, will return a pointer to the 
> global Value representing the pool for category 1, and will return a 
> pointer to the pool's Argument for category 4 -- but those are really 
> only guesses, and I'd very much appreciate confirmation that I guessed 
> right :)
>
> Thanks in advance for your help,
> --Patrick
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>