llvm/unittests/IR/CFGBuilder.cpp

   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");