From ed1ac4ae8eadb907ec6a41bb74cae1777a4e28d2 Mon Sep 17 00:00:00 2001 From: Andreas Neustifter Date: Fri, 4 Sep 2009 12:34:44 +0000 Subject: Converted MaximumSpanningTree algorithm to a generic template, this could go into llvm/ADT. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81001 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Instrumentation/CMakeLists.txt | 1 - .../Instrumentation/MaximumSpanningTree.cpp | 119 --------------------- .../Instrumentation/MaximumSpanningTree.h | 78 +++++++++++--- .../Instrumentation/OptimalEdgeProfiling.cpp | 4 +- 4 files changed, 64 insertions(+), 138 deletions(-) delete mode 100644 lib/Transforms/Instrumentation/MaximumSpanningTree.cpp (limited to 'lib/Transforms') diff --git a/lib/Transforms/Instrumentation/CMakeLists.txt b/lib/Transforms/Instrumentation/CMakeLists.txt index be6a451f57..494928e438 100644 --- a/lib/Transforms/Instrumentation/CMakeLists.txt +++ b/lib/Transforms/Instrumentation/CMakeLists.txt @@ -1,7 +1,6 @@ add_llvm_library(LLVMInstrumentation BlockProfiling.cpp EdgeProfiling.cpp - MaximumSpanningTree.cpp OptimalEdgeProfiling.cpp ProfilingUtils.cpp RSProfiling.cpp diff --git a/lib/Transforms/Instrumentation/MaximumSpanningTree.cpp b/lib/Transforms/Instrumentation/MaximumSpanningTree.cpp deleted file mode 100644 index 19c4a83f76..0000000000 --- a/lib/Transforms/Instrumentation/MaximumSpanningTree.cpp +++ /dev/null @@ -1,119 +0,0 @@ -//===- MaximumSpanningTree.cpp - LLVM Pass to estimate profile info -------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This module privides means for calculating a maximum spanning tree for the -// CFG of a function according to a given profile. The tree does not contain -// leaf edges, since they are needed for optimal edge profiling. -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "maximum-spanning-tree" -#include "MaximumSpanningTree.h" -#include "llvm/ADT/EquivalenceClasses.h" -#include "llvm/Support/Compiler.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Format.h" -using namespace llvm; - -namespace { - // compare two weighted edges - struct VISIBILITY_HIDDEN EdgeWeightCompare { - bool operator()(const ProfileInfo::EdgeWeight X, - const ProfileInfo::EdgeWeight Y) const { - if (X.second > Y.second) return true; - if (X.second < Y.second) return false; - - // It would be enough to just compare the weights of the edges and be - // done. With edges of the same weight this may lead to a different MST - // each time the MST is created. To have more stable sorting (and thus - // more stable MSTs) furhter sort the edges. - if (X.first.first != 0 && Y.first.first == 0) return true; - if (X.first.first == 0 && Y.first.first != 0) return false; - if (X.first.first == 0 && Y.first.first == 0) return false; - - if (X.first.first->size() > Y.first.first->size()) return true; - if (X.first.first->size() < Y.first.first->size()) return false; - - if (X.first.second != 0 && Y.first.second == 0) return true; - if (X.first.second == 0 && Y.first.second != 0) return false; - if (X.first.second == 0 && Y.first.second == 0) return false; - - if (X.first.second->size() > Y.first.second->size()) return true; - if (X.first.second->size() < Y.first.second->size()) return false; - - return false; - } - }; -} - -static void inline printMSTEdge(ProfileInfo::EdgeWeight E, - const char *M) { - DEBUG(errs() << "--Edge " << E.first - <<" (Weight "<< format("%g",E.second) << ") " - << (M) << "\n"); -} - -// MaximumSpanningTree() - Takes a function and returns a spanning tree -// according to the currently active profiling information, the leaf edges are -// NOT in the MST. MaximumSpanningTree uses the algorithm of Kruskal. -MaximumSpanningTree::MaximumSpanningTree(std::vector - &EdgeVector) { - - std::sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare()); - - // Create spanning tree, Forest contains a special data structure - // that makes checking if two nodes are already in a common (sub-)tree - // fast and cheap. - EquivalenceClasses Forest; - for (std::vector::iterator bbi = EdgeVector.begin(), - bbe = EdgeVector.end(); bbi != bbe; ++bbi) { - Forest.insert(bbi->first.first); - Forest.insert(bbi->first.second); - } - Forest.insert(0); - - // Iterate over the sorted edges, biggest first. - for (std::vector::iterator bbi = EdgeVector.begin(), - bbe = EdgeVector.end(); bbi != bbe; ++bbi) { - ProfileInfo::Edge e = (*bbi).first; - - if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) { - Forest.unionSets(e.first, e.second); - // So we know now that the edge is not already in a subtree (and not - // (0,entry)), so we push the edge to the MST if it has some successors. - MST.push_back(e); - printMSTEdge(*bbi,"in MST"); - } else { - // This edge is either (0,entry) or (BB,0) or would create a circle in a - // subtree. - printMSTEdge(*bbi,"*not* in MST"); - } - } - - // Sort the MST edges. - std::stable_sort(MST.begin(),MST.end()); -} - -MaximumSpanningTree::MaxSpanTree::iterator MaximumSpanningTree::begin() { - return MST.begin(); -} - -MaximumSpanningTree::MaxSpanTree::iterator MaximumSpanningTree::end() { - return MST.end(); -} - -void MaximumSpanningTree::dump() { - errs()<<"{"; - for ( MaxSpanTree::iterator ei = MST.begin(), ee = MST.end(); - ei!=ee; ++ei ) { - errs()<<"("<<((*ei).first?(*ei).first->getNameStr():"0")<<","; - errs()<<(*ei).second->getNameStr()<<")"; - } - errs()<<"}\n"; -} diff --git a/lib/Transforms/Instrumentation/MaximumSpanningTree.h b/lib/Transforms/Instrumentation/MaximumSpanningTree.h index 2343985f23..2951dbcea9 100644 --- a/lib/Transforms/Instrumentation/MaximumSpanningTree.h +++ b/lib/Transforms/Instrumentation/MaximumSpanningTree.h @@ -7,43 +7,87 @@ // //===----------------------------------------------------------------------===// // -// This module privides means for calculating a maximum spanning tree for the -// CFG of a function according to a given profile. +// This module privides means for calculating a maximum spanning tree for a +// given set of weighted edges. The type parameter T is the type of a node. // //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H #define LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H -#include "llvm/Analysis/ProfileInfo.h" -#include "llvm/Support/raw_ostream.h" +#include "llvm/ADT/EquivalenceClasses.h" #include +#include namespace llvm { - class Function; + /// MaximumSpanningTree - A MST implementation. + /// The type parameter T determines the type of the nodes of the graph. + template class MaximumSpanningTree { - public: - typedef std::vector MaxSpanTree; + // A comparing class for comparing weighted edges. + template + struct EdgeWeightCompare { + bool operator()(typename MaximumSpanningTree::EdgeWeight X, + typename MaximumSpanningTree::EdgeWeight Y) const { + if (X.second > Y.second) return true; + if (X.second < Y.second) return false; + return false; + } + }; + + public: + typedef std::pair Edge; + typedef std::pair EdgeWeight; + typedef std::vector EdgeWeights; protected: + typedef std::vector MaxSpanTree; + MaxSpanTree MST; public: static char ID; // Class identification, replacement for typeinfo - // MaxSpanTree() - Calculates a MST for a function according to a profile. - // If inverted is true, all the edges *not* in the MST are returned. As a - // special also all leaf edges of the MST are not included, this makes it - // easier for the OptimalEdgeProfileInstrumentation to use this MST to do - // an optimal profiling. - MaximumSpanningTree(std::vector&); - virtual ~MaximumSpanningTree() {} + /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a + /// spanning tree. + MaximumSpanningTree(EdgeWeights &EdgeVector) { + + std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare()); + + // Create spanning tree, Forest contains a special data structure + // that makes checking if two nodes are already in a common (sub-)tree + // fast and cheap. + EquivalenceClasses Forest; + for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), + EWe = EdgeVector.end(); EWi != EWe; ++EWi) { + Edge e = (*EWi).first; + + Forest.insert(e.first); + Forest.insert(e.second); + } + + // Iterate over the sorted edges, biggest first. + for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), + EWe = EdgeVector.end(); EWi != EWe; ++EWi) { + Edge e = (*EWi).first; + + if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) { + Forest.unionSets(e.first, e.second); + // So we know now that the edge is not already in a subtree, so we push + // the edge to the MST. + MST.push_back(e); + } + } + } - virtual MaxSpanTree::iterator begin(); - virtual MaxSpanTree::iterator end(); + typename MaxSpanTree::iterator begin() { + return MST.begin(); + } - virtual void dump(); + typename MaxSpanTree::iterator end() { + return MST.end(); + } }; } // End llvm namespace diff --git a/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp b/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp index 2c06423872..cdaf5f1b0d 100644 --- a/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp +++ b/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp @@ -17,6 +17,7 @@ #include "llvm/Module.h" #include "llvm/Pass.h" #include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/ProfileInfo.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Support/Debug.h" @@ -131,7 +132,8 @@ bool OptimalEdgeProfiler::runOnModule(Module &M) { ProfileInfo::EdgeWeights ECs = getAnalysisID(ProfileEstimatorPassID, *F).getEdgeWeights(F); std::vector EdgeVector(ECs.begin(), ECs.end()); - MaximumSpanningTree MST = MaximumSpanningTree(EdgeVector); + MaximumSpanningTree MST (EdgeVector); + std::stable_sort(MST.begin(),MST.end()); // Check if (0,entry) not in the MST. If not, instrument edge // (IncrementCounterInBlock()) and set the counter initially to zero, if -- cgit v1.2.3