Changeset 4880 for icGREP


Ignore:
Timestamp:
Nov 24, 2015, 4:27:35 PM (4 years ago)
Author:
nmedfort
Message:

More work on n-ary operations.

Location:
icGREP/icgrep-devel/icgrep
Files:
11 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4878 r4880  
    6464SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_compiler.cpp pablo/carry_manager.cpp pablo/carry_data.cpp IDISA/idisa_builder.cpp)
    6565SET(PABLO_SRC ${PABLO_SRC} pablo/analysis/pabloverifier.cpp)
    66 SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/codemotionpass.cpp pablo/passes/flattenassociativedfg.cpp)
     66SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/codemotionpass.cpp pablo/optimizers/distributivepass.cpp pablo/passes/flattenassociativedfg.cpp)
    6767SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/booleanreassociationpass.cpp)
    6868IF (ENABLE_MULTIPLEXING)
     
    317317SET(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS} -O3 -DNDEBUG")
    318318IF (${CMAKE_SYSTEM} MATCHES "Linux")
    319     SET(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS} -g -fsanitize=address") # -fsanitize=address
     319    SET(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS} -g -fsanitize=address -fno-omit-frame-pointer")
    320320ENDIF()
    321321
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r4878 r4880  
    22
    33#include <pablo/codegenstate.h>
     4#include <pablo/analysis/pabloverifier.hpp>
     5#include <pablo/optimizers/pablo_simplifier.hpp>
     6#include <boost/container/flat_set.hpp>
    47#include <boost/container/flat_map.hpp>
    58#include <boost/graph/adjacency_list.hpp>
     
    1013namespace pablo {
    1114
    12 using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
    13 using DistributionMap = flat_map<PabloAST *, DistributionGraph::vertex_descriptor>;
    14 
    15 using VertexSet = std::vector<Variadic *>;
     15using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     16using Vertex = Graph::vertex_descriptor;
     17using Map = flat_map<PabloAST *, Vertex>;
     18using VertexSet = std::vector<Vertex>;
    1619using Biclique = std::pair<VertexSet, VertexSet>;
    1720using BicliqueSet = std::vector<Biclique>;
     
    2427 * @brief getVertex
    2528 ** ------------------------------------------------------------------------------------------------------------- */
    26 static inline DistributionGraph::vertex_descriptor getVertex(const PabloAST * value, DistributionGraph & G, DistributionMap & M) {
     29static inline Vertex getVertex(PabloAST * value, Graph & G, Map & M) {
    2730    const auto f = M.find(value);
    2831    if (f != M.end()) {
     
    3538
    3639/** ------------------------------------------------------------------------------------------------------------- *
    37  * @brief enumerateBicliques
     40 * @brief generateDistributionGraph
    3841 *
    39  * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
    40  * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
    41  * bipartition A and their adjacencies to be in B.
    42   ** ------------------------------------------------------------------------------------------------------------- */
    43 template <class Graph>
    44 static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
    45     using IntersectionSets = std::set<VertexSet>;
    46 
    47     IntersectionSets B1;
    48     for (auto u : A) {
    49         if (in_degree(u, G) > 0) {
    50             VertexSet incomingAdjacencies;
    51             incomingAdjacencies.reserve(in_degree(u, G));
    52             for (auto e : make_iterator_range(in_edges(u, G))) {
    53                 incomingAdjacencies.push_back(source(e, G));
    54             }
    55             std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
    56             B1.insert(std::move(incomingAdjacencies));
    57         }
    58     }
    59 
    60     IntersectionSets B(B1);
    61 
    62     IntersectionSets Bi;
    63 
    64     VertexSet clique;
    65     for (auto i = B1.begin(); i != B1.end(); ++i) {
    66         for (auto j = i; ++j != B1.end(); ) {
    67             std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    68             if (clique.size() > 0) {
    69                 if (B.count(clique) == 0) {
    70                     Bi.insert(clique);
    71                 }
    72                 clique.clear();
    73             }
    74         }
    75     }
    76 
    77     for (;;) {
    78         if (Bi.empty()) {
    79             break;
    80         }
    81         B.insert(Bi.begin(), Bi.end());
    82         IntersectionSets Bk;
    83         for (auto i = B1.begin(); i != B1.end(); ++i) {
    84             for (auto j = Bi.begin(); j != Bi.end(); ++j) {
    85                 std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    86                 if (clique.size() > 0) {
    87                     if (B.count(clique) == 0) {
    88                         Bk.insert(clique);
    89                     }
    90                     clique.clear();
    91                 }
    92             }
    93         }
    94         Bi.swap(Bk);
    95     }
    96 
    97     BicliqueSet cliques;
    98     cliques.reserve(B.size());
    99     for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
    100         VertexSet Ai(A);
    101         for (const Vertex u : *Bi) {
    102             VertexSet Aj;
    103             Aj.reserve(out_degree(u, G));
    104             for (auto e : make_iterator_range(out_edges(u, G))) {
    105                 Aj.push_back(target(e, G));
    106             }
    107             std::sort(Aj.begin(), Aj.end());
    108             VertexSet Ak;
    109             Ak.reserve(std::min(Ai.size(), Aj.size()));
    110             std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
    111             Ai.swap(Ak);
    112         }
    113         assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
    114         cliques.emplace_back(std::move(Ai), std::move(*Bi));
    115     }
    116     return std::move(cliques);
     42 * Generate a graph G describing the potential applications of the distributive law for the given block.
     43 ** ------------------------------------------------------------------------------------------------------------- */
     44VertexSet generateDistributionGraph(PabloBlock * block, Graph & G) {
     45    Map M;
     46    VertexSet distSet;
     47    for (Statement * stmt : *block) {
     48        if (isa<And>(stmt) || isa<Or>(stmt)) {
     49            const TypeId outerTypeId = stmt->getClassTypeId();
     50            const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
     51            flat_set<PabloAST *> distributable;
     52            for (PabloAST * const expr : *cast<Variadic>(stmt)) {
     53                if (LLVM_UNLIKELY(expr->getClassTypeId() == innerTypeId)) {
     54                    bool safe = true;
     55                    for (PabloAST * const user : expr->users()) {
     56                        if (user->getClassTypeId() != outerTypeId) {
     57                            safe = false;
     58                            break;
     59                        }
     60                    }
     61                    if (safe) {
     62                        distributable.insert(expr);
     63                    }
     64                }
     65            }
     66            if (LLVM_LIKELY(distributable.size() > 1)) {
     67                flat_map<PabloAST *, bool> observedMoreThanOnce;
     68                bool anyOpportunities = false;
     69                for (const PabloAST * distOperation : distributable) {
     70                    for (PabloAST * const distVar : *cast<Variadic>(distOperation)) {
     71                        auto ob = observedMoreThanOnce.find(distVar);
     72                        if (ob == observedMoreThanOnce.end()) {
     73                            observedMoreThanOnce.emplace(distVar, false);
     74                        } else {
     75                            ob->second = true;
     76                            anyOpportunities = true;
     77                        }
     78                    }
     79                }
     80                if (anyOpportunities) {
     81                    for (const auto ob : observedMoreThanOnce) {
     82                        PabloAST * distVar = nullptr;
     83                        bool observedTwice = false;
     84                        std::tie(distVar, observedTwice) = ob;
     85                        if (observedTwice) {
     86                            const Vertex z = getVertex(stmt, G, M);
     87                            distSet.push_back(z);
     88                            for (PabloAST * const distOperation : distVar->users()) {
     89                                if (distributable.count(distOperation)) {
     90                                    const Vertex y = getVertex(distOperation, G, M);
     91                                    add_edge(getVertex(distVar, G, M), y, G);
     92                                    add_edge(y, z, G);
     93                                }
     94                            }
     95                        }
     96                    }
     97                }
     98            }
     99        }
     100    }
     101    return distSet;
    117102}
    118103
     
    191176
    192177/** ------------------------------------------------------------------------------------------------------------- *
     178 * @brief enumerateBicliques
     179 *
     180 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
     181 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in
     182 * bipartition A and their adjacencies to be in B.
     183  ** ------------------------------------------------------------------------------------------------------------- */
     184static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) {
     185    using IntersectionSets = std::set<VertexSet>;
     186
     187    IntersectionSets B1;
     188    for (auto u : A) {
     189        if (in_degree(u, G) > 0) {
     190            VertexSet incomingAdjacencies;
     191            incomingAdjacencies.reserve(in_degree(u, G));
     192            for (auto e : make_iterator_range(in_edges(u, G))) {
     193                incomingAdjacencies.push_back(source(e, G));
     194            }
     195            std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end());
     196            B1.insert(std::move(incomingAdjacencies));
     197        }
     198    }
     199
     200    IntersectionSets B(B1);
     201
     202    IntersectionSets Bi;
     203
     204    VertexSet clique;
     205    for (auto i = B1.begin(); i != B1.end(); ++i) {
     206        for (auto j = i; ++j != B1.end(); ) {
     207            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
     208            if (clique.size() > 0) {
     209                if (B.count(clique) == 0) {
     210                    Bi.insert(clique);
     211                }
     212                clique.clear();
     213            }
     214        }
     215    }
     216
     217    for (;;) {
     218        if (Bi.empty()) {
     219            break;
     220        }
     221        B.insert(Bi.begin(), Bi.end());
     222        IntersectionSets Bk;
     223        for (auto i = B1.begin(); i != B1.end(); ++i) {
     224            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
     225                std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
     226                if (clique.size() > 0) {
     227                    if (B.count(clique) == 0) {
     228                        Bk.insert(clique);
     229                    }
     230                    clique.clear();
     231                }
     232            }
     233        }
     234        Bi.swap(Bk);
     235    }
     236
     237    BicliqueSet cliques;
     238    cliques.reserve(B.size());
     239    for (auto Bi = B.begin(); Bi != B.end(); ++Bi) {
     240        VertexSet Ai(A);
     241        for (const Vertex u : *Bi) {
     242            VertexSet Aj;
     243            Aj.reserve(out_degree(u, G));
     244            for (auto e : make_iterator_range(out_edges(u, G))) {
     245                Aj.push_back(target(e, G));
     246            }
     247            std::sort(Aj.begin(), Aj.end());
     248            VertexSet Ak;
     249            Ak.reserve(std::min(Ai.size(), Aj.size()));
     250            std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak));
     251            Ai.swap(Ak);
     252        }
     253        assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly
     254        cliques.emplace_back(std::move(Ai), std::move(*Bi));
     255    }
     256    return std::move(cliques);
     257}
     258
     259/** ------------------------------------------------------------------------------------------------------------- *
    193260 * @brief removeUnhelpfulBicliques
    194261 *
     
    197264 * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique.
    198265 ** ------------------------------------------------------------------------------------------------------------- */
    199 static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, DistributionGraph & G) {
     266static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, Graph & G) {
    200267    for (auto ci = cliques.begin(); ci != cliques.end(); ) {
    201268        const auto cardinalityA = std::get<0>(*ci).size();
     
    220287 * @brief safeDistributionSets
    221288 ** ------------------------------------------------------------------------------------------------------------- */
    222 static DistributionSets safeDistributionSets(DistributionGraph & G) {
    223 
    224     VertexSet sinks;
    225     for (const auto u : make_iterator_range(vertices(G))) {
    226         if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    227             sinks.push_back(u);
    228         }
    229     }
    230 
     289static DistributionSets safeDistributionSets(Graph & G, const VertexSet & distSet) {
    231290    DistributionSets T;
    232     BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(G, sinks), G), 1);
     291    BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(G, distSet), G), 1);
    233292    for (Biclique & lower : lowerSet) {
    234293        BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(G, std::get<1>(lower)), 2);
     
    241300
    242301/** ------------------------------------------------------------------------------------------------------------- *
    243  * @brief generateDistributionGraph
    244  *
    245  * Generate a graph G describing the potential applications of the distributive law for the given block.
    246  ** ------------------------------------------------------------------------------------------------------------- */
    247 void generateDistributionGraph(PabloBlock * block, DistributionGraph & G) {
    248     DistributionMap M;
     302 * @brief distribute
     303 ** ------------------------------------------------------------------------------------------------------------- */
     304inline bool DistributivePass::distribute(PabloBlock * const block) {
     305
     306    Graph G;
     307
     308    const VertexSet distSet = generateDistributionGraph(block, G);
     309
     310    // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
     311    if (LLVM_UNLIKELY(distSet.empty())) {
     312        return false;
     313    }
     314
     315    const DistributionSets distributionSets = safeDistributionSets(G, distSet);
     316
     317    if (LLVM_UNLIKELY(distributionSets.empty())) {
     318        return false;
     319    }
     320
     321    for (const DistributionSet & set : distributionSets) {
     322
     323        // Each distribution tuple consists of the sources, intermediary, and sink nodes.
     324        const VertexSet & sources = std::get<0>(set);
     325        const VertexSet & intermediary = std::get<1>(set);
     326        const VertexSet & sinks = std::get<2>(set);
     327
     328        // Find the first sink and set the insert point immediately before that.
     329        Variadic * innerOp = nullptr;
     330        Variadic * outerOp = nullptr;
     331
     332        block->setInsertPoint(cast<Variadic>(G[sinks.front()])->getPrevNode());
     333
     334        if (isa<And>(G[sinks.front()])) {
     335            outerOp = block->createAnd(intermediary.size(), PabloBlock::createOnes());
     336            innerOp = block->createOr(sources.size() + 1, outerOp);
     337        } else {
     338            outerOp = block->createOr(intermediary.size(), PabloBlock::createZeroes());
     339            innerOp = block->createAnd(sources.size() + 1, outerOp);
     340        }
     341
     342        unsigned i = 0;
     343        for (const Vertex u : intermediary) {
     344            for (const Vertex v : sinks) {
     345                cast<Variadic>(G[v])->removeOperand(cast<Variadic>(G[u]));
     346            }
     347            outerOp->setOperand(i++, cast<Variadic>(G[u]));
     348        }
     349
     350        i = 0;
     351        for (const Vertex u : sources) {
     352            for (const Vertex v : intermediary) {
     353                cast<Variadic>(G[v])->removeOperand(G[u]);
     354            }
     355            innerOp->setOperand(i++, G[u]);
     356        }
     357        for (const Vertex u : sinks) {
     358            cast<Variadic>(G[u])->addOperand(innerOp);
     359        }
     360    }
     361
     362    return true;
     363}
     364
     365/** ------------------------------------------------------------------------------------------------------------- *
     366 * @brief process
     367 ** ------------------------------------------------------------------------------------------------------------- */
     368bool DistributivePass::process(PabloBlock * const block) {
     369    bool modified = false;
    249370    for (Statement * stmt : *block) {
    250         if (isa<And>(stmt) || isa<Or>(stmt)) {
    251             const TypeId outerTypeId = stmt->getClassTypeId();
    252             const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
    253             flat_set<Variadic *> distributable;
    254             for (PabloAST * const expr : *cast<Variadic>(stmt)) {
    255                 if (LLVM_UNLIKELY(expr->getClassTypeId() == innerTypeId)) {
    256                     bool safe = true;
    257                     for (PabloAST * const user : expr->users()) {
    258                         if (user->getClassTypeId() != outerTypeId) {
    259                             safe = false;
    260                             break;
    261                         }
    262                     }
    263                     if (safe) {
    264                         distributable.insert(cast<Variadic>(expr));
    265                     }
    266                 }
    267             }
    268             if (LLVM_LIKELY(distributable.size() > 1)) {
    269                 flat_map<PabloAST *, bool> observedMoreThanOnce;
    270                 bool anyOpportunities = false;
    271                 for (const Variadic * distOperation : distributable) {
    272                     for (PabloAST * const distVar : *distOperation) {
    273                         auto ob = observedMoreThanOnce.find(distVar);
    274                         if (ob == observedMoreThanOnce.end()) {
    275                             observedMoreThanOnce.emplace(distVar, false);
    276                         } else {
    277                             ob->second = true;
    278                             anyOpportunities = true;
    279                         }
    280                     }
    281                 }
    282                 if (anyOpportunities) {
    283                     for (const auto ob : observedMoreThanOnce) {
    284                         PabloAST * const distVar = nullptr;
    285                         bool observedTwice = false;
    286                         std::tie(distVar, observedTwice) = *ob;
    287                         if (observedTwice) {
    288                             for (PabloAST * const distOperation : distVar->users()) {
    289                                 if (distributable.count(distOperation)) {
    290                                     const Vertex y = getVertex(distOperation, G, M);
    291                                     add_edge(y, getVertex(stmt, G, M), G);
    292                                     add_edge(getVertex(distVar, G, M), y, G);
    293                                 }
    294                             }
    295                         }
    296                     }
    297                 }
    298             }
    299         }
    300     }
    301 }
    302 
    303 /** ------------------------------------------------------------------------------------------------------------- *
    304  * @brief redistributeAST
    305  *
    306  * Apply the distribution law to reduce computations whenever possible.
    307  ** ------------------------------------------------------------------------------------------------------------- */
    308 void DistributivePass::redistributeAST(PabloBlock * block) const {
    309 
    310     std::vector<Vertex> mapping(num_vertices(G) + 16);
    311     std::iota(mapping.begin(), mapping.end(), 0); // 0,1,.....n
    312 
    313     for (;;) {
    314 
    315         DistributionGraph H;
    316 
    317         generateDistributionGraph(block, H);
    318 
    319         // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
    320         if (num_vertices(H) == 0) {
    321             break;
    322         }
    323 
    324         const DistributionSets distributionSets = safeDistributionSets(block, H);
    325 
    326         if (LLVM_UNLIKELY(distributionSets.empty())) {
    327             break;
    328         }
    329 
    330         for (const DistributionSet & set : distributionSets) {
    331 
    332             // Each distribution tuple consists of the sources, intermediary, and sink nodes.
    333             const VertexSet & sources = std::get<0>(set);
    334             const VertexSet & intermediary = std::get<1>(set);
    335             const VertexSet & sinks = std::get<2>(set);
    336 
    337             const TypeId outerTypeId = getType(G[mapping[H[sinks.front()]]]);
    338             assert (outerTypeId == TypeId::And || outerTypeId == TypeId::Or);
    339             const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or;
    340 
    341             // Update G to match the desired change
    342             const Vertex x = addSummaryVertex(outerTypeId, G);
    343             const Vertex y = addSummaryVertex(innerTypeId, G);
    344             mapping.resize(num_vertices(G));
    345             mapping[x] = x;
    346             mapping[y] = y;
    347 
    348             for (const Vertex i : intermediary) {
    349                 const auto u = mapping[H[i]];
    350                 assert (getType(G[u]) == innerTypeId);
    351                 for (const Vertex t : sinks) {
    352                     assert (getType(G[mapping[H[t]]]) == outerTypeId);
    353                     remove_edge(u, mapping[H[t]], G);
    354                 }
    355                 add_edge(nullptr, u, x, G);
    356             }
    357 
    358             for (const Vertex s : sources) {
    359                 const auto u = mapping[H[s]];
    360                 for (const Vertex i : intermediary) {
    361                     remove_edge(u, mapping[H[i]], G);
    362                 }
    363                 add_edge(nullptr, u, y, G);
    364             }
    365             add_edge(nullptr, x, y, G);
    366 
    367             for (const Vertex t : sinks) {
    368                 const auto v = mapping[H[t]];
    369                 add_edge(getValue(G[v]), y, v, G);
    370             }
    371 
    372             summarizeGraph(G, mapping);
    373         }
    374     }
    375 }
    376 
    377 
    378 }
     371        if (isa<If>(stmt) || isa<While>(stmt)) {
     372            modified |= process(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     373        }
     374    }
     375    modified |= distribute(block);
     376    return modified;
     377}
     378
     379/** ------------------------------------------------------------------------------------------------------------- *
     380 * @brief process
     381 ** ------------------------------------------------------------------------------------------------------------- */
     382bool DistributivePass::optimize(PabloFunction & function) {
     383    const bool modified = DistributivePass::process(function.getEntryBlock());
     384    #ifndef NDEBUG
     385    PabloVerifier::verify(function, "post-distribution");
     386    #endif
     387    Simplifier::optimize(function);
     388    return modified;
     389}
     390
     391
     392}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.h

    r4878 r4880  
    55
    66class PabloFunction;
     7class PabloBlock;
     8class Variadic;
    79
    810class DistributivePass {
     
    1012    static bool optimize(PabloFunction & function);
    1113protected:
    12 
     14    static bool process(PabloBlock * const block);
     15    static bool distribute(PabloBlock * const block);
    1316    DistributivePass() = default;
    1417};
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4871 r4880  
    362362
    363363/** ------------------------------------------------------------------------------------------------------------- *
     364 * @brief throwUnexpectedStatementTypeError
     365 ** ------------------------------------------------------------------------------------------------------------- */
     366static void throwUnexpectedStatementTypeError(const Statement * const stmt) {
     367    std::string tmp;
     368    raw_string_ostream err(tmp);
     369    err << "Unexpected statement type ";
     370    PabloPrinter::print(stmt, err);
     371    throw std::runtime_error(err.str());
     372}
     373
     374/** ------------------------------------------------------------------------------------------------------------- *
    364375 * @brief characterize
    365376 ** ------------------------------------------------------------------------------------------------------------- */
    366377inline BDD AutoMultiplexing::characterize(Statement * const stmt) {
    367 
    368     // Map our operands to the computed BDDs
    369     std::array<BDD, 3> input;
    370     for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    371         PabloAST * const op = stmt->getOperand(i);
    372         if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
    373             continue;
    374         }
    375         input[i] = get(op);
    376     }
    377 
    378     BDD bdd = bdd_zero();
     378    BDD bdd = get(stmt->getOperand(0));
    379379    switch (stmt->getClassTypeId()) {
    380380        case TypeId::Assign:
    381381        case TypeId::Next:
    382             bdd = input[0];
    383382            break;
    384383        case TypeId::And:
    385             bdd = bdd_and(input[0], input[1]);
     384            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
     385                bdd = bdd_and(bdd, get(stmt->getOperand(i)));
     386            }
    386387            break;
    387388        case TypeId::Or:
    388             bdd = bdd_or(input[0], input[1]);
     389            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
     390                bdd = bdd_or(bdd, get(stmt->getOperand(i)));
     391            }
    389392            break;
    390393        case TypeId::Xor:
    391             bdd = bdd_xor(input[0], input[1]);
     394            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
     395                bdd = bdd_xor(bdd, get(stmt->getOperand(i)));
     396            }
    392397            break;
    393398        case TypeId::Not:
    394             bdd = bdd_not(input[0]);
     399            bdd = bdd_not(bdd);
    395400            break;
    396401        case TypeId::Sel:
    397             bdd = bdd_ite(input[0], input[1], input[2]);
     402            bdd = bdd_ite(bdd, get(stmt->getOperand(1)), get(stmt->getOperand(2)));
    398403            break;
    399404        case TypeId::ScanThru:
     
    404409            return bdd_ithvar(mVariables++);
    405410        case TypeId::Advance:
    406             return characterize(cast<Advance>(stmt), input[0]);
     411            return characterize(cast<Advance>(stmt), bdd);
    407412        default:
    408             throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
     413            throwUnexpectedStatementTypeError(stmt);
    409414    }
    410415    return bdd_addref(bdd);
     
    417422
    418423    const auto k = mAdvanceAttributes.size();
    419 
    420424    std::vector<bool> unconstrained(k , false);
    421425
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4870 r4880  
    145145
    146146/** ------------------------------------------------------------------------------------------------------------- *
     147 * @brief throwUnexpectedStatementTypeError
     148 ** ------------------------------------------------------------------------------------------------------------- */
     149static void throwUnexpectedStatementTypeError(const Statement * const stmt) {
     150    std::string tmp;
     151    raw_string_ostream err(tmp);
     152    err << "Unexpected statement type ";
     153    PabloPrinter::print(stmt, err);
     154    throw std::runtime_error(err.str());
     155}
     156
     157/** ------------------------------------------------------------------------------------------------------------- *
    147158 * @brief characterize
    148159 ** ------------------------------------------------------------------------------------------------------------- */
    149160inline std::pair<BDD, bool> BDDMinimizationPass::characterize(Statement * const stmt) {
    150 
    151     BDD bdd = bdd_zero();
    152     // Map our operands to the computed BDDs
    153     std::array<BDD, 3> input;
    154     for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    155         PabloAST * const op = stmt->getOperand(i);
    156         if (op == nullptr) {
    157             throw std::runtime_error("Statement has Null operand!");
    158         }
    159         if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
    160             continue;
    161         }
    162         auto f = mCharacterizationMap.find(op);
    163         if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
    164             std::string tmp;
    165             llvm::raw_string_ostream msg(tmp);
    166             msg << "BDDMinimizationPass: uncharacterized operand " << std::to_string(i) << " of ";
    167             PabloPrinter::print(stmt, msg);
    168             throw std::runtime_error(msg.str());
    169         }
    170         input[i] = f->second;
    171     }
    172 
     161    BDD bdd = get(stmt->getOperand(0));
    173162    switch (stmt->getClassTypeId()) {
    174163        case TypeId::Assign:
    175164        case TypeId::Next:
    176             return std::make_pair(input[0], false);
     165            break;
    177166        case TypeId::And:
    178             bdd = bdd_and(input[0], input[1]);
     167            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
     168                bdd = bdd_and(bdd, get(stmt->getOperand(i)));
     169            }
    179170            break;
    180171        case TypeId::Or:
    181             bdd = bdd_or(input[0], input[1]);
     172            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
     173                bdd = bdd_or(bdd, get(stmt->getOperand(i)));
     174            }
    182175            break;
    183176        case TypeId::Xor:
    184             bdd = bdd_xor(input[0], input[1]);
     177            for (unsigned i = 1; i != stmt->getNumOperands(); ++i) {
     178                bdd = bdd_xor(bdd, get(stmt->getOperand(i)));
     179            }
    185180            break;
    186181        case TypeId::Not:
    187             bdd = bdd_not(input[0]);
     182            bdd = bdd_not(bdd);
    188183            break;
    189184        case TypeId::Sel:
    190             bdd = bdd_ite(input[0], input[1], input[2]);
     185            bdd = bdd_ite(bdd, get(stmt->getOperand(1)), get(stmt->getOperand(2)));
    191186            break;
    192187        case TypeId::MatchStar:
    193188        case TypeId::ScanThru:
    194             if (LLVM_UNLIKELY(input[1] == bdd_zero())) {
    195                 bdd = input[0];
     189            if (LLVM_UNLIKELY(get(stmt->getOperand(1)) == bdd_zero())) {
     190                break;
    196191            }
    197192        case TypeId::Advance:
    198             if (LLVM_UNLIKELY(input[0] == bdd_zero())) {
     193            if (LLVM_UNLIKELY(bdd == bdd_zero())) {
    199194                return std::make_pair(bdd_zero(), true);
    200195            }
     
    203198            return std::make_pair(bdd_ithvar(mVariables++), false);
    204199        default:
    205             throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
     200            throwUnexpectedStatementTypeError(stmt);
    206201    }
    207202    bdd_addref(bdd);
     
    213208}
    214209
     210/** ------------------------------------------------------------------------------------------------------------- *
     211 * @brief throwUnexpectedStatementTypeError
     212 ** ------------------------------------------------------------------------------------------------------------- */
     213static void throwUncharacterizedOperand(const PabloAST * const expr) {
     214    std::string tmp;
     215    raw_string_ostream err(tmp);
     216    err << "Uncharacterized operand ";
     217    PabloPrinter::print(expr, err);
     218    throw std::runtime_error(err.str());
     219}
     220
     221/** ------------------------------------------------------------------------------------------------------------- *
     222 * @brief get
     223 ** ------------------------------------------------------------------------------------------------------------- */
     224inline BDD & BDDMinimizationPass::get(const PabloAST * const expr) {
     225    auto f = mCharacterizationMap.find(expr);
     226    if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
     227        throwUncharacterizedOperand(expr);
     228    }
     229    return f->second;
     230}
     231
    215232} // end of namespace pablo
    216233
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4870 r4880  
    4545    void eliminateLogicallyEquivalentStatements(Statement * const stmt, SubsitutionMap & map);
    4646    std::pair<BDD, bool> characterize(Statement * const stmt);
     47    BDD & get(const PabloAST * const expr);
    4748private:
    4849    unsigned                        mVariables;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4878 r4880  
    2828    eliminateRedundantCode(function.getEntryBlock());
    2929    deadCodeElimination(function.getEntryBlock());
    30     eliminateRedundantEquations(function.getEntryBlock());
     30    strengthReduction(function.getEntryBlock());
    3131    #ifndef NDEBUG
    3232    PabloVerifier::verify(function, "post-simplification");
     
    440440
    441441/** ------------------------------------------------------------------------------------------------------------- *
    442  * @brief eliminateRedundantEquations
    443  ** ------------------------------------------------------------------------------------------------------------- */
    444 void Simplifier::eliminateRedundantEquations(PabloBlock * const block) {
     442 * @brief strengthReduction
     443 *
     444 * Find and replace any Pablo operations with the less expensive equivalent operations whenever possible.
     445 ** ------------------------------------------------------------------------------------------------------------- */
     446void Simplifier::strengthReduction(PabloBlock * const block) {
    445447    Statement * stmt = block->front();
    446448    while (stmt) {
    447449        if (isa<If>(stmt)) {
    448             eliminateRedundantEquations(cast<If>(stmt)->getBody());
     450            strengthReduction(cast<If>(stmt)->getBody());
    449451        } else if (isa<While>(stmt)) {
    450             eliminateRedundantEquations(cast<While>(stmt)->getBody());
     452            strengthReduction(cast<While>(stmt)->getBody());
    451453        } else if (isa<Advance>(stmt)) {
    452454            Advance * adv = cast<Advance>(stmt);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4878 r4880  
    1818    static PabloAST * foldReassociativeFunction(Variadic * const var, PabloBlock * const block);
    1919    static void deadCodeElimination(PabloBlock * const block);
    20     static void eliminateRedundantEquations(PabloBlock * const block);
     20    static void strengthReduction(PabloBlock * const block);
    2121    static bool isSuperfluous(const Assign * const assign);
    2222};
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4878 r4880  
    303303    PabloAST * removeOperand(const unsigned index);
    304304
     305    unsigned removeOperand(const PabloAST * const expr);
     306
    305307    iterator begin() {
    306308        return iterator(mOperand);
     
    603605}
    604606
     607/** ------------------------------------------------------------------------------------------------------------- *
     608 * @brief removeOperand
     609 ** ------------------------------------------------------------------------------------------------------------- */
     610inline unsigned Variadic::removeOperand(const PabloAST * const expr) {
     611    for (unsigned i = 0; i != getNumOperands(); ++i) {
     612        if (getOperand(i) == expr) {
     613            removeOperand(i);
     614            return i;
     615        }
     616    }
     617    return -1;
    605618}
    606619
     620}
     621
    607622#endif // PE_PabloAST_H
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp

    r4878 r4880  
    66#include <boost/graph/adjacency_list.hpp>
    77#include <pablo/analysis/pabloverifier.hpp>
    8 
    9 #include <boost/graph/strong_components.hpp>
     8#include <pablo/optimizers/distributivepass.h>
     9
     10
    1011#include <pablo/printer_pablos.h>
    1112#include <iostream>
     
    109110        std::sort(extractedVar->begin(), extractedVar->end());
    110111        var->addOperand(block->createNot(extractedVar));
    111         std::sort(var->begin(), var->end());
    112     }
    113 }
    114 
    115 /** ------------------------------------------------------------------------------------------------------------- *
    116  * @brief removeCommonCalculation
    117  ** ------------------------------------------------------------------------------------------------------------- */
    118 inline void FlattenAssociativeDFG::removeCommonCalculation(Assign * const def) {
     112    }
     113}
     114
     115/** ------------------------------------------------------------------------------------------------------------- *
     116 * @brief removeCommonLiterals
     117 ** ------------------------------------------------------------------------------------------------------------- */
     118inline void FlattenAssociativeDFG::removeCommonLiterals(Assign * const def) {
    119119    PabloAST * op = def->getOperand(0);
    120120    if (isa<And>(op) || isa<Or>(op) || isa<Xor>(op)) {
    121         Variadic * const var = cast<Variadic>(op);
    122         std::vector<PabloAST *> common(var->begin(), var->end());
    123         std::vector<PabloAST *> temp;
    124         temp.reserve(common.size());
    125         for (PabloAST * user : def->users()) {
    126             if (user->getClassTypeId() != var->getClassTypeId()) {
    127                 if (isa<If>(user)) {
    128                     continue;
    129                 }
    130                 return;
     121        removeCommonLiterals(def, cast<Variadic>(op));
     122    }
     123}
     124
     125/** ------------------------------------------------------------------------------------------------------------- *
     126 * @brief removeCommonLiterals
     127 ** ------------------------------------------------------------------------------------------------------------- */
     128void FlattenAssociativeDFG::removeCommonLiterals(Statement * input, Variadic * var) {
     129    std::vector<PabloAST *> common(var->begin(), var->end());
     130    std::vector<PabloAST *> temp;
     131    temp.reserve(common.size());
     132    for (PabloAST * user : input->users()) {
     133        if (user->getClassTypeId() != var->getClassTypeId()) {
     134            if (isa<If>(user) && (input != cast<If>(user)->getCondition())) {
     135                continue;
    131136            }
    132             std::set_intersection(common.begin(), common.end(), cast<Variadic>(user)->begin(), cast<Variadic>(user)->end(), std::back_inserter(temp));
    133             common.swap(temp);
    134             temp.clear();
    135         }
    136         for (PabloAST * op : common) {
    137             for (unsigned i = 0; i != var->getNumOperands(); ++i) {
    138                 if (var->getOperand(i) == op) {
    139                     var->removeOperand(i);
    140                     break;
    141                 }
    142             }
     137            return;
     138        }
     139        std::set_intersection(common.begin(), common.end(), cast<Variadic>(user)->begin(), cast<Variadic>(user)->end(), std::back_inserter(temp));
     140        common.swap(temp);
     141        temp.clear();
     142    }
     143    for (PabloAST * op : common) {
     144        var->removeOperand(op);
     145    }
     146}
     147
     148/** ------------------------------------------------------------------------------------------------------------- *
     149 * @brief removeCommonLiterals
     150 ** ------------------------------------------------------------------------------------------------------------- */
     151inline void FlattenAssociativeDFG::removeCommonLiterals(PabloBlock * const block) {
     152    for (Statement * stmt : *block) {
     153        if (isa<If>(stmt) || isa<While>(stmt)) {
     154            removeCommonLiterals(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     155        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
     156            removeCommonLiterals(cast<Variadic>(stmt), cast<Variadic>(stmt));
     157        } else if (isa<Assign>(stmt)) {
     158            removeCommonLiterals(cast<Assign>(stmt));
    143159        }
    144160    }
     
    148164 * @brief extract
    149165 ** ------------------------------------------------------------------------------------------------------------- */
    150 void FlattenAssociativeDFG::extract(PabloBlock * const block) {
    151     Statement * stmt = block->front();
    152     while (stmt) {
     166inline void FlattenAssociativeDFG::extract(PabloBlock * const block) {
     167    for (Statement * stmt : *block) {
    153168        if (isa<If>(stmt) || isa<While>(stmt)) {
    154169            extract(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    155170        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
    156171            extractNegationsOutwards(cast<Variadic>(stmt), block);
    157         } else if (isa<Assign>(stmt)) {
    158             removeCommonCalculation(cast<Assign>(stmt));
    159         }
    160         stmt = stmt->getNextNode();
     172        }
    161173    }
    162174}
     
    167179void FlattenAssociativeDFG::transform(PabloFunction & function) {
    168180
    169     FlattenAssociativeDFG::flatten(function.getEntryBlock());
    170     #ifndef NDEBUG
    171     PabloVerifier::verify(function, "post-flatten");
    172     #endif
    173     Simplifier::optimize(function);
    174 
    175     FlattenAssociativeDFG::extract(function.getEntryBlock());
    176     #ifndef NDEBUG
    177     PabloVerifier::verify(function, "post-extract");
    178     #endif
    179     Simplifier::optimize(function);
    180 
    181 }
    182 
    183 }
     181    for (;;) {
     182
     183        FlattenAssociativeDFG::flatten(function.getEntryBlock());
     184        #ifndef NDEBUG
     185        PabloVerifier::verify(function, "post-flatten");
     186        #endif
     187        FlattenAssociativeDFG::removeCommonLiterals(function.getEntryBlock());
     188        #ifndef NDEBUG
     189        PabloVerifier::verify(function, "post-remove-common-literals");
     190        #endif
     191
     192        Simplifier::optimize(function);
     193
     194        const bool distributed = DistributivePass::optimize(function);
     195
     196        FlattenAssociativeDFG::extract(function.getEntryBlock());
     197        #ifndef NDEBUG
     198        PabloVerifier::verify(function, "post-extract");
     199        #endif
     200        Simplifier::optimize(function);
     201
     202        if (distributed == 0) {
     203            break;
     204        }
     205    }
     206
     207    if (DistributivePass::optimize(function)) {
     208        throw std::runtime_error("Some distributions remained!");
     209    }
     210
     211}
     212
     213}
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.h

    r4878 r4880  
    66class PabloFunction;
    77class PabloBlock;
     8class Statement;
    89class Variadic;
    910class Not;
    1011class Assign;
    11 
    1212
    1313class FlattenAssociativeDFG {
     
    2020    static void applyNegationInwards(Not * const var, PabloBlock * const block);
    2121
     22    static void removeCommonLiterals(PabloBlock * const block);
     23    static void removeCommonLiterals(Assign * const def);
     24    static void removeCommonLiterals(Statement * input, Variadic * var);
     25
    2226    static void extract(PabloBlock * const block);
    2327    static void extractNegationsOutwards(Variadic * const var, PabloBlock * const block);
    24     static void removeCommonCalculation(Assign * const def);
    2528
    2629    FlattenAssociativeDFG() = default;
Note: See TracChangeset for help on using the changeset viewer.