//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "maximum-spanning-tree"
#include "MaximumSpanningTree.h"
-#include "llvm/Pass.h"
-#include "llvm/Analysis/Passes.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/CFG.h"
// 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(Function *F, ProfileInfo *PI,
- bool inverted = false) {
+MaximumSpanningTree::MaximumSpanningTree(std::vector<ProfileInfo::EdgeWeight>
+ &EdgeVector) {
- // Copy edges to vector, sort them biggest first.
- ProfileInfo::EdgeWeights ECs = PI->getEdgeWeights(F);
- std::vector<ProfileInfo::EdgeWeight> EdgeVector(ECs.begin(), ECs.end());
std::sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare());
// Create spanning tree, Forest contains a special data structure
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.
- if (!inverted) { MST.push_back(e); }
+ 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.
- if (inverted) { MST.push_back(e); }
printMSTEdge(*bbi,"*not* in MST");
}
}
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Instrumentation.h"
+#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Statistic.h"
#include "MaximumSpanningTree.h"
#include <set>
namespace {
class VISIBILITY_HIDDEN OptimalEdgeProfiler : public ModulePass {
bool runOnModule(Module &M);
- ProfileInfo *PI;
public:
static char ID; // Pass identification, replacement for typeid
OptimalEdgeProfiler() : ModulePass(&ID) {}
// The third parameter of MaximumSpanningTree() has the effect that not the
// actual MST is returned but the edges _not_ in the MST.
- PI = &getAnalysisID<ProfileInfo>(ProfileEstimatorPassID, *F);
- MaximumSpanningTree MST = MaximumSpanningTree(&(*F), PI, true);
+ ProfileInfo::EdgeWeights ECs =
+ getAnalysisID<ProfileInfo>(ProfileEstimatorPassID, *F).getEdgeWeights(F);
+ std::vector<ProfileInfo::EdgeWeight> EdgeVector(ECs.begin(), ECs.end());
+ MaximumSpanningTree MST = MaximumSpanningTree(EdgeVector);
// Check if (0,entry) not in the MST. If not, instrument edge
// (IncrementCounterInBlock()) and set the counter initially to zero, if
BasicBlock *entry = &(F->getEntryBlock());
ProfileInfo::Edge edge = ProfileInfo::getEdge(0,entry);
- if (std::binary_search(MST.begin(), MST.end(), edge)) {
+ if (!std::binary_search(MST.begin(), MST.end(), edge)) {
printEdgeCounter(edge,entry,i);
IncrementCounterInBlock(entry, i, Counters); NumEdgesInserted++;
Initializer[i++] = (zeroc);
// InsertedBlocks contains all blocks that were inserted for splitting an
// edge, this blocks do not have to be instrumented.
- std::set<BasicBlock*> InsertedBlocks;
+ DenseSet<BasicBlock*> InsertedBlocks;
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
// Check if block was not inserted and thus does not have to be
// instrumented.
TerminatorInst *TI = BB->getTerminator();
if (TI->getNumSuccessors() == 0) {
ProfileInfo::Edge edge = ProfileInfo::getEdge(BB,0);
- if (std::binary_search(MST.begin(), MST.end(), edge)) {
+ if (!std::binary_search(MST.begin(), MST.end(), edge)) {
printEdgeCounter(edge,BB,i);
IncrementCounterInBlock(BB, i, Counters); NumEdgesInserted++;
Initializer[i++] = (zeroc);
for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) {
BasicBlock *Succ = TI->getSuccessor(s);
ProfileInfo::Edge edge = ProfileInfo::getEdge(BB,Succ);
- if (std::binary_search(MST.begin(), MST.end(), edge)) {
+ if (!std::binary_search(MST.begin(), MST.end(), edge)) {
// If the edge is critical, split it.
bool wasInserted = SplitCriticalEdge(TI, s, this);
Succ = TI->getSuccessor(s);
- if(wasInserted)
+ if (wasInserted)
InsertedBlocks.insert(Succ);
// Okay, we are guaranteed that the edge is no longer critical. If