Ignore:
Timestamp:
Oct 16, 2018, 2:29:44 PM (7 months ago)
Author:
nmedfort
Message:

Added RE_Inspector.

Migrated RE passes to RE_Transformer.

Incorporated Memoizer functionality into RE_Transformer/Inspector.

Removed Memoizer.

Bug fix for unicode_set.

File:
1 edited

Legend:

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

    r5836 r6173  
    2828        }
    2929    }
    30     inline bool contains(T const item) const {
     30    inline bool count(T const item) const {
    3131        const auto i = std::lower_bound(std::vector<T>::begin(), std::vector<T>::end(), item);
    3232        return (i != std::vector<T>::end() && *i == item);
     
    148148            for (;;) {
    149149                temp = temp->getNextNode();
    150                 if (temp == nullptr || mUsers.contains(temp)) {
     150                if (temp == nullptr || mUsers.count(temp)) {
    151151                    if (branch) {
    152152                        // we can move the statement past a branch within its current scope
     
    178178     * @brief hoistLoopInvariants
    179179     ** ------------------------------------------------------------------------------------------------------------- */
    180     void hoistLoopInvariants(Branch * const loop) {
    181         assert (mLoopVariants.empty());
    182         for (Var * variant : loop->getEscaped()) {
    183             mLoopVariants.insert(variant);
    184             mLoopInvariants.insert(variant);
    185         }
    186         mLoopInvariants.erase(loop->getCondition());
     180    void hoistLoopInvariants(While * const loop) {
     181
     182        assert ("Loop variants were not cleared correctly." && mVariants.empty());
     183
     184        // Assume every escaped Var is tainted but not necessarily a variant. Then iterate
     185        // through the loop body and mark any statement that uses a tainted expression as
     186        // tainted itself. If a Var is assigned a tainted value, mark the Var as a variant.
     187
     188        for (const Var * var : loop->getEscaped()) {
     189            mTainted.insert(var);
     190        }
     191
     192        for (const Statement * stmt : *loop->getBody()) {
     193            if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     194                // Trust that any escaped values of an inner branch is a variant.
     195                for (const Var * var : cast<Branch>(stmt)->getEscaped()) {
     196                    mVariants.insert(var);
     197                }
     198            } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     199                const Assign * const a = cast<Assign>(stmt);
     200                if (LLVM_LIKELY(mTainted.count(a->getValue()))) {
     201                    mVariants.insert(a->getVariable());
     202               }
     203            } else {
     204                for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     205                    const PabloAST * const op = stmt->getOperand(i);
     206                    if (mTainted.count(op)) {
     207                        mTainted.insert(stmt);
     208                        break;
     209                    }
     210                }
     211            }
     212        }
     213
     214        assert ("A loop without any variants is an infinite loop" && !mVariants.empty());
     215
     216        mVariants.reserve(mTainted.size());
     217        mTainted.clear();
     218
     219        // Iterate over the loop again but this time move any invariants out of the loop.
     220        // An invariant is any statement whose operands are all non-variants.
    187221
    188222        Statement * outerNode = loop->getPrevNode();
     
    190224        while (stmt) {
    191225            if (isa<Branch>(stmt)) {
    192                 for (Var * var : cast<Branch>(stmt)->getEscaped()) {
    193                     mLoopVariants.insert(var);
    194                     mLoopInvariants.erase(var);
    195                 }
    196226                stmt = stmt->getNextNode();
    197227            } else {
    198228                bool invariant = true;
    199                 if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
    200                     if (mLoopVariants.count(cast<Assign>(stmt)->getValue()) != 0) {
     229                for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     230                    const PabloAST * const op = stmt->getOperand(i);
     231                    if (mVariants.count(op)) {
    201232                        invariant = false;
     233                        break;
    202234                    }
     235                }
     236                Statement * const next = stmt->getNextNode();
     237                if (LLVM_UNLIKELY(invariant)) {
     238                    stmt->insertAfter(outerNode);
     239                    outerNode = stmt;
    203240                } else {
    204                     for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    205                         const PabloAST * const op = stmt->getOperand(i);
    206                         if (mLoopVariants.count(op) != 0) {
    207                             if (isa<Var>(op)) {
    208                                 mLoopInvariants.erase(op);
    209                             }
    210                             invariant = false;
    211                         }
    212                     }
    213                 }
    214 
    215                 Statement * const next = stmt->getNextNode();
    216                 if (LLVM_UNLIKELY(invariant)) {                   
    217                     stmt->insertAfter(outerNode);
    218                     outerNode = stmt;                   
    219                 } else {
    220                     mLoopVariants.insert(stmt);
     241                    mVariants.insert(stmt);
    221242                }
    222243                stmt = next;
    223244            }
    224245        }
    225         mLoopVariants.clear();
    226         assert (mLoopInvariants.empty());
     246
     247        mVariants.clear();
    227248    }
    228249
     
    249270            doCodeMovement(br->getBody());
    250271            if (isa<While>(br)) {
    251                 // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
    252                 // determine whether hoisting will helpful or harmful to the expected run time.
    253                 hoistLoopInvariants(br);
    254             }
    255 
     272                hoistLoopInvariants(cast<While>(br));
     273            }
    256274        }
    257275
     
    261279    ScopeSet        mScopes;
    262280    UserSet         mUsers;
    263     LoopVariants    mLoopVariants;
    264     LoopVariants    mLoopInvariants;
     281    LoopVariants    mVariants;
     282    LoopVariants    mTainted;
    265283};
    266284
Note: See TracChangeset for help on using the changeset viewer.