lib/Target/RISCV/RISCVMergeBaseOffset.cpp

   1 //===----- RISCVMergeBaseOffset.cpp - Optimise address calculations  ------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Merge the offset of address calculation into the offset field
  10 // of instructions in a global address lowering sequence. This pass transforms:
  11 //   lui  vreg1, %hi(s)
  12 //   addi vreg2, vreg1, %lo(s)
  13 //   addi vreg3, verg2, Offset
  14 //
  15 //   Into:
  16 //   lui  vreg1, %hi(s+Offset)
  17 //   addi vreg2, vreg1, %lo(s+Offset)
  18 //
  19 // The transformation is carried out under certain conditions:
  20 // 1) The offset field in the base of global address lowering sequence is zero.
  21 // 2) The lowered global address has only one use.
  22 //
  23 // The offset field can be in a different form. This pass handles all of them.
  24 //===----------------------------------------------------------------------===//
  25
  26 #include "RISCV.h"
  27 #include "RISCVTargetMachine.h"
  28 #include "llvm/CodeGen/Passes.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Support/TargetRegistry.h"
  31 #include "llvm/Target/TargetOptions.h"
  32 #include <set>
  33 using namespace llvm;
  34
  35 #define DEBUG_TYPE "riscv-merge-base-offset"
  36 #define RISCV_MERGE_BASE_OFFSET_NAME "RISCV Merge Base Offset"
  37 namespace {
  38
  39 struct RISCVMergeBaseOffsetOpt : public MachineFunctionPass {
  40   static char ID;
  41   const MachineFunction *MF;
  42   bool runOnMachineFunction(MachineFunction &Fn) override;
  43   bool detectLuiAddiGlobal(MachineInstr &LUI, MachineInstr *&ADDI);
  44
  45   bool detectAndFoldOffset(MachineInstr &HiLUI, MachineInstr &LoADDI);
  46   void foldOffset(MachineInstr &HiLUI, MachineInstr &LoADDI, MachineInstr &Tail,
  47                   int64_t Offset);
  48   bool matchLargeOffset(MachineInstr &TailAdd, Register GSReg, int64_t &Offset);
  49   RISCVMergeBaseOffsetOpt() : MachineFunctionPass(ID) {}
  50
  51   MachineFunctionProperties getRequiredProperties() const override {
  52     return MachineFunctionProperties().set(
  53         MachineFunctionProperties::Property::IsSSA);
  54   }
  55
  56   StringRef getPassName() const override {
  57     return RISCV_MERGE_BASE_OFFSET_NAME;
  58   }
  59
  60 private:
  61   MachineRegisterInfo *MRI;
  62   std::set<MachineInstr *> DeadInstrs;
  63 };
  64 } // end anonymous namespace
  65
  66 char RISCVMergeBaseOffsetOpt::ID = 0;
  67 INITIALIZE_PASS(RISCVMergeBaseOffsetOpt, "riscv-merge-base-offset",
  68                 RISCV_MERGE_BASE_OFFSET_NAME, false, false)
  69
  70 // Detect the pattern:
  71 //   lui   vreg1, %hi(s)
  72 //   addi  vreg2, vreg1, %lo(s)
  73 //
  74 //   Pattern only accepted if:
  75 //     1) ADDI has only one use.
  76 //     2) LUI has only one use; which is the ADDI.
  77 //     3) Both ADDI and LUI have GlobalAddress type which indicates that these
  78 //        are generated from global address lowering.
  79 //     4) Offset value in the Global Address is 0.
  80 bool RISCVMergeBaseOffsetOpt::detectLuiAddiGlobal(MachineInstr &HiLUI,
  81                                                   MachineInstr *&LoADDI) {
  82   if (HiLUI.getOpcode() != RISCV::LUI ||
  83       HiLUI.getOperand(1).getTargetFlags() != RISCVII::MO_HI ||
  84       HiLUI.getOperand(1).getType() != MachineOperand::MO_GlobalAddress ||
  85       HiLUI.getOperand(1).getOffset() != 0 ||
  86       !MRI->hasOneUse(HiLUI.getOperand(0).getReg()))
  87     return false;
  88   Register HiLuiDestReg = HiLUI.getOperand(0).getReg();
  89   LoADDI = MRI->use_begin(HiLuiDestReg)->getParent();
  90   if (LoADDI->getOpcode() != RISCV::ADDI ||
  91       LoADDI->getOperand(2).getTargetFlags() != RISCVII::MO_LO ||
  92       LoADDI->getOperand(2).getType() != MachineOperand::MO_GlobalAddress ||
  93       LoADDI->getOperand(2).getOffset() != 0 ||
  94       !MRI->hasOneUse(LoADDI->getOperand(0).getReg()))
  95     return false;
  96   return true;
  97 }
  98
  99 // Update the offset in HiLUI and LoADDI instructions.
 100 // Delete the tail instruction and update all the uses to use the
 101 // output from LoADDI.
 102 void RISCVMergeBaseOffsetOpt::foldOffset(MachineInstr &HiLUI,
 103                                          MachineInstr &LoADDI,
 104                                          MachineInstr &Tail, int64_t Offset) {
 105   // Put the offset back in HiLUI and the LoADDI
 106   HiLUI.getOperand(1).setOffset(Offset);
 107   LoADDI.getOperand(2).setOffset(Offset);
 108   // Delete the tail instruction.
 109   DeadInstrs.insert(&Tail);
 110   MRI->replaceRegWith(Tail.getOperand(0).getReg(),
 111                       LoADDI.getOperand(0).getReg());
 112   LLVM_DEBUG(dbgs() << "  Merged offset " << Offset << " into base.\n"
 113                     << "     " << HiLUI << "     " << LoADDI;);
 114 }
 115
 116 // Detect patterns for large offsets that are passed into an ADD instruction.
 117 //
 118 //                     Base address lowering is of the form:
 119 //                        HiLUI:  lui   vreg1, %hi(s)
 120 //                       LoADDI:  addi  vreg2, vreg1, %lo(s)
 121 //                       /                                  \
 122 //                      /                                    \
 123 //                     /                                      \
 124 //                    /  The large offset can be of two forms: \
 125 //  1) Offset that has non zero bits in lower      2) Offset that has non zero
 126 //     12 bits and upper 20 bits                      bits in upper 20 bits only
 127 //   OffseLUI: lui   vreg3, 4
 128 // OffsetTail: addi  voff, vreg3, 188                OffsetTail: lui  voff, 128
 129 //                    \                                        /
 130 //                     \                                      /
 131 //                      \                                    /
 132 //                       \                                  /
 133 //                         TailAdd: add  vreg4, vreg2, voff
 134 bool RISCVMergeBaseOffsetOpt::matchLargeOffset(MachineInstr &TailAdd,
 135                                                Register GAReg,
 136                                                int64_t &Offset) {
 137   assert((TailAdd.getOpcode() == RISCV::ADD) && "Expected ADD instruction!");
 138   Register Rs = TailAdd.getOperand(1).getReg();
 139   Register Rt = TailAdd.getOperand(2).getReg();
 140   Register Reg = Rs == GAReg ? Rt : Rs;
 141
 142   // Can't fold if the register has more than one use.
 143   if (!MRI->hasOneUse(Reg))
 144     return false;
 145   // This can point to an ADDI or a LUI:
 146   MachineInstr &OffsetTail = *MRI->getVRegDef(Reg);
 147   if (OffsetTail.getOpcode() == RISCV::ADDI) {
 148     // The offset value has non zero bits in both %hi and %lo parts.
 149     // Detect an ADDI that feeds from a LUI instruction.
 150     MachineOperand &AddiImmOp = OffsetTail.getOperand(2);
 151     if (AddiImmOp.getTargetFlags() != RISCVII::MO_None)
 152       return false;
 153     int64_t OffLo = AddiImmOp.getImm();
 154     MachineInstr &OffsetLui =
 155         *MRI->getVRegDef(OffsetTail.getOperand(1).getReg());
 156     MachineOperand &LuiImmOp = OffsetLui.getOperand(1);
 157     if (OffsetLui.getOpcode() != RISCV::LUI ||
 158         LuiImmOp.getTargetFlags() != RISCVII::MO_None ||
 159         !MRI->hasOneUse(OffsetLui.getOperand(0).getReg()))
 160       return false;
 161     int64_t OffHi = OffsetLui.getOperand(1).getImm();
 162     Offset = (OffHi << 12) + OffLo;
 163     LLVM_DEBUG(dbgs() << "  Offset Instrs: " << OffsetTail
 164                       << "                 " << OffsetLui);
 165     DeadInstrs.insert(&OffsetTail);
 166     DeadInstrs.insert(&OffsetLui);
 167     return true;
 168   } else if (OffsetTail.getOpcode() == RISCV::LUI) {
 169     // The offset value has all zero bits in the lower 12 bits. Only LUI
 170     // exists.
 171     LLVM_DEBUG(dbgs() << "  Offset Instr: " << OffsetTail);
 172     Offset = OffsetTail.getOperand(1).getImm() << 12;
 173     DeadInstrs.insert(&OffsetTail);
 174     return true;
 175   }
 176   return false;
 177 }
 178
 179 bool RISCVMergeBaseOffsetOpt::detectAndFoldOffset(MachineInstr &HiLUI,
 180                                                   MachineInstr &LoADDI) {
 181   Register DestReg = LoADDI.getOperand(0).getReg();
 182   assert(MRI->hasOneUse(DestReg) && "expected one use for LoADDI");
 183   // LoADDI has only one use.
 184   MachineInstr &Tail = *MRI->use_begin(DestReg)->getParent();
 185   switch (Tail.getOpcode()) {
 186   default:
 187     LLVM_DEBUG(dbgs() << "Don't know how to get offset from this instr:"
 188                       << Tail);
 189     return false;
 190   case RISCV::ADDI: {
 191     // Offset is simply an immediate operand.
 192     int64_t Offset = Tail.getOperand(2).getImm();
 193     LLVM_DEBUG(dbgs() << "  Offset Instr: " << Tail);
 194     foldOffset(HiLUI, LoADDI, Tail, Offset);
 195     return true;
 196   } break;
 197   case RISCV::ADD: {
 198     // The offset is too large to fit in the immediate field of ADDI.
 199     // This can be in two forms:
 200     // 1) LUI hi_Offset followed by:
 201     //    ADDI lo_offset
 202     //    This happens in case the offset has non zero bits in
 203     //    both hi 20 and lo 12 bits.
 204     // 2) LUI (offset20)
 205     //    This happens in case the lower 12 bits of the offset are zeros.
 206     int64_t Offset;
 207     if (!matchLargeOffset(Tail, DestReg, Offset))
 208       return false;
 209     foldOffset(HiLUI, LoADDI, Tail, Offset);
 210     return true;
 211   } break;
 212   case RISCV::LB:
 213   case RISCV::LH:
 214   case RISCV::LW:
 215   case RISCV::LBU:
 216   case RISCV::LHU:
 217   case RISCV::LWU:
 218   case RISCV::LD:
 219   case RISCV::FLW:
 220   case RISCV::FLD:
 221   case RISCV::SB:
 222   case RISCV::SH:
 223   case RISCV::SW:
 224   case RISCV::SD:
 225   case RISCV::FSW:
 226   case RISCV::FSD: {
 227     // Transforms the sequence:            Into:
 228     // HiLUI:  lui vreg1, %hi(foo)          --->  lui vreg1, %hi(foo+8)
 229     // LoADDI: addi vreg2, vreg1, %lo(foo)  --->  lw vreg3, lo(foo+8)(vreg1)
 230     // Tail:   lw vreg3, 8(vreg2)
 231     if (Tail.getOperand(1).isFI())
 232       return false;
 233     // Register defined by LoADDI should be used in the base part of the
 234     // load\store instruction. Otherwise, no folding possible.
 235     Register BaseAddrReg = Tail.getOperand(1).getReg();
 236     if (DestReg != BaseAddrReg)
 237       return false;
 238     MachineOperand &TailImmOp = Tail.getOperand(2);
 239     int64_t Offset = TailImmOp.getImm();
 240     // Update the offsets in global address lowering.
 241     HiLUI.getOperand(1).setOffset(Offset);
 242     // Update the immediate in the Tail instruction to add the offset.
 243     Tail.RemoveOperand(2);
 244     MachineOperand &ImmOp = LoADDI.getOperand(2);
 245     ImmOp.setOffset(Offset);
 246     Tail.addOperand(ImmOp);
 247     // Update the base reg in the Tail instruction to feed from LUI.
 248     // Output of HiLUI is only used in LoADDI, no need to use
 249     // MRI->replaceRegWith().
 250     Tail.getOperand(1).setReg(HiLUI.getOperand(0).getReg());
 251     DeadInstrs.insert(&LoADDI);
 252     return true;
 253   } break;
 254   }
 255   return false;
 256 }
 257
 258 bool RISCVMergeBaseOffsetOpt::runOnMachineFunction(MachineFunction &Fn) {
 259   if (skipFunction(Fn.getFunction()))
 260     return false;
 261
 262   DeadInstrs.clear();
 263   MRI = &Fn.getRegInfo();
 264   for (MachineBasicBlock &MBB : Fn) {
 265     LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n");
 266     for (MachineInstr &HiLUI : MBB) {
 267       MachineInstr *LoADDI = nullptr;
 268       if (!detectLuiAddiGlobal(HiLUI, LoADDI))
 269         continue;
 270       LLVM_DEBUG(dbgs() << "  Found lowered global address with one use: "
 271                         << *LoADDI->getOperand(2).getGlobal() << "\n");
 272       // If the use count is only one, merge the offset
 273       detectAndFoldOffset(HiLUI, *LoADDI);
 274     }
 275   }
 276   // Delete dead instructions.
 277   for (auto *MI : DeadInstrs)
 278     MI->eraseFromParent();
 279   return true;
 280 }
 281
 282 /// Returns an instance of the Merge Base Offset Optimization pass.
 283 FunctionPass *llvm::createRISCVMergeBaseOffsetOptPass() {
 284   return new RISCVMergeBaseOffsetOpt();
 285 }