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

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

Location:
icGREP/icgrep-devel/icgrep
Files:
2 added
8 edited

Legend:

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

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

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

    r4627 r4629  
    104104
    105105        inline quad_iterator_return_t dereference() const {
    106             return std::make_pair(run(), quad());
     106            return std::make_pair(std::make_pair(type(), length()), quad());
    107107        }
    108108
     
    111111        }
    112112
    113         inline run_t run() const {
    114             return std::make_pair(std::get<0>(*mRunIterator), std::get<1>(*mRunIterator) - mOffset);
     113        inline run_type_t type() const {
     114            return std::get<0>(*mRunIterator);
     115        }
     116
     117        inline length_t length() const {
     118            return std::get<1>(*mRunIterator) - mOffset;
    115119        }
    116120
     
    138142
    139143    bool contains(const codepoint_t codepoint) const;
     144
     145    bool intersects(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) const;
    140146
    141147    void dump(llvm::raw_ostream & out) const;
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4626 r4629  
    6161                                      cl::cat(cPabloOptimizationsOptions));
    6262#ifdef ENABLE_MULTIPLEXING
    63 static cl::opt<bool> PabloMutualExclusionPass("csme", cl::init(true),
    64                                       cl::desc("Multiplex Advances whose inputs are mutual exclusive and replace any contradictory stream with Zero."),
     63static cl::opt<bool> PabloMutualExclusionPass("disable-multiplexing", cl::init(true),
     64                                      cl::desc("Disable combining Advances whose inputs are mutual exclusive."),
    6565                                      cl::cat(cPabloOptimizationsOptions));
    6666#endif
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r4618 r4629  
    325325UCD/PropertyObjects.cpp
    326326../QA/unit-tests/unicode_set_tests.hpp
     327pablo/optimizers/pablo_bddminimization.h
     328pablo/optimizers/pablo_bddminimization.cpp
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4612 r4629  
    117117    LOG("Characterize:            " << (end_characterize - start_characterize));
    118118
    119     RECORD_TIMESTAMP(start_minimization);
    120     am.minimize(entry);
    121     RECORD_TIMESTAMP(end_minimization);
    122     LOG("Minimize:                " << (end_minimization - start_minimization));
    123 
    124119    RECORD_TIMESTAMP(start_shutdown);
    125120    am.shutdown();
     
    314309            continue;
    315310        }
    316         mCharacterizationMap[stmt] = characterize(stmt, true);
     311        mCharacterizationMap[stmt] = characterize(stmt);
    317312    }
    318313}
     
    321316 * @brief characterize
    322317 ** ------------------------------------------------------------------------------------------------------------- */
    323 DdNode * AutoMultiplexing::characterize(Statement * const stmt, const bool throwUncharacterizedOperandError) {
     318inline DdNode * AutoMultiplexing::characterize(Statement * const stmt) {
    324319
    325320    DdNode * bdd = nullptr;
     
    333328        auto f = mCharacterizationMap.find(op);
    334329        if (LLVM_UNLIKELY(f == mCharacterizationMap.end())) {
    335             if (throwUncharacterizedOperandError) {
    336                 std::string tmp;
    337                 llvm::raw_string_ostream msg(tmp);
    338                 msg << "Uncharacterized operand " << std::to_string(i);
    339                 PabloPrinter::print(stmt, " of ", msg);
    340                 throw std::runtime_error(msg.str());
    341             }
    342             return nullptr;
     330            std::string tmp;
     331            llvm::raw_string_ostream msg(tmp);
     332            msg << "Uncharacterized operand " << std::to_string(i);
     333            PabloPrinter::print(stmt, " of ", msg);
     334            throw std::runtime_error(msg.str());
    343335        }
    344336        input[i] = f->second;
     
    377369    }
    378370
    379     if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
    380         Cudd_RecursiveDeref(mManager, bdd);
    381         bdd = Zero();
    382     }
    383 
    384371    return bdd;
    385 
    386372}
    387373
     
    490476
    491477/** ------------------------------------------------------------------------------------------------------------- *
    492  * @brief reevaluate
    493  ** ------------------------------------------------------------------------------------------------------------- */
    494 void AutoMultiplexing::reevaluate(Next * next, DdNode * value) {
    495 
    496     Assign * const initial = cast<Assign>(next->getOperand(0));
    497 
    498     if (LLVM_UNLIKELY(mCharacterizationMap[initial] == value)) {
    499         return;
    500     }
    501     mCharacterizationMap[initial] = value;
    502 
    503 
    504     std::queue<PabloAST *> Q;
    505     flat_set<PabloBlock *> within_scope;
    506 
    507     for (PabloBlock * block = next->getParent(); ;) {
    508         within_scope.insert(block);
    509         for (PabloAST * user : block->users()) {
    510             if (within_scope.insert(cast<PabloBlock>(user)).second) {
    511                 Q.push(user);
    512             }
    513         }
    514         if (Q.empty()) {
    515             break;
    516         }
    517         block = cast<PabloBlock>(Q.front());
    518         Q.pop();
    519     }
    520 
    521     std::unordered_set<PabloAST *> visited;
    522 
    523     for (Statement * current = initial; ; ) {
    524         for (PabloAST * user : current->users()) {
    525             if (Statement * stmt = dyn_cast<Statement>(user)) {
    526                 if (visited.insert(user).second && within_scope.count(stmt->getParent())) {
    527                     DdNode * bdd = characterize(stmt, false);
    528                     if (bdd && mCharacterizationMap[user] != bdd) {
    529                         mCharacterizationMap[user] = bdd;
    530                         Q.push(stmt);
    531                     }
    532                 }
    533             }
    534         }
    535         if (Q.empty()) {
    536             break;
    537         }
    538         current = cast<Statement>(Q.front());
    539         Q.pop();
    540     }
    541 
    542 }
    543 
    544 /** ------------------------------------------------------------------------------------------------------------- *
    545  * @brief minimize
    546  * @param entry the entry block of the program
    547  *
    548  * Scan through the program using the precomputed BDDs and replace any statements with equivalent BDDs with the
    549  * earlier one (assuming its in scope) and replace any contradictions with Zero.
    550  ** ------------------------------------------------------------------------------------------------------------- */
    551 inline void AutoMultiplexing::minimize(PabloBlock & entry) {
    552     SubsitutionMap baseMap;
    553     baseMap.insert(Zero(), entry.createZeroes());
    554     baseMap.insert(One(), entry.createOnes());
    555     minimize(entry, baseMap);
    556 }
    557 
    558 /** ------------------------------------------------------------------------------------------------------------- *
    559  * @brief prohibited
    560  *
    561  * If this statement is an Assign or Next node or any of its operands is a non-superfluous Assign or Next node,
    562  * then we're prohibited from minimizing this statement.
    563  ** ------------------------------------------------------------------------------------------------------------- */
    564 inline bool prohibited(const Statement * const stmt) {
    565     if (isa<Assign>(stmt) || isa<Next>(stmt)) {
    566         return true;
    567     }
    568     for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    569         const PabloAST * const  op = stmt->getOperand(i);
    570         const Assign * const assign = dyn_cast<Assign>(op);
    571         if (LLVM_UNLIKELY((assign && !assign->superfluous()) || isa<Next>(op))) {
    572             return true;
    573         }
    574     }
    575     return false;
    576 }
    577 
    578 /** ------------------------------------------------------------------------------------------------------------- *
    579  * @brief minimize
    580  ** ------------------------------------------------------------------------------------------------------------- */
    581 void AutoMultiplexing::minimize(PabloBlock & block, SubsitutionMap & parent) {
    582     SubsitutionMap subsitutionMap(&parent);
    583     for (Statement * stmt : block) {
    584         if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    585             // Set the next statement to be the first statement of the inner scope and push the
    586             // next statement of the current statement into the scope stack.
    587             minimize(isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(), subsitutionMap);
    588             continue;
    589         }
    590 
    591         if (LLVM_UNLIKELY(prohibited(stmt))) {
    592             continue;
    593         }
    594 
    595         DdNode * bdd = mCharacterizationMap[stmt];
    596         PabloAST * replacement = subsitutionMap.test(bdd, stmt);
    597         if (LLVM_UNLIKELY(replacement != nullptr)) {
    598             if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
    599                 assert (mAdvanceMap.count(stmt));
    600                 const auto k = mAdvanceMap[stmt];
    601                 const auto m = num_vertices(mConstraintGraph);
    602                 for (unsigned i = 0; i != m; ++i) {
    603                     add_edge(k, m, mConstraintGraph);
    604                 }
    605             }
    606             Cudd_RecursiveDeref(mManager, bdd);
    607             stmt->replaceWith(replacement);
    608         }
    609     }
    610 }
    611 
    612 /** ------------------------------------------------------------------------------------------------------------- *
    613478 * @brief notTransitivelyDependant
    614479 ** ------------------------------------------------------------------------------------------------------------- */
     
    1094959
    1095960                std::ostringstream prefix;
    1096                 prefix << "mux" << n << "to" << m;
     961                prefix << "mux" << n << "to" << m << '_';
    1097962                for (size_t i = 1; i <= n; ++i) {
    1098963                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
    1099964                        assert (!Q.full());
    1100965                        PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
    1101                         prefix << '_' << V[i - 1]->getName()->to_string();
     966                        // prefix << '_' << V[i - 1]->getName()->to_string();
    1102967                        Q.push_back(tmp);
    1103968                    }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4611 r4629  
    3535    using IndependentSet = std::vector<ConstraintVertex>;
    3636
    37     struct SubsitutionMap {
    38         SubsitutionMap(SubsitutionMap * parent = nullptr) : mParent(parent) {}
    39         PabloAST * test(const DdNode * node, PabloAST * stmt) {
    40             PabloAST * replacement = find(node);
    41             if (LLVM_LIKELY(replacement == nullptr)) {
    42                 mMap.insert(std::make_pair(node, stmt));
    43             }
    44             return replacement;
    45         }
    46         PabloAST * find(const DdNode * node) const {
    47             auto f = mMap.find(node);
    48             if (LLVM_LIKELY(f == mMap.end())) {
    49                 PabloAST * replacement = nullptr;
    50                 if (mParent == nullptr) {
    51                     replacement = mParent->find(node);
    52                 }
    53                 return replacement;
    54             }
    55             return f->second;
    56         }
    57         void insert(const DdNode * node, PabloAST * stmt) {
    58             mMap.insert(std::make_pair(node, stmt));
    59         }
    60     private:
    61         const SubsitutionMap * const mParent;
    62         llvm::DenseMap<const DdNode *, PabloAST *> mMap;
    63     };
    64 
    6537public:
    6638    static bool optimize(const std::vector<Var *> & input, PabloBlock & entry);
     
    6840    void initialize(const std::vector<Var *> & vars, PabloBlock & entry);
    6941    void characterize(PabloBlock & block);
    70     DdNode * characterize(Statement * const stmt, const bool throwUncharacterizedOperandError);
     42    DdNode * characterize(Statement * const stmt);
    7143    DdNode * characterize(Advance * adv, DdNode * input);
    72     void reevaluate(Next * next, DdNode * value);
    73     void minimize(PabloBlock & entry);
    74     void minimize(PabloBlock & block, SubsitutionMap & parent);
    75 
    7644    bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
    7745    bool generateMultiplexSets(RNG & rng, unsigned k = 1);
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r4626 r4629  
    3838static cl::opt<bool> DisableUnicodeLineBreak("disable-unicode-linebreak", cl::init(false),
    3939                     cl::desc("disable Unicode line breaks - use LF only"), cl::cat(fREcompilationOptions));
    40 static cl::opt<bool> DisablePregeneratedUnicode("disable-pregenerated-unicode", cl::init(false),
     40static cl::opt<bool> DisablePregeneratedUnicode("disable-pregenerated-unicode", cl::init(true),
    4141                     cl::desc("disable use of pregenerated Unicode character class sets"), cl::cat(fREcompilationOptions));
    4242
Note: See TracChangeset for help on using the changeset viewer.