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/BasicBlock.h"
17 #include "llvm/iMemory.h"
18 #include "llvm/iTerminators.h"
19 #include "llvm/iPHINode.h"
20 #include "llvm/iOther.h"
21 #include "llvm/DerivedTypes.h"
22 #include "llvm/ConstantVals.h"
23 #include "llvm/Target/TargetData.h"
24 #include "llvm/Support/InstVisitor.h"
25 #include "llvm/Argument.h"
26 #include "Support/DepthFirstIterator.h"
27 #include "Support/STLExtras.h"
30 // DEBUG_CREATE_POOLS - Enable this to turn on debug output for the pool
31 // creation phase in the top level function of a transformed data structure.
33 #define DEBUG_CREATE_POOLS 1
35 const Type *POINTERTYPE;
37 // FIXME: This is dependant on the sparc backend layout conventions!!
38 static TargetData TargetData("test");
42 DSNode *Node; // The node this pool allocation represents
43 Value *Handle; // LLVM value of the pool in the current context
44 const Type *NewType; // The transformed type of the memory objects
45 const Type *PoolType; // The type of the pool
47 const Type *getOldType() const { return Node->getType(); }
49 PoolInfo() { // Define a default ctor for map::operator[]
50 cerr << "Map subscript used to get element that doesn't exist!\n";
54 PoolInfo(DSNode *N, Value *H, const Type *NT, const Type *PT)
55 : Node(N), Handle(H), NewType(NT), PoolType(PT) {
56 // Handle can be null...
57 assert(N && NT && PT && "Pool info null!");
60 PoolInfo(DSNode *N) : Node(N), Handle(0), NewType(0), PoolType(0) {
61 assert(N && "Invalid pool info!");
63 // The new type of the memory object is the same as the old type, except
64 // that all of the pointer values are replaced with POINTERTYPE values.
65 assert(isa<StructType>(getOldType()) && "Can only handle structs!");
66 StructType *OldTy = cast<StructType>(getOldType());
67 vector<const Type *> NewElTypes;
68 NewElTypes.reserve(OldTy->getElementTypes().size());
69 for (StructType::ElementTypes::const_iterator
70 I = OldTy->getElementTypes().begin(),
71 E = OldTy->getElementTypes().end(); I != E; ++I)
72 if (PointerType *PT = dyn_cast<PointerType>(I->get()))
73 NewElTypes.push_back(POINTERTYPE);
75 NewElTypes.push_back(*I);
76 NewType = StructType::get(NewElTypes);
80 // ScalarInfo - Information about an LLVM value that we know points to some
81 // datastructure we are processing.
84 Value *Val; // Scalar value in Current Function
85 PoolInfo Pool; // The pool the scalar points into
87 ScalarInfo(Value *V, const PoolInfo &PI) : Val(V), Pool(PI) {
88 assert(V && "Null value passed to ScalarInfo ctor!");
92 // CallArgInfo - Information on one operand for a call that got expanded.
94 int ArgNo; // Call argument number this corresponds to
95 DSNode *Node; // The graph node for the pool
96 Value *PoolHandle; // The LLVM value that is the pool pointer
98 CallArgInfo(int Arg, DSNode *N, Value *PH)
99 : ArgNo(Arg), Node(N), PoolHandle(PH) {
100 assert(Arg >= -1 && N && PH && "Illegal values to CallArgInfo ctor!");
103 // operator< when sorting, sort by argument number.
104 bool operator<(const CallArgInfo &CAI) const {
105 return ArgNo < CAI.ArgNo;
109 // TransformFunctionInfo - Information about how a function eeds to be
112 struct TransformFunctionInfo {
113 // ArgInfo - Maintain information about the arguments that need to be
114 // processed. Each CallArgInfo corresponds to an argument that needs to
115 // have a pool pointer passed into the transformed function with it.
117 // As a special case, "argument" number -1 corresponds to the return value.
119 vector<CallArgInfo> ArgInfo;
121 // Func - The function to be transformed...
124 // The call instruction that is used to map CallArgInfo PoolHandle values
125 // into the new function values.
129 TransformFunctionInfo() : Func(0), Call(0) {}
131 bool operator<(const TransformFunctionInfo &TFI) const {
132 if (Func < TFI.Func) return true;
133 if (Func > TFI.Func) return false;
134 if (ArgInfo.size() < TFI.ArgInfo.size()) return true;
135 if (ArgInfo.size() > TFI.ArgInfo.size()) return false;
136 return ArgInfo < TFI.ArgInfo;
139 void finalizeConstruction() {
140 // Sort the vector so that the return value is first, followed by the
141 // argument records, in order. Note that this must be a stable sort so
142 // that the entries with the same sorting criteria (ie they are multiple
143 // pool entries for the same argument) are kept in depth first order.
144 stable_sort(ArgInfo.begin(), ArgInfo.end());
149 // Define the pass class that we implement...
150 struct PoolAllocate : public Pass {
152 POINTERTYPE = Type::UShortTy;
154 CurModule = 0; DS = 0;
155 PoolInit = PoolDestroy = PoolAlloc = PoolFree = 0;
158 // getPoolType - Get the type used by the backend for a pool of a particular
159 // type. This pool record is used to allocate nodes of type NodeType.
161 // Here, PoolTy = { NodeType*, sbyte*, uint }*
163 const StructType *getPoolType(const Type *NodeType) {
164 vector<const Type*> PoolElements;
165 PoolElements.push_back(PointerType::get(NodeType));
166 PoolElements.push_back(PointerType::get(Type::SByteTy));
167 PoolElements.push_back(Type::UIntTy);
168 StructType *Result = StructType::get(PoolElements);
170 // Add a name to the symbol table to correspond to the backend
171 // representation of this pool...
172 assert(CurModule && "No current module!?");
173 string Name = CurModule->getTypeName(NodeType);
174 if (Name.empty()) Name = CurModule->getTypeName(PoolElements[0]);
175 CurModule->addTypeName(Name+"oolbe", Result);
182 // getAnalysisUsageInfo - This function requires data structure information
183 // to be able to see what is pool allocatable.
185 virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Required,
186 Pass::AnalysisSet &,Pass::AnalysisSet &) {
187 Required.push_back(DataStructure::ID);
191 // CurModule - The module being processed.
194 // DS - The data structure graph for the module being processed.
197 // Prototypes that we add to support pool allocation...
198 Function *PoolInit, *PoolDestroy, *PoolAlloc, *PoolFree;
200 // The map of already transformed functions... note that the keys of this
201 // map do not have meaningful values for 'Call' or the 'PoolHandle' elements
202 // of the ArgInfo elements.
204 map<TransformFunctionInfo, Function*> TransformedFunctions;
206 // getTransformedFunction - Get a transformed function, or return null if
207 // the function specified hasn't been transformed yet.
209 Function *getTransformedFunction(TransformFunctionInfo &TFI) const {
210 map<TransformFunctionInfo, Function*>::const_iterator I =
211 TransformedFunctions.find(TFI);
212 if (I != TransformedFunctions.end()) return I->second;
217 // addPoolPrototypes - Add prototypes for the pool functions to the
218 // specified module and update the Pool* instance variables to point to
221 void addPoolPrototypes(Module *M);
224 // CreatePools - Insert instructions into the function we are processing to
225 // create all of the memory pool objects themselves. This also inserts
226 // destruction code. Add an alloca for each pool that is allocated to the
229 void CreatePools(Function *F, const vector<AllocDSNode*> &Allocs,
230 map<DSNode*, PoolInfo> &PoolDescs);
232 // processFunction - Convert a function to use pool allocation where
235 bool processFunction(Function *F);
237 // transformFunctionBody - This transforms the instruction in 'F' to use the
238 // pools specified in PoolDescs when modifying data structure nodes
239 // specified in the PoolDescs map. IPFGraph is the closed data structure
240 // graph for F, of which the PoolDescriptor nodes come from.
242 void transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
243 map<DSNode*, PoolInfo> &PoolDescs);
245 // transformFunction - Transform the specified function the specified way.
246 // It we have already transformed that function that way, don't do anything.
247 // The nodes in the TransformFunctionInfo come out of callers data structure
248 // graph, and the PoolDescs passed in are the caller's.
250 void transformFunction(TransformFunctionInfo &TFI,
251 FunctionDSGraph &CallerIPGraph,
252 map<DSNode*, PoolInfo> &PoolDescs);
257 // isNotPoolableAlloc - This is a predicate that returns true if the specified
258 // allocation node in a data structure graph is eligable for pool allocation.
260 static bool isNotPoolableAlloc(const AllocDSNode *DS) {
261 if (DS->isAllocaNode()) return true; // Do not pool allocate alloca's.
263 MallocInst *MI = cast<MallocInst>(DS->getAllocation());
264 if (MI->isArrayAllocation() && !isa<Constant>(MI->getArraySize()))
265 return true; // Do not allow variable size allocations...
270 // processFunction - Convert a function to use pool allocation where
273 bool PoolAllocate::processFunction(Function *F) {
274 // Get the closed datastructure graph for the current function... if there are
275 // any allocations in this graph that are not escaping, we need to pool
276 // allocate them here!
278 FunctionDSGraph &IPGraph = DS->getClosedDSGraph(F);
280 // Get all of the allocations that do not escape the current function. Since
281 // they are still live (they exist in the graph at all), this means we must
282 // have scalar references to these nodes, but the scalars are never returned.
284 vector<AllocDSNode*> Allocs;
285 IPGraph.getNonEscapingAllocations(Allocs);
287 // Filter out allocations that we cannot handle. Currently, this includes
288 // variable sized array allocations and alloca's (which we do not want to
291 Allocs.erase(remove_if(Allocs.begin(), Allocs.end(), isNotPoolableAlloc),
295 if (Allocs.empty()) return false; // Nothing to do.
297 // Insert instructions into the function we are processing to create all of
298 // the memory pool objects themselves. This also inserts destruction code.
299 // This fills in the PoolDescs map to associate the alloc node with the
300 // allocation of the memory pool corresponding to it.
302 map<DSNode*, PoolInfo> PoolDescs;
303 CreatePools(F, Allocs, PoolDescs);
305 cerr << "Transformed Entry Function: \n" << F;
307 // Now we need to figure out what called functions we need to transform, and
308 // how. To do this, we look at all of the scalars, seeing which functions are
309 // either used as a scalar value (so they return a data structure), or are
310 // passed one of our scalar values.
312 transformFunctionBody(F, IPGraph, PoolDescs);
318 //===----------------------------------------------------------------------===//
320 // NewInstructionCreator - This class is used to traverse the function being
321 // modified, changing each instruction visit'ed to use and provide pointer
322 // indexes instead of real pointers. This is what changes the body of a
323 // function to use pool allocation.
325 class NewInstructionCreator : public InstVisitor<NewInstructionCreator> {
326 PoolAllocate &PoolAllocator;
327 vector<ScalarInfo> &Scalars;
328 map<CallInst*, TransformFunctionInfo> &CallMap;
329 map<Value*, Value*> &XFormMap; // Map old pointers to new indexes
332 Instruction *I; // Instruction to update
333 unsigned OpNum; // Operand number to update
334 Value *OldVal; // The old value it had
336 RefToUpdate(Instruction *i, unsigned o, Value *ov)
337 : I(i), OpNum(o), OldVal(ov) {}
339 vector<RefToUpdate> ReferencesToUpdate;
341 const ScalarInfo &getScalarRef(const Value *V) {
342 for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
343 if (Scalars[i].Val == V) return Scalars[i];
344 assert(0 && "Scalar not found in getScalar!");
349 const ScalarInfo *getScalar(const Value *V) {
350 for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
351 if (Scalars[i].Val == V) return &Scalars[i];
355 BasicBlock::iterator ReplaceInstWith(Instruction *I, Instruction *New) {
356 BasicBlock *BB = I->getParent();
357 BasicBlock::iterator RI = find(BB->begin(), BB->end(), I);
358 BB->getInstList().replaceWith(RI, New);
363 LoadInst *createPoolBaseInstruction(Value *PtrVal) {
364 const ScalarInfo &SC = getScalarRef(PtrVal);
365 vector<Value*> Args(3);
366 Args[0] = ConstantUInt::get(Type::UIntTy, 0); // No pointer offset
367 Args[1] = ConstantUInt::get(Type::UByteTy, 0); // Field #0 of pool descriptr
368 Args[2] = ConstantUInt::get(Type::UByteTy, 0); // Field #0 of poolalloc val
369 return new LoadInst(SC.Pool.Handle, Args, PtrVal->getName()+".poolbase");
374 NewInstructionCreator(PoolAllocate &PA, vector<ScalarInfo> &S,
375 map<CallInst*, TransformFunctionInfo> &C,
376 map<Value*, Value*> &X)
377 : PoolAllocator(PA), Scalars(S), CallMap(C), XFormMap(X) {}
380 // updateReferences - The NewInstructionCreator is responsible for creating
381 // new instructions to replace the old ones in the function, and then link up
382 // references to values to their new values. For it to do this, however, it
383 // keeps track of information about the value mapping of old values to new
384 // values that need to be patched up. Given this value map and a set of
385 // instruction operands to patch, updateReferences performs the updates.
387 void updateReferences() {
388 for (unsigned i = 0, e = ReferencesToUpdate.size(); i != e; ++i) {
389 RefToUpdate &Ref = ReferencesToUpdate[i];
390 Value *NewVal = XFormMap[Ref.OldVal];
393 if (isa<Constant>(Ref.OldVal) && // Refering to a null ptr?
394 cast<Constant>(Ref.OldVal)->isNullValue()) {
395 // Transform the null pointer into a null index... caching in XFormMap
396 XFormMap[Ref.OldVal] = NewVal =Constant::getNullConstant(POINTERTYPE);
397 //} else if (isa<Argument>(Ref.OldVal)) {
399 cerr << "Unknown reference to: " << Ref.OldVal << "\n";
400 assert(XFormMap[Ref.OldVal] &&
401 "Reference to value that was not updated found!");
405 Ref.I->setOperand(Ref.OpNum, NewVal);
407 ReferencesToUpdate.clear();
410 //===--------------------------------------------------------------------===//
411 // Transformation methods:
412 // These methods specify how each type of instruction is transformed by the
413 // NewInstructionCreator instance...
414 //===--------------------------------------------------------------------===//
416 void visitGetElementPtrInst(GetElementPtrInst *I) {
417 assert(0 && "Cannot transform get element ptr instructions yet!");
420 // Replace the load instruction with a new one.
421 void visitLoadInst(LoadInst *I) {
422 Instruction *PoolBase = createPoolBaseInstruction(I->getOperand(0));
424 // Cast our index to be a UIntTy so we can use it to index into the pool...
425 CastInst *Index = new CastInst(Constant::getNullConstant(POINTERTYPE),
426 Type::UIntTy, I->getOperand(0)->getName());
428 ReferencesToUpdate.push_back(RefToUpdate(Index, 0, I->getOperand(0)));
430 vector<Value*> Indices(I->idx_begin(), I->idx_end());
431 assert(Indices[0] == ConstantUInt::get(Type::UIntTy, 0) &&
432 "Cannot handle array indexing yet!");
434 Instruction *NewLoad = new LoadInst(PoolBase, Indices, I->getName());
436 // Replace the load instruction with the new load instruction...
437 BasicBlock::iterator II = ReplaceInstWith(I, NewLoad);
439 // Add the pool base calculator instruction before the load...
440 II = NewLoad->getParent()->getInstList().insert(II, PoolBase) + 1;
442 // Add the cast before the load instruction...
443 NewLoad->getParent()->getInstList().insert(II, Index);
445 // If not yielding a pool allocated pointer, use the new load value as the
446 // value in the program instead of the old load value...
449 I->replaceAllUsesWith(NewLoad);
452 // Replace the store instruction with a new one. In the store instruction,
453 // the value stored could be a pointer type, meaning that the new store may
454 // have to change one or both of it's operands.
456 void visitStoreInst(StoreInst *I) {
457 assert(getScalar(I->getOperand(1)) &&
458 "Store inst found only storing pool allocated pointer. "
461 Value *Val = I->getOperand(0); // The value to store...
462 // Check to see if the value we are storing is a data structure pointer...
463 if (const ScalarInfo *ValScalar = getScalar(I->getOperand(0)))
464 Val = Constant::getNullConstant(POINTERTYPE); // Yes, store a dummy
466 Instruction *PoolBase = createPoolBaseInstruction(I->getOperand(1));
468 // Cast our index to be a UIntTy so we can use it to index into the pool...
469 CastInst *Index = new CastInst(Constant::getNullConstant(POINTERTYPE),
470 Type::UIntTy, I->getOperand(1)->getName());
471 ReferencesToUpdate.push_back(RefToUpdate(Index, 0, I->getOperand(1)));
473 vector<Value*> Indices(I->idx_begin(), I->idx_end());
474 assert(Indices[0] == ConstantUInt::get(Type::UIntTy, 0) &&
475 "Cannot handle array indexing yet!");
477 Instruction *NewStore = new StoreInst(Val, PoolBase, Indices);
479 if (Val != I->getOperand(0)) // Value stored was a pointer?
480 ReferencesToUpdate.push_back(RefToUpdate(NewStore, 0, I->getOperand(0)));
483 // Replace the store instruction with the cast instruction...
484 BasicBlock::iterator II = ReplaceInstWith(I, Index);
486 // Add the pool base calculator instruction before the index...
487 II = Index->getParent()->getInstList().insert(II, PoolBase) + 2;
489 // Add the store after the cast instruction...
490 Index->getParent()->getInstList().insert(II, NewStore);
494 // Create call to poolalloc for every malloc instruction
495 void visitMallocInst(MallocInst *I) {
497 Args.push_back(getScalarRef(I).Pool.Handle);
498 CallInst *Call = new CallInst(PoolAllocator.PoolAlloc, Args, I->getName());
499 ReplaceInstWith(I, Call);
502 // Convert a call to poolfree for every free instruction...
503 void visitFreeInst(FreeInst *I) {
504 // Create a new call to poolfree before the free instruction
506 Args.push_back(Constant::getNullConstant(POINTERTYPE));
507 Args.push_back(getScalarRef(I->getOperand(0)).Pool.Handle);
508 Instruction *NewCall = new CallInst(PoolAllocator.PoolFree, Args);
509 ReplaceInstWith(I, NewCall);
510 ReferencesToUpdate.push_back(RefToUpdate(NewCall, 0, I->getOperand(0)));
513 // visitCallInst - Create a new call instruction with the extra arguments for
514 // all of the memory pools that the call needs.
516 void visitCallInst(CallInst *I) {
517 TransformFunctionInfo &TI = CallMap[I];
519 // Start with all of the old arguments...
520 vector<Value*> Args(I->op_begin()+1, I->op_end());
522 for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i) {
523 // Replace all of the pointer arguments with our new pointer typed values.
524 if (TI.ArgInfo[i].ArgNo != -1)
525 Args[TI.ArgInfo[i].ArgNo] = Constant::getNullConstant(POINTERTYPE);
527 // Add all of the pool arguments...
528 Args.push_back(TI.ArgInfo[i].PoolHandle);
531 Function *NF = PoolAllocator.getTransformedFunction(TI);
532 Instruction *NewCall = new CallInst(NF, Args, I->getName());
533 ReplaceInstWith(I, NewCall);
535 // Keep track of the mapping of operands so that we can resolve them to real
537 Value *RetVal = NewCall;
538 for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i)
539 if (TI.ArgInfo[i].ArgNo != -1)
540 ReferencesToUpdate.push_back(RefToUpdate(NewCall, TI.ArgInfo[i].ArgNo+1,
541 I->getOperand(TI.ArgInfo[i].ArgNo+1)));
543 RetVal = 0; // If returning a pointer, don't change retval...
545 // If not returning a pointer, use the new call as the value in the program
546 // instead of the old call...
549 I->replaceAllUsesWith(RetVal);
552 // visitPHINode - Create a new PHI node of POINTERTYPE for all of the old Phi
555 void visitPHINode(PHINode *PN) {
556 Value *DummyVal = Constant::getNullConstant(POINTERTYPE);
557 PHINode *NewPhi = new PHINode(POINTERTYPE, PN->getName());
558 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
559 NewPhi->addIncoming(DummyVal, PN->getIncomingBlock(i));
560 ReferencesToUpdate.push_back(RefToUpdate(NewPhi, i*2,
561 PN->getIncomingValue(i)));
564 ReplaceInstWith(PN, NewPhi);
567 // visitReturnInst - Replace ret instruction with a new return...
568 void visitReturnInst(ReturnInst *I) {
569 Instruction *Ret = new ReturnInst(Constant::getNullConstant(POINTERTYPE));
570 ReplaceInstWith(I, Ret);
571 ReferencesToUpdate.push_back(RefToUpdate(Ret, 0, I->getOperand(0)));
574 // visitSetCondInst - Replace a conditional test instruction with a new one
575 void visitSetCondInst(SetCondInst *SCI) {
576 BinaryOperator *I = (BinaryOperator*)SCI;
577 Value *DummyVal = Constant::getNullConstant(POINTERTYPE);
578 BinaryOperator *New = BinaryOperator::create(I->getOpcode(), DummyVal,
579 DummyVal, I->getName());
580 ReplaceInstWith(I, New);
582 ReferencesToUpdate.push_back(RefToUpdate(New, 0, I->getOperand(0)));
583 ReferencesToUpdate.push_back(RefToUpdate(New, 1, I->getOperand(1)));
585 // Make sure branches refer to the new condition...
586 I->replaceAllUsesWith(New);
589 void visitInstruction(Instruction *I) {
590 cerr << "Unknown instruction to FunctionBodyTransformer:\n" << I;
597 static void addCallInfo(DataStructure *DS,
598 TransformFunctionInfo &TFI, CallInst *CI, int Arg,
600 map<DSNode*, PoolInfo> &PoolDescs) {
601 assert(CI->getCalledFunction() && "Cannot handle indirect calls yet!");
602 assert(TFI.Func == 0 || TFI.Func == CI->getCalledFunction() &&
603 "Function call record should always call the same function!");
604 assert(TFI.Call == 0 || TFI.Call == CI &&
605 "Call element already filled in with different value!");
606 TFI.Func = CI->getCalledFunction();
608 //FunctionDSGraph &CalledGraph = DS->getClosedDSGraph(TFI.Func);
610 // For now, add the entire graph that is pointed to by the call argument.
611 // This graph can and should be pruned to only what the function itself will
612 // use, because often this will be a dramatically smaller subset of what we
615 for (df_iterator<DSNode*> I = df_begin(GraphNode), E = df_end(GraphNode);
617 TFI.ArgInfo.push_back(CallArgInfo(Arg, *I, PoolDescs[*I].Handle));
621 // transformFunctionBody - This transforms the instruction in 'F' to use the
622 // pools specified in PoolDescs when modifying data structure nodes specified in
623 // the PoolDescs map. Specifically, scalar values specified in the Scalars
624 // vector must be remapped. IPFGraph is the closed data structure graph for F,
625 // of which the PoolDescriptor nodes come from.
627 void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
628 map<DSNode*, PoolInfo> &PoolDescs) {
630 // Loop through the value map looking for scalars that refer to nonescaping
631 // allocations. Add them to the Scalars vector. Note that we may have
632 // multiple entries in the Scalars vector for each value if it points to more
635 map<Value*, PointerValSet> &ValMap = IPFGraph.getValueMap();
636 vector<ScalarInfo> Scalars;
638 cerr << "Building scalar map:\n";
640 for (map<Value*, PointerValSet>::iterator I = ValMap.begin(),
641 E = ValMap.end(); I != E; ++I) {
642 const PointerValSet &PVS = I->second; // Set of things pointed to by scalar
644 // Check to see if the scalar points to a data structure node...
645 for (unsigned i = 0, e = PVS.size(); i != e; ++i) {
646 assert(PVS[i].Index == 0 && "Nonzero not handled yet!");
648 // If the allocation is in the nonescaping set...
649 map<DSNode*, PoolInfo>::iterator AI = PoolDescs.find(PVS[i].Node);
650 if (AI != PoolDescs.end()) { // Add it to the list of scalars
651 Scalars.push_back(ScalarInfo(I->first, AI->second));
652 cerr << "\nScalar Mapping from:" << I->first
653 << "Scalar Mapping to: "; PVS.print(cerr);
660 cerr << "\nIn '" << F->getName()
661 << "': Found the following values that point to poolable nodes:\n";
663 for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
664 cerr << Scalars[i].Val;
667 // CallMap - Contain an entry for every call instruction that needs to be
668 // transformed. Each entry in the map contains information about what we need
669 // to do to each call site to change it to work.
671 map<CallInst*, TransformFunctionInfo> CallMap;
673 // Now we need to figure out what called functions we need to transform, and
674 // how. To do this, we look at all of the scalars, seeing which functions are
675 // either used as a scalar value (so they return a data structure), or are
676 // passed one of our scalar values.
678 for (unsigned i = 0, e = Scalars.size(); i != e; ++i) {
679 Value *ScalarVal = Scalars[i].Val;
681 // Check to see if the scalar _IS_ a call...
682 if (CallInst *CI = dyn_cast<CallInst>(ScalarVal))
683 // If so, add information about the pool it will be returning...
684 addCallInfo(DS, CallMap[CI], CI, -1, Scalars[i].Pool.Node, PoolDescs);
686 // Check to see if the scalar is an operand to a call...
687 for (Value::use_iterator UI = ScalarVal->use_begin(),
688 UE = ScalarVal->use_end(); UI != UE; ++UI) {
689 if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
690 // Find out which operand this is to the call instruction...
691 User::op_iterator OI = find(CI->op_begin(), CI->op_end(), ScalarVal);
692 assert(OI != CI->op_end() && "Call on use list but not an operand!?");
693 assert(OI != CI->op_begin() && "Pointer operand is call destination?");
695 // FIXME: This is broken if the same pointer is passed to a call more
696 // than once! It will get multiple entries for the first pointer.
698 // Add the operand number and pool handle to the call table...
699 addCallInfo(DS, CallMap[CI], CI, OI-CI->op_begin()-1,
700 Scalars[i].Pool.Node, PoolDescs);
705 // Print out call map...
706 for (map<CallInst*, TransformFunctionInfo>::iterator I = CallMap.begin();
707 I != CallMap.end(); ++I) {
708 cerr << "For call: " << I->first;
709 I->second.finalizeConstruction();
710 cerr << I->second.Func->getName() << " must pass pool pointer for args #";
711 for (unsigned i = 0; i < I->second.ArgInfo.size(); ++i)
712 cerr << I->second.ArgInfo[i].ArgNo << ", ";
716 // Loop through all of the call nodes, recursively creating the new functions
717 // that we want to call... This uses a map to prevent infinite recursion and
718 // to avoid duplicating functions unneccesarily.
720 for (map<CallInst*, TransformFunctionInfo>::iterator I = CallMap.begin(),
721 E = CallMap.end(); I != E; ++I) {
722 // Make sure the entries are sorted.
723 I->second.finalizeConstruction();
725 // Transform all of the functions we need, or at least ensure there is a
726 // cached version available.
727 transformFunction(I->second, IPFGraph, PoolDescs);
730 // Now that all of the functions that we want to call are available, transform
731 // the local function so that it uses the pools locally and passes them to the
732 // functions that we just hacked up.
735 // First step, find the instructions to be modified.
736 vector<Instruction*> InstToFix;
737 for (unsigned i = 0, e = Scalars.size(); i != e; ++i) {
738 Value *ScalarVal = Scalars[i].Val;
740 // Check to see if the scalar _IS_ an instruction. If so, it is involved.
741 if (Instruction *Inst = dyn_cast<Instruction>(ScalarVal))
742 InstToFix.push_back(Inst);
744 // All all of the instructions that use the scalar as an operand...
745 for (Value::use_iterator UI = ScalarVal->use_begin(),
746 UE = ScalarVal->use_end(); UI != UE; ++UI)
747 InstToFix.push_back(cast<Instruction>(*UI));
750 // Eliminate duplicates by sorting, then removing equal neighbors.
751 sort(InstToFix.begin(), InstToFix.end());
752 InstToFix.erase(unique(InstToFix.begin(), InstToFix.end()), InstToFix.end());
754 // Loop over all of the instructions to transform, creating the new
755 // replacement instructions for them. This also unlinks them from the
756 // function so they can be safely deleted later.
758 map<Value*, Value*> XFormMap;
759 NewInstructionCreator NIC(*this, Scalars, CallMap, XFormMap);
761 // Visit all instructions... creating the new instructions that we need and
762 // unlinking the old instructions from the function...
764 for (unsigned i = 0, e = InstToFix.size(); i != e; ++i) {
765 cerr << "Fixing: " << InstToFix[i];
766 NIC.visit(InstToFix[i]);
768 //NIC.visit(InstToFix.begin(), InstToFix.end());
770 // Make all instructions we will delete "let go" of their operands... so that
771 // we can safely delete Arguments whose types have changed...
773 for_each(InstToFix.begin(), InstToFix.end(),
774 mem_fun(&Instruction::dropAllReferences));
776 // Loop through all of the pointer arguments coming into the function,
777 // replacing them with arguments of POINTERTYPE to match the function type of
780 FunctionType::ParamTypes::const_iterator TI =
781 F->getFunctionType()->getParamTypes().begin();
782 for (Function::ArgumentListType::iterator I = F->getArgumentList().begin(),
783 E = F->getArgumentList().end(); I != E; ++I, ++TI) {
785 if (Arg->getType() != *TI) {
786 assert(isa<PointerType>(Arg->getType()) && *TI == POINTERTYPE);
787 Argument *NewArg = new Argument(*TI, Arg->getName());
788 XFormMap[Arg] = NewArg; // Map old arg into new arg...
791 // Replace the old argument and then delete it...
792 delete F->getArgumentList().replaceWith(I, NewArg);
796 // Now that all of the new instructions have been created, we can update all
797 // of the references to dummy values to be references to the actual values
798 // that are computed.
800 NIC.updateReferences();
802 cerr << "TRANSFORMED FUNCTION:\n" << F;
805 // Delete all of the "instructions to fix"
806 for_each(InstToFix.begin(), InstToFix.end(), deleter<Instruction>);
808 // Since we have liberally hacked the function to pieces, we want to inform
809 // the datastructure pass that its internal representation is out of date.
811 DS->invalidateFunction(F);
814 static void addNodeMapping(DSNode *SrcNode, const PointerValSet &PVS,
815 map<DSNode*, PointerValSet> &NodeMapping) {
816 for (unsigned i = 0, e = PVS.size(); i != e; ++i)
817 if (NodeMapping[SrcNode].add(PVS[i])) { // Not in map yet?
818 assert(PVS[i].Index == 0 && "Node indexing not supported yet!");
819 DSNode *DestNode = PVS[i].Node;
821 // Loop over all of the outgoing links in the mapped graph
822 for (unsigned l = 0, le = DestNode->getNumOutgoingLinks(); l != le; ++l) {
823 PointerValSet &SrcSet = SrcNode->getOutgoingLink(l);
824 const PointerValSet &DestSet = DestNode->getOutgoingLink(l);
826 // Add all of the node mappings now!
827 for (unsigned si = 0, se = SrcSet.size(); si != se; ++si) {
828 assert(SrcSet[si].Index == 0 && "Can't handle node offset!");
829 addNodeMapping(SrcSet[si].Node, DestSet, NodeMapping);
835 // CalculateNodeMapping - There is a partial isomorphism between the graph
836 // passed in and the graph that is actually used by the function. We need to
837 // figure out what this mapping is so that we can transformFunctionBody the
838 // instructions in the function itself. Note that every node in the graph that
839 // we are interested in must be both in the local graph of the called function,
840 // and in the local graph of the calling function. Because of this, we only
841 // define the mapping for these nodes [conveniently these are the only nodes we
842 // CAN define a mapping for...]
844 // The roots of the graph that we are transforming is rooted in the arguments
845 // passed into the function from the caller. This is where we start our
846 // mapping calculation.
848 // The NodeMapping calculated maps from the callers graph to the called graph.
850 static void CalculateNodeMapping(Function *F, TransformFunctionInfo &TFI,
851 FunctionDSGraph &CallerGraph,
852 FunctionDSGraph &CalledGraph,
853 map<DSNode*, PointerValSet> &NodeMapping) {
855 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) {
856 // Figure out what nodes in the called graph the TFI.ArgInfo[i].Node node
859 // Only consider first node of sequence. Extra nodes may may be added
860 // to the TFI if the data structure requires more nodes than just the
861 // one the argument points to. We are only interested in the one the
862 // argument points to though.
864 if (TFI.ArgInfo[i].ArgNo != LastArgNo) {
865 if (TFI.ArgInfo[i].ArgNo == -1) {
866 addNodeMapping(TFI.ArgInfo[i].Node, CalledGraph.getRetNodes(),
869 // Figure out which node argument # ArgNo points to in the called graph.
870 Value *Arg = F->getArgumentList()[TFI.ArgInfo[i].ArgNo];
871 addNodeMapping(TFI.ArgInfo[i].Node, CalledGraph.getValueMap()[Arg],
874 LastArgNo = TFI.ArgInfo[i].ArgNo;
880 // transformFunction - Transform the specified function the specified way. It
881 // we have already transformed that function that way, don't do anything. The
882 // nodes in the TransformFunctionInfo come out of callers data structure graph.
884 void PoolAllocate::transformFunction(TransformFunctionInfo &TFI,
885 FunctionDSGraph &CallerIPGraph,
886 map<DSNode*, PoolInfo> &CallerPoolDesc) {
887 if (getTransformedFunction(TFI)) return; // Function xformation already done?
889 cerr << "********** Entering transformFunction for "
890 << TFI.Func->getName() << ":\n";
891 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i)
892 cerr << " ArgInfo[" << i << "] = " << TFI.ArgInfo[i].ArgNo << "\n";
895 const FunctionType *OldFuncType = TFI.Func->getFunctionType();
897 assert(!OldFuncType->isVarArg() && "Vararg functions not handled yet!");
899 // Build the type for the new function that we are transforming
900 vector<const Type*> ArgTys;
901 ArgTys.reserve(OldFuncType->getNumParams()+TFI.ArgInfo.size());
902 for (unsigned i = 0, e = OldFuncType->getNumParams(); i != e; ++i)
903 ArgTys.push_back(OldFuncType->getParamType(i));
905 const Type *RetType = OldFuncType->getReturnType();
907 // Add one pool pointer for every argument that needs to be supplemented.
908 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) {
909 if (TFI.ArgInfo[i].ArgNo == -1)
910 RetType = POINTERTYPE; // Return a pointer
912 ArgTys[TFI.ArgInfo[i].ArgNo] = POINTERTYPE; // Pass a pointer
913 ArgTys.push_back(PointerType::get(CallerPoolDesc.find(TFI.ArgInfo[i].Node)
917 // Build the new function type...
918 const FunctionType *NewFuncType = FunctionType::get(RetType, ArgTys,
919 OldFuncType->isVarArg());
921 // The new function is internal, because we know that only we can call it.
922 // This also helps subsequent IP transformations to eliminate duplicated pool
923 // pointers (which look like the same value is always passed into a parameter,
924 // allowing it to be easily eliminated).
926 Function *NewFunc = new Function(NewFuncType, true,
927 TFI.Func->getName()+".poolxform");
928 CurModule->getFunctionList().push_back(NewFunc);
931 cerr << "Created function prototype: " << NewFunc << "\n";
933 // Add the newly formed function to the TransformedFunctions table so that
934 // infinite recursion does not occur!
936 TransformedFunctions[TFI] = NewFunc;
938 // Add arguments to the function... starting with all of the old arguments
939 vector<Value*> ArgMap;
940 for (unsigned i = 0, e = TFI.Func->getArgumentList().size(); i != e; ++i) {
941 const Argument *OFA = TFI.Func->getArgumentList()[i];
942 Argument *NFA = new Argument(OFA->getType(), OFA->getName());
943 NewFunc->getArgumentList().push_back(NFA);
944 ArgMap.push_back(NFA); // Keep track of the arguments
947 // Now add all of the arguments corresponding to pools passed in...
948 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) {
949 CallArgInfo &AI = TFI.ArgInfo[i];
954 Name = ArgMap[AI.ArgNo]->getName(); // Get the arg name
955 const Type *Ty = PointerType::get(CallerPoolDesc[AI.Node].PoolType);
956 Argument *NFA = new Argument(Ty, Name+".pool");
957 NewFunc->getArgumentList().push_back(NFA);
960 // Now clone the body of the old function into the new function...
961 CloneFunctionInto(NewFunc, TFI.Func, ArgMap);
963 // Okay, now we have a function that is identical to the old one, except that
964 // it has extra arguments for the pools coming in. Now we have to get the
965 // data structure graph for the function we are replacing, and figure out how
966 // our graph nodes map to the graph nodes in the dest function.
968 FunctionDSGraph &DSGraph = DS->getClosedDSGraph(NewFunc);
970 // NodeMapping - Multimap from callers graph to called graph. We are
971 // guaranteed that the called function graph has more nodes than the caller,
972 // or exactly the same number of nodes. This is because the called function
973 // might not know that two nodes are merged when considering the callers
974 // context, but the caller obviously does. Because of this, a single node in
975 // the calling function's data structure graph can map to multiple nodes in
976 // the called functions graph.
978 map<DSNode*, PointerValSet> NodeMapping;
980 CalculateNodeMapping(NewFunc, TFI, CallerIPGraph, DSGraph,
983 // Print out the node mapping...
984 cerr << "\nNode mapping for call of " << NewFunc->getName() << "\n";
985 for (map<DSNode*, PointerValSet>::iterator I = NodeMapping.begin();
986 I != NodeMapping.end(); ++I) {
987 cerr << "Map: "; I->first->print(cerr);
988 cerr << "To: "; I->second.print(cerr);
992 // Fill in the PoolDescriptor information for the transformed function so that
993 // it can determine which value holds the pool descriptor for each data
994 // structure node that it accesses.
996 map<DSNode*, PoolInfo> PoolDescs;
998 cerr << "\nCalculating the pool descriptor map:\n";
1000 // Calculate as much of the pool descriptor map as possible. Since we have
1001 // the node mapping between the caller and callee functions, and we have the
1002 // pool descriptor information of the caller, we can calculate a partical pool
1003 // descriptor map for the called function.
1005 // The nodes that we do not have complete information for are the ones that
1006 // are accessed by loading pointers derived from arguments passed in, but that
1007 // are not passed in directly. In this case, we have all of the information
1008 // except a pool value. If the called function refers to this pool, the pool
1009 // value will be loaded from the pool graph and added to the map as neccesary.
1011 for (map<DSNode*, PointerValSet>::iterator I = NodeMapping.begin();
1012 I != NodeMapping.end(); ++I) {
1013 DSNode *CallerNode = I->first;
1014 PoolInfo &CallerPI = CallerPoolDesc[CallerNode];
1016 // Check to see if we have a node pointer passed in for this value...
1017 Value *CalleeValue = 0;
1018 for (unsigned a = 0, ae = TFI.ArgInfo.size(); a != ae; ++a)
1019 if (TFI.ArgInfo[a].Node == CallerNode) {
1020 // Calculate the argument number that the pool is to the function
1021 // call... The call instruction should not have the pool operands added
1023 unsigned ArgNo = TFI.Call->getNumOperands()-1+a;
1024 cerr << "Should be argument #: " << ArgNo << "[i = " << a << "]\n";
1025 assert(ArgNo < NewFunc->getArgumentList().size() &&
1026 "Call already has pool arguments added??");
1028 // Map the pool argument into the called function...
1029 CalleeValue = NewFunc->getArgumentList()[ArgNo];
1030 break; // Found value, quit loop
1033 // Loop over all of the data structure nodes that this incoming node maps to
1034 // Creating a PoolInfo structure for them.
1035 for (unsigned i = 0, e = I->second.size(); i != e; ++i) {
1036 assert(I->second[i].Index == 0 && "Doesn't handle subindexing yet!");
1037 DSNode *CalleeNode = I->second[i].Node;
1039 // Add the descriptor. We already know everything about it by now, much
1040 // of it is the same as the caller info.
1042 PoolDescs.insert(make_pair(CalleeNode,
1043 PoolInfo(CalleeNode, CalleeValue,
1045 CallerPI.PoolType)));
1049 // We must destroy the node mapping so that we don't have latent references
1050 // into the data structure graph for the new function. Otherwise we get
1051 // assertion failures when transformFunctionBody tries to invalidate the
1054 NodeMapping.clear();
1056 // Now that we know everything we need about the function, transform the body
1059 transformFunctionBody(NewFunc, DSGraph, PoolDescs);
1061 cerr << "Function after transformation:\n" << NewFunc;
1064 static unsigned countPointerTypes(const Type *Ty) {
1065 if (isa<PointerType>(Ty)) {
1067 } else if (StructType *STy = dyn_cast<StructType>(Ty)) {
1069 for (unsigned i = 0, e = STy->getElementTypes().size(); i != e; ++i)
1070 Num += countPointerTypes(STy->getElementTypes()[i]);
1072 } else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
1073 return countPointerTypes(ATy->getElementType());
1075 assert(Ty->isPrimitiveType() && "Unknown derived type!");
1080 // CreatePools - Insert instructions into the function we are processing to
1081 // create all of the memory pool objects themselves. This also inserts
1082 // destruction code. Add an alloca for each pool that is allocated to the
1083 // PoolDescs vector.
1085 void PoolAllocate::CreatePools(Function *F, const vector<AllocDSNode*> &Allocs,
1086 map<DSNode*, PoolInfo> &PoolDescs) {
1087 // Find all of the return nodes in the function...
1088 vector<BasicBlock*> ReturnNodes;
1089 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
1090 if (isa<ReturnInst>((*I)->getTerminator()))
1091 ReturnNodes.push_back(*I);
1093 map<DSNode*, PATypeHolder> AbsPoolTyMap;
1095 // First pass over the allocations to process...
1096 for (unsigned i = 0, e = Allocs.size(); i != e; ++i) {
1097 // Create the pooldescriptor mapping... with null entries for everything
1098 // except the node & NewType fields.
1100 map<DSNode*, PoolInfo>::iterator PI =
1101 PoolDescs.insert(make_pair(Allocs[i], PoolInfo(Allocs[i]))).first;
1103 // Add a symbol table entry for the new type if there was one for the old
1105 string OldName = CurModule->getTypeName(Allocs[i]->getType());
1106 if (!OldName.empty())
1107 CurModule->addTypeName(OldName+".p", PI->second.NewType);
1109 // Create the abstract pool types that will need to be resolved in a second
1110 // pass once an abstract type is created for each pool.
1112 // Can only handle limited shapes for now...
1113 StructType *OldNodeTy = cast<StructType>(Allocs[i]->getType());
1114 vector<const Type*> PoolTypes;
1116 // Pool type is the first element of the pool descriptor type...
1117 PoolTypes.push_back(getPoolType(PoolDescs[Allocs[i]].NewType));
1119 unsigned NumPointers = countPointerTypes(OldNodeTy);
1120 while (NumPointers--) // Add a different opaque type for each pointer
1121 PoolTypes.push_back(OpaqueType::get());
1123 assert(Allocs[i]->getNumLinks() == PoolTypes.size()-1 &&
1124 "Node should have same number of pointers as pool!");
1126 StructType *PoolType = StructType::get(PoolTypes);
1128 // Add a symbol table entry for the pooltype if possible...
1129 if (!OldName.empty()) CurModule->addTypeName(OldName+".pool", PoolType);
1131 // Create the pool type, with opaque values for pointers...
1132 AbsPoolTyMap.insert(make_pair(Allocs[i], PoolType));
1133 #ifdef DEBUG_CREATE_POOLS
1134 cerr << "POOL TY: " << AbsPoolTyMap.find(Allocs[i])->second.get() << "\n";
1138 // Now that we have types for all of the pool types, link them all together.
1139 for (unsigned i = 0, e = Allocs.size(); i != e; ++i) {
1140 PATypeHolder &PoolTyH = AbsPoolTyMap.find(Allocs[i])->second;
1142 // Resolve all of the outgoing pointer types of this pool node...
1143 for (unsigned p = 0, pe = Allocs[i]->getNumLinks(); p != pe; ++p) {
1144 PointerValSet &PVS = Allocs[i]->getLink(p);
1145 assert(!PVS.empty() && "Outgoing edge is empty, field unused, can"
1146 " probably just leave the type opaque or something dumb.");
1148 for (Out = 0; AbsPoolTyMap.count(PVS[Out].Node) == 0; ++Out)
1149 assert(Out != PVS.size() && "No edge to an outgoing allocation node!?");
1151 assert(PVS[Out].Index == 0 && "Subindexing not implemented yet!");
1153 // The actual struct type could change each time through the loop, so it's
1154 // NOT loop invariant.
1155 StructType *PoolTy = cast<StructType>(PoolTyH.get());
1157 // Get the opaque type...
1159 cast<DerivedType>(PoolTy->getElementTypes()[p+1].get());
1161 #ifdef DEBUG_CREATE_POOLS
1162 cerr << "Refining " << ElTy << " of " << PoolTy << " to "
1163 << AbsPoolTyMap.find(PVS[Out].Node)->second.get() << "\n";
1166 const Type *RefPoolTy = AbsPoolTyMap.find(PVS[Out].Node)->second.get();
1167 ElTy->refineAbstractTypeTo(PointerType::get(RefPoolTy));
1169 #ifdef DEBUG_CREATE_POOLS
1170 cerr << "Result pool type is: " << PoolTyH.get() << "\n";
1175 // Create the code that goes in the entry and exit nodes for the function...
1176 vector<Instruction*> EntryNodeInsts;
1177 for (unsigned i = 0, e = Allocs.size(); i != e; ++i) {
1178 PoolInfo &PI = PoolDescs[Allocs[i]];
1180 // Fill in the pool type for this pool...
1181 PI.PoolType = AbsPoolTyMap.find(Allocs[i])->second.get();
1182 assert(!PI.PoolType->isAbstract() &&
1183 "Pool type should not be abstract anymore!");
1185 // Add an allocation and a free for each pool...
1186 AllocaInst *PoolAlloc
1187 = new AllocaInst(PointerType::get(PI.PoolType), 0,
1188 CurModule->getTypeName(PI.PoolType));
1189 PI.Handle = PoolAlloc;
1190 EntryNodeInsts.push_back(PoolAlloc);
1191 AllocationInst *AI = Allocs[i]->getAllocation();
1193 // Initialize the pool. We need to know how big each allocation is. For
1194 // our purposes here, we assume we are allocating a scalar, or array of
1197 unsigned ElSize = TargetData.getTypeSize(AI->getAllocatedType());
1198 ElSize *= cast<ConstantUInt>(AI->getArraySize())->getValue();
1200 vector<Value*> Args;
1201 Args.push_back(ConstantUInt::get(Type::UIntTy, ElSize));
1202 Args.push_back(PoolAlloc); // Pool to initialize
1203 EntryNodeInsts.push_back(new CallInst(PoolInit, Args));
1205 // Add code to destroy the pool in all of the exit nodes of the function...
1207 Args.push_back(PoolAlloc); // Pool to initialize
1209 for (unsigned EN = 0, ENE = ReturnNodes.size(); EN != ENE; ++EN) {
1210 Instruction *Destroy = new CallInst(PoolDestroy, Args);
1212 // Insert it before the return instruction...
1213 BasicBlock *RetNode = ReturnNodes[EN];
1214 RetNode->getInstList().insert(RetNode->end()-1, Destroy);
1218 // Now that all of the pool descriptors have been created, link them together
1219 // so that called functions can get links as neccesary...
1221 for (unsigned i = 0, e = Allocs.size(); i != e; ++i) {
1222 PoolInfo &PI = PoolDescs[Allocs[i]];
1224 // For every pointer in the data structure, initialize a link that
1225 // indicates which pool to access...
1227 vector<Value*> Indices(2);
1228 Indices[0] = ConstantUInt::get(Type::UIntTy, 0);
1229 for (unsigned l = 0, le = PI.Node->getNumLinks(); l != le; ++l)
1230 // Only store an entry for the field if the field is used!
1231 if (!PI.Node->getLink(l).empty()) {
1232 assert(PI.Node->getLink(l).size() == 1 && "Should have only one link!");
1233 PointerVal PV = PI.Node->getLink(l)[0];
1234 assert(PV.Index == 0 && "Subindexing not supported yet!");
1235 PoolInfo &LinkedPool = PoolDescs[PV.Node];
1236 Indices[1] = ConstantUInt::get(Type::UByteTy, 1+l);
1238 EntryNodeInsts.push_back(new StoreInst(LinkedPool.Handle, PI.Handle,
1243 // Insert the entry node code into the entry block...
1244 F->getEntryNode()->getInstList().insert(F->getEntryNode()->begin()+1,
1245 EntryNodeInsts.begin(),
1246 EntryNodeInsts.end());
1250 // addPoolPrototypes - Add prototypes for the pool functions to the specified
1251 // module and update the Pool* instance variables to point to them.
1253 void PoolAllocate::addPoolPrototypes(Module *M) {
1254 // Get poolinit function...
1255 vector<const Type*> Args;
1256 Args.push_back(Type::UIntTy); // Num bytes per element
1257 FunctionType *PoolInitTy = FunctionType::get(Type::VoidTy, Args, true);
1258 PoolInit = M->getOrInsertFunction("poolinit", PoolInitTy);
1260 // Get pooldestroy function...
1261 Args.pop_back(); // Only takes a pool...
1262 FunctionType *PoolDestroyTy = FunctionType::get(Type::VoidTy, Args, true);
1263 PoolDestroy = M->getOrInsertFunction("pooldestroy", PoolDestroyTy);
1265 // Get the poolalloc function...
1266 FunctionType *PoolAllocTy = FunctionType::get(POINTERTYPE, Args, true);
1267 PoolAlloc = M->getOrInsertFunction("poolalloc", PoolAllocTy);
1269 // Get the poolfree function...
1270 Args.push_back(POINTERTYPE); // Pointer to free
1271 FunctionType *PoolFreeTy = FunctionType::get(Type::VoidTy, Args, true);
1272 PoolFree = M->getOrInsertFunction("poolfree", PoolFreeTy);
1274 // Add the %PoolTy type to the symbol table of the module...
1275 //M->addTypeName("PoolTy", PoolTy->getElementType());
1279 bool PoolAllocate::run(Module *M) {
1280 addPoolPrototypes(M);
1283 DS = &getAnalysis<DataStructure>();
1284 bool Changed = false;
1286 // We cannot use an iterator here because it will get invalidated when we add
1287 // functions to the module later...
1288 for (unsigned i = 0; i != M->size(); ++i)
1289 if (!M->getFunctionList()[i]->isExternal()) {
1290 Changed |= processFunction(M->getFunctionList()[i]);
1292 cerr << "Only processing one function\n";
1303 // createPoolAllocatePass - Global function to access the functionality of this
1306 Pass *createPoolAllocatePass() { return new PoolAllocate(); }