[X86][FastISel] Fix with.overflow eflags clobber (PR49587)

[nikic]

Summary

If the successor block has a phi node, then additional moves may be inserted into predecessors, which may clobber eflags. Don't try to fold the with.overflow result into the branch in that case.

This is done by explicitly checking for any phis in successor blocks, not sure if there's some more principled way to address this. Other fused compare and branch patterns avoid the issue by emitting the comparison when handling the branch, so that no instructions may be inserted in between. In this case, the with.overflow call is emitted separately (and I don't think this is avoidable, as it will generally have at least two users).

Fixes https://bugs.llvm.org/show_bug.cgi?id=49587.

[nagisa]

My feeling is that this fix is a work-around for what is a regression llvm11->12. Here's a comment I had sitting incomplete since yesterday in bugzilla:

Short summary of what I think is happening here:

FastISel::handlePHINodesInSuccessorBlocks is called from FastISel::selectInstruction before the branch is lowered. This generates a constant 0, clobbering the flags. Later, when lowering the branch itself, we have this code:

https://github.com/llvm/llvm-project/blob/fcdf7f6224610a51dc2ff47f2f1e3377329b64a7/llvm/lib/Target/X86/X86FastISel.cpp#L1758-L1769

which figures it is able to fold no problem.

In versions <=11 the handlePHINodesInSuccessorBlocks would insert the instruction for producing the constant 0 at the beginning of the MachineBB, now it only does so right before looking at the terminator.

Spent some time bisecting, the regression is somewhere in the range of a57def30f539..d79642b3db1d.

I'm hoping to finish the bisection today and look at the reasoning for the diff/commit that introduced the regression in the first place. If its not serious, it might make more sense to simply revert it.

[nikic]

@nagisa I'm pretty sure that this issue got exposed as a side-effect of D91734, but I don't think that change is to blame -- it just breaks some assumptions in existing code regarding where local values can be (re)materialized.

[nagisa]

Yeah that looks like the one.

Alright, in that case, then, there are a couple other alternative approaches that I think would likely address this class of problems in a more general way:

First, changing the emission of constant->register moves to always produce a mov, thus no longer clobbering the flags ever. This way adding arbitrary constant production all over the place wouldn't have potentially far reaching consequences.

Alternatively, mayhaps it is possible to check that we haven't inserted any machine instructions between the code generated for the intrinsic and the branch? That would make the "Make sure nothing is in the way" check significantly more direct, I feel.

(But also, feel free to ignore me, I'm not nowhere near familiar enough with FastISel to be able to say what it ought to look like)

[nikic]

In D98600#2625947, @nagisa wrote:

Yeah that looks like the one.

Alright, in that case, then, there are a couple other alternative approaches that I think would likely address this class of problems in a more general way:

First, changing the emission of constant->register moves to always produce a mov, thus no longer clobbering the flags ever. This way adding arbitrary constant production all over the place wouldn't have potentially far reaching consequences.

That would be a possibility, but does mean that we'd be using mov instead of xor for all zero constant materializations, which seems rather undesirable to me. At least if we don't want to add special-case logic just for phis.

Alternatively, mayhaps it is possible to check that we haven't inserted any machine instructions between the code generated for the intrinsic and the branch? That would make the "Make sure nothing is in the way" check significantly more direct, I feel.

This isn't possible because FastISel selects instructions in reverse order. This means that we first select the terminator (where we have to make the decision on whether to fold), then we select the phi movement, and then we select the overflow intrinsic.

[nikic]

Ping!

[RKSimon]

TBH this looks like a relatively safe workaround to me - I mentioned it to @probinson who was of the opinion that D91734 brought the issue to light as it tends to move constant materialization further down a basic block making these kind of clashes more likely.

[RKSimon]

Any more comments?

[nagisa]

None from me. As I said I'm not too qualified to have much say in fastisel, so my other comments are broadly ignorable. I do think that some fix for this needs to land (and be nominated for a backport into LLVM 12) sooner rather than later

[nikic]

For reference, here's how the alternative approach of not using xor for zero initialization would be look like (if you ignore some test update failures): https://gist.github.com/nikic/04876ffe96a5ee2ffb4be102cbbb8d60

[RKSimon]

LGTM

llvm/lib/Target/X86/X86FastISel.cpp

if (!isa<ExtractValueInst>(Itr))
       return false;
 
     // Check that the extractvalue operand comes from the intrinsic.
     const auto *EVI = cast<ExtractValueInst>(Itr);
     if (EVI->getAggregateOperand() != II)
       return false;
   }
 
+  // Make sure no potentially eflags clobbering phi moves can be inserted in
+  // between.
+  auto HasPhis = [](const BasicBlock *Succ) {
+    return !llvm::empty(Succ->phis());
+  };
+  if (I->isTerminator() && llvm::any_of(successors(I), HasPhis))
+    return false;
+
   CC = TmpCC;
   return true;
 }
 
 bool X86FastISel::isTypeLegal(Type *Ty, MVT &VT, bool AllowI1) {
   EVT evt = TLI.getValueType(DL, Ty, /*AllowUnknown=*/true);
   if (evt == MVT::Other || !evt.isSimple())
     // Unhandled type. Halt "fast" selection and bail.

llvm/test/CodeGen/X86/pr49587.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -O0 -fast-isel -mtriple=x86_64-- < %s | FileCheck %s
 
 define i32 @test(i64 %arg) nounwind {
 ; CHECK-LABEL: test:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    subq $1, %rdi
-; CHECK-NEXT:    setb %al
+; CHECK-NEXT:    setb %cl
 ; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    testb $1, %cl
 ; CHECK-NEXT:    movl %eax, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
-; CHECK-NEXT:    jb .LBB0_2
+; CHECK-NEXT:    jne .LBB0_2
 ; CHECK-NEXT:  # %bb.1: # %no_overflow
 ; CHECK-NEXT:    movl $1, %eax
 ; CHECK-NEXT:    movl %eax, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
 ; CHECK-NEXT:    jmp .LBB0_2
 ; CHECK-NEXT:  .LBB0_2: # %merge
 ; CHECK-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 ; CHECK-NEXT:    retq
 entry: