llvm/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
//  * Preserve LoopInfo.
//  * Add fixed point iteration to delete all dead blocks
//  * Add implementation using reachability to discover dead blocks.
//===----------------------------------------------------------------------===//

#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/Passes/PassBuilder.h"
#include "llvm/Passes/PassPlugin.h"
#include "llvm/Support/CommandLine.h"

usingnamespacellvm;
usingnamespacePatternMatch;

enum TutorialVersion { … };
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 …

// Remove trivially dead blocks. First version, not preserving the
// DominatorTree.
static bool removeDeadBlocks_v1(Function &F) { … }

// Remove trivially dead blocks. This is the second version and preserves the
// dominator tree.
static bool removeDeadBlocks_v2(Function &F, DominatorTree &DT) { … }

// Eliminate branches with constant conditionals. This is the first version,
// which *does not* preserve the dominator tree.
static bool eliminateCondBranches_v1(Function &F) { … }

// Eliminate branches with constant conditionals. This is the second
// version, which *does* preserve the dominator tree.
static bool eliminateCondBranches_v2(Function &F, DominatorTree &DT) { … }

// Eliminate branches with constant conditionals. This is the third
// version, which uses PatternMatch.h.
static bool eliminateCondBranches_v3(Function &F, DominatorTree &DT) { … }

// 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) { … }

// 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) { … }

static bool doSimplify_v1(Function &F) { … }

static bool doSimplify_v2(Function &F, DominatorTree &DT) { … }

static bool doSimplify_v3(Function &F, DominatorTree &DT) { … }

namespace {
struct SimplifyCFGPass : public PassInfoMixin<SimplifyCFGPass> { … };
} // namespace

/* New PM Registration */
llvm::PassPluginLibraryInfo getExampleIRTransformsPluginInfo() { … }

#ifndef LLVM_SIMPLIFYCFG_LINK_INTO_TOOLS
extern "C" LLVM_ATTRIBUTE_WEAK ::llvm::PassPluginLibraryInfo
llvmGetPassPluginInfo() { … }
#endif