Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/ARM/ARMLoadStoreOptimizer.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass -------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
/// \file This file contains a pass that performs load / store related peephole
10
/// optimizations. This pass should be run after register allocation.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "ARM.h"
15
#include "ARMBaseInstrInfo.h"
16
#include "ARMBaseRegisterInfo.h"
17
#include "ARMISelLowering.h"
18
#include "ARMMachineFunctionInfo.h"
19
#include "ARMSubtarget.h"
20
#include "MCTargetDesc/ARMAddressingModes.h"
21
#include "MCTargetDesc/ARMBaseInfo.h"
22
#include "Utils/ARMBaseInfo.h"
23
#include "llvm/ADT/ArrayRef.h"
24
#include "llvm/ADT/DenseMap.h"
25
#include "llvm/ADT/DenseSet.h"
26
#include "llvm/ADT/STLExtras.h"
27
#include "llvm/ADT/SmallPtrSet.h"
28
#include "llvm/ADT/SmallSet.h"
29
#include "llvm/ADT/SmallVector.h"
30
#include "llvm/ADT/Statistic.h"
31
#include "llvm/ADT/iterator_range.h"
32
#include "llvm/Analysis/AliasAnalysis.h"
33
#include "llvm/CodeGen/LivePhysRegs.h"
34
#include "llvm/CodeGen/MachineBasicBlock.h"
35
#include "llvm/CodeGen/MachineFunction.h"
36
#include "llvm/CodeGen/MachineFunctionPass.h"
37
#include "llvm/CodeGen/MachineInstr.h"
38
#include "llvm/CodeGen/MachineInstrBuilder.h"
39
#include "llvm/CodeGen/MachineMemOperand.h"
40
#include "llvm/CodeGen/MachineOperand.h"
41
#include "llvm/CodeGen/MachineRegisterInfo.h"
42
#include "llvm/CodeGen/RegisterClassInfo.h"
43
#include "llvm/CodeGen/TargetFrameLowering.h"
44
#include "llvm/CodeGen/TargetInstrInfo.h"
45
#include "llvm/CodeGen/TargetLowering.h"
46
#include "llvm/CodeGen/TargetRegisterInfo.h"
47
#include "llvm/CodeGen/TargetSubtargetInfo.h"
48
#include "llvm/IR/DataLayout.h"
49
#include "llvm/IR/DebugLoc.h"
50
#include "llvm/IR/DerivedTypes.h"
51
#include "llvm/IR/Function.h"
52
#include "llvm/IR/Type.h"
53
#include "llvm/MC/MCInstrDesc.h"
54
#include "llvm/Pass.h"
55
#include "llvm/Support/Allocator.h"
56
#include "llvm/Support/CommandLine.h"
57
#include "llvm/Support/Debug.h"
58
#include "llvm/Support/ErrorHandling.h"
59
#include "llvm/Support/raw_ostream.h"
60
#include <algorithm>
61
#include <cassert>
62
#include <cstddef>
63
#include <cstdlib>
64
#include <iterator>
65
#include <limits>
66
#include <utility>
67
68
using namespace llvm;
69
70
#define DEBUG_TYPE "arm-ldst-opt"
71
72
STATISTIC(NumLDMGened , "Number of ldm instructions generated");
73
STATISTIC(NumSTMGened , "Number of stm instructions generated");
74
STATISTIC(NumVLDMGened, "Number of vldm instructions generated");
75
STATISTIC(NumVSTMGened, "Number of vstm instructions generated");
76
STATISTIC(NumLdStMoved, "Number of load / store instructions moved");
77
STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation");
78
STATISTIC(NumSTRDFormed,"Number of strd created before allocation");
79
STATISTIC(NumLDRD2LDM,  "Number of ldrd instructions turned back into ldm");
80
STATISTIC(NumSTRD2STM,  "Number of strd instructions turned back into stm");
81
STATISTIC(NumLDRD2LDR,  "Number of ldrd instructions turned back into ldr's");
82
STATISTIC(NumSTRD2STR,  "Number of strd instructions turned back into str's");
83
84
/// This switch disables formation of double/multi instructions that could
85
/// potentially lead to (new) alignment traps even with CCR.UNALIGN_TRP
86
/// disabled. This can be used to create libraries that are robust even when
87
/// users provoke undefined behaviour by supplying misaligned pointers.
88
/// \see mayCombineMisaligned()
89
static cl::opt<bool>
90
AssumeMisalignedLoadStores("arm-assume-misaligned-load-store", cl::Hidden,
91
    cl::init(false), cl::desc("Be more conservative in ARM load/store opt"));
92
93
30.1k
#define ARM_LOAD_STORE_OPT_NAME "ARM load / store optimization pass"
94
95
namespace {
96
97
  /// Post- register allocation pass the combine load / store instructions to
98
  /// form ldm / stm instructions.
99
  struct ARMLoadStoreOpt : public MachineFunctionPass {
100
    static char ID;
101
102
    const MachineFunction *MF;
103
    const TargetInstrInfo *TII;
104
    const TargetRegisterInfo *TRI;
105
    const ARMSubtarget *STI;
106
    const TargetLowering *TL;
107
    ARMFunctionInfo *AFI;
108
    LivePhysRegs LiveRegs;
109
    RegisterClassInfo RegClassInfo;
110
    MachineBasicBlock::const_iterator LiveRegPos;
111
    bool LiveRegsValid;
112
    bool RegClassInfoValid;
113
    bool isThumb1, isThumb2;
114
115
4.92k
    ARMLoadStoreOpt() : MachineFunctionPass(ID) {}
116
117
    bool runOnMachineFunction(MachineFunction &Fn) override;
118
119
4.90k
    MachineFunctionProperties getRequiredProperties() const override {
120
4.90k
      return MachineFunctionProperties().set(
121
4.90k
          MachineFunctionProperties::Property::NoVRegs);
122
4.90k
    }
123
124
30.1k
    StringRef getPassName() const override { return ARM_LOAD_STORE_OPT_NAME; }
125
126
  private:
127
    /// A set of load/store MachineInstrs with same base register sorted by
128
    /// offset.
129
    struct MemOpQueueEntry {
130
      MachineInstr *MI;
131
      int Offset;        ///< Load/Store offset.
132
      unsigned Position; ///< Position as counted from end of basic block.
133
134
      MemOpQueueEntry(MachineInstr &MI, int Offset, unsigned Position)
135
107k
          : MI(&MI), Offset(Offset), Position(Position) {}
136
    };
137
    using MemOpQueue = SmallVector<MemOpQueueEntry, 8>;
138
139
    /// A set of MachineInstrs that fulfill (nearly all) conditions to get
140
    /// merged into a LDM/STM.
141
    struct MergeCandidate {
142
      /// List of instructions ordered by load/store offset.
143
      SmallVector<MachineInstr*, 4> Instrs;
144
145
      /// Index in Instrs of the instruction being latest in the schedule.
146
      unsigned LatestMIIdx;
147
148
      /// Index in Instrs of the instruction being earliest in the schedule.
149
      unsigned EarliestMIIdx;
150
151
      /// Index into the basic block where the merged instruction will be
152
      /// inserted. (See MemOpQueueEntry.Position)
153
      unsigned InsertPos;
154
155
      /// Whether the instructions can be merged into a ldm/stm instruction.
156
      bool CanMergeToLSMulti;
157
158
      /// Whether the instructions can be merged into a ldrd/strd instruction.
159
      bool CanMergeToLSDouble;
160
    };
161
    SpecificBumpPtrAllocator<MergeCandidate> Allocator;
162
    SmallVector<const MergeCandidate*,4> Candidates;
163
    SmallVector<MachineInstr*,4> MergeBaseCandidates;
164
165
    void moveLiveRegsBefore(const MachineBasicBlock &MBB,
166
                            MachineBasicBlock::const_iterator Before);
167
    unsigned findFreeReg(const TargetRegisterClass &RegClass);
168
    void UpdateBaseRegUses(MachineBasicBlock &MBB,
169
                           MachineBasicBlock::iterator MBBI, const DebugLoc &DL,
170
                           unsigned Base, unsigned WordOffset,
171
                           ARMCC::CondCodes Pred, unsigned PredReg);
172
    MachineInstr *CreateLoadStoreMulti(
173
        MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
174
        int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
175
        ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
176
        ArrayRef<std::pair<unsigned, bool>> Regs,
177
        ArrayRef<MachineInstr*> Instrs);
178
    MachineInstr *CreateLoadStoreDouble(
179
        MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
180
        int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
181
        ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
182
        ArrayRef<std::pair<unsigned, bool>> Regs,
183
        ArrayRef<MachineInstr*> Instrs) const;
184
    void FormCandidates(const MemOpQueue &MemOps);
185
    MachineInstr *MergeOpsUpdate(const MergeCandidate &Cand);
186
    bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
187
                             MachineBasicBlock::iterator &MBBI);
188
    bool MergeBaseUpdateLoadStore(MachineInstr *MI);
189
    bool MergeBaseUpdateLSMultiple(MachineInstr *MI);
190
    bool MergeBaseUpdateLSDouble(MachineInstr &MI) const;
191
    bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
192
    bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
193
    bool CombineMovBx(MachineBasicBlock &MBB);
194
  };
195
196
} // end anonymous namespace
197
198
char ARMLoadStoreOpt::ID = 0;
199
200
INITIALIZE_PASS(ARMLoadStoreOpt, "arm-ldst-opt", ARM_LOAD_STORE_OPT_NAME, false,
201
                false)
