[PowerPC] eliminate partially redundant compare instruction

[inouehrs]

Summary

This is a follow-on of D37211.

D37211 eliminates a compare instruction if two conditional branches can be made based on the one compare instruction, e.g.

if (a == 0) { ... }
else if (a < 0) { ... }

This patch extends this optimization to support partially redundant cases, which often happen in while loops.
For example, one compare instruction is moved from the loop body into the preheader by this optimization in the following example.

do {
  if (a == 0) dummy1();
  a = func(a);
} while (a > 0);

[hfinkel]

lib/Target/PowerPC/PPCMIPeephole.cpp

571

I'm not sure how this full-copy case would come up, unless:

1. The source or destination is a physical register (but we bail out in that case)
2. The source or destination have different register classes
3. This is run after PHI elimination (which this pass is not)

I can't think of a case where (2) would come up (we don't have different register classes for GPRs, except for r0 restrictions, but I believe there we just end up with one vreg with a union register class).

I short, unless you've seen this in practice, I recommend not handling it at all.

616

Please remove the parentheses here.

640

I'm okay with this, but we shouldn't have nothing in the braces. A comment is okay.

702

another -> additional

918

Space after first <<.

[inouehrs]

lib/Target/PowerPC/PPCMIPeephole.cpp

571

Disabling this full-copy case reduces the number of eliminated compares by about 1% during the bootstrap (23483 -> 23191), although I have not investigated which optimizer generates COPYs.

616

I think we cannot eliminate the parentheses of lambda.

640

I added comment to avoid empty block.

702

Fixed.

918

Fixed.

[hfinkel]

LGTM

lib/Target/PowerPC/PPCMIPeephole.cpp

571

Okay.

616

I think that you can just write:

return BB.succ_size() == 1;

640

containing compare -> containing the compare

641

the BB we will -> the BB to which we will

lib/Target/PowerPC/PPCMIPeephole.cpp

static unsigned getPredicateToIncImm(MachineInstr *BI, MachineInstr *CMPI) {
   if (PredCond == PPC::PRED_GT)
     return PPC::getPredicate(PPC::PRED_GE, PredHint);
   if (PredCond == PPC::PRED_LE)
     return PPC::getPredicate(PPC::PRED_LT, PredHint);
 
   return 0;
 }
 
