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 <optional>
26#include <utility>
27
28namespace llvm {
29
30class AAResults;
31class BasicBlock;
32class BinaryOperator;
33class BranchInst;
34class CmpInst;
35class Constant;
36class Function;
37class Instruction;
38class IntrinsicInst;
39class LazyValueInfo;
40class LoadInst;
41class PHINode;
42class SelectInst;
43class SwitchInst;
44class TargetLibraryInfo;
45class TargetTransformInfo;
46class 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.
51namespace jumpthreading {
52
53// These are at global scope so static functions can use them too.
54using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>;
55using 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.
59enum 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.
78class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
79 Function *F = nullptr;
80 FunctionAnalysisManager *FAM = nullptr;
81 TargetLibraryInfo *TLI = nullptr;
82 TargetTransformInfo *TTI = nullptr;
83 LazyValueInfo *LVI = nullptr;
84 AAResults *AA = nullptr;
85 std::unique_ptr<DomTreeUpdater> DTU;
86 std::optional<BlockFrequencyInfo *> BFI;
87 std::optional<BranchProbabilityInfo *> BPI;
88 bool ChangedSinceLastAnalysisUpdate = false;
89 bool HasGuards = false;
90#ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS
91 SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
92#else
93 SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
94#endif
95
96 unsigned BBDupThreshold;
97 unsigned DefaultBBDupThreshold;
98
99public:
100 JumpThreadingPass(int T = -1);
101
102 // Glue for old PM.
103 bool runImpl(Function &F, FunctionAnalysisManager *FAM,
104 TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
105 LazyValueInfo *LVI, AAResults *AA,
106 std::unique_ptr<DomTreeUpdater> DTU,
107 std::optional<BlockFrequencyInfo *> BFI,
108 std::optional<BranchProbabilityInfo *> BPI);
109
110 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
111
112 DomTreeUpdater *getDomTreeUpdater() const { return DTU.get(); }
113 void findLoopHeaders(Function &F);
114 bool processBlock(BasicBlock *BB);
115 bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB);
116 void updateSSA(BasicBlock *BB, BasicBlock *NewBB,
117 DenseMap<Instruction *, Value *> &ValueMapping);
118 DenseMap<Instruction *, Value *> cloneInstructions(BasicBlock::iterator BI,
119 BasicBlock::iterator BE,
120 BasicBlock *NewBB,
121 BasicBlock *PredBB);
122 bool tryThreadEdge(BasicBlock *BB,
123 const SmallVectorImpl<BasicBlock *> &PredBBs,
124 BasicBlock *SuccBB);
125 void threadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
126 BasicBlock *SuccBB);
127 bool duplicateCondBranchOnPHIIntoPred(
128 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
129
130 bool computeValueKnownInPredecessorsImpl(
131 Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
132 jumpthreading::ConstantPreference Preference,
133 DenseSet<Value *> &RecursionSet, Instruction *CxtI = nullptr);
134 bool
135 computeValueKnownInPredecessors(Value *V, BasicBlock *BB,
136 jumpthreading::PredValueInfo &Result,
137 jumpthreading::ConstantPreference Preference,
138 Instruction *CxtI = nullptr) {
139 DenseSet<Value *> RecursionSet;
140 return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
141 RecursionSet, CxtI);
142 }
143
144 Constant *evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB,
145 Value *cond);
146 bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond);
147 void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB,
148 BasicBlock *BB, BasicBlock *SuccBB);
149 bool processThreadableEdges(Value *Cond, BasicBlock *BB,
150 jumpthreading::ConstantPreference Preference,
151 Instruction *CxtI = nullptr);
152
153 bool processBranchOnPHI(PHINode *PN);
154 bool processBranchOnXOR(BinaryOperator *BO);
155 bool processImpliedCondition(BasicBlock *BB);
156
157 bool simplifyPartiallyRedundantLoad(LoadInst *LI);
158 void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI,
159 PHINode *SIUse, unsigned Idx);
160
161 bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
162 bool tryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB);
163 bool tryToUnfoldSelectInCurrBB(BasicBlock *BB);
164
165 bool processGuards(BasicBlock *BB);
166 bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
167
168private:
169 BasicBlock *splitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
170 const char *Suffix);
171 void updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
172 BasicBlock *NewBB, BasicBlock *SuccBB,
173 BlockFrequencyInfo *BFI,
174 BranchProbabilityInfo *BPI,
175 bool HasProfile);
176 /// Check if the block has profile metadata for its outgoing edges.
177 bool doesBlockHaveProfileData(BasicBlock *BB);
178
179 /// Returns analysis preserved by the pass.
180 PreservedAnalyses getPreservedAnalysis() const;
181
182 /// Helper function to run "external" analysis in the middle of JumpThreading.
183 /// It takes care of updating/invalidating other existing analysis
184 /// before/after running the "external" one.
185 template <typename AnalysisT>
186 typename AnalysisT::Result *runExternalAnalysis();
187
188 /// Returns an existing instance of BPI if any, otherwise nullptr. By
189 /// "existing" we mean either cached result provided by FunctionAnalysisManger
190 /// or created by preceding call to 'getOrCreateBPI'.
191 BranchProbabilityInfo *getBPI();
192
193 /// Returns an existing instance of BFI if any, otherwise nullptr. By
194 /// "existing" we mean either cached result provided by FunctionAnalysisManger
195 /// or created by preceding call to 'getOrCreateBFI'.
196 BlockFrequencyInfo *getBFI();
197
198 /// Returns an existing instance of BPI if any, otherwise:
199 /// if 'HasProfile' is true creates new instance through
200 /// FunctionAnalysisManager, otherwise nullptr.
201 BranchProbabilityInfo *getOrCreateBPI(bool Force = false);
202
203 /// Returns an existing instance of BFI if any, otherwise:
204 /// if 'HasProfile' is true creates new instance through
205 /// FunctionAnalysisManager, otherwise nullptr.
206 BlockFrequencyInfo *getOrCreateBFI(bool Force = false);
207};
208
209} // end namespace llvm
210
211#endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
212

source code of llvm/include/llvm/Transforms/Scalar/JumpThreading.h