1 //== llvm/CodeGen/GlobalISel/LoadStoreOpt.h - LoadStoreOpt -------*- C++ -*-==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 /// This is an optimization pass for GlobalISel generic memory operations. 10 /// Specifically, it focuses on merging stores and loads to consecutive 11 /// addresses. 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CODEGEN_GLOBALISEL_LOADSTOREOPT_H 15 #define LLVM_CODEGEN_GLOBALISEL_LOADSTOREOPT_H 16 17 #include "llvm/ADT/BitVector.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/SmallSet.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/Analysis/AliasAnalysis.h" 22 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" 23 #include "llvm/CodeGen/MachineFunction.h" 24 #include "llvm/CodeGen/MachineFunctionPass.h" 25 #include "llvm/Support/Compiler.h" 26 27 namespace llvm { 28 // Forward declarations. 29 class AnalysisUsage; 30 class GStore; 31 class LegalizerInfo; 32 class MachineBasicBlock; 33 class MachineInstr; 34 class TargetLowering; 35 struct LegalityQuery; 36 class MachineRegisterInfo; 37 namespace GISelAddressing { 38 /// Helper struct to store a base, index and offset that forms an address 39 class BaseIndexOffset { 40 private: 41 Register BaseReg; 42 Register IndexReg; 43 std::optional<int64_t> Offset; 44 45 public: 46 BaseIndexOffset() = default; getBase()47 Register getBase() { return BaseReg; } getBase()48 Register getBase() const { return BaseReg; } getIndex()49 Register getIndex() { return IndexReg; } getIndex()50 Register getIndex() const { return IndexReg; } setBase(Register NewBase)51 void setBase(Register NewBase) { BaseReg = NewBase; } setIndex(Register NewIndex)52 void setIndex(Register NewIndex) { IndexReg = NewIndex; } setOffset(std::optional<int64_t> NewOff)53 void setOffset(std::optional<int64_t> NewOff) { Offset = NewOff; } hasValidOffset()54 bool hasValidOffset() const { return Offset.has_value(); } getOffset()55 int64_t getOffset() const { return *Offset; } 56 }; 57 58 /// Returns a BaseIndexOffset which describes the pointer in \p Ptr. 59 LLVM_ABI BaseIndexOffset getPointerInfo(Register Ptr, MachineRegisterInfo &MRI); 60 61 /// Compute whether or not a memory access at \p MI1 aliases with an access at 62 /// \p MI2 \returns true if either alias/no-alias is known. Sets \p IsAlias 63 /// accordingly. 64 LLVM_ABI bool aliasIsKnownForLoadStore(const MachineInstr &MI1, 65 const MachineInstr &MI2, bool &IsAlias, 66 MachineRegisterInfo &MRI); 67 68 /// Returns true if the instruction \p MI may alias \p Other. 69 /// This function uses multiple strategies to detect aliasing, whereas 70 /// aliasIsKnownForLoadStore just looks at the addresses of load/stores and is 71 /// tries to reason about base/index/offsets. 72 LLVM_ABI bool instMayAlias(const MachineInstr &MI, const MachineInstr &Other, 73 MachineRegisterInfo &MRI, AliasAnalysis *AA); 74 } // namespace GISelAddressing 75 76 using namespace GISelAddressing; 77 78 class LLVM_ABI LoadStoreOpt : public MachineFunctionPass { 79 public: 80 static char ID; 81 82 private: 83 /// An input function to decide if the pass should run or not 84 /// on the given MachineFunction. 85 std::function<bool(const MachineFunction &)> DoNotRunPass; 86 87 MachineRegisterInfo *MRI = nullptr; 88 const TargetLowering *TLI = nullptr; 89 MachineFunction *MF = nullptr; 90 AliasAnalysis *AA = nullptr; 91 const LegalizerInfo *LI = nullptr; 92 93 MachineIRBuilder Builder; 94 95 /// Initialize the field members using \p MF. 96 void init(MachineFunction &MF); 97 98 class StoreMergeCandidate { 99 public: 100 // The base pointer used as the base for all stores in this candidate. 101 Register BasePtr; 102 // Our algorithm is very simple at the moment. We assume that in instruction 103 // order stores are writing to incremeneting consecutive addresses. So when 104 // we walk the block in reverse order, the next eligible store must write to 105 // an offset one store width lower than CurrentLowestOffset. 106 int64_t CurrentLowestOffset; 107 SmallVector<GStore *> Stores; 108 // A vector of MachineInstr/unsigned pairs to denote potential aliases that 109 // need to be checked before the candidate is considered safe to merge. The 110 // unsigned value is an index into the Stores vector. The indexed store is 111 // the highest-indexed store that has already been checked to not have an 112 // alias with the instruction. We record this so we don't have to repeat 113 // alias checks that have been already done, only those with stores added 114 // after the potential alias is recorded. 115 SmallVector<std::pair<MachineInstr *, unsigned>> PotentialAliases; 116 117 LLVM_ABI void addPotentialAlias(MachineInstr &MI); 118 119 /// Reset this candidate back to an empty one. reset()120 void reset() { 121 Stores.clear(); 122 PotentialAliases.clear(); 123 CurrentLowestOffset = 0; 124 BasePtr = Register(); 125 } 126 }; 127 128 bool isLegalOrBeforeLegalizer(const LegalityQuery &Query, 129 MachineFunction &MF) const; 130 /// If the given store is valid to be a member of the candidate, add it and 131 /// return true. Otherwise, returns false. 132 bool addStoreToCandidate(GStore &MI, StoreMergeCandidate &C); 133 /// Returns true if the instruction \p MI would potentially alias with any 134 /// stores in the candidate \p C. 135 bool operationAliasesWithCandidate(MachineInstr &MI, StoreMergeCandidate &C); 136 /// Merges the stores in the given vector into a wide store. 137 /// \p returns true if at least some of the stores were merged. 138 /// This may decide not to merge stores if heuristics predict it will not be 139 /// worth it. 140 bool mergeStores(SmallVectorImpl<GStore *> &StoresToMerge); 141 /// Perform a merge of all the stores in \p Stores into a single store. 142 /// Erases the old stores from the block when finished. 143 /// \returns true if merging was done. It may fail to perform a merge if 144 /// there are issues with materializing legal wide values. 145 bool doSingleStoreMerge(SmallVectorImpl<GStore *> &Stores); 146 bool processMergeCandidate(StoreMergeCandidate &C); 147 bool mergeBlockStores(MachineBasicBlock &MBB); 148 bool mergeFunctionStores(MachineFunction &MF); 149 150 bool mergeTruncStore(GStore &StoreMI, 151 SmallPtrSetImpl<GStore *> &DeletedStores); 152 bool mergeTruncStoresBlock(MachineBasicBlock &MBB); 153 154 /// Initialize some target-specific data structures for the store merging 155 /// optimization. \p AddrSpace indicates which address space to use when 156 /// probing the legalizer info for legal stores. 157 void initializeStoreMergeTargetInfo(unsigned AddrSpace = 0); 158 /// A map between address space numbers and a bitvector of supported stores 159 /// sizes. Each bit in the bitvector represents whether a store size of 160 /// that bit's value is legal. E.g. if bit 64 is set, then 64 bit scalar 161 /// stores are legal. 162 DenseMap<unsigned, BitVector> LegalStoreSizes; 163 bool IsPreLegalizer = false; 164 /// Contains instructions to be erased at the end of a block scan. 165 SmallSet<MachineInstr *, 16> InstsToErase; 166 167 public: 168 LoadStoreOpt(); 169 LoadStoreOpt(std::function<bool(const MachineFunction &)>); 170 getPassName()171 StringRef getPassName() const override { return "LoadStoreOpt"; } 172 getRequiredProperties()173 MachineFunctionProperties getRequiredProperties() const override { 174 return MachineFunctionProperties().setIsSSA(); 175 } 176 177 void getAnalysisUsage(AnalysisUsage &AU) const override; 178 179 bool runOnMachineFunction(MachineFunction &MF) override; 180 }; 181 182 } // End namespace llvm. 183 184 #endif 185