This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Store the SSA name range type in the tree structure
- From: Richard Biener <richard dot guenther at gmail dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>, Richard Sandiford <rdsandiford at googlemail dot com>
- Date: Thu, 28 Nov 2013 15:07:21 +0100
- Subject: Re: Store the SSA name range type in the tree structure
- Authentication-results: sourceware.org; auth=none
- References: <87li08rcm7 dot fsf at sandifor-thinkpad dot stglab dot manchester dot uk dot ibm dot com>
On Thu, Nov 28, 2013 at 12:26 PM, Richard Sandiford
<rdsandiford@googlemail.com> wrote:
> At the moment, an anti range ~[A,B] is stored as [B+1,A-1]. This makes
> it harder to store the range in the natural precision of A and B, since
> B+1 and A-1 might not be representable in that precision.
>
> This patch instead stores the original minimum and maximum values and
> uses a spare tree bit to represent the range type. The version below
> is for trunk; I've also tested a wide-int version.
>
> Tested on x86_64-linux-gnu. OK to install?
Ok.
Thanks,
Richard.
> Thanks,
> Richard
>
>
> gcc/
> * tree-core.h (tree_base): Document use of static_flag for SSA_NAME.
> * tree.h (SSA_NAME_ANTI_RANGE_P, SSA_NAME_RANGE_TYPE): New macros.
> * tree-ssanames.h (set_range_info): Add range_type argument.
> (duplicate_ssa_name_range_info): Likewise.
> * tree-ssanames.c (set_range_info): Take the range type as argument
> and store it in SSA_NAME_ANTI_RANGE_P.
> (duplicate_ssa_name_range_info): Likewise.
> (get_range_info): Use SSA_NAME_ANTI_RANGE_P.
> (set_nonzero_bits): Update call to set_range_info.
> (duplicate_ssa_name_fn): Update call to duplicate_ssa_name_range_info.
> * tree-ssa-copy.c (fini_copy_prop): Likewise.
> * tree-vrp.c (remove_range_assertions): Update call to set_range_info.
> (vrp_finalize): Likewise, passing anti-ranges directly.
>
> Index: gcc/tree-core.h
> ===================================================================
> --- gcc/tree-core.h 2013-11-15 18:23:21.113488640 +0000
> +++ gcc/tree-core.h 2013-11-28 11:12:32.956977322 +0000
> @@ -822,6 +822,9 @@ struct GTY(()) tree_base {
> TRANSACTION_EXPR_OUTER in
> TRANSACTION_EXPR
>
> + SSA_NAME_ANTI_RANGE_P in
> + SSA_NAME
> +
> public_flag:
>
> TREE_OVERFLOW in
> Index: gcc/tree.h
> ===================================================================
> --- gcc/tree.h 2013-11-20 10:58:57.275831561 +0000
> +++ gcc/tree.h 2013-11-28 11:12:32.969977280 +0000
> @@ -1434,6 +1434,14 @@ #define SSA_NAME_IS_DEFAULT_DEF(NODE) \
> #define SSA_NAME_PTR_INFO(N) \
> SSA_NAME_CHECK (N)->ssa_name.info.ptr_info
>
> +/* True if SSA_NAME_RANGE_INFO describes an anti-range. */
> +#define SSA_NAME_ANTI_RANGE_P(N) \
> + SSA_NAME_CHECK (N)->base.static_flag
> +
> +/* The type of range described by SSA_NAME_RANGE_INFO. */
> +#define SSA_NAME_RANGE_TYPE(N) \
> + (SSA_NAME_ANTI_RANGE_P (N) ? VR_ANTI_RANGE : VR_RANGE)
> +
> /* Value range info attributes for SSA_NAMEs of non pointer-type variables. */
> #define SSA_NAME_RANGE_INFO(N) \
> SSA_NAME_CHECK (N)->ssa_name.info.range_info
> Index: gcc/tree-ssanames.h
> ===================================================================
> --- gcc/tree-ssanames.h 2013-11-15 18:23:22.050485010 +0000
> +++ gcc/tree-ssanames.h 2013-11-28 11:12:32.964977296 +0000
> @@ -70,7 +70,8 @@ #define ssa_name(i) ((*cfun->gimple_df->
> enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
>
> /* Sets the value range to SSA. */
> -extern void set_range_info (tree, double_int, double_int);
> +extern void set_range_info (tree, enum value_range_type, double_int,
> + double_int);
> /* Gets the value range from SSA. */
> extern enum value_range_type get_range_info (const_tree, double_int *,
> double_int *);
> @@ -93,7 +94,8 @@ extern struct ptr_info_def *get_ptr_info
> extern tree copy_ssa_name_fn (struct function *, tree, gimple);
> extern void duplicate_ssa_name_ptr_info (tree, struct ptr_info_def *);
> extern tree duplicate_ssa_name_fn (struct function *, tree, gimple);
> -extern void duplicate_ssa_name_range_info (tree, struct range_info_def *);
> +extern void duplicate_ssa_name_range_info (tree, enum value_range_type,
> + struct range_info_def *);
> extern void release_defs (gimple);
> extern void replace_ssa_name_symbol (tree, tree);
>
> Index: gcc/tree-ssanames.c
> ===================================================================
> --- gcc/tree-ssanames.c 2013-11-20 10:59:18.330782865 +0000
> +++ gcc/tree-ssanames.c 2013-11-28 11:12:32.963977300 +0000
> @@ -178,12 +178,14 @@ make_ssa_name_fn (struct function *fn, t
> return t;
> }
>
> -/* Store range information MIN, and MAX to tree ssa_name NAME. */
> +/* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name NAME. */
>
> void
> -set_range_info (tree name, double_int min, double_int max)
> +set_range_info (tree name, enum value_range_type range_type, double_int min,
> + double_int max)
> {
> gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
> + gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
> range_info_def *ri = SSA_NAME_RANGE_INFO (name);
>
> /* Allocate if not available. */
> @@ -194,12 +196,16 @@ set_range_info (tree name, double_int mi
> ri->nonzero_bits = double_int::mask (TYPE_PRECISION (TREE_TYPE (name)));
> }
>
> + /* Record the range type. */
> + if (SSA_NAME_RANGE_TYPE (name) != range_type)
> + SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
> +
> /* Set the values. */
> ri->min = min;
> ri->max = max;
>
> /* If it is a range, try to improve nonzero_bits from the min/max. */
> - if (min.cmp (max, TYPE_UNSIGNED (TREE_TYPE (name))) != 1)
> + if (range_type == VR_RANGE)
> {
> int prec = TYPE_PRECISION (TREE_TYPE (name));
> double_int xorv;
> @@ -225,7 +231,6 @@ set_range_info (tree name, double_int mi
> enum value_range_type
> get_range_info (const_tree name, double_int *min, double_int *max)
> {
> - enum value_range_type range_type;
> gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
> gcc_assert (min && max);
> range_info_def *ri = SSA_NAME_RANGE_INFO (name);
> @@ -236,22 +241,9 @@ get_range_info (const_tree name, double_
> > 2 * HOST_BITS_PER_WIDE_INT))
> return VR_VARYING;
>
> - /* If min > max, it is VR_ANTI_RANGE. */
> - if (ri->min.cmp (ri->max, TYPE_UNSIGNED (TREE_TYPE (name))) == 1)
> - {
> - /* VR_ANTI_RANGE ~[min, max] is encoded as [max + 1, min - 1]. */
> - range_type = VR_ANTI_RANGE;
> - *min = ri->max + double_int_one;
> - *max = ri->min - double_int_one;
> - }
> - else
> - {
> - /* Otherwise (when min <= max), it is VR_RANGE. */
> - range_type = VR_RANGE;
> - *min = ri->min;
> - *max = ri->max;
> - }
> - return range_type;
> + *min = ri->min;
> + *max = ri->max;
> + return SSA_NAME_RANGE_TYPE (name);
> }
>
> /* Change non-zero bits bitmask of NAME. */
> @@ -261,7 +253,7 @@ set_nonzero_bits (tree name, double_int
> {
> gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
> if (SSA_NAME_RANGE_INFO (name) == NULL)
> - set_range_info (name,
> + set_range_info (name, VR_RANGE,
> tree_to_double_int (TYPE_MIN_VALUE (TREE_TYPE (name))),
> tree_to_double_int (TYPE_MAX_VALUE (TREE_TYPE (name))));
> range_info_def *ri = SSA_NAME_RANGE_INFO (name);
> @@ -490,15 +482,17 @@ duplicate_ssa_name_ptr_info (tree name,
> SSA_NAME_PTR_INFO (name) = new_ptr_info;
> }
>
> -/* Creates a duplicate of the range_info_def at RANGE_INFO for use by
> - the SSA name NAME. */
> +/* Creates a duplicate of the range_info_def at RANGE_INFO of type
> + RANGE_TYPE for use by the SSA name NAME. */
> void
> -duplicate_ssa_name_range_info (tree name, struct range_info_def *range_info)
> +duplicate_ssa_name_range_info (tree name, enum value_range_type range_type,
> + struct range_info_def *range_info)
> {
> struct range_info_def *new_range_info;
>
> gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
> gcc_assert (!SSA_NAME_RANGE_INFO (name));
> + gcc_assert (!SSA_NAME_ANTI_RANGE_P (name));
>
> if (!range_info)
> return;
> @@ -506,6 +500,8 @@ duplicate_ssa_name_range_info (tree name
> new_range_info = ggc_alloc_range_info_def ();
> *new_range_info = *range_info;
>
> + gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
> + SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
> SSA_NAME_RANGE_INFO (name) = new_range_info;
> }
>
> @@ -530,7 +526,8 @@ duplicate_ssa_name_fn (struct function *
> struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
>
> if (old_range_info)
> - duplicate_ssa_name_range_info (new_name, old_range_info);
> + duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name),
> + old_range_info);
> }
>
> return new_name;
> Index: gcc/tree-ssa-copy.c
> ===================================================================
> --- gcc/tree-ssa-copy.c 2013-11-20 10:59:13.528790271 +0000
> +++ gcc/tree-ssa-copy.c 2013-11-28 11:12:32.961977306 +0000
> @@ -572,6 +572,7 @@ fini_copy_prop (void)
> && SSA_NAME_RANGE_INFO (var)
> && !SSA_NAME_RANGE_INFO (copy_of[i].value))
> duplicate_ssa_name_range_info (copy_of[i].value,
> + SSA_NAME_RANGE_TYPE (var),
> SSA_NAME_RANGE_INFO (var));
> }
> }
> Index: gcc/tree-vrp.c
> ===================================================================
> --- gcc/tree-vrp.c 2013-11-20 10:58:52.760847630 +0000
> +++ gcc/tree-vrp.c 2013-11-28 11:12:32.967977287 +0000
> @@ -6583,7 +6583,8 @@ remove_range_assertions (void)
> && all_imm_uses_in_stmt_or_feed_cond (var, stmt,
> single_pred (bb)))
> {
> - set_range_info (var, SSA_NAME_RANGE_INFO (lhs)->min,
> + set_range_info (var, SSA_NAME_RANGE_TYPE (lhs),
> + SSA_NAME_RANGE_INFO (lhs)->min,
> SSA_NAME_RANGE_INFO (lhs)->max);
> maybe_set_nonzero_bits (bb, var);
> }
> @@ -9589,36 +9590,12 @@ vrp_finalize (void)
> continue;
>
> if ((TREE_CODE (vr_value[i]->min) == INTEGER_CST)
> - && (TREE_CODE (vr_value[i]->max) == INTEGER_CST))
> - {
> - if (vr_value[i]->type == VR_RANGE)
> - set_range_info (name,
> - tree_to_double_int (vr_value[i]->min),
> - tree_to_double_int (vr_value[i]->max));
> - else if (vr_value[i]->type == VR_ANTI_RANGE)
> - {
> - /* VR_ANTI_RANGE ~[min, max] is encoded compactly as
> - [max + 1, min - 1] without additional attributes.
> - When min value > max value, we know that it is
> - VR_ANTI_RANGE; it is VR_RANGE otherwise. */
> -
> - /* ~[0,0] anti-range is represented as
> - range. */
> - if (TYPE_UNSIGNED (TREE_TYPE (name))
> - && integer_zerop (vr_value[i]->min)
> - && integer_zerop (vr_value[i]->max))
> - set_range_info (name,
> - double_int_one,
> - double_int::max_value
> - (TYPE_PRECISION (TREE_TYPE (name)), true));
> - else
> - set_range_info (name,
> - tree_to_double_int (vr_value[i]->max)
> - + double_int_one,
> - tree_to_double_int (vr_value[i]->min)
> - - double_int_one);
> - }
> - }
> + && (TREE_CODE (vr_value[i]->max) == INTEGER_CST)
> + && (vr_value[i]->type == VR_RANGE
> + || vr_value[i]->type == VR_ANTI_RANGE))
> + set_range_info (name, vr_value[i]->type,
> + tree_to_double_int (vr_value[i]->min),
> + tree_to_double_int (vr_value[i]->max));
> }
>
> /* Free allocated memory. */