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