LLVM  16.0.0git
JumpThreading.h
Go to the documentation of this file.
1 //===- JumpThreading.h - thread control through conditional BBs -*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
10 /// See the comments on JumpThreadingPass.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
15 #define LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
16 
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/IR/ValueHandle.h"
24 #include <utility>
25 
26 namespace llvm {
27 
28 class AAResults;
29 class BasicBlock;
30 class BinaryOperator;
31 class BranchInst;
32 class CmpInst;
33 class Constant;
34 class DomTreeUpdater;
35 class Function;
36 class Instruction;
37 class IntrinsicInst;
38 class LazyValueInfo;
39 class LoadInst;
40 class PHINode;
41 class SelectInst;
42 class SwitchInst;
43 class TargetLibraryInfo;
44 class TargetTransformInfo;
45 class Value;
46 
47 /// A private "module" namespace for types and utilities used by
48 /// JumpThreading.
49 /// These are implementation details and should not be used by clients.
50 namespace jumpthreading {
51 
52 // These are at global scope so static functions can use them too.
55 
56 // This is used to keep track of what kind of constant we're currently hoping
57 // to find.
59 
60 } // end namespace jumpthreading
61 
62 /// This pass performs 'jump threading', which looks at blocks that have
63 /// multiple predecessors and multiple successors. If one or more of the
64 /// predecessors of the block can be proven to always jump to one of the
65 /// successors, we forward the edge from the predecessor to the successor by
66 /// duplicating the contents of this block.
67 ///
68 /// An example of when this can occur is code like this:
69 ///
70 /// if () { ...
71 /// X = 4;
72 /// }
73 /// if (X < 3) {
74 ///
75 /// In this case, the unconditional branch at the end of the first if can be
76 /// revectored to the false side of the second if.
77 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
78  TargetLibraryInfo *TLI;
80  LazyValueInfo *LVI;
81  AAResults *AA;
82  DomTreeUpdater *DTU;
83  std::unique_ptr<BlockFrequencyInfo> BFI;
84  std::unique_ptr<BranchProbabilityInfo> BPI;
85  bool HasProfileData = false;
86  bool HasGuards = false;
87 #ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS
89 #else
91 #endif
92 
93  unsigned BBDupThreshold;
94  unsigned DefaultBBDupThreshold;
95 
96 public:
97  JumpThreadingPass(int T = -1);
98 
99  // Glue for old PM.
101  LazyValueInfo *LVI, AAResults *AA, DomTreeUpdater *DTU,
102  bool HasProfileData, std::unique_ptr<BlockFrequencyInfo> BFI,
103  std::unique_ptr<BranchProbabilityInfo> BPI);
104 
106 
107  void releaseMemory() {
108  BFI.reset();
109  BPI.reset();
110  }
111 
112  void findLoopHeaders(Function &F);
113  bool processBlock(BasicBlock *BB);
115  void updateSSA(BasicBlock *BB, BasicBlock *NewBB,
116  DenseMap<Instruction *, Value *> &ValueMapping);
119  BasicBlock *NewBB,
120  BasicBlock *PredBB);
122  const SmallVectorImpl<BasicBlock *> &PredBBs,
123  BasicBlock *SuccBB);
125  BasicBlock *SuccBB);
127  BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
128 
132  DenseSet<Value *> &RecursionSet, Instruction *CxtI = nullptr);
133  bool
137  Instruction *CxtI = nullptr) {
138  DenseSet<Value *> RecursionSet;
140  RecursionSet, CxtI);
141  }
142 
144  Value *cond);
146  void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB,
147  BasicBlock *BB, BasicBlock *SuccBB);
150  Instruction *CxtI = nullptr);
151 
152  bool processBranchOnPHI(PHINode *PN);
155 
158  PHINode *SIUse, unsigned Idx);
159 
160  bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
163 
164  bool processGuards(BasicBlock *BB);
165  bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
166 
167 private:
168  BasicBlock *splitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
169  const char *Suffix);
170  void updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
171  BasicBlock *NewBB, BasicBlock *SuccBB);
172  /// Check if the block has profile metadata for its outgoing edges.
173  bool doesBlockHaveProfileData(BasicBlock *BB);
174 };
175 
176 } // end namespace llvm
177 
178 #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::JumpThreadingPass::unfoldSelectInstr
void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)
Definition: JumpThreading.cpp:2741
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::JumpThreadingPass::findLoopHeaders
void findLoopHeaders(Function &F)
findLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops...
Definition: JumpThreading.cpp:620
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
llvm::JumpThreadingPass::processBranchOnXOR
bool processBranchOnXOR(BinaryOperator *BO)
processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
Definition: JumpThreading.cpp:1847
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::jumpthreading::WantBlockAddress
@ WantBlockAddress
Definition: JumpThreading.h:58
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:173
llvm::jumpthreading::ConstantPreference
ConstantPreference
Definition: JumpThreading.h:58
llvm::JumpThreadingPass::maybethreadThroughTwoBasicBlocks
bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)
Attempt to thread through two successive basic blocks.
Definition: JumpThreading.cpp:2128
llvm::JumpThreadingPass::evaluateOnPredecessorEdge
Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond)
Definition: JumpThreading.cpp:1595
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::JumpThreadingPass::processImpliedCondition
bool processImpliedCondition(BasicBlock *BB)
Definition: JumpThreading.cpp:1246
llvm::JumpThreadingPass::tryThreadEdge
bool tryThreadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
tryThreadEdge - Thread an edge if it's safe and profitable to do so.
Definition: JumpThreading.cpp:2334
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::JumpThreadingPass::duplicateCondBranchOnPHIIntoPred
bool duplicateCondBranchOnPHIIntoPred(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs)
duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1...
Definition: JumpThreading.cpp:2613
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::JumpThreadingPass::threadEdge
void threadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
threadEdge - We have decided that it is safe and profitable to factor the blocks in PredBBs to one pr...
Definition: JumpThreading.cpp:2373
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:76
llvm::AAResults
Definition: AliasAnalysis.h:294
llvm::JumpThreadingPass::releaseMemory
void releaseMemory()
Definition: JumpThreading.h:107
llvm::jumpthreading::WantInteger
@ WantInteger
Definition: JumpThreading.h:58
SI
@ SI
Definition: SIInstrInfo.cpp:7985
DenseSet.h
llvm::Instruction
Definition: Instruction.h:42
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::JumpThreadingPass::tryToUnfoldSelect
bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)
tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2
Definition: JumpThreading.cpp:2815
llvm::JumpThreadingPass::tryToUnfoldSelectInCurrBB
bool tryToUnfoldSelectInCurrBB(BasicBlock *BB)
tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = ...
Definition: JumpThreading.cpp:2876
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
llvm::DenseSet< Value * >
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
BranchProbabilityInfo.h
llvm::JumpThreadingPass::simplifyPartiallyRedundantLoad
bool simplifyPartiallyRedundantLoad(LoadInst *LI)
simplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction,...
Definition: JumpThreading.cpp:1323
llvm::DenseMap
Definition: DenseMap.h:714
llvm::JumpThreadingPass::computeValueKnownInPredecessors
bool computeValueKnownInPredecessors(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
Definition: JumpThreading.h:134
ArrayRef.h
llvm::JumpThreadingPass
This pass performs 'jump threading', which looks at blocks that have multiple predecessors and multip...
Definition: JumpThreading.h:77
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1735
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::LazyValueInfo
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:31
llvm::JumpThreadingPass::processGuards
bool processGuards(BasicBlock *BB)
Try to propagate a guard from the current BB into one of its predecessors in case if another branch o...
Definition: JumpThreading.cpp:2976
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::BinaryOperator
Definition: InstrTypes.h:188
llvm::JumpThreadingPass::maybeMergeBasicBlockIntoOnlyPred
bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB)
Merge basic block BB into its sole predecessor if possible.
Definition: JumpThreading.cpp:1982
llvm::JumpThreadingPass::threadGuard
bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI)
Try to propagate the guard from BB which is the lower block of a diamond to one of its branches,...
Definition: JumpThreading.cpp:3010
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::JumpThreadingPass::threadThroughTwoBasicBlocks
void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)
Definition: JumpThreading.cpp:2268
BlockFrequencyInfo.h
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
ValueHandle.h
llvm::JumpThreadingPass::processThreadableEdges
bool processThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
Definition: JumpThreading.cpp:1635
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:225
llvm::JumpThreadingPass::runImpl
bool runImpl(Function &F, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, LazyValueInfo *LVI, AAResults *AA, DomTreeUpdater *DTU, bool HasProfileData, std::unique_ptr< BlockFrequencyInfo > BFI, std::unique_ptr< BranchProbabilityInfo > BPI)
Definition: JumpThreading.cpp:376
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
llvm::JumpThreadingPass::updateSSA
void updateSSA(BasicBlock *BB, BasicBlock *NewBB, DenseMap< Instruction *, Value * > &ValueMapping)
Update the SSA form.
Definition: JumpThreading.cpp:2033
llvm::JumpThreadingPass::computeValueKnownInPredecessorsImpl
bool computeValueKnownInPredecessorsImpl(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, DenseSet< Value * > &RecursionSet, Instruction *CxtI=nullptr)
computeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the ...
Definition: JumpThreading.cpp:653
SmallVector.h
llvm::PHINode
Definition: Instructions.h:2697
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3276
llvm::Sched::Preference
Preference
Definition: TargetLowering.h:97
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3132
llvm::JumpThreadingPass::cloneInstructions
DenseMap< Instruction *, Value * > cloneInstructions(BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock *NewBB, BasicBlock *PredBB)
Clone instructions in range [BI, BE) to NewBB.
Definition: JumpThreading.cpp:2079
llvm::JumpThreadingPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: JumpThreading.cpp:340
llvm::JumpThreadingPass::processBlock
bool processBlock(BasicBlock *BB)
processBlock - If there are any predecessors whose control can be threaded through to a successor,...
Definition: JumpThreading.cpp:1047
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::JumpThreadingPass::processBranchOnPHI
bool processBranchOnPHI(PHINode *PN)
processBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node (or freeze PH...
Definition: JumpThreading.cpp:1815
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::JumpThreadingPass::JumpThreadingPass
JumpThreadingPass(int T=-1)
Definition: JumpThreading.cpp:180
SmallSet.h