diff mbox

[RFC,2/3] Propagate and save value ranges wrapped information

Message ID 55381C83.4040304@linaro.org
State New
Headers show

Commit Message

Kugan Vivekanandarajah April 22, 2015, 10:11 p.m. UTC 
On 19/01/15 22:28, Richard Biener wrote:
> On Sat, 17 Jan 2015, Kugan wrote:
> 
>>
>> This patch propagate value range wrapps attribute and save this to
>> SSA_NAME.
> 
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 9b7695d..832c35d 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -103,6 +103,9 @@ struct value_range_d
>    tree min;
>    tree max;
>  
> +  /* Set to true if values in this value range could wrapp. */
> +  bool is_wrapped;
> +
>    /* Set of SSA names whose value ranges are equivalent to this one.
>       This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE.  */
>    bitmap equiv;
> 
> I can't make sense of this description (wrap with one p as well).
> I assume you mean that the expression that has this value-range
> assigned has an operation that may have wrapped?  (a value
> can't wrap)
> 
> You need to specify how is_wrapped behaves for range union and
> intersect operations and which operations can wrap.
> 
> I miss an overall description of these patches as to a) why you
> need this information and b) why it helps.
> 
> It's now also too late and thus you have plenty of time until stage1
> starts again.


Thanks Richard for the comments. Now that stage1 is open, here is the
modified patch with the changes requested.

