Changeset 5891 for icGREP


Ignore:
Timestamp:
Mar 7, 2018, 7:31:49 PM (11 months ago)
Author:
cameron
Message:

Byte test complexity analysis

Location:
icGREP/icgrep-devel/icgrep/re
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/re/re_analysis.cpp

    r5835 r5891  
    1919#include <limits.h>
    2020#include <llvm/Support/ErrorHandling.h>
     21#include <llvm/Support/raw_ostream.h>
    2122
    2223using namespace llvm;
     
    393394}
    394395
     396struct ByteTestComplexity {
     397   
     398    void gatherTests(RE * re);
     399   
     400    UCD::UnicodeSet equalityTests;
     401    UCD::UnicodeSet lessThanTests;
     402};
     403
     404void ByteTestComplexity::gatherTests(RE * re) {
     405    if (CC * cc = dyn_cast<CC>(re)) {
     406        if (cc->getAlphabet() != &cc::Byte) report_fatal_error("ByteTestComplexity: non Byte alphabet");
     407        for (const auto range : *cc) {
     408            const auto lo = re::lo_codepoint(range);
     409            const auto hi = re::hi_codepoint(range);
     410            if (lo == hi) {
     411                equalityTests.insert(lo);
     412            } else {
     413                if (lo > 0) lessThanTests.insert(lo);
     414                if (hi < 0xFF) lessThanTests.insert(hi+1);
     415            }
     416        }
     417    } else if (const Name * n = dyn_cast<Name>(re)) {
     418        gatherTests(n->getDefinition());
     419    } else if (Alt * alt = dyn_cast<Alt>(re)) {
     420        for (RE * item : *alt) {
     421            gatherTests(item);
     422        }
     423    } else if (Seq * seq = dyn_cast<Seq>(re)) {
     424        for (RE * item : *seq) {
     425            gatherTests(item);
     426        }
     427    } else if (Assertion * a = dyn_cast<Assertion>(re)) {
     428        gatherTests(a->getAsserted());
     429    } else if (Rep * rep = dyn_cast<Rep>(re)) {
     430        gatherTests(rep->getRE());
     431    } else if (Diff * diff = dyn_cast<Diff>(re)) {
     432        gatherTests(diff->getLH());
     433        gatherTests(diff->getRH());
     434    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
     435        gatherTests(e->getLH());
     436        gatherTests(e->getRH());
     437    } else if (Group * g = dyn_cast<Group>(re)) {
     438        gatherTests(g->getRE());
     439    }
     440}
     441
     442size_t byteTestComplexity(RE * re) {
     443    ByteTestComplexity btc_object;
     444    btc_object.gatherTests(re);
     445    return btc_object.equalityTests.count() + btc_object.lessThanTests.count();
     446}
     447
     448
    395449void UndefinedNameError(const Name * n) {
    396450    report_fatal_error("Error: Undefined name in regular expression: \"" + n->getName() + "\".");
  • icGREP/icgrep-devel/icgrep/re/re_analysis.h

    r5723 r5891  
    3030bool hasAssertion(const RE * re);
    3131   
     32size_t byteTestComplexity(RE * re);
     33   
    3234void UndefinedNameError (const Name * n);
    3335}
  • icGREP/icgrep-devel/icgrep/re/re_nullable.cpp

    r5880 r5891  
    165165    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
    166166        return (re_rep->getLB() == 0) || isNullable(re_rep->getRE());
    167     } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
     167    } else if (isa<Diff>(re)) {
    168168        // a Diff of Seq({}) and an Assertion represents a complemented assertion.
    169169        return false;
Note: See TracChangeset for help on using the changeset viewer.