LLVM 24.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"
24#include "llvm/IR/ValueHandle.h"
27#include <utility>
28
29namespace llvm {
30
31class AAResults;
32class AssumptionCache;
33class BasicBlock;
34class BinaryOperator;
35class CondBrInst;
36class CmpInst;
37class Constant;
38class Function;
39class Instruction;
40class IntrinsicInst;
41class LazyValueInfo;
42class LoadInst;
43class PHINode;
44struct ScalarOptions;
45class SelectInst;
46class SwitchInst;
49class Value;
50
51/// A private "module" namespace for types and utilities used by
52/// JumpThreading.
53/// These are implementation details and should not be used by clients.
54namespace jumpthreading {
55
56// These are at global scope so static functions can use them too.
59
60// This is used to keep track of what kind of constant we're currently hoping
61// to find.
63
64} // end namespace jumpthreading
65
66/// This pass performs 'jump threading', which looks at blocks that have
67/// multiple predecessors and multiple successors. If one or more of the
68/// predecessors of the block can be proven to always jump to one of the
69/// successors, we forward the edge from the predecessor to the successor by
70/// duplicating the contents of this block.
71///
72/// An example of when this can occur is code like this:
73///
74/// if () { ...
75/// X = 4;
76/// }
77/// if (X < 3) {
78///
79/// In this case, the unconditional branch at the end of the first if can be
80/// revectored to the false side of the second if.
81class JumpThreadingPass : public OptionalPassInfoMixin<JumpThreadingPass> {
82 const ScalarOptions *Opts = nullptr;
83 Function *F = nullptr;
84 FunctionAnalysisManager *FAM = nullptr;
85 TargetLibraryInfo *TLI = nullptr;
86 TargetTransformInfo *TTI = nullptr;
87 LazyValueInfo *LVI = nullptr;
88 AAResults *AA = nullptr;
89 AssumptionCache *AC = nullptr;
90 std::unique_ptr<DomTreeUpdater> DTU;
91 BlockFrequencyInfo *BFI = nullptr;
92 BranchProbabilityInfo *BPI = nullptr;
93 bool ChangedSinceLastAnalysisUpdate = false;
94 bool HasGuards = false;
95#ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS
97#else
99#endif
100
101 // JumpThreading must not processes blocks unreachable from entry. It's a
102 // waste of compute time and can potentially lead to hangs.
104
105 unsigned BBDupThreshold;
106 unsigned DefaultBBDupThreshold;
107
108public:
109 LLVM_ABI JumpThreadingPass(int T = -1);
110
111 // Glue for old PM.
114 LazyValueInfo *LVI, AAResults *AA,
115 std::unique_ptr<DomTreeUpdater> DTU,
117
119
120 DomTreeUpdater *getDomTreeUpdater() const { return DTU.get(); }
124 LLVM_ABI void updateSSA(BasicBlock *BB, BasicBlock *NewBB,
125 ValueToValueMapTy &ValueMapping);
129 BasicBlock *PredBB);
131 const SmallVectorImpl<BasicBlock *> &PredBBs,
132 BasicBlock *SuccBB);
134 const SmallVectorImpl<BasicBlock *> &PredBBs,
135 BasicBlock *SuccBB);
137 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
138
142 SmallPtrSet<Value *, 4> &RecursionSet, Instruction *CtxI = nullptr);
143 bool
147 Instruction *CtxI = nullptr) {
148 SmallPtrSet<Value *, 4> RecursionSet;
149 return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
150 RecursionSet, CtxI);
151 }
152
154 BasicBlock *PredPredBB,
155 Value *cond,
156 const DataLayout &DL);
159 BasicBlock *PredBB, BasicBlock *BB,
160 BasicBlock *SuccBB);
161 LLVM_ABI bool
164 Instruction *CtxI = nullptr);
165
169
172 SelectInst *SI, PHINode *SIUse, unsigned Idx);
173
174 LLVM_ABI bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
177
180 CondBrInst *BI);
181
182private:
183 BasicBlock *splitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
184 const char *Suffix);
185 void updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
186 BasicBlock *NewBB, BasicBlock *SuccBB,
189 bool HasProfile);
190 /// Check if the block has profile metadata for its outgoing edges.
191 bool doesBlockHaveProfileData(BasicBlock *BB);
192
193 /// Returns analysis preserved by the pass.
194 PreservedAnalyses getPreservedAnalysis() const;
195
196 /// Helper function to run "external" analysis in the middle of JumpThreading.
197 /// It takes care of updating/invalidating other existing analysis
198 /// before/after running the "external" one.
199 template <typename AnalysisT>
200 typename AnalysisT::Result *runExternalAnalysis();
201
202 /// Returns an existing instance of BPI if any, otherwise nullptr. By
203 /// "existing" we mean either cached result provided by FunctionAnalysisManger
204 /// or created by preceding call to 'getOrCreateBPI'.
205 BranchProbabilityInfo *getBPI();
206
207 /// Returns an existing instance of BFI if any, otherwise nullptr. By
208 /// "existing" we mean either cached result provided by FunctionAnalysisManger
209 /// or created by preceding call to 'getOrCreateBFI'.
210 BlockFrequencyInfo *getBFI();
211
212 /// Returns an existing instance of BPI if any, otherwise:
213 /// if 'HasProfile' is true creates new instance through
214 /// FunctionAnalysisManager, otherwise nullptr.
215 BranchProbabilityInfo *getOrCreateBPI(bool Force = false);
216
217 /// Returns an existing instance of BFI if any, otherwise:
218 /// if 'HasProfile' is true creates new instance through
219 /// FunctionAnalysisManager, otherwise nullptr.
220 BlockFrequencyInfo *getOrCreateBFI(bool Force = false);
221
222 // Internal overload of evaluateOnPredecessorEdge().
224 Value *cond, const DataLayout &DL,
225 SmallPtrSet<Value *, 8> &Visited);
226};
227
228} // end namespace llvm
229
230#endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
SDValue Pred
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_ABI
Definition Compiler.h:211
This file defines the DenseSet and SmallDenseSet classes.
#define F(x, y, z)
Definition MD5.cpp:54
#define T
SmallVector< MachineOperand, 4 > Cond
This file defines the SmallSet class.
This file defines the SmallVector class.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
InstListType::iterator iterator
Instruction iterators...
Definition BasicBlock.h:170
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Analysis providing branch probability information.
This class is the base class for the comparison instructions.
Definition InstrTypes.h:728
Conditional Branch instruction.
This is an important base class in LLVM.
Definition Constant.h:44
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
A wrapper class for inspecting calls to intrinsic functions.
LLVM_ABI bool simplifyPartiallyRedundantLoad(LoadInst *LI)
simplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction,...
LLVM_ABI bool processBranchOnXOR(BinaryOperator *BO)
processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
LLVM_ABI bool processGuards(BasicBlock *BB)
Try to propagate a guard from the current BB into one of its predecessors in case if another branch o...
LLVM_ABI void updateSSA(BasicBlock *BB, BasicBlock *NewBB, ValueToValueMapTy &ValueMapping)
Update the SSA form.
LLVM_ABI void findLoopHeaders(Function &F)
findLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops...
LLVM_ABI bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB)
Merge basic block BB into its sole predecessor if possible.
LLVM_ABI bool computeValueKnownInPredecessorsImpl(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, SmallPtrSet< Value *, 4 > &RecursionSet, Instruction *CtxI=nullptr)
computeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the ...
LLVM_ABI JumpThreadingPass(int T=-1)
LLVM_ABI void cloneInstructions(ValueToValueMapTy &ValueMapping, BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock *NewBB, BasicBlock *PredBB)
Clone instructions in range [BI, BE) to NewBB.
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond, const DataLayout &DL)
LLVM_ABI bool processBranchOnPHI(PHINode *PN)
processBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node (or freeze PH...
LLVM_ABI bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)
Attempt to thread through two successive basic blocks.
LLVM_ABI void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)
DomTreeUpdater * getDomTreeUpdater() const
LLVM_ABI bool runImpl(Function &F, FunctionAnalysisManager *FAM, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, LazyValueInfo *LVI, AAResults *AA, std::unique_ptr< DomTreeUpdater > DTU, BlockFrequencyInfo *BFI, BranchProbabilityInfo *BPI)
LLVM_ABI bool processThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CtxI=nullptr)
LLVM_ABI bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, CondBrInst *BI)
Try to propagate the guard from BB which is the lower block of a diamond to one of its branches,...
LLVM_ABI bool processBlock(BasicBlock *BB)
processBlock - If there are any predecessors whose control can be threaded through to a successor,...
LLVM_ABI bool processImpliedCondition(BasicBlock *BB)
LLVM_ABI bool duplicateCondBranchOnPHIIntoPred(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs)
duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1...
LLVM_ABI void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)
LLVM_ABI bool tryThreadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
tryThreadEdge - Thread an edge if it's safe and profitable to do so.
LLVM_ABI bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)
tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2
LLVM_ABI bool tryToUnfoldSelectInCurrBB(BasicBlock *BB)
tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = ...
bool computeValueKnownInPredecessors(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, Instruction *CtxI=nullptr)
LLVM_ABI 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...
This pass computes, caches, and vends lazy value constraint information.
An instruction for reading from memory.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
This class represents the LLVM 'select' instruction.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition SmallSet.h:134
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Multiway switch.
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM Value Representation.
Definition Value.h:75
A private "module" namespace for types and utilities used by JumpThreading.
SmallVector< std::pair< Constant *, BasicBlock * >, 8 > PredValueInfoTy
SmallVectorImpl< std::pair< Constant *, BasicBlock * > > PredValueInfo
This is an optimization pass for GlobalISel generic memory operations.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
A CRTP mix-in for passes that can be skipped.