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/SmallSet.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/Analysis/BlockFrequencyInfo.h" 22 #include "llvm/Analysis/BranchProbabilityInfo.h" 23 #include "llvm/Analysis/DomTreeUpdater.h" 24 #include "llvm/IR/ValueHandle.h" 25 #include "llvm/Support/Compiler.h" 26 #include "llvm/Transforms/Utils/ValueMapper.h" 27 #include <optional> 28 #include <utility> 29 30 namespace llvm { 31 32 class AAResults; 33 class BasicBlock; 34 class BinaryOperator; 35 class BranchInst; 36 class CmpInst; 37 class Constant; 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. 56 using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>; 57 using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>; 58 59 // This is used to keep track of what kind of constant we're currently hoping 60 // to find. 61 enum ConstantPreference { WantInteger, WantBlockAddress }; 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 Function *F = nullptr; 82 FunctionAnalysisManager *FAM = nullptr; 83 TargetLibraryInfo *TLI = nullptr; 84 TargetTransformInfo *TTI = nullptr; 85 LazyValueInfo *LVI = nullptr; 86 AAResults *AA = nullptr; 87 std::unique_ptr<DomTreeUpdater> DTU; 88 BlockFrequencyInfo *BFI = nullptr; 89 BranchProbabilityInfo *BPI = nullptr; 90 bool ChangedSinceLastAnalysisUpdate = false; 91 bool HasGuards = false; 92 #ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS 93 SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders; 94 #else 95 SmallPtrSet<const BasicBlock *, 16> LoopHeaders; 96 #endif 97 98 // JumpThreading must not processes blocks unreachable from entry. It's a 99 // waste of compute time and can potentially lead to hangs. 100 SmallPtrSet<BasicBlock *, 16> Unreachable; 101 102 unsigned BBDupThreshold; 103 unsigned DefaultBBDupThreshold; 104 105 public: 106 LLVM_ABI JumpThreadingPass(int T = -1); 107 108 // Glue for old PM. 109 LLVM_ABI bool runImpl(Function &F, FunctionAnalysisManager *FAM, 110 TargetLibraryInfo *TLI, TargetTransformInfo *TTI, 111 LazyValueInfo *LVI, AAResults *AA, 112 std::unique_ptr<DomTreeUpdater> DTU, 113 BlockFrequencyInfo *BFI, BranchProbabilityInfo *BPI); 114 115 LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 116 getDomTreeUpdater()117 DomTreeUpdater *getDomTreeUpdater() const { return DTU.get(); } 118 LLVM_ABI void findLoopHeaders(Function &F); 119 LLVM_ABI bool processBlock(BasicBlock *BB); 120 LLVM_ABI bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB); 121 LLVM_ABI void updateSSA(BasicBlock *BB, BasicBlock *NewBB, 122 ValueToValueMapTy &ValueMapping); 123 LLVM_ABI void cloneInstructions(ValueToValueMapTy &ValueMapping, 124 BasicBlock::iterator BI, 125 BasicBlock::iterator BE, BasicBlock *NewBB, 126 BasicBlock *PredBB); 127 LLVM_ABI bool tryThreadEdge(BasicBlock *BB, 128 const SmallVectorImpl<BasicBlock *> &PredBBs, 129 BasicBlock *SuccBB); 130 LLVM_ABI void threadEdge(BasicBlock *BB, 131 const SmallVectorImpl<BasicBlock *> &PredBBs, 132 BasicBlock *SuccBB); 133 LLVM_ABI bool duplicateCondBranchOnPHIIntoPred( 134 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs); 135 136 LLVM_ABI bool computeValueKnownInPredecessorsImpl( 137 Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, 138 jumpthreading::ConstantPreference Preference, 139 SmallPtrSet<Value *, 4> &RecursionSet, Instruction *CxtI = nullptr); 140 bool 141 computeValueKnownInPredecessors(Value *V, BasicBlock *BB, 142 jumpthreading::PredValueInfo &Result, 143 jumpthreading::ConstantPreference Preference, 144 Instruction *CxtI = nullptr) { 145 SmallPtrSet<Value *, 4> RecursionSet; 146 return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference, 147 RecursionSet, CxtI); 148 } 149 150 LLVM_ABI Constant *evaluateOnPredecessorEdge(BasicBlock *BB, 151 BasicBlock *PredPredBB, 152 Value *cond, 153 const DataLayout &DL); 154 LLVM_ABI bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond); 155 LLVM_ABI void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, 156 BasicBlock *PredBB, BasicBlock *BB, 157 BasicBlock *SuccBB); 158 LLVM_ABI bool 159 processThreadableEdges(Value *Cond, BasicBlock *BB, 160 jumpthreading::ConstantPreference Preference, 161 Instruction *CxtI = nullptr); 162 163 LLVM_ABI bool processBranchOnPHI(PHINode *PN); 164 LLVM_ABI bool processBranchOnXOR(BinaryOperator *BO); 165 LLVM_ABI bool processImpliedCondition(BasicBlock *BB); 166 167 LLVM_ABI bool simplifyPartiallyRedundantLoad(LoadInst *LI); 168 LLVM_ABI void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, 169 SelectInst *SI, PHINode *SIUse, unsigned Idx); 170 171 LLVM_ABI bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); 172 LLVM_ABI bool tryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB); 173 LLVM_ABI bool tryToUnfoldSelectInCurrBB(BasicBlock *BB); 174 175 LLVM_ABI bool processGuards(BasicBlock *BB); 176 LLVM_ABI bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, 177 BranchInst *BI); 178 179 private: 180 BasicBlock *splitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 181 const char *Suffix); 182 void updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB, 183 BasicBlock *NewBB, BasicBlock *SuccBB, 184 BlockFrequencyInfo *BFI, 185 BranchProbabilityInfo *BPI, 186 bool HasProfile); 187 /// Check if the block has profile metadata for its outgoing edges. 188 bool doesBlockHaveProfileData(BasicBlock *BB); 189 190 /// Returns analysis preserved by the pass. 191 PreservedAnalyses getPreservedAnalysis() const; 192 193 /// Helper function to run "external" analysis in the middle of JumpThreading. 194 /// It takes care of updating/invalidating other existing analysis 195 /// before/after running the "external" one. 196 template <typename AnalysisT> 197 typename AnalysisT::Result *runExternalAnalysis(); 198 199 /// Returns an existing instance of BPI if any, otherwise nullptr. By 200 /// "existing" we mean either cached result provided by FunctionAnalysisManger 201 /// or created by preceding call to 'getOrCreateBPI'. 202 BranchProbabilityInfo *getBPI(); 203 204 /// Returns an existing instance of BFI if any, otherwise nullptr. By 205 /// "existing" we mean either cached result provided by FunctionAnalysisManger 206 /// or created by preceding call to 'getOrCreateBFI'. 207 BlockFrequencyInfo *getBFI(); 208 209 /// Returns an existing instance of BPI if any, otherwise: 210 /// if 'HasProfile' is true creates new instance through 211 /// FunctionAnalysisManager, otherwise nullptr. 212 BranchProbabilityInfo *getOrCreateBPI(bool Force = false); 213 214 /// Returns an existing instance of BFI if any, otherwise: 215 /// if 'HasProfile' is true creates new instance through 216 /// FunctionAnalysisManager, otherwise nullptr. 217 BlockFrequencyInfo *getOrCreateBFI(bool Force = false); 218 219 // Internal overload of evaluateOnPredecessorEdge(). 220 Constant *evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, 221 Value *cond, const DataLayout &DL, 222 SmallPtrSet<Value *, 8> &Visited); 223 }; 224 225 } // end namespace llvm 226 227 #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H 228