202
203
114
static bool definesCPSR(const MachineInstr &MI) {
204
677
  for (const auto &MO : MI.operands()) {
205
677
    if (!MO.isReg())
206
229
      continue;
207
448
    if (MO.isDef() && 
MO.getReg() == ARM::CPSR117
&&
!MO.isDead()0
)
208
0
      // If the instruction has live CPSR def, then it's not safe to fold it
209
0
      // into load / store.
210
0
      return true;
211
448
  }
212
114
213
114
  return false;
214
114
}
215
216
418k
static int getMemoryOpOffset(const MachineInstr &MI) {
217
418k
  unsigned Opcode = MI.getOpcode();
218
418k
  bool isAM3 = Opcode == ARM::LDRD || 
Opcode == ARM::STRD418k
;
219
418k
  unsigned NumOperands = MI.getDesc().getNumOperands();
220
418k
  unsigned OffField = MI.getOperand(NumOperands - 3).getImm();
221
418k
222
418k
  if (Opcode == ARM::t2LDRi12 || 
Opcode == ARM::t2LDRi8327k
||
223
418k
      
Opcode == ARM::t2STRi12325k
||
Opcode == ARM::t2STRi848.3k
||
224
418k
      
Opcode == ARM::t2LDRDi847.8k
||
Opcode == ARM::t2STRDi847.8k
||
225
418k
      
Opcode == ARM::LDRi1247.8k
||
Opcode == ARM::STRi1241.1k
)
226
402k
    return OffField;
227
16.4k
228
16.4k
  // Thumb1 immediate offsets are scaled by 4
229
16.4k
  if (Opcode == ARM::tLDRi || 
Opcode == ARM::tSTRi14.5k
||
230
16.4k
      
Opcode == ARM::tLDRspi13.4k
||
Opcode == ARM::tSTRspi10.8k
)
231
7.37k
    return OffField * 4;
232
9.06k
233
9.06k
  int Offset = isAM3 ? 
ARM_AM::getAM3Offset(OffField)16
234
9.06k
    : 
ARM_AM::getAM5Offset(OffField) * 49.04k
;
235
9.06k
  ARM_AM::AddrOpc Op = isAM3 ? 
ARM_AM::getAM3Op(OffField)16
236
9.06k
    : 
ARM_AM::getAM5Op(OffField)9.04k
;
237
9.06k
238
9.06k
  if (Op == ARM_AM::sub)
239
63
    return -Offset;
240
9.00k
241
9.00k
  return Offset;
242
9.00k
}
243
244
273k
static const MachineOperand &getLoadStoreBaseOp(const MachineInstr &MI) {
245
273k
  return MI.getOperand(1);
246
273k
}
247
248
151k
static const MachineOperand &getLoadStoreRegOp(const MachineInstr &MI) {
249
151k
  return MI.getOperand(0);
250
151k
}
251
252
46.2k
static int getLoadStoreMultipleOpcode(unsigned Opcode, ARM_AM::AMSubMode Mode) {
253
46.2k
  switch (Opcode) {
254
46.2k
  
default: 0
llvm_unreachable0
("Unhandled opcode!");
255
46.2k
  case ARM::LDRi12:
256
802
    ++NumLDMGened;
257
802
    switch (Mode) {
258
802
    
default: 0
llvm_unreachable0
("Unhandled submode!");
259
802
    
case ARM_AM::ia: return ARM::LDMIA772
;
260
802
    
case ARM_AM::da: return ARM::LDMDA0
;
261
802
    
case ARM_AM::db: return ARM::LDMDB0
;
262
802
    
case ARM_AM::ib: return ARM::LDMIB30
;
263
0
    }
264
1.17k
  case ARM::STRi12:
265
1.17k
    ++NumSTMGened;
266
1.17k
    switch (Mode) {
267
1.17k
    
default: 0
llvm_unreachable0
("Unhandled submode!");
268
1.17k
    
case ARM_AM::ia: return ARM::STMIA1.15k
;
269
1.17k
    
case ARM_AM::da: return ARM::STMDA0
;
270
1.17k
    
case ARM_AM::db: return ARM::STMDB0
;
271
1.17k
    
case ARM_AM::ib: return ARM::STMIB26
;
272
0
    }
273
441
  case ARM::tLDRi:
274
441
  case ARM::tLDRspi:
275
441
    // tLDMIA is writeback-only - unless the base register is in the input
276
441
    // reglist.
277
441
    ++NumLDMGened;
278
441
    switch (Mode) {
279
441
    
default: 0
llvm_unreachable0
("Unhandled submode!");
280
441
    case ARM_AM::ia: return ARM::tLDMIA;
281
0
    }
282
330
  case ARM::tSTRi:
283
330
  case ARM::tSTRspi:
284
330
    // There is no non-writeback tSTMIA either.
285
330
    ++NumSTMGened;
286
330
    switch (Mode) {
287
330
    
default: 0
llvm_unreachable0
("Unhandled submode!");
288
330
    case ARM_AM::ia: return ARM::tSTMIA_UPD;
289
0
    }
290
5.71k
  case ARM::t2LDRi8:
291
5.71k
  case ARM::t2LDRi12:
292
5.71k
    ++NumLDMGened;
293
5.71k
    switch (Mode) {
294
5.71k
    
default: 0
llvm_unreachable0
("Unhandled submode!");
295
5.71k
    case ARM_AM::ia: return ARM::t2LDMIA;
296
5.71k
    
case ARM_AM::db: return ARM::t2LDMDB0
;
297
0
    }
298
37.2k
  case ARM::t2STRi8:
299
37.2k
  case ARM::t2STRi12:
300
37.2k
    ++NumSTMGened;
301
37.2k
    switch (Mode) {
302
37.2k
    
default: 0
llvm_unreachable0
("Unhandled submode!");
303
37.2k
    case ARM_AM::ia: return ARM::t2STMIA;
304
37.2k
    
case ARM_AM::db: return ARM::t2STMDB0
;
305
0
    }
306
61
  case ARM::VLDRS:
307
61
    ++NumVLDMGened;
308
61
    switch (Mode) {
309
61
    
default: 0
llvm_unreachable0
("Unhandled submode!");
310
61
    case ARM_AM::ia: return ARM::VLDMSIA;
311
61
    
case ARM_AM::db: return 00
; // Only VLDMSDB_UPD exists.
312
0
    }
313
38
  case ARM::VSTRS:
314
38
    ++NumVSTMGened;
315
38
    switch (Mode) {
316
38
    
default: 0
llvm_unreachable0
("Unhandled submode!");
317
38
    case ARM_AM::ia: return ARM::VSTMSIA;
318
38
    
case ARM_AM::db: return 00
; // Only VSTMSDB_UPD exists.
319
0
    }
320
288
  case ARM::VLDRD:
321
288
    ++NumVLDMGened;
322
288
    switch (Mode) {
323
288
    
default: 0
llvm_unreachable0
("Unhandled submode!");
324
288
    case ARM_AM::ia: return ARM::VLDMDIA;
325
288
    
case ARM_AM::db: return 00
; // Only VLDMDDB_UPD exists.
326
0
    }
327
135
  case ARM::VSTRD:
328
135
    ++NumVSTMGened;
329
135
    switch (Mode) {
330
135
    
default: 0
llvm_unreachable0
("Unhandled submode!");
331
135
    case ARM_AM::ia: return ARM::VSTMDIA;
332
135
    
case ARM_AM::db: return 00
; // Only VSTMDDB_UPD exists.
333
135
    }
334
46.2k
  }
335
46.2k
}
336
337
846
static ARM_AM::AMSubMode getLoadStoreMultipleSubMode(unsigned Opcode) {
338
846
  switch (Opcode) {
339
846
  
default: 0
llvm_unreachable0
("Unhandled opcode!");
340
846
  case ARM::LDMIA_RET:
341
792
  case ARM::LDMIA:
342
792
  case ARM::LDMIA_UPD:
343
792
  case ARM::STMIA:
344
792
  case ARM::STMIA_UPD:
345
792
  case ARM::tLDMIA:
346
792
  case ARM::tLDMIA_UPD:
347
792
  case ARM::tSTMIA_UPD:
348
792
  case ARM::t2LDMIA_RET:
349
792
  case ARM::t2LDMIA:
350
792
  case ARM::t2LDMIA_UPD:
351
792
  case ARM::t2STMIA:
352
792
  case ARM::t2STMIA_UPD:
353
792
  case ARM::VLDMSIA:
354
792
  case ARM::VLDMSIA_UPD:
355
792
  case ARM::VSTMSIA:
356
792
  case ARM::VSTMSIA_UPD:
357
792
  case ARM::VLDMDIA:
358
792
  case ARM::VLDMDIA_UPD:
359
792
  case ARM::VSTMDIA:
360
792
  case ARM::VSTMDIA_UPD:
361
792
    return ARM_AM::ia;
362
792
363
792
  case ARM::LDMDA:
364
0
  case ARM::LDMDA_UPD:
365
0
  case ARM::STMDA:
366
0
  case ARM::STMDA_UPD:
367
0
    return ARM_AM::da;
368
0
369
0
  case ARM::LDMDB:
370
0
  case ARM::LDMDB_UPD:
371
0
  case ARM::STMDB:
372
0
  case ARM::STMDB_UPD:
373
0
  case ARM::t2LDMDB:
374
0
  case ARM::t2LDMDB_UPD:
375
0
  case ARM::t2STMDB:
376
0
  case ARM::t2STMDB_UPD:
377
0
  case ARM::VLDMSDB_UPD:
378
0
  case ARM::VSTMSDB_UPD:
379
0
  case ARM::VLDMDDB_UPD:
380
0
  case ARM::VSTMDDB_UPD:
381
0
    return ARM_AM::db;
382
0
383
54
  case ARM::LDMIB:
384
54
  case ARM::LDMIB_UPD:
385
54
  case ARM::STMIB:
386
54
  case ARM::STMIB_UPD:
387
54
    return ARM_AM::ib;
388
846
  }
389
846
}
390
391
300k
static bool isT1i32Load(unsigned Opc) {
392
300k
  return Opc == ARM::tLDRi || 
Opc == ARM::tLDRspi299k
;
393
300k
}
394
395
296k
static bool isT2i32Load(unsigned Opc) {
396
296k
  return Opc == ARM::t2LDRi12 || 
Opc == ARM::t2LDRi8190k
;
397
296k
}
398
399
307k
static bool isi32Load(unsigned Opc) {
400
307k
  return Opc == ARM::LDRi12 || 
isT1i32Load(Opc)300k
||
isT2i32Load(Opc)296k
;
401
307k
}
402
403
64.6k
static bool isT1i32Store(unsigned Opc) {
404
64.6k
  return Opc == ARM::tSTRi || 
Opc == ARM::tSTRspi64.4k
;
405
64.6k
}
406
407
63.3k
static bool isT2i32Store(unsigned Opc) {
408
63.3k
  return Opc == ARM::t2STRi12 || 
Opc == ARM::t2STRi85.98k
;
409
63.3k
}
410
411
69.2k
static bool isi32Store(unsigned Opc) {
412
69.2k
  return Opc == ARM::STRi12 || 
isT1i32Store(Opc)64.6k
||
isT2i32Store(Opc)63.3k
;
413
69.2k
}
414
415
145k
static bool isLoadSingle(unsigned Opc) {
416
145k
  return isi32Load(Opc) || 
Opc == ARM::VLDRS104k
||
Opc == ARM::VLDRD104k
;
417
145k
}
418
419
9
static unsigned getImmScale(unsigned Opc) {
420
9
  switch (Opc) {
421
9
  
default: 0
llvm_unreachable0
("Unhandled opcode!");
422
9
  case ARM::tLDRi:
423
9
  case ARM::tSTRi:
424
9
  case ARM::tLDRspi:
425
9
  case ARM::tSTRspi:
426
9
    return 1;
427
9
  case ARM::tLDRHi:
428
0
  case ARM::tSTRHi:
429
0
    return 2;
430
0
  case ARM::tLDRBi:
431
0
  case ARM::tSTRBi:
432
0
    return 4;
433
9
  }
434
9
}
435
436
137k
static unsigned getLSMultipleTransferSize(const MachineInstr *MI) {
437
137k
  switch (MI->getOpcode()) {
438
137k
  
default: return 00
;
439
137k
  case ARM::LDRi12:
440
132k
  case ARM::STRi12:
441
132k
  case ARM::tLDRi:
442
132k
  case ARM::tSTRi:
443
132k
  case ARM::tLDRspi:
444
132k
  case ARM::tSTRspi:
445
132k
  case ARM::t2LDRi8:
446
132k
  case ARM::t2LDRi12:
447
132k
  case ARM::t2STRi8:
448
132k
  case ARM::t2STRi12:
449
132k
  case ARM::VLDRS:
450
132k
  case ARM::VSTRS:
451
132k
    return 4;
452
132k
  case ARM::VLDRD:
453
4.10k
  case ARM::VSTRD:
454
4.10k
    return 8;
455
4.10k
  case ARM::LDMIA:
456
773
  case ARM::LDMDA:
457
773
  case ARM::LDMDB:
458
773
  case ARM::LDMIB:
459
773
  case ARM::STMIA:
460
773
  case ARM::STMDA:
461
773
  case ARM::STMDB:
462
773
  case ARM::STMIB:
463
773
  case ARM::tLDMIA:
464
773
  case ARM::tLDMIA_UPD:
465
773
  case ARM::tSTMIA_UPD:
466
773
  case ARM::t2LDMIA:
467
773
  case ARM::t2LDMDB:
468
773
  case ARM::t2STMIA:
469
773
  case ARM::t2STMDB:
470
773
  case ARM::VLDMSIA:
471
773
  case ARM::VSTMSIA:
472
773
    return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 4;
473
773
  case ARM::VLDMDIA:
474
73
  case ARM::VSTMDIA:
475
73
    return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 8;
476
137k
  }
477
137k
}
478
479
/// Update future uses of the base register with the offset introduced
480
/// due to writeback. This function only works on Thumb1.
481
void ARMLoadStoreOpt::UpdateBaseRegUses(MachineBasicBlock &MBB,
482
                                        MachineBasicBlock::iterator MBBI,
483
                                        const DebugLoc &DL, unsigned Base,
484
                                        unsigned WordOffset,
485
                                        ARMCC::CondCodes Pred,
486
11
                                        unsigned PredReg) {
487
11
  assert(isThumb1 && "Can only update base register uses for Thumb1!");
488
11
  // Start updating any instructions with immediate offsets. Insert a SUB before
489
11
  // the first non-updateable instruction (if any).
490
28
  for (; MBBI != MBB.end(); 
++MBBI17
) {
491
27
    bool InsertSub = false;
492
27
    unsigned Opc = MBBI->getOpcode();
493
27
494
27
    if (MBBI->readsRegister(Base)) {
495
10
      int Offset;
496
10
      bool IsLoad =
497
10
        Opc == ARM::tLDRi || 
Opc == ARM::tLDRHi4
||
Opc == ARM::tLDRBi4
;
498
10
      bool IsStore =
499
10
        Opc == ARM::tSTRi || 
Opc == ARM::tSTRHi7
||
Opc == ARM::tSTRBi7
;
500
10
501
10
      if (IsLoad || 
IsStore4
) {
502
9
        // Loads and stores with immediate offsets can be updated, but only if
503
9
        // the new offset isn't negative.
504
9
        // The MachineOperand containing the offset immediate is the last one
505
9
        // before predicates.
506
9
        MachineOperand &MO =
507
9
          MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
508
9
        // The offsets are scaled by 1, 2 or 4 depending on the Opcode.
509
9
        Offset = MO.getImm() - WordOffset * getImmScale(Opc);
510
9
511
9
        // If storing the base register, it needs to be reset first.
512
9
        unsigned InstrSrcReg = getLoadStoreRegOp(*MBBI).getReg();
513
9
514
9
        if (Offset >= 0 && !(IsStore && 
InstrSrcReg == Base3
))
515
9
          MO.setImm(Offset);
516
0
        else
517
0
          InsertSub = true;
518
9
      } else 
if (1
(1
Opc == ARM::tSUBi81
||
Opc == ARM::tADDi81
) &&
519
1
                 
!definesCPSR(*MBBI)0
) {
520
0
        // SUBS/ADDS using this register, with a dead def of the CPSR.
521
0
        // Merge it with the update; if the merged offset is too large,
522
0
        // insert a new sub instead.
523
0
        MachineOperand &MO =
524
0
          MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
525
0
        Offset = (Opc == ARM::tSUBi8) ?
526
0
          MO.getImm() + WordOffset * 4 :
527
0
          MO.getImm() - WordOffset * 4 ;
528
0
        if (Offset >= 0 && TL->isLegalAddImmediate(Offset)) {
529
0
          // FIXME: Swap ADDS<->SUBS if Offset < 0, erase instruction if
530
0
          // Offset == 0.
531
0
          MO.setImm(Offset);
532
0
          // The base register has now been reset, so exit early.
533
0
          return;
534
0
        } else {
535
0
          InsertSub = true;
536
0
        }
537
1
      } else {
538
1
        // Can't update the instruction.
539
1
        InsertSub = true;
540
1
      }
541
17
    } else if (definesCPSR(*MBBI) || MBBI->isCall() || 
MBBI->isBranch()12
) {
542
5
      // Since SUBS sets the condition flags, we can't place the base reset
543
5
      // after an instruction that has a live CPSR def.
544
5
      // The base register might also contain an argument for a function call.
545
5
      InsertSub = true;
546
5
    }
547
27
548
27
    if (InsertSub) {
549
6
      // An instruction above couldn't be updated, so insert a sub.
550
6
      BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base)
551
6
          .add(t1CondCodeOp(true))
552
6
          .addReg(Base)
553
6
          .addImm(WordOffset * 4)
554
6
          .addImm(Pred)
555
6
          .addReg(PredReg);
556
6
      return;
557
6
    }
558
21
559
21
    if (MBBI->killsRegister(Base) || 
MBBI->definesRegister(Base)17
)
560
4
      // Register got killed. Stop updating.
561
4
      return;
562
21
  }
563
11
564
11
  // End of block was reached.
565
11
  
if (1
MBB.succ_size() > 01
) {
566
1
    // FIXME: Because of a bug, live registers are sometimes missing from
567
1
    // the successor blocks' live-in sets. This means we can't trust that
568
1
    // information and *always* have to reset at the end of a block.
569
1
    // See PR21029.
570
1
    if (MBBI != MBB.end()) 
--MBBI0
;
571
1
    BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base)
572
1
        .add(t1CondCodeOp(true))
573
1
        .addReg(Base)
574
1
        .addImm(WordOffset * 4)
575
1
        .addImm(Pred)
576
1
        .addReg(PredReg);
577
1
  }
578
1
}
579
580
/// Return the first register of class \p RegClass that is not in \p Regs.
581
225
unsigned ARMLoadStoreOpt::findFreeReg(const TargetRegisterClass &RegClass) {
582
225
  if (!RegClassInfoValid) {
583
184
    RegClassInfo.runOnMachineFunction(*MF);
584
184
    RegClassInfoValid = true;
585
184
  }
586
225
587
225
  for (unsigned Reg : RegClassInfo.getOrder(&RegClass))
588
742
    if (!LiveRegs.contains(Reg))
589
211
      return Reg;
590
225
  
return 014
;
591
225
}
592
593
/// Compute live registers just before instruction \p Before (in normal schedule
594
/// direction). Computes backwards so multiple queries in the same block must
595
/// come in reverse order.
596
void ARMLoadStoreOpt::moveLiveRegsBefore(const MachineBasicBlock &MBB,
597
225
    MachineBasicBlock::const_iterator Before) {
598
225
  // Initialize if we never queried in this block.
599
225
  if (!LiveRegsValid) {
600
206
    LiveRegs.init(*TRI);
601
206
    LiveRegs.addLiveOuts(MBB);
602
206
    LiveRegPos = MBB.end();
603
206
    LiveRegsValid = true;
604
206
  }
605
225
  // Move backward just before the "Before" position.
606
2.77k
  while (LiveRegPos != Before) {
607
2.54k
    --LiveRegPos;
608
2.54k
    LiveRegs.stepBackward(*LiveRegPos);
609
2.54k
  }
610
225
}
611
612
static bool ContainsReg(const ArrayRef<std::pair<unsigned, bool>> &Regs,
613
286
                        unsigned Reg) {
614
286
  for (const std::pair<unsigned, bool> &R : Regs)
615
877
    if (R.first == Reg)
616
8
      return true;
617
286
  
return false278
;
618
286
}
619
620
/// Create and insert a LDM or STM with Base as base register and registers in
621
/// Regs as the register operands that would be loaded / stored.  It returns
622
/// true if the transformation is done.
623
MachineInstr *ARMLoadStoreOpt::CreateLoadStoreMulti(
624
    MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
625
    int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
626
    ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
627
    ArrayRef<std::pair<unsigned, bool>> Regs,
628
1.66k
    ArrayRef<MachineInstr*> Instrs) {
629
1.66k
  unsigned NumRegs = Regs.size();
630
1.66k
  assert(NumRegs > 1);
631
1.66k
632
1.66k
  // For Thumb1 targets, it might be necessary to clobber the CPSR to merge.
633
1.66k
  // Compute liveness information for that register to make the decision.
634
1.66k
  bool SafeToClobberCPSR = !isThumb1 ||
635
1.66k
    (MBB.computeRegisterLiveness(TRI, ARM::CPSR, InsertBefore, 20) ==
636
283
     MachineBasicBlock::LQR_Dead);
637
1.66k
638
1.66k
  bool Writeback = isThumb1; // Thumb1 LDM/STM have base reg writeback.
639
1.66k
640
1.66k
  // Exception: If the base register is in the input reglist, Thumb1 LDM is
641
1.66k
  // non-writeback.
642
1.66k
  // It's also not possible to merge an STR of the base register in Thumb1.
643
1.66k
  if (isThumb1 && 
ContainsReg(Regs, Base)283
) {
644
6
    assert(Base != ARM::SP && "Thumb1 does not allow SP in register list");
645
6
    if (Opcode == ARM::tLDRi)
646
4
      Writeback = false;
647
2
    else if (Opcode == ARM::tSTRi)
648
2
      return nullptr;
649
1.66k
  }
650
1.66k
651
1.66k
  ARM_AM::AMSubMode Mode = ARM_AM::ia;
652
1.66k
  // VFP and Thumb2 do not support IB or DA modes. Thumb1 only supports IA.
653
1.66k
  bool isNotVFP = isi32Load(Opcode) || 
isi32Store(Opcode)952
;
654
1.66k
  bool haveIBAndDA = isNotVFP && 
!isThumb21.54k
&&
!isThumb1756
;
655
1.66k
656
1.66k
  if (Offset == 4 && 
haveIBAndDA99
) {
657
56
    Mode = ARM_AM::ib;
658
1.61k
  } else if (Offset == -4 * (int)NumRegs + 4 && 
haveIBAndDA0
) {
659
0
    Mode = ARM_AM::da;
660
1.61k
  } else if (Offset == -4 * (int)NumRegs && 
isNotVFP1
&&
!isThumb10
) {
661
0
    // VLDM/VSTM do not support DB mode without also updating the base reg.
662
0
    Mode = ARM_AM::db;
663
1.61k
  } else if (Offset != 0 || 
Opcode == ARM::tLDRspi651
||
Opcode == ARM::tSTRspi649
) {
664
967
    // Check if this is a supported opcode before inserting instructions to
665
967
    // calculate a new base register.
666
967
    if (!getLoadStoreMultipleOpcode(Opcode, Mode)) 
return nullptr0
;
667
967
668
967
    // If starting offset isn't zero, insert a MI to materialize a new base.
669
967
    // But only do so if it is cost effective, i.e. merging more than two
670
967
    // loads / stores.
671
967
    if (NumRegs <= 2)
672
285
      return nullptr;
673
682
674
682
    // On Thumb1, it's not worth materializing a new base register without
675
682
    // clobbering the CPSR (i.e. not using ADDS/SUBS).
676
682
    if (!SafeToClobberCPSR)
677
0
      return nullptr;
678
682
679
682
    unsigned NewBase;
680
682
    if (isi32Load(Opcode)) {
681
457
      // If it is a load, then just use one of the destination registers
682
457
      // as the new base. Will no longer be writeback in Thumb1.
683
457
      NewBase = Regs[NumRegs-1].first;
684
457
      Writeback = false;
685
457
    } else {
686
225
      // Find a free register that we can use as scratch register.
687
225
      moveLiveRegsBefore(MBB, InsertBefore);
688
225
      // The merged instruction does not exist yet but will use several Regs if
689
225
      // it is a Store.
690
225
      if (!isLoadSingle(Opcode))
691
218
        for (const std::pair<unsigned, bool> &R : Regs)
692
740
          LiveRegs.addReg(R.first);
693
225
694
225
      NewBase = findFreeReg(isThumb1 ? 
ARM::tGPRRegClass26
:
ARM::GPRRegClass199
);
695
225
      if (NewBase == 0)
696
14
        return nullptr;
697
668
    }
698
668
699
668
    int BaseOpc =
700
668
      isThumb2 ? 
ARM::t2ADDri318
:
701
668
      
(350
isThumb1350
&&
Base == ARM::SP158
) ?
ARM::tADDrSPi144
:
702
350
      
(206
isThumb1206
&&
Offset < 814
) ?
ARM::tADDi33
:
703
206
      
isThumb1 203
?
ARM::tADDi811
:
ARM::ADDri192
;
704
668
705
668
    if (Offset < 0) {
706
3
      Offset = - Offset;
707
3
      BaseOpc =
708
3
        isThumb2 ? ARM::t2SUBri :
709
3
        
(0
isThumb10
&&
Offset < 80
&&
Base != ARM::SP0
) ?
ARM::tSUBi30
:
710
0
        isThumb1 ? ARM::tSUBi8  : ARM::SUBri;
711
3
    }
712
668
713
668
    if (!TL->isLegalAddImmediate(Offset))
714
71
      // FIXME: Try add with register operand?
715
71
      return nullptr; // Probably not worth it then.
716
597
717
597
    // We can only append a kill flag to the add/sub input if the value is not
718
597
    // used in the register list of the stm as well.
719
597
    bool KillOldBase = BaseKill &&
720
597
      
(15
!isi32Store(Opcode)15
||
!ContainsReg(Regs, Base)3
);
721
597
722
597
    if (isThumb1) {
723
98
      // Thumb1: depending on immediate size, use either
724
98
      //   ADDS NewBase, Base, #imm3
725
98
      // or
726
98
      //   MOV  NewBase, Base
727
98
      //   ADDS NewBase, #imm8.
728
98
      if (Base != NewBase &&
729
98
          
(95
BaseOpc == ARM::tADDi895
||
BaseOpc == ARM::tSUBi886
)) {
730
9
        // Need to insert a MOV to the new base first.
731
9
        if (isARMLowRegister(NewBase) && isARMLowRegister(Base) &&
732
9
            !STI->hasV6Ops()) {
733
5
          // thumbv4t doesn't have lo->lo copies, and we can't predicate tMOVSr
734
5
          if (Pred != ARMCC::AL)
735
0
            return nullptr;
736
5
          BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVSr), NewBase)
737
5
            .addReg(Base, getKillRegState(KillOldBase));
738
5
        } else
739
4
          BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVr), NewBase)
