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

Made code sinking a full code motion pass.

File:
1 moved

Legend:

Unmodified
Added
Removed
  • 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}
Note: See TracChangeset for help on using the changeset viewer.