lib/Analysis/DataStructure/NodeImpl.cpp

   1 //===- NodeImpl.cpp - Implement the data structure analysis nodes ---------===//
   2 //
   3 // Implement the LLVM data structure analysis library.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/Analysis/DataStructureGraph.h"
   8 #include "llvm/Assembly/Writer.h"
   9 #include "llvm/DerivedTypes.h"
  10 #include "llvm/Function.h"
  11 #include "llvm/BasicBlock.h"
  12 #include "llvm/iMemory.h"
  13 #include "llvm/iOther.h"
  14 #include "Support/STLExtras.h"
  15 #include <algorithm>
  16 #include <sstream>
  17
  18 bool AllocDSNode::isEquivalentTo(DSNode *Node) const {
  19   if (AllocDSNode *N = dyn_cast<AllocDSNode>(Node))
  20     return getType() == Node->getType();
  21   return false;
  22 }
  23
  24 void AllocDSNode::mergeInto(DSNode *Node) const {
  25   // Make sure the merged node is variable size if this node is var size
  26   AllocDSNode *N = cast<AllocDSNode>(Node);
  27   N->isVarSize |= isVarSize;
  28 }
  29
  30 bool GlobalDSNode::isEquivalentTo(DSNode *Node) const {
  31   if (GlobalDSNode *G = dyn_cast<GlobalDSNode>(Node)) {
  32     if (G->Val != Val) return false;
  33
  34     // Check that the outgoing links are identical...
  35     assert(getNumLinks() == G->getNumLinks() && "Not identical shape?");
  36     for (unsigned i = 0, e = getNumLinks(); i != e; ++i)
  37       if (getLink(i) != G->getLink(i))          // Check links
  38         return false;
  39     return true;
  40   }
  41   return false;
  42 }
  43
  44 // Call node equivalency - Two call nodes are identical if all of the outgoing
  45 // links are the same, AND if all of the incoming links are identical.
  46 //
  47 bool CallDSNode::isEquivalentTo(DSNode *Node) const {
  48   if (CallDSNode *C = dyn_cast<CallDSNode>(Node)) {
  49     if (getReferrers().size() != C->getReferrers().size() ||
  50         C->getType() != getType())
  51       return false; // Quick check...
  52
  53     // Check that the outgoing links are identical...
  54     assert(getNumLinks() == C->getNumLinks() && "Not identical shape?");
  55     for (unsigned i = 0, e = getNumLinks(); i != e; ++i)
  56       if (getLink(i) != C->getLink(i))          // Check links
  57         return false;
  58
  59
  60     std::vector<PointerValSet*> Refs1 = C->getReferrers();
  61     std::vector<PointerValSet*> Refs2 = getReferrers();
  62
  63     sort(Refs1.begin(), Refs1.end());
  64     sort(Refs2.begin(), Refs2.end());
  65     if (Refs1 != Refs2) return false;               // Incoming edges different?
  66
  67     // Check that all outgoing links are the same...
  68     return C->ArgLinks == ArgLinks;   // Check that the arguments are identical
  69   }
  70   return false;
  71 }
  72
  73 // NodesAreEquivalent - Check to see if the nodes are equivalent in all ways
  74 // except node type.  Since we know N1 is a shadow node, N2 is allowed to be
  75 // any type.
  76 //
  77 bool ShadowDSNode::isEquivalentTo(DSNode *Node) const {
  78   return getType() == Node->getType();
  79 }
  80
  81
  82
  83
  84 //===----------------------------------------------------------------------===//
  85 //  DSNode Class Implementation
  86 //
  87
  88 static void MapPVS(PointerValSet &PVSOut, const PointerValSet &PVSIn,
  89                    map<const DSNode*, DSNode*> &NodeMap, bool ReinitOk = false){
  90   assert((ReinitOk || PVSOut.empty()) && "Value set already initialized!");
  91
  92   for (unsigned i = 0, e = PVSIn.size(); i != e; ++i)
  93     PVSOut.add(PointerVal(NodeMap[PVSIn[i].Node], PVSIn[i].Index));
  94 }
  95
  96
  97
  98 unsigned countPointerFields(const Type *Ty) {
  99   switch (Ty->getPrimitiveID()) {
 100   case Type::StructTyID: {
 101     const StructType *ST = cast<StructType>(Ty);
 102     unsigned Sum = 0;
 103     for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i)
 104       Sum += countPointerFields(ST->getContainedType(i));
 105
 106     return Sum;
 107   }
 108
 109   case Type::ArrayTyID:
 110     // All array elements are folded together...
 111     return countPointerFields(cast<ArrayType>(Ty)->getElementType());
 112
 113   case Type::PointerTyID:
 114     return 1;
 115
 116   default:                     // Some other type, just treat it like a scalar
 117     return 0;
 118   }
 119 }
 120
 121 DSNode::DSNode(enum NodeTy NT, const Type *T) : Ty(T), NodeType(NT) {
 122   // Create field entries for all of the values in this type...
 123   FieldLinks.resize(countPointerFields(getType()));
 124 }
 125
 126 void DSNode::removeReferrer(PointerValSet *PVS) {
 127   vector<PointerValSet*>::iterator I = std::find(Referrers.begin(),
 128                                                  Referrers.end(), PVS);
 129   assert(I != Referrers.end() && "PVS not pointing to node!");
 130   Referrers.erase(I);
 131 }
 132
 133
 134 // removeAllIncomingEdges - Erase all edges in the graph that point to this node
 135 void DSNode::removeAllIncomingEdges() {
 136   while (!Referrers.empty())
 137     Referrers.back()->removePointerTo(this);
 138 }
 139
 140
 141 static void replaceIn(std::string &S, char From, const std::string &To) {
 142   for (unsigned i = 0; i < S.size(); )
 143     if (S[i] == From) {
 144       S.replace(S.begin()+i, S.begin()+i+1,
 145                 To.begin(), To.end());
 146       i += To.size();
 147     } else {
 148       ++i;
 149     }
 150 }
 151
 152 static void writeEdges(std::ostream &O, const void *SrcNode,
 153                        const char *SrcNodePortName, int SrcNodeIdx,
 154                        const PointerValSet &VS, const string &EdgeAttr = "") {
 155   for (unsigned j = 0, je = VS.size(); j != je; ++j) {
 156     O << "\t\tNode" << SrcNode << SrcNodePortName;
 157     if (SrcNodeIdx != -1) O << SrcNodeIdx;
 158
 159     O << " -> Node" << VS[j].Node;
 160     if (VS[j].Index)
 161       O << ":g" << VS[j].Index;
 162
 163     if (!EdgeAttr.empty())
 164       O << "[" << EdgeAttr << "]";
 165     O << ";\n";
 166   }
 167 }
 168
 169 static string escapeLabel(const string &In) {
 170   string Label(In);
 171   replaceIn(Label, '\\', "\\\\\\\\");  // Escape caption...
 172   replaceIn(Label, ' ', "\\ ");
 173   replaceIn(Label, '{', "\\{");
 174   replaceIn(Label, '}', "\\}");
 175   return Label;
 176 }
 177
 178 void DSNode::dump() const { print(cerr); }
 179
 180 void DSNode::print(std::ostream &O) const {
 181   string Caption = escapeLabel(getCaption());
 182
 183   O << "\t\tNode" << (void*)this << " [ label =\"{" << Caption;
 184
 185   const vector<PointerValSet> *Links = getAuxLinks();
 186   if (Links && !Links->empty()) {
 187     O << "|{";
 188     for (unsigned i = 0; i < Links->size(); ++i) {
 189       if (i) O << "|";
 190       O << "<f" << i << ">";
 191     }
 192     O << "}";
 193   }
 194
 195   if (!FieldLinks.empty()) {
 196     O << "|{";
 197     for (unsigned i = 0; i < FieldLinks.size(); ++i) {
 198       if (i) O << "|";
 199       O << "<g" << i << ">";
 200     }
 201     O << "}";
 202   }
 203   O << "}\"];\n";
 204
 205   if (Links)
 206     for (unsigned i = 0; i < Links->size(); ++i)
 207       writeEdges(O, this, ":f", i, (*Links)[i]);
 208   for (unsigned i = 0; i < FieldLinks.size(); ++i)
 209     writeEdges(O, this, ":g", i, FieldLinks[i]);
 210 }
 211
 212 void DSNode::mapNode(map<const DSNode*, DSNode*> &NodeMap, const DSNode *Old) {
 213   assert(FieldLinks.size() == Old->FieldLinks.size() &&
 214          "Cloned nodes do not have the same number of links!");
 215   for (unsigned j = 0, je = FieldLinks.size(); j != je; ++j)
 216     MapPVS(FieldLinks[j], Old->FieldLinks[j], NodeMap);
 217
 218   // Map our SynthNodes...
 219   assert(SynthNodes.empty() && "Synthnodes already mapped?");
 220   SynthNodes.reserve(Old->SynthNodes.size());
 221   for (unsigned i = 0, e = Old->SynthNodes.size(); i != e; ++i)
 222     SynthNodes.push_back(std::make_pair(Old->SynthNodes[i].first,
 223                     (ShadowDSNode*)NodeMap[Old->SynthNodes[i].second]));
 224 }
 225
 226 AllocDSNode::AllocDSNode(AllocationInst *V, bool isvarsize)
 227   : DSNode(NewNode, V->getType()->getElementType()), Allocation(V) {
 228
 229   // Is variable size if incoming flag says so, or if allocation is var size
 230   // already.
 231   isVarSize = isvarsize || !isa<Constant>(V->getArraySize());
 232 }
 233
 234 bool AllocDSNode::isAllocaNode() const {
 235   return isa<AllocaInst>(Allocation);
 236 }
 237
 238
 239 string AllocDSNode::getCaption() const {
 240   stringstream OS;
 241   OS << (isMallocNode() ? "new " : "alloca ");
 242
 243   WriteTypeSymbolic(OS, getType(),
 244                     Allocation->getParent()->getParent()->getParent());
 245   if (isVarSize)
 246     OS << "[ ]";
 247   return OS.str();
 248 }
 249
 250 GlobalDSNode::GlobalDSNode(GlobalValue *V)
 251   : DSNode(GlobalNode, V->getType()->getElementType()), Val(V) {
 252 }
 253
 254 string GlobalDSNode::getCaption() const {
 255   stringstream OS;
 256   if (isa<Function>(Val))
 257     OS << "fn ";
 258   else
 259     OS << "global ";
 260
 261   WriteTypeSymbolic(OS, getType(), Val->getParent());
 262   return OS.str() + " %" + Val->getName();
 263 }
 264
 265
 266 ShadowDSNode::ShadowDSNode(const Type *Ty, Module *M) : DSNode(ShadowNode, Ty) {
 267   Mod = M;
 268   ShadowParent = 0;
 269 }
 270
 271 ShadowDSNode::ShadowDSNode(const Type *Ty, Module *M, DSNode *ShadParent)
 272   : DSNode(ShadowNode, Ty) {
 273   Mod = M;
 274   ShadowParent = ShadParent;
 275 }
 276
 277 std::string ShadowDSNode::getCaption() const {
 278   stringstream OS;
 279   OS << "shadow ";
 280   WriteTypeSymbolic(OS, getType(), Mod);
 281   return OS.str();
 282 }
 283
 284 CallDSNode::CallDSNode(CallInst *ci) : DSNode(CallNode, ci->getType()), CI(ci) {
 285   unsigned NumPtrs = 0;
 286   for (unsigned i = 0, e = ci->getNumOperands(); i != e; ++i)
 287     if (isa<PointerType>(ci->getOperand(i)->getType()))
 288       NumPtrs++;
 289   ArgLinks.resize(NumPtrs);
 290 }
 291
 292 string CallDSNode::getCaption() const {
 293   stringstream OS;
 294   if (const Function *CM = CI->getCalledFunction())
 295     OS << "call " << CM->getName();
 296   else
 297     OS << "call <indirect>";
 298   OS << ": ";
 299   WriteTypeSymbolic(OS, getType(),
 300                     CI->getParent()->getParent()->getParent());
 301   return OS.str();
 302 }
 303
 304 void CallDSNode::mapNode(map<const DSNode*, DSNode*> &NodeMap,
 305                          const DSNode *O) {
 306   const CallDSNode *Old = cast<CallDSNode>(O);
 307   DSNode::mapNode(NodeMap, Old);  // Map base portions first...
 308
 309   assert(ArgLinks.size() == Old->ArgLinks.size() && "# Arguments changed!?");
 310   for (unsigned i = 0, e = Old->ArgLinks.size(); i != e; ++i)
 311     MapPVS(ArgLinks[i], Old->ArgLinks[i], NodeMap);
 312 }
 313
 314 void FunctionDSGraph::printFunction(std::ostream &O,
 315                                     const char *Label) const {
 316   O << "\tsubgraph cluster_" << Label << "_Function" << (void*)this << " {\n";
 317   O << "\t\tlabel=\"" << Label << " Function\\ " << Func->getName() << "\";\n";
 318   for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i)
 319     AllocNodes[i]->print(O);
 320   for (unsigned i = 0, e = ShadowNodes.size(); i != e; ++i)
 321     ShadowNodes[i]->print(O);
 322   for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
 323     GlobalNodes[i]->print(O);
 324   for (unsigned i = 0, e = CallNodes.size(); i != e; ++i)
 325     CallNodes[i]->print(O);
 326
 327   if (RetNode.size()) {
 328     O << "\t\tNode" << (void*)this << Label
 329       << " [shape=\"ellipse\", label=\"Returns\"];\n";
 330     writeEdges(O, this, Label, -1, RetNode);
 331   }
 332
 333   O << "\n";
 334   for (std::map<Value*, PointerValSet>::const_iterator I = ValueMap.begin(),
 335          E = ValueMap.end(); I != E; ++I) {
 336     if (I->second.size()) {             // Only output nodes with edges...
 337       stringstream OS;
 338       WriteTypeSymbolic(OS, I->first->getType(), Func->getParent());
 339
 340       // Create node for I->first
 341       O << "\t\tNode" << (void*)I->first << Label << " [shape=\""
 342         << (isa<Argument>(I->first) ? "ellipse" : "box") << "\", label=\""
 343         << escapeLabel(OS.str()) << "\\n%" << escapeLabel(I->first->getName())
 344         << "\",fontsize=\"12.0\",color=\"gray70\"];\n";
 345
 346       // add edges from I->first to all pointers in I->second
 347       writeEdges(O, I->first, Label, -1, I->second,
 348                  "weight=\"0.9\",color=\"gray70\"");
 349     }
 350   }
 351
 352   O << "\t}\n";
 353 }
 354
 355 // Copy constructor - Since we copy the nodes over, we have to be sure to go
 356 // through and fix pointers to point into the new graph instead of into the old
 357 // graph...
 358 //
 359 FunctionDSGraph::FunctionDSGraph(const FunctionDSGraph &DSG) : Func(DSG.Func) {
 360   vector<PointerValSet> Args;
 361   RetNode = cloneFunctionIntoSelf(DSG, true, Args);
 362 }
 363
 364
 365 // cloneFunctionIntoSelf - Clone the specified method graph into the current
 366 // method graph, returning the Return's set of the graph.   If ValueMap is set
 367 // to true, the ValueMap of the function is cloned into this function as well
 368 // as the data structure graph itself.  Regardless, the arguments value sets
 369 // of DSG are copied into Args.
 370 //
 371 PointerValSet FunctionDSGraph::cloneFunctionIntoSelf(const FunctionDSGraph &DSG,
 372                                                      bool CloneValueMap,
 373                                                   vector<PointerValSet> &Args) {
 374   map<const DSNode*, DSNode*> NodeMap;  // Map from old graph to new graph...
 375   unsigned StartAllocSize = AllocNodes.size();
 376   AllocNodes.reserve(StartAllocSize+DSG.AllocNodes.size());
 377   unsigned StartShadowSize = ShadowNodes.size();
 378   ShadowNodes.reserve(StartShadowSize+DSG.ShadowNodes.size());
 379   unsigned StartGlobalSize = GlobalNodes.size();
 380   GlobalNodes.reserve(StartGlobalSize+DSG.GlobalNodes.size());
 381   unsigned StartCallSize = CallNodes.size();
 382   CallNodes.reserve(StartCallSize+DSG.CallNodes.size());
 383
 384   // Clone all of the alloc nodes similarly...
 385   for (unsigned i = 0, e = DSG.AllocNodes.size(); i != e; ++i) {
 386     AllocDSNode *New = cast<AllocDSNode>(DSG.AllocNodes[i]->clone());
 387     NodeMap[DSG.AllocNodes[i]] = New;
 388     AllocNodes.push_back(New);
 389   }
 390
 391   // Clone all of the shadow nodes similarly...
 392   for (unsigned i = 0, e = DSG.ShadowNodes.size(); i != e; ++i) {
 393     ShadowDSNode *New = cast<ShadowDSNode>(DSG.ShadowNodes[i]->clone());
 394     NodeMap[DSG.ShadowNodes[i]] = New;
 395     ShadowNodes.push_back(New);
 396   }
 397
 398   // Clone all of the global nodes...
 399   for (unsigned i = 0, e = DSG.GlobalNodes.size(); i != e; ++i) {
 400     GlobalDSNode *New = cast<GlobalDSNode>(DSG.GlobalNodes[i]->clone());
 401     NodeMap[DSG.GlobalNodes[i]] = New;
 402     GlobalNodes.push_back(New);
 403   }
 404
 405   // Clone all of the call nodes...
 406   for (unsigned i = 0, e = DSG.CallNodes.size(); i != e; ++i) {
 407     CallDSNode *New = cast<CallDSNode>(DSG.CallNodes[i]->clone());
 408     NodeMap[DSG.CallNodes[i]] = New;
 409     CallNodes.push_back(New);
 410   }
 411
 412   // Convert all of the links over in the nodes now that the map has been filled
 413   // in all the way...
 414   //
 415   for (unsigned i = 0, e = DSG.AllocNodes.size(); i != e; ++i)
 416     AllocNodes[i+StartAllocSize]->mapNode(NodeMap, DSG.AllocNodes[i]);
 417   for (unsigned i = 0, e = DSG.ShadowNodes.size(); i != e; ++i)
 418     ShadowNodes[i+StartShadowSize]->mapNode(NodeMap, DSG.ShadowNodes[i]);
 419   for (unsigned i = 0, e = DSG.GlobalNodes.size(); i != e; ++i)
 420     GlobalNodes[i+StartGlobalSize]->mapNode(NodeMap, DSG.GlobalNodes[i]);
 421   for (unsigned i = 0, e = DSG.CallNodes.size(); i != e; ++i)
 422     CallNodes[i+StartCallSize]->mapNode(NodeMap, DSG.CallNodes[i]);
 423
 424   // Convert over the arguments...
 425   Function *OF = DSG.getFunction();
 426   for (Function::ArgumentListType::iterator I = OF->getArgumentList().begin(),
 427          E = OF->getArgumentList().end(); I != E; ++I)
 428     if (isa<PointerType>(((Value*)*I)->getType())) {
 429       PointerValSet ArgPVS;
 430       assert(DSG.getValueMap().find((Value*)*I) != DSG.getValueMap().end());
 431       MapPVS(ArgPVS, DSG.getValueMap().find((Value*)*I)->second, NodeMap);
 432       assert(!ArgPVS.empty() && "Argument has no links!");
 433       Args.push_back(ArgPVS);
 434     }
 435
 436
 437   if (CloneValueMap) {
 438     // Convert value map... the values themselves stay the same, just the nodes
 439     // have to change...
 440     //
 441     for (std::map<Value*,PointerValSet>::const_iterator I =DSG.ValueMap.begin(),
 442            E = DSG.ValueMap.end(); I != E; ++I)
 443       MapPVS(ValueMap[I->first], I->second, NodeMap, true);
 444   }
 445
 446   // Convert over return node...
 447   PointerValSet RetVals;
 448   MapPVS(RetVals, DSG.RetNode, NodeMap);
 449   return RetVals;
 450 }
 451
 452
 453 FunctionDSGraph::~FunctionDSGraph() {
 454   RetNode.clear();
 455   ValueMap.clear();
 456   for_each(AllocNodes.begin(), AllocNodes.end(),
 457            mem_fun(&DSNode::dropAllReferences));
 458   for_each(ShadowNodes.begin(), ShadowNodes.end(),
 459            mem_fun(&DSNode::dropAllReferences));
 460   for_each(GlobalNodes.begin(), GlobalNodes.end(),
 461            mem_fun(&DSNode::dropAllReferences));
 462   for_each(CallNodes.begin(), CallNodes.end(),
 463            mem_fun(&DSNode::dropAllReferences));
 464   for_each(AllocNodes.begin(),  AllocNodes.end(),  deleter<DSNode>);
 465   for_each(ShadowNodes.begin(), ShadowNodes.end(), deleter<DSNode>);
 466   for_each(GlobalNodes.begin(), GlobalNodes.end(), deleter<DSNode>);
 467   for_each(CallNodes.begin(),   CallNodes.end(),   deleter<DSNode>);
 468 }
 469