LLVM  9.0.0svn
ConstantHoisting.h
Go to the documentation of this file.
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 {
70  unsigned OpndIdx;
71 
72  ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
73 };
74 
76 
77 /// Keeps track of a constant candidate and its 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.
85  unsigned CumulativeCost = 0;
86 
87  ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr) :
88  ConstInt(ConstInt), ConstExpr(ConstExpr) {}
89 
90  /// Add the user to the use list and update the cost.
91  void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
92  CumulativeCost += Cost;
93  Uses.push_back(ConstantUser(Inst, Idx));
94  }
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.
103 
105  Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {}
106 };
107 
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.
118 };
119 
120 } // end namespace consthoist
121 
122 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
123 public:
125 
126  // Glue for old PM.
129  ProfileSummaryInfo *PSI);
130 
131  void cleanup() {
132  ClonedCastMap.clear();
133  ConstIntCandVec.clear();
134  for (auto MapEntry : ConstGEPCandMap)
135  MapEntry.second.clear();
136  ConstGEPCandMap.clear();
137  ConstIntInfoVec.clear();
138  for (auto MapEntry : ConstGEPInfoMap)
139  MapEntry.second.clear();
140  ConstGEPInfoMap.clear();
141  }
142 
143 private:
146 
147  const TargetTransformInfo *TTI;
148  DominatorTree *DT;
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>;
158  ConstCandVecType ConstIntCandVec;
159  GVCandVecMapType ConstGEPCandMap;
160 
161  /// These are the final constants we decided to hoist.
164  ConstInfoVecType ConstIntInfoVec;
165  GVInfoVecMapType ConstGEPInfoMap;
166 
167  /// Keep track of cast instructions we already cloned.
169 
170  Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
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,
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
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr)
A base constant and all its rebased constants.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:59
void push_back(const T &Elt)
Definition: SmallVector.h:211
Analysis providing profile information.
Keeps track of a constant candidate and its uses.
void addUser(Instruction *Inst, unsigned Idx, unsigned Cost)
Add the user to the use list and update the cost.
F(f)
This represents a constant that has been rebased with respect to a base constant. ...
Definition: BitVector.h:937
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:888
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:372
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
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
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
Keeps track of the user of a constant and the operand index where the constant is used...
RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset, Type *Ty=nullptr)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
ConstantUser(Instruction *Inst, unsigned Idx)
A container for analyses that lazily runs them and caches their results.
RebasedConstantListType RebasedConstants
This header defines various interfaces for pass management in LLVM.
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:163