1 //===-- PoolAllocate.cpp - Pool Allocation Pass ---------------------------===//
3 // This transform changes programs so that disjoint data structures are
4 // allocated out of different pools of memory, increasing locality and shrinking
7 //===----------------------------------------------------------------------===//
9 #include "llvm/Transforms/IPO/PoolAllocate.h"
10 #include "llvm/Transforms/CloneFunction.h"
11 #include "llvm/Analysis/DataStructure.h"
12 #include "llvm/Analysis/DataStructureGraph.h"
13 #include "llvm/Pass.h"
14 #include "llvm/Module.h"
15 #include "llvm/Function.h"
16 #include "llvm/iMemory.h"
17 #include "llvm/iTerminators.h"
18 #include "llvm/iOther.h"
19 #include "llvm/ConstantVals.h"
20 #include "llvm/Target/TargetData.h"
21 #include "llvm/Support/InstVisitor.h"
22 #include "Support/DepthFirstIterator.h"
23 #include "Support/STLExtras.h"
27 // FIXME: This is dependant on the sparc backend layout conventions!!
28 static TargetData TargetData("test");
31 // ScalarInfo - Information about an LLVM value that we know points to some
32 // datastructure we are processing.
35 Value *Val; // Scalar value in Current Function
36 DSNode *Node; // DataStructure node it points to
37 Value *PoolHandle; // PoolTy* LLVM value
39 ScalarInfo(Value *V, DSNode *N, Value *PH)
40 : Val(V), Node(N), PoolHandle(PH) {
41 assert(V && N && PH && "Null value passed to ScalarInfo ctor!");
45 // CallArgInfo - Information on one operand for a call that got expanded.
47 int ArgNo; // Call argument number this corresponds to
48 DSNode *Node; // The graph node for the pool
49 Value *PoolHandle; // The LLVM value that is the pool pointer
51 CallArgInfo(int Arg, DSNode *N, Value *PH)
52 : ArgNo(Arg), Node(N), PoolHandle(PH) {
53 assert(Arg >= -1 && N && PH && "Illegal values to CallArgInfo ctor!");
56 // operator< when sorting, sort by argument number.
57 bool operator<(const CallArgInfo &CAI) const {
58 return ArgNo < CAI.ArgNo;
62 // TransformFunctionInfo - Information about how a function eeds to be
65 struct TransformFunctionInfo {
66 // ArgInfo - Maintain information about the arguments that need to be
67 // processed. Each pair corresponds to an argument (whose number is the
68 // first element) that needs to have a pool pointer (the second element)
69 // passed into the transformed function with it.
71 // As a special case, "argument" number -1 corresponds to the return value.
73 vector<CallArgInfo> ArgInfo;
75 // Func - The function to be transformed...
78 // The call instruction that is used to map CallArgInfo PoolHandle values
79 // into the new function values.
83 TransformFunctionInfo() : Func(0), Call(0) {}
85 bool operator<(const TransformFunctionInfo &TFI) const {
86 if (Func < TFI.Func) return true;
87 if (Func > TFI.Func) return false;
88 if (ArgInfo.size() < TFI.ArgInfo.size()) return true;
89 if (ArgInfo.size() > TFI.ArgInfo.size()) return false;
90 return ArgInfo < TFI.ArgInfo;
93 void finalizeConstruction() {
94 // Sort the vector so that the return value is first, followed by the
95 // argument records, in order. Note that this must be a stable sort so
96 // that the entries with the same sorting criteria (ie they are multiple
97 // pool entries for the same argument) are kept in depth first order.
98 stable_sort(ArgInfo.begin(), ArgInfo.end());
103 // Define the pass class that we implement...
104 class PoolAllocate : public Pass {
105 // PoolTy - The type of a scalar value that contains a pool pointer.
110 // Initialize the PoolTy instance variable, since the type never changes.
111 vector<const Type*> PoolElements;
112 PoolElements.push_back(PointerType::get(Type::SByteTy));
113 PoolElements.push_back(Type::UIntTy);
114 PoolTy = PointerType::get(StructType::get(PoolElements));
115 // PoolTy = { sbyte*, uint }*
117 CurModule = 0; DS = 0;
118 PoolInit = PoolDestroy = PoolAlloc = PoolFree = 0;
123 // getAnalysisUsageInfo - This function requires data structure information
124 // to be able to see what is pool allocatable.
126 virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Required,
127 Pass::AnalysisSet &,Pass::AnalysisSet &) {
128 Required.push_back(DataStructure::ID);
132 // CurModule - The module being processed.
135 // DS - The data structure graph for the module being processed.
138 // Prototypes that we add to support pool allocation...
139 Function *PoolInit, *PoolDestroy, *PoolAlloc, *PoolFree;
141 // The map of already transformed functions... note that the keys of this
142 // map do not have meaningful values for 'Call' or the 'PoolHandle' elements
143 // of the ArgInfo elements.
145 map<TransformFunctionInfo, Function*> TransformedFunctions;
147 // getTransformedFunction - Get a transformed function, or return null if
148 // the function specified hasn't been transformed yet.
150 Function *getTransformedFunction(TransformFunctionInfo &TFI) const {
151 map<TransformFunctionInfo, Function*>::const_iterator I =
152 TransformedFunctions.find(TFI);
153 if (I != TransformedFunctions.end()) return I->second;
158 // addPoolPrototypes - Add prototypes for the pool methods to the specified
159 // module and update the Pool* instance variables to point to them.
161 void addPoolPrototypes(Module *M);
164 // CreatePools - Insert instructions into the function we are processing to
165 // create all of the memory pool objects themselves. This also inserts
166 // destruction code. Add an alloca for each pool that is allocated to the
167 // PoolDescriptors map.
169 void CreatePools(Function *F, const vector<AllocDSNode*> &Allocs,
170 map<DSNode*, Value*> &PoolDescriptors);
172 // processFunction - Convert a function to use pool allocation where
175 bool processFunction(Function *F);
177 // transformFunctionBody - This transforms the instruction in 'F' to use the
178 // pools specified in PoolDescriptors when modifying data structure nodes
179 // specified in the PoolDescriptors map. IPFGraph is the closed data
180 // structure graph for F, of which the PoolDescriptor nodes come from.
182 void transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
183 map<DSNode*, Value*> &PoolDescriptors);
185 // transformFunction - Transform the specified function the specified way.
186 // It we have already transformed that function that way, don't do anything.
187 // The nodes in the TransformFunctionInfo come out of callers data structure
190 void transformFunction(TransformFunctionInfo &TFI,
191 FunctionDSGraph &CallerIPGraph);
198 // isNotPoolableAlloc - This is a predicate that returns true if the specified
199 // allocation node in a data structure graph is eligable for pool allocation.
201 static bool isNotPoolableAlloc(const AllocDSNode *DS) {
202 if (DS->isAllocaNode()) return true; // Do not pool allocate alloca's.
204 MallocInst *MI = cast<MallocInst>(DS->getAllocation());
205 if (MI->isArrayAllocation() && !isa<Constant>(MI->getArraySize()))
206 return true; // Do not allow variable size allocations...
211 // processFunction - Convert a function to use pool allocation where
214 bool PoolAllocate::processFunction(Function *F) {
215 // Get the closed datastructure graph for the current function... if there are
216 // any allocations in this graph that are not escaping, we need to pool
217 // allocate them here!
219 FunctionDSGraph &IPGraph = DS->getClosedDSGraph(F);
221 // Get all of the allocations that do not escape the current function. Since
222 // they are still live (they exist in the graph at all), this means we must
223 // have scalar references to these nodes, but the scalars are never returned.
225 vector<AllocDSNode*> Allocs;
226 IPGraph.getNonEscapingAllocations(Allocs);
228 // Filter out allocations that we cannot handle. Currently, this includes
229 // variable sized array allocations and alloca's (which we do not want to
232 Allocs.erase(remove_if(Allocs.begin(), Allocs.end(), isNotPoolableAlloc),
236 if (Allocs.empty()) return false; // Nothing to do.
238 // Insert instructions into the function we are processing to create all of
239 // the memory pool objects themselves. This also inserts destruction code.
240 // This fills in the PoolDescriptors map to associate the alloc node with the
241 // allocation of the memory pool corresponding to it.
243 map<DSNode*, Value*> PoolDescriptors;
244 CreatePools(F, Allocs, PoolDescriptors);
246 // Now we need to figure out what called methods we need to transform, and
247 // how. To do this, we look at all of the scalars, seeing which functions are
248 // either used as a scalar value (so they return a data structure), or are
249 // passed one of our scalar values.
251 transformFunctionBody(F, IPGraph, PoolDescriptors);
257 class FunctionBodyTransformer : public InstVisitor<FunctionBodyTransformer> {
258 PoolAllocate &PoolAllocator;
259 vector<ScalarInfo> &Scalars;
260 map<CallInst*, TransformFunctionInfo> &CallMap;
262 const ScalarInfo &getScalar(const Value *V) {
263 for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
264 if (Scalars[i].Val == V) return Scalars[i];
265 assert(0 && "Scalar not found in getScalar!");
270 // updateScalars - Map the scalars array entries that look like 'From' to look
273 void updateScalars(Value *From, Value *To) {
274 for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
275 if (Scalars[i].Val == From) Scalars[i].Val = To;
279 FunctionBodyTransformer(PoolAllocate &PA, vector<ScalarInfo> &S,
280 map<CallInst*, TransformFunctionInfo> &C)
281 : PoolAllocator(PA), Scalars(S), CallMap(C) {}
283 void visitMemAccessInst(MemAccessInst *MAI) {
284 // Don't do anything to load, store, or GEP yet...
287 // Convert a malloc instruction into a call to poolalloc
288 void visitMallocInst(MallocInst *I) {
289 const ScalarInfo &SC = getScalar(I);
290 BasicBlock *BB = I->getParent();
291 BasicBlock::iterator MI = find(BB->begin(), BB->end(), I);
292 BB->getInstList().remove(MI); // Remove the Malloc instruction from the BB
294 // Create a new call to poolalloc before the malloc instruction
296 Args.push_back(SC.PoolHandle);
297 CallInst *Call = new CallInst(PoolAllocator.PoolAlloc, Args, I->getName());
298 MI = BB->getInstList().insert(MI, Call)+1;
300 // If the type desired is not void*, cast it now...
302 if (Call->getType() != I->getType()) {
303 CastInst *CI = new CastInst(Ptr, I->getType(), I->getName());
304 BB->getInstList().insert(MI, CI);
308 // Change everything that used the malloc to now use the pool alloc...
309 I->replaceAllUsesWith(Ptr);
311 // Update the scalars array...
312 updateScalars(I, Ptr);
314 // Delete the instruction now.
318 // Convert the free instruction into a call to poolfree
319 void visitFreeInst(FreeInst *I) {
320 Value *Ptr = I->getOperand(0);
321 const ScalarInfo &SC = getScalar(Ptr);
322 BasicBlock *BB = I->getParent();
323 BasicBlock::iterator FI = find(BB->begin(), BB->end(), I);
325 // If the value is not an sbyte*, convert it now!
326 if (Ptr->getType() != PointerType::get(Type::SByteTy)) {
327 CastInst *CI = new CastInst(Ptr, PointerType::get(Type::SByteTy),
329 FI = BB->getInstList().insert(FI, CI)+1;
333 // Create a new call to poolfree before the free instruction
335 Args.push_back(SC.PoolHandle);
337 CallInst *Call = new CallInst(PoolAllocator.PoolFree, Args);
338 FI = BB->getInstList().insert(FI, Call)+1;
340 // Remove the old free instruction...
341 delete BB->getInstList().remove(FI);
344 // visitCallInst - Create a new call instruction with the extra arguments for
345 // all of the memory pools that the call needs.
347 void visitCallInst(CallInst *I) {
348 TransformFunctionInfo &TI = CallMap[I];
349 BasicBlock *BB = I->getParent();
350 BasicBlock::iterator CI = find(BB->begin(), BB->end(), I);
351 BB->getInstList().remove(CI); // Remove the old call instruction
353 // Start with all of the old arguments...
354 vector<Value*> Args(I->op_begin()+1, I->op_end());
356 // Add all of the pool arguments...
357 for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i)
358 Args.push_back(TI.ArgInfo[i].PoolHandle);
360 Function *NF = PoolAllocator.getTransformedFunction(TI);
361 CallInst *NewCall = new CallInst(NF, Args, I->getName());
362 BB->getInstList().insert(CI, NewCall);
364 // Change everything that used the malloc to now use the pool alloc...
365 if (I->getType() != Type::VoidTy) {
366 I->replaceAllUsesWith(NewCall);
368 // Update the scalars array...
369 updateScalars(I, NewCall);
372 delete I; // Delete the old call instruction now...
375 void visitPHINode(PHINode *PN) {
379 void visitReturnInst(ReturnInst *I) {
380 // Nothing of interest
383 void visitInstruction(Instruction *I) {
384 cerr << "Unknown instruction to FunctionBodyTransformer:\n";
391 static void addCallInfo(DataStructure *DS,
392 TransformFunctionInfo &TFI, CallInst *CI, int Arg,
394 map<DSNode*, Value*> &PoolDescriptors) {
395 assert(CI->getCalledFunction() && "Cannot handle indirect calls yet!");
396 assert(TFI.Func == 0 || TFI.Func == CI->getCalledFunction() &&
397 "Function call record should always call the same function!");
398 assert(TFI.Call == 0 || TFI.Call == CI &&
399 "Call element already filled in with different value!");
400 TFI.Func = CI->getCalledFunction();
402 //FunctionDSGraph &CalledGraph = DS->getClosedDSGraph(TFI.Func);
404 // For now, add the entire graph that is pointed to by the call argument.
405 // This graph can and should be pruned to only what the function itself will
406 // use, because often this will be a dramatically smaller subset of what we
409 for (df_iterator<DSNode*> I = df_begin(GraphNode), E = df_end(GraphNode);
411 TFI.ArgInfo.push_back(CallArgInfo(Arg, *I, PoolDescriptors[*I]));
416 // transformFunctionBody - This transforms the instruction in 'F' to use the
417 // pools specified in PoolDescriptors when modifying data structure nodes
418 // specified in the PoolDescriptors map. Specifically, scalar values specified
419 // in the Scalars vector must be remapped. IPFGraph is the closed data
420 // structure graph for F, of which the PoolDescriptor nodes come from.
422 void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
423 map<DSNode*, Value*> &PoolDescriptors) {
425 // Loop through the value map looking for scalars that refer to nonescaping
426 // allocations. Add them to the Scalars vector. Note that we may have
427 // multiple entries in the Scalars vector for each value if it points to more
430 map<Value*, PointerValSet> &ValMap = IPFGraph.getValueMap();
431 vector<ScalarInfo> Scalars;
433 cerr << "Building scalar map:\n";
435 for (map<Value*, PointerValSet>::iterator I = ValMap.begin(),
436 E = ValMap.end(); I != E; ++I) {
437 const PointerValSet &PVS = I->second; // Set of things pointed to by scalar
439 cerr << "Scalar Mapping from:"; I->first->dump();
440 cerr << "\nScalar Mapping to: "; PVS.print(cerr);
442 assert(PVS.size() == 1 &&
443 "Only handle scalars that point to one thing so far!");
445 // Check to see if the scalar points to a data structure node...
446 for (unsigned i = 0, e = PVS.size(); i != e; ++i) {
447 assert(PVS[i].Index == 0 && "Nonzero not handled yet!");
449 // If the allocation is in the nonescaping set...
450 map<DSNode*, Value*>::iterator AI = PoolDescriptors.find(PVS[i].Node);
451 if (AI != PoolDescriptors.end()) // Add it to the list of scalars
452 Scalars.push_back(ScalarInfo(I->first, PVS[i].Node, AI->second));
458 cerr << "\nIn '" << F->getName()
459 << "': Found the following values that point to poolable nodes:\n";
461 for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
462 Scalars[i].Val->dump();
464 // CallMap - Contain an entry for every call instruction that needs to be
465 // transformed. Each entry in the map contains information about what we need
466 // to do to each call site to change it to work.
468 map<CallInst*, TransformFunctionInfo> CallMap;
470 // Now we need to figure out what called methods we need to transform, and
471 // how. To do this, we look at all of the scalars, seeing which functions are
472 // either used as a scalar value (so they return a data structure), or are
473 // passed one of our scalar values.
475 for (unsigned i = 0, e = Scalars.size(); i != e; ++i) {
476 Value *ScalarVal = Scalars[i].Val;
478 // Check to see if the scalar _IS_ a call...
479 if (CallInst *CI = dyn_cast<CallInst>(ScalarVal))
480 // If so, add information about the pool it will be returning...
481 addCallInfo(DS, CallMap[CI], CI, -1, Scalars[i].Node, PoolDescriptors);
483 // Check to see if the scalar is an operand to a call...
484 for (Value::use_iterator UI = ScalarVal->use_begin(),
485 UE = ScalarVal->use_end(); UI != UE; ++UI) {
486 if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
487 // Find out which operand this is to the call instruction...
488 User::op_iterator OI = find(CI->op_begin(), CI->op_end(), ScalarVal);
489 assert(OI != CI->op_end() && "Call on use list but not an operand!?");
490 assert(OI != CI->op_begin() && "Pointer operand is call destination?");
492 // FIXME: This is broken if the same pointer is passed to a call more
493 // than once! It will get multiple entries for the first pointer.
495 // Add the operand number and pool handle to the call table...
496 addCallInfo(DS, CallMap[CI], CI, OI-CI->op_begin()-1, Scalars[i].Node,
502 // Print out call map...
503 for (map<CallInst*, TransformFunctionInfo>::iterator I = CallMap.begin();
504 I != CallMap.end(); ++I) {
505 cerr << "\nFor call: ";
507 I->second.finalizeConstruction();
508 cerr << I->second.Func->getName() << " must pass pool pointer for args #";
509 for (unsigned i = 0; i < I->second.ArgInfo.size(); ++i)
510 cerr << I->second.ArgInfo[i].ArgNo << ", ";
514 // Loop through all of the call nodes, recursively creating the new functions
515 // that we want to call... This uses a map to prevent infinite recursion and
516 // to avoid duplicating functions unneccesarily.
518 for (map<CallInst*, TransformFunctionInfo>::iterator I = CallMap.begin(),
519 E = CallMap.end(); I != E; ++I) {
520 // Make sure the entries are sorted.
521 I->second.finalizeConstruction();
523 // Transform all of the functions we need, or at least ensure there is a
524 // cached version available.
525 transformFunction(I->second, IPFGraph);
528 // Now that all of the functions that we want to call are available, transform
529 // the local method so that it uses the pools locally and passes them to the
530 // functions that we just hacked up.
533 // First step, find the instructions to be modified.
534 vector<Instruction*> InstToFix;
535 for (unsigned i = 0, e = Scalars.size(); i != e; ++i) {
536 Value *ScalarVal = Scalars[i].Val;
538 // Check to see if the scalar _IS_ an instruction. If so, it is involved.
539 if (Instruction *Inst = dyn_cast<Instruction>(ScalarVal))
540 InstToFix.push_back(Inst);
542 // All all of the instructions that use the scalar as an operand...
543 for (Value::use_iterator UI = ScalarVal->use_begin(),
544 UE = ScalarVal->use_end(); UI != UE; ++UI)
545 InstToFix.push_back(dyn_cast<Instruction>(*UI));
548 // Eliminate duplicates by sorting, then removing equal neighbors.
549 sort(InstToFix.begin(), InstToFix.end());
550 InstToFix.erase(unique(InstToFix.begin(), InstToFix.end()), InstToFix.end());
552 // Use a FunctionBodyTransformer to transform all of the involved instructions
553 FunctionBodyTransformer FBT(*this, Scalars, CallMap);
554 for (unsigned i = 0, e = InstToFix.size(); i != e; ++i)
555 FBT.visit(InstToFix[i]);
558 // Since we have liberally hacked the function to pieces, we want to inform
559 // the datastructure pass that its internal representation is out of date.
561 DS->invalidateFunction(F);
564 static void addNodeMapping(DSNode *SrcNode, const PointerValSet &PVS,
565 map<DSNode*, PointerValSet> &NodeMapping) {
566 for (unsigned i = 0, e = PVS.size(); i != e; ++i)
567 if (NodeMapping[SrcNode].add(PVS[i])) { // Not in map yet?
568 assert(PVS[i].Index == 0 && "Node indexing not supported yet!");
569 DSNode *DestNode = PVS[i].Node;
571 // Loop over all of the outgoing links in the mapped graph
572 for (unsigned l = 0, le = DestNode->getNumOutgoingLinks(); l != le; ++l) {
573 PointerValSet &SrcSet = SrcNode->getOutgoingLink(l);
574 const PointerValSet &DestSet = DestNode->getOutgoingLink(l);
575 assert((!SrcSet.empty() || DestSet.empty()) &&
576 "Dest graph should be a proper subset of the src graph!");
578 // Add all of the node mappings now!
579 for (unsigned si = 0, se = SrcSet.size(); si != se; ++si) {
580 assert(SrcSet[si].Index == 0 && "Can't handle node offset!");
581 addNodeMapping(SrcSet[si].Node, DestSet, NodeMapping);
587 // CalculateNodeMapping - There is a partial isomorphism between the graph
588 // passed in and the graph that is actually used by the function. We need to
589 // figure out what this mapping is so that we can transformFunctionBody the
590 // instructions in the function itself. Note that every node in the graph that
591 // we are interested in must be both in the local graph of the called function,
592 // and in the local graph of the calling function. Because of this, we only
593 // define the mapping for these nodes [conveniently these are the only nodes we
594 // CAN define a mapping for...]
596 // The roots of the graph that we are transforming is rooted in the arguments
597 // passed into the function from the caller. This is where we start our
598 // mapping calculation.
600 // The NodeMapping calculated maps from the callers graph to the called graph.
602 static void CalculateNodeMapping(Function *F, TransformFunctionInfo &TFI,
603 FunctionDSGraph &CallerGraph,
604 FunctionDSGraph &CalledGraph,
605 map<DSNode*, PointerValSet> &NodeMapping) {
607 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) {
608 // Figure out what nodes in the called graph the TFI.ArgInfo[i].Node node
611 // Only consider first node of sequence. Extra nodes may may be added
612 // to the TFI if the data structure requires more nodes than just the
613 // one the argument points to. We are only interested in the one the
614 // argument points to though.
616 if (TFI.ArgInfo[i].ArgNo != LastArgNo) {
617 if (TFI.ArgInfo[i].ArgNo == -1) {
618 addNodeMapping(TFI.ArgInfo[i].Node, CalledGraph.getRetNodes(),
621 // Figure out which node argument # ArgNo points to in the called graph.
622 Value *Arg = F->getArgumentList()[TFI.ArgInfo[i].ArgNo];
623 addNodeMapping(TFI.ArgInfo[i].Node, CalledGraph.getValueMap()[Arg],
626 LastArgNo = TFI.ArgInfo[i].ArgNo;
632 // transformFunction - Transform the specified function the specified way. It
633 // we have already transformed that function that way, don't do anything. The
634 // nodes in the TransformFunctionInfo come out of callers data structure graph.
636 void PoolAllocate::transformFunction(TransformFunctionInfo &TFI,
637 FunctionDSGraph &CallerIPGraph) {
638 if (getTransformedFunction(TFI)) return; // Function xformation already done?
640 cerr << "**********\nEntering transformFunction for "
641 << TFI.Func->getName() << ":\n";
642 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i)
643 cerr << " ArgInfo[" << i << "] = " << TFI.ArgInfo[i].ArgNo << "\n";
647 const FunctionType *OldFuncType = TFI.Func->getFunctionType();
649 assert(!OldFuncType->isVarArg() && "Vararg functions not handled yet!");
651 // Build the type for the new function that we are transforming
652 vector<const Type*> ArgTys;
653 for (unsigned i = 0, e = OldFuncType->getNumParams(); i != e; ++i)
654 ArgTys.push_back(OldFuncType->getParamType(i));
656 // Add one pool pointer for every argument that needs to be supplemented.
657 ArgTys.insert(ArgTys.end(), TFI.ArgInfo.size(), PoolTy);
659 // Build the new function type...
660 const // FIXME when types are not const
661 FunctionType *NewFuncType = FunctionType::get(OldFuncType->getReturnType(),
662 ArgTys,OldFuncType->isVarArg());
664 // The new function is internal, because we know that only we can call it.
665 // This also helps subsequent IP transformations to eliminate duplicated pool
666 // pointers. [in the future when they are implemented].
668 Function *NewFunc = new Function(NewFuncType, true,
669 TFI.Func->getName()+".poolxform");
670 CurModule->getFunctionList().push_back(NewFunc);
672 // Add the newly formed function to the TransformedFunctions table so that
673 // infinite recursion does not occur!
675 TransformedFunctions[TFI] = NewFunc;
677 // Add arguments to the function... starting with all of the old arguments
678 vector<Value*> ArgMap;
679 for (unsigned i = 0, e = TFI.Func->getArgumentList().size(); i != e; ++i) {
680 const FunctionArgument *OFA = TFI.Func->getArgumentList()[i];
681 FunctionArgument *NFA = new FunctionArgument(OFA->getType(),OFA->getName());
682 NewFunc->getArgumentList().push_back(NFA);
683 ArgMap.push_back(NFA); // Keep track of the arguments
686 // Now add all of the arguments corresponding to pools passed in...
687 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) {
689 if (TFI.ArgInfo[i].ArgNo == -1)
692 Name = ArgMap[TFI.ArgInfo[i].ArgNo]->getName(); // Get the arg name
693 FunctionArgument *NFA = new FunctionArgument(PoolTy, Name+".pool");
694 NewFunc->getArgumentList().push_back(NFA);
697 // Now clone the body of the old function into the new function...
698 CloneFunctionInto(NewFunc, TFI.Func, ArgMap);
700 // Okay, now we have a function that is identical to the old one, except that
701 // it has extra arguments for the pools coming in. Now we have to get the
702 // data structure graph for the function we are replacing, and figure out how
703 // our graph nodes map to the graph nodes in the dest function.
705 FunctionDSGraph &DSGraph = DS->getClosedDSGraph(NewFunc);
707 // NodeMapping - Multimap from callers graph to called graph.
709 map<DSNode*, PointerValSet> NodeMapping;
711 CalculateNodeMapping(NewFunc, TFI, CallerIPGraph, DSGraph,
714 // Print out the node mapping...
715 cerr << "\nNode mapping for call of " << NewFunc->getName() << "\n";
716 for (map<DSNode*, PointerValSet>::iterator I = NodeMapping.begin();
717 I != NodeMapping.end(); ++I) {
718 cerr << "Map: "; I->first->print(cerr);
719 cerr << "To: "; I->second.print(cerr);
723 // Fill in the PoolDescriptor information for the transformed function so that
724 // it can determine which value holds the pool descriptor for each data
725 // structure node that it accesses.
727 map<DSNode*, Value*> PoolDescriptors;
729 cerr << "\nCalculating the pool descriptor map:\n";
731 // All of the pool descriptors must be passed in as arguments...
732 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) {
733 DSNode *CallerNode = TFI.ArgInfo[i].Node;
734 Value *CallerPool = TFI.ArgInfo[i].PoolHandle;
736 cerr << "Mapped caller node: "; CallerNode->print(cerr);
737 cerr << "Mapped caller pool: "; CallerPool->dump();
739 // Calculate the argument number that the pool is to the function call...
740 // The call instruction should not have the pool operands added yet.
741 unsigned ArgNo = TFI.Call->getNumOperands()-1+i;
742 cerr << "Should be argument #: " << ArgNo << "[i = " << i << "]\n";
743 assert(ArgNo < NewFunc->getArgumentList().size() &&
744 "Call already has pool arguments added??");
746 // Map the pool argument into the called function...
747 Value *CalleePool = NewFunc->getArgumentList()[ArgNo];
749 // Map the DSNode into the callee's DSGraph
750 const PointerValSet &CalleeNodes = NodeMapping[CallerNode];
751 for (unsigned n = 0, ne = CalleeNodes.size(); n != ne; ++n) {
752 assert(CalleeNodes[n].Index == 0 && "Indexed node not handled yet!");
753 DSNode *CalleeNode = CalleeNodes[n].Node;
755 cerr << "*** to callee node: "; CalleeNode->print(cerr);
756 cerr << "*** to callee pool: "; CalleePool->dump();
759 assert(CalleeNode && CalleePool && "Invalid nodes!");
760 Value *&PV = PoolDescriptors[CalleeNode];
761 //assert((PV == 0 || PV == CalleePool) && "Invalid node remapping!");
762 PV = CalleePool; // Update the pool descriptor map!
766 // We must destroy the node mapping so that we don't have latent references
767 // into the data structure graph for the new function. Otherwise we get
768 // assertion failures when transformFunctionBody tries to invalidate the
773 // Now that we know everything we need about the function, transform the body
776 transformFunctionBody(NewFunc, DSGraph, PoolDescriptors);
778 cerr << "Function after transformation:\n";
783 // CreatePools - Insert instructions into the function we are processing to
784 // create all of the memory pool objects themselves. This also inserts
785 // destruction code. Add an alloca for each pool that is allocated to the
786 // PoolDescriptors vector.
788 void PoolAllocate::CreatePools(Function *F, const vector<AllocDSNode*> &Allocs,
789 map<DSNode*, Value*> &PoolDescriptors) {
790 // FIXME: This should use an IP version of the UnifyAllExits pass!
791 vector<BasicBlock*> ReturnNodes;
792 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
793 if (isa<ReturnInst>((*I)->getTerminator()))
794 ReturnNodes.push_back(*I);
797 // Create the code that goes in the entry and exit nodes for the method...
798 vector<Instruction*> EntryNodeInsts;
799 for (unsigned i = 0, e = Allocs.size(); i != e; ++i) {
800 // Add an allocation and a free for each pool...
801 AllocaInst *PoolAlloc = new AllocaInst(PoolTy, 0, "pool");
802 EntryNodeInsts.push_back(PoolAlloc);
803 PoolDescriptors[Allocs[i]] = PoolAlloc; // Keep track of pool allocas
804 AllocationInst *AI = Allocs[i]->getAllocation();
806 // Initialize the pool. We need to know how big each allocation is. For
807 // our purposes here, we assume we are allocating a scalar, or array of
810 unsigned ElSize = TargetData.getTypeSize(AI->getAllocatedType());
811 ElSize *= cast<ConstantUInt>(AI->getArraySize())->getValue();
814 Args.push_back(PoolAlloc); // Pool to initialize
815 Args.push_back(ConstantUInt::get(Type::UIntTy, ElSize));
816 EntryNodeInsts.push_back(new CallInst(PoolInit, Args));
818 // Destroy the pool...
821 for (unsigned EN = 0, ENE = ReturnNodes.size(); EN != ENE; ++EN) {
822 Instruction *Destroy = new CallInst(PoolDestroy, Args);
824 // Insert it before the return instruction...
825 BasicBlock *RetNode = ReturnNodes[EN];
826 RetNode->getInstList().insert(RetNode->end()-1, Destroy);
830 // Insert the entry node code into the entry block...
831 F->getEntryNode()->getInstList().insert(F->getEntryNode()->begin()+1,
832 EntryNodeInsts.begin(),
833 EntryNodeInsts.end());
837 // addPoolPrototypes - Add prototypes for the pool methods to the specified
838 // module and update the Pool* instance variables to point to them.
840 void PoolAllocate::addPoolPrototypes(Module *M) {
841 // Get PoolInit function...
842 vector<const Type*> Args;
843 Args.push_back(PoolTy); // Pool to initialize
844 Args.push_back(Type::UIntTy); // Num bytes per element
845 FunctionType *PoolInitTy = FunctionType::get(Type::VoidTy, Args, false);
846 PoolInit = M->getOrInsertFunction("poolinit", PoolInitTy);
848 // Get pooldestroy function...
849 Args.pop_back(); // Only takes a pool...
850 FunctionType *PoolDestroyTy = FunctionType::get(Type::VoidTy, Args, false);
851 PoolDestroy = M->getOrInsertFunction("pooldestroy", PoolDestroyTy);
853 const Type *PtrVoid = PointerType::get(Type::SByteTy);
855 // Get the poolalloc function...
856 FunctionType *PoolAllocTy = FunctionType::get(PtrVoid, Args, false);
857 PoolAlloc = M->getOrInsertFunction("poolalloc", PoolAllocTy);
859 // Get the poolfree function...
860 Args.push_back(PtrVoid);
861 FunctionType *PoolFreeTy = FunctionType::get(Type::VoidTy, Args, false);
862 PoolFree = M->getOrInsertFunction("poolfree", PoolFreeTy);
864 // Add the %PoolTy type to the symbol table of the module...
865 M->addTypeName("PoolTy", PoolTy->getElementType());
869 bool PoolAllocate::run(Module *M) {
870 addPoolPrototypes(M);
873 DS = &getAnalysis<DataStructure>();
874 bool Changed = false;
876 // We cannot use an iterator here because it will get invalidated when we add
877 // functions to the module later...
878 for (unsigned i = 0; i != M->size(); ++i)
879 if (!M->getFunctionList()[i]->isExternal()) {
880 Changed |= processFunction(M->getFunctionList()[i]);
882 cerr << "Only processing one function\n";
893 // createPoolAllocatePass - Global function to access the functionality of this
896 Pass *createPoolAllocatePass() { return new PoolAllocate(); }