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
30 using 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
36 namespace llvm {
37
38 static 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
47 FunctionPass *createARCOptAddrMode();
48 void initializeARCOptAddrModePass(PassRegistry &);
49 } // end namespace llvm
50
51 namespace {
52 class ARCOptAddrMode : public MachineFunctionPass {
53 public:
54 static char ID;
55
ARCOptAddrMode()56 ARCOptAddrMode() : MachineFunctionPass(ID) {}
57
getPassName() const58 StringRef getPassName() const override { return OPTADDRMODE_DESC; }
59
getAnalysisUsage(AnalysisUsage & AU) const60 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
69 private:
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
119 char ARCOptAddrMode::ID = 0;
INITIALIZE_PASS_BEGIN(ARCOptAddrMode,OPTADDRMODE_NAME,OPTADDRMODE_DESC,false,false)120 INITIALIZE_PASS_BEGIN(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false,
121 false)
122 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
123 INITIALIZE_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)
128 static bool isValidLoadStoreOffset(int64_t Off) { return isInt<9>(Off); }
129
130 // Return true if \p Off can be used as immediate operand of
131 // ADD/SUB instruction (U6 literal)
isValidIncrementOffset(int64_t Off)132 static bool isValidIncrementOffset(int64_t Off) { return isUInt<6>(Off); }
133
isAddConstantOp(const MachineInstr & MI,int64_t & Amount)134 static 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 VReg
dominatesAllUsesOf(const MachineInstr * MI,unsigned VReg,MachineDominatorTree * MDT,MachineRegisterInfo * MRI)150 static 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 (auto it = MRI->use_nodbg_begin(VReg), end = MRI->use_nodbg_end();
157 it != end; ++it) {
158 MachineInstr *User = it->getParent();
159 if (User->isPHI()) {
160 unsigned BBOperandIdx = User->getOperandNo(&*it) + 1;
161 MachineBasicBlock *MBB = User->getOperand(BBOperandIdx).getMBB();
162 if (MBB->empty()) {
163 const MachineBasicBlock *InstBB = MI->getParent();
164 assert(InstBB != MBB && "Instruction found in empty MBB");
165 if (!MDT->dominates(InstBB, MBB))
166 return false;
167 continue;
168 }
169 User = &*MBB->rbegin();
170 }
171
172 if (!MDT->dominates(MI, User))
173 return false;
174 }
175 return true;
176 }
177
178 // Return true if \p MI is load/store instruction with immediate offset
179 // which can be adjusted by \p Disp
isLoadStoreThatCanHandleDisplacement(const TargetInstrInfo * TII,const MachineInstr & MI,int64_t Disp)180 static bool isLoadStoreThatCanHandleDisplacement(const TargetInstrInfo *TII,
181 const MachineInstr &MI,
182 int64_t Disp) {
183 unsigned BasePos, OffPos;
184 if (!TII->getBaseAndOffsetPosition(MI, BasePos, OffPos))
185 return false;
186 const MachineOperand &MO = MI.getOperand(OffPos);
187 if (!MO.isImm())
188 return false;
189 int64_t Offset = MO.getImm() + Disp;
190 return isValidLoadStoreOffset(Offset);
191 }
192
noUseOfAddBeforeLoadOrStore(const MachineInstr * Add,const MachineInstr * Ldst)193 bool ARCOptAddrMode::noUseOfAddBeforeLoadOrStore(const MachineInstr *Add,
194 const MachineInstr *Ldst) {
195 Register R = Add->getOperand(0).getReg();
196 return dominatesAllUsesOf(Ldst, R, MDT, MRI);
197 }
198
tryToCombine(MachineInstr & Ldst)199 MachineInstr *ARCOptAddrMode::tryToCombine(MachineInstr &Ldst) {
200 assert(Ldst.mayLoadOrStore() && "LD/ST instruction expected");
201
202 unsigned BasePos, OffsetPos;
203
204 LLVM_DEBUG(dbgs() << "[ABAW] tryToCombine " << Ldst);
205 if (!AII->getBaseAndOffsetPosition(Ldst, BasePos, OffsetPos)) {
206 LLVM_DEBUG(dbgs() << "[ABAW] Not a recognized load/store\n");
207 return nullptr;
208 }
209
210 MachineOperand &Base = Ldst.getOperand(BasePos);
211 MachineOperand &Offset = Ldst.getOperand(OffsetPos);
212
213 assert(Base.isReg() && "Base operand must be register");
214 if (!Offset.isImm()) {
215 LLVM_DEBUG(dbgs() << "[ABAW] Offset is not immediate\n");
216 return nullptr;
217 }
218
219 Register B = Base.getReg();
220 if (Register::isStackSlot(B) || !Register::isVirtualRegister(B)) {
221 LLVM_DEBUG(dbgs() << "[ABAW] Base is not VReg\n");
222 return nullptr;
223 }
224
225 // TODO: try to generate address preincrement
226 if (Offset.getImm() != 0) {
227 LLVM_DEBUG(dbgs() << "[ABAW] Non-zero offset\n");
228 return nullptr;
229 }
230
231 for (auto &Add : MRI->use_nodbg_instructions(B)) {
232 int64_t Incr;
233 if (!isAddConstantOp(Add, Incr))
234 continue;
235 if (!isValidLoadStoreOffset(Incr))
236 continue;
237
238 SmallVector<MachineInstr *, 8> Uses;
239 MachineInstr *MoveTo = canJoinInstructions(&Ldst, &Add, &Uses);
240
241 if (!MoveTo)
242 continue;
243
244 if (!canFixPastUses(Uses, Add.getOperand(2), B))
245 continue;
246
247 LLVM_DEBUG(MachineInstr *First = &Ldst; MachineInstr *Last = &Add;
248 if (MDT->dominates(Last, First)) std::swap(First, Last);
249 dbgs() << "[ABAW] Instructions " << *First << " and " << *Last
250 << " combined\n";
251
252 );
253
254 MachineInstr *Result = Ldst.getNextNode();
255 if (MoveTo == &Add) {
256 Ldst.removeFromParent();
257 Add.getParent()->insertAfter(Add.getIterator(), &Ldst);
258 }
259 if (Result == &Add)
260 Result = Result->getNextNode();
261
262 fixPastUses(Uses, B, Incr);
263
264 int NewOpcode = ARC::getPostIncOpcode(Ldst.getOpcode());
265 assert(NewOpcode > 0 && "No postincrement form found");
266 unsigned NewBaseReg = Add.getOperand(0).getReg();
267 changeToAddrMode(Ldst, NewOpcode, NewBaseReg, Add.getOperand(2));
268 Add.eraseFromParent();
269
270 return Result;
271 }
272 return nullptr;
273 }
274
275 MachineInstr *
canJoinInstructions(MachineInstr * Ldst,MachineInstr * Add,SmallVectorImpl<MachineInstr * > * Uses)276 ARCOptAddrMode::canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add,
277 SmallVectorImpl<MachineInstr *> *Uses) {
278 assert(Ldst && Add && "NULL instruction passed");
279
280 MachineInstr *First = Add;
281 MachineInstr *Last = Ldst;
282 if (MDT->dominates(Ldst, Add))
283 std::swap(First, Last);
284 else if (!MDT->dominates(Add, Ldst))
285 return nullptr;
286
287 LLVM_DEBUG(dbgs() << "canJoinInstructions: " << *First << *Last);
288
289 unsigned BasePos, OffPos;
290
291 if (!AII->getBaseAndOffsetPosition(*Ldst, BasePos, OffPos)) {
292 LLVM_DEBUG(
293 dbgs()
294 << "[canJoinInstructions] Cannot determine base/offset position\n");
295 return nullptr;
296 }
297
298 Register BaseReg = Ldst->getOperand(BasePos).getReg();
299
300 // prohibit this:
301 // v1 = add v0, c
302 // st v1, [v0, 0]
303 // and this
304 // st v0, [v0, 0]
305 // v1 = add v0, c
306 if (Ldst->mayStore() && Ldst->getOperand(0).isReg()) {
307 Register StReg = Ldst->getOperand(0).getReg();
308 if (Add->getOperand(0).getReg() == StReg || BaseReg == StReg) {
309 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Store uses result of Add\n");
310 return nullptr;
311 }
312 }
313
314 SmallVector<MachineInstr *, 4> UsesAfterLdst;
315 SmallVector<MachineInstr *, 4> UsesAfterAdd;
316 for (MachineInstr &MI : MRI->use_nodbg_instructions(BaseReg)) {
317 if (&MI == Ldst || &MI == Add)
318 continue;
319 if (&MI != Add && MDT->dominates(Ldst, &MI))
320 UsesAfterLdst.push_back(&MI);
321 else if (!MDT->dominates(&MI, Ldst))
322 return nullptr;
323 if (MDT->dominates(Add, &MI))
324 UsesAfterAdd.push_back(&MI);
325 }
326
327 MachineInstr *Result = nullptr;
328
329 if (First == Add) {
330 // n = add b, i
331 // ...
332 // x = ld [b, o] or x = ld [n, o]
333
334 if (noUseOfAddBeforeLoadOrStore(First, Last)) {
335 Result = Last;
336 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can sink Add down to Ldst\n");
337 } else if (canHoistLoadStoreTo(Ldst, Add)) {
338 Result = First;
339 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Ldst to Add\n");
340 }
341 } else {
342 // x = ld [b, o]
343 // ...
344 // n = add b, i
345 Result = First;
346 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Add to Ldst\n");
347 }
348 if (Result && Uses)
349 *Uses = (Result == Ldst) ? UsesAfterLdst : UsesAfterAdd;
350 return Result;
351 }
352
canFixPastUses(const ArrayRef<MachineInstr * > & Uses,MachineOperand & Incr,unsigned BaseReg)353 bool ARCOptAddrMode::canFixPastUses(const ArrayRef<MachineInstr *> &Uses,
354 MachineOperand &Incr, unsigned BaseReg) {
355
356 assert(Incr.isImm() && "Expected immediate increment");
357 int64_t NewOffset = Incr.getImm();
358 for (MachineInstr *MI : Uses) {
359 int64_t Dummy;
360 if (isAddConstantOp(*MI, Dummy)) {
361 if (isValidIncrementOffset(Dummy + NewOffset))
362 continue;
363 return false;
364 }
365 if (isLoadStoreThatCanHandleDisplacement(AII, *MI, -NewOffset))
366 continue;
367 LLVM_DEBUG(dbgs() << "Instruction cannot handle displacement " << -NewOffset
368 << ": " << *MI);
369 return false;
370 }
371 return true;
372 }
373
fixPastUses(ArrayRef<MachineInstr * > Uses,unsigned NewBase,int64_t NewOffset)374 void ARCOptAddrMode::fixPastUses(ArrayRef<MachineInstr *> Uses,
375 unsigned NewBase, int64_t NewOffset) {
376
377 for (MachineInstr *MI : Uses) {
378 int64_t Amount;
379 unsigned BasePos, OffPos;
380 if (isAddConstantOp(*MI, Amount)) {
381 NewOffset += Amount;
382 assert(isValidIncrementOffset(NewOffset) &&
383 "New offset won't fit into ADD instr");
384 BasePos = 1;
385 OffPos = 2;
386 } else if (AII->getBaseAndOffsetPosition(*MI, BasePos, OffPos)) {
387 MachineOperand &MO = MI->getOperand(OffPos);
388 assert(MO.isImm() && "expected immediate operand");
389 NewOffset += MO.getImm();
390 assert(isValidLoadStoreOffset(NewOffset) &&
391 "New offset won't fit into LD/ST");
392 } else
393 llvm_unreachable("unexpected instruction");
394
395 MI->getOperand(BasePos).setReg(NewBase);
396 MI->getOperand(OffPos).setImm(NewOffset);
397 }
398 }
399
canHoistLoadStoreTo(MachineInstr * Ldst,MachineInstr * To)400 bool ARCOptAddrMode::canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) {
401 if (Ldst->getParent() != To->getParent())
402 return false;
403 MachineBasicBlock::const_iterator MI(To), ME(Ldst),
404 End(Ldst->getParent()->end());
405
406 bool IsStore = Ldst->mayStore();
407 for (; MI != ME && MI != End; ++MI) {
408 if (MI->isDebugValue())
409 continue;
410 if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() ||
411 MI->hasUnmodeledSideEffects())
412 return false;
413 if (IsStore && MI->mayLoad())
414 return false;
415 }
416
417 for (auto &O : Ldst->explicit_operands()) {
418 if (!O.isReg() || !O.isUse())
419 continue;
420 MachineInstr *OpDef = MRI->getVRegDef(O.getReg());
421 if (!OpDef || !MDT->dominates(OpDef, To))
422 return false;
423 }
424 return true;
425 }
426
427 // bool ARCOptAddrMode::canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) {
428 // // Can only sink load/store within same BB
429 // if (Ldst->getParent() != To->getParent())
430 // return false;
431 // MachineBasicBlock::const_iterator MI(Ldst), ME(To),
432 // End(Ldst->getParent()->end());
433
434 // bool IsStore = Ldst->mayStore();
435 // bool IsLoad = Ldst->mayLoad();
436
437 // Register ValReg = IsLoad ? Ldst->getOperand(0).getReg() : Register();
438 // for (; MI != ME && MI != End; ++MI) {
439 // if (MI->isDebugValue())
440 // continue;
441 // if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() ||
442 // MI->hasUnmodeledSideEffects())
443 // return false;
444 // if (IsStore && MI->mayLoad())
445 // return false;
446 // if (ValReg && MI->readsVirtualRegister(ValReg))
447 // return false;
448 // }
449 // return true;
450 // }
451
changeToAddrMode(MachineInstr & Ldst,unsigned NewOpcode,unsigned NewBase,MachineOperand & NewOffset)452 void ARCOptAddrMode::changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode,
453 unsigned NewBase,
454 MachineOperand &NewOffset) {
455 bool IsStore = Ldst.mayStore();
456 unsigned BasePos, OffPos;
457 MachineOperand Src = MachineOperand::CreateImm(0xDEADBEEF);
458 AII->getBaseAndOffsetPosition(Ldst, BasePos, OffPos);
459
460 Register BaseReg = Ldst.getOperand(BasePos).getReg();
461
462 Ldst.removeOperand(OffPos);
463 Ldst.removeOperand(BasePos);
464
465 if (IsStore) {
466 Src = Ldst.getOperand(BasePos - 1);
467 Ldst.removeOperand(BasePos - 1);
468 }
469
470 Ldst.setDesc(AST->getInstrInfo()->get(NewOpcode));
471 Ldst.addOperand(MachineOperand::CreateReg(NewBase, true));
472 if (IsStore)
473 Ldst.addOperand(Src);
474 Ldst.addOperand(MachineOperand::CreateReg(BaseReg, false));
475 Ldst.addOperand(NewOffset);
476 LLVM_DEBUG(dbgs() << "[ABAW] New Ldst: " << Ldst);
477 }
478
processBasicBlock(MachineBasicBlock & MBB)479 bool ARCOptAddrMode::processBasicBlock(MachineBasicBlock &MBB) {
480 bool Changed = false;
481 for (auto MI = MBB.begin(), ME = MBB.end(); MI != ME; ++MI) {
482 if (MI->isDebugValue())
483 continue;
484 if (!MI->mayLoad() && !MI->mayStore())
485 continue;
486 if (ARC::getPostIncOpcode(MI->getOpcode()) < 0)
487 continue;
488 MachineInstr *Res = tryToCombine(*MI);
489 if (Res) {
490 Changed = true;
491 // Res points to the next instruction. Rewind to process it
492 MI = std::prev(Res->getIterator());
493 }
494 }
495 return Changed;
496 }
497
runOnMachineFunction(MachineFunction & MF)498 bool ARCOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
499 if (skipFunction(MF.getFunction()) || KILL_PASS())
500 return false;
501
502 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
503 if (DUMP_BEFORE())
504 MF.dump();
505 #endif
506 if (VIEW_BEFORE())
507 MF.viewCFG();
508
509 AST = &MF.getSubtarget<ARCSubtarget>();
510 AII = AST->getInstrInfo();
511 MRI = &MF.getRegInfo();
512 MDT = &getAnalysis<MachineDominatorTree>();
513
514 bool Changed = false;
515 for (auto &MBB : MF)
516 Changed |= processBasicBlock(MBB);
517
518 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
519 if (DUMP_AFTER())
520 MF.dump();
521 #endif
522 if (VIEW_AFTER())
523 MF.viewCFG();
524 return Changed;
525 }
526
527 //===----------------------------------------------------------------------===//
528 // Public Constructor Functions
529 //===----------------------------------------------------------------------===//
530
createARCOptAddrMode()531 FunctionPass *llvm::createARCOptAddrMode() { return new ARCOptAddrMode(); }
532