[MachineLICM] Take regmasks into account for register pressure

[djasper]

Summary

This depends on http://reviews.llvm.org/D8986.

As far as I can tell, the changes in the tests make sense.

[qcolombet]

lib/CodeGen/MachineLICM.cpp

865

You may use BitVector::find_first and BitVector::find_next to avoid testing if i is in Clobbers.

865

You can assert i is a physical register.

868

I do not get why you need this test.

test/CodeGen/Mips/prevent-hoisting.ll

27

I am not sure I get the diff here.
What happens exactly?

Looks like we do not hoist some stuff, which seems fine based on the comment on the test.

test/CodeGen/X86/2008-10-27-CoalescerBug.ll

2

Two things here:

1. Based on the comment of the original test, it seems spilling was better. Could you double check the diff.
2. Try to use FileCheck instead of grep.

[djasper]

lib/CodeGen/MachineLICM.cpp

868

So, from what I understand (from the observed behavior is that the regmask will contain super-registers together with all their subregisters, because in fact all of them are clobbered. However, both the super register and it's subregisters count towards the same register pressure sets and thus looking at any sub-register at all makes us over-estimate the pressure in certain register sets. This checks restricts us to only take register with have no super-register into account

test/CodeGen/Mips/prevent-hoisting.ll

27

The difference is this:

The new version is:

1. BB#5: lw $22, %got(assignSE2partition)($2) $BB0_6: # =>This Inner Loop Header: Depth=1 sll $1, $17, 4 sll $2, $17, 6 addu $1, $2, $1 addu $1, $22, $1

So, sll and addu remain in the inner loop body ($BB0_6). Without this patch, the get hoisted to BB#5.

test/CodeGen/X86/2008-10-27-CoalescerBug.ll

2

So, this basically reverts the test to where it was before r116845. That patch introduced the behavior but (if the comment is right) for the wrong reason. If the instruction is cheaper than a spill reload, that should actually be handled through a different code path.

[qcolombet]

lib/CodeGen/MachineLICM.cpp

868

Ah, that makes sense.
Add a comment to explain that.

test/CodeGen/Mips/prevent-hoisting.ll

27

Does this save us some spill?

Otherwise, it does not sound like an improvement :).

test/CodeGen/X86/2008-10-27-CoalescerBug.ll

2

Interesting.
That's fine then.

lib/CodeGen/MachineLICM.cpp

private:
     void HoistOutOfLoop(MachineDomTreeNode *LoopHeaderNode);
     void HoistRegion(MachineDomTreeNode *N, bool IsHeader);
 
     /// SinkIntoLoop - Sink instructions into loops if profitable. This
     /// especially tries to prevent register spills caused by register pressure
     /// if there is little to no overhead moving instructions into loops.
     void SinkIntoLoop();
 
-    /// InitRegPressure - Find all virtual register references that are liveout
-    /// of the preheader to initialize the starting "register pressure". Note
-    /// this does not count live through (livein but not used) registers.
-    void InitRegPressure(MachineBasicBlock *BB);
+    /// InitRegPressure - Initialize the register pressure estimation for the
+    /// current loop.
+    void InitRegPressure();
+
+    /// InitRegPressureWithLiveOuts - Find all virtual register references that
+    /// are liveout of the preheader to initialize the starting "register
+    /// pressure". Note this does not count live through (livein but not used)
+    /// registers.
+    void InitRegPressureWithLiveOuts(MachineBasicBlock *BB);
 
     /// calcRegisterCost - Calculate the additional register pressure that the
     /// registers used in MI cause.
     ///
     /// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to
     /// figure out which usages are live-ins.
     /// FIXME: Figure out a way to consider 'RegSeen' from all code paths.
     DenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI,
for (int i = (int)NumChildren-1; i >= 0; --i) {
       ParentMap[Child] = Node;
       WorkList.push_back(Child);
     }
   }
 
   if (Scopes.size() == 0)
     return;
 
-  // Compute registers which are livein into the loop headers.
-  RegSeen.clear();
-  BackTrace.clear();
-  InitRegPressure(Preheader);
+  InitRegPressure();
 
   // Now perform LICM.
   for (unsigned i = 0, e = Scopes.size(); i != e; ++i) {
     MachineDomTreeNode *Node = Scopes[i];
     MachineBasicBlock *MBB = Node->getBlock();
 
     EnterScope(MBB);
 
for (MachineInstr *I : Candidates) {
     B->splice(B->getFirstNonPHI(), Preheader, I);
   }
 }
 
 static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) {
   return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg());
 }
 
