[Dominators] Add CFGBuilder testing utility

[kuhar]

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).

[dblaikie]

Ah, hmm - I was assuming this was an API for building the CFG data structures. But I see it's an API for building IR that represents particular CFGs (so you can then test the CFG analysis that builds the data structures, etc, I assume?).

How much more terse is this than the hand-written IR? (I assume that's the motivation/benefit?) How much does that help - perhaps you could show (not in anything that needs to be committed) an example of the textual IR for some of the tests, to demonstrate how much more terse it is? But I guess it's obvious enough perhaps from the tabular update array format that it is quite compact.

unittests/IR/CFGBuilder.cpp

30 ↗

(On Diff #104572)

"= default", and maybe a comment about why this is out of line (I'm assuming it's out of line/not implicit so that the header doesn't need to include the Module header, etc and can use forward declarations instead)

44 ↗

(On Diff #104572)

I think you can rephrase

From->getParent()->getParent()->getContext()

to

From->getContext()

(also BB->getParent()->getParent() is equivalent to BB->getModule() I think?)

unittests/IR/CFGBuilder.h

59–61 ↗

(On Diff #104572)

Generally operator overloads that can be non-members should be (ensures equal conversion handling for the operands/arguments)

60 ↗

(On Diff #104572)

probably use std::tie rather than std::make_pair, so that copies aren't needed.

66 ↗

(On Diff #104572)

It feels like the type name may be better to have a more meaningful name - rather than or in addition to the variable name (Operation? "Operation Op" ?)

67 ↗

(On Diff #104572)

Variable and type names being the same can be tricky - but I realize sometimes it's the tidiest option. *shrug* :)

70–71 ↗

(On Diff #104572)

Not sure if the aliases aid in readability (especially using the word 'list' in the names when they are vectors may given a mistaken impression about the performance of certain operations) - consider using the type names directly.

[kuhar]

Address David's comments.

[dblaikie]

unittests/IR/CFGBuilder.cpp

33–35 ↗

(On Diff #104771)

Oh, you could still have this inline in the header - just important that it's not a member function. It doesn't need to be a friend though, since this is a struct with only public members.

But if you do declare it as a friend (though it's not necessary/might be slightly confusing to a reader "why is this a friend if there's nothing private to access?") you can define it inline at the friend declaration - which keeps it written right where it was when it was a member function, close to the type it's defined for, etc, which is nice.

[kuhar]

Thanks for the review, David!

Ah, hmm - I was assuming this was an API for building the CFG data structures. But I see it's an API for building IR that represents particular CFGs (so you can then test the CFG analysis that builds the data structures, etc, I assume?).

I tried to clarify that in the class description -- does it help? Perhaps we should think of a better name, any ideas?

How much more terse is this than the hand-written IR? (I assume that's the motivation/benefit?) How much does that help - perhaps you could show (not in anything that needs to be committed) an example of the textual IR for some of the tests, to demonstrate how much more terse it is? But I guess it's obvious enough perhaps from the tabular update array format that it is quite compact.

Well, the thing is that writing the initial IR by hand is not that bad, but then you have to manually iterate over every basic block and assign it to a pointer (or a map of sort). The worst part is actually updating the IR within you test -- then you have to remember to update each terminator, handle edge cases when your successor is default switch case, change terminator to unreachable or return when you remove all the outgoing arcs, etc.

As an example, you can look at the ToT DominatorTreeTest.cpp. The IR modified there is really small, yet the update code still manages to pretty lengthy and thus not particularly readable. If you are really interested, I can generate some real-world examples that directly compare the two described approaches.

Thanks,
~Kuba

[kuhar]

unittests/IR/CFGBuilder.cpp

33–35 ↗

(On Diff #104771)

The thing is that I keep Arcs in a std::set, which uses the less-than operator and I think that it needs to be declared before using it.
And if I go with declaring it inline, then I'll also have to pull in the entire <tuple>. I'm not sure if something includes it transitively -- if that's the case, I'm more than happy to keep it inline.

[kuhar]

Here's a real-world example of possible use of the CFGBuilder:
https://reviews.llvm.org/D35341
https://reviews.llvm.org/D35342

CFGBuilder makes it easy not only write pretty concise test cases for the new incremental DomTree API, but also to generate different permutations of update sequences using standard algorithms -- which is not really possible if we decided to do the updates manually (without a library to automatically generate IR based on CFG description).

llvm/trunk/unittests/IR/CFGBuilder.h

+//===- CFGBuilder.h - CFG building and updating utility ----------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// CFGBuilders provides utilities fo building and updating CFG for testing
+/// purposes.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UNITTESTS_CFG_BUILDER_H
+#define LLVM_UNITTESTS_CFG_BUILDER_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Debug.h"
+
+#include <memory>
+#include <set>
+#include <vector>
+
+namespace llvm {
+
+class LLVMContext;
+class Module;
+class Function;
+class BasicBlock;
+class raw_ostream;
+
+struct CFGHolder {
+  std::unique_ptr<LLVMContext> Context;
+  std::unique_ptr<Module> M;
+  Function *F;
+
+  CFGHolder(StringRef ModuleName = "m", StringRef FunctionName = "foo");
+  ~CFGHolder(); // Defined in the .cpp file so we can use forward declarations.
+};
+
+/// \brief
+/// CFGBuilder builds IR with specific CFG, based on the supplied list of arcs.
+/// It's able to apply the provided updates and automatically modify the IR.
+///
+/// Internally it makes every basic block end with either SwitchInst or with
+/// UnreachableInst. When all arc to a BB are deleted, the BB remains in the
+/// function and doesn't get deleted.
+///
+class CFGBuilder {
+public:
+  struct Arc {
+    StringRef From;
+    StringRef To;
+
+    friend bool operator<(const Arc &LHS, const Arc &RHS);
+  };
+
+  enum class ActionKind { Insert, Delete };
+  struct Update {
+    ActionKind Action;
+    Arc Arc;
+  };
+
+  CFGBuilder(Function *F, const std::vector<Arc> &InitialArcs,
+             std::vector<Update> Updates);
+
+  BasicBlock *getOrAddBlock(StringRef BlockName);
+  Optional<Update> getNextUpdate() const;
+  Optional<Update> applyUpdate();
+  void dump(raw_ostream &OS = dbgs()) const;
+
+private:
+  void buildCFG(const std::vector<Arc> &Arcs);
+  bool connect(const Arc &A);
+  bool disconnect(const Arc &A);
+
+  Function *F;
+  unsigned UpdateIdx = 0;
+  StringMap<BasicBlock *> NameToBlock;
+  std::set<Arc> Arcs;
+  std::vector<Update> Updates;
+};
+
+} // namespace llvm
+
+#endif

llvm/trunk/unittests/IR/CFGBuilder.cpp

+//===- llvm/Testing/Support/CFGBuilder.cpp --------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "CFGBuilder.h"
+
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/TypeBuilder.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "gtest/gtest.h"
+
+#include <tuple>
+
+#define DEBUG_TYPE "cfg-builder"
+
+using namespace llvm;
+
+CFGHolder::CFGHolder(StringRef ModuleName, StringRef FunctionName)
+    : Context(llvm::make_unique<LLVMContext>()),
+      M(llvm::make_unique<Module>(ModuleName, *Context)) {
+  FunctionType *FTy = TypeBuilder<void(), false>::get(*Context);
+  F = cast<Function>(M->getOrInsertFunction(FunctionName, FTy));
+}
+CFGHolder::~CFGHolder() = default;
+
+bool llvm::operator<(const CFGBuilder::Arc &LHS, const CFGBuilder::Arc &RHS) {
+  return std::tie(LHS.From, LHS.To) < std::tie(RHS.From, RHS.To);
+}
+
+CFGBuilder::CFGBuilder(Function *F, const std::vector<Arc> &InitialArcs,
+                       std::vector<Update> Updates)
+    : F(F), Updates(std::move(Updates)) {
+  assert(F);
+  buildCFG(InitialArcs);
+}
+
+static void ConnectBlocks(BasicBlock *From, BasicBlock *To) {
+  DEBUG(dbgs() << "Creating BB arc " << From->getName() << " -> "
+               << To->getName() << "\n";
+        dbgs().flush());
+  auto *IntTy = IntegerType::get(From->getContext(), 32);
+
+  if (isa<UnreachableInst>(From->getTerminator()))
+    From->getTerminator()->eraseFromParent();
+  if (!From->getTerminator()) {
+    IRBuilder<> IRB(From);
+    IRB.CreateSwitch(ConstantInt::get(IntTy, 0), To);
+    return;
+  }
+
+  SwitchInst *SI = cast<SwitchInst>(From->getTerminator());
+  const auto Last = SI->getNumCases();
+
+  auto *IntVal = ConstantInt::get(IntTy, Last);
+  SI->addCase(IntVal, To);
+}
+
+static void DisconnectBlocks(BasicBlock *From, BasicBlock *To) {
+  DEBUG(dbgs() << "Deleting BB arc " << From->getName() << " -> "
+               << To->getName() << "\n";
+        dbgs().flush());
+  SwitchInst *SI = cast<SwitchInst>(From->getTerminator());
+
+  if (SI->getNumCases() == 0) {
+    SI->eraseFromParent();
+    IRBuilder<> IRB(From);
+    IRB.CreateUnreachable();
+    return;
+  }
+
+  if (SI->getDefaultDest() == To) {
+    auto FirstC = SI->case_begin();
+    SI->setDefaultDest(FirstC->getCaseSuccessor());
+    SI->removeCase(FirstC);
+    return;
+  }
+
+  for (auto CIt = SI->case_begin(); CIt != SI->case_end(); ++CIt)
+    if (CIt->getCaseSuccessor() == To) {
+      SI->removeCase(CIt);
+      return;
+    }
+}
+
+BasicBlock *CFGBuilder::getOrAddBlock(StringRef BlockName) {
+  auto BIt = NameToBlock.find(BlockName);
+  if (BIt != NameToBlock.end())
+    return BIt->second;
+
+  auto *BB = BasicBlock::Create(F->getParent()->getContext(), BlockName, F);
+  IRBuilder<> IRB(BB);
+  IRB.CreateUnreachable();
+  NameToBlock[BlockName] = BB;
+  return BB;
+}
+
+bool CFGBuilder::connect(const Arc &A) {
+  BasicBlock *From = getOrAddBlock(A.From);
+  BasicBlock *To = getOrAddBlock(A.To);
+  if (Arcs.count(A) != 0)
+    return false;
+
+  Arcs.insert(A);
+  ConnectBlocks(From, To);
+  return true;
+}
+
+bool CFGBuilder::disconnect(const Arc &A) {
+  assert(NameToBlock.count(A.From) != 0 && "No block to disconnect (From)");
+  assert(NameToBlock.count(A.To) != 0 && "No block to disconnect (To)");
+  if (Arcs.count(A) == 0)
+    return false;
+
+  BasicBlock *From = getOrAddBlock(A.From);
+  BasicBlock *To = getOrAddBlock(A.To);
+  Arcs.erase(A);
+  DisconnectBlocks(From, To);
+  return true;
+}
+
+void CFGBuilder::buildCFG(const std::vector<Arc> &NewArcs) {
+  for (const auto &A : NewArcs) {
+    const bool Connected = connect(A);
+    (void)Connected;
+    assert(Connected);
+  }
+}
+
+Optional<CFGBuilder::Update> CFGBuilder::getNextUpdate() const {
+  if (UpdateIdx == Updates.size())
+    return None;
+  return Updates[UpdateIdx];
+}
+
+Optional<CFGBuilder::Update> CFGBuilder::applyUpdate() {
+  if (UpdateIdx == Updates.size())
+    return None;
+  Update NextUpdate = Updates[UpdateIdx++];
+  if (NextUpdate.Action == ActionKind::Insert)
+    connect(NextUpdate.Arc);
+  else
+    disconnect(NextUpdate.Arc);
+
+  return NextUpdate;
+}
+
+void CFGBuilder::dump(raw_ostream &OS) const {
+  OS << "Arcs:\n";
+  size_t i = 0;
+  for (const auto &A : Arcs)
+    OS << "  " << i++ << ":\t" << A.From << " -> " << A.To << "\n";
+
+  OS << "Updates:\n";
+  i = 0;
+  for (const auto &U : Updates) {
+    OS << (i + 1 == UpdateIdx ? "->" : "  ") << i
+       << ((U.Action == ActionKind::Insert) ? "\tIns " : "\tDel ") << U.Arc.From
+       << " -> " << U.Arc.To << "\n";
+    ++i;
+  }
+}
+
+//---- CFGBuilder tests ---------------------------------------------------===//
+
+TEST(CFGBuilder, Construction) {
+  CFGHolder Holder;
+  std::vector<CFGBuilder::Arc> Arcs = {{"entry", "a"}, {"a", "b"}, {"a", "c"},
+                                       {"c", "d"},     {"d", "b"}, {"d", "e"},
+                                       {"d", "f"},     {"e", "f"}};
+  CFGBuilder B(Holder.F, Arcs, {});
+
+  EXPECT_TRUE(B.getOrAddBlock("entry") == &Holder.F->getEntryBlock());
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
+  EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("b")->getTerminator()));
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
+
+  auto *DSwitch = cast<SwitchInst>(B.getOrAddBlock("d")->getTerminator());
+  // d has 3 successors, but one of them if going to be a default case
+  EXPECT_EQ(DSwitch->getNumCases(), 2U);
+  EXPECT_FALSE(B.getNextUpdate()); // No updates to apply.
+}
+
+TEST(CFGBuilder, Insertions) {
+  CFGHolder Holder;
+  const auto Insert = CFGBuilder::ActionKind::Insert;
+  std::vector<CFGBuilder::Update> Updates = {
+      {Insert, {"entry", "a"}}, {Insert, {"a", "b"}}, {Insert, {"a", "c"}},
+      {Insert, {"c", "d"}},     {Insert, {"d", "b"}}, {Insert, {"d", "e"}},
+      {Insert, {"d", "f"}},     {Insert, {"e", "f"}}};
+  const size_t NumUpdates = Updates.size();
+
+  CFGBuilder B(Holder.F, {}, Updates);
+
+  size_t i = 0;
+  while (B.applyUpdate())
+    ++i;
+  EXPECT_EQ(i, NumUpdates);
+
+  EXPECT_TRUE(B.getOrAddBlock("entry") == &Holder.F->getEntryBlock());
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
+  EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("b")->getTerminator()));
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
+
+  auto *DSwitch = cast<SwitchInst>(B.getOrAddBlock("d")->getTerminator());
+  // d has 3 successors, but one of them if going to be a default case
+  EXPECT_EQ(DSwitch->getNumCases(), 2U);
+  EXPECT_FALSE(B.getNextUpdate()); // No updates to apply.
+}
+
+TEST(CFGBuilder, Deletions) {
+  CFGHolder Holder;
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"entry", "a"}, {"a", "b"}, {"a", "c"}, {"c", "d"}, {"d", "b"}};
+  const auto Delete = CFGBuilder::ActionKind::Delete;
+  std::vector<CFGBuilder::Update> Updates = {
+      {Delete, {"c", "d"}}, {Delete, {"a", "c"}}, {Delete, {"entry", "a"}},
+  };
+  const size_t NumUpdates = Updates.size();
+
+  CFGBuilder B(Holder.F, Arcs, Updates);
+
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("c")->getTerminator()));
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
+
+  auto UpdateC = B.applyUpdate();
+
+  EXPECT_TRUE(UpdateC);
+  EXPECT_EQ(UpdateC->Action, CFGBuilder::ActionKind::Delete);
+  EXPECT_EQ(UpdateC->Arc.From, "c");
+  EXPECT_EQ(UpdateC->Arc.To, "d");
+  EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("c")->getTerminator()));
+
+  size_t i = 1;
+  while (B.applyUpdate())
+    ++i;
+  EXPECT_EQ(i, NumUpdates);
+
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
+  EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("entry")->getTerminator()));
+}
+
+TEST(CFGBuilder, Rebuild) {
+  CFGHolder Holder;
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"entry", "a"}, {"a", "b"}, {"a", "c"}, {"c", "d"}, {"d", "b"}};
+  const auto Insert = CFGBuilder::ActionKind::Insert;
+  const auto Delete = CFGBuilder::ActionKind::Delete;
+  std::vector<CFGBuilder::Update> Updates = {
+      {Delete, {"c", "d"}}, {Delete, {"a", "c"}}, {Delete, {"entry", "a"}},
+      {Insert, {"c", "d"}}, {Insert, {"a", "c"}}, {Insert, {"entry", "a"}},
+  };
+  const size_t NumUpdates = Updates.size();
+
+  CFGBuilder B(Holder.F, Arcs, Updates);
+  size_t i = 0;
+  while (B.applyUpdate())
+    ++i;
+  EXPECT_EQ(i, NumUpdates);
+
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("c")->getTerminator()));
+  EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
+}

llvm/trunk/unittests/IR/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
   Passes
   )
 
 set(IRSources
   AsmWriterTest.cpp
   AttributesTest.cpp
   BasicBlockTest.cpp
+  CFGBuilder.cpp
   ConstantRangeTest.cpp
   ConstantsTest.cpp
   DebugInfoTest.cpp
   DebugTypeODRUniquingTest.cpp
   DominatorTreeTest.cpp
   FunctionTest.cpp
   PassBuilderCallbacksTest.cpp
   IRBuilderTest.cpp