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   DSGraph &G = BU->getDSGraph(F);
 258
 259   // Inline the potential targets of indirect calls
 260   hash_set<Function*> visitedFuncs;
 261   InlineIndirectCalls(F, G, visitedFuncs);
 262
 263   // The DSGraph is merged with the globals graph.
 264   G.mergeInGlobalsGraph();
 265
 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
 269   // incomplete.
 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);
 276     }
 277
 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
 283
 284   FuncInfo &FI = FunctionInfo[&F];   // Create a new entry for F
 285
 286   FI.Clone = 0;
 287
 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;
 293   } else {
 294     if (EqClass2LastPoolArg.find(FuncECs.findClass(&F)) !=
 295         EqClass2LastPoolArg.end())
 296       FI.PoolArgFirst = FI.PoolArgLast =
 297         EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1;
 298     else
 299       FI.PoolArgFirst = FI.PoolArgLast = 0;
 300   }
 301
 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;
 306
 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);
 315     }
 316
 317   // Marked the returned node as alive...
 318   if (DSNode *RetNode = G.getReturnNodeFor(F).getNode())
 319     if (RetNode->isHeapNode())
 320       RetNode->markReachableNodes(MarkedNodes);
 321
 322   if (MarkedNodes.empty())   // We don't need to clone the function if there
 323     return;                  // are no incoming arguments to be added.
 324
 325   // Erase any marked node that is not a heap node
 326
 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++);
 333     else
 334       ++I;
 335   }
 336
 337   FI.PoolArgLast += MarkedNodes.size();
 338
 339
 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;
 347   }
 348
 349 }
 350
 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.
 354 //
 355 Function *PoolAllocate::MakeFunctionClone(Function &F) {
 356
 357   DSGraph &G = BU->getDSGraph(F);
 358
 359   std::vector<DSNode*> &Nodes = G.getNodes();
 360   if (Nodes.empty())
 361     return 0;
 362
 363   FuncInfo &FI = FunctionInfo[&F];
 364
 365   hash_set<DSNode*> &MarkedNodes = FI.MarkedNodes;
 366
 367   if (!FuncECs.findClass(&F)) {
 368     // Not in any equivalence class
 369     if (MarkedNodes.empty())
 370       return 0;
 371   } else {
 372     // No need to clone if there are no pool arguments in any function in the
 373     // equivalence class
 374     if (!EqClass2LastPoolArg.count(FuncECs.findClass(&F)))
 375       return 0;
 376   }
 377
 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);
 388     }
 389     if (FI.ArgNodes.empty()) return 0;      // No nodes to be pool allocated!
 390
 391   }
 392   else {
 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);
 397
 398     for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i) {
 399       ArgTys.push_back(PoolDescPtr);      // Add the appropriate # of pool
 400                                           // descs
 401     }
 402
 403     for (hash_set<DSNode*>::iterator I = MarkedNodes.begin(),
 404            E = MarkedNodes.end(); I != E; ++I) {
 405       FI.ArgNodes.push_back(*I);
 406     }
 407
 408     assert ((FI.ArgNodes.size() == (unsigned) (FI.PoolArgLast -
 409                                                FI.PoolArgFirst)) &&
 410             "Number of ArgNodes equal to the number of pool arguments used by this function");
 411
 412     if (FI.ArgNodes.empty()) return 0;
 413   }
 414
 415
 416   ArgTys.insert(ArgTys.end(), OldFuncTy->getParamTypes().begin(),
 417                 OldFuncTy->getParamTypes().end());
 418
 419
 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());
 426
 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();
 431
 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,
 435            ++NI)
 436       NI->setName("PDa");
 437
 438     NI = New->abegin();
 439     if (FI.PoolArgFirst > 0)
 440       for (int i = 0; i < FI.PoolArgFirst; ++NI, ++i)
 441         ;
 442
 443     for (unsigned i = 0, e = FI.ArgNodes.size(); i != e; ++i, ++NI)
 444       PoolDescriptors.insert(std::make_pair(FI.ArgNodes[i], NI));
 445
 446     NI = New->abegin();
 447     if (EqClass2LastPoolArg.count(FuncECs.findClass(&F)))
 448       for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i, ++NI)
 449         ;
 450   } else {
 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));
 456       }
 457     NI = New->abegin();
 458     if (FI.ArgNodes.size())
 459       for (unsigned i = 0; i < FI.ArgNodes.size(); ++NI, ++i)
 460         ;
 461   }
 462
 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) {
 468       ValueMap[I] = NI;
 469       NI->setName(I->getName());
 470     }
 471
 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;
 477
 478   // Perform the cloning.
 479   std::vector<ReturnInst*> Returns;
 480   CloneFunctionInto(New, &F, ValueMap, Returns);
 481
 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));
 487
 488   return FI.Clone = New;
 489 }
 490
 491
 492 // processFunction - Pool allocate any data structures which are contained in
 493 // the specified function...
 494 //
 495 void PoolAllocate::ProcessFunctionBody(Function &F, Function &NewF) {
 496   DSGraph &G = BU->getDSGraph(F);
 497
 498   std::vector<DSNode*> &Nodes = G.getNodes();
 499   if (Nodes.empty()) return;     // Quick exit if nothing to do...
 500
 501   FuncInfo &FI = FunctionInfo[&F];   // Get FuncInfo for F
 502   hash_set<DSNode*> &MarkedNodes = FI.MarkedNodes;
 503
 504   DEBUG(std::cerr << "[" << F.getName() << "] Pool Allocate: ");
 505
 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]);
 513
 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);
 519   }
 520
 521   // Transform the body of the function now...
 522   TransformFunctionBody(NewF, F, G, FI);
 523 }
 524
 525
 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.
 529 //
 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);
 538
 539   TargetData &TD = getAnalysis<TargetData>();
 540
 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
 543   // destruction.
 544   //
 545   Instruction *InsertPoint = F.front().begin();
 546   for (unsigned i = 0, e = NodesToPA.size(); i != e; ++i) {
 547     DSNode *Node = NodesToPA[i];
 548
 549     // Create a new alloca instruction for the pool...
 550     Value *AI = new AllocaInst(PoolDescType, 0, "PD", InsertPoint);
 551
 552     Value *ElSize;
 553
 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()));
 557     else {
 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);
 561     }
 562
 563     // Insert the call to initialize the pool...
 564     new CallInst(PoolInit, make_vector(AI, ElSize, 0), "", InsertPoint);
 565
 566     // Update the PoolDescriptors map
 567     PoolDescriptors.insert(std::make_pair(Node, AI));
 568
 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());
 573   }
 574 }
 575
 576
 577 namespace {
 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
 584     FuncInfo &FI;
 585
 586     FuncTransform(PoolAllocate &P, DSGraph &g, DSGraph &tdg, FuncInfo &fi)
 587       : PAInfo(P), G(g), TDG(tdg), FI(fi) {
 588     }
 589
 590     void visitMallocInst(MallocInst &MI);
 591     void visitFreeInst(FreeInst &FI);
 592     void visitCallInst(CallInst &CI);
 593
 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) { }
 603
 604     void visitReturnInst(ReturnInst &I);
 605     void visitStoreInst (StoreInst &I);
 606     void visitPHINode(PHINode &I);
 607
 608     void visitInstruction(Instruction &I) {
 609       std::cerr << "PoolAllocate does not recognize this instruction\n";
 610       abort();
 611     }
 612
 613   private:
 614     DSNodeHandle& getDSNodeHFor(Value *V) {
 615       //      if (isa<Constant>(V))
 616       //        return DSNodeHandle();
 617
 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;
 623       }
 624
 625       return G.getScalarMap()[V];
 626     }
 627
 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;
 634       }
 635
 636       return TDG.getScalarMap()[V];
 637     }
 638
 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);
 643
 644       if (I != FI.PoolDescriptors.end()) {
 645         // Check that the node pointed to by V in the TD DS graph is not
 646         // collapsed
 647         DSNode *TDNode = getTDDSNodeHFor(V).getNode();
 648         if (TDNode->getType() != Type::VoidTy)
 649           return I->second;
 650         else {
 651           PAInfo.CollapseFlag = 1;
 652           return 0;
 653         }
 654       }
 655       else
 656         return 0;
 657
 658     }
 659
 660     bool isFuncPtr(Value *V);
 661
 662     Function* getFuncClass(Value *V);
 663
 664     Value* retCloneIfFunc(Value *V);
 665   };
 666 }
 667
 668 void PoolAllocate::TransformFunctionBody(Function &F, Function &OldF,
 669                                          DSGraph &G, FuncInfo &FI) {
 670   FuncTransform(*this, G, TDDS->getDSGraph(OldF), FI).visit(F);
 671 }
 672
 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());
 677   return false;
 678 }
 679
 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.
 684
 685   if (!isFuncPtr(V))
 686     return 0;
 687
 688   // Two cases:
 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
 693       return 0;
 694     if (PAInfo.EqClass2LastPoolArg.count(PAInfo.FuncECs.findClass(theFunc)))
 695       return PAInfo.FuncECs.findClass(theFunc);
 696     else
 697       return 0;
 698   }
 699
 700   // if V is not a constant
 701   DSNode *DSN = TDG.getNodeForValue(V).getNode();
 702   if (!DSN) {
 703     return 0;
 704   }
 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);
 711   }
 712
 713   return 0;
 714 }
 715
 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))
 720     if (getFuncClass(V))
 721       return PAInfo.getFuncInfo(*fixedFunc)->Clone;
 722
 723   return 0;
 724 }
 725
 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(),
 731                                      "tmp", &RI);
 732       // Insert return instruction that returns the casted value
 733       ReturnInst *RetI = new ReturnInst(CastI, &RI);
 734
 735       // Remove original return instruction
 736       RI.getParent()->getInstList().erase(&RI);
 737
 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);
 745       }
 746     }
 747 }
 748
 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(),
 753                                    "tmp", &SI);
 754     StoreInst *StoreI = new StoreInst(CastI, SI.getOperand(1), &SI);
 755     SI.getParent()->getInstList().erase(&SI);
 756
 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);
 765     }
 766   }
 767 }
 768
 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
 773
 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));
 783       } else {
 784         V->addIncoming(PI.getIncomingValue(i), PI.getIncomingBlock(i));
 785       }
 786
 787     }
 788     PI.replaceAllUsesWith(V);
 789     PI.getParent()->getInstList().erase(&PI);
 790
 791     DSGraph::ScalarMapTy &SM = G.getScalarMap();
 792     DSGraph::ScalarMapTy::iterator PII = SM.find(&PI);
 793
 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
 799     } else {
 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);
 806     }
 807   }
 808 }
 809
 810 void FuncTransform::visitMallocInst(MallocInst &MI) {
 811   // Get the pool handle for the node that this contributes to...
 812   Value *PH = getPoolHandle(&MI);
 813
 814   // NB: PH is zero even if the node is collapsed
 815   if (PH == 0) return;
 816
 817   // Insert a call to poolalloc
 818   Value *V;
 819   if (MI.isArrayAllocation())
 820     V = new CallInst(PAInfo.PoolAllocArray,
 821                      make_vector(PH, MI.getOperand(0), 0),
 822                      MI.getName(), &MI);
 823   else
 824     V = new CallInst(PAInfo.PoolAlloc, make_vector(PH, 0),
 825                      MI.getName(), &MI);
 826
 827   MI.setName("");  // Nuke MIs name
 828
 829   Value *Casted = V;
 830
 831   // Cast to the appropriate type if necessary
 832   if (V->getType() != MI.getType()) {
 833     Casted = new CastInst(V, MI.getType(), V->getName(), &MI);
 834   }
 835
 836   // Update def-use info
 837   MI.replaceAllUsesWith(Casted);
 838
 839   // Remove old malloc instruction
 840   MI.getParent()->getInstList().erase(&MI);
 841
 842   DSGraph::ScalarMapTy &SM = G.getScalarMap();
 843   DSGraph::ScalarMapTy::iterator MII = SM.find(&MI);
 844
 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));
 849     if (V != Casted)
 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));
 857     if (V != Casted)
 858       FI.NewToOldValueMap.insert(std::make_pair(Casted, MII->second));
 859     FI.NewToOldValueMap.erase(MII);
 860   }
 861 }
 862
 863 void FuncTransform::visitFreeInst(FreeInst &FrI) {
 864   Value *Arg = FrI.getOperand(0);
 865   Value *PH = getPoolHandle(Arg);  // Get the pool handle for this DSNode...
 866   if (PH == 0) return;
 867   // Insert a cast and a call to poolfree...
 868   Value *Casted = Arg;
 869   if (Arg->getType() != PointerType::get(Type::SByteTy))
 870     Casted = new CastInst(Arg, PointerType::get(Type::SByteTy),
 871                                  Arg->getName()+".casted", &FrI);
 872
 873   CallInst *FreeI = new CallInst(PAInfo.PoolFree, make_vector(PH, Casted, 0),
 874                                  "", &FrI);
 875   // Delete the now obsolete free instruction...
 876   FrI.getParent()->getInstList().erase(&FrI);
 877
 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);
 886   }
 887 }
 888
 889 static void CalcNodeMapping(DSNodeHandle& Caller, DSNodeHandle& Callee,
 890                             std::map<DSNode*, DSNode*> &NodeMapping) {
 891   DSNode *CalleeNode = Callee.getNode();
 892   DSNode *CallerNode = Caller.getNode();
 893
 894   unsigned CalleeOffset = Callee.getOffset();
 895   unsigned CallerOffset = Caller.getOffset();
 896
 897   if (CalleeNode == 0) return;
 898
 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,
 903                                                          (DSNode *) 0));
 904   }
 905
 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?");
 913   } else {
 914     NodeMapping.insert(I, std::make_pair(CalleeNode, CallerNode));
 915
 916     if (CalleeNode->getType() != CallerNode->getType() && CallerOffset == 0)
 917       DEBUG(std::cerr << "NB: Mapping of nodes between different types\n");
 918
 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;
 925
 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);
 931       } else {
 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);
 934       }
 935     } else if (numCalleeLinks > 0) {
 936       DEBUG(std::cerr <<
 937             "Caller has unexpanded node, due to indirect call perhaps!\n");
 938     }
 939   }
 940 }
 941
 942 void FuncTransform::visitCallInst(CallInst &CI) {
 943   Function *CF = CI.getCalledFunction();
 944
 945   // optimization for function pointers that are basically gotten from a cast
 946   // with only one use and constant expressions with casts in them
 947   if (!CF) {
 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)))
 955           return;
 956         else
 957           assert(0 && "Function pointer cast not handled as called function\n");
 958       }
 959     }
 960
 961   }
 962
 963   DSGraph &CallerG = G;
 964
 965   std::vector<Value*> Args;
 966   if (!CF) {   // Indirect call
 967     DEBUG(std::cerr << "  Handling call: " << CI);
 968
 969     std::map<unsigned, Value*> PoolArgs;
 970     Function *FuncClass;
 971
 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))
 982           return;
 983       }
 984
 985       FuncInfo *CFI = PAInfo.getFuncInfo(*TFI->second);
 986
 987       if (!CFI->ArgNodes.size()) continue;  // Nothing to transform...
 988
 989       DSGraph &CG = PAInfo.getBUDataStructures().getDSGraph(*TFI->second);
 990       std::map<DSNode*, DSNode*> NodeMapping;
 991
 992       Function::aiterator AI = TFI->second->abegin(), AE = TFI->second->aend();
 993       unsigned OpNum = 1;
 994       for ( ; AI != AE; ++AI, ++OpNum) {
 995         if (!isa<Constant>(CI.getOperand(OpNum)))
 996           CalcNodeMapping(getDSNodeHFor(CI.getOperand(OpNum)),
 997                           CG.getScalarMap()[AI], NodeMapping);
 998       }
 999       assert(OpNum == CI.getNumOperands() && "Varargs calls not handled yet!");
