Re: [tree-ssa] CCP and non-destructive folding problems

[Diego Novillo <dnovillo at redhat dot com>]

Apologies.  I sent an old version of the patch.  Here's the
correct one.


Diego.

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.75
diff -d -u -p -r1.903.2.75 Makefile.in
--- Makefile.in	23 Feb 2003 22:02:51 -0000	1.903.2.75
+++ Makefile.in	25 Feb 2003 15:35:13 -0000
@@ -1505,7 +1505,8 @@ tree-pretty-print.o : tree-pretty-print.
    errors.h $(TREE_H) diagnostic.h real.h $(HASHTAB_H) $(TREE_FLOW_H) \
    $(TM_H) coretypes.h
 fold-const.o : fold-const.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
-   flags.h real.h toplev.h $(HASHTAB_H) $(EXPR_H) $(RTL_H) $(GGC_H) $(TM_P_H) langhooks.h
+   flags.h real.h toplev.h $(HASHTAB_H) $(EXPR_H) $(RTL_H) $(GGC_H) $(TM_P_H) \
+   langhooks.h $(TREE_SIMPLE_H)
 diagnostic.o : diagnostic.c diagnostic.h real.h diagnostic.def \
    $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(TM_P_H) flags.h $(GGC_H) \
    input.h toplev.h intl.h langhooks.h $(LANGHOOKS_DEF_H)
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.213.2.22
diff -d -u -p -r1.213.2.22 fold-const.c
--- fold-const.c	23 Feb 2003 22:03:03 -0000	1.213.2.22
+++ fold-const.c	25 Feb 2003 15:35:13 -0000
@@ -56,6 +56,7 @@ Software Foundation, 59 Temple Place - S
 #include "ggc.h"
 #include "hashtab.h"
 #include "langhooks.h"
