[MachineSink] add one more profitable pattern for sinking

[shchenz]

Summary

This patch adds one profitable pattern to sink MI when MI->parent() dominates SuccToSinkTo and SuccToSinkTo post dominates MI->parent().

If MI is in loop and MI is:

def0, def1, defn = opcode, use0, use1, use2, use3

sinking MI to SuccToSinkTo will shorten the live range for def but will enlarge the live range for use.
But in loop, the use may be defined outside of loop, so if SuccToSinkTo is still in same loop, sinking MI should have no impact for the live range for the uses which are defined out of loop.

If we know that all the uses are defined outside of loop, it is still profitable to sink.

[qcolombet]

llvm/lib/CodeGen/MachineSink.cpp

608

Could you invert the logic to early exit and reduce the indentation here?

616

Reg == 0, should be fine. We should just skip them.

626

Instead of counting the number of live-ranges, we should probably count their weights with respect to the related register pressure set.

E.g., <smallDef>, <smallDef> = op <BigUse>

Maybe each smallDef accounts for 1 register whereas BigUse accounts for 4 registers.

[shchenz]

use registerclassweight

[shchenz]

llvm/lib/CodeGen/MachineSink.cpp

626

Good idea!

[shchenz]

gentle ping

[qcolombet]

Hi,

The update with the RegClassWeight is only partially done IMHO.
Each weight should be added/removed from the related register pressure sets. You can take a look at MachineLICM.cpp to see how to use these.

I.e., even if the total cost decreases, this doesn't guarantee that we won't go over the limit of a pressure set and thus, we would spill.
E.g.,

loop:
   smallDef =
   ... = smallDef
   bigDef = smallDef
   // lot of small defs.
  condbr loop

Sinking bigDef would be seen profitable since the weight of bigDef is greater than smallDef. However, extending smallDef will make it overlaps with a lot of small defs and may create spilling (remember that smallDef and bigDef could be on different register banks.)

For now I would suggest to either:

1. Implement the support of pressure sets, or
2. Only do the transformation when the def of the uses are outside the loop. Like you said, these won't have any impact on the register pressure.

Random though: currently MachineLICM only does hoisting. I think it would make sense to have it also do sinking.
Put differently, conceptually, given we are looking at loop invariant here, it would make sense to have this code in MachineLICM instead of MachineSink.

What do you think?

Cheers,
-Quentin

[shchenz]

@qcolombet Thanks for your good comments.

given we are looking at loop invariant here, it would make sense to have this code in MachineLICM instead of MachineSink

MachineLICM tries to move loop invariant instructions to outside of a loop(preheader of exit block). Here we want to move def closer to its use inside the loop.
If we want to support 'real' sink in MachineLICM(move loop invariant instructions to the exit block), it should always benefit for the loop's register pressure?

If we want to move def closer to its use inside the loop to benefit register pressure in MachineLICM pass, except many duplicated codes with machinesink pass, (condition checks in SinkInstruction), register estimate model in machineLICM also does not support this. I checked UpdateBackTraceRegPressure, seems now the model is designed for hoisting only. It just stores the register pressure on path from loop preheader to current BB. see RegPressure and calcRegisterCost(Sinking should have a different cost calculation). For sinking, we need to estimate the register pressure in the destination block which is not on path from loop preheader to current BB.

The real world case I met is not a loop invariant instruction, it has an operand which is a user of PHI in loop header.

So I think maybe we should implement this in machinesink pass?

But yes, the register pressure estimate is not accurate for now and your example shows this very well. If we want to estimate it accurately, maybe we can use struct RegisterPressure in RegisterPressure.h to check register pressure of the destinate BB after the sinking? If the register pressure for register pressure set exceeds the limit after the sinking, we don't sink. What do you think? @qcolombet

Thanks again for your comments.

[qcolombet]

The real world case I met is not a loop invariant instruction, it has an operand which is a user of PHI in loop header.

I see, yes, then having this in MachineSink makes sense. At least as a start :).

struct RegisterPressure is a good start, though I don't remember how it ties with the register pressure sets (TargetRegisterInfo::getRegClassPressureSets), which is ultimately what we want to use.

Given adding that is going to take some time, you could push your patch for the cases we know are always profitable: when the uses are alive across the whole loop (line 636 in the current implementation.)

Cheers,
-Quentin

[shchenz]

address @qcolombet comments:
1: firstly add the always profitable pattern

[shchenz]

Given adding that is going to take some time, you could push your patch for the cases we know are always profitable: when the uses are alive across the whole loop (line 636 in the current implementation.)

