lib/Analysis/DataStructure/FunctionRepBuilder.cpp

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