Changeset 5566


Ignore:
Timestamp:
Jul 13, 2017, 4:01:12 PM (22 months ago)
Author:
nmedfort
Message:

Work on Pablo optimizations

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
2 edited

Legend:

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

    r5535 r5566  
    177177
    178178    /** ------------------------------------------------------------------------------------------------------------- *
    179      * @brief doCodeSinking
    180      ** ------------------------------------------------------------------------------------------------------------- */
    181     void doCodeSinking(PabloBlock * const block) {
    182         Statement * stmt = block->back(); // note: reverse AST traversal
    183         while (stmt) {
    184             Statement * const prevNode = stmt->getPrevNode();
    185             sinkIfAcceptableTarget(stmt, block);
    186             stmt = prevNode;
    187         }
    188     }
    189 
    190     /** ------------------------------------------------------------------------------------------------------------- *
    191179     * @brief hoistLoopInvariants
    192180     ** ------------------------------------------------------------------------------------------------------------- */
     
    230218     ** ------------------------------------------------------------------------------------------------------------- */
    231219    void doCodeMovement(PabloBlock * const block) {
    232         doCodeSinking(block);
    233         for (Statement * stmt : *block) {
    234             if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
    235                 doCodeMovement(cast<Branch>(stmt)->getBody());
    236                 if (isa<While>(stmt)) {
    237                     // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
    238                     // determine whether hoisting will helpful or harmful to the expected run time.
    239                     hoistLoopInvariants(cast<While>(stmt));
    240                 }
    241             }
    242         }
     220
     221        std::vector<Branch *> branches;
     222
     223        Statement * stmt = block->back(); // note: reverse AST traversal
     224        while (stmt) {
     225            Statement * const prevNode = stmt->getPrevNode();
     226            sinkIfAcceptableTarget(stmt, block);
     227            if (isa<Branch>(stmt)) {
     228                branches.push_back(cast<Branch>(stmt));
     229            }
     230            stmt = prevNode;
     231        }
     232
     233        while (!branches.empty()) {
     234            Branch * const br = branches.back();
     235            branches.pop_back();
     236            doCodeMovement(br->getBody());
     237            if (isa<While>(br)) {
     238                // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
     239                // determine whether hoisting will helpful or harmful to the expected run time.
     240                hoistLoopInvariants(br);
     241            }
     242
     243        }
     244
    243245    }
    244246
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r5510 r5566  
    33#include <pablo/pablo_kernel.h>
    44#include <pablo/codegenstate.h>
     5
     6#include <pablo/boolean.h>
    57#include <pablo/branch.h>
     8#include <pablo/pe_advance.h>
     9#include <pablo/pe_count.h>
     10#include <pablo/pe_infile.h>
     11#include <pablo/pe_integer.h>
     12#include <pablo/pe_lookahead.h>
     13#include <pablo/pe_matchstar.h>
     14#include <pablo/pe_ones.h>
     15#include <pablo/pe_scanthru.h>
    616#include <pablo/pe_string.h>
    7 #include <pablo/pe_integer.h>
     17#include <pablo/pe_var.h>
    818#include <pablo/pe_zeroes.h>
    9 #include <pablo/pe_ones.h>
    10 #include <pablo/boolean.h>
    11 #include <pablo/pe_var.h>
     19
     20#include <pablo/optimizers/pablo_simplifier.hpp>
     21
    1222#include <boost/container/flat_set.hpp>
    1323#include <boost/container/flat_map.hpp>
     
    1626#include <boost/graph/topological_sort.hpp>
    1727#include <boost/function_output_iterator.hpp>
     28#include <boost/functional/hash.hpp>
     29
    1830#include <set>
     31#include <random>
     32
     33#ifndef NDEBUG
     34#include <pablo/analysis/pabloverifier.hpp>
     35#endif
    1936
    2037#include <boost/graph/strong_components.hpp>
    2138#include <llvm/Support/raw_ostream.h>
     39#include <pablo/printer_pablos.h>
     40#include <llvm/Support/CommandLine.h>
     41
     42// #define PRINT_DEBUG
    2243
    2344using namespace boost;
     
    2546using namespace llvm;
    2647
     48namespace pablo {
     49
    2750using TypeId = pablo::PabloAST::ClassTypeId;
    28 using VertexData = std::pair<pablo::PabloAST *, TypeId>;
    29 
    30 using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, pablo::PabloAST *>;
     51enum class State {
     52    Dead
     53    , Live
     54    , Modified
     55};
     56
     57using UsageTime = size_t;
     58
     59using VertexData = std::tuple<pablo::PabloAST *, TypeId, State, UsageTime>;
     60
     61using OperandIndex = unsigned;
     62
     63using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, OperandIndex>;
    3164using Vertex = Graph::vertex_descriptor;
    3265using in_edge_iterator = graph_traits<Graph>::in_edge_iterator;
    3366using out_edge_iterator = graph_traits<Graph>::out_edge_iterator;
    3467
    35 using VertexSet = std::vector<Vertex>;
    36 using Biclique = std::pair<VertexSet, VertexSet>;
     68using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
     69using DistributionVertex = DistributionGraph::vertex_descriptor;
     70
     71using Sequence = std::vector<Vertex>;
     72using Biclique = std::pair<Sequence, Sequence>;
    3773using BicliqueSet = std::vector<Biclique>;
    38 using DistributionSet = std::tuple<VertexSet, VertexSet, VertexSet>;
     74using DistributionSet = std::tuple<Sequence, Sequence, Sequence>;
    3975using DistributionSets = std::vector<DistributionSet>;
    4076
    4177using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    4278
    43 namespace pablo {
    44 
    45 
    46 /** ------------------------------------------------------------------------------------------------------------- *
    47  * @brief printGraph
    48  ** ------------------------------------------------------------------------------------------------------------- */
    49 static void printGraph(const Graph & G, const std::string & name, llvm::raw_ostream & out) {
    50 
    51     std::vector<unsigned> c(num_vertices(G));
    52     strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
    53 
    54     out << "digraph " << name << " {\n";
    55     for (auto u : make_iterator_range(vertices(G))) {
    56         if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    57             continue;
    58         }
    59         out << "v" << u << " [label=\"" << u << ": ";
    60         TypeId typeId;
    61         PabloAST * expr;
    62         std::tie(expr, typeId) = G[u];
    63         bool temporary = false;
    64         bool error = false;
    65         if (expr == nullptr || (typeId != expr->getClassTypeId() && typeId != TypeId::Var)) {
    66             temporary = true;
    67             switch (typeId) {
    68                 case TypeId::And:
    69                     out << "And";
    70                     break;
    71                 case TypeId::Or:
    72                     out << "Or";
    73                     break;
    74                 case TypeId::Xor:
    75                     out << "Xor";
    76                     break;
    77                 case TypeId::Not:
    78                     out << "Not";
    79                     break;
    80                 default:
    81                     out << "???";
    82                     error = true;
    83                     break;
    84             }
    85             if (expr) {
    86                 out << " ("; expr->print(out); out << ")";
    87             }
    88         } else {
    89             expr->print(out);
    90         }
    91         out << "\"";
    92         if (typeId == TypeId::Var) {
    93             out << " style=dashed";
    94         }
    95         if (error) {
    96             out << " color=red";
    97         } else if (temporary) {
    98             out << " color=blue";
    99         }
    100         out << "];\n";
    101     }
    102     for (auto e : make_iterator_range(edges(G))) {
    103         const auto s = source(e, G);
    104         const auto t = target(e, G);
    105         out << "v" << s << " -> v" << t;
    106         bool cyclic = (c[s] == c[t]);
    107         if (G[e] || cyclic) {
    108             out << " [";
    109             PabloAST * const expr = G[e];
    110             if (expr) {
    111                 out << "label=\"";
    112                 expr->print(out);
    113                 out << "\" ";
    114              }
    115              if (cyclic) {
    116                 out << "color=red ";
    117              }
    118              out << "]";
    119         }
    120         out << ";\n";
    121     }
    122 
    123     if (num_vertices(G) > 0) {
    124 
    125         out << "{ rank=same;";
    126         for (auto u : make_iterator_range(vertices(G))) {
    127             if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    128                 out << " v" << u;
    129             }
    130         }
    131         out << "}\n";
    132 
    133         out << "{ rank=same;";
    134         for (auto u : make_iterator_range(vertices(G))) {
    135             if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    136                 out << " v" << u;
    137             }
    138         }
    139         out << "}\n";
    140 
    141     }
    142 
    143     out << "}\n\n";
    144     out.flush();
    145 }
    146 
    14779struct PassContainer {
    148 
    149     enum Modification {
    150         None, Trivial, Structural
    151     };
    15280
    15381    /** ------------------------------------------------------------------------------------------------------------- *
     
    17098     *  (DISTRIBUTIVITY)   (A ∧ B) √ (A ∧ C) ⇔ A ∧ (B √ C)   and   (A √ B) ∧ (A √ C) ⇔ A √ (B ∧ C)
    17199     *
    172      * Try to eliminate some of the unnecessary operations from the current Variadic expressions
    173      ** ------------------------------------------------------------------------------------------------------------- */
    174     void run(PabloKernel * const kernel) {
    175         run(kernel->getEntryBlock());
    176 
    177         printGraph(G, "G", errs());
    178         if (simplifyGraph() == Structural) {
    179             // rewriteAST(first, stmt);
    180             printGraph(G, "O", errs());
    181         }
    182 
    183     }
    184 
    185     void run(PabloBlock * const block) {
    186         for (Statement * stmt : *block) {           
     100     * Try to simplify the equations and eliminate some of the unnecessary statements
     101     ** ------------------------------------------------------------------------------------------------------------- */
     102    bool run(PabloKernel * const kernel) {
     103        readAST(kernel->getEntryBlock());
     104        if (simplifyGraph()) {
     105            rewriteAST(kernel->getEntryBlock());
     106            return true;
     107        }
     108        return false;
     109    }
     110
     111    PassContainer()
     112    : R(std::random_device()()) {
     113
     114    }
     115
     116protected:
     117
     118    #if !defined(NDEBUG) || defined(PRINT_DEBUG)
     119    /** ------------------------------------------------------------------------------------------------------------- *
     120     * @brief printGraph
     121     ** ------------------------------------------------------------------------------------------------------------- */
     122    void printGraph(const std::string & name, llvm::raw_ostream & out, std::vector<Vertex> restricted = {}) {
     123
     124        const auto n = num_vertices(G);
     125        std::vector<unsigned> c(n);
     126        const auto components = strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
     127
     128        std::vector<bool> show(n, false);
     129        if (LLVM_LIKELY(restricted.empty() && n == components)) {
     130            for (const auto u : make_iterator_range(vertices(G))) {
     131                show[u] = isLive(u);
     132            }
     133        } else {
     134            std::queue<Vertex> Q;
     135            for (const auto m : restricted) {
     136                if (m < n) {
     137                    show[m] = true;
     138                    assert (Q.empty());
     139                    Q.push(m);
     140                    for (;;) {
     141                        const auto u = Q.front();
     142                        Q.pop();
     143                        for (auto e : make_iterator_range(in_edges(u, G))) {
     144                            const auto v = source(e, G);
     145                            if (show[v] || !isLive(v)) {
     146                                continue;
     147                            }
     148                            show[v] = true;
     149                            Q.push(v);
     150                        }
     151                        if (Q.empty()) {
     152                            break;
     153                        }
     154                    }
     155                }
     156            }
     157        }
     158
     159        out << "digraph " << name << " {\n";
     160        for (auto u : make_iterator_range(vertices(G))) {
     161
     162            if (show[u]) {
     163
     164                out << "v" << u << " [label=\"" << u << ": ";
     165                TypeId typeId;
     166                PabloAST * expr;
     167                State state;
     168
     169                std::tie(expr, typeId, state, std::ignore) = G[u];
     170
     171                switch (typeId) {
     172                    case TypeId::And:
     173                        out << "(∧) ";
     174                        break;
     175                    case TypeId::Or:
     176                        out << "(√) ";
     177                        break;
     178                    case TypeId::Xor:
     179                        out << "(⊕) ";
     180                        break;
     181                    case TypeId::Not:
     182                        out << "(¬) ";
     183                        break;
     184                    case TypeId::Zeroes:
     185                        out << "(0) ";
     186                        break;
     187                    case TypeId::Ones:
     188                        out << "(1) ";
     189                    default:
     190                        break;
     191                }
     192
     193                if (expr) {
     194                    PabloPrinter::print(expr, out);
     195                }
     196                const bool error = !hasValidOperandIndicies(u);
     197
     198                out << "\"";
     199                if (state == State::Modified) {
     200                    out << " style=dashed";
     201                }
     202                if (error) {
     203                    out << " color=red";
     204                } else if (isRegenerable(typeId)) {                   
     205                    out << " color=blue";
     206                }
     207                out << "];\n";
     208            }
     209        }
     210        for (auto e : make_iterator_range(edges(G))) {
     211            const auto s = source(e, G);
     212            const auto t = target(e, G);
     213            if (show[s] && show[t]) {
     214                const auto cyclic = (c[s] == c[t]);
     215                const auto nonAssoc = !isAssociative(getType(t));
     216                out << "v" << s << " -> v" << t;
     217                if (cyclic || nonAssoc) {
     218                    out << " [";
     219                    if (nonAssoc) {
     220                        out << " label=\"" << G[e] << "\"";
     221                    }
     222                    if (cyclic) {
     223                        out << " color=red";
     224                    }
     225                    out << "]";
     226                }
     227                out << ";\n";
     228            }
     229        }
     230
     231        out << "}\n\n";
     232        out.flush();
     233    }
     234    #endif
     235
     236protected:
     237
     238    /** ------------------------------------------------------------------------------------------------------------- *
     239     * @brief readAST
     240     ** ------------------------------------------------------------------------------------------------------------- */
     241    void readAST(PabloBlock * const block) {
     242        for (Statement * stmt : *block) {
     243            addStatement(stmt);
     244            if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     245                readAST(cast<Branch>(stmt)->getBody());
     246            }
     247        }
     248    }
     249
     250    /** ------------------------------------------------------------------------------------------------------------- *
     251     * @brief rewriteAST
     252     *
     253     * The goal here is to rewrite the AST with the minimal amount of perturbation to the sequence of instructions
     254     * themselves. The exception is that associative instructions are regenerated w.r.t. their sequence in the AST
     255     ** ------------------------------------------------------------------------------------------------------------- */
     256    size_t rewriteAST(PabloBlock * entry, size_t count = 0) {
     257
     258        for (Statement * stmt : *entry) {
     259
     260            const Vertex u = findVertex(stmt);
     261            const auto typeId = getType(u);
     262
     263            if (isRegenerable(typeId)) {
     264                continue;
     265            }
     266
     267            #ifdef PRINT_DEBUG
     268            errs() << u << ") ";
     269            PabloPrinter::print(stmt, errs());
     270            errs() << "\n";
     271            #endif
     272
     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
     280            assert (stmt->getClassTypeId() == typeId);
     281            assert (in_degree(u, G) == stmt->getNumOperands());
     282
     283            in_edge_iterator ei_begin, ei_end;
     284            std::tie(ei_begin, ei_end) = in_edges(u, G);
     285            auto ei = ei_begin;
     286
     287            // For each associative operand, find the vertex that describes the operand in G
     288            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     289
     290                // Does the vertex have a value and, if so, does value dominate this statement?
     291                // If not, we need to regenerate it.
     292                for (bool first_cycle = true;;) {
     293                    if (ei == ei_end) {
     294                        assert (first_cycle);
     295                        ei = ei_begin;
     296                        first_cycle = false;
     297                    }
     298                    if (G[*ei] == i) {
     299                        break;
     300                    }
     301                    ++ei;
     302                }
     303
     304                entry->setInsertPoint(stmt->getPrevNode());
     305
     306                PabloAST * const replacement = regenerateIfNecessary(stmt, entry, source(*ei, G), count);
     307                PabloAST * const op = stmt->getOperand(i);
     308                if (LLVM_UNLIKELY(replacement == op)) {
     309                    continue;
     310                }
     311
     312                #ifdef PRINT_DEBUG
     313                errs() << " " << source(*ei, G) << ") replacing ";
     314                op->print(errs());
     315                errs() << " with ";
     316                replacement->print(errs());
     317                errs() << "\n";
     318                #endif
     319
     320                stmt->setOperand(i, replacement);
     321            }
     322
     323            if (LLVM_UNLIKELY(typeId == TypeId::Assign)) {
     324                setLastUsageTime(findVertex(stmt->getOperand(0)), count);
     325            }
     326            setLastUsageTime(u, ++count);
     327            setValue(u, stmt);
     328
    187329            if (isa<Branch>(stmt)) {
    188                 addBranch(stmt);
    189                 run(cast<Branch>(stmt)->getBody());
     330                count = rewriteAST(cast<Branch>(stmt)->getBody(), count);
     331            }
     332        }
     333
     334        return count;
     335    }
     336
     337    /** ------------------------------------------------------------------------------------------------------------- *
     338     * @brief regenerateIfNecessary
     339     *
     340     * Does vertex (u) have a value and, if so, does value dominate the statement? If not, regenerate it.
     341     ** ------------------------------------------------------------------------------------------------------------- */
     342    PabloAST * regenerateIfNecessary(Statement * const stmt, PabloBlock * const entry, const Vertex u, size_t & count) {
     343
     344        assert (isLive(u));
     345        PabloAST * value = isModified(u) ? nullptr : getValue(u);
     346        if (LLVM_LIKELY(!dominates(value, stmt))) {
     347
     348            const auto n = in_degree(u, G);
     349            const TypeId typeId = getType(u);
     350
     351            #ifdef PRINT_DEBUG
     352            errs() << "   making " << u << "  " << n << "  " << (int)typeId << "\n";
     353            #endif
     354
     355            for (auto e : make_iterator_range(in_edges(u, G))) {
     356                const auto v = source(e, G);
     357                regenerateIfNecessary(stmt, entry, v, count);
     358                assert (getValue(v));
     359                assert (dominates(getValue(v), stmt));
     360            }
     361
     362            if (LLVM_LIKELY(isAssociative(typeId))) {
     363
     364                assert (n >= 2);
     365
     366                Vertex input[n];
     367                unsigned i = 0;
     368                for (auto e : make_iterator_range(in_edges(u, G))) {
     369                    input[i++] = source(e, G);
     370                }
     371                std::sort(input, input + n, [this](const Vertex u, const Vertex v) {
     372                    return getLastUsageTime(u) < getLastUsageTime(v);
     373                });
     374                value = getValue(input[0]);
     375                for (unsigned i = 1; i < n; ++i) {
     376                    PabloAST * const op = getValue(input[i]);
     377                    switch (typeId) {
     378                        case TypeId::And:
     379                            value = entry->createAnd(value, op);
     380                            break;
     381                        case TypeId::Or:
     382                            value = entry->createOr(value, op);
     383                            break;
     384                        case TypeId::Xor:
     385                            value = entry->createXor(value, op);
     386                            break;
     387                        default:
     388                            llvm_unreachable("impossible!");
     389                    }
     390                }
     391
     392            } else if (n == 1) {
     393                assert (typeId == TypeId::Not);
     394                value = getValue(first_source(in_edges(u, G)));
     395                value = entry->createNot(value);
     396
     397            } else if (n > 1) {
     398
     399                PabloAST * op[n] = { nullptr };
     400                for (auto e : make_iterator_range(in_edges(u, G))) {
     401                    const auto i = G[e];
     402                    assert (i < n);
     403                    assert (op[i] == nullptr);
     404                    op[i] = getValue(source(e, G));
     405                    assert (op[i]);
     406                }
     407
     408                switch (typeId) {
     409                    case TypeId::Advance:
     410                        value = entry->createAdvance(op[0], op[1]);
     411                        break;
     412                    case TypeId::ScanThru:
     413                        value = entry->createScanThru(op[0], op[1]);
     414                        break;
     415                    case TypeId::MatchStar:
     416                        value = entry->createMatchStar(op[0], op[1]);
     417                        break;
     418
     419                    default:
     420                        llvm_unreachable("cannot regenerate this non-associtive statement!");
     421                }
     422
    190423            } else {
    191                 addStatement(stmt);
    192             }
    193         }
    194 
    195 //        G.clear();
    196 //        M.clear();
    197 //        for (Statement * stmt : *block) {
    198 //            addStatement(stmt);
    199 //        }
    200 
    201 //        printGraph(G, "G", errs());
    202 //        if (simplifyGraph() == Structural) {
    203 //            // rewriteAST(first, stmt);
    204 //            printGraph(G, "O", errs());
    205 //        }
    206 
    207     }
     424                assert (isConstant(typeId));
     425                if (typeId == TypeId::Zeroes) {
     426                    value = entry->createZeroes();
     427                } else {
     428                    value = entry->createOnes();
     429                }
     430            }
     431
     432            setValue(u, value);
     433            setUnmodified(u);
     434        }
     435        setLastUsageTime(u, ++count);
     436        return value;
     437    }
     438
     439protected:
    208440
    209441    /** ------------------------------------------------------------------------------------------------------------- *
    210442     * @brief simplifyGraph
    211443     ** ------------------------------------------------------------------------------------------------------------- */
    212     Modification simplifyGraph() {
    213         Modification modified = None;
    214         for (;;) {
    215             const auto p1 = applyAssociativeIdentityAnnulmentLaws();
    216             const auto p2 = applyAbsorbtionComplementIdempotentLaws();
    217             const auto p3 = applyDistributivityLaw();
    218             if (std::max(std::max(p1, p2), p3) != Structural) {
    219                 break;
    220             }
    221             modified = Structural;
    222         }
     444    bool simplifyGraph() {
     445
     446        bool modified = false;
     447
     448        #ifdef PRINT_DEBUG
     449        errs() << "********************************************\n";
     450        #endif
     451
     452restart:
     453
     454        #ifdef PRINT_DEBUG
     455        errs() << "============================================ (1)\n";
     456        #endif
     457
     458        getReverseTopologicalOrdering();
     459
     460        #ifdef PRINT_DEBUG
     461        errs() << "============================================ (2)\n";
     462        #endif
     463
     464        if (applyAnnulmentAssociativeIdentityIdempotentLaws()) {
     465            modified = true;
     466            goto restart;
     467        }
     468
     469        #ifdef PRINT_DEBUG
     470        errs() << "============================================ (3)\n";
     471        #endif
     472
     473
     474        if (applyAbsorbtionComplementLaws()) {
     475            modified = true;
     476            goto restart;
     477        }
     478
     479        #ifdef PRINT_DEBUG
     480        errs() << "============================================ (4)\n";
     481        #endif
     482
     483        if (applyDistributivityLaw()) {
     484            modified = true;
     485            goto restart;
     486        }
     487
     488        if (modified) {
     489
     490            #ifdef PRINT_DEBUG
     491            errs() << "============================================ (5)\n";
     492            #endif
     493
     494            transitiveReduction();
     495
     496            #ifdef PRINT_DEBUG
     497            errs() << "============================================ (6)\n";
     498            #endif
     499
     500            factorizeGraph();
     501
     502            #ifdef PRINT_DEBUG
     503            // printGraph("G", errs());
     504            #endif           
     505        }
     506
    223507        return modified;
    224508    }
    225509
    226 protected:
    227 
    228     /** ------------------------------------------------------------------------------------------------------------- *
    229      * @brief applyAssociativeIdentityAnnulmentLaws
    230      ** ------------------------------------------------------------------------------------------------------------- */
    231     Modification applyAssociativeIdentityAnnulmentLaws() {
    232 
    233         auto identityComparator = [this](const Vertex u, const Vertex v) -> bool {
    234             const auto typeA = getType(u);
    235             assert (typeA != TypeId::Var);
    236             const auto typeB = getType(v);
    237             assert (typeB != TypeId::Var);
    238             if (LLVM_LIKELY(typeA != typeB)) {
    239                 using value_of = std::underlying_type<TypeId>::type;
    240                 return static_cast<value_of>(typeA) < static_cast<value_of>(typeB);
    241             } else {
    242                 const auto degA = in_degree(u, G);
    243                 const auto degB = in_degree(v, G);
    244                 if (degA != degB) {
    245                     return degA < degB;
    246                 } else {
    247                     Vertex adjA[degA];
    248                     Vertex adjB[degA];
    249                     in_edge_iterator ei, ej;
    250                     std::tie(ei, std::ignore) = in_edges(u, G);
    251                     std::tie(ej, std::ignore) = in_edges(v, G);
    252                     for (size_t i = 0; i < degA; ++i, ++ei, ++ej) {
    253                         adjA[i] = source(*ei, G);
    254                         adjB[i] = source(*ej, G);
    255                     }
    256                     std::sort(adjA, adjA + degA);
    257                     std::sort(adjB, adjB + degA);
    258                     for (size_t i = 0; i < degA; ++i) {
    259                         if (adjA[i] < adjB[i]) {
    260                             return true;
    261                         }
    262                     }
    263                     return false;
    264                 }
    265             }
     510    /** ------------------------------------------------------------------------------------------------------------- *
     511     * @brief getReverseTopologicalOrdering
     512     ** ------------------------------------------------------------------------------------------------------------- */
     513    void getReverseTopologicalOrdering() {
     514
     515        struct PrePassInserter {
     516            PrePassInserter & operator=(const Vertex u) {
     517                if (LLVM_LIKELY(self.isLive(u))) {
     518                    assert(self.hasValidOperandIndicies(u));
     519                    if (LLVM_LIKELY(isImmutable(self.getType(u)) || out_degree(u, self.G) != 0)) {
     520                        self.ordering.push_back(u);
     521                    } else {
     522                        self.removeVertex(u);
     523                    }
     524                }
     525                return *this;
     526            }
     527
     528            PrePassInserter(PassContainer & pc) : self(pc) { }
     529            PrePassInserter & operator*() { return *this; }
     530            PrePassInserter & operator++() { return *this; }
     531            PrePassInserter & operator++(int) { return *this; }
     532
     533        public:
     534            PassContainer & self;
    266535        };
    267536
    268         flat_set<Vertex, decltype(identityComparator)> V(identityComparator);
     537
     538        ordering.clear();
     539        ordering.reserve(num_vertices(G));
     540        topological_sort(G, PrePassInserter(*this));
     541        assert (!ordering.empty());
     542    }
     543
     544    /** ------------------------------------------------------------------------------------------------------------- *
     545     * @brief applyAnnulmentAssociativeIdentityIdempotentLaws
     546     ** ------------------------------------------------------------------------------------------------------------- */
     547    bool applyAnnulmentAssociativeIdentityIdempotentLaws() {
     548
     549        auto IdentityHash = [this](const Vertex u) {
     550            using value_of = std::underlying_type<TypeId>::type;
     551            const auto n = in_degree(u, G);
     552            Vertex operands[n];
     553            unsigned i = 0;
     554            for (auto e : make_iterator_range(in_edges(u, G))) {
     555                operands[i++] = source(e, G);
     556            }
     557            std::sort(operands, operands + n);
     558            size_t h = 0;
     559            boost::hash_combine(h, static_cast<value_of>(getType(u)));
     560            for (unsigned j = 0; j < n; ++j) {
     561                boost::hash_combine(h, operands[j]);
     562            }
     563            return h;
     564        };
     565
     566        auto IdentityComparator = [this](const Vertex u, const Vertex v) {
     567            const auto typeId = getType(u);
     568            if (LLVM_LIKELY(typeId == getType(v))) {
     569                const unsigned n = in_degree(u, G);
     570                if (LLVM_UNLIKELY(n == 0)) {
     571                    assert (isConstant(typeId) && in_degree(v, G) == 0);
     572                    return true;
     573                }
     574                if (in_degree(v, G) == n) {
     575                    Vertex adjA[n];
     576                    Vertex adjB[n];
     577                    auto ei = std::get<0>(in_edges(u, G));
     578                    auto ej = std::get<0>(in_edges(v, G));
     579                    // if this is an associative op, order doesn't matter
     580                    if (isAssociative(typeId)) {
     581                        for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
     582                            adjA[i] = source(*ei, G);
     583                            adjB[i] = source(*ej, G);
     584                        }
     585                        std::sort(adjA, adjA + n);
     586                        std::sort(adjB, adjB + n);
     587                    } else { // otherwise consider the order indicated by the edges
     588                        for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
     589                            adjA[G[*ei]] = source(*ei, G);
     590                            adjB[G[*ej]] = source(*ej, G);
     591                        }
     592                    }
     593                    for (unsigned i = 0; i < n; ++i) {
     594                        if (adjA[i] != adjB[i]) {
     595                            return false;
     596                        }
     597                    }
     598                    return true;
     599                }
     600            }
     601            return false;
     602        };
     603
     604        using IdentitySet = std::unordered_set<Vertex, decltype(IdentityHash), decltype(IdentityComparator)>;
     605
     606        IdentitySet V{0, IdentityHash, IdentityComparator};
    269607        V.reserve(num_vertices(G));
    270608
    271         VertexSet ordering;
    272         ordering.reserve(num_vertices(G));
    273 
    274         topological_sort(G, std::back_inserter(ordering)); // note: ordering is in reverse topological order
    275 
    276         Modification modified = None;
     609        bool modified = false;
    277610
    278611        for (const auto u : boost::adaptors::reverse(ordering)) {
    279             const TypeId typeId = getType(u);
    280             if (isImmutable(typeId)) {
     612            assert (isLive(u));
     613            assert(hasValidOperandIndicies(u));
     614
     615            auto typeId = getType(u);
     616
     617            if (LLVM_UNLIKELY(isImmutable(typeId))) {
    281618                continue;
    282             } else if (LLVM_UNLIKELY(typeId == TypeId::Zeroes || typeId == TypeId::Ones)) {
    283                 for(;;) {
    284                     bool done = true;
    285                     for (auto e : make_iterator_range(out_edges(u, G))) {
    286                         const auto v = target(e, G);
    287                         const auto targetTypeId = getType(v);
    288                         if (LLVM_UNLIKELY(isAssociative(targetTypeId))) {
    289 
    290                             errs() << " -- identity relationship\n";
    291 
    292                             if (isIdentityRelation(typeId, targetTypeId)) {
    293                                 remove_edge(e, G);
    294                             } else {
    295                                 setType(v, typeId == TypeId::And ? TypeId::Zeroes : TypeId::Ones);
    296                                 clear_in_edges(v, G);
    297                             }
    298                             done = false;
    299                             modified = Structural;
    300                             break;
    301                         }
    302                     }
    303                     if (done) {
    304                         break;
    305                     }
    306                 }
     619            } else if (LLVM_UNLIKELY(out_degree(u, G) == 0)) {
     620                removeVertex(u);
     621                continue;
     622            }
     623
     624            if (LLVM_UNLIKELY(isConstant(typeId))) { identity_or_annulment_check:
     625
     626                assert (typeId == getType(u));
     627
     628                const auto n = out_degree(u, G);
     629                Vertex T[n];
     630                unsigned count = 0;
     631
     632                for (auto e : make_iterator_range(out_edges(u, G))) {
     633                    const auto v = target(e, G);
     634                    if (LLVM_UNLIKELY(isDistributive(getType(v)))) {
     635                        assert (count < n);
     636                        assert (u != v);
     637                        T[count++] = v;
     638                    }
     639                }
     640
     641                while (LLVM_UNLIKELY(count-- != 0)) {
     642
     643                    // typeId           targetTypeId     Optimization
     644                    // ------------     ------------     ------------
     645                    // Zeroes           Or               identity
     646                    // Zeroes           And              annulment (0)
     647                    // Ones             Or               annulment (1)
     648                    // Ones             And              identity
     649
     650                    assert (count < n);
     651                    const auto v = T[count];
     652                    setModified(v);
     653                    modified = true;
     654                    if (isIdentityRelation(typeId, getType(v))) {
     655                        #ifdef PRINT_DEBUG
     656                        errs() << "identity " << v << " >> " << u << "\n";
     657                        #endif
     658                        assert (edge(u, v, G).second);
     659                        remove_edge(u, v, G);
     660                    } else { // annulment
     661                        #ifdef PRINT_DEBUG
     662                        errs() << "annulment (" << (int)(typeId) << ") " << u << " >> " << v << "\n";
     663                        #endif
     664                        setType(v, typeId);
     665                        clear_in_edges(v, G);
     666                    }
     667                }
     668
    307669            } else if (isAssociative(typeId)) {
    308670                if (LLVM_UNLIKELY(in_degree(u, G) == 0)) {
     671                    #ifdef PRINT_DEBUG
     672                    errs() << "nullary associative " << u << "\n";
     673                    #endif
     674                    setModified(u);
     675                    typeId = TypeId::Zeroes;
    309676                    setType(u, TypeId::Zeroes);
     677                    modified = true;
     678                    goto identity_or_annulment_check;
     679                } else if (LLVM_UNLIKELY(in_degree(u, G) == 1)) {
     680                    // An associative operation with only one element is always equivalent to the element
     681                    const auto v = first_source(in_edges(u, G));
     682                    for (const auto e : make_iterator_range(out_edges(u, G))) {
     683                        addEdge(v, target(e, G), G[e]);
     684                    }                   
     685                    #ifdef PRINT_DEBUG
     686                    errs() << "unary associative " << v << " >> " << u << "\n";
     687                    #endif
     688                    removeVertex(u);
     689                    continue;
    310690                } else {
    311                     // An associative operation with only one element is always equivalent to the element
    312                     bool contractable = true;
    313                     if (LLVM_LIKELY(in_degree(u, G) > 1)) {
    314                         for (auto e : make_iterator_range(out_edges(u, G))) {
    315                             if (LLVM_LIKELY(typeId != getType(target(e, G)))) {
    316                                 contractable = false;
    317                                 break;
     691                    // Take the transitive closure of these arcs, we may reveal the underlying equation
     692                    Vertex removed[out_degree(u, G)];
     693                    unsigned n = 0;
     694                    for (auto ei : make_iterator_range(out_edges(u, G))) {
     695                        const auto v = target(ei, G);
     696                        if (typeId == getType(v)) {
     697                            assert(hasValidOperandIndicies(v));
     698                            for (auto ej : make_iterator_range(in_edges(u, G))) {
     699                                addEdge(source(ej, G), v, G[ei]);
    318700                            }
    319                         }
    320                     }
    321                     if (LLVM_UNLIKELY(contractable)) {
    322                         for (auto ei : make_iterator_range(in_edges(u, G))) {
    323                             for (auto ej : make_iterator_range(out_edges(u, G))) {
    324                                 addEdge(source(ei, G), target(ej, G), G[ei]);
     701                            setModified(v);
     702                            removed[n++] = v;
     703                            #ifdef PRINT_DEBUG
     704                            errs() << "transitive associative " << v << " >> " << u << "\n";
     705                            #endif
     706                        }
     707                    }
     708                    for (unsigned i = 0; i < n; ++i) {
     709                        const auto v = removed[i];
     710                        assert (edge(u, v, G).second);
     711                        remove_edge(u, v, G);
     712                        assert(hasValidOperandIndicies(v));
     713                    }
     714                    if (LLVM_UNLIKELY(out_degree(u, G) == 0)) {
     715                        removeVertex(u);
     716                        continue;
     717                    }                   
     718                    if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
     719                        // Canonicalize xor operations: (A ⊕ ¬B) = (A ⊕ B ⊕ 1)
     720                        Vertex negation[in_degree(u, G)];
     721                        unsigned count = 0;
     722                        for (const auto e : make_iterator_range(in_edges(u, G))) {
     723                            const auto v = source(e, G);
     724                            const auto typeId = getType(v);
     725                            if (LLVM_UNLIKELY(typeId == TypeId::Not)) {
     726                                negation[count++] = v;
    325727                            }
    326728                        }
    327                         removeVertex(u);
    328                         modified = std::max(modified, Trivial);
    329                         continue;
    330                     }
    331 
    332                     if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
    333                         // TODO:: (A ⊕ ¬B) = (A ⊕ (B ⊕ 1)) = ¬(A ⊕ B)
    334 
    335                     }
    336 
    337 
    338 
    339                 }
    340             }
    341 
    342             assert (getType(u) != TypeId::Var);
    343 
     729                        if (LLVM_UNLIKELY(count != 0)) {
     730                            #ifdef PRINT_DEBUG
     731                            errs() << "xor canonicalization (a) " << u << "\n";
     732                            #endif
     733                            for (unsigned i = 0; i < count; ++i) {
     734                                const auto v = negation[i];
     735                                assert (edge(v, u, G).second);
     736                                remove_edge(v, u, G);
     737                                addEdge(first_source(in_edges(v, G)), u);
     738                            }
     739                            if ((count & 1) != 0) {
     740                                addEdge(makeVertex(TypeId::Ones), u);
     741                            }
     742                            setModified(u);
     743                            assert(hasValidOperandIndicies(u));
     744                            modified = true;
     745                        }
     746                    }
     747                }
     748            } else if (typeId == TypeId::Not) {
     749                assert (in_degree(u, G) == 1);
     750                const auto v = first_source(in_edges(u, G));
     751                const auto negatedTypeId = getType(v);
     752                if (LLVM_UNLIKELY(negatedTypeId == TypeId::Not)) {
     753                    // handle double negation
     754                    assert (in_degree(v, G) == 1);
     755                    const auto w = first_source(in_edges(v, G));
     756                    for (const auto e : make_iterator_range(out_edges(u, G))) {
     757                        const auto v = target(e, G);
     758                        addEdge(w, v, G[e]);
     759                        setModified(v);
     760                    }
     761                    modified = true;
     762                    #ifdef PRINT_DEBUG
     763                    errs() << "double negation " << u << " -> " << w << "\n";
     764                    #endif
     765                    removeVertex(u);
     766                    continue;
     767                } else if (LLVM_UNLIKELY(isConstant(negatedTypeId))) {
     768                    setModified(u);
     769                    typeId = (negatedTypeId == TypeId::Zeroes) ? TypeId::Ones : TypeId::Zeroes;
     770                    #ifdef PRINT_DEBUG
     771                    errs() << "constant negation (" << (int)typeId << ") " << u << "\n";
     772                    #endif
     773                    setType(u, typeId);
     774                    modified = true;
     775                    goto identity_or_annulment_check;
     776                } else if (LLVM_UNLIKELY(negatedTypeId == TypeId::Xor)) {
     777                    // Canonicalize xor operations: ¬(A ⊕ B) = (A ⊕ B ⊕ 1)
     778                    #ifdef PRINT_DEBUG
     779                    errs() << "xor canonicalization (n) " << u << "\n";
     780                    #endif
     781                    setModified(u);
     782                    setType(u, TypeId::Xor);
     783                    clear_in_edges(u, G);
     784                    for (const auto e : make_iterator_range(in_edges(v, G))) {
     785                        add_edge(source(e, G), u, 0, G);
     786                    }
     787                    addEdge(makeVertex(TypeId::Ones), u);
     788                    assert(hasValidOperandIndicies(u));
     789                    modified = true;
     790                }
     791            }
     792
     793            // check whether this vertex is a duplicate
    344794            const auto f = V.insert(u);
    345795            if (LLVM_UNLIKELY(!f.second)) {
    346                 const auto v = *f.first;
    347 
    348                 errs() << " -- replacing " << u << " with " << v << "\n";
    349 
    350                 for (auto e : make_iterator_range(out_edges(u, G))) {
    351                     addEdge(v, target(e, G), G[e]);
    352                 }
    353                 removeVertex(u);
    354                 modified = Structural;
    355             }
    356         }
     796                remapVertex(u, *f.first);
     797            }
     798        }
     799
    357800        return modified;
    358801    }
    359802
    360     /** ------------------------------------------------------------------------------------------------------------- *
    361      * @brief applyAbsorbtionComplementIdempotentLaws
    362      ** ------------------------------------------------------------------------------------------------------------- */
    363     Modification applyAbsorbtionComplementIdempotentLaws() {
    364         Modification modified = None;
    365         for (const Vertex u : make_iterator_range(vertices(G))) {
     803    // A XOR NOT(A XOR B) = NOT B
     804
     805    // A AND NOT(A AND B) = A AND NOT B
     806
     807    // A AND NOT(A OR B) = 0
     808
     809    // A OR NOT(A AND B) = 1
     810
     811    // A OR NOT(A OR B) = A OR NOT B
     812
     813    // *  (ABSORBTION)       A √ (A ∧ B) ⇔ A ∧ (A √ B) ⇔ A
     814
     815    /** ------------------------------------------------------------------------------------------------------------- *
     816     * @brief applyAbsorbtionComplementLaws
     817     ** ------------------------------------------------------------------------------------------------------------- */
     818    bool applyAbsorbtionComplementLaws() {
     819        bool modified = false;
     820        for (const Vertex u : ordering) {
     821            assert (isLive(u));
     822            assert (hasValidOperandIndicies(u));
    366823            const TypeId typeId = getType(u);
    367824            if (isDistributive(typeId)) {
    368 restart_loop:   in_edge_iterator ei_begin, ei_end;
    369                 std::tie(ei_begin, ei_end) = in_edges(u, G);
    370                 for (auto ei = ei_begin; ei != ei_end; ++ei) {
    371                     const auto v = source(*ei, G);
     825                assert (in_degree(u, G) > 0);
     826                Vertex A[in_degree(u, G)];
     827                unsigned n = 0;
     828                for (const auto ei : make_iterator_range(in_edges(u, G))) {
     829                    const auto v = source(ei, G);
     830                    assert (isLive(v));
    372831                    const auto innerTypeId = getType(v);
    373                     if (isDistributive(innerTypeId) || innerTypeId == TypeId::Not) {
    374                         in_edge_iterator ek_begin, ek_end;
    375                         std::tie(ek_begin, ek_end) = in_edges(v, G);
    376                         for (auto ej = ei_begin; ej != ei_end; ++ej) {
    377                             for (auto ek = ek_begin; ek != ek_end; ++ek) {
    378                                 if (LLVM_UNLIKELY(source(*ej, G) == source(*ek, G))) {
    379                                     modified = Structural;
     832                    auto w = v;
     833                    if (innerTypeId == TypeId::Not) {
     834                        w = first_source(in_edges(v, G));
     835                        assert ("G is cyclic!" && (w != v));
     836                        assert (isLive(w));
     837                        for (const auto ej : make_iterator_range(in_edges(u, G))) {
     838                            if (LLVM_UNLIKELY(source(ej, G) == w)) {
     839                                goto do_complement;
     840                            }
     841                        }
     842                        if (LLVM_UNLIKELY(getType(w) == oppositeTypeId(typeId))) {
     843                            // Check for implicit De Morgan's + Complement law application, e.g., A ∧ ¬(A √ B) ⇔ 0
     844                            goto check_demorgans_complement;
     845                        }
     846                    } else if (innerTypeId == oppositeTypeId(typeId)) {
     847check_demorgans_complement:
     848                        for (const auto ej : make_iterator_range(in_edges(w, G))) {
     849                            for (const auto ek : make_iterator_range(in_edges(u, G))) {
     850                                if (LLVM_UNLIKELY(source(ej, G) == source(ek, G))) {
    380851                                    if (LLVM_UNLIKELY(innerTypeId == TypeId::Not)) {
    381                                         // complement
    382                                         setType(u, typeId == TypeId::And ? TypeId::Zeroes : TypeId::Ones);
    383                                         clear_in_edges(u, G);
    384                                         goto abort_loop;
     852                                        goto do_complement;
    385853                                    } else {
    386                                         if (LLVM_LIKELY(innerTypeId != typeId)) {
    387                                             // idempotent
    388                                             remove_edge(*ei, G);
    389                                         } else {
    390                                             // absorbtion
    391                                             remove_edge(*ej, G);
    392                                         }                                       
    393                                         // this seldom occurs so if it does, just restart the process rather than
    394                                         // trying to keep the iterators valid.
    395                                         goto restart_loop;
     854                                        A[n++] = v;
     855                                        goto next_variable;
    396856                                    }
    397857                                }
     
    399859                        }
    400860                    }
    401                 }
    402             }
    403             abort_loop:;
     861next_variable:
     862                    continue;
     863                }
     864                if (LLVM_UNLIKELY(n != 0)) {
     865                    setModified(u);
     866                    modified = true;
     867                    for (;;) {
     868                        const auto v = A[--n];
     869                        #ifdef PRINT_DEBUG
     870                        errs() << "absorbing " << v  << "," << u << "\n";
     871                        #endif
     872                        assert (edge(v, u, G).second);
     873                        remove_edge(v, u, G);assert (isLive(u));
     874                        if (LLVM_UNLIKELY(out_degree(v, G) == 0)) {
     875                            removeVertex(v);
     876                        }
     877                        if (LLVM_LIKELY(n == 0)) {
     878                            break;
     879                        }
     880                    }
     881                }
     882            }
     883            continue;
     884do_complement:
     885            // -----------------------------------------------------------------------------------
     886            const auto complementTypeId = (typeId == TypeId::And) ? TypeId::Zeroes : TypeId::Ones;
     887            #ifdef PRINT_DEBUG
     888            errs() << "complement (" << (int)complementTypeId << ") " << u << "\n";
     889            #endif
     890            setModified(u);
     891            setType(u, complementTypeId);
     892            clear_in_edges(u, G);
     893            modified = true;
    404894        }
    405895        return modified;
    406896    }
    407897
    408     /** ------------------------------------------------------------------------------------------------------------- *
    409      * @brief identifyDistributableVertices
     898    void print(raw_ostream & out, const Sequence & S) {
     899        if (S.empty()) {
     900            return;
     901        }
     902        out << Gd[S[0]];
     903        for (unsigned i = 1; i < S.size(); ++i) {
     904            out << ',' << Gd[S[i]];
     905        }
     906    }
     907
     908    /** ------------------------------------------------------------------------------------------------------------- *
     909     * @brief applyDistributivityLaw
    410910     *
    411      * Let (u) ∈ V(G) be a conjunction ∧ or disjunction √ and (v) be a ∧ or √ and the opposite type of (u). If (u,v) ∈
    412      * E(G) and all outgoing edges of (v) lead to a vertex of the same type, add (u), (v) and any vertex (w) in which
    413      * (w,v) ∈ E(G) to the distribution graph H as well as the edges indicating their relationships within G.
     911     * sources        (s)               inner       (√)   (√)
     912     *               /   \                            \   /
     913     * inner       (√)   (√)            x              (∧)
     914     *               \   /                              |
     915     * outer          (∧)               sources         |  (s)
     916     *                                                  | /
     917     *                                  y              (√)
     918     *                                                  |
     919     *                                  outer          (∧)
    414920     *
    415      *                  (?) (?) (?) <-- w1, w2, ...
    416      *                     \ | /
    417      *                      (v)   <-- v
    418      *                     /   \
    419      *            u --> (∧)     (∧)
    420      *
    421      ** ------------------------------------------------------------------------------------------------------------- */
    422     void identifyDistributableVertices() {
    423 
    424         assert (D.empty() && L.empty());
    425 
    426         for (const Vertex u : make_iterator_range(vertices(G))) {
    427             const TypeId outerTypeId = getType(u);
    428             if (isDistributive(outerTypeId)) {
    429                 bool beneficial = true;
    430                 const TypeId innerTypeId = oppositeTypeId(outerTypeId);
    431                 for (auto e : make_iterator_range(out_edges(u, G))) {
    432                     const Vertex v = target(e, G);
    433                     if (LLVM_UNLIKELY(getType(v) != innerTypeId)) {
    434                         beneficial = false;
    435                         break;
    436                     }
    437                 }
    438                 if (beneficial) {
    439                     for (auto e : make_iterator_range(out_edges(u, G))) {
    440                         const auto v = target(e, G);
    441                         const auto f = std::lower_bound(D.begin(), D.end(), v);
     921     ** ------------------------------------------------------------------------------------------------------------- */
     922    bool applyDistributivityLaw() {
     923
     924        makeDistributionSubgraph();
     925
     926        bool modified = false;
     927
     928        for (;;) {
     929
     930            assert (std::is_sorted(D.begin(), D.end()));
     931
     932            // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
     933            if (LLVM_UNLIKELY(D.empty())) {
     934                break;
     935            }
     936
     937            #ifdef PRINT_DEBUG
     938            if (modified) {
     939                errs() << "--------------------------------------------\n";
     940            }
     941            #endif
     942
     943            const auto lowerSet = obtainDistributableClauses(D);
     944
     945            for (const auto & lower : lowerSet) {
     946                const auto & outer = std::get<0>(lower);
     947                const auto upperSet = obtainDistributableSources(std::get<1>(lower));
     948                for (const auto & upper : upperSet) {
     949
     950                    const auto & sources = std::get<1>(upper);
     951                    const auto & inner = std::get<0>(upper);
     952
     953                    const auto outerTypeId = getType(Gd[outer[0]]);
     954                    const auto innerTypeId = oppositeTypeId(outerTypeId);
     955
     956                    // Update G to match the desired change
     957                    const auto x = makeVertex(outerTypeId);
     958                    const auto y = makeVertex(innerTypeId);
     959
     960                    #ifdef PRINT_DEBUG
     961                    errs() << "distributing {";
     962                    print(errs(), sources);
     963                    if (innerTypeId == TypeId::And) {
     964                        errs() << "} ∧ {";
     965                    } else {
     966                        errs() << "} √ {";
     967                    }
     968                    print(errs(), inner);
     969                    if (outerTypeId == TypeId::Or) {
     970                        errs() << "} √ {";
     971                    } else {
     972                        errs() << "} ∧ {";
     973                    }
     974                    print(errs(), outer);
     975                    errs() << "} -> " << x << ',' << y << '\n';
     976                    #endif
     977
     978                    for (const auto i : inner) {
     979                        const auto u = Gd[i];
     980                        assert (getType(u) == innerTypeId);
     981                        for (const Vertex j : outer) {
     982                            const auto v = Gd[j];
     983                            assert (getType(v) == outerTypeId);
     984                            assert (edge(u, v, G).second);
     985                            remove_edge(i, j, Gd);
     986                            remove_edge(u, v, G);
     987                        }
     988                        addEdge(u, x);
     989                    }
     990
     991                    for (const Vertex i : sources) {
     992                        const auto u = Gd[i];
     993                        for (const Vertex j : inner) {
     994                            const auto v = Gd[j];
     995                            assert (edge(u, v, G).second);
     996                            remove_edge(i, j, Gd);
     997                            remove_edge(u, v, G);
     998                        }
     999
     1000                        addEdge(u, y);
     1001                    }
     1002
     1003                    addEdge(x, y);
     1004
     1005                    for (const Vertex i : outer) {
     1006                        const auto u = Gd[i];
     1007                        setModified(u);
     1008                        addEdge(y, u);
     1009                    }
     1010
     1011                    modified = true;
     1012                }
     1013            }
     1014
     1015            for (;;) {
     1016                if (LLVM_UNLIKELY(D.size() == 1)) {
     1017                    D.clear();
     1018                    break;
     1019                }
     1020                std::uniform_int_distribution<> dist(0, D.size() - 1);
     1021                const auto p = D.begin() + dist(R);
     1022                const auto u = *p;
     1023                D.erase(p);
     1024                bool found = false;
     1025                for (auto e : make_iterator_range(in_edges(u, Gd))) {
     1026                    const auto v = source(e, G);
     1027                    if (canDistribute(v, 1)) {
     1028                        auto f = std::lower_bound(D.begin(), D.end(), v);
    4421029                        if (f == D.end() || *f != v) {
    4431030                            D.insert(f, v);
    444                             assert (std::is_sorted(D.begin(), D.end()));
    445                         }
    446                     }
     1031                            found = true;
     1032                        }
     1033                    }
     1034                }
     1035                clear_in_edges(u, Gd);
     1036                if (found) {
     1037                    break;
     1038                }
     1039            }
     1040        }
     1041
     1042        Gd.clear();
     1043        Md.clear();
     1044
     1045        return modified;
     1046    }
     1047
     1048    /** ------------------------------------------------------------------------------------------------------------- *
     1049     * @brief makeDistributionSubgraph
     1050     ** ------------------------------------------------------------------------------------------------------------- */
     1051    void makeDistributionSubgraph() {
     1052        assert (D.empty());
     1053        for (const auto u : make_iterator_range(vertices(G))) {
     1054            if (isLive(u)) {
     1055                const auto outerTypeId = getType(u);
     1056                if (isDistributive(outerTypeId)) {
     1057                    const auto innerTypeId = oppositeTypeId(outerTypeId);
     1058                    for (auto ei : make_iterator_range(in_edges(u, G))) {
     1059                        const auto v = source(ei, G);
     1060                        assert (isLive(v));
     1061                        // can we distribute this vertex?
     1062                        if (getType(v) == innerTypeId) {
     1063                            // is it safe to add v to the distribution graph? I.e., do we need to calculate its value anyway?
     1064                            bool safe = true;
     1065                            for (auto ej : make_iterator_range(out_edges(v, G))) {
     1066                                const auto w = target(ej, G);
     1067                                if (isLive(w) && getType(w) != outerTypeId) {
     1068                                    safe = false;
     1069                                    break;
     1070                                }
     1071                            }
     1072                            if (safe) {
     1073                                D.push_back(v);
     1074                            }
     1075                        }
     1076                    }
     1077                    if (D.size() > 1) {
     1078                        std::sort(D.begin(), D.end());
     1079                        D.erase(std::unique(D.begin(), D.end()), D.end());
     1080                        if (LLVM_LIKELY(D.size() > 1)) {
     1081                            const auto du = addDistributionVertex(u);
     1082                            for (const auto v : D) {
     1083                                assert (isLive(v) && getType(v) == innerTypeId);
     1084                                const auto dv = addDistributionVertex(v);
     1085                                add_edge(dv, du, Gd);
     1086                                for (auto ej : make_iterator_range(in_edges(v, G))) {
     1087                                    const auto x = source(ej, G);
     1088                                    assert (isLive(x));
     1089                                    add_edge(addDistributionVertex(x), dv, Gd);
     1090                                }
     1091                            }
     1092                        }
     1093                    }
     1094                    D.clear();
     1095                }
     1096            }
     1097        }
     1098
     1099        assert (D.empty());
     1100        for (auto u : make_iterator_range(vertices(Gd))) {
     1101            if (out_degree(u, Gd) == 0) {
     1102                assert (canDistribute(u));
     1103                D.push_back(u);
     1104            }
     1105        }
     1106    }
     1107
     1108    /** ------------------------------------------------------------------------------------------------------------- *
     1109     * @brief canDistribute
     1110     ** ------------------------------------------------------------------------------------------------------------- */
     1111    bool canDistribute(const DistributionVertex u, const unsigned outDegree = 0) const {
     1112        assert (u < num_vertices(Gd));
     1113        assert (isLive(Gd[u]));       
     1114        if (out_degree(u, Gd) == outDegree && in_degree(u, Gd) > 0) {
     1115            const auto typeId = oppositeTypeId(getType(Gd[u]));           
     1116            unsigned count = 0;
     1117            for (auto e : make_iterator_range(in_edges(u, Gd))) {
     1118                if (getType(Gd[source(e, Gd)]) == typeId) {
     1119                    if (count == 1) {
     1120                        return true;
     1121                    }
     1122                    ++count;
     1123                }
     1124            }           
     1125        }
     1126        return false;
     1127    }
     1128
     1129    /** ------------------------------------------------------------------------------------------------------------- *
     1130     * @brief obtainDistributableClauses
     1131     ** ------------------------------------------------------------------------------------------------------------- */
     1132    BicliqueSet obtainDistributableClauses(const Sequence & S) {
     1133
     1134        struct OppositeType {
     1135            bool operator()(const DistributionVertex u) {
     1136                return self.getType(self.Gd[u]) == typeId;
     1137            }
     1138            OppositeType(PassContainer * const pc, const DistributionVertex u)
     1139            : self(*pc)
     1140            , typeId(oppositeTypeId(self.getType(self.Gd[u]))) {
     1141
     1142            }
     1143        private:
     1144            PassContainer & self;
     1145            const TypeId typeId;
     1146        };
     1147
     1148        struct AllUsers {
     1149            bool operator()(const DistributionVertex u) {
     1150                return out_degree(self.Gd[u], self.G) == degree;
     1151            }
     1152            AllUsers(PassContainer * const pc, const DistributionVertex u)
     1153            : self(*pc)
     1154            , degree(out_degree(self.Gd[u], self.G)) {
     1155
     1156            }
     1157        private:
     1158            PassContainer & self;
     1159            const size_t    degree;
     1160        };
     1161
     1162        // return makeIndependent(enumerateBicliques<OppositeType, AllUsers>(S, Gd, 1, 2), 1);
     1163
     1164        return enumerateBicliques<OppositeType, AllUsers>(S, Gd, 1, 2);
     1165    }
     1166
     1167    /** ------------------------------------------------------------------------------------------------------------- *
     1168     * @brief obtainDistributableSources
     1169     ** ------------------------------------------------------------------------------------------------------------- */
     1170    BicliqueSet obtainDistributableSources(const Sequence & S) {
     1171        return makeIndependent(enumerateBicliques<>(S, Gd, 2, 1), 0);
     1172    }
     1173
     1174    /** ------------------------------------------------------------------------------------------------------------- *
     1175     * @brief transitiveReduction
     1176     ** ------------------------------------------------------------------------------------------------------------- */
     1177    void transitiveReduction() {
     1178        flat_set<Vertex> T;
     1179        for (const auto u : ordering) {
     1180            if (isLive(u)) {
     1181                const auto typeId = getType(u);
     1182                if (isAssociative(typeId)) {
     1183                    assert (in_degree(u, G) != 0);
     1184                    for (auto ei : make_iterator_range(in_edges(u, G))) {
     1185                        const auto v = source(ei, G);
     1186                        assert (isLive(v));
     1187                        if (getType(v) == typeId) {
     1188                            for (auto ej : make_iterator_range(in_edges(v, G))) {
     1189                                const auto w = source(ej, G);
     1190                                assert (isLive(w));
     1191                                T.insert(w);
     1192                            }
     1193                        }
     1194                    }
     1195                    #ifndef NDEBUG
    4471196                    for (auto e : make_iterator_range(in_edges(u, G))) {
    448                         const auto v = source(e, G);
    449                         const auto f = std::lower_bound(L.begin(), L.end(), v);
    450                         if (f == L.end() || *f != v) {
    451                             L.insert(f, v);
    452                             assert (std::is_sorted(L.begin(), L.end()));
    453                         }
    454                     }
    455                 }
    456             }
    457         }
    458 
    459         // D = D - L
    460 
    461         if (!L.empty()) {
    462             if (!D.empty()) {
    463                 auto di = D.begin(), li = L.begin(), li_end = L.end();
    464                 for (;;) {
    465                     if (*li < *di) {
    466                         if (++li == li_end) {
    467                             break;
    468                         }
    469                     } else {
    470                         if (*di < *li) {
    471                             ++di;
     1197                        assert (T.count(source(e, G)) == 0);
     1198                    }
     1199                    #endif
     1200                    const auto m = in_degree(u, G);
     1201                    for (const auto w : T) {
     1202                        remove_edge(w, u, G);
     1203                    }
     1204                    T.clear();
     1205                    const auto n = in_degree(u, G);
     1206                    assert (n != 0 && n <= m);
     1207                    if (LLVM_UNLIKELY(n == 1)) {
     1208                        // An associative operation with only one element is always equivalent to the element
     1209                        const auto v = first_source(in_edges(u, G));
     1210                        #ifdef PRINT_DEBUG
     1211                        errs() << "unary associative " << v << " >> " << u << " (tr)\n";
     1212                        #endif
     1213                        for (auto e : make_iterator_range(out_edges(u, G))) {
     1214                            addEdge(v, target(e, G), G[e]);                           
     1215                        }
     1216                        removeVertex(u);
     1217                    } else if (LLVM_UNLIKELY(m != n)) {
     1218                        #ifdef PRINT_DEBUG
     1219                        errs() << "transitive reduction " << u << "\n";
     1220                        #endif
     1221                        setModified(u);
     1222                    }
     1223                }
     1224            }
     1225        }
     1226    }
     1227
     1228    /** ------------------------------------------------------------------------------------------------------------- *
     1229     * @brief factorizeGraph
     1230     *
     1231     * Factorize the associative operations in the final graph
     1232     ** ------------------------------------------------------------------------------------------------------------- */
     1233    void factorizeGraph() {
     1234
     1235        Sequence groups[3];
     1236        for (const auto u : make_iterator_range(vertices(G))) {
     1237            if (isLive(u)) {
     1238                switch (getType(u)) {
     1239                    case TypeId::And:
     1240                        groups[0].push_back(u); break;
     1241                    case TypeId::Or:
     1242                        groups[1].push_back(u); break;
     1243                    case TypeId::Xor:
     1244                        groups[2].push_back(u); break;
     1245                    default: break;
     1246                }
     1247            }
     1248        }
     1249
     1250        const TypeId op[3] = { TypeId::And, TypeId::Or, TypeId::Xor };
     1251
     1252        for (unsigned i = 0; i < 3; ++i) {
     1253
     1254            for (;;) {
     1255
     1256                auto factors = makeIndependent(enumerateBicliques<>(groups[i], G, 2, 2), 1);
     1257                if (factors.empty()) {
     1258                    break;
     1259                }
     1260
     1261                bool noChanges = true;
     1262
     1263                for (auto & factor : factors) {
     1264                    auto & targets = std::get<0>(factor);
     1265                    assert (targets.size() > 1);
     1266                    auto & sources = std::get<1>(factor);
     1267                    assert (sources.size() > 1);
     1268
     1269                    // One of the targets may be our replacement vertex.
     1270                    // If so, its in degree will equal |sources|.
     1271                    Vertex x = 0;
     1272                    bool create = true;
     1273                    for (auto j = targets.begin(); j != targets.end(); ) {
     1274                        assert (hasValidOperandIndicies(*j));
     1275                        if (in_degree(*j, G) == sources.size()) {
     1276                            x = *j;
     1277                            j = targets.erase(j);
     1278                            create = false;
    4721279                        } else {
    473                             di = D.erase(di);
    474                         }
    475                         if (di == D.end()) {
    476                             break;
    477                         }
    478                     }
    479                 }
    480             }
    481             L.clear();
    482         }
    483     }
    484 
    485     /** ------------------------------------------------------------------------------------------------------------- *
    486      * @brief applyDistributivityLaw
    487      ** ------------------------------------------------------------------------------------------------------------- */
    488     Modification applyDistributivityLaw() {
    489 
    490         identifyDistributableVertices();
    491 
    492         // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
    493         if (D.empty()) {
    494             return None;
    495         }
    496 
    497         Modification modified = None;
    498 
    499         const auto lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(D)), 1);
    500 
    501         for (auto & lower : lowerSet) {
    502             const auto upperSet = independentCliqueSets<0>(enumerateBicliques(std::get<1>(lower)), 2);
    503             for (const auto & upper : upperSet) {
    504 
    505                 const auto & sources = std::get<1>(upper);
    506                 const auto & intermediary = std::get<0>(upper);
    507                 const auto & sinks = std::get<0>(lower);
    508 
    509 
    510 
    511                 const auto outerTypeId = getType(sinks.front());
    512                 const auto innerTypeId = oppositeTypeId(outerTypeId);
    513 
    514                 errs() << " -- distributing\n";
    515 
    516                 // Update G to match the desired change
    517                 const auto x = makeVertex(outerTypeId);
    518                 const auto y = makeVertex(innerTypeId);
    519 
    520                 for (const auto i : intermediary) {
    521                     assert (getType(i) == innerTypeId);
    522                     for (const Vertex t : sinks) {
    523                         assert (getType(t) == outerTypeId);
    524                         remove_edge(i, t, G);
    525                     }
    526                     addEdge(i, x);
    527                 }
    528 
    529                 for (const Vertex s : sources) {
    530                     for (const Vertex i : intermediary) {
    531                         remove_edge(s, i, G);
    532                     }
    533                     addEdge(s, y);
    534                 }
    535                 addEdge(x, y);
    536 
    537                 for (const Vertex t : sinks) {
    538                     addEdge(y, t, std::get<0>(G[t]));
    539                 }
    540 
    541                 modified = Structural;
    542             }
    543         }
    544 
    545         D.clear();
    546 
    547         return modified;
    548     }
    549 
     1280                            ++j;
     1281                        }
     1282                    }
     1283                    if (LLVM_UNLIKELY(targets.empty())) {
     1284                        continue;
     1285                    }
     1286                    if (create) {
     1287                        x = makeVertex(op[i]);
     1288                        groups[i].push_back(x);
     1289                        for (auto u : sources) {
     1290                            addEdge(u, x);
     1291                        }
     1292                    }
     1293
     1294                    // Clear out the biclique between the source and target vertices.
     1295                    for (auto u : sources) {
     1296                        for (auto v : targets) {
     1297                            assert (edge(u, v, G).second);
     1298                            boost::remove_edge(u, v, G);
     1299                        }
     1300                    }
     1301
     1302                    for (auto v : targets) {
     1303                        assert (getType(v) == op[i]);
     1304                        addEdge(x, v);
     1305                        setModified(v);
     1306                        assert(hasValidOperandIndicies(v));
     1307                    }
     1308
     1309                    noChanges = false;
     1310                }
     1311                if (LLVM_UNLIKELY(noChanges)) {
     1312                    break;
     1313                }
     1314            }
     1315        }
     1316    }
    5501317
    5511318    /** ------------------------------------------------------------------------------------------------------------- *
     
    5551322     * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
    5561323     * bipartition A and their adjacencies to be in B.
    557       ** ------------------------------------------------------------------------------------------------------------- */
    558 
    559     BicliqueSet enumerateBicliques(const VertexSet & A) {
    560         using IntersectionSets = std::set<VertexSet>;
    561 
    562         IntersectionSets B1;
    563         for (auto u : A) {
    564             if (in_degree(u, G) > 0) {
    565                 VertexSet incomingAdjacencies;
    566                 incomingAdjacencies.reserve(in_degree(u, G));
    567                 for (auto e : make_iterator_range(in_edges(u, G))) {
    568                     incomingAdjacencies.push_back(source(e, G));
    569                 }
    570                 std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
    571                 B1.insert(std::move(incomingAdjacencies));
    572             }
    573         }
    574 
    575         IntersectionSets B(B1);
    576 
    577         IntersectionSets Bi;
    578 
    579         VertexSet clique;
    580         for (auto i = B1.begin(); i != B1.end(); ++i) {
    581             for (auto j = i; ++j != B1.end(); ) {
    582                 std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    583                 if (clique.size() > 0) {
    584                     if (B.count(clique) == 0) {
    585                         Bi.insert(clique);
     1324     ** ------------------------------------------------------------------------------------------------------------- */
     1325    template <typename Graph>
     1326    struct AcceptAny {
     1327        bool operator()(const typename Graph::vertex_descriptor) { return true; }
     1328        AcceptAny(PassContainer * const, const typename Graph::vertex_descriptor) { }
     1329    };
     1330
     1331    template <typename AcceptIntoA = AcceptAny<Graph>, typename AcceptIntoB = AcceptAny<Graph>, typename Graph>
     1332    BicliqueSet enumerateBicliques(const Sequence & S, const Graph & G, const unsigned minimumSizeA = 1, const unsigned minimumSizeB = 1) {
     1333        using IntersectionSets = std::set<Sequence>;
     1334
     1335        assert (std::is_sorted(S.begin(), S.end()));
     1336
     1337        BicliqueSet cliques(0);
     1338
     1339        if (S.size() >= minimumSizeA) {
     1340
     1341            IntersectionSets B1;
     1342            for (auto u : S) {
     1343                const auto n = in_degree(u, G);
     1344                if (n > 0) {
     1345                    Sequence B;
     1346                    B.reserve(n);
     1347                    AcceptIntoB acceptor(this, u);
     1348                    for (auto e : make_iterator_range(in_edges(u, G))) {
     1349                        const auto v = source(e, G);
     1350                        if (acceptor(v)) {
     1351                            B.push_back(v);
     1352                        }
     1353                    }
     1354                    if (B.size() >= minimumSizeB) {
     1355                        std::sort(B.begin(), B.end());
     1356                        assert(std::unique(B.begin(), B.end()) == B.end());
     1357                        B1.insert(std::move(B));
     1358                    }
     1359                }
     1360            }
     1361
     1362            IntersectionSets B(B1);
     1363
     1364            IntersectionSets Bi;
     1365
     1366            Sequence clique;
     1367            for (auto i = B1.begin(); i != B1.end(); ++i) {
     1368                assert (std::is_sorted(i->begin(), i->end()));
     1369                for (auto j = i; ++j != B1.end(); ) {
     1370                    assert (std::is_sorted(j->begin(), j->end()));
     1371                    std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
     1372                    if (clique.size() >= minimumSizeB) {
     1373                        if (B.count(clique) == 0) {
     1374                            Bi.insert(clique);
     1375                        }
    5861376                    }
    5871377                    clique.clear();
    5881378                }
    5891379            }
    590         }
    591 
    592         for (;;) {
    593             if (Bi.empty()) {
    594                 break;
    595             }
    596             B.insert(Bi.begin(), Bi.end());
     1380
    5971381            IntersectionSets Bk;
    598             for (auto i = B1.begin(); i != B1.end(); ++i) {
    599                 for (auto j = Bi.begin(); j != Bi.end(); ++j) {
    600                     std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    601                     if (clique.size() > 0) {
    602                         if (B.count(clique) == 0) {
    603                             Bk.insert(clique);
     1382            for (;;) {
     1383                if (Bi.empty()) {
     1384                    break;
     1385                }
     1386                B.insert(Bi.begin(), Bi.end());
     1387                for (auto i = B1.begin(); i != B1.end(); ++i) {
     1388                    assert (std::is_sorted(i->begin(), i->end()));
     1389                    for (auto j = Bi.begin(); j != Bi.end(); ++j) {
     1390                        assert (std::is_sorted(j->begin(), j->end()));
     1391                        std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
     1392                        if (clique.size() >= minimumSizeB) {
     1393                            if (B.count(clique) == 0) {
     1394                                Bk.insert(clique);
     1395                            }
    6041396                        }
    6051397                        clique.clear();
    6061398                    }
    6071399                }
    608             }
    609             Bi.swap(Bk);
    610         }
    611 
    612         BicliqueSet cliques;
    613         cliques.reserve(B.size());
    614         for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
    615             VertexSet Ai(A);
    616             for (const Vertex u : *Bi) {
    617                 VertexSet Aj;
    618                 Aj.reserve(out_degree(u, G));
    619                 for (auto e : make_iterator_range(out_edges(u, G))) {
    620                     Aj.push_back(target(e, G));
    621                 }
    622                 std::sort(Aj.begin(), Aj.end());
    623                 VertexSet Ak;
    624                 Ak.reserve(std::min(Ai.size(), Aj.size()));
    625                 std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
    626                 Ai.swap(Ak);
    627             }
    628             assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
    629             cliques.emplace_back(std::move(Ai), std::move(*Bi));
    630         }
     1400                Bi.swap(Bk);
     1401                Bk.clear();
     1402            }
     1403
     1404            cliques.reserve(B.size());
     1405
     1406            Sequence Aj;
     1407            Sequence Ak;
     1408            for (auto && Bi : B) {
     1409                Sequence Ai(S);
     1410                assert (Bi.size() >= minimumSizeB);
     1411                bool valid = true;
     1412                for (const Vertex u : Bi) {
     1413                    assert (std::is_sorted(Ai.begin(), Ai.end()));
     1414                    assert (Ai.size() >= minimumSizeA);
     1415                    Aj.clear();
     1416                    Aj.reserve(out_degree(u, G));
     1417                    AcceptIntoA acceptor(this, u);
     1418                    for (auto e : make_iterator_range(out_edges(u, G))) {
     1419                        const auto v = target(e, G);
     1420                        if (acceptor(v)) {
     1421                            Aj.push_back(v);
     1422                        }
     1423                    }
     1424                    if (Aj.size() < minimumSizeA) {
     1425                        valid = false;
     1426                        break;
     1427                    }
     1428                    std::sort(Aj.begin(), Aj.end());
     1429                    assert(std::unique(Aj.begin(), Aj.end()) == Aj.end());
     1430                    if (LLVM_UNLIKELY(Aj.size() < minimumSizeA)) {
     1431                        valid = false;
     1432                        break;
     1433                    }
     1434                    Ak.clear();
     1435                    Ak.reserve(std::min(Ai.size(), Aj.size()));
     1436                    std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
     1437                    if (Ak.size() < minimumSizeA) {
     1438                        valid = false;
     1439                        break;
     1440                    }
     1441                    Ai.swap(Ak);
     1442                }
     1443                if (valid) {
     1444                    cliques.emplace_back(std::move(Ai), std::move(Bi));
     1445                }
     1446            }
     1447
     1448        }
     1449
    6311450        return cliques;
    6321451    }
    6331452
    634 
    635     /** ------------------------------------------------------------------------------------------------------------- *
    636      * @brief independentCliqueSets
    637      ** ------------------------------------------------------------------------------------------------------------- */
    638     template <unsigned side>
    639     BicliqueSet && independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) {
    640 
    641 
    642         const auto l = cliques.size();
     1453    /** ------------------------------------------------------------------------------------------------------------- *
     1454     * @brief makeIndependent
     1455     ** ------------------------------------------------------------------------------------------------------------- */
     1456    BicliqueSet && makeIndependent(BicliqueSet && S, const unsigned independentSide) {
     1457
     1458        const auto l = S.size();
    6431459        IndependentSetGraph I(l);
     1460
     1461        assert (independentSide < 2);
    6441462
    6451463        // Initialize our weights
    6461464        for (unsigned i = 0; i != l; ++i) {
    647             I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
     1465            I[i] = std::get<0>(S[i]).size() * std::get<1>(S[i]).size();
    6481466        }
    6491467
    6501468        // Determine our constraints
    6511469        for (unsigned i = 0; i != l; ++i) {
     1470            const auto & Si = (independentSide == 0) ? std::get<0>(S[i]) : std::get<1>(S[i]);
    6521471            for (unsigned j = i + 1; j != l; ++j) {
    653                 if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
     1472                const auto & Sj = (independentSide == 0) ? std::get<0>(S[j]) : std::get<1>(S[j]);
     1473                if (intersects(Si, Sj)) {
    6541474                    boost::add_edge(i, j, I);
    6551475                }
     
    6581478
    6591479        // Use the greedy algorithm to choose our independent set
    660         VertexSet selected;
     1480        Sequence selected;
    6611481        for (;;) {
    6621482            unsigned w = 0;
     
    6681488                }
    6691489            }
    670             if (w < minimum) break;
     1490            if (LLVM_UNLIKELY(w == 0)) break;
    6711491            selected.push_back(u);
    6721492            I[u] = 0;
     
    6781498        // Sort the selected list and then remove the unselected cliques
    6791499        std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
    680         auto end = cliques.end();
     1500        auto end = S.end();
    6811501        for (const unsigned offset : selected) {
    682             end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
    683         }
    684         cliques.erase(cliques.begin(), end);
    685 
    686         return std::move(cliques);
    687     }
    688 
    689     /** ------------------------------------------------------------------------------------------------------------- *
    690      * @brief removeUnhelpfulBicliques
    691      *
    692      * An intermediary vertex could have more than one outgoing edge but if any that are not directed to vertices in
    693      * the lower biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if
    694      * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
    695      ** ------------------------------------------------------------------------------------------------------------- */
    696     BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques) {
    697         for (auto ci = cliques.begin(); ci != cliques.end(); ) {
    698             const auto cardinalityA = std::get<0>(*ci).size();
    699             VertexSet & B = std::get<1>(*ci);
    700             for (auto bi = B.begin(); bi != B.end(); ) {
    701                 if (out_degree(*bi, G) == cardinalityA) {
    702                     ++bi;
    703                 } else {
    704                     bi = B.erase(bi);
    705                 }
    706             }
    707             if (B.size() > 1) {
    708                 ++ci;
    709             } else {
    710                 ci = cliques.erase(ci);
    711             }
    712         }
    713         return std::move(cliques);
     1502            end = S.erase(S.begin() + offset + 1, end) - 1;
     1503        }
     1504        S.erase(S.begin(), end);
     1505
     1506        return std::move(S);
     1507    }
     1508
     1509
     1510    /** ------------------------------------------------------------------------------------------------------------- *
     1511     * @brief addDistributionVertex
     1512     ** ------------------------------------------------------------------------------------------------------------- */
     1513    DistributionVertex addDistributionVertex(const Vertex u) {
     1514        assert (u < num_vertices(G));
     1515        const auto f = Md.find(u);
     1516        if (f == Md.end()) {
     1517            #ifndef NDEBUG
     1518            for (auto v : make_iterator_range(vertices(Gd))) {
     1519                assert (Gd[v] != u);
     1520            }
     1521            #endif
     1522            const auto du = add_vertex(u, Gd);
     1523            assert (Gd[du] == u);
     1524            Md.emplace(u, du);
     1525            return du;
     1526        }
     1527        return f->second;
    7141528    }
    7151529
     
    7181532     ** ------------------------------------------------------------------------------------------------------------- */
    7191533    Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) {
    720         return add_vertex(std::make_pair(expr, typeId), G);
     1534        return add_vertex(std::make_tuple(expr, typeId, expr ? State::Live : State::Modified, 0), G);
    7211535    }
    7221536
     
    7251539     ** ------------------------------------------------------------------------------------------------------------- */
    7261540    Vertex addExpression(PabloAST * const expr) {
     1541        assert (expr);
    7271542        const auto f = M.find(expr);
    7281543        if (LLVM_LIKELY(f != M.end())) {
    7291544            return f->second;
    7301545        }
    731         TypeId typeId = TypeId::Var;
    732         if (isa<Zeroes>(expr)) {
    733             typeId = TypeId::Zeroes;
    734         } else if (isa<Ones>(expr)) {
    735             typeId = TypeId::Ones;
    736         }
    737         const auto u = makeVertex(typeId, expr);
     1546        assert (isConstant(expr->getClassTypeId()) || isLiteral(expr->getClassTypeId()));
     1547        const auto u = makeVertex(expr->getClassTypeId(), expr);
    7381548        M.emplace(expr, u);
    739         if (LLVM_UNLIKELY(isa<Not>(expr))) {
    740             PabloAST * const negated = cast<Not>(expr)->getExpr();
    741             addEdge(addExpression(negated), u, negated);
    742         }
    7431549        return u;
    7441550    }
     
    7481554     ** ------------------------------------------------------------------------------------------------------------- */
    7491555    Vertex addStatement(Statement * const stmt) {
     1556        assert (stmt);
    7501557        assert (M.count(stmt) == 0);
    7511558        const auto typeId = stmt->getClassTypeId();
    7521559        if (LLVM_UNLIKELY(typeId == TypeId::Sel)) {
    753 
    754             // expand Sel (C,T,F) statements into (C ∧ T) √ (C ∧ F)
    755 
    7561560            const auto c = addExpression(cast<Sel>(stmt)->getCondition());
    7571561            const auto t = addExpression(cast<Sel>(stmt)->getTrueExpr());
    758             const auto l = makeVertex(TypeId::And);
    759             addEdge(c, l);
    760             addEdge(t, l);
     1562            const auto f = addExpression(cast<Sel>(stmt)->getFalseExpr());
     1563            const auto u = makeVertex(TypeId::And);
     1564            add_edge(c, u, 0, G);
     1565            add_edge(t, u, 1, G);
    7611566            const auto n = makeVertex(TypeId::Not);
    762             addEdge(c, n);
    763             const auto r = makeVertex(TypeId::And);
    764             const auto f = addExpression(cast<Sel>(stmt)->getFalseExpr());
    765             addEdge(n, r);
    766             addEdge(f, r);
    767             const auto u = makeVertex(TypeId::Or, stmt);
    768             M.emplace(stmt, u);
    769             addEdge(l, u);
    770             addEdge(r, u);
    771 
    772             return u;
    773 
     1567            add_edge(c, n, 0, G);
     1568            const auto v = makeVertex(TypeId::And);
     1569            add_edge(n, v, 0, G);
     1570            add_edge(f, v, 1, G);
     1571            const auto w = makeVertex(TypeId::Or);
     1572            add_edge(u, w, 0, G);
     1573            add_edge(v, w, 1, G);
     1574            M.emplace(stmt, w);
     1575            return w;
    7741576        } else {
    775 
    7761577            const auto u = makeVertex(typeId, stmt);
    777             M.emplace(stmt, u);
    7781578            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    7791579                PabloAST * const op = stmt->getOperand(i);
     
    7811581                    continue;
    7821582                }
    783                 addEdge(addExpression(op), u, op);
    784             }
    785 
     1583                add_edge(addExpression(op), u, i, G);
     1584            }
     1585            assert(hasValidOperandIndicies(u));
     1586            M.emplace(stmt, u);
    7861587            return u;
    7871588        }
    788 
    789     }
    790 
    791     /** ------------------------------------------------------------------------------------------------------------- *
    792      * @brief addBranch
    793      ** ------------------------------------------------------------------------------------------------------------- */
    794     void addBranch(Statement * const br) {
    795         const auto u = addStatement(br);
    796         for (auto escaped : cast<Branch>(br)->getEscaped()) {
    797             addEdge(u, addExpression(escaped), escaped);
    798         }
    799     }
    800 
     1589    }
    8011590
    8021591    /** ------------------------------------------------------------------------------------------------------------- *
    8031592     * @brief addEdge
    8041593     ** ------------------------------------------------------------------------------------------------------------- */
    805     void addEdge(const Vertex u, const Vertex v, PabloAST * const value = nullptr) {
     1594    bool addEdge(const Vertex u, const Vertex v, const OperandIndex index = 0) {
    8061595        const auto typeId = getType(v);
    8071596        if (isAssociative(typeId)) {
    808             for (auto e : make_iterator_range(in_edges(u, G))) {
    809                 if (LLVM_UNLIKELY(source(e, G) == u)) {
     1597            for (const auto e : make_iterator_range(out_edges(u, G))) {
     1598                if (LLVM_UNLIKELY(target(e, G) == v)) {
    8101599                    if (LLVM_LIKELY(isDistributive(typeId))) {
    811                         G[e] = std::max(G[e], value);
     1600                        G[e] = std::max(G[e], index);
    8121601                    } else {
    8131602                        remove_edge(e, G);
    8141603                    }
    815                     return;
    816                 }
    817             }
    818         }
    819         boost::add_edge(u, v, value, G);
    820     }
     1604                    return false;
     1605                }
     1606            }
     1607        }
     1608        boost::add_edge(u, v, index, G);
     1609        return true;
     1610    }
     1611
     1612    #ifndef NDEBUG
     1613    /** ------------------------------------------------------------------------------------------------------------- *
     1614     * @brief hasValidOperandIndicies
     1615     ** ------------------------------------------------------------------------------------------------------------- */
     1616    bool hasValidOperandIndicies(const Vertex u) {
     1617        if (isLive(u)) {
     1618            const auto n = in_degree(u, G);
     1619            const auto typeId = getType(u);
     1620            if (LLVM_UNLIKELY(n == 0)) {
     1621                if (LLVM_LIKELY(isAssociative(typeId) || isNullary(typeId))) {
     1622                    return true;
     1623                }
     1624                errs() << u << " cannot be nullary " << (int)typeId << "\n";
     1625                return false;
     1626            } else if (isAssociative(typeId)) {
     1627                Vertex V[n];
     1628                unsigned i = 0;
     1629                for (auto e : make_iterator_range(in_edges(u, G))) {
     1630                    V[i++] = source(e, G);
     1631                }
     1632                std::sort(V, V + n);
     1633                for (unsigned i = 1; i != n; ++i) {
     1634                    if (LLVM_UNLIKELY(V[i - 1] == V[i])) {
     1635                        errs() << u << " has duplicate operands " << V[i] << "\n";
     1636                        return false;
     1637                    }
     1638                }
     1639            } else if (requiredOperands(typeId) == n) {
     1640                bool used[n] = { false };
     1641                for (auto e : make_iterator_range(in_edges(u, G))) {
     1642                    const auto i = G[e];
     1643                    if (LLVM_UNLIKELY(i >= n)) {
     1644                        errs() << u << " has operand index " << i << " exceeds in degree " << n << "\n";
     1645                        return false;
     1646                    } else if (LLVM_UNLIKELY(used[i])) {
     1647                        errs() << u << " has duplicate operand indicies " << i << "\n";
     1648                        return false;
     1649                    }
     1650                    used[i] = true;
     1651                }
     1652            } else {
     1653                errs() << u << " has " << n << " operands but requires " << requiredOperands(typeId) << "\n";
     1654                return false;
     1655            }
     1656        }
     1657        for (auto e : make_iterator_range(in_edges(u, G))) {
     1658            const auto v = source(e, G);
     1659            if (!isLive(v)) {
     1660                errs() << u << " has dead operand " << v << "\n";
     1661                return false;
     1662            }
     1663        }
     1664        return true;
     1665    }
     1666
     1667    static unsigned requiredOperands(const TypeId typeId) {
     1668        switch (typeId) {
     1669            case TypeId::Not:
     1670            case TypeId::InFile:
     1671            case TypeId::AtEOF:
     1672            case TypeId::Count:
     1673            case TypeId::If:
     1674            case TypeId::While:
     1675                return 1;
     1676            case TypeId::Sel:
     1677                llvm_unreachable("impossible");
     1678            default:
     1679                return 2;
     1680        }
     1681    }
     1682    #endif
    8211683
    8221684    /** ------------------------------------------------------------------------------------------------------------- *
     
    8241686     ** ------------------------------------------------------------------------------------------------------------- */
    8251687    void removeVertex(const Vertex u) {
    826         clear_vertex(u, G);
    827         setType(u, TypeId::Var);
     1688        #ifdef PRINT_DEBUG
     1689        errs() << "removing " << u << "\n";
     1690        #endif
     1691        assert (!isImmutable(getType(u)));
     1692        assert (isLive(u));
     1693        setDead(u);       
     1694        clear_out_edges(u, G);
     1695    }
     1696
     1697    /** ------------------------------------------------------------------------------------------------------------- *
     1698     * @brief remapVertex
     1699     ** ------------------------------------------------------------------------------------------------------------- */
     1700    void remapVertex(const Vertex u, const Vertex v) {
     1701        #ifdef PRINT_DEBUG
     1702        errs() << "remapping " << u << " -> " << v << "\n";
     1703        #endif
     1704        assert (u != v);
     1705        assert (isLive(v));
     1706        for (auto e : make_iterator_range(out_edges(u, G))) {
     1707            addEdge(v, target(e, G), G[e]);
     1708        }
     1709        removeVertex(u);
     1710    }
     1711
     1712    /** ------------------------------------------------------------------------------------------------------------- *
     1713     * @brief findVertex
     1714     ** ------------------------------------------------------------------------------------------------------------- */
     1715    Vertex findVertex(const PabloAST * const expr) const {
     1716        assert (expr);
     1717        const auto f = M.find(expr);
     1718        assert (f != M.end());
     1719        return f->second;
    8281720    }
    8291721
     
    8341726    inline bool intersects(Type & A, Type & B) {
    8351727        auto first1 = A.begin(), last1 = A.end();
     1728        assert (std::is_sorted(first1, last1));
    8361729        auto first2 = B.begin(), last2 = B.end();
     1730        assert (std::is_sorted(first2, last2));
    8371731        while (first1 != last1 && first2 != last2) {
    8381732            if (*first1 < *first2) {
     
    8471741    }
    8481742
    849     TypeId getType(const Vertex u) {
     1743    TypeId getType(const Vertex u) const {
     1744        assert (u < num_vertices(G));
    8501745        return std::get<1>(G[u]);
    8511746    }
    8521747
    8531748    void setType(const Vertex u, const TypeId typeId) {
     1749        assert (u < num_vertices(G));
    8541750        std::get<1>(G[u]) = typeId;
    8551751    }
    8561752
     1753    PabloAST * getValue(const Vertex u) const {
     1754        assert (u < num_vertices(G));
     1755        return std::get<0>(G[u]);
     1756    }
     1757
     1758    void setValue(const Vertex u, PabloAST * const value) {
     1759        assert (u < num_vertices(G));
     1760        std::get<0>(G[u]) = value;
     1761    }
     1762
     1763    bool isLive(const Vertex u) const {
     1764        return getState(u) != State::Dead;
     1765    }
     1766
     1767    void setDead(const Vertex u) {
     1768        setState(u, State::Dead);
     1769    }
     1770
     1771    void setUnmodified(const Vertex u) {
     1772        setState(u, State::Live);
     1773    }
     1774
     1775    bool isModified(const Vertex u) const {
     1776        return getState(u) == State::Modified;
     1777    }
     1778
     1779    void setModified(const Vertex u) {
     1780        assert(isAssociative(getType(u)) || getType(u) == TypeId::Not);
     1781        setState(u, State::Modified);
     1782    }
     1783
     1784    State getState(const Vertex u) const {
     1785        assert (u < num_vertices(G));
     1786        return std::get<2>(G[u]);
     1787    }
     1788
     1789    void setState(const Vertex u, const State value) {
     1790        assert (u < num_vertices(G));
     1791        std::get<2>(G[u]) = value;
     1792    }
     1793
     1794    UsageTime getLastUsageTime(const Vertex u) const {
     1795        assert (u < num_vertices(G));
     1796        return std::get<3>(G[u]);
     1797    }
     1798
     1799    void setLastUsageTime(const Vertex u, const UsageTime time) {
     1800        assert (u < num_vertices(G));
     1801        std::get<3>(G[u]) = time;
     1802    }
     1803
    8571804    static bool isIdentityRelation(const TypeId a, const TypeId b) {
     1805        assert (isConstant(a) && isDistributive(b));
    8581806        return !((a == TypeId::Zeroes) ^ (b == TypeId::Or));
    8591807    }
     
    8631811    }
    8641812
     1813    static bool isRegenerable(const TypeId typeId) {
     1814        return (isConstant(typeId) || isAssociative(typeId) || typeId == TypeId::Not);
     1815    }
     1816
     1817    static bool isAssociative(const PabloAST * const expr) {
     1818        return isAssociative(expr->getClassTypeId());
     1819    }
     1820
     1821    static bool isConstant(const TypeId typeId) {
     1822        return typeId == TypeId::Zeroes || typeId == TypeId::Ones;
     1823    }
     1824
     1825    static bool isLiteral(const TypeId typeId) {
     1826        return typeId == TypeId::Integer || typeId == TypeId::Var;
     1827    }
     1828
    8651829    static bool isDistributive(const TypeId typeId) {
    8661830        return (typeId == TypeId::And || typeId == TypeId::Or);
     
    8681832
    8691833    static bool isImmutable(const TypeId typeId) {
    870         return (typeId == TypeId::Var || typeId == TypeId::Assign || typeId == TypeId::Extract);
     1834        switch (typeId) {
     1835            case TypeId::Extract: case TypeId::Assign: case TypeId::If: case TypeId::While:
     1836                return true;
     1837            default:
     1838                return isLiteral(typeId);
     1839        }
     1840    }
     1841
     1842    static bool isNullary(const TypeId typeId) {
     1843        return isConstant(typeId) || isLiteral(typeId);
    8711844    }
    8721845
     
    8761849    }
    8771850
     1851    Vertex first_source(const std::pair<in_edge_iterator, in_edge_iterator> & e) const {
     1852        return source(*std::get<0>(e), G);
     1853    }
     1854
     1855    bool inCurrentScope(const PabloAST * const expr, const PabloBlock * const scope) {
     1856        return isa<Statement>(expr) && cast<Statement>(expr)->getParent() == scope;
     1857    }
     1858
    8781859private:
    8791860
    8801861    Graph G;
    881     flat_map<pablo::PabloAST *, Vertex> M;
    882     VertexSet D;
    883     VertexSet L;
     1862    flat_map<const pablo::PabloAST *, Vertex> M;
     1863
     1864    Sequence ordering;
     1865
     1866    DistributionGraph Gd;
     1867    flat_map<Vertex, DistributionVertex> Md;
     1868
     1869    Sequence D;
     1870
     1871    std::default_random_engine R;
     1872
    8841873
    8851874};
     
    8891878 ** ------------------------------------------------------------------------------------------------------------- */
    8901879bool DistributivePass::optimize(PabloKernel * const kernel) {
    891     #ifdef NDEBUG
    892     report_fatal_error("DistributivePass is unsupported");
    893     #else
     1880
    8941881    PassContainer C;
    8951882    C.run(kernel);
     1883    #ifndef NDEBUG
     1884    PabloVerifier::verify(kernel, "post-distributive-pass");
     1885    #endif
     1886    Simplifier::optimize(kernel);
    8961887    return true;
    897     #endif
    8981888}
    8991889
Note: See TracChangeset for help on using the changeset viewer.