[Bug tree-optimization/34244] New: [4.3 Regression] VRP/SCEV miscompiles Firefox

[Bug tree-optimization/34244] New: [4.3 Regression] VRP/SCEV miscompiles Firefox

[rguenth at gcc dot gnu dot org]

int* GetParent(void);
int* FindCommonAncestor(int *aNode1, int *aNode2)
{
  if (aNode1 && aNode2) {
    int offset = 0; 
    int *anc1 = aNode1;
    for (;;) {
      ++offset;
      int * parent = GetParent();
      if (!parent)
        break;
      anc1 = parent;
    }
    int *anc2 = aNode2;
    for (;;) { 
      --offset;
      int * parent = GetParent();
      if (!parent)
        break;
      anc2 = parent;
    }
    if (anc1 == anc2) {
      anc1 = aNode1;
      anc2 = aNode2;
      while (offset > 0) {
        anc1 = GetParent();
        --offset;
      }
      while (offset < 0) {
        anc2 = GetParent();
        ++offset;
      }
      while (anc1 != anc2) {
        anc1 = GetParent();
        anc2 = GetParent();
      }
      return anc1;
    }
  }
  return 0;
}

Folding predicate offset_5 < 0 to 0
Folded statement: if (offset_5 < 0)
            into: if (0)

that is, the second last loop is never executed according to VRP/SCEV because
the exit value of the third last loop

<bb 26>:
  offset_48 = ASSERT_EXPR <offset_4, offset_4 <= 0>;

is adjusted to [0, 0] by SCEV:

Visiting statement:
offset_48 = ASSERT_EXPR <offset_4, offset_4 <= 0>;

(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_48)
(get_scalar_evolution
  (scalar = offset_48)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_4)
(get_scalar_evolution
  (scalar = offset_4)
  (scalar_evolution = ))
(analyze_initial_condition
  (loop_phi_node =
offset_4 = PHI <offset_37(10), offset_32(9)>)
  (init_cond = offset_37))
(analyze_evolution_in_loop
  (loop_phi_node = offset_4 = PHI <offset_37(10), offset_32(9)>)
(add_to_evolution
  (loop_nb = 3)
  (chrec_before = offset_37)
  (to_add = -1)
  (res = {offset_37, +, -1}_3))
  (evolution_function = {offset_37, +, -1}_3))
(set_scalar_evolution
  (scalar = offset_4)
  (scalar_evolution = {offset_37, +, -1}_3))
(number_of_iterations_in_loop
(analyze_scalar_evolution
  (loop_nb = 3)
  (scalar = offset_4)
(get_scalar_evolution
  (scalar = offset_4)
  (scalar_evolution = {offset_37, +, -1}_3))
(set_scalar_evolution
  (scalar = offset_4)
  (scalar_evolution = {offset_37, +, -1}_3))
)
(analyze_scalar_evolution
  (loop_nb = 3)
  (scalar = 0)
(get_scalar_evolution
  (scalar = 0)
  (scalar_evolution = 0))
)
Analyzing # of iterations of loop 3
  exit condition 0 < [offset_46, + , -1](no_overflow)
  bounds on difference of bases: -2147483648 ... 2147483647
  result:
    # of iterations (unsigned int) offset_46, bounded by 2147483647
  (set_nb_iterations_in_loop = (unsigned int) offset_46))
(chrec_apply 
  (varying_loop = 3
) 
  (chrec = {offset_37, +, -1}_3)
  (x = offset_46)
  (res = offset_37 - offset_46))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_37)
(get_scalar_evolution 
  (scalar = offset_37)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_46)
(get_scalar_evolution 
  (scalar = offset_46)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_24)
(get_scalar_evolution 
  (scalar = offset_24)
  (scalar_evolution = {offset_40 + -1, +, -1}_2))
(number_of_iterations_in_loop
(analyze_scalar_evolution
  (loop_nb = 2)
  (scalar = parent_25)
(get_scalar_evolution 
  (scalar = parent_25)
  (scalar_evolution = parent_25))
(set_scalar_evolution 
  (scalar = parent_25)
  (scalar_evolution = parent_25))
)
(analyze_scalar_evolution
  (loop_nb = 2)
  (scalar = parent_25)
(get_scalar_evolution 
  (scalar = parent_25)
  (scalar_evolution = parent_25))
(set_scalar_evolution 
  (scalar = parent_25)
  (scalar_evolution = parent_25))
) 
  (set_nb_iterations_in_loop = scev_not_known))
)
(set_scalar_evolution 
  (scalar = offset_46)
  (scalar_evolution = offset_24))
)
(set_scalar_evolution 
  (scalar = offset_37)
  (scalar_evolution = offset_24))
)
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_46)
(get_scalar_evolution
  (scalar = offset_46)
  (scalar_evolution = offset_24))
