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

Method Overview

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<std::pair<Value *, BasicBlock *>> & RecursionSet, llvm::Instruction * CxtI = nullptr)
public bool DuplicateCondBranchOnPHIIntoPred(llvm::BasicBlock * BB, const SmallVectorImpl<llvm::BasicBlock *> & PredBBs)
public void FindLoopHeaders(llvm::Function & F)
public JumpThreadingPass(int T = -1)
public bool MaybeMergeBasicBlockIntoOnlyPred(llvm::BasicBlock * BB)
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 bool SimplifyPartiallyRedundantLoad(llvm::LoadInst * LI)
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 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)
public void UpdateSSA(llvm::BasicBlock * BB, llvm::BasicBlock * NewBB, DenseMap<llvm::Instruction *, llvm::Value *> & ValueMapping)
public void releaseMemory()
public llvm::PreservedAnalyses run(llvm::Function & F, llvm::FunctionAnalysisManager & AM)
public bool runImpl(llvm::Function & F, llvm::TargetLibraryInfo * TLI_, llvm::LazyValueInfo * LVI_, llvm::AliasAnalysis * AA_, llvm::DomTreeUpdater * DTU_, bool HasProfileData_, std::unique_ptr<BlockFrequencyInfo> BFI_, std::unique_ptr<BranchProbabilityInfo> BPI_)

Methods

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

Description

Clone instructions in range [BI, BE) to NewBB. For PHI nodes, we only clone arguments that come from PredBB. Return the map from the variables in the source basic block to the variables in the newly created basic block.

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

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:133

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<std::pair<Value*, BasicBlock*>>&
        RecursionSet,
    llvm::Instruction* CxtI = nullptr)

Description

ComputeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the value is a known ConstantInt/BlockAddress or undef in any of our predecessors. If so, return the known list of value and pred BB in the result vector. This returns true if there were any known values.

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

Parameters

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

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

Description

DuplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1 PHI node and a conditional branch on that PHI. If we can duplicate the contents of BB up into PredBB do so now, this improves the odds that the branch will be on an analyzable instruction like a compare.

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

Parameters

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

¶void FindLoopHeaders(llvm::Function& F)

Description

FindLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops. Doing this breaks up the loop nesting hierarchy and pessimizes later transformations. To prevent this from happening, we first have to find the loop headers. Here we approximate this by finding targets of backedges in the CFG. Note that there definitely are cases when we want to allow threading of edges across a loop header. For example, threading a jump from outside the loop (the preheader) to an exit block of the loop is definitely profitable. It is also almost always profitable to thread backedges from within the loop to exit blocks, and is often profitable to thread backedges to other blocks within the loop (forming a nested loop). This simple analysis is not rich enough to track all of these properties and keep it up-to-date as the CFG mutates, so we don't allow any of these transformations.

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

Parameters

llvm::Function& F

¶JumpThreadingPass(int T = -1)

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

Parameters

int T = -1

¶bool MaybeMergeBasicBlockIntoOnlyPred(
    llvm::BasicBlock* BB)

Description

Merge basic block BB into its sole predecessor if possible.

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

Parameters

llvm::BasicBlock* BB

¶bool ProcessBlock(llvm::BasicBlock* BB)

Description

ProcessBlock - If there are any predecessors whose control can be threaded through to a successor, transform them now.

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

Parameters

llvm::BasicBlock* BB

¶bool ProcessBranchOnPHI(llvm::PHINode* PN)

Description

ProcessBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node in the current block. See if there are any simplifications we can do based on inputs to the phi node.

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

Parameters

llvm::PHINode* PN

¶bool ProcessBranchOnXOR(llvm::BinaryOperator* BO)

Description

ProcessBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the current block. See if there are any simplifications we can do based on inputs to the xor.

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

Parameters

llvm::BinaryOperator* BO

¶bool ProcessGuards(llvm::BasicBlock* BB)

Description

Try to propagate a guard from the current BB into one of its predecessors in case if another branch of execution implies that the condition of this guard is always true. Currently we only process the simplest case that looks like: Start: %cond = ... br i1 %cond, label %T1, label %F1 T1: br label %Merge F1: br label %Merge Merge: %condGuard = ... call void(i1, ...) @llvm.experimental.guard( i1 %condGuard )[ "deopt"() ] And cond either implies condGuard or !condGuard. In this case all the instructions before the guard can be duplicated in both branches, and the guard is then threaded to one of them.

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

Parameters

llvm::BasicBlock* BB

¶bool ProcessImpliedCondition(llvm::BasicBlock* BB)

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

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:142

Parameters

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

¶bool SimplifyPartiallyRedundantLoad(
    llvm::LoadInst* LI)

Description

SimplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction, eliminate it by replacing it with a PHI node. This is an important optimization that encourages jump threading, and needs to be run interlaced with other jump threading tasks.

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

Parameters

llvm::LoadInst* LI

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

Description

ThreadEdge - We have decided that it is safe and profitable to factor the blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB across BB. Transform the IR to reflect this change.

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

Parameters

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

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

Description

Try to propagate the guard from BB which is the lower block of a diamond to one of its branches, in case if diamond's condition implies guard's condition.

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

Parameters

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

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

Description

TryThreadEdge - Thread an edge if it's safe and profitable to do so.

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

Parameters

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

¶bool TryToUnfoldSelect(llvm::CmpInst* CondCmp,
                       llvm::BasicBlock* BB)

Description

