[Bug c/66348] New: Simple loop with 64-bit index has only lower half initialized correctly

[Bug c/66348] New: Simple loop with 64-bit index has only lower half initialized correctly

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

            Bug ID: 66348
           Summary: Simple loop with 64-bit index has only lower half
                    initialized correctly
           Product: gcc
           Version: 4.9.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: sebastiano.vigna at unimi dot it
  Target Milestone: ---

Created attachment 35657
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35657&action=edit
Source (buffer.c) and a bunch of header files

This is a fragment of ne, the nice editor:

line_desc *nth_line_desc(const buffer *b, const int64_t n) {
   if (n < 0 || n >= b->num_lines) return NULL;

   line_desc *ld;
   const int64_t best_absolute_cost = min(n, b->num_lines - 1 - n);
   const int64_t relative_cost = b->cur_line < n ? n - b->cur_line :
b->cur_line - n;

   if (best_absolute_cost < relative_cost) {
      if (n < b->num_lines / 2) {
         ld = (line_desc *)b->line_desc_list.head;
         for(int64_t i = 0; i < n; i++) ld = (line_desc *)ld->ld_node.next;
      }
      else {
         ld = (line_desc *)b->line_desc_list.tail_pred;
         // Problematic loop
         for(int64_t i = 0; i < b->num_lines - 1 - n; i++) ld = (line_desc
*)ld->ld_node.prev;;
      }
   }
   else {
      ld = (line_desc *)b->cur_line_desc;
      if (n < b->cur_line) for(int64_t i = 0; i < b->cur_line - n; i++) ld =
(line_desc *)ld->ld_node.prev;
      else for(int64_t i = 0; i < n - b->cur_line; i++) ld = (line_desc
*)ld->ld_node.next;
   }

   return ld;
}

The loop commented as "problematic loop" is compiled (with -O3) as

        xorl    %eax, %eax      # i
        .p2align 4,,10
        .p2align 3
.L527:
        addq    $1, %rax        #, i
        movq    8(%rbx), %rbx   # ld_64->ld_node.prev, ld
        cmpq    %rdx, %rax      # D.11490, i
        jne     .L527   #,


That is, the loop index i is in %rax, but only the lower half is zeroed at the
start of the loop. When we enter the loop with a large (>32-bit) value, the
loop never ends. This happens already with -O1. We had to #pragma the function
to -O0 to make it work.

I have attached a bunch of header files and the source of the file containing
the function. Compile with 

gcc -std=c99 -D_GNU_SOURCE -D__USE_GNU -DSTDC_HEADERS -Dinline=__inline__ -O3
-DNDEBUG -c -S -fverbose-asm buffer.c

to get the code above.

[Bug c/66348] Simple loop has only lower half of the 64-bit counter initialized correctly

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I suspect there is an alias violation here rather what is described. 


In x86_64, almost all of the instructions which act on 32bit half of the
registers will zero extend. That includes xorl.

[Bug c/66348] Simple loop has only lower half of the 64-bit counter initialized correctly

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

--- Comment #2 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
Er... it's perfectly possible. My knowledge of x64 assembly is rudimentary, but
I wanted to try a diagnosis.

What is definitely true is that at -O0 we enter and exit the loop as it should
happen, and at -O1 we never exit the loop. For the time being we are
#pragma'ing the function to remove optimizations.

[Bug c/66348] Simple loop has only lower half of the 64-bit counter initialized correctly

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

--- Comment #3 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
As an additional information: we printed b->num_lines - 1 - n just before the
loop, and everything is fine--we get there with the current value both with -O0
and -O1. But we -O1 we never exit the loop.

[Bug c/66348] Simple loop has only lower half of the 64-bit counter initialized correctly

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
You can try -fsanitize=undefined and see if it fires.

[Bug c/66348] Simple loop has only lower half of the 64-bit counter initialized correctly

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

--- Comment #5 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
Fantastic tool! I didn't know about it.

But it doesn't fire. There is no undefined behaviour in that code--it's just
that the optimizer at -O1 does something wrong.

I tried a binary search over the single options induced by -O1, but it turns
out it's a combination of things--when I split the options in two half, the
problem did not show up with either half.

The code is 30-40 lines of assembly--I guess someone proficient with the output
of the compiler could easily spot what's going wrong.

[Bug c/66348] Simple loop has only lower half of the 64-bit counter initialized correctly

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

--- Comment #6 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
I forgot an important aspect: with -fsanitize=undefined the optimization bug
does not show up. The instrumentation perturbs the code enough to make it go
away.

[Bug c/66348] Simple loop has only lower half of the 64-bit counter initialized correctly

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

--- Comment #7 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
I tried also with -fsanitize=address. No problems reported. Bug not showing up.
A classical heisenbug.

[Bug c/66348] Simple loop has only lower half of the 64-bit counter initialized correctly

