Changeset 5812

Timestamp:

Dec 28, 2017, 1:15:13 PM (14 months ago)

Author:

nmedfort

Message:

Bug fix for RE local + some clean up of RE local and the RE Compiler

Location:

icGREP/icgrep-devel/icgrep

Files:

• IR_Gen/CBuilder.cpp (modified) (2 diffs)
• grep_engine.cpp (modified) (1 diff)
• re/re_compiler.cpp (modified) (18 diffs)
• re/re_compiler.h (modified) (5 diffs)
• re/re_local.cpp (modified) (6 diffs)
• re/re_local.h (modified) (1 diff)
• re/re_nullable.h (modified) (1 diff)
• re/re_reverse.cpp (modified) (8 diffs)
• re/re_reverse.h (modified) (1 diff)

icGREP/icgrep-devel/icgrep/IR_Gen/CBuilder.cpp

@@ -1311 +1311 @@
         if (Align > 1) {
             ConstantInt * align = ConstantInt::get(intPtrTy, Align);
-            CreateAssertZero(CreateURem(intSrc, align), "CreateMemCpy: Src pointer is misaligned");
-            CreateAssertZero(CreateURem(intDst, align), "CreateMemCpy: Dst pointer is misaligned");
+            CreateAssertZero(CreateURem(intSrc, align), "CreateMemCpy: Src is misaligned");
+            CreateAssertZero(CreateURem(intDst, align), "CreateMemCpy: Dst is misaligned");
         }
         Value * intSize = CreateZExtOrTrunc(Size, intPtrTy);
@@ -1326 +1326 @@
     if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
         CHECK_ADDRESS(Ptr, Size, "CreateMemSet");
+        if (Align > 1) {
+            DataLayout DL(getModule());
+            IntegerType * const intPtrTy = DL.getIntPtrType(getContext());
+            Value * intPtr = CreatePtrToInt(Ptr, intPtrTy);
+            ConstantInt * align = ConstantInt::get(intPtrTy, Align);
+            CreateAssertZero(CreateURem(intPtr, align), "CreateMemSet: Ptr is misaligned");
+        }
     }
     return IRBuilder<>::CreateMemSet(Ptr, Val, Size, Align, isVolatile, TBAATag, ScopeTag, NoAliasTag);

icGREP/icgrep-devel/icgrep/grep_engine.cpp

@@ -484 +484 @@
         mGrepDriver->performIncrementalCacheCleanupStep();
     }
-}
-
-}
+    return nullptr;
+}
+
+}

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

@@ -42 +42 @@
 using namespace llvm;
 
+using FollowMap = std::map<re::CC *, re::CC*>;
+
 namespace re {
 
-PabloAST * RE_Compiler::compile(RE * re) {
-    return markerVar(AdvanceMarker(compile(re, mPB), MarkerPosition::FinalPostPositionUnit, mPB));
-}
-    
-MarkerType RE_Compiler::compile(RE * re, PabloBuilder & pb) {
-    return process(re, makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createOnes()), pb);
+using MarkerType = RE_Compiler::MarkerType;
+
+PabloAST * RE_Compiler::compile(RE * re, PabloAST * const initialCursors) {
+    const auto markers = initialCursors ? compile(re, initialCursors, mPB) : compile(re, mPB);
+    return markerVar(AdvanceMarker(markers, FinalPostPositionUnit, mPB));
+}
+
+inline MarkerType RE_Compiler::compile(RE * re, PabloAST * const cursors, PabloBuilder & pb) {
+    return process(re, makeMarker(FinalMatchUnit, cursors), pb);
+}
+
+inline MarkerType RE_Compiler::compile(RE * re, PabloBuilder & pb) {
+    return process(re, makeMarker(FinalPostPositionUnit, pb.createOnes()), pb);
 }
     
@@ -82 +91 @@
 
 inline MarkerType RE_Compiler::compileAny(const MarkerType m, PabloBuilder & pb) {
-    PabloAST * const nextFinalByte = markerVar(AdvanceMarker(m, MarkerPosition::FinalPostPositionUnit, pb));
-    return makeMarker(MarkerPosition::FinalMatchUnit, nextFinalByte);
+    PabloAST * const nextFinalByte = markerVar(AdvanceMarker(m, FinalPostPositionUnit, pb));
+    return makeMarker(FinalMatchUnit, nextFinalByte);
 }
 
@@ -89 +98 @@
     // If Unicode CCs weren't pulled out earlier, we generate the equivalent
     // byte sequence as an RE.
-    if (cc->getAlphabet() == &cc::Unicode) return process(toUTF8(cc), marker, pb);
+    if (cc->getAlphabet() == &cc::Unicode) {
+        return process(toUTF8(cc), marker, pb);
+    }
     PabloAST * nextPos = markerVar(marker);
     if (isByteLength(cc)) {
-        if (marker.pos == MarkerPosition::FinalMatchUnit) nextPos = pb.createAdvance(nextPos, 1);
-    }
-    else {
-        nextPos = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
-    }
-    return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(nextPos, mCCCompiler.compileCC(cc, pb)));
+        if (marker.pos == FinalMatchUnit) {
+            nextPos = pb.createAdvance(nextPos, 1);
+        }
+    } else {
+        nextPos = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
+    }
+    return makeMarker(FinalMatchUnit, pb.createAnd(nextPos, mCCCompiler.compileCC(cc, pb)));
 }
 
