* [PATCH PR72817/PR73450]Fix wrong code caused by niter analyzer for NE_EXPR exit cond.
@ 2016-08-11 16:36 Bin Cheng
2016-08-12 8:06 ` Richard Biener
2016-08-16 22:09 ` Jakub Jelinek
0 siblings, 2 replies; 3+ messages in thread
From: Bin Cheng @ 2016-08-11 16:36 UTC (permalink / raw)
To: gcc-patches; +Cc: nd
[-- Attachment #1: Type: text/plain, Size: 1136 bytes --]
Hi,
I made a mistake when improving loop niter analysis for NE_EXPR exit condition.
It can results in wrong code as reported in PR72817/PR73450. In previous patch,
it simplifies below condition:
base <= FINAL ; step > 0
base >= FINAL ; step < 0
into:
base - step < FINAL ; step > 0 && base - step doesn't underflow
base - step > FINAL ; step < 0 && base - step doesn't overflow
But this is not enough. Since we adjusted IV.base to "new_base = IV.base - IV.step"
in the condition, we need to check if |FINAL - new_base| is multiple of |step| for the
adjusted base.
This patch fixes the issue as well as revises the comment. Bootstrap and test on
x86_64. Is it OK?
Thanks,
bin
2016-08-11 Bin Cheng <bin.cheng@arm.com>
PR tree-optimization/72817
PR tree-optimization/73450
* tree-ssa-loop-niter.c (number_of_iterations_ne): Check
multiple_of_p for adjusted IV.base.
gcc/testsuite/ChangeLog
2016-08-11 Bin Cheng <bin.cheng@arm.com>
PR tree-optimization/72817
PR tree-optimization/73450
* gcc.dg/tree-ssa/pr72817.c: New test.
* gcc.dg/tree-ssa/pr73450.c: New test.
[-- Attachment #2: pr72817-20160808.txt --]
[-- Type: text/plain, Size: 4316 bytes --]
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index c740ffa..8851862 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -999,33 +999,36 @@ number_of_iterations_ne (struct loop *loop, tree type, affine_iv *iv,
mpz_clear (max);
/* Compute no-overflow information for the control iv. This can be
- proven when below two conditions hold.
-
- 1) |FINAL - base| is an exact multiple of step.
- 2) IV evaluates toward FINAL at beginning, i.e:
+ proven when below two conditions are satisfied:
+ 1) IV evaluates toward FINAL at beginning, i.e:
base <= FINAL ; step > 0
base >= FINAL ; step < 0
- Note the first condition holds, the second can be then relaxed
- to below condition.
+ 2) |FINAL - base| is an exact multiple of step.
+
+ Unfortunately, it's hard to prove above conditions after pass loop-ch
+ because loop with exit condition (IV != FINAL) usually will be guarded
+ by initial-condition (IV.base - IV.step != FINAL). In this case, we
+ can alternatively try to prove below conditions:
+
+ 1') IV evaluates toward FINAL at beginning, i.e:
+ new_base = base - step < FINAL ; step > 0
+ && base - step doesn't underflow
+ new_base = base - step > FINAL ; step < 0
+ && base - step doesn't overflow
- base - step < FINAL ; step > 0
- && base - step doesn't underflow
- base - step > FINAL ; step < 0
- && base - step doesn't overflow
+ 2') |FINAL - new_base| is an exact multiple of step.
- The relaxation is important because after pass loop-ch, loop
- with exit condition (IV != FINAL) will usually be guarded by
- pre-condition (IV.base - IV.step != FINAL). Please refer to
- PR34114 as an example.
+ Please refer to PR34114 as an example of loop-ch's impact, also refer
+ to PR72817 as an example why condition 2') is necessary.
- Also note, for NE_EXPR, base equals to FINAL is a special case, in
+ Note, for NE_EXPR, base equals to FINAL is a special case, in
which the loop exits immediately, and the iv does not overflow. */
if (!niter->control.no_overflow
&& (integer_onep (s) || multiple_of_p (type, c, s)))
{
- tree t, cond, relaxed_cond = boolean_false_node;
+ tree t, cond, new_c, relaxed_cond = boolean_false_node;
if (tree_int_cst_sign_bit (iv->step))
{
@@ -1039,8 +1042,12 @@ number_of_iterations_ne (struct loop *loop, tree type, affine_iv *iv,
if (integer_nonzerop (t))
{
t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
- relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node,
- t, final);
+ new_c = fold_build2 (MINUS_EXPR, niter_type,
+ fold_convert (niter_type, t),
+ fold_convert (niter_type, final));
+ if (multiple_of_p (type, new_c, s))
+ relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node,
+ t, final);
}
}
}
@@ -1056,8 +1063,12 @@ number_of_iterations_ne (struct loop *loop, tree type, affine_iv *iv,
if (integer_nonzerop (t))
{
t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
- relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node,
- t, final);
+ new_c = fold_build2 (MINUS_EXPR, niter_type,
+ fold_convert (niter_type, final),
+ fold_convert (niter_type, t));
+ if (multiple_of_p (type, new_c, s))
+ relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node,
+ t, final);
}
}
}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr72817.c b/gcc/testsuite/gcc.dg/tree-ssa/pr72817.c
new file mode 100644
index 0000000..290e096
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr72817.c
@@ -0,0 +1,13 @@
+/* { dg-do run } */
+/* { dg-options "-O3" } */
+
+char a;
+short b;
+
+int main ()
+{
+ for (a = 3; a != -1; a -= 5)
+ while (b)
+ ;
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr73450.c b/gcc/testsuite/gcc.dg/tree-ssa/pr73450.c
new file mode 100644
index 0000000..7dd44db
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr73450.c
@@ -0,0 +1,14 @@
+/* { dg-do run } */
+/* { dg-options "-O3" } */
+
+int a;
+char b;
+int main() {
+ char c = 0;
+ for (; c != 3; c = c + 7) {
+ a = b & a;
+ if (a)
+ break;
+ }
+ return 0;
+}
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH PR72817/PR73450]Fix wrong code caused by niter analyzer for NE_EXPR exit cond.
2016-08-11 16:36 [PATCH PR72817/PR73450]Fix wrong code caused by niter analyzer for NE_EXPR exit cond Bin Cheng
@ 2016-08-12 8:06 ` Richard Biener
2016-08-16 22:09 ` Jakub Jelinek
1 sibling, 0 replies; 3+ messages in thread
From: Richard Biener @ 2016-08-12 8:06 UTC (permalink / raw)
To: Bin Cheng; +Cc: gcc-patches, nd
On Thu, Aug 11, 2016 at 6:35 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> I made a mistake when improving loop niter analysis for NE_EXPR exit condition.
> It can results in wrong code as reported in PR72817/PR73450. In previous patch,
> it simplifies below condition:
> base <= FINAL ; step > 0
> base >= FINAL ; step < 0
> into:
> base - step < FINAL ; step > 0 && base - step doesn't underflow
> base - step > FINAL ; step < 0 && base - step doesn't overflow
> But this is not enough. Since we adjusted IV.base to "new_base = IV.base - IV.step"
> in the condition, we need to check if |FINAL - new_base| is multiple of |step| for the
> adjusted base.
>
> This patch fixes the issue as well as revises the comment. Bootstrap and test on
> x86_64. Is it OK?
Ok.
Thanks,
Richard.
> Thanks,
> bin
>
> 2016-08-11 Bin Cheng <bin.cheng@arm.com>
>
> PR tree-optimization/72817
> PR tree-optimization/73450
> * tree-ssa-loop-niter.c (number_of_iterations_ne): Check
> multiple_of_p for adjusted IV.base.
>
> gcc/testsuite/ChangeLog
> 2016-08-11 Bin Cheng <bin.cheng@arm.com>
>
> PR tree-optimization/72817
> PR tree-optimization/73450
> * gcc.dg/tree-ssa/pr72817.c: New test.
> * gcc.dg/tree-ssa/pr73450.c: New test.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH PR72817/PR73450]Fix wrong code caused by niter analyzer for NE_EXPR exit cond.
2016-08-11 16:36 [PATCH PR72817/PR73450]Fix wrong code caused by niter analyzer for NE_EXPR exit cond Bin Cheng
2016-08-12 8:06 ` Richard Biener
@ 2016-08-16 22:09 ` Jakub Jelinek
1 sibling, 0 replies; 3+ messages in thread
From: Jakub Jelinek @ 2016-08-16 22:09 UTC (permalink / raw)
To: Bin Cheng; +Cc: gcc-patches, nd
On Thu, Aug 11, 2016 at 04:35:51PM +0000, Bin Cheng wrote:
> 2016-08-11 Bin Cheng <bin.cheng@arm.com>
>
> PR tree-optimization/72817
> PR tree-optimization/73450
> * gcc.dg/tree-ssa/pr72817.c: New test.
> * gcc.dg/tree-ssa/pr73450.c: New test.
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr72817.c
> @@ -0,0 +1,13 @@
> +/* { dg-do run } */
> +/* { dg-options "-O3" } */
> +
> +char a;
> +short b;
> +
> +int main ()
> +{
> + for (a = 3; a != -1; a -= 5)
> + while (b)
> + ;
> + return 0;
> +}
The testcase hangs for obvious reasons on -funsigned-char defaulting
targets. Fixed thusly, committed as obvious:
2016-08-16 Jakub Jelinek <jakub@redhat.com>
PR tree-optimization/72817
* gcc.dg/tree-ssa/pr72817.c (a): Change type from char to signed char.
--- gcc.dg/tree-ssa/pr72817.c (revision 239513)
+++ gcc.dg/tree-ssa/pr72817.c (revision 239514)
@@ -1,7 +1,7 @@
/* { dg-do run } */
/* { dg-options "-O3" } */
-char a;
+signed char a;
short b;
int main ()
Jakub
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2016-08-16 22:09 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-08-11 16:36 [PATCH PR72817/PR73450]Fix wrong code caused by niter analyzer for NE_EXPR exit cond Bin Cheng
2016-08-12 8:06 ` Richard Biener
2016-08-16 22:09 ` Jakub Jelinek
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).