[LLVMdev] Pool Allocation and DSA

[Patrick Alexander Simmons]

Thank you, and I apologize for conflating the two passes.

My main remaining concern is about what happens when there is a node in 
a function's DSGraph that points to a pool (or pools, if there are 
multiple callers) that is not in the DSGraph of that function.  For 
example, on page 3 of the 2005 PLDI paper, the DSGraph given for 
createnode(), Data is pointing to an unlabeled node in the graph.  I 
would like to know specifically what this node is and what would happen 
if getPool() were called on it.  My best guess is that getPool() would 
return NULL.

Moreover, it seems like it should be possible to call a Function with a 
pointer without passing in the pointer's pool, as long as no allocations 
are done using the pointer.  What will the DSNode for that pointer in 
the function's graph look like?  What edges will be coming out of it?

Also, after thinking about it for a while, I don't think it's ever 
possible for a node in the global DSGraph to have pointers to a pool 
that is not also global, thus preventing the problem of a global node 
having pointers into some function's DSGraph.  Am I right?

Thank you again,
--Patrick

John Criswell wrote:
> 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.
>