Re: [Open64-devel] code review - fix for Bug #778

[Fred C. <fr...@gm...>]

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:fr...@gm...]
> *Sent:* Friday, May 27, 2011 7:42 PM
> *To:* ope...@li...
> *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
> Ope...@li...  <mailto:Ope...@li...>
> https://lists.sourceforge.net/lists/listinfo/open64-devel
>