LCOV - code coverage report
Current view: top level - lib/Target/ARM - ARMLoadStoreOptimizer.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 991 1103 89.8 %
Date: 2017-09-14 15:23:50 Functions: 47 48 97.9 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13