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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
| //==- llvm/CodeGen/SelectionDAGAddressAnalysis.cpp - DAG Address Analysis --==//
//
// 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
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/SelectionDAGAddressAnalysis.h"
#include "llvm/CodeGen/ISDOpcodes.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include <cstdint>
using namespace llvm;
bool BaseIndexOffset::equalBaseIndex(const BaseIndexOffset &Other,
const SelectionDAG &DAG,
int64_t &Off) const {
// Conservatively fail if we a match failed..
if (!Base.getNode() || !Other.Base.getNode())
return false;
if (!hasValidOffset() || !Other.hasValidOffset())
return false;
// Initial Offset difference.
Off = *Other.Offset - *Offset;
if ((Other.Index == Index) && (Other.IsIndexSignExt == IsIndexSignExt)) {
// Trivial match.
if (Other.Base == Base)
return true;
// Match GlobalAddresses
if (auto *A = dyn_cast<GlobalAddressSDNode>(Base))
if (auto *B = dyn_cast<GlobalAddressSDNode>(Other.Base))
if (A->getGlobal() == B->getGlobal()) {
Off += B->getOffset() - A->getOffset();
return true;
}
// Match Constants
if (auto *A = dyn_cast<ConstantPoolSDNode>(Base))
if (auto *B = dyn_cast<ConstantPoolSDNode>(Other.Base)) {
bool IsMatch =
A->isMachineConstantPoolEntry() == B->isMachineConstantPoolEntry();
if (IsMatch) {
if (A->isMachineConstantPoolEntry())
IsMatch = A->getMachineCPVal() == B->getMachineCPVal();
else
IsMatch = A->getConstVal() == B->getConstVal();
}
if (IsMatch) {
Off += B->getOffset() - A->getOffset();
return true;
}
}
const MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
// Match FrameIndexes.
if (auto *A = dyn_cast<FrameIndexSDNode>(Base))
if (auto *B = dyn_cast<FrameIndexSDNode>(Other.Base)) {
// Equal FrameIndexes - offsets are directly comparable.
if (A->getIndex() == B->getIndex())
return true;
// Non-equal FrameIndexes - If both frame indices are fixed
// we know their relative offsets and can compare them. Otherwise
// we must be conservative.
if (MFI.isFixedObjectIndex(A->getIndex()) &&
MFI.isFixedObjectIndex(B->getIndex())) {
Off += MFI.getObjectOffset(B->getIndex()) -
MFI.getObjectOffset(A->getIndex());
return true;
}
}
}
return false;
}
bool BaseIndexOffset::computeAliasing(const SDNode *Op0,
const Optional<int64_t> NumBytes0,
const SDNode *Op1,
const Optional<int64_t> NumBytes1,
const SelectionDAG &DAG, bool &IsAlias) {
BaseIndexOffset BasePtr0 = match(Op0, DAG);
BaseIndexOffset BasePtr1 = match(Op1, DAG);
if (!(BasePtr0.getBase().getNode() && BasePtr1.getBase().getNode()))
return false;
int64_t PtrDiff;
if (NumBytes0.hasValue() && NumBytes1.hasValue() &&
BasePtr0.equalBaseIndex(BasePtr1, DAG, PtrDiff)) {
// BasePtr1 is PtrDiff away from BasePtr0. They alias if none of the
// following situations arise:
IsAlias = !(
// [----BasePtr0----]
// [---BasePtr1--]
// ========PtrDiff========>
(*NumBytes0 <= PtrDiff) ||
// [----BasePtr0----]
// [---BasePtr1--]
// =====(-PtrDiff)====>
(PtrDiff + *NumBytes1 <= 0)); // i.e. *NumBytes1 < -PtrDiff.
return true;
}
// If both BasePtr0 and BasePtr1 are FrameIndexes, we will not be
// able to calculate their relative offset if at least one arises
// from an alloca. However, these allocas cannot overlap and we
// can infer there is no alias.
if (auto *A = dyn_cast<FrameIndexSDNode>(BasePtr0.getBase()))
if (auto *B = dyn_cast<FrameIndexSDNode>(BasePtr1.getBase())) {
MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
// If the base are the same frame index but the we couldn't find a
// constant offset, (indices are different) be conservative.
if (A != B && (!MFI.isFixedObjectIndex(A->getIndex()) ||
!MFI.isFixedObjectIndex(B->getIndex()))) {
IsAlias = false;
return true;
}
}
bool IsFI0 = isa<FrameIndexSDNode>(BasePtr0.getBase());
bool IsFI1 = isa<FrameIndexSDNode>(BasePtr1.getBase());
bool IsGV0 = isa<GlobalAddressSDNode>(BasePtr0.getBase());
bool IsGV1 = isa<GlobalAddressSDNode>(BasePtr1.getBase());
bool IsCV0 = isa<ConstantPoolSDNode>(BasePtr0.getBase());
bool IsCV1 = isa<ConstantPoolSDNode>(BasePtr1.getBase());
// If of mismatched base types or checkable indices we can check
// they do not alias.
if ((BasePtr0.getIndex() == BasePtr1.getIndex() || (IsFI0 != IsFI1) ||
(IsGV0 != IsGV1) || (IsCV0 != IsCV1)) &&
(IsFI0 || IsGV0 || IsCV0) && (IsFI1 || IsGV1 || IsCV1)) {
IsAlias = false;
return true;
}
return false; // Cannot determine whether the pointers alias.
}
bool BaseIndexOffset::contains(const SelectionDAG &DAG, int64_t BitSize,
const BaseIndexOffset &Other,
int64_t OtherBitSize, int64_t &BitOffset) const {
int64_t Offset;
if (!equalBaseIndex(Other, DAG, Offset))
return false;
if (Offset >= 0) {
// Other is after *this:
// [-------*this---------]
// [---Other--]
// ==Offset==>
BitOffset = 8 * Offset;
return BitOffset + OtherBitSize <= BitSize;
}
// Other starts strictly before *this, it cannot be fully contained.
// [-------*this---------]
// [--Other--]
return false;
}
/// Parses tree in Ptr for base, index, offset addresses.
static BaseIndexOffset matchLSNode(const LSBaseSDNode *N,
const SelectionDAG &DAG) {
SDValue Ptr = N->getBasePtr();
// (((B + I*M) + c)) + c ...
SDValue Base = DAG.getTargetLoweringInfo().unwrapAddress(Ptr);
SDValue Index = SDValue();
int64_t Offset = 0;
bool IsIndexSignExt = false;
// pre-inc/pre-dec ops are components of EA.
if (N->getAddressingMode() == ISD::PRE_INC) {
if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
Offset += C->getSExtValue();
else // If unknown, give up now.
return BaseIndexOffset(SDValue(), SDValue(), 0, false);
} else if (N->getAddressingMode() == ISD::PRE_DEC) {
if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
Offset -= C->getSExtValue();
else // If unknown, give up now.
return BaseIndexOffset(SDValue(), SDValue(), 0, false);
}
// Consume constant adds & ors with appropriate masking.
while (true) {
switch (Base->getOpcode()) {
case ISD::OR:
// Only consider ORs which act as adds.
if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1)))
if (DAG.MaskedValueIsZero(Base->getOperand(0), C->getAPIntValue())) {
Offset += C->getSExtValue();
Base = DAG.getTargetLoweringInfo().unwrapAddress(Base->getOperand(0));
continue;
}
break;
case ISD::ADD:
if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1))) {
Offset += C->getSExtValue();
Base = DAG.getTargetLoweringInfo().unwrapAddress(Base->getOperand(0));
continue;
}
break;
case ISD::LOAD:
case ISD::STORE: {
auto *LSBase = cast<LSBaseSDNode>(Base.getNode());
unsigned int IndexResNo = (Base->getOpcode() == ISD::LOAD) ? 1 : 0;
if (LSBase->isIndexed() && Base.getResNo() == IndexResNo)
if (auto *C = dyn_cast<ConstantSDNode>(LSBase->getOffset())) {
auto Off = C->getSExtValue();
if (LSBase->getAddressingMode() == ISD::PRE_DEC ||
LSBase->getAddressingMode() == ISD::POST_DEC)
Offset -= Off;
else
Offset += Off;
Base = DAG.getTargetLoweringInfo().unwrapAddress(LSBase->getBasePtr());
continue;
}
break;
}
}
// If we get here break out of the loop.
break;
}
if (Base->getOpcode() == ISD::ADD) {
// TODO: The following code appears to be needless as it just
// bails on some Ptrs early, reducing the cases where we
// find equivalence. We should be able to remove this.
// Inside a loop the current BASE pointer is calculated using an ADD and a
// MUL instruction. In this case Base is the actual BASE pointer.
// (i64 add (i64 %array_ptr)
// (i64 mul (i64 %induction_var)
// (i64 %element_size)))
if (Base->getOperand(1)->getOpcode() == ISD::MUL)
return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
// Look at Base + Index + Offset cases.
Index = Base->getOperand(1);
SDValue PotentialBase = Base->getOperand(0);
// Skip signextends.
if (Index->getOpcode() == ISD::SIGN_EXTEND) {
Index = Index->getOperand(0);
IsIndexSignExt = true;
}
// Check if Index Offset pattern
if (Index->getOpcode() != ISD::ADD ||
!isa<ConstantSDNode>(Index->getOperand(1)))
return BaseIndexOffset(PotentialBase, Index, Offset, IsIndexSignExt);
Offset += cast<ConstantSDNode>(Index->getOperand(1))->getSExtValue();
Index = Index->getOperand(0);
if (Index->getOpcode() == ISD::SIGN_EXTEND) {
Index = Index->getOperand(0);
IsIndexSignExt = true;
} else
IsIndexSignExt = false;
Base = PotentialBase;
}
return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
}
BaseIndexOffset BaseIndexOffset::match(const SDNode *N,
const SelectionDAG &DAG) {
if (const auto *LS0 = dyn_cast<LSBaseSDNode>(N))
return matchLSNode(LS0, DAG);
if (const auto *LN = dyn_cast<LifetimeSDNode>(N)) {
if (LN->hasOffset())
return BaseIndexOffset(LN->getOperand(1), SDValue(), LN->getOffset(),
false);
return BaseIndexOffset(LN->getOperand(1), SDValue(), false);
}
return BaseIndexOffset();
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void BaseIndexOffset::dump() const {
print(dbgs());
}
void BaseIndexOffset::print(raw_ostream& OS) const {
OS << "BaseIndexOffset base=[";
Base->print(OS);
OS << "] index=[";
if (Index)
Index->print(OS);
OS << "] offset=" << Offset;
}
#endif
|