Thanks for this suggestion, updated this patch accordingly.
As expected, the improvement for the benchmark is gone now. : (
Will do the left part in following patch.

[qcolombet]

Hi,

As expected, the improvement for the benchmark is gone now. : (

Too bad. Hopefully it would take long to come up with the follow up path.

The source change looks good to me (there's one lint report that needs fixing though: one of the comment is larger than 80-col), but we miss a test case.

Could you add a test case that capture specifically what this patch is doing?
In other words, a test case that runs the machine sink pass alone and that fails without that patch and passes with that patch.

You can produce the skeleton of the test by running -stop-before machine-sink -simplify-mir, then you can use that output as input of your test with -run-pass=machine-sink.

Cheers,
-Quentin

[shchenz]

1: add one more mir test case
2: fix code format

[shchenz]

Thanks very much, updated, could you please help to have another look? @qcolombet

[qcolombet]

Hi @shchenz ,

1: add one more mir test case

Did you forget to do git add, I don't see it.

Cheers,
-Quentin

llvm/lib/CodeGen/MachineSink.cpp

672

This variable is a left over of the previous version of the patch.
Please delete it.

[shchenz]

delete unused variables

[shchenz]

1: add one more mir test case

Did you forget to do git add, I don't see it.

Weird, I added case test/CodeGen/PowerPC/sink-down-more-instructions-1.mir. Could you do another check?
Maybe we should delete the IR test test/CodeGen/PowerPC/sink-down-more-instructions.ll? it is same input with mir test.

[qcolombet]

Weird, I added case test/CodeGen/PowerPC/sink-down-more-instructions-1.mir. Could you do another check?

Ah sorry about that. I was expecting a new file, whereas the diff only shows a change in sinking for that file.

Up to you for the .ll file.

[shchenz]

Ah sorry about that. I was expecting a new file, whereas the diff only shows a change in sinking for that file.

To make the review easy, I pre-commit an NFC patch to add the test case. :)
Thanks very much for your patient review @qcolombet

llvm/lib/CodeGen/MachineSink.cpp

bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
   // If SuccToSinkTo post dominates then also it may be profitable if MI
   // can further profitably sinked into another block in next round.
   bool BreakPHIEdge = false;
   // FIXME - If finding successor is compile time expensive then cache results.
   if (MachineBasicBlock *MBB2 =
           FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
     return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
 
+  // If this instruction is inside a loop and sinking this instruction can make
+  // more registers live range shorten, it is still prifitable.
+  MachineLoop *ML = LI->getLoopFor(MBB);
+  int LiveRangeShortenCount = 0;
+  if (ML) {
+    for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
+      const MachineOperand &MO = MI.getOperand(i);
+      // Ignore non-register operands.
+      if (!MO.isReg())
+        continue;
+      Register Reg = MO.getReg();
+      // Don't handle physical register.
+      if (Reg == 0 || Register::isPhysicalRegister(Reg))
+        return false;
+
+      // Users for the defs are all dominated by SuccToSinkTo.
+      if (MO.isDef()) {
+        // This def register's live range is shortened after sinking.
+        bool LocalUse = false;
+        if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge,
+                                     LocalUse))
+          return false;
+        LiveRangeShortenCount++;
+      } else {
+        MachineInstr *DefMI = MRI->getVRegDef(Reg);
+        // DefMI is defined outside of loop. There should be no live range
+        // impact for this operand. Defination outside of loop means: 
+        // 1: defination is outside of loop.
+        // 2: defination is in this loop, but it is a PHI in the loop header.
+        if (LI->getLoopFor(DefMI->getParent()) != ML ||
+            (DefMI->isPHI() && LI->isLoopHeader(DefMI->getParent())))
+          continue;
+        // DefMI is inside the loop.
+        LiveRangeShortenCount--;
+      }
+    }
+    // If there is no live range shorten number degradation, we treat it as
+    // profitable. Because after sinking all users of one defination inside the
+    // loop, we can also sink the defination later.
+    if (LiveRangeShortenCount >= 0)
+      return true;
+  }
+
   // If SuccToSinkTo is final destination and it is a post dominator of current
   // block then it is not profitable to sink MI into SuccToSinkTo block.
   return false;
 }
 
 /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
 /// computing it if it was not already cached.
 SmallVector<MachineBasicBlock *, 4> &
MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
 
   // Handle cases where sinking can happen but where the sink point isn't a
   // successor. For example:
   //
   //   x = computation
   //   if () {} else {}
   //   use x
   //
   for (MachineDomTreeNode *DTChild : DT->getNode(MBB)->children()) {
     // DomTree children of MBB that have MBB as immediate dominator are added.
     if (DTChild->getIDom()->getBlock() == MI.getParent() &&
         // Skip MBBs already added to the AllSuccs vector above.
         !MBB->isSuccessor(DTChild->getBlock()))
       AllSuccs.push_back(DTChild->getBlock());
   }
 
   // Sort Successors according to their loop depth or block frequency info.

llvm/test/CodeGen/X86/2007-01-13-StackPtrIndex.ll

 ; CHECK-NEXT:    je .LBB0_16
 ; CHECK-NEXT:  .LBB0_1: # %a29b
 ; CHECK-NEXT:    cmpl %r10d, %esi
 ; CHECK-NEXT:    js .LBB0_10
 ; CHECK-NEXT:  # %bb.2: # %b158
 ; CHECK-NEXT:    movslq (%r9), %rsi
 ; CHECK-NEXT:    xorl %edi, %edi
 ; CHECK-NEXT:    xorps %xmm0, %xmm0
