diff --git a/llvm/CMakeLists.txt b/llvm/CMakeLists.txt --- a/llvm/CMakeLists.txt +++ b/llvm/CMakeLists.txt @@ -530,6 +530,10 @@ "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) diff --git a/llvm/examples/CMakeLists.txt b/llvm/examples/CMakeLists.txt --- a/llvm/examples/CMakeLists.txt +++ b/llvm/examples/CMakeLists.txt @@ -2,6 +2,7 @@ add_subdirectory(Fibonacci) add_subdirectory(HowToUseJIT) add_subdirectory(HowToUseLLJIT) +add_subdirectory(IRTransforms) add_subdirectory(LLJITExamples) add_subdirectory(Kaleidoscope) add_subdirectory(ModuleMaker) diff --git a/llvm/examples/IRTransforms/CMakeLists.txt b/llvm/examples/IRTransforms/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/llvm/examples/IRTransforms/CMakeLists.txt @@ -0,0 +1,9 @@ +add_llvm_library(ExampleIRTransforms + InitializePasses.cpp + SimplifyCFG.cpp + + ADDITIONAL_HEADER_DIRS + + DEPENDS + intrinsics_gen + ) diff --git a/llvm/examples/IRTransforms/InitializePasses.h b/llvm/examples/IRTransforms/InitializePasses.h new file mode 100644 --- /dev/null +++ b/llvm/examples/IRTransforms/InitializePasses.h @@ -0,0 +1,22 @@ +//===- 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 diff --git a/llvm/examples/IRTransforms/InitializePasses.cpp b/llvm/examples/IRTransforms/InitializePasses.cpp new file mode 100644 --- /dev/null +++ b/llvm/examples/IRTransforms/InitializePasses.cpp @@ -0,0 +1,21 @@ +//===-- 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); +} diff --git a/llvm/examples/IRTransforms/SimplifyCFG.h b/llvm/examples/IRTransforms/SimplifyCFG.h new file mode 100644 --- /dev/null +++ b/llvm/examples/IRTransforms/SimplifyCFG.h @@ -0,0 +1,24 @@ +//===- 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 diff --git a/llvm/examples/IRTransforms/SimplifyCFG.cpp b/llvm/examples/IRTransforms/SimplifyCFG.cpp new file mode 100644 --- /dev/null +++ b/llvm/examples/IRTransforms/SimplifyCFG.cpp @@ -0,0 +1,413 @@ +//===- 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 + 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 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(BB.getTerminator()); + if (!BI || !BI->isConditional()) + continue; + + // Skip blocks with conditional branches without ConstantInt conditions. + ConstantInt *CI = dyn_cast(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 DTUpdates; + // Eliminate branches with constant conditionals. + for (BasicBlock &BB : F) { + // Skip blocks without conditional branches as terminators. + BranchInst *BI = dyn_cast(BB.getTerminator()); + if (!BI || !BI->isConditional()) + continue; + + // Skip blocks with conditional branches without ConstantInt conditions. + ConstantInt *CI = dyn_cast(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 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 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(); + // Version 1 of the implementation does not preserve the dominator tree. + if (Version != V1) + AU.addPreserved(); + + 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().getDomTree(); + return doSimplify_v2(F, DT); + } + case V3: { + auto &DT = getAnalysis().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) diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg-blockaddress.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg-blockaddress.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg-blockaddress.ll @@ -0,0 +1,23 @@ +; 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 +} diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg1.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg1.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg1.ll @@ -0,0 +1,90 @@ +; 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 + +} diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg2-dead-block-order.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg2-dead-block-order.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg2-dead-block-order.ll @@ -0,0 +1,109 @@ +; 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 +} diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg3-phis.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg3-phis.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg3-phis.ll @@ -0,0 +1,70 @@ +; 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 +} diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg4-multiple-duplicate-cfg-updates.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg4-multiple-duplicate-cfg-updates.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg4-multiple-duplicate-cfg-updates.ll @@ -0,0 +1,40 @@ +; 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 +} diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg5-del-phis-for-dead-block.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg5-del-phis-for-dead-block.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg5-del-phis-for-dead-block.ll @@ -0,0 +1,122 @@ +; 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 +} diff --git a/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg6-dead-self-loop.ll b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg6-dead-self-loop.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Examples/IRTransforms/SimplifyCFG/tut-simplify-cfg6-dead-self-loop.ll @@ -0,0 +1,25 @@ +; 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 +} diff --git a/llvm/tools/opt/CMakeLists.txt b/llvm/tools/opt/CMakeLists.txt --- a/llvm/tools/opt/CMakeLists.txt +++ b/llvm/tools/opt/CMakeLists.txt @@ -42,3 +42,7 @@ 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) diff --git a/llvm/tools/opt/opt.cpp b/llvm/tools/opt/opt.cpp --- a/llvm/tools/opt/opt.cpp +++ b/llvm/tools/opt/opt.cpp @@ -476,6 +476,10 @@ getCodeModel(), GetCodeGenOptLevel()); } +#ifdef BUILD_EXAMPLES +void initializeExampleIRTransforms(llvm::PassRegistry &Registry); +#endif + #ifdef LINK_POLLY_INTO_TOOLS namespace polly { void initializePollyPasses(llvm::PassRegistry &Registry); @@ -557,6 +561,10 @@ initializeWriteBitcodePassPass(Registry); initializeHardwareLoopsPass(Registry); +#ifdef BUILD_EXAMPLES + initializeExampleIRTransforms(Registry); +#endif + #ifdef LINK_POLLY_INTO_TOOLS polly::initializePollyPasses(Registry); #endif