Likely code generation bug in GCC 4.0.1

[Claus Fischer <claus dot fischer at clausfischer dot com>]

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 <claus.fischer@clausfischer.com>
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;
}

Attachment: t.s
Description: Text document