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/DomTreeUpdater.h"
27 #include "llvm/IR/ValueHandle.h"
28 #include <memory>
29 #include <utility>
30 
31 namespace llvm {
32 
33 class BasicBlock;
34 class BinaryOperator;
35 class BranchInst;
36 class CmpInst;
37 class Constant;
38 class DomTreeUpdater;
39 class Function;
40 class Instruction;
41 class IntrinsicInst;
42 class LazyValueInfo;
43 class LoadInst;
44 class PHINode;
45 class TargetLibraryInfo;
46 class Value;
47 
48 /// A private "module" namespace for types and utilities used by
49 /// JumpThreading.
50 /// These are implementation details and should not be used by clients.
51 namespace jumpthreading {
52 
53 // These are at global scope so static functions can use them too.
54 using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>;
55 using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>;
56 
57 // This is used to keep track of what kind of constant we're currently hoping
58 // to find.
59 enum ConstantPreference { WantInteger, WantBlockAddress };
60 
61 } // end namespace jumpthreading
62 
63 /// This pass performs 'jump threading', which looks at blocks that have
64 /// multiple predecessors and multiple successors.  If one or more of the
65 /// predecessors of the block can be proven to always jump to one of the
66 /// successors, we forward the edge from the predecessor to the successor by
67 /// duplicating the contents of this block.
68 ///
69 /// An example of when this can occur is code like this:
70 ///
71 ///   if () { ...
72 ///     X = 4;
73 ///   }
74 ///   if (X < 3) {
75 ///
76 /// In this case, the unconditional branch at the end of the first if can be
77 /// revectored to the false side of the second if.
78 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
79   TargetLibraryInfo *TLI;
80   LazyValueInfo *LVI;
81   AliasAnalysis *AA;
82   DomTreeUpdater *DTU;
83   std::unique_ptr<BlockFrequencyInfo> BFI;
84   std::unique_ptr<BranchProbabilityInfo> BPI;
85   bool HasProfileData = false;
86   bool HasGuards = false;
87 #ifdef NDEBUG
88   SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
89 #else
90   SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
91 #endif
92 
93   unsigned BBDupThreshold;
94 
95 public:
96   JumpThreadingPass(int T = -1);
97 
98   // Glue for old PM.
99   bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_,
100                AliasAnalysis *AA_, DomTreeUpdater *DTU_, bool HasProfileData_,
101                std::unique_ptr<BlockFrequencyInfo> BFI_,
102                std::unique_ptr<BranchProbabilityInfo> BPI_);
103 
104   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
105 
releaseMemory()106   void releaseMemory() {
107     BFI.reset();
108     BPI.reset();
109   }
110 
111   void FindLoopHeaders(Function &F);
112   bool ProcessBlock(BasicBlock *BB);
113   bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
114                   BasicBlock *SuccBB);
115   bool DuplicateCondBranchOnPHIIntoPred(
116       BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
117 
118   bool ComputeValueKnownInPredecessorsImpl(
119       Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
120       jumpthreading::ConstantPreference Preference,
121       DenseSet<std::pair<Value *, BasicBlock *>> &RecursionSet,
122       Instruction *CxtI = nullptr);
123   bool
124   ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
125                                   jumpthreading::PredValueInfo &Result,
126                                   jumpthreading::ConstantPreference Preference,
127                                   Instruction *CxtI = nullptr) {
128     DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet;
129     return ComputeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
130                                                RecursionSet, CxtI);
131   }
132 
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   void UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI,
143                          PHINode *SIUse, unsigned Idx);
144 
145   bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
146   bool TryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB);
147   bool TryToUnfoldSelectInCurrBB(BasicBlock *BB);
148 
149   bool ProcessGuards(BasicBlock *BB);
150   bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
151 
152 private:
153   BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
154                               const char *Suffix);
155   void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
156                                     BasicBlock *NewBB, BasicBlock *SuccBB);
157   /// Check if the block has profile metadata for its outgoing edges.
158   bool doesBlockHaveProfileData(BasicBlock *BB);
159 };
160 
161 } // end namespace llvm
162 
163 #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
164