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