LLVM  14.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 TargetTransformInfo;
48 class Value;
49 
50 /// A private "module" namespace for types and utilities used by
51 /// JumpThreading.
52 /// These are implementation details and should not be used by clients.
53 namespace jumpthreading {
54 
55 // These are at global scope so static functions can use them too.
58 
59 // This is used to keep track of what kind of constant we're currently hoping
60 // to find.
62 
63 } // end namespace jumpthreading
64 
65 /// This pass performs 'jump threading', which looks at blocks that have
66 /// multiple predecessors and multiple successors. If one or more of the
67 /// predecessors of the block can be proven to always jump to one of the
68 /// successors, we forward the edge from the predecessor to the successor by
69 /// duplicating the contents of this block.
70 ///
71 /// An example of when this can occur is code like this:
72 ///
73 /// if () { ...
74 /// X = 4;
75 /// }
76 /// if (X < 3) {
77 ///
78 /// In this case, the unconditional branch at the end of the first if can be
79 /// revectored to the false side of the second if.
80 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
81  TargetLibraryInfo *TLI;
83  LazyValueInfo *LVI;
84  AAResults *AA;
85  DomTreeUpdater *DTU;
86  std::unique_ptr<BlockFrequencyInfo> BFI;
87  std::unique_ptr<BranchProbabilityInfo> BPI;
88  bool HasProfileData = false;
89  bool HasGuards = false;
90 #ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS
92 #else
94 #endif
95 
96  unsigned BBDupThreshold;
97  unsigned DefaultBBDupThreshold;
98  bool InsertFreezeWhenUnfoldingSelect;
99 
100 public:
101  JumpThreadingPass(bool InsertFreezeWhenUnfoldingSelect = false, int T = -1);
102 
103  // Glue for old PM.
105  LazyValueInfo *LVI, AAResults *AA, DomTreeUpdater *DTU,
106  bool HasProfileData, std::unique_ptr<BlockFrequencyInfo> BFI,
107  std::unique_ptr<BranchProbabilityInfo> BPI);
108 
110 
111  void releaseMemory() {
112  BFI.reset();
113  BPI.reset();
114  }
115 
116  void findLoopHeaders(Function &F);
117  bool processBlock(BasicBlock *BB);
119  void updateSSA(BasicBlock *BB, BasicBlock *NewBB,
120  DenseMap<Instruction *, Value *> &ValueMapping);
123  BasicBlock *NewBB,
124  BasicBlock *PredBB);
126  const SmallVectorImpl<BasicBlock *> &PredBBs,
127  BasicBlock *SuccBB);
129  BasicBlock *SuccBB);
131  BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
132 
136  DenseSet<Value *> &RecursionSet, Instruction *CxtI = nullptr);
137  bool
141  Instruction *CxtI = nullptr) {
142  DenseSet<Value *> RecursionSet;
144  RecursionSet, CxtI);
145  }
146 
148  Value *cond);
150  void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB,
151  BasicBlock *BB, BasicBlock *SuccBB);
154  Instruction *CxtI = nullptr);
155 
156  bool processBranchOnPHI(PHINode *PN);
159 
162  PHINode *SIUse, unsigned Idx);
163 
164  bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
167 
168  bool processGuards(BasicBlock *BB);
169  bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
170 
171 private:
172  BasicBlock *splitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
173  const char *Suffix);
174  void updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
175  BasicBlock *NewBB, BasicBlock *SuccBB);
176  /// Check if the block has profile metadata for its outgoing edges.
177  bool doesBlockHaveProfileData(BasicBlock *BB);
178 };
179 
180 } // end namespace llvm
181 
182 #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
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::JumpThreadingPass::unfoldSelectInstr
void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)
Definition: JumpThreading.cpp:2725
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:603
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:62
llvm::JumpThreadingPass::processBranchOnXOR
bool processBranchOnXOR(BinaryOperator *BO)
processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
Definition: JumpThreading.cpp:1833
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:61
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:169
DomTreeUpdater.h
llvm::jumpthreading::ConstantPreference
ConstantPreference
Definition: JumpThreading.h:61
llvm::JumpThreadingPass::maybethreadThroughTwoBasicBlocks
bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)
Attempt to thread through two successive basic blocks.
Definition: JumpThreading.cpp:2115
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:1579
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:1249
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:2318
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:2597
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:2357
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:76
llvm::AAResults
Definition: AliasAnalysis.h:508
llvm::JumpThreadingPass::releaseMemory
void releaseMemory()
Definition: JumpThreading.h:111
llvm::jumpthreading::WantInteger
@ WantInteger
Definition: JumpThreading.h:61
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:2799
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:2860
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:711
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:1303
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:138
ArrayRef.h
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::JumpThreadingPass
This pass performs 'jump threading', which looks at blocks that have multiple predecessors and multip...
Definition: JumpThreading.h:80
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1732
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
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:2962
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:1969
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:2996
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::JumpThreadingPass::threadThroughTwoBasicBlocks
void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)
Definition: JumpThreading.cpp:2252
BlockFrequencyInfo.h
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
ValueHandle.h
llvm::JumpThreadingPass::processThreadableEdges
bool processThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
Definition: JumpThreading.cpp:1619
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:221
llvm::JumpThreadingPass::runImpl
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)
Definition: JumpThreading.cpp:379
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:2020
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:636
SmallVector.h
llvm::PHINode
Definition: Instructions.h:2648
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:3227
llvm::Sched::Preference
Preference
Definition: TargetLowering.h:98
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3083
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:2066
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:1024
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
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:1801
llvm::codeview::PublicSymFlags::Function
@ Function
SmallSet.h