Changeset 5536 for icGREP


Ignore:
Timestamp:
Jun 29, 2017, 2:43:49 PM (22 months ago)
Author:
nmedfort
Message:

Flatten If branches when the condition is trivially non zero

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

Legend:

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

    r5486 r5536  
    1313#include <pablo/pe_matchstar.h>
    1414#include <pablo/pe_var.h>
     15#include <boost/container/flat_set.hpp>
    1516#ifndef NDEBUG
    1617#include <pablo/analysis/pabloverifier.hpp>
     
    3031 * @brief fold
    3132 ** ------------------------------------------------------------------------------------------------------------- */
    32 PabloAST * Simplifier::triviallyFold(Statement * stmt, PabloBlock * const block) {
     33PabloAST * triviallyFold(Statement * stmt, PabloBlock * const block) {
    3334    if (isa<Not>(stmt)) {
    3435        PabloAST * value = stmt->getOperand(0);
     
    100101
    101102/** ------------------------------------------------------------------------------------------------------------- *
    102  * @brief discardNestedIfBlock
     103 * @brief VariableTable
     104 ** ------------------------------------------------------------------------------------------------------------- */
     105struct VariableTable {
     106
     107    VariableTable(VariableTable * predecessor = nullptr)
     108    : mPredecessor(predecessor) {
     109
     110    }
     111
     112    PabloAST * get(PabloAST * const var) const {
     113        const auto f = mMap.find(var);
     114        if (f == mMap.end()) {
     115            return (mPredecessor) ? mPredecessor->get(var) : nullptr;
     116        }
     117        return f->second;
     118    }
     119
     120    void put(PabloAST * const var, PabloAST * value) {
     121        const auto f = mMap.find(var);
     122        if (LLVM_LIKELY(f == mMap.end())) {
     123            mMap.emplace(var, value);
     124        } else {
     125            f->second = value;
     126        }
     127        assert (get(var) == value);
     128    }
     129
     130    bool isNonZero(const PabloAST * const var) const {
     131        if (mNonZero.count(var) != 0) {
     132            return true;
     133        } else if (mPredecessor) {
     134            return mPredecessor->isNonZero(var);
     135        }
     136        return false;
     137    }
     138
     139    void addNonZero(const PabloAST * const var) {
     140        mNonZero.insert(var);
     141    }
     142
     143private:
     144    VariableTable * const mPredecessor;
     145    flat_map<PabloAST *, PabloAST *> mMap;
     146    flat_set<const PabloAST *> mNonZero;
     147};
     148
     149/** ------------------------------------------------------------------------------------------------------------- *
     150 * @brief isTrivial
    103151 *
    104152 * If this inner block is composed of only Boolean logic and Assign statements and there are fewer than 3
    105153 * statements, just add the statements in the inner block to the current block
    106154 ** ------------------------------------------------------------------------------------------------------------- */
    107 inline bool discardNestedIfBlock(const PabloBlock * const block) {
     155inline bool isTrivial(const PabloBlock * const block) {
    108156    unsigned computations = 0;
    109157    for (const Statement * stmt : *block) {
     
    126174
    127175/** ------------------------------------------------------------------------------------------------------------- *
    128  * @brief VariableTable
    129  ** ------------------------------------------------------------------------------------------------------------- */
    130 struct Simplifier::VariableTable {
    131 
    132     VariableTable(VariableTable * predecessor = nullptr)
    133     : mPredecessor(predecessor) {
    134 
    135     }
    136 
    137     PabloAST * get(PabloAST * const var) const {
    138         const auto f = mMap.find(var);
    139         if (f == mMap.end()) {
    140             return (mPredecessor) ? mPredecessor->get(var) : nullptr;
    141         }
    142         return f->second;
    143     }
    144 
    145     void put(PabloAST * const var, PabloAST * value) {
    146         const auto f = mMap.find(var);
    147         if (LLVM_LIKELY(f == mMap.end())) {
    148             mMap.emplace(var, value);
    149         } else {
    150             f->second = value;
    151         }
    152         assert (get(var) == value);
    153     }
    154 
    155 private:
    156     VariableTable * const mPredecessor;
    157     flat_map<PabloAST *, PabloAST *> mMap;
    158 };
     176 * @brief flatten
     177 ** ------------------------------------------------------------------------------------------------------------- */
     178Statement * flatten(Branch * const br) {
     179    Statement * stmt = br;
     180    Statement * nested = br->getBody()->front();
     181    while (nested) {
     182        Statement * next = nested->removeFromParent();
     183        nested->insertAfter(stmt);
     184        stmt = nested;
     185        nested = next;
     186    }
     187    return br->eraseFromParent();
     188}
    159189
    160190/** ------------------------------------------------------------------------------------------------------------- *
     
    164194 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
    165195 ** ------------------------------------------------------------------------------------------------------------- */
    166 void Simplifier::redundancyElimination(PabloBlock * const block, ExpressionTable * const et, VariableTable * const vt) {
     196void redundancyElimination(PabloBlock * const block, ExpressionTable * const et, VariableTable * const vt) {
    167197    VariableTable variables(vt);
    168198
     
    170200    // body since the Var will likely be assigned a different value in the current
    171201    // body that should be used on the subsequent iteration of the loop.
    172     if (While * br = dyn_cast_or_null<While>(block->getBranch())) {
    173         for (Var * var : br->getEscaped()) {
    174             variables.put(var, var);
     202    if (Branch * br = block->getBranch()) {
     203        assert ("block has a branch but the expression and variable tables were not supplied" && et && vt);
     204        variables.addNonZero(br->getCondition());
     205        if (LLVM_UNLIKELY(isa<While>(br))) {
     206            for (Var * var : cast<While>(br)->getEscaped()) {
     207                variables.put(var, var);
     208            }
    175209        }
    176210    }
     
    220254            }
    221255
     256            if (LLVM_LIKELY(isa<If>(br))) {
     257                if (LLVM_UNLIKELY(variables.isNonZero(br->getCondition()))) {
     258                    stmt = flatten(br);
     259                    continue;
     260                }
     261            }
     262
    222263            // Process the Branch body
    223264            redundancyElimination(br->getBody(), &expressions, &variables);
    224265
    225             // Check whether this If branch has enough operations nested within it to
    226             // be worth the cost of the branch.
    227             if (LLVM_UNLIKELY(isa<If>(br) && discardNestedIfBlock(br->getBody()))) {
    228                 Statement * nested = br->getBody()->front();
    229                 while (nested) {
    230                     Statement * next = nested->removeFromParent();
    231                     nested->insertAfter(stmt);
    232                     stmt = nested;
    233                     nested = next;
    234                 }
    235                 stmt = br->eraseFromParent();
    236                 continue;
     266            if (LLVM_LIKELY(isa<If>(br))) {
     267                // Check whether the cost of testing the condition and taking the branch with
     268                // 100% correct prediction rate exceeds the cost of the body itself
     269                if (LLVM_UNLIKELY(isTrivial(br->getBody()))) {
     270                    stmt = flatten(br);
     271                    continue;
     272                }
    237273            }
    238274
     
    265301            }
    266302
     303            // Check whether this statement is trivially non-zero and if so, add it to our set of non-zero variables.
     304            // This will allow us to flatten an If scope if its branch is always taken.
     305            if (isa<Or>(stmt)) {
     306                for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     307                    if (LLVM_UNLIKELY(variables.isNonZero(stmt->getOperand(i)))) {
     308                        variables.addNonZero(stmt);
     309                        break;
     310                    }
     311                }
     312            } else if (isa<Advance>(stmt)) {
     313                const Advance * const adv = cast<Advance>(stmt);
     314                if (LLVM_LIKELY(adv->getAmount() < 32)) {
     315                    if (LLVM_UNLIKELY(variables.isNonZero(adv->getExpression()))) {
     316                        variables.addNonZero(adv);
     317                    }
     318                }
     319            }
    267320        }
    268321
     
    273326    // was updated within this block and update the preceeding block's variable state appropriately.
    274327
    275     if (Branch * const br = block->getBranch()) { assert (vt);
     328    if (Branch * const br = block->getBranch()) {
    276329
    277330        // When removing identical escaped values, we have to consider that the identical Vars could
     
    311364 * @brief deadCodeElimination
    312365 ** ------------------------------------------------------------------------------------------------------------- */
    313 void Simplifier::deadCodeElimination(PabloBlock * const block) {
     366void deadCodeElimination(PabloBlock * const block) {
    314367
    315368    flat_map<PabloAST *, Assign *> unread;
     
    355408 * @brief deadCodeElimination
    356409 ** ------------------------------------------------------------------------------------------------------------- */
    357 void Simplifier::deadCodeElimination(PabloKernel * kernel) {
     410void deadCodeElimination(PabloKernel * kernel) {
    358411
    359412    deadCodeElimination(kernel->getEntryBlock());
     
    387440 * Find and replace any Pablo operations with a less expensive equivalent operation whenever possible.
    388441 ** ------------------------------------------------------------------------------------------------------------- */
    389 void Simplifier::strengthReduction(PabloBlock * const block) {
     442void strengthReduction(PabloBlock * const block) {
    390443
    391444    Statement * stmt = block->front();
     
    455508 ** ------------------------------------------------------------------------------------------------------------- */
    456509bool Simplifier::optimize(PabloKernel * kernel) {
    457     redundancyElimination(kernel->getEntryBlock());
     510    redundancyElimination(kernel->getEntryBlock(), nullptr, nullptr);
    458511    strengthReduction(kernel->getEntryBlock());
    459512    deadCodeElimination(kernel);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r5486 r5536  
    55
    66class PabloKernel;
    7 class PabloAST;
    8 class Variadic;
    9 class Statement;
    10 class PabloBlock;
    11 
    12 struct ExpressionTable;
    137
    148class Simplifier {
    15     friend class BooleanReassociationPass;
    16     struct VariableTable;
    179public:
    1810    static bool optimize(PabloKernel * kernel);
    1911protected:
    2012    Simplifier() = default;
    21 private:
    22     static PabloAST * triviallyFold(Statement * const stmt, PabloBlock * const block);
    23     static void redundancyElimination(PabloBlock * const block, ExpressionTable * et = nullptr, VariableTable * const vt = nullptr);
    24     static void deadCodeElimination(PabloKernel * const kernel);
    25     static void deadCodeElimination(PabloBlock * const block);
    26     static void strengthReduction(PabloBlock * const block);
    2713};
    2814
Note: See TracChangeset for help on using the changeset viewer.