@@ -110 +122 @@
     } else if (isUnicodeUnitLength(name)) {
         MarkerType nameMarker = compileName(name, pb);
-        MarkerType nextPos = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
+        MarkerType nextPos = AdvanceMarker(marker, FinalPostPositionUnit, pb);
         nameMarker.stream = pb.createAnd(markerVar(nextPos), markerVar(nameMarker), name->getName());
         return nameMarker;
@@ -172 +184 @@
 }
 
-MarkerType RE_Compiler::compileAlt(Alt * alt, MarkerType marker, PabloBuilder & pb) {
-    std::vector<PabloAST *>  accum(3, pb.createZeroes());
-    MarkerType const base = marker;
+MarkerType RE_Compiler::compileAlt(Alt * alt, const MarkerType base, PabloBuilder & pb) {
+    std::array<PabloAST *, 3> accum;
     // The following may be useful to force a common Advance rather than separate
     // Advances in each alternative.
+    accum.fill(pb.createZeroes());
     for (RE * re : *alt) {
         MarkerType m = process(re, base, pb);
-        MarkerPosition p = markerPos(m);
+        const MarkerPosition p = markerPos(m);
         accum[p] = pb.createOr(accum[p], markerVar(m), "alt");
     }
-    if (isa<Zeroes>(accum[MarkerPosition::InitialPostPositionUnit]) && isa<Zeroes>(accum[MarkerPosition::FinalPostPositionUnit])) {
-        return makeMarker(MarkerPosition::FinalMatchUnit, accum[MarkerPosition::FinalMatchUnit]);
-    }
-    PabloAST * combine = pb.createOr(accum[InitialPostPositionUnit], pb.createAdvance(accum[MarkerPosition::FinalMatchUnit], 1), "alt");
+    if (isa<Zeroes>(accum[InitialPostPositionUnit]) && isa<Zeroes>(accum[FinalPostPositionUnit])) {
+        return makeMarker(FinalMatchUnit, accum[FinalMatchUnit]);
+    }
+
+    PabloAST * combine = pb.createOr(accum[InitialPostPositionUnit], pb.createAdvance(accum[FinalMatchUnit], 1), "alt");
     if (isa<Zeroes>(accum[FinalPostPositionUnit])) {
         return makeMarker(InitialPostPositionUnit, combine);
     }
-    combine = pb.createOr(pb.createScanThru(pb.createAnd(mInitial, combine), mNonFinal), accum[MarkerPosition::FinalPostPositionUnit], "alt");
-    return makeMarker(MarkerPosition::FinalPostPositionUnit, combine);
+    combine = pb.createOr(pb.createScanThru(pb.createAnd(mInitial, combine), mNonFinal), accum[FinalPostPositionUnit], "alt");
+    return makeMarker(FinalPostPositionUnit, combine);
 }
 
@@ -205 +218 @@
     } else if (a->getKind() == Assertion::Kind::Boundary) {
         MarkerType cond = compile(asserted, pb);
-        if (LLVM_LIKELY(markerPos(cond) == MarkerPosition::FinalMatchUnit)) {
-            MarkerType postCond = AdvanceMarker(cond, MarkerPosition::FinalPostPositionUnit, pb);
+        if (LLVM_LIKELY(markerPos(cond) == FinalMatchUnit)) {
+            MarkerType postCond = AdvanceMarker(cond, FinalPostPositionUnit, pb);
             PabloAST * boundaryCond = pb.createXor(markerVar(cond), markerVar(postCond));
             if (a->getSense() == Assertion::Sense::Negative) {
                 boundaryCond = pb.createNot(boundaryCond);
             }
-            MarkerType fbyte = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
-            return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), boundaryCond, "boundary"));
+            MarkerType fbyte = AdvanceMarker(marker, FinalPostPositionUnit, pb);
+            return makeMarker(FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), boundaryCond, "boundary"));
         }
         else UnsupportedRE("Unsupported boundary assertion");
     } else if (isUnicodeUnitLength(asserted)) {
         MarkerType lookahead = compile(asserted, pb);
-        if (LLVM_LIKELY(markerPos(lookahead) == MarkerPosition::FinalMatchUnit)) {
+        if (LLVM_LIKELY(markerPos(lookahead) == FinalMatchUnit)) {
             PabloAST * la = markerVar(lookahead);
             if (a->getSense() == Assertion::Sense::Negative) {
                 la = pb.createNot(la);
             }
-            MarkerType fbyte = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
-            return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), la, "lookahead"));
+            MarkerType fbyte = AdvanceMarker(marker, FinalPostPositionUnit, pb);
+            return makeMarker(FinalPostPositionUnit, pb.createAnd(markerVar(fbyte), la, "lookahead"));
         }
     }
@@ -335 +348 @@
 
 MarkerType RE_Compiler::processLowerBound(RE * repeated, int lb, MarkerType marker, int ifGroupSize, PabloBuilder & pb) {
-    if (LLVM_UNLIKELY(lb == 0)) return marker;
-    else if (LLVM_UNLIKELY(lb == 1)) return process(repeated, marker, pb);
+    if (LLVM_UNLIKELY(lb == 0)) {
+        return marker;
+    } else if (LLVM_UNLIKELY(lb == 1)) {
+        return process(repeated, marker, pb);
+    }
     //
     // A bounded repetition with an upper bound of at least 2.
@@ -345 +361 @@
             PabloAST * cc = markerVar(compile(repeated, pb));
             PabloAST * cc_lb = consecutive_matches(cc, 1, lb, nullptr, pb);
-            const auto pos = markerPos(marker) == MarkerPosition::FinalMatchUnit ? lb : lb - 1;
+            const auto pos = markerPos(marker) == FinalMatchUnit ? lb : lb - 1;
             PabloAST * marker_fwd = pb.createAdvance(markerVar(marker), pos);
-            return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
+            return makeMarker(FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
         }
         else if (isUnicodeUnitLength(repeated)) {
             PabloAST * cc = markerVar(compile(repeated, pb));
             PabloAST * cc_lb = consecutive_matches(cc, 1, lb, mFinal, pb);
-            const auto pos = markerPos(marker) == MarkerPosition::FinalMatchUnit ? lb : lb - 1;
+            const auto pos = markerPos(marker) == FinalMatchUnit ? lb : lb - 1;
             PabloAST * marker_fwd = pb.createIndexedAdvance(markerVar(marker), mFinal, pos);
-            return makeMarker(MarkerPosition::FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
+            return makeMarker(FinalMatchUnit, pb.createAnd(marker_fwd, cc_lb, "lowerbound"));
         }
         else if (isTypeForLocal(repeated)) {
-            CC * firstSymSet = RE_Local::first(repeated);
-            std::map<CC *, CC*> followMap;
-            RE_Local::follow(repeated, followMap);
-            bool firstSymSet_found_in_follow = false;
-            for (auto & entry : followMap) {
-                if (entry.second->intersects(*firstSymSet)) {
-                    firstSymSet_found_in_follow = true;
-                }
-            }
-            if (!firstSymSet_found_in_follow) {
-                // When the first symbol is unique, we can use it as an index stream.
-                PabloAST * firstCCstream = markerVar(compile(firstSymSet, pb));
+            CC * const first = RE_Local::getFirstUniqueSymbol(repeated);
+            if (first) { // if the first symbol is unique, we can use it as an index stream.
+                PabloAST * firstCCstream = markerVar(compile(first, pb));
                 // Find all matches to the repeated regexp.
-                PabloAST * submatch = markerVar(AdvanceMarker(compile(repeated, pb), MarkerPosition::FinalPostPositionUnit, pb));
+                PabloAST * submatch = markerVar(AdvanceMarker(compile(repeated, pb), FinalPostPositionUnit, pb));
                 // Consecutive submatches require that the symbol following the end of one submatch is the first symbol for
                 // the next submatch.   lb-1 such submatches are required.
                 PabloAST * consecutive_submatch = consecutive_matches(submatch, 1, lb-1, firstCCstream, pb);
                 // Find submatch positions which are lb-2 start symbols forward from the current marker position.
-                PabloAST * base = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
+                PabloAST * base = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
                 PabloAST * marker_fwd = pb.createIndexedAdvance(base, firstCCstream, lb - 1);
                 PabloAST * consecutive_lb_1 = pb.createAnd(marker_fwd, consecutive_submatch);
                 // From any of these positions, any position reachable by one more occurrence of the
                 // regexp is a match.
-                return process(repeated, makeMarker(MarkerPosition::FinalPostPositionUnit, consecutive_lb_1), pb);
+                return process(repeated, makeMarker(FinalPostPositionUnit, consecutive_lb_1), pb);
             }
         }
@@ -404 +411 @@
     
 MarkerType RE_Compiler::processBoundedRep(RE * repeated, int ub, MarkerType marker, int ifGroupSize,  PabloBuilder & pb) {
-    if (LLVM_UNLIKELY(ub == 0)) return marker;
+    if (LLVM_UNLIKELY(ub == 0)) {
+        return marker;
+    }
     //
     // A bounded repetition with an upper bound of at least 2.
@@ -414 +423 @@
             // Create a mask of positions reachable within ub from current marker.
             // Use matchstar, then apply filter.
-            PabloAST * cursor = markerVar(AdvanceMarker(marker, MarkerPosition::InitialPostPositionUnit, pb));
+            PabloAST * cursor = markerVar(AdvanceMarker(marker, InitialPostPositionUnit, pb));
             // If we've advanced the cursor to the post position unit, cursor begins on the first masked bit of the bounded mask.
             // Extend the mask by ub - 1 byte positions to ensure the mask ends on the FinalMatchUnit of the repeated region.
@@ -422 +431 @@
             // "multi-byte" character. Combine the masked range with any nonFinals.
             PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
-            return makeMarker(MarkerPosition::InitialPostPositionUnit, bounded);
+            return makeMarker(InitialPostPositionUnit, bounded);
         }
         else if (isUnicodeUnitLength(repeated)) {
             // For a regexp which represent a single Unicode codepoint, we can use the mFinal stream
             // as an index stream for an indexed advance operation.
-            PabloAST * cursor = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
+            PabloAST * cursor = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
             PabloAST * upperLimitMask = reachable(cursor, 1, ub - 1, mFinal, pb);
             PabloAST * masked = pb.createAnd(markerVar(compile(repeated, pb)), upperLimitMask, "masked");
             PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
-            return makeMarker(MarkerPosition::FinalPostPositionUnit, bounded);
+            return makeMarker(FinalPostPositionUnit, bounded);
         }
         else if (isTypeForLocal(repeated)) {
-            CC * firstSymSet = RE_Local::first(repeated);
-            std::map<CC *, CC*> followMap;
-            RE_Local::follow(repeated, followMap);
-            bool firstSymSet_found_in_follow = false;
-            for (auto & entry : followMap) {
-                if (entry.second->intersects(*firstSymSet)) {
-                    firstSymSet_found_in_follow = true;
-                }
-            }
-            if (!firstSymSet_found_in_follow) {
-                // When the first symbol is unique, we can use it as an index stream.
-                PabloAST * firstCCstream = markerVar(compile(firstSymSet, pb));
-                PabloAST * cursor = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
+            CC * const first = RE_Local::getFirstUniqueSymbol(repeated);
+            if (first) { // if the first symbol is unique, we can use it as an index stream.
+                PabloAST * firstCCstream = markerVar(compile(first, pb));
+                PabloAST * cursor = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
                 PabloAST * upperLimitMask = reachable(cursor, 1, ub - 1, firstCCstream, pb);
-                PabloAST * masked = pb.createAnd(markerVar(AdvanceMarker(compile(repeated, pb), MarkerPosition::FinalPostPositionUnit, pb)), upperLimitMask, "masked");
+                PabloAST * masked = pb.createAnd(markerVar(AdvanceMarker(compile(repeated, pb), FinalPostPositionUnit, pb)), upperLimitMask, "masked");
                 PabloAST * bounded = pb.createMatchStar(cursor, pb.createOr(masked, mNonFinal), "bounded");
-                return makeMarker(MarkerPosition::FinalPostPositionUnit, bounded);
+                return makeMarker(FinalPostPositionUnit, bounded);
             }
         }
@@ -478 +478 @@
 MarkerType RE_Compiler::processUnboundedRep(RE * repeated, MarkerType marker, PabloBuilder & pb) {
     // always use PostPosition markers for unbounded repetition.
-    PabloAST * base = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
+    PabloAST * base = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
     if (isByteLength(repeated)  && !AlgorithmOptionIsSet(DisableMatchStar)) {
         PabloAST * mask = markerVar(compile(repeated, pb));
@@ -484 +484 @@
         // The post position character may land on the initial byte of a multi-byte character. Combine them with the masked range.
         PabloAST * unbounded = pb.createMatchStar(base, pb.createOr(mask, nonFinal), "unbounded");
-        return makeMarker(MarkerPosition::FinalPostPositionUnit, unbounded);
+        return makeMarker(FinalPostPositionUnit, unbounded);
     } else if (isUnicodeUnitLength(repeated) && !AlgorithmOptionIsSet(DisableMatchStar) && !AlgorithmOptionIsSet(DisableUnicodeMatchStar)) {
         PabloAST * cc = markerVar(compile(repeated, pb));
@@ -492 +492 @@
         mstar = pb.createMatchStar(base, cc);
         PabloAST * final = mFinal;
-        return makeMarker(MarkerPosition::FinalPostPositionUnit, pb.createAnd(mstar, final, "unbounded"));
+        return makeMarker(FinalPostPositionUnit, pb.createAnd(mstar, final, "unbounded"));
     } else if (mStarDepth > 0){
         PabloBuilder * const outer = pb.getParent();
@@ -500 +500 @@
         PabloAST * m1 = pb.createOr(base, starPending);
         PabloAST * m2 = pb.createOr(base, starAccum);
-        MarkerType result = process(repeated, makeMarker(MarkerPosition::FinalPostPositionUnit, m1), pb);
-        result = AdvanceMarker(result, MarkerPosition::FinalPostPositionUnit, pb);
+        MarkerType result = process(repeated, makeMarker(FinalPostPositionUnit, m1), pb);
+        result = AdvanceMarker(result, FinalPostPositionUnit, pb);
         PabloAST * loopComputation = markerVar(result);
         pb.createAssign(starPending, pb.createAnd(loopComputation, pb.createNot(m2)));
@@ -517 +517 @@
         mCompiledName = &nestedMap;
         mStarDepth++;
-        MarkerType result = process(repeated, makeMarker(MarkerPosition::FinalPostPositionUnit, whilePending), wb);
-        result = AdvanceMarker(result, MarkerPosition::FinalPostPositionUnit, wb);
+        MarkerType result = process(repeated, makeMarker(FinalPostPositionUnit, whilePending), wb);
+        result = AdvanceMarker(result, FinalPostPositionUnit, wb);
         PabloAST * loopComputation = markerVar(result);
         wb.createAssign(whilePending, wb.createAnd(loopComputation, wb.createNot(whileAccum)));
@@ -532 +532 @@
 inline MarkerType RE_Compiler::compileStart(MarkerType marker, pablo::PabloBuilder & pb) {
     PabloAST * sol = pb.createNot(pb.createAdvance(pb.createNot(mLineBreak), 1));
-    MarkerType m = AdvanceMarker(marker, MarkerPosition::InitialPostPositionUnit, pb);
-    return makeMarker(MarkerPosition::InitialPostPositionUnit, pb.createAnd(markerVar(m), sol, "sol"));
+    MarkerType m = AdvanceMarker(marker, InitialPostPositionUnit, pb);
+    return makeMarker(InitialPostPositionUnit, pb.createAnd(markerVar(m), sol, "sol"));
 }
 
 inline MarkerType RE_Compiler::compileEnd(MarkerType marker, pablo::PabloBuilder & pb) {
-    PabloAST * const nextPos = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb));
-    PabloAST * atEOL = pb.createOr(pb.createAnd(mLineBreak, nextPos), pb.createAdvance(pb.createAnd(nextPos, mCRLF), 1), "eol");
-    return makeMarker(MarkerPosition::FinalPostPositionUnit, atEOL);
+    PabloAST * const nextPos = markerVar(AdvanceMarker(marker, FinalPostPositionUnit, pb));
+    PabloAST * const atEOL = pb.createOr(pb.createAnd(mLineBreak, nextPos), pb.createAdvance(pb.createAnd(nextPos, mCRLF), 1), "eol");
+    return makeMarker(FinalPostPositionUnit, atEOL);
 }
 
 inline MarkerType RE_Compiler::AdvanceMarker(MarkerType marker, const MarkerPosition newpos, PabloBuilder & pb) {
     if (marker.pos != newpos) {
-        if (marker.pos == MarkerPosition::FinalMatchUnit) {
+        if (marker.pos == FinalMatchUnit) {
             marker.stream = pb.createAdvance(marker.stream, 1, "ipp");
-            marker.pos = MarkerPosition::InitialPostPositionUnit;
-        }
-        if (newpos == MarkerPosition::FinalPostPositionUnit) {
-            PabloAST * nonFinal = mNonFinal;
-            marker.stream = pb.createScanThru(pb.createAnd(mInitial, marker.stream), nonFinal, "fpp");
-            marker.pos = MarkerPosition::FinalPostPositionUnit;
+            marker.pos = InitialPostPositionUnit;
+        }
+        if (newpos == FinalPostPositionUnit) {
+            marker.stream = pb.createScanThru(pb.createAnd(mInitial, marker.stream), mNonFinal, "fpp");
+            marker.pos = FinalPostPositionUnit;
         }
     }
@@ -589 +588 @@
     mNonFinal = mPB.createExtract(required, mPB.getInteger(1));
     mFinal = mPB.createExtract(required, mPB.getInteger(2));
-
 }
 

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

@@ -25 +25 @@
 namespace re { class CC; }
 
-//namespace UCD {
-//class UnicodeSet;
-//}
-
 /*   Marker streams represent the results of matching steps.
      Three types of marker streams are used internally.
@@ -43 +39 @@
 namespace re {
 
-enum MarkerPosition {FinalMatchUnit, InitialPostPositionUnit, FinalPostPositionUnit};
-
-struct MarkerType { 
-    MarkerPosition pos;
-    pablo::PabloAST * stream;
-    MarkerType & operator =(const MarkerType &) = default;
-};
-
-inline MarkerPosition markerPos(const MarkerType & m) {return m.pos; }
-
-inline pablo::PabloAST * markerVar(const MarkerType & m) {return m.stream; }
-
-inline MarkerType makeMarker(MarkerPosition newpos, pablo::PabloAST * strm) {return {newpos, strm};}
-
-
 class RE_Compiler {
 public:
 
+    enum MarkerPosition {FinalMatchUnit, InitialPostPositionUnit, FinalPostPositionUnit};
+
+    struct MarkerType {
+        MarkerPosition pos;
+        pablo::PabloAST * stream;
+        MarkerType & operator =(const MarkerType &) = default;
+    };
+
     RE_Compiler(pablo::PabloKernel * kernel, cc::CC_Compiler & ccCompiler);
-    pablo::PabloAST * compile(RE * re);
+    pablo::PabloAST * compile(RE * re, pablo::PabloAST * const initialCursors = nullptr);
 
     static LLVM_ATTRIBUTE_NORETURN void UnsupportedRE(std::string errmsg);
@@ -88 +77 @@
     };
 
-    MarkerType compile(RE * re, pablo::PabloBuilder & cg);
+
+    MarkerType compile(RE * re, pablo::PabloBuilder & pb);
+    MarkerType compile(RE * re, pablo::PabloAST * const cursors, pablo::PabloBuilder & pb);
 
     MarkerType process(RE * re, MarkerType marker, pablo::PabloBuilder & pb);
@@ -95 +86 @@
     MarkerType compileSeq(Seq * seq, MarkerType marker, pablo::PabloBuilder & pb);
     MarkerType compileSeqTail(Seq::iterator current, const Seq::iterator end, int matchLenSoFar, MarkerType marker, pablo::PabloBuilder & pb);
-    MarkerType compileAlt(Alt * alt, MarkerType marker, pablo::PabloBuilder & pb);
+    MarkerType compileAlt(Alt * alt, MarkerType base, pablo::PabloBuilder & pb);
     MarkerType compileAssertion(Assertion * a, MarkerType marker, pablo::PabloBuilder & pb);
     MarkerType compileRep(Rep * rep, MarkerType marker, pablo::PabloBuilder & pb);
@@ -114 +105 @@
     MarkerType AdvanceMarker(MarkerType marker, const MarkerPosition newpos, pablo::PabloBuilder & pb);
     void AlignMarkers(MarkerType & m1, MarkerType & m2, pablo::PabloBuilder & pb);
+
+    static inline MarkerPosition markerPos(const MarkerType & m) {return m.pos; }
+    static inline pablo::PabloAST * markerVar(const MarkerType & m) {return m.stream; }
+    static inline MarkerType makeMarker(MarkerPosition newpos, pablo::PabloAST * strm) {return {newpos, strm};}
 
 private:

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

@@ -8 +8 @@
 #include <re/re_intersect.h>
 #include <re/re_assertion.h>
-#include <re/re_any.h>
 #include <re/re_analysis.h>
-#include <UCD/resolve_properties.h>
-#include <boost/container/flat_set.hpp>
+#include <re/re_nullable.h>
+#include <boost/container/flat_map.hpp>
 #include <boost/range/adaptor/reversed.hpp>
-#include <util/slab_allocator.h>
-#include <map>
 
 using namespace boost::container;
@@ -20 +17 @@
 
 namespace re {
-  
-inline void combine(CC *& a, CC * b) {
+
+using FollowMap = flat_map<const CC *, const CC*>;
+
+inline const CC * combine(const CC * a, const CC * b) {
     if (a && b) {
-        a = makeCC(a, b);
+        return makeCC(a, b);
     } else if (b) {
-        a = b;
+        return b;
     }
+    return a;
 }
 
-CC * RE_Local::first(RE * re) {
-    if (Name * name = dyn_cast<Name>(re)) {
+const CC * first(const RE * re) {
+    if (const Name * name = dyn_cast<Name>(re)) {
         if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
             return first(name->getDefinition());
@@ -36 +36 @@
             UndefinedNameError(name);
         }
-    } else if (CC * cc = dyn_cast<CC>(re)) {
+    } else if (const CC * cc = dyn_cast<CC>(re)) {
         return cc;
-    } else if (Seq * seq = dyn_cast<Seq>(re)) {
-        CC * cc = nullptr;
+    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
+        const CC * cc = nullptr;
         for (auto & si : *seq) {
-            combine(cc, first(si));
-            if (!isNullable(si)) {
+            cc = combine(cc, first(si));
+            if (!RE_Nullable::isNullable(si)) {
                 break;
             }
         }
         return cc;
-    } else if (Alt * alt = dyn_cast<Alt>(re)) {
-        CC * cc = nullptr;
+    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
+        const CC * cc = nullptr;
         for (auto & ai : *alt) {
-            combine(cc, first(ai));
+            cc = combine(cc, first(ai));
         }
         return cc;
-    } else if (Rep * rep = dyn_cast<Rep>(re)) {
+    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
         return first(rep->getRE());
-    } else if (Diff * diff = dyn_cast<Diff>(re)) {
-        if (CC * lh = first(diff->getLH())) {
-            if (CC * rh = first(diff->getRH())) {
+    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
+        if (const CC * lh = first(diff->getLH())) {
+            if (const CC * rh = first(diff->getRH())) {
                 return subtractCC(lh, rh);
             }
         }
-    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
-        if (CC * lh = first(ix->getLH())) {
-            if (CC * rh = first(ix->getRH())) {
+    } else if (const Intersect * ix = dyn_cast<Intersect>(re)) {
+        if (const CC * lh = first(ix->getLH())) {
+            if (const CC * rh = first(ix->getRH())) {
                 return intersectCC(lh, rh);
             }
@@ -71 +71 @@
 }
 
-CC * RE_Local::final(RE * re) {
-    if (Name * name = dyn_cast<Name>(re)) {
+const CC * final(const RE * re) {
+    if (const Name * name = dyn_cast<Name>(re)) {
         if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
             return final(name->getDefinition());
@@ -78 +78 @@
             UndefinedNameError(name);
         }
-    } else if (CC * cc = dyn_cast<CC>(re)) {
+    } else if (const CC * cc = dyn_cast<CC>(re)) {
         return cc;
-    } else if (Seq * seq = dyn_cast<Seq>(re)) {
-        CC * cc = nullptr;
+    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
+        const CC * cc = nullptr;
         for (auto & si : boost::adaptors::reverse(*seq)) {
-            combine(cc, first(si));
-            if (!isNullable(si)) {
+            cc = combine(cc, final(si));
+            if (!RE_Nullable::isNullable(si)) {
                 break;
             }
         }
         return cc;
-    } else if (Alt * alt = dyn_cast<Alt>(re)) {
-        CC * cc = nullptr;
+    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
+        const CC * cc = nullptr;
         for (auto & ai : *alt) {
-            combine(cc, final(ai));
+            cc = combine(cc, final(ai));
         }
         return cc;
-    } else if (Rep * rep = dyn_cast<Rep>(re)) {
+    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
         return final(rep->getRE());
-    } else if (Diff * diff = dyn_cast<Diff>(re)) {
-        if (CC * lh = final(diff->getLH())) {
-            if (CC * rh = final(diff->getRH())) {
+    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
+        if (const CC * lh = final(diff->getLH())) {
+            if (const CC * rh = final(diff->getRH())) {
                 return subtractCC(lh, rh);
             }
         }
-    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
-        if (CC * lh = final(ix->getLH())) {
-            if (CC * rh = final(ix->getRH())) {
+    } else if (const Intersect * ix = dyn_cast<Intersect>(re)) {
+        if (const CC * lh = final(ix->getLH())) {
+            if (const CC * rh = final(ix->getRH())) {
                 return intersectCC(lh, rh);
             }
@@ -114 +114 @@
 }
 
-void RE_Local::follow(RE * re, std::map<CC *, CC*> &follow_map) {
-    if (Name * name = dyn_cast<Name>(re)) {
+void follow(const RE * re, FollowMap & follows) {
+    if (const Name * name = dyn_cast<Name>(re)) {
         if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
-            return follow(name->getDefinition(), follow_map);
+            return follow(name->getDefinition(), follows);
         } else {
             UndefinedNameError(name);
         }
-    } else if (Seq * seq = dyn_cast<Seq>(re)) {
-        if (seq->size() > 0) {
-            RE * re_first = *(seq->begin());
-            RE * re_follow = makeSeq(seq->begin() + 1, seq->end());
+    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
+        if (!seq->empty()) {
+            const RE * const re_first = *(seq->begin());
+            const RE * const re_follow = makeSeq(seq->begin() + 1, seq->end());
             auto e1 = final(re_first);
             auto e2 = first(re_follow);
             if (e1 && e2) {
-                auto e = follow_map.find(e1);
-                if (e != follow_map.end()) {
+                auto e = follows.find(e1);
+                if (e != follows.end()) {
                     e->second = makeCC(e->second, e2);
                 } else {
-                    follow_map.emplace(e1, e2);
+                    follows.emplace(e1, e2);
                 }
             }
-            follow(re_first, follow_map);
-            follow(re_follow, follow_map);
+            follow(re_first, follows);
+            follow(re_follow, follows);
         }
-    } else if (Alt * alt = dyn_cast<Alt>(re)) {
+    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
         for (auto ai = alt->begin(); ai != alt->end(); ++ai) {
-            follow(*ai, follow_map);
+            follow(*ai, follows);
         }
-    } else if (Rep * rep = dyn_cast<Rep>(re)) {
-        auto e1 = final(rep->getRE());
+    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
+        const auto e1 = final(rep->getRE());
         auto e2 = first(rep->getRE());
         if (e1 && e2) {
-            auto e = follow_map.find(e1);
-            if (e != follow_map.end()) {
+            auto e = follows.find(e1);
+            if (e != follows.end()) {
                 e->second = makeCC(e->second, e2);
             } else {
-                follow_map.emplace(e1, e2);
+                follows.emplace(e1, e2);
             }
         }
-        follow(rep->getRE(), follow_map);
+        follow(rep->getRE(), follows);
     }
 }
 
-bool RE_Local::isLocalLanguage(RE * re) {    
-    UCD::UnicodeSet seen;
-    return isLocalLanguage_helper(re, seen);
-}
-
-bool RE_Local::isLocalLanguage_helper(const RE * re, UCD::UnicodeSet & seen) {
-    assert ("RE object cannot be null!" && re);
-    if (isa<Any>(re)) {
-        const bool no_intersect = seen.empty();
-        seen.insert_range(0x00, 0x10FFFF);
-        return no_intersect;
-    } else if (const CC * cc = dyn_cast<CC>(re)) {
-        const bool has_intersect = cc->intersects(seen);
-        seen = seen + *cc;
-        return !has_intersect;
-    } else if (const Name * n = dyn_cast<Name>(re)) {
-        return isLocalLanguage_helper(n->getDefinition(), seen);
-    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
-        for (const RE * item : *seq) {
-            if (!isLocalLanguage_helper(item, seen)) return false;
-        }
-        return true;
-    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
-        for (RE * item : *alt) {
-            if (!isLocalLanguage_helper(item, seen)) return false;
-        }
-        return true;
-    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
-        if (rep->getUB() > 1) return false;
-        return isLocalLanguage_helper(rep->getRE(), seen);
-    } else {
-        // A local language cannot contain Intersects, Differences, Assertions, Start, End.
-        return false;
-    }
-}
-
-bool RE_Local::isNullable(const RE * re) {
-    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
-        for (const RE * re : *re_seq) {
-            if (!isNullable(re)) {
-                return false;
+CC * RE_Local::getFirstUniqueSymbol(RE * const re) {
+    const CC * const re_first = first(re);
+    if (re_first) {
+        FollowMap follows;
+        follow(re, follows);
+        for (const auto & entry : follows) {
+            if (entry.second->intersects(*re_first)) {
+                return nullptr;
             }
         }
-        return true;
-    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
-        for (const RE * re : *re_alt) {
-            if (isNullable(re)) {
-                return true;
-            }
-        }
-    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
-        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
-    } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
-        return isNullable(diff->getLH()) && !isNullable(diff->getRH());
-    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
-        return isNullable(e->getLH()) && isNullable(e->getRH());
-    } 
-    return false;
+    }
+    return const_cast<CC *>(re_first);
 }
 

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

@@ -2 +2 @@
 #define RE_LOCAL_H
 
-#include <UCD/ucd_compiler.hpp>
-#include <map>
-
 namespace re {
 
-class RE;
+class RE; class CC;
 
-class RE_Local {
-public:
-    static CC * first(RE * re);
-    static CC * final(RE * re);
-    static void follow(RE * re, std::map<CC*, CC*> &follow_map);
-        static bool isLocalLanguage(RE * re);
-private:
-        static bool isLocalLanguage_helper(const RE * re, UCD::UnicodeSet & seen);
-        static bool isNullable(const RE * re);
+struct RE_Local {
+    static CC * getFirstUniqueSymbol(RE * re);
 };
 

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

@@ -1 +1 @@
 #ifndef RE_NULLABLE_H
 #define RE_NULLABLE_H
-
-#include <llvm/Support/Compiler.h>
 
 namespace re { class RE; }

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

@@ -19 +19 @@
 #include <re/re_intersect.h>
 #include <re/re_assertion.h>
-#include <re/printer_re.h>
 #include <llvm/Support/ErrorHandling.h>
-#include <llvm/Support/raw_ostream.h>
-#include <llvm/Support/Debug.h>
 #include <map>
+
 
 using namespace llvm;
@@ -29 +27 @@
 namespace re {
 
-RE * reverse_helper(RE * re, std::map<std::string, Name *> & captureMap) {
-    if (CC * cc = dyn_cast<CC>(re)) {
+using CaptureMap = std::map<std::string, re::Name *>;
+
+RE * reverse(RE * re, CaptureMap & captureMap) {
+    if (isa<CC>(re)) {
         return re;
     } else if (Range * rg = dyn_cast<Range>(re)) {
@@ -37 +37 @@
         std::vector<RE*> list;
         for (auto i = seq->rbegin(); i != seq->rend(); ++i) {
-            list.push_back(reverse_helper(*i, captureMap));
+            list.push_back(reverse(*i, captureMap));
         }
         return makeSeq(list.begin(), list.end());
@@ -43 +43 @@
         std::vector<RE*> list;
         for (auto i = alt->begin(); i != alt->end(); ++i) {
-            list.push_back(reverse_helper(*i, captureMap));
+            list.push_back(reverse(*i, captureMap));
         }
         return makeAlt(list.begin(), list.end());
     } else if (Rep * rep = dyn_cast<Rep>(re)) {
-        return makeRep(reverse_helper(rep->getRE(), captureMap), rep->getLB(), rep->getUB());
+        return makeRep(reverse(rep->getRE(), captureMap), rep->getLB(), rep->getUB());
     } else if (Group * g = dyn_cast<Group>(re)) {
-        return makeGroup(g->getMode(), reverse_helper(g->getRE(), captureMap), g->getSense());
+        return makeGroup(g->getMode(), reverse(g->getRE(), captureMap), g->getSense());
     } else if (Diff * diff = dyn_cast<Diff>(re)) {
-        return makeDiff(reverse_helper(diff->getLH(), captureMap), reverse_helper(diff->getRH(), captureMap));
+        return makeDiff(reverse(diff->getLH(), captureMap), reverse(diff->getRH(), captureMap));
     } else if (Intersect * e = dyn_cast<Intersect>(re)) {
-        return makeIntersect(reverse_helper(e->getLH(), captureMap), reverse_helper(e->getRH(), captureMap));
+        return makeIntersect(reverse(e->getLH(), captureMap), reverse(e->getRH(), captureMap));
     } else if (Assertion * a = dyn_cast<Assertion>(re)) {
-        return makeAssertion(reverse_helper(a->getAsserted(), captureMap), Assertion::reverseKind(a->getKind()), a->getSense());
+        return makeAssertion(reverse(a->getAsserted(), captureMap), Assertion::reverseKind(a->getKind()), a->getSense());
     } else if (isa<Start>(re)) {
         return makeEnd();
@@ -67 +67 @@
                 return makeName(n->getNamespace(), n->getName(), Name::Type::UnicodeProperty);
             case Name::Type::ZeroWidth:
-                return makeZeroWidth(n->getName(), reverse_helper(n->getDefinition(), captureMap));
-            case Name::Type::Capture: 
+                return makeZeroWidth(n->getName(), reverse(n->getDefinition(), captureMap));
+            case Name::Type::Capture:
                 {
                     std::string cname = n->getName();
@@ -77 +77 @@
                     else {
                         std::string newName = "\\" + std::to_string(captureMap.size() + 1);
-                        Name * capture = makeCapture(newName, reverse_helper(n->getDefinition(), captureMap));
+                        Name * capture = makeCapture(newName, reverse(n->getDefinition(), captureMap));
                         captureMap.insert(std::make_pair(cname, capture));
                         return capture;
@@ -92 +92 @@
                     else {
                         std::string newName = "\\" + std::to_string(captureMap.size() + 1);
-                        Name * capture = makeCapture(newName, reverse_helper(referent->getDefinition(), captureMap));
+                        Name * capture = makeCapture(newName, reverse(referent->getDefinition(), captureMap));
                         captureMap.insert(std::make_pair(cname, capture));
                         return capture;
@@ -111 +111 @@
 
 RE * reverse(RE * re) {
-    std::map<std::string, Name *> captureMap;
-    return reverse_helper(re, captureMap);
+    CaptureMap captureMap;
+    return reverse(re, captureMap);
 }
+
 }

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

@@ -8 +8 @@
 #define RE_REVERSE_H
 
-//#include <map>                           // for map
-namespace re { class RE; class Name;}
+namespace re { class RE; }
 
 namespace re {
     
-/*
-class Reverser (
-public:
-    Reverser();
-    */
-    RE * reverse(RE * re);
-    /*
-private:
-    using NameMap = std::map<std::pair<std::string, std::string>, re::Name *>;
-    unsigned                    mCaptureGroupCount;
-    NameMap                     mNameMap;
-    Memoizer                    mMemoizer;
-}
-*/
+RE * reverse(RE * re);
+
 }