Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Transforms/Scalar/JumpThreading.h
Line
Count
Source
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
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.
53
using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>;
54
using 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.
58
enum 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.
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
87
  SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
88
#else
89
  SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
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
103
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
104
105
931k
  void releaseMemory() {
106
931k
    BFI.reset();
107
931k
    BPI.reset();
108
931k
  }
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(
118
      Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
119
      jumpthreading::ConstantPreference Preference,
120
      DenseSet<std::pair<Value *, BasicBlock *>> &RecursionSet,
121
      Instruction *CxtI = nullptr);
122
  bool
123
  ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
124
                                  jumpthreading::PredValueInfo &Result,
125
                                  jumpthreading::ConstantPreference Preference,
126
3.66M
                                  Instruction *CxtI = nullptr) {
127
3.66M
    DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet;
128
3.66M
    return ComputeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
129
3.66M
                                               RecursionSet, CxtI);
130
3.66M
  }
131
132
  bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
133
                              jumpthreading::ConstantPreference Preference,
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