1 //===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This module provides means for calculating a maximum spanning tree for a
10 // given set of weighted edges. The type parameter T is the type of a node.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_LIB_TRANSFORMS_INSTRUMENTATION_MAXIMUMSPANNINGTREE_H
15 #define LLVM_LIB_TRANSFORMS_INSTRUMENTATION_MAXIMUMSPANNINGTREE_H
16 
17 #include "llvm/ADT/EquivalenceClasses.h"
18 #include "llvm/IR/BasicBlock.h"
19 #include <algorithm>
20 #include <vector>
21 
22 namespace llvm {
23 
24   /// MaximumSpanningTree - A MST implementation.
25   /// The type parameter T determines the type of the nodes of the graph.
26   template <typename T>
27   class MaximumSpanningTree {
28   public:
29     typedef std::pair<const T*, const T*> Edge;
30     typedef std::pair<Edge, double> EdgeWeight;
31     typedef std::vector<EdgeWeight> EdgeWeights;
32   protected:
33     typedef std::vector<Edge> MaxSpanTree;
34 
35     MaxSpanTree MST;
36 
37   private:
38     // A comparing class for comparing weighted edges.
39     struct EdgeWeightCompare {
getBlockSizeEdgeWeightCompare40       static bool getBlockSize(const T *X) {
41         const BasicBlock *BB = dyn_cast_or_null<BasicBlock>(X);
42         return BB ? BB->size() : 0;
43       }
44 
operatorEdgeWeightCompare45       bool operator()(EdgeWeight X, EdgeWeight Y) const {
46         if (X.second > Y.second) return true;
47         if (X.second < Y.second) return false;
48 
49         // Equal edge weights: break ties by comparing block sizes.
50         size_t XSizeA = getBlockSize(X.first.first);
51         size_t YSizeA = getBlockSize(Y.first.first);
52         if (XSizeA > YSizeA) return true;
53         if (XSizeA < YSizeA) return false;
54 
55         size_t XSizeB = getBlockSize(X.first.second);
56         size_t YSizeB = getBlockSize(Y.first.second);
57         if (XSizeB > YSizeB) return true;
58         if (XSizeB < YSizeB) return false;
59 
60         return false;
61       }
62     };
63 
64   public:
65     static char ID; // Class identification, replacement for typeinfo
66 
67     /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a
68     /// spanning tree.
MaximumSpanningTree(EdgeWeights & EdgeVector)69     MaximumSpanningTree(EdgeWeights &EdgeVector) {
70       llvm::stable_sort(EdgeVector, EdgeWeightCompare());
71 
72       // Create spanning tree, Forest contains a special data structure
73       // that makes checking if two nodes are already in a common (sub-)tree
74       // fast and cheap.
75       EquivalenceClasses<const T*> Forest;
76       for (typename EdgeWeights::iterator EWi = EdgeVector.begin(),
77            EWe = EdgeVector.end(); EWi != EWe; ++EWi) {
78         Edge e = (*EWi).first;
79 
80         Forest.insert(e.first);
81         Forest.insert(e.second);
82       }
83 
84       // Iterate over the sorted edges, biggest first.
85       for (typename EdgeWeights::iterator EWi = EdgeVector.begin(),
86            EWe = EdgeVector.end(); EWi != EWe; ++EWi) {
87         Edge e = (*EWi).first;
88 
89         if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) {
90           Forest.unionSets(e.first, e.second);
91           // So we know now that the edge is not already in a subtree, so we push
92           // the edge to the MST.
93           MST.push_back(e);
94         }
95       }
96     }
97 
begin()98     typename MaxSpanTree::iterator begin() {
99       return MST.begin();
100     }
101 
end()102     typename MaxSpanTree::iterator end() {
103       return MST.end();
104     }
105   };
106 
107 } // End llvm namespace
108 
109 #endif // LLVM_LIB_TRANSFORMS_INSTRUMENTATION_MAXIMUMSPANNINGTREE_H
110