Changeset 6173 for icGREP


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

Added RE_Inspector.

Migrated RE passes to RE_Transformer.

Incorporated Memoizer functionality into RE_Transformer/Inspector.

Removed Memoizer.

Bug fix for unicode_set.

Location:
icGREP/icgrep-devel/icgrep
Files:
1 added
2 deleted
27 edited

Legend:

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

    r6157 r6173  
    100100# RegExpADT is the core library for representing, parsing and printing regular expressions
    101101add_library(RegExpADT re/re_rep.cpp re/re_diff.cpp re/re_intersect.cpp re/re_range.cpp re/re_assertion.cpp re/printer_re.cpp re/re_utility.cpp)
    102 add_library(RegExpCompiler ${RE_PARSERS_SRC} re/casing.cpp re/to_utf8.cpp re/re_memoizer.cpp re/re_nullable.cpp re/re_simplifier.cpp re/re_star_normal.cpp re/re_minimizer.cpp re/re_local.cpp re/re_compiler.cpp re/re_analysis.cpp re/re_toolchain.cpp re/re_name_resolve.cpp re/re_name_gather.cpp re/collect_ccs.cpp re/re_multiplex.cpp re/re_utility.cpp re/grapheme_clusters.cpp re/exclude_CC.cpp re/replaceCC.cpp)
     102add_library(RegExpCompiler ${RE_PARSERS_SRC} re/casing.cpp re/to_utf8.cpp re/re_nullable.cpp re/re_simplifier.cpp re/re_star_normal.cpp re/re_minimizer.cpp re/re_local.cpp re/re_compiler.cpp re/re_analysis.cpp re/re_toolchain.cpp re/re_name_resolve.cpp re/re_name_gather.cpp re/collect_ccs.cpp re/re_multiplex.cpp re/re_utility.cpp re/grapheme_clusters.cpp re/exclude_CC.cpp re/replaceCC.cpp)
    103103add_library(UCDlib UCD/CaseFolding.cpp utf8_encoder.cpp utf16_encoder.cpp UCD/ucd_compiler.cpp UCD/PropertyObjects.cpp UCD/resolve_properties.cpp)
    104104add_library(GrepEngine  ${GREP_CORE_SRC} grep/grep_engine.cpp kernels/cc_kernel.cpp kernels/cc_scan_kernel.cpp kernels/charclasses.cpp kernels/streams_merge.cpp kernels/until_n.cpp kernels/UCD_property_kernel.cpp kernels/grapheme_kernel.cpp)
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp

    r5935 r6173  
    183183            const auto m = lengthOf(r) * QUAD_BITS;
    184184            if (LLVM_UNLIKELY(remaining < m)) {
    185                 return (base * QUAD_BITS) + remaining;
     185                return base + remaining;
    186186            }
    187187            base += m;
    188             remaining -= m * QUAD_BITS;
     188            remaining -= m;
    189189        } else { // if (typeOf(r) == Mixed) {
    190190            for (auto l = lengthOf(r); l; --l, ++qi) {
     
    197197                        const bitquad_t k = scan_forward_zeroes<bitquad_t>(q);
    198198                        if (remaining == 0) {
    199                             return (base * QUAD_BITS) + k;
     199                            return base + k;
    200200                        }
    201201                        q ^= static_cast<bitquad_t>(1) << k;
     
    203203                    }
    204204                }
    205                 ++base;
     205                base += QUAD_BITS;
    206206                remaining -= c;
    207207            }
  • icGREP/icgrep-devel/icgrep/lz4/grep/lz4_grep_base_generator.cpp

    r6165 r6173  
    2323#include <re/to_utf8.h>
    2424#include <re/re_analysis.h>
     25#include <re/re_name.h>
    2526#include <re/re_name_resolve.h>
    2627#include <re/re_name_gather.h>
  • icGREP/icgrep-devel/icgrep/lz4/lz4_base_generator.cpp

    r6150 r6173  
    1515#include <kernels/lz4/decompression/lz4_bitstream_decompression.h>
    1616
    17 
    1817using namespace llvm;
    1918using namespace parabix;
  • icGREP/icgrep-devel/icgrep/pablo/builder.cpp

    r6129 r6173  
    1818#include <pablo/ps_assign.h>
    1919#include <boost/preprocessor/variadic/elem.hpp>
     20#include <type_traits>
    2021
    2122using namespace llvm;
    2223
    2324namespace pablo {
     25
     26using TypeId = PabloAST::ClassTypeId;
    2427
    2528#define GET(I, ...) \
    2629    reinterpret_cast<decltype(BOOST_PP_VARIADIC_ELEM(I, __VA_ARGS__))>(arg##I)
    2730
    28 #define MAKE_UNARY(NAME, TYPE, ARGS...) \
     31#define MAKE_UNARY(TYPE, ARGS...) \
     32[&](){ /* immediately invoked lambda */ \
    2933struct __##NAME { \
    3034    inline PabloAST * operator()(void * const arg0) { \
    31         return mPb->NAME(GET(0, ARGS)); \
     35        return mPb->create##TYPE(GET(0, ARGS)); \
    3236    } \
    3337    inline __##NAME(PabloBlock * const pb) : mPb(pb) {} \
     
    3640}; \
    3741__##NAME functor(mPb); \
    38 PabloAST * result = mExprTable.findUnaryOrCall(std::move(functor), TYPE, ARGS)
    39 
    40 #define MAKE_NAMED_UNARY(NAME, TYPE, PREFIX, ARGS...) \
     42return cast<TYPE>(mExprTable.findUnaryOrCall(std::move(functor), TypeId::TYPE, ARGS)); \
     43}()
     44
     45#define MAKE_NAMED_UNARY(TYPE, PREFIX, ARGS...) \
     46[&](){ /* immediately invoked lambda */  \
    4147struct __##NAME { \
    4248    inline PabloAST * operator()(void * const arg0) { \
    43         return mPb->NAME(GET(0, ARGS), mPrefix); \
     49        return mPb->create##TYPE(GET(0, ARGS), mPrefix); \
    4450    } \
    4551    inline __##NAME(PabloBlock * const pb, const llvm::StringRef & prefix) : mPb(pb), mPrefix(prefix) {} \
     
    4955}; \
    5056__##NAME functor(mPb, prefix); \
    51 PabloAST * result = mExprTable.findUnaryOrCall(std::move(functor), TYPE, ARGS)
    52 
    53 #define MAKE_BINARY(NAME, TYPE, ARGS...) \
     57return cast<TYPE>(mExprTable.findUnaryOrCall(std::move(functor), TypeId::TYPE, ARGS)); \
     58}()
     59
     60#define MAKE_BINARY(TYPE, ARGS...) \
     61[&](){ /* immediately invoked lambda */  \
    5462struct __##NAME { \
    5563    inline PabloAST * operator()(void * const arg0, void * const arg1) { \
    56         return mPb->NAME(GET(0, ARGS), GET(1, ARGS)); \
     64        return mPb->create##TYPE(GET(0, ARGS), GET(1, ARGS)); \
    5765    } \
    5866    inline __##NAME(PabloBlock * const pb) : mPb(pb) {} \
     
    6169}; \
    6270__##NAME functor(mPb); \
    63 PabloAST * result = mExprTable.findBinaryOrCall(std::move(functor), TYPE, ARGS)
    64 
    65 #define MAKE_NAMED_BINARY(NAME, TYPE, PREFIX, ARGS...) \
     71return cast<TYPE>(mExprTable.findBinaryOrCall(std::move(functor), TypeId::TYPE, ARGS)); \
     72}()
     73
     74#define MAKE_NAMED_BINARY(TYPE, PREFIX, ARGS...) \
     75[&](){ /* immediately invoked lambda */  \
    6676struct __##NAME { \
    6777    inline PabloAST * operator()(void * const arg0, void * const arg1) { \
    68         return mPb->NAME(GET(0, ARGS), GET(1, ARGS), mPrefix); \
     78        return mPb->create##TYPE(GET(0, ARGS), GET(1, ARGS), mPrefix); \
    6979    } \
    7080    inline __##NAME(PabloBlock * const pb, const llvm::StringRef & prefix) : mPb(pb), mPrefix(prefix) {} \
     
    7484}; \
    7585__##NAME functor(mPb, PREFIX); \
    76 PabloAST * result = mExprTable.findBinaryOrCall(std::move(functor), TYPE, ARGS)
    77 
    78 #define MAKE_TERNARY(NAME, TYPE, ARGS...) \
     86return cast<TYPE>(mExprTable.findBinaryOrCall(std::move(functor), TypeId::TYPE, ARGS)); \
     87}()
     88
     89#define MAKE_TERNARY(TYPE, ARGS...) \
     90[&](){ /* immediately invoked lambda */  \
    7991struct __##NAME { \
    8092    inline PabloAST * operator()(void * const arg0, void * const arg1, void * const arg2) { \
    81         return mPb->NAME(GET(0, ARGS), GET(1, ARGS), GET(2, ARGS)); \
     93        return mPb->create##TYPE(GET(0, ARGS), GET(1, ARGS), GET(2, ARGS)); \
    8294    } \
    8395    inline __##NAME(PabloBlock * const pb) : mPb(pb) {} \
     
    8698}; \
    8799__##NAME functor(mPb); \
    88 PabloAST * result = mExprTable.findTernaryOrCall(std::move(functor), TYPE, ARGS)
    89 
    90 #define MAKE_NAMED_TERNARY(NAME, TYPE, PREFIX, ARGS...) \
     100return cast<TYPE>(mExprTable.findTernaryOrCall(std::move(functor), TypeId::TYPE, ARGS)); \
     101}()
     102
     103#define MAKE_NAMED_TERNARY(TYPE, PREFIX, ARGS...) \
     104[&](){ /* immediately invoked lambda */  \
    91105struct __##NAME { \
    92106    inline PabloAST * operator()(void * const arg0, void * const arg1, void * const arg2) { \
    93         return mPb->NAME(GET(0, ARGS), GET(1, ARGS), GET(2, ARGS), mPrefix); \
     107        return mPb->create##TYPE(GET(0, ARGS), GET(1, ARGS), GET(2, ARGS), mPrefix); \
    94108    } \
    95109    inline __##NAME(PabloBlock * const pb, const llvm::StringRef & prefix) : mPb(pb), mPrefix(prefix) {} \
     
    99113}; \
    100114__##NAME functor(mPb, PREFIX); \
    101 PabloAST * result = mExprTable.findTernaryOrCall(std::move(functor), TYPE, ARGS)
    102 
    103 using TypeId = PabloAST::ClassTypeId;
     115return cast<TYPE>(mExprTable.findTernaryOrCall(std::move(functor), TypeId::TYPE, ARGS)); \
     116}()
    104117
    105118PabloAST * PabloBuilder::createAdvance(PabloAST * expr, not_null<Integer *> shiftAmount) {
     
    107120        return expr;
    108121    }
    109     MAKE_BINARY(createAdvance, TypeId::Advance, expr, shiftAmount.get());
    110     return result;
     122    return MAKE_BINARY(Advance, expr, shiftAmount.get());
    111123}
    112124
     
    115127        return expr;
    116128    }
    117     MAKE_NAMED_BINARY(createAdvance, TypeId::Advance, prefix, expr, shiftAmount.get());
    118     return result;
     129    return MAKE_NAMED_BINARY(Advance, prefix, expr, shiftAmount.get());
    119130}
    120131
     
    129140        return createAdvanceThenScanTo(createAnd(expr, indexStream), indexStream);
    130141    }
    131     MAKE_TERNARY(createIndexedAdvance, TypeId::IndexedAdvance, expr, indexStream, shiftAmount.get());
    132     return result;
     142    return MAKE_TERNARY(IndexedAdvance, expr, indexStream, shiftAmount.get());
    133143}
    134144
     
    143153        return createAdvanceThenScanTo(expr, indexStream, prefix);
    144154    }
    145     MAKE_NAMED_TERNARY(createIndexedAdvance, TypeId::IndexedAdvance, prefix, expr, indexStream, shiftAmount.get());
    146     return result;
     155    return MAKE_NAMED_TERNARY(IndexedAdvance, prefix, expr, indexStream, shiftAmount.get());
    147156}
    148157   
    149158Extract * PabloBuilder::createExtract(Var * array, not_null<Integer *> index) {
    150     MAKE_BINARY(createExtract, TypeId::Extract, array, index.get());
    151     return cast<Extract>(result);
     159    return MAKE_BINARY(Extract, array, index.get());
    152160}
    153161
     
    156164        return expr;
    157165    }
    158     MAKE_BINARY(createLookahead, TypeId::Lookahead, expr, shiftAmount.get());
    159     return result;
     166    return MAKE_BINARY(Lookahead, expr, shiftAmount.get());
    160167}
    161168
     
    164171        return expr;
    165172    }
    166     MAKE_NAMED_BINARY(createLookahead, TypeId::Lookahead, prefix, expr, shiftAmount.get());
    167     return result;
     173    return MAKE_NAMED_BINARY(Lookahead, prefix, expr, shiftAmount.get());
    168174}
    169175
     
    178184        return not1->getOperand(0);
    179185    }
    180     MAKE_UNARY(createNot, TypeId::Not, expr);
    181     return result;
     186    return MAKE_UNARY(Not, expr);
    182187}
    183188
     
    192197        return not1->getOperand(0);
    193198    }
    194     MAKE_NAMED_UNARY(createNot, TypeId::Not, prefix, expr);
    195     return result;
     199    return MAKE_NAMED_UNARY(Not, prefix, expr);
    196200}
    197201
    198202PabloAST * PabloBuilder::createCount(PabloAST * expr) {
    199     MAKE_UNARY(createCount, TypeId::Count, expr);
    200     return result;
     203    return MAKE_UNARY(Count, expr);
    201204}
    202205
    203206PabloAST * PabloBuilder::createCount(PabloAST * expr, const llvm::StringRef & prefix) {
    204     MAKE_NAMED_UNARY(createCount, TypeId::Count, prefix, expr);
    205     return result;
     207    return MAKE_NAMED_UNARY(Count, prefix, expr);
    206208}
    207209
    208210PabloAST * PabloBuilder::createRepeat(not_null<Integer *> fieldWidth, PabloAST * value) {
    209     MAKE_BINARY(createRepeat, TypeId::Repeat, fieldWidth.get(), value);
    210     return result;
     211    return MAKE_BINARY(Repeat, fieldWidth.get(), value);
    211212}
    212213
    213214PabloAST * PabloBuilder::createRepeat(not_null<Integer *> fieldWidth, PabloAST * value, const llvm::StringRef & prefix) {
    214     MAKE_NAMED_BINARY(createRepeat, TypeId::Repeat, prefix, fieldWidth.get(), value);
    215     return result;
     215    return MAKE_NAMED_BINARY(Repeat, prefix, fieldWidth.get(), value);
    216216}
    217217
    218218   
    219219PabloAST * PabloBuilder::createPackL(not_null<Integer *> fieldWidth, PabloAST * value) {
    220     MAKE_BINARY(createPackL, TypeId::PackL, fieldWidth.get(), value);
    221     return result;
     220    return MAKE_BINARY(PackL, fieldWidth.get(), value);
    222221}
    223222
    224223PabloAST * PabloBuilder::createPackH(not_null<Integer *> fieldWidth, PabloAST * value) {
    225     MAKE_BINARY(createPackH, TypeId::PackH, fieldWidth.get(), value);
    226     return result;
     224    return MAKE_BINARY(PackH, fieldWidth.get(), value);
    227225}
    228226
     
    255253        std::swap(expr1, expr2);
    256254    }
    257     MAKE_BINARY(createAnd, TypeId::And, expr1, expr2);
    258     return result;
     255    return MAKE_BINARY(And, expr1, expr2);
    259256}
    260257
     
    286283        std::swap(expr1, expr2);
    287284    }
    288     MAKE_NAMED_BINARY(createAnd, TypeId::And, prefix, expr1, expr2);
    289     return result;
     285    return MAKE_NAMED_BINARY(And, prefix, expr1, expr2);
    290286}
    291287
     
    333329        std::swap(expr1, expr2);
    334330    }
    335     MAKE_BINARY(createOr, TypeId::Or, expr1, expr2);
    336     return result;
     331    return MAKE_BINARY(Or, expr1, expr2);
    337332}
    338333
     
    380375        std::swap(expr1, expr2);
    381376    }
    382     MAKE_NAMED_BINARY(createOr, TypeId::Or, prefix, expr1, expr2);
    383     return result;
     377    return MAKE_NAMED_BINARY(Or, prefix, expr1, expr2);
    384378}
    385379
     
    403397        std::swap(expr1, expr2);
    404398    }
    405     MAKE_BINARY(createXor, TypeId::Xor, expr1, expr2);
    406     return result;
     399    return MAKE_BINARY(Xor, expr1, expr2);
    407400}
    408401
     
    426419        std::swap(expr1, expr2);
    427420    }
    428     MAKE_NAMED_BINARY(createXor, TypeId::Xor, prefix, expr1, expr2);
    429     return result;
     421    return MAKE_NAMED_BINARY(Xor, prefix, expr1, expr2);
    430422}
    431423
     
    442434        }
    443435    }
    444     MAKE_BINARY(createAdd, TypeId::Add, expr1, expr2);
    445     return result;
     436    return MAKE_BINARY(Add, expr1, expr2);
    446437}
    447438
     
    458449        }
    459450    }
    460     MAKE_BINARY(createSubtract, TypeId::Subtract, expr1, expr2);
    461     return result;
     451    return MAKE_BINARY(Subtract, expr1, expr2);
    462452}
    463453
     
    466456        return getInteger(cast<Integer>(expr1)->value() < cast<Integer>(expr2)->value() ? 1 : 0);
    467457    }
    468     MAKE_BINARY(createLessThan, TypeId::LessThan, expr1, expr2);
    469     return result;
     458    return MAKE_BINARY(LessThan, expr1, expr2);
    470459}
    471460
     
    474463        return getInteger(cast<Integer>(expr1)->value() == cast<Integer>(expr2)->value() ? 1 : 0);
    475464    }
    476     MAKE_BINARY(createEquals, TypeId::Equals, expr1, expr2);
    477     return result;
     465    return MAKE_BINARY(Equals, expr1, expr2);
    478466}
    479467
    480468PabloAST * PabloBuilder::createInFile(PabloAST * expr) {
    481469    if (isa<Zeroes>(expr)) return expr;
    482     MAKE_UNARY(createInFile, TypeId::InFile, expr);
    483     return result;
     470    return MAKE_UNARY(InFile, expr);
    484471}
    485472
    486473PabloAST * PabloBuilder::createInFile(PabloAST * expr, const llvm::StringRef & prefix) {
    487     MAKE_NAMED_UNARY(createInFile, TypeId::InFile, prefix, expr);
    488     return result;
     474    return MAKE_NAMED_UNARY(InFile, prefix, expr);
    489475}
    490476
    491477PabloAST * PabloBuilder::createAtEOF(PabloAST * expr) {
    492     MAKE_UNARY(createAtEOF, TypeId::AtEOF, expr);
    493     return result;
     478    return MAKE_UNARY(AtEOF, expr);
    494479}
    495480
    496481PabloAST * PabloBuilder::createAtEOF(PabloAST * expr, const llvm::StringRef & prefix) {
    497     MAKE_NAMED_UNARY(createAtEOF, TypeId::AtEOF, prefix, expr);
    498     return result;
     482    return MAKE_NAMED_UNARY(AtEOF, prefix, expr);
    499483}
    500484
     
    503487        return marker;
    504488    }
    505     MAKE_BINARY(createMatchStar, TypeId::MatchStar, marker, charclass);
    506     return result;
     489    return MAKE_BINARY(MatchStar, marker, charclass);
    507490}
    508491
     
    511494        return marker;
    512495    }
    513     MAKE_NAMED_BINARY(createMatchStar, TypeId::MatchStar, prefix, marker, charclass);
    514     return result;
     496    return MAKE_NAMED_BINARY(MatchStar, prefix, marker, charclass);
    515497}
    516498
     
    519501        return from;
    520502    }
    521     MAKE_BINARY(createScanThru, TypeId::ScanThru, from, thru);
    522     return result;
     503    return MAKE_BINARY(ScanThru, from, thru);
    523504}
    524505
     
    527508        return from;
    528509    }
    529     MAKE_NAMED_BINARY(createScanThru, TypeId::ScanThru, prefix, from, thru);
    530     return result;
     510    return MAKE_NAMED_BINARY(ScanThru, prefix, from, thru);
    531511}
    532512
     
    535515        return from;
    536516    }
    537     MAKE_BINARY(createScanTo, TypeId::ScanTo, from, to);
    538     return result;
     517    return MAKE_BINARY(ScanTo, from, to);
    539518}
    540519
     
    543522        return from;
    544523    }
    545     MAKE_NAMED_BINARY(createScanTo, TypeId::ScanTo, prefix, from, to);
    546     return result;
     524    return MAKE_NAMED_BINARY(ScanTo, prefix, from, to);
    547525}
    548526
     
    551529        return from;
    552530    }
    553     MAKE_BINARY(createAdvanceThenScanThru, TypeId::AdvanceThenScanThru, from, thru);
    554     return result;
     531    return MAKE_BINARY(AdvanceThenScanThru, from, thru);
    555532}
    556533
     
    559536        return from;
    560537    }
    561     MAKE_NAMED_BINARY(createAdvanceThenScanThru, TypeId::AdvanceThenScanThru, prefix, from, thru);
    562     return result;
     538    return MAKE_NAMED_BINARY(AdvanceThenScanThru, prefix, from, thru);
    563539}
    564540
     
    567543        return from;
    568544    }
    569     MAKE_BINARY(createAdvanceThenScanTo, TypeId::ScanTo, from, to);
    570     return result;
     545    return MAKE_BINARY(AdvanceThenScanTo, from, to);
    571546}
    572547
     
    575550        return from;
    576551    }
    577     MAKE_NAMED_BINARY(createAdvanceThenScanTo, TypeId::ScanTo, prefix, from, to);
    578     return result;
     552    return MAKE_NAMED_BINARY(AdvanceThenScanTo, prefix, from, to);
    579553}
    580554
     
    599573        return createXor(condition, trueExpr);
    600574    }
    601     MAKE_TERNARY(createSel, TypeId::Sel, condition, trueExpr, falseExpr);
    602     return result;
     575    return MAKE_TERNARY(Sel, condition, trueExpr, falseExpr);
    603576}
    604577
     
    623596        return createXor(condition, trueExpr);
    624597    }
    625     MAKE_NAMED_TERNARY(createSel, TypeId::Sel, prefix, condition, trueExpr, falseExpr);
    626     return result;
    627 }
    628 
    629 }
     598    return MAKE_NAMED_TERNARY(Sel, prefix, condition, trueExpr, falseExpr);
     599}
     600
     601}
  • icGREP/icgrep-devel/icgrep/pablo/builder.hpp

    r5935 r6173  
    55#include <pablo/expression_map.hpp>
    66#include <pablo/pe_var.h>
     7#include <util/not_null.h>
    78
    89namespace pablo {
     
    1011class PabloBuilder {
    1112public:
    12 
    13     template<typename T>
    14     struct not_null {
    15         not_null(T const value) : _value(value) { assert(_value); }
    16         not_null(std::nullptr_t) = delete;
    17         not_null(unsigned) = delete;
    18         operator T() const { return _value; }
    19         T operator-> () const { return _value; }
    20         T get() const { return _value; }
    21     private:
    22         T const  _value;
    23     };
    2413
    2514    using iterator = PabloBlock::iterator;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.cpp

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

    r5935 r6173  
    1212#include <re/re_assertion.h>
    1313#include <cc/alphabet.h>
    14 #include <re/re_memoizer.hpp>
     14#include <re/re_toolchain.h>
    1515
    1616#include <boost/container/flat_set.hpp>
     
    2121namespace re {
    2222   
    23 struct SetCollector : private Memoizer {
    24     void collect(RE * const re);
    25 public:
    26     const cc::Alphabet * alphabet;
    27     std::vector<CC *> theSets;
    28     std::set<Name *> ignoredExternals;
     23struct SetCollector final : public RE_Inspector {
     24
     25    SetCollector(const cc::Alphabet * alphabet, const std::set<Name *> & ignoredExternals, std::vector<CC *> & ccs)
     26    : RE_Inspector(InspectionMode::IgnoreNonUnique)
     27    , alphabet(alphabet)
     28    , ignoredExternals(ignoredExternals)
     29    , ccs(ccs) {
     30
     31    }
     32
     33    void inspectName(Name * n) final {
     34        if (ignoredExternals.count(n) == 0) {
     35            RE_Inspector::inspectName(n);
     36        }
     37    }
     38
     39    void inspectCC(CC * cc) final {
     40        if (LLVM_LIKELY(cc->getAlphabet() == alphabet)) {
     41            ccs.push_back(cc);
     42        }
     43    }
     44
     45private:
     46    const cc::Alphabet * const alphabet;
     47    const std::set<Name *> & ignoredExternals;
     48    std::vector<CC *> & ccs;
    2949};
    3050
    31 void SetCollector::collect(RE * const re) {
    32     assert ("RE object cannot be null!" && re);
    33     if (CC * cc = dyn_cast<CC>(re)) {
    34         if (cc->getAlphabet() == alphabet) {
    35             if (find(cc) == end()) {
    36                 cc = memoize(cc);
    37                 theSets.push_back(cc);
    38             }
    39         }
    40     } else if (isa<Name>(re)) {
    41         if (ignoredExternals.find(cast<Name>(re)) != ignoredExternals.end()) return;
    42         auto def = cast<Name>(re)->getDefinition();
    43         if (def != nullptr)
    44             collect(def);
    45     } else if (isa<Seq>(re)) {
    46         for (auto item : *cast<Seq>(re)) {
    47             collect(item);
    48         }
    49     } else if (isa<Alt>(re)) {
    50         for (auto item : *cast<Alt>(re)) {
    51             collect(item);
    52         }
    53     } else if (isa<Rep>(re)) {
    54         collect(cast<Rep>(re)->getRE());
    55     } else if (isa<Assertion>(re)) {
    56         collect(cast<Assertion>(re)->getAsserted());
    57     } else if (isa<Diff>(re)) {
    58         collect(cast<Diff>(re)->getLH());
    59         collect(cast<Diff>(re)->getRH());
    60     } else if (isa<Intersect>(re)) {
    61         collect(cast<Intersect>(re)->getLH());
    62         collect(cast<Intersect>(re)->getRH());
    63     }
    64 }
    6551
    6652std::vector<CC *> collectCCs(RE * const re, const cc::Alphabet * a, std::set<Name *> external) {
    67     SetCollector collector;
    68     collector.alphabet = a;
    69     collector.ignoredExternals = external;
    70     collector.collect(re);
    71     return collector.theSets;
     53    std::vector<CC *> ccs;
     54    SetCollector collector(a, external, ccs);
     55    collector.inspectRE(re);
     56    return ccs;
    7257}
    7358
  • icGREP/icgrep-devel/icgrep/re/collect_ccs.h

    r5934 r6173  
    55#include <set>
    66
    7 namespace cc {class Alphabet;}
     7namespace cc { class Alphabet; }
    88namespace re {
    99
    10     class RE;
    11     class CC;
    12     class Name;
     10class RE;
     11class CC;
     12class Name;
    1313
    14     std::vector<CC *> collectCCs(RE * const re, const cc::Alphabet * a, std::set<Name *> external = {});
     14std::vector<CC *> collectCCs(RE * const re, const cc::Alphabet * a, std::set<Name *> external = {});
    1515
    1616}
  • icGREP/icgrep-devel/icgrep/re/grapheme_clusters.cpp

    r5896 r6173  
    1616#include <re/printer_re.h>
    1717#include <re/re_name_resolve.h>
     18
    1819#include <vector>                  // for vector, allocator
    1920#include <llvm/Support/Casting.h>  // for dyn_cast, isa
    2021#include <llvm/Support/ErrorHandling.h>
    2122#include <llvm/Support/raw_ostream.h>
     23
    2224
    2325/*
     
    3537namespace re {
    3638bool hasGraphemeClusterBoundary(const RE * re) {
    37     if (isa<CC>(re)) {
     39    if (isa<CC>(re) || isa<Range>(re)) {
    3840        return false;
    3941    } else if (const Name * n = dyn_cast<Name>(re)) {
     
    6971    else llvm_unreachable("Unknown RE type");
    7072}
    71    
     73
    7274RE * resolveGraphemeMode(RE * re, bool inGraphemeMode) {
    7375    if (isa<Name>(re)) {
  • icGREP/icgrep-devel/icgrep/re/parsers/parser.cpp

    r6169 r6173  
    255255    mCaptureGroupCount++;
    256256    std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
    257     Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
     257    Name * const capture  = makeCapture(captureName, captured);
    258258    auto key = std::make_pair("", captureName);
    259259    mNameMap.insert(std::make_pair(std::move(key), capture));
     
    777777
    778778CC * RE_Parser::createCC(const codepoint_t cp) {
    779     CC * cc = mMemoizer.memoize(makeCC(cp));
    780     return cc;
     779    return makeCC(cp);
    781780}
    782781
     
    817816
    818817Name * RE_Parser::makeDigitSet() {
    819     return mMemoizer.memoize(createName("nd"));
     818    return createName("nd");
    820819}
    821820
    822821Name * RE_Parser::makeAlphaNumeric() {
    823     return mMemoizer.memoize(createName("alnum"));
     822    return createName("alnum");
    824823}
    825824
    826825Name * RE_Parser::makeWhitespaceSet() {
    827     return mMemoizer.memoize(createName("whitespace"));
     826    return createName("whitespace");
    828827}
    829828
    830829Name * RE_Parser::makeWordSet() {
    831     return mMemoizer.memoize(createName("word"));
     830    return createName("word");
    832831}
    833832
     
    838837        return f->second;
    839838    }
    840     Name * const property = mMemoizer.memoize(makeName(value, Name::Type::UnicodeProperty));
     839    Name * const property = makeName(value, Name::Type::UnicodeProperty);
    841840    mNameMap.insert(std::make_pair(std::move(key), property));
    842841    return property;
     
    849848        return f->second;
    850849    }
    851     Name * const property = mMemoizer.memoize(makeName(prop, value, Name::Type::UnicodeProperty));
     850    Name * const property = makeName(prop, value, Name::Type::UnicodeProperty);
    852851    mNameMap.insert(std::make_pair(std::move(key), property));
    853852    return property;
  • icGREP/icgrep-devel/icgrep/re/parsers/parser.h

    r6169 r6173  
    99
    1010#include <map>
    11 #include <re/re_memoizer.hpp>
     11#include <set>
    1212#include <re/re_cc.h>
    1313
     
    262262    RE_Syntax                   mReSyntax;
    263263    NameMap                     mNameMap;
    264     Memoizer                    mMemoizer;
    265264};
    266265
  • icGREP/icgrep-devel/icgrep/re/re_any.h

    r5772 r6173  
    1616namespace re {
    1717
    18 class Any : public RE {
     18class Any {
    1919public:
    2020    static inline bool classof(const RE * re) {
    21         return (re->getClassTypeId() == ClassTypeId::CC) && llvm::cast<CC>(re)->full();
     21        if (llvm::isa<Name>(re)) {
     22            re = llvm::cast<Name>(re)->getDefinition();
     23            if (re == nullptr) return false;
     24        }
     25        return llvm::isa<CC>(re) && llvm::cast<CC>(re)->full();
    2226    }
    2327    static inline bool classof(const void *) {
    2428        return false;
    2529    }
    26 protected:
    27     Any() : RE(ClassTypeId::Any) {}
    28     virtual ~Any() {}
     30private:
     31    Any() {}
    2932};
    3033
  • icGREP/icgrep-devel/icgrep/re/re_diff.h

    r5267 r6173  
    1717        return mLh;
    1818    }
    19     void setLH(RE * lh) {
    20         mLh = lh;
    21     }
    2219    RE * getRH() const {
    2320        return mRh;
    24     }
    25     void setRH(RE * rh) {
    26         mRh = rh;
    2721    }
    2822protected:
     
    3731    virtual ~Diff() {}
    3832private:
    39     RE * mLh;
    40     RE * mRh;
     33    RE * const mLh;
     34    RE * const mRh;
    4135};
    4236
  • icGREP/icgrep-devel/icgrep/re/re_intersect.h

    r6171 r6173  
    3131    virtual ~Intersect() {}
    3232private:
    33     RE * mLh;
    34     RE * mRh;
     33    RE * const mLh;
     34    RE * const mRh;
    3535};
    3636
  • icGREP/icgrep-devel/icgrep/re/re_minimizer.cpp

    r5835 r6173  
    55#include <re/re_seq.h>
    66#include <re/re_rep.h>
    7 #include <re/re_diff.h>
    8 #include <re/re_intersect.h>
    9 #include <re/re_assertion.h>
    10 #include <re/re_memoizer.hpp>
     7#include <re/re_range.h>
    118#include <boost/container/flat_set.hpp>
    129#include <boost/container/flat_map.hpp>
    1310#include <llvm/ADT/SmallVector.h>
    14 
     11#include <re/re_toolchain.h>
    1512
    1613using namespace llvm;
     
    2320using List = std::vector<RE *>;
    2421
    25 struct PassContainer : private Memoizer {
    26 
    27     RE * minimize(RE * re) {
    28         const auto f = find(re);
    29         if (LLVM_UNLIKELY(f != end())) {
    30             return *f;
    31         }
    32         if (Alt * const alt = dyn_cast<Alt>(re)) {
    33             Set set;
    34             set.reserve(alt->size());
    35             for (RE * item : *alt) {
    36                 item = minimize(item);
    37                 if (LLVM_UNLIKELY(isa<Alt>(item))) {
    38                     for (RE * const innerItem : *cast<Alt>(item)) {
    39                         set.insert(innerItem);
    40                     }
    41                 } else if (CC * const cc = extractCC(item)) {
    42                     combineCC(cc);
    43                 } else {
    44                     set.insert(item);
    45                 }
    46             }
    47             // insert any CC objects into the alternation
    48             for (auto cc : mCombine) {
    49                 set.insert(memoize(cc));
    50             }
    51             mCombine.clear();
    52             // Pablo CSE may identify common prefixes but cannot identify common suffixes.
    53             extractCommonSuffixes(set);
    54             extractCommonPrefixes(set);
    55             re = makeAlt(set.begin(), set.end());
    56         } else if (Seq * const seq = dyn_cast<Seq>(re)) {
    57             List list;
    58             list.reserve(seq->size());
    59             for (RE * item : *seq) {
    60                 item = minimize(item);
    61                 if (LLVM_UNLIKELY(isa<Seq>(item))) {
    62                     for (RE * const innerItem : *cast<Seq>(item)) {
    63                         list.push_back(innerItem);
    64                     }
    65                 } else {
    66                     list.push_back(item);
    67                 }
    68             }
    69             for (unsigned i = 1, run = 0; i < list.size(); ) {
    70                 if (LLVM_UNLIKELY(list[i - 1] == list[i])) {
    71                     ++run;
    72                 } else if (LLVM_UNLIKELY(run != 0)) {
    73                     // If we have a run of the same RE, make a bounded repetition for it
    74                     const auto j = i - run; assert (j > 0);
    75                     list[j - 1] = memoize(makeRep(list[j - 1], run + 1, run + 1));
    76                     list.erase(list.begin() + j, list.begin() + i);
    77                     i = j;
    78                     run = 0;
     22struct PassContainer final : public RE_Transformer {
     23
     24    RE * transformAlt(Alt * alt) override {
     25        Set set;
     26        set.reserve(alt->size());
     27        assert ("combine list must be empty!" && mCombine.empty());
     28        for (RE * item : *alt) {
     29            // since transform will memorize every item/innerItem, set insert is sufficient here
     30            item = transform(item);
     31            if (LLVM_UNLIKELY(isa<Alt>(item))) {               
     32                for (RE * const innerItem : *cast<Alt>(item)) {
     33                    set.insert(innerItem);
     34                }
     35            } else if (CC * const cc = extractCC(item)) {
     36                combineCC(cc);
     37            } else {
     38                set.insert(item);
     39            }
     40        }
     41        // insert any CC objects into the alternation
     42        for (auto cc : mCombine) {
     43            set.insert(transform(cc));
     44        }
     45        mCombine.clear();
     46        // Pablo CSE may identify common prefixes but cannot identify common suffixes.
     47        extractCommonSuffixes(set);
     48        extractCommonPrefixes(set);
     49        if (unchanged(alt, set)) {
     50            return alt;
     51        } else {
     52            return makeAlt(set.begin(), set.end());
     53        }
     54    }
     55
     56    RE * transformSeq(Seq * seq) override {
     57        List list;
     58        list.reserve(seq->size());
     59        for (RE * item : *seq) {
     60            item = transform(item);
     61            if (LLVM_UNLIKELY(isa<Seq>(item))) {
     62                for (RE * const innerItem : *cast<Seq>(item)) {
     63                    list.push_back(innerItem);
     64                }
     65            } else {
     66                list.push_back(item);
     67            }
     68        }
     69        for (unsigned i = 1, run = 0; i < list.size(); ) {
     70            if (LLVM_UNLIKELY(list[i - 1] == list[i])) {
     71                ++run;
     72            } else if (LLVM_UNLIKELY(run != 0)) {
     73                // If we have a run of the same RE, make a bounded repetition for it
     74                const auto j = i - run; assert (j > 0);
     75                list[j - 1] = transform(makeRep(list[j - 1], run + 1, run + 1));
     76                list.erase(list.begin() + j, list.begin() + i);
     77                i = j;
     78                run = 0;
     79                continue;
     80            } else if (LLVM_UNLIKELY(isa<Rep>(list[i - 1]) && isa<Rep>(list[i]))){
     81                // If we have adjacent repetitions of the same RE, merge them
     82                Rep * const r1 = cast<Rep>(list[i - 1]);
     83                Rep * const r2 = cast<Rep>(list[i]);
     84                if (LLVM_UNLIKELY(r1->getRE() == r2->getRE())) {
     85                    list[i - 1] = transform(combineTwoReps(r1, r2));
     86                    list.erase(list.begin() + i);
    7987                    continue;
    80                 } else if (LLVM_UNLIKELY(isa<Rep>(list[i - 1]) && isa<Rep>(list[i]))){
    81                     // If we have adjacent repetitions of the same RE, merge them
    82                     Rep * const r1 = cast<Rep>(list[i - 1]);
    83                     Rep * const r2 = cast<Rep>(list[i]);
    84                     if (LLVM_UNLIKELY(r1->getRE() == r2->getRE())) {
    85                         list[i - 1] = memoize(combineTwoReps(r1, r2));
    86                         list.erase(list.begin() + i);
    87                         continue;
    88                     }
    89                 }
    90                 ++i;
    91             }
    92             re = makeSeq(list.begin(), list.end());
    93         } else if (Assertion * const a = dyn_cast<Assertion>(re)) {
    94             re = makeAssertion(minimize(a->getAsserted()), a->getKind(), a->getSense());
    95         } else if (Rep * const rep = dyn_cast<Rep>(re)) {
    96             re = makeRep(minimize(rep->getRE()), rep->getLB(), rep->getUB());
    97         } else if (Diff * const diff = dyn_cast<Diff>(re)) {
    98             re = makeDiff(minimize(diff->getLH()), minimize(diff->getRH()));
    99         } else if (Intersect * const ix = dyn_cast<Intersect>(re)) {
    100             re = makeIntersect(minimize(ix->getLH()), minimize(ix->getRH()));
    101         } else if (Name * const n = dyn_cast<Name>(re)) {
    102             RE * const def = n->getDefinition();
    103             if (LLVM_LIKELY(def != nullptr)) {
    104                 n->setDefinition(minimize(def));
    105             }
    106         }
    107         return memoize(re);
    108     }
     88                }
     89            }
     90            ++i;
     91        }
     92        if (unchanged(seq, list)) {
     93            return seq;
     94        } else {
     95            return makeSeq(list.begin(), list.end());
     96        }
     97    }
     98
     99    RE * transformName(Name * nm) override {
     100        nm->setDefinition(transform(nm->getDefinition()));
     101        return nm;
     102    }
     103
     104    PassContainer() : RE_Transformer("minimizer", NameTransformationMode::TransformDefinition) { }
    109105
    110106protected:
    111107
    112     void extractCommonPrefixes(Set & alts) {       
     108    void extractCommonPrefixes(Set & alts) {
    113109        if (LLVM_LIKELY(alts.size() > 1)) {
    114110            SmallVector<RE *, 8> optimized;
     
    137133                            if (LLVM_LIKELY(seq->size() > 1)) {
    138134                                assert (head == seq->front());
    139                                 tailSet.insert(memoize(makeSeq(seq->begin() + 1, seq->end())));
     135                                tailSet.insert(transform(tailOf(seq)));
    140136                                continue;
    141137                            }
     
    144140                            if (head != rep) {
    145141                                assert (head == rep->getRE());
    146                                 tailSet.insert(memoize(makeRepWithOneFewerRepitition(rep)));
     142                                tailSet.insert(transform(makeRepWithOneFewerRepitition(rep)));
    147143                                continue;
    148144                            }
     
    152148                    mCombine.clear();
    153149                    if (LLVM_UNLIKELY(nullable)) {
    154                         tailSet.insert(memoize(makeSeq()));
     150                        tailSet.insert(transform(makeSeq()));
    155151                    }
    156152                    RE * const tail = makeAlt(tailSet.begin(), tailSet.end());
    157                     optimized.push_back(minimize(makeSeq({ head, tail })));
     153                    optimized.push_back(transform(makeSeq({ head, tail })));
    158154                }
    159155            }
     
    189185                            if (LLVM_LIKELY(seq->size() > 1)) {
    190186                                assert (last == seq->back());
    191                                 initSet.insert(memoize(makeSeq(seq->begin(), seq->end() - 1)));
     187                                initSet.insert(transform(initOf(seq)));
    192188                                continue;
    193189                            }
     
    196192                            if (last != rep) {
    197193                                assert (last == rep->getRE());
    198                                 initSet.insert(memoize(makeRepWithOneFewerRepitition(rep)));
     194                                initSet.insert(transform(makeRepWithOneFewerRepitition(rep)));
    199195                                continue;
    200196                            }
     
    204200                    mCombine.clear();
    205201                    if (LLVM_UNLIKELY(nullable)) {
    206                         initSet.insert(memoize(makeSeq()));
     202                        initSet.insert(transform(makeSeq()));
    207203                    }
    208204                    RE * const init = makeAlt(initSet.begin(), initSet.end());
    209                     optimized.push_back(minimize(makeSeq({ init, last })));
     205                    optimized.push_back(transform(makeSeq({ init, last })));
    210206                }
    211207            }
     
    270266    }
    271267
     268    static RE * tailOf(Seq * const seq) {
     269        return makeSeq(seq->begin() + 1, seq->end());
     270    }
     271
    272272    static RE * lastOf(RE * const re) {
    273273        if (Seq * seq = dyn_cast<Seq>(re)) {
     
    283283    }
    284284
     285    static RE * initOf(Seq * const seq) {
     286        return makeSeq(seq->begin(), seq->end() - 1);
     287    }
     288
     289
     290    template <typename T>
     291    static bool unchanged(const Vector * A, const T & B) {
     292        if (A->size() != B.size()) {
     293            return false;
     294        }
     295        auto i = A->cbegin();
     296        for (const auto j : B) {
     297            if (*i != j) {
     298                return false;
     299            }
     300            ++i;
     301        }
     302        return true;
     303    }
     304
    285305    SmallVector<RE *, 16> mCombine;
    286306};
     
    289309RE * RE_Minimizer::minimize(RE * re) {
    290310    PassContainer pc;
    291     return pc.minimize(re);
     311    return pc.transformRE(re);
    292312}
    293313
  • icGREP/icgrep-devel/icgrep/re/re_multiplex.cpp

    r6170 r6173  
    1010#include <re/re_group.h>
    1111#include <re/re_analysis.h>
    12 #include <re/re_memoizer.hpp>
    1312#include <re/printer_re.h>
    1413#include <re/re_toolchain.h>
  • icGREP/icgrep-devel/icgrep/re/re_name.h

    r6159 r6173  
    4646    friend Name * makeZeroWidth(const std::string & name, RE * zerowidth);
    4747    friend Name * makeName(CC * const cc);
    48     friend Name * makeName(const std::string &, Type);
    49     friend Name * makeName(const std::string &, const std::string &, Type);
    50     friend Name * makeName(const std::string & nm, const Name::Type type, RE * defn);
     48    friend Name * makeName(const std::string &, Type, RE *);
     49    friend Name * makeName(const std::string &, const std::string &, Type, RE *);
    5150    Name(const char * nameSpace, const length_t namespaceLength, const char * name, const length_t nameLength, Type type, RE * defn)
    5251    : RE(ClassTypeId::Name)
     
    143142}
    144143
    145 inline Name * makeName(const std::string & name, const Name::Type type) {
    146     return new Name(nullptr, 0, name.c_str(), name.length(), type, nullptr);
     144inline Name * makeName(const std::string & name, const Name::Type type, RE * defn = nullptr) {
     145    return new Name(nullptr, 0, name.c_str(), name.length(), type, defn);
    147146}
    148147
    149 inline Name * makeName(const std::string & property, const std::string & value, const Name::Type type) {
    150     return new Name(property.c_str(), property.length(), value.c_str(), value.length(), type, nullptr);
    151 }
    152    
    153 inline Name * makeName(const std::string & nm, const Name::Type type, RE * defn) {
    154     return new Name(nullptr, 0, nm.c_str(), nm.length(), type, defn);
     148inline Name * makeName(const std::string & property, const std::string & value, const Name::Type type, RE * defn = nullptr) {
     149    return new Name(property.c_str(), property.length(), value.c_str(), value.length(), type, defn);
    155150}
    156151
  • icGREP/icgrep-devel/icgrep/re/re_name_gather.cpp

    r5887 r6173  
    1111#include <re/re_group.h>
    1212#include <re/re_analysis.h>
    13 #include <re/re_memoizer.hpp>
    1413#include <cc/alphabet.h>
    1514#include <UCD/ucd_compiler.hpp>
  • icGREP/icgrep-devel/icgrep/re/re_name_resolve.cpp

    r6170 r6173  
    1616#include <re/re_any.h>
    1717#include <re/re_toolchain.h>
    18 #include <re/re_memoizer.hpp>
    1918#include <UCD/resolve_properties.h>
    2019#include <cc/alphabet.h>
     
    2827namespace re {
    2928 
    30 class UnicodeNameResolver : public RE_Transformer {
     29class UnicodeNameResolver final : public RE_Transformer {
    3130public:
    3231    UnicodeNameResolver() : RE_Transformer("UnicodeNames") {}
    3332    RE * transformName(Name * name) override;
    34 private:
    35     Memoizer mMemoizer;
     33    RE * transformRange(Range * rg) override;
    3634};
    3735   
    3836RE * UnicodeNameResolver::transformName(Name * name) {
    39     auto f = mMemoizer.find(name);
    40     if (f == mMemoizer.end()) {
    41         if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
     37    if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
     38        name->setDefinition(transform(name->getDefinition()));
     39    } else if (LLVM_LIKELY(name->getType() == Name::Type::UnicodeProperty || name->getType() == Name::Type::ZeroWidth)) {
     40        if (UCD::resolvePropertyDefinition(name)) {
    4241            name->setDefinition(transform(name->getDefinition()));
    43         } else if (LLVM_LIKELY(name->getType() == Name::Type::UnicodeProperty || name->getType() == Name::Type::ZeroWidth)) {
    44             if (UCD::resolvePropertyDefinition(name)) {
    45                 name->setDefinition(transform(name->getDefinition()));
    46             } else {
    47                 name->setDefinition(makeCC(UCD::resolveUnicodeSet(name), &cc::Unicode));
    48             }
    4942        } else {
    50             UndefinedNameError(name);
     43            name->setDefinition(makeCC(UCD::resolveUnicodeSet(name), &cc::Unicode));
     44        }       
     45    } else {
     46        UndefinedNameError(name);
     47    }
     48    return name;
     49}
     50
     51RE * getDefinitionOf(RE * const re) {
     52    if (Name * const name = dyn_cast<Name>(re)) {
     53        RE * const def = name->getDefinition();
     54        if (LLVM_UNLIKELY(def == nullptr)) {
     55            llvm::report_fatal_error(name->getFullName() + " could not be resolved.");
    5156        }
    52         return mMemoizer.memoize(name);
    53     } else {
    54         return *f;
     57        return def;
    5558    }
     59    return re;
     60}
     61
     62RE * UnicodeNameResolver::transformRange(Range * rg) {
     63    RE * const x = getDefinitionOf(transform(rg->getLo()));
     64    RE * const y = getDefinitionOf(transform(rg->getHi()));
     65    return makeRange(x, y);
    5666}
    5767
     
    7383 
    7484AnchorResolution::AnchorResolution(RE * breakRE)
    75 : RE_Transformer() {
     85: RE_Transformer("Anchor Resolution") {
    7686    if (const CC * cc = dyn_cast<CC>(breakRE)) {
    7787        mIsNegated = true;
  • icGREP/icgrep-devel/icgrep/re/re_range.cpp

    r5814 r6173  
    99#include <re/re_name.h>
    1010#include <llvm/Support/Casting.h>
     11#include <llvm/Support/raw_ostream.h>
    1112#include <llvm/Support/ErrorHandling.h>
    1213
     
    1718RE * makeRange(RE * lo, RE * hi) {
    1819    if (isa<CC>(lo) && isa<CC>(hi)) {
    19         if (!((dyn_cast<CC>(lo)->count() == 1) && (dyn_cast<CC>(hi)->count() == 1)))
    20             llvm::report_fatal_error("invalid range operand");
    21         auto lo_val = dyn_cast<CC>(lo)->front().first;
    22         auto hi_val = dyn_cast<CC>(hi)->front().first;
    23         return makeCC(lo_val, hi_val, dyn_cast<CC>(hi)->getAlphabet());
     20        CC * const cc_lo = cast<CC>(lo);
     21        CC * const cc_hi = cast<CC>(hi);
     22        if (LLVM_LIKELY((cc_lo->count() == 1) && (cc_hi->count() == 1))) {
     23            const auto lo_val = cc_lo->at(0);
     24            const auto hi_val = cc_hi->at(0);
     25            if (LLVM_LIKELY(lo_val <= hi_val)) {
     26                return makeCC(lo_val, hi_val, dyn_cast<CC>(hi)->getAlphabet());
     27            }
     28        }
     29        std::string tmp;
     30        raw_string_ostream out(tmp);
     31        cc_lo->print(out);
     32        out << " to ";
     33        cc_hi->print(out);
     34        out << " are invalid range operands";
     35        report_fatal_error(out.str());
    2436    }
    2537    else if (isa<Name>(lo) && (cast<Name>(lo)->getDefinition() != nullptr)) {
  • icGREP/icgrep-devel/icgrep/re/re_range.h

    r6171 r6173  
    2424        return mHi;
    2525    }
     26
    2627protected:
    2728    friend RE * makeRange(RE*, RE*);
     
    3536    virtual ~Range() {}
    3637private:
    37     RE * mLo;
    38     RE * mHi;
     38    RE * const mLo;
     39    RE * const mHi;
    3940};
    4041
  • icGREP/icgrep-devel/icgrep/re/re_re.h

    r5765 r6173  
    1919    enum class ClassTypeId : unsigned {
    2020        Alt
    21         , Any
    2221        , Assertion
    2322        , CC
  • icGREP/icgrep-devel/icgrep/re/re_simplifier.cpp

    r5763 r6173  
    88#include <re/re_intersect.h>
    99#include <re/re_assertion.h>
    10 #include <re/re_memoizer.hpp>
     10#include <re/re_toolchain.h>
    1111#include <boost/container/flat_set.hpp>
    1212
     
    1818using List = std::vector<RE *>;
    1919
    20 struct PassContainer {
    21     RE * simplify(RE * re) {
    22         if (Alt * alt = dyn_cast<Alt>(re)) {
    23             Set set;
    24             set.reserve(alt->size());
    25             for (RE * item : *alt) {
    26                 item = simplify(item);
    27                 if (LLVM_UNLIKELY(isa<Alt>(item) && cast<Alt>(item)->empty())) {
    28                     continue;
     20struct PassContainer final : public RE_Transformer {
     21
     22    RE * transformAlt(Alt * alt) override {
     23        Set set;
     24        set.reserve(alt->size());
     25        for (RE * item : *alt) {
     26            item = transform(item);
     27            if (LLVM_UNLIKELY(isa<Alt>(item))) {
     28                for (RE * innerAlt : *cast<Alt>(item)) {
     29                    set.insert(innerAlt);
    2930                }
     31            }  else {
    3032                set.insert(item);
    3133            }
    32             re = makeAlt(set.begin(), set.end());
    33         } else if (Seq * seq = dyn_cast<Seq>(re)) {
    34             List list;
    35             list.reserve(seq->size());
    36             for (RE * item : *seq) {
    37                 item = simplify(item);
    38                 if (LLVM_UNLIKELY(isa<Seq>(item) && cast<Seq>(item)->empty())) {
    39                     continue;
    40                 }
    41                 list.push_back(item);
     34        }
     35        return makeAlt(set.begin(), set.end());
     36    }
     37
     38    RE * transformSeq(Seq * seq) override {
     39        List list;
     40        list.reserve(seq->size());
     41        for (RE * item : *seq) {
     42            item = transform(item);
     43            if (LLVM_UNLIKELY(isa<Vector>(item) && cast<Vector>(item)->empty())) {
     44                continue;
    4245            }
    43             re = makeSeq(list.begin(), list.end());
    44         } else if (Assertion * a = dyn_cast<Assertion>(re)) {
    45             re = makeAssertion(simplify(a->getAsserted()), a->getKind(), a->getSense());
    46         } else if (Rep * rep = dyn_cast<Rep>(re)) {
    47             RE * expr = simplify(rep->getRE());
    48             re = makeRep(expr, rep->getLB(), rep->getUB());
    49         } else if (Diff * diff = dyn_cast<Diff>(re)) {
    50             re = makeDiff(simplify(diff->getLH()), simplify(diff->getRH()));
    51         } else if (Range * rg = dyn_cast<Range>(re)) {
    52             re = makeRange(simplify(rg->getLo()), simplify(rg->getHi()));
    53         } else if (Intersect * e = dyn_cast<Intersect>(re)) {
    54             re = makeIntersect(simplify(e->getLH()), simplify(e->getRH()));
     46            list.push_back(item);
    5547        }
    56         return mMemoizer.memoize(re);
     48        return makeSeq(list.begin(), list.end());
    5749    }
    58 private:
    59     Memoizer mMemoizer;
     50
     51    RE * transformName(Name * nm) override {
     52        nm->setDefinition(transform(nm->getDefinition()));
     53        return nm;
     54    }
     55
     56    PassContainer() : RE_Transformer("Simplifier", NameTransformationMode::TransformDefinition) { }
     57
    6058};
    6159
    6260RE * RE_Simplifier::simplify(RE * re) {
    6361    PassContainer pc;
    64     return pc.simplify(re);
     62    return pc.transformRE(re);
    6563}
    6664
  • icGREP/icgrep-devel/icgrep/re/re_star_normal.cpp

    r6171 r6173  
    1818namespace re {
    1919
    20 RE * star_rule(RE * re) {
     20inline RE * star_rule(RE * re) {
    2121    if (Seq * seq = dyn_cast<Seq>(re)) {
    2222        if (isNullable(re)) {
  • icGREP/icgrep-devel/icgrep/re/re_toolchain.cpp

    r6171 r6173  
    107107        r = RE_Simplifier::simplify(r);
    108108    }
    109     if (PrintOptions.isSet(ShowAllREs) || PrintOptions.isSet(ShowSimplifiedREs)) {
    110         //Print to the terminal the AST that was generated by the simplifier.
    111         errs() << "Simplifier:\n" << Printer_RE::PrintRE(r) << '\n';
    112     }
    113 
    114109    if (!DefiniteLengthBackReferencesOnly(r)) {
    115110        llvm::report_fatal_error("Future back reference support: references must be within a fixed distance from a fixed-length capture.");
     
    117112    return r;
    118113}
     114
     115static bool compare(const RE * const lh, const RE * const rh);
     116
     117static bool lessThan(const Vector * const lh, const Vector * const rh) {
     118    assert (lh->getClassTypeId() == rh->getClassTypeId());
     119    assert (lh->getClassTypeId() == RE::ClassTypeId::Alt || lh->getClassTypeId() == RE::ClassTypeId::Seq);
     120    if (LLVM_LIKELY(lh->size() != rh->size())) {
     121        return lh->size() < rh->size();
     122    }
     123    for (auto i = lh->begin(), j = rh->begin(); i != lh->end(); ++i, ++j) {
     124        assert (*i && *j);
     125        if (compare(*i, *j)) {
     126            return true;
     127        } else if (compare(*j, *i)) {
     128            return false;
     129        }
     130    }
     131    return false;
     132}
     133
     134inline bool lessThan(const Name * const lh, const Name * const rh) {
     135    if (lh->getType() != rh->getType()) {
     136        return lh->getType() < rh->getType();
     137    } else if (lh->hasNamespace() != rh->hasNamespace()) {
     138        return lh->hasNamespace();
     139    } else if (lh->hasNamespace() && (lh->getNamespace() != rh->getNamespace())) {
     140        return lh->getNamespace() < rh->getNamespace();
     141    } else if (lh->getName() != rh->getName()) {
     142        return lh->getName() < rh->getName();
     143    } else if (lh->getDefinition() == nullptr) {
     144        return rh->getDefinition() != nullptr;
     145    } else if (rh->getDefinition() == nullptr) {
     146        return false;
     147    } else {
     148        return compare(lh->getDefinition(), rh->getDefinition());
     149    }
     150}
     151
     152inline bool lessThan(const Assertion * const lh, const Assertion * const rh) {
     153    if (lh->getKind() != rh->getKind()) {
     154        return lh->getKind() < rh->getKind();
     155    }
     156    if (lh->getSense() != rh->getSense()) {
     157        return lh->getSense() < rh->getSense();
     158    }
     159    return compare(lh->getAsserted(), rh->getAsserted());
     160}
     161
     162inline bool lessThan(const Rep * const lh, const Rep * const rh) {
     163    if (lh->getLB() != rh->getLB()) {
     164        return lh->getLB() < rh->getLB();
     165    }
     166    if (lh->getUB() != rh->getUB()) {
     167        return lh->getUB() < rh->getUB();
     168    }
     169    return compare(lh->getRE(), rh->getRE());
     170}
     171
     172inline bool lessThan(const Diff * const lh, const Diff * const rh) {
     173    if (compare(lh->getLH(), rh->getLH())) {
     174        return true;
     175    } else if (compare(rh->getLH(), lh->getLH())) {
     176        return false;
     177    } else if (compare(lh->getRH(), rh->getRH())) {
     178        return true;
     179    } else {
     180        return !compare(rh->getRH(), lh->getRH());
     181    }
     182}
     183
     184inline bool lessThan(const Range * const lh, const Range * const rh) {
     185    if (compare(lh->getLo(), rh->getLo())) {
     186        return true;
     187    } else if (compare(rh->getLo(), lh->getLo())) {
     188        return false;
     189    } else if (compare(lh->getHi(), rh->getHi())) {
     190        return true;
     191    } else {
     192        return !compare(rh->getHi(), lh->getHi());
     193    }
     194}
     195
     196static bool lessThan(const Intersect * const lh, const Intersect * const rh) {
     197    if (compare(lh->getLH(), rh->getLH())) {
     198        return true;
     199    } else if (compare(rh->getLH(), lh->getLH())) {
     200        return false;
     201    } else if (compare(lh->getRH(), rh->getRH())) {
     202        return true;
     203    } else {
     204        return !compare(rh->getRH(), lh->getRH());
     205    }
     206}
     207
     208inline bool lessThan(const Group * const lh, const Group * const rh) {
     209    if (lh->getMode() != rh->getMode()) {
     210        return lh->getMode() < rh->getMode();
     211    }
     212    if (lh->getSense() != rh->getSense()) {
     213        return lh->getSense() < rh->getSense();
     214    }
     215    return compare(lh->getRE(), rh->getRE());
     216}
     217
     218inline bool compare(const RE * const lh, const RE * const rh) {
     219    using Type = RE::ClassTypeId;
     220    assert (lh && rh);
     221    const auto typeL = lh->getClassTypeId();
     222    const auto typeR = rh->getClassTypeId();
     223    if (LLVM_LIKELY(typeL != typeR)) {
     224        return typeL < typeR;
     225    }
     226    switch (typeL) {
     227        case Type::Alt:
     228        case Type::Seq:
     229            return lessThan(cast<Vector>(lh), cast<Vector>(rh));
     230        case Type::End: case Type::Start:
     231            return false;
     232        case Type::Assertion:
     233            return lessThan(cast<Assertion>(lh), cast<Assertion>(rh));
     234        case Type::CC:
     235            return *cast<CC>(lh) < *cast<CC>(rh);
     236        case Type::Name:
     237            return lessThan(cast<Name>(lh), cast<Name>(rh));
     238        case Type::Group:
     239            return lessThan(cast<Group>(lh), cast<Group>(rh));
     240        case Type::Range:
     241            return lessThan(cast<Range>(lh), cast<Range>(rh));
     242        case Type::Diff:
     243            return lessThan(cast<Diff>(lh), cast<Diff>(rh));
     244        case Type::Intersect:
     245            return lessThan(cast<Intersect>(lh), cast<Intersect>(rh));
     246        case Type::Rep:
     247            return lessThan(cast<Rep>(lh), cast<Rep>(rh));
     248        default:
     249            llvm_unreachable("RE object of unknown type given to Memoizer");
     250            return false;
     251    }
     252}
     253
     254inline bool RE_Transformer::MemoizerComparator::operator()(const RE * const lh, const RE * const rh) const {
     255    return compare(lh, rh);
     256}
     257
    119258RE * RE_Transformer::transformRE(RE * re) {
    120259    RE * initialRE = re;
     
    126265}
    127266
    128 RE * RE_Transformer::transform(RE * re) {
    129     if (llvm::isa<CC>(re)) return transformCC(llvm::cast<CC>(re));
    130     else if (llvm::isa<Start>(re)) return transformStart(llvm::cast<Start>(re));
    131     else if (llvm::isa<End>(re)) return transformEnd(llvm::cast<End>(re));
    132     else if (llvm::isa<Name>(re)) return transformName(llvm::cast<Name>(re));
    133     else if (llvm::isa<Seq>(re)) return transformSeq(llvm::cast<Seq>(re));
    134     else if (llvm::isa<Alt>(re)) return transformAlt(llvm::cast<Alt>(re));
    135     else if (llvm::isa<Rep>(re)) return transformRep(llvm::cast<Rep>(re));
    136     else if (llvm::isa<Intersect>(re)) return transformIntersect(llvm::cast<Intersect>(re));
    137     else if (llvm::isa<Diff>(re)) return transformDiff(llvm::cast<Diff>(re));
    138     else if (llvm::isa<Range>(re)) return transformRange(llvm::cast<Range>(re));
    139     else if (llvm::isa<Group>(re)) return transformGroup(llvm::cast<Group>(re));
    140     else if (llvm::isa<Assertion>(re)) return transformAssertion(llvm::cast<Assertion>(re));
    141     else {
    142         llvm_unreachable("Unknown RE type");
    143         return nullptr;
    144     }
     267RE * RE_Transformer::transform(RE * const from) {
     268    assert (from);
     269    const auto f = mMap.find(from);
     270    if (f != mMap.end()) {
     271        return f->second;
     272    }
     273
     274    using T = RE::ClassTypeId;
     275    RE * to = from;
     276    #define TRANSFORM(Type) \
     277        case T::Type: to = transform##Type(llvm::cast<Type>(from)); break
     278    switch (from->getClassTypeId()) {
     279        TRANSFORM(Alt);
     280        TRANSFORM(Assertion);
     281        TRANSFORM(CC);
     282        TRANSFORM(Range);
     283        TRANSFORM(Diff);
     284        TRANSFORM(End);
     285        TRANSFORM(Intersect);
     286        TRANSFORM(Name);
     287        TRANSFORM(Group);
     288        TRANSFORM(Rep);
     289        TRANSFORM(Seq);
     290        TRANSFORM(Start);
     291        default: llvm_unreachable("Unknown RE type");
     292    }
     293    #undef TRANSFORM
     294    assert (to);
     295
     296    // Do we already have a memoized version of the transformed RE?
     297    if (from != to) {
     298        const auto f = mMap.find(to);
     299        if (LLVM_LIKELY(f == mMap.end())) {
     300            mMap.emplace(to, to);
     301        } else {
     302            to = f->second;
     303        }
     304    }
     305
     306    mMap.emplace(from, to);
     307
     308    return to;
    145309}
    146310
    147311RE * RE_Transformer::transformName(Name * nm) {
    148     if (mNameTransform == NameTransformationMode::None) return nm;
    149     RE * d = nm->getDefinition();
    150     if (d) return transform(d);
    151     UndefinedNameError(nm);
    152     return nullptr;
     312    if (mNameTransform == NameTransformationMode::None) {
     313        return nm;
     314    }
     315    RE * const d = nm->getDefinition();
     316    if (LLVM_UNLIKELY(d == nullptr)) {
     317        UndefinedNameError(nm);
     318    }
     319    return transform(d);
    153320}
    154321
     
    257424}
    258425
    259 }
     426inline bool RE_Inspector::MemoizerComparator::operator()(const RE * const lh, const RE * const rh) const {
     427    return compare(lh, rh);
     428}
     429
     430void RE_Inspector::inspectRE(RE * re) {
     431    inspect(re);
     432}
     433
     434void RE_Inspector::inspect(RE * const re) {
     435    assert (re);
     436    if (mIgnoreNonUnique == InspectionMode::IgnoreNonUnique) {
     437        if (mMap.count(re)) return;
     438        mMap.emplace(re);
     439    }
     440    using T = RE::ClassTypeId;
     441    #define INSPECT(Type) \
     442        case T::Type: inspect##Type(llvm::cast<Type>(re)); break
     443    switch (re->getClassTypeId()) {
     444        INSPECT(Alt);
     445        INSPECT(Assertion);
     446        INSPECT(CC);
     447        INSPECT(Range);
     448        INSPECT(Diff);
     449        INSPECT(End);
     450        INSPECT(Intersect);
     451        INSPECT(Name);
     452        INSPECT(Group);
     453        INSPECT(Rep);
     454        INSPECT(Seq);
     455        INSPECT(Start);
     456        default: llvm_unreachable("Unknown RE type");
     457    }
     458    #undef INSPECT
     459}
     460
     461void RE_Inspector::inspectName(Name * nm) {
     462    RE * const d = nm->getDefinition();
     463    if (d) inspect(d);
     464}
     465
     466void RE_Inspector::inspectCC(CC * cc) {
     467
     468}
     469
     470void RE_Inspector::inspectStart(Start * s) {
     471
     472}
     473
     474void RE_Inspector::inspectEnd(End * e) {
     475
     476}
     477
     478void RE_Inspector::inspectSeq(Seq * seq) {
     479    for (RE * e : *seq) {
     480        inspect(e);
     481    }
     482}
     483
     484void RE_Inspector::inspectAlt(Alt * alt) {
     485    for (RE * e : *alt) {
     486        inspect(e);
     487    }
     488}
     489
     490void RE_Inspector::inspectRep(Rep * r) {
     491    inspect(r->getRE());
     492}
     493
     494void RE_Inspector::inspectIntersect(Intersect * ix) {
     495    inspect(ix->getLH());
     496    inspect(ix->getRH());
     497}
     498
     499void RE_Inspector::inspectDiff(Diff * d) {
     500    inspect(d->getLH());
     501    inspect(d->getRH());
     502}
     503
     504void RE_Inspector::inspectRange(Range * rg) {
     505    inspect(rg->getLo());
     506    inspect(rg->getHi());
     507}
     508
     509void RE_Inspector::inspectGroup(Group * g) {
     510    inspect(g->getRE());
     511}
     512
     513void RE_Inspector::inspectAssertion(Assertion * a) {
     514    inspect(a->getAsserted());
     515}
     516
     517}
  • icGREP/icgrep-devel/icgrep/re/re_toolchain.h

    r6170 r6173  
    77#ifndef RE_TOOLCHAIN_H
    88#define RE_TOOLCHAIN_H
     9
     10#include <map>
     11#include <set>
    912#include <string>
    1013#include <llvm/Support/Compiler.h>
     14
    1115namespace llvm { namespace cl { class OptionCategory; } }
    1216namespace pablo { class PabloKernel; class PabloAST; }
     
    4044
    4145class RE_Transformer {
     46    struct MemoizerComparator {
     47        bool operator() (const RE * lh, const RE * rh) const;
     48    };
    4249public:
    43     RE_Transformer(std::string transformationName = "",
    44                    NameTransformationMode m = NameTransformationMode::None) :
    45     mTransformationName(transformationName), mNameTransform(m) {}
    4650    RE * transformRE(RE * r);
    4751protected:
     52    RE_Transformer(std::string transformationName, NameTransformationMode m = NameTransformationMode::None)
     53    : mTransformationName(std::move(transformationName)), mNameTransform(m) {}
     54
    4855    RE * transform(RE * r);
    4956    virtual RE * transformName(Name * n);
     
    5966    virtual RE * transformGroup(Group * g);
    6067    virtual RE * transformAssertion(Assertion * a);
    61    
    62     std::string mTransformationName;
    63     NameTransformationMode mNameTransform;
     68private:
     69    const std::string mTransformationName;
     70    const NameTransformationMode mNameTransform;
     71    std::map<RE *, RE *, MemoizerComparator> mMap;
     72};
     73
     74enum class InspectionMode {TraverseNonUnique, IgnoreNonUnique};
     75
     76class RE_Inspector {
     77    struct MemoizerComparator {
     78        bool operator() (const RE * lh, const RE * rh) const;
     79    };
     80public:
     81    void inspectRE(RE * r);
     82protected:
     83    RE_Inspector(const InspectionMode ignoreNonUnique = InspectionMode::IgnoreNonUnique) : mIgnoreNonUnique(ignoreNonUnique) {}
     84    void inspect(RE * r);
     85    virtual void inspectName(Name * n);
     86    virtual void inspectStart(Start * s);
     87    virtual void inspectEnd(End * e);
     88    virtual void inspectCC(CC * cc);
     89    virtual void inspectSeq(Seq * s);
     90    virtual void inspectAlt(Alt * a);
     91    virtual void inspectRep(Rep * rep);
     92    virtual void inspectIntersect(Intersect * e);
     93    virtual void inspectDiff(Diff * d);
     94    virtual void inspectRange(Range * rg);
     95    virtual void inspectGroup(Group * g);
     96    virtual void inspectAssertion(Assertion * a);
     97private:
     98    const InspectionMode mIgnoreNonUnique;
     99    std::set<RE *, MemoizerComparator> mMap;
    64100};
    65101
Note: See TracChangeset for help on using the changeset viewer.