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
27namespace llvm {
28// Forward declarations.
29class AnalysisUsage;
30class GStore;
31class LegalizerInfo;
32class MachineBasicBlock;
33class MachineInstr;
34class TargetLowering;
35struct LegalityQuery;
36class MachineRegisterInfo;
37namespace GISelAddressing {
38/// Helper struct to store a base, index and offset that forms an address
39class BaseIndexOffset {
40private:
41 Register BaseReg;
42 Register IndexReg;
43 std::optional<int64_t> Offset;
44
45public:
46 BaseIndexOffset() = default;
47 Register getBase() { return BaseReg; }
48 Register getBase() const { return BaseReg; }
49 Register getIndex() { return IndexReg; }
50 Register getIndex() const { return IndexReg; }
51 void setBase(Register NewBase) { BaseReg = NewBase; }
52 void setIndex(Register NewIndex) { IndexReg = NewIndex; }
53 void setOffset(std::optional<int64_t> NewOff) { Offset = NewOff; }
54 bool hasValidOffset() const { return Offset.has_value(); }
55 int64_t getOffset() const { return *Offset; }
56};
57
58/// Returns a BaseIndexOffset which describes the pointer in \p Ptr.
59LLVM_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.
64LLVM_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.
72LLVM_ABI bool instMayAlias(const MachineInstr &MI, const MachineInstr &Other,
73 MachineRegisterInfo &MRI, AliasAnalysis *AA);
74} // namespace GISelAddressing
75
76using namespace GISelAddressing;
77
78class LLVM_ABI LoadStoreOpt : public MachineFunctionPass {
79public:
80 static char ID;
81
82private:
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.
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
167public:
168 LoadStoreOpt();
169 LoadStoreOpt(std::function<bool(const MachineFunction &)>);
170
171 StringRef getPassName() const override { return "LoadStoreOpt"; }
172
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