Hi Fred,
"end" is greater than "const2". "const2" is the stride of memory access.
"end" is the new loop upper-bound, which is: "beginning_memory_address +
const2 * upperbound_of_original_IV".
So "end - const2" will never be below 0.
Sorry that my explanation of "end" in my 1st Email may be a bit confusing.
-Mei
From: Fred Chow [mailto:frdc...@gmail.com]
Sent: Saturday, May 28, 2011 10:12 AM
To: Ye, Mei
Cc: open64-devel@lists.sourceforge.net
Subject: Re: [Open64-devel] code review - fix for Bug #778
Hi Mei,
I buy your point, but then I can apply my argument to (end - const2) in the
loop termination test. If end is close to 0, (end - const2) can become a very
large unsigned number. That will also cause the termination test to evaluate
wrong.
Whenever a wraparound occurs in the code formed by LFTR, the iteration behavior
of the loop will change. No matter how you add constant adjustments here and
there, wraparound can still occur at runtime because we don't know the actual
address value at compilation time.
Fred
On 05/28/2011 08:49 AM, Ye, Mei wrote:
Hi Fred,
Thanks much for your comments. When sym3 is just above 0, Even though
"sym11v3= const1 - const2 + sym3" may produce a negative number, but "sym11v5
= sym11v4 + const2" should bring the value back to positive.
So the underflow won't happen. Yes, the transformation creates an overhead.
But it is needed to preserve correctness.
-Mei
From: Fred Chow [mailto:frdc...@gmail.com]
Sent: Friday, May 27, 2011 7:42 PM
To:
open64-devel@lists.sourceforge.net<mailto:open64-devel@lists.sourceforge.net>
Subject: Re: [Open64-devel] code review - fix for Bug #778
Mei,
The problem you described is the notarious wraparound issue when performing
LFTR (that's why we provide the -OPT:wrap_around_unsafe_op" flag to help
diagnose such problems when optimization changes a program's behavior). But
your claim that your change makes this problem "less likely" to occur is
elusive. Generally speaking, the value of the address
sym3
is not known until run-time. If it is just above 0, it would not have any
problem before your change, but after your change, the "- const2" may create
underflow in sym11, making it becomes a very large value, which then causes the
comparison (sym11 <= end) to give different result.
Your change just shifts the occurrence of the wraparound arbitrarily to
different range of values. Statistically speaking, the probability of
wraparound stays the same. You may claim that for your system/processor
combination, your change justifies because the value of sym3 is more likely to
be close to 0xffffffff than 0x00000000. But this is only for your system, not
in general.
On the other hand, your change introduces a small overhead due to the
additional (- const2), resulting in small performance degradation.
Fred
On 05/23/2011 05:53 PM, Ye, Mei wrote:
My earlier check-in r3502 forces loop end-test comparison to be "unsigned" in
the Linear Function Test Replacement (LFTR) phase. This fixes an overflow
problem when memory address crosses the boundary of 0x80000000 in 32-bit
architectures. The fix exposes another bug in Linear Function Test Replacement,
which is explained below using the following pseudo-codes, where "sym7" is the
original loop index, "sym11" is the memory address that replaces the original
loop index as the induction variable, and "end" is the loop upper bound. If
the value of the memory address is very closed to 0xffffffff, adding a positive
constant can overflow and produces a small positive result for "sym11v5", which
then causes "sym11v5 <= end" to be evaluated as "TRUE", and the loop is
mistakenly executed many more times than it should. This leads to seg faults.
sym7v3 = const1
sym11v3 = sym7v3 + sym3
LABEL:
sym11v4 = phi(sym11v3, sym11v5)
*sym11v4 = ...
sym11v5 = sym11v4 + const2
if (sym11v5 <= end)
goto LABEL
To fix this bug, we transform the above code into the following.
sym7v3 = const1
sym11v3 = const1 - const2 + sym3 // The result of 'const1 - const2' should use
signed type.
LABEL:
sym11v4 = phi(sym11v3, sym11v5)
sym11v5 = sym11v4 + const2
*sym11v5 = ...
if (sym11v5 <= end - const2)
goto LABEL
This transformation uses pre-increment instead of post-increment for the
induction variable update and replaces the use of "sym11v4" with "sym11v5".
My implementation replaces CR operands associated with "sym11v4" without
rehashing since none of these expressions appear outside of the loop. It is
also impractical to rehash these expressions at this point since doing so will
burn compilation time to find each occurrence from all the worklsts. I also
avoid the situations that the transformation will create new expressions having
CSE occurrences outside of the loop. This is to avoid changing CODEREPs
unintentionally.
Although this work still will not make LFTR 100% safe, but it should cover a
vast majority.
------------------------------------------------------------------------------
vRanger cuts backup time in half-while increasing security.
With the market-leading solution for virtual backup and recovery,
you get blazing-fast, flexible, and affordable data protection.
Download your free trial now.
http://p.sf.net/sfu/quest-d2dcopy1
_______________________________________________
Open64-devel mailing list
Open64-devel@lists.sourceforge.net<mailto:Open64-devel@lists.sourceforge.net>
https://lists.sourceforge.net/lists/listinfo/open64-devel
------------------------------------------------------------------------------
Simplify data backup and recovery for your virtual environment with vRanger.
Installation's a snap, and flexible recovery options mean your data is safe,
secure and there when you need it. Data protection magic?
Nope - It's vRanger. Get your free trial download today.
http://p.sf.net/sfu/quest-sfdev2dev
_______________________________________________
Open64-devel mailing list
Open64-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/open64-devel
