]> granicus.if.org Git - re2c/commit
Tag interference analysis: compare actual values, not formal RHS.
authorUlya Trofimovich <skvadrik@gmail.com>
Fri, 14 Apr 2017 10:45:23 +0000 (11:45 +0100)
committerUlya Trofimovich <skvadrik@gmail.com>
Fri, 14 Apr 2017 11:03:07 +0000 (12:03 +0100)
commit4909060f3416dd3bbcf0b16661b7bc0b651ff3bd
treee1170bc9241c33fa37cc266a0cddc02652f66a3e
parent1807b3275f6b7d90febf8effe73fd6e82bc32ae6
Tag interference analysis: compare actual values, not formal RHS.

Commands in the same basic block may have equal right hand sides,
e.g. 'x = y; z = y;'. Clearly in this case 'x' and 'z' do not interfere:
both versions are equal to 'y'. This optimization allows to deduplicate
cases like '("a" @x @y @z "b")*', where multiple tags have the same
values.

However, it is insufficient to find all commands in the current block
with RHS equal to current RHS. An example when this algorithm fails:
'x = y; w = z; z = y;', here 'x' and 'z' are assigned to the same RHS
'y', but if we merge them into one variable, 'w' will get the wrong
value.

The fix is as follows: first, ignore subsequent commands and consider
only commands that precede current command: if subsequent command that
sets LHS to the same value precedes any use of it, liveness propagation
through basic block would mark this LHS as dead and not interfering
anyway; otherwise (if use precedes setting to the same value), then it
indeed interferes with current LHS. This fixes the above example
'x = y; w = z; z = y;': when analysing 'x = y;' command we find that
'z' is alive (as before), but ignore subsequent 'z = y;' command (due
to the fix).

Second, when analysing preceding commands, calculate actual value for
each LHS (based on pessimistic assumption that on entry of basic block
all used versions are different). Formal RHS of some preceding command
may coincide with current formal RHS, but their values might differ:
'x = y; y = w; z = y;', here 'x = y;' and 'z = y;' have identical formal
RHS, but the value may be different. On the other hand, formal RHS
might be different, while their actual values are equal, as in
'x = y; w = y; z = w;'.
re2c/src/dfa/cfg/interfere.cc
re2c/test/posix_captures/basic/01.i--flex-syntax.c
re2c/test/posix_captures/basic/02.i--flex-syntax.c
re2c/test/posix_captures/glennfowler/43.i--flex-syntax.c