1000
1001       if (CI.getType() != Type::VoidTy)
1002         CalcNodeMapping(getDSNodeHFor(&CI),
1003                         CG.getReturnNodeFor(*TFI->second), NodeMapping);
1004
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);
1012         }
1013
1014       unsigned idx = CFI->PoolArgFirst;
1015
1016       // The following loop determines the pool pointers corresponding to
1017       // CFI.
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;
1022           if (LocalNode) {
1023             assert(FI.PoolDescriptors.count(LocalNode) &&
1024                    "Node not pool allocated?");
1025             PoolArgs[idx] = FI.PoolDescriptors.find(LocalNode)->second;
1026           }
1027           else
1028             // LocalNode is null when a constant is passed in as a parameter
1029             PoolArgs[idx] = Constant::getNullValue(PoolDescPtr);
1030         } else {
1031           PoolArgs[idx] = Constant::getNullValue(PoolDescPtr);
1032         }
1033       }
1034     }
1035
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]);
1041         else
1042           Args.push_back(Constant::getNullValue(PoolDescPtr));
1043       }
1044
1045       assert(Args.size()== (unsigned) PAInfo.EqClass2LastPoolArg[FuncClass] + 1
1046              && "Call has same number of pool args as the called function");
1047     }
1048
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());
1051
1052     std::string Name = CI.getName();
1053
1054     Value *NewCall;
1055     if (Args.size() > CI.getNumOperands() - 1) {
1056       // If there are any pool arguments
1057       CastInst *CastI =
1058         new CastInst(CI.getOperand(0),
1059                      PAInfo.getFuncInfo(*FuncClass)->Clone->getType(), "tmp",
1060                      &CI);
1061       NewCall = new CallInst(CastI, Args, Name, &CI);
1062     } else {
1063       NewCall = new CallInst(CI.getOperand(0), Args, Name, &CI);
1064     }
1065
1066     CI.replaceAllUsesWith(NewCall);
1067     DEBUG(std::cerr << "  Result Call: " << *NewCall);
1068
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
1076       } else {
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);
1083       }
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);
1091     }
1092   }
1093   else {
1094
1095     FuncInfo *CFI = PAInfo.getFuncInfo(*CF);
1096
1097     if (CFI == 0 || CFI->Clone == 0) return;  // Nothing to transform...
1098
1099     DEBUG(std::cerr << "  Handling call: " << CI);
1100
1101     DSGraph &CG = PAInfo.getBUDataStructures().getDSGraph(*CF);  // Callee graph
1102
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.
1108     //
1109     std::map<DSNode*, DSNode*> NodeMapping;
1110
1111     Function::aiterator AI = CF->abegin(), AE = CF->aend();
1112     unsigned OpNum = 1;
1113     for (; AI != AE; ++AI, ++OpNum) {
1114       Value *callOp = CI.getOperand(OpNum);
1115       if (!isa<Constant>(callOp))
1116         CalcNodeMapping(getDSNodeHFor(callOp), CG.getScalarMap()[AI],
1117                         NodeMapping);
1118     }
1119     assert(OpNum == CI.getNumOperands() && "Varargs calls not handled yet!");
1120
1121     // Map the return value as well...
1122     if (CI.getType() != Type::VoidTy)
1123       CalcNodeMapping(getDSNodeHFor(&CI), CG.getReturnNodeFor(*CF),
1124                       NodeMapping);
1125
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);
1133       }
1134
1135     // Okay, now that we have established our mapping, we can figure out which
1136     // pool descriptors to pass in...
1137
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));
1142     }
1143
1144     for (unsigned i = 0, e = CFI->ArgNodes.size(); i != e; ++i) {
1145       if (NodeMapping.count(CFI->ArgNodes[i])) {
1146
1147         DSNode *LocalNode = NodeMapping.find(CFI->ArgNodes[i])->second;
1148         if (LocalNode) {
1149           assert(FI.PoolDescriptors.count(LocalNode) &&
1150                  "Node not pool allocated?");
1151           Args.push_back(FI.PoolDescriptors.find(LocalNode)->second);
1152         } else
1153           Args.push_back(Constant::getNullValue(PoolDescPtr));
1154       } else {
1155         Args.push_back(Constant::getNullValue(PoolDescPtr));
1156       }
1157     }
1158
1159     Function *FuncClass = PAInfo.FuncECs.findClass(CF);
1160
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));
1165
1166     // Add the rest of the arguments...
1167     Args.insert(Args.end(), CI.op_begin()+1, CI.op_end());
1168
1169     std::string Name = CI.getName();
1170
1171     std::map<Value*,const Value*>::iterator CNewII;
1172
1173     Value *NewCall = new CallInst(CFI->Clone, Args, Name, &CI);
1174
1175     CI.replaceAllUsesWith(NewCall);
1176     DEBUG(std::cerr << "  Result Call: " << *NewCall);
1177
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
1185       } else {
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);
1193       }
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);
1200     }
1201   }
1202
1203   CI.getParent()->getInstList().erase(&CI);
1204 }