1 //===- MaximumSpanningTree.cpp - LLVM Pass to estimate profile info -------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This module privides means for calculating a maximum spanning tree for the
11 // CFG of a function according to a given profile. The tree does not contain
12 // leaf edges, since they are needed for optimal edge profiling.
14 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "maximum-spanning-tree"
16 #include "MaximumSpanningTree.h"
17 #include "llvm/Pass.h"
18 #include "llvm/Analysis/Passes.h"
19 #include "llvm/ADT/EquivalenceClasses.h"
20 #include "llvm/Support/Compiler.h"
21 #include "llvm/Support/CFG.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/Format.h"
27 // compare two weighted edges
28 struct VISIBILITY_HIDDEN EdgeWeightCompare {
29 bool operator()(const ProfileInfo::EdgeWeight X,
30 const ProfileInfo::EdgeWeight Y) const {
31 if (X.second > Y.second) return true;
32 if (X.second < Y.second) return false;
34 // It would be enough to just compare the weights of the edges and be
35 // done. With edges of the same weight this may lead to a different MST
36 // each time the MST is created. To have more stable sorting (and thus
37 // more stable MSTs) furhter sort the edges.
38 if (X.first.first != 0 && Y.first.first == 0) return true;
39 if (X.first.first == 0 && Y.first.first != 0) return false;
40 if (X.first.first == 0 && Y.first.first == 0) return false;
42 if (X.first.first->size() > Y.first.first->size()) return true;
43 if (X.first.first->size() < Y.first.first->size()) return false;
45 if (X.first.second != 0 && Y.first.second == 0) return true;
46 if (X.first.second == 0 && Y.first.second != 0) return false;
47 if (X.first.second == 0 && Y.first.second == 0) return false;
49 if (X.first.second->size() > Y.first.second->size()) return true;
50 if (X.first.second->size() < Y.first.second->size()) return false;
57 static void inline printMSTEdge(ProfileInfo::EdgeWeight E,
59 DEBUG(errs() << "--Edge " << E.first
60 <<" (Weight "<< format("%g",E.second) << ") "
64 // MaximumSpanningTree() - Takes a function and returns a spanning tree
65 // according to the currently active profiling information, the leaf edges are
66 // NOT in the MST. MaximumSpanningTree uses the algorithm of Kruskal.
67 MaximumSpanningTree::MaximumSpanningTree(Function *F, ProfileInfo *PI,
68 bool inverted = false) {
70 // Copy edges to vector, sort them biggest first.
71 ProfileInfo::EdgeWeights ECs = PI->getEdgeWeights(F);
72 std::vector<ProfileInfo::EdgeWeight> EdgeVector(ECs.begin(), ECs.end());
73 std::sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare());
75 // Create spanning tree, Forest contains a special data structure
76 // that makes checking if two nodes are already in a common (sub-)tree
78 EquivalenceClasses<const BasicBlock*> Forest;
79 for (std::vector<ProfileInfo::EdgeWeight>::iterator bbi = EdgeVector.begin(),
80 bbe = EdgeVector.end(); bbi != bbe; ++bbi) {
81 Forest.insert(bbi->first.first);
82 Forest.insert(bbi->first.second);
86 // Iterate over the sorted edges, biggest first.
87 for (std::vector<ProfileInfo::EdgeWeight>::iterator bbi = EdgeVector.begin(),
88 bbe = EdgeVector.end(); bbi != bbe; ++bbi) {
89 ProfileInfo::Edge e = (*bbi).first;
91 if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) {
92 Forest.unionSets(e.first, e.second);
93 // So we know now that the edge is not already in a subtree (and not
94 // (0,entry)), so we push the edge to the MST if it has some successors.
95 if (!inverted) { MST.push_back(e); }
96 printMSTEdge(*bbi,"in MST");
98 // This edge is either (0,entry) or (BB,0) or would create a circle in a
100 if (inverted) { MST.push_back(e); }
101 printMSTEdge(*bbi,"*not* in MST");
105 // Sort the MST edges.
106 std::stable_sort(MST.begin(),MST.end());
109 MaximumSpanningTree::MaxSpanTree::iterator MaximumSpanningTree::begin() {
113 MaximumSpanningTree::MaxSpanTree::iterator MaximumSpanningTree::end() {
117 void MaximumSpanningTree::dump() {
119 for ( MaxSpanTree::iterator ei = MST.begin(), ee = MST.end();
121 errs()<<"("<<((*ei).first?(*ei).first->getNameStr():"0")<<",";
122 errs()<<(*ei).second->getNameStr()<<")";