[PowerPC] fold addi's imm operand to its imm form consumer's displacement

[shchenz]

Summary

After MachineSink, there will be peephole opportunity for:

%0:g8rc_and_g8rc_nox0 = ADDI8 %5:g8rc_and_g8rc_nox0, 144
STD killed %7:g8rc, 16, %0:g8rc_and_g8rc_nox0 :: (store 8 into %ir.8)

------>

STD killed %7:g8rc, 160, %5:g8rc_and_g8rc_nox0 :: (store 8 into %ir.8)

This folding opportunity may become unfoldable after RA because we may redefine addi's register operand in RA. So we add this peephole before RA in convertToImmediateForm.

First try was implemented in https://reviews.llvm.org/D46377 and the author @nemanjai found out that patch can use some existing logic in later committed patch https://reviews.llvm.org/D49007.

This patch tries to do this.

[steven.zhang]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

2569

What about the IdxOfADDI and IdxOfLI ?

2573

Move the declaration of MITmp to line 2255. And I prefer to use some meaningful name.

2587

Add "break" here and you don't need to check the !OpLI.

2598

I think, you don't need two variables to keep LI and ADDI separate. How about doing it like this:

foreach operands
   if (is_li || is_addi) {
      Inst =  MITmp = MRI->getVRegDef(TrueReg);
      idx = i;
     if (is_li)
         break;
   }

if (Inst) {
   OpNoForForwarding = idx;
   DefMI = Inst;
}

2653

Do we still need to fixup the kill/dead flags if it SSA ?

3874

MI must have x-form opcode.

3904

We will initialize the Imm inside isImmElgibleForForwarding, and you don't need to initialize it with ImmOperandMI

[shchenz]

update according comments:
1: simplify the code logic a little bit.

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

2653

Yes, we need it. kill/dead flags exist even in SSA and machineverify will use these flags to do checking.
Without these fixup, we get LIT case failure.

3904

The Imm initialized in isImmElgibleForForwarding is just for DefMI, here we need the sum of the imm in DefMI and imm in MI.

[steven.zhang]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3904

That’s really not a good idea to sum the imm secretly inside isImmElgibleForForwarding, as what that function does is to check if ImmMO is eligible for forwarding, if yes, extract and set the imm. Can we add another parameter named something like int64_t base which has default initializer as 0, and add some necessary comment for that function?

[shchenz]

address comments:
1: make the imm sum explicit in function isImmElgibleForForwarding

[shchenz]

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3904

agree

[steven.zhang]

LGTM now with one minor nit.

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3906

Don't use the same variable to avoid confusion.

[shchenz]

Thanks for your review.

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

3906

Will update in the commit patch

llvm/lib/Target/PowerPC/PPCInstrInfo.h

void LoadRegFromStackSlot(MachineFunction &MF, const DebugLoc &DL,
                             unsigned DestReg, int FrameIdx,
                             const TargetRegisterClass *RC,
                             SmallVectorImpl<MachineInstr *> &NewMIs) const;
 
   // Replace the instruction with single LI if possible. \p DefMI must be LI or
   // LI8.
   bool simplifyToLI(MachineInstr &MI, MachineInstr &DefMI,
                     unsigned OpNoForForwarding, MachineInstr **KilledDef) const;
