Line data Source code
1 : //===- JumpThreading.h - thread control through conditional BBs -*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : /// \file
11 : /// See the comments on JumpThreadingPass.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
16 : #define LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
17 :
18 : #include "llvm/ADT/ArrayRef.h"
19 : #include "llvm/ADT/DenseSet.h"
20 : #include "llvm/ADT/SmallPtrSet.h"
21 : #include "llvm/ADT/SmallSet.h"
22 : #include "llvm/ADT/SmallVector.h"
23 : #include "llvm/Analysis/AliasAnalysis.h"
24 : #include "llvm/Analysis/BlockFrequencyInfo.h"
25 : #include "llvm/Analysis/BranchProbabilityInfo.h"
26 : #include "llvm/IR/DomTreeUpdater.h"
27 : #include "llvm/IR/ValueHandle.h"
28 : #include <memory>
29 : #include <utility>
30 :
31 : namespace llvm {
32 :
33 : class BasicBlock;
34 : class BinaryOperator;
35 : class BranchInst;
36 : class CmpInst;
37 : class Constant;
38 : class DomTreeUpdater;
39 : class Function;
40 : class Instruction;
41 : class IntrinsicInst;
42 : class LazyValueInfo;
43 : class LoadInst;
44 : class PHINode;
45 : class TargetLibraryInfo;
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 : TargetLibraryInfo *TLI;
80 : LazyValueInfo *LVI;
81 : AliasAnalysis *AA;
82 : DomTreeUpdater *DTU;
83 : std::unique_ptr<BlockFrequencyInfo> BFI;
84 : std::unique_ptr<BranchProbabilityInfo> BPI;
85 : bool HasProfileData = false;
86 : bool HasGuards = false;
87 : #ifdef NDEBUG
88 : SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
89 : #else
90 : SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
91 : #endif
92 : DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet;
93 :
94 : unsigned BBDupThreshold;
95 :
96 : // RAII helper for updating the recursion stack.
97 : struct RecursionSetRemover {
98 : DenseSet<std::pair<Value *, BasicBlock *>> &TheSet;
99 : std::pair<Value *, BasicBlock *> ThePair;
100 :
101 : RecursionSetRemover(DenseSet<std::pair<Value *, BasicBlock *>> &S,
102 : std::pair<Value *, BasicBlock *> P)
103 327835 : : TheSet(S), ThePair(P) {}
104 :
105 327835 : ~RecursionSetRemover() { TheSet.erase(ThePair); }
106 : };
107 :
108 : public:
109 : JumpThreadingPass(int T = -1);
110 :
111 : // Glue for old PM.
112 : bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_,
113 : AliasAnalysis *AA_, DomTreeUpdater *DTU_, bool HasProfileData_,
114 : std::unique_ptr<BlockFrequencyInfo> BFI_,
115 : std::unique_ptr<BranchProbabilityInfo> BPI_);
116 :
117 : PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
118 :
119 88190 : void releaseMemory() {
120 : BFI.reset();
121 : BPI.reset();
122 88190 : }
123 :
124 : void FindLoopHeaders(Function &F);
125 : bool ProcessBlock(BasicBlock *BB);
126 : bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
127 : BasicBlock *SuccBB);
128 : bool DuplicateCondBranchOnPHIIntoPred(
129 : BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
130 :
131 : bool
132 : ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
133 : jumpthreading::PredValueInfo &Result,
134 : jumpthreading::ConstantPreference Preference,
135 : Instruction *CxtI = nullptr);
136 : bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
137 : jumpthreading::ConstantPreference Preference,
138 : Instruction *CxtI = nullptr);
139 :
140 : bool ProcessBranchOnPHI(PHINode *PN);
141 : bool ProcessBranchOnXOR(BinaryOperator *BO);
142 : bool ProcessImpliedCondition(BasicBlock *BB);
143 :
144 : bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
145 : bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
146 : bool TryToUnfoldSelectInCurrBB(BasicBlock *BB);
147 :
148 : bool ProcessGuards(BasicBlock *BB);
149 : bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
150 :
151 : private:
152 : BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
153 : const char *Suffix);
154 : void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
155 : BasicBlock *NewBB, BasicBlock *SuccBB);
156 : /// Check if the block has profile metadata for its outgoing edges.
157 : bool doesBlockHaveProfileData(BasicBlock *BB);
158 : };
159 :
160 : } // end namespace llvm
161 :
162 : #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
|
