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/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(Val: 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 llvm
50
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<MachineDominatorTree>();
64 AU.addPreserved<MachineDominatorTree>();
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 form
76 // single post-increment instruction.
77 MachineInstr *tryToCombine(MachineInstr &Ldst);
78
79 // Returns true if result of \p Add is not used before \p Ldst
80 bool noUseOfAddBeforeLoadOrStore(const MachineInstr *Add,
81 const MachineInstr *Ldst);
82
83 // Returns true if load/store instruction \p Ldst can be hoisted up to
84 // instruction \p To
85 bool canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To);
86
87 // // Returns true if load/store instruction \p Ldst can be sunk down
88 // // to instruction \p To
89 // bool canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To);
90
91 // Check if instructions \p Ldst and \p Add can be moved to become adjacent
92 // 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 use
94 // \p Ldst's base register
95 MachineInstr *canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add,
96 SmallVectorImpl<MachineInstr *> *Uses);
97
98 // Returns true if all instruction in \p Uses array can be adjusted
99 // to accomodate increment of register \p BaseReg by \p Incr
100 bool canFixPastUses(const ArrayRef<MachineInstr *> &Uses,
101 MachineOperand &Incr, unsigned BaseReg);
102
103 // Update all instructions in \p Uses to accomodate increment
104 // of \p BaseReg by \p Offset
105 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 value
110 // \p NewOffset is instruction's new offset
111 void changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode,
112 unsigned NewBase, MachineOperand &NewOffset);
113
114 bool processBasicBlock(MachineBasicBlock &MBB);
115};
116
117} // end anonymous namespace
118
119char ARCOptAddrMode::ID = 0;
120INITIALIZE_PASS_BEGIN(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false,
121 false)
122INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
123INITIALIZE_PASS_END(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false,
124 false)
125
126// Return true if \p Off can be used as immediate offset
127// operand of load/store instruction (S9 literal)
128static bool isValidLoadStoreOffset(int64_t Off) { return isInt<9>(x: Off); }
129
130// Return true if \p Off can be used as immediate operand of
131// ADD/SUB instruction (U6 literal)
132static bool isValidIncrementOffset(int64_t Off) { return isUInt<6>(x: 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(i: 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 VReg
150static 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(Reg: VReg)) {
157 const MachineInstr *User = Use.getParent();
158 if (User->isPHI()) {
159 unsigned BBOperandIdx = Use.getOperandNo() + 1;
160 MachineBasicBlock *MBB = User->getOperand(i: 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(A: InstBB, B: MBB))
165 return false;
166 continue;
167 }
168 User = &*MBB->rbegin();
169 }
170
171 if (!MDT->dominates(A: MI, B: User))
172 return false;
173 }
174 return true;
175}
176
177// Return true if \p MI is load/store instruction with immediate offset
178// which can be adjusted by \p Disp
179static bool isLoadStoreThatCanHandleDisplacement(const TargetInstrInfo *TII,
180 const MachineInstr &MI,
181 int64_t Disp) {
182 unsigned BasePos, OffPos;
183 if (!TII->getBaseAndOffsetPosition(MI, BasePos, OffsetPos&: OffPos))
184 return false;
185 const MachineOperand &MO = MI.getOperand(i: OffPos);
186 if (!MO.isImm())
187 return false;
188 int64_t Offset = MO.getImm() + Disp;
189 return isValidLoadStoreOffset(Off: Offset);
190}
191
192bool ARCOptAddrMode::noUseOfAddBeforeLoadOrStore(const MachineInstr *Add,
193 const MachineInstr *Ldst) {
194 Register R = Add->getOperand(i: 0).getReg();
195 return dominatesAllUsesOf(MI: Ldst, VReg: 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(MI: Ldst, BasePos, OffsetPos)) {
205 LLVM_DEBUG(dbgs() << "[ABAW] Not a recognized load/store\n");
206 return nullptr;
207 }
208
209 MachineOperand &Base = Ldst.getOperand(i: BasePos);
210 MachineOperand &Offset = Ldst.getOperand(i: 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::isStackSlot(Reg: B) || !Register::isVirtualRegister(Reg: B)) {
220 LLVM_DEBUG(dbgs() << "[ABAW] Base is not VReg\n");
221 return nullptr;
222 }
223
224 // TODO: try to generate address preincrement
225 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(Reg: B)) {
231 int64_t Incr;
232 if (!isAddConstantOp(MI: Add, Amount&: Incr))
233 continue;
234 if (!isValidLoadStoreOffset(Off: Incr))
235 continue;
236
237 SmallVector<MachineInstr *, 8> Uses;
238 MachineInstr *MoveTo = canJoinInstructions(Ldst: &Ldst, Add: &Add, Uses: &Uses);
239
240 if (!MoveTo)
241 continue;
242
243 if (!canFixPastUses(Uses, Incr&: Add.getOperand(i: 2), BaseReg: 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 " << *Last
249 << " combined\n";
250
251 );
252
253 MachineInstr *Result = Ldst.getNextNode();
254 if (MoveTo == &Add) {
255 Ldst.removeFromParent();
256 Add.getParent()->insertAfter(I: Add.getIterator(), MI: &Ldst);
257 }
258 if (Result == &Add)
259 Result = Result->getNextNode();
260
261 fixPastUses(Uses, BaseReg: B, Offset: Incr);
262
263 int NewOpcode = ARC::getPostIncOpcode(Ldst.getOpcode());
264 assert(NewOpcode > 0 && "No postincrement form found");
265 unsigned NewBaseReg = Add.getOperand(i: 0).getReg();
266 changeToAddrMode(Ldst, NewOpcode, NewBase: NewBaseReg, NewOffset&: Add.getOperand(i: 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(A: Ldst, B: Add))
282 std::swap(a&: First, b&: Last);
283 else if (!MDT->dominates(A: Add, B: Ldst))
284 return nullptr;
285
286 LLVM_DEBUG(dbgs() << "canJoinInstructions: " << *First << *Last);
287
288 unsigned BasePos, OffPos;
289
290 if (!AII->getBaseAndOffsetPosition(MI: *Ldst, BasePos, OffsetPos&: OffPos)) {
291 LLVM_DEBUG(
292 dbgs()
293 << "[canJoinInstructions] Cannot determine base/offset position\n");
294 return nullptr;
295 }
296
297 Register BaseReg = Ldst->getOperand(i: BasePos).getReg();
298
299 // prohibit this:
300 // v1 = add v0, c
301 // st v1, [v0, 0]
302 // and this
303 // st v0, [v0, 0]
304 // v1 = add v0, c
305 if (Ldst->mayStore() && Ldst->getOperand(i: 0).isReg()) {
306 Register StReg = Ldst->getOperand(i: 0).getReg();
307 if (Add->getOperand(i: 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(Reg: BaseReg)) {
316 if (&MI == Ldst || &MI == Add)
317 continue;
318 if (&MI != Add && MDT->dominates(A: Ldst, B: &MI))
319 UsesAfterLdst.push_back(Elt: &MI);
320 else if (!MDT->dominates(A: &MI, B: Ldst))
321 return nullptr;
322 if (MDT->dominates(A: Add, B: &MI))
323 UsesAfterAdd.push_back(Elt: &MI);
324 }
325
326 MachineInstr *Result = nullptr;
327
328 if (First == Add) {
329 // n = add b, i
330 // ...
331 // x = ld [b, o] or x = ld [n, o]
332
333 if (noUseOfAddBeforeLoadOrStore(Add: First, Ldst: Last)) {
334 Result = Last;
335 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can sink Add down to Ldst\n");
336 } else if (canHoistLoadStoreTo(Ldst, To: 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, i
344 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: *MI, Amount&: Dummy)) {
360 if (isValidIncrementOffset(Off: Dummy + NewOffset))
361 continue;
362 return false;
363 }
364 if (isLoadStoreThatCanHandleDisplacement(AII, *MI, -NewOffset))
365 continue;
366 LLVM_DEBUG(dbgs() << "Instruction cannot handle displacement " << -NewOffset
367 << ": " << *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: *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: *MI, BasePos, OffsetPos&: OffPos)) {
386 MachineOperand &MO = MI->getOperand(i: 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 } else
392 llvm_unreachable("unexpected instruction");
393
394 MI->getOperand(i: BasePos).setReg(NewBase);
395 MI->getOperand(i: 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(Reg: O.getReg());
420 if (!OpDef || !MDT->dominates(A: OpDef, B: 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 BB
428// 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(Val: 0xDEADBEEF);
457 AII->getBaseAndOffsetPosition(MI: Ldst, BasePos, OffsetPos&: OffPos);
458
459 Register BaseReg = Ldst.getOperand(i: BasePos).getReg();
460
461 Ldst.removeOperand(OpNo: OffPos);
462 Ldst.removeOperand(OpNo: BasePos);
463
464 if (IsStore) {
465 Src = Ldst.getOperand(i: BasePos - 1);
466 Ldst.removeOperand(OpNo: BasePos - 1);
467 }
468
469 Ldst.setDesc(AST->getInstrInfo()->get(NewOpcode));
470 Ldst.addOperand(Op: MachineOperand::CreateReg(Reg: NewBase, isDef: true));
471 if (IsStore)
472 Ldst.addOperand(Op: Src);
473 Ldst.addOperand(Op: MachineOperand::CreateReg(Reg: BaseReg, isDef: false));
474 Ldst.addOperand(Op: 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(Ldst&: *MI);
488 if (Res) {
489 Changed = true;
490 // Res points to the next instruction. Rewind to process it
491 MI = std::prev(x: Res->getIterator());
492 }
493 }
494 return Changed;
495}
496
497bool ARCOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
498 if (skipFunction(F: MF.getFunction()) || KILL_PASS())
499 return false;
500
501#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
502 if (DUMP_BEFORE())
503 MF.dump();
504#endif
505 if (VIEW_BEFORE())
506 MF.viewCFG();
507
508 AST = &MF.getSubtarget<ARCSubtarget>();
509 AII = AST->getInstrInfo();
510 MRI = &MF.getRegInfo();
511 MDT = &getAnalysis<MachineDominatorTree>();
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#endif
521 if (VIEW_AFTER())
522 MF.viewCFG();
523 return Changed;
524}
525
526//===----------------------------------------------------------------------===//
527// Public Constructor Functions
528//===----------------------------------------------------------------------===//
529
530FunctionPass *llvm::createARCOptAddrMode() { return new ARCOptAddrMode(); }
531

source code of llvm/lib/Target/ARC/ARCOptAddrMode.cpp