+#include "tree-simple.h"
 
 static void encode		PARAMS ((HOST_WIDE_INT *,
 					 unsigned HOST_WIDE_INT,
@@ -5049,16 +5050,15 @@ nondestructive_fold_binary (code, type, 
   /* Note if either argument is not a real or integer constant.
      With a few exceptions, simplification is limited to cases
      where both arguments are constants.  */
-  if ((TREE_CODE (subop0) != INTEGER_CST
-       && TREE_CODE (subop0) != REAL_CST)
-      || (TREE_CODE (subop1) != INTEGER_CST
-	  && TREE_CODE (subop1) != REAL_CST))
+  if (!is_simple_const (subop0) || !is_simple_const (subop1))
     wins = 0;
 
   switch (code)
     {
     case PLUS_EXPR:
     case BIT_XOR_EXPR:
+      if (!FLOAT_TYPE_P (type) && integer_zerop (subop1))
+	return non_lvalue (convert (type, subop0));
 
     binary:
       if (!wins)
@@ -5241,12 +5241,56 @@ nondestructive_fold_binary (code, type, 
 
     case RANGE_EXPR:
       /* This could probably be handled.  */
+      return NULL_TREE;
 
-    default:
+    case TRUTH_AND_EXPR:
+      /* If either arg is constant true, drop it.  */
+      if (TREE_CODE (op0) == INTEGER_CST && ! integer_zerop (op0))
+	return non_lvalue (convert (type, op1));
+      if (TREE_CODE (op1) == INTEGER_CST && ! integer_zerop (op1))
+	return non_lvalue (convert (type, op0));
+      /* If second arg is constant zero, result is zero, but first arg
+	 must be evaluated.  */
+      if (integer_zerop (op1))
+	return omit_one_operand (type, op1, op0);
+      /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
+	 case will be handled here.  */
+      if (integer_zerop (op0))
+	return omit_one_operand (type, op0, op1);
+      return NULL_TREE;
+
+    case TRUTH_OR_EXPR:
+      /* If either arg is constant zero, drop it.  */
+      if (TREE_CODE (op0) == INTEGER_CST && integer_zerop (op0))
+	return non_lvalue (convert (type, op1));
+      if (TREE_CODE (op1) == INTEGER_CST && integer_zerop (op1))
+	return non_lvalue (convert (type, op0));
+      /* If second arg is constant true, result is true, but we must
+	 evaluate first arg.  */
+      if (TREE_CODE (op1) == INTEGER_CST && ! integer_zerop (op1))
+	return omit_one_operand (type, op1, op0);
+      /* Likewise for first arg, but note this only occurs here for
+	 TRUTH_OR_EXPR.  */
+      if (TREE_CODE (op0) == INTEGER_CST && ! integer_zerop (op0))
+	return omit_one_operand (type, op0, op1);
       return NULL_TREE;
-    }
 
+    case TRUTH_XOR_EXPR:
+      /* If either arg is constant zero, drop it.  */
+      if (integer_zerop (op0))
+	return non_lvalue (convert (type, op1));
+      if (integer_zerop (op1))
+	return non_lvalue (convert (type, op0));
+      /* If either arg is constant true, this is a logical inversion.  */
+      if (integer_onep (op0))
+	return non_lvalue (convert (type, invert_truthvalue (op1)));
+      if (integer_onep (op1))
+	return non_lvalue (convert (type, invert_truthvalue (op0)));
+      return NULL_TREE;
 
+    default:
+      return NULL_TREE;
+    }
 }
 
 /* Given the components of a unary expression CODE, TYPE and OP0,
Index: tree-simple.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-simple.c,v
retrieving revision 1.1.4.28
diff -d -u -p -r1.1.4.28 tree-simple.c
--- tree-simple.c	4 Feb 2003 03:11:15 -0000	1.1.4.28
+++ tree-simple.c	25 Feb 2003 15:35:14 -0000
@@ -638,7 +638,8 @@ is_simple_const (t)
   STRIP_NOPS (t);
 
   if (TREE_CODE (t) == ADDR_EXPR
-      && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)
+      && (TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST
+	  || TREE_CODE (TREE_OPERAND (t, 0)) == VAR_DECL))
     return 1;
 
   return (TREE_CODE (t) == INTEGER_CST
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.55
diff -d -u -p -r1.1.2.55 tree-ssa-ccp.c
--- tree-ssa-ccp.c	25 Feb 2003 13:28:25 -0000	1.1.2.55
+++ tree-ssa-ccp.c	25 Feb 2003 15:35:14 -0000
@@ -117,7 +117,7 @@ static value evaluate_stmt		PARAMS ((tre
 static void dump_lattice_value		PARAMS ((FILE *, const char *, value));
 static tree widen_bitfield		PARAMS ((tree, tree, tree));
 static bool replace_uses_in		PARAMS ((tree));
-static bool may_fold_p			PARAMS ((tree));
+static latticevalue likely_value	PARAMS ((tree, int *));
 static void fold_stmt			PARAMS ((tree));
 static tree get_rhs			PARAMS ((tree));
 static void set_rhs			PARAMS ((tree, tree));
@@ -292,6 +292,9 @@ substitute_and_fold ()
 
       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 	{
+#if defined ENABLE_CHECKING
+	  tree nd_result = NULL_TREE;
+#endif
 	  tree stmt = bsi_stmt (i);
 
 	  /* Skip statements that have been folded already.  */
@@ -300,23 +303,50 @@ substitute_and_fold ()
 
 	  /* Replace the statement with its folded version and mark it
 	     folded.  */
-	  if (dump_file && (dump_flags & TDF_DETAILS))
+#if defined ENABLE_CHECKING
+	  if (likely_value (stmt, NULL) == CONSTANT)
+	    nd_result = ccp_fold (stmt);
+
+	  if (nd_result == NULL_TREE)
 	    {
-	      fprintf (dump_file, "Line %d: replaced ", get_lineno (stmt));
-	      print_generic_stmt (dump_file, stmt, TDF_SLIM);
+	      nd_result = get_rhs (stmt);
+	      if (nd_result == NULL_TREE)
+		nd_result = stmt;
 	    }
+#endif
 
 	  if (replace_uses_in (stmt))
 	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "Line %d: replaced ", get_lineno (stmt));
+		  print_generic_stmt (dump_file, stmt, TDF_SLIM);
+		}
+
 	      fold_stmt (stmt);
 	      modify_stmt (stmt);
