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/SmallSet.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/Analysis/BlockFrequencyInfo.h"
22#include "llvm/Analysis/BranchProbabilityInfo.h"
23#include "llvm/Analysis/DomTreeUpdater.h"
24#include "llvm/IR/ValueHandle.h"
25#include "llvm/Support/Compiler.h"
26#include "llvm/Transforms/Utils/ValueMapper.h"
27#include <utility>
28
29namespace llvm {
30
31class AAResults;
32class BasicBlock;
33class BinaryOperator;
34class CondBrInst;
35class CmpInst;
36class Constant;
37class Function;
38class Instruction;
39class IntrinsicInst;
40class LazyValueInfo;
41class LoadInst;
42class PHINode;
43struct ScalarOptions;
44class SelectInst;
45class SwitchInst;
46class TargetLibraryInfo;
47class TargetTransformInfo;
48class Value;
49
50/// A private "module" namespace for types and utilities used by
51/// JumpThreading.
52/// These are implementation details and should not be used by clients.
53namespace jumpthreading {
54
55// These are at global scope so static functions can use them too.
56using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>;
57using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>;
58
59// This is used to keep track of what kind of constant we're currently hoping
60// to find.
61enum ConstantPreference { WantInteger, WantBlockAddress };
62
63} // end namespace jumpthreading
64
65/// This pass performs 'jump threading', which looks at blocks that have
66/// multiple predecessors and multiple successors. If one or more of the
67/// predecessors of the block can be proven to always jump to one of the
68/// successors, we forward the edge from the predecessor to the successor by
69/// duplicating the contents of this block.
70///
71/// An example of when this can occur is code like this:
72///
73/// if () { ...
74/// X = 4;
75/// }
76/// if (X < 3) {
77///
78/// In this case, the unconditional branch at the end of the first if can be
79/// revectored to the false side of the second if.
80class JumpThreadingPass : public OptionalPassInfoMixin<JumpThreadingPass> {
81 const ScalarOptions *Opts = nullptr;
82 Function *F = nullptr;
83 FunctionAnalysisManager *FAM = nullptr;
84 TargetLibraryInfo *TLI = nullptr;
85 TargetTransformInfo *TTI = nullptr;
86 LazyValueInfo *LVI = nullptr;
87 AAResults *AA = nullptr;
88 std::unique_ptr<DomTreeUpdater> DTU;
89 BlockFrequencyInfo *BFI = nullptr;
90 BranchProbabilityInfo *BPI = nullptr;
91 bool ChangedSinceLastAnalysisUpdate = false;
92 bool HasGuards = false;
93#ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS
94 SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
95#else
96 SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
97#endif
98
99 // JumpThreading must not processes blocks unreachable from entry. It's a
100 // waste of compute time and can potentially lead to hangs.
101 SmallPtrSet<BasicBlock *, 16> Unreachable;
102
103 unsigned BBDupThreshold;
104 unsigned DefaultBBDupThreshold;
105
106public:
107 LLVM_ABI JumpThreadingPass(int T = -1);
108
109 // Glue for old PM.
110 LLVM_ABI bool runImpl(Function &F, FunctionAnalysisManager *FAM,
111 TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
112 LazyValueInfo *LVI, AAResults *AA,
113 std::unique_ptr<DomTreeUpdater> DTU,
114 BlockFrequencyInfo *BFI, BranchProbabilityInfo *BPI);
115
116 LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
117
118 DomTreeUpdater *getDomTreeUpdater() const { return DTU.get(); }
119 LLVM_ABI void findLoopHeaders(Function &F);
120 LLVM_ABI bool processBlock(BasicBlock *BB);
121 LLVM_ABI bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB);
122 LLVM_ABI void updateSSA(BasicBlock *BB, BasicBlock *NewBB,
123 ValueToValueMapTy &ValueMapping);
124 LLVM_ABI void cloneInstructions(ValueToValueMapTy &ValueMapping,
125 BasicBlock::iterator BI,
126 BasicBlock::iterator BE, BasicBlock *NewBB,
127 BasicBlock *PredBB);
128 LLVM_ABI bool tryThreadEdge(BasicBlock *BB,
129 const SmallVectorImpl<BasicBlock *> &PredBBs,
130 BasicBlock *SuccBB);
131 LLVM_ABI void threadEdge(BasicBlock *BB,
132 const SmallVectorImpl<BasicBlock *> &PredBBs,
133 BasicBlock *SuccBB);
134 LLVM_ABI bool duplicateCondBranchOnPHIIntoPred(
135 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
136
137 LLVM_ABI bool computeValueKnownInPredecessorsImpl(
138 Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
139 jumpthreading::ConstantPreference Preference,
140 SmallPtrSet<Value *, 4> &RecursionSet, Instruction *CtxI = nullptr);
141 bool
142 computeValueKnownInPredecessors(Value *V, BasicBlock *BB,
143 jumpthreading::PredValueInfo &Result,
144 jumpthreading::ConstantPreference Preference,
145 Instruction *CtxI = nullptr) {
146 SmallPtrSet<Value *, 4> RecursionSet;
147 return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
148 RecursionSet, CtxI);
149 }
150
151 LLVM_ABI Constant *evaluateOnPredecessorEdge(BasicBlock *BB,
152 BasicBlock *PredPredBB,
153 Value *cond,
154 const DataLayout &DL);
155 LLVM_ABI bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond);
156 LLVM_ABI void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB,
157 BasicBlock *PredBB, BasicBlock *BB,
158 BasicBlock *SuccBB);
159 LLVM_ABI bool
160 processThreadableEdges(Value *Cond, BasicBlock *BB,
161 jumpthreading::ConstantPreference Preference,
162 Instruction *CtxI = nullptr);
163
164 LLVM_ABI bool processBranchOnPHI(PHINode *PN);
165 LLVM_ABI bool processBranchOnXOR(BinaryOperator *BO);
166 LLVM_ABI bool processImpliedCondition(BasicBlock *BB);
167
168 LLVM_ABI bool simplifyPartiallyRedundantLoad(LoadInst *LI);
169 LLVM_ABI void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB,
170 SelectInst *SI, PHINode *SIUse, unsigned Idx);
171
172 LLVM_ABI bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
173 LLVM_ABI bool tryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB);
174 LLVM_ABI bool tryToUnfoldSelectInCurrBB(BasicBlock *BB);
175
176 LLVM_ABI bool processGuards(BasicBlock *BB);
177 LLVM_ABI bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard,
178 CondBrInst *BI);
179
180private:
181 BasicBlock *splitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
182 const char *Suffix);
183 void updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
184 BasicBlock *NewBB, BasicBlock *SuccBB,
185 BlockFrequencyInfo *BFI,
186 BranchProbabilityInfo *BPI,
187 bool HasProfile);
188 /// Check if the block has profile metadata for its outgoing edges.
189 bool doesBlockHaveProfileData(BasicBlock *BB);
190
191 /// Returns analysis preserved by the pass.
192 PreservedAnalyses getPreservedAnalysis() const;
193
194 /// Helper function to run "external" analysis in the middle of JumpThreading.
195 /// It takes care of updating/invalidating other existing analysis
196 /// before/after running the "external" one.
197 template <typename AnalysisT>
198 typename AnalysisT::Result *runExternalAnalysis();
199
200 /// Returns an existing instance of BPI if any, otherwise nullptr. By
201 /// "existing" we mean either cached result provided by FunctionAnalysisManger
202 /// or created by preceding call to 'getOrCreateBPI'.
203 BranchProbabilityInfo *getBPI();
204
205 /// Returns an existing instance of BFI if any, otherwise nullptr. By
206 /// "existing" we mean either cached result provided by FunctionAnalysisManger
207 /// or created by preceding call to 'getOrCreateBFI'.
208 BlockFrequencyInfo *getBFI();
209
210 /// Returns an existing instance of BPI if any, otherwise:
211 /// if 'HasProfile' is true creates new instance through
212 /// FunctionAnalysisManager, otherwise nullptr.
213 BranchProbabilityInfo *getOrCreateBPI(bool Force = false);
214
215 /// Returns an existing instance of BFI if any, otherwise:
216 /// if 'HasProfile' is true creates new instance through
217 /// FunctionAnalysisManager, otherwise nullptr.
218 BlockFrequencyInfo *getOrCreateBFI(bool Force = false);
219
220 // Internal overload of evaluateOnPredecessorEdge().
221 Constant *evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB,
222 Value *cond, const DataLayout &DL,
223 SmallPtrSet<Value *, 8> &Visited);
224};
225
226} // end namespace llvm
227
228#endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
229