On Thu, 13 Jan 2022, Jiufu Guo wrote:
> Hi,
>
> Previously, there is discussion in:
> https://gcc.gnu.org/pipermail/gcc-patches/2021-December/586460.html
> I seperate it as two patches.
>
> This first patch is to avoid negative step when combining two ivs.
> The second patch is adding more accurate assumptions.
>
> This patch pass bootstrap and regtest on ppc64, ppc64le and x86_64.
> Is this ok for trunk?
>
> BR,
> Jiufu
>
> PR tree-optimization/100740
>
> gcc/ChangeLog:
>
> * tree-ssa-loop-niter.c (number_of_iterations_cond): Check
> sign of combined step.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.c-torture/execute/pr100740.c: New test.
>
>
>
> ---
> gcc/tree-ssa-loop-niter.c | 6 ++++--
> gcc/testsuite/gcc.c-torture/execute/pr100740.c | 13 +++++++++++++
> 2 files changed, 17 insertions(+), 2 deletions(-)
> create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr100740.c
>
> diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
> index b767056aeb0..439d595a79f 100644
> --- a/gcc/tree-ssa-loop-niter.c
> +++ b/gcc/tree-ssa-loop-niter.c
> @@ -1890,8 +1890,10 @@ number_of_iterations_cond (class loop *loop,
> tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
> iv0->step, iv1->step);
>
> - /* No need to check sign of the new step since below code takes care
> - of this well. */
> + /* Like cases shown in PR100740/102131, negtive step is not safe. */
> + if (tree_int_cst_sign_bit (step))
> + return false;
> +
> if (code != NE_EXPR
> && (TREE_CODE (step) != INTEGER_CST
> || !iv0->no_overflow || !iv1->no_overflow))
I think for NE_EXPR the sign is not relevant. I think the key is
that we require that iv0->no_overflow and for non-equality checks
adjusting X + C1 < Y + C2 to X + C1 - C2 < Y is only valid if that
does not cause any overflow on either side. On the LHS this is
only guaranteed if the absolute value of C1 - C2 is smaller than
that of C1 and if it has the same sign.
With the same reasoning we then know the new IV0 doesn't overflow.
So something like the following. IIRC I've proposed sth similar
a while back. I'm going to give it some testing, collecting
testcases from related PRs.
diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index b767056aeb0..74fa4f66ee2 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -1890,17 +1890,28 @@ number_of_iterations_cond (class loop *loop,
tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
iv0->step, iv1->step);
- /* No need to check sign of the new step since below code takes
care
- of this well. */
- if (code != NE_EXPR
- && (TREE_CODE (step) != INTEGER_CST
- || !iv0->no_overflow || !iv1->no_overflow))
- return false;
+ /* For code other than NE_EXPR we have to ensure moving the
evolution
+ of IV1 to that of IV0 does not introduce overflow. */
+ if (TREE_CODE (step) != INTEGER_CST
+ || !iv0->no_overflow || !iv1->no_overflow)
+ {
+ if (code != NE_EXPR)
+ return false;
+ iv0->no_overflow = false;
+ }
+ /* If the new step of IV0 has changed sign or is of greater
+ magnitude then we do not know whether IV0 does overflow
+ and thus the transform is not valid for code other than NE_EXPR
*/
+ else if (tree_int_cst_sign_bit (step) != tree_int_cst_sign_bit
(iv0->step)
+ || wi::gtu_p (wi::abs (wi::to_widest (step)),
+ wi::abs (wi::to_widest (iv0->step))))
+ {
+ if (code != NE_EXPR)
+ return false;
+ iv0->no_overflow = false;
+ }
iv0->step = step;
- if (!POINTER_TYPE_P (type))
- iv0->no_overflow = false;
-
iv1->step = build_int_cst (step_type, 0);
iv1->no_overflow = true;
}
> diff --git a/gcc/testsuite/gcc.c-torture/execute/pr100740.c
> b/gcc/testsuite/gcc.c-torture/execute/pr100740.c
> new file mode 100644
> index 00000000000..381cdeb947a
> --- /dev/null
> +++ b/gcc/testsuite/gcc.c-torture/execute/pr100740.c
> @@ -0,0 +1,13 @@
> +/* PR tree-optimization/100740 */
> +
> +unsigned a, b;
> +int
> +main ()
> +{
> + unsigned c = 0;
> + for (a = 0; a < 2; a++)
> + for (b = 0; b < 2; b++)
> + if (++c < a)
> + __builtin_abort ();
> + return 0;
> +}
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Ivo Totev; HRB 36809 (AG Nuernberg)
