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"
23#include "llvm/IR/ValueHandle.h"
24#include <utility>
26namespace llvm {
28class AAResults;
29class BasicBlock;
30class BinaryOperator;
31class BranchInst;
32class CmpInst;
33class Constant;
34class DomTreeUpdater;
35class Function;
36class Instruction;
37class IntrinsicInst;
38class LazyValueInfo;
39class LoadInst;
40class PHINode;
41class SelectInst;
42class SwitchInst;
43class TargetLibraryInfo;
44class TargetTransformInfo;
45class Value;
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.
50namespace jumpthreading {
52// These are at global scope so static functions can use them too.
56// This is used to keep track of what kind of constant we're currently hoping
57// to find.
60} // end namespace jumpthreading
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.
68/// An example of when this can occur is code like this:
70/// if () { ...
71/// X = 4;
72/// }
73/// if (X < 3) {
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.
77class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
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;
93 unsigned BBDupThreshold;
94 unsigned DefaultBBDupThreshold;
97 JumpThreadingPass(int T = -1);
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);
108 BFI.reset();
109 BPI.reset();
110 }
113 bool processBlock(BasicBlock *BB);
115 void updateSSA(BasicBlock *BB, BasicBlock *NewBB,
119 BasicBlock *NewBB,
120 BasicBlock *PredBB);
121 bool tryThreadEdge(BasicBlock *BB,
122 const SmallVectorImpl<BasicBlock *> &PredBBs,
123 BasicBlock *SuccBB);
124 void threadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
125 BasicBlock *SuccBB);
127 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
132 DenseSet<Value *> &RecursionSet, Instruction *CxtI = nullptr);
133 bool
137 Instruction *CxtI = nullptr) {
138 DenseSet<Value *> RecursionSet;
139 return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
140 RecursionSet, CxtI);
141 }
144 Value *cond);
146 void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB,
147 BasicBlock *BB, BasicBlock *SuccBB);
150 Instruction *CxtI = nullptr);
152 bool processBranchOnPHI(PHINode *PN);
158 PHINode *SIUse, unsigned Idx);
160 bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
164 bool processGuards(BasicBlock *BB);
165 bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
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);
176} // 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
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
Conditional or Unconditional Branch instruction.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:708
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:77
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 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)
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...
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)
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