Changeset 4841

Timestamp:

Oct 17, 2015, 4:25:05 PM (2 years ago)

Author:

nmedfort

Message:

Update for grapheme cluster mode and boundaries.

Location:

icGREP/icgrep-devel/icgrep

Files:

• UCD/ucd_compiler.cpp (modified) (4 diffs)
• UCD/ucd_compiler.hpp (modified) (1 diff)
• pablo/optimizers/pablo_simplifier.cpp (modified) (10 diffs)
• pablo/pabloAST.h (modified) (2 diffs)
• pablo/ps_if.h (modified) (1 diff)
• re/printer_re.cpp (modified) (2 diffs)
• re/re_analysis.cpp (modified) (2 diffs)
• re/re_compiler.cpp (modified) (16 diffs)
• re/re_compiler.h (modified) (5 diffs)
• re/re_grapheme_boundary.hpp (modified) (1 diff)
• re/re_nullable.cpp (modified) (2 diffs)
• re/re_parser.cpp (modified) (18 diffs)
• re/re_simplifier.cpp (modified) (3 diffs)
• re/re_simplifier.h (modified) (1 diff)

icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.cpp

@@ -452 +452 @@
     addTargets(names);
     generateRange(defaultIfHierachy, entry);
-    updateNames(names);
+    updateNames(names, entry);
 }
 
@@ -471 +471 @@
     addTargets(names);
     generateRange(noIfHierachy, entry);
-    updateNames(names);
+    updateNames(names, entry);
 }
 
@@ -488 +488 @@
 inline void UCDCompiler::addTargets(const NameMap & names) {
     for (const auto t : names) {
-        if (isa<CC>(t.first->getDefinition())) {
+        if (LLVM_LIKELY(isa<CC>(t.first->getDefinition()))) {
             mTargetMap.emplace(cast<CC>(t.first->getDefinition()), t.second ? t.second : PabloBlock::createZeroes());
         } else {
@@ -500 +500 @@
  * @brief updateNames
  ** ------------------------------------------------------------------------------------------------------------- */
-inline void UCDCompiler::updateNames(NameMap & names) {
+inline void UCDCompiler::updateNames(NameMap & names, PabloBuilder & entry) {
     for (auto & t : names) {
         auto f = mTargetMap.find(cast<CC>(t.first->getDefinition()));
-        t.second = f->second;
+        if (f != mTargetMap.end()) {
+            std::string name = t.first->getName();
+            if (Statement * result = dyn_cast<Statement>(f->second)) {
+                result->setName(entry.getName(name, false));
+                t.second = result;
+            } else {
+                t.second = entry.createAssign(std::move(name), f->second);
+            }
+        }
     }
     mTargetMap.clear();

icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.hpp

@@ -94 +94 @@
     void addTargets(const NameMap & names);
 
-    void updateNames(NameMap & names);
+    void updateNames(NameMap & names, PabloBuilder & entry);
 
 private:

icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

@@ -22 +22 @@
 #endif
 
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief optimize
+ ** ------------------------------------------------------------------------------------------------------------- */
 bool Simplifier::optimize(PabloFunction & function) {
     eliminateRedundantCode(function.getEntryBlock());
@@ -32 +35 @@
 }
 
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief canTriviallyFold
+ ** ------------------------------------------------------------------------------------------------------------- */
 inline static PabloAST * canTriviallyFold(Statement * stmt, PabloBlock & block) {
     for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
@@ -81 +87 @@
 }
 
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief isSuperfluous
+ ** ------------------------------------------------------------------------------------------------------------- */
 inline bool Simplifier::isSuperfluous(const Assign * const assign) {
     for (const PabloAST * inst : assign->users()) {
@@ -105 +114 @@
 }
 
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief demoteDefinedVar
+ ** ------------------------------------------------------------------------------------------------------------- */
 inline bool demoteDefinedVar(const If * ifNode, const Assign * def) {
     // If this value isn't used outside of this scope then there is no reason to allow it to escape it.
@@ -121 +133 @@
 }
 
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief replaceReachableUsersOfWith
+ ** ------------------------------------------------------------------------------------------------------------- */
 inline void replaceReachableUsersOfWith(Statement * stmt, PabloAST * expr) {
     const PabloBlock * const root = stmt->getParent();
@@ -146 +161 @@
 }
 
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief discardNestedIfBlock
+ *
+ * If this inner block is composed of only Boolean logic and Assign statements and there are fewer than 3
+ * statements, just add the statements in the inner block to the current block.
+ ** ------------------------------------------------------------------------------------------------------------- */
+inline bool discardNestedIfBlock(const PabloBlock & pb) {
+    unsigned computations = 0;
+    for (const Statement * stmt : pb) {
+        switch (stmt->getClassTypeId()) {
+            case PabloAST::ClassTypeId::And:
+            case PabloAST::ClassTypeId::Or:
+            case PabloAST::ClassTypeId::Xor:
+                if (++computations > 3) {
+                    return false;
+                }
+            case PabloAST::ClassTypeId::Not:
+            case PabloAST::ClassTypeId::Assign:
+                break;
+            default:
+                return false;
+        }
+    }
+    return true;
+}
+
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief removeIdenticalEscapedValues
+ ** ------------------------------------------------------------------------------------------------------------- */
 template <class ValueList>
 inline void removeIdenticalEscapedValues(ValueList & list) {
@@ -161 +205 @@
 }
 
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief eliminateRedundantCode
+ ** ------------------------------------------------------------------------------------------------------------- */
 void Simplifier::eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor) {
     ExpressionTable encountered(predecessor);
@@ -211 +258 @@
                 continue;
             }
+
             // Otherwise check if we any Assign reports the same value as another. If so, replace all uses of the
             // second with the first. This will simplify future analysis.
             removeIdenticalEscapedValues(ifNode->getDefined());
+
+            // Finally after we've eliminated everything we can from the If body, check whether testing the If
+            // condition will meet or exceed the cost of executing the body.
+            if (LLVM_UNLIKELY(discardNestedIfBlock(ifNode->getBody()))) {
+                Statement * nested = ifNode->getBody().front();
+                while (nested) {
+                    Statement * next = nested->removeFromParent();
+                    nested->insertAfter(stmt);
+                    stmt = nested;
+                    nested = next;
+                }
+                ifNode->getDefined().clear();
+                stmt = ifNode->eraseFromParent(true);
+                continue;
+            }
 
         } else if (While * whileNode = dyn_cast<While>(stmt)) {
@@ -244 +307 @@
 }
 
-
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief deadCodeElimination
+ ** ------------------------------------------------------------------------------------------------------------- */
 void Simplifier::deadCodeElimination(PabloBlock & block) {
     Statement * stmt = block.front();
@@ -260 +325 @@
 }
 
+/** ------------------------------------------------------------------------------------------------------------- *
+ * @brief eliminateRedundantEquations
+ ** ------------------------------------------------------------------------------------------------------------- */
 void Simplifier::eliminateRedundantEquations(PabloBlock & block) {
     Statement * stmt = block.front();

icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

@@ -213 +213 @@
         return mName;
     }
+    inline void setName(const String * const name) {
+        mName = name;
+    }
     inline Statement * getNextNode() const {
         return mNext;
@@ -239 +242 @@
             }
         }
-    }
-    inline void setName(const String * const name) {
-        mName = name;
-    }    
+    }  
 #ifndef NDEBUG
     bool noRecursiveOperand(const PabloAST * const operand);

icGREP/icgrep-devel/icgrep/pablo/ps_if.h

@@ -44 +44 @@
         return mDefined;
     }
-    void addDefined(Assign * def);
-protected:
     inline DefinedVars & getDefined() {
         return mDefined;
     }
+    void addDefined(Assign * def);
+protected:
     If(PabloAST * expr, const std::initializer_list<Assign *> definedVars, PabloBlock & body);
-
     If(PabloAST * expr, const std::vector<Assign *> & definedVars, PabloBlock & body);
 private:

icGREP/icgrep-devel/icgrep/re/printer_re.cpp

@@ -86 +86 @@
         retVal += ") ";
     }
