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