Due to wrapping in the value range computation, there was a regression
in aplha-linux
(https://gcc.gnu.org/ml/gcc-patches/2014-08/msg02458.html) while using
value range infromation to remove zero/sign extensions in rtl
expansaion. Hence I had to revert the patch that enabled zero/sign
extension. Now I am propgating this wrap_p information to SSA_NAME so
that we know, when used in PROMOTE_MODE, the values can have
unpredictable bits beyon the type width.

I have also updated the comments as below:


+  /* Set to true if the values in this range might have been wrapped
+     during the operation that computed it.
+
+     This is mainly used in zero/sign-extension elimination where value
ranges
+     computed are for the type of SSA_NAME and computation is
ultimately done
+     in PROMOTE_MODE.  Therefore, the value ranges has to be correct upto
+     PROMOTE_MODE precision.  If the operation can WRAP, higher bits in
+     PROMOTE_MODE can be unpredictable and cannot be used in zero/sign
extension
+     elimination; additional wrap_p attribute is needed to show this.
+
+     For example:
+     on alpha where PROMOTE_MODE is 64 bit and _344 is a 32 bit unsigned
+     variable,
+     _343 = ivtmp.179_52 + 2147483645;      [0x80000004, 0x800000043]
+
+     the value range VRP will compute is:
+
+     _344 = _343 * 2;			[0x8, 0x86]
+     _345 = (integer(kind=4)) _344;	[0x8, 0x86]
+
+     In PROMOTE_MODE, there will be garbage above the type width.  In
places
+     like this, attribute wrap_p will be true.
+
+     wrap_p in range union operation will be true if either of the
value range
+     has wrap_p set.  In intersect operation, true when both the value
ranges
+     have wrap_p set.  */
+  bool wrap_p;
+

Thanks,
Kugan


gcc/testsuite/ChangeLog:

2015-04-22  Kugan Vivekanandarajah  <kuganv@linaro.org>

	* gcc.dg/tree-ssa/vrp92.c: Update scanned pattern.

gcc/ChangeLog:

2015-04-22  Kugan Vivekanandarajah  <kuganv@linaro.org>

	* builtins.c (determine_block_size): Use new definition of
	 get_range_info.
	* gimple-pretty-print.c (dump_ssaname_info): Dump new wrap_p info.
	* internal-fn.c (get_range_pos_neg): Use new definition of
	 get_range_info.
	(get_min_precision): Likewise.
	* tree-ssa-copy.c (fini_copy_prop): Use new definition of
	 duplicate_ssa_range_info.
	* tree-ssa-pre.c (insert_into_preds_of_block): Likewise.
	(move_computations_dom_walker::before_dom_children): Likewise.
	* tree-ssa-phiopt.c (value_replacement): Likewise.
	* tree-ssa-pre.c (eliminate_dom_walker::before_dom_children):
	Likewise.
	* tree-ssa-loop-niter.c (determine_value_range): Use new definition.
	(record_nonwrapping_iv): Likewise.
	* tree-ssanames.c (set_range_info): Save wrap_p information.
	(get_range_info): Retrive wrap_p information.
	(set_nonzero_bits): Set wrap_p info.
	(duplicate_ssa_name_range_info): Likewise.
	(duplicate_ssa_name_fn): Likewise.
	* tree-ssanames.h: (set_range_info): Update definition.
	(get_range_info): Likewise.
	* tree-vect-patterns.c (vect_recog_divmod_pattern): Use new
	declaration get_range_info.
	* tree-vrp.c (struct value_range_d): Add wrap_p field.
	(set_value_range): Calculate and add wrap_p field.
	(set_and_canonicalize_value_range): Likewise.
	(copy_value_range): Likewise.
	(set_value_range_to_value): Likewise.
	(set_value_range_to_nonnegative): Likewise.
	(set_value_range_to_nonnull): Likewise.
	(set_value_range_to_truthvalue): Likewise.
	(abs_extent_range): Likewise.
	(get_value_range): Return wrap_p info.
	(update_value_range): Save wrap_p info.
	(extract_range_from_assert): Extract and update wrap_p info.
	(extract_range_from_ssa_name): Likewise.
	(vrp_int_const_binop): Likewise.
	(ranges_from_anti_range): Likewise.
	(extract_range_from_multiplicative_op_1): Likewise.
	(extract_range_from_binary_expr_1): Likewise.
	(extract_range_from_binary_expr): Likewise.
	(extract_range_from_unary_expr_1): Likewise.
	(extract_range_from_comparison): Likewise.
	(extract_range_basic): Likewise.
	(adjust_range_with_scev): Likewise.
	(dump_value_range): Dump wrap_p info.
	(remove_range_assertions): Update parameters.
	(vrp_intersect_ranges_1): Propagate wrap_p info.
	(vrp_meet_1): Likewise.
	(vrp_visit_phi_node): Save wrap_p info to SSA.
	(vrp_finalize): Likewise.
	* tree.h (SSA_NAME_ANTI_RANGE_P): Remove.
	(SSA_NAME_RANGE_WRAP_P): New.

Comments

Richard Biener April 30, 2015, 11:35 a.m. UTC | #1 
On Thu, Apr 23, 2015 at 12:11 AM, Kugan
<kugan.vivekanandarajah@linaro.org> wrote:
>
> On 19/01/15 22:28, Richard Biener wrote:
>> On Sat, 17 Jan 2015, Kugan wrote:
>>
>>>
>>> This patch propagate value range wrapps attribute and save this to
>>> SSA_NAME.
>>
>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>> index 9b7695d..832c35d 100644
>> --- a/gcc/tree-vrp.c
>> +++ b/gcc/tree-vrp.c
>> @@ -103,6 +103,9 @@ struct value_range_d
>>    tree min;
>>    tree max;
>>
>> +  /* Set to true if values in this value range could wrapp. */
>> +  bool is_wrapped;
>> +
>>    /* Set of SSA names whose value ranges are equivalent to this one.
>>       This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE.  */
>>    bitmap equiv;
>>
>> I can't make sense of this description (wrap with one p as well).
>> I assume you mean that the expression that has this value-range
>> assigned has an operation that may have wrapped?  (a value
>> can't wrap)
>>
>> You need to specify how is_wrapped behaves for range union and
>> intersect operations and which operations can wrap.
>>
>> I miss an overall description of these patches as to a) why you
>> need this information and b) why it helps.
>>
>> It's now also too late and thus you have plenty of time until stage1
>> starts again.
>
>
> Thanks Richard for the comments. Now that stage1 is open, here is the
> modified patch with the changes requested.
>
> Due to wrapping in the value range computation, there was a regression
> in aplha-linux
> (https://gcc.gnu.org/ml/gcc-patches/2014-08/msg02458.html) while using
> value range infromation to remove zero/sign extensions in rtl
> expansaion. Hence I had to revert the patch that enabled zero/sign
> extension. Now I am propgating this wrap_p information to SSA_NAME so
> that we know, when used in PROMOTE_MODE, the values can have
> unpredictable bits beyon the type width.
>
> I have also updated the comments as below:
>
>
> +  /* Set to true if the values in this range might have been wrapped
> +     during the operation that computed it.
> +
> +     This is mainly used in zero/sign-extension elimination where value
> ranges
> +     computed are for the type of SSA_NAME and computation is
> ultimately done
> +     in PROMOTE_MODE.  Therefore, the value ranges has to be correct upto
> +     PROMOTE_MODE precision.  If the operation can WRAP, higher bits in
> +     PROMOTE_MODE can be unpredictable and cannot be used in zero/sign
> extension
> +     elimination; additional wrap_p attribute is needed to show this.
> +
> +     For example:
> +     on alpha where PROMOTE_MODE is 64 bit and _344 is a 32 bit unsigned
> +     variable,
> +     _343 = ivtmp.179_52 + 2147483645;      [0x80000004, 0x800000043]
> +
> +     the value range VRP will compute is:
> +
> +     _344 = _343 * 2;                  [0x8, 0x86]
> +     _345 = (integer(kind=4)) _344;    [0x8, 0x86]
> +
> +     In PROMOTE_MODE, there will be garbage above the type width.  In
> places
> +     like this, attribute wrap_p will be true.
> +
> +     wrap_p in range union operation will be true if either of the
> value range
> +     has wrap_p set.  In intersect operation, true when both the value
> ranges
> +     have wrap_p set.  */
> +  bool wrap_p;
> +

So what you'd like to know is whether the value range is the same if
all operations were carried out in infinite precision (well, in PROMOTE_MODE
precision).

I'm not sure you can simply assert that we didn't wrap for example in
extract_range_from_assert.  Consider your above code and

  if (_344 < 0x87)
    {
      _346 = ASSERT_EXPR <_344, _344 < 0x87>;
...

_346 definitely should have wrap_p set.

That said, I'm not convinced this is a sustainable approach to the issue.

I've long pondered with replacing the VRP overflow checking code
(for -fstrict-overflow) with keeping two lattices - one honoring undefined
overflow and one not and then comparing the results in the end.

A similar approach could be used for your wrap_p flag.

BUT ... a way more sensible approach to reduce the required sign/zero
extensions for PROMOTE_MODE targets is to lower the IL earlier,
before we perform the 2nd VRP run and thus have the sign-/zero-extensions
being eliminated by GIMPLE optimizers rather than only at RTL time.

ISTR you (or somebody else) played with that a bit?

Thanks,
Richard.

> Thanks,
> Kugan
>
>
> gcc/testsuite/ChangeLog:
>
> 2015-04-22  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>         * gcc.dg/tree-ssa/vrp92.c: Update scanned pattern.
>
> gcc/ChangeLog:
>
> 2015-04-22  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>         * builtins.c (determine_block_size): Use new definition of
>          get_range_info.
>         * gimple-pretty-print.c (dump_ssaname_info): Dump new wrap_p info.
>         * internal-fn.c (get_range_pos_neg): Use new definition of
>          get_range_info.
>         (get_min_precision): Likewise.
>         * tree-ssa-copy.c (fini_copy_prop): Use new definition of
>          duplicate_ssa_range_info.
>         * tree-ssa-pre.c (insert_into_preds_of_block): Likewise.
>         (move_computations_dom_walker::before_dom_children): Likewise.
>         * tree-ssa-phiopt.c (value_replacement): Likewise.
>         * tree-ssa-pre.c (eliminate_dom_walker::before_dom_children):
>         Likewise.
>         * tree-ssa-loop-niter.c (determine_value_range): Use new definition.
>         (record_nonwrapping_iv): Likewise.
>         * tree-ssanames.c (set_range_info): Save wrap_p information.
>         (get_range_info): Retrive wrap_p information.
>         (set_nonzero_bits): Set wrap_p info.
>         (duplicate_ssa_name_range_info): Likewise.
>         (duplicate_ssa_name_fn): Likewise.
>         * tree-ssanames.h: (set_range_info): Update definition.
>         (get_range_info): Likewise.
>         * tree-vect-patterns.c (vect_recog_divmod_pattern): Use new
>         declaration get_range_info.
>         * tree-vrp.c (struct value_range_d): Add wrap_p field.
>         (set_value_range): Calculate and add wrap_p field.
>         (set_and_canonicalize_value_range): Likewise.
>         (copy_value_range): Likewise.
>         (set_value_range_to_value): Likewise.
>         (set_value_range_to_nonnegative): Likewise.
>         (set_value_range_to_nonnull): Likewise.
>         (set_value_range_to_truthvalue): Likewise.
>         (abs_extent_range): Likewise.
>         (get_value_range): Return wrap_p info.
>         (update_value_range): Save wrap_p info.
>         (extract_range_from_assert): Extract and update wrap_p info.
>         (extract_range_from_ssa_name): Likewise.
>         (vrp_int_const_binop): Likewise.
>         (ranges_from_anti_range): Likewise.
>         (extract_range_from_multiplicative_op_1): Likewise.
>         (extract_range_from_binary_expr_1): Likewise.
>         (extract_range_from_binary_expr): Likewise.
>         (extract_range_from_unary_expr_1): Likewise.
>         (extract_range_from_comparison): Likewise.
>         (extract_range_basic): Likewise.
>         (adjust_range_with_scev): Likewise.
>         (dump_value_range): Dump wrap_p info.
>         (remove_range_assertions): Update parameters.
>         (vrp_intersect_ranges_1): Propagate wrap_p info.
>         (vrp_meet_1): Likewise.
>         (vrp_visit_phi_node): Save wrap_p info to SSA.
>         (vrp_finalize): Likewise.
>         * tree.h (SSA_NAME_ANTI_RANGE_P): Remove.
>         (SSA_NAME_RANGE_WRAP_P): New.
Jakub Jelinek April 30, 2015, 11:40 a.m. UTC | #2 
On Thu, Apr 30, 2015 at 01:35:25PM +0200, Richard Biener wrote:
> I've long pondered with replacing the VRP overflow checking code
> (for -fstrict-overflow) with keeping two lattices - one honoring undefined
> overflow and one not and then comparing the results in the end.

Yeah, that would be greatly appreciated.  The (OVF) stuff is complete mess.

	Jakub
Richard Biener April 30, 2015, 12:12 p.m. UTC | #3 
On Thu, 30 Apr 2015, Jakub Jelinek wrote:

> On Thu, Apr 30, 2015 at 01:35:25PM +0200, Richard Biener wrote:
> > I've long pondered with replacing the VRP overflow checking code
> > (for -fstrict-overflow) with keeping two lattices - one honoring undefined
> > overflow and one not and then comparing the results in the end.
> 
> Yeah, that would be greatly appreciated.  The (OVF) stuff is complete mess.

Just to explain a little bit, the idea is to have two lattices
and run the VRP propagation stage on each one, once with
flag_wrapv forced to 1 (all conditional on -Wstrict-overflow of course).
At stmt simplifiation time then determine if the outcome is dependent
on the choice of the lattice and if so, emit a strict-overflow warning.

This will avoid the missed optimizations we currently have due to the
(OVF) stuff.

And it will simplify the code and make it easier to maintain.

As for doing sth similar for PROMOTE_MODE you'd have to replace
all SSA names TREE_TYPE (and hope VRP doesn't explode on inconsistencies).
I don't think thats going to fly well though.  Instead you could
"lower" at VRP instrumentation time, inserting sign-/zero-extensions
and remove those not necessary at VRPs final stage.  Of course that
would tie lowering to VRP which probably we don't want to do.
I've meanwhile found the prototype lowering pass and as I've commented
on that patch you need to add at least a sign-extension tree operator
for efficiency (otherwise you need two stmts and an intermediate
non-promoted type).  zero-extension can be done via a BIT_AND_EXPR
(not 100% nice, but we avoid having two ways to compute sth which
speaks against having an explicit zero-extension operator).

Richard.
Kugan Vivekanandarajah May 1, 2015, 4:55 a.m. UTC | #4 
On 30/04/15 21:35, Richard Biener wrote:
> On Thu, Apr 23, 2015 at 12:11 AM, Kugan
> <kugan.vivekanandarajah@linaro.org> wrote:
>>
>> On 19/01/15 22:28, Richard Biener wrote:
>>> On Sat, 17 Jan 2015, Kugan wrote:
>>>
>>>>
>>>> This patch propagate value range wrapps attribute and save this to
>>>> SSA_NAME.
>>>
>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>> index 9b7695d..832c35d 100644
>>> --- a/gcc/tree-vrp.c
>>> +++ b/gcc/tree-vrp.c
>>> @@ -103,6 +103,9 @@ struct value_range_d
>>>    tree min;
>>>    tree max;
>>>
>>> +  /* Set to true if values in this value range could wrapp. */
>>> +  bool is_wrapped;
>>> +
>>>    /* Set of SSA names whose value ranges are equivalent to this one.
>>>       This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE.  */
>>>    bitmap equiv;
>>>
>>> I can't make sense of this description (wrap with one p as well).
>>> I assume you mean that the expression that has this value-range
>>> assigned has an operation that may have wrapped?  (a value
>>> can't wrap)
>>>
>>> You need to specify how is_wrapped behaves for range union and
>>> intersect operations and which operations can wrap.
>>>
>>> I miss an overall description of these patches as to a) why you
>>> need this information and b) why it helps.
>>>
>>> It's now also too late and thus you have plenty of time until stage1
>>> starts again.
>>
>>
>> Thanks Richard for the comments. Now that stage1 is open, here is the
>> modified patch with the changes requested.
>>
>> Due to wrapping in the value range computation, there was a regression
>> in aplha-linux
>> (https://gcc.gnu.org/ml/gcc-patches/2014-08/msg02458.html) while using
>> value range infromation to remove zero/sign extensions in rtl
>> expansaion. Hence I had to revert the patch that enabled zero/sign
>> extension. Now I am propgating this wrap_p information to SSA_NAME so
>> that we know, when used in PROMOTE_MODE, the values can have
>> unpredictable bits beyon the type width.
>>
>> I have also updated the comments as below:
>>
>>
>> +  /* Set to true if the values in this range might have been wrapped
>> +     during the operation that computed it.
>> +
>> +     This is mainly used in zero/sign-extension elimination where value
>> ranges
>> +     computed are for the type of SSA_NAME and computation is
>> ultimately done
>> +     in PROMOTE_MODE.  Therefore, the value ranges has to be correct upto
>> +     PROMOTE_MODE precision.  If the operation can WRAP, higher bits in
>> +     PROMOTE_MODE can be unpredictable and cannot be used in zero/sign
>> extension
>> +     elimination; additional wrap_p attribute is needed to show this.
>> +
>> +     For example:
>> +     on alpha where PROMOTE_MODE is 64 bit and _344 is a 32 bit unsigned
>> +     variable,
>> +     _343 = ivtmp.179_52 + 2147483645;      [0x80000004, 0x800000043]
>> +
>> +     the value range VRP will compute is:
>> +
>> +     _344 = _343 * 2;                  [0x8, 0x86]
>> +     _345 = (integer(kind=4)) _344;    [0x8, 0x86]
>> +
>> +     In PROMOTE_MODE, there will be garbage above the type width.  In
>> places
>> +     like this, attribute wrap_p will be true.
>> +
>> +     wrap_p in range union operation will be true if either of the
>> value range
>> +     has wrap_p set.  In intersect operation, true when both the value
>> ranges
>> +     have wrap_p set.  */
>> +  bool wrap_p;
>> +

Thanks for the review.

> So what you'd like to know is whether the value range is the same if
> all operations were carried out in infinite precision (well, in PROMOTE_MODE
> precision).
> 
> I'm not sure you can simply assert that we didn't wrap for example in
> extract_range_from_assert.  Consider your above code and
> 
>   if (_344 < 0x87)
>     {
>       _346 = ASSERT_EXPR <_344, _344 < 0x87>;
> ...
> 
> _346 definitely should have wrap_p set.

I agree. I tried to do this in my patch by propagating wrap_p in
extract_range_from_unary_expr_1 for unary assignment of SSA.


> That said, I'm not convinced this is a sustainable approach to the issue.
> 
> I've long pondered with replacing the VRP overflow checking code
> (for -fstrict-overflow) with keeping two lattices - one honoring undefined
> overflow and one not and then comparing the results in the end.
> 
> A similar approach could be used for your wrap_p flag.
> 
> BUT ... a way more sensible approach to reduce the required sign/zero
> extensions for PROMOTE_MODE targets is to lower the IL earlier,
> before we perform the 2nd VRP run and thus have the sign-/zero-extensions
> being eliminated by GIMPLE optimizers rather than only at RTL time.
> 
> ISTR you (or somebody else) played with that a bit?

Sorry, I should have mentioned that I am also working on this and will
post it as a separate patch. I wanted to try both the approaches and see
what is the best ultimately (and also if they can complement each
other). Since there are some issues to sort with the wrap_p and you
prefer type promotion, I have posted the updated patch for type
promotion at: https://gcc.gnu.org/ml/gcc-patches/2015-05/msg00005.html

Thanks,
Kugan
diff mbox

Patch

diff --git a/gcc/builtins.c b/gcc/builtins.c
index 9263777..02e97f1 100644
--- a/gcc/builtins.c
+++ b/gcc/builtins.c
@@ -3158,7 +3158,7 @@  determine_block_size (tree len, rtx len_rtx,
 	*probable_max_size = *max_size = GET_MODE_MASK (GET_MODE (len_rtx));
 
       if (TREE_CODE (len) == SSA_NAME)
-	range_type = get_range_info (len, &min, &max);
+	range_type = get_range_info (len, &min, &max, NULL);
       if (range_type == VR_RANGE)
 	{
 	  if (wi::fits_uhwi_p (min) && *min_size < min.to_uhwi ())
diff --git a/gcc/gimple-pretty-print.c b/gcc/gimple-pretty-print.c
index 2f9671f..0a5c4da 100644
--- a/gcc/gimple-pretty-print.c
+++ b/gcc/gimple-pretty-print.c
@@ -1847,13 +1847,15 @@  dump_ssaname_info (pretty_printer *buffer, tree node, int spc)
       && SSA_NAME_RANGE_INFO (node))
     {
       wide_int min, max, nonzero_bits;
-      value_range_type range_type = get_range_info (node, &min, &max);
+      bool wrapped;
+      value_range_type range_type = get_range_info (node, &min, &max, &wrapped);
 
       if (range_type == VR_VARYING)
 	pp_printf (buffer, "# RANGE VR_VARYING");
       else if (range_type == VR_RANGE || range_type == VR_ANTI_RANGE)
 	{
 	  pp_printf (buffer, "# RANGE ");
+	  pp_printf (buffer, "WRAPPED  = %s ", wrapped ? "true" : "false");
 	  pp_printf (buffer, "%s[", range_type == VR_RANGE ? "" : "~");
 	  pp_wide_int (buffer, min, TYPE_SIGN (TREE_TYPE (node)));
 	  pp_printf (buffer, ", ");
diff --git a/gcc/internal-fn.c b/gcc/internal-fn.c
index 0053ed9..9b10eaa 100644
--- a/gcc/internal-fn.c
+++ b/gcc/internal-fn.c
@@ -282,7 +282,7 @@  get_range_pos_neg (tree arg)
   if (TREE_CODE (arg) != SSA_NAME)
     return 3;
   wide_int arg_min, arg_max;
-  while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE)
+  while (get_range_info (arg, &arg_min, &arg_max, NULL) != VR_RANGE)
     {
       gimple g = SSA_NAME_DEF_STMT (arg);
       if (is_gimple_assign (g)
@@ -364,7 +364,7 @@  get_min_precision (tree arg, signop sign)
   if (TREE_CODE (arg) != SSA_NAME)
     return prec + (orig_sign != sign);
   wide_int arg_min, arg_max;
-  while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE)
+  while (get_range_info (arg, &arg_min, &arg_max, NULL) != VR_RANGE)
     {
       gimple g = SSA_NAME_DEF_STMT (arg);
       if (is_gimple_assign (g)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c
index a84ba8e..0c05ead 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c
@@ -18,6 +18,6 @@  int foo (int i, int j)
   return j;
 }
 
-/* { dg-final { scan-tree-dump "res_.: \\\[1, 1\\\]" "vrp1" } } */
+/* { dg-final { scan-tree-dump "res_.: NOWRAP \\\[1, 1\\\]" "vrp1" } } */
 /* { dg-final { scan-tree-dump-not "Threaded" "vrp1" } } */
 /* { dg-final { cleanup-tree-dump "vrp1" } } */
diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c
index 5ae8e6c..963c5a7 100644
--- a/gcc/tree-ssa-copy.c
+++ b/gcc/tree-ssa-copy.c
@@ -574,8 +574,8 @@  fini_copy_prop (void)
 		   && !SSA_NAME_RANGE_INFO (copy_of[i].value)
 		   && var_bb == copy_of_bb)
 	    duplicate_ssa_name_range_info (copy_of[i].value,
-					   SSA_NAME_RANGE_TYPE (var),
-					   SSA_NAME_RANGE_INFO (var));
+					   SSA_NAME_RANGE_INFO (var),
+					   SSA_NAME_RANGE_WRAP_P (var));
 	}
     }
 
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index 11fc699..987add1 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -1245,7 +1245,6 @@  move_computations_dom_walker::before_dom_children (basic_block bb)
 	{
 	  tree lhs = gimple_assign_lhs (new_stmt);
 	  SSA_NAME_RANGE_INFO (lhs) = NULL;
-	  SSA_NAME_ANTI_RANGE_P (lhs) = 0;
 	}
       gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
       remove_phi_node (&bsi, false);
@@ -1315,7 +1314,6 @@  move_computations_dom_walker::before_dom_children (basic_block bb)
 	{
 	  tree lhs = gimple_get_lhs (stmt);
 	  SSA_NAME_RANGE_INFO (lhs) = NULL;
-	  SSA_NAME_ANTI_RANGE_P (lhs) = 0;
 	}
       /* In case this is a stmt that is not unconditionally executed
          when the target loop header is executed and the stmt may
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index fc63825..1a32a8f 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -176,7 +176,7 @@  determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
       gphi_iterator gsi;
 
       /* Either for VAR itself...  */
-      rtype = get_range_info (var, &minv, &maxv);
+      rtype = get_range_info (var, &minv, &maxv, NULL);
       /* Or for PHI results in loop->header where VAR is used as
 	 PHI argument from the loop preheader edge.  */
       for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
@@ -184,7 +184,7 @@  determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
 	  gphi *phi = gsi.phi ();
 	  wide_int minc, maxc;
 	  if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var
-	      && (get_range_info (gimple_phi_result (phi), &minc, &maxc)
+	      && (get_range_info (gimple_phi_result (phi), &minc, &maxc, NULL)
 		  == VR_RANGE))
 	    {
 	      if (rtype != VR_RANGE)
@@ -203,7 +203,7 @@  determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
 		     involved.  */
 		  if (wi::gt_p (minv, maxv, sgn))
 		    {
-		      rtype = get_range_info (var, &minv, &maxv);
+		      rtype = get_range_info (var, &minv, &maxv, NULL);
 		      break;
 		    }
 		}
@@ -2785,7 +2785,7 @@  record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
       if (TREE_CODE (orig_base) == SSA_NAME
 	  && TREE_CODE (high) == INTEGER_CST
 	  && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
-	  && get_range_info (orig_base, &min, &max) == VR_RANGE
+	  && get_range_info (orig_base, &min, &max, NULL) == VR_RANGE
 	  && wi::gts_p (high, max))
 	base = wide_int_to_tree (unsigned_type, max);
       else if (TREE_CODE (base) != INTEGER_CST)
@@ -2800,7 +2800,7 @@  record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
       if (TREE_CODE (orig_base) == SSA_NAME
 	  && TREE_CODE (low) == INTEGER_CST
 	  && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
-	  && get_range_info (orig_base, &min, &max) == VR_RANGE
+	  && get_range_info (orig_base, &min, &max, NULL) == VR_RANGE
 	  && wi::gts_p (min, low))
 	base = wide_int_to_tree (unsigned_type, min);
       else if (TREE_CODE (base) != INTEGER_CST)
diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c
index 7c846c2..b6f4e10 100644
--- a/gcc/tree-ssa-phiopt.c
+++ b/gcc/tree-ssa-phiopt.c
@@ -911,14 +911,14 @@  value_replacement (basic_block cond_bb, basic_block middle_bb,
 	     <bb 4>:
 	     # u_3 = PHI <u_6(3), 4294967295(2)>  */
 	  SSA_NAME_RANGE_INFO (lhs) = NULL;
-	  SSA_NAME_ANTI_RANGE_P (lhs) = 0;
 	  /* If available, we can use VR of phi result at least.  */
 	  tree phires = gimple_phi_result (phi);
 	  struct range_info_def *phires_range_info
 	    = SSA_NAME_RANGE_INFO (phires);
 	  if (phires_range_info)
-	    duplicate_ssa_name_range_info (lhs, SSA_NAME_RANGE_TYPE (phires),
-					   phires_range_info);
+	    duplicate_ssa_name_range_info (lhs,
+					   phires_range_info,
+					   SSA_NAME_RANGE_WRAP_P (phires));
 	}
       gimple_stmt_iterator gsi_from = gsi_for_stmt (assign);
       gsi_move_before (&gsi_from, &gsi);
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 67e5351..b5e2e87 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -3200,7 +3200,7 @@  insert_into_preds_of_block (basic_block block, unsigned int exprnum,
       && SSA_NAME_RANGE_INFO (expr->u.nary->op[0]))
     {
       wide_int min, max;
-      if (get_range_info (expr->u.nary->op[0], &min, &max) == VR_RANGE
+      if (get_range_info (expr->u.nary->op[0], &min, &max, NULL) == VR_RANGE
 	  && !wi::neg_p (min, SIGNED)
 	  && !wi::neg_p (max, SIGNED))
 	/* Just handle extension and sign-changes of all-positive ranges.  */
@@ -3208,7 +3208,8 @@  insert_into_preds_of_block (basic_block block, unsigned int exprnum,
 			wide_int_storage::from (min, TYPE_PRECISION (type),
 						TYPE_SIGN (type)),
 			wide_int_storage::from (max, TYPE_PRECISION (type),
-						TYPE_SIGN (type)));
+						TYPE_SIGN (type)),
+			false);
     }
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -4146,8 +4147,8 @@  eliminate_dom_walker::before_dom_children (basic_block b)
 		       && !SSA_NAME_RANGE_INFO (sprime)
 		       && b == sprime_b)
 		duplicate_ssa_name_range_info (sprime,
-					       SSA_NAME_RANGE_TYPE (lhs),
-					       SSA_NAME_RANGE_INFO (lhs));
+					       SSA_NAME_RANGE_INFO (lhs),
+					       SSA_NAME_RANGE_WRAP_P (lhs));
 	    }
 
 	  /* Inhibit the use of an inserted PHI on a loop header when
diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c
index 744dc43..4b0e232 100644
--- a/gcc/tree-ssanames.c
+++ b/gcc/tree-ssanames.c
@@ -201,7 +201,7 @@  make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
 
 void
 set_range_info (tree name,
-		const wide_int_ref &min, const wide_int_ref &max)
+		const wide_int_ref &min, const wide_int_ref &max, bool wrap_p)
 {
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
@@ -221,6 +221,7 @@  set_range_info (tree name,
   /* Set the values.  */
   ri->set_min (min);
   ri->set_max (max);
