LLVM 17.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"
25#include <optional>
26#include <utility>
28namespace llvm {
30class AAResults;
31class BasicBlock;
32class BinaryOperator;
33class BranchInst;
34class CmpInst;
35class Constant;
36class Function;
37class Instruction;
38class IntrinsicInst;
39class LazyValueInfo;
40class LoadInst;
41class PHINode;
42class SelectInst;
43class SwitchInst;
44class TargetLibraryInfo;
45class TargetTransformInfo;
46class Value;
48/// A private "module" namespace for types and utilities used by
49/// JumpThreading.
50/// These are implementation details and should not be used by clients.
51namespace jumpthreading {
53// These are at global scope so static functions can use them too.
57// This is used to keep track of what kind of constant we're currently hoping
58// to find.
61} // end namespace jumpthreading
63/// This pass performs 'jump threading', which looks at blocks that have
64/// multiple predecessors and multiple successors. If one or more of the
65/// predecessors of the block can be proven to always jump to one of the
66/// successors, we forward the edge from the predecessor to the successor by
67/// duplicating the contents of this block.
69/// An example of when this can occur is code like this:
71/// if () { ...
72/// X = 4;
73/// }
74/// if (X < 3) {
76/// In this case, the unconditional branch at the end of the first if can be
77/// revectored to the false side of the second if.
78class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
79 Function *F = nullptr;
80 FunctionAnalysisManager *FAM = nullptr;
81 TargetLibraryInfo *TLI = nullptr;
82 TargetTransformInfo *TTI = nullptr;
83 LazyValueInfo *LVI = nullptr;
84 AAResults *AA = nullptr;
85 std::unique_ptr<DomTreeUpdater> DTU;
86 std::optional<BlockFrequencyInfo *> BFI;
87 std::optional<BranchProbabilityInfo *> BPI;
88 bool ChangedSinceLastAnalysisUpdate = false;
89 bool HasGuards = false;
96 unsigned BBDupThreshold;
97 unsigned DefaultBBDupThreshold;
100 JumpThreadingPass(int T = -1);
102 // Glue for old PM.
105 LazyValueInfo *LVI, AAResults *AA,
106 std::unique_ptr<DomTreeUpdater> DTU,
107 std::optional<BlockFrequencyInfo *> BFI,
108 std::optional<BranchProbabilityInfo *> BPI);
112 DomTreeUpdater *getDomTreeUpdater() const { return DTU.get(); }
113 void findLoopHeaders(Function &F);
114 bool processBlock(BasicBlock *BB);
116 void updateSSA(BasicBlock *BB, BasicBlock *NewBB,
120 BasicBlock *NewBB,
121 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 DenseSet<Value *> &RecursionSet, Instruction *CxtI = nullptr);
134 bool
138 Instruction *CxtI = nullptr) {
139 DenseSet<Value *> RecursionSet;
140 return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
141 RecursionSet, CxtI);
142 }
145 Value *cond);
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
SmallVector< MachineOperand, 4 > Cond
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
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:620
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:56
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
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:701
This is an important base class in LLVM.
Definition: Constant.h:41
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
This pass performs 'jump threading', which looks at blocks that have multiple predecessors and multip...
Definition: JumpThreading.h:78
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...
DenseMap< Instruction *, Value * > cloneInstructions(BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock *NewBB, BasicBlock *PredBB)
Clone instructions in range [BI, BE) to NewBB.
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.
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)
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.
void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)
DomTreeUpdater * getDomTreeUpdater() const
Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond)
bool processThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
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 ...
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 updateSSA(BasicBlock *BB, BasicBlock *NewBB, DenseMap< Instruction *, Value * > &ValueMapping)
Update the SSA form.
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:177
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
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:450
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:577
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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:371