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 <optional> 26 #include <utility> 27 28 namespace llvm { 29 30 class AAResults; 31 class BasicBlock; 32 class BinaryOperator; 33 class BranchInst; 34 class CmpInst; 35 class Constant; 36 class Function; 37 class Instruction; 38 class IntrinsicInst; 39 class LazyValueInfo; 40 class LoadInst; 41 class PHINode; 42 class SelectInst; 43 class SwitchInst; 44 class TargetLibraryInfo; 45 class TargetTransformInfo; 46 class Value; 47 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. 51 namespace jumpthreading { 52 53 // These are at global scope so static functions can use them too. 54 using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>; 55 using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>; 56 57 // This is used to keep track of what kind of constant we're currently hoping 58 // to find. 59 enum ConstantPreference { WantInteger, WantBlockAddress }; 60 61 } // end namespace jumpthreading 62 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. 68 /// 69 /// An example of when this can occur is code like this: 70 /// 71 /// if () { ... 72 /// X = 4; 73 /// } 74 /// if (X < 3) { 75 /// 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. 78 class 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; 90 #ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS 91 SmallPtrSet<const BasicBlock *, 16> LoopHeaders; 92 #else 93 SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders; 94 #endif 95 96 unsigned BBDupThreshold; 97 unsigned DefaultBBDupThreshold; 98 99 public: 100 JumpThreadingPass(int T = -1); 101 102 // Glue for old PM. 103 bool runImpl(Function &F, FunctionAnalysisManager *FAM, 104 TargetLibraryInfo *TLI, TargetTransformInfo *TTI, 105 LazyValueInfo *LVI, AAResults *AA, 106 std::unique_ptr<DomTreeUpdater> DTU, 107 std::optional<BlockFrequencyInfo *> BFI, 108 std::optional<BranchProbabilityInfo *> BPI); 109 110 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 111 112 DomTreeUpdater *getDomTreeUpdater() const { return DTU.get(); } 113 void findLoopHeaders(Function &F); 114 bool processBlock(BasicBlock *BB); 115 bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB); 116 void updateSSA(BasicBlock *BB, BasicBlock *NewBB, 117 DenseMap<Instruction *, Value *> &ValueMapping); 118 DenseMap<Instruction *, Value *> cloneInstructions(BasicBlock::iterator BI, 119 BasicBlock::iterator BE, 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); 127 bool duplicateCondBranchOnPHIIntoPred( 128 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs); 129 130 bool computeValueKnownInPredecessorsImpl( 131 Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, 132 jumpthreading::ConstantPreference Preference, 133 DenseSet<Value *> &RecursionSet, Instruction *CxtI = nullptr); 134 bool 135 computeValueKnownInPredecessors(Value *V, BasicBlock *BB, 136 jumpthreading::PredValueInfo &Result, 137 jumpthreading::ConstantPreference Preference, 138 Instruction *CxtI = nullptr) { 139 DenseSet<Value *> RecursionSet; 140 return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference, 141 RecursionSet, CxtI); 142 } 143 144 Constant *evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, 145 Value *cond); 146 bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond); 147 void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, 148 BasicBlock *BB, BasicBlock *SuccBB); 149 bool processThreadableEdges(Value *Cond, BasicBlock *BB, 150 jumpthreading::ConstantPreference Preference, 151 Instruction *CxtI = nullptr); 152 153 bool processBranchOnPHI(PHINode *PN); 154 bool processBranchOnXOR(BinaryOperator *BO); 155 bool processImpliedCondition(BasicBlock *BB); 156 157 bool simplifyPartiallyRedundantLoad(LoadInst *LI); 158 void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, 159 PHINode *SIUse, unsigned Idx); 160 161 bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); 162 bool tryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB); 163 bool tryToUnfoldSelectInCurrBB(BasicBlock *BB); 164 165 bool processGuards(BasicBlock *BB); 166 bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI); 167 168 private: 169 BasicBlock *splitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 170 const char *Suffix); 171 void updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB, 172 BasicBlock *NewBB, BasicBlock *SuccBB, 173 BlockFrequencyInfo *BFI, 174 BranchProbabilityInfo *BPI, 175 bool HasProfile); 176 /// Check if the block has profile metadata for its outgoing edges. 177 bool doesBlockHaveProfileData(BasicBlock *BB); 178 179 /// Returns analysis preserved by the pass. 180 PreservedAnalyses getPreservedAnalysis() const; 181 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(); 187 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(); 192 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(); 197 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); 202 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); 207 }; 208 209 } // end namespace llvm 210 211 #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H 212