740
4
              .addReg(Base, getKillRegState(KillOldBase))
741
4
              .add(predOps(Pred, PredReg));
742
9
743
9
        // The following ADDS/SUBS becomes an update.
744
9
        Base = NewBase;
745
9
        KillOldBase = true;
746
9
      }
747
98
      if (BaseOpc == ARM::tADDrSPi) {
748
84
        assert(Offset % 4 == 0 && "tADDrSPi offset is scaled by 4");
749
84
        BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
750
84
            .addReg(Base, getKillRegState(KillOldBase))
751
84
            .addImm(Offset / 4)
752
84
            .add(predOps(Pred, PredReg));
753
84
      } else
754
14
        BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
755
14
            .add(t1CondCodeOp(true))
756
14
            .addReg(Base, getKillRegState(KillOldBase))
757
14
            .addImm(Offset)
758
14
            .add(predOps(Pred, PredReg));
759
499
    } else {
760
499
      BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
761
499
          .addReg(Base, getKillRegState(KillOldBase))
762
499
          .addImm(Offset)
763
499
          .add(predOps(Pred, PredReg))
764
499
          .add(condCodeOp());
765
499
    }
766
597
    Base = NewBase;
767
597
    BaseKill = true; // New base is always killed straight away.
768
597
  }
769
1.66k
770
1.66k
  bool isDef = isLoadSingle(Opcode);
771
1.29k
772
1.29k
  // Get LS multiple opcode. Note that for Thumb1 this might be an opcode with
773
1.29k
  // base register writeback.
774
1.29k
  Opcode = getLoadStoreMultipleOpcode(Opcode, Mode);
775
1.29k
  if (!Opcode)
776
0
    return nullptr;
777
1.29k
778
1.29k
  // Check if a Thumb1 LDM/STM merge is safe. This is the case if:
779
1.29k
  // - There is no writeback (LDM of base register),
780
1.29k
  // - the base register is killed by the merged instruction,
781
1.29k
  // - or it's safe to overwrite the condition flags, i.e. to insert a SUBS
782
1.29k
  //   to reset the base register.
783
1.29k
  // Otherwise, don't merge.
784
1.29k
  // It's safe to return here since the code to materialize a new base register
785
1.29k
  // above is also conditional on SafeToClobberCPSR.
786
1.29k
  if (isThumb1 && 
!SafeToClobberCPSR131
&&
Writeback1
&&
!BaseKill1
)
787
1
    return nullptr;
788
1.29k
789
1.29k
  MachineInstrBuilder MIB;
790
1.29k
791
1.29k
  if (Writeback) {
792
50
    assert(isThumb1 && "expected Writeback only inThumb1");
793
50
    if (Opcode == ARM::tLDMIA) {
794
9
      assert(!(ContainsReg(Regs, Base)) && "Thumb1 can't LDM ! with Base in Regs");
795
9
      // Update tLDMIA with writeback if necessary.
796
9
      Opcode = ARM::tLDMIA_UPD;
797
9
    }
798
50
799
50
    MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
800
50
801
50
    // Thumb1: we might need to set base writeback when building the MI.
802
50
    MIB.addReg(Base, getDefRegState(true))
803
50
       .addReg(Base, getKillRegState(BaseKill));
804
50
805
50
    // The base isn't dead after a merged instruction with writeback.
806
50
    // Insert a sub instruction after the newly formed instruction to reset.
807
50
    if (!BaseKill)
808
11
      UpdateBaseRegUses(MBB, InsertBefore, DL, Base, NumRegs, Pred, PredReg);
809
1.24k
  } else {
810
1.24k
    // No writeback, simply build the MachineInstr.
811
1.24k
    MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
812
1.24k
    MIB.addReg(Base, getKillRegState(BaseKill));
813
1.24k
  }
814
1.29k
815
1.29k
  MIB.addImm(Pred).addReg(PredReg);
816
1.29k
817
1.29k
  for (const std::pair<unsigned, bool> &R : Regs)
818
4.39k
    MIB.addReg(R.first, getDefRegState(isDef) | getKillRegState(R.second));
819
1.29k
820
1.29k
  MIB.cloneMergedMemRefs(Instrs);
821
1.29k
822
1.29k
  return MIB.getInstr();
