Changeset 4871 for icGREP


Ignore:
Timestamp:
Nov 16, 2015, 4:20:15 PM (4 years ago)
Author:
nmedfort
Message:

Minor improvements to the optimizers and AST manipulation.

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/icgrep.cpp

    r4868 r4871  
    9292    re::RE * re_ast = nullptr;
    9393    for (unsigned i = 0; i < regexVector.size(); i++) {
    94 //        try
    95 //        {
    96 //            re_ast = re::RE_Parser::parse(regexVector[i], globalFlags);
    97 //        }
    98 //        catch (ParseFailure failure)
    99 //        {
    100 //            std::cerr << "Regex parsing failure: " << failure.what() << std::endl;
    101 //            std::cerr << regexVector[i] << std::endl;
    102 //            exit(1);
    103 //        }
    104 //        catch (UCD::UnicodePropertyExpressionError e)
    105 //        {
    106 //            std::cerr << "Unicode error: " << e.what() << std::endl;
    107 //            std::cerr << regexVector[i] << std::endl;
    108 //            exit(1);
    109 //        }
    11094        re_ast = re::RE_Parser::parse(regexVector[i], globalFlags);
    11195        REs.push_back(re_ast);
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4870 r4871  
    5757    }
    5858
     59    inline static PabloBlock * Create(PabloBlock * const block) noexcept {
     60        return new PabloBlock(block->mSymbolGenerator);
     61    }
     62
    5963    PabloAST * createAdvance(PabloAST * expr, const Integer::Type shiftAmount);
    6064
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4870 r4871  
    1313#include <queue>
    1414#endif
    15 
    1615#include <pablo/printer_pablos.h>
    17 #include <llvm/Support/raw_os_ostream.h>
    1816#include <iostream>
    1917
     
    134132
    135133inline bool isNonEscaping(const VertexData & data) {
    136     return getType(data) != TypeId::Assign && getType(data) != TypeId::Next;
     134    // If these are redundant, the Simplifier pass will eliminate them. Trust that they're necessary.
     135    switch (getType(data)) {
     136        case TypeId::Assign:
     137        case TypeId::Next:
     138        case TypeId::If:
     139        case TypeId::While:
     140            return false;
     141        default:
     142            return true;
     143    }
    137144}
    138145
     
    163170 * @brief optimize
    164171 ** ------------------------------------------------------------------------------------------------------------- */
    165 bool BooleanReassociationPass::optimize(PabloFunction & function) {
     172bool BooleanReassociationPass::optimize(PabloFunction & function) {   
    166173    BooleanReassociationPass brp;
    167     // brp.resolveScopes(function);
    168     PabloVerifier::verify(function, "pre-reassociation");
    169174    brp.processScopes(function);
    170175    #ifndef NDEBUG
     
    176181
    177182/** ------------------------------------------------------------------------------------------------------------- *
    178  * @brief resolveScopes
    179  ** ------------------------------------------------------------------------------------------------------------- */
    180 inline void BooleanReassociationPass::resolveScopes(PabloFunction & function) {
    181     mResolvedScopes.emplace(function.getEntryBlock(), nullptr);
    182     resolveScopes(function.getEntryBlock());
    183 }
    184 
    185 /** ------------------------------------------------------------------------------------------------------------- *
    186  * @brief resolveScopes
    187  ** ------------------------------------------------------------------------------------------------------------- */
    188 void BooleanReassociationPass::resolveScopes(PabloBlock * const block) {
    189     for (Statement * stmt : *block) {
    190         if (isa<If>(stmt) || isa<While>(stmt)) {
    191             PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    192             mResolvedScopes.emplace(nested, stmt);
    193             resolveScopes(nested);
    194         }
    195     }
    196 }
    197 
    198 /** ------------------------------------------------------------------------------------------------------------- *
    199183 * @brief processScopes
    200184 ** ------------------------------------------------------------------------------------------------------------- */
    201185inline void BooleanReassociationPass::processScopes(PabloFunction & function) {
    202     function.setEntryBlock(processScopes(function, function.getEntryBlock()))->eraseFromParent();
     186    function.setEntryBlock(processScopes(function, function.getEntryBlock()));
    203187}
    204188
     
    211195            PabloBlock * rewrittenBlock = processScopes(f, ifNode->getBody());
    212196            mResolvedScopes.emplace(rewrittenBlock, stmt);
    213             PabloBlock * priorBlock = ifNode->setBody(rewrittenBlock);
    214             // mResolvedScopes.erase(priorBlock);
    215             priorBlock->eraseFromParent();
    216             PabloVerifier::verify(f, "post-if");
     197            ifNode->setBody(rewrittenBlock);
    217198        } else if (While * whileNode = dyn_cast<While>(stmt)) {
    218199            PabloBlock * rewrittenBlock = processScopes(f, whileNode->getBody());
    219200            mResolvedScopes.emplace(rewrittenBlock, stmt);
    220             PabloBlock * priorBlock = whileNode->setBody(rewrittenBlock);
    221             // mResolvedScopes.erase(priorBlock);
    222             priorBlock->eraseFromParent();
    223             PabloVerifier::verify(f, "post-while");
     201            whileNode->setBody(rewrittenBlock);
    224202        }
    225203    }   
     
    392370 * @brief rewriteAST
    393371 ** ------------------------------------------------------------------------------------------------------------- */
    394 PabloBlock * BooleanReassociationPass::rewriteAST(PabloFunction & f, PabloBlock * const block, Graph & G) {
     372PabloBlock * BooleanReassociationPass::rewriteAST(PabloFunction & f, PabloBlock * const originalScope, Graph & G) {
    395373
    396374    using ReadyPair = std::pair<unsigned, Vertex>;
     
    455433    PabloBlock * const newScope = PabloBlock::Create(f);
    456434
     435    // This should hold back Assign and Next nodes then write them in after any reassociated statements
     436    // are rewritten at the earliest use.
     437
    457438    // Rewrite the AST using the bottom-up ordering
    458439    while (!readySet.empty()) {
     
    461442        // NOTE: the readySet is kept in sorted "distance to sink" order; thus those closest to a
    462443        // sink will be evaluated first.
    463         unsigned best = 0;
     444        double best = 0;
    464445        auto chosen = readySet.begin();
    465446        for (auto ri = readySet.begin(); ri != readySet.end(); ++ri) {
    466447            const Vertex u = std::get<1>(*ri);
    467             unsigned kills = 0;
     448            const PabloAST * const expr = getValue(G[u]);
     449            if (expr && (isa<Assign>(expr) || isa<Next>(expr))) {
     450                chosen = ri;
     451                break;
     452            }
     453            double progress = 0;
    468454            for (auto ei : make_iterator_range(in_edges(u, G))) {
    469455                const auto v = source(ei, G);
    470                 unsigned remaining = 0;
    471                 for (auto ej : make_iterator_range(out_edges(v, G))) {
    472                     const auto w = target(ej, G);
    473                     PabloAST * expr = getValue(G[w]);
    474                     if (expr == nullptr || (isa<Statement>(expr) && cast<Statement>(expr)->getParent() != newScope)) {
    475                         if (++remaining > 1) {
    476                             break;
     456                const auto totalUsesOfIthOperand = out_degree(v, G);
     457                if (LLVM_UNLIKELY(totalUsesOfIthOperand == 0)) {
     458                    progress += 1.0;
     459                } else {
     460                    unsigned unscheduledUsesOfIthOperand = 0;
     461                    for (auto ej : make_iterator_range(out_edges(v, G))) {
     462                        if (ordering[target(ej, G)]) { // if this edge leads to an unscheduled statement
     463                            ++unscheduledUsesOfIthOperand;
    477464                        }
    478465                    }
    479                 }
    480                 if (remaining < 2) {
    481                     ++kills;
    482                 }
    483             }
    484             if (kills > best) {
     466                    progress += std::pow((double)(totalUsesOfIthOperand - unscheduledUsesOfIthOperand + 1) / (double)(totalUsesOfIthOperand), 2);
     467                }
     468            }
     469            if (progress > best) {
    485470                chosen = ri;
    486                 best = kills;
    487             }
    488         }
     471                best = progress;
     472            }
     473        }
     474
    489475        Vertex u; unsigned weight;
    490476        std::tie(weight, u) = *chosen;
    491477        readySet.erase(chosen);
    492         PabloAST * expr = getValue(G[u]);
    493478
    494479        assert (weight > 0);
    495480
    496481        if (LLVM_LIKELY(isMutable(G[u]))) {
     482            PabloAST * expr = nullptr;
    497483            if (isAssociative(G[u])) {
    498                 expr = createTree(block, newScope, u, G);
     484                expr = createTree(originalScope, newScope, u, G);
     485            } else {
     486                expr = getValue(G[u]);
    499487            }
    500488            assert (expr);
     
    507495            }
    508496            // Make sure that optimization doesn't reduce this to an already written statement
    509             if (LLVM_LIKELY(isa<Statement>(expr) && cast<Statement>(expr)->getParent() != newScope)) {
     497            if (LLVM_LIKELY(isa<Statement>(expr) && cast<Statement>(expr)->getParent() == originalScope)) {
    510498                newScope->insert(cast<Statement>(expr));
    511499            }
     
    536524        tested.clear();
    537525    }
    538 
     526    originalScope->eraseFromParent();
    539527    return newScope;
    540528}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4870 r4871  
    1818protected:
    1919    inline BooleanReassociationPass() {}
    20     void resolveScopes(PabloFunction & function);
    21     void resolveScopes(PabloBlock * const block);
    2220    void processScopes(PabloFunction & function);
    2321    PabloBlock * processScopes(PabloFunction & f, PabloBlock * const block);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4870 r4871  
    2020using namespace boost::numeric::ublas;
    2121
    22 // #define PRINT_DEBUG_OUTPUT
     22#define PRINT_DEBUG_OUTPUT
    2323
    2424#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
     
    101101using TypeId = PabloAST::ClassTypeId;
    102102
    103 bool AutoMultiplexing::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections) {
     103bool AutoMultiplexing::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections, const bool independent) {
    104104
    105105//    std::random_device rd;
     
    108108    RNG rng(seed);
    109109
    110 
    111     raw_os_ostream out(std::cerr);
    112 
    113 //    out << seed << ',';
    114 
    115110    LOG("Seed:                    " << seed);
    116111
    117112    AutoMultiplexing am(limit, maxSelections);
    118113    RECORD_TIMESTAMP(start_initialize);
    119     const unsigned advances = am.initialize(function, out);
     114    const unsigned advances = am.initialize(function, independent);
    120115    RECORD_TIMESTAMP(end_initialize);
    121116
     
    131126    am.characterize(function.getEntryBlock());
    132127    RECORD_TIMESTAMP(end_characterize);
    133 
    134     out << bdd_getnodenum() << ',' << bdd_getallocnum() << '\n';
    135128
    136129    LOG("Characterize:            " << (end_characterize - start_characterize));
     
    155148        LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
    156149
    157 //        raw_os_ostream out(std::cerr);
    158 //        PabloPrinter::print(function.getEntryBlock().statements(), out);
    159 //        out.flush();
    160 
    161150        RECORD_TIMESTAMP(start_subset_constraints);
    162151        am.applySubsetConstraints();
     
    170159
    171160        AutoMultiplexing::topologicalSort(function);
     161
     162        #ifndef NDEBUG
     163        PabloVerifier::verify(function, "post-multiplexing");
     164        #endif
    172165    }
    173166
     
    184177 * the proper variable ordering.
    185178 ** ------------------------------------------------------------------------------------------------------------- */
    186 unsigned AutoMultiplexing::initialize(PabloFunction & function, raw_ostream & out) {
    187 
    188     flat_map<const PabloAST *, unsigned> map;   
     179unsigned AutoMultiplexing::initialize(PabloFunction & function, const bool independent) {
     180
     181    flat_map<const PabloAST *, unsigned> map;
    189182    std::stack<Statement *> scope;
    190183    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
     
    229222    }
    230223
    231     out << statements << ',' << variableCount << ',' << advances << ',';
    232 
    233224    // If there are fewer than three Advances in this program, just abort. We cannot reduce it.
    234225    if (advances < 3) {
     
    243234    // which advances ought to be multiplexed.
    244235
    245     matrix<bool> G(statements, advances);
    246     G.clear();
     236    matrix<bool> G(statements, advances, false);
    247237    for (unsigned i = 0; i != advances; ++i) {
    248238        G(i, i) = true;
     
    290280    }
    291281
     282    // Can I use the data in the matrix to indicate whether an Advance is dependent on a particular instruction and only
     283    // for which there is still a use left of it?
     284
    292285    // Record the path / base constraint graph after removing any reflexive-loops.
    293286    // Since G is a use-def graph and we want our constraint graph to be a def-use graph,
    294287    // reverse the edges as we're writing them to obtain the transposed graph.
     288
    295289    mConstraintGraph = ConstraintGraph(advances);
    296290    mSubsetGraph = SubsetGraph(advances);
     
    302296                add_edge(j, i, mConstraintGraph);
    303297            }
    304         }       
     298        }
    305299    }
    306300
     
    310304    bdd_setcacheratio(64);
    311305    bdd_setmaxincrease(10000000);
    312     // bdd_setminfreenodes(10000);
    313     bdd_autoreorder(BDD_REORDER_NONE);
    314 
    315     // Map the predefined 0/1 entries
    316     mCharacterizationMap[PabloBlock::createZeroes()] = bdd_zero();
    317     mCharacterizationMap[PabloBlock::createOnes()] = bdd_one();
    318 
    319     // Order the variables so the input Vars are pushed to the end; they ought to
    320     // be the most complex to resolve.
    321     for (mVariables = 0; mVariables != function.getNumOfParameters(); ++mVariables) {
    322         mCharacterizationMap[function.getParameter(mVariables)] = bdd_ithvar(mVariables);
     306    bdd_autoreorder(BDD_REORDER_SIFT);
     307
     308    // Map the constants and input variables
     309    mCharacterization[PabloBlock::createZeroes()] = bdd_zero();
     310    mCharacterization[PabloBlock::createOnes()] = bdd_one();
     311    mVariables = function.getNumOfParameters();
     312
     313    // TODO: record information in the function to indicate which pairs of input variables are independent
     314    if (independent) {
     315        for (unsigned i = 0; i != mVariables; ++i) {
     316            BDD Vi = bdd_ithvar(i);
     317            BDD Ni = bdd_zero();
     318            for (unsigned j = 0; j != i; ++j) {
     319                Ni = bdd_addref(bdd_or(Ni, bdd_ithvar(j)));
     320            }
     321            for (unsigned j = i + 1; j != mVariables; ++j) {
     322                Ni = bdd_addref(bdd_or(Ni, bdd_ithvar(j)));
     323            }
     324            Ni = bdd_addref(bdd_not(Ni));
     325            mCharacterization[function.getParameter(i)] = bdd_addref(bdd_imp(Vi, Ni));
     326        }
     327    } else {
     328        for (unsigned i = 0; i != mVariables; ++i) {
     329            mCharacterization[function.getParameter(i)] = bdd_ithvar(i);
     330        }
    323331    }
    324332
     
    348356            }
    349357        } else {
    350             mCharacterizationMap.insert(std::make_pair(stmt, characterize(stmt)));
     358            mCharacterization.insert(std::make_pair(stmt, characterize(stmt)));
    351359        }
    352360    }
     
    408416inline BDD AutoMultiplexing::characterize(Advance * const adv, const BDD Ik) {
    409417
    410     bdd_addref(Ik);
    411 
    412418    const auto k = mAdvanceAttributes.size();
    413419
     
    420426        // If these advances are "shifting" their values by the same amount ...
    421427        const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
    422         if (adv->getOperand(1) == ithAdv->getOperand(1)) {
     428        if (independent(i, k) && adv->getOperand(1) == ithAdv->getOperand(1)) {
    423429            const BDD Ii = get(ithAdv->getOperand(0));
    424430            const BDD IiIk = bdd_addref(bdd_and(Ii, Ik));
     
    472478            // If these Advances are mutually exclusive, in the same scope, and transitively independent,
    473479            // we safely multiplex them.
    474             if ((adv->getParent() == ithAdv->getParent()) && independent(i, k)) {
     480            if (adv->getParent() == ithAdv->getParent()) {
    475481                continue;
    476482            }
     
    478484        add_edge(i, k, mConstraintGraph);
    479485    }
    480 
    481     bdd_delref(Ik);
    482486
    483487    mAdvanceAttributes.emplace_back(adv, Vk);
     
    535539            const auto i = S.begin() + IntDistribution(0, S.size() - 1)(rng);
    536540            assert (i != S.end());
    537             const ConstraintVertex u = *i;           
    538             S.erase(i);           
     541            const ConstraintVertex u = *i;
     542            S.erase(i);
    539543
    540544            for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
     
    814818        const size_t n = out_degree(idx, mMultiplexSetGraph);
    815819        if (n) {
    816             const size_t m = log2_plus_one(n);           
     820            const size_t m = log2_plus_one(n);
    817821            Advance * input[n];
    818             Advance * muxed[m];           
     822            Advance * muxed[m];
    819823
    820824            unsigned i = 0;
     
    843847                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    844848                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    845                     assert (!Q.full());                                       
     849                    assert (!Q.full());
    846850                    Q.push_back(builder.createOr(a2, a1, "muxing"));
    847851                }
     
    849853                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
    850854                // The only way this did not return an Advance statement would be if either the mux or shift amount
    851                 // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.               
     855                // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.
    852856                muxed[j] = cast<Advance>(builder.createAdvance(mux, adv->getOperand(1), prefix.str()));
    853857            }
    854858
    855             /// Perform m-to-n Demultiplexing                       
     859            /// Perform m-to-n Demultiplexing
    856860            for (size_t i = 0; i != n; ++i) {
    857861
     
    981985 ** ------------------------------------------------------------------------------------------------------------- */
    982986inline BDD & AutoMultiplexing::get(const PabloAST * const expr) {
    983     auto f = mCharacterizationMap.find(expr);
    984     assert (f != mCharacterizationMap.end());
     987    auto f = mCharacterization.find(expr);
     988    assert (f != mCharacterization.end());
    985989    return f->second;
    986990}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4870 r4871  
    3434
    3535public:
    36     static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100);
     36    static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100, const bool independent = false);
    3737protected:
    38     unsigned initialize(PabloFunction & function, raw_ostream & out);
     38    unsigned initialize(PabloFunction & function, const bool independent);
    3939    void characterize(PabloBlock * const block);
    4040    BDD characterize(Statement * const stmt);
     
    5050    BDD & get(const PabloAST * const expr);
    5151
    52 
    5352    inline AutoMultiplexing(const unsigned limit, const unsigned maxSelections)
    5453    : mLimit(limit)
     
    6362    const unsigned              mMaxSelections;
    6463    unsigned                    mVariables;
    65     CharacterizationMap         mCharacterizationMap;
     64    CharacterizationMap         mCharacterization;
    6665    ConstraintGraph             mConstraintGraph;
    6766    SubsetGraph                 mSubsetGraph;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4870 r4871  
    240240            replaceReachableUsersOfWith(next, next->getExpr());
    241241        } else if (If * ifNode = dyn_cast<If>(stmt)) {
    242             // Check to see if the Cond is Zero and delete the loop.
    243             if (LLVM_UNLIKELY(isa<Zeroes>(ifNode->getCondition()))) {
    244                 stmt = stmt->eraseFromParent();
    245                 continue;
    246             }
    247 
    248242            // Test whether all of the defined variables are necessary
    249243            If::DefinedVars & defs = ifNode->getDefined();
     
    288282
    289283        } else if (While * whileNode = dyn_cast<While>(stmt)) {
    290             const PabloAST * initial = whileNode->getCondition();
    291             if (LLVM_LIKELY(isa<Next>(initial))) {
    292                 initial = cast<Next>(initial)->getInitial();
    293             }
    294             if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
    295                 stmt = stmt->eraseFromParent();
    296                 continue;
    297             }
    298284            eliminateRedundantCode(whileNode->getBody(), &encountered);
    299285            removeIdenticalEscapedValues(whileNode->getVariants());
     286            // If the condition's Next state is Zero, we can eliminate the loop after copying the internal
     287            // statements into the body.
     288
     289
    300290        } else if (PabloAST * expr = canTriviallyFold(stmt, block)) {
    301291            stmt = stmt->replaceWith(expr, true);
     
    323313    while (stmt) {
    324314        if (isa<If>(stmt)) {
     315            if (LLVM_UNLIKELY(isa<Zeroes>(cast<If>(stmt)->getCondition()))) {
     316                stmt = stmt->eraseFromParent();
     317                continue;
     318            }
    325319            deadCodeElimination(cast<If>(stmt)->getBody());
    326320        } else if (isa<While>(stmt)) {
     321            const PabloAST * initial = cast<While>(stmt)->getCondition();
     322            if (LLVM_LIKELY(isa<Next>(initial))) {
     323                initial = cast<Next>(initial)->getInitial();
     324            }
     325            if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
     326                stmt = stmt->eraseFromParent();
     327                continue;
     328            }
    327329            deadCodeElimination(cast<While>(stmt)->getBody());
    328330        } else if (stmt->getNumUses() == 0){
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4870 r4871  
    1212public:
    1313    static bool optimize(PabloFunction & function);
    14     static void deadCodeElimination(PabloBlock * const block);
    1514protected:
    1615    Simplifier() = default;
    1716private:
    1817    static void eliminateRedundantCode(PabloBlock * const block, ExpressionTable * predecessor = nullptr);
     18    static void deadCodeElimination(PabloBlock * const block);
    1919    static void eliminateRedundantEquations(PabloBlock * const block);
    2020    static bool isSuperfluous(const Assign * const assign);
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4870 r4871  
    99#include <llvm/Support/Compiler.h>
    1010#include <pablo/printer_pablos.h>
    11 #include <iostream>
     11#include <llvm/ADT/SmallVector.h>
    1212
    1313namespace pablo {
     
    8686 * @brief replaceAllUsesWith
    8787 ** ------------------------------------------------------------------------------------------------------------- */
    88 void PabloAST::replaceAllUsesWith(PabloAST * expr) {   
     88void PabloAST::replaceAllUsesWith(PabloAST * expr) {
     89    if (LLVM_UNLIKELY(this == expr)) {
     90        return;
     91    }
    8992    Statement * replacements[mUsers.size()];
    9093    Vector::size_type users = 0;
     
    108111
    109112/** ------------------------------------------------------------------------------------------------------------- *
    110  * @brief checkForReplacementInEscapedValueList
     113 * @brief checkEscapedValueList
    111114 ** ------------------------------------------------------------------------------------------------------------- */
    112115template <class ValueType, class ValueList>
    113 inline void Statement::checkForReplacementInEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
     116inline void Statement::checkEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list) {
    114117    if (LLVM_LIKELY(isa<ValueType>(from))) {
    115118        auto f = std::find(list.begin(), list.end(), cast<ValueType>(from));
     
    125128                assert (std::find(list.begin(), list.end(), cast<ValueType>(to)) != list.end());
    126129                assert (std::find(branch->user_begin(), branch->user_end(), cast<ValueType>(to)) != branch->user_end());
    127             } else { // replacement error occured
    128                 std::string tmp;
    129                 raw_string_ostream str(tmp);
    130                 str << "cannot replace escaped value ";
    131                 PabloPrinter::print(from, str);
    132                 str << " with ";
    133                 PabloPrinter::print(to, str);
    134                 str << " in ";
    135                 PabloPrinter::print(branch, str);
    136                 throw std::runtime_error(str.str());
     130            } else {
     131                list.erase(f);
     132                branch->removeUser(from);
    137133            }
    138134        }               
     
    146142 ** ------------------------------------------------------------------------------------------------------------- */
    147143void Statement::replaceUsesOfWith(PabloAST * const from, PabloAST * const to) {
     144    if (LLVM_UNLIKELY(from == to)) {
     145        return;
     146    }
    148147    for (unsigned i = 0; i != getNumOperands(); ++i) {
    149148       if (getOperand(i) == from) {
     
    152151    }
    153152    if (LLVM_UNLIKELY(isa<If>(this))) {
    154         checkForReplacementInEscapedValueList<Assign>(this, from, to, cast<If>(this)->getDefined());
     153        checkEscapedValueList<Assign>(this, from, to, cast<If>(this)->getDefined());
    155154    } else if (LLVM_UNLIKELY(isa<While>(this))) {
    156         checkForReplacementInEscapedValueList<Next>(this, from, to, cast<While>(this)->getVariants());
     155        checkEscapedValueList<Next>(this, from, to, cast<While>(this)->getVariants());
    157156    }
    158157}
     
    222221    if (LLVM_UNLIKELY(statement == this)) {
    223222        return;
    224     }
    225     else if (LLVM_UNLIKELY(statement == nullptr)) {
     223    } else if (LLVM_UNLIKELY(statement == nullptr)) {
    226224        throw std::runtime_error("cannot insert after null statement!");
    227     }
    228     else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
     225    } else if (LLVM_UNLIKELY(statement->mParent == nullptr)) {
    229226        throw std::runtime_error("statement is not contained in a pablo block!");
    230227    }
     
    288285        mOperand[i]->removeUser(this);
    289286    }
    290     Statement * redundantBranch = nullptr;
     287    SmallVector<Statement *, 1> redundantBranches;
    291288    // If this is an If or While statement, we'll have to remove the statements within the
    292289    // body or we'll lose track of them.
     
    304301                    defs.erase(f);
    305302                    if (LLVM_UNLIKELY(defs.empty())) {
    306                         redundantBranch = ifNode;
     303                        redundantBranches.push_back(ifNode);
    307304                    }
    308                     break;
    309305                }
    310306            }
     
    320316                    vars.erase(f);
    321317                    if (LLVM_UNLIKELY(vars.empty())) {
    322                         redundantBranch = whileNode;
     318                        redundantBranches.push_back(whileNode);
    323319                    }
    324                     break;
    325320                }
    326321            }
     
    334329            PabloAST * const op = mOperand[i];
    335330            if (LLVM_LIKELY(isa<Statement>(op))) {
    336                 bool erase = false;
    337331                if (op->getNumUses() == 0) {
    338                     erase = true;
    339                 } else if ((isa<Assign>(op) || isa<Next>(op)) && op->getNumUses() == 1) {
    340                     erase = true;
    341                 }
    342                 if (erase) {
    343332                    cast<Statement>(op)->eraseFromParent(true);
    344333                }
    345334            }
    346335        }
    347         if (LLVM_UNLIKELY(redundantBranch != nullptr)) {
     336        if (LLVM_UNLIKELY(redundantBranches.size() != 0)) {
    348337            // By eliminating this redundant branch, we may inadvertantly delete the scope block this statement
    349338            // resides within. Check and return null if so.
    350             const PabloBlock * const body = isa<If>(redundantBranch) ? cast<If>(redundantBranch)->getBody() : cast<While>(redundantBranch)->getBody();
    351             const bool eliminatedScope = (body == getParent());
    352             redundantBranch->eraseFromParent(true);
     339            bool eliminatedScope = false;
     340            for (Statement * br : redundantBranches) {
     341                const PabloBlock * const body = isa<If>(br) ? cast<If>(br)->getBody() : cast<While>(br)->getBody();
     342                if (LLVM_UNLIKELY(body == getParent())) {
     343                    eliminatedScope = true;
     344                }
     345                br->eraseFromParent(true);
     346            }
    353347            if (eliminatedScope) {
    354348                return nullptr;
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4870 r4871  
    169169    friend class PabloBlock;
    170170    template <class ValueType, class ValueList>
    171     friend void checkForReplacementInEscapedValueList(const Statement *, const PabloAST * const, PabloAST * const, ValueList &);
     171    friend void checkEscapedValueList(const Statement *, const PabloAST * const, PabloAST * const, ValueList &);
    172172public:
    173173    static inline bool classof(const PabloAST * e) {
     
    247247private:
    248248    template <class ValueType, class ValueList>
    249     void checkForReplacementInEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list);
     249    void checkEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list);
    250250protected:   
    251251    const String *              mName;
  • icGREP/icgrep-devel/icgrep/toolchain.cpp

    r4870 r4871  
    130130        llvm::raw_os_ostream cerr(std::cerr);
    131131        cerr << "Initial Pablo AST:\n";
    132         PabloPrinter::print(function, cerr);
     132        PabloPrinter::print(*function, cerr);
    133133    }
    134134#ifndef NDEBUG
     
    159159        llvm::raw_os_ostream cerr(std::cerr);
    160160        cerr << "Final Pablo AST:\n";
    161         PabloPrinter::print(function, cerr);
     161        PabloPrinter::print(*function, cerr);
    162162    }
    163163}
Note: See TracChangeset for help on using the changeset viewer.