Jlm
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 
23 static void
24 Expect(
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 
72 class PtGAliasAnalysisTest final : public jlm::llvm::RvsdgTest
73 {
74  struct Outputs
75  {
76  jlm::rvsdg::Output * Global = {};
77  jlm::rvsdg::Output * Local = {};
78  jlm::rvsdg::Output * Imported = {};
79  jlm::rvsdg::Output * GetPtr = {};
80  jlm::rvsdg::Output * Func = {};
81  jlm::rvsdg::Output * P = {};
82  jlm::rvsdg::Output * Alloca1 = {};
83  jlm::rvsdg::Output * Alloca2 = {};
84  jlm::rvsdg::Output * Alloca3 = {};
85  jlm::rvsdg::Output * Alloca4 = {};
86  jlm::rvsdg::Output * Q = {};
87  jlm::rvsdg::Output * GlobalLoad = {};
88  jlm::rvsdg::Output * LocalLoad = {};
89  jlm::rvsdg::Output * ImportedLoad = {};
90  jlm::rvsdg::Output * R = {};
91  };
92 
93 public:
94  const Outputs &
95  GetOutputs() const noexcept
96  {
97  return Outputs_;
98  }
99 
100 private:
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  DeltaOperation::Create(pointerType, "global", Linkage::externalLinkage, "", false, 4));
134  {
135  const auto nullPtr =
136  ConstantPointerNullOperation::Create(globalDelta.subregion(), pointerType);
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  DeltaOperation::Create(pointerType, "local", Linkage::internalLinkage, "", false, 4));
146  {
147  const auto nullPtr =
148  ConstantPointerNullOperation::Create(localDelta.subregion(), pointerType);
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 
254 TEST(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 
354 class PtGAliasAnalysisTestOffsets final : public jlm::llvm::RvsdgTest
355 {
356  struct Outputs
357  {
358  jlm::rvsdg::Output * GlobalInt = {};
359  jlm::rvsdg::Output * GlobalLong = {};
360  jlm::rvsdg::Output * Func = {};
361  jlm::rvsdg::Output * P = {};
362  jlm::rvsdg::Output * Offset = {};
363  jlm::rvsdg::Output * IntWithOffset = {};
364  jlm::rvsdg::Output * LongWithOffset = {};
365  };
366 
367 public:
368  const Outputs &
369  GetOutputs() const noexcept
370  {
371  return Outputs_;
372  }
373 
374 private:
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 
444 TEST(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 }
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:1531
jlm::llvm
Global memory state passed between functions.
Definition: IpGraphToLlvmConverter.cpp:36
jlm::rvsdg::Outputs
static std::vector< Output * > Outputs(const Node &node, const size_t startIdx, const size_t size)
Definition: node.hpp:1077
jlm::rvsdg::outputs
static std::vector< jlm::rvsdg::Output * > outputs(const Node *node)
Definition: node.hpp:1058
Generated by doxygen 1.9.1