xref: /llvm-project/llvm/unittests/CodeGen/SelectionDAGAddressAnalysisTest.cpp (revision 81b7f115fb272ef6fd6967f4121b64814b4bcf10) 
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/MC/TargetRegistry.h"
17 #include "llvm/Support/SourceMgr.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, std::nullopt,
51                                std::nullopt, CodeGenOptLevel::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, CodeGenOptLevel::None);
77     if (!DAG)
78       report_fatal_error("DAG?");
79     OptimizationRemarkEmitter ORE(F);
80     DAG->init(*MF, ORE, nullptr, 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::getFixed(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   std::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, sameFrameObjectUnknownSize) {
125   SDLoc Loc;
126   auto Int8VT = EVT::getIntegerVT(Context, 8);
127   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4);
128   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
129   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
130   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
131   TypeSize Offset = TypeSize::getFixed(0);
132   SDValue Value = DAG->getConstant(0, Loc, VecVT);
133   SDValue Index = DAG->getMemBasePlusOffset(FIPtr, Offset, Loc);
134   SDValue Store = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index,
135                                 PtrInfo.getWithOffset(Offset));
136 
137   // Maybe unlikely that BaseIndexOffset::computeAliasing is used with the
138   // optional NumBytes being unset like in this test, but it would be confusing
139   // if that function determined IsAlias=false here.
140   std::optional<int64_t> NumBytes;
141 
142   bool IsAlias;
143   bool IsValid = BaseIndexOffset::computeAliasing(
144       Store.getNode(), NumBytes, Store.getNode(), NumBytes, *DAG, IsAlias);
145 
146   EXPECT_FALSE(IsValid);
147 }
148 
149 TEST_F(SelectionDAGAddressAnalysisTest, noAliasingFrameObjects) {
150   SDLoc Loc;
151   auto Int8VT = EVT::getIntegerVT(Context, 8);
152   // <4 x i8>
153   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4);
154   // <2 x i8>
155   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2);
156   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
157   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
158   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
159   SDValue Value = DAG->getConstant(0, Loc, SubVecVT);
160   TypeSize Offset0 = TypeSize::getFixed(0);
161   TypeSize Offset1 = SubVecVT.getStoreSize();
162   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc);
163   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
164   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index0,
165                                  PtrInfo.getWithOffset(Offset0));
166   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index1,
167                                  PtrInfo.getWithOffset(Offset1));
168   std::optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
169       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
170   std::optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
171       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
172 
173   bool IsAlias;
174   bool IsValid = BaseIndexOffset::computeAliasing(
175       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
176 
177   EXPECT_TRUE(IsValid);
178   EXPECT_FALSE(IsAlias);
179 }
180 
181 TEST_F(SelectionDAGAddressAnalysisTest, unknownSizeFrameObjects) {
182   SDLoc Loc;
183   auto Int8VT = EVT::getIntegerVT(Context, 8);
184   // <vscale x 4 x i8>
185   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
186   // <vscale x 2 x i8>
187   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
188   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
189   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
190   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
191   SDValue Value = DAG->getConstant(0, Loc, SubVecVT);
192   TypeSize Offset1 = SubVecVT.getStoreSize();
193   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
194   SDValue Store0 =
195       DAG->getStore(DAG->getEntryNode(), Loc, Value, FIPtr, PtrInfo);
196   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index1,
197                                  MachinePointerInfo(PtrInfo.getAddrSpace()));
198   std::optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
199       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
200   std::optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
201       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
202 
203   bool IsAlias;
204   bool IsValid = BaseIndexOffset::computeAliasing(
205       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
206 
207   EXPECT_FALSE(IsValid);
208 }
209 
210 TEST_F(SelectionDAGAddressAnalysisTest, globalWithFrameObject) {
211   SDLoc Loc;
212   auto Int8VT = EVT::getIntegerVT(Context, 8);
213   // <vscale x 4 x i8>
214   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
215   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
216   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
217   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
218   SDValue Value = DAG->getConstant(0, Loc, VecVT);
219   TypeSize Offset = TypeSize::getFixed(0);
220   SDValue Index = DAG->getMemBasePlusOffset(FIPtr, Offset, Loc);
221   SDValue Store = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index,
222                                 PtrInfo.getWithOffset(Offset));
223   std::optional<int64_t> NumBytes = MemoryLocation::getSizeOrUnknown(
224       cast<StoreSDNode>(Store)->getMemoryVT().getStoreSize());
225   EVT GTy = DAG->getTargetLoweringInfo().getValueType(DAG->getDataLayout(),
226                                                       G->getType());
227   SDValue GValue = DAG->getConstant(0, Loc, GTy);
228   SDValue GAddr = DAG->getGlobalAddress(G, Loc, GTy);
229   SDValue GStore = DAG->getStore(DAG->getEntryNode(), Loc, GValue, GAddr,
230                                  MachinePointerInfo(G, 0));
231   std::optional<int64_t> GNumBytes = MemoryLocation::getSizeOrUnknown(
232       cast<StoreSDNode>(GStore)->getMemoryVT().getStoreSize());
233 
234   bool IsAlias;
235   bool IsValid = BaseIndexOffset::computeAliasing(
236       Store.getNode(), NumBytes, GStore.getNode(), GNumBytes, *DAG, IsAlias);
237 
238   EXPECT_TRUE(IsValid);
239   EXPECT_FALSE(IsAlias);
240 }
241 
242 TEST_F(SelectionDAGAddressAnalysisTest, globalWithAliasedGlobal) {
243   SDLoc Loc;
244 
245   EVT GTy = DAG->getTargetLoweringInfo().getValueType(DAG->getDataLayout(),
246                                                       G->getType());
247   SDValue GValue = DAG->getConstant(0, Loc, GTy);
248   SDValue GAddr = DAG->getGlobalAddress(G, Loc, GTy);
249   SDValue GStore = DAG->getStore(DAG->getEntryNode(), Loc, GValue, GAddr,
250                                  MachinePointerInfo(G, 0));
251   std::optional<int64_t> GNumBytes = MemoryLocation::getSizeOrUnknown(
252       cast<StoreSDNode>(GStore)->getMemoryVT().getStoreSize());
253 
254   SDValue AliasedGValue = DAG->getConstant(1, Loc, GTy);
255   SDValue AliasedGAddr = DAG->getGlobalAddress(AliasedG, Loc, GTy);
256   SDValue AliasedGStore =
257       DAG->getStore(DAG->getEntryNode(), Loc, AliasedGValue, AliasedGAddr,
258                     MachinePointerInfo(AliasedG, 0));
259 
260   bool IsAlias;
261   bool IsValid = BaseIndexOffset::computeAliasing(GStore.getNode(), GNumBytes,
262                                                   AliasedGStore.getNode(),
263                                                   GNumBytes, *DAG, IsAlias);
264 
265   // With some deeper analysis we could detect if G and AliasedG is aliasing or
266   // not. But computeAliasing is currently defensive and assumes that a
267   // GlobalAlias might alias with any global variable.
268   EXPECT_FALSE(IsValid);
269 }
270 
271 TEST_F(SelectionDAGAddressAnalysisTest, fixedSizeFrameObjectsWithinDiff) {
272   SDLoc Loc;
273   auto Int8VT = EVT::getIntegerVT(Context, 8);
274   // <vscale x 4 x i8>
275   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
276   // <vscale x 2 x i8>
277   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
278   // <2 x i8>
279   auto SubFixedVecVT2xi8 = EVT::getVectorVT(Context, Int8VT, 2);
280   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
281   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
282   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
283   SDValue Value0 = DAG->getConstant(0, Loc, SubFixedVecVT2xi8);
284   SDValue Value1 = DAG->getConstant(0, Loc, SubVecVT);
285   TypeSize Offset0 = TypeSize::getFixed(0);
286   TypeSize Offset1 = SubFixedVecVT2xi8.getStoreSize();
287   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc);
288   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
289   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0,
290                                  PtrInfo.getWithOffset(Offset0));
291   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1,
292                                  PtrInfo.getWithOffset(Offset1));
293   std::optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
294       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
295   std::optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
296       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
297 
298   bool IsAlias;
299   bool IsValid = BaseIndexOffset::computeAliasing(
300       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
301   EXPECT_TRUE(IsValid);
302   EXPECT_FALSE(IsAlias);
303 
304   IsValid = BaseIndexOffset::computeAliasing(
305       Store1.getNode(), NumBytes1, Store0.getNode(), NumBytes0, *DAG, IsAlias);
306   EXPECT_TRUE(IsValid);
307   EXPECT_FALSE(IsAlias);
308 }
309 
310 TEST_F(SelectionDAGAddressAnalysisTest, fixedSizeFrameObjectsOutOfDiff) {
311   SDLoc Loc;
312   auto Int8VT = EVT::getIntegerVT(Context, 8);
313   // <vscale x 4 x i8>
314   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
315   // <vscale x 2 x i8>
316   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
317   // <2 x i8>
318   auto SubFixedVecVT2xi8 = EVT::getVectorVT(Context, Int8VT, 2);
319   // <4 x i8>
320   auto SubFixedVecVT4xi8 = EVT::getVectorVT(Context, Int8VT, 4);
321   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
322   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
323   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
324   SDValue Value0 = DAG->getConstant(0, Loc, SubFixedVecVT4xi8);
325   SDValue Value1 = DAG->getConstant(0, Loc, SubVecVT);
326   TypeSize Offset0 = TypeSize::getFixed(0);
327   TypeSize Offset1 = SubFixedVecVT2xi8.getStoreSize();
328   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc);
329   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
330   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0,
331                                  PtrInfo.getWithOffset(Offset0));
332   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1,
333                                  PtrInfo.getWithOffset(Offset1));
334   std::optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
335       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
336   std::optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
337       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
338 
339   bool IsAlias;
340   bool IsValid = BaseIndexOffset::computeAliasing(
341       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
342   EXPECT_TRUE(IsValid);
343   EXPECT_TRUE(IsAlias);
344 }
345 
346 TEST_F(SelectionDAGAddressAnalysisTest, twoFixedStackObjects) {
347   SDLoc Loc;
348   auto Int8VT = EVT::getIntegerVT(Context, 8);
349   // <vscale x 2 x i8>
350   auto VecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
351   // <2 x i8>
352   auto FixedVecVT = EVT::getVectorVT(Context, Int8VT, 2);
353   SDValue FIPtr0 = DAG->CreateStackTemporary(FixedVecVT);
354   SDValue FIPtr1 = DAG->CreateStackTemporary(VecVT);
355   int FI0 = cast<FrameIndexSDNode>(FIPtr0.getNode())->getIndex();
356   int FI1 = cast<FrameIndexSDNode>(FIPtr1.getNode())->getIndex();
357   MachinePointerInfo PtrInfo0 = MachinePointerInfo::getFixedStack(*MF, FI0);
358   MachinePointerInfo PtrInfo1 = MachinePointerInfo::getFixedStack(*MF, FI1);
359   SDValue Value0 = DAG->getConstant(0, Loc, FixedVecVT);
360   SDValue Value1 = DAG->getConstant(0, Loc, VecVT);
361   TypeSize Offset0 = TypeSize::getFixed(0);
362   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr0, Offset0, Loc);
363   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr1, Offset0, Loc);
364   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0,
365                                  PtrInfo0.getWithOffset(Offset0));
366   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1,
367                                  PtrInfo1.getWithOffset(Offset0));
368   std::optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
369       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
370   std::optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
371       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
372 
373   bool IsAlias;
374   bool IsValid = BaseIndexOffset::computeAliasing(
375       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
376   EXPECT_TRUE(IsValid);
377   EXPECT_FALSE(IsAlias);
378 }
379 
380 } // end namespace llvm
381