Reduced test case, compile with llc -march=x86 -mcpu=i486 < t.ll:

define void @​gst_atomic_queue_push() {
entry:
br label %while.body

while.body:
%0 = load volatile i32* undef, align 4
fence seq_cst
%1 = load volatile i32* undef, align 4
%cmp = icmp sgt i32 %1, %0
br i1 %cmp, label %while.body, label %if.then

if.then:
ret void
}

fix for assertion failure
The attached patch changes the WorkList in InitDAGTopologicalSorting into a FIFO queue. Items that are added earlier to the list need to get a higher index than later items because they may be successors of the later items. This fixes the assertion failure, but does not fix the bug yet. The bug does not appear with -msse2. In that case the mfence instruction is used. So something seems to go wrong with the -mno-sse2 fence (lock orl $0,(%esp)).

proposed fix
This patch fixes the bug for me. It creates a new X86ISD::FENCE node and lowers ISD::ATOMIC_FENCE to it instead of to X86::OR32mrLocked. Then during instruction selection X86ISD::FENCE is replaced by X86::LOCK_OR32mi8.

The patch to fix the assertion failure turns not to be necessary but it's still a valid patch I think.

Proposed fix, updated for ToT
As-is, the proposed fix doesn't compile with top-of-trunk:

llvm[3]: Compiling X86ISelDAGToDAG.cpp for Release+Asserts build
lib/Target/X86/X86ISelDAGToDAG.cpp:1867:18: error: no matching member function for call to 'getMachineNode'
return CurDAG->getMachineNode(X86::LOCK_OR32mi8, dl, MVT::Other, Ops);
~~~~~~~~^~~~~~~~~~~~~~
include/llvm/CodeGen/SelectionDAG.h:824:18: note: candidate function not viable: no known conversion from 'llvm::DebugLoc' to 'llvm::SDLoc' for 2nd argument
MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
^

and so on for all the possible overloads. Apparently llvm:DebugLoc has been replaced with llvm::SDLoc after the 3.3 release.

I have updated the patch to compile with top-of-trunk. Now the only thing missing is a good testcase...

And I agree, your earlier patch replacing vector with queue should also go in, as a separate commit of course.

For some reason, this fix also changes the behavior of the codegen a little, since it makes test/CodeGen/X86/2012-01-16-mfence-nosse-flags.ll fail. This is because instead of the expected "cmpl $0, %eax", it now generates "testl %eax, %eax". I have no idea why yet. If it is correct, that other test must also be updated.

For some reason, this fix also changes the behavior of the codegen a little,
since it makes test/CodeGen/X86/2012-01-16-mfence-nosse-flags.ll fail. This
is because instead of the expected "cmpl $0, %eax", it now generates "testl
%eax, %eax". I have no idea why yet. If it is correct, that other test
must also be updated.

I'm not sufficiently familiar with llvm internals to know if this is a correct explanation but I suspect the reason is that the fence used to be "xorl r,r \ lock orl r,(%esp)" whereas now it is "lock orl $O,(%esp)" (in the old code there was getConstant(0) and now it's getTargetConstant(0)).

In the test case the comparison comes before the fence which means initially llvm expected to be able to reuse the zero for the fence in the comparison (cmpl r,%eax) and this isn't optimised into a testl. Later the comparison is rescheduled and llvm doesn't know r isn't clobbered so it becomes cmpl $0,%eax. With the patch the fence doesn't require a zero so initially there's cmpl $0,%eax which is optimised into a testl that is then rescheduled.

First I tried to keep the getConstant(0), as an operand to X86ISD::FENCE and then instruction selection would choose between LOCK_OR32mi8 and LOCK_OR32mr based on whether the zero was used only once or not. This basically worked but I couldn't figure out what to put in the .td file for X86ISD::FENCE with an operand and I couldn't get it to optimise {__sync_synchronize();return 0;} which had two "xorl %eax,%eax" (llvm doesn't seem to know the src operand in LOCK_OR isn't clobbered).

As for a test case, wouldn't Benjamin Kramer's test above be good enough?

Proposed fix, updated for ToT, with testcase
Updated the fix with a testcase specific for this PR, taken from comment 1.

I also had to update the testcase for bug 11768, which now generates more efficient code, e.g. before the fix it generated:

    movl    ptr, %eax
    xorl    %ecx, %ecx
    lock
    orl     %ecx, (%esp)
    cmpl    $0, %eax
    je      .LBB0_1

after the fix it generates:

    movl    ptr, %eax
    lock
    orl     $0, (%esp)
    testl   %eax, %eax
    je      .LBB0_1

I've done some digging on exactly why it's failing, so I'll record my discoveries in case I forget over the weekend. The issue is that SelectionDAG comes across:

A = Node(load volatile)
MachineNode(ORfence)
B Node(load volatile)
Node(sub A, B)

in chain order. When deciding whether it can merge the sub and the "A load", as is x86's wont, it tries to check if combining those chains would create a cycle.

Unfortunately it stops looking when it reaches a MachineNode, thinking that everything beyond that point must be selected and hence OK (SelectionDAG.cpp:1863). That is an incorrect assumption in this case and a loopy SUB32rm is emitted.

So the patch works by making sure there isn't a pre-selected MachineNode to find during this check. It would be nice to assume that MachineNodes only exist after selection, but if so, we've got quite a bit of refactoring in multiple backends to get there.

I'll see if I can work out what the performance implications of doing a more thorough search here are.

Fixed in r191165. Thanks Tim!

mentioned in issue llvm/llvm-bugzilla-archive#15981