[RISCV] Eagerly delete instructions in MergeBaseOffset.

[craig.topper]

Summary

The only iterator we're holding points to HiLUI and we never
delete that so I think it is safe to delete everything else
immediately.

I want to split detectAndFoldOffset into two phases. First, combine
LUI+ADDI with any ADD/ADDI/SHXADD that comes after it. This may
open opportunities to fold the ADDI from the LUI+ADDI into a
load/store address. So the load/store folding should run as a
second phase even if the ADD/ADDI/SHXADD made changes.

In order to do this we need to eagerly delete instructions in the
first phase so that we don't have dead users of the LUI+ADDI
when we start the second phase.

Patches to split the phases will come later.

[asb]

The change seems functionally correct to me, and the reasoning for the change makes sense. I think the comments for each modified function just need to be updated.

llvm/lib/Target/RISCV/RISCVMergeBaseOffset.cpp

70–72

Comment needs updating to reflect this mutates the MBB rather than just detecting the pattern

134–136

Comment needs updating to reflect this mutates the MBB rather than just detecting the pattern

209

Comment needs updating to reflect this mutates the MBB rather than just detecting the pattern

[craig.topper]

Update comments

[craig.topper]

llvm/lib/Target/RISCV/RISCVMergeBaseOffset.cpp

70–72

This code didn't get updated so I think it is still correct.

[craig.topper]

Ping

[luismarques]

LGTM.

PS: This is going to force me to rebase D123265 again, though... :(

[luismarques]

@craig.topper Thanks for helping push D123265 through. I can rebase this for you if you want, it seems easier than the other way around.

[asb]

LGTM, thanks for updating the comments.

llvm/lib/Target/RISCV/RISCVMergeBaseOffset.cpp

 public:
   static char ID;
   bool runOnMachineFunction(MachineFunction &Fn) override;
   bool detectFoldable(MachineInstr &Hi, MachineInstr *&Lo);
 
   bool detectAndFoldOffset(MachineInstr &Hi, MachineInstr &Lo);
   void foldOffset(MachineInstr &Hi, MachineInstr &Lo, MachineInstr &Tail,
                   int64_t Offset);
-  bool matchLargeOffset(MachineInstr &TailAdd, Register GSReg, int64_t &Offset);
-  bool matchShiftedOffset(MachineInstr &TailShXAdd, Register GSReg,
-                          int64_t &Offset);
+  bool foldLargeOffset(MachineInstr &Hi, MachineInstr &Lo,
+                       MachineInstr &TailAdd, Register GSReg);
+  bool foldShiftedOffset(MachineInstr &Hi, MachineInstr &Lo,
+                         MachineInstr &TailShXAdd, Register GSReg);
 
   RISCVMergeBaseOffsetOpt() : MachineFunctionPass(ID) {}
 
   MachineFunctionProperties getRequiredProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::IsSSA);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
   StringRef getPassName() const override {
     return RISCV_MERGE_BASE_OFFSET_NAME;
   }
 
 private:
   MachineRegisterInfo *MRI;
-  std::set<MachineInstr *> DeadInstrs;
 };
 } // end anonymous namespace
 
 char RISCVMergeBaseOffsetOpt::ID = 0;
 INITIALIZE_PASS(RISCVMergeBaseOffsetOpt, DEBUG_TYPE,
                 RISCV_MERGE_BASE_OFFSET_NAME, false, false)
 
 // Detect either of the patterns:
 //
 // 1. (medlow pattern):
 //   lui   vreg1, %hi(s)
 //   addi  vreg2, vreg1, %lo(s)
 //
 // 2. (medany pattern):
 // .Lpcrel_hi1:
 //   auipc vreg1, %pcrel_hi(s)
 //   addi  vreg2, vreg1, %pcrel_lo(.Lpcrel_hi1)
 //

 void RISCVMergeBaseOffsetOpt::foldOffset(MachineInstr &Hi, MachineInstr &Lo,
                                          MachineInstr &Tail, int64_t Offset) {
   assert(isInt<32>(Offset) && "Unexpected offset");
   // Put the offset back in Hi and the Lo
   Hi.getOperand(1).setOffset(Offset);
   if (Hi.getOpcode() != RISCV::AUIPC)
     Lo.getOperand(2).setOffset(Offset);
   // Delete the tail instruction.
-  DeadInstrs.insert(&Tail);
   MRI->replaceRegWith(Tail.getOperand(0).getReg(), Lo.getOperand(0).getReg());
+  Tail.eraseFromParent();
   LLVM_DEBUG(dbgs() << "  Merged offset " << Offset << " into base.\n"
                     << "     " << Hi << "     " << Lo;);
 }
 
 // Detect patterns for large offsets that are passed into an ADD instruction.