823
1.29k
}
824
825
MachineInstr *ARMLoadStoreOpt::CreateLoadStoreDouble(
826
    MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
827
    int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
828
    ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
829
    ArrayRef<std::pair<unsigned, bool>> Regs,
830
15.9k
    ArrayRef<MachineInstr*> Instrs) const {
831
15.9k
  bool IsLoad = isi32Load(Opcode);
832
15.9k
  assert((IsLoad || isi32Store(Opcode)) && "Must have integer load or store");
833
15.9k
  unsigned LoadStoreOpcode = IsLoad ? 
ARM::t2LDRDi81.51k
:
ARM::t2STRDi814.4k
;
834
15.9k
835
15.9k
  assert(Regs.size() == 2);
836
15.9k
  MachineInstrBuilder MIB = BuildMI(MBB, InsertBefore, DL,
837
15.9k
                                    TII->get(LoadStoreOpcode));
838
15.9k
  if (IsLoad) {
839
1.51k
    MIB.addReg(Regs[0].first, RegState::Define)
840
1.51k
       .addReg(Regs[1].first, RegState::Define);
841
14.4k
  } else {
842
14.4k
    MIB.addReg(Regs[0].first, getKillRegState(Regs[0].second))
843
14.4k
       .addReg(Regs[1].first, getKillRegState(Regs[1].second));
844
14.4k
  }
845
15.9k
  MIB.addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
846
15.9k
  MIB.cloneMergedMemRefs(Instrs);
847
15.9k
  return MIB.getInstr();
848
15.9k
}
849
850
/// Call MergeOps and update MemOps and merges accordingly on success.
851
17.6k
MachineInstr *ARMLoadStoreOpt::MergeOpsUpdate(const MergeCandidate &Cand) {
852
17.6k
  const MachineInstr *First = Cand.Instrs.front();
853
17.6k
  unsigned Opcode = First->getOpcode();
854
17.6k
  bool IsLoad = isLoadSingle(Opcode);
855
17.6k
  SmallVector<std::pair<unsigned, bool>, 8> Regs;
856
17.6k
  SmallVector<unsigned, 4> ImpDefs;
857
17.6k
  DenseSet<unsigned> KilledRegs;
858
17.6k
  DenseSet<unsigned> UsedRegs;
859
17.6k
  // Determine list of registers and list of implicit super-register defs.
860
37.1k
  for (const MachineInstr *MI : Cand.Instrs) {
861
37.1k
    const MachineOperand &MO = getLoadStoreRegOp(*MI);
862
37.1k
    unsigned Reg = MO.getReg();
863
37.1k
    bool IsKill = MO.isKill();
864
37.1k
    if (IsKill)
865
14.9k
      KilledRegs.insert(Reg);
866
37.1k
    Regs.push_back(std::make_pair(Reg, IsKill));
867
37.1k
    UsedRegs.insert(Reg);
868
37.1k
869
37.1k
    if (IsLoad) {
870
5.63k
      // Collect any implicit defs of super-registers, after merging we can't
871
5.63k
      // be sure anymore that we properly preserved these live ranges and must
872
5.63k
      // removed these implicit operands.
873
5.63k
      for (const MachineOperand &MO : MI->implicit_operands()) {
874
155
        if (!MO.isReg() || !MO.isDef() || 
MO.isDead()99
)
875
56
          continue;
876
99
        assert(MO.isImplicit());
877
99
        unsigned DefReg = MO.getReg();
878
99
879
99
        if (is_contained(ImpDefs, DefReg))
880
21
          continue;
881
78
        // We can ignore cases where the super-reg is read and written.
882
78
        if (MI->readsRegister(DefReg))
883
35
          continue;
884
43
        ImpDefs.push_back(DefReg);
885
43
      }
886
5.63k
    }
887
37.1k
  }
888
17.6k
889
17.6k
  // Attempt the merge.
890
17.6k
  using iterator = MachineBasicBlock::iterator;
891
17.6k
892
17.6k
  MachineInstr *LatestMI = Cand.Instrs[Cand.LatestMIIdx];
893
17.6k
  iterator InsertBefore = std::next(iterator(LatestMI));
894
17.6k
  MachineBasicBlock &MBB = *LatestMI->getParent();
895
17.6k
  unsigned Offset = getMemoryOpOffset(*First);
896
17.6k
  unsigned Base = getLoadStoreBaseOp(*First).getReg();
897
17.6k
  bool BaseKill = LatestMI->killsRegister(Base);
898
17.6k
  unsigned PredReg = 0;
899
17.6k
  ARMCC::CondCodes Pred = getInstrPredicate(*First, PredReg);
900
17.6k
  DebugLoc DL = First->getDebugLoc();
901
17.6k
  MachineInstr *Merged = nullptr;
902
17.6k
  if (Cand.CanMergeToLSDouble)
903
15.9k
    Merged = CreateLoadStoreDouble(MBB, InsertBefore, Offset, Base, BaseKill,
904
15.9k
                                   Opcode, Pred, PredReg, DL, Regs,
905
15.9k
                                   Cand.Instrs);
906
17.6k
  if (!Merged && 
Cand.CanMergeToLSMulti1.66k
)
907
1.66k
    Merged = CreateLoadStoreMulti(MBB, InsertBefore, Offset, Base, BaseKill,
908
1.66k
                                  Opcode, Pred, PredReg, DL, Regs, Cand.Instrs);
909
17.6k
  if (!Merged)
910
373
    return nullptr;
911
17.2k
912
17.2k
  // Determine earliest instruction that will get removed. We then keep an
913
17.2k
  // iterator just above it so the following erases don't invalidated it.
914
17.2k
  iterator EarliestI(Cand.Instrs[Cand.EarliestMIIdx]);
915
17.2k
  bool EarliestAtBegin = false;
916
17.2k
  if (EarliestI == MBB.begin()) {
917
884
    EarliestAtBegin = true;
918
16.3k
  } else {
919
16.3k
    EarliestI = std::prev(EarliestI);
920
16.3k
  }
921
17.2k
922
17.2k
  // Remove instructions which have been merged.
923
17.2k
  for (MachineInstr *MI : Cand.Instrs)
924
36.2k
    MBB.erase(MI);
925
17.2k
926
17.2k
  // Determine range between the earliest removed instruction and the new one.
927
17.2k
  if (EarliestAtBegin)
928
884
    EarliestI = MBB.begin();
929
16.3k
  else
930
16.3k
    EarliestI = std::next(EarliestI);
931
17.2k
  auto FixupRange = make_range(EarliestI, iterator(Merged));
932
17.2k
933
17.2k
  if (isLoadSingle(Opcode)) {
934
2.07k
    // If the previous loads defined a super-reg, then we have to mark earlier
935
2.07k
    // operands undef; Replicate the super-reg def on the merged instruction.
936
2.07k
    for (MachineInstr &MI : FixupRange) {
937
432
      for (unsigned &ImpDefReg : ImpDefs) {
938
9
        for (MachineOperand &MO : MI.implicit_operands()) {
939
2
          if (!MO.isReg() || MO.getReg() != ImpDefReg)
940
0
            continue;
941
2
          if (MO.readsReg())
942
1
            MO.setIsUndef();
943
1
          else if (MO.isDef())
944
1
            ImpDefReg = 0;
945
2
        }
946
9
      }
947
432
    }
948
2.07k
949
2.07k
    MachineInstrBuilder MIB(*Merged->getParent()->getParent(), Merged);
950
2.07k
    for (unsigned ImpDef : ImpDefs)
951
29
      MIB.addReg(ImpDef, RegState::ImplicitDefine);
952
15.1k
  } else {
953
15.1k
    // Remove kill flags: We are possibly storing the values later now.
954
15.1k
    assert(isi32Store(Opcode) || Opcode == ARM::VSTRS || Opcode == ARM::VSTRD);
955
15.1k
    for (MachineInstr &MI : FixupRange) {
956
1.99k
      for (MachineOperand &MO : MI.uses()) {
957
1.99k
        if (!MO.isReg() || 
!MO.isKill()1.19k
)
958
1.95k
          continue;
959
45
        if (UsedRegs.count(MO.getReg()))
960
4
          MO.setIsKill(false);
961
45
      }
962
405
    }
963
15.1k
    assert(ImpDefs.empty());
964
15.1k
  }
965
17.2k
966
17.2k
  return Merged;
967
17.2k
}
968
969
76.9k
static bool isValidLSDoubleOffset(int Offset) {
970
76.9k
  unsigned Value = abs(Offset);
971
76.9k
  // t2LDRDi8/t2STRDi8 supports an 8 bit immediate which is internally
972
76.9k
  // multiplied by 4.
973
76.9k
  return (Value % 4) == 0 && 
Value < 102476.9k
;
974
76.9k
}
975
976
/// Return true for loads/stores that can be combined to a double/multi
977
/// operation without increasing the requirements for alignment.
978
static bool mayCombineMisaligned(const TargetSubtargetInfo &STI,
979
46
                                 const MachineInstr &MI) {
980
46
  // vldr/vstr trap on misaligned pointers anyway, forming vldm makes no
981
46
  // difference.
982
46
  unsigned Opcode = MI.getOpcode();
983
46
  if (!isi32Load(Opcode) && 
!isi32Store(Opcode)13
)
984
3
    return true;
985
43
986
43
  // Stack pointer alignment is out of the programmers control so we can trust
987
43
  // SP-relative loads/stores.
988
43
  if (getLoadStoreBaseOp(MI).getReg() == ARM::SP &&
989
43
      
STI.getFrameLowering()->getTransientStackAlignment() >= 44
)
990
4
    return true;
991
39
  return false;
992
39
}
993
994
/// Find candidates for load/store multiple merge in list of MemOpQueueEntries.
995
75.9k
void ARMLoadStoreOpt::FormCandidates(const MemOpQueue &MemOps) {
996
75.9k
  const MachineInstr *FirstMI = MemOps[0].MI;
997
75.9k
  unsigned Opcode = FirstMI->getOpcode();
998
75.9k
  bool isNotVFP = isi32Load(Opcode) || 
isi32Store(Opcode)37.0k
;
999
75.9k
  unsigned Size = getLSMultipleTransferSize(FirstMI);
1000
75.9k
1001
75.9k
  unsigned SIndex = 0;
1002
75.9k
  unsigned EIndex = MemOps.size();
1003
88.0k
  do {
1004
88.0k
    // Look at the first instruction.
1005
88.0k
    const MachineInstr *MI = MemOps[SIndex].MI;
1006
88.0k
    int Offset = MemOps[SIndex].Offset;
1007
88.0k
    const MachineOperand &PMO = getLoadStoreRegOp(*MI);
1008
88.0k
    unsigned PReg = PMO.getReg();
1009
88.0k
    unsigned PRegNum = PMO.isUndef() ? 
std::numeric_limits<unsigned>::max()0
1010
88.0k
                                     : TRI->getEncodingValue(PReg);
1011
88.0k
    unsigned Latest = SIndex;
1012
88.0k
    unsigned Earliest = SIndex;
1013
88.0k
    unsigned Count = 1;
1014
88.0k
    bool CanMergeToLSDouble =
1015
88.0k
      STI->isThumb2() && 
isNotVFP77.8k
&&
isValidLSDoubleOffset(Offset)76.9k
;
1016
88.0k
    // ARM errata 602117: LDRD with base in list may result in incorrect base
1017
88.0k
    // register when interrupted or faulted.
1018
88.0k
    if (STI->isCortexM3() && 
isi32Load(Opcode)618
&&
1019
88.0k
        
PReg == getLoadStoreBaseOp(*MI).getReg()361
)
1020
7
      CanMergeToLSDouble = false;
1021
88.0k
1022
88.0k
    bool CanMergeToLSMulti = true;
1023
88.0k
    // On swift vldm/vstm starting with an odd register number as that needs
1024
88.0k
    // more uops than single vldrs.
1025
88.0k
    if (STI->hasSlowOddRegister() && 
!isNotVFP23.8k
&&
(PRegNum % 2) == 164
)
1026
5
      CanMergeToLSMulti = false;
1027
88.0k
1028
88.0k
    // LDRD/STRD do not allow SP/PC. LDM/STM do not support it or have it
1029
88.0k
    // deprecated; LDM to PC is fine but cannot happen here.
1030
88.0k
    if (PReg == ARM::SP || 
PReg == ARM::PC88.0k
)
1031
5
      CanMergeToLSMulti = CanMergeToLSDouble = false;
1032
88.0k
1033
88.0k
    // Should we be conservative?
1034
88.0k
    if (AssumeMisalignedLoadStores && 
!mayCombineMisaligned(*STI, *MI)46
)
1035
39
      CanMergeToLSMulti = CanMergeToLSDouble = false;
1036
88.0k
1037
88.0k
    // vldm / vstm limit are 32 for S variants, 16 for D variants.
1038
88.0k
    unsigned Limit;
1039
88.0k
    switch (Opcode) {
1040
88.0k
    default:
1041
85.8k
      Limit = UINT_MAX;
1042
85.8k
      break;
1043
88.0k
    case ARM::VLDRD:
1044
2.21k
    case ARM::VSTRD:
1045
2.21k
      Limit = 16;
1046
2.21k
      break;
1047
88.0k
    }
1048
88.0k
1049
88.0k
    // Merge following instructions where possible.
1050
107k
    
for (unsigned I = SIndex+1; 88.0k
I < EIndex;
++I, ++Count19.5k
) {
1051
31.6k
      int NewOffset = MemOps[I].Offset;
1052
31.6k
      if (NewOffset != Offset + (int)Size)
1053
5.18k
        break;
1054
26.5k
      const MachineOperand &MO = getLoadStoreRegOp(*MemOps[I].MI);
1055
26.5k
      unsigned Reg = MO.getReg();
1056
26.5k
      if (Reg == ARM::SP || Reg == ARM::PC)
1057
0
        break;
1058
26.5k
      if (Count == Limit)
1059
1
        break;
1060
26.5k
1061
26.5k
      // See if the current load/store may be part of a multi load/store.
1062
26.5k
      unsigned RegNum = MO.isUndef() ? 
std::numeric_limits<unsigned>::max()0
1063
26.5k
                                     : TRI->getEncodingValue(Reg);
1064
26.5k
      bool PartOfLSMulti = CanMergeToLSMulti;
1065
26.5k
      if (PartOfLSMulti) {
1066
22.9k
        // Register numbers must be in ascending order.
1067
22.9k
        if (RegNum <= PRegNum)
1068
14.5k
          PartOfLSMulti = false;
1069
8.38k
        // For VFP / NEON load/store multiples, the registers must be
1070
8.38k
        // consecutive and within the limit on the number of registers per
1071
8.38k
        // instruction.
1072
8.38k
        else if (!isNotVFP && 
RegNum != PRegNum+1389
)
1073
82
          PartOfLSMulti = false;
1074
22.9k
      }
1075
26.5k
      // See if the current load/store may be part of a double load/store.
1076
26.5k
      bool PartOfLSDouble = CanMergeToLSDouble && 
Count <= 123.0k
;
1077
26.5k
1078
26.5k
      if (!PartOfLSMulti && 
!PartOfLSDouble18.2k
)
1079
6.94k
        break;
1080
19.5k
      CanMergeToLSMulti &= PartOfLSMulti;
1081
19.5k
      CanMergeToLSDouble &= PartOfLSDouble;
1082
19.5k
      // Track MemOp with latest and earliest position (Positions are
1083
19.5k
      // counted in reverse).
1084
19.5k
      unsigned Position = MemOps[I].Position;
1085
19.5k
      if (Position < MemOps[Latest].Position)
1086
15.1k
        Latest = I;
1087
4.41k
      else if (Position > MemOps[Earliest].Position)
1088
4.39k
        Earliest = I;
1089
19.5k
      // Prepare for next MemOp.
1090
19.5k
      Offset += Size;
1091
19.5k
      PRegNum = RegNum;
1092
19.5k
    }
1093
88.0k
1094
88.0k
    // Form a candidate from the Ops collected so far.
1095
88.0k
    MergeCandidate *Candidate = new(Allocator.Allocate()) MergeCandidate;
1096
195k
    for (unsigned C = SIndex, CE = SIndex + Count; C < CE; 
++C107k
)
1097
107k
      Candidate->Instrs.push_back(MemOps[C].MI);
1098
88.0k
    Candidate->LatestMIIdx = Latest - SIndex;
1099
88.0k
    Candidate->EarliestMIIdx = Earliest - SIndex;
1100
88.0k
    Candidate->InsertPos = MemOps[Latest].Position;
1101
88.0k
    if (Count == 1)
1102
70.4k
      CanMergeToLSMulti = CanMergeToLSDouble = false;
1103
88.0k
    Candidate->CanMergeToLSMulti = CanMergeToLSMulti;
1104
88.0k
    Candidate->CanMergeToLSDouble = CanMergeToLSDouble;
1105
88.0k
    Candidates.push_back(Candidate);
1106
88.0k
    // Continue after the chain.
1107
88.0k
    SIndex += Count;
1108
88.0k
  } while (SIndex < EIndex);
1109
75.9k
}
1110
1111
static unsigned getUpdatingLSMultipleOpcode(unsigned Opc,
1112
12
                                            ARM_AM::AMSubMode Mode) {
1113
12
  switch (Opc) {
1114
12
  
default: 0
llvm_unreachable0
("Unhandled opcode!");
1115
12
  case ARM::LDMIA:
1116
2
  case ARM::LDMDA:
1117
2
  case ARM::LDMDB:
1118
2
  case ARM::LDMIB:
1119
2
    switch (Mode) {
1120
2
    
default: 0
llvm_unreachable0
("Unhandled submode!");
1121
2
    case ARM_AM::ia: return ARM::LDMIA_UPD;
1122
2
    
case ARM_AM::ib: return ARM::LDMIB_UPD0
;
1123
2
    
case ARM_AM::da: return ARM::LDMDA_UPD0
;
1124
2
    
case ARM_AM::db: return ARM::LDMDB_UPD0
;
1125
0
    }
1126
1
  case ARM::STMIA:
1127
1
  case ARM::STMDA:
1128
1
  case ARM::STMDB:
1129
1
  case ARM::STMIB:
1130
1
    switch (Mode) {
1131
1
    
default: 0
llvm_unreachable0
("Unhandled submode!");
1132
1
    case ARM_AM::ia: return ARM::STMIA_UPD;
1133
1
    
case ARM_AM::ib: return ARM::STMIB_UPD0
;
1134
1
    
case ARM_AM::da: return ARM::STMDA_UPD0
;
1135
1
    
case ARM_AM::db: return ARM::STMDB_UPD0
;
1136
0
    }
1137
2
  case ARM::t2LDMIA:
1138
2
  case ARM::t2LDMDB:
1139
2
    switch (Mode) {
1140
2
    
default: 0
llvm_unreachable0
("Unhandled submode!");
1141
2
    case ARM_AM::ia: return ARM::t2LDMIA_UPD;
1142
2
    
case ARM_AM::db: return ARM::t2LDMDB_UPD0
;
1143
0
    }
1144
4
  case ARM::t2STMIA:
1145
4
  case ARM::t2STMDB:
1146
4
    switch (Mode) {
1147
4
    
default: 0
llvm_unreachable0
("Unhandled submode!");
1148
4
    case ARM_AM::ia: return ARM::t2STMIA_UPD;
1149
4
    
case ARM_AM::db: return ARM::t2STMDB_UPD0
;
1150
0
    }
1151
0
  case ARM::VLDMSIA:
1152
0
    switch (Mode) {
1153
0
    default: llvm_unreachable("Unhandled submode!");
1154
0
    case ARM_AM::ia: return ARM::VLDMSIA_UPD;
1155
0
    case ARM_AM::db: return ARM::VLDMSDB_UPD;
1156
0
    }
1157
0
  case ARM::VLDMDIA:
1158
0
    switch (Mode) {
1159
0
    default: llvm_unreachable("Unhandled submode!");
1160
0
    case ARM_AM::ia: return ARM::VLDMDIA_UPD;
1161
0
    case ARM_AM::db: return ARM::VLDMDDB_UPD;
1162
0
    }
1163
0
  case ARM::VSTMSIA:
1164
0
    switch (Mode) {
1165
0
    default: llvm_unreachable("Unhandled submode!");
1166
0
    case ARM_AM::ia: return ARM::VSTMSIA_UPD;
1167
0
    case ARM_AM::db: return ARM::VSTMSDB_UPD;
1168
0
    }
1169
3
  case ARM::VSTMDIA:
1170
3
    switch (Mode) {
1171
3
    
default: 0
llvm_unreachable0
("Unhandled submode!");
1172
3
    case ARM_AM::ia: return ARM::VSTMDIA_UPD;
1173
3
    
case ARM_AM::db: return ARM::VSTMDDB_UPD0
;
1174
3
    }
1175
12
  }
1176
12
}
1177
1178
/// Check if the given instruction increments or decrements a register and
1179
/// return the amount it is incremented/decremented. Returns 0 if the CPSR flags
1180
/// generated by the instruction are possibly read as well.
1181
static int isIncrementOrDecrement(const MachineInstr &MI, unsigned Reg,
1182
48.7k
                                  ARMCC::CondCodes Pred, unsigned PredReg) {
1183
48.7k
  bool CheckCPSRDef;
1184
48.7k
  int Scale;
1185
48.7k
  switch (MI.getOpcode()) {
1186
48.7k
  
case ARM::tADDi8: Scale = 4; CheckCPSRDef = true; break0
;
1187
48.7k
  
case ARM::tSUBi8: Scale = -4; CheckCPSRDef = true; break0
;
1188
48.7k
  case ARM::t2SUBri:
1189
435
  case ARM::SUBri:   Scale = -1; CheckCPSRDef = true; break;
1190
4.29k
  case ARM::t2ADDri:
1191
4.29k
  case ARM::ADDri:   Scale =  1; CheckCPSRDef = true; break;
1192
4.29k
  
case ARM::tADDspi: Scale = 4; CheckCPSRDef = false; break400
;
1193
4.29k
  
case ARM::tSUBspi: Scale = -4; CheckCPSRDef = false; break164
;
1194
43.4k
  default: return 0;
1195
5.29k
  }
1196
5.29k
1197
5.29k
  unsigned MIPredReg;
1198
5.29k
  if (MI.getOperand(0).getReg() != Reg ||
1199
5.29k
      
MI.getOperand(1).getReg() != Reg1.59k
||
1200
5.29k
      
getInstrPredicate(MI, MIPredReg) != Pred276
||
1201
5.29k
      
MIPredReg != PredReg239
)
1202
5.05k
    return 0;
1203
239
1204
239
  if (CheckCPSRDef && 
definesCPSR(MI)97
)
1205
0
    return 0;
1206
239
  return MI.getOperand(2).getImm() * Scale;
1207
239
}
1208
1209
/// Searches for an increment or decrement of \p Reg before \p MBBI.
1210
static MachineBasicBlock::iterator
1211
findIncDecBefore(MachineBasicBlock::iterator MBBI, unsigned Reg,
1212
26.9k
                 ARMCC::CondCodes Pred, unsigned PredReg, int &Offset) {
1213
26.9k
  Offset = 0;
1214
26.9k
  MachineBasicBlock &MBB = *MBBI->getParent();
1215
26.9k
  MachineBasicBlock::iterator BeginMBBI = MBB.begin();
1216
26.9k
  MachineBasicBlock::iterator EndMBBI = MBB.end();
1217
26.9k
  if (MBBI == BeginMBBI)
1218
3.90k
    return EndMBBI;
1219
23.0k
1220
23.0k
  // Skip debug values.
1221
23.0k
  MachineBasicBlock::iterator PrevMBBI = std::prev(MBBI);
1222
23.0k
  while (PrevMBBI->isDebugInstr() && 
PrevMBBI != BeginMBBI6
)
1223
4
    --PrevMBBI;
1224
23.0k
1225
23.0k
  Offset = isIncrementOrDecrement(*PrevMBBI, Reg, Pred, PredReg);
1226
23.0k
  return Offset == 0 ? 
EndMBBI22.9k
:
PrevMBBI126
;
1227
23.0k
}
1228
1229
/// Searches for a increment or decrement of \p Reg after \p MBBI.
1230
static MachineBasicBlock::iterator
1231
findIncDecAfter(MachineBasicBlock::iterator MBBI, unsigned Reg,
1232
26.8k
                ARMCC::CondCodes Pred, unsigned PredReg, int &Offset) {
1233
26.8k
  Offset = 0;
1234
26.8k
  MachineBasicBlock &MBB = *MBBI->getParent();
1235
26.8k
  MachineBasicBlock::iterator EndMBBI = MBB.end();
1236
26.8k
  MachineBasicBlock::iterator NextMBBI = std::next(MBBI);
1237
26.8k
  // Skip debug values.
1238
26.8k
  while (NextMBBI != EndMBBI && 
NextMBBI->isDebugInstr()25.7k
)
1239
5
    ++NextMBBI;
1240
26.8k
  if (NextMBBI == EndMBBI)
1241
1.14k
    return EndMBBI;
1242
25.7k
1243
25.7k
  Offset = isIncrementOrDecrement(*NextMBBI, Reg, Pred, PredReg);
1244
25.7k
  return Offset == 0 ? 
EndMBBI25.5k
:
NextMBBI113
;
1245
25.7k
}
1246
1247
/// Fold proceeding/trailing inc/dec of base register into the
1248
/// LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible:
1249
///
1250
/// stmia rn, <ra, rb, rc>
1251
/// rn := rn + 4 * 3;
1252
/// =>
1253
/// stmia rn!, <ra, rb, rc>
1254
///
1255
/// rn := rn - 4 * 3;
1256
/// ldmia rn, <ra, rb, rc>
1257
/// =>
1258
/// ldmdb rn!, <ra, rb, rc>
1259
1.29k
bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineInstr *MI) {
1260
1.29k
  // Thumb1 is already using updating loads/stores.
1261
1.29k
  if (isThumb1) 
return false130
;
1262
1.16k
1263
1.16k
  const MachineOperand &BaseOP = MI->getOperand(0);
1264
1.16k
  unsigned Base = BaseOP.getReg();
1265
1.16k
  bool BaseKill = BaseOP.isKill();
1266
1.16k
  unsigned PredReg = 0;
1267
1.16k
  ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1268
1.16k
  unsigned Opcode = MI->getOpcode();
1269
1.16k
  DebugLoc DL = MI->getDebugLoc();
1270
1.16k
1271
1.16k
  // Can't use an updating ld/st if the base register is also a dest
1272
1.16k
  // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
1273
5.98k
  for (unsigned i = 2, e = MI->getNumOperands(); i != e; 
++i4.82k
)
1274
5.14k
    if (MI->getOperand(i).getReg() == Base)
1275
320
      return false;
1276
1.16k
1277
1.16k
  int Bytes = getLSMultipleTransferSize(MI);
1278
846
  MachineBasicBlock &MBB = *MI->getParent();
1279
846
  MachineBasicBlock::iterator MBBI(MI);
1280
846
  int Offset;
1281
846
  MachineBasicBlock::iterator MergeInstr
1282
846
    = findIncDecBefore(MBBI, Base, Pred, PredReg, Offset);
1283
846
  ARM_AM::AMSubMode Mode = getLoadStoreMultipleSubMode(Opcode);
1284
846
  if (Mode == ARM_AM::ia && 
Offset == -Bytes792
) {
1285
0
    Mode = ARM_AM::db;
1286
846
  } else if (Mode == ARM_AM::ib && 
Offset == -Bytes54
) {
1287
0
    Mode = ARM_AM::da;
1288
846
  } else {
1289
846
    MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1290
846
    if (((Mode != ARM_AM::ia && 
Mode != ARM_AM::ib54
) || Offset != Bytes) &&
1291
846
        
(841
(841
Mode != ARM_AM::da841
&&
Mode != ARM_AM::db841
) ||
Offset != -Bytes0
)) {
1292
841
1293
841
      // We couldn't find an inc/dec to merge. But if the base is dead, we
1294
841
      // can still change to a writeback form as that will save us 2 bytes
1295
841
      // of code size. It can create WAW hazards though, so only do it if
1296
841
      // we're minimizing code size.
1297
841
      if (!STI->hasMinSize() || 
!BaseKill14
)
1298
834
        return false;
1299
7
1300
7
      bool HighRegsUsed = false;
1301
35
      for (unsigned i = 2, e = MI->getNumOperands(); i != e; 
++i28
)
1302
28
        if (MI->getOperand(i).getReg() >= ARM::R8) {
1303
0
          HighRegsUsed = true;
1304
0
          break;
1305
0
        }
1306
7
1307
7
      if (!HighRegsUsed)
1308
7
        MergeInstr = MBB.end();
1309
0
      else
1310
0
        return false;
1311
12
    }
1312
846
  }
1313
12
  if (MergeInstr != MBB.end())
1314
5
    MBB.erase(MergeInstr);
1315
12
1316
12
  unsigned NewOpc = getUpdatingLSMultipleOpcode(Opcode, Mode);
1317
12
  MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
1318
12
    .addReg(Base, getDefRegState(true)) // WB base register
1319
12
    .addReg(Base, getKillRegState(BaseKill))
1320
12
    .addImm(Pred).addReg(PredReg);
1321
12
1322
12
  // Transfer the rest of operands.
1323
46
  for (unsigned OpNum = 3, e = MI->getNumOperands(); OpNum != e; 
++OpNum34
)
1324
34
    MIB.add(MI->getOperand(OpNum));
1325
12
1326
12
  // Transfer memoperands.
1327
12
  MIB.setMemRefs(MI->memoperands());
1328
12
1329
12
  MBB.erase(MBBI);
1330
12
  return true;
1331
12
}
1332
1333
static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc,
1334
42
                                             ARM_AM::AddrOpc Mode) {
1335
42
  switch (Opc) {
1336
42
  case ARM::LDRi12:
1337
0
    return ARM::LDR_PRE_IMM;
1338
42
  case ARM::STRi12:
1339
1
    return ARM::STR_PRE_IMM;
1340
42
  case ARM::VLDRS:
1341
0
    return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1342
42
  case ARM::VLDRD:
1343
0
    return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
1344
42
  case ARM::VSTRS:
1345
0
    return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1346
42
  case ARM::VSTRD:
1347
0
    return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
1348
42
  case ARM::t2LDRi8:
1349
0
  case ARM::t2LDRi12:
1350
0
    return ARM::t2LDR_PRE;
1351
41
  case ARM::t2STRi8:
1352
41
  case ARM::t2STRi12:
1353
41
    return ARM::t2STR_PRE;
1354
41
  
default: 0
llvm_unreachable0
("Unhandled opcode!");
1355
42
  }
1356
42
}
1357
1358
static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc,
1359
42
                                              ARM_AM::AddrOpc Mode) {
1360
42
  switch (Opc) {
1361
42
  case ARM::LDRi12:
1362
8
    return ARM::LDR_POST_IMM;
1363
42
  case ARM::STRi12:
1364
13
    return ARM::STR_POST_IMM;
1365
42
  case ARM::VLDRS:
1366
0
    return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1367
42
  case ARM::VLDRD:
1368
2
    return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : 
ARM::VLDMDDB_UPD0
;
1369
42
  case ARM::VSTRS:
1370
0
    return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1371
42
  case ARM::VSTRD:
1372
10
    return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : 
ARM::VSTMDDB_UPD0
;
1373
42
  case ARM::t2LDRi8:
1374
3
  case ARM::t2LDRi12:
1375
3
    return ARM::t2LDR_POST;
1376
6
  case ARM::t2STRi8:
1377
6
  case ARM::t2STRi12:
1378
6
    return ARM::t2STR_POST;
1379
6
  
default: 0
llvm_unreachable0
("Unhandled opcode!");
1380
42
  }
1381
42
}
1382
1383
/// Fold proceeding/trailing inc/dec of base register into the
1384
/// LDR/STR/FLD{D|S}/FST{D|S} op when possible:
1385
71.3k
bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineInstr *MI) {
1386
71.3k
  // Thumb1 doesn't have updating LDR/STR.
1387
71.3k
  // FIXME: Use LDM/STM with single register instead.
1388
71.3k
  if (isThumb1) 
return false3.75k
;
1389
67.5k
1390
67.5k
  unsigned Base = getLoadStoreBaseOp(*MI).getReg();
1391
67.5k
  bool BaseKill = getLoadStoreBaseOp(*MI).isKill();
1392
67.5k
  unsigned Opcode = MI->getOpcode();
1393
67.5k
  DebugLoc DL = MI->getDebugLoc();
1394
67.5k
  bool isAM5 = (Opcode == ARM::VLDRD || 
Opcode == ARM::VLDRS65.8k
||
1395
67.5k
                
Opcode == ARM::VSTRD65.6k
||
Opcode == ARM::VSTRS65.1k
);
1396
67.5k
  bool isAM2 = (Opcode == ARM::LDRi12 || 
Opcode == ARM::STRi1265.4k
);
1397
67.5k
  if (isi32Load(Opcode) || 
isi32Store(Opcode)31.1k
)
1398
64.7k
    if (MI->getOperand(2).getImm() != 0)
1399
42.7k
      return false;
1400
24.8k
  if (isAM5 && 
ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 02.80k
)
1401
836
    return false;
1402
23.9k
1403
23.9k
  // Can't do the merge if the destination register is the same as the would-be
1404
23.9k
  // writeback register.
1405
23.9k
  if (MI->getOperand(0).getReg() == Base)
1406
7.56k
    return false;
1407
16.4k
1408
16.4k
  unsigned PredReg = 0;
1409
16.4k
  ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1410
16.4k
  int Bytes = getLSMultipleTransferSize(MI);
1411
16.4k
  MachineBasicBlock &MBB = *MI->getParent();
1412
16.4k
  MachineBasicBlock::iterator MBBI(MI);
1413
16.4k
  int Offset;
1414
16.4k
  MachineBasicBlock::iterator MergeInstr
1415
16.4k
    = findIncDecBefore(MBBI, Base, Pred, PredReg, Offset);
1416
16.4k
  unsigned NewOpc;
1417
16.4k
  if (!isAM5 && 
Offset == Bytes14.4k
) {
1418
0
    NewOpc = getPreIndexedLoadStoreOpcode(Opcode, ARM_AM::add);
1419
16.4k
  } else if (Offset == -Bytes) {
1420
42
    NewOpc = getPreIndexedLoadStoreOpcode(Opcode, ARM_AM::sub);
1421
16.3k
  } else {
1422
16.3k
    MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1423
16.3k
    if (Offset == Bytes) {
1424
42
      NewOpc = getPostIndexedLoadStoreOpcode(Opcode, ARM_AM::add);
1425
16.3k
    } else if (!isAM5 && 
Offset == -Bytes14.3k
) {
1426
0
      NewOpc = getPostIndexedLoadStoreOpcode(Opcode, ARM_AM::sub);
1427
0
    } else
1428
16.3k
      return false;
1429
84
  }
1430
84
  MBB.erase(MergeInstr);
1431
84
1432
84
  ARM_AM::AddrOpc AddSub = Offset < 0 ? 
ARM_AM::sub42
:
ARM_AM::add42
;
1433
84
1434
84
  bool isLd = isLoadSingle(Opcode);
1435
84
  if (isAM5) {
1436
12
    // VLDM[SD]_UPD, VSTM[SD]_UPD
1437
12
    // (There are no base-updating versions of VLDR/VSTR instructions, but the
1438
12
    // updating load/store-multiple instructions can be used with only one
1439
12
    // register.)
1440
12
    MachineOperand &MO = MI->getOperand(0);
1441
12
    BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
1442
12
      .addReg(Base, getDefRegState(true)) // WB base register
1443
12
      .addReg(Base, getKillRegState(isLd ? 
BaseKill2
:
false10
))
1444
12
      .addImm(Pred).addReg(PredReg)
1445
12
      .addReg(MO.getReg(), (isLd ? 
getDefRegState(true)2
:
1446
12
                            
getKillRegState(MO.isKill())10
))
1447
12
      .cloneMemRefs(*MI);
1448
72
  } else if (isLd) {
1449
11
    if (isAM2) {
1450
8
      // LDR_PRE, LDR_POST
1451
8
      if (NewOpc == ARM::LDR_PRE_IMM || NewOpc == ARM::LDRB_PRE_IMM) {
1452
0
        BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1453
0
          .addReg(Base, RegState::Define)
1454
0
          .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg)
1455
0
          .cloneMemRefs(*MI);
1456
8
      } else {
1457
8
        int Imm = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
1458
8
        BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1459
8
            .addReg(Base, RegState::Define)
1460
8
            .addReg(Base)
1461
8
            .addReg(0)
1462
8
            .addImm(Imm)
1463
8
            .add(predOps(Pred, PredReg))
1464
8
            .cloneMemRefs(*MI);
1465
8
      }
1466
8
    } else {
1467
3
      // t2LDR_PRE, t2LDR_POST
1468
3
      BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1469
3
          .addReg(Base, RegState::Define)
1470
3
          .addReg(Base)
1471
3
          .addImm(Offset)
1472
3
          .add(predOps(Pred, PredReg))
1473
3
          .cloneMemRefs(*MI);
1474
3
    }
1475
61
  } else {
1476
61
    MachineOperand &MO = MI->getOperand(0);
1477
61
    // FIXME: post-indexed stores use am2offset_imm, which still encodes
1478
61
    // the vestigal zero-reg offset register. When that's fixed, this clause
1479
61
    // can be removed entirely.
1480
61
    if (isAM2 && 
NewOpc == ARM::STR_POST_IMM14
) {
1481
13
      int Imm = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
1482
13
      // STR_PRE, STR_POST
1483
13
      BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
1484
13
          .addReg(MO.getReg(), getKillRegState(MO.isKill()))
1485
13
          .addReg(Base)
1486
13
          .addReg(0)
1487
13
          .addImm(Imm)
1488
13
          .add(predOps(Pred, PredReg))
1489
13
          .cloneMemRefs(*MI);
1490
48
    } else {
1491
48
      // t2STR_PRE, t2STR_POST
1492
48
      BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
1493
48
          .addReg(MO.getReg(), getKillRegState(MO.isKill()))
1494
48
          .addReg(Base)
1495
48
          .addImm(Offset)
1496
48
          .add(predOps(Pred, PredReg))
1497
48
          .cloneMemRefs(*MI);
1498
48
    }
1499
61
  }
