Changeset 5570


Ignore:
Timestamp:
Jul 17, 2017, 2:23:40 PM (5 months ago)
Author:
nmedfort
Message:

Corrected DistributionPass? algorithm.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r5567 r5570  
    1717#include <pablo/pe_var.h>
    1818#include <pablo/pe_zeroes.h>
     19#include <pablo/builder.hpp>
    1920
    2021#include <pablo/optimizers/pablo_simplifier.hpp>
     
    3031#include <set>
    3132#include <unordered_set>
    32 #include <random>
    3333
    3434#ifndef NDEBUG
     
    4949
    5050using TypeId = pablo::PabloAST::ClassTypeId;
     51
    5152enum class State {
    5253    Dead
     
    9899     *  (DISTRIBUTIVITY)   (A ∧ B) √ (A ∧ C) ⇔ A ∧ (B √ C)   and   (A √ B) ∧ (A √ C) ⇔ A √ (B ∧ C)
    99100     *
     101     *  (DE MORGAN'S)      ¬(A ∧ B) ⇔ ¬A √ ¬B   and   Â¬(A √ B) ⇔ ¬A ∧ ¬B
     102     *
    100103     * Try to simplify the equations and eliminate some of the unnecessary statements
    101104     ** ------------------------------------------------------------------------------------------------------------- */
    102105    bool run(PabloKernel * const kernel) {
    103106        readAST(kernel->getEntryBlock());
    104         if (simplifyGraph()) {
     107        if (LLVM_LIKELY(simplifyGraph())) {
    105108            rewriteAST(kernel->getEntryBlock());
    106109            return true;
     
    109112    }
    110113
    111     PassContainer()
    112     : R(std::random_device()()) {
    113 
    114     }
    115 
    116114protected:
    117115
    118     #if !defined(NDEBUG) || defined(PRINT_DEBUG)
     116    #if defined(PRINT_DEBUG)
    119117    /** ------------------------------------------------------------------------------------------------------------- *
    120118     * @brief printGraph
     
    134132            std::queue<Vertex> Q;
    135133            for (const auto m : restricted) {
    136                 if (m < n) {
     134                if (m < n && isLive(m)) {
    137135                    show[m] = true;
    138136                    assert (Q.empty());
     
    153151                        }
    154152                    }
     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                    }
    155157                }
    156158            }
     
    169171                std::tie(expr, typeId, state, std::ignore) = G[u];
    170172
     173                bool space = true;
     174
    171175                switch (typeId) {
    172176                    case TypeId::And:
    173                         out << "(∧) ";
     177                        out << "(∧)";
    174178                        break;
    175179                    case TypeId::Or:
    176                         out << "(√) ";
     180                        out << "(√)";
    177181                        break;
    178182                    case TypeId::Xor:
    179                         out << "(⊕) ";
     183                        out << "(⊕)";
    180184                        break;
    181185                    case TypeId::Not:
    182                         out << "(¬) ";
     186                        out << "(¬)";
    183187                        break;
    184188                    case TypeId::Zeroes:
    185                         out << "(0) ";
     189                        out << "(⊥)";
    186190                        break;
    187191                    case TypeId::Ones:
    188                         out << "(1) ";
     192                        out << "(⊀)";
    189193                    default:
     194                        space = false;
    190195                        break;
    191196                }
    192 
    193197                if (expr) {
    194                     PabloPrinter::print(expr, out);
    195                 }
     198                    if (space) {
     199                        out << ' ';
     200                    }
     201                    expr->print(out);
     202                }
     203
    196204                const bool error = !hasValidOperandIndicies(u);
    197205
     
    261269            const auto typeId = getType(u);
    262270
    263             if (isRegenerable(typeId)) {
     271            if (isDead(u) || isRegenerable(typeId)) {
    264272                continue;
    265273            }
     
    271279            #endif
    272280
    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));
    280282            assert (stmt->getClassTypeId() == typeId);
     283            assert (hasValidOperandIndicies(u));
    281284            assert (in_degree(u, G) == stmt->getNumOperands());
    282285
     
    302305                entry->setInsertPoint(stmt->getPrevNode());
    303306
    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));
    319308            }
    320309
    321310            if (LLVM_UNLIKELY(typeId == TypeId::Assign)) {
    322                 setLastUsageTime(findVertex(stmt->getOperand(0)), count);
     311                setLastUsageTime(findVertex(stmt->getOperand(0)), ++count);
    323312            }
    324313            setLastUsageTime(u, ++count);
     
    341330
    342331        assert (isLive(u));
     332        const TypeId typeId = getType(u);
    343333        PabloAST * value = isModified(u) ? nullptr : getValue(u);
    344334        if (LLVM_LIKELY(!dominates(value, stmt))) {
    345335
    346             const auto n = in_degree(u, G);
    347             const TypeId typeId = getType(u);
     336            const auto n = in_degree(u, G);           
    348337
    349338            #ifdef PRINT_DEBUG
     
    367356                    input[i++] = source(e, G);
    368357                }
     358
    369359                std::sort(input, input + n, [this](const Vertex u, const Vertex v) {
    370360                    return getLastUsageTime(u) < getLastUsageTime(v);
    371361                });
     362
     363                PabloBuilder builder(entry);
    372364                value = getValue(input[0]);
    373365                for (unsigned i = 1; i < n; ++i) {
     
    375367                    switch (typeId) {
    376368                        case TypeId::And:
    377                             value = entry->createAnd(value, op);
     369                            value = builder.createAnd(value, op);
    378370                            break;
    379371                        case TypeId::Or:
    380                             value = entry->createOr(value, op);
     372                            value = builder.createOr(value, op);
    381373                            break;
    382374                        case TypeId::Xor:
    383                             value = entry->createXor(value, op);
     375                            value = builder.createXor(value, op);
    384376                            break;
    385377                        default:
     
    390382            } else if (n == 1) {
    391383                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))));
    395385            } else if (n > 1) {
    396386
     
    431421            setUnmodified(u);
    432422        }
    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        }
    434429        return value;
    435430    }
     
    441436     ** ------------------------------------------------------------------------------------------------------------- */
    442437    bool simplifyGraph() {
    443 
    444438        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 
     439repeat: getReverseTopologicalOrdering();
     440        compactGraph();
    481441        if (applyDistributivityLaw()) {
    482442            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();
    505447        return modified;
    506448    }
     
    541483
    542484    /** ------------------------------------------------------------------------------------------------------------- *
    543      * @brief applyAnnulmentAssociativeIdentityIdempotentLaws
    544      ** ------------------------------------------------------------------------------------------------------------- */
    545     bool applyAnnulmentAssociativeIdentityIdempotentLaws() {
     485     * @brief compactGraph
     486     ** ------------------------------------------------------------------------------------------------------------- */
     487    void compactGraph() {
    546488
    547489        auto IdentityHash = [this](const Vertex u) {
     
    605547        V.reserve(num_vertices(G));
    606548
    607         bool modified = false;
    608 
    609549        for (const auto u : boost::adaptors::reverse(ordering)) {
     550
    610551            assert (isLive(u));
    611             assert(hasValidOperandIndicies(u));
    612 
    613             auto typeId = getType(u);
    614 
     552
     553            const auto typeId = getType(u);
    615554            if (LLVM_UNLIKELY(isImmutable(typeId))) {
    616555                continue;
     
    620559            }
    621560
    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                }
    667567            } 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)) {
    687569                    continue;
    688                 } else {
    689                     // Take the transitive closure of these arcs, we may reveal the underlying equation
    690                     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_DEBUG
    702                             errs() << "transitive associative " << v << " >> " << u << "\n";
    703                             #endif
    704                         }
    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_DEBUG
    729                             errs() << "xor canonicalization (a) " << u << "\n";
    730                             #endif
    731                             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                     }
    745570                }
    746571            } 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)) {
    764573                    continue;
    765                 } else if (LLVM_UNLIKELY(isConstant(negatedTypeId))) {
    766                     setModified(u);
    767                     typeId = (negatedTypeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes;
    768                     #ifdef PRINT_DEBUG
    769                     errs() << "constant negation (" << (int)typeId << ") " << u << "\n";
    770                     #endif
    771                     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_DEBUG
    777                     errs() << "xor canonicalization (n) " << u << "\n";
    778                     #endif
    779                     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;
    788574                }
    789575            }
    790576
    791577            // check whether this vertex is a duplicate
    792             const auto f = V.insert(u);
     578            auto f = V.insert(u);
    793579            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)) {
    885595            #ifdef PRINT_DEBUG
    886             errs() << "complement (" << (int)complementTypeId << ") " << u << "\n";
     596            errs() << "nullary associative " << u << "\n";
    887597            #endif
    888598            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);
    890705            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
    905933
    906934    /** ------------------------------------------------------------------------------------------------------------- *
     
    922950        makeDistributionSubgraph();
    923951
     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
    924957        bool modified = false;
    925958
    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;
    10371025            }
    10381026        }
     
    10481036     ** ------------------------------------------------------------------------------------------------------------- */
    10491037    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)) {
    10531043                const auto outerTypeId = getType(u);
    10541044                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))) {
    10571051                        const auto v = source(ei, G);
    10581052                        assert (isLive(v));
    1059                         // can we distribute this vertex?
    10601053                        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?
    10621054                            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))) {
    10641056                                const auto w = target(ej, G);
    1065                                 if (isLive(w) && getType(w) != outerTypeId) {
     1057                                assert (isLive(w));
     1058                                if (getType(w) != outerTypeId) {
    10661059                                    safe = false;
    10671060                                    break;
     
    10691062                            }
    10701063                            if (safe) {
    1071                                 D.push_back(v);
     1064                                D[count++] = v;
    10721065                            }
    10731066                        }
    10741067                    }
    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) {
    10821074                                const auto dv = addDistributionVertex(v);
    10831075                                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);
    10881080                                }
    10891081                            }
    10901082                        }
    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());
    11251089    }
    11261090
     
    11291093     ** ------------------------------------------------------------------------------------------------------------- */
    11301094    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);
    11631114    }
    11641115
     
    11671118     ** ------------------------------------------------------------------------------------------------------------- */
    11681119    BicliqueSet obtainDistributableSources(const Sequence & S) {
    1169         return makeIndependent(enumerateBicliques<>(S, Gd, 2, 1), 0);
     1120        return makeIndependent(enumerateBicliques(S, Gd, 2, 1), 0);
    11701121    }
    11711122
     
    11961147                    }
    11971148                    #endif
    1198                     const auto m = in_degree(u, G);
    11991149                    for (const auto w : T) {
    12001150                        remove_edge(w, u, G);
    12011151                    }
    12021152                    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];
    12231176        }
    12241177    }
     
    12501203        for (unsigned i = 0; i < 3; ++i) {
    12511204
    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");
    12791236                        }
    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
    12871274                        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                            }
    12891280                        }
    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
    12941283                        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));
    12971288                        }
    12981289                    }
    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
     1295private:
    13151296
    13161297    /** ------------------------------------------------------------------------------------------------------------- *
     
    13181299     *
    13191300     * 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 A to be in
    1321      * 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).
    13221303     ** ------------------------------------------------------------------------------------------------------------- */
    13231304    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>
    13301305    BicliqueSet enumerateBicliques(const Sequence & S, const Graph & G, const unsigned minimumSizeA = 1, const unsigned minimumSizeB = 1) {
    13311306        using IntersectionSets = std::set<Sequence>;
     
    13351310        BicliqueSet cliques(0);
    13361311
    1337         if (S.size() >= minimumSizeA) {
     1312        if (LLVM_LIKELY(S.size() >= minimumSizeA)) {
    13381313
    13391314            IntersectionSets B1;
    13401315            for (auto u : S) {
    13411316                const auto n = in_degree(u, G);
    1342                 if (n > 0) {
     1317                if (n >= minimumSizeB) {
    13431318                    Sequence B;
    13441319                    B.reserve(n);
    1345                     AcceptIntoB acceptor(this, u);
    13461320                    for (auto e : make_iterator_range(in_edges(u, G))) {
    13471321                        const auto v = source(e, G);
    1348                         if (acceptor(v)) {
     1322                        if (out_degree(v, G) >= minimumSizeA) {
    13491323                            B.push_back(v);
    13501324                        }
     
    13621336            IntersectionSets Bi;
    13631337
    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) {
    13661340                assert (std::is_sorted(i->begin(), i->end()));
    1367                 for (auto j = i; ++j != B1.end(); ) {
     1341                for (auto j = i; ++j != end; ) {
    13681342                    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;
    13801352            for (;;) {
    13811353                if (Bi.empty()) {
     
    13851357                for (auto i = B1.begin(); i != B1.end(); ++i) {
    13861358                    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) {
    13881360                        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);
    13941364                        }
    1395                         clique.clear();
    1396                     }
    1397                 }
    1398                 Bi.swap(Bk);
    1399                 Bk.clear();
     1365                        T.clear();
     1366                    }
     1367                }
     1368                Bi.swap(Bj);
     1369                Bj.clear();
    14001370            }
    14011371
     
    14031373
    14041374            Sequence Aj;
    1405             Sequence Ak;
    14061375            for (auto && Bi : B) {
    14071376                Sequence Ai(S);
    14081377                assert (Bi.size() >= minimumSizeB);
    1409                 bool valid = true;
     1378                bool largeEnough = true;
    14101379                for (const Vertex u : Bi) {
    14111380                    assert (std::is_sorted(Ai.begin(), Ai.end()));
    14121381                    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());
    14131391                    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));
    14221394                    if (Aj.size() < minimumSizeA) {
    1423                         valid = false;
     1395                        largeEnough = false;
    14241396                        break;
    14251397                    }
    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) {
    14421401                    cliques.emplace_back(std::move(Ai), std::move(Bi));
    14431402                }
     
    15031462
    15041463        return std::move(S);
    1505     }
    1506 
    1507 
    1508     /** ------------------------------------------------------------------------------------------------------------- *
    1509      * @brief addDistributionVertex
    1510      ** ------------------------------------------------------------------------------------------------------------- */
    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 NDEBUG
    1516             for (auto v : make_iterator_range(vertices(Gd))) {
    1517                 assert (Gd[v] != u);
    1518             }
    1519             #endif
    1520             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;
    15261464    }
    15271465
     
    16081546    }
    16091547
    1610     #ifndef NDEBUG
     1548    #if !defined(NDEBUG) || defined(PRINT_DEBUG)
    16111549    /** ------------------------------------------------------------------------------------------------------------- *
    16121550     * @brief hasValidOperandIndicies
    16131551     ** ------------------------------------------------------------------------------------------------------------- */
    1614     bool hasValidOperandIndicies(const Vertex u) {
     1552    bool hasValidOperandIndicies(const Vertex u, const bool report = true) {
    16151553        if (isLive(u)) {
    16161554            const auto n = in_degree(u, G);
     
    16201558                    return true;
    16211559                }
    1622                 errs() << u << " cannot be nullary " << (int)typeId << "\n";
     1560                if (report) {
     1561                    errs() << u << " cannot be nullary " << (int)typeId << "\n";
     1562                }
    16231563                return false;
    16241564            } else if (isAssociative(typeId)) {
     
    16311571                for (unsigned i = 1; i != n; ++i) {
    16321572                    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                        }
    16341576                        return false;
    16351577                    }
     
    16401582                    const auto i = G[e];
    16411583                    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                        }
    16431587                        return false;
    16441588                    } 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                        }
    16461592                        return false;
    16471593                    }
     
    16491595                }
    16501596            } 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                }
    16521600                return false;
    16531601            }
     
    16561604            const auto v = source(e, G);
    16571605            if (!isLive(v)) {
    1658                 errs() << u << " has dead operand " << v << "\n";
     1606                if (report) {
     1607                    errs() << u << " has dead operand " << v << "\n";
     1608                }
    16591609                return false;
    16601610            }
     
    16871637        errs() << "removing " << u << "\n";
    16881638        #endif
    1689         assert (!isImmutable(getType(u)));
    16901639        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);
    16931648    }
    16941649
     
    17021657        assert (u != v);
    17031658        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        }
    17041665        for (auto e : make_iterator_range(out_edges(u, G))) {
    17051666            addEdge(v, target(e, G), G[e]);
     
    17151676        const auto f = M.find(expr);
    17161677        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        }
    17171697        return f->second;
    17181698    }
     
    17631743    }
    17641744
     1745    bool isDead(const Vertex u) const {
     1746        return getState(u) == State::Dead;
     1747    }
     1748
    17651749    void setDead(const Vertex u) {
    17661750        setState(u, State::Dead);
     
    17761760
    17771761    void setModified(const Vertex u) {
    1778         assert(isAssociative(getType(u)) || getType(u) == TypeId::Not);
     1762        assert(!isImmutable(getType(u)));
    17791763        setState(u, State::Modified);
    17801764    }
     
    18421826    }
    18431827
     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
    18441845    static TypeId oppositeTypeId(const TypeId typeId) {
    18451846        assert (isDistributive(typeId));
     
    18601861    flat_map<const pablo::PabloAST *, Vertex> M;
    18611862
    1862     Sequence ordering;
    1863 
    18641863    DistributionGraph Gd;
    18651864    flat_map<Vertex, DistributionVertex> Md;
    18661865
    1867     Sequence D;
    1868 
    1869     std::default_random_engine R;
    1870 
    1871 
     1866    Sequence ordering;
     1867    Sequence distributable;
    18721868};
    18731869
Note: See TracChangeset for help on using the changeset viewer.