public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/57343] wrong code on x86_64-linux at -Os and above
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
@ 2013-05-20 22:55 ` glisse at gcc dot gnu.org
2013-05-21 6:23 ` [Bug tree-optimization/57343] [4.8/4.9 Regression] " jakub at gcc dot gnu.org
` (9 subsequent siblings)
10 siblings, 0 replies; 11+ messages in thread
From: glisse at gcc dot gnu.org @ 2013-05-20 22:55 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
Marc Glisse <glisse at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Keywords| |wrong-code
Component|rtl-optimization |tree-optimization
--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Reduced a bit:
int printf (const char *, ...);
int c = 0;
int main ()
{
int i;
int f = 1;
for (i = 0; i < 5; i++)
{
--c;
unsigned char h = c * 100;
if (h == 0)
{
f = 0;
break;
}
}
printf ("%d\n", f);
return 0;
}
-O1 is enough. Disabling cunroll seems to help.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
2013-05-20 22:55 ` [Bug tree-optimization/57343] wrong code on x86_64-linux at -Os and above glisse at gcc dot gnu.org
@ 2013-05-21 6:23 ` jakub at gcc dot gnu.org
2013-05-21 9:54 ` rguenth at gcc dot gnu.org
` (8 subsequent siblings)
10 siblings, 0 replies; 11+ messages in thread
From: jakub at gcc dot gnu.org @ 2013-05-21 6:23 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Last reconfirmed| |2013-05-21
CC| |jakub at gcc dot gnu.org
Target Milestone|--- |4.8.1
Summary|wrong code on x86_64-linux |[4.8/4.9 Regression] wrong
|at -Os and above |code on x86_64-linux at -Os
| |and above
Ever confirmed|0 |1
--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r193098 .
int c = 0;
int
main ()
{
int i, f = 1;
for (i = 0; i < 5; i++)
{
--c;
unsigned char h = c * 100;
if (h == 0)
{
f = 0;
break;
}
}
if (f != 1)
__builtin_abort ();
return 0;
}
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
2013-05-20 22:55 ` [Bug tree-optimization/57343] wrong code on x86_64-linux at -Os and above glisse at gcc dot gnu.org
2013-05-21 6:23 ` [Bug tree-optimization/57343] [4.8/4.9 Regression] " jakub at gcc dot gnu.org
@ 2013-05-21 9:54 ` rguenth at gcc dot gnu.org
2013-05-21 11:54 ` rguenth at gcc dot gnu.org
` (7 subsequent siblings)
10 siblings, 0 replies; 11+ messages in thread
From: rguenth at gcc dot gnu.org @ 2013-05-21 9:54 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|NEW |ASSIGNED
Assignee|unassigned at gcc dot gnu.org |rguenth at gcc dot gnu.org
--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I'll have a look.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
` (2 preceding siblings ...)
2013-05-21 9:54 ` rguenth at gcc dot gnu.org
@ 2013-05-21 11:54 ` rguenth at gcc dot gnu.org
2013-05-21 12:19 ` rguenth at gcc dot gnu.org
` (6 subsequent siblings)
10 siblings, 0 replies; 11+ messages in thread
From: rguenth at gcc dot gnu.org @ 2013-05-21 11:54 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |rakdver at gcc dot gnu.org
--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
The value C is equal to final - base, where final and base are the final and
initial value of the actual induction variable in the analysed loop. BNDS
bounds the value of this difference when computed in signed type with
unbounded range, while the computation of C is performed in an unsigned
type with the range matching the range of the type of the induction
variable.
In particular, BNDS.up contains an upper bound on C in the following cases:
-- if the iv must reach its final value without overflow, i.e., if
NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
-- if final >= base, which we know to hold when BNDS.below >= 0. */
static void
number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
bounds *bnds, bool exit_must_be_taken)
{
double_int max;
mpz_t d;
bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
|| mpz_sgn (bnds->below) >= 0);
for the case in question (IV of unsigned char type, base
((unsigned char) (c_lsm.4_12 + -1)) * 100 and step 100 (negated 156))
the bnds values (below 0, up 255 - full range of unsigned char) the
fact that the IV overflows cannot be simply ignored - and I don't see
how we can derive from below >= 0 that final (which is zero!) is
>= base.
We then fall to
if (multiple_of_p (TREE_TYPE (c), c, s))
{
/* If C is an exact multiple of S, then its value will be reached before
the induction variable overflows (unless the loop is exited in some
other way before). Note that the actual induction variable in the
loop (which ranges from base to final instead of from 0 to C) may
overflow, in which case BNDS.up will not be giving a correct upper
bound on C; thus, BNDS_U_VALID had to be computed in advance. */
no_overflow = true;
exit_must_be_taken = true;
which ends up with no_overflow = true and things going downhill from here.
Note that the original, non-negated bnds would _not_ have mpz_sgn (bnds->below)
>= 0 (but -255):
/* Rearrange the terms so that we get inequality S * i <> C, with S
positive. Also cast everything to the unsigned type. If IV does
not overflow, BNDS bounds the value of C. Also, this is the
case if the computation |FINAL - IV->base| does not overflow, i.e.,
if BNDS->below in the result is nonnegative. */
if (tree_int_cst_sign_bit (iv->step))
{
s = fold_convert (niter_type,
fold_build1 (NEGATE_EXPR, type, iv->step));
c = fold_build2 (MINUS_EXPR, niter_type,
fold_convert (niter_type, iv->base),
fold_convert (niter_type, final));
bounds_negate (bnds);
Here |FINAL - IV->base| does overflow, but bounds_negate shadows this.
But even before that we have IVCANON remove the pointless exit
Removed pointless exit: if (i_11 <= 4)
Added canonical iv to loop 1, 3 iterations.
then it adds back the canonical IV, but that's pointless in the next
analysis run done by cunroll and removed there.
The bogus upper bound is determined from local_pure_const via finite_loop_p ()
on the non-header-copied form and the estimate from the h == 0 test.
Analyzing # of iterations of loop 1
exit condition [(unsigned char) (c_6 + -1) * 100, + , 156] != 0
bounds on difference of bases: -255 ... 0
result:
# of iterations (((unsigned char) (c_6 + -1) * 100) /[ex] 4) * 41 & 63,
bounded by 2
In the end I think that number_of_iterations_ne_max does not properly
honor the case where for
if (multiple_of_p (TREE_TYPE (c), c, s))
{
/* If C is an exact multiple of S, then its value will be reached before
the induction variable overflows (unless the loop is exited in some
other way before). Note that the actual induction variable in the
loop (which ranges from base to final instead of from 0 to C) may
overflow, in which case BNDS.up will not be giving a correct upper
bound on C; thus, BNDS_U_VALID had to be computed in advance. */
no_overflow = true;
that multiply overflows. At least the IV does not range from 0 to C
for (unsigned char) (c_6 + -1) * 100.
I have a hard time following the logic that this all is correct for
wrapping IVs ... that said,
Index: gcc/tree-ssa-loop-niter.c
===================================================================
--- gcc/tree-ssa-loop-niter.c (revision 199137)
+++ gcc/tree-ssa-loop-niter.c (working copy)
@@ -627,7 +627,7 @@ number_of_iterations_ne (tree type, affi
not overflow, BNDS bounds the value of C. Also, this is the
case if the computation |FINAL - IV->base| does not overflow, i.e.,
if BNDS->below in the result is nonnegative. */
- if (tree_int_cst_sign_bit (iv->step))
+ if (tree_int_cst_sgn (iv->step) == -1)
{
s = fold_convert (niter_type,
fold_build1 (NEGATE_EXPR, type, iv->step));
fixes the testcase (otherwise untested).
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
` (3 preceding siblings ...)
2013-05-21 11:54 ` rguenth at gcc dot gnu.org
@ 2013-05-21 12:19 ` rguenth at gcc dot gnu.org
2013-05-21 14:41 ` rakdver at gcc dot gnu.org
` (5 subsequent siblings)
10 siblings, 0 replies; 11+ messages in thread
From: rguenth at gcc dot gnu.org @ 2013-05-21 12:19 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> Index: gcc/tree-ssa-loop-niter.c
> ===================================================================
> --- gcc/tree-ssa-loop-niter.c (revision 199137)
> +++ gcc/tree-ssa-loop-niter.c (working copy)
> @@ -627,7 +627,7 @@ number_of_iterations_ne (tree type, affi
> not overflow, BNDS bounds the value of C. Also, this is the
> case if the computation |FINAL - IV->base| does not overflow, i.e.,
> if BNDS->below in the result is nonnegative. */
> - if (tree_int_cst_sign_bit (iv->step))
> + if (tree_int_cst_sgn (iv->step) == -1)
> {
> s = fold_convert (niter_type,
> fold_build1 (NEGATE_EXPR, type, iv->step));
>
> fixes the testcase (otherwise untested).
Doesn't work and fails bootstrap.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
` (4 preceding siblings ...)
2013-05-21 12:19 ` rguenth at gcc dot gnu.org
@ 2013-05-21 14:41 ` rakdver at gcc dot gnu.org
2013-05-27 7:55 ` rguenther at suse dot de
` (4 subsequent siblings)
10 siblings, 0 replies; 11+ messages in thread
From: rakdver at gcc dot gnu.org @ 2013-05-21 14:41 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
--- Comment #6 from Zdenek Dvorak <rakdver at gcc dot gnu.org> ---
I will have a look.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
` (5 preceding siblings ...)
2013-05-21 14:41 ` rakdver at gcc dot gnu.org
@ 2013-05-27 7:55 ` rguenther at suse dot de
2013-05-27 9:01 ` rguenth at gcc dot gnu.org
` (3 subsequent siblings)
10 siblings, 0 replies; 11+ messages in thread
From: rguenther at suse dot de @ 2013-05-27 7:55 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
--- Comment #8 from rguenther at suse dot de <rguenther at suse dot de> ---
On Fri, 24 May 2013, rakdver at gcc dot gnu.org wrote:
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
>
> --- Comment #7 from Zdenek Dvorak <rakdver at gcc dot gnu.org> ---
> (In reply to Richard Biener from comment #4)
> > We then fall to
> >
> > if (multiple_of_p (TREE_TYPE (c), c, s))
> > {
> > /* If C is an exact multiple of S, then its value will be reached
> > before
> > the induction variable overflows (unless the loop is exited in some
> > other way before). Note that the actual induction variable in the
> > loop (which ranges from base to final instead of from 0 to C) may
> > overflow, in which case BNDS.up will not be giving a correct upper
> > bound on C; thus, BNDS_U_VALID had to be computed in advance. */
> > no_overflow = true;
> > exit_must_be_taken = true;
> >
> > which ends up with no_overflow = true and things going downhill from here.
>
> This is the problem -- multiple_of_p claims that (var * 100) is a multiple of
> 100, which is not the case if the multiplication overflows. I am not sure
> whether this is an expected behavior of multiple_of_p, or whether this could
> cause problems in its other uses.
>
> A conservative fix here would be to replace the multiple_of_p test here by some
> safer tests -- important special cases are:
> 1) both c and s are constants and c is a multiple of s
> 2) s = 1
Thanks. I'll audit other uses of multiple_of_p to see whether the
current behavior is desired or a bug.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug tree-optimization/57343] [4.8/4.9 Regression] wrong code on x86_64-linux at -Os and above
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
` (6 preceding siblings ...)
2013-05-27 7:55 ` rguenther at suse dot de
@ 2013-05-27 9:01 ` rguenth at gcc dot gnu.org
2013-05-27 13:03 ` [Bug tree-optimization/57343] [4.8 " rguenth at gcc dot gnu.org
` (2 subsequent siblings)
10 siblings, 0 replies; 11+ messages in thread
From: rguenth at gcc dot gnu.org @ 2013-05-27 9:01 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to rguenther@suse.de from comment #8)
> On Fri, 24 May 2013, rakdver at gcc dot gnu.org wrote:
>
> > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
> >
> > --- Comment #7 from Zdenek Dvorak <rakdver at gcc dot gnu.org> ---
> > (In reply to Richard Biener from comment #4)
> > > We then fall to
> > >
> > > if (multiple_of_p (TREE_TYPE (c), c, s))
> > > {
> > > /* If C is an exact multiple of S, then its value will be reached
> > > before
> > > the induction variable overflows (unless the loop is exited in some
> > > other way before). Note that the actual induction variable in the
> > > loop (which ranges from base to final instead of from 0 to C) may
> > > overflow, in which case BNDS.up will not be giving a correct upper
> > > bound on C; thus, BNDS_U_VALID had to be computed in advance. */
> > > no_overflow = true;
> > > exit_must_be_taken = true;
> > >
> > > which ends up with no_overflow = true and things going downhill from here.
> >
> > This is the problem -- multiple_of_p claims that (var * 100) is a multiple of
> > 100, which is not the case if the multiplication overflows. I am not sure
> > whether this is an expected behavior of multiple_of_p, or whether this could
> > cause problems in its other uses.
> >
> > A conservative fix here would be to replace the multiple_of_p test here by some
> > safer tests -- important special cases are:
> > 1) both c and s are constants and c is a multiple of s
> > 2) s = 1
>
> Thanks. I'll audit other uses of multiple_of_p to see whether the
> current behavior is desired or a bug.
Most uses are ok, the extract_muldiv_1 use is questionable. I'll fixup
the use in niter analysis like the following:
- if (multiple_of_p (TREE_TYPE (c), c, s))
+ if (integer_onep (s)
+ || (TREE_CODE (c) == INTEGER_CST
+ && TREE_CODE (s) == INTEGER_CST
+ && tree_to_double_int (c).mod (tree_to_double_int (s),
+ TYPE_UNSIGNED (type),
+ EXACT_DIV_EXPR).is_zero ())
+ || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (c))
+ && multiple_of_p (type, c, s)))
{
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug tree-optimization/57343] [4.8 Regression] wrong code on x86_64-linux at -Os and above
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
` (7 preceding siblings ...)
2013-05-27 9:01 ` rguenth at gcc dot gnu.org
@ 2013-05-27 13:03 ` rguenth at gcc dot gnu.org
2013-08-29 13:09 ` jakub at gcc dot gnu.org
2013-08-29 13:17 ` jakub at gcc dot gnu.org
10 siblings, 0 replies; 11+ messages in thread
From: rguenth at gcc dot gnu.org @ 2013-05-27 13:03 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Known to work| |4.9.0
Target Milestone|4.8.1 |4.8.2
Summary|[4.8/4.9 Regression] wrong |[4.8 Regression] wrong code
|code on x86_64-linux at -Os |on x86_64-linux at -Os and
|and above |above
Known to fail| |4.8.1
--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Mon May 27 13:02:24 2013
New Revision: 199357
URL: http://gcc.gnu.org/viewcvs?rev=199357&root=gcc&view=rev
Log:
2013-05-27 Richard Biener <rguenther@suse.de>
PR tree-optimization/57343
* tree-ssa-loop-niter.c (number_of_iterations_ne_max): Do not
use multiple_of_p if not TYPE_OVERFLOW_UNDEFINED.
(number_of_iterations_cond): Do not build the folded tree.
* gcc.dg/torture/pr57343.c: New testcase.
Added:
trunk/gcc/testsuite/gcc.dg/torture/pr57343.c
Modified:
trunk/gcc/ChangeLog
trunk/gcc/testsuite/ChangeLog
trunk/gcc/tree-ssa-loop-niter.c
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug tree-optimization/57343] [4.8 Regression] wrong code on x86_64-linux at -Os and above
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
` (8 preceding siblings ...)
2013-05-27 13:03 ` [Bug tree-optimization/57343] [4.8 " rguenth at gcc dot gnu.org
@ 2013-08-29 13:09 ` jakub at gcc dot gnu.org
2013-08-29 13:17 ` jakub at gcc dot gnu.org
10 siblings, 0 replies; 11+ messages in thread
From: jakub at gcc dot gnu.org @ 2013-08-29 13:09 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Thu Aug 29 13:09:26 2013
New Revision: 202072
URL: http://gcc.gnu.org/viewcvs?rev=202072&root=gcc&view=rev
Log:
Backported from mainline
2013-05-27 Richard Biener <rguenther@suse.de>
PR tree-optimization/57343
* tree-ssa-loop-niter.c (number_of_iterations_ne_max): Do not
use multiple_of_p if not TYPE_OVERFLOW_UNDEFINED.
(number_of_iterations_cond): Do not build the folded tree.
* gcc.dg/torture/pr57343.c: New testcase.
Added:
branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/torture/pr57343.c
Modified:
branches/gcc-4_8-branch/gcc/ChangeLog
branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
branches/gcc-4_8-branch/gcc/tree-ssa-loop-niter.c
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug tree-optimization/57343] [4.8 Regression] wrong code on x86_64-linux at -Os and above
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
` (9 preceding siblings ...)
2013-08-29 13:09 ` jakub at gcc dot gnu.org
@ 2013-08-29 13:17 ` jakub at gcc dot gnu.org
10 siblings, 0 replies; 11+ messages in thread
From: jakub at gcc dot gnu.org @ 2013-08-29 13:17 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57343
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |RESOLVED
Resolution|--- |FIXED
--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2013-08-29 13:17 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <bug-57343-4@http.gcc.gnu.org/bugzilla/>
2013-05-20 22:55 ` [Bug tree-optimization/57343] wrong code on x86_64-linux at -Os and above glisse at gcc dot gnu.org
2013-05-21 6:23 ` [Bug tree-optimization/57343] [4.8/4.9 Regression] " jakub at gcc dot gnu.org
2013-05-21 9:54 ` rguenth at gcc dot gnu.org
2013-05-21 11:54 ` rguenth at gcc dot gnu.org
2013-05-21 12:19 ` rguenth at gcc dot gnu.org
2013-05-21 14:41 ` rakdver at gcc dot gnu.org
2013-05-27 7:55 ` rguenther at suse dot de
2013-05-27 9:01 ` rguenth at gcc dot gnu.org
2013-05-27 13:03 ` [Bug tree-optimization/57343] [4.8 " rguenth at gcc dot gnu.org
2013-08-29 13:09 ` jakub at gcc dot gnu.org
2013-08-29 13:17 ` jakub at gcc dot gnu.org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).