-    else if (const GraphemeBoundary * g = dyn_cast<GraphemeBoundary>(re))
-    {
+    else if (const GraphemeBoundary * g = dyn_cast<GraphemeBoundary>(re)) {
         retVal = "Grapheme";
         switch (g->getType()) {
@@ -100 +99 @@
         }
         retVal += "Boundary(";
-        retVal += PrintRE(g->getExpression());
-        retVal += ") ";
+        if (g->getExpression()) {
+            retVal += PrintRE(g->getExpression());
+        }
+        retVal += ")";
     }
     else if (isa<const End>(re))

icGREP/icgrep-devel/icgrep/re/re_analysis.cpp

@@ -63 +63 @@
         // Eventually names might be set up for not unit length items.
         return (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty || n->getType() == Name::Type::Byte);
-    } else if (const GraphemeBoundary * gb = dyn_cast<GraphemeBoundary>(re)) {
-        return isUnicodeUnitLength(gb->getExpression());
     }
     return false; // otherwise
@@ -127 +125 @@
                 return std::make_pair(0, std::numeric_limits<int>::max());
         }
-    } else if (const GraphemeBoundary * gb = dyn_cast<GraphemeBoundary>(re)) {
-        return std::make_pair(getUnicodeUnitLengthRange(gb->getExpression()).first, std::numeric_limits<int>::max());
+    } else if (const GraphemeBoundary * gp = dyn_cast<GraphemeBoundary>(re)) {
+        if (gp->getExpression()) {
+            return getUnicodeUnitLengthRange(gp->getExpression());
+        }
+        return std::make_pair(0, 0);
     }
     return std::make_pair(1, 1);

icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

@@ -174 +174 @@
                             const UCD::ExternalProperty & ep = UCD::resolveExternalProperty(functionName);
                             Call * call = mPB.createCall(Prototype::Create(functionName, std::get<1>(ep), std::get<2>(ep), std::get<0>(ep)), mCCCompiler.getBasisBits());
