X86InstrInfo: Look across basic blocks in optimizeCompareInstr

[MatzeB]

Summary

This extends optimizeCompareInstr to continue the backwards search when it reached the beginning of a basic block. If there is a single predecessor block then we can just continue the search in that block and mark the EFLAGS register as live-in.

[craig.topper]

llvm/lib/Target/X86/X86InstrInfo.cpp

4291

Should this be in the first patch where this comment was created?

[pengfei]

llvm/lib/Target/X86/X86InstrInfo.cpp

4475–4478

Do we have a test for it?

[MatzeB]

llvm/lib/Target/X86/X86InstrInfo.cpp

4291

just dropped the change instead.

4475–4478

Added one.

[MatzeB]

ping

[pengfei]

LGTM. Please wait for 1 or 2 days for other reviewers' comments.

[craig.topper]

LGTM

[MatzeB]

rebase; update jump_sign.ll test

[RKSimon]

LGTM - cheers

llvm/lib/Target/X86/X86InstrInfo.cpp

bool X86InstrInfo::optimizeCompareInstr(MachineInstr &CmpInstr, Register SrcReg,
   MachineInstr *MI = nullptr;
   MachineInstr *Sub = nullptr;
   MachineInstr *Movr0Inst = nullptr;
   bool NoSignFlag = false;
   bool ClearsOverflowFlag = false;
   bool ShouldUpdateCC = false;
   X86::CondCode NewCC = X86::COND_INVALID;
 
   // Search backward from CmpInstr for the next instruction defining EFLAGS.
   const TargetRegisterInfo *TRI = &getRegisterInfo();
   MachineBasicBlock &CmpMBB = *CmpInstr.getParent();
   MachineBasicBlock::reverse_iterator From =
       std::next(MachineBasicBlock::reverse_iterator(CmpInstr));
   MachineInstr *SrcRegDef = MRI->getVRegDef(SrcReg);
   assert(SrcRegDef && "Must have a definition (SSA)");
-  for (MachineInstr &Inst : make_range(From, CmpMBB.rend())) {
+  for (MachineBasicBlock *MBB = &CmpMBB;;) {
+    for (MachineInstr &Inst : make_range(From, MBB->rend())) {
       // Try to use EFLAGS from the instruction defining %SrcReg. Example:
       //     %eax = addl ...
       //     ...                // EFLAGS not changed
       //     testl %eax, %eax   // <-- can be removed
       if (&Inst == SrcRegDef) {
-      if (IsCmpZero && isDefConvertible(Inst, NoSignFlag, ClearsOverflowFlag)) {
+        if (IsCmpZero &&
+            isDefConvertible(Inst, NoSignFlag, ClearsOverflowFlag)) {
           MI = &Inst;
           break;
         }
         // Cannot find other candidates before definition of SrcReg.
         return false;
       }
 
       if (Inst.modifiesRegister(X86::EFLAGS, TRI)) {
-      // Try to use EFLAGS produced by an instruction reading %SrcReg. Example:
+        // Try to use EFLAGS produced by an instruction reading %SrcReg.
+        // Example:
         //      %eax = ...
         //      ...
         //      popcntl %eax
         //      ...                 // EFLAGS not changed
         //      testl %eax, %eax    // <-- can be removed
         if (IsCmpZero) {
           NewCC = isUseDefConvertible(Inst);
           if (NewCC != X86::COND_INVALID && Inst.getOperand(1).isReg() &&
               Inst.getOperand(1).getReg() == SrcReg) {
             ShouldUpdateCC = true;
             MI = &Inst;
             break;
           }
         }
 
         // Try to use EFLAGS from an instruction with similar flag results.
         // Example:
         //     sub x, y  or  cmp x, y
         //     ...           // EFLAGS not changed
         //     cmp x, y      // <-- can be removed
-      if (!IsCmpZero && isRedundantFlagInstr(CmpInstr, SrcReg, SrcReg2, CmpMask,
-                                             CmpValue, Inst)) {
+        if (!IsCmpZero && isRedundantFlagInstr(CmpInstr, SrcReg, SrcReg2,
+                                               CmpMask, CmpValue, Inst)) {
           Sub = &Inst;
           break;
         }
 
         // MOV32r0 is implemented with xor which clobbers condition code. It is
         // safe to move up, if the definition to EFLAGS is dead and earlier
         // instructions do not read or write EFLAGS.
         if (!Movr0Inst && Inst.getOpcode() == X86::MOV32r0 &&
             Inst.registerDefIsDead(X86::EFLAGS, TRI)) {
           Movr0Inst = &Inst;
           continue;
         }
 
         // Cannot do anything for any other EFLAG changes.
         return false;
       }
     }
 
-  // Return false if no candidates exist.
-  if (!MI && !Sub)
+    if (MI || Sub)
+      break;
+
+    // Reached begin of basic block. Continue in predecessor if there is
+    // exactly one.
+    if (MBB->pred_size() != 1)
       return false;
+    MBB = *MBB->pred_begin();
+    From = MBB->rbegin();
+  }
 
   bool IsSwapped =
       (SrcReg2 != 0 && Sub && Sub->getOperand(1).getReg() == SrcReg2 &&
        Sub->getOperand(2).getReg() == SrcReg);
 
   // Scan forward from the instruction after CmpInstr for uses of EFLAGS.
   // It is safe to remove CmpInstr if EFLAGS is redefined or killed.
   // If we are done with the basic block, we need to check whether EFLAGS is
bool X86InstrInfo::optimizeCompareInstr(MachineInstr &CmpInstr, Register SrcReg,
   if ((IsCmpZero || IsSwapped) && !IsSafe) {
     for (MachineBasicBlock *Successor : CmpMBB.successors())
       if (Successor->isLiveIn(X86::EFLAGS))
         return false;
   }
 
   // The instruction to be updated is either Sub or MI.
   Sub = IsCmpZero ? MI : Sub;
+  MachineBasicBlock *SubBB = Sub->getParent();
   // Move Movr0Inst to the appropriate place before Sub.
   if (Movr0Inst) {
+    // Only move within the same block so we don't accidentally move to a
+    // block with higher execution frequency.
+    if (&CmpMBB != SubBB)
+      return false;
     // Look backwards until we find a def that doesn't use the current EFLAGS.
     MachineBasicBlock::reverse_iterator InsertI = Sub,
                                         InsertE = Sub->getParent()->rend();
     for (; InsertI != InsertE; ++InsertI) {
       MachineInstr *Instr = &*InsertI;
       if (!Instr->readsRegister(X86::EFLAGS, TRI) &&
           Instr->modifiesRegister(X86::EFLAGS, TRI)) {
-        Sub->getParent()->remove(Movr0Inst);
+        Movr0Inst->getParent()->remove(Movr0Inst);
         Instr->getParent()->insert(MachineBasicBlock::iterator(Instr),
                                    Movr0Inst);
         break;
       }
     }
     if (InsertI == InsertE)
       return false;
   }
 
   // Make sure Sub instruction defines EFLAGS and mark the def live.
   MachineOperand *FlagDef = Sub->findRegisterDefOperand(X86::EFLAGS);
   assert(FlagDef && "Unable to locate a def EFLAGS operand");
   FlagDef->setIsDead(false);
 
   CmpInstr.eraseFromParent();
 
   // Modify the condition code of instructions in OpsToUpdate.
   for (auto &Op : OpsToUpdate) {
     Op.first->getOperand(Op.first->getDesc().getNumOperands() - 1)
         .setImm(Op.second);
   }
+  // Add EFLAGS to block live-ins between CmpBB and block of flags producer.
+  for (MachineBasicBlock *MBB = &CmpMBB; MBB != SubBB;
+       MBB = *MBB->pred_begin()) {
+    assert(MBB->pred_size() == 1 && "Expected exactly one predecessor");
+    if (!MBB->isLiveIn(X86::EFLAGS))
+      MBB->addLiveIn(X86::EFLAGS);
+  }
   return true;
 }
 
 /// Try to remove the load by folding it to a register
 /// operand at the use. We fold the load instructions if load defines a virtual
 /// register, the virtual register is used once in the same BB, and the
 /// instructions in-between do not load or store, and have no side effects.
 MachineInstr *X86InstrInfo::optimizeLoadInstr(MachineInstr &MI,

llvm/test/CodeGen/X86/jump_sign.ll

 ; CHECK-NEXT:    cmovgl %ecx, %eax
 ; CHECK-NEXT:    retl
   %cmp = icmp sgt i32 %a, %b
   %sub = sub nsw i32 %a, %b
   %cond = select i1 %cmp, i32 %b, i32 %sub
   ret i32 %cond
 }
 
-; If EFLAGS is live-out, we can't remove cmp if there exists
-; a swapped sub.
+; (This used to test that an unsafe removal of cmp in bb.0 is not happening,
+;  but now we can do so safely).
 define i32 @func_l2(i32 %a, i32 %b) nounwind {
 ; CHECK-LABEL: func_l2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; CHECK-NEXT:    movl %ecx, %eax
-; CHECK-NEXT:    subl %edx, %eax
+; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; CHECK-NEXT:    movl %eax, %ecx
+; CHECK-NEXT:    subl %edx, %ecx
 ; CHECK-NEXT:    jne .LBB8_2
 ; CHECK-NEXT:  # %bb.1: # %if.then
-; CHECK-NEXT:    cmpl %ecx, %edx
-; CHECK-NEXT:    cmovlel %ecx, %eax
+; CHECK-NEXT:    cmovll %ecx, %eax
+; CHECK-NEXT:    retl
 ; CHECK-NEXT:  .LBB8_2: # %if.else
+; CHECK-NEXT:    movl %ecx, %eax
 ; CHECK-NEXT:    retl
   %cmp = icmp eq i32 %b, %a
   %sub = sub nsw i32 %a, %b
   br i1 %cmp, label %if.then, label %if.else
 
 if.then:
   %cmp2 = icmp sgt i32 %b, %a
   %sel = select i1 %cmp2, i32 %sub, i32 %a

llvm/test/CodeGen/X86/optimize-compare.mir

bb.0:
     %0:gr64 = COPY $rsi
     %1:gr64 = DEC64r %0, implicit-def $eflags
     ; CMP should be removed.
     CMP64ri8 %1, 0, implicit-def $eflags
     %2:gr64 = LEA64r %1, 5, $noreg, 12, $noreg
     $al = SETCCr 4, implicit $eflags
 ...
 ---
+name: opt_multiple_blocks
+tracksRegLiveness: true
+body: |
+  ; CHECK-LABEL: name: opt_multiple_blocks
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr64 = COPY undef $rsi
+  ; CHECK-NEXT:   [[INC64r:%[0-9]+]]:gr64 = INC64r [[COPY]], implicit-def $eflags
+  ; CHECK-NEXT:   PUSH64r undef $rcx, implicit-def $rsp, implicit $rsp
+  ; CHECK-NEXT:   $rcx = POP64r implicit-def $rsp, implicit $rsp
+  ; CHECK-NEXT:   JMP_1 %bb.1
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   liveins: $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[LEA64r:%[0-9]+]]:gr64 = LEA64r [[INC64r]], 5, $noreg, 12, $noreg
+  ; CHECK-NEXT:   $al = SETCCr 4, implicit $eflags
+  bb.0:
+    %0:gr64 = COPY undef $rsi
+    %1:gr64 = INC64r %0, implicit-def $eflags
+    PUSH64r undef $rcx, implicit-def $rsp, implicit $rsp
+    $rcx = POP64r implicit-def $rsp, implicit $rsp
+    JMP_1 %bb.1
+
+  bb.1:
+    ; TEST should be removed.
+    TEST64rr %1, %1, implicit-def $eflags
+    %2:gr64 = LEA64r %1, 5, $noreg, 12, $noreg
+    $al = SETCCr 4, implicit $eflags
+...
+---
+name: opt_multiple_blocks_noopt_0
+body: |
+  ; CHECK-LABEL: name: opt_multiple_blocks_noopt_0
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr64 = COPY undef $rsi
+  ; CHECK-NEXT:   [[INC64r:%[0-9]+]]:gr64 = INC64r [[COPY]], implicit-def $eflags
+  ; CHECK-NEXT:   JMP_1 %bb.1
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   TEST64rr [[INC64r]], [[INC64r]], implicit-def $eflags
+  ; CHECK-NEXT:   [[LEA64r:%[0-9]+]]:gr64 = LEA64r [[INC64r]], 5, $noreg, 12, $noreg
+  ; CHECK-NEXT:   $al = SETCCr 4, implicit $eflags
+  ; CHECK-NEXT:   JCC_1 %bb.1, 2, implicit $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  bb.0:
+    %0:gr64 = COPY undef $rsi
+    %1:gr64 = INC64r %0, implicit-def $eflags
+    JMP_1 %bb.1
+
+  bb.1:
+    ; The TEST64rr should not be removed, since there are multiple preds.
+    TEST64rr %1, %1, implicit-def $eflags
+    %2:gr64 = LEA64r %1, 5, $noreg, 12, $noreg
+    $al = SETCCr 4, implicit $eflags
+    JCC_1 %bb.1, 2, implicit $eflags
+
+  bb.2:
+...
+---
+name: opt_multiple_blocks_noopt_1
+body: |
+  ; CHECK-LABEL: name: opt_multiple_blocks_noopt_1
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   JMP_1 %bb.1
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr64 = COPY undef $rsi
+  ; CHECK-NEXT:   TEST64rr [[COPY]], [[COPY]], implicit-def $eflags
+  ; CHECK-NEXT:   JCC_1 %bb.1, 2, implicit $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   [[MOV32r0_:%[0-9]+]]:gr32 = MOV32r0 implicit-def $eflags
+  ; CHECK-NEXT:   TEST64rr [[COPY]], [[COPY]], implicit-def $eflags
+  ; CHECK-NEXT:   $al = SETCCr 4, implicit $eflags
+  bb.0:
+    JMP_1 %bb.1
+
+  bb.1:
+    %0:gr64 = COPY undef $rsi
+    TEST64rr %0, %0, implicit-def $eflags
+    JCC_1 %bb.1, 2, implicit $eflags
+
+  bb.2:
+    ; We should not move MOV32r0 up into the loop (that would be correct but
+    ; slow).
+    %1:gr32 = MOV32r0 implicit-def $eflags
+    ; TEST should not be removed because of MOV32r0.
+    TEST64rr %0, %0, implicit-def $eflags
+    $al = SETCCr 4, implicit $eflags
+...
+---
 name: opt_zerocmp_user_0
 body: |
   bb.0:
     ; CHECK-LABEL: name: opt_zerocmp_user_0
     ; CHECK: [[COPY:%[0-9]+]]:gr32 = COPY $esi
     ; CHECK-NEXT: [[NEG32r:%[0-9]+]]:gr32 = NEG32r [[COPY]], implicit-def $eflags
     ; CHECK-NEXT: $al = SETCCr 3, implicit $eflags
     %0:gr32 = COPY $esi