Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Transforms/Scalar/ConstantHoisting.h
Line
Count
Source
1
//==- ConstantHoisting.h - Prepare code for expensive constants --*- 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
// This pass identifies expensive constants to hoist and coalesces them to
10
// better prepare it for SelectionDAG-based code generation. This works around
11
// the limitations of the basic-block-at-a-time approach.
12
//
13
// First it scans all instructions for integer constants and calculates its
14
// cost. If the constant can be folded into the instruction (the cost is
15
// TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
16
// consider it expensive and leave it alone. This is the default behavior and
17
// the default implementation of getIntImmCost will always return TCC_Free.
18
//
19
// If the cost is more than TCC_BASIC, then the integer constant can't be folded
20
// into the instruction and it might be beneficial to hoist the constant.
21
// Similar constants are coalesced to reduce register pressure and
22
// materialization code.
23
//
24
// When a constant is hoisted, it is also hidden behind a bitcast to force it to
25
// be live-out of the basic block. Otherwise the constant would be just
26
// duplicated and each basic block would have its own copy in the SelectionDAG.
27
// The SelectionDAG recognizes such constants as opaque and doesn't perform
28
// certain transformations on them, which would create a new expensive constant.
29
//
30
// This optimization is only applied to integer constants in instructions and
31
// simple (this means not nested) constant cast expressions. For example:
32
// %0 = load i64* inttoptr (i64 big_constant to i64*)
33
//
34
//===----------------------------------------------------------------------===//
35
36
#ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
37
#define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
38
39
#include "llvm/ADT/DenseMap.h"
40
#include "llvm/ADT/PointerUnion.h"
41
#include "llvm/ADT/SmallPtrSet.h"
42
#include "llvm/ADT/SmallVector.h"
43
#include "llvm/IR/PassManager.h"
44
#include <algorithm>
45
#include <vector>
46
47
namespace llvm {
48
49
class BasicBlock;
50
class BlockFrequencyInfo;
51
class Constant;
52
class ConstantInt;
53
class ConstantExpr;
54
class DominatorTree;
55
class Function;
56
class GlobalVariable;
57
class Instruction;
58
class ProfileSummaryInfo;
59
class TargetTransformInfo;
60
61
/// A private "module" namespace for types and utilities used by
62
/// ConstantHoisting. These are implementation details and should not be used by
63
/// clients.
64
namespace consthoist {
65
66
/// Keeps track of the user of a constant and the operand index where the
67
/// constant is used.
68
struct ConstantUser {
69
  Instruction *Inst;
70
  unsigned OpndIdx;
71
72
49.7k
  ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
73
};
74
75
using ConstantUseListType = SmallVector<ConstantUser, 8>;
76
77
/// Keeps track of a constant candidate and its uses.
78
struct ConstantCandidate {
79
  ConstantUseListType Uses;
80
  // If the candidate is a ConstantExpr (currely only constant GEP expressions
81
  // whose base pointers are GlobalVariables are supported), ConstInt records
82
  // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
83
  ConstantInt *ConstInt;
84
  ConstantExpr *ConstExpr;
85
  unsigned CumulativeCost = 0;
86
87
  ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr) :
88
22.8k
      ConstInt(ConstInt), ConstExpr(ConstExpr) {}
89
90
  /// Add the user to the use list and update the cost.
91
49.7k
  void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
92
49.7k
    CumulativeCost += Cost;
93
49.7k
    Uses.push_back(ConstantUser(Inst, Idx));
94
49.7k
  }
95
};
96
97
/// This represents a constant that has been rebased with respect to a
98
/// base constant. The difference to the base constant is recorded in Offset.
99
struct RebasedConstantInfo {
100
  ConstantUseListType Uses;
101
  Constant *Offset;
102
  Type *Ty;
103
104
  RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset,
105
10.3k
      Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {}
106
};
107
108
using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
109
110
/// A base constant and all its rebased constants.
111
struct ConstantInfo {
112
  // If the candidate is a ConstantExpr (currely only constant GEP expressions
113
  // whose base pointers are GlobalVariables are supported), ConstInt records
114
  // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
115
  ConstantInt *BaseInt;
116
  ConstantExpr *BaseExpr;
117
  RebasedConstantListType RebasedConstants;
118
};
119
120
} // end namespace consthoist
121
122
class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
123
public:
124
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
125
126
  // Glue for old PM.
127
  bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
128
               BlockFrequencyInfo *BFI, BasicBlock &Entry,
129
               ProfileSummaryInfo *PSI);
130
131
489k
  void cleanup() {
132
489k
    ClonedCastMap.clear();
133
489k
    ConstIntCandVec.clear();
134
489k
    for (auto MapEntry : ConstGEPCandMap)
135
5
      MapEntry.second.clear();
136
489k
    ConstGEPCandMap.clear();
137
489k
    ConstIntInfoVec.clear();
138
489k
    for (auto MapEntry : ConstGEPInfoMap)
139
5
      MapEntry.second.clear();
140
489k
    ConstGEPInfoMap.clear();
141
489k
  }
142
143
private:
144
  using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>;
145
  using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>;
146
147
  const TargetTransformInfo *TTI;
148
  DominatorTree *DT;
149
  BlockFrequencyInfo *BFI;
150
  LLVMContext *Ctx;
151
  const DataLayout *DL;
152
  BasicBlock *Entry;
153
  ProfileSummaryInfo *PSI;
154
155
  /// Keeps track of constant candidates found in the function.
156
  using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
157
  using GVCandVecMapType = DenseMap<GlobalVariable *, ConstCandVecType>;
158
  ConstCandVecType ConstIntCandVec;
159
  GVCandVecMapType ConstGEPCandMap;
160
161
  /// These are the final constants we decided to hoist.
162
  using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>;
163
  using GVInfoVecMapType = DenseMap<GlobalVariable *, ConstInfoVecType>;
164
  ConstInfoVecType ConstIntInfoVec;
165
  GVInfoVecMapType ConstGEPInfoMap;
166
167
  /// Keep track of cast instructions we already cloned.
168
  SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
169
170
  Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
171
  SmallPtrSet<Instruction *, 8>
172
  findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
173
  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
174
                                 Instruction *Inst, unsigned Idx,
175
                                 ConstantInt *ConstInt);
176
  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
177
                                 Instruction *Inst, unsigned Idx,
178
                                 ConstantExpr *ConstExpr);
179
  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
180
                                 Instruction *Inst, unsigned Idx);
181
  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
182
                                 Instruction *Inst);
183
  void collectConstantCandidates(Function &Fn);
184
  void findAndMakeBaseConstant(ConstCandVecType::iterator S,
185
                               ConstCandVecType::iterator E,
186
      SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec);
187
  unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
188
                                    ConstCandVecType::iterator E,
189
                                    ConstCandVecType::iterator &MaxCostItr);
190
  // If BaseGV is nullptr, find base among Constant Integer candidates;
191
  // otherwise find base among constant GEPs sharing BaseGV as base pointer.
192
  void findBaseConstants(GlobalVariable *BaseGV);
193
  void emitBaseConstants(Instruction *Base, Constant *Offset, Type *Ty,
194
                         const consthoist::ConstantUser &ConstUser);
195
  // If BaseGV is nullptr, emit Constant Integer base; otherwise emit
196
  // constant GEP base.
197
  bool emitBaseConstants(GlobalVariable *BaseGV);
198
  void deleteDeadCastInst() const;
199
  bool optimizeConstants(Function &Fn);
200
};
201
202
} // end namespace llvm
203
204
#endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H