[MachineCSE] Extend the scope of multi block processing.

[skatkov]

Summary

At the moment CSE consider only one predecessor if it is alone.
This patch allows to search in any number of block if for each
of them there is only one predecessor.

The LookAheadLimit still controls the number of instruction
to proceed.

The motivation case is in llvm/test/CodeGen/X86/cse-two-preds.mir and https://godbolt.org/z/rEj9GPfnY

[goldstein.w.n]

llvm/lib/CodeGen/MachineCSE.cpp

369

Why reverse iterator?

llvm/test/CodeGen/Thumb2/thumb2-cbnz.ll

9

why change the IR in this test?

llvm/test/CodeGen/X86/ins_subreg_coalesce-3.ll

63

Seems to cause a regression here?

[skatkov]

Thank you, for review!

llvm/lib/CodeGen/MachineCSE.cpp

369

This is due to way I filled BB2Visit. It contains all BasicBlocks from MI parent to CSMI parent. If I traverse it in this order it is natural to use reverse iterator.

If you'd like I can re-write it in opposite way (whether we go from CMSI to MI or vise versa nothing is changed).
Use iterator and push back basic blocks from BB2Visit.

llvm/test/CodeGen/Thumb2/thumb2-cbnz.ll

9

The test is artificial, it contains the the same comparison in several basic blocks. To be honest such IR should not be in CodeGen, middle end should simplify it.

The basic block where cbnz is expected actually contains a comparison which is always true (due to dominating check). With this change the corresponding comparison is just eliminated and test fails.

Taking into account the name of test I decided to modify the test to keep the possibility to generate cbnz.

llvm/test/CodeGen/X86/ins_subreg_coalesce-3.ll

63

Indeed. The reason of regression is a difference in behavior of BranchFolding pass.
This problem I've tried to resolve in https://reviews.llvm.org/D148514 but as we saw I need to do more work there.
Briefly, before this change BranchFolding was able to handle this case in tail merging, due to the same tail

test
jcc

in several basic blocks.
With this change some intermittent test instruction has been eliminated and BrachFolding/TailMerging has smaller tail now and cannot handle it.

Taking into account that this test is also contains several identical branches (should be eliminated in middle end), the name of the test says that this test is not about BranchFolding or this branch at all and I plan to do something with BranchFolding optimization, I guess we can accept this regression.

[skatkov]

Re-factor code to avoid usage of reverse iterator.

[skatkov]

cosmetic changes.

[skatkov]

another small change - early bailout.

[skatkov]

ping

[goldstein.w.n]

llvm/test/CodeGen/X86/ins_subreg_coalesce-3.ll

63

Given that is causes a regression here, I think D148514 should proceed this patch.

[goldstein.w.n]

llvm/test/CodeGen/X86/ins_subreg_coalesce-3.ll

63

Given that is causes a regression here, I think D148514 should proceed this patch.

Can you make them a series?

[skatkov]

llvm/test/CodeGen/X86/ins_subreg_coalesce-3.ll

63

Done.

[skatkov]

At the moment I do not see simple way to implement https://reviews.llvm.org/D148514, so I put this on hold due to temporary busy with other stuff.

