This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] ccp for V_MUST_DEF operands
- From: Brian Booth <bbooth at redhat dot com>
- To: GCC-Patches <gcc-patches at gcc dot gnu dot org>
- Cc: Diego <dnovillo at redhat dot com>
- Date: Wed, 14 Jul 2004 11:07:54 -0400
- Subject: [PATCH] ccp for V_MUST_DEF operands
Hi,
This patch enables the ccp pass to work with V_MUST_DEF operands.
One thing of note is the addition of the lattice value VIRTUAL to
represent the undefined state of a virtual operand. The current
UNDEFINED lattice value assumes that the variable it is associated with
is a local variable. The difference between these two states comes into
play when propagating the results of phi nodes. Consider the phi node
x_6 = PHI < x_2, x_5 >, where x_2 is known to be a constant and x_5 is
undefined in the function. If x is a local variable, then x_5 can be
safely ignored and x_6 will take on the constant value of x_2. However,
if x is a global variable, then we cannot say for sure that x_5 is not
defined somewhere and we cannot ignore its value. In this case, we have
to mark x as being in a state other than UNDEFINED. This is where the
VIRTUAL lattice value is needed to represent a "likely defined yet
unknown" state.
Bootstrapped and tested on i686-pc-linux-gnu. OK?
Brian
--
2004-07-13 Brian Booth <bbooth@redhat.com>
* tree-ssa-ccp.c (latticevalue): Add VIRTUAL.
(substitute_and_fold): Propagate into VUSE operands when
possible.
(visit_phi_node): Handle VIRTUAL lattice value.
(cp_lattice_meet): Handle merging of lattice values when
VIRTUAL is present.
(visit_stmt): Visit assignments with V_MUST_DEFs.
(visit_assignment): Gather ccp information for V_MUST_DEF
operands.
(ccp_fold): Deal with RHS' that are constant and virtual.
(evaluate_stmt): Handle VIRTUAL likely values.
(dump_lattice_value): Dump VIRTUAL lattice values.
(initialize): Mark statements with V_MUST_DEFs as VARYING
only if the V_MUST_DEF operand is VARYING. Fix comment and
include VOPS when computing immediate uses.
(set_lattice_value): Disallow a VIRTUAL->UNDEFINED state
transition.
(replace_vuse_in): New function.
(likely_value): Remove superfluous call to get_stmt_operands and add
check of vuse operands.
(get_default_value): Set the default value of virtually
defined variables to VIRTUAL instead of VARYING.
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-ccp.c,v
retrieving revision 2.22
diff -u -p -r2.22 tree-ssa-ccp.c
--- tree-ssa-ccp.c 11 Jul 2004 18:14:48 -0000 2.22
+++ tree-ssa-ccp.c 13 Jul 2004 15:52:27 -0000
@@ -64,6 +64,7 @@ typedef enum
{
UNINITIALIZED = 0,
UNDEFINED,
+ VIRTUAL,
CONSTANT,
VARYING
} latticevalue;
@@ -139,6 +140,7 @@ static void substitute_and_fold (void);
static value evaluate_stmt (tree);
static void dump_lattice_value (FILE *, const char *, value);
static bool replace_uses_in (tree, bool *);
+static bool replace_vuse_in (tree, bool *);
static latticevalue likely_value (tree);
static tree get_rhs (tree);
static bool set_rhs (tree *, tree);
@@ -420,7 +422,8 @@ substitute_and_fold (void)
print_generic_stmt (dump_file, stmt, TDF_SLIM);
}
- if (replace_uses_in (stmt, &replaced_address))
+ if (replace_uses_in (stmt, &replaced_address)
+ || replace_vuse_in (stmt, &replaced_address))
{
bool changed = fold_stmt (bsi_stmt_ptr (i));
stmt = bsi_stmt(i);
@@ -482,6 +485,11 @@ visit_phi_node (tree phi)
phi_val = *curr_val;
break;
+ case VIRTUAL:
+ phi_val.lattice_val = VIRTUAL;
+ phi_val.const_val = NULL_TREE;
+ break;
+
case UNDEFINED:
case UNINITIALIZED:
phi_val.lattice_val = UNDEFINED;
@@ -558,10 +566,12 @@ visit_phi_node (tree phi)
/* Compute the meet operator between VAL1 and VAL2:
- any M UNDEFINED = any
- any M VARYING = VARYING
- Ci M Cj = Ci if (i == j)
- Ci M Cj = VARYING if (i != j) */
+ any M UNDEFINED = any
+ any M VARYING = VARYING
+ VIRTUAL M VIRTUAL = VIRTUAL
+ any M VIRTUAL = VARYING
+ Ci M Cj = Ci if (i == j)
+ Ci M Cj = VARYING if (i != j) */
static value
cp_lattice_meet (value val1, value val2)
{
@@ -581,6 +591,22 @@ cp_lattice_meet (value val1, value val2)
return result;
}
+ /* VIRTUAL M VIRTUAL = VIRTUAL. */
+ if (val1.lattice_val == VIRTUAL && val2.lattice_val == VIRTUAL)
+ {
+ result.lattice_val = VIRTUAL;
+ result.const_val = NULL_TREE;
+ return result;
+ }
+
+ /* any M UNKNOWN = VARYING. */
+ if (val1.lattice_val == VIRTUAL || val2.lattice_val == VIRTUAL)
+ {
+ result.lattice_val = VARYING;
+ result.const_val = NULL_TREE;
+ return result;
+ }
+
/* Ci M Cj = Ci if (i == j)
Ci M Cj = VARYING if (i != j) */
if (simple_cst_equal (val1.const_val, val2.const_val) == 1)
@@ -617,7 +643,6 @@ visit_stmt (tree stmt)
stmt_ann_t ann;
def_optype defs;
v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
/* If the statement has already been deemed to be VARYING, don't simulate
it again. */
@@ -643,8 +668,9 @@ visit_stmt (tree stmt)
/* Now examine the statement. If the statement is an assignment that
produces a single output value, evaluate its RHS to see if the lattice
value of its output has changed. */
+ v_may_defs = V_MAY_DEF_OPS (ann);
if (TREE_CODE (stmt) == MODIFY_EXPR
- && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
+ && NUM_V_MAY_DEFS (v_may_defs) == 0)
visit_assignment (stmt);
/* Definitions made by statements other than assignments to SSA_NAMEs
@@ -677,14 +703,9 @@ visit_stmt (tree stmt)
}
/* Mark all V_MAY_DEF operands VARYING. */
- v_may_defs = V_MAY_DEF_OPS (ann);
for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
def_to_varying (V_MAY_DEF_RESULT (v_may_defs, i));
- /* Mark all V_MUST_DEF operands VARYING. */
- v_must_defs = V_MUST_DEF_OPS (ann);
- for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
- def_to_varying (V_MUST_DEF_OP (v_must_defs, i));
}
@@ -695,14 +716,45 @@ static void
visit_assignment (tree stmt)
{
value val;
- tree lhs, rhs;
+ tree lhs, rhs, lhs_ssa_name = NULL_TREE;
+ vuse_optype vuses;
lhs = TREE_OPERAND (stmt, 0);
rhs = TREE_OPERAND (stmt, 1);
+ vuses = STMT_VUSE_OPS (stmt);
+
+ /* We require the SSA version number of the lhs for the value_vector.
+ Make sure we have it. */
+ if (TREE_CODE (lhs) == SSA_NAME)
+ {
+ lhs_ssa_name = lhs;
+ lhs = SSA_NAME_VAR (lhs);
+ }
+ else if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) == 0)
+ /* Ignore variables with hidden uses and volatile variables.
+ They do not have a SSA version number and are not of interest.
+ Also avoid any partial definitions of these variables. */;
+ else
+ {
+ /* If we make it here, stmt should only have one virtual definition:
+ a V_MUST_DEF. */
+
+ v_must_def_optype v_must_defs;
+ v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
+
+#if defined ENABLE_CHECKING
+ if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0
+ || NUM_V_MUST_DEFS (v_must_defs) != 1)
+ abort ();
+#endif
- if (TREE_THIS_VOLATILE (SSA_NAME_VAR (lhs)))
+ lhs_ssa_name = V_MUST_DEF_OP (v_must_defs, 0);
+ }
+
+ if (lhs_ssa_name == NULL_TREE)
{
- /* Volatile variables are always VARYING. */
+ /* Volatile variables, variables with hidden uses, and any
+ varyants thereof are always VARYING. */
val.lattice_val = VARYING;
val.const_val = NULL_TREE;
}
@@ -711,6 +763,20 @@ visit_assignment (tree stmt)
/* For a simple copy operation, we copy the lattice values. */
value *nval = get_value (rhs);
val = *nval;
+
+ /* If lhs is not a gimple register, then it cannot take on
+ an undefined value. */
+ if (!is_gimple_reg (lhs) && val.lattice_val == UNDEFINED)
+ val.lattice_val = VIRTUAL;
+ }
+ else if (DECL_P (rhs)
+ && NUM_VUSES (vuses) == 1
+ && operand_equal_p (rhs, SSA_NAME_VAR (VUSE_OP (vuses, 0)), 0))
+ {
+ /* Same as above, but the rhs is not a gimple register and yet
+ has a known VUSE. */
+ value *nval = get_value (VUSE_OP (vuses, 0));
+ val = *nval;
}
else
{
@@ -740,9 +806,13 @@ visit_assignment (tree stmt)
}
/* Set the lattice value of the statement's output. */
- set_lattice_value (lhs, val);
- if (val.lattice_val == VARYING)
- DONT_SIMULATE_AGAIN (stmt) = 1;
+ if (lhs_ssa_name != NULL_TREE)
+ {
+ set_lattice_value (lhs_ssa_name, val);
+ if (val.lattice_val == VARYING)
+ DONT_SIMULATE_AGAIN (stmt) = 1;
+ }
+
}
@@ -827,11 +897,18 @@ ccp_fold (tree stmt)
enum tree_code code = TREE_CODE (rhs);
int kind = TREE_CODE_CLASS (code);
tree retval = NULL_TREE;
+ vuse_optype vuses;
+
+ vuses = STMT_VUSE_OPS (stmt);
/* 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)
return get_value (rhs)->const_val;
+ else if (DECL_P (rhs)
+ && NUM_VUSES (vuses) == 1
+ && operand_equal_p (rhs, SSA_NAME_VAR (VUSE_OP (vuses, 0)), 0))
+ return get_value (VUSE_OP (vuses, 0))->const_val;
/* Unary operators. Note that we know the single operand must
be a constant. So this should almost always return a
@@ -1001,9 +1078,11 @@ evaluate_stmt (tree stmt)
else
{
/* The statement produced a nonconstant value. If the statement
- had undefined operands, then the result of the statement should
- be undefined. Else the result of the statement is VARYING. */
+ had undefined or virtual operands, then the result of the
+ statement should be undefined or virtual respectively.
+ Else the result of the statement is VARYING. */
val.lattice_val = (likelyvalue == UNDEFINED ? UNDEFINED : VARYING);
+ val.lattice_val = (likelyvalue == VIRTUAL ? VIRTUAL : val.lattice_val);
val.const_val = NULL_TREE;
}
@@ -1024,6 +1103,9 @@ dump_lattice_value (FILE *outf, const ch
case VARYING:
fprintf (outf, "%sVARYING", prefix);
break;
+ case VIRTUAL:
+ fprintf (outf, "%sVIRTUAL", prefix);
+ break;
case CONSTANT:
fprintf (outf, "%sCONSTANT ", prefix);
print_generic_expr (outf, val.const_val, dump_flags);
@@ -1157,6 +1239,16 @@ initialize (void)
if (get_value (def)->lattice_val == VARYING)
vary = 1;
}
+
+ /* Det the default value for each V_MUST_DEF. */
+ v_must_defs = V_MUST_DEF_OPS (ann);
+ for (x = 0; x < NUM_V_MUST_DEFS (v_must_defs); x++)
+ {
+ tree v_must_def = V_MUST_DEF_OP (v_must_defs, x);
+ if (get_value (v_must_def)->lattice_val == VARYING)
+ vary = 1;
+ }
+
DONT_SIMULATE_AGAIN (stmt) = vary;
/* Mark all V_MAY_DEF operands VARYING. */
@@ -1167,15 +1259,6 @@ initialize (void)
get_value (res)->lattice_val = VARYING;
SET_BIT (virtual_var, SSA_NAME_VERSION (res));
}
-
- /* Mark all V_MUST_DEF operands VARYING. */
- v_must_defs = V_MUST_DEF_OPS (ann);
- for (x = 0; x < NUM_V_MUST_DEFS (v_must_defs); x++)
- {
- tree v_must_def = V_MUST_DEF_OP (v_must_defs, x);
- get_value (v_must_def)->lattice_val = VARYING;
- SET_BIT (virtual_var, SSA_NAME_VERSION (v_must_def));
- }
}
for (e = bb->succ; e; e = e->succ_next)
@@ -1196,8 +1279,8 @@ initialize (void)
for (x = 0; x < PHI_NUM_ARGS (phi); x++)
{
var = PHI_ARG_DEF (phi, x);
- /* If one argument is virtual, the result is virtual, and
- therefore varying. */
+ /* If one argument has a V_MAY_DEF,
+ the result is varying. */
if (TREE_CODE (var) == SSA_NAME)
{
if (TEST_BIT (virtual_var, SSA_NAME_VERSION (var)))
@@ -1216,7 +1299,7 @@ initialize (void)
sbitmap_free (virtual_var);
/* Compute immediate uses for variables we care about. */
- compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
+ compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, need_imm_uses_for);
if (dump_file && (dump_flags & TDF_DETAILS))
dump_immediate_uses (dump_file);
@@ -1366,6 +1449,10 @@ set_lattice_value (tree var, value val)
/* CONSTANT->UNDEFINED is never a valid state transition. */
if (old->lattice_val == CONSTANT)
abort ();
+
+ /* VIRTUAL->UNDEFINED is never a valid state transition. */
+ if (old->lattice_val == VIRTUAL)
+ abort ();
/* VARYING->UNDEFINED is generally not a valid state transition,
except for values which are initialized to VARYING. */
@@ -1441,6 +1528,48 @@ replace_uses_in (tree stmt, bool *replac
return replaced;
}
+/* Replace the VUSE references in statement STMT with its immediate reaching
+ definition. Return true if the reference was replaced. If
+ REPLACED_ADDRESSES_P is given, it will be set to true if an address
+ constant was replaced. */
+
+static bool
+replace_vuse_in (tree stmt, bool *replaced_addresses_p)
+{
+ bool replaced = false;
+ vuse_optype vuses;
+ use_operand_p vuse;
+ value *val;
+
+ if (replaced_addresses_p)
+ *replaced_addresses_p = false;
+
+ get_stmt_operands (stmt);
+
+ vuses = STMT_VUSE_OPS (stmt);
+
+ if (NUM_VUSES (vuses) != 1)
+ return false;
+
+ vuse = VUSE_OP_PTR (vuses, 0);
+ val = get_value (USE_FROM_PTR (vuse));
+
+ if (val->lattice_val == CONSTANT
+ && TREE_CODE (stmt) == MODIFY_EXPR
+ && DECL_P (TREE_OPERAND (stmt, 1))
+ && operand_equal_p (TREE_OPERAND (stmt, 1),
+ SSA_NAME_VAR (USE_FROM_PTR (vuse)), 0))
+ {
+ TREE_OPERAND (stmt, 1) = val->const_val;
+ replaced = true;
+ if (POINTER_TYPE_P (TREE_TYPE (USE_FROM_PTR (vuse)))
+ && replaced_addresses_p)
+ *replaced_addresses_p = true;
+ }
+
+ return replaced;
+}
+
/* Return the likely latticevalue for STMT.
If STMT has no operands, then return CONSTANT.
@@ -1455,6 +1584,7 @@ static latticevalue
likely_value (tree stmt)
{
use_optype uses;
+ vuse_optype vuses;
size_t i;
int found_constant = 0;
stmt_ann_t ann;
@@ -1470,8 +1600,6 @@ likely_value (tree stmt)
if (get_call_expr_in (stmt) != NULL_TREE)
return VARYING;
- get_stmt_operands (stmt);
-
uses = USE_OPS (ann);
for (i = 0; i < NUM_USES (uses); i++)
{
@@ -1484,8 +1612,34 @@ likely_value (tree stmt)
if (val->lattice_val == CONSTANT)
found_constant = 1;
}
+
+ vuses = VUSE_OPS (ann);
+
+#ifdef ENABLE_CHECKING
+ /* There should be no alias loads by this point. */
+ if (NUM_VUSES (vuses) > 1)
+ abort ();
+#endif
+
+ if (NUM_VUSES (vuses))
+ {
+ tree vuse = VUSE_OP (vuses, 0);
+ value *val = get_value (vuse);
+
+ if (val->lattice_val == VIRTUAL)
+ return VIRTUAL;
+
+#ifdef ENABLE_CHECKING
+ /* There should be no VUSE operands that are UNDEFINED. */
+ if (val->lattice_val == UNDEFINED)
+ abort ();
+#endif
+
+ if (val->lattice_val == CONSTANT)
+ found_constant = 1;
+ }
- return ((found_constant || !uses) ? CONSTANT : VARYING);
+ return ((found_constant || (!uses && !vuses)) ? CONSTANT : VARYING);
}
/* A subroutine of fold_stmt_r. Attempts to fold *(A+O) to A[X].
@@ -2208,12 +2362,14 @@ set_rhs (tree *stmt_p, tree expr)
/* Return a default value for variable VAR using the following rules:
- 1- Global and static variables are considered VARYING, unless they are
- declared const.
+ 1- Function arguments are considered VARYING.
+
+ 2- Global and static variables that are declared constant are
+ considered CONSTANT.
- 2- Function arguments are considered VARYING.
+ 3- Any other virtually defined variable is considered VIRTUAL.
- 3- Any other value is considered UNDEFINED. This is useful when
+ 4- Any other value is considered UNDEFINED. This is useful when
considering PHI nodes. PHI arguments that are undefined do not
change the constant value of the PHI node, which allows for more
constants to be propagated. */
@@ -2246,10 +2402,9 @@ get_default_value (tree var)
else if (decl_function_context (sym) != current_function_decl
|| TREE_STATIC (sym))
{
- /* Globals and static variables are considered VARYING, unless they
- are declared 'const'. */
- val.lattice_val = VARYING;
-
+ /* Globals and static variables are considered CONSTANT. if they
+ are declared 'const', we use save their value into const_val.
+ Otherwise, we save the VAR_DECL */
if (TREE_READONLY (sym)
&& DECL_INITIAL (sym)
&& is_gimple_min_invariant (DECL_INITIAL (sym)))
@@ -2257,6 +2412,16 @@ get_default_value (tree var)
val.lattice_val = CONSTANT;
val.const_val = DECL_INITIAL (sym);
}
+ else
+ {
+ val.const_val = NULL_TREE;
+ val.lattice_val = VIRTUAL;
+ }
+ }
+ else if (!is_gimple_reg (sym))
+ {
+ val.const_val = NULL_TREE;
+ val.lattice_val = VIRTUAL;
}
else
{