Ignore:
Timestamp:
Jan 29, 2016, 3:38:47 PM (3 years ago)
Author:
nmedfort
Message:

Incorporated a few common case boolean optimizations in the Simplifier.

File:
1 edited

Legend:

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

    r4919 r4922  
    99#include <boost/graph/adjacency_list.hpp>
    1010
     11#include <pablo/printer_pablos.h>
     12#include <iostream>
     13
    1114using namespace boost;
    1215using namespace boost::container;
     
    1417namespace pablo {
    1518
    16 using DependencyGraph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
    17 using Vertex = DependencyGraph::vertex_descriptor;
    18 using SinkMap = flat_map<PabloAST *, Vertex>;
     19using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     20using Vertex = Graph::vertex_descriptor;
     21using Map = flat_map<PabloAST *, Vertex>;
    1922using VertexSet = std::vector<Vertex>;
    2023using Biclique = std::pair<VertexSet, VertexSet>;
     
    2225using DistributionSet = std::tuple<VertexSet, VertexSet, VertexSet>;
    2326using DistributionSets = std::vector<DistributionSet>;
    24 
    2527using TypeId = PabloAST::ClassTypeId;
    26 
    27 /** ------------------------------------------------------------------------------------------------------------- *
    28  * @brief getVertex
    29  ** ------------------------------------------------------------------------------------------------------------- */
    30 static inline Vertex getVertex(PabloAST * value, DependencyGraph & G, SinkMap & M) {
    31     const auto f = M.find(value);
    32     if (f != M.end()) {
    33         return f->second;
    34     }
    35     const auto u = add_vertex(value, G);
    36     M.emplace(value, u);
    37     return u;
    38 }
    39 
    40 /** ------------------------------------------------------------------------------------------------------------- *
    41  * @brief generateDistributionGraph
    42  *
    43  * Generate a graph G describing the potential applications of the distributive law for the given block.
    44  ** ------------------------------------------------------------------------------------------------------------- */
    45 VertexSet generateDistributionGraph(PabloBlock * block, DependencyGraph & G) {
    46     SinkMap M;
    47     VertexSet distSet;
    48     for (Statement * stmt : *block) {
    49         if (isa<And>(stmt) || isa<Or>(stmt)) {
    50             const TypeId outerTypeId = stmt->getClassTypeId();
    51             const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
    52             flat_set<PabloAST *> distributable;
    53             for (PabloAST * const expr : *cast<Variadic>(stmt)) {
    54                 if (LLVM_UNLIKELY(expr->getClassTypeId() == innerTypeId)) {
    55                     bool safe = true;
    56                     for (PabloAST * const user : expr->users()) {
    57                         if (user->getClassTypeId() != outerTypeId) {
    58                             safe = false;
    59                             break;
    60                         }
    61                     }
    62                     if (safe) {
    63                         distributable.insert(expr);
    64                     }
    65                 }
    66             }
    67             if (LLVM_LIKELY(distributable.size() > 1)) {
    68                 flat_map<PabloAST *, bool> observedMoreThanOnce;
    69                 bool anyOpportunities = false;
    70                 for (const PabloAST * distOperation : distributable) {
    71                     for (PabloAST * const distVar : *cast<Variadic>(distOperation)) {
    72                         auto ob = observedMoreThanOnce.find(distVar);
    73                         if (ob == observedMoreThanOnce.end()) {
    74                             observedMoreThanOnce.emplace(distVar, false);
    75                         } else {
    76                             ob->second = true;
    77                             anyOpportunities = true;
    78                         }
    79                     }
    80                 }
    81                 if (anyOpportunities) {
    82                     for (const auto ob : observedMoreThanOnce) {
    83                         PabloAST * distVar = nullptr;
    84                         bool observedTwice = false;
    85                         std::tie(distVar, observedTwice) = ob;
    86                         if (observedTwice) {
    87                             const Vertex z = getVertex(stmt, G, M);
    88                             distSet.push_back(z);
    89                             for (PabloAST * const distOperation : distVar->users()) {
    90                                 if (distributable.count(distOperation)) {
    91                                     const Vertex y = getVertex(distOperation, G, M);
    92                                     add_edge(getVertex(distVar, G, M), y, G);
    93                                     add_edge(y, z, G);
    94                                 }
    95                             }
    96                         }
    97                     }
    98                 }
    99             }
    100         }
    101     }
    102     return distSet;
    103 }
    10428
    10529/** ------------------------------------------------------------------------------------------------------------- *
     
    12549 * @brief independentCliqueSets
    12650 ** ------------------------------------------------------------------------------------------------------------- */
    127 template <unsigned side>
    128 inline static BicliqueSet && independentCliqueSets(BicliqueSet && bicliques, const unsigned minimum) {
     51static BicliqueSet && independentCliqueSets(BicliqueSet && bicliques, const bool uppsetSet) {
    12952    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    13053
     
    13255    IndependentSetGraph I(l);
    13356
     57
    13458    // Initialize our weights and determine the constraints
    135     for (unsigned i = 0; i != l; ++i) {
    136         I[i] = std::pow(std::get<side>(bicliques[i]).size(), 2);
    137         for (unsigned j = i + 1; j != l; ++j) {
    138             if (intersects(std::get<side>(bicliques[i]), std::get<side>(bicliques[j]))) {
    139                 add_edge(i, j, I);
    140             }
    141         }
    142     }
    143 
    144 //    // Initialize our weights and determine the constraints
    145 //    for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
    146 //        I[std::distance(bicliques.begin(), i)] = std::pow(std::get<side>(*i).size(), 2);
    147 //        for (auto j = i; ++j != bicliques.end(); ) {
    148 //            if (intersects(i->second, j->second) && intersects(i->first, j->first)) {
    149 //                add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
    150 //            }
    151 //        }
    152 //    }
     59    if (uppsetSet) {
     60        for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
     61            I[std::distance(bicliques.begin(), i)] = std::pow(std::get<0>(*i).size(), 2);
     62            for (auto j = i; ++j != bicliques.end(); ) {
     63                if (intersects(i->first, j->first)) {
     64                    add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
     65                }
     66            }
     67        }
     68    } else {
     69        for (auto i = bicliques.begin(); i != bicliques.end(); ++i) {
     70            I[std::distance(bicliques.begin(), i)] = std::pow(std::get<1>(*i).size(), 2);
     71            for (auto j = i; ++j != bicliques.end(); ) {
     72                if (intersects(i->first, j->first) && intersects(i->second, j->second)) {
     73                    add_edge(std::distance(bicliques.begin(), i), std::distance(bicliques.begin(), j), I);
     74                }
     75            }
     76        }
     77    }
     78
    15379
    15480    // Use the greedy algorithm to choose our independent set
     
    16389            }
    16490        }
    165         if (w < minimum) break;
     91        if (w < (uppsetSet ? 2 : 1)) break;
    16692        selected.push_back(u);
    16793        I[u] = 0;
     
    189115 * bipartition A and their adjacencies to be in B.
    190116  ** ------------------------------------------------------------------------------------------------------------- */
    191 static BicliqueSet enumerateBicliques(const DependencyGraph & G, const VertexSet & A) {
     117static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A, const unsigned min) {
    192118    using IntersectionSets = std::set<VertexSet>;
    193119
    194120    IntersectionSets B1;
     121    VertexSet tmp;
    195122    for (auto u : A) {
    196123        if (in_degree(u, G) > 0) {
    197             VertexSet incomingAdjacencies;
    198             incomingAdjacencies.reserve(in_degree(u, G));
     124            tmp.reserve(in_degree(u, G));
    199125            for (auto e : make_iterator_range(in_edges(u, G))) {
    200                 incomingAdjacencies.push_back(source(e, G));
    201             }
    202             std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
    203             B1.insert(std::move(incomingAdjacencies));
     126                tmp.push_back(source(e, G));
     127            }
     128            if (tmp.size() >= min) {
     129                std::sort(tmp.begin(), tmp.end());
     130                B1.emplace(tmp.begin(), tmp.end());
     131            }
     132            tmp.clear();
    204133        }
    205134    }
     
    208137
    209138    IntersectionSets Bi;
    210 
    211     VertexSet clique;
    212139    for (auto i = B1.begin(); i != B1.end(); ++i) {
    213140        for (auto j = i; ++j != B1.end(); ) {
    214             std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    215             if (clique.size() > 0) {
    216                 if (B.count(clique) == 0) {
    217                     Bi.insert(clique);
    218                 }
    219                 clique.clear();
    220             }
     141            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
     142            if (tmp.size() >= min) {
     143                if (B.count(tmp) == 0) {
     144                    Bi.emplace(tmp.begin(), tmp.end());
     145                }
     146            }
     147            tmp.clear();
    221148        }
    222149    }
     
    230157        for (auto i = B1.begin(); i != B1.end(); ++i) {
    231158            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
    232                 std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    233                 if (clique.size() > 0) {
    234                     if (B.count(clique) == 0) {
    235                         Bk.insert(clique);
     159                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(tmp));
     160                if (tmp.size() >= min) {
     161                    if (B.count(tmp) == 0) {
     162                        Bk.emplace(tmp.begin(), tmp.end());
    236163                    }
    237                     clique.clear();
    238                 }
     164                }
     165                tmp.clear();
    239166            }
    240167        }
     
    245172    cliques.reserve(B.size());
    246173    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
     174        assert (Bi->size() >= min);
    247175        VertexSet Ai(A);
    248176        for (const Vertex u : *Bi) {
     
    271199 * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
    272200 ** ------------------------------------------------------------------------------------------------------------- */
    273 static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, DependencyGraph & G) {
     201static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, const Graph & G) {
    274202    for (auto ci = cliques.begin(); ci != cliques.end(); ) {
    275203        const auto cardinalityA = std::get<0>(*ci).size();
     
    294222 * @brief safeDistributionSets
    295223 ** ------------------------------------------------------------------------------------------------------------- */
    296 static DistributionSets safeDistributionSets(DependencyGraph & G, const VertexSet & distSet) {
     224inline static DistributionSets safeDistributionSets(const Graph & G, const VertexSet & A) {
    297225    DistributionSets T;
    298     BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(G, distSet), G), 1);
     226    BicliqueSet lowerSet = independentCliqueSets(removeUnhelpfulBicliques(enumerateBicliques(G, A, 1), G), false);
    299227    for (Biclique & lower : lowerSet) {
    300         BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(G, std::get<1>(lower)), 2);
     228        BicliqueSet upperSet = independentCliqueSets(enumerateBicliques(G, std::get<1>(lower), 2), true);
    301229        for (Biclique & upper : upperSet) {
    302230            T.emplace_back(std::move(std::get<1>(upper)), std::move(std::get<0>(upper)), std::get<0>(lower));
     
    307235
    308236/** ------------------------------------------------------------------------------------------------------------- *
    309  * @brief process
    310  ** ------------------------------------------------------------------------------------------------------------- */
    311 inline void DistributivePass::process(PabloBlock * const block) {
    312 
    313     for (;;) {
    314 
    315         // FlattenAssociativeDFG::coalesce(block, false);
    316 
    317         DependencyGraph G;
    318 
    319         const VertexSet distSet = generateDistributionGraph(block, G);
    320 
    321         // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
    322         if (LLVM_UNLIKELY(distSet.empty())) {
     237 * @brief scopeDepthOf
     238 ** ------------------------------------------------------------------------------------------------------------- */
     239inline unsigned scopeDepthOf(const PabloBlock * block) {
     240    unsigned depth = 0;
     241    for (; block; ++depth, block = block->getParent());
     242    return depth;
     243}
     244
     245/** ------------------------------------------------------------------------------------------------------------- *
     246 * @brief findInsertionPoint
     247 ** ------------------------------------------------------------------------------------------------------------- */
     248inline PabloBlock * findInsertionPoint(const VertexSet & users, const Graph & G) {
     249    std::vector<PabloBlock *> scopes(0);
     250    scopes.reserve(users.size());
     251    for (Vertex u : users) {
     252        PabloBlock * const scope = cast<Statement>(G[u])->getParent(); assert (scope);
     253        if (std::find(scopes.begin(), scopes.end(), scope) == scopes.end()) {
     254            scopes.push_back(scope);
     255        }
     256    }
     257    while (scopes.size() > 1) {
     258        // Find the LCA of both scopes then add the LCA back to the list of scopes.
     259        PabloBlock * scope1 = scopes.back();
     260        scopes.pop_back();
     261        PabloBlock * scope2 = scopes.back();
     262        scopes.pop_back();
     263        assert (scope1 != scope2);
     264        unsigned depth1 = scopeDepthOf(scope1);
     265        unsigned depth2 = scopeDepthOf(scope2);
     266        // If one of these scopes is nested deeper than the other, scan upwards through
     267        // the scope tree until both scopes are at the same depth.
     268        while (depth1 > depth2) {
     269            scope1 = scope1->getParent();
     270            --depth1;
     271        }
     272        while (depth1 < depth2) {
     273            scope2 = scope2->getParent();
     274            --depth2;
     275        }
     276        assert (depth1 == depth2);
     277        // Then iteratively step backwards until we find a matching scopes; this must be
     278        // the LCA of our original pair.
     279        while (scope1 != scope2) {
     280            scope1 = scope1->getParent();
     281            scope2 = scope2->getParent();
     282        }
     283        assert (scope1 && scope2);
     284        if (std::find(scopes.begin(), scopes.end(), scope1) == scopes.end()) {
     285            scopes.push_back(scope1);
     286        }
     287    }
     288    assert (scopes.size() == 1);
     289    PabloBlock * const root = scopes.front();
     290    // Now that we know the common scope of these users, test which statement is the first to require it.
     291    flat_set<Statement *> usages;
     292    usages.reserve(users.size());
     293    for (Vertex u : users) {
     294        Statement * user = cast<Statement>(G[u]);
     295        PabloBlock * scope = user->getParent();
     296        while (scope != root) {
     297            assert (scope);
     298            user = scope->getBranch();
     299            scope = scope->getParent();
     300        }
     301        usages.insert(user);
     302    }
     303    Statement * ip = nullptr;
     304    for (Statement * stmt : *root) {
     305        if (usages.count(stmt)) {
     306            ip = stmt->getPrevNode();
    323307            break;
    324308        }
    325 
    326         const DistributionSets distributionSets = safeDistributionSets(G, distSet);
    327 
    328         if (LLVM_UNLIKELY(distributionSets.empty())) {
    329             break;
    330         }
    331 
    332         for (const DistributionSet & set : distributionSets) {
    333 
    334             // Each distribution tuple consists of the sources, intermediary, and sink nodes.
    335             const VertexSet & sources = std::get<0>(set);
    336             const VertexSet & intermediary = std::get<1>(set);
    337             const VertexSet & sinks = std::get<2>(set);
    338 
    339             // Find the first sink and set the insert point immediately before that.
    340             Variadic * innerOp = nullptr;
    341             Variadic * outerOp = nullptr;
    342 
    343             block->setInsertPoint(cast<Variadic>(G[sinks.front()])->getPrevNode());
    344             if (isa<And>(G[sinks.front()])) {
    345                 outerOp = block->createAnd(intermediary.size());
    346                 innerOp = block->createOr(sources.size() + 1);
    347             } else {
    348                 outerOp = block->createOr(intermediary.size());
    349                 innerOp = block->createAnd(sources.size() + 1);
    350             }
    351 
    352             for (const Vertex u : intermediary) {
    353                 for (const Vertex v : sinks) {
    354                     cast<Variadic>(G[v])->deleteOperand(G[u]);
    355                 }
    356                 outerOp->addOperand(G[u]);
    357             }
    358             CoalesceDFG::coalesce(outerOp);
    359 
    360             for (const Vertex u : sources) {
     309    }
     310    assert (ip);
     311    root->setInsertPoint(ip);
     312    return root;
     313}
     314
     315/** ------------------------------------------------------------------------------------------------------------- *
     316 * @brief computeDistributionGraph
     317 ** ------------------------------------------------------------------------------------------------------------- */
     318static inline void computeDistributionGraph(Variadic * const expr, Graph & G, VertexSet & A) {
     319
     320    const TypeId outerTypeId = expr->getClassTypeId();
     321    const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
     322
     323    assert (isa<And>(expr) || isa<Or>(expr));
     324
     325    Map M;
     326    for (unsigned i = 0; i != expr->getNumOperands(); ++i) {
     327        PabloAST * const op = expr->getOperand(i);
     328        if (op->getClassTypeId() == innerTypeId) {
     329            bool distributable = true;
     330            for (PabloAST * user : op->users()) {
     331                // Early check to see whether it'd be beneficial to distribute it. If this fails, we'd have
     332                // to compute the operand's value anyway, so just ignore this operand.
     333                if (user->getClassTypeId() != outerTypeId) {
     334                    distributable = false;
     335                    break;
     336                }
     337            }
     338            if (distributable) {
     339                const Vertex u = add_vertex(op, G);
     340                for (PabloAST * user : op->users()) {
     341                    const auto f = M.find(user);
     342                    Vertex v = 0;
     343                    if (LLVM_LIKELY(f != M.end())) {
     344                        v = f->second;
     345                    } else {
     346                        v = add_vertex(user, G);
     347                        M.emplace(user, v);
     348                        A.push_back(v);
     349                    }
     350                    add_edge(u, v, G);
     351                }
     352                for (PabloAST * input : *cast<Variadic>(op)) {
     353                    const auto f = M.find(input);
     354                    Vertex v = 0;
     355                    if (f != M.end()) {
     356                        v = f->second;
     357                    } else {
     358                        v = add_vertex(input, G);
     359                        M.emplace(input, v);
     360                    }
     361                    add_edge(v, u, G);
     362                }
     363            }
     364        }
     365    }
     366}
     367
     368/** ------------------------------------------------------------------------------------------------------------- *
     369 * @brief distribute
     370 *
     371 * Based on the knowledge that:
     372 *
     373 *   (P ∧ Q) √ (P ∧ R) ⇔ P ∧ (Q √ R) and (P √ Q) ∧ (P √ R) ⇔ P √ (Q ∧ R)
     374 *
     375 * Try to eliminate some of the unnecessary operations from the current Variadic expression.
     376 ** ------------------------------------------------------------------------------------------------------------- */
     377inline void DistributivePass::distribute(Variadic * const var) {
     378
     379    std::vector<Variadic *> Q;
     380
     381    assert (isa<And>(var) || isa<Or>(var));
     382
     383    Q.push_back(var);
     384
     385    Graph G;
     386    VertexSet A;
     387
     388    while (Q.size() > 0) {
     389
     390        Variadic * expr = CanonicalizeDFG::canonicalize(Q.back());
     391        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                // Test whether we can apply the identity law to distributed set. I.e., (P ∧ Q) √ (P ∧ ¬Q) ⇔ (P √ Q) ∧ (P √ ¬Q) ⇔ P
     431
     432
     433                for (const Vertex u : intermediary) {
     434                    for (const Vertex v : sources) {
     435                        cast<Variadic>(G[u])->deleteOperand(G[v]);
     436                    }
     437                }
     438                for (const Vertex u : sinks) {
     439                    for (const Vertex v : intermediary) {
     440                        cast<Variadic>(G[u])->deleteOperand(G[v]);
     441                    }
     442                }
     443
     444                PabloBlock * const block = findInsertionPoint(sinks, G);
     445                Variadic * innerOp = nullptr;
     446                Variadic * outerOp = nullptr;
     447                if (isa<And>(expr)) {
     448                    outerOp = block->createAnd(intermediary.size());
     449                    innerOp = block->createOr(sources.size() + 1);
     450                } else {
     451                    outerOp = block->createOr(intermediary.size());
     452                    innerOp = block->createAnd(sources.size() + 1);
     453                }
    361454                for (const Vertex v : intermediary) {
    362                     cast<Variadic>(G[v])->deleteOperand(G[u]);
    363                 }
    364                 innerOp->addOperand(G[u]);
    365             }
    366             innerOp->addOperand(outerOp);
    367             CoalesceDFG::coalesce(innerOp);
    368 
    369             for (const Vertex u : sinks) {
    370                 cast<Variadic>(G[u])->addOperand(innerOp);
    371             }
     455                    outerOp->addOperand(G[v]);
     456                }
     457                for (const Vertex v : sources) {
     458                    innerOp->addOperand(G[v]);
     459                }
     460                for (const Vertex u : sinks) {
     461                    cast<Variadic>(G[u])->addOperand(innerOp);
     462                }
     463                innerOp->addOperand(outerOp);
     464                // Push our newly constructed ops into the Q
     465                Q.push_back(innerOp);
     466                Q.push_back(outerOp);
     467            }
     468
     469            G.clear();
     470            A.clear();
    372471        }
    373472    }
     
    381480        if (isa<If>(stmt) || isa<While>(stmt)) {
    382481            distribute(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    383         }
    384     }
    385     process(block);
     482        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
     483            distribute(cast<Variadic>(stmt));
     484        }
     485    }
    386486}
    387487
Note: See TracChangeset for help on using the changeset viewer.