Add a --check-graph option to llvmc.

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

6 files changed, 195 insertions, 7 deletions

diff --git a/docs/CommandGuide/llvmc.pod b/docs/CommandGuide/llvmc.pod
index 7bfc3d7..17d85d7 100644
--- a/docs/CommandGuide/llvmc.pod
+++ b/docs/CommandGuide/llvmc.pod
@@ -42,6 +42,12 @@ S<-load $LLVM_DIR/Release/lib/LLVMCSimple.so>.
 
 Enable verbose mode, i.e. print out all executed commands.
 
+=item B<--check-graph>
+
+Check the compilation for common errors like mismatched output/input
+language names, multiple default edges and cycles. Hidden option,
+useful for debugging.
+
 =item B<--view-graph>
 
 Show a graphical representation of the compilation graph. Requires
diff --git a/docs/CompilerDriver.html b/docs/CompilerDriver.html
index 7d03990..e49b2e9 100644
--- a/docs/CompilerDriver.html
+++ b/docs/CompilerDriver.html
@@ -107,6 +107,9 @@ until the next -x option.</li>
 <li><tt class="docutils literal"><span class="pre">-load</span> <span class="pre">PLUGIN_NAME</span></tt> - Load the specified plugin DLL. Example:
 <tt class="docutils literal"><span class="pre">-load</span> <span class="pre">$LLVM_DIR/Release/lib/LLVMCSimple.so</span></tt>.</li>
 <li><tt class="docutils literal"><span class="pre">-v</span></tt> - Enable verbose mode, i.e. print out all executed commands.</li>
+<li><tt class="docutils literal"><span class="pre">--check-graph</span></tt> - Check the compilation for common errors like
+mismatched output/input language names, multiple default edges and
+cycles. Hidden option, useful for debugging.</li>
 <li><tt class="docutils literal"><span class="pre">--view-graph</span></tt> - Show a graphical representation of the compilation
 graph. Requires that you have <tt class="docutils literal"><span class="pre">dot</span></tt> and <tt class="docutils literal"><span class="pre">gv</span></tt> programs
 installed. Hidden option, useful for debugging.</li>
@@ -566,6 +569,13 @@ line option <tt class="docutils literal"><span class="pre">--view-graph</span></
 <a class="reference" href="http://pages.cs.wisc.edu/~ghost/">Ghostview</a> are installed. There is also a <tt class="docutils literal"><span class="pre">--dump-graph</span></tt> option that
 creates a Graphviz source file (<tt class="docutils literal"><span class="pre">compilation-graph.dot</span></tt>) in the
 current directory.</p>
+<p>Another useful option is <tt class="docutils literal"><span class="pre">--check-graph</span></tt>. It checks the compilation
+graph for common errors like mismatched output/input language names,
+multiple default edges and cycles. These checks can't be performed at
+compile-time because the plugins can load code dynamically. When
+invoked with <tt class="docutils literal"><span class="pre">--check-graph</span></tt>, <tt class="docutils literal"><span class="pre">llvmc</span></tt> doesn't perform any
+compilation tasks and returns the number of encountered errors as its
+status code.</p>
 <hr />
 <address>
 <a href="http://jigsaw.w3.org/css-validator/check/referer">
