Changeset 5271


Ignore:
Timestamp:
Jan 22, 2017, 12:29:57 PM (10 months ago)
Author:
nmedfort
Message:

Bug fix for CodeMotionPass?

File:
1 edited

Legend:

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

    r5270 r5271  
    55#include <pablo/ps_assign.h>
    66#include <pablo/pe_var.h>
     7#include <boost/container/flat_set.hpp>
     8#include <vector>
    79#ifndef NDEBUG
    810#include <pablo/analysis/pabloverifier.hpp>
    911#endif
    10 #include <boost/container/flat_set.hpp>
    11 #include <vector>
    12 
    13 #include <pablo/printer_pablos.h>
    14 #include <llvm/Support/raw_ostream.h>
    1512
    1613using namespace boost;
     
    2421 ** ------------------------------------------------------------------------------------------------------------- */
    2522bool CodeMotionPass::optimize(PabloKernel * kernel) {
    26 //    errs() << "------------------------------------------------------------------------------\n";
    27 //    errs() << "BEFORE:\n";
    28 //    errs() << "------------------------------------------------------------------------------\n";
    29 //    PabloPrinter::print(kernel, errs());
    3023    CodeMotionPass::movement(kernel->getEntryBlock());
    3124    #ifndef NDEBUG
     
    5346
    5447/** ------------------------------------------------------------------------------------------------------------- *
    55  * @brief depthTo
     48 * @brief depthOf
    5649 ** ------------------------------------------------------------------------------------------------------------- */
    57 inline static int depthTo(const PabloBlock * scope, const PabloBlock * const root) {
     50inline static int depthOf(PabloBlock * scope) {
    5851    int depth = 0;
    59     assert (scope && root);
    60     while (scope != root) {
    61         assert (scope);
     52    while (scope) {
    6253        ++depth;
    6354        scope = scope->getPredecessor();
     
    6758
    6859/** ------------------------------------------------------------------------------------------------------------- *
     60 * @brief findLCA
     61 ** ------------------------------------------------------------------------------------------------------------- */
     62inline PabloBlock * findLCA(PabloBlock * scope1, PabloBlock * scope2) {
     63    int depth1 = depthOf(scope1);
     64    int depth2 = depthOf(scope2);
     65    // If one of these scopes is nested deeper than the other, scan upwards through
     66    // the scope tree until both scopes are at the same depth.
     67    while (depth1 > depth2) {
     68        scope1 = scope1->getPredecessor();
     69        --depth1;
     70    }
     71    while (depth1 < depth2) {
     72        scope2 = scope2->getPredecessor();
     73        --depth2;
     74    }
     75    // Then iteratively step backwards until we find a matching set of scopes; this
     76    // must be the LCA of our original scopes.
     77    while (scope1 != scope2) {
     78        assert (scope1 && scope2);
     79        scope1 = scope1->getPredecessor();
     80        scope2 = scope2->getPredecessor();
     81    }
     82    return scope1;
     83}
     84
     85/** ------------------------------------------------------------------------------------------------------------- *
    6986 * @brief ScopeSet
    7087 ** ------------------------------------------------------------------------------------------------------------- */
    7188struct ScopeSet : public std::vector<PabloBlock *> {
    72     inline bool insert(PabloBlock * block) {
     89    inline void insert(PabloBlock * block) {
    7390        const auto i = std::lower_bound(begin(), end(), block);
    7491        if (i == end() || *i != block) {
    7592            std::vector<PabloBlock *>::insert(i, block);
    76             return true;
    7793        }
    78         return false;
    79     }
    80     inline bool count(PabloBlock * block) {
    81         const auto i = std::lower_bound(begin(), end(), block);
    82         return (i != end() && *i == block);
    8394    }
    8495};
     
    8798 * @brief findScopeUsages
    8899 ** ------------------------------------------------------------------------------------------------------------- */
    89 inline bool findScopeUsages(PabloAST * expr, ScopeSet & scopeSet, const PabloBlock * const block, const PabloBlock * const blocker = nullptr) {
     100inline void findUsageScopes(PabloAST * expr, ScopeSet & scopes) {
    90101    for (PabloAST * use : expr->users()) {
    91         assert (isa<Statement>(use));
    92         PabloBlock * const parent = cast<Statement>(use)->getParent();
    93         assert (parent);
    94         if (LLVM_LIKELY(parent == block)) {
    95             return false;
    96         }
    97         if (parent != blocker) {
    98             scopeSet.insert(parent);
    99         }
     102        scopes.insert(cast<Statement>(use)->getParent());
    100103    }
    101     return true;
    102104}
    103105
     
    105107 * @brief isAcceptableTarget
    106108 ** ------------------------------------------------------------------------------------------------------------- */
    107 inline bool isAcceptableTarget(Statement * stmt, ScopeSet & scopeSet, const PabloBlock * const block) {
     109inline PabloBlock * isAcceptableTarget(Statement * stmt, ScopeSet & scopes, PabloBlock * const block) {
    108110    // Scan through this statement's users to see if they're all in a nested scope. If so,
    109111    // find the least common ancestor of the scope blocks. If it is not the current scope,
    110112    // then we can sink the instruction.
    111     assert (scopeSet.empty());
    112     if (isa<Branch>(stmt)) {
    113         const auto vars = cast<Branch>(stmt)->getEscaped();
    114         if (LLVM_UNLIKELY(vars.empty())) {
    115             return false;
     113    assert (scopes.empty());
     114    if (isa<Assign>(stmt)) {
     115        return nullptr;
     116    } else if (isa<Branch>(stmt)) {
     117        for (Var * def : cast<Branch>(stmt)->getEscaped()) {
     118            findUsageScopes(def, scopes);
    116119        }
    117         for (Var * def : vars) {
    118             if (!findScopeUsages(def, scopeSet, block, cast<Branch>(stmt)->getBody())) {
    119                 return false;
    120             }
     120    } else {
     121        findUsageScopes(stmt, scopes);
     122    }
     123    if (LLVM_UNLIKELY(scopes.empty())) {
     124        return nullptr;
     125    }
     126    while (scopes.size() > 1) {
     127        PabloBlock * scope1 = scopes.back(); scopes.pop_back();
     128        PabloBlock * scope2 = scopes.back(); scopes.pop_back();
     129        scopes.insert(findLCA(scope1, scope2));
     130    }
     131    // If the LCA scope is nested within the block, return the LCA scope.
     132    // Otherwise return nullptr.
     133    PabloBlock * const scope = scopes.back(); scopes.clear();
     134    if (scope == block) {
     135        return nullptr;
     136    }
     137    PabloBlock * temp = scope;
     138    for (;;) {
     139        temp = temp->getPredecessor();
     140        if (temp == nullptr) {
     141            return nullptr;
     142        } else if (temp == block) {
     143            return scope;
    121144        }
    122         return true;
    123     } else if (isa<Assign>(stmt)) {
    124         return false;
    125145    }
    126     return findScopeUsages(stmt, scopeSet, block);
    127146}
    128147
     
    135154    while (stmt) {
    136155        Statement * prevNode = stmt->getPrevNode();
    137         if (isAcceptableTarget(stmt, scopes, block)) {
    138             while (scopes.size() > 1) {
    139 
    140                 // Find the LCA of both scopes then add the LCA back to the list of scopes.
    141                 PabloBlock * scope1 = scopes.back(); scopes.pop_back();
    142                 int depth1 = depthTo(scope1, block);
    143 
    144                 PabloBlock * scope2 = scopes.back(); scopes.pop_back();
    145                 int depth2 = depthTo(scope2, block);
    146 
    147                 // If one of these scopes is nested deeper than the other, scan upwards through
    148                 // the scope tree until both scopes are at the same depth.
    149                 while (depth1 > depth2) {
    150                     scope1 = scope1->getPredecessor();
    151                     --depth1;
    152                 }
    153                 while (depth1 < depth2) {
    154                     scope2 = scope2->getPredecessor();
    155                     --depth2;
    156                 }
    157 
    158                 // Then iteratively step backwards until we find a matching set of scopes; this
    159                 // must be the LCA of our original scopes.
    160                 while (scope1 != scope2) {
    161                     assert (scope1 && scope2);
    162                     scope1 = scope1->getPredecessor();
    163                     scope2 = scope2->getPredecessor();
    164                 }
    165                 assert (scope1);
    166                 // But if the LCA is the current block, we can't sink the statement.
    167                 if (scope1 == block) {
    168                     goto abort;
    169                 }
    170                 scopes.push_back(scope1);
    171             }
    172             assert (scopes.size() == 1);
    173             assert (isa<Branch>(stmt) ? (cast<Branch>(stmt)->getBody() != scopes.front()) : true);
    174             stmt->insertBefore(scopes.front()->front());
     156        if (PabloBlock * scope = isAcceptableTarget(stmt, scopes, block)) {
     157            stmt->insertBefore(scope->front());
    175158        }
    176 abort:  scopes.clear();
    177159        stmt = prevNode;
    178160    }
Note: See TracChangeset for help on using the changeset viewer.