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