Ignore:
Timestamp:
Jan 15, 2018, 4:48:02 PM (15 months ago)
Author:
nmedfort
Message:

Revised RE_Minimizer to use alphabets + minor optimizations to RE functions

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/re/re_alt.h

    r5811 r5835  
    5252}
    5353   
    54 inline void add_CC(std::vector<CC *> & CCs_found, CC * cc) {
    55     for (unsigned j = 0; j < CCs_found.size(); j++) {
    56         if (CCs_found[j]->getAlphabet() == cc->getAlphabet()) {
    57             CCs_found[j] = makeCC(CCs_found[j], cc);
    58             return;
    59         }
    60     }
    61     CCs_found.push_back(cc);
    62 }
    63 
    6454template<typename iterator>
    6555RE * makeAlt(iterator begin, iterator end) {
    6656    Alt * newAlt = makeAlt();
    67     bool nullableAltFound = false;
    68     std::vector<CC *> CCs_found;  // CCs with possibly different alphabets
     57    if (LLVM_UNLIKELY(begin == end)) {
     58        return newAlt;
     59    }
     60
     61    llvm::SmallVector<CC *, 2> CCs(0); // CCs with possibly different alphabets
     62    auto combineCC = [&CCs] (CC * cc) {
     63        for (CC *& existing : CCs) {
     64            if (LLVM_LIKELY(existing->getAlphabet() == cc->getAlphabet())) {
     65                existing = makeCC(existing, cc);
     66                return;
     67            }
     68        }
     69        CCs.push_back(cc);
     70    };
     71
     72    bool nullable = false;
     73    RE * emptySeq = nullptr;
    6974    for (auto i = begin; i != end; ++i) {
    7075        if (CC * cc = llvm::dyn_cast<CC>(*i)) {
    71             add_CC(CCs_found, cc);
     76            combineCC(cc);
    7277        } else if (const Alt * alt = llvm::dyn_cast<Alt>(*i)) {
    7378            // We have an Alt to embed within the alt.  We extract the individual
     
    7681            for (RE * a : *alt) {
    7782                if (CC * cc = llvm::dyn_cast<CC>(a)) {
    78                     add_CC(CCs_found, cc);
     83                    combineCC(cc);
    7984                } else if (isEmptySeq(a)) {
    80                     nullableAltFound = true;
     85                    nullable = true;
     86                    emptySeq = a;
    8187                } else {
    8288                    newAlt->push_back(a);
     
    8591        } else if (const Rep * rep = llvm::dyn_cast<Rep>(*i)) {
    8692            if (rep->getLB() == 0) {
    87                 nullableAltFound = true;
     93                nullable = true;
    8894                newAlt->push_back(makeRep(rep->getRE(), 1, rep->getUB()));
    8995            } else {
     
    9197            }
    9298        } else if (isEmptySeq(*i)) {
    93             nullableAltFound = true;
     99            nullable = true;
     100            emptySeq = *i;
    94101        } else {
    95102            newAlt->push_back(*i);
    96103        }
    97104    }
    98     for (CC * cc : CCs_found) {
    99         newAlt->push_back(cc);
     105    newAlt->insert(newAlt->end(), CCs.begin(), CCs.end());
     106    if (nullable) {
     107        if (emptySeq == nullptr) {
     108            emptySeq = makeSeq();
     109        }
     110        newAlt->push_back(emptySeq);
    100111    }
    101     if (nullableAltFound) newAlt->push_back(makeSeq());
    102     if (newAlt->size() == 1) return newAlt->front();
    103     return newAlt;
     112    return newAlt->size() == 1 ? newAlt->front() : newAlt;
    104113}
    105114
Note: See TracChangeset for help on using the changeset viewer.