-	    }
 
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    {
-	      fprintf (dump_file, " with ");
-	      print_generic_stmt (dump_file, stmt, TDF_SLIM);
-	      fprintf (dump_file, "\n");
+#if defined ENABLE_CHECKING
+	      {
+		tree result = get_rhs (stmt);
+		if (result)
+		  {
+		    /* Check that the destructive and non-destructive folders
+		       return the same value.  */
+		    if ((really_constant_p (nd_result)
+			 || really_constant_p (result))
+			&& simple_cst_equal (nd_result, result) != 1)
+		      abort ();
+		  }
+	      }
+#endif
+
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, " with ");
+		  print_generic_stmt (dump_file, stmt, TDF_SLIM);
+		  fprintf (dump_file, "\n");
+		}
 	    }
 	}
     }
@@ -581,10 +611,6 @@ visit_cond_stmt (stmt)
   block = bb_for_stmt (stmt);
   val = evaluate_stmt (stmt);
 
-  /* If the predicate is undefined, do nothing.  */
-  if (val.lattice_val == UNDEFINED)
-    return;
-
   /* Find which edge out of the conditional block will be taken and add it
      to the worklist.  If no single edge can be determined statically, add
      all outgoing edges from BLOCK.  */
@@ -641,10 +667,16 @@ ccp_fold (stmt)
      tree stmt;
 {
   tree rhs = get_rhs (stmt);
-  enum tree_code code = TREE_CODE (rhs);
-  int kind = TREE_CODE_CLASS (code);
+  enum tree_code code;
+  char kind;
   tree retval;
 
+  if (rhs == NULL_TREE)
+    return NULL_TREE;
+
+  code = TREE_CODE (rhs);
+  kind = TREE_CODE_CLASS (code);
+
   /* If the RHS is just a variable, then that variable must now have
      a constant value that we can return directly.  */
   if (TREE_CODE (rhs) == SSA_NAME)
@@ -686,7 +718,11 @@ ccp_fold (stmt)
 
   /* Binary and comparison operators.  We know one or both of the
      operands are constants.  */
-  else if (kind == '2' || kind == '<')
+  else if (kind == '2'
+           || kind == '<'
+           || code == TRUTH_AND_EXPR
+           || code == TRUTH_OR_EXPR
+           || code == TRUTH_XOR_EXPR)
     {
       /* Handle binary and comparison operators that can appear in
          GIMPLE form.  */
@@ -727,6 +763,43 @@ ccp_fold (stmt)
 	  && really_constant_p (op1))
 	return build (code, TREE_TYPE (rhs), op0, op1);
     }
+  else if (code == CALL_EXPR)
+    {
+      /* Check for a built-in function.  */
+      if (TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
+	  && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
+	      == FUNCTION_DECL)
+	  && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
+	{
+	  varray_type uses;
+
+	  uses = use_ops (stmt);
+	  if (uses)
+	    {
+	      tree *orig, result;
+	      size_t i;
+
+	      /* Preserve the original values of every operand.  */
+	      orig = xmalloc (sizeof (tree) * VARRAY_ACTIVE_SIZE (uses));
+	      for (i = 0; i < VARRAY_ACTIVE_SIZE (uses); i++)
+		orig[i] = *((tree *) VARRAY_GENERIC_PTR (uses, i));
+
+	      /* Substitute operands with their values and try to fold.  */
+	      replace_uses_in (stmt);
+	      result = fold_builtin (rhs);
+
+	      /* Restore operands to their original form.  */
+	      for (i = 0; i < VARRAY_ACTIVE_SIZE (uses); i++)
+		*((tree *) VARRAY_GENERIC_PTR (uses, i)) = orig[i];
+
+	      free (orig);
+
+	      if (result)
+		return result;
+	    }
+	}
+      return rhs;
+    }
   else
     return rhs;
 
@@ -748,13 +821,14 @@ evaluate_stmt (stmt)
 {
   value val;
   tree simplified;
+  int has_varying_ops;
 
-  val.lattice_val = VARYING;
+  val.lattice_val = likely_value (stmt, &has_varying_ops);
   val.const_val = NULL_TREE;
 
   /* If one or more operands has been determined to be a constant,
      then fold the expression.  */
-  if (may_fold_p (stmt))
+  if (val.lattice_val == CONSTANT)
     simplified = ccp_fold (stmt);
   else
     simplified = get_rhs (stmt);
@@ -764,6 +838,14 @@ evaluate_stmt (stmt)
       val.lattice_val = CONSTANT;
       val.const_val = simplified;
     }
