LLVM 19.0.0git
Go to the documentation of this file.
1//===- JumpThreading.h - thread control through conditional BBs -*- C++ -*-===//
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
9/// \file
10/// See the comments on JumpThreadingPass.
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/DenseSet.h"
19#include "llvm/ADT/SmallSet.h"
24#include "llvm/IR/ValueHandle.h"
26#include <optional>
27#include <utility>
29namespace llvm {
31class AAResults;
32class BasicBlock;
33class BinaryOperator;
34class BranchInst;
35class CmpInst;
36class Constant;
37class Function;
38class Instruction;
39class IntrinsicInst;
40class LazyValueInfo;
41class LoadInst;
42class PHINode;
43class SelectInst;
44class SwitchInst;
45class TargetLibraryInfo;
46class TargetTransformInfo;
47class Value;
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.
52namespace jumpthreading {
54// These are at global scope so static functions can use them too.
58// This is used to keep track of what kind of constant we're currently hoping
59// to find.
62} // end namespace jumpthreading
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.
70/// An example of when this can occur is code like this:
72/// if () { ...
73/// X = 4;
74/// }
75/// if (X < 3) {
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.
79class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
80 Function *F = nullptr;
81 FunctionAnalysisManager *FAM = nullptr;
82 TargetLibraryInfo *TLI = nullptr;
83 TargetTransformInfo *TTI = nullptr;
84 LazyValueInfo *LVI = nullptr;
85 AAResults *AA = nullptr;
86 std::unique_ptr<DomTreeUpdater> DTU;
87 std::optional<BlockFrequencyInfo *> BFI;
88 std::optional<BranchProbabilityInfo *> BPI;
89 bool ChangedSinceLastAnalysisUpdate = false;
90 bool HasGuards = false;
97 unsigned BBDupThreshold;
98 unsigned DefaultBBDupThreshold;
101 JumpThreadingPass(int T = -1);
103 // Glue for old PM.
106 LazyValueInfo *LVI, AAResults *AA,
107 std::unique_ptr<DomTreeUpdater> DTU,
108 std::optional<BlockFrequencyInfo *> BFI,
109 std::optional<BranchProbabilityInfo *> BPI);
113 DomTreeUpdater *getDomTreeUpdater() const { return DTU.get(); }
114 void findLoopHeaders(Function &F);
115 bool processBlock(BasicBlock *BB);
117 void updateSSA(BasicBlock *BB, BasicBlock *NewBB,
118 ValueToValueMapTy &ValueMapping);
119 void cloneInstructions(ValueToValueMapTy &ValueMapping,
121 BasicBlock *NewBB, BasicBlock *PredBB);
122 bool tryThreadEdge(BasicBlock *BB,
123 const SmallVectorImpl<BasicBlock *> &PredBBs,
124 BasicBlock *SuccBB);
125 void threadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
126 BasicBlock *SuccBB);
128 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
133 SmallPtrSet<Value *, 4> &RecursionSet, Instruction *CxtI = nullptr);
134 bool
138 Instruction *CxtI = nullptr) {
139 SmallPtrSet<Value *, 4> RecursionSet;
140 return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
141 RecursionSet, CxtI);
142 }
145 Value *cond, const DataLayout &DL);
147 void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB,
148 BasicBlock *BB, BasicBlock *SuccBB);
151 Instruction *CxtI = nullptr);
153 bool processBranchOnPHI(PHINode *PN);
159 PHINode *SIUse, unsigned Idx);
161 bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
165 bool processGuards(BasicBlock *BB);
166 bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
169 BasicBlock *splitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
170 const char *Suffix);
171 void updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
172 BasicBlock *NewBB, BasicBlock *SuccBB,
175 bool HasProfile);
176 /// Check if the block has profile metadata for its outgoing edges.
177 bool doesBlockHaveProfileData(BasicBlock *BB);
179 /// Returns analysis preserved by the pass.
180 PreservedAnalyses getPreservedAnalysis() const;
182 /// Helper function to run "external" analysis in the middle of JumpThreading.
183 /// It takes care of updating/invalidating other existing analysis
184 /// before/after running the "external" one.
185 template <typename AnalysisT>
186 typename AnalysisT::Result *runExternalAnalysis();
188 /// Returns an existing instance of BPI if any, otherwise nullptr. By
189 /// "existing" we mean either cached result provided by FunctionAnalysisManger
190 /// or created by preceding call to 'getOrCreateBPI'.
191 BranchProbabilityInfo *getBPI();
193 /// Returns an existing instance of BFI if any, otherwise nullptr. By
194 /// "existing" we mean either cached result provided by FunctionAnalysisManger
195 /// or created by preceding call to 'getOrCreateBFI'.
196 BlockFrequencyInfo *getBFI();
198 /// Returns an existing instance of BPI if any, otherwise:
199 /// if 'HasProfile' is true creates new instance through
200 /// FunctionAnalysisManager, otherwise nullptr.
201 BranchProbabilityInfo *getOrCreateBPI(bool Force = false);
203 /// Returns an existing instance of BFI if any, otherwise:
204 /// if 'HasProfile' is true creates new instance through
205 /// FunctionAnalysisManager, otherwise nullptr.
206 BlockFrequencyInfo *getOrCreateBFI(bool Force = false);
209} // end namespace llvm
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseSet and SmallDenseSet classes.
#define F(x, y, z)
Definition: MD5.cpp:55
FunctionAnalysisManager FAM
const SmallVectorImpl< MachineOperand > & Cond
This file defines the SmallSet class.
This file defines the SmallVector class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:165
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
Analysis providing branch probability information.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:983
This is an important base class in LLVM.
Definition: Constant.h:41
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:48
This pass performs 'jump threading', which looks at blocks that have multiple predecessors and multip...
Definition: JumpThreading.h:79
bool simplifyPartiallyRedundantLoad(LoadInst *LI)
simplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction,...
bool processBranchOnXOR(BinaryOperator *BO)
processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
bool processGuards(BasicBlock *BB)
Try to propagate a guard from the current BB into one of its predecessors in case if another branch o...
void updateSSA(BasicBlock *BB, BasicBlock *NewBB, ValueToValueMapTy &ValueMapping)
Update the SSA form.
bool computeValueKnownInPredecessors(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
void findLoopHeaders(Function &F)
findLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops...
bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB)
Merge basic block BB into its sole predecessor if possible.
void cloneInstructions(ValueToValueMapTy &ValueMapping, BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock *NewBB, BasicBlock *PredBB)
Clone instructions in range [BI, BE) to NewBB.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool runImpl(Function &F, FunctionAnalysisManager *FAM, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, LazyValueInfo *LVI, AAResults *AA, std::unique_ptr< DomTreeUpdater > DTU, std::optional< BlockFrequencyInfo * > BFI, std::optional< BranchProbabilityInfo * > BPI)
Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond, const DataLayout &DL)
bool processBranchOnPHI(PHINode *PN)
processBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node (or freeze PH...
bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)
Attempt to thread through two successive basic blocks.
bool computeValueKnownInPredecessorsImpl(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, SmallPtrSet< Value *, 4 > &RecursionSet, Instruction *CxtI=nullptr)
computeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the ...
void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)
DomTreeUpdater * getDomTreeUpdater() const
bool processThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
bool processBlock(BasicBlock *BB)
processBlock - If there are any predecessors whose control can be threaded through to a successor,...
bool processImpliedCondition(BasicBlock *BB)
bool duplicateCondBranchOnPHIIntoPred(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs)
duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1...
void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)
bool tryThreadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
tryThreadEdge - Thread an edge if it's safe and profitable to do so.
bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)
tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2
bool tryToUnfoldSelectInCurrBB(BasicBlock *BB)
tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = ...
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...
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,...
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:31
An instruction for reading from memory.
Definition: Instructions.h:185
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
This class represents the LLVM 'select' instruction.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:74
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:74