RootOrdering.cpp Source File (original) (raw)

16 #include "llvm/ADT/DenseMap.h"

17 #include "llvm/ADT/DenseSet.h"

18 #include "llvm/ADT/SmallVector.h"

19 #include

20 #include

22 using namespace mlir;

31 do {

32 cycle.push_back(node);

33 node = parents.lookup(node);

34 assert(node && "got an empty value in the cycle");

35 } while (node != rep);

36 return cycle;

37 }

52 Value rep = cycle.front();

57 for (auto outer = graph.begin(), e = graph.end(); outer != e; ++outer) {

58 Value target = outer->first;

59 if (cycleSet.contains(target)) {

61 unsigned parentDepth = parentDepths.lookup(target);

62 for (const auto &inner : outer->second) {

63 Value source = inner.first;

65 if (cycleSet.contains(source))

66 continue;

69 std::pair<unsigned, unsigned> cost = inner.second.cost;

70 assert(parentDepth <= cost.first && "invalid parent depth");

77 cost.first -= parentDepth;

78 auto it = repEntries.find(source);

79 if (it == repEntries.end() || it->second.cost > cost) {

80 actualTarget[source] = target;

83 repEntries[source].cost = cost;

84 }

85 }

87 graph.erase(outer);

88 } else {

92 std::pair<unsigned, unsigned> bestCost;

93 auto inner = entries.begin(), innerE = entries.end();

94 while (inner != innerE) {

95 Value source = inner->first;

96 if (cycleSet.contains(source)) {

98 if (!bestSource || bestCost > inner->second.cost) {

99 bestSource = source;

100 bestCost = inner->second.cost;

101 }

102 entries.erase(inner++);

103 } else {

104 ++inner;

105 }

106 }

107

108

109 if (bestSource) {

110 entries[rep].cost = bestCost;

111 actualSource[target] = bestSource;

112 }

113 }

114 }

115

116

117 graph[rep] = std::move(repEntries);

118 }

119

121 : graph(std::move(graph)), root(root) {}

122

124

125 parents.clear();

126 parents[root] = Value();

127 unsigned totalCost = 0;

128

129

130

132 parentDepths.reserve(graph.size());

133

134

135

136

137 for (const auto &outer : graph) {

138 Value node = outer.first;

139 if (parents.count(node))

140 continue;

141

142

143

144

145 parentDepths.clear();

146 do {

147 auto it = graph.find(node);

148 assert(it != graph.end() && "the graph is not strongly connected");

149

150

151

152 Value &bestSource = parents[node];

153 std::pair<unsigned, unsigned> bestCost;

154 for (const auto &inner : it->second) {

156 if (!bestSource || bestCost > entry.cost) {

157 bestSource = inner.first;

158 bestCost = entry.cost;

159 }

160 }

161 assert(bestSource && "the graph is not strongly connected");

162 parentDepths[node] = bestCost.first;

163 node = bestSource;

164 totalCost += bestCost.first;

165 } while (!parents.count(node));

166

167

168 if (parentDepths.count(node)) {

169

171

172

173

175

176

177 contract(graph, cycle, parentDepths, actualSource, actualTarget);

178 totalCost = solve();

179

180

181 for (auto &p : parents)

182 if (p.second == node)

183

184

185 p.second = actualSource.lookup(p.first);

186

187

188 Value parent = parents.lookup(node);

189 Value entry = actualTarget.lookup(parent);

190 cycle.push_back(node);

191 for (size_t i = 0, e = cycle.size() - 1; i < e; ++i) {

192 totalCost += parentDepths.lookup(cycle[i]);

193 if (cycle[i] == entry)

194 parents[cycle[i]] = parent;

195 else

196 parents[cycle[i]] = cycle[i + 1];

197 }

198

199

200 break;

201 }

202 }

203

204 return totalCost;

205 }

206

209

211 for (Value node : nodes) {

212 if (node != root) {

213 Value parent = parents.lookup(node);

214 assert(parent && "invalid parent");

215 children[parent].push_back(node);

216 }

217 }

218

219

221 result.reserve(nodes.size());

222 result.emplace_back(root, Value());

223

224

225 for (size_t i = 0; i < result.size(); ++i) {

226 Value node = result[i].first;

227 for (Value child : children[node])

228 result.emplace_back(child, node);

229 }

230

231 return result;

232 }

static void contract(RootOrderingGraph &graph, ArrayRef< Value > cycle, const DenseMap< Value, unsigned > &parentDepths, DenseMap< Value, Value > &actualSource, DenseMap< Value, Value > &actualTarget)

Contracts the specified cycle in the given graph in-place.

static SmallVector< Value > getCycle(const DenseMap< Value, Value > &parents, Value rep)

Returns the cycle implied by the specified parent relation, starting at the given node.

This class represents an instance of an SSA value in the MLIR system, representing a computable value...

unsigned solve()

Runs the Edmonds' algorithm for the current graph, returning the total cost of the minimum-weight spa...

std::vector< std::pair< Value, Value > > EdgeList

A list of edges (child, parent).

OptimalBranching(RootOrderingGraph graph, Value root)

Constructs the solver for the given graph and root value.

EdgeList preOrderTraversal(ArrayRef< Value > nodes) const

Returns the computed edges as visited in the preorder traversal.

Include the generated interface declarations.

The information associated with an edge in the cost graph.

std::pair< unsigned, unsigned > cost

The depth of the connector Value w.r.t.