Changeset 4638


Ignore:
Timestamp:
Jul 3, 2015, 4:48:07 PM (4 years ago)
Author:
nmedfort
Message:

Minor modifications

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

Legend:

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

    r4631 r4638  
    33#include <UCD/unicode_set.h>
    44#include <utf8_encoder.h>
    5 #include <iostream>
    65
    76using namespace cc;
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4629 r4638  
    6161                                      cl::cat(cPabloOptimizationsOptions));
    6262#ifdef ENABLE_MULTIPLEXING
    63 static cl::opt<bool> PabloMutualExclusionPass("disable-multiplexing", cl::init(true),
    64                                       cl::desc("Disable combining Advances whose inputs are mutual exclusive."),
     63static cl::opt<bool> EnableMultiplexing("enable-multiplexing", cl::init(false),
     64                                      cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."),
    6565                                      cl::cat(cPabloOptimizationsOptions));
    6666#endif
     
    106106    }
    107107
    108     if (IsPregeneratedUnicodeEnabled()) {
     108    if (UsePregeneratedUnicode()) {
    109109        resolveProperties(re_ast);
    110110    }
     
    168168    }
    169169    #ifdef ENABLE_MULTIPLEXING
    170     if (PabloMutualExclusionPass) {
    171         if (AutoMultiplexing::optimize(basisBits, main) && !DisablePabloCSE) {
    172             Simplifier::optimize(main);
    173         }
     170    if (EnableMultiplexing) {
     171        AutoMultiplexing::optimize(basisBits, main);
    174172    }
    175173    #endif
     
    182180
    183181    PabloCompiler pablo_compiler(basisBits);
    184     if (IsPregeneratedUnicodeEnabled()) {
     182    if (UsePregeneratedUnicode()) {
    185183        install_property_gc_fn_ptrs(pablo_compiler);
    186184        install_property_sc_fn_ptrs(pablo_compiler);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4629 r4638  
    2020using namespace boost::numeric::ublas;
    2121
    22 // #define PRINT_DEBUG_OUTPUT
    23 
    24 #if !defined(NDEBUG) || defined(PRINT_DEBUG_OUTPUT)
     22#define PRINT_DEBUG_OUTPUT
     23
     24#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
     25#define PRINT_DEBUG_OUTPUT
     26#endif
     27
     28#ifdef PRINT_DEBUG_OUTPUT
     29
    2530#include <iostream>
    2631
     
    96101bool AutoMultiplexing::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
    97102
    98     std::random_device rd;
    99     const auto seed = rd();
     103    // std::random_device rd;
     104    const auto seed = 2938639837; // rd();
    100105    RNG rng(seed);
    101106
     
    117122    LOG("Characterize:            " << (end_characterize - start_characterize));
    118123
     124    RECORD_TIMESTAMP(start_create_multiplex_graph);
     125    const bool multiplex = am.generateMultiplexSets(rng, 1);
     126    RECORD_TIMESTAMP(end_create_multiplex_graph);
     127    LOG("GenerateMultiplexSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
     128
     129    if (multiplex) {
     130
     131        RECORD_TIMESTAMP(start_select_multiplex_sets);
     132        am.selectMultiplexSets(rng);
     133        RECORD_TIMESTAMP(end_select_multiplex_sets);
     134        LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
     135
     136        RECORD_TIMESTAMP(start_subset_constraints);
     137        am.applySubsetConstraints();
     138        RECORD_TIMESTAMP(end_subset_constraints);
     139        LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
     140
     141        RECORD_TIMESTAMP(start_select_independent_sets);
     142        am.multiplexSelectedIndependentSets();
     143        RECORD_TIMESTAMP(end_select_independent_sets);
     144        LOG("MultiplexSelectedSets:   " << (end_select_independent_sets - start_select_independent_sets));
     145
     146        RECORD_TIMESTAMP(start_topological_sort);
     147        am.topologicalSort(entry);
     148        RECORD_TIMESTAMP(end_topological_sort);
     149        LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
     150    }
     151
    119152    RECORD_TIMESTAMP(start_shutdown);
    120153    am.shutdown();
    121154    RECORD_TIMESTAMP(end_shutdown);
    122155    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
    123 
    124     RECORD_TIMESTAMP(start_create_multiplex_graph);
    125     const bool multiplex = am.generateMultiplexSets(rng, 1);
    126     RECORD_TIMESTAMP(end_create_multiplex_graph);
    127     LOG("GenerateMultiplexSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
    128 
    129     if (multiplex) {
    130 
    131         RECORD_TIMESTAMP(start_select_multiplex_sets);
    132         am.selectMultiplexSets(rng);
    133         RECORD_TIMESTAMP(end_select_multiplex_sets);
    134         LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
    135 
    136         RECORD_TIMESTAMP(start_subset_constraints);
    137         am.applySubsetConstraints();
    138         RECORD_TIMESTAMP(end_subset_constraints);
    139         LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
    140 
    141         RECORD_TIMESTAMP(start_select_independent_sets);
    142         am.multiplexSelectedIndependentSets();
    143         RECORD_TIMESTAMP(end_select_independent_sets);
    144         LOG("MultiplexSelectedSets:   " << (end_select_independent_sets - start_select_independent_sets));
    145 
    146         RECORD_TIMESTAMP(start_topological_sort);
    147         am.topologicalSort(entry);
    148         RECORD_TIMESTAMP(end_topological_sort);
    149         LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
    150     }
    151156
    152157    LOG_NUMBER_OF_ADVANCES(entry);
     
    401406                DdNode * Ii = std::get<1>(mAdvance[i]);
    402407                DdNode * Ni = std::get<2>(mAdvance[i]);
    403                 // TODO: test both Cudd_And and Cudd_bddIntersect to see which is faster
    404                 DdNode * const IiIk = Intersect(Ik, Ii);
     408                DdNode * const IiIk = And(Ik, Ii);
    405409                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    406410                if (noSatisfyingAssignment(IiIk)) {
     
    509513}
    510514
    511 inline DdNode * AutoMultiplexing::Intersect(DdNode * const x, DdNode * const y) {
    512     DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r);
    513     return r;
    514 }
    515 
    516515inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) {
    517516    DdNode * r = Cudd_bddOr(mManager, x, y);
     
    541540
    542541inline void AutoMultiplexing::shutdown() {
     542    #ifdef PRINT_DEBUG_OUTPUT
     543    Cudd_PrintInfo(mManager, stderr);
     544    #endif
    543545    Cudd_Quit(mManager);
    544546}
     
    759761    }
    760762    #endif
    761 }
    762 
    763 /** ------------------------------------------------------------------------------------------------------------- *
    764  * @brief choose
    765  ** ------------------------------------------------------------------------------------------------------------- */
    766 
    767 inline Statement * choose(PabloAST * x, PabloAST * y, Statement * z) {
    768     return isa<Statement>(x) ? cast<Statement>(x) : (isa<Statement>(y) ? cast<Statement>(y) : z);
    769763}
    770764
     
    850844                        Q.push(std::get<0>(mAdvance[i])->getOperand(0));
    851845                    }                   
     846                    pb->setInsertPoint(adv);
    852847                    while (Q.size() > 1) {
    853848                        PabloAST * a1 = Q.front(); Q.pop();
    854                         PabloAST * a2 = Q.front(); Q.pop();
    855                         pb->setInsertPoint(cast<Statement>(a2));
    856                         Q.push(pb->createOr(a1, a2));
     849                        PabloAST * a2 = Q.front(); Q.pop();                       
     850                        Q.push(pb->createOr(a1, a2, "subset"));
    857851                    }
    858852                    assert (Q.size() == 1);
    859853
    860854                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
    861                     adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in"));
     855                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset"));
    862856
    863857                    // Similar to the above, we're going to OR together the result of each advance,
     
    873867                        Q.push(std::get<0>(mAdvance[i]));
    874868                    }
     869                    pb->setInsertPoint(adv);
    875870                    while (Q.size() > 1) {
    876871                        PabloAST * a1 = Q.front(); Q.pop();
    877                         PabloAST * a2 = Q.front(); Q.pop();
    878                         pb->setInsertPoint(choose(a2, a1, adv));
    879                         Q.push(pb->createOr(a1, a2));
     872                        PabloAST * a2 = Q.front(); Q.pop();                       
     873                        Q.push(pb->createOr(a1, a2, "subset"));
    880874                    }
    881875                    assert (Q.size() == 1);
     
    914908
    915909    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
    916     std::vector<Advance *> V(max_n);
     910    std::vector<Advance *> input(max_n);
    917911    std::vector<PabloAST *> muxed(max_m);
    918912    circular_buffer<PabloAST *> Q(max_n);
     
    931925            for (unsigned i = 0; i != n; ++ei, ++i) {
    932926                I[i] = target(*ei, mMultiplexSetGraph);
    933                 assert (I[i] < mAdvance.size());
    934927            }
    935928            std::sort(I.begin(), I.begin() + n);
    936929
    937930            for (unsigned i = 0; i != n; ++i) {
    938                 V[i] = std::get<0>(mAdvance[I[i]]);
    939             }
    940 
    941             PabloBlock * const block = V[0]->getParent();
    942             assert (block);
    943 
    944             // Sanity test to make sure every advance is in the same scope.
    945             #ifndef NDEBUG
    946             for (unsigned i = 1; i != n; ++i) {
    947                 assert (I[i - 1] < I[i]);
    948                 assert (V[i - 1] != V[i]);
    949                 assert (V[i]->getParent() == block);
    950             }
    951             #endif
    952 
    953             PabloBuilder pb(*block);
     931                input[i] = std::get<0>(mAdvance[I[i]]);
     932            }
     933
     934            PabloBlock * const block = input[0]->getParent();
     935            block->setInsertPoint(block->back());
     936            PabloBuilder builder(*block);
     937            Advance * const adv = input[0];
    954938
    955939            /// Perform n-to-m Multiplexing
    956940            for (size_t j = 0; j != m; ++j) {
    957 
    958                 assert (Q.empty());
    959941
    960942                std::ostringstream prefix;
     
    962944                for (size_t i = 1; i <= n; ++i) {
    963945                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
    964                         assert (!Q.full());
    965                         PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
    966                         // prefix << '_' << V[i - 1]->getName()->to_string();
    967                         Q.push_back(tmp);
    968                     }
    969                 }
    970 
    971                 assert (Q.size() >= 1);
    972 
    973                 Advance * const adv = V[j];
    974                 // TODO: figure out a way to determine whether we're creating a duplicate value below.
    975                 // The expression map findOrCall ought to work conceptually but the functors method
    976                 // doesn't really work anymore with the current API.
     946                        Q.push_back(input[i - 1]->getOperand(0));
     947                    }
     948                }
     949
    977950                while (Q.size() > 1) {
    978951                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    979952                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    980                     assert (!Q.full());
    981                     pb.setInsertPoint(choose(a2, a1, adv));
    982                     Q.push_back(pb.createOr(a1, a2));
    983                 }
    984                 assert (Q.size() == 1);
     953                    assert (!Q.full());                                       
     954                    Q.push_back(builder.createOr(a2, a1, "muxing"));
     955                }
    985956
    986957                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
    987                 muxed[j] = pb.createAdvance(mux, adv->getOperand(1), prefix.str());
     958                muxed[j] = builder.createAdvance(mux, adv->getOperand(1), prefix.str());
    988959            }
    989960
     
    993964            for (size_t i = 1; i <= n; ++i) {
    994965
    995                 Advance * const adv = V[i - 1];
    996 
    997                 pb.setInsertPoint(adv);
    998                 assert (Q.empty());
    999966                for (size_t j = 0; j != m; ++j) {
    1000967                    if ((i & (static_cast<size_t>(1) << j)) == 0) {
     
    1003970                }
    1004971
    1005                 assert (Q.size() <= m);
    1006                 PabloAST * neg = nullptr;
    1007972                if (LLVM_LIKELY(Q.size() > 0)) {
    1008973                    while (Q.size() > 1) {
     
    1010975                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    1011976                        assert (!Q.full());
    1012                         Q.push_back(pb.createOr(a1, a2));
     977                        Q.push_back(builder.createOr(a2, a1, "demuxing"));
    1013978                    }
    1014979                    assert (Q.size() == 1);
    1015                     neg = pb.createNot(Q.front()); Q.pop_front(); assert (neg);
    1016                 }
    1017 
    1018                 assert (Q.empty());
     980                    PabloAST * neg = Q.front(); Q.pop_front();
     981                    Q.push_back(builder.createNot(neg, "demuxing")); assert (neg);
     982                }
     983
    1019984                for (unsigned j = 0; j != m; ++j) {
    1020985                    if ((i & (static_cast<unsigned>(1) << j)) != 0) {
     
    1024989                }
    1025990
    1026                 assert (Q.size() <= m);
    1027                 assert (Q.size() >= 1);
    1028 
    1029991                while (Q.size() > 1) {
    1030992                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    1031993                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    1032994                    assert (!Q.full());
    1033                     Q.push_back(pb.createAnd(a1, a2));
    1034                 }
    1035 
    1036                 assert (Q.size() == 1);
    1037 
    1038                 PabloAST * demux = Q.front(); Q.pop_front(); assert (demux);
    1039                 if (LLVM_LIKELY(neg != nullptr)) {
    1040                     demux = pb.createAnd(demux, neg);
    1041                 }
    1042                 V[i - 1]->replaceWith(demux, true, true);
    1043             }
    1044         }
    1045     }
    1046 }
     995                    Q.push_back(builder.createAnd(a1, a2, "demuxing"));
     996                }
     997
     998                PabloAST * demuxed = Q.front(); Q.pop_front(); assert (demux);
     999                input[i - 1]->replaceWith(demuxed, true, true);
     1000            }
     1001
     1002            simplify(muxed, m, builder);
     1003        }
     1004    }
     1005}
     1006
     1007/** ------------------------------------------------------------------------------------------------------------- *
     1008 * @brief simplify
     1009 ** ------------------------------------------------------------------------------------------------------------- */
     1010void AutoMultiplexing::simplify(const std::vector<PabloAST *> & variables, const unsigned n, PabloBuilder & builder) const {
     1011
     1012
     1013
     1014
     1015
     1016
     1017}
     1018
     1019
    10471020
    10481021/** ------------------------------------------------------------------------------------------------------------- *
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4629 r4638  
    77#include <boost/graph/adjacency_list.hpp>
    88#include <boost/graph/adjacency_matrix.hpp>
    9 #include <boost/graph/edge_list.hpp>
    109#include <boost/container/flat_map.hpp>
    11 #include <boost/container/flat_set.hpp>
    1210#include <boost/numeric/ublas/matrix.hpp>
    1311#include <random>
     
    1917
    2018namespace pablo {
     19
     20class PabloBuilder;
    2121
    2222class AutoMultiplexing {
     
    4848    void applySubsetConstraints();
    4949    void multiplexSelectedIndependentSets() const;
     50    void simplify(const std::vector<PabloAST *> & variables, const unsigned m, PabloBuilder & block) const;
    5051    void topologicalSort(PabloBlock & entry) const;
    5152    inline AutoMultiplexing()
     
    5960    bool isZero(DdNode * const x) const;
    6061    DdNode * And(DdNode * const x, DdNode * const y);
    61     DdNode * Intersect(DdNode * const x, DdNode * const y);
    6262    DdNode * Or(DdNode * const x, DdNode * const y);
    6363    DdNode * Xor(DdNode * const x, DdNode * const y);
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r4631 r4638  
    3838static cl::opt<bool> DisableUnicodeLineBreak("disable-unicode-linebreak", cl::init(false),
    3939                     cl::desc("disable Unicode line breaks - use LF only"), cl::cat(fREcompilationOptions));
    40 static cl::opt<bool> DisablePregeneratedUnicode("disable-pregenerated-unicode", cl::init(false),
     40static cl::opt<bool> DisablePregeneratedUnicode("disable-pregenerated-unicode", cl::init(true),
    4141                     cl::desc("disable use of pregenerated Unicode character class sets"), cl::cat(fREcompilationOptions));
    4242
     
    4545namespace re {
    4646
    47 bool IsPregeneratedUnicodeEnabled() {
     47bool UsePregeneratedUnicode() {
    4848    return !DisablePregeneratedUnicode;
    4949}
     
    271271    }
    272272    else if (name->getType() == Name::Type::UnicodeProperty) {
    273         if (IsPregeneratedUnicodeEnabled()) {
     273        if (UsePregeneratedUnicode()) {
    274274            var = mPB.createCall(name->getName());
    275275        }
  • icGREP/icgrep-devel/icgrep/re/re_compiler.h

    r4626 r4638  
    3535namespace re {
    3636
    37 bool IsPregeneratedUnicodeEnabled();
     37bool UsePregeneratedUnicode();
    3838
    3939enum MarkerPosition {FinalMatchByte, InitialPostPositionByte, FinalPostPositionByte};
Note: See TracChangeset for help on using the changeset viewer.