Re: [PATCH PR68529]Fix not recognized scev by computing no-overflow info for loop with NE_EXPR exit condition

[Richard Biener <richard dot guenther at gmail dot com>]

On Sat, Nov 28, 2015 at 6:50 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Fri, Nov 27, 2015 at 8:51 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Fri, Nov 27, 2015 at 12:44 PM, Bin Cheng <bin.cheng@arm.com> wrote:
>>> Hi,
>>> This patch is to fix PR68529.  In my previous scev/niter overflow patches, I
>>> only computed no-overflow information for control iv in simple loops with
>>> LT_EXPR as exit condition code.  This bug is about loop with NE_EXPR as exit
>>> condition code.  Given below example:
>>>
>>> #include <stdio.h>
>>> #include <stdlib.h>
>>>
>>> int main(){
>>>     char c[10000]={};
>>>     unsigned int nchar=9999;
>>>
>>>     while(nchar--!=0){
>>>        c[nchar]='A';
>>>       }
>>>
>>>     printf("%s\n",c);
>>>     return 0;
>>> }
>>> nchar used as an index to array 'c' doesn't overflow during loop iterations.
>>> Thus &c[nchar] acts as a scev.  GCC now fails to do that.  With this patch,
>>> this issue is fixed.
>>>
>>> Furthermore, the computation of no-overflow information could be improved by
>>> using TREE_OVERFLOW_UNDEFINED semantic of signed type for C/C++.  I didn't
>>> do that because:
>>> 1) I doubt how useful it could be because I have already changed scev to use
>>> the semantic whenever possible.  It doesn't need loop niter analysis' help.
>>> 2) To do that, I need to expose chrec_convert_aggressive information out of
>>> scev in function simple_iv, because that function could corrupt
>>> TREE_OVERFLOW_UNDEFINED semantic assumption.  This isn't appropriate for
>>> Stage3.
>>>
>>> Bootstrap and test on x86_64 and x86.  I don't expect any issue on aarch64
>>> either.  Is it OK?
>>
>> +  if (integer_onep (e)
>> +      && (integer_onep (s)
>> +         || (TREE_CODE (c) == INTEGER_CST
>> +             && TREE_CODE (s) == INTEGER_CST
>> +             && wi::mod_trunc (c, s, TYPE_SIGN (type)) == 0)))
>>
>> the only thing I'm looking at here is the modulo sign.  Considering
>> we're looking at the sign bit of the step to normalize 'c' and 's' what
>> happens for
>>
>>   for (unsigned int i = 0; i != 1000; --i)
>>
>> ?  I suppose we get s == 1 and c == -1000U and you'll say the control
>> IV doesn't wrap.  Similar for i -= 2 where even when we use a signed
>> modulo (singed)-1000U % 2 is still 0.
>>
>> So I think you need to remember whether we consider the step
>> to be negative and compare iv->base and final as well.
> I think the patch does the monotonic check wrto sign of step with below code:
>
> +  if (tree_int_cst_sign_bit (iv->step))
> +    e = fold_build2 (GE_EXPR, boolean_type_node, iv->base, final);
> +  else
> +    e = fold_build2 (LE_EXPR, boolean_type_node, iv->base, final);
> +  e = simplify_using_initial_conditions (loop, e);
> +  if (integer_onep (e)
>
> It acts as expected with your example.
>
>>
>> Bonus points for a wrong-code testcase with the above.
>>
>> I'd also like to see a testcase exercising step != 1.
> I added two new tests each for "step != 1" and the previous case.  I
> also tuned original pr68529-3.c a little.  Actually for the case in
> the original patch as below:
> +void bar(char *s);
> +int foo(unsigned short l)
> +{
> +  char c[10000] = {};
> +  unsigned short nchar = 9999;
> +
> +  if (nchar < l)
> +    return -1;
> +
> +  while(nchar-- != l)
> +    {
> +      c[nchar] = 'A';
> +    }
> +
> +  bar (c);
> +  return 0;
> +}
>
> The offset IS an affine.  GCC can't detect that because condition
> "nchar (==9999) < l" is split into two conditions: "l_8 > 9999" and
> "l_8 != 9999".  For now simplify_using_initial_conditions can't merge
> range information from two different conditions.  Maybe jump threading
> can merge the two condition/jumps, or VRP improvement discussed before
> can handle that.
>
> Here is the updated patch.  Is it OK?

Ok.

Thanks,
Richard.

> Thanks,
> bin