Ignore:
Timestamp:
Sep 30, 2015, 12:26:23 PM (4 years ago)
Author:
nmedfort
Message:

Progress on multi-target UCD compilation

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

Legend:

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

    r4804 r4808  
    1212#include <queue>
    1313#include <set>
    14 #include <iostream>
    1514#include <pablo/printer_pablos.h>
    1615
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4797 r4808  
    1717#include <unordered_set>
    1818#include <pablo/optimizers/pablo_simplifier.hpp>
     19#include <pablo/optimizers/booleanreassociationpass.h>
    1920#include <pablo/analysis/pabloverifier.hpp>
    2021
     
    2425using namespace boost::numeric::ublas;
    2526
    26 // #define PRINT_DEBUG_OUTPUT
     27#define PRINT_DEBUG_OUTPUT
    2728
    2829#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_codesinking.cpp

    r4804 r4808  
    3838
    3939/** ------------------------------------------------------------------------------------------------------------- *
     40 * @brief findScopeUsages
     41 ** ------------------------------------------------------------------------------------------------------------- */
     42template <class ScopeSet>
     43inline bool findScopeUsages(Statement * stmt, ScopeSet & scopeSet, const PabloBlock & block) {
     44    for (PabloAST * use : stmt->users()) {
     45        assert (isa<Statement>(use));
     46        PabloBlock * const parent = cast<Statement>(use)->getParent();
     47        if (LLVM_LIKELY(parent == &block)) {
     48            return false;
     49        }
     50        scopeSet.insert(parent);
     51    }
     52    return true;
     53}
     54
     55/** ------------------------------------------------------------------------------------------------------------- *
     56 * @brief findScopeUsages
     57 ** ------------------------------------------------------------------------------------------------------------- */
     58template <class ScopeSet>
     59inline bool findScopeUsages(Statement * stmt, ScopeSet & scopeSet, const PabloBlock & block, const PabloBlock & ignored) {
     60    for (PabloAST * use : stmt->users()) {
     61        assert (isa<Statement>(use));
     62        PabloBlock * const parent = cast<Statement>(use)->getParent();
     63        if (LLVM_LIKELY(parent == &block)) {
     64            return false;
     65        }
     66        if (parent != &ignored) {
     67            scopeSet.insert(parent);
     68        }
     69    }
     70    return true;
     71}
     72
     73/** ------------------------------------------------------------------------------------------------------------- *
    4074 * @brief sink
    4175 ** ------------------------------------------------------------------------------------------------------------- */
    4276void CodeSinking::sink(PabloBlock & block) {
    4377
     78    ScopeSet scopes;
    4479    Statement * stmt = block.back(); // note: reverse AST traversal
    4580    while (stmt) {
    46         Statement * next = stmt->getPrevNode();
     81        Statement * prevNode = stmt->getPrevNode();
     82
     83        bool sinkable = true;
     84        // Scan through this statement's users to see if they're all in a nested scope. If so,
     85        // find the least common ancestor of the scope blocks. If it is not the current scope,
     86        // then we can sink the instruction.
    4787        if (isa<If>(stmt)) {
    48             sink(cast<If>(stmt)->getBody());
    49         } else if (isa<While>(stmt)) {
    50             sink(cast<While>(stmt)->getBody());
    51         } else if (isSafeToMove(stmt)) {
    52 
    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;
    60             bool sinkable = false;
    61             for (const PabloAST * use : stmt->users()) {
    62                 if (const Statement * user = dyn_cast<Statement>(use)) {
    63                     if (mProcessed.count(user->getParent())) {
    64                         sinkable = true;
    65                         scopes.insert(user->getParent());
    66                         continue;
    67                     }
     88            PabloBlock & nested = cast<If>(stmt)->getBody();
     89            sink(nested);
     90            for (Assign * def : cast<const If>(stmt)->getDefined()) {
     91                if (!findScopeUsages(def, scopes, block, nested)) {
    6892                    sinkable = false;
    6993                    break;
    7094                }
    7195            }
    72             if (sinkable) {
     96        } else if (isa<While>(stmt)) {
     97            PabloBlock & nested = cast<While>(stmt)->getBody();
     98            sink(nested);
     99            for (Next * var : cast<const While>(stmt)->getVariants()) {
     100                if (escapes(var) && !findScopeUsages(var, scopes, block, nested)) {
     101                    sinkable = false;
     102                    break;
     103                }
     104            }
     105        } else {
     106            sinkable = isSafeToMove(stmt) ? findScopeUsages(stmt, scopes, block) : false;
     107        }
    73108
    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);
     109        if (sinkable) {
     110            assert (scopes.size() > 0);
     111            while (scopes.size() > 1) {
     112                // Find the LCA of both scopes then add the LCA back to the list of scopes.
     113                PabloBlock * scope1 = scopes.back(); scopes.pop_back();
     114                unsigned depth1 = calculateDepthToCurrentBlock(scope1, block);
    79115
    80                     PabloBlock * scope2 = scopes.back();
    81                     scopes.pop_back();
    82                     unsigned depth2 = calculateDepthToCurrentBlock(scope2, block);
     116                PabloBlock * scope2 = scopes.back(); scopes.pop_back();
     117                unsigned depth2 = calculateDepthToCurrentBlock(scope2, block);
    83118
    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                     }
    94 
    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();
    100                     }
    101                     assert (scope1 && scope2);
    102                     // But if the LCA is the current block, we can't sink the statement.
    103                     if (scope1 == &block) {
    104                         sinkable = false;
    105                         break;
    106                     }
    107                     scopes.push_back(scope1);
     119                // If one of these scopes is nested deeper than the other, scan upwards through
     120                // the scope tree until both scopes are at the same depth.
     121                while (depth1 > depth2) {
     122                    scope1 = scope1->getParent();
     123                    --depth1;
     124                }
     125                while (depth1 < depth2) {
     126                    scope2 = scope2->getParent();
     127                    --depth2;
    108128                }
    109129
    110                 if (sinkable) {
    111                     assert (scopes.size() == 1);
    112                     stmt->insertBefore(scopes.front()->front());
     130                // Then iteratively step backwards until we find a matching set of scopes; this
     131                // must be the LCA of our original scopes.
     132                while (scope1 != scope2) {
     133                    scope1 = scope1->getParent();
     134                    scope2 = scope2->getParent();
    113135                }
     136                assert (scope1 && scope2);
     137                // But if the LCA is the current block, we can't sink the statement.
     138                if (scope1 == &block) {
     139                    sinkable = false;
     140                    break;
     141                }
     142                scopes.push_back(scope1);
     143            }
     144            if (sinkable) {
     145                assert (scopes.size() == 1);
     146                assert (isa<If>(stmt) ? &(cast<If>(stmt)->getBody()) != scopes.front() : true);
     147                assert (isa<While>(stmt) ? &(cast<While>(stmt)->getBody()) != scopes.front() : true);
     148                stmt->insertBefore(scopes.front()->front());
    114149            }
    115150        }
    116         stmt = next;
     151        scopes.clear();
     152        stmt = prevNode;
    117153    }
    118     mProcessed.insert(&block);
    119154}
    120155
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_codesinking.hpp

    r4799 r4808  
    1111
    1212class CodeSinking {
    13 
    1413    struct ScopeSet : public std::vector<PabloBlock *> {
    1514        inline bool insert(PabloBlock * block) {
     
    3332    void sink(PabloBlock & block);
    3433    CodeSinking() { }
    35 private:
    36     ScopeSet mProcessed;
    3734};
    3835
Note: See TracChangeset for help on using the changeset viewer.