[x86] Fix PR37100 by teaching the EFLAGS copy lowering to rewrite uses across basic blocks in the limited cases where it is very straight forward to do so.

[chandlerc]

Summary

This will also be useful for other places where we do some limited
EFLAGS propagation across CFG edges and need to handle copy rewrites
afterward. I think this is rapidly approaching the maximum we can and
should be doing here. Everything else begins to require either heroic
analysis to prove how to do PHI insertion manually, or somehow managing
arbitrary PHI-ing of EFLAGS with general PHI insertion. Neither of these
seem at all promising so if those cases come up, we'll almost certainly
need to rewrite the parts of LLVM that produce those patterns.

We do now require dominator trees in order to reliably diagnose patterns
that would require PHI nodes. This is a bit unfortunate but it seems
better than the completely mysterious crash we would get otherwise.

[rnk]

llvm/test/CodeGen/X86/copy-eflags.ll

293

This infinite loop with selects of undef feels over-reduced. It seems fragile, since a pass could come along and optimize the select to the non-undef operand.

I liked the test case from PR37133, but it's reliance on debug info (any, not just standalone) scares me:

int a, b;
unsigned long long c;
void e() {
  long long d;
  b = 33;
  d = a;
  if (c < a) {
    b = 32;
    d = c;
  }
  if (d)
    b = 2;
}

