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