CodeGen/PBQP/ReductionRules.h

0001 //===- ReductionRules.h - Reduction Rules -----------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // Reduction Rules.
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
0014 #define LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
0015
0016 #include "Graph.h"
0017 #include "Math.h"
0018 #include "Solution.h"
0019 #include <cassert>
0020 #include <limits>
0021
0022 namespace llvm {
0023 namespace PBQP {
0024
0025   /// Reduce a node of degree one.
0026   ///
0027   /// Propagate costs from the given node, which must be of degree one, to its
0028   /// neighbor. Notify the problem domain.
0029   template <typename GraphT>
0030   void applyR1(GraphT &G, typename GraphT::NodeId NId) {
0031     using NodeId = typename GraphT::NodeId;
0032     using EdgeId = typename GraphT::EdgeId;
0033     using Vector = typename GraphT::Vector;
0034     using Matrix = typename GraphT::Matrix;
0035     using RawVector = typename GraphT::RawVector;
0036
0037     assert(G.getNodeDegree(NId) == 1 &&
0038            "R1 applied to node with degree != 1.");
0039
0040     EdgeId EId = *G.adjEdgeIds(NId).begin();
0041     NodeId MId = G.getEdgeOtherNodeId(EId, NId);
0042
0043     const Matrix &ECosts = G.getEdgeCosts(EId);
0044     const Vector &XCosts = G.getNodeCosts(NId);
0045     RawVector YCosts = G.getNodeCosts(MId);
0046
0047     // Duplicate a little to avoid transposing matrices.
0048     if (NId == G.getEdgeNode1Id(EId)) {
0049       for (unsigned j = 0; j < YCosts.getLength(); ++j) {
0050         PBQPNum Min = ECosts[0][j] + XCosts[0];
0051         for (unsigned i = 1; i < XCosts.getLength(); ++i) {
0052           PBQPNum C = ECosts[i][j] + XCosts[i];
0053           if (C < Min)
0054             Min = C;
0055         }
0056         YCosts[j] += Min;
0057       }
0058     } else {
0059       for (unsigned i = 0; i < YCosts.getLength(); ++i) {
0060         PBQPNum Min = ECosts[i][0] + XCosts[0];
0061         for (unsigned j = 1; j < XCosts.getLength(); ++j) {
0062           PBQPNum C = ECosts[i][j] + XCosts[j];
0063           if (C < Min)
0064             Min = C;
0065         }
0066         YCosts[i] += Min;
0067       }
0068     }
0069     G.setNodeCosts(MId, YCosts);
0070     G.disconnectEdge(EId, MId);
0071   }
0072
0073   template <typename GraphT>
0074   void applyR2(GraphT &G, typename GraphT::NodeId NId) {
0075     using NodeId = typename GraphT::NodeId;
0076     using EdgeId = typename GraphT::EdgeId;
0077     using Vector = typename GraphT::Vector;
0078     using Matrix = typename GraphT::Matrix;
0079     using RawMatrix = typename GraphT::RawMatrix;
0080
0081     assert(G.getNodeDegree(NId) == 2 &&
0082            "R2 applied to node with degree != 2.");
0083
0084     const Vector &XCosts = G.getNodeCosts(NId);
0085
0086     typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin();
0087     EdgeId YXEId = *AEItr,
0088            ZXEId = *(++AEItr);
0089
0090     NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId),
0091            ZNId = G.getEdgeOtherNodeId(ZXEId, NId);
0092
0093     bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId),
0094          FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId);
0095
0096     const Matrix *YXECosts = FlipEdge1 ?
0097       new Matrix(G.getEdgeCosts(YXEId).transpose()) :
0098       &G.getEdgeCosts(YXEId);
0099
0100     const Matrix *ZXECosts = FlipEdge2 ?
0101       new Matrix(G.getEdgeCosts(ZXEId).transpose()) :
0102       &G.getEdgeCosts(ZXEId);
0103
0104     unsigned XLen = XCosts.getLength(),
0105       YLen = YXECosts->getRows(),
0106       ZLen = ZXECosts->getRows();
0107
0108     RawMatrix Delta(YLen, ZLen);
0109
0110     for (unsigned i = 0; i < YLen; ++i) {
0111       for (unsigned j = 0; j < ZLen; ++j) {
0112         PBQPNum Min = (*YXECosts)[i][0] + (*ZXECosts)[j][0] + XCosts[0];
0113         for (unsigned k = 1; k < XLen; ++k) {
0114           PBQPNum C = (*YXECosts)[i][k] + (*ZXECosts)[j][k] + XCosts[k];
0115           if (C < Min) {
0116             Min = C;
0117           }
0118         }
0119         Delta[i][j] = Min;
0120       }
0121     }
0122
0123     if (FlipEdge1)
0124       delete YXECosts;
0125
0126     if (FlipEdge2)
0127       delete ZXECosts;
0128
0129     EdgeId YZEId = G.findEdge(YNId, ZNId);
0130
0131     if (YZEId == G.invalidEdgeId()) {
0132       YZEId = G.addEdge(YNId, ZNId, Delta);
0133     } else {
0134       const Matrix &YZECosts = G.getEdgeCosts(YZEId);
0135       if (YNId == G.getEdgeNode1Id(YZEId)) {
0136         G.updateEdgeCosts(YZEId, Delta + YZECosts);
0137       } else {
0138         G.updateEdgeCosts(YZEId, Delta.transpose() + YZECosts);
0139       }
0140     }
0141
0142     G.disconnectEdge(YXEId, YNId);
0143     G.disconnectEdge(ZXEId, ZNId);
0144
0145     // TODO: Try to normalize newly added/modified edge.
0146   }
0147
0148 #ifndef NDEBUG
0149   // Does this Cost vector have any register options ?
0150   template <typename VectorT>
0151   bool hasRegisterOptions(const VectorT &V) {
0152     unsigned VL = V.getLength();
0153
0154     // An empty or spill only cost vector does not provide any register option.
0155     if (VL <= 1)
0156       return false;
0157
0158     // If there are registers in the cost vector, but all of them have infinite
0159     // costs, then ... there is no available register.
0160     for (unsigned i = 1; i < VL; ++i)
0161       if (V[i] != std::numeric_limits<PBQP::PBQPNum>::infinity())
0162         return true;
0163
0164     return false;
0165   }
0166 #endif
0167
0168   // Find a solution to a fully reduced graph by backpropagation.
0169   //
0170   // Given a graph and a reduction order, pop each node from the reduction
0171   // order and greedily compute a minimum solution based on the node costs, and
0172   // the dependent costs due to previously solved nodes.
0173   //
0174   // Note - This does not return the graph to its original (pre-reduction)
0175   //        state: the existing solvers destructively alter the node and edge
0176   //        costs. Given that, the backpropagate function doesn't attempt to
0177   //        replace the edges either, but leaves the graph in its reduced
0178   //        state.
0179   template <typename GraphT, typename StackT>
0180   Solution backpropagate(GraphT& G, StackT stack) {
0181     using NodeId = GraphBase::NodeId;
0182     using Matrix = typename GraphT::Matrix;
0183     using RawVector = typename GraphT::RawVector;
0184
0185     Solution s;
0186
0187     while (!stack.empty()) {
0188       NodeId NId = stack.back();
0189       stack.pop_back();
0190
0191       RawVector v = G.getNodeCosts(NId);
0192
0193 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
0194       // Although a conservatively allocatable node can be allocated to a register,
0195       // spilling it may provide a lower cost solution. Assert here that spilling
0196       // is done by choice, not because there were no register available.
0197       if (G.getNodeMetadata(NId).wasConservativelyAllocatable())
0198         assert(hasRegisterOptions(v) && "A conservatively allocatable node "
0199                                         "must have available register options");
0200 #endif
0201
0202       for (auto EId : G.adjEdgeIds(NId)) {
0203         const Matrix& edgeCosts = G.getEdgeCosts(EId);
0204         if (NId == G.getEdgeNode1Id(EId)) {
0205           NodeId mId = G.getEdgeNode2Id(EId);
0206           v += edgeCosts.getColAsVector(s.getSelection(mId));
0207         } else {
0208           NodeId mId = G.getEdgeNode1Id(EId);
0209           v += edgeCosts.getRowAsVector(s.getSelection(mId));
0210         }
0211       }
0212
0213       s.setSelection(NId, v.minIndex());
0214     }
0215
0216     return s;
0217   }
0218
0219 } // end namespace PBQP
0220 } // end namespace llvm
0221
0222 #endif // LLVM_CODEGEN_PBQP_REDUCTIONRULES_H