+  // If the inst is imm-form and its register operand is produced by a ADDI, put
+  // the imm into the inst directly and remove the ADDI if possible.
+  bool transformToNewImmFormFedByAdd(MachineInstr &MI, MachineInstr &DefMI,
+                                     unsigned OpNoForForwarding) const;
   // If the inst is x-form and has imm-form and one of its operand is produced
   // by a LI, put the imm into the inst directly and remove the LI if possible.
   bool transformToImmFormFedByLI(MachineInstr &MI, const ImmInstrInfo &III,
                                  unsigned ConstantOpNo,
                                  MachineInstr &DefMI) const;
   // If the inst is x-form and has imm-form and one of its operand is produced
   // by an add-immediate, try to transform it when possible.
   bool transformToImmFormFedByAdd(MachineInstr &MI, const ImmInstrInfo &III,
class PPCInstrInfo : public PPCGenInstrInfo {
   bool isUseMIElgibleForForwarding(MachineInstr &MI, const ImmInstrInfo &III,
                                    unsigned OpNoForForwarding) const;
   bool isDefMIElgibleForForwarding(MachineInstr &DefMI,
                                    const ImmInstrInfo &III,
                                    MachineOperand *&ImmMO,
                                    MachineOperand *&RegMO) const;
   bool isImmElgibleForForwarding(const MachineOperand &ImmMO,
                                  const MachineInstr &DefMI,
                                  const ImmInstrInfo &III,
-                                 int64_t &Imm) const;
+                                 int64_t &Imm,
+                                 int64_t BaseImm = 0) const;
   bool isRegElgibleForForwarding(const MachineOperand &RegMO,
                                  const MachineInstr &DefMI,
                                  const MachineInstr &MI, bool KillDefMI,
                                  bool &IsFwdFeederRegKilled) const;
   unsigned getSpillTarget() const;
   const unsigned *getStoreOpcodesForSpillArray() const;
   const unsigned *getLoadOpcodesForSpillArray() const;
   int16_t getFMAOpIdxInfo(unsigned Opcode) const;

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

MachineInstr *PPCInstrInfo::getForwardingDefMI(
   MachineInstr &MI,
   unsigned &OpNoForForwarding,
   bool &SeenIntermediateUse) const {
   OpNoForForwarding = ~0U;
   MachineInstr *DefMI = nullptr;
   MachineRegisterInfo *MRI = &MI.getParent()->getParent()->getRegInfo();
   const TargetRegisterInfo *TRI = &getRegisterInfo();
   // If we're in SSA, get the defs through the MRI. Otherwise, only look
-  // within the basic block to see if the register is defined using an LI/LI8.
+  // within the basic block to see if the register is defined using an
+  // LI/LI8/ADDI/ADDI8.
   if (MRI->isSSA()) {
     for (int i = 1, e = MI.getNumOperands(); i < e; i++) {
       if (!MI.getOperand(i).isReg())
         continue;
       Register Reg = MI.getOperand(i).getReg();
       if (!Register::isVirtualRegister(Reg))
         continue;
       unsigned TrueReg = TRI->lookThruCopyLike(Reg, MRI);
       if (Register::isVirtualRegister(TrueReg)) {
         DefMI = MRI->getVRegDef(TrueReg);
-        if (DefMI->getOpcode() == PPC::LI || DefMI->getOpcode() == PPC::LI8) {
+        if (DefMI->getOpcode() == PPC::LI || DefMI->getOpcode() == PPC::LI8 ||
+            DefMI->getOpcode() == PPC::ADDI ||
+            DefMI->getOpcode() == PPC::ADDI8) {
           OpNoForForwarding = i;
+          // The ADDI and LI operand maybe exist in one instruction at same
+          // time. we prefer to fold LI operand as LI only has one Imm operand
+          // and is more possible to be converted. So if current DefMI is
+          // ADDI/ADDI8, we continue to find possible LI/LI8.
+          if (DefMI->getOpcode() == PPC::LI || DefMI->getOpcode() == PPC::LI8)
             break;
         }
       }
     }
   } else {
     // Looking back through the definition for each operand could be expensive,
     // so exit early if this isn't an instruction that either has an immediate
     // form or is already an immediate form that we can handle.
     ImmInstrInfo III;
     unsigned Opc = MI.getOpcode();
     bool ConvertibleImmForm =
         Opc == PPC::CMPWI || Opc == PPC::CMPLWI || Opc == PPC::CMPDI ||
         Opc == PPC::CMPLDI || Opc == PPC::ADDI || Opc == PPC::ADDI8 ||
         Opc == PPC::ORI || Opc == PPC::ORI8 || Opc == PPC::XORI ||
         Opc == PPC::XORI8 || Opc == PPC::RLDICL || Opc == PPC::RLDICL_rec ||
         Opc == PPC::RLDICL_32 || Opc == PPC::RLDICL_32_64 ||
         Opc == PPC::RLWINM || Opc == PPC::RLWINM_rec || Opc == PPC::RLWINM8 ||
         Opc == PPC::RLWINM8_rec;
     bool IsVFReg = (MI.getNumOperands() && MI.getOperand(0).isReg())
                        ? isVFRegister(MI.getOperand(0).getReg())

 }
 
 const unsigned *PPCInstrInfo::getLoadOpcodesForSpillArray() const {
   return LoadSpillOpcodesArray[getSpillTarget()];
 }
 
 void PPCInstrInfo::fixupIsDeadOrKill(MachineInstr &StartMI, MachineInstr &EndMI,
                                      unsigned RegNo) const {
-  const MachineRegisterInfo &MRI =
-      StartMI.getParent()->getParent()->getRegInfo();
-  if (MRI.isSSA())
-    return;
 
   // Instructions between [StartMI, EndMI] should be in same basic block.
   assert((StartMI.getParent() == EndMI.getParent()) &&
          "Instructions are not in same basic block");
 
   bool IsKillSet = false;
 
   auto clearOperandKillInfo = [=] (MachineInstr &MI, unsigned Index) {
if (!DefMI)
     return false;
   assert(ForwardingOperand < MI.getNumOperands() &&
          "The forwarding operand needs to be valid at this point");
   bool IsForwardingOperandKilled = MI.getOperand(ForwardingOperand).isKill();
   bool KillFwdDefMI = !SeenIntermediateUse && IsForwardingOperandKilled;
   if (KilledDef && KillFwdDefMI)
     *KilledDef = DefMI;
 
+  // If this is a imm instruction and its register operands is produced by ADDI,
+  // put the imm into imm inst directly.
+  if (RI.getMappedIdxOpcForImmOpc(MI.getOpcode()) !=
+          PPC::INSTRUCTION_LIST_END &&
+      transformToNewImmFormFedByAdd(MI, *DefMI, ForwardingOperand))
+    return true;
+
   ImmInstrInfo III;
   bool IsVFReg = MI.getOperand(0).isReg()
                      ? isVFRegister(MI.getOperand(0).getReg())
                      : false;
   bool HasImmForm = instrHasImmForm(MI.getOpcode(), IsVFReg, III, PostRA);
   // If this is a reg+reg instruction that has a reg+imm form,
   // and one of the operands is produced by an add-immediate,
   // try to convert it.
bool PPCInstrInfo::isDefMIElgibleForForwarding(MachineInstr &DefMI,
   if (Opc != PPC::ADDItocL && Opc != PPC::ADDI && Opc != PPC::ADDI8)
     return false;
 
   assert(DefMI.getNumOperands() >= 3 &&
          "Add inst must have at least three operands");
   RegMO = &DefMI.getOperand(1);
   ImmMO = &DefMI.getOperand(2);
 
+  // Before RA, ADDI first operand could be a frame index.
+  if (!RegMO->isReg())
+    return false;
+
   // This DefMI is elgible for forwarding if it is:
   // 1. add inst
   // 2. one of the operands is Imm/CPI/Global.
   return isAnImmediateOperand(*ImmMO);
 }
 
 bool PPCInstrInfo::isRegElgibleForForwarding(
     const MachineOperand &RegMO, const MachineInstr &DefMI,
if (DefMI.modifiesRegister(Reg, &getRegisterInfo()))
     return KillDefMI;
 
   return true;
 }
 
 bool PPCInstrInfo::isImmElgibleForForwarding(const MachineOperand &ImmMO,
                                              const MachineInstr &DefMI,
                                              const ImmInstrInfo &III,
-                                             int64_t &Imm) const {
+                                             int64_t &Imm,
+                                             int64_t BaseImm) const {
   assert(isAnImmediateOperand(ImmMO) && "ImmMO is NOT an immediate");
   if (DefMI.getOpcode() == PPC::ADDItocL) {
     // The operand for ADDItocL is CPI, which isn't imm at compiling time,
     // However, we know that, it is 16-bit width, and has the alignment of 4.
     // Check if the instruction met the requirement.
     if (III.ImmMustBeMultipleOf > 4 ||
        III.TruncateImmTo || III.ImmWidth != 16)
       return false;
 
     // Going from XForm to DForm loads means that the displacement needs to be
     // not just an immediate but also a multiple of 4, or 16 depending on the
     // load. A DForm load cannot be represented if it is a multiple of say 2.
     // XForm loads do not have this restriction.
     if (ImmMO.isGlobal() &&
         ImmMO.getGlobal()->getAlignment() < III.ImmMustBeMultipleOf)
       return false;
 
     return true;
   }
 
   if (ImmMO.isImm()) {
     // It is Imm, we need to check if the Imm fit the range.
-    int64_t Immediate = ImmMO.getImm();
     // Sign-extend to 64-bits.
-    Imm = ((uint64_t)Immediate & ~0x7FFFuLL) != 0 ?
-      (Immediate | 0xFFFFFFFFFFFF0000) : Immediate;
+    // DefMI may be folded with another imm form instruction, the result Imm is
+    // the sum of Imm of DefMI and BaseImm which is from imm form instruction.
+    Imm = SignExtend64<16>(ImmMO.getImm() + BaseImm);
 
     if (Imm % III.ImmMustBeMultipleOf)
       return false;
     if (III.TruncateImmTo)
       Imm &= ((1 << III.TruncateImmTo) - 1);
     if (III.SignedImm) {
       APInt ActualValue(64, Imm, true);
       if (!ActualValue.isSignedIntN(III.ImmWidth))
if (ReplaceWithLI) {
 
     LLVM_DEBUG(dbgs() << "With:\n");
     LLVM_DEBUG(MI.dump());
     return true;
   }
   return false;
 }
 
+bool PPCInstrInfo::transformToNewImmFormFedByAdd(
+    MachineInstr &MI, MachineInstr &DefMI, unsigned OpNoForForwarding) const {
+  MachineRegisterInfo *MRI = &MI.getParent()->getParent()->getRegInfo();
+  bool PostRA = !MRI->isSSA();
+  // FIXME: extend this to post-ra. Need to do some change in getForwardingDefMI
+  // for post-ra.
+  if (PostRA)
+    return false;
+
+  // Only handle load/store.
+  if (!MI.mayLoadOrStore())
+    return false;
+
+  unsigned XFormOpcode = RI.getMappedIdxOpcForImmOpc(MI.getOpcode());
+
+  assert((XFormOpcode != PPC::INSTRUCTION_LIST_END) &&
+         "MI must have x-form opcode");
+
+  // get Imm Form info.
+  ImmInstrInfo III;
+  bool IsVFReg = MI.getOperand(0).isReg()
+                     ? isVFRegister(MI.getOperand(0).getReg())
+                     : false;
+
+  if (!instrHasImmForm(XFormOpcode, IsVFReg, III, PostRA))
+    return false;
+
+  if (!III.IsSummingOperands)
+    return false;
+
+  if (OpNoForForwarding != III.OpNoForForwarding)
+    return false;
+
+  MachineOperand ImmOperandMI = MI.getOperand(III.ImmOpNo);
+  if (!ImmOperandMI.isImm())
+    return false;
+
+  // Check DefMI.
+  MachineOperand *ImmMO = nullptr;
+  MachineOperand *RegMO = nullptr;
+  if (!isDefMIElgibleForForwarding(DefMI, III, ImmMO, RegMO))
+    return false;
+  assert(ImmMO && RegMO && "Imm and Reg operand must have been set");
+
+  // Check Imm.
+  // Set Imm from imm instruction as base and get new Imm inside
+  // isImmElgibleForForwarding.
+  int64_t Imm = ImmOperandMI.getImm();
+  if (!isImmElgibleForForwarding(*ImmMO, DefMI, III, Imm, Imm))
+    return false;
+
+  // Get killed info in case fixup needed after transformation.
+  unsigned ForwardKilledOperandReg = ~0U;
+  if (MI.getOperand(III.OpNoForForwarding).isKill())
+    ForwardKilledOperandReg = MI.getOperand(III.OpNoForForwarding).getReg();
+
+  // Do the transform
+  LLVM_DEBUG(dbgs() << "Replacing instruction:\n");
+  LLVM_DEBUG(MI.dump());
+  LLVM_DEBUG(dbgs() << "Fed by:\n");
+  LLVM_DEBUG(DefMI.dump());
+
+  MI.getOperand(III.OpNoForForwarding).setReg(RegMO->getReg());
+  MI.getOperand(III.OpNoForForwarding).setIsKill(RegMO->isKill());
+  MI.getOperand(III.ImmOpNo).setImm(Imm);
+
+  // FIXME: fix kill/dead flag if MI and DefMI are not in same basic block.
+  if (DefMI.getParent() == MI.getParent()) {
+    // Check if reg is killed between MI and DefMI.
+    auto IsKilledFor = [&](unsigned Reg) {
+      MachineBasicBlock::const_reverse_iterator It = MI;
+      MachineBasicBlock::const_reverse_iterator E = DefMI;
+      It++;
+      for (; It != E; ++It) {
+        if (It->killsRegister(Reg))
+          return true;
+      }
+      return false;
+    };
+
+    // Update kill flag
+    if (RegMO->isKill() || IsKilledFor(RegMO->getReg()))
+      fixupIsDeadOrKill(DefMI, MI, RegMO->getReg());
+    if (ForwardKilledOperandReg != ~0U)
+      fixupIsDeadOrKill(DefMI, MI, ForwardKilledOperandReg);
+  }
+
+  LLVM_DEBUG(dbgs() << "With:\n");
+  LLVM_DEBUG(MI.dump());
+  return true;
+}
+
 // If an X-Form instruction is fed by an add-immediate and one of its operands
 // is the literal zero, attempt to forward the source of the add-immediate to
 // the corresponding D-Form instruction with the displacement coming from
 // the immediate being added.
 bool PPCInstrInfo::transformToImmFormFedByAdd(
     MachineInstr &MI, const ImmInstrInfo &III, unsigned OpNoForForwarding,
     MachineInstr &DefMI, bool KillDefMI) const {
   //         RegMO ImmMO

llvm/test/CodeGen/PowerPC/convert-ri-addi-to-ri.mir

+# RUN: llc -mtriple=powerpc64le-unknown-linux-gnu -verify-machineinstrs \
+# RUN:   -run-pass ppc-mi-peepholes -ppc-convert-rr-to-ri %s -o - | FileCheck %s
+
+---
+name: foldNewDformStore
+# CHECK: name: foldNewDformStore
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    liveins: $x3
+
+    %0:g8rc_and_g8rc_nox0 = COPY $x3
+    %1:g8rc_and_g8rc_nox0 = ADDI8 %0:g8rc_and_g8rc_nox0, 144
+    %2:g8rc = LI8 0
+    ; CHECK: STD killed %2, 160, %0
+    STD killed %2:g8rc, 16, %1:g8rc_and_g8rc_nox0
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name: foldNewDformStoreAlignNotMatch
+# CHECK: name: foldNewDformStoreAlignNotMatch
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    liveins: $x3
+
+    %0:g8rc_and_g8rc_nox0 = COPY $x3
+    %1:g8rc_and_g8rc_nox0 = ADDI8 %0:g8rc_and_g8rc_nox0, 141
+    %2:g8rc = LI8 0
+    ; CHECK: STD killed %2, 16, %1
+    STD killed %2:g8rc, 16, %1:g8rc_and_g8rc_nox0
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name: foldNewDformStoreKilledFlag
+# CHECK: name: foldNewDformStoreKilledFlag
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    liveins: $x3
+
+    %0:g8rc_and_g8rc_nox0 = COPY $x3
+    %1:g8rc_and_g8rc_nox0 = ADDI8 %0:g8rc_and_g8rc_nox0, 144
+    %2:g8rc = LI8 0
+    ; CHECK: STD %1, 0, %0
+    STD %1:g8rc_and_g8rc_nox0, 0, killed %0:g8rc_and_g8rc_nox0
+    ; CHECK: STD killed %2, 160, killed %0
+    STD killed %2:g8rc, 16, %1:g8rc_and_g8rc_nox0
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name: foldNewDformPreferLIOperand
+# CHECK: name: foldNewDformPreferLIOperand
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+  liveins: $x3
+  %0:g8rc_and_g8rc_nox0 = COPY $x3
+  %1:g8rc = ADDI8 %0:g8rc_and_g8rc_nox0, 1
+  %2:g8rc = LI8 1
+  ; CHECK: SUBFIC8 killed %1, 1, implicit-def $carry
+  %3:g8rc = SUBFC8 killed %1:g8rc, %2:g8rc, implicit-def $carry
+  %4:g8rc = SUBFE8 %2:g8rc, %2:g8rc, implicit-def dead $carry, implicit $carry
+  %5:g8rc = NEG8 killed %4:g8rc
+  $x3 = COPY %5:g8rc
+  BLR8 implicit $lr8, implicit $rm, implicit $x3
+...