Changeset 4799


Ignore:
Timestamp:
Sep 27, 2015, 2:07:22 PM (2 years ago)
Author:
nmedfort
Message:

Bug fix for verifier and rewrite of the code sinking optimization pass.

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

Legend:

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

    r4797 r4799  
    105105
    106106if(ENABLE_MULTIPLEXING)
    107 set(MULTIPLEXING_FLAG -multiplexing -reassoc) # -multiplexing-dist=${PROJECT_BINARY_DIR}/ucd-multiplexing.csv #-ldc=ldc.csv
     107set(MULTIPLEXING_FLAG -multiplexing -reassoc -multiplexing-dist=${PROJECT_BINARY_DIR}/ucd-multiplexing.csv) # -multiplexing-dist=${PROJECT_BINARY_DIR}/ucd-multiplexing.csv #-ldc=ldc.csv
    108108endif()
    109109
  • icGREP/icgrep-devel/icgrep/pablo/analysis/pabloverifier.cpp

    r4797 r4799  
    152152            if (isa<If>(stmt)) {
    153153                for (const Assign * def : cast<If>(stmt)->getDefined()) {
    154                     if (def->getParent() != &block) {
     154                    if (def->getParent() != &nested) {
    155155                        misreportedEscapingValue = def;
    156156                        break;
     
    159159            } else {
    160160                for (const Next * var : cast<While>(stmt)->getVariants()) {
    161                     if (var->getParent() != &block) {
     161                    if (var->getParent() != &nested) {
    162162                        misreportedEscapingValue = var;
    163163                        break;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_codesinking.cpp

    r4797 r4799  
    55namespace pablo {
    66
    7 bool CodeSinking::optimize(PabloFunction & function)
    8 {
     7/** ------------------------------------------------------------------------------------------------------------- *
     8 * @brief optimize
     9 ** ------------------------------------------------------------------------------------------------------------- */
     10bool CodeSinking::optimize(PabloFunction & function) {
    911    CodeSinking lcf;
    1012    lcf.sink(function.getEntryBlock());
    1113    #ifndef NDEBUG
    12     PabloVerifier::verify(*function, "post-sinking");
     14    PabloVerifier::verify(function, "post-sinking");
    1315    #endif
    1416    return true;
    1517}
    1618
     19/** ------------------------------------------------------------------------------------------------------------- *
     20 * @brief isSafeToMove
     21 ** ------------------------------------------------------------------------------------------------------------- */
    1722inline static bool isSafeToMove(Statement * stmt) {
    18     if (isa<Assign>(stmt) || isa<Next>(stmt)) {
    19         return false;
    20     }
    21     return true;
     23    return !isa<Assign>(stmt) && !isa<Next>(stmt);
    2224}
    2325
     26/** ------------------------------------------------------------------------------------------------------------- *
     27 * @brief calculateDepthToCurrentBlock
     28 ** ------------------------------------------------------------------------------------------------------------- */
     29inline static unsigned calculateDepthToCurrentBlock(const PabloBlock * scope, const PabloBlock & root) {
     30    unsigned depth = 0;
     31    while (scope != &root) {
     32        ++depth;
     33        assert (scope);
     34        scope = scope->getParent();
     35    }
     36    return depth;
     37}
     38
     39/** ------------------------------------------------------------------------------------------------------------- *
     40 * @brief sink
     41 ** ------------------------------------------------------------------------------------------------------------- */
    2442void CodeSinking::sink(PabloBlock & block) {
    2543
    26     Statement * stmt = block.back();
     44    Statement * stmt = block.back(); // note: reverse AST traversal
    2745    while (stmt) {
    2846        Statement * next = stmt->getPrevNode();
    2947        if (isa<If>(stmt)) {
    30             If * ifNode = cast<If>(stmt);
    31             assert (ifNode->getParent() == &block);
    32             sink(ifNode->getBody());
    33         }
    34         else if (isa<While>(stmt)) {
    35             While * whileNode = cast<While>(stmt);
    36             assert (whileNode->getParent() == &block);
    37             sink(whileNode->getBody());
    38         }
    39         else if (isSafeToMove(stmt)) {
     48            sink(cast<If>(stmt)->getBody());
     49        } else if (isa<While>(stmt)) {
     50            sink(cast<While>(stmt)->getBody());
     51        } else if (isSafeToMove(stmt)) {
    4052
    41             BlockSetVector ancestors;
     53            // Scan through this statement's users to see if they're all in a nested scope. If so,
     54            // find the least comon ancestor of the scope blocks. If it is not the current scope,
     55            // then we can sink the instruction.
     56
     57            // (Note: the current scope is added to the list of processed ones AFTER we've traversed it.)
     58
     59            ScopeSet scopes;
    4260            bool canSinkInstruction = false;
    43             for (const PabloAST * u : stmt->users()) {
    44                 if (const Statement * use = dyn_cast<Statement>(u)) {
    45                     if (mProcessed.count(use->getParent())) {
     61            for (const PabloAST * use : stmt->users()) {
     62                if (const Statement * user = dyn_cast<Statement>(use)) {
     63                    if (mProcessed.count(user->getParent())) {
    4664                        canSinkInstruction = true;
    47                         ancestors.insert(use->getParent());
     65                        scopes.insert(user->getParent());
    4866                        continue;
    4967                    }
     
    5472            if (canSinkInstruction) {
    5573
    56                 assert (ancestors.size() >= 1);
     74                while (scopes.size() > 1) {
     75                    // Find the LCA of both scopes then add the LCA back to the list of scopes.
     76                    PabloBlock * scope1 = scopes.back();
     77                    scopes.pop_back();
     78                    unsigned depth1 = calculateDepthToCurrentBlock(scope1, block);
    5779
    58                 if (ancestors.size() > 1) {
    59                     BlockSetVector P1, P2;
    60                     while (ancestors.size() > 1) {
     80                    PabloBlock * scope2 = scopes.back();
     81                    scopes.pop_back();
     82                    unsigned depth2 = calculateDepthToCurrentBlock(scope2, block);
    6183
    62                         PabloBlock * u = ancestors.back();
    63                         while (u != &block) {
    64                             P1.push_back(u);
    65                             u = u->getParent();
    66                         }
    67                         ancestors.pop_back();
     84                    // If one of these scopes is nested deeper than the other, scan upwards through
     85                    // the scope tree until both scopes are at the same depth.
     86                    while (depth1 > depth2) {
     87                        scope1 = scope1->getParent();
     88                        --depth1;
     89                    }
     90                    while (depth1 < depth2) {
     91                        scope2 = scope2->getParent();
     92                        --depth2;
     93                    }
    6894
    69                         PabloBlock * v = ancestors.back();
    70                         while (v != &block) {
    71                             P2.push_back(v);
    72                             v = v->getParent();
    73                         }
    74                         ancestors.pop_back();
    75 
    76                         // P1 and P2 now contain the paths from the 'sink' to the 'source'. Scan backwards though them
    77                         // to find the first differing element. The last non-differing block is our LCA. If none
    78                         // exists for any two paths, this instruction cannot be sunk (or would just be sunk to the
    79                         // same position it's at now.)
    80 
    81                         PabloBlock * lca = nullptr;
    82                         auto p1 = P1.rbegin(), p2 = P2.rbegin();
    83 
    84                         for (; p1 != P1.rend() && p2 != P2.rend(); ++p1, ++p2) {
    85                             if (*p1 != *p2) {
    86                                 break;
    87                             }
    88 
    89                             lca = *p1;
    90                         }
    91 
    92                         if (lca == nullptr) {
    93                             canSinkInstruction = false;
    94                             break;
    95                         }
    96 
    97                         P1.clear();
    98                         P2.clear();
    99                         ancestors.insert(lca);
     95                    // Then iteratively step backwards until we find a matching set of scopes; this
     96                    // must be the LCA of our original scopes.
     97                    while (scope1 != scope2) {
     98                        scope1 = scope1->getParent();
     99                        scope2 = scope2->getParent();
    100100                    }
     101                    assert (scope1 && scope2);
     102                    // But if the LCA is the current block, we can't sink the statement.
     103                    if (scope1 == &block) {
     104                        canSinkInstruction = false;
     105                        break;
     106                    }
     107                    scopes.push_back(scope1);
    101108                }
    102109
    103110                if (canSinkInstruction) {
    104                     assert (ancestors.size() == 1);
    105                     PabloBlock * const lca = *ancestors.begin();
    106                     stmt->insertBefore(lca->front());
     111                    assert (scopes.size() == 1);
     112                    stmt->insertBefore(scopes.front()->front());
    107113                }
    108114            }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_codesinking.hpp

    r4657 r4799  
    1212class CodeSinking {
    1313
    14     struct BlockSetVector : public std::vector<PabloBlock *> {
     14    struct ScopeSet : public std::vector<PabloBlock *> {
    1515        inline bool insert(PabloBlock * block) {
    1616            const auto i = std::lower_bound(begin(), end(), block);
     
    3434    CodeSinking() { }
    3535private:
    36     BlockSetVector mProcessed;
     36    ScopeSet mProcessed;
    3737};
    3838
Note: See TracChangeset for help on using the changeset viewer.