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/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" 27 #include <memory> 28 #include <utility> 29 30 namespace llvm { 31 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 TargetLibraryInfo; 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 LazyValueInfo *LVI; 80 AliasAnalysis *AA; 81 DomTreeUpdater *DTU; 82 std::unique_ptr<BlockFrequencyInfo> BFI; 83 std::unique_ptr<BranchProbabilityInfo> BPI; 84 bool HasProfileData = false; 85 bool HasGuards = false; 86 #ifdef NDEBUG 87 SmallPtrSet<const BasicBlock *, 16> LoopHeaders; 88 #else 89 SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders; 90 #endif 91 92 unsigned BBDupThreshold; 93 94 public: 95 JumpThreadingPass(int T = -1); 96 97 // Glue for old PM. 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_); 102 103 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 104 105 void releaseMemory() { 106 BFI.reset(); 107 BPI.reset(); 108 } 109 110 void FindLoopHeaders(Function &F); 111 bool ProcessBlock(BasicBlock *BB); 112 bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs, 113 BasicBlock *SuccBB); 114 bool DuplicateCondBranchOnPHIIntoPred( 115 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs); 116 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); 122 bool 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, 129 RecursionSet, CxtI); 130 } 131 132 bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB, 133 jumpthreading::ConstantPreference Preference, 134 Instruction *CxtI = nullptr); 135 136 bool ProcessBranchOnPHI(PHINode *PN); 137 bool ProcessBranchOnXOR(BinaryOperator *BO); 138 bool ProcessImpliedCondition(BasicBlock *BB); 139 140 bool SimplifyPartiallyRedundantLoad(LoadInst *LI); 141 void UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, 142 PHINode *SIUse, unsigned Idx); 143 144 bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); 145 bool TryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB); 146 bool TryToUnfoldSelectInCurrBB(BasicBlock *BB); 147 148 bool ProcessGuards(BasicBlock *BB); 149 bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI); 150 151 private: 152 BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 153 const char *Suffix); 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); 158 }; 159 160 } // end namespace llvm 161 162 #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H 163