LLVM  13.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/SmallPtrSet.h"
20 #include "llvm/ADT/SmallSet.h"
21 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/IR/ValueHandle.h"
26 #include <memory>
27 #include <utility>
28 
29 namespace llvm {
30 
31 class AAResults;
32 class BasicBlock;
33 class BinaryOperator;
34 class BranchInst;
35 class CmpInst;
36 class Constant;
37 class DomTreeUpdater;
38 class Function;
39 class Instruction;
40 class IntrinsicInst;
41 class LazyValueInfo;
42 class LoadInst;
43 class PHINode;
44 class SelectInst;
45 class SwitchInst;
46 class TargetLibraryInfo;
47 class Value;
48 
49 /// A private "module" namespace for types and utilities used by
50 /// JumpThreading.
51 /// These are implementation details and should not be used by clients.
52 namespace jumpthreading {
53 
54 // These are at global scope so static functions can use them too.
57 
58 // This is used to keep track of what kind of constant we're currently hoping
59 // to find.
61 
62 } // end namespace jumpthreading
63 
64 /// This pass performs 'jump threading', which looks at blocks that have
65 /// multiple predecessors and multiple successors. If one or more of the
66 /// predecessors of the block can be proven to always jump to one of the
67 /// successors, we forward the edge from the predecessor to the successor by
68 /// duplicating the contents of this block.
69 ///
70 /// An example of when this can occur is code like this:
71 ///
72 /// if () { ...
73 /// X = 4;
74 /// }
75 /// if (X < 3) {
76 ///
77 /// In this case, the unconditional branch at the end of the first if can be
78 /// revectored to the false side of the second if.
79 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
80  TargetLibraryInfo *TLI;
81  LazyValueInfo *LVI;
82  AAResults *AA;
83  DomTreeUpdater *DTU;
84  std::unique_ptr<BlockFrequencyInfo> BFI;
85  std::unique_ptr<BranchProbabilityInfo> BPI;
86  bool HasProfileData = false;
87  bool HasGuards = false;
88 #ifdef NDEBUG
90 #else
92 #endif
93 
94  unsigned BBDupThreshold;
95  unsigned DefaultBBDupThreshold;
96  bool InsertFreezeWhenUnfoldingSelect;
97 
98 public:
99  JumpThreadingPass(bool InsertFreezeWhenUnfoldingSelect = false, int T = -1);
100 
101  // Glue for old PM.
103  AAResults *AA, DomTreeUpdater *DTU, bool HasProfileData,
104  std::unique_ptr<BlockFrequencyInfo> BFI,
105  std::unique_ptr<BranchProbabilityInfo> BPI);
106 
108 
109  void releaseMemory() {
110  BFI.reset();
111  BPI.reset();
112  }
113 
114  void findLoopHeaders(Function &F);
115  bool processBlock(BasicBlock *BB);
117  void updateSSA(BasicBlock *BB, BasicBlock *NewBB,
118  DenseMap<Instruction *, Value *> &ValueMapping);
121  BasicBlock *NewBB,
122  BasicBlock *PredBB);
124  const SmallVectorImpl<BasicBlock *> &PredBBs,
125  BasicBlock *SuccBB);
127  BasicBlock *SuccBB);
129  BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
130 
134  DenseSet<Value *> &RecursionSet, Instruction *CxtI = nullptr);
135  bool
139  Instruction *CxtI = nullptr) {
140  DenseSet<Value *> RecursionSet;
142  RecursionSet, CxtI);
143  }
144 
146  Value *cond);
148  void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB,
149  BasicBlock *BB, BasicBlock *SuccBB);
152  Instruction *CxtI = nullptr);
153 
154  bool processBranchOnPHI(PHINode *PN);
157 
160  PHINode *SIUse, unsigned Idx);
161 
162  bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
165 
166  bool processGuards(BasicBlock *BB);
167  bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
168 
169 private:
170  BasicBlock *splitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
171  const char *Suffix);
172  void updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
173  BasicBlock *NewBB, BasicBlock *SuccBB);
174  /// Check if the block has profile metadata for its outgoing edges.
175  bool doesBlockHaveProfileData(BasicBlock *BB);
176 };
177 
178 } // end namespace llvm
179 
180 #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:155
llvm
Definition: AllocatorList.h:23
llvm::JumpThreadingPass::unfoldSelectInstr
void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)
Definition: JumpThreading.cpp:2734
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
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:611
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:61
llvm::JumpThreadingPass::processBranchOnXOR
bool processBranchOnXOR(BinaryOperator *BO)
processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
Definition: JumpThreading.cpp:1842
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::jumpthreading::WantBlockAddress
@ WantBlockAddress
Definition: JumpThreading.h:60
DomTreeUpdater.h
llvm::JumpThreadingPass::runImpl
bool runImpl(Function &F, TargetLibraryInfo *TLI, LazyValueInfo *LVI, AAResults *AA, DomTreeUpdater *DTU, bool HasProfileData, std::unique_ptr< BlockFrequencyInfo > BFI, std::unique_ptr< BranchProbabilityInfo > BPI)
Definition: JumpThreading.cpp:380
llvm::jumpthreading::ConstantPreference
ConstantPreference
Definition: JumpThreading.h:60
llvm::JumpThreadingPass::maybethreadThroughTwoBasicBlocks
bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)
Attempt to thread through two successive basic blocks.
Definition: JumpThreading.cpp:2124
llvm::JumpThreadingPass::JumpThreadingPass
JumpThreadingPass(bool InsertFreezeWhenUnfoldingSelect=false, int T=-1)
Definition: JumpThreading.cpp:182
llvm::JumpThreadingPass::evaluateOnPredecessorEdge
Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond)
Definition: JumpThreading.cpp:1588
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
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:449
llvm::JumpThreadingPass::processImpliedCondition
bool processImpliedCondition(BasicBlock *BB)
Definition: JumpThreading.cpp:1257
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:2327
F
#define F(x, y, z)
Definition: MD5.cpp:56
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:2606
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:2366
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:69
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::JumpThreadingPass::releaseMemory
void releaseMemory()
Definition: JumpThreading.h:109
llvm::jumpthreading::WantInteger
@ WantInteger
Definition: JumpThreading.h:60
SI
@ SI
Definition: SIInstrInfo.cpp:7411
DenseSet.h
llvm::Instruction
Definition: Instruction.h:45
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
SmallPtrSet.h
llvm::JumpThreadingPass::tryToUnfoldSelect
bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)
tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2
Definition: JumpThreading.cpp:2808
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:2869
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:712
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:1311
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:136
ArrayRef.h
llvm::JumpThreadingPass
This pass performs 'jump threading', which looks at blocks that have multiple predecessors and multip...
Definition: JumpThreading.h:79
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1715
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
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:2971
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:190
llvm::JumpThreadingPass::maybeMergeBasicBlockIntoOnlyPred
bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB)
Merge basic block BB into its sole predecessor if possible.
Definition: JumpThreading.cpp:1978
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:3005
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
llvm::JumpThreadingPass::threadThroughTwoBasicBlocks
void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)
Definition: JumpThreading.cpp:2261
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:1628
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:207
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
llvm::JumpThreadingPass::updateSSA
void updateSSA(BasicBlock *BB, BasicBlock *NewBB, DenseMap< Instruction *, Value * > &ValueMapping)
Update the SSA form.
Definition: JumpThreading.cpp:2029
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:644
SmallVector.h
llvm::PHINode
Definition: Instructions.h:2572
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
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:3151
llvm::Sched::Preference
Preference
Definition: TargetLowering.h:97
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3007
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:2075
llvm::JumpThreadingPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: JumpThreading.cpp:343
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:1032
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
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:1810
llvm::codeview::PublicSymFlags::Function
@ Function
SmallSet.h