* rtl expansion without zero/sign extension based on VRP
@ 2013-05-13 3:45 Kugan
2013-05-13 8:17 ` Richard Biener
0 siblings, 1 reply; 4+ messages in thread
From: Kugan @ 2013-05-13 3:45 UTC (permalink / raw)
To: gcc-patches; +Cc: ebotcazou, ramana.radhakrishnan, Richard Earnshaw
[-- Attachment #1: Type: text/plain, Size: 1902 bytes --]
Hi,
This patch removes some of the redundant sign/zero
extensions using value ranges informations generated by VRP.
When GIMPLE_ASSIGN stmts with LHS type smaller than word is expanded to
rtl, if we can prove that RHS expression value can always fit in LHS
type and there is no sign conversion, truncation and extension to fit
the type is redundant. Subreg and Zero/sign extensions are therefore
redundant.
For example, when an expression is evaluated and it's value is assigned
to variable of type short, the generated rtl would look something like
the following.
(set (reg:SI 110)
(zero_extend:SI (subreg:HI (reg:SI 117) 0)))
However, if during value range propagation, if we can say for certain
that the value of the expression which is present in register 117 is
within the limits of short and there is no sign conversion, we don’t
need to perform the subreg and zero_extend; instead we can generate the
following rtl.
(set (reg:SI 110)
(reg:SI 117)))
Attached patch adds value range information to gimple stmts during value
range propagation pass and expands rtl without subreg and zero/sign
extension if the value range is within the limits of it's type.
This change improve the geomean of spec2k int benchmark with ref by
about ~3.5% on an arm chromebook.
Tested on X86_64 and ARM.
I would like review comments on this.
Thanks,
Kugan
2013-05-09 Kugan Vivekanandarajah <kuganv@linaro.org>
* gcc/gimple.h (gimple_is_exp_fit_lhs, gimple_set_exp_fit_lhs): New
function.
* gcc/tree-vrp.c (process_stmt_for_ext_elimination): Likewise.
* (is_msb_set, range_fits_type): Likewise.
* (vrp_finalize): Call process_stmt_for_ext_elimination.
* gcc/dojump.c (do_compare_and_jump): generates rtl without
zero/sign extension
if process_stmt_for_ext_elimination tells so.
* gcc/cfgexpand.c (expand_gimple_stmt_1): Likewise.
[-- Attachment #2: vrp_extension_elimination.diff --]
[-- Type: text/x-patch, Size: 12986 bytes --]
diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c
index c187273..c43468b 100644
--- a/gcc/cfgexpand.c
+++ b/gcc/cfgexpand.c
@@ -2279,6 +2279,7 @@ expand_gimple_stmt_1 (gimple stmt)
bool nontemporal = gimple_assign_nontemporal_move_p (stmt);
struct separate_ops ops;
bool promoted = false;
+ bool ext_redundant = false;
target = expand_expr (lhs, NULL_RTX, VOIDmode, EXPAND_WRITE);
if (GET_CODE (target) == SUBREG && SUBREG_PROMOTED_VAR_P (target))
@@ -2309,8 +2310,33 @@ expand_gimple_stmt_1 (gimple stmt)
temp = expand_expr_real_2 (&ops, temp, GET_MODE (target),
EXPAND_NORMAL);
+ /* During VRP if we detected extension as rdundant
+ and can be removed. */
+ if (promoted && gimple_is_exp_fit_lhs (stmt)
+ && is_gimple_assign (stmt)
+ && INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
+ {
+ rtx src = (GET_CODE (temp) == SUBREG)
+ ? SUBREG_REG (temp) : temp;
+ rtx dst = (GET_CODE (target) == SUBREG)
+ ? SUBREG_REG (target) : target;
+ if (GET_MODE (src) == GET_MODE (dst))
+ {
+ promoted = false;
+ ext_redundant = true;
+ }
+ }
+
if (temp == target)
;
+ else if (ext_redundant)
+ {
+ rtx src = (GET_CODE (temp) == SUBREG)
+ ? SUBREG_REG (temp) : temp;
+ rtx dst = (GET_CODE (target) == SUBREG)
+ ? SUBREG_REG (target) : target;
+ emit_move_insn (dst, src);
+ }
else if (promoted)
{
int unsignedp = SUBREG_PROMOTED_UNSIGNED_P (target);
diff --git a/gcc/dojump.c b/gcc/dojump.c
index 3f04eac..3336ff6 100644
--- a/gcc/dojump.c
+++ b/gcc/dojump.c
@@ -34,6 +34,7 @@ along with GCC; see the file COPYING3. If not see
#include "ggc.h"
#include "basic-block.h"
#include "tm_p.h"
+#include "gimple.h"
static bool prefer_and_bit_test (enum machine_mode, int);
static void do_jump_by_parts_greater (tree, tree, int, rtx, rtx, int);
@@ -1118,6 +1119,73 @@ do_compare_and_jump (tree treeop0, tree treeop1, enum rtx_code signed_code,
type = TREE_TYPE (treeop1);
mode = TYPE_MODE (type);
}
+
+ /* Is zero/sign extension redundant for op1 as per VRP. */
+ bool promoted1 = false;
+ if (GET_CODE (op0) == SUBREG && SUBREG_PROMOTED_VAR_P (op0))
+ promoted1 = true;
+ if (promoted1)
+ {
+ gimple stmt = SSA_NAME_DEF_STMT (treeop0);
+ if (!gimple_is_exp_fit_lhs (stmt))
+ {
+ promoted1 = false;
+ }
+ }
+
+ /* Is zero/sign extension redundant for op2 as per VRP. */
+ bool promoted2 = false;
+ if (GET_CODE (op1) == SUBREG && SUBREG_PROMOTED_VAR_P (op1))
+ promoted2 = true;
+ if (promoted2)
+ {
+ gimple stmt = SSA_NAME_DEF_STMT (treeop1);
+ if (!gimple_is_exp_fit_lhs (stmt))
+ {
+ promoted2 = false;
+ }
+ }
+
+ /* If zero/sign extension is redundant, generate RTL
+ for operands without zero/sign extension. */
+ if ((promoted1 || TREE_CODE (treeop0) == INTEGER_CST)
+ && (promoted2 || TREE_CODE (treeop1) == INTEGER_CST))
+ {
+ /* First operand is constant. */
+ if ((TREE_CODE (treeop1) == INTEGER_CST)
+ && (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (treeop1))) <= UNITS_PER_WORD))
+ {
+ rtx new_op0 = gen_reg_rtx (GET_MODE (SUBREG_REG (op0)));
+ emit_move_insn (new_op0, SUBREG_REG (op0));
+ op0 = new_op0;
+ }
+
+ /* Other operand is constant. */
+ else if ((TREE_CODE (treeop0) == INTEGER_CST)
+ && (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (treeop0)))
+ <= UNITS_PER_WORD))
+ {
+ rtx new_op1 = gen_reg_rtx (GET_MODE (SUBREG_REG (op1)));
+ emit_move_insn (new_op1, SUBREG_REG (op1));
+ op1 = new_op1;
+ }
+
+ /* both operands are not constant. */
+ else if ((TREE_CODE (treeop0) != INTEGER_CST)
+ && (TREE_CODE (treeop1) != INTEGER_CST))
+ {
+ rtx new_op0 = gen_reg_rtx (GET_MODE (SUBREG_REG (op0)));
+ emit_move_insn (new_op0, SUBREG_REG (op0));
+ rtx new_op1 = gen_reg_rtx (GET_MODE (SUBREG_REG (op1)));
+ emit_move_insn (new_op1, SUBREG_REG (op1));
+ if (GET_MODE (new_op0) == GET_MODE (new_op1))
+ {
+ op0 = new_op0;
+ op1 = new_op1;
+ }
+ }
+ }
+
unsignedp = TYPE_UNSIGNED (type);
code = unsignedp ? unsigned_code : signed_code;
diff --git a/gcc/gimple.h b/gcc/gimple.h
index b4de403..f0d5998 100644
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -191,6 +191,11 @@ struct GTY((chain_next ("%h.next"))) gimple_statement_base {
in there. */
unsigned int subcode : 16;
+ /* if an assignment gimple statement has RHS expression that can fit
+ LHS type, zero/sign extension to truncate is redundant.
+ Set this if we detect extension as redundant during VRP. */
+ unsigned sign_zero_ext_redundant : 1;
+
/* UID of this statement. This is used by passes that want to
assign IDs to statements. It must be assigned and used by each
pass. By default it should be assumed to contain garbage. */
@@ -1208,6 +1213,21 @@ set_bb_seq (basic_block bb, gimple_seq seq)
bb->il.gimple.seq = seq;
}
+/* returns the sign/zero extension redundant flag. */
+
+static inline bool
+gimple_is_exp_fit_lhs (gimple stmt)
+{
+ return stmt->gsbase.sign_zero_ext_redundant;
+}
+
+/* Sets the sign/zero extension redundant flag. */
+
+static inline void
+gimple_set_exp_fit_lhs (gimple stmt, bool val_p)
+{
+ stmt->gsbase.sign_zero_ext_redundant = val_p;
+}
/* Return the code for GIMPLE statement G. */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index b5de683..08f203b 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -9095,6 +9095,197 @@ simplify_stmt_for_jump_threading (gimple stmt, gimple within_stmt)
gimple_cond_rhs (stmt), within_stmt);
}
+/* Check to see if the value range can be safely contained in
+ with the type. i.e. zero/sign extension to truncate is redyndant. */
+static bool
+range_fits_type (value_range_t *vr, tree type)
+{
+ tree type_min = TYPE_MINVAL (type);
+ tree type_max = TYPE_MAXVAL (type);
+
+ if (vr->type != VR_RANGE
+ || is_overflow_infinity (vr->min)
+ || is_overflow_infinity (vr->max)
+ || is_negative_overflow_infinity (vr->min)
+ || is_negative_overflow_infinity (vr->max))
+ {
+ /* if value range overflows. */
+ return false;
+ }
+
+ bool unsigned_cmp = false;
+
+ /* Unsigged type and value range is positive. */
+ if (TYPE_UNSIGNED (type)
+ && value_range_nonnegative_p (vr))
+ {
+ unsigned_cmp = true;
+ }
+
+ if (unsigned_cmp)
+ {
+ /* unsigned type and positive value range. */
+ return INT_CST_LT_UNSIGNED (vr->max, type_max)
+ || operand_equal_p (vr->max, type_max, 0);
+ }
+ else
+ {
+ bool min_ok, max_ok;
+ /* signed comparision. */
+ min_ok = INT_CST_LT (type_min, vr->min)
+ || operand_equal_p (type_min, vr->min, 0);
+ max_ok = INT_CST_LT (vr->max, type_max)
+ || operand_equal_p (vr->max, type_max, 0);
+
+ return (min_ok && max_ok);
+ }
+}
+
+/* Check if the most significant bit in the value for the type is set.
+ if we are sure that msb is not set, return false.
+ If in doubt return true. */
+
+static bool
+is_msb_set (tree val, tree type)
+{
+ tree msb;
+
+ if (TREE_CODE (val) != INTEGER_CST || TYPE_SIZE (type) == NULL_TREE)
+ return true;
+
+ switch (GET_MODE_SIZE (TYPE_MODE (type)))
+ {
+ case 1:
+ msb = build_int_cstu (integer_type_node, 0x80);
+ break;
+ case 2:
+ msb = build_int_cstu (integer_type_node, 0x8000);
+ break;
+ case 4:
+ msb = build_int_cstu (integer_type_node, 0x80000000);
+ break;
+ default:
+ return true;
+ }
+
+ if (operand_less_p (val, msb) == 1)
+ return false;
+
+ return true;
+}
+
+
+/* process gimple assign stmts and see if the sign/zero extensions are
+ redundant. i.e. if an assignment gimple statement has RHS expression
+ value that can fit in LHS type, truncation is redundant. Zero/sign
+ extensions in this case can be removed.
+
+ Example, if the register 117 in the following rtl has a value range
+ that can fit in HImode, zero_extend here is redundant.
+ (set (reg:SI 110)
+ (zero_extend:SI (subreg:HI (reg:SI 117) 0)))
+
+ Therefore the zero_extend can be droped and we can generate the following
+ rtl instead
+ (set (reg:SI 110)
+ (reg:SI 117))
+
+ process_stmt_for_ext_elimination process GIMPLE_ASSIGN stmts based on the
+ VRP information and adds this information to the stmt. Later, when the
+ gimple is expanded to RTL, zero_extend/sign_extends are dropped if it is
+ redundant. */
+
+static void
+process_stmt_for_ext_elimination ()
+{
+ basic_block bb;
+ FOR_EACH_BB (bb)
+ {
+ gimple_stmt_iterator si;
+
+ for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+ {
+ gimple stmt = gsi_stmt (si);
+ /* Only interested in GIMPLE_ASSIGN. */
+ if (!stmt
+ || gimple_is_exp_fit_lhs (stmt)
+ || !is_gimple_assign (stmt))
+ continue;
+
+ enum tree_code stmt_code = gimple_assign_rhs_code (stmt);
+ tree lhs = gimple_get_lhs (stmt);
+ tree rhs1 = gimple_assign_rhs1 (stmt);
+ tree rhs2 = gimple_assign_rhs2 (stmt);
+
+ /* Skip if the lhs is not integeral. */
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+ || CONSTANT_CLASS_P (lhs))
+ continue;
+
+ /* Process unary assign stmt. */
+ if (TREE_CODE_CLASS (stmt_code) == tcc_unary)
+ {
+ value_range_t vr = VR_INITIALIZER;
+ value_range_t *p_vr = &vr;
+ if ((stmt_code == NOP_EXPR || stmt_code == CONVERT_EXPR)
+ && (TREE_CODE (rhs1) == SSA_NAME))
+ {
+ p_vr = get_value_range (rhs1);
+ }
+ else
+ {
+ /* Get the value range for the expression. */
+ extract_range_from_unary_expr (p_vr,
+ gimple_assign_rhs_code (stmt),
+ TREE_TYPE (rhs1), rhs1);
+ }
+ if (range_int_cst_p (p_vr))
+ {
+ if (range_fits_type (p_vr, TREE_TYPE (lhs)))
+ {
+ gimple_set_exp_fit_lhs (stmt, true);
+ gsi_set_stmt (&si, stmt);
+ }
+ }
+ }
+
+ /* Process binary assign stmt. */
+ else if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
+ == tcc_binary)
+ {
+ value_range_t vr = VR_INITIALIZER;
+ gcc_assert (rhs1);
+ gcc_assert (rhs2);
+
+ /* If MSB is set for the constant operand, RTL will
+ sign extend even when it is positive.
+ Skip such stmts for zero/sign extension processing. */
+
+ if ((CONSTANT_CLASS_P (rhs1)
+ && is_msb_set (rhs1, TREE_TYPE (lhs)))
+ || (CONSTANT_CLASS_P(rhs2)
+ && is_msb_set (rhs2, TREE_TYPE (lhs))))
+ {
+ continue;
+ }
+
+ /* Get the value range for the expression. */
+ extract_range_from_binary_expr (&vr,
+ gimple_assign_rhs_code (stmt),
+ TREE_TYPE (rhs1), rhs1, rhs2);
+ if (range_int_cst_p (&vr))
+ {
+ if (range_fits_type (&vr, TREE_TYPE (lhs)))
+ {
+ gimple_set_exp_fit_lhs (stmt, true);
+ gsi_set_stmt (&si, stmt);
+ }
+ }
+ }
+ }
+ }
+}
+
/* Blocks which have more than one predecessor and more than
one successor present jump threading opportunities, i.e.,
when the block is reached from a specific predecessor, we
@@ -9243,6 +9434,8 @@ vrp_finalize (void)
if (warn_array_bounds)
check_all_array_refs ();
+ process_stmt_for_ext_elimination ();
+
/* We must identify jump threading opportunities before we release
the datastructures built by VRP. */
identify_jump_threads ();
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: rtl expansion without zero/sign extension based on VRP
2013-05-13 3:45 rtl expansion without zero/sign extension based on VRP Kugan
@ 2013-05-13 8:17 ` Richard Biener
2013-05-17 11:40 ` Kugan
0 siblings, 1 reply; 4+ messages in thread
From: Richard Biener @ 2013-05-13 8:17 UTC (permalink / raw)
To: Kugan; +Cc: gcc-patches, ebotcazou, ramana.radhakrishnan, Richard Earnshaw
On Mon, May 13, 2013 at 5:45 AM, Kugan
<kugan.vivekanandarajah@linaro.org> wrote:
> Hi,
>
> This patch removes some of the redundant sign/zero
> extensions using value ranges informations generated by VRP.
>
> When GIMPLE_ASSIGN stmts with LHS type smaller than word is expanded to
> rtl, if we can prove that RHS expression value can always fit in LHS
> type and there is no sign conversion, truncation and extension to fit
> the type is redundant. Subreg and Zero/sign extensions are therefore
> redundant.
>
> For example, when an expression is evaluated and it's value is assigned
> to variable of type short, the generated rtl would look something like
> the following.
>
> (set (reg:SI 110)
> (zero_extend:SI (subreg:HI (reg:SI 117) 0)))
>
> However, if during value range propagation, if we can say for certain
> that the value of the expression which is present in register 117 is
> within the limits of short and there is no sign conversion, we don’t
> need to perform the subreg and zero_extend; instead we can generate the
> following rtl.
>
> (set (reg:SI 110)
> (reg:SI 117)))
>
> Attached patch adds value range information to gimple stmts during value
> range propagation pass and expands rtl without subreg and zero/sign
> extension if the value range is within the limits of it's type.
>
> This change improve the geomean of spec2k int benchmark with ref by about
> ~3.5% on an arm chromebook.
>
> Tested on X86_64 and ARM.
>
> I would like review comments on this.
A few comments on the way you preserve this information.
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -191,6 +191,11 @@ struct GTY((chain_next ("%h.next")))
gimple_statement_base {
in there. */
unsigned int subcode : 16;
+ /* if an assignment gimple statement has RHS expression that can fit
+ LHS type, zero/sign extension to truncate is redundant.
+ Set this if we detect extension as redundant during VRP. */
+ unsigned sign_zero_ext_redundant : 1;
+
this enlarges all gimple statements by 8 bytes, so it's out of the question.
My original plan to preserve value-range information was to re-use
SSA_NAME_PTR_INFO which is where we already store value-range
information for pointers:
struct GTY(()) ptr_info_def
{
/* The points-to solution. */
struct pt_solution pt;
/* Alignment and misalignment of the pointer in bytes. Together
align and misalign specify low known bits of the pointer.
ptr & (align - 1) == misalign. */
/* When known, this is the power-of-two byte alignment of the object this
pointer points into. This is usually DECL_ALIGN_UNIT for decls and
MALLOC_ABI_ALIGNMENT for allocated storage. When the alignment is not
known, it is zero. Do not access directly but use functions
get_ptr_info_alignment, set_ptr_info_alignment,
mark_ptr_info_alignment_unknown and similar. */
unsigned int align;
/* When alignment is known, the byte offset this pointer differs from the
above alignment. Access only through the same helper functions as align
above. */
unsigned int misalign;
};
what you'd do is to make the ptr_info_def reference from tree_ssa_name a
reference to a union of the above (for pointer SSA names) and an alternate
info like
struct range_info_def {
double_int min;
double_int max;
};
or a more compressed format (a reference to a mode or type it fits for example).
The very specific case in question also points at the fact that we have
two conversion tree codes, NOP_EXPR and CONVERT_EXPR, and we've
tried to unify them (but didn't finish up that task)...
+static void
+process_stmt_for_ext_elimination ()
+{
we already do all the analysis when looking for opportunities to eliminate
the intermediate cast in (T2)(T1)x in simplify_conversion_using_ranges,
that's the place that should handle this case.
Richard.
> Thanks,
> Kugan
>
>
> 2013-05-09 Kugan Vivekanandarajah <kuganv@linaro.org>
>
> * gcc/gimple.h (gimple_is_exp_fit_lhs, gimple_set_exp_fit_lhs): New
> function.
> * gcc/tree-vrp.c (process_stmt_for_ext_elimination): Likewise.
> * (is_msb_set, range_fits_type): Likewise.
> * (vrp_finalize): Call process_stmt_for_ext_elimination.
> * gcc/dojump.c (do_compare_and_jump): generates rtl without
> zero/sign extension
> if process_stmt_for_ext_elimination tells so.
> * gcc/cfgexpand.c (expand_gimple_stmt_1): Likewise.
>
>
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: rtl expansion without zero/sign extension based on VRP
2013-05-13 8:17 ` Richard Biener
@ 2013-05-17 11:40 ` Kugan
2013-05-22 10:29 ` Richard Biener
0 siblings, 1 reply; 4+ messages in thread
From: Kugan @ 2013-05-17 11:40 UTC (permalink / raw)
To: Richard Biener
Cc: gcc-patches, ebotcazou, ramana.radhakrishnan, Richard Earnshaw
[-- Attachment #1: Type: text/plain, Size: 5672 bytes --]
On 13/05/13 17:47, Richard Biener wrote:
> On Mon, May 13, 2013 at 5:45 AM, Kugan
> <kugan.vivekanandarajah@linaro.org> wrote:
>> Hi,
>>
>> This patch removes some of the redundant sign/zero
>> extensions using value ranges informations generated by VRP.
>>
>> When GIMPLE_ASSIGN stmts with LHS type smaller than word is expanded to
>> rtl, if we can prove that RHS expression value can always fit in LHS
>> type and there is no sign conversion, truncation and extension to fit
>> the type is redundant. Subreg and Zero/sign extensions are therefore
>> redundant.
>>
>> For example, when an expression is evaluated and it's value is assigned
>> to variable of type short, the generated rtl would look something like
>> the following.
>>
>> (set (reg:SI 110)
>> (zero_extend:SI (subreg:HI (reg:SI 117) 0)))
>>
>> However, if during value range propagation, if we can say for certain
>> that the value of the expression which is present in register 117 is
>> within the limits of short and there is no sign conversion, we don’t
>> need to perform the subreg and zero_extend; instead we can generate the
>> following rtl.
>>
>> (set (reg:SI 110)
>> (reg:SI 117)))
>>
>> Attached patch adds value range information to gimple stmts during value
>> range propagation pass and expands rtl without subreg and zero/sign
>> extension if the value range is within the limits of it's type.
>>
>> This change improve the geomean of spec2k int benchmark with ref by about
>> ~3.5% on an arm chromebook.
>>
>> Tested on X86_64 and ARM.
>>
>> I would like review comments on this.
>
> A few comments on the way you preserve this information.
>
Thanks Richard for reviewing it.
> --- a/gcc/gimple.h
> +++ b/gcc/gimple.h
> @@ -191,6 +191,11 @@ struct GTY((chain_next ("%h.next")))
> gimple_statement_base {
> in there. */
> unsigned int subcode : 16;
>
> + /* if an assignment gimple statement has RHS expression that can fit
> + LHS type, zero/sign extension to truncate is redundant.
> + Set this if we detect extension as redundant during VRP. */
> + unsigned sign_zero_ext_redundant : 1;
> +
>
> this enlarges all gimple statements by 8 bytes, so it's out of the question.
>
> My original plan to preserve value-range information was to re-use
> SSA_NAME_PTR_INFO which is where we already store value-range
> information for pointers:
>
> struct GTY(()) ptr_info_def
> {
> /* The points-to solution. */
> struct pt_solution pt;
>
> /* Alignment and misalignment of the pointer in bytes. Together
> align and misalign specify low known bits of the pointer.
> ptr & (align - 1) == misalign. */
>
> /* When known, this is the power-of-two byte alignment of the object this
> pointer points into. This is usually DECL_ALIGN_UNIT for decls and
> MALLOC_ABI_ALIGNMENT for allocated storage. When the alignment is not
> known, it is zero. Do not access directly but use functions
> get_ptr_info_alignment, set_ptr_info_alignment,
> mark_ptr_info_alignment_unknown and similar. */
> unsigned int align;
>
> /* When alignment is known, the byte offset this pointer differs from the
> above alignment. Access only through the same helper functions as align
> above. */
> unsigned int misalign;
> };
>
> what you'd do is to make the ptr_info_def reference from tree_ssa_name a
> reference to a union of the above (for pointer SSA names) and an alternate
> info like
>
> struct range_info_def {
> double_int min;
> double_int max;
> };
>
I have now changed the way I am preserving this information as you have
suggested.
> or a more compressed format (a reference to a mode or type it fits for example).
>
> The very specific case in question also points at the fact that we have
> two conversion tree codes, NOP_EXPR and CONVERT_EXPR, and we've
> tried to unify them (but didn't finish up that task)...
>
We can also remove sign/zero extension in cases other than NOP_EXPR and
CONVERT_EXPR, if the value range of the RHS expressions fits LHS type
without sign change.
For example, please look at the following gimple stmt and the resulting rtl:
;; c_3 = c_2(D) & 15;
;; Without the patch
(insn 6 5 7 (set (reg:SI 116)
(and:SI (reg/v:SI 115 [ c ])
(const_int 15 [0xf]))) c5.c:4 -1
(nil))
(insn 7 6 0 (set (reg/v:SI 111 [ c ])
(zero_extend:SI (subreg:QI (reg:SI 116) 0))) c5.c:4 -1
(nil))
;; with the patch
(insn 6 5 7 (set (reg:SI 116)
(and:SI (reg/v:SI 115 [ c ])
(const_int 15 [0xf]))) c5.c:4 -1
(nil))
(insn 7 6 0 (set (reg/v:SI 111 [ c ])
(reg:SI 116)) c5.c:4 -1
(nil))
> +static void
> +process_stmt_for_ext_elimination ()
> +{
>
> we already do all the analysis when looking for opportunities to eliminate
> the intermediate cast in (T2)(T1)x in simplify_conversion_using_ranges,
> that's the place that should handle this case.
>
I have changed this.
I have attached patch with the above changes.
Thanks,
Kugan
> Richard.
>
>> Thanks,
>> Kugan
>>
>>
>> 2013-05-09 Kugan Vivekanandarajah <kuganv@linaro.org>
>>
>> * gcc/gimple.h (gimple_is_exp_fit_lhs, gimple_set_exp_fit_lhs): New
>> function.
>> * gcc/tree-vrp.c (process_stmt_for_ext_elimination): Likewise.
>> * (is_msb_set, range_fits_type): Likewise.
>> * (vrp_finalize): Call process_stmt_for_ext_elimination.
>> * gcc/dojump.c (do_compare_and_jump): generates rtl without
>> zero/sign extension
>> if process_stmt_for_ext_elimination tells so.
>> * gcc/cfgexpand.c (expand_gimple_stmt_1): Likewise.
>>
>>
[-- Attachment #2: vrp_extension_elimination_r1.diff --]
[-- Type: text/x-patch, Size: 17667 bytes --]
diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c
index c187273..d7d47f9 100644
--- a/gcc/cfgexpand.c
+++ b/gcc/cfgexpand.c
@@ -2279,6 +2279,7 @@ expand_gimple_stmt_1 (gimple stmt)
bool nontemporal = gimple_assign_nontemporal_move_p (stmt);
struct separate_ops ops;
bool promoted = false;
+ bool ext_redundant = false;
target = expand_expr (lhs, NULL_RTX, VOIDmode, EXPAND_WRITE);
if (GET_CODE (target) == SUBREG && SUBREG_PROMOTED_VAR_P (target))
@@ -2309,8 +2310,34 @@ expand_gimple_stmt_1 (gimple stmt)
temp = expand_expr_real_2 (&ops, temp, GET_MODE (target),
EXPAND_NORMAL);
+ if (promoted
+ && !POINTER_TYPE_P (TREE_TYPE (lhs))
+ && tree_ssa_is_extension_redundant (lhs))
+ {
+ /* VRP detected extension as redundant. Remove it. */
+ rtx src = (GET_CODE (temp) == SUBREG)
+ ? SUBREG_REG (temp) : temp;
+ rtx dst = (GET_CODE (target) == SUBREG)
+ ? SUBREG_REG (target) : target;
+
+ if (GET_MODE (src) == GET_MODE (dst))
+ {
+ promoted = false;
+ ext_redundant = true;
+ }
+ }
+
if (temp == target)
;
+ else if (ext_redundant)
+ {
+ rtx src = (GET_CODE (temp) == SUBREG)
+ ? SUBREG_REG (temp) : temp;
+ rtx dst = (GET_CODE (target) == SUBREG)
+ ? SUBREG_REG (target) : target;
+
+ emit_move_insn (dst, src);
+ }
else if (promoted)
{
int unsignedp = SUBREG_PROMOTED_UNSIGNED_P (target);
diff --git a/gcc/dojump.c b/gcc/dojump.c
index 3f04eac..3c3505f 100644
--- a/gcc/dojump.c
+++ b/gcc/dojump.c
@@ -1118,6 +1118,58 @@ do_compare_and_jump (tree treeop0, tree treeop1, enum rtx_code signed_code,
type = TREE_TYPE (treeop1);
mode = TYPE_MODE (type);
}
+
+ /* Is zero/sign extension redundant as per VRP. */
+ bool op0_extension_redundant = false;
+ bool op1_extension_redundant = false;
+
+ if (GET_CODE (op0) == SUBREG && SUBREG_PROMOTED_VAR_P (op0))
+ op0_extension_redundant = tree_ssa_is_extension_redundant (treeop0);
+
+ if (GET_CODE (op1) == SUBREG && SUBREG_PROMOTED_VAR_P (op1))
+ op1_extension_redundant = tree_ssa_is_extension_redundant (treeop1);
+
+ /* If zero/sign extension is redundant, generate RTL
+ for operands without zero/sign extension. */
+ if ((op0_extension_redundant || TREE_CODE (treeop0) == INTEGER_CST)
+ && (op1_extension_redundant || TREE_CODE (treeop1) == INTEGER_CST))
+ {
+ if ((TREE_CODE (treeop1) == INTEGER_CST)
+ && (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (treeop1))) <= UNITS_PER_WORD))
+ {
+ /* First operand is constant. */
+ rtx new_op0 = gen_reg_rtx (GET_MODE (SUBREG_REG (op0)));
+
+ emit_move_insn (new_op0, SUBREG_REG (op0));
+ op0 = new_op0;
+ }
+ else if ((TREE_CODE (treeop0) == INTEGER_CST)
+ && (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (treeop0)))
+ <= UNITS_PER_WORD))
+ {
+ /* Other operand is constant. */
+ rtx new_op1 = gen_reg_rtx (GET_MODE (SUBREG_REG (op1)));
+
+ emit_move_insn (new_op1, SUBREG_REG (op1));
+ op1 = new_op1;
+ }
+ else if ((TREE_CODE (treeop0) != INTEGER_CST)
+ && (TREE_CODE (treeop1) != INTEGER_CST))
+ {
+ /* both operands are not constant. */
+ rtx new_op0 = gen_reg_rtx (GET_MODE (SUBREG_REG (op0)));
+ rtx new_op1 = gen_reg_rtx (GET_MODE (SUBREG_REG (op1)));
+
+ emit_move_insn (new_op0, SUBREG_REG (op0));
+ emit_move_insn (new_op1, SUBREG_REG (op1));
+ if (GET_MODE (new_op0) == GET_MODE (new_op1))
+ {
+ op0 = new_op0;
+ op1 = new_op1;
+ }
+ }
+ }
+
unsignedp = TYPE_UNSIGNED (type);
code = unsignedp ? unsigned_code : signed_code;
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index 01fe363..51074a3 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -147,6 +147,15 @@ struct GTY(()) ptr_info_def
unsigned int misalign;
};
+struct GTY (()) range_info_def {
+ double_int min;
+ double_int max;
+ /* if an assignment gimple statement has RHS expression that can fit
+ LHS type, zero/sign extension to truncate is redundant.
+ Set this if we detect extension as redundant during VRP. */
+ bool sign_zero_ext_redundant;
+};
+
/* 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
@@ -532,6 +541,7 @@ 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-ssanames.c b/gcc/tree-ssanames.c
index 0a405ce..4d6776d 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));
@@ -266,6 +270,14 @@ mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
pi->misalign = 0;
}
+/* State that the range described by RI has default values. */
+
+void
+mark_range_info_unknown (struct range_info_def *ri)
+{
+ ri->sign_zero_ext_redundant = 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 +371,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 +399,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 b5de683..6aa8551 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -8925,6 +8925,165 @@ simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
return true;
}
+/* Check to see if the value range can be safely contained in
+ with the type. i.e. zero/sign extension to truncate is redyndant. */
+static bool
+range_fits_type (value_range_t *vr, tree type)
+{
+ tree type_min = TYPE_MINVAL (type);
+ tree type_max = TYPE_MAXVAL (type);
+ bool unsigned_cmp = false;
+
+ /* if value range overflows. */
+ if (vr->type != VR_RANGE
+ || is_overflow_infinity (vr->min)
+ || is_overflow_infinity (vr->max)
+ || is_negative_overflow_infinity (vr->min)
+ || is_negative_overflow_infinity (vr->max))
+ return false;
+
+ /* Unsigged type and value range is positive. */
+ if (TYPE_UNSIGNED (type)
+ && value_range_nonnegative_p (vr))
+ unsigned_cmp = true;
+
+ if (unsigned_cmp)
+ {
+ /* unsigned type and positive value range. */
+ return INT_CST_LT_UNSIGNED (vr->max, type_max)
+ || operand_equal_p (vr->max, type_max, 0);
+ }
+ else
+ {
+ bool min_ok, max_ok;
+ /* signed comparision. */
+ min_ok = INT_CST_LT (type_min, vr->min)
+ || operand_equal_p (type_min, vr->min, 0);
+ max_ok = INT_CST_LT (vr->max, type_max)
+ || operand_equal_p (vr->max, type_max, 0);
+
+ return (min_ok && max_ok);
+ }
+}
+
+/* Check if the most significant bit in the value for the type is set.
+ if we are sure that msb is not set, return false.
+ If in doubt return true. */
+
+static bool
+is_msb_set (tree val, tree type)
+{
+ tree msb;
+
+ if (TREE_CODE (val) != INTEGER_CST || TYPE_SIZE (type) == NULL_TREE)
+ return true;
+
+ switch (GET_MODE_SIZE (TYPE_MODE (type)))
+ {
+ case 1:
+ msb = build_int_cstu (integer_type_node, 0x80);
+ break;
+ case 2:
+ msb = build_int_cstu (integer_type_node, 0x8000);
+ break;
+ case 4:
+ msb = build_int_cstu (integer_type_node, 0x80000000);
+ break;
+ default:
+ return true;
+ }
+
+ if (operand_less_p (val, msb) == 1)
+ return false;
+
+ return true;
+}
+
+
+/* process gimple assign stmts and see if the sign/zero extensions are
+ redundant. i.e. if an assignment gimple statement has RHS expression
+ value that can fit in LHS type, truncation is redundant. Zero/sign
+ extensions in this case can be removed.
+
+ Example, if the register 117 in the following rtl has a value range
+ that can fit in HImode, zero_extend here is redundant.
+ (set (reg:SI 110)
+ (zero_extend:SI (subreg:HI (reg:SI 117) 0)))
+
+ Therefore the zero_extend can be droped and we can generate the following
+ rtl instead
+ (set (reg:SI 110)
+ (reg:SI 117))
+
+ process GIMPLE_ASSIGN stmts based on the VRP information and return true if
+ tree_ssa assigned with this statement has redundant zero/sign extension;
+ false otherwise. */
+
+static bool
+is_zero_sign_extension_redundant (gimple stmt)
+{
+ enum tree_code stmt_code = gimple_assign_rhs_code (stmt);
+ tree lhs = gimple_get_lhs (stmt);
+ tree rhs1 = gimple_assign_rhs1 (stmt);
+
+ /* Skip if the lhs is not integeral. */
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+ || CONSTANT_CLASS_P (lhs))
+ return false;
+
+ /* Process unary assign stmt. */
+ if (TREE_CODE_CLASS (stmt_code) == tcc_unary)
+ {
+ value_range_t vr = VR_INITIALIZER;
+ value_range_t *p_vr = &vr;
+
+ /* Get the value range for the expression. */
+ if ((stmt_code == NOP_EXPR || stmt_code == CONVERT_EXPR)
+ && (TREE_CODE (rhs1) == SSA_NAME))
+ p_vr = get_value_range (rhs1);
+ else
+ extract_range_from_unary_expr (p_vr,
+ gimple_assign_rhs_code (stmt),
+ TREE_TYPE (rhs1), rhs1);
+ if (range_int_cst_p (p_vr))
+ {
+ if (range_fits_type (p_vr, TREE_TYPE (lhs)))
+ return true;
+ }
+ }
+ /* Process binary assign stmt. */
+ else if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
+ == tcc_binary)
+ {
+ value_range_t vr = VR_INITIALIZER;
+ tree rhs2 = gimple_assign_rhs2 (stmt);
+ gcc_assert (rhs1);
+ gcc_assert (rhs2);
+
+ /* If MSB is set for the constant operand, RTL will
+ sign extend even when it is positive.
+ Skip such stmts for zero/sign extension processing. */
+
+ if ((CONSTANT_CLASS_P (rhs1)
+ && is_msb_set (rhs1, TREE_TYPE (lhs)))
+ || (CONSTANT_CLASS_P(rhs2)
+ && is_msb_set (rhs2, TREE_TYPE (lhs))))
+ return false;
+
+ /* Get the value range for the expression. */
+ extract_range_from_binary_expr (&vr,
+ gimple_assign_rhs_code (stmt),
+ TREE_TYPE (rhs1), rhs1, rhs2);
+ if (range_int_cst_p (&vr))
+ {
+ if (range_fits_type (&vr, TREE_TYPE (lhs)))
+ return true;
+ }
+ }
+
+ return false;
+}
+
/* Simplify STMT using ranges if possible. */
static bool
@@ -8936,6 +9095,12 @@ simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
tree rhs1 = gimple_assign_rhs1 (stmt);
+ /* check if zero/sign extension is redundant for ssa defined
+ statement and update if it is. */
+ if (!POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
+ && is_zero_sign_extension_redundant (stmt))
+ tree_ssa_set_extension_redundant (gimple_assign_lhs (stmt), true);
+
switch (rhs_code)
{
case EQ_EXPR:
diff --git a/gcc/tree.c b/gcc/tree.c
index d93c6ae..ca13daf 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -269,6 +269,63 @@ const char * const omp_clause_code_name[] =
"mergeable"
};
+/* Return the value range info type for ssa. */
+
+int
+tree_ssa_vrp_info_type (tree_ssa_name *ssa)
+{
+ gcc_assert (ssa);
+ gimple stmt = ssa->def_stmt;
+
+ /* if not a pointer type, it is range_info. */
+ if (stmt && is_gimple_assign (stmt))
+ {
+ tree lhs = gimple_assign_lhs (stmt);
+ if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
+ return TREE_SSA_RANGE_INFO;
+ }
+
+ return TREE_SSA_PTR_INFO;
+}
+
+/* Is zero/sign extension redundant for an ssa def stmt. */
+
+bool
+tree_ssa_is_extension_redundant (tree ssa)
+{
+ gcc_assert (TREE_CODE (ssa) == SSA_NAME);
+ gimple stmt = SSA_NAME_DEF_STMT (ssa);
+
+ if (is_gimple_assign (stmt))
+ {
+ range_info_def *ri = SSA_NAME_RANGE_INFO (ssa);
+
+ if (ri && ri->sign_zero_ext_redundant)
+ return true;
+ }
+
+ return false;
+}
+
+/* Set zero/sign extension redundant for ssa def stmt. */
+
+void
+tree_ssa_set_extension_redundant (tree ssa, bool val)
+{
+ gimple stmt = SSA_NAME_DEF_STMT (ssa);
+ gcc_assert (!POINTER_TYPE_P (TREE_TYPE (ssa)));
+ gcc_assert (TREE_CODE (ssa) == SSA_NAME);
+ range_info_def *ri = SSA_NAME_RANGE_INFO (ssa);
+
+ if (ri == NULL)
+ {
+ ri = ggc_alloc_cleared_range_info_def ();
+ mark_range_info_unknown (ri);
+ SSA_NAME_RANGE_INFO (ssa) = ri;
+ }
+
+ ri->sign_zero_ext_redundant = val;
+}
/* Return the tree node structure used by tree code CODE. */
diff --git a/gcc/tree.h b/gcc/tree.h
index a46d276..58ca396 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -1950,10 +1950,15 @@ 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
+
+/* 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
/* 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. */
@@ -1969,6 +1974,12 @@ typedef struct GTY(()) ssa_use_operand_d {
tree *GTY((skip(""))) use;
} ssa_use_operand_t;
+
+/* The garbage collector needs to know the interpretation of the
+ value range info in the tree_ssa_name. */
+#define TREE_SSA_PTR_INFO (0)
+#define TREE_SSA_RANGE_INFO (1)
+
/* Return the immediate_use information for an SSA_NAME. */
#define SSA_NAME_IMM_USE_NODE(NODE) SSA_NAME_CHECK (NODE)->ssa_name.imm_uses
@@ -1981,8 +1992,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 ("TREE_SSA_PTR_INFO"))) ptr_info_def *ptr_info;
+ /* range attributes used for zero/sign extension elimination. */
+ struct GTY ((tag ("TREE_SSA_RANGE_INFO"))) range_info_def *range_info;
+ } GTY ((desc ("tree_ssa_vrp_info_type (&%1)"))) vrp;
/* Immediate uses list for this SSA_NAME. */
struct ssa_use_operand_d imm_uses;
@@ -5361,6 +5377,15 @@ extern tree skip_simple_constant_arithmetic (tree);
enum tree_node_structure_enum tree_node_structure (const_tree);
+/* Return the value range info type for ssa. */
+int tree_ssa_vrp_info_type (tree_ssa_name *);
+
+/* Is zero/sign extension redundant for an ssa def stmt. */
+bool tree_ssa_is_extension_redundant (tree);
+
+/* set zero/sign extension redundant for an ssa def stmt. */
+void tree_ssa_set_extension_redundant (tree ssa, bool val);
+
/* Return true if EXP contains a PLACEHOLDER_EXPR, i.e. if it represents a
size or offset that depends on a field within a record. */
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: rtl expansion without zero/sign extension based on VRP
2013-05-17 11:40 ` Kugan
@ 2013-05-22 10:29 ` Richard Biener
0 siblings, 0 replies; 4+ messages in thread
From: Richard Biener @ 2013-05-22 10:29 UTC (permalink / raw)
To: Kugan; +Cc: gcc-patches, ebotcazou, ramana.radhakrishnan, Richard Earnshaw
On Fri, May 17, 2013 at 1:40 PM, Kugan
<kugan.vivekanandarajah@linaro.org> wrote:
> On 13/05/13 17:47, Richard Biener wrote:
>>
>> On Mon, May 13, 2013 at 5:45 AM, Kugan
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>
>>> Hi,
>>>
>>> This patch removes some of the redundant sign/zero
>>> extensions using value ranges informations generated by VRP.
>>>
>>> When GIMPLE_ASSIGN stmts with LHS type smaller than word is expanded to
>>> rtl, if we can prove that RHS expression value can always fit in LHS
>>> type and there is no sign conversion, truncation and extension to fit
>>> the type is redundant. Subreg and Zero/sign extensions are therefore
>>> redundant.
>>>
>>> For example, when an expression is evaluated and it's value is assigned
>>> to variable of type short, the generated rtl would look something like
>>> the following.
>>>
>>> (set (reg:SI 110)
>>> (zero_extend:SI (subreg:HI (reg:SI 117) 0)))
>>>
>>> However, if during value range propagation, if we can say for certain
>>> that the value of the expression which is present in register 117 is
>>> within the limits of short and there is no sign conversion, we don’t
>>> need to perform the subreg and zero_extend; instead we can generate the
>>> following rtl.
>>>
>>> (set (reg:SI 110)
>>> (reg:SI 117)))
>>>
>>> Attached patch adds value range information to gimple stmts during value
>>> range propagation pass and expands rtl without subreg and zero/sign
>>> extension if the value range is within the limits of it's type.
>>>
>>> This change improve the geomean of spec2k int benchmark with ref by about
>>> ~3.5% on an arm chromebook.
>>>
>>> Tested on X86_64 and ARM.
>>>
>>> I would like review comments on this.
>>
>>
>> A few comments on the way you preserve this information.
>>
>
> Thanks Richard for reviewing it.
>
>
>> --- a/gcc/gimple.h
>> +++ b/gcc/gimple.h
>> @@ -191,6 +191,11 @@ struct GTY((chain_next ("%h.next")))
>> gimple_statement_base {
>> in there. */
>> unsigned int subcode : 16;
>>
>> + /* if an assignment gimple statement has RHS expression that can fit
>> + LHS type, zero/sign extension to truncate is redundant.
>> + Set this if we detect extension as redundant during VRP. */
>> + unsigned sign_zero_ext_redundant : 1;
>> +
>>
>> this enlarges all gimple statements by 8 bytes, so it's out of the
>> question.
>>
>> My original plan to preserve value-range information was to re-use
>> SSA_NAME_PTR_INFO which is where we already store value-range
>> information for pointers:
>>
>> struct GTY(()) ptr_info_def
>> {
>> /* The points-to solution. */
>> struct pt_solution pt;
>>
>> /* Alignment and misalignment of the pointer in bytes. Together
>> align and misalign specify low known bits of the pointer.
>> ptr & (align - 1) == misalign. */
>>
>> /* When known, this is the power-of-two byte alignment of the object
>> this
>> pointer points into. This is usually DECL_ALIGN_UNIT for decls and
>> MALLOC_ABI_ALIGNMENT for allocated storage. When the alignment is
>> not
>> known, it is zero. Do not access directly but use functions
>> get_ptr_info_alignment, set_ptr_info_alignment,
>> mark_ptr_info_alignment_unknown and similar. */
>> unsigned int align;
>>
>> /* When alignment is known, the byte offset this pointer differs from
>> the
>> above alignment. Access only through the same helper functions as
>> align
>> above. */
>> unsigned int misalign;
>> };
>>
>> what you'd do is to make the ptr_info_def reference from tree_ssa_name a
>> reference to a union of the above (for pointer SSA names) and an alternate
>> info like
>>
>> struct range_info_def {
>> double_int min;
>> double_int max;
>> };
>>
>
> I have now changed the way I am preserving this information as you have
> suggested.
>
>
>> or a more compressed format (a reference to a mode or type it fits for
>> example).
>>
>> The very specific case in question also points at the fact that we have
>> two conversion tree codes, NOP_EXPR and CONVERT_EXPR, and we've
>> tried to unify them (but didn't finish up that task)...
>>
>
> We can also remove sign/zero extension in cases other than NOP_EXPR and
> CONVERT_EXPR, if the value range of the RHS expressions fits LHS type
> without sign change.
>
> For example, please look at the following gimple stmt and the resulting rtl:
>
> ;; c_3 = c_2(D) & 15;
>
> ;; Without the patch
> (insn 6 5 7 (set (reg:SI 116)
> (and:SI (reg/v:SI 115 [ c ])
> (const_int 15 [0xf]))) c5.c:4 -1
> (nil))
>
> (insn 7 6 0 (set (reg/v:SI 111 [ c ])
> (zero_extend:SI (subreg:QI (reg:SI 116) 0))) c5.c:4 -1
> (nil))
>
> ;; with the patch
> (insn 6 5 7 (set (reg:SI 116)
> (and:SI (reg/v:SI 115 [ c ])
> (const_int 15 [0xf]))) c5.c:4 -1
> (nil))
>
> (insn 7 6 0 (set (reg/v:SI 111 [ c ])
> (reg:SI 116)) c5.c:4 -1
> (nil))
>
>
>
>> +static void
>> +process_stmt_for_ext_elimination ()
>> +{
>>
>> we already do all the analysis when looking for opportunities to eliminate
>> the intermediate cast in (T2)(T1)x in simplify_conversion_using_ranges,
>> that's the place that should handle this case.
>>
> I have changed this.
>
>
> I have attached patch with the above changes.
Quick comments below
+ /* value range information. */
+ union vrp_info_type {
+ /* Pointer attributes used for alias analysis. */
+ struct GTY ((tag ("TREE_SSA_PTR_INFO"))) ptr_info_def *ptr_info;
+ /* range attributes used for zero/sign extension elimination. */
+ struct GTY ((tag ("TREE_SSA_RANGE_INFO"))) range_info_def *range_info;
+ } GTY ((desc ("tree_ssa_vrp_info_type (&%1)"))) vrp;
I think desc ("POINTER_TYPE_P (TREE_TYPE (&%1))") and re-ordering
of the union members would have worked, too?
+struct GTY (()) range_info_def {
+ double_int min;
+ double_int max;
+ /* if an assignment gimple statement has RHS expression that can fit
+ LHS type, zero/sign extension to truncate is redundant.
+ Set this if we detect extension as redundant during VRP. */
+ bool sign_zero_ext_redundant;
+};
the sign_zero_ext_redundant flag is redundant I think. Also instead of
post-processing the expand_expr_real_2 output in expand_gimple_stmt
you should adjust the CASE_CONVERT case and/or the REDUCE_BITFIELD
handling in expand_expr_real_2 to check whether the source operand
value-range fits in the destination. Also note that this may be highly
target specific and simply dropping SUBREGs and then emitting a move
insn like you do looks odd.
AFAIK you can at most remove truncations of > word_mode registers
as SUBREGs behave differently (see also STRICT_LOW_PART).
That said - you need to find another reviewer for the RTL expansion pieces.
Can you split the patch into a piece introducing range_info_def and just
populate the min/max members from VRP before we call substitute_and_fold?
You probably want to add a flag for whether the min/max pair represents a
range or an anti-range as well.
Thanks,
Richard.
>
> Thanks,
> Kugan
>
>> Richard.
>>
>>> Thanks,
>>> Kugan
>>>
>>>
>>> 2013-05-09 Kugan Vivekanandarajah <kuganv@linaro.org>
>>>
>>> * gcc/gimple.h (gimple_is_exp_fit_lhs, gimple_set_exp_fit_lhs): New
>>> function.
>>> * gcc/tree-vrp.c (process_stmt_for_ext_elimination): Likewise.
>>> * (is_msb_set, range_fits_type): Likewise.
>>> * (vrp_finalize): Call process_stmt_for_ext_elimination.
>>> * gcc/dojump.c (do_compare_and_jump): generates rtl without
>>> zero/sign extension
>>> if process_stmt_for_ext_elimination tells so.
>>> * gcc/cfgexpand.c (expand_gimple_stmt_1): Likewise.
>>>
>>>
>
>
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2013-05-22 10:29 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-05-13 3:45 rtl expansion without zero/sign extension based on VRP Kugan
2013-05-13 8:17 ` Richard Biener
2013-05-17 11:40 ` Kugan
2013-05-22 10:29 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).