1 //==- llvm/CodeGen/SelectionDAGAddressAnalysis.cpp - DAG Address Analysis --==//
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
7 //===----------------------------------------------------------------------===//
9 #include "llvm/CodeGen/SelectionDAGAddressAnalysis.h"
10 #include "llvm/CodeGen/ISDOpcodes.h"
11 #include "llvm/CodeGen/MachineFrameInfo.h"
12 #include "llvm/CodeGen/MachineFunction.h"
13 #include "llvm/CodeGen/SelectionDAG.h"
14 #include "llvm/CodeGen/SelectionDAGNodes.h"
15 #include "llvm/CodeGen/TargetLowering.h"
16 #include "llvm/Support/Casting.h"
21 bool BaseIndexOffset::equalBaseIndex(const BaseIndexOffset &Other,
22 const SelectionDAG &DAG,
24 // Conservatively fail if we a match failed..
25 if (!Base.getNode() || !Other.Base.getNode())
27 if (!hasValidOffset() || !Other.hasValidOffset())
29 // Initial Offset difference.
30 Off = *Other.Offset - *Offset;
32 if ((Other.Index == Index) && (Other.IsIndexSignExt == IsIndexSignExt)) {
34 if (Other.Base == Base)
37 // Match GlobalAddresses
38 if (auto *A = dyn_cast<GlobalAddressSDNode>(Base))
39 if (auto *B = dyn_cast<GlobalAddressSDNode>(Other.Base))
40 if (A->getGlobal() == B->getGlobal()) {
41 Off += B->getOffset() - A->getOffset();
46 if (auto *A = dyn_cast<ConstantPoolSDNode>(Base))
47 if (auto *B = dyn_cast<ConstantPoolSDNode>(Other.Base)) {
49 A->isMachineConstantPoolEntry() == B->isMachineConstantPoolEntry();
51 if (A->isMachineConstantPoolEntry())
52 IsMatch = A->getMachineCPVal() == B->getMachineCPVal();
54 IsMatch = A->getConstVal() == B->getConstVal();
57 Off += B->getOffset() - A->getOffset();
62 const MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
64 // Match FrameIndexes.
65 if (auto *A = dyn_cast<FrameIndexSDNode>(Base))
66 if (auto *B = dyn_cast<FrameIndexSDNode>(Other.Base)) {
67 // Equal FrameIndexes - offsets are directly comparable.
68 if (A->getIndex() == B->getIndex())
70 // Non-equal FrameIndexes - If both frame indices are fixed
71 // we know their relative offsets and can compare them. Otherwise
72 // we must be conservative.
73 if (MFI.isFixedObjectIndex(A->getIndex()) &&
74 MFI.isFixedObjectIndex(B->getIndex())) {
75 Off += MFI.getObjectOffset(B->getIndex()) -
76 MFI.getObjectOffset(A->getIndex());
84 bool BaseIndexOffset::computeAliasing(const SDNode *Op0,
85 const Optional<int64_t> NumBytes0,
87 const Optional<int64_t> NumBytes1,
88 const SelectionDAG &DAG, bool &IsAlias) {
90 BaseIndexOffset BasePtr0 = match(Op0, DAG);
91 BaseIndexOffset BasePtr1 = match(Op1, DAG);
93 if (!(BasePtr0.getBase().getNode() && BasePtr1.getBase().getNode()))
96 if (NumBytes0.hasValue() && NumBytes1.hasValue() &&
97 BasePtr0.equalBaseIndex(BasePtr1, DAG, PtrDiff)) {
98 // BasePtr1 is PtrDiff away from BasePtr0. They alias if none of the
99 // following situations arise:
101 // [----BasePtr0----]
103 // ========PtrDiff========>
104 (*NumBytes0 <= PtrDiff) ||
105 // [----BasePtr0----]
107 // =====(-PtrDiff)====>
108 (PtrDiff + *NumBytes1 <= 0)); // i.e. *NumBytes1 < -PtrDiff.
111 // If both BasePtr0 and BasePtr1 are FrameIndexes, we will not be
112 // able to calculate their relative offset if at least one arises
113 // from an alloca. However, these allocas cannot overlap and we
114 // can infer there is no alias.
115 if (auto *A = dyn_cast<FrameIndexSDNode>(BasePtr0.getBase()))
116 if (auto *B = dyn_cast<FrameIndexSDNode>(BasePtr1.getBase())) {
117 MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
118 // If the base are the same frame index but the we couldn't find a
119 // constant offset, (indices are different) be conservative.
120 if (A != B && (!MFI.isFixedObjectIndex(A->getIndex()) ||
121 !MFI.isFixedObjectIndex(B->getIndex()))) {
127 bool IsFI0 = isa<FrameIndexSDNode>(BasePtr0.getBase());
128 bool IsFI1 = isa<FrameIndexSDNode>(BasePtr1.getBase());
129 bool IsGV0 = isa<GlobalAddressSDNode>(BasePtr0.getBase());
130 bool IsGV1 = isa<GlobalAddressSDNode>(BasePtr1.getBase());
131 bool IsCV0 = isa<ConstantPoolSDNode>(BasePtr0.getBase());
132 bool IsCV1 = isa<ConstantPoolSDNode>(BasePtr1.getBase());
134 // If of mismatched base types or checkable indices we can check
135 // they do not alias.
136 if ((BasePtr0.getIndex() == BasePtr1.getIndex() || (IsFI0 != IsFI1) ||
137 (IsGV0 != IsGV1) || (IsCV0 != IsCV1)) &&
138 (IsFI0 || IsGV0 || IsCV0) && (IsFI1 || IsGV1 || IsCV1)) {
142 return false; // Cannot determine whether the pointers alias.
145 bool BaseIndexOffset::contains(const SelectionDAG &DAG, int64_t BitSize,
146 const BaseIndexOffset &Other,
147 int64_t OtherBitSize, int64_t &BitOffset) const {
149 if (!equalBaseIndex(Other, DAG, Offset))
152 // Other is after *this:
153 // [-------*this---------]
156 BitOffset = 8 * Offset;
157 return BitOffset + OtherBitSize <= BitSize;
159 // Other starts strictly before *this, it cannot be fully contained.
160 // [-------*this---------]
165 /// Parses tree in Ptr for base, index, offset addresses.
166 static BaseIndexOffset matchLSNode(const LSBaseSDNode *N,
167 const SelectionDAG &DAG) {
168 SDValue Ptr = N->getBasePtr();
170 // (((B + I*M) + c)) + c ...
171 SDValue Base = DAG.getTargetLoweringInfo().unwrapAddress(Ptr);
172 SDValue Index = SDValue();
174 bool IsIndexSignExt = false;
176 // pre-inc/pre-dec ops are components of EA.
177 if (N->getAddressingMode() == ISD::PRE_INC) {
178 if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
179 Offset += C->getSExtValue();
180 else // If unknown, give up now.
181 return BaseIndexOffset(SDValue(), SDValue(), 0, false);
182 } else if (N->getAddressingMode() == ISD::PRE_DEC) {
183 if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
184 Offset -= C->getSExtValue();
185 else // If unknown, give up now.
186 return BaseIndexOffset(SDValue(), SDValue(), 0, false);
189 // Consume constant adds & ors with appropriate masking.
191 switch (Base->getOpcode()) {
193 // Only consider ORs which act as adds.
194 if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1)))
195 if (DAG.MaskedValueIsZero(Base->getOperand(0), C->getAPIntValue())) {
196 Offset += C->getSExtValue();
197 Base = DAG.getTargetLoweringInfo().unwrapAddress(Base->getOperand(0));
202 if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1))) {
203 Offset += C->getSExtValue();
204 Base = DAG.getTargetLoweringInfo().unwrapAddress(Base->getOperand(0));
210 auto *LSBase = cast<LSBaseSDNode>(Base.getNode());
211 unsigned int IndexResNo = (Base->getOpcode() == ISD::LOAD) ? 1 : 0;
212 if (LSBase->isIndexed() && Base.getResNo() == IndexResNo)
213 if (auto *C = dyn_cast<ConstantSDNode>(LSBase->getOffset())) {
214 auto Off = C->getSExtValue();
215 if (LSBase->getAddressingMode() == ISD::PRE_DEC ||
216 LSBase->getAddressingMode() == ISD::POST_DEC)
220 Base = DAG.getTargetLoweringInfo().unwrapAddress(LSBase->getBasePtr());
226 // If we get here break out of the loop.
230 if (Base->getOpcode() == ISD::ADD) {
231 // TODO: The following code appears to be needless as it just
232 // bails on some Ptrs early, reducing the cases where we
233 // find equivalence. We should be able to remove this.
234 // Inside a loop the current BASE pointer is calculated using an ADD and a
235 // MUL instruction. In this case Base is the actual BASE pointer.
236 // (i64 add (i64 %array_ptr)
237 // (i64 mul (i64 %induction_var)
238 // (i64 %element_size)))
239 if (Base->getOperand(1)->getOpcode() == ISD::MUL)
240 return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
242 // Look at Base + Index + Offset cases.
243 Index = Base->getOperand(1);
244 SDValue PotentialBase = Base->getOperand(0);
247 if (Index->getOpcode() == ISD::SIGN_EXTEND) {
248 Index = Index->getOperand(0);
249 IsIndexSignExt = true;
252 // Check if Index Offset pattern
253 if (Index->getOpcode() != ISD::ADD ||
254 !isa<ConstantSDNode>(Index->getOperand(1)))
255 return BaseIndexOffset(PotentialBase, Index, Offset, IsIndexSignExt);
257 Offset += cast<ConstantSDNode>(Index->getOperand(1))->getSExtValue();
258 Index = Index->getOperand(0);
259 if (Index->getOpcode() == ISD::SIGN_EXTEND) {
260 Index = Index->getOperand(0);
261 IsIndexSignExt = true;
263 IsIndexSignExt = false;
264 Base = PotentialBase;
266 return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
269 BaseIndexOffset BaseIndexOffset::match(const SDNode *N,
270 const SelectionDAG &DAG) {
271 if (const auto *LS0 = dyn_cast<LSBaseSDNode>(N))
272 return matchLSNode(LS0, DAG);
273 if (const auto *LN = dyn_cast<LifetimeSDNode>(N)) {
275 return BaseIndexOffset(LN->getOperand(1), SDValue(), LN->getOffset(),
277 return BaseIndexOffset(LN->getOperand(1), SDValue(), false);
279 return BaseIndexOffset();
282 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
284 LLVM_DUMP_METHOD void BaseIndexOffset::dump() const {
288 void BaseIndexOffset::print(raw_ostream& OS) const {
289 OS << "BaseIndexOffset base=[";
294 OS << "] offset=" << Offset;