Coverage Report

Created: 2017-10-03 07:32

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