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/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
28
29 using namespace llvm;
30
31 #define OPTADDRMODE_DESC "ARC load/store address mode"
32 #define OPTADDRMODE_NAME "arc-addr-mode"
33 #define DEBUG_TYPE "arc-addr-mode"
34
35 namespace llvm {
36 FunctionPass *createARCOptAddrMode();
37 void initializeARCOptAddrModePass(PassRegistry &);
38 } // end namespace llvm
39
40 namespace {
41 class ARCOptAddrMode : public MachineFunctionPass {
42 public:
43 static char ID;
44
ARCOptAddrMode()45 ARCOptAddrMode() : MachineFunctionPass(ID) {}
46
getPassName() const47 StringRef getPassName() const override { return OPTADDRMODE_DESC; }
48
getAnalysisUsage(AnalysisUsage & AU) const49 void getAnalysisUsage(AnalysisUsage &AU) const override {
50 AU.setPreservesCFG();
51 MachineFunctionPass::getAnalysisUsage(AU);
52 AU.addRequired<MachineDominatorTree>();
53 AU.addPreserved<MachineDominatorTree>();
54 }
55
56 bool runOnMachineFunction(MachineFunction &MF) override;
57
58 private:
59 const ARCSubtarget *AST = nullptr;
60 const ARCInstrInfo *AII = nullptr;
61 MachineRegisterInfo *MRI = nullptr;
62 MachineDominatorTree *MDT = nullptr;
63
64 // Tries to combine \p Ldst with increment of its base register to form
65 // single post-increment instruction.
66 MachineInstr *tryToCombine(MachineInstr &Ldst);
67
68 // Returns true if result of \p Add is not used before \p Ldst
69 bool noUseOfAddBeforeLoadOrStore(const MachineInstr *Add,
70 const MachineInstr *Ldst);
71
72 // Returns true if load/store instruction \p Ldst can be hoisted up to
73 // instruction \p To
74 bool canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To);
75
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);
79
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);
86
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);
91
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,
95 int64_t Offset);
96
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);
102
103 bool processBasicBlock(MachineBasicBlock &MBB);
104 };
105
106 } // end anonymous namespace
107
108 char ARCOptAddrMode::ID = 0;
INITIALIZE_PASS_BEGIN(ARCOptAddrMode,OPTADDRMODE_NAME,OPTADDRMODE_DESC,false,false)109 INITIALIZE_PASS_BEGIN(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false,
110 false)
111 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
112 INITIALIZE_PASS_END(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false,
113 false)
114
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); }
118
119 // Return true if \p Off can be used as immediate operand of
120 // ADD/SUB instruction (U6 literal)
isValidIncrementOffset(int64_t Off)121 static bool isValidIncrementOffset(int64_t Off) { return isUInt<6>(Off); }
122
isAddConstantOp(const MachineInstr & MI,int64_t & Amount)123 static bool isAddConstantOp(const MachineInstr &MI, int64_t &Amount) {
124 int64_t Sign = 1;
125 switch (MI.getOpcode()) {
126 case ARC::SUB_rru6:
127 Sign = -1;
128 LLVM_FALLTHROUGH;
129 case ARC::ADD_rru6:
130 assert(MI.getOperand(2).isImm() && "Expected immediate operand");
131 Amount = Sign * MI.getOperand(2).getImm();
132 return true;
133 default:
134 return false;
135 }
136 }
137
138 // Return true if \p MI dominates of uses of virtual register \p VReg
dominatesAllUsesOf(const MachineInstr * MI,unsigned VReg,MachineDominatorTree * MDT,MachineRegisterInfo * MRI)139 static bool dominatesAllUsesOf(const MachineInstr *MI, unsigned VReg,
140 MachineDominatorTree *MDT,
141 MachineRegisterInfo *MRI) {
142
143 assert(Register::isVirtualRegister(VReg) && "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
isLoadStoreThatCanHandleDisplacement(const TargetInstrInfo * TII,const MachineInstr & MI,int64_t 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
noUseOfAddBeforeLoadOrStore(const MachineInstr * Add,const MachineInstr * Ldst)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);
186 }
187
tryToCombine(MachineInstr & Ldst)188 MachineInstr *ARCOptAddrMode::tryToCombine(MachineInstr &Ldst) {
189 assert(Ldst.mayLoadOrStore() && "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 Register B = Base.getReg();
209 if (Register::isStackSlot(B) || !Register::isVirtualRegister(B)) {
210 LLVM_DEBUG(dbgs() << "[ABAW] Base is not VReg\n");
211 return nullptr;
212 }
213
214 // TODO: try to generate address preincrement
215 if (Offset.getImm() != 0) {
216 LLVM_DEBUG(dbgs() << "[ABAW] Non-zero offset\n");
217 return nullptr;
218 }
219
220 for (auto &Add : MRI->use_nodbg_instructions(B)) {
221 int64_t Incr;
222 if (!isAddConstantOp(Add, Incr))
223 continue;
224 if (!isValidLoadStoreOffset(Incr))
225 continue;
226
227 SmallVector<MachineInstr *, 8> Uses;
228 MachineInstr *MoveTo = canJoinInstructions(&Ldst, &Add, &Uses);
229
230 if (!MoveTo)
231 continue;
232
233 if (!canFixPastUses(Uses, Add.getOperand(2), B))
234 continue;
235
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
239 << " combined\n";
240
241 );
242
243 MachineInstr *Result = Ldst.getNextNode();
244 if (MoveTo == &Add) {
245 Ldst.removeFromParent();
246 Add.getParent()->insertAfter(Add.getIterator(), &Ldst);
247 }
248 if (Result == &Add)
249 Result = Result->getNextNode();
250
251 fixPastUses(Uses, B, Incr);
252
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();
258
259 return Result;
260 }
261 return nullptr;
262 }
263
264 MachineInstr *
canJoinInstructions(MachineInstr * Ldst,MachineInstr * Add,SmallVectorImpl<MachineInstr * > * Uses)265 ARCOptAddrMode::canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add,
266 SmallVectorImpl<MachineInstr *> *Uses) {
267 assert(Ldst && Add && "NULL instruction passed");
268
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))
274 return nullptr;
275
276 LLVM_DEBUG(dbgs() << "canJoinInstructions: " << *First << *Last);
277
278 unsigned BasePos, OffPos;
279
280 if (!AII->getBaseAndOffsetPosition(*Ldst, BasePos, OffPos)) {
281 LLVM_DEBUG(
282 dbgs()
283 << "[canJoinInstructions] Cannot determine base/offset position\n");
284 return nullptr;
285 }
286
287 Register BaseReg = Ldst->getOperand(BasePos).getReg();
288
289 // prohibit this:
290 // v1 = add v0, c
291 // st v1, [v0, 0]
292 // and this
293 // st v0, [v0, 0]
294 // v1 = add v0, c
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");
299 return nullptr;
300 }
301 }
302
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)
307 continue;
308 if (&MI != Add && MDT->dominates(Ldst, &MI))
309 UsesAfterLdst.push_back(&MI);
310 else if (!MDT->dominates(&MI, Ldst))
311 return nullptr;
312 if (MDT->dominates(Add, &MI))
313 UsesAfterAdd.push_back(&MI);
314 }
315
316 MachineInstr *Result = nullptr;
317
318 if (First == Add) {
319 // n = add b, i
320 // ...
321 // x = ld [b, o] or x = ld [n, o]
322
323 if (noUseOfAddBeforeLoadOrStore(First, Last)) {
324 Result = Last;
325 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can sink Add down to Ldst\n");
326 } else if (canHoistLoadStoreTo(Ldst, Add)) {
327 Result = First;
328 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Ldst to Add\n");
329 }
330 } else {
331 // x = ld [b, o]
332 // ...
333 // n = add b, i
334 Result = First;
335 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Add to Ldst\n");
336 }
337 if (Result && Uses)
338 *Uses = (Result == Ldst) ? UsesAfterLdst : UsesAfterAdd;
339 return Result;
340 }
341
canFixPastUses(const ArrayRef<MachineInstr * > & Uses,MachineOperand & Incr,unsigned BaseReg)342 bool ARCOptAddrMode::canFixPastUses(const ArrayRef<MachineInstr *> &Uses,
343 MachineOperand &Incr, unsigned BaseReg) {
344
345 assert(Incr.isImm() && "Expected immediate increment");
346 int64_t NewOffset = Incr.getImm();
347 for (MachineInstr *MI : Uses) {
348 int64_t Dummy;
349 if (isAddConstantOp(*MI, Dummy)) {
350 if (isValidIncrementOffset(Dummy + NewOffset))
351 continue;
352 return false;
353 }
354 if (isLoadStoreThatCanHandleDisplacement(AII, *MI, -NewOffset))
355 continue;
356 LLVM_DEBUG(dbgs() << "Instruction cannot handle displacement " << -NewOffset
357 << ": " << *MI);
358 return false;
359 }
360 return true;
361 }
362
fixPastUses(ArrayRef<MachineInstr * > Uses,unsigned NewBase,int64_t NewOffset)363 void ARCOptAddrMode::fixPastUses(ArrayRef<MachineInstr *> Uses,
364 unsigned NewBase, int64_t NewOffset) {
365
366 for (MachineInstr *MI : Uses) {
367 int64_t Amount;
368 unsigned BasePos, OffPos;
369 if (isAddConstantOp(*MI, Amount)) {
370 NewOffset += Amount;
371 assert(isValidIncrementOffset(NewOffset) &&
372 "New offset won't fit into ADD instr");
373 BasePos = 1;
374 OffPos = 2;
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");
381 } else
382 llvm_unreachable("unexpected instruction");
383
384 MI->getOperand(BasePos).setReg(NewBase);
385 MI->getOperand(OffPos).setImm(NewOffset);
386 }
387 }
388
canHoistLoadStoreTo(MachineInstr * Ldst,MachineInstr * To)389 bool ARCOptAddrMode::canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) {
390 if (Ldst->getParent() != To->getParent())
391 return false;
392 MachineBasicBlock::const_iterator MI(To), ME(Ldst),
393 End(Ldst->getParent()->end());
394
395 bool IsStore = Ldst->mayStore();
396 for (; MI != ME && MI != End; ++MI) {
397 if (MI->isDebugValue())
398 continue;
399 if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() ||
400 MI->hasUnmodeledSideEffects())
401 return false;
402 if (IsStore && MI->mayLoad())
403 return false;
404 }
405
406 for (auto &O : Ldst->explicit_operands()) {
407 if (!O.isReg() || !O.isUse())
408 continue;
409 MachineInstr *OpDef = MRI->getVRegDef(O.getReg());
410 if (!OpDef || !MDT->dominates(OpDef, To))
411 return false;
412 }
413 return true;
414 }
415
canSinkLoadStoreTo(MachineInstr * Ldst,MachineInstr * To)416 bool ARCOptAddrMode::canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) {
417 // Can only sink load/store within same BB
418 if (Ldst->getParent() != To->getParent())
419 return false;
420 MachineBasicBlock::const_iterator MI(Ldst), ME(To),
421 End(Ldst->getParent()->end());
422
423 bool IsStore = Ldst->mayStore();
424 bool IsLoad = Ldst->mayLoad();
425
426 Register ValReg = IsLoad ? Ldst->getOperand(0).getReg() : Register();
427 for (; MI != ME && MI != End; ++MI) {
428 if (MI->isDebugValue())
429 continue;
430 if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() ||
431 MI->hasUnmodeledSideEffects())
432 return false;
433 if (IsStore && MI->mayLoad())
434 return false;
435 if (ValReg && MI->readsVirtualRegister(ValReg))
436 return false;
437 }
438 return true;
439 }
440
changeToAddrMode(MachineInstr & Ldst,unsigned NewOpcode,unsigned NewBase,MachineOperand & NewOffset)441 void ARCOptAddrMode::changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode,
442 unsigned NewBase,
443 MachineOperand &NewOffset) {
444 bool IsStore = Ldst.mayStore();
445 unsigned BasePos, OffPos;
446 MachineOperand Src = MachineOperand::CreateImm(0xDEADBEEF);
447 AII->getBaseAndOffsetPosition(Ldst, BasePos, OffPos);
448
449 Register BaseReg = Ldst.getOperand(BasePos).getReg();
450
451 Ldst.RemoveOperand(OffPos);
452 Ldst.RemoveOperand(BasePos);
453
454 if (IsStore) {
455 Src = Ldst.getOperand(BasePos - 1);
456 Ldst.RemoveOperand(BasePos - 1);
457 }
458
459 Ldst.setDesc(AST->getInstrInfo()->get(NewOpcode));
460 Ldst.addOperand(MachineOperand::CreateReg(NewBase, true));
461 if (IsStore)
462 Ldst.addOperand(Src);
463 Ldst.addOperand(MachineOperand::CreateReg(BaseReg, false));
464 Ldst.addOperand(NewOffset);
465 LLVM_DEBUG(dbgs() << "[ABAW] New Ldst: " << Ldst);
466 }
467
processBasicBlock(MachineBasicBlock & MBB)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())
472 continue;
473 if (!MI->mayLoad() && !MI->mayStore())
474 continue;
475 if (ARC::getPostIncOpcode(MI->getOpcode()) < 0)
476 continue;
477 MachineInstr *Res = tryToCombine(*MI);
478 if (Res) {
479 Changed = true;
480 // Res points to the next instruction. Rewind to process it
481 MI = std::prev(Res->getIterator());
482 }
483 }
484 return Changed;
485 }
486
runOnMachineFunction(MachineFunction & MF)487 bool ARCOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
488 if (skipFunction(MF.getFunction()))
489 return false;
490
491 AST = &MF.getSubtarget<ARCSubtarget>();
492 AII = AST->getInstrInfo();
493 MRI = &MF.getRegInfo();
494 MDT = &getAnalysis<MachineDominatorTree>();
495
496 bool Changed = false;
497 for (auto &MBB : MF)
498 Changed |= processBasicBlock(MBB);
499 return Changed;
500 }
501
502 //===----------------------------------------------------------------------===//
503 // Public Constructor Functions
504 //===----------------------------------------------------------------------===//
505
createARCOptAddrMode()506 FunctionPass *llvm::createARCOptAddrMode() { return new ARCOptAddrMode(); }
507