Patchwork rtl expansion without zero/sign extension based on VRP

login
register
mail settings
Submitter Kugan
Date May 17, 2013, 11:40 a.m.
Message ID <5196171D.1030903@linaro.org>
Download mbox | patch
Permalink /patch/244618/
State New
Headers show

Comments

Kugan - May 17, 2013, 11:40 a.m.
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.
>>
>>
Richard Guenther - May 22, 2013, 10:28 a.m.
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.
>>>
>>>
>
>

Patch

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.  */