@@ -259,8 +259,8 @@ chk_uses (tree, tree *idx, void *data)
with aliasing issues as we are moving memory reads. */
static bool
-propagate_with_phi (basic_block bb, gphi *phi, struct phiprop_d *phivn,
- size_t n)
+propagate_with_phi_1 (basic_block bb, gphi *phi, struct phiprop_d *phivn,
+ size_t n)
{
tree ptr = PHI_RESULT (phi);
gimple *use_stmt;
@@ -440,6 +440,207 @@ next:;
return phi_inserted;
}
+/* Return TRUE if USE_STMT, which uses PHI_RESULT will likely produce
+ a constant result if PHI_RESULT is itself a constant. Else return
+ FALSE.
+
+ It is safe for this routine to always return TRUE. If the result
+ is not a constant it will be detected and properly handled later.
+
+ This is overly conservative. If USE_STMT were to produce an SSA_NAME,
+ then that would still work for our purposes. */
+
+static bool
+stmt_likely_produces_constant_result (gimple *use_stmt, tree phi_result)
+{
+ enum tree_code code = gimple_assign_rhs_code (use_stmt);
+ switch (TREE_CODE_CLASS (code))
+ {
+ /* With few exceptions, a unary operator applied to a constant
+ will result in a constant. So they are OK without digging
+ deeper into the operator/operands. */
+ case tcc_unary:
+ return true;
+
+ /* For binary and comparisons we'll generally be able to generate
+ a constant if only one operand is an SSA_NAME. */
+ case tcc_binary:
+ case tcc_comparison:
+ {
+ tree rhs1 = gimple_assign_rhs1 (use_stmt);
+ tree rhs2 = gimple_assign_rhs2 (use_stmt);
+
+ /* We need to check for RES op CONST and CONST op RES. Consider
+ MINUS_EXPR or MIN/MAX where RES could be the first or the second
+ argument. */
+ if (rhs1 == phi_result
+ && TREE_CODE_CLASS (TREE_CODE (rhs2)) == tcc_constant)
+ return true;
+
+ if (rhs2 == phi_result
+ && TREE_CODE_CLASS (TREE_CODE (rhs1)) == tcc_constant)
+ return true;
+
+ /* We do not try to handle two SSA_NAME operands. */
+ return false;
+ }
+
+ /* There might be some tcc_reference or tcc_exceptional types we
+ could handle with deeper investigation. COND_EXPR comes to mind. */
+ default:
+ return false;
+ }
+}
+
+/* PHI in block BB produces RESULT. PHI_RESULT is used in USE_STMT.
+
+ All of PHIs arguments are simple constants. See if propagating
+ the PHI arguments into USE_STMT produces a constant. If that is
+ the case for all the PHI arguments, then STMT is replaced with a
+ new PHI and we return TRUE. Else make no changes to the IL and
+ return FALSE.
+
+ When applied this transformation reduces runtime computations and
+ replaces them with either constant initializations. This also enables
+ jump threading to occur earlier in the optimization pipeline. */
+
+static bool
+fold_use_into_phi (gphi *phi, gimple *use_stmt,
+ basic_block bb, tree phi_result)
+{
+ /* Now verify the use is an assigment to an SSA_NAME. */
+ if (!is_gimple_assign (use_stmt)
+ || TREE_CODE (gimple_assign_lhs (use_stmt)) != SSA_NAME)
+ return false;
+
+ /* If USE_STMT does not likely produce a constant result, then
+ do not try to fold this use. Note this is overly conservative
+ as we could handle USE_STMT simplifying to an SSA_NAME rather than
+ just constants. */
+ if (!stmt_likely_produces_constant_result (use_stmt, phi_result))
+ return false;
+
+ /* Build a new PHI node to replace the definition of the USE_STMT's LHS. */
+ gphi *new_phi = create_phi_node (NULL_TREE, bb);
+
+ /* Now fill in its arguments by applying the operator to each
+ argument of the original PHI. */
+ edge e;
+ edge_iterator ei;
+ tree use_result = gimple_assign_lhs (use_stmt);
+ tree type = TREE_TYPE (use_result);
+ enum tree_code code = gimple_assign_rhs_code (use_stmt);
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ tree old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ tree new_arg;
+
+ switch (TREE_CODE_CLASS (code))
+ {
+ case tcc_unary:
+ new_arg = fold_unary_to_constant (code, type, old_arg);
+ break;
+
+ case tcc_binary:
+ case tcc_comparison:
+ {
+ tree rhs1 = gimple_assign_rhs1 (use_stmt);
+ tree rhs2 = gimple_assign_rhs2 (use_stmt);
+ if (rhs1 == phi_result)
+ new_arg = fold_binary (code, type,
+ old_arg, gimple_assign_rhs2 (use_stmt));
+ else if (rhs2 == phi_result)
+ new_arg = fold_binary (code, type,
+ gimple_assign_rhs1 (use_stmt), old_arg);
+ else
+ gcc_unreachable ();
+ break;
+ }
+
+ default:
+ gcc_unreachable ();
+ }
+
+ /* We did not get a constant. This can happen (imagine division
+ by zero). We have to remove the PHI from the IL, as the PHI
+ is only partially constructed. */
+ if (!new_arg)
+ {
+ /* Set the PHI_RESULT to a new, throw-away SSA_NAME. This avoids
+ problems unlinking the "uses" of a currently NULL PHI_RESULT. */
+ gimple_phi_set_result (new_phi, make_ssa_name (type));
+
+ /* Actually remove the PHI from the IL. It is safe to remove the
+ PHI if some of its PHI arguments are still uninitialized. */
+ gimple_stmt_iterator gsi = gsi_for_stmt (new_phi);
+ remove_phi_node (&gsi, true);
+ return false;
+ }
+
+ source_location locus = gimple_phi_arg_location_from_edge (phi, e);
+ add_phi_arg (new_phi, new_arg, e, locus);
+ }
+
+ gimple_phi_set_result (new_phi, use_result);
+
+ /* At this point we have our new PHI installed where we want it.
+ Delete the old PHI and USE_STMT. */
+ gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
+ gsi_remove (&gsi, true);
+ return true;
+}
+
+/* Look for sequences like this:
+
+ # iftmp.4_16 = PHI <0(7), 1(8), 0(9)>
+ _30 = (unsigned char) iftmp.4_16;
+
+ We can "hoist" the conversion into the PHI and get it for free, generating:
+
+ # iftmp.4_16 = PHI <0(7), 1(8), 0(9)>
+ # _30 = PHI <0(7), 1(8), 0(9)>
+
+ DCE will eliminate the first PHI. In addition to getting the conversion
+ for free, removal of the conversion improves backwards threading. */
+
+static bool
+propagate_with_phi_2 (basic_block bb, gphi *phi)
+{
+ /* First verify that all the arguments of the PHI are constants.
+
+ This is overly conservative. Consider:
+
+ y = PHI (x, -1, 0);
+ z = y & x;
+
+ We could transform that into:
+
+ y = PHI (x, -1, 0);
+ z = PHI (x, x, 0);
+
+ It's not clear how important those cases are and we punt them
+ for now. */
+ use_operand_p arg_p;
+ ssa_op_iter i;
+ FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
+ {
+ tree arg = USE_FROM_PTR (arg_p);
+ if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant)
+ return false;
+ }
+
+ /* Not iterate over each immediate use to see if the statement can
+ be implemented as a PHI rather than a real statement. */
+ gimple *use_stmt;
+ imm_use_iterator ui;
+ bool retval = false;
+ tree phi_result = PHI_RESULT (phi);
+ FOR_EACH_IMM_USE_STMT (use_stmt, ui, phi_result)
+ retval |= fold_use_into_phi (phi, use_stmt, bb, phi_result);
+
+ return retval;
+}
+
/* Main entry for phiprop pass. */
namespace {
@@ -492,7 +693,10 @@ pass_phiprop::execute (function *fun)
single_succ (ENTRY_BLOCK_PTR_FOR_FN (fun)));
FOR_EACH_VEC_ELT (bbs, i, bb)
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
+ {
+ did_something |= propagate_with_phi_1 (bb, gsi.phi (), phivn, n);
+ did_something |= propagate_with_phi_2 (bb, gsi.phi ());
+ }
if (did_something)
gsi_commit_edge_inserts ();
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O3 -funroll-loops -fno-tree-vectorize -fdump-tree-cunroll-details -fdump-tree-cunrolli-details -fno-peel-loops" } */
+/* { dg-options "-O3 -fno-tree-phiprop -funroll-loops -fno-tree-vectorize -fdump-tree-cunroll-details -fdump-tree-cunrolli-details -fno-peel-loops" } */
#define N 8
#define M 14
new file mode 100644
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -funroll-loops -fno-tree-vectorize -fdump-tree-cunroll-details -fdump-tree-cunrolli-details -fdump-tree-phiprop -fno-peel-loops" } */
+
+#include "pr61743-1.c"
+
+/* { dg-final { scan-tree-dump-times "PHI <(\?:320|384|448)\\(\[0-9\]+\\), (\?:320|384|448)\\(\[0-9\]+\\), (\?:320|384|448)\\(\[0-9\]+\\)>" 1 "phiprop"} } */
+
+/* The code with PHI back propagation is simpler and we unswitch more. */
+/* { dg-final { scan-tree-dump-times "loop with 4 iterations completely unrolled" 10 "cunroll" } } */
+/* { dg-final { scan-tree-dump-times "loop with 9 iterations completely unrolled" 2 "cunrolli" } } */
@@ -1,6 +1,6 @@
/* PR tree-optimization/61839. */
/* { dg-do run } */
-/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-optimized" } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fno-tree-phiprop -fdump-tree-optimized" } */
/* { dg-require-effective-target int32plus } */
__attribute__ ((noinline))
new file mode 100644
@@ -0,0 +1,11 @@
+/* PR tree-optimization/61839. */
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-phiprop" } */
+/* { dg-require-effective-target int32plus } */
+
+#include "pr61839_1.c"
+
+/* Scan for c = 972195717) >> [0, 1] in function foo. */
+/* { dg-final { scan-tree-dump-times "486097858 : 972195717" 1 "vrp1" } } */
+/* Scan for c = 972195717) >> [2, 3] in function bar. */
+/* { dg-final { scan-tree-dump-times "PHI <(?:243048929|121524464)\\(\[0-9\]+\\), (?:243048929|121524464)\\(\[0-9\]+\\)>" 1 "phiprop"} } */
@@ -1,6 +1,6 @@
/* PR tree-optimization/61839. */
/* { dg-do run } */
-/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-optimized" } */
+/* { dg-options "-O2 -fno-tree-phiprop -fdump-tree-vrp1 -fdump-tree-optimized" } */
__attribute__ ((noinline))
int foo (int a, unsigned b)
new file mode 100644
@@ -0,0 +1,9 @@
+/* PR tree-optimization/61839. */
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-phiprop -fdump-tree-optimized" } */
+#include "pr61839_3.c"
+
+/* Scan for a PHI with (12, 13) << 8 in function foo. */
+/* { dg-final { scan-tree-dump-times "PHI <\(3072|3328\)\\(\[0-9\]+\\), \(3072|3328\)\\(\[0-9\
+]+\\)>" 1 "phiprop"} } */
+/* { dg-final { scan-tree-dump-times "3072" 0 "optimized" } } */
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+/* { dg-options "-O2 -fno-tree-phiprop -fdump-tree-pre-stats" } */
int foo(void)
{
int x, c, y;
new file mode 100644
@@ -0,0 +1,6 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-phiprop" } */
+#include "ssa-pre-4.c"
+/* We should eliminate the x+1 computation from this routine, replacing
+ it with a phi of 3, 4 */
+/* { dg-final { scan-tree-dump-times "PHI <\[34\]\\(\[0-9\]+\\), \[34\]\\(\[0-9\]+\\)>" 1 "phiprop"} } */