xref: /llvm-project/llvm/unittests/CodeGen/SelectionDAGAddressAnalysisTest.cpp (revision 1896fb2cfffcf120eb28cefb67ac3d56035adc43) 
1 //===- llvm/unittest/CodeGen/SelectionDAGAddressAnalysisTest.cpp  ---------===//
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/Analysis/OptimizationRemarkEmitter.h"
12 #include "llvm/AsmParser/Parser.h"
13 #include "llvm/CodeGen/MachineModuleInfo.h"
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "llvm/CodeGen/TargetLowering.h"
16 #include "llvm/Support/SourceMgr.h"
17 #include "llvm/Support/TargetRegistry.h"
18 #include "llvm/Support/TargetSelect.h"
19 #include "llvm/Target/TargetMachine.h"
20 #include "gtest/gtest.h"
21 
22 namespace llvm {
23 
24 class SelectionDAGAddressAnalysisTest : public testing::Test {
25 protected:
26   static void SetUpTestCase() {
27     InitializeAllTargets();
28     InitializeAllTargetMCs();
29   }
30 
31   void SetUp() override {
32     StringRef Assembly = "@g = global i32 0\n"
33                          "@g_alias = alias i32, i32* @g\n"
34                          "define i32 @f() {\n"
35                          "  %1 = load i32, i32* @g\n"
36                          "  ret i32 %1\n"
37                          "}";
38 
39     Triple TargetTriple("aarch64--");
40     std::string Error;
41     const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
42     // FIXME: These tests do not depend on AArch64 specifically, but we have to
43     // initialize a target. A skeleton Target for unittests would allow us to
44     // always run these tests.
45     if (!T)
46       GTEST_SKIP();
47 
48     TargetOptions Options;
49     TM = std::unique_ptr<LLVMTargetMachine>(static_cast<LLVMTargetMachine *>(
50         T->createTargetMachine("AArch64", "", "+sve", Options, None, None,
51                                CodeGenOpt::Aggressive)));
52     if (!TM)
53       GTEST_SKIP();
54 
55     SMDiagnostic SMError;
56     M = parseAssemblyString(Assembly, SMError, Context);
57     if (!M)
58       report_fatal_error(SMError.getMessage());
59     M->setDataLayout(TM->createDataLayout());
60 
61     F = M->getFunction("f");
62     if (!F)
63       report_fatal_error("F?");
64     G = M->getGlobalVariable("g");
65     if (!G)
66       report_fatal_error("G?");
67     AliasedG = M->getNamedAlias("g_alias");
68     if (!AliasedG)
69       report_fatal_error("AliasedG?");
70 
71     MachineModuleInfo MMI(TM.get());
72 
73     MF = std::make_unique<MachineFunction>(*F, *TM, *TM->getSubtargetImpl(*F),
74                                            0, MMI);
75 
76     DAG = std::make_unique<SelectionDAG>(*TM, CodeGenOpt::None);
77     if (!DAG)
78       report_fatal_error("DAG?");
79     OptimizationRemarkEmitter ORE(F);
80     DAG->init(*MF, ORE, nullptr, nullptr, nullptr, nullptr, nullptr);
81   }
82 
83   TargetLoweringBase::LegalizeTypeAction getTypeAction(EVT VT) {
84     return DAG->getTargetLoweringInfo().getTypeAction(Context, VT);
85   }
86 
87   EVT getTypeToTransformTo(EVT VT) {
88     return DAG->getTargetLoweringInfo().getTypeToTransformTo(Context, VT);
89   }
90 
91   LLVMContext Context;
92   std::unique_ptr<LLVMTargetMachine> TM;
93   std::unique_ptr<Module> M;
94   Function *F;
95   GlobalVariable *G;
96   GlobalAlias *AliasedG;
97   std::unique_ptr<MachineFunction> MF;
98   std::unique_ptr<SelectionDAG> DAG;
99 };
100 
101 TEST_F(SelectionDAGAddressAnalysisTest, sameFrameObject) {
102   SDLoc Loc;
103   auto Int8VT = EVT::getIntegerVT(Context, 8);
104   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4);
105   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
106   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
107   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
108   TypeSize Offset = TypeSize::Fixed(0);
109   SDValue Value = DAG->getConstant(0, Loc, VecVT);
110   SDValue Index = DAG->getMemBasePlusOffset(FIPtr, Offset, Loc);
111   SDValue Store = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index,
112                                 PtrInfo.getWithOffset(Offset));
113   Optional<int64_t> NumBytes = MemoryLocation::getSizeOrUnknown(
114       cast<StoreSDNode>(Store)->getMemoryVT().getStoreSize());
115 
116   bool IsAlias;
117   bool IsValid = BaseIndexOffset::computeAliasing(
118       Store.getNode(), NumBytes, Store.getNode(), NumBytes, *DAG, IsAlias);
119 
120   EXPECT_TRUE(IsValid);
121   EXPECT_TRUE(IsAlias);
122 }
123 
124 TEST_F(SelectionDAGAddressAnalysisTest, noAliasingFrameObjects) {
125   SDLoc Loc;
126   auto Int8VT = EVT::getIntegerVT(Context, 8);
127   // <4 x i8>
128   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4);
129   // <2 x i8>
130   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2);
131   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
132   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
133   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
134   SDValue Value = DAG->getConstant(0, Loc, SubVecVT);
135   TypeSize Offset0 = TypeSize::Fixed(0);
136   TypeSize Offset1 = SubVecVT.getStoreSize();
137   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc);
138   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
139   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index0,
140                                  PtrInfo.getWithOffset(Offset0));
141   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index1,
142                                  PtrInfo.getWithOffset(Offset1));
143   Optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
144       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
145   Optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
146       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
147 
148   bool IsAlias;
149   bool IsValid = BaseIndexOffset::computeAliasing(
150       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
151 
152   EXPECT_TRUE(IsValid);
153   EXPECT_FALSE(IsAlias);
154 }
155 
156 TEST_F(SelectionDAGAddressAnalysisTest, unknownSizeFrameObjects) {
157   SDLoc Loc;
158   auto Int8VT = EVT::getIntegerVT(Context, 8);
159   // <vscale x 4 x i8>
160   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
161   // <vscale x 2 x i8>
162   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
163   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
164   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
165   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
166   SDValue Value = DAG->getConstant(0, Loc, SubVecVT);
167   TypeSize Offset1 = SubVecVT.getStoreSize();
168   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
169   SDValue Store0 =
170       DAG->getStore(DAG->getEntryNode(), Loc, Value, FIPtr, PtrInfo);
171   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index1,
172                                  MachinePointerInfo(PtrInfo.getAddrSpace()));
173   Optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
174       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
175   Optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
176       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
177 
178   bool IsAlias;
179   bool IsValid = BaseIndexOffset::computeAliasing(
180       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
181 
182   EXPECT_FALSE(IsValid);
183 }
184 
185 TEST_F(SelectionDAGAddressAnalysisTest, globalWithFrameObject) {
186   SDLoc Loc;
187   auto Int8VT = EVT::getIntegerVT(Context, 8);
188   // <vscale x 4 x i8>
189   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
190   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
191   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
192   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
193   SDValue Value = DAG->getConstant(0, Loc, VecVT);
194   TypeSize Offset = TypeSize::Fixed(0);
195   SDValue Index = DAG->getMemBasePlusOffset(FIPtr, Offset, Loc);
196   SDValue Store = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index,
197                                 PtrInfo.getWithOffset(Offset));
198   Optional<int64_t> NumBytes = MemoryLocation::getSizeOrUnknown(
199       cast<StoreSDNode>(Store)->getMemoryVT().getStoreSize());
200   EVT GTy = DAG->getTargetLoweringInfo().getValueType(DAG->getDataLayout(),
201                                                       G->getType());
202   SDValue GValue = DAG->getConstant(0, Loc, GTy);
203   SDValue GAddr = DAG->getGlobalAddress(G, Loc, GTy);
204   SDValue GStore = DAG->getStore(DAG->getEntryNode(), Loc, GValue, GAddr,
205                                  MachinePointerInfo(G, 0));
206   Optional<int64_t> GNumBytes = MemoryLocation::getSizeOrUnknown(
207       cast<StoreSDNode>(GStore)->getMemoryVT().getStoreSize());
208 
209   bool IsAlias;
210   bool IsValid = BaseIndexOffset::computeAliasing(
211       Store.getNode(), NumBytes, GStore.getNode(), GNumBytes, *DAG, IsAlias);
212 
213   EXPECT_TRUE(IsValid);
214   EXPECT_FALSE(IsAlias);
215 }
216 
217 TEST_F(SelectionDAGAddressAnalysisTest, globalWithAliasedGlobal) {
218   SDLoc Loc;
219 
220   EVT GTy = DAG->getTargetLoweringInfo().getValueType(DAG->getDataLayout(),
221                                                       G->getType());
222   SDValue GValue = DAG->getConstant(0, Loc, GTy);
223   SDValue GAddr = DAG->getGlobalAddress(G, Loc, GTy);
224   SDValue GStore = DAG->getStore(DAG->getEntryNode(), Loc, GValue, GAddr,
225                                  MachinePointerInfo(G, 0));
226   Optional<int64_t> GNumBytes = MemoryLocation::getSizeOrUnknown(
227       cast<StoreSDNode>(GStore)->getMemoryVT().getStoreSize());
228 
229   SDValue AliasedGValue = DAG->getConstant(1, Loc, GTy);
230   SDValue AliasedGAddr = DAG->getGlobalAddress(AliasedG, Loc, GTy);
231   SDValue AliasedGStore =
232       DAG->getStore(DAG->getEntryNode(), Loc, AliasedGValue, AliasedGAddr,
233                     MachinePointerInfo(AliasedG, 0));
234 
235   bool IsAlias;
236   bool IsValid = BaseIndexOffset::computeAliasing(GStore.getNode(), GNumBytes,
237                                                   AliasedGStore.getNode(),
238                                                   GNumBytes, *DAG, IsAlias);
239 
240   // With some deeper analysis we could detect if G and AliasedG is aliasing or
241   // not. But computeAliasing is currently defensive and assumes that a
242   // GlobalAlias might alias with any global variable.
243   EXPECT_FALSE(IsValid);
244 }
245 
246 TEST_F(SelectionDAGAddressAnalysisTest, fixedSizeFrameObjectsWithinDiff) {
247   SDLoc Loc;
248   auto Int8VT = EVT::getIntegerVT(Context, 8);
249   // <vscale x 4 x i8>
250   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
251   // <vscale x 2 x i8>
252   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
253   // <2 x i8>
254   auto SubFixedVecVT2xi8 = EVT::getVectorVT(Context, Int8VT, 2);
255   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
256   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
257   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
258   SDValue Value0 = DAG->getConstant(0, Loc, SubFixedVecVT2xi8);
259   SDValue Value1 = DAG->getConstant(0, Loc, SubVecVT);
260   TypeSize Offset0 = TypeSize::Fixed(0);
261   TypeSize Offset1 = SubFixedVecVT2xi8.getStoreSize();
262   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc);
263   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
264   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0,
265                                  PtrInfo.getWithOffset(Offset0));
266   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1,
267                                  PtrInfo.getWithOffset(Offset1));
268   Optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
269       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
270   Optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
271       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
272 
273   bool IsAlias;
274   bool IsValid = BaseIndexOffset::computeAliasing(
275       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
276   EXPECT_TRUE(IsValid);
277   EXPECT_FALSE(IsAlias);
278 
279   IsValid = BaseIndexOffset::computeAliasing(
280       Store1.getNode(), NumBytes1, Store0.getNode(), NumBytes0, *DAG, IsAlias);
281   EXPECT_TRUE(IsValid);
282   EXPECT_FALSE(IsAlias);
283 }
284 
285 TEST_F(SelectionDAGAddressAnalysisTest, fixedSizeFrameObjectsOutOfDiff) {
286   SDLoc Loc;
287   auto Int8VT = EVT::getIntegerVT(Context, 8);
288   // <vscale x 4 x i8>
289   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
290   // <vscale x 2 x i8>
291   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
292   // <2 x i8>
293   auto SubFixedVecVT2xi8 = EVT::getVectorVT(Context, Int8VT, 2);
294   // <4 x i8>
295   auto SubFixedVecVT4xi8 = EVT::getVectorVT(Context, Int8VT, 4);
296   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
297   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
298   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
299   SDValue Value0 = DAG->getConstant(0, Loc, SubFixedVecVT4xi8);
300   SDValue Value1 = DAG->getConstant(0, Loc, SubVecVT);
301   TypeSize Offset0 = TypeSize::Fixed(0);
302   TypeSize Offset1 = SubFixedVecVT2xi8.getStoreSize();
303   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc);
304   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
305   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0,
306                                  PtrInfo.getWithOffset(Offset0));
307   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1,
308                                  PtrInfo.getWithOffset(Offset1));
309   Optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
310       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
311   Optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
312       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
313 
314   bool IsAlias;
315   bool IsValid = BaseIndexOffset::computeAliasing(
316       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
317   EXPECT_TRUE(IsValid);
318   EXPECT_TRUE(IsAlias);
319 }
320 
321 TEST_F(SelectionDAGAddressAnalysisTest, twoFixedStackObjects) {
322   SDLoc Loc;
323   auto Int8VT = EVT::getIntegerVT(Context, 8);
324   // <vscale x 2 x i8>
325   auto VecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
326   // <2 x i8>
327   auto FixedVecVT = EVT::getVectorVT(Context, Int8VT, 2);
328   SDValue FIPtr0 = DAG->CreateStackTemporary(FixedVecVT);
329   SDValue FIPtr1 = DAG->CreateStackTemporary(VecVT);
330   int FI0 = cast<FrameIndexSDNode>(FIPtr0.getNode())->getIndex();
331   int FI1 = cast<FrameIndexSDNode>(FIPtr1.getNode())->getIndex();
332   MachinePointerInfo PtrInfo0 = MachinePointerInfo::getFixedStack(*MF, FI0);
333   MachinePointerInfo PtrInfo1 = MachinePointerInfo::getFixedStack(*MF, FI1);
334   SDValue Value0 = DAG->getConstant(0, Loc, FixedVecVT);
335   SDValue Value1 = DAG->getConstant(0, Loc, VecVT);
336   TypeSize Offset0 = TypeSize::Fixed(0);
337   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr0, Offset0, Loc);
338   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr1, Offset0, Loc);
339   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0,
340                                  PtrInfo0.getWithOffset(Offset0));
341   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1,
342                                  PtrInfo1.getWithOffset(Offset0));
343   Optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
344       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
345   Optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
346       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
347 
348   bool IsAlias;
349   bool IsValid = BaseIndexOffset::computeAliasing(
350       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
351   EXPECT_TRUE(IsValid);
352   EXPECT_FALSE(IsAlias);
353 }
354 
355 } // end namespace llvm
356