This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 4 Aug 2010 14:22:05 +0200 (CEST)
- Subject: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs
This is one more preparation for bit-CCP, make the lattice fully
abstract in the propagator and query it via a callback in
substitute_and_fold. This patch also makes us do less work
substituting and folding by doing a walk over all SSA names first
and replacing their definition with the value from the lattice.
Bootstrapped and tested on x86_64-unknown-linux-gnu. c52102b
and c52102d now fail, because they rely on undefined signed integer
overflow.
Committed to trunk.
Richard.
2010-08-04 Richard Guenther <rguenther@suse.de>
* tree-ssa-propagate.h (struct prop_value_d, prop_value_t): Move ...
* tree-ssa-ccp.c: ... here.
* tree-ssa-copy.c: ... and here.
* tree-ssa-propagate.h (enum value_range_type, struct value_range_d,
value_range_t): Move ...
* tree-vrp.c: ... here.
* tree-ssa-propagate.h (ssa_prop_get_value_fn): New typedef.
(substitute_and_fold): Adjust prototype.
* tree-ssa-propagate.c (replace_uses_in): Adjust.
(replace_phi_args_in): Likewise.
(substitute_and_fold): Take callback to query lattice instead
of pointer to lattice. Replace SSA name defs with lattice
values first.
* tree-ssa-ccp.c (ccp_finalize): Adjust.
* tree-ssa-copy.c (copy_prop_visit_phi_node): Adjust.
(get_value): New function.
(fini_copy_prop): Adjust.
* tree-vrp.c (vrp_finalize): Adjust.
* gcc.dg/tree-ssa/vrp35.c: Adjust.
* gcc.dg/tree-ssa/vrp36.c: Likewise.
* gcc.dg/tree-ssa/vrp50.c: Likewise.
* gcc.dg/tree-ssa/vrp52.c: Likewise.
Index: trunk/gcc/tree-ssa-ccp.c
===================================================================
*** trunk.orig/gcc/tree-ssa-ccp.c 2010-08-03 16:12:40.000000000 +0200
--- trunk/gcc/tree-ssa-ccp.c 2010-08-03 16:17:23.000000000 +0200
*************** typedef enum
*** 144,149 ****
--- 144,159 ----
VARYING
} ccp_lattice_t;
+ struct prop_value_d {
+ /* Lattice value. */
+ ccp_lattice_t lattice_val;
+
+ /* Propagated value. */
+ tree value;
+ };
+
+ typedef struct prop_value_d prop_value_t;
+
/* Array of propagated constant values. After propagation,
CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If
the constant is held in an SSA name representing a memory store
*************** ccp_finalize (void)
*** 645,651 ****
do_dbg_cnt ();
/* Perform substitutions based on the known constant values. */
! something_changed = substitute_and_fold (const_val, ccp_fold_stmt, true);
free (const_val);
const_val = NULL;
--- 655,662 ----
do_dbg_cnt ();
/* Perform substitutions based on the known constant values. */
! something_changed = substitute_and_fold (get_constant_value,
! ccp_fold_stmt, true);
free (const_val);
const_val = NULL;
Index: trunk/gcc/tree-ssa-copy.c
===================================================================
*** trunk.orig/gcc/tree-ssa-copy.c 2010-08-03 16:12:40.000000000 +0200
--- trunk/gcc/tree-ssa-copy.c 2010-08-03 16:17:23.000000000 +0200
*************** propagate_tree_value_into_stmt (gimple_s
*** 285,290 ****
--- 285,298 ----
After propagation, the copy-of value for each variable X_i is
converted into the final value by walking the copy-of chains and
updating COPY_OF[i].VALUE to be the last element of the chain. */
+
+ struct prop_value_d {
+ /* Copy-of value. */
+ tree value;
+ };
+
+ typedef struct prop_value_d prop_value_t;
+
static prop_value_t *copy_of;
/* Used in set_copy_of_val to determine if the last link of a copy-of
*************** copy_prop_visit_phi_node (gimple phi)
*** 626,632 ****
{
enum ssa_prop_result retval;
unsigned i;
! prop_value_t phi_val = { 0, NULL_TREE };
tree lhs = gimple_phi_result (phi);
--- 634,640 ----
{
enum ssa_prop_result retval;
unsigned i;
! prop_value_t phi_val = { NULL_TREE };
tree lhs = gimple_phi_result (phi);
*************** init_copy_prop (void)
*** 818,823 ****
--- 826,841 ----
}
}
+ /* Callback for substitute_and_fold to get at the final copy-of values. */
+
+ static tree
+ get_value (tree name)
+ {
+ tree val = copy_of[SSA_NAME_VERSION (name)].value;
+ if (val && val != name)
+ return val;
+ return NULL_TREE;
+ }
/* Deallocate memory used in copy propagation and do final
substitution. */
*************** init_copy_prop (void)
*** 825,836 ****
static void
fini_copy_prop (void)
{
! size_t i;
! prop_value_t *tmp;
/* Set the final copy-of value for each variable by traversing the
copy-of chains. */
- tmp = XCNEWVEC (prop_value_t, num_ssa_names);
for (i = 1; i < num_ssa_names; i++)
{
tree var = ssa_name (i);
--- 843,852 ----
static void
fini_copy_prop (void)
{
! unsigned i;
/* Set the final copy-of value for each variable by traversing the
copy-of chains. */
for (i = 1; i < num_ssa_names; i++)
{
tree var = ssa_name (i);
*************** fini_copy_prop (void)
*** 839,845 ****
|| copy_of[i].value == var)
continue;
! tmp[i].value = get_last_copy_of (var);
/* In theory the points-to solution of all members of the
copy chain is their intersection. For now we do not bother
--- 855,861 ----
|| copy_of[i].value == var)
continue;
! copy_of[i].value = get_last_copy_of (var);
/* In theory the points-to solution of all members of the
copy chain is their intersection. For now we do not bother
*************** fini_copy_prop (void)
*** 847,864 ****
information completely by setting the points-to solution
of the representative to the first solution we find if
it doesn't have one already. */
! if (tmp[i].value != var
&& POINTER_TYPE_P (TREE_TYPE (var))
&& SSA_NAME_PTR_INFO (var)
! && !SSA_NAME_PTR_INFO (tmp[i].value))
! duplicate_ssa_name_ptr_info (tmp[i].value, SSA_NAME_PTR_INFO (var));
}
! substitute_and_fold (tmp, NULL, true);
free (cached_last_copy_of);
free (copy_of);
- free (tmp);
}
--- 863,879 ----
information completely by setting the points-to solution
of the representative to the first solution we find if
it doesn't have one already. */
! if (copy_of[i].value != var
&& POINTER_TYPE_P (TREE_TYPE (var))
&& SSA_NAME_PTR_INFO (var)
! && !SSA_NAME_PTR_INFO (copy_of[i].value))
! duplicate_ssa_name_ptr_info (copy_of[i].value, SSA_NAME_PTR_INFO (var));
}
! substitute_and_fold (get_value, NULL, true);
free (cached_last_copy_of);
free (copy_of);
}
Index: trunk/gcc/tree-ssa-propagate.c
===================================================================
*** trunk.orig/gcc/tree-ssa-propagate.c 2010-08-03 16:12:40.000000000 +0200
--- trunk/gcc/tree-ssa-propagate.c 2010-08-04 10:22:27.000000000 +0200
*************** static struct prop_stats_d prop_stats;
*** 872,878 ****
PROP_VALUE. Return true if at least one reference was replaced. */
static bool
! replace_uses_in (gimple stmt, prop_value_t *prop_value)
{
bool replaced = false;
use_operand_p use;
--- 872,878 ----
PROP_VALUE. Return true if at least one reference was replaced. */
static bool
! replace_uses_in (gimple stmt, ssa_prop_get_value_fn get_value)
{
bool replaced = false;
use_operand_p use;
*************** replace_uses_in (gimple stmt, prop_value
*** 881,887 ****
FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
tree tuse = USE_FROM_PTR (use);
! tree val = prop_value[SSA_NAME_VERSION (tuse)].value;
if (val == tuse || val == NULL_TREE)
continue;
--- 881,887 ----
FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
tree tuse = USE_FROM_PTR (use);
! tree val = (*get_value) (tuse);
if (val == tuse || val == NULL_TREE)
continue;
*************** replace_uses_in (gimple stmt, prop_value
*** 911,917 ****
values from PROP_VALUE. */
static void
! replace_phi_args_in (gimple phi, prop_value_t *prop_value)
{
size_t i;
bool replaced = false;
--- 911,917 ----
values from PROP_VALUE. */
static void
! replace_phi_args_in (gimple phi, ssa_prop_get_value_fn get_value)
{
size_t i;
bool replaced = false;
*************** replace_phi_args_in (gimple phi, prop_va
*** 928,934 ****
if (TREE_CODE (arg) == SSA_NAME)
{
! tree val = prop_value[SSA_NAME_VERSION (arg)].value;
if (val && val != arg && may_propagate_copy (arg, val))
{
--- 928,934 ----
if (TREE_CODE (arg) == SSA_NAME)
{
! tree val = (*get_value) (arg);
if (val && val != arg && may_propagate_copy (arg, val))
{
*************** replace_phi_args_in (gimple phi, prop_va
*** 978,990 ****
Return TRUE when something changed. */
bool
! substitute_and_fold (prop_value_t *prop_value, ssa_prop_fold_stmt_fn fold_fn,
bool do_dce)
{
basic_block bb;
bool something_changed = false;
! if (prop_value == NULL && !fold_fn)
return false;
if (dump_file && (dump_flags & TDF_DETAILS))
--- 978,992 ----
Return TRUE when something changed. */
bool
! substitute_and_fold (ssa_prop_get_value_fn get_value_fn,
! ssa_prop_fold_stmt_fn fold_fn,
bool do_dce)
{
basic_block bb;
bool something_changed = false;
+ unsigned i;
! if (!get_value_fn && !fold_fn)
return false;
if (dump_file && (dump_flags & TDF_DETAILS))
*************** substitute_and_fold (prop_value_t *prop_
*** 992,1006 ****
memset (&prop_stats, 0, sizeof (prop_stats));
! /* Substitute values in every statement of every basic block. */
FOR_EACH_BB (bb)
{
gimple_stmt_iterator i;
/* Propagate known values into PHI nodes. */
! if (prop_value)
for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
! replace_phi_args_in (gsi_stmt (i), prop_value);
/* Propagate known values into stmts. Do a backward walk to expose
more trivially deletable stmts. */
--- 994,1059 ----
memset (&prop_stats, 0, sizeof (prop_stats));
! /* Substitute lattice values at definition sites. */
! if (get_value_fn)
! for (i = 1; i < num_ssa_names; ++i)
! {
! tree name = ssa_name (i);
! tree val;
! gimple def_stmt;
! gimple_stmt_iterator gsi;
!
! if (!name
! || !is_gimple_reg (name))
! continue;
!
! def_stmt = SSA_NAME_DEF_STMT (name);
! if (gimple_nop_p (def_stmt)
! /* Do not substitute ASSERT_EXPR rhs, this will confuse VRP. */
! || (gimple_assign_single_p (def_stmt)
! && gimple_assign_rhs_code (def_stmt) == ASSERT_EXPR)
! || !(val = (*get_value_fn) (name))
! || !may_propagate_copy (name, val))
! continue;
!
! gsi = gsi_for_stmt (def_stmt);
! if (is_gimple_assign (def_stmt))
! {
! gimple_assign_set_rhs_with_ops (&gsi, TREE_CODE (val),
! val, NULL_TREE);
! gcc_assert (gsi_stmt (gsi) == def_stmt);
! if (maybe_clean_eh_stmt (def_stmt))
! gimple_purge_dead_eh_edges (gimple_bb (def_stmt));
! update_stmt (def_stmt);
! }
! else if (is_gimple_call (def_stmt))
! {
! if (update_call_from_tree (&gsi, val)
! && maybe_clean_or_replace_eh_stmt (def_stmt, gsi_stmt (gsi)))
! gimple_purge_dead_eh_edges (gimple_bb (gsi_stmt (gsi)));
! }
! else if (gimple_code (def_stmt) == GIMPLE_PHI)
! {
! gimple new_stmt = gimple_build_assign (name, val);
! gimple_stmt_iterator gsi2;
! SSA_NAME_DEF_STMT (name) = new_stmt;
! gsi2 = gsi_after_labels (gimple_bb (def_stmt));
! gsi_insert_before (&gsi2, new_stmt, GSI_SAME_STMT);
! remove_phi_node (&gsi, false);
! }
!
! something_changed = true;
! }
!
! /* Propagate into all uses and fold. */
FOR_EACH_BB (bb)
{
gimple_stmt_iterator i;
/* Propagate known values into PHI nodes. */
! if (get_value_fn)
for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
! replace_phi_args_in (gsi_stmt (i), get_value_fn);
/* Propagate known values into stmts. Do a backward walk to expose
more trivially deletable stmts. */
*************** substitute_and_fold (prop_value_t *prop_
*** 1073,1081 ****
/* Only replace real uses if we couldn't fold the
statement using value range information. */
! if (prop_value
&& !did_replace)
! did_replace |= replace_uses_in (stmt, prop_value);
/* If we made a replacement, fold the statement. */
if (did_replace)
--- 1126,1134 ----
/* Only replace real uses if we couldn't fold the
statement using value range information. */
! if (get_value_fn
&& !did_replace)
! did_replace |= replace_uses_in (stmt, get_value_fn);
/* If we made a replacement, fold the statement. */
if (did_replace)
Index: trunk/gcc/tree-ssa-propagate.h
===================================================================
*** trunk.orig/gcc/tree-ssa-propagate.h 2010-08-03 16:12:40.000000000 +0200
--- trunk/gcc/tree-ssa-propagate.h 2010-08-03 16:17:23.000000000 +0200
*************** enum ssa_prop_result {
*** 61,116 ****
};
- struct prop_value_d {
- /* Lattice value. Each propagator is free to define its own
- lattice and this field is only meaningful while propagating.
- It will not be used by substitute_and_fold. */
- unsigned lattice_val;
-
- /* Propagated value. */
- tree value;
- };
-
- typedef struct prop_value_d prop_value_t;
-
-
- /* Type of value ranges. See value_range_d for a description of these
- types. */
- enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
-
- /* Range of values that can be associated with an SSA_NAME after VRP
- has executed. */
- struct value_range_d
- {
- /* Lattice value represented by this range. */
- enum value_range_type type;
-
- /* Minimum and maximum values represented by this range. These
- values should be interpreted as follows:
-
- - If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must
- be NULL.
-
- - If TYPE == VR_RANGE then MIN holds the minimum value and
- MAX holds the maximum value of the range [MIN, MAX].
-
- - If TYPE == ANTI_RANGE the variable is known to NOT
- take any values in the range [MIN, MAX]. */
- tree min;
- tree max;
-
- /* Set of SSA names whose value ranges are equivalent to this one.
- This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */
- bitmap equiv;
- };
-
- typedef struct value_range_d value_range_t;
-
-
/* Call-back functions used by the value propagation engine. */
typedef enum ssa_prop_result (*ssa_prop_visit_stmt_fn) (gimple, edge *, tree *);
typedef enum ssa_prop_result (*ssa_prop_visit_phi_fn) (gimple);
typedef bool (*ssa_prop_fold_stmt_fn) (gimple_stmt_iterator *gsi);
/* In tree-ssa-propagate.c */
--- 61,71 ----
};
/* Call-back functions used by the value propagation engine. */
typedef enum ssa_prop_result (*ssa_prop_visit_stmt_fn) (gimple, edge *, tree *);
typedef enum ssa_prop_result (*ssa_prop_visit_phi_fn) (gimple);
typedef bool (*ssa_prop_fold_stmt_fn) (gimple_stmt_iterator *gsi);
+ typedef tree (*ssa_prop_get_value_fn) (tree);
/* In tree-ssa-propagate.c */
*************** bool valid_gimple_rhs_p (tree);
*** 119,124 ****
void move_ssa_defining_stmt_for_defs (gimple, gimple);
bool update_call_from_tree (gimple_stmt_iterator *, tree);
bool stmt_makes_single_store (gimple);
! bool substitute_and_fold (prop_value_t *, ssa_prop_fold_stmt_fn, bool);
#endif /* _TREE_SSA_PROPAGATE_H */
--- 74,79 ----
void move_ssa_defining_stmt_for_defs (gimple, gimple);
bool update_call_from_tree (gimple_stmt_iterator *, tree);
bool stmt_makes_single_store (gimple);
! bool substitute_and_fold (ssa_prop_get_value_fn, ssa_prop_fold_stmt_fn, bool);
#endif /* _TREE_SSA_PROPAGATE_H */
Index: trunk/gcc/tree-vrp.c
===================================================================
*** trunk.orig/gcc/tree-vrp.c 2010-08-03 16:12:40.000000000 +0200
--- trunk/gcc/tree-vrp.c 2010-08-03 16:36:26.000000000 +0200
*************** along with GCC; see the file COPYING3.
*** 42,47 ****
--- 42,79 ----
#include "tree-chrec.h"
+ /* Type of value ranges. See value_range_d for a description of these
+ types. */
+ enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
+
+ /* Range of values that can be associated with an SSA_NAME after VRP
+ has executed. */
+ struct value_range_d
+ {
+ /* Lattice value represented by this range. */
+ enum value_range_type type;
+
+ /* Minimum and maximum values represented by this range. These
+ values should be interpreted as follows:
+
+ - If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must
+ be NULL.
+
+ - If TYPE == VR_RANGE then MIN holds the minimum value and
+ MAX holds the maximum value of the range [MIN, MAX].
+
+ - If TYPE == ANTI_RANGE the variable is known to NOT
+ take any values in the range [MIN, MAX]. */
+ tree min;
+ tree max;
+
+ /* Set of SSA names whose value ranges are equivalent to this one.
+ This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */
+ bitmap equiv;
+ };
+
+ typedef struct value_range_d value_range_t;
+
/* Set of SSA names found live during the RPO traversal of the function
for still active basic-blocks. */
static sbitmap *live;
*************** static void
*** 7526,7533 ****
vrp_finalize (void)
{
size_t i;
- prop_value_t *single_val_range;
- bool do_value_subst_p;
unsigned num = num_ssa_names;
if (dump_file)
--- 7558,7563 ----
*************** vrp_finalize (void)
*** 7537,7567 ****
fprintf (dump_file, "\n");
}
! /* We may have ended with ranges that have exactly one value. Those
! values can be substituted as any other const propagated
! value using substitute_and_fold. */
! single_val_range = XCNEWVEC (prop_value_t, num);
!
! do_value_subst_p = false;
! for (i = 0; i < num; i++)
! if (vr_value[i]
! && vr_value[i]->type == VR_RANGE
! && vr_value[i]->min == vr_value[i]->max
! && is_gimple_min_invariant (vr_value[i]->min))
! {
! single_val_range[i].value = vr_value[i]->min;
! do_value_subst_p = true;
! }
!
! if (!do_value_subst_p)
! {
! /* We found no single-valued ranges, don't waste time trying to
! do single value substitution in substitute_and_fold. */
! free (single_val_range);
! single_val_range = NULL;
! }
!
! substitute_and_fold (single_val_range, vrp_fold_stmt, false);
if (warn_array_bounds)
check_all_array_refs ();
--- 7567,7574 ----
fprintf (dump_file, "\n");
}
! substitute_and_fold (op_with_constant_singleton_value_range,
! vrp_fold_stmt, false);
if (warn_array_bounds)
check_all_array_refs ();
*************** vrp_finalize (void)
*** 7578,7584 ****
free (vr_value[i]);
}
- free (single_val_range);
free (vr_value);
free (vr_phi_edge_counts);
--- 7585,7590 ----
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c 2009-09-15 15:27:14.000000000 +0200
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c 2010-08-03 16:28:29.000000000 +0200
*************** int test1(int i, int k)
*** 11,15 ****
return 1;
}
! /* { dg-final { scan-tree-dump "Folding predicate j_.* == 10 to 0" "vrp1" } } */
/* { dg-final { cleanup-tree-dump "vrp1" } } */
--- 11,15 ----
return 1;
}
! /* { dg-final { scan-tree-dump-not "j_.* == 10" "vrp1" } } */
/* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c 2009-09-15 15:27:14.000000000 +0200
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c 2010-08-03 16:28:52.000000000 +0200
*************** int foo(int i)
*** 8,12 ****
return 1;
}
! /* { dg-final { scan-tree-dump "Folding predicate i_.* == 1 to 0" "vrp1" } } */
/* { dg-final { cleanup-tree-dump "vrp1" } } */
--- 8,12 ----
return 1;
}
! /* { dg-final { scan-tree-dump-not "i_.* == 1" "vrp1" } } */
/* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp50.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp50.c 2010-07-09 10:21:18.000000000 +0200
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp50.c 2010-08-03 16:29:27.000000000 +0200
*************** int baz (int x, int y)
*** 30,36 ****
return x < 20;
}
! /* { dg-final { scan-tree-dump "Folding predicate i_\[^\n\r\]* to 1" "vrp1" } } */
! /* { dg-final { scan-tree-dump "Folding predicate c_\[^\n\r\]* to 1" "vrp1" } } */
! /* { dg-final { scan-tree-dump "Folding predicate x_\[^\n\r\]* to 1" "vrp1" } } */
/* { dg-final { cleanup-tree-dump "vrp1" } } */
--- 30,34 ----
return x < 20;
}
! /* { dg-final { scan-tree-dump-times "return 1;" 3 "vrp1" } } */
/* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp52.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp52.c 2010-07-10 13:25:52.000000000 +0200
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp52.c 2010-08-03 16:29:43.000000000 +0200
*************** foo (unsigned int i, unsigned int j)
*** 12,16 ****
return i >= 1024 + 2048;
}
! /* { dg-final { scan-tree-dump "Folding predicate i_\[^\n\r\]* to 1" "vrp1" } } */
/* { dg-final { cleanup-tree-dump "vrp1" } } */
--- 12,16 ----
return i >= 1024 + 2048;
}
! /* { dg-final { scan-tree-dump-times "return 1;" 1 "vrp1" } } */
/* { dg-final { cleanup-tree-dump "vrp1" } } */