llvm/llvm/lib/Transforms/Scalar/ADCE.cpp

//===- ADCE.cpp - Code to perform dead code elimination -------------------===//
//
// 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 Aggressive Dead Code Elimination pass.  This pass
// optimistically assumes that all instructions are dead until proven otherwise,
// allowing it to eliminate dead computations that other DCE passes do not
// catch, particularly involving loop computations.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/ADCE.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/IteratedDominanceFrontier.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/Value.h"
#include "llvm/ProfileData/InstrProf.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#include <cstddef>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumRemoved, "Number of instructions removed");
STATISTIC(NumBranchesRemoved, "Number of branch instructions removed");

// This is a temporary option until we change the interface to this pass based
// on optimization level.
static cl::opt<bool> RemoveControlFlowFlag("adce-remove-control-flow",
                                           cl::init(true), cl::Hidden);

// This option enables removing of may-be-infinite loops which have no other
// effect.
static cl::opt<bool> RemoveLoops("adce-remove-loops", cl::init(false),
                                 cl::Hidden);

namespace {

/// Information about Instructions
struct InstInfoType { … };

/// Information about basic blocks relevant to dead code elimination.
struct BlockInfoType { … };

struct ADCEChanged { … };

class AggressiveDeadCodeElimination { … };

} // end anonymous namespace

ADCEChanged AggressiveDeadCodeElimination::performDeadCodeElimination() { … }

static bool isUnconditionalBranch(Instruction *Term) { … }

void AggressiveDeadCodeElimination::initialize() { … }

bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) { … }

// Check if this instruction is a runtime call for value profiling and
// if it's instrumenting a constant.
bool AggressiveDeadCodeElimination::isInstrumentsConstant(Instruction &I) { … }

void AggressiveDeadCodeElimination::markLiveInstructions() { … }

void AggressiveDeadCodeElimination::markLive(Instruction *I) { … }

void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) { … }

void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) { … }

void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) { … }

void AggressiveDeadCodeElimination::markPhiLive(PHINode *PN) { … }

void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() { … }

//===----------------------------------------------------------------------===//
//
//  Routines to update the CFG and SSA information before removing dead code.
//
//===----------------------------------------------------------------------===//
ADCEChanged AggressiveDeadCodeElimination::removeDeadInstructions() { … }

// A dead region is the set of dead blocks with a common live post-dominator.
bool AggressiveDeadCodeElimination::updateDeadRegions() { … }

// reverse top-sort order
void AggressiveDeadCodeElimination::computeReversePostOrder() { … }

void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
                                                      BasicBlock *Target) { … }

//===----------------------------------------------------------------------===//
//
// Pass Manager integration code
//
//===----------------------------------------------------------------------===//
PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) { … }