+  SSA_NAME_RANGE_WRAP_P (name) = wrap_p;
 
   /* If it is a range, try to improve nonzero_bits from the min/max.  */
   if (wi::cmp (min, max, TYPE_SIGN (TREE_TYPE (name))) < 0)
@@ -238,7 +239,7 @@  set_range_info (tree name,
    is used to determine if MIN and MAX are valid values.  */
 
 enum value_range_type
-get_range_info (const_tree name, wide_int *min, wide_int *max)
+get_range_info (const_tree name, wide_int *min, wide_int *max, bool *wrap_p)
 {
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   gcc_assert (min && max);
@@ -266,6 +267,8 @@  get_range_info (const_tree name, wide_int *min, wide_int *max)
       *min = ri->get_min ();
       *max = ri->get_max ();
     }
+  if (wrap_p)
+    *wrap_p = SSA_NAME_RANGE_WRAP_P (name);
   return range_type;
 }
 
@@ -278,7 +281,8 @@  set_nonzero_bits (tree name, const wide_int_ref &mask)
   if (SSA_NAME_RANGE_INFO (name) == NULL)
     set_range_info (name,
 		    TYPE_MIN_VALUE (TREE_TYPE (name)),
-		    TYPE_MAX_VALUE (TREE_TYPE (name)));
+		    TYPE_MAX_VALUE (TREE_TYPE (name)),
+		    false);
   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
   ri->set_nonzero_bits (mask);
 }
