Jlm
Loading...
Searching...
No Matches
PointsToGraphAliasAnalysisTests.cpp
Go to the documentation of this file.
1/*
2 * Copyright 2025 Håvard Krogstie <krogstie.havard@gmail.com>
3 * See COPYING for terms of redistribution.
4 */
5
6#include <gtest/gtest.h>
7
8#include <jlm/llvm/ir/CallingConvention.hpp>
9#include <jlm/llvm/ir/operators/alloca.hpp>
10#include <jlm/llvm/ir/operators/GetElementPtr.hpp>
11#include <jlm/llvm/ir/operators/Load.hpp>
12#include <jlm/llvm/ir/operators/operators.hpp>
13#include <jlm/llvm/ir/operators/Store.hpp>
14#include <jlm/llvm/opt/alias-analyses/Andersen.hpp>
15#include <jlm/llvm/opt/alias-analyses/PointsToGraphAliasAnalysis.hpp>
16#include <jlm/llvm/TestRvsdgs.hpp>
17#include <jlm/rvsdg/bitstring/constant.hpp>
18#include <jlm/rvsdg/view.hpp>
19
23static void
24Expect(
25 jlm::llvm::aa::AliasAnalysis & aa,
26 const jlm::rvsdg::Output & p1,
27 size_t s1,
28 const jlm::rvsdg::Output & p2,
29 size_t s2,
30 jlm::llvm::aa::AliasAnalysis::AliasQueryResponse expected)
31{
32 const auto actual = aa.Query(p1, s1, p2, s2);
33 EXPECT_EQ(actual, expected);
34
35 // An alias analysis query should always be symmetrical, so check the opposite as well
36 const auto mirror = aa.Query(p2, s2, p1, s1);
37 EXPECT_EQ(mirror, expected);
38}
39
72class PtGAliasAnalysisTest final : public jlm::llvm::RvsdgTest
73{
92
93public:
94 const Outputs &
95 GetOutputs() const noexcept
96 {
97 return Outputs_;
98 }
99
100private:
101 std::unique_ptr<jlm::llvm::LlvmRvsdgModule>
102 SetupRvsdg() override
103 {
104 using namespace jlm;
105 using namespace jlm::llvm;
106
107 auto rvsdgModule = LlvmRvsdgModule::Create(jlm::util::FilePath(""), "", "");
108 auto & rvsdg = rvsdgModule->Rvsdg();
109
110 const auto pointerType = PointerType::Create();
111 const auto intType = rvsdg::BitType::Create(32);
112 const auto ioStateType = IOStateType::Create();
113 const auto memoryStateType = MemoryStateType::Create();
114
115 const auto funcType = rvsdg::FunctionType::Create(
116 { pointerType, ioStateType, memoryStateType },
117 { ioStateType, memoryStateType });
118
119 const auto getPtrFuncType = rvsdg::FunctionType::Create(
120 { ioStateType, memoryStateType },
121 { pointerType, ioStateType, memoryStateType });
122
123 Outputs_.GetPtr = &LlvmGraphImport::createFunctionImport(
124 rvsdg,
125 getPtrFuncType,
126 "getPtr",
127 Linkage::externalLinkage,
128 CallingConvention::Default);
129
130 // Create the global pointer variable "global", that is exported
131 auto & globalDelta = *rvsdg::DeltaNode::Create(
132 &rvsdg.GetRootRegion(),
133 LlvmDeltaOperation::Create(pointerType, "global", Linkage::externalLinkage, "", false, 4));
134 {
135 const auto nullPtr =
136 ConstantPointerNullOperation::createNode(*globalDelta.subregion()).output(0);
137 globalDelta.finalize(nullPtr);
138 }
139 rvsdg::GraphExport::Create(globalDelta.output(), "global");
140 Outputs_.Global = &globalDelta.output();
141
142 // Create the global variable "local", that is not exported
143 auto & localDelta = *rvsdg::DeltaNode::Create(
144 &rvsdg.GetRootRegion(),
145 LlvmDeltaOperation::Create(pointerType, "local", Linkage::internalLinkage, "", false, 4));
146 {
147 const auto nullPtr =
148 ConstantPointerNullOperation::createNode(*localDelta.subregion()).output(0);
149 localDelta.finalize(nullPtr);
150 }
151 Outputs_.Local = &localDelta.output();
152
153 Outputs_.Imported = &LlvmGraphImport::createGlobalImport(
154 rvsdg,
155 pointerType,
156 pointerType,
157 "imported",
158 Linkage::externalLinkage,
159 false,
160 4);
161
162 // Setup the function "func"
163 {
164 auto & lambdaNode = *rvsdg::LambdaNode::Create(
165 rvsdg.GetRootRegion(),
166 LlvmLambdaOperation::Create(funcType, "func", Linkage::internalLinkage));
167
168 Outputs_.P = lambdaNode.GetFunctionArguments()[0];
169 auto ioState = lambdaNode.GetFunctionArguments()[1];
170 auto memoryState = lambdaNode.GetFunctionArguments()[2];
171
172 const auto getPtrCtxVar = lambdaNode.AddContextVar(*Outputs_.GetPtr).inner;
173 const auto globalCtxVar = lambdaNode.AddContextVar(*Outputs_.Global).inner;
174 const auto localCtxVar = lambdaNode.AddContextVar(*Outputs_.Local).inner;
175 const auto importedCtxVar = lambdaNode.AddContextVar(*Outputs_.Imported).inner;
176
177 const auto constantOne =
178 &rvsdg::BitConstantOperation::create(*lambdaNode.subregion(), { 32, 1 });
179
180 const auto alloca1Outputs = AllocaOperation::create(intType, constantOne, 4);
181 const auto alloca2Outputs = AllocaOperation::create(intType, constantOne, 4);
182 const auto alloca3Outputs = AllocaOperation::create(intType, constantOne, 4);
183 const auto alloca4Outputs = AllocaOperation::create(intType, constantOne, 4);
184
185 Outputs_.Alloca1 = alloca1Outputs[0];
186 Outputs_.Alloca2 = alloca2Outputs[0];
187 Outputs_.Alloca3 = alloca3Outputs[0];
188 Outputs_.Alloca4 = alloca4Outputs[0];
189
190 memoryState = MemoryStateMergeOperation::Create({ memoryState,
191 alloca1Outputs[1],
192 alloca2Outputs[1],
193 alloca3Outputs[1],
194 alloca4Outputs[1] });
195
196 // Load: q = *p;
197 const auto loadP =
198 LoadNonVolatileOperation::Create(Outputs_.P, { memoryState }, pointerType, 8);
199 Outputs_.Q = loadP[0];
200 memoryState = loadP[1];
201
202 // Store the address of alloca1 to p
203 const auto storeP =
204 StoreNonVolatileOperation::Create(Outputs_.P, Outputs_.Alloca1, { memoryState }, 8);
205 memoryState = storeP[0];
206
207 // Create loads of the global variables
208 const auto loadGlobal =
209 LoadNonVolatileOperation::Create(globalCtxVar, { memoryState }, pointerType, 8);
210 Outputs_.GlobalLoad = loadGlobal[0];
211 memoryState = loadGlobal[1];
212
213 const auto loadLocal =
214 LoadNonVolatileOperation::Create(localCtxVar, { memoryState }, pointerType, 8);
215 Outputs_.LocalLoad = loadLocal[0];
216 memoryState = loadLocal[1];
217
218 const auto loadImported =
219 LoadNonVolatileOperation::Create(importedCtxVar, { memoryState }, pointerType, 8);
220 Outputs_.ImportedLoad = loadImported[0];
221 memoryState = loadImported[1];
222
223 // Store to global values
224 const auto storeGlobal =
225 StoreNonVolatileOperation::Create(globalCtxVar, Outputs_.Alloca2, { memoryState }, 8);
226 memoryState = storeGlobal[0];
227
228 const auto storeLocal =
229 StoreNonVolatileOperation::Create(localCtxVar, Outputs_.Alloca3, { memoryState }, 8);
230 memoryState = storeLocal[0];
231
232 const auto storeImported =
233 StoreNonVolatileOperation::Create(importedCtxVar, Outputs_.Alloca4, { memoryState }, 8);
234 memoryState = storeImported[0];
235
236 // Get r by calling getPtr()
237 const auto callOutputs =
238 CallOperation::Create(getPtrCtxVar, getPtrFuncType, { ioState, memoryState });
239 Outputs_.R = callOutputs[0];
240 ioState = callOutputs[1];
241 memoryState = callOutputs[2];
242
243 lambdaNode.finalize({ ioState, memoryState });
244 Outputs_.Func = lambdaNode.output();
245 }
246 rvsdg::GraphExport::Create(*Outputs_.Func, "func");
247
248 return rvsdgModule;
249 }
250
251 Outputs Outputs_ = {};
252};
253
254TEST(PointsToGraphAnalysisTests, TestPtGAliasAnalysis)
255{
256 using namespace jlm::llvm::aa;
257
258 // Arrange
259 PtGAliasAnalysisTest rvsdg;
260 rvsdg.InitializeTest();
261 const auto & outputs = rvsdg.GetOutputs();
262
263 // jlm::rvsdg::view(&rvsdg.graph().GetRootRegion(), stdout);
264
265 Andersen andersen;
266 auto pointsToGraph = andersen.Analyze(rvsdg.module());
267 std::cout << PointsToGraph::dumpDot(*pointsToGraph) << std::endl;
268 PointsToGraphAliasAnalysis aa(std::move(pointsToGraph));
269
270 // Assert
271
272 // Distinct global variables do not alias
273 Expect(aa, *outputs.Global, 8, *outputs.Local, 8, AliasAnalysis::NoAlias);
274 Expect(aa, *outputs.Global, 8, *outputs.Imported, 8, AliasAnalysis::NoAlias);
275 Expect(aa, *outputs.Local, 8, *outputs.Imported, 8, AliasAnalysis::NoAlias);
276
277 // The same global variable aliases itself
278 Expect(aa, *outputs.Global, 8, *outputs.Global, 8, AliasAnalysis::MustAlias);
279 Expect(aa, *outputs.Local, 8, *outputs.Local, 8, AliasAnalysis::MustAlias);
280 Expect(aa, *outputs.Imported, 4, *outputs.Imported, 4, AliasAnalysis::MustAlias);
281
282 // Distinct allocas never alias with each other or globals
283 Expect(aa, *outputs.Alloca1, 8, *outputs.Alloca2, 8, AliasAnalysis::NoAlias);
284 Expect(aa, *outputs.Alloca1, 8, *outputs.Alloca3, 8, AliasAnalysis::NoAlias);
285 Expect(aa, *outputs.Alloca1, 8, *outputs.Alloca4, 8, AliasAnalysis::NoAlias);
286 Expect(aa, *outputs.Alloca1, 8, *outputs.Global, 8, AliasAnalysis::NoAlias);
287 Expect(aa, *outputs.Alloca1, 8, *outputs.Local, 8, AliasAnalysis::NoAlias);
288 Expect(aa, *outputs.Alloca1, 8, *outputs.Imported, 8, AliasAnalysis::NoAlias);
289
290 // The pointer argument may point to any escaped memory
291 Expect(aa, *outputs.P, 8, *outputs.Global, 8, AliasAnalysis::MayAlias);
292 Expect(aa, *outputs.P, 8, *outputs.Imported, 8, AliasAnalysis::MayAlias);
293 // But not things that have not escaped
294 Expect(aa, *outputs.P, 8, *outputs.Local, 8, AliasAnalysis::NoAlias);
295 Expect(aa, *outputs.P, 8, *outputs.Alloca3, 8, AliasAnalysis::NoAlias);
296
297 // The pointer q, loaded from p, is likewise unknown
298 Expect(aa, *outputs.Q, 8, *outputs.Global, 8, AliasAnalysis::MayAlias);
299 Expect(aa, *outputs.Q, 8, *outputs.Imported, 8, AliasAnalysis::MayAlias);
300 Expect(aa, *outputs.Q, 8, *outputs.P, 8, AliasAnalysis::MayAlias);
301 Expect(aa, *outputs.Q, 8, *outputs.Local, 8, AliasAnalysis::NoAlias);
302 Expect(aa, *outputs.Q, 8, *outputs.Alloca3, 8, AliasAnalysis::NoAlias);
303
304 // The pointer value loaded from global can point to anything externally available
305 Expect(aa, *outputs.GlobalLoad, 4, *outputs.Global, 4, AliasAnalysis::MayAlias);
306 Expect(aa, *outputs.GlobalLoad, 4, *outputs.Imported, 4, AliasAnalysis::MayAlias);
307 Expect(aa, *outputs.GlobalLoad, 4, *outputs.Alloca1, 4, AliasAnalysis::MayAlias);
308 Expect(aa, *outputs.GlobalLoad, 4, *outputs.Local, 4, AliasAnalysis::NoAlias);
309
310 // The pointer value loaded from local can not point to anything (except alloca3)
311 Expect(aa, *outputs.LocalLoad, 4, *outputs.Global, 4, AliasAnalysis::NoAlias);
312 Expect(aa, *outputs.LocalLoad, 4, *outputs.Imported, 4, AliasAnalysis::NoAlias);
313 Expect(aa, *outputs.LocalLoad, 4, *outputs.Alloca1, 4, AliasAnalysis::NoAlias);
314 Expect(aa, *outputs.LocalLoad, 4, *outputs.Alloca2, 4, AliasAnalysis::NoAlias);
315 Expect(aa, *outputs.LocalLoad, 4, *outputs.Alloca4, 4, AliasAnalysis::NoAlias);
316 Expect(aa, *outputs.LocalLoad, 4, *outputs.P, 4, AliasAnalysis::NoAlias);
317 Expect(aa, *outputs.LocalLoad, 4, *outputs.Q, 4, AliasAnalysis::NoAlias);
318
319 // The pointer value loaded from imported is just like the one loaded from global
320 Expect(aa, *outputs.ImportedLoad, 4, *outputs.Global, 4, AliasAnalysis::MayAlias);
321 Expect(aa, *outputs.ImportedLoad, 4, *outputs.Imported, 4, AliasAnalysis::MayAlias);
322 Expect(aa, *outputs.ImportedLoad, 4, *outputs.Alloca1, 4, AliasAnalysis::MayAlias);
323 Expect(aa, *outputs.ImportedLoad, 4, *outputs.Local, 4, AliasAnalysis::NoAlias);
324
325 // The pointer we get from getPtr() can point to anything that is externally available
326 Expect(aa, *outputs.R, 4, *outputs.Global, 4, AliasAnalysis::MayAlias);
327 Expect(aa, *outputs.R, 4, *outputs.Imported, 4, AliasAnalysis::MayAlias);
328 Expect(aa, *outputs.R, 4, *outputs.Alloca1, 4, AliasAnalysis::MayAlias);
329 Expect(aa, *outputs.R, 4, *outputs.Alloca2, 4, AliasAnalysis::MayAlias);
330 Expect(aa, *outputs.R, 4, *outputs.Alloca4, 4, AliasAnalysis::MayAlias);
331 Expect(aa, *outputs.R, 4, *outputs.P, 4, AliasAnalysis::MayAlias);
332 Expect(aa, *outputs.R, 4, *outputs.Q, 4, AliasAnalysis::MayAlias);
333
334 // It can not point to alloca3, as it never escaped the module
335 Expect(aa, *outputs.R, 4, *outputs.Alloca3, 4, AliasAnalysis::NoAlias);
336}
337
354class PtGAliasAnalysisTestOffsets final : public jlm::llvm::RvsdgTest
355{
366
367public:
368 const Outputs &
369 GetOutputs() const noexcept
370 {
371 return Outputs_;
372 }
373
374private:
375 std::unique_ptr<jlm::llvm::LlvmRvsdgModule>
376 SetupRvsdg() override
377 {
378 using namespace jlm;
379 using namespace jlm::llvm;
380
381 auto rvsdgModule = LlvmRvsdgModule::Create(jlm::util::FilePath(""), "", "");
382 auto & rvsdg = rvsdgModule->Rvsdg();
383
384 const auto pointerType = PointerType::Create();
385 const auto byteType = rvsdg::BitType::Create(8);
386 const auto int32Type = rvsdg::BitType::Create(32);
387 const auto int64Type = rvsdg::BitType::Create(64);
388 const auto ioStateType = IOStateType::Create();
389 const auto memoryStateType = MemoryStateType::Create();
390
391 const auto funcType = rvsdg::FunctionType::Create(
392 { pointerType, int32Type, ioStateType, memoryStateType },
393 { ioStateType, memoryStateType });
394
395 Outputs_.GlobalInt = &LlvmGraphImport::createGlobalImport(
396 rvsdg,
397 int32Type,
398 pointerType,
399 "globalInt",
400 Linkage::externalLinkage,
401 false,
402 4);
403
404 Outputs_.GlobalLong = &LlvmGraphImport::createGlobalImport(
405 rvsdg,
406 int64Type,
407 pointerType,
408 "globalLong",
409 Linkage::externalLinkage,
410 false,
411 4);
412
413 // Setup the function "func"
414 {
415 auto & lambdaNode = *rvsdg::LambdaNode::Create(
416 rvsdg.GetRootRegion(),
417 LlvmLambdaOperation::Create(funcType, "func", Linkage::internalLinkage));
418
419 Outputs_.P = lambdaNode.GetFunctionArguments()[0];
420 Outputs_.Offset = lambdaNode.GetFunctionArguments()[1];
421 auto ioState = lambdaNode.GetFunctionArguments()[2];
422 auto memoryState = lambdaNode.GetFunctionArguments()[3];
423
424 const auto globalIntCtxVar = lambdaNode.AddContextVar(*Outputs_.GlobalInt).inner;
425 const auto globalLongCtxVar = lambdaNode.AddContextVar(*Outputs_.GlobalLong).inner;
426
427 Outputs_.IntWithOffset =
428 GetElementPtrOperation::create(globalIntCtxVar, { Outputs_.Offset }, byteType);
429 Outputs_.LongWithOffset =
430 GetElementPtrOperation::create(globalLongCtxVar, { Outputs_.Offset }, byteType);
431
432 lambdaNode.finalize({ ioState, memoryState });
433 Outputs_.Func = lambdaNode.output();
434 }
435 // Ensure func is being called from external modules
436 rvsdg::GraphExport::Create(*Outputs_.Func, "func");
437
438 return rvsdgModule;
439 }
440
441 Outputs Outputs_ = {};
442};
443
444TEST(PointsToGraphAnalysisTests, TestPtGAliasAnalysisOffsets)
445{
446 using namespace jlm::llvm::aa;
447
448 // Arrange
449 PtGAliasAnalysisTestOffsets rvsdg;
450 rvsdg.InitializeTest();
451 const auto & outputs = rvsdg.GetOutputs();
452
453 // jlm::rvsdg::view(&rvsdg.graph().GetRootRegion(), stdout);
454
455 Andersen andersen;
456 auto pointsToGraph = andersen.Analyze(rvsdg.module());
457 std::cout << PointsToGraph::dumpDot(*pointsToGraph) << std::endl;
458 PointsToGraphAliasAnalysis aa(std::move(pointsToGraph));
459
460 // Assert
461
462 // Distinct global variables do not alias
463 Expect(aa, *outputs.GlobalInt, 4, *outputs.GlobalLong, 4, AliasAnalysis::NoAlias);
464
465 // The pointer argument can alias with either
466 Expect(aa, *outputs.P, 4, *outputs.GlobalInt, 4, AliasAnalysis::MayAlias);
467 Expect(aa, *outputs.P, 8, *outputs.GlobalLong, 8, AliasAnalysis::MayAlias);
468
469 // If the accessed size is too large, the pointer argument can't access smaller memory objects
470 Expect(aa, *outputs.P, 5, *outputs.GlobalInt, 4, AliasAnalysis::NoAlias);
471 Expect(aa, *outputs.P, 9, *outputs.GlobalLong, 8, AliasAnalysis::NoAlias);
472
473 // With small access sizes, the unknown offset causes MayAlias
474 Expect(aa, *outputs.IntWithOffset, 2, *outputs.GlobalInt, 2, AliasAnalysis::MayAlias);
475 Expect(aa, *outputs.LongWithOffset, 2, *outputs.GlobalLong, 2, AliasAnalysis::MayAlias);
476
477 // Even with an unknown offset, the pointers are not mixed
478 Expect(aa, *outputs.IntWithOffset, 2, *outputs.GlobalLong, 2, AliasAnalysis::NoAlias);
479 Expect(aa, *outputs.LongWithOffset, 2, *outputs.GlobalInt, 2, AliasAnalysis::NoAlias);
480
481 // With full access sizes, the unknown offset can be ignored, and we get MustAlias
482 Expect(aa, *outputs.IntWithOffset, 4, *outputs.GlobalInt, 4, AliasAnalysis::MustAlias);
483 Expect(aa, *outputs.LongWithOffset, 8, *outputs.GlobalLong, 8, AliasAnalysis::MustAlias);
484}
expected
std::int64_t expected
Definition IntegerOperationsTests.cpp:26
Expect
static void Expect(jlm::llvm::aa::AliasAnalysis &aa, const jlm::rvsdg::Output &p1, size_t s1, const jlm::rvsdg::Output &p2, size_t s2, jlm::llvm::aa::AliasAnalysis::AliasQueryResponse expected)
Definition PointsToGraphAliasAnalysisTests.cpp:24
TEST
TEST(PointsToGraphAnalysisTests, TestPtGAliasAnalysis)
Definition PointsToGraphAliasAnalysisTests.cpp:254
PtGAliasAnalysisTestOffsets::GetOutputs
const Outputs & GetOutputs() const noexcept
Definition PointsToGraphAliasAnalysisTests.cpp:369
PtGAliasAnalysisTestOffsets::SetupRvsdg
std::unique_ptr< jlm::llvm::LlvmRvsdgModule > SetupRvsdg() override
Create RVSDG for this test.
Definition PointsToGraphAliasAnalysisTests.cpp:376
PtGAliasAnalysisTest::GetOutputs
const Outputs & GetOutputs() const noexcept
Definition PointsToGraphAliasAnalysisTests.cpp:95
PtGAliasAnalysisTest::SetupRvsdg
std::unique_ptr< jlm::llvm::LlvmRvsdgModule > SetupRvsdg() override
Create RVSDG for this test.
Definition PointsToGraphAliasAnalysisTests.cpp:102
jlm::llvm::RvsdgTest
RvsdgTest class.
Definition TestRvsdgs.hpp:29
jlm::llvm::RvsdgTest::module
jlm::llvm::LlvmRvsdgModule & module()
Definition TestRvsdgs.hpp:34
jlm::llvm::aa::AliasAnalysis::Query
virtual AliasQueryResponse Query(const rvsdg::Output &p1, size_t s1, const rvsdg::Output &p2, size_t s2)=0
jlm::llvm::aa::Andersen::Analyze
std::unique_ptr< PointsToGraph > Analyze(const rvsdg::RvsdgModule &module, util::StatisticsCollector &statisticsCollector) override
Definition Andersen.cpp:1575
jlm::llvm
Global memory state passed between functions.
Definition IpGraphToLlvmConverter.cpp:40
Generated by doxygen 1.9.8