-                            name->setCompiled(mPB.createAnd(call, mAny));
+                            name->setCompiled(call);
                         } else {
                         #endif
@@ -241 +241 @@
             }
         } else if (GraphemeBoundary * gb = dyn_cast<GraphemeBoundary>(re)) {
-            if (LLVM_LIKELY(gb->getGraphemeExtenderRule() == nullptr)) {
+            if (LLVM_LIKELY(gb->getBoundaryRule() == nullptr)) {
                 switch (gb->getType()) {
                     case GraphemeBoundary::Type::ClusterBoundary:
                         if (graphemeClusterRule == nullptr) {
-                            graphemeClusterRule = cast<Name>(resolve(generateGraphemeClusterExtenderRule()));
+                            graphemeClusterRule = cast<Name>(resolve(generateGraphemeClusterBoundaryRule()));
                         }
                         gb->setBoundaryRule(graphemeClusterRule);
@@ -253 +253 @@
                 }
             }
-            gb->setExpression(resolve(gb->getExpression()));
+            if (gb->getExpression()) {
+                resolve(gb->getExpression());
+            }
         }
         return re;
@@ -261 +263 @@
     std::unordered_set<Name *> visited;
 
-    std::function<void(RE*)> gather = [&](RE * re) {
+    std::function<void(RE*)> gather = [&](RE * re) {        
         if (Name * name = dyn_cast<Name>(re)) {
             if (visited.insert(name).second) {
@@ -289 +291 @@
             gather(ix->getRH());
         } else if (GraphemeBoundary * gb = dyn_cast<GraphemeBoundary>(re)) {
-            gather(gb->getExpression());
-            gather(gb->getGraphemeExtenderRule());
+            if (gb->getExpression()) {
+                gather(gb->getExpression());
+            }
+            gather(gb->getBoundaryRule());
         }
     };
@@ -302 +306 @@
         for (auto t : nameMap) {
             if (t.second) {
-                mCompiledName.insert(std::make_pair(t.first, makeMarker(MarkerPosition::FinalMatchByte, mPB.createAnd(t.second, mAny))));
+                mCompiledName.insert(std::make_pair(t.first, makeMarker(MarkerPosition::FinalMatchByte, t.second)));
             }
         }
@@ -309 +313 @@
     // Now precompile any grapheme segmentation rules
     if (graphemeClusterRule) {
-        mCompiledName.insert(std::make_pair(graphemeClusterRule, compileName(graphemeClusterRule, mPB)));
+        auto gcb = compileName(graphemeClusterRule, mPB);
+        mCompiledName.insert(std::make_pair(graphemeClusterRule, gcb));
     }
     return re;
@@ -318 +323 @@
 }
 
-Name * RE_Compiler::generateGraphemeClusterExtenderRule() {
+Name * RE_Compiler::generateGraphemeClusterBoundaryRule() {
     // 3.1.1 Grapheme Cluster Boundary Rules
     #define Behind(x) makeLookBehindAssertion(x)
@@ -324 +329 @@
 
     RE * GCB_Control = makeName("gcb", "cn", Name::Type::UnicodeProperty);
-
+    RE * GCB_CR = makeName("gcb", "cr", Name::Type::UnicodeProperty);
+    RE * GCB_LF = makeName("gcb", "lf", Name::Type::UnicodeProperty);
+
+    // Break at the start and end of text.
     RE * GCB_1 = makeStart();
     RE * GCB_2 = makeEnd();
+    // Do not break between a CR and LF.
+    RE * GCB_3 = makeSeq({Behind(GCB_CR), Ahead(GCB_LF)});
+    // Otherwise, break before and after controls.
     RE * GCB_4 = Behind(GCB_Control);
     RE * GCB_5 = Ahead(GCB_Control);
-
-    RE * GCB_1_5 = makeAlt({GCB_1, GCB_2, makeSeq({GCB_4, GCB_5})});
+    RE * GCB_1_5 = makeAlt({GCB_1, GCB_2, makeDiff(makeSeq({GCB_4, GCB_5}), GCB_3)});
 
     RE * GCB_L = makeName("gcb", "l", Name::Type::UnicodeProperty);
@@ -338 +348 @@
     RE * GCB_T = makeName("gcb", "t", Name::Type::UnicodeProperty);
     RE * GCB_RI = makeName("gcb", "ri", Name::Type::UnicodeProperty);
-    // Legacy rules
+    // Do not break Hangul syllable sequences.
     RE * GCB_6 = makeSeq({Behind(GCB_L), Ahead(makeAlt({GCB_L, GCB_V, GCB_LV, GCB_LVT}))});
     RE * GCB_7 = makeSeq({Behind(makeAlt({GCB_LV, GCB_V})), Ahead(makeAlt({GCB_V, GCB_T}))});
     RE * GCB_8 = makeSeq({Behind(makeAlt({GCB_LVT, GCB_T})), Ahead(GCB_T)});
+    // Do not break between regional indicator symbols.
     RE * GCB_8a = makeSeq({Behind(GCB_RI), Ahead(GCB_RI)});
+    // Do not break before extending characters.
     RE * GCB_9 = Ahead(makeName("gcb", "ex", Name::Type::UnicodeProperty));
-    // Extended rules
+    // Do not break before SpacingMarks, or after Prepend characters.
     RE * GCB_9a = Ahead(makeName("gcb", "sm", Name::Type::UnicodeProperty));
     RE * GCB_9b = Behind(makeName("gcb", "pp", Name::Type::UnicodeProperty));
-
     RE * GCB_6_9b = makeAlt({GCB_6, GCB_7, GCB_8, GCB_8a, GCB_9, GCB_9a, GCB_9b});
+    // Otherwise, break everywhere.
+    RE * GCB_10 = makeSeq({Behind(makeAny()), Ahead(makeAny())});
+
     Name * gcb = makeName("gcb", Name::Type::UnicodeProperty);
-    gcb->setDefinition(makeDiff(GCB_6_9b,  GCB_1_5));
-
+    gcb->setDefinition(makeAlt({GCB_1_5, makeDiff(GCB_10, GCB_6_9b)}));
     return gcb;
 }
@@ -550 +563 @@
 
 inline PabloAST * RE_Compiler::consecutive_matches(PabloAST * repeated, int length, int repeat_count, PabloBuilder & pb) {
-        int i = length;
-        int total = repeat_count * length;
-        PabloAST * consecutive_i = repeated;
-        while (i * 2 < total) {
-            PabloAST * v = consecutive_i;
-            PabloAST * v2 =  pb.createAdvance(v, i);
-            i *= 2;
-            consecutive_i = pb.createAnd(v, v2, "at" + std::to_string(i) + "of" + std::to_string(total));
-        }        
-        if (i < total) {
-            PabloAST * v = consecutive_i;
-            consecutive_i = pb.createAnd(v, pb.createAdvance(v, total - i), "at" + std::to_string(total));
-        }
-        return consecutive_i;
-}
-
-inline PabloAST * RE_Compiler::reachable(PabloAST *repeated, int repeated_lgth, int repeat_count, PabloBuilder & pb) {
-        int i = repeated_lgth;
-        int total_lgth = repeat_count * repeated_lgth;
-        if (repeat_count == 0) {
-            return repeated;
-        }
-        PabloAST * reachable_i = pb.createOr(repeated, pb.createAdvance(repeated, 1), "within1");
-        while (i * 2 < total_lgth) {
-            PabloAST * v = reachable_i;
-            PabloAST * v2 =  pb.createAdvance(v, i);
-            i *= 2;
-            reachable_i = pb.createOr(v, v2, "within" + std::to_string(i));
-        }        
-        if (i < total_lgth) {
-            PabloAST * v = reachable_i;
-            reachable_i = pb.createOr(v, pb.createAdvance(v, total_lgth - i), "within" + std::to_string(total_lgth));
-        }
-        return reachable_i;
+    int i = length;
+    int total = repeat_count * length;
+    PabloAST * consecutive_i = repeated;
+    while (i * 2 < total) {
+        PabloAST * v = consecutive_i;
+        PabloAST * v2 =  pb.createAdvance(v, i);
+        i *= 2;
+        consecutive_i = pb.createAnd(v, v2, "at" + std::to_string(i) + "of" + std::to_string(total));
+    }
+    if (i < total) {
+        PabloAST * v = consecutive_i;
+        consecutive_i = pb.createAnd(v, pb.createAdvance(v, total - i), "at" + std::to_string(total));
+    }
+    return consecutive_i;
+}
+
+inline PabloAST * RE_Compiler::reachable(PabloAST * repeated, int length, int repeat_count, PabloBuilder & pb) {
+    int i = length;
+    int total_lgth = repeat_count * length;
+    if (repeat_count == 0) {
+        return repeated;
+    }
+    PabloAST * reachable_i = pb.createOr(repeated, pb.createAdvance(repeated, 1), "within1");
+    while (i * 2 < total_lgth) {
+        PabloAST * v = reachable_i;
+        PabloAST * v2 =  pb.createAdvance(v, i);
+        i *= 2;
+        reachable_i = pb.createOr(v, v2, "within" + std::to_string(i));
+    }
+    if (i < total_lgth) {
+        PabloAST * v = reachable_i;
+        reachable_i = pb.createOr(v, pb.createAdvance(v, total_lgth - i), "within" + std::to_string(total_lgth));
+    }
+    return reachable_i;
 }
 
@@ -633 +646 @@
         }
         return makeMarker(MarkerPosition::InitialPostPositionByte, mstar);
-    }
-    else if (isUnicodeUnitLength(repeated) && !DisableMatchStar && !DisableUnicodeMatchStar) {
+    } else if (isUnicodeUnitLength(repeated) && !DisableMatchStar && !DisableUnicodeMatchStar) {
         PabloAST * cc = markerVar(compile(repeated, pb));
         PabloAST * mstar = nullptr;
         PabloAST * nonFinal = mNonFinal;
-        if (mGraphemeExtenderRule) {
-            nonFinal = pb.createOr(nonFinal, mGraphemeExtenderRule);
+        if (mGraphemeBoundaryRule) {
+            nonFinal = pb.createOr(nonFinal, pb.createNot(mGraphemeBoundaryRule, "gext"));
         }
         cc = pb.createOr(cc, nonFinal);
@@ -648 +660 @@
         }
         PabloAST * final = mFinal;
-        if (mGraphemeExtenderRule) {
-            final = pb.createOr(final, pb.createNot(mGraphemeExtenderRule));
+        if (mGraphemeBoundaryRule) {
+            final = mGraphemeBoundaryRule;
         }
         return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(mstar, final, "unbounded"));
@@ -705 +717 @@
     if (UNICODE_LINE_BREAK) {
         PabloAST * nextPos = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionByte, pb));
-        return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(nextPos, mUnicodeLineBreak, "end"));
+        return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(nextPos, mUnicodeLineBreak, "eol"));
     } else {
         PabloAST * nextPos = markerVar(AdvanceMarker(marker, MarkerPosition::InitialPostPositionByte, pb));  // For LF match
@@ -712 +724 @@
 }
 
