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

Work on lowering + minor bug fixes.

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

    r4890 r4899  
    1616class FactorizeDFG {
    1717    using ScopeDepth = boost::container::flat_map<const PabloBlock *, unsigned>;
    18     using VertexSet = std::vector<PabloAST *>;
     18    using ScopeSet = std::vector<PabloBlock *>;
     19    using ASTVector = std::vector<PabloAST *>;
     20    struct OrderingMap {
     21        unsigned of(const PabloAST * const expr) const {
     22            auto f = mMap.find(expr);
     23            if (f == mMap.end()) {
     24                return mParent ? mParent->of(expr) : 0;
     25            }
     26            return f->second;
     27        }
     28        inline void enumerate(const PabloAST * const expr) {
     29            mMap.emplace(expr, ++mOrderingCount);
     30        }
     31        OrderingMap() :  mParent(nullptr), mOrderingCount(0) {}
     32        OrderingMap(OrderingMap * const parent) :  mParent(parent), mOrderingCount(parent->mOrderingCount) {}
     33        ~OrderingMap() { if (mParent) { mParent->mOrderingCount = mOrderingCount; } }
     34    private:
     35        OrderingMap * const mParent;
     36        unsigned mOrderingCount;
     37        boost::container::flat_map<const PabloAST *, unsigned> mMap;
     38    };
     39
    1940public:
    2041    static void transform(PabloFunction & function);
    2142protected:   
    22     void initialize(const PabloFunction & function);
    23     void initialize(const PabloBlock * const block, const unsigned depth);
    24     void CSE(PabloBlock * const block);
    25     void CSE(Variadic * const var);
    26     PabloBlock * chooseInsertionScope(const VertexSet & users);
    27     void findInsertionPoint(const VertexSet & operands, PabloBlock * const scope);
    28     void finalize(PabloBlock * const block);
    29     Statement * finalize(Variadic * const var, PabloBlock * block);
     43    void enumerateScopeDepth(const PabloFunction & function);
     44    void enumerateScopeDepth(const PabloBlock * const block, const unsigned depth);
     45    void cse(PabloBlock * const block);
     46    void cse(Variadic * const var);
     47    PabloBlock * chooseInsertionScope(const ASTVector & users);
     48    void findInsertionPoint(const ASTVector & operands, PabloBlock * const scope);
     49    void lower(PabloFunction & function);
     50//    void lower(PabloBlock * const block, OrderingMap & parent);
     51//    PabloAST * lower(Variadic * const var, PabloBlock * block, OrderingMap & order);
     52    void lower(PabloBlock * const block);
     53    Statement * lower(Variadic * const var, PabloBlock * block);
    3054    FactorizeDFG() = default;
    3155private:
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.cpp

    r4896 r4899  
    66#include <boost/container/flat_map.hpp>
    77#include <boost/graph/adjacency_list.hpp>
    8 
    9 #include <pablo/printer_pablos.h>
    10 #include <iostream>
     8#include <queue>
    119
    1210using namespace boost;
     
    119117 * @brief deMorgansReduction
    120118 ** ------------------------------------------------------------------------------------------------------------- */
    121 inline void FlattenAssociativeDFG::deMorgansReduction(PabloBlock * const block) {
     119void FlattenAssociativeDFG::deMorgansReduction(PabloBlock * const block, const bool traverse) {
    122120    for (Statement * stmt : *block) {
    123         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    124             deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     121        if (LLVM_UNLIKELY((isa<If>(stmt) || isa<While>(stmt)) && traverse)) {
     122            deMorgansReduction(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), true);
    125123        } else if (isa<And>(stmt) || isa<Or>(stmt)) {
    126124            deMorgansReduction(cast<Variadic>(stmt), block);
     
    138136using Graph = adjacency_list<vecS, vecS, bidirectionalS, VertexData, Variadic *>;
    139137using Vertex = Graph::vertex_descriptor;
    140 using Map = flat_map<TypeId, Vertex>;
     138using SourceMap = flat_map<Assign *, Vertex>;
     139using SinkMap = flat_map<TypeId, Vertex>;
    141140using VertexSet = std::vector<Vertex>;
    142141using Biclique = std::pair<VertexSet, VertexSet>;
     
    146145 * @brief addToVariadicGraph
    147146 ** ------------------------------------------------------------------------------------------------------------- */
    148 static bool addToVariadicGraph(Assign * const def, Graph & G, Map & M, VertexSet & A) {
    149 
    150     // Test if its valid to transform this statement
    151     for (PabloAST * user : def->users()) {
    152         if (isa<Variadic>(user) == 0) {
    153             if (isa<If>(user)) {
    154                 const auto defs = cast<If>(user)->getDefined();
    155                 if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), def) != defs.end())) {
    156                     continue;
    157                 }
    158             }
    159             return false;
    160         }
    161     }
    162 
    163     // Add the statement and its users to G
    164     const Vertex u = add_vertex(VertexData(def), G);
    165     A.push_back(u);
    166     for (PabloAST * user : def->users()) {
    167         if (isa<Variadic>(user)) {
    168             auto f = M.find(user->getClassTypeId());
    169             if (f == M.end()) {
    170                 f = M.emplace(user->getClassTypeId(), add_vertex(VertexData(user->getClassTypeId()), G)).first;
    171             }
    172             assert (f != M.end());
    173             G[add_edge(u, f->second, G).first] = cast<Variadic>(user);
     147static bool addToVariadicGraph(Assign * const def, Graph & G, SourceMap & A, SinkMap & B) {
     148
     149    if (LLVM_LIKELY(A.count(def) == 0)) {
     150        // Test if its valid to transform this statement
     151        for (PabloAST * user : def->users()) {
     152            if (isa<Variadic>(user) == 0) {
     153                if (isa<If>(user)) {
     154                    if (LLVM_LIKELY(cast<If>(user)->getCondition() != def)) {
     155                        continue;
     156                    }
     157                }
     158                return false;
     159            }
     160        }
     161
     162        // Add the statement and its users to G
     163        const Vertex u = add_vertex(VertexData(def), G);
     164        A.emplace(def, u);
     165        for (PabloAST * user : def->users()) {
     166            if (isa<Variadic>(user)) {
     167                auto f = B.find(user->getClassTypeId());
     168                if (f == B.end()) {
     169                    f = B.emplace(user->getClassTypeId(), add_vertex(VertexData(user->getClassTypeId()), G)).first;
     170                }
     171                assert (f != B.end());
     172                G[add_edge(u, f->second, G).first] = cast<Variadic>(user);
     173            }
    174174        }
    175175    }
     
    342342 * @brief tryToPartiallyExtractVariadic
    343343 ** ------------------------------------------------------------------------------------------------------------- */
    344 void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
     344inline void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(Variadic * const var) {
    345345
    346346    for (unsigned i = 0; i < var->getNumOperands(); ++i) {
    347347        PabloAST * const op = var->getOperand(i);
    348348        if (isa<Assign>(op)) {
     349
    349350            // Have we found a variadic operation that can sunk into a nested scope?
    350351            for (unsigned j = i + 1; j != var->getNumOperands(); ++j) {
     
    352353                if (LLVM_UNLIKELY(matches(op, var->getOperand(j)))) {
    353354                    Graph G;
    354                     Map M;
    355                     VertexSet A;
    356                     if (addToVariadicGraph(cast<Assign>(op), G, M, A) == 0) {
     355                    SourceMap A;
     356                    SinkMap B;
     357                    if (addToVariadicGraph(cast<Assign>(op), G, A, B) == 0) {
    357358                        invalid = true;
    358359                        break;
    359360                    }
    360                     addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, M, A);
     361                    addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, A, B);
    361362                    for (++j; j != var->getNumOperands(); ++j) {
    362363                        if (LLVM_UNLIKELY(matches(op, var->getOperand(j)))) {
    363                             addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, M, A);
     364                            addToVariadicGraph(cast<Assign>(var->getOperand(j)), G, A, B);
    364365                        }
    365366                    }
     367
    366368                    if (A.size() > 1) {
    367                         const auto S = independentCliqueSets<0>(std::move(enumerateBicliques(G, A)), 2);
     369
     370                        VertexSet H;
     371                        H.reserve(A.size());
     372                        for (auto a : A) {
     373                            H.push_back(a.second);
     374                        }
     375
     376                        const auto S = independentCliqueSets<0>(std::move(enumerateBicliques(G, H)), 2);
     377                        assert (S.size() > 0);
    368378                        for (const Biclique & C : S) {
    369379                            const VertexSet & sources = std::get<0>(C);
    370380                            const VertexSet & variadics = std::get<1>(C);
     381                            assert (variadics.size() > 0);
     382                            assert (sources.size() > variadics.size());
    371383                            PabloBlock * const block = cast<Assign>(op)->getParent();
    372384                            block->setInsertPoint(block->back());
     
    383395                                        joiner = block->createXor(sources.size());
    384396                                        break;
    385                                     default:
    386                                         break;
     397                                    default: llvm_unreachable("Unexpected!");
    387398                                }
    388399                                assert (joiner);
    389                                 flat_set<Variadic *> vars;
     400                                flat_set<Assign *> defs;
    390401                                for (const auto u : sources) {
    391                                     Assign * const def = G[u].def;
    392                                     joiner->addOperand(def->getOperand(0));
    393                                     for (auto e : make_iterator_range(out_edges(u, G))) {
    394                                         if (LLVM_LIKELY(target(e, G) == v)) {
    395                                             Variadic * const var = cast<Variadic>(G[e]);
    396                                             vars.insert(var);
    397                                             var->deleteOperand(def);
    398                                         }
    399                                     }
    400                                     assert (def->getNumUses() == 1);
    401                                     def->eraseFromParent();
     402                                    defs.insert(G[u].def);
    402403                                }
     404                                for (Assign * def : defs) {
     405                                    joiner->addOperand(def->getOperand(0));                                   
     406                                }
     407
    403408                                coalesce(joiner);
    404                                 Assign * const def = block->createAssign("m", joiner);
    405                                 cast<If>(block->getBranch())->addDefined(def);
    406                                 for (Variadic * var : vars) {
    407                                     var->addOperand(def);
     409                                Assign * const joined = block->createAssign("m", joiner);
     410
     411                                for (Assign * def : defs) {
     412                                    def->replaceWith(joined);
     413                                    assert (def->getNumUses() == 0);
    408414                                }
    409415                            }
    410416                        }
     417                        --i;
    411418                    }
    412419                    break;
     
    421428
    422429/** ------------------------------------------------------------------------------------------------------------- *
    423  * @brief removeFalseScopeDependencies
    424  ** ------------------------------------------------------------------------------------------------------------- */
    425 inline void FlattenAssociativeDFG::removeFalseScopeDependencies(Assign * const def) {
    426     if (isa<Variadic>(def->getOperand(0))) {
    427         Variadic * const var = cast<Variadic>(def->getOperand(0));
    428         for (unsigned i = 0; i != var->getNumOperands(); ++i) {
    429             if (isa<Assign>(var->getOperand(i))) {
    430                 Assign * const nestedDef = cast<Assign>(var->getOperand(i));
    431                 if (LLVM_LIKELY(nestedDef->getOperand(0)->getClassTypeId() == var->getClassTypeId())) {
    432                     if (LLVM_LIKELY(nestedDef->getNumUses() == 2)) { // The If node that produces it and the "var"
    433                         Variadic * const nestedVar = cast<Variadic>(nestedDef->getOperand(0));
    434                         if (LLVM_LIKELY(nestedVar->getNumUses() == 1 && nestedVar->getNumOperands() > 0)) {
    435                             for (unsigned i = 0, j = 0; ; ) {
    436                                 if (var->getOperand(i) < nestedVar->getOperand(j)) {
    437                                     if (++i == var->getNumOperands()) {
    438                                         break;
    439                                     }
    440                                 } else {
    441                                     if (var->getOperand(i) > nestedVar->getOperand(j)) {
    442                                         ++j;
    443                                     } else {
    444                                         nestedVar->removeOperand(j);
    445                                     }
    446                                     if (j == nestedVar->getNumOperands()) {
    447                                         break;
    448                                     }
    449                                 }
    450                             }
     430 * @brief tryToPartiallyExtractVariadic
     431 ** ------------------------------------------------------------------------------------------------------------- */
     432void FlattenAssociativeDFG::tryToPartiallyExtractVariadic(PabloBlock * const block) {
     433    for (Statement * stmt = block->back(); stmt; stmt = stmt->getPrevNode()) {
     434        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     435            tryToPartiallyExtractVariadic(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
     436        } else if (isa<Variadic>(stmt)) {
     437            tryToPartiallyExtractVariadic(cast<Variadic>(stmt));
     438        }
     439    }
     440}
     441
     442using ScopeDependencyGraph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     443using ScopeDependencyMap = flat_map<PabloAST *, ScopeDependencyGraph::vertex_descriptor>;
     444
     445/** ------------------------------------------------------------------------------------------------------------- *
     446 * @brief find
     447 ** ------------------------------------------------------------------------------------------------------------- */
     448inline ScopeDependencyGraph::vertex_descriptor find(PabloAST * expr, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     449    auto f = M.find(expr);
     450    if (f == M.end()) {
     451        f = M.emplace(expr, add_vertex(expr, G)).first;
     452    }
     453    return f->second;
     454}
     455
     456/** ------------------------------------------------------------------------------------------------------------- *
     457 * @brief buildScopeDependencyGraph
     458 ** ------------------------------------------------------------------------------------------------------------- */
     459ScopeDependencyGraph::vertex_descriptor buildScopeDependencyGraph(Variadic * const var, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     460    auto f = M.find(var);
     461    if (f != M.end()) {
     462        return f->second;
     463    }
     464    auto u = add_vertex(var, G);
     465    M.emplace(var, u);
     466    for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     467        PabloAST * expr = var->getOperand(i);
     468        PabloAST * value = var;
     469        while (isa<Assign>(expr)) {           
     470            value = expr;
     471            expr = cast<Assign>(expr)->getExpression();
     472        }
     473        if ((expr->getClassTypeId() == var->getClassTypeId()) && (expr->getNumUses() == 1)) {
     474            const auto v = find(value, G, M);
     475            add_edge(v, u, G);
     476            add_edge(buildScopeDependencyGraph(cast<Variadic>(expr), G, M), v, G);
     477        }
     478    }
     479    return u;
     480}
     481
     482/** ------------------------------------------------------------------------------------------------------------- *
     483 * @brief analyzeScopeDependencies
     484 ** ------------------------------------------------------------------------------------------------------------- */
     485inline void analyzeScopeDependencies(Assign * const def, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     486    if (LLVM_LIKELY(isa<Variadic>(def->getExpression()))) {
     487        buildScopeDependencyGraph(cast<Variadic>(def->getExpression()), G, M);
     488    }
     489}
     490
     491/** ------------------------------------------------------------------------------------------------------------- *
     492 * @brief analyzeScopeDependencies
     493 ** ------------------------------------------------------------------------------------------------------------- */
     494void analyzeScopeDependencies(PabloBlock * const block, ScopeDependencyGraph & G, ScopeDependencyMap & M) {
     495    for (Statement * stmt : *block) {
     496        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     497            analyzeScopeDependencies(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), G, M);
     498        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     499            analyzeScopeDependencies(cast<Assign>(stmt), G, M);
     500        }
     501    }
     502}
     503
     504/** ------------------------------------------------------------------------------------------------------------- *
     505 * @brief removeDependenciesWithUnresolvedUses
     506 ** ------------------------------------------------------------------------------------------------------------- */
     507void removeDependenciesWithUnresolvedUses(ScopeDependencyGraph & G) {
     508    for (auto u : make_iterator_range(vertices(G))) {
     509        const PabloAST * const expr = G[u];
     510        unsigned uses = 0;
     511        if (isa<Assign>(expr)) {
     512            for (const PabloAST * user : cast<Assign>(expr)->users()) {
     513                if (!isa<If>(user) || cast<If>(user)->getCondition() == expr) {
     514                    ++uses;
     515                }
     516            }
     517        } else {
     518            uses = expr->getNumUses();
     519        }
     520        if (uses != out_degree(u, G)) {
     521            clear_out_edges(u, G);
     522        }
     523    }
     524}
     525
     526/** ------------------------------------------------------------------------------------------------------------- *
     527 * @brief eliminateUnecessaryDependencies
     528 ** ------------------------------------------------------------------------------------------------------------- */
     529void eliminateUnecessaryDependencies(ScopeDependencyGraph & G) {
     530    using Vertex = ScopeDependencyGraph::vertex_descriptor;
     531    std::vector<bool> visited(num_vertices(G), false);
     532    std::queue<Vertex> Q;
     533    for (auto u : make_iterator_range(vertices(G))) {
     534        if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     535            Q.push(u);
     536        }
     537    }
     538    while (Q.size() > 0) {
     539        const auto u = Q.front(); Q.pop();
     540        visited[u] = true;
     541        for (auto e : make_iterator_range(in_edges(u, G))) {
     542            bool usersHaveBeenVisited = true;
     543            const auto v = source(e, G);
     544            for (auto e : make_iterator_range(out_edges(v, G))) {
     545                if (visited[target(e, G)] == 0) {
     546                    usersHaveBeenVisited = false;
     547                    break;
     548                }
     549            }
     550            if (usersHaveBeenVisited) {
     551                Q.push(v);
     552                for (auto e : make_iterator_range(in_edges(u, G))) {
     553                    const auto w = source(e, G);
     554                    if (w != v) {
     555                        auto f = add_edge(w, v, G);
     556                        if (f.second == 0) {
     557                            cast<Variadic>(G[v])->deleteOperand(G[w]);
    451558                        }
    452559                    }
     
    463570 * If statement. Unless necessary for correctness, eliminate it as we can potentially schedule the If nodes
    464571 * better without the sequential dependency.
    465  ** ------------------------------------------------------------------------------------------------------------- */
    466 void FlattenAssociativeDFG::removeFalseScopeDependencies(PabloBlock * const block) {
    467     for (Statement * stmt = block->back(); stmt; stmt = stmt->getPrevNode()) {
    468         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    469             removeFalseScopeDependencies(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    470         } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
    471             removeFalseScopeDependencies(cast<Assign>(stmt));
    472         } else if (isa<Variadic>(stmt)) {
    473             tryToPartiallyExtractVariadic(cast<Variadic>(stmt));
    474         }
    475     }
     572 *
     573 * TODO: make this only iterate over the scope blocks and test the scope branch.
     574 ** ------------------------------------------------------------------------------------------------------------- */
     575inline void FlattenAssociativeDFG::removeFalseScopeDependencies(PabloFunction & function) {
     576    ScopeDependencyGraph G;
     577    {
     578        ScopeDependencyMap M;
     579        analyzeScopeDependencies(function.getEntryBlock(), G, M);
     580    }
     581    removeDependenciesWithUnresolvedUses(G);
     582    eliminateUnecessaryDependencies(G);
    476583}
    477584
     
    488595    Simplifier::optimize(function);
    489596
    490     FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock());
     597    FlattenAssociativeDFG::deMorgansReduction(function.getEntryBlock(), true);
    491598    #ifndef NDEBUG
    492599    PabloVerifier::verify(function, "post-demorgans-reduction");
     
    495602    Simplifier::optimize(function);
    496603
    497     FlattenAssociativeDFG::removeFalseScopeDependencies(function.getEntryBlock());
     604    FlattenAssociativeDFG::removeFalseScopeDependencies(function);
    498605    #ifndef NDEBUG
    499606    PabloVerifier::verify(function, "post-remove-false-scope-dependencies");
    500607    #endif
    501608
     609    FlattenAssociativeDFG::tryToPartiallyExtractVariadic(function.getEntryBlock());
     610    #ifndef NDEBUG
     611    PabloVerifier::verify(function, "post-partial-variadic-extraction");
     612    #endif
     613
    502614    Simplifier::optimize(function);
    503 }
    504 
    505 }
     615
     616
     617}
     618
     619}
  • icGREP/icgrep-devel/icgrep/pablo/passes/flattenassociativedfg.h

    r4896 r4899  
    2020    static void coalesce(Variadic * const var);
    2121    static void deMorgansExpansion(Not * const var, PabloBlock * const block);
    22     static void deMorgansReduction(PabloBlock * const block);
     22    static void deMorgansReduction(PabloBlock * const block, const bool traverse);
    2323    static void deMorgansReduction(Variadic * const var, PabloBlock * const block);
    24     static void removeFalseScopeDependencies(PabloBlock * const block);
    25     static void removeFalseScopeDependencies(Assign * const def);
     24    static void tryToPartiallyExtractVariadic(PabloBlock * const block);
    2625    static void tryToPartiallyExtractVariadic(Variadic * const var);
     26    static void removeFalseScopeDependencies(PabloFunction & function);
    2727    FlattenAssociativeDFG() = default;
    2828};
Note: See TracChangeset for help on using the changeset viewer.