Changeset 5811


Ignore:
Timestamp:
Dec 27, 2017, 6:01:51 PM (3 weeks ago)
Author:
cameron
Message:

RE optimizations

File:
1 edited

Legend:

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

    r5784 r5811  
    99
    1010#include "re_re.h"
    11 #include "re_cc.h"
     11#include <re/re_cc.h>
     12#include <re/re_seq.h>
     13#include <re/re_rep.h>
     14#include <re/printer_re.h>
    1215#include <llvm/Support/Casting.h>
    1316
     
    4851    return new Alt();
    4952}
     53   
     54inline 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}
    5063
    5164template<typename iterator>
    5265RE * makeAlt(iterator begin, iterator end) {
    5366    Alt * newAlt = makeAlt();
    54     CC * unionCC = nullptr;
     67    bool nullableAltFound = false;
     68    std::vector<CC *> CCs_found;  // CCs with possibly different alphabets
    5569    for (auto i = begin; i != end; ++i) {
    5670        if (CC * cc = llvm::dyn_cast<CC>(*i)) {
    57             unionCC = unionCC ? makeCC(unionCC, cc) : cc;
     71            add_CC(CCs_found, cc);
    5872        } else if (const Alt * alt = llvm::dyn_cast<Alt>(*i)) {
    5973            // We have an Alt to embed within the alt.  We extract the individual
     
    6276            for (RE * a : *alt) {
    6377                if (CC * cc = llvm::dyn_cast<CC>(a)) {
    64                     unionCC = unionCC ? makeCC(unionCC, cc) : cc;
     78                    add_CC(CCs_found, cc);
     79                } else if (isEmptySeq(a)) {
     80                    nullableAltFound = true;
    6581                } else {
    6682                    newAlt->push_back(a);
    6783                }
    6884            }
    69         }
    70         else {
     85        } else if (const Rep * rep = llvm::dyn_cast<Rep>(*i)) {
     86            if (rep->getLB() == 0) {
     87                nullableAltFound = true;
     88                newAlt->push_back(makeRep(rep->getRE(), 1, rep->getUB()));
     89            } else {
     90                newAlt->push_back(*i);
     91            }
     92        } else if (isEmptySeq(*i)) {
     93            nullableAltFound = true;
     94        } else {
    7195            newAlt->push_back(*i);
    7296        }
    7397    }
    74     if (unionCC) {
    75         newAlt->push_back(unionCC);
     98    for (CC * cc : CCs_found) {
     99        newAlt->push_back(cc);
    76100    }
     101    if (nullableAltFound) newAlt->push_back(makeSeq());
    77102    if (newAlt->size() == 1) return newAlt->front();
    78103    return newAlt;
     
    83108}
    84109
     110// An Alt with no members represent the empty set.
     111inline bool isEmptySet(RE * r) {
     112    return llvm::isa<Alt>(r) && llvm::cast<Alt>(r)->empty();
     113}
    85114}
    86115
Note: See TracChangeset for help on using the changeset viewer.