SCEV sometimes fails to compute the final value of a loop PHI when the
entry value does not match the value produced by later iterations. For
example:
# y = PHI <y_next, 666>
i_next = i + 1;
y_next = i_next * 10;
The PHI value is:
666, 10, 20, 30, ...
This is not a normal affine recurrence. But if the latch count is
known to be nonzero, the entry value cannot be the value seen after
the loop. The final value is the latch argument evaluated at iteration
niter - 1.
Teach SCEV final value replacement to handle this case.
This patch was bootstrapped and regression tested on aarch64-linux-gnu.
gcc/:
* tree-scalar-evolution.cc
(compute_final_value_from_loop_phi_latch): New function.
(final_value_replacement_loop): Use it.
gcc/testsuite/:
* gcc.dg/tree-ssa/sccp-unused-loop-phi.c: New test.
---
Changes since v1:
- Removed no use requirement from loop phi
- Use number_of_iterations_exit in caller
- Removed redundant null checks
gcc/testsuite/gcc.dg/tree-ssa/sccp-loop-phi.c | 55 +++++++++++++
gcc/tree-scalar-evolution.cc | 77 ++++++++++++++++++-
2 files changed, 131 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/sccp-loop-phi.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/sccp-loop-phi.c
b/gcc/testsuite/gcc.dg/tree-ssa/sccp-loop-phi.c
new file mode 100644
index 00000000000..3518a1957b3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/sccp-loop-phi.c
@@ -0,0 +1,55 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp -fdump-tree-optimized" } */
+
+int
+const_init_unused_phi (void)
+{
+ int x = 0;
+ for (int i = 0, y = 666; i != 19; i++, y = i * 10)
+ x = y;
+ return x;
+}
+
+int
+conditional_init_unused_phi (int c)
+{
+ int x = 0;
+ int y;
+
+ if (c != 0)
+ y = 20;
+ else
+ y = 30;
+
+ for (int i = 0; i != 19; i++, y = i * 10)
+ x = y;
+
+ return x;
+}
+
+int
+nested_unused_phi (void)
+{
+ int acc = 0;
+
+ for (int i = 0; i < 20; i++)
+ {
+ int x = 0;
+ for (int j = 0, y = 123; j != 19; j++, y = i + 10)
+ x = y;
+ acc += x;
+ }
+
+ return acc;
+}
+
+/* Expected:
+ const_init_unused_phi -> 180
+ conditional_init_unused_phi -> 180
+ nested_unused_phi -> sum_{i=0}^{19} (i + 10) = 390
+ There should be no loop left in the optimized dump.
+*/
+
+/* { dg-final { scan-tree-dump-times "return 180" 2 "sccp" } } */
+/* { dg-final { scan-tree-dump "return 390" "sccp" } } */
+/* { dg-final { scan-tree-dump-times "goto" 0 "optimized" } } */
diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
index f524786f33b..18dc198fe96 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -3845,6 +3845,70 @@ analyze_and_compute_bitop_with_inv_effect (class loop*
loop, tree phidef,
return fold_build2 (code1, type, inv, match_op[0]);
}
+/* Try to compute the final value of PHIDEF when PHIDEF is the result of a
+ loop-header PHI.
+
+ This handles the nonzero-latch-count delayed-value form:
+
+ y_phi = PHI <latch_arg (latch), init (preheader)>
+
+ If the latch count is known to be nonzero, the final value is:
+
+ latch_arg evaluated at iteration niter - 1
+
+ Return NULL_TREE if the pattern does not apply. */
+static tree
+compute_final_value_from_loop_phi_latch (class loop *loop,
+ class loop *ex_loop, tree phidef, tree niter, bool* folded_casts)
+{
+ if (TREE_CODE (phidef) != SSA_NAME)
+ return NULL_TREE;
+
+ gimple* def_stmt = SSA_NAME_DEF_STMT (phidef);
+ gphi *header_phi = dyn_cast<gphi*> (def_stmt);
+ if (!header_phi
+ || gimple_bb (header_phi) != loop->header
+ || gimple_phi_num_args (header_phi) != 2)
+ return NULL_TREE;
+
+ tree latch_arg = PHI_ARG_DEF_FROM_EDGE (header_phi,
+ loop_latch_edge (loop));
+
+ tree ev = analyze_scalar_evolution_in_loop (ex_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));
+
+ 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;
+ }
+ return NULL_TREE;
+}
+
/* Do final value replacement for LOOP, return true if we did anything. */
bool
@@ -3895,8 +3959,9 @@ final_value_replacement_loop (class loop *loop)
def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
&folded_casts);
- tree bitinv_def, bit_def;
+ tree bitinv_def, bit_def, phi_latch_final_value;
unsigned HOST_WIDE_INT niter_num;
+ class tree_niter_desc niter_desc;
if (def != chrec_dont_know)
def = compute_overall_effect_of_inner_loop (ex_loop, def);
@@ -3932,6 +3997,16 @@ final_value_replacement_loop (class loop *loop)
niter_num)))
def = bit_def;
+ else if (number_of_iterations_exit (loop, exit, &niter_desc, false)
+ && integer_zerop (niter_desc.may_be_zero)
+ && (phi_latch_final_value
+ = compute_final_value_from_loop_phi_latch (loop,
+ ex_loop,
+ phidef,
+ niter_desc.niter,
+ &folded_casts)))
+ def = phi_latch_final_value;
+
bool cond_overflow_p;
if (!tree_does_not_contain_chrecs (def)
|| chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
--
2.43.0
