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] COND_EXPRs in GIMPLE code and vectorizer


Roberto COSTA wrote:
Diego Novillo wrote:

Roberto COSTA wrote on 09/28/06 05:51:


If time allows me, I'd like to try to see what happens if COND_EXPRs are kept throughout the GIMPLE passes (I confess I'm curious). Logically, I see them as richer constructs (they carry more information than the equivalent control-flow code), like MIN_EXPRs and MAX_EXPRs.


Be wary of VRP and thread jumping if you do this. Both rely on the current COND_EXPR format quite heavily.


Before committing into anything, I will study the implications on these in order to evaluate the effort needed.

I've recently spent some time to study how vrp, dom and jump threading work; such implications are now clear to me.
I don't know yet how to solve them in the hypothesis that as many COND_EXPRs as possible are kept throughout the GIMPLE passes.


In the meantime, there are a few changes I made to some of the middle-end passes that I think are useful even when the gimplifier expands COND_EXPR expressions (the current behavior).
Basically, such passes currently handle COND_EXPR nodes only as statements and they may miss optimization opportunities in the presence of COND_EXPR expressions.
The following patch extends them to support COND_EXPR expressions.


I succesfully bootstrapped all languages on my i686 machine, with no regressions.

Comments?

Cheers,
Roberto
2006-10-17  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.
	* fold-const.c (fold_cond_expr_with_comparison): Bug fix, avoid
	infinite recursion when folding COND_EXPRs.
	* tree-ssa-ccp.c (get_maxval_strlen): Handle COND_EXPR nodes
	used as expressions.
	* 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 117639)
+++ 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
@@ -1947,6 +1948,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.  */
 
@@ -1988,6 +2023,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/fold-const.c
===================================================================
--- gcc/fold-const.c	(revision 117639)
+++ gcc/fold-const.c	(working copy)
@@ -4626,9 +4626,14 @@ fold_cond_expr_with_comparison (tree typ
     switch (comp_code)
       {
       case EQ_EXPR:
-	/* We can replace A with C1 in this case.  */
-	arg1 = fold_convert (type, arg01);
-	return fold_build3 (COND_EXPR, type, arg0, arg1, arg2);
+        /* Avoid infinite recursion */
+        if (TREE_CODE (arg1) != INTEGER_CST)
+          {
+            /* We can replace A with C1 in this case.  */
+            arg1 = fold_convert (type, arg01);
+            return fold_build3 (COND_EXPR, type, arg0, arg1, arg2);
+          }
+        break;
 
       case LT_EXPR:
 	/* If C1 is C2 + 1, this is min(A, C2).  */
Index: gcc/tree-ssa-ccp.c
===================================================================
--- gcc/tree-ssa-ccp.c	(revision 117639)
+++ gcc/tree-ssa-ccp.c	(working copy)
@@ -2085,6 +2085,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;
Index: gcc/tree-ssa-forwprop.c
===================================================================
--- gcc/tree-ssa-forwprop.c	(revision 117639)
+++ 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 
@@ -1001,6 +1002,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);
 	    }
@@ -1011,7 +1017,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 117639)
+++ 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]