This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH]: Improved handling of COND_EXPR in middle-end passes


Diego Novillo wrote:
Roberto COSTA wrote on 11/27/06 05:34:

then, as a write-after-approval maintainer, I formally request the approval to check in the patch.

The mere act of submitting a patch implies a formal request for approval.

It's what I thought at first, but then I had the impression that it wasn't so... better to avoid misunderstandings.


Two different opinions do not imply consensus. I'm inclined to agree with Zdenek, but I also wonder whether the savings are significant to justify the added complexity sprinkled everywhere we need to support COND_EXPRs.

Why is this better than just converting the IFs when needed? Similarly, if we are going to support lval = COND_EXPR, are we *always* emitting them? If the memory savings are significant, then I would argue that we need to always emit them and make sure that all passes know how to deal with them.

Would you be interested in gathering some stats so that we have something concrete to argue with?

The question COND_EXPR as rhs vs explicit control-flow is the very reason why I started this short investigation about COND_EXPRs in GIMPLE.
In particular, I was interested in the impact of the two alternatives for the CLI back-end project.


At first glance, I was inclined to believe that supporting lval = COND_EXPR be a good thing. This led me to check what happens if the middle-end exposes many more COND_EXPRs than it currently does.
In my experiments, I patched the gimplifier in order not to expand COND_EXPRs used as expressions (when it's safe to do so); as a reminder, the gimplifier always expands such COND_EXPRs in the mainline.
After doing that, I discovered that some middle-end passes (beside dom and jump threading, which I already knew) were missing optimization opportunities because of the presence of unhandled COND_EXPR rhs. I also found out a bug leading to an infinite recursion in folding COND_EXPR nodes.
The patch I'm proposing just covers these issues: it supports COND_EXPR rhs in middle-end passes that aren't dealing with them but that could trivially do so and it fixes the above-mentioned bug.
I believe the same issues affect the mainline, they only show up much more rarely because of the quasi-sistematic elimination of COND_EXPR expressions done by the gimplifier.
I purposefully write "quasi-sistematic" elimination, since such COND_EXPRs are seldom reintroduced, i.e. by folding.


If you ask me now which is my position about this debate, I frankly say I don't have any strong opinion in favor or against either solution.
As a matter of fact, the conclusion of my investigation is that keeping COND_EXPRs as rhs doesn't have any significant impact to CLI back-end nor to a virtual machine executing CLI bytecode; hence, the current decision is to simplify them just before the emission of CLI bytecode.
I have no elements nor figures to state this in general.


What I'm arguing here is that, in the absence of a clear-cut decision about the matter, the behavior of the middle-end is sometimes inconsistent in this respect; this patch makes it a bit more consistent in cases in which consistency is achieved at low cost.
When and if COND_EXPRs are abolished from all rhs, then I have no objections in removing all the code aimed at them, this patch included.
But if the other solution be chosen, this patch avoids somebody else finding out and fixing the same issues I saw.


Cheers,
Roberto

P.S.: The patch is re-posted below with no changes, as a reference.


2006-11-22  Roberto Costa  <roberto.costa@st.com>

	* tree-vrp.c (extract_range_from_cond_expr): New.
	(extract_range_from_expr): Handle COND_EXPR nodes used as expressions.
	* tree-ssa-ccp.c (get_maxval_strlen): Handle COND_EXPR nodes used
	as expressions.
	(fold_stmt): Bug fix, avoid infinite recursion when folding COND_EXPRs.
	* tree-ssa-forwprop.c (simplify_cond, forward_propagate_into_cond,
	tree_ssa_forward_propagate_single_use_vars): Handle COND_EXPR nodes
	used as expressions.
	* tree-object-size.c (cond_expr_object_size): New.
	(collect_object_sizes_for): Handle COND_EXPR nodes used as expressions.

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 119088)
+++ gcc/tree-vrp.c	(working copy)
@@ -43,6 +43,7 @@ static sbitmap found_in_subgraph;
 
 /* Local functions.  */
 static int compare_values (tree val1, tree val2);
+static void vrp_meet (value_range_t *, value_range_t *);
 
 /* Location information for ASSERT_EXPRs.  Each instance of this
    structure describes an ASSERT_EXPR for an SSA name.  Since a single
@@ -1858,6 +1859,40 @@ extract_range_from_unary_expr (value_ran
 }
 
 
+/* Extract range information from a conditional expression EXPR based on
+   the ranges of each of its operands and the expression code.  */
+
+static void
+extract_range_from_cond_expr (value_range_t *vr, tree expr)
+{
+  tree op0, op1;
+  value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+  value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+
+  /* Get value ranges for each operand.  For constant operands, create
+     a new value range with the operand to simplify processing.  */
+  op0 = COND_EXPR_THEN (expr);
+  if (TREE_CODE (op0) == SSA_NAME)
+    vr0 = *(get_value_range (op0));
+  else if (is_gimple_min_invariant (op0))
+    set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
+  else
+    set_value_range_to_varying (&vr0);
+
+  op1 = COND_EXPR_ELSE (expr);
+  if (TREE_CODE (op1) == SSA_NAME)
+    vr1 = *(get_value_range (op1));
+  else if (is_gimple_min_invariant (op1))
+    set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
+  else
+    set_value_range_to_varying (&vr1);
+
+  /* The resulting value range is the union of the operand ranges */
+  vrp_meet (&vr0, &vr1);
+  copy_value_range (vr, &vr0);
+}
+
+
 /* Extract range information from a comparison expression EXPR based
    on the range of its operand and the expression code.  */
 
