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 PHI result is not
used inside the loop and 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 (ssa_name_has_nondebug_use_in_loop_p):
New function.
(compute_final_value_from_unused_loop_phi): New function.
(final_value_replacement_loop): Use it.
gcc/testsuite/:
* gcc.dg/tree-ssa/sccp-unused-loop-phi.c: New test.
---
.../gcc.dg/tree-ssa/sccp-unused-loop-phi.c | 55 +++++++++
gcc/tree-scalar-evolution.cc | 108 +++++++++++++++++-
2 files changed, 162 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/sccp-unused-loop-phi.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/sccp-unused-loop-phi.c
b/gcc/testsuite/gcc.dg/tree-ssa/sccp-unused-loop-phi.c
new file mode 100644
index 00000000000..3518a1957b3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/sccp-unused-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..56be952cda0 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -3845,6 +3845,104 @@ analyze_and_compute_bitop_with_inv_effect (class loop*
loop, tree phidef,
return fold_build2 (code1, type, inv, match_op[0]);
}
+static bool
+ssa_name_has_nondebug_use_in_loop_p (tree name, class loop* loop)
+{
+ gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
+
+ imm_use_iterator imm_iter;
+ use_operand_p use_p;
+
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
+ {
+ gimple* use_stmt = USE_STMT (use_p);
+
+ if (!use_stmt || is_gimple_debug (use_stmt))
+ continue;
+
+ basic_block use_bb = gimple_bb (use_stmt);
+ if (use_bb && flow_bb_inside_loop_p (loop, use_bb))
+ return true;
+ }
+
+ return false;
+}
+
+/* Try to compute the final value of PHIDEF when PHIDEF is the result of a
+ loop-header PHI whose value is not used inside LOOP.
+
+ 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_unused_loop_phi (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
+ || ssa_name_has_nondebug_use_in_loop_p (phidef, loop))
+ return NULL_TREE;
+
+ /* This helper only handles the case where at least one latch
+ edge is definitely taken. */
+ if (!tree_fits_uhwi_p (niter) || tree_to_uhwi (niter) == 0)
+ return NULL_TREE;
+
+ edge latch = loop_latch_edge (loop);
+ if (!latch)
+ return NULL_TREE;
+
+ tree latch_arg = PHI_ARG_DEF_FROM_EDGE (header_phi, latch);
+ if (!latch_arg)
+ return NULL_TREE;
+
+ 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,7 +3993,7 @@ 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, unused_phi_final_value;
unsigned HOST_WIDE_INT niter_num;
if (def != chrec_dont_know)
@@ -3932,6 +4030,14 @@ final_value_replacement_loop (class loop *loop)
niter_num)))
def = bit_def;
+ else if ((unused_phi_final_value
+ = compute_final_value_from_unused_loop_phi (loop,
+ ex_loop,
+ phidef,
+ niter,
+ &folded_casts)))
+ def = unused_phi_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
