Re: optimization/5344: gcc 3.0.3 optimizer generates incorrect code

Re: optimization/5344: gcc 3.0.3 optimizer generates incorrect code

[anguiano]

Synopsis: gcc 3.0.3 optimizer generates incorrect code

State-Changed-From-To: open->closed
State-Changed-By: anguiano
State-Changed-When: Tue Feb 12 19:09:48 2002
State-Changed-Why:
    Bogus bug report.  Problem exists only in author's source code.  The problem in the code is that the variable temp1 is unsigned.
    The author assumes temp1 can be negative.  Sections of code dealing
    with temp1 < 0 are optimized away because they are not possible.  If diff is
    used instead, the generated code is different, because diff is signed
    and therefore can be negative.

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=5344

Re: optimization/5344 gcc 3.0.3 optimizer generates incorrect code

[Ricardo Anguiano]

The following reply was made to PR optimization/5344; it has been noted by GNATS.

From: Ricardo Anguiano <anguiano@codesourcery.com>
To: gcc-gnats@gcc.gnu.org, gcc-prs@gcc.gnu.org, cosmos@visi.com,
   gcc-bugs@gcc.gnu.org, nobody@gcc.gnu.org
Cc:  
Subject: Re: optimization/5344 gcc 3.0.3 optimizer generates incorrect code
Date: 12 Feb 2002 11:12:39 -0800

 Greetings,
 
 This email is a response to GNATS submission #5344.  I do not have
 access to change the GNATS database.
 
 Running the C code by hand reveals the binary search algorithm
 implementation to be incorrect: It doesn't handle the following case
 well:
         array of size 1
 	containing fd=34
 	searching for fd=40
 
 The variable *p_i ends up the the value of 2.
 
 The main problem with this code is that the variable tmp1 is unsigned.
 The Writer assumes temp1 can be negative.  Sections of code dealing
 with temp1 < 0 are optimized away they are not possible.  If diff is
 used instead, the generated code is different, because diff is signed
 and therefore can be negative.
 
 This code reveals no bugs in the compiler.  Please don't make compiler
 maintainers debug your code.  Use a standard library function like
 bsearch.
 
 A paraphrase from \emph{Programming Pearls}, second edition, by Jon
 Bentley, column 4, "Writing Correct Programs", p. 34:
 
      "Most programmers think that ... writing [binary search] s easy.
      They're wrong....
 
      "Given ample time, only about ten percent of professional
      programmers were able to get this small program right.  But they
      aren't the only ones to find this task difficult: in the history
      of Section 6.2.1 of his \emph{Sorting and Searching}, Knuth
      points out that while the first binary search was published in
      1946, the first published binary search without bugs did not
      appear until 1962."
 
 Thanks,
 Ricardo Anguiano             anguiano@codesourcery.com
 CodeSourcery, LLC            http://www.codesourcery.com

optimization/5344: gcc 3.0.3 optimizer generates incorrect code

[cosmos]

>Number:         5344
>Category:       optimization
>Synopsis:       gcc 3.0.3 optimizer generates incorrect code
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          wrong-code
>Submitter-Id:   net
>Arrival-Date:   Wed Jan 09 22:46:00 PST 2002
>Closed-Date:
>Last-Modified:
>Originator:     Clay Harris
>Release:        3.0.3
>Organization:
>Environment:
System: Linux vorlon.zahadum.world 2.4.16 #2 SMP Wed Dec 12 02:10:51 CST 2001 i686 unknown
Architecture: i686

	
host: i686-pc-linux-gnu
build: i686-pc-linux-gnu
target: i686-pc-linux-gnu
configured with: ../configure 
>Description:
	Compiling the following program with 'gcc -O2 -S search_bug3.c'
	generates incorrect code.  Pay special attention to the 2nd
	if statement and the recalculation of i in the .s file.
>How-To-Repeat:

search_bug3.c:

/* #include <sys/poll.h> */
struct pollfd
  {
    int fd;
    short int events;
    short int revents;
  };

int search1 (
    unsigned int * __restrict__         i_p,
    int                                 fd,
    unsigned int                        num,
    struct pollfd * __restrict__        poll_p)
{
    int                                 diff;
    unsigned int                        i;
    unsigned int                        l;
    unsigned int                        u;
    unsigned int                        tmp1;

    /*
     * Find the fd (or the next highest fd to insert before)
     * in the poll_array using a binary search.
     */

    u = num;
    l = 0;
    i = num >> 1;

    while (l < u)
    {
        tmp1 = poll_p[i].fd - fd;

        if (tmp1 == 0)
            goto FOUND_IT;

        if (tmp1 > 0)
            u = i;
        else 
            l = i + 1;

        i = (l + u) >> 1;
    }

    if (tmp1 < 0)
        i++;

FOUND_IT: ;

    diff = tmp1;

    *i_p = i;
    return (diff);
}

search_bug3.s:

	.file	"search_bug3.c"
	.text
	.align 16
.globl search1
	.type	search1,@function
search1:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%edi
	movl	16(%ebp), %eax
	pushl	%esi
	movl	12(%ebp), %ecx
	pushl	%ebx
	xorl	%ebx, %ebx
	movl	%eax, %edx
	shrl	%edx
	cmpl	%eax, %ebx
	movl	20(%ebp), %edi
	jae	.L6
	.p2align 4
.L4:
	movl	(%edi,%edx,8), %eax
	movl	%eax, %esi
	subl	%ecx, %esi
	je	.L6
	movl	%edx, %eax
	shrl	%edx
	cmpl	%eax, %ebx
	jb	.L4
.L6:
	movl	8(%ebp), %eax
	movl	%edx, (%eax)
	movl	%esi, %eax
	popl	%ebx
	popl	%esi
	popl	%edi
	popl	%ebp
	ret
.Lfe1:
	.size	search1,.Lfe1-search1
	.ident	"GCC: (GNU) 3.0.3"

>Fix:
	No known fix.  The following are work-arounds:
	If optimization is turned off, it appears correct code is
	generated.
	If the variable tmp1 is removed from the program (replaced
	by variable diff), it appears that correct code is
	generated.
>Release-Note:
>Audit-Trail:
>Unformatted: