Skip to content

Commit eb370ad

Browse files
kuharkuhar
committedJul 13, 2017
[Dominators] Add CFGBuilder testing utility
Summary: This patch introduces a new testing utility for building and modifying CFG -- CFGBuilder. The primary use case for the utility is testing the upcoming incremental dominator tree update API. The current design provides a simple mechanism of constructing arbitrary graphs and then applying series of updates to them. CFGBuilder takes care of creating empty functions, connecting and disconnecting basic blocks. Under the hood it uses SwitchInst and UnreachableInst. It will be also possible to create a thin wrapper over CFGBuilder for parsing string input and to hook it up to other textual tools (e.g. opt used with FileCheck). Reviewers: dberlin, sanjoy, grosser, dblaikie Reviewed By: dblaikie Subscribers: davide, mgorny, llvm-commits Differential Revision: https://reviews.llvm.org/D34798 llvm-svn: 307960
1 parent 971add5 commit eb370ad

File tree

3 files changed

+366
-0
lines changed

3 files changed

+366
-0
lines changed
 

‎llvm/unittests/IR/CFGBuilder.cpp

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

‎llvm/unittests/IR/CFGBuilder.h

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
//===- CFGBuilder.h - CFG building and updating utility ----------*- C++ -*-==//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
/// \file
10+
/// CFGBuilders provides utilities fo building and updating CFG for testing
11+
/// purposes.
12+
///
13+
//===----------------------------------------------------------------------===//
14+
15+
#ifndef LLVM_UNITTESTS_CFG_BUILDER_H
16+
#define LLVM_UNITTESTS_CFG_BUILDER_H
17+
18+
#include "llvm/ADT/DenseMap.h"
19+
#include "llvm/ADT/Optional.h"
20+
#include "llvm/ADT/StringMap.h"
21+
#include "llvm/ADT/StringRef.h"
22+
#include "llvm/Support/Debug.h"
23+
24+
#include <memory>
25+
#include <set>
26+
#include <vector>
27+
28+
namespace llvm {
29+
30+
class LLVMContext;
31+
class Module;
32+
class Function;
33+
class BasicBlock;
34+
class raw_ostream;
35+
36+
struct CFGHolder {
37+
std::unique_ptr<LLVMContext> Context;
38+
std::unique_ptr<Module> M;
39+
Function *F;
40+
41+
CFGHolder(StringRef ModuleName = "m", StringRef FunctionName = "foo");
42+
~CFGHolder(); // Defined in the .cpp file so we can use forward declarations.
43+
};
44+
45+
/// \brief
46+
/// CFGBuilder builds IR with specific CFG, based on the supplied list of arcs.
47+
/// It's able to apply the provided updates and automatically modify the IR.
48+
///
49+
/// Internally it makes every basic block end with either SwitchInst or with
50+
/// UnreachableInst. When all arc to a BB are deleted, the BB remains in the
51+
/// function and doesn't get deleted.
52+
///
53+
class CFGBuilder {
54+
public:
55+
struct Arc {
56+
StringRef From;
57+
StringRef To;
58+
59+
friend bool operator<(const Arc &LHS, const Arc &RHS);
60+
};
61+
62+
enum class ActionKind { Insert, Delete };
63+
struct Update {
64+
ActionKind Action;
65+
Arc Arc;
66+
};
67+
68+
CFGBuilder(Function *F, const std::vector<Arc> &InitialArcs,
69+
std::vector<Update> Updates);
70+
71+
BasicBlock *getOrAddBlock(StringRef BlockName);
72+
Optional<Update> getNextUpdate() const;
73+
Optional<Update> applyUpdate();
74+
void dump(raw_ostream &OS = dbgs()) const;
75+
76+
private:
77+
void buildCFG(const std::vector<Arc> &Arcs);
78+
bool connect(const Arc &A);
79+
bool disconnect(const Arc &A);
80+
81+
Function *F;
82+
unsigned UpdateIdx = 0;
83+
StringMap<BasicBlock *> NameToBlock;
84+
std::set<Arc> Arcs;
85+
std::vector<Update> Updates;
86+
};
87+
88+
} // namespace llvm
89+
90+
#endif

‎llvm/unittests/IR/CMakeLists.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@ set(IRSources
1010
AsmWriterTest.cpp
1111
AttributesTest.cpp
1212
BasicBlockTest.cpp
13+
CFGBuilder.cpp
1314
ConstantRangeTest.cpp
1415
ConstantsTest.cpp
1516
DebugInfoTest.cpp

0 commit comments

Comments
 (0)