Changeset 4744
 Timestamp:
 Aug 23, 2015, 2:27:12 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4741 r4744 29 29 terminals.push_back(function.getResult(i)); 30 30 } 31 scan(function.getEntryBlock(), std::move(terminals));31 return scan(function.getEntryBlock(), std::move(terminals)); 32 32 } 33 33 … … 68 68 **  */ 69 69 static inline bool isCutNecessary(const Vertex u, const Vertex v, const Graph & G, const std::vector<unsigned> & component) { 70 // Either this edge crosses a component boundary or the operations performed by the vertices differs, we need to cut 71 // the graph here and generate two partial equations. 70 72 if (LLVM_UNLIKELY(component[u] != component[v])) { 71 73 return true; … … 77 79 78 80 /**  * 79 * @brief isCutNecessary80 **  */81 static bool print(const Graph & G, const std::vector<unsigned> & component, raw_os_ostream & out) {82 bool hasError = false;83 out << "digraph G {\n";84 unsigned i = 0;85 for (auto u : make_iterator_range(vertices(G))) {86 out << "u" << u << " [label=\"";87 out << i++ << " : ";88 PabloPrinter::print(G[u], out);89 out << " (" << component[u] << ')';90 out << "\"";91 if (isaBooleanOperation(G[u]) && (in_degree(u, G) == 1  in_degree(u, G) > 2)) {92 out << " color=red";93 hasError = true;94 }95 out << "];\n";96 }97 for (auto e : make_iterator_range(edges(G))) {98 Vertex u = source(e, G);99 Vertex v = target(e, G);100 out << "u" << u << " > u" << v;101 if (isCutNecessary(u, v, G, component)) {102 out << " [color=red]";103 hasError = true;104 }105 out << ";\n";106 }107 out << "}\n";108 out.flush();109 return hasError;110 }111 112 /**  *113 81 * @brief scan 114 82 **  */ … … 118 86 using VertexQueue = std::queue<Vertex>; 119 87 using EdgeQueue = std::queue<std::pair<Vertex, Vertex>>; 88 89 PabloBuilder builder(block); 120 90 121 91 for (Statement * stmt : block) { … … 128 98 Terminals terminals(vars.begin(), vars.end()); 129 99 scan(cast<While>(stmt)>getBody(), std::move(terminals)); 100 } else { 101 builder.record(stmt); 130 102 } 131 103 } … … 134 106 // safely rearrange expressions such as "((((a âš b) âš c) âš d) âš e) âš f" into "((a âš b) âš (c âš d)) âš (e âš f)". 135 107 136 raw_os_ostream out(std::cerr); 137 138 out << "=================================================\n"; 139 140 PabloBuilder builder(block); 108 bool modifiedAST = false; 141 109 142 110 for (;;) { … … 167 135 } 168 136 } 169 170 137 } 171 138 … … 194 161 195 162 // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of 196 // another terminal, we need to make sure we compute it .163 // another terminal, we need to make sure we compute it as an independent subexpression. 197 164 std::vector<unsigned> ordering; 198 165 ordering.reserve(num_vertices(G)); … … 203 170 204 171 // Mark which computation component these vertices are in based on their topological (occurence) order. 205 unsigned co unt= 0;172 unsigned components = 0; 206 173 for (auto u : ordering) { 207 174 unsigned id = 0; 208 // If this one of our original terminals ora sink in G, it is the root of a new component.175 // If this is a sink in G, it is the root of a new component. 209 176 if (out_degree(u, G) == 0) { 210 id = ++co unt;177 id = ++components; 211 178 } else { 212 179 for (auto e : make_iterator_range(out_edges(u, G))) { … … 218 185 } 219 186 220 if (count > 1) { 221 // Cut the graph wherever a computation crosses a component 222 EdgeQueue Q; 223 graph_traits<Graph>::edge_iterator ei, ei_end; 224 225 for (std::tie(ei, ei_end) = edges(G); ei != ei_end; ) { 226 const Graph::edge_descriptor e = *ei++; 227 const Vertex u = source(e, G); 228 const Vertex v = target(e, G); 229 if (LLVM_UNLIKELY(isCutNecessary(u, v, G, component))) { 230 Q.push(std::make_pair(u, v)); 231 remove_edge(u, v, G); 232 } 233 } 234 235 // If no edges cross a component, we're done. 187 // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because 188 // the instructions corresponding to the pair of nodes differs. 189 EdgeQueue Q; 190 graph_traits<Graph>::edge_iterator ei, ei_end; 191 192 for (std::tie(ei, ei_end) = edges(G); ei != ei_end; ) { 193 const Graph::edge_descriptor e = *ei++; 194 const Vertex u = source(e, G); 195 const Vertex v = target(e, G); 196 if (LLVM_UNLIKELY(isCutNecessary(u, v, G, component))) { 197 Q.push(std::make_pair(u, v)); 198 remove_edge(u, v, G); 199 } 200 } 201 202 // If no cuts are necessary, we're done. 203 if (Q.empty()) { 204 break; 205 } 206 207 for (;;) { 208 209 Vertex u, v; 210 std::tie(u, v) = Q.front(); Q.pop(); 211 212 // The vertex belonging to a component with a greater number must come "earlier" 213 // in the program. By replicating it, this ensures it's computed as an output of 214 // one component and used as an input of another. 215 216 if (component[u] < component[v]) { 217 std::swap(u, v); 218 } 219 220 // Replicate u and fix the ordering and component vectors to reflect the change in G. 221 Vertex w = add_vertex(G[u], G); 222 ordering.insert(std::find(ordering.begin(), ordering.end(), u), w); 223 assert (component.size() == w); 224 component.push_back(component[v]); 225 add_edge(w, v, G); 226 227 // However, after we do so, we need to make sure the original source vertex will be a 228 // sink in G unless it is also an input variable (in which case we'd simply end up with 229 // extraneous isolated vertex. Otherwise, we need to make further cuts and replications. 230 231 if (in_degree(u, G) != 0) { 232 for (auto e : make_iterator_range(out_edges(u, G))) { 233 Q.push(std::make_pair(source(e, G), target(e, G))); 234 } 235 clear_out_edges(u, G); 236 } 237 236 238 if (Q.empty()) { 237 break; // outer for loop 238 } 239 240 for (;;) { 241 242 Vertex u, v; 243 std::tie(u, v) = Q.front(); Q.pop(); 244 245 // The vertex belonging to a component with a greater number must come "earlier" 246 // in the program. By replicating it, this ensures it's computed as an output of 247 // one component and used as an input of another. 248 249 if (component[u] < component[v]) { 250 std::swap(u, v); 251 } 252 253 // Replicate u and fix the ordering and component vectors to reflect the change in G. 254 Vertex w = add_vertex(G[u], G); 255 ordering.insert(std::find(ordering.begin(), ordering.end(), u), w); 256 assert (component.size() == w); 257 component.push_back(component[v]); 258 add_edge(w, v, G); 259 260 // However, after we do so, we need to make sure the original source vertex will be a 261 // sink in G unless it is also an input variable (in which case we'd simply end up with 262 // extraneous isolated vertex. Otherwise, we need to make further cuts and replications. 263 264 if (in_degree(u, G) != 0) { 265 for (auto e : make_iterator_range(out_edges(u, G))) { 266 Q.push(std::make_pair(source(e, G), target(e, G))); 267 } 268 clear_out_edges(u, G); 269 } 270 271 if (Q.empty()) { 272 break; 273 } 274 275 } 276 continue; // outer for loop 277 } 278 break; // outer for loop 279 } 280 281 if (print(G, component, out)) { 282 PabloPrinter::print(block.statements(), out); 283 out.flush(); 284 throw std::runtime_error("Illegal graph generated!"); 239 break; 240 } 241 242 } 285 243 } 286 244 287 245 // Scan through the graph in reverse order so that we find all subexpressions first 288 for (auto ui = ordering.begin(); ui != ordering.end(); ++ui) { 289 const Vertex u = *ui; 246 for (const Vertex u : ordering) { 290 247 if (out_degree(u, G) == 0 && in_degree(u, G) != 0) { 291 292 out << "  checking component " << component[u] << " : ";293 PabloPrinter::print(G[u], out);294 out << "\n";295 out.flush();296 248 297 249 // While we're collecting our variable set V, keep track of the maximum path length L. … … 305 257 unsigned maxPathLength = 0; 306 258 L.emplace(v, 0); 307 for (;;) { 308 assert (isa<Statement>(G[v]) ? cast<Statement>(G[v])>getParent() != nullptr : true); 259 for (;;) { 309 260 if (in_degree(v, G) == 0) { 310 261 V.insert(G[v]); … … 332 283 // Should we optimize this portion of the AST? 333 284 if (maxPathLength > ceil_log2(V.size())) { 334 335 out << "  rewriting component " << component[u] << " : P=" << maxPathLength << ", V=" << V.size() << " (" << ceil_log2(V.size()) << ")\n"; 336 out.flush(); 337 285 Statement * stmt = cast<Statement>(G[u]); 338 286 circular_buffer<PabloAST *> Q(V.size()); 339 287 for (PabloAST * var : V) { 340 288 Q.push_back(var); 341 289 } 342 Statement * stmt = cast<Statement>(G[u]);343 290 344 291 block.setInsertPoint(stmt>getPrevNode()); … … 355 302 Q.push_back(builder.createOr(e1, e2)); 356 303 } 357 } else { // if (isa<Xor>(stmt)) {304 } else { assert(isa<Xor>(stmt)); 358 305 while (Q.size() > 1) { 359 306 PabloAST * e1 = Q.front(); Q.pop_front(); … … 362 309 } 363 310 } 364 stmt>replaceWith(Q.front(), true, true); 365 } 366 367 for (auto uj = ui; ++uj != ordering.end(); ) { 368 assert (isa<Statement>(G[*uj]) ? cast<Statement>(G[*uj])>getParent() != nullptr : true); 369 } 370 311 stmt>replaceAllUsesWith(Q.front()); 312 modifiedAST = true; 313 } 371 314 } 372 315 } … … 393 336 394 337 terminals.assign(nextSet.begin(), nextSet.end()); 395 396 out << "\n"; 338 } 339 340 // If we modified the AST, we likely left dead code in it. Go through and remove any from this block. 341 if (modifiedAST) { 342 Statement * stmt = block.front(); 343 while (stmt) { 344 if (stmt>getNumUses() == 0 && !(isa<If>(stmt)  isa<While>(stmt))){ 345 stmt = stmt>eraseFromParent(true); 346 } else { 347 stmt = stmt>getNextNode(); 348 } 349 } 397 350 } 398 351 }
Note: See TracChangeset
for help on using the changeset viewer.