Ignore:
Timestamp:
Jan 15, 2018, 4:48:02 PM (18 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_star_normal.cpp

    r5646 r5835  
    1212#include <re/re_assertion.h>
    1313#include <re/re_analysis.h>
     14#include <re/re_nullable.h>
    1415
    1516using namespace llvm;
     
    1718namespace re {
    1819
     20RE * RE_Star_Normal::optimize(RE * re) {
     21    if (Alt * alt = dyn_cast<Alt>(re)) {
     22        std::vector<RE *> list;
     23        list.reserve(alt->size());
     24        for (RE * re : *alt) {
     25            list.push_back(optimize(re));
     26        }
     27        re = makeAlt(list.begin(), list.end());
     28    } else if (Seq * seq = dyn_cast<Seq>(re)) {
     29        RE * head = *(seq->begin());
     30        RE * tail = makeSeq(seq->begin() + 1, seq->end());
     31        const auto headNullable = RE_Nullable::isNullable(head);
     32        head = headNullable ? optimize(head) : star_normal(head);
     33        const auto tailNullable = RE_Nullable::isNullable(tail);
     34        tail = tailNullable ? optimize(tail) : star_normal(tail);
     35        if (LLVM_UNLIKELY(headNullable && tailNullable)) {
     36            re = makeAlt({head, tail});
     37        } else {
     38            re = makeSeq({head, tail});
     39        }
     40    } else if (Assertion * a = dyn_cast<Assertion>(re)) {
     41        re = makeAssertion(optimize(a->getAsserted()), a->getKind(), a->getSense());
     42    } else if (Rep * rep = dyn_cast<Rep>(re)) {
     43        RE * const expr = optimize(rep->getRE());
     44        if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
     45            re = expr;
     46        } else {
     47            re = makeRep(expr, rep->getLB(), rep->getUB());
     48        }
     49    } else if (Diff * diff = dyn_cast<Diff>(re)) {
     50        re = makeDiff(optimize(diff->getLH()), optimize(diff->getRH()));
     51    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
     52        re = makeIntersect(optimize(e->getLH()), optimize(e->getRH()));
     53    } else if (Name * name = dyn_cast<Name>(re)) {
     54        if (name->getDefinition()) {
     55            name->setDefinition(optimize(name->getDefinition()));
     56        }
     57    }
     58    return re;
     59}
     60
    1961RE * RE_Star_Normal::star_normal(RE * re) {
    20 
    2162    if (Alt * alt = dyn_cast<Alt>(re)) {
    2263        std::vector<RE *> list;
     
    3778    } else if (Rep * rep = dyn_cast<Rep>(re)) {
    3879         if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
    39             RE * expr = helper(rep->getRE());
     80            RE * expr = optimize(rep->getRE());
    4081            re = makeRep(expr, 0, rep->getUB());
    4182        } else {
     
    5596}
    5697
    57 RE * RE_Star_Normal::helper(RE * re) {
    58     if (Alt * alt = dyn_cast<Alt>(re)) {
    59         std::vector<RE *> list;
    60         list.reserve(alt->size());
    61         for (RE * re : *alt) {
    62             list.push_back(helper(re));
    63         }
    64         re = makeAlt(list.begin(), list.end());
    65     } else if (Seq * seq = dyn_cast<Seq>(re)) {
    66         RE * const re_first = *(seq->begin());
    67         RE * const re_follow = makeSeq(seq->begin() + 1, seq->end());
    68         const auto isFirstNullable = isNullable(re_first);
    69         const auto isFollowNullable = isNullable(re_follow);
    70         if (LLVM_LIKELY(!isFirstNullable && !isFollowNullable)) {
    71             re = makeSeq({star_normal(re_first), star_normal(re_follow)});
    72         } else if (!isFirstNullable && isFollowNullable) {
    73             re = makeSeq({helper(re_first), star_normal(re_follow)});
    74         } else if (isFirstNullable && !isFollowNullable) {
    75             re = makeSeq({star_normal(re_first), helper(re_follow)});
    76         } else {
    77             re = makeAlt({helper(re_first), helper(re_follow)});
    78         }
    79     } else if (Assertion * a = dyn_cast<Assertion>(re)) {
    80         re = makeAssertion(helper(a->getAsserted()), a->getKind(), a->getSense());
    81     } else if (Rep * rep = dyn_cast<Rep>(re)) {
    82         RE * const expr = helper(rep->getRE());
    83         if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
    84             re = expr;
    85         } else {
    86             re = makeRep(expr, rep->getLB(), rep->getUB());
    87         }
    88     } else if (Diff * diff = dyn_cast<Diff>(re)) {
    89         re = makeDiff(helper(diff->getLH()), helper(diff->getRH()));
    90     } else if (Intersect * e = dyn_cast<Intersect>(re)) {
    91         re = makeIntersect(helper(e->getLH()), helper(e->getRH()));
    92     } else if (Name * name = dyn_cast<Name>(re)) {
    93         if (name->getDefinition()) {
    94             name->setDefinition(helper(name->getDefinition()));
    95         }
    96     }
    97     return re;
    9898}
    99 
    100 bool RE_Star_Normal::isNullable(const RE * re) {
    101     if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
    102         for (const RE * re : *re_seq) {
    103             if (!isNullable(re)) {
    104                 return false;
    105             }
    106         }
    107         return true;
    108     } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
    109         for (const RE * re : *re_alt) {
    110             if (isNullable(re)) {
    111                 return true;
    112             }
    113         }
    114     } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
    115         return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
    116     } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
    117         return isNullable(diff->getLH()) && !isNullable(diff->getRH());
    118     } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
    119         return isNullable(e->getLH()) && isNullable(e->getRH());
    120     }
    121     return false;
    122 }
    123 
    124 
    125 }
Note: See TracChangeset for help on using the changeset viewer.