class JumpThreadingPass

Declaration

class JumpThreadingPass : public PassInfoMixin { /* full declaration omitted */ };

Description

This pass performs 'jump threading', which looks at blocks that have multiple predecessors and multiple successors. If one or more of the predecessors of the block can be proven to always jump to one of the successors, we forward the edge from the predecessor to the successor by duplicating the contents of this block. An example of when this can occur is code like this: if () { ... X = 4; } if (X < 3) { In this case, the unconditional branch at the end of the first if can be revectored to the false side of the second if.

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:77

Inherits from: PassInfoMixin

Member Variables

private llvm::TargetLibraryInfo* TLI
private llvm::TargetTransformInfo* TTI
private llvm::LazyValueInfo* LVI
private llvm::AAResults* AA
private llvm::DomTreeUpdater* DTU
private std::unique_ptr<BlockFrequencyInfo> BFI
private std::unique_ptr<BranchProbabilityInfo> BPI
private bool HasProfileData = false
private bool HasGuards = false
private SmallSet<AssertingVH<const llvm::BasicBlock>, 16> LoopHeaders
private unsigned int BBDupThreshold
private unsigned int DefaultBBDupThreshold

Method Overview

  • public JumpThreadingPass(int T = -1)
  • public DenseMap<llvm::Instruction *, llvm::Value *> cloneInstructions(BasicBlock::iterator BI, BasicBlock::iterator BE, llvm::BasicBlock * NewBB, llvm::BasicBlock * PredBB)
  • public bool computeValueKnownInPredecessors(llvm::Value * V, llvm::BasicBlock * BB, jumpthreading::PredValueInfo & Result, jumpthreading::ConstantPreference Preference, llvm::Instruction * CxtI = nullptr)
  • public bool computeValueKnownInPredecessorsImpl(llvm::Value * V, llvm::BasicBlock * BB, jumpthreading::PredValueInfo & Result, jumpthreading::ConstantPreference Preference, DenseSet<llvm::Value *> & RecursionSet, llvm::Instruction * CxtI = nullptr)
  • private bool doesBlockHaveProfileData(llvm::BasicBlock * BB)
  • public bool duplicateCondBranchOnPHIIntoPred(llvm::BasicBlock * BB, const SmallVectorImpl<llvm::BasicBlock *> & PredBBs)
  • public llvm::Constant * evaluateOnPredecessorEdge(llvm::BasicBlock * BB, llvm::BasicBlock * PredPredBB, llvm::Value * cond)
  • public void findLoopHeaders(llvm::Function & F)
  • public bool maybeMergeBasicBlockIntoOnlyPred(llvm::BasicBlock * BB)
  • public bool maybethreadThroughTwoBasicBlocks(llvm::BasicBlock * BB, llvm::Value * Cond)
  • public bool processBlock(llvm::BasicBlock * BB)
  • public bool processBranchOnPHI(llvm::PHINode * PN)
  • public bool processBranchOnXOR(llvm::BinaryOperator * BO)
  • public bool processGuards(llvm::BasicBlock * BB)
  • public bool processImpliedCondition(llvm::BasicBlock * BB)
  • public bool processThreadableEdges(llvm::Value * Cond, llvm::BasicBlock * BB, jumpthreading::ConstantPreference Preference, llvm::Instruction * CxtI = nullptr)
  • public void releaseMemory()
  • public llvm::PreservedAnalyses run(llvm::Function & F, llvm::FunctionAnalysisManager & AM)
  • public bool runImpl(llvm::Function & F, llvm::TargetLibraryInfo * TLI, llvm::TargetTransformInfo * TTI, llvm::LazyValueInfo * LVI, llvm::AAResults * AA, llvm::DomTreeUpdater * DTU, bool HasProfileData, std::unique_ptr<BlockFrequencyInfo> BFI, std::unique_ptr<BranchProbabilityInfo> BPI)
  • public bool simplifyPartiallyRedundantLoad(llvm::LoadInst * LI)
  • private llvm::BasicBlock * splitBlockPreds(llvm::BasicBlock * BB, ArrayRef<llvm::BasicBlock *> Preds, const char * Suffix)
  • public void threadEdge(llvm::BasicBlock * BB, const SmallVectorImpl<llvm::BasicBlock *> & PredBBs, llvm::BasicBlock * SuccBB)
  • public bool threadGuard(llvm::BasicBlock * BB, llvm::IntrinsicInst * Guard, llvm::BranchInst * BI)
  • public void threadThroughTwoBasicBlocks(llvm::BasicBlock * PredPredBB, llvm::BasicBlock * PredBB, llvm::BasicBlock * BB, llvm::BasicBlock * SuccBB)
  • public bool tryThreadEdge(llvm::BasicBlock * BB, const SmallVectorImpl<llvm::BasicBlock *> & PredBBs, llvm::BasicBlock * SuccBB)
  • public bool tryToUnfoldSelect(llvm::CmpInst * CondCmp, llvm::BasicBlock * BB)
  • public bool tryToUnfoldSelect(llvm::SwitchInst * SI, llvm::BasicBlock * BB)
  • public bool tryToUnfoldSelectInCurrBB(llvm::BasicBlock * BB)
  • public void unfoldSelectInstr(llvm::BasicBlock * Pred, llvm::BasicBlock * BB, llvm::SelectInst * SI, llvm::PHINode * SIUse, unsigned int Idx)
  • private void updateBlockFreqAndEdgeWeight(llvm::BasicBlock * PredBB, llvm::BasicBlock * BB, llvm::BasicBlock * NewBB, llvm::BasicBlock * SuccBB)
  • public void updateSSA(llvm::BasicBlock * BB, llvm::BasicBlock * NewBB, DenseMap<llvm::Instruction *, llvm::Value *> & ValueMapping)

Methods

JumpThreadingPass(int T = -1)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:97

Parameters

int T = -1

DenseMap<llvm::Instruction*, llvm::Value*>
cloneInstructions(BasicBlock::iterator BI,
                  BasicBlock::iterator BE,
                  llvm::BasicBlock* NewBB,
                  llvm::BasicBlock* PredBB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:117

Parameters

BasicBlock::iterator BI
BasicBlock::iterator BE
llvm::BasicBlock* NewBB
llvm::BasicBlock* PredBB

bool computeValueKnownInPredecessors(
    llvm::Value* V,
    llvm::BasicBlock* BB,
    jumpthreading::PredValueInfo& Result,
    jumpthreading::ConstantPreference Preference,
    llvm::Instruction* CxtI = nullptr)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:134

Parameters

llvm::Value* V
llvm::BasicBlock* BB
jumpthreading::PredValueInfo& Result
jumpthreading::ConstantPreference Preference
llvm::Instruction* CxtI = nullptr

bool computeValueKnownInPredecessorsImpl(
    llvm::Value* V,
    llvm::BasicBlock* BB,
    jumpthreading::PredValueInfo& Result,
    jumpthreading::ConstantPreference Preference,
    DenseSet<llvm::Value*>& RecursionSet,
    llvm::Instruction* CxtI = nullptr)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:129

Parameters

llvm::Value* V
llvm::BasicBlock* BB
jumpthreading::PredValueInfo& Result
jumpthreading::ConstantPreference Preference
DenseSet<llvm::Value*>& RecursionSet
llvm::Instruction* CxtI = nullptr

bool doesBlockHaveProfileData(
    llvm::BasicBlock* BB)

Description

Check if the block has profile metadata for its outgoing edges.

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:173

Parameters

llvm::BasicBlock* BB

bool duplicateCondBranchOnPHIIntoPred(
    llvm::BasicBlock* BB,
    const SmallVectorImpl<llvm::BasicBlock*>&
        PredBBs)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:126

Parameters

llvm::BasicBlock* BB
const SmallVectorImpl<llvm::BasicBlock*>& PredBBs

llvm::Constant* evaluateOnPredecessorEdge(
    llvm::BasicBlock* BB,
    llvm::BasicBlock* PredPredBB,
    llvm::Value* cond)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:143

Parameters

llvm::BasicBlock* BB
llvm::BasicBlock* PredPredBB
llvm::Value* cond

void findLoopHeaders(llvm::Function& F)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:112

Parameters

llvm::Function& F

bool maybeMergeBasicBlockIntoOnlyPred(
    llvm::BasicBlock* BB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:114

Parameters

llvm::BasicBlock* BB

bool maybethreadThroughTwoBasicBlocks(
    llvm::BasicBlock* BB,
    llvm::Value* Cond)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:145

Parameters

llvm::BasicBlock* BB
llvm::Value* Cond

bool processBlock(llvm::BasicBlock* BB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:113

Parameters

llvm::BasicBlock* BB

bool processBranchOnPHI(llvm::PHINode* PN)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:152

Parameters

llvm::PHINode* PN

bool processBranchOnXOR(llvm::BinaryOperator* BO)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:153

Parameters

llvm::BinaryOperator* BO

bool processGuards(llvm::BasicBlock* BB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:164

Parameters

llvm::BasicBlock* BB

bool processImpliedCondition(llvm::BasicBlock* BB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:154

Parameters

llvm::BasicBlock* BB

bool processThreadableEdges(
    llvm::Value* Cond,
    llvm::BasicBlock* BB,
    jumpthreading::ConstantPreference Preference,
    llvm::Instruction* CxtI = nullptr)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:148

Parameters

llvm::Value* Cond
llvm::BasicBlock* BB
jumpthreading::ConstantPreference Preference
llvm::Instruction* CxtI = nullptr

void releaseMemory()

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:107

llvm::PreservedAnalyses run(
    llvm::Function& F,
    llvm::FunctionAnalysisManager& AM)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:105

Parameters

llvm::Function& F
llvm::FunctionAnalysisManager& AM

bool runImpl(
    llvm::Function& F,
    llvm::TargetLibraryInfo* TLI,
    llvm::TargetTransformInfo* TTI,
    llvm::LazyValueInfo* LVI,
    llvm::AAResults* AA,
    llvm::DomTreeUpdater* DTU,
    bool HasProfileData,
    std::unique_ptr<BlockFrequencyInfo> BFI,
    std::unique_ptr<BranchProbabilityInfo> BPI)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:100

Parameters

llvm::Function& F
llvm::TargetLibraryInfo* TLI
llvm::TargetTransformInfo* TTI
llvm::LazyValueInfo* LVI
llvm::AAResults* AA
llvm::DomTreeUpdater* DTU
bool HasProfileData
std::unique_ptr<BlockFrequencyInfo> BFI
std::unique_ptr<BranchProbabilityInfo> BPI

bool simplifyPartiallyRedundantLoad(
    llvm::LoadInst* LI)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:156

Parameters

llvm::LoadInst* LI

llvm::BasicBlock* splitBlockPreds(
    llvm::BasicBlock* BB,
    ArrayRef<llvm::BasicBlock*> Preds,
    const char* Suffix)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:168

Parameters

llvm::BasicBlock* BB
ArrayRef<llvm::BasicBlock*> Preds
const char* Suffix

void threadEdge(
    llvm::BasicBlock* BB,
    const SmallVectorImpl<llvm::BasicBlock*>&
        PredBBs,
    llvm::BasicBlock* SuccBB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:124

Parameters

llvm::BasicBlock* BB
const SmallVectorImpl<llvm::BasicBlock*>& PredBBs
llvm::BasicBlock* SuccBB

bool threadGuard(llvm::BasicBlock* BB,
                 llvm::IntrinsicInst* Guard,
                 llvm::BranchInst* BI)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:165

Parameters

llvm::BasicBlock* BB
llvm::IntrinsicInst* Guard
llvm::BranchInst* BI

void threadThroughTwoBasicBlocks(
    llvm::BasicBlock* PredPredBB,
    llvm::BasicBlock* PredBB,
    llvm::BasicBlock* BB,
    llvm::BasicBlock* SuccBB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:146

Parameters

llvm::BasicBlock* PredPredBB
llvm::BasicBlock* PredBB
llvm::BasicBlock* BB
llvm::BasicBlock* SuccBB

bool tryThreadEdge(
    llvm::BasicBlock* BB,
    const SmallVectorImpl<llvm::BasicBlock*>&
        PredBBs,
    llvm::BasicBlock* SuccBB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:121

Parameters

llvm::BasicBlock* BB
const SmallVectorImpl<llvm::BasicBlock*>& PredBBs
llvm::BasicBlock* SuccBB

bool tryToUnfoldSelect(llvm::CmpInst* CondCmp,
                       llvm::BasicBlock* BB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:160

Parameters

llvm::CmpInst* CondCmp
llvm::BasicBlock* BB

bool tryToUnfoldSelect(llvm::SwitchInst* SI,
                       llvm::BasicBlock* BB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:161

Parameters

llvm::SwitchInst* SI
llvm::BasicBlock* BB

bool tryToUnfoldSelectInCurrBB(
    llvm::BasicBlock* BB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:162

Parameters

llvm::BasicBlock* BB

void unfoldSelectInstr(llvm::BasicBlock* Pred,
                       llvm::BasicBlock* BB,
                       llvm::SelectInst* SI,
                       llvm::PHINode* SIUse,
                       unsigned int Idx)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:157

Parameters

llvm::BasicBlock* Pred
llvm::BasicBlock* BB
llvm::SelectInst* SI
llvm::PHINode* SIUse
unsigned int Idx

void updateBlockFreqAndEdgeWeight(
    llvm::BasicBlock* PredBB,
    llvm::BasicBlock* BB,
    llvm::BasicBlock* NewBB,
    llvm::BasicBlock* SuccBB)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:170

Parameters

llvm::BasicBlock* PredBB
llvm::BasicBlock* BB
llvm::BasicBlock* NewBB
llvm::BasicBlock* SuccBB

void updateSSA(
    llvm::BasicBlock* BB,
    llvm::BasicBlock* NewBB,
    DenseMap<llvm::Instruction*, llvm::Value*>&
        ValueMapping)

Declared at: llvm/include/llvm/Transforms/Scalar/JumpThreading.h:115

Parameters

llvm::BasicBlock* BB
llvm::BasicBlock* NewBB
DenseMap<llvm::Instruction*, llvm::Value*>& ValueMapping