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   unsigned DefaultBBDupThreshold;
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 MaybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB);
114   void UpdateSSA(BasicBlock *BB, BasicBlock *NewBB,
115                  DenseMap<Instruction *, Value *> &ValueMapping);
116   DenseMap<Instruction *, Value *> CloneInstructions(BasicBlock::iterator BI,
117                                                      BasicBlock::iterator BE,
118                                                      BasicBlock *NewBB,
119                                                      BasicBlock *PredBB);
120   bool TryThreadEdge(BasicBlock *BB,
121                      const SmallVectorImpl<BasicBlock *> &PredBBs,
122                      BasicBlock *SuccBB);
123   void ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
124                   BasicBlock *SuccBB);
125   bool DuplicateCondBranchOnPHIIntoPred(
126       BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
127 
128   bool ComputeValueKnownInPredecessorsImpl(
129       Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
130       jumpthreading::ConstantPreference Preference,
131       DenseSet<Value *> &RecursionSet, Instruction *CxtI = nullptr);
132   bool
133   ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
134                                   jumpthreading::PredValueInfo &Result,
135                                   jumpthreading::ConstantPreference Preference,
136                                   Instruction *CxtI = nullptr) {
137     DenseSet<Value *> RecursionSet;
138     return ComputeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
139                                                RecursionSet, CxtI);
140   }
141 
142   Constant *EvaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB,
143                                       Value *cond);
144   bool MaybeThreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond);
145   void ThreadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB,
146                                    BasicBlock *BB, BasicBlock *SuccBB);
147   bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
148                               jumpthreading::ConstantPreference Preference,
149                               Instruction *CxtI = nullptr);
150 
151   bool ProcessBranchOnPHI(PHINode *PN);
152   bool ProcessBranchOnXOR(BinaryOperator *BO);
153   bool ProcessImpliedCondition(BasicBlock *BB);
154 
155   bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
156   void UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI,
157                          PHINode *SIUse, unsigned Idx);
158 
159   bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
160   bool TryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB);
161   bool TryToUnfoldSelectInCurrBB(BasicBlock *BB);
162 
163   bool ProcessGuards(BasicBlock *BB);
164   bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
165 
166 private:
167   BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
168                               const char *Suffix);
169   void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
170                                     BasicBlock *NewBB, BasicBlock *SuccBB);
171   /// Check if the block has profile metadata for its outgoing edges.
172   bool doesBlockHaveProfileData(BasicBlock *BB);
173 };
174 
175 } // end namespace llvm
176 
177 #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
178