From 026065807999d65746adc1ffdbabcc66ff5472ff Mon Sep 17 00:00:00 2001 From: Mikhail Glushenkov Date: Tue, 6 May 2008 18:07:14 +0000 Subject: Add TopologicalSort method to CompilationGraph. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50743 91177308-0d34-0410-b5e6-96231b3b80d8 --- tools/llvmc2/CompilationGraph.cpp | 90 +++++++++++++++++++++++++-------------- tools/llvmc2/CompilationGraph.h | 19 +++++++-- tools/llvmc2/Tools.td | 2 - tools/llvmc2/llvmc.cpp | 5 ++- 4 files changed, 78 insertions(+), 38 deletions(-) (limited to 'tools/llvmc2') diff --git a/tools/llvmc2/CompilationGraph.cpp b/tools/llvmc2/CompilationGraph.cpp index 079007d255..8f3918f9e4 100644 --- a/tools/llvmc2/CompilationGraph.cpp +++ b/tools/llvmc2/CompilationGraph.cpp @@ -17,6 +17,10 @@ #include "llvm/Support/DOTGraphTraits.h" #include "llvm/Support/GraphWriter.h" +#include +#include +#include +#include #include using namespace llvm; @@ -166,46 +170,70 @@ CompilationGraph::PassThroughGraph (sys::Path& In, return ret; } -int CompilationGraph::Build (const sys::Path& TempDir) const { - const JoinTool* JT = 0; +// Sort the nodes in topological order. +void CompilationGraph::TopologicalSort(std::vector& Out) { + std::queue Q; + Q.push(&getNode("root")); + + while (!Q.empty()) { + const Node* A = Q.front(); + Q.pop(); + Out.push_back(A); + for (Node::const_iterator EB = A->EdgesBegin(), EE = A->EdgesEnd(); + EB != EE; ++EB) { + Node* B = &getNode((*EB)->ToolName()); + B->DecrInEdges(); + if (B->HasNoInEdges()) + Q.push(B); + } + } +} + +namespace { + bool NotJoinNode(const Node* N) { + return N->ToolPtr ? !N->ToolPtr->IsJoin() : true; + } +} + +// Call TopologicalSort and filter the resulting list to include +// only Join nodes. +void CompilationGraph:: +TopologicalSortFilterJoinNodes(std::vector& Out) { + std::vector TopSorted; + TopologicalSort(TopSorted); + std::remove_copy_if(TopSorted.begin(), TopSorted.end(), + std::back_inserter(Out), NotJoinNode); +} + +// Find head of the toolchain corresponding to the given file. +const Node* CompilationGraph::FindToolChain(const sys::Path& In) const { + const std::string& InLanguage = getLanguage(In); + const tools_vector_type& TV = getToolsVector(InLanguage); + if (TV.empty()) + throw std::runtime_error("No toolchain corresponding to language" + + InLanguage + " found!"); + return &getNode(ChooseEdge(TV)->ToolName()); +} + +int CompilationGraph::Build (const sys::Path& TempDir) { // For each input file: for (cl::list::const_iterator B = InputFilenames.begin(), E = InputFilenames.end(); B != E; ++B) { sys::Path In = sys::Path(*B); - // Get to the head of the toolchain. - const std::string& InLanguage = getLanguage(In); - const tools_vector_type& TV = getToolsVector(InLanguage); - if (TV.empty()) - throw std::runtime_error("No toolchain corresponding to language" - + InLanguage + " found!"); - const Node* N = &getNode(ChooseEdge(TV)->ToolName()); - - // Pass it through the chain starting at head. - const JoinTool* NewJoin = PassThroughGraph(In, N, TempDir); - if (JT && NewJoin && JT != NewJoin) - throw std::runtime_error("Graphs with multiple Join nodes" - "are not yet supported!"); - else if (NewJoin) - JT = NewJoin; + // Find the toolchain corresponding to this file. + const Node* N = FindToolChain(In); + // Pass file through the chain starting at head. + PassThroughGraph(In, N, TempDir); } - // For all join nodes in topological order: - // TOFIX: implement. - if (JT) { - sys::Path Out; - // If the final output name is empty, set it to "a.out" - if (!OutputFilename.empty()) { - Out = sys::Path(OutputFilename); - } - else { - Out = sys::Path("a"); - Out.appendSuffix(JT->OutputSuffix()); - } + std::vector JTV; + TopologicalSortFilterJoinNodes(JTV); - if (JT->GenerateAction(Out).Execute() != 0) - throw std::runtime_error("Tool returned error code!"); + // For all join nodes in topological order: + for (std::vector::iterator B = JTV.begin(), E = JTV.end(); + B != E; ++B) { } return 0; diff --git a/tools/llvmc2/CompilationGraph.h b/tools/llvmc2/CompilationGraph.h index bf97857351..dc388d0fa7 100644 --- a/tools/llvmc2/CompilationGraph.h +++ b/tools/llvmc2/CompilationGraph.h @@ -61,7 +61,8 @@ namespace llvmcc { OwningGraph(G), ToolPtr(T), InEdges(0) {} bool HasChildren() const { return !OutEdges.empty(); } - const std::string Name() const { return ToolPtr->Name(); } + const std::string Name() const + { return ToolPtr ? ToolPtr->Name() : "root"; } // Iteration. iterator EdgesBegin() { return OutEdges.begin(); } @@ -75,6 +76,8 @@ namespace llvmcc { // Inward edge counter. Used by Build() to implement topological // sort. + // TOTHINK: Move the counter back into Tool classes? Makes us more + // const-correct. void IncrInEdges() { ++InEdges; } void DecrInEdges() { --InEdges; } bool HasNoInEdges() const { return InEdges == 0; } @@ -82,15 +85,17 @@ namespace llvmcc { // Needed to implement NodeChildIterator/GraphTraits CompilationGraph* OwningGraph; // The corresponding Tool. + // WARNING: For the root node, ToolPtr is NULL. llvm::IntrusiveRefCntPtr ToolPtr; // Links to children. container_type OutEdges; - // Number of parents. + // Number of parents. Used for topological sorting. unsigned InEdges; }; class NodesIterator; + // The compilation graph itself. class CompilationGraph { // Main data structure. typedef llvm::StringMap nodes_map_type; @@ -121,7 +126,7 @@ namespace llvmcc { // Build - Build target(s) from the input file set. Command-line // options are passed implicitly as global variables. - int Build(llvm::sys::Path const& tempDir) const; + int Build(llvm::sys::Path const& tempDir); // Return a reference to the node correponding to the given tool // name. Throws std::runtime_error. @@ -158,6 +163,14 @@ namespace llvmcc { const Node* StartNode, const llvm::sys::Path& TempDir) const; + // Find head of the toolchain corresponding to the given file. + const Node* FindToolChain(const llvm::sys::Path& In) const; + + // Sort the nodes in topological order. + void TopologicalSort(std::vector& Out); + // Call TopologicalSort and filter the resulting list to include + // only Join nodes. + void TopologicalSortFilterJoinNodes(std::vector& Out); }; /// GraphTraits support code. diff --git a/tools/llvmc2/Tools.td b/tools/llvmc2/Tools.td index 76ec856171..67104ec2c7 100644 --- a/tools/llvmc2/Tools.td +++ b/tools/llvmc2/Tools.td @@ -39,8 +39,6 @@ def opt : Tool< [(in_language "llvm-bitcode"), (out_language "llvm-bitcode"), (switch_option "opt", (help "Enable opt")), - //(parameter_option "O", (help "Test Parameter")), - //(prefix_list_option "P", (help "Test Parameter List")), (output_suffix "bc"), (cmd_line "opt $INFILE -o $OUTFILE") ]>; diff --git a/tools/llvmc2/llvmc.cpp b/tools/llvmc2/llvmc.cpp index b991202e43..aeb8b331b4 100644 --- a/tools/llvmc2/llvmc.cpp +++ b/tools/llvmc2/llvmc.cpp @@ -45,7 +45,7 @@ cl::opt ViewGraph("view-graph", cl::Hidden); namespace { - int BuildTargets(const CompilationGraph& graph) { + int BuildTargets(CompilationGraph& graph) { int ret; sys::Path tempDir(sys::Path::GetTemporaryDirectory()); @@ -67,7 +67,7 @@ int main(int argc, char** argv) { CompilationGraph graph; cl::ParseCommandLineOptions(argc, argv, - "LLVM Compiler Driver(Work In Progress)"); + "LLVM Compiler Driver (Work In Progress)"); PopulateCompilationGraph(graph); if (WriteGraph) { @@ -80,6 +80,7 @@ int main(int argc, char** argv) { return 0; } + if (InputFilenames.empty()) { std::cerr << "No input files.\n"; return 1; -- cgit v1.2.3