[PowerPC] Fix the liveins for ppc-expand-isel pass

[ZhangKang]

Summary

In the ppc-expand-isel pass, we use stepForward() to update the liveness, this function is not recommended, because it need the accurate kill info.

In fact, we have the function computeAndAddLiveIns(), it will use stepBackward() to update the liveness. It's the recommended method to update the liveins.

I have use the option machine-verifier-strict-livein provided in https://reviews.llvm.org/D78586/ to test this patch.
In the patch D78586, there are 57 PowerPC cases failed, after using this patch, 54 cases can pass, and the left 3 cases should be the cases issue.

[efriedma]

llvm/lib/Target/PowerPC/PPCExpandISEL.cpp

454

Is the clearLiveIns() call necessary? I would have thought that TrueBlock has no liveins set, since you just created it.

[lkail]

llvm/lib/Target/PowerPC/PPCExpandISEL.cpp

390

I notice computeAndAddLiveIns will call stepBackward, this comment says it will lead to cyclic dependence. Is it still the case for current code?

[ZhangKang]

llvm/lib/Target/PowerPC/PPCExpandISEL.cpp

390

If the livenins of successors are right, we can using stepBackward method to calculate the livenins for this MachineBasicBlock.
Here, the successors of MBB are equal the to the successors of NewSuccessor, and the liveins of successors are right for MBB. So we can use stepBackward method to calculate the liveness for NewSuccessor.

454

If there are more than one ISEL for BIL, we will get assert error the TrueBlock has the liveins for last ISEL instruction.
For example:

bb.0.entry:
    liveins: $x4, $x5, $x6, $x7

    renamable $cr0 = CMPWI renamable $r7, 0
    renamable $r3 = ISEL killed renamable $r7, killed renamable $r4, renamable $cr0gt, implicit $x4, implicit $x7
    renamable $r4 = ISEL killed renamable $r5, killed renamable $r6, killed renamable $cr0gt, implicit $cr0, implicit $x6, implicit $x5
    renamable $r3 = nsw ADD4 killed renamable $r3, killed renamable $r4
    renamable $x3 = EXTSW_32_64 killed renamable $r3
    BLR8 implicit $lr8, implicit $rm, implicit killed $x3

We will get:

bb.0.entry:
  successors: %bb.2(0x40000000), %bb.1(0x40000000)
  liveins: $x4, $x5, $x6, $x7

  renamable $cr0 = CMPWI renamable $r7, 0
  BC killed renamable $cr0gt, %bb.2

bb.1.entry:
  successors: %bb.3(0x80000000)
  liveins: $r6, $r4

  renamable $r3 = ORI killed renamable $r4, 0
  renamable $r4 = ORI killed renamable $r6, 0
  B %bb.3

bb.2.entry:
  successors: %bb.3(0x80000000)
  liveins: $r5, $r7

  renamable $r3 = ADDI killed renamable $r7, 0
  renamable $r4 = ADDI killed renamable $r5, 0

bb.3.entry:
  liveins: $r3, $r4

  renamable $r3 = nsw ADD4 killed renamable $r3, killed renamable $r4
  renamable $x3 = EXTSW_32_64 killed renamable $r3
  BLR8 implicit $lr8, implicit $rm, implicit killed $x3

But your comment reminder me that I should calculate the liveins out of the for loop. I will update the patch.

[ZhangKang]

Move update liveins out of for loop.

[lkail]

This comment was removed by lkail.

[lkail]

llvm/lib/Target/PowerPC/PPCExpandISEL.cpp

390

Ok, I get it. The origin implementation

// Copy the original liveIns of MBB to NewSuccessor.

has been problematic. We might have some registers killed before the isel instruction.

llvm/test/CodeGen/PowerPC/expand-isel-liveness.mir

50–80

Could you provide test case that ISEL is the last instruction of a MBB?

[ZhangKang]

llvm/lib/Target/PowerPC/PPCExpandISEL.cpp

390

Only for the special case 1, all registers used by ISEL are the same one, we should care about the killed/dead flag. I think it should be fixed in another patch.

