LLVM  9.0.0svn
JumpThreading.h
Go to the documentation of this file.
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"
26 #include "llvm/IR/ValueHandle.h"
27 #include <memory>
28 #include <utility>
29 
30 namespace llvm {
31 
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 TargetLibraryInfo;
45 class Value;
46 
47 /// A private "module" namespace for types and utilities used by
48 /// JumpThreading.
49 /// These are implementation details and should not be used by clients.
50 namespace jumpthreading {
51 
52 // These are at global scope so static functions can use them too.
55 
56 // This is used to keep track of what kind of constant we're currently hoping
57 // to find.
59 
60 } // end namespace jumpthreading
61 
62 /// This pass performs 'jump threading', which looks at blocks that have
63 /// multiple predecessors and multiple successors. If one or more of the
64 /// predecessors of the block can be proven to always jump to one of the
65 /// successors, we forward the edge from the predecessor to the successor by
66 /// duplicating the contents of this block.
67 ///
68 /// An example of when this can occur is code like this:
69 ///
70 /// if () { ...
71 /// X = 4;
72 /// }
73 /// if (X < 3) {
74 ///
75 /// In this case, the unconditional branch at the end of the first if can be
76 /// revectored to the false side of the second if.
77 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
78  TargetLibraryInfo *TLI;
79  LazyValueInfo *LVI;
80  AliasAnalysis *AA;
81  DomTreeUpdater *DTU;
82  std::unique_ptr<BlockFrequencyInfo> BFI;
83  std::unique_ptr<BranchProbabilityInfo> BPI;
84  bool HasProfileData = false;
85  bool HasGuards = false;
86 #ifdef NDEBUG
88 #else
90 #endif
91 
92  unsigned BBDupThreshold;
93 
94 public:
95  JumpThreadingPass(int T = -1);
96 
97  // Glue for old PM.
98  bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_,
99  AliasAnalysis *AA_, DomTreeUpdater *DTU_, bool HasProfileData_,
100  std::unique_ptr<BlockFrequencyInfo> BFI_,
101  std::unique_ptr<BranchProbabilityInfo> BPI_);
102 
104 
105  void releaseMemory() {
106  BFI.reset();
107  BPI.reset();
108  }
109 
110  void FindLoopHeaders(Function &F);
111  bool ProcessBlock(BasicBlock *BB);
112  bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
113  BasicBlock *SuccBB);
114  bool DuplicateCondBranchOnPHIIntoPred(
115  BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
116 
117  bool ComputeValueKnownInPredecessorsImpl(
120  DenseSet<std::pair<Value *, BasicBlock *>> &RecursionSet,
121  Instruction *CxtI = nullptr);
122  bool
126  Instruction *CxtI = nullptr) {
128  return ComputeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
129  RecursionSet, CxtI);
130  }
131 
132  bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
134  Instruction *CxtI = nullptr);
135 
136  bool ProcessBranchOnPHI(PHINode *PN);
137  bool ProcessBranchOnXOR(BinaryOperator *BO);
138  bool ProcessImpliedCondition(BasicBlock *BB);
139 
140  bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
141  void UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI,
142  PHINode *SIUse, unsigned Idx);
143 
144  bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
145  bool TryToUnfoldSelect(SwitchInst *SI, 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
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:722
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:59
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
F(f)
An instruction for reading from memory.
Definition: Instructions.h:167
This class represents the LLVM &#39;select&#39; instruction.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:372
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:198
bool ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Conditional or Unconditional Branch instruction.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Provides information about what library functions are available for the current target.
This pass performs &#39;jump threading&#39;, which looks at blocks that have multiple predecessors and multip...
Definition: JumpThreading.h:77
Multiway switch.
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:31
LLVM Value Representation.
Definition: Value.h:72
A container for analyses that lazily runs them and caches their results.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43