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.
6 //===----------------------------------------------------------------------===//
8 #define DEBUG_TYPE "PoolAllocation"
9 #include "llvm/Transforms/PoolAllocate.h"
10 #include "llvm/Transforms/Utils/Cloning.h"
11 #include "llvm/Analysis/DataStructure.h"
12 #include "llvm/Analysis/DSGraph.h"
13 #include "llvm/Module.h"
14 #include "llvm/DerivedTypes.h"
15 #include "llvm/Constants.h"
16 #include "llvm/Instructions.h"
17 #include "llvm/Target/TargetData.h"
18 #include "llvm/Support/InstVisitor.h"
19 #include "Support/Debug.h"
20 #include "Support/VectorExtras.h"
24 const Type *VoidPtrTy = PointerType::get(Type::SByteTy);
26 // The type to allocate for a pool descriptor: { sbyte*, uint, uint }
27 // void *Data (the data)
28 // unsigned NodeSize (size of an allocated node)
29 // unsigned FreeablePool (are slabs in the pool freeable upon calls to
31 const Type *PoolDescType =
32 StructType::get(make_vector<const Type*>(VoidPtrTy, Type::UIntTy,
35 const PointerType *PoolDescPtr = PointerType::get(PoolDescType);
37 RegisterOpt<PoolAllocate>
38 X("poolalloc", "Pool allocate disjoint data structures");
41 void PoolAllocate::getAnalysisUsage(AnalysisUsage &AU) const {
42 AU.addRequired<BUDataStructures>();
43 AU.addRequired<TDDataStructures>();
44 AU.addRequired<TargetData>();
47 // Prints out the functions mapped to the leader of the equivalence class they
49 void PoolAllocate::printFuncECs() {
50 std::map<Function*, Function*> &leaderMap = FuncECs.getLeaderMap();
51 std::cerr << "Indirect Function Map \n";
52 for (std::map<Function*, Function*>::iterator LI = leaderMap.begin(),
53 LE = leaderMap.end(); LI != LE; ++LI) {
54 std::cerr << LI->first->getName() << ": leader is "
55 << LI->second->getName() << "\n";
59 static void printNTOMap(std::map<Value*, const Value*> &NTOM) {
60 std::cerr << "NTOM MAP\n";
61 for (std::map<Value*, const Value *>::iterator I = NTOM.begin(),
62 E = NTOM.end(); I != E; ++I) {
63 if (!isa<Function>(I->first) && !isa<BasicBlock>(I->first))
64 std::cerr << *I->first << " to " << *I->second << "\n";
68 void PoolAllocate::buildIndirectFunctionSets(Module &M) {
69 // Iterate over the module looking for indirect calls to functions
71 // Get top down DSGraph for the functions
72 TDDS = &getAnalysis<TDDataStructures>();
74 for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
76 DEBUG(std::cerr << "Processing indirect calls function:" << MI->getName() << "\n");
81 DSGraph &TDG = TDDS->getDSGraph(*MI);
83 std::vector<DSCallSite> callSites = TDG.getFunctionCalls();
85 // For each call site in the function
86 // All the functions that can be called at the call site are put in the
87 // same equivalence class.
88 for (std::vector<DSCallSite>::iterator CSI = callSites.begin(),
89 CSE = callSites.end(); CSI != CSE ; ++CSI) {
90 if (CSI->isIndirectCall()) {
91 DSNode *DSN = CSI->getCalleeNode();
92 if (DSN->isIncomplete())
93 std::cerr << "Incomplete node " << CSI->getCallInst();
94 // assert(DSN->isGlobalNode());
95 const std::vector<GlobalValue*> &Callees = DSN->getGlobals();
96 if (Callees.size() > 0) {
97 Function *firstCalledF = dyn_cast<Function>(*Callees.begin());
98 FuncECs.addElement(firstCalledF);
99 CallInstTargets.insert(std::pair<CallInst*,Function*>
100 (&CSI->getCallInst(),
102 if (Callees.size() > 1) {
103 for (std::vector<GlobalValue*>::const_iterator CalleesI =
104 Callees.begin()+1, CalleesE = Callees.end();
105 CalleesI != CalleesE; ++CalleesI) {
106 Function *calledF = dyn_cast<Function>(*CalleesI);
107 FuncECs.unionSetsWith(firstCalledF, calledF);
108 CallInstTargets.insert(std::pair<CallInst*,Function*>
109 (&CSI->getCallInst(), calledF));
113 std::cerr << "No targets " << CSI->getCallInst();
119 // Print the equivalence classes
120 DEBUG(printFuncECs());
123 bool PoolAllocate::run(Module &M) {
124 if (M.begin() == M.end()) return false;
128 BU = &getAnalysis<BUDataStructures>();
130 buildIndirectFunctionSets(M);
132 std::map<Function*, Function*> FuncMap;
134 // Loop over the functions in the original program finding the pool desc.
135 // arguments necessary for each function that is indirectly callable.
136 // For each equivalence class, make a list of pool arguments and update
137 // the PoolArgFirst and PoolArgLast values for each function.
138 Module::iterator LastOrigFunction = --M.end();
139 for (Module::iterator I = M.begin(); ; ++I) {
140 if (!I->isExternal())
141 FindFunctionPoolArgs(*I);
142 if (I == LastOrigFunction) break;
145 // Now clone a function using the pool arg list obtained in the previous
146 // pass over the modules.
147 // Loop over only the function initially in the program, don't traverse newly
148 // added ones. If the function uses memory, make its clone.
149 for (Module::iterator I = M.begin(); ; ++I) {
150 if (!I->isExternal())
151 if (Function *R = MakeFunctionClone(*I))
153 if (I == LastOrigFunction) break;
158 // Now that all call targets are available, rewrite the function bodies of the
160 for (Module::iterator I = M.begin(); I != LastOrigFunction; ++I)
161 if (!I->isExternal()) {
162 std::map<Function*, Function*>::iterator FI = FuncMap.find(I);
163 ProcessFunctionBody(*I, FI != FuncMap.end() ? *FI->second : *I);
167 std::cerr << "Pool Allocation successful! However all data structures may not be pool allocated\n";
173 // AddPoolPrototypes - Add prototypes for the pool functions to the specified
174 // module and update the Pool* instance variables to point to them.
176 void PoolAllocate::AddPoolPrototypes() {
177 CurModule->addTypeName("PoolDescriptor", PoolDescType);
179 // Get poolinit function...
180 FunctionType *PoolInitTy =
181 FunctionType::get(Type::VoidTy,
182 make_vector<const Type*>(PoolDescPtr, Type::UIntTy, 0),
184 PoolInit = CurModule->getOrInsertFunction("poolinit", PoolInitTy);
186 // Get pooldestroy function...
187 std::vector<const Type*> PDArgs(1, PoolDescPtr);
188 FunctionType *PoolDestroyTy =
189 FunctionType::get(Type::VoidTy, PDArgs, false);
190 PoolDestroy = CurModule->getOrInsertFunction("pooldestroy", PoolDestroyTy);
192 // Get the poolalloc function...
193 FunctionType *PoolAllocTy = FunctionType::get(VoidPtrTy, PDArgs, false);
194 PoolAlloc = CurModule->getOrInsertFunction("poolalloc", PoolAllocTy);
196 // Get the poolfree function...
197 PDArgs.push_back(VoidPtrTy); // Pointer to free
198 FunctionType *PoolFreeTy = FunctionType::get(Type::VoidTy, PDArgs, false);
199 PoolFree = CurModule->getOrInsertFunction("poolfree", PoolFreeTy);
201 // The poolallocarray function
202 FunctionType *PoolAllocArrayTy =
203 FunctionType::get(VoidPtrTy,
204 make_vector<const Type*>(PoolDescPtr, Type::UIntTy, 0),
206 PoolAllocArray = CurModule->getOrInsertFunction("poolallocarray",
211 // Inline the DSGraphs of functions corresponding to the potential targets at
212 // indirect call sites into the DS Graph of the callee.
213 // This is required to know what pools to create/pass at the call site in the
216 void PoolAllocate::InlineIndirectCalls(Function &F, DSGraph &G,
217 hash_set<Function*> &visited) {
218 std::vector<DSCallSite> callSites = G.getFunctionCalls();
222 // For each indirect call site in the function, inline all the potential
224 for (std::vector<DSCallSite>::iterator CSI = callSites.begin(),
225 CSE = callSites.end(); CSI != CSE; ++CSI) {
226 if (CSI->isIndirectCall()) {
227 CallInst &CI = CSI->getCallInst();
228 std::pair<std::multimap<CallInst*, Function*>::iterator,
229 std::multimap<CallInst*, Function*>::iterator> Targets =
230 CallInstTargets.equal_range(&CI);
231 for (std::multimap<CallInst*, Function*>::iterator TFI = Targets.first,
232 TFE = Targets.second; TFI != TFE; ++TFI) {
233 DSGraph &TargetG = BU->getDSGraph(*TFI->second);
234 // Call the function recursively if the callee is not yet inlined
235 // and if it hasn't been visited in this sequence of calls
236 // The latter is dependent on the fact that the graphs of all functions
237 // in an SCC are actually the same
238 if (InlinedFuncs.find(TFI->second) == InlinedFuncs.end() &&
239 visited.find(TFI->second) == visited.end()) {
240 InlineIndirectCalls(*TFI->second, TargetG, visited);
242 G.mergeInGraph(*CSI, *TFI->second, TargetG, DSGraph::KeepModRefBits |
243 DSGraph::KeepAllocaBit | DSGraph::DontCloneCallNodes |
244 DSGraph::DontCloneAuxCallNodes);
249 // Mark this function as one whose graph is inlined with its indirect
250 // function targets' DS Graphs. This ensures that every function is inlined
252 InlinedFuncs.insert(&F);
255 void PoolAllocate::FindFunctionPoolArgs(Function &F) {
257 DSGraph &G = BU->getDSGraph(F);
259 // Inline the potential targets of indirect calls
260 hash_set<Function*> visitedFuncs;
261 InlineIndirectCalls(F, G, visitedFuncs);
263 // The DSGraph is merged with the globals graph.
264 G.mergeInGlobalsGraph();
266 // The nodes reachable from globals need to be recognized as potential
267 // arguments. This is required because, upon merging in the globals graph,
268 // the nodes pointed to by globals that are not live are not marked
270 hash_set<DSNode*> NodesFromGlobals;
271 for (DSGraph::ScalarMapTy::iterator I = G.getScalarMap().begin(),
272 E = G.getScalarMap().end(); I != E; ++I)
273 if (isa<GlobalValue>(I->first)) { // Found a global
274 DSNodeHandle &GH = I->second;
275 GH.getNode()->markReachableNodes(NodesFromGlobals);
278 // At this point the DS Graphs have been modified in place including
279 // information about globals as well as indirect calls, making it useful
280 // for pool allocation
281 std::vector<DSNode*> &Nodes = G.getNodes();
282 if (Nodes.empty()) return ; // No memory activity, nothing is required
284 FuncInfo &FI = FunctionInfo[&F]; // Create a new entry for F
288 // Initialize the PoolArgFirst and PoolArgLast for the function depending
289 // on whether there have been other functions in the equivalence class
290 // that have pool arguments so far in the analysis.
291 if (!FuncECs.findClass(&F)) {
292 FI.PoolArgFirst = FI.PoolArgLast = 0;
294 if (EqClass2LastPoolArg.find(FuncECs.findClass(&F)) !=
295 EqClass2LastPoolArg.end())
296 FI.PoolArgFirst = FI.PoolArgLast =
297 EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1;
299 FI.PoolArgFirst = FI.PoolArgLast = 0;
302 // Find DataStructure nodes which are allocated in pools non-local to the
303 // current function. This set will contain all of the DSNodes which require
304 // pools to be passed in from outside of the function.
305 hash_set<DSNode*> &MarkedNodes = FI.MarkedNodes;
307 // Mark globals and incomplete nodes as live... (this handles arguments)
308 if (F.getName() != "main")
309 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
310 if (Nodes[i]->isGlobalNode() && !Nodes[i]->isIncomplete())
311 DEBUG(std::cerr << "Global node is not Incomplete\n");
312 if ((Nodes[i]->isIncomplete() || Nodes[i]->isGlobalNode() ||
313 NodesFromGlobals.count(Nodes[i])) && Nodes[i]->isHeapNode())
314 Nodes[i]->markReachableNodes(MarkedNodes);
317 // Marked the returned node as alive...
318 if (DSNode *RetNode = G.getReturnNodeFor(F).getNode())
319 if (RetNode->isHeapNode())
320 RetNode->markReachableNodes(MarkedNodes);
322 if (MarkedNodes.empty()) // We don't need to clone the function if there
323 return; // are no incoming arguments to be added.
325 // Erase any marked node that is not a heap node
327 for (hash_set<DSNode*>::iterator I = MarkedNodes.begin(),
328 E = MarkedNodes.end(); I != E; ) {
329 // erase invalidates hash_set iterators if the iterator points to the
330 // element being erased
331 if (!(*I)->isHeapNode())
332 MarkedNodes.erase(I++);
337 FI.PoolArgLast += MarkedNodes.size();
340 if (FuncECs.findClass(&F)) {
341 // Update the equivalence class last pool argument information
342 // only if there actually were pool arguments to the function.
343 // Also, there is no entry for the Eq. class in EqClass2LastPoolArg
344 // if there are no functions in the equivalence class with pool arguments.
345 if (FI.PoolArgLast != FI.PoolArgFirst)
346 EqClass2LastPoolArg[FuncECs.findClass(&F)] = FI.PoolArgLast - 1;
351 // MakeFunctionClone - If the specified function needs to be modified for pool
352 // allocation support, make a clone of it, adding additional arguments as
353 // neccesary, and return it. If not, just return null.
355 Function *PoolAllocate::MakeFunctionClone(Function &F) {
357 DSGraph &G = BU->getDSGraph(F);
359 std::vector<DSNode*> &Nodes = G.getNodes();
363 FuncInfo &FI = FunctionInfo[&F];
365 hash_set<DSNode*> &MarkedNodes = FI.MarkedNodes;
367 if (!FuncECs.findClass(&F)) {
368 // Not in any equivalence class
369 if (MarkedNodes.empty())
372 // No need to clone if there are no pool arguments in any function in the
374 if (!EqClass2LastPoolArg.count(FuncECs.findClass(&F)))
378 // Figure out what the arguments are to be for the new version of the function
379 const FunctionType *OldFuncTy = F.getFunctionType();
380 std::vector<const Type*> ArgTys;
381 if (!FuncECs.findClass(&F)) {
382 ArgTys.reserve(OldFuncTy->getParamTypes().size() + MarkedNodes.size());
383 FI.ArgNodes.reserve(MarkedNodes.size());
384 for (hash_set<DSNode*>::iterator I = MarkedNodes.begin(),
385 E = MarkedNodes.end(); I != E; ++I) {
386 ArgTys.push_back(PoolDescPtr); // Add the appropriate # of pool descs
387 FI.ArgNodes.push_back(*I);
389 if (FI.ArgNodes.empty()) return 0; // No nodes to be pool allocated!
393 // This function is a member of an equivalence class and needs to be cloned
394 ArgTys.reserve(OldFuncTy->getParamTypes().size() +
395 EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1);
396 FI.ArgNodes.reserve(EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1);
398 for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i) {
399 ArgTys.push_back(PoolDescPtr); // Add the appropriate # of pool
403 for (hash_set<DSNode*>::iterator I = MarkedNodes.begin(),
404 E = MarkedNodes.end(); I != E; ++I) {
405 FI.ArgNodes.push_back(*I);
408 assert ((FI.ArgNodes.size() == (unsigned) (FI.PoolArgLast -
410 "Number of ArgNodes equal to the number of pool arguments used by this function");
412 if (FI.ArgNodes.empty()) return 0;
416 ArgTys.insert(ArgTys.end(), OldFuncTy->getParamTypes().begin(),
417 OldFuncTy->getParamTypes().end());
420 // Create the new function prototype
421 FunctionType *FuncTy = FunctionType::get(OldFuncTy->getReturnType(), ArgTys,
422 OldFuncTy->isVarArg());
423 // Create the new function...
424 Function *New = new Function(FuncTy, GlobalValue::InternalLinkage,
425 F.getName(), F.getParent());
427 // Set the rest of the new arguments names to be PDa<n> and add entries to the
428 // pool descriptors map
429 std::map<DSNode*, Value*> &PoolDescriptors = FI.PoolDescriptors;
430 Function::aiterator NI = New->abegin();
432 if (FuncECs.findClass(&F)) {
433 // If the function belongs to an equivalence class
434 for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i,
439 if (FI.PoolArgFirst > 0)
440 for (int i = 0; i < FI.PoolArgFirst; ++NI, ++i)
443 for (unsigned i = 0, e = FI.ArgNodes.size(); i != e; ++i, ++NI)
444 PoolDescriptors.insert(std::make_pair(FI.ArgNodes[i], NI));
447 if (EqClass2LastPoolArg.count(FuncECs.findClass(&F)))
448 for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i, ++NI)
451 // If the function does not belong to an equivalence class
452 if (FI.ArgNodes.size())
453 for (unsigned i = 0, e = FI.ArgNodes.size(); i != e; ++i, ++NI) {
454 NI->setName("PDa"); // Add pd entry
455 PoolDescriptors.insert(std::make_pair(FI.ArgNodes[i], NI));
458 if (FI.ArgNodes.size())
459 for (unsigned i = 0; i < FI.ArgNodes.size(); ++NI, ++i)
463 // Map the existing arguments of the old function to the corresponding
464 // arguments of the new function.
465 std::map<const Value*, Value*> ValueMap;
466 if (NI != New->aend())
467 for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I, ++NI) {
469 NI->setName(I->getName());
472 // Populate the value map with all of the globals in the program.
473 // FIXME: This should be unneccesary!
474 Module &M = *F.getParent();
475 for (Module::iterator I = M.begin(), E=M.end(); I!=E; ++I) ValueMap[I] = I;
476 for (Module::giterator I = M.gbegin(), E=M.gend(); I!=E; ++I) ValueMap[I] = I;
478 // Perform the cloning.
479 std::vector<ReturnInst*> Returns;
480 CloneFunctionInto(New, &F, ValueMap, Returns);
482 // Invert the ValueMap into the NewToOldValueMap
483 std::map<Value*, const Value*> &NewToOldValueMap = FI.NewToOldValueMap;
484 for (std::map<const Value*, Value*>::iterator I = ValueMap.begin(),
485 E = ValueMap.end(); I != E; ++I)
486 NewToOldValueMap.insert(std::make_pair(I->second, I->first));
488 return FI.Clone = New;
492 // processFunction - Pool allocate any data structures which are contained in
493 // the specified function...
495 void PoolAllocate::ProcessFunctionBody(Function &F, Function &NewF) {
496 DSGraph &G = BU->getDSGraph(F);
498 std::vector<DSNode*> &Nodes = G.getNodes();
499 if (Nodes.empty()) return; // Quick exit if nothing to do...
501 FuncInfo &FI = FunctionInfo[&F]; // Get FuncInfo for F
502 hash_set<DSNode*> &MarkedNodes = FI.MarkedNodes;
504 DEBUG(std::cerr << "[" << F.getName() << "] Pool Allocate: ");
506 // Loop over all of the nodes which are non-escaping, adding pool-allocatable
507 // ones to the NodesToPA vector.
508 std::vector<DSNode*> NodesToPA;
509 for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
510 if (Nodes[i]->isHeapNode() && // Pick nodes with heap elems
511 !MarkedNodes.count(Nodes[i])) // Can't be marked
512 NodesToPA.push_back(Nodes[i]);
514 DEBUG(std::cerr << NodesToPA.size() << " nodes to pool allocate\n");
515 if (!NodesToPA.empty()) {
516 // Create pool construction/destruction code
517 std::map<DSNode*, Value*> &PoolDescriptors = FI.PoolDescriptors;
518 CreatePools(NewF, NodesToPA, PoolDescriptors);
521 // Transform the body of the function now...
522 TransformFunctionBody(NewF, F, G, FI);
526 // CreatePools - This creates the pool initialization and destruction code for
527 // the DSNodes specified by the NodesToPA list. This adds an entry to the
528 // PoolDescriptors map for each DSNode.
530 void PoolAllocate::CreatePools(Function &F,
531 const std::vector<DSNode*> &NodesToPA,
532 std::map<DSNode*, Value*> &PoolDescriptors) {
533 // Find all of the return nodes in the CFG...
534 std::vector<BasicBlock*> ReturnNodes;
535 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
536 if (isa<ReturnInst>(I->getTerminator()))
537 ReturnNodes.push_back(I);
539 TargetData &TD = getAnalysis<TargetData>();
541 // Loop over all of the pools, inserting code into the entry block of the
542 // function for the initialization and code in the exit blocks for
545 Instruction *InsertPoint = F.front().begin();
546 for (unsigned i = 0, e = NodesToPA.size(); i != e; ++i) {
547 DSNode *Node = NodesToPA[i];
549 // Create a new alloca instruction for the pool...
550 Value *AI = new AllocaInst(PoolDescType, 0, "PD", InsertPoint);
554 // Void types in DS graph are never used
555 if (Node->getType() != Type::VoidTy)
556 ElSize = ConstantUInt::get(Type::UIntTy, TD.getTypeSize(Node->getType()));
558 DEBUG(std::cerr << "Potential node collapsing in " << F.getName()
559 << ". All Data Structures may not be pool allocated\n");
560 ElSize = ConstantUInt::get(Type::UIntTy, 0);
563 // Insert the call to initialize the pool...
564 new CallInst(PoolInit, make_vector(AI, ElSize, 0), "", InsertPoint);
566 // Update the PoolDescriptors map
567 PoolDescriptors.insert(std::make_pair(Node, AI));
569 // Insert a call to pool destroy before each return inst in the function
570 for (unsigned r = 0, e = ReturnNodes.size(); r != e; ++r)
571 new CallInst(PoolDestroy, make_vector(AI, 0), "",
572 ReturnNodes[r]->getTerminator());
578 /// FuncTransform - This class implements transformation required of pool
579 /// allocated functions.
580 struct FuncTransform : public InstVisitor<FuncTransform> {
581 PoolAllocate &PAInfo;
582 DSGraph &G; // The Bottom-up DS Graph
583 DSGraph &TDG; // The Top-down DS Graph
586 FuncTransform(PoolAllocate &P, DSGraph &g, DSGraph &tdg, FuncInfo &fi)
587 : PAInfo(P), G(g), TDG(tdg), FI(fi) {
590 void visitMallocInst(MallocInst &MI);
591 void visitFreeInst(FreeInst &FI);
592 void visitCallInst(CallInst &CI);
594 // The following instructions are never modified by pool allocation
595 void visitBranchInst(BranchInst &I) { }
596 void visitBinaryOperator(Instruction &I) { }
597 void visitShiftInst (ShiftInst &I) { }
598 void visitSwitchInst (SwitchInst &I) { }
599 void visitCastInst (CastInst &I) { }
600 void visitAllocaInst(AllocaInst &I) { }
601 void visitLoadInst(LoadInst &I) { }
602 void visitGetElementPtrInst (GetElementPtrInst &I) { }
604 void visitReturnInst(ReturnInst &I);
605 void visitStoreInst (StoreInst &I);
606 void visitPHINode(PHINode &I);
608 void visitInstruction(Instruction &I) {
609 std::cerr << "PoolAllocate does not recognize this instruction\n";
614 DSNodeHandle& getDSNodeHFor(Value *V) {
615 // if (isa<Constant>(V))
616 // return DSNodeHandle();
618 if (!FI.NewToOldValueMap.empty()) {
619 // If the NewToOldValueMap is in effect, use it.
620 std::map<Value*,const Value*>::iterator I = FI.NewToOldValueMap.find(V);
621 if (I != FI.NewToOldValueMap.end())
622 V = (Value*)I->second;
625 return G.getScalarMap()[V];
628 DSNodeHandle& getTDDSNodeHFor(Value *V) {
629 if (!FI.NewToOldValueMap.empty()) {
630 // If the NewToOldValueMap is in effect, use it.
631 std::map<Value*,const Value*>::iterator I = FI.NewToOldValueMap.find(V);
632 if (I != FI.NewToOldValueMap.end())
633 V = (Value*)I->second;
636 return TDG.getScalarMap()[V];
639 Value *getPoolHandle(Value *V) {
640 DSNode *Node = getDSNodeHFor(V).getNode();
641 // Get the pool handle for this DSNode...
642 std::map<DSNode*, Value*>::iterator I = FI.PoolDescriptors.find(Node);
644 if (I != FI.PoolDescriptors.end()) {
645 // Check that the node pointed to by V in the TD DS graph is not
647 DSNode *TDNode = getTDDSNodeHFor(V).getNode();
648 if (TDNode->getType() != Type::VoidTy)
651 PAInfo.CollapseFlag = 1;
660 bool isFuncPtr(Value *V);
662 Function* getFuncClass(Value *V);
664 Value* retCloneIfFunc(Value *V);
668 void PoolAllocate::TransformFunctionBody(Function &F, Function &OldF,
669 DSGraph &G, FuncInfo &FI) {
670 FuncTransform(*this, G, TDDS->getDSGraph(OldF), FI).visit(F);
673 // Returns true if V is a function pointer
674 bool FuncTransform::isFuncPtr(Value *V) {
675 if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
676 return isa<FunctionType>(PTy->getElementType());
680 // Given a function pointer, return the function eq. class if one exists
681 Function* FuncTransform::getFuncClass(Value *V) {
682 // Look at DSGraph and see if the set of of functions it could point to
683 // are pool allocated.
689 // if V is a constant
690 if (Function *theFunc = dyn_cast<Function>(V)) {
691 if (!PAInfo.FuncECs.findClass(theFunc))
692 // If this function does not belong to any equivalence class
694 if (PAInfo.EqClass2LastPoolArg.count(PAInfo.FuncECs.findClass(theFunc)))
695 return PAInfo.FuncECs.findClass(theFunc);
700 // if V is not a constant
701 DSNode *DSN = TDG.getNodeForValue(V).getNode();
705 const std::vector<GlobalValue*> &Callees = DSN->getGlobals();
706 if (Callees.size() > 0) {
707 Function *calledF = dyn_cast<Function>(*Callees.begin());
708 assert(PAInfo.FuncECs.findClass(calledF) && "should exist in some eq. class");
709 if (PAInfo.EqClass2LastPoolArg.count(PAInfo.FuncECs.findClass(calledF)))
710 return PAInfo.FuncECs.findClass(calledF);
716 // Returns the clone if V is a static function (not a pointer) and belongs
717 // to an equivalence class i.e. is pool allocated
718 Value* FuncTransform::retCloneIfFunc(Value *V) {
719 if (Function *fixedFunc = dyn_cast<Function>(V))
721 return PAInfo.getFuncInfo(*fixedFunc)->Clone;
726 void FuncTransform::visitReturnInst (ReturnInst &RI) {
727 if (RI.getNumOperands())
728 if (Value *clonedFunc = retCloneIfFunc(RI.getOperand(0))) {
729 // Cast the clone of RI.getOperand(0) to the non-pool-allocated type
730 CastInst *CastI = new CastInst(clonedFunc, RI.getOperand(0)->getType(),
732 // Insert return instruction that returns the casted value
733 ReturnInst *RetI = new ReturnInst(CastI, &RI);
735 // Remove original return instruction
736 RI.getParent()->getInstList().erase(&RI);
738 if (!FI.NewToOldValueMap.empty()) {
739 std::map<Value*,const Value*>::iterator II =
740 FI.NewToOldValueMap.find(&RI);
741 assert(II != FI.NewToOldValueMap.end() &&
742 "RI not found in clone?");
743 FI.NewToOldValueMap.insert(std::make_pair(RetI, II->second));
744 FI.NewToOldValueMap.erase(II);
749 void FuncTransform::visitStoreInst (StoreInst &SI) {
750 // Check if a constant function is being stored
751 if (Value *clonedFunc = retCloneIfFunc(SI.getOperand(0))) {
752 CastInst *CastI = new CastInst(clonedFunc, SI.getOperand(0)->getType(),
754 StoreInst *StoreI = new StoreInst(CastI, SI.getOperand(1), &SI);
755 SI.getParent()->getInstList().erase(&SI);
757 // Update the NewToOldValueMap if this is a clone
758 if (!FI.NewToOldValueMap.empty()) {
759 std::map<Value*,const Value*>::iterator II =
760 FI.NewToOldValueMap.find(&SI);
761 assert(II != FI.NewToOldValueMap.end() &&
762 "SI not found in clone?");
763 FI.NewToOldValueMap.insert(std::make_pair(StoreI, II->second));
764 FI.NewToOldValueMap.erase(II);
769 void FuncTransform::visitPHINode(PHINode &PI) {
770 // If any of the operands of the PHI node is a constant function pointer
771 // that is cloned, the cast instruction has to be inserted at the end of the
772 // previous basic block
774 if (isFuncPtr(&PI)) {
775 PHINode *V = new PHINode(PI.getType(), PI.getName(), &PI);
776 for (unsigned i = 0 ; i < PI.getNumIncomingValues(); ++i) {
777 if (Value *clonedFunc = retCloneIfFunc(PI.getIncomingValue(i))) {
778 // Insert CastInst at the end of PI.getIncomingBlock(i)
779 BasicBlock::iterator BBI = --PI.getIncomingBlock(i)->end();
780 // BBI now points to the terminator instruction of the basic block.
781 CastInst *CastI = new CastInst(clonedFunc, PI.getType(), "tmp", BBI);
782 V->addIncoming(CastI, PI.getIncomingBlock(i));
784 V->addIncoming(PI.getIncomingValue(i), PI.getIncomingBlock(i));
788 PI.replaceAllUsesWith(V);
789 PI.getParent()->getInstList().erase(&PI);
791 DSGraph::ScalarMapTy &SM = G.getScalarMap();
792 DSGraph::ScalarMapTy::iterator PII = SM.find(&PI);
794 // Update Scalar map of DSGraph if this is one of the original functions
795 // Otherwise update the NewToOldValueMap
796 if (PII != SM.end()) {
797 SM.insert(std::make_pair(V, PII->second));
798 SM.erase(PII); // Destroy the PHINode
800 std::map<Value*,const Value*>::iterator II =
801 FI.NewToOldValueMap.find(&PI);
802 assert(II != FI.NewToOldValueMap.end() &&
803 "PhiI not found in clone?");
804 FI.NewToOldValueMap.insert(std::make_pair(V, II->second));
805 FI.NewToOldValueMap.erase(II);
810 void FuncTransform::visitMallocInst(MallocInst &MI) {
811 // Get the pool handle for the node that this contributes to...
812 Value *PH = getPoolHandle(&MI);
814 // NB: PH is zero even if the node is collapsed
817 // Insert a call to poolalloc
819 if (MI.isArrayAllocation())
820 V = new CallInst(PAInfo.PoolAllocArray,
821 make_vector(PH, MI.getOperand(0), 0),
824 V = new CallInst(PAInfo.PoolAlloc, make_vector(PH, 0),
827 MI.setName(""); // Nuke MIs name
831 // Cast to the appropriate type if necessary
832 if (V->getType() != MI.getType()) {
833 Casted = new CastInst(V, MI.getType(), V->getName(), &MI);
836 // Update def-use info
837 MI.replaceAllUsesWith(Casted);
839 // Remove old malloc instruction
840 MI.getParent()->getInstList().erase(&MI);
842 DSGraph::ScalarMapTy &SM = G.getScalarMap();
843 DSGraph::ScalarMapTy::iterator MII = SM.find(&MI);
845 // If we are modifying the original function, update the DSGraph...
846 if (MII != SM.end()) {
847 // V and Casted now point to whatever the original malloc did...
848 SM.insert(std::make_pair(V, MII->second));
850 SM.insert(std::make_pair(Casted, MII->second));
851 SM.erase(MII); // The malloc is now destroyed
852 } else { // Otherwise, update the NewToOldValueMap
853 std::map<Value*,const Value*>::iterator MII =
854 FI.NewToOldValueMap.find(&MI);
855 assert(MII != FI.NewToOldValueMap.end() && "MI not found in clone?");
856 FI.NewToOldValueMap.insert(std::make_pair(V, MII->second));
858 FI.NewToOldValueMap.insert(std::make_pair(Casted, MII->second));
859 FI.NewToOldValueMap.erase(MII);
863 void FuncTransform::visitFreeInst(FreeInst &FrI) {
864 Value *Arg = FrI.getOperand(0);
865 Value *PH = getPoolHandle(Arg); // Get the pool handle for this DSNode...
867 // Insert a cast and a call to poolfree...
869 if (Arg->getType() != PointerType::get(Type::SByteTy))
870 Casted = new CastInst(Arg, PointerType::get(Type::SByteTy),
871 Arg->getName()+".casted", &FrI);
873 CallInst *FreeI = new CallInst(PAInfo.PoolFree, make_vector(PH, Casted, 0),
875 // Delete the now obsolete free instruction...
876 FrI.getParent()->getInstList().erase(&FrI);
878 // Update the NewToOldValueMap if this is a clone
879 if (!FI.NewToOldValueMap.empty()) {
880 std::map<Value*,const Value*>::iterator II =
881 FI.NewToOldValueMap.find(&FrI);
882 assert(II != FI.NewToOldValueMap.end() &&
883 "FrI not found in clone?");
884 FI.NewToOldValueMap.insert(std::make_pair(FreeI, II->second));
885 FI.NewToOldValueMap.erase(II);
889 static void CalcNodeMapping(DSNodeHandle& Caller, DSNodeHandle& Callee,
890 std::map<DSNode*, DSNode*> &NodeMapping) {
891 DSNode *CalleeNode = Callee.getNode();
892 DSNode *CallerNode = Caller.getNode();
894 unsigned CalleeOffset = Callee.getOffset();
895 unsigned CallerOffset = Caller.getOffset();
897 if (CalleeNode == 0) return;
899 // If callee has a node and caller doesn't, then a constant argument was
900 // passed by the caller
901 if (CallerNode == 0) {
902 NodeMapping.insert(NodeMapping.end(), std::make_pair(CalleeNode,
906 // Map the callee node to the caller node.
907 // NB: The callee node could be of a different type. Eg. if it points to the
908 // field of a struct that the caller points to
909 std::map<DSNode*, DSNode*>::iterator I = NodeMapping.find(CalleeNode);
910 if (I != NodeMapping.end()) { // Node already in map...
911 assert(I->second == CallerNode &&
912 "Node maps to different nodes on paths?");
914 NodeMapping.insert(I, std::make_pair(CalleeNode, CallerNode));
916 if (CalleeNode->getType() != CallerNode->getType() && CallerOffset == 0)
917 DEBUG(std::cerr << "NB: Mapping of nodes between different types\n");
919 // Recursively map the callee links to the caller links starting from the
920 // offset in the node into which they are mapped.
921 // Being a BU Graph, the callee ought to have smaller number of links unless
922 // there is collapsing in the caller
923 unsigned numCallerLinks = CallerNode->getNumLinks() - CallerOffset;
924 unsigned numCalleeLinks = CalleeNode->getNumLinks() - CalleeOffset;
926 if (numCallerLinks > 0) {
927 if (numCallerLinks < numCalleeLinks) {
928 DEBUG(std::cerr << "Potential node collapsing in caller\n");
929 for (unsigned i = 0, e = numCalleeLinks; i != e; ++i)
930 CalcNodeMapping(CallerNode->getLink(((i%numCallerLinks) << DS::PointerShift) + CallerOffset), CalleeNode->getLink((i << DS::PointerShift) + CalleeOffset), NodeMapping);
932 for (unsigned i = 0, e = numCalleeLinks; i != e; ++i)
933 CalcNodeMapping(CallerNode->getLink((i << DS::PointerShift) + CallerOffset), CalleeNode->getLink((i << DS::PointerShift) + CalleeOffset), NodeMapping);
935 } else if (numCalleeLinks > 0) {
937 "Caller has unexpanded node, due to indirect call perhaps!\n");
942 void FuncTransform::visitCallInst(CallInst &CI) {
943 Function *CF = CI.getCalledFunction();
945 // optimization for function pointers that are basically gotten from a cast
946 // with only one use and constant expressions with casts in them
948 if (CastInst* CastI = dyn_cast<CastInst>(CI.getCalledValue())) {
949 if (isa<Function>(CastI->getOperand(0)) &&
950 CastI->getOperand(0)->getType() == CastI->getType())
951 CF = dyn_cast<Function>(CastI->getOperand(0));
952 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(CI.getOperand(0))) {
953 if (CE->getOpcode() == Instruction::Cast) {
954 if (isa<ConstantPointerRef>(CE->getOperand(0)))
957 assert(0 && "Function pointer cast not handled as called function\n");
963 DSGraph &CallerG = G;
965 std::vector<Value*> Args;
966 if (!CF) { // Indirect call
967 DEBUG(std::cerr << " Handling call: " << CI);
969 std::map<unsigned, Value*> PoolArgs;
972 std::pair<std::multimap<CallInst*, Function*>::iterator,
973 std::multimap<CallInst*, Function*>::iterator> Targets =
974 PAInfo.CallInstTargets.equal_range(&CI);
975 for (std::multimap<CallInst*, Function*>::iterator TFI = Targets.first,
976 TFE = Targets.second; TFI != TFE; ++TFI) {
977 if (TFI == Targets.first) {
978 FuncClass = PAInfo.FuncECs.findClass(TFI->second);
979 // Nothing to transform if there are no pool arguments in this
980 // equivalence class of functions.
981 if (!PAInfo.EqClass2LastPoolArg.count(FuncClass))
985 FuncInfo *CFI = PAInfo.getFuncInfo(*TFI->second);
987 if (!CFI->ArgNodes.size()) continue; // Nothing to transform...
989 DSGraph &CG = PAInfo.getBUDataStructures().getDSGraph(*TFI->second);
990 std::map<DSNode*, DSNode*> NodeMapping;
992 Function::aiterator AI = TFI->second->abegin(), AE = TFI->second->aend();
994 for ( ; AI != AE; ++AI, ++OpNum) {
995 if (!isa<Constant>(CI.getOperand(OpNum)))
996 CalcNodeMapping(getDSNodeHFor(CI.getOperand(OpNum)),
997 CG.getScalarMap()[AI], NodeMapping);
999 assert(OpNum == CI.getNumOperands() && "Varargs calls not handled yet!");
1001 if (CI.getType() != Type::VoidTy)
1002 CalcNodeMapping(getDSNodeHFor(&CI),
1003 CG.getReturnNodeFor(*TFI->second), NodeMapping);
1005 // Map the nodes that are pointed to by globals.
1006 // For all globals map getDSNodeForGlobal(g)->CG.getDSNodeForGlobal(g)
1007 for (DSGraph::ScalarMapTy::iterator SMI = G.getScalarMap().begin(),
1008 SME = G.getScalarMap().end(); SMI != SME; ++SMI)
1009 if (isa<GlobalValue>(SMI->first)) {
1010 CalcNodeMapping(SMI->second,
1011 CG.getScalarMap()[SMI->first], NodeMapping);
1014 unsigned idx = CFI->PoolArgFirst;
1016 // The following loop determines the pool pointers corresponding to
1018 for (unsigned i = 0, e = CFI->ArgNodes.size(); i != e; ++i, ++idx) {
1019 if (NodeMapping.count(CFI->ArgNodes[i])) {
1020 assert(NodeMapping.count(CFI->ArgNodes[i]) && "Node not in mapping!");
1021 DSNode *LocalNode = NodeMapping.find(CFI->ArgNodes[i])->second;
1023 assert(FI.PoolDescriptors.count(LocalNode) &&
1024 "Node not pool allocated?");
1025 PoolArgs[idx] = FI.PoolDescriptors.find(LocalNode)->second;
1028 // LocalNode is null when a constant is passed in as a parameter
1029 PoolArgs[idx] = Constant::getNullValue(PoolDescPtr);
1031 PoolArgs[idx] = Constant::getNullValue(PoolDescPtr);
1036 // Push the pool arguments into Args.
1037 if (PAInfo.EqClass2LastPoolArg.count(FuncClass)) {
1038 for (int i = 0; i <= PAInfo.EqClass2LastPoolArg[FuncClass]; ++i) {
1039 if (PoolArgs.find(i) != PoolArgs.end())
1040 Args.push_back(PoolArgs[i]);
1042 Args.push_back(Constant::getNullValue(PoolDescPtr));
1045 assert(Args.size()== (unsigned) PAInfo.EqClass2LastPoolArg[FuncClass] + 1
1046 && "Call has same number of pool args as the called function");
1049 // Add the rest of the arguments (the original arguments of the function)...
1050 Args.insert(Args.end(), CI.op_begin()+1, CI.op_end());
1052 std::string Name = CI.getName();
1055 if (Args.size() > CI.getNumOperands() - 1) {
1056 // If there are any pool arguments
1058 new CastInst(CI.getOperand(0),
1059 PAInfo.getFuncInfo(*FuncClass)->Clone->getType(), "tmp",
1061 NewCall = new CallInst(CastI, Args, Name, &CI);
1063 NewCall = new CallInst(CI.getOperand(0), Args, Name, &CI);
1066 CI.replaceAllUsesWith(NewCall);
1067 DEBUG(std::cerr << " Result Call: " << *NewCall);
1069 if (CI.getType() != Type::VoidTy) {
1070 // If we are modifying the original function, update the DSGraph...
1071 DSGraph::ScalarMapTy &SM = G.getScalarMap();
1072 DSGraph::ScalarMapTy::iterator CII = SM.find(&CI);
1073 if (CII != SM.end()) {
1074 SM.insert(std::make_pair(NewCall, CII->second));
1075 SM.erase(CII); // Destroy the CallInst
1077 // Otherwise update the NewToOldValueMap with the new CI return value
1078 std::map<Value*,const Value*>::iterator CII =
1079 FI.NewToOldValueMap.find(&CI);
1080 assert(CII != FI.NewToOldValueMap.end() && "CI not found in clone?");
1081 FI.NewToOldValueMap.insert(std::make_pair(NewCall, CII->second));
1082 FI.NewToOldValueMap.erase(CII);
1084 } else if (!FI.NewToOldValueMap.empty()) {
1085 std::map<Value*,const Value*>::iterator II =
1086 FI.NewToOldValueMap.find(&CI);
1087 assert(II != FI.NewToOldValueMap.end() &&
1088 "CI not found in clone?");
1089 FI.NewToOldValueMap.insert(std::make_pair(NewCall, II->second));
1090 FI.NewToOldValueMap.erase(II);
1095 FuncInfo *CFI = PAInfo.getFuncInfo(*CF);
1097 if (CFI == 0 || CFI->Clone == 0) return; // Nothing to transform...
1099 DEBUG(std::cerr << " Handling call: " << CI);
1101 DSGraph &CG = PAInfo.getBUDataStructures().getDSGraph(*CF); // Callee graph
1103 // We need to figure out which local pool descriptors correspond to the pool
1104 // descriptor arguments passed into the function call. Calculate a mapping
1105 // from callee DSNodes to caller DSNodes. We construct a partial isomophism
1106 // between the graphs to figure out which pool descriptors need to be passed
1107 // in. The roots of this mapping is found from arguments and return values.
1109 std::map<DSNode*, DSNode*> NodeMapping;
1111 Function::aiterator AI = CF->abegin(), AE = CF->aend();
1113 for (; AI != AE; ++AI, ++OpNum) {
1114 Value *callOp = CI.getOperand(OpNum);
1115 if (!isa<Constant>(callOp))
1116 CalcNodeMapping(getDSNodeHFor(callOp), CG.getScalarMap()[AI],
1119 assert(OpNum == CI.getNumOperands() && "Varargs calls not handled yet!");
1121 // Map the return value as well...
1122 if (CI.getType() != Type::VoidTy)
1123 CalcNodeMapping(getDSNodeHFor(&CI), CG.getReturnNodeFor(*CF),
1126 // Map the nodes that are pointed to by globals.
1127 // For all globals map getDSNodeForGlobal(g)->CG.getDSNodeForGlobal(g)
1128 for (DSGraph::ScalarMapTy::iterator SMI = G.getScalarMap().begin(),
1129 SME = G.getScalarMap().end(); SMI != SME; ++SMI)
1130 if (isa<GlobalValue>(SMI->first)) {
1131 CalcNodeMapping(SMI->second,
1132 CG.getScalarMap()[SMI->first], NodeMapping);
1135 // Okay, now that we have established our mapping, we can figure out which
1136 // pool descriptors to pass in...
1138 // Add an argument for each pool which must be passed in...
1139 if (CFI->PoolArgFirst != 0) {
1140 for (int i = 0; i < CFI->PoolArgFirst; ++i)
1141 Args.push_back(Constant::getNullValue(PoolDescPtr));
1144 for (unsigned i = 0, e = CFI->ArgNodes.size(); i != e; ++i) {
1145 if (NodeMapping.count(CFI->ArgNodes[i])) {
1147 DSNode *LocalNode = NodeMapping.find(CFI->ArgNodes[i])->second;
1149 assert(FI.PoolDescriptors.count(LocalNode) &&
1150 "Node not pool allocated?");
1151 Args.push_back(FI.PoolDescriptors.find(LocalNode)->second);
1153 Args.push_back(Constant::getNullValue(PoolDescPtr));
1155 Args.push_back(Constant::getNullValue(PoolDescPtr));
1159 Function *FuncClass = PAInfo.FuncECs.findClass(CF);
1161 if (PAInfo.EqClass2LastPoolArg.count(FuncClass))
1162 for (int i = CFI->PoolArgLast;
1163 i <= PAInfo.EqClass2LastPoolArg[FuncClass]; ++i)
1164 Args.push_back(Constant::getNullValue(PoolDescPtr));
1166 // Add the rest of the arguments...
1167 Args.insert(Args.end(), CI.op_begin()+1, CI.op_end());
1169 std::string Name = CI.getName();
1171 std::map<Value*,const Value*>::iterator CNewII;
1173 Value *NewCall = new CallInst(CFI->Clone, Args, Name, &CI);
1175 CI.replaceAllUsesWith(NewCall);
1176 DEBUG(std::cerr << " Result Call: " << *NewCall);
1178 if (CI.getType() != Type::VoidTy) {
1179 // If we are modifying the original function, update the DSGraph...
1180 DSGraph::ScalarMapTy &SM = G.getScalarMap();
1181 DSGraph::ScalarMapTy::iterator CII = SM.find(&CI);
1182 if (CII != SM.end()) {
1183 SM.insert(std::make_pair(NewCall, CII->second));
1184 SM.erase(CII); // Destroy the CallInst
1186 // Otherwise update the NewToOldValueMap with the new CI return value
1187 std::map<Value*,const Value*>::iterator CNII =
1188 FI.NewToOldValueMap.find(&CI);
1189 assert(CNII != FI.NewToOldValueMap.end() && CNII->second &&
1190 "CI not found in clone?");
1191 FI.NewToOldValueMap.insert(std::make_pair(NewCall, CNII->second));
1192 FI.NewToOldValueMap.erase(CNII);
1194 } else if (!FI.NewToOldValueMap.empty()) {
1195 std::map<Value*,const Value*>::iterator II =
1196 FI.NewToOldValueMap.find(&CI);
1197 assert(II != FI.NewToOldValueMap.end() && "CI not found in clone?");
1198 FI.NewToOldValueMap.insert(std::make_pair(NewCall, II->second));
1199 FI.NewToOldValueMap.erase(II);
1203 CI.getParent()->getInstList().erase(&CI);