xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583) 
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 
equalBaseIndex(const BaseIndexOffset & Other,const SelectionDAG & DAG,int64_t & Off) const24 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>(Base)) {
42       if (auto *B = dyn_cast<GlobalAddressSDNode>(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>(Base)) {
53       if (auto *B = dyn_cast<ConstantPoolSDNode>(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>(Base))
73       if (auto *B = dyn_cast<FrameIndexSDNode>(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(A->getIndex()) &&
82             MFI.isFixedObjectIndex(B->getIndex())) {
83           Off += MFI.getObjectOffset(B->getIndex()) -
84                  MFI.getObjectOffset(A->getIndex());
85           return true;
86         }
87       }
88   }
89 
90   return false;
91 }
92 
computeAliasing(const SDNode * Op0,const LocationSize NumBytes0,const SDNode * Op1,const LocationSize NumBytes1,const SelectionDAG & DAG,bool & IsAlias)93 bool BaseIndexOffset::computeAliasing(const SDNode *Op0,
94                                       const LocationSize NumBytes0,
95                                       const SDNode *Op1,
96                                       const LocationSize NumBytes1,
97                                       const SelectionDAG &DAG, bool &IsAlias) {
98   BaseIndexOffset BasePtr0 = match(Op0, DAG);
99   if (!BasePtr0.getBase().getNode())
100     return false;
101 
102   BaseIndexOffset BasePtr1 = match(Op1, DAG);
103   if (!BasePtr1.getBase().getNode())
104     return false;
105 
106   int64_t PtrDiff;
107   if (BasePtr0.equalBaseIndex(BasePtr1, DAG, PtrDiff)) {
108     // If the size of memory access is unknown, do not use it to analysis.
109     // BasePtr1 is PtrDiff away from BasePtr0. They alias if none of the
110     // following situations arise:
111     if (PtrDiff >= 0 && NumBytes0.hasValue() && !NumBytes0.isScalable()) {
112       // [----BasePtr0----]
113       //                         [---BasePtr1--]
114       // ========PtrDiff========>
115       IsAlias = !(static_cast<int64_t>(NumBytes0.getValue().getFixedValue()) <=
116                   PtrDiff);
117       return true;
118     }
119     if (PtrDiff < 0 && NumBytes1.hasValue() && !NumBytes1.isScalable()) {
120       //                     [----BasePtr0----]
121       // [---BasePtr1--]
122       // =====(-PtrDiff)====>
123       IsAlias = !((PtrDiff + static_cast<int64_t>(
124                                  NumBytes1.getValue().getFixedValue())) <= 0);
125       return true;
126     }
127     return false;
128   }
129   // If both BasePtr0 and BasePtr1 are FrameIndexes, we will not be
130   // able to calculate their relative offset if at least one arises
131   // from an alloca. However, these allocas cannot overlap and we
132   // can infer there is no alias.
133   if (auto *A = dyn_cast<FrameIndexSDNode>(BasePtr0.getBase()))
134     if (auto *B = dyn_cast<FrameIndexSDNode>(BasePtr1.getBase())) {
135       MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
136       // If the base are the same frame index but the we couldn't find a
137       // constant offset, (indices are different) be conservative.
138       if (A->getIndex() != B->getIndex() && (!MFI.isFixedObjectIndex(A->getIndex()) ||
139                      !MFI.isFixedObjectIndex(B->getIndex()))) {
140         IsAlias = false;
141         return true;
142       }
143     }
144 
145   bool IsFI0 = isa<FrameIndexSDNode>(BasePtr0.getBase());
146   bool IsFI1 = isa<FrameIndexSDNode>(BasePtr1.getBase());
147   bool IsGV0 = isa<GlobalAddressSDNode>(BasePtr0.getBase());
148   bool IsGV1 = isa<GlobalAddressSDNode>(BasePtr1.getBase());
149   bool IsCV0 = isa<ConstantPoolSDNode>(BasePtr0.getBase());
150   bool IsCV1 = isa<ConstantPoolSDNode>(BasePtr1.getBase());
151 
152   if ((IsFI0 || IsGV0 || IsCV0) && (IsFI1 || IsGV1 || IsCV1)) {
153     // We can derive NoAlias In case of mismatched base types.
154     if (IsFI0 != IsFI1 || IsGV0 != IsGV1 || IsCV0 != IsCV1) {
155       IsAlias = false;
156       return true;
157     }
158     if (IsGV0 && IsGV1) {
159       auto *GV0 = cast<GlobalAddressSDNode>(BasePtr0.getBase())->getGlobal();
160       auto *GV1 = cast<GlobalAddressSDNode>(BasePtr1.getBase())->getGlobal();
161       // It doesn't make sense to access one global value using another globals
162       // values address, so we can assume that there is no aliasing in case of
163       // two different globals (unless we have symbols that may indirectly point
164       // to each other).
165       // FIXME: This is perhaps a bit too defensive. We could try to follow the
166       // chain with aliasee information for GlobalAlias variables to find out if
167       // we indirect symbols may alias or not.
168       if (GV0 != GV1 && !isa<GlobalAlias>(GV0) && !isa<GlobalAlias>(GV1)) {
169         IsAlias = false;
170         return true;
171       }
172     }
173   }
174   return false; // Cannot determine whether the pointers alias.
175 }
176 
contains(const SelectionDAG & DAG,int64_t BitSize,const BaseIndexOffset & Other,int64_t OtherBitSize,int64_t & BitOffset) const177 bool BaseIndexOffset::contains(const SelectionDAG &DAG, int64_t BitSize,
178                                const BaseIndexOffset &Other,
179                                int64_t OtherBitSize, int64_t &BitOffset) const {
180   int64_t Offset;
181   if (!equalBaseIndex(Other, DAG, Offset))
182     return false;
183   if (Offset >= 0) {
184     // Other is after *this:
185     // [-------*this---------]
186     //            [---Other--]
187     // ==Offset==>
188     BitOffset = 8 * Offset;
189     return BitOffset + OtherBitSize <= BitSize;
190   }
191   // Other starts strictly before *this, it cannot be fully contained.
192   //    [-------*this---------]
193   // [--Other--]
194   return false;
195 }
196 
197 /// Parses tree in Ptr for base, index, offset addresses.
matchLSNode(const LSBaseSDNode * N,const SelectionDAG & DAG)198 static BaseIndexOffset matchLSNode(const LSBaseSDNode *N,
199                                    const SelectionDAG &DAG) {
200   SDValue Ptr = N->getBasePtr();
201 
202   // (((B + I*M) + c)) + c ...
203   SDValue Base = DAG.getTargetLoweringInfo().unwrapAddress(Ptr);
204   SDValue Index = SDValue();
205   int64_t Offset = 0;
206   bool IsIndexSignExt = false;
207 
208   // pre-inc/pre-dec ops are components of EA.
209   if (N->getAddressingMode() == ISD::PRE_INC) {
210     if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
211       Offset += C->getSExtValue();
212     else // If unknown, give up now.
213       return BaseIndexOffset(SDValue(), SDValue(), 0, false);
214   } else if (N->getAddressingMode() == ISD::PRE_DEC) {
215     if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
216       Offset -= C->getSExtValue();
217     else // If unknown, give up now.
218       return BaseIndexOffset(SDValue(), SDValue(), 0, false);
219   }
220 
221   // Consume constant adds & ors with appropriate masking.
222   while (true) {
223     switch (Base->getOpcode()) {
224     case ISD::OR:
225       // Only consider ORs which act as adds.
226       if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1)))
227         if (DAG.MaskedValueIsZero(Base->getOperand(0), C->getAPIntValue())) {
228           Offset += C->getSExtValue();
229           Base = DAG.getTargetLoweringInfo().unwrapAddress(Base->getOperand(0));
230           continue;
231         }
232       break;
233     case ISD::ADD:
234       if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1))) {
235         Offset += C->getSExtValue();
236         Base = DAG.getTargetLoweringInfo().unwrapAddress(Base->getOperand(0));
237         continue;
238       }
239       break;
240     case ISD::LOAD:
241     case ISD::STORE: {
242       auto *LSBase = cast<LSBaseSDNode>(Base.getNode());
243       unsigned int IndexResNo = (Base->getOpcode() == ISD::LOAD) ? 1 : 0;
244       if (LSBase->isIndexed() && Base.getResNo() == IndexResNo)
245         if (auto *C = dyn_cast<ConstantSDNode>(LSBase->getOffset())) {
246           auto Off = C->getSExtValue();
247           if (LSBase->getAddressingMode() == ISD::PRE_DEC ||
248               LSBase->getAddressingMode() == ISD::POST_DEC)
249             Offset -= Off;
250           else
251             Offset += Off;
252           Base = DAG.getTargetLoweringInfo().unwrapAddress(LSBase->getBasePtr());
253           continue;
254         }
255       break;
256     }
257     }
258     // If we get here break out of the loop.
259     break;
260   }
261 
262   if (Base->getOpcode() == ISD::ADD) {
263     // TODO: The following code appears to be needless as it just
264     //       bails on some Ptrs early, reducing the cases where we
265     //       find equivalence. We should be able to remove this.
266     // Inside a loop the current BASE pointer is calculated using an ADD and a
267     // MUL instruction. In this case Base is the actual BASE pointer.
268     // (i64 add (i64 %array_ptr)
269     //          (i64 mul (i64 %induction_var)
270     //                   (i64 %element_size)))
271     if (Base->getOperand(1)->getOpcode() == ISD::MUL)
272       return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
273 
274     // Look at Base + Index + Offset cases.
275     Index = Base->getOperand(1);
276     SDValue PotentialBase = Base->getOperand(0);
277 
278     // Skip signextends.
279     if (Index->getOpcode() == ISD::SIGN_EXTEND) {
280       Index = Index->getOperand(0);
281       IsIndexSignExt = true;
282     }
283 
284     // Check if Index Offset pattern
285     if (Index->getOpcode() != ISD::ADD ||
286         !isa<ConstantSDNode>(Index->getOperand(1)))
287       return BaseIndexOffset(PotentialBase, Index, Offset, IsIndexSignExt);
288 
289     Offset += cast<ConstantSDNode>(Index->getOperand(1))->getSExtValue();
290     Index = Index->getOperand(0);
291     if (Index->getOpcode() == ISD::SIGN_EXTEND) {
292       Index = Index->getOperand(0);
293       IsIndexSignExt = true;
294     } else
295       IsIndexSignExt = false;
296     Base = PotentialBase;
297   }
298   return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
299 }
300 
match(const SDNode * N,const SelectionDAG & DAG)301 BaseIndexOffset BaseIndexOffset::match(const SDNode *N,
302                                        const SelectionDAG &DAG) {
303   if (const auto *LS0 = dyn_cast<LSBaseSDNode>(N))
304     return matchLSNode(LS0, DAG);
305   if (const auto *LN = dyn_cast<LifetimeSDNode>(N)) {
306     if (LN->hasOffset())
307       return BaseIndexOffset(LN->getOperand(1), SDValue(), LN->getOffset(),
308                              false);
309     return BaseIndexOffset(LN->getOperand(1), SDValue(), false);
310   }
311   return BaseIndexOffset();
312 }
313 
314 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
315 
dump() const316 LLVM_DUMP_METHOD void BaseIndexOffset::dump() const {
317   print(dbgs());
318 }
319 
print(raw_ostream & OS) const320 void BaseIndexOffset::print(raw_ostream& OS) const {
321   OS << "BaseIndexOffset base=[";
322   Base->print(OS);
323   OS << "] index=[";
324   if (Index)
325     Index->print(OS);
326   OS << "] offset=" << Offset;
327 }
328 
329 #endif
330