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 if (X.first.first != 0 && Y.first.first == 0) return true;
35 if (X.first.first == 0 && Y.first.first != 0) return false;
36 if (X.first.first == 0 && Y.first.first == 0) return false;
38 if (X.first.first->size() > Y.first.first->size()) return true;
39 if (X.first.first->size() < Y.first.first->size()) return false;
41 if (X.first.second != 0 && Y.first.second == 0) return true;
42 if (X.first.second == 0 && Y.first.second != 0) return false;
43 if (X.first.second == 0 && Y.first.second == 0) return false;
45 if (X.first.second->size() > Y.first.second->size()) return true;
46 if (X.first.second->size() < Y.first.second->size()) return false;
53 static void inline printMSTEdge(ProfileInfo::EdgeWeight E,
55 DEBUG(errs() << "--Edge " << E.first
56 <<" (Weight "<< format("%g",E.second) << ") "
60 // MaximumSpanningTree() - Takes a function and returns a spanning tree
61 // according to the currently active profiling information, the leaf edges are
62 // NOT in the MST. MaximumSpanningTree uses the algorithm of Kruskal.
63 MaximumSpanningTree::MaximumSpanningTree(Function *F, ProfileInfo *PI,
64 bool inverted = false) {
66 // Copy edges to vector, sort them biggest first.
67 ProfileInfo::EdgeWeights ECs = PI->getEdgeWeights(F);
68 std::vector<ProfileInfo::EdgeWeight> EdgeVector(ECs.begin(), ECs.end());
69 std::sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare());
71 // Create spanning tree, Forest contains a special data structure
72 // that makes checking if two nodes are already in a common (sub-)tree
74 EquivalenceClasses<const BasicBlock*> Forest;
75 for (std::vector<ProfileInfo::EdgeWeight>::iterator bbi = EdgeVector.begin(),
76 bbe = EdgeVector.end(); bbi != bbe; ++bbi) {
77 Forest.insert(bbi->first.first);
78 Forest.insert(bbi->first.second);
82 // Iterate over the sorted edges, biggest first.
83 for (std::vector<ProfileInfo::EdgeWeight>::iterator bbi = EdgeVector.begin(),
84 bbe = EdgeVector.end(); bbi != bbe; ++bbi) {
85 ProfileInfo::Edge e = (*bbi).first;
87 if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) {
88 Forest.unionSets(e.first, e.second);
89 // So we know now that the edge is not already in a subtree (and not
90 // (0,entry)), so we push the edge to the MST if it has some successors.
91 if (!inverted) { MST.push_back(e); }
92 printMSTEdge(*bbi,"in MST");
94 // This edge is either (0,entry) or (BB,0) or would create a circle in a
96 if (inverted) { MST.push_back(e); }
97 printMSTEdge(*bbi,"*not* in MST");
101 // Sort the MST edges.
102 std::stable_sort(MST.begin(),MST.end());
105 MaximumSpanningTree::MaxSpanTree::iterator MaximumSpanningTree::begin() {
109 MaximumSpanningTree::MaxSpanTree::iterator MaximumSpanningTree::end() {
113 void MaximumSpanningTree::dump() {
115 for ( MaxSpanTree::iterator ei = MST.begin(), ee = MST.end();
117 errs()<<"("<<((*ei).first?(*ei).first->getNameStr():"0")<<",";
118 errs()<<(*ei).second->getNameStr()<<")";