include/llvm/CodeGen/PBQP/ReductionRules.h

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