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->getReturnNodes().empty()) 00047 M = G->getReturnNodes().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 for (unsigned i = 0, e = N->getGlobals().size(); i != e; ++i) { 00078 WriteAsOperand(OS, N->getGlobals()[i], false, true, M); 00079 OS << "\n"; 00080 } 00081 00082 return OS.str(); 00083 } 00084 00085 namespace llvm { 00086 template<> 00087 struct DOTGraphTraits<const DSGraph*> : public DefaultDOTGraphTraits { 00088 static std::string getGraphName(const DSGraph *G) { 00089 switch (G->getReturnNodes().size()) { 00090 case 0: return G->getFunctionNames(); 00091 case 1: return "Function " + G->getFunctionNames(); 00092 default: return "Functions: " + G->getFunctionNames(); 00093 } 00094 } 00095 00096 static std::string getNodeLabel(const DSNode *Node, const DSGraph *Graph) { 00097 return getCaption(Node, Graph); 00098 } 00099 00100 static std::string getNodeAttributes(const DSNode *N) { 00101 return "shape=Mrecord"; 00102 } 00103 00104 static bool edgeTargetsEdgeSource(const void *Node, 00105 DSNode::const_iterator I) { 00106 unsigned O = I.getNode()->getLink(I.getOffset()).getOffset(); 00107 return (O >> DS::PointerShift) != 0; 00108 } 00109 00110 static DSNode::const_iterator getEdgeTarget(const DSNode *Node, 00111 DSNode::const_iterator I) { 00112 unsigned O = I.getNode()->getLink(I.getOffset()).getOffset(); 00113 unsigned LinkNo = O >> DS::PointerShift; 00114 const DSNode *N = *I; 00115 DSNode::const_iterator R = N->begin(); 00116 for (; LinkNo; --LinkNo) 00117 ++R; 00118 return R; 00119 } 00120 00121 00122 /// addCustomGraphFeatures - Use this graph writing hook to emit call nodes 00123 /// and the return node. 00124 /// 00125 static void addCustomGraphFeatures(const DSGraph *G, 00126 GraphWriter<const DSGraph*> &GW) { 00127 Module *CurMod = 0; 00128 if (!G->getReturnNodes().empty()) 00129 CurMod = G->getReturnNodes().begin()->first->getParent(); 00130 else { 00131 // If there is a global in the graph, we can use it to find the module. 00132 const DSScalarMap &SM = G->getScalarMap(); 00133 if (SM.global_begin() != SM.global_end()) 00134 CurMod = (*SM.global_begin())->getParent(); 00135 } 00136 00137 00138 // Add scalar nodes to the graph... 00139 const DSGraph::ScalarMapTy &VM = G->getScalarMap(); 00140 for (DSGraph::ScalarMapTy::const_iterator I = VM.begin(); I != VM.end();++I) 00141 if (!isa<GlobalValue>(I->first)) { 00142 std::stringstream OS; 00143 WriteAsOperand(OS, I->first, false, true, CurMod); 00144 GW.emitSimpleNode(I->first, "", OS.str()); 00145 00146 // Add edge from return node to real destination 00147 DSNode *DestNode = I->second.getNode(); 00148 int EdgeDest = I->second.getOffset() >> DS::PointerShift; 00149 if (EdgeDest == 0) EdgeDest = -1; 00150 GW.emitEdge(I->first, -1, DestNode, 00151 EdgeDest, "arrowtail=tee,color=gray63"); 00152 } 00153 00154 00155 // Output the returned value pointer... 00156 const DSGraph::ReturnNodesTy &RetNodes = G->getReturnNodes(); 00157 for (DSGraph::ReturnNodesTy::const_iterator I = RetNodes.begin(), 00158 E = RetNodes.end(); I != E; ++I) 00159 if (I->second.getNode()) { 00160 std::string Label; 00161 if (RetNodes.size() == 1) 00162 Label = "returning"; 00163 else 00164 Label = I->first->getName() + " ret node"; 00165 // Output the return node... 00166 GW.emitSimpleNode((void*)I->first, "plaintext=circle", Label); 00167 00168 // Add edge from return node to real destination 00169 DSNode *RetNode = I->second.getNode(); 00170 int RetEdgeDest = I->second.getOffset() >> DS::PointerShift;; 00171 if (RetEdgeDest == 0) RetEdgeDest = -1; 00172 GW.emitEdge((void*)I->first, -1, RetNode, 00173 RetEdgeDest, "arrowtail=tee,color=gray63"); 00174 } 00175 00176 // Output all of the call nodes... 00177 const std::vector<DSCallSite> &FCs = 00178 G->shouldPrintAuxCalls() ? G->getAuxFunctionCalls() 00179 : G->getFunctionCalls(); 00180 for (unsigned i = 0, e = FCs.size(); i != e; ++i) { 00181 const DSCallSite &Call = FCs[i]; 00182 std::vector<std::string> EdgeSourceCaptions(Call.getNumPtrArgs()+2); 00183 EdgeSourceCaptions[0] = "r"; 00184 if (Call.isDirectCall()) 00185 EdgeSourceCaptions[1] = Call.getCalleeFunc()->getName(); 00186 else 00187 EdgeSourceCaptions[1] = "f"; 00188 00189 GW.emitSimpleNode(&Call, "shape=record", "call", Call.getNumPtrArgs()+2, 00190 &EdgeSourceCaptions); 00191 00192 if (DSNode *N = Call.getRetVal().getNode()) { 00193 int EdgeDest = Call.getRetVal().getOffset() >> DS::PointerShift; 00194 if (EdgeDest == 0) EdgeDest = -1; 00195 GW.emitEdge(&Call, 0, N, EdgeDest, "color=gray63,tailclip=false"); 00196 } 00197 00198 // Print out the callee... 00199 if (Call.isIndirectCall()) { 00200 DSNode *N = Call.getCalleeNode(); 00201 assert(N && "Null call site callee node!"); 00202 GW.emitEdge(&Call, 1, N, -1, "color=gray63,tailclip=false"); 00203 } 00204 00205 for (unsigned j = 0, e = Call.getNumPtrArgs(); j != e; ++j) 00206 if (DSNode *N = Call.getPtrArg(j).getNode()) { 00207 int EdgeDest = Call.getPtrArg(j).getOffset() >> DS::PointerShift; 00208 if (EdgeDest == 0) EdgeDest = -1; 00209 GW.emitEdge(&Call, j+2, N, EdgeDest, "color=gray63,tailclip=false"); 00210 } 00211 } 00212 } 00213 }; 00214 } // end namespace llvm 00215 00216 void DSNode::print(std::ostream &O, const DSGraph *G) const { 00217 GraphWriter<const DSGraph *> W(O, G); 00218 W.writeNode(this); 00219 } 00220 00221 void DSGraph::print(std::ostream &O) const { 00222 WriteGraph(O, this, "DataStructures"); 00223 } 00224 00225 void DSGraph::writeGraphToFile(std::ostream &O, 00226 const std::string &GraphName) const { 00227 std::string Filename = GraphName + ".dot"; 00228 O << "Writing '" << Filename << "'..."; 00229 std::ofstream F(Filename.c_str()); 00230 00231 if (F.good()) { 00232 print(F); 00233 unsigned NumCalls = shouldPrintAuxCalls() ? 00234 getAuxFunctionCalls().size() : getFunctionCalls().size(); 00235 O << " [" << getGraphSize() << "+" << NumCalls << "]\n"; 00236 } else { 00237 O << " error opening file for writing!\n"; 00238 } 00239 } 00240 00241 /// viewGraph - Emit a dot graph, run 'dot', run gv on the postscript file, 00242 /// then cleanup. For use from the debugger. 00243 /// 00244 void DSGraph::viewGraph() const { 00245 std::ofstream F("/tmp/tempgraph.dot"); 00246 if (!F.good()) { 00247 std::cerr << "Error opening '/tmp/tempgraph.dot' for temporary graph!\n"; 00248 return; 00249 } 00250 print(F); 00251 F.close(); 00252 if (system("dot -Tps -Gsize=10,7.5 -Grotate=90 /tmp/tempgraph.dot > /tmp/tempgraph.ps")) 00253 std::cerr << "Error running dot: 'dot' not in path?\n"; 00254 system("gv /tmp/tempgraph.ps"); 00255 system("rm /tmp/tempgraph.dot /tmp/tempgraph.ps"); 00256 } 00257 00258 00259 template <typename Collection> 00260 static void printCollection(const Collection &C, std::ostream &O, 00261 const Module *M, const std::string &Prefix) { 00262 if (M == 0) { 00263 O << "Null Module pointer, cannot continue!\n"; 00264 return; 00265 } 00266 00267 unsigned TotalNumNodes = 0, TotalCallNodes = 0; 00268 for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) 00269 if (C.hasGraph(*I)) { 00270 DSGraph &Gr = C.getDSGraph((Function&)*I); 00271 TotalNumNodes += Gr.getGraphSize(); 00272 unsigned NumCalls = Gr.shouldPrintAuxCalls() ? 00273 Gr.getAuxFunctionCalls().size() : Gr.getFunctionCalls().size(); 00274 00275 TotalCallNodes += NumCalls; 00276 if (I->getName() == "main" || !OnlyPrintMain) 00277 Gr.writeGraphToFile(O, Prefix+I->getName()); 00278 else { 00279 O << "Skipped Writing '" << Prefix+I->getName() << ".dot'... [" 00280 << Gr.getGraphSize() << "+" << NumCalls << "]\n"; 00281 } 00282 00283 unsigned GraphSize = Gr.getGraphSize(); 00284 if (MaxGraphSize < GraphSize) MaxGraphSize = GraphSize; 00285 00286 for (DSGraph::node_iterator NI = Gr.node_begin(), E = Gr.node_end(); 00287 NI != E; ++NI) 00288 if ((*NI)->isNodeCompletelyFolded()) 00289 ++NumFoldedNodes; 00290 } 00291 00292 DSGraph &GG = C.getGlobalsGraph(); 00293 TotalNumNodes += GG.getGraphSize(); 00294 TotalCallNodes += GG.getFunctionCalls().size(); 00295 if (!OnlyPrintMain) { 00296 GG.writeGraphToFile(O, Prefix+"GlobalsGraph"); 00297 } else { 00298 O << "Skipped Writing '" << Prefix << "GlobalsGraph.dot'... [" 00299 << GG.getGraphSize() << "+" << GG.getFunctionCalls().size() << "]\n"; 00300 } 00301 00302 O << "\nGraphs contain [" << TotalNumNodes << "+" << TotalCallNodes 00303 << "] nodes total" << std::endl; 00304 } 00305 00306 00307 // print - Print out the analysis results... 00308 void LocalDataStructures::print(std::ostream &O, const Module *M) const { 00309 if (DontPrintAnything) return; 00310 printCollection(*this, O, M, "ds."); 00311 } 00312 00313 void BUDataStructures::print(std::ostream &O, const Module *M) const { 00314 if (DontPrintAnything) return; 00315 printCollection(*this, O, M, "bu."); 00316 } 00317 00318 void TDDataStructures::print(std::ostream &O, const Module *M) const { 00319 if (DontPrintAnything) return; 00320 printCollection(*this, O, M, "td."); 00321 } 00322 00323 void CompleteBUDataStructures::print(std::ostream &O, const Module *M) const { 00324 if (DontPrintAnything) return; 00325 printCollection(*this, O, M, "cbu."); 00326 } 00327 00328