1 //===- ARCOptAddrMode.cpp ---------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
10 /// This pass folds LD/ST + ADD pairs into Pre/Post-increment form of
11 /// load/store instructions.
12 //===----------------------------------------------------------------------===//
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/InitializePasses.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
31 #define OPTADDRMODE_DESC "ARC load/store address mode"
32 #define OPTADDRMODE_NAME "arc-addr-mode"
33 #define DEBUG_TYPE "arc-addr-mode"
36 FunctionPass *createARCOptAddrMode();
37 void initializeARCOptAddrModePass(PassRegistry &);
38 } // end namespace llvm
41 class ARCOptAddrMode : public MachineFunctionPass {
45 ARCOptAddrMode() : MachineFunctionPass(ID) {}
47 StringRef getPassName() const override { return OPTADDRMODE_DESC; }
49 void getAnalysisUsage(AnalysisUsage &AU) const override {
51 MachineFunctionPass::getAnalysisUsage(AU);
52 AU.addRequired<MachineDominatorTree>();
53 AU.addPreserved<MachineDominatorTree>();
56 bool runOnMachineFunction(MachineFunction &MF) override;
59 const ARCSubtarget *AST = nullptr;
60 const ARCInstrInfo *AII = nullptr;
61 MachineRegisterInfo *MRI = nullptr;
62 MachineDominatorTree *MDT = nullptr;
64 // Tries to combine \p Ldst with increment of its base register to form
65 // single post-increment instruction.
66 MachineInstr *tryToCombine(MachineInstr &Ldst);
68 // Returns true if result of \p Add is not used before \p Ldst
69 bool noUseOfAddBeforeLoadOrStore(const MachineInstr *Add,
70 const MachineInstr *Ldst);
72 // Returns true if load/store instruction \p Ldst can be hoisted up to
74 bool canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To);
76 // Returns true if load/store instruction \p Ldst can be sunk down
77 // to instruction \p To
78 bool canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To);
80 // Check if instructions \p Ldst and \p Add can be moved to become adjacent
81 // If they can return instruction which need not to move.
82 // If \p Uses is not null, fill it with instructions after \p Ldst which use
83 // \p Ldst's base register
84 MachineInstr *canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add,
85 SmallVectorImpl<MachineInstr *> *Uses);
87 // Returns true if all instruction in \p Uses array can be adjusted
88 // to accomodate increment of register \p BaseReg by \p Incr
89 bool canFixPastUses(const ArrayRef<MachineInstr *> &Uses,
90 MachineOperand &Incr, unsigned BaseReg);
92 // Update all instructions in \p Uses to accomodate increment
93 // of \p BaseReg by \p Offset
94 void fixPastUses(ArrayRef<MachineInstr *> Uses, unsigned BaseReg,
97 // Change instruction \p Ldst to postincrement form.
98 // \p NewBase is register to hold update base value
99 // \p NewOffset is instruction's new offset
100 void changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode,
101 unsigned NewBase, MachineOperand &NewOffset);
103 bool processBasicBlock(MachineBasicBlock &MBB);
106 } // end anonymous namespace
108 char ARCOptAddrMode::ID = 0;
109 INITIALIZE_PASS_BEGIN(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false,
111 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
112 INITIALIZE_PASS_END(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false,
115 // Return true if \p Off can be used as immediate offset
116 // operand of load/store instruction (S9 literal)
117 static bool isValidLoadStoreOffset(int64_t Off) { return isInt<9>(Off); }
119 // Return true if \p Off can be used as immediate operand of
120 // ADD/SUB instruction (U6 literal)
121 static bool isValidIncrementOffset(int64_t Off) { return isUInt<6>(Off); }
123 static bool isAddConstantOp(const MachineInstr &MI, int64_t &Amount) {
125 switch (MI.getOpcode()) {
130 assert(MI.getOperand(2).isImm() && "Expected immediate operand");
131 Amount = Sign * MI.getOperand(2).getImm();
138 // Return true if \p MI dominates of uses of virtual register \p VReg
139 static bool dominatesAllUsesOf(const MachineInstr *MI, unsigned VReg,
140 MachineDominatorTree *MDT,
141 MachineRegisterInfo *MRI) {
143 assert(Register::isVirtualRegister(VReg) && "Expected virtual register!");
145 for (auto it = MRI->use_nodbg_begin(VReg), end = MRI->use_nodbg_end();
147 MachineInstr *User = it->getParent();
149 unsigned BBOperandIdx = User->getOperandNo(&*it) + 1;
150 MachineBasicBlock *MBB = User->getOperand(BBOperandIdx).getMBB();
152 const MachineBasicBlock *InstBB = MI->getParent();
153 assert(InstBB != MBB && "Instruction found in empty MBB");
154 if (!MDT->dominates(InstBB, MBB))
158 User = &*MBB->rbegin();
161 if (!MDT->dominates(MI, User))
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,
172 unsigned BasePos, OffPos;
173 if (!TII->getBaseAndOffsetPosition(MI, BasePos, OffPos))
175 const MachineOperand &MO = MI.getOperand(OffPos);
178 int64_t Offset = MO.getImm() + Disp;
179 return isValidLoadStoreOffset(Offset);
182 bool ARCOptAddrMode::noUseOfAddBeforeLoadOrStore(const MachineInstr *Add,
183 const MachineInstr *Ldst) {
184 Register R = Add->getOperand(0).getReg();
185 return dominatesAllUsesOf(Ldst, R, MDT, MRI);
188 MachineInstr *ARCOptAddrMode::tryToCombine(MachineInstr &Ldst) {
189 assert(Ldst.mayLoadOrStore() && "LD/ST instruction expected");
191 unsigned BasePos, OffsetPos;
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");
199 MachineOperand &Base = Ldst.getOperand(BasePos);
200 MachineOperand &Offset = Ldst.getOperand(OffsetPos);
202 assert(Base.isReg() && "Base operand must be register");
203 if (!Offset.isImm()) {
204 LLVM_DEBUG(dbgs() << "[ABAW] Offset is not immediate\n");
208 Register B = Base.getReg();
209 if (Register::isStackSlot(B) || !Register::isVirtualRegister(B)) {
210 LLVM_DEBUG(dbgs() << "[ABAW] Base is not VReg\n");
214 // TODO: try to generate address preincrement
215 if (Offset.getImm() != 0) {
216 LLVM_DEBUG(dbgs() << "[ABAW] Non-zero offset\n");
220 for (auto &Add : MRI->use_nodbg_instructions(B)) {
222 if (!isAddConstantOp(Add, Incr))
224 if (!isValidLoadStoreOffset(Incr))
227 SmallVector<MachineInstr *, 8> Uses;
228 MachineInstr *MoveTo = canJoinInstructions(&Ldst, &Add, &Uses);
233 if (!canFixPastUses(Uses, Add.getOperand(2), B))
236 LLVM_DEBUG(MachineInstr *First = &Ldst; MachineInstr *Last = &Add;
237 if (MDT->dominates(Last, First)) std::swap(First, Last);
238 dbgs() << "[ABAW] Instructions " << *First << " and " << *Last
243 MachineInstr *Result = Ldst.getNextNode();
244 if (MoveTo == &Add) {
245 Ldst.removeFromParent();
246 Add.getParent()->insertAfter(Add.getIterator(), &Ldst);
249 Result = Result->getNextNode();
251 fixPastUses(Uses, B, Incr);
253 int NewOpcode = ARC::getPostIncOpcode(Ldst.getOpcode());
254 assert(NewOpcode > 0 && "No postincrement form found");
255 unsigned NewBaseReg = Add.getOperand(0).getReg();
256 changeToAddrMode(Ldst, NewOpcode, NewBaseReg, Add.getOperand(2));
257 Add.eraseFromParent();
265 ARCOptAddrMode::canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add,
266 SmallVectorImpl<MachineInstr *> *Uses) {
267 assert(Ldst && Add && "NULL instruction passed");
269 MachineInstr *First = Add;
270 MachineInstr *Last = Ldst;
271 if (MDT->dominates(Ldst, Add))
272 std::swap(First, Last);
273 else if (!MDT->dominates(Add, Ldst))
276 LLVM_DEBUG(dbgs() << "canJoinInstructions: " << *First << *Last);
278 unsigned BasePos, OffPos;
280 if (!AII->getBaseAndOffsetPosition(*Ldst, BasePos, OffPos)) {
283 << "[canJoinInstructions] Cannot determine base/offset position\n");
287 Register BaseReg = Ldst->getOperand(BasePos).getReg();
295 if (Ldst->mayStore() && Ldst->getOperand(0).isReg()) {
296 Register StReg = Ldst->getOperand(0).getReg();
297 if (Add->getOperand(0).getReg() == StReg || BaseReg == StReg) {
298 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Store uses result of Add\n");
303 SmallVector<MachineInstr *, 4> UsesAfterLdst;
304 SmallVector<MachineInstr *, 4> UsesAfterAdd;
305 for (MachineInstr &MI : MRI->use_nodbg_instructions(BaseReg)) {
306 if (&MI == Ldst || &MI == Add)
308 if (&MI != Add && MDT->dominates(Ldst, &MI))
309 UsesAfterLdst.push_back(&MI);
310 else if (!MDT->dominates(&MI, Ldst))
312 if (MDT->dominates(Add, &MI))
313 UsesAfterAdd.push_back(&MI);
316 MachineInstr *Result = nullptr;
321 // x = ld [b, o] or x = ld [n, o]
323 if (noUseOfAddBeforeLoadOrStore(First, Last)) {
325 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can sink Add down to Ldst\n");
326 } else if (canHoistLoadStoreTo(Ldst, Add)) {
328 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Ldst to Add\n");
335 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Add to Ldst\n");
338 *Uses = (Result == Ldst) ? UsesAfterLdst : UsesAfterAdd;
342 bool ARCOptAddrMode::canFixPastUses(const ArrayRef<MachineInstr *> &Uses,
343 MachineOperand &Incr, unsigned BaseReg) {
345 assert(Incr.isImm() && "Expected immediate increment");
346 int64_t NewOffset = Incr.getImm();
347 for (MachineInstr *MI : Uses) {
349 if (isAddConstantOp(*MI, Dummy)) {
350 if (isValidIncrementOffset(Dummy + NewOffset))
354 if (isLoadStoreThatCanHandleDisplacement(AII, *MI, -NewOffset))
356 LLVM_DEBUG(dbgs() << "Instruction cannot handle displacement " << -NewOffset
363 void ARCOptAddrMode::fixPastUses(ArrayRef<MachineInstr *> Uses,
364 unsigned NewBase, int64_t NewOffset) {
366 for (MachineInstr *MI : Uses) {
368 unsigned BasePos, OffPos;
369 if (isAddConstantOp(*MI, Amount)) {
371 assert(isValidIncrementOffset(NewOffset) &&
372 "New offset won't fit into ADD instr");
375 } else if (AII->getBaseAndOffsetPosition(*MI, BasePos, OffPos)) {
376 MachineOperand &MO = MI->getOperand(OffPos);
377 assert(MO.isImm() && "expected immediate operand");
378 NewOffset += MO.getImm();
379 assert(isValidLoadStoreOffset(NewOffset) &&
380 "New offset won't fit into LD/ST");
382 llvm_unreachable("unexpected instruction");
384 MI->getOperand(BasePos).setReg(NewBase);
385 MI->getOperand(OffPos).setImm(NewOffset);
389 bool ARCOptAddrMode::canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) {
390 if (Ldst->getParent() != To->getParent())
392 MachineBasicBlock::const_iterator MI(To), ME(Ldst),
393 End(Ldst->getParent()->end());
395 bool IsStore = Ldst->mayStore();
396 for (; MI != ME && MI != End; ++MI) {
397 if (MI->isDebugValue())
399 if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() ||
400 MI->hasUnmodeledSideEffects())
402 if (IsStore && MI->mayLoad())
406 for (auto &O : Ldst->explicit_operands()) {
407 if (!O.isReg() || !O.isUse())
409 MachineInstr *OpDef = MRI->getVRegDef(O.getReg());
410 if (!OpDef || !MDT->dominates(OpDef, To))
416 bool ARCOptAddrMode::canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) {
417 // Can only sink load/store within same BB
418 if (Ldst->getParent() != To->getParent())
420 MachineBasicBlock::const_iterator MI(Ldst), ME(To),
421 End(Ldst->getParent()->end());
423 bool IsStore = Ldst->mayStore();
424 bool IsLoad = Ldst->mayLoad();
426 Register ValReg = IsLoad ? Ldst->getOperand(0).getReg() : Register();
427 for (; MI != ME && MI != End; ++MI) {
428 if (MI->isDebugValue())
430 if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() ||
431 MI->hasUnmodeledSideEffects())
433 if (IsStore && MI->mayLoad())
435 if (ValReg && MI->readsVirtualRegister(ValReg))
441 void ARCOptAddrMode::changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode,
443 MachineOperand &NewOffset) {
444 bool IsStore = Ldst.mayStore();
445 unsigned BasePos, OffPos;
446 MachineOperand Src = MachineOperand::CreateImm(0xDEADBEEF);
447 AII->getBaseAndOffsetPosition(Ldst, BasePos, OffPos);
449 Register BaseReg = Ldst.getOperand(BasePos).getReg();
451 Ldst.RemoveOperand(OffPos);
452 Ldst.RemoveOperand(BasePos);
455 Src = Ldst.getOperand(BasePos - 1);
456 Ldst.RemoveOperand(BasePos - 1);
459 Ldst.setDesc(AST->getInstrInfo()->get(NewOpcode));
460 Ldst.addOperand(MachineOperand::CreateReg(NewBase, true));
462 Ldst.addOperand(Src);
463 Ldst.addOperand(MachineOperand::CreateReg(BaseReg, false));
464 Ldst.addOperand(NewOffset);
465 LLVM_DEBUG(dbgs() << "[ABAW] New Ldst: " << Ldst);
468 bool ARCOptAddrMode::processBasicBlock(MachineBasicBlock &MBB) {
469 bool Changed = false;
470 for (auto MI = MBB.begin(), ME = MBB.end(); MI != ME; ++MI) {
471 if (MI->isDebugValue())
473 if (!MI->mayLoad() && !MI->mayStore())
475 if (ARC::getPostIncOpcode(MI->getOpcode()) < 0)
477 MachineInstr *Res = tryToCombine(*MI);
480 // Res points to the next instruction. Rewind to process it
481 MI = std::prev(Res->getIterator());
487 bool ARCOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
488 if (skipFunction(MF.getFunction()))
491 AST = &MF.getSubtarget<ARCSubtarget>();
492 AII = AST->getInstrInfo();
493 MRI = &MF.getRegInfo();
494 MDT = &getAnalysis<MachineDominatorTree>();
496 bool Changed = false;
498 Changed |= processBasicBlock(MBB);
502 //===----------------------------------------------------------------------===//
503 // Public Constructor Functions
504 //===----------------------------------------------------------------------===//
506 FunctionPass *llvm::createARCOptAddrMode() { return new ARCOptAddrMode(); }