+// This takes a Phi node and returns a register value for the spefied BB.
+static unsigned getIncomingRegForBlock(MachineInstr *Phi,
+                                       MachineBasicBlock *MBB) {
+  for (unsigned I = 2, E = Phi->getNumOperands() + 1; I != E; I += 2) {
+    MachineOperand &MO = Phi->getOperand(I);
+    if (MO.getMBB() == MBB)
+      return Phi->getOperand(I-1).getReg();
+  }
+  llvm_unreachable("invalid src basic block for this Phi node\n");
+  return 0;
+}
+
+// This function tracks the source of the register through register copy.
+// If BB1 and BB2 are non-NULL, we also track PHI instruction in BB2
+// assuming that the control comes from BB1 into BB2.
+static unsigned getSrcVReg(unsigned Reg, MachineBasicBlock *BB1,
+                           MachineBasicBlock *BB2, MachineRegisterInfo *MRI) {
+  unsigned SrcReg = Reg;
+  while (1) {
+    unsigned NextReg = SrcReg;
+    MachineInstr *Inst = MRI->getVRegDef(SrcReg);
+    if (BB1 && Inst->getOpcode() == PPC::PHI && Inst->getParent() == BB2) {
+      NextReg = getIncomingRegForBlock(Inst, BB1);
+      // We track through PHI only once to avoid infinite loop.
+      BB1 = nullptr;
+    }
+    else if (Inst->isFullCopy())
+      NextReg = Inst->getOperand(1).getReg();
+    if (NextReg == SrcReg || !TargetRegisterInfo::isVirtualRegister(NextReg))
+      break;
+    SrcReg = NextReg;
+  }
+  return SrcReg;
+}
+
 static bool eligibleForCompareElimination(MachineBasicBlock &MBB,
+                                          MachineBasicBlock *&PredMBB,
+                                          MachineBasicBlock *&MBBtoMoveCmp,
                                           MachineRegisterInfo *MRI) {
 
   auto isEligibleBB = [&](MachineBasicBlock &BB) {
     auto BII = BB.getFirstInstrTerminator();
     // We optimize BBs ending with a conditional branch.
     // We check only for BCC here, not BCCLR, because BCCLR
     // will be formed only later in the pipeline. 
     if (BB.succ_size() == 2 &&
if (BB.succ_size() == 2 &&
         if (MO.isReg() && !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
           return false;
 
       return true;
     }
     return false;
   };
 
-  if (MBB.pred_size() != 1)
+  auto isEligibleForMoveCmp = [](MachineBasicBlock &BB) {
+    // If this BB has more than one successor, we can create a new BB and
+    // move the compare instruction in the new BB.
+    // So far, we do not move compare instruction to a BB having multiple
+    // successors to avoid potentially increasing code size.
+    return (BB.succ_size() == 1);
+  };
+
+  if (!isEligibleBB(MBB))
+    return false;
+
+  unsigned NumPredBBs = MBB.pred_size();
+  if (NumPredBBs == 1) {
+    MachineBasicBlock *TmpMBB = *MBB.pred_begin();
+    if (isEligibleBB(*TmpMBB)) {
+      PredMBB = TmpMBB;
+      MBBtoMoveCmp = nullptr;
+      return true;
+    }
+  }
+  else if (NumPredBBs == 2) {
+    // We check for partially redundant case.
+    // So far, we support cases with only two predecessors
+    // to avoid increasing the number of instructions.
+    MachineBasicBlock::pred_iterator PI = MBB.pred_begin();
+    MachineBasicBlock *Pred1MBB = *PI;
+    MachineBasicBlock *Pred2MBB = *(PI+1);
+
+    if (isEligibleBB(*Pred1MBB) && isEligibleForMoveCmp(*Pred2MBB)) {
+    }
+    else if (isEligibleBB(*Pred2MBB) && isEligibleForMoveCmp(*Pred1MBB)) {
+      std::swap(Pred1MBB, Pred2MBB);
+    }
+    else return false;
+
+    // Here, Pred2MBB is a BB we need to append a compare instruction.
+    // We cannot move the compare instruction if operands are not available
+    // in Pred2MBB (i.e. defined in MBB by an instruction other than PHI).
+    MachineInstr *BI = &*MBB.getFirstInstrTerminator();
+    MachineInstr *CMPI = MRI->getVRegDef(BI->getOperand(1).getReg());
+    for (int I = 1; I <= 2; I++)
+      if (CMPI->getOperand(I).isReg()) {
+        MachineInstr *Inst = MRI->getVRegDef(CMPI->getOperand(I).getReg());
+        if (Inst->getParent() == &MBB && Inst->getOpcode() != PPC::PHI)
           return false;
+      }
 
-  MachineBasicBlock *PredMBB = *MBB.pred_begin();
-  if (isEligibleBB(MBB) && isEligibleBB(*PredMBB))
+    PredMBB = Pred1MBB;
+    MBBtoMoveCmp = Pred2MBB;
     return true;
+  }
 
   return false;
 }
 
 // If multiple conditional branches are executed based on the (essentially)
 // same comparison, we merge compare instructions into one and make multiple
 // conditional branches on this comparison.
 // For example,

 //   beq    0, .LBB0_3
 //   cmpwi  r3, 0       ; greather than -1 means greater or equal to 0
 //   bge    0, .LBB0_4
 
 bool PPCMIPeephole::eliminateRedundantCompare(void) {
   bool Simplified = false;
 
   for (MachineBasicBlock &MBB2 : *MF) {
-    // We only consider two basic blocks MBB1 and MBB2 if
+    MachineBasicBlock *MBB1 = nullptr, *MBBtoMoveCmp = nullptr;
+
+    // For fully redundant case, we select two basic blocks MBB1 and MBB2
+    // as an optimization target if
     // - both MBBs end with a conditional branch,
     // - MBB1 is the only predecessor of MBB2, and
     // - compare does not take a physical register as a operand in both MBBs.
-    if (!eligibleForCompareElimination(MBB2, MRI))
+    // In this case, eligibleForCompareElimination sets MBBtoMoveCmp nullptr.
+    //
+    // As partially redundant case, we additionally handle if MBB2 has one
+    // another predecessor, which has only one successor (MBB2).
+    // In this case, we move the compre instruction originally in MBB2 into
+    // MBBtoMoveCmp. This partially redundant case is typically appear by
+    // compiling a while loop; here, MBBtoMoveCmp is the loop preheader.
+    //
+    // Overview of CFG of related basic blocks
+    // Fully redundant case        Partially redundant case
+    //   --------                   ----------------  --------
+    //   | MBB1 | (w/ 2 succ)       | MBBtoMoveCmp |  | MBB1 | (w/ 2 succ)
+    //   --------                   ----------------  --------
+    //      |    \                     (w/ 1 succ) \     |    \
+    //      |     \                                 \    |     \
+    //      |                                        \   |
+    //   --------                                     --------
+    //   | MBB2 | (w/ 1 pred                          | MBB2 | (w/ 2 pred
+    //   -------- and 2 succ)                         -------- and 2 succ)
+    //      |    \                                       |    \
+    //      |     \                                      |     \
+    //
+    if (!eligibleForCompareElimination(MBB2, MBB1, MBBtoMoveCmp, MRI))
       continue;
 
-    MachineBasicBlock *MBB1 = *MBB2.pred_begin();
     MachineInstr *BI1   = &*MBB1->getFirstInstrTerminator();
     MachineInstr *CMPI1 = MRI->getVRegDef(BI1->getOperand(1).getReg());
 
     MachineInstr *BI2   = &*MBB2.getFirstInstrTerminator();
     MachineInstr *CMPI2 = MRI->getVRegDef(BI2->getOperand(1).getReg());
+    bool IsPartiallyRedundant = (MBBtoMoveCmp != nullptr);
 
     // We cannot optimize an unsupported compare opcode or
     // a mix of 32-bit and 64-bit comaprisons
     if (!isSupportedCmpOp(CMPI1->getOpcode()) ||
         !isSupportedCmpOp(CMPI2->getOpcode()) ||
         is64bitCmpOp(CMPI1->getOpcode()) != is64bitCmpOp(CMPI2->getOpcode()))
       continue;
 
     unsigned NewOpCode = 0;
     unsigned NewPredicate1 = 0, NewPredicate2 = 0;
     int16_t Imm1 = 0, NewImm1 = 0, Imm2 = 0, NewImm2 = 0;
+    bool SwapOperands = false;
 
     if (CMPI1->getOpcode() != CMPI2->getOpcode()) {
       // Typically, unsigned comparison is used for equality check, but
       // we replace it with a signed comparison if the comparison
       // to be merged is a signed comparison.
       // In other cases of opcode mismatch, we cannot optimize this.
       if (isEqOrNe(BI2) &&
           CMPI1->getOpcode() == getSignedCmpOpCode(CMPI2->getOpcode()))
         NewOpCode = CMPI1->getOpcode();
       else if (isEqOrNe(BI1) &&
                getSignedCmpOpCode(CMPI1->getOpcode()) == CMPI2->getOpcode())
         NewOpCode = CMPI2->getOpcode();
       else continue;
     }
 
     if (CMPI1->getOperand(2).isReg() && CMPI2->getOperand(2).isReg()) {
       // In case of comparisons between two registers, these two registers
       // must be same to merge two comparisons.
-      unsigned Cmp1Operand1 = CMPI1->getOperand(1).getReg();
-      unsigned Cmp1Operand2 = CMPI1->getOperand(2).getReg();
-      unsigned Cmp2Operand1 = CMPI2->getOperand(1).getReg();
-      unsigned Cmp2Operand2 = CMPI2->getOperand(2).getReg();
+      unsigned Cmp1Operand1 = getSrcVReg(CMPI1->getOperand(1).getReg(),
+                                         nullptr, nullptr, MRI);
+      unsigned Cmp1Operand2 = getSrcVReg(CMPI1->getOperand(2).getReg(),
+                                         nullptr, nullptr, MRI);
+      unsigned Cmp2Operand1 = getSrcVReg(CMPI2->getOperand(1).getReg(),
+                                         MBB1, &MBB2, MRI);
+      unsigned Cmp2Operand2 = getSrcVReg(CMPI2->getOperand(2).getReg(),
+                                         MBB1, &MBB2, MRI);
+
       if (Cmp1Operand1 == Cmp2Operand1 && Cmp1Operand2 == Cmp2Operand2) {
         // Same pair of registers in the same order; ready to merge as is.
       }
       else if (Cmp1Operand1 == Cmp2Operand2 && Cmp1Operand2 == Cmp2Operand1) {
         // Same pair of registers in different order.
         // We reverse the predicate to merge compare instructions.
         PPC::Predicate Pred = (PPC::Predicate)BI2->getOperand(0).getImm();
         NewPredicate2 = (unsigned)PPC::getSwappedPredicate(Pred);
+        // In case of partial redundancy, we need to swap operands
+        // in another compare instruction.
+        SwapOperands = true;
       }
       else continue;
     }
     else if (CMPI1->getOperand(2).isImm() && CMPI2->getOperand(2).isImm()){
       // In case of comparisons between a register and an immediate,
       // the operand register must be same for two compare instructions.
-      if (CMPI1->getOperand(1).getReg() != CMPI2->getOperand(1).getReg())
+      unsigned Cmp1Operand1 = getSrcVReg(CMPI1->getOperand(1).getReg(),
+                                         nullptr, nullptr, MRI);
+      unsigned Cmp2Operand1 = getSrcVReg(CMPI2->getOperand(1).getReg(),
+                                         MBB1, &MBB2, MRI);
+      if (Cmp1Operand1 != Cmp2Operand1)
         continue;
 
       NewImm1 = Imm1 = (int16_t)CMPI1->getOperand(2).getImm();
       NewImm2 = Imm2 = (int16_t)CMPI2->getOperand(2).getImm();
 
       // If immediate are not same, we try to adjust by changing predicate;
       // e.g. GT imm means GE (imm+1).
       if (Imm1 != Imm2 && (!isEqOrNe(BI2) || !isEqOrNe(BI1))) {
for (MachineBasicBlock &MBB2 : *MF) {
     }
     if (NewPredicate2) {
       BI2->getOperand(0).setImm(NewPredicate2);
     }
     if (NewImm1 != Imm1) {
       CMPI1->getOperand(2).setImm(NewImm1);
     }
 
+    if (IsPartiallyRedundant) {
+      // We touch up the compare instruction in MBB2 and move it to
+      // a previous BB to handle partially redundant case.
+      if (SwapOperands) {
+        unsigned Op1 = CMPI2->getOperand(1).getReg();
+        unsigned Op2 = CMPI2->getOperand(2).getReg();
+        CMPI2->getOperand(1).setReg(Op2);
+        CMPI2->getOperand(2).setReg(Op1);
+      }
+      if (NewImm2 != Imm2) {
+        CMPI2->getOperand(2).setImm(NewImm2);
+      }
+      for (int I = 1; I <= 2; I++) {
+        if (CMPI2->getOperand(I).isReg()) {
+          MachineInstr *Inst = MRI->getVRegDef(CMPI2->getOperand(I).getReg());
+          if (Inst->getParent() != &MBB2)
+            continue;
+
+          assert(Inst->getOpcode() == PPC::PHI &&
+                 "We cannot support if an operand comes from this BB.");
+          unsigned SrcReg = getIncomingRegForBlock(Inst, MBBtoMoveCmp);
+          CMPI2->getOperand(I).setReg(SrcReg);
+        }
+      }
+      auto I = MachineBasicBlock::iterator(MBBtoMoveCmp->getFirstTerminator());
+      MBBtoMoveCmp->splice(I, &MBB2, MachineBasicBlock::iterator(CMPI2));
+
+      DebugLoc DL = CMPI2->getDebugLoc();
+      unsigned NewVReg = MRI->createVirtualRegister(&PPC::CRRCRegClass);
+      BuildMI(MBB2, MBB2.begin(), DL,
+              TII->get(PPC::PHI), NewVReg)
+        .addReg(BI1->getOperand(1).getReg()).addMBB(MBB1)
+        .addReg(BI2->getOperand(1).getReg()).addMBB(MBBtoMoveCmp);
+      BI2->getOperand(1).setReg(NewVReg);
+    }
+    else {
       // We finally eliminate compare instruction in MBB2.
       BI2->getOperand(1).setReg(BI1->getOperand(1).getReg());
+      CMPI2->eraseFromParent();
+    }
     BI2->getOperand(1).setIsKill(true);
     BI1->getOperand(1).setIsKill(false);
-    CMPI2->eraseFromParent();
 
     DEBUG(dbgs() << "into a compare and two branches:\n");
     DEBUG(CMPI1->dump());
     DEBUG(BI1->dump());
     DEBUG(BI2->dump());
+    if (IsPartiallyRedundant) {
+      DEBUG(dbgs() <<"The following compare is moved into BB#" <<
+            MBBtoMoveCmp->getNumber() << " to handle partial redundancy.\n");
+      DEBUG(CMPI2->dump());
+    }
 
     Simplified = true;
   }
 
   return Simplified;
 }
 
 // This is used to find the "true" source register for an

test/CodeGen/PowerPC/cmp_elimination.ll

if.end3.sink.split:
   %g2.sink = phi i32* [ @g2, %if.else ], [ @g1, %entry ]
   store i32 0, i32* %g2.sink, align 4
   br label %if.end
 
 if.end:
   ret void
 }
 
+; partially redundant case
+define void @func28(i32 signext %a) {
+; CHECK-LABEL: @func28
+; CHECK: cmplwi  [[REG1:[0-9]+]], [[REG2:[0-9]+]]
+; CHECK: .[[LABEL1:[A-Z0-9_]+]]:
+; CHECK-NOT: cmp
+; CHECK: bne   0, .[[LABEL2:[A-Z0-9_]+]]
+; CHECK: bl dummy1
+; CHECK: .[[LABEL2]]:
+; CHECK: cmpwi   [[REG1]], [[REG2]]
+; CHECK: bgt   0, .[[LABEL1]]
+; CHECK: blr
+entry:
+  br label %do.body
+
+do.body:
+  %a.addr.0 = phi i32 [ %a, %entry ], [ %call, %if.end ]
+  %cmp = icmp eq i32 %a.addr.0, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  tail call void @dummy1() #2
+  br label %if.end
+
+if.end:
+  %call = tail call signext i32 @func(i32 signext %a.addr.0) #2
+  %cmp1 = icmp sgt i32 %call, 0
+  br i1 %cmp1, label %do.body, label %do.end
+
+do.end:
+  ret void
+}
+
 declare void @dummy1()
 declare void @dummy2()
 declare void @dummy3()
+declare signext i32 @func(i32 signext)
 
 !1 = !{!"branch_weights", i32 2000, i32 1}
 !2 = !{!"branch_weights", i32 1, i32 2000}