Changeset 4868 for icGREP


Ignore:
Timestamp:
Nov 12, 2015, 4:26:25 PM (4 years ago)
Author:
nmedfort
Message:

Work on bug fixes for multiplexing pass.

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

Legend:

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

    r4856 r4868  
    140140IF (ENABLE_MULTIPLEXING)
    141141message(STATUS "Enabling Multiplexing")
    142 SET(CUDD_ROOT "${CMAKE_SOURCE_DIR}/../cudd-2.5.1")
    143 file(GLOB CUDD_SOURCES "${CUDD_ROOT}/cudd/*.c")
    144 file(GLOB EPD_SOURCES "${CUDD_ROOT}/epd/*.c")
    145 file(GLOB MTR_SOURCES "${CUDD_ROOT}/mtr/*.c")
    146 file(GLOB ST_SOURCES "${CUDD_ROOT}/st/*.c")
    147 file(GLOB UTIL_SOURCES "${CUDD_ROOT}/util/*.c")
    148 add_library(CUDD ${UTIL_SOURCES} ${MTR_SOURCES} ${CUDD_SOURCES} ${ST_SOURCES} ${EPD_SOURCES})
    149 include_directories(${CUDD_ROOT}/cudd)
    150 include_directories(${CUDD_ROOT}/epd)
    151 include_directories(${CUDD_ROOT}/mtr)
    152 include_directories(${CUDD_ROOT}/st)
    153 include_directories(${CUDD_ROOT}/util)
    154 target_link_libraries (PabloADT CUDD)
     142SET(BUDDY_ROOT "${CMAKE_SOURCE_DIR}/../buddy-2.4")
     143file(GLOB BUDDY_SOURCES "${BUDDY_ROOT}/src/*.cpp")
     144add_library(BUDDY ${BUDDY_SOURCES})
     145include_directories(${BUDDY_ROOT}/src)
     146target_link_libraries (PabloADT BUDDY)
    155147SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DENABLE_MULTIPLEXING")
    156148ENDIF()
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r4854 r4868  
    409409pablo/optimizers/codemotionpass.h
    410410pablo/optimizers/codemotionpass.cpp
     411../buddy-2.4/src/bdd.h
     412../buddy-2.4/src/bddio.cpp
     413../buddy-2.4/src/bddop.cpp
     414../buddy-2.4/src/bvec.cpp
     415../buddy-2.4/src/bvec.h
     416../buddy-2.4/src/cache.cpp
     417../buddy-2.4/src/cache.h
     418../buddy-2.4/src/fdd.cpp
     419../buddy-2.4/src/fdd.h
     420../buddy-2.4/src/imatrix.cpp
     421../buddy-2.4/src/imatrix.h
     422../buddy-2.4/src/kernel.cpp
     423../buddy-2.4/src/kernel.h
     424../buddy-2.4/src/pairs.cpp
     425../buddy-2.4/src/prime.cpp
     426../buddy-2.4/src/prime.h
     427../buddy-2.4/src/reorder.cpp
     428../buddy-2.4/src/tree.cpp
     429../buddy-2.4/src/bdd.h
     430../buddy-2.4/src/bddio.c
     431../buddy-2.4/src/bddop.c
     432../buddy-2.4/src/bddtest.cxx
     433../buddy-2.4/src/bddtree.h
     434../buddy-2.4/src/cache.h
     435../buddy-2.4/src/cache.c
     436../buddy-2.4/src/bvec.c
     437../buddy-2.4/src/bvec.h
     438../buddy-2.4/src/cppext.cxx
     439../buddy-2.4/src/fdd.c
     440../buddy-2.4/src/fdd.h
     441../buddy-2.4/src/imatrix.h
     442../buddy-2.4/src/imatrix.c
     443../buddy-2.4/src/pairs.c
     444../buddy-2.4/src/prime.c
     445../buddy-2.4/src/prime.h
     446../buddy-2.4/src/tree.c
     447../buddy-2.4/src/kernel.h
     448../buddy-2.4/src/kernel.c
     449../buddy-2.4/src/config.h
     450../buddy-2.4/src/bddtree.h
     451UCD/EastAsianWidth.h
     452UCD/DerivedCoreProperties.h
     453UCD/PropList.h
     454UCD/LineBreak.h
     455UCD/Scripts.h
     456UCD/ScriptExtensions.h
     457UCD/HangulSyllableType.h
     458UCD/Blocks.h
     459UCD/PropertyAliases.h
     460UCD/DerivedGeneralCategory.h
     461UCD/CaseFolding_txt.h
     462UCD/DerivedJoiningGroup.h
     463UCD/GraphemeBreakProperty.h
     464UCD/DerivedCombiningClass.h
     465UCD/WordBreakProperty.h
     466UCD/DerivedDecompositionType.h
     467UCD/DerivedBinaryProperties.h
     468UCD/DerivedNumericType.h
     469UCD/CaseFolding_txt.cpp
     470UCD/DerivedBidiClass.h
     471UCD/PropertyObjectTable.h
     472UCD/DerivedAge.h
     473UCD/DerivedJoiningType.h
     474UCD/PropertyValueAliases.h
     475UCD/SentenceBreakProperty.h
     476UCD/resolve_properties.h
     477UCD/PropertyObjects.h
     478UCD/PropertyObjects.cpp
     479UCD/precompiled_properties.cpp
     480UCD/precompiled_properties.h
     481UCD/resolve_properties.cpp
     482UCD/ucd_compiler.hpp
     483UCD/ucd_compiler.cpp
     484UCD/unicode_set.h
     485UCD/unicode_set.cpp
  • icGREP/icgrep-devel/icgrep/icgrep-devel.includes

    r4788 r4868  
    55pablo/analysis
    66pablo/optimizers
    7 ../cudd-2.5.1/cudd
    8 ../cudd-2.5.1/util
    97UCD
    10 ../ucd
    11 ../QA/unit-tests
    128/usr/include/boost/filesystem
    139/usr/include/boost/iostreams
    1410/usr/include/boost/system
     11../cudd-2.5.1/cudd
     12../buddy-2.4/src
  • icGREP/icgrep-devel/icgrep/icgrep.cpp

    r4860 r4868  
    9292    re::RE * re_ast = nullptr;
    9393    for (unsigned i = 0; i < regexVector.size(); i++) {
    94         try
    95         {
    96             re_ast = re::RE_Parser::parse(regexVector[i], globalFlags);
    97         }
    98         catch (ParseFailure failure)
    99         {
    100             std::cerr << "Regex parsing failure: " << failure.what() << std::endl;
    101             std::cerr << regexVector[i] << std::endl;
    102             exit(1);
    103         }
    104         catch (UCD::UnicodePropertyExpressionError e)
    105         {
    106             std::cerr << "Unicode error: " << e.what() << std::endl;
    107             std::cerr << regexVector[i] << std::endl;
    108             exit(1);
    109         }
     94//        try
     95//        {
     96//            re_ast = re::RE_Parser::parse(regexVector[i], globalFlags);
     97//        }
     98//        catch (ParseFailure failure)
     99//        {
     100//            std::cerr << "Regex parsing failure: " << failure.what() << std::endl;
     101//            std::cerr << regexVector[i] << std::endl;
     102//            exit(1);
     103//        }
     104//        catch (UCD::UnicodePropertyExpressionError e)
     105//        {
     106//            std::cerr << "Unicode error: " << e.what() << std::endl;
     107//            std::cerr << regexVector[i] << std::endl;
     108//            exit(1);
     109//        }
     110        re_ast = re::RE_Parser::parse(regexVector[i], globalFlags);
    110111        REs.push_back(re_ast);
    111112    }
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r4861 r4868  
    258258    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
    259259        return renameNonNamedNode(expr2, std::move(prefix));
    260     } else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
     260    }
     261    else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
    261262        return renameNonNamedNode(expr1, std::move(prefix));
    262263    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     
    337338    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
    338339        return renameNonNamedNode(expr2, std::move(prefix));
    339     } else if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
     340    }
     341    else if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
    340342        return renameNonNamedNode(expr1, std::move(prefix));
    341343    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
     
    453455PabloAST * PabloBlock::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string prefix) {
    454456    assert (condition && trueExpr && falseExpr);
    455 
    456457    if (isa<Zeroes>(condition)){
    457458        return renameNonNamedNode(falseExpr, std::move(prefix));
     
    526527    return nextScopeIndex;
    527528}   
    528            
    529    
    530        
    531529   
    532530/// CONSTRUCTOR
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4862 r4868  
    44#include <boost/circular_buffer.hpp>
    55#include <boost/graph/adjacency_list.hpp>
     6#include <boost/graph/filtered_graph.hpp>
    67#include <boost/graph/topological_sort.hpp>
    78#include <pablo/optimizers/pablo_simplifier.hpp>
     
    910#include <algorithm>
    1011#include <numeric> // std::iota
     12
     13#ifndef NDEBUG
     14#include <queue>
     15#include <pablo/printer_pablos.h>
     16#include <iostream>
     17#include <llvm/Support/raw_os_ostream.h>
     18#include <boost/graph/strong_components.hpp>
     19#endif
     20
    1121
    1222using namespace boost;
     
    511521                }
    512522                if (ready) {
     523
    513524                    auto entry = std::make_pair(ordering[v], v);
    514525                    auto position = std::lower_bound(readySet.begin(), readySet.end(), entry, readyComparator);
     
    531542 * @brief summarizeAST
    532543 *
    533  * This function scans through a scope blockand computes a DAG G in which any sequences of AND, OR or XOR functions
     544 * This function scans through a scope block and computes a DAG G in which any sequences of AND, OR or XOR functions
    534545 * are "flattened" (i.e., allowed to have any number of inputs.)
    535546 ** ------------------------------------------------------------------------------------------------------------- */
     
    556567                const Vertex v = getSummaryVertex(def, G, M, block);
    557568                add_edge(def, u, v, G);
    558                 resolveUsages(v, def, block, G, M, stmt);
     569                resolveNestedUsages(v, def, block, G, M, stmt);
    559570            }
    560571        } else if (isa<While>(stmt)) {
     
    569580                remove_edge(v, u, G);
    570581                add_edge(var, u, v, G);
    571                 resolveUsages(v, var, block, G, M, stmt);
     582                resolveNestedUsages(v, var, block, G, M, stmt);
    572583            }
    573584        } else {
    574             resolveUsages(u, stmt, block, G, M);
     585            resolveNestedUsages(u, stmt, block, G, M);
    575586        }
    576587    }
     
    580591
    581592/** ------------------------------------------------------------------------------------------------------------- *
    582  * @brief resolveUsages
    583  ** ------------------------------------------------------------------------------------------------------------- */
    584 void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, const Statement * const ignoreIfThis) const {
     593 * @brief resolveNestedUsages
     594 ** ------------------------------------------------------------------------------------------------------------- */
     595void BooleanReassociationPass::resolveNestedUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, const Statement * const ignoreIfThis) const {
    585596    for (PabloAST * user : expr->users()) {
    586597        assert (user);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4862 r4868  
    2525    void summarizeAST(PabloBlock & block, Graph & G, Map & M) const;
    2626    static void summarizeGraph(const PabloBlock & block, Graph & G, std::vector<Vertex> & mapping, Map &M);
    27     void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, const Statement * const ignoreIfThis = nullptr) const;
     27    void resolveNestedUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, const Statement * const ignoreIfThis = nullptr) const;
    2828    void redistributeAST(const PabloBlock & block, Graph & G, Map & M) const;
    2929    void rewriteAST(PabloBlock & block, Graph & G);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4860 r4868  
    99#include <boost/graph/topological_sort.hpp>
    1010#include <boost/range/iterator_range.hpp>
    11 #include <llvm/ADT/BitVector.h>
    12 #include <cudd.h>
    13 #include <cuddInt.h>
    14 #include <util.h>
     11#include <pablo/analysis/pabloverifier.hpp>
    1512#include <stack>
    1613#include <queue>
    1714#include <unordered_set>
    18 #include <pablo/optimizers/booleanreassociationpass.h>
    19 #include <pablo/analysis/pabloverifier.hpp>
     15#include <bdd.h>
    2016
    2117using namespace llvm;
     
    116112    AutoMultiplexing am(limit, maxSelections);
    117113    RECORD_TIMESTAMP(start_initialize);
    118     const bool abort = am.initialize(function);
     114    const unsigned advances = am.initialize(function);
    119115    RECORD_TIMESTAMP(end_initialize);
    120116
     
    123119    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
    124120
    125     if (abort) {
     121    if (advances == 0) {
    126122        return false;
    127123    }
     
    132128
    133129    LOG("Characterize:            " << (end_characterize - start_characterize));
     130
     131    LOG("Nodes in BDD:            " << bdd_getnodenum() << " of " << bdd_getallocnum());
     132
     133    RECORD_TIMESTAMP(start_shutdown);
     134    bdd_done();
     135    RECORD_TIMESTAMP(end_shutdown);
     136    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
    134137
    135138    RECORD_TIMESTAMP(start_create_multiplex_graph);
     
    138141    LOG("GenerateCandidateSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
    139142
    140     RECORD_TIMESTAMP(start_shutdown);
    141     am.Shutdown();
    142     RECORD_TIMESTAMP(end_shutdown);
    143     LOG("Shutdown:                " << (end_shutdown - start_shutdown));
    144 
    145143    if (multiplex) {
    146144
     
    160158        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
    161159
    162         #ifndef NDEBUG
    163         PabloVerifier::verify(function, "post-multiplexing");
    164         #endif
    165 
    166         BooleanReassociationPass::optimize(function);
     160        AutoMultiplexing::topologicalSort(function);
    167161    }
    168162
     
    179173 * the proper variable ordering.
    180174 ** ------------------------------------------------------------------------------------------------------------- */
    181 bool AutoMultiplexing::initialize(PabloFunction & function) {
     175unsigned AutoMultiplexing::initialize(PabloFunction & function) {
    182176
    183177    flat_map<const PabloAST *, unsigned> map;   
     
    186180
    187181    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    188     unsigned n = 0, m = 0;
     182    unsigned statements = 0, advances = 0;
     183    unsigned maxDepth = 0;
     184    mResolvedScopes.emplace(&function.getEntryBlock(), nullptr);
    189185    for (Statement * stmt = function.getEntryBlock().front(); ; ) {
    190186        while ( stmt ) {
    191             ++n;
     187            ++statements;
    192188            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    193189                // Set the next statement to be the first statement of the inner scope and push the
     
    197193                scope.push(stmt->getNextNode());
    198194                stmt = nested.front();
     195                maxDepth = std::max<unsigned>(maxDepth, scope.size());
    199196                assert (stmt);
    200197                continue;
     
    205202            switch (stmt->getClassTypeId()) {
    206203                case TypeId::Advance:
    207                     mAdvanceMap.emplace(stmt, m);
    208                     map.emplace(stmt, m++);
     204                    ++advances;
     205                case TypeId::ScanThru:
    209206                case TypeId::Call:
    210                 case TypeId::ScanThru:
    211207                case TypeId::MatchStar:
    212                     variableCount++;
     208                    ++variableCount;
    213209                    break;
    214210                default:
     
    225221
    226222    // If there are fewer than three Advances in this program, just abort. We cannot reduce it.
    227     if (m < 3) {
    228         return true;
     223    if (advances < 3) {
     224        return 0;
    229225    }
    230226
     
    236232    // which advances ought to be multiplexed.
    237233
    238     matrix<bool> G(n, m); // Let G be a matrix with n rows of m (Advance) elements
     234    matrix<bool> G(statements, advances);
    239235    G.clear();
    240     for (unsigned i = 0; i != m; ++i) {
     236    for (unsigned i = 0; i != advances; ++i) {
    241237        G(i, i) = true;
    242238    }
    243239
    244     n = m;
    245     m = 0;
    246 
    247     const Statement * stmt = function.getEntryBlock().front();
    248     for (;;) {
     240    unsigned n = advances;
     241    unsigned m = 0;
     242
     243    for (const Statement * stmt = function.getEntryBlock().front();;) {
    249244        while ( stmt ) {
    250245
    251             unsigned u;
     246            unsigned u = 0;
    252247            if (isa<Advance>(stmt)) {
    253                 assert (mAdvanceMap.count(stmt) && mAdvanceMap[stmt] == m);
    254248                u = m++;
    255             }
    256             else {
     249            } else {
    257250                u = n++;
    258                 map.emplace(stmt, u);
    259             }
     251            }
     252            map.emplace(stmt, u);
    260253
    261254            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     
    289282    // Since G is a use-def graph and we want our constraint graph to be a def-use graph,
    290283    // reverse the edges as we're writing them to obtain the transposed graph.
    291     mConstraintGraph = ConstraintGraph(m);
    292     mSubsetGraph = SubsetGraph(m);
    293 
    294     for (unsigned i = 0; i != m; ++i) {
     284    mConstraintGraph = ConstraintGraph(advances);
     285    mSubsetGraph = SubsetGraph(advances);
     286
     287    for (unsigned i = 0; i != advances; ++i) {
    295288        G(i, i) = false;
    296         for (unsigned j = 0; j != m; ++j) {
     289        for (unsigned j = 0; j != advances; ++j) {
    297290            if (G(i, j)) {
    298291                add_edge(j, i, mConstraintGraph);
     
    302295
    303296    // Initialize the BDD engine ...
    304     mManager = Cudd_Init((variableCount + function.getNumOfParameters()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    305     Cudd_AutodynDisable(mManager);
     297    bdd_init(10000000, 100000);
     298    bdd_setvarnum(variableCount + function.getNumOfParameters());
     299    bdd_setcacheratio(64);
     300    bdd_setmaxincrease(10000000);
     301    // bdd_setminfreenodes(10000);
     302    bdd_autoreorder(BDD_REORDER_NONE);
    306303
    307304    // Map the predefined 0/1 entries
    308     mCharacterizationMap[PabloBlock::createZeroes()] = Zero();
    309     mCharacterizationMap[PabloBlock::createOnes()] = One();
     305    mCharacterizationMap[PabloBlock::createZeroes()] = bdd_zero();
     306    mCharacterizationMap[PabloBlock::createOnes()] = bdd_one();
    310307
    311308    // Order the variables so the input Vars are pushed to the end; they ought to
    312309    // be the most complex to resolve.
    313     for (auto i = 0; i != function.getNumOfParameters(); ++i) {
    314         mCharacterizationMap[function.getParameter(i)] = Cudd_bddIthVar(mManager, variableCount++);
    315     }
    316 
    317     return false;
     310    for (mVariables = 0; mVariables != function.getNumOfParameters(); ++mVariables) {
     311        mCharacterizationMap[function.getParameter(mVariables)] = bdd_ithvar(mVariables);
     312    }
     313
     314    return advances;
    318315}
    319316
     
    324321 * Scan through the program and iteratively compute the BDDs for each statement.
    325322 ** ------------------------------------------------------------------------------------------------------------- */
    326 void AutoMultiplexing::characterize(PabloBlock &block) {
     323void AutoMultiplexing::characterize(PabloBlock & block) {
    327324    for (Statement * stmt : block) {
    328325        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    329             const auto start = mRecentCharacterizations.size();
    330326            characterize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody());
    331             assert (mRecentCharacterizations.size() >= start);
    332             if (isa<If>(stmt)) {
    333                 const auto & defined = cast<const If>(stmt)->getDefined();
    334                 for (auto pair = mRecentCharacterizations.begin() + start; pair != mRecentCharacterizations.end(); ++pair) {
    335                     const PabloAST * expr = nullptr;
    336                     DdNode * bdd = nullptr;
    337                     std::tie(expr, bdd) = *pair;
    338                     if (LLVM_UNLIKELY(isa<Assign>(expr))) {
    339                         if (LLVM_LIKELY(std::find(defined.begin(), defined.end(), expr) != defined.end())) {
    340                             continue;
    341                         }
    342                     }
    343                     mCharacterizationMap.erase(mCharacterizationMap.find(expr));
    344                     if (LLVM_UNLIKELY(Cudd_IsConstant(bdd))) {
    345                         continue;
    346                     }
    347                     Deref(bdd);
    348                 }
    349             }
    350             else { // if isa<While>(stmt)
    351                 const auto & variants = cast<const While>(stmt)->getVariants();
    352                 for (auto pair = mRecentCharacterizations.begin() + start; pair != mRecentCharacterizations.end(); ++pair) {
    353                     const PabloAST * expr = nullptr;
    354                     DdNode * bdd = nullptr;
    355                     std::tie(expr, bdd) = *pair;
    356                     if (LLVM_UNLIKELY(isa<Next>(expr))) {
    357                         if (LLVM_LIKELY(std::find(variants.begin(), variants.end(), expr) != variants.end())) {
    358                             DdNode *& next = mCharacterizationMap[expr];
    359                             next = Or(next, bdd);
    360                             Ref(next);
    361                             continue;
    362                         }
    363                     }
    364                     mCharacterizationMap.erase(mCharacterizationMap.find(expr));
    365                     if (LLVM_UNLIKELY(Cudd_IsConstant(bdd))) {
    366                         continue;
    367                     }
    368                     Deref(bdd);
    369                 }
    370             }
    371             mRecentCharacterizations.erase(mRecentCharacterizations.begin() + start, mRecentCharacterizations.end());
    372             continue;
    373         }
    374 
    375         DdNode * var = characterize(stmt);
    376         mCharacterizationMap[stmt] = var;       
     327        } else {
     328            mCharacterizationMap.insert(std::make_pair(stmt, characterize(stmt)));
     329        }
    377330    }
    378331}
     
    381334 * @brief characterize
    382335 ** ------------------------------------------------------------------------------------------------------------- */
    383 inline DdNode * AutoMultiplexing::characterize(Statement * const stmt) {
    384 
    385     DdNode * bdd = nullptr;
     336inline BDD AutoMultiplexing::characterize(Statement * const stmt) {
     337
    386338    // Map our operands to the computed BDDs
    387     std::array<DdNode *, 3> input;
     339    std::array<BDD, 3> input;
    388340    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    389341        PabloAST * const op = stmt->getOperand(i);
     
    402354    }
    403355
     356    BDD bdd = bdd_zero();
    404357    switch (stmt->getClassTypeId()) {
    405358        case TypeId::Assign:
     
    408361            break;
    409362        case TypeId::And:
    410             bdd = And(input[0], input[1]);
    411             break;       
     363            bdd = bdd_and(input[0], input[1]);
     364            break;
    412365        case TypeId::Or:
    413             bdd = Or(input[0], input[1]);
     366            bdd = bdd_or(input[0], input[1]);
    414367            break;
    415368        case TypeId::Xor:
    416             bdd = Xor(input[0], input[1]);
     369            bdd = bdd_xor(input[0], input[1]);
    417370            break;
    418371        case TypeId::Not:
    419             bdd = Not(input[0]);
     372            bdd = bdd_not(input[0]);
    420373            break;
    421374        case TypeId::Sel:
    422             bdd = Ite(input[0], input[1], input[2]);
     375            bdd = bdd_ite(input[0], input[1], input[2]);
    423376            break;
    424377        case TypeId::ScanThru:
    425             // It may be possible use "Not(input[1])" for ScanThrus if we rule out the possibility
    426             // of a contradition being erroneously calculated later. An example of this
    427             // would be ¬(ScanThru(c,m) √ m)
     378            // ScanThru(c, m) := (c + m) ∧ ¬m. We can conservatively represent this statement using the BDD for ¬m --- provided
     379            // no derivative of this statement is negated in any fashion.
    428380        case TypeId::MatchStar:
    429381        case TypeId::Call:
    430             bdd = NewVar();
    431             mRecentCharacterizations.emplace_back(stmt, bdd);
    432             return bdd;
     382            return bdd_ithvar(mVariables++);
    433383        case TypeId::Advance:
    434             // This returns so that it doesn't mistakeningly replace the Advance with 0 or add it
    435             // to the list of recent characterizations.
    436384            return characterize(cast<Advance>(stmt), input[0]);
    437385        default:
    438386            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
    439387    }
    440     Ref(bdd);
    441     mRecentCharacterizations.emplace_back(stmt, bdd);
    442     return bdd;
     388    return bdd_addref(bdd);
    443389}
    444390
     
    446392 * @brief characterize
    447393 ** ------------------------------------------------------------------------------------------------------------- */
    448 inline DdNode * AutoMultiplexing::characterize(Advance *adv, DdNode * input) {
    449     DdNode * Ik, * Ck, * Nk;
    450     if (LLVM_UNLIKELY(isZero(input))) {
    451         Ik = Ck = Nk = Zero();
    452     }
    453     else {
    454 
    455         Ik = input;
    456         Ref(input);
    457         Ck = NewVar();
    458         Nk = Not(Ck);
    459 
    460         assert (mAdvanceMap.count(adv));
    461 
    462         const auto k = mAdvanceMap[adv];
    463 
    464         std::vector<bool> unconstrained(k , false);
    465 
    466         // Can we use a transposed copy of the subset graph to determine an ordering of variables?
    467         for (unsigned i = 0; i != k; ++i) {
    468             // Have we already proven that these are unconstrained by the subset relationships?
    469             if (unconstrained[i]) continue;
    470             Advance * tmp = std::get<0>(mAdvance[i]);
    471             // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
    472             if ((adv->getOperand(1) == tmp->getOperand(1)) && (notTransitivelyDependant(i, k))) {
    473                 DdNode * Ii = std::get<1>(mAdvance[i]);
    474                 DdNode * const IiIk = And(Ik, Ii);
    475                 Ref(IiIk);
    476                 // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    477                 if (NoSatisfyingAssignment(IiIk)) {
    478                     assert (mCharacterizationMap.count(tmp));
    479                     DdNode *& Ci = mCharacterizationMap[tmp];
    480                     // Mark the i-th and k-th Advances as being mutually exclusive
    481                     DdNode * Ni = std::get<2>(mAdvance[i]);
    482                     Ck = And(Ck, Ni); Ref(Ck);
    483                     Ci = And(Ci, Nk); Ref(Ci);
    484                     // If Ai ∩ Ak = âˆ
     394inline BDD AutoMultiplexing::characterize(Advance * const adv, const BDD Ik) {
     395
     396    assert (Ik != bdd_zero());
     397
     398    bdd_addref(Ik);
     399
     400    const auto k = mAdvanceAttributes.size();
     401
     402    std::vector<bool> unconstrained(k , false);
     403
     404    for (unsigned i = 0; i != k; ++i) {
     405        // Have we already proven that these are unconstrained by the subset relationships?
     406        if (unconstrained[i]) continue;
     407
     408        const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
     409        // If these advances are "shifting" their values by the same amount ...
     410        if (adv->getOperand(1) == ithAdv->getOperand(1)) {
     411            BDD Ii = std::get<1>(mAdvanceAttributes[i]);
     412            const BDD IiIk = bdd_and(Ik, Ii);
     413            bdd_addref(IiIk);
     414            // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
     415            if (bdd_satone(IiIk) == bdd_zero()) {
     416                // If Ai ∩ Ak = âˆ
    485417 and Aj ⊂ Ai, Aj ∩ Ak = âˆ
    486418.
    487                     graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
    488                     for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    489                         const auto j = source(*ei, mSubsetGraph);
    490                         if (notTransitivelyDependant(k, j)) {
    491                             Advance * adv = std::get<0>(mAdvance[j]);
    492                             assert (mCharacterizationMap.count(adv));
    493                             DdNode *& Cj = mCharacterizationMap[adv];
    494                             DdNode * Nj = std::get<2>(mAdvance[j]);
    495                             // Mark the i-th and j-th Advances as being mutually exclusive
    496                             Ck = And(Ck, Nj); Ref(Ck);
    497                             Cj = And(Cj, Nk); Ref(Cj);
    498                             unconstrained[j] = true;
    499                         }
    500                     }
    501                     unconstrained[i] = true;
    502                 }
    503                 else if (Ik == IiIk) {
    504                     // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k,i).
    505                     // These edges will be moved into the multiplex set graph if Ai and Ak happen to be
    506                     // in the same mutually exclusive set.
    507                     add_edge(k, i, mSubsetGraph);
    508                     // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
    509                     graph_traits<SubsetGraph>::out_edge_iterator ei, ei_end;
    510                     for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    511                         const auto j = target(*ei, mSubsetGraph);
    512                         add_edge(k, j, mSubsetGraph);
    513                         unconstrained[j] = true;
    514                     }
    515                     unconstrained[i] = true;
    516                 }
    517                 else if (Ii == IiIk) {
    518                     // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i,k).
    519                     add_edge(i, k, mSubsetGraph);
    520                     // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
    521                     graph_traits<SubsetGraph>::in_edge_iterator ei, ei_end;
    522                     for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    523                         const auto j = source(*ei, mSubsetGraph);
    524                         add_edge(j, k, mSubsetGraph);
    525                         unconstrained[j] = true;
    526                     }
    527                     unconstrained[i] = true;
    528                 }
    529                 Deref(IiIk);
    530             }
    531         }
    532 
    533         for (unsigned i = 0; i != k; ++i) {
    534             const Advance * const tmp = std::get<0>(mAdvance[i]);
    535             // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
    536             if (!unconstrained[i] || (adv->getParent() != tmp->getParent())) {
    537                 // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
    538                 // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
    539                 add_edge(i, k, mConstraintGraph);
    540             }
    541         }
    542     }
    543 
    544     mAdvance.emplace_back(adv, Ik, Nk);
     419                for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
     420                     unconstrained[source(e, mSubsetGraph)] = true;
     421                }
     422                unconstrained[i] = true;
     423            } else if (Ik == IiIk) {
     424                // If Ik = Ii ∩ Ik then Ik ⊂ Ii. Record this in the subset graph with the arc (k, i).
     425                // The AST will be modified to make these mutually exclusive if Ai and Ak end up in
     426                // the same multiplexing set.
     427                add_edge(k, i, mSubsetGraph);
     428                // If Ak ⊂ Ai and Ai ⊂ Aj, Ak ⊂ Aj.
     429                for (auto e : make_iterator_range(out_edges(i, mSubsetGraph))) {
     430                    const auto j = target(e, mSubsetGraph);
     431                    add_edge(k, j, mSubsetGraph);
     432                    unconstrained[j] = true;
     433                }
     434                unconstrained[i] = true;
     435            } else if (Ii == IiIk) {
     436                // If Ii = Ii ∩ Ik then Ii ⊂ Ik. Record this in the subset graph with the arc (i, k).
     437                add_edge(i, k, mSubsetGraph);
     438                // If Ai ⊂ Ak and Aj ⊂ Ai, Aj ⊂ Ak.
     439                for (auto e : make_iterator_range(in_edges(i, mSubsetGraph))) {
     440                    const auto j = source(e, mSubsetGraph);
     441                    add_edge(j, k, mSubsetGraph);
     442                    unconstrained[j] = true;
     443                }
     444                unconstrained[i] = true;
     445            }
     446            bdd_delref(IiIk);
     447        }
     448    }
     449
     450    const BDD Vk = bdd_ithvar(mVariables++);
     451
     452    BDD Ck = Vk;
     453
     454    for (unsigned i = 0; i != k; ++i) {
     455        const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
     456        auto f = mCharacterizationMap.find(ithAdv);
     457        assert (f != mCharacterizationMap.end());
     458        BDD & Ci = f->second;
     459        const BDD Vi = std::get<2>(mAdvanceAttributes[i]);
     460        if (unconstrained[i]) {
     461            Ck = bdd_and(Ck, bdd_not(Vi));
     462            bdd_addref(Ck);
     463            Ci = bdd_and(Ci, bdd_not(Vk));
     464            bdd_addref(Ci);
     465            // If these Advances are mutually exclusive, in the same scope, and transitively independent,
     466            // we safely multiplex them.
     467            if ((adv->getParent() == ithAdv->getParent()) && independent(i, k)) {
     468                continue;
     469            }
     470        } else { // TODO: investigate how to determine when it's safe to avoid computing these
     471            Ck = bdd_imp(Ck, Vi);
     472            bdd_addref(Ck);
     473            Ci = bdd_imp(Ci, Vk);
     474            bdd_addref(Ci);
     475        }
     476        add_edge(i, k, mConstraintGraph);
     477    }
     478
     479    mAdvanceAttributes.emplace_back(adv, Ik, Vk);
     480
    545481    return Ck;
    546482}
    547483
    548484/** ------------------------------------------------------------------------------------------------------------- *
    549  * @brief notTransitivelyDependant
    550  ** ------------------------------------------------------------------------------------------------------------- */
    551 inline bool AutoMultiplexing::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const {
     485 * @brief independent
     486 ** ------------------------------------------------------------------------------------------------------------- */
     487inline bool AutoMultiplexing::independent(const ConstraintVertex i, const ConstraintVertex j) const {
    552488    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
    553489    return (mConstraintGraph.get_edge(i, j) == 0);
    554 }
    555 
    556 /** ------------------------------------------------------------------------------------------------------------- *
    557  * @brief CUDD wrappers
    558  ** ------------------------------------------------------------------------------------------------------------- */
    559 
    560 inline DdNode * AutoMultiplexing::Zero() const {
    561     return Cudd_ReadLogicZero(mManager);
    562 }
    563 
    564 inline DdNode * AutoMultiplexing::One() const {
    565     return Cudd_ReadOne(mManager);
    566 }
    567 
    568 inline DdNode * AutoMultiplexing::NewVar() {
    569     DdNode * var = Cudd_bddIthVar(mManager, mVariables++);
    570     return var;
    571 }
    572 
    573 inline bool AutoMultiplexing::isZero(DdNode * const x) const {
    574     return x == Zero();
    575 }
    576 
    577 inline DdNode * AutoMultiplexing::And(DdNode * const x, DdNode * const y) {
    578     return Cudd_bddAnd(mManager, x, y);
    579 }
    580 
    581 inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) {
    582     return Cudd_bddOr(mManager, x, y);
    583 }
    584 
    585 inline DdNode * AutoMultiplexing::Xor(DdNode * const x, DdNode * const y) {
    586     return Cudd_bddXor(mManager, x, y);
    587 }
    588 
    589 inline DdNode * AutoMultiplexing::Not(DdNode * const x) const {
    590     return Cudd_Not(x);
    591 }
    592 
    593 inline DdNode * AutoMultiplexing::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
    594     return Cudd_bddIte(mManager, x, y, z);
    595 }
    596 
    597 inline bool AutoMultiplexing::NoSatisfyingAssignment(DdNode * const x) {
    598     return Cudd_bddLeq(mManager, x, Zero());
    599 }
    600 
    601 inline void AutoMultiplexing::Ref(DdNode * const x) {
    602     assert (x);
    603     Cudd_Ref(x);
    604 }
    605 
    606 inline void AutoMultiplexing::Deref(DdNode * const x) {
    607     assert (x);
    608     Cudd_RecursiveDeref(mManager, x);
    609 }
    610 
    611 inline void AutoMultiplexing::Shutdown() {
    612 //    #ifdef PRINT_DEBUG_OUTPUT
    613 //    Cudd_PrintInfo(mManager, stderr);
    614 //    #endif
    615     Cudd_Quit(mManager);
    616490}
    617491
     
    870744void AutoMultiplexing::applySubsetConstraints() {
    871745
    872     // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
    873     // relationships of our independent sets.
    874     const unsigned m = num_vertices(mConstraintGraph);
    875     const unsigned n = num_vertices(mMultiplexSetGraph);
    876 
    877     // Add in any edges from our subset constraints to M that are within the same set.
    878     bool hasSubsetConstraint = false;
    879 
    880     for (auto ei : make_iterator_range(edges(mSubsetGraph))) {
    881         const auto u = source(ei, mSubsetGraph);
    882         const auto v = target(ei, mSubsetGraph);
    883         // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
    884         // "set vertex". Add the edge between the vertices.
    885         for (auto ej : make_iterator_range(in_edges(u, mMultiplexSetGraph))) {
    886             auto w = target(ej, mMultiplexSetGraph);
    887             // Only check (v, w) if w is a "set vertex".
    888             if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
    889                 add_edge(u, v, mMultiplexSetGraph);
    890                 hasSubsetConstraint = true;
    891             }
    892         }
    893     }
    894 
    895     if (LLVM_UNLIKELY(hasSubsetConstraint)) {
    896         // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
    897         // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
    898         // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
    899 
    900         std::vector<MultiplexSetGraph::vertex_descriptor> V;
    901         std::stack<MultiplexSetGraph::vertex_descriptor> S;
    902         std::queue<PabloAST *> Q;
    903         BitVector D(n - m, 0);
    904 
    905         for (auto i = m; i != n; ++i) {
    906             // For each member of a "set vertex" ...
    907             for (auto e : make_iterator_range(out_edges(i, mMultiplexSetGraph))) {
    908                 const auto s = source(e, mMultiplexSetGraph);
    909                 if (out_degree(s, mMultiplexSetGraph) != 0) {
    910                     // First scan through the subgraph of vertices in M dominated by s and build up the set T,
    911                     // consisting of all sinks w.r.t. vertex s.
    912                     auto u = s;
    913                     for (;;) {
    914                         graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
    915                         for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
    916                             auto v = target(*ej, mMultiplexSetGraph);
    917                             if (D.test(v)) {
    918                                 continue;
    919                             }
    920                             D.set(v);
    921                             if (out_degree(v, mMultiplexSetGraph) == 0) {
    922                                 V.push_back(v);
    923                             }
    924                             else {
    925                                 S.push(v);
    926                             }
    927                         }
    928                         if (S.empty()) {
    929                             break;
    930                         }
    931                         u = S.top();
    932                         S.pop();
    933                     }
    934                     D.clear();
    935                     // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
    936                     // with the complement of each advance indicated by V.
    937 
    938                     Advance * adv = std::get<0>(mAdvance[s]);
    939                     PabloBlock * pb = adv->getParent();
    940 
    941                     for (auto i : V) {
    942                         Q.push(std::get<0>(mAdvance[i])->getOperand(0));
    943                     }                   
    944                     pb->setInsertPoint(adv);
    945                     while (Q.size() > 1) {
    946                         PabloAST * a1 = Q.front(); Q.pop();
    947                         PabloAST * a2 = Q.front(); Q.pop();                       
    948                         Q.push(pb->createOr(a1, a2, "subset"));
    949                     }
    950                     assert (Q.size() == 1);
    951 
    952                     PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
    953                     adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset"));
    954 
    955                     // Similar to the above, we're going to OR together the result of each advance,
    956                     // including s. This will restore the advanced variable back to its original state.
    957 
    958                     // Gather the original users to this advance. We'll be manipulating it shortly.
    959                     std::vector<PabloAST *> U(adv->users().begin(), adv->users().end());
    960 
    961                     // Add s to V and sort the list; it'll be closer to being in topological order.
    962                     V.push_back(s);
    963                     std::sort(V.begin(), V.end());
    964                     for (auto i : V) {
    965                         Q.push(std::get<0>(mAdvance[i]));
    966                     }
    967                     pb->setInsertPoint(adv);
    968                     while (Q.size() > 1) {
    969                         PabloAST * a1 = Q.front(); Q.pop();
    970                         PabloAST * a2 = Q.front(); Q.pop();                       
    971                         Q.push(pb->createOr(a1, a2, "subset"));
    972                     }
    973                     assert (Q.size() == 1);
    974 
    975                     PabloAST * const input = Q.front(); Q.pop();
    976                     for (PabloAST * use : U) {
    977                         if (LLVM_LIKELY(isa<Statement>(use))) {
    978                             cast<Statement>(use)->replaceUsesOfWith(adv, input);
    979                         }
    980                     }
    981 
    982                     pb->setInsertPoint(pb->back());
    983 
    984                     V.clear();
    985 
    986                 }
    987             }
    988         }
     746    using SubsetEdgeIterator = graph_traits<SubsetGraph>::edge_iterator;
     747
     748    // If Ai ⊂ Aj then the subset graph will contain the arc (i, j). Remove all arcs corresponding to vertices
     749    // that are not elements of the same multiplexing set.
     750    SubsetEdgeIterator ei, ei_end, ei_next;
     751    std::tie(ei, ei_end) = edges(mSubsetGraph);
     752    for (ei_next = ei; ei != ei_end; ei = ei_next) {
     753        ++ei_next;
     754        const auto u = source(*ei, mSubsetGraph);
     755        const auto v = target(*ei, mSubsetGraph);
     756        if (in_degree(u, mMultiplexSetGraph) != 0 && in_degree(v, mMultiplexSetGraph) != 0) {
     757            const auto su = source(*(in_edges(u, mMultiplexSetGraph).first), mMultiplexSetGraph);
     758            const auto sv = source(*(in_edges(v, mMultiplexSetGraph).first), mMultiplexSetGraph);
     759            if (su == sv) {
     760                continue;
     761            }
     762        }
     763        remove_edge(*ei, mSubsetGraph);
     764    }
     765
     766    if (num_edges(mSubsetGraph) != 0) {
     767
     768        // At least one subset constraint exists; perform a transitive reduction on the graph to ensure that
     769        // we perform the minimum number of AST modifications for the given multiplexing sets.
     770
     771        transitiveReductionOfSubsetGraph();
     772
     773        // Afterwards modify the AST to ensure that multiplexing algorithm can ignore any subset constraints
     774        for (auto e : make_iterator_range(edges(mSubsetGraph))) {
     775            Advance * adv1 = std::get<0>(mAdvanceAttributes[source(e, mSubsetGraph)]);
     776            Advance * adv2 = std::get<0>(mAdvanceAttributes[target(e, mSubsetGraph)]);
     777            assert (adv1->getParent() == adv2->getParent());
     778            PabloBlock * const pb = adv1->getParent();
     779            pb->setInsertPoint(adv2->getPrevNode());
     780            adv2->setOperand(0, pb->createAnd(adv2->getOperand(0), pb->createNot(adv1->getOperand(0)), "subset"));
     781            pb->setInsertPoint(adv2);
     782            adv2->replaceAllUsesWith(pb->createOr(adv1, adv2, "merge"));
     783        }
     784
    989785    }
    990786}
     
    1005801
    1006802    circular_buffer<PabloAST *> Q(max_n);
    1007     flat_set<PabloBlock *> modified;
    1008803
    1009804    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
     
    1019814            unsigned i = 0;
    1020815            for (const auto e : make_iterator_range(out_edges(idx, mMultiplexSetGraph))) {
    1021                 input[i] = std::get<0>(mAdvance[target(e, mMultiplexSetGraph)]);
    1022                 assert (input[i]);
    1023                 ++i;
    1024             }
    1025             assert (i == n);
     816                input[i++] = std::get<0>(mAdvanceAttributes[target(e, mMultiplexSetGraph)]);
     817            }
    1026818
    1027819            Advance * const adv = input[0];
    1028             assert (adv);
    1029             PabloBlock * const block = adv->getParent();
    1030             assert (block);           
     820            PabloBlock * const block = adv->getParent(); assert (block);
    1031821            PabloBuilder builder(*block);
    1032822            block->setInsertPoint(block->back());
     
    1038828                prefix << "mux" << n << "to" << m << '.' << (j + 1);
    1039829                for (size_t i = 0; i != n; ++i) {
    1040                     if (((i + 1) & (1ULL << j)) != 0) {
     830                    if (((i + 1) & (1UL << j)) != 0) {
    1041831                        assert (input[i]->getParent() == block);
    1042832                        Q.push_back(input[i]->getOperand(0));
     
    1062852                // Construct the demuxed values and replaces all the users of the original advances with them.
    1063853                for (size_t j = 0; j != m; ++j) {
    1064                     if (((i + 1) & (1ULL << j)) == 0) {
     854                    if (((i + 1) & (1UL << j)) == 0) {
    1065855                        Q.push_back(muxed[j]);
    1066856                    }
     
    1075865                    }
    1076866                    assert (Q.size() == 1);
    1077                     PabloAST * neg = Q.front(); Q.pop_front();
    1078                     Q.push_back(builder.createNot(neg, "demuxing")); assert (neg);
     867                    PabloAST * neg = Q.front(); Q.pop_front(); assert (neg);
     868                    Q.push_back(builder.createNot(neg, "demuxing"));
    1079869                }
    1080870
     
    1096886                input[i]->replaceWith(demuxed, true, true);
    1097887            }
    1098             modified.insert(block);
    1099         }
    1100     }
     888        }
     889    }
     890}
     891
     892/** ------------------------------------------------------------------------------------------------------------- *
     893 * @brief topologicalSort
     894 *
     895 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
     896 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
     897 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
     898 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
     899 * it's not necessarily the original ordering.
     900 ** ------------------------------------------------------------------------------------------------------------- */
     901void AutoMultiplexing::topologicalSort(PabloFunction & function) {
     902    // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
     903    std::unordered_set<const PabloAST *> encountered;
     904    std::stack<Statement *> scope;
     905    for (Statement * stmt = function.getEntryBlock().front(); ; ) { restart:
     906        while ( stmt ) {
     907            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     908                PabloAST * const op = stmt->getOperand(i);
     909                if (LLVM_LIKELY(isa<Statement>(op))) {
     910                    if (LLVM_UNLIKELY(encountered.count(op) == 0)) {
     911                        if (LLVM_UNLIKELY(isa<While>(stmt) && isa<Next>(op))) {
     912                            if (encountered.count(cast<Next>(op)->getInitial()) != 0) {
     913                                continue;
     914                            }
     915                        }
     916                        Statement * const next = stmt->getNextNode();
     917                        stmt->insertAfter(cast<Statement>(op));
     918                        stmt = next;
     919                        goto restart;
     920                    }
     921                }
     922            }
     923            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     924                // Set the next statement to be the first statement of the inner scope and push the
     925                // next statement of the current statement into the scope stack.
     926                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     927                scope.push(stmt->getNextNode());
     928                stmt = nested.front();
     929                continue;
     930            }
     931            encountered.insert(stmt);
     932            stmt = stmt->getNextNode();
     933        }
     934        if (scope.empty()) {
     935            break;
     936        }
     937        stmt = scope.top();
     938        scope.pop();
     939    }
     940}
     941
     942/** ------------------------------------------------------------------------------------------------------------- *
     943 * @brief transitiveReductionOfSubsetGraph
     944 ** ------------------------------------------------------------------------------------------------------------- */
     945void AutoMultiplexing::transitiveReductionOfSubsetGraph() {
     946    std::vector<SubsetGraph::vertex_descriptor> Q;
     947    for (auto u : make_iterator_range(vertices(mSubsetGraph))) {
     948        if (in_degree(u, mSubsetGraph) == 0 && out_degree(u, mSubsetGraph) != 0) {
     949            Q.push_back(u);
     950        }
     951    }
     952    flat_set<SubsetGraph::vertex_descriptor> targets;
     953    flat_set<SubsetGraph::vertex_descriptor> visited;
     954    do {
     955        const auto u = Q.back(); Q.pop_back();
     956        for (auto ei : make_iterator_range(out_edges(u, mSubsetGraph))) {
     957            for (auto ej : make_iterator_range(out_edges(target(ei, mSubsetGraph), mSubsetGraph))) {
     958                targets.insert(target(ej, mSubsetGraph));
     959            }
     960        }
     961        for (auto v : targets) {
     962            remove_edge(u, v, mSubsetGraph);
     963        }
     964        for (auto e : make_iterator_range(out_edges(u, mSubsetGraph))) {
     965            const auto v = target(e, mSubsetGraph);
     966            if (visited.insert(v).second) {
     967                Q.push_back(v);
     968            }
     969        }
     970    } while (Q.size() > 0);
    1101971}
    1102972
    1103973} // end of namespace pablo
    1104 
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4860 r4868  
    1313#include <llvm/ADT/DenseMap.h>
    1414
    15 struct DdManager; // forward declare of the CUDD manager
    16 struct DdNode;
     15typedef int BDD;
    1716
    1817namespace pablo {
     
    2322class AutoMultiplexing {
    2423
    25     using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
     24    using CharacterizationMap = llvm::DenseMap<const PabloAST *, BDD>;
    2625    using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
    2726    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
     
    3029    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    3130    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    32     // the Advance pointer, input BDD and the BDD variable of the i-th Advance
    33     using AdvanceMap = boost::container::flat_map<const Statement *, unsigned>;
    34     using AdvanceVector = std::vector<std::tuple<Advance *, DdNode *, DdNode *>>;
     31    using AdvanceAttributes = std::vector<std::tuple<Advance *, BDD, BDD>>; // the Advance pointer, input BDD, the base BDD variable
    3532    using VertexVector = std::vector<ConstraintVertex>;
    36     using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;
    3733    using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
    38     using TopologicalGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, Statement *>;
    39     using TopologicalVertex = TopologicalGraph::vertex_descriptor;
    40     using TopologicalMap = boost::container::flat_map<const Statement *, TopologicalVertex>;
     34
    4135public:
    4236    static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100);
    4337protected:
    44     bool initialize(PabloFunction & function);
     38    unsigned initialize(PabloFunction & function);
    4539    void characterize(PabloBlock & block);
    46     DdNode * characterize(Statement * const stmt);
    47     DdNode * characterize(Advance * adv, DdNode * input);
    48     bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
     40    BDD characterize(Statement * const stmt);
     41    BDD characterize(Advance * const adv, const BDD Ik);
     42    bool independent(const ConstraintVertex i, const ConstraintVertex j) const;
    4943    bool generateCandidateSets(RNG & rng);
    5044    void addCandidateSet(const VertexVector & S, RNG & rng);
    5145    void selectMultiplexSets(RNG &);
     46    void transitiveReductionOfSubsetGraph() ;
    5247    void applySubsetConstraints();
    5348    void multiplexSelectedIndependentSets(PabloFunction & function);
     49    static void topologicalSort(PabloFunction & function);
    5450
    5551    inline AutoMultiplexing(const unsigned limit, const unsigned maxSelections)
     
    6258
    6359private:
    64 
    65     DdNode * Zero() const;
    66     DdNode * One() const;
    67     bool isZero(DdNode * const x) const;
    68     DdNode * And(DdNode * const x, DdNode * const y);
    69     DdNode * Or(DdNode * const x, DdNode * const y);
    70     DdNode * Xor(DdNode * const x, DdNode * const y);
    71     DdNode * Not(DdNode * x) const;
    72     DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
    73     DdNode * NewVar();
    74     void Ref(DdNode * const x);
    75     void Deref(DdNode * const x);
    76     bool NoSatisfyingAssignment(DdNode * const x);
    77     void Shutdown();
    78 
    79 private:
    80     DdManager *                 mManager;
    81     const unsigned              mLimit;
     60    unsigned                    mLimit;
    8261    const unsigned              mMaxSelections;
    8362    unsigned                    mVariables;
     
    8564    ConstraintGraph             mConstraintGraph;
    8665    SubsetGraph                 mSubsetGraph;
    87     AdvanceMap                  mAdvanceMap;
    88     AdvanceVector               mAdvance;
     66    AdvanceAttributes           mAdvanceAttributes;
    8967    MultiplexSetGraph           mMultiplexSetGraph;
    90     RecentCharacterizations     mRecentCharacterizations;
    9168    ScopeMap                    mResolvedScopes;
    9269};
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4804 r4868  
    33#include <pablo/builder.hpp>
    44#include <pablo/printer_pablos.h>
    5 #include <cudd.h>
    6 #include <util.h>
    75#include <pablo/optimizers/pablo_simplifier.hpp>
    86#include <pablo/analysis/pabloverifier.hpp>
    97#include <stack>
     8#include <bdd.h>
    109
    1110using namespace llvm;
     
    1615
    1716using TypeId = PabloAST::ClassTypeId;
     17
     18// TODO: add in analysis to verify that the outputs of an If would be zero if the If cond is false?
     19
     20// TODO: test whether an If node can be moved into another If body in the same scope?
    1821
    1922bool BDDMinimizationPass::optimize(PabloFunction & function) {
     
    2124    am.initialize(function);
    2225    am.eliminateLogicallyEquivalentStatements(function);
    23     am.shutdown();
     26    bdd_done();
    2427    #ifndef NDEBUG
    2528    PabloVerifier::verify(function, "post-bdd-minimization");
     
    3740
    3841    std::stack<Statement *> scope;
    39     unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
    40 
     42    unsigned variableCount = function.getNumOfParameters(); // number of statements that cannot always be categorized without generating a new variable
     43    unsigned statementCount = 0;
    4144    for (const Statement * stmt = function.getEntryBlock().front(); ; ) {
    4245        while ( stmt ) {
     
    5053                continue;
    5154            }
     55            ++statementCount;
    5256            switch (stmt->getClassTypeId()) {
    5357                case TypeId::Advance:
     
    6973
    7074    // Initialize the BDD engine ...
    71     mManager = Cudd_Init(variableCount + function.getNumOfParameters() - function.getNumOfResults(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    72     mVariables = 0;
    73     Cudd_MakeTreeNode(mManager, 0, function.getNumOfParameters(), MTR_DEFAULT);
     75    bdd_init(1000000, 10000);
     76    bdd_setvarnum(variableCount + function.getNumOfParameters());
     77    bdd_setcacheratio(32);
     78    bdd_setmaxincrease(1000000);
     79    bdd_disable_reorder();
     80
    7481    // Map the predefined 0/1 entries
    75     mCharacterizationMap[PabloBlock::createZeroes()] = Zero();
    76     mCharacterizationMap[PabloBlock::createOnes()] = One();
     82    mCharacterizationMap[PabloBlock::createZeroes()] = bdd_zero();
     83    mCharacterizationMap[PabloBlock::createOnes()] = bdd_one();
    7784    // Order the variables so the input Vars are pushed to the end; they ought to
    7885    // be the most complex to resolve.   
    79     for (auto i = 0; i != function.getNumOfParameters(); ++i) {
    80         mCharacterizationMap[function.getParameter(i)] = NewVar(function.getParameter(i));
    81     }
    82     Cudd_SetSiftMaxVar(mManager, 1000000);
    83     Cudd_SetSiftMaxSwap(mManager, 1000000000);
    84     Cudd_AutodynEnable(mManager, CUDD_REORDER_LAZY_SIFT);
     86    for (mVariables = 0; mVariables != function.getNumOfParameters(); ++mVariables) {
     87        mCharacterizationMap[function.getParameter(mVariables)] = bdd_ithvar(mVariables);
     88    }
    8589}
    8690
     
    9094void BDDMinimizationPass::eliminateLogicallyEquivalentStatements(PabloFunction & function) {
    9195    SubsitutionMap baseMap;
    92     baseMap.insert(Zero(), function.getEntryBlock().createZeroes());
    93     baseMap.insert(One(), function.getEntryBlock().createOnes());
     96    baseMap.insert(bdd_zero(), function.getEntryBlock().createZeroes());
     97    baseMap.insert(bdd_one(), function.getEntryBlock().createOnes());
    9498    eliminateLogicallyEquivalentStatements(function.getEntryBlock(), baseMap);
    9599}
     
    108112            for (Next * var : cast<const While>(stmt)->getVariants()) {
    109113                if (!escapes(var)) {
    110                     Cudd_RecursiveDeref(mManager, mCharacterizationMap[var]);
     114                    bdd_delref(mCharacterizationMap[var]);
    111115                    mCharacterizationMap.erase(var);
    112116                }
     
    121125            /// cost of each scope is close enough w.r.t. the probability both branches are taken.
    122126
    123             DdNode * bdd = nullptr;
     127            BDD bdd = bdd_zero();
    124128            bool test = false;
    125129            std::tie(bdd, test) = characterize(stmt);
     
    127131                PabloAST * replacement = map.get(bdd);
    128132                if (LLVM_UNLIKELY(replacement != nullptr)) {
    129                     Cudd_RecursiveDeref(mManager, bdd);
     133                    bdd_delref(bdd);
    130134                    stmt = stmt->replaceWith(replacement, false, true);
    131135                    continue;
    132136                }
    133             } else if (LLVM_LIKELY(nonConstant(bdd))) {
     137            } else if (LLVM_LIKELY(!bdd_constant(bdd))) {
    134138                map.insert(bdd, stmt);
    135139            }
     
    143147 * @brief characterize
    144148 ** ------------------------------------------------------------------------------------------------------------- */
    145 inline std::pair<DdNode *, bool> BDDMinimizationPass::characterize(Statement * const stmt) {
    146 
    147     DdNode * bdd = nullptr;
     149inline std::pair<BDD, bool> BDDMinimizationPass::characterize(Statement * const stmt) {
     150
     151    BDD bdd = bdd_zero();
    148152    // Map our operands to the computed BDDs
    149     std::array<DdNode *, 3> input;
     153    std::array<BDD, 3> input;
    150154    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    151155        PabloAST * const op = stmt->getOperand(i);
     
    172176            return std::make_pair(input[0], false);
    173177        case TypeId::And:
    174             bdd = And(input[0], input[1]);
     178            bdd = bdd_and(input[0], input[1]);
    175179            break;
    176180        case TypeId::Or:
    177             bdd = Or(input[0], input[1]);
     181            bdd = bdd_or(input[0], input[1]);
    178182            break;
    179183        case TypeId::Xor:
    180             bdd = Xor(input[0], input[1]);
     184            bdd = bdd_xor(input[0], input[1]);
    181185            break;
    182186        case TypeId::Not:
    183             bdd = Not(input[0]);
     187            bdd = bdd_not(input[0]);
    184188            break;
    185189        case TypeId::Sel:
    186             bdd = Ite(input[0], input[1], input[2]);
     190            bdd = bdd_ite(input[0], input[1], input[2]);
    187191            break;
    188192        case TypeId::MatchStar:
    189193        case TypeId::ScanThru:
    190             if (LLVM_UNLIKELY(input[1] == Zero())) {
    191                 return std::make_pair(Zero(), true);
     194            if (LLVM_UNLIKELY(input[1] == bdd_zero())) {
     195                bdd = input[0];
    192196            }
    193197        case TypeId::Advance:
    194             if (LLVM_UNLIKELY(input[0] == Zero())) {
    195                 return std::make_pair(Zero(), true);
     198            if (LLVM_UNLIKELY(input[0] == bdd_zero())) {
     199                return std::make_pair(bdd_zero(), true);
    196200            }
    197201        case TypeId::Call:
    198202            // TODO: we may have more than one output. Need to fix call class to allow for it.
    199             return std::make_pair(NewVar(stmt), false);
     203            return std::make_pair(bdd_ithvar(mVariables++), false);
    200204        default:
    201205            throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
    202206    }
    203     Cudd_Ref(bdd);
    204     if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
    205         Cudd_RecursiveDeref(mManager, bdd);
    206         bdd = Zero();
     207    bdd_addref(bdd);
     208    if (LLVM_UNLIKELY(bdd_satone(bdd) == bdd_zero())) {
     209        bdd_delref(bdd);
     210        bdd = bdd_zero();
    207211    }
    208212    return std::make_pair(bdd, true);
    209213}
    210214
    211 /** ------------------------------------------------------------------------------------------------------------- *
    212  * @brief CUDD wrappers
    213  ** ------------------------------------------------------------------------------------------------------------- */
    214 
    215 inline DdNode * BDDMinimizationPass::Zero() const {
    216     return Cudd_ReadLogicZero(mManager);
    217 }
    218 
    219 inline DdNode * BDDMinimizationPass::One() const {
    220     return Cudd_ReadOne(mManager);
    221 }
    222 
    223 inline DdNode * BDDMinimizationPass::NewVar(const PabloAST *) {
    224     return Cudd_bddIthVar(mManager, mVariables++);
    225 }
    226 
    227 inline bool BDDMinimizationPass::nonConstant(DdNode * const x) const {
    228     return x != Zero() && x != One();
    229 }
    230 
    231 inline DdNode * BDDMinimizationPass::And(DdNode * const x, DdNode * const y) {
    232     return Cudd_bddAnd(mManager, x, y);
    233 }
    234 
    235 inline DdNode * BDDMinimizationPass::Or(DdNode * const x, DdNode * const y) {
    236     return Cudd_bddOr(mManager, x, y);
    237 }
    238 
    239 inline DdNode * BDDMinimizationPass::Xor(DdNode * const x, DdNode * const y) {
    240     return Cudd_bddXor(mManager, x, y);
    241 }
    242 
    243 inline DdNode * BDDMinimizationPass::Not(DdNode * const x) const {
    244     return Cudd_Not(x);
    245 }
    246 
    247 inline DdNode * BDDMinimizationPass::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
    248     return Cudd_bddIte(mManager, x, y, z);
    249 }
    250 
    251 inline bool BDDMinimizationPass::noSatisfyingAssignment(DdNode * const x) {
    252     return Cudd_bddLeq(mManager, x, Zero());
    253 }
    254 
    255 inline void BDDMinimizationPass::shutdown() {
    256     Cudd_Quit(mManager);
    257     mCharacterizationMap.clear();
    258 }
    259 
    260215} // end of namespace pablo
    261216
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.h

    r4804 r4868  
    55#include <vector>
    66
    7 struct DdManager; // forward declare of the CUDD manager
    8 struct DdNode;
     7typedef int BDD;
    98
    109namespace pablo {
     
    1312class PabloBlock;
    1413class PabloFunction;
    15 class PabloBuilder;
    1614class Statement;
    1715
    1816class BDDMinimizationPass {
    1917
    20     using CharacterizationMap = boost::container::flat_map<const PabloAST *, DdNode *>;
    21     using Terminals = std::vector<Statement *>;
     18    using CharacterizationMap = boost::container::flat_map<const PabloAST *, BDD>;
    2219
    2320    struct SubsitutionMap {
    2421        SubsitutionMap(SubsitutionMap * parent = nullptr) : mParent(parent) {}
    2522
    26         PabloAST * get(const DdNode * node) const {
     23        PabloAST * get(const BDD node) const {
    2724            auto f = mMap.find(node);
    2825            if (f == mMap.end()) {
     
    3229        }
    3330
    34         void insert(const DdNode * node, PabloAST * stmt) {
     31        void insert(const BDD node, PabloAST * stmt) {
    3532            mMap.emplace(node, stmt);
    3633        }
    3734    private:
    3835        const SubsitutionMap * const mParent;
    39         boost::container::flat_map<const DdNode *, PabloAST *> mMap;
     36        boost::container::flat_map<BDD, PabloAST *> mMap;
    4037    };
    4138
     
    4744    void eliminateLogicallyEquivalentStatements(PabloBlock & block, SubsitutionMap & parent);
    4845    void eliminateLogicallyEquivalentStatements(Statement * const stmt, SubsitutionMap & map);
    49     std::pair<DdNode *, bool> characterize(Statement * const stmt);
     46    std::pair<BDD, bool> characterize(Statement * const stmt);
    5047private:
    51     DdNode * Zero() const;
    52     DdNode * One() const;
    53     bool nonConstant(DdNode * const x) const;
    54     DdNode * And(DdNode * const x, DdNode * const y);
    55     DdNode * Intersect(DdNode * const x, DdNode * const y);
    56     DdNode * Or(DdNode * const x, DdNode * const y);
    57     DdNode * Xor(DdNode * const x, DdNode * const y);
    58     DdNode * Not(DdNode * x) const;
    59     DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
    60     DdNode * NewVar(const PabloAST *);
    61     bool noSatisfyingAssignment(DdNode * const x);
    62     void shutdown();
    63 private:
    64     DdManager *                     mManager;
    6548    unsigned                        mVariables;
    6649    CharacterizationMap             mCharacterizationMap;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4866 r4868  
    216216}
    217217
    218 
    219218/** ------------------------------------------------------------------------------------------------------------- *
    220219 * @brief eliminateRedundantCode
    221220 *
    222  * Note: Do not recursively erase statements in this function. The ExpressionTable could use deleted statements
    223  * as replacements. Let the DCE remove the unnecessary statements with the final Use-Def information.
     221 * Note: Do not recursively delete statements in this function. The ExpressionTable could use deleted statements
     222 * as replacements. Let the DCE remove the unnecessary statements with the finalized Def-Use information.
    224223 ** ------------------------------------------------------------------------------------------------------------- */
    225224void Simplifier::eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor) {
     
    233232            // the Assign's expression directly.
    234233            if (isSuperfluous(assign)) {
    235                 stmt = assign->replaceWith(assign->getExpression(), true);
     234                stmt = assign->replaceWith(assign->getExpression());
    236235                continue;
    237236            }
     
    247246            }
    248247
    249             bool evaluate = true;
     248            // Test whether all of the defined variables are necessary
    250249            If::DefinedVars & defs = ifNode->getDefined();
    251             while (evaluate) {
    252                 evaluate = false;
    253                 // Process the If body
    254                 eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
    255                 // Now test whether all of the defined variables are necessary
    256                 for (auto itr = defs.begin(); itr != defs.end(); ) {
    257                     Assign * def = *itr;
    258                     if (LLVM_UNLIKELY(demoteDefinedVar(ifNode, def))) {
    259                         itr = defs.erase(itr);
    260                         def->replaceWith(def->getExpression());
    261                         evaluate = true;
    262                         continue;
    263                     }
    264                     ++itr;
    265                 }
    266             }
     250            for (auto def = defs.begin(); def != defs.end(); ) {
     251                if (LLVM_UNLIKELY(demoteDefinedVar(ifNode, *def))) {
     252                    (*def)->replaceWith((*def)->getExpression());
     253                    def = ifNode->removeDefined(*def);
     254                    continue;
     255                }
     256                ++def;
     257            }
     258
     259            // Process the If body
     260            eliminateRedundantCode(cast<If>(stmt)->getBody(), &encountered);
    267261
    268262            // If we ended up removing all of the defined variables, delete the If node.
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4861 r4868  
    8787 ** ------------------------------------------------------------------------------------------------------------- */
    8888void PabloAST::replaceAllUsesWith(PabloAST * expr) {   
    89     Statement * user[mUsers.size()];
     89    Statement * replacements[mUsers.size()];
    9090    Vector::size_type users = 0;
    91     for (PabloAST * u : mUsers) {
    92         if (isa<Statement>(u) && u != expr) {
    93             user[users++] = cast<Statement>(u);
    94         }
     91    bool exprIsAUser = false;
     92    assert (expr);
     93    for (PabloAST * user : mUsers) {
     94        if (LLVM_UNLIKELY(user == expr)) {
     95            exprIsAUser = true;
     96            continue;
     97        }
     98        replacements[users++] = cast<Statement>(user);
    9599    }
    96100    mUsers.clear();
    97     assert (expr);
     101    if (LLVM_UNLIKELY(exprIsAUser)) {
     102        mUsers.push_back(expr);
     103    }
    98104    for (Vector::size_type i = 0; i != users; ++i) {
    99         user[i]->replaceUsesOfWith(this, expr);
     105        replacements[i]->replaceUsesOfWith(this, expr);
    100106    }
    101107}
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.cpp

    r4860 r4868  
    4646}
    4747
    48 void If::removeDefined(Assign * def) {
     48If::DefinedVars::iterator If::removeDefined(Assign * def) {
    4949    auto f = std::find(mDefined.begin(), mDefined.end(), def);
    5050    if (LLVM_LIKELY(f != mDefined.end())) {
    51         mDefined.erase(f);
    5251        def->removeUser(this);
    5352        this->removeUser(def);
     53        return mDefined.erase(f);
    5454    }
     55    return mDefined.end();
    5556}
    5657
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.h

    r4856 r4868  
    4848    }
    4949    void addDefined(Assign * def);
    50     void removeDefined(Assign * def);
     50    DefinedVars::iterator removeDefined(Assign * def);
    5151protected:
    5252    If(PabloAST * expr, const std::initializer_list<Assign *> definedVars, PabloBlock & body);
  • icGREP/icgrep-devel/icgrep/toolchain.cpp

    r4854 r4868  
    148148        pablo::BDDMinimizationPass::optimize(*function);
    149149        pablo::AutoMultiplexing::optimize(*function, MultiplexingSetLimit, MultiplexingSelectionLimit);
    150     }   
     150    }
    151151    if (EnableReassociation) {
    152152        pablo::BooleanReassociationPass::optimize(*function);
Note: See TracChangeset for help on using the changeset viewer.