Ignore:
Timestamp:
May 22, 2017, 12:14:19 PM (2 years ago)
Author:
nmedfort
Message:

Restructuring work for the Driver classes. Start of work to eliminate the memory leaks with the ExecutionEngine?. Replaced custom AlignedMalloc? with backend call to std::aligned_malloc. Salvaged some work on DistributionPass? for reevaluation.

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
6 edited

Legend:

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

    r5440 r5464  
    222222        iBuilder->CreateMemCpy(newArray, array, capacitySize, BlockWidth);
    223223        iBuilder->CreateMemZero(iBuilder->CreateGEP(newArray, capacitySize), capacitySize, BlockWidth);
    224         iBuilder->CreateAlignedFree(array);
     224        iBuilder->CreateFree(array);
    225225        newArray = iBuilder->CreatePointerCast(newArray, array->getType());
    226226        iBuilder->CreateStore(newArray, arrayPtr);
     
    235235        iBuilder->CreateMemCpy(newSummary, summary, summarySize, BlockWidth);
    236236        iBuilder->CreateMemZero(iBuilder->CreateGEP(newSummary, summarySize), iBuilder->getSize(2 * BlockWidth), BlockWidth);
    237         iBuilder->CreateAlignedFree(summary);
     237        iBuilder->CreateFree(summary);
    238238
    239239        Value * ptr1 = iBuilder->CreateGEP(newSummary, summarySize);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r5267 r5464  
    11#include "distributivepass.h"
    22
     3#include <pablo/pablo_kernel.h>
    34#include <pablo/codegenstate.h>
    4 #ifndef NDEBUG
    5 #include <pablo/analysis/pabloverifier.hpp>
    6 #endif
    7 #include <pablo/optimizers/pablo_simplifier.hpp>
    8 #include <pablo/passes/flattenassociativedfg.h>
     5#include <pablo/branch.h>
     6#include <pablo/pe_string.h>
     7#include <pablo/pe_integer.h>
     8#include <pablo/pe_zeroes.h>
     9#include <pablo/pe_ones.h>
     10#include <pablo/boolean.h>
    911#include <boost/container/flat_set.hpp>
    1012#include <boost/container/flat_map.hpp>
    1113#include <boost/graph/adjacency_list.hpp>
    12 
    13 #include <pablo/printer_pablos.h>
    14 #include <iostream>
     14#include <boost/graph/topological_sort.hpp>
     15#include <boost/function_output_iterator.hpp>
     16
     17#include <boost/graph/strong_components.hpp>
     18#include <llvm/Support/raw_ostream.h>
    1519
    1620using namespace boost;
    1721using namespace boost::container;
    18 
    19 namespace pablo {
    20 
    21 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     22using namespace llvm;
     23
     24using TypeId = pablo::PabloAST::ClassTypeId;
     25using VertexData = std::pair<pablo::PabloAST *, TypeId>;
     26
     27using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, VertexData, pablo::PabloAST *>;
    2228using Vertex = Graph::vertex_descriptor;
    23 using Map = flat_map<PabloAST *, Vertex>;
     29
     30using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
     31using DistributionVertex = DistributionGraph::vertex_descriptor;
     32
    2433using VertexSet = std::vector<Vertex>;
    2534using Biclique = std::pair<VertexSet, VertexSet>;
     
    2736using DistributionSet = std::tuple<VertexSet, VertexSet, VertexSet>;
    2837using DistributionSets = std::vector<DistributionSet>;
    29 using TypeId = PabloAST::ClassTypeId;
     38
     39using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
     40
     41namespace pablo {
     42
    3043
    3144/** ------------------------------------------------------------------------------------------------------------- *
    32  * @brief intersects
     45 * @brief printGraph
    3346 ** ------------------------------------------------------------------------------------------------------------- */
    34 template <class Type>
    35 inline bool intersects(Type & A, Type & B) {
    36     auto first1 = A.begin(), last1 = A.end();
    37     auto first2 = B.begin(), last2 = B.end();
    38     while (first1 != last1 && first2 != last2) {
    39         if (*first1 < *first2) {
    40             ++first1;
    41         } else if (*first2 < *first1) {
    42             ++first2;
     47static void printGraph(const Graph & G, const std::string & name, llvm::raw_ostream & out) {
     48
     49    std::vector<unsigned> c(num_vertices(G));
     50    strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
     51
     52    out << "digraph " << name << " {\n";
     53    for (auto u : make_iterator_range(vertices(G))) {
     54        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     55            continue;
     56        }
     57        out << "v" << u << " [label=\"" << u << ": ";
     58        TypeId typeId;
     59        PabloAST * expr;
     60        std::tie(expr, typeId) = G[u];
     61        bool temporary = false;
     62        bool error = false;
     63        if (expr == nullptr || (typeId != expr->getClassTypeId() && typeId != TypeId::Var)) {
     64            temporary = true;
     65            switch (typeId) {
     66                case TypeId::And:
     67                    out << "And";
     68                    break;
     69                case TypeId::Or:
     70                    out << "Or";
     71                    break;
     72                case TypeId::Xor:
     73                    out << "Xor";
     74                    break;
     75                case TypeId::Not:
     76                    out << "Not";
     77                    break;
     78                default:
     79                    out << "???";
     80                    error = true;
     81                    break;
     82            }
     83            if (expr) {
     84                out << " ("; expr->print(out); out << ")";
     85            }
    4386        } else {
    44             return true;
    45         }
    46     }
    47     return false;
     87            expr->print(out);
     88        }
     89        out << "\"";
     90        if (typeId == TypeId::Var) {
     91            out << " style=dashed";
     92        }
     93        if (error) {
     94            out << " color=red";
     95        } else if (temporary) {
     96            out << " color=blue";
     97        }
     98        out << "];\n";
     99    }
     100    for (auto e : make_iterator_range(edges(G))) {
     101        const auto s = source(e, G);
     102        const auto t = target(e, G);
     103        out << "v" << s << " -> v" << t;
     104        bool cyclic = (c[s] == c[t]);
     105        if (G[e] || cyclic) {
     106            out << " [";
     107            PabloAST * const expr = G[e];
     108            if (expr) {
     109                out << "label=\"";
     110                expr->print(out);
     111                out << "\" ";
     112             }
     113             if (cyclic) {
     114                out << "color=red ";
     115             }
     116             out << "]";
     117        }
     118        out << ";\n";
     119    }
     120
     121    if (num_vertices(G) > 0) {
     122
     123        out << "{ rank=same;";
     124        for (auto u : make_iterator_range(vertices(G))) {
     125            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     126                out << " v" << u;
     127            }
     128        }
     129        out << "}\n";
     130
     131        out << "{ rank=same;";
     132        for (auto u : make_iterator_range(vertices(G))) {
     133            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     134                out << " v" << u;
     135            }
     136        }
     137        out << "}\n";
     138
     139    }
     140
     141    out << "}\n\n";
     142    out.flush();
    48143}
    49144
    50 /** ------------------------------------------------------------------------------------------------------------- *
    51  * @brief independentCliqueSets
    52  ** ------------------------------------------------------------------------------------------------------------- */
    53 static BicliqueSet && independentCliqueSets(BicliqueSet && bicliques, const bool uppsetSet) {
    54     using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    55 
    56     const auto l = bicliques.size();
    57     IndependentSetGraph I(l);
    58 
    59 
    60     // Initialize our weights and determine the constraints
    61     if (uppsetSet) {
    62         for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
    63             I[std::distance(bicliques.begin(), i)] = std::pow(std::get<0>(*i).size(), 2);
    64             for (auto j = i; ++j != bicliques.end(); ) {
    65                 if (intersects(i->first, j->first)) {
    66                     add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
    67                 }
    68             }
    69         }
    70     } else {
    71         for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
    72             I[std::distance(bicliques.begin(), i)] = std::pow(std::get<1>(*i).size(), 2);
    73             for (auto j = i; ++j != bicliques.end(); ) {
    74                 if (intersects(i->first, j->first) && intersects(i->second, j->second)) {
    75                     add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
    76                 }
    77             }
    78         }
    79     }
    80 
    81 
    82     // Use the greedy algorithm to choose our independent set
    83     VertexSet selected;
    84     for (;;) {
    85         unsigned w = 0;
    86         Vertex u = 0;
     145struct PassContainer {
     146
     147    /** ------------------------------------------------------------------------------------------------------------- *
     148     * @brief run
     149     *
     150     * Based on the knowledge that:
     151     *
     152     *  (ASSOCIATIVITY)    A ∧ (B ∧ C) ⇔ (A ∧ B) ∧ C ⇔ A ∧ B ∧ C   and   A √ (B √ C) ⇔ (A √ B) √ C ⇔ A √ B √ C
     153     *
     154     *  (IDENTITY)         A √ 0 ⇔ A   and   A ∧ 1 = A
     155     *
     156     *  (ANNULMENT)        A ∧ 0 ⇔ 0   and   A √ 1 = 1
     157     *
     158     *  (IDEMPOTENT)       A √ (A √ B) ⇔ A √ B   and   A ∧ (A ∧ B) ⇔ A ∧ B
     159     *
     160     *  (ABSORBTION)       A √ (A ∧ B) ⇔ A ∧ (A √ B) ⇔ A
     161     *
     162     *  (COMPLEMENT)       A √ ¬A ⇔ 1   and   A ∧ ¬A = 0
     163     *
     164     *  (DISTRIBUTIVITY)   (A ∧ B) √ (A ∧ C) ⇔ A ∧ (B √ C)   and   (A √ B) ∧ (A √ C) ⇔ A √ (B ∧ C)
     165     *
     166     * Try to eliminate some of the unnecessary operations from the current Variadic expressions
     167     ** ------------------------------------------------------------------------------------------------------------- */
     168    void run(PabloBlock * const block) {
     169        Statement * stmt = block->front();
     170        // Statement * first = stmt;
     171        while (stmt) {
     172            Statement * next = stmt->getNextNode();
     173            if (isa<Branch>(stmt)) {
     174                // addUsageInformation();
     175                if (simplifyGraph()) {
     176                    // rewriteAST(first, stmt);
     177
     178                    // printGraph(G, "G", errs());
     179                }
     180
     181
     182
     183                G.clear();
     184                M.clear();
     185                run(cast<Branch>(stmt)->getBody());
     186                G.clear();
     187                M.clear();
     188            } else {
     189                addStatement(stmt);
     190            }
     191            stmt = next;
     192        }
     193    }
     194
     195protected:
     196
     197//    /** ------------------------------------------------------------------------------------------------------------- *
     198//     * @brief addUsageInformation
     199//     *
     200//     * Populate G with the user information of each statement so that we can determine whether it'll be cost effective
     201//     * to distribute an operation.
     202//     ** ------------------------------------------------------------------------------------------------------------- */
     203//    void addUsageInformation() {
     204//        for (const Vertex u : make_iterator_range(vertices(G))) {
     205//            PabloAST * expr; TypeId typeId;
     206//            std::tie(expr, typeId) = G[u];
     207//            if (LLVM_LIKELY(typeId != TypeId::Var)) {
     208//                for (PabloAST * user : expr->users()) {
     209//                    add_edge(u, addExpression(user), user, G);
     210//                }
     211//            }
     212//        }
     213//    }
     214
     215    /** ------------------------------------------------------------------------------------------------------------- *
     216     * @brief applyAssociativeIdentityAnnulmentLaws
     217     ** ------------------------------------------------------------------------------------------------------------- */
     218    bool applyAssociativeIdentityAnnulmentLaws() {
     219
     220        bool modified = false;
     221
     222        std::function<void(const Vertex)> apply = [&](const Vertex u) {
     223            PabloAST * expr; TypeId typeId;
     224            std::tie(expr, typeId) = G[u];
     225
     226
     227
     228            if (LLVM_UNLIKELY(typeId == TypeId::Zeroes || typeId == TypeId::Ones)) {
     229repeat:         for (auto e : make_iterator_range(out_edges(u, G))) {
     230                    const auto v = target(e, G);
     231                    const auto targetTypeId = getType(v);
     232                    if (LLVM_UNLIKELY(isAssociative(targetTypeId))) {
     233                        if (isIdentityRelation(typeId, targetTypeId)) {
     234                            remove_edge(e, G);
     235                        } else {
     236                            setType(v, typeId == TypeId::And ? TypeId::Zeroes : TypeId::Ones);
     237                            clear_in_edges(v, G);
     238                            apply(v);
     239                        }
     240                        modified = true;
     241                        goto repeat;
     242                    }
     243                }
     244            } else if (isAssociative(typeId)) {
     245
     246                bool contractable = true;
     247                // an associative operation with only one element is always equivalent to the element
     248                if (LLVM_LIKELY(in_degree(u, G) != 1)) {
     249                    for (auto e : make_iterator_range(out_edges(u, G))) {
     250                        if (LLVM_LIKELY(typeId != getType(target(e, G)))) {
     251                            contractable = false;
     252                            break;
     253                        }
     254                    }
     255                }
     256                if (LLVM_UNLIKELY(contractable)) {
     257                    for (auto ei : make_iterator_range(in_edges(u, G))) {
     258                        for (auto ej : make_iterator_range(out_edges(u, G))) {
     259                            add_edge(source(ei, G), target(ej, G), expr, G);
     260                        }
     261                    }
     262                    clear_vertex(u, G);
     263                    setType(u, TypeId::Var);
     264                    modified = true;
     265                }
     266            }
     267        };
     268
     269        // note: calls "apply" on each vertex in reverse topological order
     270        topological_sort(G, boost::make_function_output_iterator(apply));
     271
     272        return modified;
     273    }
     274
     275    /** ------------------------------------------------------------------------------------------------------------- *
     276     * @brief applyAbsorbtionComplementIdempotentLaws
     277     ** ------------------------------------------------------------------------------------------------------------- */
     278    bool applyAbsorbtionComplementIdempotentLaws() {
     279        using in_edge_iterator = graph_traits<Graph>::in_edge_iterator;
     280        bool modified = false;
     281        for (const Vertex u : make_iterator_range(vertices(G))) {
     282            const TypeId typeId = getType(u);
     283            if (isDistributive(typeId)) {
     284restart_loop:   in_edge_iterator ei_begin, ei_end;
     285                std::tie(ei_begin, ei_end) = in_edges(u, G);
     286                for (auto ei = ei_begin; ei != ei_end; ++ei) {
     287                    const auto v = source(*ei, G);
     288                    const auto innerTypeId = getType(v);
     289                    if (isDistributive(innerTypeId) || innerTypeId == TypeId::Not) {
     290                        in_edge_iterator ek_begin, ek_end;
     291                        std::tie(ek_begin, ek_end) = in_edges(v, G);
     292                        for (auto ej = ei_begin; ej != ei_end; ++ej) {
     293                            for (auto ek = ek_begin; ek != ek_end; ++ek) {
     294                                if (LLVM_UNLIKELY(source(*ej, G) == source(*ek, G))) {
     295                                    if (LLVM_UNLIKELY(innerTypeId == TypeId::Not)) {
     296                                        // complement
     297                                        setType(u, typeId == TypeId::And ? TypeId::Zeroes : TypeId::Ones);
     298                                        clear_in_edges(u, G);
     299                                        goto abort_loop;
     300                                    } else {
     301                                        if (LLVM_LIKELY(innerTypeId != typeId)) {
     302                                            // idempotent
     303                                            remove_edge(*ei, G);
     304                                        } else {
     305                                            // absorbtion
     306                                            remove_edge(*ej, G);
     307                                        }
     308                                        modified = true;
     309                                        // this seldom occurs so if it does, just restart the process rather than
     310                                        // trying to keep the iterators valid.
     311                                        goto restart_loop;
     312                                    }
     313                                }
     314                            }
     315                        }
     316                    }
     317                }
     318            }
     319            abort_loop:;
     320        }
     321        return modified;
     322    }
     323
     324
     325    /** ------------------------------------------------------------------------------------------------------------- *
     326     * @brief contractGraph
     327     *
     328     * This function scans through a scope block and computes a DAG G in which any sequences of AND, OR or XOR functions
     329     * are "flattened" (i.e., allowed to have any number of inputs.)
     330     ** ------------------------------------------------------------------------------------------------------------- */
     331    bool contractGraph() {
     332        bool modified = false;
     333        bool alreadyGoneOnce = false;
     334        for (;;) {
     335            if (applyAssociativeIdentityAnnulmentLaws()) {
     336                modified = true;
     337            } else if (alreadyGoneOnce) {
     338                break;
     339            }
     340            if (applyAbsorbtionComplementIdempotentLaws()) {
     341                modified = true;
     342            } else { // if (alreadyGoneOnce) {
     343                break;
     344            }
     345            alreadyGoneOnce = true;
     346        }
     347        return modified;
     348    }
     349
     350    /** ------------------------------------------------------------------------------------------------------------- *
     351     * @brief addVertex
     352     ** ------------------------------------------------------------------------------------------------------------- */
     353    DistributionVertex addVertex(const Vertex u) {
     354        const auto f = D.find(u);
     355        if (LLVM_LIKELY(f != D.end())) {
     356            return f->second;
     357        }
     358        const auto v = add_vertex(u, H);
     359        D.emplace(u, v);
     360        return v;
     361    }
     362
     363    /** ------------------------------------------------------------------------------------------------------------- *
     364     * @brief generateDistributionGraph
     365     *
     366     * Let (u) ∈ V(G) be a conjunction ∧ or disjunction √ and (v) be a ∧ or √ and the opposite type of (u). If (u,v) ∈
     367     * 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
     368     * (w,v) ∈ E(G) to the distribution graph H as well as the edges indicating their relationships within G.
     369     *
     370     *                  (?) (?) (?) <-- w1, w2, ...
     371     *                     \ | /
     372     *                      (v)   <-- v
     373     *                     /   \
     374     *            u --> (∧)     (∧)
     375     *
     376     ** ------------------------------------------------------------------------------------------------------------- */
     377    void generateDistributionGraph() {
     378
     379        assert (D.empty());
     380
     381        flat_set<Vertex> distributable;
     382        flat_set<Vertex> observed;
     383
     384        for (const Vertex u : make_iterator_range(vertices(G))) {
     385            const TypeId outerTypeId = getType(u);
     386            if (isDistributive(outerTypeId)) {
     387                const TypeId innerTypeId = oppositeTypeId(outerTypeId);
     388                for (auto e : make_iterator_range(in_edges(u, G))) {
     389                    const Vertex v = source(e, G);
     390                    if (LLVM_UNLIKELY(std::get<1>(G[v]) == innerTypeId)) {
     391                        bool beneficial = true;
     392                        for (const auto e : make_iterator_range(out_edges(v, G))) {
     393                            if (std::get<1>(G[target(e, G)]) != outerTypeId) {
     394                                beneficial = false;
     395                                break;
     396                            }
     397                        }
     398                        if (beneficial) {
     399                            distributable.insert(v);
     400                        }
     401                    }
     402                }
     403                if (LLVM_LIKELY(distributable.size() > 1)) {
     404                    for (const Vertex v : distributable) {
     405                        for (auto e : make_iterator_range(in_edges(v, G))) {
     406                            observed.insert(source(e, G));
     407                        }
     408                    }
     409                    for (const Vertex w : observed) {
     410                        for (auto e : make_iterator_range(out_edges(w, G))) {
     411                            const Vertex v = target(e, G);
     412                            if (distributable.count(v)) {
     413                                const Vertex y = addVertex(v);
     414                                boost::add_edge(y, addVertex(u), H);
     415                                boost::add_edge(addVertex(w), y, H);
     416                            }
     417                        }
     418                    }
     419                    observed.clear();
     420                }
     421                distributable.clear();
     422            }
     423        }
     424
     425        D.clear();
     426    }
     427
     428
     429    /** ------------------------------------------------------------------------------------------------------------- *
     430     * @brief redistributeAST
     431     *
     432     * Apply the distribution law to reduce computations whenever possible.
     433     ** ------------------------------------------------------------------------------------------------------------- */
     434    bool simplifyGraph() {
     435
     436        VertexSet sinks;
     437
     438        bool modified = false;
     439
     440        for (;;) {
     441
     442            assert (num_vertices(H) == 0 && num_edges(H) == 0);
     443
     444            if (contractGraph()) {
     445                modified = true;
     446            }
     447
     448            generateDistributionGraph();
     449
     450            // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
     451            if (num_vertices(H) == 0) {
     452                break;
     453            }
     454
     455            for (const Vertex u : make_iterator_range(vertices(H))) {
     456                if (out_degree(u, H) == 0 && in_degree(u, H) != 0) {
     457                    sinks.push_back(u);
     458                }
     459            }
     460            std::sort(sinks.begin(), sinks.end());
     461
     462            bool done = true;
     463
     464            const auto lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(sinks)), 1);
     465
     466            for (auto & lower : lowerSet) {
     467                const auto upperSet = independentCliqueSets<0>(enumerateBicliques(std::get<1>(lower)), 2);
     468                for (const auto & upper : upperSet) {
     469
     470                    const auto & sources = std::get<1>(upper);
     471                    const auto & intermediary = std::get<0>(upper);
     472                    const auto & sinks = std::get<0>(lower);
     473
     474                    const auto outerTypeId = getType(H[sinks.front()]);
     475                    const auto innerTypeId = oppositeTypeId(outerTypeId);
     476
     477                    // Update G to match the desired change
     478                    const auto x = makeVertex(outerTypeId);
     479                    const auto y = makeVertex(innerTypeId);
     480
     481                    for (const auto i : intermediary) {
     482                        const auto u = H[i];
     483                        assert (getType(u) == innerTypeId);
     484                        for (const Vertex t : sinks) {
     485                            assert (getType(H[t]) == outerTypeId);
     486                            remove_edge(u, H[t], G);
     487                        }
     488                        add_edge(u, x, nullptr, G);
     489                    }
     490
     491                    for (const Vertex s : sources) {
     492                        const auto u = H[s];
     493                        for (const Vertex i : intermediary) {
     494                            remove_edge(u, H[i], G);
     495                        }
     496                        add_edge(u, y, nullptr, G);
     497                    }
     498                    add_edge(x, y, nullptr, G);
     499
     500                    for (const Vertex t : sinks) {
     501                        const auto v = H[t];
     502                        add_edge(y, v, std::get<0>(G[v]), G);
     503                    }
     504
     505                    done = false;
     506                }
     507            }
     508
     509            H.clear();
     510
     511            if (done) {
     512                break;
     513            } else {
     514                sinks.clear();
     515                modified = true;
     516            }
     517        }
     518
     519        assert (num_vertices(H) == 0 && num_edges(H) == 0);
     520
     521        return modified;
     522    }
     523
     524
     525    /** ------------------------------------------------------------------------------------------------------------- *
     526     * @brief enumerateBicliques
     527     *
     528     * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
     529     * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
     530     * bipartition A and their adjacencies to be in B.
     531      ** ------------------------------------------------------------------------------------------------------------- */
     532
     533    BicliqueSet enumerateBicliques(const VertexSet & A) {
     534        using IntersectionSets = std::set<VertexSet>;
     535
     536        IntersectionSets B1;
     537        for (auto u : A) {
     538            if (in_degree(u, H) > 0) {
     539                VertexSet incomingAdjacencies;
     540                incomingAdjacencies.reserve(in_degree(u, H));
     541                for (auto e : make_iterator_range(in_edges(u, H))) {
     542                    incomingAdjacencies.push_back(source(e, H));
     543                }
     544                std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
     545                B1.insert(std::move(incomingAdjacencies));
     546            }
     547        }
     548
     549        IntersectionSets B(B1);
     550
     551        IntersectionSets Bi;
     552
     553        VertexSet clique;
     554        for (auto i = B1.begin(); i != B1.end(); ++i) {
     555            for (auto j = i; ++j != B1.end(); ) {
     556                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
     557                if (clique.size() > 0) {
     558                    if (B.count(clique) == 0) {
     559                        Bi.insert(clique);
     560                    }
     561                    clique.clear();
     562                }
     563            }
     564        }
     565
     566        for (;;) {
     567            if (Bi.empty()) {
     568                break;
     569            }
     570            B.insert(Bi.begin(), Bi.end());
     571            IntersectionSets Bk;
     572            for (auto i = B1.begin(); i != B1.end(); ++i) {
     573                for (auto j = Bi.begin(); j != Bi.end(); ++j) {
     574                    std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
     575                    if (clique.size() > 0) {
     576                        if (B.count(clique) == 0) {
     577                            Bk.insert(clique);
     578                        }
     579                        clique.clear();
     580                    }
     581                }
     582            }
     583            Bi.swap(Bk);
     584        }
     585
     586        BicliqueSet cliques;
     587        cliques.reserve(B.size());
     588        for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
     589            VertexSet Ai(A);
     590            for (const Vertex u : *Bi) {
     591                VertexSet Aj;
     592                Aj.reserve(out_degree(u, H));
     593                for (auto e : make_iterator_range(out_edges(u, H))) {
     594                    Aj.push_back(target(e, H));
     595                }
     596                std::sort(Aj.begin(), Aj.end());
     597                VertexSet Ak;
     598                Ak.reserve(std::min(Ai.size(), Aj.size()));
     599                std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
     600                Ai.swap(Ak);
     601            }
     602            assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
     603            cliques.emplace_back(std::move(Ai), std::move(*Bi));
     604        }
     605        return std::move(cliques);
     606    }
     607
     608
     609    /** ------------------------------------------------------------------------------------------------------------- *
     610     * @brief independentCliqueSets
     611     ** ------------------------------------------------------------------------------------------------------------- */
     612    template <unsigned side>
     613    BicliqueSet && independentCliqueSets(BicliqueSet && cliques, const unsigned minimum) {
     614
     615
     616        const auto l = cliques.size();
     617        IndependentSetGraph I(l);
     618
     619        // Initialize our weights
    87620        for (unsigned i = 0; i != l; ++i) {
    88             if (I[i] > w) {
    89                 w = I[i];
    90                 u = i;
    91             }
    92         }
    93         if (w < (uppsetSet ? 2 : 1)) break;
    94         selected.push_back(u);
    95         I[u] = 0;
    96         for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
    97             I[v] = 0;
    98         }
    99     }
    100 
    101     // Sort the selected list and then remove the unselected cliques
    102     std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
    103     auto end = bicliques.end();
    104     for (const unsigned offset : selected) {
    105         end = bicliques.erase(bicliques.begin() + offset + 1, end) - 1;
    106     }
    107     bicliques.erase(bicliques.begin(), end);
    108 
    109     return std::move(bicliques);
    110 }
    111 
    112 /** ------------------------------------------------------------------------------------------------------------- *
    113  * @brief enumerateBicliques
    114  *
    115  * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
    116  * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
    117  * bipartition A and their adjacencies to be in B.
    118   ** ------------------------------------------------------------------------------------------------------------- */
    119 static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A, const unsigned min) {
    120     using IntersectionSets = std::set<VertexSet>;
    121 
    122     IntersectionSets B1;
    123     VertexSet tmp;
    124     for (auto u : A) {
    125         if (in_degree(u, G) > 0) {
    126             tmp.reserve(in_degree(u, G));
    127             for (auto e : make_iterator_range(in_edges(u, G))) {
    128                 tmp.push_back(source(e, G));
    129             }
    130             if (tmp.size() >= min) {
    131                 std::sort(tmp.begin(), tmp.end());
    132                 B1.emplace(tmp.begin(), tmp.end());
    133             }
    134             tmp.clear();
    135         }
    136     }
    137 
    138     IntersectionSets B(B1);
    139 
    140     IntersectionSets Bi;
    141     for (auto i = B1.begin(); i != B1.end(); ++i) {
    142         for (auto j = i; ++j != B1.end(); ) {
    143             std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
    144             if (tmp.size() >= min) {
    145                 if (B.count(tmp) == 0) {
    146                     Bi.emplace(tmp.begin(), tmp.end());
    147                 }
    148             }
    149             tmp.clear();
    150         }
    151     }
    152 
    153     for (;;) {
    154         if (Bi.empty()) {
    155             break;
    156         }
    157         B.insert(Bi.begin(), Bi.end());
    158         IntersectionSets Bk;
    159         for (auto i = B1.begin(); i != B1.end(); ++i) {
    160             for (auto j = Bi.begin(); j != Bi.end(); ++j) {
    161                 std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
    162                 if (tmp.size() >= min) {
    163                     if (B.count(tmp) == 0) {
    164                         Bk.emplace(tmp.begin(), tmp.end());
    165                     }
    166                 }
    167                 tmp.clear();
    168             }
    169         }
    170         Bi.swap(Bk);
    171     }
    172 
    173     BicliqueSet cliques;
    174     cliques.reserve(B.size());
    175     for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
    176         assert (Bi->size() >= min);
    177         VertexSet Ai(A);
    178         for (const Vertex u : *Bi) {
    179             VertexSet Aj;
    180             Aj.reserve(out_degree(u, G));
    181             for (auto e : make_iterator_range(out_edges(u, G))) {
    182                 Aj.push_back(target(e, G));
    183             }
    184             std::sort(Aj.begin(), Aj.end());
    185             VertexSet Ak;
    186             Ak.reserve(std::min(Ai.size(), Aj.size()));
    187             std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
    188             Ai.swap(Ak);
    189         }
    190         assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
    191         cliques.emplace_back(std::move(Ai), std::move(*Bi));
    192     }
    193     return std::move(cliques);
    194 }
    195 
    196 /** ------------------------------------------------------------------------------------------------------------- *
    197  * @brief removeUnhelpfulBicliques
    198  *
    199  * An intermediary vertex could have more than one outgoing edge but if any that are not directed to vertices in
    200  * the lower biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if
    201  * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
    202  ** ------------------------------------------------------------------------------------------------------------- */
    203 static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, const Graph & G) {
    204     for (auto ci = cliques.begin(); ci != cliques.end(); ) {
    205         const auto cardinalityA = std::get<0>(*ci).size();
    206         VertexSet & B = std::get<1>(*ci);
    207         for (auto bi = B.begin(); bi != B.end(); ) {
    208             if (G[*bi]->getNumUses() == cardinalityA) {
    209                 ++bi;
     621            I[i] = std::pow(std::get<side>(cliques[i]).size(), 2);
     622        }
     623
     624        // Determine our constraints
     625        for (unsigned i = 0; i != l; ++i) {
     626            for (unsigned j = i + 1; j != l; ++j) {
     627                if (intersects(std::get<side>(cliques[i]), std::get<side>(cliques[j]))) {
     628                    boost::add_edge(i, j, I);
     629                }
     630            }
     631        }
     632
     633        // Use the greedy algorithm to choose our independent set
     634        VertexSet selected;
     635        for (;;) {
     636            unsigned w = 0;
     637            Vertex u = 0;
     638            for (unsigned i = 0; i != l; ++i) {
     639                if (I[i] > w) {
     640                    w = I[i];
     641                    u = i;
     642                }
     643            }
     644            if (w < minimum) break;
     645            selected.push_back(u);
     646            I[u] = 0;
     647            for (auto v : make_iterator_range(adjacent_vertices(u, I))) {
     648                I[v] = 0;
     649            }
     650        }
     651
     652        // Sort the selected list and then remove the unselected cliques
     653        std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
     654        auto end = cliques.end();
     655        for (const unsigned offset : selected) {
     656            end = cliques.erase(cliques.begin() + offset + 1, end) - 1;
     657        }
     658        cliques.erase(cliques.begin(), end);
     659
     660        return std::move(cliques);
     661    }
     662
     663    /** ------------------------------------------------------------------------------------------------------------- *
     664     * @brief removeUnhelpfulBicliques
     665     *
     666     * An intermediary vertex could have more than one outgoing edge but if any that are not directed to vertices in
     667     * the lower biclique, we'll need to compute that specific value anyway. Remove them from the clique set and if
     668     * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
     669     ** ------------------------------------------------------------------------------------------------------------- */
     670    BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques) {
     671        for (auto ci = cliques.begin(); ci != cliques.end(); ) {
     672            const auto cardinalityA = std::get<0>(*ci).size();
     673            VertexSet & B = std::get<1>(*ci);
     674            for (auto bi = B.begin(); bi != B.end(); ) {
     675                if (out_degree(H[*bi], G) == cardinalityA) {
     676                    ++bi;
     677                } else {
     678                    bi = B.erase(bi);
     679                }
     680            }
     681            if (B.size() > 1) {
     682                ++ci;
    210683            } else {
    211                 bi = B.erase(bi);
    212             }
    213         }
    214         if (B.size() > 1) {
    215             ++ci;
    216         } else {
    217             ci = cliques.erase(ci);
    218         }
    219     }
    220     return std::move(cliques);
    221 }
    222 
    223 /** ------------------------------------------------------------------------------------------------------------- *
    224  * @brief safeDistributionSets
    225  ** ------------------------------------------------------------------------------------------------------------- */
    226 inline static DistributionSets safeDistributionSets(const Graph & G, const VertexSet & A) {
    227     DistributionSets T;
    228     BicliqueSet lowerSet = independentCliqueSets(removeUnhelpfulBicliques(enumerateBicliques(G, A, 1), G), false);
    229     for (Biclique & lower : lowerSet) {
    230         BicliqueSet upperSet = independentCliqueSets(enumerateBicliques(G, std::get<1>(lower), 2), true);
    231         for (Biclique & upper : upperSet) {
    232             T.emplace_back(std::move(std::get<1>(upper)), std::move(std::get<0>(upper)), std::get<0>(lower));
    233         }
    234     }
    235     return std::move(T);
    236 }
    237 
    238 /** ------------------------------------------------------------------------------------------------------------- *
    239  * @brief scopeDepthOf
    240  ** ------------------------------------------------------------------------------------------------------------- */
    241 inline unsigned scopeDepthOf(const PabloBlock * block) {
    242     unsigned depth = 0;
    243     for (; block; ++depth, block = block->getPredecessor());
    244     return depth;
    245 }
    246 
    247 /** ------------------------------------------------------------------------------------------------------------- *
    248  * @brief findInsertionPoint
    249  ** ------------------------------------------------------------------------------------------------------------- */
    250 inline PabloBlock * findInsertionPoint(const VertexSet & users, const Graph & G) {
    251     std::vector<PabloBlock *> scopes(0);
    252     scopes.reserve(users.size());
    253     for (Vertex u : users) {
    254         PabloBlock * const scope = cast<Statement>(G[u])->getParent(); assert (scope);
    255         if (std::find(scopes.begin(), scopes.end(), scope) == scopes.end()) {
    256             scopes.push_back(scope);
    257         }
    258     }
    259     while (scopes.size() > 1) {
    260         // Find the LCA of both scopes then add the LCA back to the list of scopes.
    261         PabloBlock * scope1 = scopes.back();
    262         scopes.pop_back();
    263         PabloBlock * scope2 = scopes.back();
    264         scopes.pop_back();
    265         assert (scope1 != scope2);
    266         unsigned depth1 = scopeDepthOf(scope1);
    267         unsigned depth2 = scopeDepthOf(scope2);
    268         // If one of these scopes is nested deeper than the other, scan upwards through
    269         // the scope tree until both scopes are at the same depth.
    270         while (depth1 > depth2) {
    271             scope1 = scope1->getPredecessor();
    272             --depth1;
    273         }
    274         while (depth1 < depth2) {
    275             scope2 = scope2->getPredecessor();
    276             --depth2;
    277         }
    278         assert (depth1 == depth2);
    279         // Then iteratively step backwards until we find a matching scopes; this must be
    280         // the LCA of our original pair.
    281         while (scope1 != scope2) {
    282             scope1 = scope1->getPredecessor();
    283             scope2 = scope2->getPredecessor();
    284         }
    285         assert (scope1 && scope2);
    286         if (std::find(scopes.begin(), scopes.end(), scope1) == scopes.end()) {
    287             scopes.push_back(scope1);
    288         }
    289     }
    290     assert (scopes.size() == 1);
    291     PabloBlock * const root = scopes.front();
    292     // Now that we know the common scope of these users, test which statement is the first to require it.
    293     flat_set<Statement *> usages;
    294     usages.reserve(users.size());
    295     for (Vertex u : users) {
    296         Statement * user = cast<Statement>(G[u]);
    297         PabloBlock * scope = user->getParent();
    298         while (scope != root) {
    299             assert (scope);
    300             user = scope->getBranch();
    301             scope = scope->getPredecessor();
    302         }
    303         usages.insert(user);
    304     }
    305     Statement * ip = nullptr;
    306     for (Statement * stmt : *root) {
    307         if (usages.count(stmt)) {
    308             ip = stmt->getPrevNode();
    309             break;
    310         }
    311     }
    312     assert (ip);
    313     root->setInsertPoint(ip);
    314     return root;
    315 }
    316 
    317 /** ------------------------------------------------------------------------------------------------------------- *
    318  * @brief computeDistributionGraph
    319  ** ------------------------------------------------------------------------------------------------------------- */
    320 static inline void computeDistributionGraph(Variadic * const expr, Graph & G, VertexSet & A) {
    321 
    322     TypeId outerTypeId = expr->getClassTypeId();
    323     TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
    324 
    325     assert (isa<And>(expr) || isa<Or>(expr));
    326 
    327     Map M;
    328     for (unsigned i = 0; i != expr->getNumOperands(); ++i) {
    329         PabloAST * const op = expr->getOperand(i);
    330         if (op->getClassTypeId() == innerTypeId) {
    331             bool distributable = true;
    332             for (PabloAST * user : op->users()) {
    333                 // Early check to see whether it'd be beneficial to distribute it. If this fails, we'd have
    334                 // to compute the operand's value anyway, so just ignore this operand.
    335                 if (user->getClassTypeId() != outerTypeId) {
    336                     distributable = false;
    337                     break;
    338                 }
    339             }
    340             if (distributable) {
    341                 const Vertex u = add_vertex(op, G);
    342                 for (PabloAST * user : op->users()) {
    343                     const auto f = M.find(user);
    344                     Vertex v = 0;
    345                     if (LLVM_LIKELY(f != M.end())) {
    346                         v = f->second;
    347                     } else {
    348                         v = add_vertex(user, G);
    349                         M.emplace(user, v);
    350                         A.push_back(v);
    351                     }
    352                     add_edge(u, v, G);
    353                 }
    354                 for (PabloAST * input : *cast<Variadic>(op)) {
    355                     const auto f = M.find(input);
    356                     Vertex v = 0;
    357                     if (f != M.end()) {
    358                         v = f->second;
    359                     } else {
    360                         v = add_vertex(input, G);
    361                         M.emplace(input, v);
    362                     }
    363                     add_edge(v, u, G);
    364                 }
    365             }
    366         }
    367     }
    368 }
    369 
    370 /** ------------------------------------------------------------------------------------------------------------- *
    371  * @brief distribute
    372  *
    373  * Based on the knowledge that:
    374  *
    375  *   (P ∧ Q) √ (P ∧ R) ⇔ P ∧ (Q √ R) and (P √ Q) ∧ (P √ R) ⇔ P √ (Q ∧ R)
    376  *
    377  * Try to eliminate some of the unnecessary operations from the current Variadic expression.
    378  ** ------------------------------------------------------------------------------------------------------------- */
    379 inline void DistributivePass::distribute(Variadic * const var) {
    380 
    381 
    382 
    383     assert (isa<And>(var) || isa<Or>(var));
     684                ci = cliques.erase(ci);
     685            }
     686        }
     687        return std::move(cliques);
     688    }
     689
     690    /** ------------------------------------------------------------------------------------------------------------- *
     691     * @brief addTemporary
     692     ** ------------------------------------------------------------------------------------------------------------- */
     693    Vertex makeVertex(const TypeId typeId, PabloAST * const expr = nullptr) {
     694        return add_vertex(std::make_pair(expr, typeId), G);
     695    }
     696
     697    /** ------------------------------------------------------------------------------------------------------------- *
     698     * @brief addExpression
     699     ** ------------------------------------------------------------------------------------------------------------- */
     700    Vertex addExpression(PabloAST * const expr) {
     701        const auto f = M.find(expr);
     702        if (LLVM_LIKELY(f != M.end())) {
     703            return f->second;
     704        }
     705        TypeId typeId = TypeId::Var;
     706        if (isa<Zeroes>(expr)) {
     707            typeId = TypeId::Zeroes;
     708        } else if (isa<Ones>(expr)) {
     709            typeId = TypeId::Ones;
     710        }
     711        const auto u = makeVertex(typeId, expr);
     712        M.emplace(expr, u);
     713        return u;
     714    }
     715
     716    /** ------------------------------------------------------------------------------------------------------------- *
     717     * @brief addStatement
     718     ** ------------------------------------------------------------------------------------------------------------- */
     719    void addStatement(Statement * const stmt) {
     720        assert (M.count(stmt) == 0);
     721        const auto typeId = stmt->getClassTypeId();
     722        const auto u = makeVertex(typeId, stmt);
     723        M.emplace(stmt, u);
     724        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     725            PabloAST * const op = stmt->getOperand(i);
     726            if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
     727                continue;
     728            }
     729            const auto v = addExpression(op);
     730            add_edge(v, u, op, G);
     731            if (LLVM_UNLIKELY(isa<Not>(op))) {
     732                PabloAST * const negated = cast<Not>(op)->getExpr();
     733                add_edge(addExpression(negated), v, negated, G);
     734            }
     735        }
     736    }
     737
     738    /** ------------------------------------------------------------------------------------------------------------- *
     739     * @brief intersects
     740     ** ------------------------------------------------------------------------------------------------------------- */
     741    template <class Type>
     742    inline bool intersects(Type & A, Type & B) {
     743        auto first1 = A.begin(), last1 = A.end();
     744        auto first2 = B.begin(), last2 = B.end();
     745        while (first1 != last1 && first2 != last2) {
     746            if (*first1 < *first2) {
     747                ++first1;
     748            } else if (*first2 < *first1) {
     749                ++first2;
     750            } else {
     751                return true;
     752            }
     753        }
     754        return false;
     755    }
     756
     757    TypeId getType(const Vertex u) {
     758        return std::get<1>(G[u]);
     759    }
     760
     761    void setType(const Vertex u, const TypeId typeId) {
     762        std::get<1>(G[u]) = typeId;
     763    }
     764
     765    static bool isIdentityRelation(const TypeId a, const TypeId b) {
     766        return !((a == TypeId::Zeroes) ^ (b == TypeId::Or));
     767    }
     768
     769    static bool isAssociative(const TypeId typeId) {
     770        return (isDistributive(typeId) || typeId == TypeId::Xor);
     771    }
     772
     773    static bool isDistributive(const TypeId typeId) {
     774        return (typeId == TypeId::And || typeId == TypeId::Or);
     775    }
     776
     777    static TypeId oppositeTypeId(const TypeId typeId) {
     778        assert (isDistributive(typeId));
     779        return (typeId == TypeId::And) ? TypeId::Or : TypeId::And;
     780    }
     781
     782    void add_edge(const Vertex u, const Vertex v, PabloAST * const value, Graph & G) {
     783        G[std::get<0>(boost::add_edge(u, v, G))] = value;
     784    }
     785
     786private:
    384787
    385788    Graph G;
    386     VertexSet A;
    387 
    388     std::vector<Variadic *> Q = {var};
    389 
    390     while (!Q.empty()) {
    391         Variadic * expr = CanonicalizeDFG::canonicalize(Q.back()); Q.pop_back();
    392         PabloAST * const replacement = Simplifier::fold(expr, expr->getParent());
    393         if (LLVM_UNLIKELY(replacement != nullptr)) {
    394             expr->replaceWith(replacement, true, true);
    395             if (LLVM_UNLIKELY(isa<Variadic>(replacement))) {
    396                 Q.push_back(cast<Variadic>(replacement));
    397             }
    398             continue;
    399         }
    400 
    401         if (LLVM_LIKELY(isa<And>(expr) || isa<Or>(expr))) {
    402 
    403             computeDistributionGraph(expr, G, A);
    404 
    405             // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
    406             if (num_vertices(G) == 0) {
    407                 assert (A.empty());
    408                 continue;
    409             }
    410 
    411             const auto S = safeDistributionSets(G, A);
    412             if (S.empty()) {
    413                 G.clear();
    414                 A.clear();
    415                 continue;
    416             }
    417 
    418             Q.push_back(expr);
    419 
    420             for (const DistributionSet & set : S) {
    421 
    422                 // Each distribution tuple consists of the sources, intermediary, and sink nodes.
    423                 const VertexSet & sources = std::get<0>(set);
    424                 assert (sources.size() > 0);
    425                 const VertexSet & intermediary = std::get<1>(set);
    426                 assert (intermediary.size() > 1);
    427                 const VertexSet & sinks = std::get<2>(set);
    428                 assert (sinks.size() > 0);
    429 
    430                 for (const Vertex u : intermediary) {
    431                     for (const Vertex v : sources) {
    432                         cast<Variadic>(G[u])->deleteOperand(G[v]);
    433                     }
    434                 }
    435                 for (const Vertex u : sinks) {
    436                     for (const Vertex v : intermediary) {
    437                         cast<Variadic>(G[u])->deleteOperand(G[v]);
    438                     }
    439                 }
    440 
    441                 PabloBlock * const block = findInsertionPoint(sinks, G);
    442                 Variadic * innerOp = nullptr;
    443                 Variadic * outerOp = nullptr;
    444                 if (isa<And>(expr)) {
    445                     outerOp = block->createAnd(intermediary.size());
    446                     innerOp = block->createOr(sources.size() + 1);
    447                 } else {
    448                     outerOp = block->createOr(intermediary.size());
    449                     innerOp = block->createAnd(sources.size() + 1);
    450                 }
    451                 for (const Vertex v : intermediary) {
    452                     outerOp->addOperand(G[v]);
    453                 }
    454                 for (const Vertex v : sources) {
    455                     innerOp->addOperand(G[v]);
    456                 }
    457                 for (const Vertex u : sinks) {
    458                     cast<Variadic>(G[u])->addOperand(innerOp);
    459                 }
    460                 innerOp->addOperand(outerOp);
    461                 // Push our newly constructed ops into the Q
    462                 Q.push_back(innerOp);
    463                 Q.push_back(outerOp);
    464 
    465                 unmodified = false;
    466             }
    467 
    468             G.clear();
    469             A.clear();
    470         }
    471     }
    472 
    473 }
    474 
    475 /** ------------------------------------------------------------------------------------------------------------- *
    476  * @brief distribute
    477  ** ------------------------------------------------------------------------------------------------------------- */
    478 void DistributivePass::distribute(PabloBlock * const block) {
    479     Statement * stmt = block->front();
    480     while (stmt) {
    481         Statement * next = stmt->getNextNode();
    482         if (isa<If>(stmt) || isa<While>(stmt)) {
    483             distribute(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    484         } else if (isa<And>(stmt) || isa<Or>(stmt)) {
    485             distribute(cast<Variadic>(stmt));
    486         }
    487         stmt = next;
    488     }
    489 }
     789    flat_map<pablo::PabloAST *, Vertex> M;
     790
     791    DistributionGraph H;
     792    flat_map<Vertex, DistributionVertex> D;
     793
     794};
    490795
    491796/** ------------------------------------------------------------------------------------------------------------- *
    492797 * @brief optimize
    493798 ** ------------------------------------------------------------------------------------------------------------- */
    494 bool DistributivePass::optimize(PabloFunction & function) {
    495     DistributivePass dp;
    496     unsigned rounds = 0;
    497     for (;;) {
    498         dp.unmodified = true;
    499         dp.distribute(function.getEntryBlock());
    500         if (dp.unmodified) {
    501             break;
    502         }
    503         ++rounds;
    504         #ifndef NDEBUG
    505         PabloVerifier::verify(function, "post-distribution");
    506         #endif
    507         Simplifier::optimize(function);
    508     }
    509     return rounds > 0;
     799bool DistributivePass::optimize(PabloKernel * const kernel) {
     800    PassContainer C;
     801    C.run(kernel->getEntryBlock());
     802    return true;
    510803}
    511804
    512 
    513805}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.h

    r4927 r5464  
    1 #ifndef DISTRIBUTIVEPASS_H
    2 #define DISTRIBUTIVEPASS_H
     1#ifndef PABLO_DISTRIBUTIVEPASS_H
     2#define PABLO_DISTRIBUTIVEPASS_H
    33
    44namespace pablo {
    55
    6 class PabloFunction;
    7 class PabloBlock;
    8 class Variadic;
     6class PabloKernel;
    97
    108class DistributivePass {
    119public:
    12     static bool optimize(PabloFunction & function);
    13 protected:
    14     void distribute(PabloBlock * const block);
    15     void distribute(Variadic * const var);
    16     DistributivePass() = default;
    17 private:
    18     bool unmodified;
     10    static bool optimize(pablo::PabloKernel * const kernel);
    1911};
    2012
  • icGREP/icgrep-devel/icgrep/pablo/pablo_kernel.cpp

    r5454 r5464  
    1414#include <llvm/IR/Module.h>
    1515
    16 using namespace pablo;
    1716using namespace kernel;
    1817using namespace parabix;
     
    2928    return false;
    3029}
     30
     31namespace pablo {
    3132
    3233Var * PabloKernel::getInputStreamVar(const std::string & name) {
     
    209210}
    210211
     212}
  • icGREP/icgrep-devel/icgrep/pablo/pablo_toolchain.cpp

    r5454 r5464  
    99#include <pablo/optimizers/pablo_simplifier.hpp>
    1010#include <pablo/optimizers/codemotionpass.h>
    11 #include <pablo/passes/flattenassociativedfg.h>
     11#include <pablo/optimizers/distributivepass.h>
    1212#include <pablo/passes/flattenif.hpp>
    13 #include <pablo/passes/factorizedfg.h>
    14 #ifdef ENABLE_MULTIPLEXING
    15 #include <pablo/optimizers/pablo_automultiplexing.hpp>
    16 #include <pablo/optimizers/pablo_bddminimization.h>
    17 #include <pablo/optimizers/booleanreassociationpass.h>
    18 #include <pablo/optimizers/distributivepass.h>
    19 #include <pablo/optimizers/schedulingprepass.h>
    20 #endif
    2113#include <pablo/analysis/pabloverifier.hpp>
    2214#include <pablo/printer_pablos.h>
     
    2416#include <llvm/Support/FileSystem.h>
    2517#include <llvm/Support/raw_ostream.h>
    26 #ifdef PRINT_TIMING_INFORMATION
    27 #include <hrtime.h>
    28 #endif
    29 
    3018
    3119using namespace llvm;
     
    4331DebugOptions(cl::values(clEnumVal(ShowPablo, "Print generated Pablo code"),
    4432                        clEnumVal(ShowOptimizedPablo, "Print optimizeed Pablo code"),
    45                         clEnumVal(ShowUnloweredPablo, "Print Pablo code prior to lowering."),
    4633                        clEnumVal(DumpTrace, "Generate dynamic traces of executed Pablo assignments."),
    4734                        clEnumValEnd), cl::cat(PabloOptions));
     
    5340    PabloOptimizationsOptions(cl::values(clEnumVal(DisableSimplification, "Disable Pablo Simplification pass (not recommended)"),
    5441                                         clEnumVal(DisableCodeMotion, "Moves statements into the innermost legal If-scope and moves invariants out of While-loops."),
    55 #ifdef ENABLE_MULTIPLEXING
    56                                          clEnumVal(EnableMultiplexing, "combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."),
    57                                          clEnumVal(EnableLowering, "coalesce associative functions prior to optimization passes."),
    58                                          clEnumVal(EnablePreDistribution, "apply distribution law optimization prior to multiplexing."),
    59                                          clEnumVal(EnablePostDistribution, "apply distribution law optimization after multiplexing."),
    60                                          clEnumVal(EnablePrePassScheduling, "apply pre-pass scheduling prior to LLVM IR generation."),
    61 #endif                                         
    62                             clEnumValEnd), cl::cat(PabloOptions));
     42                                         clEnumVal(EnableDistribution, "apply distribution law optimization."),
     43                                         clEnumValEnd), cl::cat(PabloOptions));
    6344
    6445bool DebugOptionIsSet(PabloDebugFlags flag) {return DebugOptions.isSet(flag);}
    6546   
    66 
    67 
    68 #ifdef PRINT_TIMING_INFORMATION
    69 #define READ_CYCLE_COUNTER(name) name = read_cycle_counter();
    70 #else
    71 #define READ_CYCLE_COUNTER(name)
    72 #endif
    73 
    74 #ifdef PRINT_TIMING_INFORMATION
    75 unsigned COUNT_STATEMENTS(const PabloKernel * const entry) {
    76     std::stack<const Statement *> scope;
    77     unsigned statements = 0;
    78     // Scan through and collect all the advances, scanthrus and matchstars ...
    79     for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
    80         while ( stmt ) {
    81             ++statements;
    82             if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    83                 // Set the next statement to be the first statement of the inner scope and push the
    84                 // next statement of the current statement into the scope stack.
    85                 const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    86                 scope.push(stmt->getNextNode());
    87                 stmt = nested->front();
    88                 assert (stmt);
    89                 continue;
    90             }
    91             stmt = stmt->getNextNode();
    92         }
    93         if (scope.empty()) {
    94             break;
    95         }
    96         stmt = scope.top();
    97         scope.pop();
    98     }
    99     return statements;
    100 }
    101 
    102 unsigned COUNT_ADVANCES(const PabloKernel * const entry) {
    103 
    104     std::stack<const Statement *> scope;
    105     unsigned advances = 0;
    106 
    107     // Scan through and collect all the advances, scanthrus and matchstars ...
    108     for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
    109         while ( stmt ) {
    110             if (isa<Advance>(stmt)) {
    111                 ++advances;
    112             }
    113             else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    114                 // Set the next statement to be the first statement of the inner scope and push the
    115                 // next statement of the current statement into the scope stack.
    116                 const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    117                 scope.push(stmt->getNextNode());
    118                 stmt = nested->front();
    119                 assert (stmt);
    120                 continue;
    121             }
    122             stmt = stmt->getNextNode();
    123         }
    124         if (scope.empty()) {
    125             break;
    126         }
    127         stmt = scope.top();
    128         scope.pop();
    129     }
    130     return advances;
    131 }
    132 
    133 using DistributionMap = boost::container::flat_map<unsigned, unsigned>;
    134 
    135 DistributionMap SUMMARIZE_VARIADIC_DISTRIBUTION(const PabloKernel * const entry) {
    136     std::stack<const Statement *> scope;
    137     DistributionMap distribution;
    138     // Scan through and collect all the advances, scanthrus and matchstars ...
    139     for (const Statement * stmt = entry->getEntryBlock()->front(); ; ) {
    140         while ( stmt ) {
    141             if (isa<Variadic>(stmt)) {
    142                 auto f = distribution.find(stmt->getNumOperands());
    143                 if (f == distribution.end()) {
    144                     distribution.emplace(stmt->getNumOperands(), 1);
    145                 } else {
    146                     f->second += 1;
    147                 }
    148             }
    149             else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    150                 // Set the next statement to be the first statement of the inner scope and push the
    151                 // next statement of the current statement into the scope stack.
    152                 const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    153                 scope.push(stmt->getNextNode());
    154                 stmt = nested->front();
    155                 assert (stmt);
    156                 continue;
    157             }
    158             stmt = stmt->getNextNode();
    159         }
    160         if (scope.empty()) {
    161             break;
    162         }
    163         stmt = scope.top();
    164         scope.pop();
    165     }
    166     return distribution;
    167 }
    168 #endif
    16947
    17048void pablo_function_passes(PabloKernel * kernel) {
     
    18159
    18260    // Scan through the pablo code and perform DCE and CSE
    183 
    184 #ifdef PRINT_TIMING_INFORMATION
    185     timestamp_t simplification_start = 0, simplification_end = 0;
    186     timestamp_t flattenif_start = 0, flattenif_end = 0;
    187     timestamp_t coalescing_start = 0, coalescing_end = 0;
    188     timestamp_t sinking_start = 0, sinking_end = 0;
    189     timestamp_t pre_distribution_start = 0, pre_distribution_end = 0;
    190     timestamp_t multiplexing_start = 0, multiplexing_end = 0;
    191     timestamp_t post_distribution_start = 0, post_distribution_end = 0;
    192     timestamp_t lowering_start = 0, lowering_end = 0;
    193     timestamp_t scheduling_start = 0, scheduling_end = 0;
    194     DistributionMap distribution;
    195     const timestamp_t optimization_start = read_cycle_counter();
    196 #endif
    19761    if (LLVM_LIKELY(!PabloOptimizationsOptions.isSet(DisableSimplification))) {
    198         READ_CYCLE_COUNTER(simplification_start);
    19962        Simplifier::optimize(kernel);
    200         READ_CYCLE_COUNTER(simplification_end);
    20163    }
    20264    if (Flatten){
    203         READ_CYCLE_COUNTER(flattenif_start);
    20465        FlattenIf::transform(kernel);
    205         READ_CYCLE_COUNTER(flattenif_end);
    20666    }
    207 #ifdef ENABLE_MULTIPLEXING
    208 //    if (PabloOptimizationsOptions.isSet(EnableLowering) || PabloOptimizationsOptions.isSet(EnablePreDistribution) || PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
    209 //        READ_CYCLE_COUNTER(coalescing_start);
    210 //        CanonicalizeDFG::transform(kernel);
    211 //        READ_CYCLE_COUNTER(coalescing_end);
    212 //    }
    213     if (PabloOptimizationsOptions.isSet(EnablePreDistribution)) {
    214         READ_CYCLE_COUNTER(pre_distribution_start);
    215         BooleanReassociationPass::optimize(kernel);
    216         READ_CYCLE_COUNTER(pre_distribution_end);
     67    if (LLVM_LIKELY(!PabloOptimizationsOptions.isSet(DisableCodeMotion))) {
     68        CodeMotionPass::optimize(kernel);
    21769    }
    218     if (PabloOptimizationsOptions.isSet(EnableMultiplexing)) {
    219         READ_CYCLE_COUNTER(multiplexing_start);
    220         MultiplexingPass::optimize(kernel);
    221         READ_CYCLE_COUNTER(multiplexing_end);
    222 //        if (PabloOptimizationsOptions.isSet(EnableLowering) || PabloOptimizationsOptions.isSet(EnablePreDistribution) || PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
    223 //            CanonicalizeDFG::transform(kernel);
    224 //        }
     70    if (PabloOptimizationsOptions.isSet(EnableDistribution)) {
     71        DistributivePass::optimize(kernel);
    22572    }
    226     if (PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
    227         READ_CYCLE_COUNTER(post_distribution_start);
    228         BooleanReassociationPass::optimize(kernel);
    229         READ_CYCLE_COUNTER(post_distribution_end);
    230     }
    231 #endif
    232     if (LLVM_LIKELY(!PabloOptimizationsOptions.isSet(DisableCodeMotion))) {
    233         READ_CYCLE_COUNTER(sinking_start);
    234         CodeMotionPass::optimize(kernel);
    235         READ_CYCLE_COUNTER(sinking_end);
    236     }
    237 #ifdef ENABLE_MULTIPLEXING
    238     if (DebugOptions.isSet(ShowUnloweredPablo)) {
    239         //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
    240         errs() << "Unlowered Pablo AST:\n";
    241         PabloPrinter::print(kernel, errs());
    242     }
    243     #ifdef PRINT_TIMING_INFORMATION
    244     distribution = SUMMARIZE_VARIADIC_DISTRIBUTION(function);
    245     #endif
    246 //    if (PabloOptimizationsOptions.isSet(EnableLowering) || PabloOptimizationsOptions.isSet(EnablePreDistribution) || PabloOptimizationsOptions.isSet(EnablePostDistribution)) {
    247 //        READ_CYCLE_COUNTER(lowering_start);
    248 //        FactorizeDFG::transform(kernel);
    249 //        READ_CYCLE_COUNTER(lowering_end);
    250 //    }
    251 //    if (PabloOptimizationsOptions.isSet(EnablePrePassScheduling)) {
    252 //        READ_CYCLE_COUNTER(scheduling_start);
    253 //        SchedulingPrePass::optimize(kernel);
    254 //        READ_CYCLE_COUNTER(scheduling_end);
    255 //    }
    256 #endif
    257 #ifdef PRINT_TIMING_INFORMATION
    258     const timestamp_t optimization_end = read_cycle_counter();
    259 #endif
    26073    if (DebugOptions.isSet(ShowOptimizedPablo)) {
    26174        if (PabloOutputFilename.empty()) {
     
    26982        }
    27083    }
    271 #ifdef PRINT_TIMING_INFORMATION
    272     errs() << "PABLO OPTIMIZATION TIME: " << (optimization_end - optimization_start) << "\n";
    273     errs() << "  SIMPLIFICATION TIME: " << (simplification_end - simplification_start) << "\n";
    274     errs() << "  COALESCING TIME: " << (coalescing_end - coalescing_start) << "\n";
    275     errs() << "  SINKING TIME: " << (sinking_end - sinking_start) << "\n";
    276     errs() << "  PRE-DISTRIBUTION TIME: " << (pre_distribution_end - pre_distribution_start) << "\n";
    277     errs() << "  MULTIPLEXING TIME: " << (multiplexing_end - multiplexing_start) << "\n";
    278     errs() << "  LOWERING TIME: " << (lowering_end - lowering_start) << "\n";
    279     errs() << "  FLATTENIF TIME: " << (flattenif_end - flattenif_start) << "\n";
    280     errs() << "  POST-DISTRIBUTION TIME: " << (post_distribution_end - post_distribution_start) << "\n";
    281     errs() << "  SCHEDULING TIME: " << (scheduling_end - scheduling_start) << "\n";
    282     errs() << "PABLO STATEMENTS: " << COUNT_STATEMENTS(function) << "\n";
    283     errs() << "PABLO ADVANCES: " << COUNT_ADVANCES(function) << "\n";
    284     errs() << "PRE-LOWERING VARIADIC DISTRIBUTION: ";
    285     bool join = false;
    286     for (auto dist : distribution) {
    287         if (join) {
    288             errs() << ';';
    289         }
    290         errs() << dist.first << '|' << dist.second;
    291         join = true;
    292     }
    293     errs() << "\n";
    294 #endif
    29584}
    29685
  • icGREP/icgrep-devel/icgrep/pablo/pablo_toolchain.h

    r5454 r5464  
    1414
    1515enum PabloDebugFlags {
    16     ShowPablo, ShowOptimizedPablo, ShowUnloweredPablo, DumpTrace,
     16    ShowPablo, ShowOptimizedPablo, DumpTrace,
    1717};
    1818
    1919enum PabloCompilationFlags {
    20     DisableSimplification, DisableCodeMotion,
    21     EnableMultiplexing, EnableLowering, EnablePreDistribution, EnablePostDistribution, EnablePrePassScheduling
     20    DisableSimplification, DisableCodeMotion, EnableDistribution
    2221};
    2322   
Note: See TracChangeset for help on using the changeset viewer.