xref: /freebsd/contrib/llvm-project/llvm/include/llvm/Transforms/Scalar/JumpThreading.h (revision 924226fba12cc9a228c73b956e1b7fa24c60b055)
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/BlockFrequencyInfo.h"
23 #include "llvm/Analysis/BranchProbabilityInfo.h"
24 #include "llvm/Analysis/DomTreeUpdater.h"
25 #include "llvm/IR/ValueHandle.h"
26 #include <memory>
27 #include <utility>
28 
29 namespace llvm {
30 
31 class AAResults;
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 SelectInst;
45 class SwitchInst;
46 class TargetLibraryInfo;
47 class TargetTransformInfo;
48 class 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.
53 namespace jumpthreading {
54 
55 // These are at global scope so static functions can use them too.
56 using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>;
57 using 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.
61 enum 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.
80 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
81   TargetLibraryInfo *TLI;
82   TargetTransformInfo *TTI;
83   LazyValueInfo *LVI;
84   AAResults *AA;
85   DomTreeUpdater *DTU;
86   std::unique_ptr<BlockFrequencyInfo> BFI;
87   std::unique_ptr<BranchProbabilityInfo> BPI;
88   bool HasProfileData = 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   bool InsertFreezeWhenUnfoldingSelect;
99 
100 public:
101   JumpThreadingPass(bool InsertFreezeWhenUnfoldingSelect = false, int T = -1);
102 
103   // Glue for old PM.
104   bool runImpl(Function &F, TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
105                LazyValueInfo *LVI, AAResults *AA, DomTreeUpdater *DTU,
106                bool HasProfileData, std::unique_ptr<BlockFrequencyInfo> BFI,
107                std::unique_ptr<BranchProbabilityInfo> BPI);
108 
109   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
110 
111   void releaseMemory() {
112     BFI.reset();
113     BPI.reset();
114   }
115 
116   void findLoopHeaders(Function &F);
117   bool processBlock(BasicBlock *BB);
118   bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB);
119   void updateSSA(BasicBlock *BB, BasicBlock *NewBB,
120                  DenseMap<Instruction *, Value *> &ValueMapping);
121   DenseMap<Instruction *, Value *> cloneInstructions(BasicBlock::iterator BI,
122                                                      BasicBlock::iterator BE,
123                                                      BasicBlock *NewBB,
124                                                      BasicBlock *PredBB);
125   bool tryThreadEdge(BasicBlock *BB,
126                      const SmallVectorImpl<BasicBlock *> &PredBBs,
127                      BasicBlock *SuccBB);
128   void threadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
129                   BasicBlock *SuccBB);
130   bool duplicateCondBranchOnPHIIntoPred(
131       BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
132 
133   bool computeValueKnownInPredecessorsImpl(
134       Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
135       jumpthreading::ConstantPreference Preference,
136       DenseSet<Value *> &RecursionSet, Instruction *CxtI = nullptr);
137   bool
138   computeValueKnownInPredecessors(Value *V, BasicBlock *BB,
139                                   jumpthreading::PredValueInfo &Result,
140                                   jumpthreading::ConstantPreference Preference,
141                                   Instruction *CxtI = nullptr) {
142     DenseSet<Value *> RecursionSet;
143     return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
144                                                RecursionSet, CxtI);
145   }
146 
147   Constant *evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB,
148                                       Value *cond);
149   bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond);
150   void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB,
151                                    BasicBlock *BB, BasicBlock *SuccBB);
152   bool processThreadableEdges(Value *Cond, BasicBlock *BB,
153                               jumpthreading::ConstantPreference Preference,
154                               Instruction *CxtI = nullptr);
155 
156   bool processBranchOnPHI(PHINode *PN);
157   bool processBranchOnXOR(BinaryOperator *BO);
158   bool processImpliedCondition(BasicBlock *BB);
159 
160   bool simplifyPartiallyRedundantLoad(LoadInst *LI);
161   void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI,
162                          PHINode *SIUse, unsigned Idx);
163 
164   bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
165   bool tryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB);
166   bool tryToUnfoldSelectInCurrBB(BasicBlock *BB);
167 
168   bool processGuards(BasicBlock *BB);
169   bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
170 
171 private:
172   BasicBlock *splitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
173                               const char *Suffix);
174   void updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
175                                     BasicBlock *NewBB, BasicBlock *SuccBB);
176   /// Check if the block has profile metadata for its outgoing edges.
177   bool doesBlockHaveProfileData(BasicBlock *BB);
178 };
179 
180 } // end namespace llvm
181 
182 #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
183