Jlm
MemoryStateEncoderTests.cpp
Go to the documentation of this file.
1 /*
2  * Copyright 2020 Nico Reißmann <nico.reissmann@gmail.com>
3  * See COPYING for terms of redistribution.
4  */
5 
6 #include <gtest/gtest.h>
7 
8 #include <jlm/llvm/ir/LambdaMemoryState.hpp>
9 #include <jlm/llvm/ir/operators/IntegerOperations.hpp>
10 #include <jlm/llvm/ir/operators/Load.hpp>
11 #include <jlm/llvm/ir/operators/MemoryStateOperations.hpp>
12 #include <jlm/llvm/ir/operators/operators.hpp>
13 #include <jlm/llvm/ir/operators/StdLibIntrinsicOperations.hpp>
14 #include <jlm/llvm/ir/operators/Store.hpp>
15 #include <jlm/llvm/opt/alias-analyses/AgnosticModRefSummarizer.hpp>
16 #include <jlm/llvm/opt/alias-analyses/Andersen.hpp>
17 #include <jlm/llvm/opt/alias-analyses/EliminatedModRefSummarizer.hpp>
18 #include <jlm/llvm/opt/alias-analyses/MemoryStateEncoder.hpp>
19 #include <jlm/llvm/opt/alias-analyses/RegionAwareModRefSummarizer.hpp>
20 #include <jlm/llvm/TestRvsdgs.hpp>
21 #include <jlm/rvsdg/view.hpp>
22 
23 template<class Analysis, class TModRefSummarizer>
24 static void
25 encodeStates(jlm::rvsdg::RvsdgModule & rvsdgModule)
26 {
27  static_assert(
28  std::is_base_of_v<jlm::llvm::aa::PointsToAnalysis, Analysis>,
29  "Analysis should be derived from PointsToAnalysis class.");
30 
31  static_assert(
32  std::is_base_of_v<jlm::llvm::aa::ModRefSummarizer, TModRefSummarizer>,
33  "TModRefSummarizer should be derived from ModRefSummarizer class.");
34 
35  jlm::rvsdg::view(&rvsdgModule.Rvsdg().GetRootRegion(), stdout);
36 
37  jlm::util::StatisticsCollector statisticsCollector;
38 
39  Analysis aliasAnalysis;
40  auto pointsToGraph = aliasAnalysis.Analyze(rvsdgModule, statisticsCollector);
41  std::cout << jlm::llvm::aa::PointsToGraph::dumpDot(*pointsToGraph);
42 
43  TModRefSummarizer summarizer;
44  auto modRefSummary =
45  summarizer.SummarizeModRefs(rvsdgModule, *pointsToGraph, statisticsCollector);
46 
47  jlm::llvm::aa::MemoryStateEncoder encoder;
48  std::cout << "run encoder\n";
49  encoder.Encode(rvsdgModule, *modRefSummary, statisticsCollector);
50  jlm::rvsdg::view(&rvsdgModule.Rvsdg().GetRootRegion(), stdout);
51 }
52 
53 template<class OP>
54 static bool
55 is(const jlm::rvsdg::Node & node, size_t numInputs, size_t numOutputs)
56 {
57  return jlm::rvsdg::is<OP>(&node) && node.ninputs() == numInputs && node.noutputs() == numOutputs;
58 }
59 
60 TEST(MemoryStateEncoderTests, storeTest1AndersenAgnostic)
61 {
62  using namespace jlm::llvm;
63 
64  StoreTest1 test;
65  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
66 
67  EXPECT_EQ(test.lambda->subregion()->numNodes(), 14u);
68 
69  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
70  *test.lambda->GetFunctionResults()[0]->origin());
71  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 6, 1));
72 
73  // Agnostic ModRef summaries lead to Join operations for all allocas
74  auto [aJoinNode, aJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
75  test.alloca_a->output(1)->SingleUser());
76  auto [bJoinNode, bJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
77  test.alloca_b->output(1)->SingleUser());
78  auto [cJoinNode, cJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
79  test.alloca_c->output(1)->SingleUser());
80  auto [dJoinNode, dJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
81  test.alloca_d->output(1)->SingleUser());
82  EXPECT_TRUE(aJoinOp && aJoinNode->output(0)->nusers() == 1);
83  EXPECT_TRUE(bJoinOp && bJoinNode->output(0)->nusers() == 1);
84  EXPECT_TRUE(cJoinOp && cJoinNode->output(0)->nusers() == 1);
85  EXPECT_TRUE(dJoinOp && dJoinNode->output(0)->nusers() == 1);
86 
87  // the d alloca is not used by any operation, and goes straight to the call exit
88  EXPECT_EQ(
89  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(dJoinNode->output(0)->SingleUser()),
90  lambdaExitMerge);
91 
92  auto storeD = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(cJoinNode->output(0)->SingleUser());
93  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeD, 3, 1));
94  EXPECT_EQ(storeD->input(0)->origin(), test.alloca_c->output(0));
95  EXPECT_EQ(storeD->input(1)->origin(), test.alloca_d->output(0));
96 
97  auto storeC = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(bJoinNode->output(0)->SingleUser());
98  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeC, 3, 1));
99  EXPECT_EQ(storeC->input(0)->origin(), test.alloca_b->output(0));
100  EXPECT_EQ(storeC->input(1)->origin(), test.alloca_c->output(0));
101 
102  auto storeB = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(aJoinNode->output(0)->SingleUser());
103  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeB, 3, 1));
104  EXPECT_EQ(storeB->input(0)->origin(), test.alloca_a->output(0));
105  EXPECT_EQ(storeB->input(1)->origin(), test.alloca_b->output(0));
106 }
107 
108 TEST(MemoryStateEncoderTests, storeTest1AndersenRegionAware)
109 {
110  using namespace jlm::llvm;
111 
112  StoreTest1 test;
113  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
114 
115  EXPECT_EQ(test.lambda->subregion()->numNodes(), 1u);
116 
117  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
118  *test.lambda->GetFunctionResults()[0]->origin());
119  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 0, 1));
120 }
121 
122 TEST(MemoryStateEncoderTests, storeTest2AndersenAgnostic)
123 {
124  using namespace jlm::llvm;
125 
126  StoreTest2 test;
127  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
128 
129  EXPECT_EQ(test.lambda->subregion()->numNodes(), 17u);
130 
131  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
132  *test.lambda->GetFunctionResults()[0]->origin());
133  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 7, 1));
134 
135  // Agnostic ModRef summaries lead to Join operations for all allocas
136  auto [aJoinNode, aJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
137  test.alloca_a->output(1)->SingleUser());
138  auto [bJoinNode, bJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
139  test.alloca_b->output(1)->SingleUser());
140  auto [xJoinNode, xJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
141  test.alloca_x->output(1)->SingleUser());
142  auto [yJoinNode, yJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
143  test.alloca_y->output(1)->SingleUser());
144  auto [pJoinNode, pJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
145  test.alloca_p->output(1)->SingleUser());
146  EXPECT_TRUE(aJoinOp && aJoinNode->output(0)->nusers() == 1);
147  EXPECT_TRUE(bJoinOp && bJoinNode->output(0)->nusers() == 1);
148  EXPECT_TRUE(xJoinOp && xJoinNode->output(0)->nusers() == 1);
149  EXPECT_TRUE(yJoinOp && yJoinNode->output(0)->nusers() == 1);
150  EXPECT_TRUE(pJoinOp && pJoinNode->output(0)->nusers() == 1);
151 
152  EXPECT_EQ(
153  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(aJoinNode->output(0)->SingleUser()),
154  lambdaExitMerge);
155  EXPECT_EQ(
156  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(bJoinNode->output(0)->SingleUser()),
157  lambdaExitMerge);
158 
159  auto storeA =
160  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(test.alloca_a->output(0)->SingleUser());
161  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeA, 3, 1));
162  EXPECT_EQ(storeA->input(0)->origin(), test.alloca_x->output(0));
163  EXPECT_EQ(storeA->input(1)->origin(), test.alloca_a->output(0));
164  EXPECT_TRUE(
165  jlm::rvsdg::IsOwnerNodeOperation<MemoryStateJoinOperation>(*storeA->input(2)->origin()));
166 
167  auto storeB =
168  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(test.alloca_b->output(0)->SingleUser());
169  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeB, 3, 1));
170  EXPECT_EQ(storeB->input(0)->origin(), test.alloca_y->output(0));
171  EXPECT_EQ(storeB->input(1)->origin(), test.alloca_b->output(0));
172  EXPECT_TRUE(
173  jlm::rvsdg::IsOwnerNodeOperation<MemoryStateJoinOperation>(*storeB->input(2)->origin()));
174 
175  auto storeX = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(pJoinNode->output(0)->SingleUser());
176  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeX, 3, 1));
177  EXPECT_EQ(storeX->input(0)->origin(), test.alloca_p->output(0));
178  EXPECT_EQ(storeX->input(1)->origin(), test.alloca_x->output(0));
179  EXPECT_TRUE(
180  jlm::rvsdg::IsOwnerNodeOperation<MemoryStateJoinOperation>(*storeX->input(2)->origin()));
181 
182  auto storeY = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(storeX->output(0)->SingleUser());
183  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeY, 3, 1));
184  EXPECT_EQ(storeY->input(0)->origin(), test.alloca_p->output(0));
185  EXPECT_EQ(storeY->input(1)->origin(), test.alloca_y->output(0));
186  EXPECT_EQ(storeY->input(2)->origin(), storeX->output(0));
187 }
188 
189 TEST(MemoryStateEncoderTests, storeTest2AndersenRegionAware)
190 {
191  using namespace jlm::llvm;
192 
193  StoreTest1 test;
194  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
195 
196  EXPECT_EQ(test.lambda->subregion()->numNodes(), 1u);
197 
198  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
199  *test.lambda->GetFunctionResults()[0]->origin());
200  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 0, 1));
201 }
202 
203 TEST(MemoryStateEncoderTests, loadTest1AndersenAgnostic)
204 {
205  using namespace jlm::llvm;
206 
207  LoadTest1 test;
208  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
209 
210  EXPECT_EQ(test.lambda->subregion()->numNodes(), 4u);
211 
212  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
213  *test.lambda->GetFunctionResults()[1]->origin());
214  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 2, 1));
215 
216  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
217  test.lambda->GetFunctionArguments()[1]->SingleUser());
218  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 2));
219 
220  auto loadA = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
221  *test.lambda->GetFunctionResults()[0]->origin());
222  auto loadX = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadA->input(0)->origin());
223 
224  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadA, 3, 3));
225  EXPECT_EQ(jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadA->input(1)->origin()), loadX);
226 
227  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadX, 3, 3));
228  EXPECT_EQ(loadX->input(0)->origin(), test.lambda->GetFunctionArguments()[0]);
229  EXPECT_EQ(
230  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadX->input(1)->origin()),
231  lambdaEntrySplit);
232 }
233 
234 TEST(MemoryStateEncoderTests, loadTest1AndersenRegionAware)
235 {
236  using namespace jlm::llvm;
237 
238  LoadTest1 test;
239  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
240 
241  EXPECT_EQ(test.lambda->subregion()->numNodes(), 4u);
242 
243  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
244  *test.lambda->GetFunctionResults()[1]->origin());
245  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 1, 1));
246 
247  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
248  test.lambda->GetFunctionArguments()[1]->SingleUser());
249  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 1));
250 
251  auto loadA = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
252  *test.lambda->GetFunctionResults()[0]->origin());
253  auto loadX = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadA->input(0)->origin());
254 
255  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadA, 2, 2));
256  EXPECT_EQ(jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadA->input(1)->origin()), loadX);
257 
258  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadX, 2, 2));
259  EXPECT_EQ(loadX->input(0)->origin(), test.lambda->GetFunctionArguments()[0]);
260  EXPECT_EQ(
261  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadX->input(1)->origin()),
262  lambdaEntrySplit);
263 }
264 
265 TEST(MemoryStateEncoderTests, loadTest2AndersenAgnostic)
266 {
267  using namespace jlm::llvm;
268  LoadTest2 test;
269  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
270 
271  EXPECT_EQ(test.lambda->subregion()->numNodes(), 19u);
272 
273  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
274  *test.lambda->GetFunctionResults()[0]->origin());
275  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 7, 1));
276 
277  // Agnostic ModRef summaries lead to Join operations for all allocas
278  auto [aJoinNode, aJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
279  test.alloca_a->output(1)->SingleUser());
280  auto [bJoinNode, bJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
281  test.alloca_b->output(1)->SingleUser());
282  auto [xJoinNode, xJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
283  test.alloca_x->output(1)->SingleUser());
284  auto [yJoinNode, yJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
285  test.alloca_y->output(1)->SingleUser());
286  auto [pJoinNode, pJoinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
287  test.alloca_p->output(1)->SingleUser());
288  EXPECT_TRUE(aJoinOp && aJoinNode->output(0)->nusers() == 1);
289  EXPECT_TRUE(bJoinOp && bJoinNode->output(0)->nusers() == 1);
290  EXPECT_TRUE(xJoinOp && xJoinNode->output(0)->nusers() == 1);
291  EXPECT_TRUE(yJoinOp && yJoinNode->output(0)->nusers() == 1);
292  EXPECT_TRUE(pJoinOp && pJoinNode->output(0)->nusers() == 1);
293 
294  EXPECT_EQ(
295  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(aJoinNode->output(0)->SingleUser()),
296  lambdaExitMerge);
297  EXPECT_EQ(
298  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(bJoinNode->output(0)->SingleUser()),
299  lambdaExitMerge);
300 
301  auto storeA =
302  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(test.alloca_a->output(0)->SingleUser());
303  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeA, 3, 1));
304  EXPECT_EQ(storeA->input(0)->origin(), test.alloca_x->output(0));
305  EXPECT_TRUE(
306  jlm::rvsdg::IsOwnerNodeOperation<MemoryStateJoinOperation>(*storeA->input(2)->origin()));
307 
308  auto storeB =
309  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(test.alloca_b->output(0)->SingleUser());
310  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeB, 3, 1));
311  EXPECT_EQ(storeB->input(0)->origin(), test.alloca_y->output(0));
312  EXPECT_TRUE(
313  jlm::rvsdg::IsOwnerNodeOperation<MemoryStateJoinOperation>(*storeB->input(2)->origin()));
314 
315  auto storeX = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(pJoinNode->output(0)->SingleUser());
316  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeX, 3, 1));
317  EXPECT_EQ(storeX->input(0)->origin(), test.alloca_p->output(0));
318  EXPECT_EQ(storeX->input(1)->origin(), test.alloca_x->output(0));
319  EXPECT_TRUE(
320  jlm::rvsdg::IsOwnerNodeOperation<MemoryStateJoinOperation>(*storeX->input(2)->origin()));
321 
322  auto load1 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(storeX->output(0)->SingleUser());
323  EXPECT_TRUE(is<LoadNonVolatileOperation>(*load1, 2, 2));
324  EXPECT_EQ(load1->input(0)->origin(), test.alloca_p->output(0));
325  EXPECT_EQ(load1->input(1)->origin(), storeX->output(0));
326 
327  auto load2 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(load1->output(0)->SingleUser());
328  EXPECT_TRUE(is<LoadNonVolatileOperation>(*load2, 2, 2));
329  EXPECT_EQ(load2->input(1)->origin(), storeA->output(0));
330 
331  auto storeY = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(load2->output(0)->SingleUser());
332  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeY, 3, 1));
333  EXPECT_EQ(storeY->input(0)->origin(), test.alloca_y->output(0));
334  EXPECT_EQ(storeY->input(2)->origin(), storeB->output(0));
335 }
336 
337 TEST(MemoryStateEncoderTests, loadTest2AndersenRegionAware)
338 {
339  using namespace jlm::llvm;
340 
341  LoadTest2 test;
342  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
343 
344  EXPECT_EQ(test.lambda->subregion()->numNodes(), 1u);
345 
346  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
347  *test.lambda->GetFunctionResults()[0]->origin());
348  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 0, 1));
349 }
350 
351 TEST(MemoryStateEncoderTests, loadFromUndefAndersenAgnostic)
352 {
353  using namespace jlm::llvm;
354 
355  LoadFromUndefTest test;
356  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
357  EXPECT_EQ(test.Lambda().subregion()->numNodes(), 4u);
358 
359  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
360  *test.Lambda().GetFunctionResults()[1]->origin());
361  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 2, 1));
362 
363  auto load = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
364  *test.Lambda().GetFunctionResults()[0]->origin());
365  EXPECT_TRUE(is<LoadNonVolatileOperation>(*load, 1, 1));
366 
367  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
368  test.Lambda().GetFunctionArguments()[0]->SingleUser());
369  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 2));
370 }
371 
372 TEST(MemoryStateEncoderTests, loadFromUndefAndersenRegionAware)
373 {
374  using namespace jlm::llvm;
375 
376  LoadFromUndefTest test;
377  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
378 
379  EXPECT_EQ(test.Lambda().subregion()->numNodes(), 3u);
380 
381  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
382  *test.Lambda().GetFunctionResults()[1]->origin());
383  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 0, 1));
384 
385  auto load = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
386  *test.Lambda().GetFunctionResults()[0]->origin());
387  EXPECT_TRUE(is<LoadNonVolatileOperation>(*load, 1, 1));
388 }
389 
390 TEST(MemoryStateEncoderTests, callTest1AndersenAgnostic)
391 {
392  using namespace jlm::llvm;
393 
394  CallTest1 test;
395  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
396 
397  /* validate f */
398  {
399  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
400  *test.lambda_f->GetFunctionArguments()[3]->Users().begin());
401  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
402  *test.lambda_f->GetFunctionResults()[2]->origin());
403  auto loadX = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
404  *test.lambda_f->GetFunctionArguments()[0]->Users().begin());
405  auto loadY = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
406  *test.lambda_f->GetFunctionArguments()[1]->Users().begin());
407 
408  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 7, 1));
409  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 7));
410 
411  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadX, 2, 2));
412  EXPECT_EQ(
413  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadX->input(1)->origin()),
414  lambdaEntrySplit);
415 
416  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadY, 2, 2));
417  EXPECT_EQ(
418  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadY->input(1)->origin()),
419  lambdaEntrySplit);
420  }
421 
422  /* validate g */
423  {
424  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
425  *test.lambda_g->GetFunctionArguments()[3]->Users().begin());
426  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
427  *test.lambda_g->GetFunctionResults()[2]->origin());
428  auto loadX = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
429  *test.lambda_g->GetFunctionArguments()[0]->Users().begin());
430  auto loadY = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
431  *test.lambda_g->GetFunctionArguments()[1]->Users().begin());
432 
433  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 7, 1));
434  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 7));
435 
436  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadX, 2, 2));
437  EXPECT_EQ(
438  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadX->input(1)->origin()),
439  lambdaEntrySplit);
440 
441  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadY, 2, 2));
442  EXPECT_TRUE(jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadY->input(1)->origin()) == loadX);
443  }
444 
445  /* validate h */
446  {
447  auto callEntryMerge =
448  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*test.CallF().input(4)->origin());
449  auto callExitSplit =
450  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(test.CallF().output(2)->SingleUser());
451 
452  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 7, 1));
453  EXPECT_TRUE(is<CallExitMemoryStateSplitOperation>(*callExitSplit, 1, 7));
454 
455  callEntryMerge =
456  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*test.CallG().input(4)->origin());
457  callExitSplit =
458  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(test.CallG().output(2)->SingleUser());
459 
460  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 7, 1));
461  EXPECT_TRUE(is<CallExitMemoryStateSplitOperation>(*callExitSplit, 1, 7));
462  }
463 }
464 
465 TEST(MemoryStateEncoderTests, callTest1AndersenRegionAware)
466 {
467  using namespace jlm::llvm;
468 
469  CallTest1 test;
470  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
471 
472  /* validate f */
473  {
474  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
475  test.lambda_f->GetFunctionArguments()[3]->SingleUser());
476  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
477  *test.lambda_f->GetFunctionResults()[2]->origin());
478  auto loadX = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
479  test.lambda_f->GetFunctionArguments()[0]->SingleUser());
480  auto loadY = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
481  test.lambda_f->GetFunctionArguments()[1]->SingleUser());
482 
483  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 2, 1));
484  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 2));
485 
486  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadX, 2, 2));
487  EXPECT_EQ(
488  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadX->input(1)->origin()),
489  lambdaEntrySplit);
490 
491  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadY, 2, 2));
492  EXPECT_EQ(
493  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadY->input(1)->origin()),
494  lambdaEntrySplit);
495  }
496 
497  /* validate g */
498  {
499  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
500  test.lambda_g->GetFunctionArguments()[3]->SingleUser());
501  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
502  *test.lambda_g->GetFunctionResults()[2]->origin());
503  auto loadX = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
504  test.lambda_g->GetFunctionArguments()[0]->SingleUser());
505  auto loadY = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
506  test.lambda_g->GetFunctionArguments()[1]->SingleUser());
507 
508  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 1, 1));
509  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 1));
510 
511  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadX, 2, 2));
512  EXPECT_EQ(
513  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadX->input(1)->origin()),
514  lambdaEntrySplit);
515 
516  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadY, 2, 2));
517  EXPECT_EQ(jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadY->input(1)->origin()), loadX);
518  }
519 
520  /* validate h */
521  {
522  auto callEntryMerge =
523  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*test.CallF().input(4)->origin());
524  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 2, 1));
525  // There is no call exit split, as it has been removed by dead node elimination
526  EXPECT_EQ(test.CallF().output(2)->nusers(), 0u);
527 
528  callEntryMerge =
529  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*test.CallG().input(4)->origin());
530  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 1, 1));
531  EXPECT_EQ(test.CallG().output(2)->nusers(), 0u);
532  }
533 }
534 
535 TEST(MemoryStateEncoderTests, callTest2AndersenAgnostic)
536 {
537  using namespace jlm::llvm;
538  CallTest2 test;
539  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
540 
541  /* validate create function */
542  {
543  EXPECT_EQ(test.lambda_create->subregion()->numNodes(), 7u);
544 
545  auto stateJoin = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
546  MallocOperation::memoryStateOutput(*test.malloc).SingleUser());
547  EXPECT_TRUE(is<MemoryStateJoinOperation>(*stateJoin, 2, 1));
548 
549  auto lambdaEntrySplit =
550  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*stateJoin->input(1)->origin());
551  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 5));
552 
553  auto lambdaExitMerge =
554  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(stateJoin->output(0)->SingleUser());
555  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 5, 1));
556 
557  auto mallocStateLambdaEntryIndex = stateJoin->input(1)->origin()->index();
558  auto mallocStateLambdaExitIndex = stateJoin->output(0)->SingleUser().index();
559  EXPECT_EQ(mallocStateLambdaEntryIndex, mallocStateLambdaExitIndex);
560  }
561 
562  /* validate destroy function */
563  {
564  EXPECT_EQ(test.lambda_destroy->subregion()->numNodes(), 4u);
565  }
566 
567  /* validate test function */
568  {
569  EXPECT_EQ(test.lambda_test->subregion()->numNodes(), 16u);
570  }
571 }
572 
573 TEST(MemoryStateEncoderTests, callTest2AndersenRegionAware)
574 {
575  using namespace jlm::llvm;
576 
577  CallTest2 test;
578  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
579 
580  /* validate create function */
581  {
582  EXPECT_EQ(test.lambda_create->subregion()->numNodes(), 7u);
583 
584  auto stateJoin = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
585  MallocOperation::memoryStateOutput(*test.malloc).SingleUser());
586  EXPECT_TRUE(is<MemoryStateJoinOperation>(*stateJoin, 2, 1));
587 
588  auto lambdaEntrySplit =
589  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*stateJoin->input(1)->origin());
590  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 1));
591 
592  auto lambdaExitMerge =
593  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(stateJoin->output(0)->SingleUser());
594  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 1, 1));
595 
596  auto mallocStateLambdaEntryIndex = stateJoin->input(1)->origin()->index();
597  auto mallocStateLambdaExitIndex = stateJoin->output(0)->SingleUser().index();
598  EXPECT_EQ(mallocStateLambdaEntryIndex, mallocStateLambdaExitIndex);
599  }
600 
601  /* validate destroy function */
602  {
603  EXPECT_EQ(test.lambda_destroy->subregion()->numNodes(), 4u);
604  }
605 
606  /* validate test function */
607  {
608  EXPECT_EQ(test.lambda_test->subregion()->numNodes(), 16u);
609  }
610 }
611 
612 TEST(MemoryStateEncoderTests, indirectCallTest1AndersenAgnostic)
613 {
614  using namespace jlm::llvm;
615 
616  IndirectCallTest1 test;
617  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
618 
619  /* validate indcall function */
620  {
621  EXPECT_EQ(test.GetLambdaIndcall().subregion()->numNodes(), 6u);
622 
623  auto lambda_exit_mux = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
624  *test.GetLambdaIndcall().GetFunctionResults()[2]->origin());
625  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambda_exit_mux, 5, 1));
626 
627  auto call_exit_mux =
628  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambda_exit_mux->input(0)->origin());
629  EXPECT_TRUE(is<CallExitMemoryStateSplitOperation>(*call_exit_mux, 1, 5));
630 
631  auto call = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call_exit_mux->input(0)->origin());
632  EXPECT_TRUE(is<CallOperation>(*call, 3, 3));
633 
634  auto call_entry_mux = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call->input(2)->origin());
635  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*call_entry_mux, 5, 1));
636 
637  auto lambda_entry_mux =
638  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call_entry_mux->input(2)->origin());
639  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambda_entry_mux, 1, 5));
640  }
641 
642  /* validate test function */
643  {
644  EXPECT_EQ(test.GetLambdaTest().subregion()->numNodes(), 9u);
645 
646  auto lambda_exit_mux = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
647  *test.GetLambdaTest().GetFunctionResults()[2]->origin());
648  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambda_exit_mux, 5, 1));
649 
650  auto call_exit_mux =
651  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambda_exit_mux->input(0)->origin());
652  EXPECT_TRUE(is<CallExitMemoryStateSplitOperation>(*call_exit_mux, 1, 5));
653 
654  auto call = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call_exit_mux->input(0)->origin());
655  EXPECT_TRUE(is<CallOperation>(*call, 4, 3));
656 
657  auto call_entry_mux = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call->input(3)->origin());
658  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*call_entry_mux, 5, 1));
659 
660  call_exit_mux =
661  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call_entry_mux->input(0)->origin());
662  EXPECT_TRUE(is<CallExitMemoryStateSplitOperation>(*call_exit_mux, 1, 5));
663 
664  call = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call_exit_mux->input(0)->origin());
665  EXPECT_TRUE(is<CallOperation>(*call, 4, 3));
666 
667  call_entry_mux = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call->input(3)->origin());
668  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*call_entry_mux, 5, 1));
669 
670  auto lambda_entry_mux =
671  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call_entry_mux->input(2)->origin());
672  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambda_entry_mux, 1, 5));
673  }
674 }
675 
676 TEST(MemoryStateEncoderTests, indirectCallTest1AndersenRegionAware)
677 {
678  using namespace jlm::llvm;
679 
680  IndirectCallTest1 test;
681  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
682 
683  /* validate indcall function */
684  {
685  EXPECT_EQ(test.GetLambdaIndcall().subregion()->numNodes(), 4u);
686 
687  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
688  *test.GetLambdaIndcall().GetFunctionResults()[2]->origin());
689  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 0, 1));
690 
691  auto call = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
692  *test.GetLambdaIndcall().GetFunctionResults()[0]->origin());
693  EXPECT_TRUE(is<CallOperation>(*call, 3, 3));
694 
695  auto callEntryMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call->input(2)->origin());
696  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 0, 1));
697  }
698 
699  /* validate test function */
700  {
701  EXPECT_EQ(test.GetLambdaTest().subregion()->numNodes(), 6u);
702 
703  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
704  *test.GetLambdaTest().GetFunctionResults()[2]->origin());
705  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 0, 1));
706 
707  auto add = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
708  *test.GetLambdaTest().GetFunctionResults()[0]->origin());
709  EXPECT_TRUE(is<jlm::rvsdg::BinaryOperation>(*add, 2, 1));
710 
711  auto call = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*add->input(0)->origin());
712  EXPECT_TRUE(is<CallOperation>(*call, 4, 3));
713 
714  auto callEntryMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call->input(3)->origin());
715  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 0, 1));
716 
717  call = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*add->input(1)->origin());
718  EXPECT_TRUE(is<CallOperation>(*call, 4, 3));
719 
720  callEntryMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call->input(3)->origin());
721  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 0, 1));
722  }
723 }
724 
725 TEST(MemoryStateEncoderTests, indirectCallTest2AndersenAgnostic)
726 {
727  using namespace jlm::llvm;
728 
729  IndirectCallTest2 test;
730  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
731 
732  // validate function three()
733  {
734  EXPECT_EQ(test.GetLambdaThree().subregion()->numNodes(), 3u);
735 
736  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
737  *test.GetLambdaThree().GetFunctionResults()[2]->origin());
738  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 13, 1));
739 
740  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
741  test.GetLambdaThree().GetFunctionArguments()[1]->SingleUser());
742  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 13));
743  }
744 
745  // validate function four()
746  {
747  EXPECT_EQ(test.GetLambdaFour().subregion()->numNodes(), 3u);
748 
749  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
750  *test.GetLambdaFour().GetFunctionResults()[2]->origin());
751  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 13, 1));
752 
753  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
754  test.GetLambdaFour().GetFunctionArguments()[1]->SingleUser());
755  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 13));
756  }
757 
758  // validate function i()
759  {
760  EXPECT_EQ(test.GetLambdaI().subregion()->numNodes(), 6u);
761 
762  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
763  *test.GetLambdaI().GetFunctionResults()[2]->origin());
764  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 13, 1));
765 
766  auto callExitSplit =
767  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambdaExitMerge->input(0)->origin());
768  EXPECT_TRUE(is<CallExitMemoryStateSplitOperation>(*callExitSplit, 1, 13));
769 
770  auto callEntryMerge =
771  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*test.GetIndirectCall().input(2)->origin());
772  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 13, 1));
773 
774  auto lambdaEntrySplit =
775  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*callEntryMerge->input(0)->origin());
776  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 13));
777  }
778 }
779 
780 TEST(MemoryStateEncoderTests, indirectCallTest2AndersenRegionAware)
781 {
782  using namespace jlm::llvm;
783 
784  IndirectCallTest2 test;
785  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
786 
787  // validate function three()
788  {
789  EXPECT_EQ(test.GetLambdaThree().subregion()->numNodes(), 2u);
790 
791  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
792  *test.GetLambdaThree().GetFunctionResults()[2]->origin());
793  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 0, 1));
794  }
795 
796  // validate function four()
797  {
798  EXPECT_EQ(test.GetLambdaFour().subregion()->numNodes(), 2u);
799 
800  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
801  *test.GetLambdaFour().GetFunctionResults()[2]->origin());
802  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 0, 1));
803  }
804 
805  // validate function i()
806  {
807  EXPECT_EQ(test.GetLambdaI().subregion()->numNodes(), 4u);
808 
809  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
810  *test.GetLambdaI().GetFunctionResults()[2]->origin());
811  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 0, 1));
812 
813  auto callEntryMerge =
814  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*test.GetIndirectCall().input(2)->origin());
815  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 0, 1));
816  }
817 
818  // validate function x()
819  {
820  EXPECT_EQ(test.GetLambdaX().subregion()->numNodes(), 7u);
821 
822  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
823  *test.GetLambdaX().GetFunctionResults()[2]->origin());
824  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 2, 1));
825 
826  auto callEntryMerge =
827  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*test.GetCallIWithThree().input(3)->origin());
828  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 0, 1));
829  }
830 
831  // validate function y()
832  {
833  EXPECT_EQ(test.GetLambdaY().subregion()->numNodes(), 7u);
834 
835  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
836  *test.GetLambdaY().GetFunctionResults()[2]->origin());
837  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 1, 1));
838 
839  auto callEntryMerge =
840  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*test.GetCallIWithFour().input(3)->origin());
841  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 0, 1));
842  }
843 
844  // validate function test()
845  {
846  EXPECT_EQ(test.GetLambdaTest().subregion()->numNodes(), 14u);
847 
848  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
849  *test.GetLambdaTest().GetFunctionResults()[2]->origin());
850  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 2, 1));
851 
852  auto loadG1 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
853  test.GetLambdaTest().GetContextVars()[2].inner->SingleUser());
854  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadG1, 2, 2));
855 
856  auto loadG2 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
857  test.GetLambdaTest().GetContextVars()[3].inner->SingleUser());
858  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadG2, 2, 2));
859 
860  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
861  test.GetLambdaTest().GetFunctionArguments()[1]->SingleUser());
862  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 2));
863  }
864 
865  // validate function test2()
866  {
867  EXPECT_EQ(test.GetLambdaTest2().subregion()->numNodes(), 5u);
868 
869  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
870  *test.GetLambdaTest2().GetFunctionResults()[2]->origin());
871  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 0, 1));
872 
873  // The entry memory state is unused
874  EXPECT_EQ(test.GetLambdaTest2().GetFunctionArguments()[1]->nusers(), 0u);
875  }
876 }
877 
878 TEST(MemoryStateEncoderTests, gammaTestAndersenAgnostic)
879 {
880  using namespace jlm::llvm;
881 
882  GammaTest test;
883  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
884 
885  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
886  *test.lambda->GetFunctionResults()[1]->origin());
887  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 2, 1));
888 
889  auto loadTmp2 =
890  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambdaExitMerge->input(0)->origin());
891  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadTmp2, 3, 3));
892 
893  auto loadTmp1 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadTmp2->input(1)->origin());
894  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadTmp1, 3, 3));
895 
896  auto gamma = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadTmp1->input(1)->origin());
897  EXPECT_EQ(gamma, test.gamma);
898 }
899 
900 TEST(MemoryStateEncoderTests, gammaTestAndersenRegionAware)
901 {
902  using namespace jlm::llvm;
903 
904  GammaTest test;
905  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
906 
907  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
908  *test.lambda->GetFunctionResults()[1]->origin());
909  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 1, 1));
910 
911  auto loadTmp2 =
912  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambdaExitMerge->input(0)->origin());
913  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadTmp2, 2, 2));
914 
915  auto loadTmp1 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadTmp2->input(1)->origin());
916  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadTmp1, 2, 2));
917 
918  auto lambdaEntrySplit =
919  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadTmp1->input(1)->origin());
920  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 1));
921 }
922 
923 TEST(MemoryStateEncoderTests, thetaTestAndersenAgnostic)
924 {
925  using namespace jlm::llvm;
926 
927  ThetaTest test;
928  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
929 
930  EXPECT_EQ(test.lambda->subregion()->numNodes(), 4u);
931 
932  auto lambda_exit_mux = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
933  *test.lambda->GetFunctionResults()[0]->origin());
934  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambda_exit_mux, 2, 1));
935 
936  auto thetaOutput = lambda_exit_mux->input(0)->origin();
937  auto theta = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::ThetaNode>(*thetaOutput);
938  EXPECT_EQ(theta, test.theta);
939 
940  auto loopvar = theta->MapOutputLoopVar(*thetaOutput);
941  auto storeStateOutput = loopvar.post->origin();
942  auto store = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeStateOutput);
943  EXPECT_TRUE(is<StoreNonVolatileOperation>(*store, 4, 2));
944  EXPECT_EQ(store->input(storeStateOutput->index() + 2)->origin(), loopvar.pre);
945 
946  auto lambda_entry_mux = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loopvar.input->origin());
947  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambda_entry_mux, 1, 2));
948 }
949 
950 TEST(MemoryStateEncoderTests, thetaTestAndersenRegionAware)
951 {
952  using namespace jlm::llvm;
953 
954  ThetaTest test;
955  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
956 
957  EXPECT_EQ(test.lambda->subregion()->numNodes(), 4u);
958 
959  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
960  *test.lambda->GetFunctionResults()[0]->origin());
961  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 1, 1));
962 
963  auto thetaOutput = lambdaExitMerge->input(0)->origin();
964  auto theta = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::ThetaNode>(*thetaOutput);
965  EXPECT_EQ(theta, test.theta);
966  auto loopvar = theta->MapOutputLoopVar(*thetaOutput);
967 
968  auto storeStateOutput = loopvar.post->origin();
969  auto store = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeStateOutput);
970  EXPECT_TRUE(is<StoreNonVolatileOperation>(*store, 3, 1));
971  EXPECT_EQ(store->input(storeStateOutput->index() + 2)->origin(), loopvar.pre);
972 
973  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loopvar.input->origin());
974  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 1));
975 }
976 
977 TEST(MemoryStateEncoderTests, deltaTest1AndersenAgnostic)
978 {
979  using namespace jlm::llvm;
980 
981  DeltaTest1 test;
982  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
983 
984  EXPECT_EQ(test.lambda_h->subregion()->numNodes(), 7u);
985 
986  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
987  test.lambda_h->GetFunctionArguments()[1]->SingleUser());
988  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 4));
989 
990  auto storeF =
991  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(test.constantFive->output(0)->SingleUser());
992  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeF, 3, 1));
993  EXPECT_EQ(
994  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeF->input(2)->origin()),
995  lambdaEntrySplit);
996 
997  auto deltaStateIndex = storeF->input(2)->origin()->index();
998 
999  auto loadF = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1000  test.lambda_g->GetFunctionArguments()[0]->SingleUser());
1001  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadF, 2, 2));
1002  EXPECT_EQ(loadF->input(1)->origin()->index(), deltaStateIndex);
1003 }
1004 
1005 TEST(MemoryStateEncoderTests, deltaTest1AndersenRegionAware)
1006 {
1007  using namespace jlm::llvm;
1008 
1009  DeltaTest1 test;
1010  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
1011 
1012  EXPECT_EQ(test.lambda_h->subregion()->numNodes(), 7u);
1013 
1014  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1015  test.lambda_h->GetFunctionArguments()[1]->SingleUser());
1016  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 1));
1017 
1018  auto storeF =
1019  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(test.constantFive->output(0)->SingleUser());
1020  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeF, 3, 1));
1021  EXPECT_EQ(
1022  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeF->input(2)->origin()),
1023  lambdaEntrySplit);
1024 
1025  auto deltaStateIndex = storeF->input(2)->origin()->index();
1026 
1027  auto loadF = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1028  test.lambda_g->GetFunctionArguments()[0]->SingleUser());
1029  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadF, 2, 2));
1030  EXPECT_EQ(loadF->input(1)->origin()->index(), deltaStateIndex);
1031 }
1032 
1033 TEST(MemoryStateEncoderTests, deltaTest2AndersenAgnostic)
1034 {
1035  using namespace jlm::llvm;
1036 
1037  DeltaTest2 test;
1038  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
1039 
1040  EXPECT_EQ(test.lambda_f2->subregion()->numNodes(), 9u);
1041 
1042  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1043  test.lambda_f2->GetFunctionArguments()[1]->SingleUser());
1044  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 5));
1045 
1046  auto storeD1InF2 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1047  test.lambda_f2->GetContextVars()[0].inner->SingleUser());
1048  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeD1InF2, 3, 1));
1049  EXPECT_EQ(
1050  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeD1InF2->input(2)->origin()),
1051  lambdaEntrySplit);
1052 
1053  auto d1StateIndex = storeD1InF2->input(2)->origin()->index();
1054 
1055  auto storeD1InF1 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1056  test.lambda_f1->GetContextVars()[0].inner->SingleUser());
1057  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeD1InF1, 3, 1));
1058 
1059  EXPECT_EQ(d1StateIndex, storeD1InF1->input(2)->origin()->index());
1060 
1061  auto storeD2InF2 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1062  test.lambda_f2->GetContextVars()[1].inner->SingleUser());
1063  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeD1InF2, 3, 1));
1064 
1065  EXPECT_NE(d1StateIndex, storeD2InF2->input(2)->origin()->index());
1066 }
1067 
1068 TEST(MemoryStateEncoderTests, deltaTest2AndersenRegionAware)
1069 {
1070  using namespace jlm::llvm;
1071 
1072  DeltaTest2 test;
1073  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
1074 
1075  /* Validate f1() */
1076  {
1077  EXPECT_EQ(test.lambda_f1->subregion()->numNodes(), 4u);
1078 
1079  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1080  *test.lambda_f1->GetFunctionResults()[1]->origin());
1081  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 1, 1));
1082 
1083  auto storeNode =
1084  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambdaExitMerge->input(0)->origin());
1085  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeNode, 3, 1));
1086 
1087  auto lambdaEntrySplit =
1088  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeNode->input(2)->origin());
1089  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 1));
1090  }
1091 
1092  /* Validate f2() */
1093  {
1094  EXPECT_EQ(test.lambda_f2->subregion()->numNodes(), 9u);
1095 
1096  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1097  test.lambda_f2->GetFunctionArguments()[1]->SingleUser());
1098  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 2));
1099 
1100  auto storeD1 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1101  test.lambda_f2->GetContextVars()[0].inner->SingleUser());
1102  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeD1, 3, 1));
1103  EXPECT_EQ(
1104  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeD1->input(2)->origin()),
1105  lambdaEntrySplit);
1106 
1107  auto storeD2 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1108  test.lambda_f2->GetContextVars()[1].inner->SingleUser());
1109  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeD2, 3, 1));
1110  EXPECT_EQ(
1111  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeD2->input(2)->origin()),
1112  lambdaEntrySplit);
1113 
1114  auto callEntryMerge =
1115  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(storeD1->output(0)->SingleUser());
1116  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 1, 1));
1117 
1118  auto callF1 =
1119  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(callEntryMerge->output(0)->SingleUser());
1120  EXPECT_TRUE(is<CallOperation>(*callF1, 3, 2));
1121 
1122  auto callExitSplit =
1123  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(callF1->output(1)->SingleUser());
1124  EXPECT_TRUE(is<CallExitMemoryStateSplitOperation>(*callExitSplit, 1, 1));
1125 
1126  auto lambdaExitMerge =
1127  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(callExitSplit->output(0)->SingleUser());
1128  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 2, 1));
1129  }
1130 }
1131 
1132 TEST(MemoryStateEncoderTests, deltaTest3AndersenAgnostic)
1133 {
1134  using namespace jlm::llvm;
1135 
1136  DeltaTest3 test;
1137  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
1138 
1139  /* validate f() */
1140  {
1141  EXPECT_EQ(test.LambdaF().subregion()->numNodes(), 6u);
1142 
1143  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1144  *test.LambdaF().GetFunctionResults()[2]->origin());
1145  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 5, 1));
1146 
1147  auto truncNode = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1148  *test.LambdaF().GetFunctionResults()[0]->origin());
1149  EXPECT_TRUE(is<TruncOperation>(*truncNode, 1, 1));
1150 
1151  auto loadG1Node = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*truncNode->input(0)->origin());
1152  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadG1Node, 2, 2));
1153 
1154  auto lambdaEntrySplit =
1155  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadG1Node->input(1)->origin());
1156  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 5));
1157 
1158  jlm::rvsdg::Node * storeG2Node = nullptr;
1159  for (size_t n = 0; n < lambdaExitMerge->ninputs(); n++)
1160  {
1161  auto input = lambdaExitMerge->input(n);
1162  auto node = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*input->origin());
1163  if (is<StoreNonVolatileOperation>(node))
1164  {
1165  storeG2Node = node;
1166  break;
1167  }
1168  }
1169  EXPECT_NE(storeG2Node, nullptr);
1170 
1171  auto loadG2Node =
1172  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeG2Node->input(2)->origin());
1173  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadG2Node, 2, 2));
1174 
1175  auto node = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadG2Node->input(1)->origin());
1176  EXPECT_EQ(node, lambdaEntrySplit);
1177  }
1178 }
1179 
1180 TEST(MemoryStateEncoderTests, deltaTest3AndersenRegionAware)
1181 {
1182  using namespace jlm::llvm;
1183 
1184  DeltaTest3 test;
1185  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
1186 
1187  /* validate f() */
1188  {
1189  EXPECT_EQ(test.LambdaF().subregion()->numNodes(), 6u);
1190 
1191  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1192  *test.LambdaF().GetFunctionResults()[2]->origin());
1193  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 2, 1));
1194 
1195  auto truncNode = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1196  *test.LambdaF().GetFunctionResults()[0]->origin());
1197  EXPECT_TRUE(is<TruncOperation>(*truncNode, 1, 1));
1198 
1199  auto loadG1Node = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*truncNode->input(0)->origin());
1200  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadG1Node, 2, 2));
1201 
1202  auto lambdaEntrySplit =
1203  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadG1Node->input(1)->origin());
1204  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 2));
1205 
1206  jlm::rvsdg::Node * storeG2Node = nullptr;
1207  for (size_t n = 0; n < lambdaExitMerge->ninputs(); n++)
1208  {
1209  auto input = lambdaExitMerge->input(n);
1210  auto node = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*input->origin());
1211  if (is<StoreNonVolatileOperation>(node))
1212  {
1213  storeG2Node = node;
1214  break;
1215  }
1216  }
1217  EXPECT_NE(storeG2Node, nullptr);
1218 
1219  auto loadG2Node =
1220  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeG2Node->input(2)->origin());
1221  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadG2Node, 2, 2));
1222 
1223  auto node = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*loadG2Node->input(1)->origin());
1224  EXPECT_EQ(node, lambdaEntrySplit);
1225  }
1226 }
1227 
1228 TEST(MemoryStateEncoderTests, importTestAndersenAgnostic)
1229 {
1230  using namespace jlm::llvm;
1231 
1232  ImportTest test;
1233  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
1234 
1235  EXPECT_EQ(test.lambda_f2->subregion()->numNodes(), 9u);
1236 
1237  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1238  test.lambda_f2->GetFunctionArguments()[1]->SingleUser());
1239  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 5));
1240 
1241  auto storeD1InF2 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1242  test.lambda_f2->GetContextVars()[0].inner->SingleUser());
1243  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeD1InF2, 3, 1));
1244  EXPECT_EQ(
1245  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeD1InF2->input(2)->origin()),
1246  lambdaEntrySplit);
1247 
1248  auto d1StateIndex = storeD1InF2->input(2)->origin()->index();
1249 
1250  auto storeD1InF1 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1251  test.lambda_f1->GetContextVars()[0].inner->SingleUser());
1252  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeD1InF1, 3, 1));
1253 
1254  EXPECT_EQ(d1StateIndex, storeD1InF1->input(2)->origin()->index());
1255 
1256  auto storeD2InF2 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1257  test.lambda_f2->GetContextVars()[1].inner->SingleUser());
1258  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeD1InF2, 3, 1));
1259 
1260  EXPECT_NE(d1StateIndex, storeD2InF2->input(2)->origin()->index());
1261 }
1262 
1263 TEST(MemoryStateEncoderTests, importTestAndersenRegionAware)
1264 {
1265  using namespace jlm::llvm;
1266 
1267  ImportTest test;
1268  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
1269 
1270  /* Validate f1() */
1271  {
1272  EXPECT_EQ(test.lambda_f1->subregion()->numNodes(), 4u);
1273 
1274  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1275  *test.lambda_f1->GetFunctionResults()[1]->origin());
1276  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 1, 1));
1277 
1278  auto storeNode =
1279  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambdaExitMerge->input(0)->origin());
1280  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeNode, 3, 1));
1281 
1282  auto lambdaEntrySplit =
1283  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeNode->input(2)->origin());
1284  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 1));
1285  }
1286 
1287  /* Validate f2() */
1288  {
1289  EXPECT_EQ(test.lambda_f2->subregion()->numNodes(), 9u);
1290 
1291  auto lambdaEntrySplit = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1292  test.lambda_f2->GetFunctionArguments()[1]->SingleUser());
1293  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 2));
1294 
1295  auto storeD1 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1296  test.lambda_f2->GetContextVars()[0].inner->SingleUser());
1297  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeD1, 3, 1));
1298  EXPECT_EQ(
1299  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeD1->input(2)->origin()),
1300  lambdaEntrySplit);
1301 
1302  auto storeD2 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1303  test.lambda_f2->GetContextVars()[1].inner->SingleUser());
1304  EXPECT_TRUE(is<StoreNonVolatileOperation>(*storeD2, 3, 1));
1305  EXPECT_EQ(
1306  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*storeD2->input(2)->origin()),
1307  lambdaEntrySplit);
1308 
1309  auto callEntryMerge =
1310  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(storeD1->output(0)->SingleUser());
1311  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 1, 1));
1312 
1313  auto callF1 =
1314  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(callEntryMerge->output(0)->SingleUser());
1315  EXPECT_TRUE(is<CallOperation>(*callF1, 3, 2));
1316 
1317  auto callExitSplit =
1318  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(callF1->output(1)->SingleUser());
1319  EXPECT_TRUE(is<CallExitMemoryStateSplitOperation>(*callExitSplit, 1, 1));
1320 
1321  auto lambdaExitMerge =
1322  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(callExitSplit->output(0)->SingleUser());
1323  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 2, 1));
1324  }
1325 }
1326 
1327 TEST(MemoryStateEncoderTests, phiTest1AndersenAgnostic)
1328 {
1329  using namespace jlm::llvm;
1330 
1331  PhiTest1 test;
1332  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
1333 
1334  auto [joinNode, joinOp] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
1335  test.alloca->output(1)->SingleUser());
1336  EXPECT_TRUE(joinNode && joinOp);
1337  auto arrayStateIndex = joinNode->output(0)->SingleUser().index();
1338 
1339  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1340  *test.lambda_fib->GetFunctionResults()[1]->origin());
1341  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 4, 1));
1342 
1343  auto store = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1344  *lambdaExitMerge->input(arrayStateIndex)->origin());
1345  EXPECT_TRUE(is<StoreNonVolatileOperation>(*store, 3, 1));
1346 
1347  auto gamma = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*store->input(2)->origin());
1348  EXPECT_EQ(gamma, test.gamma);
1349 
1350  auto gammaStateIndex = store->input(2)->origin()->index();
1351 
1352  auto load1 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1353  *test.gamma->GetExitVars()[gammaStateIndex].branchResult[0]->origin());
1354  EXPECT_TRUE(is<LoadNonVolatileOperation>(*load1, 2, 2));
1355 
1356  auto load2 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*load1->input(1)->origin());
1357  EXPECT_TRUE(is<LoadNonVolatileOperation>(*load2, 2, 2));
1358 
1359  EXPECT_EQ(load2->input(1)->origin()->index(), arrayStateIndex);
1360 }
1361 
1362 TEST(MemoryStateEncoderTests, phiTest1AndersenRegionAware)
1363 {
1364  using namespace jlm::llvm;
1365 
1366  PhiTest1 test;
1367  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
1368 
1369  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1370  *test.lambda_fib->GetFunctionResults()[1]->origin());
1371  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 1, 1));
1372 
1373  auto gamma = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1374  *test.lambda_fib->GetFunctionResults()[0]->origin());
1375  EXPECT_EQ(gamma, test.gamma);
1376 
1377  // In the region aware, we know that the alloca is non-reentrant, so there is no Join
1378  auto [node, op] = jlm::rvsdg::TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(
1379  test.alloca->output(1)->SingleUser());
1380  EXPECT_EQ(op, nullptr);
1381 }
1382 
1383 TEST(MemoryStateEncoderTests, memCpyTestAndersenAgnostic)
1384 {
1385  using namespace jlm::llvm;
1386 
1387  MemcpyTest test;
1388  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
1389 
1390  /*
1391  * Validate function f
1392  */
1393  {
1394  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1395  *test.LambdaF().GetFunctionResults()[2]->origin());
1396  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 5, 1));
1397 
1398  auto load = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1399  *test.LambdaF().GetFunctionResults()[0]->origin());
1400  EXPECT_TRUE(is<LoadNonVolatileOperation>(*load, 2, 2));
1401 
1402  auto store = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*load->input(1)->origin());
1403  EXPECT_TRUE(is<StoreNonVolatileOperation>(*store, 3, 1));
1404 
1405  auto lambdaEntrySplit =
1406  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*store->input(2)->origin());
1407  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 5));
1408  }
1409 
1410  /*
1411  * Validate function g
1412  */
1413  {
1414  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1415  *test.LambdaG().GetFunctionResults()[2]->origin());
1416  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 5, 1));
1417 
1418  auto callExitSplit =
1419  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambdaExitMerge->input(0)->origin());
1420  EXPECT_TRUE(is<CallExitMemoryStateSplitOperation>(*callExitSplit, 1, 5));
1421 
1422  auto call = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*callExitSplit->input(0)->origin());
1423  EXPECT_TRUE(is<CallOperation>(*call, 3, 3));
1424 
1425  auto callEntryMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*call->input(2)->origin());
1426  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 5, 1));
1427 
1428  jlm::rvsdg::Node * memcpy = nullptr;
1429  for (size_t n = 0; n < callEntryMerge->ninputs(); n++)
1430  {
1431  auto node =
1432  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*callEntryMerge->input(n)->origin());
1433  if (is<MemCpyNonVolatileOperation>(node))
1434  memcpy = node;
1435  }
1436  EXPECT_NE(memcpy, nullptr);
1437  EXPECT_TRUE(is<MemCpyNonVolatileOperation>(*memcpy, 5, 2));
1438 
1439  auto lambdaEntrySplit =
1440  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*memcpy->input(4)->origin());
1441  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 5));
1442  }
1443 }
1444 
1445 TEST(MemoryStateEncoderTests, memCpyAndersenRegionAware)
1446 {
1447  using namespace jlm::llvm;
1448 
1449  MemcpyTest test;
1450  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(test.module());
1451 
1452  /*
1453  * Validate function f
1454  */
1455  {
1456  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1457  *test.LambdaF().GetFunctionResults()[2]->origin());
1458  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 1, 1));
1459 
1460  auto load = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1461  *test.LambdaF().GetFunctionResults()[0]->origin());
1462  EXPECT_TRUE(is<LoadNonVolatileOperation>(*load, 2, 2));
1463 
1464  auto store = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*load->input(1)->origin());
1465  EXPECT_TRUE(is<StoreNonVolatileOperation>(*store, 3, 1));
1466 
1467  auto lambdaEntrySplit =
1468  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*store->input(2)->origin());
1469  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 1));
1470  }
1471 
1472  /*
1473  * Validate function g
1474  */
1475  {
1476  auto callNode = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1477  test.LambdaG().GetContextVars()[2].inner->SingleUser());
1478  EXPECT_TRUE(is<CallOperation>(*callNode, 3, 3));
1479 
1480  auto callEntryMerge =
1481  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*callNode->input(2)->origin());
1482  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMerge, 1, 1));
1483 
1484  auto callExitSplit =
1485  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(callNode->output(2)->SingleUser());
1486  EXPECT_TRUE(is<CallExitMemoryStateSplitOperation>(*callExitSplit, 1, 1));
1487 
1488  auto memcpyNode =
1489  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*callEntryMerge->input(0)->origin());
1490  EXPECT_TRUE(is<MemCpyNonVolatileOperation>(*memcpyNode, 5, 2));
1491 
1492  auto lambdaEntrySplit =
1493  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*memcpyNode->input(3)->origin());
1494  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 2));
1495  EXPECT_EQ(
1496  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*memcpyNode->input(4)->origin()),
1497  lambdaEntrySplit);
1498 
1499  auto lambdaExitMerge =
1500  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(callExitSplit->output(0)->SingleUser());
1501  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 2, 1));
1502  }
1503 }
1504 
1505 TEST(MemoryStateEncoderTests, freeNullTestAndersenAgnostic)
1506 {
1507  using namespace jlm::llvm;
1508  using namespace jlm::rvsdg;
1509 
1510  FreeNullTest test;
1511  encodeStates<aa::Andersen, aa::AgnosticModRefSummarizer>(test.module());
1512 
1513  auto lambdaExitMerge = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1514  *GetMemoryStateRegionResult(test.LambdaMain()).origin());
1515  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 2, 1));
1516 
1517  auto free = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(
1518  *test.LambdaMain().GetFunctionResults()[0]->origin());
1519  EXPECT_TRUE(is<FreeOperation>(*free, 2, 1));
1520 
1521  auto lambdaEntrySplit =
1522  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambdaExitMerge->input(0)->origin());
1523  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 2));
1524 }
1525 
1526 TEST(MemoryStateEncoderTests, LambdaMemoryStateArgumentMultipleUsers)
1527 {
1528  using namespace jlm::llvm;
1529  using namespace jlm::rvsdg;
1530  using namespace jlm::util;
1531 
1532  // Arrange
1533  auto bitType32 = BitType::Create(32);
1534  auto ioStateType = IOStateType::Create();
1535  auto memoryStateType = MemoryStateType::Create();
1536  auto pointerType = PointerType::Create();
1537  auto functionTypeOne = FunctionType::Create(
1538  { ioStateType, memoryStateType },
1539  { bitType32, ioStateType, memoryStateType });
1540  auto functionTypeMain = FunctionType::Create(
1541  { pointerType, ioStateType, memoryStateType },
1542  { bitType32, ioStateType, memoryStateType });
1543 
1544  jlm::llvm::LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
1545  auto & rvsdg = rvsdgModule.Rvsdg();
1546 
1547  LambdaNode * lambdaOne = nullptr;
1548  {
1549  lambdaOne = LambdaNode::Create(
1550  rvsdg.GetRootRegion(),
1551  LlvmLambdaOperation::Create(functionTypeOne, "one", Linkage::privateLinkage));
1552  auto ioStateArgument = lambdaOne->GetFunctionArguments()[0];
1553  auto memoryStateArgument = lambdaOne->GetFunctionArguments()[1];
1554 
1555  auto & one = IntegerConstantOperation::Create(*lambdaOne->subregion(), 32, 1);
1556 
1557  lambdaOne->finalize({ one.output(0), ioStateArgument, memoryStateArgument });
1558  }
1559 
1560  LambdaNode * lambdaMain = nullptr;
1561  {
1562  lambdaMain = LambdaNode::Create(
1563  rvsdg.GetRootRegion(),
1564  LlvmLambdaOperation::Create(functionTypeMain, "main", Linkage::externalLinkage));
1565  auto pointerArgument = lambdaMain->GetFunctionArguments()[0];
1566  auto ioStateArgument = lambdaMain->GetFunctionArguments()[1];
1567  auto memoryStateArgument = lambdaMain->GetFunctionArguments()[2];
1568  auto ctxVarOne = lambdaMain->AddContextVar(*lambdaOne->output());
1569 
1570  auto callResults = CallOperation::Create(
1571  ctxVarOne.inner,
1572  functionTypeOne,
1573  { ioStateArgument, memoryStateArgument });
1574 
1575  auto & loadNode = LoadNonVolatileOperation::CreateNode(
1576  *pointerArgument,
1577  { memoryStateArgument },
1578  bitType32,
1579  4);
1580 
1581  auto & addNode = CreateOpNode<IntegerAddOperation>({ callResults[0], loadNode.output(0) }, 32);
1582 
1583  lambdaMain->finalize({ addNode.output(0), callResults[1], loadNode.output(1) });
1584  }
1585 
1586  GraphExport::Create(*lambdaMain->output(), "main");
1587 
1588  view(rvsdg, stdout);
1589 
1590  // Act
1591  encodeStates<aa::Andersen, aa::RegionAwareModRefSummarizer>(rvsdgModule);
1592 
1593  view(rvsdg, stdout);
1594 
1595  // Assert
1596  {
1597  auto lambdaExitMerge =
1598  TryGetOwnerNode<SimpleNode>(*GetMemoryStateRegionResult(*lambdaMain).origin());
1599  EXPECT_TRUE(is<LambdaExitMemoryStateMergeOperation>(*lambdaExitMerge, 1, 1));
1600 
1601  auto loadNode = TryGetOwnerNode<SimpleNode>(*lambdaExitMerge->input(0)->origin());
1602  EXPECT_TRUE(is<LoadNonVolatileOperation>(*loadNode, 2, 2));
1603 
1604  auto lambdaEntrySplit = TryGetOwnerNode<SimpleNode>(*loadNode->input(1)->origin());
1605  EXPECT_TRUE(is<LambdaEntryMemoryStateSplitOperation>(*lambdaEntrySplit, 1, 1));
1606 
1607  auto addNode = TryGetOwnerNode<SimpleNode>(*lambdaMain->GetFunctionResults()[0]->origin());
1608  EXPECT_TRUE(is<IntegerAddOperation>(*addNode, 2, 1));
1609 
1610  auto callNode = TryGetOwnerNode<SimpleNode>(*addNode->input(0)->origin());
1611  EXPECT_TRUE(is<CallOperation>(*callNode, 3, 3));
1612  EXPECT_TRUE(CallOperation::GetMemoryStateOutput(*callNode).IsDead());
1613 
1614  auto callEntryMergeNode =
1615  TryGetOwnerNode<SimpleNode>(*CallOperation::GetMemoryStateInput(*callNode).origin());
1616  EXPECT_TRUE(is<CallEntryMemoryStateMergeOperation>(*callEntryMergeNode, 0, 1));
1617  }
1618 }
statisticsCollector
static jlm::util::StatisticsCollector statisticsCollector
Definition: CommonNodeEliminationTests.cpp:21
encodeStates
static void encodeStates(jlm::rvsdg::RvsdgModule &rvsdgModule)
Definition: MemoryStateEncoderTests.cpp:25
TEST
TEST(MemoryStateEncoderTests, storeTest1AndersenAgnostic)
Definition: MemoryStateEncoderTests.cpp:60
is
static bool is(const jlm::rvsdg::Node &node, size_t numInputs, size_t numOutputs)
Definition: MemoryStateEncoderTests.cpp:55
jlm::llvm::CallOperation::GetMemoryStateInput
static rvsdg::Input & GetMemoryStateInput(const rvsdg::Node &node) noexcept
Definition: call.hpp:357
jlm::llvm::CallOperation::GetMemoryStateOutput
static rvsdg::Output & GetMemoryStateOutput(const rvsdg::Node &node) noexcept
Definition: call.hpp:369
jlm::llvm::CallOperation::Create
static std::vector< rvsdg::Output * > Create(rvsdg::Output *function, std::shared_ptr< const rvsdg::FunctionType > functionType, const std::vector< rvsdg::Output * > &arguments)
Definition: call.hpp:464
jlm::llvm::CallTest1
CallTest1 class.
Definition: TestRvsdgs.hpp:425
jlm::llvm::CallTest1::CallG
const rvsdg::SimpleNode & CallG() const noexcept
Definition: TestRvsdgs.hpp:438
jlm::llvm::CallTest1::lambda_g
jlm::rvsdg::LambdaNode * lambda_g
Definition: TestRvsdgs.hpp:444
jlm::llvm::CallTest1::lambda_f
jlm::rvsdg::LambdaNode * lambda_f
Definition: TestRvsdgs.hpp:443
jlm::llvm::CallTest1::CallF
const rvsdg::SimpleNode & CallF() const noexcept
Definition: TestRvsdgs.hpp:432
jlm::llvm::CallTest2
CallTest2 class.
Definition: TestRvsdgs.hpp:488
jlm::llvm::CallTest2::lambda_test
jlm::rvsdg::LambdaNode * lambda_test
Definition: TestRvsdgs.hpp:516
jlm::llvm::CallTest2::lambda_create
jlm::rvsdg::LambdaNode * lambda_create
Definition: TestRvsdgs.hpp:514
jlm::llvm::CallTest2::lambda_destroy
jlm::rvsdg::LambdaNode * lambda_destroy
Definition: TestRvsdgs.hpp:515
jlm::llvm::CallTest2::malloc
rvsdg::SimpleNode * malloc
Definition: TestRvsdgs.hpp:518
jlm::llvm::DeltaTest1
DeltaTest1 class.
Definition: TestRvsdgs.hpp:1161
jlm::llvm::DeltaTest1::lambda_h
jlm::rvsdg::LambdaNode * lambda_h
Definition: TestRvsdgs.hpp:1170
jlm::llvm::DeltaTest1::constantFive
rvsdg::Node * constantFive
Definition: TestRvsdgs.hpp:1174
jlm::llvm::DeltaTest1::lambda_g
jlm::rvsdg::LambdaNode * lambda_g
Definition: TestRvsdgs.hpp:1169
jlm::llvm::DeltaTest2
DeltaTest2 class.
Definition: TestRvsdgs.hpp:1210
jlm::llvm::DeltaTest2::lambda_f2
jlm::rvsdg::LambdaNode * lambda_f2
Definition: TestRvsdgs.hpp:1219
jlm::llvm::DeltaTest2::lambda_f1
jlm::rvsdg::LambdaNode * lambda_f1
Definition: TestRvsdgs.hpp:1218
jlm::llvm::DeltaTest3
DeltaTest3 class.
Definition: TestRvsdgs.hpp:1257
jlm::llvm::DeltaTest3::LambdaF
const jlm::rvsdg::LambdaNode & LambdaF() const noexcept
Definition: TestRvsdgs.hpp:1260
jlm::llvm::FreeNullTest
RVSDG module with a call to free(NULL).
Definition: TestRvsdgs.hpp:2399
jlm::llvm::FreeNullTest::LambdaMain
rvsdg::LambdaNode & LambdaMain() const noexcept
Definition: TestRvsdgs.hpp:2402
jlm::llvm::GammaTest
GammaTest class.
Definition: TestRvsdgs.hpp:961
jlm::llvm::GammaTest::gamma
rvsdg::GammaNode * gamma
Definition: TestRvsdgs.hpp:969
jlm::llvm::GammaTest::lambda
jlm::rvsdg::LambdaNode * lambda
Definition: TestRvsdgs.hpp:967
jlm::llvm::IOStateType::Create
static std::shared_ptr< const IOStateType > Create()
Definition: types.cpp:343
jlm::llvm::ImportTest
ImportTest class.
Definition: TestRvsdgs.hpp:1329
jlm::llvm::ImportTest::lambda_f1
jlm::rvsdg::LambdaNode * lambda_f1
Definition: TestRvsdgs.hpp:1337
jlm::llvm::ImportTest::lambda_f2
jlm::rvsdg::LambdaNode * lambda_f2
Definition: TestRvsdgs.hpp:1338
jlm::llvm::IndirectCallTest1
IndirectCallTest1 class.
Definition: TestRvsdgs.hpp:566
jlm::llvm::IndirectCallTest1::GetLambdaTest
const jlm::rvsdg::LambdaNode & GetLambdaTest() const noexcept
Definition: TestRvsdgs.hpp:605
jlm::llvm::IndirectCallTest1::GetLambdaIndcall
const jlm::rvsdg::LambdaNode & GetLambdaIndcall() const noexcept
Definition: TestRvsdgs.hpp:599
jlm::llvm::IndirectCallTest2
IndirectCallTest2 class.
Definition: TestRvsdgs.hpp:687
jlm::llvm::IndirectCallTest2::GetCallIWithFour
rvsdg::SimpleNode & GetCallIWithFour() const noexcept
Definition: TestRvsdgs.hpp:756
jlm::llvm::IndirectCallTest2::GetLambdaI
jlm::rvsdg::LambdaNode & GetLambdaI() const noexcept
Definition: TestRvsdgs.hpp:714
jlm::llvm::IndirectCallTest2::GetLambdaFour
jlm::rvsdg::LambdaNode & GetLambdaFour() const noexcept
Definition: TestRvsdgs.hpp:708
jlm::llvm::IndirectCallTest2::GetLambdaTest
jlm::rvsdg::LambdaNode & GetLambdaTest() const noexcept
Definition: TestRvsdgs.hpp:732
jlm::llvm::IndirectCallTest2::GetCallIWithThree
rvsdg::SimpleNode & GetCallIWithThree() const noexcept
Definition: TestRvsdgs.hpp:750
jlm::llvm::IndirectCallTest2::GetLambdaTest2
jlm::rvsdg::LambdaNode & GetLambdaTest2() const noexcept
Definition: TestRvsdgs.hpp:738
jlm::llvm::IndirectCallTest2::GetLambdaX
jlm::rvsdg::LambdaNode & GetLambdaX() const noexcept
Definition: TestRvsdgs.hpp:720
jlm::llvm::IndirectCallTest2::GetIndirectCall
rvsdg::SimpleNode & GetIndirectCall() const noexcept
Definition: TestRvsdgs.hpp:744
jlm::llvm::IndirectCallTest2::GetLambdaY
jlm::rvsdg::LambdaNode & GetLambdaY() const noexcept
Definition: TestRvsdgs.hpp:726
jlm::llvm::IndirectCallTest2::GetLambdaThree
jlm::rvsdg::LambdaNode & GetLambdaThree() const noexcept
Definition: TestRvsdgs.hpp:702
jlm::llvm::IntegerConstantOperation::Create
static rvsdg::Node & Create(rvsdg::Region &region, IntegerValueRepresentation representation)
Definition: IntegerOperations.hpp:50
jlm::llvm::LlvmLambdaOperation::Create
static std::unique_ptr< LlvmLambdaOperation > Create(std::shared_ptr< const jlm::rvsdg::FunctionType > type, std::string name, const jlm::llvm::Linkage &linkage, jlm::llvm::CallingConvention callingConvention, jlm::llvm::AttributeSet attributes)
Definition: lambda.hpp:84
jlm::llvm::LoadFromUndefTest
LoadFromUndefTest class.
Definition: TestRvsdgs.hpp:236
jlm::llvm::LoadFromUndefTest::Lambda
const jlm::rvsdg::LambdaNode & Lambda() const noexcept
Definition: TestRvsdgs.hpp:243
jlm::llvm::LoadNonVolatileOperation::CreateNode
static rvsdg::SimpleNode & CreateNode(rvsdg::Region &region, std::unique_ptr< LoadNonVolatileOperation > loadOperation, const std::vector< rvsdg::Output * > &operands)
Definition: Load.hpp:466
jlm::llvm::LoadTest1
LoadTest1 class.
Definition: TestRvsdgs.hpp:161
jlm::llvm::LoadTest1::lambda
jlm::rvsdg::LambdaNode * lambda
Definition: TestRvsdgs.hpp:167
jlm::llvm::LoadTest2
LoadTest2 class.
Definition: TestRvsdgs.hpp:200
jlm::llvm::LoadTest2::alloca_p
rvsdg::SimpleNode * alloca_p
Definition: TestRvsdgs.hpp:214
jlm::llvm::LoadTest2::lambda
jlm::rvsdg::LambdaNode * lambda
Definition: TestRvsdgs.hpp:206
jlm::llvm::LoadTest2::alloca_y
rvsdg::SimpleNode * alloca_y
Definition: TestRvsdgs.hpp:213
jlm::llvm::LoadTest2::alloca_a
rvsdg::SimpleNode * alloca_a
Definition: TestRvsdgs.hpp:210
jlm::llvm::LoadTest2::alloca_x
rvsdg::SimpleNode * alloca_x
Definition: TestRvsdgs.hpp:212
jlm::llvm::LoadTest2::alloca_b
rvsdg::SimpleNode * alloca_b
Definition: TestRvsdgs.hpp:211
jlm::llvm::MallocOperation::memoryStateOutput
static rvsdg::Output & memoryStateOutput(const rvsdg::Node &node)
Definition: operators.hpp:2476
jlm::llvm::MemcpyTest
MemcpyTest class.
Definition: TestRvsdgs.hpp:1858
jlm::llvm::MemcpyTest::LambdaF
const jlm::rvsdg::LambdaNode & LambdaF() const noexcept
Definition: TestRvsdgs.hpp:1861
jlm::llvm::MemcpyTest::LambdaG
const jlm::rvsdg::LambdaNode & LambdaG() const noexcept
Definition: TestRvsdgs.hpp:1867
jlm::llvm::MemoryStateType::Create
static std::shared_ptr< const MemoryStateType > Create()
Definition: types.cpp:379
jlm::llvm::PhiTest1
PhiTest1 class.
Definition: TestRvsdgs.hpp:1382
jlm::llvm::PhiTest1::gamma
rvsdg::GammaNode * gamma
Definition: TestRvsdgs.hpp:1405
jlm::llvm::PhiTest1::alloca
rvsdg::SimpleNode * alloca
Definition: TestRvsdgs.hpp:1409
jlm::llvm::PhiTest1::lambda_fib
jlm::rvsdg::LambdaNode * lambda_fib
Definition: TestRvsdgs.hpp:1402
jlm::llvm::PointerType::Create
static std::shared_ptr< const PointerType > Create()
Definition: types.cpp:45
jlm::llvm::RvsdgTest::module
jlm::llvm::LlvmRvsdgModule & module()
Definition: TestRvsdgs.hpp:34
jlm::llvm::StoreTest1
StoreTest1 class.
Definition: TestRvsdgs.hpp:89
jlm::llvm::StoreTest1::alloca_c
rvsdg::SimpleNode * alloca_c
Definition: TestRvsdgs.hpp:101
jlm::llvm::StoreTest1::alloca_a
rvsdg::SimpleNode * alloca_a
Definition: TestRvsdgs.hpp:99
jlm::llvm::StoreTest1::alloca_d
rvsdg::SimpleNode * alloca_d
Definition: TestRvsdgs.hpp:102
jlm::llvm::StoreTest1::lambda
jlm::rvsdg::LambdaNode * lambda
Definition: TestRvsdgs.hpp:95
jlm::llvm::StoreTest1::alloca_b
rvsdg::SimpleNode * alloca_b
Definition: TestRvsdgs.hpp:100
jlm::llvm::StoreTest2
StoreTest2 class.
Definition: TestRvsdgs.hpp:127
jlm::llvm::StoreTest2::alloca_p
rvsdg::SimpleNode * alloca_p
Definition: TestRvsdgs.hpp:141
jlm::llvm::StoreTest2::lambda
jlm::rvsdg::LambdaNode * lambda
Definition: TestRvsdgs.hpp:133
jlm::llvm::StoreTest2::alloca_y
rvsdg::SimpleNode * alloca_y
Definition: TestRvsdgs.hpp:140
jlm::llvm::StoreTest2::alloca_x
rvsdg::SimpleNode * alloca_x
Definition: TestRvsdgs.hpp:139
jlm::llvm::StoreTest2::alloca_b
rvsdg::SimpleNode * alloca_b
Definition: TestRvsdgs.hpp:138
jlm::llvm::StoreTest2::alloca_a
rvsdg::SimpleNode * alloca_a
Definition: TestRvsdgs.hpp:137
jlm::llvm::ThetaTest
ThetaTest class.
Definition: TestRvsdgs.hpp:1125
jlm::llvm::ThetaTest::lambda
jlm::rvsdg::LambdaNode * lambda
Definition: TestRvsdgs.hpp:1131
jlm::llvm::ThetaTest::theta
jlm::rvsdg::ThetaNode * theta
Definition: TestRvsdgs.hpp:1132
jlm::llvm::aa::MemoryStateEncoder::Encode
void Encode(rvsdg::RvsdgModule &rvsdgModule, const ModRefSummary &modRefSummary, util::StatisticsCollector &statisticsCollector)
Definition: MemoryStateEncoder.cpp:629
jlm::llvm::aa::PointsToGraph::dumpDot
static std::string dumpDot(const PointsToGraph &pointsToGraph)
Definition: PointsToGraph.cpp:547
jlm::rvsdg::GammaNode::GetExitVars
std::vector< ExitVar > GetExitVars() const
Gets all exit variables for this gamma.
Definition: gamma.cpp:381
jlm::rvsdg::Graph::GetRootRegion
Region & GetRootRegion() const noexcept
Definition: graph.hpp:99
jlm::rvsdg::Input::origin
Output * origin() const noexcept
Definition: node.hpp:58
jlm::rvsdg::LambdaNode
Lambda node.
Definition: lambda.hpp:83
jlm::rvsdg::LambdaNode::finalize
rvsdg::Output * finalize(const std::vector< jlm::rvsdg::Output * > &results)
Definition: lambda.cpp:146
jlm::rvsdg::LambdaNode::GetFunctionArguments
std::vector< rvsdg::Output * > GetFunctionArguments() const
Definition: lambda.cpp:57
jlm::rvsdg::LambdaNode::subregion
rvsdg::Region * subregion() const noexcept
Definition: lambda.hpp:138
jlm::rvsdg::LambdaNode::AddContextVar
ContextVar AddContextVar(jlm::rvsdg::Output &origin)
Adds a context/free variable to the lambda node.
Definition: lambda.cpp:131
jlm::rvsdg::LambdaNode::GetFunctionResults
std::vector< rvsdg::Input * > GetFunctionResults() const
Definition: lambda.cpp:69
jlm::rvsdg::LambdaNode::output
rvsdg::Output * output() const noexcept
Definition: lambda.cpp:176
jlm::rvsdg::LambdaNode::GetContextVars
std::vector< ContextVar > GetContextVars() const noexcept
Gets all bound context variables.
Definition: lambda.cpp:119
jlm::rvsdg::Node::input
NodeInput * input(size_t index) const noexcept
Definition: node.hpp:615
jlm::rvsdg::Node::output
NodeOutput * output(size_t index) const noexcept
Definition: node.hpp:650
jlm::rvsdg::Node::ninputs
size_t ninputs() const noexcept
Definition: node.hpp:609
jlm::rvsdg::Node::noutputs
size_t noutputs() const noexcept
Definition: node.hpp:644
jlm::rvsdg::Output::SingleUser
rvsdg::Input & SingleUser() noexcept
Definition: node.hpp:347
jlm::rvsdg::Output::IsDead
bool IsDead() const noexcept
Definition: node.hpp:295
jlm::rvsdg::Output::nusers
size_t nusers() const noexcept
Definition: node.hpp:280
jlm::rvsdg::Region::numNodes
size_t numNodes() const noexcept
Definition: region.hpp:481
jlm::rvsdg::RvsdgModule::Rvsdg
Graph & Rvsdg() noexcept
Definition: RvsdgModule.hpp:57
jlm::rvsdg::SimpleNode::input
NodeInput * input(size_t index) const noexcept
Definition: simple-node.hpp:82
jlm::rvsdg::SimpleNode::output
NodeOutput * output(size_t index) const noexcept
Definition: simple-node.hpp:88
jlm::llvm
Global memory state passed between functions.
Definition: IpGraphToLlvmConverter.cpp:36
jlm::llvm::GetMemoryStateRegionResult
rvsdg::Input & GetMemoryStateRegionResult(const rvsdg::LambdaNode &lambdaNode) noexcept
Definition: LambdaMemoryState.cpp:22
jlm::rvsdg::view
std::string view(const rvsdg::Region *region)
Definition: view.cpp:142
Generated by doxygen 1.9.1