Changeset 5570
 Timestamp:
 Jul 17, 2017, 2:23:40 PM (5 weeks ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/distributivepass.cpp
r5567 r5570 17 17 #include <pablo/pe_var.h> 18 18 #include <pablo/pe_zeroes.h> 19 #include <pablo/builder.hpp> 19 20 20 21 #include <pablo/optimizers/pablo_simplifier.hpp> … … 30 31 #include <set> 31 32 #include <unordered_set> 32 #include <random>33 33 34 34 #ifndef NDEBUG … … 49 49 50 50 using TypeId = pablo::PabloAST::ClassTypeId; 51 51 52 enum class State { 52 53 Dead … … 98 99 * (DISTRIBUTIVITY) (A â§ B) âš (A â§ C) â A â§ (B âš C) and (A âš B) â§ (A âš C) â A âš (B â§ C) 99 100 * 101 * (DE MORGAN'S) Â¬(A â§ B) â Â¬A âš Â¬B and Â¬(A âš B) â Â¬A â§ Â¬B 102 * 100 103 * Try to simplify the equations and eliminate some of the unnecessary statements 101 104 **  */ 102 105 bool run(PabloKernel * const kernel) { 103 106 readAST(kernel>getEntryBlock()); 104 if ( simplifyGraph()) {107 if (LLVM_LIKELY(simplifyGraph())) { 105 108 rewriteAST(kernel>getEntryBlock()); 106 109 return true; … … 109 112 } 110 113 111 PassContainer()112 : R(std::random_device()()) {113 114 }115 116 114 protected: 117 115 118 #if !defined(NDEBUG) defined(PRINT_DEBUG)116 #if defined(PRINT_DEBUG) 119 117 /**  * 120 118 * @brief printGraph … … 134 132 std::queue<Vertex> Q; 135 133 for (const auto m : restricted) { 136 if (m < n ) {134 if (m < n && isLive(m)) { 137 135 show[m] = true; 138 136 assert (Q.empty()); … … 153 151 } 154 152 } 153 for (auto e : make_iterator_range(out_edges(m, G))) { 154 const auto v = target(e, G); 155 show[v] = isLive(v) ? true : show[v]; 156 } 155 157 } 156 158 } … … 169 171 std::tie(expr, typeId, state, std::ignore) = G[u]; 170 172 173 bool space = true; 174 171 175 switch (typeId) { 172 176 case TypeId::And: 173 out << "(â§) 177 out << "(â§)"; 174 178 break; 175 179 case TypeId::Or: 176 out << "(âš) 180 out << "(âš)"; 177 181 break; 178 182 case TypeId::Xor: 179 out << "(â) 183 out << "(â)"; 180 184 break; 181 185 case TypeId::Not: 182 out << "(Â¬) 186 out << "(Â¬)"; 183 187 break; 184 188 case TypeId::Zeroes: 185 out << "( 0)";189 out << "(â¥)"; 186 190 break; 187 191 case TypeId::Ones: 188 out << "( 1)";192 out << "(â€)"; 189 193 default: 194 space = false; 190 195 break; 191 196 } 192 193 197 if (expr) { 194 PabloPrinter::print(expr, out); 195 } 198 if (space) { 199 out << ' '; 200 } 201 expr>print(out); 202 } 203 196 204 const bool error = !hasValidOperandIndicies(u); 197 205 … … 261 269 const auto typeId = getType(u); 262 270 263 if (is Regenerable(typeId)) {271 if (isDead(u)  isRegenerable(typeId)) { 264 272 continue; 265 273 } … … 271 279 #endif 272 280 273 #ifndef NDEBUG 274 if (LLVM_UNLIKELY(in_degree(u, G) != stmt>getNumOperands())) { 275 printGraph("E", errs()); 276 errs() << "in degree (" << in_degree(u, G) << ") of " << u << " does not match number of operands (" << stmt>getNumOperands() << ")\n"; 277 } 278 #endif 279 281 assert (isLive(u)); 280 282 assert (stmt>getClassTypeId() == typeId); 283 assert (hasValidOperandIndicies(u)); 281 284 assert (in_degree(u, G) == stmt>getNumOperands()); 282 285 … … 302 305 entry>setInsertPoint(stmt>getPrevNode()); 303 306 304 PabloAST * const replacement = regenerateIfNecessary(stmt, entry, source(*ei, G), count); 305 PabloAST * const op = stmt>getOperand(i); 306 if (LLVM_UNLIKELY(replacement == op)) { 307 continue; 308 } 309 310 #ifdef PRINT_DEBUG 311 errs() << " " << source(*ei, G) << ") replacing "; 312 op>print(errs()); 313 errs() << " with "; 314 replacement>print(errs()); 315 errs() << "\n"; 316 #endif 317 318 stmt>setOperand(i, replacement); 307 stmt>setOperand(i, regenerateIfNecessary(stmt, entry, source(*ei, G), count)); 319 308 } 320 309 321 310 if (LLVM_UNLIKELY(typeId == TypeId::Assign)) { 322 setLastUsageTime(findVertex(stmt>getOperand(0)), count);311 setLastUsageTime(findVertex(stmt>getOperand(0)), ++count); 323 312 } 324 313 setLastUsageTime(u, ++count); … … 341 330 342 331 assert (isLive(u)); 332 const TypeId typeId = getType(u); 343 333 PabloAST * value = isModified(u) ? nullptr : getValue(u); 344 334 if (LLVM_LIKELY(!dominates(value, stmt))) { 345 335 346 const auto n = in_degree(u, G); 347 const TypeId typeId = getType(u); 336 const auto n = in_degree(u, G); 348 337 349 338 #ifdef PRINT_DEBUG … … 367 356 input[i++] = source(e, G); 368 357 } 358 369 359 std::sort(input, input + n, [this](const Vertex u, const Vertex v) { 370 360 return getLastUsageTime(u) < getLastUsageTime(v); 371 361 }); 362 363 PabloBuilder builder(entry); 372 364 value = getValue(input[0]); 373 365 for (unsigned i = 1; i < n; ++i) { … … 375 367 switch (typeId) { 376 368 case TypeId::And: 377 value = entry>createAnd(value, op);369 value = builder.createAnd(value, op); 378 370 break; 379 371 case TypeId::Or: 380 value = entry>createOr(value, op);372 value = builder.createOr(value, op); 381 373 break; 382 374 case TypeId::Xor: 383 value = entry>createXor(value, op);375 value = builder.createXor(value, op); 384 376 break; 385 377 default: … … 390 382 } else if (n == 1) { 391 383 assert (typeId == TypeId::Not); 392 value = getValue(first_source(in_edges(u, G))); 393 value = entry>createNot(value); 394 384 value = entry>createNot(getValue(first_source(in_edges(u, G)))); 395 385 } else if (n > 1) { 396 386 … … 431 421 setUnmodified(u); 432 422 } 433 setLastUsageTime(u, ++count); 423 // negations inherit the last usage time from their operand 424 if (LLVM_UNLIKELY(typeId == TypeId::Not)) { 425 setLastUsageTime(u, getLastUsageTime(first_source(in_edges(u, G)))); 426 } else { 427 setLastUsageTime(u, ++count); 428 } 434 429 return value; 435 430 } … … 441 436 **  */ 442 437 bool simplifyGraph() { 443 444 438 bool modified = false; 445 446 #ifdef PRINT_DEBUG 447 errs() << "********************************************\n"; 448 #endif 449 450 restart: 451 452 #ifdef PRINT_DEBUG 453 errs() << "============================================ (1)\n"; 454 #endif 455 456 getReverseTopologicalOrdering(); 457 458 #ifdef PRINT_DEBUG 459 errs() << "============================================ (2)\n"; 460 #endif 461 462 if (applyAnnulmentAssociativeIdentityIdempotentLaws()) { 463 modified = true; 464 goto restart; 465 } 466 467 #ifdef PRINT_DEBUG 468 errs() << "============================================ (3)\n"; 469 #endif 470 471 472 if (applyAbsorbtionComplementLaws()) { 473 modified = true; 474 goto restart; 475 } 476 477 #ifdef PRINT_DEBUG 478 errs() << "============================================ (4)\n"; 479 #endif 480 439 repeat: getReverseTopologicalOrdering(); 440 compactGraph(); 481 441 if (applyDistributivityLaw()) { 482 442 modified = true; 483 goto restart; 484 } 485 486 if (modified) { 487 488 #ifdef PRINT_DEBUG 489 errs() << "============================================ (5)\n"; 490 #endif 491 492 transitiveReduction(); 493 494 #ifdef PRINT_DEBUG 495 errs() << "============================================ (6)\n"; 496 #endif 497 498 factorizeGraph(); 499 500 #ifdef PRINT_DEBUG 501 // printGraph("G", errs()); 502 #endif 503 } 504 443 goto repeat; 444 } 445 transitiveReduction(); 446 factorizeGraph(); 505 447 return modified; 506 448 } … … 541 483 542 484 /**  * 543 * @brief applyAnnulmentAssociativeIdentityIdempotentLaws544 **  */ 545 bool applyAnnulmentAssociativeIdentityIdempotentLaws() {485 * @brief compactGraph 486 **  */ 487 void compactGraph() { 546 488 547 489 auto IdentityHash = [this](const Vertex u) { … … 605 547 V.reserve(num_vertices(G)); 606 548 607 bool modified = false;608 609 549 for (const auto u : boost::adaptors::reverse(ordering)) { 550 610 551 assert (isLive(u)); 611 assert(hasValidOperandIndicies(u)); 612 613 auto typeId = getType(u); 614 552 553 const auto typeId = getType(u); 615 554 if (LLVM_UNLIKELY(isImmutable(typeId))) { 616 555 continue; … … 620 559 } 621 560 622 if (LLVM_UNLIKELY(isConstant(typeId))) { identity_or_annulment_check: 623 624 assert (typeId == getType(u)); 625 626 const auto n = out_degree(u, G); 627 Vertex T[n]; 628 unsigned count = 0; 629 630 for (auto e : make_iterator_range(out_edges(u, G))) { 631 const auto v = target(e, G); 632 if (LLVM_UNLIKELY(isDistributive(getType(v)))) { 633 assert (count < n); 634 assert (u != v); 635 T[count++] = v; 636 } 637 } 638 639 while (LLVM_UNLIKELY(count != 0)) { 640 641 // typeId targetTypeId Optimization 642 //    643 // Zeroes Or identity 644 // Zeroes And annulment (0) 645 // Ones Or annulment (1) 646 // Ones And identity 647 648 assert (count < n); 649 const auto v = T[count]; 650 setModified(v); 651 modified = true; 652 if (isIdentityRelation(typeId, getType(v))) { 653 #ifdef PRINT_DEBUG 654 errs() << "identity " << v << " >> " << u << "\n"; 655 #endif 656 assert (edge(u, v, G).second); 657 remove_edge(u, v, G); 658 } else { // annulment 659 #ifdef PRINT_DEBUG 660 errs() << "annulment (" << (int)(typeId) << ") " << u << " >> " << v << "\n"; 661 #endif 662 setType(v, typeId); 663 clear_in_edges(v, G); 664 } 665 } 666 561 assert (hasValidOperandIndicies(u)); 562 563 if (LLVM_UNLIKELY(isConstant(typeId))) { 564 if (processConstant(u, typeId)) { 565 continue; 566 } 667 567 } else if (isAssociative(typeId)) { 668 if (LLVM_UNLIKELY(in_degree(u, G) == 0)) { 669 #ifdef PRINT_DEBUG 670 errs() << "nullary associative " << u << "\n"; 671 #endif 672 setModified(u); 673 typeId = TypeId::Zeroes; 674 setType(u, TypeId::Zeroes); 675 modified = true; 676 goto identity_or_annulment_check; 677 } else if (LLVM_UNLIKELY(in_degree(u, G) == 1)) { 678 // An associative operation with only one element is always equivalent to the element 679 const auto v = first_source(in_edges(u, G)); 680 for (const auto e : make_iterator_range(out_edges(u, G))) { 681 addEdge(v, target(e, G), G[e]); 682 } 683 #ifdef PRINT_DEBUG 684 errs() << "unary associative " << v << " >> " << u << "\n"; 685 #endif 686 removeVertex(u); 568 if (processAssociative(u, typeId)) { 687 569 continue; 688 } else {689 // Take the transitive closure of these arcs, we may reveal the underlying equation690 Vertex removed[out_degree(u, G)];691 unsigned n = 0;692 for (auto ei : make_iterator_range(out_edges(u, G))) {693 const auto v = target(ei, G);694 if (typeId == getType(v)) {695 assert(hasValidOperandIndicies(v));696 for (auto ej : make_iterator_range(in_edges(u, G))) {697 addEdge(source(ej, G), v, G[ei]);698 }699 setModified(v);700 removed[n++] = v;701 #ifdef PRINT_DEBUG702 errs() << "transitive associative " << v << " >> " << u << "\n";703 #endif704 }705 }706 for (unsigned i = 0; i < n; ++i) {707 const auto v = removed[i];708 assert (edge(u, v, G).second);709 remove_edge(u, v, G);710 assert(hasValidOperandIndicies(v));711 }712 if (LLVM_UNLIKELY(out_degree(u, G) == 0)) {713 removeVertex(u);714 continue;715 }716 if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {717 // Canonicalize xor operations: (A â Â¬B) = (A â B â 1)718 Vertex negation[in_degree(u, G)];719 unsigned count = 0;720 for (const auto e : make_iterator_range(in_edges(u, G))) {721 const auto v = source(e, G);722 const auto typeId = getType(v);723 if (LLVM_UNLIKELY(typeId == TypeId::Not)) {724 negation[count++] = v;725 }726 }727 if (LLVM_UNLIKELY(count != 0)) {728 #ifdef PRINT_DEBUG729 errs() << "xor canonicalization (a) " << u << "\n";730 #endif731 for (unsigned i = 0; i < count; ++i) {732 const auto v = negation[i];733 assert (edge(v, u, G).second);734 remove_edge(v, u, G);735 addEdge(first_source(in_edges(v, G)), u);736 }737 if ((count & 1) != 0) {738 addEdge(makeVertex(TypeId::Ones), u);739 }740 setModified(u);741 assert(hasValidOperandIndicies(u));742 modified = true;743 }744 }745 570 } 746 571 } else if (typeId == TypeId::Not) { 747 assert (in_degree(u, G) == 1); 748 const auto v = first_source(in_edges(u, G)); 749 const auto negatedTypeId = getType(v); 750 if (LLVM_UNLIKELY(negatedTypeId == TypeId::Not)) { 751 // handle double negation 752 assert (in_degree(v, G) == 1); 753 const auto w = first_source(in_edges(v, G)); 754 for (const auto e : make_iterator_range(out_edges(u, G))) { 755 const auto v = target(e, G); 756 addEdge(w, v, G[e]); 757 setModified(v); 758 } 759 modified = true; 760 #ifdef PRINT_DEBUG 761 errs() << "double negation " << u << " > " << w << "\n"; 762 #endif 763 removeVertex(u); 572 if (processNegation(u, typeId)) { 764 573 continue; 765 } else if (LLVM_UNLIKELY(isConstant(negatedTypeId))) {766 setModified(u);767 typeId = (negatedTypeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes;768 #ifdef PRINT_DEBUG769 errs() << "constant negation (" << (int)typeId << ") " << u << "\n";770 #endif771 setType(u, typeId);772 modified = true;773 goto identity_or_annulment_check;774 } else if (LLVM_UNLIKELY(negatedTypeId == TypeId::Xor)) {775 // Canonicalize xor operations: Â¬(A â B) = (A â B â 1)776 #ifdef PRINT_DEBUG777 errs() << "xor canonicalization (n) " << u << "\n";778 #endif779 setModified(u);780 setType(u, TypeId::Xor);781 clear_in_edges(u, G);782 for (const auto e : make_iterator_range(in_edges(v, G))) {783 add_edge(source(e, G), u, 0, G);784 }785 addEdge(makeVertex(TypeId::Ones), u);786 assert(hasValidOperandIndicies(u));787 modified = true;788 574 } 789 575 } 790 576 791 577 // check whether this vertex is a duplicate 792 constauto f = V.insert(u);578 auto f = V.insert(u); 793 579 if (LLVM_UNLIKELY(!f.second)) { 794 remapVertex(u, *f.first); 795 } 796 } 797 798 return modified; 799 } 800 801 // A XOR NOT(A XOR B) = NOT B 802 803 // A AND NOT(A AND B) = A AND NOT B 804 805 // A AND NOT(A OR B) = 0 806 807 // A OR NOT(A AND B) = 1 808 809 // A OR NOT(A OR B) = A OR NOT B 810 811 // * (ABSORBTION) A âš (A â§ B) â A â§ (A âš B) â A 812 813 /**  * 814 * @brief applyAbsorbtionComplementLaws 815 **  */ 816 bool applyAbsorbtionComplementLaws() { 817 bool modified = false; 818 for (const Vertex u : ordering) { 819 assert (isLive(u)); 820 assert (hasValidOperandIndicies(u)); 821 const TypeId typeId = getType(u); 822 if (isDistributive(typeId)) { 823 assert (in_degree(u, G) > 0); 824 Vertex A[in_degree(u, G)]; 825 unsigned n = 0; 826 for (const auto ei : make_iterator_range(in_edges(u, G))) { 827 const auto v = source(ei, G); 828 assert (isLive(v)); 829 const auto innerTypeId = getType(v); 830 auto w = v; 831 if (innerTypeId == TypeId::Not) { 832 w = first_source(in_edges(v, G)); 833 assert ("G is cyclic!" && (w != v)); 834 assert (isLive(w)); 835 for (const auto ej : make_iterator_range(in_edges(u, G))) { 836 if (LLVM_UNLIKELY(source(ej, G) == w)) { 837 goto do_complement; 838 } 839 } 840 if (LLVM_UNLIKELY(getType(w) == oppositeTypeId(typeId))) { 841 // Check for implicit De Morgan's + Complement law application, e.g., A â§ Â¬(A âš B) â 0 842 goto check_demorgans_complement; 843 } 844 } else if (innerTypeId == oppositeTypeId(typeId)) { 845 check_demorgans_complement: 846 for (const auto ej : make_iterator_range(in_edges(w, G))) { 847 for (const auto ek : make_iterator_range(in_edges(u, G))) { 848 if (LLVM_UNLIKELY(source(ej, G) == source(ek, G))) { 849 if (LLVM_UNLIKELY(innerTypeId == TypeId::Not)) { 850 goto do_complement; 851 } else { 852 A[n++] = v; 853 goto next_variable; 854 } 855 } 856 } 857 } 858 } 859 next_variable: 860 continue; 861 } 862 if (LLVM_UNLIKELY(n != 0)) { 863 setModified(u); 864 modified = true; 865 for (;;) { 866 const auto v = A[n]; 867 #ifdef PRINT_DEBUG 868 errs() << "absorbing " << v << "," << u << "\n"; 869 #endif 870 assert (edge(v, u, G).second); 871 remove_edge(v, u, G);assert (isLive(u)); 872 if (LLVM_UNLIKELY(out_degree(v, G) == 0)) { 873 removeVertex(v); 874 } 875 if (LLVM_LIKELY(n == 0)) { 876 break; 877 } 878 } 879 } 880 } 881 continue; 882 do_complement: 883 //  884 const auto complementTypeId = (typeId == TypeId::And) ? TypeId::Zeroes : TypeId::Ones; 580 remapVertex(u, *f.first); 581 } 582 } 583 } 584 585 /**  * 586 * @brief processAssociative 587 **  */ 588 bool processAssociative(const Vertex u, const TypeId typeId) { 589 590 assert (isLive(u)); 591 assert (getType(u) == typeId); 592 assert (isAssociative(typeId)); 593 594 if (LLVM_UNLIKELY(in_degree(u, G) == 0)) { 885 595 #ifdef PRINT_DEBUG 886 errs() << " complement (" << (int)complementTypeId << ")" << u << "\n";596 errs() << "nullary associative " << u << "\n"; 887 597 #endif 888 598 setModified(u); 889 setType(u, complementTypeId); 599 setType(u, TypeId::Zeroes); 600 return processConstant(u, TypeId::Zeroes); 601 } else if (LLVM_UNLIKELY(in_degree(u, G) == 1)) { 602 // An associative operation with only one element is always equivalent to the element 603 const auto v = first_source(in_edges(u, G)); 604 for (const auto e : make_iterator_range(out_edges(u, G))) { 605 addEdge(v, target(e, G), G[e]); 606 } 607 #ifdef PRINT_DEBUG 608 errs() << "unary associative " << v << " > " << u << "\n"; 609 #endif 610 removeVertex(u); 611 return true; 612 } else { 613 // Take the transitive closure of these arcs to reveal the underlying equations 614 Vertex removed[out_degree(u, G)]; 615 unsigned n = 0; 616 for (auto ei : make_iterator_range(out_edges(u, G))) { 617 const auto v = target(ei, G); 618 if (typeId == getType(v)) { 619 assert(hasValidOperandIndicies(v)); 620 for (auto ej : make_iterator_range(in_edges(u, G))) { 621 addEdge(source(ej, G), v, G[ei]); 622 } 623 setModified(v); 624 removed[n++] = v; 625 #ifdef PRINT_DEBUG 626 errs() << "transitive associative " << v << " > " << u << "\n"; 627 #endif 628 } 629 } 630 for (unsigned i = 0; i < n; ++i) { 631 const auto v = removed[i]; 632 assert (edge(u, v, G).second); 633 remove_edge(u, v, G); 634 assert(hasValidOperandIndicies(v)); 635 } 636 if (LLVM_UNLIKELY(out_degree(u, G) == 0)) { 637 removeVertex(u); 638 return true; 639 } 640 if (LLVM_UNLIKELY(typeId == TypeId::Xor)) { 641 // Canonicalize xor operations: (A â Â¬B) = (A â B â 1) 642 Vertex negation[in_degree(u, G)]; 643 unsigned count = 0; 644 for (const auto e : make_iterator_range(in_edges(u, G))) { 645 const auto v = source(e, G); 646 if (LLVM_UNLIKELY(getType(v) == TypeId::Not)) { 647 negation[count++] = v; 648 } 649 } 650 if (LLVM_UNLIKELY(count != 0)) { 651 #ifdef PRINT_DEBUG 652 errs() << "xor canonicalization (a) " << u << "\n"; 653 #endif 654 for (unsigned i = 0; i < count; ++i) { 655 const auto v = negation[i]; 656 assert (edge(v, u, G).second); 657 remove_edge(v, u, G); 658 addEdge(first_source(in_edges(v, G)), u); 659 } 660 if ((count & 1) != 0) { 661 addEdge(makeVertex(TypeId::Ones), u); 662 } 663 setModified(u); 664 assert(hasValidOperandIndicies(u)); 665 } 666 } else { // perform De Morgan's law expansion 667 applyDeMorgans(u, typeId); 668 return applyAbsorbtionComplementLaw(u, typeId); 669 } 670 } 671 return false; 672 } 673 674 /**  * 675 * @brief processNegation 676 **  */ 677 bool processNegation(const Vertex u, const TypeId typeId) { 678 679 assert (isLive(u)); 680 assert ("negation must have one input!" && in_degree(u, G) == 1); 681 assert (getType(u) == typeId); 682 assert (typeId == TypeId::Not); 683 684 const auto v = first_source(in_edges(u, G)); 685 const auto negatedTypeId = getType(v); 686 if (LLVM_UNLIKELY(negatedTypeId == TypeId::Not)) { // Â¬Â¬A = A 687 const auto w = first_source(in_edges(v, G)); 688 #ifdef PRINT_DEBUG 689 errs() << "double negation " << u << " > " << w << "\n"; 690 #endif 691 for (const auto e : make_iterator_range(out_edges(u, G))) { 692 const auto v = target(e, G); 693 addEdge(w, v, G[e]); 694 setModified(v); 695 } 696 removeVertex(u); 697 return true; 698 } else if (LLVM_UNLIKELY(negatedTypeId == TypeId::Xor)) { 699 // Canonicalize xor operations: Â¬(A â B) = (A â B â 1) 700 #ifdef PRINT_DEBUG 701 errs() << "xor canonicalization (n) " << u << "\n"; 702 #endif 703 setModified(u); 704 setType(u, TypeId::Xor); 890 705 clear_in_edges(u, G); 891 modified = true; 892 } 893 return modified; 894 } 895 896 void print(raw_ostream & out, const Sequence & S) { 897 if (S.empty()) { 898 return; 899 } 900 out << Gd[S[0]]; 901 for (unsigned i = 1; i < S.size(); ++i) { 902 out << ',' << Gd[S[i]]; 903 } 904 } 706 for (const auto e : make_iterator_range(in_edges(v, G))) { 707 add_edge(source(e, G), u, 0, G); 708 } 709 addEdge(makeVertex(TypeId::Ones), u); 710 assert(hasValidOperandIndicies(u)); 711 } 712 return false; 713 } 714 715 /**  * 716 * @brief applyDeMorgans 717 **  */ 718 void applyDeMorgans(const Vertex u, const TypeId typeId) { 719 720 assert (isLive(u)); 721 assert (in_degree(u, G) > 0); 722 assert (getType(u) == typeId); 723 assert (isDistributive(typeId)); 724 725 Vertex A[in_degree(u, G)]; 726 unsigned n = 0; 727 for (const auto e : make_iterator_range(in_edges(u, G))) { 728 const auto v = source(e, G); 729 if (LLVM_UNLIKELY(getType(v) == TypeId::Not)) { 730 const auto w = first_source(in_edges(v, G)); 731 if (LLVM_UNLIKELY(getType(w) == oppositeTypeId(typeId))) { 732 A[n++] = v; 733 } 734 } 735 } 736 737 if (LLVM_UNLIKELY(n != 0)) { 738 for (unsigned i = 0; i < n; ++i) { 739 const auto v = A[i]; 740 #ifdef PRINT_DEBUG 741 errs() << "de morgan's expansion " << v << " > " << u << "\n"; 742 #endif 743 assert (edge(v, u, G).second); 744 assert (getType(v) == TypeId::Not); 745 remove_edge(v, u, G); 746 // NOTE: we cannot remove v even if this was its last edge since 747 // it must be in our duplicate check map 748 const auto w = first_source(in_edges(v, G)); 749 assert (getType(w) == oppositeTypeId(typeId)); 750 for (const auto e : make_iterator_range(in_edges(w, G))) { 751 const auto x = makeVertex(TypeId::Not); 752 add_edge(source(e, G), x, 0, G); 753 addEdge(x, u); 754 } 755 } 756 setModified(u); 757 assert(hasValidOperandIndicies(u)); 758 } 759 760 } 761 762 /**  * 763 * @brief applyAbsorbtionComplementLaw 764 **  */ 765 bool applyAbsorbtionComplementLaw(const Vertex u, const TypeId typeId) { 766 767 assert (isLive(u)); 768 assert (in_degree(u, G) > 0); 769 assert (getType(u) == typeId); 770 assert (isDistributive(typeId)); 771 772 Vertex A[in_degree(u, G)]; 773 unsigned n = 0; 774 for (const auto ei : make_iterator_range(in_edges(u, G))) { 775 const auto v = source(ei, G); 776 assert (isLive(v)); 777 const auto innerTypeId = getType(v); 778 if (innerTypeId == TypeId::Not) { 779 const auto w = first_source(in_edges(v, G)); 780 assert ("G is cyclic!" && (w != v)); 781 assert (isLive(w)); 782 for (const auto ej : make_iterator_range(in_edges(u, G))) { 783 if (LLVM_UNLIKELY(source(ej, G) == w)) { 784 const auto complementTypeId = (typeId == TypeId::And) ? TypeId::Zeroes : TypeId::Ones; 785 #ifdef PRINT_DEBUG 786 errs() << "complement (" << (int)complementTypeId << ") " << u << "\n"; 787 #endif 788 setModified(u); 789 setType(u, complementTypeId); 790 clear_in_edges(u, G); 791 return processConstant(u, complementTypeId); 792 } 793 } 794 } else if (innerTypeId == oppositeTypeId(typeId) && LLVM_UNLIKELY(absorbs(u, v))) { 795 A[n++] = v; 796 } 797 } 798 799 if (n) { 800 setModified(u); 801 for (;;) { 802 const auto v = A[n]; 803 #ifdef PRINT_DEBUG 804 errs() << "absorbing " << v << "," << u << "\n"; 805 #endif 806 assert (edge(v, u, G).second); 807 remove_edge(v, u, G); 808 if (LLVM_UNLIKELY(out_degree(v, G) == 0)) { 809 removeVertex(v); 810 } 811 if (LLVM_LIKELY(n == 0)) { 812 break; 813 } 814 } 815 } 816 817 return false; 818 } 819 820 /**  * 821 * @brief absorbs 822 **  */ 823 bool absorbs(const Vertex u, const Vertex v) { 824 assert (getType(u) == oppositeTypeId(getType(v))); 825 for (const auto ei : make_iterator_range(in_edges(u, G))) { 826 for (const auto ej : make_iterator_range(in_edges(v, G))) { 827 if (LLVM_UNLIKELY(source(ei, G) == source(ej, G))) { 828 return true; 829 } 830 } 831 } 832 return false; 833 } 834 835 /**  * 836 * @brief processConstant 837 **  */ 838 bool processConstant(const Vertex u, const TypeId typeId) { 839 840 const auto l = out_degree(u, G); 841 Vertex modification[l]; 842 unsigned n = 0; 843 unsigned m = 0; 844 845 assert (isConstant(typeId)); 846 assert (getType(u) == typeId); 847 848 for (auto e : make_iterator_range(out_edges(u, G))) { 849 const auto v = target(e, G); 850 const auto targetTypeId = getType(v); 851 if (LLVM_UNLIKELY(isDistributive(targetTypeId))) { 852 // typeId targetTypeId Optimization 853 //    854 // Zeroes Or identity 855 // Zeroes And annulment (0) 856 // Ones Or annulment (1) 857 // Ones And identity 858 if (isIdentityRelation(typeId, targetTypeId)) { 859 #ifdef PRINT_DEBUG 860 errs() << "identity (" << (int)(typeId) << ") " << v << " >> " << u << "\n"; 861 #endif 862 modification[l  ++n] = v; 863 } else { // annulment 864 #ifdef PRINT_DEBUG 865 errs() << "annulment (" << (int)(typeId) << ") " << u << " >> " << v << "\n"; 866 #endif 867 setType(v, typeId); 868 modification[m++] = v; 869 } 870 } else if (LLVM_UNLIKELY(targetTypeId == TypeId::Not)) { 871 const auto negatedTypeId = (typeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes; 872 #ifdef PRINT_DEBUG 873 errs() << "constant negation (" << (int)typeId << ") " << u << "\n"; 874 #endif 875 setType(u, negatedTypeId); 876 modification[m++] = v; 877 } else if (LLVM_UNLIKELY(isStreamOperation(typeId))) { 878 if (LLVM_LIKELY(typeId == TypeId::Zeroes)) { 879 #ifdef PRINT_DEBUG 880 errs() << "zero propagation (" << (int)(typeId) << ") " << u << " >> " << v << "\n"; 881 #endif 882 setType(v, TypeId::Zeroes); 883 modification[m++] = v; 884 } else { // if (typeId == TypeId::Ones) { 885 switch (targetTypeId) { 886 case TypeId::ScanThru: 887 if (LLVM_UNLIKELY(G[e] == 1)) { 888 setType(v, TypeId::Zeroes); 889 modification[m++] = v; 890 } 891 break; 892 case TypeId::MatchStar: 893 if (LLVM_UNLIKELY(G[e] == 0)) { 894 setType(v, TypeId::Ones); 895 modification[m++] = v; 896 } 897 break; 898 default: break; 899 } 900 } 901 } 902 } 903 904 if (LLVM_LIKELY(n == 0 && m == 0)) { 905 return false; 906 } 907 908 // handle any identity graph modifications 909 while (LLVM_UNLIKELY(n != 0)) { 910 const auto v = modification[l  n]; 911 setModified(v); 912 remove_edge(u, v, G); 913 } 914 915 // ... then handle the rest 916 while (LLVM_LIKELY(m != 0)) { 917 const auto v = modification[m]; 918 setModified(v); 919 clear_in_edges(v, G); 920 // We could recursively call "processConstant" but this could cause a stack overflow 921 // in a pathological case. Instead rely on the fact v will be processed eventually by 922 // the outer loop. 923 } 924 925 if (LLVM_UNLIKELY(out_degree(u, G) == 0)) { 926 removeVertex(u); 927 return true; 928 } 929 930 return false; 931 } 932 905 933 906 934 /**  * … … 922 950 makeDistributionSubgraph(); 923 951 952 // If we found no potential opportunities then we cannot apply the distribution law to any part of G. 953 if (LLVM_UNLIKELY(distributable.empty())) { 954 return false; 955 } 956 924 957 bool modified = false; 925 958 926 for (;;) { 927 928 assert (std::is_sorted(D.begin(), D.end())); 929 930 // If we found no potential opportunities then we cannot apply the distribution law to any part of G. 931 if (LLVM_UNLIKELY(D.empty())) { 932 break; 933 } 934 935 #ifdef PRINT_DEBUG 936 if (modified) { 937 errs() << "\n"; 938 } 939 #endif 940 941 const auto lowerSet = obtainDistributableClauses(D); 942 943 for (const auto & lower : lowerSet) { 944 const auto & outer = std::get<0>(lower); 945 const auto upperSet = obtainDistributableSources(std::get<1>(lower)); 946 for (const auto & upper : upperSet) { 947 948 const auto & sources = std::get<1>(upper); 949 const auto & inner = std::get<0>(upper); 950 951 const auto outerTypeId = getType(Gd[outer[0]]); 952 const auto innerTypeId = oppositeTypeId(outerTypeId); 953 954 // Update G to match the desired change 955 const auto x = makeVertex(outerTypeId); 956 const auto y = makeVertex(innerTypeId); 957 958 #ifdef PRINT_DEBUG 959 errs() << "distributing {"; 960 print(errs(), sources); 961 if (innerTypeId == TypeId::And) { 962 errs() << "} â§ {"; 963 } else { 964 errs() << "} âš {"; 965 } 966 print(errs(), inner); 967 if (outerTypeId == TypeId::Or) { 968 errs() << "} âš {"; 969 } else { 970 errs() << "} â§ {"; 971 } 972 print(errs(), outer); 973 errs() << "} > " << x << ',' << y << '\n'; 974 #endif 975 976 for (const auto i : inner) { 977 const auto u = Gd[i]; 978 assert (getType(u) == innerTypeId); 979 for (const Vertex j : outer) { 980 const auto v = Gd[j]; 981 assert (getType(v) == outerTypeId); 982 assert (edge(u, v, G).second); 983 remove_edge(i, j, Gd); 984 remove_edge(u, v, G); 985 } 986 addEdge(u, x); 987 } 988 989 for (const Vertex i : sources) { 990 const auto u = Gd[i]; 991 for (const Vertex j : inner) { 992 const auto v = Gd[j]; 993 assert (edge(u, v, G).second); 994 remove_edge(i, j, Gd); 995 remove_edge(u, v, G); 996 } 997 998 addEdge(u, y); 999 } 1000 1001 addEdge(x, y); 1002 1003 for (const Vertex i : outer) { 1004 const auto u = Gd[i]; 1005 setModified(u); 1006 addEdge(y, u); 1007 } 1008 1009 modified = true; 1010 } 1011 } 1012 1013 for (;;) { 1014 if (LLVM_UNLIKELY(D.size() == 1)) { 1015 D.clear(); 1016 break; 1017 } 1018 std::uniform_int_distribution<> dist(0, D.size()  1); 1019 const auto p = D.begin() + dist(R); 1020 const auto u = *p; 1021 D.erase(p); 1022 bool found = false; 1023 for (auto e : make_iterator_range(in_edges(u, Gd))) { 1024 const auto v = source(e, G); 1025 if (canDistribute(v, 1)) { 1026 auto f = std::lower_bound(D.begin(), D.end(), v); 1027 if (f == D.end()  *f != v) { 1028 D.insert(f, v); 1029 found = true; 1030 } 1031 } 1032 } 1033 clear_in_edges(u, Gd); 1034 if (found) { 1035 break; 1036 } 959 const auto lowerSet = obtainDistributableClauses(distributable); 960 for (const auto & lower : lowerSet) { 961 const auto & outer = std::get<0>(lower); 962 const auto upperSet = obtainDistributableSources(std::get<1>(lower)); 963 for (const auto & upper : upperSet) { 964 const auto & inner = std::get<0>(upper); 965 const auto & sources = std::get<1>(upper); 966 967 const auto outerTypeId = getType(Gd[outer[0]]); 968 const auto innerTypeId = oppositeTypeId(outerTypeId); 969 970 // Update G to match the desired change 971 const auto x = makeVertex(outerTypeId); 972 const auto y = makeVertex(innerTypeId); 973 974 #ifdef PRINT_DEBUG 975 errs() << "distributing {"; 976 print_dist(errs(), sources); 977 if (innerTypeId == TypeId::And) { 978 errs() << "} â§ {"; 979 } else { 980 errs() << "} âš {"; 981 } 982 print_dist(errs(), inner); 983 if (outerTypeId == TypeId::Or) { 984 errs() << "} âš {"; 985 } else { 986 errs() << "} â§ {"; 987 } 988 print_dist(errs(), outer); 989 errs() << "} > " << x << ',' << y << '\n'; 990 #endif 991 992 for (const Vertex i : sources) { 993 const auto u = Gd[i]; 994 for (const Vertex j : inner) { 995 const auto v = Gd[j]; 996 assert (edge(u, v, G).second); 997 assert (getType(v) == innerTypeId); 998 remove_edge(u, v, G); 999 } 1000 addEdge(u, y); 1001 } 1002 1003 for (const auto i : inner) { 1004 const auto u = Gd[i]; 1005 assert (getType(u) == innerTypeId); 1006 for (const Vertex j : outer) { 1007 const auto v = Gd[j]; 1008 assert (edge(u, v, G).second); 1009 assert (getType(v) == outerTypeId); 1010 remove_edge(u, v, G); 1011 } 1012 addEdge(u, x); 1013 } 1014 1015 addEdge(x, y); 1016 1017 for (const Vertex i : outer) { 1018 const auto u = Gd[i]; 1019 assert (getType(u) == outerTypeId); 1020 setModified(u); 1021 addEdge(y, u); 1022 } 1023 1024 modified = true; 1037 1025 } 1038 1026 } … … 1048 1036 **  */ 1049 1037 void makeDistributionSubgraph() { 1050 assert (D.empty()); 1051 for (const auto u : make_iterator_range(vertices(G))) { 1052 if (isLive(u)) { 1038 // TODO: instead of creating a subgraph, mark the vertices in G as being part of the subgraph? The last usage 1039 // time could be a "round counter" 1040 distributable.clear(); 1041 for (const auto u : boost::adaptors::reverse(ordering)) { 1042 if (LLVM_LIKELY(isLive(u) && out_degree(u, G) != 0)) { 1053 1043 const auto outerTypeId = getType(u); 1054 1044 if (isDistributive(outerTypeId)) { 1055 const auto innerTypeId = oppositeTypeId(outerTypeId); 1056 for (auto ei : make_iterator_range(in_edges(u, G))) { 1045 const auto n = in_degree(u, G); 1046 assert (n > 1); 1047 const auto innerTypeId = oppositeTypeId(getType(u)); 1048 Vertex D[n]; 1049 unsigned count = 0; 1050 for (const auto ei : make_iterator_range(in_edges(u, G))) { 1057 1051 const auto v = source(ei, G); 1058 1052 assert (isLive(v)); 1059 // can we distribute this vertex?1060 1053 if (getType(v) == innerTypeId) { 1061 // is it safe to add v to the distribution graph? I.e., do we need to calculate its value anyway?1062 1054 bool safe = true; 1063 for ( auto ej : make_iterator_range(out_edges(v, G))) {1055 for (const auto ej : make_iterator_range(out_edges(v, G))) { 1064 1056 const auto w = target(ej, G); 1065 if (isLive(w) && getType(w) != outerTypeId) { 1057 assert (isLive(w)); 1058 if (getType(w) != outerTypeId) { 1066 1059 safe = false; 1067 1060 break; … … 1069 1062 } 1070 1063 if (safe) { 1071 D .push_back(v);1064 D[count++] = v; 1072 1065 } 1073 1066 } 1074 1067 } 1075 if (D.size() > 1) { 1076 std::sort(D.begin(), D.end()); 1077 D.erase(std::unique(D.begin(), D.end()), D.end()); 1078 if (LLVM_LIKELY(D.size() > 1)) { 1079 const auto du = addDistributionVertex(u); 1080 for (const auto v : D) { 1081 assert (isLive(v) && getType(v) == innerTypeId); 1068 if (count > 1) { 1069 const auto du = addDistributionVertex(u); 1070 for (unsigned i = 0; i < count; ++i) { 1071 const auto v = D[i]; 1072 assert (isLive(v)); 1073 if (getType(v) == innerTypeId) { 1082 1074 const auto dv = addDistributionVertex(v); 1083 1075 add_edge(dv, du, Gd); 1084 for ( auto ej : make_iterator_range(in_edges(v, G))) {1085 const auto x= source(ej, G);1086 assert (isLive( x));1087 add_edge(addDistributionVertex( x), dv, Gd);1076 for (const auto ej : make_iterator_range(in_edges(v, G))) { 1077 const auto w = source(ej, G); 1078 assert (isLive(w)); 1079 add_edge(addDistributionVertex(w), dv, Gd); 1088 1080 } 1089 1081 } 1090 1082 } 1091 } 1092 D.clear(); 1093 } 1094 } 1095 } 1096 1097 assert (D.empty()); 1098 for (auto u : make_iterator_range(vertices(Gd))) { 1099 if (out_degree(u, Gd) == 0) { 1100 assert (canDistribute(u)); 1101 D.push_back(u); 1102 } 1103 } 1104 } 1105 1106 /**  * 1107 * @brief canDistribute 1108 **  */ 1109 bool canDistribute(const DistributionVertex u, const unsigned outDegree = 0) const { 1110 assert (u < num_vertices(Gd)); 1111 assert (isLive(Gd[u])); 1112 if (out_degree(u, Gd) == outDegree && in_degree(u, Gd) > 0) { 1113 const auto typeId = oppositeTypeId(getType(Gd[u])); 1114 unsigned count = 0; 1115 for (auto e : make_iterator_range(in_edges(u, Gd))) { 1116 if (getType(Gd[source(e, Gd)]) == typeId) { 1117 if (count == 1) { 1118 return true; 1119 } 1120 ++count; 1121 } 1122 } 1123 } 1124 return false; 1083 distributable.push_back(du); 1084 } 1085 } 1086 } 1087 } 1088 std::sort(distributable.begin(), distributable.end()); 1125 1089 } 1126 1090 … … 1129 1093 **  */ 1130 1094 BicliqueSet obtainDistributableClauses(const Sequence & S) { 1131 1132 struct OppositeType { 1133 bool operator()(const DistributionVertex u) { 1134 return self.getType(self.Gd[u]) == typeId; 1135 } 1136 OppositeType(PassContainer * const pc, const DistributionVertex u) 1137 : self(*pc) 1138 , typeId(oppositeTypeId(self.getType(self.Gd[u]))) { 1139 1140 } 1141 private: 1142 PassContainer & self; 1143 const TypeId typeId; 1144 }; 1145 1146 struct AllUsers { 1147 bool operator()(const DistributionVertex u) { 1148 return out_degree(self.Gd[u], self.G) == degree; 1149 } 1150 AllUsers(PassContainer * const pc, const DistributionVertex u) 1151 : self(*pc) 1152 , degree(out_degree(self.Gd[u], self.G)) { 1153 1154 } 1155 private: 1156 PassContainer & self; 1157 const size_t degree; 1158 }; 1159 1160 // return makeIndependent(enumerateBicliques<OppositeType, AllUsers>(S, Gd, 1, 2), 1); 1161 1162 return enumerateBicliques<OppositeType, AllUsers>(S, Gd, 1, 2); 1095 auto cliques = enumerateBicliques(S, Gd, 1, 2); 1096 // remove any cliques from our set that do not contain all of their users 1097 for (auto ci = cliques.begin(); ci != cliques.end(); ) { 1098 const auto & A = std::get<0>(*ci); 1099 auto & B = std::get<1>(*ci); 1100 for (auto bi = B.begin(); bi != B.end(); ) { 1101 if (out_degree(Gd[*bi], G) != A.size()) { 1102 bi = B.erase(bi); 1103 } else { 1104 ++bi; 1105 } 1106 } 1107 if (B.size() < 2) { 1108 ci = cliques.erase(ci); 1109 } else { 1110 ++ci; 1111 } 1112 } 1113 return makeIndependent(std::move(cliques), 0); 1163 1114 } 1164 1115 … … 1167 1118 **  */ 1168 1119 BicliqueSet obtainDistributableSources(const Sequence & S) { 1169 return makeIndependent(enumerateBicliques <>(S, Gd, 2, 1), 0);1120 return makeIndependent(enumerateBicliques(S, Gd, 2, 1), 0); 1170 1121 } 1171 1122 … … 1196 1147 } 1197 1148 #endif 1198 const auto m = in_degree(u, G);1199 1149 for (const auto w : T) { 1200 1150 remove_edge(w, u, G); 1201 1151 } 1202 1152 T.clear(); 1203 const auto n = in_degree(u, G); 1204 assert (n != 0 && n <= m); 1205 if (LLVM_UNLIKELY(n == 1)) { 1206 // An associative operation with only one element is always equivalent to the element 1207 const auto v = first_source(in_edges(u, G)); 1208 #ifdef PRINT_DEBUG 1209 errs() << "unary associative " << v << " >> " << u << " (tr)\n"; 1210 #endif 1211 for (auto e : make_iterator_range(out_edges(u, G))) { 1212 addEdge(v, target(e, G), G[e]); 1213 } 1214 removeVertex(u); 1215 } else if (LLVM_UNLIKELY(m != n)) { 1216 #ifdef PRINT_DEBUG 1217 errs() << "transitive reduction " << u << "\n"; 1218 #endif 1219 setModified(u); 1220 } 1221 } 1222 } 1153 assert (in_degree(u, G) > 1); 1154 } 1155 } 1156 } 1157 } 1158 1159 void print_dist(raw_ostream & out, const Sequence & S) { 1160 if (S.empty()) { 1161 return; 1162 } 1163 out << Gd[S[0]]; 1164 for (unsigned i = 1; i < S.size(); ++i) { 1165 out << ',' << Gd[S[i]]; 1166 } 1167 } 1168 1169 void print(raw_ostream & out, const Sequence & S) { 1170 if (S.empty()) { 1171 return; 1172 } 1173 out << S[0]; 1174 for (unsigned i = 1; i < S.size(); ++i) { 1175 out << ',' << S[i]; 1223 1176 } 1224 1177 } … … 1250 1203 for (unsigned i = 0; i < 3; ++i) { 1251 1204 1252 for (;;) { 1253 1254 auto factors = makeIndependent(enumerateBicliques<>(groups[i], G, 2, 2), 1); 1255 if (factors.empty()) { 1256 break; 1257 } 1258 1259 bool noChanges = true; 1260 1261 for (auto & factor : factors) { 1262 auto & targets = std::get<0>(factor); 1263 assert (targets.size() > 1); 1264 auto & sources = std::get<1>(factor); 1265 assert (sources.size() > 1); 1266 1267 // One of the targets may be our replacement vertex. 1268 // If so, its in degree will equal sources. 1269 Vertex x = 0; 1270 bool create = true; 1271 for (auto j = targets.begin(); j != targets.end(); ) { 1272 assert (hasValidOperandIndicies(*j)); 1273 if (in_degree(*j, G) == sources.size()) { 1274 x = *j; 1275 j = targets.erase(j); 1276 create = false; 1277 } else { 1278 ++j; 1205 // Although we risk losing better combinations by greedily taking the larger factorings, 1206 // choosing only those of minSize or greater first can significantly reduce the running 1207 // time of this optimization. 1208 1209 for (unsigned minSize = 64; minSize >= 2; minSize /= 2) { 1210 1211 for (;;) { 1212 1213 #ifdef PRINT_DEBUG 1214 errs() << "\n"; 1215 #endif 1216 1217 auto factors = makeIndependent(enumerateBicliques(groups[i], G, 2, minSize), 1); 1218 if (factors.empty()) { 1219 break; 1220 } 1221 1222 for (auto & factor : factors) { 1223 const auto & sources = std::get<1>(factor); 1224 assert (sources.size() > 1); 1225 auto & targets = std::get<0>(factor); 1226 assert (targets.size() > 1); 1227 1228 #ifdef PRINT_DEBUG 1229 errs() << "factoring {"; 1230 print(errs(), sources); 1231 switch (op[i]) { 1232 case TypeId::And: errs() << "} â§ {"; break; 1233 case TypeId::Or: errs() << "} âš {"; break; 1234 case TypeId::Xor: errs() << "} â {"; break; 1235 default: llvm_unreachable("impossible"); 1279 1236 } 1280 } 1281 if (LLVM_UNLIKELY(targets.empty())) { 1282 continue; 1283 } 1284 if (create) { 1285 x = makeVertex(op[i]); 1286 groups[i].push_back(x); 1237 print(errs(), targets); 1238 errs() << "} > "; 1239 #endif 1240 1241 // Check whether one of the targets is the factorization 1242 Vertex x = 0; 1243 bool create = true; 1244 for (auto j = targets.begin(); j != targets.end(); ) { 1245 assert (hasValidOperandIndicies(*j)); 1246 if (in_degree(*j, G) == sources.size()) { 1247 if (LLVM_LIKELY(create)) { 1248 x = *j; 1249 create = false; 1250 } else { 1251 for (auto e : make_iterator_range(out_edges(*j, G))) { 1252 addEdge(x, target(e, G), G[e]); 1253 } 1254 removeVertex(*j); 1255 } 1256 j = targets.erase(j); 1257 } else { 1258 ++j; 1259 } 1260 } 1261 if (create) { 1262 x = makeVertex(op[i]); 1263 groups[i].push_back(x); 1264 for (auto u : sources) { 1265 add_edge(u, x, 0, G); 1266 } 1267 assert (hasValidOperandIndicies(x)); 1268 } 1269 #ifdef PRINT_DEBUG 1270 errs() << x << '\n'; 1271 #endif 1272 1273 // Remove the biclique between the source and target vertices 1287 1274 for (auto u : sources) { 1288 addEdge(u, x); 1275 for (auto v : targets) { 1276 assert (getType(v) == op[i]); 1277 assert (edge(u, v, G).second); 1278 boost::remove_edge(u, v, G); 1279 } 1289 1280 } 1290 } 1291 1292 // Clear out the biclique between the source and target vertices. 1293 for (auto u : sources) { 1281 1282 // ... and replace it with the factorization 1294 1283 for (auto v : targets) { 1295 assert (edge(u, v, G).second); 1296 boost::remove_edge(u, v, G); 1284 assert (getType(v) == op[i]); 1285 addEdge(x, v); 1286 setModified(v); 1287 assert(hasValidOperandIndicies(v)); 1297 1288 } 1298 1289 } 1299 1300 for (auto v : targets) { 1301 assert (getType(v) == op[i]); 1302 addEdge(x, v); 1303 setModified(v); 1304 assert(hasValidOperandIndicies(v)); 1305 } 1306 1307 noChanges = false; 1308 } 1309 if (LLVM_UNLIKELY(noChanges)) { 1310 break; 1311 } 1312 } 1313 } 1314 } 1290 } 1291 } 1292 } 1293 } 1294 1295 private: 1315 1296 1316 1297 /**  * … … 1318 1299 * 1319 1300 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal 1320 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set Ato be in1321 * bipartition A and their adjacencies to be in B.1301 * bicliques" by Alexe et. al. (2003). This implementation considers all verticies in set S to be in 1302 * bipartition A (0) and their *INCOMING* adjacencies to be in B (1). 1322 1303 **  */ 1323 1304 template <typename Graph> 1324 struct AcceptAny {1325 bool operator()(const typename Graph::vertex_descriptor) { return true; }1326 AcceptAny(PassContainer * const, const typename Graph::vertex_descriptor) { }1327 };1328 1329 template <typename AcceptIntoA = AcceptAny<Graph>, typename AcceptIntoB = AcceptAny<Graph>, typename Graph>1330 1305 BicliqueSet enumerateBicliques(const Sequence & S, const Graph & G, const unsigned minimumSizeA = 1, const unsigned minimumSizeB = 1) { 1331 1306 using IntersectionSets = std::set<Sequence>; … … 1335 1310 BicliqueSet cliques(0); 1336 1311 1337 if ( S.size() >= minimumSizeA) {1312 if (LLVM_LIKELY(S.size() >= minimumSizeA)) { 1338 1313 1339 1314 IntersectionSets B1; 1340 1315 for (auto u : S) { 1341 1316 const auto n = in_degree(u, G); 1342 if (n > 0) {1317 if (n >= minimumSizeB) { 1343 1318 Sequence B; 1344 1319 B.reserve(n); 1345 AcceptIntoB acceptor(this, u);1346 1320 for (auto e : make_iterator_range(in_edges(u, G))) { 1347 1321 const auto v = source(e, G); 1348 if ( acceptor(v)) {1322 if (out_degree(v, G) >= minimumSizeA) { 1349 1323 B.push_back(v); 1350 1324 } … … 1362 1336 IntersectionSets Bi; 1363 1337 1364 Sequence clique;1365 for (auto i = B1.begin() ; i != B1.end(); ++i) {1338 Sequence T; 1339 for (auto i = B1.begin(), end = B1.end(); i != end; ++i) { 1366 1340 assert (std::is_sorted(i>begin(), i>end())); 1367 for (auto j = i; ++j != B1.end(); ) {1341 for (auto j = i; ++j != end; ) { 1368 1342 assert (std::is_sorted(j>begin(), j>end())); 1369 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 1370 if (clique.size() >= minimumSizeB) { 1371 if (B.count(clique) == 0) { 1372 Bi.insert(clique); 1373 } 1374 } 1375 clique.clear(); 1376 } 1377 } 1378 1379 IntersectionSets Bk; 1343 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(T)); 1344 if ((T.size() >= minimumSizeB) && (B.count(T) == 0)) { 1345 Bi.insert(T); 1346 } 1347 T.clear(); 1348 } 1349 } 1350 1351 IntersectionSets Bj; 1380 1352 for (;;) { 1381 1353 if (Bi.empty()) { … … 1385 1357 for (auto i = B1.begin(); i != B1.end(); ++i) { 1386 1358 assert (std::is_sorted(i>begin(), i>end())); 1387 for (auto j = Bi.begin() ; j != Bi.end(); ++j) {1359 for (auto j = Bi.begin(), end = Bi.end(); j != end; ++j) { 1388 1360 assert (std::is_sorted(j>begin(), j>end())); 1389 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 1390 if (clique.size() >= minimumSizeB) { 1391 if (B.count(clique) == 0) { 1392 Bk.insert(clique); 1393 } 1361 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(T)); 1362 if ((T.size() >= minimumSizeB) && (B.count(T) == 0)) { 1363 Bj.insert(T); 1394 1364 } 1395 clique.clear();1396 } 1397 } 1398 Bi.swap(B k);1399 B k.clear();1365 T.clear(); 1366 } 1367 } 1368 Bi.swap(Bj); 1369 Bj.clear(); 1400 1370 } 1401 1371 … … 1403 1373 1404 1374 Sequence Aj; 1405 Sequence Ak;1406 1375 for (auto && Bi : B) { 1407 1376 Sequence Ai(S); 1408 1377 assert (Bi.size() >= minimumSizeB); 1409 bool valid= true;1378 bool largeEnough = true; 1410 1379 for (const Vertex u : Bi) { 1411 1380 assert (std::is_sorted(Ai.begin(), Ai.end())); 1412 1381 assert (Ai.size() >= minimumSizeA); 1382 T.clear(); 1383 const auto m = out_degree(u, G); 1384 assert (m >= minimumSizeA); 1385 T.reserve(m); 1386 for (auto e : make_iterator_range(out_edges(u, G))) { 1387 T.push_back(target(e, G)); 1388 } 1389 std::sort(T.begin(), T.end()); 1390 assert(std::unique(T.begin(), T.end()) == T.end()); 1413 1391 Aj.clear(); 1414 Aj.reserve(out_degree(u, G)); 1415 AcceptIntoA acceptor(this, u); 1416 for (auto e : make_iterator_range(out_edges(u, G))) { 1417 const auto v = target(e, G); 1418 if (acceptor(v)) { 1419 Aj.push_back(v); 1420 } 1421 } 1392 Aj.reserve(std::min(Ai.size(), T.size())); 1393 std::set_intersection(Ai.begin(), Ai.end(), T.begin(), T.end(), std::back_inserter(Aj)); 1422 1394 if (Aj.size() < minimumSizeA) { 1423 valid= false;1395 largeEnough = false; 1424 1396 break; 1425 1397 } 1426 std::sort(Aj.begin(), Aj.end()); 1427 assert(std::unique(Aj.begin(), Aj.end()) == Aj.end()); 1428 if (LLVM_UNLIKELY(Aj.size() < minimumSizeA)) { 1429 valid = false; 1430 break; 1431 } 1432 Ak.clear(); 1433 Ak.reserve(std::min(Ai.size(), Aj.size())); 1434 std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak)); 1435 if (Ak.size() < minimumSizeA) { 1436 valid = false; 1437 break; 1438 } 1439 Ai.swap(Ak); 1440 } 1441 if (valid) { 1398 Ai.swap(Aj); 1399 } 1400 if (largeEnough) { 1442 1401 cliques.emplace_back(std::move(Ai), std::move(Bi)); 1443 1402 } … … 1503 1462 1504 1463 return std::move(S); 1505 }1506 1507 1508 /**  *1509 * @brief addDistributionVertex1510 **  */1511 DistributionVertex addDistributionVertex(const Vertex u) {1512 assert (u < num_vertices(G));1513 const auto f = Md.find(u);1514 if (f == Md.end()) {1515 #ifndef NDEBUG1516 for (auto v : make_iterator_range(vertices(Gd))) {1517 assert (Gd[v] != u);1518 }1519 #endif1520 const auto du = add_vertex(u, Gd);1521 assert (Gd[du] == u);1522 Md.emplace(u, du);1523 return du;1524 }1525 return f>second;1526 1464 } 1527 1465 … … 1608 1546 } 1609 1547 1610 #if ndef NDEBUG1548 #if !defined(NDEBUG)  defined(PRINT_DEBUG) 1611 1549 /**  * 1612 1550 * @brief hasValidOperandIndicies 1613 1551 **  */ 1614 bool hasValidOperandIndicies(const Vertex u ) {1552 bool hasValidOperandIndicies(const Vertex u, const bool report = true) { 1615 1553 if (isLive(u)) { 1616 1554 const auto n = in_degree(u, G); … … 1620 1558 return true; 1621 1559 } 1622 errs() << u << " cannot be nullary " << (int)typeId << "\n"; 1560 if (report) { 1561 errs() << u << " cannot be nullary " << (int)typeId << "\n"; 1562 } 1623 1563 return false; 1624 1564 } else if (isAssociative(typeId)) { … … 1631 1571 for (unsigned i = 1; i != n; ++i) { 1632 1572 if (LLVM_UNLIKELY(V[i  1] == V[i])) { 1633 errs() << u << " has duplicate operands " << V[i] << "\n"; 1573 if (report) { 1574 errs() << u << " has duplicate operands " << V[i] << "\n"; 1575 } 1634 1576 return false; 1635 1577 } … … 1640 1582 const auto i = G[e]; 1641 1583 if (LLVM_UNLIKELY(i >= n)) { 1642 errs() << u << " has operand index " << i << " exceeds in degree " << n << "\n"; 1584 if (report) { 1585 errs() << u << " has operand index " << i << " exceeds in degree " << n << "\n"; 1586 } 1643 1587 return false; 1644 1588 } else if (LLVM_UNLIKELY(used[i])) { 1645 errs() << u << " has duplicate operand indicies " << i << "\n"; 1589 if (report) { 1590 errs() << u << " has duplicate operand indicies " << i << "\n"; 1591 } 1646 1592 return false; 1647 1593 } … … 1649 1595 } 1650 1596 } else { 1651 errs() << u << " has " << n << " operands but requires " << requiredOperands(typeId) << "\n"; 1597 if (report) { 1598 errs() << u << " has " << n << " operands but requires " << requiredOperands(typeId) << "\n"; 1599 } 1652 1600 return false; 1653 1601 } … … 1656 1604 const auto v = source(e, G); 1657 1605 if (!isLive(v)) { 1658 errs() << u << " has dead operand " << v << "\n"; 1606 if (report) { 1607 errs() << u << " has dead operand " << v << "\n"; 1608 } 1659 1609 return false; 1660 1610 } … … 1687 1637 errs() << "removing " << u << "\n"; 1688 1638 #endif 1689 assert (!isImmutable(getType(u)));1690 1639 assert (isLive(u)); 1691 setDead(u); 1692 clear_out_edges(u, G); 1640 setDead(u); 1641 for (const auto e : make_iterator_range(in_edges(u, G))) { 1642 const auto v = source(e, G); 1643 if (LLVM_UNLIKELY(out_degree(v, G) == 1)) { 1644 removeVertex(v); 1645 } 1646 } 1647 clear_vertex(u, G); 1693 1648 } 1694 1649 … … 1702 1657 assert (u != v); 1703 1658 assert (isLive(v)); 1659 assert (isRegenerable(getType(u))  getValue(u)); 1660 if (PabloAST * expr = getValue(u)) { 1661 auto f = M.find(expr); 1662 assert (f>second == u); 1663 f>second = v; 1664 } 1704 1665 for (auto e : make_iterator_range(out_edges(u, G))) { 1705 1666 addEdge(v, target(e, G), G[e]); … … 1715 1676 const auto f = M.find(expr); 1716 1677 assert (f != M.end()); 1678 return f>second; 1679 } 1680 1681 /**  * 1682 * @brief addDistributionVertex 1683 **  */ 1684 DistributionVertex addDistributionVertex(const Vertex u) { 1685 assert (isLive(u)); 1686 const auto f = Md.find(u); 1687 if (f == Md.end()) { 1688 #ifndef NDEBUG 1689 for (auto v : make_iterator_range(vertices(Gd))) { 1690 assert ("duplicate vertex found that was not in Md!" && Gd[v] != u); 1691 } 1692 #endif 1693 const auto du = add_vertex(u, Gd); 1694 Md.emplace(u, du); 1695 return du; 1696 } 1717 1697 return f>second; 1718 1698 } … … 1763 1743 } 1764 1744 1745 bool isDead(const Vertex u) const { 1746 return getState(u) == State::Dead; 1747 } 1748 1765 1749 void setDead(const Vertex u) { 1766 1750 setState(u, State::Dead); … … 1776 1760 1777 1761 void setModified(const Vertex u) { 1778 assert( isAssociative(getType(u))  getType(u) == TypeId::Not);1762 assert(!isImmutable(getType(u))); 1779 1763 setState(u, State::Modified); 1780 1764 } … … 1842 1826 } 1843 1827 1828 static bool isStreamOperation(const TypeId typeId) { 1829 switch (typeId) { 1830 case TypeId::Advance: 1831 case TypeId::ScanThru: 1832 case TypeId::AdvanceThenScanThru: 1833 // case TypeId::ScanTo: 1834 // case TypeId::AdvanceThenScanTo: 1835 case TypeId::Lookahead: 1836 case TypeId::MatchStar: 1837 case TypeId::InFile: 1838 case TypeId::AtEOF: 1839 return true; 1840 default: 1841 return false; 1842 } 1843 } 1844 1844 1845 static TypeId oppositeTypeId(const TypeId typeId) { 1845 1846 assert (isDistributive(typeId)); … … 1860 1861 flat_map<const pablo::PabloAST *, Vertex> M; 1861 1862 1862 Sequence ordering;1863 1864 1863 DistributionGraph Gd; 1865 1864 flat_map<Vertex, DistributionVertex> Md; 1866 1865 1867 Sequence D; 1868 1869 std::default_random_engine R; 1870 1871 1866 Sequence ordering; 1867 Sequence distributable; 1872 1868 }; 1873 1869
Note: See TracChangeset
for help on using the changeset viewer.