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
29using 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
35namespace llvm {
36FunctionPass *createARCOptAddrMode();
37void initializeARCOptAddrModePass(PassRegistry &);
38} // end namespace llvm
39
40namespace {
41class ARCOptAddrMode : public MachineFunctionPass {
42public:
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
58private:
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
108char ARCOptAddrMode::ID = 0;
109INITIALIZE_PASS_BEGIN(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false,
110                      false)
111INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
112INITIALIZE_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)
117static 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)
121static bool isValidIncrementOffset(int64_t Off) { return isUInt<6>(Off); }
122
123static 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
139static 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
169static 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
182bool 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
188MachineInstr *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
264MachineInstr *
265ARCOptAddrMode::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
342bool 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
363void 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
389bool 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
416bool 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
441void 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
468bool 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
487bool 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
506FunctionPass *llvm::createARCOptAddrMode() { return new ARCOptAddrMode(); }
507