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" 22 #include "llvm/Analysis/BlockFrequencyInfo.h" 23 #include "llvm/Analysis/BranchProbabilityInfo.h" 24 #include "llvm/Analysis/DomTreeUpdater.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. 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 TargetLibraryInfo *TLI; 82 TargetTransformInfo *TTI; 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 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 bool InsertFreezeWhenUnfoldingSelect; 99 100 public: 101 JumpThreadingPass(bool InsertFreezeWhenUnfoldingSelect = false, int T = -1); 102 103 // Glue for old PM. 104 bool runImpl(Function &F, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, 105 LazyValueInfo *LVI, AAResults *AA, DomTreeUpdater *DTU, 106 bool HasProfileData, std::unique_ptr<BlockFrequencyInfo> BFI, 107 std::unique_ptr<BranchProbabilityInfo> BPI); 108 109 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 110 111 void releaseMemory() { 112 BFI.reset(); 113 BPI.reset(); 114 } 115 116 void findLoopHeaders(Function &F); 117 bool processBlock(BasicBlock *BB); 118 bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB); 119 void updateSSA(BasicBlock *BB, BasicBlock *NewBB, 120 DenseMap<Instruction *, Value *> &ValueMapping); 121 DenseMap<Instruction *, Value *> cloneInstructions(BasicBlock::iterator BI, 122 BasicBlock::iterator BE, 123 BasicBlock *NewBB, 124 BasicBlock *PredBB); 125 bool tryThreadEdge(BasicBlock *BB, 126 const SmallVectorImpl<BasicBlock *> &PredBBs, 127 BasicBlock *SuccBB); 128 void threadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs, 129 BasicBlock *SuccBB); 130 bool duplicateCondBranchOnPHIIntoPred( 131 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs); 132 133 bool computeValueKnownInPredecessorsImpl( 134 Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, 135 jumpthreading::ConstantPreference Preference, 136 DenseSet<Value *> &RecursionSet, Instruction *CxtI = nullptr); 137 bool 138 computeValueKnownInPredecessors(Value *V, BasicBlock *BB, 139 jumpthreading::PredValueInfo &Result, 140 jumpthreading::ConstantPreference Preference, 141 Instruction *CxtI = nullptr) { 142 DenseSet<Value *> RecursionSet; 143 return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference, 144 RecursionSet, CxtI); 145 } 146 147 Constant *evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, 148 Value *cond); 149 bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond); 150 void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, 151 BasicBlock *BB, BasicBlock *SuccBB); 152 bool processThreadableEdges(Value *Cond, BasicBlock *BB, 153 jumpthreading::ConstantPreference Preference, 154 Instruction *CxtI = nullptr); 155 156 bool processBranchOnPHI(PHINode *PN); 157 bool processBranchOnXOR(BinaryOperator *BO); 158 bool processImpliedCondition(BasicBlock *BB); 159 160 bool simplifyPartiallyRedundantLoad(LoadInst *LI); 161 void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, 162 PHINode *SIUse, unsigned Idx); 163 164 bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); 165 bool tryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB); 166 bool tryToUnfoldSelectInCurrBB(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 183