This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] CCP and non-destructive folding problems
- From: Diego Novillo <dnovillo at redhat dot com>
- To: Jeff Law <law at redhat dot com>
- Cc: gcc at gcc dot gnu dot org
- Date: Tue, 25 Feb 2003 10:27:22 -0500
- Subject: [tree-ssa] CCP and non-destructive folding problems
- Organization: Red Hat Canada
My recent change to the flowgraph exposed a couple of problems in
CCP:
(1) ccp_fold() and fold() are not always returning the same
value. For instance, strlen("abc") is folded to 3 by
fold(), but not folded by ccp_fold().
(2) The evaluation of statements (evaluate_stmt) always returns
VARYING when it can't fold it. Suppose that evaluate_stmt is
called with 'a_1 = b_2 + 3;'.
If 'b_2' has an UNDEFINED value at the time, evaluate_stmt
will return VARYING. If at a later iteration b_2 becomes
CONSTANT, then we will have a VARYING->CONSTANT transition.
The attached patch started as a fix for (2). Now, evaluate_stmt
will return UNDEFINED when the expression has a chance of
becoming CONSTANT at a later time. However, this exposes a bug
in the non-destructive folder. Returning UNDEFINED is a
dangerous proposition because of the optimistic evaluation of PHI
nodes. Suppose we have the following code:
1 p_1 = "abcdef";
2 while (1)
3 {
4 p_2 = PHI (p_1, p_3);
5 if (...)
6 break;
7 ...
8 p_3 = p_2 + 1;
9 }
When CCP visits the PHI expression at line 4 for the first time,
it determines that p_1 has a CONSTANT value and, since p_3 comes
from an unexecutable edge, it has an UNDEFINED value. Therefore,
it assigns p_2 the CONSTANT value "abcdef".
We then get to the assignment at line 8. Since p_2 is "abcdef",
we call the non-destructive fold, which can't handle "abcdef" + 1
and returns the expression unmodified. Since all the operands of
the expression are constants, evaluate_stmt() returns UNDEFINED
because it thinks the evaluation may fold at a later time.
Since the lattice value for line 8 didn't change, we end the CCP
pass with
1 p_1 = "abcdef";
2 while (1)
3 {
4 p_2 = PHI ("abcdef", UNDEFINED);
5 if (...)
6 break;
7 ...
8 p_3 = "abcdef" + 1;
9 }
which is then folded at the end to:
1 p_1 = "abcdef";
2 while (1)
3 {
4 p_2 = "abcdef";
5 if (...)
6 break;
7 ...
8 p_3 = "bcdef";
9 }
Oops. This means that:
(a) evaluate_stmt() has to be careful when returning UNDEFINED.
The optimistic evaluation of PHI nodes may cause problems
like the one above. I fixed this particular one by copying
more code from the destructive folder into the
non-destructive folder.
(b) The non-destructive and destructive folders must always
return the same values. I've added a (moderately expensive)
check for this in the final fold pass.
I don't like the direction where this is taking us. We have two
different implementations of fold() with quite a bit of code
duplication. It's a maintenance problem. We *really* need to
sit down and re-design fold(). We have three parameters:
- Need a non-destructive fold mechanism.
- Need to have an efficient implementation that can make
simplifying assumptions when dealing with GIMPLE trees.
- Need to share more code so that we don't have the problems we
are having now with two diverging implementations.
It may make sense to write fold() in terms of the non-destructive
fold. Jeff, do you have anything in mind regarding this problem?
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 03:09:34 -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 03:09:34 -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 03:09:34 -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.54
diff -d -u -p -r1.1.2.54 tree-ssa-ccp.c
--- tree-ssa-ccp.c 19 Feb 2003 21:17:23 -0000 1.1.2.54
+++ tree-ssa-ccp.c 25 Feb 2003 03:09:34 -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,14 +821,26 @@ 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))
- simplified = ccp_fold (stmt);
+ if (val.lattice_val == CONSTANT)
+ {
+ /* FIXME. Hideous hack to work around nondestructive fold bug. */
+ if (0)
+ simplified = ccp_fold (stmt);
+ else
+ {
+ tree copy = copy_stmt (stmt);
+ replace_uses_in (copy);
+ fold_stmt (copy);
+ simplified = get_rhs (copy);
+ }
+ }
else
simplified = get_rhs (stmt);
@@ -764,6 +849,19 @@ evaluate_stmt (stmt)
val.lattice_val = CONSTANT;
val.const_val = simplified;
}
+ else
+ {
+ /* FIXME. Hideous hack to work around bootstrapping problems. By
+ setting the value to UNDEFINED we are miscompiling calls.o. */
+#if 0
+ /* 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;
+#endif
+ val.lattice_val = VARYING;
+ }
/* Debugging dumps. */
if (dump_file && (dump_flags & TDF_DETAILS))
@@ -959,10 +1057,14 @@ def_to_undefined (var)
/* VARYING->UNDEFINED is generally not a valid state transition,
except for values which are initialized to VARYING. */
+ /* FIXME. Hideous hack to work around bootstrapping problems. See note
+ in eval_stmt(). */
+#if 0
if (value->lattice_val == VARYING
&& get_default_value (var).lattice_val != VARYING)
abort ();
#endif
+#endif
if (value->lattice_val != UNDEFINED)
{
@@ -1030,10 +1132,14 @@ set_lattice_value (var, val)
#ifdef ENABLE_CHECKING
/* VARYING -> CONSTANT is an invalid state transition, except
for objects which start off in a VARYING state. */
+ /* FIXME. Hideous hack to work around bootstrapping problems.
+ See note in eval_stmt(). */
+#if 0
if (old_val->lattice_val == VARYING
&& get_default_value (var).lattice_val != VARYING)
abort ();
#endif
+#endif
/* If the constant for VAR has changed, then this VAR is
really varying. */
@@ -1083,32 +1189,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;
}