contrib/llvm-project/llvm/lib/Target/ARC/ARCOptAddrMode.cpp

   1 //===- ARCOptAddrMode.cpp ---------------------------------------------===//
   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 /// \file
  10 /// This pass folds LD/ST + ADD pairs into Pre/Post-increment form  of
  11 /// load/store instructions.
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "ARC.h"
  15 #define GET_INSTRMAP_INFO
  16 #include "ARCInstrInfo.h"
  17 #include "ARCTargetMachine.h"
  18 #include "llvm/CodeGen/MachineBasicBlock.h"
  19 #include "llvm/CodeGen/MachineDominators.h"
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/MachineInstr.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/CodeGen/TargetRegisterInfo.h"
  24 #include "llvm/IR/Function.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/raw_ostream.h"
  27
  28 using namespace llvm;
  29
  30 #define OPTADDRMODE_DESC "ARC load/store address mode"
  31 #define OPTADDRMODE_NAME "arc-addr-mode"
  32 #define DEBUG_TYPE "arc-addr-mode"
  33
  34 namespace llvm {
  35 FunctionPass *createARCOptAddrMode();
  36 void initializeARCOptAddrModePass(PassRegistry &);
  37 } // end namespace llvm
  38
  39 namespace {
  40 class ARCOptAddrMode : public MachineFunctionPass {
  41 public:
  42   static char ID;
  43
  44   ARCOptAddrMode() : MachineFunctionPass(ID) {}
  45
  46   StringRef getPassName() const override { return OPTADDRMODE_DESC; }
  47
  48   void getAnalysisUsage(AnalysisUsage &AU) const override {
  49     AU.setPreservesCFG();
  50     MachineFunctionPass::getAnalysisUsage(AU);
  51     AU.addRequired<MachineDominatorTree>();
  52     AU.addPreserved<MachineDominatorTree>();
  53   }
  54
  55   bool runOnMachineFunction(MachineFunction &MF) override;
  56
  57 private:
  58   const ARCSubtarget *AST = nullptr;
  59   const ARCInstrInfo *AII = nullptr;
  60   MachineRegisterInfo *MRI = nullptr;
  61   MachineDominatorTree *MDT = nullptr;
  62
  63   // Tries to combine \p Ldst with increment of its base register to form
  64   // single post-increment instruction.
  65   MachineInstr *tryToCombine(MachineInstr &Ldst);
  66
  67   // Returns true if result of \p Add is not used before \p Ldst
  68   bool noUseOfAddBeforeLoadOrStore(const MachineInstr *Add,
  69                                    const MachineInstr *Ldst);
  70
  71   // Returns true if load/store instruction \p Ldst can be hoisted up to
  72   // instruction \p To
  73   bool canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To);
  74
  75   // Returns true if load/store instruction \p Ldst can be sunk down
  76   // to instruction \p To
  77   bool canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To);
  78
  79   // Check if instructions \p Ldst and \p Add can be moved to become adjacent
  80   // If they can return instruction which need not to move.
  81   // If \p Uses is not null, fill it with instructions after \p Ldst which use
  82   // \p Ldst's base register
  83   MachineInstr *canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add,
  84                                     SmallVectorImpl<MachineInstr *> *Uses);
  85
  86   // Returns true if all instruction in \p Uses array can be adjusted
  87   // to accomodate increment of register \p BaseReg by \p Incr
  88   bool canFixPastUses(const ArrayRef<MachineInstr *> &Uses,
  89                       MachineOperand &Incr, unsigned BaseReg);
  90
  91   // Update all instructions in \p Uses to accomodate increment
  92   // of \p BaseReg by \p Offset
  93   void fixPastUses(ArrayRef<MachineInstr *> Uses, unsigned BaseReg,
  94                    int64_t Offset);
  95
  96   // Change instruction \p Ldst to postincrement form.
  97   // \p NewBase is register to hold update base value
  98   // \p NewOffset is instruction's new offset
  99   void changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode,
 100                         unsigned NewBase, MachineOperand &NewOffset);
 101
 102   bool processBasicBlock(MachineBasicBlock &MBB);
 103 };
 104
 105 } // end anonymous namespace
 106
 107 char ARCOptAddrMode::ID = 0;
 108 INITIALIZE_PASS_BEGIN(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false,
 109                       false)
 110 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 111 INITIALIZE_PASS_END(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false,
 112                     false)
 113
 114 // Return true if \p Off can be used as immediate offset
 115 // operand of load/store instruction (S9 literal)
 116 static bool isValidLoadStoreOffset(int64_t Off) { return isInt<9>(Off); }
 117
 118 // Return true if \p Off can be used as immediate operand of
 119 // ADD/SUB instruction (U6 literal)
 120 static bool isValidIncrementOffset(int64_t Off) { return isUInt<6>(Off); }
 121
 122 static bool isAddConstantOp(const MachineInstr &MI, int64_t &Amount) {
 123   int64_t Sign = 1;
 124   switch (MI.getOpcode()) {
 125   case ARC::SUB_rru6:
 126     Sign = -1;
 127     LLVM_FALLTHROUGH;
 128   case ARC::ADD_rru6:
 129     assert(MI.getOperand(2).isImm() && "Expected immediate operand");
 130     Amount = Sign * MI.getOperand(2).getImm();
 131     return true;
 132   default:
 133     return false;
 134   }
 135 }
 136
 137 // Return true if \p MI dominates of uses of virtual register \p VReg
 138 static bool dominatesAllUsesOf(const MachineInstr *MI, unsigned VReg,
 139                                MachineDominatorTree *MDT,
 140                                MachineRegisterInfo *MRI) {
 141
 142   assert(TargetRegisterInfo::isVirtualRegister(VReg) &&
 143          "Expected virtual register!");
 144
 145   for (auto it = MRI->use_nodbg_begin(VReg), end = MRI->use_nodbg_end();
 146        it != end; ++it) {
 147     MachineInstr *User = it->getParent();
 148     if (User->isPHI()) {
 149       unsigned BBOperandIdx = User->getOperandNo(&*it) + 1;
 150       MachineBasicBlock *MBB = User->getOperand(BBOperandIdx).getMBB();
 151       if (MBB->empty()) {
 152         const MachineBasicBlock *InstBB = MI->getParent();
 153         assert(InstBB != MBB && "Instruction found in empty MBB");
 154         if (!MDT->dominates(InstBB, MBB))
 155           return false;
 156         continue;
 157       }
 158       User = &*MBB->rbegin();
 159     }
 160
 161     if (!MDT->dominates(MI, User))
 162       return false;
 163   }
 164   return true;
 165 }
 166
 167 // Return true if \p MI is load/store instruction with immediate offset
 168 // which can be adjusted by \p Disp
 169 static bool isLoadStoreThatCanHandleDisplacement(const TargetInstrInfo *TII,
 170                                                  const MachineInstr &MI,
 171                                                  int64_t Disp) {
 172   unsigned BasePos, OffPos;
 173   if (!TII->getBaseAndOffsetPosition(MI, BasePos, OffPos))
 174     return false;
 175   const MachineOperand &MO = MI.getOperand(OffPos);
 176   if (!MO.isImm())
 177     return false;
 178   int64_t Offset = MO.getImm() + Disp;
 179   return isValidLoadStoreOffset(Offset);
 180 }
 181
 182 bool ARCOptAddrMode::noUseOfAddBeforeLoadOrStore(const MachineInstr *Add,
 183                                                  const MachineInstr *Ldst) {
 184   unsigned R = Add->getOperand(0).getReg();
 185   return dominatesAllUsesOf(Ldst, R, MDT, MRI);
 186 }
 187
 188 MachineInstr *ARCOptAddrMode::tryToCombine(MachineInstr &Ldst) {
 189   assert((Ldst.mayLoad() || Ldst.mayStore()) && "LD/ST instruction expected");
 190
 191   unsigned BasePos, OffsetPos;
 192
 193   LLVM_DEBUG(dbgs() << "[ABAW] tryToCombine " << Ldst);
 194   if (!AII->getBaseAndOffsetPosition(Ldst, BasePos, OffsetPos)) {
 195     LLVM_DEBUG(dbgs() << "[ABAW] Not a recognized load/store\n");
 196     return nullptr;
 197   }
 198
 199   MachineOperand &Base = Ldst.getOperand(BasePos);
 200   MachineOperand &Offset = Ldst.getOperand(OffsetPos);
 201
 202   assert(Base.isReg() && "Base operand must be register");
 203   if (!Offset.isImm()) {
 204     LLVM_DEBUG(dbgs() << "[ABAW] Offset is not immediate\n");
 205     return nullptr;
 206   }
 207
 208   unsigned B = Base.getReg();
 209   if (TargetRegisterInfo::isStackSlot(B) ||
 210       !TargetRegisterInfo::isVirtualRegister(B)) {
 211     LLVM_DEBUG(dbgs() << "[ABAW] Base is not VReg\n");
 212     return nullptr;
 213   }
 214
 215   // TODO: try to generate address preincrement
 216   if (Offset.getImm() != 0) {
 217     LLVM_DEBUG(dbgs() << "[ABAW] Non-zero offset\n");
 218     return nullptr;
 219   }
 220
 221   for (auto &Add : MRI->use_nodbg_instructions(B)) {
 222     int64_t Incr;
 223     if (!isAddConstantOp(Add, Incr))
 224       continue;
 225     if (!isValidLoadStoreOffset(Incr))
 226       continue;
 227
 228     SmallVector<MachineInstr *, 8> Uses;
 229     MachineInstr *MoveTo = canJoinInstructions(&Ldst, &Add, &Uses);
 230
 231     if (!MoveTo)
 232       continue;
 233
 234     if (!canFixPastUses(Uses, Add.getOperand(2), B))
 235       continue;
 236
 237     LLVM_DEBUG(MachineInstr *First = &Ldst; MachineInstr *Last = &Add;
 238                if (MDT->dominates(Last, First)) std::swap(First, Last);
 239                dbgs() << "[ABAW] Instructions " << *First << " and " << *Last
 240                       << " combined\n";
 241
 242     );
 243
 244     MachineInstr *Result = Ldst.getNextNode();
 245     if (MoveTo == &Add) {
 246       Ldst.removeFromParent();
 247       Add.getParent()->insertAfter(Add.getIterator(), &Ldst);
 248     }
 249     if (Result == &Add)
 250       Result = Result->getNextNode();
 251
 252     fixPastUses(Uses, B, Incr);
 253
 254     int NewOpcode = ARC::getPostIncOpcode(Ldst.getOpcode());
 255     assert(NewOpcode > 0 && "No postincrement form found");
 256     unsigned NewBaseReg = Add.getOperand(0).getReg();
 257     changeToAddrMode(Ldst, NewOpcode, NewBaseReg, Add.getOperand(2));
 258     Add.eraseFromParent();
 259
 260     return Result;
 261   }
 262   return nullptr;
 263 }
 264
 265 MachineInstr *
 266 ARCOptAddrMode::canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add,
 267                                     SmallVectorImpl<MachineInstr *> *Uses) {
 268   assert(Ldst && Add && "NULL instruction passed");
 269
 270   MachineInstr *First = Add;
 271   MachineInstr *Last = Ldst;
 272   if (MDT->dominates(Ldst, Add))
 273     std::swap(First, Last);
 274   else if (!MDT->dominates(Add, Ldst))
 275     return nullptr;
 276
 277   LLVM_DEBUG(dbgs() << "canJoinInstructions: " << *First << *Last);
 278
 279   unsigned BasePos, OffPos;
 280
 281   if (!AII->getBaseAndOffsetPosition(*Ldst, BasePos, OffPos)) {
 282     LLVM_DEBUG(
 283         dbgs()
 284         << "[canJoinInstructions] Cannot determine base/offset position\n");
 285     return nullptr;
 286   }
 287
 288   unsigned BaseReg = Ldst->getOperand(BasePos).getReg();
 289
 290   // prohibit this:
 291   //   v1 = add v0, c
 292   //   st v1, [v0, 0]
 293   // and this
 294   //   st v0, [v0, 0]
 295   //   v1 = add v0, c
 296   if (Ldst->mayStore() && Ldst->getOperand(0).isReg()) {
 297     unsigned StReg = Ldst->getOperand(0).getReg();
 298     if (Add->getOperand(0).getReg() == StReg || BaseReg == StReg) {
 299       LLVM_DEBUG(dbgs() << "[canJoinInstructions] Store uses result of Add\n");
 300       return nullptr;
 301     }
 302   }
 303
 304   SmallVector<MachineInstr *, 4> UsesAfterLdst;
 305   SmallVector<MachineInstr *, 4> UsesAfterAdd;
 306   for (MachineInstr &MI : MRI->use_nodbg_instructions(BaseReg)) {
 307     if (&MI == Ldst || &MI == Add)
 308       continue;
 309     if (&MI != Add && MDT->dominates(Ldst, &MI))
 310       UsesAfterLdst.push_back(&MI);
 311     else if (!MDT->dominates(&MI, Ldst))
 312       return nullptr;
 313     if (MDT->dominates(Add, &MI))
 314       UsesAfterAdd.push_back(&MI);
 315   }
 316
 317   MachineInstr *Result = nullptr;
 318
 319   if (First == Add) {
 320     //  n = add b, i
 321     //  ...
 322     //  x = ld [b, o] or x = ld [n, o]
 323
 324     if (noUseOfAddBeforeLoadOrStore(First, Last)) {
 325       Result = Last;
 326       LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can sink Add down to Ldst\n");
 327     } else if (canHoistLoadStoreTo(Ldst, Add)) {
 328       Result = First;
 329       LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Ldst to Add\n");
 330     }
 331   } else {
 332     // x = ld [b, o]
 333     // ...
 334     // n = add b, i
 335     Result = First;
 336     LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Add to Ldst\n");
 337   }
 338   if (Result && Uses)
 339     *Uses = (Result == Ldst) ? UsesAfterLdst : UsesAfterAdd;
 340   return Result;
 341 }
 342
 343 bool ARCOptAddrMode::canFixPastUses(const ArrayRef<MachineInstr *> &Uses,
 344                                     MachineOperand &Incr, unsigned BaseReg) {
 345
 346   assert(Incr.isImm() && "Expected immediate increment");
 347   int64_t NewOffset = Incr.getImm();
 348   for (MachineInstr *MI : Uses) {
 349     int64_t Dummy;
 350     if (isAddConstantOp(*MI, Dummy)) {
 351       if (isValidIncrementOffset(Dummy + NewOffset))
 352         continue;
 353       return false;
 354     }
 355     if (isLoadStoreThatCanHandleDisplacement(AII, *MI, -NewOffset))
 356       continue;
 357     LLVM_DEBUG(dbgs() << "Instruction cannot handle displacement " << -NewOffset
 358                       << ": " << *MI);
 359     return false;
 360   }
 361   return true;
 362 }
 363
 364 void ARCOptAddrMode::fixPastUses(ArrayRef<MachineInstr *> Uses,
 365                                  unsigned NewBase, int64_t NewOffset) {
 366
 367   for (MachineInstr *MI : Uses) {
 368     int64_t Amount;
 369     unsigned BasePos, OffPos;
 370     if (isAddConstantOp(*MI, Amount)) {
 371       NewOffset += Amount;
 372       assert(isValidIncrementOffset(NewOffset) &&
 373              "New offset won't fit into ADD instr");
 374       BasePos = 1;
 375       OffPos = 2;
 376     } else if (AII->getBaseAndOffsetPosition(*MI, BasePos, OffPos)) {
 377       MachineOperand &MO = MI->getOperand(OffPos);
 378       assert(MO.isImm() && "expected immediate operand");
 379       NewOffset += MO.getImm();
 380       assert(isValidLoadStoreOffset(NewOffset) &&
 381              "New offset won't fit into LD/ST");
 382     } else
 383       llvm_unreachable("unexpected instruction");
 384
 385     MI->getOperand(BasePos).setReg(NewBase);
 386     MI->getOperand(OffPos).setImm(NewOffset);
 387   }
 388 }
 389
 390 bool ARCOptAddrMode::canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) {
 391   if (Ldst->getParent() != To->getParent())
 392     return false;
 393   MachineBasicBlock::const_iterator MI(To), ME(Ldst),
 394       End(Ldst->getParent()->end());
 395
 396   bool IsStore = Ldst->mayStore();
 397   for (; MI != ME && MI != End; ++MI) {
 398     if (MI->isDebugValue())
 399       continue;
 400     if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() ||
 401         MI->hasUnmodeledSideEffects())
 402       return false;
 403     if (IsStore && MI->mayLoad())
 404       return false;
 405   }
 406
 407   for (auto &O : Ldst->explicit_operands()) {
 408     if (!O.isReg() || !O.isUse())
 409       continue;
 410     MachineInstr *OpDef = MRI->getVRegDef(O.getReg());
 411     if (!OpDef || !MDT->dominates(OpDef, To))
 412       return false;
 413   }
 414   return true;
 415 }
 416
 417 bool ARCOptAddrMode::canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) {
 418   // Can only sink load/store within same BB
 419   if (Ldst->getParent() != To->getParent())
 420     return false;
 421   MachineBasicBlock::const_iterator MI(Ldst), ME(To),
 422       End(Ldst->getParent()->end());
 423
 424   bool IsStore = Ldst->mayStore();
 425   bool IsLoad = Ldst->mayLoad();
 426
 427   Register ValReg = IsLoad ? Ldst->getOperand(0).getReg() : Register();
 428   for (; MI != ME && MI != End; ++MI) {
 429     if (MI->isDebugValue())
 430       continue;
 431     if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() ||
 432         MI->hasUnmodeledSideEffects())
 433       return false;
 434     if (IsStore && MI->mayLoad())
 435       return false;
 436     if (ValReg && MI->readsVirtualRegister(ValReg))
 437       return false;
 438   }
 439   return true;
 440 }
 441
 442 void ARCOptAddrMode::changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode,
 443                                       unsigned NewBase,
 444                                       MachineOperand &NewOffset) {
 445   bool IsStore = Ldst.mayStore();
 446   unsigned BasePos, OffPos;
 447   MachineOperand Src = MachineOperand::CreateImm(0xDEADBEEF);
 448   AII->getBaseAndOffsetPosition(Ldst, BasePos, OffPos);
 449
 450   unsigned BaseReg = Ldst.getOperand(BasePos).getReg();
 451
 452   Ldst.RemoveOperand(OffPos);
 453   Ldst.RemoveOperand(BasePos);
 454
 455   if (IsStore) {
 456     Src = Ldst.getOperand(BasePos - 1);
 457     Ldst.RemoveOperand(BasePos - 1);
 458   }
 459
 460   Ldst.setDesc(AST->getInstrInfo()->get(NewOpcode));
 461   Ldst.addOperand(MachineOperand::CreateReg(NewBase, true));
 462   if (IsStore)
 463     Ldst.addOperand(Src);
 464   Ldst.addOperand(MachineOperand::CreateReg(BaseReg, false));
 465   Ldst.addOperand(NewOffset);
 466   LLVM_DEBUG(dbgs() << "[ABAW] New Ldst: " << Ldst);
 467 }
 468
 469 bool ARCOptAddrMode::processBasicBlock(MachineBasicBlock &MBB) {
 470   bool Changed = false;
 471   for (auto MI = MBB.begin(), ME = MBB.end(); MI != ME; ++MI) {
 472     if (MI->isDebugValue())
 473       continue;
 474     if (!MI->mayLoad() && !MI->mayStore())
 475       continue;
 476     if (ARC::getPostIncOpcode(MI->getOpcode()) < 0)
 477       continue;
 478     MachineInstr *Res = tryToCombine(*MI);
 479     if (Res) {
 480       Changed = true;
 481       // Res points to the next instruction. Rewind to process it
 482       MI = std::prev(Res->getIterator());
 483     }
 484   }
 485   return Changed;
 486 }
 487
 488 bool ARCOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
 489   if (skipFunction(MF.getFunction()))
 490     return false;
 491
 492   AST = &MF.getSubtarget<ARCSubtarget>();
 493   AII = AST->getInstrInfo();
 494   MRI = &MF.getRegInfo();
 495   MDT = &getAnalysis<MachineDominatorTree>();
 496
 497   bool Changed = false;
 498   for (auto &MBB : MF)
 499     Changed |= processBasicBlock(MBB);
 500   return Changed;
 501 }
 502
 503 //===----------------------------------------------------------------------===//
 504 //                         Public Constructor Functions
 505 //===----------------------------------------------------------------------===//
 506
 507 FunctionPass *llvm::createARCOptAddrMode() { return new ARCOptAddrMode(); }