1500
84
  MBB.erase(MBBI);
1501
84
1502
84
  return true;
1503
84
}
1504
1505
20.4k
bool ARMLoadStoreOpt::MergeBaseUpdateLSDouble(MachineInstr &MI) const {
1506
20.4k
  unsigned Opcode = MI.getOpcode();
1507
20.4k
  assert((Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8) &&
1508
20.4k
         "Must have t2STRDi8 or t2LDRDi8");
1509
20.4k
  if (MI.getOperand(3).getImm() != 0)
1510
10.6k
    return false;
1511
9.76k
1512
9.76k
  // Behaviour for writeback is undefined if base register is the same as one
1513
9.76k
  // of the others.
1514
9.76k
  const MachineOperand &BaseOp = MI.getOperand(2);
1515
9.76k
  unsigned Base = BaseOp.getReg();
1516
9.76k
  const MachineOperand &Reg0Op = MI.getOperand(0);
1517
9.76k
  const MachineOperand &Reg1Op = MI.getOperand(1);
1518
9.76k
  if (Reg0Op.getReg() == Base || 
Reg1Op.getReg() == Base9.69k
)
1519
85
    return false;
1520
9.67k
1521
9.67k
  unsigned PredReg;
1522
9.67k
  ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
1523
9.67k
  MachineBasicBlock::iterator MBBI(MI);
1524
9.67k
  MachineBasicBlock &MBB = *MI.getParent();
1525
9.67k
  int Offset;
1526
9.67k
  MachineBasicBlock::iterator MergeInstr = findIncDecBefore(MBBI, Base, Pred,
1527
9.67k
                                                            PredReg, Offset);
1528
9.67k
  unsigned NewOpc;
1529
9.67k
  if (Offset == 8 || Offset == -8) {
1530
51
    NewOpc = Opcode == ARM::t2LDRDi8 ? 
ARM::t2LDRD_PRE0
: ARM::t2STRD_PRE;
1531
9.62k
  } else {
1532
9.62k
    MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1533
9.62k
    if (Offset == 8 || 
Offset == -89.59k
) {
1534
36
      NewOpc = Opcode == ARM::t2LDRDi8 ? 
ARM::t2LDRD_POST16
:
ARM::t2STRD_POST20
;
1535
36
    } else
1536
9.58k
      return false;
1537
87
  }
1538
87
  MBB.erase(MergeInstr);
1539
87
1540
87
  DebugLoc DL = MI.getDebugLoc();
1541
87
  MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc));
1542
87
  if (NewOpc == ARM::t2LDRD_PRE || NewOpc == ARM::t2LDRD_POST) {
1543
16
    MIB.add(Reg0Op).add(Reg1Op).addReg(BaseOp.getReg(), RegState::Define);
1544
71
  } else {
1545
71
    assert(NewOpc == ARM::t2STRD_PRE || NewOpc == ARM::t2STRD_POST);
1546
71
    MIB.addReg(BaseOp.getReg(), RegState::Define).add(Reg0Op).add(Reg1Op);
1547
71
  }
1548
87
  MIB.addReg(BaseOp.getReg(), RegState::Kill)
1549
87
     .addImm(Offset).addImm(Pred).addReg(PredReg);
1550
87
  assert(TII->get(Opcode).getNumOperands() == 6 &&
1551
87
         TII->get(NewOpc).getNumOperands() == 7 &&
1552
87
         "Unexpected number of operands in Opcode specification.");
1553
87
1554
87
  // Transfer implicit operands.
1555
87
  for (const MachineOperand &MO : MI.implicit_operands())
1556
0
    MIB.add(MO);
1557
87
  MIB.cloneMemRefs(MI);
1558
87
1559
87
  MBB.erase(MBBI);
1560
87
  return true;