llvm/lib/CodeGen/MachineCSE.cpp

 }
 
 bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
                                   SmallSet<MCRegister, 8> &PhysRefs,
                                   PhysDefVector &PhysDefs,
                                   bool &NonLocal) const {
   // For now conservatively returns false if the common subexpression is
   // not in the same basic block as the given instruction. The only exception
-  // is if the common subexpression is in the sole predecessor block.
-  const MachineBasicBlock *MBB = MI->getParent();
+  // is if the common subexpression is in chain of sole predecessor blocks.
   const MachineBasicBlock *CSMBB = CSMI->getParent();
-
-  bool CrossMBB = false;
-  if (CSMBB != MBB) {
-    if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB)
+  // BB2Visit contains [MBB, CSMBB). Might be empty if MBB == CSMBB.
+  SmallVector<MachineBasicBlock *, 4> BB2Visit;
+  for (auto *MBB = MI->getParent(); MBB != CSMBB; MBB = *MBB->pred_begin()) {
+    if (MBB->pred_size() != 1)
       return false;
+    BB2Visit.push_back(MBB);
+  }
 
+  if (!BB2Visit.empty()) {
     for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) {
       if (MRI->isAllocatable(PhysDefs[i].second) ||
           MRI->isReserved(PhysDefs[i].second))
         // Avoid extending live range of physical registers if they are
         //allocatable or reserved.
         return false;
     }
-    CrossMBB = true;
   }
   MachineBasicBlock::const_iterator I = CSMI; I = std::next(I);
   MachineBasicBlock::const_iterator E = MI;
   MachineBasicBlock::const_iterator EE = CSMBB->end();
   unsigned LookAheadLeft = LookAheadLimit;
   while (LookAheadLeft) {
     // Skip over dbg_value's.
     while (I != E && I != EE && I->isDebugInstr())
       ++I;
 
     if (I == EE) {
-      assert(CrossMBB && "Reaching end-of-MBB without finding MI?");
-      (void)CrossMBB;
-      CrossMBB = false;
+      assert(!BB2Visit.empty() && "Missed CSMI?");
+      auto *BB = BB2Visit.pop_back_val();
       NonLocal = true;
-      I = MBB->begin();
-      EE = MBB->end();
+      I = BB->begin();
+      EE = BB->end();
       continue;
     }
 
     if (I == E)
       return true;
 
     for (const MachineOperand &MO : I->operands()) {
       // RegMasks go on instructions like calls that clobber lots of physregs.

llvm/test/CodeGen/Thumb2/thumb2-cbnz.ll

 ; RUN: llc < %s -mtriple=thumbv7-apple-darwin -mcpu=cortex-a8 -arm-atomic-cfg-tidy=0 | FileCheck %s
 ; rdar://7354379
 
 declare double @foo(double) nounwind readnone
 
 define void @t(i32 %c, double %b) {
 entry:
-; CHECK:      cmp r0, #0
-  %cmp1 = icmp ne i32 %c, 0
+; CHECK:      cmp r0, #2
+  %cmp1 = icmp ne i32 %c, 2
   br i1 %cmp1, label %bb3, label %bb1
 
 bb1:                                              ; preds = %entry
   unreachable
 
 bb3:                                              ; preds = %entry
-  %cmp2 = icmp ne i32 %c, 0
+  %cmp2 = icmp ne i32 %c, 1
   br i1 %cmp2, label %bb7, label %bb5
 
 bb5:                                              ; preds = %bb3
   unreachable
 
 bb7:                                              ; preds = %bb3
   %cmp3 = icmp ne i32 %c, 0
   br i1 %cmp3, label %bb11, label %bb9

llvm/test/CodeGen/X86/2007-11-30-LoadFolding-Bug.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-- -mattr=+sse2 | FileCheck %s
 ; Increment in loop bb.i28.i adjusted to 2, to prevent loop reversal from
 ; kicking in.
 
 declare fastcc void @rdft(i32, i32, ptr, ptr, ptr)
 
 define fastcc void @mp_sqrt(i32 %n, i32 %radix, ptr %in, ptr %out, ptr %tmp1, ptr %tmp2, i32 %nfft, ptr %tmp1fft, ptr %tmp2fft, ptr %ip, ptr %w) nounwind {
 ; CHECK-LABEL: mp_sqrt:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    pushl %ebp
 ; CHECK-NEXT:    pushl %ebx
 ; CHECK-NEXT:    pushl %edi
 ; CHECK-NEXT:    pushl %esi
 ; CHECK-NEXT:    movl %edx, %esi
-; CHECK-NEXT:    movb $1, %cl
+; CHECK-NEXT:    movb $1, %al
 ; CHECK-NEXT:    movl $1, %ebx
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %edi
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_1: # %bb.i5
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
-; CHECK-NEXT:    movl %ecx, %eax
+; CHECK-NEXT:    movl %eax, %ecx
 ; CHECK-NEXT:    addl %ebx, %ebx
-; CHECK-NEXT:    xorl %ecx, %ecx
-; CHECK-NEXT:    testb $1, %al
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    testb $1, %cl
 ; CHECK-NEXT:    jne .LBB0_1
 ; CHECK-NEXT:  # %bb.2: # %mp_unexp_mp2d.exit.i
 ; CHECK-NEXT:    je .LBB0_10
 ; CHECK-NEXT:  # %bb.3: # %cond_next.i
-; CHECK-NEXT:    testb $1, %al
 ; CHECK-NEXT:    jne .LBB0_10
 ; CHECK-NEXT:  # %bb.4: # %cond_next36.i
 ; CHECK-NEXT:    movl $0, 0
-; CHECK-NEXT:    movzbl %al, %ebp
+; CHECK-NEXT:    movzbl %cl, %ebp
 ; CHECK-NEXT:    andl $1, %ebp
 ; CHECK-NEXT:    xorpd %xmm0, %xmm0
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    xorl %ecx, %ecx
 ; CHECK-NEXT:    xorpd %xmm1, %xmm1
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_5: # %bb.i28.i
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1

llvm/test/CodeGen/X86/2008-04-17-CoalescerBug.ll

 ; CHECK-NEXT:    .cfi_offset %ebp, -8
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; CHECK-NEXT:    movzbl {{[0-9]+}}(%esp), %ebx
 ; CHECK-NEXT:    testb $1, %bl
 ; CHECK-NEXT:    je LBB0_25
 ; CHECK-NEXT:  ## %bb.1: ## %bb116.i
 ; CHECK-NEXT:    je LBB0_25
 ; CHECK-NEXT:  ## %bb.2: ## %bb52.i.i
-; CHECK-NEXT:    testb $1, %bl
 ; CHECK-NEXT:    je LBB0_25
 ; CHECK-NEXT:  ## %bb.3: ## %bb142.i
+; CHECK-NEXT:    testb $1, %bl
 ; CHECK-NEXT:    je LBB0_25
 ; CHECK-NEXT:  ## %bb.4:
 ; CHECK-NEXT:    movl L_.str89$non_lazy_ptr, %edi
 ; CHECK-NEXT:    movb $1, %bh
 ; CHECK-NEXT:    movl L_.str$non_lazy_ptr, %ebp
 ; CHECK-NEXT:    jmp LBB0_5
 ; CHECK-NEXT:  LBB0_21: ## %bb7806
 ; CHECK-NEXT:    ## in Loop: Header=BB0_5 Depth=1

llvm/test/CodeGen/X86/cse-two-preds.mir

body:             |
   ; CHECK-NEXT:   successors: %bb.8(0x40000000), %bb.2(0x40000000)
   ; CHECK-NEXT:   liveins: $eflags
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   JCC_1 %bb.8, 7, implicit $eflags
   ; CHECK-NEXT:   JMP_1 %bb.2
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.2.NGT:
   ; CHECK-NEXT:   successors: %bb.8(0x50000000), %bb.3(0x30000000)
+  ; CHECK-NEXT:   liveins: $eflags
   ; CHECK-NEXT: {{  $}}
-  ; CHECK-NEXT:   nofpexcept VUCOMISSrr [[COPY1]], [[COPY]], implicit-def $eflags, implicit $mxcsr
   ; CHECK-NEXT:   JCC_1 %bb.8, 5, implicit $eflags
   ; CHECK-NEXT:   JMP_1 %bb.3
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.3.EQ:
   ; CHECK-NEXT:   successors: %bb.4(0x40000000), %bb.5(0x40000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   [[VMOVSS2DIrr:%[0-9]+]]:gr32 = VMOVSS2DIrr [[COPY1]]
   ; CHECK-NEXT:   TEST32rr [[VMOVSS2DIrr]], [[VMOVSS2DIrr]], implicit-def $eflags

llvm/test/CodeGen/X86/ins_subreg_coalesce-3.ll

; RUN: llc < %s -mtriple=x86_64-- | FileCheck %s
   %struct.head_type = type { [2 x %struct.LIST], %struct.FIRST_UNION, %struct.SECOND_UNION, %struct.THIRD_UNION, %struct.FOURTH_UNION, ptr, { ptr }, ptr, ptr, ptr, ptr, ptr, ptr, ptr, ptr, i32 }
   %struct.metrics = type { i16, i16, i16, i16, i16 }
   %struct.rec = type { %struct.head_type }
 
 define void @FontChange(i1 %foo) nounwind {
 ; CHECK-LABEL: FontChange:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    je .LBB0_9
+; CHECK-NEXT:    je .LBB0_11
+; CHECK-NEXT:  # %bb.1: # %bb298
+; CHECK-NEXT:    je .LBB0_3
+; CHECK-NEXT:  # %bb.2: # %bb304
+; CHECK-NEXT:    je .LBB0_4
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB0_1: # %bb366
+; CHECK-NEXT:  .LBB0_3: # %bb366
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    jne .LBB0_1
-; CHECK-NEXT:  # %bb.2: # %bb428
+; CHECK-NEXT:    jne .LBB0_3
+; CHECK-NEXT:  .LBB0_4: # %bb428
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    je .LBB0_9
+; CHECK-NEXT:    je .LBB0_11
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB0_3: # %bb650
+; CHECK-NEXT:  .LBB0_5: # %bb650
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    cmpb $0, 0
-; CHECK-NEXT:    je .LBB0_3
-; CHECK-NEXT:  # %bb.4: # %bb662
+; CHECK-NEXT:    je .LBB0_5
+; CHECK-NEXT:  # %bb.6: # %bb662
 ; CHECK-NEXT:    movl 0, %eax
 ; CHECK-NEXT:    movl %eax, %ecx
 ; CHECK-NEXT:    andl $57344, %ecx # imm = 0xE000
 ; CHECK-NEXT:    cmpl $8192, %ecx # imm = 0x2000
-; CHECK-NEXT:    jne .LBB0_9
-; CHECK-NEXT:  # %bb.5: # %bb4884
+; CHECK-NEXT:    jne .LBB0_11
+; CHECK-NEXT:  # %bb.7: # %bb4884
 ; CHECK-NEXT:    andl $7168, %eax # imm = 0x1C00
 ; CHECK-NEXT:    cmpl $1024, %eax # imm = 0x400
-; CHECK-NEXT:    jne .LBB0_9
-; CHECK-NEXT:  # %bb.6: # %bb4932
+; CHECK-NEXT:    jne .LBB0_11
+; CHECK-NEXT:  # %bb.8: # %bb4932
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    jne .LBB0_9
-; CHECK-NEXT:  # %bb.7: # %bb4940
+; CHECK-NEXT:    jne .LBB0_11
+; CHECK-NEXT:  # %bb.9: # %bb4940
 ; CHECK-NEXT:    movl 0, %eax
 ; CHECK-NEXT:    cmpl $160, %eax
-; CHECK-NEXT:    je .LBB0_9
-; CHECK-NEXT:  # %bb.8: # %bb4940
+; CHECK-NEXT:    je .LBB0_11
+; CHECK-NEXT:  # %bb.10: # %bb4940
 ; CHECK-NEXT:    cmpl $159, %eax
-; CHECK-NEXT:  .LBB0_9: # %bb4897
+; CHECK-NEXT:  .LBB0_11: # %bb4897
 ; CHECK-NEXT:    retq
 entry:
   br i1 %foo, label %bb298, label %bb49
 bb49:   ; preds = %entry
   ret void
 bb298:    ; preds = %entry
   br i1 %foo, label %bb304, label %bb366
 bb304:    ; preds = %bb298
   br i1 %foo, label %bb330, label %bb428