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

Incorporated a few common case boolean optimizations in the Simplifier.

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
4 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
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.h

    r4887 r4922  
    1313protected:
    1414    static void distribute(PabloBlock * const block);
    15     static void process(PabloBlock * const block);
     15    static void distribute(Variadic * const expr);
    1616    DistributivePass() = default;
    1717};
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4919 r4922  
    77#include <boost/container/flat_set.hpp>
    88
     9#include <pablo/printer_pablos.h>
     10#include <iostream>
     11
    912namespace pablo {
    1013
     
    1215using SmallSet = boost::container::flat_set<Type>;
    1316
    14 /** ------------------------------------------------------------------------------------------------------------- *
    15  * @brief optimize
    16  ** ------------------------------------------------------------------------------------------------------------- */
    17 bool Simplifier::optimize(PabloFunction & function) {
    18     // negationsShouldImmediatelySucceedTheirLiteral(function.getEntryBlock());
    19     #ifndef NDEBUG
    20     PabloVerifier::verify(function, "post-negation-must-immediately-succeed-their-literal");
    21     #endif
    22     eliminateRedundantCode(function.getEntryBlock());
    23     #ifndef NDEBUG
    24     PabloVerifier::verify(function, "post-eliminate-redundant-code");
    25     #endif
    26     deadCodeElimination(function.getEntryBlock());
    27     #ifndef NDEBUG
    28     PabloVerifier::verify(function, "post-dead-code-elimination");
    29     #endif
    30     strengthReduction(function.getEntryBlock());
    31     #ifndef NDEBUG
    32     PabloVerifier::verify(function, "post-strength-reduction");
    33     #endif
    34     return true;
    35 }
    36 
    37 /** ------------------------------------------------------------------------------------------------------------- *
    38  * @brief isReassociative
    39  ** ------------------------------------------------------------------------------------------------------------- */
    40 inline bool isReassociative(const Statement * const stmt) {
    41     switch (stmt->getClassTypeId()) {
    42         case PabloAST::ClassTypeId::And:
    43         case PabloAST::ClassTypeId::Or:
    44         case PabloAST::ClassTypeId::Xor:
    45             return true;
    46         default: return false;
    47     }
    48 }
     17using TypeId = PabloAST::ClassTypeId;
    4918
    5019/** ------------------------------------------------------------------------------------------------------------- *
    5120 * @brief fold
    52  ** ------------------------------------------------------------------------------------------------------------- */
    53 inline PabloAST * Simplifier::fold(Variadic * const var, PabloBlock * const block) {
     21 *
     22 * Note: if folding alters this variadic without making any other modification to the AST, it will return null as
     23 * if no change was made.
     24 ** ------------------------------------------------------------------------------------------------------------- */
     25PabloAST * Simplifier::fold(Variadic * var, PabloBlock * const block) {
    5426
    5527    assert (var);
     
    6840    // Ensure all operands of a reassociatiable function are consistently ordered.
    6941    std::sort(var->begin(), var->end());
    70 
    7142    // Apply the idempotence law to any And and Or statement and the identity law to any Xor
    72     for (unsigned i = 1; i < var->getNumOperands(); ) {
    73         if (var->getOperand(i - 1) == var->getOperand(i)) {
     43    for (int i = var->getNumOperands() - 1; i > 0; --i) {
     44        if (LLVM_UNLIKELY(var->getOperand(i) == var->getOperand(i - 1))) {
    7445            var->removeOperand(i);
    7546            if (LLVM_UNLIKELY(isa<Xor>(var))) {
    76                 var->removeOperand(i - 1);
    77             }
     47                var->removeOperand(--i);
     48            }
     49        }
     50    }
     51
     52    // Apply the annihilator and identity laws
     53    for (unsigned i = 0; i != var->getNumOperands(); ) {
     54        if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
     55            if (LLVM_UNLIKELY(isa<And>(var))) {
     56                return PabloBlock::createZeroes();
     57            }
     58            var->removeOperand(i);
    7859            continue;
     60        } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
     61            if (LLVM_UNLIKELY(isa<Or>(var))) {
     62                return PabloBlock::createOnes();
     63            } else if (LLVM_UNLIKELY(isa<Xor>(var))) {
     64                negated = !negated;
     65            }
     66            var->removeOperand(i);
     67            continue;
    7968        }
    8069        ++i;
    8170    }
    8271
    83     if (LLVM_LIKELY(!isa<Xor>(var))) {
     72    PabloAST * replacement = nullptr;
     73
     74    if (LLVM_LIKELY(isa<And>(var) || isa<Or>(var))) {
     75        // Apply an implicit distribution + identity law whenever possible
     76        //    (P ∧ Q) √ (P ∧ ¬Q) = P √ (Q ∧ ¬Q) ⇔ (P √ Q) ∧ (P √ ¬Q) = P ∧ (Q √ ¬Q) ⇔ P
     77        bool modified = false;
     78        const TypeId typeId = isa<And>(var) ? TypeId::Or : TypeId::And;
     79        for (unsigned i = 1; i < var->getNumOperands(); ++i) {
     80            if (var->getOperand(i)->getClassTypeId() == typeId) {
     81                Variadic * const op_i = cast<Variadic>(var->getOperand(i));
     82                assert (std::is_sorted(op_i->begin(), op_i->end()));
     83                for (unsigned j = 0; j < i; ++j) {
     84                    if (var->getOperand(j)->getClassTypeId() == typeId) {
     85                        Variadic * const op_j = cast<Variadic>(var->getOperand(j));
     86                        assert (std::is_sorted(op_j->begin(), op_j->end()));
     87                        if (op_i->getNumOperands() == op_j->getNumOperands()) {
     88                            // If vi and vj differ by precisely one operand each, say di and dj, and di ⇔ ¬dj, then
     89                            // we can apply this rule.
     90                            unsigned vi = 0, vj = 0;
     91                            const unsigned operands = op_i->getNumOperands();
     92                            unsigned di = operands - 1, dj = operands - 1;
     93                            bool differsByOne = true;
     94                            while (vi < operands && vj < operands) {
     95                                if (op_i->getOperand(vi) < op_j->getOperand(vj)) {
     96                                    if (LLVM_UNLIKELY(di != (operands - 1))) { // <- we want the branch predictor to fail only once
     97                                        differsByOne = false;
     98                                        break;
     99                                    }
     100                                    di = vi++;
     101                                } else if (op_j->getOperand(vj) < op_i->getOperand(vi)) {
     102                                    if (LLVM_UNLIKELY(dj != (operands - 1))) {
     103                                        differsByOne = false;
     104                                        break;
     105                                    }
     106                                    dj = vj++;
     107                                } else {
     108                                    ++vi;
     109                                    ++vj;
     110                                }
     111                            }
     112                            if (LLVM_UNLIKELY(differsByOne)) {
     113                                assert (di < operands && dj < operands);
     114                                assert ("Found an equivalent set of operations that was not deduced earlier!" && !equals(op_i, op_j));
     115                                bool apply = false;
     116                                if (isa<Not>(op_i->getOperand(di))) {
     117                                    apply = equals(cast<Not>(op_i->getOperand(di))->getOperand(0), op_j->getOperand(dj));
     118                                } else if (isa<Not>(op_j->getOperand(dj))) {
     119                                    apply = equals(cast<Not>(op_j->getOperand(dj))->getOperand(0), op_i->getOperand(di));
     120                                }
     121                                if (LLVM_UNLIKELY(apply)) {
     122                                    // Although we can apply this rule, we have a potential problem. If P is not a "literal", we cannot modify
     123                                    // var without creating a new And or Or statement. This however may mean that the "redundancyElimination"
     124                                    // pass could miss a statement if its not added after this statement.
     125                                    PabloAST * expr = nullptr;
     126                                    if (operands == 2) {
     127                                        expr = op_i->getOperand(1 ^ di);
     128                                        if (LLVM_LIKELY(var->getNumOperands() == 2)) {
     129                                            return expr;
     130                                        }
     131                                    } else { // if (operands > 2) {
     132                                        assert (operands > 2);
     133                                        block->setInsertPoint(var->getPrevNode());
     134                                        Variadic * nested = nullptr;
     135                                        if (typeId == TypeId::And) {
     136                                            nested = block->createAnd(operands - 1);
     137                                        } else { // if (typeId == TypeId::Or) {
     138                                            nested = block->createOr(operands - 1);
     139                                        }
     140                                        for (unsigned k = 0; k != di; ++k) {
     141                                            nested->addOperand(op_i->getOperand(k));
     142                                        }
     143                                        for (unsigned k = di + 1; k < operands; ++k) {
     144                                            nested->addOperand(op_i->getOperand(k));
     145                                        }
     146                                        expr = nested;
     147                                        replacement = var;
     148                                    }
     149                                    var->setOperand(j, expr);
     150                                    var->removeOperand(i);
     151                                    i = 0;
     152                                    modified = true;
     153                                    break;
     154                                }
     155                            }
     156                        }
     157                    }
     158                }
     159            }
     160        }
     161
     162        // Apply the absorption law whenever possible
     163        //   P √ (P ∧ Q) ⇔ P ∧ (P √ Q) ⇔ P
     164        for (unsigned i = 1; i < var->getNumOperands(); ++i) {
     165            PabloAST * const op = var->getOperand(i);
     166            if (op->getClassTypeId() == typeId) {
     167                Variadic * const vi = cast<Variadic>(op);
     168                assert (std::is_sorted(vi->begin(), vi->end()));
     169                for (unsigned j = 0; j < i; ++j) {
     170                    assert (var->getOperand(i) == vi);
     171                    if (var->getOperand(j)->getClassTypeId() == typeId) {
     172                        Variadic * const vj = cast<Variadic>(var->getOperand(j));
     173                        assert (std::is_sorted(vj->begin(), vj->end()));
     174                        if (vi->getNumOperands() < vj->getNumOperands()) {
     175                            if (LLVM_UNLIKELY(std::includes(vi->begin(), vi->end(), vj->begin(), vj->end()))) {
     176                                var->removeOperand(i--);
     177                                break;
     178                            }
     179                        } else { // if (vi->getNumOperands() >= vj->getNumOperands()) {
     180                            if (LLVM_UNLIKELY(std::includes(vj->begin(), vj->end(), vi->begin(), vi->end()))) {
     181                                var->removeOperand(j--); i--;
     182                            }
     183                        }
     184                    }
     185                }
     186            } else { // treat the operand as a literal
     187                for (unsigned j = 0; j < var->getNumOperands(); ) {
     188                    if (var->getOperand(j)->getClassTypeId() == typeId) {
     189                        Variadic * const vj = cast<Variadic>(var->getOperand(j));
     190                        assert (std::is_sorted(vj->begin(), vj->end()));
     191                        if (LLVM_UNLIKELY(std::binary_search(vj->begin(), vj->end(), op))) {
     192                            var->removeOperand(j);
     193                            continue;
     194                        }
     195                    }
     196                    ++j;
     197                }
     198            }
     199        }
     200
    84201        // Apply the complementation law whenever possible.
    85202        for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    86203            if (isa<Not>(var->getOperand(i))) {
    87                 const PabloAST * const negatedOp = cast<Not>(var->getOperand(i))->getOperand(0);
     204                const PabloAST * const negated = cast<Not>(var->getOperand(i))->getOperand(0);
    88205                for (unsigned j = 0; j != var->getNumOperands(); ++j) {
    89                     if (LLVM_UNLIKELY(equals(var->getOperand(j), negatedOp))) {
    90                         if (isa<And>(var)) { // (A ∧ ¬A) ∧ B = 0 for any B
     206                    if (LLVM_UNLIKELY(var->getOperand(j) == negated)) {
     207                        if (isa<And>(var)) { // (A ∧ ¬A) ∧ B ⇔ 0 for any B
    91208                            return PabloBlock::createZeroes();
    92                         } else if (isa<Or>(var)) { // (A √ ¬A) √ B = 1 for any B
     209                        } else { // if (isa<Or>(var)) { // (A √ ¬A) √ B ⇔ 1 for any B
    93210                            return PabloBlock::createOnes();
    94211                        }
     
    97214            }
    98215        }
    99     }
    100 
    101     // Apply the annihilator and identity laws
    102     for (unsigned i = 0; i != var->getNumOperands(); ) {
    103         if (LLVM_UNLIKELY(isa<Zeroes>(var->getOperand(i)))) {
    104             if (isa<And>(var)) {
    105                 return PabloBlock::createZeroes();
    106             }
    107             var->removeOperand(i);
    108             continue;
    109         } else if (LLVM_UNLIKELY(isa<Ones>(var->getOperand(i)))) {
    110             if (isa<Or>(var)) {
    111                 return PabloBlock::createOnes();
    112             } else if (isa<Xor>(var)) {
    113                 negated = !negated;
    114             }
    115             var->removeOperand(i);
    116             continue;
    117         }
    118         ++i;
    119     }
    120 
    121     PabloAST * replacement = nullptr;
     216
     217        if (LLVM_UNLIKELY(modified)) {
     218            // Ensure all operands of a reassociatiable function are consistently ordered.
     219            std::sort(var->begin(), var->end());
     220            // Apply the idempotence law to any And and Or statement
     221            for (int i = var->getNumOperands() - 1; i > 0; --i) {
     222                if (LLVM_UNLIKELY(var->getOperand(i) == var->getOperand(i - 1))) {
     223                    var->removeOperand(i);
     224                }
     225            }
     226        }
     227
     228    } // end of if (LLVM_LIKELY(isa<And>(var) || isa<Or>(var)))
     229
    122230    if (LLVM_UNLIKELY(var->getNumOperands() < 2)) {
    123         replacement = (var->getNumOperands() == 0) ? PabloBlock::createZeroes() : var->getOperand(0);
     231        if (LLVM_UNLIKELY(var->getNumOperands() == 0)) {
     232            return PabloBlock::createZeroes();
     233        }
     234        replacement = var->getOperand(0);
     235    }
     236    // If we marked this var as being a replacement for itself, then we must have manipulated some of its inner
     237    // operands in such a way that we had to generate new statements for it. Thus we need to generate a new "var"
     238    // so that the "redundancyElimination" pass doesn't miss one of its operands.
     239    if (LLVM_UNLIKELY(replacement == var)) {
     240        Variadic * replacementVar = nullptr;
     241        if (isa<And>(var)) {
     242            replacementVar = block->createAnd(var->getNumOperands());
     243        } else if (isa<Or>(var)) {
     244            replacementVar = block->createOr(var->getNumOperands());
     245        } else { // if (isa<Xor>(var)) {
     246            replacementVar = block->createXor(var->getNumOperands());
     247        }
     248        assert (std::is_sorted(var->begin(), var->end()));
     249        for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     250            replacementVar->addOperand(var->getOperand(i));
     251        }
     252        replacement = replacementVar;
    124253    }
    125254    if (LLVM_UNLIKELY(negated)) {
     255        assert (isa<Xor>(var));
    126256        block->setInsertPoint(var);
    127257        replacement = block->createNot(replacement ? replacement : var);
    128258    }
     259    assert (replacement != var);
    129260    return replacement;
    130261}
     
    133264 * @brief fold
    134265 ** ------------------------------------------------------------------------------------------------------------- */
    135 inline PabloAST * Simplifier::fold(Statement * stmt, PabloBlock * block) {
    136     if (isReassociative(stmt)) {
     266inline PabloAST * Simplifier::fold(Statement * stmt, PabloBlock * const block) {
     267    if (isa<Variadic>(stmt)) {
    137268        return fold(cast<Variadic>(stmt), block);
    138269    } else if (isa<Not>(stmt)) {
    139270        PabloAST * value = stmt->getOperand(0);
    140271        if (LLVM_UNLIKELY(isa<Not>(value))) {
    141             return cast<Not>(value)->getOperand(0);
     272            return cast<Not>(value)->getOperand(0); // ¬¬A ⇔ A
    142273        } else if (LLVM_UNLIKELY(isa<Zeroes>(value))) {
    143             return block->createOnes();
     274            return PabloBlock::createOnes(); // ¬0 ⇔ 1
    144275        }  else if (LLVM_UNLIKELY(isa<Ones>(value))) {
    145             return block->createZeroes();
     276            return PabloBlock::createZeroes(); // ¬1 ⇔ 0
    146277        }
    147278    } else if (isa<Advance>(stmt)) {
    148279        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(0)))) {
    149             return block->createZeroes();
     280            return PabloBlock::createZeroes();
    150281        }
    151282    } else {
     
    166297                }
    167298            } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
    168                 block->setInsertPoint(stmt->getPrevNode());
    169299                switch (stmt->getClassTypeId()) {
    170300                    case PabloAST::ClassTypeId::Sel:
     
    176306                        }
    177307                    case PabloAST::ClassTypeId::ScanThru:
    178                         if (i == 1) {
    179                             return block->createZeroes();
     308                        if (LLVM_UNLIKELY(i == 1)) {
     309                            return PabloBlock::createZeroes();
    180310                        }
    181311                        break;
    182312                    case PabloAST::ClassTypeId::MatchStar:
    183                         if (i == 0) {
    184                             return block->createOnes();
     313                        if (LLVM_UNLIKELY(i == 0)) {
     314                            return PabloBlock::createOnes();
    185315                        }
    186316                        break;
     
    305435
    306436/** ------------------------------------------------------------------------------------------------------------- *
    307  * @brief eliminateRedundantCode
     437 * @brief redundancyElimination
    308438 *
    309439 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
    310440 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
    311441 ** ------------------------------------------------------------------------------------------------------------- */
    312 void Simplifier::eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor) {
     442void Simplifier::redundancyElimination(PabloBlock * const block, ExpressionTable * predecessor) {
    313443    ExpressionTable encountered(predecessor);
    314444    Statement * stmt = block->front();
     
    320450            // the Assign's expression directly.
    321451            if (isSuperfluous(assign)) {
    322                 stmt = assign->replaceWith(assign->getExpression());               
     452                stmt = assign->replaceWith(assign->getExpression());
    323453                continue;
    324454            }
     
    345475
    346476            // Process the If body
    347             eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
     477            redundancyElimination(cast<If>(stmt)->getBody(), &encountered);
    348478
    349479            // If we ended up removing all of the defined variables, delete the If node.
     
    384514                continue;
    385515            }
    386             eliminateRedundantCode(whileNode->getBody(), &encountered);
     516            redundancyElimination(whileNode->getBody(), &encountered);
    387517            removeIdenticalEscapedValues(whileNode->getVariants());
    388518            // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
    389519            // statements into the body.
    390520        } else {
    391             if (PabloAST * folded = fold(stmt, block)) {
    392                 // If we determine we can fold this statement,
    393                 Statement * const prior = stmt->getPrevNode();
     521            Statement * const prior = stmt->getPrevNode();
     522            PabloAST * const folded = fold(stmt, block);
     523            if (folded) {
     524                // If we determine we can fold this statement, go back to the original prior node of this statement.
     525                // New statements may have been inserted after it.
    394526                stmt->replaceWith(folded, true);
    395527                stmt = LLVM_LIKELY(prior != nullptr) ? prior->getNextNode() : block->front();
     
    468600        stmt = stmt->getNextNode();
    469601    }
    470     block->setInsertPoint(block->back());
    471 }
    472 
    473 /** ------------------------------------------------------------------------------------------------------------- *
    474  * @brief negationsShouldImmediatelySucceedTheirLiteral
    475  *
    476  * Assuming that most negations are actually replaced by an ANDC operations or that we only need a literal or its
    477  * negation, by pushing all negations up to immediately succeed the literal we should generate equally efficient
    478  * code whilst simplifying analysis.
    479  *
    480  * TODO: this theory needs evaluation.
    481  ** ------------------------------------------------------------------------------------------------------------- */
    482 void Simplifier::negationsShouldImmediatelySucceedTheirLiteral(PabloBlock * const block) {
    483     Statement * stmt = block->front();
    484     while (stmt) {
    485         Statement * next = stmt->getNextNode();
    486         if (isa<If>(stmt)) {
    487             negationsShouldImmediatelySucceedTheirLiteral(cast<If>(stmt)->getBody());
    488         } else if (isa<While>(stmt)) {
    489             negationsShouldImmediatelySucceedTheirLiteral(cast<While>(stmt)->getBody());
    490         } else if (isa<Not>(stmt)) {
    491             PabloAST * op = cast<Not>(stmt)->getExpr();
    492             if (LLVM_LIKELY(isa<Statement>(op))) {
    493                 PabloBlock * scope = cast<Statement>(op)->getParent();
    494                 // If the operand is not in a nested scope, we can move it.
    495                 for (;;) {
    496                     if (LLVM_UNLIKELY(scope == nullptr)) {
    497                         stmt->insertAfter(cast<Statement>(op));
    498                         break;
    499                     }
    500                     scope = scope->getParent();
    501                     if (LLVM_UNLIKELY(scope == block)) {
    502                         break;
    503                     }
    504                 }
    505             }
    506         }
    507         stmt = next;
    508     }
    509 }
    510 
    511 }
     602}
     603
     604/** ------------------------------------------------------------------------------------------------------------- *
     605 * @brief optimize
     606 ** ------------------------------------------------------------------------------------------------------------- */
     607bool Simplifier::optimize(PabloFunction & function) {
     608    redundancyElimination(function.getEntryBlock());
     609    #ifndef NDEBUG
     610    PabloVerifier::verify(function, "post-eliminate-redundant-code");
     611    #endif
     612    deadCodeElimination(function.getEntryBlock());
     613    #ifndef NDEBUG
     614    PabloVerifier::verify(function, "post-dead-code-elimination");
     615    #endif
     616    strengthReduction(function.getEntryBlock());
     617    #ifndef NDEBUG
     618    PabloVerifier::verify(function, "post-strength-reduction");
     619    #endif
     620    return true;
     621}
     622
     623}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4919 r4922  
    1010
    1111class Simplifier {
     12    friend class DistributivePass;
    1213public:
    1314    static bool optimize(PabloFunction & function);
     
    1516    Simplifier() = default;
    1617private:
    17     static void negationsShouldImmediatelySucceedTheirLiteral(PabloBlock * const block);
    18     static void eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor = nullptr);
    19     static PabloAST * fold(Variadic * const var, PabloBlock * const block);
     18    static void redundancyElimination(PabloBlock * const block, ExpressionTable * predecessor = nullptr);
     19    static PabloAST * fold(Variadic * var, PabloBlock * const block);
    2020    static PabloAST * fold(Statement * const stmt, PabloBlock * const block);
    2121    static void deadCodeElimination(PabloBlock * const block);
Note: See TracChangeset for help on using the changeset viewer.