On 08/07/15 00:41, Jeff Law wrote:
> On 07/07/2015 06:50 AM, Kugan wrote:
>>
>> Thanks for the review. I have addressed your comments above in the
>> attached patch.
>>
>> I have one question with respect to unary operation. For generic unary
>> operation with INTEGER_CST, do we skip this or do we have to perform the
>> inverse operation so that the conversion after PHI will restore it? Is
>> there any easy way to do this safely?
> I think we'd have to invert the operation -- some of which are trivial,
> such as BIT_NOT_EXPR.
>
> NEGATE_EXPR is trivial once you filter out the cases where inversion
> will create signed overflow (ie INT_MIN and like when arg1 is an
> INTEGER_CST).
>
> Similarly ABS_EXPR is trivial once you filter out cases where arg1 is a
> negative INTEGER_CST.
>
> If you want to try and handle those cases, I'm certainly comfortable
> with that as a follow-up. Obviously we'll want to testcases for them,
> including the cases where we don't want to make the transformation for
> NEGATE_EXPR and ABS_EXPR.
>
> There may be other special cases we need to handle for other unary
> operations. I haven't walked through the full list.
Thanks Jeff for the review.As you said later, I will skip generic unary
in this patch and work on that as an addition on top of this.
>
>>
>> Bootstrapped and regression tested the attached patch on
>> x86-64-none-linux-gnu with no new regressions.
>>
>> Thanks,
>> Kugan
>>
>>
>> p.txt
>>
>>
>> diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c
>> index 92b4ab0..1d6de9b 100644
>> --- a/gcc/tree-ssa-phiopt.c
>> +++ b/gcc/tree-ssa-phiopt.c
>> @@ -73,6 +73,7 @@ along with GCC; see the file COPYING3. If not see
>> static unsigned int tree_ssa_phiopt_worker (bool, bool);
>> static bool conditional_replacement (basic_block, basic_block,
>> edge, edge, gphi *, tree, tree);
>> +static bool factor_out_conditional_conversion (edge, edge, gphi *,
>> tree, tree);
>> static int value_replacement (basic_block, basic_block,
>> edge, edge, gimple, tree, tree);
>> static bool minmax_replacement (basic_block, basic_block,
>> @@ -335,6 +336,17 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool
>> do_hoist_loads)
>> node. */
>> gcc_assert (arg0 != NULL && arg1 != NULL);
>>
>> + if (factor_out_conditional_conversion (e1, e2, phi, arg0, arg1))
>> + {
>> + /* Update arg0 and arg1. */
>> + phis = phi_nodes (bb2);
>> + phi = single_non_singleton_phi_for_edges (phis, e1, e2);
>> + gcc_assert (phi);
>> + arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
>> + arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
>> + gcc_assert (arg0 != NULL && arg1 != NULL);
>> + }
>> +
> So small comment before this block of code indicating why we're
> recomputing these values. Something like this perhaps:
>
> /* factor_out_conditional_conversion may create a new PHI in BB2 and
> eliminate an existing PHI in BB2. Recompute values that may be
> affected by that change. */
>
>
> Or something along those lines.
Done.
>
>
>> /* Do the replacement of conditional if it can be done. */
>> if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
>> cfgchanged = true;
>> @@ -410,6 +422,133 @@ replace_phi_edge_with_variable (basic_block
>> cond_block,
>> bb->index);
>> }
>>
>> +/* PR66726: Factor conversion out of COND_EXPR. If the arguments of
>> the PHI
>> + stmt are CONVERT_STMT, factor out the conversion and perform the
>> conversion
>> + to the result of PHI stmt. */
>> +
>> +static bool
>> +factor_out_conditional_conversion (edge e0, edge e1, gphi *phi,
>> + tree arg0, tree arg1)
>> +{
>> + gimple arg0_def_stmt = NULL, arg1_def_stmt = NULL, new_stmt;
>> + tree new_arg0 = NULL_TREE, new_arg1 = NULL_TREE;
>> + tree temp, result;
>> + gphi *newphi;
>> + gimple_stmt_iterator gsi, gsi_for_def;
>> + source_location locus = gimple_location (phi);
>> + enum tree_code convert_code;
>> +
>> + /* Handle only PHI statements with two arguments. TODO: If all
>> + other arguments to PHI are INTEGER_CST, we can handle more
>> + than two arguments too. */
>> + if (gimple_phi_num_args (phi) != 2)
>> + return false;
> Similarly we can handle more than one SSA_NAME if their defining
> statement all have the same unary operation. Might as well add that to
> the comment too. While handling > 2 arguments is certainly possible, I
> really wonder how often those cases occur in practice.
>
Comment added. I will work on the implementation after this patch.
>> +
>> + /* If arg0 is an SSA_NAME and the stmt which defines arg0 is
>> + a conversion. */
>> + arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
>> + if (!is_gimple_assign (arg0_def_stmt)
>> + || (!gimple_assign_cast_p (arg0_def_stmt)
>> + && (get_gimple_rhs_class (gimple_assign_rhs_code (arg0_def_stmt))
>> + != GIMPLE_UNARY_RHS)))
> So what happens if arg0_def_stmt is a GIMPLE_UNARY_RHS other than a
> NOP_EXPR or CONVERT_EXPR? I'd probably punt anything that is not a
> gimple_assign_cast_p for the first iteration and follow-up with handling
> of the other unary operations as a follow-up.
>
>
>
>> + return false;
>> +
>> + /* Use the LHS as new_arg0. */
> s/LHS/RHS/
>
Done.
>> + convert_code = gimple_assign_rhs_code (arg0_def_stmt);
>> + new_arg0 = gimple_assign_rhs1 (arg0_def_stmt);
>> + if (convert_code == VIEW_CONVERT_EXPR)
>> + new_arg0 = TREE_OPERAND (new_arg0, 0);
> Is this really right for VIEW_CONVERT_EXPR? Also, do we do the right
> thing for FIX_TRUNC_EXPR?
>
I experimented with this and it seems to me that FIX_TRUNC_EXPR does not
need this. I added an execution testcase for VIEW_CONVERT_EXPR.
>
>> +
>> + /* If arg1 is an SSA_NAME and the stmt which defines arg0 is
>> + a conversion. */
> s/arg0/arg1/
>
> It's also the case that if arg1 is an SSA_NAME, then it must do the same
> operation as we found in arg0's defining statement. I see that's
> properly tested in the code, so just a minor comment updated needed.
>
>> +
>> + /* Create a new PHI stmt. */
>> + result = PHI_RESULT (phi);
>> + temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
>> + newphi = create_phi_node (temp, gimple_bb (phi));
>> +
>> + if (dump_file && (dump_flags & TDF_DETAILS))
>> + {
>> + fprintf (dump_file, "PHI ");
>> + print_generic_expr (dump_file, gimple_phi_result (phi), 0);
>> + fprintf (dump_file,
>> + " changed to factor conversion out from COND_EXPR.\n");
>> + fprintf (dump_file, "New stmt with CAST that defines ");
>> + print_generic_expr (dump_file, result, 0);
>> + fprintf (dump_file, ".\n");
>> + }
>> +
>> + /* Remove the old cast(s) that has single use. */
>> + if (arg0_def_stmt && has_single_use (arg0))
>> + {
>> + gsi_for_def = gsi_for_stmt (arg0_def_stmt);
>> + gsi_remove (&gsi_for_def, true);
>> + }
>> +
>> + if (arg1_def_stmt && has_single_use (arg1))
>> + {
>> + gsi_for_def = gsi_for_stmt (arg1_def_stmt);
>> + gsi_remove (&gsi_for_def, true);
>> + }
> So I would move the have_single_use tests up higher and reject the
> transformation if arg0/arg1 have > 1 use. The reason is if arg0/arg1
> have > 1 use, then this transformation actually increases the number of
> expressions evaluated at runtime.
Done.
>
> It'd probably be good to include a test when arg0 or arg1 are both
> SSA_NAMEs and new_arg0 and new_arg1 have > 1 use to verify the
> transformation does not apply in that case.
>
Done. Bootstrapped and regression tested on x86-64-none-linux-gnu with
no new regressions. Is this OK for trunk?
Thanks,
Kugan
diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr66726.c
b/gcc/testsuite/g++.dg/tree-ssa/pr66726.c
index e69de29..9b3bd8f 100644
--- a/gcc/testsuite/g++.dg/tree-ssa/pr66726.c
+++ b/gcc/testsuite/g++.dg/tree-ssa/pr66726.c
@@ -0,0 +1,36 @@
+
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+/* Execution test for converting VIEW_CONVERT_EXPR. */
+
+struct cpp_num {
+ bool f;
+};
+
+extern cpp_num __attribute__((noinline))
+foo (cpp_num lhs,
+ cpp_num rhs)
+{
+ lhs.f = lhs.f || rhs.f;
+ return lhs;
+}
+
+cpp_num lhs, rhs, r;
+
+int main ()
+{
+
+ lhs.f = false;
+ rhs.f = false;
+ r = foo (lhs, rhs);
+ if (r.f)
+ __builtin_abort ();
+
+
+ lhs.f = false;
+ rhs.f = true;
+ r = foo (lhs, rhs);
+ if (!r.f)
+ __builtin_abort ();
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr66726-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr66726-2.c
index e69de29..ab43d48 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr66726-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr66726-2.c
@@ -0,0 +1,19 @@
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-phiopt1-details" } */
+
+extern void bar (char, char);
+int
+foo (char b)
+{
+ char a;
+ a = b;
+ b = 'b';
+ bar (a, b);
+ b = a;
+ if (b == 0)
+ a++;
+ return a + b;
+}
+
+/* { dg-final { scan-tree-dump-times "factor conversion out" 0 "phiopt1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr66726.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr66726.c
index e69de29..a4c7418 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr66726.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr66726.c
@@ -0,0 +1,15 @@
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-phiopt1-details" } */
+
+extern unsigned short mode_size[];
+
+int
+oof (int mode)
+{
+ return (64 < mode_size[mode] ? 64 : mode_size[mode]);
+}
+
+/* { dg-final { scan-tree-dump-times "factor conversion out" 1 "phiopt1" } } */
+/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "phiopt1" } } */
+
diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c
index 92b4ab0..766ec63 100644
--- a/gcc/tree-ssa-phiopt.c
+++ b/gcc/tree-ssa-phiopt.c
@@ -73,6 +73,7 @@ along with GCC; see the file COPYING3. If not see
static unsigned int tree_ssa_phiopt_worker (bool, bool);
static bool conditional_replacement (basic_block, basic_block,
edge, edge, gphi *, tree, tree);
+static bool factor_out_conditional_conversion (edge, edge, gphi *, tree, tree);
static int value_replacement (basic_block, basic_block,
edge, edge, gimple, tree, tree);
static bool minmax_replacement (basic_block, basic_block,
@@ -335,6 +336,19 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool
do_hoist_loads)
node. */
gcc_assert (arg0 != NULL && arg1 != NULL);
+ if (factor_out_conditional_conversion (e1, e2, phi, arg0, arg1))
+ {
+ /* factor_out_conditional_conversion may create a new PHI in
+ BB2 and eliminate an existing PHI in BB2. Recompute values
+ that may be affected by that change. */
+ phis = phi_nodes (bb2);
+ phi = single_non_singleton_phi_for_edges (phis, e1, e2);
+ gcc_assert (phi);
+ arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
+ arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
+ gcc_assert (arg0 != NULL && arg1 != NULL);
+ }
+
/* Do the replacement of conditional if it can be done. */
if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
cfgchanged = true;
@@ -410,6 +424,134 @@ replace_phi_edge_with_variable (basic_block cond_block,
bb->index);
}
+/* PR66726: Factor conversion out of COND_EXPR. If the arguments of the PHI
+ stmt are CONVERT_STMT, factor out the conversion and perform the conversion
+ to the result of PHI stmt. */
+
+static bool
+factor_out_conditional_conversion (edge e0, edge e1, gphi *phi,
+ tree arg0, tree arg1)
+{
+ gimple arg0_def_stmt = NULL, arg1_def_stmt = NULL, new_stmt;
+ tree new_arg0 = NULL_TREE, new_arg1 = NULL_TREE;
+ tree temp, result;
+ gphi *newphi;
+ gimple_stmt_iterator gsi, gsi_for_def;
+ source_location locus = gimple_location (phi);
+ enum tree_code convert_code;
+
+ /* 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 false;
+
+ /* First canonicalize to simplify tests. */
+ if (TREE_CODE (arg0) != SSA_NAME)
+ {
+ std::swap (arg0, arg1);
+ std::swap (e0, e1);
+ }
+
+ if (TREE_CODE (arg0) != SSA_NAME
+ || (TREE_CODE (arg1) != SSA_NAME
+ && TREE_CODE (arg1) != INTEGER_CST))
+ return false;
+
+ /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
+ a conversion. */
+ arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
+ if (!is_gimple_assign (arg0_def_stmt)
+ || !gimple_assign_cast_p (arg0_def_stmt))
+ return false;
+
+ /* Use the RHS as new_arg0. */
+ convert_code = gimple_assign_rhs_code (arg0_def_stmt);
+ new_arg0 = gimple_assign_rhs1 (arg0_def_stmt);
+ if (convert_code == VIEW_CONVERT_EXPR)
+ new_arg0 = TREE_OPERAND (new_arg0, 0);
+
+ if (TREE_CODE (arg1) == SSA_NAME)
+ {
+ /* Check if arg1 is an SSA_NAME and the stmt which defines arg1
+ is a conversion. */
+ arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
+ if (!is_gimple_assign (arg1_def_stmt)
+ || gimple_assign_rhs_code (arg1_def_stmt) != convert_code)
+ return false;
+
+ /* Use the RHS as new_arg1. */
+ new_arg1 = gimple_assign_rhs1 (arg1_def_stmt);
+ if (convert_code == VIEW_CONVERT_EXPR)
+ new_arg1 = TREE_OPERAND (new_arg1, 0);
+ }
+ else
+ {
+ /* If arg1 is an INTEGER_CST, fold it to new type. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (new_arg0))
+ && int_fits_type_p (arg1, TREE_TYPE (new_arg0)))
+ {
+ if (gimple_assign_cast_p (arg0_def_stmt))
+ new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
+ else
+ return false;
+ }
+ else
+ return false;
+ }
+
+ /* If arg0/arg1 have > 1 use, then this transformation actually increases
+ the number of expressions evaluated at runtime. */
+ if (!has_single_use (arg0)
+ || (arg1_def_stmt && !has_single_use (arg1)))
+ return false;
+
+ /* If types of new_arg0 and new_arg1 are different bailout. */
+ if (TREE_TYPE (new_arg0) != TREE_TYPE (new_arg1))
+ return false;
+
+ /* Create a new PHI stmt. */
+ result = PHI_RESULT (phi);
+ temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
+ newphi = create_phi_node (temp, gimple_bb (phi));
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "PHI ");
+ print_generic_expr (dump_file, gimple_phi_result (phi), 0);
+ fprintf (dump_file,
+ " changed to factor conversion out from COND_EXPR.\n");
+ fprintf (dump_file, "New stmt with CAST that defines ");
+ print_generic_expr (dump_file, result, 0);
+ fprintf (dump_file, ".\n");
+ }
+
+ /* Remove the old cast(s) that has single use. */
+ gsi_for_def = gsi_for_stmt (arg0_def_stmt);
+ gsi_remove (&gsi_for_def, true);
+ if (arg1_def_stmt)
+ {
+ gsi_for_def = gsi_for_stmt (arg1_def_stmt);
+ gsi_remove (&gsi_for_def, true);
+ }
+
+ add_phi_arg (newphi, new_arg0, e0, locus);
+ add_phi_arg (newphi, new_arg1, e1, locus);
+
+ /* Create the conversion stmt and insert it. */
+ if (convert_code == VIEW_CONVERT_EXPR)
+ temp = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (result), temp);
+ new_stmt = gimple_build_assign (result, convert_code, temp);
+ gsi = gsi_after_labels (gimple_bb (phi));
+ gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
+
+ /* Remove he original PHI stmt. */
+ gsi = gsi_for_stmt (phi);
+ gsi_remove (&gsi, true);
+ return true;
+}
+
/* The function conditional_replacement does the main work of doing the
conditional replacement. Return true if the replacement is done.
Otherwise return false.
@@ -2142,6 +2284,26 @@ gate_hoist_loads (void)
This pass also performs a fifth transformation of a slightly different
flavor.
+ Factor conversion in COND_EXPR
+ ------------------------------
+
+ This transformation factors the conversion out of COND_EXPR with
+ factor_out_conditional_conversion.
+
+ For example:
+ if (a <= CST) goto <bb 3>; else goto <bb 4>;
+ <bb 3>:
+ tmp = (int) a;
+ <bb 4>:
+ tmp = PHI <tmp, CST>
+
+ Into:
+ if (a <= CST) goto <bb 3>; else goto <bb 4>;
+ <bb 3>:
+ <bb 4>:
+ a = PHI <a, CST>
+ tmp = (int) a;
+
Adjacent Load Hoisting
----------------------