-/// InitRegPressure - Find all virtual register references that are liveout of
-/// the preheader to initialize the starting "register pressure". Note this
-/// does not count live through (livein but not used) registers.
-void MachineLICM::InitRegPressure(MachineBasicBlock *BB) {
+/// InitRegPressure - Initialize the register pressure estimation for the
+/// current loop.
+void MachineLICM::InitRegPressure() {
+  MachineBasicBlock *Preheader = getCurPreheader();
+  if (!Preheader)
+    return;
+
+  // Compute registers which are livein into the loop headers.
+  RegSeen.clear();
+  BackTrace.clear();
+  InitRegPressureWithLiveOuts(Preheader);
+
+  // Compute registers which are clobbered somewhere in the loop.
+  BitVector Clobbers(TRI->getNumRegs());
+  for (MachineBasicBlock *BB : CurLoop->getBlocks()) {
+    for (const MachineInstr &MI : *BB) {
+      for (const MachineOperand &MO : MI.operands()) {
+        if (MO.isRegMask())
+          Clobbers.setBitsNotInMask(MO.getRegMask());
+      }
+    }
+  }
+
+  for (unsigned i = 0, e = Clobbers.size(); i != e; ++i) {
+    if (!Clobbers.test(i) || !TRI->isPhysicalRegister(i) ||
+        !TRI->isInAllocatableClass(i))
+      continue;
+    if (MCSuperRegIterator(i, TRI).isValid())
+      continue;
+    const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(i);
+    RegClassWeight W = TRI->getRegClassWeight(RC);
+    const int *PS = TRI->getRegClassPressureSets(RC);
+    for (; *PS != -1; ++PS)
+      RegPressure[*PS] += W.RegWeight;
+  }
+}
+
+/// InitRegPressureWithLiveOuts - Find all virtual register references that are
+/// liveout of the preheader to initialize the starting "register pressure".
+/// Note this does not count live through (livein but not used) registers.
+void MachineLICM::InitRegPressureWithLiveOuts(MachineBasicBlock *BB) {
   std::fill(RegPressure.begin(), RegPressure.end(), 0);
 
   // If the preheader has only a single predecessor and it ends with a
   // fallthrough or an unconditional branch, then scan its predecessor for live
   // defs as well. This happens whenever the preheader is created by splitting
   // the critical edge from the loop predecessor to the loop header.
   if (BB->pred_size() == 1) {
     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
     SmallVector<MachineOperand, 4> Cond;
     if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty())
-      InitRegPressure(*BB->pred_begin());
+      InitRegPressureWithLiveOuts(*BB->pred_begin());
   }
 
   for (const MachineInstr &MI : *BB)
     UpdateRegPressure(&MI, /*ConsiderUnseenAsDef=*/true);
 }
 
 /// UpdateRegPressure - Update estimate of register pressure after the
 /// specified instruction.