@@ -1899,6 +1934,8 @@ extract_range_from_expr (value_range_t *
     extract_range_from_binary_expr (vr, expr);
   else if (TREE_CODE_CLASS (code) == tcc_unary)
     extract_range_from_unary_expr (vr, expr);
+  else if (code == COND_EXPR)
+    extract_range_from_cond_expr (vr, expr);
   else if (TREE_CODE_CLASS (code) == tcc_comparison)
     extract_range_from_comparison (vr, expr);
   else if (is_gimple_min_invariant (expr))
Index: gcc/tree-ssa-ccp.c
===================================================================
--- gcc/tree-ssa-ccp.c	(revision 119088)
+++ gcc/tree-ssa-ccp.c	(working copy)
@@ -2053,6 +2053,10 @@ get_maxval_strlen (tree arg, tree *lengt
   
   if (TREE_CODE (arg) != SSA_NAME)
     {
+      if (TREE_CODE (arg) == COND_EXPR)
+        return get_maxval_strlen (COND_EXPR_THEN (arg), length, visited, type)
+               && get_maxval_strlen (COND_EXPR_ELSE (arg), length, visited, type);
+
       if (type == 2)
 	{
 	  val = arg;
@@ -2382,6 +2386,13 @@ fold_stmt (tree *stmt_p)
 	    }
 	}
     }
+  else if (TREE_CODE (rhs) == COND_EXPR)
+    {
+      tree temp = fold (COND_EXPR_COND (rhs));
+      if (temp != COND_EXPR_COND (rhs))
+        result = fold_build3 (COND_EXPR, TREE_TYPE (rhs), temp,
+                              COND_EXPR_THEN (rhs), COND_EXPR_ELSE (rhs));
+    }
 
   /* If we couldn't fold the RHS, hand over to the generic fold routines.  */
   if (result == NULL_TREE)
Index: gcc/tree-ssa-forwprop.c
===================================================================
--- gcc/tree-ssa-forwprop.c	(revision 119088)
+++ gcc/tree-ssa-forwprop.c	(working copy)
@@ -490,15 +490,16 @@ find_equivalent_equality_comparison (tre
   return NULL;
 }
 
-/* STMT is a COND_EXPR
+/* EXPR is a COND_EXPR
+   STMT is the statement containing EXPR.
 
    This routine attempts to find equivalent forms of the condition
    which we may be able to optimize better.  */
 
 static void
-simplify_cond (tree stmt)
+simplify_cond (tree cond_expr, tree stmt)
 {
-  tree cond = COND_EXPR_COND (stmt);
+  tree cond = COND_EXPR_COND (cond_expr);
 
   if (COMPARISON_CLASS_P (cond))
     {
@@ -517,7 +518,7 @@ simplify_cond (tree stmt)
 
 	      if (new_cond)
 		{
-		  COND_EXPR_COND (stmt) = new_cond;
+		  COND_EXPR_COND (cond_expr) = new_cond;
 		  update_stmt (stmt);
 		}
 	    }
@@ -529,7 +530,7 @@ simplify_cond (tree stmt)
    times as possible.  */
 
 static void
-forward_propagate_into_cond (tree cond_expr)
+forward_propagate_into_cond (tree cond_expr, tree stmt)
 {
   gcc_assert (TREE_CODE (cond_expr) == COND_EXPR);
 
@@ -554,7 +555,7 @@ forward_propagate_into_cond (tree cond_e
 	}
 
       COND_EXPR_COND (cond_expr) = new_cond;
-      update_stmt (cond_expr);
+      update_stmt (stmt);
 
       if (has_zero_uses (test_var))
 	{
@@ -569,7 +570,7 @@ forward_propagate_into_cond (tree cond_e
      against a constant where the SSA_NAME is the result of a
      conversion.  Perhaps this should be folded into the rest
      of the COND_EXPR simplification code.  */
-  simplify_cond (cond_expr);
+  simplify_cond (cond_expr, stmt);
 }
 
 /* We've just substituted an ADDR_EXPR into stmt.  Update all the 
@@ -1003,6 +1004,11 @@ tree_ssa_forward_propagate_single_use_va
 		  simplify_not_neg_expr (stmt);
 		  bsi_next (&bsi);
 		}
+              else if (TREE_CODE (rhs) == COND_EXPR)
+                {
+                  forward_propagate_into_cond (rhs, stmt);
+		  bsi_next (&bsi);
+                }
 	      else
 		bsi_next (&bsi);
 	    }
@@ -1013,7 +1019,7 @@ tree_ssa_forward_propagate_single_use_va
 	    }
 	  else if (TREE_CODE (stmt) == COND_EXPR)
 	    {
-	      forward_propagate_into_cond (stmt);
+	      forward_propagate_into_cond (stmt, stmt);
 	      bsi_next (&bsi);
 	    }
 	  else
Index: gcc/tree-object-size.c
===================================================================
--- gcc/tree-object-size.c	(revision 119088)
+++ gcc/tree-object-size.c	(working copy)
@@ -50,6 +50,7 @@ static void expr_object_size (struct obj
 static bool merge_object_sizes (struct object_size_info *, tree, tree,
 				unsigned HOST_WIDE_INT);
 static bool plus_expr_object_size (struct object_size_info *, tree, tree);
+static bool cond_expr_object_size (struct object_size_info *, tree, tree);
 static unsigned int compute_object_sizes (void);
 static void init_offset_limit (void);
 static void check_for_plus_in_loops (struct object_size_info *, tree);
@@ -621,6 +622,40 @@ plus_expr_object_size (struct object_siz
 }
 
 
+/* Compute object_sizes for PTR, defined to VALUE, which is
+   a COND_EXPR.  Return true if the object size might need reexamination
+   later.  */
+
+static bool
+cond_expr_object_size (struct object_size_info *osi, tree var, tree value)
+{
+  tree then_, else_;
+  int object_size_type = osi->object_size_type;
+  unsigned int varno = SSA_NAME_VERSION (var);
+  bool reexamine = false;
+
+  gcc_assert (TREE_CODE (value) == COND_EXPR);
+
+  if (object_sizes[object_size_type][varno] == unknown[object_size_type])
+    return false;
+
+  then_ = COND_EXPR_THEN (value);
+  else_ = COND_EXPR_ELSE (value);
+
+  if (TREE_CODE (then_) == SSA_NAME)
+    reexamine |= merge_object_sizes (osi, var, then_, 0);
+  else
+    expr_object_size (osi, var, then_);
+
+  if (TREE_CODE (else_) == SSA_NAME)
+    reexamine |= merge_object_sizes (osi, var, else_, 0);
+  else
+    expr_object_size (osi, var, else_);
+
+  return reexamine;
+}
+
+
 /* Compute object sizes for VAR.
    For ADDR_EXPR an object size is the number of remaining bytes
    to the end of the object (where what is considered an object depends on
@@ -711,6 +746,9 @@ collect_object_sizes_for (struct object_
 	else if (TREE_CODE (rhs) == PLUS_EXPR)
 	  reexamine = plus_expr_object_size (osi, var, rhs);
 
+        else if (TREE_CODE (rhs) == COND_EXPR)
+	  reexamine = cond_expr_object_size (osi, var, rhs);
+
 	else
 	  expr_object_size (osi, var, rhs);
 	break;

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]