[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[jiwang at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

Jiong Wang  changed:

   What|Removed |Added

 Status|NEW |RESOLVED
 Resolution|--- |FIXED

--- Comment #12 from Jiong Wang  ---
Mark as fixed.

[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[jiwang at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

--- Comment #11 from Jiong Wang  ---
Author: jiwang
Date: Mon Nov 23 12:14:05 2015
New Revision: 230754

URL: https://gcc.gnu.org/viewcvs?rev=230754=gcc=rev
Log:
[Patch] Drop constant overflow flag in adjust_range_with_scev when possible

2015-11-23  Richard Biener  
Jiong Wang  

gcc/
  PR tree-optimization/68317
  PR tree-optimization/68326
  * tree-vrp.c (adjust_range_with_scev): Call drop_tree_overflow if the
  final min and max are not infinity.

gcc/testsuite/
  * gcc.dg/pr68317.c: New testcase.


Added:
trunk/gcc/testsuite/gcc.dg/pr68317.c
Modified:
trunk/gcc/ChangeLog
trunk/gcc/testsuite/ChangeLog
trunk/gcc/tree-vrp.c

[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

--- Comment #10 from Richard Biener  ---
(In reply to Jiong Wang from comment #9)
> (In reply to Richard Biener from comment #7)
> > (In reply to Jiong Wang from comment #6)
> > > Created attachment 36741 [details]
> > > prototype-fix
> > > 
> > > diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
> > > index b614412..55a6334 100644
> > > --- a/gcc/tree-ssa-loop-manip.c
> > > +++ b/gcc/tree-ssa-loop-manip.c
> > > @@ -136,6 +136,11 @@ create_iv (tree base, tree step, tree var, struct 
> > > loop
> > > *loop,
> > >  gsi_insert_seq_on_edge_immediate (pe, stmts);
> > >  
> > >phi = create_phi_node (vb, loop->header);
> > > +  if (TREE_OVERFLOW (initial)
> > > +  && TREE_CODE (initial) == INTEGER_CST
> > > +  && int_fits_type_p (initial, TREE_TYPE (vb)))
> > > +initial = drop_tree_overflow (initial);
> > > +
> > >add_phi_arg (phi, initial, loop_preheader_edge (loop), 
> > > UNKNOWN_LOCATION);
> > >add_phi_arg (phi, va, loop_latch_edge (loop), UNKNOWN_LOCATION);
> > >  }
> > 
> > I think it's better to track down where the constant is generated.  I
> > see initial is created by
> > 
> >   initial = force_gimple_operand (base, , true, var);
> > 
> > thus likely base is already the same constant (passed from the caller).
> > 
> > I usually set a breakpoint on the return statement of ggc_internal_alloc
> > conditional on the return value being the tree with the overflow.
> > 
> > Once the overflow value is returned from fold_* () it should be stripped
> > off its overflow flag.  Unconditionally so with just
> > 
> >   if (TREE_OVERFLOW_P (..))
> >.. = drop_tree_overflow (..);
> 
> Richard,
> 
>  After further investigation on where the overflow flag comes
>  from. I found there are too many possibility.
> 
>  For example, for the testcase reported in PR68326, it's originated at
>  fully_constant_expression, at tree-ssa-pre.c when handling tcc_unary,
>  the fold_unary will set overflag flag.
> 
>  While for the testcase in this PR, there are quite a few OVF variables,
>  For the one caused the ICE, the OVF is inherited from another OVF
>  variable and the most early I can track down is at tree-ssa-ccp.c, tree
>  variable "simplified" is simplifed by gimple-fold infrastructure, and
>  conclude to be overflowed which is correct (C source code is
>  print(..."0x%08x...", (0xff4 + i) * 0x10..., the multiply are
>  assumed to be generating signed int, thus overflowed.), While my
> understanding
>  is it's only used to generate warning. So I tested to call
> drop_tree_overflow,
>  but then later passes will re-calculate the variable, and re-set the
> overflow
>  flag, for example in chrec_fold*.
> 
>  I don't undertand related code base, and fell it will be dangerous to 
>  just call drop_tree_overflow in those places.

Well, the GIMPLE IL should have _no_ constants with TREE_OVERFLOW set.
I even had checking code for that (but it tripped, obviously as you noticed ;))

>  After a second thinking, this ICE is caused by adjust_range_with_scev
>  getting range with overflowed constants min or max. So given there are
>  too many places to generate OVF, can we just do a check in
>  adjust_range_with_scev, if the constant min or max in the range info
>  can fit into the variable type, then naturally we should treat those
>  OVF as false alarm and drop them? something like the following, which I
>  think can fix the OVF side-effect caused by r230150.
> 
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index e2393e4..56440b1 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -4331,6 +4331,16 @@ adjust_range_with_scev (value_range *vr, struct loop
> *loop,
>   && is_positive_overflow_infinity (max)))
>  return;
> 
> +  if (TREE_CODE (min) == INTEGER_CST
> +  && TREE_OVERFLOW (min)
> +  && int_fits_type_p (min, type))
> +min = drop_tree_overflow (min);
> +
> +  if (TREE_CODE (max) == INTEGER_CST
> +  && TREE_OVERFLOW (max)
> +  && int_fits_type_p (max, type))
> +max = drop_tree_overflow (max);
> +
>set_value_range (vr, VR_RANGE, min, max, vr->equiv);
>  }

The constant will be always in-range so it doesn't make much sense in this
form.
Note also that positive/negative_overflow_infinities are to be preserved,
only other overflows need to be dropped here.

Yes, a workaround here might be ok in the end but in reality all those
other places you identified should be fixed.  So the above code should be

  if (TREE_OVERFLOW_P (min)
  && ! is_negative_overflow_infinity (min))
min = drop_tree_overflow (min);
  if (TREE_OVERFLOW_P (max)
  && ! is_positive_overflow_infinity (max))
max = drop_tree_overflow (max);

[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[jiwang at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

--- Comment #9 from Jiong Wang  ---
(In reply to Richard Biener from comment #7)
> (In reply to Jiong Wang from comment #6)
> > Created attachment 36741 [details]
> > prototype-fix
> > 
> > diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
> > index b614412..55a6334 100644
> > --- a/gcc/tree-ssa-loop-manip.c
> > +++ b/gcc/tree-ssa-loop-manip.c
> > @@ -136,6 +136,11 @@ create_iv (tree base, tree step, tree var, struct loop
> > *loop,
> >  gsi_insert_seq_on_edge_immediate (pe, stmts);
> >  
> >phi = create_phi_node (vb, loop->header);
> > +  if (TREE_OVERFLOW (initial)
> > +  && TREE_CODE (initial) == INTEGER_CST
> > +  && int_fits_type_p (initial, TREE_TYPE (vb)))
> > +initial = drop_tree_overflow (initial);
> > +
> >add_phi_arg (phi, initial, loop_preheader_edge (loop), UNKNOWN_LOCATION);
> >add_phi_arg (phi, va, loop_latch_edge (loop), UNKNOWN_LOCATION);
> >  }
> 
> I think it's better to track down where the constant is generated.  I
> see initial is created by
> 
>   initial = force_gimple_operand (base, , true, var);
> 
> thus likely base is already the same constant (passed from the caller).
> 
> I usually set a breakpoint on the return statement of ggc_internal_alloc
> conditional on the return value being the tree with the overflow.
> 
> Once the overflow value is returned from fold_* () it should be stripped
> off its overflow flag.  Unconditionally so with just
> 
>   if (TREE_OVERFLOW_P (..))
>.. = drop_tree_overflow (..);

Richard,

 After further investigation on where the overflow flag comes
 from. I found there are too many possibility.

 For example, for the testcase reported in PR68326, it's originated at
 fully_constant_expression, at tree-ssa-pre.c when handling tcc_unary,
 the fold_unary will set overflag flag.

 While for the testcase in this PR, there are quite a few OVF variables,
 For the one caused the ICE, the OVF is inherited from another OVF
 variable and the most early I can track down is at tree-ssa-ccp.c, tree
 variable "simplified" is simplifed by gimple-fold infrastructure, and
 conclude to be overflowed which is correct (C source code is
 print(..."0x%08x...", (0xff4 + i) * 0x10..., the multiply are
 assumed to be generating signed int, thus overflowed.), While my understanding
 is it's only used to generate warning. So I tested to call drop_tree_overflow,
 but then later passes will re-calculate the variable, and re-set the overflow
 flag, for example in chrec_fold*.

 I don't undertand related code base, and fell it will be dangerous to 
 just call drop_tree_overflow in those places.

 After a second thinking, this ICE is caused by adjust_range_with_scev
 getting range with overflowed constants min or max. So given there are
 too many places to generate OVF, can we just do a check in
 adjust_range_with_scev, if the constant min or max in the range info
 can fit into the variable type, then naturally we should treat those
 OVF as false alarm and drop them? something like the following, which I
 think can fix the OVF side-effect caused by r230150.

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index e2393e4..56440b1 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -4331,6 +4331,16 @@ adjust_range_with_scev (value_range *vr, struct loop
*loop,
  && is_positive_overflow_infinity (max)))
 return;

+  if (TREE_CODE (min) == INTEGER_CST
+  && TREE_OVERFLOW (min)
+  && int_fits_type_p (min, type))
+min = drop_tree_overflow (min);
+
+  if (TREE_CODE (max) == INTEGER_CST
+  && TREE_OVERFLOW (max)
+  && int_fits_type_p (max, type))
+max = drop_tree_overflow (max);
+
   set_value_range (vr, VR_RANGE, min, max, vr->equiv);
 }

[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[jiwang at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

--- Comment #8 from Jiong Wang  ---
(In reply to Richard Biener from comment #7)
> (In reply to Jiong Wang from comment #6)
> > Created attachment 36741 [details]
> > prototype-fix
> > 
> > (In reply to Richard Biener from comment #3)
> > > (gdb) p debug_generic_expr (max)
> > > 4294443008(OVF)
> > > +  # ivtmp.8_8 = PHI <4294443008(OVF)(2), ivtmp.8_11(4)>
> > > +  _5 = (int) ivtmp.8_8;
> > >fn2 (_5);
> > > -  i_7 = i_1 + -1;
> > >  
> > >:
> > > +  ivtmp.8_11 = ivtmp.8_8 - 524288;
> > >goto ;
> > >  
> > >  }
> > > 
> > > note that the infinite loop contains undefined overflow.
> > > 
> > > IVOPTs should simply strip the overflow flag (using drop_tree_overflow).
> > 
> > And my further investigation shows PR68326 is caused by the same issue.
> > 
> >  # ivtmp.8_8 = PHI <4294443008(OVF)(2), ivtmp.8_11(4)>
> > 
> > the new phi node destination is with unsigned int type, the constant
> > value 4294443008 can fit into it, it's marked as OVF because
> > it's treated as signed type. For the simple testcase in PR68326,
> > the overflow number is 4294967286 which is -10, while there happen be
> > another signed integer with initial value -10. So, looks like the unsigned
> > 4294967286 somehow inherited the signed type from the other value in some
> > tree pass, then some valid constant is marked with OVF unnecessarily.
> > 
> > Anyway, below is my fix, does it looks the correct approach to you?
> > 
> > drop_tree_overflow is invoked during create_iv, if the constant can actually
> > fit into the type. I only checked INTEGER_CST, not for others like REAL, as 
> > I
> > though they won't suffer from the unsigned/signed type issue.
> > 
> > x86-64 bootstrap is OK with this patch, will do more testing if the approach
> > is OK.
> > 
> > diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
> > index b614412..55a6334 100644
> > --- a/gcc/tree-ssa-loop-manip.c
> > +++ b/gcc/tree-ssa-loop-manip.c
> > @@ -136,6 +136,11 @@ create_iv (tree base, tree step, tree var, struct loop
> > *loop,
> >  gsi_insert_seq_on_edge_immediate (pe, stmts);
> >  
> >phi = create_phi_node (vb, loop->header);
> > +  if (TREE_OVERFLOW (initial)
> > +  && TREE_CODE (initial) == INTEGER_CST
> > +  && int_fits_type_p (initial, TREE_TYPE (vb)))
> > +initial = drop_tree_overflow (initial);
> > +
> >add_phi_arg (phi, initial, loop_preheader_edge (loop), UNKNOWN_LOCATION);
> >add_phi_arg (phi, va, loop_latch_edge (loop), UNKNOWN_LOCATION);
> >  }
> 
> I think it's better to track down where the constant is generated. 

OK, I will do a further tracking.


> Once the overflow value is returned from fold_* () it should be stripped
> off its overflow flag.  Unconditionally so with just
> 
>   if (TREE_OVERFLOW_P (..))
>.. = drop_tree_overflow (..);

I don't understand the scope of OVERFLOW flag will affect, so was dropping the
flag only when it's really a overflow.

[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

--- Comment #7 from Richard Biener  ---
(In reply to Jiong Wang from comment #6)
> Created attachment 36741 [details]
> prototype-fix
> 
> (In reply to Richard Biener from comment #3)
> > (gdb) p debug_generic_expr (max)
> > 4294443008(OVF)
> > +  # ivtmp.8_8 = PHI <4294443008(OVF)(2), ivtmp.8_11(4)>
> > +  _5 = (int) ivtmp.8_8;
> >fn2 (_5);
> > -  i_7 = i_1 + -1;
> >  
> >:
> > +  ivtmp.8_11 = ivtmp.8_8 - 524288;
> >goto ;
> >  
> >  }
> > 
> > note that the infinite loop contains undefined overflow.
> > 
> > IVOPTs should simply strip the overflow flag (using drop_tree_overflow).
> 
> And my further investigation shows PR68326 is caused by the same issue.
> 
>  # ivtmp.8_8 = PHI <4294443008(OVF)(2), ivtmp.8_11(4)>
> 
> the new phi node destination is with unsigned int type, the constant
> value 4294443008 can fit into it, it's marked as OVF because
> it's treated as signed type. For the simple testcase in PR68326,
> the overflow number is 4294967286 which is -10, while there happen be
> another signed integer with initial value -10. So, looks like the unsigned
> 4294967286 somehow inherited the signed type from the other value in some
> tree pass, then some valid constant is marked with OVF unnecessarily.
> 
> Anyway, below is my fix, does it looks the correct approach to you?
> 
> drop_tree_overflow is invoked during create_iv, if the constant can actually
> fit into the type. I only checked INTEGER_CST, not for others like REAL, as I
> though they won't suffer from the unsigned/signed type issue.
> 
> x86-64 bootstrap is OK with this patch, will do more testing if the approach
> is OK.
> 
> diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
> index b614412..55a6334 100644
> --- a/gcc/tree-ssa-loop-manip.c
> +++ b/gcc/tree-ssa-loop-manip.c
> @@ -136,6 +136,11 @@ create_iv (tree base, tree step, tree var, struct loop
> *loop,
>  gsi_insert_seq_on_edge_immediate (pe, stmts);
>  
>phi = create_phi_node (vb, loop->header);
> +  if (TREE_OVERFLOW (initial)
> +  && TREE_CODE (initial) == INTEGER_CST
> +  && int_fits_type_p (initial, TREE_TYPE (vb)))
> +initial = drop_tree_overflow (initial);
> +
>add_phi_arg (phi, initial, loop_preheader_edge (loop), UNKNOWN_LOCATION);
>add_phi_arg (phi, va, loop_latch_edge (loop), UNKNOWN_LOCATION);
>  }

I think it's better to track down where the constant is generated.  I
see initial is created by

  initial = force_gimple_operand (base, , true, var);

thus likely base is already the same constant (passed from the caller).

I usually set a breakpoint on the return statement of ggc_internal_alloc
conditional on the return value being the tree with the overflow.

Once the overflow value is returned from fold_* () it should be stripped
off its overflow flag.  Unconditionally so with just

  if (TREE_OVERFLOW_P (..))
   .. = drop_tree_overflow (..);

[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[jiwang at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

--- Comment #6 from Jiong Wang  ---
Created attachment 36741
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36741=edit
prototype-fix

(In reply to Richard Biener from comment #3)
> (gdb) p debug_generic_expr (max)
> 4294443008(OVF)
> +  # ivtmp.8_8 = PHI <4294443008(OVF)(2), ivtmp.8_11(4)>
> +  _5 = (int) ivtmp.8_8;
>fn2 (_5);
> -  i_7 = i_1 + -1;
>  
>:
> +  ivtmp.8_11 = ivtmp.8_8 - 524288;
>goto ;
>  
>  }
> 
> note that the infinite loop contains undefined overflow.
> 
> IVOPTs should simply strip the overflow flag (using drop_tree_overflow).

And my further investigation shows PR68326 is caused by the same issue.

 # ivtmp.8_8 = PHI <4294443008(OVF)(2), ivtmp.8_11(4)>

the new phi node destination is with unsigned int type, the constant
value 4294443008 can fit into it, it's marked as OVF because
it's treated as signed type. For the simple testcase in PR68326,
the overflow number is 4294967286 which is -10, while there happen be
another signed integer with initial value -10. So, looks like the unsigned
4294967286 somehow inherited the signed type from the other value in some
tree pass, then some valid constant is marked with OVF unnecessarily.

Anyway, below is my fix, does it looks the correct approach to you?

drop_tree_overflow is invoked during create_iv, if the constant can actually
fit into the type. I only checked INTEGER_CST, not for others like REAL, as I
though they won't suffer from the unsigned/signed type issue.

x86-64 bootstrap is OK with this patch, will do more testing if the approach is
OK.

diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index b614412..55a6334 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -136,6 +136,11 @@ create_iv (tree base, tree step, tree var, struct loop
*loop,
 gsi_insert_seq_on_edge_immediate (pe, stmts);

   phi = create_phi_node (vb, loop->header);
+  if (TREE_OVERFLOW (initial)
+  && TREE_CODE (initial) == INTEGER_CST
+  && int_fits_type_p (initial, TREE_TYPE (vb)))
+initial = drop_tree_overflow (initial);
+
   add_phi_arg (phi, initial, loop_preheader_edge (loop), UNKNOWN_LOCATION);
   add_phi_arg (phi, va, loop_latch_edge (loop), UNKNOWN_LOCATION);
 }

[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[jiwang at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

Jiong Wang  changed:

   What|Removed |Added

 CC||jiwang at gcc dot gnu.org

--- Comment #5 from Jiong Wang  ---
(In reply to Marek Polacek from comment #4)
> FWIW, started with r230150.

Sorry for the breakage, let me have a further check

[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

Marek Polacek  changed:

   What|Removed |Added

 CC||mpolacek at gcc dot gnu.org

--- Comment #4 from Marek Polacek  ---
FWIW, started with r230150.

[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

Richard Biener  changed:

   What|Removed |Added

   Target Milestone|--- |6.0

--- Comment #3 from Richard Biener  ---
(gdb) p debug_generic_expr (max)
4294443008(OVF)

We have OVF in the IL before VRP:

fn1 ()
{
  unsigned int ivtmp.8;
  int i;
  int _5;

  :

  :
  # ivtmp.8_8 = PHI <4294443008(OVF)(2), ivtmp.8_11(3)>
  _5 = (int) ivtmp.8_8;
  fn2 (_5);
  ivtmp.8_11 = ivtmp.8_8 - 524288;
  goto ;

introduced by IVOPTs which does

 fn1 ()
 {
+  unsigned int ivtmp.8;
   int i;
-  int _4;
   int _5;

   :

   :
-  # i_1 = PHI <7(2), i_7(4)>
-  _4 = i_1 + 8184;
-  _5 = _4 * 524288;
+  # ivtmp.8_8 = PHI <4294443008(OVF)(2), ivtmp.8_11(4)>
+  _5 = (int) ivtmp.8_8;
   fn2 (_5);
-  i_7 = i_1 + -1;

   :
+  ivtmp.8_11 = ivtmp.8_8 - 524288;
   goto ;

 }

note that the infinite loop contains undefined overflow.

IVOPTs should simply strip the overflow flag (using drop_tree_overflow).

[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

Markus Trippelsdorf  changed:

   What|Removed |Added

 CC||su at cs dot ucdavis.edu

--- Comment #2 from Markus Trippelsdorf  ---
*** Bug 68326 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/68317] [6 regression] ice in set_value_range, at tree-vrp.c:380

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68317

Markus Trippelsdorf  changed:

   What|Removed |Added

 Status|UNCONFIRMED |NEW
   Last reconfirmed||2015-11-12
 CC||trippels at gcc dot gnu.org
  Component|c   |tree-optimization
Summary|ice in set_value_range, at  |[6 regression] ice in
   |tree-vrp.c:380  |set_value_range, at
   ||tree-vrp.c:380
 Ever confirmed|0   |1

--- Comment #1 from Markus Trippelsdorf  ---
markus@x4 tmp % cat bug243.c
extern int fn2(int);
void fn1() {
  int i = 7;
  for (;; i--)
fn2((8184 + i) * 524288);
}

markus@x4 tmp % gcc -c -O2 bug243.c
bug243.c: In function ‘fn1’:
bug243.c:2:6: internal compiler error: in set_value_range, at tree-vrp.c:380