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 /// \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/DenseSet.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/SmallSet.h" 20 #include "llvm/Analysis/BlockFrequencyInfo.h" 21 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 22 #include "llvm/Analysis/BranchProbabilityInfo.h" 23 #include "llvm/Analysis/LazyValueInfo.h" 24 #include "llvm/Analysis/TargetLibraryInfo.h" 25 #include "llvm/IR/Instructions.h" 26 #include "llvm/IR/ValueHandle.h" 27 28 namespace llvm { 29 30 /// A private "module" namespace for types and utilities used by 31 /// JumpThreading. 32 /// These are implementation details and should not be used by clients. 33 namespace jumpthreading { 34 // These are at global scope so static functions can use them too. 35 typedef SmallVectorImpl<std::pair<Constant *, BasicBlock *>> PredValueInfo; 36 typedef SmallVector<std::pair<Constant *, BasicBlock *>, 8> PredValueInfoTy; 37 38 // This is used to keep track of what kind of constant we're currently hoping 39 // to find. 40 enum ConstantPreference { WantInteger, WantBlockAddress }; 41 } 42 43 /// This pass performs 'jump threading', which looks at blocks that have 44 /// multiple predecessors and multiple successors. If one or more of the 45 /// predecessors of the block can be proven to always jump to one of the 46 /// successors, we forward the edge from the predecessor to the successor by 47 /// duplicating the contents of this block. 48 /// 49 /// An example of when this can occur is code like this: 50 /// 51 /// if () { ... 52 /// X = 4; 53 /// } 54 /// if (X < 3) { 55 /// 56 /// In this case, the unconditional branch at the end of the first if can be 57 /// revectored to the false side of the second if. 58 /// 59 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> { 60 TargetLibraryInfo *TLI; 61 LazyValueInfo *LVI; 62 std::unique_ptr<BlockFrequencyInfo> BFI; 63 std::unique_ptr<BranchProbabilityInfo> BPI; 64 bool HasProfileData = false; 65 #ifdef NDEBUG 66 SmallPtrSet<const BasicBlock *, 16> LoopHeaders; 67 #else 68 SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders; 69 #endif 70 DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet; 71 72 unsigned BBDupThreshold; 73 74 // RAII helper for updating the recursion stack. 75 struct RecursionSetRemover { 76 DenseSet<std::pair<Value *, BasicBlock *>> &TheSet; 77 std::pair<Value *, BasicBlock *> ThePair; 78 RecursionSetRemoverRecursionSetRemover79 RecursionSetRemover(DenseSet<std::pair<Value *, BasicBlock *>> &S, 80 std::pair<Value *, BasicBlock *> P) 81 : TheSet(S), ThePair(P) {} 82 ~RecursionSetRemoverRecursionSetRemover83 ~RecursionSetRemover() { TheSet.erase(ThePair); } 84 }; 85 86 public: 87 JumpThreadingPass(int T = -1); 88 // Hack for MSVC 2013 which seems like it can't synthesize this. JumpThreadingPass(JumpThreadingPass && Other)89 JumpThreadingPass(JumpThreadingPass &&Other) 90 : TLI(Other.TLI), LVI(Other.LVI), BFI(std::move(Other.BFI)), 91 BPI(std::move(Other.BPI)), HasProfileData(Other.HasProfileData), 92 LoopHeaders(std::move(Other.LoopHeaders)), 93 RecursionSet(std::move(Other.RecursionSet)), 94 BBDupThreshold(Other.BBDupThreshold) {} 95 96 // Glue for old PM. 97 bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_, 98 bool HasProfileData_, std::unique_ptr<BlockFrequencyInfo> BFI_, 99 std::unique_ptr<BranchProbabilityInfo> BPI_); 100 101 PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); 102 releaseMemory()103 void releaseMemory() { 104 BFI.reset(); 105 BPI.reset(); 106 } 107 108 void FindLoopHeaders(Function &F); 109 bool ProcessBlock(BasicBlock *BB); 110 bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs, 111 BasicBlock *SuccBB); 112 bool DuplicateCondBranchOnPHIIntoPred( 113 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs); 114 115 bool 116 ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, 117 jumpthreading::PredValueInfo &Result, 118 jumpthreading::ConstantPreference Preference, 119 Instruction *CxtI = nullptr); 120 bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB, 121 jumpthreading::ConstantPreference Preference, 122 Instruction *CxtI = nullptr); 123 124 bool ProcessBranchOnPHI(PHINode *PN); 125 bool ProcessBranchOnXOR(BinaryOperator *BO); 126 bool ProcessImpliedCondition(BasicBlock *BB); 127 128 bool SimplifyPartiallyRedundantLoad(LoadInst *LI); 129 bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); 130 bool TryToUnfoldSelectInCurrBB(BasicBlock *BB); 131 132 private: 133 BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 134 const char *Suffix); 135 void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB, 136 BasicBlock *NewBB, BasicBlock *SuccBB); 137 }; 138 139 } // end namespace llvm 140 141 #endif 142