This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH GCC]Improve how we handle overflow in scev by using overflow information computed for control iv in loop niter, part II
- From: "Bin.Cheng" <amker dot cheng at gmail dot com>
- To: Richard Biener <richard dot guenther at gmail dot com>
- Cc: Bin Cheng <bin dot cheng at arm dot com>, GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Tue, 2 Jun 2015 17:30:13 +0800
- Subject: Re: [PATCH GCC]Improve how we handle overflow in scev by using overflow information computed for control iv in loop niter, part II
- Authentication-results: sourceware.org; auth=none
- References: <000001d097a3$c846a200$58d3e600$ at arm dot com> <CAFiYyc3+1KqERA7w9TUdcKUMLj=RGxQPwsaoUbd2kMnoMwCHqA at mail dot gmail dot com> <CAHFci2-HP6Byzesq+2b--AthhcLDSp8_bKXPxWCQjw6o=j501w at mail dot gmail dot com> <CAFiYyc38N_zdhSYoMGBnBeqFnJSJewSY+v8P2EJAaBnZ_Vo68A at mail dot gmail dot com>
On Tue, Jun 2, 2015 at 4:40 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, Jun 2, 2015 at 4:55 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>> On Mon, Jun 1, 2015 at 6:45 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Tue, May 26, 2015 at 1:04 PM, Bin Cheng <bin.cheng@arm.com> wrote:
>>>> Hi,
>>>> My first part patch improving how we handle overflow in scev is posted at
>>>> https://gcc.gnu.org/ml/gcc-patches/2015-05/msg01795.html . Here comes the
>>>> second part patch.
>>>>
>>>> This patch does below improvements:
>>>> 1) Computes and records control iv for each loop's exit edge. This
>>>> provides a way to compute overflow information in loop niter and use it in
>>>> different customers. It think it's useful, especially with option
>>>> -funsafe-loop-optimizers.
>>>> 2) Improve chrec_convert by adding new interface
>>>> loop_exits_before_overflow. It checks if a converted IV overflows wrto its
>>>> type and loop using overflow information of loop's control iv. This
>>>> basically propagates no-overflow information from control iv to ivs
>>>> converted from control iv. Moreover, we can further improve the logic by
>>>> using possible VRP information in the future.
>>>
>>> But 2) you already posted (and I have approved it but you didn't commit yet?).
>>>
>>> Can you commit that approved patch and only send the parts I didn't approve
>>> yet?
>>>
>>> Thanks,
>>> Richard.
>>>
>>>> With this patch, cases like scev-9.c and scev-10.c in patch can be handled
>>>> now. Cases reported in PR48052 can be vectorized too.
>>>> Opinions?
>>>>
>>>> Thanks,
>>>> bin
>>>>
>>>>
>>>> 2015-05-26 Bin Cheng <bin.cheng@arm.com>
>>>>
>>>> * cfgloop.h (struct control_iv): New.
>>>> (struct loop): New field control_ivs.
>>>> * tree-ssa-loop-niter.c : Include "stor-layout.h".
>>>> (number_of_iterations_lt): Set no_overflow information.
>>>> (number_of_iterations_exit): Init control iv in niter struct.
>>>> (record_control_iv): New.
>>>> (estimate_numbers_of_iterations_loop): Call record_control_iv.
>>>> (loop_exits_before_overflow): New. Interface factored out of
>>>> scev_probably_wraps_p.
>>>> (scev_probably_wraps_p): Factor loop niter related code into
>>>> loop_exits_before_overflow.
>>>> (free_numbers_of_iterations_estimates_loop): Free control ivs.
>>>> * tree-ssa-loop-niter.h (free_loop_control_ivs): New.
>>>>
>>>> gcc/testsuite/ChangeLog
>>>> 2015-05-26 Bin Cheng <bin.cheng@arm.com>
>>>>
>>>> PR tree-optimization/48052
>>>> * gcc.dg/tree-ssa/scev-8.c: New.
>>>> * gcc.dg/tree-ssa/scev-9.c: New.
>>>> * gcc.dg/tree-ssa/scev-10.c: New.
>>>> * gcc.dg/vect/pr48052.c: New.
>>>>
>>
>> Hi Richard,
>> I think you replied the review message of this patch to another
>> thread. Sorry for being mis-leading. S I copied and answered your
>> review comments in this thread thus we can continue here.
>>
>>>> + /* Done proving if this is a no-overflow control IV. */
>>>> + if (operand_equal_p (base, civ->base, 0))
>>>> + return true;
>>>
>>> so all control IVs are no-overflow?
>>
>> This patch only records known no-overflow control ivs in loop
>> structure, so it depends on loop niter analyzer. For now, this patch
>> (and the existing code) sets no-overflow flag only for two cases. One
>> is the step-1 case, the other one is in assert_no_overflow_lt.
>> As a matter of fact, we may want to set no_overflow flag for all cases
>> with -funsafe-loop-optimizations in the future. In that case, we will
>> assume all control IVs are no-overflow.
>>
>>>
>>>> + base <= UPPER_BOUND (type) - step ;;step > 0
>>>> + base >= LOWER_BOUND (type) - step ;;step < 0
>>>> +
>>>> + by using loop's initial condition. */
>>>> + stepped = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step);
>>>> + if (operand_equal_p (stepped, civ->base, 0))
>>>> + {
>>>> + if (tree_int_cst_sign_bit (step))
>>>> + {
>>>> + code = LT_EXPR;
>>>> + extreme = lower_bound_in_type (type, type);
>>>> + }
>>>> + else
>>>> + {
>>>> + code = GT_EXPR;
>>>> + extreme = upper_bound_in_type (type, type);
>>>> + }
>>>> + extreme = fold_build2 (MINUS_EXPR, type, extreme, step);
>>>> + e = fold_build2 (code, boolean_type_node, base, extreme);
>>>
>>> looks like you are actually computing base + step <= UPPER_BOUND (type)
>>> so maybe adjust the comment. But as both step and UPPER_BOUND (type)
>>> are constants why not compute it the way the comment specifies it? Comparison
>>> codes also don't match the comment and we try to prove the condition is false.
>> I tried to prove the condition are satisfied by proving the reverse
>> condition ("base > UPPER_BOUND (type) - step") is false here. In the
>> updated patch, I revised comments to reflect that logic. Is it ok?
>>
>>>
>>> This also reminds me of eventually pushing forward my idea of strengthening
>>> simplify_using_initial_
>>> conditions by using the VRP machinery (I have a small
>>> prototype patch for that).
>> Interesting. If I understand correctly, VRP info is hold for ssa var
>> on a global scope basis? The loop's initial condition may strengthen
>> var's range information, rather than the contrary. Actually I tried
>> to refine vrp info in scope of loop and used the refined vrp
>> information in loop optimizer (In the thread which you replied this
>> review message to). Looking forward to seeing how it's handled in
>> your patch.
>
> Attached (don't remember the state of the patch, but of course some
> caching is missing here).
If I understand correctly, you are trying to compute/refine
control-flow sensitive vrp information by using loop's initial
conditions. I did kind of same thing in the old patch, but yes, your
patch is of course more general. One point is we can extend the idea
to non-loop control flows, for example, if-then-else. I guess it
might be harder to develop a caching structure dealing with non-loop
control flows
>
>>>
>>>> +/* The structure describing a non-overflow control induction variable
>>>> + of loop's exit edge. */
>>>> +struct GTY ((chain_next ("%h.next"))) control_iv {
>>>> + tree base;
>>>> + tree step;
>>>> + struct control_iv *next;
>>>> +};
>>>
>>> The comment suggests these don't exist for multiple edges? Maybe you
>>> can clarify this.
>> As the linked list structure suggests, we can support one no-overflow
>> iv for each loop's exit edge. I revised the comment a little bit.
>>
>>>
>>> Otherwise the patch looks ok.
>>
>> I attached the updated patch, does it look fine?
>
> Yes.
Will apply the patch later.
Thanks,
bin
>
> Thanks,
> Richard.
>
>> Thanks,
>> bin
>>>
>>> Thanks,
>>> Richard.