[WIP!][Dominators] Add a tool for benchmarking the incremental updater

[kuhar]

Summary

NOTE: This is a *very* work-in-progress patch and I don't intend to commit it. Please ignore it.

A short braindump:
Benchmarking the DominatorTree batch updater is a bit difficult right now, because it doesn't get widely used. Profiling it directly produces just a lot of noise. The other problem is that the update sequences produces by LoopRotation and LoopUnswitching ten to be very short (<= 3), which won't be representative of other real-world uses.

My idea for benchmarking it is to create a new tool that reads bitcode files and turns them into new modules with IR emitted with the CFGBuilder, so that it's easy to randomly generate some update sequence and apply it on the CFG. It should be easy to add a command line parameter for specifying absolute and relative update sequence lengths, ratio of insertions to deletions, etc.

My initial benchmarks on CFGs and update sequences generated manually suggest that there isn't any obvious *static* scheduling for batch updates. This is kind of expected, as different permutations of updates affect the dynamic depth in dominator trees. Because of that, we need to find a way to estimate the intermediate depth in the domiantor tree at the update point. The general heuristic that seems to work fine in my test is to maximize the total depth where the updates start, meaning, we want to perform the updates as deep in the tree as possible. This should work by minimizing the chance of recomputing bigger subtrees, as the incremental algorithm performs tree updates that are bounded by the depth in the tree.
But at this point, I don't know how to do that, and I need more data too support my intuition and observe some properties of the incremental algorithm.

[kuhar]

To make it more clear, the simplest dynamic scheduling that I'd expect to work somewhat reasonably would be to look ahead on the next N updates in the update sequence, and greedily pick the one that us lowest in the tree. (And N could be min(UpdatesLeft, SmallConstant = 64)).

[grosser]

I mark this as requesting changes such that it does not appear in my "to-review" queue. Looking forward to see this evolve.

tools/LLVMBuild.txt

 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [common]
 subdirectories =
  bugpoint
  dsymutil
+ dt-benchmark
  llc
  lli
  llvm-ar
  llvm-as
  llvm-bcanalyzer
  llvm-cat
  llvm-cov
  llvm-cvtres

tools/dt-benchmark/CFGB.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 <tuple>
+#include <vector>
+
+namespace llvm {
+
+  class LLVMContext;
+  class Module;
+  class Function;
+  class BasicBlock;
+  class raw_ostream;
+
+namespace Benchmark {
+
+  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) {
+        return std::tie(LHS.From, LHS.To) <
+               std::tie(RHS.From, RHS.To);
+      }
+    };
+
+    enum class ActionKind { Insert, Delete };
+    struct Update {
+      ActionKind Action;
+      Arc Edge;
+    };
+
+    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 Benchmark
+
+} // namespace llvm
+
+#endif

tools/dt-benchmark/CFGB.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 "CFGB.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"
+
+#define DEBUG_TYPE "cfg-builder"
+
+using namespace llvm;
+using namespace llvm::Benchmark;
+
+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;
+
+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) {
+    connect(A);
+  }
+}
+
+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.Edge);
+  else
+    disconnect(NextUpdate.Edge);
+
+  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.Edge.From << " -> " << U.Edge.To << "\n";
+    ++i;
+  }
+}
+

tools/dt-benchmark/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Analysis
+  BitReader
+  BitWriter
+  Core
+  IRReader
+  Support
+  )
+
+add_llvm_tool(dt-benchmark
+    dt-benchmark.cpp
+    CFGB.cpp
+  )

tools/dt-benchmark/LLVMBuild.txt

+;===- ./tools/dt-benchmark/LLVMBuild.txt -----------------------*- Conf -*--===;
+;
+;                     The LLVM Compiler Infrastructure
+;
+; This file is distributed under the University of Illinois Open Source
+; License. See LICENSE.TXT for details.
+;
+;===------------------------------------------------------------------------===;
+;
+; This is an LLVMBuild description file for the components in this subdirectory.
+;
+; For more information on the LLVMBuild system, please see:
+;
+;   http://llvm.org/docs/LLVMBuild.html
+;
+;===------------------------------------------------------------------------===;
+
+[component_0]
+type = Tool
+name = dt-benchmark
+parent = Tools
+required_libraries = BitReader

tools/dt-benchmark/dt-benchmark.cpp

