278 lines · 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-exception6//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 21using namespace llvm;22 23CFGHolder::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}29CFGHolder::~CFGHolder() = default;30 31CFGBuilder::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 38static 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 59static 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 86BasicBlock *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 98bool 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 109bool 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 122void 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 130std::optional<CFGBuilder::Update> CFGBuilder::getNextUpdate() const {131 if (UpdateIdx == Updates.size())132 return std::nullopt;133 return Updates[UpdateIdx];134}135 136std::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 else143 disconnect(NextUpdate.Edge);144 145 return NextUpdate;146}147 148void 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 ? "->" : " ") << i158 << ((U.Action == ActionKind::Insert) ? "\tIns " : "\tDel ")159 << U.Edge.From << " -> " << U.Edge.To << "\n";160 ++i;161 }162}163 164//---- CFGBuilder tests ---------------------------------------------------===//165 166TEST(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 case181 EXPECT_EQ(DSwitch->getNumCases(), 2U);182 EXPECT_FALSE(B.getNextUpdate()); // No updates to apply.183}184 185TEST(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 case209 EXPECT_EQ(DSwitch->getNumCases(), 2U);210 EXPECT_FALSE(B.getNextUpdate()); // No updates to apply.211}212 213TEST(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 247TEST(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 271static_assert(std::is_trivially_copyable_v<succ_iterator>,272 "trivially copyable");273static_assert(std::is_trivially_copyable_v<const_succ_iterator>,274 "trivially copyable");275static_assert(std::is_trivially_copyable_v<succ_range>, "trivially copyable");276static_assert(std::is_trivially_copyable_v<const_succ_range>,277 "trivially copyable");278