@@ -505,14 +509,13 @@  duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
    RANGE_TYPE for use by the SSA name NAME.  */
 void
 duplicate_ssa_name_range_info (tree name,
-			       enum value_range_type range_type ATTRIBUTE_UNUSED,
-			       struct range_info_def *range_info)
+			       struct range_info_def *range_info,
+			       bool wrap_p)
 {
   struct range_info_def *new_range_info;
 
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   gcc_assert (!SSA_NAME_RANGE_INFO (name));
-  gcc_assert (!SSA_NAME_ANTI_RANGE_P (name));
 
   if (!range_info)
     return;
@@ -523,6 +526,7 @@  duplicate_ssa_name_range_info (tree name,
   new_range_info = static_cast<range_info_def *> (ggc_internal_alloc (size));
   memcpy (new_range_info, range_info, size);
 
+  SSA_NAME_RANGE_WRAP_P (name) = wrap_p;
   SSA_NAME_RANGE_INFO (name) = new_range_info;
 }
 
@@ -547,8 +551,9 @@  duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt)
       struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
 
       if (old_range_info)
-	duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name),
-				       old_range_info);
+	duplicate_ssa_name_range_info (new_name,
+				       old_range_info,
+				       SSA_NAME_RANGE_WRAP_P (name));
     }
 
   return new_name;
diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h
index 0d4b212..7bb33db 100644
--- a/gcc/tree-ssanames.h
+++ b/gcc/tree-ssanames.h
@@ -69,10 +69,10 @@  enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
 
 /* Sets the value range to SSA.  */
 extern void set_range_info (tree, const wide_int_ref &,
-			    const wide_int_ref &);
+			    const wide_int_ref &, bool);
 /* Gets the value range from SSA.  */
 extern enum value_range_type get_range_info (const_tree, wide_int *,
-					     wide_int *);
+					     wide_int *, bool *);
 extern void set_nonzero_bits (tree, const wide_int_ref &);
 extern wide_int get_nonzero_bits (const_tree);
 extern void init_ssanames (struct function *, int);
@@ -92,8 +92,9 @@  extern struct ptr_info_def *get_ptr_info (tree);
 extern tree copy_ssa_name_fn (struct function *, tree, gimple);
 extern void duplicate_ssa_name_ptr_info (tree, struct ptr_info_def *);
 extern tree duplicate_ssa_name_fn (struct function *, tree, gimple);
-extern void duplicate_ssa_name_range_info (tree, enum value_range_type,
-					   struct range_info_def *);
+extern void duplicate_ssa_name_range_info (tree,
+					   struct range_info_def *,
+					   bool);
 extern void release_defs (gimple);
 extern void replace_ssa_name_symbol (tree, tree);
 
diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c
index 86d2447..fc22f53 100644
--- a/gcc/tree-vect-patterns.c
+++ b/gcc/tree-vect-patterns.c
@@ -2563,7 +2563,7 @@  vect_recog_divmod_pattern (vec<gimple> *stmts,
 
       wide_int oprnd0_min, oprnd0_max;
       int msb = 1;
-      if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max) == VR_RANGE)
+      if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max, NULL) == VR_RANGE)
 	{
 	  if (!wi::neg_p (oprnd0_min, TYPE_SIGN (itype)))
 	    msb = 0;
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index d823be9..a988aaf 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -114,6 +114,34 @@  struct value_range_d
   tree min;
   tree max;
 
+  /* Set to true if the values in this range might have been wrapped
+     during the operation that computed it.
+
+     This is mainly used in zero/sign-extension elimination where value ranges
+     computed are for the type of SSA_NAME and computation is ultimately done
+     in PROMOTE_MODE.  Therefore, the value ranges has to be correct upto
+     PROMOTE_MODE precision.  If the operation can WRAP, higher bits in
+     PROMOTE_MODE can be unpredictable and cannot be used in zero/sign extension
+     elimination; additional wrap_p attribute is needed to show this.
+
+     For example:
+     on alpha where PROMOTE_MODE is 64 bit and _344 is a 32 bit unsigned
+     variable,
+     _343 = ivtmp.179_52 + 2147483645;      [0x80000004, 0x800000043]
+
+     the value range VRP will compute is:
+
+     _344 = _343 * 2;			[0x8, 0x86]
+     _345 = (integer(kind=4)) _344;	[0x8, 0x86]
+
+     In PROMOTE_MODE, there will be garbage above the type width.  In places
+     like this, attribute wrap_p will be true.
+
+     wrap_p in range union operation will be true if either of the value range
+     has wrap_p set.  In intersect operation, true when both the value ranges
+     have wrap_p set.  */
+  bool wrap_p;
+
   /* Set of SSA names whose value ranges are equivalent to this one.
      This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE.  */
   bitmap equiv;
@@ -121,7 +149,7 @@  struct value_range_d
 
 typedef struct value_range_d value_range_t;
 
-#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }
+#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, false, NULL }
 
 /* Set of SSA names found live during the RPO traversal of the function
    for still active basic-blocks.  */
@@ -469,7 +497,7 @@  set_value_range_to_varying (value_range_t *vr)
 
 static void
 set_value_range (value_range_t *vr, enum value_range_type t, tree min,
-		 tree max, bitmap equiv)
+		 tree max, bool wrap_p, bitmap equiv)
 {
 #if defined ENABLE_CHECKING
   /* Check the validity of the range.  */
@@ -503,6 +531,7 @@  set_value_range (value_range_t *vr, enum value_range_type t, tree min,
   vr->type = t;
   vr->min = min;
   vr->max = max;
+  vr->wrap_p = wrap_p;
 
   /* Since updating the equivalence set involves deep copying the
      bitmaps, only do it if absolutely necessary.  */
@@ -531,7 +560,7 @@  set_value_range (value_range_t *vr, enum value_range_type t, tree min,
 
 static void
 set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
-				  tree min, tree max, bitmap equiv)
+				  tree min, tree max, bool wrap_p, bitmap equiv)
 {
   /* Use the canonical setters for VR_UNDEFINED and VR_VARYING.  */
   if (t == VR_UNDEFINED)
@@ -549,7 +578,7 @@  set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
   if (TREE_CODE (min) != INTEGER_CST
       || TREE_CODE (max) != INTEGER_CST)
     {
-      set_value_range (vr, t, min, max, equiv);
+      set_value_range (vr, t, min, max, wrap_p, equiv);
       return;
     }
 
@@ -637,7 +666,7 @@  set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
       return;
     }
 
-  set_value_range (vr, t, min, max, equiv);
+  set_value_range (vr, t, min, max, wrap_p, equiv);
 }
 
 /* Copy value range FROM into value range TO.  */
