LLVM API Documentation
00001 //===- Printer.cpp - Code for printing data structure graphs nicely -------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the 'dot' graph printer. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/Analysis/DataStructure/DataStructure.h" 00015 #include "llvm/Analysis/DataStructure/DSGraph.h" 00016 #include "llvm/Analysis/DataStructure/DSGraphTraits.h" 00017 #include "llvm/Module.h" 00018 #include "llvm/Constants.h" 00019 #include "llvm/Assembly/Writer.h" 00020 #include "llvm/Support/CommandLine.h" 00021 #include "llvm/Support/GraphWriter.h" 00022 #include "llvm/ADT/Statistic.h" 00023 #include <fstream> 00024 #include <sstream> 00025 using namespace llvm; 00026 00027 // OnlyPrintMain - The DataStructure printer exposes this option to allow 00028 // printing of only the graph for "main". 00029 // 00030 namespace { 00031 cl::opt<bool> OnlyPrintMain("only-print-main-ds", cl::ReallyHidden); 00032 cl::opt<bool> DontPrintAnything("dont-print-ds", cl::ReallyHidden); 00033 Statistic<> MaxGraphSize ("dsa", "Maximum graph size"); 00034 Statistic<> NumFoldedNodes ("dsa", "Number of folded nodes (in final graph)"); 00035 } 00036 00037 void DSNode::dump() const { print(std::cerr, 0); } 00038 00039 static std::string getCaption(const DSNode *N, const DSGraph *G) { 00040 std::stringstream OS; 00041 Module *M = 0; 00042 00043 if (!G) G = N->getParentGraph(); 00044 00045 // Get the module from ONE of the functions in the graph it is available. 00046 if (G && G->retnodes_begin() != G->retnodes_end()) 00047 M = G->retnodes_begin()->first->getParent(); 00048 if (M == 0 && G) { 00049 // If there is a global in the graph, we can use it to find the module. 00050 const DSScalarMap &SM = G->getScalarMap(); 00051 if (SM.global_begin() != SM.global_end()) 00052 M = (*SM.global_begin())->getParent(); 00053 } 00054 00055 if (N->isNodeCompletelyFolded()) 00056 OS << "COLLAPSED"; 00057 else { 00058 WriteTypeSymbolic(OS, N->getType(), M); 00059 if (N->isArray()) 00060 OS << " array"; 00061 } 00062 if (unsigned NodeType = N->getNodeFlags()) { 00063 OS << ": "; 00064 if (NodeType & DSNode::AllocaNode ) OS << "S"; 00065 if (NodeType & DSNode::HeapNode ) OS << "H"; 00066 if (NodeType & DSNode::GlobalNode ) OS << "G"; 00067 if (NodeType & DSNode::UnknownNode) OS << "U"; 00068 if (NodeType & DSNode::Incomplete ) OS << "I"; 00069 if (NodeType & DSNode::Modified ) OS << "M"; 00070 if (NodeType & DSNode::Read ) OS << "R"; 00071 #ifndef NDEBUG 00072 if (NodeType & DSNode::DEAD ) OS << "<dead>"; 00073 #endif 00074 OS << "\n"; 00075 } 00076 00077 EquivalenceClasses<GlobalValue*> *GlobalECs = 0; 00078 if (G) GlobalECs = &G->getGlobalECs(); 00079 00080 for (unsigned i = 0, e = N->getGlobalsList().size(); i != e; ++i) { 00081 WriteAsOperand(OS, N->getGlobalsList()[i], false, true, M); 00082 00083 // Figure out how many globals are equivalent to this one. 00084 if (GlobalECs) { 00085 EquivalenceClasses<GlobalValue*>::iterator I = 00086 GlobalECs->findValue(N->getGlobalsList()[i]); 00087 if (I != GlobalECs->end()) { 00088 unsigned NumMembers = 00089 std::distance(GlobalECs->member_begin(I), GlobalECs->member_end()); 00090 if (NumMembers != 1) OS << " + " << (NumMembers-1) << " EC"; 00091 } 00092 } 00093 OS << "\n"; 00094 } 00095 00096 return OS.str(); 00097 } 00098 00099 namespace llvm { 00100 template<> 00101 struct DOTGraphTraits<const DSGraph*> : public DefaultDOTGraphTraits { 00102 static std::string getGraphName(const DSGraph *G) { 00103 switch (G->getReturnNodes().size()) { 00104 case 0: return G->getFunctionNames(); 00105 case 1: return "Function " + G->getFunctionNames(); 00106 default: return "Functions: " + G->getFunctionNames(); 00107 } 00108 } 00109 00110 static std::string getNodeLabel(const DSNode *Node, const DSGraph *Graph) { 00111 return getCaption(Node, Graph); 00112 } 00113 00114 static std::string getNodeAttributes(const DSNode *N) { 00115 return "shape=Mrecord"; 00116 } 00117 00118 static bool edgeTargetsEdgeSource(const void *Node, 00119 DSNode::const_iterator I) { 00120 unsigned O = I.getNode()->getLink(I.getOffset()).getOffset(); 00121 return (O >> DS::PointerShift) != 0; 00122 } 00123 00124 static DSNode::const_iterator getEdgeTarget(const DSNode *Node, 00125 DSNode::const_iterator I) { 00126 unsigned O = I.getNode()->getLink(I.getOffset()).getOffset(); 00127 unsigned LinkNo = O >> DS::PointerShift; 00128 const DSNode *N = *I; 00129 DSNode::const_iterator R = N->begin(); 00130 for (; LinkNo; --LinkNo) 00131 ++R; 00132 return R; 00133 } 00134 00135 00136 /// addCustomGraphFeatures - Use this graph writing hook to emit call nodes 00137 /// and the return node. 00138 /// 00139 static void addCustomGraphFeatures(const DSGraph *G, 00140 GraphWriter<const DSGraph*> &GW) { 00141 Module *CurMod = 0; 00142 if (G->retnodes_begin() != G->retnodes_end()) 00143 CurMod = G->retnodes_begin()->first->getParent(); 00144 else { 00145 // If there is a global in the graph, we can use it to find the module. 00146 const DSScalarMap &SM = G->getScalarMap(); 00147 if (SM.global_begin() != SM.global_end()) 00148 CurMod = (*SM.global_begin())->getParent(); 00149 } 00150 00151 00152 // Add scalar nodes to the graph... 00153 const DSGraph::ScalarMapTy &VM = G->getScalarMap(); 00154 for (DSGraph::ScalarMapTy::const_iterator I = VM.begin(); I != VM.end();++I) 00155 if (!isa<GlobalValue>(I->first)) { 00156 std::stringstream OS; 00157 WriteAsOperand(OS, I->first, false, true, CurMod); 00158 GW.emitSimpleNode(I->first, "", OS.str()); 00159 00160 // Add edge from return node to real destination 00161 DSNode *DestNode = I->second.getNode(); 00162 int EdgeDest = I->second.getOffset() >> DS::PointerShift; 00163 if (EdgeDest == 0) EdgeDest = -1; 00164 GW.emitEdge(I->first, -1, DestNode, 00165 EdgeDest, "arrowtail=tee,color=gray63"); 00166 } 00167 00168 00169 // Output the returned value pointer... 00170 for (DSGraph::retnodes_iterator I = G->retnodes_begin(), 00171 E = G->retnodes_end(); I != E; ++I) 00172 if (I->second.getNode()) { 00173 std::string Label; 00174 if (G->getReturnNodes().size() == 1) 00175 Label = "returning"; 00176 else 00177 Label = I->first->getName() + " ret node"; 00178 // Output the return node... 00179 GW.emitSimpleNode((void*)I->first, "plaintext=circle", Label); 00180 00181 // Add edge from return node to real destination 00182 DSNode *RetNode = I->second.getNode(); 00183 int RetEdgeDest = I->second.getOffset() >> DS::PointerShift;; 00184 if (RetEdgeDest == 0) RetEdgeDest = -1; 00185 GW.emitEdge((void*)I->first, -1, RetNode, 00186 RetEdgeDest, "arrowtail=tee,color=gray63"); 00187 } 00188 00189 // Output all of the call nodes... 00190 const std::list<DSCallSite> &FCs = 00191 G->shouldPrintAuxCalls() ? G->getAuxFunctionCalls() 00192 : G->getFunctionCalls(); 00193 for (std::list<DSCallSite>::const_iterator I = FCs.begin(), E = FCs.end(); 00194 I != E; ++I) { 00195 const DSCallSite &Call = *I; 00196 std::vector<std::string> EdgeSourceCaptions(Call.getNumPtrArgs()+2); 00197 EdgeSourceCaptions[0] = "r"; 00198 if (Call.isDirectCall()) 00199 EdgeSourceCaptions[1] = Call.getCalleeFunc()->getName(); 00200 else 00201 EdgeSourceCaptions[1] = "f"; 00202 00203 GW.emitSimpleNode(&Call, "shape=record", "call", Call.getNumPtrArgs()+2, 00204 &EdgeSourceCaptions); 00205 00206 if (DSNode *N = Call.getRetVal().getNode()) { 00207 int EdgeDest = Call.getRetVal().getOffset() >> DS::PointerShift; 00208 if (EdgeDest == 0) EdgeDest = -1; 00209 GW.emitEdge(&Call, 0, N, EdgeDest, "color=gray63,tailclip=false"); 00210 } 00211 00212 // Print out the callee... 00213 if (Call.isIndirectCall()) { 00214 DSNode *N = Call.getCalleeNode(); 00215 assert(N && "Null call site callee node!"); 00216 GW.emitEdge(&Call, 1, N, -1, "color=gray63,tailclip=false"); 00217 } 00218 00219 for (unsigned j = 0, e = Call.getNumPtrArgs(); j != e; ++j) 00220 if (DSNode *N = Call.getPtrArg(j).getNode()) { 00221 int EdgeDest = Call.getPtrArg(j).getOffset() >> DS::PointerShift; 00222 if (EdgeDest == 0) EdgeDest = -1; 00223 GW.emitEdge(&Call, j+2, N, EdgeDest, "color=gray63,tailclip=false"); 00224 } 00225 } 00226 } 00227 }; 00228 } // end namespace llvm 00229 00230 void DSNode::print(std::ostream &O, const DSGraph *G) const { 00231 GraphWriter<const DSGraph *> W(O, G); 00232 W.writeNode(this); 00233 } 00234 00235 void DSGraph::print(std::ostream &O) const { 00236 WriteGraph(O, this, "DataStructures"); 00237 } 00238 00239 void DSGraph::writeGraphToFile(std::ostream &O, 00240 const std::string &GraphName) const { 00241 std::string Filename = GraphName + ".dot"; 00242 O << "Writing '" << Filename << "'..."; 00243 std::ofstream F(Filename.c_str()); 00244 00245 if (F.good()) { 00246 print(F); 00247 unsigned NumCalls = shouldPrintAuxCalls() ? 00248 getAuxFunctionCalls().size() : getFunctionCalls().size(); 00249 O << " [" << getGraphSize() << "+" << NumCalls << "]\n"; 00250 } else { 00251 O << " error opening file for writing!\n"; 00252 } 00253 } 00254 00255 /// viewGraph - Emit a dot graph, run 'dot', run gv on the postscript file, 00256 /// then cleanup. For use from the debugger. 00257 /// 00258 void DSGraph::viewGraph() const { 00259 std::ofstream F("/tmp/tempgraph.dot"); 00260 if (!F.good()) { 00261 std::cerr << "Error opening '/tmp/tempgraph.dot' for temporary graph!\n"; 00262 return; 00263 } 00264 print(F); 00265 F.close(); 00266 if (system("dot -Tps -Gsize=10,7.5 -Grotate=90 /tmp/tempgraph.dot > /tmp/tempgraph.ps")) 00267 std::cerr << "Error running dot: 'dot' not in path?\n"; 00268 system("gv /tmp/tempgraph.ps"); 00269 system("rm /tmp/tempgraph.dot /tmp/tempgraph.ps"); 00270 } 00271 00272 00273 template <typename Collection> 00274 static void printCollection(const Collection &C, std::ostream &O, 00275 const Module *M, const std::string &Prefix) { 00276 if (M == 0) { 00277 O << "Null Module pointer, cannot continue!\n"; 00278 return; 00279 } 00280 00281 unsigned TotalNumNodes = 0, TotalCallNodes = 0; 00282 for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) 00283 if (C.hasGraph(*I)) { 00284 DSGraph &Gr = C.getDSGraph((Function&)*I); 00285 unsigned NumCalls = Gr.shouldPrintAuxCalls() ? 00286 Gr.getAuxFunctionCalls().size() : Gr.getFunctionCalls().size(); 00287 bool IsDuplicateGraph = false; 00288 00289 if (I->getName() == "main" || !OnlyPrintMain) { 00290 Function *SCCFn = Gr.retnodes_begin()->first; 00291 if (&*I == SCCFn) { 00292 Gr.writeGraphToFile(O, Prefix+I->getName()); 00293 } else { 00294 IsDuplicateGraph = true; // Don't double count node/call nodes. 00295 O << "Didn't write '" << Prefix+I->getName() 00296 << ".dot' - Graph already emitted to '" << Prefix+SCCFn->getName() 00297 << "\n"; 00298 } 00299 } else { 00300 Function *SCCFn = Gr.retnodes_begin()->first; 00301 if (&*I == SCCFn) { 00302 O << "Skipped Writing '" << Prefix+I->getName() << ".dot'... [" 00303 << Gr.getGraphSize() << "+" << NumCalls << "]\n"; 00304 } else { 00305 IsDuplicateGraph = true; // Don't double count node/call nodes. 00306 } 00307 } 00308 00309 if (!IsDuplicateGraph) { 00310 unsigned GraphSize = Gr.getGraphSize(); 00311 if (MaxGraphSize < GraphSize) MaxGraphSize = GraphSize; 00312 00313 TotalNumNodes += Gr.getGraphSize(); 00314 TotalCallNodes += NumCalls; 00315 for (DSGraph::node_iterator NI = Gr.node_begin(), E = Gr.node_end(); 00316 NI != E; ++NI) 00317 if (NI->isNodeCompletelyFolded()) 00318 ++NumFoldedNodes; 00319 } 00320 } 00321 00322 DSGraph &GG = C.getGlobalsGraph(); 00323 TotalNumNodes += GG.getGraphSize(); 00324 TotalCallNodes += GG.getFunctionCalls().size(); 00325 if (!OnlyPrintMain) { 00326 GG.writeGraphToFile(O, Prefix+"GlobalsGraph"); 00327 } else { 00328 O << "Skipped Writing '" << Prefix << "GlobalsGraph.dot'... [" 00329 << GG.getGraphSize() << "+" << GG.getFunctionCalls().size() << "]\n"; 00330 } 00331 00332 O << "\nGraphs contain [" << TotalNumNodes << "+" << TotalCallNodes 00333 << "] nodes total" << std::endl; 00334 } 00335 00336 00337 // print - Print out the analysis results... 00338 void LocalDataStructures::print(std::ostream &O, const Module *M) const { 00339 if (DontPrintAnything) return; 00340 printCollection(*this, O, M, "ds."); 00341 } 00342 00343 void BUDataStructures::print(std::ostream &O, const Module *M) const { 00344 if (DontPrintAnything) return; 00345 printCollection(*this, O, M, "bu."); 00346 } 00347 00348 void TDDataStructures::print(std::ostream &O, const Module *M) const { 00349 if (DontPrintAnything) return; 00350 printCollection(*this, O, M, "td."); 00351 } 00352 00353 void CompleteBUDataStructures::print(std::ostream &O, const Module *M) const { 00354 if (DontPrintAnything) return; 00355 printCollection(*this, O, M, "cbu."); 00356 } 00357 00358 00359 void EquivClassGraphs::print(std::ostream &O, const Module *M) const { 00360 if (DontPrintAnything) return; 00361 printCollection(*this, O, M, "eq."); 00362 } 00363