Changeset 4797


Ignore:
Timestamp:
Sep 27, 2015, 1:32:27 AM (2 years ago)
Author:
nmedfort
Message:

Progress on multi-target UCD compiler.

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

Legend:

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

    r4793 r4797  
    6060endif()
    6161if(USE_BOOST_MMAP)
    62   SET(REQ_BOOST_COMPONENTS ${REQ_BOOST_COMPONENTS} system iostreams filesystem)
     62  SET(REQ_BOOST_COMPONENTS ${REQ_BOOST_COMPONENTS} iostreams filesystem)
    6363endif()
    6464
  • icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.cpp

    r4736 r4797  
    1111
    1212/** ------------------------------------------------------------------------------------------------------------- *
    13  * @brief generateWithDefaultIfHierarchy
    14  * @param set the unicode set to generate
    15  * @param the entry block to the function we're filling
    16  * @return the output stream with a 1-bit in any position of a character in the unicode set
    17  ** ------------------------------------------------------------------------------------------------------------- */
    18 PabloAST * UCDCompiler::generateWithIfHierarchy(const RangeList & ifRanges, const UnicodeSet & set, PabloBuilder & entry) {
     13 * @brief generateRange
     14 ** ------------------------------------------------------------------------------------------------------------- */
     15void UCDCompiler::generateRange(const RangeList & ifRanges, PabloBuilder & entry) {
    1916    // Pregenerate the suffix var outside of the if ranges. The DCE pass will either eliminate it if it's not used or the
    2017    // code sinking pass will move appropriately into an inner if block.
    21     mSuffixVar = mCharacterClassCompiler.compileCC(makeCC(0x80, 0xBF), entry);
    22     return generateWithIfHierarchy(ifRanges, set, 0, CC::UNICODE_MAX, entry);
    23 }
    24 
    25 /** ------------------------------------------------------------------------------------------------------------- *
    26  * @brief generateCharClassDefsInIfHierarchy
     18    CC *  suffix = makeCC(0x80, 0xBF);
     19    assert (!suffix->empty());
     20    mSuffixVar = mCharacterClassCompiler.compileCC(suffix, entry);
     21    generateRange(ifRanges, 0, CC::UNICODE_MAX, entry);
     22}
     23
     24/** ------------------------------------------------------------------------------------------------------------- *
     25 * @brief generateRange
    2726 * @param ifRangeList
    2827 ** ------------------------------------------------------------------------------------------------------------- */
    29 PabloAST * UCDCompiler::generateWithIfHierarchy(const RangeList & ifRanges, const UnicodeSet & set, const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder) {
    30 
    31     PabloAST * target = builder.createZeroes();
     28void UCDCompiler::generateRange(const RangeList & ifRanges, const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder) {
     29
    3230    // Codepoints in unenclosed ranges will be computed unconditionally.
    3331    // Generate them first so that computed subexpressions may be shared
    3432    // with calculations within the if hierarchy.
    35 
    3633    const auto enclosed = rangeIntersect(ifRanges, lo, hi);
    37 
    3834    for (const auto rg : rangeGaps(enclosed, lo, hi)) {
    39         target = generateSubRanges(set, lo_codepoint(rg), hi_codepoint(rg), builder, target);
     35        generateSubRanges(lo_codepoint(rg), hi_codepoint(rg), builder);
    4036    }
    4137
     
    4339    const auto inner = innerRanges(enclosed);
    4440    for (const auto range : outer) {
    45         codepoint_t lo, hi;
    46         std::tie(lo, hi) = range;
    47         if (set.intersects(lo, hi)) {
     41
     42        TargetVector intersectingTargets;
     43        TargetVector nonIntersectingTargets;
     44
     45        // Split our current target list into two sets: the intersecting and non-intersecting ones. Any non-
     46        // intersecting set will be removed from the current map to eliminate the possibility of it being
     47        // considered until after we leave the current range. The intersecting sets are also stored to ensure
     48        // that we know what the original target value was going into this range block so tha we can OR the
     49        // inner value with the outer value.
     50
     51        for (auto ti = mTargetMap.begin(); ti != mTargetMap.end(); ) {           
     52            if (ti->first->intersects(range.first, range.second)) {
     53                intersectingTargets.emplace_back(ti->first, ti->second);
     54                ++ti;
     55            } else {
     56                nonIntersectingTargets.emplace_back(ti->first, ti->second);
     57                ti = mTargetMap.erase(ti);
     58            }
     59        }
     60        if (mTargetMap.size() > 0) {
     61
    4862            PabloBuilder inner_block = PabloBuilder::Create(builder);
    49             PabloAST * inner_target = generateWithIfHierarchy(inner, set, lo, hi, inner_block);
     63
     64            generateRange(inner, range.first, range.second, inner_block);
     65
     66            std::vector<Assign *> targets;
     67            for (auto ti = intersectingTargets.begin(); ti != intersectingTargets.end(); ) {
     68                auto f = mTargetMap.find(ti->first);
     69                assert (f != mTargetMap.end());
     70                if (LLVM_UNLIKELY(isa<Zeroes>(f->second))) {
     71                    ti = intersectingTargets.erase(ti);
     72                    continue;
     73                }
     74                Assign * escapedValue = inner_block.createAssign("m", f->second);
     75                targets.push_back(escapedValue);
     76                f->second = escapedValue;
     77                ++ti;
     78            }
     79
    5080            // If this range is empty, just skip creating the if block
    51             if (LLVM_UNLIKELY(isa<Zeroes>(inner_target))) {
    52                 continue;
    53             }
    54             Assign * matches = inner_block.createAssign("m", inner_target);
    55             builder.createIf(ifTestCompiler(lo, hi, builder), {matches}, inner_block);
    56             target = builder.createOr(target, matches);
    57         }
    58     }
    59 
    60     return target;
    61 }
    62 
    63 /** ------------------------------------------------------------------------------------------------------------- *
    64  * @brief generateCharClassSubDefs
    65  * @param ifRangeList
    66  ** ------------------------------------------------------------------------------------------------------------- */
    67 PabloAST * UCDCompiler::generateSubRanges(const UnicodeSet & set, const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder, PabloAST * target) {
    68     const auto range = rangeIntersect(set, lo, hi);
    69     // Divide by UTF-8 length, separating out E0, ED, F0 and F4 ranges
    70     const std::array<interval_t, 9> ranges =
    71         {{{0, 0x7F}, {0x80, 0x7FF}, {0x800, 0xFFF}, {0x1000, 0xD7FF}, {0xD800, 0xDFFF},
    72          {0xE000, 0xFFFF}, {0x10000, 0x3FFFF}, {0x40000, 0xFFFFF}, {0x100000, 0x10FFFF}}};
    73     for (auto r : ranges) {
    74         const auto subrange = rangeIntersect(range, lo_codepoint(r), hi_codepoint(r));
    75         target = sequenceGenerator(std::move(subrange), 1, builder, target, nullptr);
    76     }
    77     return target;
     81            if (targets.size() > 0) {
     82                builder.createIf(ifTestCompiler(range.first, range.second, builder), std::move(targets), inner_block);
     83                for (const auto ti : intersectingTargets) {
     84                    auto f = mTargetMap.find(ti.first);
     85                    assert (f != mTargetMap.end());
     86                    assert (isa<Assign>(f->second));
     87                    f->second = builder.createOr(ti.second, f->second);
     88                }
     89            }
     90        }
     91        for (Target t : nonIntersectingTargets) {
     92            mTargetMap.insert(t);
     93        }
     94    }
     95}
     96
     97/** ------------------------------------------------------------------------------------------------------------- *
     98 * @brief generateSubRanges
     99 ** ------------------------------------------------------------------------------------------------------------- */
     100void UCDCompiler::generateSubRanges(const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder) {
     101    for (Target & t : mTargetMap) {
     102        const auto range = rangeIntersect(*t.first, lo, hi);
     103        PabloAST * target = t.second;
     104        // Divide by UTF-8 length, separating out E0, ED, F0 and F4 ranges
     105        const std::array<interval_t, 9> ranges =
     106            {{{0, 0x7F}, {0x80, 0x7FF}, {0x800, 0xFFF}, {0x1000, 0xD7FF}, {0xD800, 0xDFFF},
     107             {0xE000, 0xFFFF}, {0x10000, 0x3FFFF}, {0x40000, 0xFFFFF}, {0x100000, 0x10FFFF}}};
     108        for (auto r : ranges) {
     109            const auto subrange = rangeIntersect(range, lo_codepoint(r), hi_codepoint(r));
     110            target = sequenceGenerator(std::move(subrange), 1, builder, target, nullptr);
     111        }
     112        t.second = target;
     113    }
    78114}
    79115
     
    88124PabloAST * UCDCompiler::sequenceGenerator(const RangeList && ranges, const unsigned byte_no, PabloBuilder & builder, PabloAST * target, PabloAST * prefix) {
    89125
    90     if (LLVM_LIKELY(!ranges.empty())) {
     126    if (LLVM_LIKELY(ranges.size() > 0)) {
    91127
    92128        codepoint_t lo, hi;
     
    100136            target = sequenceGenerator(std::move(rangeIntersect(ranges, lo, mid)), byte_no, builder, target, prefix);
    101137            target = sequenceGenerator(std::move(rangeIntersect(ranges, mid + 1, hi)), byte_no, builder, target, prefix);
    102         }
    103         else if (min == byte_no) {
     138        } else if (min == byte_no) {
    104139            // We have a single byte remaining to match for all code points in this CC.
    105140            // Use the byte class compiler to generate matches for these codepoints.
     
    110145            }
    111146            target = builder.createOr(target, var);
    112         }
    113         else {
     147        } else {
    114148            for (auto rg : ranges) {
    115149                codepoint_t lo, hi;
     
    122156                        target = sequenceGenerator(lo, mid, byte_no, builder, target, prefix);
    123157                        target = sequenceGenerator(mid + 1, hi, byte_no, builder, target, prefix);
    124                     }
    125                     else if (!UTF8_Encoder::isHighCodePointAfterByte(hi, byte_no)) {
     158                    } else if (!UTF8_Encoder::isHighCodePointAfterByte(hi, byte_no)) {
    126159                        const codepoint_t mid = hi & ~((1 << (6 * (min - byte_no))) - 1);
    127160                        target = sequenceGenerator(lo, mid - 1, byte_no, builder, target, prefix);
    128161                        target = sequenceGenerator(mid, hi, byte_no, builder, target, prefix);
    129                     }
    130                     else { // we have a prefix group of type (a)
     162                    } else { // we have a prefix group of type (a)
    131163                        PabloAST * var = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), builder);
    132164                        if (byte_no > 1) {
     
    185217        PabloAST * cc = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), builder);
    186218        target = builder.createAnd(cc, target);
    187     }
    188     else if (lo_byte == hi_byte) {
     219    } else if (lo_byte == hi_byte) {
    189220        PabloAST * cc = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), builder);
    190221        target = builder.createAnd(cc, target);
    191222        target = builder.createAdvance(target, 1);
    192223        target = ifTestCompiler(lo, hi, byte_no + 1, builder, target);
    193     }
    194     else if (!at_hi_boundary) {
     224    } else if (!at_hi_boundary) {
    195225        const auto mid = UTF8_Encoder::minCodePointWithCommonBytes(hi, byte_no);
    196226        PabloAST * e1 = ifTestCompiler(lo, mid - 1, byte_no, builder, target);
    197227        PabloAST * e2 = ifTestCompiler(mid, hi, byte_no, builder, target);
    198228        target = builder.createOr(e1, e2);
    199     }
    200     else {
     229    } else {
    201230        const auto mid = UTF8_Encoder::maxCodePointWithCommonBytes(lo, byte_no);
    202231        PabloAST * e1 = ifTestCompiler(lo, mid, byte_no, builder, target);
     
    272301        if (LLVM_UNLIKELY(list.empty())) {
    273302            gaps.emplace_back(lo, hi);
    274         }
    275         else {
     303        } else {
    276304            codepoint_t cp = lo;
    277305            for (const auto & i : list) {
    278306                if (hi_codepoint(i) < cp) {
    279307                    continue;
    280                 }
    281                 else if (lo_codepoint(i) > cp) {
     308                } else if (lo_codepoint(i) > cp) {
    282309                    gaps.emplace_back(cp, lo_codepoint(i) - 1);
    283                 }
    284                 else if (hi_codepoint(i) >= hi) {
     310                } else if (hi_codepoint(i) >= hi) {
    285311                    continue;
    286312                }
     
    315341/** ------------------------------------------------------------------------------------------------------------- *
    316342 * @brief innerRanges
    317  * @param list
    318343 ** ------------------------------------------------------------------------------------------------------------- */
    319344UCDCompiler::RangeList UCDCompiler::innerRanges(const RangeList & list) {
     
    323348            if (hi_codepoint(*j) <= hi_codepoint(*i)) {
    324349                ranges.emplace_back(lo_codepoint(*j), hi_codepoint(*j));
    325             }
    326             else {
     350            } else {
    327351                i = j;
    328352            }
     
    330354    }
    331355    return ranges;
     356}
     357
     358/** ------------------------------------------------------------------------------------------------------------- *
     359 * @brief addTarget
     360 ** ------------------------------------------------------------------------------------------------------------- */
     361inline void UCDCompiler::addTarget(const UnicodeSet & set) {
     362#ifdef USE_BOOST
     363    mTargetMap.emplace(&set, PabloBlock::createZeroes());
     364#else
     365    mTargetMap.insert(std::make_pair(&set, PabloBlock::createZeroes()));
     366#endif
    332367}
    333368
     
    427462        {0x10000, 0x10FFFF}};
    428463
    429     return generateWithIfHierarchy(defaultIfHierachy, set, entry);
     464    addTarget(set);
     465    generateRange(defaultIfHierachy, entry);
     466    return mTargetMap[&set];
    430467}
    431468
     
    437474 ** ------------------------------------------------------------------------------------------------------------- */
    438475PabloAST * UCDCompiler::generateWithoutIfHierarchy(const UnicodeSet & set, PabloBuilder & entry) {
    439 
    440476    const RangeList defaultIfHierachy = {{0x10000, 0x10FFFF}};
    441 
    442     return generateWithIfHierarchy(defaultIfHierachy, set, entry);
     477    addTarget(set);
     478    generateRange(defaultIfHierachy, entry);
     479    return mTargetMap[&set];
    443480}
    444481
  • icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.hpp

    r4736 r4797  
    22#define UCDCOMPILER_HPP
    33
     4#include <re/re_cc.h>
    45#include <vector>
    5 #include <re/re_cc.h>
     6#ifdef USE_BOOST
     7#include <boost/container/flat_map.hpp>
     8#else
     9#include <unordered_map>
     10#endif
    611
    712namespace cc {
     
    2530    using codepoint_t = re::codepoint_t;
    2631    using RangeList = std::vector<re::interval_t>;
     32    #ifdef USE_BOOST
     33    using TargetMap = boost::container::flat_map<const UnicodeSet *, PabloAST *>;
     34    #else
     35    using TargetMap = std::unordered_map<const UnicodeSet *, PabloAST *>;
     36    #endif
     37    using Target = TargetMap::value_type;
     38    using TargetVector = std::vector<Target>;
    2739
    2840public:
     
    3345    PabloAST * generateWithoutIfHierarchy(const UnicodeSet & set, PabloBuilder & entry);
    3446
    35     PabloAST * generateWithIfHierarchy(const RangeList & ifRanges, const UnicodeSet & set, PabloBuilder & entry);
    36 
    3747protected:
    3848
    39     PabloAST * generateWithIfHierarchy(const RangeList & ifRanges, const UnicodeSet & set, const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder);
     49    void generateRange(const RangeList & ifRanges, PabloBuilder & entry);
    4050
    41     PabloAST * generateSubRanges(const UnicodeSet & set, const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder, PabloAST * target);
     51    void generateRange(const RangeList & ifRanges, const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder);
     52
     53    void generateSubRanges(const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder);
    4254
    4355    PabloAST * sequenceGenerator(const RangeList && ranges, const unsigned byte_no, PabloBuilder & builder, PabloAST * target, PabloAST * prefix);
     
    5062
    5163    PabloAST * makePrefix(const codepoint_t cp, const unsigned byte_no, PabloBuilder & builder, PabloAST * prefix);
     64
     65    void addTarget(const UnicodeSet & set);
    5266
    5367    static RangeList byteDefinitions(const RangeList & list, const unsigned byte_no);
     
    6579    cc::CC_Compiler &       mCharacterClassCompiler;
    6680    PabloAST *              mSuffixVar;
     81    TargetMap               mTargetMap;
    6782};
    6883
  • icGREP/icgrep-devel/icgrep/cc/cc_compiler.cpp

    r4788 r4797  
    133133
    134134template<typename PabloBlockOrBuilder>
    135 PabloAST * CC_Compiler::bit_pattern_expr(const unsigned pattern, unsigned selected_bits, PabloBlockOrBuilder &pb)
    136 {
    137     if (selected_bits == 0) {
    138         return pb.createOnes();
    139     }
    140 
    141     std::vector<PabloAST*> bit_terms;
    142     for (unsigned i = 0; selected_bits; ++i) {
    143         unsigned test_bit = static_cast<unsigned>(1) << i;
    144         if ((selected_bits & test_bit) != 0) {
    145             if ((pattern & test_bit) == 0) {
    146                 bit_terms.push_back(pb.createNot(getBasisVar(i)));
    147             }
    148             else {
    149                 bit_terms.push_back(getBasisVar(i));
    150             }
    151         }
    152         else {
    153             bit_terms.push_back(pb.createOnes());
    154         }
    155         selected_bits &= ~test_bit;
    156     }
    157 
    158     if (bit_terms.size() > 1) {
    159         //Reduce the list so that all of the expressions are contained within a single expression.
    160         std::vector<PabloAST*> new_terms;
    161         new_terms.reserve(bit_terms.size() / 2);
    162         do {
    163             for (auto i = 0; i < (bit_terms.size() / 2); i++) {
    164                 new_terms.push_back(pb.createAnd(bit_terms[(2 * i) + 1], bit_terms[2 * i]));
    165             }
    166             if (bit_terms.size() % 2 == 1) {
    167                 new_terms.push_back(bit_terms[bit_terms.size() - 1]);
    168             }
    169             bit_terms.swap(new_terms);
    170             new_terms.clear();
    171         }
    172         while (bit_terms.size() > 1);
    173     }
    174     return bit_terms[0];
     135PabloAST * CC_Compiler::bit_pattern_expr(const unsigned pattern, unsigned selected_bits, PabloBlockOrBuilder & pb) {
     136    if (LLVM_UNLIKELY(selected_bits == 0)) {
     137        return PabloBlock::createOnes();
     138    } else {
     139        std::vector<PabloAST*> terms;
     140        for (unsigned i = 0; selected_bits; ++i) {
     141            unsigned test_bit = static_cast<unsigned>(1) << i;
     142            PabloAST * term = PabloBlock::createOnes();
     143            if (selected_bits & test_bit) {
     144                term = getBasisVar(i);
     145                if ((pattern & test_bit) == 0) {
     146                    term = pb.createNot(term);
     147                }
     148                selected_bits ^= test_bit;
     149            }
     150            terms.push_back(term);
     151        }
     152        if (terms.size() > 1) {
     153            //Reduce the list so that all of the expressions are contained within a single expression.
     154            std::vector<PabloAST*> temp;
     155            temp.reserve(terms.size());
     156            do {
     157                for (unsigned i = 0; i < (terms.size() / 2); i++) {
     158                    temp.push_back(pb.createAnd(terms[2 * i], terms[(2 * i) + 1]));
     159                }
     160                if (terms.size() % 2 == 1) {
     161                    temp.push_back(terms.back());
     162                }
     163                terms.swap(temp);
     164                temp.clear();
     165            }
     166            while (terms.size() > 1);
     167        }
     168        assert (terms.size() == 1);
     169        return terms.front();
     170    }
    175171}
    176172
     
    269265
    270266inline Var * CC_Compiler::getBasisVar(const int i) const {
     267    assert (i >= 0 && i < mEncoding.getBits());
    271268    return mBasisBit[mEncoding.getBits() - i - 1];
    272269}
  • icGREP/icgrep-devel/icgrep/do_grep.cpp

    r4795 r4797  
    7070            mLineNum++;
    7171        }
     72        assert (buffer + line_end < mFileBuffer + mFileSize);
    7273        if (mShowFileNameOption) {
    7374            out << mFileName << ':';
     
    7778        }
    7879        if ((buffer[line_start] == 0xA) && (line_start != line_end)) {
    79             // The line "starts" on the LF of a CRLF.  Really the end of the last line.
     80            // The LF of a CRLF.  Really the end of the last line.
    8081            line_start++;
    81         }
    82         if (buffer + line_end == mFileBuffer + mFileSize) {
    83             // The match position is at end-of-file.   We have a final unterminated line.
    84             out.write(&buffer[line_start], line_end - line_start);
    85             if (mNormalizeLineBreaksOption) {
    86               out << '\n';  // terminate it
    87             }
    88             return line_end;
    8982        }
    9083        unsigned char end_byte = (unsigned char)buffer[line_end];
     
    10194        }
    10295        else {
    103             if (end_byte == 0x0D) {
     96            if (end_byte == 0x0) {
     97                // This must be a sentinel byte position at the end of file.
     98                // Do not write it.
     99                line_end--;
     100            } else if (end_byte == 0x0D) {
    104101                // Check for line_end on first byte of CRLF;  note that we don't
    105102                // want to access past the end of buffer.
     
    270267    //Final Partial Block (may be empty, but there could be carries pending).
    271268   
    272    
    273269    const auto EOF_mask = bitblock::srl(simd<1>::constant<1>(), convert(BLOCK_SIZE - remaining));
    274270   
    275     if (remaining == 0) {  // No data, we may be at a page boundary.   Do not access memory.
    276         basis_bits.bit_0 = simd<1>::constant<0>();
    277         basis_bits.bit_1 = simd<1>::constant<0>();
    278         basis_bits.bit_2 = simd<1>::constant<0>();
    279         basis_bits.bit_3 = simd<1>::constant<0>();
    280         basis_bits.bit_4 = simd<1>::constant<0>();
    281         basis_bits.bit_5 = simd<1>::constant<0>();
    282         basis_bits.bit_6 = simd<1>::constant<0>();
    283         basis_bits.bit_7 = simd<1>::constant<0>();
    284     }
    285     else { // At least 1 byte, so we are not at a page boundary yet, safe to access a full block.
    286         s2p_do_final_block(reinterpret_cast<BytePack *>(mFileBuffer + (blk * BLOCK_SIZE) + (segment * SEGMENT_SIZE)), basis_bits, EOF_mask);
    287     }
     271    s2p_do_final_block(reinterpret_cast<BytePack *>(mFileBuffer + (blk * BLOCK_SIZE) + (segment * SEGMENT_SIZE)), basis_bits, EOF_mask);
    288272
    289273    if (finalLineIsUnterminated()) {
  • icGREP/icgrep-devel/icgrep/generate_predefined_ucd_functions.cpp

    r4788 r4797  
    242242        (*LongestDependenceChainFile) << name;
    243243    }
    244     // std::cerr << name << std::endl;
     244    #ifndef NDEBUG
     245    std::cerr << name << std::endl;
     246    #endif
    245247    PabloFunction * function = PabloFunction::Create(std::move(name), 8, 1);
    246248    Encoding encoding(Encoding::Type::UTF_8, 8);
     
    259261    function->setResult(0, builder.createAssign("matches", result));
    260262    // Optimize it at the pablo level
     263    PabloVerifier::verify(*function, "creation");
    261264    Simplifier::optimize(*function);
    262265    CodeSinking::optimize(*function);
    263 
    264266    #ifdef ENABLE_MULTIPLEXING
    265267    BDDMinimizationPass::optimize(*function);
     
    284286    #endif
    285287    if (EnableReassociation) {
    286         BooleanReassociationPass::optimize(*function);
     288        BooleanReassociationPass::optimize(*function);       
    287289    }
    288290
  • icGREP/icgrep-devel/icgrep/icgrep-devel.config

    r4788 r4797  
     1#define USE_BOOST
    12#define USE_BOOST_MMAP
  • icGREP/icgrep-devel/icgrep/icgrep.cpp

    r4788 r4797  
    4646#include <re/printer_re.h>
    4747#include <pablo/printer_pablos.h>
     48#include <pablo/analysis/pabloverifier.hpp>
    4849
    4950#include "do_grep.h"
     
    249250    if (EnableMultiplexing) {
    250251        pablo::BDDMinimizationPass::optimize(*function);
    251         pablo::AutoMultiplexing::optimize(*function);       
     252        pablo::AutoMultiplexing::optimize(*function);
    252253    }   
    253254    if (EnableReassociation) {
     
    357358       
    358359        pablo::PabloFunction * function = re2pablo_compiler(encoding, re_ast);
     360        #ifndef NDEBUG
     361        pablo::PabloVerifier::verify(*function, "creation");
     362        #endif
    359363
    360364        pablo_function_passes(function);
  • icGREP/icgrep-devel/icgrep/pablo/analysis/pabloverifier.cpp

    r4775 r4797  
    55#include <iostream>
    66#include <boost/container/flat_set.hpp>
     7#include <boost/container/flat_map.hpp>
     8
     9using namespace boost::container;
    710
    811namespace pablo {
    912
     13using ScopeSet = flat_set<const PabloBlock *>;
     14
     15/** ------------------------------------------------------------------------------------------------------------- *
     16 * @brief verifyUseDefInformation
     17 ** ------------------------------------------------------------------------------------------------------------- */
     18template<typename VectorType>
     19bool checkVector(const Statement * value, const VectorType & vector) {
     20    for (auto escapedValue : vector) {
     21        if (escapedValue == value) {
     22            return false;
     23        }
     24    }
     25    return true;
     26}
     27
     28void verifyUseDefInformation(const PabloBlock & block, const ScopeSet & validScopes) {
     29    for (const Statement * stmt : block) {
     30
     31        for (const PabloAST * use : stmt->users()) {
     32            if (LLVM_LIKELY(isa<Statement>(use))) {
     33                const Statement * const user = cast<Statement>(use);
     34                // test whether this user is in a block in the program
     35                if (LLVM_UNLIKELY(validScopes.count(user->getParent()) == 0)) {
     36                    std::string tmp;
     37                    raw_string_ostream str(tmp);
     38                    PabloPrinter::print(user, "PabloVerifier: use-def error: ", str);
     39                    PabloPrinter::print(stmt, " is a user of ", str);
     40                    if (user->getParent() == nullptr) {
     41                        str << " but is not in any scope.";
     42                    } else {
     43                        str << " but is in a deleted scope.";
     44                    }
     45                    throw std::runtime_error(str.str());
     46                }
     47                bool notFound = true;
     48                for (unsigned i = 0; i != user->getNumOperands(); ++i) {
     49                    if (user->getOperand(i) == stmt) {
     50                        notFound = false;
     51                        break;
     52                    }
     53                }
     54                if (LLVM_UNLIKELY(notFound)) {
     55                    if (const If * ifNode = dyn_cast<If>(stmt)) {
     56                        notFound = checkVector(user, ifNode->getDefined());
     57                    } else if (const If * ifNode = dyn_cast<If>(user)) {
     58                        notFound = checkVector(stmt, ifNode->getDefined());
     59                    } else if (const While * whileNode = dyn_cast<While>(stmt)) {
     60                        notFound = checkVector(user, whileNode->getVariants());
     61                    } else if (const While * whileNode = dyn_cast<While>(user)) {
     62                        notFound = checkVector(stmt, whileNode->getVariants());
     63                    } else if (isa<Next>(stmt) && isa<Assign>(use)) {
     64                        notFound = (use != cast<Next>(stmt)->getInitial());
     65                    }
     66                    if (LLVM_UNLIKELY(notFound)) {
     67                        std::string tmp;
     68                        raw_string_ostream str(tmp);
     69                        str << "PabloVerifier: use-def error: ";
     70                        PabloPrinter::print(stmt, str);
     71                        str << " is not a definition of ";
     72                        PabloPrinter::print(use, str);
     73                        throw std::runtime_error(str.str());
     74                    }
     75                }
     76            }
     77        }
     78        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     79            const PabloAST * const def = stmt->getOperand(i);
     80            bool notFound = true;
     81            for (const PabloAST * use : def->users()) {
     82                if (use == stmt) {
     83                    notFound = false;
     84                    break;
     85                }
     86            }
     87            if (LLVM_UNLIKELY(notFound)) {
     88                std::string tmp;
     89                raw_string_ostream str(tmp);
     90                PabloPrinter::print(stmt, "PabloVerifier: def-use error: ", str);
     91                str << " is not a user of ";
     92                PabloPrinter::print(def, str);
     93                throw std::runtime_error(str.str());
     94            }
     95        }
     96        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     97            verifyUseDefInformation(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
     98        }
     99    }
     100}
     101
     102void gatherValidScopes(const PabloBlock & block, ScopeSet & validScopes) {
     103    validScopes.insert(&block);
     104    for (const Statement * stmt : block) {
     105        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     106            gatherValidScopes(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), validScopes);
     107        }
     108    }
     109}
     110
     111void verifyUseDefInformation(const PabloFunction & function) {
     112    ScopeSet validScopes;
     113    gatherValidScopes(function.getEntryBlock(), validScopes);
     114    verifyUseDefInformation(function.getEntryBlock(), validScopes);
     115}
     116
     117/** ------------------------------------------------------------------------------------------------------------- *
     118 * @brief verifyProgramStructure
     119 ** ------------------------------------------------------------------------------------------------------------- */
     120void verifyProgramStructure(const PabloBlock & block) {
     121    const Statement * prev = nullptr;
     122    for (const Statement * stmt : block) {
     123        if (LLVM_UNLIKELY(stmt->getPrevNode() != prev)) {
     124            std::string tmp;
     125            raw_string_ostream str(tmp);
     126            PabloPrinter::print(stmt, "PabloVerifier: structure error: ", str);
     127            str << " succeeds ";
     128            PabloPrinter::print(prev, str);
     129            str << " but expects to preceed  ";
     130            PabloPrinter::print(stmt->getPrevNode(), str);
     131            throw std::runtime_error(str.str());
     132        }
     133        prev = stmt;
     134        if (LLVM_UNLIKELY(stmt->getParent() != &block)) {
     135            std::string tmp;
     136            raw_string_ostream str(tmp);
     137            PabloPrinter::print(stmt, "PabloVerifier: structure error: ", str);
     138            str << " is not contained in its reported scope block";
     139            throw std::runtime_error(str.str());
     140        }
     141        if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     142            const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     143            if (LLVM_UNLIKELY(nested.getParent() != &block)) {
     144                std::string tmp;
     145                raw_string_ostream str(tmp);
     146                str << "PabloVerifier: structure error: body of ";
     147                PabloPrinter::print(stmt, str);
     148                str << " is not nested within the expected scope block";
     149                throw std::runtime_error(str.str());
     150            }
     151            const Statement * misreportedEscapingValue = nullptr;
     152            if (isa<If>(stmt)) {
     153                for (const Assign * def : cast<If>(stmt)->getDefined()) {
     154                    if (def->getParent() != &block) {
     155                        misreportedEscapingValue = def;
     156                        break;
     157                    }
     158                }
     159            } else {
     160                for (const Next * var : cast<While>(stmt)->getVariants()) {
     161                    if (var->getParent() != &block) {
     162                        misreportedEscapingValue = var;
     163                        break;
     164                    }
     165                }
     166            }
     167            if (misreportedEscapingValue) {
     168                std::string tmp;
     169                raw_string_ostream str(tmp);
     170                str << "PabloVerifier: structure error: ";
     171                PabloPrinter::print(misreportedEscapingValue, str);
     172                str << " is not contained within the body of ";
     173                PabloPrinter::print(stmt, str);
     174                throw std::runtime_error(str.str());
     175            }
     176            verifyProgramStructure(nested);
     177        }
     178    }
     179}
     180
     181inline void verifyProgramStructure(const PabloFunction & function) {
     182    verifyProgramStructure(function.getEntryBlock());
     183}
     184
     185/** ------------------------------------------------------------------------------------------------------------- *
     186 * @brief isTopologicallyOrdered
     187 ** ------------------------------------------------------------------------------------------------------------- */
    10188struct OrderingVerifier {
    11189    OrderingVerifier() : mParent(nullptr) {}
     
    27205};
    28206
    29 void isTopologicallyOrdered(const PabloBlock & block, const OrderingVerifier & parent, const bool ignoreUnusedStatements) {
     207void isTopologicallyOrdered(const PabloBlock & block, const OrderingVerifier & parent) {
    30208    OrderingVerifier ov(parent);
    31     const Statement * previousStatement = nullptr;
    32     for (const Statement * stmt : block) {
    33         if (stmt->getPrevNode() != previousStatement) {
    34             // TODO: make this actually test whether the operand is ever defined,
    35             // or if it was defined in a scope that cannot be reached?
    36             std::string tmp;
    37             raw_string_ostream str(tmp);
    38             PabloPrinter::print(stmt, "PabloVerifier: ", str);
    39             str << " is not preceeded by the expected statement!";
    40             throw std::runtime_error(str.str());
    41         }
    42         previousStatement = stmt;
    43         if (stmt->getNumUses() == 0 && ignoreUnusedStatements) {
    44             continue;
    45         }
     209    for (const Statement * stmt : block) {
    46210        if (LLVM_UNLIKELY(isa<While>(stmt))) {
    47             isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov, ignoreUnusedStatements);
     211            isTopologicallyOrdered(cast<While>(stmt)->getBody(), ov);
    48212            for (const Next * var : cast<While>(stmt)->getVariants()) {
    49213                ov.insert(var);
     
    51215        }
    52216        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    53             const PabloAST * op = stmt->getOperand(i);
    54             if ((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == false) {
     217            const PabloAST * const op = stmt->getOperand(i);
     218            if (LLVM_UNLIKELY((isa<Statement>(op) || isa<Var>(op)) && ov.count(op) == 0)) {
    55219                // TODO: make this actually test whether the operand is ever defined,
    56220                // or if it was defined in a scope that cannot be reached?
     
    65229        ov.insert(stmt);
    66230        if (LLVM_UNLIKELY(isa<If>(stmt))) {
    67             isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov, ignoreUnusedStatements);
     231            isTopologicallyOrdered(cast<If>(stmt)->getBody(), ov);
    68232            for (const Assign * def : cast<If>(stmt)->getDefined()) {
    69233                ov.insert(def);
     
    73237}
    74238
    75 void isTopologicallyOrdered(const PabloFunction & function, const bool ignoreUnusedStatements) {
     239void isTopologicallyOrdered(const PabloFunction & function) {
    76240    OrderingVerifier ov;
    77241    for (unsigned i = 0; i != function.getNumOfParameters(); ++i) {
    78242        ov.insert(function.getParameter(i));
    79243    }
    80     isTopologicallyOrdered(function.getEntryBlock(), ov, ignoreUnusedStatements);
    81 }
    82 
    83 void PabloVerifier::verify(const PabloFunction & function, const bool ignoreUnusedStatements) {
     244    isTopologicallyOrdered(function.getEntryBlock(), ov);
     245}
     246
     247void PabloVerifier::verify(const PabloFunction & function, const std::string location) {
    84248    try {
    85         isTopologicallyOrdered(function, ignoreUnusedStatements);
     249        verifyProgramStructure(function);
     250        verifyUseDefInformation(function);
     251        isTopologicallyOrdered(function);
    86252    } catch(std::runtime_error err) {
    87253        raw_os_ostream out(std::cerr);
    88254        PabloPrinter::print(function.getEntryBlock().statements(), out);
    89255        out.flush();
    90         throw err;
    91     }
    92 }
    93 
    94 }
     256        if (location.empty()) {
     257            throw err;
     258        } else {
     259            throw std::runtime_error(std::string(err.what()) + " @ " + location);
     260        }
     261    }
     262}
     263
     264}
  • icGREP/icgrep-devel/icgrep/pablo/analysis/pabloverifier.hpp

    r4771 r4797  
    11#ifndef PABLOVERIFIER_HPP
    22#define PABLOVERIFIER_HPP
     3
     4#include <string>
    35
    46namespace pablo {
     
    810class PabloVerifier {
    911public:
    10     static void verify(const PabloFunction & function, const bool ignoreUnusedStatements = true);
    11 private:
    12 
     12    static void verify(const PabloFunction & function, const std::string location = "");
    1313};
    1414
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp

    r4792 r4797  
    319319   
    320320   
    321 // Use field size 32 for BLOCK_SIZE 256, so that signmasks are i8.
    322 #if (BLOCK_SIZE==256)
    323 //#define PARALLEL_LONG_ADD
    324 #define PARALLEL_LONG_ADD_DIGIT_SIZE 32
    325 #endif
    326    
    327321/* Methods for getting and setting individual carry values. */
    328322   
     
    340334void CarryManager::setCarryOpCarryOut(unsigned localIndex, Value * carry_out_strm) {
    341335    unsigned posn = carryOpPosition(localIndex);
    342 #ifndef PARALLEL_LONG_ADD
    343336    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
    344337        extractAndSaveCarryOutBits(carry_out_strm, posn, 1);
     
    351344        }
    352345    }
    353 #else
    354     if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
    355         // Carry is at low bit position
    356         unsigned packIndex = posn / mPACK_SIZE;
    357         unsigned packOffset = posn % mPACK_SIZE;
    358         Value * field = mBuilder->CreateZExt(carry_out_strm, mBuilder->getIntNTy(mPACK_SIZE));
    359         if (packOffset != 0) {
    360             field = mBuilder->CreateShl(field, mBuilder->getInt64(packOffset));
    361         }
    362         if (mCarryOutPack[packIndex] == nullptr) {
    363             mCarryOutPack[packIndex] = field;
    364         }
    365         else {
    366             mCarryOutPack[packIndex] = mBuilder->CreateOr(mCarryOutPack[packIndex], field);
    367         }       
    368     }
    369     else {
    370         Value * carry_bit = mBuilder->CreateZExt(carry_out_strm, mBuilder->getIntNTy(BLOCK_SIZE));
    371         mCarryOutPack[posn] = mBuilder->CreateBitCast(carry_bit, mBitBlockType);
    372         if (mCarryInfo->getWhileDepth() == 0) {
    373             storeCarryPack(posn);
    374         }
    375     }
    376 
    377    
    378 #endif
    379 }
    380 
    381    
    382    
     346}
     347
    383348Value* CarryManager::genShiftLeft64(Value* e) {
    384349    Value* i128_val = mBuilder->CreateBitCast(e, mBuilder->getIntNTy(BLOCK_SIZE));
     
    386351}
    387352
    388 Value* MatchStar(IRBuilder<> * b, Value * m, Value * c) {
    389     return b->CreateOr(b->CreateXor(b->CreateAdd(b->CreateAnd(m, c), c), c), m);
    390 }
    391        
    392353Value * CarryManager::addCarryInCarryOut(int localIndex, Value* e1, Value* e2) {
    393354#if (BLOCK_SIZE == 128)
     
    404365    setCarryOpCarryOut(localIndex, carry_out_strm);
    405366    return sum;
    406 #elif (defined(PARALLEL_LONG_ADD))
     367#else
    407368    //BLOCK_SIZE == 256, there is no other implementation
    408     Type * longAddVectorType = VectorType::get(mBuilder->getIntNTy(PARALLEL_LONG_ADD_DIGIT_SIZE), BLOCK_SIZE/PARALLEL_LONG_ADD_DIGIT_SIZE);
    409     Type * longAddBitMaskIntegerType = mBuilder->getIntNTy(BLOCK_SIZE/PARALLEL_LONG_ADD_DIGIT_SIZE);
    410     Type * longAddBitMaskVectorType = VectorType::get(mBuilder->getIntNTy(1), BLOCK_SIZE/PARALLEL_LONG_ADD_DIGIT_SIZE);
    411     // double the mask size to allow room for carry-out.
    412     Type * longAddBitMaskManipulationType = mBuilder->getIntNTy(2 * BLOCK_SIZE/PARALLEL_LONG_ADD_DIGIT_SIZE);
    413     Value * all_ones = Constant::getAllOnesValue(longAddVectorType);
    414     Value * carryin = iBuilder->mvmd_extract(2 * BLOCK_SIZE/PARALLEL_LONG_ADD_DIGIT_SIZE, getCarryOpCarryIn(localIndex), 0);
    415     Value * carrygen = mBuilder->CreateAnd(e1, e2, "carrygen");
    416     Value * carryprop = mBuilder->CreateOr(e1, e2, "carryprop");
    417     // Sum individual digits.
    418     Value * digitsum = iBuilder->simd_add(PARALLEL_LONG_ADD_DIGIT_SIZE, e1, e2);
    419     Value * digitcarry = mBuilder->CreateOr(carrygen, mBuilder->CreateAnd(carryprop, mBuilder->CreateNot(digitsum)));
    420     Value * carry_mask = mBuilder->CreateZExt(iBuilder->hsimd_signmask(PARALLEL_LONG_ADD_DIGIT_SIZE, digitcarry), longAddBitMaskManipulationType);
    421     Value * bubble_fields = iBuilder->simd_eq(PARALLEL_LONG_ADD_DIGIT_SIZE, digitsum, all_ones);
    422     Value * bubble_mask = mBuilder->CreateZExt(iBuilder->hsimd_signmask(PARALLEL_LONG_ADD_DIGIT_SIZE, bubble_fields), longAddBitMaskManipulationType);
    423     Value * carry_markers = mBuilder->CreateAdd(mBuilder->CreateAdd(carry_mask, carry_mask), carryin); 
    424     Value * increments = MatchStar(mBuilder, carry_markers, bubble_mask);
    425     Value * carry_out = mBuilder->CreateLShr(increments, BLOCK_SIZE/PARALLEL_LONG_ADD_DIGIT_SIZE);
    426     Value * spread = mBuilder->CreateZExt(mBuilder->CreateBitCast(mBuilder->CreateTrunc(increments, longAddBitMaskIntegerType), longAddBitMaskVectorType), longAddVectorType);
    427     Value* sum = iBuilder->simd_add(PARALLEL_LONG_ADD_DIGIT_SIZE, digitsum, spread);
    428     setCarryOpCarryOut(localIndex, carry_out);
    429     return sum;
    430 #else
    431     //BLOCK_SIZE == 256, default implementation
    432369    Value * carryq_value = getCarryOpCarryIn(localIndex);
    433370    Value* carrygen = mBuilder->CreateAnd(e1, e2, "carrygen");
     
    522459 }
    523460 */
     461
    524462   
    525463Value * CarryManager::longAdvanceCarryInCarryOut(int localIndex, unsigned shift_amount, Value * carry_out) {
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r4788 r4797  
    99namespace pablo {
    1010
    11 Zeroes * const PabloBlock::mZeroes = new Zeroes();
    12 
    13 Ones * const PabloBlock::mOnes = new Ones();
     11Zeroes PabloBlock::mZeroes;
     12
     13Ones PabloBlock::mOnes;
    1414
    1515inline PabloAST * PabloBlock::renameNonNamedNode(PabloAST * expr, const std::string && prefix) {
     
    339339    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
    340340        return renameNonNamedNode(expr2, std::move(prefix));
    341     }
    342     if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
     341    } else if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
    343342        return renameNonNamedNode(expr1, std::move(prefix));
    344     }
    345     else if (Not * not1 = dyn_cast<Not>(expr1)) {
     343    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    346344        // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
    347345        return createNot(createAnd(not1->getExpr(), createNot(expr2)), prefix);
    348     }
    349     else if (Not * not2 = dyn_cast<Not>(expr2)) {
     346    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
    350347        // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
    351348        return createNot(createAnd(not2->getExpr(), createNot(expr1)), prefix);
    352     }
    353     else if (And * and1 = dyn_cast<And>(expr1)) {
     349    } else if (And * and1 = dyn_cast<And>(expr1)) {
    354350        if (And * and2 = dyn_cast<And>(expr2)) {
    355351            PabloAST * const expr1a = and1->getExpr1();
     
    361357            if (equals(expr1a, expr2a)) {
    362358                return createAnd(expr1a, createOr(expr1b, expr2b), prefix);
    363             }
    364             else if (equals(expr1b, expr2b)) {
     359            } else if (equals(expr1b, expr2b)) {
    365360                return createAnd(expr1b, createOr(expr1a, expr2a), prefix);
    366             }
    367             else if (equals(expr1a, expr2b)) {
     361            } else if (equals(expr1a, expr2b)) {
    368362                return createAnd(expr1a, createOr(expr1b, expr2a), prefix);
    369             }
    370             else if (equals(expr1b, expr2a)) {
     363            } else if (equals(expr1b, expr2a)) {
    371364                return createAnd(expr1b, createOr(expr1a, expr2b), prefix);
    372365            }
     
    388381PabloAST * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2) {
    389382    assert (expr1 && expr2);
     383    if (expr1 == expr2) {
     384        return PabloBlock::createZeroes();
     385    }
    390386    if (isa<Ones>(expr1)) {
    391387        return createNot(expr2);
    392     }
    393     else if (isa<Zeroes>(expr1)){
     388    } else if (isa<Zeroes>(expr1)){
    394389        return expr2;
    395     }
    396     else if (isa<Ones>(expr2)) {
     390    } else if (isa<Ones>(expr2)) {
    397391        return createNot(expr1);
    398     }
    399     else if (isa<Zeroes>(expr2)){
     392    } else if (isa<Zeroes>(expr2)){
    400393        return expr1;
    401     }
    402     else if (Not * not1 = dyn_cast<Not>(expr1)) {
     394    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    403395        if (Not * not2 = dyn_cast<Not>(expr2)) {
    404396            return createXor(not1->getExpr(), not2->getExpr());
     
    413405PabloAST * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
    414406    assert (expr1 && expr2);
     407    if (expr1 == expr2) {
     408        return PabloBlock::createZeroes();
     409    }
    415410    if (isa<Ones>(expr1)) {
    416411        return createNot(expr2, prefix);
    417     }
    418     else if (isa<Zeroes>(expr1)){
     412    } else if (isa<Zeroes>(expr1)){
    419413        return expr2;
    420     }
    421     else if (isa<Ones>(expr2)) {
     414    } else if (isa<Ones>(expr2)) {
    422415        return createNot(expr1, prefix);
    423     }
    424     else if (isa<Zeroes>(expr2)){
     416    } else if (isa<Zeroes>(expr2)){
    425417        return expr1;
    426     }
    427     else if (Not * not1 = dyn_cast<Not>(expr1)) {
     418    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
    428419        if (Not * not2 = dyn_cast<Not>(expr2)) {
    429420            return createXor(not1->getExpr(), not2->getExpr(), prefix);
     
    442433    if (isa<Ones>(condition)) {
    443434        return trueExpr;
    444     }
    445     else if (isa<Zeroes>(condition)){
     435    } else if (isa<Zeroes>(condition)){
    446436        return falseExpr;
    447     }
    448     else if (isa<Ones>(trueExpr)) {
     437    } else if (isa<Ones>(trueExpr)) {
    449438        return createOr(condition, falseExpr);
    450     }
    451     else if (isa<Zeroes>(trueExpr)){
     439    } else if (isa<Zeroes>(trueExpr)){
    452440        return createAnd(createNot(condition), falseExpr);
    453     }
    454     else if (isa<Ones>(falseExpr)) {
     441    } else if (isa<Ones>(falseExpr)) {
    455442        return createOr(createNot(condition), trueExpr);
    456     }
    457     else if (isa<Zeroes>(falseExpr)){
     443    } else if (isa<Zeroes>(falseExpr)){
    458444        return createAnd(condition, trueExpr);
    459     }
    460     else if (equals(trueExpr, falseExpr)) {
     445    } else if (equals(trueExpr, falseExpr)) {
    461446        return trueExpr;
    462     }
    463     else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getExpr(), falseExpr)) {
     447    } else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getExpr(), falseExpr)) {
    464448        return createXor(condition, falseExpr);
    465     }
    466     else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getExpr())){
     449    } else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getExpr())){
    467450        return createXor(condition, falseExpr);
    468451    }
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4788 r4797  
    7070
    7171    static inline Zeroes * createZeroes() {
    72         return mZeroes;
     72        return &mZeroes;
    7373    }
    7474
    7575    static inline Ones * createOnes() {
    76         return mOnes;
     76        return &mOnes;
    7777    }
    7878
     
    225225
    226226private:       
    227     static Zeroes * const                               mZeroes;
    228     static Ones * const                                 mOnes;
     227    static Zeroes                                       mZeroes;
     228    static Ones                                         mOnes;
    229229    SymbolGenerator &                                   mSymbolGenerator;
    230230    PabloBlock *                                        mParent;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.cpp

    r4788 r4797  
    2525using Vertex = Graph::vertex_descriptor;
    2626using VertexData = BooleanReassociationPass::VertexData;
    27 using VertexQueue = circular_buffer<Vertex>;
    2827using Map = BooleanReassociationPass::Map;
    2928using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Vertex>;
     
    4544}
    4645
    47 inline bool has_edge(const Vertex u, const Vertex v, const Graph & G) {
    48     return edge(u, v, G).second == true;
    49 }
    50 
    51 inline bool no_edge(const Vertex u, const Vertex v, const Graph & G) {
    52     return edge(u, v, G).second == false;
    53 }
     46#ifndef NDEBUG
     47static bool no_path(const Vertex u, const Vertex v, const Graph & G) {
     48    if (u == v) return false;
     49    flat_set<Vertex> V;
     50    std::queue<Vertex> Q;
     51    Q.push(u);
     52    for (;;) {
     53        Vertex w = Q.front();
     54        if (w == v) {
     55            return false;
     56        }
     57        Q.pop();
     58        for (auto e : make_iterator_range(out_edges(w, G))) {
     59            Vertex x = target(e, G);
     60            if (V.count(x)) continue;
     61            Q.push(x);
     62            V.insert(x);
     63        }
     64        if (Q.empty()) {
     65            break;
     66        }
     67    }
     68    return true;
     69}
     70#endif
    5471
    5572inline void add_edge(PabloAST * expr, const Vertex u, const Vertex v, Graph & G) {
    56     assert (u != v);
    57     assert (no_edge(v, u, G));
     73    assert (no_path(v, u, G));
    5874    // Make sure each edge is unique
    5975    for (auto e : make_iterator_range(out_edges(u, G))) {
     
    111127}
    112128
    113 inline bool isNegated(const VertexData & data) {
    114     return getType(data) == TypeId::Not && (getValue(data) != nullptr);
     129inline bool isConstant(const VertexData & data) {
     130    switch (getType(data)) {
     131        case TypeId::Zeroes:
     132        case TypeId::Ones:
     133            return true;
     134        default: return false;
     135    }
    115136}
    116137
     
    147168
    148169/** ------------------------------------------------------------------------------------------------------------- *
    149  * @brief intersection_count
    150  ** ------------------------------------------------------------------------------------------------------------- */
    151 template <class Type>
    152 inline unsigned intersection_count(const Type & A, const Type & B) {
    153     auto first1 = A.begin(), last1 = A.end();
    154     auto first2 = B.begin(), last2 = B.end();
    155     unsigned count = 0;
    156     while (first1 != last1 && first2 != last2) {
    157         if (*first1 < *first2) {
    158             ++first1;
    159         } else if (*first2 < *first1) {
    160             ++first2;
    161         } else {
    162             ++count;
    163         }
    164     }
    165     return count;
    166 }
    167 
    168 
    169 /** ------------------------------------------------------------------------------------------------------------- *
    170170 * @brief optimize
    171171 ** ------------------------------------------------------------------------------------------------------------- */
     
    173173    BooleanReassociationPass brp;
    174174    brp.resolveScopes(function);
    175     brp.processScopes(function);
     175    brp.processScopes(function);   
     176    #ifndef NDEBUG
     177    Simplifier::deadCodeElimination(function.getEntryBlock());
     178    PabloVerifier::verify(function, "post-reassociation");
     179    #endif
    176180    Simplifier::optimize(function);
    177181    return true;
     
    232236    M.insert(std::make_pair(value, u));
    233237    return u;
    234 }
    235 
    236 /** ------------------------------------------------------------------------------------------------------------- *
    237  * @brief printGraph
    238  ** ------------------------------------------------------------------------------------------------------------- */
    239 static void printGraph(const PabloBlock & block, const Graph & G, const std::string name) {
    240     raw_os_ostream out(std::cerr);
    241 
    242     std::vector<unsigned> c(num_vertices(G));
    243     strong_components(G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
    244 
    245     out << "digraph " << name << " {\n";
    246     for (auto u : make_iterator_range(vertices(G))) {
    247         if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    248             continue;
    249         }
    250         out << "v" << u << " [label=\"" << u << ": ";
    251         PabloAST * expr;
    252         TypeId typeId;
    253         std::tie(typeId, expr) = G[u];
    254         bool temporary = false;
    255         bool error = false;
    256         if (expr == nullptr) {
    257             temporary = true;
    258             switch (typeId) {
    259                 case TypeId::And:
    260                     out << "And";
    261                     break;
    262                 case TypeId::Or:
    263                     out << "Or";
    264                     break;
    265                 case TypeId::Xor:
    266                     out << "Xor";
    267                     break;
    268                 default:
    269                     out << "???";
    270                     error = true;
    271                     break;
    272             }
    273         } else if (isMutable(G[u], block)) {
    274             if (LLVM_UNLIKELY(isa<If>(expr))) {
    275                 out << "If ";
    276                 PabloPrinter::print(cast<If>(expr)->getOperand(0), out);
    277                 out << ":";
    278             } else if (LLVM_UNLIKELY(isa<While>(expr))) {
    279                 out << "While ";
    280                 PabloPrinter::print(cast<While>(expr)->getOperand(0), out);
    281                 out << ":";
    282             } else {
    283                 PabloPrinter::print(cast<Statement>(expr), "", out);
    284             }
    285         } else {
    286             PabloPrinter::print(expr, out);
    287         }
    288         out << "\"";
    289         if (!isMutable(G[u], block)) {
    290             out << " style=dashed";
    291         }
    292         if (error) {
    293             out << " color=red";
    294         } else if (temporary) {
    295             out << " color=blue";
    296         }
    297         out << "];\n";
    298     }
    299     for (auto e : make_iterator_range(edges(G))) {
    300         const auto s = source(e, G);
    301         const auto t = target(e, G);
    302         out << "v" << s << " -> v" << t;
    303         bool cyclic = (c[s] == c[t]);
    304         if (G[e] || cyclic) {
    305             out << " [";
    306              if (G[e]) {
    307                 out << "label=\"";
    308                 PabloPrinter::print(G[e], out);
    309                 out << "\" ";
    310              }
    311              if (cyclic) {
    312                 out << "color=red ";
    313              }
    314              out << "]";
    315         }
    316         out << ";\n";
    317     }
    318 
    319     if (num_vertices(G) > 0) {
    320 
    321         out << "{ rank=same;";
    322         for (auto u : make_iterator_range(vertices(G))) {
    323             if (in_degree(u, G) == 0 && out_degree(u, G) != 0) {
    324                 out << " v" << u;
    325             }
    326         }
    327         out << "}\n";
    328 
    329         out << "{ rank=same;";
    330         for (auto u : make_iterator_range(vertices(G))) {
    331             if (out_degree(u, G) == 0 && in_degree(u, G) != 0) {
    332                 out << " v" << u;
    333             }
    334         }
    335         out << "}\n";
    336 
    337     }
    338 
    339     out << "}\n\n";
    340     out.flush();
    341238}
    342239
     
    386283inline void BooleanReassociationPass::processScope(PabloFunction &, PabloBlock & block) {
    387284    Graph G;
    388     summarizeAST(block, G);
    389     redistributeAST(block, G);
     285    Map M;
     286    summarizeAST(block, G, M);
     287    redistributeAST(block, G, M);
    390288    rewriteAST(block, G);
    391289}
     
    395293 ** ------------------------------------------------------------------------------------------------------------- */
    396294void BooleanReassociationPass::rewriteAST(PabloBlock & block, Graph & G) {
    397 
    398 //    // Clear out the current AST
    399 //    std::vector<Statement *> currentAST;
    400 //    for (Statement * stmt = block.front(); stmt; stmt = stmt->removeFromParent()) {
    401 //        currentAST.push_back(stmt);
    402 //    }
    403295    // Rewrite the AST in accordance to G
    404296    circular_buffer<Vertex> Q(num_vertices(G));
     
    408300    unsigned statementCount = 0;
    409301    WrittenAt writtenAt;
     302    writtenAt.emplace(PabloBlock::createZeroes(), 0);
     303    writtenAt.emplace(PabloBlock::createOnes(), 0);
    410304    while (!Q.empty()) {
    411305        const Vertex u = Q.back();
    412306        Q.pop_back();
    413         // Supress any isolated vertices; the AST must be a single connected component.
     307        // Supress any isolated vertices
    414308        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
    415309            continue;
     
    449343        writtenAt.emplace(expr, statementIndex);
    450344    }
    451 //    // Erase any AST node that weren't placed back into the AST
    452 //    for (Statement * stmt : currentAST) {
    453 //        if (stmt->getParent() == nullptr) {
    454 //            stmt->eraseFromParent(true);
    455 //        }
    456 //    }
    457345}
    458346
     
    463351 * are "flattened" (i.e., allowed to have any number of inputs.)
    464352 ** ------------------------------------------------------------------------------------------------------------- */
    465 void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G) const {
    466     Map M;
     353void BooleanReassociationPass::summarizeAST(PabloBlock & block, Graph & G, Map & M) const {
    467354    // Compute the base def-use graph ...
    468355    for (Statement * stmt : block) {
     
    506393    }
    507394    std::vector<Vertex> mapping(num_vertices(G));
    508     summarizeGraph(block, G, mapping);
     395    summarizeGraph(block, G, mapping, M);
    509396}
    510397
     
    512399 * @brief resolveUsages
    513400 ** ------------------------------------------------------------------------------------------------------------- */
    514 void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis) const {
     401void BooleanReassociationPass::resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, const Statement * const ignoreIfThis) const {
    515402    for (PabloAST * user : expr->users()) {
    516403        assert (user);
     
    550437 * @brief summarizeGraph
    551438 ** ------------------------------------------------------------------------------------------------------------- */
    552 inline void BooleanReassociationPass::summarizeGraph(const PabloBlock &, Graph & G, std::vector<Vertex> & mapping) {
     439inline void BooleanReassociationPass::summarizeGraph(const PabloBlock &, Graph & G, std::vector<Vertex> & mapping, Map &) {
    553440    std::vector<Vertex> reverse_topological_ordering;
    554441    reverse_topological_ordering.reserve(num_vertices(G));
     
    556443    topological_sort(G, std::back_inserter(reverse_topological_ordering));
    557444    assert(mapping.size() >= num_vertices(G));
    558     for (const Vertex u : reverse_topological_ordering) {
    559         if (LLVM_LIKELY(out_degree(u, G) > 0)) {
     445    for (const Vertex u : reverse_topological_ordering) {       
     446        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     447            continue;
     448        } else if (LLVM_LIKELY(out_degree(u, G) > 0)) {
    560449            if (isAssociative(G[u])) {
    561450                if (LLVM_UNLIKELY(in_degree(u, G) == 1)) {
     
    572461                        }
    573462                    }
    574                     clear_vertex(u, G);
     463                    mapping[u] = v;
     464                    clear_vertex(u, G);                   
    575465                    getType(G[u]) = TypeId::Var;
    576                     mapping[u] = v;
     466                    getValue(G[u]) = nullptr;
    577467                    continue;
    578468                } else if (LLVM_UNLIKELY(out_degree(u, G) == 1)) {
     
    586476                            add_edge(G[ei], source(ej, G), v, G);
    587477                        }
     478                        mapping[u] = v;
    588479                        clear_vertex(u, G);
    589480                        getType(G[u]) = TypeId::Var;
    590                         mapping[u] = v;
     481                        getValue(G[u]) = nullptr;
     482                        continue;
    591483                    }
    592484                }
     
    595487            clear_in_edges(u, G);
    596488            getType(G[u]) = TypeId::Var;
     489            getValue(G[u]) = nullptr;
     490            continue;
    597491        }
    598492    }   
     
    792686void generateDistributionGraph(const Graph & G, DistributionGraph & H) {
    793687    DistributionMap M;
    794     for (const Vertex u : make_iterator_range(vertices(G))) {       
    795         if (isDistributive(G[u])) {
     688    for (const Vertex u : make_iterator_range(vertices(G))) {
     689        if (in_degree(u, G) == 0 && out_degree(u, G) == 0) {
     690            continue;
     691        } else if (isDistributive(G[u])) {
    796692            const TypeId outerTypeId = getType(G[u]);
    797693            const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
     
    855751 * Apply the distribution law to reduce computations whenever possible.
    856752 ** ------------------------------------------------------------------------------------------------------------- */
    857 void BooleanReassociationPass::redistributeAST(const PabloBlock & block, Graph & G) const {
     753void BooleanReassociationPass::redistributeAST(const PabloBlock & block, Graph & G, Map & M) const {
    858754
    859755    std::vector<Vertex> mapping(num_vertices(G) + 16);
     
    888784            const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or;
    889785
    890             // Update G to match the desired changes (TODO: modify this to reuse a discarded vertex instead)
    891             const Vertex x = add_vertex(std::make_pair(outerTypeId, nullptr), G);
    892             const Vertex y = add_vertex(std::make_pair(innerTypeId, nullptr), G);
     786            // Update G to match the desired change
     787            const Vertex x = addSummaryVertex(outerTypeId, G);
     788            const Vertex y = addSummaryVertex(innerTypeId, G);
    893789            mapping.resize(num_vertices(G));
    894790            mapping[x] = x;
     
    912808                add_edge(nullptr, u, y, G);
    913809            }
    914 
    915810            add_edge(nullptr, x, y, G);
    916811
     
    920815            }
    921816
    922             summarizeGraph(block, G, mapping);
    923         }
    924     }
     817            summarizeGraph(block, G, mapping, M);
     818        }
     819    }
     820}
     821
     822/** ------------------------------------------------------------------------------------------------------------- *
     823 * @brief addSummaryVertex
     824 ** ------------------------------------------------------------------------------------------------------------- */
     825inline Vertex BooleanReassociationPass::addSummaryVertex(const TypeId typeId, Graph & G) {
     826    return add_vertex(std::make_pair(typeId, nullptr), G);
    925827}
    926828
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/booleanreassociationpass.h

    r4775 r4797  
    2626    void processScopes(PabloFunction & function, PabloBlock & block);
    2727    void processScope(PabloFunction &, PabloBlock & block);
    28     void summarizeAST(PabloBlock & block, Graph & G) const;
    29     static void summarizeGraph(const PabloBlock & block, Graph & G, std::vector<Vertex> & mapping);
    30     void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, Statement * ignoreIfThis = nullptr) const;
    31     void redistributeAST(const PabloBlock & block, Graph & G) const;
     28    void summarizeAST(PabloBlock & block, Graph & G, Map & M) const;
     29    static void findAndPropogateAnyConstants(const Vertex u, Graph & G, Map & M);
     30    static void summarizeGraph(const PabloBlock & block, Graph & G, std::vector<Vertex> & mapping, Map &M);
     31    void resolveUsages(const Vertex u, PabloAST * expr, PabloBlock & block, Graph & G, Map & M, const Statement * const ignoreIfThis = nullptr) const;
     32    void redistributeAST(const PabloBlock & block, Graph & G, Map & M) const;
    3233    void rewriteAST(PabloBlock & block, Graph & G);
    3334    static PabloAST * createTree(PabloBlock & block, const Vertex u, Graph & G, const WrittenAt & writtenAt);
    3435    static Vertex getSummaryVertex(PabloAST * expr, Graph & G, Map & M, const PabloBlock & block);
     36    static Vertex addSummaryVertex(const PabloAST::ClassTypeId typeId, Graph & G);
    3537private:
    3638    ScopeMap mResolvedScopes;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4788 r4797  
    107107bool AutoMultiplexing::optimize(PabloFunction & function) {
    108108
    109     // std::random_device rd;
     109//    std::random_device rd;
     110//    const auto seed = rd();
    110111    const auto seed = 83234827342;
    111112    RNG rng(seed);
     
    158159        RECORD_TIMESTAMP(end_select_independent_sets);
    159160        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
     161
     162        #ifndef NDEBUG
     163        PabloVerifier::verify(function, "post-multiplexing");
     164        #endif
    160165
    161166        Simplifier::optimize(function);
     
    842847
    843848        for (auto i = m; i != n; ++i) {
    844             graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
    845849            // For each member of a "set vertex" ...
    846850            for (auto e : make_iterator_range(out_edges(i, mMultiplexSetGraph))) {
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_bddminimization.cpp

    r4788 r4797  
    1111#include <boost/circular_buffer.hpp>
    1212#include <pablo/optimizers/pablo_simplifier.hpp>
    13 #include <boost/container/flat_set.hpp>
    14 #include <boost/container/flat_map.hpp>
    15 #include <boost/graph/adjacency_list.hpp>
    16 #include <boost/graph/topological_sort.hpp>
     13#include <pablo/analysis/pabloverifier.hpp>
    1714
    1815using namespace llvm;
     
    2825    am.initialize(function);
    2926    am.eliminateLogicallyEquivalentStatements(function);
    30 
    3127    am.shutdown();
     28    #ifndef NDEBUG
     29    PabloVerifier::verify(function, "post-bdd-minimization");
     30    #endif
    3231    return Simplifier::optimize(function);
    3332}
     
    6261                    ++variableCount;
    6362                    break;
    64                 case TypeId::Next:
    65                     if (escapes(stmt)) {
    66                         ++variableCount;
    67                     }
    68                 default:
    69                     break;
     63                default: break;
    7064            }
    7165            stmt = stmt->getNextNode();
     
    114108        if (LLVM_UNLIKELY(isa<If>(stmt))) {
    115109            eliminateLogicallyEquivalentStatements(cast<If>(stmt)->getBody(), map);
    116             for (Assign * def : cast<const If>(stmt)->getDefined()) {
    117                 // Any defined variable that wasn't used outside of the If scope would have
    118                 // been demoted by the Simplifier pass.
    119                 map.insert(mCharacterizationMap[def], def);
    120             }
    121110        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    122111            eliminateLogicallyEquivalentStatements(cast<While>(stmt)->getBody(), map);
    123112            for (Next * var : cast<const While>(stmt)->getVariants()) {
    124                 if (escapes(var)) {
    125                     map.insert(NewVar(var), var);
    126                 } else { // we don't need to retain the BDD for this variant
     113                if (!escapes(var)) {
    127114                    Cudd_RecursiveDeref(mManager, mCharacterizationMap[var]);
    128115                    mCharacterizationMap.erase(var);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_codesinking.cpp

    r4657 r4797  
    11#include "pablo_codesinking.hpp"
    22#include <pablo/function.h>
     3#include <pablo/analysis/pabloverifier.hpp>
    34
    45namespace pablo {
     
    89    CodeSinking lcf;
    910    lcf.sink(function.getEntryBlock());
     11    #ifndef NDEBUG
     12    PabloVerifier::verify(*function, "post-sinking");
     13    #endif
    1014    return true;
    1115}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4788 r4797  
    44#include <pablo/function.h>
    55#include <pablo/printer_pablos.h>
     6#include <pablo/analysis/pabloverifier.hpp>
    67#include <unordered_map>
    78#include <iostream>
     
    1213    eliminateRedundantCode(function.getEntryBlock());
    1314    deadCodeElimination(function.getEntryBlock());
    14     eliminateRedundantComplexStatements(function.getEntryBlock());
     15    // eliminateRedundantComplexStatements(function.getEntryBlock());
     16    #ifndef NDEBUG
     17    PabloVerifier::verify(function, "post-simplification");
     18    #endif
    1519    return true;
    1620}
     
    2731    return false;
    2832}
    29 
    30 #ifndef NDEBUG
    31 static bool verifyStatementIsInSameBlock(const Statement * const stmt, const PabloBlock & block) {
    32     Statement * curr = block.front();
    33     while (curr) {
    34         if (curr == stmt) {
    35             return true;
    36         }
    37         curr = curr->getNextNode();
    38     }
    39     return false;
    40 }
    41 #endif
    4233
    4334inline bool Simplifier::isSuperfluous(const Assign * const assign) {
     
    6758inline bool demoteDefinedVar(const If * ifNode, const Assign * def) {
    6859    // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
    69     if (!escapes(def) || (ifNode->getCondition() == def->getExpression())) {
     60    if (!escapes(def)) {
    7061        return true;
    7162    }
     
    7465        return true;
    7566    }
    76     // Finally, if the assignment is a constant Zero or One, it's already known.
     67    // Finally, if the assignment is a constant, it's already known.
    7768    if (isa<Zeroes>(def->getExpression()) || isa<Ones>(def->getExpression()))  {
    7869        return true;
     
    8374void Simplifier::eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor) {
    8475    ExpressionTable encountered(predecessor);
    85 
    8676    Statement * stmt = block.front();
    87 
    8877    while (stmt) {
    89 
    90         assert (stmt);
    91         assert (verifyStatementIsInSameBlock(stmt, block));
    92 
    9378        if (Assign * assign = dyn_cast<Assign>(stmt)) {
    9479            // If we have an Assign whose users do not contain an If or Next node, we can replace its users with
     
    10287                continue;
    10388            }
    104         }
    105         else if (If * ifNode = dyn_cast<If>(stmt)) {
     89            // Force the uses of an local Assign to be the expression instead.
     90            for (PabloAST * use : assign->users()) {
     91                if (Statement * user = dyn_cast<Statement>(use)) {
     92                    if (LLVM_UNLIKELY(user->getParent() == &block)) {
     93                        user->replaceUsesOfWith(assign, assign->getExpression());
     94                    }
     95                }
     96            }
     97        } else if (If * ifNode = dyn_cast<If>(stmt)) {
    10698            // Check to see if the Cond is Zero and delete the loop.
    10799            if (LLVM_UNLIKELY(isa<Zeroes>(ifNode->getCondition()))) {
     
    151143                }
    152144            }
    153         }
    154         else if (isa<While>(stmt)) {
     145        } else if (isa<While>(stmt)) {
    155146            eliminateRedundantCode(cast<While>(stmt)->getBody(), &encountered);
    156         }       
    157         else if (stmt->getNumUses() == 0) {
    158             // If this statement has no users, we can discard it. If a future "identical" statement occurs that does
    159             // have users, we can use that statement instead.
    160             stmt = stmt->eraseFromParent();
    161             continue;
    162         }
    163         else if (canTriviallyFold(stmt)) { // non-Assign node
    164 
     147        } else if (canTriviallyFold(stmt)) { // non-Assign node
    165148            // Do a trivial folding test to see if we're using all 0s or 1s as an operand.
    166149            PabloAST * expr = nullptr;
     
    202185            }
    203186            stmt = stmt->replaceWith(expr);
    204             // the next statement could be an Assign; just restart the loop.
     187            block.setInsertPoint(block.back());
    205188            continue;
    206         }
    207         else {
     189        } else {
    208190            // When we're creating the Pablo program, it's possible to have multiple instances of an "identical"
    209191            // statement. By recording which statements have already been seen, we can detect the redundant statements
     
    211193            // and erase this statement from the AST
    212194            const auto f = encountered.findOrAdd(stmt);
    213             if (!std::get<1>(f)) {
    214                 stmt = stmt->replaceWith(std::get<0>(f), true, true);
     195            if (f.second == false) {
     196                stmt = stmt->replaceWith(f.first, true, true);
    215197                continue;
    216198            }
    217199        }
    218         assert (stmt);
    219200        stmt = stmt->getNextNode();
    220201    }
    221     block.setInsertPoint(block.back());
    222202}
    223203
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4788 r4797  
    2929bool equals(const PabloAST * expr1, const PabloAST * expr2) {
    3030    assert (expr1 && expr2);
    31     if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
     31    if (expr1 == expr2) {
     32        return true;
     33    } else if (expr1->getClassTypeId() == expr2->getClassTypeId()) {
    3234        if ((isa<Zeroes>(expr1)) || (isa<Ones>(expr1))) {
    3335            return true;
    34         }
    35         else if (const Var * var1 = dyn_cast<const Var>(expr1)) {
     36        } else if (const Var * var1 = dyn_cast<const Var>(expr1)) {
    3637            if (const Var * var2 = cast<const Var>(expr2)) {
    3738                return (var1->getName() == var2->getName());
    3839            }
    39         }
    40         else if (const Not* not1 = dyn_cast<const Not>(expr1)) {
     40        } else if (const Not* not1 = dyn_cast<const Not>(expr1)) {
    4141            if (const Not* not2 = cast<const Not>(expr2)) {
    4242                return equals(not1->getExpr(), not2->getExpr());
    4343            }
    44         }
    45         else if (const And* and1 = dyn_cast<const And>(expr1)) {
     44        } else if (const And* and1 = dyn_cast<const And>(expr1)) {
    4645            if (const And* and2 = cast<const And>(expr2)) {
    4746                if (equals(and1->getExpr1(), and2->getExpr1())) {
    4847                    return equals(and1->getExpr2(), and2->getExpr2());
    49                 }
    50                 else if (equals(and1->getExpr1(), and2->getExpr2())) {
     48                } else if (equals(and1->getExpr1(), and2->getExpr2())) {
    5149                    return equals(and1->getExpr2(), and2->getExpr1());
    5250                }
    5351            }
    54         }
    55         else if (const Or * or1 = dyn_cast<const Or>(expr1)) {
     52        } else if (const Or * or1 = dyn_cast<const Or>(expr1)) {
    5653            if (const Or* or2 = cast<const Or>(expr2)) {
    5754                if (equals(or1->getExpr1(), or2->getExpr1())) {
    5855                    return equals(or1->getExpr2(), or2->getExpr2());
    59                 }
    60                 else if (equals(or1->getExpr1(), or2->getExpr2())) {
     56                } else if (equals(or1->getExpr1(), or2->getExpr2())) {
    6157                    return equals(or1->getExpr2(), or2->getExpr1());
    6258                }
    6359            }
    64         }
    65         else if (const Xor * xor1 = dyn_cast<const Xor>(expr1)) {
     60        } else if (const Xor * xor1 = dyn_cast<const Xor>(expr1)) {
    6661            if (const Xor * xor2 = cast<const Xor>(expr2)) {
    6762                if (equals(xor1->getExpr1(), xor2->getExpr1())) {
    6863                    return equals(xor1->getExpr2(), xor2->getExpr2());
    69                 }
    70                 else if (equals(xor1->getExpr1(), xor2->getExpr2())) {
     64                } else if (equals(xor1->getExpr1(), xor2->getExpr2())) {
    7165                    return equals(xor1->getExpr2(), xor2->getExpr1());
    7266                }
    7367            }
    74         }
    75         else if (const Sel* sel1 = dyn_cast<const Sel>(expr1)) {
    76             if (const Sel* sel2 = cast<const Sel>(expr2)) {
    77                 if (equals(sel1->getCondition(), sel2->getCondition())) {
    78                     if (equals(sel1->getTrueExpr(), sel2->getTrueExpr())) {
    79                         return equals(sel1->getFalseExpr(), sel2->getFalseExpr());
    80                     }
    81                 }
    82             }
     68        } else if (isa<Integer>(expr1) || isa<String>(expr1) || isa<Call>(expr1)) {
     69            // If these weren't equivalent by address they won't be equivalent by their operands.
     70            return false;
     71        } else { // Non-reassociatable functions (i.e., Sel, Advance, ScanThru, MatchStar)
     72            const Statement * stmt1 = cast<Statement>(expr1);
     73            const Statement * stmt2 = cast<Statement>(expr2);
     74            assert (stmt1->getNumOperands() == stmt2->getNumOperands());
     75            for (unsigned i = 0; i != stmt1->getNumOperands(); ++i) {
     76                if (!equals(stmt1->getOperand(i), stmt2->getOperand(i))) {
     77                    return false;
     78                }
     79            }
     80            return true;
    8381        }
    8482    }
  • icGREP/icgrep-devel/icgrep/pablo/pe_and.h

    r4650 r4797  
    3333    : Statement(ClassTypeId::And, {expr1, expr2}, name)
    3434    {
    35 
     35        assert (getNumOperands() == 2);
    3636    }
    3737};
  • icGREP/icgrep-devel/icgrep/pablo/pe_or.h

    r4650 r4797  
    3333    : Statement(ClassTypeId::Or, {expr1, expr2}, name)
    3434    {
    35 
     35        assert (getNumOperands() == 2);
    3636    }
    3737};
  • icGREP/icgrep-devel/icgrep/pablo/pe_xor.h

    r4650 r4797  
    3434    : Statement(ClassTypeId::Xor, {expr1, expr2}, name)
    3535    {
    36 
     36        assert (getNumOperands() == 2);
    3737    }
    3838};
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.cpp

    r4776 r4797  
    7272    }
    7373    else if (const Next * next = dyn_cast<const Next>(stmt)) {       
    74         strm << next->getName() << "' = ";
     74        strm << "Next(" << next->getName() << ") = ";
    7575        print(next->getExpr(), strm);
    7676    }
     
    183183    }
    184184    else {
    185         strm << indent << "**UNKNOWN Pablo Statement type **" << "\n";
     185        strm << "???";
    186186    }
    187187}
     
    195195        strm << "1";
    196196    } else if (const Var * var = dyn_cast<const Var>(expr)) {
     197        assert (var->getName());
    197198        strm  << var->getName();
    198199    } else if (const Next * next = dyn_cast<const Next>(expr)) {
     200        assert (next->getName());
    199201        strm << "Next(" << next->getName() << ")";
    200202    } else if (const If * ifstmt = dyn_cast<If>(expr)) {
     
    207209        assert (stmt->getName());
    208210        strm << stmt->getName();
     211    } else if (isa<Integer>(expr)) {
     212        strm << cast<Integer>(expr)->value();
    209213    } else {
    210214        strm << "???";
  • icGREP/icgrep-devel/icgrep/re/re_cc.cpp

    r4621 r4797  
    3232    if ((type == ByteClass) && (max_codepoint() >= 0x80)) {
    3333        name << "BC";
    34     }
    35     else {
     34    } else {
    3635        name << "CC";
    3736    }
     
    5554            mSparseCharSet.emplace(i, lo, hi);
    5655            return;
    57         }
    58         else if (lo > hi_codepoint(i) + 1) {
     56        } else if (lo > hi_codepoint(i) + 1) {
    5957            ++i;
    60         }
    61         else {
     58        } else {
    6259            // ranges overlap; expand the range to include the overlapp
    6360            lo_codepoint(i) = std::min(lo_codepoint(i), lo);
  • icGREP/icgrep-devel/icgrep/re/re_parser.cpp

    r4796 r4797  
    3535    RE_Parser parser(regular_expression);
    3636    parser.fModeFlagSet = initialFlags;
    37     parser.fNested = false;
    3837    RE * re = parser.parse_RE();
    3938    if (re == nullptr) {
     
    4746    , _end(regular_expression.end())
    4847    , fModeFlagSet(0)
    49     , fNested(false)
    5048    {
    5149       
     
    8078RE * RE_Parser::parse_RE() {
    8179    RE * r = parse_alt();
     80    if (_cursor != _end) {
     81        throw ParseFailure("Unrecognized junk remaining at end of regexp");
     82    }
    8283    return r;
    8384}
     
    129130            case '*': case '+': case '?': case '{':
    130131                throw NothingToRepeat();
    131             case ']':
     132            case ']': case '}':
    132133                if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
    133134                    return build_CC(parse_utf8_codepoint());
    134135                }
    135                 else throw ParseFailure("Use  \\] for literal ].");
    136             case '}':
    137                 if (fNested) {
    138                     return nullptr;  //  a recursive invocation for a regexp in \N{...}
    139                 }
    140                 else if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
    141                     return build_CC(parse_utf8_codepoint());
    142                 }
    143                 else throw ParseFailure("Use \\} for literal }.");
     136                else throw ParseFailure("Use  \\] or \\} for literal ] or }.");
    144137            case '[':
    145138                _cursor++;
     
    366359#define bit40(x) (1ULL << ((x) - 0x40))
    367360const uint64_t setEscapeCharacters = bit40('b') | bit40('p') | bit40('d') | bit40('w') | bit40('s') |
    368                                      bit40('B') | bit40('P') | bit40('D') | bit40('W') | bit40('S') | bit40('N');
     361                                     bit40('B') | bit40('P') | bit40('D') | bit40('W') | bit40('S');
    369362
    370363inline bool isSetEscapeChar(char c) {
     
    418411            ++_cursor;
    419412            return complemented ? makeComplement(s) : s;
    420         case 'N':
    421             ++_cursor;
    422             if (_cursor == _end || *_cursor != '{') throw ParseFailure("Malformed \\N expression");
    423             ++_cursor;
    424             s = parseNamePatternExpression();
    425             if (_cursor == _end || *_cursor != '}') throw ParseFailure("Malformed \\N expression");
    426             ++_cursor;
    427             return s;
    428413        default:
    429414            throw ParseFailure("Internal error");
     
    537522    return property;
    538523}
    539 
    540 CC * RE_Parser::parseNamePatternExpression(){
    541    
    542     re::ModeFlagSet outerFlags = fModeFlagSet;
    543     fModeFlagSet = 1;
    544    
    545     bool outerNested = fNested;
    546     fNested = true;
    547    
    548     RE * nameRE = parse_RE();
    549    
    550     // Reset outer parsing state.
    551     fModeFlagSet = outerFlags;
    552     fNested = outerNested;
    553 
    554    
    555     // Embed the nameRE in ";.*$nameRE" to skip the codepoint field of Uname.txt
    556     RE * embedded = makeSeq({re::makeCC(0x3B), re::makeRep(re::makeAny(), 0, Rep::UNBOUNDED_REP), nameRE});
    557    
    558    
    559     throw ParseFailure("\\N{...} character name expression recognized but not yet supported.");
    560 
    561    
    562 }
    563 
    564524
    565525CharsetOperatorKind RE_Parser::getCharsetOperator() {
     
    868828            ++_cursor;
    869829            return parse_hex_codepoint(8,8);  // ICU compatibility
     830        case 'N':
     831            ++_cursor;
     832            throw ParseFailure("\\N{...} character name syntax not yet supported.");
     833
    870834        default:
    871835            // Escaped letters should be reserved for special functions.
  • icGREP/icgrep-devel/icgrep/re/re_parser.h

    r4796 r4797  
    7777
    7878    Name * parsePropertyExpression();
    79    
    80     CC * parseNamePatternExpression();
    81    
     79       
    8280    RE * makeComplement(RE * s);
    8381    RE * makeWordBoundary();
     
    119117    const cursor_t              _end;
    120118    ModeFlagSet                 fModeFlagSet;
    121     bool                        fNested;
    122119    NameMap                     mNameMap;
    123120};
Note: See TracChangeset for help on using the changeset viewer.