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