diff mbox

[PR66726] Factor conversion out of COND_EXPR

Message ID 559EFEE5.6030006@linaro.org
State New
Headers show

Commit Message

Kugan Vivekanandarajah July 9, 2015, 11:08 p.m. UTC 
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

Comments

Kugan Vivekanandarajah July 12, 2015, 11:24 a.m. UTC | #1 
On 11/07/15 06:40, Jeff Law wrote:
> On 07/09/2015 05:08 PM, Kugan wrote:
> 
>> Done. Bootstrapped and regression tested on x86-64-none-linux-gnu with
>> no new regressions. Is this OK for trunk?
> Thanks for the additional testcases.
> 
> 
> 
>> +  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;
>> +    }
> Something looks goofy here formatting-wise.  Can you please check for
> horizontal whitespace consistency before committing.
> 
> 
> 
>> +
>> +  /* If types of new_arg0 and new_arg1 are different bailout.  */
>> +  if (TREE_TYPE (new_arg0) != TREE_TYPE (new_arg1))
>> +    return false;
> Seems like this should use types_compatible_p here.  You're testing
> pointer equality, but as long as the types are compatible, we should be
> able to make the transformation.
> 
> With the horizontal whitespace fixed and using types_compatible_p this
> is OK for the trunk.  So pre-approved with those two changes and a final
> bootstrap/regression test (due to the types_compatible_p change).
> 
> jeff
> 

Thanks. Committed as r225722 with the changes. Also did a fresh
bootstrap and regression testing on x86_64-none-linux-gnu before committing.

Thanks,
Kugan
diff mbox

Patch

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
    ----------------------