1 //===- ARMLoadStoreOptimizer.cpp - ARM 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 /// \file This file contains a pass that performs load / store related peephole
10 /// optimizations. This pass should be run after register allocation.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "ARM.h"
15 #include "ARMBaseInstrInfo.h"
16 #include "ARMBaseRegisterInfo.h"
17 #include "ARMISelLowering.h"
18 #include "ARMMachineFunctionInfo.h"
19 #include "ARMSubtarget.h"
20 #include "MCTargetDesc/ARMAddressingModes.h"
21 #include "MCTargetDesc/ARMBaseInfo.h"
22 #include "Utils/ARMBaseInfo.h"
23 #include "llvm/ADT/ArrayRef.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/DenseSet.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/ADT/iterator_range.h"
32 #include "llvm/Analysis/AliasAnalysis.h"
33 #include "llvm/CodeGen/LivePhysRegs.h"
34 #include "llvm/CodeGen/MachineBasicBlock.h"
35 #include "llvm/CodeGen/MachineDominators.h"
36 #include "llvm/CodeGen/MachineFunction.h"
37 #include "llvm/CodeGen/MachineFunctionPass.h"
38 #include "llvm/CodeGen/MachineInstr.h"
39 #include "llvm/CodeGen/MachineInstrBuilder.h"
40 #include "llvm/CodeGen/MachineMemOperand.h"
41 #include "llvm/CodeGen/MachineOperand.h"
42 #include "llvm/CodeGen/MachineRegisterInfo.h"
43 #include "llvm/CodeGen/RegisterClassInfo.h"
44 #include "llvm/CodeGen/TargetFrameLowering.h"
45 #include "llvm/CodeGen/TargetInstrInfo.h"
46 #include "llvm/CodeGen/TargetLowering.h"
47 #include "llvm/CodeGen/TargetRegisterInfo.h"
48 #include "llvm/CodeGen/TargetSubtargetInfo.h"
49 #include "llvm/IR/DataLayout.h"
50 #include "llvm/IR/DebugLoc.h"
51 #include "llvm/IR/DerivedTypes.h"
52 #include "llvm/IR/Function.h"
53 #include "llvm/IR/Type.h"
54 #include "llvm/InitializePasses.h"
55 #include "llvm/MC/MCInstrDesc.h"
56 #include "llvm/Pass.h"
57 #include "llvm/Support/Allocator.h"
58 #include "llvm/Support/CommandLine.h"
59 #include "llvm/Support/Debug.h"
60 #include "llvm/Support/ErrorHandling.h"
61 #include "llvm/Support/raw_ostream.h"
62 #include <algorithm>
63 #include <cassert>
64 #include <cstddef>
65 #include <cstdlib>
66 #include <iterator>
67 #include <limits>
68 #include <utility>
69
70 using namespace llvm;
71
72 #define DEBUG_TYPE "arm-ldst-opt"
73
74 STATISTIC(NumLDMGened , "Number of ldm instructions generated");
75 STATISTIC(NumSTMGened , "Number of stm instructions generated");
76 STATISTIC(NumVLDMGened, "Number of vldm instructions generated");
77 STATISTIC(NumVSTMGened, "Number of vstm instructions generated");
78 STATISTIC(NumLdStMoved, "Number of load / store instructions moved");
79 STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation");
80 STATISTIC(NumSTRDFormed,"Number of strd created before allocation");
81 STATISTIC(NumLDRD2LDM, "Number of ldrd instructions turned back into ldm");
82 STATISTIC(NumSTRD2STM, "Number of strd instructions turned back into stm");
83 STATISTIC(NumLDRD2LDR, "Number of ldrd instructions turned back into ldr's");
84 STATISTIC(NumSTRD2STR, "Number of strd instructions turned back into str's");
85
86 /// This switch disables formation of double/multi instructions that could
87 /// potentially lead to (new) alignment traps even with CCR.UNALIGN_TRP
88 /// disabled. This can be used to create libraries that are robust even when
89 /// users provoke undefined behaviour by supplying misaligned pointers.
90 /// \see mayCombineMisaligned()
91 static cl::opt<bool>
92 AssumeMisalignedLoadStores("arm-assume-misaligned-load-store", cl::Hidden,
93 cl::init(false), cl::desc("Be more conservative in ARM load/store opt"));
94
95 #define ARM_LOAD_STORE_OPT_NAME "ARM load / store optimization pass"
96
97 namespace {
98
99 /// Post- register allocation pass the combine load / store instructions to
100 /// form ldm / stm instructions.
101 struct ARMLoadStoreOpt : public MachineFunctionPass {
102 static char ID;
103
104 const MachineFunction *MF;
105 const TargetInstrInfo *TII;
106 const TargetRegisterInfo *TRI;
107 const ARMSubtarget *STI;
108 const TargetLowering *TL;
109 ARMFunctionInfo *AFI;
110 LivePhysRegs LiveRegs;
111 RegisterClassInfo RegClassInfo;
112 MachineBasicBlock::const_iterator LiveRegPos;
113 bool LiveRegsValid;
114 bool RegClassInfoValid;
115 bool isThumb1, isThumb2;
116
ARMLoadStoreOpt__anon7c5dfe910111::ARMLoadStoreOpt117 ARMLoadStoreOpt() : MachineFunctionPass(ID) {}
118
119 bool runOnMachineFunction(MachineFunction &Fn) override;
120
getRequiredProperties__anon7c5dfe910111::ARMLoadStoreOpt121 MachineFunctionProperties getRequiredProperties() const override {
122 return MachineFunctionProperties().set(
123 MachineFunctionProperties::Property::NoVRegs);
124 }
125
getPassName__anon7c5dfe910111::ARMLoadStoreOpt126 StringRef getPassName() const override { return ARM_LOAD_STORE_OPT_NAME; }
127
128 private:
129 /// A set of load/store MachineInstrs with same base register sorted by
130 /// offset.
131 struct MemOpQueueEntry {
132 MachineInstr *MI;
133 int Offset; ///< Load/Store offset.
134 unsigned Position; ///< Position as counted from end of basic block.
135
MemOpQueueEntry__anon7c5dfe910111::ARMLoadStoreOpt::MemOpQueueEntry136 MemOpQueueEntry(MachineInstr &MI, int Offset, unsigned Position)
137 : MI(&MI), Offset(Offset), Position(Position) {}
138 };
139 using MemOpQueue = SmallVector<MemOpQueueEntry, 8>;
140
141 /// A set of MachineInstrs that fulfill (nearly all) conditions to get
142 /// merged into a LDM/STM.
143 struct MergeCandidate {
144 /// List of instructions ordered by load/store offset.
145 SmallVector<MachineInstr*, 4> Instrs;
146
147 /// Index in Instrs of the instruction being latest in the schedule.
148 unsigned LatestMIIdx;
149
150 /// Index in Instrs of the instruction being earliest in the schedule.
151 unsigned EarliestMIIdx;
152
153 /// Index into the basic block where the merged instruction will be
154 /// inserted. (See MemOpQueueEntry.Position)
155 unsigned InsertPos;
156
157 /// Whether the instructions can be merged into a ldm/stm instruction.
158 bool CanMergeToLSMulti;
159
160 /// Whether the instructions can be merged into a ldrd/strd instruction.
161 bool CanMergeToLSDouble;
162 };
163 SpecificBumpPtrAllocator<MergeCandidate> Allocator;
164 SmallVector<const MergeCandidate*,4> Candidates;
165 SmallVector<MachineInstr*,4> MergeBaseCandidates;
166
167 void moveLiveRegsBefore(const MachineBasicBlock &MBB,
168 MachineBasicBlock::const_iterator Before);
169 unsigned findFreeReg(const TargetRegisterClass &RegClass);
170 void UpdateBaseRegUses(MachineBasicBlock &MBB,
171 MachineBasicBlock::iterator MBBI, const DebugLoc &DL,
172 unsigned Base, unsigned WordOffset,
173 ARMCC::CondCodes Pred, unsigned PredReg);
174 MachineInstr *CreateLoadStoreMulti(
175 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
176 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
177 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
178 ArrayRef<std::pair<unsigned, bool>> Regs,
179 ArrayRef<MachineInstr*> Instrs);
180 MachineInstr *CreateLoadStoreDouble(
181 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
182 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
183 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
184 ArrayRef<std::pair<unsigned, bool>> Regs,
185 ArrayRef<MachineInstr*> Instrs) const;
186 void FormCandidates(const MemOpQueue &MemOps);
187 MachineInstr *MergeOpsUpdate(const MergeCandidate &Cand);
188 bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
189 MachineBasicBlock::iterator &MBBI);
190 bool MergeBaseUpdateLoadStore(MachineInstr *MI);
191 bool MergeBaseUpdateLSMultiple(MachineInstr *MI);
192 bool MergeBaseUpdateLSDouble(MachineInstr &MI) const;
193 bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
194 bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
195 bool CombineMovBx(MachineBasicBlock &MBB);
196 };
197
198 } // end anonymous namespace
199
200 char ARMLoadStoreOpt::ID = 0;
201
202 INITIALIZE_PASS(ARMLoadStoreOpt, "arm-ldst-opt", ARM_LOAD_STORE_OPT_NAME, false,
203 false)
204
definesCPSR(const MachineInstr & MI)205 static bool definesCPSR(const MachineInstr &MI) {
206 for (const auto &MO : MI.operands()) {
207 if (!MO.isReg())
208 continue;
209 if (MO.isDef() && MO.getReg() == ARM::CPSR && !MO.isDead())
210 // If the instruction has live CPSR def, then it's not safe to fold it
211 // into load / store.
212 return true;
213 }
214
215 return false;
216 }
217
getMemoryOpOffset(const MachineInstr & MI)218 static int getMemoryOpOffset(const MachineInstr &MI) {
219 unsigned Opcode = MI.getOpcode();
220 bool isAM3 = Opcode == ARM::LDRD || Opcode == ARM::STRD;
221 unsigned NumOperands = MI.getDesc().getNumOperands();
222 unsigned OffField = MI.getOperand(NumOperands - 3).getImm();
223
224 if (Opcode == ARM::t2LDRi12 || Opcode == ARM::t2LDRi8 ||
225 Opcode == ARM::t2STRi12 || Opcode == ARM::t2STRi8 ||
226 Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8 ||
227 Opcode == ARM::LDRi12 || Opcode == ARM::STRi12)
228 return OffField;
229
230 // Thumb1 immediate offsets are scaled by 4
231 if (Opcode == ARM::tLDRi || Opcode == ARM::tSTRi ||
232 Opcode == ARM::tLDRspi || Opcode == ARM::tSTRspi)
233 return OffField * 4;
234
235 int Offset = isAM3 ? ARM_AM::getAM3Offset(OffField)
236 : ARM_AM::getAM5Offset(OffField) * 4;
237 ARM_AM::AddrOpc Op = isAM3 ? ARM_AM::getAM3Op(OffField)
238 : ARM_AM::getAM5Op(OffField);
239
240 if (Op == ARM_AM::sub)
241 return -Offset;
242
243 return Offset;
244 }
245
getLoadStoreBaseOp(const MachineInstr & MI)246 static const MachineOperand &getLoadStoreBaseOp(const MachineInstr &MI) {
247 return MI.getOperand(1);
248 }
249
getLoadStoreRegOp(const MachineInstr & MI)250 static const MachineOperand &getLoadStoreRegOp(const MachineInstr &MI) {
251 return MI.getOperand(0);
252 }
253
getLoadStoreMultipleOpcode(unsigned Opcode,ARM_AM::AMSubMode Mode)254 static int getLoadStoreMultipleOpcode(unsigned Opcode, ARM_AM::AMSubMode Mode) {
255 switch (Opcode) {
256 default: llvm_unreachable("Unhandled opcode!");
257 case ARM::LDRi12:
258 ++NumLDMGened;
259 switch (Mode) {
260 default: llvm_unreachable("Unhandled submode!");
261 case ARM_AM::ia: return ARM::LDMIA;
262 case ARM_AM::da: return ARM::LDMDA;
263 case ARM_AM::db: return ARM::LDMDB;
264 case ARM_AM::ib: return ARM::LDMIB;
265 }
266 case ARM::STRi12:
267 ++NumSTMGened;
268 switch (Mode) {
269 default: llvm_unreachable("Unhandled submode!");
270 case ARM_AM::ia: return ARM::STMIA;
271 case ARM_AM::da: return ARM::STMDA;
272 case ARM_AM::db: return ARM::STMDB;
273 case ARM_AM::ib: return ARM::STMIB;
274 }
275 case ARM::tLDRi:
276 case ARM::tLDRspi:
277 // tLDMIA is writeback-only - unless the base register is in the input
278 // reglist.
279 ++NumLDMGened;
280 switch (Mode) {
281 default: llvm_unreachable("Unhandled submode!");
282 case ARM_AM::ia: return ARM::tLDMIA;
283 }
284 case ARM::tSTRi:
285 case ARM::tSTRspi:
286 // There is no non-writeback tSTMIA either.
287 ++NumSTMGened;
288 switch (Mode) {
289 default: llvm_unreachable("Unhandled submode!");
290 case ARM_AM::ia: return ARM::tSTMIA_UPD;
291 }
292 case ARM::t2LDRi8:
293 case ARM::t2LDRi12:
294 ++NumLDMGened;
295 switch (Mode) {
296 default: llvm_unreachable("Unhandled submode!");
297 case ARM_AM::ia: return ARM::t2LDMIA;
298 case ARM_AM::db: return ARM::t2LDMDB;
299 }
300 case ARM::t2STRi8:
301 case ARM::t2STRi12:
302 ++NumSTMGened;
303 switch (Mode) {
304 default: llvm_unreachable("Unhandled submode!");
305 case ARM_AM::ia: return ARM::t2STMIA;
306 case ARM_AM::db: return ARM::t2STMDB;
307 }
308 case ARM::VLDRS:
309 ++NumVLDMGened;
310 switch (Mode) {
311 default: llvm_unreachable("Unhandled submode!");
312 case ARM_AM::ia: return ARM::VLDMSIA;
313 case ARM_AM::db: return 0; // Only VLDMSDB_UPD exists.
314 }
315 case ARM::VSTRS:
316 ++NumVSTMGened;
317 switch (Mode) {
318 default: llvm_unreachable("Unhandled submode!");
319 case ARM_AM::ia: return ARM::VSTMSIA;
320 case ARM_AM::db: return 0; // Only VSTMSDB_UPD exists.
321 }
322 case ARM::VLDRD:
323 ++NumVLDMGened;
324 switch (Mode) {
325 default: llvm_unreachable("Unhandled submode!");
326 case ARM_AM::ia: return ARM::VLDMDIA;
327 case ARM_AM::db: return 0; // Only VLDMDDB_UPD exists.
328 }
329 case ARM::VSTRD:
330 ++NumVSTMGened;
331 switch (Mode) {
332 default: llvm_unreachable("Unhandled submode!");
333 case ARM_AM::ia: return ARM::VSTMDIA;
334 case ARM_AM::db: return 0; // Only VSTMDDB_UPD exists.
335 }
336 }
337 }
338
getLoadStoreMultipleSubMode(unsigned Opcode)339 static ARM_AM::AMSubMode getLoadStoreMultipleSubMode(unsigned Opcode) {
340 switch (Opcode) {
341 default: llvm_unreachable("Unhandled opcode!");
342 case ARM::LDMIA_RET:
343 case ARM::LDMIA:
344 case ARM::LDMIA_UPD:
345 case ARM::STMIA:
346 case ARM::STMIA_UPD:
347 case ARM::tLDMIA:
348 case ARM::tLDMIA_UPD:
349 case ARM::tSTMIA_UPD:
350 case ARM::t2LDMIA_RET:
351 case ARM::t2LDMIA:
352 case ARM::t2LDMIA_UPD:
353 case ARM::t2STMIA:
354 case ARM::t2STMIA_UPD:
355 case ARM::VLDMSIA:
356 case ARM::VLDMSIA_UPD:
357 case ARM::VSTMSIA:
358 case ARM::VSTMSIA_UPD:
359 case ARM::VLDMDIA:
360 case ARM::VLDMDIA_UPD:
361 case ARM::VSTMDIA:
362 case ARM::VSTMDIA_UPD:
363 return ARM_AM::ia;
364
365 case ARM::LDMDA:
366 case ARM::LDMDA_UPD:
367 case ARM::STMDA:
368 case ARM::STMDA_UPD:
369 return ARM_AM::da;
370
371 case ARM::LDMDB:
372 case ARM::LDMDB_UPD:
373 case ARM::STMDB:
374 case ARM::STMDB_UPD:
375 case ARM::t2LDMDB:
376 case ARM::t2LDMDB_UPD:
377 case ARM::t2STMDB:
378 case ARM::t2STMDB_UPD:
379 case ARM::VLDMSDB_UPD:
380 case ARM::VSTMSDB_UPD:
381 case ARM::VLDMDDB_UPD:
382 case ARM::VSTMDDB_UPD:
383 return ARM_AM::db;
384
385 case ARM::LDMIB:
386 case ARM::LDMIB_UPD:
387 case ARM::STMIB:
388 case ARM::STMIB_UPD:
389 return ARM_AM::ib;
390 }
391 }
392
isT1i32Load(unsigned Opc)393 static bool isT1i32Load(unsigned Opc) {
394 return Opc == ARM::tLDRi || Opc == ARM::tLDRspi;
395 }
396
isT2i32Load(unsigned Opc)397 static bool isT2i32Load(unsigned Opc) {
398 return Opc == ARM::t2LDRi12 || Opc == ARM::t2LDRi8;
399 }
400
isi32Load(unsigned Opc)401 static bool isi32Load(unsigned Opc) {
402 return Opc == ARM::LDRi12 || isT1i32Load(Opc) || isT2i32Load(Opc) ;
403 }
404
isT1i32Store(unsigned Opc)405 static bool isT1i32Store(unsigned Opc) {
406 return Opc == ARM::tSTRi || Opc == ARM::tSTRspi;
407 }
408
isT2i32Store(unsigned Opc)409 static bool isT2i32Store(unsigned Opc) {
410 return Opc == ARM::t2STRi12 || Opc == ARM::t2STRi8;
411 }
412
isi32Store(unsigned Opc)413 static bool isi32Store(unsigned Opc) {
414 return Opc == ARM::STRi12 || isT1i32Store(Opc) || isT2i32Store(Opc);
415 }
416
isLoadSingle(unsigned Opc)417 static bool isLoadSingle(unsigned Opc) {
418 return isi32Load(Opc) || Opc == ARM::VLDRS || Opc == ARM::VLDRD;
419 }
420
getImmScale(unsigned Opc)421 static unsigned getImmScale(unsigned Opc) {
422 switch (Opc) {
423 default: llvm_unreachable("Unhandled opcode!");
424 case ARM::tLDRi:
425 case ARM::tSTRi:
426 case ARM::tLDRspi:
427 case ARM::tSTRspi:
428 return 1;
429 case ARM::tLDRHi:
430 case ARM::tSTRHi:
431 return 2;
432 case ARM::tLDRBi:
433 case ARM::tSTRBi:
434 return 4;
435 }
436 }
437
getLSMultipleTransferSize(const MachineInstr * MI)438 static unsigned getLSMultipleTransferSize(const MachineInstr *MI) {
439 switch (MI->getOpcode()) {
440 default: return 0;
441 case ARM::LDRi12:
442 case ARM::STRi12:
443 case ARM::tLDRi:
444 case ARM::tSTRi:
445 case ARM::tLDRspi:
446 case ARM::tSTRspi:
447 case ARM::t2LDRi8:
448 case ARM::t2LDRi12:
449 case ARM::t2STRi8:
450 case ARM::t2STRi12:
451 case ARM::VLDRS:
452 case ARM::VSTRS:
453 return 4;
454 case ARM::VLDRD:
455 case ARM::VSTRD:
456 return 8;
457 case ARM::LDMIA:
458 case ARM::LDMDA:
459 case ARM::LDMDB:
460 case ARM::LDMIB:
461 case ARM::STMIA:
462 case ARM::STMDA:
463 case ARM::STMDB:
464 case ARM::STMIB:
465 case ARM::tLDMIA:
466 case ARM::tLDMIA_UPD:
467 case ARM::tSTMIA_UPD:
468 case ARM::t2LDMIA:
469 case ARM::t2LDMDB:
470 case ARM::t2STMIA:
471 case ARM::t2STMDB:
472 case ARM::VLDMSIA:
473 case ARM::VSTMSIA:
474 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 4;
475 case ARM::VLDMDIA:
476 case ARM::VSTMDIA:
477 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 8;
478 }
479 }
480
481 /// Update future uses of the base register with the offset introduced
482 /// due to writeback. This function only works on Thumb1.
UpdateBaseRegUses(MachineBasicBlock & MBB,MachineBasicBlock::iterator MBBI,const DebugLoc & DL,unsigned Base,unsigned WordOffset,ARMCC::CondCodes Pred,unsigned PredReg)483 void ARMLoadStoreOpt::UpdateBaseRegUses(MachineBasicBlock &MBB,
484 MachineBasicBlock::iterator MBBI,
485 const DebugLoc &DL, unsigned Base,
486 unsigned WordOffset,
487 ARMCC::CondCodes Pred,
488 unsigned PredReg) {
489 assert(isThumb1 && "Can only update base register uses for Thumb1!");
490 // Start updating any instructions with immediate offsets. Insert a SUB before
491 // the first non-updateable instruction (if any).
492 for (; MBBI != MBB.end(); ++MBBI) {
493 bool InsertSub = false;
494 unsigned Opc = MBBI->getOpcode();
495
496 if (MBBI->readsRegister(Base)) {
497 int Offset;
498 bool IsLoad =
499 Opc == ARM::tLDRi || Opc == ARM::tLDRHi || Opc == ARM::tLDRBi;
500 bool IsStore =
501 Opc == ARM::tSTRi || Opc == ARM::tSTRHi || Opc == ARM::tSTRBi;
502
503 if (IsLoad || IsStore) {
504 // Loads and stores with immediate offsets can be updated, but only if
505 // the new offset isn't negative.
506 // The MachineOperand containing the offset immediate is the last one
507 // before predicates.
508 MachineOperand &MO =
509 MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
510 // The offsets are scaled by 1, 2 or 4 depending on the Opcode.
511 Offset = MO.getImm() - WordOffset * getImmScale(Opc);
512
513 // If storing the base register, it needs to be reset first.
514 Register InstrSrcReg = getLoadStoreRegOp(*MBBI).getReg();
515
516 if (Offset >= 0 && !(IsStore && InstrSrcReg == Base))
517 MO.setImm(Offset);
518 else
519 InsertSub = true;
520 } else if ((Opc == ARM::tSUBi8 || Opc == ARM::tADDi8) &&
521 !definesCPSR(*MBBI)) {
522 // SUBS/ADDS using this register, with a dead def of the CPSR.
523 // Merge it with the update; if the merged offset is too large,
524 // insert a new sub instead.
525 MachineOperand &MO =
526 MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
527 Offset = (Opc == ARM::tSUBi8) ?
528 MO.getImm() + WordOffset * 4 :
529 MO.getImm() - WordOffset * 4 ;
530 if (Offset >= 0 && TL->isLegalAddImmediate(Offset)) {
531 // FIXME: Swap ADDS<->SUBS if Offset < 0, erase instruction if
532 // Offset == 0.
533 MO.setImm(Offset);
534 // The base register has now been reset, so exit early.
535 return;
536 } else {
537 InsertSub = true;
538 }
539 } else {
540 // Can't update the instruction.
541 InsertSub = true;
542 }
543 } else if (definesCPSR(*MBBI) || MBBI->isCall() || MBBI->isBranch()) {
544 // Since SUBS sets the condition flags, we can't place the base reset
545 // after an instruction that has a live CPSR def.
546 // The base register might also contain an argument for a function call.
547 InsertSub = true;
548 }
549
550 if (InsertSub) {
551 // An instruction above couldn't be updated, so insert a sub.
552 BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base)
553 .add(t1CondCodeOp(true))
554 .addReg(Base)
555 .addImm(WordOffset * 4)
556 .addImm(Pred)
557 .addReg(PredReg);
558 return;
559 }
560
561 if (MBBI->killsRegister(Base) || MBBI->definesRegister(Base))
562 // Register got killed. Stop updating.
563 return;
564 }
565
566 // End of block was reached.
567 if (MBB.succ_size() > 0) {
568 // FIXME: Because of a bug, live registers are sometimes missing from
569 // the successor blocks' live-in sets. This means we can't trust that
570 // information and *always* have to reset at the end of a block.
571 // See PR21029.
572 if (MBBI != MBB.end()) --MBBI;
573 BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base)
574 .add(t1CondCodeOp(true))
575 .addReg(Base)
576 .addImm(WordOffset * 4)
577 .addImm(Pred)
578 .addReg(PredReg);
579 }
580 }
581
582 /// Return the first register of class \p RegClass that is not in \p Regs.
findFreeReg(const TargetRegisterClass & RegClass)583 unsigned ARMLoadStoreOpt::findFreeReg(const TargetRegisterClass &RegClass) {
584 if (!RegClassInfoValid) {
585 RegClassInfo.runOnMachineFunction(*MF);
586 RegClassInfoValid = true;
587 }
588
589 for (unsigned Reg : RegClassInfo.getOrder(&RegClass))
590 if (!LiveRegs.contains(Reg))
591 return Reg;
592 return 0;
593 }
594
595 /// Compute live registers just before instruction \p Before (in normal schedule
596 /// direction). Computes backwards so multiple queries in the same block must
597 /// come in reverse order.
moveLiveRegsBefore(const MachineBasicBlock & MBB,MachineBasicBlock::const_iterator Before)598 void ARMLoadStoreOpt::moveLiveRegsBefore(const MachineBasicBlock &MBB,
599 MachineBasicBlock::const_iterator Before) {
600 // Initialize if we never queried in this block.
601 if (!LiveRegsValid) {
602 LiveRegs.init(*TRI);
603 LiveRegs.addLiveOuts(MBB);
604 LiveRegPos = MBB.end();
605 LiveRegsValid = true;
606 }
607 // Move backward just before the "Before" position.
608 while (LiveRegPos != Before) {
609 --LiveRegPos;
610 LiveRegs.stepBackward(*LiveRegPos);
611 }
612 }
613
ContainsReg(const ArrayRef<std::pair<unsigned,bool>> & Regs,unsigned Reg)614 static bool ContainsReg(const ArrayRef<std::pair<unsigned, bool>> &Regs,
615 unsigned Reg) {
616 for (const std::pair<unsigned, bool> &R : Regs)
617 if (R.first == Reg)
618 return true;
619 return false;
620 }
621
622 /// Create and insert a LDM or STM with Base as base register and registers in
623 /// Regs as the register operands that would be loaded / stored. It returns
624 /// true if the transformation is done.
CreateLoadStoreMulti(MachineBasicBlock & MBB,MachineBasicBlock::iterator InsertBefore,int Offset,unsigned Base,bool BaseKill,unsigned Opcode,ARMCC::CondCodes Pred,unsigned PredReg,const DebugLoc & DL,ArrayRef<std::pair<unsigned,bool>> Regs,ArrayRef<MachineInstr * > Instrs)625 MachineInstr *ARMLoadStoreOpt::CreateLoadStoreMulti(
626 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
627 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
628 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
629 ArrayRef<std::pair<unsigned, bool>> Regs,
630 ArrayRef<MachineInstr*> Instrs) {
631 unsigned NumRegs = Regs.size();
632 assert(NumRegs > 1);
633
634 // For Thumb1 targets, it might be necessary to clobber the CPSR to merge.
635 // Compute liveness information for that register to make the decision.
636 bool SafeToClobberCPSR = !isThumb1 ||
637 (MBB.computeRegisterLiveness(TRI, ARM::CPSR, InsertBefore, 20) ==
638 MachineBasicBlock::LQR_Dead);
639
640 bool Writeback = isThumb1; // Thumb1 LDM/STM have base reg writeback.
641
642 // Exception: If the base register is in the input reglist, Thumb1 LDM is
643 // non-writeback.
644 // It's also not possible to merge an STR of the base register in Thumb1.
645 if (isThumb1 && ContainsReg(Regs, Base)) {
646 assert(Base != ARM::SP && "Thumb1 does not allow SP in register list");
647 if (Opcode == ARM::tLDRi)
648 Writeback = false;
649 else if (Opcode == ARM::tSTRi)
650 return nullptr;
651 }
652
653 ARM_AM::AMSubMode Mode = ARM_AM::ia;
654 // VFP and Thumb2 do not support IB or DA modes. Thumb1 only supports IA.
655 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
656 bool haveIBAndDA = isNotVFP && !isThumb2 && !isThumb1;
657
658 if (Offset == 4 && haveIBAndDA) {
659 Mode = ARM_AM::ib;
660 } else if (Offset == -4 * (int)NumRegs + 4 && haveIBAndDA) {
661 Mode = ARM_AM::da;
662 } else if (Offset == -4 * (int)NumRegs && isNotVFP && !isThumb1) {
663 // VLDM/VSTM do not support DB mode without also updating the base reg.
664 Mode = ARM_AM::db;
665 } else if (Offset != 0 || Opcode == ARM::tLDRspi || Opcode == ARM::tSTRspi) {
666 // Check if this is a supported opcode before inserting instructions to
667 // calculate a new base register.
668 if (!getLoadStoreMultipleOpcode(Opcode, Mode)) return nullptr;
669
670 // If starting offset isn't zero, insert a MI to materialize a new base.
671 // But only do so if it is cost effective, i.e. merging more than two
672 // loads / stores.
673 if (NumRegs <= 2)
674 return nullptr;
675
676 // On Thumb1, it's not worth materializing a new base register without
677 // clobbering the CPSR (i.e. not using ADDS/SUBS).
678 if (!SafeToClobberCPSR)
679 return nullptr;
680
681 unsigned NewBase;
682 if (isi32Load(Opcode)) {
683 // If it is a load, then just use one of the destination registers
684 // as the new base. Will no longer be writeback in Thumb1.
685 NewBase = Regs[NumRegs-1].first;
686 Writeback = false;
687 } else {
688 // Find a free register that we can use as scratch register.
689 moveLiveRegsBefore(MBB, InsertBefore);
690 // The merged instruction does not exist yet but will use several Regs if
691 // it is a Store.
692 if (!isLoadSingle(Opcode))
693 for (const std::pair<unsigned, bool> &R : Regs)
694 LiveRegs.addReg(R.first);
695
696 NewBase = findFreeReg(isThumb1 ? ARM::tGPRRegClass : ARM::GPRRegClass);
697 if (NewBase == 0)
698 return nullptr;
699 }
700
701 int BaseOpc = isThumb2 ? (BaseKill && Base == ARM::SP ? ARM::t2ADDspImm
702 : ARM::t2ADDri)
703 : (isThumb1 && Base == ARM::SP)
704 ? ARM::tADDrSPi
705 : (isThumb1 && Offset < 8)
706 ? ARM::tADDi3
707 : isThumb1 ? ARM::tADDi8 : ARM::ADDri;
708
709 if (Offset < 0) {
710 // FIXME: There are no Thumb1 load/store instructions with negative
711 // offsets. So the Base != ARM::SP might be unnecessary.
712 Offset = -Offset;
713 BaseOpc = isThumb2 ? (BaseKill && Base == ARM::SP ? ARM::t2SUBspImm
714 : ARM::t2SUBri)
715 : (isThumb1 && Offset < 8 && Base != ARM::SP)
716 ? ARM::tSUBi3
717 : isThumb1 ? ARM::tSUBi8 : ARM::SUBri;
718 }
719
720 if (!TL->isLegalAddImmediate(Offset))
721 // FIXME: Try add with register operand?
722 return nullptr; // Probably not worth it then.
723
724 // We can only append a kill flag to the add/sub input if the value is not
725 // used in the register list of the stm as well.
726 bool KillOldBase = BaseKill &&
727 (!isi32Store(Opcode) || !ContainsReg(Regs, Base));
728
729 if (isThumb1) {
730 // Thumb1: depending on immediate size, use either
731 // ADDS NewBase, Base, #imm3
732 // or
733 // MOV NewBase, Base
734 // ADDS NewBase, #imm8.
735 if (Base != NewBase &&
736 (BaseOpc == ARM::tADDi8 || BaseOpc == ARM::tSUBi8)) {
737 // Need to insert a MOV to the new base first.
738 if (isARMLowRegister(NewBase) && isARMLowRegister(Base) &&
739 !STI->hasV6Ops()) {
740 // thumbv4t doesn't have lo->lo copies, and we can't predicate tMOVSr
741 if (Pred != ARMCC::AL)
742 return nullptr;
743 BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVSr), NewBase)
744 .addReg(Base, getKillRegState(KillOldBase));
745 } else
746 BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVr), NewBase)
747 .addReg(Base, getKillRegState(KillOldBase))
748 .add(predOps(Pred, PredReg));
749
750 // The following ADDS/SUBS becomes an update.
751 Base = NewBase;
752 KillOldBase = true;
753 }
754 if (BaseOpc == ARM::tADDrSPi) {
755 assert(Offset % 4 == 0 && "tADDrSPi offset is scaled by 4");
756 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
757 .addReg(Base, getKillRegState(KillOldBase))
758 .addImm(Offset / 4)
759 .add(predOps(Pred, PredReg));
760 } else
761 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
762 .add(t1CondCodeOp(true))
763 .addReg(Base, getKillRegState(KillOldBase))
764 .addImm(Offset)
765 .add(predOps(Pred, PredReg));
766 } else {
767 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
768 .addReg(Base, getKillRegState(KillOldBase))
769 .addImm(Offset)
770 .add(predOps(Pred, PredReg))
771 .add(condCodeOp());
772 }
773 Base = NewBase;
774 BaseKill = true; // New base is always killed straight away.
775 }
776
777 bool isDef = isLoadSingle(Opcode);
778
779 // Get LS multiple opcode. Note that for Thumb1 this might be an opcode with
780 // base register writeback.
781 Opcode = getLoadStoreMultipleOpcode(Opcode, Mode);
782 if (!Opcode)
783 return nullptr;
784
785 // Check if a Thumb1 LDM/STM merge is safe. This is the case if:
786 // - There is no writeback (LDM of base register),
787 // - the base register is killed by the merged instruction,
788 // - or it's safe to overwrite the condition flags, i.e. to insert a SUBS
789 // to reset the base register.
790 // Otherwise, don't merge.
791 // It's safe to return here since the code to materialize a new base register
792 // above is also conditional on SafeToClobberCPSR.
793 if (isThumb1 && !SafeToClobberCPSR && Writeback && !BaseKill)
794 return nullptr;
795
796 MachineInstrBuilder MIB;
797
798 if (Writeback) {
799 assert(isThumb1 && "expected Writeback only inThumb1");
800 if (Opcode == ARM::tLDMIA) {
801 assert(!(ContainsReg(Regs, Base)) && "Thumb1 can't LDM ! with Base in Regs");
802 // Update tLDMIA with writeback if necessary.
803 Opcode = ARM::tLDMIA_UPD;
804 }
805
806 MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
807
808 // Thumb1: we might need to set base writeback when building the MI.
809 MIB.addReg(Base, getDefRegState(true))
810 .addReg(Base, getKillRegState(BaseKill));
811
812 // The base isn't dead after a merged instruction with writeback.
813 // Insert a sub instruction after the newly formed instruction to reset.
814 if (!BaseKill)
815 UpdateBaseRegUses(MBB, InsertBefore, DL, Base, NumRegs, Pred, PredReg);
816 } else {
817 // No writeback, simply build the MachineInstr.
818 MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
819 MIB.addReg(Base, getKillRegState(BaseKill));
820 }
821
822 MIB.addImm(Pred).addReg(PredReg);
823
824 for (const std::pair<unsigned, bool> &R : Regs)
825 MIB.addReg(R.first, getDefRegState(isDef) | getKillRegState(R.second));
826
827 MIB.cloneMergedMemRefs(Instrs);
828
829 return MIB.getInstr();
830 }
831
CreateLoadStoreDouble(MachineBasicBlock & MBB,MachineBasicBlock::iterator InsertBefore,int Offset,unsigned Base,bool BaseKill,unsigned Opcode,ARMCC::CondCodes Pred,unsigned PredReg,const DebugLoc & DL,ArrayRef<std::pair<unsigned,bool>> Regs,ArrayRef<MachineInstr * > Instrs) const832 MachineInstr *ARMLoadStoreOpt::CreateLoadStoreDouble(
833 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
834 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
835 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
836 ArrayRef<std::pair<unsigned, bool>> Regs,
837 ArrayRef<MachineInstr*> Instrs) const {
838 bool IsLoad = isi32Load(Opcode);
839 assert((IsLoad || isi32Store(Opcode)) && "Must have integer load or store");
840 unsigned LoadStoreOpcode = IsLoad ? ARM::t2LDRDi8 : ARM::t2STRDi8;
841
842 assert(Regs.size() == 2);
843 MachineInstrBuilder MIB = BuildMI(MBB, InsertBefore, DL,
844 TII->get(LoadStoreOpcode));
845 if (IsLoad) {
846 MIB.addReg(Regs[0].first, RegState::Define)
847 .addReg(Regs[1].first, RegState::Define);
848 } else {
849 MIB.addReg(Regs[0].first, getKillRegState(Regs[0].second))
850 .addReg(Regs[1].first, getKillRegState(Regs[1].second));
851 }
852 MIB.addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
853 MIB.cloneMergedMemRefs(Instrs);
854 return MIB.getInstr();
855 }
856
857 /// Call MergeOps and update MemOps and merges accordingly on success.
MergeOpsUpdate(const MergeCandidate & Cand)858 MachineInstr *ARMLoadStoreOpt::MergeOpsUpdate(const MergeCandidate &Cand) {
859 const MachineInstr *First = Cand.Instrs.front();
860 unsigned Opcode = First->getOpcode();
861 bool IsLoad = isLoadSingle(Opcode);
862 SmallVector<std::pair<unsigned, bool>, 8> Regs;
863 SmallVector<unsigned, 4> ImpDefs;
864 DenseSet<unsigned> KilledRegs;
865 DenseSet<unsigned> UsedRegs;
866 // Determine list of registers and list of implicit super-register defs.
867 for (const MachineInstr *MI : Cand.Instrs) {
868 const MachineOperand &MO = getLoadStoreRegOp(*MI);
869 Register Reg = MO.getReg();
870 bool IsKill = MO.isKill();
871 if (IsKill)
872 KilledRegs.insert(Reg);
873 Regs.push_back(std::make_pair(Reg, IsKill));
874 UsedRegs.insert(Reg);
875
876 if (IsLoad) {
877 // Collect any implicit defs of super-registers, after merging we can't
878 // be sure anymore that we properly preserved these live ranges and must
879 // removed these implicit operands.
880 for (const MachineOperand &MO : MI->implicit_operands()) {
881 if (!MO.isReg() || !MO.isDef() || MO.isDead())
882 continue;
883 assert(MO.isImplicit());
884 Register DefReg = MO.getReg();
885
886 if (is_contained(ImpDefs, DefReg))
887 continue;
888 // We can ignore cases where the super-reg is read and written.
889 if (MI->readsRegister(DefReg))
890 continue;
891 ImpDefs.push_back(DefReg);
892 }
893 }
894 }
895
896 // Attempt the merge.
897 using iterator = MachineBasicBlock::iterator;
898
899 MachineInstr *LatestMI = Cand.Instrs[Cand.LatestMIIdx];
900 iterator InsertBefore = std::next(iterator(LatestMI));
901 MachineBasicBlock &MBB = *LatestMI->getParent();
902 unsigned Offset = getMemoryOpOffset(*First);
903 Register Base = getLoadStoreBaseOp(*First).getReg();
904 bool BaseKill = LatestMI->killsRegister(Base);
905 Register PredReg;
906 ARMCC::CondCodes Pred = getInstrPredicate(*First, PredReg);
907 DebugLoc DL = First->getDebugLoc();
908 MachineInstr *Merged = nullptr;
909 if (Cand.CanMergeToLSDouble)
910 Merged = CreateLoadStoreDouble(MBB, InsertBefore, Offset, Base, BaseKill,
911 Opcode, Pred, PredReg, DL, Regs,
912 Cand.Instrs);
913 if (!Merged && Cand.CanMergeToLSMulti)
914 Merged = CreateLoadStoreMulti(MBB, InsertBefore, Offset, Base, BaseKill,
915 Opcode, Pred, PredReg, DL, Regs, Cand.Instrs);
916 if (!Merged)
917 return nullptr;
918
919 // Determine earliest instruction that will get removed. We then keep an
920 // iterator just above it so the following erases don't invalidated it.
921 iterator EarliestI(Cand.Instrs[Cand.EarliestMIIdx]);
922 bool EarliestAtBegin = false;
923 if (EarliestI == MBB.begin()) {
924 EarliestAtBegin = true;
925 } else {
926 EarliestI = std::prev(EarliestI);
927 }
928
929 // Remove instructions which have been merged.
930 for (MachineInstr *MI : Cand.Instrs)
931 MBB.erase(MI);
932
933 // Determine range between the earliest removed instruction and the new one.
934 if (EarliestAtBegin)
935 EarliestI = MBB.begin();
936 else
937 EarliestI = std::next(EarliestI);
938 auto FixupRange = make_range(EarliestI, iterator(Merged));
939
940 if (isLoadSingle(Opcode)) {
941 // If the previous loads defined a super-reg, then we have to mark earlier
942 // operands undef; Replicate the super-reg def on the merged instruction.
943 for (MachineInstr &MI : FixupRange) {
944 for (unsigned &ImpDefReg : ImpDefs) {
945 for (MachineOperand &MO : MI.implicit_operands()) {
946 if (!MO.isReg() || MO.getReg() != ImpDefReg)
947 continue;
948 if (MO.readsReg())
949 MO.setIsUndef();
950 else if (MO.isDef())
951 ImpDefReg = 0;
952 }
953 }
954 }
955
956 MachineInstrBuilder MIB(*Merged->getParent()->getParent(), Merged);
957 for (unsigned ImpDef : ImpDefs)
958 MIB.addReg(ImpDef, RegState::ImplicitDefine);
959 } else {
960 // Remove kill flags: We are possibly storing the values later now.
961 assert(isi32Store(Opcode) || Opcode == ARM::VSTRS || Opcode == ARM::VSTRD);
962 for (MachineInstr &MI : FixupRange) {
963 for (MachineOperand &MO : MI.uses()) {
964 if (!MO.isReg() || !MO.isKill())
965 continue;
966 if (UsedRegs.count(MO.getReg()))
967 MO.setIsKill(false);
968 }
969 }
970 assert(ImpDefs.empty());
971 }
972
973 return Merged;
974 }
975
isValidLSDoubleOffset(int Offset)976 static bool isValidLSDoubleOffset(int Offset) {
977 unsigned Value = abs(Offset);
978 // t2LDRDi8/t2STRDi8 supports an 8 bit immediate which is internally
979 // multiplied by 4.
980 return (Value % 4) == 0 && Value < 1024;
981 }
982
983 /// Return true for loads/stores that can be combined to a double/multi
984 /// operation without increasing the requirements for alignment.
mayCombineMisaligned(const TargetSubtargetInfo & STI,const MachineInstr & MI)985 static bool mayCombineMisaligned(const TargetSubtargetInfo &STI,
986 const MachineInstr &MI) {
987 // vldr/vstr trap on misaligned pointers anyway, forming vldm makes no
988 // difference.
989 unsigned Opcode = MI.getOpcode();
990 if (!isi32Load(Opcode) && !isi32Store(Opcode))
991 return true;
992
993 // Stack pointer alignment is out of the programmers control so we can trust
994 // SP-relative loads/stores.
995 if (getLoadStoreBaseOp(MI).getReg() == ARM::SP &&
996 STI.getFrameLowering()->getTransientStackAlign() >= Align(4))
997 return true;
998 return false;
999 }
1000
1001 /// Find candidates for load/store multiple merge in list of MemOpQueueEntries.
FormCandidates(const MemOpQueue & MemOps)1002 void ARMLoadStoreOpt::FormCandidates(const MemOpQueue &MemOps) {
1003 const MachineInstr *FirstMI = MemOps[0].MI;
1004 unsigned Opcode = FirstMI->getOpcode();
1005 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
1006 unsigned Size = getLSMultipleTransferSize(FirstMI);
1007
1008 unsigned SIndex = 0;
1009 unsigned EIndex = MemOps.size();
1010 do {
1011 // Look at the first instruction.
1012 const MachineInstr *MI = MemOps[SIndex].MI;
1013 int Offset = MemOps[SIndex].Offset;
1014 const MachineOperand &PMO = getLoadStoreRegOp(*MI);
1015 Register PReg = PMO.getReg();
1016 unsigned PRegNum = PMO.isUndef() ? std::numeric_limits<unsigned>::max()
1017 : TRI->getEncodingValue(PReg);
1018 unsigned Latest = SIndex;
1019 unsigned Earliest = SIndex;
1020 unsigned Count = 1;
1021 bool CanMergeToLSDouble =
1022 STI->isThumb2() && isNotVFP && isValidLSDoubleOffset(Offset);
1023 // ARM errata 602117: LDRD with base in list may result in incorrect base
1024 // register when interrupted or faulted.
1025 if (STI->isCortexM3() && isi32Load(Opcode) &&
1026 PReg == getLoadStoreBaseOp(*MI).getReg())
1027 CanMergeToLSDouble = false;
1028
1029 bool CanMergeToLSMulti = true;
1030 // On swift vldm/vstm starting with an odd register number as that needs
1031 // more uops than single vldrs.
1032 if (STI->hasSlowOddRegister() && !isNotVFP && (PRegNum % 2) == 1)
1033 CanMergeToLSMulti = false;
1034
1035 // LDRD/STRD do not allow SP/PC. LDM/STM do not support it or have it
1036 // deprecated; LDM to PC is fine but cannot happen here.
1037 if (PReg == ARM::SP || PReg == ARM::PC)
1038 CanMergeToLSMulti = CanMergeToLSDouble = false;
1039
1040 // Should we be conservative?
1041 if (AssumeMisalignedLoadStores && !mayCombineMisaligned(*STI, *MI))
1042 CanMergeToLSMulti = CanMergeToLSDouble = false;
1043
1044 // vldm / vstm limit are 32 for S variants, 16 for D variants.
1045 unsigned Limit;
1046 switch (Opcode) {
1047 default:
1048 Limit = UINT_MAX;
1049 break;
1050 case ARM::VLDRD:
1051 case ARM::VSTRD:
1052 Limit = 16;
1053 break;
1054 }
1055
1056 // Merge following instructions where possible.
1057 for (unsigned I = SIndex+1; I < EIndex; ++I, ++Count) {
1058 int NewOffset = MemOps[I].Offset;
1059 if (NewOffset != Offset + (int)Size)
1060 break;
1061 const MachineOperand &MO = getLoadStoreRegOp(*MemOps[I].MI);
1062 Register Reg = MO.getReg();
1063 if (Reg == ARM::SP || Reg == ARM::PC)
1064 break;
1065 if (Count == Limit)
1066 break;
1067
1068 // See if the current load/store may be part of a multi load/store.
1069 unsigned RegNum = MO.isUndef() ? std::numeric_limits<unsigned>::max()
1070 : TRI->getEncodingValue(Reg);
1071 bool PartOfLSMulti = CanMergeToLSMulti;
1072 if (PartOfLSMulti) {
1073 // Register numbers must be in ascending order.
1074 if (RegNum <= PRegNum)
1075 PartOfLSMulti = false;
1076 // For VFP / NEON load/store multiples, the registers must be
1077 // consecutive and within the limit on the number of registers per
1078 // instruction.
1079 else if (!isNotVFP && RegNum != PRegNum+1)
1080 PartOfLSMulti = false;
1081 }
1082 // See if the current load/store may be part of a double load/store.
1083 bool PartOfLSDouble = CanMergeToLSDouble && Count <= 1;
1084
1085 if (!PartOfLSMulti && !PartOfLSDouble)
1086 break;
1087 CanMergeToLSMulti &= PartOfLSMulti;
1088 CanMergeToLSDouble &= PartOfLSDouble;
1089 // Track MemOp with latest and earliest position (Positions are
1090 // counted in reverse).
1091 unsigned Position = MemOps[I].Position;
1092 if (Position < MemOps[Latest].Position)
1093 Latest = I;
1094 else if (Position > MemOps[Earliest].Position)
1095 Earliest = I;
1096 // Prepare for next MemOp.
1097 Offset += Size;
1098 PRegNum = RegNum;
1099 }
1100
1101 // Form a candidate from the Ops collected so far.
1102 MergeCandidate *Candidate = new(Allocator.Allocate()) MergeCandidate;
1103 for (unsigned C = SIndex, CE = SIndex + Count; C < CE; ++C)
1104 Candidate->Instrs.push_back(MemOps[C].MI);
1105 Candidate->LatestMIIdx = Latest - SIndex;
1106 Candidate->EarliestMIIdx = Earliest - SIndex;
1107 Candidate->InsertPos = MemOps[Latest].Position;
1108 if (Count == 1)
1109 CanMergeToLSMulti = CanMergeToLSDouble = false;
1110 Candidate->CanMergeToLSMulti = CanMergeToLSMulti;
1111 Candidate->CanMergeToLSDouble = CanMergeToLSDouble;
1112 Candidates.push_back(Candidate);
1113 // Continue after the chain.
1114 SIndex += Count;
1115 } while (SIndex < EIndex);
1116 }
1117
getUpdatingLSMultipleOpcode(unsigned Opc,ARM_AM::AMSubMode Mode)1118 static unsigned getUpdatingLSMultipleOpcode(unsigned Opc,
1119 ARM_AM::AMSubMode Mode) {
1120 switch (Opc) {
1121 default: llvm_unreachable("Unhandled opcode!");
1122 case ARM::LDMIA:
1123 case ARM::LDMDA:
1124 case ARM::LDMDB:
1125 case ARM::LDMIB:
1126 switch (Mode) {
1127 default: llvm_unreachable("Unhandled submode!");
1128 case ARM_AM::ia: return ARM::LDMIA_UPD;
1129 case ARM_AM::ib: return ARM::LDMIB_UPD;
1130 case ARM_AM::da: return ARM::LDMDA_UPD;
1131 case ARM_AM::db: return ARM::LDMDB_UPD;
1132 }
1133 case ARM::STMIA:
1134 case ARM::STMDA:
1135 case ARM::STMDB:
1136 case ARM::STMIB:
1137 switch (Mode) {
1138 default: llvm_unreachable("Unhandled submode!");
1139 case ARM_AM::ia: return ARM::STMIA_UPD;
1140 case ARM_AM::ib: return ARM::STMIB_UPD;
1141 case ARM_AM::da: return ARM::STMDA_UPD;
1142 case ARM_AM::db: return ARM::STMDB_UPD;
1143 }
1144 case ARM::t2LDMIA:
1145 case ARM::t2LDMDB:
1146 switch (Mode) {
1147 default: llvm_unreachable("Unhandled submode!");
1148 case ARM_AM::ia: return ARM::t2LDMIA_UPD;
1149 case ARM_AM::db: return ARM::t2LDMDB_UPD;
1150 }
1151 case ARM::t2STMIA:
1152 case ARM::t2STMDB:
1153 switch (Mode) {
1154 default: llvm_unreachable("Unhandled submode!");
1155 case ARM_AM::ia: return ARM::t2STMIA_UPD;
1156 case ARM_AM::db: return ARM::t2STMDB_UPD;
1157 }
1158 case ARM::VLDMSIA:
1159 switch (Mode) {
1160 default: llvm_unreachable("Unhandled submode!");
1161 case ARM_AM::ia: return ARM::VLDMSIA_UPD;
1162 case ARM_AM::db: return ARM::VLDMSDB_UPD;
1163 }
1164 case ARM::VLDMDIA:
1165 switch (Mode) {
1166 default: llvm_unreachable("Unhandled submode!");
1167 case ARM_AM::ia: return ARM::VLDMDIA_UPD;
1168 case ARM_AM::db: return ARM::VLDMDDB_UPD;
1169 }
1170 case ARM::VSTMSIA:
1171 switch (Mode) {
1172 default: llvm_unreachable("Unhandled submode!");
1173 case ARM_AM::ia: return ARM::VSTMSIA_UPD;
1174 case ARM_AM::db: return ARM::VSTMSDB_UPD;
1175 }
1176 case ARM::VSTMDIA:
1177 switch (Mode) {
1178 default: llvm_unreachable("Unhandled submode!");
1179 case ARM_AM::ia: return ARM::VSTMDIA_UPD;
1180 case ARM_AM::db: return ARM::VSTMDDB_UPD;
1181 }
1182 }
1183 }
1184
1185 /// Check if the given instruction increments or decrements a register and
1186 /// return the amount it is incremented/decremented. Returns 0 if the CPSR flags
1187 /// generated by the instruction are possibly read as well.
isIncrementOrDecrement(const MachineInstr & MI,Register Reg,ARMCC::CondCodes Pred,Register PredReg)1188 static int isIncrementOrDecrement(const MachineInstr &MI, Register Reg,
1189 ARMCC::CondCodes Pred, Register PredReg) {
1190 bool CheckCPSRDef;
1191 int Scale;
1192 switch (MI.getOpcode()) {
1193 case ARM::tADDi8: Scale = 4; CheckCPSRDef = true; break;
1194 case ARM::tSUBi8: Scale = -4; CheckCPSRDef = true; break;
1195 case ARM::t2SUBri:
1196 case ARM::t2SUBspImm:
1197 case ARM::SUBri: Scale = -1; CheckCPSRDef = true; break;
1198 case ARM::t2ADDri:
1199 case ARM::t2ADDspImm:
1200 case ARM::ADDri: Scale = 1; CheckCPSRDef = true; break;
1201 case ARM::tADDspi: Scale = 4; CheckCPSRDef = false; break;
1202 case ARM::tSUBspi: Scale = -4; CheckCPSRDef = false; break;
1203 default: return 0;
1204 }
1205
1206 Register MIPredReg;
1207 if (MI.getOperand(0).getReg() != Reg ||
1208 MI.getOperand(1).getReg() != Reg ||
1209 getInstrPredicate(MI, MIPredReg) != Pred ||
1210 MIPredReg != PredReg)
1211 return 0;
1212
1213 if (CheckCPSRDef && definesCPSR(MI))
1214 return 0;
1215 return MI.getOperand(2).getImm() * Scale;
1216 }
1217
1218 /// Searches for an increment or decrement of \p Reg before \p MBBI.
1219 static MachineBasicBlock::iterator
findIncDecBefore(MachineBasicBlock::iterator MBBI,Register Reg,ARMCC::CondCodes Pred,Register PredReg,int & Offset)1220 findIncDecBefore(MachineBasicBlock::iterator MBBI, Register Reg,
1221 ARMCC::CondCodes Pred, Register PredReg, int &Offset) {
1222 Offset = 0;
1223 MachineBasicBlock &MBB = *MBBI->getParent();
1224 MachineBasicBlock::iterator BeginMBBI = MBB.begin();
1225 MachineBasicBlock::iterator EndMBBI = MBB.end();
1226 if (MBBI == BeginMBBI)
1227 return EndMBBI;
1228
1229 // Skip debug values.
1230 MachineBasicBlock::iterator PrevMBBI = std::prev(MBBI);
1231 while (PrevMBBI->isDebugInstr() && PrevMBBI != BeginMBBI)
1232 --PrevMBBI;
1233
1234 Offset = isIncrementOrDecrement(*PrevMBBI, Reg, Pred, PredReg);
1235 return Offset == 0 ? EndMBBI : PrevMBBI;
1236 }
1237
1238 /// Searches for a increment or decrement of \p Reg after \p MBBI.
1239 static MachineBasicBlock::iterator
findIncDecAfter(MachineBasicBlock::iterator MBBI,Register Reg,ARMCC::CondCodes Pred,Register PredReg,int & Offset)1240 findIncDecAfter(MachineBasicBlock::iterator MBBI, Register Reg,
1241 ARMCC::CondCodes Pred, Register PredReg, int &Offset) {
1242 Offset = 0;
1243 MachineBasicBlock &MBB = *MBBI->getParent();
1244 MachineBasicBlock::iterator EndMBBI = MBB.end();
1245 MachineBasicBlock::iterator NextMBBI = std::next(MBBI);
1246 // Skip debug values.
1247 while (NextMBBI != EndMBBI && NextMBBI->isDebugInstr())
1248 ++NextMBBI;
1249 if (NextMBBI == EndMBBI)
1250 return EndMBBI;
1251
1252 Offset = isIncrementOrDecrement(*NextMBBI, Reg, Pred, PredReg);
1253 return Offset == 0 ? EndMBBI : NextMBBI;
1254 }
1255
1256 /// Fold proceeding/trailing inc/dec of base register into the
1257 /// LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible:
1258 ///
1259 /// stmia rn, <ra, rb, rc>
1260 /// rn := rn + 4 * 3;
1261 /// =>
1262 /// stmia rn!, <ra, rb, rc>
1263 ///
1264 /// rn := rn - 4 * 3;
1265 /// ldmia rn, <ra, rb, rc>
1266 /// =>
1267 /// ldmdb rn!, <ra, rb, rc>
MergeBaseUpdateLSMultiple(MachineInstr * MI)1268 bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineInstr *MI) {
1269 // Thumb1 is already using updating loads/stores.
1270 if (isThumb1) return false;
1271 LLVM_DEBUG(dbgs() << "Attempting to merge update of: " << *MI);
1272
1273 const MachineOperand &BaseOP = MI->getOperand(0);
1274 Register Base = BaseOP.getReg();
1275 bool BaseKill = BaseOP.isKill();
1276 Register PredReg;
1277 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1278 unsigned Opcode = MI->getOpcode();
1279 DebugLoc DL = MI->getDebugLoc();
1280
1281 // Can't use an updating ld/st if the base register is also a dest
1282 // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
1283 for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i)
1284 if (MI->getOperand(i).getReg() == Base)
1285 return false;
1286
1287 int Bytes = getLSMultipleTransferSize(MI);
1288 MachineBasicBlock &MBB = *MI->getParent();
1289 MachineBasicBlock::iterator MBBI(MI);
1290 int Offset;
1291 MachineBasicBlock::iterator MergeInstr
1292 = findIncDecBefore(MBBI, Base, Pred, PredReg, Offset);
1293 ARM_AM::AMSubMode Mode = getLoadStoreMultipleSubMode(Opcode);
1294 if (Mode == ARM_AM::ia && Offset == -Bytes) {
1295 Mode = ARM_AM::db;
1296 } else if (Mode == ARM_AM::ib && Offset == -Bytes) {
1297 Mode = ARM_AM::da;
1298 } else {
1299 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1300 if (((Mode != ARM_AM::ia && Mode != ARM_AM::ib) || Offset != Bytes) &&
1301 ((Mode != ARM_AM::da && Mode != ARM_AM::db) || Offset != -Bytes)) {
1302
1303 // We couldn't find an inc/dec to merge. But if the base is dead, we
1304 // can still change to a writeback form as that will save us 2 bytes
1305 // of code size. It can create WAW hazards though, so only do it if
1306 // we're minimizing code size.
1307 if (!STI->hasMinSize() || !BaseKill)
1308 return false;
1309
1310 bool HighRegsUsed = false;
1311 for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i)
1312 if (MI->getOperand(i).getReg() >= ARM::R8) {
1313 HighRegsUsed = true;
1314 break;
1315 }
1316
1317 if (!HighRegsUsed)
1318 MergeInstr = MBB.end();
1319 else
1320 return false;
1321 }
1322 }
1323 if (MergeInstr != MBB.end()) {
1324 LLVM_DEBUG(dbgs() << " Erasing old increment: " << *MergeInstr);
1325 MBB.erase(MergeInstr);
1326 }
1327
1328 unsigned NewOpc = getUpdatingLSMultipleOpcode(Opcode, Mode);
1329 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
1330 .addReg(Base, getDefRegState(true)) // WB base register
1331 .addReg(Base, getKillRegState(BaseKill))
1332 .addImm(Pred).addReg(PredReg);
1333
1334 // Transfer the rest of operands.
1335 for (unsigned OpNum = 3, e = MI->getNumOperands(); OpNum != e; ++OpNum)
1336 MIB.add(MI->getOperand(OpNum));
1337
1338 // Transfer memoperands.
1339 MIB.setMemRefs(MI->memoperands());
1340
1341 LLVM_DEBUG(dbgs() << " Added new load/store: " << *MIB);
1342 MBB.erase(MBBI);
1343 return true;
1344 }
1345
getPreIndexedLoadStoreOpcode(unsigned Opc,ARM_AM::AddrOpc Mode)1346 static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc,
1347 ARM_AM::AddrOpc Mode) {
1348 switch (Opc) {
1349 case ARM::LDRi12:
1350 return ARM::LDR_PRE_IMM;
1351 case ARM::STRi12:
1352 return ARM::STR_PRE_IMM;
1353 case ARM::VLDRS:
1354 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1355 case ARM::VLDRD:
1356 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
1357 case ARM::VSTRS:
1358 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1359 case ARM::VSTRD:
1360 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
1361 case ARM::t2LDRi8:
1362 case ARM::t2LDRi12:
1363 return ARM::t2LDR_PRE;
1364 case ARM::t2STRi8:
1365 case ARM::t2STRi12:
1366 return ARM::t2STR_PRE;
1367 default: llvm_unreachable("Unhandled opcode!");
1368 }
1369 }
1370
getPostIndexedLoadStoreOpcode(unsigned Opc,ARM_AM::AddrOpc Mode)1371 static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc,
1372 ARM_AM::AddrOpc Mode) {
1373 switch (Opc) {
1374 case ARM::LDRi12:
1375 return ARM::LDR_POST_IMM;
1376 case ARM::STRi12:
1377 return ARM::STR_POST_IMM;
1378 case ARM::VLDRS:
1379 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1380 case ARM::VLDRD:
1381 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
1382 case ARM::VSTRS:
1383 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1384 case ARM::VSTRD:
1385 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
1386 case ARM::t2LDRi8:
1387 case ARM::t2LDRi12:
1388 return ARM::t2LDR_POST;
1389 case ARM::t2LDRBi8:
1390 case ARM::t2LDRBi12:
1391 return ARM::t2LDRB_POST;
1392 case ARM::t2LDRSBi8:
1393 case ARM::t2LDRSBi12:
1394 return ARM::t2LDRSB_POST;
1395 case ARM::t2LDRHi8:
1396 case ARM::t2LDRHi12:
1397 return ARM::t2LDRH_POST;
1398 case ARM::t2LDRSHi8:
1399 case ARM::t2LDRSHi12:
1400 return ARM::t2LDRSH_POST;
1401 case ARM::t2STRi8:
1402 case ARM::t2STRi12:
1403 return ARM::t2STR_POST;
1404 case ARM::t2STRBi8:
1405 case ARM::t2STRBi12:
1406 return ARM::t2STRB_POST;
1407 case ARM::t2STRHi8:
1408 case ARM::t2STRHi12:
1409 return ARM::t2STRH_POST;
1410
1411 case ARM::MVE_VLDRBS16:
1412 return ARM::MVE_VLDRBS16_post;
1413 case ARM::MVE_VLDRBS32:
1414 return ARM::MVE_VLDRBS32_post;
1415 case ARM::MVE_VLDRBU16:
1416 return ARM::MVE_VLDRBU16_post;
1417 case ARM::MVE_VLDRBU32:
1418 return ARM::MVE_VLDRBU32_post;
1419 case ARM::MVE_VLDRHS32:
1420 return ARM::MVE_VLDRHS32_post;
1421 case ARM::MVE_VLDRHU32:
1422 return ARM::MVE_VLDRHU32_post;
1423 case ARM::MVE_VLDRBU8:
1424 return ARM::MVE_VLDRBU8_post;
1425 case ARM::MVE_VLDRHU16:
1426 return ARM::MVE_VLDRHU16_post;
1427 case ARM::MVE_VLDRWU32:
1428 return ARM::MVE_VLDRWU32_post;
1429 case ARM::MVE_VSTRB16:
1430 return ARM::MVE_VSTRB16_post;
1431 case ARM::MVE_VSTRB32:
1432 return ARM::MVE_VSTRB32_post;
1433 case ARM::MVE_VSTRH32:
1434 return ARM::MVE_VSTRH32_post;
1435 case ARM::MVE_VSTRBU8:
1436 return ARM::MVE_VSTRBU8_post;
1437 case ARM::MVE_VSTRHU16:
1438 return ARM::MVE_VSTRHU16_post;
1439 case ARM::MVE_VSTRWU32:
1440 return ARM::MVE_VSTRWU32_post;
1441
1442 default: llvm_unreachable("Unhandled opcode!");
1443 }
1444 }
1445
1446 /// Fold proceeding/trailing inc/dec of base register into the
1447 /// LDR/STR/FLD{D|S}/FST{D|S} op when possible:
MergeBaseUpdateLoadStore(MachineInstr * MI)1448 bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineInstr *MI) {
1449 // Thumb1 doesn't have updating LDR/STR.
1450 // FIXME: Use LDM/STM with single register instead.
1451 if (isThumb1) return false;
1452 LLVM_DEBUG(dbgs() << "Attempting to merge update of: " << *MI);
1453
1454 Register Base = getLoadStoreBaseOp(*MI).getReg();
1455 bool BaseKill = getLoadStoreBaseOp(*MI).isKill();
1456 unsigned Opcode = MI->getOpcode();
1457 DebugLoc DL = MI->getDebugLoc();
1458 bool isAM5 = (Opcode == ARM::VLDRD || Opcode == ARM::VLDRS ||
1459 Opcode == ARM::VSTRD || Opcode == ARM::VSTRS);
1460 bool isAM2 = (Opcode == ARM::LDRi12 || Opcode == ARM::STRi12);
1461 if (isi32Load(Opcode) || isi32Store(Opcode))
1462 if (MI->getOperand(2).getImm() != 0)
1463 return false;
1464 if (isAM5 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0)
1465 return false;
1466
1467 // Can't do the merge if the destination register is the same as the would-be
1468 // writeback register.
1469 if (MI->getOperand(0).getReg() == Base)
1470 return false;
1471
1472 Register PredReg;
1473 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1474 int Bytes = getLSMultipleTransferSize(MI);
1475 MachineBasicBlock &MBB = *MI->getParent();
1476 MachineBasicBlock::iterator MBBI(MI);
1477 int Offset;
1478 MachineBasicBlock::iterator MergeInstr
1479 = findIncDecBefore(MBBI, Base, Pred, PredReg, Offset);
1480 unsigned NewOpc;
1481 if (!isAM5 && Offset == Bytes) {
1482 NewOpc = getPreIndexedLoadStoreOpcode(Opcode, ARM_AM::add);
1483 } else if (Offset == -Bytes) {
1484 NewOpc = getPreIndexedLoadStoreOpcode(Opcode, ARM_AM::sub);
1485 } else {
1486 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1487 if (Offset == Bytes) {
1488 NewOpc = getPostIndexedLoadStoreOpcode(Opcode, ARM_AM::add);
1489 } else if (!isAM5 && Offset == -Bytes) {
1490 NewOpc = getPostIndexedLoadStoreOpcode(Opcode, ARM_AM::sub);
1491 } else
1492 return false;
1493 }
1494 LLVM_DEBUG(dbgs() << " Erasing old increment: " << *MergeInstr);
1495 MBB.erase(MergeInstr);
1496
1497 ARM_AM::AddrOpc AddSub = Offset < 0 ? ARM_AM::sub : ARM_AM::add;
1498
1499 bool isLd = isLoadSingle(Opcode);
1500 if (isAM5) {
1501 // VLDM[SD]_UPD, VSTM[SD]_UPD
1502 // (There are no base-updating versions of VLDR/VSTR instructions, but the
1503 // updating load/store-multiple instructions can be used with only one
1504 // register.)
1505 MachineOperand &MO = MI->getOperand(0);
1506 auto MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
1507 .addReg(Base, getDefRegState(true)) // WB base register
1508 .addReg(Base, getKillRegState(isLd ? BaseKill : false))
1509 .addImm(Pred)
1510 .addReg(PredReg)
1511 .addReg(MO.getReg(), (isLd ? getDefRegState(true)
1512 : getKillRegState(MO.isKill())))
1513 .cloneMemRefs(*MI);
1514 (void)MIB;
1515 LLVM_DEBUG(dbgs() << " Added new instruction: " << *MIB);
1516 } else if (isLd) {
1517 if (isAM2) {
1518 // LDR_PRE, LDR_POST
1519 if (NewOpc == ARM::LDR_PRE_IMM || NewOpc == ARM::LDRB_PRE_IMM) {
1520 auto MIB =
1521 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1522 .addReg(Base, RegState::Define)
1523 .addReg(Base)
1524 .addImm(Offset)
1525 .addImm(Pred)
1526 .addReg(PredReg)
1527 .cloneMemRefs(*MI);
1528 (void)MIB;
1529 LLVM_DEBUG(dbgs() << " Added new instruction: " << *MIB);
1530 } else {
1531 int Imm = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
1532 auto MIB =
1533 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1534 .addReg(Base, RegState::Define)
1535 .addReg(Base)
1536 .addReg(0)
1537 .addImm(Imm)
1538 .add(predOps(Pred, PredReg))
1539 .cloneMemRefs(*MI);
1540 (void)MIB;
1541 LLVM_DEBUG(dbgs() << " Added new instruction: " << *MIB);
1542 }
1543 } else {
1544 // t2LDR_PRE, t2LDR_POST
1545 auto MIB =
1546 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1547 .addReg(Base, RegState::Define)
1548 .addReg(Base)
1549 .addImm(Offset)
1550 .add(predOps(Pred, PredReg))
1551 .cloneMemRefs(*MI);
1552 (void)MIB;
1553 LLVM_DEBUG(dbgs() << " Added new instruction: " << *MIB);
1554 }
1555 } else {
1556 MachineOperand &MO = MI->getOperand(0);
1557 // FIXME: post-indexed stores use am2offset_imm, which still encodes
1558 // the vestigal zero-reg offset register. When that's fixed, this clause
1559 // can be removed entirely.
1560 if (isAM2 && NewOpc == ARM::STR_POST_IMM) {
1561 int Imm = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
1562 // STR_PRE, STR_POST
1563 auto MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
1564 .addReg(MO.getReg(), getKillRegState(MO.isKill()))
1565 .addReg(Base)
1566 .addReg(0)
1567 .addImm(Imm)
1568 .add(predOps(Pred, PredReg))
1569 .cloneMemRefs(*MI);
1570 (void)MIB;
1571 LLVM_DEBUG(dbgs() << " Added new instruction: " << *MIB);
1572 } else {
1573 // t2STR_PRE, t2STR_POST
1574 auto MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
1575 .addReg(MO.getReg(), getKillRegState(MO.isKill()))
1576 .addReg(Base)
1577 .addImm(Offset)
1578 .add(predOps(Pred, PredReg))
1579 .cloneMemRefs(*MI);
1580 (void)MIB;
1581 LLVM_DEBUG(dbgs() << " Added new instruction: " << *MIB);
1582 }
1583 }
1584 MBB.erase(MBBI);
1585
1586 return true;
1587 }
1588
MergeBaseUpdateLSDouble(MachineInstr & MI) const1589 bool ARMLoadStoreOpt::MergeBaseUpdateLSDouble(MachineInstr &MI) const {
1590 unsigned Opcode = MI.getOpcode();
1591 assert((Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8) &&
1592 "Must have t2STRDi8 or t2LDRDi8");
1593 if (MI.getOperand(3).getImm() != 0)
1594 return false;
1595 LLVM_DEBUG(dbgs() << "Attempting to merge update of: " << MI);
1596
1597 // Behaviour for writeback is undefined if base register is the same as one
1598 // of the others.
1599 const MachineOperand &BaseOp = MI.getOperand(2);
1600 Register Base = BaseOp.getReg();
1601 const MachineOperand &Reg0Op = MI.getOperand(0);
1602 const MachineOperand &Reg1Op = MI.getOperand(1);
1603 if (Reg0Op.getReg() == Base || Reg1Op.getReg() == Base)
1604 return false;
1605
1606 Register PredReg;
1607 ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
1608 MachineBasicBlock::iterator MBBI(MI);
1609 MachineBasicBlock &MBB = *MI.getParent();
1610 int Offset;
1611 MachineBasicBlock::iterator MergeInstr = findIncDecBefore(MBBI, Base, Pred,
1612 PredReg, Offset);
1613 unsigned NewOpc;
1614 if (Offset == 8 || Offset == -8) {
1615 NewOpc = Opcode == ARM::t2LDRDi8 ? ARM::t2LDRD_PRE : ARM::t2STRD_PRE;
1616 } else {
1617 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1618 if (Offset == 8 || Offset == -8) {
1619 NewOpc = Opcode == ARM::t2LDRDi8 ? ARM::t2LDRD_POST : ARM::t2STRD_POST;
1620 } else
1621 return false;
1622 }
1623 LLVM_DEBUG(dbgs() << " Erasing old increment: " << *MergeInstr);
1624 MBB.erase(MergeInstr);
1625
1626 DebugLoc DL = MI.getDebugLoc();
1627 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc));
1628 if (NewOpc == ARM::t2LDRD_PRE || NewOpc == ARM::t2LDRD_POST) {
1629 MIB.add(Reg0Op).add(Reg1Op).addReg(BaseOp.getReg(), RegState::Define);
1630 } else {
1631 assert(NewOpc == ARM::t2STRD_PRE || NewOpc == ARM::t2STRD_POST);
1632 MIB.addReg(BaseOp.getReg(), RegState::Define).add(Reg0Op).add(Reg1Op);
1633 }
1634 MIB.addReg(BaseOp.getReg(), RegState::Kill)
1635 .addImm(Offset).addImm(Pred).addReg(PredReg);
1636 assert(TII->get(Opcode).getNumOperands() == 6 &&
1637 TII->get(NewOpc).getNumOperands() == 7 &&
1638 "Unexpected number of operands in Opcode specification.");
1639
1640 // Transfer implicit operands.
1641 for (const MachineOperand &MO : MI.implicit_operands())
1642 MIB.add(MO);
1643 MIB.cloneMemRefs(MI);
1644
1645 LLVM_DEBUG(dbgs() << " Added new load/store: " << *MIB);
1646 MBB.erase(MBBI);
1647 return true;
1648 }
1649
1650 /// Returns true if instruction is a memory operation that this pass is capable
1651 /// of operating on.
isMemoryOp(const MachineInstr & MI)1652 static bool isMemoryOp(const MachineInstr &MI) {
1653 unsigned Opcode = MI.getOpcode();
1654 switch (Opcode) {
1655 case ARM::VLDRS:
1656 case ARM::VSTRS:
1657 case ARM::VLDRD:
1658 case ARM::VSTRD:
1659 case ARM::LDRi12:
1660 case ARM::STRi12:
1661 case ARM::tLDRi:
1662 case ARM::tSTRi:
1663 case ARM::tLDRspi:
1664 case ARM::tSTRspi:
1665 case ARM::t2LDRi8:
1666 case ARM::t2LDRi12:
1667 case ARM::t2STRi8:
1668 case ARM::t2STRi12:
1669 break;
1670 default:
1671 return false;
1672 }
1673 if (!MI.getOperand(1).isReg())
1674 return false;
1675
1676 // When no memory operands are present, conservatively assume unaligned,
1677 // volatile, unfoldable.
1678 if (!MI.hasOneMemOperand())
1679 return false;
1680
1681 const MachineMemOperand &MMO = **MI.memoperands_begin();
1682
1683 // Don't touch volatile memory accesses - we may be changing their order.
1684 // TODO: We could allow unordered and monotonic atomics here, but we need to
1685 // make sure the resulting ldm/stm is correctly marked as atomic.
1686 if (MMO.isVolatile() || MMO.isAtomic())
1687 return false;
1688
1689 // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is
1690 // not.
1691 if (MMO.getAlign() < Align(4))
1692 return false;
1693
1694 // str <undef> could probably be eliminated entirely, but for now we just want
1695 // to avoid making a mess of it.
1696 // FIXME: Use str <undef> as a wildcard to enable better stm folding.
1697 if (MI.getOperand(0).isReg() && MI.getOperand(0).isUndef())
1698 return false;
1699
1700 // Likewise don't mess with references to undefined addresses.
1701 if (MI.getOperand(1).isUndef())
1702 return false;
1703
1704 return true;
1705 }
1706
InsertLDR_STR(MachineBasicBlock & MBB,MachineBasicBlock::iterator & MBBI,int Offset,bool isDef,unsigned NewOpc,unsigned Reg,bool RegDeadKill,bool RegUndef,unsigned BaseReg,bool BaseKill,bool BaseUndef,ARMCC::CondCodes Pred,unsigned PredReg,const TargetInstrInfo * TII,MachineInstr * MI)1707 static void InsertLDR_STR(MachineBasicBlock &MBB,
1708 MachineBasicBlock::iterator &MBBI, int Offset,
1709 bool isDef, unsigned NewOpc, unsigned Reg,
1710 bool RegDeadKill, bool RegUndef, unsigned BaseReg,
1711 bool BaseKill, bool BaseUndef, ARMCC::CondCodes Pred,
1712 unsigned PredReg, const TargetInstrInfo *TII,
1713 MachineInstr *MI) {
1714 if (isDef) {
1715 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1716 TII->get(NewOpc))
1717 .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill))
1718 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1719 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1720 // FIXME: This is overly conservative; the new instruction accesses 4
1721 // bytes, not 8.
1722 MIB.cloneMemRefs(*MI);
1723 } else {
1724 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1725 TII->get(NewOpc))
1726 .addReg(Reg, getKillRegState(RegDeadKill) | getUndefRegState(RegUndef))
1727 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1728 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1729 // FIXME: This is overly conservative; the new instruction accesses 4
1730 // bytes, not 8.
1731 MIB.cloneMemRefs(*MI);
1732 }
1733 }
1734
FixInvalidRegPairOp(MachineBasicBlock & MBB,MachineBasicBlock::iterator & MBBI)1735 bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB,
1736 MachineBasicBlock::iterator &MBBI) {
1737 MachineInstr *MI = &*MBBI;
1738 unsigned Opcode = MI->getOpcode();
1739 // FIXME: Code/comments below check Opcode == t2STRDi8, but this check returns
1740 // if we see this opcode.
1741 if (Opcode != ARM::LDRD && Opcode != ARM::STRD && Opcode != ARM::t2LDRDi8)
1742 return false;
1743
1744 const MachineOperand &BaseOp = MI->getOperand(2);
1745 Register BaseReg = BaseOp.getReg();
1746 Register EvenReg = MI->getOperand(0).getReg();
1747 Register OddReg = MI->getOperand(1).getReg();
1748 unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false);
1749 unsigned OddRegNum = TRI->getDwarfRegNum(OddReg, false);
1750
1751 // ARM errata 602117: LDRD with base in list may result in incorrect base
1752 // register when interrupted or faulted.
1753 bool Errata602117 = EvenReg == BaseReg &&
1754 (Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8) && STI->isCortexM3();
1755 // ARM LDRD/STRD needs consecutive registers.
1756 bool NonConsecutiveRegs = (Opcode == ARM::LDRD || Opcode == ARM::STRD) &&
1757 (EvenRegNum % 2 != 0 || EvenRegNum + 1 != OddRegNum);
1758
1759 if (!Errata602117 && !NonConsecutiveRegs)
1760 return false;
1761
1762 bool isT2 = Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8;
1763 bool isLd = Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8;
1764 bool EvenDeadKill = isLd ?
1765 MI->getOperand(0).isDead() : MI->getOperand(0).isKill();
1766 bool EvenUndef = MI->getOperand(0).isUndef();
1767 bool OddDeadKill = isLd ?
1768 MI->getOperand(1).isDead() : MI->getOperand(1).isKill();
1769 bool OddUndef = MI->getOperand(1).isUndef();
1770 bool BaseKill = BaseOp.isKill();
1771 bool BaseUndef = BaseOp.isUndef();
1772 assert((isT2 || MI->getOperand(3).getReg() == ARM::NoRegister) &&
1773 "register offset not handled below");
1774 int OffImm = getMemoryOpOffset(*MI);
1775 Register PredReg;
1776 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1777
1778 if (OddRegNum > EvenRegNum && OffImm == 0) {
1779 // Ascending register numbers and no offset. It's safe to change it to a
1780 // ldm or stm.
1781 unsigned NewOpc = (isLd)
1782 ? (isT2 ? ARM::t2LDMIA : ARM::LDMIA)
1783 : (isT2 ? ARM::t2STMIA : ARM::STMIA);
1784 if (isLd) {
1785 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1786 .addReg(BaseReg, getKillRegState(BaseKill))
1787 .addImm(Pred).addReg(PredReg)
1788 .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill))
1789 .addReg(OddReg, getDefRegState(isLd) | getDeadRegState(OddDeadKill))
1790 .cloneMemRefs(*MI);
1791 ++NumLDRD2LDM;
1792 } else {
1793 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1794 .addReg(BaseReg, getKillRegState(BaseKill))
1795 .addImm(Pred).addReg(PredReg)
1796 .addReg(EvenReg,
1797 getKillRegState(EvenDeadKill) | getUndefRegState(EvenUndef))
1798 .addReg(OddReg,
1799 getKillRegState(OddDeadKill) | getUndefRegState(OddUndef))
1800 .cloneMemRefs(*MI);
1801 ++NumSTRD2STM;
1802 }
1803 } else {
1804 // Split into two instructions.
1805 unsigned NewOpc = (isLd)
1806 ? (isT2 ? (OffImm < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1807 : (isT2 ? (OffImm < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1808 // Be extra careful for thumb2. t2LDRi8 can't reference a zero offset,
1809 // so adjust and use t2LDRi12 here for that.
1810 unsigned NewOpc2 = (isLd)
1811 ? (isT2 ? (OffImm+4 < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1812 : (isT2 ? (OffImm+4 < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1813 // If this is a load, make sure the first load does not clobber the base
1814 // register before the second load reads it.
1815 if (isLd && TRI->regsOverlap(EvenReg, BaseReg)) {
1816 assert(!TRI->regsOverlap(OddReg, BaseReg));
1817 InsertLDR_STR(MBB, MBBI, OffImm + 4, isLd, NewOpc2, OddReg, OddDeadKill,
1818 false, BaseReg, false, BaseUndef, Pred, PredReg, TII, MI);
1819 InsertLDR_STR(MBB, MBBI, OffImm, isLd, NewOpc, EvenReg, EvenDeadKill,
1820 false, BaseReg, BaseKill, BaseUndef, Pred, PredReg, TII,
1821 MI);
1822 } else {
1823 if (OddReg == EvenReg && EvenDeadKill) {
1824 // If the two source operands are the same, the kill marker is
1825 // probably on the first one. e.g.
1826 // t2STRDi8 killed %r5, %r5, killed %r9, 0, 14, %reg0
1827 EvenDeadKill = false;
1828 OddDeadKill = true;
1829 }
1830 // Never kill the base register in the first instruction.
1831 if (EvenReg == BaseReg)
1832 EvenDeadKill = false;
1833 InsertLDR_STR(MBB, MBBI, OffImm, isLd, NewOpc, EvenReg, EvenDeadKill,
1834 EvenUndef, BaseReg, false, BaseUndef, Pred, PredReg, TII,
1835 MI);
1836 InsertLDR_STR(MBB, MBBI, OffImm + 4, isLd, NewOpc2, OddReg, OddDeadKill,
1837 OddUndef, BaseReg, BaseKill, BaseUndef, Pred, PredReg, TII,
1838 MI);
1839 }
1840 if (isLd)
1841 ++NumLDRD2LDR;
1842 else
1843 ++NumSTRD2STR;
1844 }
1845
1846 MBBI = MBB.erase(MBBI);
1847 return true;
1848 }
1849
1850 /// An optimization pass to turn multiple LDR / STR ops of the same base and
1851 /// incrementing offset into LDM / STM ops.
LoadStoreMultipleOpti(MachineBasicBlock & MBB)1852 bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
1853 MemOpQueue MemOps;
1854 unsigned CurrBase = 0;
1855 unsigned CurrOpc = ~0u;
1856 ARMCC::CondCodes CurrPred = ARMCC::AL;
1857 unsigned Position = 0;
1858 assert(Candidates.size() == 0);
1859 assert(MergeBaseCandidates.size() == 0);
1860 LiveRegsValid = false;
1861
1862 for (MachineBasicBlock::iterator I = MBB.end(), MBBI; I != MBB.begin();
1863 I = MBBI) {
1864 // The instruction in front of the iterator is the one we look at.
1865 MBBI = std::prev(I);
1866 if (FixInvalidRegPairOp(MBB, MBBI))
1867 continue;
1868 ++Position;
1869
1870 if (isMemoryOp(*MBBI)) {
1871 unsigned Opcode = MBBI->getOpcode();
1872 const MachineOperand &MO = MBBI->getOperand(0);
1873 Register Reg = MO.getReg();
1874 Register Base = getLoadStoreBaseOp(*MBBI).getReg();
1875 Register PredReg;
1876 ARMCC::CondCodes Pred = getInstrPredicate(*MBBI, PredReg);
1877 int Offset = getMemoryOpOffset(*MBBI);
1878 if (CurrBase == 0) {
1879 // Start of a new chain.
1880 CurrBase = Base;
1881 CurrOpc = Opcode;
1882 CurrPred = Pred;
1883 MemOps.push_back(MemOpQueueEntry(*MBBI, Offset, Position));
1884 continue;
1885 }
1886 // Note: No need to match PredReg in the next if.
1887 if (CurrOpc == Opcode && CurrBase == Base && CurrPred == Pred) {
1888 // Watch out for:
1889 // r4 := ldr [r0, #8]
1890 // r4 := ldr [r0, #4]
1891 // or
1892 // r0 := ldr [r0]
1893 // If a load overrides the base register or a register loaded by
1894 // another load in our chain, we cannot take this instruction.
1895 bool Overlap = false;
1896 if (isLoadSingle(Opcode)) {
1897 Overlap = (Base == Reg);
1898 if (!Overlap) {
1899 for (const MemOpQueueEntry &E : MemOps) {
1900 if (TRI->regsOverlap(Reg, E.MI->getOperand(0).getReg())) {
1901 Overlap = true;
1902 break;
1903 }
1904 }
1905 }
1906 }
1907
1908 if (!Overlap) {
1909 // Check offset and sort memory operation into the current chain.
1910 if (Offset > MemOps.back().Offset) {
1911 MemOps.push_back(MemOpQueueEntry(*MBBI, Offset, Position));
1912 continue;
1913 } else {
1914 MemOpQueue::iterator MI, ME;
1915 for (MI = MemOps.begin(), ME = MemOps.end(); MI != ME; ++MI) {
1916 if (Offset < MI->Offset) {
1917 // Found a place to insert.
1918 break;
1919 }
1920 if (Offset == MI->Offset) {
1921 // Collision, abort.
1922 MI = ME;
1923 break;
1924 }
1925 }
1926 if (MI != MemOps.end()) {
1927 MemOps.insert(MI, MemOpQueueEntry(*MBBI, Offset, Position));
1928 continue;
1929 }
1930 }
1931 }
1932 }
1933
1934 // Don't advance the iterator; The op will start a new chain next.
1935 MBBI = I;
1936 --Position;
1937 // Fallthrough to look into existing chain.
1938 } else if (MBBI->isDebugInstr()) {
1939 continue;
1940 } else if (MBBI->getOpcode() == ARM::t2LDRDi8 ||
1941 MBBI->getOpcode() == ARM::t2STRDi8) {
1942 // ARMPreAllocLoadStoreOpt has already formed some LDRD/STRD instructions
1943 // remember them because we may still be able to merge add/sub into them.
1944 MergeBaseCandidates.push_back(&*MBBI);
1945 }
1946
1947 // If we are here then the chain is broken; Extract candidates for a merge.
1948 if (MemOps.size() > 0) {
1949 FormCandidates(MemOps);
1950 // Reset for the next chain.
1951 CurrBase = 0;
1952 CurrOpc = ~0u;
1953 CurrPred = ARMCC::AL;
1954 MemOps.clear();
1955 }
1956 }
1957 if (MemOps.size() > 0)
1958 FormCandidates(MemOps);
1959
1960 // Sort candidates so they get processed from end to begin of the basic
1961 // block later; This is necessary for liveness calculation.
1962 auto LessThan = [](const MergeCandidate* M0, const MergeCandidate *M1) {
1963 return M0->InsertPos < M1->InsertPos;
1964 };
1965 llvm::sort(Candidates, LessThan);
1966
1967 // Go through list of candidates and merge.
1968 bool Changed = false;
1969 for (const MergeCandidate *Candidate : Candidates) {
1970 if (Candidate->CanMergeToLSMulti || Candidate->CanMergeToLSDouble) {
1971 MachineInstr *Merged = MergeOpsUpdate(*Candidate);
1972 // Merge preceding/trailing base inc/dec into the merged op.
1973 if (Merged) {
1974 Changed = true;
1975 unsigned Opcode = Merged->getOpcode();
1976 if (Opcode == ARM::t2STRDi8 || Opcode == ARM::t2LDRDi8)
1977 MergeBaseUpdateLSDouble(*Merged);
1978 else
1979 MergeBaseUpdateLSMultiple(Merged);
1980 } else {
1981 for (MachineInstr *MI : Candidate->Instrs) {
1982 if (MergeBaseUpdateLoadStore(MI))
1983 Changed = true;
1984 }
1985 }
1986 } else {
1987 assert(Candidate->Instrs.size() == 1);
1988 if (MergeBaseUpdateLoadStore(Candidate->Instrs.front()))
1989 Changed = true;
1990 }
1991 }
1992 Candidates.clear();
1993 // Try to fold add/sub into the LDRD/STRD formed by ARMPreAllocLoadStoreOpt.
1994 for (MachineInstr *MI : MergeBaseCandidates)
1995 MergeBaseUpdateLSDouble(*MI);
1996 MergeBaseCandidates.clear();
1997
1998 return Changed;
1999 }
2000
2001 /// If this is a exit BB, try merging the return ops ("bx lr" and "mov pc, lr")
2002 /// into the preceding stack restore so it directly restore the value of LR
2003 /// into pc.
2004 /// ldmfd sp!, {..., lr}
2005 /// bx lr
2006 /// or
2007 /// ldmfd sp!, {..., lr}
2008 /// mov pc, lr
2009 /// =>
2010 /// ldmfd sp!, {..., pc}
MergeReturnIntoLDM(MachineBasicBlock & MBB)2011 bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) {
2012 // Thumb1 LDM doesn't allow high registers.
2013 if (isThumb1) return false;
2014 if (MBB.empty()) return false;
2015
2016 MachineBasicBlock::iterator MBBI = MBB.getLastNonDebugInstr();
2017 if (MBBI != MBB.begin() && MBBI != MBB.end() &&
2018 (MBBI->getOpcode() == ARM::BX_RET ||
2019 MBBI->getOpcode() == ARM::tBX_RET ||
2020 MBBI->getOpcode() == ARM::MOVPCLR)) {
2021 MachineBasicBlock::iterator PrevI = std::prev(MBBI);
2022 // Ignore any debug instructions.
2023 while (PrevI->isDebugInstr() && PrevI != MBB.begin())
2024 --PrevI;
2025 MachineInstr &PrevMI = *PrevI;
2026 unsigned Opcode = PrevMI.getOpcode();
2027 if (Opcode == ARM::LDMIA_UPD || Opcode == ARM::LDMDA_UPD ||
2028 Opcode == ARM::LDMDB_UPD || Opcode == ARM::LDMIB_UPD ||
2029 Opcode == ARM::t2LDMIA_UPD || Opcode == ARM::t2LDMDB_UPD) {
2030 MachineOperand &MO = PrevMI.getOperand(PrevMI.getNumOperands() - 1);
2031 if (MO.getReg() != ARM::LR)
2032 return false;
2033 unsigned NewOpc = (isThumb2 ? ARM::t2LDMIA_RET : ARM::LDMIA_RET);
2034 assert(((isThumb2 && Opcode == ARM::t2LDMIA_UPD) ||
2035 Opcode == ARM::LDMIA_UPD) && "Unsupported multiple load-return!");
2036 PrevMI.setDesc(TII->get(NewOpc));
2037 MO.setReg(ARM::PC);
2038 PrevMI.copyImplicitOps(*MBB.getParent(), *MBBI);
2039 MBB.erase(MBBI);
2040 // We now restore LR into PC so it is not live-out of the return block
2041 // anymore: Clear the CSI Restored bit.
2042 MachineFrameInfo &MFI = MBB.getParent()->getFrameInfo();
2043 // CSI should be fixed after PrologEpilog Insertion
2044 assert(MFI.isCalleeSavedInfoValid() && "CSI should be valid");
2045 for (CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) {
2046 if (Info.getReg() == ARM::LR) {
2047 Info.setRestored(false);
2048 break;
2049 }
2050 }
2051 return true;
2052 }
2053 }
2054 return false;
2055 }
2056
CombineMovBx(MachineBasicBlock & MBB)2057 bool ARMLoadStoreOpt::CombineMovBx(MachineBasicBlock &MBB) {
2058 MachineBasicBlock::iterator MBBI = MBB.getFirstTerminator();
2059 if (MBBI == MBB.begin() || MBBI == MBB.end() ||
2060 MBBI->getOpcode() != ARM::tBX_RET)
2061 return false;
2062
2063 MachineBasicBlock::iterator Prev = MBBI;
2064 --Prev;
2065 if (Prev->getOpcode() != ARM::tMOVr || !Prev->definesRegister(ARM::LR))
2066 return false;
2067
2068 for (auto Use : Prev->uses())
2069 if (Use.isKill()) {
2070 assert(STI->hasV4TOps());
2071 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(ARM::tBX))
2072 .addReg(Use.getReg(), RegState::Kill)
2073 .add(predOps(ARMCC::AL))
2074 .copyImplicitOps(*MBBI);
2075 MBB.erase(MBBI);
2076 MBB.erase(Prev);
2077 return true;
2078 }
2079
2080 llvm_unreachable("tMOVr doesn't kill a reg before tBX_RET?");
2081 }
2082
runOnMachineFunction(MachineFunction & Fn)2083 bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
2084 if (skipFunction(Fn.getFunction()))
2085 return false;
2086
2087 MF = &Fn;
2088 STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
2089 TL = STI->getTargetLowering();
2090 AFI = Fn.getInfo<ARMFunctionInfo>();
2091 TII = STI->getInstrInfo();
2092 TRI = STI->getRegisterInfo();
2093
2094 RegClassInfoValid = false;
2095 isThumb2 = AFI->isThumb2Function();
2096 isThumb1 = AFI->isThumbFunction() && !isThumb2;
2097
2098 bool Modified = false;
2099 for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
2100 ++MFI) {
2101 MachineBasicBlock &MBB = *MFI;
2102 Modified |= LoadStoreMultipleOpti(MBB);
2103 if (STI->hasV5TOps())
2104 Modified |= MergeReturnIntoLDM(MBB);
2105 if (isThumb1)
2106 Modified |= CombineMovBx(MBB);
2107 }
2108
2109 Allocator.DestroyAll();
2110 return Modified;
2111 }
2112
2113 #define ARM_PREALLOC_LOAD_STORE_OPT_NAME \
2114 "ARM pre- register allocation load / store optimization pass"
2115
2116 namespace {
2117
2118 /// Pre- register allocation pass that move load / stores from consecutive
2119 /// locations close to make it more likely they will be combined later.
2120 struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{
2121 static char ID;
2122
2123 AliasAnalysis *AA;
2124 const DataLayout *TD;
2125 const TargetInstrInfo *TII;
2126 const TargetRegisterInfo *TRI;
2127 const ARMSubtarget *STI;
2128 MachineRegisterInfo *MRI;
2129 MachineDominatorTree *DT;
2130 MachineFunction *MF;
2131
ARMPreAllocLoadStoreOpt__anon7c5dfe910311::ARMPreAllocLoadStoreOpt2132 ARMPreAllocLoadStoreOpt() : MachineFunctionPass(ID) {}
2133
2134 bool runOnMachineFunction(MachineFunction &Fn) override;
2135
getPassName__anon7c5dfe910311::ARMPreAllocLoadStoreOpt2136 StringRef getPassName() const override {
2137 return ARM_PREALLOC_LOAD_STORE_OPT_NAME;
2138 }
2139
getAnalysisUsage__anon7c5dfe910311::ARMPreAllocLoadStoreOpt2140 void getAnalysisUsage(AnalysisUsage &AU) const override {
2141 AU.addRequired<AAResultsWrapperPass>();
2142 AU.addRequired<MachineDominatorTree>();
2143 AU.addPreserved<MachineDominatorTree>();
2144 MachineFunctionPass::getAnalysisUsage(AU);
2145 }
2146
2147 private:
2148 bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl,
2149 unsigned &NewOpc, Register &EvenReg, Register &OddReg,
2150 Register &BaseReg, int &Offset, Register &PredReg,
2151 ARMCC::CondCodes &Pred, bool &isT2);
2152 bool RescheduleOps(MachineBasicBlock *MBB,
2153 SmallVectorImpl<MachineInstr *> &Ops,
2154 unsigned Base, bool isLd,
2155 DenseMap<MachineInstr*, unsigned> &MI2LocMap);
2156 bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
2157 bool DistributeIncrements();
2158 bool DistributeIncrements(Register Base);
2159 };
2160
2161 } // end anonymous namespace
2162
2163 char ARMPreAllocLoadStoreOpt::ID = 0;
2164
2165 INITIALIZE_PASS_BEGIN(ARMPreAllocLoadStoreOpt, "arm-prera-ldst-opt",
2166 ARM_PREALLOC_LOAD_STORE_OPT_NAME, false, false)
2167 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
2168 INITIALIZE_PASS_END(ARMPreAllocLoadStoreOpt, "arm-prera-ldst-opt",
2169 ARM_PREALLOC_LOAD_STORE_OPT_NAME, false, false)
2170
2171 // Limit the number of instructions to be rescheduled.
2172 // FIXME: tune this limit, and/or come up with some better heuristics.
2173 static cl::opt<unsigned> InstReorderLimit("arm-prera-ldst-opt-reorder-limit",
2174 cl::init(8), cl::Hidden);
2175
runOnMachineFunction(MachineFunction & Fn)2176 bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
2177 if (AssumeMisalignedLoadStores || skipFunction(Fn.getFunction()))
2178 return false;
2179
2180 TD = &Fn.getDataLayout();
2181 STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
2182 TII = STI->getInstrInfo();
2183 TRI = STI->getRegisterInfo();
2184 MRI = &Fn.getRegInfo();
2185 DT = &getAnalysis<MachineDominatorTree>();
2186 MF = &Fn;
2187 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
2188
2189 bool Modified = DistributeIncrements();
2190 for (MachineBasicBlock &MFI : Fn)
2191 Modified |= RescheduleLoadStoreInstrs(&MFI);
2192
2193 return Modified;
2194 }
2195
IsSafeAndProfitableToMove(bool isLd,unsigned Base,MachineBasicBlock::iterator I,MachineBasicBlock::iterator E,SmallPtrSetImpl<MachineInstr * > & MemOps,SmallSet<unsigned,4> & MemRegs,const TargetRegisterInfo * TRI,AliasAnalysis * AA)2196 static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base,
2197 MachineBasicBlock::iterator I,
2198 MachineBasicBlock::iterator E,
2199 SmallPtrSetImpl<MachineInstr*> &MemOps,
2200 SmallSet<unsigned, 4> &MemRegs,
2201 const TargetRegisterInfo *TRI,
2202 AliasAnalysis *AA) {
2203 // Are there stores / loads / calls between them?
2204 SmallSet<unsigned, 4> AddedRegPressure;
2205 while (++I != E) {
2206 if (I->isDebugInstr() || MemOps.count(&*I))
2207 continue;
2208 if (I->isCall() || I->isTerminator() || I->hasUnmodeledSideEffects())
2209 return false;
2210 if (I->mayStore() || (!isLd && I->mayLoad()))
2211 for (MachineInstr *MemOp : MemOps)
2212 if (I->mayAlias(AA, *MemOp, /*UseTBAA*/ false))
2213 return false;
2214 for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) {
2215 MachineOperand &MO = I->getOperand(j);
2216 if (!MO.isReg())
2217 continue;
2218 Register Reg = MO.getReg();
2219 if (MO.isDef() && TRI->regsOverlap(Reg, Base))
2220 return false;
2221 if (Reg != Base && !MemRegs.count(Reg))
2222 AddedRegPressure.insert(Reg);
2223 }
2224 }
2225
2226 // Estimate register pressure increase due to the transformation.
2227 if (MemRegs.size() <= 4)
2228 // Ok if we are moving small number of instructions.
2229 return true;
2230 return AddedRegPressure.size() <= MemRegs.size() * 2;
2231 }
2232
CanFormLdStDWord(MachineInstr * Op0,MachineInstr * Op1,DebugLoc & dl,unsigned & NewOpc,Register & FirstReg,Register & SecondReg,Register & BaseReg,int & Offset,Register & PredReg,ARMCC::CondCodes & Pred,bool & isT2)2233 bool ARMPreAllocLoadStoreOpt::CanFormLdStDWord(
2234 MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl, unsigned &NewOpc,
2235 Register &FirstReg, Register &SecondReg, Register &BaseReg, int &Offset,
2236 Register &PredReg, ARMCC::CondCodes &Pred, bool &isT2) {
2237 // Make sure we're allowed to generate LDRD/STRD.
2238 if (!STI->hasV5TEOps())
2239 return false;
2240
2241 // FIXME: VLDRS / VSTRS -> VLDRD / VSTRD
2242 unsigned Scale = 1;
2243 unsigned Opcode = Op0->getOpcode();
2244 if (Opcode == ARM::LDRi12) {
2245 NewOpc = ARM::LDRD;
2246 } else if (Opcode == ARM::STRi12) {
2247 NewOpc = ARM::STRD;
2248 } else if (Opcode == ARM::t2LDRi8 || Opcode == ARM::t2LDRi12) {
2249 NewOpc = ARM::t2LDRDi8;
2250 Scale = 4;
2251 isT2 = true;
2252 } else if (Opcode == ARM::t2STRi8 || Opcode == ARM::t2STRi12) {
2253 NewOpc = ARM::t2STRDi8;
2254 Scale = 4;
2255 isT2 = true;
2256 } else {
2257 return false;
2258 }
2259
2260 // Make sure the base address satisfies i64 ld / st alignment requirement.
2261 // At the moment, we ignore the memoryoperand's value.
2262 // If we want to use AliasAnalysis, we should check it accordingly.
2263 if (!Op0->hasOneMemOperand() ||
2264 (*Op0->memoperands_begin())->isVolatile() ||
2265 (*Op0->memoperands_begin())->isAtomic())
2266 return false;
2267
2268 Align Alignment = (*Op0->memoperands_begin())->getAlign();
2269 const Function &Func = MF->getFunction();
2270 Align ReqAlign =
2271 STI->hasV6Ops() ? TD->getABITypeAlign(Type::getInt64Ty(Func.getContext()))
2272 : Align(8); // Pre-v6 need 8-byte align
2273 if (Alignment < ReqAlign)
2274 return false;
2275
2276 // Then make sure the immediate offset fits.
2277 int OffImm = getMemoryOpOffset(*Op0);
2278 if (isT2) {
2279 int Limit = (1 << 8) * Scale;
2280 if (OffImm >= Limit || (OffImm <= -Limit) || (OffImm & (Scale-1)))
2281 return false;
2282 Offset = OffImm;
2283 } else {
2284 ARM_AM::AddrOpc AddSub = ARM_AM::add;
2285 if (OffImm < 0) {
2286 AddSub = ARM_AM::sub;
2287 OffImm = - OffImm;
2288 }
2289 int Limit = (1 << 8) * Scale;
2290 if (OffImm >= Limit || (OffImm & (Scale-1)))
2291 return false;
2292 Offset = ARM_AM::getAM3Opc(AddSub, OffImm);
2293 }
2294 FirstReg = Op0->getOperand(0).getReg();
2295 SecondReg = Op1->getOperand(0).getReg();
2296 if (FirstReg == SecondReg)
2297 return false;
2298 BaseReg = Op0->getOperand(1).getReg();
2299 Pred = getInstrPredicate(*Op0, PredReg);
2300 dl = Op0->getDebugLoc();
2301 return true;
2302 }
2303
RescheduleOps(MachineBasicBlock * MBB,SmallVectorImpl<MachineInstr * > & Ops,unsigned Base,bool isLd,DenseMap<MachineInstr *,unsigned> & MI2LocMap)2304 bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB,
2305 SmallVectorImpl<MachineInstr *> &Ops,
2306 unsigned Base, bool isLd,
2307 DenseMap<MachineInstr*, unsigned> &MI2LocMap) {
2308 bool RetVal = false;
2309
2310 // Sort by offset (in reverse order).
2311 llvm::sort(Ops, [](const MachineInstr *LHS, const MachineInstr *RHS) {
2312 int LOffset = getMemoryOpOffset(*LHS);
2313 int ROffset = getMemoryOpOffset(*RHS);
2314 assert(LHS == RHS || LOffset != ROffset);
2315 return LOffset > ROffset;
2316 });
2317
2318 // The loads / stores of the same base are in order. Scan them from first to
2319 // last and check for the following:
2320 // 1. Any def of base.
2321 // 2. Any gaps.
2322 while (Ops.size() > 1) {
2323 unsigned FirstLoc = ~0U;
2324 unsigned LastLoc = 0;
2325 MachineInstr *FirstOp = nullptr;
2326 MachineInstr *LastOp = nullptr;
2327 int LastOffset = 0;
2328 unsigned LastOpcode = 0;
2329 unsigned LastBytes = 0;
2330 unsigned NumMove = 0;
2331 for (int i = Ops.size() - 1; i >= 0; --i) {
2332 // Make sure each operation has the same kind.
2333 MachineInstr *Op = Ops[i];
2334 unsigned LSMOpcode
2335 = getLoadStoreMultipleOpcode(Op->getOpcode(), ARM_AM::ia);
2336 if (LastOpcode && LSMOpcode != LastOpcode)
2337 break;
2338
2339 // Check that we have a continuous set of offsets.
2340 int Offset = getMemoryOpOffset(*Op);
2341 unsigned Bytes = getLSMultipleTransferSize(Op);
2342 if (LastBytes) {
2343 if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes))
2344 break;
2345 }
2346
2347 // Don't try to reschedule too many instructions.
2348 if (NumMove == InstReorderLimit)
2349 break;
2350
2351 // Found a mergable instruction; save information about it.
2352 ++NumMove;
2353 LastOffset = Offset;
2354 LastBytes = Bytes;
2355 LastOpcode = LSMOpcode;
2356
2357 unsigned Loc = MI2LocMap[Op];
2358 if (Loc <= FirstLoc) {
2359 FirstLoc = Loc;
2360 FirstOp = Op;
2361 }
2362 if (Loc >= LastLoc) {
2363 LastLoc = Loc;
2364 LastOp = Op;
2365 }
2366 }
2367
2368 if (NumMove <= 1)
2369 Ops.pop_back();
2370 else {
2371 SmallPtrSet<MachineInstr*, 4> MemOps;
2372 SmallSet<unsigned, 4> MemRegs;
2373 for (size_t i = Ops.size() - NumMove, e = Ops.size(); i != e; ++i) {
2374 MemOps.insert(Ops[i]);
2375 MemRegs.insert(Ops[i]->getOperand(0).getReg());
2376 }
2377
2378 // Be conservative, if the instructions are too far apart, don't
2379 // move them. We want to limit the increase of register pressure.
2380 bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this.
2381 if (DoMove)
2382 DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp,
2383 MemOps, MemRegs, TRI, AA);
2384 if (!DoMove) {
2385 for (unsigned i = 0; i != NumMove; ++i)
2386 Ops.pop_back();
2387 } else {
2388 // This is the new location for the loads / stores.
2389 MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp;
2390 while (InsertPos != MBB->end() &&
2391 (MemOps.count(&*InsertPos) || InsertPos->isDebugInstr()))
2392 ++InsertPos;
2393
2394 // If we are moving a pair of loads / stores, see if it makes sense
2395 // to try to allocate a pair of registers that can form register pairs.
2396 MachineInstr *Op0 = Ops.back();
2397 MachineInstr *Op1 = Ops[Ops.size()-2];
2398 Register FirstReg, SecondReg;
2399 Register BaseReg, PredReg;
2400 ARMCC::CondCodes Pred = ARMCC::AL;
2401 bool isT2 = false;
2402 unsigned NewOpc = 0;
2403 int Offset = 0;
2404 DebugLoc dl;
2405 if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc,
2406 FirstReg, SecondReg, BaseReg,
2407 Offset, PredReg, Pred, isT2)) {
2408 Ops.pop_back();
2409 Ops.pop_back();
2410
2411 const MCInstrDesc &MCID = TII->get(NewOpc);
2412 const TargetRegisterClass *TRC = TII->getRegClass(MCID, 0, TRI, *MF);
2413 MRI->constrainRegClass(FirstReg, TRC);
2414 MRI->constrainRegClass(SecondReg, TRC);
2415
2416 // Form the pair instruction.
2417 if (isLd) {
2418 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
2419 .addReg(FirstReg, RegState::Define)
2420 .addReg(SecondReg, RegState::Define)
2421 .addReg(BaseReg);
2422 // FIXME: We're converting from LDRi12 to an insn that still
2423 // uses addrmode2, so we need an explicit offset reg. It should
2424 // always by reg0 since we're transforming LDRi12s.
2425 if (!isT2)
2426 MIB.addReg(0);
2427 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
2428 MIB.cloneMergedMemRefs({Op0, Op1});
2429 LLVM_DEBUG(dbgs() << "Formed " << *MIB << "\n");
2430 ++NumLDRDFormed;
2431 } else {
2432 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
2433 .addReg(FirstReg)
2434 .addReg(SecondReg)
2435 .addReg(BaseReg);
2436 // FIXME: We're converting from LDRi12 to an insn that still
2437 // uses addrmode2, so we need an explicit offset reg. It should
2438 // always by reg0 since we're transforming STRi12s.
2439 if (!isT2)
2440 MIB.addReg(0);
2441 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
2442 MIB.cloneMergedMemRefs({Op0, Op1});
2443 LLVM_DEBUG(dbgs() << "Formed " << *MIB << "\n");
2444 ++NumSTRDFormed;
2445 }
2446 MBB->erase(Op0);
2447 MBB->erase(Op1);
2448
2449 if (!isT2) {
2450 // Add register allocation hints to form register pairs.
2451 MRI->setRegAllocationHint(FirstReg, ARMRI::RegPairEven, SecondReg);
2452 MRI->setRegAllocationHint(SecondReg, ARMRI::RegPairOdd, FirstReg);
2453 }
2454 } else {
2455 for (unsigned i = 0; i != NumMove; ++i) {
2456 MachineInstr *Op = Ops.back();
2457 Ops.pop_back();
2458 MBB->splice(InsertPos, MBB, Op);
2459 }
2460 }
2461
2462 NumLdStMoved += NumMove;
2463 RetVal = true;
2464 }
2465 }
2466 }
2467
2468 return RetVal;
2469 }
2470
2471 bool
RescheduleLoadStoreInstrs(MachineBasicBlock * MBB)2472 ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {
2473 bool RetVal = false;
2474
2475 DenseMap<MachineInstr*, unsigned> MI2LocMap;
2476 using MapIt = DenseMap<unsigned, SmallVector<MachineInstr *, 4>>::iterator;
2477 using Base2InstMap = DenseMap<unsigned, SmallVector<MachineInstr *, 4>>;
2478 using BaseVec = SmallVector<unsigned, 4>;
2479 Base2InstMap Base2LdsMap;
2480 Base2InstMap Base2StsMap;
2481 BaseVec LdBases;
2482 BaseVec StBases;
2483
2484 unsigned Loc = 0;
2485 MachineBasicBlock::iterator MBBI = MBB->begin();
2486 MachineBasicBlock::iterator E = MBB->end();
2487 while (MBBI != E) {
2488 for (; MBBI != E; ++MBBI) {
2489 MachineInstr &MI = *MBBI;
2490 if (MI.isCall() || MI.isTerminator()) {
2491 // Stop at barriers.
2492 ++MBBI;
2493 break;
2494 }
2495
2496 if (!MI.isDebugInstr())
2497 MI2LocMap[&MI] = ++Loc;
2498
2499 if (!isMemoryOp(MI))
2500 continue;
2501 Register PredReg;
2502 if (getInstrPredicate(MI, PredReg) != ARMCC::AL)
2503 continue;
2504
2505 int Opc = MI.getOpcode();
2506 bool isLd = isLoadSingle(Opc);
2507 Register Base = MI.getOperand(1).getReg();
2508 int Offset = getMemoryOpOffset(MI);
2509 bool StopHere = false;
2510 auto FindBases = [&] (Base2InstMap &Base2Ops, BaseVec &Bases) {
2511 MapIt BI = Base2Ops.find(Base);
2512 if (BI == Base2Ops.end()) {
2513 Base2Ops[Base].push_back(&MI);
2514 Bases.push_back(Base);
2515 return;
2516 }
2517 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
2518 if (Offset == getMemoryOpOffset(*BI->second[i])) {
2519 StopHere = true;
2520 break;
2521 }
2522 }
2523 if (!StopHere)
2524 BI->second.push_back(&MI);
2525 };
2526
2527 if (isLd)
2528 FindBases(Base2LdsMap, LdBases);
2529 else
2530 FindBases(Base2StsMap, StBases);
2531
2532 if (StopHere) {
2533 // Found a duplicate (a base+offset combination that's seen earlier).
2534 // Backtrack.
2535 --Loc;
2536 break;
2537 }
2538 }
2539
2540 // Re-schedule loads.
2541 for (unsigned i = 0, e = LdBases.size(); i != e; ++i) {
2542 unsigned Base = LdBases[i];
2543 SmallVectorImpl<MachineInstr *> &Lds = Base2LdsMap[Base];
2544 if (Lds.size() > 1)
2545 RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap);
2546 }
2547
2548 // Re-schedule stores.
2549 for (unsigned i = 0, e = StBases.size(); i != e; ++i) {
2550 unsigned Base = StBases[i];
2551 SmallVectorImpl<MachineInstr *> &Sts = Base2StsMap[Base];
2552 if (Sts.size() > 1)
2553 RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap);
2554 }
2555
2556 if (MBBI != E) {
2557 Base2LdsMap.clear();
2558 Base2StsMap.clear();
2559 LdBases.clear();
2560 StBases.clear();
2561 }
2562 }
2563
2564 return RetVal;
2565 }
2566
2567 // Get the Base register operand index from the memory access MachineInst if we
2568 // should attempt to distribute postinc on it. Return -1 if not of a valid
2569 // instruction type. If it returns an index, it is assumed that instruction is a
2570 // r+i indexing mode, and getBaseOperandIndex() + 1 is the Offset index.
getBaseOperandIndex(MachineInstr & MI)2571 static int getBaseOperandIndex(MachineInstr &MI) {
2572 switch (MI.getOpcode()) {
2573 case ARM::MVE_VLDRBS16:
2574 case ARM::MVE_VLDRBS32:
2575 case ARM::MVE_VLDRBU16:
2576 case ARM::MVE_VLDRBU32:
2577 case ARM::MVE_VLDRHS32:
2578 case ARM::MVE_VLDRHU32:
2579 case ARM::MVE_VLDRBU8:
2580 case ARM::MVE_VLDRHU16:
2581 case ARM::MVE_VLDRWU32:
2582 case ARM::MVE_VSTRB16:
2583 case ARM::MVE_VSTRB32:
2584 case ARM::MVE_VSTRH32:
2585 case ARM::MVE_VSTRBU8:
2586 case ARM::MVE_VSTRHU16:
2587 case ARM::MVE_VSTRWU32:
2588 case ARM::t2LDRHi8:
2589 case ARM::t2LDRHi12:
2590 case ARM::t2LDRSHi8:
2591 case ARM::t2LDRSHi12:
2592 case ARM::t2LDRBi8:
2593 case ARM::t2LDRBi12:
2594 case ARM::t2LDRSBi8:
2595 case ARM::t2LDRSBi12:
2596 case ARM::t2STRBi8:
2597 case ARM::t2STRBi12:
2598 case ARM::t2STRHi8:
2599 case ARM::t2STRHi12:
2600 return 1;
2601 case ARM::MVE_VLDRBS16_post:
2602 case ARM::MVE_VLDRBS32_post:
2603 case ARM::MVE_VLDRBU16_post:
2604 case ARM::MVE_VLDRBU32_post:
2605 case ARM::MVE_VLDRHS32_post:
2606 case ARM::MVE_VLDRHU32_post:
2607 case ARM::MVE_VLDRBU8_post:
2608 case ARM::MVE_VLDRHU16_post:
2609 case ARM::MVE_VLDRWU32_post:
2610 case ARM::MVE_VSTRB16_post:
2611 case ARM::MVE_VSTRB32_post:
2612 case ARM::MVE_VSTRH32_post:
2613 case ARM::MVE_VSTRBU8_post:
2614 case ARM::MVE_VSTRHU16_post:
2615 case ARM::MVE_VSTRWU32_post:
2616 case ARM::MVE_VLDRBS16_pre:
2617 case ARM::MVE_VLDRBS32_pre:
2618 case ARM::MVE_VLDRBU16_pre:
2619 case ARM::MVE_VLDRBU32_pre:
2620 case ARM::MVE_VLDRHS32_pre:
2621 case ARM::MVE_VLDRHU32_pre:
2622 case ARM::MVE_VLDRBU8_pre:
2623 case ARM::MVE_VLDRHU16_pre:
2624 case ARM::MVE_VLDRWU32_pre:
2625 case ARM::MVE_VSTRB16_pre:
2626 case ARM::MVE_VSTRB32_pre:
2627 case ARM::MVE_VSTRH32_pre:
2628 case ARM::MVE_VSTRBU8_pre:
2629 case ARM::MVE_VSTRHU16_pre:
2630 case ARM::MVE_VSTRWU32_pre:
2631 return 2;
2632 }
2633 return -1;
2634 }
2635
isPostIndex(MachineInstr & MI)2636 static bool isPostIndex(MachineInstr &MI) {
2637 switch (MI.getOpcode()) {
2638 case ARM::MVE_VLDRBS16_post:
2639 case ARM::MVE_VLDRBS32_post:
2640 case ARM::MVE_VLDRBU16_post:
2641 case ARM::MVE_VLDRBU32_post:
2642 case ARM::MVE_VLDRHS32_post:
2643 case ARM::MVE_VLDRHU32_post:
2644 case ARM::MVE_VLDRBU8_post:
2645 case ARM::MVE_VLDRHU16_post:
2646 case ARM::MVE_VLDRWU32_post:
2647 case ARM::MVE_VSTRB16_post:
2648 case ARM::MVE_VSTRB32_post:
2649 case ARM::MVE_VSTRH32_post:
2650 case ARM::MVE_VSTRBU8_post:
2651 case ARM::MVE_VSTRHU16_post:
2652 case ARM::MVE_VSTRWU32_post:
2653 return true;
2654 }
2655 return false;
2656 }
2657
isPreIndex(MachineInstr & MI)2658 static bool isPreIndex(MachineInstr &MI) {
2659 switch (MI.getOpcode()) {
2660 case ARM::MVE_VLDRBS16_pre:
2661 case ARM::MVE_VLDRBS32_pre:
2662 case ARM::MVE_VLDRBU16_pre:
2663 case ARM::MVE_VLDRBU32_pre:
2664 case ARM::MVE_VLDRHS32_pre:
2665 case ARM::MVE_VLDRHU32_pre:
2666 case ARM::MVE_VLDRBU8_pre:
2667 case ARM::MVE_VLDRHU16_pre:
2668 case ARM::MVE_VLDRWU32_pre:
2669 case ARM::MVE_VSTRB16_pre:
2670 case ARM::MVE_VSTRB32_pre:
2671 case ARM::MVE_VSTRH32_pre:
2672 case ARM::MVE_VSTRBU8_pre:
2673 case ARM::MVE_VSTRHU16_pre:
2674 case ARM::MVE_VSTRWU32_pre:
2675 return true;
2676 }
2677 return false;
2678 }
2679
2680 // Given a memory access Opcode, check that the give Imm would be a valid Offset
2681 // for this instruction (same as isLegalAddressImm), Or if the instruction
2682 // could be easily converted to one where that was valid. For example converting
2683 // t2LDRi12 to t2LDRi8 for negative offsets. Works in conjunction with
2684 // AdjustBaseAndOffset below.
isLegalOrConvertableAddressImm(unsigned Opcode,int Imm,const TargetInstrInfo * TII,int & CodesizeEstimate)2685 static bool isLegalOrConvertableAddressImm(unsigned Opcode, int Imm,
2686 const TargetInstrInfo *TII,
2687 int &CodesizeEstimate) {
2688 if (isLegalAddressImm(Opcode, Imm, TII))
2689 return true;
2690
2691 // We can convert AddrModeT2_i12 to AddrModeT2_i8.
2692 const MCInstrDesc &Desc = TII->get(Opcode);
2693 unsigned AddrMode = (Desc.TSFlags & ARMII::AddrModeMask);
2694 switch (AddrMode) {
2695 case ARMII::AddrModeT2_i12:
2696 CodesizeEstimate += 1;
2697 return std::abs(Imm) < (((1 << 8) * 1) - 1);
2698 }
2699 return false;
2700 }
2701
2702 // Given an MI adjust its address BaseReg to use NewBaseReg and address offset
2703 // by -Offset. This can either happen in-place or be a replacement as MI is
2704 // converted to another instruction type.
AdjustBaseAndOffset(MachineInstr * MI,Register NewBaseReg,int Offset,const TargetInstrInfo * TII)2705 static void AdjustBaseAndOffset(MachineInstr *MI, Register NewBaseReg,
2706 int Offset, const TargetInstrInfo *TII) {
2707 unsigned BaseOp = getBaseOperandIndex(*MI);
2708 MI->getOperand(BaseOp).setReg(NewBaseReg);
2709 int OldOffset = MI->getOperand(BaseOp + 1).getImm();
2710 if (isLegalAddressImm(MI->getOpcode(), OldOffset - Offset, TII))
2711 MI->getOperand(BaseOp + 1).setImm(OldOffset - Offset);
2712 else {
2713 unsigned ConvOpcode;
2714 switch (MI->getOpcode()) {
2715 case ARM::t2LDRHi12:
2716 ConvOpcode = ARM::t2LDRHi8;
2717 break;
2718 case ARM::t2LDRSHi12:
2719 ConvOpcode = ARM::t2LDRSHi8;
2720 break;
2721 case ARM::t2LDRBi12:
2722 ConvOpcode = ARM::t2LDRBi8;
2723 break;
2724 case ARM::t2LDRSBi12:
2725 ConvOpcode = ARM::t2LDRSBi8;
2726 break;
2727 case ARM::t2STRHi12:
2728 ConvOpcode = ARM::t2STRHi8;
2729 break;
2730 case ARM::t2STRBi12:
2731 ConvOpcode = ARM::t2STRBi8;
2732 break;
2733 default:
2734 llvm_unreachable("Unhandled convertable opcode");
2735 }
2736 assert(isLegalAddressImm(ConvOpcode, OldOffset - Offset, TII) &&
2737 "Illegal Address Immediate after convert!");
2738
2739 const MCInstrDesc &MCID = TII->get(ConvOpcode);
2740 BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), MCID)
2741 .add(MI->getOperand(0))
2742 .add(MI->getOperand(1))
2743 .addImm(OldOffset - Offset)
2744 .add(MI->getOperand(3))
2745 .add(MI->getOperand(4))
2746 .cloneMemRefs(*MI);
2747 MI->eraseFromParent();
2748 }
2749 }
2750
createPostIncLoadStore(MachineInstr * MI,int Offset,Register NewReg,const TargetInstrInfo * TII,const TargetRegisterInfo * TRI)2751 static MachineInstr *createPostIncLoadStore(MachineInstr *MI, int Offset,
2752 Register NewReg,
2753 const TargetInstrInfo *TII,
2754 const TargetRegisterInfo *TRI) {
2755 MachineFunction *MF = MI->getMF();
2756 MachineRegisterInfo &MRI = MF->getRegInfo();
2757
2758 unsigned NewOpcode = getPostIndexedLoadStoreOpcode(
2759 MI->getOpcode(), Offset > 0 ? ARM_AM::add : ARM_AM::sub);
2760
2761 const MCInstrDesc &MCID = TII->get(NewOpcode);
2762 // Constrain the def register class
2763 const TargetRegisterClass *TRC = TII->getRegClass(MCID, 0, TRI, *MF);
2764 MRI.constrainRegClass(NewReg, TRC);
2765 // And do the same for the base operand
2766 TRC = TII->getRegClass(MCID, 2, TRI, *MF);
2767 MRI.constrainRegClass(MI->getOperand(1).getReg(), TRC);
2768
2769 unsigned AddrMode = (MCID.TSFlags & ARMII::AddrModeMask);
2770 switch (AddrMode) {
2771 case ARMII::AddrModeT2_i7:
2772 case ARMII::AddrModeT2_i7s2:
2773 case ARMII::AddrModeT2_i7s4:
2774 // Any MVE load/store
2775 return BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), MCID)
2776 .addReg(NewReg, RegState::Define)
2777 .add(MI->getOperand(0))
2778 .add(MI->getOperand(1))
2779 .addImm(Offset)
2780 .add(MI->getOperand(3))
2781 .add(MI->getOperand(4))
2782 .cloneMemRefs(*MI);
2783 case ARMII::AddrModeT2_i8:
2784 if (MI->mayLoad()) {
2785 return BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), MCID)
2786 .add(MI->getOperand(0))
2787 .addReg(NewReg, RegState::Define)
2788 .add(MI->getOperand(1))
2789 .addImm(Offset)
2790 .add(MI->getOperand(3))
2791 .add(MI->getOperand(4))
2792 .cloneMemRefs(*MI);
2793 } else {
2794 return BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), MCID)
2795 .addReg(NewReg, RegState::Define)
2796 .add(MI->getOperand(0))
2797 .add(MI->getOperand(1))
2798 .addImm(Offset)
2799 .add(MI->getOperand(3))
2800 .add(MI->getOperand(4))
2801 .cloneMemRefs(*MI);
2802 }
2803 default:
2804 llvm_unreachable("Unhandled createPostIncLoadStore");
2805 }
2806 }
2807
2808 // Given a Base Register, optimise the load/store uses to attempt to create more
2809 // post-inc accesses and less register moves. We do this by taking zero offset
2810 // loads/stores with an add, and convert them to a postinc load/store of the
2811 // same type. Any subsequent accesses will be adjusted to use and account for
2812 // the post-inc value.
2813 // For example:
2814 // LDR #0 LDR_POSTINC #16
2815 // LDR #4 LDR #-12
2816 // LDR #8 LDR #-8
2817 // LDR #12 LDR #-4
2818 // ADD #16
2819 //
2820 // At the same time if we do not find an increment but do find an existing
2821 // pre/post inc instruction, we can still adjust the offsets of subsequent
2822 // instructions to save the register move that would otherwise be needed for the
2823 // in-place increment.
DistributeIncrements(Register Base)2824 bool ARMPreAllocLoadStoreOpt::DistributeIncrements(Register Base) {
2825 // We are looking for:
2826 // One zero offset load/store that can become postinc
2827 MachineInstr *BaseAccess = nullptr;
2828 MachineInstr *PrePostInc = nullptr;
2829 // An increment that can be folded in
2830 MachineInstr *Increment = nullptr;
2831 // Other accesses after BaseAccess that will need to be updated to use the
2832 // postinc value.
2833 SmallPtrSet<MachineInstr *, 8> OtherAccesses;
2834 for (auto &Use : MRI->use_nodbg_instructions(Base)) {
2835 if (!Increment && getAddSubImmediate(Use) != 0) {
2836 Increment = &Use;
2837 continue;
2838 }
2839
2840 int BaseOp = getBaseOperandIndex(Use);
2841 if (BaseOp == -1)
2842 return false;
2843
2844 if (!Use.getOperand(BaseOp).isReg() ||
2845 Use.getOperand(BaseOp).getReg() != Base)
2846 return false;
2847 if (isPreIndex(Use) || isPostIndex(Use))
2848 PrePostInc = &Use;
2849 else if (Use.getOperand(BaseOp + 1).getImm() == 0)
2850 BaseAccess = &Use;
2851 else
2852 OtherAccesses.insert(&Use);
2853 }
2854
2855 int IncrementOffset;
2856 Register NewBaseReg;
2857 if (BaseAccess && Increment) {
2858 if (PrePostInc || BaseAccess->getParent() != Increment->getParent())
2859 return false;
2860 Register PredReg;
2861 if (Increment->definesRegister(ARM::CPSR) ||
2862 getInstrPredicate(*Increment, PredReg) != ARMCC::AL)
2863 return false;
2864
2865 LLVM_DEBUG(dbgs() << "\nAttempting to distribute increments on VirtualReg "
2866 << Base.virtRegIndex() << "\n");
2867
2868 // Make sure that Increment has no uses before BaseAccess.
2869 for (MachineInstr &Use :
2870 MRI->use_nodbg_instructions(Increment->getOperand(0).getReg())) {
2871 if (!DT->dominates(BaseAccess, &Use) || &Use == BaseAccess) {
2872 LLVM_DEBUG(dbgs() << " BaseAccess doesn't dominate use of increment\n");
2873 return false;
2874 }
2875 }
2876
2877 // Make sure that Increment can be folded into Base
2878 IncrementOffset = getAddSubImmediate(*Increment);
2879 unsigned NewPostIncOpcode = getPostIndexedLoadStoreOpcode(
2880 BaseAccess->getOpcode(), IncrementOffset > 0 ? ARM_AM::add : ARM_AM::sub);
2881 if (!isLegalAddressImm(NewPostIncOpcode, IncrementOffset, TII)) {
2882 LLVM_DEBUG(dbgs() << " Illegal addressing mode immediate on postinc\n");
2883 return false;
2884 }
2885 }
2886 else if (PrePostInc) {
2887 // If we already have a pre/post index load/store then set BaseAccess,
2888 // IncrementOffset and NewBaseReg to the values it already produces,
2889 // allowing us to update and subsequent uses of BaseOp reg with the
2890 // incremented value.
2891 if (Increment)
2892 return false;
2893
2894 LLVM_DEBUG(dbgs() << "\nAttempting to distribute increments on already "
2895 << "indexed VirtualReg " << Base.virtRegIndex() << "\n");
2896 int BaseOp = getBaseOperandIndex(*PrePostInc);
2897 IncrementOffset = PrePostInc->getOperand(BaseOp+1).getImm();
2898 BaseAccess = PrePostInc;
2899 NewBaseReg = PrePostInc->getOperand(0).getReg();
2900 }
2901 else
2902 return false;
2903
2904 // And make sure that the negative value of increment can be added to all
2905 // other offsets after the BaseAccess. We rely on either
2906 // dominates(BaseAccess, OtherAccess) or dominates(OtherAccess, BaseAccess)
2907 // to keep things simple.
2908 // This also adds a simple codesize metric, to detect if an instruction (like
2909 // t2LDRBi12) which can often be shrunk to a thumb1 instruction (tLDRBi)
2910 // cannot because it is converted to something else (t2LDRBi8). We start this
2911 // at -1 for the gain from removing the increment.
2912 SmallPtrSet<MachineInstr *, 4> SuccessorAccesses;
2913 int CodesizeEstimate = -1;
2914 for (auto *Use : OtherAccesses) {
2915 if (DT->dominates(BaseAccess, Use)) {
2916 SuccessorAccesses.insert(Use);
2917 unsigned BaseOp = getBaseOperandIndex(*Use);
2918 if (!isLegalOrConvertableAddressImm(Use->getOpcode(),
2919 Use->getOperand(BaseOp + 1).getImm() -
2920 IncrementOffset,
2921 TII, CodesizeEstimate)) {
2922 LLVM_DEBUG(dbgs() << " Illegal addressing mode immediate on use\n");
2923 return false;
2924 }
2925 } else if (!DT->dominates(Use, BaseAccess)) {
2926 LLVM_DEBUG(
2927 dbgs() << " Unknown dominance relation between Base and Use\n");
2928 return false;
2929 }
2930 }
2931 if (STI->hasMinSize() && CodesizeEstimate > 0) {
2932 LLVM_DEBUG(dbgs() << " Expected to grow instructions under minsize\n");
2933 return false;
2934 }
2935
2936 if (!PrePostInc) {
2937 // Replace BaseAccess with a post inc
2938 LLVM_DEBUG(dbgs() << "Changing: "; BaseAccess->dump());
2939 LLVM_DEBUG(dbgs() << " And : "; Increment->dump());
2940 NewBaseReg = Increment->getOperand(0).getReg();
2941 MachineInstr *BaseAccessPost =
2942 createPostIncLoadStore(BaseAccess, IncrementOffset, NewBaseReg, TII, TRI);
2943 BaseAccess->eraseFromParent();
2944 Increment->eraseFromParent();
2945 (void)BaseAccessPost;
2946 LLVM_DEBUG(dbgs() << " To : "; BaseAccessPost->dump());
2947 }
2948
2949 for (auto *Use : SuccessorAccesses) {
2950 LLVM_DEBUG(dbgs() << "Changing: "; Use->dump());
2951 AdjustBaseAndOffset(Use, NewBaseReg, IncrementOffset, TII);
2952 LLVM_DEBUG(dbgs() << " To : "; Use->dump());
2953 }
2954
2955 // Remove the kill flag from all uses of NewBaseReg, in case any old uses
2956 // remain.
2957 for (MachineOperand &Op : MRI->use_nodbg_operands(NewBaseReg))
2958 Op.setIsKill(false);
2959 return true;
2960 }
2961
DistributeIncrements()2962 bool ARMPreAllocLoadStoreOpt::DistributeIncrements() {
2963 bool Changed = false;
2964 SmallSetVector<Register, 4> Visited;
2965 for (auto &MBB : *MF) {
2966 for (auto &MI : MBB) {
2967 int BaseOp = getBaseOperandIndex(MI);
2968 if (BaseOp == -1 || !MI.getOperand(BaseOp).isReg())
2969 continue;
2970
2971 Register Base = MI.getOperand(BaseOp).getReg();
2972 if (!Base.isVirtual() || Visited.count(Base))
2973 continue;
2974
2975 Visited.insert(Base);
2976 }
2977 }
2978
2979 for (auto Base : Visited)
2980 Changed |= DistributeIncrements(Base);
2981
2982 return Changed;
2983 }
2984
2985 /// Returns an instance of the load / store optimization pass.
createARMLoadStoreOptimizationPass(bool PreAlloc)2986 FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) {
2987 if (PreAlloc)
2988 return new ARMPreAllocLoadStoreOpt();
2989 return new ARMLoadStoreOpt();
2990 }
2991