1 //===- llvm/Testing/Support/CFGBuilder.cpp --------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "CFGBuilder.h"
10
11 #include "llvm/IR/CFG.h"
12 #include "llvm/IR/IRBuilder.h"
13 #include "llvm/IR/LLVMContext.h"
14 #include "llvm/IR/Module.h"
15 #include "llvm/Support/Debug.h"
16 #include "llvm/Support/raw_ostream.h"
17 #include "gtest/gtest.h"
18
19 #define DEBUG_TYPE "cfg-builder"
20
21 using namespace llvm;
22
CFGHolder(StringRef ModuleName,StringRef FunctionName)23 CFGHolder::CFGHolder(StringRef ModuleName, StringRef FunctionName)
24 : Context(std::make_unique<LLVMContext>()),
25 M(std::make_unique<Module>(ModuleName, *Context)) {
26 FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Context), {}, false);
27 F = Function::Create(FTy, Function::ExternalLinkage, FunctionName, M.get());
28 }
29 CFGHolder::~CFGHolder() = default;
30
CFGBuilder(Function * F,const std::vector<Arc> & InitialArcs,std::vector<Update> Updates)31 CFGBuilder::CFGBuilder(Function *F, const std::vector<Arc> &InitialArcs,
32 std::vector<Update> Updates)
33 : F(F), Updates(std::move(Updates)) {
34 assert(F);
35 buildCFG(InitialArcs);
36 }
37
ConnectBlocks(BasicBlock * From,BasicBlock * To)38 static void ConnectBlocks(BasicBlock *From, BasicBlock *To) {
39 LLVM_DEBUG(dbgs() << "Creating BB arc " << From->getName() << " -> "
40 << To->getName() << "\n";
41 dbgs().flush());
42 auto *IntTy = IntegerType::get(From->getContext(), 32);
43
44 if (isa<UnreachableInst>(From->getTerminator()))
45 From->getTerminator()->eraseFromParent();
46 if (!From->getTerminator()) {
47 IRBuilder<> IRB(From);
48 IRB.CreateSwitch(ConstantInt::get(IntTy, 0), To);
49 return;
50 }
51
52 SwitchInst *SI = cast<SwitchInst>(From->getTerminator());
53 const auto Last = SI->getNumCases();
54
55 auto *IntVal = ConstantInt::get(IntTy, Last);
56 SI->addCase(IntVal, To);
57 }
58
DisconnectBlocks(BasicBlock * From,BasicBlock * To)59 static void DisconnectBlocks(BasicBlock *From, BasicBlock *To) {
60 LLVM_DEBUG(dbgs() << "Deleting BB arc " << From->getName() << " -> "
61 << To->getName() << "\n";
62 dbgs().flush());
63 SwitchInst *SI = cast<SwitchInst>(From->getTerminator());
64
65 if (SI->getNumCases() == 0) {
66 SI->eraseFromParent();
67 IRBuilder<> IRB(From);
68 IRB.CreateUnreachable();
69 return;
70 }
71
72 if (SI->getDefaultDest() == To) {
73 auto FirstC = SI->case_begin();
74 SI->setDefaultDest(FirstC->getCaseSuccessor());
75 SI->removeCase(FirstC);
76 return;
77 }
78
79 for (auto CIt = SI->case_begin(); CIt != SI->case_end(); ++CIt)
80 if (CIt->getCaseSuccessor() == To) {
81 SI->removeCase(CIt);
82 return;
83 }
84 }
85
getOrAddBlock(StringRef BlockName)86 BasicBlock *CFGBuilder::getOrAddBlock(StringRef BlockName) {
87 auto BIt = NameToBlock.find(BlockName);
88 if (BIt != NameToBlock.end())
89 return BIt->second;
90
91 auto *BB = BasicBlock::Create(F->getParent()->getContext(), BlockName, F);
92 IRBuilder<> IRB(BB);
93 IRB.CreateUnreachable();
94 NameToBlock[BlockName] = BB;
95 return BB;
96 }
97
connect(const Arc & A)98 bool CFGBuilder::connect(const Arc &A) {
99 BasicBlock *From = getOrAddBlock(A.From);
100 BasicBlock *To = getOrAddBlock(A.To);
101 if (Arcs.count(A) != 0)
102 return false;
103
104 Arcs.insert(A);
105 ConnectBlocks(From, To);
106 return true;
107 }
108
disconnect(const Arc & A)109 bool CFGBuilder::disconnect(const Arc &A) {
110 assert(NameToBlock.count(A.From) != 0 && "No block to disconnect (From)");
111 assert(NameToBlock.count(A.To) != 0 && "No block to disconnect (To)");
112 if (Arcs.count(A) == 0)
113 return false;
114
115 BasicBlock *From = getOrAddBlock(A.From);
116 BasicBlock *To = getOrAddBlock(A.To);
117 Arcs.erase(A);
118 DisconnectBlocks(From, To);
119 return true;
120 }
121
buildCFG(const std::vector<Arc> & NewArcs)122 void CFGBuilder::buildCFG(const std::vector<Arc> &NewArcs) {
123 for (const auto &A : NewArcs) {
124 const bool Connected = connect(A);
125 (void)Connected;
126 assert(Connected);
127 }
128 }
129
getNextUpdate() const130 std::optional<CFGBuilder::Update> CFGBuilder::getNextUpdate() const {
131 if (UpdateIdx == Updates.size())
132 return std::nullopt;
133 return Updates[UpdateIdx];
134 }
135
applyUpdate()136 std::optional<CFGBuilder::Update> CFGBuilder::applyUpdate() {
137 if (UpdateIdx == Updates.size())
138 return std::nullopt;
139 Update NextUpdate = Updates[UpdateIdx++];
140 if (NextUpdate.Action == ActionKind::Insert)
141 connect(NextUpdate.Edge);
142 else
143 disconnect(NextUpdate.Edge);
144
145 return NextUpdate;
146 }
147
dump(raw_ostream & OS) const148 void CFGBuilder::dump(raw_ostream &OS) const {
149 OS << "Arcs:\n";
150 size_t i = 0;
151 for (const auto &A : Arcs)
152 OS << " " << i++ << ":\t" << A.From << " -> " << A.To << "\n";
153
154 OS << "Updates:\n";
155 i = 0;
156 for (const auto &U : Updates) {
157 OS << (i + 1 == UpdateIdx ? "->" : " ") << i
158 << ((U.Action == ActionKind::Insert) ? "\tIns " : "\tDel ")
159 << U.Edge.From << " -> " << U.Edge.To << "\n";
160 ++i;
161 }
162 }
163
164 //---- CFGBuilder tests ---------------------------------------------------===//
165
TEST(CFGBuilder,Construction)166 TEST(CFGBuilder, Construction) {
167 CFGHolder Holder;
168 std::vector<CFGBuilder::Arc> Arcs = {{"entry", "a"}, {"a", "b"}, {"a", "c"},
169 {"c", "d"}, {"d", "b"}, {"d", "e"},
170 {"d", "f"}, {"e", "f"}};
171 CFGBuilder B(Holder.F, Arcs, {});
172
173 EXPECT_TRUE(B.getOrAddBlock("entry") == &Holder.F->getEntryBlock());
174 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
175 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
176 EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("b")->getTerminator()));
177 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
178
179 auto *DSwitch = cast<SwitchInst>(B.getOrAddBlock("d")->getTerminator());
180 // d has 3 successors, but one of them if going to be a default case
181 EXPECT_EQ(DSwitch->getNumCases(), 2U);
182 EXPECT_FALSE(B.getNextUpdate()); // No updates to apply.
183 }
184
TEST(CFGBuilder,Insertions)185 TEST(CFGBuilder, Insertions) {
186 CFGHolder Holder;
187 const auto Insert = CFGBuilder::ActionKind::Insert;
188 std::vector<CFGBuilder::Update> Updates = {
189 {Insert, {"entry", "a"}}, {Insert, {"a", "b"}}, {Insert, {"a", "c"}},
190 {Insert, {"c", "d"}}, {Insert, {"d", "b"}}, {Insert, {"d", "e"}},
191 {Insert, {"d", "f"}}, {Insert, {"e", "f"}}};
192 const size_t NumUpdates = Updates.size();
193
194 CFGBuilder B(Holder.F, {}, Updates);
195
196 size_t i = 0;
197 while (B.applyUpdate())
198 ++i;
199 EXPECT_EQ(i, NumUpdates);
200
201 EXPECT_TRUE(B.getOrAddBlock("entry") == &Holder.F->getEntryBlock());
202 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
203 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
204 EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("b")->getTerminator()));
205 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
206
207 auto *DSwitch = cast<SwitchInst>(B.getOrAddBlock("d")->getTerminator());
208 // d has 3 successors, but one of them if going to be a default case
209 EXPECT_EQ(DSwitch->getNumCases(), 2U);
210 EXPECT_FALSE(B.getNextUpdate()); // No updates to apply.
211 }
212
TEST(CFGBuilder,Deletions)213 TEST(CFGBuilder, Deletions) {
214 CFGHolder Holder;
215 std::vector<CFGBuilder::Arc> Arcs = {
216 {"entry", "a"}, {"a", "b"}, {"a", "c"}, {"c", "d"}, {"d", "b"}};
217 const auto Delete = CFGBuilder::ActionKind::Delete;
218 std::vector<CFGBuilder::Update> Updates = {
219 {Delete, {"c", "d"}}, {Delete, {"a", "c"}}, {Delete, {"entry", "a"}},
220 };
221 const size_t NumUpdates = Updates.size();
222
223 CFGBuilder B(Holder.F, Arcs, Updates);
224
225 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
226 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
227 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("c")->getTerminator()));
228 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
229
230 auto UpdateC = B.applyUpdate();
231
232 EXPECT_TRUE(UpdateC);
233 EXPECT_EQ(UpdateC->Action, CFGBuilder::ActionKind::Delete);
234 EXPECT_EQ(UpdateC->Edge.From, "c");
235 EXPECT_EQ(UpdateC->Edge.To, "d");
236 EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("c")->getTerminator()));
237
238 size_t i = 1;
239 while (B.applyUpdate())
240 ++i;
241 EXPECT_EQ(i, NumUpdates);
242
243 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
244 EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("entry")->getTerminator()));
245 }
246
TEST(CFGBuilder,Rebuild)247 TEST(CFGBuilder, Rebuild) {
248 CFGHolder Holder;
249 std::vector<CFGBuilder::Arc> Arcs = {
250 {"entry", "a"}, {"a", "b"}, {"a", "c"}, {"c", "d"}, {"d", "b"}};
251 const auto Insert = CFGBuilder::ActionKind::Insert;
252 const auto Delete = CFGBuilder::ActionKind::Delete;
253 std::vector<CFGBuilder::Update> Updates = {
254 {Delete, {"c", "d"}}, {Delete, {"a", "c"}}, {Delete, {"entry", "a"}},
255 {Insert, {"c", "d"}}, {Insert, {"a", "c"}}, {Insert, {"entry", "a"}},
256 };
257 const size_t NumUpdates = Updates.size();
258
259 CFGBuilder B(Holder.F, Arcs, Updates);
260 size_t i = 0;
261 while (B.applyUpdate())
262 ++i;
263 EXPECT_EQ(i, NumUpdates);
264
265 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
266 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
267 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("c")->getTerminator()));
268 EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
269 }
270
271 static_assert(std::is_trivially_copyable_v<succ_iterator>,
272 "trivially copyable");
273 static_assert(std::is_trivially_copyable_v<const_succ_iterator>,
274 "trivially copyable");
275 static_assert(std::is_trivially_copyable_v<succ_range>, "trivially copyable");
276 static_assert(std::is_trivially_copyable_v<const_succ_range>,
277 "trivially copyable");
278