include/llvm/CodeGen/PBQP/ReductionRules.h

   1 //===- ReductionRules.h - Reduction Rules -----------------------*- 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 // Reduction Rules.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
  14 #define LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
  15
  16 #include "Graph.h"
  17 #include "Math.h"
  18 #include "Solution.h"
  19 #include <cassert>
  20 #include <limits>
  21
  22 namespace llvm {
  23 namespace PBQP {
  24
  25   /// Reduce a node of degree one.
  26   ///
  27   /// Propagate costs from the given node, which must be of degree one, to its
  28   /// neighbor. Notify the problem domain.
  29   template <typename GraphT>
  30   void applyR1(GraphT &G, typename GraphT::NodeId NId) {
  31     using NodeId = typename GraphT::NodeId;
  32     using EdgeId = typename GraphT::EdgeId;
  33     using Vector = typename GraphT::Vector;
  34     using Matrix = typename GraphT::Matrix;
  35     using RawVector = typename GraphT::RawVector;
  36
  37     assert(G.getNodeDegree(NId) == 1 &&
  38            "R1 applied to node with degree != 1.");
  39
  40     EdgeId EId = *G.adjEdgeIds(NId).begin();
  41     NodeId MId = G.getEdgeOtherNodeId(EId, NId);
  42
  43     const Matrix &ECosts = G.getEdgeCosts(EId);
  44     const Vector &XCosts = G.getNodeCosts(NId);
  45     RawVector YCosts = G.getNodeCosts(MId);
  46
  47     // Duplicate a little to avoid transposing matrices.
  48     if (NId == G.getEdgeNode1Id(EId)) {
  49       for (unsigned j = 0; j < YCosts.getLength(); ++j) {
  50         PBQPNum Min = ECosts[0][j] + XCosts[0];
  51         for (unsigned i = 1; i < XCosts.getLength(); ++i) {
  52           PBQPNum C = ECosts[i][j] + XCosts[i];
  53           if (C < Min)
  54             Min = C;
  55         }
  56         YCosts[j] += Min;
  57       }
  58     } else {
  59       for (unsigned i = 0; i < YCosts.getLength(); ++i) {
  60         PBQPNum Min = ECosts[i][0] + XCosts[0];
  61         for (unsigned j = 1; j < XCosts.getLength(); ++j) {
  62           PBQPNum C = ECosts[i][j] + XCosts[j];
  63           if (C < Min)
  64             Min = C;
  65         }
  66         YCosts[i] += Min;
  67       }
  68     }
  69     G.setNodeCosts(MId, YCosts);
  70     G.disconnectEdge(EId, MId);
  71   }
  72
  73   template <typename GraphT>
  74   void applyR2(GraphT &G, typename GraphT::NodeId NId) {
  75     using NodeId = typename GraphT::NodeId;
  76     using EdgeId = typename GraphT::EdgeId;
  77     using Vector = typename GraphT::Vector;
  78     using Matrix = typename GraphT::Matrix;
  79     using RawMatrix = typename GraphT::RawMatrix;
  80
  81     assert(G.getNodeDegree(NId) == 2 &&
  82            "R2 applied to node with degree != 2.");
  83
  84     const Vector &XCosts = G.getNodeCosts(NId);
  85
  86     typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin();
  87     EdgeId YXEId = *AEItr,
  88            ZXEId = *(++AEItr);
  89
  90     NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId),
  91            ZNId = G.getEdgeOtherNodeId(ZXEId, NId);
  92
  93     bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId),
  94          FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId);
  95
  96     const Matrix *YXECosts = FlipEdge1 ?
  97       new Matrix(G.getEdgeCosts(YXEId).transpose()) :
  98       &G.getEdgeCosts(YXEId);
  99
 100     const Matrix *ZXECosts = FlipEdge2 ?
 101       new Matrix(G.getEdgeCosts(ZXEId).transpose()) :
 102       &G.getEdgeCosts(ZXEId);
 103
 104     unsigned XLen = XCosts.getLength(),
 105       YLen = YXECosts->getRows(),
 106       ZLen = ZXECosts->getRows();
 107
 108     RawMatrix Delta(YLen, ZLen);
 109
 110     for (unsigned i = 0; i < YLen; ++i) {
 111       for (unsigned j = 0; j < ZLen; ++j) {
 112         PBQPNum Min = (*YXECosts)[i][0] + (*ZXECosts)[j][0] + XCosts[0];
 113         for (unsigned k = 1; k < XLen; ++k) {
 114           PBQPNum C = (*YXECosts)[i][k] + (*ZXECosts)[j][k] + XCosts[k];
 115           if (C < Min) {
 116             Min = C;
 117           }
 118         }
 119         Delta[i][j] = Min;
 120       }
 121     }
 122
 123     if (FlipEdge1)
 124       delete YXECosts;
 125
 126     if (FlipEdge2)
 127       delete ZXECosts;
 128
 129     EdgeId YZEId = G.findEdge(YNId, ZNId);
 130
 131     if (YZEId == G.invalidEdgeId()) {
 132       YZEId = G.addEdge(YNId, ZNId, Delta);
 133     } else {
 134       const Matrix &YZECosts = G.getEdgeCosts(YZEId);
 135       if (YNId == G.getEdgeNode1Id(YZEId)) {
 136         G.updateEdgeCosts(YZEId, Delta + YZECosts);
 137       } else {
 138         G.updateEdgeCosts(YZEId, Delta.transpose() + YZECosts);
 139       }
 140     }
 141
 142     G.disconnectEdge(YXEId, YNId);
 143     G.disconnectEdge(ZXEId, ZNId);
 144
 145     // TODO: Try to normalize newly added/modified edge.
 146   }
 147
 148 #ifndef NDEBUG
 149   // Does this Cost vector have any register options ?
 150   template <typename VectorT>
 151   bool hasRegisterOptions(const VectorT &V) {
 152     unsigned VL = V.getLength();
 153
 154     // An empty or spill only cost vector does not provide any register option.
 155     if (VL <= 1)
 156       return false;
 157
 158     // If there are registers in the cost vector, but all of them have infinite
 159     // costs, then ... there is no available register.
 160     for (unsigned i = 1; i < VL; ++i)
 161       if (V[i] != std::numeric_limits<PBQP::PBQPNum>::infinity())
 162         return true;
 163
 164     return false;
 165   }
 166 #endif
 167
 168   // Find a solution to a fully reduced graph by backpropagation.
 169   //
 170   // Given a graph and a reduction order, pop each node from the reduction
 171   // order and greedily compute a minimum solution based on the node costs, and
 172   // the dependent costs due to previously solved nodes.
 173   //
 174   // Note - This does not return the graph to its original (pre-reduction)
 175   //        state: the existing solvers destructively alter the node and edge
 176   //        costs. Given that, the backpropagate function doesn't attempt to
 177   //        replace the edges either, but leaves the graph in its reduced
 178   //        state.
 179   template <typename GraphT, typename StackT>
 180   Solution backpropagate(GraphT& G, StackT stack) {
 181     using NodeId = GraphBase::NodeId;
 182     using Matrix = typename GraphT::Matrix;
 183     using RawVector = typename GraphT::RawVector;
 184
 185     Solution s;
 186
 187     while (!stack.empty()) {
 188       NodeId NId = stack.back();
 189       stack.pop_back();
 190
 191       RawVector v = G.getNodeCosts(NId);
 192
 193 #ifndef NDEBUG
 194       // Although a conservatively allocatable node can be allocated to a register,
 195       // spilling it may provide a lower cost solution. Assert here that spilling
 196       // is done by choice, not because there were no register available.
 197       if (G.getNodeMetadata(NId).wasConservativelyAllocatable())
 198         assert(hasRegisterOptions(v) && "A conservatively allocatable node "
 199                                         "must have available register options");
 200 #endif
 201
 202       for (auto EId : G.adjEdgeIds(NId)) {
 203         const Matrix& edgeCosts = G.getEdgeCosts(EId);
 204         if (NId == G.getEdgeNode1Id(EId)) {
 205           NodeId mId = G.getEdgeNode2Id(EId);
 206           v += edgeCosts.getColAsVector(s.getSelection(mId));
 207         } else {
 208           NodeId mId = G.getEdgeNode1Id(EId);
 209           v += edgeCosts.getRowAsVector(s.getSelection(mId));
 210         }
 211       }
 212
 213       s.setSelection(NId, v.minIndex());
 214     }
 215
 216     return s;
 217   }
 218
 219 } // end namespace PBQP
 220 } // end namespace llvm
 221
 222 #endif // LLVM_CODEGEN_PBQP_REDUCTIONRULES_H