Sometimes factor_out_conditional_operation can factor out
an operation that causes a phi node to become the same element.
Other times, we want to factor out a binary operator because
it can improve code generation, an example is PR 110015 (openjpeg).
Note this includes a heuristic to decide if factoring out the operation
is profitable or not. It can be expanded to include a better live range
extend detector. Right now it has a simple one where if it is live on a
dominating path, it is considered a live or if there are a small # of
assign statements (defaults to 5), then it does not extend the live range
too much.
Bootstrapped and tested on x86_64-linux-gnu.
PR tree-optimization/112418
gcc/ChangeLog:
* tree-ssa-phiopt.cc (is_factor_profitable): New function.
(factor_out_conditional_operation): Add merge argument. Remove
arg0/arg1 arguments. Return bool instead of the new phi.
Early return for virtual ops. Call is_factor_profitable to
check if the factoring would be profitable.
(pass_phiopt::execute): Call factor_out_conditional_operation
on all phis instead of just singleton phi.
* doc/invoke.texi (--param phiopt-factor-max-stmts-live=): Document.
* params.opt (--param=phiopt-factor-max-stmts-live=): New opt.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/factor_op_phi-1.c: New test.
* gcc.dg/tree-ssa/factor_op_phi-2.c: New test.
* gcc.dg/tree-ssa/factor_op_phi-3.c: New test.
* gcc.dg/tree-ssa/factor_op_phi-4.c: New test.
Signed-off-by: Andrew Pinski <quic_apin...@quicinc.com>
---
gcc/doc/invoke.texi | 4 +
gcc/params.opt | 4 +
.../gcc.dg/tree-ssa/factor_op_phi-1.c | 27 +++
.../gcc.dg/tree-ssa/factor_op_phi-2.c | 29 +++
.../gcc.dg/tree-ssa/factor_op_phi-3.c | 33 +++
.../gcc.dg/tree-ssa/factor_op_phi-4.c | 29 +++
gcc/tree-ssa-phiopt.cc | 209 ++++++++++++------
7 files changed, 272 insertions(+), 63 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-3.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-4.c
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 8437b2029ed..aebcc9082ff 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -15473,6 +15473,10 @@ In each case, the @var{value} is an integer. The
following choices
of @var{name} are recognized for all targets:
@table @gcctabopt
+@item phiopt-factor-max-stmts-live
+When factoring statements out of if/then/else, this is the max # of statements
+after the defining statement to be allow to extend the lifetime of a name
+
@item predictable-branch-outcome
When branch is predicted to be taken with probability lower than this threshold
(in percent), then it is considered well predictable.
diff --git a/gcc/params.opt b/gcc/params.opt
index a08e4c1042d..24f440bbe71 100644
--- a/gcc/params.opt
+++ b/gcc/params.opt
@@ -861,6 +861,10 @@ Enum(parloops_schedule_type) String(runtime)
Value(PARLOOPS_SCHEDULE_RUNTIME)
Common Joined UInteger Var(param_partial_inlining_entry_probability) Init(70)
Optimization IntegerRange(0, 100) Param
Maximum probability of the entry BB of split region (in percent relative to
entry BB of the function) to make partial inlining happen.
+-param=phiopt-factor-max-stmts-live=
+Common Joined UInteger Var(param_phiopt_factor_max_stmts_live) Init(5)
Optimization IntegerRange(0, 100) Param
+Maximum number of statements allowed inbetween the statement and the end to
considered not extending the liferange.
+
-param=predictable-branch-outcome=
Common Joined UInteger Var(param_predictable_branch_outcome) Init(2)
IntegerRange(0, 50) Param Optimization
Maximal estimated outcome of branch considered predictable.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-1.c
new file mode 100644
index 00000000000..6c0971ff801
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-1.c
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-phiopt1-details -fdump-tree-optimized" } */
+
+/* PR tree-optimization/112418 */
+
+int f(int a, int b, int d)
+{
+ int c;
+ if (a < 0)
+ {
+ a = -a;
+ c = d > 0 ? d : -d;
+ }
+ else
+ {
+ a = a;
+ c = d > 0 ? d : -d;
+ }
+ return a + c;
+}
+
+/* ABS <d> should be able to pull out of the if statement early on in phiopt1.
*/
+/* { dg-final { scan-tree-dump "changed to factor operation out from "
"phiopt1" } } */
+/* { dg-final { scan-tree-dump-not "if " "phiopt1" } } */
+/* { dg-final { scan-tree-dump-times "ABS_EXPR " 2 "phiopt1" } } */
+/* { dg-final { scan-tree-dump-not "if " "optimized" } } */
+/* { dg-final { scan-tree-dump-times "ABS_EXPR " 2 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-2.c
new file mode 100644
index 00000000000..93e2eb3a051
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-2.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-phiopt1-details -fdump-tree-optimized" } */
+
+/* PR tree-optimization/112418 */
+
+/* This is factor_op_phi-1.c but with statements swapped in the inner if. */
+
+int f(int a, int b, int d)
+{
+ int c;
+ if (a < 0)
+ {
+ c = d > 0 ? d : -d;
+ a = -a;
+ }
+ else
+ {
+ c = d > 0 ? d : -d;
+ a = a;
+ }
+ return a + c;
+}
+
+/* ABS <d> should be able to pull out of the if statement early on in phiopt1.
*/
+/* { dg-final { scan-tree-dump "changed to factor operation out from "
"phiopt1" } } */
+/* { dg-final { scan-tree-dump-not "if " "phiopt1" } } */
+/* { dg-final { scan-tree-dump-times "ABS_EXPR " 2 "phiopt1" } } */
+/* { dg-final { scan-tree-dump-not "if " "optimized" } } */
+/* { dg-final { scan-tree-dump-times "ABS_EXPR " 2 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-3.c
new file mode 100644
index 00000000000..0aca877fa36
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-3.c
@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-phiopt1-details -fdump-tree-optimized" } */
+
+int h(void);
+int h1(void);
+
+int f(int a, int b, int d)
+{
+ int c;
+ if (a < 0)
+ {
+ a = h();
+ c = d > 0 ? d : -d;
+ a += h();
+ }
+ else
+ {
+ a = h1();
+ c = d > 0 ? d : -d;
+ a += h1();
+ }
+ return a + c;
+}
+
+/* ABS <d> should be not to pulled out of the if statement early on in phiopt1
as it lengthes d's
+ live range over a call.
+ Note pre can lift the */
+/* { dg-final { scan-tree-dump-not "changed to factor operation out from "
"phiopt1" } } */
+/* { dg-final { scan-tree-dump "if " "phiopt1" } } */
+/* { dg-final { scan-tree-dump "if " "optimized" } } */
+/* There will be 2 ABS due to the need for it in the inner if. */
+/* { dg-final { scan-tree-dump-times "ABS_EXPR " 2 "phiopt1" } } */
+/* { dg-final { scan-tree-dump-times "ABS_EXPR " 2 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-4.c
b/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-4.c
new file mode 100644
index 00000000000..482c39b203b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/factor_op_phi-4.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-phiopt1-details -fdump-tree-optimized" } */
+
+/* PR tree-optimization/112418 */
+
+/* This is factor_op_phi-1.c but with statements swapped in the inner if. */
+
+int f(int a, int b, int d, int e)
+{
+ int c;
+ if (a < 0)
+ {
+ c = d > 0 ? d : -d;
+ a = -a;
+ }
+ else
+ {
+ c = e > 0 ? e : -e;
+ a = a;
+ }
+ return a + c;
+}
+
+/* ABS <d> should be able to pull out of the if statement early on in phiopt1.
*/
+/* { dg-final { scan-tree-dump "changed to factor operation out from "
"phiopt1" } } */
+/* { dg-final { scan-tree-dump-times "if " 1 "phiopt1" } } */
+/* { dg-final { scan-tree-dump-times "ABS_EXPR " 1 "phiopt1" } } */
+/* { dg-final { scan-tree-dump-times "if " 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "ABS_EXPR " 1 "optimized" } } */
diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index f3ee3a80c0f..38cc8506d1f 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -213,14 +213,90 @@ replace_phi_edge_with_variable (basic_block cond_block,
bb->index);
}
+/* Returns true if the ARG used from DEF_STMT is profitable to move
+ to a PHI node of the basic block MERGE where the new statement
+ will be located. */
+static bool
+is_factor_profitable (gimple *def_stmt, basic_block merge, tree arg)
+{
+ /* The defining statement should be conditional. */
+ if (dominated_by_p (CDI_DOMINATORS, merge,
+ gimple_bb (def_stmt)))
+ return false;
+
+ /* If the arg is invariant, then there is
+ no extending of the live range. */
+ if (is_gimple_min_invariant (arg))
+ return true;
+
+ /* Otherwise, the arg needs to be a ssa name. */
+ if (TREE_CODE (arg) != SSA_NAME)
+ return false;
+
+ /* We should not increase the live range of arg
+ across too many statements or calls. */
+ gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
+ gsi_next_nondebug (&gsi);
+
+ /* Skip past nops and predicates. */
+ while (!gsi_end_p (gsi)
+ && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
+ || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT))
+ gsi_next_nondebug (&gsi);
+
+ /* If the defining statement is at the end of the bb, then it is
+ always profitable to be to move. */
+ if (gsi_end_p (gsi))
+ return true;
+
+ /* Check if the uses of arg is dominated by merge block, this is a quick and
+ rough estimate if arg is still alive at the merge bb. */
+ /* FIXME: extend to a more complete live range detection. */
+ use_operand_p use_p;
+ imm_use_iterator iter;
+ FOR_EACH_IMM_USE_FAST (use_p, iter, arg)
+ {
+ gimple *use_stmt = USE_STMT (use_p);
+ basic_block use_bb = gimple_bb (use_stmt);
+ if (dominated_by_p (CDI_DOMINATORS, merge, use_bb))
+ return true;
+ }
+
+ /* If there are a few (non-call/asm) statements between
+ the old defining statement and end of the bb, then
+ the live range of new arg does not increase enough. */
+ int max_statements = param_phiopt_factor_max_stmts_live;
+
+ while (!gsi_end_p (gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ auto gcode = gimple_code (stmt);
+ /* Skip over NOPs and predicts. */
+ if (gcode == GIMPLE_NOP
+ || gcode == GIMPLE_PREDICT)
+ {
+ gsi_next_nondebug (&gsi);
+ continue;
+ }
+ /* Non-assigns will extend the live range too much. */
+ if (gcode != GIMPLE_ASSIGN)
+ return false;
+ max_statements --;
+ if (max_statements == 0)
+ return false;
+ gsi_next_nondebug (&gsi);
+ }
+ return true;
+}
+
/* PR66726: Factor operations out of COND_EXPR. If the arguments of the PHI
stmt are Unary operator, factor out the operation and perform the operation
to the result of PHI stmt. COND_STMT is the controlling predicate.
- Return the newly-created PHI, if any. */
+ Return true if the operation was factored out; false otherwise. */
-static gphi *
-factor_out_conditional_operation (edge e0, edge e1, gphi *phi,
- tree arg0, tree arg1, gimple *cond_stmt)
+static bool
+factor_out_conditional_operation (edge e0, edge e1, basic_block merge,
+ gphi *phi, gimple *cond_stmt)
{
gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL;
tree temp, result;
@@ -229,12 +305,21 @@ factor_out_conditional_operation (edge e0, edge e1, gphi
*phi,
location_t locus = gimple_location (phi);
gimple_match_op arg0_op, arg1_op;
- /* Handle only PHI statements with two arguments. TODO: If all
- other arguments to PHI are INTEGER_CST or if their defining
- statement have the same unary operation, we can handle more
- than two arguments too. */
- if (gimple_phi_num_args (phi) != 2)
- return NULL;
+ /* We should only get here if the phi had two arguments. */
+ gcc_assert (gimple_phi_num_args (phi) == 2);
+
+ /* Virtual operands are never handled. */
+ if (virtual_operand_p (gimple_phi_result (phi)))
+ return false;
+
+ tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
+ tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
+ gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
+
+ /* Arugments that are the same don't have anything to be
+ done to them. */
+ if (operand_equal_for_phi_arg_p (arg0, arg1))
+ return false;
/* First canonicalize to simplify tests. */
if (TREE_CODE (arg0) != SSA_NAME)
@@ -246,21 +331,21 @@ factor_out_conditional_operation (edge e0, edge e1, gphi
*phi,
if (TREE_CODE (arg0) != SSA_NAME
|| (TREE_CODE (arg1) != SSA_NAME
&& TREE_CODE (arg1) != INTEGER_CST))
- return NULL;
+ return false;
/* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
an unary operation. */
arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
if (!gimple_extract_op (arg0_def_stmt, &arg0_op))
- return NULL;
+ return false;
/* Check to make sure none of the operands are in abnormal phis. */
if (arg0_op.operands_occurs_in_abnormal_phi ())
- return NULL;
+ return false;
/* Currently just support one operand expressions. */
if (arg0_op.num_ops != 1)
- return NULL;
+ return false;
tree new_arg0 = arg0_op.ops[0];
tree new_arg1;
@@ -268,42 +353,45 @@ factor_out_conditional_operation (edge e0, edge e1, gphi
*phi,
/* If arg0 have > 1 use, then this transformation actually increases
the number of expressions evaluated at runtime. */
if (!has_single_use (arg0))
- return NULL;
+ return false;
+ if (!is_factor_profitable (arg0_def_stmt, merge, new_arg0))
+ return false;
if (TREE_CODE (arg1) == SSA_NAME)
{
/* Check if arg1 is an SSA_NAME. */
arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
if (!gimple_extract_op (arg1_def_stmt, &arg1_op))
- return NULL;
+ return false;
if (arg1_op.code != arg0_op.code)
- return NULL;
+ return false;
if (arg1_op.num_ops != arg0_op.num_ops)
- return NULL;
+ return false;
if (arg1_op.operands_occurs_in_abnormal_phi ())
- return NULL;
+ return false;
/* If arg1 have > 1 use, then this transformation actually increases
the number of expressions evaluated at runtime. */
if (!has_single_use (arg1))
- return NULL;
+ return false;
- /* Either arg1_def_stmt or arg0_def_stmt should be conditional. */
- if (dominated_by_p (CDI_DOMINATORS, gimple_bb (phi), gimple_bb
(arg0_def_stmt))
- && dominated_by_p (CDI_DOMINATORS,
- gimple_bb (phi), gimple_bb (arg1_def_stmt)))
- return NULL;
new_arg1 = arg1_op.ops[0];
+
+ if (!is_factor_profitable (arg1_def_stmt, merge, new_arg1))
+ return false;
}
else
{
+ /* For constants only handle if the phi was the only one. */
+ if (single_non_singleton_phi_for_edges (phi_nodes (merge), e0, e1) ==
NULL)
+ return false;
/* TODO: handle more than just casts here. */
if (!gimple_assign_cast_p (arg0_def_stmt))
- return NULL;
+ return false;
/* arg0_def_stmt should be conditional. */
if (dominated_by_p (CDI_DOMINATORS, gimple_bb (phi), gimple_bb
(arg0_def_stmt)))
- return NULL;
+ return false;
/* Only handle if arg1 is a INTEGER_CST and one that fits
into the new type or if it is the same precision. */
@@ -311,7 +399,7 @@ factor_out_conditional_operation (edge e0, edge e1, gphi
*phi,
|| !(int_fits_type_p (arg1, TREE_TYPE (new_arg0))
|| (TYPE_PRECISION (TREE_TYPE (new_arg0))
== TYPE_PRECISION (TREE_TYPE (arg1)))))
- return NULL;
+ return false;
/* For the INTEGER_CST case, we are just moving the
conversion from one place to another, which can often
@@ -356,26 +444,16 @@ factor_out_conditional_operation (edge e0, edge e1, gphi
*phi,
&& !(INTEGRAL_TYPE_P (lhst)
&& TYPE_UNSIGNED (lhst)
&& TYPE_PRECISION (lhst) == 1))
- return NULL;
+ return false;
if (lhs != gimple_assign_rhs1 (arg0_def_stmt))
- return NULL;
+ return false;
gsi_prev_nondebug (&gsi);
if (!gsi_end_p (gsi))
- return NULL;
+ return false;
}
else
- return NULL;
+ return false;
}
- gsi = gsi_for_stmt (arg0_def_stmt);
- gsi_next_nondebug (&gsi);
- /* Skip past nops and predicates. */
- while (!gsi_end_p (gsi)
- && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
- || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT))
- gsi_next_nondebug (&gsi);
- /* Reject if the statement was not at the end of the block. */
- if (!gsi_end_p (gsi))
- return NULL;
}
new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
@@ -386,7 +464,7 @@ factor_out_conditional_operation (edge e0, edge e1, gphi
*phi,
/* If types of new_arg0 and new_arg1 are different bailout. */
if (!types_compatible_p (TREE_TYPE (new_arg0), TREE_TYPE (new_arg1)))
- return NULL;
+ return false;
/* Create a new PHI stmt. */
result = gimple_phi_result (phi);
@@ -404,7 +482,7 @@ factor_out_conditional_operation (edge e0, edge e1, gphi
*phi,
if (!result)
{
release_ssa_name (temp);
- return NULL;
+ return false;
}
gsi = gsi_after_labels (gimple_bb (phi));
@@ -444,7 +522,7 @@ factor_out_conditional_operation (edge e0, edge e1, gphi
*phi,
statistics_counter_event (cfun, "factored out operation", 1);
- return newphi;
+ return true;
}
@@ -4327,6 +4405,29 @@ pass_phiopt::execute (function *)
basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
gimple_seq phis = phi_nodes (merge);
+ if (gimple_seq_empty_p (phis))
+ return;
+
+ /* Factor out operations from the phi if possible. */
+ if (single_pred_p (bb1)
+ && EDGE_COUNT (merge->preds) == 2)
+ {
+ for (gsi = gsi_start (phis); !gsi_end_p (gsi); )
+ {
+ gphi *phi = as_a <gphi *> (gsi_stmt (gsi));
+
+ if (factor_out_conditional_operation (e1, e2, merge, phi,
+ cond_stmt))
+ {
+ /* Start over if there was an operation that was factored out
because the new phi might have another opportunity. */
+ phis = phi_nodes (merge);
+ gsi = gsi_start (phis);
+ }
+ else
+ gsi_next (&gsi);
+ }
+ }
+
/* Value replacement can work with more than one PHI
so try that first. */
if (!early_p && !diamond_p)
@@ -4353,24 +4454,6 @@ pass_phiopt::execute (function *)
node. */
gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
- if (single_pred_p (bb1)
- && EDGE_COUNT (merge->preds) == 2)
- {
- gphi *newphi = phi;
- while (newphi)
- {
- phi = newphi;
- /* factor_out_conditional_operation may create a new PHI in
- BB2 and eliminate an existing PHI in BB2. Recompute values
- that may be affected by that change. */
- arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
- arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
- gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
- newphi = factor_out_conditional_operation (e1, e2, phi,
- arg0, arg1,
- cond_stmt);
- }
- }
/* Do the replacement of conditional if it can be done. */
if (match_simplify_replacement (bb, bb1, bb2, e1, e2, phi,
--
2.43.0