-inline MarkerType RE_Compiler::compileGraphemeBoundary(GraphemeBoundary * gb, const MarkerType marker, pablo::PabloBuilder & pb) {
-    const auto inGraphemeBoundaryRule = mGraphemeExtenderRule;
-    auto f = mCompiledName.find(gb->getGraphemeExtenderRule());
-    if (LLVM_UNLIKELY(f == mCompiledName.end())) {
-        throw std::runtime_error("Internal error: failed to locate grapheme boundary rule!");
-    }
-    mGraphemeExtenderRule = markerVar(f->second);
-    assert (mGraphemeExtenderRule);
-    MarkerType result = process(gb->getExpression(), marker, pb);
-    mGraphemeExtenderRule = inGraphemeBoundaryRule;
-    return result;
-}
-
-inline MarkerType RE_Compiler::AdvanceMarker(const MarkerType m, const MarkerPosition newpos, PabloBuilder & pb) {
-    if (m.pos == newpos) return m;
-    PabloAST * a = m.stream;
-    if (m.pos == MarkerPosition::FinalMatchByte) {
-        // Must advance the previous marker to the InitialPostPositionByte
-        a = pb.createAdvance(a, 1, "ipp");
-    }
-    // Now at InitialPostPositionByte; is a further advance needed?
-    if (newpos == MarkerPosition::FinalPostPositionByte) {
-        // Must advance through nonfinal bytes
-        PabloAST * nonFinal = mNonFinal;
-        if (mGraphemeExtenderRule) {
-            nonFinal = pb.createOr(nonFinal, mGraphemeExtenderRule, "gext");
-        }
-        a = pb.createScanThru(pb.createAnd(mInitial, a), nonFinal, "fpp");
-    }
-    return {newpos, a};
+inline MarkerType RE_Compiler::compileGraphemeBoundary(GraphemeBoundary * gb, MarkerType marker, pablo::PabloBuilder & pb) {
+    auto f = mCompiledName.find(gb->getBoundaryRule());
+    assert ("Internal error: failed to locate grapheme boundary rule!" && (f != mCompiledName.end()));
+    if (gb->getExpression()) {
+        const auto graphemeBoundaryRule = mGraphemeBoundaryRule;
+        mGraphemeBoundaryRule = markerVar(f->second);
+        marker = process(gb->getExpression(), marker, pb);
+        marker = AdvanceMarker(marker, MarkerPosition::FinalPostPositionByte, pb);
+        mGraphemeBoundaryRule = graphemeBoundaryRule;
+    } else {
+        marker = AdvanceMarker(marker, MarkerPosition::FinalPostPositionByte, pb);
+        PabloAST * rule = markerVar(f->second);
+        if (gb->getSense() == GraphemeBoundary::Sense::Negative) {
+            rule = pb.createNot(rule);
+        }
+        marker = makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(markerVar(marker), rule, "gb"));
+    }
+    return marker;
+}
+
+inline MarkerType RE_Compiler::AdvanceMarker(MarkerType marker, const MarkerPosition newpos, PabloBuilder & pb) {
+    if (marker.pos != newpos) {
+        if (marker.pos == MarkerPosition::FinalMatchByte) {
+            marker.stream = pb.createAdvance(marker.stream, 1, "ipp");
+            marker.pos = MarkerPosition::InitialPostPositionByte;
+        }
+        if (newpos == MarkerPosition::FinalPostPositionByte) {
+            PabloAST * nonFinal = mNonFinal;
+            if (mGraphemeBoundaryRule) {
+                nonFinal = pb.createOr(nonFinal, pb.createNot(mGraphemeBoundaryRule, "gext"));
+            }
+            marker.stream = pb.createScanThru(pb.createAnd(mInitial, marker.stream), nonFinal, "fpp");
+            marker.pos = MarkerPosition::FinalPostPositionByte;
+        }
+    }
+    return marker;
 }
 
