PR tree-optimization/81549 exposes delayed loop values represented by a
chain of loop-header PHIs.
When the loop executes at least twice, the final value of t0 is 2.
Scalar-evolution analysis does not always reduce such peeled PHI chains
to a usable final value.
Extend compute_final_value_from_loop_phi_latch to follow loop-header PHI
latch arguments until a loop-invariant value is reached. Record the
minimum number of latch executions required by the chain and only use
the invariant value when the iteration count proves that minimum.
Keep the existing exit-PHI final-value replacement path rather than
rewriting arbitrary uses outside the loop.
gcc/ChangeLog:
PR tree-optimization/81549
* tree-scalar-evolution.cc (latch_executions_at_least): New function.
(compute_final_value_from_loop_phi_latch): Follow loop-header PHI
latch chains when scalar-evolution analysis cannot produce a final
value.
gcc/testsuite/ChangeLog:
PR tree-optimization/81549
* gcc.dg/tree-ssa/pr81549.c: New test.
* gcc.dg/tree-ssa/pr81549-2.c: New test.
Signed-off-by: Naveen <[email protected]>
---
gcc/testsuite/gcc.dg/tree-ssa/pr81549-2.c | 46 +++++++++++
gcc/testsuite/gcc.dg/tree-ssa/pr81549.c | 28 +++++++
gcc/tree-scalar-evolution.cc | 95 ++++++++++++++++++-----
3 files changed, 148 insertions(+), 21 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr81549-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr81549.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr81549-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr81549-2.c
new file mode 100644
index 00000000000..236ef0cabd0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr81549-2.c
@@ -0,0 +1,46 @@
+/* PR tree-optimization/81549 */
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+int a[4];
+
+__attribute__((noipa)) int
+f (int n)
+{
+ int t0 = a[0];
+ int t1 = a[1];
+
+ for (int i = 0; i < n; ++i)
+ {
+ t0 = t1;
+ t1 = 2;
+ }
+
+ return t0;
+}
+
+__attribute__((noipa)) int
+g (void)
+{
+ int t0 = a[0];
+ int t1 = a[1];
+
+ for (int i = 0; i < 1; ++i)
+ {
+ t0 = t1;
+ t1 = 2;
+ }
+
+ return t0;
+}
+
+int
+main (void)
+{
+ a[0] = 11;
+ a[1] = 22;
+
+ if (f (0) != 11 || f (1) != 22 || f (2) != 2 || g () != 22)
+ __builtin_abort ();
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr81549.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr81549.c
new file mode 100644
index 00000000000..fdbe79ab1c5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr81549.c
@@ -0,0 +1,28 @@
+/* PR tree-optimization/81549 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-details -fdump-tree-optimized" } */
+
+int a[10000];
+
+int
+f (void)
+{
+ int t0 = a[0];
+ int t1 = a[1];
+
+ for (int i = 0; i < 100; ++i)
+ {
+ a[i] = 1;
+ t0 = t1;
+ t1 = 2;
+ }
+
+ a[100] = t0;
+ a[101] = t1;
+ return t0 + t1;
+}
+
+/* { dg-final { scan-tree-dump-times "with expr: 2" 1 "sccp" } } */
+/* { dg-final { scan-tree-dump {a\[100\] = 2;} "sccp" } } */
+/* { dg-final { scan-tree-dump {a\[101\] = 2;} "sccp" } } */
+/* { dg-final { scan-tree-dump "return 4;" "optimized" } } */
diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
index cd99cbe86ce..ce4ee03bb1d 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -3862,6 +3862,18 @@ analyze_and_compute_bitop_with_inv_effect (class loop*
loop, tree phidef,
return fold_build2 (code1, type, inv, match_op[0]);
}
+/* Return true if NITER is known to be at least MIN_NITER. */
+
+static bool
+latch_executions_at_least (tree niter, unsigned min_niter)
+{
+ if (min_niter == 1)
+ return tree_expr_nonzero_p (niter);
+
+ return (tree_fits_uhwi_p (niter)
+ && tree_to_uhwi (niter) >= min_niter);
+}
+
/* Try to compute the final value of PHIDEF when PHIDEF is the result of a
loop-header PHI.
@@ -3894,34 +3906,75 @@ compute_final_value_from_loop_phi_latch (class loop
*loop,
loop,
latch_arg,
folded_casts);
- if (ev == chrec_dont_know)
- return NULL_TREE;
- bool invariant_p;
- if (no_evolution_in_loop_p (ev, ex_loop->num, &invariant_p) && invariant_p)
- return ev;
- else if (TREE_CODE (ev) == POLYNOMIAL_CHREC
- && get_chrec_loop (ev) == ex_loop)
- {
- tree niter_type = TREE_TYPE (niter);
- tree prev_iter = fold_build2 (MINUS_EXPR,
- niter_type,
- niter,
- build_one_cst (niter_type));
+ if (ev != chrec_dont_know)
+ {
+ bool invariant_p;
+ if (no_evolution_in_loop_p (ev, ex_loop->num, &invariant_p)
+ && invariant_p)
+ return ev;
+ else if (TREE_CODE (ev) == POLYNOMIAL_CHREC
+ && get_chrec_loop (ev) == ex_loop)
+ {
+ tree niter_type = TREE_TYPE (niter);
+ tree prev_iter = fold_build2 (MINUS_EXPR,
+ niter_type,
+ niter,
+ build_one_cst (niter_type));
+
+ tree res = chrec_apply (ex_loop->num, ev, prev_iter);
+ if (res == chrec_dont_know)
+ return NULL_TREE;
+
+ if (chrec_contains_symbols_defined_in_loop (res, ex_loop->num))
+ {
+ res = instantiate_parameters (ex_loop, res);
+ if (res == chrec_dont_know)
+ return NULL_TREE;
+ }
+
+ return res;
+ }
+ }
+
+ /* SCEV can leave a delayed value as a chain of loop-header PHIs:
- tree res = chrec_apply (ex_loop->num, ev, prev_iter);
- if (res == chrec_dont_know)
- return NULL_TREE;
+ P0 = PHI <INIT0, P1>
+ P1 = PHI <INIT1, INV>
- if (chrec_contains_symbols_defined_in_loop (res, ex_loop->num))
+ After two latch executions P0 has the loop-invariant value INV.
+ Follow such chains explicitly and keep track of the required number
+ of latch executions. */
+ edge latch = loop_latch_edge (loop);
+ auto_vec<tree, 8> visited;
+ tree val = latch_arg;
+ unsigned min_niter = 1;
+
+ while (!expr_invariant_in_loop_p (loop, val))
{
- res = instantiate_parameters (ex_loop, res);
- if (res == chrec_dont_know)
+ if (TREE_CODE (val) != SSA_NAME)
+ return NULL_TREE;
+
+ for (unsigned i = 0; i < visited.length (); ++i)
+ if (visited[i] == val)
+ return NULL_TREE;
+ visited.safe_push (val);
+
+ gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (val));
+ if (!phi
+ || gimple_bb (phi) != loop->header
+ || gimple_phi_num_args (phi) != 2
+ || virtual_operand_p (PHI_RESULT (phi))
+ || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
return NULL_TREE;
+
+ val = PHI_ARG_DEF_FROM_EDGE (phi, latch);
+ ++min_niter;
}
- return res;
- }
+ if (latch_executions_at_least (niter, min_niter))
+ return val;
+
return NULL_TREE;
}
--
2.34.1
