[RegisterCoalesing] Eliminate unnecessary live range shrinking inside of reMaterializeTrivialDef

[wmi]

Summary

For the following mir case below:
%2:gr32 = MOV32ri -343593632
$edx = COPY %2:gr32
TCRETURNdi64 @llvm_gcda_emit_function, 0
$edx = COPY %2:gr32
TCRETURNdi64 @llvm_gcda_emit_function, 0
...

During RegisterCoalescing, %edx = COPY %2:gr32 will be replaced by %edx = MOV32ri -343593632 in reMaterializeTrivialDef, and each time we do the replacement, shrinkUses will be called to shrink the live range of %2. shrinkUses is a relative high cost operation. If we have a lot of COPY to be eliminated in reMaterializeTrivialDef, we will see compile time problem. However, if we know there is other use of %2 after the current COPY instruction, we don't need to call shrinkUses because we know the live range of %2 is not going to change after the COPY is removed.

The patch will skip shrinkUses call when deleting a COPY instruction if the live range of %2 lives at the DeadSlot of the COPY instruction and the live range doesn't live at the end of current basicblock (to avoid the current COPY is the last use of %2 in a loop or cycle)

We saw in an extreme case that the file's compile time was reduced from 300s to 200s because of the patch.

lib/CodeGen/RegisterCoalescer.cpp

for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) {
     for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
       if (LiveRange *LR = LIS->getCachedRegUnit(*Units))
         LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
   }
 
   DEBUG(dbgs() << "Remat: " << NewMI);
   ++NumReMats;
 
+  // shrinkToUses has relative high cost. If there is other use of the SrcReg
+  // after CopyMI in MBB, it is unnecessary to update the live range. This
+  // can save a lot of compile time in some extreme cases.
+  if (SrcInt.liveAt(CopyIdx.getDeadSlot()) && !LIS->isLiveOutOfMBB(SrcInt, MBB))
+    return true;
+
   // The source interval can become smaller because we removed a use.
   shrinkToUses(&SrcInt, &DeadDefs);
   if (!DeadDefs.empty()) {
     // If the virtual SrcReg is completely eliminated, update all DBG_VALUEs
     // to describe DstReg instead.
     for (MachineOperand &UseMO : MRI->use_operands(SrcReg)) {
       MachineInstr *UseMI = UseMO.getParent();
       if (UseMI->isDebugValue()) {

test/CodeGen/X86/only-necessary-shrink.mir

+# REQUIRES: asserts
+# RUN: llc -run-pass simple-register-coalescing -mtriple=x86_64-gnu-unknown -debug-only=regalloc -o - %s 2>&1| FileCheck %s
+--- |
+  target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+  
+  declare void @hoo(i32)
+  
+  define internal void @foo() {
+    tail call void @hoo(i32 -343593632)
+    tail call void @hoo(i32 -343593632)
+    tail call void @hoo(i32 -343593632)
+    ret void
+  }
+  
+  define internal void @goo() {
+    %a = add i32 -343593632, 0
+    br label %while.body
+  
+  while.body:                                       ; preds = %while.body, %0
+    tail call void @hoo(i32 -343593632)
+    br label %while.body
+  }
+  
+  ; Function Attrs: nounwind
+  declare void @llvm.stackprotector(i8*, i8**) #0
+  
+  attributes #0 = { nounwind }
+
+...
+---
+name:            foo
+alignment:       4
+tracksRegLiveness: true
+registers:       
+  - { id: 0, class: gr32 }
+frameInfo:       
+  hasCalls:        true
+body:             |
+  bb.0 (%ir-block.0):
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    %0:gr32 = MOV32ri -343593632
+    $edi = COPY %0
+    CALL64pcrel32 @hoo, csr_64, implicit $rsp, implicit $ssp, implicit killed $edi, implicit-def $rsp, implicit-def $ssp
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    $edi = COPY %0
+    CALL64pcrel32 @hoo, csr_64, implicit $rsp, implicit $ssp, implicit killed $edi, implicit-def $rsp, implicit-def $ssp
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    $edi = COPY killed %0
+    TCRETURNdi64 @hoo, 0, csr_64, implicit $rsp, implicit $ssp, implicit killed $edi
+
+    ; Check only one shink operation happens and that shrink will lead to dead
+    ; def being deleted.
+    ; CHECK-LABEL: Function: foo
+    ; CHECK-NOT: Shrunk
+    ; CHECK: Shrunk
+    ; CHECK-NEXT: Deleting dead def
+
+...
+---
+name:            goo
+alignment:       4
+tracksRegLiveness: true
+registers:       
+  - { id: 0, class: gr32 }
+frameInfo:       
+  hasCalls:        true
+body:             |
+  bb.0 (%ir-block.0):
+    %0:gr32 = MOV32ri -343593632
+  
+  bb.1.while.body:
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    $edi = COPY %0
+    CALL64pcrel32 @hoo, csr_64, implicit $rsp, implicit $ssp, implicit killed $edi, implicit-def $rsp, implicit-def $ssp
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    JMP_1 %bb.1
+
+    ; Check one shink operation happens and that shrink will lead to dead
+    ; def being deleted.
+    ; CHECK-LABEL: Function: goo
+    ; CHECK-NOT: Shrunk
+    ; CHECK: Shrunk
+    ; CHECK-NEXT: Deleting dead def
+
+...