Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/PBQP/ReductionRules.h
Line
Count
Source (jump to first uncovered line)
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
20
  void applyR1(GraphT &G, typename GraphT::NodeId NId) {
31
20
    using NodeId = typename GraphT::NodeId;
32
20
    using EdgeId = typename GraphT::EdgeId;
33
20
    using Vector = typename GraphT::Vector;
34
20
    using Matrix = typename GraphT::Matrix;
35
20
    using RawVector = typename GraphT::RawVector;
36
20
37
20
    assert(G.getNodeDegree(NId) == 1 &&
38
20
           "R1 applied to node with degree != 1.");
39
20
40
20
    EdgeId EId = *G.adjEdgeIds(NId).begin();
41
20
    NodeId MId = G.getEdgeOtherNodeId(EId, NId);
42
20
43
20
    const Matrix &ECosts = G.getEdgeCosts(EId);
44
20
    const Vector &XCosts = G.getNodeCosts(NId);
45
20
    RawVector YCosts = G.getNodeCosts(MId);
46
20
47
20
    // Duplicate a little to avoid transposing matrices.
48
20
    if (NId == G.getEdgeNode1Id(EId)) {
49
293
      for (unsigned j = 0; j < YCosts.getLength(); 
++j284
) {
50
284
        PBQPNum Min = ECosts[0][j] + XCosts[0];
51
9.05k
        for (unsigned i = 1; i < XCosts.getLength(); 
++i8.76k
) {
52
8.76k
          PBQPNum C = ECosts[i][j] + XCosts[i];
53
8.76k
          if (C < Min)
54
372
            Min = C;
55
8.76k
        }
56
284
        YCosts[j] += Min;
57
284
      }
58
11
    } else {
59
316
      for (unsigned i = 0; i < YCosts.getLength(); 
++i305
) {
60
305
        PBQPNum Min = ECosts[i][0] + XCosts[0];
61
9.52k
        for (unsigned j = 1; j < XCosts.getLength(); 
++j9.22k
) {
62
9.22k
          PBQPNum C = ECosts[i][j] + XCosts[j];
63
9.22k
          if (C < Min)
64
305
            Min = C;
65
9.22k
        }
66
305
        YCosts[i] += Min;
67
305
      }
68
11
    }
69
20
    G.setNodeCosts(MId, YCosts);
70
20
    G.disconnectEdge(EId, MId);
71
20
  }
72
73
  template <typename GraphT>
74
33
  void applyR2(GraphT &G, typename GraphT::NodeId NId) {
75
33
    using NodeId = typename GraphT::NodeId;
76
33
    using EdgeId = typename GraphT::EdgeId;
77
33
    using Vector = typename GraphT::Vector;
78
33
    using Matrix = typename GraphT::Matrix;
79
33
    using RawMatrix = typename GraphT::RawMatrix;
80
33
81
33
    assert(G.getNodeDegree(NId) == 2 &&
82
33
           "R2 applied to node with degree != 2.");
83
33
84
33
    const Vector &XCosts = G.getNodeCosts(NId);
85
33
86
33
    typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin();
87
33
    EdgeId YXEId = *AEItr,
88
33
           ZXEId = *(++AEItr);
89
33
90
33
    NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId),
91
33
           ZNId = G.getEdgeOtherNodeId(ZXEId, NId);
92
33
93
33
    bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId),
94
33
         FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId);
95
33
96
33
    const Matrix *YXECosts = FlipEdge1 ?
97
4
      new Matrix(G.getEdgeCosts(YXEId).transpose()) :
98
33
      
&G.getEdgeCosts(YXEId)29
;
99
33
100
33
    const Matrix *ZXECosts = FlipEdge2 ?
101
19
      new Matrix(G.getEdgeCosts(ZXEId).transpose()) :
102
33
      
&G.getEdgeCosts(ZXEId)14
;
103
33
104
33
    unsigned XLen = XCosts.getLength(),
105
33
      YLen = YXECosts->getRows(),
106
33
      ZLen = ZXECosts->getRows();
107
33
108
33
    RawMatrix Delta(YLen, ZLen);
109
33
110
1.05k
    for (unsigned i = 0; i < YLen; 
++i1.02k
) {
111
34.0k
      for (unsigned j = 0; j < ZLen; 
++j33.0k
) {
112
33.0k
        PBQPNum Min = (*YXECosts)[i][0] + (*ZXECosts)[j][0] + XCosts[0];
113
1.07M
        for (unsigned k = 1; k < XLen; 
++k1.04M
) {
114
1.04M
          PBQPNum C = (*YXECosts)[i][k] + (*ZXECosts)[j][k] + XCosts[k];
115
1.04M
          if (C < Min) {
116
36.5k
            Min = C;
117
36.5k
          }
118
1.04M
        }
119
33.0k
        Delta[i][j] = Min;
120
33.0k
      }
121
1.02k
    }
122
33
123
33
    if (FlipEdge1)
124
4
      delete YXECosts;
125
33
126
33
    if (FlipEdge2)
127
19
      delete ZXECosts;
128
33
129
33
    EdgeId YZEId = G.findEdge(YNId, ZNId);
130
33
131
33
    if (YZEId == G.invalidEdgeId()) {
132
0
      YZEId = G.addEdge(YNId, ZNId, Delta);
133
33
    } else {
134
33
      const Matrix &YZECosts = G.getEdgeCosts(YZEId);
135
33
      if (YNId == G.getEdgeNode1Id(YZEId)) {
136
30
        G.updateEdgeCosts(YZEId, Delta + YZECosts);
137
30
      } else {
138
3
        G.updateEdgeCosts(YZEId, Delta.transpose() + YZECosts);
139
3
      }
140
33
    }
141
33
142
33
    G.disconnectEdge(YXEId, YNId);
143
33
    G.disconnectEdge(ZXEId, ZNId);
144
33
145
33
    // TODO: Try to normalize newly added/modified edge.
146
33
  }
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
8
  Solution backpropagate(GraphT& G, StackT stack) {
181
8
    using NodeId = GraphBase::NodeId;
182
8
    using Matrix = typename GraphT::Matrix;
183
8
    using RawVector = typename GraphT::RawVector;
184
8
185
8
    Solution s;
186
8
187
161
    while (!stack.empty()) {
188
153
      NodeId NId = stack.back();
189
153
      stack.pop_back();
190
153
191
153
      RawVector v = G.getNodeCosts(NId);
192
153
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
559
      for (auto EId : G.adjEdgeIds(NId)) {
203
559
        const Matrix& edgeCosts = G.getEdgeCosts(EId);
204
559
        if (NId == G.getEdgeNode1Id(EId)) {
205
168
          NodeId mId = G.getEdgeNode2Id(EId);
206
168
          v += edgeCosts.getColAsVector(s.getSelection(mId));
207
391
        } else {
208
391
          NodeId mId = G.getEdgeNode1Id(EId);
209
391
          v += edgeCosts.getRowAsVector(s.getSelection(mId));
210
391
        }
211
559
      }
212
153
213
153
      s.setSelection(NId, v.minIndex());
214
153
    }
215
8
216
8
    return s;
217
8
  }
218
219
} // end namespace PBQP
220
} // end namespace llvm
221
222
#endif // LLVM_CODEGEN_PBQP_REDUCTIONRULES_H