@@ -645,7 +674,8 @@  set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
 static inline void
 copy_value_range (value_range_t *to, value_range_t *from)
 {
-  set_value_range (to, from->type, from->min, from->max, from->equiv);
+  set_value_range (to, from->type, from->min, from->max,
+		   from->wrap_p, from->equiv);
 }
 
 /* Set value range VR to a single value.  This function is only called
@@ -659,7 +689,7 @@  set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv)
   gcc_assert (is_gimple_min_invariant (val));
   if (TREE_OVERFLOW_P (val))
     val = drop_tree_overflow (val);
-  set_value_range (vr, VR_RANGE, val, val, equiv);
+  set_value_range (vr, VR_RANGE, val, val, false, equiv);
 }
 
 /* Set value range VR to a non-negative range of type TYPE.
@@ -685,6 +715,7 @@  set_value_range_to_nonnegative (value_range_t *vr, tree type,
 		   (overflow_infinity
 		    ? positive_overflow_infinity (type)
 		    : TYPE_MAX_VALUE (type)),
+		   false,
 		   vr->equiv);
 }
 
@@ -694,7 +725,7 @@  static inline void
 set_value_range_to_nonnull (value_range_t *vr, tree type)
 {
   tree zero = build_int_cst (type, 0);
-  set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
+  set_value_range (vr, VR_ANTI_RANGE, zero, zero, false, vr->equiv);
 }
 
 
@@ -717,6 +748,7 @@  set_value_range_to_truthvalue (value_range_t *vr, tree type)
   else
     set_value_range (vr, VR_RANGE,
 		     build_int_cst (type, 0), build_int_cst (type, 1),
+		     false,
 		     vr->equiv);
 }
 
@@ -753,7 +785,7 @@  abs_extent_range (value_range_t *vr, tree min, tree max)
       set_value_range_to_varying (vr);
       return;
     }
-  set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
+  set_and_canonicalize_value_range (vr, VR_RANGE, min, max, false, NULL);
 }
 
 
@@ -766,7 +798,7 @@  static value_range_t *
 get_value_range (const_tree var)
 {
   static const struct value_range_d vr_const_varying
-    = { VR_VARYING, NULL_TREE, NULL_TREE, NULL };
+    = { VR_VARYING, NULL_TREE, NULL_TREE, false, NULL };
   value_range_t *vr;
   tree sym;
   unsigned ver = SSA_NAME_VERSION (var);
@@ -864,13 +896,15 @@  update_value_range (const_tree var, value_range_t *new_vr)
   if (INTEGRAL_TYPE_P (TREE_TYPE (var)))
     {
       wide_int min, max;
-      value_range_type rtype = get_range_info (var, &min, &max);
+      bool wrap_p = false;
+      value_range_type rtype = get_range_info (var, &min, &max, &wrap_p);
       if (rtype == VR_RANGE || rtype == VR_ANTI_RANGE)
 	{
 	  value_range_d nr;
 	  nr.type = rtype;
 	  nr.min = wide_int_to_tree (TREE_TYPE (var), min);
 	  nr.max = wide_int_to_tree (TREE_TYPE (var), max);
+	  nr.wrap_p = wrap_p;
 	  nr.equiv = NULL;
 	  vrp_intersect_ranges (new_vr, &nr);
 	}
@@ -895,6 +929,7 @@  update_value_range (const_tree var, value_range_t *new_vr)
 	set_value_range_to_varying (old_vr);
       else
 	set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
+			 new_vr->wrap_p,
 			 new_vr->equiv);
     }
 
@@ -1788,10 +1823,10 @@  extract_range_from_assert (value_range_t *vr_p, tree expr)
 	 this for us.  */
       if (cond_code == LE_EXPR)
         set_and_canonicalize_value_range (vr_p, VR_RANGE,
-					  min, max, vr_p->equiv);
+					  min, max, false, vr_p->equiv);
       else if (cond_code == GT_EXPR)
         set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
-					  min, max, vr_p->equiv);
+					  min, max, false, vr_p->equiv);
       else
 	gcc_unreachable ();
     }
@@ -1812,7 +1847,7 @@  extract_range_from_assert (value_range_t *vr_p, tree expr)
 	  max = limit;
 	}
 
-      set_value_range (vr_p, range_type, min, max, vr_p->equiv);
+      set_value_range (vr_p, range_type, min, max, false, vr_p->equiv);
 
       /* When asserting the equality VAR == LIMIT and LIMIT is another
 	 SSA name, the new range will also inherit the equivalence set
@@ -1864,7 +1899,7 @@  extract_range_from_assert (value_range_t *vr_p, tree expr)
 	min = max = limit;
 
       set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
-					min, max, vr_p->equiv);
+					min, max, false, vr_p->equiv);
     }
   else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
     {
@@ -1903,7 +1938,7 @@  extract_range_from_assert (value_range_t *vr_p, tree expr)
 		TREE_NO_WARNING (max) = 1;
 	    }
 
-	  set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
+	  set_value_range (vr_p, VR_RANGE, min, max, false, vr_p->equiv);
 	}
     }
   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
@@ -1943,7 +1978,7 @@  extract_range_from_assert (value_range_t *vr_p, tree expr)
 		TREE_NO_WARNING (min) = 1;
 	    }
 
-	  set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
+	  set_value_range (vr_p, VR_RANGE, min, max, false, vr_p->equiv);
 	}
     }
   else
@@ -1975,12 +2010,11 @@  extract_range_from_ssa_name (value_range_t *vr, tree var)
   if (var_vr->type != VR_VARYING)
     copy_value_range (vr, var_vr);
   else
-    set_value_range (vr, VR_RANGE, var, var, NULL);
+    set_value_range (vr, VR_RANGE, var, var, false, NULL);
 
   add_equivalence (&vr->equiv, var);
 }
 
-
 /* Wrapper around int_const_binop.  If the operation overflows and we
    are not using wrapping arithmetic, then adjust the result to be
    -INF or +INF depending on CODE, VAL1 and VAL2.  This can return
@@ -1988,11 +2022,13 @@  extract_range_from_ssa_name (value_range_t *vr, tree var)
    the type does not support it.  */
 
 static tree
-vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
+vrp_int_const_binop (enum tree_code code, tree val1, tree val2, bool *wrap_p)
 {
   tree res;
 
   res = int_const_binop (code, val1, val2);
+  if (wrap_p)
+    *wrap_p = false;
 
   /* If we are using unsigned arithmetic, operate symbolically
      on -INF and +INF as int_const_binop only handles signed overflow.  */
@@ -2036,7 +2072,10 @@  vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
   else if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
     /* If the singed operation wraps then int_const_binop has done
        everything we want.  */
-    ;
+    {
+      if (wrap_p)
+	*wrap_p = true;
+    }
   /* Signed division of -1/0 overflows and by the time it gets here
      returns NULL_TREE.  */
   else if (!res)
@@ -2200,12 +2239,14 @@  ranges_from_anti_range (value_range_t *ar,
       vr0->type = VR_RANGE;
       vr0->min = vrp_val_min (type);
       vr0->max = wide_int_to_tree (type, wi::sub (ar->min, 1));
+      vr0->wrap_p = ar->wrap_p;
     }
   if (!vrp_val_is_max (ar->max))
     {
       vr1->type = VR_RANGE;
       vr1->min = wide_int_to_tree (type, wi::add (ar->max, 1));
       vr1->max = vrp_val_max (type);
+      vr1->wrap_p = ar->wrap_p;
     }
   if (vr0->type == VR_UNDEFINED)
     {
@@ -2230,6 +2271,8 @@  extract_range_from_multiplicative_op_1 (value_range_t *vr,
   tree min, max;
   bool sop;
   int cmp;
+  bool wrap_p = false;
+  bool t_wrap_p = false;
 
   /* Multiplications, divisions and shifts are a bit tricky to handle,
      depending on the mix of signs we have in the two ranges, we
@@ -2259,35 +2302,43 @@  extract_range_from_multiplicative_op_1 (value_range_t *vr,
 
   /* Compute the 4 cross operations.  */
   sop = false;
-  val[0] = vrp_int_const_binop (code, vr0->min, vr1->min);
+  val[0] = vrp_int_const_binop (code, vr0->min, vr1->min, &t_wrap_p);
   if (val[0] == NULL_TREE)
     sop = true;
+  if (t_wrap_p)
+    wrap_p = true;
 
   if (vr1->max == vr1->min)
     val[1] = NULL_TREE;
   else
     {
-      val[1] = vrp_int_const_binop (code, vr0->min, vr1->max);
+      val[1] = vrp_int_const_binop (code, vr0->min, vr1->max, &t_wrap_p);
       if (val[1] == NULL_TREE)
 	sop = true;
+      if (t_wrap_p)
+	wrap_p = true;
     }
 
   if (vr0->max == vr0->min)
     val[2] = NULL_TREE;
   else
     {
-      val[2] = vrp_int_const_binop (code, vr0->max, vr1->min);
+      val[2] = vrp_int_const_binop (code, vr0->max, vr1->min, &t_wrap_p);
       if (val[2] == NULL_TREE)
 	sop = true;
+      if (t_wrap_p)
+	wrap_p = true;
     }
 
   if (vr0->min == vr0->max || vr1->min == vr1->max)
     val[3] = NULL_TREE;
   else
     {
-      val[3] = vrp_int_const_binop (code, vr0->max, vr1->max);
+      val[3] = vrp_int_const_binop (code, vr0->max, vr1->max, &t_wrap_p);
       if (val[3] == NULL_TREE)
 	sop = true;
+      if (t_wrap_p)
+	wrap_p = true;
     }
 
   if (sop)
@@ -2367,7 +2418,7 @@  extract_range_from_multiplicative_op_1 (value_range_t *vr,
       set_value_range_to_varying (vr);
     }
   else
-    set_value_range (vr, type, min, max, NULL);
+    set_value_range (vr, type, min, max, wrap_p, NULL);
 }
 
 /* Extract range information from a binary operation CODE based on
@@ -2384,6 +2435,7 @@  extract_range_from_binary_expr_1 (value_range_t *vr,
   enum value_range_type type;
   tree min = NULL_TREE, max = NULL_TREE;
   int cmp;
+  bool vr_wrap_p = false;
 
   if (!INTEGRAL_TYPE_P (expr_type)
       && !POINTER_TYPE_P (expr_type))
@@ -2683,6 +2735,13 @@  extract_range_from_binary_expr_1 (value_range_t *vr,
 		 range kind and bounds appropriately.  */
 	      wide_int tmin = wide_int::from (wmin, prec, sgn);
 	      wide_int tmax = wide_int::from (wmax, prec, sgn);
+
+	      if (wi::cmp (wmin, type_min, sgn) == -1
+		  || wi::cmp (wmin, type_max, sgn) == 1
+		  || wi::cmp (wmax, type_min, sgn) == -1
+		  || wi::cmp (wmax, type_max, sgn) == 1)
+		vr_wrap_p = true;
+
 	      if (min_ovf == max_ovf)
 		{
 		  /* No overflow or both overflow or underflow.  The
@@ -2835,8 +2894,8 @@  extract_range_from_binary_expr_1 (value_range_t *vr,
 	      /* For operations that make the resulting range directly
 		 proportional to the original ranges, apply the operation to
 		 the same end of each range.  */
-	      min = vrp_int_const_binop (code, vr0.min, vr1.min);
-	      max = vrp_int_const_binop (code, vr0.max, vr1.max);
+	      min = vrp_int_const_binop (code, vr0.min, vr1.min, NULL);
+	      max = vrp_int_const_binop (code, vr0.max, vr1.max, NULL);
 	    }
 	  else if (code == MIN_EXPR)
 	    {
@@ -2960,9 +3019,10 @@  extract_range_from_binary_expr_1 (value_range_t *vr,
 
 	  /* The following should handle the wrapping and selecting
 	     VR_ANTI_RANGE for us.  */
+	  vr_wrap_p = true;
 	  min = wide_int_to_tree (expr_type, prod0);
 	  max = wide_int_to_tree (expr_type, prod3);
-	  set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
+	  set_and_canonicalize_value_range (vr, VR_RANGE, min, max, vr_wrap_p, NULL);
 	  return;
 	}
 
@@ -3330,7 +3390,7 @@  extract_range_from_binary_expr_1 (value_range_t *vr,
       set_value_range_to_varying (vr);
     }
   else
-    set_value_range (vr, type, min, max, NULL);
+    set_value_range (vr, type, min, max, vr_wrap_p, NULL);
 }
 
 /* Extract range information from a binary expression OP0 CODE OP1 based on
@@ -3379,15 +3439,15 @@  extract_range_from_binary_expr (value_range_t *vr,
 
       /* Try with VR0 and [-INF, OP1].  */
       if (is_gimple_min_invariant (minus_p ? vr0.max : vr0.min))
-	set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL);
+	set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, false, NULL);
 
       /* Try with VR0 and [OP1, +INF].  */
       else if (is_gimple_min_invariant (minus_p ? vr0.min : vr0.max))
-	set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL);
+	set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), false, NULL);
 
       /* Try with VR0 and [OP1, OP1].  */
       else
-	set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL);
+	set_value_range (&n_vr1, VR_RANGE, op1, op1, false, NULL);
 
       extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1);
     }
@@ -3403,15 +3463,15 @@  extract_range_from_binary_expr (value_range_t *vr,
 
       /* Try with [-INF, OP0] and VR1.  */
       if (is_gimple_min_invariant (minus_p ? vr1.max : vr1.min))
-	set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL);
+	set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, false, NULL);
 
       /* Try with [OP0, +INF] and VR1.  */
       else if (is_gimple_min_invariant (minus_p ? vr1.min : vr1.max))
-	set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL);
+	set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), false, NULL);
 
       /* Try with [OP0, OP0] and VR1.  */
       else
-	set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL);
+	set_value_range (&n_vr0, VR_RANGE, op0, op0, false, NULL);
 
       extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
     }
@@ -3544,18 +3604,27 @@  extract_range_from_unary_expr_1 (value_range_t *vr,
 		         size_int (TYPE_PRECISION (outer_type)))))))
 	{
 	  tree new_min, new_max;
+	  bool wrap_p =  vr0.wrap_p;
 	  if (is_overflow_infinity (vr0.min))
 	    new_min = negative_overflow_infinity (outer_type);
 	  else
-	    new_min = force_fit_type (outer_type, wi::to_widest (vr0.min),
-				      0, false);
+	    {
+	      if (!int_fits_type_p (vr0.max, outer_type))
+		wrap_p = true;
+	      new_min = force_fit_type (outer_type, wi::to_widest (vr0.min),
+					0, false);
+	    }
 	  if (is_overflow_infinity (vr0.max))
 	    new_max = positive_overflow_infinity (outer_type);
 	  else
-	    new_max = force_fit_type (outer_type, wi::to_widest (vr0.max),
-				      0, false);
+	    {
+	      if (!int_fits_type_p (vr0.max, outer_type))
+		wrap_p = true;
+	      new_max = force_fit_type (outer_type, wi::to_widest (vr0.max),
+					0, false);
+	    }
 	  set_and_canonicalize_value_range (vr, vr0.type,
-					    new_min, new_max, NULL);
+					    new_min, new_max, wrap_p, NULL);
 	  return;
 	}
 
@@ -3712,7 +3781,7 @@  extract_range_from_unary_expr_1 (value_range_t *vr,
 	  set_value_range_to_varying (vr);
 	}
       else
-	set_value_range (vr, vr0.type, min, max, NULL);
+	set_value_range (vr, vr0.type, min, max, false, NULL);
       return;
     }
 
