lib/Transforms/IPO/PoolAllocate.cpp

   1 //===-- PoolAllocate.cpp - Pool Allocation Pass ---------------------------===//
   2 //
   3 // This transform changes programs so that disjoint data structures are
   4 // allocated out of different pools of memory, increasing locality.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   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"
  21 using namespace PA;
  22
  23 namespace {
  24   const Type *VoidPtrTy = PointerType::get(Type::SByteTy);
  25
  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
  30   //                        poolfree?)
  31   const Type *PoolDescType =
  32   StructType::get(make_vector<const Type*>(VoidPtrTy, Type::UIntTy,
  33                                            Type::UIntTy, 0));
  34
  35   const PointerType *PoolDescPtr = PointerType::get(PoolDescType);
  36
  37   RegisterOpt<PoolAllocate>
  38   X("poolalloc", "Pool allocate disjoint data structures");
  39 }
  40
  41 void PoolAllocate::getAnalysisUsage(AnalysisUsage &AU) const {
  42   AU.addRequired<BUDataStructures>();
  43   AU.addRequired<TDDataStructures>();
  44   AU.addRequired<TargetData>();
  45 }
  46
  47 // Prints out the functions mapped to the leader of the equivalence class they
  48 // belong to.
  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";
  56   }
  57 }
  58
  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";
  65   }
  66 }
  67
  68 void PoolAllocate::buildIndirectFunctionSets(Module &M) {
  69   // Iterate over the module looking for indirect calls to functions
  70
  71   // Get top down DSGraph for the functions
  72   TDDS = &getAnalysis<TDDataStructures>();
  73
  74   for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
  75
  76     DEBUG(std::cerr << "Processing indirect calls function:" <<  MI->getName() << "\n");
  77
  78     if (MI->isExternal())
  79       continue;
  80
  81     DSGraph &TDG = TDDS->getDSGraph(*MI);
  82
  83     std::vector<DSCallSite> callSites = TDG.getFunctionCalls();
  84
  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(),
 101                                   firstCalledF));
 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));
 110             }
 111           }
 112         } else {
 113           std::cerr << "No targets " << CSI->getCallInst();
 114         }
 115       }
 116     }
 117   }
 118
 119   // Print the equivalence classes
 120   DEBUG(printFuncECs());
 121 }
 122
 123 bool PoolAllocate::run(Module &M) {
 124   if (M.begin() == M.end()) return false;
 125   CurModule = &M;
 126
 127   AddPoolPrototypes();
 128   BU = &getAnalysis<BUDataStructures>();
 129
 130   buildIndirectFunctionSets(M);
 131
 132   std::map<Function*, Function*> FuncMap;
 133
 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;
 143   }
 144
 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))
 152         FuncMap[I] = R;
 153     if (I == LastOrigFunction) break;
 154   }
 155
 156   ++LastOrigFunction;
 157
 158   // Now that all call targets are available, rewrite the function bodies of the
 159   // clones.
 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);
 164     }
 165
 166   if (CollapseFlag)
 167     std::cerr << "Pool Allocation successful! However all data structures may not be pool allocated\n";
 168
 169   return true;
 170 }
 171
 172
 173 // AddPoolPrototypes - Add prototypes for the pool functions to the specified
 174 // module and update the Pool* instance variables to point to them.
 175 //
 176 void PoolAllocate::AddPoolPrototypes() {
 177   CurModule->addTypeName("PoolDescriptor", PoolDescType);
 178
 179   // Get poolinit function...
 180   FunctionType *PoolInitTy =
 181     FunctionType::get(Type::VoidTy,
 182                       make_vector<const Type*>(PoolDescPtr, Type::UIntTy, 0),
 183                       false);
 184   PoolInit = CurModule->getOrInsertFunction("poolinit", PoolInitTy);
 185
 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);
 191
 192   // Get the poolalloc function...
 193   FunctionType *PoolAllocTy = FunctionType::get(VoidPtrTy, PDArgs, false);
 194   PoolAlloc = CurModule->getOrInsertFunction("poolalloc", PoolAllocTy);
 195
 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);
 200
 201   // The poolallocarray function
 202   FunctionType *PoolAllocArrayTy =
 203     FunctionType::get(VoidPtrTy,
 204                       make_vector<const Type*>(PoolDescPtr, Type::UIntTy, 0),
 205                       false);
 206   PoolAllocArray = CurModule->getOrInsertFunction("poolallocarray",
 207                                                   PoolAllocArrayTy);
 208
 209 }
 210
 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
 214 // caller
 215 //
 216 void PoolAllocate::InlineIndirectCalls(Function &F, DSGraph &G,
 217                                        hash_set<Function*> &visited) {
 218   std::vector<DSCallSite> callSites = G.getFunctionCalls();
 219
 220   visited.insert(&F);
 221
 222   // For each indirect call site in the function, inline all the potential
 223   // targets
 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);
 241         }
 242         G.mergeInGraph(*CSI, *TFI->second, TargetG, DSGraph::KeepModRefBits |
 243                        DSGraph::KeepAllocaBit | DSGraph::DontCloneCallNodes |
 244                        DSGraph::DontCloneAuxCallNodes);
 245       }
 246     }
 247   }
 248
 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
 251   // exactly once
 252   InlinedFuncs.insert(&F);
 253 }
 254
 255 void PoolAllocate::FindFunctionPoolArgs(Function &F) {
 256
 257   // The DSGraph is merged with the globals graph.
 258   DSGraph &G = BU->getDSGraph(F);
 259   G.mergeInGlobalsGraph();
 260
 261   // Inline the potential targets of indirect calls
 262   hash_set<Function*> visitedFuncs;
 263   InlineIndirectCalls(F, G, visitedFuncs);
 264
 265   // At this point the DS Graphs have been modified in place including
 266   // information about globals as well as indirect calls, making it useful
 267   // for pool allocation
 268   std::vector<DSNode*> &Nodes = G.getNodes();
 269   if (Nodes.empty()) return ;  // No memory activity, nothing is required
 270
 271   FuncInfo &FI = FunctionInfo[&F];   // Create a new entry for F
 272
 273   FI.Clone = 0;
 274
 275   // Initialize the PoolArgFirst and PoolArgLast for the function depending
 276   // on whether there have been other functions in the equivalence class
 277   // that have pool arguments so far in the analysis.
 278   if (!FuncECs.findClass(&F)) {
 279     FI.PoolArgFirst = FI.PoolArgLast = 0;
 280   } else {
 281     if (EqClass2LastPoolArg.find(FuncECs.findClass(&F)) !=
 282         EqClass2LastPoolArg.end())
 283       FI.PoolArgFirst = FI.PoolArgLast =
 284         EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1;
 285     else
 286       FI.PoolArgFirst = FI.PoolArgLast = 0;
 287   }
 288
 289   // Find DataStructure nodes which are allocated in pools non-local to the
 290   // current function.  This set will contain all of the DSNodes which require
 291   // pools to be passed in from outside of the function.
 292   hash_set<DSNode*> &MarkedNodes = FI.MarkedNodes;
 293
 294   // Mark globals and incomplete nodes as live... (this handles arguments)
 295   if (F.getName() != "main")
 296     for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
 297       if (Nodes[i]->isGlobalNode() && !Nodes[i]->isIncomplete())
 298         DEBUG(std::cerr << "Global node is not Incomplete\n");
 299       if ((Nodes[i]->isIncomplete() || Nodes[i]->isGlobalNode()) &&
 300           Nodes[i]->isHeapNode())
 301         Nodes[i]->markReachableNodes(MarkedNodes);
 302     }
 303
 304   // Marked the returned node as alive...
 305   if (DSNode *RetNode = G.getReturnNodeFor(F).getNode())
 306     if (RetNode->isHeapNode())
 307       RetNode->markReachableNodes(MarkedNodes);
 308
 309   if (MarkedNodes.empty())   // We don't need to clone the function if there
 310     return;                  // are no incoming arguments to be added.
 311
 312   // Erase any marked node that is not a heap node
 313
 314   for (hash_set<DSNode*>::iterator I = MarkedNodes.begin(),
 315          E = MarkedNodes.end(); I != E; ) {
 316     // erase invalidates hash_set iterators if the iterator points to the
 317     // element being erased
 318     if (!(*I)->isHeapNode())
 319       MarkedNodes.erase(I++);
 320     else
 321       ++I;
 322   }
 323
 324   FI.PoolArgLast += MarkedNodes.size();
 325
 326
 327   if (FuncECs.findClass(&F)) {
 328     // Update the equivalence class last pool argument information
 329     // only if there actually were pool arguments to the function.
 330     // Also, there is no entry for the Eq. class in EqClass2LastPoolArg
 331     // if there are no functions in the equivalence class with pool arguments.
 332     if (FI.PoolArgLast != FI.PoolArgFirst)
 333       EqClass2LastPoolArg[FuncECs.findClass(&F)] = FI.PoolArgLast - 1;
 334   }
 335
 336 }
 337
 338 // MakeFunctionClone - If the specified function needs to be modified for pool
 339 // allocation support, make a clone of it, adding additional arguments as
 340 // neccesary, and return it.  If not, just return null.
 341 //
 342 Function *PoolAllocate::MakeFunctionClone(Function &F) {
 343
 344   DSGraph &G = BU->getDSGraph(F);
 345
 346   std::vector<DSNode*> &Nodes = G.getNodes();
 347   if (Nodes.empty())
 348     return 0;
 349
 350   FuncInfo &FI = FunctionInfo[&F];
 351
 352   hash_set<DSNode*> &MarkedNodes = FI.MarkedNodes;
 353
 354   if (!FuncECs.findClass(&F)) {
 355     // Not in any equivalence class
 356     if (MarkedNodes.empty())
 357       return 0;
 358   } else {
 359     // No need to clone if there are no pool arguments in any function in the
 360     // equivalence class
 361     if (!EqClass2LastPoolArg.count(FuncECs.findClass(&F)))
 362       return 0;
 363   }
 364
 365   // Figure out what the arguments are to be for the new version of the function
 366   const FunctionType *OldFuncTy = F.getFunctionType();
 367   std::vector<const Type*> ArgTys;
 368   if (!FuncECs.findClass(&F)) {
 369     ArgTys.reserve(OldFuncTy->getParamTypes().size() + MarkedNodes.size());
 370     FI.ArgNodes.reserve(MarkedNodes.size());
 371     for (hash_set<DSNode*>::iterator I = MarkedNodes.begin(),
 372            E = MarkedNodes.end(); I != E; ++I) {
 373       ArgTys.push_back(PoolDescPtr);      // Add the appropriate # of pool descs
 374       FI.ArgNodes.push_back(*I);
 375     }
 376     if (FI.ArgNodes.empty()) return 0;      // No nodes to be pool allocated!
 377
 378   }
 379   else {
 380     // This function is a member of an equivalence class and needs to be cloned
 381     ArgTys.reserve(OldFuncTy->getParamTypes().size() +
 382                    EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1);
 383     FI.ArgNodes.reserve(EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1);
 384
 385     for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i) {
 386       ArgTys.push_back(PoolDescPtr);      // Add the appropriate # of pool
 387                                           // descs
 388     }
 389
 390     for (hash_set<DSNode*>::iterator I = MarkedNodes.begin(),
 391            E = MarkedNodes.end(); I != E; ++I) {
 392       FI.ArgNodes.push_back(*I);
 393     }
 394
 395     assert ((FI.ArgNodes.size() == (unsigned) (FI.PoolArgLast -
 396                                                FI.PoolArgFirst)) &&
 397             "Number of ArgNodes equal to the number of pool arguments used by this function");
 398
 399     if (FI.ArgNodes.empty()) return 0;
 400   }
 401
 402
 403   ArgTys.insert(ArgTys.end(), OldFuncTy->getParamTypes().begin(),
 404                 OldFuncTy->getParamTypes().end());
 405
 406
 407   // Create the new function prototype
 408   FunctionType *FuncTy = FunctionType::get(OldFuncTy->getReturnType(), ArgTys,
 409                                            OldFuncTy->isVarArg());
 410   // Create the new function...
 411   Function *New = new Function(FuncTy, GlobalValue::InternalLinkage,
 412                                F.getName(), F.getParent());
 413
 414   // Set the rest of the new arguments names to be PDa<n> and add entries to the
 415   // pool descriptors map
 416   std::map<DSNode*, Value*> &PoolDescriptors = FI.PoolDescriptors;
 417   Function::aiterator NI = New->abegin();
 418
 419   if (FuncECs.findClass(&F)) {
 420     // If the function belongs to an equivalence class
 421     for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i,
 422            ++NI)
 423       NI->setName("PDa");
 424
 425     NI = New->abegin();
 426     if (FI.PoolArgFirst > 0)
 427       for (int i = 0; i < FI.PoolArgFirst; ++NI, ++i)
 428         ;
 429
 430     for (unsigned i = 0, e = FI.ArgNodes.size(); i != e; ++i, ++NI)
 431       PoolDescriptors.insert(std::make_pair(FI.ArgNodes[i], NI));
 432
 433     NI = New->abegin();
 434     if (EqClass2LastPoolArg.count(FuncECs.findClass(&F)))
 435       for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i, ++NI)
 436         ;
 437   } else {
 438     // If the function does not belong to an equivalence class
 439     if (FI.ArgNodes.size())
 440       for (unsigned i = 0, e = FI.ArgNodes.size(); i != e; ++i, ++NI) {
 441         NI->setName("PDa");  // Add pd entry
 442         PoolDescriptors.insert(std::make_pair(FI.ArgNodes[i], NI));
 443       }
 444     NI = New->abegin();
 445     if (FI.ArgNodes.size())
 446       for (unsigned i = 0; i < FI.ArgNodes.size(); ++NI, ++i)
 447         ;
 448   }
 449
 450   // Map the existing arguments of the old function to the corresponding
 451   // arguments of the new function.
 452   std::map<const Value*, Value*> ValueMap;
 453   if (NI != New->aend())
 454     for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I, ++NI) {
 455       ValueMap[I] = NI;
 456       NI->setName(I->getName());
 457     }
 458
 459   // Populate the value map with all of the globals in the program.
 460   // FIXME: This should be unneccesary!
 461   Module &M = *F.getParent();
 462   for (Module::iterator I = M.begin(), E=M.end(); I!=E; ++I)    ValueMap[I] = I;
 463   for (Module::giterator I = M.gbegin(), E=M.gend(); I!=E; ++I) ValueMap[I] = I;
 464
 465   // Perform the cloning.
 466   std::vector<ReturnInst*> Returns;
 467   CloneFunctionInto(New, &F, ValueMap, Returns);
 468
 469   // Invert the ValueMap into the NewToOldValueMap
 470   std::map<Value*, const Value*> &NewToOldValueMap = FI.NewToOldValueMap;
 471   for (std::map<const Value*, Value*>::iterator I = ValueMap.begin(),
 472          E = ValueMap.end(); I != E; ++I)
 473     NewToOldValueMap.insert(std::make_pair(I->second, I->first));
 474
 475   return FI.Clone = New;
 476 }
 477
 478
 479 // processFunction - Pool allocate any data structures which are contained in
 480 // the specified function...
 481 //
 482 void PoolAllocate::ProcessFunctionBody(Function &F, Function &NewF) {
 483   DSGraph &G = BU->getDSGraph(F);
 484
 485   std::vector<DSNode*> &Nodes = G.getNodes();
 486   if (Nodes.empty()) return;     // Quick exit if nothing to do...
 487
 488   FuncInfo &FI = FunctionInfo[&F];   // Get FuncInfo for F
 489   hash_set<DSNode*> &MarkedNodes = FI.MarkedNodes;
 490
 491   DEBUG(std::cerr << "[" << F.getName() << "] Pool Allocate: ");
 492
 493   // Loop over all of the nodes which are non-escaping, adding pool-allocatable
 494   // ones to the NodesToPA vector.
 495   std::vector<DSNode*> NodesToPA;
 496   for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
 497     if (Nodes[i]->isHeapNode() &&   // Pick nodes with heap elems
 498         !MarkedNodes.count(Nodes[i]))              // Can't be marked
 499       NodesToPA.push_back(Nodes[i]);
 500
 501   DEBUG(std::cerr << NodesToPA.size() << " nodes to pool allocate\n");
 502   if (!NodesToPA.empty()) {
 503     // Create pool construction/destruction code
 504     std::map<DSNode*, Value*> &PoolDescriptors = FI.PoolDescriptors;
 505     CreatePools(NewF, NodesToPA, PoolDescriptors);
 506   }
 507
 508   // Transform the body of the function now...
 509   TransformFunctionBody(NewF, F, G, FI);
 510 }
 511
 512
 513 // CreatePools - This creates the pool initialization and destruction code for
 514 // the DSNodes specified by the NodesToPA list.  This adds an entry to the
 515 // PoolDescriptors map for each DSNode.
 516 //
 517 void PoolAllocate::CreatePools(Function &F,
 518                                const std::vector<DSNode*> &NodesToPA,
 519                                std::map<DSNode*, Value*> &PoolDescriptors) {
 520   // Find all of the return nodes in the CFG...
 521   std::vector<BasicBlock*> ReturnNodes;
 522   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 523     if (isa<ReturnInst>(I->getTerminator()))
 524       ReturnNodes.push_back(I);
 525
 526   TargetData &TD = getAnalysis<TargetData>();
 527
 528   // Loop over all of the pools, inserting code into the entry block of the
 529   // function for the initialization and code in the exit blocks for
 530   // destruction.
 531   //
 532   Instruction *InsertPoint = F.front().begin();
 533   for (unsigned i = 0, e = NodesToPA.size(); i != e; ++i) {
 534     DSNode *Node = NodesToPA[i];
 535
 536     // Create a new alloca instruction for the pool...
 537     Value *AI = new AllocaInst(PoolDescType, 0, "PD", InsertPoint);
 538
 539     Value *ElSize;
 540
 541     // Void types in DS graph are never used
 542     if (Node->getType() != Type::VoidTy)
 543       ElSize = ConstantUInt::get(Type::UIntTy, TD.getTypeSize(Node->getType()));
 544     else {
 545       DEBUG(std::cerr << "Potential node collapsing in " << F.getName()
 546                 << ". All Data Structures may not be pool allocated\n");
 547       ElSize = ConstantUInt::get(Type::UIntTy, 0);
 548     }
 549
 550     // Insert the call to initialize the pool...
 551     new CallInst(PoolInit, make_vector(AI, ElSize, 0), "", InsertPoint);
 552
 553     // Update the PoolDescriptors map
 554     PoolDescriptors.insert(std::make_pair(Node, AI));
 555
 556     // Insert a call to pool destroy before each return inst in the function
 557     for (unsigned r = 0, e = ReturnNodes.size(); r != e; ++r)
 558       new CallInst(PoolDestroy, make_vector(AI, 0), "",
 559                    ReturnNodes[r]->getTerminator());
 560   }
 561 }
 562
 563
 564 namespace {
 565   /// FuncTransform - This class implements transformation required of pool
 566   /// allocated functions.
 567   struct FuncTransform : public InstVisitor<FuncTransform> {
 568     PoolAllocate &PAInfo;
 569     DSGraph &G;      // The Bottom-up DS Graph
 570     DSGraph &TDG;    // The Top-down DS Graph
 571     FuncInfo &FI;
 572
 573     FuncTransform(PoolAllocate &P, DSGraph &g, DSGraph &tdg, FuncInfo &fi)
 574       : PAInfo(P), G(g), TDG(tdg), FI(fi) {
 575     }
 576
 577     void visitMallocInst(MallocInst &MI);
 578     void visitFreeInst(FreeInst &FI);
 579     void visitCallInst(CallInst &CI);
 580
 581     // The following instructions are never modified by pool allocation
 582     void visitBranchInst(BranchInst &I) { }
 583     void visitBinaryOperator(Instruction &I) { }
 584     void visitShiftInst (ShiftInst &I) { }
 585     void visitSwitchInst (SwitchInst &I) { }
 586     void visitCastInst (CastInst &I) { }
 587     void visitAllocaInst(AllocaInst &I) { }
 588     void visitLoadInst(LoadInst &I) { }
 589     void visitGetElementPtrInst (GetElementPtrInst &I) { }
 590
 591     void visitReturnInst(ReturnInst &I);
 592     void visitStoreInst (StoreInst &I);
 593     void visitPHINode(PHINode &I);
 594
 595     void visitInstruction(Instruction &I) {
 596       std::cerr << "PoolAllocate does not recognize this instruction\n";
 597       abort();
 598     }
 599
 600   private:
 601     DSNodeHandle& getDSNodeHFor(Value *V) {
 602       //      if (isa<Constant>(V))
 603       //        return DSNodeHandle();
 604
 605       if (!FI.NewToOldValueMap.empty()) {
 606         // If the NewToOldValueMap is in effect, use it.
 607         std::map<Value*,const Value*>::iterator I = FI.NewToOldValueMap.find(V);
 608         if (I != FI.NewToOldValueMap.end())
 609           V = (Value*)I->second;
 610       }
 611
 612       return G.getScalarMap()[V];
 613     }
 614
 615     DSNodeHandle& getTDDSNodeHFor(Value *V) {
 616       if (!FI.NewToOldValueMap.empty()) {
 617         // If the NewToOldValueMap is in effect, use it.
 618         std::map<Value*,const Value*>::iterator I = FI.NewToOldValueMap.find(V);
 619         if (I != FI.NewToOldValueMap.end())
 620           V = (Value*)I->second;
 621       }
 622
 623       return TDG.getScalarMap()[V];
 624     }
 625
 626     Value *getPoolHandle(Value *V) {
 627       DSNode *Node = getDSNodeHFor(V).getNode();
 628       // Get the pool handle for this DSNode...
 629       std::map<DSNode*, Value*>::iterator I = FI.PoolDescriptors.find(Node);
 630
 631       if (I != FI.PoolDescriptors.end()) {
 632         // Check that the node pointed to by V in the TD DS graph is not
 633         // collapsed
 634         DSNode *TDNode = getTDDSNodeHFor(V).getNode();
 635         if (TDNode->getType() != Type::VoidTy)
 636           return I->second;
 637         else {
 638           PAInfo.CollapseFlag = 1;
 639           return 0;
 640         }
 641       }
 642       else
 643         return 0;
 644
 645     }
 646
 647     bool isFuncPtr(Value *V);
 648
 649     Function* getFuncClass(Value *V);
 650
 651     Value* retCloneIfFunc(Value *V);
 652   };
 653 }
 654
 655 void PoolAllocate::TransformFunctionBody(Function &F, Function &OldF,
 656                                          DSGraph &G, FuncInfo &FI) {
 657   FuncTransform(*this, G, TDDS->getDSGraph(OldF), FI).visit(F);
 658 }
 659
 660 // Returns true if V is a function pointer
 661 bool FuncTransform::isFuncPtr(Value *V) {
 662   if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
 663      return isa<FunctionType>(PTy->getElementType());
 664   return false;
 665 }
 666
 667 // Given a function pointer, return the function eq. class if one exists
 668 Function* FuncTransform::getFuncClass(Value *V) {
 669   // Look at DSGraph and see if the set of of functions it could point to
 670   // are pool allocated.
 671
 672   if (!isFuncPtr(V))
 673     return 0;
 674
 675   // Two cases:
 676   // if V is a constant
 677   if (Function *theFunc = dyn_cast<Function>(V)) {
 678     if (!PAInfo.FuncECs.findClass(theFunc))
 679       // If this function does not belong to any equivalence class
 680       return 0;
 681     if (PAInfo.EqClass2LastPoolArg.count(PAInfo.FuncECs.findClass(theFunc)))
 682       return PAInfo.FuncECs.findClass(theFunc);
 683     else
 684       return 0;
 685   }
 686
 687   // if V is not a constant
 688   DSNode *DSN = TDG.getNodeForValue(V).getNode();
 689   if (!DSN) {
 690     return 0;
 691   }
 692   const std::vector<GlobalValue*> &Callees = DSN->getGlobals();
 693   if (Callees.size() > 0) {
 694     Function *calledF = dyn_cast<Function>(*Callees.begin());
 695     assert(PAInfo.FuncECs.findClass(calledF) && "should exist in some eq. class");
 696     if (PAInfo.EqClass2LastPoolArg.count(PAInfo.FuncECs.findClass(calledF)))
 697       return PAInfo.FuncECs.findClass(calledF);
 698   }
 699
 700   return 0;
 701 }
 702
 703 // Returns the clone if  V is a static function (not a pointer) and belongs
 704 // to an equivalence class i.e. is pool allocated
 705 Value* FuncTransform::retCloneIfFunc(Value *V) {
 706   if (Function *fixedFunc = dyn_cast<Function>(V))
 707     if (getFuncClass(V))
 708       return PAInfo.getFuncInfo(*fixedFunc)->Clone;
 709
 710   return 0;
 711 }
 712
 713 void FuncTransform::visitReturnInst (ReturnInst &RI) {
 714   if (RI.getNumOperands())
 715     if (Value *clonedFunc = retCloneIfFunc(RI.getOperand(0))) {
 716       // Cast the clone of RI.getOperand(0) to the non-pool-allocated type
 717       CastInst *CastI = new CastInst(clonedFunc, RI.getOperand(0)->getType(),
 718                                      "tmp", &RI);
 719       // Insert return instruction that returns the casted value
 720       ReturnInst *RetI = new ReturnInst(CastI, &RI);
 721
 722       // Remove original return instruction
 723       RI.getParent()->getInstList().erase(&RI);
 724
 725       if (!FI.NewToOldValueMap.empty()) {
 726         std::map<Value*,const Value*>::iterator II =
 727           FI.NewToOldValueMap.find(&RI);
 728         assert(II != FI.NewToOldValueMap.end() &&
 729                "RI not found in clone?");
 730         FI.NewToOldValueMap.insert(std::make_pair(RetI, II->second));
 731         FI.NewToOldValueMap.erase(II);
 732       }
 733     }
 734 }
 735
 736 void FuncTransform::visitStoreInst (StoreInst &SI) {
 737   // Check if a constant function is being stored
 738   if (Value *clonedFunc = retCloneIfFunc(SI.getOperand(0))) {
 739     CastInst *CastI = new CastInst(clonedFunc, SI.getOperand(0)->getType(),
 740                                    "tmp", &SI);
 741     StoreInst *StoreI = new StoreInst(CastI, SI.getOperand(1), &SI);
 742     SI.getParent()->getInstList().erase(&SI);
 743
 744     // Update the NewToOldValueMap if this is a clone
 745     if (!FI.NewToOldValueMap.empty()) {
 746       std::map<Value*,const Value*>::iterator II =
 747         FI.NewToOldValueMap.find(&SI);
 748       assert(II != FI.NewToOldValueMap.end() &&
 749              "SI not found in clone?");
 750       FI.NewToOldValueMap.insert(std::make_pair(StoreI, II->second));
 751       FI.NewToOldValueMap.erase(II);
 752     }
 753   }
 754 }
 755
 756 void FuncTransform::visitPHINode(PHINode &PI) {
 757   // If any of the operands of the PHI node is a constant function pointer
 758   // that is cloned, the cast instruction has to be inserted at the end of the
 759   // previous basic block
 760
 761   if (isFuncPtr(&PI)) {
 762     PHINode *V = new PHINode(PI.getType(), PI.getName(), &PI);
 763     for (unsigned i = 0 ; i < PI.getNumIncomingValues(); ++i) {
 764       if (Value *clonedFunc = retCloneIfFunc(PI.getIncomingValue(i))) {
 765         // Insert CastInst at the end of  PI.getIncomingBlock(i)
 766         BasicBlock::iterator BBI = --PI.getIncomingBlock(i)->end();
 767         // BBI now points to the terminator instruction of the basic block.
 768         CastInst *CastI = new CastInst(clonedFunc, PI.getType(), "tmp", BBI);
 769         V->addIncoming(CastI, PI.getIncomingBlock(i));
 770       } else {
 771         V->addIncoming(PI.getIncomingValue(i), PI.getIncomingBlock(i));
 772       }
 773
 774     }
 775     PI.replaceAllUsesWith(V);
 776     PI.getParent()->getInstList().erase(&PI);
 777
 778     DSGraph::ScalarMapTy &SM = G.getScalarMap();
 779     DSGraph::ScalarMapTy::iterator PII = SM.find(&PI);
 780
 781     // Update Scalar map of DSGraph if this is one of the original functions
 782     // Otherwise update the NewToOldValueMap
 783     if (PII != SM.end()) {
 784       SM.insert(std::make_pair(V, PII->second));
 785       SM.erase(PII);                     // Destroy the PHINode
 786     } else {
 787       std::map<Value*,const Value*>::iterator II =
 788         FI.NewToOldValueMap.find(&PI);
 789       assert(II != FI.NewToOldValueMap.end() &&
 790              "PhiI not found in clone?");
 791       FI.NewToOldValueMap.insert(std::make_pair(V, II->second));
 792       FI.NewToOldValueMap.erase(II);
 793     }
 794   }
 795 }
 796
 797 void FuncTransform::visitMallocInst(MallocInst &MI) {
 798   // Get the pool handle for the node that this contributes to...
 799   Value *PH = getPoolHandle(&MI);
 800
 801   // NB: PH is zero even if the node is collapsed
 802   if (PH == 0) return;
 803
 804   // Insert a call to poolalloc
 805   Value *V;
 806   if (MI.isArrayAllocation())
 807     V = new CallInst(PAInfo.PoolAllocArray,
 808                      make_vector(PH, MI.getOperand(0), 0),
 809                      MI.getName(), &MI);
 810   else
 811     V = new CallInst(PAInfo.PoolAlloc, make_vector(PH, 0),
 812                      MI.getName(), &MI);
 813
 814   MI.setName("");  // Nuke MIs name
 815
 816   Value *Casted = V;
 817
 818   // Cast to the appropriate type if necessary
 819   if (V->getType() != MI.getType()) {
 820     Casted = new CastInst(V, MI.getType(), V->getName(), &MI);
 821   }
 822
 823   // Update def-use info
 824   MI.replaceAllUsesWith(Casted);
 825
 826   // Remove old malloc instruction
 827   MI.getParent()->getInstList().erase(&MI);
 828
 829   DSGraph::ScalarMapTy &SM = G.getScalarMap();
 830   DSGraph::ScalarMapTy::iterator MII = SM.find(&MI);
 831
 832   // If we are modifying the original function, update the DSGraph...
 833   if (MII != SM.end()) {
 834     // V and Casted now point to whatever the original malloc did...
 835     SM.insert(std::make_pair(V, MII->second));
 836     if (V != Casted)
 837       SM.insert(std::make_pair(Casted, MII->second));
 838     SM.erase(MII);                     // The malloc is now destroyed
 839   } else {             // Otherwise, update the NewToOldValueMap
 840     std::map<Value*,const Value*>::iterator MII =
 841       FI.NewToOldValueMap.find(&MI);
 842     assert(MII != FI.NewToOldValueMap.end() && "MI not found in clone?");
 843     FI.NewToOldValueMap.insert(std::make_pair(V, MII->second));
 844     if (V != Casted)
 845       FI.NewToOldValueMap.insert(std::make_pair(Casted, MII->second));
 846     FI.NewToOldValueMap.erase(MII);
 847   }
 848 }
 849
 850 void FuncTransform::visitFreeInst(FreeInst &FrI) {
 851   Value *Arg = FrI.getOperand(0);
 852   Value *PH = getPoolHandle(Arg);  // Get the pool handle for this DSNode...
 853   if (PH == 0) return;
 854   // Insert a cast and a call to poolfree...
 855   Value *Casted = Arg;
 856   if (Arg->getType() != PointerType::get(Type::SByteTy))
 857     Casted = new CastInst(Arg, PointerType::get(Type::SByteTy),
 858                                  Arg->getName()+".casted", &FrI);
 859
 860   CallInst *FreeI = new CallInst(PAInfo.PoolFree, make_vector(PH, Casted, 0),
 861                                  "", &FrI);
 862   // Delete the now obsolete free instruction...
 863   FrI.getParent()->getInstList().erase(&FrI);
 864
 865   // Update the NewToOldValueMap if this is a clone
 866   if (!FI.NewToOldValueMap.empty()) {
 867     std::map<Value*,const Value*>::iterator II =
 868       FI.NewToOldValueMap.find(&FrI);
 869     assert(II != FI.NewToOldValueMap.end() &&
 870            "FrI not found in clone?");
 871     FI.NewToOldValueMap.insert(std::make_pair(FreeI, II->second));
 872     FI.NewToOldValueMap.erase(II);
 873   }
 874 }
 875
 876 static void CalcNodeMapping(DSNodeHandle& Caller, DSNodeHandle& Callee,
 877                             std::map<DSNode*, DSNode*> &NodeMapping) {
 878   DSNode *CalleeNode = Callee.getNode();
 879   DSNode *CallerNode = Caller.getNode();
 880
 881   unsigned CalleeOffset = Callee.getOffset();
 882   unsigned CallerOffset = Caller.getOffset();
 883
 884   if (CalleeNode == 0) return;
 885
 886   // If callee has a node and caller doesn't, then a constant argument was
 887   // passed by the caller
 888   if (CallerNode == 0) {
 889     NodeMapping.insert(NodeMapping.end(), std::make_pair(CalleeNode,
 890                                                          (DSNode *) 0));
 891   }
 892
 893   // Map the callee node to the caller node.
 894   // NB: The callee node could be of a different type. Eg. if it points to the
 895   // field of a struct that the caller points to
 896   std::map<DSNode*, DSNode*>::iterator I = NodeMapping.find(CalleeNode);
 897   if (I != NodeMapping.end()) {   // Node already in map...
 898     assert(I->second == CallerNode &&
 899            "Node maps to different nodes on paths?");
 900   } else {
 901     NodeMapping.insert(I, std::make_pair(CalleeNode, CallerNode));
 902
 903     if (CalleeNode->getType() != CallerNode->getType() && CallerOffset == 0)
 904       DEBUG(std::cerr << "NB: Mapping of nodes between different types\n");
 905
 906     // Recursively map the callee links to the caller links starting from the
 907     // offset in the node into which they are mapped.
 908     // Being a BU Graph, the callee ought to have smaller number of links unless
 909     // there is collapsing in the caller
 910     unsigned numCallerLinks = CallerNode->getNumLinks() - CallerOffset;
 911     unsigned numCalleeLinks = CalleeNode->getNumLinks() - CalleeOffset;
 912
 913     if (numCallerLinks > 0) {
 914       if (numCallerLinks < numCalleeLinks) {
 915         DEBUG(std::cerr << "Potential node collapsing in caller\n");
 916         for (unsigned i = 0, e = numCalleeLinks; i != e; ++i)
 917           CalcNodeMapping(CallerNode->getLink(((i%numCallerLinks) << DS::PointerShift) + CallerOffset), CalleeNode->getLink((i << DS::PointerShift) + CalleeOffset), NodeMapping);
 918       } else {
 919         for (unsigned i = 0, e = numCalleeLinks; i != e; ++i)
 920           CalcNodeMapping(CallerNode->getLink((i << DS::PointerShift) + CallerOffset), CalleeNode->getLink((i << DS::PointerShift) + CalleeOffset), NodeMapping);
 921       }
 922     } else if (numCalleeLinks > 0) {
 923       DEBUG(std::cerr <<
 924             "Caller has unexpanded node, due to indirect call perhaps!\n");
 925     }
 926   }
 927 }
 928
 929 void FuncTransform::visitCallInst(CallInst &CI) {
 930   Function *CF = CI.getCalledFunction();
 931
 932   // optimization for function pointers that are basically gotten from a cast
 933   // with only one use and constant expressions with casts in them
 934   if (!CF) {
 935     if (CastInst* CastI = dyn_cast<CastInst>(CI.getCalledValue())) {
 936       if (isa<Function>(CastI->getOperand(0)) &&
 937           CastI->getOperand(0)->getType() == CastI->getType())
 938         CF = dyn_cast<Function>(CastI->getOperand(0));
 939     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(CI.getOperand(0))) {
 940       if (CE->getOpcode() == Instruction::Cast) {
 941         if (isa<ConstantPointerRef>(CE->getOperand(0)))
 942           return;
 943         else
 944           assert(0 && "Function pointer cast not handled as called function\n");
 945       }
 946     }
 947
 948   }
 949
 950   DSGraph &CallerG = G;
 951
 952   std::vector<Value*> Args;
 953   if (!CF) {   // Indirect call
 954     DEBUG(std::cerr << "  Handling call: " << CI);
 955
 956     std::map<unsigned, Value*> PoolArgs;
 957     Function *FuncClass;
 958
 959     std::pair<std::multimap<CallInst*, Function*>::iterator,
 960               std::multimap<CallInst*, Function*>::iterator> Targets =
 961       PAInfo.CallInstTargets.equal_range(&CI);
 962     for (std::multimap<CallInst*, Function*>::iterator TFI = Targets.first,
 963            TFE = Targets.second; TFI != TFE; ++TFI) {
 964       if (TFI == Targets.first) {
 965         FuncClass = PAInfo.FuncECs.findClass(TFI->second);
 966         // Nothing to transform if there are no pool arguments in this
 967         // equivalence class of functions.
 968         if (!PAInfo.EqClass2LastPoolArg.count(FuncClass))
 969           return;
 970       }
 971
 972       FuncInfo *CFI = PAInfo.getFuncInfo(*TFI->second);
 973
 974       if (!CFI->ArgNodes.size()) continue;  // Nothing to transform...
 975
 976       DSGraph &CG = PAInfo.getBUDataStructures().getDSGraph(*TFI->second);
 977       std::map<DSNode*, DSNode*> NodeMapping;
 978
 979       Function::aiterator AI = TFI->second->abegin(), AE = TFI->second->aend();
 980       unsigned OpNum = 1;
 981       for ( ; AI != AE; ++AI, ++OpNum) {
 982         if (!isa<Constant>(CI.getOperand(OpNum)))
 983           CalcNodeMapping(getDSNodeHFor(CI.getOperand(OpNum)),
 984                           CG.getScalarMap()[AI], NodeMapping);
 985       }
 986       assert(OpNum == CI.getNumOperands() && "Varargs calls not handled yet!");
 987
 988       if (CI.getType() != Type::VoidTy)
 989         CalcNodeMapping(getDSNodeHFor(&CI),
 990                         CG.getReturnNodeFor(*TFI->second), NodeMapping);
 991
 992       // Map the nodes that are pointed to by globals.
 993       // For all globals map getDSNodeForGlobal(g)->CG.getDSNodeForGlobal(g)
 994       for (DSGraph::ScalarMapTy::iterator SMI = G.getScalarMap().begin(),
 995              SME = G.getScalarMap().end(); SMI != SME; ++SMI)
 996         if (isa<GlobalValue>(SMI->first)) {
 997           CalcNodeMapping(SMI->second,
 998                           CG.getScalarMap()[SMI->first], NodeMapping);
 999         }
1000
1001       unsigned idx = CFI->PoolArgFirst;
1002
1003       // The following loop determines the pool pointers corresponding to
1004       // CFI.
1005       for (unsigned i = 0, e = CFI->ArgNodes.size(); i != e; ++i, ++idx) {
1006         if (NodeMapping.count(CFI->ArgNodes[i])) {
1007           assert(NodeMapping.count(CFI->ArgNodes[i]) && "Node not in mapping!");
1008           DSNode *LocalNode = NodeMapping.find(CFI->ArgNodes[i])->second;
1009           if (LocalNode) {
1010             assert(FI.PoolDescriptors.count(LocalNode) &&
1011                    "Node not pool allocated?");
1012             PoolArgs[idx] = FI.PoolDescriptors.find(LocalNode)->second;
1013           }
1014           else
1015             // LocalNode is null when a constant is passed in as a parameter
1016             PoolArgs[idx] = Constant::getNullValue(PoolDescPtr);
1017         } else {
1018           PoolArgs[idx] = Constant::getNullValue(PoolDescPtr);
1019         }
1020       }
1021     }
1022
1023     // Push the pool arguments into Args.
1024     if (PAInfo.EqClass2LastPoolArg.count(FuncClass)) {
1025       for (int i = 0; i <= PAInfo.EqClass2LastPoolArg[FuncClass]; ++i) {
1026         if (PoolArgs.find(i) != PoolArgs.end())
1027           Args.push_back(PoolArgs[i]);
1028         else
1029           Args.push_back(Constant::getNullValue(PoolDescPtr));
1030       }
1031
1032       assert(Args.size()== (unsigned) PAInfo.EqClass2LastPoolArg[FuncClass] + 1
1033              && "Call has same number of pool args as the called function");
1034     }
1035
1036     // Add the rest of the arguments (the original arguments of the function)...
1037     Args.insert(Args.end(), CI.op_begin()+1, CI.op_end());
1038
1039     std::string Name = CI.getName();
1040
1041     Value *NewCall;
1042     if (Args.size() > CI.getNumOperands() - 1) {
1043       // If there are any pool arguments
1044       CastInst *CastI =
1045         new CastInst(CI.getOperand(0),
1046                      PAInfo.getFuncInfo(*FuncClass)->Clone->getType(), "tmp",
1047                      &CI);
1048       NewCall = new CallInst(CastI, Args, Name, &CI);
1049     } else {
1050       NewCall = new CallInst(CI.getOperand(0), Args, Name, &CI);
1051     }
1052
1053     CI.replaceAllUsesWith(NewCall);
1054     DEBUG(std::cerr << "  Result Call: " << *NewCall);
1055
1056     if (CI.getType() != Type::VoidTy) {
1057       // If we are modifying the original function, update the DSGraph...
1058       DSGraph::ScalarMapTy &SM = G.getScalarMap();
1059       DSGraph::ScalarMapTy::iterator CII = SM.find(&CI);
1060       if (CII != SM.end()) {
1061         SM.insert(std::make_pair(NewCall, CII->second));
1062         SM.erase(CII);                     // Destroy the CallInst
1063       } else {
1064         // Otherwise update the NewToOldValueMap with the new CI return value
1065         std::map<Value*,const Value*>::iterator CII =
1066           FI.NewToOldValueMap.find(&CI);
1067         assert(CII != FI.NewToOldValueMap.end() && "CI not found in clone?");
1068         FI.NewToOldValueMap.insert(std::make_pair(NewCall, CII->second));
1069         FI.NewToOldValueMap.erase(CII);
1070       }
1071     } else if (!FI.NewToOldValueMap.empty()) {
1072       std::map<Value*,const Value*>::iterator II =
1073         FI.NewToOldValueMap.find(&CI);
1074       assert(II != FI.NewToOldValueMap.end() &&
1075              "CI not found in clone?");
1076       FI.NewToOldValueMap.insert(std::make_pair(NewCall, II->second));
1077       FI.NewToOldValueMap.erase(II);
1078     }
1079   }
1080   else {
1081
1082     FuncInfo *CFI = PAInfo.getFuncInfo(*CF);
1083
1084     if (CFI == 0 || CFI->Clone == 0) return;  // Nothing to transform...
1085
1086     DEBUG(std::cerr << "  Handling call: " << CI);
1087
1088     DSGraph &CG = PAInfo.getBUDataStructures().getDSGraph(*CF);  // Callee graph
1089
1090     // We need to figure out which local pool descriptors correspond to the pool
1091     // descriptor arguments passed into the function call.  Calculate a mapping
1092     // from callee DSNodes to caller DSNodes.  We construct a partial isomophism
1093     // between the graphs to figure out which pool descriptors need to be passed
1094     // in.  The roots of this mapping is found from arguments and return values.
1095     //
1096     std::map<DSNode*, DSNode*> NodeMapping;
1097
1098     Function::aiterator AI = CF->abegin(), AE = CF->aend();
1099     unsigned OpNum = 1;
1100     for (; AI != AE; ++AI, ++OpNum) {
1101       Value *callOp = CI.getOperand(OpNum);
1102       if (!isa<Constant>(callOp))
1103         CalcNodeMapping(getDSNodeHFor(callOp), CG.getScalarMap()[AI],
1104                         NodeMapping);
1105     }
1106     assert(OpNum == CI.getNumOperands() && "Varargs calls not handled yet!");
1107
1108     // Map the return value as well...
1109     if (CI.getType() != Type::VoidTy)
1110       CalcNodeMapping(getDSNodeHFor(&CI), CG.getReturnNodeFor(*CF),
1111                       NodeMapping);
1112
1113     // Map the nodes that are pointed to by globals.
1114     // For all globals map getDSNodeForGlobal(g)->CG.getDSNodeForGlobal(g)
1115     for (DSGraph::ScalarMapTy::iterator SMI = G.getScalarMap().begin(),
1116            SME = G.getScalarMap().end(); SMI != SME; ++SMI)
1117       if (isa<GlobalValue>(SMI->first)) {
1118         CalcNodeMapping(SMI->second,
1119                         CG.getScalarMap()[SMI->first], NodeMapping);
1120       }
1121
1122     // Okay, now that we have established our mapping, we can figure out which
1123     // pool descriptors to pass in...
1124
1125     // Add an argument for each pool which must be passed in...
1126     if (CFI->PoolArgFirst != 0) {
1127       for (int i = 0; i < CFI->PoolArgFirst; ++i)
1128         Args.push_back(Constant::getNullValue(PoolDescPtr));
1129     }
1130
1131     for (unsigned i = 0, e = CFI->ArgNodes.size(); i != e; ++i) {
1132       if (NodeMapping.count(CFI->ArgNodes[i])) {
1133
1134         DSNode *LocalNode = NodeMapping.find(CFI->ArgNodes[i])->second;
1135         if (LocalNode) {
1136           assert(FI.PoolDescriptors.count(LocalNode) &&
1137                  "Node not pool allocated?");
1138           Args.push_back(FI.PoolDescriptors.find(LocalNode)->second);
1139         } else
1140           Args.push_back(Constant::getNullValue(PoolDescPtr));
1141       } else {
1142         Args.push_back(Constant::getNullValue(PoolDescPtr));
1143       }
1144     }
1145
1146     Function *FuncClass = PAInfo.FuncECs.findClass(CF);
1147
1148     if (PAInfo.EqClass2LastPoolArg.count(FuncClass))
1149       for (int i = CFI->PoolArgLast;
1150            i <= PAInfo.EqClass2LastPoolArg[FuncClass]; ++i)
1151         Args.push_back(Constant::getNullValue(PoolDescPtr));
1152
1153     // Add the rest of the arguments...
1154     Args.insert(Args.end(), CI.op_begin()+1, CI.op_end());
1155
1156     std::string Name = CI.getName();
1157
1158     std::map<Value*,const Value*>::iterator CNewII;
1159
1160     Value *NewCall = new CallInst(CFI->Clone, Args, Name, &CI);
1161
1162     CI.replaceAllUsesWith(NewCall);
1163     DEBUG(std::cerr << "  Result Call: " << *NewCall);
1164
1165     if (CI.getType() != Type::VoidTy) {
1166       // If we are modifying the original function, update the DSGraph...
1167       DSGraph::ScalarMapTy &SM = G.getScalarMap();
1168       DSGraph::ScalarMapTy::iterator CII = SM.find(&CI);
1169       if (CII != SM.end()) {
1170         SM.insert(std::make_pair(NewCall, CII->second));
1171         SM.erase(CII);                     // Destroy the CallInst
1172       } else {
1173         // Otherwise update the NewToOldValueMap with the new CI return value
1174         std::map<Value*,const Value*>::iterator CNII =
1175           FI.NewToOldValueMap.find(&CI);
1176         assert(CNII != FI.NewToOldValueMap.end() && CNII->second &&
1177                "CI not found in clone?");
1178         FI.NewToOldValueMap.insert(std::make_pair(NewCall, CNII->second));
1179         FI.NewToOldValueMap.erase(CNII);
1180       }
1181     } else if (!FI.NewToOldValueMap.empty()) {
1182       std::map<Value*,const Value*>::iterator II =
1183         FI.NewToOldValueMap.find(&CI);
1184       assert(II != FI.NewToOldValueMap.end() && "CI not found in clone?");
1185       FI.NewToOldValueMap.insert(std::make_pair(NewCall, II->second));
1186       FI.NewToOldValueMap.erase(II);
1187     }
1188   }
1189
1190   CI.getParent()->getInstList().erase(&CI);
1191 }