test/CodeGen/Mips/prevent-hoisting.ll

 
 ; The check for first "addiu" instruction is added so that we can match the correct "b" instruction.
 ; CHECK:           addiu ${{[0-9]+}}, $zero, -1
 ; CHECK:           b $[[BB0:BB[0-9_]+]]
 ; CHECK-NEXT:      addiu ${{[0-9]+}}, $zero, 0
 
 ; Check that at the start of a fallthrough block there is a instruction that writes to $1.
 ; CHECK-NEXT:  {{BB[0-9_#]+}}: 
-; CHECK-NEXT:      lw      $[[R1:[0-9]+]], %got(assignSE2partition)($[[R2:[0-9]+]])
+; CHECK-NEXT:      lw      ${{[0-9]+}}, %got(assignSE2partition)($[[R2:[0-9]+]])
+; CHECK-NEXT:  {{BB[0-9_#]+}}: 
 ; CHECK-NEXT:      sll $1, $[[R0:[0-9]+]], 4
 
 ; Check that identical instructions are at the start of a target block.
 ; CHECK:       [[BB0]]:
-; CHECK-NEXT:      lw      $[[R1]], %got(assignSE2partition)($[[R2]])
+; CHECK-NEXT:      lw      ${{[0-9]+}}, %got(assignSE2partition)($[[R2]])
+; CHECK-NEXT:  {{BB[0-9_#]+}}: 
 ; CHECK-NEXT:      sll $1, $[[R0]], 4
 
 
 %struct.img_par = type { i32, i32, i32, i32, i32*, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [16 x [16 x i16]], [6 x [32 x i32]], [16 x [16 x i32]], [4 x [12 x [4 x [4 x i32]]]], [16 x i32], i8**, i32*, i32***, i32**, i32, i32, i32, i32, %struct.Slice*, %struct.macroblock*, i32, i32, i32, i32, i32, i32, %struct.DecRefPicMarking_s*, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [3 x i32], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32***, i32***, i32****, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [3 x [2 x i32]], [3 x [2 x i32]], i32, i32, i32, i32, %struct.timeb, %struct.timeb, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32 }
 %struct.Slice = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, %struct.datapartition*, %struct.MotionInfoContexts*, %struct.TextureInfoContexts*, i32, i32*, i32*, i32*, i32, i32*, i32*, i32*, i32 (%struct.img_par*, %struct.inp_par*)*, i32, i32, i32, i32 }
 %struct.datapartition = type { %struct.Bitstream*, %struct.DecodingEnvironment, i32 (%struct.syntaxelement*, %struct.img_par*, %struct.datapartition*)* }
 %struct.Bitstream = type { i32, i32, i32, i32, i8*, i32 }
 %struct.DecodingEnvironment = type { i32, i32, i32, i32, i32, i8*, i32* }

test/CodeGen/X86/2008-10-27-CoalescerBug.ll

 ; REQUIRES: asserts
-; RUN: llc < %s -mtriple=i386-apple-darwin -mattr=+sse2 -stats 2>&1 | FileCheck %s
-; Now this test spills one register. But a reload in the loop is cheaper than
-; the divsd so it's a win.
+; RUN: llc < %s -mtriple=i386-apple-darwin -mattr=+sse2 -stats 2>&1 | not grep "Number of spills inserted"
 
 define fastcc void @fourn(double* %data, i32 %isign) nounwind {
-; CHECK: fourn
 entry:
   br label %bb
 
 bb:   ; preds = %bb, %entry
   %indvar93 = phi i32 [ 0, %entry ], [ %idim.030, %bb ]    ; <i32> [#uses=2]
   %idim.030 = add i32 %indvar93, 1    ; <i32> [#uses=1]
   %0 = add i32 %indvar93, 2   ; <i32> [#uses=1]
   %1 = icmp sgt i32 %0, 2    ; <i1> [#uses=1]
   br i1 %1, label %bb30.loopexit, label %bb
 
-; CHECK: %bb30.loopexit
-; CHECK: divsd %xmm0
-; CHECK: movsd %xmm0, 16(%esp)
-; CHECK: %bb3
 bb3:    ; preds = %bb30.loopexit, %bb25, %bb3
   %2 = load i32, i32* null, align 4    ; <i32> [#uses=1]
   %3 = mul i32 %2, 0    ; <i32> [#uses=1]
   %4 = icmp slt i32 0, %3    ; <i1> [#uses=1]
   br i1 %4, label %bb18, label %bb3
 
 bb18:   ; preds = %bb3
   %5 = fdiv double %11, 0.000000e+00    ; <double> [#uses=1]

test/CodeGen/X86/licm-regpressure.ll

 ; RUN: llc < %s -mtriple=x86_64-linux | FileCheck %s
-; This tests currently fails as MachineLICM does not compute register pressure
-; correctly. More details: llvm.org/PR23143
-; XFAIL: *
 
 ; MachineLICM should take register pressure into account.
 ; CHECK-NOT: Spill
 
 %struct.A = type { i32, i32, i32, i32, i32, i32, i32 }
 
 define void @test(i1 %b, %struct.A* %a) nounwind {
 entry:
   br label %loop-header
 
 loop-header:
   br label %loop-body
 
 loop-body:
   %0 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 0
-  %1 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 1
-  %2 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 2
-  %3 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 3
-  %4 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 4
-  %5 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 5
-  %6 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 6
   call void @assign(i32* %0)
+  %1 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 1
   call void @assign(i32* %1)
+  %2 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 2
   call void @assign(i32* %2)
+  %3 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 3
   call void @assign(i32* %3)
+  %4 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 4
   call void @assign(i32* %4)
+  %5 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 5
   call void @assign(i32* %5)
+  %6 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 6
   call void @assign(i32* %6)
   br i1 %b, label %loop-body, label %loop-exit
 
 loop-exit:
   ret void
 }
 
 declare void @assign(i32*)