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.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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}
Note: See TracChangeset for help on using the changeset viewer.