Store the SSA name range type in the tree structure
Richard Sandiford
rsandifo@linux.vnet.ibm.com
Thu Nov 28 22:30:00 GMT 2013
Richard Biener <richard.guenther@gmail.com> writes:
> 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.
Applied, thanks. For the record, here's the version I put on wide-int,
which is just a mechanical change from the trunk version.
Richard
Index: gcc/tree-core.h
===================================================================
--- gcc/tree-core.h 2013-11-27 11:31:27.043671967 +0000
+++ gcc/tree-core.h 2013-11-27 11:31:59.596530816 +0000
@@ -836,6 +836,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-ssa-copy.c
===================================================================
--- gcc/tree-ssa-copy.c 2013-11-27 11:31:27.043671967 +0000
+++ gcc/tree-ssa-copy.c 2013-11-27 11:31:59.603530785 +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-ssanames.c
===================================================================
--- gcc/tree-ssanames.c 2013-11-27 11:31:29.165662775 +0000
+++ gcc/tree-ssanames.c 2013-11-27 17:51:40.346250076 +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, const widest_int &min, const widest_int &max)
+set_range_info (tree name, enum value_range_type range_type,
+ const widest_int &min, const widest_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. */
@@ -195,12 +197,16 @@ set_range_info (tree name, const widest_
false);
}
+ /* 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 (wi::cmp (min, max, TYPE_SIGN (TREE_TYPE (name))) != 1)
+ if (range_type == VR_RANGE)
{
int prec = TYPE_PRECISION (TREE_TYPE (name));
@@ -223,7 +229,6 @@ set_range_info (tree name, const widest_
enum value_range_type
get_range_info (const_tree name, widest_int *min, widest_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);
@@ -234,22 +239,9 @@ get_range_info (const_tree name, widest_
> 2 * HOST_BITS_PER_WIDE_INT))
return VR_VARYING;
- /* If min > max, it is VR_ANTI_RANGE. */
- if (wi::cmp (ri->min, ri->max, TYPE_SIGN (TREE_TYPE (name))) == 1)
- {
- /* VR_ANTI_RANGE ~[min, max] is encoded as [max + 1, min - 1]. */
- range_type = VR_ANTI_RANGE;
- *min = ri->max + 1;
- *max = ri->min - 1;
- }
- 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. */
@@ -259,7 +251,7 @@ set_nonzero_bits (tree name, const wides
{
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,
wi::to_widest (TYPE_MIN_VALUE (TREE_TYPE (name))),
wi::to_widest (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-ssanames.h
===================================================================
--- gcc/tree-ssanames.h 2013-11-27 11:31:29.165662775 +0000
+++ gcc/tree-ssanames.h 2013-11-27 17:51:40.346250076 +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, const widest_int &, const widest_int &);
+extern void set_range_info (tree, enum value_range_type, const widest_int &,
+ const widest_int &);
/* Gets the value range from SSA. */
extern enum value_range_type get_range_info (const_tree, widest_int *,
widest_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-vrp.c
===================================================================
--- gcc/tree-vrp.c 2013-11-27 11:31:27.043671967 +0000
+++ gcc/tree-vrp.c 2013-11-27 17:52:03.753140623 +0000
@@ -6507,7 +6507,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);
}
@@ -9530,34 +9531,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, wi::to_widest (vr_value[i]->min),
- wi::to_widest (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))
- {
- unsigned prec = TYPE_PRECISION (TREE_TYPE (name));
- set_range_info (name, 1,
- wi::mask <widest_int> (prec, false));
- }
- else
- set_range_info (name,
- wi::to_widest (vr_value[i]->max) + 1,
- wi::to_widest (vr_value[i]->min) - 1);
- }
- }
+ && (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,
+ wi::to_widest (vr_value[i]->min),
+ wi::to_widest (vr_value[i]->max));
}
/* Free allocated memory. */
Index: gcc/tree.h
===================================================================
--- gcc/tree.h 2013-11-27 11:31:27.043671967 +0000
+++ gcc/tree.h 2013-11-27 11:31:59.645530603 +0000
@@ -1438,6 +1438,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
More information about the Gcc-patches
mailing list