]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/Transforms/Instrumentation/MaximumSpanningTree.h
1 //===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===//
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 provides means for calculating a maximum spanning tree for a
11 // given set of weighted edges. The type parameter T is the type of a node.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H
16 #define LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H
18 #include "llvm/ADT/EquivalenceClasses.h"
19 #include "llvm/IR/BasicBlock.h"
25 /// MaximumSpanningTree - A MST implementation.
26 /// The type parameter T determines the type of the nodes of the graph.
28 class MaximumSpanningTree
{
30 typedef std::pair
<const T
*, const T
*> Edge
;
31 typedef std::pair
<Edge
, double> EdgeWeight
;
32 typedef std::vector
<EdgeWeight
> EdgeWeights
;
34 typedef std::vector
<Edge
> MaxSpanTree
;
39 // A comparing class for comparing weighted edges.
40 struct EdgeWeightCompare
{
41 static bool getBlockSize(const T
*X
) {
42 const BasicBlock
*BB
= dyn_cast_or_null
<BasicBlock
>(X
);
43 return BB
? BB
->size() : 0;
46 bool operator()(EdgeWeight X
, EdgeWeight Y
) const {
47 if (X
.second
> Y
.second
) return true;
48 if (X
.second
< Y
.second
) return false;
50 // Equal edge weights: break ties by comparing block sizes.
51 size_t XSizeA
= getBlockSize(X
.first
.first
);
52 size_t YSizeA
= getBlockSize(Y
.first
.first
);
53 if (XSizeA
> YSizeA
) return true;
54 if (XSizeA
< YSizeA
) return false;
56 size_t XSizeB
= getBlockSize(X
.first
.second
);
57 size_t YSizeB
= getBlockSize(Y
.first
.second
);
58 if (XSizeB
> YSizeB
) return true;
59 if (XSizeB
< YSizeB
) return false;
66 static char ID
; // Class identification, replacement for typeinfo
68 /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a
70 MaximumSpanningTree(EdgeWeights
&EdgeVector
) {
72 std::stable_sort(EdgeVector
.begin(), EdgeVector
.end(), EdgeWeightCompare());
74 // Create spanning tree, Forest contains a special data structure
75 // that makes checking if two nodes are already in a common (sub-)tree
77 EquivalenceClasses
<const T
*> Forest
;
78 for (typename
EdgeWeights::iterator EWi
= EdgeVector
.begin(),
79 EWe
= EdgeVector
.end(); EWi
!= EWe
; ++EWi
) {
80 Edge e
= (*EWi
).first
;
82 Forest
.insert(e
.first
);
83 Forest
.insert(e
.second
);
86 // Iterate over the sorted edges, biggest first.
87 for (typename
EdgeWeights::iterator EWi
= EdgeVector
.begin(),
88 EWe
= EdgeVector
.end(); EWi
!= EWe
; ++EWi
) {
89 Edge e
= (*EWi
).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, so we push
94 // the edge to the MST.
100 typename
MaxSpanTree::iterator
begin() {
104 typename
MaxSpanTree::iterator
end() {
109 } // End llvm namespace