LLVM  14.0.0git
MaximumSpanningTree.h
Go to the documentation of this file.
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 
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>
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 
36 
37  private:
38  // A comparing class for comparing weighted edges.
39  struct EdgeWeightCompare {
40  static bool getBlockSize(const T *X) {
41  const BasicBlock *BB = dyn_cast_or_null<BasicBlock>(X);
42  return BB ? BB->size() : 0;
43  }
44 
45  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.
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.
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 
98  typename MaxSpanTree::iterator begin() {
99  return MST.begin();
100  }
101 
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
llvm::MaximumSpanningTree::ID
static char ID
Definition: MaximumSpanningTree.h:65
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::MaximumSpanningTree
MaximumSpanningTree - A MST implementation.
Definition: MaximumSpanningTree.h:27
llvm::EquivalenceClasses
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
Definition: EquivalenceClasses.h:59
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::EquivalenceClasses::insert
iterator insert(const ElemTy &Data)
insert - Insert a new value into the union/find set, ignoring the request if the value already exists...
Definition: EquivalenceClasses.h:218
llvm::EquivalenceClasses::findLeader
member_iterator findLeader(iterator I) const
findLeader - Given a value in the set, return a member iterator for the equivalence class it is in.
Definition: EquivalenceClasses.h:226
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::MaximumSpanningTree::MST
MaxSpanTree MST
Definition: MaximumSpanningTree.h:35
llvm::MaximumSpanningTree::Edge
std::pair< const T *, const T * > Edge
Definition: MaximumSpanningTree.h:29
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
BasicBlock.h
llvm::MaximumSpanningTree::MaxSpanTree
std::vector< Edge > MaxSpanTree
Definition: MaximumSpanningTree.h:33
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::MaximumSpanningTree::begin
MaxSpanTree::iterator begin()
Definition: MaximumSpanningTree.h:98
llvm::MaximumSpanningTree::EdgeWeights
std::vector< EdgeWeight > EdgeWeights
Definition: MaximumSpanningTree.h:31
llvm::MaximumSpanningTree::end
MaxSpanTree::iterator end()
Definition: MaximumSpanningTree.h:102
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1716
EquivalenceClasses.h
llvm::MaximumSpanningTree::MaximumSpanningTree
MaximumSpanningTree(EdgeWeights &EdgeVector)
MaximumSpanningTree() - Takes a vector of weighted edges and returns a spanning tree.
Definition: MaximumSpanningTree.h:69
llvm::EquivalenceClasses::unionSets
member_iterator unionSets(const ElemTy &V1, const ElemTy &V2)
union - Merge the two equivalence sets for the specified values, inserting them if they do not alread...
Definition: EquivalenceClasses.h:236
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::MaximumSpanningTree::EdgeWeight
std::pair< Edge, double > EdgeWeight
Definition: MaximumSpanningTree.h:30