Added GraphTraits to source-level CFGs (CFG and CFGBlock) to allow

(LLVM-provided) graph algorithms such as DFS and graph visualization
to work effortless on source-level CFGs.

Further cleanup on pretty printing of CFGs.  CFGBlock::dump and
CFGBlock::print now take the parent CFG as an argument.  This allows
CFGBlocks to print their own appropriate label indicating whether or
not they are the Entry/Exit/IndirectGotoBlock without the CFG::print
routine doing it instead.

Added Graphviz visualization for CFGs: CFG::viewCFG.  This employs the
GraphTraits just implemented.

Added "-view-cfg" mode the to clang driver.  This is identical to
"-dump-cfg" except that it calls Graphviz to visualize the CFGs
instead of dumping them to the terminal.


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@41580 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 182 insertions, 43 deletions

diff --git a/AST/CFG.cpp b/AST/CFG.cpp
index 79195a3850..2d6e240943 100644
--- a/AST/CFG.cpp
+++ b/AST/CFG.cpp
@@ -17,9 +17,13 @@
 #include "clang/AST/StmtVisitor.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Support/GraphWriter.h"
+#include "llvm/Config/config.h"
 #include <iostream>
 #include <iomanip>
 #include <algorithm>
+#include <sstream>
+
 using namespace clang;
 
 namespace {
@@ -871,44 +875,33 @@ CFG* CFG::buildCFG(Stmt* Statement) {
 /// reverseStmts - Reverses the orders of statements within a CFGBlock.
 void CFGBlock::reverseStmts() { std::reverse(Stmts.begin(),Stmts.end()); }
 
+
+//===----------------------------------------------------------------------===//
+// CFG pretty printing
+//===----------------------------------------------------------------------===//
+
 /// dump - A simple pretty printer of a CFG that outputs to stderr.
-void CFG::dump() { print(std::cerr); }
+void CFG::dump() const { print(std::cerr); }
 
 /// print - A simple pretty printer of a CFG that outputs to an ostream.
-void CFG::print(std::ostream& OS) {
-  // Print the Entry block.
-  if (begin() != end()) {
-    CFGBlock& Entry = getEntry();
-    OS << "\n [ B" << Entry.getBlockID() << " (ENTRY) ]\n";
-    Entry.print(OS);
-  }
+void CFG::print(std::ostream& OS) const {
+  
+  // Print the entry block.
+  getEntry().print(OS,this);
 
   // Iterate through the CFGBlocks and print them one by one.
-  for (iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
+  for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
     // Skip the entry block, because we already printed it.
     if (&(*I) == &getEntry() || &(*I) == &getExit()) continue;
-      
-    OS << "\n  [ B" << I->getBlockID();
-
-    if (&(*I) == getIndirectGotoBlock())
-      OS << " (INDIRECT GOTO DISPATCH) ]\n";
-    else
-      OS << " ]\n";
-      
-    I->print(OS);
+    I->print(OS,this);
   }
-
-  // Print the Exit Block.  
-  if (begin() != end()) {
-    CFGBlock& Exit = getExit();
-    OS << "\n [ B" << Exit.getBlockID() << " (EXIT) ]\n";
-    Exit.print(OS);
-  }    
+  
+  // Print the exit block.
+  getExit().print(OS,this);
 
   OS << "\n";
 }
 
-
 namespace {
 
 class CFGBlockTerminatorPrint : public StmtVisitor<CFGBlockTerminatorPrint,
@@ -919,7 +912,7 @@ public:
   
   void VisitIfStmt(IfStmt* I) {
     OS << "if ";
-    I->getCond()->printPretty(std::cerr);
+    I->getCond()->printPretty(OS);
     OS << "\n";
   }
   
@@ -962,16 +955,25 @@ public:
 } // end anonymous namespace
 
 /// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
-void CFGBlock::dump() { print(std::cerr); }
+void CFGBlock::dump(const CFG* cfg) const { print(std::cerr,cfg); }
 
 /// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
 ///   Generally this will only be called from CFG::print.
-void CFGBlock::print(std::ostream& OS) {
+void CFGBlock::print(std::ostream& OS, const CFG* cfg) const {
+
+  // Print the header.
+  OS << "\n [ B" << getBlockID();  
+  if (this == &cfg->getEntry()) { OS << " (ENTRY) ]\n"; }
+  else if (this == &cfg->getExit()) { OS << " (EXIT) ]\n"; }
+  else if (this == cfg->getIndirectGotoBlock()) { 
+    OS << " (INDIRECT GOTO DISPATCH) ]\n";
+  }
+  else OS << " ]\n";
 
   // Iterate through the statements in the block and print them.
   OS << "    ------------------------\n";
   unsigned j = 1;
-  for (iterator I = Stmts.begin(), E = Stmts.end() ; I != E ; ++I, ++j ) {
+  for (const_iterator I = Stmts.begin(), E = Stmts.end() ; I != E ; ++I, ++j ) {
     // Print the statement # in the basic block.
     OS << "    " << std::setw(3) << j << ": ";    
 
@@ -991,7 +993,7 @@ void CFGBlock::print(std::ostream& OS) {
   // Print the predecessors of this block.
   OS << "    Predecessors (" << pred_size() << "):";
   unsigned i = 0;
-  for (pred_iterator I = pred_begin(), E = pred_end(); I != E; ++I, ++i ) {
+  for (const_pred_iterator I = pred_begin(), E = pred_end(); I != E; ++I, ++i) {
     if (i == 8 || (i-8) == 0) {
       OS << "\n     ";
     }
@@ -1008,7 +1010,7 @@ void CFGBlock::print(std::ostream& OS) {
   // Print the successors of this block.
   OS << "    Successors (" << succ_size() << "):";
   i = 0;
-  for (succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I, ++i ) {
+  for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I, ++i) {
     if (i == 8 || (i-8) % 10 == 0) {
       OS << "\n    ";
     }
@@ -1016,3 +1018,39 @@ void CFGBlock::print(std::ostream& OS) {
   }
   OS << '\n';
 }
+
+//===----------------------------------------------------------------------===//
+// CFG Graphviz Visualization
+//===----------------------------------------------------------------------===//
+
+namespace llvm {
+template<>
+struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits {
+  static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph) {
+
+    std::ostringstream Out;
+    Node->print(Out,Graph);
+    std::string OutStr = Out.str();
+
+    if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
+
+    // Process string output to make it nicer...
+    for (unsigned i = 0; i != OutStr.length(); ++i)
+      if (OutStr[i] == '\n') {                            // Left justify
+        OutStr[i] = '\\';
+        OutStr.insert(OutStr.begin()+i+1, 'l');
+      }
+      
+    return OutStr;
+  }
+};
+} // end namespace llvm
+
+void CFG::viewCFG() const {
+#ifndef NDEBUG
+  llvm::ViewGraph(this,"CFG");
+#else
+  std::cerr << "CFG::viewCFG is only available in debug builds on "
+            << "systems with Graphviz or gv!" << std::endl;
+#endif
+}
diff --git a/Driver/ASTStreamers.cpp b/Driver/ASTStreamers.cpp
index c819623f41..5e78e033c9 100644
--- a/Driver/ASTStreamers.cpp
+++ b/Driver/ASTStreamers.cpp
@@ -155,7 +155,9 @@ void clang::DumpASTs(Preprocessor &PP, unsigned MainFileID, bool Stats) {
   ASTStreamer_Terminate(Streamer);
 }
 
-void clang::DumpCFGs(Preprocessor &PP, unsigned MainFileID, bool Stats) {
+void clang::DumpCFGs(Preprocessor &PP, unsigned MainFileID,
+                     bool Stats, bool use_graphviz) 
+{
   ASTContext Context(PP.getTargetInfo(), PP.getIdentifierTable());
   ASTStreamerTy *Streamer = ASTStreamer_Init(PP, Context, MainFileID);
   
@@ -164,8 +166,9 @@ void clang::DumpCFGs(Preprocessor &PP, unsigned MainFileID, bool Stats) {
       if (FD->getBody()) {
         PrintFunctionDeclStart(FD);
         fprintf(stderr,"\n");
-        if (CFG* C = CFG::buildCFG(FD->getBody()))
-          C->dump();
+        if (CFG* C = CFG::buildCFG(FD->getBody())) {
+          if (use_graphviz) C->viewCFG(); else C->dump();
+        }
         else
           fprintf(stderr," Error processing CFG.\n");
       }
diff --git a/Driver/ASTStreamers.h b/Driver/ASTStreamers.h
index 6e90e2f683..dfd9d54239 100644
--- a/Driver/ASTStreamers.h
+++ b/Driver/ASTStreamers.h
@@ -23,7 +23,9 @@ class TypedefDecl;
 void BuildASTs(Preprocessor &PP, unsigned MainFileID, bool Stats);
 void PrintASTs(Preprocessor &PP, unsigned MainFileID, bool Stats);
 void DumpASTs(Preprocessor &PP, unsigned MainFileID, bool Stats);
-void DumpCFGs(Preprocessor &PP, unsigned MainFileID, bool Stats);  
+
+void DumpCFGs(Preprocessor &PP, unsigned MainFileID,
+              bool Stats, bool use_graphviz = false);  
 
 } // end clang namespace
 
diff --git a/Driver/clang.cpp b/Driver/clang.cpp
index 14f48870e5..2bb4422b75 100644
--- a/Driver/clang.cpp
+++ b/Driver/clang.cpp
@@ -53,6 +53,7 @@ enum ProgActions {
   ParseASTCheck,                // Parse ASTs and check diagnostics.
   ParseAST,                     // Parse ASTs.
   ParseCFGDump,                 // Parse ASTS. Build CFGs. Print CFGs.
+  ParseCFGView,                 // Parse ASTS. Build CFGs. View CFGs (Graphviz).
   ParsePrintCallbacks,          // Parse and print each callback.
   ParseSyntaxOnly,              // Parse and perform semantic analysis.
   ParseNoop,                    // Parse with noop callbacks.
@@ -86,7 +87,9 @@ ProgAction(llvm::cl::desc("Choose output type:"), llvm::cl::ZeroOrMore,
              clEnumValN(ParseASTCheck, "parse-ast-check",
                         "Run parser, build ASTs, then check diagnostics"),
              clEnumValN(ParseCFGDump, "dump-cfg",
-                        "Run parser, build ASTs, then build and print CFGs."),
+                        "Run parser, then build and print CFGs."),
+             clEnumValN(ParseCFGView, "view-cfg",
+                        "Run parser, then build and view CFGs with Graphviz."),  
              clEnumValN(EmitLLVM, "emit-llvm",
                         "Build ASTs then convert to LLVM, emit .ll file"),
              clEnumValEnd));
@@ -840,6 +843,9 @@ static void ProcessInputFile(Preprocessor &PP, unsigned MainFileID,
   case ParseCFGDump:
     DumpCFGs(PP, MainFileID, Stats);
     break;
+  case ParseCFGView:
+    DumpCFGs(PP, MainFileID, Stats, true);
+    break;
   case EmitLLVM:
     EmitLLVMFromASTs(PP, MainFileID, Stats);
     break;
diff --git a/include/clang/AST/CFG.h b/include/clang/AST/CFG.h
index 80009d841d..18157d1363 100644
--- a/include/clang/AST/CFG.h
+++ b/include/clang/AST/CFG.h
@@ -12,6 +12,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/GraphTraits.h"
 #include <list>
 #include <vector>
 #include <iosfwd>
@@ -19,6 +20,7 @@
 namespace clang {
 
 class Stmt;
+class CFG;
   
 /// CFGBlock - Represents a single basic block in a source-level CFG.
 ///  It consists of:
@@ -139,8 +141,8 @@ public:
   
   unsigned getBlockID() const { return BlockID; }
   
-  void dump();
-  void print(std::ostream& OS);
+  void dump(const CFG* cfg) const;
+  void print(std::ostream& OS, const CFG* cfg) const;
 };
   
 
@@ -183,17 +185,105 @@ public:
   const_reverse_iterator    rend()        const    { return Blocks.rend(); }
   
   CFGBlock&                 getEntry()             { return *Entry; }
+  const CFGBlock&           getEntry()    const    { return *Entry; }
   CFGBlock&                 getExit()              { return *Exit; }
-  CFGBlock*                 getIndirectGotoBlock() { return IndirectGotoBlock; }
+  const CFGBlock&           getExit()     const    { return *Exit; }
+
+  CFGBlock*        getIndirectGotoBlock() { return IndirectGotoBlock; }
+  const CFGBlock*  getIndirectGotoBlock() const { return IndirectGotoBlock; }
   
   // Utility
   
   CFGBlock* createBlock(unsigned blockID);
   static CFG* buildCFG(Stmt* AST);
-  void print(std::ostream& OS);
-  void dump();
+  void viewCFG() const;
+  void print(std::ostream& OS) const;
+  void dump() const;
   void setEntry(CFGBlock *B) { Entry = B; }
   void setIndirectGotoBlock(CFGBlock* B) { IndirectGotoBlock = B; }   
 };
-
 } // end namespace clang
+
+//===----------------------------------------------------------------------===//
+// GraphTraits specializations for CFG basic block graphs (source-level CFGs)
+//===----------------------------------------------------------------------===//
+
+namespace llvm {
+
+// Traits for: CFGBlock
+
+template <> struct GraphTraits<clang::CFGBlock* > {
+  typedef clang::CFGBlock NodeType;
+  typedef clang::CFGBlock::succ_iterator ChildIteratorType;
+  
+  static NodeType* getEntryNode(clang::CFGBlock* BB)
+  { return BB; }
+
+  static inline ChildIteratorType child_begin(NodeType* N)
+  { return N->succ_begin(); }
+    
+  static inline ChildIteratorType child_end(NodeType* N)
+  { return N->succ_end(); }
+};
+
+template <> struct GraphTraits<const clang::CFGBlock* > {
+  typedef const clang::CFGBlock NodeType;
+  typedef clang::CFGBlock::const_succ_iterator ChildIteratorType;
+  
+  static NodeType* getEntryNode(const clang::CFGBlock* BB)
+  { return BB; }
+  
+  static inline ChildIteratorType child_begin(NodeType* N)
+  { return N->succ_begin(); }
+  
+  static inline ChildIteratorType child_end(NodeType* N)
+  { return N->succ_end(); }
+};
+
+template <> struct GraphTraits<Inverse<const clang::CFGBlock*> > {
+  typedef const clang::CFGBlock NodeType;
+  typedef clang::CFGBlock::const_pred_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(Inverse<const clang::CFGBlock*> G)
+  { return G.Graph; }
+
+  static inline ChildIteratorType child_begin(NodeType* N)
+  { return N->pred_begin(); }
+  
+  static inline ChildIteratorType child_end(NodeType* N)
+  { return N->pred_end(); }
+};
+
+// Traits for: CFG
+
+template <> struct GraphTraits<clang::CFG* > 
+            : public GraphTraits<clang::CFGBlock* >  {
+
+  typedef clang::CFG::iterator nodes_iterator;
+  
+  static NodeType *getEntryNode(clang::CFG* F) { return &F->getEntry(); }  
+  static nodes_iterator nodes_begin(clang::CFG* F) { return F->begin(); }
+  static nodes_iterator nodes_end(clang::CFG* F) { return F->end(); }
+};
+
+template <> struct GraphTraits< const clang::CFG* > 
+            : public GraphTraits< const clang::CFGBlock* >  {
+
+  typedef clang::CFG::const_iterator nodes_iterator;            
+
+  static NodeType *getEntryNode( const clang::CFG* F) { return &F->getEntry(); }
+  static nodes_iterator nodes_begin( const clang::CFG* F) { return F->begin(); }
+  static nodes_iterator nodes_end( const clang::CFG* F) { return F->end(); }
+};
+
+template <> struct GraphTraits<Inverse<const clang::CFG*> >
+            : public GraphTraits<Inverse<const clang::CFGBlock*> > {
+
+  typedef clang::CFG::const_iterator nodes_iterator;
+
+  static NodeType *getEntryNode(const clang::CFG* F) { return &F->getExit(); }
+  static nodes_iterator nodes_begin(const clang::CFG* F) { return F->begin();}
+  static nodes_iterator nodes_end(const clang::CFG* F) { return F->end(); }
+};
+  
+} // end llvm namespace