lib/Transforms/Instrumentation/MaximumSpanningTree.h

   1 //===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H
  16 #define LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H
  17
  18 #include "llvm/ADT/EquivalenceClasses.h"
  19 #include "llvm/IR/BasicBlock.h"
  20 #include <algorithm>
  21 #include <vector>
  22
  23 namespace llvm {
  24
  25   /// MaximumSpanningTree - A MST implementation.
  26   /// The type parameter T determines the type of the nodes of the graph.
  27   template <typename T>
  28   class MaximumSpanningTree {
  29   public:
  30     typedef std::pair<const T*, const T*> Edge;
  31     typedef std::pair<Edge, double> EdgeWeight;
  32     typedef std::vector<EdgeWeight> EdgeWeights;
  33   protected:
  34     typedef std::vector<Edge> MaxSpanTree;
  35
  36     MaxSpanTree MST;
  37
  38   private:
  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;
  44       }
  45
  46       bool operator()(EdgeWeight X, EdgeWeight Y) const {
  47         if (X.second > Y.second) return true;
  48         if (X.second < Y.second) return false;
  49
  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;
  55
  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;
  60
  61         return false;
  62       }
  63     };
  64
  65   public:
  66     static char ID; // Class identification, replacement for typeinfo
  67
  68     /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a
  69     /// spanning tree.
  70     MaximumSpanningTree(EdgeWeights &EdgeVector) {
  71
  72       std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare());
  73
  74       // Create spanning tree, Forest contains a special data structure
  75       // that makes checking if two nodes are already in a common (sub-)tree
  76       // fast and cheap.
  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;
  81
  82         Forest.insert(e.first);
  83         Forest.insert(e.second);
  84       }
  85
  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;
  90
  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.
  95           MST.push_back(e);
  96         }
  97       }
  98     }
  99
 100     typename MaxSpanTree::iterator begin() {
 101       return MST.begin();
 102     }
 103
 104     typename MaxSpanTree::iterator end() {
 105       return MST.end();
 106     }
 107   };
 108
 109 } // End llvm namespace
 110
 111 #endif