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?
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; }
I will have a look. What target is this on, and what flags are used for compilation?
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.
> 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.
> # 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.
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).
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.
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.
Patch: http://gcc.gnu.org/ml/gcc-patches/2007-11/msg01607.html
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
Fixed, thanks.
gcc.dg/tree-ssa/pr34244.c in http://gcc.gnu.org/viewcvs?view=rev&revision=130527 has duplicated content.
Zdenek fixed that.
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
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