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 |
172 | |