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 | |
20 | using namespace llvm; |
21 | |
22 | CFGHolder::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 | } |
28 | CFGHolder::~CFGHolder() = default; |
29 | |
30 | CFGBuilder::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 | |
37 | static 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 | |
58 | static 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 | |
85 | BasicBlock *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 | |
97 | bool 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 | |
108 | bool 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 | |
121 | void 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 | |
129 | std::optional<CFGBuilder::Update> CFGBuilder::getNextUpdate() const { |
130 | if (UpdateIdx == Updates.size()) |
131 | return std::nullopt; |
132 | return Updates[UpdateIdx]; |
133 | } |
134 | |
135 | std::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 | |
147 | void 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 | |
165 | TEST(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 | |
184 | TEST(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 | |
212 | TEST(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 | |
246 | TEST(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 | |
270 | static_assert(std::is_trivially_copyable_v<succ_iterator>, |
271 | "trivially copyable" ); |
272 | static_assert(std::is_trivially_copyable_v<const_succ_iterator>, |
273 | "trivially copyable" ); |
274 | static_assert(std::is_trivially_copyable_v<succ_range>, "trivially copyable" ); |
275 | static_assert(std::is_trivially_copyable_v<const_succ_range>, |
276 | "trivially copyable" ); |
277 | |