1 //===- JumpThreading.h - thread control through conditional BBs -*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 /// \file 11 /// See the comments on JumpThreadingPass. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H 16 #define LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H 17 18 #include "llvm/ADT/ArrayRef.h" 19 #include "llvm/ADT/DenseSet.h" 20 #include "llvm/ADT/SmallPtrSet.h" 21 #include "llvm/ADT/SmallSet.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/Analysis/AliasAnalysis.h" 24 #include "llvm/Analysis/BlockFrequencyInfo.h" 25 #include "llvm/Analysis/BranchProbabilityInfo.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 Function; 38 class Instruction; 39 class IntrinsicInst; 40 class LazyValueInfo; 41 class LoadInst; 42 class PHINode; 43 class TargetLibraryInfo; 44 class Value; 45 46 /// A private "module" namespace for types and utilities used by 47 /// JumpThreading. 48 /// These are implementation details and should not be used by clients. 49 namespace jumpthreading { 50 51 // These are at global scope so static functions can use them too. 52 using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>; 53 using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>; 54 55 // This is used to keep track of what kind of constant we're currently hoping 56 // to find. 57 enum ConstantPreference { WantInteger, WantBlockAddress }; 58 59 } // end namespace jumpthreading 60 61 /// This pass performs 'jump threading', which looks at blocks that have 62 /// multiple predecessors and multiple successors. If one or more of the 63 /// predecessors of the block can be proven to always jump to one of the 64 /// successors, we forward the edge from the predecessor to the successor by 65 /// duplicating the contents of this block. 66 /// 67 /// An example of when this can occur is code like this: 68 /// 69 /// if () { ... 70 /// X = 4; 71 /// } 72 /// if (X < 3) { 73 /// 74 /// In this case, the unconditional branch at the end of the first if can be 75 /// revectored to the false side of the second if. 76 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> { 77 TargetLibraryInfo *TLI; 78 LazyValueInfo *LVI; 79 AliasAnalysis *AA; 80 std::unique_ptr<BlockFrequencyInfo> BFI; 81 std::unique_ptr<BranchProbabilityInfo> BPI; 82 bool HasProfileData = false; 83 bool HasGuards = false; 84 #ifdef NDEBUG 85 SmallPtrSet<const BasicBlock *, 16> LoopHeaders; 86 #else 87 SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders; 88 #endif 89 DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet; 90 91 unsigned BBDupThreshold; 92 93 // RAII helper for updating the recursion stack. 94 struct RecursionSetRemover { 95 DenseSet<std::pair<Value *, BasicBlock *>> &TheSet; 96 std::pair<Value *, BasicBlock *> ThePair; 97 98 RecursionSetRemover(DenseSet<std::pair<Value *, BasicBlock *>> &S, 99 std::pair<Value *, BasicBlock *> P) 100 : TheSet(S), ThePair(P) {} 101 102 ~RecursionSetRemover() { TheSet.erase(ThePair); } 103 }; 104 105 public: 106 JumpThreadingPass(int T = -1); 107 108 // Glue for old PM. 109 bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_, 110 AliasAnalysis *AA_, bool HasProfileData_, 111 std::unique_ptr<BlockFrequencyInfo> BFI_, 112 std::unique_ptr<BranchProbabilityInfo> BPI_); 113 114 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 115 116 void releaseMemory() { 117 BFI.reset(); 118 BPI.reset(); 119 } 120 121 void FindLoopHeaders(Function &F); 122 bool ProcessBlock(BasicBlock *BB); 123 bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs, 124 BasicBlock *SuccBB); 125 bool DuplicateCondBranchOnPHIIntoPred( 126 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs); 127 128 bool 129 ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, 130 jumpthreading::PredValueInfo &Result, 131 jumpthreading::ConstantPreference Preference, 132 Instruction *CxtI = nullptr); 133 bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB, 134 jumpthreading::ConstantPreference Preference, 135 Instruction *CxtI = nullptr); 136 137 bool ProcessBranchOnPHI(PHINode *PN); 138 bool ProcessBranchOnXOR(BinaryOperator *BO); 139 bool ProcessImpliedCondition(BasicBlock *BB); 140 141 bool SimplifyPartiallyRedundantLoad(LoadInst *LI); 142 bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); 143 bool TryToUnfoldSelectInCurrBB(BasicBlock *BB); 144 145 bool ProcessGuards(BasicBlock *BB); 146 bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI); 147 148 private: 149 BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 150 const char *Suffix); 151 void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB, 152 BasicBlock *NewBB, BasicBlock *SuccBB); 153 /// Check if the block has profile metadata for its outgoing edges. 154 bool doesBlockHaveProfileData(BasicBlock *BB); 155 }; 156 157 } // end namespace llvm 158 159 #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H 160