+// If the pattern is found, updates the offset in Hi and Lo instructions
+// and deletes TailAdd and the instructions that produced the offset.
 //
 //                     Base address lowering is of the form:
-//                        HiLUI:  lui   vreg1, %hi(s)
-//                       LoADDI:  addi  vreg2, vreg1, %lo(s)
+//                       Hi:  lui   vreg1, %hi(s)
+//                       Lo:  addi  vreg2, vreg1, %lo(s)
 //                       /                                  \
 //                      /                                    \
 //                     /                                      \
 //                    /  The large offset can be of two forms: \
 //  1) Offset that has non zero bits in lower      2) Offset that has non zero
 //     12 bits and upper 20 bits                      bits in upper 20 bits only
 //   OffseLUI: lui   vreg3, 4
 // OffsetTail: addi  voff, vreg3, 188                OffsetTail: lui  voff, 128
 //                    \                                        /
 //                     \                                      /
 //                      \                                    /
 //                       \                                  /
 //                         TailAdd: add  vreg4, vreg2, voff
-bool RISCVMergeBaseOffsetOpt::matchLargeOffset(MachineInstr &TailAdd,
-                                               Register GAReg,
-                                               int64_t &Offset) {
+bool RISCVMergeBaseOffsetOpt::foldLargeOffset(MachineInstr &Hi,
+                                              MachineInstr &Lo,
+                                              MachineInstr &TailAdd,
+                                              Register GAReg) {
   assert((TailAdd.getOpcode() == RISCV::ADD) && "Expected ADD instruction!");
   Register Rs = TailAdd.getOperand(1).getReg();
   Register Rt = TailAdd.getOperand(2).getReg();
   Register Reg = Rs == GAReg ? Rt : Rs;
 
   // Can't fold if the register has more than one use.
   if (!MRI->hasOneUse(Reg))
     return false;
if (OffsetTail.getOpcode() == RISCV::ADDI ||
     int64_t OffLo = AddiImmOp.getImm();
     MachineInstr &OffsetLui =
         *MRI->getVRegDef(OffsetTail.getOperand(1).getReg());
     MachineOperand &LuiImmOp = OffsetLui.getOperand(1);
     if (OffsetLui.getOpcode() != RISCV::LUI ||
         LuiImmOp.getTargetFlags() != RISCVII::MO_None ||
         !MRI->hasOneUse(OffsetLui.getOperand(0).getReg()))
       return false;
-    Offset = SignExtend64<32>(LuiImmOp.getImm() << 12);
+    int64_t Offset = SignExtend64<32>(LuiImmOp.getImm() << 12);
     Offset += OffLo;
     // RV32 ignores the upper 32 bits. ADDIW sign extends the result.
     if (!ST->is64Bit() || OffsetTail.getOpcode() == RISCV::ADDIW)
        Offset = SignExtend64<32>(Offset);
     // We can only fold simm32 offsets.
     if (!isInt<32>(Offset))
       return false;
     LLVM_DEBUG(dbgs() << "  Offset Instrs: " << OffsetTail
                       << "                 " << OffsetLui);
-    DeadInstrs.insert(&OffsetTail);
-    DeadInstrs.insert(&OffsetLui);
+    foldOffset(Hi, Lo, TailAdd, Offset);
+    OffsetTail.eraseFromParent();
+    OffsetLui.eraseFromParent();
     return true;
   } else if (OffsetTail.getOpcode() == RISCV::LUI) {
     // The offset value has all zero bits in the lower 12 bits. Only LUI
     // exists.
     LLVM_DEBUG(dbgs() << "  Offset Instr: " << OffsetTail);
-    Offset = SignExtend64<32>(OffsetTail.getOperand(1).getImm() << 12);
-    DeadInstrs.insert(&OffsetTail);
+    int64_t Offset = SignExtend64<32>(OffsetTail.getOperand(1).getImm() << 12);
+    foldOffset(Hi, Lo, TailAdd, Offset);
+    OffsetTail.eraseFromParent();
     return true;
   }
   return false;
 }
 
 // Detect patterns for offsets that are passed into a SHXADD instruction.
 // The offset has 1, 2, or 3 trailing zeros and fits in simm13, simm14, simm15.
 // The constant is created with addi voff, x0, C, and shXadd is used to
 // fill insert the trailing zeros and do the addition.
+// If the pattern is found, updates the offset in Hi and Lo instructions
+// and deletes TailShXAdd and the instructions that produced the offset.
 //
 // Hi:         lui     vreg1, %hi(s)
 // Lo:         addi    vreg2, vreg1, %lo(s)
 // OffsetTail: addi    voff, x0, C
 // TailAdd:    shXadd  vreg4, voff, vreg2
-bool RISCVMergeBaseOffsetOpt::matchShiftedOffset(MachineInstr &TailShXAdd,
-                                                 Register GAReg,
-                                                 int64_t &Offset) {
+bool RISCVMergeBaseOffsetOpt::foldShiftedOffset(MachineInstr &Hi,
+                                                MachineInstr &Lo,
+                                                MachineInstr &TailShXAdd,
+                                                Register GAReg) {
   assert((TailShXAdd.getOpcode() == RISCV::SH1ADD ||
           TailShXAdd.getOpcode() == RISCV::SH2ADD ||
           TailShXAdd.getOpcode() == RISCV::SH3ADD) &&
          "Expected SHXADD instruction!");
 
   // The first source is the shifted operand.
   Register Rs1 = TailShXAdd.getOperand(1).getReg();
 
   if (GAReg != TailShXAdd.getOperand(2).getReg())
     return false;
 
   // Can't fold if the register has more than one use.
   if (!MRI->hasOneUse(Rs1))
     return false;
   // This can point to an ADDI X0, C.
   MachineInstr &OffsetTail = *MRI->getVRegDef(Rs1);
   if (OffsetTail.getOpcode() != RISCV::ADDI)
     return false;
   if (!OffsetTail.getOperand(1).isReg() ||
       OffsetTail.getOperand(1).getReg() != RISCV::X0 ||
       !OffsetTail.getOperand(2).isImm())
     return false;
 
-  Offset = OffsetTail.getOperand(2).getImm();
+  int64_t Offset = OffsetTail.getOperand(2).getImm();
   assert(isInt<12>(Offset) && "Unexpected offset");
 
   unsigned ShAmt;
   switch (TailShXAdd.getOpcode()) {
   default: llvm_unreachable("Unexpected opcode");
   case RISCV::SH1ADD: ShAmt = 1; break;
   case RISCV::SH2ADD: ShAmt = 2; break;
   case RISCV::SH3ADD: ShAmt = 3; break;
   }
 
   Offset = (uint64_t)Offset << ShAmt;
 
   LLVM_DEBUG(dbgs() << "  Offset Instr: " << OffsetTail);
-  DeadInstrs.insert(&OffsetTail);
+  foldOffset(Hi, Lo, TailShXAdd, Offset);
+  OffsetTail.eraseFromParent();
   return true;
 }
 
 bool RISCVMergeBaseOffsetOpt::detectAndFoldOffset(MachineInstr &Hi,
                                                   MachineInstr &Lo) {
   Register DestReg = Lo.getOperand(0).getReg();
 
   // First, look for arithmetic instructions we can get an offset from.
case RISCV::ADDI: {
 
       // We might have two ADDIs in a row.
       Register TailDestReg = Tail.getOperand(0).getReg();
       if (MRI->hasOneUse(TailDestReg)) {
         MachineInstr &TailTail = *MRI->use_instr_begin(TailDestReg);
         if (TailTail.getOpcode() == RISCV::ADDI) {
           Offset += TailTail.getOperand(2).getImm();
           LLVM_DEBUG(dbgs() << "  Offset Instrs: " << Tail << TailTail);
-          DeadInstrs.insert(&Tail);
           foldOffset(Hi, Lo, TailTail, Offset);
+          Tail.eraseFromParent();
           return true;
         }
       }
 
       LLVM_DEBUG(dbgs() << "  Offset Instr: " << Tail);
       foldOffset(Hi, Lo, Tail, Offset);
       return true;
     }
     case RISCV::ADD: {
       // The offset is too large to fit in the immediate field of ADDI.
       // This can be in two forms:
       // 1) LUI hi_Offset followed by:
       //    ADDI lo_offset
       //    This happens in case the offset has non zero bits in
       //    both hi 20 and lo 12 bits.
       // 2) LUI (offset20)
       //    This happens in case the lower 12 bits of the offset are zeros.
-      int64_t Offset;
-      if (!matchLargeOffset(Tail, DestReg, Offset))
-        return false;
-      foldOffset(Hi, Lo, Tail, Offset);
-      return true;
+      return foldLargeOffset(Hi, Lo, Tail, DestReg);
     }
     case RISCV::SH1ADD:
     case RISCV::SH2ADD:
     case RISCV::SH3ADD: {
       // The offset is too large to fit in the immediate field of ADDI.
       // It may be encoded as (SH2ADD (ADDI X0, C), DestReg) or
       // (SH3ADD (ADDI X0, C), DestReg).
-      int64_t Offset;
-      if (!matchShiftedOffset(Tail, DestReg, Offset))
-        return false;
-      foldOffset(Hi, Lo, Tail, Offset);
-      return true;
+      return foldShiftedOffset(Hi, Lo, Tail, DestReg);
     }
     }
   }
 
   // We didn't find an arithmetic instruction. If all the uses are memory ops
   // with the same offset, we can transform:
   //
   // 1. (medlow pattern):
for (MachineInstr &UseMI :
        llvm::make_early_inc_range(MRI->use_instructions(DestReg))) {
     UseMI.removeOperand(2);
     UseMI.addOperand(ImmOp);
     // Update the base reg in the Tail instruction to feed from LUI.
     // Output of Hi is only used in Lo, no need to use MRI->replaceRegWith().
     UseMI.getOperand(1).setReg(Hi.getOperand(0).getReg());
   }
 
-  DeadInstrs.insert(&Lo);
+  Lo.eraseFromParent();
   return true;
 }
 
 bool RISCVMergeBaseOffsetOpt::runOnMachineFunction(MachineFunction &Fn) {
   if (skipFunction(Fn.getFunction()))
     return false;
 
   ST = &Fn.getSubtarget<RISCVSubtarget>();
 
   bool MadeChange = false;
-  DeadInstrs.clear();
   MRI = &Fn.getRegInfo();
   for (MachineBasicBlock &MBB : Fn) {
     LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n");
     for (MachineInstr &Hi : MBB) {
       MachineInstr *Lo = nullptr;
       if (!detectFoldable(Hi, Lo))
         continue;
       LLVM_DEBUG(dbgs() << "  Found lowered global address: "
                         << *Hi.getOperand(2).getGlobal() << "\n");
       MadeChange |= detectAndFoldOffset(Hi, *Lo);
     }
   }
-  // Delete dead instructions.
-  for (auto *MI : DeadInstrs)
-    MI->eraseFromParent();
+
   return MadeChange;
 }
 
 /// Returns an instance of the Merge Base Offset Optimization pass.
 FunctionPass *llvm::createRISCVMergeBaseOffsetOptPass() {
   return new RISCVMergeBaseOffsetOpt();
 }