Jlm
RegionTests.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/rvsdg/TestNodes.hpp>
9 #include <jlm/rvsdg/TestOperations.hpp>
10 #include <jlm/rvsdg/TestType.hpp>
11 #include <jlm/util/AnnotationMap.hpp>
12 
13 #include <algorithm>
14 #include <cassert>
15 
16 TEST(RegionTests, IteratorRanges)
17 {
18  using namespace jlm::rvsdg;
19 
20  // Arrange
21  auto valueType = jlm::rvsdg::TestType::createValueType();
22 
23  jlm::rvsdg::Graph graph;
24 
25  auto structuralNode = TestStructuralNode::create(&graph.GetRootRegion(), 1);
26  auto & subregion = *structuralNode->subregion(0);
27  auto & constSubregion = *static_cast<const jlm::rvsdg::Region *>(structuralNode->subregion(0));
28 
29  auto & argument0 = *structuralNode->addArguments(valueType).argument[0];
30  auto & argument1 = *structuralNode->addArguments(valueType).argument[0];
31 
32  auto topNode0 = TestOperation::createNode(&subregion, {}, { valueType });
33  auto node0 = TestOperation::createNode(&subregion, { &argument0 }, { valueType });
34  auto node1 = TestOperation::createNode(&subregion, { &argument1 }, { valueType });
35  auto bottomNode0 =
36  TestOperation::createNode(&subregion, { &argument0, &argument1 }, { valueType });
37 
38  const auto outputVar0 = structuralNode->addResults({ topNode0->output(0) });
39  const auto outputVar1 = structuralNode->addResults({ node0->output(0) });
40  const auto outputVar2 = structuralNode->addResults({ node1->output(0) });
41 
42  // Act & Assert
43  auto numArguments = std::distance(subregion.Arguments().begin(), subregion.Arguments().end());
44  EXPECT_EQ(numArguments, 2);
45  for (auto & argument : constSubregion.Arguments())
46  {
47  EXPECT_TRUE(argument == &argument0 || argument == &argument1);
48  }
49 
50  auto numTopNodes = std::distance(subregion.TopNodes().begin(), subregion.TopNodes().end());
51  EXPECT_EQ(numTopNodes, 1);
52  for (auto & topNode : constSubregion.TopNodes())
53  {
54  EXPECT_EQ(&topNode, topNode0);
55  }
56 
57  auto numNodes = std::distance(subregion.Nodes().begin(), subregion.Nodes().end());
58  EXPECT_EQ(numNodes, 4);
59  for (auto & node : constSubregion.Nodes())
60  {
61  EXPECT_TRUE(&node == topNode0 || &node == node0 || &node == node1 || &node == bottomNode0);
62  }
63 
64  auto numBottomNodes =
65  std::distance(subregion.BottomNodes().begin(), subregion.BottomNodes().end());
66  EXPECT_EQ(numBottomNodes, 1);
67  for (auto & bottomNode : constSubregion.BottomNodes())
68  {
69  EXPECT_EQ(&bottomNode, bottomNode0);
70  }
71 
72  auto numResults = std::distance(subregion.Results().begin(), subregion.Results().end());
73  EXPECT_EQ(numResults, 3);
74  for (auto & result : constSubregion.Results())
75  {
76  EXPECT_TRUE(
77  result == outputVar0.result[0] || result == outputVar1.result[0]
78  || result == outputVar2.result[0]);
79  }
80 }
81 
82 TEST(RegionTests, Contains)
83 {
84  using namespace jlm::rvsdg;
85 
86  // Arrange
87  auto valueType = jlm::rvsdg::TestType::createValueType();
88 
89  jlm::rvsdg::Graph graph;
90  auto import = &jlm::rvsdg::GraphImport::Create(graph, valueType, "import");
91 
92  auto structuralNode1 = TestStructuralNode::create(&graph.GetRootRegion(), 1);
93  auto inputVar1 = structuralNode1->addInputWithArguments(*import);
94  TestUnaryOperation::create(
95  structuralNode1->subregion(0),
96  valueType,
97  inputVar1.argument[0],
98  valueType);
99 
100  auto structuralNode2 = TestStructuralNode::create(&graph.GetRootRegion(), 1);
101  auto inputVar2 = structuralNode2->addInputWithArguments(*import);
102  TestBinaryOperation::create(valueType, valueType, inputVar2.argument[0], inputVar2.argument[0]);
103 
104  // Act & Assert
105  EXPECT_TRUE(
106  jlm::rvsdg::Region::ContainsNodeType<TestStructuralNode>(graph.GetRootRegion(), false));
107  EXPECT_TRUE(
108  jlm::rvsdg::Region::ContainsOperation<TestUnaryOperation>(graph.GetRootRegion(), true));
109  EXPECT_TRUE(
110  jlm::rvsdg::Region::ContainsOperation<TestBinaryOperation>(graph.GetRootRegion(), true));
111  EXPECT_TRUE(!jlm::rvsdg::Region::ContainsOperation<TestOperation>(graph.GetRootRegion(), true));
112 }
113 
114 TEST(RegionTests, IsRootRegion)
115 {
116  using namespace jlm::rvsdg;
117 
118  // Arrange
119  jlm::rvsdg::Graph graph;
120 
121  auto structuralNode = TestStructuralNode::create(&graph.GetRootRegion(), 1);
122 
123  // Act & Assert
124  EXPECT_TRUE(graph.GetRootRegion().IsRootRegion());
125  EXPECT_FALSE(structuralNode->subregion(0)->IsRootRegion());
126 }
127 
128 TEST(RegionTests, NumRegions_EmptyRvsdg)
129 {
130  using namespace jlm::rvsdg;
131 
132  // Arrange
133  Graph graph;
134 
135  // Act & Assert
136  EXPECT_EQ(Region::NumRegions(graph.GetRootRegion()), 1u);
137 }
138 
139 TEST(RegionTests, NumRegions_NonEmptyRvsdg)
140 {
141  using namespace jlm::rvsdg;
142 
143  // Arrange
144  const Graph graph;
145  auto structuralNode = TestStructuralNode::create(&graph.GetRootRegion(), 4);
146  TestStructuralNode::create(structuralNode->subregion(0), 2);
147  TestStructuralNode::create(structuralNode->subregion(3), 5);
148 
149  // Act & Assert
150  constexpr unsigned int numTotalSubRegions = 1 + 4 + 2 + 5;
151  EXPECT_EQ(Region::NumRegions(graph.GetRootRegion()), numTotalSubRegions);
152 }
153 
154 TEST(RegionTests, RemoveResults)
155 {
156  using namespace jlm::rvsdg;
157 
158  // Arrange
159  const auto valueType = TestType::createValueType();
160 
161  Graph rvsdg;
162  auto & rootRegion = rvsdg.GetRootRegion();
163  const RecordingObserver observer(rootRegion);
164 
165  auto & i0 = GraphImport::Create(rvsdg, valueType, "i0");
166  auto & i1 = GraphImport::Create(rvsdg, valueType, "i1");
167  auto & i2 = GraphImport::Create(rvsdg, valueType, "i2");
168  auto & i3 = GraphImport::Create(rvsdg, valueType, "i3");
169  auto & i4 = GraphImport::Create(rvsdg, valueType, "i4");
170  auto & i5 = GraphImport::Create(rvsdg, valueType, "i5");
171  auto & i6 = GraphImport::Create(rvsdg, valueType, "i6");
172  auto & i7 = GraphImport::Create(rvsdg, valueType, "i7");
173  auto & i8 = GraphImport::Create(rvsdg, valueType, "i8");
174  auto & i9 = GraphImport::Create(rvsdg, valueType, "i9");
175 
176  GraphExport::Create(i0, "x0");
177  GraphExport::Create(i1, "x1");
178  GraphExport::Create(i2, "x2");
179  GraphExport::Create(i3, "x3");
180  GraphExport::Create(i4, "x4");
181  GraphExport::Create(i5, "x5");
182  GraphExport::Create(i6, "x6");
183  GraphExport::Create(i7, "x7");
184  GraphExport::Create(i8, "x8");
185  GraphExport::Create(i9, "x9");
186 
187  // Act & Arrange
188  EXPECT_EQ(rvsdg.GetRootRegion().nresults(), 10u);
189 
190  // Remove all results that have an even index
191  size_t numRemovedResults = rootRegion.RemoveResults({ 0, 2, 4, 6, 8 });
192  EXPECT_EQ(numRemovedResults, 5u);
193  EXPECT_EQ(rootRegion.nresults(), 5u);
194  EXPECT_EQ(rootRegion.result(0)->origin(), &i1);
195  EXPECT_EQ(rootRegion.result(1)->origin(), &i3);
196  EXPECT_EQ(rootRegion.result(2)->origin(), &i5);
197  EXPECT_EQ(rootRegion.result(3)->origin(), &i7);
198  EXPECT_EQ(rootRegion.result(4)->origin(), &i9);
199  EXPECT_EQ(i0.nusers(), 0u);
200  EXPECT_EQ(i2.nusers(), 0u);
201  EXPECT_EQ(i4.nusers(), 0u);
202  EXPECT_EQ(i6.nusers(), 0u);
203  EXPECT_EQ(i8.nusers(), 0u);
204  EXPECT_EQ(observer.destroyedInputIndices(), std::vector<size_t>({ 0, 2, 4, 6, 8 }));
205 
206  // Remove no result
207  numRemovedResults = rootRegion.RemoveResults({});
208  EXPECT_EQ(numRemovedResults, 0u);
209  EXPECT_EQ(rootRegion.nresults(), 5u);
210  EXPECT_EQ(observer.destroyedInputIndices(), std::vector<size_t>({ 0, 2, 4, 6, 8 }));
211 
212  // Remove non-existent input
213  numRemovedResults = rootRegion.RemoveResults({ 15 });
214  EXPECT_EQ(numRemovedResults, 0u);
215  EXPECT_EQ(rootRegion.nresults(), 5u);
216  EXPECT_EQ(observer.destroyedInputIndices(), std::vector<size_t>({ 0, 2, 4, 6, 8 }));
217 
218  // Remove remaining results
219  numRemovedResults = rootRegion.RemoveResults({ 0, 1, 2, 3, 4 });
220  EXPECT_EQ(numRemovedResults, 5u);
221  EXPECT_EQ(rootRegion.nresults(), 0u);
222  EXPECT_EQ(i1.nusers(), 0u);
223  EXPECT_EQ(i3.nusers(), 0u);
224  EXPECT_EQ(i5.nusers(), 0u);
225  EXPECT_EQ(i7.nusers(), 0u);
226  EXPECT_EQ(i9.nusers(), 0u);
227  EXPECT_EQ(
228  observer.destroyedInputIndices(),
229  std::vector<size_t>({ 0, 2, 4, 6, 8, 0, 1, 2, 3, 4 }));
230 }
231 
232 TEST(RegionTests, RemoveArguments)
233 {
234  using namespace jlm::rvsdg;
235 
236  // Arrange
237  Graph rvsdg;
238  auto & rootRegion = rvsdg.GetRootRegion();
239 
240  auto valueType = jlm::rvsdg::TestType::createValueType();
241  auto argument0 = &GraphImport::Create(rvsdg, valueType, "argument0");
242  auto argument1 = &GraphImport::Create(rvsdg, valueType, "argument1");
243  auto argument2 = &GraphImport::Create(rvsdg, valueType, "argument2");
244  auto argument3 = &GraphImport::Create(rvsdg, valueType, "argument3");
245  auto argument4 = &GraphImport::Create(rvsdg, valueType, "argument4");
246  auto argument5 = &GraphImport::Create(rvsdg, valueType, "argument5");
247  auto argument6 = &GraphImport::Create(rvsdg, valueType, "argument6");
248  auto argument7 = &GraphImport::Create(rvsdg, valueType, "argument7");
249  auto argument8 = &GraphImport::Create(rvsdg, valueType, "argument8");
250  auto argument9 = &GraphImport::Create(rvsdg, valueType, "argument9");
251 
252  auto node = TestOperation::createNode(
253  &rvsdg.GetRootRegion(),
254  { argument2, argument4, argument6 },
255  { valueType });
256 
257  // Act & Arrange
258  EXPECT_EQ(rootRegion.narguments(), 10u);
259  EXPECT_EQ(argument0->index(), 0u);
260  EXPECT_EQ(argument1->index(), 1u);
261  EXPECT_EQ(argument2->index(), 2u);
262  EXPECT_EQ(argument3->index(), 3u);
263  EXPECT_EQ(argument4->index(), 4u);
264  EXPECT_EQ(argument5->index(), 5u);
265  EXPECT_EQ(argument6->index(), 6u);
266  EXPECT_EQ(argument7->index(), 7u);
267  EXPECT_EQ(argument8->index(), 8u);
268  EXPECT_EQ(argument9->index(), 9u);
269 
270  // Remove all arguments that have an even index
271  size_t numRemovedArguments = rootRegion.RemoveArguments({ 0, 2, 4, 6, 8 });
272  // We expect only argument0 and argument8 to be removed, as argument2, argument4, and
273  // argument6 are not dead
274  EXPECT_EQ(numRemovedArguments, 2u);
275  EXPECT_EQ(rootRegion.narguments(), 8u);
276  EXPECT_EQ(argument1->index(), 0u);
277  EXPECT_EQ(argument2->index(), 1u);
278  EXPECT_EQ(argument3->index(), 2u);
279  EXPECT_EQ(argument4->index(), 3u);
280  EXPECT_EQ(argument5->index(), 4u);
281  EXPECT_EQ(argument6->index(), 5u);
282  EXPECT_EQ(argument7->index(), 6u);
283  EXPECT_EQ(argument9->index(), 7u);
284 
285  // Reassign arguments to avoid mental gymnastics
286  argument0 = argument1;
287  argument1 = argument2;
288  argument2 = argument3;
289  argument3 = argument4;
290  argument4 = argument5;
291  argument5 = argument6;
292  argument6 = argument7;
293  argument7 = argument9;
294 
295  // Remove all users from the arguments
296  rootRegion.removeNode(node);
297 
298  // Remove all arguments that have an even index
299  numRemovedArguments = rootRegion.RemoveArguments({ 0, 2, 4, 6 });
300  // We expect argument0, argument2, argument4, and argument6 to be removed
301  EXPECT_EQ(numRemovedArguments, 4u);
302  EXPECT_EQ(rootRegion.narguments(), 4u);
303  EXPECT_EQ(argument1->index(), 0u);
304  EXPECT_EQ(argument3->index(), 1u);
305  EXPECT_EQ(argument5->index(), 2u);
306  EXPECT_EQ(argument7->index(), 3u);
307 
308  // Reassign arguments to avoid mental gymnastics
309  argument0 = argument1;
310  argument1 = argument3;
311  argument2 = argument5;
312  argument3 = argument7;
313 
314  // Remove no argument
315  numRemovedArguments = rootRegion.RemoveArguments({});
316  EXPECT_EQ(numRemovedArguments, 0u);
317  EXPECT_EQ(rootRegion.narguments(), 4u);
318  EXPECT_EQ(argument0->index(), 0u);
319  EXPECT_EQ(argument1->index(), 1u);
320  EXPECT_EQ(argument2->index(), 2u);
321  EXPECT_EQ(argument3->index(), 3u);
322 
323  // Remove non-existent argument
324  numRemovedArguments = rootRegion.RemoveArguments({ 15 });
325  EXPECT_EQ(numRemovedArguments, 0u);
326  EXPECT_EQ(rootRegion.narguments(), 4u);
327 
328  // Remove all remaining arguments
329  numRemovedArguments = rootRegion.RemoveArguments({ 0, 1, 2, 3 });
330  EXPECT_EQ(numRemovedArguments, 4u);
331  EXPECT_EQ(rootRegion.narguments(), 0u);
332 }
333 
334 TEST(RegionTests, PruneArguments)
335 {
336  using namespace jlm::rvsdg;
337 
338  // Arrange
339  auto valueType = TestType::createValueType();
340 
341  Graph rvsdg;
342  auto structuralNode = TestStructuralNode::create(&rvsdg.GetRootRegion(), 1);
343 
344  auto & argument0 = *structuralNode->addArguments(valueType).argument[0];
345  structuralNode->addArguments(valueType);
346  auto & argument2 = *structuralNode->addArguments(valueType).argument[0];
347 
348  auto node = TestOperation::createNode(
349  structuralNode->subregion(0),
350  { &argument0, &argument2 },
351  { valueType });
352 
353  // Act & Arrange
354  EXPECT_EQ(structuralNode->subregion(0)->narguments(), 3u);
355 
356  size_t numRemovedArguments = structuralNode->subregion(0)->PruneArguments();
357  EXPECT_EQ(numRemovedArguments, 1u);
358  EXPECT_EQ(structuralNode->subregion(0)->narguments(), 2u);
359  EXPECT_EQ(argument0.index(), 0u);
360  EXPECT_EQ(argument2.index(), 1u);
361 
362  structuralNode->subregion(0)->removeNode(node);
363  numRemovedArguments = structuralNode->subregion(0)->PruneArguments();
364  EXPECT_EQ(numRemovedArguments, 2u);
365  EXPECT_EQ(structuralNode->subregion(0)->narguments(), 0u);
366 }
367 
368 TEST(RegionTests, ToTree_EmptyRvsdg)
369 {
370  using namespace jlm::rvsdg;
371 
372  // Arrange
373  Graph rvsdg;
374 
375  // Act
376  auto tree = Region::ToTree(rvsdg.GetRootRegion());
377  std::cout << tree << std::flush;
378 
379  // Assert
380  EXPECT_EQ(tree, "RootRegion\n");
381 }
382 
383 TEST(RegionTests, ToTree_EmptyRvsdgWithAnnotations)
384 {
385  using namespace jlm::rvsdg;
386  using namespace jlm::util;
387 
388  // Arrange
389  Graph rvsdg;
390 
391  AnnotationMap annotationMap;
392  annotationMap.AddAnnotation(
393  &rvsdg.GetRootRegion(),
394  Annotation("NumNodes", static_cast<uint64_t>(rvsdg.GetRootRegion().numNodes())));
395 
396  // Act
397  auto tree = Region::ToTree(rvsdg.GetRootRegion(), annotationMap);
398  std::cout << tree << std::flush;
399 
400  // Assert
401  EXPECT_EQ(tree, "RootRegion NumNodes:0\n");
402 }
403 
404 TEST(RegionTests, ToTree_RvsdgWithStructuralNodes)
405 {
406  using namespace jlm::rvsdg;
407 
408  // Arrange
409  Graph rvsdg;
410  auto structuralNode = TestStructuralNode::create(&rvsdg.GetRootRegion(), 2);
411  TestStructuralNode::create(structuralNode->subregion(0), 1);
412  TestStructuralNode::create(structuralNode->subregion(1), 3);
413 
414  // Act
415  auto tree = Region::ToTree(rvsdg.GetRootRegion());
416  std::cout << tree << std::flush;
417 
418  // Assert
419  auto numLines = std::count(tree.begin(), tree.end(), '\n');
420 
421  // We should find '\n' 10 times: 1 root region + 3 structural nodes + 6 subregions
422  EXPECT_EQ(numLines, 10);
423 
424  // Check that the last line printed looks accordingly
425  auto lastLine = std::string("----Region[2]\n");
426  EXPECT_EQ(tree.compare(tree.size() - lastLine.size(), lastLine.size(), lastLine), 0);
427 }
428 
429 TEST(RegionTests, ToTree_RvsdgWithStructuralNodesAndAnnotations)
430 {
431  using namespace jlm::rvsdg;
432  using namespace jlm::util;
433 
434  // Arrange
435  Graph rvsdg;
436  auto structuralNode1 = TestStructuralNode::create(&rvsdg.GetRootRegion(), 2);
437  auto structuralNode2 = TestStructuralNode::create(structuralNode1->subregion(1), 3);
438  auto subregion2 = structuralNode2->subregion(2);
439 
440  AnnotationMap annotationMap;
441  annotationMap.AddAnnotation(
442  subregion2,
443  Annotation("NumNodes", static_cast<uint64_t>(subregion2->numNodes())));
444  annotationMap.AddAnnotation(
445  subregion2,
446  Annotation("NumArguments", static_cast<uint64_t>(subregion2->narguments())));
447 
448  // Act
449  auto tree = Region::ToTree(rvsdg.GetRootRegion(), annotationMap);
450  std::cout << tree << std::flush;
451 
452  // Assert
453  auto numLines = std::count(tree.begin(), tree.end(), '\n');
454 
455  // We should find '\n' 8 times: 1 root region + 2 structural nodes + 5 subregions
456  EXPECT_EQ(numLines, 8);
457 
458  // Check that the last line printed looks accordingly
459  auto lastLine = std::string("----Region[2] NumNodes:0 NumArguments:0\n");
460  EXPECT_EQ(tree.compare(tree.size() - lastLine.size(), lastLine.size(), lastLine), 0);
461 }
462 
463 TEST(RegionTests, toJson_EmptyRvsdg)
464 {
465  using namespace jlm::rvsdg;
466 
467  // Arrange
468  Graph rvsdg;
469 
470  // Act
471  const auto json = Region::toJson(rvsdg.GetRootRegion());
472  std::cout << json << std::flush;
473 
474  // Assert
475  EXPECT_EQ(json, "{}");
476 }
477 
478 TEST(RegionTests, toJson_EmptyRvsdgWithAnnotations)
479 {
480  using namespace jlm::rvsdg;
481  using namespace jlm::util;
482 
483  // Arrange
484  Graph rvsdg;
485 
486  AnnotationMap annotationMap;
487  annotationMap.AddAnnotation(
488  &rvsdg.GetRootRegion(),
489  Annotation("NumNodes", static_cast<uint64_t>(rvsdg.GetRootRegion().numNodes())));
490 
491  // Act
492  const auto json = Region::toJson(rvsdg.GetRootRegion(), annotationMap);
493  std::cout << json << std::flush;
494 
495  // Assert
496  EXPECT_EQ(json, "{\"NumNodes\":0}");
497 }
498 
499 TEST(RegionTests, toJson_RvsdgWithStructuralNodes)
500 {
501  using namespace jlm::rvsdg;
502  using namespace jlm::util;
503 
504  // Arrange
505  Graph rvsdg;
506  auto structuralNode = TestStructuralNode::create(&rvsdg.GetRootRegion(), 2);
507  TestStructuralNode::create(structuralNode->subregion(0), 1);
508  TestStructuralNode::create(structuralNode->subregion(1), 1);
509  TestStructuralNode::create(structuralNode->subregion(1), 3);
510 
511  AnnotationMap annotationMap;
512  annotationMap.AddAnnotation(
513  structuralNode->subregion(1),
514  { "RegionId", structuralNode->subregion(1)->getRegionId() });
515 
516  // Act
517  const auto json = Region::toJson(rvsdg.GetRootRegion(), annotationMap);
518  std::cout << json << std::flush;
519 
520  // Assert
521  EXPECT_EQ(
522  json,
523  "{\"StructuralNodes\":[{\"DebugString\":\"TestStructuralOperation\",\"Subregions\":"
524  "[{\"StructuralNodes\":[{\"DebugString\":\"TestStructuralOperation\",\"Subregions\":"
525  "[{}]}]},{\"RegionId\":2,\"StructuralNodes\":[{\"DebugString\":"
526  "\"TestStructuralOperation\",\"Subregions\":[{}]},{\"DebugString\":"
527  "\"TestStructuralOperation\",\"Subregions\":[{},{},{}]}]}]}]}");
528 }
529 
530 TEST(RegionTests, toJson_RvsdgWithStructuralNodesAndAnnotations)
531 {
532  using namespace jlm::rvsdg;
533  using namespace jlm::util;
534 
535  // Arrange
536  Graph rvsdg;
537  auto structuralNode1 = TestStructuralNode::create(&rvsdg.GetRootRegion(), 2);
538  auto structuralNode2 = TestStructuralNode::create(structuralNode1->subregion(1), 3);
539  auto subregion2 = structuralNode2->subregion(2);
540 
541  AnnotationMap annotationMap;
542  annotationMap.AddAnnotation(
543  subregion2,
544  Annotation("NumNodes", static_cast<uint64_t>(subregion2->numNodes())));
545  annotationMap.AddAnnotation(
546  subregion2,
547  Annotation("NumArguments", static_cast<uint64_t>(subregion2->narguments())));
548 
549  // Act
550  const auto json = Region::toJson(rvsdg.GetRootRegion(), annotationMap);
551  std::cout << json << std::flush;
552 
553  // Assert
554  EXPECT_EQ(
555  json,
556  "{\"StructuralNodes\":[{\"DebugString\":\"TestStructuralOperation\",\"Subregions\":"
557  "[{},{\"StructuralNodes\":[{\"DebugString\":\"TestStructuralOperation\",\"Subregions\""
558  ":[{},{},{\"NumNodes\":0,\"NumArguments\":0}]}]}]}]}");
559 }
560 
561 TEST(RegionTests, BottomNodeTests)
562 {
563  using namespace jlm::rvsdg;
564 
565  auto valueType = TestType::createValueType();
566 
567  // Arrange
568  Graph rvsdg;
569 
570  // Act & Assert
571  // A newly created node without any users should automatically be added to the bottom nodes
572  auto structuralNode = TestStructuralNode::create(&rvsdg.GetRootRegion(), 1);
573  EXPECT_TRUE(structuralNode->IsDead());
574  EXPECT_EQ(rvsdg.GetRootRegion().numBottomNodes(), 1u);
575  EXPECT_EQ(&*(rvsdg.GetRootRegion().BottomNodes().begin()), structuralNode);
576 
577  // The node cedes to be dead
578  auto & output = structuralNode->addOutputOnly(valueType);
579  GraphExport::Create(output, "x");
580  EXPECT_FALSE(structuralNode->IsDead());
581  EXPECT_EQ(rvsdg.GetRootRegion().numBottomNodes(), 0u);
582  EXPECT_EQ(rvsdg.GetRootRegion().BottomNodes().begin(), rvsdg.GetRootRegion().BottomNodes().end());
583 
584  // And it becomes dead again
585  rvsdg.GetRootRegion().RemoveResults({ 0 });
586  EXPECT_TRUE(structuralNode->IsDead());
587  EXPECT_EQ(rvsdg.GetRootRegion().numBottomNodes(), 1u);
588  EXPECT_EQ(&*(rvsdg.GetRootRegion().BottomNodes().begin()), structuralNode);
589 }
590 
591 TEST(RegionTests, computeDepthMap)
592 {
593  // Arrange
594  using namespace jlm::rvsdg;
595 
596  auto valueType = TestType::createValueType();
597 
598  Graph rvsdg;
599 
600  auto & i0 = GraphImport::Create(rvsdg, valueType, "i0");
601  auto & i1 = GraphImport::Create(rvsdg, valueType, "i1");
602 
603  auto node0 = TestOperation::createNode(&rvsdg.GetRootRegion(), {}, { valueType });
604  auto node1 =
605  TestOperation::createNode(&rvsdg.GetRootRegion(), { node0->output(0), &i0 }, { valueType });
606  auto node2 = TestOperation::createNode(&rvsdg.GetRootRegion(), { &i1 }, { valueType });
607  auto node3 = TestOperation::createNode(
608  &rvsdg.GetRootRegion(),
609  { node1->output(0), node2->output(0) },
610  { valueType });
611 
612  GraphExport::Create(*node3->output(0), "x0");
613 
614  // Act
615  const auto depthMap = computeDepthMap(rvsdg.GetRootRegion());
616 
617  // Assert
618  EXPECT_EQ(depthMap.size(), 4u);
619  EXPECT_EQ(depthMap.at(node0), 0u);
620  EXPECT_EQ(depthMap.at(node1), 1u);
621  EXPECT_EQ(depthMap.at(node2), 0u);
622  EXPECT_EQ(depthMap.at(node3), 2u);
623 }
624 
625 TEST(RegionTests, Ancestor)
626 {
627  using namespace jlm::rvsdg;
628 
629  // Arrange
630  jlm::rvsdg::Graph graph;
631 
632  auto structuralNode1 = TestStructuralNode::create(&graph.GetRootRegion(), 1);
633  auto structuralNode2 = TestStructuralNode::create(&graph.GetRootRegion(), 1);
634  auto structuralNode3 = TestStructuralNode::create(structuralNode1->subregion(0), 1);
635  auto structuralNode4 = TestStructuralNode::create(structuralNode3->subregion(0), 1);
636 
637  // Act & Assert
638  // The root region is an ancestor of all the regions
639  EXPECT_TRUE(Region::isAncestor(*structuralNode1->subregion(0), graph.GetRootRegion()));
640  EXPECT_TRUE(Region::isAncestor(*structuralNode2->subregion(0), graph.GetRootRegion()));
641  EXPECT_TRUE(Region::isAncestor(*structuralNode3->subregion(0), graph.GetRootRegion()));
642  EXPECT_TRUE(Region::isAncestor(*structuralNode4->subregion(0), graph.GetRootRegion()));
643 
644  // A region is not it's own ancestor
645  EXPECT_FALSE(Region::isAncestor(*structuralNode1->subregion(0), *structuralNode1->subregion(0)));
646 
647  // Two unrelated regions are not ancestors
648  EXPECT_FALSE(Region::isAncestor(*structuralNode1->subregion(0), *structuralNode2->subregion(0)));
649 
650  // Ancestry works at multiple levels of nesting
651  EXPECT_TRUE(Region::isAncestor(*structuralNode3->subregion(0), *structuralNode1->subregion(0)));
652  EXPECT_TRUE(Region::isAncestor(*structuralNode4->subregion(0), *structuralNode1->subregion(0)));
653 }
Contains
static bool Contains(const jlm::llvm::InterProceduralGraphModule &module, const std::string &)
Definition: FNegTests.cpp:19
TEST
TEST(RegionTests, IteratorRanges)
Definition: RegionTests.cpp:16
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::GetRootRegion
Region & GetRootRegion() const noexcept
Definition: graph.hpp:99
jlm::rvsdg::RecordingObserver::destroyedInputIndices
const std::vector< size_t > & destroyedInputIndices() const noexcept
Definition: region.hpp:907
jlm::rvsdg::Region
Represent acyclic RVSDG subgraphs.
Definition: region.hpp:213
jlm::rvsdg::Region::RemoveResults
size_t RemoveResults(const util::HashSet< size_t > &indices)
Definition: region.cpp:278
jlm::rvsdg::Region::BottomNodes
BottomNodeRange BottomNodes() noexcept
Definition: region.hpp:347
jlm::rvsdg::Region::numNodes
size_t numNodes() const noexcept
Definition: region.hpp:481
jlm::rvsdg::Region::toJson
static std::string toJson(const Region &region, const util::AnnotationMap &annotationMap) noexcept
Definition: region.cpp:487
jlm::rvsdg::Region::ToTree
static std::string ToTree(const rvsdg::Region &region, const util::AnnotationMap &annotationMap) noexcept
Definition: region.cpp:627
jlm::rvsdg::Region::nresults
size_t nresults() const noexcept
Definition: region.hpp:465
jlm::rvsdg::Region::argument
RegionArgument * argument(size_t index) const noexcept
Definition: region.hpp:437
jlm::rvsdg::Region::IsRootRegion
bool IsRootRegion() const noexcept
Definition: region.cpp:170
jlm::rvsdg::Region::NumRegions
static size_t NumRegions(const rvsdg::Region &region) noexcept
Definition: region.cpp:453
jlm::rvsdg::Region::numBottomNodes
size_t numBottomNodes() const noexcept
Definition: region.hpp:499
jlm::rvsdg::Region::isAncestor
static bool isAncestor(const rvsdg::Region &region, const rvsdg::Region &ancestor) noexcept
Definition: region.cpp:471
jlm::rvsdg::TestBinaryOperation::create
static Node * create(const std::shared_ptr< const Type > &operandType, std::shared_ptr< const Type > resultType, Output *op1, Output *op2)
Definition: TestOperations.hpp:128
jlm::rvsdg::TestOperation::createNode
static SimpleNode * createNode(Region *region, const std::vector< Output * > &operands, std::vector< std::shared_ptr< const Type >> resultTypes)
Definition: TestOperations.hpp:191
jlm::rvsdg::TestStructuralNode::create
static TestStructuralNode * create(Region *parent, const size_t numSubregions)
Definition: TestNodes.hpp:152
jlm::rvsdg::TestType::createValueType
static std::shared_ptr< const TestType > createValueType()
Definition: TestType.cpp:67
jlm::rvsdg::TestUnaryOperation::create
static Node * create(Region *, std::shared_ptr< const Type > operandType, Output *operand, std::shared_ptr< const Type > resultType)
Definition: TestOperations.hpp:70
jlm::util::AnnotationMap::AddAnnotation
void AddAnnotation(const void *key, Annotation annotation)
Definition: AnnotationMap.hpp:212
jlm::rvsdg::computeDepthMap
std::unordered_map< const Node *, size_t > computeDepthMap(const Region &region)
Definition: region.cpp:765
Generated by doxygen 1.9.1