1561
87
}
1562
1563
/// Returns true if instruction is a memory operation that this pass is capable
1564
/// of operating on.
1565
1.56M
static bool isMemoryOp(const MachineInstr &MI) {
1566
1.56M
  unsigned Opcode = MI.getOpcode();
1567
1.56M
  switch (Opcode) {
1568
1.56M
  case ARM::VLDRS:
1569
234k
  case ARM::VSTRS:
1570
234k
  case ARM::VLDRD:
1571
234k
  case ARM::VSTRD:
1572
234k
  case ARM::LDRi12:
1573
234k
  case ARM::STRi12:
1574
234k
  case ARM::tLDRi:
1575
234k
  case ARM::tSTRi:
1576
234k
  case ARM::tLDRspi:
1577
234k
  case ARM::tSTRspi:
1578
234k
  case ARM::t2LDRi8:
1579
234k
  case ARM::t2LDRi12:
1580
234k
  case ARM::t2STRi8:
1581
234k
  case ARM::t2STRi12:
1582
234k
    break;
1583
1.32M
  default:
1584
1.32M
    return false;
1585
234k
  }
1586
234k
  if (!MI.getOperand(1).isReg())
1587
33.1k
    return false;
1588
201k
1589
201k
  // When no memory operands are present, conservatively assume unaligned,
1590
201k
  // volatile, unfoldable.
1591
201k
  if (!MI.hasOneMemOperand())
1592
1.47k
    return false;
1593
200k
1594
200k
  const MachineMemOperand &MMO = **MI.memoperands_begin();
1595
200k
1596
200k
  // Don't touch volatile memory accesses - we may be changing their order.
1597
200k
  // TODO: We could allow unordered and monotonic atomics here, but we need to
1598
200k
  // make sure the resulting ldm/stm is correctly marked as atomic. 
1599
200k
  if (MMO.isVolatile() || 
MMO.isAtomic()196k
)
1600
3.95k
    return false;
1601
196k
1602
196k
  // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is
1603
196k
  // not.
1604
196k
  if (MMO.getAlignment() < 4)
1605
455
    return false;
1606
195k
1607
195k
  // str <undef> could probably be eliminated entirely, but for now we just want
1608
195k
  // to avoid making a mess of it.
1609
195k
  // FIXME: Use str <undef> as a wildcard to enable better stm folding.
1610
195k
  if (MI.getOperand(0).isReg() && MI.getOperand(0).isUndef())
1611
0
    return false;
1612
195k
1613
195k
  // Likewise don't mess with references to undefined addresses.
1614
195k
  if (MI.getOperand(1).isUndef())
1615
87
    return false;
1616
195k
1617
195k
  return true;
1618
195k
}
1619
1620
static void InsertLDR_STR(MachineBasicBlock &MBB,
1621
                          MachineBasicBlock::iterator &MBBI, int Offset,
1622
                          bool isDef, unsigned NewOpc, unsigned Reg,
1623
                          bool RegDeadKill, bool RegUndef, unsigned BaseReg,
1624
                          bool BaseKill, bool BaseUndef, ARMCC::CondCodes Pred,
1625
                          unsigned PredReg, const TargetInstrInfo *TII,
1626
12
                          MachineInstr *MI) {
1627
12
  if (isDef) {
1628
2
    MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1629
2
                                      TII->get(NewOpc))
1630
2
      .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill))
1631
2
      .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1632
2
    MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1633
2
    // FIXME: This is overly conservative; the new instruction accesses 4
1634
2
    // bytes, not 8.
1635
2
    MIB.cloneMemRefs(*MI);
1636
10
  } else {
1637
10
    MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1638
10
                                      TII->get(NewOpc))
1639
10
      .addReg(Reg, getKillRegState(RegDeadKill) | getUndefRegState(RegUndef))
1640
10
      .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1641
10
    MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1642
10
    // FIXME: This is overly conservative; the new instruction accesses 4
1643
10
    // bytes, not 8.
1644
10
    MIB.cloneMemRefs(*MI);
1645
10
  }
1646
12
}
1647
1648
bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB,
1649
760k
                                          MachineBasicBlock::iterator &MBBI) {
1650
760k
  MachineInstr *MI = &*MBBI;
1651
760k
  unsigned Opcode = MI->getOpcode();
1652
760k
  // FIXME: Code/comments below check Opcode == t2STRDi8, but this check returns
1653
760k
  // if we see this opcode.
1654
760k
  if (Opcode != ARM::LDRD && 
Opcode != ARM::STRD759k
&&
Opcode != ARM::t2LDRDi8759k
)
1655
758k
    return false;
1656
1.15k
1657
1.15k
  const MachineOperand &BaseOp = MI->getOperand(2);
1658
1.15k
  unsigned BaseReg = BaseOp.getReg();
1659
1.15k
  unsigned EvenReg = MI->getOperand(0).getReg();
1660
1.15k
  unsigned OddReg  = MI->getOperand(1).getReg();
1661
1.15k
  unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false);
1662
1.15k
  unsigned OddRegNum  = TRI->getDwarfRegNum(OddReg, false);
1663
1.15k
1664
1.15k
  // ARM errata 602117: LDRD with base in list may result in incorrect base
1665
1.15k
  // register when interrupted or faulted.
1666
1.15k
  bool Errata602117 = EvenReg == BaseReg &&
1667
1.15k
    
(141
Opcode == ARM::LDRD141
||
Opcode == ARM::t2LDRDi8121
) &&
STI->isCortexM3()141
;
1668
1.15k
  // ARM LDRD/STRD needs consecutive registers.
1669
1.15k
  bool NonConsecutiveRegs = (Opcode == ARM::LDRD || 
Opcode == ARM::STRD1.11k
) &&
1670
1.15k
    
(105
EvenRegNum % 2 != 0105
||
EvenRegNum + 1 != OddRegNum101
);
1671
1.15k
1672
1.15k
  if (!Errata602117 && 
!NonConsecutiveRegs1.14k
)
1673
1.12k
    return false;
1674
24
1675
24
  bool isT2 = Opcode == ARM::t2LDRDi8 || 
Opcode == ARM::t2STRDi816
;
1676
24
  bool isLd = Opcode == ARM::LDRD || 
Opcode == ARM::t2LDRDi823
;
1677
24
  bool EvenDeadKill = isLd ?
1678
15
    
MI->getOperand(0).isDead()9
: MI->getOperand(0).isKill();
1679
24
  bool EvenUndef = MI->getOperand(0).isUndef();
1680
24
  bool OddDeadKill  = isLd ?
1681
15
    
MI->getOperand(1).isDead()9
: MI->getOperand(1).isKill();
1682
24
  bool OddUndef = MI->getOperand(1).isUndef();
1683
24
  bool BaseKill = BaseOp.isKill();
1684
24
  bool BaseUndef = BaseOp.isUndef();
1685
24
  assert((isT2 || MI->getOperand(3).getReg() == ARM::NoRegister) &&
1686
24
         "register offset not handled below");
1687
24
  int OffImm = getMemoryOpOffset(*MI);
1688
24
  unsigned PredReg = 0;
1689
24
  ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1690
24
1691
24
  if (OddRegNum > EvenRegNum && 
OffImm == 019
) {
1692
18
    // Ascending register numbers and no offset. It's safe to change it to a
1693
18
    // ldm or stm.
1694
18
    unsigned NewOpc = (isLd)
1695
18
      ? 
(isT2 8
?
ARM::t2LDMIA8
:
ARM::LDMIA0
)
1696
18
      : 
(isT2 10
?
ARM::t2STMIA0
:
ARM::STMIA10
);
1697
18
    if (isLd) {
1698
8
      BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1699
8
        .addReg(BaseReg, getKillRegState(BaseKill))
1700
8
        .addImm(Pred).addReg(PredReg)
1701
8
        .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill))
1702
8
        .addReg(OddReg,  getDefRegState(isLd) | getDeadRegState(OddDeadKill))
1703
8
        .cloneMemRefs(*MI);
1704
8
      ++NumLDRD2LDM;
1705
10
    } else {
1706
10
      BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1707
10
        .addReg(BaseReg, getKillRegState(BaseKill))
1708
10
        .addImm(Pred).addReg(PredReg)
1709
10
        .addReg(EvenReg,
1710
10
                getKillRegState(EvenDeadKill) | getUndefRegState(EvenUndef))
1711
10
        .addReg(OddReg,
1712
10
                getKillRegState(OddDeadKill)  | getUndefRegState(OddUndef))
1713
10
        .cloneMemRefs(*MI);
1714
10
      ++NumSTRD2STM;
1715
10
    }
1716
18
  } else {
1717
6
    // Split into two instructions.
1718
6
    unsigned NewOpc = (isLd)
1719
6
      ? 
(isT2 1
?
(OffImm < 0 0
?
ARM::t2LDRi80
:
ARM::t2LDRi120
) :
ARM::LDRi121
)
1720
6
      : 
(isT2 5
?
(OffImm < 0 0
?
ARM::t2STRi80
:
ARM::t2STRi120
) :
ARM::STRi125
);
1721
6
    // Be extra careful for thumb2. t2LDRi8 can't reference a zero offset,
1722
6
    // so adjust and use t2LDRi12 here for that.
1723
6
    unsigned NewOpc2 = (isLd)
1724
6
      ? 
(isT2 1
?
(OffImm+4 < 0 0
?
ARM::t2LDRi80
:
ARM::t2LDRi120
) :
ARM::LDRi121
)
1725
6
      : 
(isT2 5
?
(OffImm+4 < 0 0
?
ARM::t2STRi80
:
ARM::t2STRi120
) :
ARM::STRi125
);
1726
6
    // If this is a load, make sure the first load does not clobber the base
1727
6
    // register before the second load reads it.
1728
6
    if (isLd && 
TRI->regsOverlap(EvenReg, BaseReg)1
) {
1729
1
      assert(!TRI->regsOverlap(OddReg, BaseReg));
1730
1
      InsertLDR_STR(MBB, MBBI, OffImm + 4, isLd, NewOpc2, OddReg, OddDeadKill,
1731
1
                    false, BaseReg, false, BaseUndef, Pred, PredReg, TII, MI);
1732
1
      InsertLDR_STR(MBB, MBBI, OffImm, isLd, NewOpc, EvenReg, EvenDeadKill,
1733
1
                    false, BaseReg, BaseKill, BaseUndef, Pred, PredReg, TII,
1734
1
                    MI);
1735
5
    } else {
1736
5
      if (OddReg == EvenReg && 
EvenDeadKill0
) {
1737
0
        // If the two source operands are the same, the kill marker is
1738
0
        // probably on the first one. e.g.
1739
0
        // t2STRDi8 killed %r5, %r5, killed %r9, 0, 14, %reg0
1740
0
        EvenDeadKill = false;
1741
0
        OddDeadKill = true;
1742
0
      }
1743
5
      // Never kill the base register in the first instruction.
1744
5
      if (EvenReg == BaseReg)
1745
0
        EvenDeadKill = false;
1746
5
      InsertLDR_STR(MBB, MBBI, OffImm, isLd, NewOpc, EvenReg, EvenDeadKill,
1747
5
                    EvenUndef, BaseReg, false, BaseUndef, Pred, PredReg, TII,
1748
5
                    MI);
1749
5
      InsertLDR_STR(MBB, MBBI, OffImm + 4, isLd, NewOpc2, OddReg, OddDeadKill,
1750
5
                    OddUndef, BaseReg, BaseKill, BaseUndef, Pred, PredReg, TII,
1751
5
                    MI);
1752
5
    }
1753
6
    if (isLd)
1754
1
      ++NumLDRD2LDR;
1755
5
    else
1756
5
      ++NumSTRD2STR;
1757
6
  }
1758
24
1759
24
  MBBI = MBB.erase(MBBI);
1760
24
  return true;
1761
24
}
1762
1763
/// An optimization pass to turn multiple LDR / STR ops of the same base and
1764
/// incrementing offset into LDM / STM ops.
1765
110k
bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
1766
110k
  MemOpQueue MemOps;
1767
110k
  unsigned CurrBase = 0;
1768
110k
  unsigned CurrOpc = ~0u;
1769
110k
  ARMCC::CondCodes CurrPred = ARMCC::AL;
1770
110k
  unsigned Position = 0;
1771
110k
  assert(Candidates.size() == 0);
1772
110k
  assert(MergeBaseCandidates.size() == 0);
1773
110k
  LiveRegsValid = false;
1774
110k
1775
870k
  for (MachineBasicBlock::iterator I = MBB.end(), MBBI; I != MBB.begin();
1776
760k
       I = MBBI) {
1777
760k
    // The instruction in front of the iterator is the one we look at.
1778
760k
    MBBI = std::prev(I);
1779
760k
    if (FixInvalidRegPairOp(MBB, MBBI))
1780
24
      continue;
1781
759k
    ++Position;
1782
759k
1783
759k
    if (isMemoryOp(*MBBI)) {
1784
120k
      unsigned Opcode = MBBI->getOpcode();
1785
120k
      const MachineOperand &MO = MBBI->getOperand(0);
1786
120k
      unsigned Reg = MO.getReg();
1787
120k
      unsigned Base = getLoadStoreBaseOp(*MBBI).getReg();
1788
120k
      unsigned PredReg = 0;
1789
120k
      ARMCC::CondCodes Pred = getInstrPredicate(*MBBI, PredReg);
1790
120k
      int Offset = getMemoryOpOffset(*MBBI);
1791
120k
      if (CurrBase == 0) {
1792
75.9k
        // Start of a new chain.
1793
75.9k
        CurrBase = Base;
1794
75.9k
        CurrOpc  = Opcode;
1795
75.9k
        CurrPred = Pred;
1796
75.9k
        MemOps.push_back(MemOpQueueEntry(*MBBI, Offset, Position));
1797
75.9k
        continue;
1798
75.9k
      }
1799
44.6k
      // Note: No need to match PredReg in the next if.
1800
44.6k
      if (CurrOpc == Opcode && 
CurrBase == Base37.9k
&&
CurrPred == Pred33.8k
) {
1801
33.8k
        // Watch out for:
1802
33.8k
        //   r4 := ldr [r0, #8]
1803
33.8k
        //   r4 := ldr [r0, #4]
1804
33.8k
        // or
1805
33.8k
        //   r0 := ldr [r0]
1806
33.8k
        // If a load overrides the base register or a register loaded by
1807
33.8k
        // another load in our chain, we cannot take this instruction.
1808
33.8k
        bool Overlap = false;
1809
33.8k
        if (isLoadSingle(Opcode)) {
1810
7.21k
          Overlap = (Base == Reg);
1811
7.21k
          if (!Overlap) {
1812
8.16k
            for (const MemOpQueueEntry &E : MemOps) {
1813
8.16k
              if (TRI->regsOverlap(Reg, E.MI->getOperand(0).getReg())) {
1814
0
                Overlap = true;
1815
0
                break;
1816
0
              }
1817
8.16k
            }
1818
5.03k
          }
1819
7.21k
        }
1820
33.8k
1821
33.8k
        if (!Overlap) {
1822
31.6k
          // Check offset and sort memory operation into the current chain.
1823
31.6k
          if (Offset > MemOps.back().Offset) {
1824
8.03k
            MemOps.push_back(MemOpQueueEntry(*MBBI, Offset, Position));
1825
8.03k
            continue;
1826
23.6k
          } else {
1827
23.6k
            MemOpQueue::iterator MI, ME;
1828
24.6k
            for (MI = MemOps.begin(), ME = MemOps.end(); MI != ME; 
++MI1.01k
) {
1829
24.6k
              if (Offset < MI->Offset) {
1830
23.6k
                // Found a place to insert.
1831
23.6k
                break;
1832
23.6k
              }
1833
1.01k
              if (Offset == MI->Offset) {
1834
5
                // Collision, abort.
1835
5
                MI = ME;
1836
5
                break;
1837
5
              }
1838
1.01k
            }
1839
23.6k
            if (MI != MemOps.end()) {
1840
23.6k
              MemOps.insert(MI, MemOpQueueEntry(*MBBI, Offset, Position));
1841
23.6k
              continue;
1842
23.6k
            }
1843
12.9k
          }
1844
31.6k
        }
1845
33.8k
      }
1846
12.9k
1847
12.9k
      // Don't advance the iterator; The op will start a new chain next.
1848
12.9k
      MBBI = I;
1849
12.9k
      --Position;
1850
12.9k
      // Fallthrough to look into existing chain.
1851
639k
    } else if (MBBI->isDebugInstr()) {
1852
146
      continue;
1853
639k
    } else if (MBBI->getOpcode() == ARM::t2LDRDi8 ||
1854
639k
               
MBBI->getOpcode() == ARM::t2STRDi8638k
) {
1855
4.46k
      // ARMPreAllocLoadStoreOpt has already formed some LDRD/STRD instructions
1856
4.46k
      // remember them because we may still be able to merge add/sub into them.
1857
4.46k
      MergeBaseCandidates.push_back(&*MBBI);
1858
4.46k
    }
1859
759k
1860
759k
    // If we are here then the chain is broken; Extract candidates for a merge.
1861
759k
    
if (652k
MemOps.size() > 0652k
) {
1862
63.1k
      FormCandidates(MemOps);
1863
63.1k
      // Reset for the next chain.
1864
63.1k
      CurrBase = 0;
1865
63.1k
      CurrOpc = ~0u;
1866
63.1k
      CurrPred = ARMCC::AL;
1867
63.1k
      MemOps.clear();
1868
63.1k
    }
1869
652k
  }