+  else
+    {
+      /* If we had estimated the value to be CONSTANT but failed, set it to
+	 VARYING if the statement has at least one VARYING operand.
+	 Otherwise, set its value to UNDEFINED.  */
+      if (val.lattice_val == CONSTANT)
+	val.lattice_val = (has_varying_ops) ? VARYING : UNDEFINED;
+    }
 
   /* Debugging dumps.  */
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -957,16 +1039,12 @@ def_to_undefined (var)
   if (value->lattice_val == CONSTANT)
     abort ();
 
-  /* FIXME: Hideous hack to overcome bugs in ccp_fold() that returns
-     VARYING for expressions that will later become UNDEFINED or CONSTANT.  */
-#if 0
   /* VARYING->UNDEFINED is generally not a valid state transition,
      except for values which are initialized to VARYING.  */
   if (value->lattice_val == VARYING
       && get_default_value (var).lattice_val != VARYING)
     abort ();
 #endif
-#endif
 
   if (value->lattice_val != UNDEFINED)
     {
@@ -1031,9 +1109,6 @@ set_lattice_value (var, val)
 
           add_var_to_ssa_edges_worklist (var);
 
-  /* FIXME: Hideous hack to overcome bugs in ccp_fold() that returns
-     VARYING for expressions that will later become UNDEFINED or CONSTANT.  */
-#if 0
 #ifdef ENABLE_CHECKING
 	  /* VARYING -> CONSTANT is an invalid state transition, except
 	     for objects which start off in a VARYING state.  */
@@ -1041,7 +1116,6 @@ set_lattice_value (var, val)
 	      && get_default_value (var).lattice_val != VARYING)
 	    abort ();
 #endif
-#endif
 
 	  /* If the constant for VAR has changed, then this VAR is
 	     really varying.  */
@@ -1091,32 +1165,78 @@ replace_uses_in (stmt)
 }
 
 
-/* Return nonzero if STMT has a reasonable chance of folding into
-   something simpler.
+/* Return the likely value of STMT using the following estimates:
 
-   We consider STMT likely to fold if at least one of its operands
-   is a constant.  */
+   - If at least one operand has a CONSTANT value, the statement has a
+     reasonable chance of folding into something simpler, return CONSTANT
+     in this case.
 
-static bool
-may_fold_p (stmt)
+   - If all the operands are UNDEFINED, return UNDEFINED.
+
+   - If at least one operand is VARYING or the statement has virtual loads,
+     return VARYING.
+
+   On return, if HAS_VARYING_OPS_P is not NULL, *HAS_VARYING_OPS_P will be
+   non-zero if the statement has at least one VARYING operand.  */
+
+static latticevalue
+likely_value (stmt, has_varying_ops_p)
      tree stmt;
+     int *has_varying_ops_p;
 {
   varray_type uses;
   size_t i;
+  int may_fold;
+  latticevalue v;
+  int has_varying_ops;
 
   get_stmt_operands (stmt);
 
+  has_varying_ops = 0;
+  may_fold = 0;
   uses = use_ops (stmt);
+
+  if (uses && dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Likely value for statement: ");
+      print_generic_stmt (dump_file, stmt, TDF_SLIM);
+      fprintf (dump_file, "\n");
+    }
+
   for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
     {
       tree *use = VARRAY_GENERIC_PTR (uses, i);
       value *val = get_value (*use);
 
       if (val->lattice_val == CONSTANT)
-	return true;
+	may_fold = 1;
+      else if (val->lattice_val == VARYING)
+	has_varying_ops = 1;
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "\tVariable: ");
+	  print_generic_expr (dump_file, *use, 0);
+	  dump_lattice_value (dump_file, " -> ", *val);
+	  fprintf (dump_file, "\n");
+	}
     }
 
-  return false;
+  if (vuse_ops (stmt))
+    has_varying_ops = 1;
+
+  v = (may_fold) ? CONSTANT : (has_varying_ops) ? VARYING : UNDEFINED;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Statement's likely value: %s\n\n",
+	     (v == CONSTANT) ? "CONSTANT"
+	     : (v == UNDEFINED) ? "UNDEFINED"
+	     : "VARYING");
+
+  if (has_varying_ops_p)
+    *has_varying_ops_p = has_varying_ops;
+
+  return v;
 }