Changeset 4854


Ignore:
Timestamp:
Oct 28, 2015, 12:47:36 PM (3 years ago)
Author:
nmedfort
Message:

Made code sinking a full code motion pass.

Location:
icGREP/icgrep-devel/icgrep
Files:
5 edited
2 moved

Legend:

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

    r4820 r4854  
    7070SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_compiler.cpp pablo/carry_manager.cpp pablo/carry_data.cpp IDISA/idisa_builder.cpp)
    7171SET(PABLO_SRC ${PABLO_SRC} pablo/analysis/pabloverifier.cpp)
    72 SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/pablo_codesinking.cpp pablo/optimizers/booleanreassociationpass.cpp)
     72SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/codemotionpass.cpp pablo/optimizers/booleanreassociationpass.cpp)
    7373IF (ENABLE_MULTIPLEXING)
    7474SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_automultiplexing.cpp pablo/optimizers/pablo_bddminimization.cpp)
  • icGREP/icgrep-devel/icgrep/generate_predefined_ucd_functions.cpp

    r4839 r4854  
    264264    PabloVerifier::verify(*function, "creation");
    265265    Simplifier::optimize(*function);
    266     CodeSinking::optimize(*function);
     266    CodeMotionPass::optimize(*function);
    267267    #ifdef ENABLE_MULTIPLEXING
    268268    BDDMinimizationPass::optimize(*function);
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r4829 r4854  
    407407re/re_alt.h
    408408re/re_grapheme_boundary.hpp
     409pablo/optimizers/codemotionpass.h
     410pablo/optimizers/codemotionpass.cpp
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.cpp

    r4853 r4854  
    1 #include "pablo_codesinking.hpp"
     1#include "codemotionpass.h"
    22#include <pablo/function.h>
     3#include <pablo/ps_while.h>
    34#include <pablo/analysis/pabloverifier.hpp>
     5#ifdef USE_BOOST
     6#include <boost/container/flat_set.hpp>
     7#else
     8#include <unordered_set>
     9#endif
     10#include <pablo/printer_pablos.h>
     11#include <iostream>
    412
    513namespace pablo {
    614
     15#ifdef USE_BOOST
     16using LoopVariants = boost::container::flat_set<const PabloAST *>;
     17#else
     18using LoopVariants = std::unordered_set<const PabloAST *>;
     19#endif
     20
    721/** ------------------------------------------------------------------------------------------------------------- *
    822 * @brief optimize
    923 ** ------------------------------------------------------------------------------------------------------------- */
    10 bool CodeSinking::optimize(PabloFunction & function) {
    11     CodeSinking lcf;
    12     lcf.sink(function.getEntryBlock());
     24bool CodeMotionPass::optimize(PabloFunction & function) {
     25    CodeMotionPass::process(function.getEntryBlock());
    1326    #ifndef NDEBUG
    1427    PabloVerifier::verify(function, "post-sinking");
     
    1629    return true;
    1730}
     31
     32/** ------------------------------------------------------------------------------------------------------------- *
     33 * @brief process
     34 ** ------------------------------------------------------------------------------------------------------------- */
     35void CodeMotionPass::process(PabloBlock & block) {
     36    sink(block);
     37    for (Statement * stmt : block) {
     38        if (isa<If>(stmt)) {
     39            process(cast<If>(stmt)->getBody());
     40        } else if (isa<While>(stmt)) {
     41            process(cast<While>(stmt)->getBody());
     42            // TODO: if we analyzed the probability of this loop being executed once, twice or many times, we could
     43            // determine hoisting will helpful or harmful to the expected run time.
     44            hoistLoopInvariants(cast<While>(stmt));
     45        }
     46    }
     47}
     48
    1849
    1950/** ------------------------------------------------------------------------------------------------------------- *
     
    72103
    73104/** ------------------------------------------------------------------------------------------------------------- *
     105 * @brief isAcceptableTarget
     106 ** ------------------------------------------------------------------------------------------------------------- */
     107inline bool CodeMotionPass::isAcceptableTarget(Statement * stmt, ScopeSet & scopeSet, const PabloBlock & block) {
     108    // Scan through this statement's users to see if they're all in a nested scope. If so,
     109    // find the least common ancestor of the scope blocks. If it is not the current scope,
     110    // then we can sink the instruction.
     111    if (isa<If>(stmt)) {
     112        for (Assign * def : cast<If>(stmt)->getDefined()) {
     113            if (!findScopeUsages(def, scopeSet, block, cast<If>(stmt)->getBody())) {
     114                return false;
     115            }
     116        }
     117    } else if (isa<While>(stmt)) {
     118        for (Next * var : cast<While>(stmt)->getVariants()) {
     119            if (escapes(var) && !findScopeUsages(var, scopeSet, block, cast<While>(stmt)->getBody())) {
     120                return false;
     121            }
     122        }
     123    } else if (isSafeToMove(stmt)) {
     124        return findScopeUsages(stmt, scopeSet, block);
     125    }
     126    return false;
     127}
     128
     129/** ------------------------------------------------------------------------------------------------------------- *
    74130 * @brief sink
    75131 ** ------------------------------------------------------------------------------------------------------------- */
    76 void CodeSinking::sink(PabloBlock & block) {
    77 
     132void CodeMotionPass::sink(PabloBlock & block) {
    78133    ScopeSet scopes;
    79134    Statement * stmt = block.back(); // note: reverse AST traversal
    80135    while (stmt) {
    81136        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.
    87         if (isa<If>(stmt)) {
    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)) {
    92                     sinkable = false;
    93                     break;
    94                 }
    95             }
    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         }
    108 
    109         if (sinkable) {
     137        if (isAcceptableTarget(stmt, scopes, block)) {
    110138            assert (scopes.size() > 0);
    111139            while (scopes.size() > 1) {
     
    137165                // But if the LCA is the current block, we can't sink the statement.
    138166                if (scope1 == &block) {
    139                     sinkable = false;
     167                    goto abort;
     168                }
     169                scopes.push_back(scope1);
     170            }
     171            assert (scopes.size() == 1);
     172            assert (isa<If>(stmt) ? &(cast<If>(stmt)->getBody()) != scopes.front() : true);
     173            assert (isa<While>(stmt) ? &(cast<While>(stmt)->getBody()) != scopes.front() : true);
     174            stmt->insertBefore(scopes.front()->front());
     175        }
     176abort:  scopes.clear();
     177        stmt = prevNode;
     178    }
     179}
     180
     181/** ------------------------------------------------------------------------------------------------------------- *
     182 * @brief hoistWhileLoopInvariants
     183 ** ------------------------------------------------------------------------------------------------------------- */
     184void CodeMotionPass::hoistLoopInvariants(While * loop) {
     185    LoopVariants loopVariants;
     186    for (Next * variant : loop->getVariants()) {
     187        loopVariants.insert(variant);
     188        loopVariants.insert(variant->getInitial());
     189    }
     190    Statement * outerNode = loop->getPrevNode();
     191    Statement * stmt = loop->getBody().front();
     192    while (stmt) {
     193        if (isa<If>(stmt)) {
     194            for (Assign * def : cast<If>(stmt)->getDefined()) {
     195                loopVariants.insert(def);
     196            }
     197        } else if (isa<While>(stmt)) {
     198            for (Next * var : cast<While>(stmt)->getVariants()) {
     199                loopVariants.insert(var);
     200            }
     201        } else {
     202            bool invariant = true;
     203            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     204                if (loopVariants.count(stmt->getOperand(i)) != 0) {
     205                    invariant = false;
    140206                    break;
    141207                }
    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());
    149             }
    150         }
    151         scopes.clear();
    152         stmt = prevNode;
    153     }
    154 }
    155 
    156 }
     208            }
     209            if (LLVM_UNLIKELY(invariant)) {
     210                Statement * next = stmt->getNextNode();
     211                stmt->insertAfter(outerNode);
     212                outerNode = stmt;
     213                stmt = next;
     214            } else {
     215                loopVariants.insert(stmt);
     216                stmt = stmt->getNextNode();
     217            }
     218        }
     219    }
     220}
     221
     222}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.h

    r4853 r4854  
    1010class PabloFunction;
    1111
    12 class CodeSinking {
     12class CodeMotionPass {
    1313    struct ScopeSet : public std::vector<PabloBlock *> {
    1414        inline bool insert(PabloBlock * block) {
     
    3030    static bool optimize(PabloFunction & function);
    3131protected:
    32     void sink(PabloBlock & block);
    33     CodeSinking() { }
     32    static void process(PabloBlock & block);
     33    static bool isAcceptableTarget(Statement *stmt, ScopeSet & scopeSet, const PabloBlock & block);
     34    static void sink(PabloBlock & block);   
     35    static void hoistLoopInvariants(While * loop);
    3436};
    3537
  • icGREP/icgrep-devel/icgrep/pablo/ps_while.h

    r4805 r4854  
    1919
    2020    using NextAllocator = VectorAllocator::rebind<Next*>::other;
    21     using NextVars = std::vector<Next *, NextAllocator>;
     21    using Variants = std::vector<Next *, NextAllocator>;
    2222
    2323    static inline bool classof(const PabloAST * e) {
     
    3232        return getOperand(0);
    3333    }
    34     inline NextVars & getVariants() {
     34    inline Variants & getVariants() {
    3535        return mNext;
    3636    }
    37     inline const NextVars & getVariants() const {
     37    inline const Variants & getVariants() const {
    3838        return mNext;
    3939    }
     
    5050private:
    5151    PabloBlock &    mBody;
    52     NextVars        mNext;
     52    Variants        mNext;
    5353};
    5454
  • icGREP/icgrep-devel/icgrep/toolchain.cpp

    r4848 r4854  
    3636#include <pablo/pablo_compiler.h>
    3737#include <pablo/optimizers/pablo_simplifier.hpp>
    38 #include <pablo/optimizers/pablo_codesinking.hpp>
     38#include <pablo/optimizers/codemotionpass.h>
    3939#ifdef ENABLE_MULTIPLEXING
    4040#include <pablo/optimizers/pablo_automultiplexing.hpp>
     
    142142    }
    143143    if (PabloSinkingPass) {
    144         pablo::CodeSinking::optimize(*function);
     144        pablo::CodeMotionPass::optimize(*function);
    145145    }
    146146#ifdef ENABLE_MULTIPLEXING   
Note: See TracChangeset for help on using the changeset viewer.