Jlm
Loading...
Searching...
No Matches
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
16TEST(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, 2u);
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, 1u);
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, 4u);
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, 1u);
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, 3u);
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
82TEST(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
114TEST(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
128TEST(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
139TEST(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
154TEST(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
232TEST(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
334TEST(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
368TEST(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
383TEST(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
404TEST(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, 10u);
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
429TEST(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, 8u);
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
463TEST(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
478TEST(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
499TEST(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
530TEST(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 ":[{},{},{\"NumArguments\":0,\"NumNodes\":0}]}]}]}]}");
559}
560
561TEST(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
591TEST(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
625TEST(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
654 // Swapping the order makes the function return false
655 EXPECT_FALSE(Region::isAncestor(*structuralNode1->subregion(0), *structuralNode3->subregion(0)));
656 EXPECT_FALSE(Region::isAncestor(*structuralNode1->subregion(0), *structuralNode4->subregion(0)));
657}
658
659TEST(RegionTests, DepthTest)
660{
661 using namespace jlm::rvsdg;
662
663 // Arrange
664 jlm::rvsdg::Graph graph;
665
666 auto structuralNode = TestStructuralNode::create(&graph.GetRootRegion(), 2);
667 auto innerStructuralNode = TestStructuralNode::create(structuralNode->subregion(0), 1);
668
669 // Act & Assert
670 EXPECT_EQ(graph.GetRootRegion().getDepth(), 0u);
671 EXPECT_EQ(structuralNode->region()->getDepth(), 0u);
672 EXPECT_EQ(structuralNode->subregion(0)->getDepth(), 1u);
673 EXPECT_EQ(structuralNode->subregion(1)->getDepth(), 1u);
674 EXPECT_EQ(innerStructuralNode->region()->getDepth(), 1u);
675 EXPECT_EQ(innerStructuralNode->subregion(0)->getDepth(), 2u);
676}
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::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:964
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:281
jlm::rvsdg::Region::argument
RegionArgument * argument(size_t index) const noexcept
Definition region.hpp:466
jlm::rvsdg::Region::BottomNodes
BottomNodeRange BottomNodes() noexcept
Definition region.hpp:394
jlm::rvsdg::Region::numNodes
size_t numNodes() const noexcept
Definition region.hpp:510
jlm::rvsdg::Region::nresults
size_t nresults() const noexcept
Definition region.hpp:494
jlm::rvsdg::Region::IsRootRegion
bool IsRootRegion() const noexcept
Definition region.cpp:173
jlm::rvsdg::Region::numBottomNodes
size_t numBottomNodes() const noexcept
Definition region.hpp:528
jlm::rvsdg::Region::getDepth
size_t getDepth() const noexcept
Definition region.hpp:291
jlm::rvsdg::TestType::createValueType
static std::shared_ptr< const TestType > createValueType()
Definition TestType.cpp:67
jlm::util::AnnotationMap::AddAnnotation
void AddAnnotation(const void *key, Annotation annotation)
Definition AnnotationMap.hpp:212
Generated by doxygen 1.9.8