+//===-- dt-benchmark.cpp - DomTrees benchmarking tool  --------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/Dominators.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/IR/TypeBuilder.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/PrettyStackTrace.h"
+#include "llvm/Support/Program.h"
+#include "llvm/Support/Signals.h"
+#include "llvm/Support/SourceMgr.h"
+
+#include "CFGB.h"
+
+#include <chrono>
+#include <fstream>
+#include <random>
+#include <sstream>
+
+#define DEBUG_TYPE "dt-benchmark"
+
+using namespace llvm;
+using namespace llvm::Benchmark;
+
+static cl::opt<std::string> InputFile(cl::Positional, cl::desc("<input file>"),
+                                      cl::Required);
+static cl::opt<unsigned> Iterations("i", cl::desc("No iterations"),
+                                    cl::init(1));
+
+static cl::opt<bool> BDT("dt", cl::desc("Benchmark DT"));
+static cl::opt<bool> BPDT("pdt", cl::desc("Benchmark PDT"));
+
+static cl::opt<bool> Verify("verify", cl::desc("Verify correctness"),
+                            cl::init(false));
+static cl::opt<bool> Progress("progress", cl::desc("Show progress"));
+
+extern bool llvm::VerifyDomInfo;
+
+static std::unique_ptr<Module> GetModule(StringRef Filename) {
+  auto *Context = new LLVMContext();
+  SMDiagnostic Diags;
+  auto M = parseIRFile(InputFile, Diags, *Context);
+  if (!M)
+    Diags.print(InputFile.c_str(), errs());
+
+  return M;
+}
+
+template <typename F>
+std::chrono::microseconds Time(StringRef Desc, F Fun, int No = -1,
+                               int Total = -1) {
+  const auto StartTime = std::chrono::steady_clock::now();
+  Fun();
+  const auto EndTime = std::chrono::steady_clock::now();
+  const auto ElapsedMs = std::chrono::duration_cast<std::chrono::microseconds>(
+      EndTime - StartTime);
+
+  if (Progress) {
+    std::string Buff;
+    raw_string_ostream RSO(Buff);
+    RSO << '[' << No << '/' << Total << "]\t";
+    RSO << Desc << "\t" << ElapsedMs.count() << "\tus\n";
+    RSO.flush();
+    outs() << Buff;
+  }
+  return ElapsedMs;
+};
+
+static void RunOld(Module &M) {
+  const int NumFun = M.getFunctionList().size();
+  int current = -1;
+  std::chrono::microseconds TotalElapsed{0};
+  for (auto &F : M.getFunctionList()) {
+    if (F.getBasicBlockList().empty())
+      continue;
+
+    DEBUG(dbgs() << F.getName() << "\n");
+
+    TotalElapsed += Time("Old DT",
+                         [&] {
+                           DominatorTree DT(F);
+                         },
+                         ++current, NumFun);
+  }
+
+  outs() << "Old DT\t" << TotalElapsed.count() << "\tus\n";
+}
+
+static bool AreConnected(BasicBlock *A, BasicBlock *B) {
+  assert(A && B);
+  return llvm::find(successors(A), B) != succ_end(A);
+}
+
+static void RunBenchmark(Module& M) {
+  DEBUG(dbgs() << "Converting to CFG-only\n");
+  LLVMContext Context;
+  Module CFGM("benchmark", Context);
+  FunctionType *FTy = TypeBuilder<void(), false>::get(Context);
+
+  for (auto &F : M.functions()) {
+    auto *NF = cast<Function>(CFGM.getOrInsertFunction(F.getName(), FTy));
+
+    std::vector<CFGBuilder::Arc> Arcs;
+    std::vector<StringRef> BBNames;
+    std::vector<BasicBlock *> BBs;
+
+    for (BasicBlock &BB : F) {
+      BBs.push_back(&BB);
+      BBNames.push_back(BB.getName());
+      StringRef BBName = BB.getName();
+      for (auto *Succ : successors(&BB))
+        Arcs.push_back({BBName, Succ->getName()});
+    }
+
+    DenseSet<std::pair<BasicBlock *, BasicBlock *>> Enqueued;
+    std::vector<CFGBuilder::Update> Updates;
+
+    const size_t NumUpdates = 10;
+    while(Updates.size() < NumUpdates) {
+      BasicBlock *A;
+      BasicBlock *B;
+
+      //if (!Enqueued.count({}))
+    }
+
+
+    CFGBuilder Builder(NF, Arcs, {});
+    DEBUG(dbgs() << (NF->getName()) << "\n");
+  }
+}
+
+int main(int argc, char **argv) {
+  sys::PrintStackTraceOnErrorSignal(argv[0]);
+  PrettyStackTraceProgram X(argc, argv);
+  cl::ParseCommandLineOptions(argc, argv, "dominators");
+
+  auto M = GetModule(InputFile);
+  if (!M)
+    return 1;
+
+  outs() << "Bitcode read; module has " << M->getFunctionList().size()
+         << " functions\n";
+
+  VerifyDomInfo = Verify.getValue();
+  if (VerifyDomInfo)
+    outs() << "=== Verification on ===\n";
+
+  if (BDT) {
+    RunBenchmark(*M);
+  }
+  return 0;
+}