Ignore:
Timestamp:
Dec 23, 2015, 4:28:42 PM (3 years ago)
Author:
nmedfort
Message:

Work on lowering + minor bug fixes.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/passes/factorizedfg.cpp

    r4896 r4899  
    1919using TypeId = PabloAST::ClassTypeId;
    2020
     21///** ------------------------------------------------------------------------------------------------------------- *
     22// * @brief lower
     23// ** ------------------------------------------------------------------------------------------------------------- */
     24//inline PabloAST * FactorizeDFG::lower(Variadic * const var, PabloBlock * block, OrderingMap & order) {
     25//    PabloAST * result = nullptr;
     26//    assert (var->getNumOperands() > 2);
     27////    // Sort the operands by their order in the current AST
     28////    std::sort(var->begin(), var->end(),
     29////        [&order](const PabloAST * const a, const PabloAST * const b)
     30////    {
     31////        return order.of(a) > order.of(b);
     32////    });
     33////    unsigned operands = var->getNumOperands();
     34////    // Swap the final two operands so that we can just append the temporary calculations onto the end
     35////    // and trust that the PENULTIMATE operand is the "latest" in the AST.
     36////    PabloAST * const item = var->getOperand(operands - 1);
     37////    var->setOperand(operands - 1, var->getOperand(operands - 2));
     38////    var->setOperand(operands - 2, item);
     39//    // Finally rewrite all of the variadic statements as binary operations
     40//    block->setInsertPoint(var->getPrevNode());
     41//    while (var->getNumOperands() > 1) {
     42//        PabloAST * const op2 = var->removeOperand(1);
     43//        PabloAST * const op1 = var->removeOperand(0);
     44//        assert (op1 != op2);
     45//        if (isa<And>(var)) {
     46//            result = block->createAnd(op1, op2);
     47//        } else if (isa<Or>(var)) {
     48//            result = block->createOr(op1, op2);
     49//        } else { // if (isa<Xor>(var)) {
     50//            result = block->createXor(op1, op2);
     51//        }
     52//        var->addOperand(result);
     53//    }
     54//    assert (result);
     55//    return result;
     56//}
     57
     58///** ------------------------------------------------------------------------------------------------------------- *
     59// * @brief lower
     60// ** ------------------------------------------------------------------------------------------------------------- */
     61//void FactorizeDFG::lower(PabloBlock * const block, OrderingMap & parent) {
     62//    OrderingMap order(parent);
     63//    Statement * stmt = block->front();
     64//    while (stmt) {
     65//        if (isa<If>(stmt) || isa<While>(stmt)) {
     66//            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), order);
     67//            if (isa<If>(stmt)) {
     68//                for (Assign * def : cast<If>(stmt)->getDefined()) {
     69//                    order.enumerate(def);
     70//                }
     71//            } else { // if (isa<While>(stmt)) {
     72//                for (Next * var : cast<While>(stmt)->getVariants()) {
     73//                    order.enumerate(var);
     74//                }
     75//            }
     76//        } else {
     77//            if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
     78//                // We should maintain an ordering list and sort each Variadic according to it prior to writing them out.
     79//                PabloAST * result = lower(cast<Variadic>(stmt), block, order);
     80//                order.enumerate(result);
     81//                stmt = stmt->replaceWith(result, true);
     82//                continue;
     83//            }
     84//            order.enumerate(stmt);
     85//        }
     86//        stmt = stmt->getNextNode();
     87//    }
     88//}
     89
    2190/** ------------------------------------------------------------------------------------------------------------- *
    2291 * @brief finalize
    2392 ** ------------------------------------------------------------------------------------------------------------- */
    24 inline Statement * FactorizeDFG::finalize(Variadic * const var, PabloBlock * block) {
     93inline Statement * FactorizeDFG::lower(Variadic * const var, PabloBlock * block) {
    2594    PabloAST * result = nullptr;
    2695    assert (var->getNumOperands() > 2);
     
    45114 * @brief finalize
    46115 ** ------------------------------------------------------------------------------------------------------------- */
    47 void FactorizeDFG::finalize(PabloBlock * const block) {
     116void FactorizeDFG::lower(PabloBlock * const block) {
    48117    Statement * stmt = block->front();
    49118    while (stmt) {
    50119        if (isa<If>(stmt) || isa<While>(stmt)) {
    51             finalize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     120            lower(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    52121        } else if ((isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) && (stmt->getNumOperands() > 2)) {
    53122            // We should maintain an ordering list and sort each Variadic according to it prior to writing them out.
    54             stmt = finalize(cast<Variadic>(stmt), block);
     123            stmt = lower(cast<Variadic>(stmt), block);
    55124            continue;
    56125        }
     
    58127    }
    59128}
     129
     130///** ------------------------------------------------------------------------------------------------------------- *
     131// * @brief lower
     132// ** ------------------------------------------------------------------------------------------------------------- */
     133//inline void FactorizeDFG::lower(PabloFunction & function) {
     134//    OrderingMap ordering;
     135//    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
     136//        ordering.enumerate(function.getParameter(i));
     137//    }
     138//    lower(function.getEntryBlock(), ordering);
     139//}
    60140
    61141/** ------------------------------------------------------------------------------------------------------------- *
     
    162242 * @brief chooseInsertionPoint
    163243 ** ------------------------------------------------------------------------------------------------------------- */
    164 inline PabloBlock * FactorizeDFG::chooseInsertionScope(const VertexSet & users) {
    165 
    166     std::vector<PabloBlock *> scopes;
     244inline PabloBlock * FactorizeDFG::chooseInsertionScope(const ASTVector & users) {
     245
     246    ScopeSet scopes;
    167247    scopes.reserve(users.size());
    168248
     
    212292 * @brief findInsertionPoint
    213293 ** ------------------------------------------------------------------------------------------------------------- */
    214 void FactorizeDFG::findInsertionPoint(const VertexSet & operands, PabloBlock * const scope) {
     294void FactorizeDFG::findInsertionPoint(const ASTVector & operands, PabloBlock * const scope) {
    215295    const flat_set<const PabloAST *> ops(operands.begin(), operands.end());
    216296    Statement * stmt = scope->back();
     
    240320
    241321/** ------------------------------------------------------------------------------------------------------------- *
    242  * @brief Common Subexpression Elimination
    243  ** ------------------------------------------------------------------------------------------------------------- */
    244 inline void FactorizeDFG::CSE(Variadic * var) {
     322 * @brief cse
     323 ** ------------------------------------------------------------------------------------------------------------- */
     324inline void FactorizeDFG::cse(Variadic * var) {
    245325    while (var->getNumOperands() > 2) {
    246326        BicliqueSet bicliques = enumerateBicliques(var);
     
    248328            break;
    249329        }
    250         VertexSet operands;
    251         VertexSet users;
     330        ASTVector operands;
     331        ASTVector users;
    252332        std::tie(operands, users) = pick(std::move(bicliques));
    253 
    254333        PabloBlock * const block = chooseInsertionScope(users);
    255334        findInsertionPoint(operands, block);
     
    272351
    273352/** ------------------------------------------------------------------------------------------------------------- *
    274  * @brief Common Subexpression Elimination
    275  ** ------------------------------------------------------------------------------------------------------------- */
    276 void FactorizeDFG::CSE(PabloBlock * const block) {
     353 * @brief cse
     354 *
     355 * Perform common subexpression elimination on the Variadic statements
     356 ** ------------------------------------------------------------------------------------------------------------- */
     357void FactorizeDFG::cse(PabloBlock * const block) {
    277358    Statement * stmt = block->front();
    278359    while (stmt) {
    279360        if (isa<If>(stmt) || isa<While>(stmt)) {           
    280             CSE(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     361            cse(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    281362        } else if (isa<And>(stmt) || isa<Or>(stmt) || isa<Xor>(stmt)) {
    282             CSE(cast<Variadic>(stmt));
     363            cse(cast<Variadic>(stmt));
    283364        }
    284365        stmt = stmt->getNextNode();
     
    287368
    288369/** ------------------------------------------------------------------------------------------------------------- *
    289  * @brief preScanDFG
    290  ** ------------------------------------------------------------------------------------------------------------- */
    291 void FactorizeDFG::initialize(const PabloBlock * const block, const unsigned depth) {
     370 * @brief enumerateScopeDepth
     371 ** ------------------------------------------------------------------------------------------------------------- */
     372void FactorizeDFG::enumerateScopeDepth(const PabloBlock * const block, const unsigned depth) {
    292373    const Statement * stmt = block->front();
    293374    while (stmt) {
     
    295376            PabloBlock * body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    296377            mScopeDepth.emplace(body, depth);
    297             initialize(body, depth + 1);
     378            enumerateScopeDepth(body, depth + 1);
    298379        }
    299380        stmt = stmt->getNextNode();
     
    302383
    303384/** ------------------------------------------------------------------------------------------------------------- *
    304  * @brief preScanDFG
    305  ** ------------------------------------------------------------------------------------------------------------- */
    306 inline void FactorizeDFG::initialize(const PabloFunction &function) {
     385 * @brief enumerateScopeDepth
     386 ** ------------------------------------------------------------------------------------------------------------- */
     387inline void FactorizeDFG::enumerateScopeDepth(const PabloFunction & function) {
    307388    mScopeDepth.emplace(function.getEntryBlock(), 0);
    308     initialize(function.getEntryBlock(), 1);
     389    enumerateScopeDepth(function.getEntryBlock(), 1);
    309390}
    310391
     
    314395void FactorizeDFG::transform(PabloFunction & function) {
    315396    FactorizeDFG ldfg;
    316     ldfg.initialize(function);
    317     ldfg.CSE(function.getEntryBlock());
     397    ldfg.enumerateScopeDepth(function);
     398    ldfg.cse(function.getEntryBlock());
    318399    #ifndef NDEBUG
    319     PabloVerifier::verify(function, "post-factorize");
    320     #endif
    321     ldfg.finalize(function.getEntryBlock());
    322     #ifndef NDEBUG
    323     PabloVerifier::verify(function, "post-finalize");
     400    PabloVerifier::verify(function, "post-cse");
    324401    #endif
    325402    Simplifier::optimize(function);
    326 }
    327 
    328 }
     403    ldfg.lower(function.getEntryBlock());
     404    #ifndef NDEBUG
     405    PabloVerifier::verify(function, "post-lowering");
     406    #endif   
     407}
     408
     409}
Note: See TracChangeset for help on using the changeset viewer.