 Timestamp:
 Sep 11, 2015, 4:57:13 PM (4 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo/optimizers
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4767 r4768 36 36 using DistributionSets = std::vector<DistributionSet>; 37 37 38 /**  * 39 * @brief helper functions 40 **  */ 38 41 template <class Graph> 39 42 static VertexSet incomingVertexSet(const Vertex u, const Graph & G) { … … 70 73 } 71 74 75 template<typename Iterator> 76 inline Graph::edge_descriptor first(const std::pair<Iterator, Iterator> & range) { 77 assert (range.first != range.second); 78 return *range.first; 79 } 80 81 inline void add_edge(PabloAST * expr, const Vertex u, const Vertex v, Graph & G) { 82 G[add_edge(u, v, G).first] = expr; 83 } 84 85 static unsigned distributionCount = 0; 72 86 /**  * 73 87 * @brief optimize … … 167 181 168 182 /**  * 183 * @brief printGraph 184 **  */ 185 static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) { 186 raw_os_ostream out(std::cerr); 187 188 std::vector<unsigned> component(num_vertices(G)); 189 strong_components(G, make_iterator_property_map(component.begin(), get(vertex_index, G))); 190 191 std::vector<Vertex> ordering; 192 ordering.reserve(num_vertices(G)); 193 topological_sort(G, std::back_inserter(ordering)); 194 std::reverse(ordering.begin(), ordering.end()); 195 196 out << "digraph " << name << " {\n"; 197 for (auto u : ordering) { 198 if (in_degree(u, G) == 0 && out_degree(u, G) == 0) { 199 continue; 200 } 201 out << "v" << u << " [label=\""; 202 PabloAST * expr = G[u]; 203 if (isa<Statement>(expr)) { 204 if (LLVM_UNLIKELY(isa<If>(expr))) { 205 out << "If "; 206 PabloPrinter::print(cast<If>(expr)>getOperand(0), out); 207 out << ":"; 208 } else if (LLVM_UNLIKELY(isa<While>(expr))) { 209 out << "While "; 210 PabloPrinter::print(cast<While>(expr)>getOperand(0), out); 211 out << ":"; 212 } else { 213 PabloPrinter::print(cast<Statement>(expr), "", out); 214 } 215 } else { 216 PabloPrinter::print(expr, out); 217 } 218 out << "\""; 219 if (!inCurrentBlock(expr, block)) { 220 out << " style=dashed"; 221 } 222 out << "];\n"; 223 } 224 225 for (auto e : make_iterator_range(edges(G))) { 226 const auto i = source(e, G), j = target(e, G); 227 out << "v" << i << " > v" << j; 228 if (LLVM_UNLIKELY(component[i] == component[j])) { 229 out << "[color=red]"; 230 } 231 out << ";\n"; 232 } 233 234 if (num_vertices(G) > 0) { 235 236 out << "{ rank=same;"; 237 for (auto u : ordering) { 238 if (in_degree(u, G) == 0 && out_degree(u, G) != 0) { 239 out << " v" << u; 240 } 241 } 242 out << "}\n"; 243 244 out << "{ rank=same;"; 245 for (auto u : ordering) { 246 if (out_degree(u, G) == 0 && in_degree(u, G) != 0) { 247 out << " v" << u; 248 } 249 } 250 out << "}\n"; 251 252 } 253 254 out << "}\n\n"; 255 out.flush(); 256 } 257 258 /**  * 259 * @brief printGraph 260 **  */ 261 template<typename SubgraphType> 262 static void printGraph(const PabloBlock & block, const SubgraphType & S, const Graph & G, const std::string name) { 263 raw_os_ostream out(std::cerr); 264 out << "digraph " << name << " {\n"; 265 for (auto u : make_iterator_range(vertices(S))) { 266 if (in_degree(u, S) == 0 && out_degree(u, S) == 0) { 267 continue; 268 } 269 out << "v" << u << " [label=\""; 270 PabloAST * expr = G[S[u]]; 271 if (isa<Statement>(expr)) { 272 if (LLVM_UNLIKELY(isa<If>(expr))) { 273 out << "If "; 274 PabloPrinter::print(cast<If>(expr)>getOperand(0), out); 275 out << ":"; 276 } else if (LLVM_UNLIKELY(isa<While>(expr))) { 277 out << "While "; 278 PabloPrinter::print(cast<While>(expr)>getOperand(0), out); 279 out << ":"; 280 } else { 281 PabloPrinter::print(cast<Statement>(expr), "", out); 282 } 283 } else { 284 PabloPrinter::print(expr, out); 285 } 286 out << "\""; 287 if (!inCurrentBlock(expr, block)) { 288 out << " style=dashed"; 289 } 290 out << "];\n"; 291 } 292 for (auto e : make_iterator_range(edges(S))) { 293 out << "v" << source(e, S) << " > v" << target(e, S) << ";\n"; 294 } 295 296 if (num_vertices(S) > 0) { 297 298 out << "{ rank=same;"; 299 for (auto u : make_iterator_range(vertices(S))) { 300 if (in_degree(u, S) == 0 && out_degree(u, S) != 0) { 301 out << " v" << u; 302 } 303 } 304 out << "}\n"; 305 306 out << "{ rank=same;"; 307 for (auto u : make_iterator_range(vertices(S))) { 308 if (out_degree(u, S) == 0 && in_degree(u, S) != 0) { 309 out << " v" << u; 310 } 311 } 312 out << "}\n"; 313 314 } 315 316 out << "}\n\n"; 317 out.flush(); 318 } 319 320 321 /**  * 169 322 * @brief createTree 170 323 **  */ 171 324 static PabloAST * createTree(PabloBlock & block, const PabloAST::ClassTypeId typeId, circular_buffer<PabloAST *> & Q) { 172 assert (Q.size() > 0);325 assert (Q.size() > 1); 173 326 while (Q.size() > 1) { 174 327 PabloAST * e1 = Q.front(); Q.pop_front(); … … 199 352 200 353 summarizeAST(block, G); 354 assert (summarizeGraph(block, G) == false); 201 355 redistributeAST(block, G); 356 assert (summarizeGraph(block, G) == false); 357 358 raw_os_ostream out(std::cerr); 359 out << "======================================================\n"; 360 PabloPrinter::print(block, " > ", out); 361 out << "\n"; 362 out.flush(); 363 364 printGraph(block, G, "G"); 365 366 out << "\n"; 202 367 203 368 circular_buffer<Vertex> Q(num_vertices(G)); 204 topological_sort(G, std::front_inserter(Q)); 205 circular_buffer<PabloAST *> nodes; 369 topological_sort(G, std::back_inserter(Q)); 206 370 block.setInsertPoint(nullptr); 207 371 208 372 while (!Q.empty()) { 209 const Vertex u = Q.front(); 210 Q.pop_front(); 211 PabloAST * expr = G[u]; 212 if (LLVM_LIKELY(inCurrentBlock(expr, block))) { 213 if (isOptimizable(expr)) { 214 if (in_degree(u, G) != 0 && out_degree(u, G) != 0) { 215 if (LLVM_UNLIKELY(nodes.capacity() < in_degree(u, G))) { 216 nodes.set_capacity(in_degree(u, G)); 217 } 373 const Vertex u = Q.back(); Q.pop_back(); 374 if (LLVM_LIKELY(in_degree(u, G) != 0  out_degree(u, G) != 0)) { 375 if (LLVM_LIKELY(inCurrentBlock(G[u], block))) { 376 Statement * stmt = cast<Statement>(G[u]); 377 PabloPrinter::print(stmt, "  ", out); out << '\n'; 378 if (isOptimizable(stmt)) { 379 circular_buffer<PabloAST *> nodes(in_degree(u, G)); 218 380 for (auto e : make_iterator_range(in_edges(u, G))) { 219 381 nodes.push_back(G[source(e, G)]); 220 382 } 221 G[u] = createTree(block, expr>getClassTypeId(), nodes); 222 cast<Statement>(expr)>replaceWith(G[u], true, true); 223 if (LLVM_UNLIKELY(isa<Var>(G[u]))) { 224 continue; 383 Statement * replacement = cast<Statement>(createTree(block, stmt>getClassTypeId(), nodes)); 384 stmt>replaceWith(replacement, false, true); 385 G[u] = stmt = replacement; 386 PabloPrinter::print(replacement, " > replaced with ", out); out << '\n'; 387 } else { 388 for (const auto e : make_iterator_range(in_edges(u, G))) { 389 const auto v = source(e, G); 390 if (LLVM_UNLIKELY(G[v] != G[e])) { 391 392 393 394 } 225 395 } 226 expr = G[u];227 396 } 228 } 229 block.insert(cast<Statement>(expr)); 230 } 231 } 397 block.insert(stmt); 398 } 399 } 400 } 401 402 out << "\n"; 403 PabloPrinter::print(block, " < ", out); 404 out << "\n"; 405 out.flush(); 406 232 407 PabloVerifier::verify(function); 233 234 408 } 235 409 … … 242 416 **  */ 243 417 void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const { 244 245 418 Map M; 246 247 419 // Compute the base defuse graph ... 248 420 for (Statement * stmt : block) { … … 253 425 continue; 254 426 } 255 add_edge( getVertex(op, G, M), u, G);427 add_edge(op, getVertex(op, G, M), u, G); 256 428 } 257 429 if (isa<If>(stmt)) { 258 430 for (Assign * def : cast<const If>(stmt)>getDefined()) { 259 431 const Vertex v = getVertex(def, G, M); 260 add_edge( u, v, G);261 resolveUsages(v, def, block, G, M );432 add_edge(def, u, v, G); 433 resolveUsages(v, def, block, G, M, stmt); 262 434 } 263 435 } else if (isa<While>(stmt)) { 264 436 for (Next * var : cast<const While>(stmt)>getVariants()) { 265 437 const Vertex v = getVertex(var, G, M); 266 add_edge( u, v, G);267 resolveUsages(v, var, block, G, M );438 add_edge(var, u, v, G); 439 resolveUsages(v, var, block, G, M, stmt); 268 440 } 269 441 } else { … … 271 443 } 272 444 } 273 274 std::vector<Vertex> ordering; 275 ordering.reserve(num_vertices(G)); 276 topological_sort(G, std::back_inserter(ordering)); 277 278 for (auto i = ordering.rbegin(); i != ordering.rend(); ++i) { 279 const Vertex u = *i; 280 if (isOptimizable(G[u])) { 281 std::vector<Vertex> removable; 282 for (auto e : make_iterator_range(in_edges(u, G))) { 283 const Vertex v = source(e, G); 284 if (out_degree(v, G) == 1 && in_degree(v, G) != 0 && G[u]>getClassTypeId() == G[v]>getClassTypeId()) { 285 removable.push_back(v); 286 for (auto e : make_iterator_range(in_edges(v, G))) { 287 add_edge(source(e, G), u, G); 445 summarizeGraph(block, G); 446 } 447 448 /**  * 449 * @brief resolveUsages 450 **  */ 451 bool BooleanReassociationPass::summarizeGraph(PabloBlock & block, Graph & G) { 452 bool modified = false; 453 std::vector<Vertex> reverseTopologicalOrdering; 454 reverseTopologicalOrdering.reserve(num_vertices(G)); 455 topological_sort(G, std::back_inserter(reverseTopologicalOrdering)); 456 for (const Vertex u : reverseTopologicalOrdering) { 457 if (isOptimizable(G[u]) && inCurrentBlock(G[u], block)) { 458 if (LLVM_UNLIKELY(in_degree(u, G) == 1)) { 459 // We have a redundant node here that'll simply end up being a duplicate 460 // of the input value. Remove it and add any of its outgoing edges to its 461 // input node. 462 const auto ei = first(in_edges(u, G)); 463 const Vertex v = source(ei, G); 464 for (auto ej : make_iterator_range(out_edges(u, G))) { 465 add_edge(G[ei], v, target(ej, G), G); 466 } 467 clear_vertex(u, G); 468 modified = true; 469 continue; 470 } else if (LLVM_UNLIKELY(out_degree(u, G) == 1)) { 471 // Otherwise if we have a single user, we have a similar case as above but 472 // we can only merge this vertex into the outgoing instruction if they are 473 // of the same type. 474 const auto ei = first(out_edges(u, G)); 475 const Vertex v = target(ei, G); 476 if (LLVM_UNLIKELY(G[v]>getClassTypeId() == G[u]>getClassTypeId())) { 477 for (auto ej : make_iterator_range(in_edges(u, G))) { 478 add_edge(G[ei], source(ej, G), v, G); 288 479 } 480 clear_vertex(u, G); 481 modified = true; 482 continue; 289 483 } 290 484 } 291 for (auto v : removable) { 292 clear_vertex(v, G); 293 } 294 } 295 } 485 } 486 // Finally, eliminate any unnecessary instruction 487 if (LLVM_UNLIKELY(out_degree(u, G) == 0 && !(isa<Assign>(G[u])  isa<Next>(G[u])))) { 488 clear_in_edges(u, G); 489 } 490 } 491 assert (modified ? (summarizeGraph(block, G) == false) : true); 492 return modified; 296 493 } 297 494 … … 299 496 * @brief resolveUsages 300 497 **  */ 301 void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M ) const {498 void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis) const { 302 499 for (PabloAST * user : expr>users()) { 303 500 assert (user); … … 314 511 if (LLVM_UNLIKELY(f == mResolvedScopes.end())) { 315 512 throw std::runtime_error("Failed to resolve scope block!"); 513 } 514 if (LLVM_UNLIKELY(f>second == ignoreIfThis)) { 515 break; 316 516 } 317 517 add_edge(u, getVertex(f>second, G, M), G); … … 584 784 bool anyChanges = false; 585 785 786 ++distributionCount; 787 586 788 for (;;) { 587 789 … … 630 832 const Vertex y = add_vertex(nullptr, G); 631 833 for (const Vertex u : intermediary) { 632 add_edge( H[u], x, G);834 add_edge(nullptr, H[u], x, G); 633 835 } 634 836 for (const Vertex s : sources) { 635 add_edge( H[s], y, G);837 add_edge(nullptr, H[s], y, G); 636 838 } 637 839 for (const Vertex t : sinks) { 638 add_edge(y, H[t], G); 639 } 640 add_edge(x, y, G); 641 840 add_edge(nullptr, y, H[t], G); 841 } 842 add_edge(nullptr, x, y, G); 642 843 643 844 // Now begin transforming the AST (TODO: fix the abstraction so I can defer creation until the final phase) … … 653 854 654 855 // Summarize the graph after transforming G 655 std::vector<Vertex> ordering; 656 ordering.reserve(num_vertices(G)); 657 for (const Vertex u : ordering) { 658 if (LLVM_UNLIKELY(out_degree(u, G) == 1 && inCurrentBlock(G[u], block))) { 659 if (isOptimizable(G[u])) { 660 const Vertex v = target(*(out_edges(u, G).first), G); 661 if (LLVM_UNLIKELY(G[v]>getClassTypeId() == G[u]>getClassTypeId())) { 662 for (auto e : make_iterator_range(in_edges(u, G))) { 663 assert (source(e, G) != u); 664 add_edge(source(e, G), v, G); 665 } 666 clear_vertex(u, G); 667 } 668 } 669 } 670 } 856 summarizeGraph(block, G); 671 857 } 672 858 anyChanges = true; 
icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.h
r4766 r4768 10 10 class BooleanReassociationPass { 11 11 public: 12 using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST * >;12 using Graph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, PabloAST *, PabloAST *>; 13 13 using Vertex = Graph::vertex_descriptor; 14 14 using Map = std::unordered_map<const PabloAST *, Vertex>; … … 23 23 void processScope(PabloFunction & function, PabloBlock & block); 24 24 void summarizeAST(PabloBlock & block, Graph & G) const; 25 void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M) const; 25 static bool summarizeGraph(PabloBlock & block, Graph & G); 26 void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis = nullptr) const; 26 27 bool redistributeAST(PabloBlock & block, Graph & G) const; 27 28 private: 
icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_simplifier.hpp
r4658 r4768 12 12 public: 13 13 static bool optimize(PabloFunction & function); 14 static void deadCodeElimination(PabloBlock & block); 14 15 protected: 15 16 Simplifier(); 16 17 private: 17 18 static void eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor = nullptr); 18 static void deadCodeElimination(PabloBlock & block);19 19 static void eliminateRedundantComplexStatements(PabloBlock & block); 20 20 static bool isSuperfluous(const Assign * const assign);
Note: See TracChangeset
for help on using the changeset viewer.