llvm-gcc bootstrap is broken

[asl]

Bugzilla Link	2343
Resolution	FIXED
Resolved on	Nov 07, 2018 00:17
Version	trunk
OS	Linux
Attachments	Function is question
CC	@isanbard,@nlewycky

Extended Description

It seems, that recent taildup changes revealed some subtle bugs not known before. Consider attached .bc file. The C snippet in question is:

    tree cases = get_cases_for_edge (e, stmt);

    /* If we have a list of cases associated with E, then use it
       as it's a lot faster than walking the entire case vector.  */
    if (cases)
      {
        edge e2 = find_edge (e->src, dest);
        tree last, first;

        first = cases;
        while (cases)
          {
            last = cases;
            CASE_LABEL (cases) = label;
            cases = TREE_CHAIN (cases);
          }

        /* If there was already an edge in the CFG, then we need
           to move all the cases associated with E to E2.  */
         if (e2)
          {
            tree cases2 = get_cases_for_edge (e2, stmt);

            TREE_CHAIN (last) = TREE_CHAIN (cases2);
            TREE_CHAIN (cases2) = first;
          }
      }

From this we can see, that last is the 'if (e2)' is always non-NULL. The LLVM IR is also fine (only part showed):

bb392: ; preds = %bb379, %bb319
%last.0 = phi %struct.tree_node* [ undef, %bb319 ], [ %cases.0, %bb379 ] ; <%struct.tree_node*> [#use$
%cases.0 = phi %struct.tree_node* [ %tmp314, %bb319 ], [ %tmp391, %bb379 ] ; <%struct.tree_node*> [#use$
%tmp394 = icmp eq %struct.tree_node* %cases.0, null ; [#uses=1]
br i1 %tmp394, label %bb397, label %bb326

This is header of the loop and jump from %bb319 is possible iff %tmp314 is non-null, thus loop executes at least one time and %last.0 is properly initialized (thus - non null).

Let's look into generated assembler:
movl %ecx, %ebx
testl %ebx, %ebx
jne .LBB1_47 # bb326
.LBB1_52: # bb397
testl %eax, %eax
je .LBB1_80 # bb695
.LBB1_53: # bb402
movl %esi, 4(%esp)
movl %eax, (%esp)
call get_cases_for_edge
movl (%eax), %esi
movl %esi, (%ebx)

here %last.0 is %ebx and we saw that after call %ebx is always zero! I suppose, that codedegen 'merged' %last.0 and %cases.0 somehow (or some codegen passes)

[nlewycky]

I've finished my bisect. The patch at fault is r51138 in llvm-gcc:

---

r51138 | evancheng | 2008-05-15 00:41:59 -0700 (Thu, 15 May 2008) | 1 line

Remove tail duplication pass.

[asl]

I've finished my bisect. The patch at fault is r51138 in llvm-gcc:

---

r51138 | evancheng | 2008-05-15 00:41:59 -0700 (Thu, 15 May 2008) | 1 line

Remove tail duplication pass.

Yes, I'm pretty sure, that this revealed some subtle bug, which was hidden by taildup...

[isanbard]

First iteration of SROA that has the failure

[isanbard]

The bug is in the code generator and is exposed by the scalar replacement of aggregates pass. If you initialize the "last" variable to 0, the bug goes away. Also note that if you run "llc" with "-regalloc=local", the bug goes away.

I'm attaching a couple of .bc files. I modified SROA to iterate only a certain number of times. The "broken.bc" file is the first iteration that still has the failure. The "okay.bc" file is the last iteration that still has the failure.

[isanbard]

The last iteration of SROA that doesn't have the bug.

[llvmbot]

Thanks - however, the last two attachments are identical?

[isanbard]

The last iteration of SROA that doesn't have the bug.

[llvmbot]

The fact it works with -regalloc=local doesn't mean it's a register allocation bug. It's very possible the optimizer has introduced not well defined behavior and we just happen to get lucky with -regalloc=local.

[llvmbot]

Looking at broken.bc
bb497: ; preds = %bb483, %bb411
...
%last.0 = phi %struct.tree_node* [ undef, %bb411 ], [ %cases.0, %bb483 ] ; <%struct.tree_node*> [#uses=1]

The phi node looks curious. I don't see how last can ever be undef.

[asl]

Looking at broken.bc
bb497: ; preds = %bb483, %bb411
...
%last.0 = phi %struct.tree_node* [ undef, %bb411 ], [ %cases.0, %bb483
] ; <%struct.tree_node*> [#uses=1]

The phi node looks curious. I don't see how last can ever be undef.
It's undef per initialization. But loop is executed at least 1 time, so it should be always initialized to %cases.0 before get_cases_for_edge() is run

[llvmbot]

Ok, I stand corrected. This does look like a codegen issue. llc -f -mtriple=i386-linux broken.bc

.LBB1_41: # bb497
movl %ebx, %ebp
testl %ebp, %ebp
jne .LBB1_33 # bb418
.LBB1_42: # bb502
testl %eax, %eax
je .LBB1_71 # bb841
.LBB1_43: # bb507
movl %esi, 4(%esp)
movl %eax, (%esp)
call get_cases_for_edge
movl %eax, 184(%esp)
movl (%eax), %esi
movl %esi, (%ebp)

Yep, it's storing into address in %ebp which is guaranteed zero.

[llvmbot]

Looks like a pre-Evan coalescer bug. Fixed here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20080519/062735.html

Now the code snippet looks like this:
movl %edx, %edi
movl %ecx, %edx
testl %edx, %edx
jne .LBB1_47 # bb326
.LBB1_52: # bb397
testl %eax, %eax
je .LBB1_80 # bb695
.LBB1_53: # bb402
movl %esi, 4(%esp)
movl %eax, (%esp)
call get_cases_for_edge
movl (%eax), %esi
movl %esi, (%edi)

This correctly saves the previous iteration of "case" into "last" (%edi) and used it as store address. Please verify this fixes Linux i386 llvm-gcc bootstrapping.

[nlewycky]

Excellent. Thanks Evan!