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
7 //===----------------------------------------------------------------------===//
10 /// See the comments on JumpThreadingPass.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
15 #define LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
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"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/Analysis/BlockFrequencyInfo.h"
24 #include "llvm/Analysis/BranchProbabilityInfo.h"
25 #include "llvm/Analysis/DomTreeUpdater.h"
26 #include "llvm/IR/ValueHandle.h"
44 class TargetLibraryInfo;
47 /// A private "module" namespace for types and utilities used by
49 /// These are implementation details and should not be used by clients.
50 namespace jumpthreading {
52 // These are at global scope so static functions can use them too.
53 using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>;
54 using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>;
56 // This is used to keep track of what kind of constant we're currently hoping
58 enum ConstantPreference { WantInteger, WantBlockAddress };
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:
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.
77 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
78 TargetLibraryInfo *TLI;
82 std::unique_ptr<BlockFrequencyInfo> BFI;
83 std::unique_ptr<BranchProbabilityInfo> BPI;
84 bool HasProfileData = false;
85 bool HasGuards = false;
87 SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
89 SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
92 unsigned BBDupThreshold;
95 JumpThreadingPass(int T = -1);
98 bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_,
99 AliasAnalysis *AA_, DomTreeUpdater *DTU_, bool HasProfileData_,
100 std::unique_ptr<BlockFrequencyInfo> BFI_,
101 std::unique_ptr<BranchProbabilityInfo> BPI_);
103 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
105 void releaseMemory() {
110 void FindLoopHeaders(Function &F);
111 bool ProcessBlock(BasicBlock *BB);
112 bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
114 bool DuplicateCondBranchOnPHIIntoPred(
115 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
117 bool ComputeValueKnownInPredecessorsImpl(
118 Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
119 jumpthreading::ConstantPreference Preference,
120 DenseSet<std::pair<Value *, BasicBlock *>> &RecursionSet,
121 Instruction *CxtI = nullptr);
123 ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
124 jumpthreading::PredValueInfo &Result,
125 jumpthreading::ConstantPreference Preference,
126 Instruction *CxtI = nullptr) {
127 DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet;
128 return ComputeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
132 bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
133 jumpthreading::ConstantPreference Preference,
134 Instruction *CxtI = nullptr);
136 bool ProcessBranchOnPHI(PHINode *PN);
137 bool ProcessBranchOnXOR(BinaryOperator *BO);
138 bool ProcessImpliedCondition(BasicBlock *BB);
140 bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
141 void UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI,
142 PHINode *SIUse, unsigned Idx);
144 bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
145 bool TryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB);
146 bool TryToUnfoldSelectInCurrBB(BasicBlock *BB);
148 bool ProcessGuards(BasicBlock *BB);
149 bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
152 BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
154 void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
155 BasicBlock *NewBB, BasicBlock *SuccBB);
156 /// Check if the block has profile metadata for its outgoing edges.
157 bool doesBlockHaveProfileData(BasicBlock *BB);
160 } // end namespace llvm
162 #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H