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