Changeset 4762
 Timestamp:
 Sep 6, 2015, 4:22:31 PM (4 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.cpp
r4761 r4762 33 33 brp.resolveScopes(function); 34 34 brp.processScopes(function); 35 36 raw_os_ostream out(std::cerr); 37 PabloPrinter::print(function.getEntryBlock().statements(), out); 38 35 39 Simplifier::optimize(function); 36 40 return true; … … 130 134 } 131 135 132 / **  *133 * @brief isCutNecessary134 **  */135 static inline bool isCutNecessary(const Vertex u, const Vertex v, const Graph & G, const std::vector<unsigned> & component) {136 // Either this edge crosses a component boundary or the operations performed by the vertices differs, we need to cut137 // the graph here and generate two partial equations.138 if (LLVM_UNLIKELY(component[u] != component[v])) {139 return true;140 } else if (LLVM_UNLIKELY((in_degree(u, G) != 0) && (G[u]>getClassTypeId() != G[v]>getClassTypeId()))) {141 return true;142 }143 return false;144 }145 146 / **  *147 * @brief push148 **  */149 static inline void push(const Vertex u, VertexQueue & Q) {150 if (LLVM_UNLIKELY(Q.full())) {151 Q.set_capacity(Q.capacity() * 2);152 }153 Q.push_back(u);154 assert (Q.back() == u);155 }156 157 / **  *158 * @brief pop159 **  */160 static inline Vertex pop(VertexQueue & Q) {161 assert (!Q.empty() && "Popping an empty vertex queue");162 const Vertex u = Q.front();163 Q.pop_front();164 return u;165 }136 ///**  * 137 // * @brief isCutNecessary 138 // **  */ 139 //static inline bool isCutNecessary(const Vertex u, const Vertex v, const Graph & G, const std::vector<unsigned> & component) { 140 // // Either this edge crosses a component boundary or the operations performed by the vertices differs, we need to cut 141 // // the graph here and generate two partial equations. 142 // if (LLVM_UNLIKELY(component[u] != component[v])) { 143 // return true; 144 // } else if (LLVM_UNLIKELY((in_degree(u, G) != 0) && (G[u]>getClassTypeId() != G[v]>getClassTypeId()))) { 145 // return true; 146 // } 147 // return false; 148 //} 149 150 ///**  * 151 // * @brief push 152 // **  */ 153 //static inline void push(const Vertex u, VertexQueue & Q) { 154 // if (LLVM_UNLIKELY(Q.full())) { 155 // Q.set_capacity(Q.capacity() * 2); 156 // } 157 // Q.push_back(u); 158 // assert (Q.back() == u); 159 //} 160 161 ///**  * 162 // * @brief pop 163 // **  */ 164 //static inline Vertex pop(VertexQueue & Q) { 165 // assert (!Q.empty() && "Popping an empty vertex queue"); 166 // const Vertex u = Q.front(); 167 // Q.pop_front(); 168 // return u; 169 //} 166 170 167 171 /**  * … … 170 174 template<typename ValueType, typename GraphType, typename MapType> 171 175 static inline Vertex getVertex(ValueType value, GraphType & G, MapType & M) { 176 assert (value); 172 177 const auto f = M.find(value); 173 178 if (f != M.end()) { … … 212 217 out << "digraph " << name << " {\n"; 213 218 for (auto u : make_iterator_range(vertices(G))) { 219 if (in_degree(u, G) == 0 && out_degree(u, G) == 0) { 220 continue; 221 } 214 222 out << "v" << u << " [label=\""; 215 223 PabloAST * expr = G[u]; … … 330 338 inline void BooleanReassociationPass::processScope(PabloBlock & block, std::vector<Statement *> && terminals) { 331 339 Graph G; 332 summarizeAST(block, terminals, G); 333 334 printGraph(block, G, "G0"); 335 340 summarizeAST(block, G); 336 341 redistributeAST(block, G); 337 338 printGraph(block, G, "G1"); 342 printGraph(block, G, "G"); 343 344 345 346 339 347 340 348 circular_buffer<Vertex> Q(num_vertices(G)); … … 347 355 const Vertex u = Q.front(); 348 356 Q.pop_front(); 349 PabloAST * expr = G[u]; 350 if (LLVM_LIKELY(inCurrentBlock(expr, block))) { 351 switch (expr>getClassTypeId()) { 352 case TypeId::And: 353 case TypeId::Or: 354 case TypeId::Xor: 355 if (LLVM_UNLIKELY(in_degree(u, G) < 2)) { 356 std::string tmp; 357 raw_string_ostream str(tmp); 358 PabloPrinter::print(cast<Statement>(expr), "Unexpected error: ", str); 359 str << " only had " << in_degree(u, G) << " nodes!"; 360 throw std::runtime_error(str.str()); 361 } 362 nodes.set_capacity(in_degree(u, G)); 363 for (auto e : make_iterator_range(in_edges(u, G))) { 364 nodes.push_back(G[source(e, G)]); 365 } 366 expr = createTree(block, expr>getClassTypeId(), nodes); 367 default: 368 block.insert(cast<Statement>(expr)); 357 if (LLVM_LIKELY(in_degree(u, G) != 0  out_degree(u, G) != 0)) { 358 PabloAST * expr = G[u]; 359 if (LLVM_LIKELY(inCurrentBlock(expr, block))) { 360 switch (expr>getClassTypeId()) { 361 case TypeId::And: 362 case TypeId::Or: 363 case TypeId::Xor: { 364 nodes.set_capacity(in_degree(u, G)); 365 for (auto e : make_iterator_range(in_edges(u, G))) { 366 nodes.push_back(G[source(e, G)]); 367 } 368 PabloAST * replacement = createTree(block, expr>getClassTypeId(), nodes); 369 cast<Statement>(expr)>replaceWith(replacement, true, true); 370 expr = replacement; 371 } 372 default: 373 block.insert(cast<Statement>(expr)); 374 } 369 375 } 370 376 } … … 381 387 * reassociate them in the most efficient way possible. 382 388 **  */ 383 void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> terminals, Graph & G) const { 384 385 VertexQueue Q(128); 386 EdgeQueue E; 389 void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const { 390 387 391 Map M; 388 392 389 for (;;) { 390 391 Graph Gk; 392 Map Mk; 393 394 // Generate a graph depicting the relationships between the terminals. If the original terminals 395 // cannot be optimized with this algorithm bypass them in favour of their operands. If those cannot 396 // be optimized, they'll be left as the initial terminals for the next "layer" of the AST. 397 398 for (Statement * term : terminals) { 399 if (LLVM_LIKELY(Mk.count(term) == 0)) { 400 // add or find this terminal in our global graph 401 Vertex x = getVertex(term, G, M); 402 if (inCurrentBlock(term, block)) { 403 if (isOptimizable(term)) { 404 const Vertex u = add_vertex(term, Gk); 405 Mk.insert(std::make_pair(term, u)); 406 push(u, Q); 407 continue; 408 } 409 } else if (isa<Assign>(term)  isa<Next>(term)) { 410 // If this is an Assign (Next) node whose operand does not originate from the current block 411 // then check to see if there is an If (While) node that does. 412 Statement * branch = nullptr; 413 if (isa<Assign>(term)) { 414 for (PabloAST * user : term>users()) { 415 if (isa<If>(user)) { 416 const If * ifNode = cast<If>(user); 417 if (inCurrentBlock(ifNode, block)) { 418 const auto & defs = ifNode>getDefined(); 419 if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), cast<Assign>(term)) != defs.end())) { 420 branch = cast<Statement>(user); 421 break; 422 } 423 } 424 } 393 // Compute the base defuse graph ... 394 for (Statement * stmt : block) { 395 const Vertex u = getVertex(stmt, G, M); 396 for (unsigned i = 0; i != stmt>getNumOperands(); ++i) { 397 PabloAST * const op = stmt>getOperand(i); 398 if (LLVM_UNLIKELY(isa<Integer>(op)  isa<String>(op))) { 399 continue; 400 } 401 add_edge(getVertex(op, G, M), u, G); 402 } 403 if (isa<If>(stmt)) { 404 for (Assign * def : cast<const If>(stmt)>getDefined()) { 405 add_edge(u, getVertex(def, G, M), G); 406 } 407 } else if (isa<While>(stmt)) { 408 for (Next * var : cast<const While>(stmt)>getVariants()) { 409 add_edge(u, getVertex(var, G, M), G); 410 } 411 } else if (isOptimizable(stmt)) { 412 for (PabloAST * user : stmt>users()) { 413 if (LLVM_LIKELY(isa<Statement>(user))) { 414 PabloBlock * parent = cast<Statement>(user)>getParent(); 415 if (LLVM_UNLIKELY(parent != &block)) { 416 while (parent>getParent() != &block) { 417 parent = parent>getParent(); 425 418 } 426 } else { // if (isa<Next>(term)) 427 for (PabloAST * user : term>users()) { 428 if (isa<While>(user)) { 429 const While * whileNode = cast<While>(user); 430 if (inCurrentBlock(whileNode, block)) { 431 const auto & vars = whileNode>getVariants(); 432 if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), cast<Next>(term)) != vars.end())) { 433 branch = cast<Statement>(user); 434 break; 435 } 436 } 437 } 419 if (LLVM_UNLIKELY(parent == nullptr)) { 420 throw std::runtime_error("Could not locate nested scope block!"); 438 421 } 439 } 440 441 // If we didn't find a branch, then the Assign (Next) node must have come from a preceeding 442 // block. Just skip it for now. 443 if (branch == nullptr) { 444 continue; 445 } 446 447 // Otherwise add the branch to G and test its operands rather than the original terminal 448 const Vertex z = getVertex(branch, G, M); 449 add_edge(z, x, G); 450 x = z; 451 term = branch; 452 } 453 454 for (unsigned i = 0; i != term>getNumOperands(); ++i) { 455 PabloAST * const op = term>getOperand(i); 456 if (LLVM_LIKELY(inCurrentBlock(op, block))) { 457 const Vertex y = getVertex(op, G, M); 458 add_edge(y, x, G); 459 if (LLVM_LIKELY(Mk.count(op) == 0)) { 460 const Vertex v = add_vertex(op, Gk); 461 Mk.insert(std::make_pair(op, v)); 462 push(v, Q); 422 const auto f = mResolvedScopes.find(parent); 423 if (LLVM_UNLIKELY(f == mResolvedScopes.end())) { 424 throw std::runtime_error("Failed to resolve scope block!"); 463 425 } 426 add_edge(u, getVertex(f>second, G, M), G); 464 427 } 465 428 } 466 429 } 467 430 } 468 469 if (LLVM_UNLIKELY(Q.empty())) { 470 break; 471 } 472 473 for (;;) { 474 const Vertex u = pop(Q); 475 if (isOptimizable(Gk[u])) { 476 Statement * stmt = cast<Statement>(Gk[u]); 477 // If any user of this statement is not in the current block, determine the outermost If/While node 478 // that contains this statement within and add an edge from this statement to it to denote both the 479 // topological ordering necessary and that this statement must be computed. 480 for (PabloAST * user : stmt>users()) { 481 if (LLVM_LIKELY(isa<Statement>(user))) { 482 PabloBlock * parent = cast<Statement>(user)>getParent(); 483 if (LLVM_UNLIKELY(parent != &block)) { 484 while (parent>getParent() != &block) { 485 parent = parent>getParent(); 486 } 487 if (LLVM_UNLIKELY(parent == nullptr)) { 488 throw std::runtime_error("Could not locate nested scope block!"); 489 } 490 const auto f = mResolvedScopes.find(parent); 491 if (LLVM_UNLIKELY(f == mResolvedScopes.end())) { 492 throw std::runtime_error("Failed to resolve scope block!"); 493 } 494 add_edge(u, getVertex(f>second, Gk, Mk), Gk); 495 } 431 } 432 433 std::vector<Vertex> ordering; 434 ordering.reserve(num_vertices(G)); 435 topological_sort(G, std::back_inserter(ordering)); 436 437 for (auto i = ordering.rbegin(); i != ordering.rend(); ++i) { 438 const Vertex u = *i; 439 if (isOptimizable(G[u])) { 440 std::vector<Vertex> removable; 441 for (auto e : make_iterator_range(in_edges(u, G))) { 442 const Vertex v = source(e, G); 443 if (out_degree(v, G) == 1 && in_degree(v, G) != 0 && G[u]>getClassTypeId() == G[v]>getClassTypeId()) { 444 removable.push_back(v); 445 for (auto e : make_iterator_range(in_edges(v, G))) { 446 add_edge(source(e, G), u, G); 496 447 } 497 448 } 498 // Scan through the usedef chains to locate any chains of rearrangable expressions and their inputs 499 for (unsigned i = 0; i != 2; ++i) { 500 PabloAST * op = stmt>getOperand(i); 501 auto f = Mk.find(op); 502 if (f == Mk.end()) { 503 const Vertex v = add_vertex(op, Gk); 504 f = Mk.insert(std::make_pair(op, v)).first; 505 if (op>getClassTypeId() == stmt>getClassTypeId() && inCurrentBlock(cast<Statement>(op), block)) { 506 push(v, Q); 507 } 508 } 509 add_edge(f>second, u, Gk); 510 } 511 } 512 if (Q.empty()) { 513 break; 514 } 515 } 516 517 // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of 518 // another terminal, we need to make sure we compute it as an independent subexpression. 519 std::vector<unsigned> ordering; 520 ordering.reserve(num_vertices(Gk)); 521 topological_sort(Gk, std::back_inserter(ordering)); 522 std::vector<unsigned> component(num_vertices(Gk)); 523 524 for (;;) { 525 526 // Mark which computation component these vertices are in based on their topological (occurence) order. 527 unsigned components = 0; 528 for (auto u : ordering) { 529 unsigned id = 0; 530 // If this is a sink in G, it is the root of a new component. 531 if (out_degree(u, Gk) == 0) { 532 id = ++components; 533 } else { // otherwise it belongs to the outermost component. 534 for (auto e : make_iterator_range(out_edges(u, Gk))) { 535 id = std::max(id, component[target(e, Gk)]); 536 } 537 } 538 assert (id && "Topological ordering failed!"); 539 component[u] = id; 540 } 541 542 // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because 543 // the instructions corresponding to the pair of nodes differs. 544 graph_traits<Graph>::edge_iterator ei, ei_end; 545 for (std::tie(ei, ei_end) = edges(Gk); ei != ei_end; ) { 546 const Graph::edge_descriptor e = *ei++; 547 const Vertex u = source(e, Gk); 548 const Vertex v = target(e, Gk); 549 if (LLVM_UNLIKELY(isCutNecessary(u, v, Gk, component))) { 550 E.push(std::make_pair(u, v)); 551 remove_edge(u, v, Gk); 552 } 553 } 554 555 // If no cuts are necessary, we're done. 556 if (E.empty()) { 557 break; 558 } 559 560 for (;;) { 561 562 Vertex u, v; 563 std::tie(u, v) = E.front(); E.pop(); 564 565 // The vertex belonging to a component with a greater number must come "earlier" 566 // in the program. By replicating it, this ensures it's computed as an output of 567 // one component and used as an input of another. 568 if (component[u] < component[v]) { 569 std::swap(u, v); 570 } 571 572 // Replicate u and fix the ordering and component vectors to reflect the change in Gk. 573 Vertex w = add_vertex(Gk[u], Gk); 574 ordering.insert(std::find(ordering.begin(), ordering.end(), u), w); 575 assert (component.size() == w); 576 component.push_back(component[v]); 577 add_edge(w, v, Gk); 578 579 // However, after we do so, we need to make sure the original source vertex will be a 580 // sink in Gk unless it is also an input variable (in which case we'd simply end up with 581 // extraneous isolated vertex. Otherwise, we need to make further cuts and replications. 582 if (in_degree(u, Gk) != 0) { 583 for (auto e : make_iterator_range(out_edges(u, Gk))) { 584 E.push(std::make_pair(source(e, Gk), target(e, Gk))); 585 } 586 clear_out_edges(u, Gk); 587 } 588 589 if (E.empty()) { 590 break; 591 } 592 } 593 } 594 595 // Scan through the graph so that we process the outermost expressions first 596 for (const Vertex u : ordering) { 597 if (LLVM_UNLIKELY(out_degree(u, Gk) == 0)) { 598 // Create a vertex marking the output statement we may end up replacing 599 // and collect the set of source variables in the component 600 const Vertex x = getVertex(Gk[u], G, M); 601 if (LLVM_LIKELY(in_degree(u, Gk) > 0)) { 602 flat_set<PabloAST *> vars; 603 flat_set<Vertex> visited; 604 for (Vertex v = u;;) { 605 if (in_degree(v, Gk) == 0) { 606 vars.insert(Gk[v]); 607 } else { 608 for (auto e : make_iterator_range(in_edges(v, Gk))) { 609 const Vertex w = source(e, Gk); 610 if (LLVM_LIKELY(visited.insert(w).second)) { 611 push(w, Q); 612 } 613 } 614 } 615 if (Q.empty()) { 616 break; 617 } 618 v = pop(Q); 619 } 620 for (PabloAST * var : vars) { 621 add_edge(getVertex(var, G, M), x, G); 622 } 623 } 624 } 625 } 626 627 // Determine the source variables of the next "layer" of the AST 628 flat_set<Statement *> nextSet; 629 for (auto u : ordering) { 630 if (LLVM_UNLIKELY(in_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) { 631 nextSet.insert(cast<Statement>(Gk[u])); 632 } else if (LLVM_UNLIKELY(out_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) { 633 // some input will also be the output of some subgraph of Gk whenever we cut and 634 // replicated a vertex. We don't need to reevaluate it as part of the next layer. 635 nextSet.erase(cast<Statement>(Gk[u])); 636 } 637 } 638 639 if (LLVM_UNLIKELY(nextSet.empty())) { 640 break; 641 } 642 643 terminals.assign(nextSet.begin(), nextSet.end()); 644 } 645 } 449 } 450 for (auto v : removable) { 451 clear_vertex(v, G); 452 } 453 } 454 } 455 456 } 457 458 459 ///**  * 460 // * @brief summarizeAST 461 // * 462 // * This function scans through a basic block (starting by its terminals) and computes a DAG in which any sequences 463 // * of AND, OR or XOR functions are "flattened" (i.e., allowed to have any number of inputs.) This allows us to 464 // * reassociate them in the most efficient way possible. 465 // **  */ 466 //void BooleanReassociationPass::summarizeAST(PabloBlock & block, std::vector<Statement *> terminals, Graph & G) const { 467 468 // VertexQueue Q(128); 469 // EdgeQueue E; 470 // Map M; 471 472 473 474 // raw_os_ostream out(std::cerr); 475 476 // out << "================================================================\n"; 477 478 // for (;;) { 479 480 481 // Graph Gk; 482 // Map Mk; 483 484 // // Generate a graph depicting the relationships between the terminals. If the original terminals 485 // // cannot be optimized with this algorithm bypass them in favour of their operands. If those cannot 486 // // be optimized, they'll be left as the initial terminals for the next "layer" of the AST. 487 488 // for (Statement * term : terminals) { 489 // if (LLVM_LIKELY(Mk.count(term) == 0)) { 490 // // add or find this terminal in our global graph 491 // Vertex x = getVertex(term, G, M); 492 493 // PabloPrinter::print(term, "term: ", out); 494 // out << '\n'; 495 496 497 // if (inCurrentBlock(term, block)) { 498 // if (isOptimizable(term)) { 499 // const Vertex u = add_vertex(term, Gk); 500 // Mk.insert(std::make_pair(term, u)); 501 // push(u, Q); 502 // continue; 503 // } 504 // } else if (isa<Assign>(term)  isa<Next>(term)) { 505 // // If this is an Assign (Next) node whose operand does not originate from the current block 506 // // then check to see if there is an If (While) node that does. 507 // Statement * branch = nullptr; 508 // if (isa<Assign>(term)) { 509 // for (PabloAST * user : term>users()) { 510 // if (isa<If>(user)) { 511 // const If * ifNode = cast<If>(user); 512 // if (inCurrentBlock(ifNode, block)) { 513 // const auto & defs = ifNode>getDefined(); 514 // if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), cast<Assign>(term)) != defs.end())) { 515 // branch = cast<Statement>(user); 516 // break; 517 // } 518 // } 519 // } 520 // } 521 // } else { // if (isa<Next>(term)) 522 // for (PabloAST * user : term>users()) { 523 // if (isa<While>(user)) { 524 // const While * whileNode = cast<While>(user); 525 // if (inCurrentBlock(whileNode, block)) { 526 // const auto & vars = whileNode>getVariants(); 527 // if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), cast<Next>(term)) != vars.end())) { 528 // branch = cast<Statement>(user); 529 // break; 530 // } 531 // } 532 // } 533 // } 534 // } 535 536 // // If we didn't find a branch, then the Assign (Next) node must have come from a preceeding 537 // // block. Just skip it for now. 538 // if (branch == nullptr) { 539 // continue; 540 // } 541 542 // // Otherwise add the branch to G and test its operands rather than the original terminal 543 // const Vertex z = getVertex(branch, G, M); 544 // add_edge(z, x, G); 545 // x = z; 546 // term = branch; 547 548 // } 549 550 // for (unsigned i = 0; i != term>getNumOperands(); ++i) { 551 // PabloAST * const op = term>getOperand(i); 552 // if (LLVM_LIKELY(inCurrentBlock(op, block))) { 553 // const Vertex y = getVertex(op, G, M); 554 // add_edge(y, x, G); 555 556 // if (LLVM_LIKELY(Mk.count(op) == 0)) { 557 // const Vertex v = add_vertex(op, Gk); 558 // Mk.insert(std::make_pair(op, v)); 559 // push(v, Q); 560 // } 561 // } 562 // } 563 // } 564 // } 565 566 // out << "\n"; 567 // out.flush(); 568 569 // if (LLVM_UNLIKELY(Q.empty())) { 570 // break; 571 // } 572 573 // for (;;) { 574 // const Vertex u = pop(Q); 575 // if (isOptimizable(Gk[u])) { 576 // Statement * stmt = cast<Statement>(Gk[u]); 577 // // If any user of this statement is not in the current block, determine the outermost If/While node 578 // // that contains this statement within and add an edge from this statement to it to denote both the 579 // // topological ordering necessary and that this statement must be computed. 580 // for (PabloAST * user : stmt>users()) { 581 // if (LLVM_LIKELY(isa<Statement>(user))) { 582 // PabloBlock * parent = cast<Statement>(user)>getParent(); 583 // if (LLVM_UNLIKELY(parent != &block)) { 584 // while (parent>getParent() != &block) { 585 // parent = parent>getParent(); 586 // } 587 // if (LLVM_UNLIKELY(parent == nullptr)) { 588 // throw std::runtime_error("Could not locate nested scope block!"); 589 // } 590 // const auto f = mResolvedScopes.find(parent); 591 // if (LLVM_UNLIKELY(f == mResolvedScopes.end())) { 592 // throw std::runtime_error("Failed to resolve scope block!"); 593 // } 594 // add_edge(u, getVertex(f>second, Gk, Mk), Gk); 595 // } 596 // } 597 // } 598 // // Scan through the usedef chains to locate any chains of rearrangable expressions and their inputs 599 // for (unsigned i = 0; i != 2; ++i) { 600 // PabloAST * op = stmt>getOperand(i); 601 // auto f = Mk.find(op); 602 // if (f == Mk.end()) { 603 // const Vertex v = add_vertex(op, Gk); 604 // f = Mk.insert(std::make_pair(op, v)).first; 605 // if (op>getClassTypeId() == stmt>getClassTypeId() && inCurrentBlock(cast<Statement>(op), block)) { 606 // push(v, Q); 607 // } 608 // } 609 // add_edge(f>second, u, Gk); 610 // } 611 // } 612 // if (Q.empty()) { 613 // break; 614 // } 615 // } 616 617 // printGraph(block, Gk, "Gk1"); 618 619 // // Generate a topological ordering for G; if one of our terminals happens to also be a partial computation of 620 // // another terminal, we need to make sure we compute it as an independent subexpression. 621 // std::vector<unsigned> ordering; 622 // ordering.reserve(num_vertices(Gk)); 623 // topological_sort(Gk, std::back_inserter(ordering)); 624 // std::vector<unsigned> component(num_vertices(Gk), 0); 625 626 // // Mark which computation component each terminal is in based on their topological (occurence) order. 627 // unsigned components = 0; 628 // std::sort(terminals.begin(), terminals.end()); 629 // for (auto u : ordering) { 630 // unsigned id = 0; 631 // // If this is a sink in G, it is the root of a new component. 632 // if (out_degree(u, Gk) == 0  std::binary_search(terminals.begin(), terminals.end(), Gk[u])) { 633 // id = ++components; 634 // } else { // otherwise it belongs to the outermost component. 635 // for (auto e : make_iterator_range(out_edges(u, Gk))) { 636 // assert (component[target(e, Gk)] != 0); 637 // id = std::max(id, component[target(e, Gk)]); 638 // } 639 // } 640 // assert (id && "Topological ordering failed!"); 641 // component[u] = id; 642 // } 643 644 // for (;;) { 645 646 // // Cut the graph wherever a computation crosses a component or whenever we need to cut the graph because 647 // // the instructions corresponding to the pair of nodes differs. 648 // graph_traits<Graph>::edge_iterator ei, ei_end; 649 // for (std::tie(ei, ei_end) = edges(Gk); ei != ei_end; ) { 650 // const Graph::edge_descriptor e = *ei++; 651 // const Vertex u = source(e, Gk); 652 // const Vertex v = target(e, Gk); 653 // if (LLVM_UNLIKELY(isCutNecessary(u, v, Gk, component))) { 654 // E.push(std::make_pair(u, v)); 655 // remove_edge(u, v, Gk); 656 // } 657 // } 658 659 // // If no cuts are necessary, we're done. 660 // if (E.empty()) { 661 // break; 662 // } 663 664 // for (;;) { 665 666 // Vertex u, v; 667 // std::tie(u, v) = E.front(); E.pop(); 668 669 // // The vertex belonging to a component with a greater number must come "earlier" 670 // // in the program. By replicating it, this ensures it's computed as an output of 671 // // one component and used as an input of another. 672 // if (component[u] < component[v]) { 673 // std::swap(u, v); 674 // } 675 676 // // Replicate u and fix the ordering and component vectors to reflect the change in Gk. 677 // const Vertex w = add_vertex(Gk[u], Gk); 678 // ordering.insert(std::find(ordering.begin(), ordering.end(), u), w); 679 // assert (component.size() == w); 680 // component.push_back(component[v]); 681 // add_edge(w, v, Gk); 682 683 // // However, after we do so, we need to make sure the original source vertex will be a 684 // // sink in Gk unless it is also an input variable (in which case we'd simply end up with 685 // // extraneous isolated vertex. Otherwise, we need to make further cuts and replications. 686 // if (in_degree(u, Gk) != 0) { 687 // for (auto e : make_iterator_range(out_edges(u, Gk))) { 688 // E.push(std::make_pair(source(e, Gk), target(e, Gk))); 689 // } 690 // clear_out_edges(u, Gk); 691 // } 692 693 // if (E.empty()) { 694 // break; 695 // } 696 // } 697 698 // // Mark which computation component each sink is in based on their topological (occurence) order. 699 // unsigned components = 0; 700 // #ifndef NDEBUG 701 // std::fill(component.begin(), component.end(), 0); 702 // #endif 703 // for (auto u : ordering) { 704 // unsigned id = 0; 705 // // If this is a sink in G, it is the root of a new component. 706 // if (out_degree(u, Gk) == 0) { 707 // id = ++components; 708 // } else { // otherwise it belongs to the outermost component. 709 // for (auto e : make_iterator_range(out_edges(u, Gk))) { 710 // assert (component[target(e, Gk)] != 0); 711 // id = std::max(id, component[target(e, Gk)]); 712 // } 713 // } 714 // assert (id && "Topological ordering failed!"); 715 // component[u] = id; 716 // } 717 // } 718 719 // printGraph(block, Gk, "Gk2"); 720 721 // // Scan through the graph so that we process the outermost expressions first 722 // for (const Vertex u : ordering) { 723 // if (LLVM_UNLIKELY(out_degree(u, Gk) == 0)) { 724 // // Create a vertex marking the output statement we may end up replacing 725 // // and collect the set of source variables in the component 726 // const Vertex x = getVertex(Gk[u], G, M); 727 // if (LLVM_LIKELY(in_degree(u, Gk) > 0)) { 728 // flat_set<PabloAST *> vars; 729 // flat_set<Vertex> visited; 730 // for (Vertex v = u;;) { 731 // if (in_degree(v, Gk) == 0) { 732 // vars.insert(Gk[v]); 733 // } else { 734 // for (auto e : make_iterator_range(in_edges(v, Gk))) { 735 // const Vertex w = source(e, Gk); 736 // if (LLVM_LIKELY(visited.insert(w).second)) { 737 // push(w, Q); 738 // } 739 // } 740 // } 741 // if (Q.empty()) { 742 // break; 743 // } 744 // v = pop(Q); 745 // } 746 // for (PabloAST * var : vars) { 747 // add_edge(getVertex(var, G, M), x, G); 748 // } 749 // } 750 // } 751 // } 752 753 // // Determine the source variables of the next "layer" of the AST 754 // flat_set<Statement *> nextSet; 755 // for (auto u : ordering) { 756 // if (LLVM_UNLIKELY(in_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) { 757 // nextSet.insert(cast<Statement>(Gk[u])); 758 // } else if (LLVM_UNLIKELY(out_degree(u, Gk) == 0 && isa<Statement>(Gk[u]))) { 759 // // some input will also be the output of some subgraph of Gk whenever we cut and 760 // // replicated a vertex. We don't need to reevaluate it as part of the next layer. 761 // nextSet.erase(cast<Statement>(Gk[u])); 762 // } 763 // } 764 765 // if (LLVM_UNLIKELY(nextSet.empty())) { 766 // break; 767 // } 768 769 // out << "\n"; 770 771 // terminals.assign(nextSet.begin(), nextSet.end()); 772 // } 773 774 775 776 //} 646 777 647 778 using VertexSet = std::vector<Vertex>; … … 1028 1159 } 1029 1160 1030 printGraph(block, H, G, "H0");1031 1032 1161 segmentInto3LevelGraph(H); 1033 1162 1034 printGraph(block, H, G, "H1");1035 1036 1163 const VertexSets distributionSets = safeDistributionSets(H); 1037 1164 1038 printGraph(block, H, G, "H 2");1165 printGraph(block, H, G, "H"); 1039 1166 1040 1167 // If no sources remain, no bicliques were found that would have a meaningful impact on the AST. … … 1088 1215 add_edge(y, H[t], G); 1089 1216 } 1217 for (const Vertex u : intermediary) { 1218 if (LLVM_UNLIKELY(in_degree(H[u], G) == 0)) { 1219 clear_out_edges(H[u], G); 1220 } 1221 } 1090 1222 } 1091 1223 anyChanges = true; 
icGREP/icgrepdevel/icgrep/pablo/optimizers/booleanreassociationpass.h
r4756 r4762 22 22 void processScopes(PabloBlock & block, std::vector<Statement *> && terminals); 23 23 void processScope(PabloBlock & block, std::vector<Statement *> && terminals); 24 void summarizeAST(PabloBlock & block, std::vector<Statement *> terminals,Graph & G) const;24 void summarizeAST(PabloBlock & block, Graph & G) const; 25 25 bool redistributeAST(PabloBlock & block, Graph & G) const; 26 26 private: 
icGREP/icgrepdevel/icgrep/pablo/printer_pablos.cpp
r4718 r4762 193 193 if (expr == nullptr) { 194 194 strm << "<nullexpr>"; 195 } 196 else if (isa<const Zeroes>(expr)) { 195 } else if (isa<const Zeroes>(expr)) { 197 196 strm << "0"; 198 } 199 else if (isa<const Ones>(expr)) { 197 } else if (isa<const Ones>(expr)) { 200 198 strm << "1"; 201 } 202 else if (const Var * var = dyn_cast<const Var>(expr)) { 199 } else if (const Var * var = dyn_cast<const Var>(expr)) { 203 200 strm << var>getName(); 204 } 205 else if (const Next * next = dyn_cast<const Next>(expr)) { 201 } else if (const Next * next = dyn_cast<const Next>(expr)) { 206 202 strm << "Next(" << next>getName() << ")"; 207 } 208 else if (const Statement * stmt = dyn_cast<Statement>(expr)) { 203 } else if (const If * ifstmt = dyn_cast<If>(expr)) { 204 strm << "if "; 205 print(ifstmt>getCondition(), strm); 206 } else if (const While * whl = dyn_cast<While>(expr)) { 207 strm << "while "; 208 print(whl>getCondition(), strm); 209 } else if (const Statement * stmt = dyn_cast<Statement>(expr)) { 209 210 strm << stmt>getName(); 210 } 211 else { 211 } else { 212 212 strm << "**UNKNOWN Pablo Expression type **\n" << "\n"; 213 213 }
Note: See TracChangeset
for help on using the changeset viewer.