JumpThreading.h revision 360784 
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/AliasAnalysis.h"
23#include "llvm/Analysis/BlockFrequencyInfo.h"
24#include "llvm/Analysis/BranchProbabilityInfo.h"
25#include "llvm/Analysis/DomTreeUpdater.h"
26#include "llvm/IR/ValueHandle.h"
27#include <memory>
28#include <utility>
29
30namespace llvm {
31
32class BasicBlock;
33class BinaryOperator;
34class BranchInst;
35class CmpInst;
36class Constant;
37class DomTreeUpdater;
38class Function;
39class Instruction;
40class IntrinsicInst;
41class LazyValueInfo;
42class LoadInst;
43class PHINode;
44class TargetLibraryInfo;
45class 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.
50namespace jumpthreading {
51
52// These are at global scope so static functions can use them too.
53using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>;
54using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>;
55
56// This is used to keep track of what kind of constant we're currently hoping
57// to find.
58enum ConstantPreference { WantInteger, WantBlockAddress };
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.
77class 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
87  SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
88#else
89  SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
90#endif
91
92  unsigned BBDupThreshold;
93
94public:
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
103  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
104
105  void releaseMemory() {
106    BFI.reset();
107    BPI.reset();
108  }
109
110  void FindLoopHeaders(Function &F);
111  bool ProcessBlock(BasicBlock *BB);
112  bool MaybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB);
113  void UpdateSSA(BasicBlock *BB, BasicBlock *NewBB,
114                 DenseMap<Instruction *, Value *> &ValueMapping);
115  DenseMap<Instruction *, Value *> CloneInstructions(BasicBlock::iterator BI,
116                                                     BasicBlock::iterator BE,
117                                                     BasicBlock *NewBB,
118                                                     BasicBlock *PredBB);
119  bool TryThreadEdge(BasicBlock *BB,
120                     const SmallVectorImpl<BasicBlock *> &PredBBs,
121                     BasicBlock *SuccBB);
122  void ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
123                  BasicBlock *SuccBB);
124  bool DuplicateCondBranchOnPHIIntoPred(
125      BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
126
127  bool ComputeValueKnownInPredecessorsImpl(
128      Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
129      jumpthreading::ConstantPreference Preference,
130      DenseSet<std::pair<Value *, BasicBlock *>> &RecursionSet,
131      Instruction *CxtI = nullptr);
132  bool
133  ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
134                                  jumpthreading::PredValueInfo &Result,
135                                  jumpthreading::ConstantPreference Preference,
136                                  Instruction *CxtI = nullptr) {
137    DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet;
138    return ComputeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
139                                               RecursionSet, CxtI);
140  }
141
142  bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
143                              jumpthreading::ConstantPreference Preference,
144                              Instruction *CxtI = nullptr);
145
146  bool ProcessBranchOnPHI(PHINode *PN);
147  bool ProcessBranchOnXOR(BinaryOperator *BO);
148  bool ProcessImpliedCondition(BasicBlock *BB);
149
150  bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
151  void UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI,
152                         PHINode *SIUse, unsigned Idx);
153
154  bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
155  bool TryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB);
156  bool TryToUnfoldSelectInCurrBB(BasicBlock *BB);
157
158  bool ProcessGuards(BasicBlock *BB);
159  bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
160
161private:
162  BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
163                              const char *Suffix);
164  void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
165                                    BasicBlock *NewBB, BasicBlock *SuccBB);
166  /// Check if the block has profile metadata for its outgoing edges.
167  bool doesBlockHaveProfileData(BasicBlock *BB);
168};
169
170} // end namespace llvm
171
172#endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
173