ivopts improvement

[Tom de Vries]

Hi Zdenek,

I rewrote the patch to remove the use of use_uses_inced_iv.

On 03/14/2011 03:03 PM, Zdenek Dvorak wrote:
> Hi,
> 
>>> (since the use_uses_inced_iv test is meaningless).
>>
>> To me it seems use_uses_inced_iv has meaning:
>> - it models something: it states whether the comparison is using
>>   the iv increment result or the iv phi result.
> 
> but that has nothing to do with the value of the iv.  For instance,
> in the following:
> 
> a = phi (0, a')
> b = phi (1, b')
> c = phi (1, c')
> 
> a' = a + 1;
> tmp = b;
> 
> compare (a'/tmp/c, something)
> 
> b' = tmp + 1;
> c' = c + 1;
> 
> a', tmp and c are completely equivalent, yet your code for some reason claims
> to handle c and the other two differently.

That a' and c have the same value and the code handles them differently
does not necessarily mean that the code is incorrect.  The way I would
formulate it is that the code has implementation limitations, which are
expressed in an awkward way.

> tmp = b;

You're right, the calculation of use_uses_inced_iv assumed that it looks
at either the iv phi or the iv increment, so that was not safe.


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.

What I tried to do previously was to first prove a relation p_1 == i_2 +
ssa_name between i_2 and p_1, and then figure out (in the awkward code)
if I was allowed to assume p_6 == i_7 + ssa_name.

Now, I try to prove that relation between i_7 and p_6 instead, which
makes the code in iv_elimination_compare_lt simpler.

This has as casualty though that the 'int' case (the case that use->iv
is not compatible with sizetype) does not work anymore. That would need
more work.

The code still has the same limitation, meaning it will transform the
first 2 examples, but not the last 2 examples of the series of 4
mentioned earlier.

Changes compared to previous submission:
- changed name of fold_walk_def_plus into fold_diff_to_ssa_name
- added extra intelligence in fold_diff_to_ssa_name to deal with
  (a + x) - (b - x).
- don't calculate real_iv_use_base, calculate instead base_cand_at_use
  to simplify code

Thanks,
-Tom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: iterator.6.6-ml.patch
Type: text/x-patch
Size: 9415 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20110315/89c21d1b/attachment.bin>