[Examples] Add IRTransformations directory to examples.

[fhahn]

Summary

This patch adds a new IRTransformations directory to llvm/examples/. This is
intended to serve as a new home for example transformations/analysis
code used by various tutorials.

If LLVM_BUILD_EXAMPLES is enabled, the ExamplesIRTransforms library is
linked into the opt binary and the example passes become available.

To start off with, it contains the CFG simplifications used in the IR
part of the 'Getting Started With LLVM: Basics' tutorial at the US LLVM
Developers Meeting 2019.

[fhahn]

Move struct for new PM pass to .cpp file

[paquette]

llvm/examples/IRTransforms/TutorialSimplifyCFG.cpp

375 ↗

(On Diff #226359)

Is there any reason that we don't check the version like in the legacy runOnFunction?

[Meinersbur]

llvm/tools/opt/opt.cpp

564–566

I'd prefer if the production code stays distinct from examples. In this case D61446 would allow a solution.

[andwar]

I think that having a reference to these examples somewhere in the official docs would be very helpful. Maybe somewhere here: http://llvm.org/docs/WritingAnLLVMPass.html?

[nit] I'd keep the names of files and passes shorter and remove 'Tutorial' from names. IMHO it doesn't really add much in terms of self-documentation, yet makes everything a bit harder to read.

llvm/examples/IRTransforms/TutorialSimplifyCFG.cpp

17 ↗

(On Diff #226359)

[nit] Unnecessary empty line.

54 ↗

(On Diff #226359)

Commented out code is most likely to become stale - I'd remove it.

58 ↗

(On Diff #226359)

[nit] 'a undef' --> 'an undef'

95 ↗

(On Diff #226359)

Same as above.

140 ↗

(On Diff #226359)

'second first' --> 'first'

176 ↗

(On Diff #226359)

'second third' -> 'third'?

177 ↗

(On Diff #226359)

[nit] 'use' -> 'uses'

llvm/examples/IRTransforms/TutorialSimplifyCFG.h

17 ↗

(On Diff #226359)

[nit] Did you mean initializeTutorialSimplifyCFGLegacyPMPass instead?

[fhahn]

Address review comments: removed tutorial from file names, fixed comments, match tutorial version in the NewPM as well. Also added a few TODOs and ideas for future improvements.

[fhahn]

llvm/examples/IRTransforms/TutorialSimplifyCFG.cpp

54 ↗

(On Diff #226359)

Yes, ideally it should be also uncommented, but I am not entirely sure yet how to best integrate such small variations. I'd like to leave it in, with a todo for now.

375 ↗

(On Diff #226359)

Nope, I just missed it! Updated. Although the pass still needs to be hooked up properly so the new PM actually knows about it. I've added a TODO

llvm/examples/IRTransforms/TutorialSimplifyCFG.h

17 ↗

(On Diff #226359)

Nope, the INITIALIZE_PASS macros will add a Pass at the end of the pass class name.

llvm/tools/opt/opt.cpp

564–566

I think we should move to the mechanism, once it lands. In the meantime, I think having that in opt should be low risk, as opt is mostly used for testing anyways and the example passes are completely separated from the transforms library.

[fhahn]

In D69416#1722297, @andwar wrote:

I think that having a reference to these examples somewhere in the official docs would be very helpful. Maybe somewhere here: http://llvm.org/docs/WritingAnLLVMPass.html?

Agreed, we should integrate the new examples in the official docs. WritingAnLLVMPass seems like a good candidate, but currently it seems a bit crowded already and I'd like to think about how to best integrate it a bit more carefully.

[nit] I'd keep the names of files and passes shorter and remove 'Tutorial' from names. IMHO it doesn't really add much in terms of self-documentation, yet makes everything a bit harder to read.

Yep, it should already be obvious from the path and the tutorial part seems redundant. But I have no strong feelings either way.

[andwar]

Includes are missing in SimplifyCFG.h:

cmake -G Ninja -DLLVM_TARGETS_TO_BUILD=X86 -DCMAKE_BUILD_TYPE=Release   -DLLVM_USE_NEWPM=On -DLLVM_BUILD_EXAMPLES=On ../../llvm/
(...)
ninja opt
(...)
/work/llvm-project/llvm/examples/IRTransforms/SimplifyCFG.h:15:1: error: unknown type name 'FunctionPass'
FunctionPass *createSimplifyCFGPass();
^
/work/llvm-project/llvm/examples/IRTransforms/SimplifyCFG.h:17:40: error: unknown type name 'PassRegistry'
void initializeSimplifyCFGLegacyPMPass(PassRegistry &);
                                       ^

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg-blockaddress.ll

17

[nit] For this example the names of BBs are rather irrelevant, but if.then (or if.else) could suggest otherwise. Maybe worth renaming? Just a thought.

[fhahn]

Fix build error, changed if.then;if.else BB names to bb1 and bb2.

[andwar]

This is great stuff, thank you for doing this!

1. Why not test with all versions (v1, v2 and v3) in all tests? Does the output change?
2. AFAIK there are no official guidelines on this (and both approaches are used in practice), but I'd rename SimplifyCFGLegacyPass to SimplifyCFGLegacy (fewer characters, meaning still clear). But please use the one you prefer the most.
3. I'd prefer to see this fully working with the new PM or no new PM support at all. Otherwise it can be confusing.

llvm/examples/IRTransforms/SimplifyCFG.cpp

11

1. Could you add a quick summary of your passes (and the variants)? Also, since this a tutorial - maybe also worth mentioning the tests? They are an integral part of this, but this could be non-obvious for beginners.
2. "implements" twice
3. Definitely worth adding a link to the video (once it's uploaded)

16

Why not do it now? AFAIK it's been agreed that the new PM is to become the default.

If you prefer to leave it for later then I wouldn't be adding the new PM implementation at all. It's currently not used and not tested.

124

[nit] This is (together with v2 and v3) your least commented function.

373–375

AFAIK, this is neither used nor needed.

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg2-dead-block-order.ll

45

The following line suggests that BB_2 is always bb.2. You don't need a regex here.

92

[nit] extra line

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg3-phis.ll

24

The following line suggests that BB_3 is always bb.3.

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg4-multiple-duplicate-cfg-updates.ll

5

Won't the default version (i.e. v1) invalidate the DominatorTree? (i.e. it won't use DomTreeUpdater).

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg6-dead-self-loop.ll

19

DELETEME

[fhahn]

Thanks. Updated to address the comments.

In D69416#1733007, @andwar wrote:

This is great stuff, thank you for doing this!

1. Why not test with all versions (v1, v2 and v3) in all tests? Does the output change?

Nope, I just did not update all tests. it's done now :)

2. AFAIK there are no official guidelines on this (and both approaches are used in practice), but I'd rename SimplifyCFGLegacyPass to SimplifyCFGLegacy (fewer characters, meaning still clear). But please use the one you prefer the most.

I'd prefer to keep it as is for now.

3. I'd prefer to see this fully working with the new PM or no new PM support at all. Otherwise it can be confusing.

Agreed, I've removed the partial new PM stuff for now.

llvm/examples/IRTransforms/SimplifyCFG.cpp

16

I'd prefer to get a first version in sooner rather than later and do the new PM support as follow-up. I've removed the NewPM stuff in the meantime.

373–375

That's a leftover from living in lib/Transforms. I've had it in the passmanagerbuilder as well.

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg2-dead-block-order.ll

45

That's what the autogeneration script generates. I agree it's not ideal and we should fix it there.

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg3-phis.ll

24

Same as earlier, this should be fixed in the generation script.

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg4-multiple-duplicate-cfg-updates.ll

5

Yes, this is just relevant for the DomTreeUpdater version. It's tested now.

[andwar]

LGTM

Thanks for addressing my comments!

[paquette]

LGTM aside from typos

llvm/examples/IRTransforms/SimplifyCFG.cpp

76

s/remote/remove/

117

s/remote/remove/

157

typo: predecessors

193

typo on predecessors here too

[fhahn]

Thanks for the reviews everyone :)

[svenvh]

llvm/tools/opt/opt.cpp

564–566

This change seems to be causing a problem with the nightly packages from apt.llvm.org. Installing the packages llvm-10-tools llvm-10-dev clang-format-10 clang-tidy-10 libclang-10-dev lldb-10 without installing the examples makes the exported cmake files unusable:

CMake Error at /usr/lib/llvm-10/lib/cmake/llvm/LLVMExports.cmake:1350 (message):
  The imported target "ExampleIRTransforms" references the file

     "/usr/lib/llvm-10/lib/libExampleIRTransforms.a"

  but this file does not exist.  Possible reasons include:

  * The file was deleted, renamed, or moved to another location.

  * An install or uninstall procedure did not complete successfully.

  * The installation package was faulty and contained

     "/usr/lib/llvm-10/lib/cmake/llvm/LLVMExports.cmake"

  but not all the files it references.

Call Stack (most recent call first):
  /usr/lib/llvm-10/cmake/LLVMConfig.cmake:256 (include)
  CMakeLists.txt:29 (find_package)

[fhahn]

llvm/tools/opt/opt.cpp

564–566

Thanks, I'll take a look!

[svenvh]

llvm/tools/opt/opt.cpp

564–566

After taking a closer look, installing the llvm-10-examples package actually does not solve the problem; cmake still fails with the same error.

[fhahn]

llvm/tools/opt/opt.cpp

564–566

I think it should be fixed by D70590, which excludes libExampleIRTransforms.a from the ALL target.

[fhahn]

llvm/tools/opt/opt.cpp

564–566

@svenvh I've recommitted the change with a fix that should address the issue. Please let me know if the problem you are seeing re-surfaces.

[svenvh]

llvm/tools/opt/opt.cpp

564–566

Thanks @fhahn! It seems fine now, though a similar problem (unrelated to your commit) appeared on the "Bye" example.

llvm/CMakeLists.txt

option(LLVM_BUILD_RUNTIMES
   "Build the LLVM runtimes. If OFF, just generate build targets." ON)
 
 option(LLVM_BUILD_RUNTIME
   "Build the LLVM runtime libraries." ON)
 option(LLVM_BUILD_EXAMPLES
   "Build the LLVM example programs. If OFF, just generate build targets." OFF)
 option(LLVM_INCLUDE_EXAMPLES "Generate build targets for the LLVM examples" ON)
 
+if(LLVM_BUILD_EXAMPLES)
+  add_definitions(-DBUILD_EXAMPLES)
+endif(LLVM_BUILD_EXAMPLES)
+
 option(LLVM_BUILD_TESTS
   "Build LLVM unit tests. If OFF, just generate build targets." OFF)
 option(LLVM_INCLUDE_TESTS "Generate build targets for the LLVM unit tests." ON)
 option(LLVM_INCLUDE_GO_TESTS "Include the Go bindings tests in test build targets." ON)
 
 option(LLVM_BUILD_BENCHMARKS "Add LLVM benchmark targets to the list of default
 targets. If OFF, benchmarks still could be built using Benchmarks target." OFF)
 option(LLVM_INCLUDE_BENCHMARKS "Generate benchmark targets. If OFF, benchmarks can't be built." ON)

llvm/examples/CMakeLists.txt

 add_subdirectory(BrainF)
 add_subdirectory(Fibonacci)
 add_subdirectory(HowToUseJIT)
 add_subdirectory(HowToUseLLJIT)
+add_subdirectory(IRTransforms)
 add_subdirectory(LLJITExamples)
 add_subdirectory(Kaleidoscope)
 add_subdirectory(ModuleMaker)
 add_subdirectory(SpeculativeJIT)
 
 if(LLVM_ENABLE_EH AND (NOT WIN32) AND (NOT "${LLVM_NATIVE_ARCH}" STREQUAL "ARM"))
     add_subdirectory(ExceptionDemo)
 endif()
 
 if( HAVE_PTHREAD_H )
   add_subdirectory(ParallelJIT)
 endif( HAVE_PTHREAD_H )

llvm/examples/IRTransforms/CMakeLists.txt

+add_llvm_library(ExampleIRTransforms
+  InitializePasses.cpp
+  SimplifyCFG.cpp
+
+  ADDITIONAL_HEADER_DIRS
+
+  DEPENDS
+  intrinsics_gen
+  )

llvm/examples/IRTransforms/InitializePasses.h

+//===- InitializePasses.h - -------------------------------------*- C++ -*-===//
+//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_EXAMPLES_IRTRANSFORMS_INITIALIZEPASSES__H
+#define LLVM_EXAMPLES_IRTRANSFORMS_INITIALIZEPASSES__H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+void initializeExampleIRTransforms(PassRegistry &Registry);
+void initializeSimplifyCFGLegacyPassPass(PassRegistry &Registry);
+
+} // end namespace llvm
+
+#endif

llvm/examples/IRTransforms/InitializePasses.cpp

+//===-- InitializePasses.cpp ----------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements implements the initialization hook for the example
+// transforms.
+//
+//===----------------------------------------------------------------------===//
+
+#include "InitializePasses.h"
+#include "llvm/PassRegistry.h"
+
+using namespace llvm;
+
+void initializeExampleIRTransforms(PassRegistry &Registry) {
+  initializeSimplifyCFGLegacyPassPass(Registry);
+}

llvm/examples/IRTransforms/SimplifyCFG.h

+//===- SimplifyCFG.h - Tutorial SimplifyCFG ---------------------*- C++ -*-===//
+//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_EXAMPLES_IRTRANSFORMS_SIMPLIFYCFG__H
+#define LLVM_EXAMPLES_IRTRANSFORMS_SIMPLIFYCFG__H
+
+#include "llvm/Pass.h"
+#include "llvm/PassRegistry.h"
+
+namespace llvm {
+
+FunctionPass *createSimplifyCFGPass();
+
+void initializeSimplifyCFGLegacyPassPass(PassRegistry &);
+
+} // end namespace llvm
+
+#endif // LLVM_EXAMPLES_IRTRANSFORMS_SIMPLIFYCFG__H

llvm/examples/IRTransforms/SimplifyCFG.cpp

+//===- SimplifyCFG.cpp ----------------------------------------------------===//
+//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the control flow graph (CFG) simplifications
+// presented as part of the 'Getting Started With LLVM: Basics' tutorial at the
+// US LLVM Developers Meeting 2019. It also contains additional material.
+//
+// The current file contains three different CFG simplifications. There are
+// multiple versions of each implementation (e.g. _v1 and _v2), which implement
+// additional functionality (e.g. preserving analysis like the DominatorTree) or
+// use additional utilities to simplify the code (e.g. LLVM's PatternMatch.h).
+// The available simplifications are:
+//  1. Trivially Dead block Removal (removeDeadBlocks_v[1,2]).
+//     This simplifications removes all blocks without predecessors in the CFG
+//     from a function.
+//  2. Conditional Branch Elimination (eliminateCondBranches_v[1,2,3])
+//     This simplification replaces conditional branches with constant integer
+//     conditions with unconditional branches.
+//  3. Single Predecessor Block Merging (mergeIntoSinglePredecessor_v[1,2])
+//     This simplification merges blocks with a single predecessor into the
+//     predecessor, if that block has a single successor.
+//
+// TODOs
+//  * Hook up pass to the new pass manager.
+//  * Preserve LoopInfo.
+//  * Add fixed point iteration to delete all dead blocks
+//  * Add implementation using reachability to discover dead blocks.
+//===----------------------------------------------------------------------===//
+
+#include "SimplifyCFG.h"
+#include "InitializePasses.h"
+#include "llvm/Analysis/DomTreeUpdater.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/CommandLine.h"
+
+using namespace llvm;
+using namespace PatternMatch;
+
+enum TutorialVersion { V1, V2, V3 };
+static cl::opt<TutorialVersion>
+    Version("tut-simplifycfg-version", cl::desc("Select tutorial version"),
+            cl::Hidden, cl::ValueOptional, cl::init(V1),
+            cl::values(clEnumValN(V1, "v1", "version 1"),
+                       clEnumValN(V2, "v2", "version 2"),
+                       clEnumValN(V3, "v3", "version 3"),
+                       // Sentinel value for unspecified option.
+                       clEnumValN(V3, "", "")));
+
+#define DEBUG_TYPE "tut-simplifycfg"
+
+// Remove trivially dead blocks. First version, not preserving the
+// DominatorTree.
+static bool removeDeadBlocks_v1(Function &F) {
+  bool Changed = false;
+
+  // Remove trivially dead blocks.
+  for (BasicBlock &BB : make_early_inc_range(F)) {
+    // Skip blocks we know to not be trivially dead. We know a block is
+    // guaranteed to be dead, iff it is neither the entry block nor
+    // has any predecessors.
+    if (&F.getEntryBlock() == &BB || !pred_empty(&BB))
+      continue;
+
+    // Notify successors of BB that BB is going to be removed. This removes
+    // incoming values from BB from PHIs in the successors. Note that this will
+    // not actually remove BB from the predecessor lists of its successors.
+    for (BasicBlock *Succ : successors(&BB))
+      Succ->removePredecessor(&BB);
+    // TODO: Find a better place to put such small variations.
+    // Alternatively, we can update the PHI nodes manually:
+    // for (PHINode &PN : make_early_inc_range(Succ->phis()))
+    //  PN.removeIncomingValue(&BB);
+
+    // Replace all instructions in BB with an undef constant. The block is
+    // unreachable, so the results of the instructions should never get used.
+    while (!BB.empty()) {
+      Instruction &I = BB.back();
+      I.replaceAllUsesWith(UndefValue::get(I.getType()));
+      I.eraseFromParent();
+    }
+
+    // Finally remove the basic block.
+    BB.eraseFromParent();
+    Changed = true;
+  }
+
+  return Changed;
+}
+
+// Remove trivially dead blocks. This is the second version and preserves the
+// dominator tree.
+static bool removeDeadBlocks_v2(Function &F, DominatorTree &DT) {
+  bool Changed = false;
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
+
+  // Remove trivially dead blocks.
+  for (BasicBlock &BB : make_early_inc_range(F)) {
+    // Skip blocks we know to not be trivially dead. We know a block is
+    // guaranteed to be dead, iff it is neither the entry block nor
+    // has any predecessors.
+    if (&F.getEntryBlock() == &BB || !pred_empty(&BB))
+      continue;
+
+    // Notify successors of BB that BB is going to be removed. This removes
+    // incoming values from BB from PHIs in the successors. Note that this will
+    // not actually remove BB from the predecessor lists of its successors.
+    for (BasicBlock *Succ : successors(&BB)) {
+      Succ->removePredecessor(&BB);
+
+      // Collect updates that need to be applied to the dominator tree.
+      DTUpdates.push_back({DominatorTree::Delete, &BB, Succ});
+    }
+
+    // Remove BB via the DomTreeUpdater. DomTreeUpdater::deleteBB conveniently
+    // removes the instructions in BB as well.
+    DTU.deleteBB(&BB);
+    Changed = true;
+  }
+
+  // Apply updates permissively, to remove duplicates.
+  DTU.applyUpdatesPermissive(DTUpdates);
+
+  return Changed;
+}
+
+// Eliminate branches with constant conditionals. This is the first version,
+// which *does not* preserve the dominator tree.
+static bool eliminateCondBranches_v1(Function &F) {
+  bool Changed = false;
+
+  // Eliminate branches with constant conditionals.
+  for (BasicBlock &BB : F) {
+    // Skip blocks without conditional branches as terminators.
+    BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator());
+    if (!BI || !BI->isConditional())
+      continue;
+
+    // Skip blocks with conditional branches without ConstantInt conditions.
+    ConstantInt *CI = dyn_cast<ConstantInt>(BI->getCondition());
+    if (!CI)
+      continue;
+
+    // We use the branch condition (CI), to select the successor we remove:
+    // if CI == 1 (true), we remove the second successor, otherwise the first.
+    BasicBlock *RemovedSucc = BI->getSuccessor(CI->isOne());
+    // Tell RemovedSucc we will remove BB from its predecessors.
+    RemovedSucc->removePredecessor(&BB);
+
+    // Replace the conditional branch with an unconditional one, by creating
+    // a new unconditional branch to the selected successor and removing the
+    // conditional one.
+    BranchInst::Create(BI->getSuccessor(CI->isZero()), BI);
+    BI->eraseFromParent();
+    Changed = true;
+  }
+
+  return Changed;
+}
+
+// Eliminate branches with constant conditionals. This is the second
+// version, which *does* preserve the dominator tree.
+static bool eliminateCondBranches_v2(Function &F, DominatorTree &DT) {
+  bool Changed = false;
+
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
+  // Eliminate branches with constant conditionals.
+  for (BasicBlock &BB : F) {
+    // Skip blocks without conditional branches as terminators.
+    BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator());
+    if (!BI || !BI->isConditional())
+      continue;
+
+    // Skip blocks with conditional branches without ConstantInt conditions.
+    ConstantInt *CI = dyn_cast<ConstantInt>(BI->getCondition());
+    if (!CI)
+      continue;
+
+    // We use the branch condition (CI), to select the successor we remove:
+    // if CI == 1 (true), we remove the second successor, otherwise the first.
+    BasicBlock *RemovedSucc = BI->getSuccessor(CI->isOne());
+    // Tell RemovedSucc we will remove BB from its predecessors.
+    RemovedSucc->removePredecessor(&BB);
+
+    // Replace the conditional branch with an unconditional one, by creating
+    // a new unconditional branch to the selected successor and removing the
+    // conditional one.
+    BranchInst *NewBranch =
+        BranchInst::Create(BI->getSuccessor(CI->isZero()), BI);
+    BI->eraseFromParent();
+
+    // Delete the edge between BB and RemovedSucc in the DominatorTree, iff
+    // the conditional branch did not use RemovedSucc as both the true and false
+    // branches.
+    if (NewBranch->getSuccessor(0) != RemovedSucc)
+      DTUpdates.push_back({DominatorTree::Delete, &BB, RemovedSucc});
+    Changed = true;
+  }
+
+  // Apply updates permissively, to remove duplicates.
+  DTU.applyUpdatesPermissive(DTUpdates);
+
+  return Changed;
+}
+
+// Eliminate branches with constant conditionals. This is the third
+// version, which uses PatternMatch.h.
+static bool eliminateCondBranches_v3(Function &F, DominatorTree &DT) {
+  bool Changed = false;
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
+
+  // Eliminate branches with constant conditionals.
+  for (BasicBlock &BB : F) {
+    ConstantInt *CI = nullptr;
+    BasicBlock *TakenSucc, *RemovedSucc;
+    // Check if the terminator is a conditional branch, with constant integer
+    // condition and also capture the successor blocks as TakenSucc and
+    // RemovedSucc.
+    if (!match(BB.getTerminator(),
+               m_Br(m_ConstantInt(CI), m_BasicBlock(TakenSucc),
+                    m_BasicBlock(RemovedSucc))))
+      continue;
+
+    // If the condition is false, swap TakenSucc and RemovedSucc.
+    if (CI->isZero())
+      std::swap(TakenSucc, RemovedSucc);
+
+    // Tell RemovedSucc we will remove BB from its predecessors.
+    RemovedSucc->removePredecessor(&BB);
+
+    // Replace the conditional branch with an unconditional one, by creating
+    // a new unconditional branch to the selected successor and removing the
+    // conditional one.
+
+    BranchInst *NewBranch = BranchInst::Create(TakenSucc, BB.getTerminator());
+    BB.getTerminator()->eraseFromParent();
+
+    // Delete the edge between BB and RemovedSucc in the DominatorTree, iff
+    // the conditional branch did not use RemovedSucc as both the true and false
+    // branches.
+    if (NewBranch->getSuccessor(0) != RemovedSucc)
+      DTUpdates.push_back({DominatorTree::Delete, &BB, RemovedSucc});
+    Changed = true;
+  }
+
+  // Apply updates permissively, to remove duplicates.
+  DTU.applyUpdatesPermissive(DTUpdates);
+  return Changed;
+}
+
+// Merge basic blocks into their single predecessor, if their predecessor has a
+// single successor. This is the first version and does not preserve the
+// DominatorTree.
+static bool mergeIntoSinglePredecessor_v1(Function &F) {
+  bool Changed = false;
+
+  // Merge blocks with single predecessors.
+  for (BasicBlock &BB : make_early_inc_range(F)) {
+    BasicBlock *Pred = BB.getSinglePredecessor();
+    // Make sure  BB has a single predecessor Pred and BB is the single
+    // successor of Pred.
+    if (!Pred || Pred->getSingleSuccessor() != &BB)
+      continue;
+
+    // Do not try to merge self loops. That can happen in dead blocks.
+    if (Pred == &BB)
+      continue;
+
+    // Need to replace it before nuking the branch.
+    BB.replaceAllUsesWith(Pred);
+    // PHI nodes in BB can only have a single incoming value. Remove them.
+    for (PHINode &PN : make_early_inc_range(BB.phis())) {
+      PN.replaceAllUsesWith(PN.getIncomingValue(0));
+      PN.eraseFromParent();
+    }
+    // Move all instructions from BB to Pred.
+    for (Instruction &I : make_early_inc_range(BB))
+      I.moveBefore(Pred->getTerminator());
+
+    // Remove the Pred's terminator (which jumped to BB). BB's terminator
+    // will become Pred's terminator.
+    Pred->getTerminator()->eraseFromParent();
+    BB.eraseFromParent();
+
+    Changed = true;
+  }
+
+  return Changed;
+}
+
+// Merge basic blocks into their single predecessor, if their predecessor has a
+// single successor. This is the second version and does preserve the
+// DominatorTree.
+static bool mergeIntoSinglePredecessor_v2(Function &F, DominatorTree &DT) {
+  bool Changed = false;
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
+
+  // Merge blocks with single predecessors.
+  for (BasicBlock &BB : make_early_inc_range(F)) {
+    BasicBlock *Pred = BB.getSinglePredecessor();
+    // Make sure  BB has a single predecessor Pred and BB is the single
+    // successor of Pred.
+    if (!Pred || Pred->getSingleSuccessor() != &BB)
+      continue;
+
+    // Do not try to merge self loops. That can happen in dead blocks.
+    if (Pred == &BB)
+      continue;
+
+    // Tell DTU about the changes to the CFG: All edges from BB to its
+    // successors get removed and we add edges between Pred and BB's successors.
+    for (BasicBlock *Succ : successors(&BB)) {
+      DTUpdates.push_back({DominatorTree::Delete, &BB, Succ});
+      DTUpdates.push_back({DominatorTree::Insert, Pred, Succ});
+    }
+    // Also remove the edge between Pred and BB.
+    DTUpdates.push_back({DominatorTree::Delete, Pred, &BB});
+
+    // Need to replace it before nuking the branch.
+    BB.replaceAllUsesWith(Pred);
+    // PHI nodes in BB can only have a single incoming value. Remove them.
+    for (PHINode &PN : make_early_inc_range(BB.phis())) {
+      PN.replaceAllUsesWith(PN.getIncomingValue(0));
+      PN.eraseFromParent();
+    }
+    // Move all instructions from BB to Pred.
+    for (Instruction &I : make_early_inc_range(BB))
+      I.moveBefore(Pred->getTerminator());
+
+    // Remove the Pred's terminator (which jumped to BB). BB's terminator
+    // will become Pred's terminator.
+    Pred->getTerminator()->eraseFromParent();
+    DTU.deleteBB(&BB);
+
+    Changed = true;
+  }
+
+  // Apply updates permissively, to remove duplicates.
+  DTU.applyUpdatesPermissive(DTUpdates);
+  return Changed;
+}
+
+static bool doSimplify_v1(Function &F) {
+  return eliminateCondBranches_v1(F) & mergeIntoSinglePredecessor_v1(F) &
+         removeDeadBlocks_v1(F);
+}
+
+static bool doSimplify_v2(Function &F, DominatorTree &DT) {
+  return eliminateCondBranches_v2(F, DT) &
+         mergeIntoSinglePredecessor_v2(F, DT) & removeDeadBlocks_v2(F, DT);
+}
+
+static bool doSimplify_v3(Function &F, DominatorTree &DT) {
+  return eliminateCondBranches_v3(F, DT) &
+         mergeIntoSinglePredecessor_v2(F, DT) & removeDeadBlocks_v2(F, DT);
+}
+
+namespace {
+struct SimplifyCFGLegacyPass : public FunctionPass {
+  static char ID;
+  SimplifyCFGLegacyPass() : FunctionPass(ID) {
+    initializeSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<DominatorTreeWrapperPass>();
+    // Version 1 of the implementation does not preserve the dominator tree.
+    if (Version != V1)
+      AU.addPreserved<DominatorTreeWrapperPass>();
+
+    FunctionPass::getAnalysisUsage(AU);
+  }
+
+  bool runOnFunction(Function &F) override {
+    if (skipFunction(F))
+      return false;
+
+    switch (Version) {
+    case V1:
+      return doSimplify_v1(F);
+    case V2: {
+      auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+      return doSimplify_v2(F, DT);
+    }
+    case V3: {
+      auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+      return doSimplify_v3(F, DT);
+    }
+    }
+
+    llvm_unreachable("Unsupported version");
+  }
+};
+} // namespace
+
+char SimplifyCFGLegacyPass::ID = 0;
+INITIALIZE_PASS_BEGIN(SimplifyCFGLegacyPass, DEBUG_TYPE,
+                      "Tutorial CFG simplification", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_END(SimplifyCFGLegacyPass, DEBUG_TYPE,
+                    "Tutorial CFG simplifications", false, false)

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg-blockaddress.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 -S < %s | FileCheck %s
+
+define i8* @simp1(i32 %x) {
+; CHECK-LABEL: @simp1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 42
+; CHECK-NEXT:    [[ADDR:%.*]] = select i1 [[CMP]], i8* inttoptr (i32 1 to i8*), i8* inttoptr (i32 1 to i8*)
+; CHECK-NEXT:    ret i8* [[ADDR]]
+;
+entry:
+  %cmp = icmp slt i32 %x, 42
+  %addr = select i1 %cmp, i8* blockaddress(@simp1, %bb1), i8* blockaddress(@simp1, %bb2)
+  ret i8* %addr
+
+bb1:
+  ret i8* null
+
+bb2:
+  ret i8* null
+}

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg1.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 -S < %s | FileCheck %s
+
+define i32 @simp1() {
+; CHECK-LABEL: @simp1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 10
+;
+entry:
+  br i1 true, label %if.then, label %if.else
+
+if.then:
+  ret i32 10
+
+if.else:
+  ret i32 12
+}
+
+define i32 @simp2() {
+; CHECK-LABEL: @simp2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 200
+;
+entry:
+  br i1 false, label %if.then, label %if.else
+
+if.then:
+  ret i32 99
+
+if.else:
+  ret i32 200
+}
+
+declare void @foo(i64)
+
+define i64 @merge_into_predecessor(i64 %a, i64 %b) {
+; CHECK-LABEL: @merge_into_predecessor(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[R:%.*]] = add i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    call void @foo(i64 [[R]])
+; CHECK-NEXT:    call void @foo(i64 [[A]])
+; CHECK-NEXT:    ret i64 [[R]]
+;
+entry:
+  br label %bb.next
+
+bb.next:
+  %r = add i64 %a, %b
+  call void @foo(i64 %r)
+  call void @foo(i64 %a)
+  br label %bb.next.next
+
+bb.next.next:
+  ret i64 %r
+}
+
+define i64 @merge_into_predecessor_with_phi(i64 %a, i64 %b, i1 %c) {
+; CHECK-LABEL: @merge_into_predecessor_with_phi(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @foo(i64 [[B:%.*]])
+; CHECK-NEXT:    [[R:%.*]] = add i64 [[A:%.*]], [[B]]
+; CHECK-NEXT:    call void @foo(i64 [[R]])
+; CHECK-NEXT:    call void @foo(i64 [[A]])
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB_NEXT_NEXT:%.*]], label [[BB_EXIT:%.*]]
+; CHECK:       bb.next.next:
+; CHECK-NEXT:    br label [[BB_EXIT]]
+; CHECK:       bb.exit:
+; CHECK-NEXT:    [[RET:%.*]] = phi i64 [ [[R]], [[ENTRY:%.*]] ], [ 10, [[BB_NEXT_NEXT]] ]
+; CHECK-NEXT:    ret i64 [[RET]]
+;
+entry:
+  call void @foo(i64 %b)
+  br label %bb.next
+
+bb.next:
+  %r = add i64 %a, %b
+  call void @foo(i64 %r)
+  call void @foo(i64 %a)
+  br i1 %c, label %bb.next.next, label %bb.exit
+
+bb.next.next:
+  br label %bb.exit
+
+bb.exit:
+  %ret = phi i64 [ %r, %bb.next], [ 10, %bb.next.next]
+  ret i64 %ret
+
+}

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg2-dead-block-order.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 -S < %s | FileCheck %s
+
+define i32 @remove_dead_blocks() {
+; CHECK-LABEL: @remove_dead_blocks(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+; CHECK-NEXT:  }
+;
+entry:
+  ret i32 1
+
+bb.1:
+  ret i32 2
+
+bb.2:
+  ret i32 3
+}
+
+define i32 @simp1() {
+; CHECK-LABEL: @simp1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+; CHECK:       bb.1:
+; CHECK-NEXT:    ret i32 2
+; CHECK-NEXT:  }
+;
+entry:
+  ret i32 1
+
+bb.1:
+  ret i32 2
+
+bb.2:
+  br i1 undef, label %bb.1, label %bb.3
+
+bb.3:
+  ret i32 3
+}
+
+define i32 @remove_dead_block_with_phi() {
+; CHECK-LABEL: @remove_dead_block_with_phi(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[BB_2:%.*]]
+; CHECK:       bb.2:
+; CHECK-NEXT:    ret i32 1
+; CHECK-NEXT:  }
+;
+entry:
+  br label %bb.2
+
+bb.1:
+  br label %bb.2
+
+bb.2:
+  %rv = phi i32 [ 1, %entry ], [ 2, %bb.1 ]
+  ret i32 %rv
+}
+
+define i32 @remove_dead_blocks_remaining_uses(i32 %a) {
+; CHECK-LABEL: @remove_dead_blocks_remaining_uses(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+; CHECK-NEXT:  }
+;
+entry:
+  ret i32 1
+
+bb.2:
+  ret i32 %res
+
+bb.1:
+  %res = add i32 %a, 10
+  br label %bb.2
+}
+
+define i32 @remove_dead_blocks_remaining_uses2(i32 %a, i1 %cond) {
+; CHECK-LABEL: @remove_dead_blocks_remaining_uses2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+; CHECK:       bb.2:
+; CHECK-NEXT:    [[RES2:%.*]] = add i32 undef, 10
+; CHECK-NEXT:    [[RES3:%.*]] = mul i32 [[RES2]], undef
+; CHECK-NEXT:    ret i32 [[RES3]]
+; CHECK:       bb.3:
+; CHECK-NEXT:    ret i32 undef
+; CHECK-NEXT:  }
+;
+entry:
+  ret i32 1
+
+bb.2:
+  %res2 = add i32 %res, 10
+  %res3 = mul i32 %res2, %res
+  ret i32 %res3
+
+bb.3:
+  br label %bb.4
+
+bb.4:
+  ret i32 %res
+
+bb.1:
+  %res = add i32 %a, 10
+  br i1 %cond, label %bb.2, label %bb.3
+  br label %bb.2
+}

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg3-phis.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 -S < %s | FileCheck %s
+
+define i32 @phi_cond_branch_eliminated() {
+; CHECK-LABEL: @phi_cond_branch_eliminated(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 20
+;
+entry:
+  br i1 true, label %bb.2, label %bb.3
+
+bb.2:
+  br label %bb.3
+
+bb.3:
+  %ret = phi i32 [ 10, %entry ], [ 20, %bb.2 ]
+  ret i32 %ret
+}
+
+define i32 @phi_removed() {
+; CHECK-LABEL: @phi_removed(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[BB_3:%.*]]
+; CHECK:       bb.3:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br i1 false, label %bb.2, label %bb.3
+
+bb.2:
+  %pv = phi i32 [ 10, %entry ]
+  br label %bb.3
+
+bb.3:
+  ret i32 0
+}
+
+define i32 @phi_in_dead_region() {
+; CHECK-LABEL: @phi_in_dead_region(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+;
+entry:
+  ret i32 1
+
+bb.1:
+  br i1 true, label %bb.2, label %bb.3
+
+bb.2:
+  br label %bb.3
+
+bb.3:
+  %ret = phi i32 [ 10, %bb.1 ], [ 20, %bb.2 ]
+  ret i32 %ret
+}
+
+define i32 @phi_in_mergable_blocks() {
+; CHECK-LABEL: @phi_in_mergable_blocks(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 10
+;
+entry:
+  br label %bb.1
+
+bb.1:
+  %pv = phi i32 [ 10, %entry ]
+  ret i32 %pv
+}

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg4-multiple-duplicate-cfg-updates.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 < %s -S -verify-dom-info | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 < %s -S -verify-dom-info | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 < %s -S -verify-dom-info | FileCheck %s
+
+; Check that we do not crash when we remove edges multiple times in
+; the DomTreeUpdater.
+define void @test() {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i8 undef, label [[IF_THEN_EPIL:%.*]] [
+; CHECK-NEXT:    i8 32, label [[FOR_INC_EPIL:%.*]]
+; CHECK-NEXT:    i8 46, label [[FOR_INC_EPIL]]
+; CHECK-NEXT:    i8 95, label [[FOR_INC_EPIL]]
+; CHECK-NEXT:    i8 45, label [[FOR_INC_EPIL]]
+; CHECK-NEXT:    i8 126, label [[FOR_INC_EPIL]]
+; CHECK-NEXT:    ]
+; CHECK:       if.then.epil:
+; CHECK-NEXT:    unreachable
+; CHECK:       for.inc.epil:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.body.epil
+
+for.body.epil:                                    ; preds = %entry
+  switch i8 undef, label %if.then.epil [
+  i8 32, label %for.inc.epil
+  i8 46, label %for.inc.epil
+  i8 95, label %for.inc.epil
+  i8 45, label %for.inc.epil
+  i8 126, label %for.inc.epil
+  ]
+
+if.then.epil:                                     ; preds = %for.body.epil
+  unreachable
+
+for.inc.epil:                                     ; preds = %for.body.epil, %for.body.epil, %for.body.epil, %for.body.epil, %for.body.epil
+  ret void
+}

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg5-del-phis-for-dead-block.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 < %s -S -verify-dom-info | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 < %s -S -verify-dom-info | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 < %s -S -verify-dom-info | FileCheck %s
+
+define void @test() {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 undef, label [[SW_DEFAULT23:%.*]] [
+; CHECK-NEXT:    i32 129, label [[SW_BB:%.*]]
+; CHECK-NEXT:    i32 215, label [[SW_BB1:%.*]]
+; CHECK-NEXT:    i32 117, label [[SW_BB1]]
+; CHECK-NEXT:    i32 207, label [[SW_BB1]]
+; CHECK-NEXT:    i32 158, label [[SW_BB1]]
+; CHECK-NEXT:    i32 94, label [[SW_BB1]]
+; CHECK-NEXT:    i32 219, label [[SW_BB1]]
+; CHECK-NEXT:    i32 88, label [[SW_BB1]]
+; CHECK-NEXT:    i32 168, label [[SW_BB1]]
+; CHECK-NEXT:    i32 295, label [[SW_BB1]]
+; CHECK-NEXT:    i32 294, label [[SW_BB1]]
+; CHECK-NEXT:    i32 296, label [[SW_BB1]]
+; CHECK-NEXT:    i32 67, label [[SW_BB1]]
+; CHECK-NEXT:    i32 293, label [[SW_BB1]]
+; CHECK-NEXT:    i32 382, label [[SW_BB1]]
+; CHECK-NEXT:    i32 335, label [[SW_BB1]]
+; CHECK-NEXT:    i32 393, label [[SW_BB1]]
+; CHECK-NEXT:    i32 415, label [[SW_BB1]]
+; CHECK-NEXT:    i32 400, label [[SW_BB1]]
+; CHECK-NEXT:    i32 383, label [[SW_BB1]]
+; CHECK-NEXT:    i32 421, label [[SW_BB1]]
+; CHECK-NEXT:    i32 422, label [[SW_BB1]]
+; CHECK-NEXT:    i32 302, label [[SW_BB1]]
+; CHECK-NEXT:    i32 303, label [[SW_BB1]]
+; CHECK-NEXT:    i32 304, label [[SW_BB1]]
+; CHECK-NEXT:    i32 420, label [[SW_BB1]]
+; CHECK-NEXT:    i32 401, label [[SW_EPILOG24:%.*]]
+; CHECK-NEXT:    i32 53, label [[SW_BB12:%.*]]
+; CHECK-NEXT:    i32 44, label [[SW_BB12]]
+; CHECK-NEXT:    ]
+; CHECK:       sw.bb:
+; CHECK-NEXT:    unreachable
+; CHECK:       sw.bb1:
+; CHECK-NEXT:    br label [[SW_EPILOG24]]
+; CHECK:       sw.bb12:
+; CHECK-NEXT:    switch i32 undef, label [[SW_DEFAULT:%.*]] [
+; CHECK-NEXT:    i32 47, label [[SW_BB13:%.*]]
+; CHECK-NEXT:    i32 8, label [[SW_BB13]]
+; CHECK-NEXT:    ]
+; CHECK:       sw.bb13:
+; CHECK-NEXT:    unreachable
+; CHECK:       sw.default:
+; CHECK-NEXT:    unreachable
+; CHECK:       sw.default23:
+; CHECK-NEXT:    unreachable
+; CHECK:       sw.epilog24:
+; CHECK-NEXT:    [[PREVIOUS_3:%.*]] = phi i32 [ undef, [[SW_BB1]] ], [ 401, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    unreachable
+;
+entry:
+  br label %while.body
+
+while.body:                                       ; preds = %entry
+  switch i32 undef, label %sw.default23 [
+  i32 129, label %sw.bb
+  i32 215, label %sw.bb1
+  i32 117, label %sw.bb1
+  i32 207, label %sw.bb1
+  i32 158, label %sw.bb1
+  i32 94, label %sw.bb1
+  i32 219, label %sw.bb1
+  i32 88, label %sw.bb1
+  i32 168, label %sw.bb1
+  i32 295, label %sw.bb1
+  i32 294, label %sw.bb1
+  i32 296, label %sw.bb1
+  i32 67, label %sw.bb1
+  i32 293, label %sw.bb1
+  i32 382, label %sw.bb1
+  i32 335, label %sw.bb1
+  i32 393, label %sw.bb1
+  i32 415, label %sw.bb1
+  i32 400, label %sw.bb1
+  i32 383, label %sw.bb1
+  i32 421, label %sw.bb1
+  i32 422, label %sw.bb1
+  i32 302, label %sw.bb1
+  i32 303, label %sw.bb1
+  i32 304, label %sw.bb1
+  i32 420, label %sw.bb1
+  i32 401, label %sw.epilog24
+  i32 53, label %sw.bb12
+  i32 44, label %sw.bb12
+  ]
+
+sw.bb:                                            ; preds = %while.body
+  unreachable
+
+sw.bb1:                                           ; preds = %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body, %while.body
+  br i1 false, label %land.lhs.true, label %sw.epilog24
+
+land.lhs.true:                                    ; preds = %sw.bb1
+  br label %sw.epilog24
+
+sw.bb12:                                          ; preds = %while.body, %while.body
+  switch i32 undef, label %sw.default [
+  i32 47, label %sw.bb13
+  i32 8, label %sw.bb13
+  ]
+
+sw.bb13:                                          ; preds = %sw.bb12, %sw.bb12
+  unreachable
+
+sw.default:                                       ; preds = %sw.bb12
+  unreachable
+
+sw.default23:                                     ; preds = %while.body
+  unreachable
+
+sw.epilog24:                                      ; preds = %land.lhs.true, %sw.bb1, %while.body
+  %Previous.3 = phi i32 [ undef, %land.lhs.true ], [ undef, %sw.bb1 ], [ 401, %while.body ]
+  unreachable
+}

llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg6-dead-self-loop.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v1 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v2 -S < %s | FileCheck %s
+; RUN: opt -tut-simplifycfg -tut-simplifycfg-version=v3 -S < %s | FileCheck %s
+
+define i32 @simp1() {
+; CHECK-LABEL: @simp1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+; CHECK:       bb.1:
+; CHECK-NEXT:    br label [[BB_1:%.*]]
+; CHECK:       bb.2:
+; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 0, [[BB_2:%.*]] ]
+; CHECK-NEXT:    br label [[BB_2]]
+;
+entry:
+  ret i32 1
+
+bb.1:
+  br label %bb.1
+
+bb.2:
+  %p = phi i32 [ 0, %bb.2]
+  br label %bb.2
+}

llvm/tools/opt/CMakeLists.txt

add_llvm_tool(opt
   intrinsics_gen
   SUPPORT_PLUGINS
   )
 export_executable_symbols(opt)
 
 if(WITH_POLLY AND LINK_POLLY_INTO_TOOLS)
   target_link_libraries(opt PRIVATE Polly)
 endif(WITH_POLLY AND LINK_POLLY_INTO_TOOLS)
+
+if(LLVM_BUILD_EXAMPLES)
+    target_link_libraries(opt PRIVATE ExampleIRTransforms)
+endif(LLVM_BUILD_EXAMPLES)

llvm/tools/opt/opt.cpp

if (!TheTarget) {
     return nullptr;
   }
 
   return TheTarget->createTargetMachine(TheTriple.getTriple(), CPUStr,
                                         FeaturesStr, Options, getRelocModel(),
                                         getCodeModel(), GetCodeGenOptLevel());
 }
 
+#ifdef BUILD_EXAMPLES
+void initializeExampleIRTransforms(llvm::PassRegistry &Registry);
+#endif
+
 #ifdef LINK_POLLY_INTO_TOOLS
 namespace polly {
 void initializePollyPasses(llvm::PassRegistry &Registry);
 }
 #endif
 
 void exportDebugifyStats(llvm::StringRef Path, const DebugifyStatsMap &Map) {
   std::error_code EC;
int main(int argc, char **argv) {
   initializeEntryExitInstrumenterPass(Registry);
   initializePostInlineEntryExitInstrumenterPass(Registry);
   initializeUnreachableBlockElimLegacyPassPass(Registry);
   initializeExpandReductionsPass(Registry);
   initializeWasmEHPreparePass(Registry);
   initializeWriteBitcodePassPass(Registry);
   initializeHardwareLoopsPass(Registry);
 
+#ifdef BUILD_EXAMPLES
+  initializeExampleIRTransforms(Registry);
+#endif
+
 #ifdef LINK_POLLY_INTO_TOOLS
   polly::initializePollyPasses(Registry);
 #endif
 
   cl::ParseCommandLineOptions(argc, argv,
     "llvm .bc -> .bc modular optimizer and analysis printer\n");
 
   if (AnalyzeOnly && NoOutput) {