1//===- AArch64LoadStoreOptimizer.cpp - AArch64 load/store opt. pass -------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains a pass that performs load / store related peephole
10// optimizations. This pass should be run after register allocation.
11//
12// The pass runs after the PrologEpilogInserter where we emit the CFI
13// instructions. In order to preserve the correctness of the unwind informaiton,
14// the pass should not change the order of any two instructions, one of which
15// has the FrameSetup/FrameDestroy flag or, alternatively, apply an add-hoc fix
16// to unwind information.
17//
18//===----------------------------------------------------------------------===//
19
20#include "AArch64InstrInfo.h"
21#include "AArch64MachineFunctionInfo.h"
22#include "AArch64Subtarget.h"
23#include "MCTargetDesc/AArch64AddressingModes.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/ADT/StringRef.h"
27#include "llvm/ADT/iterator_range.h"
28#include "llvm/Analysis/AliasAnalysis.h"
29#include "llvm/CodeGen/MachineBasicBlock.h"
30#include "llvm/CodeGen/MachineFunction.h"
31#include "llvm/CodeGen/MachineFunctionPass.h"
32#include "llvm/CodeGen/MachineInstr.h"
33#include "llvm/CodeGen/MachineInstrBuilder.h"
34#include "llvm/CodeGen/MachineOperand.h"
35#include "llvm/CodeGen/MachineRegisterInfo.h"
36#include "llvm/CodeGen/TargetRegisterInfo.h"
37#include "llvm/IR/DebugLoc.h"
38#include "llvm/MC/MCAsmInfo.h"
39#include "llvm/MC/MCDwarf.h"
40#include "llvm/MC/MCRegisterInfo.h"
41#include "llvm/Pass.h"
42#include "llvm/Support/CommandLine.h"
43#include "llvm/Support/Debug.h"
44#include "llvm/Support/DebugCounter.h"
45#include "llvm/Support/ErrorHandling.h"
46#include "llvm/Support/raw_ostream.h"
47#include <cassert>
48#include <cstdint>
49#include <functional>
50#include <iterator>
51#include <limits>
52#include <optional>
53
54using namespace llvm;
55
56#define DEBUG_TYPE "aarch64-ldst-opt"
57
58STATISTIC(NumPairCreated, "Number of load/store pair instructions generated");
59STATISTIC(NumPostFolded, "Number of post-index updates folded");
60STATISTIC(NumPreFolded, "Number of pre-index updates folded");
61STATISTIC(NumUnscaledPairCreated,
62 "Number of load/store from unscaled generated");
63STATISTIC(NumZeroStoresPromoted, "Number of narrow zero stores promoted");
64STATISTIC(NumLoadsFromStoresPromoted, "Number of loads from stores promoted");
65STATISTIC(NumFailedAlignmentCheck, "Number of load/store pair transformation "
66 "not passed the alignment check");
67
68DEBUG_COUNTER(RegRenamingCounter, DEBUG_TYPE "-reg-renaming",
69 "Controls which pairs are considered for renaming");
70
71// The LdStLimit limits how far we search for load/store pairs.
72static cl::opt<unsigned> LdStLimit("aarch64-load-store-scan-limit",
73 cl::init(Val: 20), cl::Hidden);
74
75// The UpdateLimit limits how far we search for update instructions when we form
76// pre-/post-index instructions.
77static cl::opt<unsigned> UpdateLimit("aarch64-update-scan-limit", cl::init(Val: 100),
78 cl::Hidden);
79
80// Enable register renaming to find additional store pairing opportunities.
81static cl::opt<bool> EnableRenaming("aarch64-load-store-renaming",
82 cl::init(Val: true), cl::Hidden);
83
84#define AARCH64_LOAD_STORE_OPT_NAME "AArch64 load / store optimization pass"
85
86namespace {
87
88using LdStPairFlags = struct LdStPairFlags {
89 // If a matching instruction is found, MergeForward is set to true if the
90 // merge is to remove the first instruction and replace the second with
91 // a pair-wise insn, and false if the reverse is true.
92 bool MergeForward = false;
93
94 // SExtIdx gives the index of the result of the load pair that must be
95 // extended. The value of SExtIdx assumes that the paired load produces the
96 // value in this order: (I, returned iterator), i.e., -1 means no value has
97 // to be extended, 0 means I, and 1 means the returned iterator.
98 int SExtIdx = -1;
99
100 // If not none, RenameReg can be used to rename the result register of the
101 // first store in a pair. Currently this only works when merging stores
102 // forward.
103 std::optional<MCPhysReg> RenameReg;
104
105 LdStPairFlags() = default;
106
107 void setMergeForward(bool V = true) { MergeForward = V; }
108 bool getMergeForward() const { return MergeForward; }
109
110 void setSExtIdx(int V) { SExtIdx = V; }
111 int getSExtIdx() const { return SExtIdx; }
112
113 void setRenameReg(MCPhysReg R) { RenameReg = R; }
114 void clearRenameReg() { RenameReg = std::nullopt; }
115 std::optional<MCPhysReg> getRenameReg() const { return RenameReg; }
116};
117
118struct AArch64LoadStoreOpt : public MachineFunctionPass {
119 static char ID;
120
121 AArch64LoadStoreOpt() : MachineFunctionPass(ID) {
122 initializeAArch64LoadStoreOptPass(*PassRegistry::getPassRegistry());
123 }
124
125 AliasAnalysis *AA;
126 const AArch64InstrInfo *TII;
127 const TargetRegisterInfo *TRI;
128 const AArch64Subtarget *Subtarget;
129
130 // Track which register units have been modified and used.
131 LiveRegUnits ModifiedRegUnits, UsedRegUnits;
132 LiveRegUnits DefinedInBB;
133
134 void getAnalysisUsage(AnalysisUsage &AU) const override {
135 AU.addRequired<AAResultsWrapperPass>();
136 MachineFunctionPass::getAnalysisUsage(AU);
137 }
138
139 // Scan the instructions looking for a load/store that can be combined
140 // with the current instruction into a load/store pair.
141 // Return the matching instruction if one is found, else MBB->end().
142 MachineBasicBlock::iterator findMatchingInsn(MachineBasicBlock::iterator I,
143 LdStPairFlags &Flags,
144 unsigned Limit,
145 bool FindNarrowMerge);
146
147 // Scan the instructions looking for a store that writes to the address from
148 // which the current load instruction reads. Return true if one is found.
149 bool findMatchingStore(MachineBasicBlock::iterator I, unsigned Limit,
150 MachineBasicBlock::iterator &StoreI);
151
152 // Merge the two instructions indicated into a wider narrow store instruction.
153 MachineBasicBlock::iterator
154 mergeNarrowZeroStores(MachineBasicBlock::iterator I,
155 MachineBasicBlock::iterator MergeMI,
156 const LdStPairFlags &Flags);
157
158 // Merge the two instructions indicated into a single pair-wise instruction.
159 MachineBasicBlock::iterator
160 mergePairedInsns(MachineBasicBlock::iterator I,
161 MachineBasicBlock::iterator Paired,
162 const LdStPairFlags &Flags);
163
164 // Promote the load that reads directly from the address stored to.
165 MachineBasicBlock::iterator
166 promoteLoadFromStore(MachineBasicBlock::iterator LoadI,
167 MachineBasicBlock::iterator StoreI);
168
169 // Scan the instruction list to find a base register update that can
170 // be combined with the current instruction (a load or store) using
171 // pre or post indexed addressing with writeback. Scan forwards.
172 MachineBasicBlock::iterator
173 findMatchingUpdateInsnForward(MachineBasicBlock::iterator I,
174 int UnscaledOffset, unsigned Limit);
175
176 // Scan the instruction list to find a base register update that can
177 // be combined with the current instruction (a load or store) using
178 // pre or post indexed addressing with writeback. Scan backwards.
179 MachineBasicBlock::iterator
180 findMatchingUpdateInsnBackward(MachineBasicBlock::iterator I, unsigned Limit);
181
182 // Find an instruction that updates the base register of the ld/st
183 // instruction.
184 bool isMatchingUpdateInsn(MachineInstr &MemMI, MachineInstr &MI,
185 unsigned BaseReg, int Offset);
186
187 // Merge a pre- or post-index base register update into a ld/st instruction.
188 MachineBasicBlock::iterator
189 mergeUpdateInsn(MachineBasicBlock::iterator I,
190 MachineBasicBlock::iterator Update, bool IsPreIdx);
191
192 // Find and merge zero store instructions.
193 bool tryToMergeZeroStInst(MachineBasicBlock::iterator &MBBI);
194
195 // Find and pair ldr/str instructions.
196 bool tryToPairLdStInst(MachineBasicBlock::iterator &MBBI);
197
198 // Find and promote load instructions which read directly from store.
199 bool tryToPromoteLoadFromStore(MachineBasicBlock::iterator &MBBI);
200
201 // Find and merge a base register updates before or after a ld/st instruction.
202 bool tryToMergeLdStUpdate(MachineBasicBlock::iterator &MBBI);
203
204 bool optimizeBlock(MachineBasicBlock &MBB, bool EnableNarrowZeroStOpt);
205
206 bool runOnMachineFunction(MachineFunction &Fn) override;
207
208 MachineFunctionProperties getRequiredProperties() const override {
209 return MachineFunctionProperties().set(
210 MachineFunctionProperties::Property::NoVRegs);
211 }
212
213 StringRef getPassName() const override { return AARCH64_LOAD_STORE_OPT_NAME; }
214};
215
216char AArch64LoadStoreOpt::ID = 0;
217
218} // end anonymous namespace
219
220INITIALIZE_PASS(AArch64LoadStoreOpt, "aarch64-ldst-opt",
221 AARCH64_LOAD_STORE_OPT_NAME, false, false)
222
223static bool isNarrowStore(unsigned Opc) {
224 switch (Opc) {
225 default:
226 return false;
227 case AArch64::STRBBui:
228 case AArch64::STURBBi:
229 case AArch64::STRHHui:
230 case AArch64::STURHHi:
231 return true;
232 }
233}
234
235// These instruction set memory tag and either keep memory contents unchanged or
236// set it to zero, ignoring the address part of the source register.
237static bool isTagStore(const MachineInstr &MI) {
238 switch (MI.getOpcode()) {
239 default:
240 return false;
241 case AArch64::STGi:
242 case AArch64::STZGi:
243 case AArch64::ST2Gi:
244 case AArch64::STZ2Gi:
245 return true;
246 }
247}
248
249static unsigned getMatchingNonSExtOpcode(unsigned Opc,
250 bool *IsValidLdStrOpc = nullptr) {
251 if (IsValidLdStrOpc)
252 *IsValidLdStrOpc = true;
253 switch (Opc) {
254 default:
255 if (IsValidLdStrOpc)
256 *IsValidLdStrOpc = false;
257 return std::numeric_limits<unsigned>::max();
258 case AArch64::STRDui:
259 case AArch64::STURDi:
260 case AArch64::STRDpre:
261 case AArch64::STRQui:
262 case AArch64::STURQi:
263 case AArch64::STRQpre:
264 case AArch64::STRBBui:
265 case AArch64::STURBBi:
266 case AArch64::STRHHui:
267 case AArch64::STURHHi:
268 case AArch64::STRWui:
269 case AArch64::STRWpre:
270 case AArch64::STURWi:
271 case AArch64::STRXui:
272 case AArch64::STRXpre:
273 case AArch64::STURXi:
274 case AArch64::LDRDui:
275 case AArch64::LDURDi:
276 case AArch64::LDRDpre:
277 case AArch64::LDRQui:
278 case AArch64::LDURQi:
279 case AArch64::LDRQpre:
280 case AArch64::LDRWui:
281 case AArch64::LDURWi:
282 case AArch64::LDRWpre:
283 case AArch64::LDRXui:
284 case AArch64::LDURXi:
285 case AArch64::LDRXpre:
286 case AArch64::STRSui:
287 case AArch64::STURSi:
288 case AArch64::STRSpre:
289 case AArch64::LDRSui:
290 case AArch64::LDURSi:
291 case AArch64::LDRSpre:
292 return Opc;
293 case AArch64::LDRSWui:
294 return AArch64::LDRWui;
295 case AArch64::LDURSWi:
296 return AArch64::LDURWi;
297 case AArch64::LDRSWpre:
298 return AArch64::LDRWpre;
299 }
300}
301
302static unsigned getMatchingWideOpcode(unsigned Opc) {
303 switch (Opc) {
304 default:
305 llvm_unreachable("Opcode has no wide equivalent!");
306 case AArch64::STRBBui:
307 return AArch64::STRHHui;
308 case AArch64::STRHHui:
309 return AArch64::STRWui;
310 case AArch64::STURBBi:
311 return AArch64::STURHHi;
312 case AArch64::STURHHi:
313 return AArch64::STURWi;
314 case AArch64::STURWi:
315 return AArch64::STURXi;
316 case AArch64::STRWui:
317 return AArch64::STRXui;
318 }
319}
320
321static unsigned getMatchingPairOpcode(unsigned Opc) {
322 switch (Opc) {
323 default:
324 llvm_unreachable("Opcode has no pairwise equivalent!");
325 case AArch64::STRSui:
326 case AArch64::STURSi:
327 return AArch64::STPSi;
328 case AArch64::STRSpre:
329 return AArch64::STPSpre;
330 case AArch64::STRDui:
331 case AArch64::STURDi:
332 return AArch64::STPDi;
333 case AArch64::STRDpre:
334 return AArch64::STPDpre;
335 case AArch64::STRQui:
336 case AArch64::STURQi:
337 return AArch64::STPQi;
338 case AArch64::STRQpre:
339 return AArch64::STPQpre;
340 case AArch64::STRWui:
341 case AArch64::STURWi:
342 return AArch64::STPWi;
343 case AArch64::STRWpre:
344 return AArch64::STPWpre;
345 case AArch64::STRXui:
346 case AArch64::STURXi:
347 return AArch64::STPXi;
348 case AArch64::STRXpre:
349 return AArch64::STPXpre;
350 case AArch64::LDRSui:
351 case AArch64::LDURSi:
352 return AArch64::LDPSi;
353 case AArch64::LDRSpre:
354 return AArch64::LDPSpre;
355 case AArch64::LDRDui:
356 case AArch64::LDURDi:
357 return AArch64::LDPDi;
358 case AArch64::LDRDpre:
359 return AArch64::LDPDpre;
360 case AArch64::LDRQui:
361 case AArch64::LDURQi:
362 return AArch64::LDPQi;
363 case AArch64::LDRQpre:
364 return AArch64::LDPQpre;
365 case AArch64::LDRWui:
366 case AArch64::LDURWi:
367 return AArch64::LDPWi;
368 case AArch64::LDRWpre:
369 return AArch64::LDPWpre;
370 case AArch64::LDRXui:
371 case AArch64::LDURXi:
372 return AArch64::LDPXi;
373 case AArch64::LDRXpre:
374 return AArch64::LDPXpre;
375 case AArch64::LDRSWui:
376 case AArch64::LDURSWi:
377 return AArch64::LDPSWi;
378 case AArch64::LDRSWpre:
379 return AArch64::LDPSWpre;
380 }
381}
382
383static unsigned isMatchingStore(MachineInstr &LoadInst,
384 MachineInstr &StoreInst) {
385 unsigned LdOpc = LoadInst.getOpcode();
386 unsigned StOpc = StoreInst.getOpcode();
387 switch (LdOpc) {
388 default:
389 llvm_unreachable("Unsupported load instruction!");
390 case AArch64::LDRBBui:
391 return StOpc == AArch64::STRBBui || StOpc == AArch64::STRHHui ||
392 StOpc == AArch64::STRWui || StOpc == AArch64::STRXui;
393 case AArch64::LDURBBi:
394 return StOpc == AArch64::STURBBi || StOpc == AArch64::STURHHi ||
395 StOpc == AArch64::STURWi || StOpc == AArch64::STURXi;
396 case AArch64::LDRHHui:
397 return StOpc == AArch64::STRHHui || StOpc == AArch64::STRWui ||
398 StOpc == AArch64::STRXui;
399 case AArch64::LDURHHi:
400 return StOpc == AArch64::STURHHi || StOpc == AArch64::STURWi ||
401 StOpc == AArch64::STURXi;
402 case AArch64::LDRWui:
403 return StOpc == AArch64::STRWui || StOpc == AArch64::STRXui;
404 case AArch64::LDURWi:
405 return StOpc == AArch64::STURWi || StOpc == AArch64::STURXi;
406 case AArch64::LDRXui:
407 return StOpc == AArch64::STRXui;
408 case AArch64::LDURXi:
409 return StOpc == AArch64::STURXi;
410 }
411}
412
413static unsigned getPreIndexedOpcode(unsigned Opc) {
414 // FIXME: We don't currently support creating pre-indexed loads/stores when
415 // the load or store is the unscaled version. If we decide to perform such an
416 // optimization in the future the cases for the unscaled loads/stores will
417 // need to be added here.
418 switch (Opc) {
419 default:
420 llvm_unreachable("Opcode has no pre-indexed equivalent!");
421 case AArch64::STRSui:
422 return AArch64::STRSpre;
423 case AArch64::STRDui:
424 return AArch64::STRDpre;
425 case AArch64::STRQui:
426 return AArch64::STRQpre;
427 case AArch64::STRBBui:
428 return AArch64::STRBBpre;
429 case AArch64::STRHHui:
430 return AArch64::STRHHpre;
431 case AArch64::STRWui:
432 return AArch64::STRWpre;
433 case AArch64::STRXui:
434 return AArch64::STRXpre;
435 case AArch64::LDRSui:
436 return AArch64::LDRSpre;
437 case AArch64::LDRDui:
438 return AArch64::LDRDpre;
439 case AArch64::LDRQui:
440 return AArch64::LDRQpre;
441 case AArch64::LDRBBui:
442 return AArch64::LDRBBpre;
443 case AArch64::LDRHHui:
444 return AArch64::LDRHHpre;
445 case AArch64::LDRWui:
446 return AArch64::LDRWpre;
447 case AArch64::LDRXui:
448 return AArch64::LDRXpre;
449 case AArch64::LDRSWui:
450 return AArch64::LDRSWpre;
451 case AArch64::LDPSi:
452 return AArch64::LDPSpre;
453 case AArch64::LDPSWi:
454 return AArch64::LDPSWpre;
455 case AArch64::LDPDi:
456 return AArch64::LDPDpre;
457 case AArch64::LDPQi:
458 return AArch64::LDPQpre;
459 case AArch64::LDPWi:
460 return AArch64::LDPWpre;
461 case AArch64::LDPXi:
462 return AArch64::LDPXpre;
463 case AArch64::STPSi:
464 return AArch64::STPSpre;
465 case AArch64::STPDi:
466 return AArch64::STPDpre;
467 case AArch64::STPQi:
468 return AArch64::STPQpre;
469 case AArch64::STPWi:
470 return AArch64::STPWpre;
471 case AArch64::STPXi:
472 return AArch64::STPXpre;
473 case AArch64::STGi:
474 return AArch64::STGPreIndex;
475 case AArch64::STZGi:
476 return AArch64::STZGPreIndex;
477 case AArch64::ST2Gi:
478 return AArch64::ST2GPreIndex;
479 case AArch64::STZ2Gi:
480 return AArch64::STZ2GPreIndex;
481 case AArch64::STGPi:
482 return AArch64::STGPpre;
483 }
484}
485
486static unsigned getPostIndexedOpcode(unsigned Opc) {
487 switch (Opc) {
488 default:
489 llvm_unreachable("Opcode has no post-indexed wise equivalent!");
490 case AArch64::STRSui:
491 case AArch64::STURSi:
492 return AArch64::STRSpost;
493 case AArch64::STRDui:
494 case AArch64::STURDi:
495 return AArch64::STRDpost;
496 case AArch64::STRQui:
497 case AArch64::STURQi:
498 return AArch64::STRQpost;
499 case AArch64::STRBBui:
500 return AArch64::STRBBpost;
501 case AArch64::STRHHui:
502 return AArch64::STRHHpost;
503 case AArch64::STRWui:
504 case AArch64::STURWi:
505 return AArch64::STRWpost;
506 case AArch64::STRXui:
507 case AArch64::STURXi:
508 return AArch64::STRXpost;
509 case AArch64::LDRSui:
510 case AArch64::LDURSi:
511 return AArch64::LDRSpost;
512 case AArch64::LDRDui:
513 case AArch64::LDURDi:
514 return AArch64::LDRDpost;
515 case AArch64::LDRQui:
516 case AArch64::LDURQi:
517 return AArch64::LDRQpost;
518 case AArch64::LDRBBui:
519 return AArch64::LDRBBpost;
520 case AArch64::LDRHHui:
521 return AArch64::LDRHHpost;
522 case AArch64::LDRWui:
523 case AArch64::LDURWi:
524 return AArch64::LDRWpost;
525 case AArch64::LDRXui:
526 case AArch64::LDURXi:
527 return AArch64::LDRXpost;
528 case AArch64::LDRSWui:
529 return AArch64::LDRSWpost;
530 case AArch64::LDPSi:
531 return AArch64::LDPSpost;
532 case AArch64::LDPSWi:
533 return AArch64::LDPSWpost;
534 case AArch64::LDPDi:
535 return AArch64::LDPDpost;
536 case AArch64::LDPQi:
537 return AArch64::LDPQpost;
538 case AArch64::LDPWi:
539 return AArch64::LDPWpost;
540 case AArch64::LDPXi:
541 return AArch64::LDPXpost;
542 case AArch64::STPSi:
543 return AArch64::STPSpost;
544 case AArch64::STPDi:
545 return AArch64::STPDpost;
546 case AArch64::STPQi:
547 return AArch64::STPQpost;
548 case AArch64::STPWi:
549 return AArch64::STPWpost;
550 case AArch64::STPXi:
551 return AArch64::STPXpost;
552 case AArch64::STGi:
553 return AArch64::STGPostIndex;
554 case AArch64::STZGi:
555 return AArch64::STZGPostIndex;
556 case AArch64::ST2Gi:
557 return AArch64::ST2GPostIndex;
558 case AArch64::STZ2Gi:
559 return AArch64::STZ2GPostIndex;
560 case AArch64::STGPi:
561 return AArch64::STGPpost;
562 }
563}
564
565static bool isPreLdStPairCandidate(MachineInstr &FirstMI, MachineInstr &MI) {
566
567 unsigned OpcA = FirstMI.getOpcode();
568 unsigned OpcB = MI.getOpcode();
569
570 switch (OpcA) {
571 default:
572 return false;
573 case AArch64::STRSpre:
574 return (OpcB == AArch64::STRSui) || (OpcB == AArch64::STURSi);
575 case AArch64::STRDpre:
576 return (OpcB == AArch64::STRDui) || (OpcB == AArch64::STURDi);
577 case AArch64::STRQpre:
578 return (OpcB == AArch64::STRQui) || (OpcB == AArch64::STURQi);
579 case AArch64::STRWpre:
580 return (OpcB == AArch64::STRWui) || (OpcB == AArch64::STURWi);
581 case AArch64::STRXpre:
582 return (OpcB == AArch64::STRXui) || (OpcB == AArch64::STURXi);
583 case AArch64::LDRSpre:
584 return (OpcB == AArch64::LDRSui) || (OpcB == AArch64::LDURSi);
585 case AArch64::LDRDpre:
586 return (OpcB == AArch64::LDRDui) || (OpcB == AArch64::LDURDi);
587 case AArch64::LDRQpre:
588 return (OpcB == AArch64::LDRQui) || (OpcB == AArch64::LDURQi);
589 case AArch64::LDRWpre:
590 return (OpcB == AArch64::LDRWui) || (OpcB == AArch64::LDURWi);
591 case AArch64::LDRXpre:
592 return (OpcB == AArch64::LDRXui) || (OpcB == AArch64::LDURXi);
593 case AArch64::LDRSWpre:
594 return (OpcB == AArch64::LDRSWui) || (OpcB == AArch64::LDURSWi);
595 }
596}
597
598// Returns the scale and offset range of pre/post indexed variants of MI.
599static void getPrePostIndexedMemOpInfo(const MachineInstr &MI, int &Scale,
600 int &MinOffset, int &MaxOffset) {
601 bool IsPaired = AArch64InstrInfo::isPairedLdSt(MI);
602 bool IsTagStore = isTagStore(MI);
603 // ST*G and all paired ldst have the same scale in pre/post-indexed variants
604 // as in the "unsigned offset" variant.
605 // All other pre/post indexed ldst instructions are unscaled.
606 Scale = (IsTagStore || IsPaired) ? AArch64InstrInfo::getMemScale(MI) : 1;
607
608 if (IsPaired) {
609 MinOffset = -64;
610 MaxOffset = 63;
611 } else {
612 MinOffset = -256;
613 MaxOffset = 255;
614 }
615}
616
617static MachineOperand &getLdStRegOp(MachineInstr &MI,
618 unsigned PairedRegOp = 0) {
619 assert(PairedRegOp < 2 && "Unexpected register operand idx.");
620 bool IsPreLdSt = AArch64InstrInfo::isPreLdSt(MI);
621 if (IsPreLdSt)
622 PairedRegOp += 1;
623 unsigned Idx =
624 AArch64InstrInfo::isPairedLdSt(MI) || IsPreLdSt ? PairedRegOp : 0;
625 return MI.getOperand(i: Idx);
626}
627
628static bool isLdOffsetInRangeOfSt(MachineInstr &LoadInst,
629 MachineInstr &StoreInst,
630 const AArch64InstrInfo *TII) {
631 assert(isMatchingStore(LoadInst, StoreInst) && "Expect only matched ld/st.");
632 int LoadSize = TII->getMemScale(MI: LoadInst);
633 int StoreSize = TII->getMemScale(MI: StoreInst);
634 int UnscaledStOffset =
635 TII->hasUnscaledLdStOffset(MI&: StoreInst)
636 ? AArch64InstrInfo::getLdStOffsetOp(MI: StoreInst).getImm()
637 : AArch64InstrInfo::getLdStOffsetOp(MI: StoreInst).getImm() * StoreSize;
638 int UnscaledLdOffset =
639 TII->hasUnscaledLdStOffset(MI&: LoadInst)
640 ? AArch64InstrInfo::getLdStOffsetOp(MI: LoadInst).getImm()
641 : AArch64InstrInfo::getLdStOffsetOp(MI: LoadInst).getImm() * LoadSize;
642 return (UnscaledStOffset <= UnscaledLdOffset) &&
643 (UnscaledLdOffset + LoadSize <= (UnscaledStOffset + StoreSize));
644}
645
646static bool isPromotableZeroStoreInst(MachineInstr &MI) {
647 unsigned Opc = MI.getOpcode();
648 return (Opc == AArch64::STRWui || Opc == AArch64::STURWi ||
649 isNarrowStore(Opc)) &&
650 getLdStRegOp(MI).getReg() == AArch64::WZR;
651}
652
653static bool isPromotableLoadFromStore(MachineInstr &MI) {
654 switch (MI.getOpcode()) {
655 default:
656 return false;
657 // Scaled instructions.
658 case AArch64::LDRBBui:
659 case AArch64::LDRHHui:
660 case AArch64::LDRWui:
661 case AArch64::LDRXui:
662 // Unscaled instructions.
663 case AArch64::LDURBBi:
664 case AArch64::LDURHHi:
665 case AArch64::LDURWi:
666 case AArch64::LDURXi:
667 return true;
668 }
669}
670
671static bool isMergeableLdStUpdate(MachineInstr &MI) {
672 unsigned Opc = MI.getOpcode();
673 switch (Opc) {
674 default:
675 return false;
676 // Scaled instructions.
677 case AArch64::STRSui:
678 case AArch64::STRDui:
679 case AArch64::STRQui:
680 case AArch64::STRXui:
681 case AArch64::STRWui:
682 case AArch64::STRHHui:
683 case AArch64::STRBBui:
684 case AArch64::LDRSui:
685 case AArch64::LDRDui:
686 case AArch64::LDRQui:
687 case AArch64::LDRXui:
688 case AArch64::LDRWui:
689 case AArch64::LDRHHui:
690 case AArch64::LDRBBui:
691 case AArch64::STGi:
692 case AArch64::STZGi:
693 case AArch64::ST2Gi:
694 case AArch64::STZ2Gi:
695 case AArch64::STGPi:
696 // Unscaled instructions.
697 case AArch64::STURSi:
698 case AArch64::STURDi:
699 case AArch64::STURQi:
700 case AArch64::STURWi:
701 case AArch64::STURXi:
702 case AArch64::LDURSi:
703 case AArch64::LDURDi:
704 case AArch64::LDURQi:
705 case AArch64::LDURWi:
706 case AArch64::LDURXi:
707 // Paired instructions.
708 case AArch64::LDPSi:
709 case AArch64::LDPSWi:
710 case AArch64::LDPDi:
711 case AArch64::LDPQi:
712 case AArch64::LDPWi:
713 case AArch64::LDPXi:
714 case AArch64::STPSi:
715 case AArch64::STPDi:
716 case AArch64::STPQi:
717 case AArch64::STPWi:
718 case AArch64::STPXi:
719 // Make sure this is a reg+imm (as opposed to an address reloc).
720 if (!AArch64InstrInfo::getLdStOffsetOp(MI).isImm())
721 return false;
722
723 return true;
724 }
725}
726
727static bool isRewritableImplicitDef(unsigned Opc) {
728 switch (Opc) {
729 default:
730 return false;
731 case AArch64::ORRWrs:
732 case AArch64::ADDWri:
733 return true;
734 }
735}
736
737MachineBasicBlock::iterator
738AArch64LoadStoreOpt::mergeNarrowZeroStores(MachineBasicBlock::iterator I,
739 MachineBasicBlock::iterator MergeMI,
740 const LdStPairFlags &Flags) {
741 assert(isPromotableZeroStoreInst(*I) && isPromotableZeroStoreInst(*MergeMI) &&
742 "Expected promotable zero stores.");
743
744 MachineBasicBlock::iterator E = I->getParent()->end();
745 MachineBasicBlock::iterator NextI = next_nodbg(It: I, End: E);
746 // If NextI is the second of the two instructions to be merged, we need
747 // to skip one further. Either way we merge will invalidate the iterator,
748 // and we don't need to scan the new instruction, as it's a pairwise
749 // instruction, which we're not considering for further action anyway.
750 if (NextI == MergeMI)
751 NextI = next_nodbg(It: NextI, End: E);
752
753 unsigned Opc = I->getOpcode();
754 unsigned MergeMIOpc = MergeMI->getOpcode();
755 bool IsScaled = !TII->hasUnscaledLdStOffset(Opc);
756 bool IsMergedMIScaled = !TII->hasUnscaledLdStOffset(Opc: MergeMIOpc);
757 int OffsetStride = IsScaled ? TII->getMemScale(MI: *I) : 1;
758 int MergeMIOffsetStride = IsMergedMIScaled ? TII->getMemScale(MI: *MergeMI) : 1;
759
760 bool MergeForward = Flags.getMergeForward();
761 // Insert our new paired instruction after whichever of the paired
762 // instructions MergeForward indicates.
763 MachineBasicBlock::iterator InsertionPoint = MergeForward ? MergeMI : I;
764 // Also based on MergeForward is from where we copy the base register operand
765 // so we get the flags compatible with the input code.
766 const MachineOperand &BaseRegOp =
767 MergeForward ? AArch64InstrInfo::getLdStBaseOp(MI: *MergeMI)
768 : AArch64InstrInfo::getLdStBaseOp(MI: *I);
769
770 // Which register is Rt and which is Rt2 depends on the offset order.
771 int64_t IOffsetInBytes =
772 AArch64InstrInfo::getLdStOffsetOp(MI: *I).getImm() * OffsetStride;
773 int64_t MIOffsetInBytes =
774 AArch64InstrInfo::getLdStOffsetOp(MI: *MergeMI).getImm() *
775 MergeMIOffsetStride;
776 // Select final offset based on the offset order.
777 int64_t OffsetImm;
778 if (IOffsetInBytes > MIOffsetInBytes)
779 OffsetImm = MIOffsetInBytes;
780 else
781 OffsetImm = IOffsetInBytes;
782
783 int NewOpcode = getMatchingWideOpcode(Opc);
784 bool FinalIsScaled = !TII->hasUnscaledLdStOffset(Opc: NewOpcode);
785
786 // Adjust final offset if the result opcode is a scaled store.
787 if (FinalIsScaled) {
788 int NewOffsetStride = FinalIsScaled ? TII->getMemScale(Opc: NewOpcode) : 1;
789 assert(((OffsetImm % NewOffsetStride) == 0) &&
790 "Offset should be a multiple of the store memory scale");
791 OffsetImm = OffsetImm / NewOffsetStride;
792 }
793
794 // Construct the new instruction.
795 DebugLoc DL = I->getDebugLoc();
796 MachineBasicBlock *MBB = I->getParent();
797 MachineInstrBuilder MIB;
798 MIB = BuildMI(BB&: *MBB, I: InsertionPoint, MIMD: DL, MCID: TII->get(Opcode: getMatchingWideOpcode(Opc)))
799 .addReg(RegNo: isNarrowStore(Opc) ? AArch64::WZR : AArch64::XZR)
800 .add(MO: BaseRegOp)
801 .addImm(Val: OffsetImm)
802 .cloneMergedMemRefs(OtherMIs: {&*I, &*MergeMI})
803 .setMIFlags(I->mergeFlagsWith(Other: *MergeMI));
804 (void)MIB;
805
806 LLVM_DEBUG(dbgs() << "Creating wider store. Replacing instructions:\n ");
807 LLVM_DEBUG(I->print(dbgs()));
808 LLVM_DEBUG(dbgs() << " ");
809 LLVM_DEBUG(MergeMI->print(dbgs()));
810 LLVM_DEBUG(dbgs() << " with instruction:\n ");
811 LLVM_DEBUG(((MachineInstr *)MIB)->print(dbgs()));
812 LLVM_DEBUG(dbgs() << "\n");
813
814 // Erase the old instructions.
815 I->eraseFromParent();
816 MergeMI->eraseFromParent();
817 return NextI;
818}
819
820// Apply Fn to all instructions between MI and the beginning of the block, until
821// a def for DefReg is reached. Returns true, iff Fn returns true for all
822// visited instructions. Stop after visiting Limit iterations.
823static bool forAllMIsUntilDef(MachineInstr &MI, MCPhysReg DefReg,
824 const TargetRegisterInfo *TRI, unsigned Limit,
825 std::function<bool(MachineInstr &, bool)> &Fn) {
826 auto MBB = MI.getParent();
827 for (MachineInstr &I :
828 instructionsWithoutDebug(It: MI.getReverseIterator(), End: MBB->instr_rend())) {
829 if (!Limit)
830 return false;
831 --Limit;
832
833 bool isDef = any_of(Range: I.operands(), P: [DefReg, TRI](MachineOperand &MOP) {
834 return MOP.isReg() && MOP.isDef() && !MOP.isDebug() && MOP.getReg() &&
835 TRI->regsOverlap(RegA: MOP.getReg(), RegB: DefReg);
836 });
837 if (!Fn(I, isDef))
838 return false;
839 if (isDef)
840 break;
841 }
842 return true;
843}
844
845static void updateDefinedRegisters(MachineInstr &MI, LiveRegUnits &Units,
846 const TargetRegisterInfo *TRI) {
847
848 for (const MachineOperand &MOP : phys_regs_and_masks(MI))
849 if (MOP.isReg() && MOP.isKill())
850 Units.removeReg(Reg: MOP.getReg());
851
852 for (const MachineOperand &MOP : phys_regs_and_masks(MI))
853 if (MOP.isReg() && !MOP.isKill())
854 Units.addReg(Reg: MOP.getReg());
855}
856
857MachineBasicBlock::iterator
858AArch64LoadStoreOpt::mergePairedInsns(MachineBasicBlock::iterator I,
859 MachineBasicBlock::iterator Paired,
860 const LdStPairFlags &Flags) {
861 MachineBasicBlock::iterator E = I->getParent()->end();
862 MachineBasicBlock::iterator NextI = next_nodbg(It: I, End: E);
863 // If NextI is the second of the two instructions to be merged, we need
864 // to skip one further. Either way we merge will invalidate the iterator,
865 // and we don't need to scan the new instruction, as it's a pairwise
866 // instruction, which we're not considering for further action anyway.
867 if (NextI == Paired)
868 NextI = next_nodbg(It: NextI, End: E);
869
870 int SExtIdx = Flags.getSExtIdx();
871 unsigned Opc =
872 SExtIdx == -1 ? I->getOpcode() : getMatchingNonSExtOpcode(Opc: I->getOpcode());
873 bool IsUnscaled = TII->hasUnscaledLdStOffset(Opc);
874 int OffsetStride = IsUnscaled ? TII->getMemScale(MI: *I) : 1;
875
876 bool MergeForward = Flags.getMergeForward();
877
878 std::optional<MCPhysReg> RenameReg = Flags.getRenameReg();
879 if (RenameReg) {
880 MCRegister RegToRename = getLdStRegOp(MI&: *I).getReg();
881 DefinedInBB.addReg(Reg: *RenameReg);
882
883 // Return the sub/super register for RenameReg, matching the size of
884 // OriginalReg.
885 auto GetMatchingSubReg =
886 [this, RenameReg](const TargetRegisterClass *C) -> MCPhysReg {
887 for (MCPhysReg SubOrSuper :
888 TRI->sub_and_superregs_inclusive(Reg: *RenameReg)) {
889 if (C->contains(Reg: SubOrSuper))
890 return SubOrSuper;
891 }
892 llvm_unreachable("Should have found matching sub or super register!");
893 };
894
895 std::function<bool(MachineInstr &, bool)> UpdateMIs =
896 [this, RegToRename, GetMatchingSubReg, MergeForward](MachineInstr &MI,
897 bool IsDef) {
898 if (IsDef) {
899 bool SeenDef = false;
900 for (unsigned OpIdx = 0; OpIdx < MI.getNumOperands(); ++OpIdx) {
901 MachineOperand &MOP = MI.getOperand(i: OpIdx);
902 // Rename the first explicit definition and all implicit
903 // definitions matching RegToRename.
904 if (MOP.isReg() && !MOP.isDebug() && MOP.getReg() &&
905 (!MergeForward || !SeenDef ||
906 (MOP.isDef() && MOP.isImplicit())) &&
907 TRI->regsOverlap(RegA: MOP.getReg(), RegB: RegToRename)) {
908 assert((MOP.isImplicit() ||
909 (MOP.isRenamable() && !MOP.isEarlyClobber())) &&
910 "Need renamable operands");
911 Register MatchingReg;
912 if (const TargetRegisterClass *RC =
913 MI.getRegClassConstraint(OpIdx, TII, TRI))
914 MatchingReg = GetMatchingSubReg(RC);
915 else {
916 if (!isRewritableImplicitDef(Opc: MI.getOpcode()))
917 continue;
918 MatchingReg = GetMatchingSubReg(
919 TRI->getMinimalPhysRegClass(Reg: MOP.getReg()));
920 }
921 MOP.setReg(MatchingReg);
922 SeenDef = true;
923 }
924 }
925 } else {
926 for (unsigned OpIdx = 0; OpIdx < MI.getNumOperands(); ++OpIdx) {
927 MachineOperand &MOP = MI.getOperand(i: OpIdx);
928 if (MOP.isReg() && !MOP.isDebug() && MOP.getReg() &&
929 TRI->regsOverlap(RegA: MOP.getReg(), RegB: RegToRename)) {
930 assert((MOP.isImplicit() ||
931 (MOP.isRenamable() && !MOP.isEarlyClobber())) &&
932 "Need renamable operands");
933 Register MatchingReg;
934 if (const TargetRegisterClass *RC =
935 MI.getRegClassConstraint(OpIdx, TII, TRI))
936 MatchingReg = GetMatchingSubReg(RC);
937 else
938 MatchingReg = GetMatchingSubReg(
939 TRI->getMinimalPhysRegClass(Reg: MOP.getReg()));
940 assert(MatchingReg != AArch64::NoRegister &&
941 "Cannot find matching regs for renaming");
942 MOP.setReg(MatchingReg);
943 }
944 }
945 }
946 LLVM_DEBUG(dbgs() << "Renamed " << MI);
947 return true;
948 };
949 forAllMIsUntilDef(MI&: MergeForward ? *I : *std::prev(x: Paired), DefReg: RegToRename, TRI,
950 UINT32_MAX, Fn&: UpdateMIs);
951
952#if !defined(NDEBUG)
953 // For forward merging store:
954 // Make sure the register used for renaming is not used between the
955 // paired instructions. That would trash the content before the new
956 // paired instruction.
957 MCPhysReg RegToCheck = *RenameReg;
958 // For backward merging load:
959 // Make sure the register being renamed is not used between the
960 // paired instructions. That would trash the content after the new
961 // paired instruction.
962 if (!MergeForward)
963 RegToCheck = RegToRename;
964 for (auto &MI :
965 iterator_range<MachineInstrBundleIterator<llvm::MachineInstr>>(
966 MergeForward ? std::next(I) : I,
967 MergeForward ? std::next(Paired) : Paired))
968 assert(all_of(MI.operands(),
969 [this, RegToCheck](const MachineOperand &MOP) {
970 return !MOP.isReg() || MOP.isDebug() || !MOP.getReg() ||
971 MOP.isUndef() ||
972 !TRI->regsOverlap(MOP.getReg(), RegToCheck);
973 }) &&
974 "Rename register used between paired instruction, trashing the "
975 "content");
976#endif
977 }
978
979 // Insert our new paired instruction after whichever of the paired
980 // instructions MergeForward indicates.
981 MachineBasicBlock::iterator InsertionPoint = MergeForward ? Paired : I;
982 // Also based on MergeForward is from where we copy the base register operand
983 // so we get the flags compatible with the input code.
984 const MachineOperand &BaseRegOp =
985 MergeForward ? AArch64InstrInfo::getLdStBaseOp(MI: *Paired)
986 : AArch64InstrInfo::getLdStBaseOp(MI: *I);
987
988 int Offset = AArch64InstrInfo::getLdStOffsetOp(MI: *I).getImm();
989 int PairedOffset = AArch64InstrInfo::getLdStOffsetOp(MI: *Paired).getImm();
990 bool PairedIsUnscaled = TII->hasUnscaledLdStOffset(Opc: Paired->getOpcode());
991 if (IsUnscaled != PairedIsUnscaled) {
992 // We're trying to pair instructions that differ in how they are scaled. If
993 // I is scaled then scale the offset of Paired accordingly. Otherwise, do
994 // the opposite (i.e., make Paired's offset unscaled).
995 int MemSize = TII->getMemScale(MI: *Paired);
996 if (PairedIsUnscaled) {
997 // If the unscaled offset isn't a multiple of the MemSize, we can't
998 // pair the operations together.
999 assert(!(PairedOffset % TII->getMemScale(*Paired)) &&
1000 "Offset should be a multiple of the stride!");
1001 PairedOffset /= MemSize;
1002 } else {
1003 PairedOffset *= MemSize;
1004 }
1005 }
1006
1007 // Which register is Rt and which is Rt2 depends on the offset order.
1008 // However, for pre load/stores the Rt should be the one of the pre
1009 // load/store.
1010 MachineInstr *RtMI, *Rt2MI;
1011 if (Offset == PairedOffset + OffsetStride &&
1012 !AArch64InstrInfo::isPreLdSt(MI: *I)) {
1013 RtMI = &*Paired;
1014 Rt2MI = &*I;
1015 // Here we swapped the assumption made for SExtIdx.
1016 // I.e., we turn ldp I, Paired into ldp Paired, I.
1017 // Update the index accordingly.
1018 if (SExtIdx != -1)
1019 SExtIdx = (SExtIdx + 1) % 2;
1020 } else {
1021 RtMI = &*I;
1022 Rt2MI = &*Paired;
1023 }
1024 int OffsetImm = AArch64InstrInfo::getLdStOffsetOp(MI: *RtMI).getImm();
1025 // Scale the immediate offset, if necessary.
1026 if (TII->hasUnscaledLdStOffset(Opc: RtMI->getOpcode())) {
1027 assert(!(OffsetImm % TII->getMemScale(*RtMI)) &&
1028 "Unscaled offset cannot be scaled.");
1029 OffsetImm /= TII->getMemScale(MI: *RtMI);
1030 }
1031
1032 // Construct the new instruction.
1033 MachineInstrBuilder MIB;
1034 DebugLoc DL = I->getDebugLoc();
1035 MachineBasicBlock *MBB = I->getParent();
1036 MachineOperand RegOp0 = getLdStRegOp(MI&: *RtMI);
1037 MachineOperand RegOp1 = getLdStRegOp(MI&: *Rt2MI);
1038 MachineOperand &PairedRegOp = RtMI == &*Paired ? RegOp0 : RegOp1;
1039 // Kill flags may become invalid when moving stores for pairing.
1040 if (RegOp0.isUse()) {
1041 if (!MergeForward) {
1042 // Clear kill flags on store if moving upwards. Example:
1043 // STRWui kill %w0, ...
1044 // USE %w1
1045 // STRWui kill %w1 ; need to clear kill flag when moving STRWui upwards
1046 // We are about to move the store of w1, so its kill flag may become
1047 // invalid; not the case for w0.
1048 // Since w1 is used between the stores, the kill flag on w1 is cleared
1049 // after merging.
1050 // STPWi kill %w0, %w1, ...
1051 // USE %w1
1052 for (auto It = std::next(x: I); It != Paired && PairedRegOp.isKill(); ++It)
1053 if (It->readsRegister(Reg: PairedRegOp.getReg(), TRI))
1054 PairedRegOp.setIsKill(false);
1055 } else {
1056 // Clear kill flags of the first stores register. Example:
1057 // STRWui %w1, ...
1058 // USE kill %w1 ; need to clear kill flag when moving STRWui downwards
1059 // STRW %w0
1060 Register Reg = getLdStRegOp(MI&: *I).getReg();
1061 for (MachineInstr &MI : make_range(x: std::next(x: I), y: Paired))
1062 MI.clearRegisterKills(Reg, RegInfo: TRI);
1063 }
1064 }
1065
1066 unsigned int MatchPairOpcode = getMatchingPairOpcode(Opc);
1067 MIB = BuildMI(BB&: *MBB, I: InsertionPoint, MIMD: DL, MCID: TII->get(Opcode: MatchPairOpcode));
1068
1069 // Adds the pre-index operand for pre-indexed ld/st pairs.
1070 if (AArch64InstrInfo::isPreLdSt(MI: *RtMI))
1071 MIB.addReg(RegNo: BaseRegOp.getReg(), flags: RegState::Define);
1072
1073 MIB.add(MO: RegOp0)
1074 .add(MO: RegOp1)
1075 .add(MO: BaseRegOp)
1076 .addImm(Val: OffsetImm)
1077 .cloneMergedMemRefs(OtherMIs: {&*I, &*Paired})
1078 .setMIFlags(I->mergeFlagsWith(Other: *Paired));
1079
1080 (void)MIB;
1081
1082 LLVM_DEBUG(
1083 dbgs() << "Creating pair load/store. Replacing instructions:\n ");
1084 LLVM_DEBUG(I->print(dbgs()));
1085 LLVM_DEBUG(dbgs() << " ");
1086 LLVM_DEBUG(Paired->print(dbgs()));
1087 LLVM_DEBUG(dbgs() << " with instruction:\n ");
1088 if (SExtIdx != -1) {
1089 // Generate the sign extension for the proper result of the ldp.
1090 // I.e., with X1, that would be:
1091 // %w1 = KILL %w1, implicit-def %x1
1092 // %x1 = SBFMXri killed %x1, 0, 31
1093 MachineOperand &DstMO = MIB->getOperand(i: SExtIdx);
1094 // Right now, DstMO has the extended register, since it comes from an
1095 // extended opcode.
1096 Register DstRegX = DstMO.getReg();
1097 // Get the W variant of that register.
1098 Register DstRegW = TRI->getSubReg(Reg: DstRegX, Idx: AArch64::sub_32);
1099 // Update the result of LDP to use the W instead of the X variant.
1100 DstMO.setReg(DstRegW);
1101 LLVM_DEBUG(((MachineInstr *)MIB)->print(dbgs()));
1102 LLVM_DEBUG(dbgs() << "\n");
1103 // Make the machine verifier happy by providing a definition for
1104 // the X register.
1105 // Insert this definition right after the generated LDP, i.e., before
1106 // InsertionPoint.
1107 MachineInstrBuilder MIBKill =
1108 BuildMI(BB&: *MBB, I: InsertionPoint, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::KILL), DestReg: DstRegW)
1109 .addReg(RegNo: DstRegW)
1110 .addReg(RegNo: DstRegX, flags: RegState::Define);
1111 MIBKill->getOperand(i: 2).setImplicit();
1112 // Create the sign extension.
1113 MachineInstrBuilder MIBSXTW =
1114 BuildMI(BB&: *MBB, I: InsertionPoint, MIMD: DL, MCID: TII->get(Opcode: AArch64::SBFMXri), DestReg: DstRegX)
1115 .addReg(RegNo: DstRegX)
1116 .addImm(Val: 0)
1117 .addImm(Val: 31);
1118 (void)MIBSXTW;
1119 LLVM_DEBUG(dbgs() << " Extend operand:\n ");
1120 LLVM_DEBUG(((MachineInstr *)MIBSXTW)->print(dbgs()));
1121 } else {
1122 LLVM_DEBUG(((MachineInstr *)MIB)->print(dbgs()));
1123 }
1124 LLVM_DEBUG(dbgs() << "\n");
1125
1126 if (MergeForward)
1127 for (const MachineOperand &MOP : phys_regs_and_masks(MI: *I))
1128 if (MOP.isReg() && MOP.isKill())
1129 DefinedInBB.addReg(Reg: MOP.getReg());
1130
1131 // Erase the old instructions.
1132 I->eraseFromParent();
1133 Paired->eraseFromParent();
1134
1135 return NextI;
1136}
1137
1138MachineBasicBlock::iterator
1139AArch64LoadStoreOpt::promoteLoadFromStore(MachineBasicBlock::iterator LoadI,
1140 MachineBasicBlock::iterator StoreI) {
1141 MachineBasicBlock::iterator NextI =
1142 next_nodbg(It: LoadI, End: LoadI->getParent()->end());
1143
1144 int LoadSize = TII->getMemScale(MI: *LoadI);
1145 int StoreSize = TII->getMemScale(MI: *StoreI);
1146 Register LdRt = getLdStRegOp(MI&: *LoadI).getReg();
1147 const MachineOperand &StMO = getLdStRegOp(MI&: *StoreI);
1148 Register StRt = getLdStRegOp(MI&: *StoreI).getReg();
1149 bool IsStoreXReg = TRI->getRegClass(i: AArch64::GPR64RegClassID)->contains(Reg: StRt);
1150
1151 assert((IsStoreXReg ||
1152 TRI->getRegClass(AArch64::GPR32RegClassID)->contains(StRt)) &&
1153 "Unexpected RegClass");
1154
1155 MachineInstr *BitExtMI;
1156 if (LoadSize == StoreSize && (LoadSize == 4 || LoadSize == 8)) {
1157 // Remove the load, if the destination register of the loads is the same
1158 // register for stored value.
1159 if (StRt == LdRt && LoadSize == 8) {
1160 for (MachineInstr &MI : make_range(x: StoreI->getIterator(),
1161 y: LoadI->getIterator())) {
1162 if (MI.killsRegister(Reg: StRt, TRI)) {
1163 MI.clearRegisterKills(Reg: StRt, RegInfo: TRI);
1164 break;
1165 }
1166 }
1167 LLVM_DEBUG(dbgs() << "Remove load instruction:\n ");
1168 LLVM_DEBUG(LoadI->print(dbgs()));
1169 LLVM_DEBUG(dbgs() << "\n");
1170 LoadI->eraseFromParent();
1171 return NextI;
1172 }
1173 // Replace the load with a mov if the load and store are in the same size.
1174 BitExtMI =
1175 BuildMI(BB&: *LoadI->getParent(), I: LoadI, MIMD: LoadI->getDebugLoc(),
1176 MCID: TII->get(Opcode: IsStoreXReg ? AArch64::ORRXrs : AArch64::ORRWrs), DestReg: LdRt)
1177 .addReg(RegNo: IsStoreXReg ? AArch64::XZR : AArch64::WZR)
1178 .add(MO: StMO)
1179 .addImm(Val: AArch64_AM::getShifterImm(ST: AArch64_AM::LSL, Imm: 0))
1180 .setMIFlags(LoadI->getFlags());
1181 } else {
1182 // FIXME: Currently we disable this transformation in big-endian targets as
1183 // performance and correctness are verified only in little-endian.
1184 if (!Subtarget->isLittleEndian())
1185 return NextI;
1186 bool IsUnscaled = TII->hasUnscaledLdStOffset(MI&: *LoadI);
1187 assert(IsUnscaled == TII->hasUnscaledLdStOffset(*StoreI) &&
1188 "Unsupported ld/st match");
1189 assert(LoadSize <= StoreSize && "Invalid load size");
1190 int UnscaledLdOffset =
1191 IsUnscaled
1192 ? AArch64InstrInfo::getLdStOffsetOp(MI: *LoadI).getImm()
1193 : AArch64InstrInfo::getLdStOffsetOp(MI: *LoadI).getImm() * LoadSize;
1194 int UnscaledStOffset =
1195 IsUnscaled
1196 ? AArch64InstrInfo::getLdStOffsetOp(MI: *StoreI).getImm()
1197 : AArch64InstrInfo::getLdStOffsetOp(MI: *StoreI).getImm() * StoreSize;
1198 int Width = LoadSize * 8;
1199 Register DestReg =
1200 IsStoreXReg ? Register(TRI->getMatchingSuperReg(
1201 Reg: LdRt, SubIdx: AArch64::sub_32, RC: &AArch64::GPR64RegClass))
1202 : LdRt;
1203
1204 assert((UnscaledLdOffset >= UnscaledStOffset &&
1205 (UnscaledLdOffset + LoadSize) <= UnscaledStOffset + StoreSize) &&
1206 "Invalid offset");
1207
1208 int Immr = 8 * (UnscaledLdOffset - UnscaledStOffset);
1209 int Imms = Immr + Width - 1;
1210 if (UnscaledLdOffset == UnscaledStOffset) {
1211 uint32_t AndMaskEncoded = ((IsStoreXReg ? 1 : 0) << 12) // N
1212 | ((Immr) << 6) // immr
1213 | ((Imms) << 0) // imms
1214 ;
1215
1216 BitExtMI =
1217 BuildMI(BB&: *LoadI->getParent(), I: LoadI, MIMD: LoadI->getDebugLoc(),
1218 MCID: TII->get(Opcode: IsStoreXReg ? AArch64::ANDXri : AArch64::ANDWri),
1219 DestReg)
1220 .add(MO: StMO)
1221 .addImm(Val: AndMaskEncoded)
1222 .setMIFlags(LoadI->getFlags());
1223 } else {
1224 BitExtMI =
1225 BuildMI(BB&: *LoadI->getParent(), I: LoadI, MIMD: LoadI->getDebugLoc(),
1226 MCID: TII->get(Opcode: IsStoreXReg ? AArch64::UBFMXri : AArch64::UBFMWri),
1227 DestReg)
1228 .add(MO: StMO)
1229 .addImm(Val: Immr)
1230 .addImm(Val: Imms)
1231 .setMIFlags(LoadI->getFlags());
1232 }
1233 }
1234
1235 // Clear kill flags between store and load.
1236 for (MachineInstr &MI : make_range(x: StoreI->getIterator(),
1237 y: BitExtMI->getIterator()))
1238 if (MI.killsRegister(Reg: StRt, TRI)) {
1239 MI.clearRegisterKills(Reg: StRt, RegInfo: TRI);
1240 break;
1241 }
1242
1243 LLVM_DEBUG(dbgs() << "Promoting load by replacing :\n ");
1244 LLVM_DEBUG(StoreI->print(dbgs()));
1245 LLVM_DEBUG(dbgs() << " ");
1246 LLVM_DEBUG(LoadI->print(dbgs()));
1247 LLVM_DEBUG(dbgs() << " with instructions:\n ");
1248 LLVM_DEBUG(StoreI->print(dbgs()));
1249 LLVM_DEBUG(dbgs() << " ");
1250 LLVM_DEBUG((BitExtMI)->print(dbgs()));
1251 LLVM_DEBUG(dbgs() << "\n");
1252
1253 // Erase the old instructions.
1254 LoadI->eraseFromParent();
1255 return NextI;
1256}
1257
1258static bool inBoundsForPair(bool IsUnscaled, int Offset, int OffsetStride) {
1259 // Convert the byte-offset used by unscaled into an "element" offset used
1260 // by the scaled pair load/store instructions.
1261 if (IsUnscaled) {
1262 // If the byte-offset isn't a multiple of the stride, there's no point
1263 // trying to match it.
1264 if (Offset % OffsetStride)
1265 return false;
1266 Offset /= OffsetStride;
1267 }
1268 return Offset <= 63 && Offset >= -64;
1269}
1270
1271// Do alignment, specialized to power of 2 and for signed ints,
1272// avoiding having to do a C-style cast from uint_64t to int when
1273// using alignTo from include/llvm/Support/MathExtras.h.
1274// FIXME: Move this function to include/MathExtras.h?
1275static int alignTo(int Num, int PowOf2) {
1276 return (Num + PowOf2 - 1) & ~(PowOf2 - 1);
1277}
1278
1279static bool mayAlias(MachineInstr &MIa,
1280 SmallVectorImpl<MachineInstr *> &MemInsns,
1281 AliasAnalysis *AA) {
1282 for (MachineInstr *MIb : MemInsns) {
1283 if (MIa.mayAlias(AA, Other: *MIb, /*UseTBAA*/ false)) {
1284 LLVM_DEBUG(dbgs() << "Aliasing with: "; MIb->dump());
1285 return true;
1286 }
1287 }
1288
1289 LLVM_DEBUG(dbgs() << "No aliases found\n");
1290 return false;
1291}
1292
1293bool AArch64LoadStoreOpt::findMatchingStore(
1294 MachineBasicBlock::iterator I, unsigned Limit,
1295 MachineBasicBlock::iterator &StoreI) {
1296 MachineBasicBlock::iterator B = I->getParent()->begin();
1297 MachineBasicBlock::iterator MBBI = I;
1298 MachineInstr &LoadMI = *I;
1299 Register BaseReg = AArch64InstrInfo::getLdStBaseOp(MI: LoadMI).getReg();
1300
1301 // If the load is the first instruction in the block, there's obviously
1302 // not any matching store.
1303 if (MBBI == B)
1304 return false;
1305
1306 // Track which register units have been modified and used between the first
1307 // insn and the second insn.
1308 ModifiedRegUnits.clear();
1309 UsedRegUnits.clear();
1310
1311 unsigned Count = 0;
1312 do {
1313 MBBI = prev_nodbg(It: MBBI, Begin: B);
1314 MachineInstr &MI = *MBBI;
1315
1316 // Don't count transient instructions towards the search limit since there
1317 // may be different numbers of them if e.g. debug information is present.
1318 if (!MI.isTransient())
1319 ++Count;
1320
1321 // If the load instruction reads directly from the address to which the
1322 // store instruction writes and the stored value is not modified, we can
1323 // promote the load. Since we do not handle stores with pre-/post-index,
1324 // it's unnecessary to check if BaseReg is modified by the store itself.
1325 // Also we can't handle stores without an immediate offset operand,
1326 // while the operand might be the address for a global variable.
1327 if (MI.mayStore() && isMatchingStore(LoadInst&: LoadMI, StoreInst&: MI) &&
1328 BaseReg == AArch64InstrInfo::getLdStBaseOp(MI).getReg() &&
1329 AArch64InstrInfo::getLdStOffsetOp(MI).isImm() &&
1330 isLdOffsetInRangeOfSt(LoadInst&: LoadMI, StoreInst&: MI, TII) &&
1331 ModifiedRegUnits.available(Reg: getLdStRegOp(MI).getReg())) {
1332 StoreI = MBBI;
1333 return true;
1334 }
1335
1336 if (MI.isCall())
1337 return false;
1338
1339 // Update modified / uses register units.
1340 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits, TRI);
1341
1342 // Otherwise, if the base register is modified, we have no match, so
1343 // return early.
1344 if (!ModifiedRegUnits.available(Reg: BaseReg))
1345 return false;
1346
1347 // If we encounter a store aliased with the load, return early.
1348 if (MI.mayStore() && LoadMI.mayAlias(AA, Other: MI, /*UseTBAA*/ false))
1349 return false;
1350 } while (MBBI != B && Count < Limit);
1351 return false;
1352}
1353
1354static bool needsWinCFI(const MachineFunction *MF) {
1355 return MF->getTarget().getMCAsmInfo()->usesWindowsCFI() &&
1356 MF->getFunction().needsUnwindTableEntry();
1357}
1358
1359// Returns true if FirstMI and MI are candidates for merging or pairing.
1360// Otherwise, returns false.
1361static bool areCandidatesToMergeOrPair(MachineInstr &FirstMI, MachineInstr &MI,
1362 LdStPairFlags &Flags,
1363 const AArch64InstrInfo *TII) {
1364 // If this is volatile or if pairing is suppressed, not a candidate.
1365 if (MI.hasOrderedMemoryRef() || TII->isLdStPairSuppressed(MI))
1366 return false;
1367
1368 // We should have already checked FirstMI for pair suppression and volatility.
1369 assert(!FirstMI.hasOrderedMemoryRef() &&
1370 !TII->isLdStPairSuppressed(FirstMI) &&
1371 "FirstMI shouldn't get here if either of these checks are true.");
1372
1373 if (needsWinCFI(MF: MI.getMF()) && (MI.getFlag(Flag: MachineInstr::FrameSetup) ||
1374 MI.getFlag(Flag: MachineInstr::FrameDestroy)))
1375 return false;
1376
1377 unsigned OpcA = FirstMI.getOpcode();
1378 unsigned OpcB = MI.getOpcode();
1379
1380 // Opcodes match: If the opcodes are pre ld/st there is nothing more to check.
1381 if (OpcA == OpcB)
1382 return !AArch64InstrInfo::isPreLdSt(MI: FirstMI);
1383
1384 // Two pre ld/st of different opcodes cannot be merged either
1385 if (AArch64InstrInfo::isPreLdSt(MI: FirstMI) && AArch64InstrInfo::isPreLdSt(MI))
1386 return false;
1387
1388 // Try to match a sign-extended load/store with a zero-extended load/store.
1389 bool IsValidLdStrOpc, PairIsValidLdStrOpc;
1390 unsigned NonSExtOpc = getMatchingNonSExtOpcode(Opc: OpcA, IsValidLdStrOpc: &IsValidLdStrOpc);
1391 assert(IsValidLdStrOpc &&
1392 "Given Opc should be a Load or Store with an immediate");
1393 // OpcA will be the first instruction in the pair.
1394 if (NonSExtOpc == getMatchingNonSExtOpcode(Opc: OpcB, IsValidLdStrOpc: &PairIsValidLdStrOpc)) {
1395 Flags.setSExtIdx(NonSExtOpc == (unsigned)OpcA ? 1 : 0);
1396 return true;
1397 }
1398
1399 // If the second instruction isn't even a mergable/pairable load/store, bail
1400 // out.
1401 if (!PairIsValidLdStrOpc)
1402 return false;
1403
1404 // FIXME: We don't support merging narrow stores with mixed scaled/unscaled
1405 // offsets.
1406 if (isNarrowStore(Opc: OpcA) || isNarrowStore(Opc: OpcB))
1407 return false;
1408
1409 // The STR<S,D,Q,W,X>pre - STR<S,D,Q,W,X>ui and
1410 // LDR<S,D,Q,W,X,SW>pre-LDR<S,D,Q,W,X,SW>ui
1411 // are candidate pairs that can be merged.
1412 if (isPreLdStPairCandidate(FirstMI, MI))
1413 return true;
1414
1415 // Try to match an unscaled load/store with a scaled load/store.
1416 return TII->hasUnscaledLdStOffset(Opc: OpcA) != TII->hasUnscaledLdStOffset(Opc: OpcB) &&
1417 getMatchingPairOpcode(Opc: OpcA) == getMatchingPairOpcode(Opc: OpcB);
1418
1419 // FIXME: Can we also match a mixed sext/zext unscaled/scaled pair?
1420}
1421
1422static bool canRenameMOP(const MachineOperand &MOP,
1423 const TargetRegisterInfo *TRI) {
1424 if (MOP.isReg()) {
1425 auto *RegClass = TRI->getMinimalPhysRegClass(Reg: MOP.getReg());
1426 // Renaming registers with multiple disjunct sub-registers (e.g. the
1427 // result of a LD3) means that all sub-registers are renamed, potentially
1428 // impacting other instructions we did not check. Bail out.
1429 // Note that this relies on the structure of the AArch64 register file. In
1430 // particular, a subregister cannot be written without overwriting the
1431 // whole register.
1432 if (RegClass->HasDisjunctSubRegs) {
1433 LLVM_DEBUG(
1434 dbgs()
1435 << " Cannot rename operands with multiple disjunct subregisters ("
1436 << MOP << ")\n");
1437 return false;
1438 }
1439
1440 // We cannot rename arbitrary implicit-defs, the specific rule to rewrite
1441 // them must be known. For example, in ORRWrs the implicit-def
1442 // corresponds to the result register.
1443 if (MOP.isImplicit() && MOP.isDef()) {
1444 if (!isRewritableImplicitDef(Opc: MOP.getParent()->getOpcode()))
1445 return false;
1446 return TRI->isSuperOrSubRegisterEq(
1447 RegA: MOP.getParent()->getOperand(i: 0).getReg(), RegB: MOP.getReg());
1448 }
1449 }
1450 return MOP.isImplicit() ||
1451 (MOP.isRenamable() && !MOP.isEarlyClobber() && !MOP.isTied());
1452}
1453
1454static bool
1455canRenameUpToDef(MachineInstr &FirstMI, LiveRegUnits &UsedInBetween,
1456 SmallPtrSetImpl<const TargetRegisterClass *> &RequiredClasses,
1457 const TargetRegisterInfo *TRI) {
1458 if (!FirstMI.mayStore())
1459 return false;
1460
1461 // Check if we can find an unused register which we can use to rename
1462 // the register used by the first load/store.
1463
1464 auto RegToRename = getLdStRegOp(MI&: FirstMI).getReg();
1465 // For now, we only rename if the store operand gets killed at the store.
1466 if (!getLdStRegOp(MI&: FirstMI).isKill() &&
1467 !any_of(Range: FirstMI.operands(),
1468 P: [TRI, RegToRename](const MachineOperand &MOP) {
1469 return MOP.isReg() && !MOP.isDebug() && MOP.getReg() &&
1470 MOP.isImplicit() && MOP.isKill() &&
1471 TRI->regsOverlap(RegA: RegToRename, RegB: MOP.getReg());
1472 })) {
1473 LLVM_DEBUG(dbgs() << " Operand not killed at " << FirstMI);
1474 return false;
1475 }
1476
1477 bool FoundDef = false;
1478
1479 // For each instruction between FirstMI and the previous def for RegToRename,
1480 // we
1481 // * check if we can rename RegToRename in this instruction
1482 // * collect the registers used and required register classes for RegToRename.
1483 std::function<bool(MachineInstr &, bool)> CheckMIs = [&](MachineInstr &MI,
1484 bool IsDef) {
1485 LLVM_DEBUG(dbgs() << "Checking " << MI);
1486 // Currently we do not try to rename across frame-setup instructions.
1487 if (MI.getFlag(Flag: MachineInstr::FrameSetup)) {
1488 LLVM_DEBUG(dbgs() << " Cannot rename framesetup instructions "
1489 << "currently\n");
1490 return false;
1491 }
1492
1493 UsedInBetween.accumulate(MI);
1494
1495 // For a definition, check that we can rename the definition and exit the
1496 // loop.
1497 FoundDef = IsDef;
1498
1499 // For defs, check if we can rename the first def of RegToRename.
1500 if (FoundDef) {
1501 // For some pseudo instructions, we might not generate code in the end
1502 // (e.g. KILL) and we would end up without a correct def for the rename
1503 // register.
1504 // TODO: This might be overly conservative and we could handle those cases
1505 // in multiple ways:
1506 // 1. Insert an extra copy, to materialize the def.
1507 // 2. Skip pseudo-defs until we find an non-pseudo def.
1508 if (MI.isPseudo()) {
1509 LLVM_DEBUG(dbgs() << " Cannot rename pseudo/bundle instruction\n");
1510 return false;
1511 }
1512
1513 for (auto &MOP : MI.operands()) {
1514 if (!MOP.isReg() || !MOP.isDef() || MOP.isDebug() || !MOP.getReg() ||
1515 !TRI->regsOverlap(RegA: MOP.getReg(), RegB: RegToRename))
1516 continue;
1517 if (!canRenameMOP(MOP, TRI)) {
1518 LLVM_DEBUG(dbgs() << " Cannot rename " << MOP << " in " << MI);
1519 return false;
1520 }
1521 RequiredClasses.insert(Ptr: TRI->getMinimalPhysRegClass(Reg: MOP.getReg()));
1522 }
1523 return true;
1524 } else {
1525 for (auto &MOP : MI.operands()) {
1526 if (!MOP.isReg() || MOP.isDebug() || !MOP.getReg() ||
1527 !TRI->regsOverlap(RegA: MOP.getReg(), RegB: RegToRename))
1528 continue;
1529
1530 if (!canRenameMOP(MOP, TRI)) {
1531 LLVM_DEBUG(dbgs() << " Cannot rename " << MOP << " in " << MI);
1532 return false;
1533 }
1534 RequiredClasses.insert(Ptr: TRI->getMinimalPhysRegClass(Reg: MOP.getReg()));
1535 }
1536 }
1537 return true;
1538 };
1539
1540 if (!forAllMIsUntilDef(MI&: FirstMI, DefReg: RegToRename, TRI, Limit: LdStLimit, Fn&: CheckMIs))
1541 return false;
1542
1543 if (!FoundDef) {
1544 LLVM_DEBUG(dbgs() << " Did not find definition for register in BB\n");
1545 return false;
1546 }
1547 return true;
1548}
1549
1550// We want to merge the second load into the first by rewriting the usages of
1551// the same reg between first (incl.) and second (excl.). We don't need to care
1552// about any insns before FirstLoad or after SecondLoad.
1553// 1. The second load writes new value into the same reg.
1554// - The renaming is impossible to impact later use of the reg.
1555// - The second load always trash the value written by the first load which
1556// means the reg must be killed before the second load.
1557// 2. The first load must be a def for the same reg so we don't need to look
1558// into anything before it.
1559static bool canRenameUntilSecondLoad(
1560 MachineInstr &FirstLoad, MachineInstr &SecondLoad,
1561 LiveRegUnits &UsedInBetween,
1562 SmallPtrSetImpl<const TargetRegisterClass *> &RequiredClasses,
1563 const TargetRegisterInfo *TRI) {
1564 if (FirstLoad.isPseudo())
1565 return false;
1566
1567 UsedInBetween.accumulate(MI: FirstLoad);
1568 auto RegToRename = getLdStRegOp(MI&: FirstLoad).getReg();
1569 bool Success = std::all_of(
1570 first: FirstLoad.getIterator(), last: SecondLoad.getIterator(),
1571 pred: [&](MachineInstr &MI) {
1572 LLVM_DEBUG(dbgs() << "Checking " << MI);
1573 // Currently we do not try to rename across frame-setup instructions.
1574 if (MI.getFlag(Flag: MachineInstr::FrameSetup)) {
1575 LLVM_DEBUG(dbgs() << " Cannot rename framesetup instructions "
1576 << "currently\n");
1577 return false;
1578 }
1579
1580 for (auto &MOP : MI.operands()) {
1581 if (!MOP.isReg() || MOP.isDebug() || !MOP.getReg() ||
1582 !TRI->regsOverlap(RegA: MOP.getReg(), RegB: RegToRename))
1583 continue;
1584 if (!canRenameMOP(MOP, TRI)) {
1585 LLVM_DEBUG(dbgs() << " Cannot rename " << MOP << " in " << MI);
1586 return false;
1587 }
1588 RequiredClasses.insert(Ptr: TRI->getMinimalPhysRegClass(Reg: MOP.getReg()));
1589 }
1590
1591 return true;
1592 });
1593 return Success;
1594}
1595
1596// Check if we can find a physical register for renaming \p Reg. This register
1597// must:
1598// * not be defined already in \p DefinedInBB; DefinedInBB must contain all
1599// defined registers up to the point where the renamed register will be used,
1600// * not used in \p UsedInBetween; UsedInBetween must contain all accessed
1601// registers in the range the rename register will be used,
1602// * is available in all used register classes (checked using RequiredClasses).
1603static std::optional<MCPhysReg> tryToFindRegisterToRename(
1604 const MachineFunction &MF, Register Reg, LiveRegUnits &DefinedInBB,
1605 LiveRegUnits &UsedInBetween,
1606 SmallPtrSetImpl<const TargetRegisterClass *> &RequiredClasses,
1607 const TargetRegisterInfo *TRI) {
1608 const MachineRegisterInfo &RegInfo = MF.getRegInfo();
1609
1610 // Checks if any sub- or super-register of PR is callee saved.
1611 auto AnySubOrSuperRegCalleePreserved = [&MF, TRI](MCPhysReg PR) {
1612 return any_of(Range: TRI->sub_and_superregs_inclusive(Reg: PR),
1613 P: [&MF, TRI](MCPhysReg SubOrSuper) {
1614 return TRI->isCalleeSavedPhysReg(PhysReg: SubOrSuper, MF);
1615 });
1616 };
1617
1618 // Check if PR or one of its sub- or super-registers can be used for all
1619 // required register classes.
1620 auto CanBeUsedForAllClasses = [&RequiredClasses, TRI](MCPhysReg PR) {
1621 return all_of(Range&: RequiredClasses, P: [PR, TRI](const TargetRegisterClass *C) {
1622 return any_of(
1623 Range: TRI->sub_and_superregs_inclusive(Reg: PR),
1624 P: [C](MCPhysReg SubOrSuper) { return C->contains(Reg: SubOrSuper); });
1625 });
1626 };
1627
1628 auto *RegClass = TRI->getMinimalPhysRegClass(Reg);
1629 for (const MCPhysReg &PR : *RegClass) {
1630 if (DefinedInBB.available(Reg: PR) && UsedInBetween.available(Reg: PR) &&
1631 !RegInfo.isReserved(PhysReg: PR) && !AnySubOrSuperRegCalleePreserved(PR) &&
1632 CanBeUsedForAllClasses(PR)) {
1633 DefinedInBB.addReg(Reg: PR);
1634 LLVM_DEBUG(dbgs() << "Found rename register " << printReg(PR, TRI)
1635 << "\n");
1636 return {PR};
1637 }
1638 }
1639 LLVM_DEBUG(dbgs() << "No rename register found from "
1640 << TRI->getRegClassName(RegClass) << "\n");
1641 return std::nullopt;
1642}
1643
1644// For store pairs: returns a register from FirstMI to the beginning of the
1645// block that can be renamed.
1646// For load pairs: returns a register from FirstMI to MI that can be renamed.
1647static std::optional<MCPhysReg> findRenameRegForSameLdStRegPair(
1648 std::optional<bool> MaybeCanRename, MachineInstr &FirstMI, MachineInstr &MI,
1649 Register Reg, LiveRegUnits &DefinedInBB, LiveRegUnits &UsedInBetween,
1650 SmallPtrSetImpl<const TargetRegisterClass *> &RequiredClasses,
1651 const TargetRegisterInfo *TRI) {
1652 std::optional<MCPhysReg> RenameReg;
1653 if (!DebugCounter::shouldExecute(CounterName: RegRenamingCounter))
1654 return RenameReg;
1655
1656 auto *RegClass = TRI->getMinimalPhysRegClass(Reg: getLdStRegOp(MI&: FirstMI).getReg());
1657 MachineFunction &MF = *FirstMI.getParent()->getParent();
1658 if (!RegClass || !MF.getRegInfo().tracksLiveness())
1659 return RenameReg;
1660
1661 const bool IsLoad = FirstMI.mayLoad();
1662
1663 if (!MaybeCanRename) {
1664 if (IsLoad)
1665 MaybeCanRename = {canRenameUntilSecondLoad(FirstLoad&: FirstMI, SecondLoad&: MI, UsedInBetween,
1666 RequiredClasses, TRI)};
1667 else
1668 MaybeCanRename = {
1669 canRenameUpToDef(FirstMI, UsedInBetween, RequiredClasses, TRI)};
1670 }
1671
1672 if (*MaybeCanRename) {
1673 RenameReg = tryToFindRegisterToRename(MF, Reg, DefinedInBB, UsedInBetween,
1674 RequiredClasses, TRI);
1675 }
1676 return RenameReg;
1677}
1678
1679/// Scan the instructions looking for a load/store that can be combined with the
1680/// current instruction into a wider equivalent or a load/store pair.
1681MachineBasicBlock::iterator
1682AArch64LoadStoreOpt::findMatchingInsn(MachineBasicBlock::iterator I,
1683 LdStPairFlags &Flags, unsigned Limit,
1684 bool FindNarrowMerge) {
1685 MachineBasicBlock::iterator E = I->getParent()->end();
1686 MachineBasicBlock::iterator MBBI = I;
1687 MachineBasicBlock::iterator MBBIWithRenameReg;
1688 MachineInstr &FirstMI = *I;
1689 MBBI = next_nodbg(It: MBBI, End: E);
1690
1691 bool MayLoad = FirstMI.mayLoad();
1692 bool IsUnscaled = TII->hasUnscaledLdStOffset(MI&: FirstMI);
1693 Register Reg = getLdStRegOp(MI&: FirstMI).getReg();
1694 Register BaseReg = AArch64InstrInfo::getLdStBaseOp(MI: FirstMI).getReg();
1695 int Offset = AArch64InstrInfo::getLdStOffsetOp(MI: FirstMI).getImm();
1696 int OffsetStride = IsUnscaled ? TII->getMemScale(MI: FirstMI) : 1;
1697 bool IsPromotableZeroStore = isPromotableZeroStoreInst(MI&: FirstMI);
1698
1699 std::optional<bool> MaybeCanRename;
1700 if (!EnableRenaming)
1701 MaybeCanRename = {false};
1702
1703 SmallPtrSet<const TargetRegisterClass *, 5> RequiredClasses;
1704 LiveRegUnits UsedInBetween;
1705 UsedInBetween.init(TRI: *TRI);
1706
1707 Flags.clearRenameReg();
1708
1709 // Track which register units have been modified and used between the first
1710 // insn (inclusive) and the second insn.
1711 ModifiedRegUnits.clear();
1712 UsedRegUnits.clear();
1713
1714 // Remember any instructions that read/write memory between FirstMI and MI.
1715 SmallVector<MachineInstr *, 4> MemInsns;
1716
1717 LLVM_DEBUG(dbgs() << "Find match for: "; FirstMI.dump());
1718 for (unsigned Count = 0; MBBI != E && Count < Limit;
1719 MBBI = next_nodbg(It: MBBI, End: E)) {
1720 MachineInstr &MI = *MBBI;
1721 LLVM_DEBUG(dbgs() << "Analysing 2nd insn: "; MI.dump());
1722
1723 UsedInBetween.accumulate(MI);
1724
1725 // Don't count transient instructions towards the search limit since there
1726 // may be different numbers of them if e.g. debug information is present.
1727 if (!MI.isTransient())
1728 ++Count;
1729
1730 Flags.setSExtIdx(-1);
1731 if (areCandidatesToMergeOrPair(FirstMI, MI, Flags, TII) &&
1732 AArch64InstrInfo::getLdStOffsetOp(MI).isImm()) {
1733 assert(MI.mayLoadOrStore() && "Expected memory operation.");
1734 // If we've found another instruction with the same opcode, check to see
1735 // if the base and offset are compatible with our starting instruction.
1736 // These instructions all have scaled immediate operands, so we just
1737 // check for +1/-1. Make sure to check the new instruction offset is
1738 // actually an immediate and not a symbolic reference destined for
1739 // a relocation.
1740 Register MIBaseReg = AArch64InstrInfo::getLdStBaseOp(MI).getReg();
1741 int MIOffset = AArch64InstrInfo::getLdStOffsetOp(MI).getImm();
1742 bool MIIsUnscaled = TII->hasUnscaledLdStOffset(MI);
1743 if (IsUnscaled != MIIsUnscaled) {
1744 // We're trying to pair instructions that differ in how they are scaled.
1745 // If FirstMI is scaled then scale the offset of MI accordingly.
1746 // Otherwise, do the opposite (i.e., make MI's offset unscaled).
1747 int MemSize = TII->getMemScale(MI);
1748 if (MIIsUnscaled) {
1749 // If the unscaled offset isn't a multiple of the MemSize, we can't
1750 // pair the operations together: bail and keep looking.
1751 if (MIOffset % MemSize) {
1752 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits,
1753 UsedRegUnits, TRI);
1754 MemInsns.push_back(Elt: &MI);
1755 continue;
1756 }
1757 MIOffset /= MemSize;
1758 } else {
1759 MIOffset *= MemSize;
1760 }
1761 }
1762
1763 bool IsPreLdSt = isPreLdStPairCandidate(FirstMI, MI);
1764
1765 if (BaseReg == MIBaseReg) {
1766 // If the offset of the second ld/st is not equal to the size of the
1767 // destination register it can’t be paired with a pre-index ld/st
1768 // pair. Additionally if the base reg is used or modified the operations
1769 // can't be paired: bail and keep looking.
1770 if (IsPreLdSt) {
1771 bool IsOutOfBounds = MIOffset != TII->getMemScale(MI);
1772 bool IsBaseRegUsed = !UsedRegUnits.available(
1773 Reg: AArch64InstrInfo::getLdStBaseOp(MI).getReg());
1774 bool IsBaseRegModified = !ModifiedRegUnits.available(
1775 Reg: AArch64InstrInfo::getLdStBaseOp(MI).getReg());
1776 // If the stored value and the address of the second instruction is
1777 // the same, it needs to be using the updated register and therefore
1778 // it must not be folded.
1779 bool IsMIRegTheSame =
1780 TRI->regsOverlap(RegA: getLdStRegOp(MI).getReg(),
1781 RegB: AArch64InstrInfo::getLdStBaseOp(MI).getReg());
1782 if (IsOutOfBounds || IsBaseRegUsed || IsBaseRegModified ||
1783 IsMIRegTheSame) {
1784 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits,
1785 UsedRegUnits, TRI);
1786 MemInsns.push_back(Elt: &MI);
1787 continue;
1788 }
1789 } else {
1790 if ((Offset != MIOffset + OffsetStride) &&
1791 (Offset + OffsetStride != MIOffset)) {
1792 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits,
1793 UsedRegUnits, TRI);
1794 MemInsns.push_back(Elt: &MI);
1795 continue;
1796 }
1797 }
1798
1799 int MinOffset = Offset < MIOffset ? Offset : MIOffset;
1800 if (FindNarrowMerge) {
1801 // If the alignment requirements of the scaled wide load/store
1802 // instruction can't express the offset of the scaled narrow input,
1803 // bail and keep looking. For promotable zero stores, allow only when
1804 // the stored value is the same (i.e., WZR).
1805 if ((!IsUnscaled && alignTo(Num: MinOffset, PowOf2: 2) != MinOffset) ||
1806 (IsPromotableZeroStore && Reg != getLdStRegOp(MI).getReg())) {
1807 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits,
1808 UsedRegUnits, TRI);
1809 MemInsns.push_back(Elt: &MI);
1810 continue;
1811 }
1812 } else {
1813 // Pairwise instructions have a 7-bit signed offset field. Single
1814 // insns have a 12-bit unsigned offset field. If the resultant
1815 // immediate offset of merging these instructions is out of range for
1816 // a pairwise instruction, bail and keep looking.
1817 if (!inBoundsForPair(IsUnscaled, Offset: MinOffset, OffsetStride)) {
1818 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits,
1819 UsedRegUnits, TRI);
1820 MemInsns.push_back(Elt: &MI);
1821 LLVM_DEBUG(dbgs() << "Offset doesn't fit in immediate, "
1822 << "keep looking.\n");
1823 continue;
1824 }
1825 // If the alignment requirements of the paired (scaled) instruction
1826 // can't express the offset of the unscaled input, bail and keep
1827 // looking.
1828 if (IsUnscaled && (alignTo(Num: MinOffset, PowOf2: OffsetStride) != MinOffset)) {
1829 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits,
1830 UsedRegUnits, TRI);
1831 MemInsns.push_back(Elt: &MI);
1832 LLVM_DEBUG(dbgs()
1833 << "Offset doesn't fit due to alignment requirements, "
1834 << "keep looking.\n");
1835 continue;
1836 }
1837 }
1838
1839 // If the BaseReg has been modified, then we cannot do the optimization.
1840 // For example, in the following pattern
1841 // ldr x1 [x2]
1842 // ldr x2 [x3]
1843 // ldr x4 [x2, #8],
1844 // the first and third ldr cannot be converted to ldp x1, x4, [x2]
1845 if (!ModifiedRegUnits.available(Reg: BaseReg))
1846 return E;
1847
1848 const bool SameLoadReg = MayLoad && TRI->isSuperOrSubRegisterEq(
1849 RegA: Reg, RegB: getLdStRegOp(MI).getReg());
1850
1851 // If the Rt of the second instruction (destination register of the
1852 // load) was not modified or used between the two instructions and none
1853 // of the instructions between the second and first alias with the
1854 // second, we can combine the second into the first.
1855 bool RtNotModified =
1856 ModifiedRegUnits.available(Reg: getLdStRegOp(MI).getReg());
1857 bool RtNotUsed = !(MI.mayLoad() && !SameLoadReg &&
1858 !UsedRegUnits.available(Reg: getLdStRegOp(MI).getReg()));
1859
1860 LLVM_DEBUG(dbgs() << "Checking, can combine 2nd into 1st insn:\n"
1861 << "Reg '" << getLdStRegOp(MI) << "' not modified: "
1862 << (RtNotModified ? "true" : "false") << "\n"
1863 << "Reg '" << getLdStRegOp(MI) << "' not used: "
1864 << (RtNotUsed ? "true" : "false") << "\n");
1865
1866 if (RtNotModified && RtNotUsed && !mayAlias(MIa&: MI, MemInsns, AA)) {
1867 // For pairs loading into the same reg, try to find a renaming
1868 // opportunity to allow the renaming of Reg between FirstMI and MI
1869 // and combine MI into FirstMI; otherwise bail and keep looking.
1870 if (SameLoadReg) {
1871 std::optional<MCPhysReg> RenameReg =
1872 findRenameRegForSameLdStRegPair(MaybeCanRename, FirstMI, MI,
1873 Reg, DefinedInBB, UsedInBetween,
1874 RequiredClasses, TRI);
1875 if (!RenameReg) {
1876 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits,
1877 UsedRegUnits, TRI);
1878 MemInsns.push_back(Elt: &MI);
1879 LLVM_DEBUG(dbgs() << "Can't find reg for renaming, "
1880 << "keep looking.\n");
1881 continue;
1882 }
1883 Flags.setRenameReg(*RenameReg);
1884 }
1885
1886 Flags.setMergeForward(false);
1887 if (!SameLoadReg)
1888 Flags.clearRenameReg();
1889 return MBBI;
1890 }
1891
1892 // Likewise, if the Rt of the first instruction is not modified or used
1893 // between the two instructions and none of the instructions between the
1894 // first and the second alias with the first, we can combine the first
1895 // into the second.
1896 RtNotModified = !(
1897 MayLoad && !UsedRegUnits.available(Reg: getLdStRegOp(MI&: FirstMI).getReg()));
1898
1899 LLVM_DEBUG(dbgs() << "Checking, can combine 1st into 2nd insn:\n"
1900 << "Reg '" << getLdStRegOp(FirstMI)
1901 << "' not modified: "
1902 << (RtNotModified ? "true" : "false") << "\n");
1903
1904 if (RtNotModified && !mayAlias(MIa&: FirstMI, MemInsns, AA)) {
1905 if (ModifiedRegUnits.available(Reg: getLdStRegOp(MI&: FirstMI).getReg())) {
1906 Flags.setMergeForward(true);
1907 Flags.clearRenameReg();
1908 return MBBI;
1909 }
1910
1911 std::optional<MCPhysReg> RenameReg = findRenameRegForSameLdStRegPair(
1912 MaybeCanRename, FirstMI, MI, Reg, DefinedInBB, UsedInBetween,
1913 RequiredClasses, TRI);
1914 if (RenameReg) {
1915 Flags.setMergeForward(true);
1916 Flags.setRenameReg(*RenameReg);
1917 MBBIWithRenameReg = MBBI;
1918 }
1919 }
1920 LLVM_DEBUG(dbgs() << "Unable to combine these instructions due to "
1921 << "interference in between, keep looking.\n");
1922 }
1923 }
1924
1925 if (Flags.getRenameReg())
1926 return MBBIWithRenameReg;
1927
1928 // If the instruction wasn't a matching load or store. Stop searching if we
1929 // encounter a call instruction that might modify memory.
1930 if (MI.isCall()) {
1931 LLVM_DEBUG(dbgs() << "Found a call, stop looking.\n");
1932 return E;
1933 }
1934
1935 // Update modified / uses register units.
1936 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits, TRI);
1937
1938 // Otherwise, if the base register is modified, we have no match, so
1939 // return early.
1940 if (!ModifiedRegUnits.available(Reg: BaseReg)) {
1941 LLVM_DEBUG(dbgs() << "Base reg is modified, stop looking.\n");
1942 return E;
1943 }
1944
1945 // Update list of instructions that read/write memory.
1946 if (MI.mayLoadOrStore())
1947 MemInsns.push_back(Elt: &MI);
1948 }
1949 return E;
1950}
1951
1952static MachineBasicBlock::iterator
1953maybeMoveCFI(MachineInstr &MI, MachineBasicBlock::iterator MaybeCFI) {
1954 auto End = MI.getParent()->end();
1955 if (MaybeCFI == End ||
1956 MaybeCFI->getOpcode() != TargetOpcode::CFI_INSTRUCTION ||
1957 !(MI.getFlag(Flag: MachineInstr::FrameSetup) ||
1958 MI.getFlag(Flag: MachineInstr::FrameDestroy)) ||
1959 AArch64InstrInfo::getLdStBaseOp(MI).getReg() != AArch64::SP)
1960 return End;
1961
1962 const MachineFunction &MF = *MI.getParent()->getParent();
1963 unsigned CFIIndex = MaybeCFI->getOperand(i: 0).getCFIIndex();
1964 const MCCFIInstruction &CFI = MF.getFrameInstructions()[CFIIndex];
1965 switch (CFI.getOperation()) {
1966 case MCCFIInstruction::OpDefCfa:
1967 case MCCFIInstruction::OpDefCfaOffset:
1968 return MaybeCFI;
1969 default:
1970 return End;
1971 }
1972}
1973
1974MachineBasicBlock::iterator
1975AArch64LoadStoreOpt::mergeUpdateInsn(MachineBasicBlock::iterator I,
1976 MachineBasicBlock::iterator Update,
1977 bool IsPreIdx) {
1978 assert((Update->getOpcode() == AArch64::ADDXri ||
1979 Update->getOpcode() == AArch64::SUBXri) &&
1980 "Unexpected base register update instruction to merge!");
1981 MachineBasicBlock::iterator E = I->getParent()->end();
1982 MachineBasicBlock::iterator NextI = next_nodbg(It: I, End: E);
1983
1984 // If updating the SP and the following instruction is CFA offset related CFI
1985 // instruction move it after the merged instruction.
1986 MachineBasicBlock::iterator CFI =
1987 IsPreIdx ? maybeMoveCFI(MI&: *Update, MaybeCFI: next_nodbg(It: Update, End: E)) : E;
1988
1989 // Return the instruction following the merged instruction, which is
1990 // the instruction following our unmerged load. Unless that's the add/sub
1991 // instruction we're merging, in which case it's the one after that.
1992 if (NextI == Update)
1993 NextI = next_nodbg(It: NextI, End: E);
1994
1995 int Value = Update->getOperand(i: 2).getImm();
1996 assert(AArch64_AM::getShiftValue(Update->getOperand(3).getImm()) == 0 &&
1997 "Can't merge 1 << 12 offset into pre-/post-indexed load / store");
1998 if (Update->getOpcode() == AArch64::SUBXri)
1999 Value = -Value;
2000
2001 unsigned NewOpc = IsPreIdx ? getPreIndexedOpcode(Opc: I->getOpcode())
2002 : getPostIndexedOpcode(Opc: I->getOpcode());
2003 MachineInstrBuilder MIB;
2004 int Scale, MinOffset, MaxOffset;
2005 getPrePostIndexedMemOpInfo(MI: *I, Scale, MinOffset, MaxOffset);
2006 if (!AArch64InstrInfo::isPairedLdSt(MI: *I)) {
2007 // Non-paired instruction.
2008 MIB = BuildMI(BB&: *I->getParent(), I, MIMD: I->getDebugLoc(), MCID: TII->get(Opcode: NewOpc))
2009 .add(MO: getLdStRegOp(MI&: *Update))
2010 .add(MO: getLdStRegOp(MI&: *I))
2011 .add(MO: AArch64InstrInfo::getLdStBaseOp(MI: *I))
2012 .addImm(Val: Value / Scale)
2013 .setMemRefs(I->memoperands())
2014 .setMIFlags(I->mergeFlagsWith(Other: *Update));
2015 } else {
2016 // Paired instruction.
2017 MIB = BuildMI(BB&: *I->getParent(), I, MIMD: I->getDebugLoc(), MCID: TII->get(Opcode: NewOpc))
2018 .add(MO: getLdStRegOp(MI&: *Update))
2019 .add(MO: getLdStRegOp(MI&: *I, PairedRegOp: 0))
2020 .add(MO: getLdStRegOp(MI&: *I, PairedRegOp: 1))
2021 .add(MO: AArch64InstrInfo::getLdStBaseOp(MI: *I))
2022 .addImm(Val: Value / Scale)
2023 .setMemRefs(I->memoperands())
2024 .setMIFlags(I->mergeFlagsWith(Other: *Update));
2025 }
2026 if (CFI != E) {
2027 MachineBasicBlock *MBB = I->getParent();
2028 MBB->splice(Where: std::next(x: MIB.getInstr()->getIterator()), Other: MBB, From: CFI);
2029 }
2030
2031 if (IsPreIdx) {
2032 ++NumPreFolded;
2033 LLVM_DEBUG(dbgs() << "Creating pre-indexed load/store.");
2034 } else {
2035 ++NumPostFolded;
2036 LLVM_DEBUG(dbgs() << "Creating post-indexed load/store.");
2037 }
2038 LLVM_DEBUG(dbgs() << " Replacing instructions:\n ");
2039 LLVM_DEBUG(I->print(dbgs()));
2040 LLVM_DEBUG(dbgs() << " ");
2041 LLVM_DEBUG(Update->print(dbgs()));
2042 LLVM_DEBUG(dbgs() << " with instruction:\n ");
2043 LLVM_DEBUG(((MachineInstr *)MIB)->print(dbgs()));
2044 LLVM_DEBUG(dbgs() << "\n");
2045
2046 // Erase the old instructions for the block.
2047 I->eraseFromParent();
2048 Update->eraseFromParent();
2049
2050 return NextI;
2051}
2052
2053bool AArch64LoadStoreOpt::isMatchingUpdateInsn(MachineInstr &MemMI,
2054 MachineInstr &MI,
2055 unsigned BaseReg, int Offset) {
2056 switch (MI.getOpcode()) {
2057 default:
2058 break;
2059 case AArch64::SUBXri:
2060 case AArch64::ADDXri:
2061 // Make sure it's a vanilla immediate operand, not a relocation or
2062 // anything else we can't handle.
2063 if (!MI.getOperand(i: 2).isImm())
2064 break;
2065 // Watch out for 1 << 12 shifted value.
2066 if (AArch64_AM::getShiftValue(Imm: MI.getOperand(i: 3).getImm()))
2067 break;
2068
2069 // The update instruction source and destination register must be the
2070 // same as the load/store base register.
2071 if (MI.getOperand(i: 0).getReg() != BaseReg ||
2072 MI.getOperand(i: 1).getReg() != BaseReg)
2073 break;
2074
2075 int UpdateOffset = MI.getOperand(i: 2).getImm();
2076 if (MI.getOpcode() == AArch64::SUBXri)
2077 UpdateOffset = -UpdateOffset;
2078
2079 // The immediate must be a multiple of the scaling factor of the pre/post
2080 // indexed instruction.
2081 int Scale, MinOffset, MaxOffset;
2082 getPrePostIndexedMemOpInfo(MI: MemMI, Scale, MinOffset, MaxOffset);
2083 if (UpdateOffset % Scale != 0)
2084 break;
2085
2086 // Scaled offset must fit in the instruction immediate.
2087 int ScaledOffset = UpdateOffset / Scale;
2088 if (ScaledOffset > MaxOffset || ScaledOffset < MinOffset)
2089 break;
2090
2091 // If we have a non-zero Offset, we check that it matches the amount
2092 // we're adding to the register.
2093 if (!Offset || Offset == UpdateOffset)
2094 return true;
2095 break;
2096 }
2097 return false;
2098}
2099
2100MachineBasicBlock::iterator AArch64LoadStoreOpt::findMatchingUpdateInsnForward(
2101 MachineBasicBlock::iterator I, int UnscaledOffset, unsigned Limit) {
2102 MachineBasicBlock::iterator E = I->getParent()->end();
2103 MachineInstr &MemMI = *I;
2104 MachineBasicBlock::iterator MBBI = I;
2105
2106 Register BaseReg = AArch64InstrInfo::getLdStBaseOp(MI: MemMI).getReg();
2107 int MIUnscaledOffset = AArch64InstrInfo::getLdStOffsetOp(MI: MemMI).getImm() *
2108 TII->getMemScale(MI: MemMI);
2109
2110 // Scan forward looking for post-index opportunities. Updating instructions
2111 // can't be formed if the memory instruction doesn't have the offset we're
2112 // looking for.
2113 if (MIUnscaledOffset != UnscaledOffset)
2114 return E;
2115
2116 // If the base register overlaps a source/destination register, we can't
2117 // merge the update. This does not apply to tag store instructions which
2118 // ignore the address part of the source register.
2119 // This does not apply to STGPi as well, which does not have unpredictable
2120 // behavior in this case unlike normal stores, and always performs writeback
2121 // after reading the source register value.
2122 if (!isTagStore(MI: MemMI) && MemMI.getOpcode() != AArch64::STGPi) {
2123 bool IsPairedInsn = AArch64InstrInfo::isPairedLdSt(MI: MemMI);
2124 for (unsigned i = 0, e = IsPairedInsn ? 2 : 1; i != e; ++i) {
2125 Register DestReg = getLdStRegOp(MI&: MemMI, PairedRegOp: i).getReg();
2126 if (DestReg == BaseReg || TRI->isSubRegister(RegA: BaseReg, RegB: DestReg))
2127 return E;
2128 }
2129 }
2130
2131 // Track which register units have been modified and used between the first
2132 // insn (inclusive) and the second insn.
2133 ModifiedRegUnits.clear();
2134 UsedRegUnits.clear();
2135 MBBI = next_nodbg(It: MBBI, End: E);
2136
2137 // We can't post-increment the stack pointer if any instruction between
2138 // the memory access (I) and the increment (MBBI) can access the memory
2139 // region defined by [SP, MBBI].
2140 const bool BaseRegSP = BaseReg == AArch64::SP;
2141 if (BaseRegSP && needsWinCFI(MF: I->getMF())) {
2142 // FIXME: For now, we always block the optimization over SP in windows
2143 // targets as it requires to adjust the unwind/debug info, messing up
2144 // the unwind info can actually cause a miscompile.
2145 return E;
2146 }
2147
2148 for (unsigned Count = 0; MBBI != E && Count < Limit;
2149 MBBI = next_nodbg(It: MBBI, End: E)) {
2150 MachineInstr &MI = *MBBI;
2151
2152 // Don't count transient instructions towards the search limit since there
2153 // may be different numbers of them if e.g. debug information is present.
2154 if (!MI.isTransient())
2155 ++Count;
2156
2157 // If we found a match, return it.
2158 if (isMatchingUpdateInsn(MemMI&: *I, MI, BaseReg, Offset: UnscaledOffset))
2159 return MBBI;
2160
2161 // Update the status of what the instruction clobbered and used.
2162 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits, TRI);
2163
2164 // Otherwise, if the base register is used or modified, we have no match, so
2165 // return early.
2166 // If we are optimizing SP, do not allow instructions that may load or store
2167 // in between the load and the optimized value update.
2168 if (!ModifiedRegUnits.available(Reg: BaseReg) ||
2169 !UsedRegUnits.available(Reg: BaseReg) ||
2170 (BaseRegSP && MBBI->mayLoadOrStore()))
2171 return E;
2172 }
2173 return E;
2174}
2175
2176MachineBasicBlock::iterator AArch64LoadStoreOpt::findMatchingUpdateInsnBackward(
2177 MachineBasicBlock::iterator I, unsigned Limit) {
2178 MachineBasicBlock::iterator B = I->getParent()->begin();
2179 MachineBasicBlock::iterator E = I->getParent()->end();
2180 MachineInstr &MemMI = *I;
2181 MachineBasicBlock::iterator MBBI = I;
2182 MachineFunction &MF = *MemMI.getMF();
2183
2184 Register BaseReg = AArch64InstrInfo::getLdStBaseOp(MI: MemMI).getReg();
2185 int Offset = AArch64InstrInfo::getLdStOffsetOp(MI: MemMI).getImm();
2186
2187 // If the load/store is the first instruction in the block, there's obviously
2188 // not any matching update. Ditto if the memory offset isn't zero.
2189 if (MBBI == B || Offset != 0)
2190 return E;
2191 // If the base register overlaps a destination register, we can't
2192 // merge the update.
2193 if (!isTagStore(MI: MemMI)) {
2194 bool IsPairedInsn = AArch64InstrInfo::isPairedLdSt(MI: MemMI);
2195 for (unsigned i = 0, e = IsPairedInsn ? 2 : 1; i != e; ++i) {
2196 Register DestReg = getLdStRegOp(MI&: MemMI, PairedRegOp: i).getReg();
2197 if (DestReg == BaseReg || TRI->isSubRegister(RegA: BaseReg, RegB: DestReg))
2198 return E;
2199 }
2200 }
2201
2202 const bool BaseRegSP = BaseReg == AArch64::SP;
2203 if (BaseRegSP && needsWinCFI(MF: I->getMF())) {
2204 // FIXME: For now, we always block the optimization over SP in windows
2205 // targets as it requires to adjust the unwind/debug info, messing up
2206 // the unwind info can actually cause a miscompile.
2207 return E;
2208 }
2209
2210 const AArch64Subtarget &Subtarget = MF.getSubtarget<AArch64Subtarget>();
2211 unsigned RedZoneSize =
2212 Subtarget.getTargetLowering()->getRedZoneSize(F: MF.getFunction());
2213
2214 // Track which register units have been modified and used between the first
2215 // insn (inclusive) and the second insn.
2216 ModifiedRegUnits.clear();
2217 UsedRegUnits.clear();
2218 unsigned Count = 0;
2219 bool MemAcessBeforeSPPreInc = false;
2220 do {
2221 MBBI = prev_nodbg(It: MBBI, Begin: B);
2222 MachineInstr &MI = *MBBI;
2223
2224 // Don't count transient instructions towards the search limit since there
2225 // may be different numbers of them if e.g. debug information is present.
2226 if (!MI.isTransient())
2227 ++Count;
2228
2229 // If we found a match, return it.
2230 if (isMatchingUpdateInsn(MemMI&: *I, MI, BaseReg, Offset)) {
2231 // Check that the update value is within our red zone limit (which may be
2232 // zero).
2233 if (MemAcessBeforeSPPreInc && MBBI->getOperand(i: 2).getImm() > RedZoneSize)
2234 return E;
2235 return MBBI;
2236 }
2237
2238 // Update the status of what the instruction clobbered and used.
2239 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits, TRI);
2240
2241 // Otherwise, if the base register is used or modified, we have no match, so
2242 // return early.
2243 if (!ModifiedRegUnits.available(Reg: BaseReg) ||
2244 !UsedRegUnits.available(Reg: BaseReg))
2245 return E;
2246 // Keep track if we have a memory access before an SP pre-increment, in this
2247 // case we need to validate later that the update amount respects the red
2248 // zone.
2249 if (BaseRegSP && MBBI->mayLoadOrStore())
2250 MemAcessBeforeSPPreInc = true;
2251 } while (MBBI != B && Count < Limit);
2252 return E;
2253}
2254
2255bool AArch64LoadStoreOpt::tryToPromoteLoadFromStore(
2256 MachineBasicBlock::iterator &MBBI) {
2257 MachineInstr &MI = *MBBI;
2258 // If this is a volatile load, don't mess with it.
2259 if (MI.hasOrderedMemoryRef())
2260 return false;
2261
2262 if (needsWinCFI(MF: MI.getMF()) && MI.getFlag(Flag: MachineInstr::FrameDestroy))
2263 return false;
2264
2265 // Make sure this is a reg+imm.
2266 // FIXME: It is possible to extend it to handle reg+reg cases.
2267 if (!AArch64InstrInfo::getLdStOffsetOp(MI).isImm())
2268 return false;
2269
2270 // Look backward up to LdStLimit instructions.
2271 MachineBasicBlock::iterator StoreI;
2272 if (findMatchingStore(I: MBBI, Limit: LdStLimit, StoreI)) {
2273 ++NumLoadsFromStoresPromoted;
2274 // Promote the load. Keeping the iterator straight is a
2275 // pain, so we let the merge routine tell us what the next instruction
2276 // is after it's done mucking about.
2277 MBBI = promoteLoadFromStore(LoadI: MBBI, StoreI);
2278 return true;
2279 }
2280 return false;
2281}
2282
2283// Merge adjacent zero stores into a wider store.
2284bool AArch64LoadStoreOpt::tryToMergeZeroStInst(
2285 MachineBasicBlock::iterator &MBBI) {
2286 assert(isPromotableZeroStoreInst(*MBBI) && "Expected narrow store.");
2287 MachineInstr &MI = *MBBI;
2288 MachineBasicBlock::iterator E = MI.getParent()->end();
2289
2290 if (!TII->isCandidateToMergeOrPair(MI))
2291 return false;
2292
2293 // Look ahead up to LdStLimit instructions for a mergable instruction.
2294 LdStPairFlags Flags;
2295 MachineBasicBlock::iterator MergeMI =
2296 findMatchingInsn(I: MBBI, Flags, Limit: LdStLimit, /* FindNarrowMerge = */ true);
2297 if (MergeMI != E) {
2298 ++NumZeroStoresPromoted;
2299
2300 // Keeping the iterator straight is a pain, so we let the merge routine tell
2301 // us what the next instruction is after it's done mucking about.
2302 MBBI = mergeNarrowZeroStores(I: MBBI, MergeMI, Flags);
2303 return true;
2304 }
2305 return false;
2306}
2307
2308// Find loads and stores that can be merged into a single load or store pair
2309// instruction.
2310bool AArch64LoadStoreOpt::tryToPairLdStInst(MachineBasicBlock::iterator &MBBI) {
2311 MachineInstr &MI = *MBBI;
2312 MachineBasicBlock::iterator E = MI.getParent()->end();
2313
2314 if (!TII->isCandidateToMergeOrPair(MI))
2315 return false;
2316
2317 // If disable-ldp feature is opted, do not emit ldp.
2318 if (MI.mayLoad() && Subtarget->hasDisableLdp())
2319 return false;
2320
2321 // If disable-stp feature is opted, do not emit stp.
2322 if (MI.mayStore() && Subtarget->hasDisableStp())
2323 return false;
2324
2325 // Early exit if the offset is not possible to match. (6 bits of positive
2326 // range, plus allow an extra one in case we find a later insn that matches
2327 // with Offset-1)
2328 bool IsUnscaled = TII->hasUnscaledLdStOffset(MI);
2329 int Offset = AArch64InstrInfo::getLdStOffsetOp(MI).getImm();
2330 int OffsetStride = IsUnscaled ? TII->getMemScale(MI) : 1;
2331 // Allow one more for offset.
2332 if (Offset > 0)
2333 Offset -= OffsetStride;
2334 if (!inBoundsForPair(IsUnscaled, Offset, OffsetStride))
2335 return false;
2336
2337 // Look ahead up to LdStLimit instructions for a pairable instruction.
2338 LdStPairFlags Flags;
2339 MachineBasicBlock::iterator Paired =
2340 findMatchingInsn(I: MBBI, Flags, Limit: LdStLimit, /* FindNarrowMerge = */ false);
2341 if (Paired != E) {
2342 // Keeping the iterator straight is a pain, so we let the merge routine tell
2343 // us what the next instruction is after it's done mucking about.
2344 auto Prev = std::prev(x: MBBI);
2345
2346 // Fetch the memoperand of the load/store that is a candidate for
2347 // combination.
2348 MachineMemOperand *MemOp =
2349 MI.memoperands_empty() ? nullptr : MI.memoperands().front();
2350
2351 // If a load/store arrives and ldp/stp-aligned-only feature is opted, check
2352 // that the alignment of the source pointer is at least double the alignment
2353 // of the type.
2354 if ((MI.mayLoad() && Subtarget->hasLdpAlignedOnly()) ||
2355 (MI.mayStore() && Subtarget->hasStpAlignedOnly())) {
2356 // If there is no size/align information, cancel the transformation.
2357 if (!MemOp || !MemOp->getMemoryType().isValid()) {
2358 NumFailedAlignmentCheck++;
2359 return false;
2360 }
2361
2362 // Get the needed alignments to check them if
2363 // ldp-aligned-only/stp-aligned-only features are opted.
2364 uint64_t MemAlignment = MemOp->getAlign().value();
2365 uint64_t TypeAlignment = Align(MemOp->getSize().getValue()).value();
2366
2367 if (MemAlignment < 2 * TypeAlignment) {
2368 NumFailedAlignmentCheck++;
2369 return false;
2370 }
2371 }
2372
2373 ++NumPairCreated;
2374 if (TII->hasUnscaledLdStOffset(MI))
2375 ++NumUnscaledPairCreated;
2376
2377 MBBI = mergePairedInsns(I: MBBI, Paired, Flags);
2378 // Collect liveness info for instructions between Prev and the new position
2379 // MBBI.
2380 for (auto I = std::next(x: Prev); I != MBBI; I++)
2381 updateDefinedRegisters(MI&: *I, Units&: DefinedInBB, TRI);
2382
2383 return true;
2384 }
2385 return false;
2386}
2387
2388bool AArch64LoadStoreOpt::tryToMergeLdStUpdate
2389 (MachineBasicBlock::iterator &MBBI) {
2390 MachineInstr &MI = *MBBI;
2391 MachineBasicBlock::iterator E = MI.getParent()->end();
2392 MachineBasicBlock::iterator Update;
2393
2394 // Look forward to try to form a post-index instruction. For example,
2395 // ldr x0, [x20]
2396 // add x20, x20, #32
2397 // merged into:
2398 // ldr x0, [x20], #32
2399 Update = findMatchingUpdateInsnForward(I: MBBI, UnscaledOffset: 0, Limit: UpdateLimit);
2400 if (Update != E) {
2401 // Merge the update into the ld/st.
2402 MBBI = mergeUpdateInsn(I: MBBI, Update, /*IsPreIdx=*/false);
2403 return true;
2404 }
2405
2406 // Don't know how to handle unscaled pre/post-index versions below, so bail.
2407 if (TII->hasUnscaledLdStOffset(Opc: MI.getOpcode()))
2408 return false;
2409
2410 // Look back to try to find a pre-index instruction. For example,
2411 // add x0, x0, #8
2412 // ldr x1, [x0]
2413 // merged into:
2414 // ldr x1, [x0, #8]!
2415 Update = findMatchingUpdateInsnBackward(I: MBBI, Limit: UpdateLimit);
2416 if (Update != E) {
2417 // Merge the update into the ld/st.
2418 MBBI = mergeUpdateInsn(I: MBBI, Update, /*IsPreIdx=*/true);
2419 return true;
2420 }
2421
2422 // The immediate in the load/store is scaled by the size of the memory
2423 // operation. The immediate in the add we're looking for,
2424 // however, is not, so adjust here.
2425 int UnscaledOffset =
2426 AArch64InstrInfo::getLdStOffsetOp(MI).getImm() * TII->getMemScale(MI);
2427
2428 // Look forward to try to find a pre-index instruction. For example,
2429 // ldr x1, [x0, #64]
2430 // add x0, x0, #64
2431 // merged into:
2432 // ldr x1, [x0, #64]!
2433 Update = findMatchingUpdateInsnForward(I: MBBI, UnscaledOffset, Limit: UpdateLimit);
2434 if (Update != E) {
2435 // Merge the update into the ld/st.
2436 MBBI = mergeUpdateInsn(I: MBBI, Update, /*IsPreIdx=*/true);
2437 return true;
2438 }
2439
2440 return false;
2441}
2442
2443bool AArch64LoadStoreOpt::optimizeBlock(MachineBasicBlock &MBB,
2444 bool EnableNarrowZeroStOpt) {
2445
2446 bool Modified = false;
2447 // Four tranformations to do here:
2448 // 1) Find loads that directly read from stores and promote them by
2449 // replacing with mov instructions. If the store is wider than the load,
2450 // the load will be replaced with a bitfield extract.
2451 // e.g.,
2452 // str w1, [x0, #4]
2453 // ldrh w2, [x0, #6]
2454 // ; becomes
2455 // str w1, [x0, #4]
2456 // lsr w2, w1, #16
2457 for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
2458 MBBI != E;) {
2459 if (isPromotableLoadFromStore(MI&: *MBBI) && tryToPromoteLoadFromStore(MBBI))
2460 Modified = true;
2461 else
2462 ++MBBI;
2463 }
2464 // 2) Merge adjacent zero stores into a wider store.
2465 // e.g.,
2466 // strh wzr, [x0]
2467 // strh wzr, [x0, #2]
2468 // ; becomes
2469 // str wzr, [x0]
2470 // e.g.,
2471 // str wzr, [x0]
2472 // str wzr, [x0, #4]
2473 // ; becomes
2474 // str xzr, [x0]
2475 if (EnableNarrowZeroStOpt)
2476 for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
2477 MBBI != E;) {
2478 if (isPromotableZeroStoreInst(MI&: *MBBI) && tryToMergeZeroStInst(MBBI))
2479 Modified = true;
2480 else
2481 ++MBBI;
2482 }
2483 // 3) Find loads and stores that can be merged into a single load or store
2484 // pair instruction.
2485 // e.g.,
2486 // ldr x0, [x2]
2487 // ldr x1, [x2, #8]
2488 // ; becomes
2489 // ldp x0, x1, [x2]
2490
2491 if (MBB.getParent()->getRegInfo().tracksLiveness()) {
2492 DefinedInBB.clear();
2493 DefinedInBB.addLiveIns(MBB);
2494 }
2495
2496 for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
2497 MBBI != E;) {
2498 // Track currently live registers up to this point, to help with
2499 // searching for a rename register on demand.
2500 updateDefinedRegisters(MI&: *MBBI, Units&: DefinedInBB, TRI);
2501 if (TII->isPairableLdStInst(MI: *MBBI) && tryToPairLdStInst(MBBI))
2502 Modified = true;
2503 else
2504 ++MBBI;
2505 }
2506 // 4) Find base register updates that can be merged into the load or store
2507 // as a base-reg writeback.
2508 // e.g.,
2509 // ldr x0, [x2]
2510 // add x2, x2, #4
2511 // ; becomes
2512 // ldr x0, [x2], #4
2513 for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
2514 MBBI != E;) {
2515 if (isMergeableLdStUpdate(MI&: *MBBI) && tryToMergeLdStUpdate(MBBI))
2516 Modified = true;
2517 else
2518 ++MBBI;
2519 }
2520
2521 return Modified;
2522}
2523
2524bool AArch64LoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
2525 if (skipFunction(F: Fn.getFunction()))
2526 return false;
2527
2528 Subtarget = &Fn.getSubtarget<AArch64Subtarget>();
2529 TII = static_cast<const AArch64InstrInfo *>(Subtarget->getInstrInfo());
2530 TRI = Subtarget->getRegisterInfo();
2531 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
2532
2533 // Resize the modified and used register unit trackers. We do this once
2534 // per function and then clear the register units each time we optimize a load
2535 // or store.
2536 ModifiedRegUnits.init(TRI: *TRI);
2537 UsedRegUnits.init(TRI: *TRI);
2538 DefinedInBB.init(TRI: *TRI);
2539
2540 bool Modified = false;
2541 bool enableNarrowZeroStOpt = !Subtarget->requiresStrictAlign();
2542 for (auto &MBB : Fn) {
2543 auto M = optimizeBlock(MBB, EnableNarrowZeroStOpt: enableNarrowZeroStOpt);
2544 Modified |= M;
2545 }
2546
2547 return Modified;
2548}
2549
2550// FIXME: Do we need/want a pre-alloc pass like ARM has to try to keep loads and
2551// stores near one another? Note: The pre-RA instruction scheduler already has
2552// hooks to try and schedule pairable loads/stores together to improve pairing
2553// opportunities. Thus, pre-RA pairing pass may not be worth the effort.
2554
2555// FIXME: When pairing store instructions it's very possible for this pass to
2556// hoist a store with a KILL marker above another use (without a KILL marker).
2557// The resulting IR is invalid, but nothing uses the KILL markers after this
2558// pass, so it's never caused a problem in practice.
2559
2560/// createAArch64LoadStoreOptimizationPass - returns an instance of the
2561/// load / store optimization pass.
2562FunctionPass *llvm::createAArch64LoadStoreOptimizationPass() {
2563 return new AArch64LoadStoreOpt();
2564}
2565