Fix PR43567 (-ftree-loop-linear)

Mon Jul 12 07:51:00 GMT 2010

On Mon, Jul 12, 2010 at 2:52 AM, Sebastian Pop <sebpop@gmail.com> wrote:
> On Sat, Jul 10, 2010 at 17:29, Tom de Vries <tjvries@xs4all.nl> wrote:
>> The testcase pr43567-1.c (see patch below) does not return 0 as it should:
>> ...
>> $ gcc -O2 -ftree-loop-linear -fno-tree-ch pr43567-1.c ; ./a.out ; echo $?
>> 1
>> $
>> ...
>>
>> This is probably a duplicate of bug 20612. When the patch from bug 20612 in
>> lambda_loopnest_to_gcc_loopnest is reverted, the compiler ICEs in verify_ssa,
>> with a similar message as in bug 20612:
>> ...
>> pr43567-1.c: In function ‘test’:
>> pr43567-1.c:5:6: error: definition in block 3 does not dominate use in block 4
>> for SSA_NAME: lnivtmp.6_20 in statement:
>> if (lletmp.8_17 >= lnivtmp.6_20)
>> pr43567-1.c:5:6: internal compiler error: verify_ssa failed
>> Please submit a full bug report,
>> with preprocessed source if appropriate.
>> See <http://gcc.gnu.org/bugs.html> for instructions.
>> ...
>>
>> When we stop after lambda_loopnest_to_gcc_loopnest, and dump the function test,
>> it looks like this (without the patch):
>> ...
>> <bb 2>:
>>  goto <bb 6>;
>> <bb 3>:
>>  D.2742_6 = (long unsigned int) lnivtmp.3_5;
>>  D.2743_7 = D.2742_6 * 4;
>>  D.2744_9 = a_8(D) + D.2743_7;
>>  *D.2744_9 = 0;
>>  j_10 = lnivtmp.3_5 + 1;
>>  lnivtmp.6_20 = lnivtmp.6_18 + 1;
>> <bb 4>:
>>  # j_2 = PHI <0(7), j_10(3)>
>>  # lnivtmp.6_18 = PHI <0(7), lnivtmp.6_20(3)>
>>  lletmp.8_17 = n_4(D) + -1;
>>  if (lletmp.8_17 >= lnivtmp.6_20)
>>    goto <bb 3>;
>>  else
>>    goto <bb 5>;
>> <bb 5>:
>>  i_11 = lnivtmp.6_18 + 1;
>>  lnivtmp.3_19 = lnivtmp.3_5 + 1;
>> <bb 6>:
>>  # i_1 = PHI <0(2), i_11(5)>
>>  # lnivtmp.3_5 = PHI <0(2), lnivtmp.3_19(5)>
>>  lletmp.5_16 = n_4(D) + -1;
>>  if (lletmp.5_16 >= lnivtmp.3_19)
>>    goto <bb 7>;
>>  else
>>    goto <bb 8>;
>> <bb 7>:
>>  goto <bb 4>;
>> <bb 8>:
>>  return;
>> ...
>>
>> The problem is the following: in bb4, in the comparison
>> 'lletmp.8_17 >= lnivtmp.6_20', we use lnivtmp.6_20. This ssavar has its def
>> (the increment 'lnivtmp.6_20 = lnivtmp.6_18 + 1') in bb3, which does not
>> dominate the use in bb4, so this is indeed illegal ssa.
>> What should have been used instead in the comparison, is the local value of the
>> iv: lnivtmp.6_18, defined by ' lnivtmp.6_18 = PHI <0(7), lnivtmp.6_20(3)>'.
>>
>> The patch from bug 20612 in lambda_loopnest_to_gcc_loopnest prevents the
>> ssa_verify failure, but does not generate correct code. Representation at the
>> same point (with that patch):
>> ...
>> <bb 2>:
>>  goto <bb 6>;
>> <bb 3>:
>>  D.2742_6 = (long unsigned int) lnivtmp.3_5;
>>  D.2743_7 = D.2742_6 * 4;
>>  D.2744_9 = a_8(D) + D.2743_7;
>>  *D.2744_9 = 0;
>>  j_10 = lnivtmp.3_5 + 1;
>>  lnivtmp.6_21 = lnivtmp.6_20 + 1;
>> <bb 4>:
>>  # j_2 = PHI <0(7), j_10(3)>
>>  # lnivtmp.6_20 = PHI <0(7), lnivtmp.6_21(3)>
>>  lletmp.8_18 = n_4(D) + -1;
>>  lnivtmp.6_22 = lnivtmp.6_20 + 1;
>>  if (lletmp.8_18 >= lnivtmp.6_22)
>>    goto <bb 3>;
>>  else
>>    goto <bb 5>;
>> <bb 5>:
>>  i_11 = lnivtmp.6_20 + 1;
>>  lnivtmp.3_19 = lnivtmp.3_5 + 1;
>> <bb 6>:
>>  # i_1 = PHI <0(2), i_11(5)>
>>  # lnivtmp.3_5 = PHI <0(2), lnivtmp.3_19(5)>
>>  lletmp.5_16 = n_4(D) + -1;
>>  lnivtmp.3_17 = lnivtmp.3_5 + 1;
>>  if (lletmp.5_16 >= lnivtmp.3_17)
>>    goto <bb 7>;
>>  else
>>    goto <bb 8>;
>> <bb 7>:
>>  goto <bb 4>;
>> <bb 8>:
>>  return;
>> ...
>>
>> The comparison 'lletmp.8_18 >= lnivtmp.6_22' uses lnivtmp.6_22, defined by the
>> extra increment 'lnivtmp.6_22 = lnivtmp.6_20 + 1'. This extra increment however
>> uses lnivtmp.6_20, defined by 'lnivtmp.6_20 = PHI <0(7), lnivtmp.6_21(3)>',
>> which uses lnivtmp.6_21 defined by the original increment
>> 'lnivtmp.6_21 = lnivtmp.6_20 + 1'. So, the ivvar is incremented twice before
>> testing it in the comparison.
>>
>> The code that adds the extra insert is not correct currently, but I can't say
>> whether the original patch was already wrong, or that it was correct but got
>> corrupted in a later checkin (there have been a few). Either way, I tried
>> to fix the problem without using an extra increment.
>>
>> Why doesn't this problem exist for -ftree-ch? Take a look at the representation
>> at the same point (again without the patch):
>> ...
>> <bb 2>:
>>  if (n_4(D) > 0)
>>    goto <bb 3>;
>>  else
>>    goto <bb 9>;
>> <bb 3>:
>>  goto <bb 8>;
>> <bb 4>:
>> <bb 5>:
>>  # j_22 = PHI <j_10(4), 0(8)>
>>  # lnivtmp.10_12 = PHI <lnivtmp.10_2(4), 0(8)>
>>  lletmp.12_1 = n_4(D) + -1;
>>  D.2742_6 = (long unsigned int) lnivtmp.7_20;
>>  D.2743_7 = D.2742_6 * 4;
>>  D.2744_9 = a_8(D) + D.2743_7;
>>  *D.2744_9 = 0;
>>  j_10 = lnivtmp.7_20 + 1;
>>  lnivtmp.10_2 = lnivtmp.10_12 + 1;
>>  if (lletmp.12_1 >= lnivtmp.10_2)
>>    goto <bb 4>;
>>  else
>>    goto <bb 6>;
>> <bb 6>:
>>  lletmp.9_21 = n_4(D) + -1;
>>  i_11 = lnivtmp.10_12 + 1;
>>  lnivtmp.7_13 = lnivtmp.7_20 + 1;
>>  if (lletmp.9_21 >= lnivtmp.7_13)
>>    goto <bb 7>;
>>  else
>>    goto <bb 9>;
>> <bb 7>:
>> <bb 8>:
>>  # i_18 = PHI <i_11(7), 0(3)>
>>  # lnivtmp.7_20 = PHI <lnivtmp.7_13(7), 0(3)>
>>  goto <bb 5>;
>> <bb 9>:
>>  return;
>> ...
>>
>> We see that the increment 'lnivtmp.10_2 = lnivtmp.10_12 + 1' is positioned in
>> front of the comparison 'lletmp.12_1 >= lnivtmp.10_2', and the comparison
>> correctly uses the local value of the iv, which is the result of the increment.
>>
>> The patch reverts the original fix, and fixes the issue by testing for the case
>> that the increment does not dominate the comparison, and then using the
>> appropriate local ivvar.
>>
>> The patch was bootstrapped and regression tested (gcc, objc, gfortran, g++,
>> libgomp, libstdc++, libjava, libmudflap, libffi) on x86_64-unknown-linux-gnu
>> with and without patch, with similar results (apart from execution failure of
>> pr43567-1.c, which fails without patch).
>>
>> Ok for trunk? I don't have copyright assignment (started that process though)
>> or write access.
>>
>>        PR tree-optimization/43567
>>        * lambda-code.c (lambda_loopnest_to_gcc_loopnest): Check for the
>>        case that the increment does not dominate the comparison, and use
>>        the appropriate ivvar.
>
> This looks good to me, but I cannot approve this change.
> Richi, could you review this patch please?

The patch doesn't look obviously correct to me.  It seems tailored
to the symptom (the IV increment doesn't dominate the use, so
use some other?!).  The dominance check also looks odd.

But maybe both are because of the wording.  I have no idea about
loop-linear, so I won't review the patch.

Richard.

> Thanks,
> Sebastian
>