ReductionRules.h Source File (original) (raw)

13#ifndef LLVM_CODEGEN_PBQP_REDUCTIONRULES_H

14#define LLVM_CODEGEN_PBQP_REDUCTIONRULES_H

19#include

20#include

22namespace llvm {

23namespace PBQP {

29 template

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;

37 assert(G.getNodeDegree(NId) == 1 &&

38 "R1 applied to node with degree != 1.");

40 EdgeId EId = *G.adjEdgeIds(NId).begin();

41 NodeId MId = G.getEdgeOtherNodeId(EId, NId);

43 const Matrix &ECosts = G.getEdgeCosts(EId);

44 const Vector &XCosts = G.getNodeCosts(NId);

45 RawVector YCosts = G.getNodeCosts(MId);

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 }

73 template

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;

81 assert(G.getNodeDegree(NId) == 2 &&

82 "R2 applied to node with degree != 2.");

84 const Vector &XCosts = G.getNodeCosts(NId);

86 typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin();

87 EdgeId YXEId = *AEItr,

88 ZXEId = *(++AEItr);

90 NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId),

91 ZNId = G.getEdgeOtherNodeId(ZXEId, NId);

93 bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId),

94 FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId);

96 const Matrix *YXECosts = FlipEdge1 ?

97 new Matrix(G.getEdgeCosts(YXEId).transpose()) :

98 &G.getEdgeCosts(YXEId);

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

146 }

147

148#ifndef NDEBUG

149

150 template

152 unsigned VL = V.getLength();

153

154

155 if (VL <= 1)

156 return false;

157

158

159

160 for (unsigned i = 1; i < VL; ++i)

161 if (V[i] != std::numeric_limitsPBQP::PBQPNum::infinity())

162 return true;

163

164 return false;

165 }

166#endif

167

168

169

170

171

172

173

174

175

176

177

178

179 template <typename GraphT, typename StackT>

182 using Matrix = typename GraphT::Matrix;

183 using RawVector = typename GraphT::RawVector;

184

186

187 while (!stack.empty()) {

188 NodeId NId = stack.back();

189 stack.pop_back();

190

191 RawVector v = G.getNodeCosts(NId);

192

193#if LLVM_ENABLE_ABI_BREAKING_CHECKS

194

195

196

197 if (G.getNodeMetadata(NId).wasConservativelyAllocatable())

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);

207 } else {

208 NodeId mId = G.getEdgeNode1Id(EId);

210 }

211 }

212

214 }

215

216 return s;

217 }

218

219}

220}

221

222#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

unsigned getRows() const

Return the number of rows in this matrix.

Vector getColAsVector(unsigned C) const

Returns the given column as a vector.

Vector getRowAsVector(unsigned R) const

Returns the given row as a vector.

Represents a solution to a PBQP problem.

void setSelection(GraphBase::NodeId nodeId, unsigned selection)

Set the selection for a given node.

unsigned getSelection(GraphBase::NodeId nodeId) const

Get a node's selection.

unsigned getLength() const

Return the length of the vector.

@ C

The default llvm calling convention, compatible with C.

void applyR2(GraphT &G, typename GraphT::NodeId NId)

Definition ReductionRules.h:74

void applyR1(GraphT &G, typename GraphT::NodeId NId)

Reduce a node of degree one.

Definition ReductionRules.h:30

Solution backpropagate(GraphT &G, StackT stack)

Definition ReductionRules.h:180

bool hasRegisterOptions(const VectorT &V)

Definition ReductionRules.h:151

This is an optimization pass for GlobalISel generic memory operations.