Re: [PATCH GCC]Improve how we handle overflow in scev by using overflow information computed for control iv in loop niter, part II
On Tue, Jun 2, 2015 at 4:40 PM, Richard Biener
richard.guent...@gmail.com wrote:
On Tue, Jun 2, 2015 at 4:55 AM, Bin.Cheng amker.ch...@gmail.com wrote:
On Mon, Jun 1, 2015 at 6:45 PM, Richard Biener
richard.guent...@gmail.com wrote:
On Tue, May 26, 2015 at 1:04 PM, Bin Cheng bin.ch...@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.ch...@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.ch...@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
Re: [PATCH GCC]Improve how we handle overflow in scev by using overflow information computed for control iv in loop niter, part II
On Tue, Jun 2, 2015 at 4:55 AM, Bin.Cheng amker.ch...@gmail.com wrote:
On Mon, Jun 1, 2015 at 6:45 PM, Richard Biener
richard.guent...@gmail.com wrote:
On Tue, May 26, 2015 at 1:04 PM, Bin Cheng bin.ch...@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.ch...@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.ch...@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
Re: [PATCH GCC]Improve how we handle overflow in scev by using overflow information computed for control iv in loop niter, part II
On Tue, Jun 2, 2015 at 11:30 AM, Bin.Cheng amker.ch...@gmail.com wrote:
On Tue, Jun 2, 2015 at 4:40 PM, Richard Biener
richard.guent...@gmail.com wrote:
On Tue, Jun 2, 2015 at 4:55 AM, Bin.Cheng amker.ch...@gmail.com wrote:
On Mon, Jun 1, 2015 at 6:45 PM, Richard Biener
richard.guent...@gmail.com wrote:
On Tue, May 26, 2015 at 1:04 PM, Bin Cheng bin.ch...@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.ch...@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.ch...@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
Re: [PATCH GCC]Improve how we handle overflow in scev by using overflow information computed for control iv in loop niter, part II
On Tue, May 26, 2015 at 1:04 PM, Bin Cheng bin.ch...@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.ch...@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.ch...@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.
Re: [PATCH GCC]Improve how we handle overflow in scev by using overflow information computed for control iv in loop niter, part II
On Mon, Jun 1, 2015 at 6:45 PM, Richard Biener
richard.guent...@gmail.com wrote:
On Tue, May 26, 2015 at 1:04 PM, Bin Cheng bin.ch...@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.ch...@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.ch...@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
