[RISCV] Extend the Merge Base Offset pass to handle AUIPC+ADDI

[luismarques]

Summary

Builds upon D123264, adding support to merge the low part of the LLA address into the load/store instruction offsets.

This needs more testing and more tests. But the priority is reviewing D123264, to clarify if this is even a viable approach.

[craig.topper]

llvm/lib/Target/RISCV/RISCVMergeBaseOffset.cpp

275

Do we need to check that the immediate operand of the load/store is 0 before we remove it?

[luismarques]

• Rebase
• Handle non-zero offsets in tail load/store instructions

[luismarques]

Nit: tweak comments.

[luismarques]

Rebase after D128599.

[craig.topper]

I think calling setOffset on the pcrel_lo offset is incorrect. That always points to the auipc it shouldn't have an offset.

llvm/test/CodeGen/RISCV/fold-addi-loadstore.ll

365 ↗

(On Diff #443089)

This is incorrect. There shouldn't be a +4 on the pcrel_lo relocation.

378 ↗

(On Diff #443089)

Here too

417 ↗

(On Diff #443089)

And here

[luismarques]

Fix pointing to the AUIPC label

[craig.topper]

llvm/lib/Target/RISCV/RISCVMergeBaseOffset.cpp

124

This should also be skipped if Hi is AUIPC

[luismarques]

Address review feedback

[craig.topper]

LGTM

llvm/lib/Target/RISCV/RISCVMergeBaseOffset.cpp

 //===----- RISCVMergeBaseOffset.cpp - Optimise address calculations  ------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Merge the offset of address calculation into the offset field
-// of instructions in a global address lowering sequence. This pass transforms:
-//   lui  vreg1, %hi(s)
-//   addi vreg2, vreg1, %lo(s)
-//   addi vreg3, verg2, Offset
-//
-//   Into:
-//   lui  vreg1, %hi(s+Offset)
-//   addi vreg2, vreg1, %lo(s+Offset)
-//
-// The transformation is carried out under certain conditions:
-// 1) The offset field in the base of global address lowering sequence is zero.
-// 2) The lowered global address has only one use.
+// of instructions in a global address lowering sequence.
 //
-// The offset field can be in a different form. This pass handles all of them.
 //===----------------------------------------------------------------------===//
 
 #include "RISCV.h"
 #include "RISCVTargetMachine.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/MC/TargetRegistry.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Target/TargetOptions.h"
 #include <set>
 using namespace llvm;
 
 #define DEBUG_TYPE "riscv-merge-base-offset"
 #define RISCV_MERGE_BASE_OFFSET_NAME "RISCV Merge Base Offset"
 namespace {
 
 struct RISCVMergeBaseOffsetOpt : public MachineFunctionPass {
   static char ID;
   bool runOnMachineFunction(MachineFunction &Fn) override;
-  bool detectLuiAddiGlobal(MachineInstr &LUI, MachineInstr *&ADDI);
+  bool detectFoldable(MachineInstr &Hi, MachineInstr *&Lo);
 
-  bool detectAndFoldOffset(MachineInstr &HiLUI, MachineInstr &LoADDI);
-  void foldOffset(MachineInstr &HiLUI, MachineInstr &LoADDI, MachineInstr &Tail,
+  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);
   RISCVMergeBaseOffsetOpt() : MachineFunctionPass(ID) {}
 
   MachineFunctionProperties getRequiredProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::IsSSA);
   }
private:
   std::set<MachineInstr *> DeadInstrs;
 };
 } // end anonymous namespace
 
 char RISCVMergeBaseOffsetOpt::ID = 0;
 INITIALIZE_PASS(RISCVMergeBaseOffsetOpt, DEBUG_TYPE,
                 RISCV_MERGE_BASE_OFFSET_NAME, false, false)
 
-// Detect the pattern:
+// Detect either of the patterns:
+//
+// 1. (medlow pattern):
 //   lui   vreg1, %hi(s)
 //   addi  vreg2, vreg1, %lo(s)
 //
-//   Pattern only accepted if:
-//     1) ADDI has only one use.
-//     2) LUI has only one use; which is the ADDI.
-//     3) Both ADDI and LUI have GlobalAddress type which indicates that these
-//        are generated from global address lowering.
+// 2. (medany pattern):
+// .LBB0_1:
+//   auipc vreg1, %pcrel_hi(s)
+//   addi  vreg2, vreg1, %pcrel_lo(.LBB0_1)
+//
+//  The pattern is only accepted if:
+//     1) The first instruction has only one use, which is the ADDI.
+//     2) ADDI has only one use.
+//     3) The address operands have the appropriate type, reflecting the
+//        lowering of a global address using medlow or medany.
 //     4) Offset value in the Global Address is 0.
-bool RISCVMergeBaseOffsetOpt::detectLuiAddiGlobal(MachineInstr &HiLUI,
-                                                  MachineInstr *&LoADDI) {
-  if (HiLUI.getOpcode() != RISCV::LUI ||
-      HiLUI.getOperand(1).getTargetFlags() != RISCVII::MO_HI ||
-      HiLUI.getOperand(1).getType() != MachineOperand::MO_GlobalAddress ||
-      HiLUI.getOperand(1).getOffset() != 0 ||
-      !MRI->hasOneUse(HiLUI.getOperand(0).getReg()))
+bool RISCVMergeBaseOffsetOpt::detectFoldable(MachineInstr &Hi,
+                                             MachineInstr *&Lo) {
+  if (Hi.getOpcode() == RISCV::LUI) {
+    if (Hi.getOperand(1).getTargetFlags() != RISCVII::MO_HI ||
+        Hi.getOperand(1).getType() != MachineOperand::MO_GlobalAddress ||
+        Hi.getOperand(1).getOffset() != 0 ||
+        !MRI->hasOneUse(Hi.getOperand(0).getReg()))
       return false;
-  Register HiLuiDestReg = HiLUI.getOperand(0).getReg();
-  LoADDI = MRI->use_begin(HiLuiDestReg)->getParent();
-  if (LoADDI->getOpcode() != RISCV::ADDI ||
-      LoADDI->getOperand(2).getTargetFlags() != RISCVII::MO_LO ||
-      LoADDI->getOperand(2).getType() != MachineOperand::MO_GlobalAddress ||
-      LoADDI->getOperand(2).getOffset() != 0 ||
-      !MRI->hasOneUse(LoADDI->getOperand(0).getReg()))
+    Register HiDestReg = Hi.getOperand(0).getReg();
+    Lo = MRI->use_begin(HiDestReg)->getParent();
+    if (Lo->getOpcode() != RISCV::ADDI ||
+        Lo->getOperand(2).getTargetFlags() != RISCVII::MO_LO ||
+        Lo->getOperand(2).getType() != MachineOperand::MO_GlobalAddress ||
+        Lo->getOperand(2).getOffset() != 0 ||
+        !MRI->hasOneUse(Lo->getOperand(0).getReg()))
+      return false;
+    return true;
+  } else if (Hi.getOpcode() == RISCV::AUIPC) {
+    if (Hi.getOperand(1).getTargetFlags() != RISCVII::MO_PCREL_HI ||
+        Hi.getOperand(1).getType() != MachineOperand::MO_GlobalAddress ||
+        Hi.getOperand(1).getOffset() != 0 ||
+        !MRI->hasOneUse(Hi.getOperand(0).getReg()))
+      return false;
+    Register HiDestReg = Hi.getOperand(0).getReg();
+    Lo = MRI->use_begin(HiDestReg)->getParent();
+    if (Lo->getOpcode() != RISCV::ADDI ||
+        Lo->getOperand(2).getTargetFlags() != RISCVII::MO_PCREL_LO ||
+        Lo->getOperand(2).getType() != MachineOperand::MO_MCSymbol ||
+        !MRI->hasOneUse(Lo->getOperand(0).getReg()))
       return false;
     return true;
+  } else {
+    return false;
+  }
 }
 
-// Update the offset in HiLUI and LoADDI instructions.
+// Update the offset in Hi and Lo instructions.
 // Delete the tail instruction and update all the uses to use the
-// output from LoADDI.
-void RISCVMergeBaseOffsetOpt::foldOffset(MachineInstr &HiLUI,
-                                         MachineInstr &LoADDI,
+// output from Lo.
+void RISCVMergeBaseOffsetOpt::foldOffset(MachineInstr &Hi,
+                                         MachineInstr &Lo,
                                          MachineInstr &Tail, int64_t Offset) {
-  // Put the offset back in HiLUI and the LoADDI
-  HiLUI.getOperand(1).setOffset(Offset);
-  LoADDI.getOperand(2).setOffset(Offset);
+  // Put the offset back in Hi and the Lo
+  Hi.getOperand(1).setOffset(Offset);
+  Lo.getOperand(2).setOffset(Offset);
   // Delete the tail instruction.
   DeadInstrs.insert(&Tail);
-  MRI->replaceRegWith(Tail.getOperand(0).getReg(),
-                      LoADDI.getOperand(0).getReg());
+  MRI->replaceRegWith(Tail.getOperand(0).getReg(), Lo.getOperand(0).getReg());
   LLVM_DEBUG(dbgs() << "  Merged offset " << Offset << " into base.\n"
-                    << "     " << HiLUI << "     " << LoADDI;);
+                    << "     " << Hi << "     " << Lo;);
 }
 
 // Detect patterns for large offsets that are passed into an ADD instruction.
 //
 //                     Base address lowering is of the form:
 //                        HiLUI:  lui   vreg1, %hi(s)
 //                       LoADDI:  addi  vreg2, vreg1, %lo(s)
 //                       /                                  \
if (OffsetTail.getOpcode() == RISCV::ADDI) {
     LLVM_DEBUG(dbgs() << "  Offset Instr: " << OffsetTail);
     Offset = OffsetTail.getOperand(1).getImm() << 12;
     DeadInstrs.insert(&OffsetTail);
     return true;
   }
   return false;
 }
 
-bool RISCVMergeBaseOffsetOpt::detectAndFoldOffset(MachineInstr &HiLUI,
-                                                  MachineInstr &LoADDI) {
-  Register DestReg = LoADDI.getOperand(0).getReg();
-  assert(MRI->hasOneUse(DestReg) && "expected one use for LoADDI");
-  // LoADDI has only one use.
+bool RISCVMergeBaseOffsetOpt::detectAndFoldOffset(MachineInstr &Hi,
+                                                  MachineInstr &Lo) {
+  Register DestReg = Lo.getOperand(0).getReg();
+  assert(MRI->hasOneUse(DestReg) && "expected one use for Lo");
+  // Lo has only one use.
   MachineInstr &Tail = *MRI->use_begin(DestReg)->getParent();
   switch (Tail.getOpcode()) {
   default:
     LLVM_DEBUG(dbgs() << "Don't know how to get offset from this instr:"
                       << Tail);
     return false;
   case RISCV::ADDI: {
+    if (Hi.getOpcode() != RISCV::LUI)
+      return false;
     // Offset is simply an immediate operand.
     int64_t Offset = Tail.getOperand(2).getImm();
     LLVM_DEBUG(dbgs() << "  Offset Instr: " << Tail);
-    foldOffset(HiLUI, LoADDI, Tail, Offset);
+    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.
+    if (Hi.getOpcode() != RISCV::LUI)
+      return false;
     int64_t Offset;
     if (!matchLargeOffset(Tail, DestReg, Offset))
       return false;
-    foldOffset(HiLUI, LoADDI, Tail, Offset);
+    foldOffset(Hi, Lo, Tail, Offset);
     return true;
   }
   case RISCV::LB:
   case RISCV::LH:
   case RISCV::LW:
   case RISCV::LBU:
   case RISCV::LHU:
   case RISCV::LWU:
   case RISCV::LD:
   case RISCV::FLH:
   case RISCV::FLW:
   case RISCV::FLD:
   case RISCV::SB:
   case RISCV::SH:
   case RISCV::SW:
   case RISCV::SD:
   case RISCV::FSH:
   case RISCV::FSW:
   case RISCV::FSD: {
     // Transforms the sequence:            Into:
-    // HiLUI:  lui vreg1, %hi(foo)          --->  lui vreg1, %hi(foo+8)
-    // LoADDI: addi vreg2, vreg1, %lo(foo)  --->  lw vreg3, lo(foo+8)(vreg1)
-    // Tail:   lw vreg3, 8(vreg2)
+    // Hi:   lui vreg1, %hi(foo)          --->  lui vreg1, %hi(foo+8)
+    // Lo:   addi vreg2, vreg1, %lo(foo)  --->  lw vreg3, lo(foo+8)(vreg1)
+    // Tail: lw vreg3, 8(vreg2)
     if (Tail.getOperand(1).isFI())
       return false;
-    // Register defined by LoADDI should be used in the base part of the
+    // Register defined by Lo should be used in the base part of the
     // load\store instruction. Otherwise, no folding possible.
     Register BaseAddrReg = Tail.getOperand(1).getReg();
     if (DestReg != BaseAddrReg)
       return false;
+    if (Hi.getOpcode() == RISCV::LUI) {
       MachineOperand &TailImmOp = Tail.getOperand(2);
       int64_t Offset = TailImmOp.getImm();
       // Update the offsets in global address lowering.
-    HiLUI.getOperand(1).setOffset(Offset);
+      Hi.getOperand(1).setOffset(Offset);
       // Update the immediate in the Tail instruction to add the offset.
       Tail.removeOperand(2);
-    MachineOperand &ImmOp = LoADDI.getOperand(2);
+      MachineOperand &ImmOp = Lo.getOperand(2);
       ImmOp.setOffset(Offset);
       Tail.addOperand(ImmOp);
       // Update the base reg in the Tail instruction to feed from LUI.
-    // Output of HiLUI is only used in LoADDI, no need to use
+      // Output of Hi is only used in Lo, no need to use
       // MRI->replaceRegWith().
-    Tail.getOperand(1).setReg(HiLUI.getOperand(0).getReg());
-    DeadInstrs.insert(&LoADDI);
+      Tail.getOperand(1).setReg(Hi.getOperand(0).getReg());
+    } else {
+      Tail.removeOperand(2);
+      Tail.addOperand(Lo.getOperand(2));
+      Tail.getOperand(1).setReg(Hi.getOperand(0).getReg());
+    }
+    DeadInstrs.insert(&Lo);
     return true;
   }
   }
   return false;
 }
 
 bool RISCVMergeBaseOffsetOpt::runOnMachineFunction(MachineFunction &Fn) {
   if (skipFunction(Fn.getFunction()))
     return false;
 
   bool MadeChange = false;
   DeadInstrs.clear();
   MRI = &Fn.getRegInfo();
   for (MachineBasicBlock &MBB : Fn) {
     LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n");
-    for (MachineInstr &HiLUI : MBB) {
-      MachineInstr *LoADDI = nullptr;
-      if (!detectLuiAddiGlobal(HiLUI, LoADDI))
+    for (MachineInstr &Hi : MBB) {
+      MachineInstr *Lo = nullptr;
+      if (!detectFoldable(Hi, Lo))
         continue;
       LLVM_DEBUG(dbgs() << "  Found lowered global address with one use: "
-                        << *LoADDI->getOperand(2).getGlobal() << "\n");
+                        << *Hi.getOperand(2).getGlobal() << "\n");
       // If the use count is only one, merge the offset
-      MadeChange |= detectAndFoldOffset(HiLUI, *LoADDI);
+      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();
 }

llvm/test/CodeGen/RISCV/codemodel-lowering.ll

 ; RV32I-SMALL-NEXT:    lui a0, %hi(G)
 ; RV32I-SMALL-NEXT:    lw a0, %lo(G)(a0)
 ; RV32I-SMALL-NEXT:    ret
 ;
 ; RV32I-MEDIUM-LABEL: lower_global:
 ; RV32I-MEDIUM:       # %bb.0:
 ; RV32I-MEDIUM-NEXT:  .LPCRelHi0:
 ; RV32I-MEDIUM-NEXT:    auipc a0, %pcrel_hi(G)
-; RV32I-MEDIUM-NEXT:    addi a0, a0, %pcrel_lo(.LPCRelHi0)
-; RV32I-MEDIUM-NEXT:    lw a0, 0(a0)
+; RV32I-MEDIUM-NEXT:    lw a0, %pcrel_lo(.LPCRelHi0)(a0)
 ; RV32I-MEDIUM-NEXT:    ret
   %1 = load volatile i32, i32* @G
   ret i32 %1
 }
 
 ; Check lowering of blockaddresses
 
 @addr = global i8* null
 
 define void @lower_blockaddress() nounwind {
 ; RV32I-SMALL-LABEL: lower_blockaddress:
 ; RV32I-SMALL:       # %bb.0:
 ; RV32I-SMALL-NEXT:    lui a0, %hi(addr)
 ; RV32I-SMALL-NEXT:    li a1, 1
 ; RV32I-SMALL-NEXT:    sw a1, %lo(addr)(a0)
 ; RV32I-SMALL-NEXT:    ret
 ;
 ; RV32I-MEDIUM-LABEL: lower_blockaddress:
 ; RV32I-MEDIUM:       # %bb.0:
 ; RV32I-MEDIUM-NEXT:  .LPCRelHi1:
 ; RV32I-MEDIUM-NEXT:    auipc a0, %pcrel_hi(addr)
-; RV32I-MEDIUM-NEXT:    addi a0, a0, %pcrel_lo(.LPCRelHi1)
 ; RV32I-MEDIUM-NEXT:    li a1, 1
-; RV32I-MEDIUM-NEXT:    sw a1, 0(a0)
+; RV32I-MEDIUM-NEXT:    sw a1, %pcrel_lo(.LPCRelHi1)(a0)
 ; RV32I-MEDIUM-NEXT:    ret
   store volatile i8* blockaddress(@lower_blockaddress, %block), i8** @addr
   ret void
 
 block:
   unreachable
 }
 

llvm/test/CodeGen/RISCV/machinelicm-address-pseudos.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=riscv32 -relocation-model=pic -verify-machineinstrs < %s \
 ; RUN:   | FileCheck -check-prefixes=RV32I %s
 ; RUN: llc -mtriple=riscv64 -relocation-model=pic -verify-machineinstrs < %s \
 ; RUN:   | FileCheck -check-prefixes=RV64I %s
 
 ; Verifies that MachineLICM can hoist address generation pseudos out of loops.
 
 @l = protected global i32 0, align 4
 
 define void @test_lla(i32 signext %n) {
 ; RV32I-LABEL: test_lla:
 ; RV32I:       # %bb.0: # %entry
 ; RV32I-NEXT:  .LPCRelHi0:
-; RV32I-NEXT:    auipc a2, %pcrel_hi(l)
-; RV32I-NEXT:    li a1, 0
-; RV32I-NEXT:    addi a2, a2, %pcrel_lo(.LPCRelHi0)
+; RV32I-NEXT:    auipc a1, %pcrel_hi(l)
+; RV32I-NEXT:    li a2, 0
 ; RV32I-NEXT:  .LBB0_1: # %loop
 ; RV32I-NEXT:    # =>This Inner Loop Header: Depth=1
-; RV32I-NEXT:    lw a3, 0(a2)
-; RV32I-NEXT:    addi a1, a1, 1
-; RV32I-NEXT:    blt a1, a0, .LBB0_1
+; RV32I-NEXT:    lw a3, %pcrel_lo(.LPCRelHi0)(a1)
+; RV32I-NEXT:    addi a2, a2, 1
+; RV32I-NEXT:    blt a2, a0, .LBB0_1
 ; RV32I-NEXT:  # %bb.2: # %ret
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: test_lla:
 ; RV64I:       # %bb.0: # %entry
 ; RV64I-NEXT:  .LPCRelHi0:
-; RV64I-NEXT:    auipc a2, %pcrel_hi(l)
-; RV64I-NEXT:    li a1, 0
-; RV64I-NEXT:    addi a2, a2, %pcrel_lo(.LPCRelHi0)
+; RV64I-NEXT:    auipc a1, %pcrel_hi(l)
+; RV64I-NEXT:    li a2, 0
 ; RV64I-NEXT:  .LBB0_1: # %loop
 ; RV64I-NEXT:    # =>This Inner Loop Header: Depth=1
-; RV64I-NEXT:    lw a3, 0(a2)
-; RV64I-NEXT:    addiw a1, a1, 1
-; RV64I-NEXT:    blt a1, a0, .LBB0_1
+; RV64I-NEXT:    lw a3, %pcrel_lo(.LPCRelHi0)(a1)
+; RV64I-NEXT:    addiw a2, a2, 1
+; RV64I-NEXT:    blt a2, a0, .LBB0_1
 ; RV64I-NEXT:  # %bb.2: # %ret
 ; RV64I-NEXT:    ret
 entry:
   br label %loop
 
 loop:
   %i = phi i32 [ %inc, %loop ], [ 0, %entry ]
   %0 = load volatile i32, i32* @l, align 4