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/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>(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
  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
  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
  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
  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
  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
 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
 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 Optional<CFGBuilder::Update> CFGBuilder::getNextUpdate() const {
 130   if (UpdateIdx == Updates.size())
 131     return None;
 132   return Updates[UpdateIdx];
 133 }
 134
 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
 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 = {{"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
 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
 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
 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<succ_const_iterator>::value,
 273               "trivially copyable");
 274 static_assert(is_trivially_copyable<succ_range>::value, "trivially copyable");
 275 static_assert(is_trivially_copyable<succ_const_range>::value,
 276               "trivially copyable");