//===- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass -------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // /// \file This file contains a pass that performs load / store related peephole /// optimizations. This pass should be run after register allocation. // //===----------------------------------------------------------------------===// #include "ARM.h" #include "ARMBaseInstrInfo.h" #include "ARMBaseRegisterInfo.h" #include "ARMISelLowering.h" #include "ARMMachineFunctionInfo.h" #include "ARMSubtarget.h" #include "MCTargetDesc/ARMAddressingModes.h" #include "MCTargetDesc/ARMBaseInfo.h" #include "Utils/ARMBaseInfo.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveRegUnits.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/RegisterClassInfo.h" #include "llvm/CodeGen/TargetFrameLowering.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetLowering.h" #include "llvm/CodeGen/TargetRegisterInfo.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DebugLoc.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Function.h" #include "llvm/IR/Type.h" #include "llvm/InitializePasses.h" #include "llvm/MC/MCInstrDesc.h" #include "llvm/Pass.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> #include <cassert> #include <cstddef> #include <cstdlib> #include <iterator> #include <limits> #include <utility> usingnamespacellvm; #define DEBUG_TYPE … STATISTIC(NumLDMGened , "Number of ldm instructions generated"); STATISTIC(NumSTMGened , "Number of stm instructions generated"); STATISTIC(NumVLDMGened, "Number of vldm instructions generated"); STATISTIC(NumVSTMGened, "Number of vstm instructions generated"); STATISTIC(NumLdStMoved, "Number of load / store instructions moved"); STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation"); STATISTIC(NumSTRDFormed,"Number of strd created before allocation"); STATISTIC(NumLDRD2LDM, "Number of ldrd instructions turned back into ldm"); STATISTIC(NumSTRD2STM, "Number of strd instructions turned back into stm"); STATISTIC(NumLDRD2LDR, "Number of ldrd instructions turned back into ldr's"); STATISTIC(NumSTRD2STR, "Number of strd instructions turned back into str's"); /// This switch disables formation of double/multi instructions that could /// potentially lead to (new) alignment traps even with CCR.UNALIGN_TRP /// disabled. This can be used to create libraries that are robust even when /// users provoke undefined behaviour by supplying misaligned pointers. /// \see mayCombineMisaligned() static cl::opt<bool> AssumeMisalignedLoadStores("arm-assume-misaligned-load-store", cl::Hidden, cl::init(false), cl::desc("Be more conservative in ARM load/store opt")); #define ARM_LOAD_STORE_OPT_NAME … namespace { /// Post- register allocation pass the combine load / store instructions to /// form ldm / stm instructions. struct ARMLoadStoreOpt : public MachineFunctionPass { … }; } // end anonymous namespace char ARMLoadStoreOpt::ID = …; INITIALIZE_PASS(…) static bool definesCPSR(const MachineInstr &MI) { … } static int getMemoryOpOffset(const MachineInstr &MI) { … } static const MachineOperand &getLoadStoreBaseOp(const MachineInstr &MI) { … } static const MachineOperand &getLoadStoreRegOp(const MachineInstr &MI) { … } static int getLoadStoreMultipleOpcode(unsigned Opcode, ARM_AM::AMSubMode Mode) { … } static ARM_AM::AMSubMode getLoadStoreMultipleSubMode(unsigned Opcode) { … } static bool isT1i32Load(unsigned Opc) { … } static bool isT2i32Load(unsigned Opc) { … } static bool isi32Load(unsigned Opc) { … } static bool isT1i32Store(unsigned Opc) { … } static bool isT2i32Store(unsigned Opc) { … } static bool isi32Store(unsigned Opc) { … } static bool isLoadSingle(unsigned Opc) { … } static unsigned getImmScale(unsigned Opc) { … } static unsigned getLSMultipleTransferSize(const MachineInstr *MI) { … } /// Update future uses of the base register with the offset introduced /// due to writeback. This function only works on Thumb1. void ARMLoadStoreOpt::UpdateBaseRegUses(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, const DebugLoc &DL, unsigned Base, unsigned WordOffset, ARMCC::CondCodes Pred, unsigned PredReg) { … } /// Return the first register of class \p RegClass that is not in \p Regs. unsigned ARMLoadStoreOpt::findFreeReg(const TargetRegisterClass &RegClass) { … } /// Compute live registers just before instruction \p Before (in normal schedule /// direction). Computes backwards so multiple queries in the same block must /// come in reverse order. void ARMLoadStoreOpt::moveLiveRegsBefore(const MachineBasicBlock &MBB, MachineBasicBlock::const_iterator Before) { … } static bool ContainsReg(const ArrayRef<std::pair<unsigned, bool>> &Regs, unsigned Reg) { … } /// Create and insert a LDM or STM with Base as base register and registers in /// Regs as the register operands that would be loaded / stored. It returns /// true if the transformation is done. MachineInstr *ARMLoadStoreOpt::CreateLoadStoreMulti( MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore, int Offset, unsigned Base, bool BaseKill, unsigned Opcode, ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL, ArrayRef<std::pair<unsigned, bool>> Regs, ArrayRef<MachineInstr*> Instrs) { … } MachineInstr *ARMLoadStoreOpt::CreateLoadStoreDouble( MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore, int Offset, unsigned Base, bool BaseKill, unsigned Opcode, ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL, ArrayRef<std::pair<unsigned, bool>> Regs, ArrayRef<MachineInstr*> Instrs) const { … } /// Call MergeOps and update MemOps and merges accordingly on success. MachineInstr *ARMLoadStoreOpt::MergeOpsUpdate(const MergeCandidate &Cand) { … } static bool isValidLSDoubleOffset(int Offset) { … } /// Return true for loads/stores that can be combined to a double/multi /// operation without increasing the requirements for alignment. static bool mayCombineMisaligned(const TargetSubtargetInfo &STI, const MachineInstr &MI) { … } /// Find candidates for load/store multiple merge in list of MemOpQueueEntries. void ARMLoadStoreOpt::FormCandidates(const MemOpQueue &MemOps) { … } static unsigned getUpdatingLSMultipleOpcode(unsigned Opc, ARM_AM::AMSubMode Mode) { … } /// Check if the given instruction increments or decrements a register and /// return the amount it is incremented/decremented. Returns 0 if the CPSR flags /// generated by the instruction are possibly read as well. static int isIncrementOrDecrement(const MachineInstr &MI, Register Reg, ARMCC::CondCodes Pred, Register PredReg) { … } /// Searches for an increment or decrement of \p Reg before \p MBBI. static MachineBasicBlock::iterator findIncDecBefore(MachineBasicBlock::iterator MBBI, Register Reg, ARMCC::CondCodes Pred, Register PredReg, int &Offset) { … } /// Searches for a increment or decrement of \p Reg after \p MBBI. static MachineBasicBlock::iterator findIncDecAfter(MachineBasicBlock::iterator MBBI, Register Reg, ARMCC::CondCodes Pred, Register PredReg, int &Offset, const TargetRegisterInfo *TRI) { … } /// Fold proceeding/trailing inc/dec of base register into the /// LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible: /// /// stmia rn, <ra, rb, rc> /// rn := rn + 4 * 3; /// => /// stmia rn!, <ra, rb, rc> /// /// rn := rn - 4 * 3; /// ldmia rn, <ra, rb, rc> /// => /// ldmdb rn!, <ra, rb, rc> bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineInstr *MI) { … } static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc, ARM_AM::AddrOpc Mode) { … } static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc, ARM_AM::AddrOpc Mode) { … } /// Fold proceeding/trailing inc/dec of base register into the /// LDR/STR/FLD{D|S}/FST{D|S} op when possible: bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineInstr *MI) { … } bool ARMLoadStoreOpt::MergeBaseUpdateLSDouble(MachineInstr &MI) const { … } /// Returns true if instruction is a memory operation that this pass is capable /// of operating on. static bool isMemoryOp(const MachineInstr &MI) { … } static void InsertLDR_STR(MachineBasicBlock &MBB, MachineBasicBlock::iterator &MBBI, int Offset, bool isDef, unsigned NewOpc, unsigned Reg, bool RegDeadKill, bool RegUndef, unsigned BaseReg, bool BaseKill, bool BaseUndef, ARMCC::CondCodes Pred, unsigned PredReg, const TargetInstrInfo *TII, MachineInstr *MI) { … } bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB, MachineBasicBlock::iterator &MBBI) { … } /// An optimization pass to turn multiple LDR / STR ops of the same base and /// incrementing offset into LDM / STM ops. bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) { … } /// If this is a exit BB, try merging the return ops ("bx lr" and "mov pc, lr") /// into the preceding stack restore so it directly restore the value of LR /// into pc. /// ldmfd sp!, {..., lr} /// bx lr /// or /// ldmfd sp!, {..., lr} /// mov pc, lr /// => /// ldmfd sp!, {..., pc} bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) { … } bool ARMLoadStoreOpt::CombineMovBx(MachineBasicBlock &MBB) { … } bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) { … } #define ARM_PREALLOC_LOAD_STORE_OPT_NAME … namespace { /// Pre- register allocation pass that move load / stores from consecutive /// locations close to make it more likely they will be combined later. struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{ … }; } // end anonymous namespace char ARMPreAllocLoadStoreOpt::ID = …; INITIALIZE_PASS_BEGIN(ARMPreAllocLoadStoreOpt, "arm-prera-ldst-opt", ARM_PREALLOC_LOAD_STORE_OPT_NAME, false, false) INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass) INITIALIZE_PASS_END(ARMPreAllocLoadStoreOpt, "arm-prera-ldst-opt", ARM_PREALLOC_LOAD_STORE_OPT_NAME, false, false) // Limit the number of instructions to be rescheduled. // FIXME: tune this limit, and/or come up with some better heuristics. static cl::opt<unsigned> InstReorderLimit("arm-prera-ldst-opt-reorder-limit", cl::init(8), cl::Hidden); bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) { … } static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base, MachineBasicBlock::iterator I, MachineBasicBlock::iterator E, SmallPtrSetImpl<MachineInstr*> &MemOps, SmallSet<unsigned, 4> &MemRegs, const TargetRegisterInfo *TRI, AliasAnalysis *AA) { … } bool ARMPreAllocLoadStoreOpt::CanFormLdStDWord( MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl, unsigned &NewOpc, Register &FirstReg, Register &SecondReg, Register &BaseReg, int &Offset, Register &PredReg, ARMCC::CondCodes &Pred, bool &isT2) { … } bool ARMPreAllocLoadStoreOpt::RescheduleOps( MachineBasicBlock *MBB, SmallVectorImpl<MachineInstr *> &Ops, unsigned Base, bool isLd, DenseMap<MachineInstr *, unsigned> &MI2LocMap, SmallDenseMap<Register, SmallVector<MachineInstr *>, 8> &RegisterMap) { … } static void forEachDbgRegOperand(MachineInstr *MI, std::function<void(MachineOperand &)> Fn) { … } // Update the RegisterMap with the instruction that was moved because a // DBG_VALUE_LIST may need to be moved again. static void updateRegisterMapForDbgValueListAfterMove( SmallDenseMap<Register, SmallVector<MachineInstr *>, 8> &RegisterMap, MachineInstr *DbgValueListInstr, MachineInstr *InstrToReplace) { … } static DebugVariable createDebugVariableFromMachineInstr(MachineInstr *MI) { … } bool ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) { … } // Get the Base register operand index from the memory access MachineInst if we // should attempt to distribute postinc on it. Return -1 if not of a valid // instruction type. If it returns an index, it is assumed that instruction is a // r+i indexing mode, and getBaseOperandIndex() + 1 is the Offset index. static int getBaseOperandIndex(MachineInstr &MI) { … } static bool isPostIndex(MachineInstr &MI) { … } static bool isPreIndex(MachineInstr &MI) { … } // Given a memory access Opcode, check that the give Imm would be a valid Offset // for this instruction (same as isLegalAddressImm), Or if the instruction // could be easily converted to one where that was valid. For example converting // t2LDRi12 to t2LDRi8 for negative offsets. Works in conjunction with // AdjustBaseAndOffset below. static bool isLegalOrConvertableAddressImm(unsigned Opcode, int Imm, const TargetInstrInfo *TII, int &CodesizeEstimate) { … } // Given an MI adjust its address BaseReg to use NewBaseReg and address offset // by -Offset. This can either happen in-place or be a replacement as MI is // converted to another instruction type. static void AdjustBaseAndOffset(MachineInstr *MI, Register NewBaseReg, int Offset, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) { … } static MachineInstr *createPostIncLoadStore(MachineInstr *MI, int Offset, Register NewReg, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) { … } // Given a Base Register, optimise the load/store uses to attempt to create more // post-inc accesses and less register moves. We do this by taking zero offset // loads/stores with an add, and convert them to a postinc load/store of the // same type. Any subsequent accesses will be adjusted to use and account for // the post-inc value. // For example: // LDR #0 LDR_POSTINC #16 // LDR #4 LDR #-12 // LDR #8 LDR #-8 // LDR #12 LDR #-4 // ADD #16 // // At the same time if we do not find an increment but do find an existing // pre/post inc instruction, we can still adjust the offsets of subsequent // instructions to save the register move that would otherwise be needed for the // in-place increment. bool ARMPreAllocLoadStoreOpt::DistributeIncrements(Register Base) { … } bool ARMPreAllocLoadStoreOpt::DistributeIncrements() { … } /// Returns an instance of the load / store optimization pass. FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) { … }
Codebase Browser
llvm