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