[ping][PATCH][1 of 2] Add value range info to SSA_NAME for zero sign extension elimination in RTL
Christophe Lyon
christophe.lyon@linaro.org
Mon Sep 23 15:55:00 GMT 2013
Kugan,
>> I have changed all of the above in the attached patch and ChangeLog. If this
>> is OK, could someone please commit it for me. I don’t have access to commit
>> it.
>>
>> Bootstrapped and regtested on x86_64-unknown-linux-gnu and arm-none
>> linux-gnueabi.
>
> Ok.
>
> Thanks and sorry that it took so long,
> Richard.
>
>> Thanks,
>> Kugan
>>
>>
I have committed it for you (rev 202831), with a few modifications
(ChangeLog formatting, typos).
Here is what I have committed:
2013-09-23 Kugan Vivekanandarajah <kuganv@linaro.org>
* gimple-pretty-print.c (dump_ssaname_info): New function.
(dump_gimple_phi): Call it.
(pp_gimple_stmt_1): Likewise.
* tree-core.h (tree_ssa_name): New union ssa_name_info_type field.
(range_info_def): Declare.
* tree-pretty-print.c (pp_double_int): New function.
(dump_generic_node): Call it.
* tree-pretty-print.h (pp_double_int): Declare.
* tree-ssa-alias.c (dump_alias_info): Check pointer type.
* tree-ssanames.h (range_info_def): New structure.
(value_range_type): Move definition here.
(set_range_info, value_range_type, duplicate_ssa_name_range_info):
Declare.
* tree-ssanames.c (make_ssa_name_fn): Check pointer type at
initialization.
(set_range_info): New function.
(get_range_info): Likewise.
(duplicate_ssa_name_range_info): Likewise.
(duplicate_ssa_name_fn): Check pointer type and call
duplicate_ssa_name_range_info.
* tree-ssa-copy.c (fini_copy_prop): Likewise.
* tree-vrp.c (value_range_type): Remove definition, now in
tree-ssanames.h.
(vrp_finalize): Call set_range_info to update value range of
SSA_NAMEs.
* tree.h (SSA_NAME_PTR_INFO): Macro changed to access via union.
(SSA_NAME_RANGE_INFO): New macro.
-------------- next part --------------
Index: gcc/gimple-pretty-print.c
===================================================================
--- gcc/gimple-pretty-print.c (revision 202830)
+++ gcc/gimple-pretty-print.c (working copy)
@@ -1600,23 +1600,20 @@ dump_gimple_asm (pretty_printer *buffer,
}
}
-
-/* Dump a PHI node PHI. BUFFER, SPC and FLAGS are as in pp_gimple_stmt_1.
- The caller is responsible for calling pp_flush on BUFFER to finalize
- pretty printer. */
+/* Dump ptr_info and range_info for NODE on pretty_printer BUFFER with
+ SPC spaces of indent. */
static void
-dump_gimple_phi (pretty_printer *buffer, gimple phi, int spc, int flags)
+dump_ssaname_info (pretty_printer *buffer, tree node, int spc)
{
- size_t i;
- tree lhs = gimple_phi_result (phi);
+ if (TREE_CODE (node) != SSA_NAME)
+ return;
- if (flags & TDF_ALIAS
- && POINTER_TYPE_P (TREE_TYPE (lhs))
- && SSA_NAME_PTR_INFO (lhs))
+ if (POINTER_TYPE_P (TREE_TYPE (node))
+ && SSA_NAME_PTR_INFO (node))
{
unsigned int align, misalign;
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs);
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO (node);
pp_string (buffer, "PT = ");
pp_points_to_solution (buffer, &pi->pt);
newline_and_indent (buffer, spc);
@@ -1628,6 +1625,41 @@ dump_gimple_phi (pretty_printer *buffer,
pp_string (buffer, "# ");
}
+ if (!POINTER_TYPE_P (TREE_TYPE (node))
+ && SSA_NAME_RANGE_INFO (node))
+ {
+ double_int min, max;
+ value_range_type range_type = get_range_info (node, &min, &max);
+
+ if (range_type == VR_VARYING)
+ pp_printf (buffer, "# RANGE VR_VARYING");
+ else if (range_type == VR_RANGE || range_type == VR_ANTI_RANGE)
+ {
+ pp_printf (buffer, "# RANGE ");
+ pp_printf (buffer, "%s[", range_type == VR_RANGE ? "" : "~");
+ pp_double_int (buffer, min, TYPE_UNSIGNED (TREE_TYPE (node)));
+ pp_printf (buffer, ", ");
+ pp_double_int (buffer, max, TYPE_UNSIGNED (TREE_TYPE (node)));
+ pp_printf (buffer, "]");
+ newline_and_indent (buffer, spc);
+ }
+ }
+}
+
+
+/* Dump a PHI node PHI. BUFFER, SPC and FLAGS are as in pp_gimple_stmt_1.
+ The caller is responsible for calling pp_flush on BUFFER to finalize
+ pretty printer. */
+
+static void
+dump_gimple_phi (pretty_printer *buffer, gimple phi, int spc, int flags)
+{
+ size_t i;
+ tree lhs = gimple_phi_result (phi);
+
+ if (flags & TDF_ALIAS)
+ dump_ssaname_info (buffer, lhs, spc);
+
if (flags & TDF_RAW)
dump_gimple_fmt (buffer, spc, flags, "%G <%T, ", phi,
gimple_phi_result (phi));
@@ -1908,27 +1940,9 @@ pp_gimple_stmt_1 (pretty_printer *buffer
&& gimple_has_mem_ops (gs))
dump_gimple_mem_ops (buffer, gs, spc, flags);
- if ((flags & TDF_ALIAS)
- && gimple_has_lhs (gs))
- {
- tree lhs = gimple_get_lhs (gs);
- if (TREE_CODE (lhs) == SSA_NAME
- && POINTER_TYPE_P (TREE_TYPE (lhs))
- && SSA_NAME_PTR_INFO (lhs))
- {
- unsigned int align, misalign;
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs);
- pp_string (buffer, "# PT = ");
- pp_points_to_solution (buffer, &pi->pt);
- newline_and_indent (buffer, spc);
- if (get_ptr_info_alignment (pi, &align, &misalign))
- {
- pp_printf (buffer, "# ALIGN = %u, MISALIGN = %u",
- align, misalign);
- newline_and_indent (buffer, spc);
- }
- }
- }
+ if (gimple_has_lhs (gs)
+ && (flags & TDF_ALIAS))
+ dump_ssaname_info (buffer, gimple_get_lhs (gs), spc);
switch (gimple_code (gs))
{
Index: gcc/tree-core.h
===================================================================
--- gcc/tree-core.h (revision 202830)
+++ gcc/tree-core.h (working copy)
@@ -43,6 +43,7 @@ struct function;
struct real_value;
struct fixed_value;
struct ptr_info_def;
+struct range_info_def;
struct die_struct;
struct pointer_set_t;
@@ -1050,8 +1051,14 @@ struct GTY(()) tree_ssa_name {
/* Statement that defines this SSA name. */
gimple def_stmt;
- /* Pointer attributes used for alias analysis. */
- struct ptr_info_def *ptr_info;
+ /* Value range information. */
+ union ssa_name_info_type {
+ /* Pointer attributes used for alias analysis. */
+ struct GTY ((tag ("0"))) ptr_info_def *ptr_info;
+ /* Value range attributes used for zero/sign extension elimination. */
+ struct GTY ((tag ("1"))) range_info_def *range_info;
+ } GTY ((desc ("%1.typed.type ?" \
+ "!POINTER_TYPE_P (TREE_TYPE ((tree)&%1)) : 2"))) info;
/* Immediate uses list for this SSA_NAME. */
struct ssa_use_operand_d imm_uses;
Index: gcc/tree-pretty-print.c
===================================================================
--- gcc/tree-pretty-print.c (revision 202830)
+++ gcc/tree-pretty-print.c (working copy)
@@ -1062,29 +1062,9 @@ dump_generic_node (pretty_printer *buffe
pp_wide_integer (buffer, TREE_INT_CST_LOW (node));
pp_string (buffer, "B"); /* pseudo-unit */
}
- else if (host_integerp (node, 0))
- pp_wide_integer (buffer, TREE_INT_CST_LOW (node));
- else if (host_integerp (node, 1))
- pp_unsigned_wide_integer (buffer, TREE_INT_CST_LOW (node));
else
- {
- tree val = node;
- unsigned HOST_WIDE_INT low = TREE_INT_CST_LOW (val);
- HOST_WIDE_INT high = TREE_INT_CST_HIGH (val);
-
- if (tree_int_cst_sgn (val) < 0)
- {
- pp_minus (buffer);
- high = ~high + !low;
- low = -low;
- }
- /* Would "%x%0*x" or "%x%*0x" get zero-padding on all
- systems? */
- sprintf (pp_buffer (buffer)->digit_buffer,
- HOST_WIDE_INT_PRINT_DOUBLE_HEX,
- (unsigned HOST_WIDE_INT) high, low);
- pp_string (buffer, pp_buffer (buffer)->digit_buffer);
- }
+ pp_double_int (buffer, tree_to_double_int (node),
+ TYPE_UNSIGNED (TREE_TYPE (node)));
break;
case REAL_CST:
@@ -3196,3 +3176,31 @@ dump_function_header (FILE *dump_file, t
else
fprintf (dump_file, ")\n\n");
}
+
+/* Dump double_int D to pretty_printer PP. UNS is true
+ if D is unsigned and false otherwise. */
+void
+pp_double_int (pretty_printer *pp, double_int d, bool uns)
+{
+ if (d.fits_shwi ())
+ pp_wide_integer (pp, d.low);
+ else if (d.fits_uhwi ())
+ pp_unsigned_wide_integer (pp, d.low);
+ else
+ {
+ unsigned HOST_WIDE_INT low = d.low;
+ HOST_WIDE_INT high = d.high;
+ if (!uns && d.is_negative ())
+ {
+ pp_minus (pp);
+ high = ~high + !low;
+ low = -low;
+ }
+ /* Would "%x%0*x" or "%x%*0x" get zero-padding on all
+ systems? */
+ sprintf (pp_buffer (pp)->digit_buffer,
+ HOST_WIDE_INT_PRINT_DOUBLE_HEX,
+ (unsigned HOST_WIDE_INT) high, low);
+ pp_string (pp, pp_buffer (pp)->digit_buffer);
+ }
+}
Index: gcc/tree-pretty-print.h
===================================================================
--- gcc/tree-pretty-print.h (revision 202830)
+++ gcc/tree-pretty-print.h (working copy)
@@ -23,6 +23,7 @@ along with GCC; see the file COPYING3.
#define GCC_TREE_PRETTY_PRINT_H
#include "pretty-print.h"
+#include "double-int.h"
#define pp_unsupported_tree(PP, T) \
pp_verbatim (PP, "#%qs not supported by %s#", \
@@ -46,6 +47,7 @@ extern void debug_generic_stmt (tree);
extern void debug_tree_chain (tree);
extern void percent_K_format (text_info *);
extern void dump_function_header (FILE *, tree, int);
+extern void pp_double_int (pretty_printer *pp, double_int d, bool uns);
/* In c-pretty-print.c */
extern void debug_c_tree (tree);
Index: gcc/tree-ssa-alias.c
===================================================================
--- gcc/tree-ssa-alias.c (revision 202830)
+++ gcc/tree-ssa-alias.c (working copy)
@@ -404,6 +404,7 @@ dump_alias_info (FILE *file)
struct ptr_info_def *pi;
if (ptr == NULL_TREE
+ || !POINTER_TYPE_P (TREE_TYPE (ptr))
|| SSA_NAME_IN_FREE_LIST (ptr))
continue;
Index: gcc/tree-ssa-copy.c
===================================================================
--- gcc/tree-ssa-copy.c (revision 202830)
+++ gcc/tree-ssa-copy.c (working copy)
@@ -767,11 +767,19 @@ fini_copy_prop (void)
of the representative to the first solution we find if
it doesn't have one already. */
if (copy_of[i].value != var
- && TREE_CODE (copy_of[i].value) == SSA_NAME
- && 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));
+ && TREE_CODE (copy_of[i].value) == SSA_NAME)
+ {
+ if (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));
+ else if (!POINTER_TYPE_P (TREE_TYPE (var))
+ && 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_INFO (var));
+ }
}
/* Don't do DCE if SCEV is initialized. It would destroy the scev cache. */
Index: gcc/tree-ssanames.c
===================================================================
--- gcc/tree-ssanames.c (revision 202830)
+++ gcc/tree-ssanames.c (working copy)
@@ -154,7 +154,11 @@ make_ssa_name_fn (struct function *fn, t
SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
}
SSA_NAME_DEF_STMT (t) = stmt;
- SSA_NAME_PTR_INFO (t) = NULL;
+ if (POINTER_TYPE_P (TREE_TYPE (t)))
+ SSA_NAME_PTR_INFO (t) = NULL;
+ else
+ SSA_NAME_RANGE_INFO (t) = NULL;
+
SSA_NAME_IN_FREE_LIST (t) = 0;
SSA_NAME_IS_DEFAULT_DEF (t) = 0;
imm = &(SSA_NAME_IMM_USE_NODE (t));
@@ -166,6 +170,62 @@ make_ssa_name_fn (struct function *fn, t
return t;
}
+/* Store range information MIN, and MAX to tree ssa_name NAME. */
+
+void
+set_range_info (tree name, double_int min, double_int max)
+{
+ gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
+ range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+
+ /* Allocate if not available. */
+ if (ri == NULL)
+ {
+ ri = ggc_alloc_cleared_range_info_def ();
+ SSA_NAME_RANGE_INFO (name) = ri;
+ }
+
+ /* Set the values. */
+ ri->min = min;
+ ri->max = max;
+}
+
+
+/* Gets range information MIN, MAX and returns enum value_range_type
+ corresponding to tree ssa_name NAME. enum value_range_type returned
+ is used to determine if MIN and MAX are valid values. */
+
+enum value_range_type
+get_range_info (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);
+
+ /* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs
+ with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision. */
+ if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name)))
+ > 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;
+}
/* We no longer need the SSA_NAME expression VAR, release it so that
it may be reused.
@@ -362,6 +422,26 @@ 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. */
+void
+duplicate_ssa_name_range_info (tree name, 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));
+
+ if (!range_info)
+ return;
+
+ new_range_info = ggc_alloc_range_info_def ();
+ *new_range_info = *range_info;
+
+ SSA_NAME_RANGE_INFO (name) = new_range_info;
+}
+
+
/* Creates a duplicate of a ssa name NAME tobe defined by statement STMT
in function FN. */
@@ -370,10 +450,20 @@ tree
duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt)
{
tree new_name = copy_ssa_name_fn (fn, name, stmt);
- struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
+ if (POINTER_TYPE_P (TREE_TYPE (name)))
+ {
+ struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
- if (old_ptr_info)
- duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
+ if (old_ptr_info)
+ duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
+ }
+ else
+ {
+ 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);
+ }
return new_name;
}
Index: gcc/tree-ssanames.h
===================================================================
--- gcc/tree-ssanames.h (revision 202830)
+++ gcc/tree-ssanames.h (working copy)
@@ -45,6 +45,15 @@ struct GTY(()) ptr_info_def
unsigned int misalign;
};
+/* Value range information for SSA_NAMEs representing non-pointer variables. */
+
+struct GTY (()) range_info_def {
+ /* Minimum for value range. */
+ double_int min;
+ /* Maximum for value range. */
+ double_int max;
+};
+
#define SSANAMES(fun) (fun)->gimple_df->ssa_names
#define MODIFIED_NORETURN_CALLS(fun) (fun)->gimple_df->modified_noreturn_calls
@@ -54,6 +63,15 @@ struct GTY(()) ptr_info_def
#define ssa_name(i) ((*cfun->gimple_df->ssa_names)[(i)])
+/* Type of value ranges. See value_range_d In tree-vrp.c for a
+ description of these types. */
+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 ssa, double_int min, double_int max);
+/* Gets the value range from SSA. */
+extern enum value_range_type get_range_info (tree name, double_int *min,
+ double_int *max);
extern void init_ssanames (struct function *, int);
extern void fini_ssanames (void);
extern void ssanames_print_statistics (void);
@@ -71,6 +89,7 @@ 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 release_defs (gimple);
extern void replace_ssa_name_symbol (tree, tree);
Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c (revision 202830)
+++ gcc/tree-vrp.c (working copy)
@@ -41,9 +41,6 @@ along with GCC; see the file COPYING3.
#include "optabs.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. */
@@ -9452,6 +9449,50 @@ vrp_finalize (void)
the datastructures built by VRP. */
identify_jump_threads ();
+ /* Set value range to non pointer SSA_NAMEs. */
+ for (i = 0; i < num_vr_values; i++)
+ if (vr_value[i])
+ {
+ tree name = ssa_name (i);
+
+ if (POINTER_TYPE_P (TREE_TYPE (name))
+ || (vr_value[i]->type == VR_VARYING)
+ || (vr_value[i]->type == VR_UNDEFINED))
+ 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);
+ }
+ }
+ }
+
/* Free allocated memory. */
for (i = 0; i < num_vr_values; i++)
if (vr_value[i])
Index: gcc/tree.h
===================================================================
--- gcc/tree.h (revision 202830)
+++ gcc/tree.h (working copy)
@@ -1336,7 +1336,11 @@ extern void protected_set_expr_location
/* Attributes for SSA_NAMEs for pointer-type variables. */
#define SSA_NAME_PTR_INFO(N) \
- SSA_NAME_CHECK (N)->ssa_name.ptr_info
+ SSA_NAME_CHECK (N)->ssa_name.info.ptr_info
+
+/* 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
/* Return the immediate_use information for an SSA_NAME. */
#define SSA_NAME_IMM_USE_NODE(NODE) SSA_NAME_CHECK (NODE)->ssa_name.imm_uses
More information about the Gcc-patches
mailing list