Changeset 4442


Ignore:
Timestamp:
Jan 25, 2015, 1:42:55 PM (4 years ago)
Author:
cameron
Message:

Simple if-insertion strategy at starDepth 0

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

Legend:

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

    r4415 r4442  
    1111#include "re_intersect.h"
    1212#include "re_assertion.h"
     13#include <limits.h>
    1314
    1415namespace re {
     
    8081    return false; // otherwise
    8182}
    82    
     83   
     84int minMatchLength(RE * re) {
     85    if (Alt * alt = dyn_cast<Alt>(re)) {
     86        int minAltLength = INT_MAX;
     87        for (RE * re : *alt) {
     88            minAltLength = std::min(minAltLength, minMatchLength(re));
     89        }
     90        return minAltLength;
     91    }
     92    else if (Seq * seq = dyn_cast<Seq>(re)) {
     93        int minSeqLength = 0;
     94        for (RE * re : *seq) {
     95            minSeqLength += minMatchLength(re);
     96        }
     97        return minSeqLength;
     98    }
     99    else if (Rep * rep = dyn_cast<Rep>(re)) {
     100        if (rep->getLB() == 0) return 0;
     101        else return (rep->getLB()) * minMatchLength(rep->getRE());
     102    }
     103    else if (isa<Assertion>(re)) {
     104        return 0;
     105    }
     106    else if (Diff * diff = dyn_cast<Diff>(re)) {
     107        return minMatchLength(diff->getLH());
     108    }
     109    else if (Intersect * e = dyn_cast<Intersect>(re)) {
     110        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
     111    }
     112    else if (isa<Any>(re)) {
     113        return 1;
     114    }
     115    else if (isa<Name>(re)) {
     116        return 1;
     117    }
     118    return 0; // otherwise
    83119}
     120
     121
     122}
  • icGREP/icgrep-devel/icgrep/re/re_analysis.h

    r4393 r4442  
    1212bool isUnicodeUnitLength(RE * re);
    1313
     14int minMatchLength(RE * re);
     15
    1416}
    1517
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r4441 r4442  
    3535, mInitial(nullptr)
    3636, mNonFinal(nullptr)
     37, mStarDepth(0)
    3738{
    3839
     
    243244
    244245MarkerType RE_Compiler::process(Seq * seq, MarkerType marker, PabloBlock & pb) {
    245     for (RE * re : *seq) {
    246         marker = process(re, marker, pb);
    247     }
    248     return marker;
     246    // if-hierarchies are not inserted within unbounded repetitions
     247    if (mStarDepth > 0) {
     248        for (RE * re : *seq) {
     249            marker = process(re, marker, pb);
     250        }
     251        return marker;
     252    }
     253    else {
     254        return processSeqTail(seq->begin(), seq->end(), 0, marker, pb);
     255    }
     256}
     257
     258#define matchLengthBetweenIfs 2
     259   
     260MarkerType RE_Compiler::processSeqTail(Seq::iterator current, Seq::iterator end, int matchLenSoFar, MarkerType marker, PabloBlock & pb) {
     261    if (current == end) return marker;
     262    if (matchLenSoFar < matchLengthBetweenIfs) {
     263        RE * r = *current;
     264        marker = process(r, marker, pb);
     265        current++;
     266        return processSeqTail(current, end, matchLenSoFar + minMatchLength(r), marker, pb);
     267    }
     268    else {
     269        PabloBlock & nested = PabloBlock::Create(pb);
     270        MarkerType m1 = processSeqTail(current, end, 0, marker, nested);
     271        Assign * m1a = nested.createAssign("m", markerVar(m1));
     272        pb.createIf(markerVar(marker), std::move(std::vector<Assign *>{m1a}), nested);
     273        return makeMarker(m1.pos, m1a);
     274    }
    249275}
    250276
     
    390416    }
    391417    // Fall through to general case.
     418    mStarDepth++;
    392419    while (lb-- != 0) {
    393420        marker = process(repeated, marker, pb);
    394421    }
     422    mStarDepth--;
    395423    return marker;
    396424}
     
    408436    }
    409437    // Fall through to general case.
     438    mStarDepth++;
    410439    while (ub-- != 0) {
    411440        MarkerType a = process(repeated, marker, pb);
     
    414443        marker = makeMarker(markerPos(a), pb.createOr(markerVar(a), markerVar(m), "m"));
    415444    }
     445    mStarDepth--;
    416446    return marker;
    417447}
     
    434464
    435465        PabloBlock & wb = PabloBlock::Create(pb);
     466        mStarDepth++;
    436467
    437468        PabloAST * loopComputation = markerVar(AdvanceMarker(process(repeated, makeMarker(InitialPostPositionByte, whileTest), wb), InitialPostPositionByte, wb));
     
    440471
    441472        pb.createWhile(nextWhileTest, wb);
     473        mStarDepth--;
    442474
    443475        return makeMarker(InitialPostPositionByte, pb.createAssign("unbounded", nextWhileAccum));
  • icGREP/icgrep-devel/icgrep/re/re_compiler.h

    r4439 r4442  
    99
    1010#include <re/re_re.h>
     11#include <re/re_seq.h>
    1112#include <cc/cc_compiler.h>
    1213
     
    7677    MarkerType process(Name * name, MarkerType marker, pablo::PabloBlock & pb);
    7778    MarkerType process(Seq * seq, MarkerType marker, pablo::PabloBlock & pb);
     79    MarkerType processSeqTail(Seq::iterator current, Seq::iterator end, int matchLenSoFar, MarkerType marker, pablo::PabloBlock & pb);
    7880    MarkerType process(Alt * alt, MarkerType marker, pablo::PabloBlock & pb);
    7981    MarkerType process(Assertion * a, MarkerType marker, pablo::PabloBlock & pb);
     
    9496    pablo::PabloAST *                               mInitial;
    9597    pablo::Assign *                                 mNonFinal;
     98    int                                             mStarDepth;
    9699};
    97100
Note: See TracChangeset for help on using the changeset viewer.