Dear GCC folks,
I think I found a code generation bug in GCC 4.0.1.
I'm sending this mail to make sure this bug is known and
is or will be removed in newer versions.
On a quick glance I couldn't find it in the bug database,
so it may not be known.
***
I am developing a simulation program that appears to show a
bug when compiled with gcc 4.0.1 (cross-compiler on Linux
for MINGW target) but compiles fine with GCC 3 or GCC 4.1.2
(native on Linux) as well as with gcc 3 mingw on Cygwin/Windows.
For the 4.0.1 cross-compiled program, the bug disappears
when the function is duplicated under another name, and
the duplicate is called instead in the critical place.
The original (buggy) function is not inlined, but the
duplicate is inlined because it's only called in one
place.
The function is an AVL tree deletion which operates
with pointers only.
I attach the C source code and the assembler code (output of
objdump -d) to this mail. I have marked the two places in C
where I think the bug appears with a comment containing "BUG".
I'm not good enough in assembler to verify the bug there.
What seems to happen is that the value of ta, which should be
set to the address of the parent node's left-child pointer in
this case, remains unchanged, i.e. remains pointing to 'dummy'.
Then, in the subsequent assignment *ta = r the pointer does
not get changed appropriately.
Before filing this as a bug, I'd like some person who can
read assembler to examine the situation.
I'll gladly assist with further information.
***
The code is compiled with this command:
i386-pc-mingw32-gcc -DHAVE_CONFIG_H -I. -I../../bugsklsim/src -I..
-std=gnu9x -W -Wall -Wpointer-arith -Wstrict-prototypes -Wmissing-prototypes
-Wbad-function-cast -Wcast-qual -Wcast-align -Wmissing-declarations
-Wnested-externs -Winline -Waggregate-return -Wshadow -g -O2 -MT sklsim.o -MD
-MP -MF ".deps/sklsim.Tpo" -c -o sklsim.o ../../bugsklsim/src/sklsim.c
Best regards,
Claus Fischer
--
Claus Fischer <[EMAIL PROTECTED]>
http://www.clausfischer.com/
typedef struct sklsim_event_s {
/* AVL tree */
int ev_bal; /* Tree balance: -1 left 0 middle 1 right */
struct sklsim_event_s *ev_l;/* Left subtree */
struct sklsim_event_s *ev_r;/* Right subtree */
struct sklsim_event_s *ev_p;/* Parent */
/* Those members not used in deletend function: */
double t; /* Time of next event */
sklsim_otype_t otype; /* Object type: OTYPE_PAX, OTYPE_AC, ... */
} sklsim_event_t;
/* AVL Tree: Delete node d from the tree. Node d must be in the tree.
* Return a pointer to the tree root, or to the top node of the tree.
* For root-less trees, return the new tree pointer.
*/
static sklsim_event_t * eventtree_deletend( sklsim_event_t * d)
{
sklsim_event_t * s; /* Node to be removed */
sklsim_event_t * su; /* Parent of s */
sklsim_event_t * sc; /* Child of s */
/* Nodes for the rebalancing loop */
sklsim_event_t * t;
sklsim_event_t * x;
/* The algorithm removes element d from the tree. If d has
two children, the algorithm first removes d's next left
neighbour, s, which is the rightmost node in d's left
subtree. At the very end, s is put in d's place in the
tree. */
/* (1) Find node s to remove instead of d */
/* ************************************** */
/* Find node s such that
* - if d has not two children, s is d
* - else s is the immediate left neighbour of d
* - s has one child node or none
*/
s = d;
if (s->ev_r != 0)
{
sklsim_event_t * ss;
ss = s->ev_l;
while (ss != 0)
{
s = ss;
ss = s->ev_r;
}
}
/* (2) Adjust the tree above s to reflect the future reduced height of s */
/* ********************************************************************* */
/* State:
* The height of the subtree rooted at s will be reduced in (3)
* when s will be removed. Before that happens, the balances
* of all nodes above s need to be adjusted.
* In the loop, the height of s is considered to be reduced already.
*/
/* The loop reduces height of subtree x under its parent t */
x = s;
t = s->ev_p;
while (t != 0)
{
sklsim_event_t * tu; /* parent of subtree t */
sklsim_event_t * *ta; /* address of pointer to subtree t */
sklsim_event_t * dummy;
/* Parent and address of t */
tu = t->ev_p;
if (tu != 0)
{
if (tu->ev_l == t)
ta = &tu->ev_l; /* BUG HAPPENS HERE, I THINK */
else
ta = &tu->ev_r;
}
else
{
ta = &dummy;
}
/* State:
* - The height of x has been reduced.
* - t is the parent of x.
* - t's subtree will be rearranged (including t)
* - tu is the parent of t or NIL
* - ta is the address of the parent's pointer to t
* After rearrangement:
* - the new subtree will be hooked under ta
* - if the subtree under ta has lost height:
* x is set to the new subtree under ta
* and the loop will continue
* - if the subtree under ta has kept its height:
* the loop is ended
*/
/* x is left subtree of t */
if (x == t->ev_l)
{
/* No rotation */
if (t->ev_bal == 0)
{
t->ev_bal = 1;
break;
}
/* No rotation */
else if (t->ev_bal == -1)
{
t->ev_bal = 0;
x = t;
}
else /* right balanced */
{
sklsim_event_t * r = t->ev_r;
sklsim_event_t * m = r->ev_l;
/* Single rotation */
if (r->ev_bal != -1)
{
/* r's balance can be right or middle */
*ta = r; /* BUG MANIFESTS HERE */
r->ev_p = tu;
t->ev_p = r;
if (m != 0) m->ev_p = t;
t->ev_r = m;
r->ev_l = t;
/* r's balance can be middle or right */
t->ev_bal =
(r->ev_bal == 0 ?
1 : 0);
r->ev_bal =
(r->ev_bal == 0 ?
-1 : 0);
if (r->ev_bal != 0)
break; /* r's height same as t's height before */
x = r;
}
/* Double rotation (*m guaranteed to exist) */
else
{
*ta = m;
m->ev_p = tu;
t->ev_p = m;
r->ev_p = m;
t->ev_r = m->ev_l;
if (m->ev_l != 0) m->ev_l->ev_p = t;
m->ev_l = t;
r->ev_l = m->ev_r;
if (m->ev_r != 0) m->ev_r->ev_p = r;
m->ev_r = r;
/* m's balance can be left, middle, or right */
t->ev_bal =
(m->ev_bal == 1 ?
-1 : 0);
r->ev_bal =
(m->ev_bal == -1 ?
1 : 0);
m->ev_bal = 0;
x = m;
}
}
}
/* x is right subtree of t */
else if (x == t->ev_r)
{
/* No rotation */
if (t->ev_bal == 0)
{
t->ev_bal = -1;
break;
}
/* No rotation */
else if (t->ev_bal == 1)
{
t->ev_bal = 0;
x = t;
}
else /* left balanced */
{
sklsim_event_t * l = t->ev_l;
sklsim_event_t * m = l->ev_r;
/* Single rotation */
if (l->ev_bal != 1)
{
/* l's balance can be left or middle */
*ta = l;
l->ev_p = tu;
t->ev_p = l;
if (m != 0)
m->ev_p = t;
t->ev_l = m;
l->ev_r = t;
/* l's balance can be middle or left */
t->ev_bal =
(l->ev_bal == 0 ?
-1 : 0);
l->ev_bal =
(l->ev_bal == 0 ?
1 : 0);
if (l->ev_bal != 0)
break; /* l's height same as t's height before */
x = l;
}
/* Double rotation (*m guaranteed to exist) */
else
{
*ta = m;
m->ev_p = tu;
t->ev_p = m;
l->ev_p = m;
t->ev_l = m->ev_r;
if (m->ev_r != 0)
m->ev_r->ev_p = t;
m->ev_r = t;
l->ev_r = m->ev_l;
if (m->ev_l != 0)
m->ev_l->ev_p = l;
m->ev_l = l;
/* m's balance can be left, middle, or right */
t->ev_bal =
(m->ev_bal == -1 ?
1 : 0);
l->ev_bal =
(m->ev_bal == 1 ?
-1 : 0);
m->ev_bal = 0;
x = m;
}
}
}
/* State:
* The subtree under ta/tu is rearranged as described above.
* Set t to the parent of x, and re-run the loop.
*/
t = tu;
}
/* State:
* The tree above s is rebalanced and readjusted
* for the decreased height of the subtree under s.
*
* In the current tree, the balance of the parent of s
* is temporarily inconsistent; it already reflects the
* new height of the subtree of s.
*/
/* (3) Remove s from the tree */
/* ************************** */
/* Remove s from the tree and put its child sc in its place */
/* Remember s has only one child, or none at all */
if (s->ev_l != 0)
sc = s->ev_l;
else
sc = s->ev_r;
su = s->ev_p;
if (su != 0)
{
if (su->ev_l == s)
su->ev_l = sc;
else
su->ev_r = sc;
}
if (sc != 0)
{
sc->ev_p = su;
}
/* State:
*
* The tree is correctly balanced now, and s is removed
* from the tree. The node su is the former parent of s.
*/
/* (4) Substitute s for d */
/* ********************** */
if (s != d)
{
sklsim_event_t * l;
sklsim_event_t * r;
/* Substitute s for d */
su = d->ev_p;
if (su != 0)
{
if (su->ev_l == d)
su->ev_l = s;
else
su->ev_r = s;
}
s->ev_p = su;
l = d->ev_l;
s->ev_l = l;
if (l != 0) l->ev_p = s;
r = d->ev_r;
s->ev_r = r;
if (r != 0) r->ev_p = s;
s->ev_bal = d->ev_bal;
}
else
s = sc;
/* State:
*
* - d is removed from the tree
* - su is the former parent of the deleted node d.
* - s is a node in the tree (child of su) or NIL.
* - the tree is properly balanced
* - the subtree up to s is fully correct
*/
/* (5) Clean the deleted node */
/* ************************** */
d->ev_p = 0;
d->ev_l = 0;
d->ev_r = 0;
d->ev_bal = 0;
/* (6) Find top of tree */
/* ******************** */
/* Make s the top node of the tree, or NIL */
while (su != 0)
{
s = su;
su = su->ev_p;
}
return su != 0 ? su : s;
}
sklsim_simulate.o: file format pe-i386
Disassembly of section .text:
000003ac <_eventtree_deletend>:
3ac: 55 push %ebp
3ad: 89 e5 mov %esp,%ebp
3af: 57 push %edi
3b0: 56 push %esi
3b1: 53 push %ebx
3b2: 52 push %edx
3b3: 89 45 f0 mov %eax,0xfffffff0(%ebp)
3b6: 8b 78 08 mov 0x8(%eax),%edi
3b9: 85 ff test %edi,%edi
3bb: 0f 84 9a 01 00 00 je 55b <_eventtree_deletend+0x1af>
3c1: 8b 40 04 mov 0x4(%eax),%eax
3c4: 85 c0 test %eax,%eax
3c6: 75 0a jne 3d2 <_eventtree_deletend+0x26>
3c8: e9 8e 01 00 00 jmp 55b <_eventtree_deletend+0x1af>
3cd: 8d 76 00 lea 0x0(%esi),%esi
3d0: 89 d0 mov %edx,%eax
3d2: 8b 50 08 mov 0x8(%eax),%edx
3d5: 85 d2 test %edx,%edx
3d7: 75 f7 jne 3d0 <_eventtree_deletend+0x24>
3d9: 89 c6 mov %eax,%esi
3db: 8b 4e 0c mov 0xc(%esi),%ecx
3de: 89 ca mov %ecx,%edx
3e0: 85 c9 test %ecx,%ecx
3e2: 74 77 je 45b <_eventtree_deletend+0xaf>
3e4: 89 f0 mov %esi,%eax
3e6: eb 0f jmp 3f7 <_eventtree_deletend+0x4b>
3e8: 3b 42 08 cmp 0x8(%edx),%eax
3eb: 0f 84 0f 01 00 00 je 500 <_eventtree_deletend+0x154>
3f1: 89 fa mov %edi,%edx
3f3: 85 ff test %edi,%edi
3f5: 74 61 je 458 <_eventtree_deletend+0xac>
3f7: 8b 7a 0c mov 0xc(%edx),%edi
3fa: 8b 4a 04 mov 0x4(%edx),%ecx
3fd: 39 c8 cmp %ecx,%eax
3ff: 75 e7 jne 3e8 <_eventtree_deletend+0x3c>
401: 8b 02 mov (%edx),%eax
403: 85 c0 test %eax,%eax
405: 0f 84 0d 02 00 00 je 618 <_eventtree_deletend+0x26c>
40b: 40 inc %eax
40c: 0f 84 3c 01 00 00 je 54e <_eventtree_deletend+0x1a2>
412: 8b 4a 08 mov 0x8(%edx),%ecx
415: 8b 59 04 mov 0x4(%ecx),%ebx
418: 8b 01 mov (%ecx),%eax
41a: 83 f8 ff cmp $0xffffffff,%eax
41d: 0f 84 40 01 00 00 je 563 <_eventtree_deletend+0x1b7>
423: 89 79 0c mov %edi,0xc(%ecx)
426: 89 4a 0c mov %ecx,0xc(%edx)
429: 85 db test %ebx,%ebx
42b: 74 03 je 430 <_eventtree_deletend+0x84>
42d: 89 53 0c mov %edx,0xc(%ebx)
430: 89 5a 08 mov %ebx,0x8(%edx)
433: 89 51 04 mov %edx,0x4(%ecx)
436: 85 c0 test %eax,%eax
438: 0f 94 c0 sete %al
43b: 0f b6 c0 movzbl %al,%eax
43e: 89 02 mov %eax,(%edx)
440: 8b 01 mov (%ecx),%eax
442: 83 f8 01 cmp $0x1,%eax
445: 19 c0 sbb %eax,%eax
447: 89 01 mov %eax,(%ecx)
449: 85 c0 test %eax,%eax
44b: 75 0b jne 458 <_eventtree_deletend+0xac>
44d: 89 c8 mov %ecx,%eax
44f: 89 fa mov %edi,%edx
451: 85 ff test %edi,%edi
453: 75 a2 jne 3f7 <_eventtree_deletend+0x4b>
455: 8d 76 00 lea 0x0(%esi),%esi
458: 8b 4e 0c mov 0xc(%esi),%ecx
45b: 8b 46 04 mov 0x4(%esi),%eax
45e: 85 c0 test %eax,%eax
460: 0f 84 9a 01 00 00 je 600 <_eventtree_deletend+0x254>
466: 89 ca mov %ecx,%edx
468: 85 c9 test %ecx,%ecx
46a: 74 0c je 478 <_eventtree_deletend+0xcc>
46c: 3b 71 04 cmp 0x4(%ecx),%esi
46f: 0f 84 93 01 00 00 je 608 <_eventtree_deletend+0x25c>
475: 89 41 08 mov %eax,0x8(%ecx)
478: 85 c0 test %eax,%eax
47a: 74 03 je 47f <_eventtree_deletend+0xd3>
47c: 89 48 0c mov %ecx,0xc(%eax)
47f: 3b 75 f0 cmp 0xfffffff0(%ebp),%esi
482: 0f 84 71 01 00 00 je 5f9 <_eventtree_deletend+0x24d>
488: 8b 4d f0 mov 0xfffffff0(%ebp),%ecx
48b: 8b 51 0c mov 0xc(%ecx),%edx
48e: 85 d2 test %edx,%edx
490: 74 0c je 49e <_eventtree_deletend+0xf2>
492: 3b 4a 04 cmp 0x4(%edx),%ecx
495: 0f 84 75 01 00 00 je 610 <_eventtree_deletend+0x264>
49b: 89 72 08 mov %esi,0x8(%edx)
49e: 89 56 0c mov %edx,0xc(%esi)
4a1: 8b 4d f0 mov 0xfffffff0(%ebp),%ecx
4a4: 8b 41 04 mov 0x4(%ecx),%eax
4a7: 89 46 04 mov %eax,0x4(%esi)
4aa: 85 c0 test %eax,%eax
4ac: 74 03 je 4b1 <_eventtree_deletend+0x105>
4ae: 89 70 0c mov %esi,0xc(%eax)
4b1: 8b 4d f0 mov 0xfffffff0(%ebp),%ecx
4b4: 8b 41 08 mov 0x8(%ecx),%eax
4b7: 89 46 08 mov %eax,0x8(%esi)
4ba: 85 c0 test %eax,%eax
4bc: 74 03 je 4c1 <_eventtree_deletend+0x115>
4be: 89 70 0c mov %esi,0xc(%eax)
4c1: 8b 4d f0 mov 0xfffffff0(%ebp),%ecx
4c4: 8b 01 mov (%ecx),%eax
4c6: 89 06 mov %eax,(%esi)
4c8: 8b 45 f0 mov 0xfffffff0(%ebp),%eax
4cb: c7 40 0c 00 00 00 00 movl $0x0,0xc(%eax)
4d2: c7 40 04 00 00 00 00 movl $0x0,0x4(%eax)
4d9: c7 40 08 00 00 00 00 movl $0x0,0x8(%eax)
4e0: c7 00 00 00 00 00 movl $0x0,(%eax)
4e6: 85 d2 test %edx,%edx
4e8: 75 04 jne 4ee <_eventtree_deletend+0x142>
4ea: eb 0b jmp 4f7 <_eventtree_deletend+0x14b>
4ec: 89 c2 mov %eax,%edx
4ee: 8b 42 0c mov 0xc(%edx),%eax
4f1: 85 c0 test %eax,%eax
4f3: 75 f7 jne 4ec <_eventtree_deletend+0x140>
4f5: 89 d6 mov %edx,%esi
4f7: 89 f0 mov %esi,%eax
4f9: 5e pop %esi
4fa: 5b pop %ebx
4fb: 5e pop %esi
4fc: 5f pop %edi
4fd: c9 leave
4fe: c3 ret
4ff: 90 nop
500: 8b 02 mov (%edx),%eax
502: 85 c0 test %eax,%eax
504: 0f 84 1c 01 00 00 je 626 <_eventtree_deletend+0x27a>
50a: 48 dec %eax
50b: 74 41 je 54e <_eventtree_deletend+0x1a2>
50d: 8b 59 08 mov 0x8(%ecx),%ebx
510: 8b 01 mov (%ecx),%eax
512: 83 f8 01 cmp $0x1,%eax
515: 0f 84 93 00 00 00 je 5ae <_eventtree_deletend+0x202>
51b: 89 79 0c mov %edi,0xc(%ecx)
51e: 89 4a 0c mov %ecx,0xc(%edx)
521: 85 db test %ebx,%ebx
523: 74 03 je 528 <_eventtree_deletend+0x17c>
525: 89 53 0c mov %edx,0xc(%ebx)
528: 89 5a 04 mov %ebx,0x4(%edx)
52b: 89 51 08 mov %edx,0x8(%ecx)
52e: 83 f8 01 cmp $0x1,%eax
531: 19 c0 sbb %eax,%eax
533: 89 02 mov %eax,(%edx)
535: 31 c0 xor %eax,%eax
537: 83 39 00 cmpl $0x0,(%ecx)
53a: 0f 94 c0 sete %al
53d: 89 01 mov %eax,(%ecx)
53f: 85 c0 test %eax,%eax
541: 0f 85 11 ff ff ff jne 458 <_eventtree_deletend+0xac>
547: 89 c8 mov %ecx,%eax
549: e9 01 ff ff ff jmp 44f <_eventtree_deletend+0xa3>
54e: c7 02 00 00 00 00 movl $0x0,(%edx)
554: 89 d0 mov %edx,%eax
556: e9 96 fe ff ff jmp 3f1 <_eventtree_deletend+0x45>
55b: 8b 75 f0 mov 0xfffffff0(%ebp),%esi
55e: e9 78 fe ff ff jmp 3db <_eventtree_deletend+0x2f>
563: 89 7b 0c mov %edi,0xc(%ebx)
566: 89 5a 0c mov %ebx,0xc(%edx)
569: 89 59 0c mov %ebx,0xc(%ecx)
56c: 8b 43 04 mov 0x4(%ebx),%eax
56f: 89 42 08 mov %eax,0x8(%edx)
572: 85 c0 test %eax,%eax
574: 74 03 je 579 <_eventtree_deletend+0x1cd>
576: 89 50 0c mov %edx,0xc(%eax)
579: 89 53 04 mov %edx,0x4(%ebx)
57c: 8b 43 08 mov 0x8(%ebx),%eax
57f: 89 41 04 mov %eax,0x4(%ecx)
582: 85 c0 test %eax,%eax
584: 74 03 je 589 <_eventtree_deletend+0x1dd>
586: 89 48 0c mov %ecx,0xc(%eax)
589: 89 4b 08 mov %ecx,0x8(%ebx)
58c: 31 c0 xor %eax,%eax
58e: 83 3b 01 cmpl $0x1,(%ebx)
591: 0f 95 c0 setne %al
594: 48 dec %eax
595: 89 02 mov %eax,(%edx)
597: 31 c0 xor %eax,%eax
599: 83 3b ff cmpl $0xffffffff,(%ebx)
59c: 0f 94 c0 sete %al
59f: 89 01 mov %eax,(%ecx)
5a1: c7 03 00 00 00 00 movl $0x0,(%ebx)
5a7: 89 d8 mov %ebx,%eax
5a9: e9 43 fe ff ff jmp 3f1 <_eventtree_deletend+0x45>
5ae: 89 7b 0c mov %edi,0xc(%ebx)
5b1: 89 5a 0c mov %ebx,0xc(%edx)
5b4: 89 59 0c mov %ebx,0xc(%ecx)
5b7: 8b 43 08 mov 0x8(%ebx),%eax
5ba: 89 42 04 mov %eax,0x4(%edx)
5bd: 85 c0 test %eax,%eax
5bf: 74 03 je 5c4 <_eventtree_deletend+0x218>
5c1: 89 50 0c mov %edx,0xc(%eax)
5c4: 89 53 08 mov %edx,0x8(%ebx)
5c7: 8b 43 04 mov 0x4(%ebx),%eax
5ca: 89 41 08 mov %eax,0x8(%ecx)
5cd: 85 c0 test %eax,%eax
5cf: 74 03 je 5d4 <_eventtree_deletend+0x228>
5d1: 89 48 0c mov %ecx,0xc(%eax)
5d4: 89 4b 04 mov %ecx,0x4(%ebx)
5d7: 31 c0 xor %eax,%eax
5d9: 83 3b ff cmpl $0xffffffff,(%ebx)
5dc: 0f 94 c0 sete %al
5df: 89 02 mov %eax,(%edx)
5e1: 31 c0 xor %eax,%eax
5e3: 83 3b 01 cmpl $0x1,(%ebx)
5e6: 0f 95 c0 setne %al
5e9: 48 dec %eax
5ea: 89 01 mov %eax,(%ecx)
5ec: c7 03 00 00 00 00 movl $0x0,(%ebx)
5f2: 89 d8 mov %ebx,%eax
5f4: e9 f8 fd ff ff jmp 3f1 <_eventtree_deletend+0x45>
5f9: 89 c6 mov %eax,%esi
5fb: e9 c8 fe ff ff jmp 4c8 <_eventtree_deletend+0x11c>
600: 8b 46 08 mov 0x8(%esi),%eax
603: e9 5e fe ff ff jmp 466 <_eventtree_deletend+0xba>
608: 89 41 04 mov %eax,0x4(%ecx)
60b: e9 68 fe ff ff jmp 478 <_eventtree_deletend+0xcc>
610: 89 72 04 mov %esi,0x4(%edx)
613: e9 86 fe ff ff jmp 49e <_eventtree_deletend+0xf2>
618: c7 02 01 00 00 00 movl $0x1,(%edx)
61e: 8b 4e 0c mov 0xc(%esi),%ecx
621: e9 35 fe ff ff jmp 45b <_eventtree_deletend+0xaf>
626: c7 02 ff ff ff ff movl $0xffffffff,(%edx)
62c: 8b 4e 0c mov 0xc(%esi),%ecx
62f: e9 27 fe ff ff jmp 45b <_eventtree_deletend+0xaf>
