Jlm
Loading...
Searching...
No Matches
ControlFlowRestructuringTests.cpp
Go to the documentation of this file.
1/*
2 * Copyright 2015 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/frontend/ControlFlowRestructuring.hpp>
9#include <jlm/llvm/ir/basic-block.hpp>
10#include <jlm/llvm/ir/cfg-structure.hpp>
11#include <jlm/llvm/ir/ipgraph-module.hpp>
12#include <jlm/llvm/ir/operators/IntegerOperations.hpp>
13#include <jlm/llvm/ir/operators/operators.hpp>
14#include <jlm/rvsdg/control.hpp>
15
16TEST(ControlFlowRestructuringTests, AcyclicStructured)
17{
18 using namespace jlm::llvm;
19
20 InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
21
22 ControlFlowGraph cfg(module);
23 auto bb1 = BasicBlock::create(cfg);
24 auto bb2 = BasicBlock::create(cfg);
25 auto bb3 = BasicBlock::create(cfg);
26 auto bb4 = BasicBlock::create(cfg);
27
28 cfg.exit()->divert_inedges(bb1);
29 bb1->add_outedge(bb2);
30 bb1->add_outedge(bb3);
31 bb2->add_outedge(bb4);
32 bb3->add_outedge(bb4);
33 bb4->add_outedge(cfg.exit());
34
35 // jlm::view_ascii(cfg, stdout);
36
37 size_t nnodes = cfg.nnodes();
38 RestructureBranches(cfg);
39
40 // jlm::view_ascii(cfg, stdout);
41
42 EXPECT_EQ(nnodes, cfg.nnodes());
43}
44
45TEST(ControlFlowRestructuringTests, AcyclicUnstructured)
46{
47 using namespace jlm::llvm;
48
49 InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
50
51 ControlFlowGraph cfg(module);
52 auto bb1 = BasicBlock::create(cfg);
53 auto bb2 = BasicBlock::create(cfg);
54 auto bb3 = BasicBlock::create(cfg);
55 auto bb4 = BasicBlock::create(cfg);
56
57 cfg.exit()->divert_inedges(bb1);
58 bb1->add_outedge(bb2);
59 bb1->add_outedge(bb3);
60 bb2->add_outedge(bb3);
61 bb2->add_outedge(bb4);
62 bb3->add_outedge(bb4);
63 bb4->add_outedge(cfg.exit());
64
65 // jlm::view_ascii(cfg, stdout);
66
67 RestructureBranches(cfg);
68
69 // jlm::view_ascii(cfg, stdout);
70
71 EXPECT_TRUE(is_proper_structured(cfg));
72}
73
74TEST(ControlFlowRestructuringTests, NestedDoWhileLoop)
75{
76 using namespace jlm::llvm;
77
78 InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
79
80 ControlFlowGraph cfg(module);
81 auto bb1 = BasicBlock::create(cfg);
82 auto bb2 = BasicBlock::create(cfg);
83 auto bb3 = BasicBlock::create(cfg);
84
85 cfg.exit()->divert_inedges(bb1);
86 bb1->add_outedge(bb2);
87
88 bb2->add_outedge(bb3);
89 bb2->add_outedge(bb2);
90
91 bb3->add_outedge(cfg.exit());
92 bb3->add_outedge(bb1);
93
94 // jlm::view_ascii(cfg, stdout);
95
96 const size_t numNodesBeforeRestructuring = cfg.nnodes();
97 RestructureControlFlow(cfg);
98
99 // jlm::view_ascii(cfg, stdout);
100
101 EXPECT_EQ(cfg.nnodes(), numNodesBeforeRestructuring);
102 EXPECT_EQ(bb2->OutEdge(0)->sink(), bb3);
103 EXPECT_EQ(bb2->OutEdge(1)->sink(), bb2);
104 EXPECT_EQ(bb3->OutEdge(0)->sink(), cfg.exit());
105 EXPECT_EQ(bb3->OutEdge(1)->sink(), bb1);
106}
107
108TEST(ControlFlowRestructuringTests, DoWhileLoopWithWrongRepetitionEdge)
109{
110 using namespace jlm::llvm;
111 using namespace jlm::rvsdg;
112
113 // Arrange
114 InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
115
116 ControlFlowGraph cfg(module);
117 auto bb1 = BasicBlock::create(cfg);
118
119 cfg.exit()->divert_inedges(bb1);
120 bb1->add_outedge(bb1);
121 bb1->add_outedge(cfg.exit());
122
123 auto c1Operation = std::make_unique<IntegerConstantOperation>(BitValueRepresentation(1, 1));
124 bb1->append_last(ThreeAddressCode::create(std::move(c1Operation), {}));
125 auto matchOperation = std::unique_ptr<MatchOperation>(new MatchOperation(1, { { 1, 1 } }, 0, 2));
126 bb1->append_last(
127 ThreeAddressCode::create(std::move(matchOperation), { bb1->tacs().last()->result(0) }));
128 bb1->append_last(BranchOperation::create(2, bb1->tacs().last()->result(0)));
129
130 // Act
131 const size_t numNodesBeforeRestructuring = cfg.nnodes();
132 RestructureControlFlow(cfg);
133
134 // Assert
135 EXPECT_EQ(numNodesBeforeRestructuring, cfg.nnodes());
136 EXPECT_EQ(bb1->OutEdge(0)->sink(), cfg.exit());
137 EXPECT_EQ(bb1->OutEdge(1)->sink(), bb1);
138
139 auto matchTac = *std::next(bb1->tacs().rbegin(), 1);
140 auto newMatchOperation = jlm::util::assertedCast<const MatchOperation>(&matchTac->operation());
141 EXPECT_EQ(newMatchOperation->nalternatives(), 2u);
142 EXPECT_EQ(newMatchOperation->default_alternative(), 1u);
143 EXPECT_EQ(newMatchOperation->begin()->first, 1u);
144 EXPECT_EQ(newMatchOperation->begin()->second, 0u);
145}
146
147TEST(ControlFlowRestructuringTests, WhileLoop)
148{
149 using namespace jlm::llvm;
150
151 InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
152
153 ControlFlowGraph cfg(module);
154 auto bb1 = BasicBlock::create(cfg);
155 auto bb2 = BasicBlock::create(cfg);
156
157 cfg.exit()->divert_inedges(bb1);
158 bb1->add_outedge(cfg.exit());
159 bb1->add_outedge(bb2);
160 bb2->add_outedge(bb1);
161
162 // jlm::view_ascii(cfg, stdout);
163
164 RestructureControlFlow(cfg);
165
166 /* FIXME: Nodes are not printed in the right order */
167 // jlm::view_ascii(cfg, stdout);
168
169 EXPECT_TRUE(is_proper_structured(cfg));
170}
171
172TEST(ControlFlowRestructuringTests, IrreducibleCfg)
173{
174 using namespace jlm::llvm;
175
176 InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
177
178 ControlFlowGraph cfg(module);
179 auto bb1 = BasicBlock::create(cfg);
180 auto bb2 = BasicBlock::create(cfg);
181 auto bb3 = BasicBlock::create(cfg);
182 auto bb4 = BasicBlock::create(cfg);
183 auto bb5 = BasicBlock::create(cfg);
184
185 cfg.exit()->divert_inedges(bb1);
186 bb1->add_outedge(bb2);
187 bb1->add_outedge(bb3);
188 bb2->add_outedge(bb4);
189 bb2->add_outedge(bb3);
190 bb3->add_outedge(bb2);
191 bb3->add_outedge(bb5);
192 bb4->add_outedge(cfg.exit());
193 bb5->add_outedge(cfg.exit());
194
195 // jlm::view_ascii(cfg, stdout);
196
197 RestructureControlFlow(cfg);
198
199 // jlm::view_ascii(cfg, stdout);
200 EXPECT_TRUE(is_proper_structured(cfg));
201}
202
203TEST(ControlFlowRestructuringTests, AcyclicUnstructuredInDoWhileLoop)
204{
205 using namespace jlm::llvm;
206
207 InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
208
209 ControlFlowGraph cfg(module);
210 auto bb1 = BasicBlock::create(cfg);
211 auto bb2 = BasicBlock::create(cfg);
212 auto bb3 = BasicBlock::create(cfg);
213 auto bb4 = BasicBlock::create(cfg);
214
215 cfg.exit()->divert_inedges(bb1);
216 bb1->add_outedge(bb3);
217 bb1->add_outedge(bb2);
218 bb2->add_outedge(bb3);
219 bb2->add_outedge(bb4);
220 bb3->add_outedge(bb4);
221 bb4->add_outedge(cfg.exit());
222 bb4->add_outedge(bb1);
223
224 // jlm::view_ascii(cfg, stdout);
225
226 RestructureControlFlow(cfg);
227
228 // jlm::view_ascii(cfg, stdout);
229 EXPECT_TRUE(is_proper_structured(cfg));
230}
231
232TEST(ControlFlowRestructuringTests, LorBeforeDoWhileLoop)
233{
234 using namespace jlm::llvm;
235
236 InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
237
238 ControlFlowGraph cfg(module);
239 auto bb1 = BasicBlock::create(cfg);
240 auto bb2 = BasicBlock::create(cfg);
241 auto bb3 = BasicBlock::create(cfg);
242 auto bb4 = BasicBlock::create(cfg);
243
244 cfg.exit()->divert_inedges(bb1);
245 bb1->add_outedge(bb2);
246 bb1->add_outedge(bb3);
247 bb2->add_outedge(bb4);
248 bb2->add_outedge(bb3);
249 bb3->add_outedge(bb4);
250 bb4->add_outedge(cfg.exit());
251 bb4->add_outedge(bb4);
252
253 // jlm::view_ascii(cfg, stdout);
254
255 RestructureControlFlow(cfg);
256
257 // jlm::view_ascii(cfg, stdout);
258 EXPECT_TRUE(is_proper_structured(cfg));
259}
260
261TEST(ControlFlowRestructuringTests, StaticEndlessLoop)
262{
263 using namespace jlm::llvm;
264
265 InterProceduralGraphModule im(jlm::util::FilePath(""), "", "");
266
267 ControlFlowGraph cfg(im);
268 auto bb1 = BasicBlock::create(cfg);
269 auto bb2 = BasicBlock::create(cfg);
270
271 cfg.exit()->divert_inedges(bb1);
272 bb1->add_outedge(bb2);
273 bb1->add_outedge(bb1);
274 bb1->add_outedge(cfg.exit());
275 bb2->add_outedge(bb2);
276
277 // jlm::print_dot(cfg, stdout);
278
279 RestructureControlFlow(cfg);
280
281 // jlm::print_dot(cfg, stdout);
282 EXPECT_TRUE(is_proper_structured(cfg));
283}
TEST
TEST(ControlFlowRestructuringTests, AcyclicStructured)
Definition ControlFlowRestructuringTests.cpp:16
jlm::llvm::ControlFlowGraphNode::divert_inedges
void divert_inedges(llvm::ControlFlowGraphNode *new_successor)
Definition cfg-node.hpp:171
jlm::llvm::ControlFlowGraph::exit
ExitNode * exit() const noexcept
Definition cfg.hpp:212
jlm::llvm::ControlFlowGraph::nnodes
size_t nnodes() const noexcept
Definition cfg.hpp:241
jlm::llvm
Global memory state passed between functions.
Definition IpGraphToLlvmConverter.cpp:40
Generated by doxygen 1.9.8