Jlm
MemoryStateOperationTests.cpp
Go to the documentation of this file.
1 /*
2  * Copyright 2024 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/operators/alloca.hpp>
9 #include <jlm/llvm/ir/operators/Load.hpp>
10 #include <jlm/llvm/ir/operators/MemoryStateOperations.hpp>
11 #include <jlm/llvm/ir/operators/Store.hpp>
12 #include <jlm/llvm/ir/RvsdgModule.hpp>
13 #include <jlm/rvsdg/NodeNormalization.hpp>
14 #include <jlm/rvsdg/TestOperations.hpp>
15 #include <jlm/rvsdg/TestType.hpp>
16 #include <jlm/rvsdg/view.hpp>
17 
18 TEST(MemoryStateOperationTests, MemoryStateSplitEquality)
19 {
20  using namespace jlm::llvm;
21  using namespace jlm::rvsdg;
22 
23  // Arrange
24  auto memoryStateType = MemoryStateType::Create();
25  MemoryStateSplitOperation operation1(2);
26  MemoryStateSplitOperation operation2(4);
27  TestOperation operation3({ memoryStateType }, { memoryStateType, memoryStateType });
28 
29  // Act & Assert
30  EXPECT_EQ(operation1, operation1);
31  EXPECT_NE(operation1, operation2); // Number of results differ
32  EXPECT_NE(operation1, operation3); // Operation differs
33 }
34 
35 TEST(MemoryStateOperationTests, MemoryStateSplitNormalizeSingleResult)
36 {
37  using namespace jlm::llvm;
38  using namespace jlm::rvsdg;
39 
40  // Arrange
41  const auto memoryStateType = MemoryStateType::Create();
42 
43  Graph rvsdg;
44  auto & ix = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x");
45 
46  auto & splitNode = MemoryStateSplitOperation::CreateNode(ix, 1);
47 
48  auto & ex = jlm::rvsdg::GraphExport::Create(*splitNode.output(0), "x");
49 
50  view(&rvsdg.GetRootRegion(), stdout);
51 
52  // Act
53  jlm::rvsdg::ReduceNode<MemoryStateSplitOperation>(
54  MemoryStateSplitOperation::NormalizeSingleResult,
55  splitNode);
56  rvsdg.PruneNodes();
57  view(&rvsdg.GetRootRegion(), stdout);
58 
59  // Assert
60  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 0u);
61  EXPECT_EQ(ex.origin(), &ix);
62 }
63 
64 TEST(MemoryStateOperationTests, MemoryStateSplitNormalizeNestedSplits)
65 {
66  using namespace jlm::llvm;
67  using namespace jlm::rvsdg;
68 
69  // Arrange
70  const auto memoryStateType = MemoryStateType::Create();
71  Graph rvsdg;
72  auto & ix = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x");
73 
74  auto & splitNode0 = MemoryStateSplitOperation::CreateNode(ix, 3);
75  auto & splitNode1 = MemoryStateSplitOperation::CreateNode(*splitNode0.output(0), 2);
76  auto & splitNode2 = MemoryStateSplitOperation::CreateNode(*splitNode0.output(2), 2);
77 
78  auto & ex0 = jlm::rvsdg::GraphExport::Create(*splitNode1.output(0), "sn10");
79  auto & ex1 = jlm::rvsdg::GraphExport::Create(*splitNode1.output(1), "sn11");
80  auto & ex2 = jlm::rvsdg::GraphExport::Create(*splitNode0.output(1), "sn01");
81  auto & ex3 = jlm::rvsdg::GraphExport::Create(*splitNode2.output(0), "sn20");
82  auto & ex4 = jlm::rvsdg::GraphExport::Create(*splitNode2.output(1), "sn21");
83 
84  view(&rvsdg.GetRootRegion(), stdout);
85 
86  // Act
87  jlm::rvsdg::ReduceNode<MemoryStateSplitOperation>(
88  MemoryStateSplitOperation::NormalizeNestedSplits,
89  splitNode1);
90  jlm::rvsdg::ReduceNode<MemoryStateSplitOperation>(
91  MemoryStateSplitOperation::NormalizeNestedSplits,
92  splitNode2);
93  rvsdg.PruneNodes();
94  view(&rvsdg.GetRootRegion(), stdout);
95 
96  // Assert
97  // We should only have MemoryStateSplit left
98  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 1u);
99  auto [splitNode, splitOperation] =
100  TryGetSimpleNodeAndOptionalOp<MemoryStateSplitOperation>(*ex0.origin());
101  EXPECT_TRUE(splitNode && splitOperation);
102 
103  // We should have 7 outputs:
104  // - 2 from splitNode1
105  // - 2 from splitNode2
106  // - 1 from splitNode0
107  // - 1 from splitNode0 -> splitNode1
108  // - 1 from splitNode0 -> splitNode2
109  EXPECT_EQ(splitNode->noutputs(), 7u);
110  EXPECT_EQ(TryGetOwnerNode<SimpleNode>(*ex0.origin()), splitNode);
111  EXPECT_EQ(TryGetOwnerNode<SimpleNode>(*ex1.origin()), splitNode);
112  EXPECT_EQ(TryGetOwnerNode<SimpleNode>(*ex2.origin()), splitNode);
113  EXPECT_EQ(TryGetOwnerNode<SimpleNode>(*ex3.origin()), splitNode);
114  EXPECT_EQ(TryGetOwnerNode<SimpleNode>(*ex4.origin()), splitNode);
115 }
116 
117 TEST(MemoryStateOperationTests, MemoryStateSplitNormalizeSplitMerge)
118 {
119  using namespace jlm::llvm;
120  using namespace jlm::rvsdg;
121 
122  // Arrange
123  const auto memoryStateType = MemoryStateType::Create();
124  Graph rvsdg;
125  auto & ix0 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x");
126  auto & ix1 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x");
127  auto & ix2 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x");
128 
129  auto mergeResult = MemoryStateMergeOperation::Create({ &ix0, &ix1, &ix2 });
130  auto & splitNode = MemoryStateSplitOperation::CreateNode(*mergeResult, 3);
131 
132  auto & ex0 = jlm::rvsdg::GraphExport::Create(*splitNode.output(0), "ex0");
133  auto & ex1 = jlm::rvsdg::GraphExport::Create(*splitNode.output(1), "ex1");
134  auto & ex2 = jlm::rvsdg::GraphExport::Create(*splitNode.output(2), "ex2");
135 
136  view(&rvsdg.GetRootRegion(), stdout);
137 
138  // Act
139  jlm::rvsdg::ReduceNode<MemoryStateSplitOperation>(
140  MemoryStateSplitOperation::NormalizeSplitMerge,
141  splitNode);
142  rvsdg.PruneNodes();
143  view(&rvsdg.GetRootRegion(), stdout);
144 
145  // Assert
146  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 0u);
147  EXPECT_EQ(ex0.origin(), &ix0);
148  EXPECT_EQ(ex1.origin(), &ix1);
149  EXPECT_EQ(ex2.origin(), &ix2);
150 }
151 
152 TEST(MemoryStateOperationTests, MemoryStateMergeEquality)
153 {
154  using namespace jlm::llvm;
155  using namespace jlm::rvsdg;
156 
157  // Arrange
158  auto memoryStateType = MemoryStateType::Create();
159  MemoryStateMergeOperation operation1(2);
160  MemoryStateMergeOperation operation2(4);
161  TestOperation operation3({ memoryStateType, memoryStateType }, { memoryStateType });
162 
163  // Act & Assert
164  EXPECT_EQ(operation1, operation1);
165  EXPECT_NE(operation1, operation2); // Number of operands differ
166  EXPECT_NE(operation1, operation3); // Operation differs
167 }
168 
169 TEST(MemoryStateOperationTests, MemoryStateMergeNormalizeSingleOperand)
170 {
171  using namespace jlm::llvm;
172  using namespace jlm::rvsdg;
173 
174  // Arrange
175  const auto memoryStateType = MemoryStateType::Create();
176 
177  Graph rvsdg;
178  auto & ix = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x");
179 
180  auto & mergeNode = MemoryStateMergeOperation::CreateNode({ &ix });
181 
182  auto & ex = jlm::rvsdg::GraphExport::Create(*mergeNode.output(0), "x");
183 
184  view(&rvsdg.GetRootRegion(), stdout);
185 
186  // Act
187  ReduceNode<MemoryStateMergeOperation>(
188  MemoryStateMergeOperation::NormalizeSingleOperand,
189  mergeNode);
190  rvsdg.PruneNodes();
191  view(&rvsdg.GetRootRegion(), stdout);
192 
193  // Assert
194  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 0u);
195  EXPECT_EQ(ex.origin(), &ix);
196 }
197 
198 TEST(MemoryStateOperationTests, MemoryStateMergeNormalizeDuplicateOperands)
199 {
200  using namespace jlm::llvm;
201  using namespace jlm::rvsdg;
202 
203  // Arrange
204  const auto memoryStateType = MemoryStateType::Create();
205 
206  Graph rvsdg;
207  auto & ix0 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x0");
208  auto & ix1 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x1");
209 
210  auto & node = MemoryStateMergeOperation::CreateNode({ &ix0, &ix0, &ix1, &ix1 });
211 
212  auto & ex = jlm::rvsdg::GraphExport::Create(*node.output(0), "x");
213 
214  view(&rvsdg.GetRootRegion(), stdout);
215 
216  // Act
217  ReduceNode<MemoryStateMergeOperation>(
218  MemoryStateMergeOperation::NormalizeDuplicateOperands,
219  node);
220  rvsdg.PruneNodes();
221  view(&rvsdg.GetRootRegion(), stdout);
222 
223  // Assert
224  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 1u);
225  auto [mergeNode, mergeOperation] =
226  TryGetSimpleNodeAndOptionalOp<MemoryStateMergeOperation>(*ex.origin());
227  EXPECT_TRUE(mergeNode && mergeOperation);
228 
229  EXPECT_EQ(mergeNode->ninputs(), 2u);
230 }
231 
232 TEST(MemoryStateOperationTests, MemoryStateMergeNormalizeNestedMerges)
233 {
234  using namespace jlm::llvm;
235  using namespace jlm::rvsdg;
236 
237  // Arrange
238  const auto memoryStateType = MemoryStateType::Create();
239 
240  Graph rvsdg;
241  auto & ix0 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x0");
242  auto & ix1 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x1");
243  auto & ix2 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x2");
244  auto & ix3 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x3");
245  auto & ix4 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x4");
246 
247  auto & mergeNode0 = MemoryStateMergeOperation::CreateNode({ &ix0, &ix1 });
248  auto & mergeNode1 = MemoryStateMergeOperation::CreateNode({ &ix2, &ix3 });
249  auto & mergeNode2 =
250  MemoryStateMergeOperation::CreateNode({ mergeNode0.output(0), mergeNode1.output(0), &ix4 });
251 
252  auto & ex = jlm::rvsdg::GraphExport::Create(*mergeNode2.output(0), "x");
253 
254  view(&rvsdg.GetRootRegion(), stdout);
255 
256  // Act
257  ReduceNode<MemoryStateMergeOperation>(
258  MemoryStateMergeOperation::NormalizeNestedMerges,
259  mergeNode2);
260  rvsdg.PruneNodes();
261  view(&rvsdg.GetRootRegion(), stdout);
262 
263  // Assert
264  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 1u);
265  auto [mergeNode, mergeOperation] =
266  TryGetSimpleNodeAndOptionalOp<MemoryStateMergeOperation>(*ex.origin());
267  EXPECT_TRUE(mergeNode && mergeOperation);
268 
269  EXPECT_EQ(mergeNode->ninputs(), 5u);
270 }
271 
272 TEST(MemoryStateOperationTests, MemoryStateMergeNormalizeNestedSplits)
273 {
274  using namespace jlm::llvm;
275  using namespace jlm::rvsdg;
276 
277  // Arrange
278  const auto memoryStateType = MemoryStateType::Create();
279 
280  Graph rvsdg;
281  auto & ix0 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x0");
282  auto & ix1 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x1");
283  auto & ix2 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x2");
284 
285  auto & splitNode0 = MemoryStateSplitOperation::CreateNode(ix0, 2);
286  auto & splitNode1 = MemoryStateSplitOperation::CreateNode(ix1, 2);
287  auto & mergeNode = MemoryStateMergeOperation::CreateNode({ splitNode0.output(0),
288  splitNode0.output(1),
289  splitNode1.output(0),
290  splitNode1.output(1),
291  &ix2 });
292 
293  auto & ex = jlm::rvsdg::GraphExport::Create(*mergeNode.output(0), "x");
294 
295  view(&rvsdg.GetRootRegion(), stdout);
296 
297  // Act
298  ReduceNode<MemoryStateMergeOperation>(MemoryStateMergeOperation::NormalizeMergeSplit, mergeNode);
299  rvsdg.PruneNodes();
300  view(&rvsdg.GetRootRegion(), stdout);
301 
302  // Assert
303  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 1u);
304  auto [node, mergeOperation] =
305  TryGetSimpleNodeAndOptionalOp<MemoryStateMergeOperation>(*ex.origin());
306  EXPECT_TRUE(node && mergeOperation);
307 
308  EXPECT_EQ(node->ninputs(), 5u);
309  EXPECT_EQ(node->input(0)->origin(), &ix0);
310  EXPECT_EQ(node->input(1)->origin(), &ix0);
311  EXPECT_EQ(node->input(2)->origin(), &ix1);
312  EXPECT_EQ(node->input(3)->origin(), &ix1);
313  EXPECT_EQ(node->input(4)->origin(), &ix2);
314 }
315 
316 TEST(MemoryStateOperationTests, MemoryStateJoin_NormalizeSingleOperand)
317 {
318  using namespace jlm::llvm;
319  using namespace jlm::rvsdg;
320 
321  // Arrange
322  const auto memoryStateType = MemoryStateType::Create();
323 
324  Graph rvsdg;
325  auto & ix = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x");
326 
327  auto & mergeNode = MemoryStateJoinOperation::CreateNode({ &ix });
328 
329  auto & ex = GraphExport::Create(*mergeNode.output(0), "x");
330 
331  view(&rvsdg.GetRootRegion(), stdout);
332 
333  // Act
334  ReduceNode<MemoryStateJoinOperation>(MemoryStateJoinOperation::NormalizeSingleOperand, mergeNode);
335  rvsdg.PruneNodes();
336  view(&rvsdg.GetRootRegion(), stdout);
337 
338  // Assert
339  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 0u);
340  EXPECT_EQ(ex.origin(), &ix);
341 }
342 
343 TEST(MemoryStateOperationTests, MemoryStateJoin_NormalizeDuplicateOperands)
344 {
345  using namespace jlm::llvm;
346  using namespace jlm::rvsdg;
347 
348  // Arrange
349  const auto memoryStateType = MemoryStateType::Create();
350 
351  Graph rvsdg;
352  auto & i0 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "i0");
353  auto & i1 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "i1");
354 
355  auto & node0 = MemoryStateJoinOperation::CreateNode({ &i0, &i0, &i1, &i1 });
356  auto & node1 = MemoryStateJoinOperation::CreateNode({ &i0, &i0, &i0, &i0 });
357 
358  auto & x0 = GraphExport::Create(*node0.output(0), "x0");
359  auto & x1 = GraphExport::Create(*node1.output(0), "x1");
360 
361  view(&rvsdg.GetRootRegion(), stdout);
362 
363  // Act
364  ReduceNode<MemoryStateJoinOperation>(MemoryStateJoinOperation::NormalizeDuplicateOperands, node0);
365  ReduceNode<MemoryStateJoinOperation>(MemoryStateJoinOperation::NormalizeDuplicateOperands, node1);
366  rvsdg.PruneNodes();
367  view(&rvsdg.GetRootRegion(), stdout);
368 
369  // Assert
370  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 1u);
371 
372  {
373  auto [joinNode, joinOperation] =
374  TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(*x0.origin());
375  EXPECT_TRUE(joinNode && joinOperation);
376 
377  EXPECT_EQ(joinNode->ninputs(), 2u);
378  EXPECT_EQ(joinNode->input(0)->origin(), &i0);
379  EXPECT_EQ(joinNode->input(1)->origin(), &i1);
380  }
381 
382  {
383  EXPECT_EQ(x1.origin(), &i0);
384  }
385 }
386 
387 TEST(MemoryStateOperationTests, MemoryStateJoin_NormalizeNestedJoins)
388 {
389  using namespace jlm::llvm;
390  using namespace jlm::rvsdg;
391 
392  // Arrange
393  const auto memoryStateType = MemoryStateType::Create();
394 
395  Graph rvsdg;
396  auto & ix0 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x0");
397  auto & ix1 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x1");
398  auto & ix2 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x2");
399  auto & ix3 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x3");
400  auto & ix4 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x4");
401  auto & ix5 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "x4");
402 
403  auto & joinNode0 = MemoryStateJoinOperation::CreateNode({ &ix0, &ix1 });
404  auto & joinNode1 = MemoryStateJoinOperation::CreateNode({ joinNode0.output(0), &ix2 });
405  auto & joinNode2 = MemoryStateJoinOperation::CreateNode({ &ix3, &ix4 });
406  auto & joinNode3 =
407  MemoryStateJoinOperation::CreateNode({ joinNode1.output(0), joinNode2.output(0), &ix5 });
408 
409  auto & ex = GraphExport::Create(*joinNode3.output(0), "x");
410 
411  view(&rvsdg.GetRootRegion(), stdout);
412 
413  // Act
414  ReduceNode<MemoryStateJoinOperation>(MemoryStateJoinOperation::NormalizeNestedJoins, joinNode3);
415  rvsdg.PruneNodes();
416  view(&rvsdg.GetRootRegion(), stdout);
417 
418  // Assert
419  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 1u);
420  auto [joinNode, joinOperation] =
421  TryGetSimpleNodeAndOptionalOp<MemoryStateJoinOperation>(*ex.origin());
422  EXPECT_TRUE(joinNode && joinOperation);
423 
424  EXPECT_EQ(joinNode->ninputs(), 6u);
425  EXPECT_EQ(joinNode->input(0)->origin(), &ix0);
426  EXPECT_EQ(joinNode->input(1)->origin(), &ix1);
427  EXPECT_EQ(joinNode->input(2)->origin(), &ix2);
428  EXPECT_EQ(joinNode->input(3)->origin(), &ix3);
429  EXPECT_EQ(joinNode->input(4)->origin(), &ix4);
430  EXPECT_EQ(joinNode->input(5)->origin(), &ix5);
431 }
432 
433 TEST(MemoryStateOperationTests, LambdaEntryMemStateOperatorEquality)
434 {
435  using namespace jlm::llvm;
436  using namespace jlm::rvsdg;
437 
438  // Arrange
439  auto memoryStateType = MemoryStateType::Create();
440  const LambdaEntryMemoryStateSplitOperation operation1({ 1, 2 });
441  const LambdaEntryMemoryStateSplitOperation operation2({ 3, 4 });
442  const LambdaEntryMemoryStateSplitOperation operation3({ 1, 2, 3, 4 });
443  const TestOperation operation4({ memoryStateType }, { memoryStateType, memoryStateType });
444 
445  // Act & Assert
446  EXPECT_EQ(operation1, operation1);
447  EXPECT_NE(operation1, operation2); // Memory node identifiers differ
448  EXPECT_NE(operation1, operation3); // Number of results differ
449  EXPECT_NE(operation1, operation4); // Operation differs
450 }
451 
452 TEST(MemoryStateOperationTests, LambdaExitMemStateOperatorEquality)
453 {
454  using namespace jlm::llvm;
455  using namespace jlm::rvsdg;
456 
457  // Arrange
458  auto memoryStateType = MemoryStateType::Create();
459  const LambdaExitMemoryStateMergeOperation operation1({ 1, 2 });
460  const LambdaExitMemoryStateMergeOperation operation2({ 3, 4 });
461  const LambdaExitMemoryStateMergeOperation operation3({ 1, 2, 3, 4 });
462  TestOperation operation4({ memoryStateType, memoryStateType }, { memoryStateType });
463 
464  // Act & Assert
465  EXPECT_EQ(operation1, operation1);
466  EXPECT_NE(operation1, operation2); // Memory node identifiers differ
467  EXPECT_NE(operation1, operation3); // Number of results differ
468  EXPECT_NE(operation1, operation3); // Operation differs
469 }
470 
471 TEST(MemoryStateOperationTests, LambdaExitMemoryStateMergeNormalizeLoad)
472 {
473  using namespace jlm::llvm;
474  using namespace jlm::rvsdg;
475 
476  // Arrange
477  const auto bit32Type = BitType::Create(32);
478  const auto memoryStateType = MemoryStateType::Create();
479  const auto valueType = TestType::createValueType();
480 
481  Graph graph;
482  auto & memState1 = jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "memState1");
483  auto & memState2 = jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "memState1");
484  auto & size = jlm::rvsdg::GraphImport::Create(graph, bit32Type, "size");
485 
486  auto allocaResults = AllocaOperation::create(valueType, &size, 4);
487  auto & loadNode =
488  LoadNonVolatileOperation::CreateNode(*allocaResults[0], { allocaResults[1] }, valueType, 4);
489 
490  auto & lambdaExitMergeNode1 = LambdaExitMemoryStateMergeOperation::CreateNode(
491  graph.GetRootRegion(),
492  { loadNode.output(1), &memState1 },
493  { 1, 2 });
494 
495  auto & lambdaExitMergeNode2 = LambdaExitMemoryStateMergeOperation::CreateNode(
496  graph.GetRootRegion(),
497  { &memState2, &memState1 },
498  { 3, 2 });
499 
500  auto & x = GraphExport::Create(*lambdaExitMergeNode1.output(0), "x");
501  auto & y = GraphExport::Create(*lambdaExitMergeNode2.output(0), "y");
502  GraphExport::Create(*loadNode.output(0), "z");
503 
504  view(&graph.GetRootRegion(), stdout);
505 
506  // Act
507  const auto success = jlm::rvsdg::ReduceNode<LambdaExitMemoryStateMergeOperation>(
508  LambdaExitMemoryStateMergeOperation::NormalizeLoadFromAlloca,
509  *jlm::util::assertedCast<SimpleNode>(&lambdaExitMergeNode1));
510  graph.PruneNodes();
511 
512  view(&graph.GetRootRegion(), stdout);
513 
514  // Assert
515  EXPECT_TRUE(success);
516  EXPECT_EQ(graph.GetRootRegion().numNodes(), 4u);
517 
518  // The lambdaExitMergeNode1 should have been replaced
519  const auto [memStateMerge1Node, memStateMerge1Operation] =
520  TryGetSimpleNodeAndOptionalOp<LambdaExitMemoryStateMergeOperation>(*x.origin());
521  EXPECT_NE(memStateMerge1Node, &lambdaExitMergeNode1);
522  EXPECT_EQ(memStateMerge1Node->ninputs(), 2u);
523  EXPECT_EQ(memStateMerge1Node->input(0)->origin(), allocaResults[1]);
524  EXPECT_EQ(memStateMerge1Node->input(1)->origin(), &memState1);
525  EXPECT_EQ(memStateMerge1Operation->getMemoryNodeIds(), std::vector<MemoryNodeId>({ 1, 2 }));
526 
527  // The lambdaExitMergeNode2 should not have been replaced
528  const auto memStateMerge2Node = TryGetOwnerNode<Node>(*y.origin());
529  EXPECT_EQ(memStateMerge2Node, &lambdaExitMergeNode2);
530 }
531 
532 TEST(MemoryStateOperationTests, LambdaExitMemoryStateMergeNormalizeStore)
533 {
534  using namespace jlm::llvm;
535  using namespace jlm::rvsdg;
536 
537  // Arrange
538  const auto bit32Type = BitType::Create(32);
539  const auto memoryStateType = MemoryStateType::Create();
540  const auto valueType = TestType::createValueType();
541 
542  Graph graph;
543  auto & memState1 = jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "memState1");
544  auto & memState2 = jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "memState1");
545  auto & size = jlm::rvsdg::GraphImport::Create(graph, bit32Type, "size");
546 
547  auto allocaResults = AllocaOperation::create(valueType, &size, 4);
548  auto & storeNode =
549  StoreNonVolatileOperation::CreateNode(*allocaResults[0], size, { allocaResults[1] }, 4);
550 
551  auto & lambdaExitMergeNode1 = LambdaExitMemoryStateMergeOperation::CreateNode(
552  graph.GetRootRegion(),
553  { storeNode.output(0), &memState1 },
554  { 1, 2 });
555 
556  auto & lambdaExitMergeNode2 = LambdaExitMemoryStateMergeOperation::CreateNode(
557  graph.GetRootRegion(),
558  { &memState2, &memState1 },
559  { 3, 1 });
560 
561  auto & x = GraphExport::Create(*lambdaExitMergeNode1.output(0), "x");
562  auto & y = GraphExport::Create(*lambdaExitMergeNode2.output(0), "y");
563 
564  view(&graph.GetRootRegion(), stdout);
565 
566  // Act
567  const auto success = jlm::rvsdg::ReduceNode<LambdaExitMemoryStateMergeOperation>(
568  LambdaExitMemoryStateMergeOperation::NormalizeStoreToAlloca,
569  *jlm::util::assertedCast<SimpleNode>(&lambdaExitMergeNode1));
570  graph.PruneNodes();
571 
572  view(&graph.GetRootRegion(), stdout);
573 
574  // Assert
575  EXPECT_TRUE(success);
576  EXPECT_EQ(graph.GetRootRegion().numNodes(), 3u);
577 
578  // The lambdaExitMergeNode1 should have been replaced
579  const auto [memStateMerge1Node, memStateMerge1Operation] =
580  TryGetSimpleNodeAndOptionalOp<LambdaExitMemoryStateMergeOperation>(*x.origin());
581  EXPECT_NE(memStateMerge1Node, &lambdaExitMergeNode1);
582  EXPECT_EQ(memStateMerge1Node->ninputs(), 2u);
583  EXPECT_EQ(memStateMerge1Node->input(0)->origin(), allocaResults[1]);
584  EXPECT_EQ(memStateMerge1Node->input(1)->origin(), &memState1);
585  EXPECT_EQ(memStateMerge1Operation->getMemoryNodeIds(), std::vector<MemoryNodeId>({ 1, 2 }));
586 
587  // The lambdaExitMergeNode2 should not have been replaced
588  const auto memStateMerge2Node = TryGetOwnerNode<Node>(*y.origin());
589  EXPECT_EQ(memStateMerge2Node, &lambdaExitMergeNode2);
590 }
591 
592 TEST(MemoryStateOperationTests, LambdaExitMemoryStateMergeNormalizeAlloca)
593 {
594  using namespace jlm::llvm;
595  using namespace jlm::rvsdg;
596 
597  // Arrange
598  const auto bit32Type = BitType::Create(32);
599  const auto memoryStateType = MemoryStateType::Create();
600  const auto valueType = TestType::createValueType();
601 
602  Graph graph;
603  auto & memState1 = jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "memState1");
604  auto & memState2 = jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "memState1");
605  auto & size = jlm::rvsdg::GraphImport::Create(graph, bit32Type, "size");
606 
607  auto allocaResults = AllocaOperation::create(valueType, &size, 4);
608 
609  auto & lambdaExitMergeNode1 = LambdaExitMemoryStateMergeOperation::CreateNode(
610  graph.GetRootRegion(),
611  { allocaResults[1], &memState1 },
612  { 1, 2 });
613 
614  auto & lambdaExitMergeNode2 = LambdaExitMemoryStateMergeOperation::CreateNode(
615  graph.GetRootRegion(),
616  { &memState2, &memState1 },
617  { 3, 2 });
618 
619  auto & x = GraphExport::Create(*lambdaExitMergeNode1.output(0), "x");
620  auto & y = GraphExport::Create(*lambdaExitMergeNode2.output(0), "y");
621 
622  view(&graph.GetRootRegion(), stdout);
623 
624  // Act
625  const auto success = jlm::rvsdg::ReduceNode<LambdaExitMemoryStateMergeOperation>(
626  LambdaExitMemoryStateMergeOperation::NormalizeAlloca,
627  *jlm::util::assertedCast<SimpleNode>(&lambdaExitMergeNode1));
628  graph.PruneNodes();
629 
630  view(&graph.GetRootRegion(), stdout);
631 
632  // Assert
633  EXPECT_TRUE(success);
634  EXPECT_EQ(graph.GetRootRegion().numNodes(), 3u);
635 
636  // The lambdaExitMergeNode1 should have been replaced
637  const auto [memStateMerge1Node, memStateMerge1Operation] =
638  TryGetSimpleNodeAndOptionalOp<LambdaExitMemoryStateMergeOperation>(*x.origin());
639  EXPECT_NE(memStateMerge1Node, &lambdaExitMergeNode1);
640  EXPECT_EQ(memStateMerge1Node->ninputs(), 2u);
641  EXPECT_EQ(memStateMerge1Operation->getMemoryNodeIds(), std::vector<MemoryNodeId>({ 1, 2 }));
642  const auto undefNode = TryGetOwnerNode<Node>(*memStateMerge1Node->input(0)->origin());
643  EXPECT_NE(undefNode, nullptr);
644  EXPECT_EQ(memStateMerge1Node->input(1)->origin(), &memState1);
645 
646  // The lambdaExitMergeNode2 should not have been replaced
647  const auto memStateMerge2Node = TryGetOwnerNode<Node>(*y.origin());
648  EXPECT_EQ(memStateMerge2Node, &lambdaExitMergeNode2);
649 }
650 
651 TEST(MemoryStateOperationTests, CallEntryMemStateOperatorEquality)
652 {
653  using namespace jlm::llvm;
654  using namespace jlm::rvsdg;
655 
656  // Arrange
657  auto memoryStateType = MemoryStateType::Create();
658  const CallEntryMemoryStateMergeOperation operation1({ 1, 2 });
659  const CallEntryMemoryStateMergeOperation operation2({ 3, 4 });
660  const CallEntryMemoryStateMergeOperation operation3({ 1, 2, 3, 4 });
661  TestOperation operation4({ memoryStateType, memoryStateType }, { memoryStateType });
662 
663  // Act & Assert
664  EXPECT_EQ(operation1, operation1);
665  EXPECT_NE(operation1, operation2); // Memory node identifiers differ
666  EXPECT_NE(operation1, operation3); // Number of operands differ
667  EXPECT_NE(operation1, operation3); // Operation differs
668 }
669 
670 TEST(MemoryStateOperationTests, CallExitMemStateOperatorEquality)
671 {
672  using namespace jlm::llvm;
673  using namespace jlm::rvsdg;
674 
675  // Arrange
676  auto memoryStateType = MemoryStateType::Create();
677  const CallExitMemoryStateSplitOperation operation1({ 1, 2 });
678  const CallExitMemoryStateSplitOperation operation2({ 3, 4 });
679  const CallExitMemoryStateSplitOperation operation3({ 1, 2, 3, 4 });
680  const TestOperation operation4({ memoryStateType }, { memoryStateType, memoryStateType });
681 
682  // Act & Assert
683  EXPECT_EQ(operation1, operation1);
684  EXPECT_NE(operation1, operation2); // Memory node identifiers differ
685  EXPECT_NE(operation1, operation3); // Number of memory node identifiers differ
686  EXPECT_NE(operation1, operation4); // Operation differs
687 }
TEST
TEST(MemoryStateOperationTests, MemoryStateSplitEquality)
Definition: MemoryStateOperationTests.cpp:18
jlm::llvm::AllocaOperation::create
static std::vector< rvsdg::Output * > create(std::shared_ptr< const rvsdg::Type > allocatedType, rvsdg::Output *count, const size_t alignment)
Definition: alloca.hpp:131
jlm::llvm::LambdaExitMemoryStateMergeOperation::NormalizeLoadFromAlloca
static std::optional< std::vector< rvsdg::Output * > > NormalizeLoadFromAlloca(const LambdaExitMemoryStateMergeOperation &operation, const std::vector< rvsdg::Output * > &operands)
Definition: MemoryStateOperations.cpp:438
jlm::llvm::LambdaExitMemoryStateMergeOperation::NormalizeStoreToAlloca
static std::optional< std::vector< rvsdg::Output * > > NormalizeStoreToAlloca(const LambdaExitMemoryStateMergeOperation &operation, const std::vector< rvsdg::Output * > &operands)
Definition: MemoryStateOperations.cpp:477
jlm::llvm::LambdaExitMemoryStateMergeOperation::CreateNode
static rvsdg::SimpleNode & CreateNode(rvsdg::Region &region, const std::vector< rvsdg::Output * > &operands, const std::vector< MemoryNodeId > &memoryNodeIds)
Definition: MemoryStateOperations.hpp:468
jlm::llvm::LambdaExitMemoryStateMergeOperation::NormalizeAlloca
static std::optional< std::vector< rvsdg::Output * > > NormalizeAlloca(const LambdaExitMemoryStateMergeOperation &operation, const std::vector< rvsdg::Output * > &operands)
Definition: MemoryStateOperations.cpp:517
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::MemoryStateJoinOperation::NormalizeDuplicateOperands
static std::optional< std::vector< rvsdg::Output * > > NormalizeDuplicateOperands(const MemoryStateJoinOperation &operation, const std::vector< rvsdg::Output * > &operands)
Removes duplicated operands from the MemoryStateJoinOperation.
Definition: MemoryStateOperations.cpp:167
jlm::llvm::MemoryStateJoinOperation::NormalizeNestedJoins
static std::optional< std::vector< rvsdg::Output * > > NormalizeNestedJoins(const MemoryStateJoinOperation &operation, const std::vector< rvsdg::Output * > &operands)
Fuses nested MemoryStateJoinOperation nodes into a single node.
Definition: MemoryStateOperations.cpp:195
jlm::llvm::MemoryStateJoinOperation::NormalizeSingleOperand
static std::optional< std::vector< rvsdg::Output * > > NormalizeSingleOperand(const MemoryStateJoinOperation &operation, const std::vector< rvsdg::Output * > &operands)
Removes the MemoryStateJoinOperation as it has only a single operand, i.e., no joining is performed.
Definition: MemoryStateOperations.cpp:156
jlm::llvm::MemoryStateJoinOperation::CreateNode
static rvsdg::SimpleNode & CreateNode(const std::vector< rvsdg::Output * > &operands)
Definition: MemoryStateOperations.hpp:194
jlm::llvm::MemoryStateMergeOperation::NormalizeNestedMerges
static std::optional< std::vector< rvsdg::Output * > > NormalizeNestedMerges(const MemoryStateMergeOperation &operation, const std::vector< rvsdg::Output * > &operands)
Fuses nested merges into a single merge.
Definition: MemoryStateOperations.cpp:93
jlm::llvm::MemoryStateMergeOperation::CreateNode
static rvsdg::SimpleNode & CreateNode(const std::vector< rvsdg::Output * > &operands)
Definition: MemoryStateOperations.hpp:108
jlm::llvm::MemoryStateMergeOperation::Create
static rvsdg::Output * Create(const std::vector< rvsdg::Output * > &operands)
Definition: MemoryStateOperations.hpp:114
jlm::llvm::MemoryStateMergeOperation::NormalizeMergeSplit
static std::optional< std::vector< rvsdg::Output * > > NormalizeMergeSplit(const MemoryStateMergeOperation &operation, const std::vector< rvsdg::Output * > &operands)
Fuses nested splits into a single merge.
Definition: MemoryStateOperations.cpp:108
jlm::llvm::MemoryStateMergeOperation::NormalizeSingleOperand
static std::optional< std::vector< rvsdg::Output * > > NormalizeSingleOperand(const MemoryStateMergeOperation &operation, const std::vector< rvsdg::Output * > &operands)
Removes the MemoryStateMergeOperation as it has only a single operand, i.e., no merging is performed.
Definition: MemoryStateOperations.cpp:38
jlm::llvm::MemoryStateMergeOperation::NormalizeDuplicateOperands
static std::optional< std::vector< rvsdg::Output * > > NormalizeDuplicateOperands(const MemoryStateMergeOperation &operation, const std::vector< rvsdg::Output * > &operands)
Removes duplicated operands from the MemoryStateMergeOperation.
Definition: MemoryStateOperations.cpp:49
jlm::llvm::MemoryStateSplitOperation::NormalizeNestedSplits
static std::optional< std::vector< rvsdg::Output * > > NormalizeNestedSplits(const MemoryStateSplitOperation &operation, const std::vector< rvsdg::Output * > &operands)
Fuses nested splits into a single split.
Definition: MemoryStateOperations.cpp:244
jlm::llvm::MemoryStateSplitOperation::NormalizeSingleResult
static std::optional< std::vector< rvsdg::Output * > > NormalizeSingleResult(const MemoryStateSplitOperation &operation, const std::vector< rvsdg::Output * > &operands)
Removes the MemoryStateSplitOperation as it has only a single result, i.e., no splitting is performed...
Definition: MemoryStateOperations.cpp:231
jlm::llvm::MemoryStateSplitOperation::NormalizeSplitMerge
static std::optional< std::vector< rvsdg::Output * > > NormalizeSplitMerge(const MemoryStateSplitOperation &operation, const std::vector< rvsdg::Output * > &operands)
Removes an idempotent split-merge pair.
Definition: MemoryStateOperations.cpp:270
jlm::llvm::MemoryStateSplitOperation::CreateNode
static rvsdg::SimpleNode & CreateNode(rvsdg::Output &operand, const size_t numResults)
Definition: MemoryStateOperations.hpp:266
jlm::llvm::MemoryStateType::Create
static std::shared_ptr< const MemoryStateType > Create()
Definition: types.cpp:379
jlm::llvm::StoreNonVolatileOperation::CreateNode
static rvsdg::SimpleNode & CreateNode(rvsdg::Output &address, rvsdg::Output &value, const std::vector< rvsdg::Output * > &memoryStates, size_t alignment)
Definition: Store.hpp:323
jlm::rvsdg::GraphExport::Create
static GraphExport & Create(Output &origin, std::string name)
Definition: graph.cpp:62
jlm::rvsdg::GraphImport::Create
static GraphImport & Create(Graph &graph, std::shared_ptr< const rvsdg::Type > type, std::string name)
Definition: graph.cpp:36
jlm::rvsdg::Graph::PruneNodes
void PruneNodes()
Definition: graph.hpp:116
jlm::rvsdg::Graph::GetRootRegion
Region & GetRootRegion() const noexcept
Definition: graph.hpp:99
jlm::rvsdg::Region::numNodes
size_t numNodes() const noexcept
Definition: region.hpp:481
jlm::llvm
Global memory state passed between functions.
Definition: IpGraphToLlvmConverter.cpp:36
jlm::rvsdg::view
std::string view(const rvsdg::Region *region)
Definition: view.cpp:142
Generated by doxygen 1.9.1