1870
110k
  if (MemOps.size() > 0)
1871
12.7k
    FormCandidates(MemOps);
1872
110k
1873
110k
  // Sort candidates so they get processed from end to begin of the basic
1874
110k
  // block later; This is necessary for liveness calculation.
1875
110k
  auto LessThan = [](const MergeCandidate* M0, const MergeCandidate *M1) {
1876
58.3k
    return M0->InsertPos < M1->InsertPos;
1877
58.3k
  };
1878
110k
  llvm::sort(Candidates, LessThan);
1879
110k
1880
110k
  // Go through list of candidates and merge.
1881
110k
  bool Changed = false;
1882
110k
  for (const MergeCandidate *Candidate : Candidates) {
1883
88.0k
    if (Candidate->CanMergeToLSMulti || 
Candidate->CanMergeToLSDouble81.7k
) {
1884
17.6k
      MachineInstr *Merged = MergeOpsUpdate(*Candidate);
1885
17.6k
      // Merge preceding/trailing base inc/dec into the merged op.
1886
17.6k
      if (Merged) {
1887
17.2k
        Changed = true;
1888
17.2k
        unsigned Opcode = Merged->getOpcode();
1889
17.2k
        if (Opcode == ARM::t2STRDi8 || 
Opcode == ARM::t2LDRDi82.81k
)
1890
15.9k
          MergeBaseUpdateLSDouble(*Merged);
1891
1.29k
        else
1892
1.29k
          MergeBaseUpdateLSMultiple(Merged);
1893
17.2k
      } else {
1894
897
        for (MachineInstr *MI : Candidate->Instrs) {
1895
897
          if (MergeBaseUpdateLoadStore(MI))
1896
0
            Changed = true;
1897
897
        }
1898
373
      }
1899
70.4k
    } else {
1900
70.4k
      assert(Candidate->Instrs.size() == 1);
1901
70.4k
      if (MergeBaseUpdateLoadStore(Candidate->Instrs.front()))
1902
84
        Changed = true;
1903
70.4k
    }
1904
88.0k
  }
1905
110k
  Candidates.clear();
1906
110k
  // Try to fold add/sub into the LDRD/STRD formed by ARMPreAllocLoadStoreOpt.
1907
110k
  for (MachineInstr *MI : MergeBaseCandidates)
1908
4.46k
    MergeBaseUpdateLSDouble(*MI);
1909
110k
  MergeBaseCandidates.clear();
1910
110k
1911
110k
  return Changed;
1912
110k
}
1913
1914
/// If this is a exit BB, try merging the return ops ("bx lr" and "mov pc, lr")
1915
/// into the preceding stack restore so it directly restore the value of LR
1916
/// into pc.
1917
///   ldmfd sp!, {..., lr}
1918
///   bx lr
1919
/// or
1920
///   ldmfd sp!, {..., lr}
1921
///   mov pc, lr
1922
/// =>
1923
///   ldmfd sp!, {..., pc}
1924
106k
bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) {
1925
106k
  // Thumb1 LDM doesn't allow high registers.
1926
106k
  if (isThumb1) 
return false3.74k
;
1927
102k
  if (MBB.empty()) 
return false48
;
1928
102k
1929
102k
  MachineBasicBlock::iterator MBBI = MBB.getLastNonDebugInstr();
1930
102k
  if (MBBI != MBB.begin() && 
MBBI != MBB.end()96.0k
&&
1931
102k
      
(96.0k
MBBI->getOpcode() == ARM::BX_RET96.0k
||
1932
96.0k
       
MBBI->getOpcode() == ARM::tBX_RET92.6k
||
1933
96.0k
       
MBBI->getOpcode() == ARM::MOVPCLR86.3k
)) {
1934
9.62k
    MachineBasicBlock::iterator PrevI = std::prev(MBBI);
1935
9.62k
    // Ignore any debug instructions.
1936
9.62k
    while (PrevI->isDebugInstr() && 
PrevI != MBB.begin()7
)
1937
5
      --PrevI;
1938
9.62k
    MachineInstr &PrevMI = *PrevI;
1939
9.62k
    unsigned Opcode = PrevMI.getOpcode();
1940
9.62k
    if (Opcode == ARM::LDMIA_UPD || 
Opcode == ARM::LDMDA_UPD9.61k
||
1941
9.62k
        
Opcode == ARM::LDMDB_UPD9.61k
||
Opcode == ARM::LDMIB_UPD9.61k
||
1942
9.62k
        
Opcode == ARM::t2LDMIA_UPD9.61k
||
Opcode == ARM::t2LDMDB_UPD9.56k
) {
1943
57
      MachineOperand &MO = PrevMI.getOperand(PrevMI.getNumOperands() - 1);
1944
57
      if (MO.getReg() != ARM::LR)
1945
4
        return false;
1946
53
      unsigned NewOpc = (isThumb2 ? 
ARM::t2LDMIA_RET48
:
ARM::LDMIA_RET5
);
1947
53
      assert(((isThumb2 && Opcode == ARM::t2LDMIA_UPD) ||
1948
53
              Opcode == ARM::LDMIA_UPD) && "Unsupported multiple load-return!");
1949
53
      PrevMI.setDesc(TII->get(NewOpc));
1950
53
      MO.setReg(ARM::PC);
1951
53
      PrevMI.copyImplicitOps(*MBB.getParent(), *MBBI);
1952
53
      MBB.erase(MBBI);
1953
53
      // We now restore LR into PC so it is not live-out of the return block
1954
53
      // anymore: Clear the CSI Restored bit.
1955
53
      MachineFrameInfo &MFI = MBB.getParent()->getFrameInfo();
1956
53
      // CSI should be fixed after PrologEpilog Insertion
1957
53
      assert(MFI.isCalleeSavedInfoValid() && "CSI should be valid");
1958
53
      for (CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) {
1959
53
        if (Info.getReg() == ARM::LR) {
1960
53
          Info.setRestored(false);
1961
53
          break;
1962
53
        }
1963
53
      }
1964
53
      return true;
1965
53
    }
1966
9.62k
  }
1967
102k
  return false;
1968
102k
}
1969
1970
4.38k
bool ARMLoadStoreOpt::CombineMovBx(MachineBasicBlock &MBB) {
1971
4.38k
  MachineBasicBlock::iterator MBBI = MBB.getFirstTerminator();
1972
4.38k
  if (MBBI == MBB.begin() || 
MBBI == MBB.end()4.20k
||
1973
4.38k
      
MBBI->getOpcode() != ARM::tBX_RET3.40k
)
1974
3.45k
    return false;
1975
929
1976
929
  MachineBasicBlock::iterator Prev = MBBI;
1977
929
  --Prev;
1978
929
  if (Prev->getOpcode() != ARM::tMOVr || 
!Prev->definesRegister(ARM::LR)199
)
1979
744
    return false;
1980
185
1981
185
  for (auto Use : Prev->uses())
1982
185
    if (Use.isKill()) {
1983
185
      assert(STI->hasV4TOps());
1984
185
      BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(ARM::tBX))
1985
185
          .addReg(Use.getReg(), RegState::Kill)
1986
185
          .add(predOps(ARMCC::AL))
1987
185
          .copyImplicitOps(*MBBI);
1988
185
      MBB.erase(MBBI);
1989
185
      MBB.erase(Prev);
1990
185
      return true;
1991
185
    }
1992
185
1993
185
  
llvm_unreachable0
("tMOVr doesn't kill a reg before tBX_RET?");
1994
185
}
1995
1996
25.2k
bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
1997
25.2k
  if (skipFunction(Fn.getFunction()))
1998
11
    return false;
1999
25.2k
2000
25.2k
  MF = &Fn;
2001
25.2k
  STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
2002
25.2k
  TL = STI->getTargetLowering();
2003
25.2k
  AFI = Fn.getInfo<ARMFunctionInfo>();
2004
25.2k
  TII = STI->getInstrInfo();
2005
25.2k
  TRI = STI->getRegisterInfo();
2006
25.2k
2007
25.2k
  RegClassInfoValid = false;
2008
25.2k
  isThumb2 = AFI->isThumb2Function();
2009
25.2k
  isThumb1 = AFI->isThumbFunction() && 
!isThumb217.0k
;
2010
25.2k
2011
25.2k
  bool Modified = false;
2012
136k
  for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
2013
110k
       ++MFI) {
2014
110k
    MachineBasicBlock &MBB = *MFI;
2015
110k
    Modified |= LoadStoreMultipleOpti(MBB);
2016
110k
    if (STI->hasV5TOps())
2017
106k
      Modified |= MergeReturnIntoLDM(MBB);
2018
110k
    if (isThumb1)
2019
4.38k
      Modified |= CombineMovBx(MBB);
2020
110k
  }
2021
25.2k
2022
25.2k
  Allocator.DestroyAll();
2023
25.2k
  return Modified;
2024
25.2k
}
2025
2026
#define ARM_PREALLOC_LOAD_STORE_OPT_NAME                                       \
2027
30.1k
  "ARM pre- register allocation load / store optimization pass"
2028
2029
namespace {
2030
2031
  /// Pre- register allocation pass that move load / stores from consecutive
2032
  /// locations close to make it more likely they will be combined later.
2033
  struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{
2034
    static char ID;
2035
2036
    AliasAnalysis *AA;
2037
    const DataLayout *TD;
2038
    const TargetInstrInfo *TII;
2039
    const TargetRegisterInfo *TRI;
2040
    const ARMSubtarget *STI;
2041
    MachineRegisterInfo *MRI;
2042
    MachineFunction *MF;
2043
2044
4.91k
    ARMPreAllocLoadStoreOpt() : MachineFunctionPass(ID) {}
2045
2046
    bool runOnMachineFunction(MachineFunction &Fn) override;
2047
2048
30.1k
    StringRef getPassName() const override {
2049
30.1k
      return ARM_PREALLOC_LOAD_STORE_OPT_NAME;
2050
30.1k
    }
2051
2052
4.90k
    void getAnalysisUsage(AnalysisUsage &AU) const override {
2053
4.90k
      AU.addRequired<AAResultsWrapperPass>();
2054
4.90k
      MachineFunctionPass::getAnalysisUsage(AU);
2055
4.90k
    }
2056
2057
  private:
2058
    bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl,
2059
                          unsigned &NewOpc, unsigned &EvenReg,
2060
                          unsigned &OddReg, unsigned &BaseReg,
2061
                          int &Offset,
2062
                          unsigned &PredReg, ARMCC::CondCodes &Pred,
2063
                          bool &isT2);
2064
    bool RescheduleOps(MachineBasicBlock *MBB,
2065
                       SmallVectorImpl<MachineInstr *> &Ops,
2066
                       unsigned Base, bool isLd,
2067
                       DenseMap<MachineInstr*, unsigned> &MI2LocMap);
2068
    bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
2069
  };
2070
2071
} // end anonymous namespace
2072
2073
char ARMPreAllocLoadStoreOpt::ID = 0;
2074
2075
INITIALIZE_PASS(ARMPreAllocLoadStoreOpt, "arm-prera-ldst-opt",
2076
                ARM_PREALLOC_LOAD_STORE_OPT_NAME, false, false)
2077
2078
// Limit the number of instructions to be rescheduled.
2079
// FIXME: tune this limit, and/or come up with some better heuristics.
2080
static cl::opt<unsigned> InstReorderLimit("arm-prera-ldst-opt-reorder-limit",
2081
                                          cl::init(8), cl::Hidden);
2082
2083
25.2k
bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
2084
25.2k
  if (AssumeMisalignedLoadStores || 
skipFunction(Fn.getFunction())25.2k
)
2085
30
    return false;
2086
25.2k
2087
25.2k
  TD = &Fn.getDataLayout();
2088
25.2k
  STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
2089
25.2k
  TII = STI->getInstrInfo();
2090
25.2k
  TRI = STI->getRegisterInfo();
2091
25.2k
  MRI = &Fn.getRegInfo();
2092
25.2k
  MF  = &Fn;
2093
25.2k
  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
2094
25.2k
2095
25.2k
  bool Modified = false;
2096
25.2k
  for (MachineBasicBlock &MFI : Fn)
2097
113k
    Modified |= RescheduleLoadStoreInstrs(&MFI);
2098
25.2k
2099
25.2k
  return Modified;
2100
25.2k
}
2101
2102
static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base,
2103
                                      MachineBasicBlock::iterator I,
2104
                                      MachineBasicBlock::iterator E,
2105
                                      SmallPtrSetImpl<MachineInstr*> &MemOps,
2106
                                      SmallSet<unsigned, 4> &MemRegs,
2107
                                      const TargetRegisterInfo *TRI,
2108
14.2k
                                      AliasAnalysis *AA) {
2109
14.2k
  // Are there stores / loads / calls between them?
2110
14.2k
  SmallSet<unsigned, 4> AddedRegPressure;
2111
31.0k
  while (++I != E) {
2112
17.2k
    if (I->isDebugInstr() || 
MemOps.count(&*I)17.2k
)
2113
11.2k
      continue;
2114
5.98k
    if (I->isCall() || I->isTerminator() || I->hasUnmodeledSideEffects())
2115
129
      return false;
2116
5.85k
    if (I->mayStore() || 
(5.39k
!isLd5.39k
&&
I->mayLoad()4.94k
))
2117
733
      for (MachineInstr *MemOp : MemOps)
2118
2.02k
        if (I->mayAlias(AA, *MemOp, /*UseTBAA*/ false))
2119
379
          return false;
2120
30.0k
    
for (unsigned j = 0, NumOps = I->getNumOperands(); 5.47k
j != NumOps;
++j24.5k
) {
2121
24.5k
      MachineOperand &MO = I->getOperand(j);
2122
24.5k
      if (!MO.isReg())
2123
9.27k
        continue;
2124
15.3k
      unsigned Reg = MO.getReg();
2125
15.3k
      if (MO.isDef() && 
TRI->regsOverlap(Reg, Base)5.27k
)
2126
0
        return false;
2127
15.3k
      if (Reg != Base && 
!MemRegs.count(Reg)14.9k
)
2128
11.1k
        AddedRegPressure.insert(Reg);
2129
15.3k
    }
2130
5.47k
  }
2131
14.2k
2132
14.2k
  // Estimate register pressure increase due to the transformation.
2133
14.2k
  
if (13.7k
MemRegs.size() <= 413.7k
)
2134
13.5k
    // Ok if we are moving small number of instructions.
2135
13.5k
    return true;
2136
223
  return AddedRegPressure.size() <= MemRegs.size() * 2;
2137
223
}
2138
2139
bool
2140
ARMPreAllocLoadStoreOpt::CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1,
2141
                                          DebugLoc &dl, unsigned &NewOpc,
2142
                                          unsigned &FirstReg,
2143
                                          unsigned &SecondReg,
2144
                                          unsigned &BaseReg, int &Offset,
2145
                                          unsigned &PredReg,
2146
                                          ARMCC::CondCodes &Pred,