@@ -758 +776 @@
 , mUnicodeLineBreak(nullptr)
 , mAny(nullptr)
-, mGraphemeExtenderRule(nullptr)
+, mGraphemeBoundaryRule(nullptr)
 , mInitial(nullptr)
 , mNonFinal(nullptr)

icGREP/icgrep-devel/icgrep/re/re_compiler.h

@@ -63 +63 @@
 
     MarkerType compile(RE * re, pablo::PabloBuilder & cg);
-    MarkerType AdvanceMarker(const MarkerType m, const MarkerPosition newpos, pablo::PabloBuilder & pb);
-    
-    void AlignMarkers(MarkerType & m1, MarkerType & m2, pablo::PabloBuilder & pb);
-    
+
     MarkerType process(RE * re, MarkerType marker, pablo::PabloBuilder & pb);
     MarkerType compileName(Name * name, MarkerType marker, pablo::PabloBuilder & pb);
@@ -77 +74 @@
     MarkerType compileIntersect(Intersect * x, MarkerType marker, pablo::PabloBuilder & cg);
     pablo::PabloAST * consecutive_matches(pablo::PabloAST * repeated,  int length, int repeat_count, pablo::PabloBuilder & pb);
-    pablo::PabloAST * reachable(pablo::PabloAST * repeated,  int repeated_lgth, int repeat_count, pablo::PabloBuilder & pb);
+    pablo::PabloAST * reachable(pablo::PabloAST * repeated,  int length, int repeat_count, pablo::PabloBuilder & pb);
     static bool isFixedLength(RE * regexp);
     MarkerType processLowerBound(RE * repeated,  int lb, MarkerType marker, pablo::PabloBuilder & pb);
@@ -84 +81 @@
     RE * resolveUnicodeProperties(RE * re);
 
-    Name * generateGraphemeClusterExtenderRule();
+    Name * generateGraphemeClusterBoundaryRule();
     MarkerType compileName(Name * name, pablo::PabloBuilder & pb);
     MarkerType compileAny(const MarkerType m, pablo::PabloBuilder & pb);
     MarkerType compileStart(const MarkerType marker, pablo::PabloBuilder & pb);
     MarkerType compileEnd(const MarkerType marker, pablo::PabloBuilder & pb);
-    MarkerType compileGraphemeBoundary(GraphemeBoundary *gb, const MarkerType marker, pablo::PabloBuilder & pb);
+    MarkerType compileGraphemeBoundary(GraphemeBoundary *gb, MarkerType marker, pablo::PabloBuilder & pb);
+
+    MarkerType AdvanceMarker(MarkerType marker, const MarkerPosition newpos, pablo::PabloBuilder & pb);
+    void AlignMarkers(MarkerType & m1, MarkerType & m2, pablo::PabloBuilder & pb);
 
 private:
