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/IR/ValueHandle.h" 24 #include <utility> 25 26 namespace llvm { 27 28 class AAResults; 29 class BasicBlock; 30 class BinaryOperator; 31 class BranchInst; 32 class CmpInst; 33 class Constant; 34 class DomTreeUpdater; 35 class Function; 36 class Instruction; 37 class IntrinsicInst; 38 class LazyValueInfo; 39 class LoadInst; 40 class PHINode; 41 class SelectInst; 42 class SwitchInst; 43 class TargetLibraryInfo; 44 class TargetTransformInfo; 45 class Value; 46 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. 50 namespace jumpthreading { 51 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>; 55 56 // This is used to keep track of what kind of constant we're currently hoping 57 // to find. 58 enum ConstantPreference { WantInteger, WantBlockAddress }; 59 60 } // end namespace jumpthreading 61 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. 67 /// 68 /// An example of when this can occur is code like this: 69 /// 70 /// if () { ... 71 /// X = 4; 72 /// } 73 /// if (X < 3) { 74 /// 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; 79 TargetTransformInfo *TTI; 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; 87 #ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS 88 SmallPtrSet<const BasicBlock *, 16> LoopHeaders; 89 #else 90 SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders; 91 #endif 92 93 unsigned BBDupThreshold; 94 unsigned DefaultBBDupThreshold; 95 96 public: 97 JumpThreadingPass(int T = -1); 98 99 // Glue for old PM. 100 bool runImpl(Function &F, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, 101 LazyValueInfo *LVI, AAResults *AA, DomTreeUpdater *DTU, 102 bool HasProfileData, std::unique_ptr<BlockFrequencyInfo> BFI, 103 std::unique_ptr<BranchProbabilityInfo> BPI); 104 105 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 106 107 void releaseMemory() { 108 BFI.reset(); 109 BPI.reset(); 110 } 111 112 void findLoopHeaders(Function &F); 113 bool processBlock(BasicBlock *BB); 114 bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB); 115 void updateSSA(BasicBlock *BB, BasicBlock *NewBB, 116 DenseMap<Instruction *, Value *> &ValueMapping); 117 DenseMap<Instruction *, Value *> cloneInstructions(BasicBlock::iterator BI, 118 BasicBlock::iterator BE, 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); 126 bool duplicateCondBranchOnPHIIntoPred( 127 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs); 128 129 bool computeValueKnownInPredecessorsImpl( 130 Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, 131 jumpthreading::ConstantPreference Preference, 132 DenseSet<Value *> &RecursionSet, Instruction *CxtI = nullptr); 133 bool 134 computeValueKnownInPredecessors(Value *V, BasicBlock *BB, 135 jumpthreading::PredValueInfo &Result, 136 jumpthreading::ConstantPreference Preference, 137 Instruction *CxtI = nullptr) { 138 DenseSet<Value *> RecursionSet; 139 return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference, 140 RecursionSet, CxtI); 141 } 142 143 Constant *evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, 144 Value *cond); 145 bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond); 146 void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, 147 BasicBlock *BB, BasicBlock *SuccBB); 148 bool processThreadableEdges(Value *Cond, BasicBlock *BB, 149 jumpthreading::ConstantPreference Preference, 150 Instruction *CxtI = nullptr); 151 152 bool processBranchOnPHI(PHINode *PN); 153 bool processBranchOnXOR(BinaryOperator *BO); 154 bool processImpliedCondition(BasicBlock *BB); 155 156 bool simplifyPartiallyRedundantLoad(LoadInst *LI); 157 void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, 158 PHINode *SIUse, unsigned Idx); 159 160 bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); 161 bool tryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB); 162 bool tryToUnfoldSelectInCurrBB(BasicBlock *BB); 163 164 bool processGuards(BasicBlock *BB); 165 bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI); 166 167 private: 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); 174 }; 175 176 } // end namespace llvm 177 178 #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H 179