1198090Srdivacky//===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===// 2198090Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6198090Srdivacky// 7198090Srdivacky//===----------------------------------------------------------------------===// 8198090Srdivacky// 9221345Sdim// This module provides means for calculating a maximum spanning tree for a 10198090Srdivacky// given set of weighted edges. The type parameter T is the type of a node. 11198090Srdivacky// 12198090Srdivacky//===----------------------------------------------------------------------===// 13198090Srdivacky 14321369Sdim#ifndef LLVM_LIB_TRANSFORMS_INSTRUMENTATION_MAXIMUMSPANNINGTREE_H 15321369Sdim#define LLVM_LIB_TRANSFORMS_INSTRUMENTATION_MAXIMUMSPANNINGTREE_H 16198090Srdivacky 17198090Srdivacky#include "llvm/ADT/EquivalenceClasses.h" 18249423Sdim#include "llvm/IR/BasicBlock.h" 19249423Sdim#include <algorithm> 20198090Srdivacky#include <vector> 21198090Srdivacky 22198090Srdivackynamespace llvm { 23198090Srdivacky 24198090Srdivacky /// MaximumSpanningTree - A MST implementation. 25198090Srdivacky /// The type parameter T determines the type of the nodes of the graph. 26198090Srdivacky template <typename T> 27198090Srdivacky class MaximumSpanningTree { 28243830Sdim public: 29243830Sdim typedef std::pair<const T*, const T*> Edge; 30243830Sdim typedef std::pair<Edge, double> EdgeWeight; 31243830Sdim typedef std::vector<EdgeWeight> EdgeWeights; 32243830Sdim protected: 33243830Sdim typedef std::vector<Edge> MaxSpanTree; 34198090Srdivacky 35243830Sdim MaxSpanTree MST; 36243830Sdim 37243830Sdim private: 38198090Srdivacky // A comparing class for comparing weighted edges. 39198090Srdivacky struct EdgeWeightCompare { 40243830Sdim static bool getBlockSize(const T *X) { 41243830Sdim const BasicBlock *BB = dyn_cast_or_null<BasicBlock>(X); 42243830Sdim return BB ? BB->size() : 0; 43243830Sdim } 44243830Sdim 45243830Sdim bool operator()(EdgeWeight X, EdgeWeight Y) const { 46198090Srdivacky if (X.second > Y.second) return true; 47198090Srdivacky if (X.second < Y.second) return false; 48243830Sdim 49243830Sdim // Equal edge weights: break ties by comparing block sizes. 50243830Sdim size_t XSizeA = getBlockSize(X.first.first); 51243830Sdim size_t YSizeA = getBlockSize(Y.first.first); 52243830Sdim if (XSizeA > YSizeA) return true; 53243830Sdim if (XSizeA < YSizeA) return false; 54243830Sdim 55243830Sdim size_t XSizeB = getBlockSize(X.first.second); 56243830Sdim size_t YSizeB = getBlockSize(Y.first.second); 57243830Sdim if (XSizeB > YSizeB) return true; 58243830Sdim if (XSizeB < YSizeB) return false; 59243830Sdim 60198090Srdivacky return false; 61198090Srdivacky } 62198090Srdivacky }; 63198090Srdivacky 64198090Srdivacky public: 65198090Srdivacky static char ID; // Class identification, replacement for typeinfo 66198090Srdivacky 67198090Srdivacky /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a 68198090Srdivacky /// spanning tree. 69198090Srdivacky MaximumSpanningTree(EdgeWeights &EdgeVector) { 70353358Sdim llvm::stable_sort(EdgeVector, EdgeWeightCompare()); 71198090Srdivacky 72198090Srdivacky // Create spanning tree, Forest contains a special data structure 73198090Srdivacky // that makes checking if two nodes are already in a common (sub-)tree 74198090Srdivacky // fast and cheap. 75198090Srdivacky EquivalenceClasses<const T*> Forest; 76198090Srdivacky for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 77198090Srdivacky EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 78198090Srdivacky Edge e = (*EWi).first; 79198090Srdivacky 80198090Srdivacky Forest.insert(e.first); 81198090Srdivacky Forest.insert(e.second); 82198090Srdivacky } 83198090Srdivacky 84198090Srdivacky // Iterate over the sorted edges, biggest first. 85198090Srdivacky for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 86198090Srdivacky EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 87198090Srdivacky Edge e = (*EWi).first; 88198090Srdivacky 89198090Srdivacky if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) { 90198090Srdivacky Forest.unionSets(e.first, e.second); 91198090Srdivacky // So we know now that the edge is not already in a subtree, so we push 92198090Srdivacky // the edge to the MST. 93198090Srdivacky MST.push_back(e); 94198090Srdivacky } 95198090Srdivacky } 96198090Srdivacky } 97198090Srdivacky 98198090Srdivacky typename MaxSpanTree::iterator begin() { 99198090Srdivacky return MST.begin(); 100198090Srdivacky } 101198090Srdivacky 102198090Srdivacky typename MaxSpanTree::iterator end() { 103198090Srdivacky return MST.end(); 104198090Srdivacky } 105198090Srdivacky }; 106198090Srdivacky 107198090Srdivacky} // End llvm namespace 108198090Srdivacky 109321369Sdim#endif // LLVM_LIB_TRANSFORMS_INSTRUMENTATION_MAXIMUMSPANNINGTREE_H 110