[SystemZ] Improve emitSelect()

[jonpa]

Summary

Merge more Select pseudo instructions in emitSelect() by allowing other instructions between them as long as they do not clobber CC.

[jonpa]

Tried to make some more tests in multiselect.ll to cover merging of Select pseudos. Trunk fails on @test1.

At least at the moment, the DAG->DAG output/finalize-isel input is having the machine instructions in a corresponding order to the LLVM I/R ones (the MDBR in @test1 is really in between the two SelectF64 instructions). Would it be better to do .mir tests and just test the emitSelect() output by doing '-run-pass=finalize-isel'? That way we would have full control over input to emitSelect() and check its output directly.

[jonpa]

Put 'NextMIIt->getOperand(3).getImm() == CCValid' in an assert instead since this must be true.

Avoid name clash with argument 'MI' by using the name 'SelMI' instead in for loop.

Save DBG_VALUE instructions that use a Select pseudo in a vector and move them to after the new PHI nodes. In docs/SourceLevelDebugging.rst, there is an example (under "Instruction Scheduling") of moving down a definition would require keeping the original DBG_VALUE instruction but setting it to undefined, while creating a new DBG_VALUE following the sunk instruction. This does not seem to be done by e.g. MachineSink, which merely moves the DBG_VALUE down...

debuginstr-02.mir test updated to also check that the DBG_VALUE instructions are moved (and not deleted).

[uweigand]

This looks quite good to me, just a couple of (more or less cosmetic) comments inline.

lib/Target/SystemZ/SystemZISelLowering.cpp

6568–6569

Comment needs to be updated.

6615

Why do this here? I think it would be more straightforward for the caller to delete those, like it did before. (Or else, the function comment/name should be updated.)

6662

It would seem clearer to check for isDebugValue outside the loop -- that characteristic is loop-invariant here. Then you wouldn't need the IsDbg flag either.

[jonpa]

Thanks for review - patch updated.

Now also checking for *any* debug instruction. Currently this would mean also recognizing a debug label, which I am not sure if might be present here, but it should not be using any Select pseudo value.

lib/Target/SystemZ/SystemZISelLowering.cpp

6615

My idea was to only iterate over the Selects once, but I suppose that may make the call to createPHIsForSelects() less natural.

6662

Good point, thanks.

I also made sure that any debug instruction will not interfere with Count, while expecting that a debug instruction that uses a select must be a debug value (currently there could perhaps also be debug labels).

[uweigand]

LGTM, thanks!

[jonpa]

Thanks for review!
r372873

lib/Target/SystemZ/SystemZISelLowering.cpp

static bool isSelectPseudo(MachineInstr &MI) {
   default:
     return false;
   }
 }
 
 // Helper function, which inserts PHI functions into SinkMBB:
 //   %Result(i) = phi [ %FalseValue(i), FalseMBB ], [ %TrueValue(i), TrueMBB ],
 // where %FalseValue(i) and %TrueValue(i) are taken from the consequent Selects
 // in [MIItBegin, MIItEnd) range.
