Changeset 5592


Ignore:
Timestamp:
Aug 3, 2017, 12:49:20 PM (3 months ago)
Author:
nmedfort
Message:

Modifications to DistributionPass?

File:
1 edited

Legend:

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

    r5571 r5592  
    2020
    2121#include <pablo/optimizers/pablo_simplifier.hpp>
     22#include <pablo/analysis/pabloverifier.hpp>
    2223
    2324#include <boost/container/flat_set.hpp>
     
    3233#include <unordered_set>
    3334
     35#include <boost/graph/strong_components.hpp>
     36#include <llvm/Support/raw_ostream.h>
     37#include <pablo/printer_pablos.h>
     38
    3439using namespace boost;
    3540using namespace boost::container;
    3641using namespace llvm;
    37 
    38 namespace pablo {
    39 
    40 using TypeId = pablo::PabloAST::ClassTypeId;
     42using namespace pablo;
     43
     44using TypeId = PabloAST::ClassTypeId;
    4145
    4246enum class State {
     
    4852using UsageTime = size_t;
    4953
    50 using VertexData = std::tuple<pablo::PabloAST *, TypeId, State, UsageTime>;
     54using VertexData = std::tuple<PabloAST *, TypeId, State, UsageTime>;
    5155
    5256using OperandIndex = unsigned;
    5357
    54 using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, OperandIndex>;
     58struct svecS{};
     59
     60namespace boost {
     61
     62    template<class T>
     63    struct __sorted_edge_vector : public std::vector<T> {
     64        using iterator = typename std::vector<T>::iterator;
     65        void push_back(const T & item) {
     66            std::vector<T>::insert(std::upper_bound(std::vector<T>::begin(), std::vector<T>::end(), item), item);
     67        }
     68    };
     69
     70    template <class ValueType> struct container_gen<svecS, ValueType> {
     71        typedef __sorted_edge_vector<ValueType> type;
     72    };
     73
     74    template <> struct parallel_edge_traits<svecS> {
     75        typedef allow_parallel_edge_tag type;
     76    };
     77
     78    template<class T> graph_detail::vector_tag container_category(const __sorted_edge_vector<T>&) {
     79        return graph_detail::vector_tag();
     80    }
     81
     82    template <class T> graph_detail::unstable_tag iterator_stability(const __sorted_edge_vector<T>&) {
     83        return graph_detail::unstable_tag();
     84    }
     85}
     86
     87namespace pablo {
     88
     89using Graph = adjacency_list<svecS, vecS, bidirectionalS, VertexData, OperandIndex, vecS>;
    5590using Vertex = Graph::vertex_descriptor;
    56 using in_edge_iterator = graph_traits<Graph>::in_edge_iterator;
    57 using out_edge_iterator = graph_traits<Graph>::out_edge_iterator;
    58 
    59 using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
     91using Edge = Graph::edge_descriptor;
     92using InEdgeIterator = graph_traits<Graph>::in_edge_iterator;
     93using DistributionGraph = adjacency_list<setS, vecS, bidirectionalS, Vertex>;
    6094using DistributionVertex = DistributionGraph::vertex_descriptor;
    6195
     
    66100using DistributionSets = std::vector<DistributionSet>;
    67101
    68 using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
     102using IndependentSetGraph = adjacency_list<vecS, vecS, undirectedS, size_t>;
    69103
    70104struct PassContainer {
     
    102136    }
    103137
     138    PassContainer()
     139    : reprocessGraph(false)
     140    , V{0, IdentityHash(G), IdentityComparator(G)} {
     141
     142    }
     143
    104144protected:
    105145
     
    122162     * themselves. The exception is that associative instructions are regenerated w.r.t. their sequence in the AST
    123163     ** ------------------------------------------------------------------------------------------------------------- */
    124     size_t rewriteAST(PabloBlock * entry, size_t count = 0) {
    125 
    126         for (Statement * stmt : *entry) {
     164    size_t rewriteAST(PabloBlock * const entry, size_t count = 0) {
     165
     166        Statement * stmt = entry->front();
     167
     168        while (stmt) {
    127169
    128170            const Vertex u = findVertex(stmt);
    129             const auto typeId = getType(u);
    130 
    131             // There are two main reasons to ignore a statement: (1) it's dead or regenerable and thus not of interest,
     171
     172            // There are two reasons to ignore a statement: (1) it's dead or regenerable and thus not of interest,
    132173            // and (2), the value in G strictly dominates the statement. Typically, if two expressions are equivalent,
    133             // they're in disjoint nested scopes. When neither dominates the other, this algorithm updates G as it
    134             // processes the statements. However, if one dominates the other, G must refer to the dominating statement
    135             // to avoid producing an illegal AST.
    136 
    137             if (LLVM_LIKELY(isDead(u) || isRegenerable(typeId)) || LLVM_UNLIKELY(strictly_dominates(getValue(u), stmt))) {
     174            // they're in disjoint nested scopes. When this occurs, they're merged into a single vertex in G to avoid
     175            // redundant computations but must still be written individually in the AST. Sometimes equivalent statements
     176            // are found during optimization. If one such statement dominates the other, G must refer to the dominating
     177            // statement to avoid producing an illegal AST.
     178
     179            if (LLVM_LIKELY(isDead(u) || isRegenerable(getType(u)))) {
     180                stmt = stmt->eraseFromParent(false);
    138181                continue;
     182            } else if (LLVM_UNLIKELY(isModified(u) && strictly_dominates(getValue(u), stmt))) {
     183                stmt = stmt->replaceWith(getValue(u));
     184                continue;
    139185            }
    140186
    141187            assert (isLive(u));
    142             assert (stmt->getClassTypeId() == typeId);
     188            assert (stmt->getClassTypeId() == getType(u));
    143189            assert (hasValidOperandIndicies(u));
    144190            assert (in_degree(u, G) == stmt->getNumOperands());
    145191
    146             in_edge_iterator ei_begin, ei_end;
    147             std::tie(ei_begin, ei_end) = in_edges(u, G);
    148             auto ei = ei_begin;
    149 
    150             // For each associative operand, find the vertex that describes the operand in G
    151             for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
    152 
    153                 // Does the vertex have a value and, if so, does value dominate this statement?
    154                 // If not, we need to regenerate it.
    155                 for (;;) {
    156                     if (ei == ei_end) {
    157                         ei = ei_begin;
    158                     }
    159                     if (G[*ei] == i) {
    160                         break;
    161                     }
    162                     ++ei;
    163                 }
    164 
    165                 entry->setInsertPoint(stmt->getPrevNode());
    166 
    167                 stmt->setOperand(i, regenerateIfNecessary(stmt, entry, source(*ei, G), count));
    168             }
    169 
    170             if (LLVM_UNLIKELY(typeId == TypeId::Assign)) {
    171                 setLastUsageTime(findVertex(stmt->getOperand(0)), ++count);
    172             }
     192            // Suppose we take a subgraph of G that contains every operand we'd have to regenerate to execute this
     193            // statement? We could apply local optimizations to the subgraph with respect to the last usage time of
     194            // each non-regenerated value and minimize the pairwise difference in last usage time, taking into account
     195            // that we can use negations of variables when they've been used more recently.
     196
     197            // This could take incorporate rematerialization by determining whether it is cheaper / possible to
     198            // recompute a value with what is already given but the Simplifer Pass could undo these changes if it
     199            // recognizes a duplicate value in scope.
     200
     201            entry->setInsertPoint(stmt->getPrevNode());
     202            for (const auto e : make_iterator_range(in_edges(u, G))) {
     203                stmt->setOperand(G[e], regenerateIfNecessary(stmt, entry, source(e, G), count));
     204            }
     205            setValue(u, stmt);
    173206            setLastUsageTime(u, ++count);
    174             setValue(u, stmt);
    175207
    176208            if (isa<Branch>(stmt)) {
    177209                count = rewriteAST(cast<Branch>(stmt)->getBody(), count);
    178210            }
     211
     212            stmt = stmt->getNextNode();
    179213        }
    180214
     
    187221     * Does vertex (u) have a value and, if so, does value dominate the statement? If not, regenerate it.
    188222     ** ------------------------------------------------------------------------------------------------------------- */
    189     PabloAST * regenerateIfNecessary(Statement * const stmt, PabloBlock * const entry, const Vertex u, size_t & count) {
    190 
     223    PabloAST * regenerateIfNecessary(Statement * const ip, PabloBlock * const entry, const Vertex u, size_t & count) {
    191224        assert (isLive(u));
    192 
    193         const TypeId typeId = getType(u);
    194 
    195         PabloAST * value = isModified(u) ? nullptr : getValue(u);
    196         if (LLVM_LIKELY(!dominates(value, stmt))) {
    197 
    198             assert (isRegenerable(typeId));
    199 
    200             for (auto e : make_iterator_range(in_edges(u, G))) {
    201                 const auto v = source(e, G);
    202                 regenerateIfNecessary(stmt, entry, v, count);
    203                 assert (getValue(v));
    204                 assert (dominates(getValue(v), stmt));
    205             }
    206 
    207             if (LLVM_LIKELY(isAssociative(typeId))) {
    208 
    209                 const auto n = in_degree(u, G);
    210 
    211                 assert (n >= 2);
     225        PabloAST * value = getValue(u);
     226        if (!dominates(value, ip)) {
     227
     228            assert (isRegenerable(getType(u)));
     229
     230            // if the outdegree of this vertex > 1, try setting the insertion point to a dominating position?
     231
     232            for (const auto e : make_iterator_range(in_edges(u, G))) {
     233                regenerateIfNecessary(ip, entry, source(e, G), count);
     234            }
     235
     236            const auto n = in_degree(u, G);
     237
     238            if (LLVM_UNLIKELY(n == 0)) {
     239                const TypeId typeId = getType(u);
     240                assert (isConstant(typeId));
     241                if (typeId == TypeId::Zeroes) {
     242                    value = entry->createZeroes();
     243                } else {
     244                    value = entry->createOnes();
     245                }
     246            } else if (LLVM_LIKELY(n != 1)) {
     247
     248                const TypeId typeId = getType(u);
     249
     250                assert (isAssociative(typeId));
    212251
    213252                // Suppose we try to minimize the pairwise difference in last usage time,
     
    220259                for (auto e : make_iterator_range(in_edges(u, G))) {
    221260                    input[i++] = source(e, G);
     261                    assert (getLastUsageTime(source(e, G)) > 0);
    222262                }
    223263
     
    226266                });
    227267
     268//                for (unsigned i = 0; i < n; ++i) {
     269//                    setLastUsageTime(input[i], ++count);
     270//                }
     271
    228272                PabloBuilder builder(entry);
    229273                value = getValue(input[0]);
    230274                for (unsigned i = 1; i < n; ++i) {
    231                     PabloAST * const op = getValue(input[i]);
     275                    PabloAST * const op = getValue(input[i]);                   
    232276                    switch (typeId) {
    233277                        case TypeId::And:
     
    244288                    }
    245289                }
    246 
    247             } else if (typeId == TypeId::Not) {
    248                 assert (in_degree(u, G) == 1);
    249                 value = entry->createNot(getValue(first_source(in_edges(u, G))));
    250290            } else {
    251                 assert (isConstant(typeId));
    252                 assert (in_degree(u, G) == 0);
    253                 if (typeId == TypeId::Zeroes) {
    254                     value = entry->createZeroes();
    255                 } else {
    256                     value = entry->createOnes();
    257                 }
    258             }
    259 
     291                value = entry->createNot(getValue(getNegatedLiteral(u)));
     292            }
     293            assert (value);
    260294            setValue(u, value);
    261295            setUnmodified(u);
    262         }
    263 
    264         // negations inherit the last usage time from their operand
    265         if (LLVM_UNLIKELY(typeId == TypeId::Not)) {
    266             setLastUsageTime(u, getLastUsageTime(first_source(in_edges(u, G))));
     296            setLastUsageTime(u, ++count);
     297        }       
     298        return value;
     299    }
     300
     301protected:
     302
     303    /** ------------------------------------------------------------------------------------------------------------- *
     304     * @brief printGraph
     305     ** ------------------------------------------------------------------------------------------------------------- */
     306    void printGraph(const std::string & name, llvm::raw_ostream & out, std::vector<Vertex> restricted = {}) {
     307
     308        const auto n = num_vertices(G);
     309        std::vector<unsigned> c(n);
     310        const auto components = strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
     311
     312        std::vector<bool> show(n, false);
     313        if (LLVM_LIKELY(restricted.empty() && n == components)) {
     314            for (const auto u : make_iterator_range(vertices(G))) {
     315                show[u] = isLive(u);
     316            }
    267317        } else {
    268             setLastUsageTime(u, ++count);
    269         }
    270         return value;
    271     }
    272 
    273 protected:
     318            std::queue<Vertex> Q;
     319            for (const auto m : restricted) {
     320                if (m < n && isLive(m)) {
     321                    show[m] = true;
     322                    assert (Q.empty());
     323                    Q.push(m);
     324                    for (;;) {
     325                        const auto u = Q.front();
     326                        Q.pop();
     327                        for (auto e : make_iterator_range(in_edges(u, G))) {
     328                            const auto v = source(e, G);
     329                            if (show[v] || !isLive(v)) {
     330                                continue;
     331                            }
     332                            show[v] = true;
     333                            Q.push(v);
     334                        }
     335                        if (Q.empty()) {
     336                            break;
     337                        }
     338                    }
     339                    for (auto e : make_iterator_range(out_edges(m, G))) {
     340                        const auto v = target(e, G);
     341                        show[v] = isLive(v) ? true : show[v];
     342                    }
     343                }
     344            }
     345        }
     346
     347        out << "digraph " << name << " {\n";
     348        for (auto u : make_iterator_range(vertices(G))) {
     349
     350            if (show[u]) {
     351
     352                out << "v" << u << " [label=\"" << u << ": ";
     353                TypeId typeId;
     354                PabloAST * expr;
     355                State state;
     356
     357                std::tie(expr, typeId, state, std::ignore) = G[u];
     358
     359                bool space = true;
     360
     361                switch (typeId) {
     362                    case TypeId::And:
     363                        out << "(∧)";
     364                        break;
     365                    case TypeId::Or:
     366                        out << "(√)";
     367                        break;
     368                    case TypeId::Xor:
     369                        out << "(⊕)";
     370                        break;
     371                    case TypeId::Not:
     372                        out << "(¬)";
     373                        break;
     374                    case TypeId::Zeroes:
     375                        out << "(⊥)";
     376                        break;
     377                    case TypeId::Ones:
     378                        out << "(⊀)";
     379                    default:
     380                        space = false;
     381                        break;
     382                }
     383                if (expr) {
     384                    if (space) {
     385                        out << ' ';
     386                    }
     387                    expr->print(out);
     388                }
     389
     390                out << "\"";
     391                if (!hasValidOperandIndicies(u)) {
     392                    out << " color=red style=bold";
     393                } else if (!(isImmutable(typeId) || out_degree(u, G) > 0)) {
     394                    out << " color=orange style=bold";
     395                } else if (isRegenerable(typeId)) {
     396                    out << " color=blue";
     397                    if (state == State::Modified) {
     398                        out << " style=dashed";
     399                    }
     400                }
     401                out << "];\n";
     402            }
     403        }
     404        for (auto e : make_iterator_range(edges(G))) {
     405            const auto s = source(e, G);
     406            const auto t = target(e, G);
     407            if (show[s] && show[t]) {
     408                const auto cyclic = (c[s] == c[t]);
     409                const auto nonAssoc = !isAssociative(getType(t));
     410                out << "v" << s << " -> v" << t;
     411                if (cyclic || nonAssoc) {
     412                    out << " [";
     413                    if (nonAssoc) {
     414                        out << " label=\"" << G[e] << "\"";
     415                    }
     416                    if (cyclic) {
     417                        out << " color=red";
     418                    }
     419                    out << "]";
     420                }
     421                out << ";\n";
     422            }
     423        }
     424
     425        out << "}\n\n";
     426        out.flush();
     427    }
    274428
    275429    /** ------------------------------------------------------------------------------------------------------------- *
     
    278432    bool simplifyGraph() {
    279433        bool modified = false;
    280 repeat: getReverseTopologicalOrdering();
    281         compactGraph();
    282         if (applyDistributivityLaw()) {
    283             modified = true;
    284             goto repeat;
    285         }
    286         factorizeGraph();
     434        errs() << "=================================================================\n";
     435        printGraph("S", errs());
     436        V.reserve(num_vertices(G));
     437        for (;;) {
     438            V.clear();
     439            getReverseTopologicalOrdering();
     440            if (compactGraph()) {
     441                continue;
     442            }
     443            if (applyDistributivityLaw()) {
     444                modified = true;
     445                continue;
     446            }
     447            break;
     448        }
     449        if (modified) {
     450            factorizeGraph();
     451            errs() << "-----------------------------------------------------------------\n";
     452            printGraph("F", errs());
     453        }
    287454        return modified;
    288455    }
     
    325492     * @brief compactGraph
    326493     ** ------------------------------------------------------------------------------------------------------------- */
    327     void compactGraph() {
    328 
    329         auto IdentityHash = [this](const Vertex u) {
    330             using value_of = std::underlying_type<TypeId>::type;
    331             const auto n = in_degree(u, G);
    332             Vertex operands[n];
    333             unsigned i = 0;
    334             for (auto e : make_iterator_range(in_edges(u, G))) {
    335                 operands[i++] = source(e, G);
    336             }
    337             std::sort(operands, operands + n);
    338             size_t h = 0;
    339             boost::hash_combine(h, static_cast<value_of>(getType(u)));
    340             for (unsigned j = 0; j < n; ++j) {
    341                 boost::hash_combine(h, operands[j]);
    342             }
    343             return h;
    344         };
    345 
    346         auto IdentityComparator = [this](const Vertex u, const Vertex v) {
    347             const auto typeId = getType(u);
    348             if (LLVM_LIKELY(typeId == getType(v))) {
    349                 const unsigned n = in_degree(u, G);
    350                 if (LLVM_UNLIKELY(n == 0)) {
    351                     assert (isConstant(typeId) && in_degree(v, G) == 0);
    352                     return true;
    353                 }
    354                 if (in_degree(v, G) == n) {
    355                     Vertex adjA[n];
    356                     Vertex adjB[n];
    357                     auto ei = std::get<0>(in_edges(u, G));
    358                     auto ej = std::get<0>(in_edges(v, G));
    359                     // if this is an associative op, order doesn't matter
    360                     if (isAssociative(typeId)) {
    361                         for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
    362                             adjA[i] = source(*ei, G);
    363                             adjB[i] = source(*ej, G);
    364                         }
    365                         std::sort(adjA, adjA + n);
    366                         std::sort(adjB, adjB + n);
    367                     } else { // otherwise consider the order indicated by the edges
    368                         for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
    369                             adjA[G[*ei]] = source(*ei, G);
    370                             adjB[G[*ej]] = source(*ej, G);
    371                         }
    372                     }
    373                     for (unsigned i = 0; i < n; ++i) {
    374                         if (adjA[i] != adjB[i]) {
    375                             return false;
    376                         }
    377                     }
    378                     return true;
    379                 }
    380             }
    381             return false;
    382         };
    383 
    384         using IdentitySet = std::unordered_set<Vertex, decltype(IdentityHash), decltype(IdentityComparator)>;
    385 
    386         IdentitySet V{0, IdentityHash, IdentityComparator};
    387         V.reserve(num_vertices(G));
    388 
     494    bool compactGraph() {
     495        reprocessGraph = false;
    389496        for (const auto u : boost::adaptors::reverse(ordering)) {
    390 
    391             assert (isLive(u));
    392 
    393             const auto typeId = getType(u);
    394             if (LLVM_UNLIKELY(isImmutable(typeId))) {
    395                 continue;
    396             }
    397 
    398             assert (hasValidOperandIndicies(u));
    399 
    400             assert (out_degree(u, G) > 0);
    401 
    402             if (LLVM_UNLIKELY(isConstant(typeId))) {
    403                 if (processConstant(u, typeId)) {
     497            if (LLVM_LIKELY(isLive(u))) {
     498                const auto typeId = getType(u);
     499                if (LLVM_UNLIKELY(isImmutable(typeId))) {
    404500                    continue;
    405501                }
    406             } else if (isAssociative(typeId)) {
    407                 if (processAssociative(u, typeId)) {
     502                assert (hasValidOperandIndicies(u));
     503                if (LLVM_UNLIKELY(out_degree(u, G) == 0)) {
     504                    removeVertex(u);
    408505                    continue;
    409506                }
    410             } else if (typeId == TypeId::Not) {
    411                 if (processNegation(u, typeId)) {
    412                     continue;
    413                 }
    414             }
    415 
    416             // check whether this vertex is a duplicate
    417             auto f = V.insert(u);
    418             if (LLVM_UNLIKELY(!f.second)) {
    419                 remapVertex(u, *f.first);             
    420             }
    421         }
     507                if (LLVM_UNLIKELY(isConstant(typeId))) {
     508                    if (processConstant(u, typeId)) {
     509                        continue;
     510                    }
     511                } else if (isAssociative(typeId)) {
     512                    if (processAssociative(u, typeId)) {
     513                        continue;
     514                    }
     515                } else if (typeId == TypeId::Not) {
     516                    if (processNegation(u)) {
     517                        continue;
     518                    }
     519                }
     520                consolidate(u);
     521            }
     522        }
     523        return reprocessGraph;
    422524    }
    423525
     
    439541            const auto v = first_source(in_edges(u, G));
    440542            for (const auto e : make_iterator_range(out_edges(u, G))) {
    441                 addEdge(v, target(e, G), G[e]);
     543                addEdge(v, target(e, G), G[e]);               
    442544            }
    443545            removeVertex(u);
     
    445547        } else {
    446548            // Take the transitive closure of these arcs to reveal the underlying equations
    447             Vertex removed[out_degree(u, G)];
    448             unsigned n = 0;
    449             for (auto ei : make_iterator_range(out_edges(u, G))) {
    450                 const auto v = target(ei, G);
    451                 if (typeId == getType(v)) {
    452                     assert(hasValidOperandIndicies(v));
    453                     for (auto ej : make_iterator_range(in_edges(u, G))) {
    454                         addEdge(source(ej, G), v, G[ei]);
    455                     }
    456                     setModified(v);
    457                     removed[n++] = v;
    458                 }
    459             }
     549            if (transitiveClosure(u, typeId)) {
     550                return true;
     551            }
     552            if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
     553                canonicalizeXor(u);
     554            } else { // is distributive
     555                applyDeMorganExpansion(u, typeId);
     556                if (LLVM_UNLIKELY(applyAbsorbtionComplementLaw(u, typeId))) {
     557                    return true;
     558                }
     559            }
     560        }
     561        return false;
     562    }
     563
     564    /** ------------------------------------------------------------------------------------------------------------- *
     565     * @brief transitiveClosure
     566     ** ------------------------------------------------------------------------------------------------------------- */
     567    bool transitiveClosure(const Vertex u, const TypeId typeId) {
     568        // Take the transitive closure of these arcs to reveal the underlying equations
     569
     570        assert (isLive(u));
     571        assert (getType(u) == typeId);
     572        assert (isAssociative(typeId));
     573
     574        Vertex removed[out_degree(u, G)];
     575        unsigned n = 0;
     576        for (auto ei : make_iterator_range(out_edges(u, G))) {
     577            const auto v = target(ei, G);
     578            if (getType(v) == typeId) {
     579                assert(hasValidOperandIndicies(v));
     580                for (auto ej : make_iterator_range(in_edges(u, G))) {
     581                    addEdge(source(ej, G), v);
     582                }
     583                setModified(v);
     584                removed[n++] = v;
     585            }
     586        }
     587        for (unsigned i = 0; i < n; ++i) {
     588            const auto v = removed[i];
     589            assert (edge(u, v, G).second);
     590            remove_edge(u, v, G);
     591            assert(hasValidOperandIndicies(v));
     592        }
     593        if (out_degree(u, G) == 0) {
     594            removeVertex(u);
     595            return true;
     596        }
     597        return false;
     598    }
     599
     600    /** ------------------------------------------------------------------------------------------------------------- *
     601     * @brief canonicalizeXor
     602     *
     603     * (A ⊕ ¬B) = (A ⊕ B ⊕ 1) = ¬(A ⊕ B)
     604     ** ------------------------------------------------------------------------------------------------------------- */
     605    void canonicalizeXor(const Vertex u) {
     606
     607        assert (isLive(u));
     608        assert (getType(u) == TypeId::Xor);
     609
     610        const auto l = in_degree(u, G);
     611        Vertex negation[l];
     612        unsigned n = 0, m = 0;
     613        for (const auto e : make_iterator_range(in_edges(u, G))) {
     614            const auto v = source(e, G);
     615            const auto typeId = getType(v);
     616            if (LLVM_UNLIKELY(typeId == TypeId::Not)) {
     617                negation[n++] = v;
     618            } else if (LLVM_UNLIKELY(typeId == TypeId::Ones)) {
     619                negation[l - ++m] = v;
     620            }
     621        }
     622        if (LLVM_UNLIKELY(n != 0 || m != 0)) {
    460623            for (unsigned i = 0; i < n; ++i) {
    461                 const auto v = removed[i];
    462                 assert (edge(u, v, G).second);
    463                 remove_edge(u, v, G);
    464                 assert(hasValidOperandIndicies(v));
    465             }
    466             if (LLVM_UNLIKELY(out_degree(u, G) == 0)) {
    467                 removeVertex(u);
    468                 return true;
    469             }
    470             if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
    471                 // Canonicalize xor operations: (A ⊕ ¬B) = (A ⊕ B ⊕ 1)
    472                 Vertex negation[in_degree(u, G)];
    473                 unsigned count = 0;
    474                 for (const auto e : make_iterator_range(in_edges(u, G))) {
    475                     const auto v = source(e, G);
    476                     if (LLVM_UNLIKELY(getType(v) == TypeId::Not)) {
    477                         negation[count++] = v;
    478                     }
    479                 }
    480                 if (LLVM_UNLIKELY(count != 0)) {
    481                     for (unsigned i = 0; i < count; ++i) {
    482                         const auto v = negation[i];
    483                         assert (edge(v, u, G).second);
    484                         remove_edge(v, u, G);
    485                         addEdge(first_source(in_edges(v, G)), u);
    486                     }
    487                     if ((count & 1) != 0) {
    488                         addEdge(makeVertex(TypeId::Ones), u);
    489                     }
    490                     setModified(u);
    491                     assert(hasValidOperandIndicies(u));
    492                 }
    493             } else { // perform De Morgan's law expansion
    494                 applyDeMorgans(u, typeId);
    495                 return applyAbsorbtionComplementLaw(u, typeId);
    496             }
    497         }
    498         return false;
     624                const auto v = negation[i];
     625                assert (edge(v, u, G).second);
     626                remove_edge(v, u, G);
     627                addEdge(first_source(in_edges(v, G)), u);
     628            }
     629            for (unsigned i = 0; i < m; ++i) {
     630                const auto v = negation[(l - 1) - i];
     631                assert (edge(v, u, G).second);
     632                remove_edge(v, u, G);
     633            }
     634            if (((n + m) & 1) != 0) {
     635                const auto x = makeVertex(TypeId::Not);
     636                for (const auto e : make_iterator_range(out_edges(u, G))) {
     637                    add_edge(x, target(e, G), G[e], G);
     638                }
     639                clear_out_edges(u, G);
     640                add_edge(u, x, 0, G);
     641            }
     642            setModified(u);
     643            assert(hasValidOperandIndicies(u));
     644        }
    499645    }
    500646
     
    502648     * @brief processNegation
    503649     ** ------------------------------------------------------------------------------------------------------------- */
    504     bool processNegation(const Vertex u, const TypeId typeId) {
     650    bool processNegation(const Vertex u) {
    505651
    506652        assert (isLive(u));
    507653        assert ("negation must have one input!" && in_degree(u, G) == 1);
    508         assert (getType(u) == typeId);
    509         assert (typeId == TypeId::Not);
     654        assert (getType(u) == TypeId::Not);
    510655
    511656        const auto v = first_source(in_edges(u, G));
    512657        const auto negatedTypeId = getType(v);
    513658        if (LLVM_UNLIKELY(negatedTypeId == TypeId::Not)) { // ¬¬A = A
    514             const auto w = first_source(in_edges(v, G));
     659            const auto w = getNegatedLiteral(v);
    515660            for (const auto e : make_iterator_range(out_edges(u, G))) {
    516661                const auto v = target(e, G);
     
    520665            removeVertex(u);
    521666            return true;
    522         } else if (LLVM_UNLIKELY(negatedTypeId == TypeId::Xor)) {
    523             // Canonicalize xor operations: ¬(A ⊕ B) = (A ⊕ B ⊕ 1)
    524             setModified(u);
    525             setType(u, TypeId::Xor);
    526             clear_in_edges(u, G);
    527             for (const auto e : make_iterator_range(in_edges(v, G))) {
    528                 add_edge(source(e, G), u, 0, G);
    529             }
    530             addEdge(makeVertex(TypeId::Ones), u);
    531             assert(hasValidOperandIndicies(u));
    532667        }
    533668        return false;
     
    535670
    536671    /** ------------------------------------------------------------------------------------------------------------- *
    537      * @brief applyDeMorgans
    538      ** ------------------------------------------------------------------------------------------------------------- */
    539     void applyDeMorgans(const Vertex u, const TypeId typeId) {
     672     * @brief applyDeMorganExpansion
     673     ** ------------------------------------------------------------------------------------------------------------- */
     674    bool applyDeMorganExpansion(const Vertex u, const TypeId typeId) {
    540675
    541676        assert (isLive(u));
     
    549684            const auto v = source(e, G);
    550685            if (LLVM_UNLIKELY(getType(v) == TypeId::Not)) {
    551                 const auto w = first_source(in_edges(v, G));
    552                 if (LLVM_UNLIKELY(getType(w) == oppositeTypeId(typeId))) {
     686                if (LLVM_UNLIKELY(isDistributive(getType(getNegatedLiteral(v))))) {
    553687                    A[n++] = v;
    554688                }
     
    562696                assert (getType(v) == TypeId::Not);
    563697                remove_edge(v, u, G);
    564                 // NOTE: we cannot remove v even if this was its last edge since
    565                 // it must be in our duplicate check map
    566                 const auto w = first_source(in_edges(v, G));
    567                 assert (getType(w) == oppositeTypeId(typeId));
     698                const auto w = getNegatedLiteral(v);
     699                auto x = u;
     700                const auto innerTypeId = oppositeTypeId(getType(w));
     701                if (innerTypeId != typeId) {
     702                    x = makeVertex(innerTypeId);
     703                    add_edge(x, u, 0, G);
     704                }
    568705                for (const auto e : make_iterator_range(in_edges(w, G))) {
    569                     const auto x = makeVertex(TypeId::Not);
    570                     add_edge(source(e, G), x, 0, G);
    571                     addEdge(x, u);
     706                    addEdge(getNegationOf(source(e, G)), x);
    572707                }
    573708            }
    574709            setModified(u);
     710            reprocessGraph = true;
    575711            assert(hasValidOperandIndicies(u));
    576         }
    577 
     712            return true;
     713        }
     714        return false;
     715    }
     716
     717    /** ------------------------------------------------------------------------------------------------------------- *
     718     * @brief applyXorTransformation
     719     *
     720     * (A ∧ ¬B ∧ C) √ (¬A ∧ B ∧ D) ⇔ (A ⊕ B) ∧ ((A ∧ C) √ (B ∧ D))
     721     *
     722     * (A √ ¬B √ C) ∧ (¬A √ B √ D) ⇔ ¬(A ⊕ B) √ ((A √ C) ∧ (B √ D))
     723     ** ------------------------------------------------------------------------------------------------------------- */
     724    bool applyXorTransformation() {
     725        reprocessGraph = false;
     726        for (const auto u : ordering) {
     727            const auto typeId = getType(u);
     728            if (isDistributive(typeId)) {
     729                if (LLVM_LIKELY(in_degree(u, G) > 1)) {
     730                    while (LLVM_UNLIKELY(applyXorTransformation(u, typeId)));
     731                }
     732            }
     733        }
     734        return reprocessGraph;
     735    }
     736
     737    /** ------------------------------------------------------------------------------------------------------------- *
     738     * @brief applyXorTransformation
     739     *
     740     * (A ∧ ¬B ∧ C) √ (¬A ∧ B ∧ D) ⇔ (A ⊕ B) ∧ ((A ∧ C) √ (B ∧ D))
     741     *
     742     * (A √ ¬B √ C) ∧ (¬A √ B √ D) ⇔ ¬(A ⊕ B) √ ((A √ C) ∧ (B √ D))
     743     ** ------------------------------------------------------------------------------------------------------------- */
     744    bool applyXorTransformation(const Vertex u, const TypeId typeId) {
     745
     746        if (in_degree(u, G) != 2) {
     747            return false;
     748        }
     749
     750        unsigned clauses = 0;
     751        unsigned count = 0;
     752        assert (getType(u) == typeId);
     753        const TypeId innerTypeId = oppositeTypeId(typeId);
     754        assert (in_degree(u, G) > 1);
     755
     756        for (const auto e : make_iterator_range(in_edges(u, G))) {
     757            const auto v = source(e, G);
     758            if (isXorCandidate(v, innerTypeId)) {
     759                ++clauses;
     760                count += in_degree(v, G);
     761            }
     762        }
     763
     764        if (clauses > 1) {
     765            unsigned B[clauses + 1];
     766            Vertex C[clauses];
     767            Vertex V[count];
     768
     769            unsigned i = 0, j = 0;
     770
     771            for (const auto e : make_iterator_range(in_edges(u, G))) {
     772                const auto v = source(e, G);
     773                if (isXorCandidate(v, innerTypeId)) {
     774                    B[i] = j;
     775                    C[i] = v;
     776                    for (const auto e : make_iterator_range(in_edges(v, G))) {
     777                        V[j++] = source(e, G);
     778                    }
     779                    // We know no clause contains {A, A}, {A, ¬A} or {¬¬A} for any A.
     780                    std::sort(V + B[i++], V + j, [this](const Vertex u, const Vertex v){
     781                        return removeNegation(u) < removeNegation(v);
     782                    });
     783                }
     784            }
     785            B[clauses] = j;
     786
     787            for (unsigned i = 0; i < (clauses - 1); ++i) {
     788                for (unsigned j = (i + 1); j < clauses; ++j) {
     789                    bool first = true;
     790                    unsigned ei = B[i], ej = B[j], ek = 0;
     791                    while (ei < B[i + 1] && ej < B[j + 1]) {
     792                        if (V[ei] == V[ej]) {
     793                            ++ei, ++ej;
     794                        } else {
     795                            if (LLVM_UNLIKELY(isNegationOf(V[ei], V[ej]))) {
     796                                if (LLVM_LIKELY(first)) {
     797                                    ek = ei;
     798                                    first = false;
     799                                    ++ei, ++ej;
     800                                    continue;
     801                                } else {
     802                                    const auto x = V[ek];
     803                                    const auto v = C[i];
     804                                    const auto y = V[ej];
     805                                    const auto w = C[j];
     806
     807                                    reprocessGraph = true;
     808
     809                                    assert (edge(x, v, G).second);
     810                                    remove_edge(x, v, G);
     811                                    assert (edge(y, w, G).second);
     812                                    remove_edge(y, w, G);
     813
     814                                    const auto a = makeVertex(typeId);
     815                                    add_edge(v, a, 0, G);
     816                                    add_edge(w, a, 0, G);
     817
     818                                    const auto z = makeVertex(TypeId::Xor);
     819                                    add_edge(x, z, 0, G);
     820                                    add_edge(y, z, 0, G);
     821
     822                                    auto b = z;
     823                                    if (LLVM_UNLIKELY(typeId == TypeId::And)) {
     824                                        b = getNegationOf(z);
     825                                    }
     826                                    canonicalizeXor(z);
     827                                    if (LLVM_UNLIKELY(b != z)) {
     828                                        processNegation(b);
     829                                    }
     830
     831                                    if (in_degree(u, G) == 2) {
     832                                        clear_in_edges(u, G);
     833                                        setType(u, innerTypeId);
     834                                        add_edge(a, u, 0, G);
     835                                        add_edge(b, u, 0, G);
     836                                        return false;
     837                                    } else {
     838                                        assert (edge(v, u, G).second);
     839                                        remove_edge(v, u, G);
     840                                        assert (edge(w, u, G).second);
     841                                        remove_edge(w, u, G);
     842                                        const auto c = makeVertex(innerTypeId);
     843                                        add_edge(a, c, 0, G);
     844                                        add_edge(b, c, 0, G);
     845                                        add_edge(c, u, 0, G);
     846                                        assert (in_degree(u, G) > 1);
     847                                        return true;
     848                                    }
     849                                }
     850                            }
     851                            if (removeNegation(V[ei]) < removeNegation(V[ej])) {
     852                                ++ei;
     853                            } else {
     854                                ++ej;
     855                            }
     856                        }
     857                    }
     858                }
     859            }
     860        }
     861        return false;
     862    }
     863
     864    bool isXorCandidate(const Vertex u, const TypeId typeId) const {
     865        assert (isAssociative(typeId));
     866        return (getType(u) == typeId) && (out_degree(u, G) == 1) && (in_degree(u, G) > 1);
     867    }
     868
     869    bool isNegationOf(const Vertex u, const Vertex v) const {
     870        const auto t = (getType(u) == TypeId::Not);
     871        if (t ^ (getType(v) == TypeId::Not)) {
     872            if (t) {
     873                return getNegatedLiteral(u) == v;
     874            } else { // if (getType(y) == TypeId::Not) {
     875                return u == getNegatedLiteral(v);
     876            }
     877        }
     878        return false;
     879    }
     880
     881    /** ------------------------------------------------------------------------------------------------------------- *
     882     * @brief getNegationOf
     883     ** ------------------------------------------------------------------------------------------------------------- */
     884    Vertex getNegationOf(const Vertex u) {
     885        if (getType(u) == TypeId::Not) {
     886            return getNegatedLiteral(u);
     887        } else {
     888            for (const auto e : make_iterator_range(out_edges(u, G))) {
     889                const auto v = target(e, G);
     890                if (getType(v) == TypeId::Not) {
     891                    return v;
     892                }
     893            }
     894            const auto v = makeVertex(TypeId::Not);
     895            add_edge(u, v, 0, G);
     896            return v;
     897        }
     898    }
     899
     900    Vertex getNegatedLiteral(const Vertex u) const {
     901        assert (getType(u) == TypeId::Not);
     902        assert (in_degree(u, G) == 1);
     903        return first_source(in_edges(u, G));
     904    }
     905
     906    Vertex removeNegation(const Vertex u) const {
     907        return getType(u) == TypeId::Not ? getNegatedLiteral(u) : u;
    578908    }
    579909
     
    595925            const auto innerTypeId = getType(v);
    596926            if (innerTypeId == TypeId::Not) {
    597                 const auto w = first_source(in_edges(v, G));
     927                const auto w = getNegatedLiteral(v);
    598928                assert (isLive(w));
    599929                for (const auto ej : make_iterator_range(in_edges(u, G))) {
     
    613943        if (n) {
    614944            setModified(u);
     945            reprocessGraph = true;
    615946            for (;;) {
    616947                const auto v = A[--n];
     
    7171048            setModified(v);
    7181049            clear_in_edges(v, G);
    719             // We could recursively call "processConstant" but this could cause a stack overflow
    720             // in a pathological case. Instead rely on the fact v will be processed eventually.
    7211050        }
    7221051
     
    7281057        return false;
    7291058    }
    730 
    7311059
    7321060    /** ------------------------------------------------------------------------------------------------------------- *
     
    7601088            const auto upperSet = obtainDistributableSources(std::get<1>(lower));
    7611089            for (const auto & upper : upperSet) {
     1090
    7621091                const auto & inner = std::get<0>(upper);
    7631092                const auto & sources = std::get<1>(upper);
     
    7671096
    7681097                // Update G to match the desired change
    769                 const auto x = makeVertex(outerTypeId);
    770                 const auto y = makeVertex(innerTypeId);
     1098                auto x = makeVertex(outerTypeId);
     1099                auto y = makeVertex(innerTypeId);
    7711100
    7721101                for (const Vertex i : sources) {
     
    7781107                        remove_edge(u, v, G);
    7791108                    }
    780                     addEdge(u, y);
    781                 }
    782 
     1109                    add_edge(u, y, 0, G);
     1110                }
     1111                y = consolidate(y);
    7831112                for (const auto i : inner) {
    7841113                    const auto u = Gd[i];
     
    7901119                        remove_edge(u, v, G);
    7911120                    }
    792                     addEdge(u, x);
    793                 }
    794 
     1121                    add_edge(u, x, 0, G);
     1122                }
     1123                x = consolidate(x);
    7951124                addEdge(x, y);
    796 
    7971125                for (const Vertex i : outer) {
    7981126                    const auto u = Gd[i];
     
    8011129                    addEdge(y, u);
    8021130                }
    803 
    8041131                modified = true;
    8051132            }
     
    8241151                if (isDistributive(outerTypeId)) {
    8251152                    const auto n = in_degree(u, G);
     1153                    if (n < 2) continue;
    8261154                    assert (n > 1);
    8271155                    const auto innerTypeId = oppositeTypeId(getType(u));
     
    9081236    void factorizeGraph() {
    9091237
    910         Sequence groups[3];
     1238        Sequence associative;
    9111239        for (const auto u : make_iterator_range(vertices(G))) {
    912             if (isLive(u)) {
    913                 switch (getType(u)) {
    914                     case TypeId::And:
    915                         groups[0].push_back(u); break;
    916                     case TypeId::Or:
    917                         groups[1].push_back(u); break;
    918                     case TypeId::Xor:
    919                         groups[2].push_back(u); break;
    920                     default: break;
    921                 }
    922             }
    923         }
    924 
    925         const TypeId op[3] = { TypeId::And, TypeId::Or, TypeId::Xor };
    926 
    927         for (unsigned i = 0; i < 3; ++i) {
    928 
    929             // Although we risk losing better combinations by greedily taking the larger factorings,
    930             // choosing only those of minSize or greater first can significantly reduce the running
    931             // time of this optimization.
    932 
    933             for (unsigned minSize = 64; minSize >= 2; minSize /= 2)  {
    934 
    935                 for (;;) {
    936 
    937                     auto factors = makeIndependent(enumerateBicliques(groups[i], G, 2, minSize), 1);
    938                     if (factors.empty()) {
    939                         break;
    940                     }
    941 
    942                     for (auto & factor : factors) {
    943                         const auto & sources = std::get<1>(factor);
    944                         assert (sources.size() > 1);
    945                         auto & targets = std::get<0>(factor);
    946                         assert (targets.size() > 1);
    947 
    948                         // Check whether one of the targets is the factorization
    949                         Vertex x = 0;
    950                         bool create = true;
    951                         for (auto j = targets.begin(); j != targets.end(); ) {
    952                             assert (hasValidOperandIndicies(*j));
    953                             if (in_degree(*j, G) == sources.size()) {
    954                                 if (LLVM_LIKELY(create)) {
    955                                     x = *j;
    956                                     create = false;
    957                                 } else {
    958                                     for (auto e : make_iterator_range(out_edges(*j, G))) {
    959                                         addEdge(x, target(e, G), G[e]);
    960                                     }
    961                                     removeVertex(*j);
    962                                 }
    963                                 j = targets.erase(j);
    964                             } else {
    965                                 ++j;
     1240            if (isLive(u) && isAssociative(getType(u))) {
     1241                associative.push_back(u);
     1242            }
     1243        }
     1244
     1245        // Although we risk losing better combinations by greedily taking the larger factorings,
     1246        // choosing only those of minSize or greater first can significantly reduce the running
     1247        // time of this optimization.
     1248
     1249        Sequence group[3];
     1250
     1251        const TypeId typeCode[3] = { TypeId::And, TypeId::Or, TypeId::Xor };
     1252
     1253        for (;;) {
     1254
     1255            auto factors = makeIndependent(enumerateBicliques(associative, G, 2, 2), 1);
     1256            if (factors.empty()) {
     1257                break;
     1258            }
     1259
     1260            bool unchanged = true;
     1261
     1262            for (auto & factor : factors) {
     1263                const auto & sources = std::get<1>(factor);
     1264                assert (sources.size() > 1);
     1265                auto & targets = std::get<0>(factor);
     1266                assert (targets.size() > 1);
     1267
     1268                for (unsigned k = 0; k < 3; ++k) {
     1269                    assert (group[k].empty());
     1270                }
     1271
     1272                // Group the target sets and check whether any target is the factorization
     1273                Vertex t[3];
     1274                bool create[3] = { true, true, true };
     1275                for (const auto u : targets) {
     1276                    assert (hasValidOperandIndicies(u));
     1277                    const auto k = factorGroup(getType(u));
     1278                    if (LLVM_UNLIKELY(in_degree(u, G) == sources.size())) {
     1279                        if (LLVM_LIKELY(create[k])) {
     1280                            t[k] = u;
     1281                            create[k] = false;
     1282                        } else {
     1283                            for (auto e : make_iterator_range(out_edges(u, G))) {
     1284                                addEdge(t[k], target(e, G), G[e]);
    9661285                            }
     1286                            removeVertex(u);
    9671287                        }
    968                         if (create) {
    969                             x = makeVertex(op[i]);
    970                             groups[i].push_back(x);
    971                             for (auto u : sources) {
    972                                 add_edge(u, x, 0, G);
    973                             }
    974                             assert (hasValidOperandIndicies(x));
     1288                    } else {
     1289                        group[k].push_back(u);
     1290                    }
     1291                }
     1292
     1293                for (unsigned k = 0; k < 3; ++k) {
     1294                    if (LLVM_LIKELY(group[k].empty())) {
     1295                        continue;
     1296                    }
     1297                    if (LLVM_LIKELY(create[k])) {
     1298                        t[k] = makeVertex(typeCode[k]);
     1299                        for (auto u : sources) {
     1300                            add_edge(u, t[k], 0, G);
    9751301                        }
    976 
    977                         // Remove the biclique between the source and target vertices
    978                         for (auto u : sources) {
    979                             for (auto v : targets) {
    980                                 assert (getType(v) == op[i]);
    981                                 assert (edge(u, v, G).second);
    982                                 boost::remove_edge(u, v, G);
    983                             }
     1302                        associative.push_back(t[k]);
     1303                    }
     1304                    assert (hasValidOperandIndicies(t[k]));
     1305                    // Remove the biclique between the source and target vertices
     1306                    for (auto u : sources) {
     1307                        for (auto v : group[k]) {
     1308                            assert (getType(v) == typeCode[k]);
     1309                            assert (edge(u, v, G).second);
     1310                            boost::remove_edge(u, v, G);
    9841311                        }
    985 
    986                         // ... and replace it with the factorization
    987                         for (auto v : targets) {
    988                             assert (getType(v) == op[i]);
    989                             addEdge(x, v);
    990                             setModified(v);
    991                             assert(hasValidOperandIndicies(v));
    992                         }
    993                     }
    994                 }
    995             }
    996         }
    997     }
     1312                    }
     1313                    // ... and replace it with the factorization
     1314                    for (auto v : group[k]) {
     1315                        assert (getType(v) == typeCode[k]);
     1316                        addEdge(t[k], v);
     1317                        setModified(v);
     1318                        assert(hasValidOperandIndicies(v));
     1319                    }
     1320                    group[k].clear();
     1321                    unchanged = false;
     1322                }
     1323            }
     1324
     1325            if (unchanged) {
     1326                break;
     1327            }
     1328        }
     1329
     1330//        #ifndef NDEBUG
     1331//        for (const auto u : make_iterator_range(vertices(G))) {
     1332//            if (LLVM_LIKELY(isLive(u))) {
     1333//                const auto typeId = getType(u);
     1334//                if (isAssociative(typeId)) {
     1335//                    if (in_degree(u, G) != 2) {
     1336//                        bool atMostOneSourceVertexCanHaveAnOutDegreeOverOne = true;
     1337//                        for (auto e : make_iterator_range(in_edges(u, G))) {
     1338//                            if (out_degree(source(e, G), G) != 1) {
     1339//                                assert (atMostOneSourceVertexCanHaveAnOutDegreeOverOne);
     1340//                                atMostOneSourceVertexCanHaveAnOutDegreeOverOne = false;
     1341//                            }
     1342//                        }
     1343//                    }
     1344//                }
     1345//            }
     1346//        }
     1347//        #endif
     1348
     1349    }
     1350
     1351    unsigned factorGroup(const TypeId typeId) {
     1352        switch (typeId) {
     1353            case TypeId::And:
     1354                return 0; break;
     1355            case TypeId::Or:
     1356                return 1; break;
     1357            case TypeId::Xor:
     1358                return 2; break;
     1359            default: llvm_unreachable("impossible");
     1360        }
     1361    }
     1362
     1363//    /** ------------------------------------------------------------------------------------------------------------- *
     1364//     * @brief applyDeMorganContraction
     1365//     ** ------------------------------------------------------------------------------------------------------------- */
     1366//    bool applyDeMorganContraction(const Vertex u, const TypeId typeId) {
     1367
     1368//        assert (isLive(u));
     1369//        assert (in_degree(u, G) > 0);
     1370//        assert (getType(u) == typeId);
     1371//        assert (isDistributive(typeId));
     1372
     1373//        Vertex T[in_degree(u, G)];
     1374//        unsigned n = 0;
     1375//        for (const auto e : make_iterator_range(in_edges(u, G))) {
     1376//            const auto v = source(e, G);
     1377//            if (getType(v) == TypeId::Not) {
     1378//                T[n++] = v;
     1379//            }
     1380//        }
     1381//        if (LLVM_UNLIKELY(n > 1)) {
     1382//            const auto oppositeType = oppositeTypeId(typeId);
     1383//            Vertex x = makeVertex(oppositeType);
     1384//            for (unsigned i = 0; i < n; ++i) {
     1385//                const auto v = T[i];
     1386//                const auto w = first_source(in_edges(v, G));
     1387//                add_edge(w, x, 0, G);
     1388//                remove_edge(v, u, G);
     1389//            }
     1390//            x = consolidate(x);
     1391//            if (in_degree(u, G) == 0) {
     1392//                setType(u, TypeId::Not);
     1393//                add_edge(x, u, 0, G);
     1394//                processNegation(u);
     1395//                return true;
     1396//            } else {
     1397//                Vertex y = makeVertex(TypeId::Not);
     1398//                add_edge(x, y, 0, G);
     1399//                y = consolidate(y);
     1400//                add_edge(y, u, 0, G);
     1401//                processNegation(y);
     1402//            }
     1403//            return processAssociative(x, oppositeType);
     1404//        }
     1405//        return false;
     1406//    }
     1407
    9981408
    9991409private:
     
    10291439                    }
    10301440                    if (B.size() >= minimumSizeB) {
    1031                         std::sort(B.begin(), B.end());
    1032                         assert(std::unique(B.begin(), B.end()) == B.end());
     1441                        // std::sort(B.begin(), B.end());
     1442                        assert (std::is_sorted(B.begin(), B.end()));
     1443                        assert (std::unique(B.begin(), B.end()) == B.end());
    10331444                        B1.insert(std::move(B));
    10341445                    }
     
    10911502                        T.push_back(target(e, G));
    10921503                    }
    1093                     std::sort(T.begin(), T.end());
    1094                     assert(std::unique(T.begin(), T.end()) == T.end());
     1504                    // std::sort(T.begin(), T.end());
     1505                    assert (std::is_sorted(T.begin(), T.end()));
     1506                    assert (std::unique(T.begin(), T.end()) == T.end());
    10951507                    Aj.clear();
    10961508                    Aj.reserve(std::min(Ai.size(), T.size()));
     
    11181530
    11191531        const auto l = S.size();
    1120         IndependentSetGraph I(l);
    1121 
    11221532        assert (independentSide < 2);
    1123 
    1124         // Initialize our weights
    1125         for (unsigned i = 0; i != l; ++i) {
    1126             I[i] = std::get<0>(S[i]).size() * std::get<1>(S[i]).size();
    1127         }
    1128 
    1129         // Determine our constraints
    1130         for (unsigned i = 0; i != l; ++i) {
    1131             const auto & Si = (independentSide == 0) ? std::get<0>(S[i]) : std::get<1>(S[i]);
    1132             for (unsigned j = i + 1; j != l; ++j) {
    1133                 const auto & Sj = (independentSide == 0) ? std::get<0>(S[j]) : std::get<1>(S[j]);
    1134                 if (intersects(Si, Sj)) {
    1135                     boost::add_edge(i, j, I);
    1136                 }
    1137             }
    1138         }
    1139 
    1140         // Use the greedy algorithm to choose our independent set
    1141         Sequence selected;
    1142         for (;;) {
    1143             unsigned w = 0;
    1144             Vertex u = 0;
     1533        if (LLVM_LIKELY(l > 1)) {
     1534
     1535            IndependentSetGraph I(l);
     1536
     1537            // Initialize our weights
    11451538            for (unsigned i = 0; i != l; ++i) {
    1146                 if (I[i] > w) {
    1147                     w = I[i];
    1148                     u = i;
    1149                 }
    1150             }
    1151             if (LLVM_UNLIKELY(w == 0)) break;
    1152             selected.push_back(u);
    1153             I[u] = 0;
    1154             for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
    1155                 I[v] = 0;
    1156             }
    1157         }
    1158 
    1159         // Sort the selected list and then remove the unselected cliques
    1160         std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
    1161         auto end = S.end();
    1162         for (const unsigned offset : selected) {
    1163             end = S.erase(S.begin() + offset + 1, end) - 1;
    1164         }
    1165         S.erase(S.begin(), end);
     1539                I[i] = std::get<0>(S[i]).size() * std::get<1>(S[i]).size();
     1540            }
     1541
     1542            // Determine our constraints
     1543            for (unsigned i = 0; i != l; ++i) {
     1544                const auto & Si = (independentSide == 0) ? std::get<0>(S[i]) : std::get<1>(S[i]);
     1545                for (unsigned j = i + 1; j != l; ++j) {
     1546                    const auto & Sj = (independentSide == 0) ? std::get<0>(S[j]) : std::get<1>(S[j]);
     1547                    if (intersects(Si, Sj)) {
     1548                        boost::add_edge(i, j, I);
     1549                    }
     1550                }
     1551            }
     1552
     1553            // Use the greedy algorithm to choose our independent set
     1554            Sequence selected;
     1555            for (;;) {
     1556                Vertex u = 0;
     1557                auto w = I[0];
     1558                for (unsigned i = 1; i != l; ++i) {
     1559                    if (I[i] > w) {
     1560                        w = I[i];
     1561                        u = i;
     1562                    }
     1563                }
     1564                if (LLVM_UNLIKELY(w == 0)) break;
     1565                selected.push_back(u);
     1566                I[u] = 0;
     1567                for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
     1568                    I[v] = 0;
     1569                }
     1570            }
     1571
     1572            // Sort the selected list and then remove the unselected cliques
     1573            std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
     1574            auto end = S.end();
     1575            for (const unsigned offset : selected) {
     1576                end = S.erase(S.begin() + offset + 1, end) - 1;
     1577            }
     1578            S.erase(S.begin(), end);
     1579        }
    11661580
    11671581        return std::move(S);
     
    11721586     ** ------------------------------------------------------------------------------------------------------------- */
    11731587    Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) {
     1588        reprocessGraph = true;
    11741589        return add_vertex(std::make_tuple(expr, typeId, expr ? State::Live : State::Modified, 0), G);
    11751590    }
     
    12141629            M.emplace(stmt, w);
    12151630            return w;
     1631//        } else if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
     1632//            assert (stmt->getNumOperands() == 2);
     1633//            const auto a = addExpression(stmt->getOperand(0));
     1634//            const auto b = addExpression(stmt->getOperand(1));
     1635//            const auto c = makeVertex(TypeId::Not);
     1636//            add_edge(b, c, 0, G);
     1637//            const auto d = makeVertex(TypeId::Not);
     1638//            add_edge(a, d, 0, G);
     1639//            const auto u = makeVertex(TypeId::And);
     1640//            add_edge(a, u, 0, G);
     1641//            add_edge(c, u, 1, G);
     1642//            const auto v = makeVertex(TypeId::And);
     1643//            add_edge(b, v, 0, G);
     1644//            add_edge(d, v, 1, G);
     1645//            const auto w = makeVertex(TypeId::Or);
     1646//            add_edge(u, w, 0, G);
     1647//            add_edge(v, w, 1, G);
     1648//            M.emplace(stmt, w);
     1649//            return w;
    12161650        } else {
    1217             const auto u = makeVertex(typeId, stmt);
     1651            const auto u = makeVertex(typeId, isRegenerable(typeId) ? nullptr : stmt);
    12181652            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    12191653                PabloAST * const op = stmt->getOperand(i);
     
    12371671            for (const auto e : make_iterator_range(out_edges(u, G))) {
    12381672                if (LLVM_UNLIKELY(target(e, G) == v)) {
    1239                     if (LLVM_LIKELY(isDistributive(typeId))) {
    1240                         G[e] = std::max(G[e], index);
    1241                     } else {
     1673                    if (LLVM_UNLIKELY(typeId == TypeId::Xor)) {
    12421674                        remove_edge(e, G);
    12431675                    }
     
    12501682    }
    12511683
    1252     #ifndef NDEBUG
    12531684    /** ------------------------------------------------------------------------------------------------------------- *
    12541685     * @brief hasValidOperandIndicies
     
    13371768        return isConstant(typeId) || isLiteral(typeId);
    13381769    }
    1339     #endif
    13401770
    13411771    /** ------------------------------------------------------------------------------------------------------------- *
     
    13441774    void removeVertex(const Vertex u) { assert (isLive(u));
    13451775        setDead(u);
     1776        Vertex D[in_degree(u, G)];
     1777        unsigned n = 0;
     1778        for (const auto e : make_iterator_range(in_edges(u, G))) {
     1779            const auto v = source(e, G);
     1780            if (LLVM_UNLIKELY(out_degree(v, G) == 1)) {
     1781                D[n++] = v;
     1782            }
     1783        }
     1784        while (LLVM_UNLIKELY(n != 0)) {
     1785            removeVertex(D[--n]);
     1786        }
    13461787        clear_vertex(u, G);
    1347     }
    1348 
    1349     /** ------------------------------------------------------------------------------------------------------------- *
    1350      * @brief remapVertex
    1351      ** ------------------------------------------------------------------------------------------------------------- */
    1352     void remapVertex(const Vertex u, const Vertex v) { assert (u != v);
     1788        reprocessGraph = true;
     1789    }
     1790
     1791    /** ------------------------------------------------------------------------------------------------------------- *
     1792     * @brief consolidate
     1793     ** ------------------------------------------------------------------------------------------------------------- */
     1794    Vertex consolidate(const Vertex u) {
     1795        assert (isLive(u));
     1796        assert (hasValidOperandIndicies(u));
     1797        const auto f = V.insert(u);
     1798        if (LLVM_UNLIKELY(f.second)) {           
     1799            return u;
     1800        }
     1801        const auto v = *f.first;
     1802        assert (u != v);
     1803        assert (isLive(v));
    13531804        const PabloAST * expr = getValue(u);
    13541805        if (expr) {
     1806            assert (!isRegenerable(getType(u)));
    13551807            auto f = M.find(expr);
    13561808            assert (f != M.end() && f->second == u);
    13571809            f->second = v;
    13581810            setValue(v, nullptr);
     1811            setModified(v);
    13591812        }
    13601813        for (const auto e : make_iterator_range(out_edges(u, G))) {
     
    13621815        }
    13631816        removeVertex(u);
     1817        return v;
    13641818    }
    13651819
     
    14141868    }
    14151869
    1416     TypeId getType(const Vertex u) const {
     1870    static TypeId getType(const Vertex u, const Graph & G) {
    14171871        assert (u < num_vertices(G));
    14181872        return std::get<1>(G[u]);
     1873    }
     1874
     1875    TypeId getType(const Vertex u) const {
     1876        return getType(u, G);
    14191877    }
    14201878
     
    14241882    }
    14251883
    1426     PabloAST * getValue(const Vertex u) const {
     1884    static PabloAST * getValue(const Vertex u, const Graph & G) {
    14271885        assert (u < num_vertices(G));
    14281886        return std::get<0>(G[u]);
     1887    }
     1888
     1889    PabloAST * getValue(const Vertex u) const {
     1890        return getValue(u, G);
    14291891    }
    14301892
     
    14551917
    14561918    void setModified(const Vertex u) {
    1457         assert(!isImmutable(getType(u)));
    14581919        setState(u, State::Modified);
    14591920    }
     
    14761937    void setLastUsageTime(const Vertex u, const UsageTime time) {
    14771938        assert (u < num_vertices(G));
     1939
     1940//        errs() << "   " << u << " ";
     1941//        PabloPrinter::print(getValue(u), errs());
     1942//        errs() << " @ " << time << "\n";
     1943
     1944
    14781945        std::get<3>(G[u]) = time;
    14791946    }
     
    15392006    }
    15402007
    1541     Vertex first_source(const std::pair<in_edge_iterator, in_edge_iterator> & e) const {
     2008    Vertex first_source(const std::pair<InEdgeIterator, InEdgeIterator> & e) const {
    15422009        return source(*std::get<0>(e), G);
    15432010    }
    15442011
    15452012private:
     2013
     2014    struct IdentityHash {
     2015        size_t operator()(const Vertex u) const {
     2016            using value_of = std::underlying_type<TypeId>::type;
     2017//            InEdgeIterator begin, end;
     2018//            std::tie(begin, end) = in_edges(u, G);
     2019//            assert (std::is_sorted(begin, end));
     2020            const auto n = in_degree(u, G);
     2021            Vertex operands[n];
     2022            unsigned i = 0;
     2023            for (auto e : make_iterator_range(in_edges(u, G))) {
     2024                operands[i++] = source(e, G);
     2025            }
     2026            std::sort(operands, operands + n);
     2027            size_t h = 0;
     2028            boost::hash_combine(h, static_cast<value_of>(PassContainer::getType(u, G)));
     2029            for (unsigned j = 0; j < n; ++j) {
     2030                boost::hash_combine(h, operands[j]);
     2031            }
     2032//            for (auto e : make_iterator_range(in_edges(u, G))) {
     2033//                boost::hash_combine(h, source(e, G));
     2034//            }
     2035            return h;
     2036        }
     2037        IdentityHash (const Graph & g) : G(g) { }
     2038    private:
     2039        const Graph & G;
     2040    };
     2041
     2042    struct IdentityComparator {
     2043        bool operator()(const Vertex u, const Vertex v) const {
     2044            const auto typeId = getType(u, G);
     2045            if (LLVM_LIKELY(typeId == getType(v, G))) {
     2046                const unsigned n = in_degree(u, G);
     2047                if (LLVM_UNLIKELY(n == 0)) {
     2048                    assert (isNullary(typeId) && in_degree(v, G) == 0);
     2049                    if (LLVM_UNLIKELY(isLiteral(typeId))) {
     2050                        assert (getValue(u, G) && getValue(v, G));
     2051                        return getValue(u, G) == getValue(v, G);
     2052                    }
     2053                    return true;
     2054                }
     2055                if (in_degree(v, G) == n) {
     2056                    Vertex adjA[n];
     2057                    Vertex adjB[n];
     2058                    auto ei = std::get<0>(in_edges(u, G));
     2059                    auto ej = std::get<0>(in_edges(v, G));
     2060                    // if this is an associative op, order doesn't matter
     2061                    if (isAssociative(typeId)) {
     2062                        for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
     2063                            adjA[i] = source(*ei, G);
     2064                            adjB[i] = source(*ej, G);
     2065                        }
     2066                        assert(std::is_sorted(adjA, adjA + n));
     2067                        assert(std::is_sorted(adjB, adjB + n));
     2068                    } else { // otherwise consider the order indicated by the edges
     2069                        for (unsigned i = 0; i < n; ++i, ++ei, ++ej) {
     2070                            adjA[G[*ei]] = source(*ei, G);
     2071                            adjB[G[*ej]] = source(*ej, G);
     2072                        }
     2073                    }
     2074                    for (unsigned i = 0; i < n; ++i) {
     2075                        if (adjA[i] != adjB[i]) {
     2076                            return false;
     2077                        }
     2078                    }
     2079                    return true;
     2080                }
     2081            }
     2082            return false;
     2083        }
     2084        IdentityComparator (const Graph & g) : G(g) { }
     2085    private:
     2086        const Graph & G;
     2087    };
     2088
     2089    using IdentitySet = std::unordered_set<Vertex, IdentityHash, IdentityComparator>;
     2090
     2091private:
     2092
     2093    bool reprocessGraph;
    15462094
    15472095    Graph G;
    15482096    flat_map<const pablo::PabloAST *, Vertex> M;
     2097
     2098    IdentitySet V;
    15492099
    15502100    DistributionGraph Gd;
     
    15642114    PabloVerifier::verify(kernel, "post-distributive-pass");
    15652115    #endif
     2116
     2117//    errs() << "-----------------------------------------------\n"
     2118//              "BEFORE SIMPLIFICATION:\n"
     2119//              "-----------------------------------------------\n";
     2120//    PabloPrinter::print(kernel, errs());
     2121
    15662122    Simplifier::optimize(kernel);
     2123
     2124//    errs() << "-----------------------------------------------\n"
     2125//              "AFTER SIMPLIFICATION:\n"
     2126//              "-----------------------------------------------\n";
     2127//    PabloPrinter::print(kernel, errs());
     2128
    15672129    return true;
    15682130}
Note: See TracChangeset for help on using the changeset viewer.