blob: 62d57f3f4986111549c561a92b447905cd280d0e [file] [log] [blame]
Jia Liub22310f2012-02-18 12:03:15 +00001//===-- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass ------------===//
Evan Cheng10043e22007-01-19 07:51:42 +00002//
3// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Evan Cheng10043e22007-01-19 07:51:42 +00007//
8//===----------------------------------------------------------------------===//
9//
Matthias Braunec50fa62015-06-01 21:26:23 +000010/// \file This file contains a pass that performs load / store related peephole
11/// optimizations. This pass should be run after register allocation.
Evan Cheng10043e22007-01-19 07:51:42 +000012//
13//===----------------------------------------------------------------------===//
14
Evan Cheng10043e22007-01-19 07:51:42 +000015#include "ARM.h"
Evan Cheng2aa91cc2009-08-08 03:20:32 +000016#include "ARMBaseInstrInfo.h"
Craig Topper5fa0caa2012-03-26 00:45:15 +000017#include "ARMBaseRegisterInfo.h"
James Molloy556763d2014-05-16 14:14:30 +000018#include "ARMISelLowering.h"
Evan Chengf030f2d2007-03-07 20:30:36 +000019#include "ARMMachineFunctionInfo.h"
Craig Toppera9253262014-03-22 23:51:00 +000020#include "ARMSubtarget.h"
Evan Chenga20cde32011-07-20 23:34:39 +000021#include "MCTargetDesc/ARMAddressingModes.h"
Eric Christopherae326492015-03-12 22:48:50 +000022#include "ThumbRegisterInfo.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000023#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/ADT/SmallPtrSet.h"
26#include "llvm/ADT/SmallSet.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/ADT/Statistic.h"
Evan Cheng10043e22007-01-19 07:51:42 +000029#include "llvm/CodeGen/MachineBasicBlock.h"
30#include "llvm/CodeGen/MachineFunctionPass.h"
31#include "llvm/CodeGen/MachineInstr.h"
32#include "llvm/CodeGen/MachineInstrBuilder.h"
Evan Cheng185c9ef2009-06-13 09:12:55 +000033#include "llvm/CodeGen/MachineRegisterInfo.h"
Matthias Brauna4a3182d2015-07-10 18:08:49 +000034#include "llvm/CodeGen/RegisterClassInfo.h"
Evan Chenga20cde32011-07-20 23:34:39 +000035#include "llvm/CodeGen/SelectionDAGNodes.h"
Matthias Brauna4a3182d2015-07-10 18:08:49 +000036#include "llvm/CodeGen/LivePhysRegs.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000037#include "llvm/IR/DataLayout.h"
38#include "llvm/IR/DerivedTypes.h"
39#include "llvm/IR/Function.h"
Matthias Brauna4a3182d2015-07-10 18:08:49 +000040#include "llvm/Support/Allocator.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000041#include "llvm/Support/Debug.h"
42#include "llvm/Support/ErrorHandling.h"
Benjamin Kramer799003b2015-03-23 19:32:43 +000043#include "llvm/Support/raw_ostream.h"
Evan Cheng10043e22007-01-19 07:51:42 +000044#include "llvm/Target/TargetInstrInfo.h"
45#include "llvm/Target/TargetMachine.h"
Evan Cheng1283c6a2009-06-15 08:28:29 +000046#include "llvm/Target/TargetRegisterInfo.h"
Evan Cheng10043e22007-01-19 07:51:42 +000047using namespace llvm;
48
Chandler Carruth84e68b22014-04-22 02:41:26 +000049#define DEBUG_TYPE "arm-ldst-opt"
50
Evan Cheng10043e22007-01-19 07:51:42 +000051STATISTIC(NumLDMGened , "Number of ldm instructions generated");
52STATISTIC(NumSTMGened , "Number of stm instructions generated");
Jim Grosbachd7cf55c2009-11-09 00:11:35 +000053STATISTIC(NumVLDMGened, "Number of vldm instructions generated");
54STATISTIC(NumVSTMGened, "Number of vstm instructions generated");
Evan Cheng185c9ef2009-06-13 09:12:55 +000055STATISTIC(NumLdStMoved, "Number of load / store instructions moved");
Evan Cheng0e796032009-06-18 02:04:01 +000056STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation");
57STATISTIC(NumSTRDFormed,"Number of strd created before allocation");
58STATISTIC(NumLDRD2LDM, "Number of ldrd instructions turned back into ldm");
59STATISTIC(NumSTRD2STM, "Number of strd instructions turned back into stm");
60STATISTIC(NumLDRD2LDR, "Number of ldrd instructions turned back into ldr's");
61STATISTIC(NumSTRD2STR, "Number of strd instructions turned back into str's");
Evan Cheng185c9ef2009-06-13 09:12:55 +000062
Matthias Braunf2909122016-03-02 19:20:00 +000063/// This switch disables formation of double/multi instructions that could
64/// potentially lead to (new) alignment traps even with CCR.UNALIGN_TRP
65/// disabled. This can be used to create libraries that are robust even when
66/// users provoke undefined behaviour by supplying misaligned pointers.
67/// \see mayCombineMisaligned()
68static cl::opt<bool>
69AssumeMisalignedLoadStores("arm-assume-misaligned-load-store", cl::Hidden,
70 cl::init(false), cl::desc("Be more conservative in ARM load/store opt"));
71
David Grossd9c1bc92015-07-23 22:12:46 +000072#define ARM_LOAD_STORE_OPT_NAME "ARM load / store optimization pass"
73
Evan Cheng10043e22007-01-19 07:51:42 +000074namespace {
Matthias Braunec50fa62015-06-01 21:26:23 +000075 /// Post- register allocation pass the combine load / store instructions to
76 /// form ldm / stm instructions.
Nick Lewycky02d5f772009-10-25 06:33:48 +000077 struct ARMLoadStoreOpt : public MachineFunctionPass {
Devang Patel8c78a0b2007-05-03 01:11:54 +000078 static char ID;
Matthias Braun8f456fb2016-07-16 02:24:10 +000079 ARMLoadStoreOpt() : MachineFunctionPass(ID) {}
Devang Patel09f162c2007-05-01 21:15:47 +000080
Matthias Brauna4a3182d2015-07-10 18:08:49 +000081 const MachineFunction *MF;
Evan Cheng10043e22007-01-19 07:51:42 +000082 const TargetInstrInfo *TII;
Dan Gohman3a4be0f2008-02-10 18:45:23 +000083 const TargetRegisterInfo *TRI;
Evan Chengc3770ac2011-11-08 21:21:09 +000084 const ARMSubtarget *STI;
James Molloy556763d2014-05-16 14:14:30 +000085 const TargetLowering *TL;
Evan Chengf030f2d2007-03-07 20:30:36 +000086 ARMFunctionInfo *AFI;
Matthias Brauna4a3182d2015-07-10 18:08:49 +000087 LivePhysRegs LiveRegs;
88 RegisterClassInfo RegClassInfo;
89 MachineBasicBlock::const_iterator LiveRegPos;
90 bool LiveRegsValid;
91 bool RegClassInfoValid;
James Molloy92a15072014-05-16 14:11:38 +000092 bool isThumb1, isThumb2;
Evan Cheng10043e22007-01-19 07:51:42 +000093
Craig Topper6bc27bf2014-03-10 02:09:33 +000094 bool runOnMachineFunction(MachineFunction &Fn) override;
Evan Cheng10043e22007-01-19 07:51:42 +000095
Derek Schuff1dbf7a52016-04-04 17:09:25 +000096 MachineFunctionProperties getRequiredProperties() const override {
97 return MachineFunctionProperties().set(
98 MachineFunctionProperties::Property::AllVRegsAllocated);
99 }
100
Craig Topper6bc27bf2014-03-10 02:09:33 +0000101 const char *getPassName() const override {
David Grossd9c1bc92015-07-23 22:12:46 +0000102 return ARM_LOAD_STORE_OPT_NAME;
Evan Cheng10043e22007-01-19 07:51:42 +0000103 }
104
105 private:
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000106 /// A set of load/store MachineInstrs with same base register sorted by
107 /// offset.
Evan Cheng10043e22007-01-19 07:51:42 +0000108 struct MemOpQueueEntry {
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000109 MachineInstr *MI;
110 int Offset; ///< Load/Store offset.
111 unsigned Position; ///< Position as counted from end of basic block.
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +0000112 MemOpQueueEntry(MachineInstr &MI, int Offset, unsigned Position)
113 : MI(&MI), Offset(Offset), Position(Position) {}
Evan Cheng10043e22007-01-19 07:51:42 +0000114 };
115 typedef SmallVector<MemOpQueueEntry,8> MemOpQueue;
Evan Cheng10043e22007-01-19 07:51:42 +0000116
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000117 /// A set of MachineInstrs that fulfill (nearly all) conditions to get
118 /// merged into a LDM/STM.
119 struct MergeCandidate {
120 /// List of instructions ordered by load/store offset.
121 SmallVector<MachineInstr*, 4> Instrs;
122 /// Index in Instrs of the instruction being latest in the schedule.
123 unsigned LatestMIIdx;
124 /// Index in Instrs of the instruction being earliest in the schedule.
125 unsigned EarliestMIIdx;
126 /// Index into the basic block where the merged instruction will be
127 /// inserted. (See MemOpQueueEntry.Position)
128 unsigned InsertPos;
Matthias Braune40d89e2015-07-21 00:18:59 +0000129 /// Whether the instructions can be merged into a ldm/stm instruction.
130 bool CanMergeToLSMulti;
131 /// Whether the instructions can be merged into a ldrd/strd instruction.
132 bool CanMergeToLSDouble;
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000133 };
Matthias Braune40d89e2015-07-21 00:18:59 +0000134 SpecificBumpPtrAllocator<MergeCandidate> Allocator;
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000135 SmallVector<const MergeCandidate*,4> Candidates;
Matthias Brauna50d2202015-07-21 00:19:01 +0000136 SmallVector<MachineInstr*,4> MergeBaseCandidates;
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000137
138 void moveLiveRegsBefore(const MachineBasicBlock &MBB,
139 MachineBasicBlock::const_iterator Before);
140 unsigned findFreeReg(const TargetRegisterClass &RegClass);
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000141 void UpdateBaseRegUses(MachineBasicBlock &MBB,
Benjamin Kramerbdc49562016-06-12 15:39:02 +0000142 MachineBasicBlock::iterator MBBI, const DebugLoc &DL,
143 unsigned Base, unsigned WordOffset,
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000144 ARMCC::CondCodes Pred, unsigned PredReg);
Benjamin Kramerbdc49562016-06-12 15:39:02 +0000145 MachineInstr *CreateLoadStoreMulti(
146 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
147 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
148 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
149 ArrayRef<std::pair<unsigned, bool>> Regs);
150 MachineInstr *CreateLoadStoreDouble(
151 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
152 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
153 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
154 ArrayRef<std::pair<unsigned, bool>> Regs) const;
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000155 void FormCandidates(const MemOpQueue &MemOps);
156 MachineInstr *MergeOpsUpdate(const MergeCandidate &Cand);
Evan Cheng1283c6a2009-06-15 08:28:29 +0000157 bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
158 MachineBasicBlock::iterator &MBBI);
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000159 bool MergeBaseUpdateLoadStore(MachineInstr *MI);
160 bool MergeBaseUpdateLSMultiple(MachineInstr *MI);
Matthias Brauna50d2202015-07-21 00:19:01 +0000161 bool MergeBaseUpdateLSDouble(MachineInstr &MI) const;
Evan Cheng10043e22007-01-19 07:51:42 +0000162 bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
163 bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
Artyom Skrobov2aca0c62015-12-28 21:40:45 +0000164 bool CombineMovBx(MachineBasicBlock &MBB);
Evan Cheng10043e22007-01-19 07:51:42 +0000165 };
Devang Patel8c78a0b2007-05-03 01:11:54 +0000166 char ARMLoadStoreOpt::ID = 0;
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000167}
Evan Cheng10043e22007-01-19 07:51:42 +0000168
Matthias Braun8f456fb2016-07-16 02:24:10 +0000169INITIALIZE_PASS(ARMLoadStoreOpt, "arm-ldst-opt", ARM_LOAD_STORE_OPT_NAME, false,
170 false)
David Grossd9c1bc92015-07-23 22:12:46 +0000171
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +0000172static bool definesCPSR(const MachineInstr &MI) {
173 for (const auto &MO : MI.operands()) {
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000174 if (!MO.isReg())
175 continue;
176 if (MO.isDef() && MO.getReg() == ARM::CPSR && !MO.isDead())
177 // If the instruction has live CPSR def, then it's not safe to fold it
178 // into load / store.
179 return true;
180 }
181
182 return false;
183}
184
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +0000185static int getMemoryOpOffset(const MachineInstr &MI) {
186 unsigned Opcode = MI.getOpcode();
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000187 bool isAM3 = Opcode == ARM::LDRD || Opcode == ARM::STRD;
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +0000188 unsigned NumOperands = MI.getDesc().getNumOperands();
189 unsigned OffField = MI.getOperand(NumOperands - 3).getImm();
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000190
191 if (Opcode == ARM::t2LDRi12 || Opcode == ARM::t2LDRi8 ||
192 Opcode == ARM::t2STRi12 || Opcode == ARM::t2STRi8 ||
193 Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8 ||
194 Opcode == ARM::LDRi12 || Opcode == ARM::STRi12)
195 return OffField;
196
197 // Thumb1 immediate offsets are scaled by 4
Renato Golinb9887ef2015-02-25 14:41:06 +0000198 if (Opcode == ARM::tLDRi || Opcode == ARM::tSTRi ||
199 Opcode == ARM::tLDRspi || Opcode == ARM::tSTRspi)
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000200 return OffField * 4;
201
202 int Offset = isAM3 ? ARM_AM::getAM3Offset(OffField)
203 : ARM_AM::getAM5Offset(OffField) * 4;
204 ARM_AM::AddrOpc Op = isAM3 ? ARM_AM::getAM3Op(OffField)
205 : ARM_AM::getAM5Op(OffField);
206
207 if (Op == ARM_AM::sub)
208 return -Offset;
209
210 return Offset;
211}
212
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000213static const MachineOperand &getLoadStoreBaseOp(const MachineInstr &MI) {
214 return MI.getOperand(1);
215}
216
217static const MachineOperand &getLoadStoreRegOp(const MachineInstr &MI) {
218 return MI.getOperand(0);
219}
220
Matthias Braunfa3872e2015-05-18 20:27:55 +0000221static int getLoadStoreMultipleOpcode(unsigned Opcode, ARM_AM::AMSubMode Mode) {
Evan Cheng10043e22007-01-19 07:51:42 +0000222 switch (Opcode) {
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000223 default: llvm_unreachable("Unhandled opcode!");
Jim Grosbach1e4d9a12010-10-26 22:37:02 +0000224 case ARM::LDRi12:
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000225 ++NumLDMGened;
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000226 switch (Mode) {
227 default: llvm_unreachable("Unhandled submode!");
228 case ARM_AM::ia: return ARM::LDMIA;
229 case ARM_AM::da: return ARM::LDMDA;
230 case ARM_AM::db: return ARM::LDMDB;
231 case ARM_AM::ib: return ARM::LDMIB;
232 }
Jim Grosbach338de3e2010-10-27 23:12:14 +0000233 case ARM::STRi12:
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000234 ++NumSTMGened;
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000235 switch (Mode) {
236 default: llvm_unreachable("Unhandled submode!");
237 case ARM_AM::ia: return ARM::STMIA;
238 case ARM_AM::da: return ARM::STMDA;
239 case ARM_AM::db: return ARM::STMDB;
240 case ARM_AM::ib: return ARM::STMIB;
241 }
James Molloy556763d2014-05-16 14:14:30 +0000242 case ARM::tLDRi:
Renato Golinb9887ef2015-02-25 14:41:06 +0000243 case ARM::tLDRspi:
James Molloy556763d2014-05-16 14:14:30 +0000244 // tLDMIA is writeback-only - unless the base register is in the input
245 // reglist.
246 ++NumLDMGened;
247 switch (Mode) {
248 default: llvm_unreachable("Unhandled submode!");
249 case ARM_AM::ia: return ARM::tLDMIA;
250 }
251 case ARM::tSTRi:
Renato Golinb9887ef2015-02-25 14:41:06 +0000252 case ARM::tSTRspi:
James Molloy556763d2014-05-16 14:14:30 +0000253 // There is no non-writeback tSTMIA either.
254 ++NumSTMGened;
255 switch (Mode) {
256 default: llvm_unreachable("Unhandled submode!");
257 case ARM_AM::ia: return ARM::tSTMIA_UPD;
258 }
Evan Cheng4605e8a2009-07-09 23:11:34 +0000259 case ARM::t2LDRi8:
260 case ARM::t2LDRi12:
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000261 ++NumLDMGened;
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000262 switch (Mode) {
263 default: llvm_unreachable("Unhandled submode!");
264 case ARM_AM::ia: return ARM::t2LDMIA;
265 case ARM_AM::db: return ARM::t2LDMDB;
266 }
Evan Cheng4605e8a2009-07-09 23:11:34 +0000267 case ARM::t2STRi8:
268 case ARM::t2STRi12:
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000269 ++NumSTMGened;
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000270 switch (Mode) {
271 default: llvm_unreachable("Unhandled submode!");
272 case ARM_AM::ia: return ARM::t2STMIA;
273 case ARM_AM::db: return ARM::t2STMDB;
274 }
Jim Grosbachd7cf55c2009-11-09 00:11:35 +0000275 case ARM::VLDRS:
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000276 ++NumVLDMGened;
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000277 switch (Mode) {
278 default: llvm_unreachable("Unhandled submode!");
279 case ARM_AM::ia: return ARM::VLDMSIA;
Owen Andersond6c5a742011-03-29 16:45:53 +0000280 case ARM_AM::db: return 0; // Only VLDMSDB_UPD exists.
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000281 }
Jim Grosbachd7cf55c2009-11-09 00:11:35 +0000282 case ARM::VSTRS:
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000283 ++NumVSTMGened;
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000284 switch (Mode) {
285 default: llvm_unreachable("Unhandled submode!");
286 case ARM_AM::ia: return ARM::VSTMSIA;
Owen Andersond6c5a742011-03-29 16:45:53 +0000287 case ARM_AM::db: return 0; // Only VSTMSDB_UPD exists.
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000288 }
Jim Grosbachd7cf55c2009-11-09 00:11:35 +0000289 case ARM::VLDRD:
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000290 ++NumVLDMGened;
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000291 switch (Mode) {
292 default: llvm_unreachable("Unhandled submode!");
293 case ARM_AM::ia: return ARM::VLDMDIA;
Owen Andersond6c5a742011-03-29 16:45:53 +0000294 case ARM_AM::db: return 0; // Only VLDMDDB_UPD exists.
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000295 }
Jim Grosbachd7cf55c2009-11-09 00:11:35 +0000296 case ARM::VSTRD:
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000297 ++NumVSTMGened;
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000298 switch (Mode) {
299 default: llvm_unreachable("Unhandled submode!");
300 case ARM_AM::ia: return ARM::VSTMDIA;
Owen Andersond6c5a742011-03-29 16:45:53 +0000301 case ARM_AM::db: return 0; // Only VSTMDDB_UPD exists.
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000302 }
Evan Cheng10043e22007-01-19 07:51:42 +0000303 }
Evan Cheng10043e22007-01-19 07:51:42 +0000304}
305
Benjamin Kramer113b2a92015-06-05 14:32:54 +0000306static ARM_AM::AMSubMode getLoadStoreMultipleSubMode(unsigned Opcode) {
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000307 switch (Opcode) {
308 default: llvm_unreachable("Unhandled opcode!");
Bill Wendlingb9bd5942010-11-18 19:44:29 +0000309 case ARM::LDMIA_RET:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000310 case ARM::LDMIA:
Bill Wendling11cc1762010-11-17 19:16:20 +0000311 case ARM::LDMIA_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000312 case ARM::STMIA:
Bill Wendling11cc1762010-11-17 19:16:20 +0000313 case ARM::STMIA_UPD:
James Molloy556763d2014-05-16 14:14:30 +0000314 case ARM::tLDMIA:
315 case ARM::tLDMIA_UPD:
316 case ARM::tSTMIA_UPD:
Bill Wendlingb9bd5942010-11-18 19:44:29 +0000317 case ARM::t2LDMIA_RET:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000318 case ARM::t2LDMIA:
Bill Wendling11cc1762010-11-17 19:16:20 +0000319 case ARM::t2LDMIA_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000320 case ARM::t2STMIA:
Bill Wendling11cc1762010-11-17 19:16:20 +0000321 case ARM::t2STMIA_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000322 case ARM::VLDMSIA:
Bill Wendling11cc1762010-11-17 19:16:20 +0000323 case ARM::VLDMSIA_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000324 case ARM::VSTMSIA:
Bill Wendling11cc1762010-11-17 19:16:20 +0000325 case ARM::VSTMSIA_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000326 case ARM::VLDMDIA:
Bill Wendling11cc1762010-11-17 19:16:20 +0000327 case ARM::VLDMDIA_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000328 case ARM::VSTMDIA:
Bill Wendling11cc1762010-11-17 19:16:20 +0000329 case ARM::VSTMDIA_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000330 return ARM_AM::ia;
331
332 case ARM::LDMDA:
Bill Wendling11cc1762010-11-17 19:16:20 +0000333 case ARM::LDMDA_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000334 case ARM::STMDA:
Bill Wendling11cc1762010-11-17 19:16:20 +0000335 case ARM::STMDA_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000336 return ARM_AM::da;
337
338 case ARM::LDMDB:
Bill Wendling11cc1762010-11-17 19:16:20 +0000339 case ARM::LDMDB_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000340 case ARM::STMDB:
Bill Wendling11cc1762010-11-17 19:16:20 +0000341 case ARM::STMDB_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000342 case ARM::t2LDMDB:
Bill Wendling11cc1762010-11-17 19:16:20 +0000343 case ARM::t2LDMDB_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000344 case ARM::t2STMDB:
Bill Wendling11cc1762010-11-17 19:16:20 +0000345 case ARM::t2STMDB_UPD:
Bill Wendling11cc1762010-11-17 19:16:20 +0000346 case ARM::VLDMSDB_UPD:
Bill Wendling11cc1762010-11-17 19:16:20 +0000347 case ARM::VSTMSDB_UPD:
Bill Wendling11cc1762010-11-17 19:16:20 +0000348 case ARM::VLDMDDB_UPD:
Bill Wendling11cc1762010-11-17 19:16:20 +0000349 case ARM::VSTMDDB_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000350 return ARM_AM::db;
351
352 case ARM::LDMIB:
Bill Wendling11cc1762010-11-17 19:16:20 +0000353 case ARM::LDMIB_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000354 case ARM::STMIB:
Bill Wendling11cc1762010-11-17 19:16:20 +0000355 case ARM::STMIB_UPD:
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000356 return ARM_AM::ib;
357 }
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000358}
359
James Molloy556763d2014-05-16 14:14:30 +0000360static bool isT1i32Load(unsigned Opc) {
Renato Golinb9887ef2015-02-25 14:41:06 +0000361 return Opc == ARM::tLDRi || Opc == ARM::tLDRspi;
James Molloy556763d2014-05-16 14:14:30 +0000362}
363
Evan Cheng71756e72009-08-04 01:43:45 +0000364static bool isT2i32Load(unsigned Opc) {
365 return Opc == ARM::t2LDRi12 || Opc == ARM::t2LDRi8;
366}
367
Evan Cheng4605e8a2009-07-09 23:11:34 +0000368static bool isi32Load(unsigned Opc) {
James Molloy556763d2014-05-16 14:14:30 +0000369 return Opc == ARM::LDRi12 || isT1i32Load(Opc) || isT2i32Load(Opc) ;
370}
371
372static bool isT1i32Store(unsigned Opc) {
Renato Golinb9887ef2015-02-25 14:41:06 +0000373 return Opc == ARM::tSTRi || Opc == ARM::tSTRspi;
Evan Cheng71756e72009-08-04 01:43:45 +0000374}
375
376static bool isT2i32Store(unsigned Opc) {
377 return Opc == ARM::t2STRi12 || Opc == ARM::t2STRi8;
Evan Cheng4605e8a2009-07-09 23:11:34 +0000378}
379
380static bool isi32Store(unsigned Opc) {
James Molloy556763d2014-05-16 14:14:30 +0000381 return Opc == ARM::STRi12 || isT1i32Store(Opc) || isT2i32Store(Opc);
382}
383
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000384static bool isLoadSingle(unsigned Opc) {
385 return isi32Load(Opc) || Opc == ARM::VLDRS || Opc == ARM::VLDRD;
386}
387
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000388static unsigned getImmScale(unsigned Opc) {
389 switch (Opc) {
390 default: llvm_unreachable("Unhandled opcode!");
391 case ARM::tLDRi:
392 case ARM::tSTRi:
Renato Golinb9887ef2015-02-25 14:41:06 +0000393 case ARM::tLDRspi:
394 case ARM::tSTRspi:
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000395 return 1;
396 case ARM::tLDRHi:
397 case ARM::tSTRHi:
398 return 2;
399 case ARM::tLDRBi:
400 case ARM::tSTRBi:
401 return 4;
402 }
403}
404
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000405static unsigned getLSMultipleTransferSize(const MachineInstr *MI) {
406 switch (MI->getOpcode()) {
407 default: return 0;
408 case ARM::LDRi12:
409 case ARM::STRi12:
410 case ARM::tLDRi:
411 case ARM::tSTRi:
412 case ARM::tLDRspi:
413 case ARM::tSTRspi:
414 case ARM::t2LDRi8:
415 case ARM::t2LDRi12:
416 case ARM::t2STRi8:
417 case ARM::t2STRi12:
418 case ARM::VLDRS:
419 case ARM::VSTRS:
420 return 4;
421 case ARM::VLDRD:
422 case ARM::VSTRD:
423 return 8;
424 case ARM::LDMIA:
425 case ARM::LDMDA:
426 case ARM::LDMDB:
427 case ARM::LDMIB:
428 case ARM::STMIA:
429 case ARM::STMDA:
430 case ARM::STMDB:
431 case ARM::STMIB:
432 case ARM::tLDMIA:
433 case ARM::tLDMIA_UPD:
434 case ARM::tSTMIA_UPD:
435 case ARM::t2LDMIA:
436 case ARM::t2LDMDB:
437 case ARM::t2STMIA:
438 case ARM::t2STMDB:
439 case ARM::VLDMSIA:
440 case ARM::VSTMSIA:
441 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 4;
442 case ARM::VLDMDIA:
443 case ARM::VSTMDIA:
444 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 8;
445 }
446}
447
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000448/// Update future uses of the base register with the offset introduced
449/// due to writeback. This function only works on Thumb1.
Benjamin Kramerbdc49562016-06-12 15:39:02 +0000450void ARMLoadStoreOpt::UpdateBaseRegUses(MachineBasicBlock &MBB,
451 MachineBasicBlock::iterator MBBI,
452 const DebugLoc &DL, unsigned Base,
453 unsigned WordOffset,
454 ARMCC::CondCodes Pred,
455 unsigned PredReg) {
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000456 assert(isThumb1 && "Can only update base register uses for Thumb1!");
457 // Start updating any instructions with immediate offsets. Insert a SUB before
458 // the first non-updateable instruction (if any).
459 for (; MBBI != MBB.end(); ++MBBI) {
460 bool InsertSub = false;
461 unsigned Opc = MBBI->getOpcode();
462
463 if (MBBI->readsRegister(Base)) {
464 int Offset;
465 bool IsLoad =
466 Opc == ARM::tLDRi || Opc == ARM::tLDRHi || Opc == ARM::tLDRBi;
467 bool IsStore =
468 Opc == ARM::tSTRi || Opc == ARM::tSTRHi || Opc == ARM::tSTRBi;
469
470 if (IsLoad || IsStore) {
471 // Loads and stores with immediate offsets can be updated, but only if
472 // the new offset isn't negative.
473 // The MachineOperand containing the offset immediate is the last one
474 // before predicates.
475 MachineOperand &MO =
476 MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
477 // The offsets are scaled by 1, 2 or 4 depending on the Opcode.
478 Offset = MO.getImm() - WordOffset * getImmScale(Opc);
479
480 // If storing the base register, it needs to be reset first.
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000481 unsigned InstrSrcReg = getLoadStoreRegOp(*MBBI).getReg();
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000482
483 if (Offset >= 0 && !(IsStore && InstrSrcReg == Base))
484 MO.setImm(Offset);
485 else
486 InsertSub = true;
487
488 } else if ((Opc == ARM::tSUBi8 || Opc == ARM::tADDi8) &&
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +0000489 !definesCPSR(*MBBI)) {
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000490 // SUBS/ADDS using this register, with a dead def of the CPSR.
491 // Merge it with the update; if the merged offset is too large,
492 // insert a new sub instead.
493 MachineOperand &MO =
494 MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
495 Offset = (Opc == ARM::tSUBi8) ?
496 MO.getImm() + WordOffset * 4 :
497 MO.getImm() - WordOffset * 4 ;
498 if (Offset >= 0 && TL->isLegalAddImmediate(Offset)) {
499 // FIXME: Swap ADDS<->SUBS if Offset < 0, erase instruction if
500 // Offset == 0.
501 MO.setImm(Offset);
502 // The base register has now been reset, so exit early.
503 return;
504 } else {
505 InsertSub = true;
506 }
507
508 } else {
509 // Can't update the instruction.
510 InsertSub = true;
511 }
512
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +0000513 } else if (definesCPSR(*MBBI) || MBBI->isCall() || MBBI->isBranch()) {
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000514 // Since SUBS sets the condition flags, we can't place the base reset
515 // after an instruction that has a live CPSR def.
516 // The base register might also contain an argument for a function call.
517 InsertSub = true;
518 }
519
520 if (InsertSub) {
521 // An instruction above couldn't be updated, so insert a sub.
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000522 AddDefaultT1CC(BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base), true)
Matthias Braunaa9fa352015-05-27 05:12:40 +0000523 .addReg(Base).addImm(WordOffset * 4).addImm(Pred).addReg(PredReg);
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000524 return;
525 }
526
John Brawnd86e0042015-06-23 16:02:11 +0000527 if (MBBI->killsRegister(Base) || MBBI->definesRegister(Base))
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000528 // Register got killed. Stop updating.
529 return;
530 }
531
532 // End of block was reached.
533 if (MBB.succ_size() > 0) {
534 // FIXME: Because of a bug, live registers are sometimes missing from
535 // the successor blocks' live-in sets. This means we can't trust that
536 // information and *always* have to reset at the end of a block.
537 // See PR21029.
538 if (MBBI != MBB.end()) --MBBI;
539 AddDefaultT1CC(
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000540 BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base), true)
Matthias Braunaa9fa352015-05-27 05:12:40 +0000541 .addReg(Base).addImm(WordOffset * 4).addImm(Pred).addReg(PredReg);
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000542 }
543}
544
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000545/// Return the first register of class \p RegClass that is not in \p Regs.
546unsigned ARMLoadStoreOpt::findFreeReg(const TargetRegisterClass &RegClass) {
547 if (!RegClassInfoValid) {
548 RegClassInfo.runOnMachineFunction(*MF);
549 RegClassInfoValid = true;
550 }
551
552 for (unsigned Reg : RegClassInfo.getOrder(&RegClass))
553 if (!LiveRegs.contains(Reg))
554 return Reg;
555 return 0;
556}
557
558/// Compute live registers just before instruction \p Before (in normal schedule
559/// direction). Computes backwards so multiple queries in the same block must
560/// come in reverse order.
561void ARMLoadStoreOpt::moveLiveRegsBefore(const MachineBasicBlock &MBB,
562 MachineBasicBlock::const_iterator Before) {
563 // Initialize if we never queried in this block.
564 if (!LiveRegsValid) {
565 LiveRegs.init(TRI);
Matthias Braund1aabb22016-05-03 00:24:32 +0000566 LiveRegs.addLiveOuts(MBB);
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000567 LiveRegPos = MBB.end();
568 LiveRegsValid = true;
569 }
570 // Move backward just before the "Before" position.
571 while (LiveRegPos != Before) {
572 --LiveRegPos;
573 LiveRegs.stepBackward(*LiveRegPos);
574 }
575}
576
577static bool ContainsReg(const ArrayRef<std::pair<unsigned, bool>> &Regs,
578 unsigned Reg) {
579 for (const std::pair<unsigned, bool> &R : Regs)
580 if (R.first == Reg)
581 return true;
582 return false;
583}
584
Matthias Braunec50fa62015-06-01 21:26:23 +0000585/// Create and insert a LDM or STM with Base as base register and registers in
586/// Regs as the register operands that would be loaded / stored. It returns
587/// true if the transformation is done.
Benjamin Kramerbdc49562016-06-12 15:39:02 +0000588MachineInstr *ARMLoadStoreOpt::CreateLoadStoreMulti(
589 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
590 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
591 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
592 ArrayRef<std::pair<unsigned, bool>> Regs) {
Evan Cheng10043e22007-01-19 07:51:42 +0000593 unsigned NumRegs = Regs.size();
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000594 assert(NumRegs > 1);
Evan Cheng10043e22007-01-19 07:51:42 +0000595
Moritz Rotheef9f4d2014-09-16 16:25:07 +0000596 // For Thumb1 targets, it might be necessary to clobber the CPSR to merge.
597 // Compute liveness information for that register to make the decision.
598 bool SafeToClobberCPSR = !isThumb1 ||
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000599 (MBB.computeRegisterLiveness(TRI, ARM::CPSR, InsertBefore, 20) ==
Moritz Rotheef9f4d2014-09-16 16:25:07 +0000600 MachineBasicBlock::LQR_Dead);
601
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000602 bool Writeback = isThumb1; // Thumb1 LDM/STM have base reg writeback.
603
604 // Exception: If the base register is in the input reglist, Thumb1 LDM is
605 // non-writeback.
606 // It's also not possible to merge an STR of the base register in Thumb1.
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000607 if (isThumb1 && isi32Load(Opcode) && ContainsReg(Regs, Base)) {
608 assert(Base != ARM::SP && "Thumb1 does not allow SP in register list");
609 if (Opcode == ARM::tLDRi) {
610 Writeback = false;
611 } else if (Opcode == ARM::tSTRi) {
612 return nullptr;
613 }
614 }
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000615
Evan Cheng10043e22007-01-19 07:51:42 +0000616 ARM_AM::AMSubMode Mode = ARM_AM::ia;
James Molloy556763d2014-05-16 14:14:30 +0000617 // VFP and Thumb2 do not support IB or DA modes. Thumb1 only supports IA.
Bob Wilson13ce07f2010-08-27 23:18:17 +0000618 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
James Molloy556763d2014-05-16 14:14:30 +0000619 bool haveIBAndDA = isNotVFP && !isThumb2 && !isThumb1;
620
James Molloybb73c232014-05-16 14:08:46 +0000621 if (Offset == 4 && haveIBAndDA) {
Evan Cheng10043e22007-01-19 07:51:42 +0000622 Mode = ARM_AM::ib;
James Molloybb73c232014-05-16 14:08:46 +0000623 } else if (Offset == -4 * (int)NumRegs + 4 && haveIBAndDA) {
Evan Cheng10043e22007-01-19 07:51:42 +0000624 Mode = ARM_AM::da;
James Molloy556763d2014-05-16 14:14:30 +0000625 } else if (Offset == -4 * (int)NumRegs && isNotVFP && !isThumb1) {
Bob Wilsonca5af122010-08-27 23:57:52 +0000626 // VLDM/VSTM do not support DB mode without also updating the base reg.
Evan Cheng10043e22007-01-19 07:51:42 +0000627 Mode = ARM_AM::db;
Renato Golinb9887ef2015-02-25 14:41:06 +0000628 } else if (Offset != 0 || Opcode == ARM::tLDRspi || Opcode == ARM::tSTRspi) {
James Molloybb73c232014-05-16 14:08:46 +0000629 // Check if this is a supported opcode before inserting instructions to
Owen Anderson7ac53ad2011-03-29 20:27:38 +0000630 // calculate a new base register.
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000631 if (!getLoadStoreMultipleOpcode(Opcode, Mode)) return nullptr;
Owen Anderson7ac53ad2011-03-29 20:27:38 +0000632
Evan Cheng10043e22007-01-19 07:51:42 +0000633 // If starting offset isn't zero, insert a MI to materialize a new base.
634 // But only do so if it is cost effective, i.e. merging more than two
635 // loads / stores.
636 if (NumRegs <= 2)
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000637 return nullptr;
Evan Cheng10043e22007-01-19 07:51:42 +0000638
Moritz Rotheef9f4d2014-09-16 16:25:07 +0000639 // On Thumb1, it's not worth materializing a new base register without
640 // clobbering the CPSR (i.e. not using ADDS/SUBS).
641 if (!SafeToClobberCPSR)
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000642 return nullptr;
Moritz Rotheef9f4d2014-09-16 16:25:07 +0000643
Evan Cheng10043e22007-01-19 07:51:42 +0000644 unsigned NewBase;
James Molloybb73c232014-05-16 14:08:46 +0000645 if (isi32Load(Opcode)) {
Scott Douglass290183d2015-10-01 11:56:19 +0000646 // If it is a load, then just use one of the destination registers
647 // as the new base. Will no longer be writeback in Thumb1.
Evan Cheng41bc2fd2007-03-06 21:59:20 +0000648 NewBase = Regs[NumRegs-1].first;
Scott Douglass290183d2015-10-01 11:56:19 +0000649 Writeback = false;
James Molloybb73c232014-05-16 14:08:46 +0000650 } else {
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000651 // Find a free register that we can use as scratch register.
652 moveLiveRegsBefore(MBB, InsertBefore);
653 // The merged instruction does not exist yet but will use several Regs if
654 // it is a Store.
655 if (!isLoadSingle(Opcode))
656 for (const std::pair<unsigned, bool> &R : Regs)
657 LiveRegs.addReg(R.first);
658
659 NewBase = findFreeReg(isThumb1 ? ARM::tGPRRegClass : ARM::GPRRegClass);
Evan Cheng41bc2fd2007-03-06 21:59:20 +0000660 if (NewBase == 0)
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000661 return nullptr;
Evan Cheng10043e22007-01-19 07:51:42 +0000662 }
James Molloy556763d2014-05-16 14:14:30 +0000663
664 int BaseOpc =
665 isThumb2 ? ARM::t2ADDri :
Renato Golinb9887ef2015-02-25 14:41:06 +0000666 (isThumb1 && Base == ARM::SP) ? ARM::tADDrSPi :
Moritz Rothdfdda0d2014-08-21 17:11:03 +0000667 (isThumb1 && Offset < 8) ? ARM::tADDi3 :
James Molloy556763d2014-05-16 14:14:30 +0000668 isThumb1 ? ARM::tADDi8 : ARM::ADDri;
669
Evan Cheng10043e22007-01-19 07:51:42 +0000670 if (Offset < 0) {
Moritz Rothdfdda0d2014-08-21 17:11:03 +0000671 Offset = - Offset;
James Molloy556763d2014-05-16 14:14:30 +0000672 BaseOpc =
673 isThumb2 ? ARM::t2SUBri :
Renato Golinb9887ef2015-02-25 14:41:06 +0000674 (isThumb1 && Offset < 8 && Base != ARM::SP) ? ARM::tSUBi3 :
James Molloy556763d2014-05-16 14:14:30 +0000675 isThumb1 ? ARM::tSUBi8 : ARM::SUBri;
Evan Cheng10043e22007-01-19 07:51:42 +0000676 }
Evan Cheng41bc2fd2007-03-06 21:59:20 +0000677
James Molloy556763d2014-05-16 14:14:30 +0000678 if (!TL->isLegalAddImmediate(Offset))
679 // FIXME: Try add with register operand?
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000680 return nullptr; // Probably not worth it then.
681
682 // We can only append a kill flag to the add/sub input if the value is not
683 // used in the register list of the stm as well.
684 bool KillOldBase = BaseKill &&
685 (!isi32Store(Opcode) || !ContainsReg(Regs, Base));
James Molloy556763d2014-05-16 14:14:30 +0000686
687 if (isThumb1) {
Moritz Rothdfdda0d2014-08-21 17:11:03 +0000688 // Thumb1: depending on immediate size, use either
Moritz Rotheef9f4d2014-09-16 16:25:07 +0000689 // ADDS NewBase, Base, #imm3
Moritz Rothdfdda0d2014-08-21 17:11:03 +0000690 // or
Moritz Rotheef9f4d2014-09-16 16:25:07 +0000691 // MOV NewBase, Base
692 // ADDS NewBase, #imm8.
Renato Golinb9887ef2015-02-25 14:41:06 +0000693 if (Base != NewBase &&
694 (BaseOpc == ARM::tADDi8 || BaseOpc == ARM::tSUBi8)) {
James Molloy556763d2014-05-16 14:14:30 +0000695 // Need to insert a MOV to the new base first.
Jonathan Roelofs229eb4c2015-01-21 22:39:43 +0000696 if (isARMLowRegister(NewBase) && isARMLowRegister(Base) &&
Eric Christopher1b21f002015-01-29 00:19:33 +0000697 !STI->hasV6Ops()) {
Jonathan Roelofs229eb4c2015-01-21 22:39:43 +0000698 // thumbv4t doesn't have lo->lo copies, and we can't predicate tMOVSr
699 if (Pred != ARMCC::AL)
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000700 return nullptr;
701 BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVSr), NewBase)
702 .addReg(Base, getKillRegState(KillOldBase));
Jonathan Roelofs229eb4c2015-01-21 22:39:43 +0000703 } else
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000704 BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVr), NewBase)
705 .addReg(Base, getKillRegState(KillOldBase))
Jonathan Roelofs229eb4c2015-01-21 22:39:43 +0000706 .addImm(Pred).addReg(PredReg);
707
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000708 // The following ADDS/SUBS becomes an update.
Moritz Rothdfdda0d2014-08-21 17:11:03 +0000709 Base = NewBase;
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000710 KillOldBase = true;
James Molloy556763d2014-05-16 14:14:30 +0000711 }
Renato Golinb9887ef2015-02-25 14:41:06 +0000712 if (BaseOpc == ARM::tADDrSPi) {
713 assert(Offset % 4 == 0 && "tADDrSPi offset is scaled by 4");
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000714 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
715 .addReg(Base, getKillRegState(KillOldBase)).addImm(Offset/4)
Renato Golinb9887ef2015-02-25 14:41:06 +0000716 .addImm(Pred).addReg(PredReg);
717 } else
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000718 AddDefaultT1CC(
719 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase), true)
720 .addReg(Base, getKillRegState(KillOldBase)).addImm(Offset)
Renato Golinb9887ef2015-02-25 14:41:06 +0000721 .addImm(Pred).addReg(PredReg);
James Molloy556763d2014-05-16 14:14:30 +0000722 } else {
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000723 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
724 .addReg(Base, getKillRegState(KillOldBase)).addImm(Offset)
James Molloy556763d2014-05-16 14:14:30 +0000725 .addImm(Pred).addReg(PredReg).addReg(0);
726 }
Evan Cheng10043e22007-01-19 07:51:42 +0000727 Base = NewBase;
James Molloybb73c232014-05-16 14:08:46 +0000728 BaseKill = true; // New base is always killed straight away.
Evan Cheng10043e22007-01-19 07:51:42 +0000729 }
730
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000731 bool isDef = isLoadSingle(Opcode);
James Molloy556763d2014-05-16 14:14:30 +0000732
733 // Get LS multiple opcode. Note that for Thumb1 this might be an opcode with
734 // base register writeback.
Bill Wendlinga68e3a52010-11-16 01:16:36 +0000735 Opcode = getLoadStoreMultipleOpcode(Opcode, Mode);
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000736 if (!Opcode)
737 return nullptr;
James Molloy556763d2014-05-16 14:14:30 +0000738
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000739 // Check if a Thumb1 LDM/STM merge is safe. This is the case if:
740 // - There is no writeback (LDM of base register),
741 // - the base register is killed by the merged instruction,
742 // - or it's safe to overwrite the condition flags, i.e. to insert a SUBS
743 // to reset the base register.
744 // Otherwise, don't merge.
745 // It's safe to return here since the code to materialize a new base register
746 // above is also conditional on SafeToClobberCPSR.
747 if (isThumb1 && !SafeToClobberCPSR && Writeback && !BaseKill)
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000748 return nullptr;
Moritz Roth8f376562014-08-15 17:00:30 +0000749
James Molloy556763d2014-05-16 14:14:30 +0000750 MachineInstrBuilder MIB;
751
752 if (Writeback) {
Scott Douglass290183d2015-10-01 11:56:19 +0000753 assert(isThumb1 && "expected Writeback only inThumb1");
754 if (Opcode == ARM::tLDMIA) {
755 assert(!(ContainsReg(Regs, Base)) && "Thumb1 can't LDM ! with Base in Regs");
James Molloy556763d2014-05-16 14:14:30 +0000756 // Update tLDMIA with writeback if necessary.
757 Opcode = ARM::tLDMIA_UPD;
Scott Douglass290183d2015-10-01 11:56:19 +0000758 }
James Molloy556763d2014-05-16 14:14:30 +0000759
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000760 MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
James Molloy556763d2014-05-16 14:14:30 +0000761
762 // Thumb1: we might need to set base writeback when building the MI.
763 MIB.addReg(Base, getDefRegState(true))
764 .addReg(Base, getKillRegState(BaseKill));
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000765
766 // The base isn't dead after a merged instruction with writeback.
767 // Insert a sub instruction after the newly formed instruction to reset.
768 if (!BaseKill)
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000769 UpdateBaseRegUses(MBB, InsertBefore, DL, Base, NumRegs, Pred, PredReg);
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000770
James Molloy556763d2014-05-16 14:14:30 +0000771 } else {
772 // No writeback, simply build the MachineInstr.
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000773 MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
James Molloy556763d2014-05-16 14:14:30 +0000774 MIB.addReg(Base, getKillRegState(BaseKill));
775 }
776
777 MIB.addImm(Pred).addReg(PredReg);
778
Matthias Braunaa9fa352015-05-27 05:12:40 +0000779 for (const std::pair<unsigned, bool> &R : Regs)
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000780 MIB.addReg(R.first, getDefRegState(isDef) | getKillRegState(R.second));
Evan Cheng10043e22007-01-19 07:51:42 +0000781
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000782 return MIB.getInstr();
Tim Northover569f69d2013-10-10 09:28:20 +0000783}
784
Benjamin Kramerbdc49562016-06-12 15:39:02 +0000785MachineInstr *ARMLoadStoreOpt::CreateLoadStoreDouble(
786 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
787 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
788 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
789 ArrayRef<std::pair<unsigned, bool>> Regs) const {
Matthias Braune40d89e2015-07-21 00:18:59 +0000790 bool IsLoad = isi32Load(Opcode);
791 assert((IsLoad || isi32Store(Opcode)) && "Must have integer load or store");
792 unsigned LoadStoreOpcode = IsLoad ? ARM::t2LDRDi8 : ARM::t2STRDi8;
793
794 assert(Regs.size() == 2);
795 MachineInstrBuilder MIB = BuildMI(MBB, InsertBefore, DL,
796 TII->get(LoadStoreOpcode));
797 if (IsLoad) {
798 MIB.addReg(Regs[0].first, RegState::Define)
799 .addReg(Regs[1].first, RegState::Define);
800 } else {
801 MIB.addReg(Regs[0].first, getKillRegState(Regs[0].second))
802 .addReg(Regs[1].first, getKillRegState(Regs[1].second));
803 }
804 MIB.addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
805 return MIB.getInstr();
806}
807
Matthias Braunec50fa62015-06-01 21:26:23 +0000808/// Call MergeOps and update MemOps and merges accordingly on success.
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000809MachineInstr *ARMLoadStoreOpt::MergeOpsUpdate(const MergeCandidate &Cand) {
810 const MachineInstr *First = Cand.Instrs.front();
811 unsigned Opcode = First->getOpcode();
812 bool IsLoad = isLoadSingle(Opcode);
Evan Cheng1fb4de82010-06-21 21:21:14 +0000813 SmallVector<std::pair<unsigned, bool>, 8> Regs;
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000814 SmallVector<unsigned, 4> ImpDefs;
815 DenseSet<unsigned> KilledRegs;
Pete Coopere3c81612015-07-16 00:09:18 +0000816 DenseSet<unsigned> UsedRegs;
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000817 // Determine list of registers and list of implicit super-register defs.
818 for (const MachineInstr *MI : Cand.Instrs) {
819 const MachineOperand &MO = getLoadStoreRegOp(*MI);
820 unsigned Reg = MO.getReg();
821 bool IsKill = MO.isKill();
822 if (IsKill)
823 KilledRegs.insert(Reg);
824 Regs.push_back(std::make_pair(Reg, IsKill));
Pete Coopere3c81612015-07-16 00:09:18 +0000825 UsedRegs.insert(Reg);
Jakob Stoklund Olesencdee3262012-03-28 22:50:56 +0000826
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000827 if (IsLoad) {
828 // Collect any implicit defs of super-registers, after merging we can't
829 // be sure anymore that we properly preserved these live ranges and must
830 // removed these implicit operands.
831 for (const MachineOperand &MO : MI->implicit_operands()) {
832 if (!MO.isReg() || !MO.isDef() || MO.isDead())
833 continue;
834 assert(MO.isImplicit());
835 unsigned DefReg = MO.getReg();
836
837 if (std::find(ImpDefs.begin(), ImpDefs.end(), DefReg) != ImpDefs.end())
838 continue;
839 // We can ignore cases where the super-reg is read and written.
840 if (MI->readsRegister(DefReg))
841 continue;
Jakob Stoklund Olesencdee3262012-03-28 22:50:56 +0000842 ImpDefs.push_back(DefReg);
Evan Cheng1fb4de82010-06-21 21:21:14 +0000843 }
844 }
Jakob Stoklund Olesen655e4e62009-12-23 21:28:23 +0000845 }
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000846
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000847 // Attempt the merge.
848 typedef MachineBasicBlock::iterator iterator;
849 MachineInstr *LatestMI = Cand.Instrs[Cand.LatestMIIdx];
850 iterator InsertBefore = std::next(iterator(LatestMI));
851 MachineBasicBlock &MBB = *LatestMI->getParent();
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +0000852 unsigned Offset = getMemoryOpOffset(*First);
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000853 unsigned Base = getLoadStoreBaseOp(*First).getReg();
854 bool BaseKill = LatestMI->killsRegister(Base);
855 unsigned PredReg = 0;
Duncan P. N. Exon Smith6307eb52016-02-23 02:46:52 +0000856 ARMCC::CondCodes Pred = getInstrPredicate(*First, PredReg);
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000857 DebugLoc DL = First->getDebugLoc();
Matthias Braune40d89e2015-07-21 00:18:59 +0000858 MachineInstr *Merged = nullptr;
859 if (Cand.CanMergeToLSDouble)
860 Merged = CreateLoadStoreDouble(MBB, InsertBefore, Offset, Base, BaseKill,
861 Opcode, Pred, PredReg, DL, Regs);
862 if (!Merged && Cand.CanMergeToLSMulti)
863 Merged = CreateLoadStoreMulti(MBB, InsertBefore, Offset, Base, BaseKill,
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000864 Opcode, Pred, PredReg, DL, Regs);
865 if (!Merged)
866 return nullptr;
867
868 // Determine earliest instruction that will get removed. We then keep an
869 // iterator just above it so the following erases don't invalidated it.
870 iterator EarliestI(Cand.Instrs[Cand.EarliestMIIdx]);
871 bool EarliestAtBegin = false;
872 if (EarliestI == MBB.begin()) {
873 EarliestAtBegin = true;
874 } else {
875 EarliestI = std::prev(EarliestI);
Moritz Rothf5d0c7c2014-09-24 16:35:50 +0000876 }
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000877
878 // Remove instructions which have been merged.
879 for (MachineInstr *MI : Cand.Instrs)
880 MBB.erase(MI);
881
882 // Determine range between the earliest removed instruction and the new one.
883 if (EarliestAtBegin)
884 EarliestI = MBB.begin();
885 else
886 EarliestI = std::next(EarliestI);
887 auto FixupRange = make_range(EarliestI, iterator(Merged));
888
889 if (isLoadSingle(Opcode)) {
890 // If the previous loads defined a super-reg, then we have to mark earlier
891 // operands undef; Replicate the super-reg def on the merged instruction.
892 for (MachineInstr &MI : FixupRange) {
893 for (unsigned &ImpDefReg : ImpDefs) {
894 for (MachineOperand &MO : MI.implicit_operands()) {
895 if (!MO.isReg() || MO.getReg() != ImpDefReg)
896 continue;
897 if (MO.readsReg())
898 MO.setIsUndef();
899 else if (MO.isDef())
900 ImpDefReg = 0;
901 }
902 }
903 }
904
905 MachineInstrBuilder MIB(*Merged->getParent()->getParent(), Merged);
906 for (unsigned ImpDef : ImpDefs)
907 MIB.addReg(ImpDef, RegState::ImplicitDefine);
908 } else {
909 // Remove kill flags: We are possibly storing the values later now.
910 assert(isi32Store(Opcode) || Opcode == ARM::VSTRS || Opcode == ARM::VSTRD);
911 for (MachineInstr &MI : FixupRange) {
912 for (MachineOperand &MO : MI.uses()) {
913 if (!MO.isReg() || !MO.isKill())
914 continue;
Pete Coopere3c81612015-07-16 00:09:18 +0000915 if (UsedRegs.count(MO.getReg()))
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000916 MO.setIsKill(false);
917 }
918 }
919 assert(ImpDefs.empty());
920 }
921
922 return Merged;
Jakob Stoklund Olesen655e4e62009-12-23 21:28:23 +0000923}
924
Matthias Braune40d89e2015-07-21 00:18:59 +0000925static bool isValidLSDoubleOffset(int Offset) {
926 unsigned Value = abs(Offset);
927 // t2LDRDi8/t2STRDi8 supports an 8 bit immediate which is internally
928 // multiplied by 4.
929 return (Value % 4) == 0 && Value < 1024;
930}
931
Matthias Braunf2909122016-03-02 19:20:00 +0000932/// Return true for loads/stores that can be combined to a double/multi
933/// operation without increasing the requirements for alignment.
934static bool mayCombineMisaligned(const TargetSubtargetInfo &STI,
935 const MachineInstr &MI) {
936 // vldr/vstr trap on misaligned pointers anyway, forming vldm makes no
937 // difference.
938 unsigned Opcode = MI.getOpcode();
939 if (!isi32Load(Opcode) && !isi32Store(Opcode))
940 return true;
941
942 // Stack pointer alignment is out of the programmers control so we can trust
943 // SP-relative loads/stores.
944 if (getLoadStoreBaseOp(MI).getReg() == ARM::SP &&
945 STI.getFrameLowering()->getTransientStackAlignment() >= 4)
946 return true;
947 return false;
948}
949
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000950/// Find candidates for load/store multiple merge in list of MemOpQueueEntries.
951void ARMLoadStoreOpt::FormCandidates(const MemOpQueue &MemOps) {
952 const MachineInstr *FirstMI = MemOps[0].MI;
953 unsigned Opcode = FirstMI->getOpcode();
Bob Wilson13ce07f2010-08-27 23:18:17 +0000954 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000955 unsigned Size = getLSMultipleTransferSize(FirstMI);
Evan Cheng0f7cbe82007-05-15 01:29:07 +0000956
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000957 unsigned SIndex = 0;
958 unsigned EIndex = MemOps.size();
959 do {
960 // Look at the first instruction.
961 const MachineInstr *MI = MemOps[SIndex].MI;
962 int Offset = MemOps[SIndex].Offset;
963 const MachineOperand &PMO = getLoadStoreRegOp(*MI);
964 unsigned PReg = PMO.getReg();
965 unsigned PRegNum = PMO.isUndef() ? UINT_MAX : TRI->getEncodingValue(PReg);
966 unsigned Latest = SIndex;
967 unsigned Earliest = SIndex;
968 unsigned Count = 1;
Matthias Braune40d89e2015-07-21 00:18:59 +0000969 bool CanMergeToLSDouble =
970 STI->isThumb2() && isNotVFP && isValidLSDoubleOffset(Offset);
971 // ARM errata 602117: LDRD with base in list may result in incorrect base
972 // register when interrupted or faulted.
973 if (STI->isCortexM3() && isi32Load(Opcode) &&
974 PReg == getLoadStoreBaseOp(*MI).getReg())
975 CanMergeToLSDouble = false;
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000976
Matthias Braune40d89e2015-07-21 00:18:59 +0000977 bool CanMergeToLSMulti = true;
978 // On swift vldm/vstm starting with an odd register number as that needs
979 // more uops than single vldrs.
Diana Picus4879b052016-07-06 09:22:23 +0000980 if (STI->hasSlowOddRegister() && !isNotVFP && (PRegNum % 2) == 1)
Matthias Braune40d89e2015-07-21 00:18:59 +0000981 CanMergeToLSMulti = false;
982
983 // LDRD/STRD do not allow SP/PC. LDM/STM do not support it or have it
984 // deprecated; LDM to PC is fine but cannot happen here.
985 if (PReg == ARM::SP || PReg == ARM::PC)
986 CanMergeToLSMulti = CanMergeToLSDouble = false;
987
Matthias Braunf2909122016-03-02 19:20:00 +0000988 // Should we be conservative?
989 if (AssumeMisalignedLoadStores && !mayCombineMisaligned(*STI, *MI))
990 CanMergeToLSMulti = CanMergeToLSDouble = false;
991
Matthias Braune40d89e2015-07-21 00:18:59 +0000992 // Merge following instructions where possible.
Matthias Brauna4a3182d2015-07-10 18:08:49 +0000993 for (unsigned I = SIndex+1; I < EIndex; ++I, ++Count) {
994 int NewOffset = MemOps[I].Offset;
995 if (NewOffset != Offset + (int)Size)
996 break;
997 const MachineOperand &MO = getLoadStoreRegOp(*MemOps[I].MI);
998 unsigned Reg = MO.getReg();
Matthias Braune40d89e2015-07-21 00:18:59 +0000999 if (Reg == ARM::SP || Reg == ARM::PC)
Matthias Braun731e3592015-07-20 23:17:20 +00001000 break;
1001
Matthias Braune40d89e2015-07-21 00:18:59 +00001002 // See if the current load/store may be part of a multi load/store.
1003 unsigned RegNum = MO.isUndef() ? UINT_MAX : TRI->getEncodingValue(Reg);
1004 bool PartOfLSMulti = CanMergeToLSMulti;
1005 if (PartOfLSMulti) {
1006 // Register numbers must be in ascending order.
1007 if (RegNum <= PRegNum)
1008 PartOfLSMulti = false;
1009 // For VFP / NEON load/store multiples, the registers must be
1010 // consecutive and within the limit on the number of registers per
1011 // instruction.
1012 else if (!isNotVFP && RegNum != PRegNum+1)
1013 PartOfLSMulti = false;
1014 }
1015 // See if the current load/store may be part of a double load/store.
1016 bool PartOfLSDouble = CanMergeToLSDouble && Count <= 1;
1017
1018 if (!PartOfLSMulti && !PartOfLSDouble)
1019 break;
1020 CanMergeToLSMulti &= PartOfLSMulti;
1021 CanMergeToLSDouble &= PartOfLSDouble;
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001022 // Track MemOp with latest and earliest position (Positions are
1023 // counted in reverse).
1024 unsigned Position = MemOps[I].Position;
1025 if (Position < MemOps[Latest].Position)
1026 Latest = I;
1027 else if (Position > MemOps[Earliest].Position)
1028 Earliest = I;
1029 // Prepare for next MemOp.
Evan Cheng10043e22007-01-19 07:51:42 +00001030 Offset += Size;
Evan Cheng10043e22007-01-19 07:51:42 +00001031 PRegNum = RegNum;
Evan Cheng10043e22007-01-19 07:51:42 +00001032 }
1033
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001034 // Form a candidate from the Ops collected so far.
Matthias Braune40d89e2015-07-21 00:18:59 +00001035 MergeCandidate *Candidate = new(Allocator.Allocate()) MergeCandidate;
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001036 for (unsigned C = SIndex, CE = SIndex + Count; C < CE; ++C)
1037 Candidate->Instrs.push_back(MemOps[C].MI);
1038 Candidate->LatestMIIdx = Latest - SIndex;
1039 Candidate->EarliestMIIdx = Earliest - SIndex;
1040 Candidate->InsertPos = MemOps[Latest].Position;
Matthias Braune40d89e2015-07-21 00:18:59 +00001041 if (Count == 1)
1042 CanMergeToLSMulti = CanMergeToLSDouble = false;
1043 Candidate->CanMergeToLSMulti = CanMergeToLSMulti;
1044 Candidate->CanMergeToLSDouble = CanMergeToLSDouble;
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001045 Candidates.push_back(Candidate);
1046 // Continue after the chain.
1047 SIndex += Count;
1048 } while (SIndex < EIndex);
Evan Cheng10043e22007-01-19 07:51:42 +00001049}
1050
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001051static unsigned getUpdatingLSMultipleOpcode(unsigned Opc,
1052 ARM_AM::AMSubMode Mode) {
Bob Wilson947f04b2010-03-13 01:08:20 +00001053 switch (Opc) {
Bob Wilson947f04b2010-03-13 01:08:20 +00001054 default: llvm_unreachable("Unhandled opcode!");
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001055 case ARM::LDMIA:
1056 case ARM::LDMDA:
1057 case ARM::LDMDB:
1058 case ARM::LDMIB:
1059 switch (Mode) {
1060 default: llvm_unreachable("Unhandled submode!");
1061 case ARM_AM::ia: return ARM::LDMIA_UPD;
1062 case ARM_AM::ib: return ARM::LDMIB_UPD;
1063 case ARM_AM::da: return ARM::LDMDA_UPD;
1064 case ARM_AM::db: return ARM::LDMDB_UPD;
1065 }
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001066 case ARM::STMIA:
1067 case ARM::STMDA:
1068 case ARM::STMDB:
1069 case ARM::STMIB:
1070 switch (Mode) {
1071 default: llvm_unreachable("Unhandled submode!");
1072 case ARM_AM::ia: return ARM::STMIA_UPD;
1073 case ARM_AM::ib: return ARM::STMIB_UPD;
1074 case ARM_AM::da: return ARM::STMDA_UPD;
1075 case ARM_AM::db: return ARM::STMDB_UPD;
1076 }
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001077 case ARM::t2LDMIA:
1078 case ARM::t2LDMDB:
1079 switch (Mode) {
1080 default: llvm_unreachable("Unhandled submode!");
1081 case ARM_AM::ia: return ARM::t2LDMIA_UPD;
1082 case ARM_AM::db: return ARM::t2LDMDB_UPD;
1083 }
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001084 case ARM::t2STMIA:
1085 case ARM::t2STMDB:
1086 switch (Mode) {
1087 default: llvm_unreachable("Unhandled submode!");
1088 case ARM_AM::ia: return ARM::t2STMIA_UPD;
1089 case ARM_AM::db: return ARM::t2STMDB_UPD;
1090 }
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001091 case ARM::VLDMSIA:
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001092 switch (Mode) {
1093 default: llvm_unreachable("Unhandled submode!");
1094 case ARM_AM::ia: return ARM::VLDMSIA_UPD;
1095 case ARM_AM::db: return ARM::VLDMSDB_UPD;
1096 }
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001097 case ARM::VLDMDIA:
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001098 switch (Mode) {
1099 default: llvm_unreachable("Unhandled submode!");
1100 case ARM_AM::ia: return ARM::VLDMDIA_UPD;
1101 case ARM_AM::db: return ARM::VLDMDDB_UPD;
1102 }
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001103 case ARM::VSTMSIA:
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001104 switch (Mode) {
1105 default: llvm_unreachable("Unhandled submode!");
1106 case ARM_AM::ia: return ARM::VSTMSIA_UPD;
1107 case ARM_AM::db: return ARM::VSTMSDB_UPD;
1108 }
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001109 case ARM::VSTMDIA:
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001110 switch (Mode) {
1111 default: llvm_unreachable("Unhandled submode!");
1112 case ARM_AM::ia: return ARM::VSTMDIA_UPD;
1113 case ARM_AM::db: return ARM::VSTMDDB_UPD;
1114 }
Bob Wilson947f04b2010-03-13 01:08:20 +00001115 }
Bob Wilson947f04b2010-03-13 01:08:20 +00001116}
1117
Matthias Brauna50d2202015-07-21 00:19:01 +00001118/// Check if the given instruction increments or decrements a register and
1119/// return the amount it is incremented/decremented. Returns 0 if the CPSR flags
1120/// generated by the instruction are possibly read as well.
1121static int isIncrementOrDecrement(const MachineInstr &MI, unsigned Reg,
1122 ARMCC::CondCodes Pred, unsigned PredReg) {
1123 bool CheckCPSRDef;
1124 int Scale;
1125 switch (MI.getOpcode()) {
1126 case ARM::tADDi8: Scale = 4; CheckCPSRDef = true; break;
1127 case ARM::tSUBi8: Scale = -4; CheckCPSRDef = true; break;
1128 case ARM::t2SUBri:
1129 case ARM::SUBri: Scale = -1; CheckCPSRDef = true; break;
1130 case ARM::t2ADDri:
1131 case ARM::ADDri: Scale = 1; CheckCPSRDef = true; break;
1132 case ARM::tADDspi: Scale = 4; CheckCPSRDef = false; break;
1133 case ARM::tSUBspi: Scale = -4; CheckCPSRDef = false; break;
1134 default: return 0;
1135 }
1136
1137 unsigned MIPredReg;
1138 if (MI.getOperand(0).getReg() != Reg ||
1139 MI.getOperand(1).getReg() != Reg ||
Duncan P. N. Exon Smith6307eb52016-02-23 02:46:52 +00001140 getInstrPredicate(MI, MIPredReg) != Pred ||
Matthias Brauna50d2202015-07-21 00:19:01 +00001141 MIPredReg != PredReg)
1142 return 0;
1143
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00001144 if (CheckCPSRDef && definesCPSR(MI))
Matthias Brauna50d2202015-07-21 00:19:01 +00001145 return 0;
1146 return MI.getOperand(2).getImm() * Scale;
1147}
1148
1149/// Searches for an increment or decrement of \p Reg before \p MBBI.
1150static MachineBasicBlock::iterator
1151findIncDecBefore(MachineBasicBlock::iterator MBBI, unsigned Reg,
1152 ARMCC::CondCodes Pred, unsigned PredReg, int &Offset) {
1153 Offset = 0;
1154 MachineBasicBlock &MBB = *MBBI->getParent();
1155 MachineBasicBlock::iterator BeginMBBI = MBB.begin();
1156 MachineBasicBlock::iterator EndMBBI = MBB.end();
1157 if (MBBI == BeginMBBI)
1158 return EndMBBI;
1159
1160 // Skip debug values.
1161 MachineBasicBlock::iterator PrevMBBI = std::prev(MBBI);
1162 while (PrevMBBI->isDebugValue() && PrevMBBI != BeginMBBI)
1163 --PrevMBBI;
1164
1165 Offset = isIncrementOrDecrement(*PrevMBBI, Reg, Pred, PredReg);
1166 return Offset == 0 ? EndMBBI : PrevMBBI;
1167}
1168
1169/// Searches for a increment or decrement of \p Reg after \p MBBI.
1170static MachineBasicBlock::iterator
1171findIncDecAfter(MachineBasicBlock::iterator MBBI, unsigned Reg,
1172 ARMCC::CondCodes Pred, unsigned PredReg, int &Offset) {
1173 Offset = 0;
1174 MachineBasicBlock &MBB = *MBBI->getParent();
1175 MachineBasicBlock::iterator EndMBBI = MBB.end();
1176 MachineBasicBlock::iterator NextMBBI = std::next(MBBI);
1177 // Skip debug values.
1178 while (NextMBBI != EndMBBI && NextMBBI->isDebugValue())
1179 ++NextMBBI;
1180 if (NextMBBI == EndMBBI)
1181 return EndMBBI;
1182
1183 Offset = isIncrementOrDecrement(*NextMBBI, Reg, Pred, PredReg);
1184 return Offset == 0 ? EndMBBI : NextMBBI;
1185}
1186
Matthias Braunec50fa62015-06-01 21:26:23 +00001187/// Fold proceeding/trailing inc/dec of base register into the
1188/// LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible:
Evan Cheng10043e22007-01-19 07:51:42 +00001189///
1190/// stmia rn, <ra, rb, rc>
1191/// rn := rn + 4 * 3;
1192/// =>
1193/// stmia rn!, <ra, rb, rc>
1194///
1195/// rn := rn - 4 * 3;
1196/// ldmia rn, <ra, rb, rc>
1197/// =>
1198/// ldmdb rn!, <ra, rb, rc>
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001199bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineInstr *MI) {
James Molloy556763d2014-05-16 14:14:30 +00001200 // Thumb1 is already using updating loads/stores.
1201 if (isThumb1) return false;
1202
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001203 const MachineOperand &BaseOP = MI->getOperand(0);
1204 unsigned Base = BaseOP.getReg();
1205 bool BaseKill = BaseOP.isKill();
Evan Cheng94f04c62007-07-05 07:18:20 +00001206 unsigned PredReg = 0;
Duncan P. N. Exon Smith6307eb52016-02-23 02:46:52 +00001207 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
Matthias Braunfa3872e2015-05-18 20:27:55 +00001208 unsigned Opcode = MI->getOpcode();
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001209 DebugLoc DL = MI->getDebugLoc();
Evan Cheng10043e22007-01-19 07:51:42 +00001210
Bob Wilson13ce07f2010-08-27 23:18:17 +00001211 // Can't use an updating ld/st if the base register is also a dest
1212 // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001213 for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i)
Bob Wilson13ce07f2010-08-27 23:18:17 +00001214 if (MI->getOperand(i).getReg() == Base)
1215 return false;
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001216
Matthias Brauna50d2202015-07-21 00:19:01 +00001217 int Bytes = getLSMultipleTransferSize(MI);
Matthias Braun84e28972015-07-20 23:17:16 +00001218 MachineBasicBlock &MBB = *MI->getParent();
Matthias Braun84e28972015-07-20 23:17:16 +00001219 MachineBasicBlock::iterator MBBI(MI);
Matthias Brauna50d2202015-07-21 00:19:01 +00001220 int Offset;
1221 MachineBasicBlock::iterator MergeInstr
1222 = findIncDecBefore(MBBI, Base, Pred, PredReg, Offset);
1223 ARM_AM::AMSubMode Mode = getLoadStoreMultipleSubMode(Opcode);
1224 if (Mode == ARM_AM::ia && Offset == -Bytes) {
1225 Mode = ARM_AM::db;
1226 } else if (Mode == ARM_AM::ib && Offset == -Bytes) {
1227 Mode = ARM_AM::da;
1228 } else {
1229 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1230 if (((Mode != ARM_AM::ia && Mode != ARM_AM::ib) || Offset != Bytes) &&
James Molloy75afc952016-06-07 11:47:24 +00001231 ((Mode != ARM_AM::da && Mode != ARM_AM::db) || Offset != -Bytes)) {
1232
1233 // We couldn't find an inc/dec to merge. But if the base is dead, we
1234 // can still change to a writeback form as that will save us 2 bytes
1235 // of code size. It can create WAW hazards though, so only do it if
1236 // we're minimizing code size.
1237 if (!MBB.getParent()->getFunction()->optForMinSize() || !BaseKill)
1238 return false;
1239
1240 bool HighRegsUsed = false;
1241 for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i)
1242 if (MI->getOperand(i).getReg() >= ARM::R8) {
1243 HighRegsUsed = true;
1244 break;
1245 }
1246
1247 if (!HighRegsUsed)
1248 MergeInstr = MBB.end();
1249 else
1250 return false;
1251 }
Bob Wilson947f04b2010-03-13 01:08:20 +00001252 }
James Molloy75afc952016-06-07 11:47:24 +00001253 if (MergeInstr != MBB.end())
1254 MBB.erase(MergeInstr);
Bob Wilson947f04b2010-03-13 01:08:20 +00001255
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001256 unsigned NewOpc = getUpdatingLSMultipleOpcode(Opcode, Mode);
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001257 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
Bob Wilson947f04b2010-03-13 01:08:20 +00001258 .addReg(Base, getDefRegState(true)) // WB base register
Bob Wilson13ce07f2010-08-27 23:18:17 +00001259 .addReg(Base, getKillRegState(BaseKill))
Bob Wilson13ce07f2010-08-27 23:18:17 +00001260 .addImm(Pred).addReg(PredReg);
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001261
Bob Wilson947f04b2010-03-13 01:08:20 +00001262 // Transfer the rest of operands.
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001263 for (unsigned OpNum = 3, e = MI->getNumOperands(); OpNum != e; ++OpNum)
Bob Wilson947f04b2010-03-13 01:08:20 +00001264 MIB.addOperand(MI->getOperand(OpNum));
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001265
Bob Wilson947f04b2010-03-13 01:08:20 +00001266 // Transfer memoperands.
Chris Lattner1d0c2572011-04-29 05:24:29 +00001267 MIB->setMemRefs(MI->memoperands_begin(), MI->memoperands_end());
Bob Wilson947f04b2010-03-13 01:08:20 +00001268
1269 MBB.erase(MBBI);
1270 return true;
Evan Cheng10043e22007-01-19 07:51:42 +00001271}
1272
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001273static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc,
1274 ARM_AM::AddrOpc Mode) {
Evan Cheng10043e22007-01-19 07:51:42 +00001275 switch (Opc) {
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001276 case ARM::LDRi12:
Owen Anderson16d33f32011-08-26 20:43:14 +00001277 return ARM::LDR_PRE_IMM;
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001278 case ARM::STRi12:
Owen Anderson2aedba62011-07-26 20:54:26 +00001279 return ARM::STR_PRE_IMM;
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001280 case ARM::VLDRS:
1281 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1282 case ARM::VLDRD:
1283 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
1284 case ARM::VSTRS:
1285 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1286 case ARM::VSTRD:
1287 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
Evan Cheng4605e8a2009-07-09 23:11:34 +00001288 case ARM::t2LDRi8:
1289 case ARM::t2LDRi12:
1290 return ARM::t2LDR_PRE;
1291 case ARM::t2STRi8:
1292 case ARM::t2STRi12:
1293 return ARM::t2STR_PRE;
Torok Edwinfbcc6632009-07-14 16:55:14 +00001294 default: llvm_unreachable("Unhandled opcode!");
Evan Cheng10043e22007-01-19 07:51:42 +00001295 }
Evan Cheng10043e22007-01-19 07:51:42 +00001296}
1297
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001298static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc,
1299 ARM_AM::AddrOpc Mode) {
Evan Cheng10043e22007-01-19 07:51:42 +00001300 switch (Opc) {
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001301 case ARM::LDRi12:
Owen Anderson2aedba62011-07-26 20:54:26 +00001302 return ARM::LDR_POST_IMM;
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001303 case ARM::STRi12:
Owen Anderson2aedba62011-07-26 20:54:26 +00001304 return ARM::STR_POST_IMM;
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001305 case ARM::VLDRS:
1306 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1307 case ARM::VLDRD:
1308 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
1309 case ARM::VSTRS:
1310 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1311 case ARM::VSTRD:
1312 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
Evan Cheng4605e8a2009-07-09 23:11:34 +00001313 case ARM::t2LDRi8:
1314 case ARM::t2LDRi12:
1315 return ARM::t2LDR_POST;
1316 case ARM::t2STRi8:
1317 case ARM::t2STRi12:
1318 return ARM::t2STR_POST;
Torok Edwinfbcc6632009-07-14 16:55:14 +00001319 default: llvm_unreachable("Unhandled opcode!");
Evan Cheng10043e22007-01-19 07:51:42 +00001320 }
Evan Cheng10043e22007-01-19 07:51:42 +00001321}
1322
Matthias Braunec50fa62015-06-01 21:26:23 +00001323/// Fold proceeding/trailing inc/dec of base register into the
1324/// LDR/STR/FLD{D|S}/FST{D|S} op when possible:
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001325bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineInstr *MI) {
James Molloy556763d2014-05-16 14:14:30 +00001326 // Thumb1 doesn't have updating LDR/STR.
1327 // FIXME: Use LDM/STM with single register instead.
1328 if (isThumb1) return false;
1329
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001330 unsigned Base = getLoadStoreBaseOp(*MI).getReg();
1331 bool BaseKill = getLoadStoreBaseOp(*MI).isKill();
Matthias Braunfa3872e2015-05-18 20:27:55 +00001332 unsigned Opcode = MI->getOpcode();
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001333 DebugLoc DL = MI->getDebugLoc();
Bob Wilsonaf10d272010-03-12 22:50:09 +00001334 bool isAM5 = (Opcode == ARM::VLDRD || Opcode == ARM::VLDRS ||
1335 Opcode == ARM::VSTRD || Opcode == ARM::VSTRS);
Jim Grosbach338de3e2010-10-27 23:12:14 +00001336 bool isAM2 = (Opcode == ARM::LDRi12 || Opcode == ARM::STRi12);
1337 if (isi32Load(Opcode) || isi32Store(Opcode))
Jim Grosbach1e4d9a12010-10-26 22:37:02 +00001338 if (MI->getOperand(2).getImm() != 0)
1339 return false;
Bob Wilsonaf10d272010-03-12 22:50:09 +00001340 if (isAM5 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0)
Evan Cheng4605e8a2009-07-09 23:11:34 +00001341 return false;
Evan Cheng10043e22007-01-19 07:51:42 +00001342
Evan Cheng10043e22007-01-19 07:51:42 +00001343 // Can't do the merge if the destination register is the same as the would-be
1344 // writeback register.
Chad Rosierace9c5d2013-03-25 16:29:20 +00001345 if (MI->getOperand(0).getReg() == Base)
Evan Cheng10043e22007-01-19 07:51:42 +00001346 return false;
1347
Evan Cheng94f04c62007-07-05 07:18:20 +00001348 unsigned PredReg = 0;
Duncan P. N. Exon Smith6307eb52016-02-23 02:46:52 +00001349 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
Matthias Brauna50d2202015-07-21 00:19:01 +00001350 int Bytes = getLSMultipleTransferSize(MI);
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001351 MachineBasicBlock &MBB = *MI->getParent();
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001352 MachineBasicBlock::iterator MBBI(MI);
Matthias Brauna50d2202015-07-21 00:19:01 +00001353 int Offset;
1354 MachineBasicBlock::iterator MergeInstr
1355 = findIncDecBefore(MBBI, Base, Pred, PredReg, Offset);
1356 unsigned NewOpc;
1357 if (!isAM5 && Offset == Bytes) {
1358 NewOpc = getPreIndexedLoadStoreOpcode(Opcode, ARM_AM::add);
1359 } else if (Offset == -Bytes) {
1360 NewOpc = getPreIndexedLoadStoreOpcode(Opcode, ARM_AM::sub);
1361 } else {
1362 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1363 if (Offset == Bytes) {
1364 NewOpc = getPostIndexedLoadStoreOpcode(Opcode, ARM_AM::add);
1365 } else if (!isAM5 && Offset == -Bytes) {
1366 NewOpc = getPostIndexedLoadStoreOpcode(Opcode, ARM_AM::sub);
1367 } else
1368 return false;
Evan Cheng10043e22007-01-19 07:51:42 +00001369 }
Matthias Brauna50d2202015-07-21 00:19:01 +00001370 MBB.erase(MergeInstr);
Evan Cheng10043e22007-01-19 07:51:42 +00001371
Matthias Brauna50d2202015-07-21 00:19:01 +00001372 ARM_AM::AddrOpc AddSub = Offset < 0 ? ARM_AM::sub : ARM_AM::add;
Evan Cheng10043e22007-01-19 07:51:42 +00001373
Matthias Brauna50d2202015-07-21 00:19:01 +00001374 bool isLd = isLoadSingle(Opcode);
Bob Wilson53149402010-03-13 00:43:32 +00001375 if (isAM5) {
James Molloybb73c232014-05-16 14:08:46 +00001376 // VLDM[SD]_UPD, VSTM[SD]_UPD
Bob Wilson13ce07f2010-08-27 23:18:17 +00001377 // (There are no base-updating versions of VLDR/VSTR instructions, but the
1378 // updating load/store-multiple instructions can be used with only one
1379 // register.)
Bob Wilson53149402010-03-13 00:43:32 +00001380 MachineOperand &MO = MI->getOperand(0);
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001381 BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
Bob Wilson947f04b2010-03-13 01:08:20 +00001382 .addReg(Base, getDefRegState(true)) // WB base register
Bob Wilson53149402010-03-13 00:43:32 +00001383 .addReg(Base, getKillRegState(isLd ? BaseKill : false))
Bob Wilson53149402010-03-13 00:43:32 +00001384 .addImm(Pred).addReg(PredReg)
Bob Wilson53149402010-03-13 00:43:32 +00001385 .addReg(MO.getReg(), (isLd ? getDefRegState(true) :
1386 getKillRegState(MO.isKill())));
1387 } else if (isLd) {
Jim Grosbach23254742011-08-12 22:20:41 +00001388 if (isAM2) {
Owen Anderson63143432011-08-29 17:59:41 +00001389 // LDR_PRE, LDR_POST
1390 if (NewOpc == ARM::LDR_PRE_IMM || NewOpc == ARM::LDRB_PRE_IMM) {
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001391 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
Owen Anderson63143432011-08-29 17:59:41 +00001392 .addReg(Base, RegState::Define)
1393 .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
1394 } else {
Matthias Brauna50d2202015-07-21 00:19:01 +00001395 int Imm = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001396 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
Owen Anderson63143432011-08-29 17:59:41 +00001397 .addReg(Base, RegState::Define)
Matthias Brauna50d2202015-07-21 00:19:01 +00001398 .addReg(Base).addReg(0).addImm(Imm).addImm(Pred).addReg(PredReg);
Owen Anderson63143432011-08-29 17:59:41 +00001399 }
Jim Grosbach23254742011-08-12 22:20:41 +00001400 } else {
Evan Cheng71756e72009-08-04 01:43:45 +00001401 // t2LDR_PRE, t2LDR_POST
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001402 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
Evan Cheng71756e72009-08-04 01:43:45 +00001403 .addReg(Base, RegState::Define)
1404 .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
Jim Grosbach23254742011-08-12 22:20:41 +00001405 }
Evan Cheng71756e72009-08-04 01:43:45 +00001406 } else {
1407 MachineOperand &MO = MI->getOperand(0);
Jim Grosbachf0c95ca2011-08-05 20:35:44 +00001408 // FIXME: post-indexed stores use am2offset_imm, which still encodes
1409 // the vestigal zero-reg offset register. When that's fixed, this clause
1410 // can be removed entirely.
Jim Grosbach23254742011-08-12 22:20:41 +00001411 if (isAM2 && NewOpc == ARM::STR_POST_IMM) {
Matthias Brauna50d2202015-07-21 00:19:01 +00001412 int Imm = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
Evan Cheng71756e72009-08-04 01:43:45 +00001413 // STR_PRE, STR_POST
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001414 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
Evan Cheng71756e72009-08-04 01:43:45 +00001415 .addReg(MO.getReg(), getKillRegState(MO.isKill()))
Matthias Brauna50d2202015-07-21 00:19:01 +00001416 .addReg(Base).addReg(0).addImm(Imm).addImm(Pred).addReg(PredReg);
Jim Grosbach23254742011-08-12 22:20:41 +00001417 } else {
Evan Cheng71756e72009-08-04 01:43:45 +00001418 // t2STR_PRE, t2STR_POST
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001419 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
Evan Cheng71756e72009-08-04 01:43:45 +00001420 .addReg(MO.getReg(), getKillRegState(MO.isKill()))
1421 .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
Jim Grosbach23254742011-08-12 22:20:41 +00001422 }
Evan Cheng10043e22007-01-19 07:51:42 +00001423 }
1424 MBB.erase(MBBI);
1425
1426 return true;
1427}
1428
Matthias Brauna50d2202015-07-21 00:19:01 +00001429bool ARMLoadStoreOpt::MergeBaseUpdateLSDouble(MachineInstr &MI) const {
1430 unsigned Opcode = MI.getOpcode();
1431 assert((Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8) &&
1432 "Must have t2STRDi8 or t2LDRDi8");
1433 if (MI.getOperand(3).getImm() != 0)
1434 return false;
1435
1436 // Behaviour for writeback is undefined if base register is the same as one
1437 // of the others.
1438 const MachineOperand &BaseOp = MI.getOperand(2);
1439 unsigned Base = BaseOp.getReg();
1440 const MachineOperand &Reg0Op = MI.getOperand(0);
1441 const MachineOperand &Reg1Op = MI.getOperand(1);
1442 if (Reg0Op.getReg() == Base || Reg1Op.getReg() == Base)
1443 return false;
1444
1445 unsigned PredReg;
Duncan P. N. Exon Smith6307eb52016-02-23 02:46:52 +00001446 ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
Matthias Brauna50d2202015-07-21 00:19:01 +00001447 MachineBasicBlock::iterator MBBI(MI);
1448 MachineBasicBlock &MBB = *MI.getParent();
1449 int Offset;
1450 MachineBasicBlock::iterator MergeInstr = findIncDecBefore(MBBI, Base, Pred,
1451 PredReg, Offset);
1452 unsigned NewOpc;
1453 if (Offset == 8 || Offset == -8) {
1454 NewOpc = Opcode == ARM::t2LDRDi8 ? ARM::t2LDRD_PRE : ARM::t2STRD_PRE;
1455 } else {
1456 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1457 if (Offset == 8 || Offset == -8) {
1458 NewOpc = Opcode == ARM::t2LDRDi8 ? ARM::t2LDRD_POST : ARM::t2STRD_POST;
1459 } else
1460 return false;
1461 }
1462 MBB.erase(MergeInstr);
1463
1464 DebugLoc DL = MI.getDebugLoc();
1465 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc));
1466 if (NewOpc == ARM::t2LDRD_PRE || NewOpc == ARM::t2LDRD_POST) {
1467 MIB.addOperand(Reg0Op).addOperand(Reg1Op)
1468 .addReg(BaseOp.getReg(), RegState::Define);
1469 } else {
1470 assert(NewOpc == ARM::t2STRD_PRE || NewOpc == ARM::t2STRD_POST);
1471 MIB.addReg(BaseOp.getReg(), RegState::Define)
1472 .addOperand(Reg0Op).addOperand(Reg1Op);
1473 }
1474 MIB.addReg(BaseOp.getReg(), RegState::Kill)
1475 .addImm(Offset).addImm(Pred).addReg(PredReg);
1476 assert(TII->get(Opcode).getNumOperands() == 6 &&
1477 TII->get(NewOpc).getNumOperands() == 7 &&
1478 "Unexpected number of operands in Opcode specification.");
1479
1480 // Transfer implicit operands.
1481 for (const MachineOperand &MO : MI.implicit_operands())
1482 MIB.addOperand(MO);
1483 MIB->setMemRefs(MI.memoperands_begin(), MI.memoperands_end());
1484
1485 MBB.erase(MBBI);
1486 return true;
1487}
1488
Matthias Braunec50fa62015-06-01 21:26:23 +00001489/// Returns true if instruction is a memory operation that this pass is capable
1490/// of operating on.
Matthias Braun5a1857b2015-11-21 02:09:49 +00001491static bool isMemoryOp(const MachineInstr &MI) {
1492 unsigned Opcode = MI.getOpcode();
Evan Chengd28de672007-03-06 18:02:41 +00001493 switch (Opcode) {
Jim Grosbachd7cf55c2009-11-09 00:11:35 +00001494 case ARM::VLDRS:
1495 case ARM::VSTRS:
Jim Grosbachd7cf55c2009-11-09 00:11:35 +00001496 case ARM::VLDRD:
1497 case ARM::VSTRD:
Jim Grosbach1e4d9a12010-10-26 22:37:02 +00001498 case ARM::LDRi12:
Jim Grosbach338de3e2010-10-27 23:12:14 +00001499 case ARM::STRi12:
James Molloy556763d2014-05-16 14:14:30 +00001500 case ARM::tLDRi:
1501 case ARM::tSTRi:
Renato Golinb9887ef2015-02-25 14:41:06 +00001502 case ARM::tLDRspi:
1503 case ARM::tSTRspi:
Evan Cheng4605e8a2009-07-09 23:11:34 +00001504 case ARM::t2LDRi8:
1505 case ARM::t2LDRi12:
1506 case ARM::t2STRi8:
1507 case ARM::t2STRi12:
Matthias Braun5a1857b2015-11-21 02:09:49 +00001508 break;
1509 default:
1510 return false;
Evan Chengd28de672007-03-06 18:02:41 +00001511 }
Matthias Braun5a1857b2015-11-21 02:09:49 +00001512 if (!MI.getOperand(1).isReg())
1513 return false;
1514
1515 // When no memory operands are present, conservatively assume unaligned,
1516 // volatile, unfoldable.
1517 if (!MI.hasOneMemOperand())
1518 return false;
1519
1520 const MachineMemOperand &MMO = **MI.memoperands_begin();
1521
1522 // Don't touch volatile memory accesses - we may be changing their order.
1523 if (MMO.isVolatile())
1524 return false;
1525
1526 // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is
1527 // not.
1528 if (MMO.getAlignment() < 4)
1529 return false;
1530
1531 // str <undef> could probably be eliminated entirely, but for now we just want
1532 // to avoid making a mess of it.
1533 // FIXME: Use str <undef> as a wildcard to enable better stm folding.
1534 if (MI.getOperand(0).isReg() && MI.getOperand(0).isUndef())
1535 return false;
1536
1537 // Likewise don't mess with references to undefined addresses.
1538 if (MI.getOperand(1).isUndef())
1539 return false;
1540
1541 return true;
Evan Chengd28de672007-03-06 18:02:41 +00001542}
1543
Evan Cheng1283c6a2009-06-15 08:28:29 +00001544static void InsertLDR_STR(MachineBasicBlock &MBB,
Benjamin Kramerbdc49562016-06-12 15:39:02 +00001545 MachineBasicBlock::iterator &MBBI, int Offset,
1546 bool isDef, const DebugLoc &DL, unsigned NewOpc,
Evan Chenga6b9cab2009-09-27 09:46:04 +00001547 unsigned Reg, bool RegDeadKill, bool RegUndef,
1548 unsigned BaseReg, bool BaseKill, bool BaseUndef,
Benjamin Kramerbdc49562016-06-12 15:39:02 +00001549 bool OffKill, bool OffUndef, ARMCC::CondCodes Pred,
1550 unsigned PredReg, const TargetInstrInfo *TII,
1551 bool isT2) {
Evan Chenga6b9cab2009-09-27 09:46:04 +00001552 if (isDef) {
1553 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1554 TII->get(NewOpc))
Evan Cheng5d8df7f2009-06-19 01:59:04 +00001555 .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill))
Evan Chenga6b9cab2009-09-27 09:46:04 +00001556 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
Evan Chenga6b9cab2009-09-27 09:46:04 +00001557 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1558 } else {
1559 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1560 TII->get(NewOpc))
1561 .addReg(Reg, getKillRegState(RegDeadKill) | getUndefRegState(RegUndef))
1562 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
Evan Chenga6b9cab2009-09-27 09:46:04 +00001563 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1564 }
Evan Cheng1283c6a2009-06-15 08:28:29 +00001565}
1566
1567bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB,
1568 MachineBasicBlock::iterator &MBBI) {
1569 MachineInstr *MI = &*MBBI;
1570 unsigned Opcode = MI->getOpcode();
Matthias Braunba3ecc32015-06-24 20:03:27 +00001571 if (Opcode != ARM::LDRD && Opcode != ARM::STRD && Opcode != ARM::t2LDRDi8)
1572 return false;
Evan Cheng1283c6a2009-06-15 08:28:29 +00001573
Matthias Braunba3ecc32015-06-24 20:03:27 +00001574 const MachineOperand &BaseOp = MI->getOperand(2);
1575 unsigned BaseReg = BaseOp.getReg();
1576 unsigned EvenReg = MI->getOperand(0).getReg();
1577 unsigned OddReg = MI->getOperand(1).getReg();
1578 unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false);
1579 unsigned OddRegNum = TRI->getDwarfRegNum(OddReg, false);
Evan Cheng1283c6a2009-06-15 08:28:29 +00001580
Matthias Braunba3ecc32015-06-24 20:03:27 +00001581 // ARM errata 602117: LDRD with base in list may result in incorrect base
1582 // register when interrupted or faulted.
1583 bool Errata602117 = EvenReg == BaseReg &&
1584 (Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8) && STI->isCortexM3();
1585 // ARM LDRD/STRD needs consecutive registers.
1586 bool NonConsecutiveRegs = (Opcode == ARM::LDRD || Opcode == ARM::STRD) &&
1587 (EvenRegNum % 2 != 0 || EvenRegNum + 1 != OddRegNum);
1588
1589 if (!Errata602117 && !NonConsecutiveRegs)
1590 return false;
1591
Matthias Braunba3ecc32015-06-24 20:03:27 +00001592 bool isT2 = Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8;
1593 bool isLd = Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8;
1594 bool EvenDeadKill = isLd ?
1595 MI->getOperand(0).isDead() : MI->getOperand(0).isKill();
1596 bool EvenUndef = MI->getOperand(0).isUndef();
1597 bool OddDeadKill = isLd ?
1598 MI->getOperand(1).isDead() : MI->getOperand(1).isKill();
1599 bool OddUndef = MI->getOperand(1).isUndef();
1600 bool BaseKill = BaseOp.isKill();
1601 bool BaseUndef = BaseOp.isUndef();
1602 bool OffKill = isT2 ? false : MI->getOperand(3).isKill();
1603 bool OffUndef = isT2 ? false : MI->getOperand(3).isUndef();
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00001604 int OffImm = getMemoryOpOffset(*MI);
Matthias Braunba3ecc32015-06-24 20:03:27 +00001605 unsigned PredReg = 0;
Duncan P. N. Exon Smith6307eb52016-02-23 02:46:52 +00001606 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
Matthias Braunba3ecc32015-06-24 20:03:27 +00001607
1608 if (OddRegNum > EvenRegNum && OffImm == 0) {
1609 // Ascending register numbers and no offset. It's safe to change it to a
1610 // ldm or stm.
1611 unsigned NewOpc = (isLd)
1612 ? (isT2 ? ARM::t2LDMIA : ARM::LDMIA)
1613 : (isT2 ? ARM::t2STMIA : ARM::STMIA);
1614 if (isLd) {
1615 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1616 .addReg(BaseReg, getKillRegState(BaseKill))
1617 .addImm(Pred).addReg(PredReg)
1618 .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill))
1619 .addReg(OddReg, getDefRegState(isLd) | getDeadRegState(OddDeadKill));
1620 ++NumLDRD2LDM;
Evan Cheng1283c6a2009-06-15 08:28:29 +00001621 } else {
Matthias Braunba3ecc32015-06-24 20:03:27 +00001622 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1623 .addReg(BaseReg, getKillRegState(BaseKill))
1624 .addImm(Pred).addReg(PredReg)
1625 .addReg(EvenReg,
1626 getKillRegState(EvenDeadKill) | getUndefRegState(EvenUndef))
1627 .addReg(OddReg,
1628 getKillRegState(OddDeadKill) | getUndefRegState(OddUndef));
1629 ++NumSTRD2STM;
Evan Cheng1283c6a2009-06-15 08:28:29 +00001630 }
Matthias Braunba3ecc32015-06-24 20:03:27 +00001631 } else {
1632 // Split into two instructions.
1633 unsigned NewOpc = (isLd)
1634 ? (isT2 ? (OffImm < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1635 : (isT2 ? (OffImm < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1636 // Be extra careful for thumb2. t2LDRi8 can't reference a zero offset,
1637 // so adjust and use t2LDRi12 here for that.
1638 unsigned NewOpc2 = (isLd)
1639 ? (isT2 ? (OffImm+4 < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1640 : (isT2 ? (OffImm+4 < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1641 DebugLoc dl = MBBI->getDebugLoc();
1642 // If this is a load and base register is killed, it may have been
1643 // re-defed by the load, make sure the first load does not clobber it.
1644 if (isLd &&
1645 (BaseKill || OffKill) &&
1646 (TRI->regsOverlap(EvenReg, BaseReg))) {
1647 assert(!TRI->regsOverlap(OddReg, BaseReg));
1648 InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc2,
1649 OddReg, OddDeadKill, false,
1650 BaseReg, false, BaseUndef, false, OffUndef,
1651 Pred, PredReg, TII, isT2);
Matthias Braunba3ecc32015-06-24 20:03:27 +00001652 InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc,
1653 EvenReg, EvenDeadKill, false,
1654 BaseReg, BaseKill, BaseUndef, OffKill, OffUndef,
1655 Pred, PredReg, TII, isT2);
1656 } else {
1657 if (OddReg == EvenReg && EvenDeadKill) {
1658 // If the two source operands are the same, the kill marker is
1659 // probably on the first one. e.g.
1660 // t2STRDi8 %R5<kill>, %R5, %R9<kill>, 0, 14, %reg0
1661 EvenDeadKill = false;
1662 OddDeadKill = true;
1663 }
1664 // Never kill the base register in the first instruction.
1665 if (EvenReg == BaseReg)
1666 EvenDeadKill = false;
1667 InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc,
1668 EvenReg, EvenDeadKill, EvenUndef,
1669 BaseReg, false, BaseUndef, false, OffUndef,
1670 Pred, PredReg, TII, isT2);
Matthias Braunba3ecc32015-06-24 20:03:27 +00001671 InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc2,
1672 OddReg, OddDeadKill, OddUndef,
1673 BaseReg, BaseKill, BaseUndef, OffKill, OffUndef,
1674 Pred, PredReg, TII, isT2);
1675 }
1676 if (isLd)
1677 ++NumLDRD2LDR;
1678 else
1679 ++NumSTRD2STR;
Evan Cheng1283c6a2009-06-15 08:28:29 +00001680 }
Matthias Braunba3ecc32015-06-24 20:03:27 +00001681
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001682 MBBI = MBB.erase(MBBI);
Matthias Braunba3ecc32015-06-24 20:03:27 +00001683 return true;
Evan Cheng1283c6a2009-06-15 08:28:29 +00001684}
1685
Matthias Braunec50fa62015-06-01 21:26:23 +00001686/// An optimization pass to turn multiple LDR / STR ops of the same base and
1687/// incrementing offset into LDM / STM ops.
Evan Cheng10043e22007-01-19 07:51:42 +00001688bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
Evan Cheng10043e22007-01-19 07:51:42 +00001689 MemOpQueue MemOps;
1690 unsigned CurrBase = 0;
Matthias Braunfa3872e2015-05-18 20:27:55 +00001691 unsigned CurrOpc = ~0u;
Evan Cheng0f7cbe82007-05-15 01:29:07 +00001692 ARMCC::CondCodes CurrPred = ARMCC::AL;
Evan Cheng10043e22007-01-19 07:51:42 +00001693 unsigned Position = 0;
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001694 assert(Candidates.size() == 0);
Matthias Brauna50d2202015-07-21 00:19:01 +00001695 assert(MergeBaseCandidates.size() == 0);
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001696 LiveRegsValid = false;
Evan Chengd28de672007-03-06 18:02:41 +00001697
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001698 for (MachineBasicBlock::iterator I = MBB.end(), MBBI; I != MBB.begin();
1699 I = MBBI) {
1700 // The instruction in front of the iterator is the one we look at.
1701 MBBI = std::prev(I);
Evan Cheng1283c6a2009-06-15 08:28:29 +00001702 if (FixInvalidRegPairOp(MBB, MBBI))
1703 continue;
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001704 ++Position;
Evan Cheng1283c6a2009-06-15 08:28:29 +00001705
Matthias Braun5a1857b2015-11-21 02:09:49 +00001706 if (isMemoryOp(*MBBI)) {
Matthias Braunfa3872e2015-05-18 20:27:55 +00001707 unsigned Opcode = MBBI->getOpcode();
Evan Cheng1fb4de82010-06-21 21:21:14 +00001708 const MachineOperand &MO = MBBI->getOperand(0);
1709 unsigned Reg = MO.getReg();
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001710 unsigned Base = getLoadStoreBaseOp(*MBBI).getReg();
Evan Cheng94f04c62007-07-05 07:18:20 +00001711 unsigned PredReg = 0;
Duncan P. N. Exon Smith6307eb52016-02-23 02:46:52 +00001712 ARMCC::CondCodes Pred = getInstrPredicate(*MBBI, PredReg);
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00001713 int Offset = getMemoryOpOffset(*MBBI);
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001714 if (CurrBase == 0) {
Evan Cheng10043e22007-01-19 07:51:42 +00001715 // Start of a new chain.
1716 CurrBase = Base;
1717 CurrOpc = Opcode;
Evan Cheng0f7cbe82007-05-15 01:29:07 +00001718 CurrPred = Pred;
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00001719 MemOps.push_back(MemOpQueueEntry(*MBBI, Offset, Position));
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001720 continue;
1721 }
1722 // Note: No need to match PredReg in the next if.
1723 if (CurrOpc == Opcode && CurrBase == Base && CurrPred == Pred) {
1724 // Watch out for:
1725 // r4 := ldr [r0, #8]
1726 // r4 := ldr [r0, #4]
1727 // or
1728 // r0 := ldr [r0]
1729 // If a load overrides the base register or a register loaded by
1730 // another load in our chain, we cannot take this instruction.
1731 bool Overlap = false;
1732 if (isLoadSingle(Opcode)) {
1733 Overlap = (Base == Reg);
1734 if (!Overlap) {
1735 for (const MemOpQueueEntry &E : MemOps) {
1736 if (TRI->regsOverlap(Reg, E.MI->getOperand(0).getReg())) {
1737 Overlap = true;
Evan Cheng10043e22007-01-19 07:51:42 +00001738 break;
1739 }
1740 }
1741 }
1742 }
Evan Cheng10043e22007-01-19 07:51:42 +00001743
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001744 if (!Overlap) {
1745 // Check offset and sort memory operation into the current chain.
1746 if (Offset > MemOps.back().Offset) {
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00001747 MemOps.push_back(MemOpQueueEntry(*MBBI, Offset, Position));
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001748 continue;
1749 } else {
1750 MemOpQueue::iterator MI, ME;
1751 for (MI = MemOps.begin(), ME = MemOps.end(); MI != ME; ++MI) {
1752 if (Offset < MI->Offset) {
1753 // Found a place to insert.
1754 break;
1755 }
1756 if (Offset == MI->Offset) {
1757 // Collision, abort.
1758 MI = ME;
1759 break;
1760 }
1761 }
1762 if (MI != MemOps.end()) {
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00001763 MemOps.insert(MI, MemOpQueueEntry(*MBBI, Offset, Position));
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001764 continue;
1765 }
1766 }
Evan Cheng7f5976e2009-06-04 01:15:28 +00001767 }
Evan Cheng2818fdd2007-03-07 02:38:05 +00001768 }
Evan Cheng10043e22007-01-19 07:51:42 +00001769
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001770 // Don't advance the iterator; The op will start a new chain next.
1771 MBBI = I;
1772 --Position;
1773 // Fallthrough to look into existing chain.
Matthias Brauna50d2202015-07-21 00:19:01 +00001774 } else if (MBBI->isDebugValue()) {
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001775 continue;
Matthias Brauna50d2202015-07-21 00:19:01 +00001776 } else if (MBBI->getOpcode() == ARM::t2LDRDi8 ||
1777 MBBI->getOpcode() == ARM::t2STRDi8) {
1778 // ARMPreAllocLoadStoreOpt has already formed some LDRD/STRD instructions
1779 // remember them because we may still be able to merge add/sub into them.
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00001780 MergeBaseCandidates.push_back(&*MBBI);
Matthias Brauna50d2202015-07-21 00:19:01 +00001781 }
1782
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001783
1784 // If we are here then the chain is broken; Extract candidates for a merge.
1785 if (MemOps.size() > 0) {
1786 FormCandidates(MemOps);
1787 // Reset for the next chain.
Evan Cheng10043e22007-01-19 07:51:42 +00001788 CurrBase = 0;
Matthias Braunfa3872e2015-05-18 20:27:55 +00001789 CurrOpc = ~0u;
Evan Cheng0f7cbe82007-05-15 01:29:07 +00001790 CurrPred = ARMCC::AL;
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001791 MemOps.clear();
Evan Cheng10043e22007-01-19 07:51:42 +00001792 }
1793 }
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001794 if (MemOps.size() > 0)
1795 FormCandidates(MemOps);
1796
1797 // Sort candidates so they get processed from end to begin of the basic
1798 // block later; This is necessary for liveness calculation.
1799 auto LessThan = [](const MergeCandidate* M0, const MergeCandidate *M1) {
1800 return M0->InsertPos < M1->InsertPos;
1801 };
1802 std::sort(Candidates.begin(), Candidates.end(), LessThan);
1803
1804 // Go through list of candidates and merge.
1805 bool Changed = false;
1806 for (const MergeCandidate *Candidate : Candidates) {
Matthias Braune40d89e2015-07-21 00:18:59 +00001807 if (Candidate->CanMergeToLSMulti || Candidate->CanMergeToLSDouble) {
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001808 MachineInstr *Merged = MergeOpsUpdate(*Candidate);
1809 // Merge preceding/trailing base inc/dec into the merged op.
1810 if (Merged) {
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001811 Changed = true;
Matthias Braune40d89e2015-07-21 00:18:59 +00001812 unsigned Opcode = Merged->getOpcode();
Matthias Brauna50d2202015-07-21 00:19:01 +00001813 if (Opcode == ARM::t2STRDi8 || Opcode == ARM::t2LDRDi8)
1814 MergeBaseUpdateLSDouble(*Merged);
1815 else
Matthias Braune40d89e2015-07-21 00:18:59 +00001816 MergeBaseUpdateLSMultiple(Merged);
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001817 } else {
1818 for (MachineInstr *MI : Candidate->Instrs) {
1819 if (MergeBaseUpdateLoadStore(MI))
1820 Changed = true;
1821 }
1822 }
1823 } else {
1824 assert(Candidate->Instrs.size() == 1);
1825 if (MergeBaseUpdateLoadStore(Candidate->Instrs.front()))
1826 Changed = true;
1827 }
1828 }
1829 Candidates.clear();
Matthias Brauna50d2202015-07-21 00:19:01 +00001830 // Try to fold add/sub into the LDRD/STRD formed by ARMPreAllocLoadStoreOpt.
1831 for (MachineInstr *MI : MergeBaseCandidates)
1832 MergeBaseUpdateLSDouble(*MI);
1833 MergeBaseCandidates.clear();
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001834
1835 return Changed;
Evan Cheng10043e22007-01-19 07:51:42 +00001836}
1837
Matthias Braunec50fa62015-06-01 21:26:23 +00001838/// If this is a exit BB, try merging the return ops ("bx lr" and "mov pc, lr")
1839/// into the preceding stack restore so it directly restore the value of LR
1840/// into pc.
Bob Wilson162242b2010-03-20 22:20:40 +00001841/// ldmfd sp!, {..., lr}
Evan Cheng10043e22007-01-19 07:51:42 +00001842/// bx lr
Bob Wilson162242b2010-03-20 22:20:40 +00001843/// or
1844/// ldmfd sp!, {..., lr}
1845/// mov pc, lr
Evan Cheng10043e22007-01-19 07:51:42 +00001846/// =>
Bob Wilson162242b2010-03-20 22:20:40 +00001847/// ldmfd sp!, {..., pc}
Evan Cheng10043e22007-01-19 07:51:42 +00001848bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) {
James Molloy556763d2014-05-16 14:14:30 +00001849 // Thumb1 LDM doesn't allow high registers.
1850 if (isThumb1) return false;
Evan Cheng10043e22007-01-19 07:51:42 +00001851 if (MBB.empty()) return false;
1852
Jakob Stoklund Olesenbbb1a542011-01-13 22:47:43 +00001853 MachineBasicBlock::iterator MBBI = MBB.getLastNonDebugInstr();
Evan Cheng4605e8a2009-07-09 23:11:34 +00001854 if (MBBI != MBB.begin() &&
Bob Wilson162242b2010-03-20 22:20:40 +00001855 (MBBI->getOpcode() == ARM::BX_RET ||
1856 MBBI->getOpcode() == ARM::tBX_RET ||
1857 MBBI->getOpcode() == ARM::MOVPCLR)) {
Adrian Prantl5d9acc22015-12-21 19:25:03 +00001858 MachineBasicBlock::iterator PrevI = std::prev(MBBI);
1859 // Ignore any DBG_VALUE instructions.
1860 while (PrevI->isDebugValue() && PrevI != MBB.begin())
1861 --PrevI;
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00001862 MachineInstr &PrevMI = *PrevI;
1863 unsigned Opcode = PrevMI.getOpcode();
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001864 if (Opcode == ARM::LDMIA_UPD || Opcode == ARM::LDMDA_UPD ||
1865 Opcode == ARM::LDMDB_UPD || Opcode == ARM::LDMIB_UPD ||
1866 Opcode == ARM::t2LDMIA_UPD || Opcode == ARM::t2LDMDB_UPD) {
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00001867 MachineOperand &MO = PrevMI.getOperand(PrevMI.getNumOperands() - 1);
Evan Cheng71756e72009-08-04 01:43:45 +00001868 if (MO.getReg() != ARM::LR)
1869 return false;
Bill Wendlinga68e3a52010-11-16 01:16:36 +00001870 unsigned NewOpc = (isThumb2 ? ARM::t2LDMIA_RET : ARM::LDMIA_RET);
1871 assert(((isThumb2 && Opcode == ARM::t2LDMIA_UPD) ||
1872 Opcode == ARM::LDMIA_UPD) && "Unsupported multiple load-return!");
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00001873 PrevMI.setDesc(TII->get(NewOpc));
Evan Cheng71756e72009-08-04 01:43:45 +00001874 MO.setReg(ARM::PC);
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00001875 PrevMI.copyImplicitOps(*MBB.getParent(), *MBBI);
Evan Cheng71756e72009-08-04 01:43:45 +00001876 MBB.erase(MBBI);
1877 return true;
Evan Cheng10043e22007-01-19 07:51:42 +00001878 }
1879 }
1880 return false;
1881}
1882
Artyom Skrobov2aca0c62015-12-28 21:40:45 +00001883bool ARMLoadStoreOpt::CombineMovBx(MachineBasicBlock &MBB) {
1884 MachineBasicBlock::iterator MBBI = MBB.getFirstTerminator();
1885 if (MBBI == MBB.begin() || MBBI == MBB.end() ||
1886 MBBI->getOpcode() != ARM::tBX_RET)
1887 return false;
1888
1889 MachineBasicBlock::iterator Prev = MBBI;
1890 --Prev;
1891 if (Prev->getOpcode() != ARM::tMOVr || !Prev->definesRegister(ARM::LR))
1892 return false;
1893
1894 for (auto Use : Prev->uses())
1895 if (Use.isKill()) {
1896 AddDefaultPred(BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(ARM::tBX))
Duncan P. N. Exon Smithfd8cc232016-02-27 20:01:33 +00001897 .addReg(Use.getReg(), RegState::Kill))
1898 .copyImplicitOps(*MBBI);
Artyom Skrobov2aca0c62015-12-28 21:40:45 +00001899 MBB.erase(MBBI);
1900 MBB.erase(Prev);
1901 return true;
1902 }
1903
1904 llvm_unreachable("tMOVr doesn't kill a reg before tBX_RET?");
1905}
1906
Evan Cheng10043e22007-01-19 07:51:42 +00001907bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
Andrew Kaylora2b91112016-04-25 22:01:04 +00001908 if (skipFunction(*Fn.getFunction()))
1909 return false;
1910
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001911 MF = &Fn;
Eric Christopher1b21f002015-01-29 00:19:33 +00001912 STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
1913 TL = STI->getTargetLowering();
Evan Chengf030f2d2007-03-07 20:30:36 +00001914 AFI = Fn.getInfo<ARMFunctionInfo>();
Eric Christopher1b21f002015-01-29 00:19:33 +00001915 TII = STI->getInstrInfo();
1916 TRI = STI->getRegisterInfo();
Chad Rosier9659de32015-08-07 17:02:29 +00001917
Matthias Brauna4a3182d2015-07-10 18:08:49 +00001918 RegClassInfoValid = false;
Evan Cheng4605e8a2009-07-09 23:11:34 +00001919 isThumb2 = AFI->isThumb2Function();
James Molloy92a15072014-05-16 14:11:38 +00001920 isThumb1 = AFI->isThumbFunction() && !isThumb2;
1921
Evan Cheng10043e22007-01-19 07:51:42 +00001922 bool Modified = false;
1923 for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
1924 ++MFI) {
1925 MachineBasicBlock &MBB = *MFI;
1926 Modified |= LoadStoreMultipleOpti(MBB);
Eric Christopher1b21f002015-01-29 00:19:33 +00001927 if (STI->hasV5TOps())
Bob Wilson914df822011-01-06 19:24:41 +00001928 Modified |= MergeReturnIntoLDM(MBB);
Artyom Skrobov2aca0c62015-12-28 21:40:45 +00001929 if (isThumb1)
1930 Modified |= CombineMovBx(MBB);
Evan Cheng10043e22007-01-19 07:51:42 +00001931 }
Evan Chengd28de672007-03-06 18:02:41 +00001932
Matthias Braune40d89e2015-07-21 00:18:59 +00001933 Allocator.DestroyAll();
Evan Cheng10043e22007-01-19 07:51:42 +00001934 return Modified;
1935}
Evan Cheng185c9ef2009-06-13 09:12:55 +00001936
Chad Rosier5d485db2015-09-16 13:11:31 +00001937#define ARM_PREALLOC_LOAD_STORE_OPT_NAME \
1938 "ARM pre- register allocation load / store optimization pass"
1939
Evan Cheng185c9ef2009-06-13 09:12:55 +00001940namespace {
Matthias Braunec50fa62015-06-01 21:26:23 +00001941 /// Pre- register allocation pass that move load / stores from consecutive
1942 /// locations close to make it more likely they will be combined later.
Nick Lewycky02d5f772009-10-25 06:33:48 +00001943 struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{
Evan Cheng185c9ef2009-06-13 09:12:55 +00001944 static char ID;
Matthias Braun8f456fb2016-07-16 02:24:10 +00001945 ARMPreAllocLoadStoreOpt() : MachineFunctionPass(ID) {}
Evan Cheng185c9ef2009-06-13 09:12:55 +00001946
Micah Villmowcdfe20b2012-10-08 16:38:25 +00001947 const DataLayout *TD;
Evan Cheng185c9ef2009-06-13 09:12:55 +00001948 const TargetInstrInfo *TII;
1949 const TargetRegisterInfo *TRI;
Evan Cheng1283c6a2009-06-15 08:28:29 +00001950 const ARMSubtarget *STI;
Evan Cheng185c9ef2009-06-13 09:12:55 +00001951 MachineRegisterInfo *MRI;
Evan Chengfd6aad72009-09-25 21:44:53 +00001952 MachineFunction *MF;
Evan Cheng185c9ef2009-06-13 09:12:55 +00001953
Craig Topper6bc27bf2014-03-10 02:09:33 +00001954 bool runOnMachineFunction(MachineFunction &Fn) override;
Evan Cheng185c9ef2009-06-13 09:12:55 +00001955
Craig Topper6bc27bf2014-03-10 02:09:33 +00001956 const char *getPassName() const override {
Chad Rosier5d485db2015-09-16 13:11:31 +00001957 return ARM_PREALLOC_LOAD_STORE_OPT_NAME;
Evan Cheng185c9ef2009-06-13 09:12:55 +00001958 }
1959
1960 private:
Evan Chengeba57e42009-06-15 20:54:56 +00001961 bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl,
1962 unsigned &NewOpc, unsigned &EvenReg,
1963 unsigned &OddReg, unsigned &BaseReg,
Jim Grosbach338de3e2010-10-27 23:12:14 +00001964 int &Offset,
Evan Chengfd6aad72009-09-25 21:44:53 +00001965 unsigned &PredReg, ARMCC::CondCodes &Pred,
1966 bool &isT2);
Evan Cheng185c9ef2009-06-13 09:12:55 +00001967 bool RescheduleOps(MachineBasicBlock *MBB,
Craig Topperaf0dea12013-07-04 01:31:24 +00001968 SmallVectorImpl<MachineInstr *> &Ops,
Evan Cheng185c9ef2009-06-13 09:12:55 +00001969 unsigned Base, bool isLd,
1970 DenseMap<MachineInstr*, unsigned> &MI2LocMap);
1971 bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
1972 };
1973 char ARMPreAllocLoadStoreOpt::ID = 0;
Alexander Kornienkof00654e2015-06-23 09:49:53 +00001974}
Evan Cheng185c9ef2009-06-13 09:12:55 +00001975
Matthias Braun8f456fb2016-07-16 02:24:10 +00001976INITIALIZE_PASS(ARMPreAllocLoadStoreOpt, "arm-prera-ldst-opt",
Chad Rosier5d485db2015-09-16 13:11:31 +00001977 ARM_PREALLOC_LOAD_STORE_OPT_NAME, false, false)
1978
Evan Cheng185c9ef2009-06-13 09:12:55 +00001979bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
Andrew Kaylora2b91112016-04-25 22:01:04 +00001980 if (AssumeMisalignedLoadStores || skipFunction(*Fn.getFunction()))
Matthias Braunf2909122016-03-02 19:20:00 +00001981 return false;
1982
Mehdi Aminibd7287e2015-07-16 06:11:10 +00001983 TD = &Fn.getDataLayout();
Eric Christopher7c558cf2014-10-14 08:44:19 +00001984 STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
Eric Christopher1b21f002015-01-29 00:19:33 +00001985 TII = STI->getInstrInfo();
1986 TRI = STI->getRegisterInfo();
Evan Cheng185c9ef2009-06-13 09:12:55 +00001987 MRI = &Fn.getRegInfo();
Evan Chengfd6aad72009-09-25 21:44:53 +00001988 MF = &Fn;
Evan Cheng185c9ef2009-06-13 09:12:55 +00001989
1990 bool Modified = false;
Duncan P. N. Exon Smith9f9559e2015-10-19 23:25:57 +00001991 for (MachineBasicBlock &MFI : Fn)
1992 Modified |= RescheduleLoadStoreInstrs(&MFI);
Evan Cheng185c9ef2009-06-13 09:12:55 +00001993
1994 return Modified;
1995}
1996
Evan Chengb4b20bb2009-06-19 23:17:27 +00001997static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base,
1998 MachineBasicBlock::iterator I,
1999 MachineBasicBlock::iterator E,
Craig Topper71b7b682014-08-21 05:55:13 +00002000 SmallPtrSetImpl<MachineInstr*> &MemOps,
Evan Chengb4b20bb2009-06-19 23:17:27 +00002001 SmallSet<unsigned, 4> &MemRegs,
2002 const TargetRegisterInfo *TRI) {
Evan Cheng185c9ef2009-06-13 09:12:55 +00002003 // Are there stores / loads / calls between them?
2004 // FIXME: This is overly conservative. We should make use of alias information
2005 // some day.
Evan Chengb4b20bb2009-06-19 23:17:27 +00002006 SmallSet<unsigned, 4> AddedRegPressure;
Evan Cheng185c9ef2009-06-13 09:12:55 +00002007 while (++I != E) {
Jim Grosbach4e5e6a82010-06-04 01:23:30 +00002008 if (I->isDebugValue() || MemOps.count(&*I))
Evan Chengb4b20bb2009-06-19 23:17:27 +00002009 continue;
Evan Cheng7f8e5632011-12-07 07:15:52 +00002010 if (I->isCall() || I->isTerminator() || I->hasUnmodeledSideEffects())
Evan Cheng185c9ef2009-06-13 09:12:55 +00002011 return false;
Evan Cheng7f8e5632011-12-07 07:15:52 +00002012 if (isLd && I->mayStore())
Evan Cheng185c9ef2009-06-13 09:12:55 +00002013 return false;
2014 if (!isLd) {
Evan Cheng7f8e5632011-12-07 07:15:52 +00002015 if (I->mayLoad())
Evan Cheng185c9ef2009-06-13 09:12:55 +00002016 return false;
2017 // It's not safe to move the first 'str' down.
2018 // str r1, [r0]
2019 // strh r5, [r0]
2020 // str r4, [r0, #+4]
Evan Cheng7f8e5632011-12-07 07:15:52 +00002021 if (I->mayStore())
Evan Cheng185c9ef2009-06-13 09:12:55 +00002022 return false;
2023 }
2024 for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) {
2025 MachineOperand &MO = I->getOperand(j);
Evan Chengb4b20bb2009-06-19 23:17:27 +00002026 if (!MO.isReg())
2027 continue;
2028 unsigned Reg = MO.getReg();
2029 if (MO.isDef() && TRI->regsOverlap(Reg, Base))
Evan Cheng185c9ef2009-06-13 09:12:55 +00002030 return false;
Evan Chengb4b20bb2009-06-19 23:17:27 +00002031 if (Reg != Base && !MemRegs.count(Reg))
2032 AddedRegPressure.insert(Reg);
Evan Cheng185c9ef2009-06-13 09:12:55 +00002033 }
2034 }
Evan Chengb4b20bb2009-06-19 23:17:27 +00002035
2036 // Estimate register pressure increase due to the transformation.
2037 if (MemRegs.size() <= 4)
2038 // Ok if we are moving small number of instructions.
2039 return true;
2040 return AddedRegPressure.size() <= MemRegs.size() * 2;
Evan Cheng185c9ef2009-06-13 09:12:55 +00002041}
2042
Evan Chengeba57e42009-06-15 20:54:56 +00002043bool
2044ARMPreAllocLoadStoreOpt::CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1,
Matthias Braun125c9f52015-06-03 16:30:24 +00002045 DebugLoc &dl, unsigned &NewOpc,
2046 unsigned &FirstReg,
2047 unsigned &SecondReg,
2048 unsigned &BaseReg, int &Offset,
2049 unsigned &PredReg,
Evan Chengfd6aad72009-09-25 21:44:53 +00002050 ARMCC::CondCodes &Pred,
2051 bool &isT2) {
Evan Cheng139c3db2009-09-29 07:07:30 +00002052 // Make sure we're allowed to generate LDRD/STRD.
2053 if (!STI->hasV5TEOps())
2054 return false;
2055
Jim Grosbachd7cf55c2009-11-09 00:11:35 +00002056 // FIXME: VLDRS / VSTRS -> VLDRD / VSTRD
Evan Chengfd6aad72009-09-25 21:44:53 +00002057 unsigned Scale = 1;
Evan Chengeba57e42009-06-15 20:54:56 +00002058 unsigned Opcode = Op0->getOpcode();
James Molloybb73c232014-05-16 14:08:46 +00002059 if (Opcode == ARM::LDRi12) {
Evan Chengeba57e42009-06-15 20:54:56 +00002060 NewOpc = ARM::LDRD;
James Molloybb73c232014-05-16 14:08:46 +00002061 } else if (Opcode == ARM::STRi12) {
Evan Chengeba57e42009-06-15 20:54:56 +00002062 NewOpc = ARM::STRD;
James Molloybb73c232014-05-16 14:08:46 +00002063 } else if (Opcode == ARM::t2LDRi8 || Opcode == ARM::t2LDRi12) {
Evan Chengfd6aad72009-09-25 21:44:53 +00002064 NewOpc = ARM::t2LDRDi8;
2065 Scale = 4;
2066 isT2 = true;
2067 } else if (Opcode == ARM::t2STRi8 || Opcode == ARM::t2STRi12) {
2068 NewOpc = ARM::t2STRDi8;
2069 Scale = 4;
2070 isT2 = true;
James Molloybb73c232014-05-16 14:08:46 +00002071 } else {
Evan Chengfd6aad72009-09-25 21:44:53 +00002072 return false;
James Molloybb73c232014-05-16 14:08:46 +00002073 }
Evan Chengfd6aad72009-09-25 21:44:53 +00002074
Jim Grosbach9302bfd2010-10-26 19:34:41 +00002075 // Make sure the base address satisfies i64 ld / st alignment requirement.
Quentin Colombet663150f2013-06-20 22:51:44 +00002076 // At the moment, we ignore the memoryoperand's value.
2077 // If we want to use AliasAnalysis, we should check it accordingly.
Evan Chengeba57e42009-06-15 20:54:56 +00002078 if (!Op0->hasOneMemOperand() ||
Dan Gohman48b185d2009-09-25 20:36:54 +00002079 (*Op0->memoperands_begin())->isVolatile())
Evan Cheng1283c6a2009-06-15 08:28:29 +00002080 return false;
2081
Dan Gohman48b185d2009-09-25 20:36:54 +00002082 unsigned Align = (*Op0->memoperands_begin())->getAlignment();
Dan Gohman913c9982010-04-15 04:33:49 +00002083 const Function *Func = MF->getFunction();
Evan Cheng1283c6a2009-06-15 08:28:29 +00002084 unsigned ReqAlign = STI->hasV6Ops()
Jim Grosbach338de3e2010-10-27 23:12:14 +00002085 ? TD->getABITypeAlignment(Type::getInt64Ty(Func->getContext()))
Evan Chengfd6aad72009-09-25 21:44:53 +00002086 : 8; // Pre-v6 need 8-byte align
Evan Chengeba57e42009-06-15 20:54:56 +00002087 if (Align < ReqAlign)
2088 return false;
2089
2090 // Then make sure the immediate offset fits.
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002091 int OffImm = getMemoryOpOffset(*Op0);
Evan Chenga6b9cab2009-09-27 09:46:04 +00002092 if (isT2) {
Evan Cheng42401d62011-03-15 18:41:52 +00002093 int Limit = (1 << 8) * Scale;
2094 if (OffImm >= Limit || (OffImm <= -Limit) || (OffImm & (Scale-1)))
2095 return false;
Evan Chengfd6aad72009-09-25 21:44:53 +00002096 Offset = OffImm;
Evan Chenga6b9cab2009-09-27 09:46:04 +00002097 } else {
2098 ARM_AM::AddrOpc AddSub = ARM_AM::add;
2099 if (OffImm < 0) {
2100 AddSub = ARM_AM::sub;
2101 OffImm = - OffImm;
2102 }
2103 int Limit = (1 << 8) * Scale;
2104 if (OffImm >= Limit || (OffImm & (Scale-1)))
2105 return false;
Evan Chengfd6aad72009-09-25 21:44:53 +00002106 Offset = ARM_AM::getAM3Opc(AddSub, OffImm);
Evan Chenga6b9cab2009-09-27 09:46:04 +00002107 }
Matthias Braun125c9f52015-06-03 16:30:24 +00002108 FirstReg = Op0->getOperand(0).getReg();
2109 SecondReg = Op1->getOperand(0).getReg();
2110 if (FirstReg == SecondReg)
Evan Chengeba57e42009-06-15 20:54:56 +00002111 return false;
2112 BaseReg = Op0->getOperand(1).getReg();
Duncan P. N. Exon Smith6307eb52016-02-23 02:46:52 +00002113 Pred = getInstrPredicate(*Op0, PredReg);
Evan Chengeba57e42009-06-15 20:54:56 +00002114 dl = Op0->getDebugLoc();
2115 return true;
Evan Cheng1283c6a2009-06-15 08:28:29 +00002116}
2117
Evan Cheng185c9ef2009-06-13 09:12:55 +00002118bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB,
Craig Topperaf0dea12013-07-04 01:31:24 +00002119 SmallVectorImpl<MachineInstr *> &Ops,
Evan Cheng185c9ef2009-06-13 09:12:55 +00002120 unsigned Base, bool isLd,
2121 DenseMap<MachineInstr*, unsigned> &MI2LocMap) {
2122 bool RetVal = false;
2123
2124 // Sort by offset (in reverse order).
Benjamin Kramer3a377bc2014-03-01 11:47:00 +00002125 std::sort(Ops.begin(), Ops.end(),
2126 [](const MachineInstr *LHS, const MachineInstr *RHS) {
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002127 int LOffset = getMemoryOpOffset(*LHS);
2128 int ROffset = getMemoryOpOffset(*RHS);
2129 assert(LHS == RHS || LOffset != ROffset);
2130 return LOffset > ROffset;
2131 });
Evan Cheng185c9ef2009-06-13 09:12:55 +00002132
2133 // The loads / stores of the same base are in order. Scan them from first to
Jim Grosbach1bcdf322010-06-04 00:15:00 +00002134 // last and check for the following:
Evan Cheng185c9ef2009-06-13 09:12:55 +00002135 // 1. Any def of base.
2136 // 2. Any gaps.
2137 while (Ops.size() > 1) {
2138 unsigned FirstLoc = ~0U;
2139 unsigned LastLoc = 0;
Craig Topper062a2ba2014-04-25 05:30:21 +00002140 MachineInstr *FirstOp = nullptr;
2141 MachineInstr *LastOp = nullptr;
Evan Cheng185c9ef2009-06-13 09:12:55 +00002142 int LastOffset = 0;
Evan Cheng0e796032009-06-18 02:04:01 +00002143 unsigned LastOpcode = 0;
Evan Cheng185c9ef2009-06-13 09:12:55 +00002144 unsigned LastBytes = 0;
2145 unsigned NumMove = 0;
2146 for (int i = Ops.size() - 1; i >= 0; --i) {
2147 MachineInstr *Op = Ops[i];
2148 unsigned Loc = MI2LocMap[Op];
2149 if (Loc <= FirstLoc) {
2150 FirstLoc = Loc;
2151 FirstOp = Op;
2152 }
2153 if (Loc >= LastLoc) {
2154 LastLoc = Loc;
2155 LastOp = Op;
2156 }
2157
Andrew Trick642f0f62012-01-11 03:56:08 +00002158 unsigned LSMOpcode
2159 = getLoadStoreMultipleOpcode(Op->getOpcode(), ARM_AM::ia);
2160 if (LastOpcode && LSMOpcode != LastOpcode)
Evan Cheng0e796032009-06-18 02:04:01 +00002161 break;
2162
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002163 int Offset = getMemoryOpOffset(*Op);
Evan Cheng185c9ef2009-06-13 09:12:55 +00002164 unsigned Bytes = getLSMultipleTransferSize(Op);
2165 if (LastBytes) {
2166 if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes))
2167 break;
2168 }
2169 LastOffset = Offset;
2170 LastBytes = Bytes;
Andrew Trick642f0f62012-01-11 03:56:08 +00002171 LastOpcode = LSMOpcode;
Evan Chengfd6aad72009-09-25 21:44:53 +00002172 if (++NumMove == 8) // FIXME: Tune this limit.
Evan Cheng185c9ef2009-06-13 09:12:55 +00002173 break;
2174 }
2175
2176 if (NumMove <= 1)
2177 Ops.pop_back();
2178 else {
Evan Chengb4b20bb2009-06-19 23:17:27 +00002179 SmallPtrSet<MachineInstr*, 4> MemOps;
2180 SmallSet<unsigned, 4> MemRegs;
2181 for (int i = NumMove-1; i >= 0; --i) {
2182 MemOps.insert(Ops[i]);
2183 MemRegs.insert(Ops[i]->getOperand(0).getReg());
2184 }
Evan Cheng185c9ef2009-06-13 09:12:55 +00002185
2186 // Be conservative, if the instructions are too far apart, don't
2187 // move them. We want to limit the increase of register pressure.
Evan Chengb4b20bb2009-06-19 23:17:27 +00002188 bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this.
Evan Cheng185c9ef2009-06-13 09:12:55 +00002189 if (DoMove)
Evan Chengb4b20bb2009-06-19 23:17:27 +00002190 DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp,
2191 MemOps, MemRegs, TRI);
Evan Cheng185c9ef2009-06-13 09:12:55 +00002192 if (!DoMove) {
2193 for (unsigned i = 0; i != NumMove; ++i)
2194 Ops.pop_back();
2195 } else {
2196 // This is the new location for the loads / stores.
2197 MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp;
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002198 while (InsertPos != MBB->end() &&
2199 (MemOps.count(&*InsertPos) || InsertPos->isDebugValue()))
Evan Cheng185c9ef2009-06-13 09:12:55 +00002200 ++InsertPos;
Evan Cheng1283c6a2009-06-15 08:28:29 +00002201
2202 // If we are moving a pair of loads / stores, see if it makes sense
2203 // to try to allocate a pair of registers that can form register pairs.
Evan Chengeba57e42009-06-15 20:54:56 +00002204 MachineInstr *Op0 = Ops.back();
2205 MachineInstr *Op1 = Ops[Ops.size()-2];
Matthias Braun125c9f52015-06-03 16:30:24 +00002206 unsigned FirstReg = 0, SecondReg = 0;
Jim Grosbach338de3e2010-10-27 23:12:14 +00002207 unsigned BaseReg = 0, PredReg = 0;
Evan Chengeba57e42009-06-15 20:54:56 +00002208 ARMCC::CondCodes Pred = ARMCC::AL;
Evan Chengfd6aad72009-09-25 21:44:53 +00002209 bool isT2 = false;
Evan Chengeba57e42009-06-15 20:54:56 +00002210 unsigned NewOpc = 0;
Evan Chenga6b9cab2009-09-27 09:46:04 +00002211 int Offset = 0;
Evan Chengeba57e42009-06-15 20:54:56 +00002212 DebugLoc dl;
2213 if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc,
Matthias Braun125c9f52015-06-03 16:30:24 +00002214 FirstReg, SecondReg, BaseReg,
Evan Chengfd6aad72009-09-25 21:44:53 +00002215 Offset, PredReg, Pred, isT2)) {
Evan Chengeba57e42009-06-15 20:54:56 +00002216 Ops.pop_back();
2217 Ops.pop_back();
Evan Cheng1283c6a2009-06-15 08:28:29 +00002218
Evan Cheng6cc775f2011-06-28 19:10:37 +00002219 const MCInstrDesc &MCID = TII->get(NewOpc);
Jakob Stoklund Olesen3c52f022012-05-07 22:10:26 +00002220 const TargetRegisterClass *TRC = TII->getRegClass(MCID, 0, TRI, *MF);
Matthias Braun125c9f52015-06-03 16:30:24 +00002221 MRI->constrainRegClass(FirstReg, TRC);
2222 MRI->constrainRegClass(SecondReg, TRC);
Cameron Zwarichec645bf2011-05-18 21:25:14 +00002223
Evan Chengeba57e42009-06-15 20:54:56 +00002224 // Form the pair instruction.
Evan Cheng0e796032009-06-18 02:04:01 +00002225 if (isLd) {
Evan Cheng6cc775f2011-06-28 19:10:37 +00002226 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
Matthias Braun125c9f52015-06-03 16:30:24 +00002227 .addReg(FirstReg, RegState::Define)
2228 .addReg(SecondReg, RegState::Define)
Evan Chengfd6aad72009-09-25 21:44:53 +00002229 .addReg(BaseReg);
Jim Grosbach338de3e2010-10-27 23:12:14 +00002230 // FIXME: We're converting from LDRi12 to an insn that still
Jim Grosbach1e4d9a12010-10-26 22:37:02 +00002231 // uses addrmode2, so we need an explicit offset reg. It should
Jim Grosbach338de3e2010-10-27 23:12:14 +00002232 // always by reg0 since we're transforming LDRi12s.
Evan Chengfd6aad72009-09-25 21:44:53 +00002233 if (!isT2)
Jim Grosbach1e4d9a12010-10-26 22:37:02 +00002234 MIB.addReg(0);
Evan Chengfd6aad72009-09-25 21:44:53 +00002235 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
Philip Reamesc86ed002016-01-06 04:39:03 +00002236 MIB.setMemRefs(Op0->mergeMemRefsWith(*Op1));
Andrew Trick28c1d182011-11-11 22:18:09 +00002237 DEBUG(dbgs() << "Formed " << *MIB << "\n");
Evan Cheng0e796032009-06-18 02:04:01 +00002238 ++NumLDRDFormed;
2239 } else {
Evan Cheng6cc775f2011-06-28 19:10:37 +00002240 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
Matthias Braun125c9f52015-06-03 16:30:24 +00002241 .addReg(FirstReg)
2242 .addReg(SecondReg)
Evan Chengfd6aad72009-09-25 21:44:53 +00002243 .addReg(BaseReg);
Jim Grosbach338de3e2010-10-27 23:12:14 +00002244 // FIXME: We're converting from LDRi12 to an insn that still
2245 // uses addrmode2, so we need an explicit offset reg. It should
2246 // always by reg0 since we're transforming STRi12s.
Evan Chengfd6aad72009-09-25 21:44:53 +00002247 if (!isT2)
Jim Grosbach338de3e2010-10-27 23:12:14 +00002248 MIB.addReg(0);
Evan Chengfd6aad72009-09-25 21:44:53 +00002249 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
Philip Reamesc86ed002016-01-06 04:39:03 +00002250 MIB.setMemRefs(Op0->mergeMemRefsWith(*Op1));
Andrew Trick28c1d182011-11-11 22:18:09 +00002251 DEBUG(dbgs() << "Formed " << *MIB << "\n");
Evan Cheng0e796032009-06-18 02:04:01 +00002252 ++NumSTRDFormed;
2253 }
2254 MBB->erase(Op0);
2255 MBB->erase(Op1);
Evan Cheng1283c6a2009-06-15 08:28:29 +00002256
Matthias Braun125c9f52015-06-03 16:30:24 +00002257 if (!isT2) {
2258 // Add register allocation hints to form register pairs.
2259 MRI->setRegAllocationHint(FirstReg, ARMRI::RegPairEven, SecondReg);
2260 MRI->setRegAllocationHint(SecondReg, ARMRI::RegPairOdd, FirstReg);
2261 }
Evan Chengeba57e42009-06-15 20:54:56 +00002262 } else {
2263 for (unsigned i = 0; i != NumMove; ++i) {
2264 MachineInstr *Op = Ops.back();
2265 Ops.pop_back();
2266 MBB->splice(InsertPos, MBB, Op);
2267 }
Evan Cheng185c9ef2009-06-13 09:12:55 +00002268 }
2269
2270 NumLdStMoved += NumMove;
2271 RetVal = true;
2272 }
2273 }
2274 }
2275
2276 return RetVal;
2277}
2278
2279bool
2280ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {
2281 bool RetVal = false;
2282
2283 DenseMap<MachineInstr*, unsigned> MI2LocMap;
2284 DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2LdsMap;
2285 DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2StsMap;
2286 SmallVector<unsigned, 4> LdBases;
2287 SmallVector<unsigned, 4> StBases;
2288
2289 unsigned Loc = 0;
2290 MachineBasicBlock::iterator MBBI = MBB->begin();
2291 MachineBasicBlock::iterator E = MBB->end();
2292 while (MBBI != E) {
2293 for (; MBBI != E; ++MBBI) {
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002294 MachineInstr &MI = *MBBI;
2295 if (MI.isCall() || MI.isTerminator()) {
Evan Cheng185c9ef2009-06-13 09:12:55 +00002296 // Stop at barriers.
2297 ++MBBI;
2298 break;
2299 }
2300
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002301 if (!MI.isDebugValue())
2302 MI2LocMap[&MI] = ++Loc;
Jim Grosbach4e5e6a82010-06-04 01:23:30 +00002303
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002304 if (!isMemoryOp(MI))
Evan Cheng185c9ef2009-06-13 09:12:55 +00002305 continue;
2306 unsigned PredReg = 0;
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002307 if (getInstrPredicate(MI, PredReg) != ARMCC::AL)
Evan Cheng185c9ef2009-06-13 09:12:55 +00002308 continue;
2309
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002310 int Opc = MI.getOpcode();
Matthias Brauna4a3182d2015-07-10 18:08:49 +00002311 bool isLd = isLoadSingle(Opc);
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002312 unsigned Base = MI.getOperand(1).getReg();
Evan Cheng185c9ef2009-06-13 09:12:55 +00002313 int Offset = getMemoryOpOffset(MI);
2314
2315 bool StopHere = false;
2316 if (isLd) {
2317 DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
2318 Base2LdsMap.find(Base);
2319 if (BI != Base2LdsMap.end()) {
2320 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002321 if (Offset == getMemoryOpOffset(*BI->second[i])) {
Evan Cheng185c9ef2009-06-13 09:12:55 +00002322 StopHere = true;
2323 break;
2324 }
2325 }
2326 if (!StopHere)
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002327 BI->second.push_back(&MI);
Evan Cheng185c9ef2009-06-13 09:12:55 +00002328 } else {
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002329 Base2LdsMap[Base].push_back(&MI);
Evan Cheng185c9ef2009-06-13 09:12:55 +00002330 LdBases.push_back(Base);
2331 }
2332 } else {
2333 DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
2334 Base2StsMap.find(Base);
2335 if (BI != Base2StsMap.end()) {
2336 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002337 if (Offset == getMemoryOpOffset(*BI->second[i])) {
Evan Cheng185c9ef2009-06-13 09:12:55 +00002338 StopHere = true;
2339 break;
2340 }
2341 }
2342 if (!StopHere)
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002343 BI->second.push_back(&MI);
Evan Cheng185c9ef2009-06-13 09:12:55 +00002344 } else {
Duncan P. N. Exon Smith29c52492016-07-08 20:21:17 +00002345 Base2StsMap[Base].push_back(&MI);
Evan Cheng185c9ef2009-06-13 09:12:55 +00002346 StBases.push_back(Base);
2347 }
2348 }
2349
2350 if (StopHere) {
Evan Chengb4b20bb2009-06-19 23:17:27 +00002351 // Found a duplicate (a base+offset combination that's seen earlier).
2352 // Backtrack.
Evan Cheng185c9ef2009-06-13 09:12:55 +00002353 --Loc;
2354 break;
2355 }
2356 }
2357
2358 // Re-schedule loads.
2359 for (unsigned i = 0, e = LdBases.size(); i != e; ++i) {
2360 unsigned Base = LdBases[i];
Craig Topperaf0dea12013-07-04 01:31:24 +00002361 SmallVectorImpl<MachineInstr *> &Lds = Base2LdsMap[Base];
Evan Cheng185c9ef2009-06-13 09:12:55 +00002362 if (Lds.size() > 1)
2363 RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap);
2364 }
2365
2366 // Re-schedule stores.
2367 for (unsigned i = 0, e = StBases.size(); i != e; ++i) {
2368 unsigned Base = StBases[i];
Craig Topperaf0dea12013-07-04 01:31:24 +00002369 SmallVectorImpl<MachineInstr *> &Sts = Base2StsMap[Base];
Evan Cheng185c9ef2009-06-13 09:12:55 +00002370 if (Sts.size() > 1)
2371 RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap);
2372 }
2373
2374 if (MBBI != E) {
2375 Base2LdsMap.clear();
2376 Base2StsMap.clear();
2377 LdBases.clear();
2378 StBases.clear();
2379 }
2380 }
2381
2382 return RetVal;
2383}
2384
2385
Matthias Braunec50fa62015-06-01 21:26:23 +00002386/// Returns an instance of the load / store optimization pass.
Evan Cheng185c9ef2009-06-13 09:12:55 +00002387FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) {
2388 if (PreAlloc)
2389 return new ARMPreAllocLoadStoreOpt();
2390 return new ARMLoadStoreOpt();
2391}