We should reopen it or file a split separate bug, because we generate two more BBs on that code when debug info is enabled. :(

In any case, is there a better way to write this test case using legalized arithmetic? An i128 x64 test case with live-out eflags might also be interesting.

[chandlerc]

llvm/test/CodeGen/X86/copy-eflags.ll

293

I actually tried some to remove the undef stuff. I couldn't find a pattern that triggered the bug. =[ I guess I can keep trying...

[chandlerc]

Arrange this test case to be slightly less brittle.

[chandlerc]

llvm/test/CodeGen/X86/copy-eflags.ll

293

Got the undefs out. How much more should I do here?

[rnk]

lgtm

llvm/test/CodeGen/X86/copy-eflags.ll

293

I guess the live-out eflags are getting created by a combination of SBB and select-to-jump x86 lowering logic. I guess this is as reduced as we can get.

[mzolotukhin]

llvm/trunk/lib/Target/X86/X86FlagsCopyLowering.cpp

445–457 ↗

(On Diff #142943)

Could all of this be under DEBUG? The fatal error we're reporting here looks like an internal compiler assert anyway.
If we put in entirely under DEBUG, we can avoid building dominators in Release compilers.

[chandlerc]

llvm/trunk/lib/Target/X86/X86FlagsCopyLowering.cpp

445–457 ↗

(On Diff #142943)

The reason we've kept a number of these as fatal errors is due to our concern about latent problems in LLVM. We're essentially introducing a pretty novel set of constraints on what kinds of EFLAGS copies can be lowered, and trying to get somewhat more reliable failure modes if this bites us...

And at least one of these already helped uncover a bug (that this patch is fixing)...

Is the domtree analysis cost showing up significantly in compile times for you? Are there other concerns?

[mzolotukhin]

llvm/trunk/lib/Target/X86/X86FlagsCopyLowering.cpp

445–457 ↗

(On Diff #142943)

I see a value of having it on at least for some time, but I think in the long run we should turn it into an assert. Would it be possible?

I just noticed a new pass in the pipeline and wanted to check if it can be avoided. On O0 dom-tree analysis costs ~0.25% geomean (on CTMark), so each separate invocation doesn't seem to cost much, but they add up eventually.

By the way, why didn't we catch the bug you are talking about with RA compiler bots? Maybe that's an argument for adding more RA bots?

[chandlerc]

llvm/trunk/lib/Target/X86/X86FlagsCopyLowering.cpp

445–457 ↗

(On Diff #142943)

Sorry, I misunderstood. Long term, we can almost certainly move all of this to an assert-only kind of check. We just are benefiting (for now) from more aggressive checking.

But you ask a great question: why don't the release+asserts deployments catch these?

The frustrating thing is that some of the patterns here are *really* rare, or really tricky to reproduce. One of the test cases we got only reproduces when you build the input with debug info enabled! We still don't know why. The other test case only reproduces on 32-bit x86, where we (sadly) have much less testing.

It's also somewhat rare for benchmarks to hit this because the old lowering was *really* slow. If it were happening frequently in benchmarks, it might have been fixed sooner or the benchmarks would have been changed to not do that.... =/

llvm/lib/Target/X86/X86FlagsCopyLowering.cpp

 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
+#include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/MachineSSAUpdater.h"
public:
   /// Pass identification, replacement for typeid.
   static char ID;
 
 private:
   MachineRegisterInfo *MRI;
   const X86InstrInfo *TII;
   const TargetRegisterInfo *TRI;
   const TargetRegisterClass *PromoteRC;
+  MachineDominatorTree *MDT;
 
   CondRegArray collectCondsInRegs(MachineBasicBlock &MBB,
                                   MachineInstr &CopyDefI);
 
   unsigned promoteCondToReg(MachineBasicBlock &MBB,
                             MachineBasicBlock::iterator TestPos,
                             DebugLoc TestLoc, X86::CondCode Cond);
   std::pair<unsigned, bool>

 
 FunctionPass *llvm::createX86FlagsCopyLoweringPass() {
   return new X86FlagsCopyLoweringPass();
 }
 
 char X86FlagsCopyLoweringPass::ID = 0;
 
 void X86FlagsCopyLoweringPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<MachineDominatorTree>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 namespace {
 /// An enumeration of the arithmetic instruction mnemonics which have
 /// interesting flag semantics.
 ///
 /// We can map instruction opcodes into these mnemonics to make it easy to

 bool X86FlagsCopyLoweringPass::runOnMachineFunction(MachineFunction &MF) {
   DEBUG(dbgs() << "********** " << getPassName() << " : " << MF.getName()
                << " **********\n");
 
   auto &Subtarget = MF.getSubtarget<X86Subtarget>();
   MRI = &MF.getRegInfo();
   TII = Subtarget.getInstrInfo();
   TRI = Subtarget.getRegisterInfo();
+  MDT = &getAnalysis<MachineDominatorTree>();
   PromoteRC = &X86::GR8RegClass;
 
   if (MF.begin() == MF.end())
     // Nothing to do for a degenerate empty function...
     return false;
 
   SmallVector<MachineInstr *, 4> Copies;
   for (MachineBasicBlock &MBB : MF)
for (MachineInstr *CopyI : Copies) {
 
     // Gather the condition flags that have already been preserved in
     // registers. We do this from scratch each time as we expect there to be
     // very few of them and we expect to not revisit the same copy definition
     // many times. If either of those change sufficiently we could build a map
     // of these up front instead.
     CondRegArray CondRegs = collectCondsInRegs(TestMBB, CopyDefI);
 
-    for (auto MII = std::next(CopyI->getIterator()), MIE = MBB.instr_end();
+    // Collect the basic blocks we need to scan. Typically this will just be
+    // a single basic block but we may have to scan multiple blocks if the
+    // EFLAGS copy lives into successors.
+    SmallVector<MachineBasicBlock *, 2> Blocks;
+    SmallPtrSet<MachineBasicBlock *, 2> VisitedBlocks;
+    Blocks.push_back(&MBB);
+    VisitedBlocks.insert(&MBB);
+
+    do {
+      MachineBasicBlock &UseMBB = *Blocks.pop_back_val();
+
+      // We currently don't do any PHI insertion and so we require that the
+      // test basic block dominates all of the use basic blocks.
+      //
+      // We could in theory do PHI insertion here if it becomes useful by just
+      // taking undef values in along every edge that we don't trace this
+      // EFLAGS copy along. This isn't as bad as fully general PHI insertion,
+      // but still seems like a great deal of complexity.
+      //
+      // Because it is theoretically possible that some earlier MI pass or
+      // other lowering transformation could induce this to happen, we do
+      // a hard check even in non-debug builds here.
+      if (&TestMBB != &UseMBB && !MDT->dominates(&TestMBB, &UseMBB)) {
+        DEBUG({
+          dbgs() << "ERROR: Encountered use that is not dominated by our test "
+                    "basic block! Rewriting this would require inserting PHI "
+                    "nodes to track the flag state across the CFG.\n\nTest "
+                    "block:\n";
+          TestMBB.dump();
+          dbgs() << "Use block:\n";
+          UseMBB.dump();
+        });
+        report_fatal_error("Cannot lower EFLAGS copy when original copy def "
+                           "does not dominate all uses.");
+      }
+
+      for (auto MII = &UseMBB == &MBB ? std::next(CopyI->getIterator())
+                                      : UseMBB.instr_begin(),
+                MIE = UseMBB.instr_end();
            MII != MIE;) {
         MachineInstr &MI = *MII++;
         MachineOperand *FlagUse = MI.findRegisterUseOperand(X86::EFLAGS);
         if (!FlagUse) {
           if (MI.findRegisterDefOperand(X86::EFLAGS)) {
             // If EFLAGS are defined, it's as-if they were killed. We can stop
             // scanning here.
             //
             // NB!!! Many instructions only modify some flags. LLVM currently
-          // models this as clobbering all flags, but if that ever changes this
-          // will need to be carefully updated to handle that more complex
-          // logic.
+            // models this as clobbering all flags, but if that ever changes
+            // this will need to be carefully updated to handle that more
+            // complex logic.
             FlagsKilled = true;
             break;
           }
           continue;
         }
 
         DEBUG(dbgs() << "  Rewriting use: "; MI.dump());
 
         // Check the kill flag before we rewrite as that may change it.
         if (FlagUse->isKill())
           FlagsKilled = true;
 
         // Once we encounter a branch, the rest of the instructions must also be
         // branches. We can't rewrite in place here, so we handle them below.
         //
         // Note that we don't have to handle tail calls here, even conditional
         // tail calls, as those are not introduced into the X86 MI until post-RA
         // branch folding or black placement. As a consequence, we get to deal
         // with the simpler formulation of conditional branches followed by tail
         // calls.
         if (X86::getCondFromBranchOpc(MI.getOpcode()) != X86::COND_INVALID) {
           auto JmpIt = MI.getIterator();
           do {
             JmpIs.push_back(&*JmpIt);
             ++JmpIt;
-        } while (JmpIt != MBB.instr_end() &&
+          } while (JmpIt != UseMBB.instr_end() &&
                    X86::getCondFromBranchOpc(JmpIt->getOpcode()) !=
                        X86::COND_INVALID);
           break;
         }
 
         // Otherwise we can just rewrite in-place.
         if (X86::getCondFromCMovOpc(MI.getOpcode()) != X86::COND_INVALID) {
           rewriteCMov(TestMBB, TestPos, TestLoc, MI, *FlagUse, CondRegs);
-      } else if (X86::getCondFromSETOpc(MI.getOpcode()) != X86::COND_INVALID) {
+        } else if (X86::getCondFromSETOpc(MI.getOpcode()) !=
+                   X86::COND_INVALID) {
           rewriteSetCC(TestMBB, TestPos, TestLoc, MI, *FlagUse, CondRegs);
         } else if (MI.getOpcode() == TargetOpcode::COPY) {
           rewriteCopy(MI, *FlagUse, CopyDefI);
         } else {
-        // We assume that arithmetic instructions that use flags also def them.
+          // We assume that arithmetic instructions that use flags also def
+          // them.
           assert(MI.findRegisterDefOperand(X86::EFLAGS) &&
                  "Expected a def of EFLAGS for this instruction!");
 
           // NB!!! Several arithmetic instructions only *partially* update
           // flags. Theoretically, we could generate MI code sequences that
           // would rely on this fact and observe different flags independently.
           // But currently LLVM models all of these instructions as clobbering
           // all the flags in an undef way. We rely on that to simplify the
           // logic.
           FlagsKilled = true;
 
           rewriteArithmetic(TestMBB, TestPos, TestLoc, MI, *FlagUse, CondRegs);
           break;
         }
 
         // If this was the last use of the flags, we're done.
         if (FlagsKilled)
           break;
       }
 
-    // If we didn't find a kill (or equivalent) check that the flags don't
-    // live-out of the basic block. Currently we don't support lowering copies
-    // of flags that live out in this fashion.
-    if (!FlagsKilled &&
-        llvm::any_of(MBB.successors(), [](MachineBasicBlock *SuccMBB) {
-          return SuccMBB->isLiveIn(X86::EFLAGS);
-        })) {
-      DEBUG({
-        dbgs() << "ERROR: Found a copied EFLAGS live-out from basic block:\n"
-               << "----\n";
-        MBB.dump();
-        dbgs() << "----\n"
-               << "ERROR: Cannot lower this EFLAGS copy!\n";
-      });
-      report_fatal_error(
-          "Cannot lower EFLAGS copy that lives out of a basic block!");
-    }
+      // If the flags were killed, we're done with this block.
+      if (FlagsKilled)
+        break;
+
+      // Otherwise we need to scan successors for ones where the flags live-in
+      // and queue those up for processing.
+      for (MachineBasicBlock *SuccMBB : UseMBB.successors())
+        if (SuccMBB->isLiveIn(X86::EFLAGS) &&
+            VisitedBlocks.insert(SuccMBB).second)
+          Blocks.push_back(SuccMBB);
+    } while (!Blocks.empty());
 
     // Now rewrite the jumps that use the flags. These we handle specially
-    // because if there are multiple jumps we'll have to do surgery on the CFG.
+    // because if there are multiple jumps in a single basic block we'll have
+    // to do surgery on the CFG.
+    MachineBasicBlock *LastJmpMBB = nullptr;
     for (MachineInstr *JmpI : JmpIs) {
-      // Past the first jump we need to split the blocks apart.
-      if (JmpI != JmpIs.front())
+      // Past the first jump within a basic block we need to split the blocks
+      // apart.
+      if (JmpI->getParent() == LastJmpMBB)
         splitBlock(*JmpI->getParent(), *JmpI, *TII);
+      else
+        LastJmpMBB = JmpI->getParent();
 
       rewriteCondJmp(TestMBB, TestPos, TestLoc, *JmpI, CondRegs);
     }
 
     // FIXME: Mark the last use of EFLAGS before the copy's def as a kill if
     // the copy's def operand is itself a kill.
   }
 

llvm/test/CodeGen/X86/O0-pipeline.ll

 ; CHECK-NEXT:       Exception handling preparation
 ; CHECK-NEXT:       Safe Stack instrumentation pass
 ; CHECK-NEXT:       Insert stack protectors
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:       X86 DAG->DAG Instruction Selection
 ; CHECK-NEXT:       X86 PIC Global Base Reg Initialization
 ; CHECK-NEXT:       Expand ISel Pseudo-instructions
 ; CHECK-NEXT:       Local Stack Slot Allocation
+; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       X86 EFLAGS copy lowering
 ; CHECK-NEXT:       X86 WinAlloca Expander
 ; CHECK-NEXT:       Eliminate PHI nodes for register allocation
 ; CHECK-NEXT:       Two-Address instruction pass
 ; CHECK-NEXT:       Fast Register Allocator
 ; CHECK-NEXT:       Bundle Machine CFG Edges
 ; CHECK-NEXT:       X86 FP Stackifier
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis

llvm/test/CodeGen/X86/O3-pipeline.ll

 ; CHECK-NEXT:       Machine code sinking
 ; CHECK-NEXT:       Peephole Optimizations
 ; CHECK-NEXT:       Remove dead machine instructions
 ; CHECK-NEXT:       Live Range Shrink
 ; CHECK-NEXT:       X86 Fixup SetCC
 ; CHECK-NEXT:       X86 LEA Optimize
 ; CHECK-NEXT:       X86 Optimize Call Frame
 ; CHECK-NEXT:       X86 Avoid Store Forwarding Block
+; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       X86 EFLAGS copy lowering
 ; CHECK-NEXT:       X86 WinAlloca Expander
 ; CHECK-NEXT:       Detect Dead Lanes
 ; CHECK-NEXT:       Process Implicit Definitions
 ; CHECK-NEXT:       Remove unreachable machine basic blocks
 ; CHECK-NEXT:       Live Variable Analysis
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Natural Loop Construction

llvm/test/CodeGen/X86/copy-eflags.ll

 then:
   tail call void @external_a()
   ret void
 
 else:
   tail call void @external_b()
   ret void
 }
+
+; Test a function that gets special select lowering into CFG with copied EFLAGS
+; threaded across the CFG. This requires our EFLAGS copy rewriting to handle
+; cross-block rewrites in at least some narrow cases.
+;
+; Note that the 'undef' values here are significant! Other values will in many
+; cases not effectively trigger the lowering we're interested in exercising.
+define void @PR37100(i8 %arg1, i16 %arg2, i64 %arg3) {
+; X32-LABEL: PR37100:
+; X32:       # %bb.0: # %bb
+; X32-NEXT:    pushl %ebx
+; X32-NEXT:    .cfi_def_cfa_offset 8
+; X32-NEXT:    pushl %edi
+; X32-NEXT:    .cfi_def_cfa_offset 12
+; X32-NEXT:    pushl %esi
+; X32-NEXT:    .cfi_def_cfa_offset 16
+; X32-NEXT:    .cfi_offset %esi, -16
+; X32-NEXT:    .cfi_offset %edi, -12
+; X32-NEXT:    .cfi_offset %ebx, -8
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi
+; X32-NEXT:    movb {{[0-9]+}}(%esp), %bl
+; X32-NEXT:    jmp .LBB3_1
+; X32-NEXT:    .p2align 4, 0x90
+; X32-NEXT:  .LBB3_5: # %bb1
+; X32-NEXT:    # in Loop: Header=BB3_1 Depth=1
+; X32-NEXT:    xorl %eax, %eax
+; X32-NEXT:    xorl %edx, %edx
+; X32-NEXT:    idivl %edi
+; X32-NEXT:  .LBB3_1: # %bb1
+; X32-NEXT:    # =>This Inner Loop Header: Depth=1
+; X32-NEXT:    movsbl %bl, %eax
+; X32-NEXT:    movl %eax, %edx
+; X32-NEXT:    sarl $31, %edx
+; X32-NEXT:    cmpl %eax, %esi
+; X32-NEXT:    movl %ecx, %eax
+; X32-NEXT:    sbbl %edx, %eax
+; X32-NEXT:    setl %al
+; X32-NEXT:    setl %dl
+; X32-NEXT:    movzbl %dl, %edi
+; X32-NEXT:    negl %edi
+; X32-NEXT:    testb $-1, %al
+; X32-NEXT:    jne .LBB3_3
+; X32-NEXT:  # %bb.2: # %bb1
+; X32-NEXT:    # in Loop: Header=BB3_1 Depth=1
+; X32-NEXT:    # implicit-def: $bl
+; X32-NEXT:  .LBB3_3: # %bb1
+; X32-NEXT:    # in Loop: Header=BB3_1 Depth=1
+; X32-NEXT:    testb $-1, %al
+; X32-NEXT:    jne .LBB3_5
+; X32-NEXT:  # %bb.4: # %bb1
+; X32-NEXT:    # in Loop: Header=BB3_1 Depth=1
+; X32-NEXT:    # implicit-def: $edi
+; X32-NEXT:    jmp .LBB3_5
+;
+; X64-LABEL: PR37100:
+; X64:       # %bb.0: # %bb
+; X64-NEXT:    movq %rdx, %rcx
+; X64-NEXT:    jmp .LBB3_1
+; X64-NEXT:    .p2align 4, 0x90
+; X64-NEXT:  .LBB3_3: # %bb1
+; X64-NEXT:    # in Loop: Header=BB3_1 Depth=1
+; X64-NEXT:    cmovll %eax, %esi
+; X64-NEXT:    xorl %eax, %eax
+; X64-NEXT:    xorl %edx, %edx
+; X64-NEXT:    idivl %esi
+; X64-NEXT:  .LBB3_1: # %bb1
+; X64-NEXT:    # =>This Inner Loop Header: Depth=1
+; X64-NEXT:    movsbq %dil, %rdx
+; X64-NEXT:    xorl %eax, %eax
+; X64-NEXT:    cmpq %rdx, %rcx
+; X64-NEXT:    setl %al
+; X64-NEXT:    negl %eax
+; X64-NEXT:    cmpq %rdx, %rcx
+; X64-NEXT:    jl .LBB3_3
+; X64-NEXT:  # %bb.2: # %bb1
+; X64-NEXT:    # in Loop: Header=BB3_1 Depth=1
+; X64-NEXT:    # implicit-def: $dil
+; X64-NEXT:    jmp .LBB3_3
+bb:
+  br label %bb1
+
+bb1:
+  %tmp = phi i8 [ %tmp8, %bb1 ], [ %arg1, %bb ]
+  %tmp2 = phi i16 [ %tmp11, %bb1 ], [ %arg2, %bb ]
+  %tmp3 = icmp sgt i16 %tmp2, 7
+  %tmp4 = select i1 %tmp3, i16 %tmp2, i16 7
+  %tmp5 = sext i8 %tmp to i64
+  %tmp6 = icmp slt i64 %arg3, %tmp5
+  %tmp7 = sext i1 %tmp6 to i32
+  %tmp8 = select i1 %tmp6, i8 %tmp, i8 undef
+  %tmp9 = select i1 %tmp6, i32 %tmp7, i32 undef
+  %tmp10 = srem i32 0, %tmp9
+  %tmp11 = trunc i32 %tmp10 to i16
+  br label %bb1
+}