From b334de679f30f9b0320b07266033623418059845 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Fri, 30 Sep 2016 11:22:53 +0100 Subject: [PATCH] Attribute tag liveness to edges, not states (to refine analysis). State granularity is too crude: there might be two different paths to the same state, with some tag alive on one path but not on the other. If liveness is attributed to states, then tag liveness on one path implies tag liveness in the join state, which affects the other path. But if liveness is attributed to edges, then liveness of one path won't affect liveness of the other. --- re2c/src/ir/dfa/tag_deduplication.cc | 44 +++++++++++---------- re2c/test/tags/dedup4.i--tags.c | 7 ++-- re2c/test/tags/fallback1.i--tags.c | 2 +- re2c/test/tags/fallback1.i--tags.re | 2 +- re2c/test/tags/fallback2.i--tags.c | 59 ++++++++++++++++++++++++++++ re2c/test/tags/fallback2.i--tags.re | 19 +++++++++ 6 files changed, 107 insertions(+), 26 deletions(-) create mode 100644 re2c/test/tags/fallback2.i--tags.c create mode 100644 re2c/test/tags/fallback2.i--tags.re diff --git a/re2c/src/ir/dfa/tag_deduplication.cc b/re2c/src/ir/dfa/tag_deduplication.cc index 3f83a784..ee9c5404 100644 --- a/re2c/src/ir/dfa/tag_deduplication.cc +++ b/re2c/src/ir/dfa/tag_deduplication.cc @@ -7,24 +7,24 @@ namespace re2c struct revarc_t { + size_t edge; size_t dest; size_t tags; revarc_t *next; }; -static void backprop(revarc_t **rdfa, - Tagpool &tagpool, - size_t *live, - size_t tags, - size_t state) +static void backprop(revarc_t **rdfa, bool *been, size_t state, + size_t *live, size_t tags, Tagpool &tagpool) { - const size_t l = live[state]; - live[state] = tagpool.orl(l, tags); - if (l == live[state]) return; + if (been[state]) return; + been[state] = true; for (const revarc_t *a = rdfa[state]; a; a = a->next) { - backprop(rdfa, tagpool, live, - tagpool.andlinv(tags, a->tags), a->dest); + live[a->edge] = tagpool.orl(live[a->edge], tags); + const size_t l = tagpool.andlinv(tags, a->tags); + if (l != ZERO_TAGS) { + backprop(rdfa, been, a->dest, live, l, tagpool); + } } } @@ -34,12 +34,12 @@ static void forwprop(const dfa_t &dfa, bool *been, size_t state, if (been[state]) return; been[state] = true; - live[state] = dfa.tagpool.orl(live[state], need); - const dfa_state_t *s = dfa.states[state]; + size_t *l = &live[state * dfa.nchars]; for (size_t c = 0; c < dfa.nchars; ++c) { const size_t dest = s->arcs[c]; if (dest != dfa_t::NIL && dfa.states[dest]->fallthru) { + l[c] = dfa.tagpool.orl(l[c], need); forwprop(dfa, been, dest, live, need); } } @@ -57,6 +57,7 @@ static void forwprop(const dfa_t &dfa, bool *been, size_t state, static void calc_live(const dfa_t &dfa, size_t *live) { const size_t nstates = dfa.states.size(); + bool *been = new bool[nstates]; // backward-propagate rule tags revarc_t **rdfa = new revarc_t*[nstates](); @@ -67,6 +68,7 @@ static void calc_live(const dfa_t &dfa, size_t *live) for (size_t c = 0; c < dfa.nchars; ++c) { const size_t j = s->arcs[c]; if (j != dfa_t::NIL) { + a->edge = i * dfa.nchars + c; a->dest = i; a->tags = s->tags[c]; a->next = rdfa[j]; @@ -79,14 +81,14 @@ static void calc_live(const dfa_t &dfa, size_t *live) if (s->rule != Rule::NONE) { const size_t need = dfa.tagpool.andlinv( dfa.rules[s->rule].tags, s->rule_tags); - backprop(rdfa, dfa.tagpool, live, need, i); + std::fill(been, been + nstates, false); + backprop(rdfa, been, i, live, need, dfa.tagpool); } } delete[] rdfa; delete[] rarcs; // forward-propagate fallback tags - bool *been = new bool[nstates]; for (size_t i = 0; i < nstates; ++i) { dfa_state_t *s = dfa.states[i]; if (s->fallback) { @@ -104,11 +106,11 @@ static void mask_dead(dfa_t &dfa, const size_t *live) const size_t nstates = dfa.states.size(); for (size_t i = 0; i < nstates; ++i) { dfa_state_t *s = dfa.states[i]; + const size_t *l = &live[i * dfa.nchars]; for (size_t c = 0; c < dfa.nchars; ++c) { const size_t j = s->arcs[c]; if (j != dfa_t::NIL) { - s->tags[c] = dfa.tagpool.andl(s->tags[c], - live[j]); + s->tags[c] = dfa.tagpool.andl(s->tags[c], l[c]); } } if (s->rule != Rule::NONE) { @@ -144,11 +146,11 @@ static void incompatibility_table(const dfa_t &dfa, const size_t ntags = dfa.tags.size(); for (size_t i = 0; i < nstates; ++i) { const dfa_state_t *s = dfa.states[i]; + const size_t *l = &livetags[i * dfa.nchars]; for (size_t c = 0; c < dfa.nchars; ++c) { const size_t j = s->arcs[c]; if (j != dfa_t::NIL) { - incompatible(incompattbl, dfa.tagpool, - livetags[j], s->tags[c]); + incompatible(incompattbl, dfa.tagpool, l[c], s->tags[c]); } } if (s->rule != Rule::NONE) { @@ -241,8 +243,10 @@ size_t deduplicate_tags(dfa_t &dfa) return 0; } - const size_t nstates = dfa.states.size(); - size_t *live = new size_t[nstates](); + const size_t + nstates = dfa.states.size(), + nedges = nstates * dfa.nchars; + size_t *live = new size_t[nedges](); calc_live(dfa, live); mask_dead(dfa, live); diff --git a/re2c/test/tags/dedup4.i--tags.c b/re2c/test/tags/dedup4.i--tags.c index 8c5aa46b..10be1595 100644 --- a/re2c/test/tags/dedup4.i--tags.c +++ b/re2c/test/tags/dedup4.i--tags.c @@ -132,7 +132,6 @@ yy23: unsigned int yyaccept = 0; long yytag0p; long yytag1; - long yytag1p; YYCTXMARKER = YYCURSOR; if ((YYLIMIT - YYCURSOR) < 2) YYFILL(2); yych = *YYCURSOR; @@ -148,10 +147,10 @@ yy28: yych = *(YYMARKER = ++YYCURSOR); switch (yych) { case 'b': - yytag0p = yytag1p = (YYCURSOR - YYCTXMARKER); + yytag0p = (YYCURSOR - YYCTXMARKER); goto yy30; case 'c': - yytag1 = yytag1p = (YYCURSOR - YYCTXMARKER); + yytag0p = yytag1 = (YYCURSOR - YYCTXMARKER); goto yy32; default: yytag0p = (YYCURSOR - YYCTXMARKER); @@ -199,7 +198,7 @@ yy34: } yy35: YYCURSOR = YYCTXMARKER + yytag1; - { (YYCTXMARKER + yytag1p) } + { (YYCTXMARKER + yytag0p) } } diff --git a/re2c/test/tags/fallback1.i--tags.c b/re2c/test/tags/fallback1.i--tags.c index 42bddc1c..88092f13 100644 --- a/re2c/test/tags/fallback1.i--tags.c +++ b/re2c/test/tags/fallback1.i--tags.c @@ -1,7 +1,7 @@ /* Generated by re2c */ // This test demonstrates that fallback tags should be forward-propagated // from final states, and that merging all possible fallback tags and -// bacward-propagating them from default transitions is too crude, +// backward-propagating them from default transitions is too crude, // inhibits tag interference where there is none and gets in the way // of tag deduplication. diff --git a/re2c/test/tags/fallback1.i--tags.re b/re2c/test/tags/fallback1.i--tags.re index 6498b864..2f465d27 100644 --- a/re2c/test/tags/fallback1.i--tags.re +++ b/re2c/test/tags/fallback1.i--tags.re @@ -1,6 +1,6 @@ // This test demonstrates that fallback tags should be forward-propagated // from final states, and that merging all possible fallback tags and -// bacward-propagating them from default transitions is too crude, +// backward-propagating them from default transitions is too crude, // inhibits tag interference where there is none and gets in the way // of tag deduplication. diff --git a/re2c/test/tags/fallback2.i--tags.c b/re2c/test/tags/fallback2.i--tags.c new file mode 100644 index 00000000..7255c72a --- /dev/null +++ b/re2c/test/tags/fallback2.i--tags.c @@ -0,0 +1,59 @@ +/* Generated by re2c */ +// This test shows that tag liveness should be attributed to DFA edges, +// not to DFA states. State granularity is too crude: there might be +// two different paths to the same state, with some tag alive on one +// path but not on the other. If liveness is attributed to states, then +// tag liveness on one path implies tag liveness in the join state, +// which affects the other path. But if liveness is attributed to +// edges, then liveness of one path won't affect liveness of the other. + +// In this example tag 'p' is loop-invariant: it should be moved out +// of loop and set once in the very end. However, if liveness is +// attributed to states rather than edges, the accepting state (dispatch +// on 'yyaccept') will force liveness on the looping path and prevent +// tag from hoisting out of loop. + + +{ + YYCTYPE yych; + unsigned int yyaccept = 0; + long yytag0p; + YYCTXMARKER = YYCURSOR; + if (YYLIMIT <= YYCURSOR) YYFILL(1); + yych = *(YYMARKER = YYCURSOR); + switch (yych) { + case 'a': goto yy3; + default: goto yy2; + } +yy2: + { (YYCTXMARKER + yytag0p) } +yy3: + ++YYCURSOR; + if (YYLIMIT <= YYCURSOR) YYFILL(1); + yych = *YYCURSOR; + switch (yych) { + case 'b': goto yy5; + default: goto yy4; + } +yy4: + YYCURSOR = YYMARKER; + if (yyaccept == 0) { + goto yy2; + } else { + yytag0p = (YYCURSOR - YYCTXMARKER); + goto yy2; + } +yy5: + yyaccept = 1; + YYMARKER = ++YYCURSOR; + if (YYLIMIT <= YYCURSOR) YYFILL(1); + yych = *YYCURSOR; + switch (yych) { + case 'a': goto yy3; + default: + yytag0p = (YYCURSOR - YYCTXMARKER); + goto yy2; + } +} + +re2c: warning: line 17: rule matches empty string [-Wmatch-empty-string] diff --git a/re2c/test/tags/fallback2.i--tags.re b/re2c/test/tags/fallback2.i--tags.re new file mode 100644 index 00000000..2a244c1b --- /dev/null +++ b/re2c/test/tags/fallback2.i--tags.re @@ -0,0 +1,19 @@ +// This test shows that tag liveness should be attributed to DFA edges, +// not to DFA states. State granularity is too crude: there might be +// two different paths to the same state, with some tag alive on one +// path but not on the other. If liveness is attributed to states, then +// tag liveness on one path implies tag liveness in the join state, +// which affects the other path. But if liveness is attributed to +// edges, then liveness of one path won't affect liveness of the other. + +// In this example tag 'p' is loop-invariant: it should be moved out +// of loop and set once in the very end. However, if liveness is +// attributed to states rather than edges, the accepting state (dispatch +// on 'yyaccept') will force liveness on the looping path and prevent +// tag from hoisting out of loop. + +/*!re2c + + ("ab" @p)* { @p } + +*/ -- 2.40.0