From d07bc5ce04beb25e1a92600bb36141263b5714e7 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Fri, 2 Dec 2016 23:33:51 +0000 Subject: [PATCH] Don't loose liveness of tags that occur on both sides of 'copy' commands. When processing chain of 'copy' commands like 'x = y; y = z;' one should first mark all left hand sides ('x' and 'y') as dead, then mark all right hand sides as alive ('y' and 'z'). This way 'y' will end up alive, as it should be. Found by slyfox's fuzzer. :) --- re2c/src/ir/dfa/cfg/liveanal.cc | 7 + re2c/test/tags/twopass.i--tags.c | 214 ++++++++++++++++++++++++++++++ re2c/test/tags/twopass.i--tags.re | 9 ++ 3 files changed, 230 insertions(+) create mode 100644 re2c/test/tags/twopass.i--tags.c create mode 100644 re2c/test/tags/twopass.i--tags.re diff --git a/re2c/src/ir/dfa/cfg/liveanal.cc b/re2c/src/ir/dfa/cfg/liveanal.cc index b64149ac..8cba078f 100644 --- a/re2c/src/ir/dfa/cfg/liveanal.cc +++ b/re2c/src/ir/dfa/cfg/liveanal.cc @@ -58,6 +58,8 @@ void cfg_t::liveness_analysis(const cfg_t &cfg, bool *live) for (const tagsave_t *p = cmd->save; p; p = p->next) { buf2[p->ver] = false; } + + // need two passes: same version may occur as both LHS and RHS for (const tagcopy_t *p = cmd->copy; p; p = p->next) { if (l[p->lhs]) { buf2[p->lhs] = false; @@ -107,10 +109,15 @@ void cfg_t::liveness_analysis(const cfg_t &cfg, bool *live) for (const tagsave_t *p = b->cmd->save; p; p = p->next) { buf1[p->ver] = false; } + + // need two passes: same version may occur as both LHS and RHS for (const tagcopy_t *p = b->cmd->copy; p; p = p->next) { buf1[p->lhs] = false; + } + for (const tagcopy_t *p = b->cmd->copy; p; p = p->next) { buf1[p->rhs] = true; } + for (cfg_ix_t *j = b->succb; j < b->succe; ++j) { bool *liv = &live[*j * nver]; for (size_t v = 0; v < nver; ++v) { diff --git a/re2c/test/tags/twopass.i--tags.c b/re2c/test/tags/twopass.i--tags.c new file mode 100644 index 00000000..0a459408 --- /dev/null +++ b/re2c/test/tags/twopass.i--tags.c @@ -0,0 +1,214 @@ +/* Generated by re2c */ +// need two passes in liveness analyses for chains of copy commands: +// same version may occur as both LHS and RHS, e.g. 'x = y; y = z;' + + +{ + YYCTYPE yych; + unsigned int yyaccept = 0; + if ((YYLIMIT - YYCURSOR) < 6) YYFILL(6); + yych = *(YYMARKER = YYCURSOR); + switch (yych) { + case 'a': + yyt2 = YYCURSOR; + goto yy4; + case 'b': + yyt1 = yyt2 = yyt3 = YYCURSOR; + goto yy6; + default: + yyt3 = YYCURSOR; + goto yy3; + } +yy2: + s = yyt4; + r = yyt2; + {} +yy3: + yyaccept = 1; + yych = *(YYMARKER = ++YYCURSOR); + switch (yych) { + case 'a': + yyt4 = YYCURSOR; + goto yy10; + case 'b': + yyt2 = yyt4 = YYCURSOR; + goto yy11; + default: + yyt2 = YYCURSOR; + goto yy8; + } +yy4: + yych = *++YYCURSOR; + switch (yych) { + case 'b': goto yy13; + default: goto yy5; + } +yy5: + YYCURSOR = YYMARKER; + switch (yyaccept) { + case 0: + yyt2 = yyt4 = NULL; + goto yy2; + case 1: + yyt2 = yyt3; + yyt4 = YYCURSOR; + goto yy2; + case 2: + yyt3 = yyt1; + yyt1 = yyt2; + goto yy7; + case 3: + yyt4 = YYCURSOR; + goto yy2; + case 4: + yyt2 = yyt3; + goto yy2; + default: goto yy7; + } +yy6: + yyaccept = 2; + yych = *(YYMARKER = ++YYCURSOR); + switch (yych) { + case 'a': + yyt4 = YYCURSOR; + goto yy10; + case 'b': + yyt2 = yyt4 = YYCURSOR; + goto yy11; + default: + yyt2 = YYCURSOR; + goto yy8; + } +yy7: + y = yyt1; + q = yyt3; + p = yyt2; + {} +yy8: + yyaccept = 3; + YYMARKER = ++YYCURSOR; + if (YYLIMIT <= YYCURSOR) YYFILL(1); + yych = *YYCURSOR; + switch (yych) { + case 'a': + yyt3 = yyt2; + yyt4 = YYCURSOR; + goto yy10; + case 'b': + yyt3 = yyt2; + yyt2 = yyt4 = YYCURSOR; + goto yy11; + default: + yyt2 = YYCURSOR; + goto yy8; + } +yy10: + ++YYCURSOR; + if (YYLIMIT <= YYCURSOR) YYFILL(1); + yych = *YYCURSOR; + switch (yych) { + case 'b': goto yy14; + default: goto yy5; + } +yy11: + ++YYCURSOR; + if (YYLIMIT <= YYCURSOR) YYFILL(1); + yych = *YYCURSOR; + switch (yych) { + case 'a': goto yy14; + case 'b': + yyt3 = yyt2; + yyt2 = yyt4 = YYCURSOR; + goto yy11; + default: + yyt2 = YYCURSOR; + goto yy8; + } +yy13: + yych = *++YYCURSOR; + switch (yych) { + case 'a': goto yy17; + case 'b': + yyt3 = NULL; + yyt1 = YYCURSOR; + goto yy18; + default: + yyt3 = NULL; + yyt1 = YYCURSOR; + goto yy15; + } +yy14: + yyaccept = 4; + YYMARKER = ++YYCURSOR; + if (YYLIMIT <= YYCURSOR) YYFILL(1); + yych = *YYCURSOR; + switch (yych) { + case 'a': goto yy10; + case 'b': + yyt2 = YYCURSOR; + goto yy11; + default: + yyt2 = YYCURSOR; + goto yy8; + } +yy15: + ++YYCURSOR; + if (YYLIMIT <= YYCURSOR) YYFILL(1); + yych = *YYCURSOR; + switch (yych) { + case 'a': goto yy5; + case 'b': goto yy18; + default: goto yy15; + } +yy17: + yych = *++YYCURSOR; + switch (yych) { + case 'a': + yyt2 = NULL; + goto yy20; + case 'b': + yyt2 = NULL; + yyt1 = yyt3 = YYCURSOR; + goto yy18; + default: + yyt2 = NULL; + yyt1 = yyt3 = YYCURSOR; + goto yy15; + } +yy18: + yyaccept = 5; + YYMARKER = ++YYCURSOR; + if (YYLIMIT <= YYCURSOR) YYFILL(1); + yych = *YYCURSOR; + switch (yych) { + case 'a': goto yy7; + case 'b': goto yy18; + default: goto yy15; + } +yy20: + yych = *++YYCURSOR; + switch (yych) { + case 'b': goto yy21; + default: goto yy5; + } +yy21: + ++YYCURSOR; + switch ((yych = *YYCURSOR)) { + case 'a': goto yy5; + case 'b': + yyt3 = NULL; + yyt1 = YYCURSOR; + goto yy18; + default: + yyt3 = NULL; + yyt1 = YYCURSOR; + goto yy15; + } +} + +re2c: warning: line 7: rule matches empty string [-Wmatch-empty-string] +re2c: warning: line 6: tag 'y' is nondeterministic [-Wnondeterministic-tags] +re2c: warning: line 6: tag 'q' is nondeterministic [-Wnondeterministic-tags] +re2c: warning: line 6: tag 'p' is nondeterministic [-Wnondeterministic-tags] +re2c: warning: line 7: tag 's' is nondeterministic [-Wnondeterministic-tags] +re2c: warning: line 7: tag 'r' is nondeterministic [-Wnondeterministic-tags] diff --git a/re2c/test/tags/twopass.i--tags.re b/re2c/test/tags/twopass.i--tags.re new file mode 100644 index 00000000..69005366 --- /dev/null +++ b/re2c/test/tags/twopass.i--tags.re @@ -0,0 +1,9 @@ +// need two passes in liveness analyses for chains of copy commands: +// same version may occur as both LHS and RHS, e.g. 'x = y; y = z;' + +/*!re2c + +(@p | [^b] "ba") ("ab" | @q) @y [^a]* "b" {} +(@r [^a] @s ("ab" | "ba")*)* {} + +*/ -- 2.40.0