[ubizjak at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

--- Comment #8 from Uroš Bizjak <ubizjak at gmail dot com> ---
(In reply to Sebastiano Vigna from comment #0)

> The loop commented as "problematic loop" is compiled (with -O3) as
> 
>         xorl    %eax, %eax      # i
>
> That is, the loop index i is in %rax, but only the lower half is zeroed at
> the start of the loop. When we enter the loop with a large (>32-bit) value,
> the loop never ends. This happens already with -O1. We had to #pragma the
> function to -O0 to make it work.

If you are referring to the xorl insn above, then rest assured that it zeroes
the whole 64bit register.  Your bug is elsewhere.
>From gcc-bugs-return-488170-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Fri Jun 05 15:52:32 2015
Return-Path: <gcc-bugs-return-488170-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 71164 invoked by alias); 5 Jun 2015 15:52:32 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 71113 invoked by uid 48); 5 Jun 2015 15:52:28 -0000
From: "redi at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/63860] Ill-formed std::pair::swap implementation?
Date: Fri, 05 Jun 2015 15:52:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: redi at gcc dot gnu.org
X-Bugzilla-Status: RESOLVED
X-Bugzilla-Resolution: FIXED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 6.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status resolution target_milestone
Message-ID: <bug-63860-4-XQ4xnge8q1@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-63860-4@http.gcc.gnu.org/bugzilla/>
References: <bug-63860-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-06/txt/msg00502.txt.bz2
Content-length: 647

https://gcc.gnu.org/bugzilla/show_bug.cgi?idc860

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|5.2                         |6.0

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Should be fixed on trunk by r224153

I don't see any point fixing it for 5.2 since G++ and Clang already accept the
ill-formed code, and aren't going to suddenly stop doing so.

[Bug c/66348] Simple loop never exit with -O1, exits with -O0

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

--- Comment #9 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
As I said, I was trying (a bit naively, admittedly) a diagnosis. I agree
fully--I'm no expert in x86 assembly. But it is a fact that the problematic
loop never exits with -O1, and exits normally with -O0. The loop does not write
any memory except for the local variable ld, so if the list of pointers was
broken we should get a segment violation. Instead, it simply never exits
(keeping 100% CPU load).

[Bug c/66348] Simple loop never exits with -O1, exits with -O0

[miyuki at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

Mikhail Maltsev <miyuki at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |miyuki at gcc dot gnu.org

--- Comment #10 from Mikhail Maltsev <miyuki at gcc dot gnu.org> ---
You should probably provide a reproducer:
1. Modify your program in such way that it does not require any user's action
and/or command line switches to exhibit the problem (i.e. it should either hang
or exit normally with code 0, depending on compiler flags used)
2. If your program requires some libraries (ncurses, or something like that),
try to comment-out library calls or write some simple stubs insead of them.
3. It should not require any external files. If it does, try to hardcode all
data into the program (e.g., if your text editor requires a file to be opened,
use a static char array, which will contain that file).
4. It sould compile without any external headers. To achive this, just run each
of your sources through preprocessor, like this:
gcc -std=c99 -D_GNU_SOURCE -D__USE_GNU -DSTDC_HEADERS -Dinline=__inline__ -O1
-DNDEBUG -E buffer.c > buffer.i
5. Just in case, ensure that the bug still persists: compile the preprocessed
sources and check that behavior did not change.
6. Compress all preprocessed sources and attach the archive.

[Bug c/66348] Simple loop never exits with -O1, exits with -O0

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

--- Comment #11 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
Dear Mikhail,
I have several ongoing open-source projects and, believe me, I make exactly the
same recommendation to people reporting bugs. They are perfectly sensible and
certainly the way to go in 99% of the cases.

The problem is that we face what is called a "heisenbug". Any tentative to
observe it or reproduce it fails. Add ubsan: no bug. Add a print in the loop:
no bug. Isolate the behaviour by having a main() calling the faulty function
with the same parameters: no bug.

Reproducing requires running ne (the nice editor) on a machine with at least
256GB of RAM, opening a 30GB file and running a specified macro. I don't think
this is doable. But if anybody is interested in reproducing the bug, I can
provide an account, given ssh credentials, and a directory with all necessary
instructions. Running ne using the given macro reproduces exactly the bug. But
all my tentatives to reduce the size of the source failed miserably.

Heisenbugs are very often (but not always) compiler bugs. In our case, I
finally settled for

         // Problematic loop
         for(int64_t i = 0; i < b->num_lines - 1 - n; i++) {
            if ( i == -1 ) fputc('.', stderr); // ***
            ld = (line_desc *)ld->ld_node.prev;
         }

I just added the line marked ***. It does nothing--i is never -1. Nothing is
ever printed. But now the code runs correctly when using -O3.

Does this prove that I'm facing a compiler bug? I don't know for certain, but
I'm pretty sure it does, and considering the very short function in which the
bug appears it would be probably easy to check whether this is true or not.

[Bug c/66348] Simple loop never exits with -O1, exits with -O0

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

--- Comment #12 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
BTW, to further restrict the search I'm trying to replicate the bug with
-fsanitize=address, or at least to get to the problematic call under
-fsanitize=address, but it'll take a while. I have to recompile the gcc suite,
as the current version of libasan does not allocate more than 64GB (in Fedora,
libasan is built with gcc).

[Bug middle-end/66348] Simple loop never exits with -O1, exits with -O0

[sebastiano.vigna at unimi dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66348

Sebastiano Vigna <sebastiano.vigna at unimi dot it> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #14 from Sebastiano Vigna <sebastiano.vigna at unimi dot it> ---
In retrospect, and knowing what I know now, I don't understand why nobody just
suggested to compile with -fno-strict-aliasing. The cause of the problem are
ithe gcc super-strict aliasing rules. Compiling with -f-no-strict-aliasing
solved the problem.