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 // This pass requires a DCE & instcombine pass to be run after it for best
10 //===----------------------------------------------------------------------===//
12 #include "llvm/Transforms/IPO/PoolAllocate.h"
13 #include "llvm/Transforms/Utils/CloneFunction.h"
14 #include "llvm/Analysis/DataStructureGraph.h"
15 #include "llvm/Module.h"
16 #include "llvm/iMemory.h"
17 #include "llvm/iTerminators.h"
18 #include "llvm/iPHINode.h"
19 #include "llvm/iOther.h"
20 #include "llvm/DerivedTypes.h"
21 #include "llvm/Constants.h"
22 #include "llvm/Target/TargetData.h"
23 #include "llvm/Support/InstVisitor.h"
24 #include "Support/DepthFirstIterator.h"
25 #include "Support/STLExtras.h"
35 // DEBUG_CREATE_POOLS - Enable this to turn on debug output for the pool
36 // creation phase in the top level function of a transformed data structure.
38 //#define DEBUG_CREATE_POOLS 1
40 // DEBUG_TRANSFORM_PROGRESS - Enable this to get lots of debug output on what
41 // the transformation is doing.
43 //#define DEBUG_TRANSFORM_PROGRESS 1
45 // DEBUG_POOLBASE_LOAD_ELIMINATOR - Turn this on to get statistics about how
46 // many static loads were eliminated from a function...
48 #define DEBUG_POOLBASE_LOAD_ELIMINATOR 1
50 #include "Support/CommandLine.h"
52 Ptr8bits, Ptr16bits, Ptr32bits
55 static cl::opt<PtrSize>
56 ReqPointerSize("poolalloc-ptr-size",
57 cl::desc("Set pointer size for -poolalloc pass"),
59 clEnumValN(Ptr32bits, "32", "Use 32 bit indices for pointers"),
60 clEnumValN(Ptr16bits, "16", "Use 16 bit indices for pointers"),
61 clEnumValN(Ptr8bits , "8", "Use 8 bit indices for pointers"),
65 DisableRLE("no-pool-load-elim", cl::Hidden,
66 cl::desc("Disable pool load elimination after poolalloc pass"));
68 const Type *POINTERTYPE;
70 // FIXME: This is dependant on the sparc backend layout conventions!!
71 static TargetData TargetData("test");
73 static const Type *getPointerTransformedType(const Type *Ty) {
74 if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
76 } else if (const StructType *STy = dyn_cast<StructType>(Ty)) {
77 vector<const Type *> NewElTypes;
78 NewElTypes.reserve(STy->getElementTypes().size());
79 for (StructType::ElementTypes::const_iterator
80 I = STy->getElementTypes().begin(),
81 E = STy->getElementTypes().end(); I != E; ++I)
82 NewElTypes.push_back(getPointerTransformedType(*I));
83 return StructType::get(NewElTypes);
84 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
85 return ArrayType::get(getPointerTransformedType(ATy->getElementType()),
86 ATy->getNumElements());
88 assert(Ty->isPrimitiveType() && "Unknown derived type!");
95 DSNode *Node; // The node this pool allocation represents
96 Value *Handle; // LLVM value of the pool in the current context
97 const Type *NewType; // The transformed type of the memory objects
98 const Type *PoolType; // The type of the pool
100 const Type *getOldType() const { return Node->getType(); }
102 PoolInfo() { // Define a default ctor for map::operator[]
103 cerr << "Map subscript used to get element that doesn't exist!\n";
107 PoolInfo(DSNode *N, Value *H, const Type *NT, const Type *PT)
108 : Node(N), Handle(H), NewType(NT), PoolType(PT) {
109 // Handle can be null...
110 assert(N && NT && PT && "Pool info null!");
113 PoolInfo(DSNode *N) : Node(N), Handle(0), NewType(0), PoolType(0) {
114 assert(N && "Invalid pool info!");
116 // The new type of the memory object is the same as the old type, except
117 // that all of the pointer values are replaced with POINTERTYPE values.
118 NewType = getPointerTransformedType(getOldType());
122 // ScalarInfo - Information about an LLVM value that we know points to some
123 // datastructure we are processing.
126 Value *Val; // Scalar value in Current Function
127 PoolInfo Pool; // The pool the scalar points into
129 ScalarInfo(Value *V, const PoolInfo &PI) : Val(V), Pool(PI) {
130 assert(V && "Null value passed to ScalarInfo ctor!");
134 // CallArgInfo - Information on one operand for a call that got expanded.
136 int ArgNo; // Call argument number this corresponds to
137 DSNode *Node; // The graph node for the pool
138 Value *PoolHandle; // The LLVM value that is the pool pointer
140 CallArgInfo(int Arg, DSNode *N, Value *PH)
141 : ArgNo(Arg), Node(N), PoolHandle(PH) {
142 assert(Arg >= -1 && N && PH && "Illegal values to CallArgInfo ctor!");
145 // operator< when sorting, sort by argument number.
146 bool operator<(const CallArgInfo &CAI) const {
147 return ArgNo < CAI.ArgNo;
151 // TransformFunctionInfo - Information about how a function eeds to be
154 struct TransformFunctionInfo {
155 // ArgInfo - Maintain information about the arguments that need to be
156 // processed. Each CallArgInfo corresponds to an argument that needs to
157 // have a pool pointer passed into the transformed function with it.
159 // As a special case, "argument" number -1 corresponds to the return value.
161 vector<CallArgInfo> ArgInfo;
163 // Func - The function to be transformed...
166 // The call instruction that is used to map CallArgInfo PoolHandle values
167 // into the new function values.
171 TransformFunctionInfo() : Func(0), Call(0) {}
173 bool operator<(const TransformFunctionInfo &TFI) const {
174 if (Func < TFI.Func) return true;
175 if (Func > TFI.Func) return false;
176 if (ArgInfo.size() < TFI.ArgInfo.size()) return true;
177 if (ArgInfo.size() > TFI.ArgInfo.size()) return false;
178 return ArgInfo < TFI.ArgInfo;
181 void finalizeConstruction() {
182 // Sort the vector so that the return value is first, followed by the
183 // argument records, in order. Note that this must be a stable sort so
184 // that the entries with the same sorting criteria (ie they are multiple
185 // pool entries for the same argument) are kept in depth first order.
186 std::stable_sort(ArgInfo.begin(), ArgInfo.end());
189 // addCallInfo - For a specified function call CI, figure out which pool
190 // descriptors need to be passed in as arguments, and which arguments need
191 // to be transformed into indices. If Arg != -1, the specified call
192 // argument is passed in as a pointer to a data structure.
194 void addCallInfo(DataStructure *DS, CallInst *CI, int Arg,
195 DSNode *GraphNode, map<DSNode*, PoolInfo> &PoolDescs);
197 // Make sure that all dependant arguments are added to this transformation
198 // info. For example, if we call foo(null, P) and foo treats it's first and
199 // second arguments as belonging to the same data structure, the we MUST add
200 // entries to know that the null needs to be transformed into an index as
203 void ensureDependantArgumentsIncluded(DataStructure *DS,
204 map<DSNode*, PoolInfo> &PoolDescs);
208 // Define the pass class that we implement...
209 struct PoolAllocate : public Pass {
210 const char *getPassName() const { return "Pool Allocate"; }
213 switch (ReqPointerSize) {
214 case Ptr32bits: POINTERTYPE = Type::UIntTy; break;
215 case Ptr16bits: POINTERTYPE = Type::UShortTy; break;
216 case Ptr8bits: POINTERTYPE = Type::UByteTy; break;
219 CurModule = 0; DS = 0;
220 PoolInit = PoolDestroy = PoolAlloc = PoolFree = 0;
223 // getPoolType - Get the type used by the backend for a pool of a particular
224 // type. This pool record is used to allocate nodes of type NodeType.
226 // Here, PoolTy = { NodeType*, sbyte*, uint }*
228 const StructType *getPoolType(const Type *NodeType) {
229 vector<const Type*> PoolElements;
230 PoolElements.push_back(PointerType::get(NodeType));
231 PoolElements.push_back(PointerType::get(Type::SByteTy));
232 PoolElements.push_back(Type::UIntTy);
233 StructType *Result = StructType::get(PoolElements);
235 // Add a name to the symbol table to correspond to the backend
236 // representation of this pool...
237 assert(CurModule && "No current module!?");
238 string Name = CurModule->getTypeName(NodeType);
239 if (Name.empty()) Name = CurModule->getTypeName(PoolElements[0]);
240 CurModule->addTypeName(Name+"oolbe", Result);
247 // getAnalysisUsage - This function requires data structure information
248 // to be able to see what is pool allocatable.
250 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
251 AU.addRequired(DataStructure::ID);
255 // CurModule - The module being processed.
258 // DS - The data structure graph for the module being processed.
261 // Prototypes that we add to support pool allocation...
262 Function *PoolInit, *PoolDestroy, *PoolAlloc, *PoolAllocArray, *PoolFree;
264 // The map of already transformed functions... note that the keys of this
265 // map do not have meaningful values for 'Call' or the 'PoolHandle' elements
266 // of the ArgInfo elements.
268 map<TransformFunctionInfo, Function*> TransformedFunctions;
270 // getTransformedFunction - Get a transformed function, or return null if
271 // the function specified hasn't been transformed yet.
273 Function *getTransformedFunction(TransformFunctionInfo &TFI) const {
274 map<TransformFunctionInfo, Function*>::const_iterator I =
275 TransformedFunctions.find(TFI);
276 if (I != TransformedFunctions.end()) return I->second;
281 // addPoolPrototypes - Add prototypes for the pool functions to the
282 // specified module and update the Pool* instance variables to point to
285 void addPoolPrototypes(Module &M);
288 // CreatePools - Insert instructions into the function we are processing to
289 // create all of the memory pool objects themselves. This also inserts
290 // destruction code. Add an alloca for each pool that is allocated to the
293 void CreatePools(Function *F, const vector<AllocDSNode*> &Allocs,
294 map<DSNode*, PoolInfo> &PoolDescs);
296 // processFunction - Convert a function to use pool allocation where
299 bool processFunction(Function *F);
301 // transformFunctionBody - This transforms the instruction in 'F' to use the
302 // pools specified in PoolDescs when modifying data structure nodes
303 // specified in the PoolDescs map. IPFGraph is the closed data structure
304 // graph for F, of which the PoolDescriptor nodes come from.
306 void transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
307 map<DSNode*, PoolInfo> &PoolDescs);
309 // transformFunction - Transform the specified function the specified way.
310 // It we have already transformed that function that way, don't do anything.
311 // The nodes in the TransformFunctionInfo come out of callers data structure
312 // graph, and the PoolDescs passed in are the caller's.
314 void transformFunction(TransformFunctionInfo &TFI,
315 FunctionDSGraph &CallerIPGraph,
316 map<DSNode*, PoolInfo> &PoolDescs);
321 // isNotPoolableAlloc - This is a predicate that returns true if the specified
322 // allocation node in a data structure graph is eligable for pool allocation.
324 static bool isNotPoolableAlloc(const AllocDSNode *DS) {
325 if (DS->isAllocaNode()) return true; // Do not pool allocate alloca's.
329 // processFunction - Convert a function to use pool allocation where
332 bool PoolAllocate::processFunction(Function *F) {
333 // Get the closed datastructure graph for the current function... if there are
334 // any allocations in this graph that are not escaping, we need to pool
335 // allocate them here!
337 FunctionDSGraph &IPGraph = DS->getClosedDSGraph(F);
339 // Get all of the allocations that do not escape the current function. Since
340 // they are still live (they exist in the graph at all), this means we must
341 // have scalar references to these nodes, but the scalars are never returned.
343 vector<AllocDSNode*> Allocs;
344 IPGraph.getNonEscapingAllocations(Allocs);
346 // Filter out allocations that we cannot handle. Currently, this includes
347 // variable sized array allocations and alloca's (which we do not want to
350 Allocs.erase(std::remove_if(Allocs.begin(), Allocs.end(), isNotPoolableAlloc),
354 if (Allocs.empty()) return false; // Nothing to do.
356 #ifdef DEBUG_TRANSFORM_PROGRESS
357 cerr << "Transforming Function: " << F->getName() << "\n";
360 // Insert instructions into the function we are processing to create all of
361 // the memory pool objects themselves. This also inserts destruction code.
362 // This fills in the PoolDescs map to associate the alloc node with the
363 // allocation of the memory pool corresponding to it.
365 map<DSNode*, PoolInfo> PoolDescs;
366 CreatePools(F, Allocs, PoolDescs);
368 #ifdef DEBUG_TRANSFORM_PROGRESS
369 cerr << "Transformed Entry Function: \n" << F;
372 // Now we need to figure out what called functions we need to transform, and
373 // how. To do this, we look at all of the scalars, seeing which functions are
374 // either used as a scalar value (so they return a data structure), or are
375 // passed one of our scalar values.
377 transformFunctionBody(F, IPGraph, PoolDescs);
383 //===----------------------------------------------------------------------===//
385 // NewInstructionCreator - This class is used to traverse the function being
386 // modified, changing each instruction visit'ed to use and provide pointer
387 // indexes instead of real pointers. This is what changes the body of a
388 // function to use pool allocation.
390 class NewInstructionCreator : public InstVisitor<NewInstructionCreator> {
391 PoolAllocate &PoolAllocator;
392 vector<ScalarInfo> &Scalars;
393 map<CallInst*, TransformFunctionInfo> &CallMap;
394 map<Value*, Value*> &XFormMap; // Map old pointers to new indexes
397 Instruction *I; // Instruction to update
398 unsigned OpNum; // Operand number to update
399 Value *OldVal; // The old value it had
401 RefToUpdate(Instruction *i, unsigned o, Value *ov)
402 : I(i), OpNum(o), OldVal(ov) {}
404 vector<RefToUpdate> ReferencesToUpdate;
406 const ScalarInfo &getScalarRef(const Value *V) {
407 for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
408 if (Scalars[i].Val == V) return Scalars[i];
410 cerr << "Could not find scalar " << V << " in scalar map!\n";
411 assert(0 && "Scalar not found in getScalar!");
416 const ScalarInfo *getScalar(const Value *V) {
417 for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
418 if (Scalars[i].Val == V) return &Scalars[i];
422 BasicBlock::iterator ReplaceInstWith(Instruction &I, Instruction *New) {
423 BasicBlock *BB = I.getParent();
424 BasicBlock::iterator RI = &I;
425 BB->getInstList().remove(RI);
426 BB->getInstList().insert(RI, New);
431 Instruction *createPoolBaseInstruction(Value *PtrVal) {
432 const ScalarInfo &SC = getScalarRef(PtrVal);
433 vector<Value*> Args(3);
434 Args[0] = ConstantUInt::get(Type::UIntTy, 0); // No pointer offset
435 Args[1] = ConstantUInt::get(Type::UByteTy, 0); // Field #0 of pool descriptr
436 Args[2] = ConstantUInt::get(Type::UByteTy, 0); // Field #0 of poolalloc val
437 return new LoadInst(SC.Pool.Handle, Args, PtrVal->getName()+".poolbase");
442 NewInstructionCreator(PoolAllocate &PA, vector<ScalarInfo> &S,
443 map<CallInst*, TransformFunctionInfo> &C,
444 map<Value*, Value*> &X)
445 : PoolAllocator(PA), Scalars(S), CallMap(C), XFormMap(X) {}
448 // updateReferences - The NewInstructionCreator is responsible for creating
449 // new instructions to replace the old ones in the function, and then link up
450 // references to values to their new values. For it to do this, however, it
451 // keeps track of information about the value mapping of old values to new
452 // values that need to be patched up. Given this value map and a set of
453 // instruction operands to patch, updateReferences performs the updates.
455 void updateReferences() {
456 for (unsigned i = 0, e = ReferencesToUpdate.size(); i != e; ++i) {
457 RefToUpdate &Ref = ReferencesToUpdate[i];
458 Value *NewVal = XFormMap[Ref.OldVal];
461 if (isa<Constant>(Ref.OldVal) && // Refering to a null ptr?
462 cast<Constant>(Ref.OldVal)->isNullValue()) {
463 // Transform the null pointer into a null index... caching in XFormMap
464 XFormMap[Ref.OldVal] = NewVal = Constant::getNullValue(POINTERTYPE);
465 //} else if (isa<Argument>(Ref.OldVal)) {
467 cerr << "Unknown reference to: " << Ref.OldVal << "\n";
468 assert(XFormMap[Ref.OldVal] &&
469 "Reference to value that was not updated found!");
473 Ref.I->setOperand(Ref.OpNum, NewVal);
475 ReferencesToUpdate.clear();
478 //===--------------------------------------------------------------------===//
479 // Transformation methods:
480 // These methods specify how each type of instruction is transformed by the
481 // NewInstructionCreator instance...
482 //===--------------------------------------------------------------------===//
484 void visitGetElementPtrInst(GetElementPtrInst &I) {
485 assert(0 && "Cannot transform get element ptr instructions yet!");
488 // Replace the load instruction with a new one.
489 void visitLoadInst(LoadInst &I) {
490 vector<Instruction *> BeforeInsts;
492 // Cast our index to be a UIntTy so we can use it to index into the pool...
493 CastInst *Index = new CastInst(Constant::getNullValue(POINTERTYPE),
494 Type::UIntTy, I.getOperand(0)->getName());
495 BeforeInsts.push_back(Index);
496 ReferencesToUpdate.push_back(RefToUpdate(Index, 0, I.getOperand(0)));
498 // Include the pool base instruction...
499 Instruction *PoolBase = createPoolBaseInstruction(I.getOperand(0));
500 BeforeInsts.push_back(PoolBase);
502 Instruction *IdxInst =
503 BinaryOperator::create(Instruction::Add, *I.idx_begin(), Index,
505 BeforeInsts.push_back(IdxInst);
507 vector<Value*> Indices(I.idx_begin(), I.idx_end());
508 Indices[0] = IdxInst;
509 Instruction *Address = new GetElementPtrInst(PoolBase, Indices,
510 I.getName()+".addr");
511 BeforeInsts.push_back(Address);
513 Instruction *NewLoad = new LoadInst(Address, I.getName());
515 // Replace the load instruction with the new load instruction...
516 BasicBlock::iterator II = ReplaceInstWith(I, NewLoad);
518 // Add all of the instructions before the load...
519 NewLoad->getParent()->getInstList().insert(II, BeforeInsts.begin(),
522 // If not yielding a pool allocated pointer, use the new load value as the
523 // value in the program instead of the old load value...
526 I.replaceAllUsesWith(NewLoad);
529 // Replace the store instruction with a new one. In the store instruction,
530 // the value stored could be a pointer type, meaning that the new store may
531 // have to change one or both of it's operands.
533 void visitStoreInst(StoreInst &I) {
534 assert(getScalar(I.getOperand(1)) &&
535 "Store inst found only storing pool allocated pointer. "
538 Value *Val = I.getOperand(0); // The value to store...
540 // Check to see if the value we are storing is a data structure pointer...
541 //if (const ScalarInfo *ValScalar = getScalar(I.getOperand(0)))
542 if (isa<PointerType>(I.getOperand(0)->getType()))
543 Val = Constant::getNullValue(POINTERTYPE); // Yes, store a dummy
545 Instruction *PoolBase = createPoolBaseInstruction(I.getOperand(1));
547 // Cast our index to be a UIntTy so we can use it to index into the pool...
548 CastInst *Index = new CastInst(Constant::getNullValue(POINTERTYPE),
549 Type::UIntTy, I.getOperand(1)->getName());
550 ReferencesToUpdate.push_back(RefToUpdate(Index, 0, I.getOperand(1)));
552 // Instructions to add after the Index...
553 vector<Instruction*> AfterInsts;
555 Instruction *IdxInst =
556 BinaryOperator::create(Instruction::Add, *I.idx_begin(), Index, "idx");
557 AfterInsts.push_back(IdxInst);
559 vector<Value*> Indices(I.idx_begin(), I.idx_end());
560 Indices[0] = IdxInst;
561 Instruction *Address = new GetElementPtrInst(PoolBase, Indices,
562 I.getName()+"storeaddr");
563 AfterInsts.push_back(Address);
565 Instruction *NewStore = new StoreInst(Val, Address);
566 AfterInsts.push_back(NewStore);
567 if (Val != I.getOperand(0)) // Value stored was a pointer?
568 ReferencesToUpdate.push_back(RefToUpdate(NewStore, 0, I.getOperand(0)));
571 // Replace the store instruction with the cast instruction...
572 BasicBlock::iterator II = ReplaceInstWith(I, Index);
574 // Add the pool base calculator instruction before the index...
575 II = ++Index->getParent()->getInstList().insert(II, PoolBase);
578 // Add the instructions that go after the index...
579 Index->getParent()->getInstList().insert(II, AfterInsts.begin(),
584 // Create call to poolalloc for every malloc instruction
585 void visitMallocInst(MallocInst &I) {
586 const ScalarInfo &SCI = getScalarRef(&I);
590 if (!I.isArrayAllocation()) {
591 Args.push_back(SCI.Pool.Handle);
592 Call = new CallInst(PoolAllocator.PoolAlloc, Args, I.getName());
594 Args.push_back(I.getArraySize());
595 Args.push_back(SCI.Pool.Handle);
596 Call = new CallInst(PoolAllocator.PoolAllocArray, Args, I.getName());
599 ReplaceInstWith(I, Call);
602 // Convert a call to poolfree for every free instruction...
603 void visitFreeInst(FreeInst &I) {
604 // Create a new call to poolfree before the free instruction
606 Args.push_back(Constant::getNullValue(POINTERTYPE));
607 Args.push_back(getScalarRef(I.getOperand(0)).Pool.Handle);
608 Instruction *NewCall = new CallInst(PoolAllocator.PoolFree, Args);
609 ReplaceInstWith(I, NewCall);
610 ReferencesToUpdate.push_back(RefToUpdate(NewCall, 1, I.getOperand(0)));
613 // visitCallInst - Create a new call instruction with the extra arguments for
614 // all of the memory pools that the call needs.
616 void visitCallInst(CallInst &I) {
617 TransformFunctionInfo &TI = CallMap[&I];
619 // Start with all of the old arguments...
620 vector<Value*> Args(I.op_begin()+1, I.op_end());
622 for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i) {
623 // Replace all of the pointer arguments with our new pointer typed values.
624 if (TI.ArgInfo[i].ArgNo != -1)
625 Args[TI.ArgInfo[i].ArgNo] = Constant::getNullValue(POINTERTYPE);
627 // Add all of the pool arguments...
628 Args.push_back(TI.ArgInfo[i].PoolHandle);
631 Function *NF = PoolAllocator.getTransformedFunction(TI);
632 Instruction *NewCall = new CallInst(NF, Args, I.getName());
633 ReplaceInstWith(I, NewCall);
635 // Keep track of the mapping of operands so that we can resolve them to real
637 Value *RetVal = NewCall;
638 for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i)
639 if (TI.ArgInfo[i].ArgNo != -1)
640 ReferencesToUpdate.push_back(RefToUpdate(NewCall, TI.ArgInfo[i].ArgNo+1,
641 I.getOperand(TI.ArgInfo[i].ArgNo+1)));
643 RetVal = 0; // If returning a pointer, don't change retval...
645 // If not returning a pointer, use the new call as the value in the program
646 // instead of the old call...
649 I.replaceAllUsesWith(RetVal);
652 // visitPHINode - Create a new PHI node of POINTERTYPE for all of the old Phi
655 void visitPHINode(PHINode &PN) {
656 Value *DummyVal = Constant::getNullValue(POINTERTYPE);
657 PHINode *NewPhi = new PHINode(POINTERTYPE, PN.getName());
658 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
659 NewPhi->addIncoming(DummyVal, PN.getIncomingBlock(i));
660 ReferencesToUpdate.push_back(RefToUpdate(NewPhi, i*2,
661 PN.getIncomingValue(i)));
664 ReplaceInstWith(PN, NewPhi);
667 // visitReturnInst - Replace ret instruction with a new return...
668 void visitReturnInst(ReturnInst &I) {
669 Instruction *Ret = new ReturnInst(Constant::getNullValue(POINTERTYPE));
670 ReplaceInstWith(I, Ret);
671 ReferencesToUpdate.push_back(RefToUpdate(Ret, 0, I.getOperand(0)));
674 // visitSetCondInst - Replace a conditional test instruction with a new one
675 void visitSetCondInst(SetCondInst &SCI) {
676 BinaryOperator &I = (BinaryOperator&)SCI;
677 Value *DummyVal = Constant::getNullValue(POINTERTYPE);
678 BinaryOperator *New = BinaryOperator::create(I.getOpcode(), DummyVal,
679 DummyVal, I.getName());
680 ReplaceInstWith(I, New);
682 ReferencesToUpdate.push_back(RefToUpdate(New, 0, I.getOperand(0)));
683 ReferencesToUpdate.push_back(RefToUpdate(New, 1, I.getOperand(1)));
685 // Make sure branches refer to the new condition...
686 I.replaceAllUsesWith(New);
689 void visitInstruction(Instruction &I) {
690 cerr << "Unknown instruction to FunctionBodyTransformer:\n" << I;
695 // PoolBaseLoadEliminator - Every load and store through a pool allocated
696 // pointer causes a load of the real pool base out of the pool descriptor.
697 // Iterate through the function, doing a local elimination pass of duplicate
698 // loads. This attempts to turn the all too common:
700 // %reg109.poolbase22 = load %root.pool* %root.pool, uint 0, ubyte 0, ubyte 0
701 // %reg207 = load %root.p* %reg109.poolbase22, uint %reg109, ubyte 0, ubyte 0
702 // %reg109.poolbase23 = load %root.pool* %root.pool, uint 0, ubyte 0, ubyte 0
703 // store double %reg207, %root.p* %reg109.poolbase23, uint %reg109, ...
706 // %reg109.poolbase22 = load %root.pool* %root.pool, uint 0, ubyte 0, ubyte 0
707 // %reg207 = load %root.p* %reg109.poolbase22, uint %reg109, ubyte 0, ubyte 0
708 // store double %reg207, %root.p* %reg109.poolbase22, uint %reg109, ...
711 class PoolBaseLoadEliminator : public InstVisitor<PoolBaseLoadEliminator> {
712 // PoolDescValues - Keep track of the values in the current function that are
713 // pool descriptors (loads from which we want to eliminate).
715 vector<Value*> PoolDescValues;
717 // PoolDescMap - As we are analyzing a BB, keep track of which load to use
718 // when referencing a pool descriptor.
720 map<Value*, LoadInst*> PoolDescMap;
722 // These two fields keep track of statistics of how effective we are, if
723 // debugging is enabled.
725 unsigned Eliminated, Remaining;
727 // Compact the pool descriptor map into a list of the pool descriptors in the
728 // current context that we should know about...
730 PoolBaseLoadEliminator(const map<DSNode*, PoolInfo> &PoolDescs) {
731 Eliminated = Remaining = 0;
732 for (map<DSNode*, PoolInfo>::const_iterator I = PoolDescs.begin(),
733 E = PoolDescs.end(); I != E; ++I)
734 PoolDescValues.push_back(I->second.Handle);
736 // Remove duplicates from the list of pool values
737 sort(PoolDescValues.begin(), PoolDescValues.end());
738 PoolDescValues.erase(unique(PoolDescValues.begin(), PoolDescValues.end()),
739 PoolDescValues.end());
742 #ifdef DEBUG_POOLBASE_LOAD_ELIMINATOR
743 void visitFunction(Function &F) {
744 cerr << "Pool Load Elim '" << F.getName() << "'\t";
746 ~PoolBaseLoadEliminator() {
747 unsigned Total = Eliminated+Remaining;
749 cerr << "removed " << Eliminated << "["
750 << Eliminated*100/Total << "%] loads, leaving "
751 << Remaining << ".\n";
755 // Loop over the function, looking for loads to eliminate. Because we are a
756 // local transformation, we reset all of our state when we enter a new basic
759 void visitBasicBlock(BasicBlock &) {
760 PoolDescMap.clear(); // Forget state.
763 // Starting with an empty basic block, we scan it looking for loads of the
764 // pool descriptor. When we find a load, we add it to the PoolDescMap,
765 // indicating that we have a value available to recycle next time we see the
766 // poolbase of this instruction being loaded.
768 void visitLoadInst(LoadInst &LI) {
769 Value *LoadAddr = LI.getPointerOperand();
770 map<Value*, LoadInst*>::iterator VIt = PoolDescMap.find(LoadAddr);
771 if (VIt != PoolDescMap.end()) { // We already have a value for this load?
772 LI.replaceAllUsesWith(VIt->second); // Make the current load dead
775 // This load might not be a load of a pool pointer, check to see if it is
776 if (LI.getNumOperands() == 4 && // load pool, uint 0, ubyte 0, ubyte 0
777 find(PoolDescValues.begin(), PoolDescValues.end(), LoadAddr) !=
778 PoolDescValues.end()) {
780 assert("Make sure it's a load of the pool base, not a chaining field" &&
781 LI.getOperand(1) == Constant::getNullValue(Type::UIntTy) &&
782 LI.getOperand(2) == Constant::getNullValue(Type::UByteTy) &&
783 LI.getOperand(3) == Constant::getNullValue(Type::UByteTy));
785 // If it is a load of a pool base, keep track of it for future reference
786 PoolDescMap.insert(std::make_pair(LoadAddr, &LI));
792 // If we run across a function call, forget all state... Calls to
793 // poolalloc/poolfree can invalidate the pool base pointer, so it should be
794 // reloaded the next time it is used. Furthermore, a call to a random
795 // function might call one of these functions, so be conservative. Through
796 // more analysis, this could be improved in the future.
798 void visitCallInst(CallInst &) {
803 static void addNodeMapping(DSNode *SrcNode, const PointerValSet &PVS,
804 map<DSNode*, PointerValSet> &NodeMapping) {
805 for (unsigned i = 0, e = PVS.size(); i != e; ++i)
806 if (NodeMapping[SrcNode].add(PVS[i])) { // Not in map yet?
807 assert(PVS[i].Index == 0 && "Node indexing not supported yet!");
808 DSNode *DestNode = PVS[i].Node;
810 // Loop over all of the outgoing links in the mapped graph
811 for (unsigned l = 0, le = DestNode->getNumOutgoingLinks(); l != le; ++l) {
812 PointerValSet &SrcSet = SrcNode->getOutgoingLink(l);
813 const PointerValSet &DestSet = DestNode->getOutgoingLink(l);
815 // Add all of the node mappings now!
816 for (unsigned si = 0, se = SrcSet.size(); si != se; ++si) {
817 assert(SrcSet[si].Index == 0 && "Can't handle node offset!");
818 addNodeMapping(SrcSet[si].Node, DestSet, NodeMapping);
824 // CalculateNodeMapping - There is a partial isomorphism between the graph
825 // passed in and the graph that is actually used by the function. We need to
826 // figure out what this mapping is so that we can transformFunctionBody the
827 // instructions in the function itself. Note that every node in the graph that
828 // we are interested in must be both in the local graph of the called function,
829 // and in the local graph of the calling function. Because of this, we only
830 // define the mapping for these nodes [conveniently these are the only nodes we
831 // CAN define a mapping for...]
833 // The roots of the graph that we are transforming is rooted in the arguments
834 // passed into the function from the caller. This is where we start our
835 // mapping calculation.
837 // The NodeMapping calculated maps from the callers graph to the called graph.
839 static void CalculateNodeMapping(Function *F, TransformFunctionInfo &TFI,
840 FunctionDSGraph &CallerGraph,
841 FunctionDSGraph &CalledGraph,
842 map<DSNode*, PointerValSet> &NodeMapping) {
844 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) {
845 // Figure out what nodes in the called graph the TFI.ArgInfo[i].Node node
848 // Only consider first node of sequence. Extra nodes may may be added
849 // to the TFI if the data structure requires more nodes than just the
850 // one the argument points to. We are only interested in the one the
851 // argument points to though.
853 if (TFI.ArgInfo[i].ArgNo != LastArgNo) {
854 if (TFI.ArgInfo[i].ArgNo == -1) {
855 addNodeMapping(TFI.ArgInfo[i].Node, CalledGraph.getRetNodes(),
858 // Figure out which node argument # ArgNo points to in the called graph.
859 Function::aiterator AI = F->abegin();
860 std::advance(AI, TFI.ArgInfo[i].ArgNo);
861 addNodeMapping(TFI.ArgInfo[i].Node, CalledGraph.getValueMap()[AI],
864 LastArgNo = TFI.ArgInfo[i].ArgNo;
872 // addCallInfo - For a specified function call CI, figure out which pool
873 // descriptors need to be passed in as arguments, and which arguments need to be
874 // transformed into indices. If Arg != -1, the specified call argument is
875 // passed in as a pointer to a data structure.
877 void TransformFunctionInfo::addCallInfo(DataStructure *DS, CallInst *CI,
878 int Arg, DSNode *GraphNode,
879 map<DSNode*, PoolInfo> &PoolDescs) {
880 assert(CI->getCalledFunction() && "Cannot handle indirect calls yet!");
881 assert(Func == 0 || Func == CI->getCalledFunction() &&
882 "Function call record should always call the same function!");
883 assert(Call == 0 || Call == CI &&
884 "Call element already filled in with different value!");
885 Func = CI->getCalledFunction();
887 //FunctionDSGraph &CalledGraph = DS->getClosedDSGraph(Func);
889 // For now, add the entire graph that is pointed to by the call argument.
890 // This graph can and should be pruned to only what the function itself will
891 // use, because often this will be a dramatically smaller subset of what we
894 // FIXME: This should use pool links instead of extra arguments!
896 for (df_iterator<DSNode*> I = df_begin(GraphNode), E = df_end(GraphNode);
898 ArgInfo.push_back(CallArgInfo(Arg, *I, PoolDescs[*I].Handle));
901 static void markReachableNodes(const PointerValSet &Vals,
902 set<DSNode*> &ReachableNodes) {
903 for (unsigned n = 0, ne = Vals.size(); n != ne; ++n) {
904 DSNode *N = Vals[n].Node;
905 if (ReachableNodes.count(N) == 0) // Haven't already processed node?
906 ReachableNodes.insert(df_begin(N), df_end(N)); // Insert all
910 // Make sure that all dependant arguments are added to this transformation info.
911 // For example, if we call foo(null, P) and foo treats it's first and second
912 // arguments as belonging to the same data structure, the we MUST add entries to
913 // know that the null needs to be transformed into an index as well.
915 void TransformFunctionInfo::ensureDependantArgumentsIncluded(DataStructure *DS,
916 map<DSNode*, PoolInfo> &PoolDescs) {
917 // FIXME: This does not work for indirect function calls!!!
918 if (Func == 0) return; // FIXME!
920 // Make sure argument entries are sorted.
921 finalizeConstruction();
923 // Loop over the function signature, checking to see if there are any pointer
924 // arguments that we do not convert... if there is something we haven't
925 // converted, set done to false.
929 if (isa<PointerType>(Func->getReturnType())) // Make sure we convert retval
930 if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == -1) {
931 // We DO transform the ret val... skip all possible entries for retval
932 while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == -1)
939 for (Function::aiterator I = Func->abegin(), E = Func->aend(); I!=E; ++I,++i){
940 if (isa<PointerType>(I->getType())) {
941 if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == (int)i) {
942 // We DO transform this arg... skip all possible entries for argument
943 while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == (int)i)
952 // If we already have entries for all pointer arguments and retvals, there
953 // certainly is no work to do. Bail out early to avoid building relatively
954 // expensive data structures.
958 #ifdef DEBUG_TRANSFORM_PROGRESS
959 cerr << "Must ensure dependant arguments for: " << Func->getName() << "\n";
962 // Otherwise, we MIGHT have to add the arguments/retval if they are part of
963 // the same datastructure graph as some other argument or retval that we ARE
966 // Get the data structure graph for the called function.
968 FunctionDSGraph &CalledDS = DS->getClosedDSGraph(Func);
970 // Build a mapping between the nodes in our current graph and the nodes in the
971 // called function's graph. We build it based on our _incomplete_
972 // transformation information, because it contains all of the info that we
975 map<DSNode*, PointerValSet> NodeMapping;
976 CalculateNodeMapping(Func, *this,
977 DS->getClosedDSGraph(Call->getParent()->getParent()),
978 CalledDS, NodeMapping);
980 // Build the inverted version of the node mapping, that maps from a node in
981 // the called functions graph to a single node in the caller graph.
983 map<DSNode*, DSNode*> InverseNodeMap;
984 for (map<DSNode*, PointerValSet>::iterator I = NodeMapping.begin(),
985 E = NodeMapping.end(); I != E; ++I) {
986 PointerValSet &CalledNodes = I->second;
987 for (unsigned i = 0, e = CalledNodes.size(); i != e; ++i)
988 InverseNodeMap[CalledNodes[i].Node] = I->first;
990 NodeMapping.clear(); // Done with information, free memory
992 // Build a set of reachable nodes from the arguments/retval that we ARE
994 set<DSNode*> ReachableNodes;
996 // Loop through all of the arguments, marking all of the reachable data
997 // structure nodes reachable if they are from this pointer...
999 for (unsigned i = 0, e = ArgInfo.size(); i != e; ++i) {
1000 if (ArgInfo[i].ArgNo == -1) {
1001 if (i == 0) // Only process retvals once (performance opt)
1002 markReachableNodes(CalledDS.getRetNodes(), ReachableNodes);
1003 } else { // If it's an argument value...
1004 Function::aiterator AI = Func->abegin();
1005 std::advance(AI, ArgInfo[i].ArgNo);
1006 if (isa<PointerType>(AI->getType()))
1007 markReachableNodes(CalledDS.getValueMap()[AI], ReachableNodes);
1011 // Now that we know which nodes are already reachable, see if any of the
1012 // arguments that we are not passing values in for can reach one of the
1013 // existing nodes...
1016 // <FIXME> IN THEORY, we should allow arbitrary paths from the argument to
1017 // nodes we know about. The problem is that if we do this, then I don't know
1018 // how to get pool pointers for this head list. Since we are completely
1019 // deadline driven, I'll just allow direct accesses to the graph. </FIXME>
1023 if (isa<PointerType>(Func->getReturnType())) // Make sure we convert retval
1024 if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == -1) {
1025 // We DO transform the ret val... skip all possible entries for retval
1026 while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == -1)
1029 // See what the return value points to...
1031 // FIXME: This should generalize to any number of nodes, just see if any
1033 assert(CalledDS.getRetNodes().size() == 1 &&
1034 "Assumes only one node is returned");
1035 DSNode *N = CalledDS.getRetNodes()[0].Node;
1037 // If the return value is not marked as being passed in, but it NEEDS to
1038 // be transformed, then make it known now.
1040 if (ReachableNodes.count(N)) {
1041 #ifdef DEBUG_TRANSFORM_PROGRESS
1042 cerr << "ensure dependant arguments adds return value entry!\n";
1044 addCallInfo(DS, Call, -1, InverseNodeMap[N], PoolDescs);
1047 finalizeConstruction();
1052 for (Function::aiterator I = Func->abegin(), E = Func->aend(); I!=E; ++I, ++i)
1053 if (isa<PointerType>(I->getType())) {
1054 if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == (int)i) {
1055 // We DO transform this arg... skip all possible entries for argument
1056 while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == (int)i)
1059 // This should generalize to any number of nodes, just see if any are
1061 assert(CalledDS.getValueMap()[I].size() == 1 &&
1062 "Only handle case where pointing to one node so far!");
1064 // If the arg is not marked as being passed in, but it NEEDS to
1065 // be transformed, then make it known now.
1067 DSNode *N = CalledDS.getValueMap()[I][0].Node;
1068 if (ReachableNodes.count(N)) {
1069 #ifdef DEBUG_TRANSFORM_PROGRESS
1070 cerr << "ensure dependant arguments adds for arg #" << i << "\n";
1072 addCallInfo(DS, Call, i, InverseNodeMap[N], PoolDescs);
1075 finalizeConstruction();
1082 // transformFunctionBody - This transforms the instruction in 'F' to use the
1083 // pools specified in PoolDescs when modifying data structure nodes specified in
1084 // the PoolDescs map. Specifically, scalar values specified in the Scalars
1085 // vector must be remapped. IPFGraph is the closed data structure graph for F,
1086 // of which the PoolDescriptor nodes come from.
1088 void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
1089 map<DSNode*, PoolInfo> &PoolDescs) {
1091 // Loop through the value map looking for scalars that refer to nonescaping
1092 // allocations. Add them to the Scalars vector. Note that we may have
1093 // multiple entries in the Scalars vector for each value if it points to more
1096 map<Value*, PointerValSet> &ValMap = IPFGraph.getValueMap();
1097 vector<ScalarInfo> Scalars;
1099 #ifdef DEBUG_TRANSFORM_PROGRESS
1100 cerr << "Building scalar map for fn '" << F->getName() << "' body:\n";
1103 for (map<Value*, PointerValSet>::iterator I = ValMap.begin(),
1104 E = ValMap.end(); I != E; ++I) {
1105 const PointerValSet &PVS = I->second; // Set of things pointed to by scalar
1107 // Check to see if the scalar points to a data structure node...
1108 for (unsigned i = 0, e = PVS.size(); i != e; ++i) {
1109 if (PVS[i].Index) { cerr << "Problem in " << F->getName() << " for " << I->first << "\n"; }
1110 assert(PVS[i].Index == 0 && "Nonzero not handled yet!");
1112 // If the allocation is in the nonescaping set...
1113 map<DSNode*, PoolInfo>::iterator AI = PoolDescs.find(PVS[i].Node);
1114 if (AI != PoolDescs.end()) { // Add it to the list of scalars
1115 Scalars.push_back(ScalarInfo(I->first, AI->second));
1116 #ifdef DEBUG_TRANSFORM_PROGRESS
1117 cerr << "\nScalar Mapping from:" << I->first
1118 << "Scalar Mapping to: "; PVS.print(cerr);
1124 #ifdef DEBUG_TRANSFORM_PROGRESS
1125 cerr << "\nIn '" << F->getName()
1126 << "': Found the following values that point to poolable nodes:\n";
1128 for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
1129 cerr << Scalars[i].Val;
1133 // CallMap - Contain an entry for every call instruction that needs to be
1134 // transformed. Each entry in the map contains information about what we need
1135 // to do to each call site to change it to work.
1137 map<CallInst*, TransformFunctionInfo> CallMap;
1139 // Now we need to figure out what called functions we need to transform, and
1140 // how. To do this, we look at all of the scalars, seeing which functions are
1141 // either used as a scalar value (so they return a data structure), or are
1142 // passed one of our scalar values.
1144 for (unsigned i = 0, e = Scalars.size(); i != e; ++i) {
1145 Value *ScalarVal = Scalars[i].Val;
1147 // Check to see if the scalar _IS_ a call...
1148 if (CallInst *CI = dyn_cast<CallInst>(ScalarVal))
1149 // If so, add information about the pool it will be returning...
1150 CallMap[CI].addCallInfo(DS, CI, -1, Scalars[i].Pool.Node, PoolDescs);
1152 // Check to see if the scalar is an operand to a call...
1153 for (Value::use_iterator UI = ScalarVal->use_begin(),
1154 UE = ScalarVal->use_end(); UI != UE; ++UI) {
1155 if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
1156 // Find out which operand this is to the call instruction...
1157 User::op_iterator OI = find(CI->op_begin(), CI->op_end(), ScalarVal);
1158 assert(OI != CI->op_end() && "Call on use list but not an operand!?");
1159 assert(OI != CI->op_begin() && "Pointer operand is call destination?");
1161 // FIXME: This is broken if the same pointer is passed to a call more
1162 // than once! It will get multiple entries for the first pointer.
1164 // Add the operand number and pool handle to the call table...
1165 CallMap[CI].addCallInfo(DS, CI, OI-CI->op_begin()-1,
1166 Scalars[i].Pool.Node, PoolDescs);
1171 // Make sure that all dependant arguments are added as well. For example, if
1172 // we call foo(null, P) and foo treats it's first and second arguments as
1173 // belonging to the same data structure, the we MUST set up the CallMap to
1174 // know that the null needs to be transformed into an index as well.
1176 for (map<CallInst*, TransformFunctionInfo>::iterator I = CallMap.begin();
1177 I != CallMap.end(); ++I)
1178 I->second.ensureDependantArgumentsIncluded(DS, PoolDescs);
1180 #ifdef DEBUG_TRANSFORM_PROGRESS
1181 // Print out call map...
1182 for (map<CallInst*, TransformFunctionInfo>::iterator I = CallMap.begin();
1183 I != CallMap.end(); ++I) {
1184 cerr << "For call: " << I->first;
1185 cerr << I->second.Func->getName() << " must pass pool pointer for args #";
1186 for (unsigned i = 0; i < I->second.ArgInfo.size(); ++i)
1187 cerr << I->second.ArgInfo[i].ArgNo << ", ";
1192 // Loop through all of the call nodes, recursively creating the new functions
1193 // that we want to call... This uses a map to prevent infinite recursion and
1194 // to avoid duplicating functions unneccesarily.
1196 for (map<CallInst*, TransformFunctionInfo>::iterator I = CallMap.begin(),
1197 E = CallMap.end(); I != E; ++I) {
1198 // Transform all of the functions we need, or at least ensure there is a
1199 // cached version available.
1200 transformFunction(I->second, IPFGraph, PoolDescs);
1203 // Now that all of the functions that we want to call are available, transform
1204 // the local function so that it uses the pools locally and passes them to the
1205 // functions that we just hacked up.
1208 // First step, find the instructions to be modified.
1209 vector<Instruction*> InstToFix;
1210 for (unsigned i = 0, e = Scalars.size(); i != e; ++i) {
1211 Value *ScalarVal = Scalars[i].Val;
1213 // Check to see if the scalar _IS_ an instruction. If so, it is involved.
1214 if (Instruction *Inst = dyn_cast<Instruction>(ScalarVal))
1215 InstToFix.push_back(Inst);
1217 // All all of the instructions that use the scalar as an operand...
1218 for (Value::use_iterator UI = ScalarVal->use_begin(),
1219 UE = ScalarVal->use_end(); UI != UE; ++UI)
1220 InstToFix.push_back(cast<Instruction>(*UI));
1223 // Make sure that we get return instructions that return a null value from the
1226 if (!IPFGraph.getRetNodes().empty()) {
1227 assert(IPFGraph.getRetNodes().size() == 1 && "Can only return one node?");
1228 PointerVal RetNode = IPFGraph.getRetNodes()[0];
1229 assert(RetNode.Index == 0 && "Subindexing not implemented yet!");
1231 // Only process return instructions if the return value of this function is
1232 // part of one of the data structures we are transforming...
1234 if (PoolDescs.count(RetNode.Node)) {
1235 // Loop over all of the basic blocks, adding return instructions...
1236 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
1237 if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator()))
1238 InstToFix.push_back(RI);
1244 // Eliminate duplicates by sorting, then removing equal neighbors.
1245 sort(InstToFix.begin(), InstToFix.end());
1246 InstToFix.erase(unique(InstToFix.begin(), InstToFix.end()), InstToFix.end());
1248 // Loop over all of the instructions to transform, creating the new
1249 // replacement instructions for them. This also unlinks them from the
1250 // function so they can be safely deleted later.
1252 map<Value*, Value*> XFormMap;
1253 NewInstructionCreator NIC(*this, Scalars, CallMap, XFormMap);
1255 // Visit all instructions... creating the new instructions that we need and
1256 // unlinking the old instructions from the function...
1258 #ifdef DEBUG_TRANSFORM_PROGRESS
1259 for (unsigned i = 0, e = InstToFix.size(); i != e; ++i) {
1260 cerr << "Fixing: " << InstToFix[i];
1261 NIC.visit(*InstToFix[i]);
1264 NIC.visit(InstToFix.begin(), InstToFix.end());
1267 // Make all instructions we will delete "let go" of their operands... so that
1268 // we can safely delete Arguments whose types have changed...
1270 for_each(InstToFix.begin(), InstToFix.end(),
1271 std::mem_fun(&Instruction::dropAllReferences));
1273 // Loop through all of the pointer arguments coming into the function,
1274 // replacing them with arguments of POINTERTYPE to match the function type of
1277 FunctionType::ParamTypes::const_iterator TI =
1278 F->getFunctionType()->getParamTypes().begin();
1279 for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I, ++TI) {
1280 if (I->getType() != *TI) {
1281 assert(isa<PointerType>(I->getType()) && *TI == POINTERTYPE);
1282 Argument *NewArg = new Argument(*TI, I->getName());
1283 XFormMap[I] = NewArg; // Map old arg into new arg...
1285 // Replace the old argument and then delete it...
1286 I = F->getArgumentList().erase(I);
1287 I = F->getArgumentList().insert(I, NewArg);
1291 // Now that all of the new instructions have been created, we can update all
1292 // of the references to dummy values to be references to the actual values
1293 // that are computed.
1295 NIC.updateReferences();
1297 #ifdef DEBUG_TRANSFORM_PROGRESS
1298 cerr << "TRANSFORMED FUNCTION:\n" << F;
1301 // Delete all of the "instructions to fix"
1302 for_each(InstToFix.begin(), InstToFix.end(), deleter<Instruction>);
1304 // Eliminate pool base loads that we can easily prove are redundant
1306 PoolBaseLoadEliminator(PoolDescs).visit(F);
1308 // Since we have liberally hacked the function to pieces, we want to inform
1309 // the datastructure pass that its internal representation is out of date.
1311 DS->invalidateFunction(F);
1316 // transformFunction - Transform the specified function the specified way. It
1317 // we have already transformed that function that way, don't do anything. The
1318 // nodes in the TransformFunctionInfo come out of callers data structure graph.
1320 void PoolAllocate::transformFunction(TransformFunctionInfo &TFI,
1321 FunctionDSGraph &CallerIPGraph,
1322 map<DSNode*, PoolInfo> &CallerPoolDesc) {
1323 if (getTransformedFunction(TFI)) return; // Function xformation already done?
1325 #ifdef DEBUG_TRANSFORM_PROGRESS
1326 cerr << "********** Entering transformFunction for "
1327 << TFI.Func->getName() << ":\n";
1328 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i)
1329 cerr << " ArgInfo[" << i << "] = " << TFI.ArgInfo[i].ArgNo << "\n";
1333 const FunctionType *OldFuncType = TFI.Func->getFunctionType();
1335 assert(!OldFuncType->isVarArg() && "Vararg functions not handled yet!");
1337 // Build the type for the new function that we are transforming
1338 vector<const Type*> ArgTys;
1339 ArgTys.reserve(OldFuncType->getNumParams()+TFI.ArgInfo.size());
1340 for (unsigned i = 0, e = OldFuncType->getNumParams(); i != e; ++i)
1341 ArgTys.push_back(OldFuncType->getParamType(i));
1343 const Type *RetType = OldFuncType->getReturnType();
1345 // Add one pool pointer for every argument that needs to be supplemented.
1346 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) {
1347 if (TFI.ArgInfo[i].ArgNo == -1)
1348 RetType = POINTERTYPE; // Return a pointer
1350 ArgTys[TFI.ArgInfo[i].ArgNo] = POINTERTYPE; // Pass a pointer
1351 ArgTys.push_back(PointerType::get(CallerPoolDesc.find(TFI.ArgInfo[i].Node)
1352 ->second.PoolType));
1355 // Build the new function type...
1356 const FunctionType *NewFuncType = FunctionType::get(RetType, ArgTys,
1357 OldFuncType->isVarArg());
1359 // The new function is internal, because we know that only we can call it.
1360 // This also helps subsequent IP transformations to eliminate duplicated pool
1361 // pointers (which look like the same value is always passed into a parameter,
1362 // allowing it to be easily eliminated).
1364 Function *NewFunc = new Function(NewFuncType, true,
1365 TFI.Func->getName()+".poolxform");
1366 CurModule->getFunctionList().push_back(NewFunc);
1369 #ifdef DEBUG_TRANSFORM_PROGRESS
1370 cerr << "Created function prototype: " << NewFunc << "\n";
1373 // Add the newly formed function to the TransformedFunctions table so that
1374 // infinite recursion does not occur!
1376 TransformedFunctions[TFI] = NewFunc;
1378 // Add arguments to the function... starting with all of the old arguments
1379 vector<Value*> ArgMap;
1380 for (Function::const_aiterator I = TFI.Func->abegin(), E = TFI.Func->aend();
1382 Argument *NFA = new Argument(I->getType(), I->getName());
1383 NewFunc->getArgumentList().push_back(NFA);
1384 ArgMap.push_back(NFA); // Keep track of the arguments
1387 // Now add all of the arguments corresponding to pools passed in...
1388 for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) {
1389 CallArgInfo &AI = TFI.ArgInfo[i];
1394 Name = ArgMap[AI.ArgNo]->getName(); // Get the arg name
1395 const Type *Ty = PointerType::get(CallerPoolDesc[AI.Node].PoolType);
1396 Argument *NFA = new Argument(Ty, Name+".pool");
1397 NewFunc->getArgumentList().push_back(NFA);
1400 // Now clone the body of the old function into the new function...
1401 CloneFunctionInto(NewFunc, TFI.Func, ArgMap);
1403 // Okay, now we have a function that is identical to the old one, except that
1404 // it has extra arguments for the pools coming in. Now we have to get the
1405 // data structure graph for the function we are replacing, and figure out how
1406 // our graph nodes map to the graph nodes in the dest function.
1408 FunctionDSGraph &DSGraph = DS->getClosedDSGraph(NewFunc);
1410 // NodeMapping - Multimap from callers graph to called graph. We are
1411 // guaranteed that the called function graph has more nodes than the caller,
1412 // or exactly the same number of nodes. This is because the called function
1413 // might not know that two nodes are merged when considering the callers
1414 // context, but the caller obviously does. Because of this, a single node in
1415 // the calling function's data structure graph can map to multiple nodes in
1416 // the called functions graph.
1418 map<DSNode*, PointerValSet> NodeMapping;
1420 CalculateNodeMapping(NewFunc, TFI, CallerIPGraph, DSGraph,
1423 // Print out the node mapping...
1424 #ifdef DEBUG_TRANSFORM_PROGRESS
1425 cerr << "\nNode mapping for call of " << NewFunc->getName() << "\n";
1426 for (map<DSNode*, PointerValSet>::iterator I = NodeMapping.begin();
1427 I != NodeMapping.end(); ++I) {
1428 cerr << "Map: "; I->first->print(cerr);
1429 cerr << "To: "; I->second.print(cerr);
1434 // Fill in the PoolDescriptor information for the transformed function so that
1435 // it can determine which value holds the pool descriptor for each data
1436 // structure node that it accesses.
1438 map<DSNode*, PoolInfo> PoolDescs;
1440 #ifdef DEBUG_TRANSFORM_PROGRESS
1441 cerr << "\nCalculating the pool descriptor map:\n";
1444 // Calculate as much of the pool descriptor map as possible. Since we have
1445 // the node mapping between the caller and callee functions, and we have the
1446 // pool descriptor information of the caller, we can calculate a partical pool
1447 // descriptor map for the called function.
1449 // The nodes that we do not have complete information for are the ones that
1450 // are accessed by loading pointers derived from arguments passed in, but that
1451 // are not passed in directly. In this case, we have all of the information
1452 // except a pool value. If the called function refers to this pool, the pool
1453 // value will be loaded from the pool graph and added to the map as neccesary.
1455 for (map<DSNode*, PointerValSet>::iterator I = NodeMapping.begin();
1456 I != NodeMapping.end(); ++I) {
1457 DSNode *CallerNode = I->first;
1458 PoolInfo &CallerPI = CallerPoolDesc[CallerNode];
1460 // Check to see if we have a node pointer passed in for this value...
1461 Value *CalleeValue = 0;
1462 for (unsigned a = 0, ae = TFI.ArgInfo.size(); a != ae; ++a)
1463 if (TFI.ArgInfo[a].Node == CallerNode) {
1464 // Calculate the argument number that the pool is to the function
1465 // call... The call instruction should not have the pool operands added
1467 unsigned ArgNo = TFI.Call->getNumOperands()-1+a;
1468 #ifdef DEBUG_TRANSFORM_PROGRESS
1469 cerr << "Should be argument #: " << ArgNo << "[i = " << a << "]\n";
1471 assert(ArgNo < NewFunc->asize() &&
1472 "Call already has pool arguments added??");
1474 // Map the pool argument into the called function...
1475 Function::aiterator AI = NewFunc->abegin();
1476 std::advance(AI, ArgNo);
1478 break; // Found value, quit loop
1481 // Loop over all of the data structure nodes that this incoming node maps to
1482 // Creating a PoolInfo structure for them.
1483 for (unsigned i = 0, e = I->second.size(); i != e; ++i) {
1484 assert(I->second[i].Index == 0 && "Doesn't handle subindexing yet!");
1485 DSNode *CalleeNode = I->second[i].Node;
1487 // Add the descriptor. We already know everything about it by now, much
1488 // of it is the same as the caller info.
1490 PoolDescs.insert(std::make_pair(CalleeNode,
1491 PoolInfo(CalleeNode, CalleeValue,
1493 CallerPI.PoolType)));
1497 // We must destroy the node mapping so that we don't have latent references
1498 // into the data structure graph for the new function. Otherwise we get
1499 // assertion failures when transformFunctionBody tries to invalidate the
1502 NodeMapping.clear();
1504 // Now that we know everything we need about the function, transform the body
1507 transformFunctionBody(NewFunc, DSGraph, PoolDescs);
1509 #ifdef DEBUG_TRANSFORM_PROGRESS
1510 cerr << "Function after transformation:\n" << NewFunc;
1514 static unsigned countPointerTypes(const Type *Ty) {
1515 if (isa<PointerType>(Ty)) {
1517 } else if (const StructType *STy = dyn_cast<StructType>(Ty)) {
1519 for (unsigned i = 0, e = STy->getElementTypes().size(); i != e; ++i)
1520 Num += countPointerTypes(STy->getElementTypes()[i]);
1522 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
1523 return countPointerTypes(ATy->getElementType());
1525 assert(Ty->isPrimitiveType() && "Unknown derived type!");
1530 // CreatePools - Insert instructions into the function we are processing to
1531 // create all of the memory pool objects themselves. This also inserts
1532 // destruction code. Add an alloca for each pool that is allocated to the
1533 // PoolDescs vector.
1535 void PoolAllocate::CreatePools(Function *F, const vector<AllocDSNode*> &Allocs,
1536 map<DSNode*, PoolInfo> &PoolDescs) {
1537 // Find all of the return nodes in the function...
1538 vector<BasicBlock*> ReturnNodes;
1539 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
1540 if (isa<ReturnInst>(I->getTerminator()))
1541 ReturnNodes.push_back(I);
1543 #ifdef DEBUG_CREATE_POOLS
1544 cerr << "Allocs that we are pool allocating:\n";
1545 for (unsigned i = 0, e = Allocs.size(); i != e; ++i)
1549 map<DSNode*, PATypeHolder> AbsPoolTyMap;
1551 // First pass over the allocations to process...
1552 for (unsigned i = 0, e = Allocs.size(); i != e; ++i) {
1553 // Create the pooldescriptor mapping... with null entries for everything
1554 // except the node & NewType fields.
1556 map<DSNode*, PoolInfo>::iterator PI =
1557 PoolDescs.insert(std::make_pair(Allocs[i], PoolInfo(Allocs[i]))).first;
1559 // Add a symbol table entry for the new type if there was one for the old
1561 string OldName = CurModule->getTypeName(Allocs[i]->getType());
1562 if (OldName.empty()) OldName = "node";
1563 CurModule->addTypeName(OldName+".p", PI->second.NewType);
1565 // Create the abstract pool types that will need to be resolved in a second
1566 // pass once an abstract type is created for each pool.
1568 // Can only handle limited shapes for now...
1569 const Type *OldNodeTy = Allocs[i]->getType();
1570 vector<const Type*> PoolTypes;
1572 // Pool type is the first element of the pool descriptor type...
1573 PoolTypes.push_back(getPoolType(PoolDescs[Allocs[i]].NewType));
1575 unsigned NumPointers = countPointerTypes(OldNodeTy);
1576 while (NumPointers--) // Add a different opaque type for each pointer
1577 PoolTypes.push_back(OpaqueType::get());
1579 assert(Allocs[i]->getNumLinks() == PoolTypes.size()-1 &&
1580 "Node should have same number of pointers as pool!");
1582 StructType *PoolType = StructType::get(PoolTypes);
1584 // Add a symbol table entry for the pooltype if possible...
1585 CurModule->addTypeName(OldName+".pool", PoolType);
1587 // Create the pool type, with opaque values for pointers...
1588 AbsPoolTyMap.insert(std::make_pair(Allocs[i], PoolType));
1589 #ifdef DEBUG_CREATE_POOLS
1590 cerr << "POOL TY: " << AbsPoolTyMap.find(Allocs[i])->second.get() << "\n";
1594 // Now that we have types for all of the pool types, link them all together.
1595 for (unsigned i = 0, e = Allocs.size(); i != e; ++i) {
1596 PATypeHolder &PoolTyH = AbsPoolTyMap.find(Allocs[i])->second;
1598 // Resolve all of the outgoing pointer types of this pool node...
1599 for (unsigned p = 0, pe = Allocs[i]->getNumLinks(); p != pe; ++p) {
1600 PointerValSet &PVS = Allocs[i]->getLink(p);
1601 assert(!PVS.empty() && "Outgoing edge is empty, field unused, can"
1602 " probably just leave the type opaque or something dumb.");
1604 for (Out = 0; AbsPoolTyMap.count(PVS[Out].Node) == 0; ++Out)
1605 assert(Out != PVS.size() && "No edge to an outgoing allocation node!?");
1607 assert(PVS[Out].Index == 0 && "Subindexing not implemented yet!");
1609 // The actual struct type could change each time through the loop, so it's
1610 // NOT loop invariant.
1611 const StructType *PoolTy = cast<StructType>(PoolTyH.get());
1613 // Get the opaque type...
1614 DerivedType *ElTy = (DerivedType*)(PoolTy->getElementTypes()[p+1].get());
1616 #ifdef DEBUG_CREATE_POOLS
1617 cerr << "Refining " << ElTy << " of " << PoolTy << " to "
1618 << AbsPoolTyMap.find(PVS[Out].Node)->second.get() << "\n";
1621 const Type *RefPoolTy = AbsPoolTyMap.find(PVS[Out].Node)->second.get();
1622 ElTy->refineAbstractTypeTo(PointerType::get(RefPoolTy));
1624 #ifdef DEBUG_CREATE_POOLS
1625 cerr << "Result pool type is: " << PoolTyH.get() << "\n";
1630 // Create the code that goes in the entry and exit nodes for the function...
1631 vector<Instruction*> EntryNodeInsts;
1632 for (unsigned i = 0, e = Allocs.size(); i != e; ++i) {
1633 PoolInfo &PI = PoolDescs[Allocs[i]];
1635 // Fill in the pool type for this pool...
1636 PI.PoolType = AbsPoolTyMap.find(Allocs[i])->second.get();
1637 assert(!PI.PoolType->isAbstract() &&
1638 "Pool type should not be abstract anymore!");
1640 // Add an allocation and a free for each pool...
1641 AllocaInst *PoolAlloc
1642 = new AllocaInst(PointerType::get(PI.PoolType), 0,
1643 CurModule->getTypeName(PI.PoolType));
1644 PI.Handle = PoolAlloc;
1645 EntryNodeInsts.push_back(PoolAlloc);
1646 AllocationInst *AI = Allocs[i]->getAllocation();
1648 // Initialize the pool. We need to know how big each allocation is. For
1649 // our purposes here, we assume we are allocating a scalar, or array of
1652 unsigned ElSize = TargetData.getTypeSize(PI.NewType);
1654 vector<Value*> Args;
1655 Args.push_back(ConstantUInt::get(Type::UIntTy, ElSize));
1656 Args.push_back(PoolAlloc); // Pool to initialize
1657 EntryNodeInsts.push_back(new CallInst(PoolInit, Args));
1659 // Add code to destroy the pool in all of the exit nodes of the function...
1661 Args.push_back(PoolAlloc); // Pool to initialize
1663 for (unsigned EN = 0, ENE = ReturnNodes.size(); EN != ENE; ++EN) {
1664 Instruction *Destroy = new CallInst(PoolDestroy, Args);
1666 // Insert it before the return instruction...
1667 BasicBlock *RetNode = ReturnNodes[EN];
1668 RetNode->getInstList().insert(RetNode->end()--, Destroy);
1672 // Now that all of the pool descriptors have been created, link them together
1673 // so that called functions can get links as neccesary...
1675 for (unsigned i = 0, e = Allocs.size(); i != e; ++i) {
1676 PoolInfo &PI = PoolDescs[Allocs[i]];
1678 // For every pointer in the data structure, initialize a link that
1679 // indicates which pool to access...
1681 vector<Value*> Indices(2);
1682 Indices[0] = ConstantUInt::get(Type::UIntTy, 0);
1683 for (unsigned l = 0, le = PI.Node->getNumLinks(); l != le; ++l)
1684 // Only store an entry for the field if the field is used!
1685 if (!PI.Node->getLink(l).empty()) {
1686 assert(PI.Node->getLink(l).size() == 1 && "Should have only one link!");
1687 PointerVal PV = PI.Node->getLink(l)[0];
1688 assert(PV.Index == 0 && "Subindexing not supported yet!");
1689 PoolInfo &LinkedPool = PoolDescs[PV.Node];
1690 Indices[1] = ConstantUInt::get(Type::UByteTy, 1+l);
1692 EntryNodeInsts.push_back(new StoreInst(LinkedPool.Handle, PI.Handle,
1697 // Insert the entry node code into the entry block...
1698 F->getEntryNode().getInstList().insert(++F->getEntryNode().begin(),
1699 EntryNodeInsts.begin(),
1700 EntryNodeInsts.end());
1704 // addPoolPrototypes - Add prototypes for the pool functions to the specified
1705 // module and update the Pool* instance variables to point to them.
1707 void PoolAllocate::addPoolPrototypes(Module &M) {
1708 // Get poolinit function...
1709 vector<const Type*> Args;
1710 Args.push_back(Type::UIntTy); // Num bytes per element
1711 FunctionType *PoolInitTy = FunctionType::get(Type::VoidTy, Args, true);
1712 PoolInit = M.getOrInsertFunction("poolinit", PoolInitTy);
1714 // Get pooldestroy function...
1715 Args.pop_back(); // Only takes a pool...
1716 FunctionType *PoolDestroyTy = FunctionType::get(Type::VoidTy, Args, true);
1717 PoolDestroy = M.getOrInsertFunction("pooldestroy", PoolDestroyTy);
1719 // Get the poolalloc function...
1720 FunctionType *PoolAllocTy = FunctionType::get(POINTERTYPE, Args, true);
1721 PoolAlloc = M.getOrInsertFunction("poolalloc", PoolAllocTy);
1723 // Get the poolfree function...
1724 Args.push_back(POINTERTYPE); // Pointer to free
1725 FunctionType *PoolFreeTy = FunctionType::get(Type::VoidTy, Args, true);
1726 PoolFree = M.getOrInsertFunction("poolfree", PoolFreeTy);
1728 Args[0] = Type::UIntTy; // Number of slots to allocate
1729 FunctionType *PoolAllocArrayTy = FunctionType::get(POINTERTYPE, Args, true);
1730 PoolAllocArray = M.getOrInsertFunction("poolallocarray", PoolAllocArrayTy);
1734 bool PoolAllocate::run(Module &M) {
1735 addPoolPrototypes(M);
1738 DS = &getAnalysis<DataStructure>();
1739 bool Changed = false;
1741 for (Module::iterator I = M.begin(); I != M.end(); ++I)
1742 if (!I->isExternal()) {
1743 Changed |= processFunction(I);
1745 cerr << "Only processing one function\n";
1756 // createPoolAllocatePass - Global function to access the functionality of this
1759 Pass *createPoolAllocatePass() {
1760 assert(0 && "Pool allocator disabled!");
1761 //return new PoolAllocate();