Andreas Koch
koch****@esa*****
2009年 6月 26日 (金) 10:08:59 JST
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
There appears to be an error in data flow analysis (or I am misinterpreting
the output, which might also be the case) in COINS 1.4.4.3:
Consider the following sample program, which I am using to play with PRE:
int foo(int a, int b, int c) {
int r, q;
if (c)
q = a * b; // <-- This will be Block 2, marked by _lab3
else
c++;
r = a * b;
return (q+r+c);
}
After performing local CSE in doPRE(), initiateDataFlowInformation() is
called, which gives the following summary:
...
Data flow summary of foo
ExpId and IR correspondence
_xId2 1 <var c>
_xId3 2 (cmpNe <var c><const 0>)
_xId4 3 <var q> LHS
_xId5 4 <var a>
_xId6 5 <var b>
_xId7 6 (mult <var a><var b>)
_xId8 7 <var q>
_xId9 8 <var c> LHS
_xId10 9 (add <var c><const 1>)
_xId11 10 <var r> LHS
_xId12 11 <var r>
_xId13 12 (add <var q><var r>)
_xId14 13 (add (add <var q><var r>)<var c>)
...
BBlock 2 _lab3
def assign 17
kill
reach
defined _xId3
used _xId4(q) _xId5(a) <-- this appears to be wrong
exposed _xId4(q) _xId5(a) <-- this appears to be wrong
eGen _xId7
eKill _xId4(q) _xId8(q) _xId13 _xId14
availin _xId3
availOut _xId3 _xId7
liveIn _xId2(c) _xId4(q) _xId5(a) <-- this appears to be wrong
liveOut _xId2(c) _xId3 _xId4(q) _xId5(a) <-- similar
defIn _xId3
defOut _xId3
defNodes
...
Block 2 computes q = a * b, thus I would expect
used = { _xId5(a), _xId6(b) }
exposed = { _xId5(a), _xId6(b) }
liveIn = { _xId2(c), _xId5(a), _xId6(b) }
liveOut = { _xId2(c), _xId5(a), _xId6(b), _xId8(q) }
...
This possible error causes problems later in computeAntloc(), which computes
to {} for B2, instead of { _xId7 }, thus PRE does not eliminate the partially
redundant r = a * b in the example.
Might this be be an off-by-one error (_xId4,_xId5 instead of the correct
_xId5, _xId6)? It appears to occur even earlier when the sets are computed:
...
DBGF findExposed B2
DBGF getSetRefReprList B2
DBGF lSetRefReprList SetRefReprList SetRefRepr assign 17 int
DBGF IR assign 17 SetRefReprHirImpl: lUseNodeList = [var 20 int a, var
21 int b]
lUse [b 4, a 3] exposed [b 4, a 3] toExpVector [b 4, a 3] sym b 4 sym
a 3 lDef q 2
DBGF sortExpIdCollection [_xId4 3, _xId5 4] findExposed B2 _xId4(q) _xId5(a)
Indices appear to be mixed up here: lUse and exposed correctly contain {a,b},
here referred to using the numbers 3 and 4. However, they are incorrectly
associated with ExpId _xId4 and _xId5 (which are 'q' and 'a')
...
=====[Used(B)]=====
...
BlockNO =2
1 2 3 4 5 6 7 8 9 10 11 12 13
- ---------------------------------------
0 0 1 1 0 0 0 0 0 0 0 0 0
DBGF sortExpIdCollection [_xId4 3, _xId5 4]_xId4(q) _xId5(a)
...
Used(B2) has the bits of IDs 3 and 4 set (which are the same numbers
internally used in findExposed for 'a' and 'b'), but according to the ExpID-IR
correspondence table they mean 'q' and 'a', instead of 'a' and 'b'.
In some cases, there appears to be a discrepancy in COINS how bit indices are
handled. BitVectorImpl can accept Index 0, however,
BitVectorIterator.nextIndex() returns 0 to indicate that no more 1-bits
remain. Maybe something went wrong along those lines?
Since I've just started working with this part of COINS, I'm not certain that
I interpret the data correctly. Maybe one of the experts can chime in here?
Many thanks,
Andreas Koch
- --
Prof. Dr. Andreas Koch koch****@esa*****
Technische Universität Darmstadt, FB20 Phone : x49-6151-16-4378
Embedded Systems and Applications Group (ESA) FAX : x49-6151-16-5472
Hochschulstr. 10, D-64289 Darmstadt, Germany * PGP key available *
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEARECAAYFAkpEH6oACgkQk5ta2EV7Doy9EwCfcjEu3s2Ts1/Rml/PeA34nBN4
0QEAn0+FppQTqinjloVCowR5ZrFfZGmx
=RFl3
-----END PGP SIGNATURE-----