lib/Analysis/DataStructure/FunctionRepBuilder.cpp

   1 //===- FunctionRepBuilder.cpp - Build the local datastructure graph -------===//
   2 //
   3 // Build the local datastructure graph for a single method.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "FunctionRepBuilder.h"
   8 #include "llvm/Function.h"
   9 #include "llvm/BasicBlock.h"
  10 #include "llvm/iMemory.h"
  11 #include "llvm/iPHINode.h"
  12 #include "llvm/iOther.h"
  13 #include "llvm/iTerminators.h"
  14 #include "llvm/DerivedTypes.h"
  15 #include "llvm/ConstantVals.h"
  16 #include "Support/STLExtras.h"
  17 #include <algorithm>
  18
  19 // synthesizeNode - Create a new shadow node that is to be linked into this
  20 // chain..
  21 // FIXME: This should not take a FunctionRepBuilder as an argument!
  22 //
  23 ShadowDSNode *ShadowDSNode::synthesizeNode(const Type *Ty,
  24                                            FunctionRepBuilder *Rep) {
  25   // If we are a derived shadow node, defer to our parent to synthesize the node
  26   if (ShadowParent) return ShadowParent->synthesizeNode(Ty, Rep);
  27
  28   // See if we have already synthesized a node of this type...
  29   for (unsigned i = 0, e = SynthNodes.size(); i != e; ++i)
  30     if (SynthNodes[i].first == Ty) return SynthNodes[i].second;
  31
  32   // No we haven't.  Do so now and add it to our list of saved nodes...
  33   ShadowDSNode *SN = new ShadowDSNode(Ty, Mod, this);
  34   SynthNodes.push_back(make_pair(Ty, SN));
  35   Rep->addShadowNode(SN);
  36   return SN;
  37 }
  38
  39
  40
  41
  42 // visitOperand - If the specified instruction operand is a global value, add
  43 // a node for it...
  44 //
  45 void InitVisitor::visitOperand(Value *V) {
  46   if (!Rep->ValueMap.count(V))                  // Only process it once...
  47     if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
  48       GlobalDSNode *N = new GlobalDSNode(GV);
  49       Rep->GlobalNodes.push_back(N);
  50       Rep->ValueMap[V].add(N);
  51       Rep->addAllUsesToWorkList(GV);
  52
  53       // FIXME: If the global variable has fields, we should add critical
  54       // shadow nodes to represent them!
  55     }
  56 }
  57
  58
  59 // visitCallInst - Create a call node for the callinst, and create as shadow
  60 // node if the call returns a pointer value.  Check to see if the call node
  61 // uses any global variables...
  62 //
  63 void InitVisitor::visitCallInst(CallInst *CI) {
  64   CallDSNode *C = new CallDSNode(CI);
  65   Rep->CallNodes.push_back(C);
  66   Rep->CallMap[CI] = C;
  67
  68   if (PointerType *PT = dyn_cast<PointerType>(CI->getType())) {
  69     // Create a critical shadow node to represent the memory object that the
  70     // return value points to...
  71     ShadowDSNode *Shad = new ShadowDSNode(PT->getElementType(),
  72                                           Func->getParent(), true);
  73     Rep->ShadowNodes.push_back(Shad);
  74
  75     // The return value of the function is a pointer to the shadow value
  76     // just created...
  77     //
  78     C->getLink(0).add(Shad);
  79
  80     // The call instruction returns a pointer to the shadow block...
  81     Rep->ValueMap[CI].add(Shad, CI);
  82
  83     // If the call returns a value with pointer type, add all of the users
  84     // of the call instruction to the work list...
  85     Rep->addAllUsesToWorkList(CI);
  86   }
  87
  88   // Loop over all of the operands of the call instruction (except the first
  89   // one), to look for global variable references...
  90   //
  91   for_each(CI->op_begin()+1, CI->op_end(),   // Skip first arg
  92            bind_obj(this, &InitVisitor::visitOperand));
  93 }
  94
  95
  96 // visitAllocationInst - Create an allocation node for the allocation.  Since
  97 // allocation instructions do not take pointer arguments, they cannot refer to
  98 // global vars...
  99 //
 100 void InitVisitor::visitAllocationInst(AllocationInst *AI) {
 101   AllocDSNode *N = new AllocDSNode(AI);
 102   Rep->AllocNodes.push_back(N);
 103
 104   Rep->ValueMap[AI].add(N, AI);
 105
 106   // Add all of the users of the malloc instruction to the work list...
 107   Rep->addAllUsesToWorkList(AI);
 108 }
 109
 110
 111 // Visit all other instruction types.  Here we just scan, looking for uses of
 112 // global variables...
 113 //
 114 void InitVisitor::visitInstruction(Instruction *I) {
 115   for_each(I->op_begin(), I->op_end(),
 116            bind_obj(this, &InitVisitor::visitOperand));
 117 }
 118
 119
 120 // addAllUsesToWorkList - Add all of the instructions users of the specified
 121 // value to the work list for further processing...
 122 //
 123 void FunctionRepBuilder::addAllUsesToWorkList(Value *V) {
 124   //cerr << "Adding all uses of " << V << "\n";
 125   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) {
 126     Instruction *Inst = cast<Instruction>(*I);
 127     // When processing global values, it's possible that the instructions on
 128     // the use list are not all in this method.  Only add the instructions
 129     // that _are_ in this method.
 130     //
 131     if (Inst->getParent()->getParent() == F->getFunction())
 132       // Only let an instruction occur on the work list once...
 133       if (std::find(WorkList.begin(), WorkList.end(), Inst) == WorkList.end())
 134         WorkList.push_back(Inst);
 135   }
 136 }
 137
 138
 139
 140
 141 void FunctionRepBuilder::initializeWorkList(Function *Func) {
 142   // Add all of the arguments to the method to the graph and add all users to
 143   // the worklists...
 144   //
 145   for (Function::ArgumentListType::iterator I = Func->getArgumentList().begin(),
 146          E = Func->getArgumentList().end(); I != E; ++I)
 147     // Only process arguments that are of pointer type...
 148     if (PointerType *PT = dyn_cast<PointerType>((*I)->getType())) {
 149       ArgDSNode *Arg = new ArgDSNode(*I);
 150       ArgNodes.push_back(Arg);
 151
 152       // Add a critical shadow value for it to represent what it is pointing
 153       // to and add this to the value map...
 154       ShadowDSNode *Shad = new ShadowDSNode(PT->getElementType(),
 155                                             Func->getParent(), true);
 156       ShadowNodes.push_back(Shad);
 157       ValueMap[*I].add(PointerVal(Shad), *I);
 158
 159       // The value of the argument is the shadow value...
 160       Arg->getLink(0).add(Shad);
 161
 162       // Make sure that all users of the argument are processed...
 163       addAllUsesToWorkList(*I);
 164     }
 165
 166   // Iterate over the instructions in the method.  Create nodes for malloc and
 167   // call instructions.  Add all uses of these to the worklist of instructions
 168   // to process.
 169   //
 170   InitVisitor IV(this, Func);
 171   IV.visit(Func);
 172 }
 173
 174
 175
 176
 177 PointerVal FunctionRepBuilder::getIndexedPointerDest(const PointerVal &InP,
 178                                                      const MemAccessInst *MAI) {
 179   unsigned Index = InP.Index;
 180   const Type *SrcTy = MAI->getPointerOperand()->getType();
 181
 182   for (MemAccessInst::const_op_iterator I = MAI->idx_begin(),
 183          E = MAI->idx_end(); I != E; ++I)
 184     if ((*I)->getType() == Type::UByteTy) {     // Look for struct indices...
 185       StructType *STy = cast<StructType>(SrcTy);
 186       unsigned StructIdx = cast<ConstantUInt>(*I)->getValue();
 187       for (unsigned i = 0; i != StructIdx; ++i)
 188         Index += countPointerFields(STy->getContainedType(i));
 189
 190       // Advance SrcTy to be the new element type...
 191       SrcTy = STy->getContainedType(StructIdx);
 192     } else {
 193       // Otherwise, stepping into array or initial pointer, just increment type
 194       SrcTy = cast<SequentialType>(SrcTy)->getElementType();
 195     }
 196
 197   return PointerVal(InP.Node, Index);
 198 }
 199
 200 static PointerValSet &getField(const PointerVal &DestPtr) {
 201   assert(DestPtr.Node != 0);
 202
 203   return DestPtr.Node->getLink(DestPtr.Index);
 204 }
 205
 206
 207 // Reprocessing a GEP instruction is the result of the pointer operand
 208 // changing.  This means that the set of possible values for the GEP
 209 // needs to be expanded.
 210 //
 211 void FunctionRepBuilder::visitGetElementPtrInst(GetElementPtrInst *GEP) {
 212   PointerValSet &GEPPVS = ValueMap[GEP];   // PointerValSet to expand
 213
 214   // Get the input pointer val set...
 215   const PointerValSet &SrcPVS = ValueMap[GEP->getOperand(0)];
 216
 217   bool Changed = false;  // Process each input value... propogating it.
 218   for (unsigned i = 0, e = SrcPVS.size(); i != e; ++i) {
 219     // Calculate where the resulting pointer would point based on an
 220     // input of 'Val' as the pointer type... and add it to our outgoing
 221     // value set.  Keep track of whether or not we actually changed
 222     // anything.
 223     //
 224     Changed |= GEPPVS.add(getIndexedPointerDest(SrcPVS[i], GEP));
 225   }
 226
 227   // If our current value set changed, notify all of the users of our
 228   // value.
 229   //
 230   if (Changed) addAllUsesToWorkList(GEP);
 231 }
 232
 233 void FunctionRepBuilder::visitReturnInst(ReturnInst *RI) {
 234   RetNode.add(ValueMap[RI->getOperand(0)]);
 235 }
 236
 237 void FunctionRepBuilder::visitLoadInst(LoadInst *LI) {
 238   // Only loads that return pointers are interesting...
 239   if (!isa<PointerType>(LI->getType())) return;
 240   const PointerType *DestTy = cast<PointerType>(LI->getType());
 241
 242   const PointerValSet &SrcPVS = ValueMap[LI->getOperand(0)];
 243   PointerValSet &LIPVS = ValueMap[LI];
 244
 245   bool Changed = false;
 246   for (unsigned si = 0, se = SrcPVS.size(); si != se; ++si) {
 247     PointerVal Ptr = getIndexedPointerDest(SrcPVS[si], LI);
 248     PointerValSet &Field = getField(Ptr);
 249
 250     if (Field.size()) {             // Field loaded wasn't null?
 251       Changed |= LIPVS.add(Field);
 252     } else if (ShadowDSNode *Shad = dyn_cast<ShadowDSNode>(Ptr.Node)) {
 253       // If we are loading a null field out of a shadow node, we need to
 254       // synthesize a new shadow node and link it in...
 255       //
 256       ShadowDSNode *SynthNode =
 257         Shad->synthesizeNode(DestTy->getElementType(), this);
 258       Field.add(SynthNode);
 259
 260       Changed |= LIPVS.add(Field);
 261     }
 262   }
 263
 264   if (Changed) addAllUsesToWorkList(LI);
 265 }
 266
 267 void FunctionRepBuilder::visitStoreInst(StoreInst *SI) {
 268   // The only stores that are interesting are stores the store pointers
 269   // into data structures...
 270   //
 271   if (!isa<PointerType>(SI->getOperand(0)->getType())) return;
 272   if (!ValueMap.count(SI->getOperand(0))) return;  // Src scalar has no values!
 273
 274   const PointerValSet &SrcPVS = ValueMap[SI->getOperand(0)];
 275   const PointerValSet &PtrPVS = ValueMap[SI->getOperand(1)];
 276
 277   for (unsigned si = 0, se = SrcPVS.size(); si != se; ++si) {
 278     const PointerVal &SrcPtr = SrcPVS[si];
 279     for (unsigned pi = 0, pe = PtrPVS.size(); pi != pe; ++pi) {
 280       PointerVal Dest = getIndexedPointerDest(PtrPVS[pi], SI);
 281
 282 #if 0
 283       cerr << "Setting Dest:\n";
 284       Dest.print(cerr);
 285       cerr << "to point to Src:\n";
 286       SrcPtr.print(cerr);
 287 #endif
 288
 289       // Add SrcPtr into the Dest field...
 290       if (getField(Dest).add(SrcPtr)) {
 291         // If we modified the dest field, then invalidate everyone that points
 292         // to Dest.
 293         const std::vector<Value*> &Ptrs = Dest.Node->getPointers();
 294         for (unsigned i = 0, e = Ptrs.size(); i != e; ++i)
 295           addAllUsesToWorkList(Ptrs[i]);
 296       }
 297     }
 298   }
 299 }
 300
 301 void FunctionRepBuilder::visitCallInst(CallInst *CI) {
 302   CallDSNode *DSN = CallMap[CI];
 303
 304   unsigned PtrNum = 0, i = 0;
 305   if (isa<Function>(CI->getOperand(0)))
 306     ++i;          // Not an Indirect function call? Skip the function pointer...
 307
 308   for (unsigned e = CI->getNumOperands(); i != e; ++i)
 309     if (isa<PointerType>(CI->getOperand(i)->getType()))
 310       DSN->addArgValue(PtrNum++, ValueMap[CI->getOperand(i)]);
 311 }
 312
 313 void FunctionRepBuilder::visitPHINode(PHINode *PN) {
 314   assert(isa<PointerType>(PN->getType()) && "Should only update ptr phis");
 315
 316   PointerValSet &PN_PVS = ValueMap[PN];
 317   bool Changed = false;
 318   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 319     Changed |= PN_PVS.add(ValueMap[PN->getIncomingValue(i)],
 320                           PN->getIncomingValue(i));
 321
 322   if (Changed) addAllUsesToWorkList(PN);
 323 }
 324
 325
 326
 327
 328 // FunctionDSGraph constructor - Perform the global analysis to determine
 329 // what the data structure usage behavior or a method looks like.
 330 //
 331 FunctionDSGraph::FunctionDSGraph(Function *F) : Func(F) {
 332   FunctionRepBuilder Builder(this);
 333   ArgNodes    = Builder.getArgNodes();
 334   AllocNodes  = Builder.getAllocNodes();
 335   ShadowNodes = Builder.getShadowNodes();
 336   GlobalNodes = Builder.getGlobalNodes();
 337   CallNodes   = Builder.getCallNodes();
 338   RetNode     = Builder.getRetNode();
 339   ValueMap    = Builder.getValueMap();
 340
 341   bool Changed = true;
 342   while (Changed) {
 343     // Eliminate shadow nodes that are not distinguishable from some other
 344     // node in the graph...
 345     //
 346     Changed = UnlinkUndistinguishableNodes();
 347
 348     // Eliminate shadow nodes that are now extraneous due to linking...
 349     Changed |= RemoveUnreachableNodes();
 350   }
 351 }
 352