208       // Special case 1, all registers used by ISEL are the same one.
209       // The non-redundant isel 0, 0, 0, N would not satisfy these conditions
210       // as it would be ISEL %R0, %ZERO, %R0, %CRN.
211       if (useSameRegister(Dest, TrueValue) &&
212           useSameRegister(Dest, FalseValue)) {
213         LLVM_DEBUG(dbgs() << "Remove redundant ISEL instruction: " << **I
214                           << "\n");
215         // FIXME: if the CR field used has no other uses, we could eliminate the
216         // instruction that defines it. This would have to be done manually
217         // since this pass runs too late to run DCE after it.
218         NumRemoved++;
219         (*I)->eraseFromParent();
220         I++;

llvm/test/CodeGen/PowerPC/expand-isel-liveness.mir

50–80

Done.

[ZhangKang]

Add a new case whose last MI is ISEL.

[efriedma]

LGTM (but please wait to see if @lkail has further comments)

[lkail]

LGTM. Thanks for fixing it.

llvm/lib/Target/PowerPC/PPCExpandISEL.cpp

if (NewSuccessor) {
     MF->insert(It, NewSuccessor);
 
     // Transfer the rest of this block into the new successor block.
     NewSuccessor->splice(NewSuccessor->end(), MBB,
                          std::next(MachineBasicBlock::iterator(BIL.back())),
                          MBB->end());
     NewSuccessor->transferSuccessorsAndUpdatePHIs(MBB);
 
-    // Copy the original liveIns of MBB to NewSuccessor.
-    for (auto &LI : MBB->liveins())
-      NewSuccessor->addLiveIn(LI);
-
-    // After splitting the NewSuccessor block, Regs defined but not killed
-    // in MBB should be treated as liveins of NewSuccessor.
-    // Note: Cannot use stepBackward instead since we are using the Reg
-    // liveness state at the end of MBB (liveOut of MBB) as the liveIn for
-    // NewSuccessor. Otherwise, will cause cyclic dependence.
-    LivePhysRegs LPR(*MF->getSubtarget<PPCSubtarget>().getRegisterInfo());
-    SmallVector<std::pair<MCPhysReg, const MachineOperand *>, 2> Clobbers;
-    for (MachineInstr &MI : *MBB)
-      LPR.stepForward(MI, Clobbers);
-    for (auto &LI : LPR)
-      NewSuccessor->addLiveIn(LI);
+    // Update the liveins for NewSuccessor.
+    LivePhysRegs LPR;
+    computeAndAddLiveIns(LPR, *NewSuccessor);
+
   } else {
     // Remove successor from MBB.
     MBB->removeSuccessor(Successor);
   }
 
   // Note that this needs to be done *after* transfering the successors from MBB
   // to the NewSuccessor block, otherwise these blocks will also be transferred
   // as successors!
for (auto &MI : BIL) {
     LLVM_DEBUG(dbgs() << "FalseValue: " << FalseValue << "\n");
     LLVM_DEBUG(dbgs() << "ConditionRegister: " << ConditionRegister << "\n");
 
     // If the Dest Register and True Value Register are not the same one, we
     // need the True Block.
     bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
     bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
 
-    if (IsADDIInstRequired) {
-      // Copy the result into the destination if the condition is true.
+    if (IsADDIInstRequired)
       BuildMI(*TrueBlock, TrueBlockI, dl,
               TII->get(isISEL8(*MI) ? PPC::ADDI8 : PPC::ADDI))
           .add(Dest)
           .add(TrueValue)
           .add(MachineOperand::CreateImm(0));
 
-      // Add the LiveIn registers required by true block.
-      TrueBlock->addLiveIn(TrueValue.getReg());
-    }
-
-    if (IsORIInstRequired) {
-      // Add the LiveIn registers required by false block.
-      FalseBlock->addLiveIn(FalseValue.getReg());
-    }
-
-    if (NewSuccessor) {
-      // Add the LiveIn registers required by NewSuccessor block.
-      NewSuccessor->addLiveIn(Dest.getReg());
-      NewSuccessor->addLiveIn(TrueValue.getReg());
-      NewSuccessor->addLiveIn(FalseValue.getReg());
-      NewSuccessor->addLiveIn(ConditionRegister.getReg());
-    }
-
-    // Copy the value into the destination if the condition is false.
+    // Copy the result into the destination if the condition is false.
     if (IsORIInstRequired)
       BuildMI(*FalseBlock, FalseBlockI, dl,
               TII->get(isISEL8(*MI) ? PPC::ORI8 : PPC::ORI))
           .add(Dest)
           .add(FalseValue)
           .add(MachineOperand::CreateImm(0));
 
     MI->eraseFromParent(); // Remove the ISEL instruction.
 
     NumExpanded++;
   }
+
+  if (IsTrueBlockRequired) {
+    // Update the liveins for TrueBlock.
+    LivePhysRegs LPR;
+    computeAndAddLiveIns(LPR, *TrueBlock);
+  }
+
+  if (IsFalseBlockRequired) {
+    // Update the liveins for FalseBlock.
+    LivePhysRegs LPR;
+    computeAndAddLiveIns(LPR, *FalseBlock);
+  }
 }
 
 void PPCExpandISEL::expandMergeableISELs(BlockISELList &BIL) {
   // At this stage all the ISELs of BIL are in the same MBB.
   MachineBasicBlock *MBB = BIL.back()->getParent();
 
   handleSpecialCases(BIL, MBB);
   reorganizeBlockLayout(BIL, MBB);
   populateBlocks(BIL);
 }
 
 INITIALIZE_PASS(PPCExpandISEL, DEBUG_TYPE, "PowerPC Expand ISEL Generation",
                 false, false)
 char PPCExpandISEL::ID = 0;
 
 FunctionPass *llvm::createPPCExpandISELPass() { return new PPCExpandISEL(); }

