Ignore:
Timestamp:
Jul 2, 2015, 9:28:21 AM (4 years ago)
Author:
nmedfort
Message:

Couple modifications to the UCD compiler. Splitting Multiplexing from BDD Minimization.

Location:
icGREP/icgrep-devel/icgrep/UCD
Files:
3 edited

Legend:

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

    r4627 r4629  
    4444        codepoint_t lo, hi;
    4545        std::tie(lo, hi) = range;
    46         if (rangeIntersect(set, lo, hi).empty()) {
    47             continue;
    48         }
    49         PabloBuilder inner_block = PabloBuilder::Create(block);
    50         PabloAST * inner_target = generateWithIfHierarchy(inner, set, lo, hi, inner_block);
    51         // If this range is empty, just skip creating the if block
    52         if (LLVM_UNLIKELY(isa<Zeroes>(inner_target))) {
    53             continue;
    54         }
    55         Assign * matches = inner_block.createAssign("m", inner_target);
    56         block.createIf(ifTestCompiler(lo, hi, block), {matches}, inner_block);
    57         target = block.createOr(target, matches);
     46        if (set.intersects(lo, hi)) {
     47            PabloBuilder inner_block = PabloBuilder::Create(block);
     48            PabloAST * inner_target = generateWithIfHierarchy(inner, set, lo, hi, inner_block);
     49            // If this range is empty, just skip creating the if block
     50            if (LLVM_UNLIKELY(isa<Zeroes>(inner_target))) {
     51                continue;
     52            }
     53            Assign * matches = inner_block.createAssign("m", inner_target);
     54            block.createIf(ifTestCompiler(lo, hi, block), {matches}, inner_block);
     55            target = block.createOr(target, matches);
     56        }
    5857    }
    5958
     
    129128                    }
    130129                    else { // we have a prefix group of type (a)
    131                         PabloAST * byteVar = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), block);
    132                         PabloAST * infix = byteVar;
     130                        PabloAST * var = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), block);
    133131                        if (byte_no > 1) {
    134                             infix = block.createAnd(block.createAdvance(prefix, 1), byteVar);
     132                            var = block.createAnd(block.createAdvance(prefix, 1), var);
    135133                        }
    136134                        PabloAST * suffixVar = mCharacterClassCompiler.compileCC(mSuffix, block);
    137135                        for (auto i = byte_no; i < UTF8_Encoder::length(lo); ++i) {
    138                             infix = block.createAnd(suffixVar, block.createAdvance(infix, 1));
     136                            var = block.createAnd(suffixVar, block.createAdvance(var, 1));
    139137                        }
    140                         target = block.createOr(target, infix);
     138                        target = block.createOr(target, var);
    141139                    }
    142140                }
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp

    r4627 r4629  
    149149    const auto e2 = other.quad_end();
    150150    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
    151         const auto run1 = i1.run();
    152         const auto run2 = i2.run();
    153         const auto n = std::min(lengthOf(run1), lengthOf(run2));
    154         if (typeOf(run1) == typeOf(run2) && typeOf(run1) != Mixed) {
    155             append_run(typeOf(run1), n, runs);
    156             i1 += n;
    157             i2 += n;
    158         }
    159         else if (typeOf(run1) == Full) {
     151        const auto n = std::min(i1.length(), i2.length());
     152        if (i1.type() == i2.type() && i1.type() != Mixed) {
     153            append_run(i1.type(), n, runs);
     154            i1 += n;
     155            i2 += n;
     156        }
     157        else if (i1.type() == Full) {
    160158            for (unsigned i = 0; i != n; ++i, ++i2) {
    161159                append_quad(i2.quad(), quads, runs);
     
    163161            i1 += n;
    164162        }
    165         else if (typeOf(run2) == Full) {
     163        else if (i2.type() == Full) {
    166164            for (unsigned i = 0; i != n; ++i, ++i1) {
    167165                append_quad(i1.quad(), quads, runs);
     
    189187    auto i1 = quad_begin(), i2 = other.quad_begin();
    190188    for (; i1 != e1 && i2 != e2; ) {
    191         const auto run1 = i1.run();
    192         const auto run2 = i2.run();
    193         const auto n = std::min(lengthOf(run1), lengthOf(run2));
    194         if ((typeOf(run1) == Empty) && (typeOf(run2) == Empty)) {
     189        const auto n = std::min(i1.length(), i2.length());
     190        if ((i1.type() == Empty) && (i2.type() == Empty)) {
    195191            append_run(Empty, n, runs);
    196192            i1 += n;
    197193            i2 += n;
    198194        }
    199         else if ((typeOf(run1) == Full) || (typeOf(run2) == Full)) {
     195        else if ((i1.type() == Full) || (i2.type() == Full)) {
    200196            append_run(Full, n, runs);
    201197            i1 += n;
    202198            i2 += n;
    203199        }
    204         else if (typeOf(run1) == Empty) {
     200        else if (i1.type() == Empty) {
    205201            for (unsigned i = 0; i != n; ++i, ++i2) {
    206202                append_quad(i2.quad(), quads, runs);
     
    208204            i1 += n;
    209205        }
    210         else if (typeOf(run2) == Empty) {
     206        else if (i2.type() == Empty) {
    211207            for (unsigned i = 0; i != n; ++i, ++i1) {
    212208                append_quad(i1.quad(), quads, runs);
     
    233229    const auto e2 = other.quad_end();
    234230    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
    235         const auto run1 = i1.run();
    236         const auto run2 = i2.run();
    237         unsigned n = std::min(lengthOf(run1), lengthOf(run2));
    238         if ((typeOf(run1) == Empty) || (typeOf(run2) == Full) || (typeOf(run1) == Full && typeOf(run2) == Empty)) {
    239             append_run(typeOf(run1), n, runs);
    240             i1 += n;
    241             i2 += n;
    242         }
    243         else if (typeOf(run1) == Full) {
     231        unsigned n = std::min(i1.length(), i2.length());
     232        if ((i1.type() == Empty) || (i2.type() == Full) || (i1.type() == Full && i2.type() == Empty)) {
     233            append_run(i1.type(), n, runs);
     234            i1 += n;
     235            i2 += n;
     236        }
     237        else if (i1.type() == Full) {
    244238            for (unsigned i = 0; i != n; ++i, ++i2) {
    245239                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
     
    247241            i1 += n;
    248242        }
    249         else if (typeOf(run2) == Empty) {
     243        else if (i2.type() == Empty) {
    250244            for (unsigned i = 0; i != n; ++i, ++i1) {
    251245                append_quad(i1.quad(), quads, runs);
     
    272266    const auto e2 = other.quad_end();
    273267    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
    274         const auto run1 = i1.run();
    275         const auto run2 = i2.run();
    276         unsigned n = std::min(lengthOf(run1), lengthOf(run2));
    277         if (typeOf(run1) != Mixed && typeOf(run2) != Mixed) {
    278             append_run(typeOf(run1) == typeOf(run2) ? Empty : Full, n, runs);
    279             i1 += n;
    280             i2 += n;
    281         }
    282         else if (typeOf(run1) == Empty) {
     268        unsigned n = std::min(i1.length(), i2.length());
     269        if (i1.type() != Mixed && i2.type() != Mixed) {
     270            append_run(i1.type() == i2.type() ? Empty : Full, n, runs);
     271            i1 += n;
     272            i2 += n;
     273        }
     274        else if (i1.type() == Empty) {
    283275            for (unsigned i = 0; i < n; ++i, ++i2) {
    284276                append_quad(i2.quad(), quads, runs);
     
    286278            i1 += n;
    287279        }
    288         else if (typeOf(run2) == Empty) {
     280        else if (i2.type() == Empty) {
    289281            for (unsigned i = 0; i < n; ++i, ++i1) {
    290282                append_quad(i1.quad(), quads, runs);
     
    292284            i2 += n;
    293285        }
    294         else if (typeOf(run1) == Full) {
     286        else if (i1.type() == Full) {
    295287            for (unsigned i = 0; i < n; ++i, ++i2) {
    296288                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
     
    298290            i1 += n;
    299291        }
    300         else if (typeOf(run2) == Empty) {
     292        else if (i2.type() == Empty) {
    301293            for (unsigned i = 0; i < n; ++i, ++i1) {
    302294                append_quad(FULL_QUAD_MASK ^ i1.quad(), quads, runs);
     
    338330bool UnicodeSet::contains(const codepoint_t codepoint) const {
    339331    auto n = codepoint / QUAD_BITS;
    340     QuadVector::const_iterator qi = mQuads.cbegin();
     332    auto qi = mQuads.cbegin();
    341333    for (const auto & r : mRuns) {
    342334        if (lengthOf(r) >= n) {
     
    348340        }
    349341        if (typeOf(r) == Mixed) {
    350             qi += n;
     342            qi += lengthOf(r);
    351343        }       
    352344        n -= lengthOf(r);
    353345    }
    354346    return false;
     347}
     348
     349/** ------------------------------------------------------------------------------------------------------------- *
     350 * @brief intersects
     351 * @param lo_codepoint
     352 * @param hi_codepoint
     353 *
     354 * Return true if this UnicodeSet contains any code point(s) between lo_codepoint and hi_codepoint
     355 ** ------------------------------------------------------------------------------------------------------------- */
     356bool UnicodeSet::intersects(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) const {
     357    quad_iterator qi = quad_begin() + lo_codepoint / QUAD_BITS;
     358    unsigned n = (hi_codepoint - lo_codepoint) / QUAD_BITS;
     359    while (n) {
     360        if (qi.type() != Empty) {
     361            return true;
     362        }
     363        const auto l = std::min<unsigned>(qi.length(), n);
     364        qi += l;
     365        n -= l;
     366    }
     367    // check the remaining portion of this quad
     368    unsigned r = (hi_codepoint - lo_codepoint) % QUAD_BITS;
     369    if (r == 0 || (++qi).type() == Empty) {
     370        return false;
     371    }
     372    if (qi.type() == Full) {
     373        return true;
     374    }
     375    return (qi.quad() & (FULL_QUAD_MASK << r)) != 0;
    355376}
    356377
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.h

    r4627 r4629  
    104104
    105105        inline quad_iterator_return_t dereference() const {
    106             return std::make_pair(run(), quad());
     106            return std::make_pair(std::make_pair(type(), length()), quad());
    107107        }
    108108
     
    111111        }
    112112
    113         inline run_t run() const {
    114             return std::make_pair(std::get<0>(*mRunIterator), std::get<1>(*mRunIterator) - mOffset);
     113        inline run_type_t type() const {
     114            return std::get<0>(*mRunIterator);
     115        }
     116
     117        inline length_t length() const {
     118            return std::get<1>(*mRunIterator) - mOffset;
    115119        }
    116120
     
    138142
    139143    bool contains(const codepoint_t codepoint) const;
     144
     145    bool intersects(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) const;
    140146
    141147    void dump(llvm::raw_ostream & out) const;
Note: See TracChangeset for help on using the changeset viewer.