Re: ivopts improvement

[Tom de Vries <vries at codesourcery dot com>]

On 03/15/2011 04:10 PM, Zdenek Dvorak wrote:
> Hi,
> 
>> I'll try to explain what my intention with the code is, by looking at a
>> pre-ivopt level example.
>>
>> <bb 2>:
>>   p_5 = p_3(D) + i_4(D);
>>
>> <bb 3>:
>>   # p_1 = PHI <p_5(2), p_6(4)>
>>   # i_2 = PHI <i_4(D)(2), i_7(4)>
>>   *p_1 = 0;
>>   p_6 = p_1 + 1;
>>   i_7 = i_2 + 1;
>>   if (i_7 < n_8(D))
>>     goto <bb 4>;
>>   else
>>     goto <bb 5>;
>>
>> <bb 4>:
>>   goto <bb 3>;
>>
>> <bb 5>:
>>   return;
>>
>> In this example, I try to analyze whether it is safe to replace
>>   i_7 < n_8
>> by
>>   p_6 < p_3 + n_8.
> 
> hmmm... is it actually safe?  What if n_8 is negative, and p_3 + n_8
> overflows?

I note that situation here in the comments in iv_elimination_compare_lt:
...
    This transformation is not valid if i and n are signed, because
     base + n might underflow.
...

and test for i == unsigned here in iv_elimination_compare_lt:
...
  /* Use should be an unsigned integral.  */
  if (!INTEGRAL_TYPE_P (use_type) || !TYPE_UNSIGNED (use_type))
    return false;
...

If i is unsigned but n is signed the code looks like this and the
transformation is done using the unsigned pretmp.3_13 rather than signed
n_8:
...
<bb 2>:
  p_5 = p_3(D) + i_4(D);
  pretmp.3_13 = (long unsigned int) n_8(D);

<bb 3>:
  # p_1 = PHI <p_5(2), p_7(4)>
  # i_2 = PHI <i_4(D)(2), i_6(4)>
  *p_1 = 0;
  i_6 = i_2 + 1;
  p_7 = p_1 + 1;
  if (i_6 < pretmp.3_13)
    goto <bb 4>;
  else
    goto <bb 5>;

<bb 4>:
  goto <bb 3>;

<bb 5>:
  return;
...


If i is unsigned and n is signed, and we compare (long signed int)i < n
then the use->iv is of type long int, and the TYPE_UNSIGNED (use_type)
test prevents the transformation.
...
  long int i.0;

<bb 2>:
  p_5 = p_3(D) + i_4(D);

<bb 3>:
  # p_1 = PHI <p_5(2), p_7(4)>
  # i_2 = PHI <i_4(D)(2), i_6(4)>
  *p_1 = 0;
  i_6 = i_2 + 1;
  p_7 = p_1 + 1;
  i.0_8 = (long int) i_6;
  if (i.0_8 < n_9(D))
    goto <bb 4>;
  else
    goto <bb 5>;

<bb 4>:
  goto <bb 3>;

<bb 5>:
  return;
...

Thanks,
- Tom