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 
28 namespace llvm {
29 
30 class AAResults;
31 class BasicBlock;
32 class BinaryOperator;
33 class BranchInst;
34 class CmpInst;
35 class Constant;
36 class Function;
37 class Instruction;
38 class IntrinsicInst;
39 class LazyValueInfo;
40 class LoadInst;
41 class PHINode;
42 class SelectInst;
43 class SwitchInst;
44 class TargetLibraryInfo;
45 class TargetTransformInfo;
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   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 
99 public:
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 
168 private:
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