Changeset 4804


Ignore:
Timestamp:
Sep 28, 2015, 2:39:59 PM (2 years ago)
Author:
nmedfort
Message:

Bug fixes

Location:
icGREP/icgrep-devel/icgrep
Files:
9 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.cpp

    r4797 r4804  
    99
    1010namespace UCD {
     11
     12/** ------------------------------------------------------------------------------------------------------------- *
     13 * @brief addTarget
     14 ** ------------------------------------------------------------------------------------------------------------- */
     15inline void UCDCompiler::addTarget(const UnicodeSet & set) {
     16    mTargetMap.emplace(&set, PabloBlock::createZeroes());
     17}
    1118
    1219/** ------------------------------------------------------------------------------------------------------------- *
     
    8996            }
    9097        }
    91         for (Target t : nonIntersectingTargets) {
    92             mTargetMap.insert(t);
     98        for (const Target t : nonIntersectingTargets) {
     99            mTargetMap.emplace(t.first, t.second);
    93100        }
    94101    }
     
    99106 ** ------------------------------------------------------------------------------------------------------------- */
    100107void UCDCompiler::generateSubRanges(const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder) {
    101     for (Target & t : mTargetMap) {
     108    for (auto & t : mTargetMap) {
    102109        const auto range = rangeIntersect(*t.first, lo, hi);
    103110        PabloAST * target = t.second;
     
    354361    }
    355362    return ranges;
    356 }
    357 
    358 /** ------------------------------------------------------------------------------------------------------------- *
    359  * @brief addTarget
    360  ** ------------------------------------------------------------------------------------------------------------- */
    361 inline void UCDCompiler::addTarget(const UnicodeSet & set) {
    362 #ifdef USE_BOOST
    363     mTargetMap.emplace(&set, PabloBlock::createZeroes());
    364 #else
    365     mTargetMap.insert(std::make_pair(&set, PabloBlock::createZeroes()));
    366 #endif
    367363}
    368364
  • icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.hpp

    r4797 r4804  
    3535    using TargetMap = std::unordered_map<const UnicodeSet *, PabloAST *>;
    3636    #endif
    37     using Target = TargetMap::value_type;
     37    using Target = std::pair<const UnicodeSet *, PabloAST *>;
    3838    using TargetVector = std::vector<Target>;
    3939
  • icGREP/icgrep-devel/icgrep/icgrep-devel.config

    r4797 r4804  
    1 #define USE_BOOST
    2 #define USE_BOOST_MMAP
  • icGREP/icgrep-devel/icgrep/pablo/analysis/pabloverifier.cpp

    r4799 r4804  
    44#include <pablo/printer_pablos.h>
    55#include <iostream>
     6#ifdef USE_BOOST
    67#include <boost/container/flat_set.hpp>
    7 #include <boost/container/flat_map.hpp>
    8 
    9 using namespace boost::container;
     8#else
     9#include <unordered_set>
     10#endif
    1011
    1112namespace pablo {
    1213
    13 using ScopeSet = flat_set<const PabloBlock *>;
     14#ifdef USE_BOOST
     15template <typename Type>
     16using SmallSet = boost::container::flat_set<Type>;
     17#else
     18template <typename Type>
     19using SmallSet = std::unordered_set<Type>;
     20#endif
     21
     22using ScopeSet = SmallSet<const PabloBlock *>;
    1423
    1524/** ------------------------------------------------------------------------------------------------------------- *
     
    202211private:
    203212    const OrderingVerifier * const mParent;
    204     boost::container::flat_set<const PabloAST *> mSet;
     213    SmallSet<const PabloAST *> mSet;
    205214};
    206215
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4797 r4804  
    66#include <boost/graph/filtered_graph.hpp>
    77#include <boost/graph/topological_sort.hpp>
    8 #include <boost/graph/strong_components.hpp>
    98#include <pablo/optimizers/pablo_simplifier.hpp>
    109#include <pablo/analysis/pabloverifier.hpp>
     
    124123        default:
    125124            return false;
    126     }
    127 }
    128 
    129 inline bool isConstant(const VertexData & data) {
    130     switch (getType(data)) {
    131         case TypeId::Zeroes:
    132         case TypeId::Ones:
    133             return true;
    134         default: return false;
    135125    }
    136126}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4797 r4804  
    22#include <pablo/codegenstate.h>
    33#include <pablo/builder.hpp>
    4 #include <stack>
    5 #include <iostream>
    64#include <pablo/printer_pablos.h>
    75#include <cudd.h>
    8 #include <cuddInt.h>
    96#include <util.h>
    10 #include <queue>
    11 #include <boost/circular_buffer.hpp>
    127#include <pablo/optimizers/pablo_simplifier.hpp>
    138#include <pablo/analysis/pabloverifier.hpp>
     9#include <stack>
    1410
    1511using namespace llvm;
     
    117113            }
    118114        } else { // attempt to characterize this statement and replace it if we've encountered an equivalent one
     115
     116            /// TODO: I found evidence that some of the UCD functions have disjunctions of nested marker values
     117            /// in which one is a superset of the other. It's not safe to eliminate the subset marker unless the
     118            /// condition that lead us to compute the first marker is a superset of the condition that let us
     119            /// compute the subset value too. We can alter the superset condition to include the union of both
     120            /// but this may lead to taking an expensive branch more often. So, we'd need to decide whether the
     121            /// cost of each scope is close enough w.r.t. the probability both branches are taken.
     122
    119123            DdNode * bdd = nullptr;
    120124            bool test = false;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4775 r4804  
    4848    void eliminateLogicallyEquivalentStatements(Statement * const stmt, SubsitutionMap & map);
    4949    std::pair<DdNode *, bool> characterize(Statement * const stmt);
    50     void identifyHiddenContradicionsAndTautologies(PabloBlock & block);
    5150private:
    5251    DdNode * Zero() const;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_codesinking.cpp

    r4799 r4804  
    5858
    5959            ScopeSet scopes;
    60             bool canSinkInstruction = false;
     60            bool sinkable = false;
    6161            for (const PabloAST * use : stmt->users()) {
    6262                if (const Statement * user = dyn_cast<Statement>(use)) {
    6363                    if (mProcessed.count(user->getParent())) {
    64                         canSinkInstruction = true;
     64                        sinkable = true;
    6565                        scopes.insert(user->getParent());
    6666                        continue;
    6767                    }
    68                     canSinkInstruction = false;
     68                    sinkable = false;
    6969                    break;
    7070                }
    7171            }
    72             if (canSinkInstruction) {
     72            if (sinkable) {
    7373
    7474                while (scopes.size() > 1) {
     
    102102                    // But if the LCA is the current block, we can't sink the statement.
    103103                    if (scope1 == &block) {
    104                         canSinkInstruction = false;
     104                        sinkable = false;
    105105                        break;
    106106                    }
     
    108108                }
    109109
    110                 if (canSinkInstruction) {
     110                if (sinkable) {
    111111                    assert (scopes.size() == 1);
    112112                    stmt->insertBefore(scopes.front()->front());
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4797 r4804  
    55#include <pablo/printer_pablos.h>
    66#include <pablo/analysis/pabloverifier.hpp>
    7 #include <unordered_map>
     7#ifdef USE_BOOST
     8#include <boost/container/flat_set.hpp>
     9#else
     10#include <unordered_set>
     11#endif
    812#include <iostream>
    913
    1014namespace pablo {
     15
     16#ifdef USE_BOOST
     17template <typename Type>
     18using SmallSet = boost::container::flat_set<Type>;
     19#else
     20template <typename Type>
     21using SmallSet = std::unordered_set<Type>;
     22#endif
    1123
    1224bool Simplifier::optimize(PabloFunction & function) {
     
    7284}
    7385
     86inline void replaceReachableUsersOfWith(Statement * stmt, PabloAST * expr) {
     87    const PabloBlock * const root = stmt->getParent();
     88    SmallSet<const PabloBlock *> forbidden;
     89    for (PabloAST * use : stmt->users()) {
     90        if (LLVM_UNLIKELY(isa<Next>(use))) {
     91            const PabloBlock * parent = cast<Next>(use)->getParent();
     92            if (parent != root) {
     93                forbidden.insert(parent);
     94            }
     95        }
     96    }
     97    for (PabloAST * use : stmt->users()) {
     98        if (Statement * user = dyn_cast<Statement>(use)) {
     99            const PabloBlock * parent = user->getParent();
     100            while (parent && forbidden.count(parent) == 0) {
     101                if (LLVM_UNLIKELY(parent == root)) {
     102                    user->replaceUsesOfWith(stmt, expr);
     103                    break;
     104                }
     105                parent = parent->getParent();
     106            }
     107        }
     108    }
     109}
     110
    74111void Simplifier::eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor) {
    75112    ExpressionTable encountered(predecessor);
     
    87124                continue;
    88125            }
    89             // Force the uses of an local Assign to be the expression instead.
    90             for (PabloAST * use : assign->users()) {
    91                 if (Statement * user = dyn_cast<Statement>(use)) {
    92                     if (LLVM_UNLIKELY(user->getParent() == &block)) {
    93                         user->replaceUsesOfWith(assign, assign->getExpression());
    94                     }
    95                 }
    96             }
     126            // Force the uses of an Assign node that can reach the original expression to use the expression instead.
     127            replaceReachableUsersOfWith(assign, assign->getExpression());
     128        } else if (Next * next = dyn_cast<Next>(stmt)) {
     129            replaceReachableUsersOfWith(next, next->getExpr());
    97130        } else if (If * ifNode = dyn_cast<If>(stmt)) {
    98131            // Check to see if the Cond is Zero and delete the loop.
    99132            if (LLVM_UNLIKELY(isa<Zeroes>(ifNode->getCondition()))) {
    100                 for (Assign * defVar : ifNode->getDefined()) {
    101                     defVar->replaceWith(PabloBlock::createZeroes(), false, true);
    102                 }
    103133                stmt = stmt->eraseFromParent(true);
    104134                continue;
     
    143173                }
    144174            }
    145         } else if (isa<While>(stmt)) {
    146             eliminateRedundantCode(cast<While>(stmt)->getBody(), &encountered);
     175        } else if (While * whileNode = dyn_cast<While>(stmt)) {
     176
     177            const PabloAST * initial = whileNode->getCondition();
     178            if (LLVM_LIKELY(isa<Next>(initial))) {
     179                initial = cast<Next>(initial)->getInitial();
     180            }
     181            if (LLVM_UNLIKELY(isa<Zeroes>(initial))) {
     182                stmt = stmt->eraseFromParent(true);
     183                continue;
     184            }
     185
     186            eliminateRedundantCode(whileNode->getBody(), &encountered);
     187
     188
    147189        } else if (canTriviallyFold(stmt)) { // non-Assign node
    148190            // Do a trivial folding test to see if we're using all 0s or 1s as an operand.
Note: See TracChangeset for help on using the changeset viewer.