llvm/test/CodeGen/PowerPC/expand-isel-liveness.mir

bb.0:
     renamable $cr5lt = CRORC killed renamable $cr5lt, killed renamable $cr0eq, implicit $cr0
     renamable $cr5lt = CRNOR killed renamable $cr5lt, killed renamable $cr5gt
     renamable $x4 = MULLD killed renamable $x4, killed renamable $x6
     renamable $x5 = ISEL8 $zero8, killed renamable $x7, killed renamable $cr5lt
     BLR8 implicit $lr8, implicit $rm, implicit killed $x3, implicit killed $x4, implicit killed $x5
 
   ; CHECK-LABEL: name: expand_isel_liveness1
   ; CHECK: bb.1:
-  ; CHECK:   liveins: $x7
+  ; CHECK:   liveins: $x3, $x4, $x7
   ; CHECK:   renamable $x5 = ORI8 killed renamable $x7, 0
   ; CHECK:   B %bb.3
   ; CHECK: bb.2:
-  ; CHECK:   liveins: $zero8
+  ; CHECK:   liveins: $x3, $x4
   ; CHECK:   renamable $x5 = ADDI8 $zero8, 0
   ; CHECK: bb.3:
-  ; CHECK:   liveins: $x3, $x4, $x5, $x6, $cr1lt, $cr1gt, $x3, $cr6lt, $cr0eq, $r3, $cr5un, $cr1eq, $cr1un, $cr6un, $cr0lt, $cr0gt, $cr6gt, $cr0un, $cr1, $cr6, $cr5eq, $x8, $r8, $cr6eq, $x4, $r4, $cr0, $cr5gt, $cr5, $cr5lt, $x7, $r7, $x5, $r5, $x5, $zero8, $x7, $cr5lt
+  ; CHECK:   liveins: $x3, $x4, $x5
   ; CHECK:   BLR8 implicit $lr8, implicit $rm, implicit killed $x3, implicit killed $x4, implicit killed $x5
 ...
 
 ---
 name:            expand_isel_liveness2
 tracksRegLiveness: true
 liveins:
   - { reg: '$r0' }
   - { reg: '$r3' }
 body:             |
   bb.0.entry:
     liveins: $r0, $r3
 
     $r5 = ADDI $r3, 1
     $cr0 = CMPWI $r3, 0
     $r3 = ISEL $zero, killed $r0, killed $cr0gt
 
   ; CHECK-LABEL: name: expand_isel_liveness2
   ; CHECK: bb.0.entry:
   ; CHECK:   liveins: $r0, $r3
   ; CHECK:   $r5 = ADDI $r3, 1
   ; CHECK:   $cr0 = CMPWI $r3, 0
   ; CHECK:   BC killed $cr0gt, %bb.2
   ; CHECK: bb.1.entry:
   ; CHECK:   liveins: $r0
   ; CHECK:   $r3 = ORI killed $r0, 0
   ; CHECK:   B %bb.3
   ; CHECK: bb.2.entry:
-  ; CHECK:   liveins: $zero
+  ; CHECK-NOT:   liveins: $zero
   ; CHECK:   $r3 = ADDI $zero, 0
 ...