1 | //==- llvm/CodeGen/SelectionDAGAddressAnalysis.cpp - DAG Address Analysis --==// |
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 | #include "llvm/CodeGen/SelectionDAGAddressAnalysis.h" |
10 | #include "llvm/Analysis/MemoryLocation.h" |
11 | #include "llvm/CodeGen/ISDOpcodes.h" |
12 | #include "llvm/CodeGen/MachineFrameInfo.h" |
13 | #include "llvm/CodeGen/MachineFunction.h" |
14 | #include "llvm/CodeGen/SelectionDAG.h" |
15 | #include "llvm/CodeGen/SelectionDAGNodes.h" |
16 | #include "llvm/CodeGen/TargetLowering.h" |
17 | #include "llvm/IR/GlobalAlias.h" |
18 | #include "llvm/Support/Casting.h" |
19 | #include "llvm/Support/Debug.h" |
20 | #include <cstdint> |
21 | |
22 | using namespace llvm; |
23 | |
24 | bool BaseIndexOffset::equalBaseIndex(const BaseIndexOffset &Other, |
25 | const SelectionDAG &DAG, |
26 | int64_t &Off) const { |
27 | // Conservatively fail if we a match failed.. |
28 | if (!Base.getNode() || !Other.Base.getNode()) |
29 | return false; |
30 | if (!hasValidOffset() || !Other.hasValidOffset()) |
31 | return false; |
32 | // Initial Offset difference. |
33 | Off = *Other.Offset - *Offset; |
34 | |
35 | if ((Other.Index == Index) && (Other.IsIndexSignExt == IsIndexSignExt)) { |
36 | // Trivial match. |
37 | if (Other.Base == Base) |
38 | return true; |
39 | |
40 | // Match GlobalAddresses |
41 | if (auto *A = dyn_cast<GlobalAddressSDNode>(Val: Base)) { |
42 | if (auto *B = dyn_cast<GlobalAddressSDNode>(Val: Other.Base)) |
43 | if (A->getGlobal() == B->getGlobal()) { |
44 | Off += B->getOffset() - A->getOffset(); |
45 | return true; |
46 | } |
47 | |
48 | return false; |
49 | } |
50 | |
51 | // Match Constants |
52 | if (auto *A = dyn_cast<ConstantPoolSDNode>(Val: Base)) { |
53 | if (auto *B = dyn_cast<ConstantPoolSDNode>(Val: Other.Base)) { |
54 | bool IsMatch = |
55 | A->isMachineConstantPoolEntry() == B->isMachineConstantPoolEntry(); |
56 | if (IsMatch) { |
57 | if (A->isMachineConstantPoolEntry()) |
58 | IsMatch = A->getMachineCPVal() == B->getMachineCPVal(); |
59 | else |
60 | IsMatch = A->getConstVal() == B->getConstVal(); |
61 | } |
62 | if (IsMatch) { |
63 | Off += B->getOffset() - A->getOffset(); |
64 | return true; |
65 | } |
66 | } |
67 | |
68 | return false; |
69 | } |
70 | |
71 | // Match FrameIndexes. |
72 | if (auto *A = dyn_cast<FrameIndexSDNode>(Val: Base)) |
73 | if (auto *B = dyn_cast<FrameIndexSDNode>(Val: Other.Base)) { |
74 | // Equal FrameIndexes - offsets are directly comparable. |
75 | if (A->getIndex() == B->getIndex()) |
76 | return true; |
77 | // Non-equal FrameIndexes - If both frame indices are fixed |
78 | // we know their relative offsets and can compare them. Otherwise |
79 | // we must be conservative. |
80 | const MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo(); |
81 | if (MFI.isFixedObjectIndex(ObjectIdx: A->getIndex()) && |
82 | MFI.isFixedObjectIndex(ObjectIdx: B->getIndex())) { |
83 | Off += MFI.getObjectOffset(ObjectIdx: B->getIndex()) - |
84 | MFI.getObjectOffset(ObjectIdx: A->getIndex()); |
85 | return true; |
86 | } |
87 | } |
88 | } |
89 | |
90 | return false; |
91 | } |
92 | |
93 | bool BaseIndexOffset::computeAliasing(const SDNode *Op0, |
94 | const std::optional<int64_t> NumBytes0, |
95 | const SDNode *Op1, |
96 | const std::optional<int64_t> NumBytes1, |
97 | const SelectionDAG &DAG, bool &IsAlias) { |
98 | |
99 | BaseIndexOffset BasePtr0 = match(N: Op0, DAG); |
100 | if (!BasePtr0.getBase().getNode()) |
101 | return false; |
102 | |
103 | BaseIndexOffset BasePtr1 = match(N: Op1, DAG); |
104 | if (!BasePtr1.getBase().getNode()) |
105 | return false; |
106 | |
107 | int64_t PtrDiff; |
108 | if (NumBytes0 && NumBytes1 && |
109 | BasePtr0.equalBaseIndex(Other: BasePtr1, DAG, Off&: PtrDiff)) { |
110 | // If the size of memory access is unknown, do not use it to analysis. |
111 | // One example of unknown size memory access is to load/store scalable |
112 | // vector objects on the stack. |
113 | // BasePtr1 is PtrDiff away from BasePtr0. They alias if none of the |
114 | // following situations arise: |
115 | if (PtrDiff >= 0 && |
116 | *NumBytes0 != static_cast<int64_t>(MemoryLocation::UnknownSize)) { |
117 | // [----BasePtr0----] |
118 | // [---BasePtr1--] |
119 | // ========PtrDiff========> |
120 | IsAlias = !(*NumBytes0 <= PtrDiff); |
121 | return true; |
122 | } |
123 | if (PtrDiff < 0 && |
124 | *NumBytes1 != static_cast<int64_t>(MemoryLocation::UnknownSize)) { |
125 | // [----BasePtr0----] |
126 | // [---BasePtr1--] |
127 | // =====(-PtrDiff)====> |
128 | IsAlias = !((PtrDiff + *NumBytes1) <= 0); |
129 | return true; |
130 | } |
131 | return false; |
132 | } |
133 | // If both BasePtr0 and BasePtr1 are FrameIndexes, we will not be |
134 | // able to calculate their relative offset if at least one arises |
135 | // from an alloca. However, these allocas cannot overlap and we |
136 | // can infer there is no alias. |
137 | if (auto *A = dyn_cast<FrameIndexSDNode>(Val: BasePtr0.getBase())) |
138 | if (auto *B = dyn_cast<FrameIndexSDNode>(Val: BasePtr1.getBase())) { |
139 | MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo(); |
140 | // If the base are the same frame index but the we couldn't find a |
141 | // constant offset, (indices are different) be conservative. |
142 | if (A->getIndex() != B->getIndex() && (!MFI.isFixedObjectIndex(ObjectIdx: A->getIndex()) || |
143 | !MFI.isFixedObjectIndex(ObjectIdx: B->getIndex()))) { |
144 | IsAlias = false; |
145 | return true; |
146 | } |
147 | } |
148 | |
149 | bool IsFI0 = isa<FrameIndexSDNode>(Val: BasePtr0.getBase()); |
150 | bool IsFI1 = isa<FrameIndexSDNode>(Val: BasePtr1.getBase()); |
151 | bool IsGV0 = isa<GlobalAddressSDNode>(Val: BasePtr0.getBase()); |
152 | bool IsGV1 = isa<GlobalAddressSDNode>(Val: BasePtr1.getBase()); |
153 | bool IsCV0 = isa<ConstantPoolSDNode>(Val: BasePtr0.getBase()); |
154 | bool IsCV1 = isa<ConstantPoolSDNode>(Val: BasePtr1.getBase()); |
155 | |
156 | if ((IsFI0 || IsGV0 || IsCV0) && (IsFI1 || IsGV1 || IsCV1)) { |
157 | // We can derive NoAlias In case of mismatched base types. |
158 | if (IsFI0 != IsFI1 || IsGV0 != IsGV1 || IsCV0 != IsCV1) { |
159 | IsAlias = false; |
160 | return true; |
161 | } |
162 | if (IsGV0 && IsGV1) { |
163 | auto *GV0 = cast<GlobalAddressSDNode>(Val: BasePtr0.getBase())->getGlobal(); |
164 | auto *GV1 = cast<GlobalAddressSDNode>(Val: BasePtr1.getBase())->getGlobal(); |
165 | // It doesn't make sense to access one global value using another globals |
166 | // values address, so we can assume that there is no aliasing in case of |
167 | // two different globals (unless we have symbols that may indirectly point |
168 | // to each other). |
169 | // FIXME: This is perhaps a bit too defensive. We could try to follow the |
170 | // chain with aliasee information for GlobalAlias variables to find out if |
171 | // we indirect symbols may alias or not. |
172 | if (GV0 != GV1 && !isa<GlobalAlias>(Val: GV0) && !isa<GlobalAlias>(Val: GV1)) { |
173 | IsAlias = false; |
174 | return true; |
175 | } |
176 | } |
177 | } |
178 | return false; // Cannot determine whether the pointers alias. |
179 | } |
180 | |
181 | bool BaseIndexOffset::contains(const SelectionDAG &DAG, int64_t BitSize, |
182 | const BaseIndexOffset &Other, |
183 | int64_t OtherBitSize, int64_t &BitOffset) const { |
184 | int64_t Offset; |
185 | if (!equalBaseIndex(Other, DAG, Off&: Offset)) |
186 | return false; |
187 | if (Offset >= 0) { |
188 | // Other is after *this: |
189 | // [-------*this---------] |
190 | // [---Other--] |
191 | // ==Offset==> |
192 | BitOffset = 8 * Offset; |
193 | return BitOffset + OtherBitSize <= BitSize; |
194 | } |
195 | // Other starts strictly before *this, it cannot be fully contained. |
196 | // [-------*this---------] |
197 | // [--Other--] |
198 | return false; |
199 | } |
200 | |
201 | /// Parses tree in Ptr for base, index, offset addresses. |
202 | static BaseIndexOffset matchLSNode(const LSBaseSDNode *N, |
203 | const SelectionDAG &DAG) { |
204 | SDValue Ptr = N->getBasePtr(); |
205 | |
206 | // (((B + I*M) + c)) + c ... |
207 | SDValue Base = DAG.getTargetLoweringInfo().unwrapAddress(N: Ptr); |
208 | SDValue Index = SDValue(); |
209 | int64_t Offset = 0; |
210 | bool IsIndexSignExt = false; |
211 | |
212 | // pre-inc/pre-dec ops are components of EA. |
213 | if (N->getAddressingMode() == ISD::PRE_INC) { |
214 | if (auto *C = dyn_cast<ConstantSDNode>(Val: N->getOffset())) |
215 | Offset += C->getSExtValue(); |
216 | else // If unknown, give up now. |
217 | return BaseIndexOffset(SDValue(), SDValue(), 0, false); |
218 | } else if (N->getAddressingMode() == ISD::PRE_DEC) { |
219 | if (auto *C = dyn_cast<ConstantSDNode>(Val: N->getOffset())) |
220 | Offset -= C->getSExtValue(); |
221 | else // If unknown, give up now. |
222 | return BaseIndexOffset(SDValue(), SDValue(), 0, false); |
223 | } |
224 | |
225 | // Consume constant adds & ors with appropriate masking. |
226 | while (true) { |
227 | switch (Base->getOpcode()) { |
228 | case ISD::OR: |
229 | // Only consider ORs which act as adds. |
230 | if (auto *C = dyn_cast<ConstantSDNode>(Val: Base->getOperand(Num: 1))) |
231 | if (DAG.MaskedValueIsZero(Op: Base->getOperand(Num: 0), Mask: C->getAPIntValue())) { |
232 | Offset += C->getSExtValue(); |
233 | Base = DAG.getTargetLoweringInfo().unwrapAddress(N: Base->getOperand(Num: 0)); |
234 | continue; |
235 | } |
236 | break; |
237 | case ISD::ADD: |
238 | if (auto *C = dyn_cast<ConstantSDNode>(Val: Base->getOperand(Num: 1))) { |
239 | Offset += C->getSExtValue(); |
240 | Base = DAG.getTargetLoweringInfo().unwrapAddress(N: Base->getOperand(Num: 0)); |
241 | continue; |
242 | } |
243 | break; |
244 | case ISD::LOAD: |
245 | case ISD::STORE: { |
246 | auto *LSBase = cast<LSBaseSDNode>(Val: Base.getNode()); |
247 | unsigned int IndexResNo = (Base->getOpcode() == ISD::LOAD) ? 1 : 0; |
248 | if (LSBase->isIndexed() && Base.getResNo() == IndexResNo) |
249 | if (auto *C = dyn_cast<ConstantSDNode>(Val: LSBase->getOffset())) { |
250 | auto Off = C->getSExtValue(); |
251 | if (LSBase->getAddressingMode() == ISD::PRE_DEC || |
252 | LSBase->getAddressingMode() == ISD::POST_DEC) |
253 | Offset -= Off; |
254 | else |
255 | Offset += Off; |
256 | Base = DAG.getTargetLoweringInfo().unwrapAddress(N: LSBase->getBasePtr()); |
257 | continue; |
258 | } |
259 | break; |
260 | } |
261 | } |
262 | // If we get here break out of the loop. |
263 | break; |
264 | } |
265 | |
266 | if (Base->getOpcode() == ISD::ADD) { |
267 | // TODO: The following code appears to be needless as it just |
268 | // bails on some Ptrs early, reducing the cases where we |
269 | // find equivalence. We should be able to remove this. |
270 | // Inside a loop the current BASE pointer is calculated using an ADD and a |
271 | // MUL instruction. In this case Base is the actual BASE pointer. |
272 | // (i64 add (i64 %array_ptr) |
273 | // (i64 mul (i64 %induction_var) |
274 | // (i64 %element_size))) |
275 | if (Base->getOperand(Num: 1)->getOpcode() == ISD::MUL) |
276 | return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt); |
277 | |
278 | // Look at Base + Index + Offset cases. |
279 | Index = Base->getOperand(Num: 1); |
280 | SDValue PotentialBase = Base->getOperand(Num: 0); |
281 | |
282 | // Skip signextends. |
283 | if (Index->getOpcode() == ISD::SIGN_EXTEND) { |
284 | Index = Index->getOperand(Num: 0); |
285 | IsIndexSignExt = true; |
286 | } |
287 | |
288 | // Check if Index Offset pattern |
289 | if (Index->getOpcode() != ISD::ADD || |
290 | !isa<ConstantSDNode>(Val: Index->getOperand(Num: 1))) |
291 | return BaseIndexOffset(PotentialBase, Index, Offset, IsIndexSignExt); |
292 | |
293 | Offset += cast<ConstantSDNode>(Val: Index->getOperand(Num: 1))->getSExtValue(); |
294 | Index = Index->getOperand(Num: 0); |
295 | if (Index->getOpcode() == ISD::SIGN_EXTEND) { |
296 | Index = Index->getOperand(Num: 0); |
297 | IsIndexSignExt = true; |
298 | } else |
299 | IsIndexSignExt = false; |
300 | Base = PotentialBase; |
301 | } |
302 | return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt); |
303 | } |
304 | |
305 | BaseIndexOffset BaseIndexOffset::match(const SDNode *N, |
306 | const SelectionDAG &DAG) { |
307 | if (const auto *LS0 = dyn_cast<LSBaseSDNode>(Val: N)) |
308 | return matchLSNode(N: LS0, DAG); |
309 | if (const auto *LN = dyn_cast<LifetimeSDNode>(Val: N)) { |
310 | if (LN->hasOffset()) |
311 | return BaseIndexOffset(LN->getOperand(Num: 1), SDValue(), LN->getOffset(), |
312 | false); |
313 | return BaseIndexOffset(LN->getOperand(Num: 1), SDValue(), false); |
314 | } |
315 | return BaseIndexOffset(); |
316 | } |
317 | |
318 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
319 | |
320 | LLVM_DUMP_METHOD void BaseIndexOffset::dump() const { |
321 | print(OS&: dbgs()); |
322 | } |
323 | |
324 | void BaseIndexOffset::print(raw_ostream& OS) const { |
325 | OS << "BaseIndexOffset base=[" ; |
326 | Base->print(OS); |
327 | OS << "] index=[" ; |
328 | if (Index) |
329 | Index->print(OS); |
330 | OS << "] offset=" << Offset; |
331 | } |
332 | |
333 | #endif |
334 | |