@@ -98 +98 @@
     pablo::PabloAST *                               mUnicodeLineBreak;
     pablo::PabloAST *                               mAny;
-    pablo::PabloAST *                               mGraphemeExtenderRule;
+    pablo::PabloAST *                               mGraphemeBoundaryRule;
     pablo::PabloAST *                               mInitial;
     pablo::Assign *                                 mNonFinal;    
@@ -106 +106 @@
     std::vector<pablo::Next *>                      mLoopVariants; // <- rethink name
     pablo::PabloBuilder                             mPB;
-    std::unordered_map<Name *, MarkerType>          mCompiledName;    
+    std::unordered_map<Name *, MarkerType>          mCompiledName;
     pablo::PabloFunction &                          mFunction;
 };

icGREP/icgrep-devel/icgrep/re/re_grapheme_boundary.hpp

@@ -16 +16 @@
 
     enum class Type {
-        ClusterBoundary     // g
-        , WordBoundary      // w
-        , LineBreakBoundary // l
-        , SentenceBoundary  // s
+        ClusterBoundary = 0     // g
+        , WordBoundary = 1      // w
+        , LineBreakBoundary = 2 // l
+        , SentenceBoundary = 3  // s
     };
 
+    enum class Sense {Positive, Negative};
+
+    inline Type getType() const { return mType; }
+    GraphemeBoundary::Sense getSense() const {return mSense;}
     inline RE * getExpression() const {return mExpression;}
-    inline void setExpression(RE * const r) {mExpression = r; }
-    inline Name * getGraphemeExtenderRule() const {return mBoundaryRule;}
-    inline void setBoundaryRule(Name * const r) {mBoundaryRule = r; }
-    inline Type getType() const {return mType;}
+    inline void setExpression(RE * const r) { mExpression = r; }
+    inline Name * getBoundaryRule() const {return mBoundaryRule;}
+    inline void setBoundaryRule(Name * const r) { mBoundaryRule = r; }
 
 protected:
-    friend GraphemeBoundary * makeGraphemeBoundary(RE * const expression, const Type type);
-    GraphemeBoundary(RE * const expression, const Type type) : RE(ClassTypeId::GraphemeBoundary), mExpression(expression), mBoundaryRule(nullptr), mType(type) {}
+    friend GraphemeBoundary * makeGraphemeBoundary(const Type type, const Sense sense, RE * expression);
+    GraphemeBoundary(const Type type, const Sense sense, RE * expression) : RE(ClassTypeId::GraphemeBoundary), mType(type), mSense(sense), mExpression(expression), mBoundaryRule(nullptr) {}
     virtual ~GraphemeBoundary() {}
 
 private:
-    RE *        mExpression;
-    Name *      mBoundaryRule;
-    const Type  mType;
+    const Type      mType;
+    const Sense     mSense;
+    RE *            mExpression;
+    Name *          mBoundaryRule;
 };
 
-inline GraphemeBoundary * makeGraphemeBoundary(RE * const expression, const GraphemeBoundary::Type type) {
-    return new GraphemeBoundary(expression, type);
+inline GraphemeBoundary * makeGraphemeBoundary(const GraphemeBoundary::Type type, const GraphemeBoundary::Sense sense, RE * expression) {
+    return new GraphemeBoundary(type, sense, expression);
+}
+
+inline GraphemeBoundary * makeGraphemeClusterBoundary(const GraphemeBoundary::Sense sense = GraphemeBoundary::Sense::Positive, RE * expression = nullptr) {
+    return makeGraphemeBoundary(GraphemeBoundary::Type::ClusterBoundary, sense, expression);
 }
 

icGREP/icgrep-devel/icgrep/re/re_nullable.cpp

@@ -49 +49 @@
             name->setDefinition(removeNullablePrefix(name->getDefinition()));
         }
-    } else if (GraphemeBoundary * g = dyn_cast<GraphemeBoundary>(re)) {
-        g->setExpression(removeNullablePrefix(g->getExpression()));
     }
     return re;
@@ -86 +84 @@
             name->setDefinition(removeNullableSuffix(name->getDefinition()));
         }
-    } else if (GraphemeBoundary * g = dyn_cast<GraphemeBoundary>(re)) {
-        g->setExpression(removeNullableSuffix(g->getExpression()));
     }
     return re;

icGREP/icgrep-devel/icgrep/re/re_parser.cpp

@@ -47 +47 @@
         throw ParseFailure("An unexpected parsing error occurred!");
     }
-    if (parser.fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) {
-        re = makeGraphemeBoundary(re, GraphemeBoundary::Type::ClusterBoundary);
-    }
     return re;
 }
@@ -72 +69 @@
 
 RE * RE_Parser::parse_RE() {
-    RE * r = parse_alt();
-    return r;
+    return parse_alt();
 }
 
