Add missing closing namespace comment.
[opencl/llvm.git] / lib / Target / AArch64 / AArch64LoadStoreOptimizer.cpp
1 //=- AArch64LoadStoreOptimizer.cpp - AArch64 load/store opt. pass -*- C++ -*-=//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains a pass that performs load / store related peephole
11 // optimizations. This pass should be run after register allocation.
12 //
13 //===----------------------------------------------------------------------===//
15 #include "AArch64InstrInfo.h"
16 #include "AArch64Subtarget.h"
17 #include "MCTargetDesc/AArch64AddressingModes.h"
18 #include "llvm/ADT/BitVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/CodeGen/MachineBasicBlock.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/MachineInstr.h"
23 #include "llvm/CodeGen/MachineInstrBuilder.h"
24 #include "llvm/Support/CommandLine.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/ErrorHandling.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include "llvm/Target/TargetInstrInfo.h"
29 #include "llvm/Target/TargetMachine.h"
30 #include "llvm/Target/TargetRegisterInfo.h"
31 using namespace llvm;
33 #define DEBUG_TYPE "aarch64-ldst-opt"
35 /// AArch64AllocLoadStoreOpt - Post-register allocation pass to combine
36 /// load / store instructions to form ldp / stp instructions.
38 STATISTIC(NumPairCreated, "Number of load/store pair instructions generated");
39 STATISTIC(NumPostFolded, "Number of post-index updates folded");
40 STATISTIC(NumPreFolded, "Number of pre-index updates folded");
41 STATISTIC(NumUnscaledPairCreated,
42           "Number of load/store from unscaled generated");
44 static cl::opt<unsigned> ScanLimit("aarch64-load-store-scan-limit",
45                                    cl::init(20), cl::Hidden);
47 // Place holder while testing unscaled load/store combining
48 static cl::opt<bool> EnableAArch64UnscaledMemOp(
49     "aarch64-unscaled-mem-op", cl::Hidden,
50     cl::desc("Allow AArch64 unscaled load/store combining"), cl::init(true));
52 namespace {
53 struct AArch64LoadStoreOpt : public MachineFunctionPass {
54   static char ID;
55   AArch64LoadStoreOpt() : MachineFunctionPass(ID) {}
57   const AArch64InstrInfo *TII;
58   const TargetRegisterInfo *TRI;
60   // Scan the instructions looking for a load/store that can be combined
61   // with the current instruction into a load/store pair.
62   // Return the matching instruction if one is found, else MBB->end().
63   // If a matching instruction is found, MergeForward is set to true if the
64   // merge is to remove the first instruction and replace the second with
65   // a pair-wise insn, and false if the reverse is true.
66   MachineBasicBlock::iterator findMatchingInsn(MachineBasicBlock::iterator I,
67                                                bool &MergeForward,
68                                                unsigned Limit);
69   // Merge the two instructions indicated into a single pair-wise instruction.
70   // If MergeForward is true, erase the first instruction and fold its
71   // operation into the second. If false, the reverse. Return the instruction
72   // following the first instruction (which may change during processing).
73   MachineBasicBlock::iterator
74   mergePairedInsns(MachineBasicBlock::iterator I,
75                    MachineBasicBlock::iterator Paired, bool MergeForward);
77   // Scan the instruction list to find a base register update that can
78   // be combined with the current instruction (a load or store) using
79   // pre or post indexed addressing with writeback. Scan forwards.
80   MachineBasicBlock::iterator
81   findMatchingUpdateInsnForward(MachineBasicBlock::iterator I, unsigned Limit,
82                                 int Value);
84   // Scan the instruction list to find a base register update that can
85   // be combined with the current instruction (a load or store) using
86   // pre or post indexed addressing with writeback. Scan backwards.
87   MachineBasicBlock::iterator
88   findMatchingUpdateInsnBackward(MachineBasicBlock::iterator I, unsigned Limit);
90   // Merge a pre-index base register update into a ld/st instruction.
91   MachineBasicBlock::iterator
92   mergePreIdxUpdateInsn(MachineBasicBlock::iterator I,
93                         MachineBasicBlock::iterator Update);
95   // Merge a post-index base register update into a ld/st instruction.
96   MachineBasicBlock::iterator
97   mergePostIdxUpdateInsn(MachineBasicBlock::iterator I,
98                          MachineBasicBlock::iterator Update);
100   bool optimizeBlock(MachineBasicBlock &MBB);
102   bool runOnMachineFunction(MachineFunction &Fn) override;
104   const char *getPassName() const override {
105     return "AArch64 load / store optimization pass";
106   }
108 private:
109   int getMemSize(MachineInstr *MemMI);
110 };
111 char AArch64LoadStoreOpt::ID = 0;
112 } // namespace
114 static bool isUnscaledLdst(unsigned Opc) {
115   switch (Opc) {
116   default:
117     return false;
118   case AArch64::STURSi:
119     return true;
120   case AArch64::STURDi:
121     return true;
122   case AArch64::STURQi:
123     return true;
124   case AArch64::STURWi:
125     return true;
126   case AArch64::STURXi:
127     return true;
128   case AArch64::LDURSi:
129     return true;
130   case AArch64::LDURDi:
131     return true;
132   case AArch64::LDURQi:
133     return true;
134   case AArch64::LDURWi:
135     return true;
136   case AArch64::LDURXi:
137     return true;
138   }
141 // Size in bytes of the data moved by an unscaled load or store
142 int AArch64LoadStoreOpt::getMemSize(MachineInstr *MemMI) {
143   switch (MemMI->getOpcode()) {
144   default:
145     llvm_unreachable("Opcode has unknown size!");
146   case AArch64::STRSui:
147   case AArch64::STURSi:
148     return 4;
149   case AArch64::STRDui:
150   case AArch64::STURDi:
151     return 8;
152   case AArch64::STRQui:
153   case AArch64::STURQi:
154     return 16;
155   case AArch64::STRWui:
156   case AArch64::STURWi:
157     return 4;
158   case AArch64::STRXui:
159   case AArch64::STURXi:
160     return 8;
161   case AArch64::LDRSui:
162   case AArch64::LDURSi:
163     return 4;
164   case AArch64::LDRDui:
165   case AArch64::LDURDi:
166     return 8;
167   case AArch64::LDRQui:
168   case AArch64::LDURQi:
169     return 16;
170   case AArch64::LDRWui:
171   case AArch64::LDURWi:
172     return 4;
173   case AArch64::LDRXui:
174   case AArch64::LDURXi:
175     return 8;
176   }
179 static unsigned getMatchingPairOpcode(unsigned Opc) {
180   switch (Opc) {
181   default:
182     llvm_unreachable("Opcode has no pairwise equivalent!");
183   case AArch64::STRSui:
184   case AArch64::STURSi:
185     return AArch64::STPSi;
186   case AArch64::STRDui:
187   case AArch64::STURDi:
188     return AArch64::STPDi;
189   case AArch64::STRQui:
190   case AArch64::STURQi:
191     return AArch64::STPQi;
192   case AArch64::STRWui:
193   case AArch64::STURWi:
194     return AArch64::STPWi;
195   case AArch64::STRXui:
196   case AArch64::STURXi:
197     return AArch64::STPXi;
198   case AArch64::LDRSui:
199   case AArch64::LDURSi:
200     return AArch64::LDPSi;
201   case AArch64::LDRDui:
202   case AArch64::LDURDi:
203     return AArch64::LDPDi;
204   case AArch64::LDRQui:
205   case AArch64::LDURQi:
206     return AArch64::LDPQi;
207   case AArch64::LDRWui:
208   case AArch64::LDURWi:
209     return AArch64::LDPWi;
210   case AArch64::LDRXui:
211   case AArch64::LDURXi:
212     return AArch64::LDPXi;
213   }
216 static unsigned getPreIndexedOpcode(unsigned Opc) {
217   switch (Opc) {
218   default:
219     llvm_unreachable("Opcode has no pre-indexed equivalent!");
220   case AArch64::STRSui:
221     return AArch64::STRSpre;
222   case AArch64::STRDui:
223     return AArch64::STRDpre;
224   case AArch64::STRQui:
225     return AArch64::STRQpre;
226   case AArch64::STRWui:
227     return AArch64::STRWpre;
228   case AArch64::STRXui:
229     return AArch64::STRXpre;
230   case AArch64::LDRSui:
231     return AArch64::LDRSpre;
232   case AArch64::LDRDui:
233     return AArch64::LDRDpre;
234   case AArch64::LDRQui:
235     return AArch64::LDRQpre;
236   case AArch64::LDRWui:
237     return AArch64::LDRWpre;
238   case AArch64::LDRXui:
239     return AArch64::LDRXpre;
240   }
243 static unsigned getPostIndexedOpcode(unsigned Opc) {
244   switch (Opc) {
245   default:
246     llvm_unreachable("Opcode has no post-indexed wise equivalent!");
247   case AArch64::STRSui:
248     return AArch64::STRSpost;
249   case AArch64::STRDui:
250     return AArch64::STRDpost;
251   case AArch64::STRQui:
252     return AArch64::STRQpost;
253   case AArch64::STRWui:
254     return AArch64::STRWpost;
255   case AArch64::STRXui:
256     return AArch64::STRXpost;
257   case AArch64::LDRSui:
258     return AArch64::LDRSpost;
259   case AArch64::LDRDui:
260     return AArch64::LDRDpost;
261   case AArch64::LDRQui:
262     return AArch64::LDRQpost;
263   case AArch64::LDRWui:
264     return AArch64::LDRWpost;
265   case AArch64::LDRXui:
266     return AArch64::LDRXpost;
267   }
270 MachineBasicBlock::iterator
271 AArch64LoadStoreOpt::mergePairedInsns(MachineBasicBlock::iterator I,
272                                       MachineBasicBlock::iterator Paired,
273                                       bool MergeForward) {
274   MachineBasicBlock::iterator NextI = I;
275   ++NextI;
276   // If NextI is the second of the two instructions to be merged, we need
277   // to skip one further. Either way we merge will invalidate the iterator,
278   // and we don't need to scan the new instruction, as it's a pairwise
279   // instruction, which we're not considering for further action anyway.
280   if (NextI == Paired)
281     ++NextI;
283   bool IsUnscaled = isUnscaledLdst(I->getOpcode());
284   int OffsetStride =
285       IsUnscaled && EnableAArch64UnscaledMemOp ? getMemSize(I) : 1;
287   unsigned NewOpc = getMatchingPairOpcode(I->getOpcode());
288   // Insert our new paired instruction after whichever of the paired
289   // instructions MergeForward indicates.
290   MachineBasicBlock::iterator InsertionPoint = MergeForward ? Paired : I;
291   // Also based on MergeForward is from where we copy the base register operand
292   // so we get the flags compatible with the input code.
293   MachineOperand &BaseRegOp =
294       MergeForward ? Paired->getOperand(1) : I->getOperand(1);
296   // Which register is Rt and which is Rt2 depends on the offset order.
297   MachineInstr *RtMI, *Rt2MI;
298   if (I->getOperand(2).getImm() ==
299       Paired->getOperand(2).getImm() + OffsetStride) {
300     RtMI = Paired;
301     Rt2MI = I;
302   } else {
303     RtMI = I;
304     Rt2MI = Paired;
305   }
306   // Handle Unscaled
307   int OffsetImm = RtMI->getOperand(2).getImm();
308   if (IsUnscaled && EnableAArch64UnscaledMemOp)
309     OffsetImm /= OffsetStride;
311   // Construct the new instruction.
312   MachineInstrBuilder MIB = BuildMI(*I->getParent(), InsertionPoint,
313                                     I->getDebugLoc(), TII->get(NewOpc))
314                                 .addOperand(RtMI->getOperand(0))
315                                 .addOperand(Rt2MI->getOperand(0))
316                                 .addOperand(BaseRegOp)
317                                 .addImm(OffsetImm);
318   (void)MIB;
320   // FIXME: Do we need/want to copy the mem operands from the source
321   //        instructions? Probably. What uses them after this?
323   DEBUG(dbgs() << "Creating pair load/store. Replacing instructions:\n    ");
324   DEBUG(I->print(dbgs()));
325   DEBUG(dbgs() << "    ");
326   DEBUG(Paired->print(dbgs()));
327   DEBUG(dbgs() << "  with instruction:\n    ");
328   DEBUG(((MachineInstr *)MIB)->print(dbgs()));
329   DEBUG(dbgs() << "\n");
331   // Erase the old instructions.
332   I->eraseFromParent();
333   Paired->eraseFromParent();
335   return NextI;
338 /// trackRegDefsUses - Remember what registers the specified instruction uses
339 /// and modifies.
340 static void trackRegDefsUses(MachineInstr *MI, BitVector &ModifiedRegs,
341                              BitVector &UsedRegs,
342                              const TargetRegisterInfo *TRI) {
343   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
344     MachineOperand &MO = MI->getOperand(i);
345     if (MO.isRegMask())
346       ModifiedRegs.setBitsNotInMask(MO.getRegMask());
348     if (!MO.isReg())
349       continue;
350     unsigned Reg = MO.getReg();
351     if (MO.isDef()) {
352       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
353         ModifiedRegs.set(*AI);
354     } else {
355       assert(MO.isUse() && "Reg operand not a def and not a use?!?");
356       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
357         UsedRegs.set(*AI);
358     }
359   }
362 static bool inBoundsForPair(bool IsUnscaled, int Offset, int OffsetStride) {
363   if (!IsUnscaled && (Offset > 63 || Offset < -64))
364     return false;
365   if (IsUnscaled) {
366     // Convert the byte-offset used by unscaled into an "element" offset used
367     // by the scaled pair load/store instructions.
368     int ElemOffset = Offset / OffsetStride;
369     if (ElemOffset > 63 || ElemOffset < -64)
370       return false;
371   }
372   return true;
375 // Do alignment, specialized to power of 2 and for signed ints,
376 // avoiding having to do a C-style cast from uint_64t to int when
377 // using RoundUpToAlignment from include/llvm/Support/MathExtras.h.
378 // FIXME: Move this function to include/MathExtras.h?
379 static int alignTo(int Num, int PowOf2) {
380   return (Num + PowOf2 - 1) & ~(PowOf2 - 1);
383 /// findMatchingInsn - Scan the instructions looking for a load/store that can
384 /// be combined with the current instruction into a load/store pair.
385 MachineBasicBlock::iterator
386 AArch64LoadStoreOpt::findMatchingInsn(MachineBasicBlock::iterator I,
387                                       bool &MergeForward, unsigned Limit) {
388   MachineBasicBlock::iterator E = I->getParent()->end();
389   MachineBasicBlock::iterator MBBI = I;
390   MachineInstr *FirstMI = I;
391   ++MBBI;
393   int Opc = FirstMI->getOpcode();
394   bool MayLoad = FirstMI->mayLoad();
395   bool IsUnscaled = isUnscaledLdst(Opc);
396   unsigned Reg = FirstMI->getOperand(0).getReg();
397   unsigned BaseReg = FirstMI->getOperand(1).getReg();
398   int Offset = FirstMI->getOperand(2).getImm();
400   // Early exit if the first instruction modifies the base register.
401   // e.g., ldr x0, [x0]
402   // Early exit if the offset if not possible to match. (6 bits of positive
403   // range, plus allow an extra one in case we find a later insn that matches
404   // with Offset-1
405   if (FirstMI->modifiesRegister(BaseReg, TRI))
406     return E;
407   int OffsetStride =
408       IsUnscaled && EnableAArch64UnscaledMemOp ? getMemSize(FirstMI) : 1;
409   if (!inBoundsForPair(IsUnscaled, Offset, OffsetStride))
410     return E;
412   // Track which registers have been modified and used between the first insn
413   // (inclusive) and the second insn.
414   BitVector ModifiedRegs, UsedRegs;
415   ModifiedRegs.resize(TRI->getNumRegs());
416   UsedRegs.resize(TRI->getNumRegs());
417   for (unsigned Count = 0; MBBI != E && Count < Limit; ++MBBI) {
418     MachineInstr *MI = MBBI;
419     // Skip DBG_VALUE instructions. Otherwise debug info can affect the
420     // optimization by changing how far we scan.
421     if (MI->isDebugValue())
422       continue;
424     // Now that we know this is a real instruction, count it.
425     ++Count;
427     if (Opc == MI->getOpcode() && MI->getOperand(2).isImm()) {
428       // If we've found another instruction with the same opcode, check to see
429       // if the base and offset are compatible with our starting instruction.
430       // These instructions all have scaled immediate operands, so we just
431       // check for +1/-1. Make sure to check the new instruction offset is
432       // actually an immediate and not a symbolic reference destined for
433       // a relocation.
434       //
435       // Pairwise instructions have a 7-bit signed offset field. Single insns
436       // have a 12-bit unsigned offset field. To be a valid combine, the
437       // final offset must be in range.
438       unsigned MIBaseReg = MI->getOperand(1).getReg();
439       int MIOffset = MI->getOperand(2).getImm();
440       if (BaseReg == MIBaseReg && ((Offset == MIOffset + OffsetStride) ||
441                                    (Offset + OffsetStride == MIOffset))) {
442         int MinOffset = Offset < MIOffset ? Offset : MIOffset;
443         // If this is a volatile load/store that otherwise matched, stop looking
444         // as something is going on that we don't have enough information to
445         // safely transform. Similarly, stop if we see a hint to avoid pairs.
446         if (MI->hasOrderedMemoryRef() || TII->isLdStPairSuppressed(MI))
447           return E;
448         // If the resultant immediate offset of merging these instructions
449         // is out of range for a pairwise instruction, bail and keep looking.
450         bool MIIsUnscaled = isUnscaledLdst(MI->getOpcode());
451         if (!inBoundsForPair(MIIsUnscaled, MinOffset, OffsetStride)) {
452           trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
453           continue;
454         }
455         // If the alignment requirements of the paired (scaled) instruction
456         // can't express the offset of the unscaled input, bail and keep
457         // looking.
458         if (IsUnscaled && EnableAArch64UnscaledMemOp &&
459             (alignTo(MinOffset, OffsetStride) != MinOffset)) {
460           trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
461           continue;
462         }
463         // If the destination register of the loads is the same register, bail
464         // and keep looking. A load-pair instruction with both destination
465         // registers the same is UNPREDICTABLE and will result in an exception.
466         if (MayLoad && Reg == MI->getOperand(0).getReg()) {
467           trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
468           continue;
469         }
471         // If the Rt of the second instruction was not modified or used between
472         // the two instructions, we can combine the second into the first.
473         if (!ModifiedRegs[MI->getOperand(0).getReg()] &&
474             !UsedRegs[MI->getOperand(0).getReg()]) {
475           MergeForward = false;
476           return MBBI;
477         }
479         // Likewise, if the Rt of the first instruction is not modified or used
480         // between the two instructions, we can combine the first into the
481         // second.
482         if (!ModifiedRegs[FirstMI->getOperand(0).getReg()] &&
483             !UsedRegs[FirstMI->getOperand(0).getReg()]) {
484           MergeForward = true;
485           return MBBI;
486         }
487         // Unable to combine these instructions due to interference in between.
488         // Keep looking.
489       }
490     }
492     // If the instruction wasn't a matching load or store, but does (or can)
493     // modify memory, stop searching, as we don't have alias analysis or
494     // anything like that to tell us whether the access is tromping on the
495     // locations we care about. The big one we want to catch is calls.
496     //
497     // FIXME: Theoretically, we can do better than that for SP and FP based
498     // references since we can effectively know where those are touching. It's
499     // unclear if it's worth the extra code, though. Most paired instructions
500     // will be sequential, perhaps with a few intervening non-memory related
501     // instructions.
502     if (MI->mayStore() || MI->isCall())
503       return E;
504     // Likewise, if we're matching a store instruction, we don't want to
505     // move across a load, as it may be reading the same location.
506     if (FirstMI->mayStore() && MI->mayLoad())
507       return E;
509     // Update modified / uses register lists.
510     trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
512     // Otherwise, if the base register is modified, we have no match, so
513     // return early.
514     if (ModifiedRegs[BaseReg])
515       return E;
516   }
517   return E;
520 MachineBasicBlock::iterator
521 AArch64LoadStoreOpt::mergePreIdxUpdateInsn(MachineBasicBlock::iterator I,
522                                            MachineBasicBlock::iterator Update) {
523   assert((Update->getOpcode() == AArch64::ADDXri ||
524           Update->getOpcode() == AArch64::SUBXri) &&
525          "Unexpected base register update instruction to merge!");
526   MachineBasicBlock::iterator NextI = I;
527   // Return the instruction following the merged instruction, which is
528   // the instruction following our unmerged load. Unless that's the add/sub
529   // instruction we're merging, in which case it's the one after that.
530   if (++NextI == Update)
531     ++NextI;
533   int Value = Update->getOperand(2).getImm();
534   assert(AArch64_AM::getShiftValue(Update->getOperand(3).getImm()) == 0 &&
535          "Can't merge 1 << 12 offset into pre-indexed load / store");
536   if (Update->getOpcode() == AArch64::SUBXri)
537     Value = -Value;
539   unsigned NewOpc = getPreIndexedOpcode(I->getOpcode());
540   MachineInstrBuilder MIB =
541       BuildMI(*I->getParent(), I, I->getDebugLoc(), TII->get(NewOpc))
542           .addOperand(Update->getOperand(0))
543           .addOperand(I->getOperand(0))
544           .addOperand(I->getOperand(1))
545           .addImm(Value);
546   (void)MIB;
548   DEBUG(dbgs() << "Creating pre-indexed load/store.");
549   DEBUG(dbgs() << "    Replacing instructions:\n    ");
550   DEBUG(I->print(dbgs()));
551   DEBUG(dbgs() << "    ");
552   DEBUG(Update->print(dbgs()));
553   DEBUG(dbgs() << "  with instruction:\n    ");
554   DEBUG(((MachineInstr *)MIB)->print(dbgs()));
555   DEBUG(dbgs() << "\n");
557   // Erase the old instructions for the block.
558   I->eraseFromParent();
559   Update->eraseFromParent();
561   return NextI;
564 MachineBasicBlock::iterator AArch64LoadStoreOpt::mergePostIdxUpdateInsn(
565     MachineBasicBlock::iterator I, MachineBasicBlock::iterator Update) {
566   assert((Update->getOpcode() == AArch64::ADDXri ||
567           Update->getOpcode() == AArch64::SUBXri) &&
568          "Unexpected base register update instruction to merge!");
569   MachineBasicBlock::iterator NextI = I;
570   // Return the instruction following the merged instruction, which is
571   // the instruction following our unmerged load. Unless that's the add/sub
572   // instruction we're merging, in which case it's the one after that.
573   if (++NextI == Update)
574     ++NextI;
576   int Value = Update->getOperand(2).getImm();
577   assert(AArch64_AM::getShiftValue(Update->getOperand(3).getImm()) == 0 &&
578          "Can't merge 1 << 12 offset into post-indexed load / store");
579   if (Update->getOpcode() == AArch64::SUBXri)
580     Value = -Value;
582   unsigned NewOpc = getPostIndexedOpcode(I->getOpcode());
583   MachineInstrBuilder MIB =
584       BuildMI(*I->getParent(), I, I->getDebugLoc(), TII->get(NewOpc))
585           .addOperand(Update->getOperand(0))
586           .addOperand(I->getOperand(0))
587           .addOperand(I->getOperand(1))
588           .addImm(Value);
589   (void)MIB;
591   DEBUG(dbgs() << "Creating post-indexed load/store.");
592   DEBUG(dbgs() << "    Replacing instructions:\n    ");
593   DEBUG(I->print(dbgs()));
594   DEBUG(dbgs() << "    ");
595   DEBUG(Update->print(dbgs()));
596   DEBUG(dbgs() << "  with instruction:\n    ");
597   DEBUG(((MachineInstr *)MIB)->print(dbgs()));
598   DEBUG(dbgs() << "\n");
600   // Erase the old instructions for the block.
601   I->eraseFromParent();
602   Update->eraseFromParent();
604   return NextI;
607 static bool isMatchingUpdateInsn(MachineInstr *MI, unsigned BaseReg,
608                                  int Offset) {
609   switch (MI->getOpcode()) {
610   default:
611     break;
612   case AArch64::SUBXri:
613     // Negate the offset for a SUB instruction.
614     Offset *= -1;
615   // FALLTHROUGH
616   case AArch64::ADDXri:
617     // Make sure it's a vanilla immediate operand, not a relocation or
618     // anything else we can't handle.
619     if (!MI->getOperand(2).isImm())
620       break;
621     // Watch out for 1 << 12 shifted value.
622     if (AArch64_AM::getShiftValue(MI->getOperand(3).getImm()))
623       break;
624     // If the instruction has the base register as source and dest and the
625     // immediate will fit in a signed 9-bit integer, then we have a match.
626     if (MI->getOperand(0).getReg() == BaseReg &&
627         MI->getOperand(1).getReg() == BaseReg &&
628         MI->getOperand(2).getImm() <= 255 &&
629         MI->getOperand(2).getImm() >= -256) {
630       // If we have a non-zero Offset, we check that it matches the amount
631       // we're adding to the register.
632       if (!Offset || Offset == MI->getOperand(2).getImm())
633         return true;
634     }
635     break;
636   }
637   return false;
640 MachineBasicBlock::iterator AArch64LoadStoreOpt::findMatchingUpdateInsnForward(
641     MachineBasicBlock::iterator I, unsigned Limit, int Value) {
642   MachineBasicBlock::iterator E = I->getParent()->end();
643   MachineInstr *MemMI = I;
644   MachineBasicBlock::iterator MBBI = I;
645   const MachineFunction &MF = *MemMI->getParent()->getParent();
647   unsigned DestReg = MemMI->getOperand(0).getReg();
648   unsigned BaseReg = MemMI->getOperand(1).getReg();
649   int Offset = MemMI->getOperand(2).getImm() *
650                TII->getRegClass(MemMI->getDesc(), 0, TRI, MF)->getSize();
652   // If the base register overlaps the destination register, we can't
653   // merge the update.
654   if (DestReg == BaseReg || TRI->isSubRegister(BaseReg, DestReg))
655     return E;
657   // Scan forward looking for post-index opportunities.
658   // Updating instructions can't be formed if the memory insn already
659   // has an offset other than the value we're looking for.
660   if (Offset != Value)
661     return E;
663   // Track which registers have been modified and used between the first insn
664   // (inclusive) and the second insn.
665   BitVector ModifiedRegs, UsedRegs;
666   ModifiedRegs.resize(TRI->getNumRegs());
667   UsedRegs.resize(TRI->getNumRegs());
668   ++MBBI;
669   for (unsigned Count = 0; MBBI != E; ++MBBI) {
670     MachineInstr *MI = MBBI;
671     // Skip DBG_VALUE instructions. Otherwise debug info can affect the
672     // optimization by changing how far we scan.
673     if (MI->isDebugValue())
674       continue;
676     // Now that we know this is a real instruction, count it.
677     ++Count;
679     // If we found a match, return it.
680     if (isMatchingUpdateInsn(MI, BaseReg, Value))
681       return MBBI;
683     // Update the status of what the instruction clobbered and used.
684     trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
686     // Otherwise, if the base register is used or modified, we have no match, so
687     // return early.
688     if (ModifiedRegs[BaseReg] || UsedRegs[BaseReg])
689       return E;
690   }
691   return E;
694 MachineBasicBlock::iterator AArch64LoadStoreOpt::findMatchingUpdateInsnBackward(
695     MachineBasicBlock::iterator I, unsigned Limit) {
696   MachineBasicBlock::iterator B = I->getParent()->begin();
697   MachineBasicBlock::iterator E = I->getParent()->end();
698   MachineInstr *MemMI = I;
699   MachineBasicBlock::iterator MBBI = I;
700   const MachineFunction &MF = *MemMI->getParent()->getParent();
702   unsigned DestReg = MemMI->getOperand(0).getReg();
703   unsigned BaseReg = MemMI->getOperand(1).getReg();
704   int Offset = MemMI->getOperand(2).getImm();
705   unsigned RegSize = TII->getRegClass(MemMI->getDesc(), 0, TRI, MF)->getSize();
707   // If the load/store is the first instruction in the block, there's obviously
708   // not any matching update. Ditto if the memory offset isn't zero.
709   if (MBBI == B || Offset != 0)
710     return E;
711   // If the base register overlaps the destination register, we can't
712   // merge the update.
713   if (DestReg == BaseReg || TRI->isSubRegister(BaseReg, DestReg))
714     return E;
716   // Track which registers have been modified and used between the first insn
717   // (inclusive) and the second insn.
718   BitVector ModifiedRegs, UsedRegs;
719   ModifiedRegs.resize(TRI->getNumRegs());
720   UsedRegs.resize(TRI->getNumRegs());
721   --MBBI;
722   for (unsigned Count = 0; MBBI != B; --MBBI) {
723     MachineInstr *MI = MBBI;
724     // Skip DBG_VALUE instructions. Otherwise debug info can affect the
725     // optimization by changing how far we scan.
726     if (MI->isDebugValue())
727       continue;
729     // Now that we know this is a real instruction, count it.
730     ++Count;
732     // If we found a match, return it.
733     if (isMatchingUpdateInsn(MI, BaseReg, RegSize))
734       return MBBI;
736     // Update the status of what the instruction clobbered and used.
737     trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
739     // Otherwise, if the base register is used or modified, we have no match, so
740     // return early.
741     if (ModifiedRegs[BaseReg] || UsedRegs[BaseReg])
742       return E;
743   }
744   return E;
747 bool AArch64LoadStoreOpt::optimizeBlock(MachineBasicBlock &MBB) {
748   bool Modified = false;
749   // Two tranformations to do here:
750   // 1) Find loads and stores that can be merged into a single load or store
751   //    pair instruction.
752   //      e.g.,
753   //        ldr x0, [x2]
754   //        ldr x1, [x2, #8]
755   //        ; becomes
756   //        ldp x0, x1, [x2]
757   // 2) Find base register updates that can be merged into the load or store
758   //    as a base-reg writeback.
759   //      e.g.,
760   //        ldr x0, [x2]
761   //        add x2, x2, #4
762   //        ; becomes
763   //        ldr x0, [x2], #4
765   for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
766        MBBI != E;) {
767     MachineInstr *MI = MBBI;
768     switch (MI->getOpcode()) {
769     default:
770       // Just move on to the next instruction.
771       ++MBBI;
772       break;
773     case AArch64::STRSui:
774     case AArch64::STRDui:
775     case AArch64::STRQui:
776     case AArch64::STRXui:
777     case AArch64::STRWui:
778     case AArch64::LDRSui:
779     case AArch64::LDRDui:
780     case AArch64::LDRQui:
781     case AArch64::LDRXui:
782     case AArch64::LDRWui:
783     // do the unscaled versions as well
784     case AArch64::STURSi:
785     case AArch64::STURDi:
786     case AArch64::STURQi:
787     case AArch64::STURWi:
788     case AArch64::STURXi:
789     case AArch64::LDURSi:
790     case AArch64::LDURDi:
791     case AArch64::LDURQi:
792     case AArch64::LDURWi:
793     case AArch64::LDURXi: {
794       // If this is a volatile load/store, don't mess with it.
795       if (MI->hasOrderedMemoryRef()) {
796         ++MBBI;
797         break;
798       }
799       // Make sure this is a reg+imm (as opposed to an address reloc).
800       if (!MI->getOperand(2).isImm()) {
801         ++MBBI;
802         break;
803       }
804       // Check if this load/store has a hint to avoid pair formation.
805       // MachineMemOperands hints are set by the AArch64StorePairSuppress pass.
806       if (TII->isLdStPairSuppressed(MI)) {
807         ++MBBI;
808         break;
809       }
810       // Look ahead up to ScanLimit instructions for a pairable instruction.
811       bool MergeForward = false;
812       MachineBasicBlock::iterator Paired =
813           findMatchingInsn(MBBI, MergeForward, ScanLimit);
814       if (Paired != E) {
815         // Merge the loads into a pair. Keeping the iterator straight is a
816         // pain, so we let the merge routine tell us what the next instruction
817         // is after it's done mucking about.
818         MBBI = mergePairedInsns(MBBI, Paired, MergeForward);
820         Modified = true;
821         ++NumPairCreated;
822         if (isUnscaledLdst(MI->getOpcode()))
823           ++NumUnscaledPairCreated;
824         break;
825       }
826       ++MBBI;
827       break;
828     }
829       // FIXME: Do the other instructions.
830     }
831   }
833   for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
834        MBBI != E;) {
835     MachineInstr *MI = MBBI;
836     // Do update merging. It's simpler to keep this separate from the above
837     // switch, though not strictly necessary.
838     int Opc = MI->getOpcode();
839     switch (Opc) {
840     default:
841       // Just move on to the next instruction.
842       ++MBBI;
843       break;
844     case AArch64::STRSui:
845     case AArch64::STRDui:
846     case AArch64::STRQui:
847     case AArch64::STRXui:
848     case AArch64::STRWui:
849     case AArch64::LDRSui:
850     case AArch64::LDRDui:
851     case AArch64::LDRQui:
852     case AArch64::LDRXui:
853     case AArch64::LDRWui:
854     // do the unscaled versions as well
855     case AArch64::STURSi:
856     case AArch64::STURDi:
857     case AArch64::STURQi:
858     case AArch64::STURWi:
859     case AArch64::STURXi:
860     case AArch64::LDURSi:
861     case AArch64::LDURDi:
862     case AArch64::LDURQi:
863     case AArch64::LDURWi:
864     case AArch64::LDURXi: {
865       // Make sure this is a reg+imm (as opposed to an address reloc).
866       if (!MI->getOperand(2).isImm()) {
867         ++MBBI;
868         break;
869       }
870       // Look ahead up to ScanLimit instructions for a mergable instruction.
871       MachineBasicBlock::iterator Update =
872           findMatchingUpdateInsnForward(MBBI, ScanLimit, 0);
873       if (Update != E) {
874         // Merge the update into the ld/st.
875         MBBI = mergePostIdxUpdateInsn(MBBI, Update);
876         Modified = true;
877         ++NumPostFolded;
878         break;
879       }
880       // Don't know how to handle pre/post-index versions, so move to the next
881       // instruction.
882       if (isUnscaledLdst(Opc)) {
883         ++MBBI;
884         break;
885       }
887       // Look back to try to find a pre-index instruction. For example,
888       // add x0, x0, #8
889       // ldr x1, [x0]
890       //   merged into:
891       // ldr x1, [x0, #8]!
892       Update = findMatchingUpdateInsnBackward(MBBI, ScanLimit);
893       if (Update != E) {
894         // Merge the update into the ld/st.
895         MBBI = mergePreIdxUpdateInsn(MBBI, Update);
896         Modified = true;
897         ++NumPreFolded;
898         break;
899       }
901       // Look forward to try to find a post-index instruction. For example,
902       // ldr x1, [x0, #64]
903       // add x0, x0, #64
904       //   merged into:
905       // ldr x1, [x0, #64]!
907       // The immediate in the load/store is scaled by the size of the register
908       // being loaded. The immediate in the add we're looking for,
909       // however, is not, so adjust here.
910       int Value = MI->getOperand(2).getImm() *
911                   TII->getRegClass(MI->getDesc(), 0, TRI, *(MBB.getParent()))
912                       ->getSize();
913       Update = findMatchingUpdateInsnForward(MBBI, ScanLimit, Value);
914       if (Update != E) {
915         // Merge the update into the ld/st.
916         MBBI = mergePreIdxUpdateInsn(MBBI, Update);
917         Modified = true;
918         ++NumPreFolded;
919         break;
920       }
922       // Nothing found. Just move to the next instruction.
923       ++MBBI;
924       break;
925     }
926       // FIXME: Do the other instructions.
927     }
928   }
930   return Modified;
933 bool AArch64LoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
934   const TargetMachine &TM = Fn.getTarget();
935   TII = static_cast<const AArch64InstrInfo *>(
936       TM.getSubtargetImpl()->getInstrInfo());
937   TRI = TM.getSubtargetImpl()->getRegisterInfo();
939   bool Modified = false;
940   for (auto &MBB : Fn)
941     Modified |= optimizeBlock(MBB);
943   return Modified;
946 // FIXME: Do we need/want a pre-alloc pass like ARM has to try to keep
947 // loads and stores near one another?
949 /// createARMLoadStoreOptimizationPass - returns an instance of the load / store
950 /// optimization pass.
951 FunctionPass *llvm::createAArch64LoadStoreOptimizationPass() {
952   return new AArch64LoadStoreOpt();