Message ID | 87li08rcm7.fsf@sandifor-thinkpad.stglab.manchester.uk.ibm.com |
---|---|
State | New |
Headers | show |
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. */
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. */