(set_scalar_evolution
  (scalar = offset_46)
  (scalar_evolution = offset_24))
)
)
(set_scalar_evolution
  (scalar = offset_48)
  (scalar_evolution = 0))
)
(instantiate_parameters
  (loop_nb = 0)
  (chrec = 0)
  (res = 0))
Found new range for offset_48: [0, 0]

where the particular error looks like this:

Analyzing # of iterations of loop 3
  exit condition 0 < [offset_46, + , -1](no_overflow)
  bounds on difference of bases: -2147483648 ... 2147483647
  result:
    # of iterations (unsigned int) offset_46, bounded by 2147483647
  (set_nb_iterations_in_loop = (unsigned int) offset_46))

as it may be zero, in case offset_46 is <= 0.

Sebastian, Zdenek - any idea what goes wrong here?


-- 
           Summary: [4.3 Regression] VRP/SCEV miscompiles Firefox
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rguenth at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2007-11-27 11:30 -------
Runtime testcase:

int __attribute__((noinline)) GetParent(void)
{
  static int count = 0;
  count++;
  switch (count)
    {
    case 1:
    case 3:
    case 4:
        return 1;
    default:
        return 0;
    }
}
int __attribute__((noinline)) FindCommonAncestor(int aNode1, int aNode2)
{
  if (aNode1 && aNode2) {
    int offset = 0;
    int anc1 = aNode1;
    for (;;) {
      ++offset;
      int  parent = GetParent();
      if (!parent)
        break;
      anc1 = parent;
    }
    int anc2 = aNode2;
    for (;;) {
      --offset;
      int  parent = GetParent();
      if (!parent)
        break;
      anc2 = parent;
    }
    if (anc1 == anc2) {
      anc1 = aNode1;
      anc2 = aNode2;
      while (offset > 0) {
        anc1 = GetParent();
        --offset;
      }
      while (offset < 0) {
        anc2 = GetParent();
        ++offset;
      }
      while (anc1 != anc2) {
        anc1 = GetParent();
        anc2 = GetParent();
      } 
      return anc1;
    }
  }
  return 0;
}
extern void abort (void);
int main()
{
  if (FindCommonAncestor (1, 1) != 0)
    abort ();
  return 0;
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
   Target Milestone|---                         |4.3.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rakdver at gcc dot gnu dot org]

------- Comment #2 from rakdver at gcc dot gnu dot org  2007-11-27 13:57 -------
I will have a look.  What target is this on, and what flags are used for
compilation?


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rakdver at gcc dot gnu dot
                   |dot org                     |org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-11-27 13:57:41
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rguenther at suse dot de]

------- Comment #3 from rguenther at suse dot de  2007-11-27 14:04 -------
Subject: Re:  [4.3 Regression] VRP/SCEV miscompiles
 Firefox

On Tue, 27 Nov 2007, rakdver at gcc dot gnu dot org wrote:

> ------- Comment #2 from rakdver at gcc dot gnu dot org  2007-11-27 13:57 -------
> I will have a look.  What target is this on, and what flags are used for
> compilation?

It fails independent of the target (x86_64 and i686 for me), -O[123s]
with -ftree-vrp enabled makes it fail.

Richard.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rakdver at gcc dot gnu dot org]

------- Comment #4 from rakdver at gcc dot gnu dot org  2007-11-27 16:48 -------
> as it may be zero, in case offset_46 is <= 0.
> 
> Sebastian, Zdenek - any idea what goes wrong here?

# of iteration analysis records an assumption that offset_46 >= 0.  However,
this is simplified to true, as the value range of offset_46 is set to [0,0] by
vrp (which seems to be wrong); so the problem is probably somewhere else in
vrp.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rakdver at gcc dot gnu dot org]

------- Comment #5 from rakdver at gcc dot gnu dot org  2007-11-27 17:00 -------
> # of iteration analysis records an assumption that offset_46 >= 0.  However,
> this is simplified to true, as the value range of offset_46 is set to [0,0] by
> vrp (which seems to be wrong); so the problem is probably somewhere else in
> vrp.

