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
26namespace llvm {
27// Forward declarations.
28class AnalysisUsage;
29class GStore;
30class LegalizerInfo;
31class MachineBasicBlock;
32class MachineInstr;
33class TargetLowering;
34struct LegalityQuery;
35class MachineRegisterInfo;
36namespace GISelAddressing {
37/// Helper struct to store a base, index and offset that forms an address
38struct 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.
46BaseIndexOffset 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.
51bool 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.
58bool instMayAlias(const MachineInstr &MI, const MachineInstr &Other,
59 MachineRegisterInfo &MRI, AliasAnalysis *AA);
60} // namespace GISelAddressing
61
62using namespace GISelAddressing;
63
64class LoadStoreOpt : public MachineFunctionPass {
65public:
66 static char ID;
67
68private:
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
153public:
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

source code of llvm/include/llvm/CodeGen/GlobalISel/LoadStoreOpt.h