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 
45   ARCOptAddrMode() : MachineFunctionPass(ID) {}
46 
47   StringRef getPassName() const override { return OPTADDRMODE_DESC; }
48 
49   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;
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)
121 static bool isValidIncrementOffset(int64_t Off) { return isUInt<6>(Off); }
122 
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
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
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 
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 
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 *
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 
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 
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 
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 
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 
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 
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 
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 
506 FunctionPass *llvm::createARCOptAddrMode() { return new ARCOptAddrMode(); }
507