Ignore:
Timestamp:
Feb 12, 2016, 4:44:35 PM (4 years ago)
Author:
nmedfort
Message:

Bug fixes

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
8 edited

Legend:

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

    r4919 r4927  
    33#include <pablo/analysis/pabloverifier.hpp>
    44#include <boost/container/flat_set.hpp>
     5#include <boost/container/flat_map.hpp>
     6#include <boost/graph/adjacency_list.hpp>
     7#include <boost/graph/topological_sort.hpp>
     8#include <boost/circular_buffer.hpp>
    59
    610using namespace boost;
     
    1317 ** ------------------------------------------------------------------------------------------------------------- */
    1418bool CodeMotionPass::optimize(PabloFunction & function) {
    15     CodeMotionPass::global(function.getEntryBlock());
     19    CodeMotionPass::movement(function.getEntryBlock());
    1620    #ifndef NDEBUG
    1721    PabloVerifier::verify(function, "post-code-motion");
     
    2125
    2226/** ------------------------------------------------------------------------------------------------------------- *
    23  * @brief process
    24  ** ------------------------------------------------------------------------------------------------------------- */
    25 void CodeMotionPass::global(PabloBlock * const block) {
     27 * @brief movement
     28 ** ------------------------------------------------------------------------------------------------------------- */
     29void CodeMotionPass::movement(PabloBlock * const block) {
    2630    sink(block);
    2731    for (Statement * stmt : *block) {
    2832        if (isa<If>(stmt)) {
    29             global(cast<If>(stmt)->getBody());
     33            movement(cast<If>(stmt)->getBody());
    3034        } else if (isa<While>(stmt)) {
    31             global(cast<While>(stmt)->getBody());
     35            movement(cast<While>(stmt)->getBody());
    3236            // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
    3337            // determine whether hoisting will helpful or harmful to the expected run time.
     
    3539        }
    3640    }
     41    reschedule(block);
    3742}
    3843
     
    4752 * @brief calculateDepthToCurrentBlock
    4853 ** ------------------------------------------------------------------------------------------------------------- */
    49 inline static unsigned calculateDepthToCurrentBlock(const PabloBlock * scope, const PabloBlock * const root) {
     54inline static unsigned depthTo(const PabloBlock * scope, const PabloBlock * const root) {
    5055    unsigned depth = 0;
    5156    while (scope != root) {
     
    103108 * @brief sink
    104109 ** ------------------------------------------------------------------------------------------------------------- */
    105 void CodeMotionPass::sink(PabloBlock * const block) {
     110inline void CodeMotionPass::sink(PabloBlock * const block) {
    106111    ScopeSet scopes;
    107112    Statement * stmt = block->back(); // note: reverse AST traversal
     
    113118                // Find the LCA of both scopes then add the LCA back to the list of scopes.
    114119                PabloBlock * scope1 = scopes.back(); scopes.pop_back();
    115                 unsigned depth1 = calculateDepthToCurrentBlock(scope1, block);
     120                unsigned depth1 = depthTo(scope1, block);
    116121
    117122                PabloBlock * scope2 = scopes.back(); scopes.pop_back();
    118                 unsigned depth2 = calculateDepthToCurrentBlock(scope2, block);
     123                unsigned depth2 = depthTo(scope2, block);
    119124
    120125                // If one of these scopes is nested deeper than the other, scan upwards through
     
    194199}
    195200
    196 }
     201/** ------------------------------------------------------------------------------------------------------------- *
     202 * @brief reschedule
     203 ** ------------------------------------------------------------------------------------------------------------- */
     204void CodeMotionPass::reschedule(PabloBlock * const block) {
     205
     206//    using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, Statement *>;
     207//    using Vertex = Graph::vertex_descriptor;
     208//    using Map = flat_map<Statement *, Vertex>;
     209
     210//    const unsigned size = std::distance(block->begin(), block->end());
     211
     212//    Graph G(size);
     213//    Map M;
     214
     215//    M.reserve(size);
     216
     217//    unsigned i = 0;
     218//    for (Statement * stmt : *block) {
     219//        G[i] = stmt;
     220//        M.emplace(stmt, i);
     221//        ++i;
     222//    }
     223
     224//    i = 0;
     225//    for (Statement * stmt : *block) {
     226//        for (PabloAST * user : stmt->users()) {
     227//            if (isa<Statement>(user)) {
     228//                Statement * use = cast<Statement>(user);
     229//                PabloBlock * parent = use->getParent();
     230//                while (parent) {
     231//                    if (parent == block) {
     232//                        break;
     233//                    }
     234//                    use = parent->getBranch();
     235//                    parent = parent->getParent();
     236//                }
     237//                auto f = M.find(use);
     238//                assert (f != M.end());
     239//                add_edge(i, f->second, G);
     240//            }
     241//        }
     242//        ++i;
     243//    }
     244
     245//    circular_buffer<Vertex> ordering(size);
     246//    std::vector<unsigned> cumulativeDependencies;
     247//    topological_sort(G, std::back_inserter(ordering));
     248   
     249
     250
     251}
     252
     253}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.h

    r4919 r4927  
    3131    static bool optimize(PabloFunction & function);
    3232protected:
    33     static void global(PabloBlock * const block);
     33    static void movement(PabloBlock * const block);
    3434    static bool isAcceptableTarget(Statement *stmt, ScopeSet & scopeSet, const PabloBlock * const block);
    3535    static void sink(PabloBlock * const block);
    3636    static void hoistLoopInvariants(While * loop);
     37
     38    static void reschedule(PabloBlock * const block);
    3739};
    3840
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r4922 r4927  
    377377inline void DistributivePass::distribute(Variadic * const var) {
    378378
    379     std::vector<Variadic *> Q;
     379
    380380
    381381    assert (isa<And>(var) || isa<Or>(var));
    382 
    383     Q.push_back(var);
    384382
    385383    Graph G;
    386384    VertexSet A;
    387385
     386    std::vector<Variadic *> Q = {var};
     387
    388388    while (Q.size() > 0) {
    389 
    390         Variadic * expr = CanonicalizeDFG::canonicalize(Q.back());
    391         Q.pop_back();
     389        Variadic * expr = CanonicalizeDFG::canonicalize(Q.back()); Q.pop_back();
    392390        PabloAST * const replacement = Simplifier::fold(expr, expr->getParent());
    393391        if (LLVM_UNLIKELY(replacement != nullptr)) {
     
    427425                const VertexSet & sinks = std::get<2>(set);
    428426                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 
    432427
    433428                for (const Vertex u : intermediary) {
     
    465460                Q.push_back(innerOp);
    466461                Q.push_back(outerOp);
     462
     463                unmodified = false;
    467464            }
    468465
     
    471468        }
    472469    }
     470
    473471}
    474472
     
    477475 ** ------------------------------------------------------------------------------------------------------------- */
    478476void DistributivePass::distribute(PabloBlock * const block) {
    479     for (Statement * stmt : *block) {
     477    Statement * stmt = block->front();
     478    while (stmt) {
     479        Statement * next = stmt->getNextNode();
    480480        if (isa<If>(stmt) || isa<While>(stmt)) {
    481481            distribute(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     
    483483            distribute(cast<Variadic>(stmt));
    484484        }
     485        stmt = next;
    485486    }
    486487}
     
    489490 * @brief optimize
    490491 ** ------------------------------------------------------------------------------------------------------------- */
    491 void DistributivePass::optimize(PabloFunction & function) {
    492     DistributivePass::distribute(function.getEntryBlock());
    493     #ifndef NDEBUG
    494     PabloVerifier::verify(function, "post-distribution");
    495     #endif
    496     Simplifier::optimize(function);
    497 }
    498 
    499 
    500 }
     492bool DistributivePass::optimize(PabloFunction & function) {
     493    DistributivePass dp;
     494    unsigned rounds = 0;
     495    for (;;) {
     496        dp.unmodified = true;
     497        dp.distribute(function.getEntryBlock());
     498        if (dp.unmodified) {
     499            break;
     500        }
     501        ++rounds;
     502        #ifndef NDEBUG
     503        PabloVerifier::verify(function, "post-distribution");
     504        #endif
     505        Simplifier::optimize(function);
     506    }
     507    return rounds > 0;
     508}
     509
     510
     511}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.h

    r4922 r4927  
    1010class DistributivePass {
    1111public:
    12     static void optimize(PabloFunction & function);
     12    static bool optimize(PabloFunction & function);
    1313protected:
    14     static void distribute(PabloBlock * const block);
    15     static void distribute(Variadic * const expr);
     14    void distribute(PabloBlock * const block);
     15    void distribute(Variadic * const var);
    1616    DistributivePass() = default;
     17private:
     18    bool unmodified;
    1719};
    1820
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4919 r4927  
    1717#include <bdd.h>
    1818
    19 /// TODO: Investigate why ./icgrep -c -multiplexing-window-size=13,14...,20 "^\p{l}$" causes segfault in BuDDy.
    20 
    2119using namespace llvm;
    2220using namespace boost;
    2321using namespace boost::container;
    2422using namespace boost::numeric::ublas;
     23
     24/// Interesting test case: ./icgrep '[\p{Lm}\p{Meetei_Mayek}]' -disable-if-hierarchy-strategy
    2525
    2626// #define PRINT_DEBUG_OUTPUT
     
    115115    std::random_device rd;
    116116    const RNG::result_type seed = rd();
    117     // const RNG::result_type seed = 83234827342;
     117//    const RNG::result_type seed = 83234827342;
    118118
    119119    LOG("Seed:                    " << seed);
     
    181181        mp.multiplexSelectedSets(function);
    182182        RECORD_TIMESTAMP(end_select_independent_sets);
    183         LOG("SelectedIndependentSets:  " << (end_select_independent_sets - start_select_independent_sets));
    184 
    185         RECORD_TIMESTAMP(start_topological_sort);
    186         MultiplexingPass::topologicalSort(function);
    187         RECORD_TIMESTAMP(end_topological_sort);
    188         LOG("TopologicalSort:          " << (end_topological_sort - start_topological_sort));
     183        LOG("MultiplexSelectedSets:    " << (end_select_independent_sets - start_select_independent_sets));
    189184
    190185        #ifndef NDEBUG
     
    954949 * @brief multiplexSelectedSets
    955950 ** ------------------------------------------------------------------------------------------------------------- */
    956 void MultiplexingPass::multiplexSelectedSets(PabloFunction &) {
     951void MultiplexingPass::multiplexSelectedSets(PabloFunction & function) {
     952    flat_set<PabloBlock *> modified;
    957953    const auto first_set = num_vertices(mConstraintGraph);
    958954    const auto last_set = num_vertices(mMultiplexSetGraph);
     
    971967            Advance * const adv = input[0];
    972968            PabloBlock * const block = adv->getParent(); assert (block);
     969            modified.insert(block);
     970
     971            circular_buffer<PabloAST *> Q(n);
     972
     973            PabloBuilder builder(block);
    973974            block->setInsertPoint(nullptr);
    974             circular_buffer<PabloAST *> Q(n);
    975             PabloBuilder builder(block);
    976975            /// Perform n-to-m Multiplexing           
    977             for (size_t j = 0; j != m; ++j) {
     976            for (size_t j = 0; j != m; ++j) {               
    978977                std::ostringstream prefix;
    979                 prefix << "mux" << n << "to" << m << '.' << (j + 1);
    980 //                Or * muxing = block->createOr(n);
    981 //                for (size_t i = 0; i != n; ++i) {
    982 //                    if (((i + 1) & (1UL << j)) != 0) {
    983 //                        assert (input[i]->getParent() == block);
    984 //                        muxing->addOperand(input[i]->getOperand(0));
    985 //                    }
    986 //                }
     978                prefix << "mux" << n << "to" << m << '.' << (j);
     979                assert (Q.empty());
    987980                for (size_t i = 0; i != n; ++i) {
    988981                    if (((i + 1) & (1UL << j)) != 0) {
     
    995988                    Q.push_back(builder.createOr(a, b));
    996989                }
    997                 PabloAST * muxing =  Q.front(); Q.clear();
     990                PabloAST * const muxing =  Q.front(); Q.clear();
    998991                muxed[j] = builder.createAdvance(muxing, adv->getOperand(1), prefix.str());
    999992                muxed_n[j] = builder.createNot(muxed[j]);
    1000993            }
    1001             /// Perform m-to-n Demultiplexing           
     994            /// Perform m-to-n Demultiplexing
     995            block->setInsertPoint(block->back());
    1002996            for (size_t i = 0; i != n; ++i) {
    1003997                // Construct the demuxed values and replaces all the users of the original advances with them.
     
    10071001                }
    10081002                while (Q.size() > 1) {
    1009                     PabloAST * a = Q.front(); Q.pop_front();
    1010                     PabloAST * b = Q.front(); Q.pop_front();
     1003                    PabloAST * const a = Q.front(); Q.pop_front();
     1004                    PabloAST * const b = Q.front(); Q.pop_front();
    10111005                    Q.push_back(builder.createAnd(a, b));
    10121006                }
    1013                 PabloAST * demuxed =  Q.front(); Q.clear();
    1014 //                And * demuxed = block->createAnd(m);
    1015 //                for (size_t j = 0; j != m; ++j) {
    1016 //                    demuxed->addOperand((((i + 1) & (1UL << j)) != 0) ? muxed[j] : muxed_n[j]);
    1017 //                }
     1007                PabloAST * const demuxed =  Q.front(); Q.clear();
    10181008                input[i]->replaceWith(demuxed, true, true);
    10191009            }
    10201010        }
     1011    }
     1012    for (PabloBlock * block : modified) {
     1013        topologicalSort(block);
    10211014    }
    10221015}
     
    10651058
    10661059/** ------------------------------------------------------------------------------------------------------------- *
    1067  * @brief OrderingVerifier
    1068  ** ------------------------------------------------------------------------------------------------------------- */
    1069 struct OrderingVerifier {
    1070     OrderingVerifier() : mParent(nullptr) {}
    1071     OrderingVerifier(const OrderingVerifier & parent) : mParent(&parent) {}
    1072     bool count(const PabloAST * expr) const {
    1073         if (mSet.count(expr)) {
    1074             return true;
    1075         } else if (mParent) {
    1076             return mParent->count(expr);
    1077         }
    1078         return false;
    1079     }
    1080     void insert(const PabloAST * expr) {
    1081         mSet.insert(expr);
    1082     }
    1083 private:
    1084     const OrderingVerifier * const mParent;
    1085     std::unordered_set<const PabloAST *> mSet;
    1086 };
    1087 
    1088 /** ------------------------------------------------------------------------------------------------------------- *
    10891060 * @brief topologicalSort
    10901061 ** ------------------------------------------------------------------------------------------------------------- */
    1091 void MultiplexingPass::topologicalSort(PabloFunction & function) {
    1092     OrderingVerifier set;
    1093     set.insert(PabloBlock::createZeroes());
    1094     set.insert(PabloBlock::createOnes());
    1095     for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
    1096         set.insert(function.getParameter(i));
    1097     }
    1098     topologicalSort(function.getEntryBlock(), set);
    1099 }
    1100 
    1101 /** ------------------------------------------------------------------------------------------------------------- *
    1102  * @brief topologicalSort
    1103  ** ------------------------------------------------------------------------------------------------------------- */
    1104 void MultiplexingPass::topologicalSort(PabloBlock * block, OrderingVerifier & parent) {
    1105     OrderingVerifier encountered(parent);
    1106     for (Statement * stmt = block->front(); stmt; ) {
     1062void MultiplexingPass::topologicalSort(PabloBlock * const block) {
     1063
     1064    using Vertex = OrderingGraph::vertex_descriptor;
     1065
     1066    OrderingGraph G;
     1067    OrderingMap M;
     1068
     1069    for (Statement * stmt : *block ) {
     1070        const auto u = add_vertex(G);
     1071        G[u] = stmt;
     1072        M.emplace(stmt, u);
    11071073        if (LLVM_UNLIKELY(isa<If>(stmt))) {
    1108             topologicalSort(cast<If>(stmt)->getBody(), encountered);
    11091074            for (Assign * def : cast<If>(stmt)->getDefined()) {
    1110                 encountered.insert(def);
     1075                M.emplace(def, u);
    11111076            }
    11121077        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    1113             topologicalSort(cast<While>(stmt)->getBody(), encountered);
    11141078            for (Next * var : cast<While>(stmt)->getVariants()) {
    1115                 encountered.insert(var);
    1116             }
    1117         }
    1118         bool unmodified = true;
     1079                M.emplace(var, u);
     1080            }
     1081        }
     1082    }
     1083
     1084    Vertex u = 0;
     1085    for (Statement * stmt : *block ) {
     1086
    11191087        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    11201088            PabloAST * const op = stmt->getOperand(i);
    1121             if (LLVM_UNLIKELY(encountered.count(op) == 0 && isa<Statement>(op))) {
    1122                 Statement * const next = stmt->getNextNode();
    1123                 Statement * pos = cast<Statement>(op);
    1124                 if (cast<Statement>(op)->getParent() != block) {
    1125                     // If we haven't already encountered the Assign or Next node, it must come from a If or
    1126                     // While node that we haven't processed yet. Scan ahead and try to locate it.
    1127                     pos = nullptr;
    1128                     if (isa<Assign>(pos)) {
    1129                         for (pos = cast<Statement>(op); pos; pos = pos->getNextNode()) {
    1130                             if (LLVM_UNLIKELY(isa<If>(pos))) {
    1131                                 const auto & defs = cast<If>(pos)->getDefined();
    1132                                 if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), op) != defs.end())) {
    1133                                     break;
    1134                                 }
    1135                             }
    1136                         }
    1137                     } else if (isa<Next>(pos)) {
    1138                         for (pos = cast<Statement>(op); pos; pos = pos->getNextNode()) {
    1139                             if (LLVM_UNLIKELY(isa<While>(pos))) {
    1140                                 const auto & vars = cast<While>(pos)->getVariants();
    1141                                 if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), op) != vars.end())) {
    1142                                     break;
    1143                                 }
    1144                             }
    1145                         }
    1146                     }
    1147                     if (LLVM_UNLIKELY(pos == nullptr)) {
    1148                         throw std::runtime_error("Unexpected error: MultiplexingPass failed to topologically sort the function!");
    1149                     }
    1150                 }
    1151                 stmt->insertAfter(pos);
    1152                 stmt = next;
    1153                 unmodified = false;
    1154                 break;
    1155             }
    1156         }
    1157         if (unmodified) {
    1158             encountered.insert(stmt);
    1159             stmt = stmt->getNextNode();
     1089            if (isa<Statement>(op)) {
     1090                auto f = M.find(cast<Statement>(op));
     1091                if (f != M.end()) {
     1092                    add_edge(f->second, u, G);
     1093                }
     1094            }
     1095        }
     1096
     1097        if (LLVM_UNLIKELY(isa<If>(stmt))) {
     1098            for (Assign * def : cast<If>(stmt)->getDefined()) {
     1099                topologicalSort(u, block, def, G, M);
     1100            }
     1101        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
     1102            for (Next * var : cast<While>(stmt)->getVariants()) {
     1103                topologicalSort(u, block, var, G, M);
     1104            }
     1105        } else {
     1106            topologicalSort(u, block, stmt, G, M);
     1107        }
     1108
     1109        ++u;
     1110
     1111    }
     1112
     1113    circular_buffer<Vertex> Q(num_vertices(G));
     1114    topological_sort(G, std::back_inserter(Q));
     1115
     1116    block->setInsertPoint(nullptr);
     1117    while (Q.size() > 0) {
     1118        const Vertex u = Q.back(); Q.pop_back();
     1119        block->insert(G[u]);
     1120    }
     1121
     1122}
     1123
     1124/** ------------------------------------------------------------------------------------------------------------- *
     1125 * @brief topologicalSort
     1126 ** ------------------------------------------------------------------------------------------------------------- */
     1127void MultiplexingPass::topologicalSort(const OrderingGraph::vertex_descriptor u, const PabloBlock * const block, const Statement * const stmt, OrderingGraph & G, OrderingMap & M) {
     1128    for (const PabloAST * user : stmt->users()) {
     1129        if (LLVM_LIKELY(isa<Statement>(user))) {
     1130            const Statement * use = cast<Statement>(user);
     1131            auto f = M.find(use);
     1132            if (LLVM_UNLIKELY(f == M.end())) {
     1133                const PabloBlock * parent = use->getParent();
     1134                for (;;) {
     1135                    if (parent == block) {
     1136                        break;
     1137                    }
     1138                    use = parent->getBranch();
     1139                    parent = parent->getParent();
     1140                    if (parent == nullptr) {
     1141                        return;
     1142                    }
     1143                }
     1144                f = M.find(use);
     1145                assert (f != M.end());
     1146                M.emplace(use, f->second);
     1147            }
     1148            const auto v = f->second;
     1149            if (LLVM_UNLIKELY(u != v)) {
     1150                add_edge(u, v, G);
     1151            }
    11601152        }
    11611153    }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4919 r4927  
    1212#include <stdint.h>
    1313#include <llvm/ADT/DenseMap.h>
     14#include <llvm/ADT/DenseSet.h>
    1415
    1516typedef int BDD;
     
    1920class PabloBuilder;
    2021class PabloFunction;
    21 struct OrderingVerifier;
    2222
    2323class MultiplexingPass {
     
    3535    using CliqueSet = boost::container::flat_set<CliqueGraph::vertex_descriptor>;
    3636    using CliqueSets = boost::container::flat_set<std::vector<CliqueGraph::vertex_descriptor>>;
     37    using OrderingGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, Statement *>;
     38    using OrderingMap = boost::container::flat_map<const Statement *, OrderingGraph::vertex_descriptor>;
    3739
    3840    using AdvanceVector = std::vector<Advance *>;
     
    7678    void multiplexSelectedSets(PabloFunction & function);
    7779
    78     static void topologicalSort(PabloFunction & function);
    79     static void topologicalSort(PabloBlock * block, OrderingVerifier & parent);
     80    static void topologicalSort(PabloBlock * const block);
     81    static void topologicalSort(const OrderingGraph::vertex_descriptor u, const PabloBlock * const block, const Statement * const stmt, OrderingGraph & G, OrderingMap & M);
    8082
    8183    BDD & get(const PabloAST * const expr);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4925 r4927  
    4040    // Ensure all operands of a reassociatiable function are consistently ordered.
    4141    std::sort(var->begin(), var->end());
     42
    4243    // Apply the idempotence law to any And and Or statement and the identity law to any Xor
    4344    for (int i = var->getNumOperands() - 1; i > 0; --i) {
    44         if (LLVM_UNLIKELY(var->getOperand(i) == var->getOperand(i - 1))) {
     45        if (LLVM_UNLIKELY(equals(var->getOperand(i), var->getOperand(i - 1)))) {
    4546            var->removeOperand(i);
    4647            if (LLVM_UNLIKELY(isa<Xor>(var))) {
     
    122123                                    // Although we can apply this transformation, we have a potential problem. If P is not a "literal", we
    123124                                    // cannot optimize var without creating a new And/Or statement. However, the redundancy elimination
    124                                     // pass will miss this new statement unless we mark "var" as its own replacement.
     125                                    // pass will miss this new statement unless we mark "var" as its own replacement. We'll end up checking
     126                                    // "var" again but termination is still guaranteed once none of the new statements can be replaced by
     127                                    // prior statements in the AST.
    125128                                    PabloAST * expr = nullptr;
    126129                                    if (operands == 2) {
     
    145148                                        replacement = var;
    146149                                    }
    147                                     var->setOperand(j, expr);
    148150                                    var->removeOperand(i);
    149                                     i = 0;
     151                                    var->removeOperand(j);
     152                                    bool unique = true;
     153                                    for (unsigned k = 0; k != var->getNumOperands(); ++k) {
     154                                        if (LLVM_UNLIKELY(equals(var->getOperand(k), expr))) {
     155                                            unique = false;
     156                                            break;
     157                                        }
     158                                    }
     159                                    if (LLVM_LIKELY(unique)) {
     160                                        var->addOperand(expr);
     161                                    }
     162                                    i -= 2;
    150163                                    break; // out of for j = 0 to i - 1
    151164                                }
     
    213226        }
    214227
    215         if (LLVM_UNLIKELY(replacement != nullptr)) {
    216             // Ensure all operands of a reassociatiable function are consistently ordered.
    217             std::sort(var->begin(), var->end());
    218             // Apply the idempotence law to any And and Or statement
    219             for (int i = var->getNumOperands() - 1; i > 0; --i) {
    220                 if (LLVM_UNLIKELY(var->getOperand(i) == var->getOperand(i - 1))) {
    221                     var->removeOperand(i);
    222                 }
    223             }
    224         }
    225 
    226228    }
    227229
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4922 r4927  
    1111class Simplifier {
    1212    friend class DistributivePass;
     13    friend class FactorizeDFG;
    1314public:
    1415    static bool optimize(PabloFunction & function);
Note: See TracChangeset for help on using the changeset viewer.