So the problem is the following:  we have a code like

if (something)
  offset = 100;
else
  offset = -100;

while (offset > 0)
  offset--;

if (offset == 0)
  launch_nuclear_rockets ();

VRP starts simulating the code, first executing the true branch of the if
(something) condition, getting offset = 100.  It then proceeds with the loop,
determining that number of iterations is offset (since we just now believe that
offset==100, this is correct, without any assumptions), thus the final value of
offset is 0 and the nuclear war always starts.

Later, VRP evaluates the false branch of the if (something) condition, setting
the value range of offset to [-100,100], and proceeds to re-evaluate the
effects of the loop.  However, scev caches the number of iterations of the
loop, so it is not re-evaluated, and we keep believing that the number of
iterations is always offset.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2007-11-28 15:47 -------
We could clear the SCEV cache for an SSA_NAME we set a new value range
(in set_value_range and set_value_range_to_varying), but I
see that SCEV also caches loop->nb_iterations which we probably would need to
clear unconditionally (for all loops).


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rakdver at kam dot mff dot cuni dot cz]

------- Comment #7 from rakdver at kam dot mff dot cuni dot cz  2007-11-28 16:05 -------
Subject: Re:  [4.3 Regression] VRP/SCEV miscompiles Firefox

> ------- Comment #6 from rguenth at gcc dot gnu dot org  2007-11-28 15:47 -------
> We could clear the SCEV cache for an SSA_NAME we set a new value range
> (in set_value_range and set_value_range_to_varying), but I
> see that SCEV also caches loop->nb_iterations which we probably would need to
> clear unconditionally (for all loops).

yes, the simplest solution is to call scev_reset somewhere (either in
set_value_range, or in adjust_range_with_scev).  However, I fear the
compile time impact would be too large (# of iterations analysis is
fairly time consuming, and not caching the results used to cause
us to spend 10% or more in it).

More feasible solution seems to be to determine the number of iterations
for all loops before the start of VRP, and to remember the values.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rguenther at suse dot de]

------- Comment #8 from rguenther at suse dot de  2007-11-28 16:13 -------
Subject: Re:  [4.3 Regression] VRP/SCEV miscompiles
 Firefox

On Wed, 28 Nov 2007, rakdver at kam dot mff dot cuni dot cz wrote:

> > ------- Comment #6 from rguenth at gcc dot gnu dot org  2007-11-28 15:47 -------
> > We could clear the SCEV cache for an SSA_NAME we set a new value range
> > (in set_value_range and set_value_range_to_varying), but I
> > see that SCEV also caches loop->nb_iterations which we probably would need to
> > clear unconditionally (for all loops).
> 
> yes, the simplest solution is to call scev_reset somewhere (either in
> set_value_range, or in adjust_range_with_scev).  However, I fear the
> compile time impact would be too large (# of iterations analysis is
> fairly time consuming, and not caching the results used to cause
> us to spend 10% or more in it).
> 
> More feasible solution seems to be to determine the number of iterations
> for all loops before the start of VRP, and to remember the values.

Or not use tree_expr_nonnegative_p from inside tree-ssa-loop-niter.c
which is where the bad feedback comes from.  But yes, computing the
number of iterations in advance should fix this as well and is probably
best.

Richard.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rakdver at gcc dot gnu dot org]

------- Comment #9 from rakdver at gcc dot gnu dot org  2007-11-29 04:29 -------
Patch: http://gcc.gnu.org/ml/gcc-patches/2007-11/msg01607.html


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |http://gcc.gnu.org/ml/gcc-
                   |                            |patches/2007-
                   |                            |11/msg01607.html


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rakdver at gcc dot gnu dot org]

------- Comment #10 from rakdver at gcc dot gnu dot org  2007-11-30 00:32 -------
Subject: Bug 34244

Author: rakdver
Date: Fri Nov 30 00:32:04 2007
New Revision: 130527

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=130527
Log:
        PR tree-optimization/34244
        * tree-vrp.c (adjust_range_with_scev): Clear scev cache.
        (record_numbers_of_iterations): New function.
        (execute_vrp): Cache the numbers of iterations of loops.
        * tree-scalar-evolution.c (scev_reset_except_niters):
        New function.
        (scev_reset): Use scev_reset_except_niters.
        * tree-scalar-evolution.h (scev_reset_except_niters): Declare.

        * gcc.dg/tree-ssa/pr34244.c: New test.


Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr34244.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-scalar-evolution.c
    trunk/gcc/tree-scalar-evolution.h
    trunk/gcc/tree-vrp.c


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[jakub at gcc dot gnu dot org]