TryToUnfoldSelect - Look for blocks of the form bb1: %a = select br bb2 bb2: %p = phi [%a, %bb1] ... %c = icmp %p br i1 %c And expand the select into a branch structure if one of its arms allows %c to be folded. This later enables threading from bb1 over bb2.

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

Parameters

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

¶bool TryToUnfoldSelect(llvm::SwitchInst* SI,
                       llvm::BasicBlock* BB)

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

Parameters

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

¶bool TryToUnfoldSelectInCurrBB(
    llvm::BasicBlock* BB)

Description

TryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: %p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ... %s = select %p, trueval, falseval or bb: %p = phi [0, %bb1], [1, %bb2], [0, %bb3], [1, %bb4], ... %c = cmp %p, 0 %s = select %c, trueval, falseval And expand the select into a branch structure. This later enables jump-threading over bb in this pass. Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold select if the associated PHI has at least one constant. If the unfolded select is not jump-threaded, it will be folded again in the later optimizations.

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

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:151

Parameters

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

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

Description

Update the SSA form. NewBB contains instructions that are copied from BB. ValueMapping maps old values in BB to new ones in NewBB.

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

Parameters

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

¶void releaseMemory()

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

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

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

Parameters

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

¶bool runImpl(
    llvm::Function& F,
    llvm::TargetLibraryInfo* TLI_,
    llvm::LazyValueInfo* LVI_,
    llvm::AliasAnalysis* 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:98

Parameters

llvm::Function& F
llvm::TargetLibraryInfo* TLI_
llvm::LazyValueInfo* LVI_
llvm::AliasAnalysis* AA_
llvm::DomTreeUpdater* DTU_
bool HasProfileData_
std::unique_ptr<BlockFrequencyInfo> BFI_
std::unique_ptr<BranchProbabilityInfo> BPI_

class JumpThreadingPass

Declaration

Description

Method Overview

Methods

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

Description

Parameters

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

Parameters

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

Description

Parameters

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

Description

Parameters

¶void FindLoopHeaders(llvm::Function& F)

Description

Parameters

¶JumpThreadingPass(int T = -1)

Parameters

¶bool MaybeMergeBasicBlockIntoOnlyPred( llvm::BasicBlock* BB)

Description

Parameters

¶bool ProcessBlock(llvm::BasicBlock* BB)

Description

Parameters

¶bool ProcessBranchOnPHI(llvm::PHINode* PN)

Description

Parameters

¶bool ProcessBranchOnXOR(llvm::BinaryOperator* BO)

Description

Parameters

¶bool ProcessGuards(llvm::BasicBlock* BB)

Description

Parameters

¶bool ProcessImpliedCondition(llvm::BasicBlock* BB)

Parameters

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

Parameters

¶bool SimplifyPartiallyRedundantLoad( llvm::LoadInst* LI)

Description

Parameters

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

Description

Parameters

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

Description

Parameters

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

Description

Parameters

¶bool TryToUnfoldSelect(llvm::CmpInst* CondCmp, llvm::BasicBlock* BB)

Description

Parameters

¶bool TryToUnfoldSelect(llvm::SwitchInst* SI, llvm::BasicBlock* BB)

Parameters

¶bool TryToUnfoldSelectInCurrBB( llvm::BasicBlock* BB)

Description

Parameters

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

Parameters

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

Description

Parameters

¶void releaseMemory()

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

Parameters

¶bool runImpl( llvm::Function& F, llvm::TargetLibraryInfo* TLI_, llvm::LazyValueInfo* LVI_, llvm::AliasAnalysis* AA_, llvm::DomTreeUpdater* DTU_, bool HasProfileData_, std::unique_ptr<BlockFrequencyInfo> BFI_, std::unique_ptr<BranchProbabilityInfo> BPI_)

Parameters

¶`DenseMap<llvm::Instruction, llvm::Value> CloneInstructions(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)`

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

¶`bool DuplicateCondBranchOnPHIIntoPred( llvm::BasicBlock* BB, const SmallVectorImpl<llvm::BasicBlock*>& PredBBs)`

¶`void FindLoopHeaders(llvm::Function& F)`

¶`JumpThreadingPass(int T = -1)`

¶`bool MaybeMergeBasicBlockIntoOnlyPred( llvm::BasicBlock* BB)`

¶`bool ProcessBlock(llvm::BasicBlock* BB)`

¶`bool ProcessBranchOnPHI(llvm::PHINode* PN)`

¶`bool ProcessBranchOnXOR(llvm::BinaryOperator* BO)`

¶`bool ProcessGuards(llvm::BasicBlock* BB)`

¶`bool ProcessImpliedCondition(llvm::BasicBlock* BB)`

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

¶`bool SimplifyPartiallyRedundantLoad( llvm::LoadInst* LI)`

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

¶`bool ThreadGuard(llvm::BasicBlock* BB, llvm::IntrinsicInst* Guard, llvm::BranchInst* BI)`

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

¶`bool TryToUnfoldSelect(llvm::CmpInst* CondCmp, llvm::BasicBlock* BB)`

¶`bool TryToUnfoldSelect(llvm::SwitchInst* SI, llvm::BasicBlock* BB)`

¶`bool TryToUnfoldSelectInCurrBB( llvm::BasicBlock* BB)`

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

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

¶`void releaseMemory()`

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

¶`bool runImpl( llvm::Function& F, llvm::TargetLibraryInfo* TLI_, llvm::LazyValueInfo* LVI_, llvm::AliasAnalysis* AA_, llvm::DomTreeUpdater* DTU_, bool HasProfileData_, std::unique_ptr<BlockFrequencyInfo> BFI_, std::unique_ptr<BranchProbabilityInfo> BPI_)`