@@ -3806,7 +3875,7 @@  extract_range_from_comparison (value_range_t *vr, enum tree_code code,
       if (is_gimple_min_invariant (val))
 	set_value_range_to_value (vr, val, vr->equiv);
       else
-	set_value_range (vr, VR_RANGE, val, val, vr->equiv);
+	set_value_range (vr, VR_RANGE, val, val, false, vr->equiv);
     }
   else
     /* The result of a comparison is always true or false.  */
@@ -4103,7 +4172,7 @@  extract_range_basic (value_range_t *vr, gimple stmt)
 	  goto bitop_builtin;
 	bitop_builtin:
 	  set_value_range (vr, VR_RANGE, build_int_cst (type, mini),
-			   build_int_cst (type, maxi), NULL);
+			   build_int_cst (type, maxi), false, NULL);
 	  return;
 	default:
 	  break;
@@ -4193,7 +4262,7 @@  extract_range_basic (value_range_t *vr, gimple stmt)
 						  NULL);
 		      else
 			set_value_range (vr, VR_RANGE, build_int_cst (type, 0),
-					 build_int_cst (type, 1), NULL);
+					 build_int_cst (type, 1), false, NULL);
 		    }
 		  else if (types_compatible_p (type, TREE_TYPE (op0))
 			   && types_compatible_p (type, TREE_TYPE (op1)))
@@ -4287,6 +4356,7 @@  adjust_range_with_scev (value_range_t *vr, struct loop *loop,
 {
   tree init, step, chrec, tmin, tmax, min, max, type, tem;
   enum ev_direction dir;
+  bool t_wrap_p = false, wrap_p = false;
 
   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
      better opportunities than a regular range, but I'm not sure.  */
@@ -4382,6 +4452,7 @@  adjust_range_with_scev (value_range_t *vr, struct loop *loop,
 	      /* Likewise if the addition did.  */
 	      if (maxvr.type == VR_RANGE)
 		{
+		  t_wrap_p = maxvr.wrap_p;
 		  tmin = maxvr.min;
 		  tmax = maxvr.max;
 		}
@@ -4393,6 +4464,7 @@  adjust_range_with_scev (value_range_t *vr, struct loop *loop,
     {
       min = tmin;
       max = tmax;
+      wrap_p = t_wrap_p;
 
       /* For VARYING or UNDEFINED ranges, just about anything we get
 	 from scalar evolutions should be better.  */
@@ -4446,7 +4518,7 @@  adjust_range_with_scev (value_range_t *vr, struct loop *loop,
 	  && is_positive_overflow_infinity (max)))
     return;
 
-  set_value_range (vr, VR_RANGE, min, max, vr->equiv);
+  set_value_range (vr, VR_RANGE, min, max, wrap_p, vr->equiv);
 }
 
 
@@ -4765,7 +4837,8 @@  dump_value_range (FILE *file, value_range_t *vr)
     {
       tree type = TREE_TYPE (vr->min);
 
-      fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
+      fprintf (file, "%s %s[", vr->wrap_p ? "WRAP" : "NOWRAP",
+	       (vr->type == VR_ANTI_RANGE) ? "~" : "");
 
       if (is_negative_overflow_infinity (vr->min))
 	fprintf (file, "-INF(OVF)");
@@ -6936,7 +7009,8 @@  remove_range_assertions (void)
 		  {
 		    set_range_info (var,
 				    SSA_NAME_RANGE_INFO (lhs)->get_min (),
-				    SSA_NAME_RANGE_INFO (lhs)->get_max ());
+				    SSA_NAME_RANGE_INFO (lhs)->get_max (),
+				    SSA_NAME_RANGE_WRAP_P (lhs));
 		    maybe_set_nonzero_bits (bb, var);
 		  }
 	      }
@@ -8604,7 +8678,9 @@  vrp_intersect_ranges_1 (value_range_t *vr0, value_range_t *vr1)
   /* Make sure to canonicalize the result though as the inversion of a
      VR_RANGE can still be a VR_RANGE.  */
   set_and_canonicalize_value_range (vr0, vr0->type,
-				    vr0->min, vr0->max, vr0->equiv);
+				    vr0->min, vr0->max,
+				    vr0->wrap_p && vr1->wrap_p,
+				    vr0->equiv);
   /* If that failed, use the saved original VR0.  */
   if (vr0->type == VR_VARYING)
     {
@@ -8655,7 +8731,8 @@  vrp_meet_1 (value_range_t *vr0, value_range_t *vr1)
 
   if (vr0->type == VR_UNDEFINED)
     {
-      set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr1->equiv);
+      set_value_range (vr0, vr1->type, vr1->min, vr1->max,
+		       vr1->wrap_p, vr1->equiv);
       return;
     }
 
@@ -8709,6 +8786,7 @@  vrp_meet_1 (value_range_t *vr0, value_range_t *vr1)
       return;
     }
   set_and_canonicalize_value_range (vr0, vr0->type, vr0->min, vr0->max,
+				    vr0->wrap_p || vr1->wrap_p,
 				    vr0->equiv);
   if (vr0->type == VR_VARYING)
     return;
@@ -8812,6 +8890,7 @@  vrp_visit_phi_node (gphi *phi)
 		      vr_arg.type = VR_RANGE;
 		      vr_arg.min = arg;
 		      vr_arg.max = arg;
+		      vr_arg.wrap_p = false;
 		      vr_arg.equiv = NULL;
 		    }
 		}
@@ -8824,6 +8903,7 @@  vrp_visit_phi_node (gphi *phi)
 	      vr_arg.type = VR_RANGE;
 	      vr_arg.min = arg;
 	      vr_arg.max = arg;
+	      vr_arg.wrap_p = false;
 	      vr_arg.equiv = NULL;
 	    }
 
@@ -10264,7 +10344,9 @@  vrp_finalize (void)
 	      || vr_value[i]->type == VR_ANTI_RANGE))
 	{
 	  if (vr_value[i]->type == VR_RANGE)
-	   set_range_info (name, vr_value[i]->min, vr_value[i]->max);
+	   set_range_info (name, vr_value[i]->min,
+			   vr_value[i]->max,
+			   vr_value[i]->wrap_p);
 	  else if (vr_value[i]->type == VR_ANTI_RANGE)
 	    {
 	      /* VR_ANTI_RANGE
@@ -10279,11 +10361,13 @@  vrp_finalize (void)
 		/* ~[0,0] anti-range is represented as range.  */
 		set_range_info (name,
 				build_int_cst (TREE_TYPE (name), 1),
-				TYPE_MAXVAL (TREE_TYPE (name)));
+				TYPE_MAXVAL (TREE_TYPE (name)),
+				vr_value[i]->wrap_p);
 	      else
 		set_range_info (name,
 				wi::add (vr_value[i]->max, 1),
-				wi::sub (vr_value[i]->min, 1));
+				wi::sub (vr_value[i]->min, 1),
+				vr_value[i]->wrap_p);
 	    }
 	}
 
diff --git a/gcc/tree.h b/gcc/tree.h
index bedf103..cc147bb 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -1542,14 +1542,11 @@  extern void protected_set_expr_location (tree, location_t);
 #define SSA_NAME_PTR_INFO(N) \
    SSA_NAME_CHECK (N)->ssa_name.info.ptr_info
 
-/* True if SSA_NAME_RANGE_INFO describes an anti-range.  */
-#define SSA_NAME_ANTI_RANGE_P(N) \
+/* True if SSA_NAME_RANGE_INFO may have wrapped during the operation that
+   calculated it.  */
+#define SSA_NAME_RANGE_WRAP_P(N) \
     SSA_NAME_CHECK (N)->base.static_flag
 
-/* The type of range described by SSA_NAME_RANGE_INFO.  */
-#define SSA_NAME_RANGE_TYPE(N) \
-    (SSA_NAME_ANTI_RANGE_P (N) ? VR_ANTI_RANGE : VR_RANGE)
-
 /* Value range info attributes for SSA_NAMEs of non pointer-type variables.  */
 #define SSA_NAME_RANGE_INFO(N) \
     SSA_NAME_CHECK (N)->ssa_name.info.range_info