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 #include "llvm/Transforms/PoolAllocate.h"
   9 #include "llvm/Transforms/Utils/Cloning.h"
  10 #include "llvm/Analysis/DataStructure.h"
  11 #include "llvm/Analysis/DSGraph.h"
  12 #include "llvm/Module.h"
  13 #include "llvm/DerivedTypes.h"
  14 #include "llvm/Constants.h"
  15 #include "llvm/Instructions.h"
  16 #include "llvm/Target/TargetData.h"
  17 #include "llvm/Support/InstVisitor.h"
  18 #include "Support/Statistic.h"
  19 #include "Support/VectorExtras.h"
  20 using namespace PA;
  21
  22 namespace {
  23   const Type *VoidPtrTy = PointerType::get(Type::SByteTy);
  24
  25   // The type to allocate for a pool descriptor: { sbyte*, uint, uint }
  26   // void *Data (the data)
  27   // unsigned NodeSize  (size of an allocated node)
  28   // unsigned FreeablePool (are slabs in the pool freeable upon calls to
  29   //                        poolfree?)
  30   const Type *PoolDescType =
  31   StructType::get(make_vector<const Type*>(VoidPtrTy, Type::UIntTy,
  32                                            Type::UIntTy, 0));
  33
  34   const PointerType *PoolDescPtr = PointerType::get(PoolDescType);
  35
  36   RegisterOpt<PoolAllocate>
  37   X("poolalloc", "Pool allocate disjoint data structures");
  38 }
  39
  40 void PoolAllocate::getAnalysisUsage(AnalysisUsage &AU) const {
  41   AU.addRequired<BUDataStructures>();
  42   AU.addRequired<TDDataStructures>();
  43   AU.addRequired<TargetData>();
  44 }
  45
  46 // Prints out the functions mapped to the leader of the equivalence class they
  47 // belong to.
  48 void PoolAllocate::printFuncECs() {
  49   std::map<Function*, Function*> &leaderMap = FuncECs.getLeaderMap();
  50   std::cerr << "Indirect Function Map \n";
  51   for (std::map<Function*, Function*>::iterator LI = leaderMap.begin(),
  52          LE = leaderMap.end(); LI != LE; ++LI) {
  53     std::cerr << LI->first->getName() << ": leader is "
  54               << LI->second->getName() << "\n";
  55   }
  56 }
  57
  58 void PoolAllocate::buildIndirectFunctionSets(Module &M) {
  59   // Iterate over the module looking for indirect calls to functions
  60
  61   // Get top down DSGraph for the functions
  62   TDDS = &getAnalysis<TDDataStructures>();
  63
  64   for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
  65
  66     DEBUG(std::cerr << "Processing indirect calls function:" <<  MI->getName() << "\n");
  67
  68     if (MI->isExternal())
  69       continue;
  70
  71     DSGraph &TDG = TDDS->getDSGraph(*MI);
  72
  73     std::vector<DSCallSite> callSites = TDG.getFunctionCalls();
  74
  75     // For each call site in the function
  76     // All the functions that can be called at the call site are put in the
  77     // same equivalence class.
  78     for (std::vector<DSCallSite>::iterator CSI = callSites.begin(),
  79            CSE = callSites.end(); CSI != CSE ; ++CSI) {
  80       if (CSI->isIndirectCall()) {
  81         DSNode *DSN = CSI->getCalleeNode();
  82         if (DSN->isIncomplete())
  83           std::cerr << "Incomplete node " << CSI->getCallInst();
  84         // assert(DSN->isGlobalNode());
  85         const std::vector<GlobalValue*> &Callees = DSN->getGlobals();
  86         if (Callees.size() > 0) {
  87           Function *firstCalledF = dyn_cast<Function>(*Callees.begin());
  88           FuncECs.addElement(firstCalledF);
  89           CallInstTargets.insert(std::pair<CallInst*,Function*>
  90                                  (&CSI->getCallInst(),
  91                                   firstCalledF));
  92           if (Callees.size() > 1) {
  93             for (std::vector<GlobalValue*>::const_iterator CalleesI =
  94                    Callees.begin()+1, CalleesE = Callees.end();
  95                  CalleesI != CalleesE; ++CalleesI) {
  96               Function *calledF = dyn_cast<Function>(*CalleesI);
  97               FuncECs.unionSetsWith(firstCalledF, calledF);
  98               CallInstTargets.insert(std::pair<CallInst*,Function*>
  99                                      (&CSI->getCallInst(), calledF));
 100             }
 101           }
 102         } else {
 103           std::cerr << "No targets " << CSI->getCallInst();
 104         }
 105       }
 106     }
 107   }
 108
 109   // Print the equivalence classes
 110   DEBUG(printFuncECs());
 111 }
 112
 113 bool PoolAllocate::run(Module &M) {
 114   if (M.begin() == M.end()) return false;
 115   CurModule = &M;
 116
 117   AddPoolPrototypes();
 118   BU = &getAnalysis<BUDataStructures>();
 119
 120   buildIndirectFunctionSets(M);
 121
 122   std::map<Function*, Function*> FuncMap;
 123
 124    // Loop over the functions in the original program finding the pool desc.
 125   // arguments necessary for each function that is indirectly callable.
 126   // For each equivalence class, make a list of pool arguments and update
 127   // the PoolArgFirst and PoolArgLast values for each function.
 128   Module::iterator LastOrigFunction = --M.end();
 129   for (Module::iterator I = M.begin(); ; ++I) {
 130     if (!I->isExternal())
 131       FindFunctionPoolArgs(*I);
 132     if (I == LastOrigFunction) break;
 133   }
 134
 135   // Now clone a function using the pool arg list obtained in the previous
 136   // pass over the modules.
 137   // Loop over only the function initially in the program, don't traverse newly
 138   // added ones.  If the function uses memory, make its clone.
 139   for (Module::iterator I = M.begin(); ; ++I) {
 140     if (!I->isExternal())
 141       if (Function *R = MakeFunctionClone(*I))
 142         FuncMap[I] = R;
 143     if (I == LastOrigFunction) break;
 144   }
 145
 146   ++LastOrigFunction;
 147
 148   // Now that all call targets are available, rewrite the function bodies of the
 149   // clones.
 150   for (Module::iterator I = M.begin(); I != LastOrigFunction; ++I)
 151     if (!I->isExternal()) {
 152       std::map<Function*, Function*>::iterator FI = FuncMap.find(I);
 153       ProcessFunctionBody(*I, FI != FuncMap.end() ? *FI->second : *I);
 154     }
 155
 156   return true;
 157 }
 158
 159
 160 // AddPoolPrototypes - Add prototypes for the pool functions to the specified
 161 // module and update the Pool* instance variables to point to them.
 162 //
 163 void PoolAllocate::AddPoolPrototypes() {
 164   CurModule->addTypeName("PoolDescriptor", PoolDescType);
 165
 166   // Get poolinit function...
 167   FunctionType *PoolInitTy =
 168     FunctionType::get(Type::VoidTy,
 169                       make_vector<const Type*>(PoolDescPtr, Type::UIntTy, 0),
 170                       false);
 171   PoolInit = CurModule->getOrInsertFunction("poolinit", PoolInitTy);
 172
 173   // Get pooldestroy function...
 174   std::vector<const Type*> PDArgs(1, PoolDescPtr);
 175   FunctionType *PoolDestroyTy =
 176     FunctionType::get(Type::VoidTy, PDArgs, false);
 177   PoolDestroy = CurModule->getOrInsertFunction("pooldestroy", PoolDestroyTy);
 178
 179   // Get the poolalloc function...
 180   FunctionType *PoolAllocTy = FunctionType::get(VoidPtrTy, PDArgs, false);
 181   PoolAlloc = CurModule->getOrInsertFunction("poolalloc", PoolAllocTy);
 182
 183   // Get the poolfree function...
 184   PDArgs.push_back(VoidPtrTy);       // Pointer to free
 185   FunctionType *PoolFreeTy = FunctionType::get(Type::VoidTy, PDArgs, false);
 186   PoolFree = CurModule->getOrInsertFunction("poolfree", PoolFreeTy);
 187
 188   // The poolallocarray function
 189   FunctionType *PoolAllocArrayTy =
 190     FunctionType::get(VoidPtrTy,
 191                       make_vector<const Type*>(PoolDescPtr, Type::UIntTy, 0),
 192                       false);
 193   PoolAllocArray = CurModule->getOrInsertFunction("poolallocarray",
 194                                                   PoolAllocArrayTy);
 195
 196 }
 197
 198 void PoolAllocate::FindFunctionPoolArgs(Function &F) {
 199   DSGraph &G = BU->getDSGraph(F);
 200   std::vector<DSNode*> &Nodes = G.getNodes();
 201   if (Nodes.empty()) return ;  // No memory activity, nothing is required
 202
 203   FuncInfo &FI = FunctionInfo[&F];   // Create a new entry for F
 204
 205   FI.Clone = 0;
 206
 207   // Initialize the PoolArgFirst and PoolArgLast for the function depending
 208   // on whether there have been other functions in the equivalence class
 209   // that have pool arguments so far in the analysis.
 210   if (!FuncECs.findClass(&F)) {
 211     FI.PoolArgFirst = FI.PoolArgLast = 0;
 212   } else {
 213     if (EqClass2LastPoolArg.find(FuncECs.findClass(&F)) !=
 214         EqClass2LastPoolArg.end())
 215       FI.PoolArgFirst = FI.PoolArgLast =
 216         EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1;
 217     else
 218       FI.PoolArgFirst = FI.PoolArgLast = 0;
 219   }
 220
 221   // Find DataStructure nodes which are allocated in pools non-local to the
 222   // current function.  This set will contain all of the DSNodes which require
 223   // pools to be passed in from outside of the function.
 224   hash_set<DSNode*> &MarkedNodes = FI.MarkedNodes;
 225
 226   // Mark globals and incomplete nodes as live... (this handles arguments)
 227   if (F.getName() != "main")
 228     for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
 229       if ((Nodes[i]->isGlobalNode() || Nodes[i]->isIncomplete()) &&
 230           Nodes[i]->isHeapNode())
 231         Nodes[i]->markReachableNodes(MarkedNodes);
 232
 233   // Marked the returned node as alive...
 234   if (DSNode *RetNode = G.getReturnNodeFor(F).getNode())
 235     if (RetNode->isHeapNode())
 236       RetNode->markReachableNodes(MarkedNodes);
 237
 238   if (MarkedNodes.empty())   // We don't need to clone the function if there
 239     return;                  // are no incoming arguments to be added.
 240
 241   for (hash_set<DSNode*>::iterator I = MarkedNodes.begin(),
 242          E = MarkedNodes.end(); I != E; ++I)
 243     FI.PoolArgLast++;
 244
 245   if (FuncECs.findClass(&F)) {
 246     // Update the equivalence class last pool argument information
 247     // only if there actually were pool arguments to the function.
 248     // Also, there is no entry for the Eq. class in EqClass2LastPoolArg
 249     // if there are no functions in the equivalence class with pool arguments.
 250     if (FI.PoolArgLast != FI.PoolArgFirst)
 251       EqClass2LastPoolArg[FuncECs.findClass(&F)] = FI.PoolArgLast - 1;
 252   }
 253
 254 }
 255
 256 // MakeFunctionClone - If the specified function needs to be modified for pool
 257 // allocation support, make a clone of it, adding additional arguments as
 258 // neccesary, and return it.  If not, just return null.
 259 //
 260 Function *PoolAllocate::MakeFunctionClone(Function &F) {
 261
 262   DSGraph &G = BU->getDSGraph(F);
 263   std::vector<DSNode*> &Nodes = G.getNodes();
 264   if (Nodes.empty())
 265     return 0;
 266
 267   FuncInfo &FI = FunctionInfo[&F];
 268
 269   hash_set<DSNode*> &MarkedNodes = FI.MarkedNodes;
 270
 271   if (!FuncECs.findClass(&F)) {
 272     // Not in any equivalence class
 273
 274     if (MarkedNodes.empty())
 275       return 0;
 276   } else {
 277     // No need to clone if there are no pool arguments in any function in the
 278     // equivalence class
 279     if (!EqClass2LastPoolArg.count(FuncECs.findClass(&F)))
 280       return 0;
 281   }
 282
 283   // Figure out what the arguments are to be for the new version of the function
 284   const FunctionType *OldFuncTy = F.getFunctionType();
 285   std::vector<const Type*> ArgTys;
 286   if (!FuncECs.findClass(&F)) {
 287     ArgTys.reserve(OldFuncTy->getParamTypes().size() + MarkedNodes.size());
 288     FI.ArgNodes.reserve(MarkedNodes.size());
 289     for (hash_set<DSNode*>::iterator I = MarkedNodes.begin(),
 290            E = MarkedNodes.end(); I != E; ++I) {
 291       ArgTys.push_back(PoolDescPtr);      // Add the appropriate # of pool descs
 292       FI.ArgNodes.push_back(*I);
 293     }
 294     if (FI.ArgNodes.empty()) return 0;      // No nodes to be pool allocated!
 295
 296   }
 297   else {
 298     // This function is a member of an equivalence class and needs to be cloned
 299     ArgTys.reserve(OldFuncTy->getParamTypes().size() +
 300                    EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1);
 301     FI.ArgNodes.reserve(EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1);
 302
 303     for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i) {
 304       ArgTys.push_back(PoolDescPtr);      // Add the appropriate # of pool
 305                                           // descs
 306     }
 307
 308     for (hash_set<DSNode*>::iterator I = MarkedNodes.begin(),
 309            E = MarkedNodes.end(); I != E; ++I) {
 310       FI.ArgNodes.push_back(*I);
 311     }
 312
 313     assert ((FI.ArgNodes.size() == (unsigned) (FI.PoolArgLast -
 314                                                FI.PoolArgFirst)) &&
 315             "Number of ArgNodes equal to the number of pool arguments used by this function");
 316   }
 317
 318
 319   ArgTys.insert(ArgTys.end(), OldFuncTy->getParamTypes().begin(),
 320                 OldFuncTy->getParamTypes().end());
 321
 322
 323   // Create the new function prototype
 324   FunctionType *FuncTy = FunctionType::get(OldFuncTy->getReturnType(), ArgTys,
 325                                            OldFuncTy->isVarArg());
 326   // Create the new function...
 327   Function *New = new Function(FuncTy, GlobalValue::InternalLinkage,
 328                                F.getName(), F.getParent());
 329
 330   // Set the rest of the new arguments names to be PDa<n> and add entries to the
 331   // pool descriptors map
 332   std::map<DSNode*, Value*> &PoolDescriptors = FI.PoolDescriptors;
 333   Function::aiterator NI = New->abegin();
 334
 335   if (FuncECs.findClass(&F)) {
 336     for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i,
 337            ++NI)
 338       NI->setName("PDa");
 339
 340     NI = New->abegin();
 341     if (FI.PoolArgFirst > 0)
 342       for (int i = 0; i < FI.PoolArgFirst; ++NI, ++i)
 343         ;
 344
 345     if (FI.ArgNodes.size() > 0)
 346       for (unsigned i = 0, e = FI.ArgNodes.size(); i != e; ++i, ++NI)
 347         PoolDescriptors.insert(std::make_pair(FI.ArgNodes[i], NI));
 348
 349     NI = New->abegin();
 350     if (EqClass2LastPoolArg.count(FuncECs.findClass(&F)))
 351       for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i, ++NI)
 352         ;
 353   } else {
 354     if (FI.ArgNodes.size())
 355       for (unsigned i = 0, e = FI.ArgNodes.size(); i != e; ++i, ++NI) {
 356         NI->setName("PDa");  // Add pd entry
 357         PoolDescriptors.insert(std::make_pair(FI.ArgNodes[i], NI));
 358       }
 359     NI = New->abegin();
 360     if (FI.ArgNodes.size())
 361       for (unsigned i = 0; i < FI.ArgNodes.size(); ++NI, ++i)
 362         ;
 363   }
 364
 365   // Map the existing arguments of the old function to the corresponding
 366   // arguments of the new function.
 367   std::map<const Value*, Value*> ValueMap;
 368   if (NI != New->aend())
 369     for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I, ++NI) {
 370       ValueMap[I] = NI;
 371       NI->setName(I->getName());
 372     }
 373
 374   // Populate the value map with all of the globals in the program.
 375   // FIXME: This should be unneccesary!
 376   Module &M = *F.getParent();
 377   for (Module::iterator I = M.begin(), E=M.end(); I!=E; ++I)    ValueMap[I] = I;
 378   for (Module::giterator I = M.gbegin(), E=M.gend(); I!=E; ++I) ValueMap[I] = I;
 379
 380   // Perform the cloning.
 381   std::vector<ReturnInst*> Returns;
 382   CloneFunctionInto(New, &F, ValueMap, Returns);
 383
 384   // Invert the ValueMap into the NewToOldValueMap
 385   std::map<Value*, const Value*> &NewToOldValueMap = FI.NewToOldValueMap;
 386   for (std::map<const Value*, Value*>::iterator I = ValueMap.begin(),
 387          E = ValueMap.end(); I != E; ++I)
 388     NewToOldValueMap.insert(std::make_pair(I->second, I->first));
 389
 390   return FI.Clone = New;
 391 }
 392
 393
 394 // processFunction - Pool allocate any data structures which are contained in
 395 // the specified function...
 396 //
 397 void PoolAllocate::ProcessFunctionBody(Function &F, Function &NewF) {
 398   DSGraph &G = BU->getDSGraph(F);
 399   std::vector<DSNode*> &Nodes = G.getNodes();
 400   if (Nodes.empty()) return;     // Quick exit if nothing to do...
 401
 402   FuncInfo &FI = FunctionInfo[&F];   // Get FuncInfo for F
 403   hash_set<DSNode*> &MarkedNodes = FI.MarkedNodes;
 404
 405   DEBUG(std::cerr << "[" << F.getName() << "] Pool Allocate: ");
 406
 407   // Loop over all of the nodes which are non-escaping, adding pool-allocatable
 408   // ones to the NodesToPA vector.
 409   std::vector<DSNode*> NodesToPA;
 410   for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
 411     if (Nodes[i]->isHeapNode() &&   // Pick nodes with heap elems
 412         !MarkedNodes.count(Nodes[i]))              // Can't be marked
 413       NodesToPA.push_back(Nodes[i]);
 414
 415   DEBUG(std::cerr << NodesToPA.size() << " nodes to pool allocate\n");
 416   if (!NodesToPA.empty()) {
 417     // Create pool construction/destruction code
 418     std::map<DSNode*, Value*> &PoolDescriptors = FI.PoolDescriptors;
 419     CreatePools(NewF, NodesToPA, PoolDescriptors);
 420   }
 421
 422   // Transform the body of the function now...
 423   TransformFunctionBody(NewF, F, G, FI);
 424 }
 425
 426
 427 // CreatePools - This creates the pool initialization and destruction code for
 428 // the DSNodes specified by the NodesToPA list.  This adds an entry to the
 429 // PoolDescriptors map for each DSNode.
 430 //
 431 void PoolAllocate::CreatePools(Function &F,
 432                                const std::vector<DSNode*> &NodesToPA,
 433                                std::map<DSNode*, Value*> &PoolDescriptors) {
 434   // Find all of the return nodes in the CFG...
 435   std::vector<BasicBlock*> ReturnNodes;
 436   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 437     if (isa<ReturnInst>(I->getTerminator()))
 438       ReturnNodes.push_back(I);
 439
 440   TargetData &TD = getAnalysis<TargetData>();
 441
 442   // Loop over all of the pools, inserting code into the entry block of the
 443   // function for the initialization and code in the exit blocks for
 444   // destruction.
 445   //
 446   Instruction *InsertPoint = F.front().begin();
 447   for (unsigned i = 0, e = NodesToPA.size(); i != e; ++i) {
 448     DSNode *Node = NodesToPA[i];
 449
 450     // Create a new alloca instruction for the pool...
 451     Value *AI = new AllocaInst(PoolDescType, 0, "PD", InsertPoint);
 452
 453     Value *ElSize;
 454
 455     // Void types in DS graph are never used
 456     if (Node->getType() != Type::VoidTy)
 457       ElSize = ConstantUInt::get(Type::UIntTy, TD.getTypeSize(Node->getType()));
 458     else
 459       ElSize = ConstantUInt::get(Type::UIntTy, 0);
 460
 461     // Insert the call to initialize the pool...
 462     new CallInst(PoolInit, make_vector(AI, ElSize, 0), "", InsertPoint);
 463
 464     // Update the PoolDescriptors map
 465     PoolDescriptors.insert(std::make_pair(Node, AI));
 466
 467     // Insert a call to pool destroy before each return inst in the function
 468     for (unsigned r = 0, e = ReturnNodes.size(); r != e; ++r)
 469       new CallInst(PoolDestroy, make_vector(AI, 0), "",
 470                    ReturnNodes[r]->getTerminator());
 471   }
 472 }
 473
 474
 475 namespace {
 476   /// FuncTransform - This class implements transformation required of pool
 477   /// allocated functions.
 478   struct FuncTransform : public InstVisitor<FuncTransform> {
 479     PoolAllocate &PAInfo;
 480     DSGraph &G;
 481     DSGraph &TDG;
 482     FuncInfo &FI;
 483
 484     FuncTransform(PoolAllocate &P, DSGraph &g, DSGraph &tdg, FuncInfo &fi)
 485       : PAInfo(P), G(g), TDG(tdg), FI(fi) {
 486     }
 487
 488     void visitMallocInst(MallocInst &MI);
 489     void visitFreeInst(FreeInst &FI);
 490     void visitCallInst(CallInst &CI);
 491
 492     // The following instructions are never modified by pool allocation
 493     void visitBranchInst(BranchInst &I) { }
 494     void visitBinaryOperator(Instruction &I) { }
 495     void visitShiftInst (ShiftInst &I) { }
 496     void visitSwitchInst (SwitchInst &I) { }
 497     void visitCastInst (CastInst &I) { }
 498     void visitAllocaInst(AllocaInst &I) { }
 499     void visitLoadInst(LoadInst &I) { }
 500     void visitGetElementPtrInst (GetElementPtrInst &I) { }
 501
 502     void visitReturnInst(ReturnInst &I);
 503     void visitStoreInst (StoreInst &I);
 504     void visitPHINode(PHINode &I);
 505
 506     void visitInstruction(Instruction &I) {
 507       std::cerr << "PoolAllocate does not recognize this instruction\n";
 508       abort();
 509     }
 510
 511   private:
 512     DSNode *getDSNodeFor(Value *V) {
 513       if (isa<Constant>(V))
 514         return 0;
 515
 516       if (!FI.NewToOldValueMap.empty()) {
 517         // If the NewToOldValueMap is in effect, use it.
 518         std::map<Value*,const Value*>::iterator I = FI.NewToOldValueMap.find(V);
 519         if (I != FI.NewToOldValueMap.end())
 520           V = (Value*)I->second;
 521       }
 522
 523       return G.getScalarMap()[V].getNode();
 524     }
 525     Value *getPoolHandle(Value *V) {
 526       DSNode *Node = getDSNodeFor(V);
 527       // Get the pool handle for this DSNode...
 528       std::map<DSNode*, Value*>::iterator I = FI.PoolDescriptors.find(Node);
 529       return I != FI.PoolDescriptors.end() ? I->second : 0;
 530     }
 531
 532     bool isFuncPtr(Value *V);
 533
 534     Function* getFuncClass(Value *V);
 535
 536     Value* retCloneIfFunc(Value *V);
 537   };
 538 }
 539
 540 void PoolAllocate::TransformFunctionBody(Function &F, Function &OldF,
 541                                          DSGraph &G, FuncInfo &FI) {
 542   FuncTransform(*this, G, TDDS->getDSGraph(OldF), FI).visit(F);
 543 }
 544
 545 // Returns true if V is a function pointer
 546 bool FuncTransform::isFuncPtr(Value *V) {
 547   if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
 548      return isa<FunctionType>(PTy->getElementType());
 549   return false;
 550 }
 551
 552 // Given a function pointer, return the function eq. class if one exists
 553 Function* FuncTransform::getFuncClass(Value *V) {
 554   // Look at DSGraph and see if the set of of functions it could point to
 555   // are pool allocated.
 556
 557   if (!isFuncPtr(V))
 558     return 0;
 559
 560   // Two cases:
 561   // if V is a constant
 562   if (Function *theFunc = dyn_cast<Function>(V)) {
 563     if (!PAInfo.FuncECs.findClass(theFunc))
 564       // If this function does not belong to any equivalence class
 565       return 0;
 566     if (PAInfo.EqClass2LastPoolArg.count(PAInfo.FuncECs.findClass(theFunc)))
 567       return PAInfo.FuncECs.findClass(theFunc);
 568     else
 569       return 0;
 570   }
 571
 572   // if V is not a constant
 573   DSNode *DSN = TDG.getNodeForValue(V).getNode();
 574   if (!DSN) {
 575     return 0;
 576   }
 577   const std::vector<GlobalValue*> &Callees = DSN->getGlobals();
 578   if (Callees.size() > 0) {
 579     Function *calledF = dyn_cast<Function>(*Callees.begin());
 580     assert(PAInfo.FuncECs.findClass(calledF) && "should exist in some eq. class");
 581     if (PAInfo.EqClass2LastPoolArg.count(PAInfo.FuncECs.findClass(calledF)))
 582       return PAInfo.FuncECs.findClass(calledF);
 583   }
 584
 585   return 0;
 586 }
 587
 588 // Returns the clone if  V is a static function (not a pointer) and belongs
 589 // to an equivalence class i.e. is pool allocated
 590 Value* FuncTransform::retCloneIfFunc(Value *V) {
 591   if (Function *fixedFunc = dyn_cast<Function>(V))
 592     if (getFuncClass(V))
 593       return PAInfo.getFuncInfo(*fixedFunc)->Clone;
 594
 595   return 0;
 596 }
 597
 598 void FuncTransform::visitReturnInst (ReturnInst &I) {
 599   if (I.getNumOperands())
 600     if (Value *clonedFunc = retCloneIfFunc(I.getOperand(0))) {
 601       // Cast the clone of I.getOperand(0) to the non-pool-allocated type
 602       CastInst *CastI = new CastInst(clonedFunc, I.getOperand(0)->getType(),
 603                                      "tmp", &I);
 604       // Insert return instruction that returns the casted value
 605       new ReturnInst(CastI, &I);
 606
 607       // Remove original return instruction
 608       I.getParent()->getInstList().erase(&I);
 609     }
 610 }
 611
 612 void FuncTransform::visitStoreInst (StoreInst &I) {
 613   // Check if a constant function is being stored
 614   if (Value *clonedFunc = retCloneIfFunc(I.getOperand(0))) {
 615     CastInst *CastI = new CastInst(clonedFunc, I.getOperand(0)->getType(),
 616                                    "tmp", &I);
 617     new StoreInst(CastI, I.getOperand(1), &I);
 618     I.getParent()->getInstList().erase(&I);
 619   }
 620 }
 621
 622 void FuncTransform::visitPHINode(PHINode &I) {
 623   // If any of the operands of the PHI node is a constant function pointer
 624   // that is cloned, the cast instruction has to be inserted at the end of the
 625   // previous basic block
 626
 627   if (isFuncPtr(&I)) {
 628     PHINode *V = new PHINode(I.getType(), I.getName(), &I);
 629     for (unsigned i = 0 ; i < I.getNumIncomingValues(); ++i) {
 630       if (Value *clonedFunc = retCloneIfFunc(I.getIncomingValue(i))) {
 631         // Insert CastInst at the end of  I.getIncomingBlock(i)
 632         BasicBlock::iterator BBI = --I.getIncomingBlock(i)->end();
 633         // BBI now points to the terminator instruction of the basic block.
 634         CastInst *CastI = new CastInst(clonedFunc, I.getType(), "tmp", BBI);
 635         V->addIncoming(CastI, I.getIncomingBlock(i));
 636       } else {
 637         V->addIncoming(I.getIncomingValue(i), I.getIncomingBlock(i));
 638       }
 639
 640     }
 641     I.replaceAllUsesWith(V);
 642     I.getParent()->getInstList().erase(&I);
 643   }
 644 }
 645
 646 void FuncTransform::visitMallocInst(MallocInst &MI) {
 647   // Get the pool handle for the node that this contributes to...
 648   Value *PH = getPoolHandle(&MI);
 649   if (PH == 0) return;
 650
 651   // Insert a call to poolalloc
 652   Value *V;
 653   if (MI.isArrayAllocation())
 654     V = new CallInst(PAInfo.PoolAllocArray,
 655                      make_vector(PH, MI.getOperand(0), 0),
 656                      MI.getName(), &MI);
 657   else
 658     V = new CallInst(PAInfo.PoolAlloc, make_vector(PH, 0),
 659                      MI.getName(), &MI);
 660
 661   MI.setName("");  // Nuke MIs name
 662
 663   // Cast to the appropriate type...
 664   Value *Casted = new CastInst(V, MI.getType(), V->getName(), &MI);
 665
 666   // Update def-use info
 667   MI.replaceAllUsesWith(Casted);
 668
 669   // Remove old malloc instruction
 670   MI.getParent()->getInstList().erase(&MI);
 671
 672   DSGraph::ScalarMapTy &SM = G.getScalarMap();
 673   DSGraph::ScalarMapTy::iterator MII = SM.find(&MI);
 674
 675   // If we are modifying the original function, update the DSGraph...
 676   if (MII != SM.end()) {
 677     // V and Casted now point to whatever the original malloc did...
 678     SM.insert(std::make_pair(V, MII->second));
 679     SM.insert(std::make_pair(Casted, MII->second));
 680     SM.erase(MII);                     // The malloc is now destroyed
 681   } else {             // Otherwise, update the NewToOldValueMap
 682     std::map<Value*,const Value*>::iterator MII =
 683       FI.NewToOldValueMap.find(&MI);
 684     assert(MII != FI.NewToOldValueMap.end() && "MI not found in clone?");
 685     FI.NewToOldValueMap.insert(std::make_pair(V, MII->second));
 686     FI.NewToOldValueMap.insert(std::make_pair(Casted, MII->second));
 687     FI.NewToOldValueMap.erase(MII);
 688   }
 689 }
 690
 691 void FuncTransform::visitFreeInst(FreeInst &FI) {
 692   Value *Arg = FI.getOperand(0);
 693   Value *PH = getPoolHandle(Arg);  // Get the pool handle for this DSNode...
 694   if (PH == 0) return;
 695   // Insert a cast and a call to poolfree...
 696   Value *Casted = new CastInst(Arg, PointerType::get(Type::SByteTy),
 697                                Arg->getName()+".casted", &FI);
 698   new CallInst(PAInfo.PoolFree, make_vector(PH, Casted, 0), "", &FI);
 699
 700   // Delete the now obsolete free instruction...
 701   FI.getParent()->getInstList().erase(&FI);
 702 }
 703
 704 static void CalcNodeMapping(DSNode *Caller, DSNode *Callee,
 705                             std::map<DSNode*, DSNode*> &NodeMapping) {
 706   if (Callee == 0) return;
 707   // assert(Caller && "Callee has node but caller doesn't??");
 708
 709   // If callee has a node and caller doesn't, then a constant argument was
 710   // passed by the caller
 711   if (Caller == 0) {
 712     NodeMapping.insert(NodeMapping.end(), std::make_pair(Callee, (DSNode*) 0));
 713   }
 714
 715   std::map<DSNode*, DSNode*>::iterator I = NodeMapping.find(Callee);
 716   if (I != NodeMapping.end()) {   // Node already in map...
 717     assert(I->second == Caller && "Node maps to different nodes on paths?");
 718   } else {
 719     NodeMapping.insert(I, std::make_pair(Callee, Caller));
 720
 721     // Recursively add pointed to nodes...
 722     unsigned numCallerLinks = Caller->getNumLinks();
 723     unsigned numCalleeLinks = Callee->getNumLinks();
 724
 725     assert (numCallerLinks <= numCalleeLinks || numCalleeLinks == 0);
 726
 727     for (unsigned i = 0, e = numCalleeLinks; i != e; ++i)
 728       CalcNodeMapping(Caller->getLink((i%numCallerLinks) << DS::PointerShift).getNode(), Callee->getLink(i << DS::PointerShift).getNode(), NodeMapping);
 729   }
 730 }
 731
 732 void FuncTransform::visitCallInst(CallInst &CI) {
 733   Function *CF = CI.getCalledFunction();
 734
 735   // optimization for function pointers that are basically gotten from a cast
 736   // with only one use and constant expressions with casts in them
 737   if (!CF) {
 738     if (CastInst* CastI = dyn_cast<CastInst>(CI.getCalledValue())) {
 739       if (isa<Function>(CastI->getOperand(0)) &&
 740           CastI->getOperand(0)->getType() == CastI->getType())
 741         CF = dyn_cast<Function>(CastI->getOperand(0));
 742     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(CI.getOperand(0))) {
 743       if (CE->getOpcode() == Instruction::Cast) {
 744         if (isa<ConstantPointerRef>(CE->getOperand(0)))
 745           return;
 746         else
 747           assert(0 && "Function pointer cast not handled as called function\n");
 748       }
 749     }
 750
 751   }
 752
 753   std::vector<Value*> Args;
 754   if (!CF) {   // Indirect call
 755     DEBUG(std::cerr << "  Handling call: " << CI);
 756
 757     std::map<unsigned, Value*> PoolArgs;
 758     Function *FuncClass;
 759
 760     std::pair<std::multimap<CallInst*, Function*>::iterator,
 761               std::multimap<CallInst*, Function*>::iterator> Targets =
 762       PAInfo.CallInstTargets.equal_range(&CI);
 763     for (std::multimap<CallInst*, Function*>::iterator TFI = Targets.first,
 764            TFE = Targets.second; TFI != TFE; ++TFI) {
 765       if (TFI == Targets.first) {
 766         FuncClass = PAInfo.FuncECs.findClass(TFI->second);
 767         // Nothing to transform if there are no pool arguments in this
 768         // equivalence class of functions.
 769         if (!PAInfo.EqClass2LastPoolArg.count(FuncClass))
 770           return;
 771       }
 772
 773       FuncInfo *CFI = PAInfo.getFuncInfo(*TFI->second);
 774
 775       if (!CFI->ArgNodes.size()) continue;  // Nothing to transform...
 776
 777       DSGraph &CG = PAInfo.getBUDataStructures().getDSGraph(*TFI->second);
 778       std::map<DSNode*, DSNode*> NodeMapping;
 779
 780       Function::aiterator AI = TFI->second->abegin(), AE = TFI->second->aend();
 781       unsigned OpNum = 1;
 782       for ( ; AI != AE; ++AI, ++OpNum) {
 783         if (!isa<Constant>(CI.getOperand(OpNum)))
 784           CalcNodeMapping(getDSNodeFor(CI.getOperand(OpNum)),
 785                           CG.getScalarMap()[AI].getNode(),
 786                           NodeMapping);
 787       }
 788       assert(OpNum == CI.getNumOperands() && "Varargs calls not handled yet!");
 789
 790       if (CI.getType() != Type::VoidTy)
 791         CalcNodeMapping(getDSNodeFor(&CI),
 792                         CG.getReturnNodeFor(*TFI->second).getNode(),
 793                         NodeMapping);
 794
 795       unsigned idx = CFI->PoolArgFirst;
 796
 797       // The following loop determines the pool pointers corresponding to
 798       // CFI.
 799       for (unsigned i = 0, e = CFI->ArgNodes.size(); i != e; ++i, ++idx) {
 800         if (NodeMapping.count(CFI->ArgNodes[i])) {
 801           assert(NodeMapping.count(CFI->ArgNodes[i]) && "Node not in mapping!");
 802           DSNode *LocalNode = NodeMapping.find(CFI->ArgNodes[i])->second;
 803           if (LocalNode) {
 804             assert(FI.PoolDescriptors.count(LocalNode) && "Node not pool allocated?");
 805             PoolArgs[idx] = FI.PoolDescriptors.find(LocalNode)->second;
 806           }
 807           else
 808             // LocalNode is null when a constant is passed in as a parameter
 809             PoolArgs[idx] = Constant::getNullValue(PoolDescPtr);
 810         } else {
 811           PoolArgs[idx] = Constant::getNullValue(PoolDescPtr);
 812         }
 813       }
 814     }
 815
 816     // Push the pool arguments into Args.
 817     if (PAInfo.EqClass2LastPoolArg.count(FuncClass)) {
 818       for (int i = 0; i <= PAInfo.EqClass2LastPoolArg[FuncClass]; ++i) {
 819         if (PoolArgs.find(i) != PoolArgs.end())
 820           Args.push_back(PoolArgs[i]);
 821         else
 822           Args.push_back(Constant::getNullValue(PoolDescPtr));
 823       }
 824
 825       assert (Args.size()== (unsigned) PAInfo.EqClass2LastPoolArg[FuncClass] + 1
 826               && "Call has same number of pool args as the called function");
 827     }
 828
 829     // Add the rest of the arguments (the original arguments of the function)...
 830     Args.insert(Args.end(), CI.op_begin()+1, CI.op_end());
 831
 832     std::string Name = CI.getName();
 833
 834     Value *NewCall;
 835     if (Args.size() > CI.getNumOperands() - 1) {
 836       // If there are any pool arguments
 837       CastInst *CastI =
 838         new CastInst(CI.getOperand(0),
 839                      PAInfo.getFuncInfo(*FuncClass)->Clone->getType(), "tmp",
 840                      &CI);
 841       NewCall = new CallInst(CastI, Args, Name, &CI);
 842     } else {
 843       NewCall = new CallInst(CI.getOperand(0), Args, Name, &CI);
 844     }
 845
 846     CI.replaceAllUsesWith(NewCall);
 847     DEBUG(std::cerr << "  Result Call: " << *NewCall);
 848   }
 849   else {
 850
 851     FuncInfo *CFI = PAInfo.getFuncInfo(*CF);
 852
 853     if (CFI == 0 || CFI->Clone == 0) return;  // Nothing to transform...
 854
 855     DEBUG(std::cerr << "  Handling call: " << CI);
 856
 857     DSGraph &CG = PAInfo.getBUDataStructures().getDSGraph(*CF);  // Callee graph
 858
 859     // We need to figure out which local pool descriptors correspond to the pool
 860     // descriptor arguments passed into the function call.  Calculate a mapping
 861     // from callee DSNodes to caller DSNodes.  We construct a partial isomophism
 862     // between the graphs to figure out which pool descriptors need to be passed
 863     // in.  The roots of this mapping is found from arguments and return values.
 864     //
 865     std::map<DSNode*, DSNode*> NodeMapping;
 866
 867     Function::aiterator AI = CF->abegin(), AE = CF->aend();
 868     unsigned OpNum = 1;
 869     for (; AI != AE; ++AI, ++OpNum) {
 870       // Check if the operand of the call is a return of another call
 871       // for the operand will be transformed in which case.
 872       // Look up the OldToNewRetValMap to see if the operand is a new value.
 873       Value *callOp = CI.getOperand(OpNum);
 874       if (!isa<Constant>(callOp))
 875         CalcNodeMapping(getDSNodeFor(callOp),CG.getScalarMap()[AI].getNode(),
 876                         NodeMapping);
 877     }
 878     assert(OpNum == CI.getNumOperands() && "Varargs calls not handled yet!");
 879
 880     // Map the return value as well...
 881     if (CI.getType() != Type::VoidTy)
 882       CalcNodeMapping(getDSNodeFor(&CI), CG.getReturnNodeFor(*CF).getNode(),
 883                       NodeMapping);
 884
 885     // Okay, now that we have established our mapping, we can figure out which
 886     // pool descriptors to pass in...
 887
 888     // Add an argument for each pool which must be passed in...
 889     if (CFI->PoolArgFirst != 0) {
 890       for (int i = 0; i < CFI->PoolArgFirst; ++i)
 891         Args.push_back(Constant::getNullValue(PoolDescPtr));
 892     }
 893
 894     for (unsigned i = 0, e = CFI->ArgNodes.size(); i != e; ++i) {
 895       if (NodeMapping.count(CFI->ArgNodes[i])) {
 896         assert(NodeMapping.count(CFI->ArgNodes[i]) && "Node not in mapping!");
 897         DSNode *LocalNode = NodeMapping.find(CFI->ArgNodes[i])->second;
 898         if (LocalNode) {
 899           assert(FI.PoolDescriptors.count(LocalNode) && "Node not pool allocated?");
 900           Args.push_back(FI.PoolDescriptors.find(LocalNode)->second);
 901         }
 902         else
 903           Args.push_back(Constant::getNullValue(PoolDescPtr));
 904       } else {
 905         Args.push_back(Constant::getNullValue(PoolDescPtr));
 906       }
 907     }
 908
 909     Function *FuncClass = PAInfo.FuncECs.findClass(CF);
 910
 911     if (PAInfo.EqClass2LastPoolArg.count(FuncClass))
 912       for (unsigned i = CFI->PoolArgLast;
 913            i <= PAInfo.EqClass2LastPoolArg.count(FuncClass); ++i)
 914         Args.push_back(Constant::getNullValue(PoolDescPtr));
 915
 916     // Add the rest of the arguments...
 917     Args.insert(Args.end(), CI.op_begin()+1, CI.op_end());
 918
 919     std::string Name = CI.getName();
 920     Value *NewCall = new CallInst(CFI->Clone, Args, Name, &CI);
 921     CI.replaceAllUsesWith(NewCall);
 922     DEBUG(std::cerr << "  Result Call: " << *NewCall);
 923
 924   }
 925
 926   CI.getParent()->getInstList().erase(&CI);
 927 }