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 
CFGHolder(StringRef ModuleName,StringRef FunctionName)22 CFGHolder::CFGHolder(StringRef ModuleName, StringRef FunctionName)
23     : Context(std::make_unique<LLVMContext>()),
24       M(std::make_unique<Module>(ModuleName, *Context)) {
25   FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Context), {}, false);
26   F = Function::Create(FTy, Function::ExternalLinkage, FunctionName, M.get());
27 }
28 CFGHolder::~CFGHolder() = default;
29 
CFGBuilder(Function * F,const std::vector<Arc> & InitialArcs,std::vector<Update> Updates)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(InitialArcs);
35 }
36 
ConnectBlocks(BasicBlock * From,BasicBlock * To)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(From->getContext(), 32);
42 
43   if (isa<UnreachableInst>(From->getTerminator()))
44     From->getTerminator()->eraseFromParent();
45   if (!From->getTerminator()) {
46     IRBuilder<> IRB(From);
47     IRB.CreateSwitch(ConstantInt::get(IntTy, 0), To);
48     return;
49   }
50 
51   SwitchInst *SI = cast<SwitchInst>(From->getTerminator());
52   const auto Last = SI->getNumCases();
53 
54   auto *IntVal = ConstantInt::get(IntTy, Last);
55   SI->addCase(IntVal, To);
56 }
57 
DisconnectBlocks(BasicBlock * From,BasicBlock * To)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>(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(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(CIt);
81       return;
82     }
83 }
84 
getOrAddBlock(StringRef BlockName)85 BasicBlock *CFGBuilder::getOrAddBlock(StringRef BlockName) {
86   auto BIt = NameToBlock.find(BlockName);
87   if (BIt != NameToBlock.end())
88     return BIt->second;
89 
90   auto *BB = BasicBlock::Create(F->getParent()->getContext(), BlockName, F);
91   IRBuilder<> IRB(BB);
92   IRB.CreateUnreachable();
93   NameToBlock[BlockName] = BB;
94   return BB;
95 }
96 
connect(const Arc & A)97 bool CFGBuilder::connect(const Arc &A) {
98   BasicBlock *From = getOrAddBlock(A.From);
99   BasicBlock *To = getOrAddBlock(A.To);
100   if (Arcs.count(A) != 0)
101     return false;
102 
103   Arcs.insert(A);
104   ConnectBlocks(From, To);
105   return true;
106 }
107 
disconnect(const Arc & A)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(A) == 0)
112     return false;
113 
114   BasicBlock *From = getOrAddBlock(A.From);
115   BasicBlock *To = getOrAddBlock(A.To);
116   Arcs.erase(A);
117   DisconnectBlocks(From, To);
118   return true;
119 }
120 
buildCFG(const std::vector<Arc> & NewArcs)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 
getNextUpdate() const129 Optional<CFGBuilder::Update> CFGBuilder::getNextUpdate() const {
130   if (UpdateIdx == Updates.size())
131     return None;
132   return Updates[UpdateIdx];
133 }
134 
applyUpdate()135 Optional<CFGBuilder::Update> CFGBuilder::applyUpdate() {
136   if (UpdateIdx == Updates.size())
137     return None;
138   Update NextUpdate = Updates[UpdateIdx++];
139   if (NextUpdate.Action == ActionKind::Insert)
140     connect(NextUpdate.Edge);
141   else
142     disconnect(NextUpdate.Edge);
143 
144   return NextUpdate;
145 }
146 
dump(raw_ostream & OS) const147 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 
TEST(CFGBuilder,Construction)165 TEST(CFGBuilder, Construction) {
166   CFGHolder Holder;
167   std::vector<CFGBuilder::Arc> Arcs = {{"entry", "a"}, {"a", "b"}, {"a", "c"},
168                                        {"c", "d"},     {"d", "b"}, {"d", "e"},
169                                        {"d", "f"},     {"e", "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>(B.getOrAddBlock("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 
TEST(CFGBuilder,Insertions)184 TEST(CFGBuilder, Insertions) {
185   CFGHolder Holder;
186   const auto Insert = CFGBuilder::ActionKind::Insert;
187   std::vector<CFGBuilder::Update> Updates = {
188       {Insert, {"entry", "a"}}, {Insert, {"a", "b"}}, {Insert, {"a", "c"}},
189       {Insert, {"c", "d"}},     {Insert, {"d", "b"}}, {Insert, {"d", "e"}},
190       {Insert, {"d", "f"}},     {Insert, {"e", "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>(B.getOrAddBlock("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 
TEST(CFGBuilder,Deletions)212 TEST(CFGBuilder, Deletions) {
213   CFGHolder Holder;
214   std::vector<CFGBuilder::Arc> Arcs = {
215       {"entry", "a"}, {"a", "b"}, {"a", "c"}, {"c", "d"}, {"d", "b"}};
216   const auto Delete = CFGBuilder::ActionKind::Delete;
217   std::vector<CFGBuilder::Update> Updates = {
218       {Delete, {"c", "d"}}, {Delete, {"a", "c"}}, {Delete, {"entry", "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 
TEST(CFGBuilder,Rebuild)246 TEST(CFGBuilder, Rebuild) {
247   CFGHolder Holder;
248   std::vector<CFGBuilder::Arc> Arcs = {
249       {"entry", "a"}, {"a", "b"}, {"a", "c"}, {"c", "d"}, {"d", "b"}};
250   const auto Insert = CFGBuilder::ActionKind::Insert;
251   const auto Delete = CFGBuilder::ActionKind::Delete;
252   std::vector<CFGBuilder::Update> Updates = {
253       {Delete, {"c", "d"}}, {Delete, {"a", "c"}}, {Delete, {"entry", "a"}},
254       {Insert, {"c", "d"}}, {Insert, {"a", "c"}}, {Insert, {"entry", "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(is_trivially_copyable<succ_iterator>::value,
271               "trivially copyable");
272 static_assert(is_trivially_copyable<const_succ_iterator>::value,
273               "trivially copyable");
274 static_assert(is_trivially_copyable<succ_range>::value, "trivially copyable");
275 static_assert(is_trivially_copyable<const_succ_range>::value,
276               "trivially copyable");
277