diff --git a/include/llvm/CompilerDriver/CompilationGraph.h b/include/llvm/CompilerDriver/CompilationGraph.h
index 029623f..090ff5f 100644
--- a/include/llvm/CompilerDriver/CompilationGraph.h
+++ b/include/llvm/CompilerDriver/CompilationGraph.h
@@ -123,6 +123,9 @@ namespace llvmc {
 
   public:
 
+    typedef nodes_map_type::iterator nodes_iterator;
+    typedef nodes_map_type::const_iterator const_nodes_iterator;
+
     CompilationGraph();
 
     /// insertNode - Insert a new node into the graph. Takes
@@ -137,6 +140,11 @@ namespace llvmc {
     /// options are passed implicitly as global variables.
     int Build(llvm::sys::Path const& TempDir, const LanguageMap& LangMap);
 
+    /// Check - Check the compilation graph for common errors like
+    /// cycles, input/output language mismatch and multiple default
+    /// edges. Prints error messages and in case it finds any errors.
+    int Check();
+
     /// getNode - Return a reference to the node correponding to the
     /// given tool name. Throws std::runtime_error.
     Node& getNode(const std::string& ToolName);
@@ -171,7 +179,8 @@ namespace llvmc {
                            const llvm::sys::Path& TempDir,
                            const LanguageMap& LangMap) const;
 
-    /// FindToolChain - Find head of the toolchain corresponding to the given file.
+    /// FindToolChain - Find head of the toolchain corresponding to
+    /// the given file.
     const Node* FindToolChain(const llvm::sys::Path& In,
                               const std::string* ForceLanguage,
                               InputLanguagesSet& InLangs,
@@ -187,6 +196,18 @@ namespace llvmc {
     /// TopologicalSortFilterJoinNodes - Call TopologicalSort and
     /// filter the resulting list to include only Join nodes.
     void TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out);
+
+    // Functions used to implement Check().
+
+    /// CheckLanguageNames - Check that output/input language names
+    /// match for all nodes.
+    int CheckLanguageNames() const;
+    /// CheckMultipleDefaultEdges - check that there are no multiple
+    /// default default edges.
+    int CheckMultipleDefaultEdges() const;
+    /// CheckCycles - Check that there are no cycles in the graph.
+    int CheckCycles();
+
   };
 
   // GraphTraits support code.
@@ -194,8 +215,8 @@ namespace llvmc {
   /// NodesIterator - Auxiliary class needed to implement GraphTraits
   /// support. Can be generalised to something like value_iterator
   /// for map-like containers.
-  class NodesIterator : public llvm::StringMap<Node>::iterator {
-    typedef llvm::StringMap<Node>::iterator super;
+  class NodesIterator : public CompilationGraph::nodes_iterator {
+    typedef CompilationGraph::nodes_iterator super;
     typedef NodesIterator ThisType;
     typedef Node* pointer;
     typedef Node& reference;
diff --git a/tools/llvmc/doc/LLVMC-Reference.rst b/tools/llvmc/doc/LLVMC-Reference.rst
index 6189ec2..1c0da18 100644
--- a/tools/llvmc/doc/LLVMC-Reference.rst
+++ b/tools/llvmc/doc/LLVMC-Reference.rst
@@ -92,6 +92,10 @@ configuration libraries:
 
 * ``-v`` - Enable verbose mode, i.e. print out all executed commands.
 
+* ``--check-graph`` - Check the compilation for common errors like
+  mismatched output/input language names, multiple default edges and
+  cycles. Hidden option, useful for debugging.
+
 * ``--view-graph`` - Show a graphical representation of the compilation
   graph. Requires that you have ``dot`` and ``gv`` programs
   installed. Hidden option, useful for debugging.
@@ -605,6 +609,14 @@ Ghostview_ are installed. There is also a ``--dump-graph`` option that
 creates a Graphviz source file (``compilation-graph.dot``) in the
 current directory.
 
+Another useful option is ``--check-graph``. It checks the compilation
+graph for common errors like mismatched output/input language names,
+multiple default edges and cycles. These checks can't be performed at
+compile-time because the plugins can load code dynamically. When
+invoked with ``--check-graph``, ``llvmc`` doesn't perform any
+compilation tasks and returns the number of encountered errors as its
+status code.
+
 .. _Graphviz: http://www.graphviz.org/
 .. _Ghostview: http://pages.cs.wisc.edu/~ghost/
 
diff --git a/tools/llvmc/driver/CompilationGraph.cpp b/tools/llvmc/driver/CompilationGraph.cpp
index 758268f..2c59ee6 100644
--- a/tools/llvmc/driver/CompilationGraph.cpp
+++ b/tools/llvmc/driver/CompilationGraph.cpp
@@ -20,6 +20,8 @@
 #include "llvm/Support/GraphWriter.h"
 
 #include <algorithm>
+#include <cstring>
+#include <iostream>
 #include <iterator>
 #include <limits>
 #include <queue>
@@ -333,6 +335,135 @@ int CompilationGraph::Build (const sys::Path& TempDir,
   return 0;
 }
 
+int CompilationGraph::CheckLanguageNames() const {
+  int ret = 0;
+  // Check that names for output and input languages on all edges do match.
+  for (const_nodes_iterator B = this->NodesMap.begin(),
+         E = this->NodesMap.end(); B != E; ++B) {
+
+    const Node & N1 = B->second;
+    if (N1.ToolPtr) {
+      for (Node::const_iterator EB = N1.EdgesBegin(), EE = N1.EdgesEnd();
+           EB != EE; ++EB) {
+        const Node& N2 = this->getNode((*EB)->ToolName());
+
+        if (!N2.ToolPtr) {
+          ++ret;
+          std::cerr << "Error: there is an edge from '" << N1.ToolPtr->Name()
+                    << "' back to the root!\n\n";
+          continue;
+        }
+
+        const char* OutLang = N1.ToolPtr->OutputLanguage();
+        const char** InLangs = N2.ToolPtr->InputLanguages();
+        bool eq = false;
+        for (;*InLangs; ++InLangs) {
+          if (std::strcmp(OutLang, *InLangs) == 0) {
+            eq = true;
+            break;
+          }
+        }
+
+        if (!eq) {
+          ++ret;
+          std::cerr << "Error: Output->input language mismatch in the edge '" <<
+            N1.ToolPtr->Name() << "' -> '" << N2.ToolPtr->Name() << "'!\n";
+
+          std::cerr << "Expected one of { ";
+
+          InLangs = N2.ToolPtr->InputLanguages();
+          for (;*InLangs; ++InLangs) {
+            std::cerr << '\'' << *InLangs << (*(InLangs+1) ? "', " : "'");
+          }
+
+          std::cerr << " }, but got '" << OutLang << "'!\n\n";
+        }
+
+      }
+    }
+  }
+
+  return ret;
+}
+
+int CompilationGraph::CheckMultipleDefaultEdges() const {
+  int ret = 0;
+  InputLanguagesSet Dummy;
+
+  for (const_nodes_iterator B = this->NodesMap.begin(),
+         E = this->NodesMap.end(); B != E; ++B) {
+    const Node& N = B->second;
+    unsigned MaxWeight = 0;
+
+    // Ignore the root node.
+    if (!N.ToolPtr)
+      continue;
+
+    for (Node::const_iterator EB = N.EdgesBegin(), EE = N.EdgesEnd();
+         EB != EE; ++EB) {
+      unsigned EdgeWeight = (*EB)->Weight(Dummy);
+      if (EdgeWeight > MaxWeight) {
+        MaxWeight = EdgeWeight;
+      }
+      else if (EdgeWeight == MaxWeight) {
+        ++ret;
+        std::cerr
+          << "Error: there are multiple maximal edges stemming from the '"
+          << N.ToolPtr->Name() << "' node!\n\n";
+        break;
+      }
+    }
+  }
+
+  return ret;
+}
+
+int CompilationGraph::CheckCycles() {
+  unsigned deleted = 0;
+  std::queue<Node*> Q;
+  Q.push(&getNode("root"));
+
+  while (!Q.empty()) {
+    Node* A = Q.front();
+    Q.pop();
+    ++deleted;
+
+    for (Node::iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
+         EB != EE; ++EB) {
+      Node* B = &getNode((*EB)->ToolName());
+      B->DecrInEdges();
+      if (B->HasNoInEdges())
+        Q.push(B);
+    }
+  }
+
+  if (deleted != NodesMap.size()) {
+    std::cerr << "Error: there are cycles in the compilation graph!\n"
+              << "Try inspecting the diagram produced by "
+      "'llvmc --view-graph'.\n\n";
+    return 1;
+  }
+
+  return 0;
+}
+
+
+int CompilationGraph::Check () {
+  // We try to catch as many errors as we can in one go.
+  int ret = 0;
+
+  // Check that output/input language names match.
+  ret += this->CheckLanguageNames();
+
+  // Check for multiple default edges.
+  ret += this->CheckMultipleDefaultEdges();
+
+  // Check for cycles.
+  ret += this->CheckCycles();
+
+  return ret;
+}
+
 // Code related to graph visualization.
 
 namespace llvm {
diff --git a/tools/llvmc/driver/llvmc.cpp b/tools/llvmc/driver/llvmc.cpp
index f3a1e57..b295c63 100644
--- a/tools/llvmc/driver/llvmc.cpp
+++ b/tools/llvmc/driver/llvmc.cpp
@@ -45,6 +45,10 @@ cl::opt<bool> DryRun("dry-run",
                      cl::desc("Only pretend to run commands"));
 cl::opt<bool> VerboseMode("v",
                           cl::desc("Enable verbose mode"));
+
+cl::opt<bool> CheckGraph("check-graph",
+                         cl::desc("Check the compilation graph for errors"),
+                         cl::Hidden);
 cl::opt<bool> WriteGraph("write-graph",
                          cl::desc("Write compilation-graph.dot file"),
                          cl::Hidden);
@@ -89,14 +93,18 @@ int main(int argc, char** argv) {
     Plugins.PopulateLanguageMap(langMap);
     Plugins.PopulateCompilationGraph(graph);
 
-    if (WriteGraph) {
-      graph.writeGraph();
-      if (!ViewGraph)
-        return 0;
+    if (CheckGraph) {
+      return graph.Check();
     }
 
     if (ViewGraph) {
       graph.viewGraph();
+      if (!WriteGraph)
+        return 0;
+    }
+
+    if (WriteGraph) {
+      graph.writeGraph();
       return 0;
     }