2147
6.93k
                                          bool &isT2) {
2148
6.93k
  // Make sure we're allowed to generate LDRD/STRD.
2149
6.93k
  if (!STI->hasV5TEOps())
2150
60
    return false;
2151
6.87k
2152
6.87k
  // FIXME: VLDRS / VSTRS -> VLDRD / VSTRD
2153
6.87k
  unsigned Scale = 1;
2154
6.87k
  unsigned Opcode = Op0->getOpcode();
2155
6.87k
  if (Opcode == ARM::LDRi12) {
2156
41
    NewOpc = ARM::LDRD;
2157
6.83k
  } else if (Opcode == ARM::STRi12) {
2158
69
    NewOpc = ARM::STRD;
2159
6.76k
  } else if (Opcode == ARM::t2LDRi8 || 
Opcode == ARM::t2LDRi126.75k
) {
2160
1.43k
    NewOpc = ARM::t2LDRDi8;
2161
1.43k
    Scale = 4;
2162
1.43k
    isT2 = true;
2163
5.33k
  } else if (Opcode == ARM::t2STRi8 || Opcode == ARM::t2STRi12) {
2164
5.21k
    NewOpc = ARM::t2STRDi8;
2165
5.21k
    Scale = 4;
2166
5.21k
    isT2 = true;
2167
5.21k
  } else {
2168
118
    return false;
2169
118
  }
2170
6.75k
2171
6.75k
  // Make sure the base address satisfies i64 ld / st alignment requirement.
2172
6.75k
  // At the moment, we ignore the memoryoperand's value.
2173
6.75k
  // If we want to use AliasAnalysis, we should check it accordingly.
2174
6.75k
  if (!Op0->hasOneMemOperand() ||
2175
6.75k
      (*Op0->memoperands_begin())->isVolatile() ||
2176
6.75k
      (*Op0->memoperands_begin())->isAtomic())
2177
0
    return false;
2178
6.75k
2179
6.75k
  unsigned Align = (*Op0->memoperands_begin())->getAlignment();
2180
6.75k
  const Function &Func = MF->getFunction();
2181
6.75k
  unsigned ReqAlign = STI->hasV6Ops()
2182
6.75k
    ? TD->getABITypeAlignment(Type::getInt64Ty(Func.getContext()))
2183
6.75k
    : 
80
; // Pre-v6 need 8-byte align
2184
6.75k
  if (Align < ReqAlign)
2185
1.94k
    return false;
2186
4.81k
2187
4.81k
  // Then make sure the immediate offset fits.
2188
4.81k
  int OffImm = getMemoryOpOffset(*Op0);
2189
4.81k
  if (isT2) {
2190
4.71k
    int Limit = (1 << 8) * Scale;
2191
4.71k
    if (OffImm >= Limit || 
(OffImm <= -Limit)4.69k
||
(OffImm & (Scale-1))4.69k
)
2192
19
      return false;
2193
4.69k
    Offset = OffImm;
2194
4.69k
  } else {
2195
101
    ARM_AM::AddrOpc AddSub = ARM_AM::add;
2196
101
    if (OffImm < 0) {
2197
0
      AddSub = ARM_AM::sub;
2198
0
      OffImm = - OffImm;
2199
0
    }
2200
101
    int Limit = (1 << 8) * Scale;
2201
101
    if (OffImm >= Limit || (OffImm & (Scale-1)))
2202
0
      return false;
2203
101
    Offset = ARM_AM::getAM3Opc(AddSub, OffImm);
2204
101
  }
2205
4.81k
  FirstReg = Op0->getOperand(0).getReg();
2206
4.79k
  SecondReg = Op1->getOperand(0).getReg();
2207
4.79k
  if (FirstReg == SecondReg)
2208
185
    return false;
2209
4.60k
  BaseReg = Op0->getOperand(1).getReg();
2210
4.60k
  Pred = getInstrPredicate(*Op0, PredReg);
2211
4.60k
  dl = Op0->getDebugLoc();
2212
4.60k
  return true;
2213
4.60k
}
2214
2215
bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB,
2216
                                 SmallVectorImpl<MachineInstr *> &Ops,
2217
                                 unsigned Base, bool isLd,
2218
14.7k
                                 DenseMap<MachineInstr*, unsigned> &MI2LocMap) {
2219
14.7k
  bool RetVal = false;
2220
14.7k
2221
14.7k
  // Sort by offset (in reverse order).
2222
36.0k
  llvm::sort(Ops, [](const MachineInstr *LHS, const MachineInstr *RHS) {
2223
36.0k
    int LOffset = getMemoryOpOffset(*LHS);
2224
36.0k
    int ROffset = getMemoryOpOffset(*RHS);
2225
36.0k
    assert(LHS == RHS || LOffset != ROffset);
2226
36.0k
    return LOffset > ROffset;
2227
36.0k
  });
2228
14.7k
2229
14.7k
  // The loads / stores of the same base are in order. Scan them from first to
2230
14.7k
  // last and check for the following:
2231
14.7k
  // 1. Any def of base.
2232
14.7k
  // 2. Any gaps.
2233
30.3k
  while (Ops.size() > 1) {
2234
15.6k
    unsigned FirstLoc = ~0U;
2235
15.6k
    unsigned LastLoc = 0;
2236
15.6k
    MachineInstr *FirstOp = nullptr;
2237
15.6k
    MachineInstr *LastOp = nullptr;
2238
15.6k
    int LastOffset = 0;
2239
15.6k
    unsigned LastOpcode = 0;
2240
15.6k
    unsigned LastBytes = 0;
2241
15.6k
    unsigned NumMove = 0;
2242
57.7k
    for (int i = Ops.size() - 1; i >= 0; 
--i42.0k
) {
2243
44.0k
      // Make sure each operation has the same kind.
2244
44.0k
      MachineInstr *Op = Ops[i];
2245
44.0k
      unsigned LSMOpcode
2246
44.0k
        = getLoadStoreMultipleOpcode(Op->getOpcode(), ARM_AM::ia);
2247
44.0k
      if (LastOpcode && 
LSMOpcode != LastOpcode28.3k
)
2248
62
        break;
2249
43.9k
2250
43.9k
      // Check that we have a continuous set of offsets.
2251
43.9k
      int Offset = getMemoryOpOffset(*Op);
2252
43.9k
      unsigned Bytes = getLSMultipleTransferSize(Op);
2253
43.9k
      if (LastBytes) {
2254
28.2k
        if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes))
2255
1.73k
          break;
2256
42.2k
      }
2257
42.2k
2258
42.2k
      // Don't try to reschedule too many instructions.
2259
42.2k
      if (NumMove == InstReorderLimit)
2260
151
        break;
2261
42.0k
2262
42.0k
      // Found a mergable instruction; save information about it.
2263
42.0k
      ++NumMove;
2264
42.0k
      LastOffset = Offset;
2265
42.0k
      LastBytes = Bytes;
2266
42.0k
      LastOpcode = LSMOpcode;
2267
42.0k
2268
42.0k
      unsigned Loc = MI2LocMap[Op];
2269
42.0k
      if (Loc <= FirstLoc) {
2270
36.5k
        FirstLoc = Loc;
2271
36.5k
        FirstOp = Op;
2272
36.5k
      }
2273
42.0k
      if (Loc >= LastLoc) {
2274
20.4k
        LastLoc = Loc;
2275
20.4k
        LastOp = Op;
2276
20.4k
      }
2277
42.0k
    }
2278
15.6k
2279
15.6k
    if (NumMove <= 1)
2280
1.34k
      Ops.pop_back();
2281
14.3k
    else {
2282
14.3k
      SmallPtrSet<MachineInstr*, 4> MemOps;
2283
14.3k
      SmallSet<unsigned, 4> MemRegs;
2284
55.0k
      for (size_t i = Ops.size() - NumMove, e = Ops.size(); i != e; 
++i40.7k
) {
2285
40.7k
        MemOps.insert(Ops[i]);
2286
40.7k
        MemRegs.insert(Ops[i]->getOperand(0).getReg());
2287
40.7k
      }
2288
14.3k
2289
14.3k
      // Be conservative, if the instructions are too far apart, don't
2290
14.3k
      // move them. We want to limit the increase of register pressure.
2291
14.3k
      bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this.
2292
14.3k
      if (DoMove)
2293
14.2k
        DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp,
2294
14.2k
                                           MemOps, MemRegs, TRI, AA);
2295
14.3k
      if (!DoMove) {
2296
2.64k
        for (unsigned i = 0; i != NumMove; 
++i2.08k
)
2297
2.08k
          Ops.pop_back();
2298
13.7k
      } else {
2299
13.7k
        // This is the new location for the loads / stores.
2300
13.7k
        MachineBasicBlock::iterator InsertPos = isLd ? 
FirstOp1.83k
:
LastOp11.9k
;
2301
29.7k
        while (InsertPos != MBB->end() &&
2302
29.7k
               
(29.5k
MemOps.count(&*InsertPos)29.5k
||
InsertPos->isDebugInstr()13.5k
))
2303
15.9k
          ++InsertPos;
2304
13.7k
2305
13.7k
        // If we are moving a pair of loads / stores, see if it makes sense
2306
13.7k
        // to try to allocate a pair of registers that can form register pairs.
2307
13.7k
        MachineInstr *Op0 = Ops.back();
2308
13.7k
        MachineInstr *Op1 = Ops[Ops.size()-2];
2309
13.7k
        unsigned FirstReg = 0, SecondReg = 0;
2310
13.7k
        unsigned BaseReg = 0, PredReg = 0;
2311
13.7k
        ARMCC::CondCodes Pred = ARMCC::AL;
2312
13.7k
        bool isT2 = false;
2313
13.7k
        unsigned NewOpc = 0;
2314
13.7k
        int Offset = 0;
2315
13.7k
        DebugLoc dl;
2316
13.7k
        if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc,
2317
6.93k
                                             FirstReg, SecondReg, BaseReg,
2318
6.93k
                                             Offset, PredReg, Pred, isT2)) {
2319
4.60k
          Ops.pop_back();
2320
4.60k
          Ops.pop_back();
2321
4.60k
2322
4.60k
          const MCInstrDesc &MCID = TII->get(NewOpc);
2323
4.60k
          const TargetRegisterClass *TRC = TII->getRegClass(MCID, 0, TRI, *MF);
2324
4.60k
          MRI->constrainRegClass(FirstReg, TRC);
2325
4.60k
          MRI->constrainRegClass(SecondReg, TRC);
2326
4.60k
2327
4.60k
          // Form the pair instruction.
2328
4.60k
          if (isLd) {
2329
1.10k
            MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
2330
1.10k
              .addReg(FirstReg, RegState::Define)
2331
1.10k
              .addReg(SecondReg, RegState::Define)
2332
1.10k
              .addReg(BaseReg);
2333
1.10k
            // FIXME: We're converting from LDRi12 to an insn that still
2334
1.10k
            // uses addrmode2, so we need an explicit offset reg. It should
2335
1.10k
            // always by reg0 since we're transforming LDRi12s.
2336
1.10k
            if (!isT2)
2337
35
              MIB.addReg(0);
2338
1.10k
            MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
2339
1.10k
            MIB.cloneMergedMemRefs({Op0, Op1});
2340
1.10k
            LLVM_DEBUG(dbgs() << "Formed " << *MIB << "\n");
2341
1.10k
            ++NumLDRDFormed;
2342
3.50k
          } else {
2343
3.50k
            MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
2344
3.50k
              .addReg(FirstReg)
2345
3.50k
              .addReg(SecondReg)
2346
3.50k
              .addReg(BaseReg);
2347
3.50k
            // FIXME: We're converting from LDRi12 to an insn that still
2348
3.50k
            // uses addrmode2, so we need an explicit offset reg. It should
2349
3.50k
            // always by reg0 since we're transforming STRi12s.
2350
3.50k
            if (!isT2)
2351
65
              MIB.addReg(0);
2352
3.50k
            MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
2353
3.50k
            MIB.cloneMergedMemRefs({Op0, Op1});
2354
3.50k
            LLVM_DEBUG(dbgs() << "Formed " << *MIB << "\n");
2355
3.50k
            ++NumSTRDFormed;
2356
3.50k
          }
2357
4.60k
          MBB->erase(Op0);
2358
4.60k
          MBB->erase(Op1);
2359
4.60k
2360
4.60k
          if (!isT2) {
2361
100
            // Add register allocation hints to form register pairs.
2362
100
            MRI->setRegAllocationHint(FirstReg, ARMRI::RegPairEven, SecondReg);
2363
100
            MRI->setRegAllocationHint(SecondReg,  ARMRI::RegPairOdd, FirstReg);
2364
100
          }
2365
9.17k
        } else {
2366
38.5k
          for (unsigned i = 0; i != NumMove; 
++i29.4k
) {
2367
29.4k
            MachineInstr *Op = Ops.back();
2368
29.4k
            Ops.pop_back();
2369
29.4k
            MBB->splice(InsertPos, MBB, Op);
2370
29.4k
          }
2371
9.17k
        }
2372
13.7k
2373
13.7k
        NumLdStMoved += NumMove;
2374
13.7k
        RetVal = true;
2375
13.7k
      }
2376
14.3k
    }
2377
15.6k
  }
2378
14.7k
2379
14.7k
  return RetVal;
2380
14.7k
}
2381
2382
bool
2383
113k
ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {
2384
113k
  bool RetVal = false;
2385
113k
2386
113k
  DenseMap<MachineInstr*, unsigned> MI2LocMap;
2387
113k
  using MapIt = DenseMap<unsigned, SmallVector<MachineInstr *, 4>>::iterator;
2388
113k
  using Base2InstMap = DenseMap<unsigned, SmallVector<MachineInstr *, 4>>;
2389
113k
  using BaseVec = SmallVector<unsigned, 4>;
2390
113k
  Base2InstMap Base2LdsMap;
2391
113k
  Base2InstMap Base2StsMap;
2392
113k
  BaseVec LdBases;
2393
113k
  BaseVec StBases;
2394
113k
2395
113k
  unsigned Loc = 0;
2396
113k
  MachineBasicBlock::iterator MBBI = MBB->begin();
2397
113k
  MachineBasicBlock::iterator E = MBB->end();
2398
322k
  while (MBBI != E) {
2399
1.01M
    for (; MBBI != E; 
++MBBI801k
) {
2400
988k
      MachineInstr &MI = *MBBI;
2401
988k
      if (MI.isCall() || 
MI.isTerminator()930k
) {
2402
186k
        // Stop at barriers.
2403
186k
        ++MBBI;
2404
186k
        break;
2405
186k
      }
2406
801k
2407
801k
      if (!MI.isDebugInstr())
2408
801k
        MI2LocMap[&MI] = ++Loc;
2409
801k
2410
801k
      if (!isMemoryOp(MI))
2411
726k
        continue;
2412
74.9k
      unsigned PredReg = 0;
2413
74.9k
      if (getInstrPredicate(MI, PredReg) != ARMCC::AL)
2414
0
        continue;
2415
74.9k
2416
74.9k
      int Opc = MI.getOpcode();
2417
74.9k
      bool isLd = isLoadSingle(Opc);
2418
74.9k
      unsigned Base = MI.getOperand(1).getReg();
2419
74.9k
      int Offset = getMemoryOpOffset(MI);
2420
74.9k
      bool StopHere = false;
2421
74.9k
      auto FindBases = [&] (Base2InstMap &Base2Ops, BaseVec &Bases) {
2422
74.9k
        MapIt BI = Base2Ops.find(Base);
2423
74.9k
        if (BI == Base2Ops.end()) {
2424
46.5k
          Base2Ops[Base].push_back(&MI);
2425
46.5k
          Bases.push_back(Base);
2426
46.5k
          return;
2427
46.5k
        }
2428
113k
        
for (unsigned i = 0, e = BI->second.size(); 28.3k
i != e;
++i84.7k
) {
2429
84.7k
          if (Offset == getMemoryOpOffset(*BI->second[i])) {
2430
51
            StopHere = true;
2431
51
            break;
2432
51
          }
2433
84.7k
        }
2434
28.3k
        if (!StopHere)
2435
28.3k
          BI->second.push_back(&MI);
2436
28.3k
      };
2437
74.9k
2438
74.9k
      if (isLd)
2439
30.9k
        FindBases(Base2LdsMap, LdBases);
2440
44.0k
      else
2441
44.0k
        FindBases(Base2StsMap, StBases);
2442
74.9k
2443
74.9k
      if (StopHere) {
2444
51
        // Found a duplicate (a base+offset combination that's seen earlier).
2445
51
        // Backtrack.
2446
51
        --Loc;
2447
51
        break;
2448
51
      }
2449
74.9k
    }
2450
209k
2451
209k
    // Re-schedule loads.
2452
236k
    for (unsigned i = 0, e = LdBases.size(); i != e; 
++i27.4k
) {
2453
27.4k
      unsigned Base = LdBases[i];
2454
27.4k
      SmallVectorImpl<MachineInstr *> &Lds = Base2LdsMap[Base];
2455
27.4k
      if (Lds.size() > 1)
2456
2.48k
        RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap);
2457
27.4k
    }
2458
209k
2459
209k
    // Re-schedule stores.
2460
228k
    for (unsigned i = 0, e = StBases.size(); i != e; 
++i19.1k
) {
2461
19.1k
      unsigned Base = StBases[i];
2462
19.1k
      SmallVectorImpl<MachineInstr *> &Sts = Base2StsMap[Base];
2463
19.1k
      if (Sts.size() > 1)
2464
12.2k
        RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap);
2465
19.1k
    }
2466
209k
2467
209k
    if (MBBI != E) {
2468
96.0k
      Base2LdsMap.clear();
2469
96.0k
      Base2StsMap.clear();
2470
96.0k
      LdBases.clear();
2471
96.0k
      StBases.clear();
2472
96.0k
    }
2473
209k
  }
2474
113k
2475
113k
  return RetVal;
2476
113k
}
2477
2478
/// Returns an instance of the load / store optimization pass.
2479
9.83k
FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) {
2480
9.83k
  if (PreAlloc)
2481
4.91k
    return new ARMPreAllocLoadStoreOpt();
2482
4.91k
  return new ARMLoadStoreOpt();
2483
4.91k
}