Changeset 4860


Ignore:
Timestamp:
Nov 5, 2015, 4:41:37 PM (3 years ago)
Author:
nmedfort
Message:

Back up check in. Memory leaks should be fixed.

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

Legend:

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

    r4841 r4860  
    229229            // We have a single byte remaining to match for all code points in this CC.
    230230            // Use the byte class compiler to generate matches for these codepoints.
    231             const auto bytes = byteDefinitions(ranges, byte_no);
    232             PabloAST * var = mCharacterClassCompiler.compileCC(makeCC(bytes), builder);
     231            PabloAST * var = mCharacterClassCompiler.compileCC(makeCC(byteDefinitions(ranges, byte_no)), builder);
    233232            if (byte_no > 1) {
    234233                var = builder.createAnd(var, builder.createAdvance(makePrefix(lo, byte_no, builder, prefix), 1));
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp

    r4850 r4860  
    2424#include <llvm/Support/Format.h>
    2525#include <include/simd-lib/builtins.hpp>
    26 #include <iostream>
     26#include <array>
    2727
    2828namespace UCD {
     
    3030using bitquad_t = UnicodeSet::bitquad_t;
    3131using run_t = UnicodeSet::run_t;
    32 using RunVector = UnicodeSet::RunVector;
    33 using QuadVector = UnicodeSet::QuadVector;
     32using interval_t = UnicodeSet::interval_t;
     33using codepoint_t = UnicodeSet::codepoint_t;
     34
     35UnicodeSet::Allocator UnicodeSet::mAllocator;
    3436
    3537const size_t QUAD_BITS = (8 * sizeof(bitquad_t));
     
    4951 * @brief append_run
    5052 ** ------------------------------------------------------------------------------------------------------------- */
     53template <class RunVector>
    5154inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) {
    5255    if (LLVM_UNLIKELY(length == 0)) {
    5356        return;
    54     }
    55     else if (!runs.empty() && typeOf(runs.back()) == type) {
     57    } else if (!runs.empty() && typeOf(runs.back()) == type) {
    5658        std::get<1>(runs.back()) += length;
    5759        return;
     
    6365 * @brief append_quad
    6466 ** ------------------------------------------------------------------------------------------------------------- */
     67template <class QuadVector, class RunVector>
    6568inline void append_quad(const bitquad_t quad, QuadVector & quads, RunVector & runs) {
    6669    run_type_t type = Empty;
    6770    if (LLVM_UNLIKELY(quad == 0)) {
    6871        type = Empty;
    69     }
    70     else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
     72    } else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
    7173        type = Full;
    72     }
    73     else {
     74    } else {
    7475        quads.emplace_back(quad);
    7576        type = Mixed;
     
    8081#ifndef NDEBUG
    8182/** ------------------------------------------------------------------------------------------------------------- *
    82  * @brief runLengthSumsUpToUnicodeQuadCount
     83 * @brief verify
    8384 *
    84  * Sanity check for each function that constructs a new UnicodeSet
    85  ** ------------------------------------------------------------------------------------------------------------- */
    86 inline bool runLengthSumsUpToUnicodeQuadCount(const RunVector & runs) {
     85 * Sanity check for each function that constructs or modifies a UnicodeSet
     86 ** ------------------------------------------------------------------------------------------------------------- */
     87template <class RunVector, class QuadVector>
     88inline bool verify(const RunVector & runs, const QuadVector & quads) {
    8789    unsigned sum = 0;
    88     for (auto & run : runs) {
    89         sum += lengthOf(run);
    90     }
    91     return sum == UNICODE_QUAD_COUNT;
     90    unsigned mixedQuads = 0;
     91    for (auto run : runs) {
     92        const auto l = lengthOf(run);
     93        if (l == 0) {
     94            throw std::runtime_error("Zero-length quad found!");
     95        }
     96        if (typeOf(run) == Mixed) {
     97            mixedQuads += l;
     98        }
     99        sum += l;
     100    }
     101    if (sum != UNICODE_QUAD_COUNT) {
     102        throw std::runtime_error("Invalid quad count: found " + std::to_string(sum) + " but expected " + std::to_string(UNICODE_QUAD_COUNT));
     103    }
     104    if (mixedQuads != quads.size()) {
     105        throw std::runtime_error("Invalid mixed quad count: found " + std::to_string(quads.size()) + " but expected " + std::to_string(mixedQuads));
     106    }
     107    for (auto quad : quads) {
     108        if (quad == 0) {
     109            throw std::runtime_error("Empty quad found in Mixed quad array!");
     110        } else if (quad == FULL_QUAD_MASK) {
     111            throw std::runtime_error("Full quad found in Mixed quad array!");
     112        }
     113    }
     114    return true;
    92115}
    93116#endif
     
    148171 ** ------------------------------------------------------------------------------------------------------------- */
    149172UnicodeSet UnicodeSet::operator~() const {
    150     RunVector runs;
    151     QuadVector quads;
     173    std::vector<run_t> runs;
     174    std::vector<bitquad_t> quads;
    152175    runs.reserve(mRuns.size());
    153176    quads.reserve(mQuads.size());
     
    167190        }
    168191    }
    169     assert (runLengthSumsUpToUnicodeQuadCount(runs));
    170192    return UnicodeSet(std::move(runs), std::move(quads));
    171193}
     
    175197 ** ------------------------------------------------------------------------------------------------------------- */
    176198UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
    177     RunVector runs;
    178     QuadVector quads;
     199    std::vector<run_t> runs;
     200    std::vector<bitquad_t> quads;
    179201    const auto e1 = quad_end();
    180202    const auto e2 = other.quad_end();
     
    209231        }
    210232    }
    211     assert (runLengthSumsUpToUnicodeQuadCount(runs));
    212233    return UnicodeSet(std::move(runs), std::move(quads));
    213234}
     
    217238 ** ------------------------------------------------------------------------------------------------------------- */
    218239UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
    219     RunVector runs;
    220     QuadVector quads;
     240    std::vector<run_t> runs;
     241    std::vector<bitquad_t> quads;
    221242    const auto e1 = quad_end();
    222243    const auto e2 = other.quad_end();
     
    228249            i1 += n;
    229250            i2 += n;
    230         }
    231         else if ((i1.type() == Full) || (i2.type() == Full)) {
     251        } else if ((i1.type() == Full) || (i2.type() == Full)) {
    232252            append_run(Full, n, runs);
    233253            i1 += n;
    234254            i2 += n;
    235         }
    236         else if (i1.type() == Empty) {
     255        } else if (i1.type() == Empty) {
    237256            for (unsigned i = 0; i != n; ++i, ++i2) {
    238257                append_quad(i2.quad(), quads, runs);
    239258            }
    240259            i1 += n;
    241         }
    242         else if (i2.type() == Empty) {
     260        } else if (i2.type() == Empty) {
    243261            for (unsigned i = 0; i != n; ++i, ++i1) {
    244262                append_quad(i1.quad(), quads, runs);
    245263            }
    246264            i2 += n;
    247         }
    248         else {
     265        } else {
    249266            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
    250267                append_quad(i1.quad() | i2.quad(), quads, runs);
     
    252269        }
    253270    }
    254     assert (runLengthSumsUpToUnicodeQuadCount(runs));
    255271    return UnicodeSet(std::move(runs), std::move(quads));
    256272}
     
    260276 ** ------------------------------------------------------------------------------------------------------------- */
    261277UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
    262     RunVector runs;
    263     QuadVector quads;
     278    std::vector<run_t> runs;
     279    std::vector<bitquad_t> quads;
    264280    const auto e1 = quad_end();
    265281    const auto e2 = other.quad_end();
     
    289305        }
    290306    }
    291     assert (runLengthSumsUpToUnicodeQuadCount(runs));
    292307    return UnicodeSet(std::move(runs), std::move(quads));
    293308}
     
    297312 ** ------------------------------------------------------------------------------------------------------------- */
    298313UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
    299     RunVector runs;
    300     QuadVector quads;
     314    std::vector<run_t> runs;
     315    std::vector<bitquad_t> quads;
    301316    const auto e1 = quad_end();
    302317    const auto e2 = other.quad_end();
     
    338353        }
    339354    }
    340     assert (runLengthSumsUpToUnicodeQuadCount(runs));
    341355    return UnicodeSet(std::move(runs), std::move(quads));
    342356}
     
    385399}
    386400
    387 ///** ------------------------------------------------------------------------------------------------------------- *
    388 // * @brief insert_range
    389 // ** ------------------------------------------------------------------------------------------------------------- */
    390 //void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi)  {
    391 
    392 //    if (LLVM_UNLIKELY(lo > hi)) {
    393 //        throw std::runtime_error('[' + std::to_string(lo) + ',' + std::to_string(hi) + "] is an illegal codepoint range!");
    394 //    } else if (LLVM_UNLIKELY(hi >= 0x110000)) {
    395 //        throw std::runtime_error(std::to_string(hi) + " exceeds maximum code point.");
    396 //    }
    397 
    398 //    auto r = mRuns.begin();
    399 //    auto q = mQuads.begin();
    400 //    unsigned offset = 0;
    401 
    402 //    auto lo_quad_no = lo / QUAD_BITS;
    403 //    auto lo_offset = lo & MOD_QUAD_BIT_MASK;
    404 
    405 //    auto hi_quad_no = hi / QUAD_BITS;
    406 //    auto hi_offset = hi & MOD_QUAD_BIT_MASK;
    407 
    408 //    // Scan up to the lo codepoint
    409 //    for (;;) {
    410 //        assert (r != mRuns.end());
    411 //        const auto l = lengthOf(*r);
    412 //        if ((offset + l) > lo_quad_no) {
    413 //            break;
    414 //        }
    415 //        if (typeOf(*r) == Mixed) {
    416 //            q += lengthOf(*r);
    417 //        }
    418 //        offset += l;
    419 //        ++r;
    420 //    }
    421 
    422 //    // Test whether the range is already 'full' and skip ahead to the first empty or mixed quad.
    423 //    // If the entire [lo,hi] range is already covered by a Full run, abort.
    424 //    while (typeOf(*r) == Full) {
    425 //        const auto l = lengthOf(*r);
    426 //        lo_quad_no += l;
    427 //        offset = lo_quad_no;
    428 //        lo_offset = 0;
    429 //        if (lo_quad_no > hi_quad_no) {
    430 //            return;
    431 //        }
    432 //        ++r;
    433 //    }
    434 
    435 //    // Otherwise, some portion of this range has to be inserted into the current sparse set.
    436 //    // Begin by inserting the initial (potentially) partial lo quad.
    437 //    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
    438 //    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
    439 //    bitquad_t quad = (lo_quad_no == hi_quad_no) ? (lo_quad & hi_quad) : lo_quad;
    440 //    run_type_t newType = (quad == FULL_QUAD_MASK) ? Full : ((quad == 0) ? Empty : Mixed);
    441 //    run_type_t runType = typeOf(*r);
    442 //    // If the original run is Mixed, we may be able to simply update the quad accordingly.
    443 //    if (runType == Mixed) {
    444 //        q += (lo_quad_no - offset);
    445 //        quad |= *q;
    446 //        if (LLVM_LIKELY(quad != FULL_QUAD_MASK)) {
    447 //            *q = quad;
    448 //            if (lo_quad_no == hi_quad_no) {
    449 //                return;
    450 //            }
    451 //        } else { // we filled a Mixed quad
    452 //            mQuads.erase(q);
    453 //        }
    454 //        newType = Full;
    455 //    }
    456 //    auto length = lengthOf(*r);
    457 //    auto splitAt = length - (lo_quad_no - offset) - 1;
    458 //    if (splitAt) {
    459 //        // reduce the original run length
    460 //        lengthOf(*r) = splitAt;
    461 //        // and add in a new quad
    462 //        r = mRuns.emplace(r, newType, 1);
    463 //    } else { // we're inserting this quad at the beginning of the run
    464 //        typeOf(*r) = newType;
    465 //        lengthOf(*r) = 1;
    466 //    }
    467 //    if (newType == Mixed) {
    468 //        q = mQuads.emplace(q, quad);
    469 //    }
    470 //    length -= splitAt + 1;
    471 //    auto remaining = (hi_quad_no - lo_quad_no);
    472 //    // We're inserting a Full run so if the original run type was Full and exceeds the
    473 //    // length of what we're inserting, we can abort without considering the hi_quad
    474 //    if (runType == Full && length > remaining) {
    475 //        return;
    476 //    }
    477 //    if (remaining) {
    478 //        r = mRuns.emplace(r, Full, remaining);
    479 
    480 
    481 
    482 //    }
    483 
    484 //}
    485 
    486 
     401/** ------------------------------------------------------------------------------------------------------------- *
     402 * @brief insert
     403 ** ------------------------------------------------------------------------------------------------------------- */
     404void UnicodeSet::insert(const codepoint_t cp) {
     405
     406    if (LLVM_UNLIKELY(cp >= UNICODE_MAX)) {
     407        throw std::runtime_error(std::to_string(cp) + " exceeds maximum code point.");
     408    }
     409
     410    codepoint_t offset = cp / QUAD_BITS;
     411    const bitquad_t value = static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK);
     412    auto run = mRuns.begin();
     413    auto quad = mQuads.begin();
     414    length_t l = 0;
     415    run_type_t t = Empty;
     416    for (;;) {
     417        std::tie(t, l) = *run;
     418        if (offset < l) {
     419            break;
     420        }
     421        if (t == Mixed) {
     422            quad += l;
     423        }
     424        offset -= l;
     425        ++run;
     426    }
     427    if (LLVM_LIKELY(t == Mixed)) {
     428        quad += offset;
     429        *quad |= value;
     430        if (LLVM_LIKELY(*quad != FULL_QUAD_MASK)) {
     431            assert (contains(cp));
     432            return;
     433        }
     434        mQuads.erase(quad);
     435    } else if (t == Empty) {
     436        mQuads.insert(quad, value);
     437    } else { // if (t == Full) {
     438        assert (contains(cp));
     439        return;
     440    }
     441    const unsigned remaining = l - (offset + 1);
     442    if (offset == 0) {
     443        *run = std::make_pair(t == Empty ? Mixed : Full, 1);
     444        if (remaining != 0) {
     445            mRuns.insert(++run, std::make_pair(t, remaining));
     446        }
     447    } else {
     448        run->second = offset;
     449        if (remaining == 0) {
     450            mRuns.insert(++run, std::make_pair(t == Empty ? Mixed : Full, 1));
     451        } else {
     452            mRuns.insert(++run, {std::make_pair(t == Empty ? Mixed : Full, 1), std::make_pair(t, remaining)});
     453        }
     454    }
     455
     456    assert (verify(mRuns, mQuads));
     457    assert (contains(cp));
     458}
     459
     460/** ------------------------------------------------------------------------------------------------------------- *
     461 * @brief insert_range
     462 ** ------------------------------------------------------------------------------------------------------------- */
     463void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi)  {
     464
     465    if (LLVM_UNLIKELY(lo > hi)) {
     466        throw std::runtime_error('[' + std::to_string(lo) + ',' + std::to_string(hi) + "] is an illegal codepoint range!");
     467    } else if (LLVM_UNLIKELY(hi > UNICODE_MAX)) {
     468        throw std::runtime_error(std::to_string(hi) + " exceeds maximum code point.");
     469    }
     470
     471    // Create a temporary run and quad set for the given range
     472    std::vector<run_t> runs;
     473    std::vector<bitquad_t> quads;
     474
     475    codepoint_t lo_index = lo / QUAD_BITS;
     476    codepoint_t hi_index = hi / QUAD_BITS;
     477
     478    auto ri = mRuns.cbegin();
     479    auto qi = mQuads.cbegin();
     480
     481    length_t length = 0;
     482    run_type_t type = Empty;
     483    // Advance past any full runs prior to the lo_index
     484    for (;;) {
     485        std::tie(type, length) = *ri;
     486        if (lo_index < length) {
     487            break;
     488        }
     489        if (type == Mixed) {
     490            qi += length;
     491        }
     492        lo_index -= length;
     493        hi_index -= length;
     494        ++ri;
     495    }
     496
     497    // Now record the runs and any quads prior to lo_index
     498    runs.assign(mRuns.cbegin(), ri);
     499    if (lo_index) {
     500        runs.push_back(std::make_pair(type, lo_index));
     501        if (type == Mixed) {
     502            qi += lo_index;
     503        }
     504        hi_index -= lo_index;
     505        length -= lo_index;
     506    }
     507
     508    quads.assign(mQuads.cbegin(), qi);
     509    // We now have everything up to the first quad added to our temporary buffers; merge in the first new quad.
     510    bitquad_t lo_quad = (FULL_QUAD_MASK << (lo & MOD_QUAD_BIT_MASK));
     511    bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - (hi & MOD_QUAD_BIT_MASK)));
     512
     513    // If our original quad is full, just append a Full run
     514    if (LLVM_UNLIKELY(type == Full)) {
     515        append_run(Full, 1, runs);
     516    } else { // Otherwise merge the new quad value with the original one
     517        if (hi_index == 0) {
     518            lo_quad &= hi_quad;
     519        }
     520        if (type == Mixed) {
     521            lo_quad |= *qi++;
     522        }
     523        append_quad(lo_quad, quads, runs);
     524    }
     525    --length;
     526
     527    // Now check if we need to write out any Full blocks between the lo and hi code points; adjust our position
     528    // in the original quad to suit.
     529    if (hi_index) {
     530        // Add in any full runs between the lo and hi quads
     531        append_run(Full, hi_index - 1, runs);
     532        // Advance past original quads that were filled in
     533        for (;;) {
     534            if (type == Mixed) {
     535                qi += length;
     536            }
     537            std::tie(type, length) = *++ri;
     538            if (hi_index < length) {
     539                break;
     540            }
     541            hi_index -= length;
     542        }
     543
     544        // Write out the hi_quad value
     545        if (LLVM_UNLIKELY(type == Full)) {
     546            append_run(Full, 1, runs);
     547        } else {
     548            if (type == Mixed) {
     549                qi += hi_index;
     550                hi_quad |= *qi++;
     551            }
     552            append_quad(hi_quad, quads, runs);
     553        }
     554    }
     555
     556    // And append any remaining values from the original data
     557    append_run(type, length - hi_index, runs);
     558    runs.insert(runs.end(), ++ri, mRuns.cend());
     559    quads.insert(quads.end(), qi, mQuads.cend());
     560
     561    assert (verify(runs, quads));
     562
     563    mRuns.assign(runs.cbegin(), runs.cend());
     564    mQuads.assign(quads.cbegin(), quads.cend());
     565}
    487566
    488567/** ------------------------------------------------------------------------------------------------------------- *
     
    492571 * Return whether this UnicodeSet contains the specified code point
    493572 ** ------------------------------------------------------------------------------------------------------------- */
    494 bool UnicodeSet::contains(const codepoint_t codepoint) const {
    495     auto n = codepoint / QUAD_BITS;
    496     auto qi = mQuads.cbegin();
    497     for (const auto & r : mRuns) {
    498         if (lengthOf(r) >= n) {
    499             if (typeOf(r) == Mixed) {
    500                 qi += n - 1;
    501                 return (*qi & (static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK))) != 0;
    502             }
    503             return (typeOf(r) == Full);
    504         }
    505         if (typeOf(r) == Mixed) {
    506             qi += lengthOf(r);
     573bool UnicodeSet::contains(const codepoint_t cp) const {
     574    codepoint_t offset = cp / QUAD_BITS;
     575    auto quad = mQuads.cbegin();
     576    for (const auto r : mRuns) {
     577        length_t l = 0;
     578        run_type_t t = Empty;
     579        std::tie(t, l) = r;
     580        if (offset < l) {
     581            if (t == Mixed) {
     582                quad += offset;
     583                return (*quad & static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK)) != 0;
     584            }
     585            return (t == Full);
     586        }
     587        if (t == Mixed) {
     588            quad += l;
    507589        }       
    508         n -= lengthOf(r);
     590        offset -= l;
    509591    }
    510592    return false;
     
    659741 * @brief Empty Set Constructor
    660742 ** ------------------------------------------------------------------------------------------------------------- */
    661 UnicodeSet::UnicodeSet() : mRuns({{{Empty, UNICODE_QUAD_COUNT}}}) { }
     743UnicodeSet::UnicodeSet()
     744: mRuns({{{Empty, UNICODE_QUAD_COUNT}}}, reinterpret_cast<RunAllocator &>(mAllocator))
     745, mQuads(reinterpret_cast<QuadAllocator &>(mAllocator))
     746{
     747    assert (verify(mRuns, mQuads));
     748}
    662749
    663750/** ------------------------------------------------------------------------------------------------------------- *
    664751 * @brief Singleton Set Constructor
    665752 ** ------------------------------------------------------------------------------------------------------------- */
    666 UnicodeSet::UnicodeSet(const codepoint_t codepoint) {
     753UnicodeSet::UnicodeSet(const codepoint_t codepoint)
     754: mRuns(reinterpret_cast<RunAllocator &>(mAllocator))
     755, mQuads(reinterpret_cast<QuadAllocator &>(mAllocator))
     756{
    667757    const codepoint_t quad_no = codepoint / QUAD_BITS;
    668     if (quad_no > 0) {
    669         append_run(Empty, quad_no, mRuns);
    670     }
     758    append_run(Empty, quad_no, mRuns);
    671759    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
    672     if (quad_no < UNICODE_QUAD_COUNT - 1) {
    673         append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
    674     }
    675     assert (runLengthSumsUpToUnicodeQuadCount(mRuns));
     760    append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
     761    assert (verify(mRuns, mQuads));
    676762}
    677763
     
    679765 * @brief Range Set Constructor
    680766 ** ------------------------------------------------------------------------------------------------------------- */
    681 UnicodeSet::UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) {
    682     const codepoint_t lo_quad_no = lo_codepoint / QUAD_BITS;
    683     const codepoint_t hi_quad_no = hi_codepoint / QUAD_BITS;
    684     const codepoint_t lo_offset = lo_codepoint & MOD_QUAD_BIT_MASK;
    685     const codepoint_t hi_offset = hi_codepoint & MOD_QUAD_BIT_MASK;
     767UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi)
     768: mRuns(reinterpret_cast<RunAllocator &>(mAllocator))
     769, mQuads(reinterpret_cast<QuadAllocator &>(mAllocator))
     770{
     771    const codepoint_t lo_index = lo / QUAD_BITS;
     772    const codepoint_t hi_index = hi / QUAD_BITS;
     773    const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
     774    const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
    686775    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
    687776    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
    688     append_run(Empty, lo_quad_no, mRuns);
    689     if (lo_quad_no == hi_quad_no) {       
    690         append_quad(lo_quad & hi_quad, mQuads, mRuns);
    691     }
    692     else {
     777    append_run(Empty, lo_index, mRuns);
     778    bitquad_t mask = hi_quad;
     779    if (lo_index == hi_index) {
     780        mask &= lo_quad;
     781    } else {
    693782        append_quad(lo_quad, mQuads, mRuns);
    694         append_run(Full, hi_quad_no - (lo_quad_no + 1), mRuns);
    695         append_quad(hi_quad, mQuads, mRuns);
    696     }
    697     if (hi_quad_no < UNICODE_QUAD_COUNT - 1) {
    698         append_run(Empty, UNICODE_QUAD_COUNT - (hi_quad_no + 1), mRuns);
    699     }
    700     assert (runLengthSumsUpToUnicodeQuadCount(mRuns));
    701 }
    702 
    703 }
     783        append_run(Full, hi_index - (lo_index + 1), mRuns);
     784    }
     785    append_quad(mask, mQuads, mRuns);
     786    append_run(Empty, UNICODE_QUAD_COUNT - (hi_index + 1), mRuns);
     787    assert (verify(mRuns, mQuads));
     788}
     789
     790/** ------------------------------------------------------------------------------------------------------------- *
     791 * @brief Range List Set Constructor
     792 ** ------------------------------------------------------------------------------------------------------------- */
     793template <typename itr>
     794void convertIntervalRangesToSparseSet(const itr begin, const itr end, UnicodeSet::RunVector & mRuns, UnicodeSet::QuadVector & mQuads) {
     795    assert (std::is_sorted(begin, end, [](const interval_t l, const interval_t r) {
     796        assert (l.first <= l.second);
     797        assert (l.second < UNICODE_MAX);
     798        assert (r.first <= r.second);
     799        assert (r.second < UNICODE_MAX);
     800        return l.second < r.first;
     801    }));
     802
     803    std::vector<run_t> runs;
     804    std::vector<bitquad_t> quads;
     805
     806    codepoint_t prior_index = 0;
     807    bitquad_t mask = 0;
     808    for (auto interval = begin; interval != end; ) {
     809        codepoint_t lo, hi;
     810        std::tie(lo, hi) = *interval;
     811        const codepoint_t lo_index = (lo / QUAD_BITS);
     812        const codepoint_t hi_index = (hi / QUAD_BITS);
     813        const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
     814        const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
     815        const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
     816        const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
     817        append_run(Empty, lo_index - prior_index, runs);
     818        if (lo_index == hi_index) {
     819            mask |= (lo_quad & hi_quad);
     820        } else {
     821            append_quad(mask | lo_quad, quads, runs);
     822            append_run(Full, hi_index - (lo_index + 1), runs);
     823            mask = hi_quad;
     824        }
     825        // if the next interval is in our current quad, continue to the next range
     826        prior_index = hi_index;
     827        if (LLVM_LIKELY(++interval != end)) {
     828            if (hi_index == (interval->first / QUAD_BITS)) {
     829                continue;
     830            }
     831        }
     832        append_quad(mask, quads, runs);
     833        mask = 0;
     834        ++prior_index;
     835    }
     836    assert (mask == 0);
     837    if (prior_index < UNICODE_QUAD_COUNT) {
     838        append_run(Empty, UNICODE_QUAD_COUNT - prior_index, runs);
     839    }   
     840    assert (verify(runs, quads));
     841    mRuns.assign(runs.begin(), runs.end());
     842    mQuads.assign(quads.begin(), quads.end());
     843}
     844
     845/** ------------------------------------------------------------------------------------------------------------- *
     846 * @brief Interval Range Constructor
     847 ** ------------------------------------------------------------------------------------------------------------- */
     848UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end)
     849: mRuns(0, {Empty, 0}, reinterpret_cast<RunAllocator &>(mAllocator))
     850, mQuads(0, 0, reinterpret_cast<QuadAllocator &>(mAllocator))
     851{
     852    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
     853}
     854
     855/** ------------------------------------------------------------------------------------------------------------- *
     856 * @brief Interval Range Constructor
     857 ** ------------------------------------------------------------------------------------------------------------- */
     858UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end)
     859: mRuns(0, {Empty, 0}, reinterpret_cast<RunAllocator &>(mAllocator))
     860, mQuads(0, 0, reinterpret_cast<QuadAllocator &>(mAllocator))
     861{
     862    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
     863}
     864
     865/** ------------------------------------------------------------------------------------------------------------- *
     866 * @brief Copy Constructor
     867 ** ------------------------------------------------------------------------------------------------------------- */
     868UnicodeSet::UnicodeSet(const UnicodeSet & other)
     869: mRuns(other.mRuns, reinterpret_cast<RunAllocator &>(mAllocator))
     870, mQuads(other.mQuads, reinterpret_cast<QuadAllocator &>(mAllocator))
     871{
     872    assert (verify(mRuns, mQuads));
     873}
     874
     875/** ------------------------------------------------------------------------------------------------------------- *
     876 * @brief Initializer Constructor
     877 ** ------------------------------------------------------------------------------------------------------------- */
     878UnicodeSet::UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q)
     879: mRuns(r.begin(), r.end(), reinterpret_cast<RunAllocator &>(mAllocator))
     880, mQuads(q.begin(), q.end(), reinterpret_cast<QuadAllocator &>(mAllocator))
     881{
     882    assert (verify(mRuns, mQuads));
     883}
     884
     885/** ------------------------------------------------------------------------------------------------------------- *
     886 * @brief Internal Vector Constructor
     887 ** ------------------------------------------------------------------------------------------------------------- */
     888inline UnicodeSet::UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q)
     889: mRuns(r.begin(), r.end(), reinterpret_cast<RunAllocator &>(mAllocator))
     890, mQuads(q.begin(), q.end(), reinterpret_cast<QuadAllocator &>(mAllocator))
     891{
     892    assert (verify(mRuns, mQuads));
     893}
     894
     895}
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.h

    r4818 r4860  
    44#include <vector>
    55#include <boost/iterator/iterator_facade.hpp>
     6#include <slab_allocator.h>
    67
    78//
     
    4849    using interval_t = std::pair<codepoint_t, codepoint_t>;
    4950
    50     using RunVector = std::vector<run_t>;
    51     using QuadVector = std::vector<bitquad_t>;
     51    using Allocator = SlabAllocator<uint32_t>;
     52    using RunAllocator = Allocator::rebind<run_t>::other;
     53    using QuadAllocator = Allocator::rebind<bitquad_t>::other;
     54
     55    using RunVector = std::vector<run_t, RunAllocator>;
     56    using QuadVector = std::vector<bitquad_t, QuadAllocator>;
     57    using RunIterator = RunVector::const_iterator;
     58    using QuadIterator = QuadVector::const_iterator;
    5259
    5360    using size_type = RunVector::size_type;
     
    7885        }
    7986    private:
    80         RunVector::const_iterator           mRunIterator;
    81         QuadVector::const_iterator          mQuadIterator;
    82         unsigned                            mMixedRunIndex;
    83         bitquad_t                           mQuadOffset;
    84         codepoint_t                         mBaseCodePoint;
    85         codepoint_t                         mMinCodePoint;
    86         codepoint_t                         mMaxCodePoint;
     87        RunIterator         mRunIterator;
     88        QuadIterator        mQuadIterator;
     89        unsigned            mMixedRunIndex;
     90        bitquad_t           mQuadOffset;
     91        codepoint_t         mBaseCodePoint;
     92        codepoint_t         mMinCodePoint;
     93        codepoint_t         mMaxCodePoint;
    8794    };
    8895
     
    96103    }
    97104
    98     class quad_iterator : public boost::iterator_facade<quad_iterator, quad_iterator_return_t, boost::random_access_traversal_tag, quad_iterator_return_t> {
    99         friend class UnicodeSet;
    100         friend class boost::iterator_core_access;
    101     public:
    102         quad_iterator(RunVector::const_iterator runIterator, QuadVector::const_iterator quadIterator)
    103             : mRunIterator(runIterator), mQuadIterator(quadIterator), mOffset(0) {}
    104 
    105         void advance(unsigned n);
    106 
    107         inline quad_iterator_return_t dereference() const {
    108             return std::make_pair(std::make_pair(type(), length()), quad());
    109         }
    110 
    111         inline void increment() {
    112             advance(1);
    113         }
    114 
    115         inline run_type_t type() const {
    116             return mRunIterator->first;
    117         }
    118 
    119         inline length_t length() const {
    120             return mRunIterator->second - mOffset;
    121         }
    122 
    123         inline bitquad_t quad() const {
    124             return *mQuadIterator;
    125         }
    126 
    127         inline bool equal(const quad_iterator & other) const {
    128             return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator);
    129         }
    130 
    131     private:
    132         RunVector::const_iterator   mRunIterator;
    133         QuadVector::const_iterator  mQuadIterator;
    134         unsigned                    mOffset;
    135     };
    136 
    137     inline quad_iterator quad_begin() const {
    138         return quad_iterator(mRuns.cbegin(), mQuads.cbegin());
    139     }
    140 
    141     inline quad_iterator quad_end() const {
    142         return quad_iterator(mRuns.cend(), mQuads.cend());
    143     }
    144 
    145105    bool contains(const codepoint_t codepoint) const;
    146106
    147107    bool intersects(const codepoint_t lo, const codepoint_t hi) const;
    148108
    149     inline void insert(const codepoint_t cp) {
    150         *this = std::move(*this + UnicodeSet(cp));
    151     }
    152 
    153     inline void insert_range(const codepoint_t lo, const codepoint_t hi) {
    154         *this = std::move(*this + UnicodeSet(lo, hi));
    155     }
     109    void insert(const codepoint_t cp);
     110
     111    void insert_range(const codepoint_t lo, const codepoint_t hi);
    156112
    157113    bool empty() const;
     
    178134    UnicodeSet();
    179135    UnicodeSet(const codepoint_t codepoint);
    180     UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint);
    181     inline UnicodeSet(const UnicodeSet & other) = default;
    182     UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q) : mRuns(r), mQuads(q) {}
    183     UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q) : mRuns(r), mQuads(q) {}
     136    UnicodeSet(const codepoint_t lo, const codepoint_t hi);
     137    UnicodeSet(const UnicodeSet & other);
     138    UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q);
     139    UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end);
     140    UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end);
    184141
    185142    inline void swap(UnicodeSet & other);
    186143    inline void swap(UnicodeSet && other);
    187144
     145protected:
     146
     147    UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q);
     148
     149    class quad_iterator : public boost::iterator_facade<quad_iterator, quad_iterator_return_t, boost::random_access_traversal_tag, quad_iterator_return_t> {
     150        friend class UnicodeSet;
     151        friend class boost::iterator_core_access;
     152    public:
     153        quad_iterator(RunIterator runIterator, QuadIterator quadIterator)
     154            : mRunIterator(runIterator), mQuadIterator(quadIterator), mOffset(0) {}
     155
     156        void advance(unsigned n);
     157
     158        inline quad_iterator_return_t dereference() const {
     159            return std::make_pair(std::make_pair(type(), length()), quad());
     160        }
     161
     162        inline void increment() {
     163            advance(1);
     164        }
     165
     166        inline run_type_t type() const {
     167            return mRunIterator->first;
     168        }
     169
     170        inline length_t length() const {
     171            return mRunIterator->second - mOffset;
     172        }
     173
     174        inline bitquad_t quad() const {
     175            return *mQuadIterator;
     176        }
     177
     178        inline bool equal(const quad_iterator & other) const {
     179            return (mRunIterator == other.mRunIterator) && (mQuadIterator == other.mQuadIterator);
     180        }
     181
     182    private:
     183        RunIterator     mRunIterator;
     184        QuadIterator    mQuadIterator;
     185        unsigned        mOffset;
     186    };
     187
     188    inline quad_iterator quad_begin() const {
     189        return quad_iterator(mRuns.cbegin(), mQuads.cbegin());
     190    }
     191
     192    inline quad_iterator quad_end() const {
     193        return quad_iterator(mRuns.cend(), mQuads.cend());
     194    }
     195
    188196private:
    189197
    190     RunVector       mRuns;
    191     QuadVector      mQuads;
     198    RunVector           mRuns;
     199    QuadVector          mQuads;
     200    static Allocator    mAllocator;
    192201};
    193202
  • icGREP/icgrep-devel/icgrep/generate_predefined_ucd_functions.cpp

    r4854 r4860  
    1616#include <pablo/analysis/pabloverifier.hpp>
    1717#include <pablo/optimizers/pablo_simplifier.hpp>
    18 #include <pablo/optimizers/pablo_codesinking.hpp>
     18#include <pablo/optimizers/codemotionpass.h>
    1919#ifdef ENABLE_MULTIPLEXING
    2020#include <pablo/optimizers/pablo_bddminimization.h>
     
    246246    std::cerr << name << std::endl;
    247247    #endif
    248     PabloFunction * function = PabloFunction::Create(std::move(name), 8, 1);
     248    PabloFunction * pbFunction = PabloFunction::Create(std::move(name), 8, 1);
    249249    Encoding encoding(Encoding::Type::UTF_8, 8);
    250     CC_Compiler ccCompiler(*function, encoding);
     250    CC_Compiler ccCompiler(*pbFunction, encoding);
    251251    UCDCompiler ucdCompiler(ccCompiler);
    252     PabloBuilder builder(function->getEntryBlock());
     252    PabloBuilder builder(pbFunction->getEntryBlock());
    253253    // Build the unicode set function
    254254    PabloAST * result = nullptr;
     
    260260        throw std::runtime_error("Unknown if hierarchy strategy!");
    261261    }
    262     function->setResult(0, builder.createAssign("matches", result));
     262    pbFunction->setResult(0, builder.createAssign("matches", result));
    263263    // Optimize it at the pablo level
    264     PabloVerifier::verify(*function, "creation");
    265     Simplifier::optimize(*function);
    266     CodeMotionPass::optimize(*function);
     264    PabloVerifier::verify(*pbFunction, "creation");
     265    Simplifier::optimize(*pbFunction);
     266    CodeMotionPass::optimize(*pbFunction);
    267267    #ifdef ENABLE_MULTIPLEXING
    268268    BDDMinimizationPass::optimize(*function);
     
    287287    #endif
    288288    if (EnableReassociation) {
    289         BooleanReassociationPass::optimize(*function);       
     289        BooleanReassociationPass::optimize(*pbFunction);
    290290    }
    291291
    292292    // Now compile the function ...
    293     llvm::Function * func = pc.compile(function, module);
    294     releaseSlabAllocatorMemory();
     293    llvm::Function * func = pc.compile(pbFunction, module);
    295294
    296295    if (LongestDependenceChainFile) {
    297         const auto pablo_metrix = computePabloDependencyChainMetrics(function);
     296        const auto pablo_metrix = computePabloDependencyChainMetrics(pbFunction);
    298297        (*LongestDependenceChainFile) << ',' << pablo_metrix.first << ',' << pablo_metrix.second;
    299298        const auto llvm_metrix = computeLLVMDependencyChainMetrics(func);
     
    301300    }
    302301
     302    delete pbFunction;
    303303}
    304304
  • icGREP/icgrep-devel/icgrep/icgrep.cpp

    r4853 r4860  
    161161        try {
    162162            icgrep_IR = pablo_compiler.compile(function);
     163            delete function;
    163164            releaseSlabAllocatorMemory();
    164         }
    165         catch (std::runtime_error e) {
     165        } catch (std::runtime_error e) {
     166            delete function;
    166167            releaseSlabAllocatorMemory();
    167168            std::cerr << "Runtime error: " << e.what() << std::endl;
    168169            exit(1);
    169170        }
    170     }
    171     else {
     171    } else {
    172172        firstInputFile = 0;  // No regexp arguments; first positional argument is a file to process.
    173173        SMDiagnostic ParseErr;
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r4797 r4860  
    534534/// CONSTRUCTOR
    535535
    536 PabloBlock::PabloBlock(SymbolGenerator & symbolGenerator)
     536PabloBlock::PabloBlock(SymbolGenerator * symbolGenerator)
    537537: PabloAST(PabloAST::ClassTypeId::Block)
    538538, mSymbolGenerator(symbolGenerator)
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4797 r4860  
    5353    }
    5454
    55     inline static PabloBlock & Create(SymbolGenerator & symbolGenerator) {
     55    inline static PabloBlock & Create(SymbolGenerator * symbolGenerator) {
     56        assert (symbolGenerator);
    5657        return *(new PabloBlock(symbolGenerator));
    5758    }
     
    173174
    174175    inline String * getName(const std::string name, const bool generated = true) const {
    175         return mSymbolGenerator.get(name, generated);
     176        return mSymbolGenerator->get(name, generated);
    176177    }
    177178
    178179    inline String * makeName(const std::string prefix, const bool generated = true) const {
    179         return mSymbolGenerator.make(prefix, generated);
     180        return mSymbolGenerator->make(prefix, generated);
    180181    }
    181182
    182183    inline Integer * getInteger(Integer::Type value) {
    183         return mSymbolGenerator.getInteger(value);
     184        return mSymbolGenerator->getInteger(value);
    184185    }
    185186
     
    200201protected:
    201202
    202     PabloBlock(SymbolGenerator & symbolGenerator);
    203 
    204     PabloBlock(PabloBlock * predecessor);
     203    explicit PabloBlock(SymbolGenerator * symbolGenerator);
     204
     205    explicit PabloBlock(PabloBlock * predecessor);
    205206
    206207    PabloAST * renameNonNamedNode(PabloAST * expr, const std::string && prefix);
     
    227228    static Zeroes                                       mZeroes;
    228229    static Ones                                         mOnes;
    229     SymbolGenerator &                                   mSymbolGenerator;
     230    SymbolGenerator *                                   mSymbolGenerator;
    230231    PabloBlock *                                        mParent;
    231232    unsigned                                            mScopeIndex;
  • icGREP/icgrep-devel/icgrep/pablo/function.cpp

    r4726 r4860  
    1616PabloFunction::PabloFunction(std::string && name, const unsigned numOfParameters, const unsigned numOfResults)
    1717: Prototype(ClassTypeId::Function, std::move(name), numOfParameters, numOfResults, nullptr)
     18, mSymbolTable(new SymbolGenerator())
    1819, mEntryBlock(PabloBlock::Create(mSymbolTable))
    1920, mParameters(reinterpret_cast<Var **>(mAllocator.allocate(sizeof(Var *) * numOfParameters)))
     
    3738}
    3839
     40void PabloFunction::operator delete(void * ptr) {
     41    PabloFunction * f = static_cast<PabloFunction *>(ptr);
     42    delete f->mSymbolTable;
     43    f->mSymbolTable = nullptr;
    3944}
     45
     46}
  • icGREP/icgrep-devel/icgrep/pablo/function.h

    r4734 r4860  
    4343        return mFunctionPtr;
    4444    }
    45 
    4645protected:
    4746    Prototype(const PabloAST::ClassTypeId type, std::string && name, const unsigned numOfParameters, const unsigned numOfResults, void * functionPtr);
     
    8988    const PabloBlock & getEntryBlock() const {
    9089        return mEntryBlock;
    91     }
    92 
    93     SymbolGenerator & getSymbolTable() {
    94         return mSymbolTable;
    9590    }
    9691
     
    142137    }
    143138
     139    void operator delete (void*);
     140
    144141    virtual ~PabloFunction() { }
    145142
     
    152149    PabloFunction(std::string && name, const unsigned numOfParameters, const unsigned numOfResults);
    153150private:
    154     PabloBlock &        mEntryBlock;
    155     SymbolGenerator     mSymbolTable;
     151    SymbolGenerator *   mSymbolTable;
     152    PabloBlock &        mEntryBlock;   
    156153    Var ** const        mParameters;
    157154    Assign ** const     mResults;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4808 r4860  
    1313#include <set>
    1414#include <pablo/printer_pablos.h>
     15#include <iostream>
     16#include <llvm/Support/raw_os_ostream.h>
     17#include <boost/graph/strong_components.hpp>
    1518
    1619using namespace boost;
     
    125128}
    126129
    127 inline bool isMutable(const VertexData & data, const PabloBlock &) {
     130inline bool isMutable(const VertexData & data) {
    128131    return getType(data) != TypeId::Var;
    129132}
     
    157160
    158161/** ------------------------------------------------------------------------------------------------------------- *
     162 * @brief printGraph
     163 ** ------------------------------------------------------------------------------------------------------------- */
     164static void printGraph(const Graph & G, const std::string name, raw_ostream & out) {
     165
     166    std::vector<unsigned> c(num_vertices(G));
     167    strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
     168
     169    out << "digraph " << name << " {\n";
     170    for (auto u : make_iterator_range(vertices(G))) {
     171        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     172            continue;
     173        }
     174        out << "v" << u << " [label=\"" << u << ": ";
     175        PabloAST * expr;
     176        TypeId typeId;
     177        std::tie(typeId, expr) = G[u];
     178        bool temporary = false;
     179        bool error = false;
     180        if (expr == nullptr) {
     181            temporary = true;
     182            switch (typeId) {
     183                case TypeId::And:
     184                    out << "And";
     185                    break;
     186                case TypeId::Or:
     187                    out << "Or";
     188                    break;
     189                case TypeId::Xor:
     190                    out << "Xor";
     191                    break;
     192                default:
     193                    out << "???";
     194                    error = true;
     195                    break;
     196            }
     197        } else if (isMutable(G[u])) {
     198            if (LLVM_UNLIKELY(isa<If>(expr))) {
     199                out << "If ";
     200                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
     201                out << ":";
     202            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
     203                out << "While ";
     204                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
     205                out << ":";
     206            } else {
     207                PabloPrinter::print(cast<Statement>(expr), "", out);
     208            }
     209        } else {
     210            PabloPrinter::print(expr, out);
     211        }
     212        out << "\"";
     213        if (!isMutable(G[u])) {
     214            out << " style=dashed";
     215        }
     216        if (error) {
     217            out << " color=red";
     218        } else if (temporary) {
     219            out << " color=blue";
     220        }
     221        out << "];\n";
     222    }
     223    for (auto e : make_iterator_range(edges(G))) {
     224        const auto s = source(e, G);
     225        const auto t = target(e, G);
     226        out << "v" << s << " -> v" << t;
     227        bool cyclic = (c[s] == c[t]);
     228        if (G[e] || cyclic) {
     229            out << " [";
     230             if (G[e]) {
     231                out << "label=\"";
     232                PabloPrinter::print(G[e], out);
     233                out << "\" ";
     234             }
     235             if (cyclic) {
     236                out << "color=red ";
     237             }
     238             out << "]";
     239        }
     240        out << ";\n";
     241    }
     242
     243    if (num_vertices(G) > 0) {
     244
     245        out << "{ rank=same;";
     246        for (auto u : make_iterator_range(vertices(G))) {
     247            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     248                out << " v" << u;
     249            }
     250        }
     251        out << "}\n";
     252
     253        out << "{ rank=same;";
     254        for (auto u : make_iterator_range(vertices(G))) {
     255            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     256                out << " v" << u;
     257            }
     258        }
     259        out << "}\n";
     260
     261    }
     262
     263    out << "}\n\n";
     264    out.flush();
     265}
     266
     267/** ------------------------------------------------------------------------------------------------------------- *
    159268 * @brief optimize
    160269 ** ------------------------------------------------------------------------------------------------------------- */
     
    164273    brp.processScopes(function);   
    165274    #ifndef NDEBUG
    166     Simplifier::deadCodeElimination(function.getEntryBlock());
    167275    PabloVerifier::verify(function, "post-reassociation");
    168276    #endif
     
    228336
    229337/** ------------------------------------------------------------------------------------------------------------- *
    230  * @brief createTree
    231  ** ------------------------------------------------------------------------------------------------------------- */
    232 PabloAST * BooleanReassociationPass::createTree(PabloBlock & block, const Vertex u, Graph & G, const WrittenAt & writtenAt) {
    233     flat_set<PabloAST *> sources;
    234     for (const auto e : make_iterator_range(in_edges(u, G))) {
    235         PabloAST * expr = getValue(G[source(e, G)]);
    236         assert ("G contains a null input variable!" && (expr != nullptr));
    237         sources.insert(expr);
    238     }
    239     circular_buffer<PabloAST *> Q(sources.begin(), sources.end());
    240     // Sort the queue in order of how the inputs were written
    241     std::sort(Q.begin(), Q.end(), [&writtenAt](const PabloAST * const e1, const PabloAST * const e2) -> bool {
    242         const auto f1 = writtenAt.find(e1); assert (f1 != writtenAt.end());
    243         const auto f2 = writtenAt.find(e2); assert (f2 != writtenAt.end());
    244         return f1->second < f2->second;
    245     });
    246 
    247     const TypeId typeId = getType(G[u]);
     338 * @brief writeTree
     339 ** ------------------------------------------------------------------------------------------------------------- */
     340inline void writeTree(PabloBlock & block, const TypeId typeId, circular_buffer<PabloAST *> & Q) {
    248341    while (Q.size() > 1) {
    249         PabloAST * e1 = Q.front(); Q.pop_front();       
     342        PabloAST * e1 = Q.front(); Q.pop_front();
    250343        PabloAST * e2 = Q.front(); Q.pop_front();
    251344        PabloAST * expr = nullptr;
     
    261354        Q.push_back(expr);
    262355    }
     356}
     357
     358/** ------------------------------------------------------------------------------------------------------------- *
     359 * @brief createTree
     360 ** ------------------------------------------------------------------------------------------------------------- */
     361PabloAST * BooleanReassociationPass::createTree(PabloBlock & block, const Vertex u, Graph & G) {
     362
     363    flat_set<PabloAST *> sources;
     364
     365    for (const auto e : make_iterator_range(in_edges(u, G))) {
     366        PabloAST * const expr = getValue(G[source(e, G)]);
     367        assert ("G contains a null input variable!" && (expr != nullptr));
     368        sources.insert(expr);
     369    }
     370
     371    circular_buffer<PabloAST *> Q(sources.size());
     372
     373    for (auto si = sources.begin(); si != sources.end(); ) {
     374        if (inCurrentBlock(*si, block)) {
     375            ++si;
     376        } else { // combine any non-Statements or statements from a preceeding block at the beginning of this block.
     377            Q.push_back(*si);
     378            si = sources.erase(si);
     379        }
     380    }
     381
     382    const TypeId typeId = getType(G[u]);
     383    Statement * current = block.front();
     384    if (Q.size() > 1) {
     385        block.setInsertPoint(nullptr);
     386        writeTree(block, typeId, Q);
     387        current = block.getInsertPoint();
     388    }
     389
     390    unsigned distance = 0;
     391    while (current) {
     392        if (sources.count(current)) {
     393            if (distance > 2) { // write out the current Q
     394                writeTree(block, typeId, Q);
     395            } else {
     396                block.setInsertPoint(current);
     397            }
     398            Q.push_back(current);
     399            distance = 0;
     400        }
     401        ++distance;
     402        current = current->getNextNode();
     403    }
     404    writeTree(block, typeId, Q);
     405    assert (Q.size() == 1);
    263406    PabloAST * const result = Q.front();
    264407    assert (result);
    265408    getValue(G[u]) = result;
     409    block.setInsertPoint(block.back());
    266410    return result;
    267411}
     
    282426 ** ------------------------------------------------------------------------------------------------------------- */
    283427void BooleanReassociationPass::rewriteAST(PabloBlock & block, Graph & G) {
    284     // Rewrite the AST in accordance to G
     428
     429    using ReadySetQueue = std::priority_queue<std::pair<unsigned, Vertex>, std::deque<std::pair<unsigned, Vertex>>, std::greater<std::pair<unsigned, Vertex>>>;
     430
     431    raw_os_ostream out(std::cerr);
     432    out << "***************************************************\n";
     433    printGraph(G, "G_" + std::to_string((unsigned long)(&block)), out);
     434
     435
     436    // Determine the bottom-up ordering of G
     437    std::vector<unsigned> ordering(num_vertices(G));
    285438    circular_buffer<Vertex> Q(num_vertices(G));
    286     topological_sort(G, std::back_inserter(Q));
    287 
    288     block.setInsertPoint(nullptr);
    289     unsigned statementCount = 0;
    290     WrittenAt writtenAt;
    291     writtenAt.emplace(PabloBlock::createZeroes(), 0);
    292     writtenAt.emplace(PabloBlock::createOnes(), 0);
     439    for (const Vertex u : make_iterator_range(vertices(G))) {
     440        if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
     441            ordering[u] = 1;
     442            Q.push_back(u);
     443        }
     444    }
     445
    293446    while (!Q.empty()) {
    294         const Vertex u = Q.back();
    295         Q.pop_back();
    296         // Supress any isolated vertices
    297         if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    298             continue;
    299         }
    300         unsigned statementIndex = 0;
     447        const Vertex u = Q.front();
     448        Q.pop_front();
     449        assert (ordering[u] > 0);
     450        for (const auto ei : make_iterator_range(in_edges(u, G))) {
     451            const Vertex v = source(ei, G);
     452            if (ordering[v] == 0) {
     453                unsigned weight = 0;
     454                bool ready = true;
     455                for (const auto ej : make_iterator_range(out_edges(v, G))) {
     456                    const Vertex w = target(ej, G);
     457                    const unsigned t = ordering[w];
     458                    if (t == 0) {
     459                        ready = false;
     460                        break;
     461                    }
     462                    weight = std::max(weight, t);
     463                }
     464                if (ready) {
     465                    assert (weight < std::numeric_limits<unsigned>::max());
     466                    assert (weight > 0);
     467                    ordering[v] = (weight + 1);
     468                    Q.push_back(v);
     469                }
     470            }
     471        }
     472    }
     473
     474    ReadySetQueue readySet;
     475    for (const Vertex u : make_iterator_range(vertices(G))) {
     476        if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
     477            readySet.emplace(ordering[u], u);
     478        }
     479    }
     480
     481    out << "---------------------------------------------------\n";
     482    out.flush();
     483
     484    // Store the original AST then clear the block
     485    std::vector<Statement *> originalAST(block.begin(), block.end());
     486    block.clear();
     487    flat_set<Vertex> contains;
     488
     489    // Rewrite the AST using the bottom-up ordering
     490    while (!readySet.empty()) {
     491
     492        Vertex u; unsigned weight;
     493        std::tie(weight, u) = readySet.top();
     494        readySet.pop();
     495
    301496        PabloAST * expr = getValue(G[u]);
    302         if (LLVM_LIKELY(isMutable(G[u], block))) {
     497
     498        out << " * processing " << u << ' ';
     499        PabloPrinter::print(expr, out);
     500        out << ", weight=" << weight;
     501        out.flush();
     502
     503        assert (weight > 0);
     504
     505        if (LLVM_LIKELY(isMutable(G[u]))) {
    303506            Statement * stmt = nullptr;
    304507            if (isAssociative(G[u])) {
    305                 PabloAST * replacement = createTree(block, u, G, writtenAt);
     508                PabloAST * replacement = createTree(block, u, G);
    306509                if (LLVM_LIKELY(inCurrentBlock(replacement, block))) {
    307510                    stmt = cast<Statement>(replacement);
    308511                } else { // optimization reduced this to a Constant, Var or a prior-scope statement
    309512                    getType(G[u]) = TypeId::Var;
    310                     continue;
     513                    goto check_ready;
    311514                }
    312515            } else { // update any potential mappings
    313                 stmt = cast<Statement>(getValue(G[u]));
     516                stmt = cast<Statement>(expr);
    314517            }
    315518            assert (stmt);
    316519            for (auto e : make_iterator_range(out_edges(u, G))) {
    317520                if (G[e] && G[e] != stmt) {
    318                     PabloAST * expr = getValue(G[target(e, G)]);
    319                     if (expr) { // processing a yet-to-be created value
    320                         cast<Statement>(expr)->replaceUsesOfWith(G[e], stmt);
     521                    if (PabloAST * user = getValue(G[target(e, G)])) {
     522                        cast<Statement>(user)->replaceUsesOfWith(G[e], stmt);
    321523                    }
    322524                }
    323525            }
    324             // make sure that optimization doesn't reduce this to an already written statement
    325             if (writtenAt.count(stmt)) {
    326                 continue;
     526            // Make sure that optimization doesn't reduce this to an already written statement
     527            if (stmt->getParent()) {
     528                goto check_ready;
    327529            }
    328530            block.insert(stmt);
    329             statementIndex = ++statementCount;
    330531            expr = stmt;
    331532        }
    332         writtenAt.emplace(expr, statementIndex);
    333     }
     533check_ready:
     534
     535        out << ", wrote ";
     536        PabloPrinter::print(expr, out);
     537        out << '\n';
     538        out.flush();
     539
     540        // mark this instruction as written
     541        ordering[u] = 0;
     542        // Now check whether any new instructions are ready
     543        for (auto ei : make_iterator_range(out_edges(u, G))) {
     544            bool ready = true;
     545            const auto v = target(ei, G);
     546            // since G may be a multigraph, we need to check whether we've already tested v
     547            if (contains.insert(v).second) {
     548                for (auto ej : make_iterator_range(in_edges(v, G))) {
     549                    if (ordering[source(ej, G)]) {
     550                        ready = false;
     551                        break;
     552                    }
     553                }
     554                if (ready) {
     555
     556                    out << "   adding " << v << ' ';
     557                    PabloPrinter::print(getValue(G[v]), out);
     558                    out << " to ready set, weight=" << ordering[v] << '\n';
     559
     560                    readySet.emplace(ordering[v], v);
     561                }
     562            }
     563        }
     564        contains.clear();
     565
     566        out << "---------------------------------------------------\n";
     567        out.flush();
     568    }
     569
     570    for (Statement * stmt : originalAST) {
     571        if (stmt->getParent() == nullptr) {
     572            stmt->eraseFromParent();
     573        }
     574    }
     575
     576    PabloPrinter::print(block.statements(), out);
     577
    334578}
    335579
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4797 r4860  
    1717    using WrittenAt = boost::container::flat_map<const PabloAST *, unsigned>;
    1818    using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
    19 
    2019    static bool optimize(PabloFunction & function);
    2120protected:
     
    2726    void processScope(PabloFunction &, PabloBlock & block);
    2827    void summarizeAST(PabloBlock & block, Graph & G, Map & M) const;
    29     static void findAndPropogateAnyConstants(const Vertex u, Graph & G, Map & M);
    3028    static void summarizeGraph(const PabloBlock & block, Graph & G, std::vector<Vertex> & mapping, Map &M);
    3129    void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, const Statement * const ignoreIfThis = nullptr) const;
    3230    void redistributeAST(const PabloBlock & block, Graph & G, Map & M) const;
    3331    void rewriteAST(PabloBlock & block, Graph & G);
    34     static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G, const WrittenAt & writtenAt);
     32    static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G);
    3533    static Vertex getSummaryVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block);
    3634    static Vertex addSummaryVertex(const PabloAST::ClassTypeId typeId, Graph & G);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/codemotionpass.cpp

    r4856 r4860  
    2525    CodeMotionPass::process(function.getEntryBlock());
    2626    #ifndef NDEBUG
    27     PabloVerifier::verify(function, "post-sinking");
     27    PabloVerifier::verify(function, "post-code-motion");
    2828    #endif
    2929    return true;
     
    4040        } else if (isa<While>(stmt)) {
    4141            process(cast<While>(stmt)->getBody());
    42             // TODO: if we analyzed the probability of this loop being executed once, twice or many times, we could
    43             // determine hoisting will helpful or harmful to the expected run time.
     42            // TODO: if we analyzed the probability of this loop being executed once, twice, or many times, we could
     43            // determine whether hoisting will helpful or harmful to the expected run time.
    4444            hoistLoopInvariants(cast<While>(stmt));
    4545        }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4822 r4860  
    1616#include <queue>
    1717#include <unordered_set>
    18 #include <pablo/optimizers/pablo_simplifier.hpp>
    1918#include <pablo/optimizers/booleanreassociationpass.h>
    2019#include <pablo/analysis/pabloverifier.hpp>
     
    165164        #endif
    166165
    167         Simplifier::optimize(function);
     166        BooleanReassociationPass::optimize(function);
    168167    }
    169168
     
    994993 * @brief multiplexSelectedIndependentSets
    995994 ** ------------------------------------------------------------------------------------------------------------- */
    996 void AutoMultiplexing::multiplexSelectedIndependentSets(PabloFunction & function) {
     995void AutoMultiplexing::multiplexSelectedIndependentSets(PabloFunction &) {
    997996
    998997    const unsigned first_set = num_vertices(mConstraintGraph);
     
    11001099        }
    11011100    }
    1102 
    1103     for (PabloBlock * block : modified) {
    1104         topologicalSort(function, *block);
    1105     }
    1106 }
    1107 
    1108 ///** ------------------------------------------------------------------------------------------------------------- *
    1109 // * @brief printGraph
    1110 // ** ------------------------------------------------------------------------------------------------------------- */
    1111 //template <class Graph>
    1112 //static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) {
    1113 //    raw_os_ostream out(std::cerr);
    1114 
    1115 //    out << "digraph " << name << " {\n";
    1116 //    for (auto u : make_iterator_range(vertices(G))) {
    1117 //        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    1118 //            continue;
    1119 //        }
    1120 //        out << "v" << u << " [label=\"" << u << ": ";
    1121 //        PabloAST * const expr = G[u];
    1122 //        if (isa<Statement>(expr)) {
    1123 //            if (LLVM_UNLIKELY(isa<If>(expr))) {
    1124 //                out << "If ";
    1125 //                PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
    1126 //                out << ":";
    1127 //            } else if (LLVM_UNLIKELY(isa<While>(expr))) {
    1128 //                out << "While ";
    1129 //                PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
    1130 //                out << ":";
    1131 //            } else {
    1132 //                PabloPrinter::print(cast<Statement>(expr), "", out);
    1133 //            }
    1134 //        } else {
    1135 //            PabloPrinter::print(expr, out);
    1136 //        }
    1137 //        out << "\"";
    1138 //        if (!isa<Statement>(expr) || cast<Statement>(expr)->getParent() != &block) {
    1139 //            out << " style=dashed";
    1140 //        }
    1141 //        out << "];\n";
    1142 //    }
    1143 //    for (auto e : make_iterator_range(edges(G))) {
    1144 //        const auto s = source(e, G);
    1145 //        const auto t = target(e, G);
    1146 //        out << "v" << s << " -> v" << t << ";\n";
    1147 //    }
    1148 
    1149 //    if (num_vertices(G) > 0) {
    1150 
    1151 //        out << "{ rank=same;";
    1152 //        for (auto u : make_iterator_range(vertices(G))) {
    1153 //            if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    1154 //                out << " v" << u;
    1155 //            }
    1156 //        }
    1157 //        out << "}\n";
    1158 
    1159 //        out << "{ rank=same;";
    1160 //        for (auto u : make_iterator_range(vertices(G))) {
    1161 //            if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    1162 //                out << " v" << u;
    1163 //            }
    1164 //        }
    1165 //        out << "}\n";
    1166 
    1167 //    }
    1168 
    1169 //    out << "}\n\n";
    1170 //    out.flush();
    1171 //}
    1172 
    1173 /** ------------------------------------------------------------------------------------------------------------- *
    1174  * @brief topologicalSort
    1175  ** ------------------------------------------------------------------------------------------------------------- */
    1176 void AutoMultiplexing::topologicalSort(PabloFunction &, PabloBlock & block) const {
    1177 
    1178     TopologicalGraph G;
    1179     TopologicalMap M;
    1180     // Compute the base def-use graph ...
    1181     for (Statement * stmt : block) {       
    1182         const TopologicalVertex u = getVertex(stmt, G, M);
    1183         if (isa<If>(stmt)) {
    1184             for (Assign * def : cast<const If>(stmt)->getDefined()) {
    1185                 resolveUsages(u, def, block, G, M, stmt);
    1186             }
    1187         } else if (isa<While>(stmt)) {
    1188             for (Next * var : cast<const While>(stmt)->getVariants()) {
    1189                 resolveUsages(u, var, block, G, M, stmt);
    1190             }
    1191         } else {
    1192             resolveUsages(u, stmt, block, G, M, nullptr);
    1193         }
    1194     }
    1195 
    1196     circular_buffer<TopologicalVertex> Q(num_vertices(G));
    1197     topological_sort(G, std::back_inserter(Q));
    1198 
    1199     block.setInsertPoint(nullptr);
    1200     while (!Q.empty()) {
    1201         Statement * stmt = G[Q.back()];
    1202         Q.pop_back();
    1203         if (stmt->getParent() == &block) {
    1204             block.insert(stmt);
    1205         }
    1206     }
    1207 
    1208 }
    1209 
    1210 /** ------------------------------------------------------------------------------------------------------------- *
    1211  * @brief resolveUsages
    1212  ** ------------------------------------------------------------------------------------------------------------- */
    1213 void AutoMultiplexing::resolveUsages(const TopologicalVertex u, Statement * expr, PabloBlock & block, TopologicalGraph & G, TopologicalMap & M, Statement * ignoreIfThis) const {
    1214     for (PabloAST * user : expr->users()) {
    1215         if (LLVM_LIKELY(user != ignoreIfThis && isa<Statement>(user))) {
    1216             PabloBlock * parent = cast<Statement>(user)->getParent();
    1217             assert (parent);
    1218             if (LLVM_LIKELY(parent == &block)) {
    1219                 add_edge(u, getVertex(cast<Statement>(user), G, M), G);
    1220             } else {
    1221                 for (;;) {
    1222                     if (LLVM_UNLIKELY(parent == nullptr)) {
    1223                         assert (isa<Assign>(expr) || isa<Next>(expr));
    1224                         break;
    1225                     } else if (parent->getParent() == &block) {
    1226                         const auto f = mResolvedScopes.find(parent);
    1227                         if (LLVM_UNLIKELY(f == mResolvedScopes.end())) {
    1228                             throw std::runtime_error("Failed to resolve scope block!");
    1229                         }
    1230                         Statement * const branch = f->second;
    1231                         if (LLVM_UNLIKELY(branch != ignoreIfThis)) {
    1232                             add_edge(u, getVertex(branch, G, M), G);
    1233                         }
    1234                         break;
    1235                     }
    1236                     parent = parent->getParent();
    1237                 }
    1238             }
    1239         }
    1240     }
    1241 }
    1242 
    1243 /** ------------------------------------------------------------------------------------------------------------- *
    1244  * @brief getVertex
    1245  ** ------------------------------------------------------------------------------------------------------------- */
    1246 AutoMultiplexing::TopologicalVertex AutoMultiplexing::getVertex(Statement * expr, TopologicalGraph & G, TopologicalMap & M) {
    1247     const auto f = M.find(expr);
    1248     if (f != M.end()) {
    1249         return f->second;
    1250     }
    1251     const auto u = add_vertex(expr, G);
    1252     M.emplace(expr, u);
    1253     return u;
    12541101}
    12551102
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4822 r4860  
    5252    void applySubsetConstraints();
    5353    void multiplexSelectedIndependentSets(PabloFunction & function);
    54     void topologicalSort(PabloFunction & function, PabloBlock & block) const;
    55     void resolveUsages(const TopologicalVertex u, Statement * expr, PabloBlock & block, TopologicalGraph & G, TopologicalMap & M, Statement * ignoreIfThis) const;
    56     static TopologicalVertex getVertex(Statement * expr, TopologicalGraph & G, TopologicalMap & M);
    5754
    5855    inline AutoMultiplexing(const unsigned limit, const unsigned maxSelections)
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4856 r4860  
    228228            if (isSuperfluous(assign)) {
    229229                if (assign->getNumUses() == 0) {
    230                     stmt = assign->eraseFromParent();
     230                    stmt = assign->eraseFromParent(true);
    231231                } else {
    232232                    stmt = assign->replaceWith(assign->getExpression(), true, true);
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4856 r4860  
    1414
    1515PabloAST::Allocator PabloAST::mAllocator;
    16 PabloAST::VectorAllocator PabloAST::mVectorAllocator;
    1716
    1817/*
     
    379378}
    380379
     380/** ------------------------------------------------------------------------------------------------------------- *
     381 * @brief clear
     382 ** ------------------------------------------------------------------------------------------------------------- */
     383void StatementList::clear() {
     384    Statement * stmt = front();
     385    while (stmt) {
     386        Statement * next = stmt->mNext;
     387        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     388            PabloBlock & body = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     389            stmt->mParent->removeUser(&body);
     390        }
     391        stmt->mPrev = nullptr;
     392        stmt->mNext = nullptr;
     393        stmt->mParent = nullptr;
     394        stmt = next;
     395    }
     396    mInsertionPoint = nullptr;
     397    mFirst = nullptr;
     398    mLast = nullptr;
     399}
     400
    381401StatementList::~StatementList() {
    382402
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r4856 r4860  
    2525class PabloAST {
    2626    friend class Statement;
     27    friend class StatementList;
    2728    friend class Var;
    2829    friend class If;   
     
    3536
    3637    using Allocator = SlabAllocator<u_int8_t>;
    37     using VectorAllocator = SlabAllocator<PabloAST *>;
     38    using VectorAllocator = Allocator::rebind<PabloAST *>::other;
    3839    using Vector = std::vector<PabloAST*, VectorAllocator>;
    3940    using user_iterator = Vector::iterator;
     
    115116        return mAllocator.allocate(size);
    116117    }
     118
     119    void operator delete (void * ptr) {
     120        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
     121    }
     122
    117123protected:
    118124    inline PabloAST(const ClassTypeId id)
    119125    : mClassTypeId(id)
    120     , mUsers(mVectorAllocator)
     126    , mUsers(reinterpret_cast<VectorAllocator &>(mAllocator))
    121127    {
    122128
     
    148154    const ClassTypeId       mClassTypeId;
    149155    Vector                  mUsers;
    150     static VectorAllocator  mVectorAllocator;
    151156};
    152157
     
    482487    }
    483488
     489    void clear();
     490
    484491    inline void setInsertPoint(Statement * const statement) {
    485492        assert (statement == nullptr || contains(statement));
  • icGREP/icgrep-devel/icgrep/pablo/ps_if.cpp

    r4856 r4860  
    88: Statement(ClassTypeId::If, {expr}, nullptr)
    99, mBody(body)
    10 , mDefined(definedVars.begin(), definedVars.end(), reinterpret_cast<DefinedAllocator &>(mVectorAllocator))
     10, mDefined(definedVars.begin(), definedVars.end(), reinterpret_cast<DefinedAllocator &>(mAllocator))
    1111{
    1212    // Conceptually, having a defined var X is identical to having:
     
    3030: Statement(ClassTypeId::If, {expr}, nullptr)
    3131, mBody(body)
    32 , mDefined(definedVars.begin(), definedVars.end(), reinterpret_cast<DefinedAllocator &>(mVectorAllocator))
     32, mDefined(definedVars.begin(), definedVars.end(), reinterpret_cast<DefinedAllocator &>(mAllocator))
    3333{
    3434    for (PabloAST * def : mDefined) {
  • icGREP/icgrep-devel/icgrep/pablo/ps_while.cpp

    r4856 r4860  
    77: Statement(ClassTypeId::While, {expr}, nullptr)
    88, mBody(body)
    9 , mNext(nextVars.begin(), nextVars.end(), reinterpret_cast<NextAllocator &>(mVectorAllocator)) {
     9, mNext(nextVars.begin(), nextVars.end(), reinterpret_cast<NextAllocator &>(mAllocator)) {
    1010    for (Next * variant : nextVars) {
    1111        variant->addUser(this);
     
    1717: Statement(ClassTypeId::While, {expr}, nullptr)
    1818, mBody(body)
    19 , mNext(nextVars.begin(), nextVars.end(), reinterpret_cast<NextAllocator &>(mVectorAllocator)) {
     19, mNext(nextVars.begin(), nextVars.end(), reinterpret_cast<NextAllocator &>(mAllocator)) {
    2020    for (Next * variant : nextVars) {
    2121        variant->addUser(this);
  • icGREP/icgrep-devel/icgrep/pablo/symbol_generator.cpp

    r4510 r4860  
    1111namespace pablo {
    1212
    13 SymbolGenerator::SymbolGenerator()
    14 : mPrefixMap()
    15 {
    16 
    17 }
    18 
    1913String * SymbolGenerator::get(const std::string name, const bool generated) {
     14    if (name.length() == 0) {
     15        throw std::runtime_error("symbol name cannot be 0-length");
     16    }
    2017    auto f = mStringMap.find(name);
    21     String * result;
     18    String * result = nullptr;
    2219    if (f == mStringMap.end()) {
    2320        result = new String(name, generated);
     21        assert (result);
    2422        mStringMap.insert(std::make_pair(std::move(name), result));
    2523    }
     
    3735        assert (result->value() == value);
    3836        mIntegerMap.insert(std::make_pair(value, result));
    39     }
    40     else {
     37    } else {
    4138        result = f->second;
    4239    }
     
    5047        mPrefixMap.insert(std::make_pair(prefix, 1));
    5148        return get(prefix, generated);
    52     }
    53     else {
     49    } else {
    5450        count = f->second++;
    5551        return get(prefix + std::to_string(count), generated);
     
    5753}
    5854
    59 SymbolGenerator::~SymbolGenerator() {
    60 
    6155}
    62 
    63 }
  • icGREP/icgrep-devel/icgrep/pablo/symbol_generator.h

    r4692 r4860  
    2828    String * make(const std::string prefix, const bool generated = true);
    2929    Integer * getInteger(const integer_t value);
    30     SymbolGenerator();
    31     ~SymbolGenerator();
     30    SymbolGenerator() = default;
     31    ~SymbolGenerator() = default;
    3232private:
    3333    std::unordered_map<std::string, integer_t>  mPrefixMap;
  • icGREP/icgrep-devel/icgrep/re/re_cc.h

    r4814 r4860  
    5050    friend CC * makeCC(const codepoint_t lo, const codepoint_t hi);
    5151    friend CC * makeCC(const CC * cc1, const CC * cc2);
    52     friend CC * makeCC(const std::initializer_list<interval_t> list);
    53     friend CC * makeCC(const std::vector<interval_t> & list);
     52    friend CC * makeCC(std::initializer_list<interval_t> list);
     53    friend CC * makeCC(std::vector<interval_t> && list);
    5454    friend CC * makeCC(UCD::UnicodeSet && set);
    5555    friend CC * subtractCC(const CC * a, const CC * b);
     
    8484    }
    8585
    86     template <typename itr>
    87     CC * initialize(itr begin, itr end);
     86    CC(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end)
     87    : RE(ClassTypeId::CC)
     88    , UCD::UnicodeSet(begin, end)
     89    {
     90
     91    }
     92
     93    CC(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end)
     94    : RE(ClassTypeId::CC)
     95    , UCD::UnicodeSet(begin, end)
     96    {
     97
     98    }
    8899
    89100};
     
    109120inline codepoint_t hi_codepoint(const CC::iterator i) {
    110121    return hi_codepoint(*i);
    111 }
    112 
    113 template<typename itr>
    114 CC * CC::initialize(itr begin, itr end) {
    115     for (auto i = begin; i != end; ++i) {
    116         insert_range(i->first, i->second);
    117     }
    118     return this;
    119122}
    120123
     
    143146}
    144147
    145 inline CC * makeCC(const std::initializer_list<interval_t> list) {
    146     return makeCC()->initialize(list.begin(), list.end());
     148inline CC * makeCC(std::initializer_list<interval_t> list) {
     149    return new CC(list.begin(), list.end());
    147150}
    148151
    149 inline CC * makeCC(const std::vector<interval_t> & list) {
    150     return makeCC()->initialize(list.begin(), list.end());
     152inline CC * makeCC(std::vector<interval_t> && list) {
     153    return new CC(list.begin(), list.end());
    151154}
    152155
     
    156159
    157160inline CC * subtractCC(const CC * a, const CC * b) {
    158     return makeCC(std::move(*a - *b));
     161    return new CC(std::move(*a - *b));
    159162}
    160163
    161164inline CC * intersectCC(const CC * a, const CC * b) {
    162     return makeCC(std::move(*a & *b));
     165    return new CC(std::move(*a & *b));
    163166}
    164167
  • icGREP/icgrep-devel/icgrep/re/re_parser.cpp

    r4852 r4860  
    531531    embedded = regular_expression_passes(encoding, embedded);
    532532
    533     pablo::PabloFunction * nameSearchFunction = re2pablo_compiler(encoding, embedded);
    534     llvm::Function * nameSearchIR = nullptr;
    535    
     533    pablo::PabloFunction * const nameSearchFunction = re2pablo_compiler(encoding, embedded);
    536534    pablo_function_passes(nameSearchFunction);
    537535    pablo::PabloCompiler pablo_compiler(VectorType::get(IntegerType::get(getGlobalContext(), 64), BLOCK_SIZE/64));
    538     try {
    539         nameSearchIR = pablo_compiler.compile(nameSearchFunction);
    540     }
    541     catch (std::runtime_error e) {
    542         releaseSlabAllocatorMemory();
    543         throw e;
    544     }
     536    llvm::Function * const nameSearchIR = pablo_compiler.compile(nameSearchFunction); // <- may throw error if parsing exception occurs.
    545537
    546538    llvm::ExecutionEngine * engine = JIT_to_ExecutionEngine(nameSearchIR);   
  • icGREP/icgrep-devel/icgrep/re/re_re.cpp

    r4510 r4860  
    33namespace re {
    44RE::Allocator RE::mAllocator;
    5 RE::VectorAllocator RE::mVectorAllocator;
    65}
  • icGREP/icgrep-devel/icgrep/re/re_re.h

    r4829 r4860  
    3939public:
    4040    using Allocator = SlabAllocator<u_int8_t>;
    41     using VectorAllocator = SlabAllocator<RE *>;
     41    using VectorAllocator = Allocator::rebind<RE *>::other;
    4242    enum class ClassTypeId : unsigned {
    4343        Alt
     
    7272
    7373    static Allocator mAllocator;
    74     static VectorAllocator mVectorAllocator;
    7574};
    7675
     
    8382    inline Vector(const ClassTypeId id)
    8483    : RE(id)
    85     , std::vector<RE*, RE::VectorAllocator>(RE::mVectorAllocator)
     84    , std::vector<RE*, RE::VectorAllocator>(reinterpret_cast<VectorAllocator &>(mAllocator))
    8685    {
    8786
     
    8988    inline Vector(const ClassTypeId id, const iterator begin, const iterator end)
    9089    : RE(id)
    91     , std::vector<RE*, RE::VectorAllocator>(begin, end, RE::mVectorAllocator) {
     90    , std::vector<RE*, RE::VectorAllocator>(begin, end, reinterpret_cast<VectorAllocator &>(mAllocator)) {
    9291
    9392    }
Note: See TracChangeset for help on using the changeset viewer.