BasicBlockUtils.cpp | Explore in Territory

//===- BasicBlockUtils.cpp - BasicBlock Utilities --------------------------==//
//
// 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 family of functions perform manipulations on basic blocks, and
// instructions contained within basic blocks.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.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 <cstdint>
#include <string>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

static cl::opt<unsigned> MaxDeoptOrUnreachableSuccessorCheckDepth(
    "max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden,
    cl::desc("Set the maximum path length when checking whether a basic block "
             "is followed by a block that either has a terminating "
             "deoptimizing call or is terminated with an unreachable"));

void llvm::detachDeadBlocks(
    ArrayRef<BasicBlock *> BBs,
    SmallVectorImpl<DominatorTree::UpdateType> *Updates,
    bool KeepOneInputPHIs) { … }

void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU,
                           bool KeepOneInputPHIs) { … }

void llvm::DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, DomTreeUpdater *DTU,
                            bool KeepOneInputPHIs) { … }

bool llvm::EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU,
                                      bool KeepOneInputPHIs) { … }

bool llvm::FoldSingleEntryPHINodes(BasicBlock *BB,
                                   MemoryDependenceResults *MemDep) { … }

bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI,
                          MemorySSAUpdater *MSSAU) { … }

bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU,
                                     LoopInfo *LI, MemorySSAUpdater *MSSAU,
                                     MemoryDependenceResults *MemDep,
                                     bool PredecessorWithTwoSuccessors,
                                     DominatorTree *DT) { … }

bool llvm::MergeBlockSuccessorsIntoGivenBlocks(
    SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L, DomTreeUpdater *DTU,
    LoopInfo *LI) { … }

/// Remove redundant instructions within sequences of consecutive dbg.value
/// instructions. This is done using a backward scan to keep the last dbg.value
/// describing a specific variable/fragment.
///
/// BackwardScan strategy:
/// ----------------------
/// Given a sequence of consecutive DbgValueInst like this
///
///   dbg.value ..., "x", FragmentX1  (*)
///   dbg.value ..., "y", FragmentY1
///   dbg.value ..., "x", FragmentX2
///   dbg.value ..., "x", FragmentX1  (**)
///
/// then the instruction marked with (*) can be removed (it is guaranteed to be
/// obsoleted by the instruction marked with (**) as the latter instruction is
/// describing the same variable using the same fragment info).
///
/// Possible improvements:
/// - Check fully overlapping fragments and not only identical fragments.
/// - Support dbg.declare. dbg.label, and possibly other meta instructions being
///   part of the sequence of consecutive instructions.
static bool
DbgVariableRecordsRemoveRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB) { … }

static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB) { … }

/// Remove redundant dbg.value instructions using a forward scan. This can
/// remove a dbg.value instruction that is redundant due to indicating that a
/// variable has the same value as already being indicated by an earlier
/// dbg.value.
///
/// ForwardScan strategy:
/// ---------------------
/// Given two identical dbg.value instructions, separated by a block of
/// instructions that isn't describing the same variable, like this
///
///   dbg.value X1, "x", FragmentX1  (**)
///   <block of instructions, none being "dbg.value ..., "x", ...">
///   dbg.value X1, "x", FragmentX1  (*)
///
/// then the instruction marked with (*) can be removed. Variable "x" is already
/// described as being mapped to the SSA value X1.
///
/// Possible improvements:
/// - Keep track of non-overlapping fragments.
static bool
DbgVariableRecordsRemoveRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) { … }

static bool
DbgVariableRecordsRemoveUndefDbgAssignsFromEntryBlock(BasicBlock *BB) { … }

static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) { … }

/// Remove redundant undef dbg.assign intrinsic from an entry block using a
/// forward scan.
/// Strategy:
/// ---------------------
/// Scanning forward, delete dbg.assign intrinsics iff they are undef, not
/// linked to an intrinsic, and don't share an aggregate variable with a debug
/// intrinsic that didn't meet the criteria. In other words, undef dbg.assigns
/// that come before non-undef debug intrinsics for the variable are
/// deleted. Given:
///
///   dbg.assign undef, "x", FragmentX1 (*)
///   <block of instructions, none being "dbg.value ..., "x", ...">
///   dbg.value %V, "x", FragmentX2
///   <block of instructions, none being "dbg.value ..., "x", ...">
///   dbg.assign undef, "x", FragmentX1
///
/// then (only) the instruction marked with (*) can be removed.
/// Possible improvements:
/// - Keep track of non-overlapping fragments.
static bool removeUndefDbgAssignsFromEntryBlock(BasicBlock *BB) { … }

bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB) { … }

void llvm::ReplaceInstWithValue(BasicBlock::iterator &BI, Value *V) { … }

void llvm::ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI,
                               Instruction *I) { … }

bool llvm::IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB) { … }

void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) { … }

BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT,
                            LoopInfo *LI, MemorySSAUpdater *MSSAU,
                            const Twine &BBName) { … }

void llvm::setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ) { … }

void llvm::updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred,
                          BasicBlock *NewPred, PHINode *Until) { … }

BasicBlock *llvm::ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ,
                                   LandingPadInst *OriginalPad,
                                   PHINode *LandingPadReplacement,
                                   const CriticalEdgeSplittingOptions &Options,
                                   const Twine &BBName) { … }

void llvm::createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,
                                      BasicBlock *SplitBB, BasicBlock *DestBB) { … }

