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