Line data Source code
1 : //==- ConstantHoisting.h - Prepare code for expensive constants --*- C++ -*-==//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This pass identifies expensive constants to hoist and coalesces them to
11 : // better prepare it for SelectionDAG-based code generation. This works around
12 : // the limitations of the basic-block-at-a-time approach.
13 : //
14 : // First it scans all instructions for integer constants and calculates its
15 : // cost. If the constant can be folded into the instruction (the cost is
16 : // TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
17 : // consider it expensive and leave it alone. This is the default behavior and
18 : // the default implementation of getIntImmCost will always return TCC_Free.
19 : //
20 : // If the cost is more than TCC_BASIC, then the integer constant can't be folded
21 : // into the instruction and it might be beneficial to hoist the constant.
22 : // Similar constants are coalesced to reduce register pressure and
23 : // materialization code.
24 : //
25 : // When a constant is hoisted, it is also hidden behind a bitcast to force it to
26 : // be live-out of the basic block. Otherwise the constant would be just
27 : // duplicated and each basic block would have its own copy in the SelectionDAG.
28 : // The SelectionDAG recognizes such constants as opaque and doesn't perform
29 : // certain transformations on them, which would create a new expensive constant.
30 : //
31 : // This optimization is only applied to integer constants in instructions and
32 : // simple (this means not nested) constant cast expressions. For example:
33 : // %0 = load i64* inttoptr (i64 big_constant to i64*)
34 : //
35 : //===----------------------------------------------------------------------===//
36 :
37 : #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
38 : #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
39 :
40 : #include "llvm/ADT/DenseMap.h"
41 : #include "llvm/ADT/PointerUnion.h"
42 : #include "llvm/ADT/SmallPtrSet.h"
43 : #include "llvm/ADT/SmallVector.h"
44 : #include "llvm/IR/PassManager.h"
45 : #include <algorithm>
46 : #include <vector>
47 :
48 : namespace llvm {
49 :
50 : class BasicBlock;
51 : class BlockFrequencyInfo;
52 : class Constant;
53 : class ConstantInt;
54 : class ConstantExpr;
55 : class DominatorTree;
56 : class Function;
57 : class GlobalVariable;
58 : class Instruction;
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 2610 : 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 9624 : 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 1738 : ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr) :
88 1738 : 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 2610 : CumulativeCost += Cost;
93 2610 : 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.
99 2794 : struct RebasedConstantInfo {
100 : ConstantUseListType Uses;
101 : Constant *Offset;
102 : Type *Ty;
103 :
104 : RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset,
105 1078 : 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 1308 : 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 :
130 198129 : void releaseMemory() {
131 198129 : ClonedCastMap.clear();
132 : ConstIntCandVec.clear();
133 198133 : for (auto MapEntry : ConstGEPCandMap)
134 : MapEntry.second.clear();
135 198129 : ConstGEPCandMap.clear();
136 : ConstIntInfoVec.clear();
137 198133 : for (auto MapEntry : ConstGEPInfoMap)
138 : MapEntry.second.clear();
139 198129 : ConstGEPInfoMap.clear();
140 198129 : }
141 :
142 : private:
143 : using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>;
144 : using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>;
145 :
146 : const TargetTransformInfo *TTI;
147 : DominatorTree *DT;
148 : BlockFrequencyInfo *BFI;
149 : LLVMContext *Ctx;
150 : const DataLayout *DL;
151 : BasicBlock *Entry;
152 :
153 : /// Keeps track of constant candidates found in the function.
154 : using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
155 : using GVCandVecMapType = DenseMap<GlobalVariable *, ConstCandVecType>;
156 : ConstCandVecType ConstIntCandVec;
157 : GVCandVecMapType ConstGEPCandMap;
158 :
159 : /// These are the final constants we decided to hoist.
160 : using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>;
161 : using GVInfoVecMapType = DenseMap<GlobalVariable *, ConstInfoVecType>;
162 : ConstInfoVecType ConstIntInfoVec;
163 : GVInfoVecMapType ConstGEPInfoMap;
164 :
165 : /// Keep track of cast instructions we already cloned.
166 : SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
167 :
168 : Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
169 : SmallPtrSet<Instruction *, 8>
170 : findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
171 : void collectConstantCandidates(ConstCandMapType &ConstCandMap,
172 : Instruction *Inst, unsigned Idx,
173 : ConstantInt *ConstInt);
174 : void collectConstantCandidates(ConstCandMapType &ConstCandMap,
175 : Instruction *Inst, unsigned Idx,
176 : ConstantExpr *ConstExpr);
177 : void collectConstantCandidates(ConstCandMapType &ConstCandMap,
178 : Instruction *Inst, unsigned Idx);
179 : void collectConstantCandidates(ConstCandMapType &ConstCandMap,
180 : Instruction *Inst);
181 : void collectConstantCandidates(Function &Fn);
182 : void findAndMakeBaseConstant(ConstCandVecType::iterator S,
183 : ConstCandVecType::iterator E,
184 : SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec);
185 : unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
186 : ConstCandVecType::iterator E,
187 : ConstCandVecType::iterator &MaxCostItr);
188 : // If BaseGV is nullptr, find base among Constant Integer candidates;
189 : // otherwise find base among constant GEPs sharing BaseGV as base pointer.
190 : void findBaseConstants(GlobalVariable *BaseGV);
191 : void emitBaseConstants(Instruction *Base, Constant *Offset, Type *Ty,
192 : const consthoist::ConstantUser &ConstUser);
193 : // If BaseGV is nullptr, emit Constant Integer base; otherwise emit
194 : // constant GEP base.
195 : bool emitBaseConstants(GlobalVariable *BaseGV);
196 : void deleteDeadCastInst() const;
197 : bool optimizeConstants(Function &Fn);
198 : };
199 :
200 : } // end namespace llvm
201 :
202 : #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
|
