This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH PR82776]Exploit more undefined pointer overflow behavior in loop niter analysis
On Wed, Nov 8, 2017 at 1:25 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Wed, Nov 8, 2017 at 11:55 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Tue, Nov 7, 2017 at 1:44 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>> On Tue, Nov 7, 2017 at 12:23 PM, Richard Biener
>>> <richard.guenther@gmail.com> wrote:
>>>> On Tue, Nov 7, 2017 at 1:17 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>>> On Tue, Nov 7, 2017 at 10:44 AM, Richard Biener
>>>>> <richard.guenther@gmail.com> wrote:
>>>>>> On Fri, Nov 3, 2017 at 1:35 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>>>>> Hi,
>>>>>>> This is a simple patch exploiting more undefined pointer overflow behavior in
>>>>>>> loop niter analysis. Originally, it only supports POINTER_PLUS_EXPR if the
>>>>>>> offset part is IV. This patch also handles the case if pointer is IV. With
>>>>>>> this patch, the while(true) loop in test can be removed by cddce pass now.
>>>>>>>
>>>>>>> Bootstrap and test on x86_64 and AArch64. This patch introduces two failures:
>>>>>>> FAIL: g++.dg/pr79095-1.C -std=gnu++98 (test for excess errors)
>>>>>>> FAIL: g++.dg/pr79095-2.C -std=gnu++11 (test for excess errors)
>>>>>>> I believe this exposes inaccurate value range information issue. For below code:
>>>>>>> /* { dg-do compile } */
>>>>>>> /* { dg-options "-Wall -O3" } */
>>>>>>>
>>>>>>> typedef long unsigned int size_t;
>>>>>>>
>>>>>>> inline void
>>>>>>> fill (int *p, size_t n, int)
>>>>>>> {
>>>>>>> while (n--)
>>>>>>> *p++ = 0;
>>>>>>> }
>>>>>>>
>>>>>>> struct B
>>>>>>> {
>>>>>>> int* p0, *p1, *p2;
>>>>>>>
>>>>>>> size_t size () const {
>>>>>>> return size_t (p1 - p0);
>>>>>>> }
>>>>>>>
>>>>>>> void resize (size_t n) {
>>>>>>> if (n > size())
>>>>>>> append (n - size());
>>>>>>> }
>>>>>>>
>>>>>>> void append (size_t n)
>>>>>>> {
>>>>>>> if (size_t (p2 - p1) >= n) {
>>>>>>> fill (p1, n, 0);
>>>>>>> }
>>>>>>> }
>>>>>>> };
>>>>>>>
>>>>>>> void foo (B &b)
>>>>>>> {
>>>>>>> if (b.size () != 0)
>>>>>>> b.resize (b.size () - 1);
>>>>>>> }
>>>>>>>
>>>>>>> GCC gives below warning with this patch:
>>>>>>> pr79095-1.C: In function ‘void foo(B&)’:
>>>>>>> pr79095-1.C:10:7: warning: iteration 4611686018427387903 invokes undefined behavior [-Waggressive-loop-optimizations]
>>>>>>> *p++ = 0;
>>>>>>> ~^~
>>>>>>> pr79095-1.C:9:11: note: within this loop
>>>>>>> while (n--)
>>>>>>> ^~
>>>>>>>
>>>>>>> Problem is VRP should understand that it's never the case with condition:
>>>>>>> (size_t (p2 - p1) >= n)
>>>>>>> in function B::append.
>>>>>>>
>>>>>>> So, any comment?
>>>>
>>>> Does it warn when not inlining fill()? Isn't the issue that one test
>>> With this patch, yes.
>>>> tests p2 - p1 and
>>>> the loop goes from p1 to p1 + (p1 - p0)?
>>> don't follow here. so the code is:
>>>
>>>>>>> inline void
>>>>>>> fill (int *p, size_t n, int)
>>>>>>> {
>>>>>>> while (n--)
>>>>>>> *p++ = 0;
>>>>>>> }
>>>
>>>>>>> void append (size_t n)
>>>>>>> {
>>>>>>> if (size_t (p2 - p1) >= n) {
>>>>>>> fill (p1, n, 0);
>>>>>>> }
>>>
>>> fill is only called if size_t (p2 - p1) >= n, so while loop in fill
>>> can only zero-out memory range [p1, p2)?
>>
>> what happens if p1 is before p0? The compare
>> p2 - p1 >= p1 - p0 doesn't tell us much when
>> iterating from p1 to p1 + ((p1 - p0) - 1), no?
> I double thought on this. Looks like the warning message is not
> spurious when p2 is before p1, in which case we have no information
> about argument "n" to the call of fill.
> Otherwise, if p1 is before p2, we can always assume n has value that
> *p++ never overflow. In this case it has nothing to do with p0,
> right?
>>
>>>
>>>>
>>>> What kind of optimization do we apply to the loop in fill?
>>> Depends on some conditions, the loop could be distributed into memset.
>>> Anyway, the warning message is issued as long as niter analysis
>>> believes it takes advantage of undefined pointer overflow behavior.
>>
>> Hmm, yes.
>>
>> Not sure if the warning will be too noisy in the end. I'd say go ahead
> I guess it could be too noisy. And as above, the warning looks like correct?
Yes, it does.
Richard.
> Thanks,
> bin
>> and add a dg-warning for the testcase for the moment.
>>
>> Thanks,
>> Richard.
>>
>>> Thanks,
>>> bin
>>>>
>>>>>> I'm looking hard but I can't see you changed anything in
>>>>>> infer_loop_bounds_from_pointer_arith
>>>>>> besides adding a expr_invariant_in_loop_p (loop, rhs2) check.
>>>>> yes, that's enough for this fix?
>>>>>
>>>>> - ptr = gimple_assign_rhs1 (stmt);
>>>>> - if (!expr_invariant_in_loop_p (loop, ptr))
>>>>> + rhs2 = gimple_assign_rhs2 (stmt);
>>>>> + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (rhs2)))
>>>>> return;
>>>>>
>>>>> - var = gimple_assign_rhs2 (stmt);
>>>>> - if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var)))
>>>>> + rhs1 = gimple_assign_rhs1 (stmt);
>>>>> + if (!expr_invariant_in_loop_p (loop, rhs1)
>>>>> + && !expr_invariant_in_loop_p (loop, rhs2))
>>>>> return;
>>>>>
>>>>> Before this change, the function skips if ptr in "res = ptr +p offset"
>>>>> is non-invariant. This change only skips if both ptr and offset are
>>>>> non-invariant, thus the PR is handled.
>>>>
>>>> Ah, of course. Thanks for the explanation.
>>>>
>>>>> Thanks,
>>>>> bin
>>>>>
>>>>>
>>>>>>
>>>>>> What am I missing?
>>>>>>
>>>>>> Richard.
>>>>>>
>>>>>>> Thanks,
>>>>>>> bin
>>>>>>> 2017-11-02 Bin Cheng <bin.cheng@arm.com>
>>>>>>>
>>>>>>> PR tree-optimization/82776
>>>>>>> * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Handle
>>>>>>> POINTER_PLUS_EXPR in which the pointer is an IV.
>>>>>>> (infer_loop_bounds_from_signedness): Refine comment.
>>>>>>>
>>>>>>> gcc/testsuite
>>>>>>> 2017-11-02 Bin Cheng <bin.cheng@arm.com>
>>>>>>>
>>>>>>> PR tree-optimization/82776
>>>>>>> * g++.dg/pr82776.C: New test.
>>>>>>> * gcc.dg/tree-ssa/split-path-6.c: Refine test.