@@ -80 +76 @@
     for (;;) {
         alt.push_back(parse_seq());
-        if (mCursor.noMore() || *mCursor != '|') {
+        if (*mCursor != '|') {
             break;
         }
         ++mCursor; // advance past the alternation character '|'
     }
-    if (alt.empty())
-    {
+    if (alt.empty()) {
         throw NoRegularExpressionFound();
     }
@@ -106 +101 @@
 
 RE * RE_Parser::parse_next_item() {
-    RE * re = nullptr;
     if (mCursor.more()) {
         switch (*mCursor) {
@@ -119 +113 @@
                 return makeEnd();
             case '|': case ')':
-                return nullptr;  // This is ugly.
+                break;
             case '*': case '+': case '?': case '{':
                 throw NothingToRepeat();
@@ -126 +120 @@
                     return createCC(parse_utf8_codepoint());
                 }
-                else throw ParseFailure("Use  \\] for literal ].");
+                throw ParseFailure("Use  \\] for literal ].");
             case '}':
                 if (fNested) {
-                    return nullptr;  //  a recursive invocation for a regexp in \N{...}
-                }
-                else if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
+                    break;  //  a recursive invocation for a regexp in \N{...}
+                } else if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
                     return createCC(parse_utf8_codepoint());
                 }
-                else throw ParseFailure("Use \\} for literal }.");
+                throw ParseFailure("Use \\} for literal }.");
             case '[':
                 mCursor++;
@@ -148 +141 @@
         }
     }
