1303231Sdim//===- JumpThreading.h - thread control through conditional BBs -*- C++ -*-===// 2303231Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6303231Sdim// 7303231Sdim//===----------------------------------------------------------------------===// 8327952Sdim// 9303231Sdim/// \file 10303231Sdim/// See the comments on JumpThreadingPass. 11327952Sdim// 12303231Sdim//===----------------------------------------------------------------------===// 13303231Sdim 14303231Sdim#ifndef LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H 15303231Sdim#define LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H 16303231Sdim 17327952Sdim#include "llvm/ADT/ArrayRef.h" 18303231Sdim#include "llvm/ADT/DenseSet.h" 19303231Sdim#include "llvm/ADT/SmallPtrSet.h" 20303231Sdim#include "llvm/ADT/SmallSet.h" 21327952Sdim#include "llvm/ADT/SmallVector.h" 22321369Sdim#include "llvm/Analysis/AliasAnalysis.h" 23303231Sdim#include "llvm/Analysis/BlockFrequencyInfo.h" 24303231Sdim#include "llvm/Analysis/BranchProbabilityInfo.h" 25353358Sdim#include "llvm/Analysis/DomTreeUpdater.h" 26303231Sdim#include "llvm/IR/ValueHandle.h" 27327952Sdim#include <memory> 28327952Sdim#include <utility> 29303231Sdim 30303231Sdimnamespace llvm { 31303231Sdim 32327952Sdimclass BasicBlock; 33327952Sdimclass BinaryOperator; 34327952Sdimclass BranchInst; 35327952Sdimclass CmpInst; 36327952Sdimclass Constant; 37344779Sdimclass DomTreeUpdater; 38327952Sdimclass Function; 39327952Sdimclass Instruction; 40327952Sdimclass IntrinsicInst; 41327952Sdimclass LazyValueInfo; 42327952Sdimclass LoadInst; 43327952Sdimclass PHINode; 44327952Sdimclass TargetLibraryInfo; 45327952Sdimclass Value; 46327952Sdim 47303231Sdim/// A private "module" namespace for types and utilities used by 48303231Sdim/// JumpThreading. 49303231Sdim/// These are implementation details and should not be used by clients. 50303231Sdimnamespace jumpthreading { 51327952Sdim 52303231Sdim// These are at global scope so static functions can use them too. 53327952Sdimusing PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>; 54327952Sdimusing PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>; 55303231Sdim 56303231Sdim// This is used to keep track of what kind of constant we're currently hoping 57303231Sdim// to find. 58303231Sdimenum ConstantPreference { WantInteger, WantBlockAddress }; 59303231Sdim 60327952Sdim} // end namespace jumpthreading 61327952Sdim 62303231Sdim/// This pass performs 'jump threading', which looks at blocks that have 63303231Sdim/// multiple predecessors and multiple successors. If one or more of the 64303231Sdim/// predecessors of the block can be proven to always jump to one of the 65303231Sdim/// successors, we forward the edge from the predecessor to the successor by 66303231Sdim/// duplicating the contents of this block. 67303231Sdim/// 68303231Sdim/// An example of when this can occur is code like this: 69303231Sdim/// 70303231Sdim/// if () { ... 71303231Sdim/// X = 4; 72303231Sdim/// } 73303231Sdim/// if (X < 3) { 74303231Sdim/// 75303231Sdim/// In this case, the unconditional branch at the end of the first if can be 76303231Sdim/// revectored to the false side of the second if. 77303231Sdimclass JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> { 78303231Sdim TargetLibraryInfo *TLI; 79303231Sdim LazyValueInfo *LVI; 80321369Sdim AliasAnalysis *AA; 81344779Sdim DomTreeUpdater *DTU; 82303231Sdim std::unique_ptr<BlockFrequencyInfo> BFI; 83303231Sdim std::unique_ptr<BranchProbabilityInfo> BPI; 84303231Sdim bool HasProfileData = false; 85321369Sdim bool HasGuards = false; 86303231Sdim#ifdef NDEBUG 87303231Sdim SmallPtrSet<const BasicBlock *, 16> LoopHeaders; 88303231Sdim#else 89303231Sdim SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders; 90303231Sdim#endif 91303231Sdim 92303231Sdim unsigned BBDupThreshold; 93303231Sdim 94303231Sdimpublic: 95303231Sdim JumpThreadingPass(int T = -1); 96303231Sdim 97303231Sdim // Glue for old PM. 98303231Sdim bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_, 99344779Sdim AliasAnalysis *AA_, DomTreeUpdater *DTU_, bool HasProfileData_, 100344779Sdim std::unique_ptr<BlockFrequencyInfo> BFI_, 101303231Sdim std::unique_ptr<BranchProbabilityInfo> BPI_); 102303231Sdim 103314564Sdim PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 104303231Sdim 105303231Sdim void releaseMemory() { 106303231Sdim BFI.reset(); 107303231Sdim BPI.reset(); 108303231Sdim } 109303231Sdim 110303231Sdim void FindLoopHeaders(Function &F); 111303231Sdim bool ProcessBlock(BasicBlock *BB); 112360784Sdim bool MaybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB); 113360784Sdim void UpdateSSA(BasicBlock *BB, BasicBlock *NewBB, 114360784Sdim DenseMap<Instruction *, Value *> &ValueMapping); 115360784Sdim DenseMap<Instruction *, Value *> CloneInstructions(BasicBlock::iterator BI, 116360784Sdim BasicBlock::iterator BE, 117360784Sdim BasicBlock *NewBB, 118360784Sdim BasicBlock *PredBB); 119360784Sdim bool TryThreadEdge(BasicBlock *BB, 120360784Sdim const SmallVectorImpl<BasicBlock *> &PredBBs, 121360784Sdim BasicBlock *SuccBB); 122360784Sdim void ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs, 123303231Sdim BasicBlock *SuccBB); 124303231Sdim bool DuplicateCondBranchOnPHIIntoPred( 125303231Sdim BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs); 126303231Sdim 127344779Sdim bool ComputeValueKnownInPredecessorsImpl( 128344779Sdim Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, 129344779Sdim jumpthreading::ConstantPreference Preference, 130344779Sdim DenseSet<std::pair<Value *, BasicBlock *>> &RecursionSet, 131344779Sdim Instruction *CxtI = nullptr); 132303231Sdim bool 133303231Sdim ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, 134303231Sdim jumpthreading::PredValueInfo &Result, 135303231Sdim jumpthreading::ConstantPreference Preference, 136344779Sdim Instruction *CxtI = nullptr) { 137344779Sdim DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet; 138344779Sdim return ComputeValueKnownInPredecessorsImpl(V, BB, Result, Preference, 139344779Sdim RecursionSet, CxtI); 140344779Sdim } 141344779Sdim 142303231Sdim bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB, 143303231Sdim jumpthreading::ConstantPreference Preference, 144303231Sdim Instruction *CxtI = nullptr); 145303231Sdim 146303231Sdim bool ProcessBranchOnPHI(PHINode *PN); 147303231Sdim bool ProcessBranchOnXOR(BinaryOperator *BO); 148303231Sdim bool ProcessImpliedCondition(BasicBlock *BB); 149303231Sdim 150303231Sdim bool SimplifyPartiallyRedundantLoad(LoadInst *LI); 151344779Sdim void UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, 152344779Sdim PHINode *SIUse, unsigned Idx); 153344779Sdim 154303231Sdim bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); 155344779Sdim bool TryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB); 156303231Sdim bool TryToUnfoldSelectInCurrBB(BasicBlock *BB); 157303231Sdim 158321369Sdim bool ProcessGuards(BasicBlock *BB); 159321369Sdim bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI); 160321369Sdim 161303231Sdimprivate: 162303231Sdim BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 163303231Sdim const char *Suffix); 164303231Sdim void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB, 165303231Sdim BasicBlock *NewBB, BasicBlock *SuccBB); 166314564Sdim /// Check if the block has profile metadata for its outgoing edges. 167314564Sdim bool doesBlockHaveProfileData(BasicBlock *BB); 168303231Sdim}; 169303231Sdim 170303231Sdim} // end namespace llvm 171303231Sdim 172327952Sdim#endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H 173