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