[AArch64] Promote loads from stores
[oota-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 //===----------------------------------------------------------------------===//
14
15 #include "AArch64InstrInfo.h"
16 #include "AArch64Subtarget.h"
17 #include "MCTargetDesc/AArch64AddressingModes.h"
18 #include "llvm/ADT/BitVector.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/CodeGen/MachineBasicBlock.h"
22 #include "llvm/CodeGen/MachineFunctionPass.h"
23 #include "llvm/CodeGen/MachineInstr.h"
24 #include "llvm/CodeGen/MachineInstrBuilder.h"
25 #include "llvm/Support/CommandLine.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/ErrorHandling.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include "llvm/Target/TargetInstrInfo.h"
30 #include "llvm/Target/TargetMachine.h"
31 #include "llvm/Target/TargetRegisterInfo.h"
32 using namespace llvm;
33
34 #define DEBUG_TYPE "aarch64-ldst-opt"
35
36 /// AArch64AllocLoadStoreOpt - Post-register allocation pass to combine
37 /// load / store instructions to form ldp / stp instructions.
38
39 STATISTIC(NumPairCreated, "Number of load/store pair instructions generated");
40 STATISTIC(NumPostFolded, "Number of post-index updates folded");
41 STATISTIC(NumPreFolded, "Number of pre-index updates folded");
42 STATISTIC(NumUnscaledPairCreated,
43           "Number of load/store from unscaled generated");
44 STATISTIC(NumNarrowLoadsPromoted, "Number of narrow loads promoted");
45 STATISTIC(NumZeroStoresPromoted, "Number of narrow zero stores promoted");
46 STATISTIC(NumLoadsFromStoresPromoted, "Number of loads from stores promoted");
47
48 static cl::opt<unsigned> ScanLimit("aarch64-load-store-scan-limit",
49                                    cl::init(20), cl::Hidden);
50
51 namespace llvm {
52 void initializeAArch64LoadStoreOptPass(PassRegistry &);
53 }
54
55 #define AARCH64_LOAD_STORE_OPT_NAME "AArch64 load / store optimization pass"
56
57 namespace {
58
59 typedef struct LdStPairFlags {
60   // If a matching instruction is found, MergeForward is set to true if the
61   // merge is to remove the first instruction and replace the second with
62   // a pair-wise insn, and false if the reverse is true.
63   bool MergeForward;
64
65   // SExtIdx gives the index of the result of the load pair that must be
66   // extended. The value of SExtIdx assumes that the paired load produces the
67   // value in this order: (I, returned iterator), i.e., -1 means no value has
68   // to be extended, 0 means I, and 1 means the returned iterator.
69   int SExtIdx;
70
71   LdStPairFlags() : MergeForward(false), SExtIdx(-1) {}
72
73   void setMergeForward(bool V = true) { MergeForward = V; }
74   bool getMergeForward() const { return MergeForward; }
75
76   void setSExtIdx(int V) { SExtIdx = V; }
77   int getSExtIdx() const { return SExtIdx; }
78
79 } LdStPairFlags;
80
81 struct AArch64LoadStoreOpt : public MachineFunctionPass {
82   static char ID;
83   AArch64LoadStoreOpt() : MachineFunctionPass(ID) {
84     initializeAArch64LoadStoreOptPass(*PassRegistry::getPassRegistry());
85   }
86
87   const AArch64InstrInfo *TII;
88   const TargetRegisterInfo *TRI;
89   const AArch64Subtarget *Subtarget;
90
91   // Scan the instructions looking for a load/store that can be combined
92   // with the current instruction into a load/store pair.
93   // Return the matching instruction if one is found, else MBB->end().
94   MachineBasicBlock::iterator findMatchingInsn(MachineBasicBlock::iterator I,
95                                                LdStPairFlags &Flags,
96                                                unsigned Limit);
97
98   // Scan the instructions looking for a store that writes to the address from
99   // which the current load instruction reads. Return true if one is found.
100   bool findMatchingStore(MachineBasicBlock::iterator I, unsigned Limit,
101                          MachineBasicBlock::iterator &StoreI);
102
103   // Merge the two instructions indicated into a single pair-wise instruction.
104   // If MergeForward is true, erase the first instruction and fold its
105   // operation into the second. If false, the reverse. Return the instruction
106   // following the first instruction (which may change during processing).
107   MachineBasicBlock::iterator
108   mergePairedInsns(MachineBasicBlock::iterator I,
109                    MachineBasicBlock::iterator Paired,
110                    const LdStPairFlags &Flags);
111
112   // Promote the load that reads directly from the address stored to.
113   MachineBasicBlock::iterator
114   promoteLoadFromStore(MachineBasicBlock::iterator LoadI,
115                        MachineBasicBlock::iterator StoreI);
116
117   // Scan the instruction list to find a base register update that can
118   // be combined with the current instruction (a load or store) using
119   // pre or post indexed addressing with writeback. Scan forwards.
120   MachineBasicBlock::iterator
121   findMatchingUpdateInsnForward(MachineBasicBlock::iterator I, unsigned Limit,
122                                 int UnscaledOffset);
123
124   // Scan the instruction list to find a base register update that can
125   // be combined with the current instruction (a load or store) using
126   // pre or post indexed addressing with writeback. Scan backwards.
127   MachineBasicBlock::iterator
128   findMatchingUpdateInsnBackward(MachineBasicBlock::iterator I, unsigned Limit);
129
130   // Find an instruction that updates the base register of the ld/st
131   // instruction.
132   bool isMatchingUpdateInsn(MachineInstr *MemMI, MachineInstr *MI,
133                             unsigned BaseReg, int Offset);
134
135   // Merge a pre- or post-index base register update into a ld/st instruction.
136   MachineBasicBlock::iterator
137   mergeUpdateInsn(MachineBasicBlock::iterator I,
138                   MachineBasicBlock::iterator Update, bool IsPreIdx);
139
140   // Find and merge foldable ldr/str instructions.
141   bool tryToMergeLdStInst(MachineBasicBlock::iterator &MBBI);
142
143   // Find and promote load instructions which read directly from store.
144   bool tryToPromoteLoadFromStore(MachineBasicBlock::iterator &MBBI);
145
146   // Check if converting two narrow loads into a single wider load with
147   // bitfield extracts could be enabled.
148   bool enableNarrowLdMerge(MachineFunction &Fn);
149
150   bool optimizeBlock(MachineBasicBlock &MBB, bool enableNarrowLdOpt);
151
152   bool runOnMachineFunction(MachineFunction &Fn) override;
153
154   const char *getPassName() const override {
155     return AARCH64_LOAD_STORE_OPT_NAME;
156   }
157 };
158 char AArch64LoadStoreOpt::ID = 0;
159 } // namespace
160
161 INITIALIZE_PASS(AArch64LoadStoreOpt, "aarch64-ldst-opt",
162                 AARCH64_LOAD_STORE_OPT_NAME, false, false)
163
164 static bool isUnscaledLdSt(unsigned Opc) {
165   switch (Opc) {
166   default:
167     return false;
168   case AArch64::STURSi:
169   case AArch64::STURDi:
170   case AArch64::STURQi:
171   case AArch64::STURBBi:
172   case AArch64::STURHHi:
173   case AArch64::STURWi:
174   case AArch64::STURXi:
175   case AArch64::LDURSi:
176   case AArch64::LDURDi:
177   case AArch64::LDURQi:
178   case AArch64::LDURWi:
179   case AArch64::LDURXi:
180   case AArch64::LDURSWi:
181   case AArch64::LDURHHi:
182   case AArch64::LDURBBi:
183   case AArch64::LDURSBWi:
184   case AArch64::LDURSHWi:
185     return true;
186   }
187 }
188
189 static bool isUnscaledLdSt(MachineInstr *MI) {
190   return isUnscaledLdSt(MI->getOpcode());
191 }
192
193 static unsigned getBitExtrOpcode(MachineInstr *MI) {
194   switch (MI->getOpcode()) {
195   default:
196     llvm_unreachable("Unexpected opcode.");
197   case AArch64::LDRBBui:
198   case AArch64::LDURBBi:
199   case AArch64::LDRHHui:
200   case AArch64::LDURHHi:
201     return AArch64::UBFMWri;
202   case AArch64::LDRSBWui:
203   case AArch64::LDURSBWi:
204   case AArch64::LDRSHWui:
205   case AArch64::LDURSHWi:
206     return AArch64::SBFMWri;
207   }
208 }
209
210 static bool isNarrowStore(unsigned Opc) {
211   switch (Opc) {
212   default:
213     return false;
214   case AArch64::STRBBui:
215   case AArch64::STURBBi:
216   case AArch64::STRHHui:
217   case AArch64::STURHHi:
218     return true;
219   }
220 }
221
222 static bool isNarrowStore(MachineInstr *MI) {
223   return isNarrowStore(MI->getOpcode());
224 }
225
226 static bool isNarrowLoad(unsigned Opc) {
227   switch (Opc) {
228   default:
229     return false;
230   case AArch64::LDRHHui:
231   case AArch64::LDURHHi:
232   case AArch64::LDRBBui:
233   case AArch64::LDURBBi:
234   case AArch64::LDRSHWui:
235   case AArch64::LDURSHWi:
236   case AArch64::LDRSBWui:
237   case AArch64::LDURSBWi:
238     return true;
239   }
240 }
241
242 static bool isNarrowLoad(MachineInstr *MI) {
243   return isNarrowLoad(MI->getOpcode());
244 }
245
246 // Scaling factor for unscaled load or store.
247 static int getMemScale(MachineInstr *MI) {
248   switch (MI->getOpcode()) {
249   default:
250     llvm_unreachable("Opcode has unknown scale!");
251   case AArch64::LDRBBui:
252   case AArch64::LDURBBi:
253   case AArch64::LDRSBWui:
254   case AArch64::LDURSBWi:
255   case AArch64::STRBBui:
256   case AArch64::STURBBi:
257     return 1;
258   case AArch64::LDRHHui:
259   case AArch64::LDURHHi:
260   case AArch64::LDRSHWui:
261   case AArch64::LDURSHWi:
262   case AArch64::STRHHui:
263   case AArch64::STURHHi:
264     return 2;
265   case AArch64::LDRSui:
266   case AArch64::LDURSi:
267   case AArch64::LDRSWui:
268   case AArch64::LDURSWi:
269   case AArch64::LDRWui:
270   case AArch64::LDURWi:
271   case AArch64::STRSui:
272   case AArch64::STURSi:
273   case AArch64::STRWui:
274   case AArch64::STURWi:
275   case AArch64::LDPSi:
276   case AArch64::LDPSWi:
277   case AArch64::LDPWi:
278   case AArch64::STPSi:
279   case AArch64::STPWi:
280     return 4;
281   case AArch64::LDRDui:
282   case AArch64::LDURDi:
283   case AArch64::LDRXui:
284   case AArch64::LDURXi:
285   case AArch64::STRDui:
286   case AArch64::STURDi:
287   case AArch64::STRXui:
288   case AArch64::STURXi:
289   case AArch64::LDPDi:
290   case AArch64::LDPXi:
291   case AArch64::STPDi:
292   case AArch64::STPXi:
293     return 8;
294   case AArch64::LDRQui:
295   case AArch64::LDURQi:
296   case AArch64::STRQui:
297   case AArch64::STURQi:
298   case AArch64::LDPQi:
299   case AArch64::STPQi:
300     return 16;
301   }
302 }
303
304 static unsigned getMatchingNonSExtOpcode(unsigned Opc,
305                                          bool *IsValidLdStrOpc = nullptr) {
306   if (IsValidLdStrOpc)
307     *IsValidLdStrOpc = true;
308   switch (Opc) {
309   default:
310     if (IsValidLdStrOpc)
311       *IsValidLdStrOpc = false;
312     return UINT_MAX;
313   case AArch64::STRDui:
314   case AArch64::STURDi:
315   case AArch64::STRQui:
316   case AArch64::STURQi:
317   case AArch64::STRBBui:
318   case AArch64::STURBBi:
319   case AArch64::STRHHui:
320   case AArch64::STURHHi:
321   case AArch64::STRWui:
322   case AArch64::STURWi:
323   case AArch64::STRXui:
324   case AArch64::STURXi:
325   case AArch64::LDRDui:
326   case AArch64::LDURDi:
327   case AArch64::LDRQui:
328   case AArch64::LDURQi:
329   case AArch64::LDRWui:
330   case AArch64::LDURWi:
331   case AArch64::LDRXui:
332   case AArch64::LDURXi:
333   case AArch64::STRSui:
334   case AArch64::STURSi:
335   case AArch64::LDRSui:
336   case AArch64::LDURSi:
337   case AArch64::LDRHHui:
338   case AArch64::LDURHHi:
339   case AArch64::LDRBBui:
340   case AArch64::LDURBBi:
341     return Opc;
342   case AArch64::LDRSWui:
343     return AArch64::LDRWui;
344   case AArch64::LDURSWi:
345     return AArch64::LDURWi;
346   case AArch64::LDRSBWui:
347     return AArch64::LDRBBui;
348   case AArch64::LDRSHWui:
349     return AArch64::LDRHHui;
350   case AArch64::LDURSBWi:
351     return AArch64::LDURBBi;
352   case AArch64::LDURSHWi:
353     return AArch64::LDURHHi;
354   }
355 }
356
357 static unsigned getMatchingPairOpcode(unsigned Opc) {
358   switch (Opc) {
359   default:
360     llvm_unreachable("Opcode has no pairwise equivalent!");
361   case AArch64::STRSui:
362   case AArch64::STURSi:
363     return AArch64::STPSi;
364   case AArch64::STRDui:
365   case AArch64::STURDi:
366     return AArch64::STPDi;
367   case AArch64::STRQui:
368   case AArch64::STURQi:
369     return AArch64::STPQi;
370   case AArch64::STRBBui:
371     return AArch64::STRHHui;
372   case AArch64::STRHHui:
373     return AArch64::STRWui;
374   case AArch64::STURBBi:
375     return AArch64::STURHHi;
376   case AArch64::STURHHi:
377     return AArch64::STURWi;
378   case AArch64::STRWui:
379   case AArch64::STURWi:
380     return AArch64::STPWi;
381   case AArch64::STRXui:
382   case AArch64::STURXi:
383     return AArch64::STPXi;
384   case AArch64::LDRSui:
385   case AArch64::LDURSi:
386     return AArch64::LDPSi;
387   case AArch64::LDRDui:
388   case AArch64::LDURDi:
389     return AArch64::LDPDi;
390   case AArch64::LDRQui:
391   case AArch64::LDURQi:
392     return AArch64::LDPQi;
393   case AArch64::LDRWui:
394   case AArch64::LDURWi:
395     return AArch64::LDPWi;
396   case AArch64::LDRXui:
397   case AArch64::LDURXi:
398     return AArch64::LDPXi;
399   case AArch64::LDRSWui:
400   case AArch64::LDURSWi:
401     return AArch64::LDPSWi;
402   case AArch64::LDRHHui:
403   case AArch64::LDRSHWui:
404     return AArch64::LDRWui;
405   case AArch64::LDURHHi:
406   case AArch64::LDURSHWi:
407     return AArch64::LDURWi;
408   case AArch64::LDRBBui:
409   case AArch64::LDRSBWui:
410     return AArch64::LDRHHui;
411   case AArch64::LDURBBi:
412   case AArch64::LDURSBWi:
413     return AArch64::LDURHHi;
414   }
415 }
416
417 static unsigned isMatchingStore(MachineInstr *LoadInst,
418                                 MachineInstr *StoreInst) {
419   unsigned LdOpc = LoadInst->getOpcode();
420   unsigned StOpc = StoreInst->getOpcode();
421   switch (LdOpc) {
422   default:
423     llvm_unreachable("Unsupported load instruction!");
424   case AArch64::LDRBBui:
425     return StOpc == AArch64::STRBBui || StOpc == AArch64::STRHHui ||
426            StOpc == AArch64::STRWui || StOpc == AArch64::STRXui;
427   case AArch64::LDURBBi:
428     return StOpc == AArch64::STURBBi || StOpc == AArch64::STURHHi ||
429            StOpc == AArch64::STURWi || StOpc == AArch64::STURXi;
430   case AArch64::LDRHHui:
431     return StOpc == AArch64::STRHHui || StOpc == AArch64::STRWui ||
432            StOpc == AArch64::STRXui;
433   case AArch64::LDURHHi:
434     return StOpc == AArch64::STURHHi || StOpc == AArch64::STURWi ||
435            StOpc == AArch64::STURXi;
436   case AArch64::LDRWui:
437     return StOpc == AArch64::STRWui || StOpc == AArch64::STRXui;
438   case AArch64::LDURWi:
439     return StOpc == AArch64::STURWi || StOpc == AArch64::STURXi;
440   case AArch64::LDRXui:
441     return StOpc == AArch64::STRXui;
442   case AArch64::LDURXi:
443     return StOpc == AArch64::STURXi;
444   }
445 }
446
447 static unsigned getPreIndexedOpcode(unsigned Opc) {
448   switch (Opc) {
449   default:
450     llvm_unreachable("Opcode has no pre-indexed equivalent!");
451   case AArch64::STRSui:
452     return AArch64::STRSpre;
453   case AArch64::STRDui:
454     return AArch64::STRDpre;
455   case AArch64::STRQui:
456     return AArch64::STRQpre;
457   case AArch64::STRBBui:
458     return AArch64::STRBBpre;
459   case AArch64::STRHHui:
460     return AArch64::STRHHpre;
461   case AArch64::STRWui:
462     return AArch64::STRWpre;
463   case AArch64::STRXui:
464     return AArch64::STRXpre;
465   case AArch64::LDRSui:
466     return AArch64::LDRSpre;
467   case AArch64::LDRDui:
468     return AArch64::LDRDpre;
469   case AArch64::LDRQui:
470     return AArch64::LDRQpre;
471   case AArch64::LDRBBui:
472     return AArch64::LDRBBpre;
473   case AArch64::LDRHHui:
474     return AArch64::LDRHHpre;
475   case AArch64::LDRWui:
476     return AArch64::LDRWpre;
477   case AArch64::LDRXui:
478     return AArch64::LDRXpre;
479   case AArch64::LDRSWui:
480     return AArch64::LDRSWpre;
481   case AArch64::LDPSi:
482     return AArch64::LDPSpre;
483   case AArch64::LDPSWi:
484     return AArch64::LDPSWpre;
485   case AArch64::LDPDi:
486     return AArch64::LDPDpre;
487   case AArch64::LDPQi:
488     return AArch64::LDPQpre;
489   case AArch64::LDPWi:
490     return AArch64::LDPWpre;
491   case AArch64::LDPXi:
492     return AArch64::LDPXpre;
493   case AArch64::STPSi:
494     return AArch64::STPSpre;
495   case AArch64::STPDi:
496     return AArch64::STPDpre;
497   case AArch64::STPQi:
498     return AArch64::STPQpre;
499   case AArch64::STPWi:
500     return AArch64::STPWpre;
501   case AArch64::STPXi:
502     return AArch64::STPXpre;
503   }
504 }
505
506 static unsigned getPostIndexedOpcode(unsigned Opc) {
507   switch (Opc) {
508   default:
509     llvm_unreachable("Opcode has no post-indexed wise equivalent!");
510   case AArch64::STRSui:
511     return AArch64::STRSpost;
512   case AArch64::STRDui:
513     return AArch64::STRDpost;
514   case AArch64::STRQui:
515     return AArch64::STRQpost;
516   case AArch64::STRBBui:
517     return AArch64::STRBBpost;
518   case AArch64::STRHHui:
519     return AArch64::STRHHpost;
520   case AArch64::STRWui:
521     return AArch64::STRWpost;
522   case AArch64::STRXui:
523     return AArch64::STRXpost;
524   case AArch64::LDRSui:
525     return AArch64::LDRSpost;
526   case AArch64::LDRDui:
527     return AArch64::LDRDpost;
528   case AArch64::LDRQui:
529     return AArch64::LDRQpost;
530   case AArch64::LDRBBui:
531     return AArch64::LDRBBpost;
532   case AArch64::LDRHHui:
533     return AArch64::LDRHHpost;
534   case AArch64::LDRWui:
535     return AArch64::LDRWpost;
536   case AArch64::LDRXui:
537     return AArch64::LDRXpost;
538   case AArch64::LDRSWui:
539     return AArch64::LDRSWpost;
540   case AArch64::LDPSi:
541     return AArch64::LDPSpost;
542   case AArch64::LDPSWi:
543     return AArch64::LDPSWpost;
544   case AArch64::LDPDi:
545     return AArch64::LDPDpost;
546   case AArch64::LDPQi:
547     return AArch64::LDPQpost;
548   case AArch64::LDPWi:
549     return AArch64::LDPWpost;
550   case AArch64::LDPXi:
551     return AArch64::LDPXpost;
552   case AArch64::STPSi:
553     return AArch64::STPSpost;
554   case AArch64::STPDi:
555     return AArch64::STPDpost;
556   case AArch64::STPQi:
557     return AArch64::STPQpost;
558   case AArch64::STPWi:
559     return AArch64::STPWpost;
560   case AArch64::STPXi:
561     return AArch64::STPXpost;
562   }
563 }
564
565 static bool isPairedLdSt(const MachineInstr *MI) {
566   switch (MI->getOpcode()) {
567   default:
568     return false;
569   case AArch64::LDPSi:
570   case AArch64::LDPSWi:
571   case AArch64::LDPDi:
572   case AArch64::LDPQi:
573   case AArch64::LDPWi:
574   case AArch64::LDPXi:
575   case AArch64::STPSi:
576   case AArch64::STPDi:
577   case AArch64::STPQi:
578   case AArch64::STPWi:
579   case AArch64::STPXi:
580     return true;
581   }
582 }
583
584 static const MachineOperand &getLdStRegOp(const MachineInstr *MI,
585                                           unsigned PairedRegOp = 0) {
586   assert(PairedRegOp < 2 && "Unexpected register operand idx.");
587   unsigned Idx = isPairedLdSt(MI) ? PairedRegOp : 0;
588   return MI->getOperand(Idx);
589 }
590
591 static const MachineOperand &getLdStBaseOp(const MachineInstr *MI) {
592   unsigned Idx = isPairedLdSt(MI) ? 2 : 1;
593   return MI->getOperand(Idx);
594 }
595
596 static const MachineOperand &getLdStOffsetOp(const MachineInstr *MI) {
597   unsigned Idx = isPairedLdSt(MI) ? 3 : 2;
598   return MI->getOperand(Idx);
599 }
600
601 static bool isLdOffsetInRangeOfSt(MachineInstr *LoadInst,
602                                   MachineInstr *StoreInst) {
603   assert(isMatchingStore(LoadInst, StoreInst) && "Expect only matched ld/st.");
604   int LoadSize = getMemScale(LoadInst);
605   int StoreSize = getMemScale(StoreInst);
606   int UnscaledStOffset = isUnscaledLdSt(StoreInst)
607                              ? getLdStOffsetOp(StoreInst).getImm()
608                              : getLdStOffsetOp(StoreInst).getImm() * StoreSize;
609   int UnscaledLdOffset = isUnscaledLdSt(LoadInst)
610                              ? getLdStOffsetOp(LoadInst).getImm()
611                              : getLdStOffsetOp(LoadInst).getImm() * LoadSize;
612   return (UnscaledStOffset <= UnscaledLdOffset) &&
613          (UnscaledLdOffset + LoadSize <= (UnscaledStOffset + StoreSize));
614 }
615
616 // Copy MachineMemOperands from Op0 and Op1 to a new array assigned to MI.
617 static void concatenateMemOperands(MachineInstr *MI, MachineInstr *Op0,
618                                    MachineInstr *Op1) {
619   assert(MI->memoperands_empty() && "expected a new machineinstr");
620   size_t numMemRefs = (Op0->memoperands_end() - Op0->memoperands_begin()) +
621                       (Op1->memoperands_end() - Op1->memoperands_begin());
622
623   MachineFunction *MF = MI->getParent()->getParent();
624   MachineSDNode::mmo_iterator MemBegin = MF->allocateMemRefsArray(numMemRefs);
625   MachineSDNode::mmo_iterator MemEnd =
626       std::copy(Op0->memoperands_begin(), Op0->memoperands_end(), MemBegin);
627   MemEnd = std::copy(Op1->memoperands_begin(), Op1->memoperands_end(), MemEnd);
628   MI->setMemRefs(MemBegin, MemEnd);
629 }
630
631 MachineBasicBlock::iterator
632 AArch64LoadStoreOpt::mergePairedInsns(MachineBasicBlock::iterator I,
633                                       MachineBasicBlock::iterator Paired,
634                                       const LdStPairFlags &Flags) {
635   MachineBasicBlock::iterator NextI = I;
636   ++NextI;
637   // If NextI is the second of the two instructions to be merged, we need
638   // to skip one further. Either way we merge will invalidate the iterator,
639   // and we don't need to scan the new instruction, as it's a pairwise
640   // instruction, which we're not considering for further action anyway.
641   if (NextI == Paired)
642     ++NextI;
643
644   int SExtIdx = Flags.getSExtIdx();
645   unsigned Opc =
646       SExtIdx == -1 ? I->getOpcode() : getMatchingNonSExtOpcode(I->getOpcode());
647   bool IsUnscaled = isUnscaledLdSt(Opc);
648   int OffsetStride = IsUnscaled ? getMemScale(I) : 1;
649
650   bool MergeForward = Flags.getMergeForward();
651   unsigned NewOpc = getMatchingPairOpcode(Opc);
652   // Insert our new paired instruction after whichever of the paired
653   // instructions MergeForward indicates.
654   MachineBasicBlock::iterator InsertionPoint = MergeForward ? Paired : I;
655   // Also based on MergeForward is from where we copy the base register operand
656   // so we get the flags compatible with the input code.
657   const MachineOperand &BaseRegOp =
658       MergeForward ? getLdStBaseOp(Paired) : getLdStBaseOp(I);
659
660   // Which register is Rt and which is Rt2 depends on the offset order.
661   MachineInstr *RtMI, *Rt2MI;
662   if (getLdStOffsetOp(I).getImm() ==
663       getLdStOffsetOp(Paired).getImm() + OffsetStride) {
664     RtMI = Paired;
665     Rt2MI = I;
666     // Here we swapped the assumption made for SExtIdx.
667     // I.e., we turn ldp I, Paired into ldp Paired, I.
668     // Update the index accordingly.
669     if (SExtIdx != -1)
670       SExtIdx = (SExtIdx + 1) % 2;
671   } else {
672     RtMI = I;
673     Rt2MI = Paired;
674   }
675
676   int OffsetImm = getLdStOffsetOp(RtMI).getImm();
677
678   if (isNarrowLoad(Opc)) {
679     // Change the scaled offset from small to large type.
680     if (!IsUnscaled) {
681       assert(((OffsetImm & 1) == 0) && "Unexpected offset to merge");
682       OffsetImm /= 2;
683     }
684     MachineInstr *RtNewDest = MergeForward ? I : Paired;
685     // When merging small (< 32 bit) loads for big-endian targets, the order of
686     // the component parts gets swapped.
687     if (!Subtarget->isLittleEndian())
688       std::swap(RtMI, Rt2MI);
689     // Construct the new load instruction.
690     MachineInstr *NewMemMI, *BitExtMI1, *BitExtMI2;
691     NewMemMI = BuildMI(*I->getParent(), InsertionPoint, I->getDebugLoc(),
692                        TII->get(NewOpc))
693                    .addOperand(getLdStRegOp(RtNewDest))
694                    .addOperand(BaseRegOp)
695                    .addImm(OffsetImm);
696
697     // Copy MachineMemOperands from the original loads.
698     concatenateMemOperands(NewMemMI, I, Paired);
699
700     DEBUG(
701         dbgs()
702         << "Creating the new load and extract. Replacing instructions:\n    ");
703     DEBUG(I->print(dbgs()));
704     DEBUG(dbgs() << "    ");
705     DEBUG(Paired->print(dbgs()));
706     DEBUG(dbgs() << "  with instructions:\n    ");
707     DEBUG((NewMemMI)->print(dbgs()));
708
709     int Width = getMemScale(I) == 1 ? 8 : 16;
710     int LSBLow = 0;
711     int LSBHigh = Width;
712     int ImmsLow = LSBLow + Width - 1;
713     int ImmsHigh = LSBHigh + Width - 1;
714     MachineInstr *ExtDestMI = MergeForward ? Paired : I;
715     if ((ExtDestMI == Rt2MI) == Subtarget->isLittleEndian()) {
716       // Create the bitfield extract for high bits.
717       BitExtMI1 = BuildMI(*I->getParent(), InsertionPoint, I->getDebugLoc(),
718                           TII->get(getBitExtrOpcode(Rt2MI)))
719                       .addOperand(getLdStRegOp(Rt2MI))
720                       .addReg(getLdStRegOp(RtNewDest).getReg())
721                       .addImm(LSBHigh)
722                       .addImm(ImmsHigh);
723       // Create the bitfield extract for low bits.
724       if (RtMI->getOpcode() == getMatchingNonSExtOpcode(RtMI->getOpcode())) {
725         // For unsigned, prefer to use AND for low bits.
726         BitExtMI2 = BuildMI(*I->getParent(), InsertionPoint, I->getDebugLoc(),
727                             TII->get(AArch64::ANDWri))
728                         .addOperand(getLdStRegOp(RtMI))
729                         .addReg(getLdStRegOp(RtNewDest).getReg())
730                         .addImm(ImmsLow);
731       } else {
732         BitExtMI2 = BuildMI(*I->getParent(), InsertionPoint, I->getDebugLoc(),
733                             TII->get(getBitExtrOpcode(RtMI)))
734                         .addOperand(getLdStRegOp(RtMI))
735                         .addReg(getLdStRegOp(RtNewDest).getReg())
736                         .addImm(LSBLow)
737                         .addImm(ImmsLow);
738       }
739     } else {
740       // Create the bitfield extract for low bits.
741       if (RtMI->getOpcode() == getMatchingNonSExtOpcode(RtMI->getOpcode())) {
742         // For unsigned, prefer to use AND for low bits.
743         BitExtMI1 = BuildMI(*I->getParent(), InsertionPoint, I->getDebugLoc(),
744                             TII->get(AArch64::ANDWri))
745                         .addOperand(getLdStRegOp(RtMI))
746                         .addReg(getLdStRegOp(RtNewDest).getReg())
747                         .addImm(ImmsLow);
748       } else {
749         BitExtMI1 = BuildMI(*I->getParent(), InsertionPoint, I->getDebugLoc(),
750                             TII->get(getBitExtrOpcode(RtMI)))
751                         .addOperand(getLdStRegOp(RtMI))
752                         .addReg(getLdStRegOp(RtNewDest).getReg())
753                         .addImm(LSBLow)
754                         .addImm(ImmsLow);
755       }
756
757       // Create the bitfield extract for high bits.
758       BitExtMI2 = BuildMI(*I->getParent(), InsertionPoint, I->getDebugLoc(),
759                           TII->get(getBitExtrOpcode(Rt2MI)))
760                       .addOperand(getLdStRegOp(Rt2MI))
761                       .addReg(getLdStRegOp(RtNewDest).getReg())
762                       .addImm(LSBHigh)
763                       .addImm(ImmsHigh);
764     }
765     DEBUG(dbgs() << "    ");
766     DEBUG((BitExtMI1)->print(dbgs()));
767     DEBUG(dbgs() << "    ");
768     DEBUG((BitExtMI2)->print(dbgs()));
769     DEBUG(dbgs() << "\n");
770
771     // Erase the old instructions.
772     I->eraseFromParent();
773     Paired->eraseFromParent();
774     return NextI;
775   }
776
777   // Construct the new instruction.
778   MachineInstrBuilder MIB;
779   if (isNarrowStore(Opc)) {
780     // Change the scaled offset from small to large type.
781     if (!IsUnscaled) {
782       assert(((OffsetImm & 1) == 0) && "Unexpected offset to merge");
783       OffsetImm /= 2;
784     }
785     MIB = BuildMI(*I->getParent(), InsertionPoint, I->getDebugLoc(),
786                   TII->get(NewOpc))
787               .addOperand(getLdStRegOp(I))
788               .addOperand(BaseRegOp)
789               .addImm(OffsetImm);
790     // Copy MachineMemOperands from the original stores.
791     concatenateMemOperands(MIB, I, Paired);
792   } else {
793     // Handle Unscaled
794     if (IsUnscaled)
795       OffsetImm /= OffsetStride;
796     MIB = BuildMI(*I->getParent(), InsertionPoint, I->getDebugLoc(),
797                   TII->get(NewOpc))
798               .addOperand(getLdStRegOp(RtMI))
799               .addOperand(getLdStRegOp(Rt2MI))
800               .addOperand(BaseRegOp)
801               .addImm(OffsetImm);
802   }
803
804   (void)MIB;
805
806   // FIXME: Do we need/want to copy the mem operands from the source
807   //        instructions? Probably. What uses them after this?
808
809   DEBUG(dbgs() << "Creating pair load/store. Replacing instructions:\n    ");
810   DEBUG(I->print(dbgs()));
811   DEBUG(dbgs() << "    ");
812   DEBUG(Paired->print(dbgs()));
813   DEBUG(dbgs() << "  with instruction:\n    ");
814
815   if (SExtIdx != -1) {
816     // Generate the sign extension for the proper result of the ldp.
817     // I.e., with X1, that would be:
818     // %W1<def> = KILL %W1, %X1<imp-def>
819     // %X1<def> = SBFMXri %X1<kill>, 0, 31
820     MachineOperand &DstMO = MIB->getOperand(SExtIdx);
821     // Right now, DstMO has the extended register, since it comes from an
822     // extended opcode.
823     unsigned DstRegX = DstMO.getReg();
824     // Get the W variant of that register.
825     unsigned DstRegW = TRI->getSubReg(DstRegX, AArch64::sub_32);
826     // Update the result of LDP to use the W instead of the X variant.
827     DstMO.setReg(DstRegW);
828     DEBUG(((MachineInstr *)MIB)->print(dbgs()));
829     DEBUG(dbgs() << "\n");
830     // Make the machine verifier happy by providing a definition for
831     // the X register.
832     // Insert this definition right after the generated LDP, i.e., before
833     // InsertionPoint.
834     MachineInstrBuilder MIBKill =
835         BuildMI(*I->getParent(), InsertionPoint, I->getDebugLoc(),
836                 TII->get(TargetOpcode::KILL), DstRegW)
837             .addReg(DstRegW)
838             .addReg(DstRegX, RegState::Define);
839     MIBKill->getOperand(2).setImplicit();
840     // Create the sign extension.
841     MachineInstrBuilder MIBSXTW =
842         BuildMI(*I->getParent(), InsertionPoint, I->getDebugLoc(),
843                 TII->get(AArch64::SBFMXri), DstRegX)
844             .addReg(DstRegX)
845             .addImm(0)
846             .addImm(31);
847     (void)MIBSXTW;
848     DEBUG(dbgs() << "  Extend operand:\n    ");
849     DEBUG(((MachineInstr *)MIBSXTW)->print(dbgs()));
850     DEBUG(dbgs() << "\n");
851   } else {
852     DEBUG(((MachineInstr *)MIB)->print(dbgs()));
853     DEBUG(dbgs() << "\n");
854   }
855
856   // Erase the old instructions.
857   I->eraseFromParent();
858   Paired->eraseFromParent();
859
860   return NextI;
861 }
862
863 MachineBasicBlock::iterator
864 AArch64LoadStoreOpt::promoteLoadFromStore(MachineBasicBlock::iterator LoadI,
865                                           MachineBasicBlock::iterator StoreI) {
866   MachineBasicBlock::iterator NextI = LoadI;
867   ++NextI;
868
869   int LoadSize = getMemScale(LoadI);
870   int StoreSize = getMemScale(StoreI);
871   unsigned LdRt = getLdStRegOp(LoadI).getReg();
872   unsigned StRt = getLdStRegOp(StoreI).getReg();
873   bool IsStoreXReg = TRI->getRegClass(AArch64::GPR64RegClassID)->contains(StRt);
874
875   assert((IsStoreXReg ||
876           TRI->getRegClass(AArch64::GPR32RegClassID)->contains(StRt)) &&
877          "Unexpected RegClass");
878
879   MachineInstr *BitExtMI;
880   if (LoadSize == StoreSize) {
881     // Remove the load, if the destination register of the loads is the same
882     // register for stored value.
883     if (StRt == LdRt) {
884       DEBUG(dbgs() << "Remove load instruction:\n    ");
885       DEBUG(LoadI->print(dbgs()));
886       DEBUG(dbgs() << "\n");
887       LoadI->eraseFromParent();
888       return NextI;
889     }
890     // Replace the load with a mov if the load and store are in the same size.
891     BitExtMI =
892         BuildMI(*LoadI->getParent(), LoadI, LoadI->getDebugLoc(),
893                 TII->get(IsStoreXReg ? AArch64::ORRXrs : AArch64::ORRWrs), LdRt)
894             .addReg(IsStoreXReg ? AArch64::XZR : AArch64::WZR)
895             .addReg(StRt)
896             .addImm(AArch64_AM::getShifterImm(AArch64_AM::LSL, 0));
897   } else {
898     // FIXME: Currently we disable this transformation in big-endian targets as
899     // performance and correctness are verified only in little-endian.
900     if (!Subtarget->isLittleEndian())
901       return NextI;
902     bool IsUnscaled = isUnscaledLdSt(LoadI);
903     assert(IsUnscaled == isUnscaledLdSt(StoreI) && "Unsupported ld/st match");
904     assert(LoadSize < StoreSize && "Invalid load size");
905     int UnscaledLdOffset = IsUnscaled
906                                ? getLdStOffsetOp(LoadI).getImm()
907                                : getLdStOffsetOp(LoadI).getImm() * LoadSize;
908     int UnscaledStOffset = IsUnscaled
909                                ? getLdStOffsetOp(StoreI).getImm()
910                                : getLdStOffsetOp(StoreI).getImm() * StoreSize;
911     int Width = LoadSize * 8;
912     int Immr = 8 * (UnscaledLdOffset - UnscaledStOffset);
913     int Imms = Immr + Width - 1;
914     unsigned DestReg = IsStoreXReg
915                            ? TRI->getMatchingSuperReg(LdRt, AArch64::sub_32,
916                                                       &AArch64::GPR64RegClass)
917                            : LdRt;
918
919     assert(((UnscaledLdOffset) >= UnscaledStOffset &&
920             (UnscaledLdOffset + LoadSize) <= UnscaledStOffset + StoreSize) &&
921            "Invalid offset");
922
923     Immr = 8 * (UnscaledLdOffset - UnscaledStOffset);
924     Imms = Immr + Width - 1;
925     if (UnscaledLdOffset == UnscaledStOffset) {
926       uint32_t AndMaskEncoded = ((IsStoreXReg ? 1 : 0) << 12) // N
927                                 | ((Immr) << 6)               // immr
928                                 | ((Imms) << 0)               // imms
929           ;
930
931       BitExtMI =
932           BuildMI(*LoadI->getParent(), LoadI, LoadI->getDebugLoc(),
933                   TII->get(IsStoreXReg ? AArch64::ANDXri : AArch64::ANDWri),
934                   DestReg)
935               .addReg(StRt)
936               .addImm(AndMaskEncoded);
937     } else {
938       BitExtMI =
939           BuildMI(*LoadI->getParent(), LoadI, LoadI->getDebugLoc(),
940                   TII->get(IsStoreXReg ? AArch64::UBFMXri : AArch64::UBFMWri),
941                   DestReg)
942               .addReg(StRt)
943               .addImm(Immr)
944               .addImm(Imms);
945     }
946   }
947
948   DEBUG(dbgs() << "Promoting load by replacing :\n    ");
949   DEBUG(StoreI->print(dbgs()));
950   DEBUG(dbgs() << "    ");
951   DEBUG(LoadI->print(dbgs()));
952   DEBUG(dbgs() << "  with instructions:\n    ");
953   DEBUG(StoreI->print(dbgs()));
954   DEBUG(dbgs() << "    ");
955   DEBUG((BitExtMI)->print(dbgs()));
956   DEBUG(dbgs() << "\n");
957
958   // Erase the old instructions.
959   LoadI->eraseFromParent();
960   return NextI;
961 }
962
963 /// trackRegDefsUses - Remember what registers the specified instruction uses
964 /// and modifies.
965 static void trackRegDefsUses(const MachineInstr *MI, BitVector &ModifiedRegs,
966                              BitVector &UsedRegs,
967                              const TargetRegisterInfo *TRI) {
968   for (const MachineOperand &MO : MI->operands()) {
969     if (MO.isRegMask())
970       ModifiedRegs.setBitsNotInMask(MO.getRegMask());
971
972     if (!MO.isReg())
973       continue;
974     unsigned Reg = MO.getReg();
975     if (MO.isDef()) {
976       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
977         ModifiedRegs.set(*AI);
978     } else {
979       assert(MO.isUse() && "Reg operand not a def and not a use?!?");
980       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
981         UsedRegs.set(*AI);
982     }
983   }
984 }
985
986 static bool inBoundsForPair(bool IsUnscaled, int Offset, int OffsetStride) {
987   // Convert the byte-offset used by unscaled into an "element" offset used
988   // by the scaled pair load/store instructions.
989   if (IsUnscaled)
990     Offset /= OffsetStride;
991
992   return Offset <= 63 && Offset >= -64;
993 }
994
995 // Do alignment, specialized to power of 2 and for signed ints,
996 // avoiding having to do a C-style cast from uint_64t to int when
997 // using RoundUpToAlignment from include/llvm/Support/MathExtras.h.
998 // FIXME: Move this function to include/MathExtras.h?
999 static int alignTo(int Num, int PowOf2) {
1000   return (Num + PowOf2 - 1) & ~(PowOf2 - 1);
1001 }
1002
1003 static bool mayAlias(MachineInstr *MIa, MachineInstr *MIb,
1004                      const AArch64InstrInfo *TII) {
1005   // One of the instructions must modify memory.
1006   if (!MIa->mayStore() && !MIb->mayStore())
1007     return false;
1008
1009   // Both instructions must be memory operations.
1010   if (!MIa->mayLoadOrStore() && !MIb->mayLoadOrStore())
1011     return false;
1012
1013   return !TII->areMemAccessesTriviallyDisjoint(MIa, MIb);
1014 }
1015
1016 static bool mayAlias(MachineInstr *MIa,
1017                      SmallVectorImpl<MachineInstr *> &MemInsns,
1018                      const AArch64InstrInfo *TII) {
1019   for (auto &MIb : MemInsns)
1020     if (mayAlias(MIa, MIb, TII))
1021       return true;
1022
1023   return false;
1024 }
1025
1026 bool AArch64LoadStoreOpt::findMatchingStore(
1027     MachineBasicBlock::iterator I, unsigned Limit,
1028     MachineBasicBlock::iterator &StoreI) {
1029   MachineBasicBlock::iterator E = I->getParent()->begin();
1030   MachineBasicBlock::iterator MBBI = I;
1031   MachineInstr *FirstMI = I;
1032   unsigned BaseReg = getLdStBaseOp(FirstMI).getReg();
1033
1034   // Track which registers have been modified and used between the first insn
1035   // and the second insn.
1036   BitVector ModifiedRegs, UsedRegs;
1037   ModifiedRegs.resize(TRI->getNumRegs());
1038   UsedRegs.resize(TRI->getNumRegs());
1039
1040   for (unsigned Count = 0; MBBI != E && Count < Limit;) {
1041     --MBBI;
1042     MachineInstr *MI = MBBI;
1043     // Skip DBG_VALUE instructions. Otherwise debug info can affect the
1044     // optimization by changing how far we scan.
1045     if (MI->isDebugValue())
1046       continue;
1047     // Now that we know this is a real instruction, count it.
1048     ++Count;
1049
1050     // If the load instruction reads directly from the address to which the
1051     // store instruction writes and the stored value is not modified, we can
1052     // promote the load. Since we do not handle stores with pre-/post-index,
1053     // it's unnecessary to check if BaseReg is modified by the store itself.
1054     if (MI->mayStore() && isMatchingStore(FirstMI, MI) &&
1055         BaseReg == getLdStBaseOp(MI).getReg() &&
1056         isLdOffsetInRangeOfSt(FirstMI, MI) &&
1057         !ModifiedRegs[getLdStRegOp(MI).getReg()]) {
1058       StoreI = MBBI;
1059       return true;
1060     }
1061
1062     if (MI->isCall())
1063       return false;
1064
1065     // Update modified / uses register lists.
1066     trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
1067
1068     // Otherwise, if the base register is modified, we have no match, so
1069     // return early.
1070     if (ModifiedRegs[BaseReg])
1071       return false;
1072
1073     // If we encounter a store aliased with the load, return early.
1074     if (MI->mayStore() && mayAlias(FirstMI, MI, TII))
1075       return false;
1076   }
1077   return false;
1078 }
1079
1080 /// findMatchingInsn - Scan the instructions looking for a load/store that can
1081 /// be combined with the current instruction into a load/store pair.
1082 MachineBasicBlock::iterator
1083 AArch64LoadStoreOpt::findMatchingInsn(MachineBasicBlock::iterator I,
1084                                       LdStPairFlags &Flags, unsigned Limit) {
1085   MachineBasicBlock::iterator E = I->getParent()->end();
1086   MachineBasicBlock::iterator MBBI = I;
1087   MachineInstr *FirstMI = I;
1088   ++MBBI;
1089
1090   unsigned Opc = FirstMI->getOpcode();
1091   bool MayLoad = FirstMI->mayLoad();
1092   bool IsUnscaled = isUnscaledLdSt(FirstMI);
1093   unsigned Reg = getLdStRegOp(FirstMI).getReg();
1094   unsigned BaseReg = getLdStBaseOp(FirstMI).getReg();
1095   int Offset = getLdStOffsetOp(FirstMI).getImm();
1096   bool IsNarrowStore = isNarrowStore(Opc);
1097
1098   // For narrow stores, find only the case where the stored value is WZR.
1099   if (IsNarrowStore && Reg != AArch64::WZR)
1100     return E;
1101
1102   // Early exit if the first instruction modifies the base register.
1103   // e.g., ldr x0, [x0]
1104   if (FirstMI->modifiesRegister(BaseReg, TRI))
1105     return E;
1106
1107   // Early exit if the offset if not possible to match. (6 bits of positive
1108   // range, plus allow an extra one in case we find a later insn that matches
1109   // with Offset-1)
1110   int OffsetStride = IsUnscaled ? getMemScale(FirstMI) : 1;
1111   if (!(isNarrowLoad(Opc) || IsNarrowStore) &&
1112       !inBoundsForPair(IsUnscaled, Offset, OffsetStride))
1113     return E;
1114
1115   // Track which registers have been modified and used between the first insn
1116   // (inclusive) and the second insn.
1117   BitVector ModifiedRegs, UsedRegs;
1118   ModifiedRegs.resize(TRI->getNumRegs());
1119   UsedRegs.resize(TRI->getNumRegs());
1120
1121   // Remember any instructions that read/write memory between FirstMI and MI.
1122   SmallVector<MachineInstr *, 4> MemInsns;
1123
1124   for (unsigned Count = 0; MBBI != E && Count < Limit; ++MBBI) {
1125     MachineInstr *MI = MBBI;
1126     // Skip DBG_VALUE instructions. Otherwise debug info can affect the
1127     // optimization by changing how far we scan.
1128     if (MI->isDebugValue())
1129       continue;
1130
1131     // Now that we know this is a real instruction, count it.
1132     ++Count;
1133
1134     bool CanMergeOpc = Opc == MI->getOpcode();
1135     Flags.setSExtIdx(-1);
1136     if (!CanMergeOpc) {
1137       bool IsValidLdStrOpc;
1138       unsigned NonSExtOpc = getMatchingNonSExtOpcode(Opc, &IsValidLdStrOpc);
1139       assert(IsValidLdStrOpc &&
1140              "Given Opc should be a Load or Store with an immediate");
1141       // Opc will be the first instruction in the pair.
1142       Flags.setSExtIdx(NonSExtOpc == (unsigned)Opc ? 1 : 0);
1143       CanMergeOpc = NonSExtOpc == getMatchingNonSExtOpcode(MI->getOpcode());
1144     }
1145
1146     if (CanMergeOpc && getLdStOffsetOp(MI).isImm()) {
1147       assert(MI->mayLoadOrStore() && "Expected memory operation.");
1148       // If we've found another instruction with the same opcode, check to see
1149       // if the base and offset are compatible with our starting instruction.
1150       // These instructions all have scaled immediate operands, so we just
1151       // check for +1/-1. Make sure to check the new instruction offset is
1152       // actually an immediate and not a symbolic reference destined for
1153       // a relocation.
1154       //
1155       // Pairwise instructions have a 7-bit signed offset field. Single insns
1156       // have a 12-bit unsigned offset field. To be a valid combine, the
1157       // final offset must be in range.
1158       unsigned MIBaseReg = getLdStBaseOp(MI).getReg();
1159       int MIOffset = getLdStOffsetOp(MI).getImm();
1160       if (BaseReg == MIBaseReg && ((Offset == MIOffset + OffsetStride) ||
1161                                    (Offset + OffsetStride == MIOffset))) {
1162         int MinOffset = Offset < MIOffset ? Offset : MIOffset;
1163         // If this is a volatile load/store that otherwise matched, stop looking
1164         // as something is going on that we don't have enough information to
1165         // safely transform. Similarly, stop if we see a hint to avoid pairs.
1166         if (MI->hasOrderedMemoryRef() || TII->isLdStPairSuppressed(MI))
1167           return E;
1168         // If the resultant immediate offset of merging these instructions
1169         // is out of range for a pairwise instruction, bail and keep looking.
1170         bool MIIsUnscaled = isUnscaledLdSt(MI);
1171         bool IsNarrowLoad = isNarrowLoad(MI->getOpcode());
1172         if (!IsNarrowLoad &&
1173             !inBoundsForPair(MIIsUnscaled, MinOffset, OffsetStride)) {
1174           trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
1175           MemInsns.push_back(MI);
1176           continue;
1177         }
1178
1179         if (IsNarrowLoad || IsNarrowStore) {
1180           // If the alignment requirements of the scaled wide load/store
1181           // instruction can't express the offset of the scaled narrow
1182           // input, bail and keep looking.
1183           if (!IsUnscaled && alignTo(MinOffset, 2) != MinOffset) {
1184             trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
1185             MemInsns.push_back(MI);
1186             continue;
1187           }
1188         } else {
1189           // If the alignment requirements of the paired (scaled) instruction
1190           // can't express the offset of the unscaled input, bail and keep
1191           // looking.
1192           if (IsUnscaled && (alignTo(MinOffset, OffsetStride) != MinOffset)) {
1193             trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
1194             MemInsns.push_back(MI);
1195             continue;
1196           }
1197         }
1198         // If the destination register of the loads is the same register, bail
1199         // and keep looking. A load-pair instruction with both destination
1200         // registers the same is UNPREDICTABLE and will result in an exception.
1201         // For narrow stores, allow only when the stored value is the same
1202         // (i.e., WZR).
1203         if ((MayLoad && Reg == getLdStRegOp(MI).getReg()) ||
1204             (IsNarrowStore && Reg != getLdStRegOp(MI).getReg())) {
1205           trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
1206           MemInsns.push_back(MI);
1207           continue;
1208         }
1209
1210         // If the Rt of the second instruction was not modified or used between
1211         // the two instructions and none of the instructions between the second
1212         // and first alias with the second, we can combine the second into the
1213         // first.
1214         if (!ModifiedRegs[getLdStRegOp(MI).getReg()] &&
1215             !(MI->mayLoad() && UsedRegs[getLdStRegOp(MI).getReg()]) &&
1216             !mayAlias(MI, MemInsns, TII)) {
1217           Flags.setMergeForward(false);
1218           return MBBI;
1219         }
1220
1221         // Likewise, if the Rt of the first instruction is not modified or used
1222         // between the two instructions and none of the instructions between the
1223         // first and the second alias with the first, we can combine the first
1224         // into the second.
1225         if (!ModifiedRegs[getLdStRegOp(FirstMI).getReg()] &&
1226             !(MayLoad && UsedRegs[getLdStRegOp(FirstMI).getReg()]) &&
1227             !mayAlias(FirstMI, MemInsns, TII)) {
1228           Flags.setMergeForward(true);
1229           return MBBI;
1230         }
1231         // Unable to combine these instructions due to interference in between.
1232         // Keep looking.
1233       }
1234     }
1235
1236     // If the instruction wasn't a matching load or store.  Stop searching if we
1237     // encounter a call instruction that might modify memory.
1238     if (MI->isCall())
1239       return E;
1240
1241     // Update modified / uses register lists.
1242     trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
1243
1244     // Otherwise, if the base register is modified, we have no match, so
1245     // return early.
1246     if (ModifiedRegs[BaseReg])
1247       return E;
1248
1249     // Update list of instructions that read/write memory.
1250     if (MI->mayLoadOrStore())
1251       MemInsns.push_back(MI);
1252   }
1253   return E;
1254 }
1255
1256 MachineBasicBlock::iterator
1257 AArch64LoadStoreOpt::mergeUpdateInsn(MachineBasicBlock::iterator I,
1258                                      MachineBasicBlock::iterator Update,
1259                                      bool IsPreIdx) {
1260   assert((Update->getOpcode() == AArch64::ADDXri ||
1261           Update->getOpcode() == AArch64::SUBXri) &&
1262          "Unexpected base register update instruction to merge!");
1263   MachineBasicBlock::iterator NextI = I;
1264   // Return the instruction following the merged instruction, which is
1265   // the instruction following our unmerged load. Unless that's the add/sub
1266   // instruction we're merging, in which case it's the one after that.
1267   if (++NextI == Update)
1268     ++NextI;
1269
1270   int Value = Update->getOperand(2).getImm();
1271   assert(AArch64_AM::getShiftValue(Update->getOperand(3).getImm()) == 0 &&
1272          "Can't merge 1 << 12 offset into pre-/post-indexed load / store");
1273   if (Update->getOpcode() == AArch64::SUBXri)
1274     Value = -Value;
1275
1276   unsigned NewOpc = IsPreIdx ? getPreIndexedOpcode(I->getOpcode())
1277                              : getPostIndexedOpcode(I->getOpcode());
1278   MachineInstrBuilder MIB;
1279   if (!isPairedLdSt(I)) {
1280     // Non-paired instruction.
1281     MIB = BuildMI(*I->getParent(), I, I->getDebugLoc(), TII->get(NewOpc))
1282               .addOperand(getLdStRegOp(Update))
1283               .addOperand(getLdStRegOp(I))
1284               .addOperand(getLdStBaseOp(I))
1285               .addImm(Value);
1286   } else {
1287     // Paired instruction.
1288     int Scale = getMemScale(I);
1289     MIB = BuildMI(*I->getParent(), I, I->getDebugLoc(), TII->get(NewOpc))
1290               .addOperand(getLdStRegOp(Update))
1291               .addOperand(getLdStRegOp(I, 0))
1292               .addOperand(getLdStRegOp(I, 1))
1293               .addOperand(getLdStBaseOp(I))
1294               .addImm(Value / Scale);
1295   }
1296   (void)MIB;
1297
1298   if (IsPreIdx)
1299     DEBUG(dbgs() << "Creating pre-indexed load/store.");
1300   else
1301     DEBUG(dbgs() << "Creating post-indexed load/store.");
1302   DEBUG(dbgs() << "    Replacing instructions:\n    ");
1303   DEBUG(I->print(dbgs()));
1304   DEBUG(dbgs() << "    ");
1305   DEBUG(Update->print(dbgs()));
1306   DEBUG(dbgs() << "  with instruction:\n    ");
1307   DEBUG(((MachineInstr *)MIB)->print(dbgs()));
1308   DEBUG(dbgs() << "\n");
1309
1310   // Erase the old instructions for the block.
1311   I->eraseFromParent();
1312   Update->eraseFromParent();
1313
1314   return NextI;
1315 }
1316
1317 bool AArch64LoadStoreOpt::isMatchingUpdateInsn(MachineInstr *MemMI,
1318                                                MachineInstr *MI,
1319                                                unsigned BaseReg, int Offset) {
1320   switch (MI->getOpcode()) {
1321   default:
1322     break;
1323   case AArch64::SUBXri:
1324     // Negate the offset for a SUB instruction.
1325     Offset *= -1;
1326   // FALLTHROUGH
1327   case AArch64::ADDXri:
1328     // Make sure it's a vanilla immediate operand, not a relocation or
1329     // anything else we can't handle.
1330     if (!MI->getOperand(2).isImm())
1331       break;
1332     // Watch out for 1 << 12 shifted value.
1333     if (AArch64_AM::getShiftValue(MI->getOperand(3).getImm()))
1334       break;
1335
1336     // The update instruction source and destination register must be the
1337     // same as the load/store base register.
1338     if (MI->getOperand(0).getReg() != BaseReg ||
1339         MI->getOperand(1).getReg() != BaseReg)
1340       break;
1341
1342     bool IsPairedInsn = isPairedLdSt(MemMI);
1343     int UpdateOffset = MI->getOperand(2).getImm();
1344     // For non-paired load/store instructions, the immediate must fit in a
1345     // signed 9-bit integer.
1346     if (!IsPairedInsn && (UpdateOffset > 255 || UpdateOffset < -256))
1347       break;
1348
1349     // For paired load/store instructions, the immediate must be a multiple of
1350     // the scaling factor.  The scaled offset must also fit into a signed 7-bit
1351     // integer.
1352     if (IsPairedInsn) {
1353       int Scale = getMemScale(MemMI);
1354       if (UpdateOffset % Scale != 0)
1355         break;
1356
1357       int ScaledOffset = UpdateOffset / Scale;
1358       if (ScaledOffset > 64 || ScaledOffset < -64)
1359         break;
1360     }
1361
1362     // If we have a non-zero Offset, we check that it matches the amount
1363     // we're adding to the register.
1364     if (!Offset || Offset == MI->getOperand(2).getImm())
1365       return true;
1366     break;
1367   }
1368   return false;
1369 }
1370
1371 MachineBasicBlock::iterator AArch64LoadStoreOpt::findMatchingUpdateInsnForward(
1372     MachineBasicBlock::iterator I, unsigned Limit, int UnscaledOffset) {
1373   MachineBasicBlock::iterator E = I->getParent()->end();
1374   MachineInstr *MemMI = I;
1375   MachineBasicBlock::iterator MBBI = I;
1376
1377   unsigned BaseReg = getLdStBaseOp(MemMI).getReg();
1378   int MIUnscaledOffset = getLdStOffsetOp(MemMI).getImm() * getMemScale(MemMI);
1379
1380   // Scan forward looking for post-index opportunities.  Updating instructions
1381   // can't be formed if the memory instruction doesn't have the offset we're
1382   // looking for.
1383   if (MIUnscaledOffset != UnscaledOffset)
1384     return E;
1385
1386   // If the base register overlaps a destination register, we can't
1387   // merge the update.
1388   bool IsPairedInsn = isPairedLdSt(MemMI);
1389   for (unsigned i = 0, e = IsPairedInsn ? 2 : 1; i != e; ++i) {
1390     unsigned DestReg = getLdStRegOp(MemMI, i).getReg();
1391     if (DestReg == BaseReg || TRI->isSubRegister(BaseReg, DestReg))
1392       return E;
1393   }
1394
1395   // Track which registers have been modified and used between the first insn
1396   // (inclusive) and the second insn.
1397   BitVector ModifiedRegs, UsedRegs;
1398   ModifiedRegs.resize(TRI->getNumRegs());
1399   UsedRegs.resize(TRI->getNumRegs());
1400   ++MBBI;
1401   for (unsigned Count = 0; MBBI != E; ++MBBI) {
1402     MachineInstr *MI = MBBI;
1403     // Skip DBG_VALUE instructions. Otherwise debug info can affect the
1404     // optimization by changing how far we scan.
1405     if (MI->isDebugValue())
1406       continue;
1407
1408     // Now that we know this is a real instruction, count it.
1409     ++Count;
1410
1411     // If we found a match, return it.
1412     if (isMatchingUpdateInsn(I, MI, BaseReg, UnscaledOffset))
1413       return MBBI;
1414
1415     // Update the status of what the instruction clobbered and used.
1416     trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
1417
1418     // Otherwise, if the base register is used or modified, we have no match, so
1419     // return early.
1420     if (ModifiedRegs[BaseReg] || UsedRegs[BaseReg])
1421       return E;
1422   }
1423   return E;
1424 }
1425
1426 MachineBasicBlock::iterator AArch64LoadStoreOpt::findMatchingUpdateInsnBackward(
1427     MachineBasicBlock::iterator I, unsigned Limit) {
1428   MachineBasicBlock::iterator B = I->getParent()->begin();
1429   MachineBasicBlock::iterator E = I->getParent()->end();
1430   MachineInstr *MemMI = I;
1431   MachineBasicBlock::iterator MBBI = I;
1432
1433   unsigned BaseReg = getLdStBaseOp(MemMI).getReg();
1434   int Offset = getLdStOffsetOp(MemMI).getImm();
1435
1436   // If the load/store is the first instruction in the block, there's obviously
1437   // not any matching update. Ditto if the memory offset isn't zero.
1438   if (MBBI == B || Offset != 0)
1439     return E;
1440   // If the base register overlaps a destination register, we can't
1441   // merge the update.
1442   bool IsPairedInsn = isPairedLdSt(MemMI);
1443   for (unsigned i = 0, e = IsPairedInsn ? 2 : 1; i != e; ++i) {
1444     unsigned DestReg = getLdStRegOp(MemMI, i).getReg();
1445     if (DestReg == BaseReg || TRI->isSubRegister(BaseReg, DestReg))
1446       return E;
1447   }
1448
1449   // Track which registers have been modified and used between the first insn
1450   // (inclusive) and the second insn.
1451   BitVector ModifiedRegs, UsedRegs;
1452   ModifiedRegs.resize(TRI->getNumRegs());
1453   UsedRegs.resize(TRI->getNumRegs());
1454   --MBBI;
1455   for (unsigned Count = 0; MBBI != B; --MBBI) {
1456     MachineInstr *MI = MBBI;
1457     // Skip DBG_VALUE instructions. Otherwise debug info can affect the
1458     // optimization by changing how far we scan.
1459     if (MI->isDebugValue())
1460       continue;
1461
1462     // Now that we know this is a real instruction, count it.
1463     ++Count;
1464
1465     // If we found a match, return it.
1466     if (isMatchingUpdateInsn(I, MI, BaseReg, Offset))
1467       return MBBI;
1468
1469     // Update the status of what the instruction clobbered and used.
1470     trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
1471
1472     // Otherwise, if the base register is used or modified, we have no match, so
1473     // return early.
1474     if (ModifiedRegs[BaseReg] || UsedRegs[BaseReg])
1475       return E;
1476   }
1477   return E;
1478 }
1479
1480 bool AArch64LoadStoreOpt::tryToPromoteLoadFromStore(
1481     MachineBasicBlock::iterator &MBBI) {
1482   MachineInstr *MI = MBBI;
1483   // If this is a volatile load, don't mess with it.
1484   if (MI->hasOrderedMemoryRef())
1485     return false;
1486
1487   // Make sure this is a reg+imm.
1488   // FIXME: It is possible to extend it to handle reg+reg cases.
1489   if (!getLdStOffsetOp(MI).isImm())
1490     return false;
1491
1492   // Look backward up to ScanLimit instructions.
1493   MachineBasicBlock::iterator StoreI;
1494   if (findMatchingStore(MBBI, ScanLimit, StoreI)) {
1495     ++NumLoadsFromStoresPromoted;
1496     // Promote the load. Keeping the iterator straight is a
1497     // pain, so we let the merge routine tell us what the next instruction
1498     // is after it's done mucking about.
1499     MBBI = promoteLoadFromStore(MBBI, StoreI);
1500     return true;
1501   }
1502   return false;
1503 }
1504
1505 bool AArch64LoadStoreOpt::tryToMergeLdStInst(
1506     MachineBasicBlock::iterator &MBBI) {
1507   MachineInstr *MI = MBBI;
1508   MachineBasicBlock::iterator E = MI->getParent()->end();
1509   // If this is a volatile load/store, don't mess with it.
1510   if (MI->hasOrderedMemoryRef())
1511     return false;
1512
1513   // Make sure this is a reg+imm (as opposed to an address reloc).
1514   if (!getLdStOffsetOp(MI).isImm())
1515     return false;
1516
1517   // Check if this load/store has a hint to avoid pair formation.
1518   // MachineMemOperands hints are set by the AArch64StorePairSuppress pass.
1519   if (TII->isLdStPairSuppressed(MI))
1520     return false;
1521
1522   // Look ahead up to ScanLimit instructions for a pairable instruction.
1523   LdStPairFlags Flags;
1524   MachineBasicBlock::iterator Paired = findMatchingInsn(MBBI, Flags, ScanLimit);
1525   if (Paired != E) {
1526     if (isNarrowLoad(MI)) {
1527       ++NumNarrowLoadsPromoted;
1528     } else if (isNarrowStore(MI)) {
1529       ++NumZeroStoresPromoted;
1530     } else {
1531       ++NumPairCreated;
1532       if (isUnscaledLdSt(MI))
1533         ++NumUnscaledPairCreated;
1534     }
1535
1536     // Merge the loads into a pair. Keeping the iterator straight is a
1537     // pain, so we let the merge routine tell us what the next instruction
1538     // is after it's done mucking about.
1539     MBBI = mergePairedInsns(MBBI, Paired, Flags);
1540     return true;
1541   }
1542   return false;
1543 }
1544
1545 bool AArch64LoadStoreOpt::optimizeBlock(MachineBasicBlock &MBB,
1546                                         bool enableNarrowLdOpt) {
1547   bool Modified = false;
1548   // Three tranformations to do here:
1549   // 1) Find loads that directly read from stores and promote them by
1550   //    replacing with mov instructions. If the store is wider than the load,
1551   //    the load will be replaced with a bitfield extract.
1552   //      e.g.,
1553   //        str w1, [x0, #4]
1554   //        ldrh w2, [x0, #6]
1555   //        ; becomes
1556   //        str w1, [x0, #4]
1557   //        lsr w2, w1, #16
1558   // 2) Find narrow loads that can be converted into a single wider load
1559   //    with bitfield extract instructions.
1560   //      e.g.,
1561   //        ldrh w0, [x2]
1562   //        ldrh w1, [x2, #2]
1563   //        ; becomes
1564   //        ldr w0, [x2]
1565   //        ubfx w1, w0, #16, #16
1566   //        and w0, w0, #ffff
1567   // 3) Find loads and stores that can be merged into a single load or store
1568   //    pair instruction.
1569   //      e.g.,
1570   //        ldr x0, [x2]
1571   //        ldr x1, [x2, #8]
1572   //        ; becomes
1573   //        ldp x0, x1, [x2]
1574   // 4) Find base register updates that can be merged into the load or store
1575   //    as a base-reg writeback.
1576   //      e.g.,
1577   //        ldr x0, [x2]
1578   //        add x2, x2, #4
1579   //        ; becomes
1580   //        ldr x0, [x2], #4
1581
1582   for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
1583        MBBI != E;) {
1584     MachineInstr *MI = MBBI;
1585     switch (MI->getOpcode()) {
1586     default:
1587       // Just move on to the next instruction.
1588       ++MBBI;
1589       break;
1590     // Scaled instructions.
1591     case AArch64::LDRBBui:
1592     case AArch64::LDRHHui:
1593     case AArch64::LDRWui:
1594     case AArch64::LDRXui:
1595     // Unscaled instructions.
1596     case AArch64::LDURBBi:
1597     case AArch64::LDURHHi:
1598     case AArch64::LDURWi:
1599     case AArch64::LDURXi: {
1600       if (tryToPromoteLoadFromStore(MBBI)) {
1601         Modified = true;
1602         break;
1603       }
1604       ++MBBI;
1605       break;
1606     }
1607       // FIXME: Do the other instructions.
1608     }
1609   }
1610
1611   for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
1612        enableNarrowLdOpt && MBBI != E;) {
1613     MachineInstr *MI = MBBI;
1614     switch (MI->getOpcode()) {
1615     default:
1616       // Just move on to the next instruction.
1617       ++MBBI;
1618       break;
1619     // Scaled instructions.
1620     case AArch64::LDRBBui:
1621     case AArch64::LDRHHui:
1622     case AArch64::LDRSBWui:
1623     case AArch64::LDRSHWui:
1624     case AArch64::STRBBui:
1625     case AArch64::STRHHui:
1626     // Unscaled instructions.
1627     case AArch64::LDURBBi:
1628     case AArch64::LDURHHi:
1629     case AArch64::LDURSBWi:
1630     case AArch64::LDURSHWi:
1631     case AArch64::STURBBi:
1632     case AArch64::STURHHi: {
1633       if (tryToMergeLdStInst(MBBI)) {
1634         Modified = true;
1635         break;
1636       }
1637       ++MBBI;
1638       break;
1639     }
1640       // FIXME: Do the other instructions.
1641     }
1642   }
1643
1644   for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
1645        MBBI != E;) {
1646     MachineInstr *MI = MBBI;
1647     switch (MI->getOpcode()) {
1648     default:
1649       // Just move on to the next instruction.
1650       ++MBBI;
1651       break;
1652     // Scaled instructions.
1653     case AArch64::STRSui:
1654     case AArch64::STRDui:
1655     case AArch64::STRQui:
1656     case AArch64::STRXui:
1657     case AArch64::STRWui:
1658     case AArch64::LDRSui:
1659     case AArch64::LDRDui:
1660     case AArch64::LDRQui:
1661     case AArch64::LDRXui:
1662     case AArch64::LDRWui:
1663     case AArch64::LDRSWui:
1664     // Unscaled instructions.
1665     case AArch64::STURSi:
1666     case AArch64::STURDi:
1667     case AArch64::STURQi:
1668     case AArch64::STURWi:
1669     case AArch64::STURXi:
1670     case AArch64::LDURSi:
1671     case AArch64::LDURDi:
1672     case AArch64::LDURQi:
1673     case AArch64::LDURWi:
1674     case AArch64::LDURXi:
1675     case AArch64::LDURSWi: {
1676       if (tryToMergeLdStInst(MBBI)) {
1677         Modified = true;
1678         break;
1679       }
1680       ++MBBI;
1681       break;
1682     }
1683       // FIXME: Do the other instructions.
1684     }
1685   }
1686
1687   for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
1688        MBBI != E;) {
1689     MachineInstr *MI = MBBI;
1690     // Do update merging. It's simpler to keep this separate from the above
1691     // switch, though not strictly necessary.
1692     unsigned Opc = MI->getOpcode();
1693     switch (Opc) {
1694     default:
1695       // Just move on to the next instruction.
1696       ++MBBI;
1697       break;
1698     // Scaled instructions.
1699     case AArch64::STRSui:
1700     case AArch64::STRDui:
1701     case AArch64::STRQui:
1702     case AArch64::STRXui:
1703     case AArch64::STRWui:
1704     case AArch64::STRHHui:
1705     case AArch64::STRBBui:
1706     case AArch64::LDRSui:
1707     case AArch64::LDRDui:
1708     case AArch64::LDRQui:
1709     case AArch64::LDRXui:
1710     case AArch64::LDRWui:
1711     case AArch64::LDRHHui:
1712     case AArch64::LDRBBui:
1713     // Unscaled instructions.
1714     case AArch64::STURSi:
1715     case AArch64::STURDi:
1716     case AArch64::STURQi:
1717     case AArch64::STURWi:
1718     case AArch64::STURXi:
1719     case AArch64::LDURSi:
1720     case AArch64::LDURDi:
1721     case AArch64::LDURQi:
1722     case AArch64::LDURWi:
1723     case AArch64::LDURXi:
1724     // Paired instructions.
1725     case AArch64::LDPSi:
1726     case AArch64::LDPSWi:
1727     case AArch64::LDPDi:
1728     case AArch64::LDPQi:
1729     case AArch64::LDPWi:
1730     case AArch64::LDPXi:
1731     case AArch64::STPSi:
1732     case AArch64::STPDi:
1733     case AArch64::STPQi:
1734     case AArch64::STPWi:
1735     case AArch64::STPXi: {
1736       // Make sure this is a reg+imm (as opposed to an address reloc).
1737       if (!getLdStOffsetOp(MI).isImm()) {
1738         ++MBBI;
1739         break;
1740       }
1741       // Look forward to try to form a post-index instruction. For example,
1742       // ldr x0, [x20]
1743       // add x20, x20, #32
1744       //   merged into:
1745       // ldr x0, [x20], #32
1746       MachineBasicBlock::iterator Update =
1747           findMatchingUpdateInsnForward(MBBI, ScanLimit, 0);
1748       if (Update != E) {
1749         // Merge the update into the ld/st.
1750         MBBI = mergeUpdateInsn(MBBI, Update, /*IsPreIdx=*/false);
1751         Modified = true;
1752         ++NumPostFolded;
1753         break;
1754       }
1755       // Don't know how to handle pre/post-index versions, so move to the next
1756       // instruction.
1757       if (isUnscaledLdSt(Opc)) {
1758         ++MBBI;
1759         break;
1760       }
1761
1762       // Look back to try to find a pre-index instruction. For example,
1763       // add x0, x0, #8
1764       // ldr x1, [x0]
1765       //   merged into:
1766       // ldr x1, [x0, #8]!
1767       Update = findMatchingUpdateInsnBackward(MBBI, ScanLimit);
1768       if (Update != E) {
1769         // Merge the update into the ld/st.
1770         MBBI = mergeUpdateInsn(MBBI, Update, /*IsPreIdx=*/true);
1771         Modified = true;
1772         ++NumPreFolded;
1773         break;
1774       }
1775       // The immediate in the load/store is scaled by the size of the memory
1776       // operation. The immediate in the add we're looking for,
1777       // however, is not, so adjust here.
1778       int UnscaledOffset = getLdStOffsetOp(MI).getImm() * getMemScale(MI);
1779
1780       // Look forward to try to find a post-index instruction. For example,
1781       // ldr x1, [x0, #64]
1782       // add x0, x0, #64
1783       //   merged into:
1784       // ldr x1, [x0, #64]!
1785       Update = findMatchingUpdateInsnForward(MBBI, ScanLimit, UnscaledOffset);
1786       if (Update != E) {
1787         // Merge the update into the ld/st.
1788         MBBI = mergeUpdateInsn(MBBI, Update, /*IsPreIdx=*/true);
1789         Modified = true;
1790         ++NumPreFolded;
1791         break;
1792       }
1793
1794       // Nothing found. Just move to the next instruction.
1795       ++MBBI;
1796       break;
1797     }
1798       // FIXME: Do the other instructions.
1799     }
1800   }
1801
1802   return Modified;
1803 }
1804
1805 bool AArch64LoadStoreOpt::enableNarrowLdMerge(MachineFunction &Fn) {
1806   bool ProfitableArch = Subtarget->isCortexA57();
1807   // FIXME: The benefit from converting narrow loads into a wider load could be
1808   // microarchitectural as it assumes that a single load with two bitfield
1809   // extracts is cheaper than two narrow loads. Currently, this conversion is
1810   // enabled only in cortex-a57 on which performance benefits were verified.
1811   return ProfitableArch && !Subtarget->requiresStrictAlign();
1812 }
1813
1814 bool AArch64LoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
1815   Subtarget = &static_cast<const AArch64Subtarget &>(Fn.getSubtarget());
1816   TII = static_cast<const AArch64InstrInfo *>(Subtarget->getInstrInfo());
1817   TRI = Subtarget->getRegisterInfo();
1818
1819   bool Modified = false;
1820   bool enableNarrowLdOpt = enableNarrowLdMerge(Fn);
1821   for (auto &MBB : Fn)
1822     Modified |= optimizeBlock(MBB, enableNarrowLdOpt);
1823
1824   return Modified;
1825 }
1826
1827 // FIXME: Do we need/want a pre-alloc pass like ARM has to try to keep
1828 // loads and stores near one another?
1829
1830 /// createAArch64LoadStoreOptimizationPass - returns an instance of the
1831 /// load / store optimization pass.
1832 FunctionPass *llvm::createAArch64LoadStoreOptimizationPass() {
1833   return new AArch64LoadStoreOpt();
1834 }