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, cl::ZeroOrMore);
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 
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 
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;
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)
132 static bool isValidIncrementOffset(int64_t Off) { return isUInt<6>(Off); }
133 
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     LLVM_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
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
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 
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 
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 *
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 
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 
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 
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 
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 
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 
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 
531 FunctionPass *llvm::createARCOptAddrMode() { return new ARCOptAddrMode(); }
532