-; CHECK-NEXT:    movb $1, %r10b
+; CHECK-NEXT:    movb $1, %r9b
 ; CHECK-NEXT:    jmp .LBB0_3
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_9: # %b1606
 ; CHECK-NEXT:    # in Loop: Header=BB0_3 Depth=1
 ; CHECK-NEXT:    testb %dil, %dil
 ; CHECK-NEXT:    je .LBB0_10
 ; CHECK-NEXT:  .LBB0_3: # %a29b173
 ; CHECK-NEXT:    # =>This Loop Header: Depth=1

 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_37: # %a30b
 ; CHECK-NEXT:    # Parent Loop BB0_3 Depth=1
 ; CHECK-NEXT:    # => This Inner Loop Header: Depth=2
 ; CHECK-NEXT:    testb %dil, %dil
 ; CHECK-NEXT:    je .LBB0_37
 ; CHECK-NEXT:  .LBB0_18: # %b188
 ; CHECK-NEXT:    # in Loop: Header=BB0_3 Depth=1
-; CHECK-NEXT:    testb %r10b, %r10b
+; CHECK-NEXT:    testb %r9b, %r9b
 ; CHECK-NEXT:    jne .LBB0_4
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_19: # %a30b294
 ; CHECK-NEXT:    # Parent Loop BB0_3 Depth=1
 ; CHECK-NEXT:    # => This Inner Loop Header: Depth=2
 ; CHECK-NEXT:    testb %dil, %dil
 ; CHECK-NEXT:    je .LBB0_19
 ; CHECK-NEXT:  .LBB0_4: # %a33b
 ; CHECK-NEXT:    # in Loop: Header=BB0_3 Depth=1
-; CHECK-NEXT:    movl %esi, %eax
-; CHECK-NEXT:    orl %r8d, %eax
-; CHECK-NEXT:    movl %eax, %r9d
-; CHECK-NEXT:    shrl $31, %r9d
-; CHECK-NEXT:    testl %eax, %eax
+; CHECK-NEXT:    movl %esi, %r10d
+; CHECK-NEXT:    orl %r8d, %r10d
 ; CHECK-NEXT:    jns .LBB0_20
 ; CHECK-NEXT:  .LBB0_5: # %a50b
 ; CHECK-NEXT:    # in Loop: Header=BB0_3 Depth=1
+; CHECK-NEXT:    shrl $31, %r10d
 ; CHECK-NEXT:    movl %r8d, %eax
 ; CHECK-NEXT:    orl %esi, %eax
-; CHECK-NEXT:    movl %eax, %r11d
-; CHECK-NEXT:    shrl $31, %r11d
-; CHECK-NEXT:    testl %eax, %eax
 ; CHECK-NEXT:    jns .LBB0_26
 ; CHECK-NEXT:  .LBB0_6: # %a57b
 ; CHECK-NEXT:    # in Loop: Header=BB0_3 Depth=1
-; CHECK-NEXT:    testb %r9b, %r9b
+; CHECK-NEXT:    shrl $31, %eax
+; CHECK-NEXT:    testb %r10b, %r10b
 ; CHECK-NEXT:    je .LBB0_30
 ; CHECK-NEXT:  .LBB0_7: # %a66b
 ; CHECK-NEXT:    # in Loop: Header=BB0_3 Depth=1
-; CHECK-NEXT:    testb %r11b, %r11b
+; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB0_8
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_34: # %a74b
 ; CHECK-NEXT:    # Parent Loop BB0_3 Depth=1
 ; CHECK-NEXT:    # => This Inner Loop Header: Depth=2
 ; CHECK-NEXT:    testb %dil, %dil
 ; CHECK-NEXT:    jne .LBB0_34
 ; CHECK-NEXT:  # %bb.35: # %b1582

 ; CHECK-NEXT:  .LBB0_38: # %a53b
 ; CHECK-NEXT:    # Parent Loop BB0_3 Depth=1
 ; CHECK-NEXT:    # Parent Loop BB0_26 Depth=2
 ; CHECK-NEXT:    # => This Inner Loop Header: Depth=3
 ; CHECK-NEXT:    testb %dil, %dil
 ; CHECK-NEXT:    je .LBB0_38
 ; CHECK-NEXT:  .LBB0_27: # %b879
 ; CHECK-NEXT:    # in Loop: Header=BB0_26 Depth=2
-; CHECK-NEXT:    testb %r10b, %r10b
+; CHECK-NEXT:    testb %r9b, %r9b
 ; CHECK-NEXT:    jne .LBB0_28
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_29: # %a53b1019
 ; CHECK-NEXT:    # Parent Loop BB0_3 Depth=1
 ; CHECK-NEXT:    # Parent Loop BB0_26 Depth=2
 ; CHECK-NEXT:    # => This Inner Loop Header: Depth=3
 ; CHECK-NEXT:    testq %rdx, %rdx
 ; CHECK-NEXT:    jle .LBB0_29