I'd like to ping this patch 1 of 2 that removes redundant zero/sign
extension using value range information.
Bootstrapped and no new regression for x86_64-unknown-linux-gnu and
arm-none-linux-gnueabi.
Thanks you for your time.
Kugan
n 14/08/13 16:49, Kugan wrote:
Hi Richard,
Here is an attempt to address your earlier review comments. Bootstrapped
and there is no new regression for X86_64 and arm. Thank you very much
for your time.
Thanks,
Kugan
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,25 @@
+2013-08-14 Kugan Vivekanandarajah <kug...@linaro.org>
+
+ * tree-flow.h (mark_range_info_unknown): New function definition.
+ * tree-ssa-alias.c (dump_alias_info) : Check pointer type.
+ * tree-ssa-copy.c (fini_copy_prop) : Check pointer type and copy
+ range info.
+ * tree-ssanames.c (make_ssa_name_fn) : Check pointer type in
+ initialize.
+ * (mark_range_info_unknown) : New function.
+ * (duplicate_ssa_name_range_info) : Likewise.
+ * (duplicate_ssa_name_fn) : Check pointer type and call correct
+ duplicate function.
+ * tree-vrp.c (extract_exp_value_range): New function.
+ * (simplify_stmt_using_ranges): Call extract_exp_value_range and
+ tree_ssa_set_value_range.
+ * tree-ssaname.c (ssa_range_info): New function.
+ * tree.h (SSA_NAME_PTR_INFO) : changed to access via union
+ * tree.h (SSA_NAME_RANGE_INFO) : New macro
+ * gimple-pretty-print.c (print_double_int) : New function.
+ * gimple-pretty-print.c (dump_gimple_phi) : Dump range info.
+ * (pp_gimple_stmt_1) : Likewise.
+
2013-08-09 Jan Hubicka <j...@suse.cz>
* cgraph.c (cgraph_create_edge_1): Clear speculative flag.
On 03/07/13 21:55, Kugan wrote:
On 17/06/13 18:33, Richard Biener wrote:
On Mon, 17 Jun 2013, Kugan wrote:
+/* Extract the value range of assigned exprassion for GIMPLE_ASSIGN
stmt.
+ If the extracted value range is valid, return true else return
+ false. */
+static bool
+extract_exp_value_range (gimple stmt, value_range_t *vr)
+{
+ gcc_assert (is_gimple_assign (stmt));
+ tree rhs1 = gimple_assign_rhs1 (stmt);
+ tree lhs = gimple_assign_lhs (stmt);
+ enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
...
@@ -8960,6 +9016,23 @@ simplify_stmt_using_ranges (gimple_stmt_iterator
*gsi)
{
enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
tree rhs1 = gimple_assign_rhs1 (stmt);
+ tree lhs = gimple_assign_lhs (stmt);
+
+ /* Set value range information for ssa. */
+ if (!POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
+ && (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
+ && !SSA_NAME_RANGE_INFO (lhs))
+ {
+ value_range_t vr = VR_INITIALIZER;
...
+ if (extract_exp_value_range (stmt, &vr))
+ tree_ssa_set_value_range (lhs,
+ tree_to_double_int (vr.min),
+ tree_to_double_int (vr.max),
+ vr.type == VR_RANGE);
+ }
This looks overly complicated to me. In vrp_finalize you can simply do
for (i = 0; i < num_vr_values; i++)
if (vr_value[i])
{
tree name = ssa_name (i);
if (POINTER_TYPE_P (name))
continue;
if (vr_value[i].type == VR_RANGE
|| vr_value[i].type == VR_ANTI_RANGE)
tree_ssa_set_value_range (name, tree_to_double_int
(vr_value[i].min), tree_to_double_int (vr_value[i].max),
vr_value[i].type
== VR_RANGE);
}
Thanks Richard for taking time to review it.
I was doing something like what you are suggesting earlier but noticed
some problems and that’s the reason why I changed.
For example, for the following testcase from the test suite,
unsigned long l = (unsigned long)-2;
unsigned short s;
int main () {
long t = l + 1;
s = l;
if (s != (unsigned short) -2)
abort ();
exit (0);
}
with the following gimple stmts
main ()
{
short unsigned int s.1;
long unsigned int l.0;
;; basic block 2, loop depth 0
;; pred: ENTRY
l.0_2 = l;
s.1_3 = (short unsigned int) l.0_2;
s = s.1_3;
if (s.1_3 != 65534)
goto <bb 3>;
else
goto <bb 4>;
;; succ: 3
;; 4
;; basic block 3, loop depth 0
;; pred: 2
abort ();
;; succ:
;; basic block 4, loop depth 0
;; pred: 2
exit (0);
;; succ:
}
has the following value range.
l.0_2: VARYING
s.1_3: [0, +INF]
From zero/sign extension point of view, the variable s.1_3 is expected
to have a value that will overflow (or varying) as this is what is
assigned to a smaller variable. extract_range_from_assignment initially
calculates the value range as VARYING but later changed to [0, +INF] by
extract_range_basic. What I need here is the value that will be assigned
from the rhs expression and not the value that we will have with proper
assignment.
I understand that the above code of mine needs to be changed but not
convinced about the best way to do that.
I can possibly re-factor extract_range_from_assignment to give me this
information with an additional argument. Could you kindly let me know
your preference.
/* SSA name annotations. */
+ union vrp_info_type {
+ /* Pointer attributes used for alias analysis. */
+ struct GTY ((tag ("TREE_SSA_PTR_INFO"))) ptr_info_def *ptr_info;
+ /* Value range attributes used for zero/sign extension elimination.
*/
/* Value range information. */
+ struct GTY ((tag ("TREE_SSA_RANGE_INFO"))) range_info_def
*range_info;
+ } GTY ((desc ("%1.def_stmt && !POINTER_TYPE_P (TREE_TYPE
((tree)&%1))"))) vrp;
why do you need to test %1.def_stmt here?
I have seen some tree_ssa_name with def_stmt NULL. Thats why I added
this. Is that something that should never happen.
Thanks,
Kugan
diff --git a/gcc/gimple-pretty-print.c b/gcc/gimple-pretty-print.c
index 1d40680..70e3f0d 100644
--- a/gcc/gimple-pretty-print.c
+++ b/gcc/gimple-pretty-print.c
@@ -1581,6 +1581,24 @@ dump_gimple_asm (pretty_printer *buffer, gimple gs, int spc, int flags)
}
}
+/* Dumps double_int CST to BUFFER. */
+
+static void
+print_double_int (pretty_printer *buffer, double_int cst)
+{
+ tree node = double_int_to_tree (integer_type_node, cst);
+ if (TREE_INT_CST_HIGH (node) == 0)
+ pp_printf (buffer, HOST_WIDE_INT_PRINT_UNSIGNED, TREE_INT_CST_LOW (node));
+ else if (TREE_INT_CST_HIGH (node) == -1
+ && TREE_INT_CST_LOW (node) != 0)
+ pp_printf (buffer, "-" HOST_WIDE_INT_PRINT_UNSIGNED,
+ -TREE_INT_CST_LOW (node));
+ else
+ pp_printf (buffer, "0x%" HOST_LONG_FORMAT "x%" HOST_LONG_FORMAT "x",
+ (unsigned HOST_WIDE_INT) TREE_INT_CST_HIGH (node),
+ (unsigned HOST_WIDE_INT) TREE_INT_CST_LOW (node));
+}
+
/* 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
@@ -1609,6 +1627,19 @@ dump_gimple_phi (pretty_printer *buffer, gimple phi, int spc, int flags)
pp_string (buffer, "# ");
}
+ if (!POINTER_TYPE_P (TREE_TYPE (lhs))
+ && SSA_NAME_RANGE_INFO (lhs))
+ {
+ struct range_info_def *ri = SSA_NAME_RANGE_INFO (lhs);
+ pp_printf (buffer, "# RANGE ");
+ pp_printf (buffer, "%s[", ri->vr_range ? "" : "~");
+ print_double_int (buffer, ri->min);
+ pp_printf (buffer, ", ");
+ print_double_int (buffer, ri->max);
+ pp_printf (buffer, "] VALID = %u ", ri->valid);
+ newline_and_indent (buffer, spc);
+ }
+
if (flags & TDF_RAW)
dump_gimple_fmt (buffer, spc, flags, "%G <%T, ", phi,
gimple_phi_result (phi));
@@ -1911,6 +1942,24 @@ pp_gimple_stmt_1 (pretty_printer *buffer, gimple gs, int spc, int flags)
}
}
+ if (gimple_has_lhs (gs))
+ {
+ tree lhs = gimple_get_lhs (gs);
+ if ((TREE_CODE (lhs) == SSA_NAME)
+ && !POINTER_TYPE_P (TREE_TYPE (lhs))
+ && SSA_NAME_RANGE_INFO (lhs))
+ {
+ struct range_info_def *ri = SSA_NAME_RANGE_INFO (lhs);
+ pp_printf (buffer, "# RANGE ");
+ pp_printf (buffer, "%s[", ri->vr_range ? "" : "~");
+ print_double_int (buffer, ri->min);
+ pp_printf (buffer, ", ");
+ print_double_int (buffer, ri->max);
+ pp_printf (buffer, "] VALID = %u ", ri->valid);
+ newline_and_indent (buffer, spc);
+ }
+ }
+
switch (gimple_code (gs))
{
case GIMPLE_ASM:
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index caa8d74..51546ce 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -147,6 +147,19 @@ struct GTY(()) ptr_info_def
unsigned int misalign;
};
+/* Value range information for SSA_NAMEs representing non-pointer variables. */
+
+struct GTY (()) range_info_def {
+ /* Minmum for value range. */
+ double_int min;
+ /* Maximum for value range. */
+ double_int max;
+ /* Set to true if VR_RANGE and false if VR_ANTI_RANGE. */
+ bool vr_range;
+ /* Set to true if range is valid. */
+ bool valid;
+};
+
/* It is advantageous to avoid things like life analysis for variables which
do not need PHI nodes. This enum describes whether or not a particular
@@ -526,12 +539,14 @@ extern tree make_ssa_name_fn (struct function *, tree, gimple);
extern tree copy_ssa_name_fn (struct function *, tree, gimple);
extern tree duplicate_ssa_name_fn (struct function *, tree, gimple);
extern void duplicate_ssa_name_ptr_info (tree, struct ptr_info_def *);
+extern void duplicate_ssa_name_range_info (tree, struct range_info_def *);
extern void release_ssa_name (tree);
extern void release_defs (gimple);
extern void replace_ssa_name_symbol (tree, tree);
extern bool get_ptr_info_alignment (struct ptr_info_def *, unsigned int *,
unsigned int *);
extern void mark_ptr_info_alignment_unknown (struct ptr_info_def *);
+extern void mark_range_info_unknown (struct range_info_def *);
extern void set_ptr_info_alignment (struct ptr_info_def *, unsigned int,
unsigned int);
extern void adjust_ptr_info_misalignment (struct ptr_info_def *,
diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
index 2ecd139..8ccecb5 100644
--- a/gcc/tree-ssa-alias.c
+++ b/gcc/tree-ssa-alias.c
@@ -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;
diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c
index 75ab54a..23f07e9 100644
--- a/gcc/tree-ssa-copy.c
+++ b/gcc/tree-ssa-copy.c
@@ -761,11 +761,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. */
diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c
index a6af3da..8750f11 100644
--- a/gcc/tree-ssanames.c
+++ b/gcc/tree-ssanames.c
@@ -151,7 +151,11 @@ make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
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));
@@ -163,6 +167,31 @@ make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
return t;
}
+/* Store range information MIN, MAX and VR_RANGE type
+ from value range propagation to tree ssa_name NAME. */
+
+void
+set_range_info (tree name, double_int min,
+ double_int max, bool vr_range)
+{
+ gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
+ gcc_assert (TREE_CODE (name) == SSA_NAME);
+ range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+
+ /* Allocate if not available. */
+ if (ri == NULL)
+ {
+ ri = ggc_alloc_cleared_range_info_def ();
+ mark_range_info_unknown (ri);
+ SSA_NAME_RANGE_INFO (name) = ri;
+ }
+
+ /* Set the values. */
+ ri->valid = true;
+ ri->min = min;
+ ri->max = max;
+ ri->vr_range = vr_range;
+}
/* We no longer need the SSA_NAME expression VAR, release it so that
it may be reused.
@@ -266,6 +295,14 @@ mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
pi->misalign = 0;
}
+/* Set the range described by RI has invalid values. */
+
+void
+mark_range_info_unknown (struct range_info_def *ri)
+{
+ ri->valid = false;
+}
+
/* Store the the power-of-two byte alignment and the deviation from that
alignment of pointer described by PI to ALIOGN and MISALIGN
respectively. */
@@ -359,6 +396,26 @@ duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
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. */
@@ -367,10 +424,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);
+ }
+ else
+ {
+ struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
- if (old_ptr_info)
- duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
+ if (old_range_info)
+ duplicate_ssa_name_range_info (new_name, old_range_info);
+ }
return new_name;
}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index ff82591..cb06793 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -3753,11 +3753,10 @@ extract_range_basic (value_range_t *vr, gimple stmt)
}
-/* Try to compute a useful range out of assignment STMT and store it
- in *VR. */
-
+/* Compute a useful range out of assignment STMT and store it
+ in VR. */
static void
-extract_range_from_assignment (value_range_t *vr, gimple stmt)
+extract_range_from_assignment_1 (value_range_t *vr, gimple stmt)
{
enum tree_code code = gimple_assign_rhs_code (stmt);
@@ -3787,6 +3786,19 @@ extract_range_from_assignment (value_range_t *vr, gimple stmt)
else
set_value_range_to_varying (vr);
+}
+
+/* Try to compute a useful range out of assignment STMT and store it
+ in *VR. */
+
+static void
+extract_range_from_assignment (value_range_t *vr, gimple stmt)
+{
+ extract_range_from_assignment_1 (vr, stmt);
+
+ /* If range is varying try to derive nonnegative or nonzero
+ range out of STMT relying primarily on generic routines
+ in fold in conjunction with range data. */
if (vr->type == VR_VARYING)
extract_range_basic (vr, stmt);
}
@@ -9124,6 +9136,34 @@ simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
{
enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
tree rhs1 = gimple_assign_rhs1 (stmt);
+ tree lhs = gimple_assign_lhs (stmt);
+
+ /* Set value range information for ssa. */
+ if (!POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
+ && (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
+ && !SSA_NAME_RANGE_INFO (lhs))
+ {
+ value_range_t vr = VR_INITIALIZER;
+
+ /* Extract the value range of assigned exprassion
+ not considering the lhs type. */
+ if ((gimple_assign_rhs_code (stmt) == NOP_EXPR)
+ || (gimple_assign_rhs_code (stmt) == CONVERT_EXPR))
+ extract_range_from_unary_expr (&vr, gimple_assign_rhs_code (stmt),
+ TREE_TYPE (rhs1),
+ gimple_assign_rhs1 (stmt));
+ else
+ extract_range_from_assignment_1 (&vr, stmt);
+
+ /* If value range is valid, set that. */
+ if ((vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
+ && range_int_cst_p (&vr))
+ set_range_info (lhs,
+ tree_to_double_int (vr.min),
+ tree_to_double_int (vr.max),
+ vr.type == VR_RANGE);
+ }
switch (rhs_code)
{
diff --git a/gcc/tree.h b/gcc/tree.h
index 94f112f..9330845 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -1950,10 +1950,19 @@ struct GTY(()) tree_exp {
/* 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.vrp.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.vrp.range_info
+
+/* Sets the value range extreacted from VRP into SSA. */
+void set_range_info (tree ssa, double_int min,
+ double_int max, bool vr_range);
/* Defined in tree-flow.h. */
struct ptr_info_def;
+struct range_info_def;
/* Immediate use linking structure. This structure is used for maintaining
a doubly linked list of uses of an SSA_NAME. */
@@ -1981,8 +1990,13 @@ 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 vrp_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.def_stmt && !POINTER_TYPE_P (TREE_TYPE ((tree)&%1))"))) vrp;
/* Immediate uses list for this SSA_NAME. */
struct ssa_use_operand_d imm_uses;