unsigned
llvm::SplitAllCriticalEdges(Function &F,
                            const CriticalEdgeSplittingOptions &Options) { … }

static BasicBlock *SplitBlockImpl(BasicBlock *Old, BasicBlock::iterator SplitPt,
                                  DomTreeUpdater *DTU, DominatorTree *DT,
                                  LoopInfo *LI, MemorySSAUpdater *MSSAU,
                                  const Twine &BBName, bool Before) { … }

BasicBlock *llvm::SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt,
                             DominatorTree *DT, LoopInfo *LI,
                             MemorySSAUpdater *MSSAU, const Twine &BBName,
                             bool Before) { … }
BasicBlock *llvm::SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt,
                             DomTreeUpdater *DTU, LoopInfo *LI,
                             MemorySSAUpdater *MSSAU, const Twine &BBName,
                             bool Before) { … }

BasicBlock *llvm::splitBlockBefore(BasicBlock *Old, BasicBlock::iterator SplitPt,
                                   DomTreeUpdater *DTU, LoopInfo *LI,
                                   MemorySSAUpdater *MSSAU,
                                   const Twine &BBName) { … }

/// Update DominatorTree, LoopInfo, and LCCSA analysis information.
/// Invalidates DFS Numbering when DTU or DT is provided.
static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB,
                                      ArrayRef<BasicBlock *> Preds,
                                      DomTreeUpdater *DTU, DominatorTree *DT,
                                      LoopInfo *LI, MemorySSAUpdater *MSSAU,
                                      bool PreserveLCSSA, bool &HasLoopExit) { … }

/// Update the PHI nodes in OrigBB to include the values coming from NewBB.
/// This also updates AliasAnalysis, if available.
static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
                           ArrayRef<BasicBlock *> Preds, BranchInst *BI,
                           bool HasLoopExit) { … }

static void SplitLandingPadPredecessorsImpl(
    BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,
    const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
    DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,
    MemorySSAUpdater *MSSAU, bool PreserveLCSSA);

static BasicBlock *
SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
                           const char *Suffix, DomTreeUpdater *DTU,
                           DominatorTree *DT, LoopInfo *LI,
                           MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { … }

BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
                                         ArrayRef<BasicBlock *> Preds,
                                         const char *Suffix, DominatorTree *DT,
                                         LoopInfo *LI, MemorySSAUpdater *MSSAU,
                                         bool PreserveLCSSA) { … }
BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
                                         ArrayRef<BasicBlock *> Preds,
                                         const char *Suffix,
                                         DomTreeUpdater *DTU, LoopInfo *LI,
                                         MemorySSAUpdater *MSSAU,
                                         bool PreserveLCSSA) { … }

static void SplitLandingPadPredecessorsImpl(
    BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,
    const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
    DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,
    MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { … }

void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB,
                                       ArrayRef<BasicBlock *> Preds,
                                       const char *Suffix1, const char *Suffix2,
                                       SmallVectorImpl<BasicBlock *> &NewBBs,
                                       DomTreeUpdater *DTU, LoopInfo *LI,
                                       MemorySSAUpdater *MSSAU,
                                       bool PreserveLCSSA) { … }

ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
                                             BasicBlock *Pred,
                                             DomTreeUpdater *DTU) { … }

Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond,
                                             BasicBlock::iterator SplitBefore,
                                             bool Unreachable,
                                             MDNode *BranchWeights,
                                             DomTreeUpdater *DTU, LoopInfo *LI,
                                             BasicBlock *ThenBlock) { … }

Instruction *llvm::SplitBlockAndInsertIfElse(Value *Cond,
                                             BasicBlock::iterator SplitBefore,
                                             bool Unreachable,
                                             MDNode *BranchWeights,
                                             DomTreeUpdater *DTU, LoopInfo *LI,
                                             BasicBlock *ElseBlock) { … }

void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, BasicBlock::iterator SplitBefore,
                                         Instruction **ThenTerm,
                                         Instruction **ElseTerm,
                                         MDNode *BranchWeights,
                                         DomTreeUpdater *DTU, LoopInfo *LI) { … }

void llvm::SplitBlockAndInsertIfThenElse(
    Value *Cond, BasicBlock::iterator SplitBefore, BasicBlock **ThenBlock,
    BasicBlock **ElseBlock, bool UnreachableThen, bool UnreachableElse,
    MDNode *BranchWeights, DomTreeUpdater *DTU, LoopInfo *LI) { … }

std::pair<Instruction*, Value*>
llvm::SplitBlockAndInsertSimpleForLoop(Value *End, Instruction *SplitBefore) { … }

void llvm::SplitBlockAndInsertForEachLane(ElementCount EC,
     Type *IndexTy, Instruction *InsertBefore,
     std::function<void(IRBuilderBase&, Value*)> Func) { … }

void llvm::SplitBlockAndInsertForEachLane(
    Value *EVL, Instruction *InsertBefore,
    std::function<void(IRBuilderBase &, Value *)> Func) { … }

BranchInst *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
                                 BasicBlock *&IfFalse) { … }

void llvm::InvertBranch(BranchInst *PBI, IRBuilderBase &Builder) { … }

bool llvm::hasOnlySimpleTerminator(const Function &F) { … }

bool llvm::isPresplitCoroSuspendExitEdge(const BasicBlock &Src,
                                         const BasicBlock &Dest) { … }
llvm/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
