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

source code of llvm/unittests/IR/CFGBuilder.cpp