Jlm
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 
13 TEST(ControlFlowRestructuringTests, AcyclicStructured)
14 {
15  using namespace jlm::llvm;
16 
17  InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
18 
19  ControlFlowGraph cfg(module);
20  auto bb1 = BasicBlock::create(cfg);
21  auto bb2 = BasicBlock::create(cfg);
22  auto bb3 = BasicBlock::create(cfg);
23  auto bb4 = BasicBlock::create(cfg);
24 
25  cfg.exit()->divert_inedges(bb1);
26  bb1->add_outedge(bb2);
27  bb1->add_outedge(bb3);
28  bb2->add_outedge(bb4);
29  bb3->add_outedge(bb4);
30  bb4->add_outedge(cfg.exit());
31 
32  // jlm::view_ascii(cfg, stdout);
33 
34  size_t nnodes = cfg.nnodes();
35  RestructureBranches(cfg);
36 
37  // jlm::view_ascii(cfg, stdout);
38 
39  EXPECT_EQ(nnodes, cfg.nnodes());
40 }
41 
42 TEST(ControlFlowRestructuringTests, AcyclicUnstructured)
43 {
44  using namespace jlm::llvm;
45 
46  InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
47 
48  ControlFlowGraph cfg(module);
49  auto bb1 = BasicBlock::create(cfg);
50  auto bb2 = BasicBlock::create(cfg);
51  auto bb3 = BasicBlock::create(cfg);
52  auto bb4 = BasicBlock::create(cfg);
53 
54  cfg.exit()->divert_inedges(bb1);
55  bb1->add_outedge(bb2);
56  bb1->add_outedge(bb3);
57  bb2->add_outedge(bb3);
58  bb2->add_outedge(bb4);
59  bb3->add_outedge(bb4);
60  bb4->add_outedge(cfg.exit());
61 
62  // jlm::view_ascii(cfg, stdout);
63 
64  RestructureBranches(cfg);
65 
66  // jlm::view_ascii(cfg, stdout);
67 
68  EXPECT_TRUE(is_proper_structured(cfg));
69 }
70 
71 TEST(ControlFlowRestructuringTests, DoWhileLoop)
72 {
73  using namespace jlm::llvm;
74 
75  InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
76 
77  ControlFlowGraph cfg(module);
78  auto bb1 = BasicBlock::create(cfg);
79  auto bb2 = BasicBlock::create(cfg);
80  auto bb3 = BasicBlock::create(cfg);
81 
82  cfg.exit()->divert_inedges(bb1);
83  bb1->add_outedge(bb2);
84  bb2->add_outedge(bb2);
85  bb2->add_outedge(bb3);
86  bb3->add_outedge(bb1);
87  bb3->add_outedge(cfg.exit());
88 
89  // jlm::view_ascii(cfg, stdout);
90 
91  size_t nnodes = cfg.nnodes();
92  RestructureControlFlow(cfg);
93 
94  // jlm::view_ascii(cfg, stdout);
95 
96  EXPECT_EQ(nnodes, cfg.nnodes());
97  EXPECT_EQ(bb2->OutEdge(0)->sink(), bb2);
98  EXPECT_EQ(bb3->OutEdge(0)->sink(), bb1);
99 }
100 
101 TEST(ControlFlowRestructuringTests, WhileLoop)
102 {
103  using namespace jlm::llvm;
104 
105  InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
106 
107  ControlFlowGraph cfg(module);
108  auto bb1 = BasicBlock::create(cfg);
109  auto bb2 = BasicBlock::create(cfg);
110 
111  cfg.exit()->divert_inedges(bb1);
112  bb1->add_outedge(cfg.exit());
113  bb1->add_outedge(bb2);
114  bb2->add_outedge(bb1);
115 
116  // jlm::view_ascii(cfg, stdout);
117 
118  RestructureControlFlow(cfg);
119 
120  /* FIXME: Nodes are not printed in the right order */
121  // jlm::view_ascii(cfg, stdout);
122 
123  EXPECT_TRUE(is_proper_structured(cfg));
124 }
125 
126 TEST(ControlFlowRestructuringTests, IrreducibleCfg)
127 {
128  using namespace jlm::llvm;
129 
130  InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
131 
132  ControlFlowGraph cfg(module);
133  auto bb1 = BasicBlock::create(cfg);
134  auto bb2 = BasicBlock::create(cfg);
135  auto bb3 = BasicBlock::create(cfg);
136  auto bb4 = BasicBlock::create(cfg);
137  auto bb5 = BasicBlock::create(cfg);
138 
139  cfg.exit()->divert_inedges(bb1);
140  bb1->add_outedge(bb2);
141  bb1->add_outedge(bb3);
142  bb2->add_outedge(bb4);
143  bb2->add_outedge(bb3);
144  bb3->add_outedge(bb2);
145  bb3->add_outedge(bb5);
146  bb4->add_outedge(cfg.exit());
147  bb5->add_outedge(cfg.exit());
148 
149  // jlm::view_ascii(cfg, stdout);
150 
151  RestructureControlFlow(cfg);
152 
153  // jlm::view_ascii(cfg, stdout);
154  EXPECT_TRUE(is_proper_structured(cfg));
155 }
156 
157 TEST(ControlFlowRestructuringTests, AcyclicUnstructuredInDoWhileLoop)
158 {
159  using namespace jlm::llvm;
160 
161  InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
162 
163  ControlFlowGraph cfg(module);
164  auto bb1 = BasicBlock::create(cfg);
165  auto bb2 = BasicBlock::create(cfg);
166  auto bb3 = BasicBlock::create(cfg);
167  auto bb4 = BasicBlock::create(cfg);
168 
169  cfg.exit()->divert_inedges(bb1);
170  bb1->add_outedge(bb3);
171  bb1->add_outedge(bb2);
172  bb2->add_outedge(bb3);
173  bb2->add_outedge(bb4);
174  bb3->add_outedge(bb4);
175  bb4->add_outedge(bb1);
176  bb4->add_outedge(cfg.exit());
177 
178  // jlm::view_ascii(cfg, stdout);
179 
180  RestructureControlFlow(cfg);
181 
182  // jlm::view_ascii(cfg, stdout);
183  EXPECT_TRUE(is_proper_structured(cfg));
184 }
185 
186 TEST(ControlFlowRestructuringTests, LorBeforeDoWhileLoop)
187 {
188  using namespace jlm::llvm;
189 
190  InterProceduralGraphModule module(jlm::util::FilePath(""), "", "");
191 
192  ControlFlowGraph cfg(module);
193  auto bb1 = BasicBlock::create(cfg);
194  auto bb2 = BasicBlock::create(cfg);
195  auto bb3 = BasicBlock::create(cfg);
196  auto bb4 = BasicBlock::create(cfg);
197 
198  cfg.exit()->divert_inedges(bb1);
199  bb1->add_outedge(bb2);
200  bb1->add_outedge(bb3);
201  bb2->add_outedge(bb4);
202  bb2->add_outedge(bb3);
203  bb3->add_outedge(bb4);
204  bb4->add_outedge(cfg.exit());
205  bb4->add_outedge(bb4);
206 
207  // jlm::view_ascii(cfg, stdout);
208 
209  RestructureControlFlow(cfg);
210 
211  // jlm::view_ascii(cfg, stdout);
212  EXPECT_TRUE(is_proper_structured(cfg));
213 }
214 
215 TEST(ControlFlowRestructuringTests, StaticEndlessLoop)
216 {
217  using namespace jlm::llvm;
218 
219  InterProceduralGraphModule im(jlm::util::FilePath(""), "", "");
220 
221  ControlFlowGraph cfg(im);
222  auto bb1 = BasicBlock::create(cfg);
223  auto bb2 = BasicBlock::create(cfg);
224 
225  cfg.exit()->divert_inedges(bb1);
226  bb1->add_outedge(bb2);
227  bb1->add_outedge(bb1);
228  bb1->add_outedge(cfg.exit());
229  bb2->add_outedge(bb2);
230 
231  // jlm::print_dot(cfg, stdout);
232 
233  RestructureControlFlow(cfg);
234 
235  // jlm::print_dot(cfg, stdout);
236  EXPECT_TRUE(is_proper_structured(cfg));
237 }
TEST
TEST(ControlFlowRestructuringTests, AcyclicStructured)
Definition: ControlFlowRestructuringTests.cpp:13
jlm::llvm::BasicBlock::create
static BasicBlock * create(ControlFlowGraph &cfg)
Definition: basic-block.cpp:37
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:36
jlm::llvm::RestructureBranches
static void RestructureBranches(ControlFlowGraphNode &entry, ControlFlowGraphNode &exit)
Definition: ControlFlowRestructuring.cpp:403
jlm::llvm::RestructureControlFlow
static void RestructureControlFlow(ControlFlowGraphNode &, ControlFlowGraphNode &, std::vector< TailControlledLoop > &)
Definition: ControlFlowRestructuring.cpp:507
jlm::llvm::is_proper_structured
bool is_proper_structured(const ControlFlowGraph &cfg)
Definition: cfg-structure.cpp:623
jlm::rvsdg::nnodes
size_t nnodes(const jlm::rvsdg::Region *region) noexcept
Definition: region.cpp:785
Generated by doxygen 1.9.1