-    return re;
-}
-
-
-// Parse some kind of parenthesized group.  Input precondition: _cursor
+    return nullptr;
+}
+
+
+// Parse some kind of parenthesized group.  Input precondition: mCursor
 // after the (
 RE * RE_Parser::parse_group() {
-    RE * subexpr;
-    RE * group_expr;
-    ModeFlagSet savedModeFlags = fModeFlagSet;
+    const ModeFlagSet modeFlagSet = fModeFlagSet;
+    RE * group_expr = nullptr;
     if (*mCursor == '?') {
         switch (*++mCursor) {
             case '#':  // comment
-                ++mCursor;
-                while (mCursor.more() && *mCursor != ')') {
-                    ++mCursor;
-                }
+                while (*++mCursor != ')');
                 ++mCursor;
                 return parse_next_item();
@@ -173 +162 @@
             case '=':
                 ++mCursor;
-                subexpr = parse_alt();
-                group_expr = makeLookAheadAssertion(subexpr);
+                group_expr = makeLookAheadAssertion(parse_alt());
                 break;
             case '!':
                 ++mCursor;
-                subexpr = parse_alt();
-                group_expr = makeNegativeLookAheadAssertion(subexpr);
+                group_expr = makeNegativeLookAheadAssertion(parse_alt());
                 break;
             case '>':
                 ++mCursor;
-                subexpr = parse_alt();
-                group_expr = makeAtomicGroup(subexpr);
+                group_expr = makeAtomicGroup(parse_alt());
                 break;
             case '|':
                 ++mCursor;
-                subexpr = parse_alt();
-                group_expr = makeBranchResetGroup(subexpr);
+                group_expr = makeBranchResetGroup(parse_alt());
                 break;
             case '<':
@@ -195 +180 @@
                 if (*mCursor == '=') {
                     ++mCursor;
-                    subexpr = parse_alt();
-                    group_expr = makeLookBehindAssertion(subexpr);
+                    group_expr = makeLookBehindAssertion(parse_alt());
                 }
                 else if (*mCursor == '!') {
                     ++mCursor;
-                    subexpr = parse_alt();
-                    group_expr = makeNegativeLookBehindAssertion(subexpr);
+                    group_expr = makeNegativeLookBehindAssertion(parse_alt());
                 } else {
                     throw ParseFailure("Illegal lookbehind assertion syntax.");
                 }
                 break;
-            case '-': case 'd' : case 'i': case 'm': case 's': case 'x': case 'g': {
-                bool negateMode = false;
-                ModeFlagType modeBit;
+            case '-': case 'd' : case 'i': case 'm': case 's': case 'x': case 'g':
                 while (*mCursor != ')' && *mCursor != ':') {
+                    bool negateMode = false;
+                    ModeFlagType modeBit;
                     if (*mCursor == '-') {
                         negateMode = true;
                         ++mCursor;
                     }
-                    switch (*mCursor++) {
+                    switch (*mCursor) {
                         case 'i': modeBit = CASE_INSENSITIVE_MODE_FLAG; break;
                         case 'g': modeBit = GRAPHEME_CLUSTER_MODE; break;
@@ -223 +206 @@
                         default: throw ParseFailure("Unsupported mode flag.");
                     }
+                    ++mCursor;
                     if (negateMode) {
                         fModeFlagSet &= ~modeBit;
@@ -233 +217 @@
                     ++mCursor;
                     group_expr = parse_alt();
+                    fModeFlagSet = modeFlagSet;
+                    break;
                 } else {  // if *_cursor == ')'
                     ++mCursor;
-                    // return immediately without restoring mode flags
                     return parse_next_item();
                 }
-                break;
-            }
             default:
                 throw ParseFailure("Illegal (? syntax.");
@@ -246 +229 @@
         group_expr = parse_alt();
     }
-    // Restore mode flags.
-    fModeFlagSet = savedModeFlags;
     if (*mCursor != ')') {
         throw ParseFailure("Closing parenthesis required.");
@@ -255 +236 @@
 }
 
-RE * RE_Parser::extend_item(RE * re) {
-    if (mCursor.noMore()) {
-        return re;
-    } else {
+inline RE * RE_Parser::extend_item(RE * re) {
+    if (LLVM_LIKELY(mCursor.more())) {
         int lb = 0, ub = 0;
+        bool hasRep = true;
         switch (*mCursor) {
             case '*':
@@ -277 +257 @@
                 break;
             default:
-                return re;
-        }
-        if (lb > MAX_REPETITION_LOWER_BOUND || ub > MAX_REPETITION_UPPER_BOUND) {
-            throw ParseFailure("Bounded repetition exceeds icgrep implementation limit");
-        }
-        if ((ub != Rep::UNBOUNDED_REP) && (lb > ub)) {
-            throw ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
-        }
-        ++mCursor;
-        if (*mCursor == '?') { // Non-greedy qualifier
-            // Greedy vs. non-greedy makes no difference for icgrep.
-            ++mCursor;
-        } else if (*mCursor == '+') {
-            ++mCursor;
-            throw ParseFailure("Possessive repetition is not supported in icgrep 1.0");
-        }
-        return makeRep(re, lb, ub);
-    }
+                hasRep = false;
+        }
+        if (hasRep) {
+            if (lb > MAX_REPETITION_LOWER_BOUND || ub > MAX_REPETITION_UPPER_BOUND) {
+                throw ParseFailure("Bounded repetition exceeds icgrep implementation limit");
+            }
+            if ((ub != Rep::UNBOUNDED_REP) && (lb > ub)) {
+                throw ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
+            }
+            ++mCursor;
+            if (*mCursor == '?') { // Non-greedy qualifier
+                // Greedy vs. non-greedy makes no difference for icgrep.
+                ++mCursor;
+            } else if (*mCursor == '+') {
+                ++mCursor;
+                throw ParseFailure("Possessive repetition is not supported in icgrep 1.0");
+            }
+            re = makeRep(re, lb, ub);
+        }
+    }
+    if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
+        re = makeGraphemeClusterBoundary(GraphemeBoundary::Sense::Positive, re);
+    }
+    return re;
 }
 
@@ -345 +331 @@
     }
 }
-    
-inline RE * makeGraphemeClusterBoundary() {
-    throw ParseFailure("makeGraphemeClusterBoundary() not yet supported.");
-}
-    
     
 RE * RE_Parser::parseEscapedSet() {
@@ -361 +342 @@
             } else {
                 switch (*++mCursor) {
-                    case 'g': re = makeGraphemeClusterBoundary();
+                    case 'g':
+                        re = makeGraphemeClusterBoundary(complemented ? GraphemeBoundary::Sense::Negative : GraphemeBoundary::Sense::Positive);
+                        break;
                     case 'w': throw ParseFailure("\\b{w} not yet supported.");
                     case 'l': throw ParseFailure("\\b{l} not yet supported.");
@@ -371 +354 @@
                 }
                 ++mCursor;
-                return complemented ? makeComplement(re) : re;
+                return re;
             }
         case 'd':
@@ -421 +404 @@
             // to get to the next extended grapheme cluster boundary.
             ++mCursor;
-            return makeGraphemeBoundary(makeAny(), GraphemeBoundary::Type::ClusterBoundary);
+            // return makeSeq({makeRep(makeAny(), 1, Rep::UNBOUNDED_REP), makeGraphemeClusterBoundary()});
+            return makeGraphemeClusterBoundary(GraphemeBoundary::Sense::Positive, makeAny());
         case 'N':
             if (*++mCursor != '{') {

icGREP/icgrep-devel/icgrep/re/re_simplifier.cpp

@@ -1 +1 @@
 #include "re_simplifier.h"
-#include "re_cc.h"
-#include "re_name.h"
-#include "re_start.h"
-#include "re_end.h"
-#include "re_seq.h"
-#include "re_alt.h"
-#include "re_rep.h"
-#include "re_diff.h"
-#include "re_intersect.h"
-#include "re_assertion.h"
+#include <re/re_name.h>
+#include <re/re_any.h>
+#include <re/re_start.h>
+#include <re/re_end.h>
+#include <re/re_alt.h>
+#include <re/re_cc.h>
+#include <re/re_seq.h>
+#include <re/re_rep.h>
+#include <re/re_diff.h>
+#include <re/re_intersect.h>
+#include <re/re_assertion.h>
+#include <re/re_grapheme_boundary.hpp>
 #include <algorithm>
 #include <memory>
@@ -24 +26 @@
         }
         re = makeAlt(list.begin(), list.end());
-    }
-    else if (Seq * seq = dyn_cast<Seq>(re)) {
+    } else if (Seq * seq = dyn_cast<Seq>(re)) {
         std::vector<RE*> list;
         list.reserve(seq->size());
@@ -32 +33 @@
         }
         re = makeSeq(list.begin(), list.end());
-    }
-    else if (Assertion * a = dyn_cast<Assertion>(re)) {
+    } else if (Assertion * a = dyn_cast<Assertion>(re)) {
         re = makeAssertion(simplify(a->getAsserted()), a->getKind(), a->getSense());
-    }
-    else if (Rep * rep = dyn_cast<Rep>(re)) {
+    } else if (Rep * rep = dyn_cast<Rep>(re)) {
         re = makeRep(simplify(rep->getRE()), rep->getLB(), rep->getUB());
-    }
-    else if (Diff * diff = dyn_cast<Diff>(re)) {
+    } else if (Diff * diff = dyn_cast<Diff>(re)) {
         re = makeDiff(simplify(diff->getLH()), diff->getRH());
-    }
-    else if (Intersect * e = dyn_cast<Intersect>(re)) {
+    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
         re = makeIntersect(simplify(e->getLH()), e->getRH());
     }

icGREP/icgrep-devel/icgrep/re/re_simplifier.h

@@ -2 +2 @@
 #define RE_SIMPLIFIER_H
 
-//Regular Expressions
-#include "re_seq.h"
-#include <list>
-
 namespace re {
 
-class Alt;
+class RE;
 
 class RE_Simplifier {