-static void createPHIsForSelects(MachineBasicBlock::iterator MIItBegin,
-                                 MachineBasicBlock::iterator MIItEnd,
+static void createPHIsForSelects(SmallVector<MachineInstr*, 8> &Selects,
                                  MachineBasicBlock *TrueMBB,
                                  MachineBasicBlock *FalseMBB,
                                  MachineBasicBlock *SinkMBB) {
   MachineFunction *MF = TrueMBB->getParent();
   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
 
-  unsigned CCValid = MIItBegin->getOperand(3).getImm();
-  unsigned CCMask = MIItBegin->getOperand(4).getImm();
-  DebugLoc DL = MIItBegin->getDebugLoc();
+  MachineInstr *FirstMI = Selects.front();
+  unsigned CCValid = FirstMI->getOperand(3).getImm();
+  unsigned CCMask = FirstMI->getOperand(4).getImm();
 
   MachineBasicBlock::iterator SinkInsertionPoint = SinkMBB->begin();
 
   // As we are creating the PHIs, we have to be careful if there is more than
   // one.  Later Selects may reference the results of earlier Selects, but later
   // PHIs have to reference the individual true/false inputs from earlier PHIs.
   // That also means that PHI construction must work forward from earlier to
   // later, and that the code must maintain a mapping from earlier PHI's
   // destination registers, and the registers that went into the PHI.
   DenseMap<unsigned, std::pair<unsigned, unsigned>> RegRewriteTable;
 
-  for (MachineBasicBlock::iterator MIIt = MIItBegin; MIIt != MIItEnd;
-       MIIt = skipDebugInstructionsForward(++MIIt, MIItEnd)) {
-    Register DestReg = MIIt->getOperand(0).getReg();
-    Register TrueReg = MIIt->getOperand(1).getReg();
-    Register FalseReg = MIIt->getOperand(2).getReg();
+  for (auto MI : Selects) {
+    Register DestReg = MI->getOperand(0).getReg();
+    Register TrueReg = MI->getOperand(1).getReg();
+    Register FalseReg = MI->getOperand(2).getReg();
 
     // If this Select we are generating is the opposite condition from
     // the jump we generated, then we have to swap the operands for the
     // PHI that is going to be generated.
-    if (MIIt->getOperand(4).getImm() == (CCValid ^ CCMask))
+    if (MI->getOperand(4).getImm() == (CCValid ^ CCMask))
       std::swap(TrueReg, FalseReg);
 
     if (RegRewriteTable.find(TrueReg) != RegRewriteTable.end())
       TrueReg = RegRewriteTable[TrueReg].first;
 
     if (RegRewriteTable.find(FalseReg) != RegRewriteTable.end())
       FalseReg = RegRewriteTable[FalseReg].second;
 
+    DebugLoc DL = MI->getDebugLoc();
     BuildMI(*SinkMBB, SinkInsertionPoint, DL, TII->get(SystemZ::PHI), DestReg)
       .addReg(TrueReg).addMBB(TrueMBB)
       .addReg(FalseReg).addMBB(FalseMBB);
 
     // Add this PHI to the rewrite table.
     RegRewriteTable[DestReg] = std::make_pair(TrueReg, FalseReg);
+
+    MI->eraseFromParent();
   }
 
   MF->getProperties().reset(MachineFunctionProperties::Property::NoPHIs);
 }
 
 // Implement EmitInstrWithCustomInserter for pseudo Select* instruction MI.
 MachineBasicBlock *
 SystemZTargetLowering::emitSelect(MachineInstr &MI,
                                   MachineBasicBlock *MBB) const {
+  assert(isSelectPseudo(MI) && "Bad call to emitSelect()");
   const SystemZInstrInfo *TII =
       static_cast<const SystemZInstrInfo *>(Subtarget.getInstrInfo());
 
   unsigned CCValid = MI.getOperand(3).getImm();
   unsigned CCMask = MI.getOperand(4).getImm();
-  DebugLoc DL = MI.getDebugLoc();
 
   // If we have a sequence of Select* pseudo instructions using the
   // same condition code value, we want to expand all of them into
   // a single pair of basic blocks using the same condition.
-  MachineInstr *LastMI = &MI;
-  MachineBasicBlock::iterator NextMIIt = skipDebugInstructionsForward(
+  SmallVector<MachineInstr*, 8> Selects;
+  Selects.push_back(&MI);
+  unsigned Count = 0;
+  for (MachineBasicBlock::iterator NextMIIt = skipDebugInstructionsForward(
            std::next(MachineBasicBlock::iterator(MI)), MBB->end());
-
-  if (isSelectPseudo(MI))
-    while (NextMIIt != MBB->end() && isSelectPseudo(*NextMIIt) &&
-           NextMIIt->getOperand(3).getImm() == CCValid &&
-           (NextMIIt->getOperand(4).getImm() == CCMask ||
-            NextMIIt->getOperand(4).getImm() == (CCValid ^ CCMask))) {
-      LastMI = &*NextMIIt;
-      NextMIIt = skipDebugInstructionsForward(++NextMIIt, MBB->end());
-    }
+       NextMIIt != MBB->end();
+       NextMIIt = skipDebugInstructionsForward(++NextMIIt, MBB->end())) {
+    if (NextMIIt->definesRegister(SystemZ::CC))
+      break;
+    if (isSelectPseudo(*NextMIIt)) {
+      if (NextMIIt->getOperand(3).getImm() == CCValid &&
+        Selects.push_back(&*NextMIIt);
+        continue;
+      }
+      break;
+    }
+    bool User = false;
+    for (auto MI : Selects)
+      if (NextMIIt->readsVirtualRegister(MI->getOperand(0).getReg())) {
+        User = true;
+        break;
+      }
+    if (User || ++Count > 20)
+      break;
 
+  MachineInstr *LastMI = Selects.back();
+  bool CCKilled =
+      (LastMI->killsRegister(SystemZ::CC) || checkCCKill(*LastMI, MBB));
   MachineBasicBlock *StartMBB = MBB;
-  MachineBasicBlock *JoinMBB  = splitBlockBefore(MI, MBB);
+  MachineBasicBlock *JoinMBB  = splitBlockAfter(LastMI, MBB);
   MachineBasicBlock *FalseMBB = emitBlockAfter(StartMBB);
 
   // Unless CC was killed in the last Select instruction, mark it as
   // live-in to both FalseMBB and JoinMBB.
-  if (!LastMI->killsRegister(SystemZ::CC) && !checkCCKill(*LastMI, JoinMBB)) {
+  if (!CCKilled) {
     FalseMBB->addLiveIn(SystemZ::CC);
     JoinMBB->addLiveIn(SystemZ::CC);
   }
 
   //  StartMBB:
   //   BRC CCMask, JoinMBB
   //   # fallthrough to FalseMBB
   MBB = StartMBB;
-  BuildMI(MBB, DL, TII->get(SystemZ::BRC))
+  BuildMI(MBB, MI.getDebugLoc(), TII->get(SystemZ::BRC))
     .addImm(CCValid).addImm(CCMask).addMBB(JoinMBB);
   MBB->addSuccessor(JoinMBB);
   MBB->addSuccessor(FalseMBB);
 
   //  FalseMBB:
   //   # fallthrough to JoinMBB
   MBB = FalseMBB;
   MBB->addSuccessor(JoinMBB);
 
   //  JoinMBB:
   //   %Result = phi [ %FalseReg, FalseMBB ], [ %TrueReg, StartMBB ]
   //  ...
   MBB = JoinMBB;
-  MachineBasicBlock::iterator MIItBegin = MachineBasicBlock::iterator(MI);
-  MachineBasicBlock::iterator MIItEnd = skipDebugInstructionsForward(
-      std::next(MachineBasicBlock::iterator(LastMI)), MBB->end());
-  createPHIsForSelects(MIItBegin, MIItEnd, StartMBB, FalseMBB, MBB);
+  createPHIsForSelects(Selects, StartMBB, FalseMBB, MBB);
 
-  StartMBB->erase(MIItBegin, MIItEnd);
   return JoinMBB;
 }
 
 // Implement EmitInstrWithCustomInserter for pseudo CondStore* instruction MI.
 // StoreOpcode is the store to use and Invert says whether the store should
 // happen when the condition is false rather than true.  If a STORE ON
 // CONDITION is available, STOCOpcode is its opcode, otherwise it is 0.
 MachineBasicBlock *SystemZTargetLowering::emitCondStore(MachineInstr &MI,

test/CodeGen/SystemZ/fp-strict-conv-10.ll

 declare i32 @llvm.experimental.constrained.fptoui.i32.f64(double, metadata)
 declare i32 @llvm.experimental.constrained.fptoui.i32.f128(fp128, metadata)
 
 ; Test f32->i32.
 define i32 @f1(float %f) {
 ; CHECK-LABEL: f1:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    larl %r1, .LCPI0_0
-; CHECK-NEXT:    le %f2, 0(%r1)
-; CHECK-NEXT:    ler %f1, %f0
-; CHECK-NEXT:    sebr %f1, %f2
-; CHECK-NEXT:    cebr %f0, %f2
+; CHECK-NEXT:    le %f1, 0(%r1)
+; CHECK-NEXT:    cebr %f0, %f1
+; CHECK-NEXT:    lhi %r0, 0
 ; CHECK-NEXT:    jl .LBB0_2
 ; CHECK-NEXT:  # %bb.1:
-; CHECK-NEXT:    ler %f0, %f1
-; CHECK-NEXT:  .LBB0_2:
-; CHECK-NEXT:    lhi %r0, 0
-; CHECK-NEXT:    jl .LBB0_4
-; CHECK-NEXT:  # %bb.3:
+; CHECK-NEXT:    sebr %f0, %f1
 ; CHECK-NEXT:    llilh %r0, 32768
-; CHECK-NEXT:  .LBB0_4:
+; CHECK-NEXT:  .LBB0_2:
 ; CHECK-NEXT:    cfebr %r2, 5, %f0
 ; CHECK-NEXT:    xr %r2, %r0
 ; CHECK-NEXT:    br %r14
   %conv = call i32 @llvm.experimental.constrained.fptoui.i32.f32(float %f,
                                                metadata !"fpexcept.strict")
   ret i32 %conv
 }
 
 ; Test f64->i32.
 define i32 @f2(double %f) {
 ; CHECK-LABEL: f2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    larl %r1, .LCPI1_0
-; CHECK-NEXT:    ldeb %f2, 0(%r1)
-; CHECK-NEXT:    ldr %f1, %f0
-; CHECK-NEXT:    sdbr %f1, %f2
-; CHECK-NEXT:    cdbr %f0, %f2
+; CHECK-NEXT:    ldeb %f1, 0(%r1)
+; CHECK-NEXT:    cdbr %f0, %f1
+; CHECK-NEXT:    lhi %r0, 0
 ; CHECK-NEXT:    jl .LBB1_2
 ; CHECK-NEXT:  # %bb.1:
-; CHECK-NEXT:    ldr %f0, %f1
-; CHECK-NEXT:  .LBB1_2:
-; CHECK-NEXT:    lhi %r0, 0
-; CHECK-NEXT:    jl .LBB1_4
-; CHECK-NEXT:  # %bb.3:
+; CHECK-NEXT:    sdbr %f0, %f1
 ; CHECK-NEXT:    llilh %r0, 32768
-; CHECK-NEXT:  .LBB1_4:
+; CHECK-NEXT:  .LBB1_2:
 ; CHECK-NEXT:    cfdbr %r2, 5, %f0
 ; CHECK-NEXT:    xr %r2, %r0
 ; CHECK-NEXT:    br %r14
   %conv = call i32 @llvm.experimental.constrained.fptoui.i32.f64(double %f,
                                                metadata !"fpexcept.strict")
   ret i32 %conv
 }
 
 ; Test f128->i32.
 define i32 @f3(fp128 *%src) {
 ; CHECK-LABEL: f3:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    ld %f0, 0(%r2)
 ; CHECK-NEXT:    ld %f2, 8(%r2)
 ; CHECK-NEXT:    larl %r1, .LCPI2_0
-; CHECK-NEXT:    lxeb %f4, 0(%r1)
-; CHECK-NEXT:    lxr %f1, %f0
-; CHECK-NEXT:    sxbr %f1, %f4
-; CHECK-NEXT:    cxbr %f0, %f4
+; CHECK-NEXT:    lxeb %f1, 0(%r1)
+; CHECK-NEXT:    cxbr %f0, %f1
+; CHECK-NEXT:    lhi %r0, 0
 ; CHECK-NEXT:    jl .LBB2_2
 ; CHECK-NEXT:  # %bb.1:
-; CHECK-NEXT:    lxr %f0, %f1
-; CHECK-NEXT:  .LBB2_2:
-; CHECK-NEXT:    lhi %r0, 0
-; CHECK-NEXT:    jl .LBB2_4
-; CHECK-NEXT:  # %bb.3:
+; CHECK-NEXT:    sxbr %f0, %f1
 ; CHECK-NEXT:    llilh %r0, 32768
-; CHECK-NEXT:  .LBB2_4:
+; CHECK-NEXT:  .LBB2_2:
 ; CHECK-NEXT:    cfxbr %r2, 5, %f0
 ; CHECK-NEXT:    xr %r2, %r0
 ; CHECK-NEXT:    br %r14
   %f = load fp128, fp128 *%src
   %conv = call i32 @llvm.experimental.constrained.fptoui.i32.f128(fp128 %f,
                                                metadata !"fpexcept.strict")
   ret i32 %conv
 }

test/CodeGen/SystemZ/fp-strict-conv-12.ll

 declare i64 @llvm.experimental.constrained.fptoui.i64.f64(double, metadata)
 declare i64 @llvm.experimental.constrained.fptoui.i64.f128(fp128, metadata)
 
 ; Test f32->i64.
 define i64 @f1(float %f) {
 ; CHECK-LABEL: f1:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    larl %r1, .LCPI0_0
-; CHECK-NEXT:    le %f2, 0(%r1)
-; CHECK-NEXT:    ler %f1, %f0
-; CHECK-NEXT:    sebr %f1, %f2
-; CHECK-NEXT:    cebr %f0, %f2
+; CHECK-NEXT:    le %f1, 0(%r1)
+; CHECK-NEXT:    cebr %f0, %f1
+; CHECK-NEXT:    lghi %r0, 0
 ; CHECK-NEXT:    jl .LBB0_2
 ; CHECK-NEXT:  # %bb.1:
-; CHECK-NEXT:    ler %f0, %f1
-; CHECK-NEXT:  .LBB0_2:
-; CHECK-NEXT:    lghi %r0, 0
-; CHECK-NEXT:    jl .LBB0_4
-; CHECK-NEXT:  # %bb.3:
+; CHECK-NEXT:    sebr %f0, %f1
 ; CHECK-NEXT:    llihh %r0, 32768
-; CHECK-NEXT:  .LBB0_4:
+; CHECK-NEXT:  .LBB0_2:
 ; CHECK-NEXT:    cgebr %r2, 5, %f0
 ; CHECK-NEXT:    xgr %r2, %r0
 ; CHECK-NEXT:    br %r14
   %conv = call i64 @llvm.experimental.constrained.fptoui.i64.f32(float %f,
                                                metadata !"fpexcept.strict")
   ret i64 %conv
 }
 
 ; Test f64->i64.
 define i64 @f2(double %f) {
 ; CHECK-LABEL: f2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    larl %r1, .LCPI1_0
-; CHECK-NEXT:    ldeb %f2, 0(%r1)
-; CHECK-NEXT:    ldr %f1, %f0
-; CHECK-NEXT:    sdbr %f1, %f2
-; CHECK-NEXT:    cdbr %f0, %f2
+; CHECK-NEXT:    ldeb %f1, 0(%r1)
+; CHECK-NEXT:    cdbr %f0, %f1
+; CHECK-NEXT:    lghi %r0, 0
 ; CHECK-NEXT:    jl .LBB1_2
 ; CHECK-NEXT:  # %bb.1:
-; CHECK-NEXT:    ldr %f0, %f1
-; CHECK-NEXT:  .LBB1_2:
-; CHECK-NEXT:    lghi %r0, 0
-; CHECK-NEXT:    jl .LBB1_4
-; CHECK-NEXT:  # %bb.3:
+; CHECK-NEXT:    sdbr %f0, %f1
 ; CHECK-NEXT:    llihh %r0, 32768
-; CHECK-NEXT:  .LBB1_4:
+; CHECK-NEXT:  .LBB1_2:
 ; CHECK-NEXT:    cgdbr %r2, 5, %f0
 ; CHECK-NEXT:    xgr %r2, %r0
 ; CHECK-NEXT:    br %r14
   %conv = call i64 @llvm.experimental.constrained.fptoui.i64.f64(double %f,
                                                metadata !"fpexcept.strict")
   ret i64 %conv
 }
 
 ; Test f128->i64.
 define i64 @f3(fp128 *%src) {
 ; CHECK-LABEL: f3:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    ld %f0, 0(%r2)
 ; CHECK-NEXT:    ld %f2, 8(%r2)
 ; CHECK-NEXT:    larl %r1, .LCPI2_0
-; CHECK-NEXT:    lxeb %f4, 0(%r1)
-; CHECK-NEXT:    lxr %f1, %f0
-; CHECK-NEXT:    sxbr %f1, %f4
-; CHECK-NEXT:    cxbr %f0, %f4
+; CHECK-NEXT:    lxeb %f1, 0(%r1)
+; CHECK-NEXT:    cxbr %f0, %f1
+; CHECK-NEXT:    lghi %r0, 0
 ; CHECK-NEXT:    jl .LBB2_2
 ; CHECK-NEXT:  # %bb.1:
-; CHECK-NEXT:    lxr %f0, %f1
-; CHECK-NEXT:  .LBB2_2:
-; CHECK-NEXT:    lghi %r0, 0
-; CHECK-NEXT:    jl .LBB2_4
-; CHECK-NEXT:  # %bb.3:
+; CHECK-NEXT:    sxbr %f0, %f1
 ; CHECK-NEXT:    llihh %r0, 32768
-; CHECK-NEXT:  .LBB2_4:
+; CHECK-NEXT:  .LBB2_2:
 ; CHECK-NEXT:    cgxbr %r2, 5, %f0
 ; CHECK-NEXT:    xgr %r2, %r0
 ; CHECK-NEXT:    br %r14
   %f = load fp128, fp128 *%src
   %conv = call i64 @llvm.experimental.constrained.fptoui.i64.f128(fp128 %f,
                                                metadata !"fpexcept.strict")
   ret i64 %conv
 }

test/CodeGen/SystemZ/multiselect.ll

 ; Test that multiple select statements using the same condition are expanded
-; into a single conditional branch.
+; into a single conditional branch when possible.
 ;
-; RUN: llc < %s -mtriple=s390x-linux-gnu | FileCheck %s
+; RUN: llc < %s -mtriple=s390x-linux-gnu -disable-block-placement | FileCheck %s
 
-define void @test(i32 signext %positive, double %base, double %offset, double* %rmin, double* %rmax) {
+define void @test0(i32 signext %positive, double %base, double %offset, double* %rmin, double* %rmax) {
 entry:
+; CHECK-LABEL: test0
 ; CHECK: cijlh %r2, 0,
 ; CHECK-NOT: cij
 ; CHECK-NOT: je
 ; CHECK-NOT: jlh
 
   %tobool = icmp eq i32 %positive, 0
   %add = fadd double %base, %offset
   %min = select i1 %tobool, double %add, double %base
   %max = select i1 %tobool, double %base, double %add
   store double %min, double* %rmin, align 8
   store double %max, double* %rmax, align 8
   ret void
 }
 
+; Two selects with an intervening instruction that doesn't clobber CC can
+; still be merged.
+define double @test1(i32 signext %positive, double %A, double %B, double %C) {
+entry:
+; CHECK-LABEL: test1
+; CHECK: cijhe {{.*}}LBB1_2
+; CHECK-NOT: cij
+; CHECK: br %r14
+
+  %tobool = icmp slt i32 %positive, 0
+  %s1  = select i1 %tobool, double %A, double %B
+  %mul = fmul double %A, %B
+  %s2  = select i1 %tobool, double %B, double %C
+  %add = fadd double %s1, %s2
+  %add2 = fadd double %add, %mul
+  ret double %add2
+}
+
+; Two selects with an intervening user of the first select can't be merged.
+define double @test2(i32 signext %positive, double %A, double %B) {
+entry:
+; CHECK-LABEL: test2
+; CHECK: cije {{.*}}LBB2_2
+; CHECK: cibe {{.*}}%r14
+; CHECK: br %r14
+
+  %tobool = icmp eq i32 %positive, 0
+  %s1  = select i1 %tobool, double %A, double %B
+  %add = fadd double %A, %s1
+  %s2  = select i1 %tobool, double %A, double %add
+  ret double %s2
+}
+
+; Two selects with different conditions can't be merged
+define double @test3(i32 signext %positive, double %A, double %B, double %C) {
+entry:
+; CHECK-LABEL: test3
+; CHECK: cijl {{.*}}LBB3_2
+; CHECK: cijl {{.*}}LBB3_4
+; CHECK: br %r14
+
+  %tobool = icmp slt i32 %positive, 0
+  %s1  = select i1 %tobool, double %A, double %B
+  %tobool2 = icmp slt i32 %positive, 2
+  %s2  = select i1 %tobool2, double %B, double %C
+  %add = fadd double %s1, %s2
+  ret double %add
+}