* [PATCH 2/3]Improve induction variable elimination
@ 2014-07-17 9:09 Bin Cheng
2014-07-25 13:01 ` Richard Biener
0 siblings, 1 reply; 8+ messages in thread
From: Bin Cheng @ 2014-07-17 9:09 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1417 bytes --]
Hi,
As quoted from the function difference_cannot_overflow_p,
/* TODO: deeper inspection may be necessary to prove the equality. */
switch (code)
{
case PLUS_EXPR:
return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
case POINTER_PLUS_EXPR:
return expr_equal_p (e2, offset);
default:
return false;
}
The overflow check can be improved by using deeper inspection to prove the
equality. This patch deals with that by making below two improvements:
a) Handles constant cases.
b) Uses affine expansion as deeper inspection to check the equality.
As a result, functions strip_wrap_conserving_type_conversions and
expr_equal_p can be removed now. A test case is also added to illustrate iv
elimination opportunity captured by this patch.
Thanks,
bin
2014-07-17 Bin Cheng <bin.cheng@arm.com>
* tree-ssa-loop-ivopts.c (ivopts_data): New field name_expansion.
(tree_ssa_iv_optimize_init): Initialize name_expansion.
(tree_ssa_iv_optimize_finalize): Free name_expansion.
(strip_wrap_conserving_type_conversions, expr_equal_p): Delete.
(difference_cannot_overflow_p): New parameter. Handle constant
cases. Use affine expansion for equality check.
(iv_elimination_compare_lt): Pass new argument.
gcc/testsuite/ChangeLog
2014-07-17 Bin Cheng <bin.cheng@arm.com>
* gcc.dg/tree-ssa/ivopts-lt-2.c: New test.
[-- Attachment #2: iv_elimination-improve-b-20140716.txt --]
[-- Type: text/plain, Size: 6877 bytes --]
Index: gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c (revision 0)
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivopts" } */
+
+void
+f1 (int *p, unsigned int i)
+{
+ p += i;
+ do
+ {
+ *p = 0;
+ p += 1;
+ i++;
+ }
+ while (i < 100);
+}
+
+/* { dg-final { scan-tree-dump-times "PHI" 1 "ivopts" } } */
+/* { dg-final { scan-tree-dump-times "PHI <p_" 1 "ivopts"} } */
+/* { dg-final { scan-tree-dump-times "p_\[0-9\]* <" 1 "ivopts" } } */
+/* { dg-final { cleanup-tree-dump "ivopts" } } */
Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c (revision 212387)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -323,6 +323,9 @@ struct ivopts_data
/* A bitmap of important candidates. */
bitmap important_candidates;
+ /* Cache used by tree_to_aff_combination_expand. */
+ struct pointer_map_t *name_expansion;
+
/* The maximum invariant id. */
unsigned max_inv_id;
@@ -877,6 +880,7 @@ tree_ssa_iv_optimize_init (struct ivopts_data *dat
data->iv_candidates.create (20);
data->inv_expr_tab = new hash_table<iv_inv_expr_hasher> (10);
data->inv_expr_id = 0;
+ data->name_expansion = NULL;
decl_rtl_to_reset.create (20);
}
@@ -4449,76 +4453,40 @@ iv_elimination_compare (struct ivopts_data *data,
return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
}
-static tree
-strip_wrap_conserving_type_conversions (tree exp)
-{
- while (tree_ssa_useless_type_conversion (exp)
- && (nowrap_type_p (TREE_TYPE (exp))
- == nowrap_type_p (TREE_TYPE (TREE_OPERAND (exp, 0)))))
- exp = TREE_OPERAND (exp, 0);
- return exp;
-}
+/* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
+ we only check either the case BASE and OFFSET are integer constants, or the
+ situation that BASE = SOMETHING + OFFSET, where the calculation is performed
+ in non-wrapping type. For the latter case, we use affine expansion for
+ further equality check.
-/* Walk the SSA form and check whether E == WHAT. Fairly simplistic, we
- check for an exact match. */
+ TODO: More generally, we could test for the situation that
+ BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
+ This would require knowing the sign of OFFSET. */
static bool
-expr_equal_p (tree e, tree what)
+difference_cannot_overflow_p (struct ivopts_data *data, tree base, tree offset)
{
- gimple stmt;
enum tree_code code;
+ tree e1, e2;
+ aff_tree aff_e1, aff_e2, aff_offset;
- e = strip_wrap_conserving_type_conversions (e);
- what = strip_wrap_conserving_type_conversions (what);
-
- code = TREE_CODE (what);
- if (TREE_TYPE (e) != TREE_TYPE (what))
- return false;
-
- if (operand_equal_p (e, what, 0))
+ /* No overflow if offset is zero. */
+ if (offset == integer_zero_node)
return true;
- if (TREE_CODE (e) != SSA_NAME)
- return false;
-
- stmt = SSA_NAME_DEF_STMT (e);
- if (gimple_code (stmt) != GIMPLE_ASSIGN
- || gimple_assign_rhs_code (stmt) != code)
- return false;
-
- switch (get_gimple_rhs_class (code))
+ /* Overflow can be checked easily for constant values. */
+ if (TREE_CODE (base) == INTEGER_CST && TREE_CODE (offset) == INTEGER_CST)
{
- case GIMPLE_BINARY_RHS:
- if (!expr_equal_p (gimple_assign_rhs2 (stmt), TREE_OPERAND (what, 1)))
- return false;
- /* Fallthru. */
+ bool overflow = false;
+ tree type = TREE_TYPE (base);
+ signop sign = TYPE_SIGN (type);
- case GIMPLE_UNARY_RHS:
- case GIMPLE_SINGLE_RHS:
- return expr_equal_p (gimple_assign_rhs1 (stmt), TREE_OPERAND (what, 0));
- default:
- return false;
+ wide_int arg2 = wide_int::from (offset, TYPE_PRECISION (type),
+ TYPE_SIGN (TREE_TYPE (offset)));
+ (void) wi::sub (base, arg2, sign, &overflow);
+ return overflow;
}
-}
-/* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
- we only detect the situation that BASE = SOMETHING + OFFSET, where the
- calculation is performed in non-wrapping type.
-
- TODO: More generally, we could test for the situation that
- BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
- This would require knowing the sign of OFFSET.
-
- Also, we only look for the first addition in the computation of BASE.
- More complex analysis would be better, but introducing it just for
- this optimization seems like an overkill. */
-
-static bool
-difference_cannot_overflow_p (tree base, tree offset)
-{
- enum tree_code code;
- tree e1, e2;
-
if (!nowrap_type_p (TREE_TYPE (base)))
return false;
@@ -4547,13 +4515,27 @@ static bool
e2 = TREE_OPERAND (base, 1);
}
- /* TODO: deeper inspection may be necessary to prove the equality. */
+ /* Use affine expansion as deeper inspection to prove the equality. */
+ tree_to_aff_combination_expand (e2, TREE_TYPE (e2),
+ &aff_e2, &data->name_expansion);
+ tree_to_aff_combination_expand (offset, TREE_TYPE (offset),
+ &aff_offset, &data->name_expansion);
+ aff_combination_scale (&aff_offset, -1);
switch (code)
{
case PLUS_EXPR:
- return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
+ aff_combination_add (&aff_e2, &aff_offset);
+ if (aff_combination_zero_p (&aff_e2))
+ return true;
+
+ tree_to_aff_combination_expand (e1, TREE_TYPE (e1),
+ &aff_e1, &data->name_expansion);
+ aff_combination_add (&aff_e1, &aff_offset);
+ return aff_combination_zero_p (&aff_e1);
+
case POINTER_PLUS_EXPR:
- return expr_equal_p (e2, offset);
+ aff_combination_add (&aff_e2, &aff_offset);
+ return aff_combination_zero_p (&aff_e2);
default:
return false;
@@ -4677,7 +4659,7 @@ iv_elimination_compare_lt (struct ivopts_data *dat
offset = fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),
cand->iv->step,
fold_convert (TREE_TYPE (cand->iv->step), a));
- if (!difference_cannot_overflow_p (cand->iv->base, offset))
+ if (!difference_cannot_overflow_p (data, cand->iv->base, offset))
return false;
/* Determine the new comparison operator. */
@@ -6805,6 +6787,7 @@ tree_ssa_iv_optimize_finalize (struct ivopts_data
data->iv_candidates.release ();
delete data->inv_expr_tab;
data->inv_expr_tab = NULL;
+ free_affine_expand_cache (&data->name_expansion);
}
/* Returns true if the loop body BODY includes any function calls. */
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/3]Improve induction variable elimination
2014-07-17 9:09 [PATCH 2/3]Improve induction variable elimination Bin Cheng
@ 2014-07-25 13:01 ` Richard Biener
2014-07-25 14:42 ` Bin.Cheng
` (2 more replies)
0 siblings, 3 replies; 8+ messages in thread
From: Richard Biener @ 2014-07-25 13:01 UTC (permalink / raw)
To: Bin Cheng; +Cc: GCC Patches
On Thu, Jul 17, 2014 at 11:08 AM, Bin Cheng <bin.cheng@arm.com> wrote:
> Hi,
> As quoted from the function difference_cannot_overflow_p,
>
> /* TODO: deeper inspection may be necessary to prove the equality. */
> switch (code)
> {
> case PLUS_EXPR:
> return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
> case POINTER_PLUS_EXPR:
> return expr_equal_p (e2, offset);
>
> default:
> return false;
> }
>
> The overflow check can be improved by using deeper inspection to prove the
> equality. This patch deals with that by making below two improvements:
> a) Handles constant cases.
> b) Uses affine expansion as deeper inspection to check the equality.
>
> As a result, functions strip_wrap_conserving_type_conversions and
> expr_equal_p can be removed now. A test case is also added to illustrate iv
> elimination opportunity captured by this patch.
>
> Thanks,
> bin
You add special casing for constants but I don't see any testcases for that.
Specifically
+ /* No overflow if offset is zero. */
+ if (offset == integer_zero_node)
return true;
is a bogus check (use integer_zerop). Apart from the special-casing of
constants the patch looks good to me.
Richard.
> 2014-07-17 Bin Cheng <bin.cheng@arm.com>
>
> * tree-ssa-loop-ivopts.c (ivopts_data): New field name_expansion.
> (tree_ssa_iv_optimize_init): Initialize name_expansion.
> (tree_ssa_iv_optimize_finalize): Free name_expansion.
> (strip_wrap_conserving_type_conversions, expr_equal_p): Delete.
> (difference_cannot_overflow_p): New parameter. Handle constant
> cases. Use affine expansion for equality check.
> (iv_elimination_compare_lt): Pass new argument.
>
> gcc/testsuite/ChangeLog
> 2014-07-17 Bin Cheng <bin.cheng@arm.com>
>
> * gcc.dg/tree-ssa/ivopts-lt-2.c: New test.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/3]Improve induction variable elimination
2014-07-25 13:01 ` Richard Biener
@ 2014-07-25 14:42 ` Bin.Cheng
2014-08-06 2:32 ` Bin.Cheng
2014-08-14 7:37 ` Bin.Cheng
2 siblings, 0 replies; 8+ messages in thread
From: Bin.Cheng @ 2014-07-25 14:42 UTC (permalink / raw)
To: Richard Biener; +Cc: Bin Cheng, GCC Patches
On Fri, Jul 25, 2014 at 1:35 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Jul 17, 2014 at 11:08 AM, Bin Cheng <bin.cheng@arm.com> wrote:
>> Hi,
>> As quoted from the function difference_cannot_overflow_p,
>>
>> /* TODO: deeper inspection may be necessary to prove the equality. */
>> switch (code)
>> {
>> case PLUS_EXPR:
>> return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
>> case POINTER_PLUS_EXPR:
>> return expr_equal_p (e2, offset);
>>
>> default:
>> return false;
>> }
>>
>> The overflow check can be improved by using deeper inspection to prove the
>> equality. This patch deals with that by making below two improvements:
>> a) Handles constant cases.
>> b) Uses affine expansion as deeper inspection to check the equality.
>>
>> As a result, functions strip_wrap_conserving_type_conversions and
>> expr_equal_p can be removed now. A test case is also added to illustrate iv
>> elimination opportunity captured by this patch.
>>
>> Thanks,
>> bin
>
> You add special casing for constants but I don't see any testcases for that.
> Specifically
>
> + /* No overflow if offset is zero. */
> + if (offset == integer_zero_node)
> return true;
>
> is a bogus check (use integer_zerop). Apart from the special-casing of
Will be changed.
> constants the patch looks good to me.
>
Ah, Now I can see that handling of constants (here the zero offset
case) is to make the 3rd patch to work. I should include this part of
code in the 3rd patch. Also I will try to reduce testcase for other
non-zero constant scenarios
Thanks,
bin
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/3]Improve induction variable elimination
2014-07-25 13:01 ` Richard Biener
2014-07-25 14:42 ` Bin.Cheng
@ 2014-08-06 2:32 ` Bin.Cheng
2014-08-06 9:55 ` Bin.Cheng
2014-08-14 7:37 ` Bin.Cheng
2 siblings, 1 reply; 8+ messages in thread
From: Bin.Cheng @ 2014-08-06 2:32 UTC (permalink / raw)
To: Richard Biener, Zdenek Dvorak; +Cc: GCC Patches
On Fri, Jul 25, 2014 at 8:35 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Jul 17, 2014 at 11:08 AM, Bin Cheng <bin.cheng@arm.com> wrote:
>> Hi,
>> As quoted from the function difference_cannot_overflow_p,
>>
>> /* TODO: deeper inspection may be necessary to prove the equality. */
>> switch (code)
>> {
>> case PLUS_EXPR:
>> return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
>> case POINTER_PLUS_EXPR:
>> return expr_equal_p (e2, offset);
>>
>> default:
>> return false;
>> }
>>
>> The overflow check can be improved by using deeper inspection to prove the
>> equality. This patch deals with that by making below two improvements:
>> a) Handles constant cases.
>> b) Uses affine expansion as deeper inspection to check the equality.
>>
>> As a result, functions strip_wrap_conserving_type_conversions and
>> expr_equal_p can be removed now. A test case is also added to illustrate iv
>> elimination opportunity captured by this patch.
>>
>> Thanks,
>> bin
>
> You add special casing for constants but I don't see any testcases for that.
> Specifically
>
> + /* No overflow if offset is zero. */
> + if (offset == integer_zero_node)
> return true;
>
> is a bogus check (use integer_zerop). Apart from the special-casing of
> constants the patch looks good to me.
Hi Richard,
I modified the patch according to your comments by removing the
constant case. Re-bootstrap and test on x86_64 and x86. Is this
version OK?
Thanks,
bin
2014-08-06 Bin Cheng <bin.cheng@arm.com>
* tree-ssa-loop-ivopts.c (ivopts_data): New field name_expansion.
(tree_ssa_iv_optimize_init): Initialize name_expansion.
(tree_ssa_iv_optimize_finalize): Free name_expansion.
(strip_wrap_conserving_type_conversions, expr_equal_p): Delete.
(difference_cannot_overflow_p): New parameter. Use affine
expansion for equality check.
(iv_elimination_compare_lt): Pass new argument.
gcc/testsuite/ChangeLog
2014-08-06 Bin Cheng <bin.cheng@arm.com>
* gcc.dg/tree-ssa/ivopts-lt-2.c: New test.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/3]Improve induction variable elimination
2014-08-06 2:32 ` Bin.Cheng
@ 2014-08-06 9:55 ` Bin.Cheng
0 siblings, 0 replies; 8+ messages in thread
From: Bin.Cheng @ 2014-08-06 9:55 UTC (permalink / raw)
To: Richard Biener, Zdenek Dvorak; +Cc: GCC Patches
[-- Attachment #1: Type: text/plain, Size: 2261 bytes --]
Forgot the patch~
On Wed, Aug 6, 2014 at 10:32 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Fri, Jul 25, 2014 at 8:35 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Thu, Jul 17, 2014 at 11:08 AM, Bin Cheng <bin.cheng@arm.com> wrote:
>>> Hi,
>>> As quoted from the function difference_cannot_overflow_p,
>>>
>>> /* TODO: deeper inspection may be necessary to prove the equality. */
>>> switch (code)
>>> {
>>> case PLUS_EXPR:
>>> return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
>>> case POINTER_PLUS_EXPR:
>>> return expr_equal_p (e2, offset);
>>>
>>> default:
>>> return false;
>>> }
>>>
>>> The overflow check can be improved by using deeper inspection to prove the
>>> equality. This patch deals with that by making below two improvements:
>>> a) Handles constant cases.
>>> b) Uses affine expansion as deeper inspection to check the equality.
>>>
>>> As a result, functions strip_wrap_conserving_type_conversions and
>>> expr_equal_p can be removed now. A test case is also added to illustrate iv
>>> elimination opportunity captured by this patch.
>>>
>>> Thanks,
>>> bin
>>
>> You add special casing for constants but I don't see any testcases for that.
>> Specifically
>>
>> + /* No overflow if offset is zero. */
>> + if (offset == integer_zero_node)
>> return true;
>>
>> is a bogus check (use integer_zerop). Apart from the special-casing of
>> constants the patch looks good to me.
>
> Hi Richard,
> I modified the patch according to your comments by removing the
> constant case. Re-bootstrap and test on x86_64 and x86. Is this
> version OK?
>
> Thanks,
> bin
>
> 2014-08-06 Bin Cheng <bin.cheng@arm.com>
>
> * tree-ssa-loop-ivopts.c (ivopts_data): New field name_expansion.
> (tree_ssa_iv_optimize_init): Initialize name_expansion.
> (tree_ssa_iv_optimize_finalize): Free name_expansion.
> (strip_wrap_conserving_type_conversions, expr_equal_p): Delete.
> (difference_cannot_overflow_p): New parameter. Use affine
> expansion for equality check.
> (iv_elimination_compare_lt): Pass new argument.
>
> gcc/testsuite/ChangeLog
> 2014-08-06 Bin Cheng <bin.cheng@arm.com>
>
> * gcc.dg/tree-ssa/ivopts-lt-2.c: New test.
[-- Attachment #2: iv_elimination-improve-b-20140805.txt --]
[-- Type: text/plain, Size: 5673 bytes --]
Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c (revision 213529)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -323,6 +323,9 @@ struct ivopts_data
/* A bitmap of important candidates. */
bitmap important_candidates;
+ /* Cache used by tree_to_aff_combination_expand. */
+ struct pointer_map_t *name_expansion;
+
/* The maximum invariant id. */
unsigned max_inv_id;
@@ -876,6 +879,7 @@ tree_ssa_iv_optimize_init (struct ivopts_data *dat
data->iv_candidates.create (20);
data->inv_expr_tab = new hash_table<iv_inv_expr_hasher> (10);
data->inv_expr_id = 0;
+ data->name_expansion = NULL;
decl_rtl_to_reset.create (20);
}
@@ -4448,75 +4452,20 @@ iv_elimination_compare (struct ivopts_data *data,
return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
}
-static tree
-strip_wrap_conserving_type_conversions (tree exp)
-{
- while (tree_ssa_useless_type_conversion (exp)
- && (nowrap_type_p (TREE_TYPE (exp))
- == nowrap_type_p (TREE_TYPE (TREE_OPERAND (exp, 0)))))
- exp = TREE_OPERAND (exp, 0);
- return exp;
-}
-
-/* Walk the SSA form and check whether E == WHAT. Fairly simplistic, we
- check for an exact match. */
-
-static bool
-expr_equal_p (tree e, tree what)
-{
- gimple stmt;
- enum tree_code code;
-
- e = strip_wrap_conserving_type_conversions (e);
- what = strip_wrap_conserving_type_conversions (what);
-
- code = TREE_CODE (what);
- if (TREE_TYPE (e) != TREE_TYPE (what))
- return false;
-
- if (operand_equal_p (e, what, 0))
- return true;
-
- if (TREE_CODE (e) != SSA_NAME)
- return false;
-
- stmt = SSA_NAME_DEF_STMT (e);
- if (gimple_code (stmt) != GIMPLE_ASSIGN
- || gimple_assign_rhs_code (stmt) != code)
- return false;
-
- switch (get_gimple_rhs_class (code))
- {
- case GIMPLE_BINARY_RHS:
- if (!expr_equal_p (gimple_assign_rhs2 (stmt), TREE_OPERAND (what, 1)))
- return false;
- /* Fallthru. */
-
- case GIMPLE_UNARY_RHS:
- case GIMPLE_SINGLE_RHS:
- return expr_equal_p (gimple_assign_rhs1 (stmt), TREE_OPERAND (what, 0));
- default:
- return false;
- }
-}
-
/* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
we only detect the situation that BASE = SOMETHING + OFFSET, where the
calculation is performed in non-wrapping type.
TODO: More generally, we could test for the situation that
BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
- This would require knowing the sign of OFFSET.
+ This would require knowing the sign of OFFSET. */
- Also, we only look for the first addition in the computation of BASE.
- More complex analysis would be better, but introducing it just for
- this optimization seems like an overkill. */
-
static bool
-difference_cannot_overflow_p (tree base, tree offset)
+difference_cannot_overflow_p (struct ivopts_data *data, tree base, tree offset)
{
enum tree_code code;
tree e1, e2;
+ aff_tree aff_e1, aff_e2, aff_offset;
if (!nowrap_type_p (TREE_TYPE (base)))
return false;
@@ -4546,13 +4495,27 @@ static bool
e2 = TREE_OPERAND (base, 1);
}
- /* TODO: deeper inspection may be necessary to prove the equality. */
+ /* Use affine expansion as deeper inspection to prove the equality. */
+ tree_to_aff_combination_expand (e2, TREE_TYPE (e2),
+ &aff_e2, &data->name_expansion);
+ tree_to_aff_combination_expand (offset, TREE_TYPE (offset),
+ &aff_offset, &data->name_expansion);
+ aff_combination_scale (&aff_offset, -1);
switch (code)
{
case PLUS_EXPR:
- return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
+ aff_combination_add (&aff_e2, &aff_offset);
+ if (aff_combination_zero_p (&aff_e2))
+ return true;
+
+ tree_to_aff_combination_expand (e1, TREE_TYPE (e1),
+ &aff_e1, &data->name_expansion);
+ aff_combination_add (&aff_e1, &aff_offset);
+ return aff_combination_zero_p (&aff_e1);
+
case POINTER_PLUS_EXPR:
- return expr_equal_p (e2, offset);
+ aff_combination_add (&aff_e2, &aff_offset);
+ return aff_combination_zero_p (&aff_e2);
default:
return false;
@@ -4676,7 +4639,7 @@ iv_elimination_compare_lt (struct ivopts_data *dat
offset = fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),
cand->iv->step,
fold_convert (TREE_TYPE (cand->iv->step), a));
- if (!difference_cannot_overflow_p (cand->iv->base, offset))
+ if (!difference_cannot_overflow_p (data, cand->iv->base, offset))
return false;
/* Determine the new comparison operator. */
@@ -6801,6 +6764,7 @@ tree_ssa_iv_optimize_finalize (struct ivopts_data
data->iv_candidates.release ();
delete data->inv_expr_tab;
data->inv_expr_tab = NULL;
+ free_affine_expand_cache (&data->name_expansion);
}
/* Returns true if the loop body BODY includes any function calls. */
Index: gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c (revision 0)
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivopts" } */
+
+void
+f1 (int *p, unsigned int i)
+{
+ p += i;
+ do
+ {
+ *p = 0;
+ p += 1;
+ i++;
+ }
+ while (i < 100);
+}
+
+/* { dg-final { scan-tree-dump-times "PHI" 1 "ivopts" } } */
+/* { dg-final { scan-tree-dump-times "PHI <p_" 1 "ivopts"} } */
+/* { dg-final { scan-tree-dump-times "p_\[0-9\]* <" 1 "ivopts" } } */
+/* { dg-final { cleanup-tree-dump "ivopts" } } */
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/3]Improve induction variable elimination
2014-07-25 13:01 ` Richard Biener
2014-07-25 14:42 ` Bin.Cheng
2014-08-06 2:32 ` Bin.Cheng
@ 2014-08-14 7:37 ` Bin.Cheng
2014-08-14 15:29 ` Sebastian Pop
2 siblings, 1 reply; 8+ messages in thread
From: Bin.Cheng @ 2014-08-14 7:37 UTC (permalink / raw)
To: Richard Biener; +Cc: Bin Cheng, GCC Patches
[-- Attachment #1: Type: text/plain, Size: 2193 bytes --]
On Fri, Jul 25, 2014 at 8:35 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Jul 17, 2014 at 11:08 AM, Bin Cheng <bin.cheng@arm.com> wrote:
>> Hi,
>> As quoted from the function difference_cannot_overflow_p,
>>
>> /* TODO: deeper inspection may be necessary to prove the equality. */
>> switch (code)
>> {
>> case PLUS_EXPR:
>> return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
>> case POINTER_PLUS_EXPR:
>> return expr_equal_p (e2, offset);
>>
>> default:
>> return false;
>> }
>>
>> The overflow check can be improved by using deeper inspection to prove the
>> equality. This patch deals with that by making below two improvements:
>> a) Handles constant cases.
>> b) Uses affine expansion as deeper inspection to check the equality.
>>
>> As a result, functions strip_wrap_conserving_type_conversions and
>> expr_equal_p can be removed now. A test case is also added to illustrate iv
>> elimination opportunity captured by this patch.
>>
>> Thanks,
>> bin
>
> You add special casing for constants but I don't see any testcases for that.
> Specifically
>
> + /* No overflow if offset is zero. */
> + if (offset == integer_zero_node)
> return true;
>
> is a bogus check (use integer_zerop). Apart from the special-casing of
> constants the patch looks good to me.
Hi,
I changed/rebased the patch which passes bootstrap/test on x86_64.
Since it was review/approved before, I will commit it in 24 hours if
there is no objection.
Thanks,
bin
>
>
>> 2014-07-17 Bin Cheng <bin.cheng@arm.com>
>>
>> * tree-ssa-loop-ivopts.c (ivopts_data): New field name_expansion.
>> (tree_ssa_iv_optimize_init): Initialize name_expansion.
>> (tree_ssa_iv_optimize_finalize): Free name_expansion.
>> (strip_wrap_conserving_type_conversions, expr_equal_p): Delete.
>> (difference_cannot_overflow_p): New parameter. Handle constant
>> cases. Use affine expansion for equality check.
>> (iv_elimination_compare_lt): Pass new argument.
>>
>> gcc/testsuite/ChangeLog
>> 2014-07-17 Bin Cheng <bin.cheng@arm.com>
>>
>> * gcc.dg/tree-ssa/ivopts-lt-2.c: New test.
[-- Attachment #2: iv_elimination-improve-b-20140814.txt --]
[-- Type: text/plain, Size: 5721 bytes --]
Index: gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c (revision 0)
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivopts" } */
+
+void
+f1 (int *p, unsigned int i)
+{
+ p += i;
+ do
+ {
+ *p = 0;
+ p += 1;
+ i++;
+ }
+ while (i < 100);
+}
+
+/* { dg-final { scan-tree-dump-times "PHI" 1 "ivopts" } } */
+/* { dg-final { scan-tree-dump-times "PHI <p_" 1 "ivopts"} } */
+/* { dg-final { scan-tree-dump-times "p_\[0-9\]* <" 1 "ivopts" } } */
+/* { dg-final { cleanup-tree-dump "ivopts" } } */
Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c (revision 213937)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -323,6 +323,9 @@ struct ivopts_data
/* A bitmap of important candidates. */
bitmap important_candidates;
+ /* Cache used by tree_to_aff_combination_expand. */
+ hash_map<tree, name_expansion *> *name_expansion_cache;
+
/* The maximum invariant id. */
unsigned max_inv_id;
@@ -876,6 +879,7 @@ tree_ssa_iv_optimize_init (struct ivopts_data *dat
data->iv_candidates.create (20);
data->inv_expr_tab = new hash_table<iv_inv_expr_hasher> (10);
data->inv_expr_id = 0;
+ data->name_expansion_cache = NULL;
decl_rtl_to_reset.create (20);
}
@@ -4462,75 +4466,20 @@ iv_elimination_compare (struct ivopts_data *data,
return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
}
-static tree
-strip_wrap_conserving_type_conversions (tree exp)
-{
- while (tree_ssa_useless_type_conversion (exp)
- && (nowrap_type_p (TREE_TYPE (exp))
- == nowrap_type_p (TREE_TYPE (TREE_OPERAND (exp, 0)))))
- exp = TREE_OPERAND (exp, 0);
- return exp;
-}
-
-/* Walk the SSA form and check whether E == WHAT. Fairly simplistic, we
- check for an exact match. */
-
-static bool
-expr_equal_p (tree e, tree what)
-{
- gimple stmt;
- enum tree_code code;
-
- e = strip_wrap_conserving_type_conversions (e);
- what = strip_wrap_conserving_type_conversions (what);
-
- code = TREE_CODE (what);
- if (TREE_TYPE (e) != TREE_TYPE (what))
- return false;
-
- if (operand_equal_p (e, what, 0))
- return true;
-
- if (TREE_CODE (e) != SSA_NAME)
- return false;
-
- stmt = SSA_NAME_DEF_STMT (e);
- if (gimple_code (stmt) != GIMPLE_ASSIGN
- || gimple_assign_rhs_code (stmt) != code)
- return false;
-
- switch (get_gimple_rhs_class (code))
- {
- case GIMPLE_BINARY_RHS:
- if (!expr_equal_p (gimple_assign_rhs2 (stmt), TREE_OPERAND (what, 1)))
- return false;
- /* Fallthru. */
-
- case GIMPLE_UNARY_RHS:
- case GIMPLE_SINGLE_RHS:
- return expr_equal_p (gimple_assign_rhs1 (stmt), TREE_OPERAND (what, 0));
- default:
- return false;
- }
-}
-
/* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
we only detect the situation that BASE = SOMETHING + OFFSET, where the
calculation is performed in non-wrapping type.
TODO: More generally, we could test for the situation that
BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
- This would require knowing the sign of OFFSET.
+ This would require knowing the sign of OFFSET. */
- Also, we only look for the first addition in the computation of BASE.
- More complex analysis would be better, but introducing it just for
- this optimization seems like an overkill. */
-
static bool
-difference_cannot_overflow_p (tree base, tree offset)
+difference_cannot_overflow_p (struct ivopts_data *data, tree base, tree offset)
{
enum tree_code code;
tree e1, e2;
+ aff_tree aff_e1, aff_e2, aff_offset;
if (!nowrap_type_p (TREE_TYPE (base)))
return false;
@@ -4560,13 +4509,27 @@ static bool
e2 = TREE_OPERAND (base, 1);
}
- /* TODO: deeper inspection may be necessary to prove the equality. */
+ /* Use affine expansion as deeper inspection to prove the equality. */
+ tree_to_aff_combination_expand (e2, TREE_TYPE (e2),
+ &aff_e2, &data->name_expansion_cache);
+ tree_to_aff_combination_expand (offset, TREE_TYPE (offset),
+ &aff_offset, &data->name_expansion_cache);
+ aff_combination_scale (&aff_offset, -1);
switch (code)
{
case PLUS_EXPR:
- return expr_equal_p (e1, offset) || expr_equal_p (e2, offset);
+ aff_combination_add (&aff_e2, &aff_offset);
+ if (aff_combination_zero_p (&aff_e2))
+ return true;
+
+ tree_to_aff_combination_expand (e1, TREE_TYPE (e1),
+ &aff_e1, &data->name_expansion_cache);
+ aff_combination_add (&aff_e1, &aff_offset);
+ return aff_combination_zero_p (&aff_e1);
+
case POINTER_PLUS_EXPR:
- return expr_equal_p (e2, offset);
+ aff_combination_add (&aff_e2, &aff_offset);
+ return aff_combination_zero_p (&aff_e2);
default:
return false;
@@ -4690,7 +4653,7 @@ iv_elimination_compare_lt (struct ivopts_data *dat
offset = fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),
cand->iv->step,
fold_convert (TREE_TYPE (cand->iv->step), a));
- if (!difference_cannot_overflow_p (cand->iv->base, offset))
+ if (!difference_cannot_overflow_p (data, cand->iv->base, offset))
return false;
/* Determine the new comparison operator. */
@@ -6815,6 +6778,7 @@ tree_ssa_iv_optimize_finalize (struct ivopts_data
data->iv_candidates.release ();
delete data->inv_expr_tab;
data->inv_expr_tab = NULL;
+ free_affine_expand_cache (&data->name_expansion_cache);
}
/* Returns true if the loop body BODY includes any function calls. */
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/3]Improve induction variable elimination
2014-08-14 7:37 ` Bin.Cheng
@ 2014-08-14 15:29 ` Sebastian Pop
2014-08-15 6:15 ` Bin.Cheng
0 siblings, 1 reply; 8+ messages in thread
From: Sebastian Pop @ 2014-08-14 15:29 UTC (permalink / raw)
To: Bin.Cheng; +Cc: Richard Biener, Bin Cheng, GCC Patches
Bin.Cheng wrote:
> >> The overflow check can be improved by using deeper inspection to prove the
> >> equality. This patch deals with that by making below two improvements:
> >> a) Handles constant cases.
> >> b) Uses affine expansion as deeper inspection to check the equality.
Looks good to me.
Thanks,
Sebastian
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/3]Improve induction variable elimination
2014-08-14 15:29 ` Sebastian Pop
@ 2014-08-15 6:15 ` Bin.Cheng
0 siblings, 0 replies; 8+ messages in thread
From: Bin.Cheng @ 2014-08-15 6:15 UTC (permalink / raw)
To: Sebastian Pop; +Cc: Richard Biener, Bin Cheng, GCC Patches
On Thu, Aug 14, 2014 at 11:29 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> Bin.Cheng wrote:
>> >> The overflow check can be improved by using deeper inspection to prove the
>> >> equality. This patch deals with that by making below two improvements:
>> >> a) Handles constant cases.
>> >> b) Uses affine expansion as deeper inspection to check the equality.
>
> Looks good to me.
Thanks for reviewing. Committed as r213997.
Thanks,
bin
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2014-08-15 6:15 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-07-17 9:09 [PATCH 2/3]Improve induction variable elimination Bin Cheng
2014-07-25 13:01 ` Richard Biener
2014-07-25 14:42 ` Bin.Cheng
2014-08-06 2:32 ` Bin.Cheng
2014-08-06 9:55 ` Bin.Cheng
2014-08-14 7:37 ` Bin.Cheng
2014-08-14 15:29 ` Sebastian Pop
2014-08-15 6:15 ` Bin.Cheng
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).