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                          "define i32 @f() {\n"
34                          "  %1 = load i32, i32* @g\n"
35                          "  ret i32 %1\n"
36                          "}";
37 
38     Triple TargetTriple("aarch64--");
39     std::string Error;
40     const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
41     // FIXME: These tests do not depend on AArch64 specifically, but we have to
42     // initialize a target. A skeleton Target for unittests would allow us to
43     // always run these tests.
44     if (!T)
45       return;
46 
47     TargetOptions Options;
48     TM = std::unique_ptr<LLVMTargetMachine>(static_cast<LLVMTargetMachine *>(
49         T->createTargetMachine("AArch64", "", "+sve", Options, None, None,
50                                CodeGenOpt::Aggressive)));
51     if (!TM)
52       return;
53 
54     SMDiagnostic SMError;
55     M = parseAssemblyString(Assembly, SMError, Context);
56     if (!M)
57       report_fatal_error(SMError.getMessage());
58     M->setDataLayout(TM->createDataLayout());
59 
60     F = M->getFunction("f");
61     if (!F)
62       report_fatal_error("F?");
63     G = M->getGlobalVariable("g");
64     if (!G)
65       report_fatal_error("G?");
66 
67     MachineModuleInfo MMI(TM.get());
68 
69     MF = std::make_unique<MachineFunction>(*F, *TM, *TM->getSubtargetImpl(*F),
70                                            0, MMI);
71 
72     DAG = std::make_unique<SelectionDAG>(*TM, CodeGenOpt::None);
73     if (!DAG)
74       report_fatal_error("DAG?");
75     OptimizationRemarkEmitter ORE(F);
76     DAG->init(*MF, ORE, nullptr, nullptr, nullptr, nullptr, nullptr);
77   }
78 
79   TargetLoweringBase::LegalizeTypeAction getTypeAction(EVT VT) {
80     return DAG->getTargetLoweringInfo().getTypeAction(Context, VT);
81   }
82 
83   EVT getTypeToTransformTo(EVT VT) {
84     return DAG->getTargetLoweringInfo().getTypeToTransformTo(Context, VT);
85   }
86 
87   LLVMContext Context;
88   std::unique_ptr<LLVMTargetMachine> TM;
89   std::unique_ptr<Module> M;
90   Function *F;
91   GlobalVariable *G;
92   std::unique_ptr<MachineFunction> MF;
93   std::unique_ptr<SelectionDAG> DAG;
94 };
95 
96 TEST_F(SelectionDAGAddressAnalysisTest, sameFrameObject) {
97   if (!TM)
98     return;
99   SDLoc Loc;
100   auto Int8VT = EVT::getIntegerVT(Context, 8);
101   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4);
102   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
103   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
104   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
105   TypeSize Offset = TypeSize::Fixed(0);
106   SDValue Value = DAG->getConstant(0, Loc, VecVT);
107   SDValue Index = DAG->getMemBasePlusOffset(FIPtr, Offset, Loc);
108   SDValue Store = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index,
109                                 PtrInfo.getWithOffset(Offset));
110   Optional<int64_t> NumBytes = MemoryLocation::getSizeOrUnknown(
111       cast<StoreSDNode>(Store)->getMemoryVT().getStoreSize());
112 
113   bool IsAlias;
114   bool IsValid = BaseIndexOffset::computeAliasing(
115       Store.getNode(), NumBytes, Store.getNode(), NumBytes, *DAG, IsAlias);
116 
117   EXPECT_TRUE(IsValid);
118   EXPECT_TRUE(IsAlias);
119 }
120 
121 TEST_F(SelectionDAGAddressAnalysisTest, noAliasingFrameObjects) {
122   if (!TM)
123     return;
124   SDLoc Loc;
125   auto Int8VT = EVT::getIntegerVT(Context, 8);
126   // <4 x i8>
127   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4);
128   // <2 x i8>
129   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2);
130   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
131   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
132   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
133   SDValue Value = DAG->getConstant(0, Loc, SubVecVT);
134   TypeSize Offset0 = TypeSize::Fixed(0);
135   TypeSize Offset1 = SubVecVT.getStoreSize();
136   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc);
137   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
138   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index0,
139                                  PtrInfo.getWithOffset(Offset0));
140   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index1,
141                                  PtrInfo.getWithOffset(Offset1));
142   Optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
143       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
144   Optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
145       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
146 
147   bool IsAlias;
148   bool IsValid = BaseIndexOffset::computeAliasing(
149       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
150 
151   EXPECT_TRUE(IsValid);
152   EXPECT_FALSE(IsAlias);
153 }
154 
155 TEST_F(SelectionDAGAddressAnalysisTest, unknownSizeFrameObjects) {
156   if (!TM)
157     return;
158   SDLoc Loc;
159   auto Int8VT = EVT::getIntegerVT(Context, 8);
160   // <vscale x 4 x i8>
161   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
162   // <vscale x 2 x i8>
163   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
164   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
165   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
166   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
167   SDValue Value = DAG->getConstant(0, Loc, SubVecVT);
168   TypeSize Offset1 = SubVecVT.getStoreSize();
169   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
170   SDValue Store0 =
171       DAG->getStore(DAG->getEntryNode(), Loc, Value, FIPtr, PtrInfo);
172   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index1,
173                                  MachinePointerInfo(PtrInfo.getAddrSpace()));
174   Optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
175       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
176   Optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
177       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
178 
179   bool IsAlias;
180   bool IsValid = BaseIndexOffset::computeAliasing(
181       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
182 
183   EXPECT_FALSE(IsValid);
184 }
185 
186 TEST_F(SelectionDAGAddressAnalysisTest, globalWithFrameObject) {
187   if (!TM)
188     return;
189   SDLoc Loc;
190   auto Int8VT = EVT::getIntegerVT(Context, 8);
191   // <vscale x 4 x i8>
192   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
193   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
194   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
195   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
196   SDValue Value = DAG->getConstant(0, Loc, VecVT);
197   TypeSize Offset = TypeSize::Fixed(0);
198   SDValue Index = DAG->getMemBasePlusOffset(FIPtr, Offset, Loc);
199   SDValue Store = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index,
200                                 PtrInfo.getWithOffset(Offset));
201   Optional<int64_t> NumBytes = MemoryLocation::getSizeOrUnknown(
202       cast<StoreSDNode>(Store)->getMemoryVT().getStoreSize());
203   EVT GTy = DAG->getTargetLoweringInfo().getValueType(DAG->getDataLayout(),
204                                                       G->getType());
205   SDValue GValue = DAG->getConstant(0, Loc, GTy);
206   SDValue GAddr = DAG->getGlobalAddress(G, Loc, GTy);
207   SDValue GStore = DAG->getStore(DAG->getEntryNode(), Loc, GValue, GAddr,
208                                  MachinePointerInfo(G, 0));
209   Optional<int64_t> GNumBytes = MemoryLocation::getSizeOrUnknown(
210       cast<StoreSDNode>(GStore)->getMemoryVT().getStoreSize());
211 
212   bool IsAlias;
213   bool IsValid = BaseIndexOffset::computeAliasing(
214       Store.getNode(), NumBytes, GStore.getNode(), GNumBytes, *DAG, IsAlias);
215 
216   EXPECT_TRUE(IsValid);
217   EXPECT_FALSE(IsAlias);
218 }
219 
220 TEST_F(SelectionDAGAddressAnalysisTest, fixedSizeFrameObjectsWithinDiff) {
221   if (!TM)
222     return;
223   SDLoc Loc;
224   auto Int8VT = EVT::getIntegerVT(Context, 8);
225   // <vscale x 4 x i8>
226   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
227   // <vscale x 2 x i8>
228   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
229   // <2 x i8>
230   auto SubFixedVecVT2xi8 = EVT::getVectorVT(Context, Int8VT, 2);
231   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
232   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
233   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
234   SDValue Value0 = DAG->getConstant(0, Loc, SubFixedVecVT2xi8);
235   SDValue Value1 = DAG->getConstant(0, Loc, SubVecVT);
236   TypeSize Offset0 = TypeSize::Fixed(0);
237   TypeSize Offset1 = SubFixedVecVT2xi8.getStoreSize();
238   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc);
239   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
240   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0,
241                                  PtrInfo.getWithOffset(Offset0));
242   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1,
243                                  PtrInfo.getWithOffset(Offset1));
244   Optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
245       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
246   Optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
247       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
248 
249   bool IsAlias;
250   bool IsValid = BaseIndexOffset::computeAliasing(
251       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
252   EXPECT_TRUE(IsValid);
253   EXPECT_FALSE(IsAlias);
254 
255   IsValid = BaseIndexOffset::computeAliasing(
256       Store1.getNode(), NumBytes1, Store0.getNode(), NumBytes0, *DAG, IsAlias);
257   EXPECT_TRUE(IsValid);
258   EXPECT_FALSE(IsAlias);
259 }
260 
261 TEST_F(SelectionDAGAddressAnalysisTest, fixedSizeFrameObjectsOutOfDiff) {
262   if (!TM)
263     return;
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   // <4 x i8>
273   auto SubFixedVecVT4xi8 = EVT::getVectorVT(Context, Int8VT, 4);
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, SubFixedVecVT4xi8);
278   SDValue Value1 = DAG->getConstant(0, Loc, SubVecVT);
279   TypeSize Offset0 = TypeSize::Fixed(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   Optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
288       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
289   Optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
290       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
291 
292   bool IsAlias;
293   bool IsValid = BaseIndexOffset::computeAliasing(
294       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
295   EXPECT_TRUE(IsValid);
296   EXPECT_TRUE(IsAlias);
297 }
298 
299 TEST_F(SelectionDAGAddressAnalysisTest, twoFixedStackObjects) {
300   if (!TM)
301     return;
302   SDLoc Loc;
303   auto Int8VT = EVT::getIntegerVT(Context, 8);
304   // <vscale x 2 x i8>
305   auto VecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
306   // <2 x i8>
307   auto FixedVecVT = EVT::getVectorVT(Context, Int8VT, 2);
308   SDValue FIPtr0 = DAG->CreateStackTemporary(FixedVecVT);
309   SDValue FIPtr1 = DAG->CreateStackTemporary(VecVT);
310   int FI0 = cast<FrameIndexSDNode>(FIPtr0.getNode())->getIndex();
311   int FI1 = cast<FrameIndexSDNode>(FIPtr1.getNode())->getIndex();
312   MachinePointerInfo PtrInfo0 = MachinePointerInfo::getFixedStack(*MF, FI0);
313   MachinePointerInfo PtrInfo1 = MachinePointerInfo::getFixedStack(*MF, FI1);
314   SDValue Value0 = DAG->getConstant(0, Loc, FixedVecVT);
315   SDValue Value1 = DAG->getConstant(0, Loc, VecVT);
316   TypeSize Offset0 = TypeSize::Fixed(0);
317   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr0, Offset0, Loc);
318   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr1, Offset0, Loc);
319   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0,
320                                  PtrInfo0.getWithOffset(Offset0));
321   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1,
322                                  PtrInfo1.getWithOffset(Offset0));
323   Optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
324       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
325   Optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
326       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
327 
328   bool IsAlias;
329   bool IsValid = BaseIndexOffset::computeAliasing(
330       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
331   EXPECT_TRUE(IsValid);
332   EXPECT_FALSE(IsAlias);
333 }
334 
335 } // end namespace llvm
336