llvm-project

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

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

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

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

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

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

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

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

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

130
std::optional<CFGBuilder::Update> CFGBuilder::getNextUpdate() const {
131
  if (UpdateIdx == Updates.size())
132
    return std::nullopt;
133
  return Updates[UpdateIdx];
134
}
135

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

148
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

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

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

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

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