------- Comment #11 from jakub at gcc dot gnu dot org  2007-11-30 07:20 -------
Fixed, thanks.


-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[hjl at lucon dot org]

------- Comment #12 from hjl at lucon dot org  2007-11-30 08:56 -------
gcc.dg/tree-ssa/pr34244.c in

http://gcc.gnu.org/viewcvs?view=rev&revision=130527

has duplicated content.


-- 

hjl at lucon dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|FIXED                       |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[jakub at gcc dot gnu dot org]

------- Comment #13 from jakub at gcc dot gnu dot org  2007-11-30 13:24 -------
Zdenek fixed that.


-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rguenth at gcc dot gnu dot org]

------- Comment #14 from rguenth at gcc dot gnu dot org  2008-05-31 13:01 -------
Subject: Bug 34244

Author: rguenth
Date: Sat May 31 13:01:10 2008
New Revision: 136237

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=136237
Log:
2008-05-31  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/34244
        * fold-const.c (tree_expr_nonnegative_warnv_p): Do not ask VRP.
        (tree_expr_nonzero_warnv_p): Likewise.
        * tree-vrp.c (vrp_expr_computes_nonnegative): Call
        ssa_name_nonnegative_p.
        (vrp_expr_computes_nonzero): Call ssa_name_nonzero_p.
        (extract_range_from_unary_expr): Use vrp_expr_computes_nonzero,
        not tree_expr_nonzero_warnv_p.

        PR tree-optimization/36262
        Revert
        2007-11-29  Zdenek Dvorak  <ook@ucw.cz>

        PR tree-optimization/34244
        * tree-vrp.c (adjust_range_with_scev): Clear scev cache.
        (record_numbers_of_iterations): New function.
        (execute_vrp): Cache the numbers of iterations of loops.
        * tree-scalar-evolution.c (scev_reset_except_niters):
        New function.
        (scev_reset): Use scev_reset_except_niters.
        * tree-scalar-evolution.h (scev_reset_except_niters): Declare.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/tree-scalar-evolution.c
    trunk/gcc/tree-scalar-evolution.h
    trunk/gcc/tree-vrp.c


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244

[Bug tree-optimization/34244] [4.3 Regression] VRP/SCEV miscompiles Firefox

[rguenth at gcc dot gnu dot org]

------- Comment #15 from rguenth at gcc dot gnu dot org  2008-06-06 20:07 -------
Subject: Bug 34244

Author: rguenth
Date: Fri Jun  6 20:06:40 2008
New Revision: 136501

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=136501
Log:
2008-06-06  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/34244
        * fold-const.c (tree_expr_nonnegative_warnv_p): Do not ask VRP.
        (tree_expr_nonzero_warnv_p): Likewise.
        * tree-vrp.c (vrp_expr_computes_nonnegative): Call
        ssa_name_nonnegative_p.
        (vrp_expr_computes_nonzero): Call ssa_name_nonzero_p.
        (extract_range_from_unary_expr): Use vrp_expr_computes_nonzero,
        not tree_expr_nonzero_warnv_p.

        PR tree-optimization/36262
        Revert
        2007-11-29  Zdenek Dvorak  <ook@ucw.cz>

        PR tree-optimization/34244
        * tree-vrp.c (adjust_range_with_scev): Clear scev cache.
        (record_numbers_of_iterations): New function.
        (execute_vrp): Cache the numbers of iterations of loops.
        * tree-scalar-evolution.c (scev_reset_except_niters):
        New function.
        (scev_reset): Use scev_reset_except_niters.
        * tree-scalar-evolution.h (scev_reset_except_niters): Declare.

Modified:
    branches/gcc-4_3-branch/gcc/ChangeLog
    branches/gcc-4_3-branch/gcc/fold-const.c
    branches/gcc-4_3-branch/gcc/tree-scalar-evolution.c
    branches/gcc-4_3-branch/gcc/tree-scalar-evolution.h
    branches/gcc-4_3-branch/gcc/tree-vrp.c


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34244