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 getIntImmCostInst 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/ArrayRef.h"
40 #include "llvm/ADT/DenseMap.h"
41 #include "llvm/ADT/MapVector.h"
42 #include "llvm/ADT/PointerUnion.h"
43 #include "llvm/ADT/SetVector.h"
44 #include "llvm/ADT/SmallVector.h"
45 #include "llvm/IR/PassManager.h"
46 #include <algorithm>
47 #include <vector>
48 
49 namespace llvm {
50 
51 class BasicBlock;
52 class BlockFrequencyInfo;
53 class Constant;
54 class ConstantInt;
55 class ConstantExpr;
56 class DominatorTree;
57 class Function;
58 class GlobalVariable;
59 class Instruction;
60 class ProfileSummaryInfo;
61 class TargetTransformInfo;
62 
63 /// A private "module" namespace for types and utilities used by
64 /// ConstantHoisting. These are implementation details and should not be used by
65 /// clients.
66 namespace consthoist {
67 
68 /// Keeps track of the user of a constant and the operand index where the
69 /// constant is used.
70 struct ConstantUser {
71   Instruction *Inst;
72   unsigned OpndIdx;
73 
74   ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
75 };
76 
77 using ConstantUseListType = SmallVector<ConstantUser, 8>;
78 
79 /// Keeps track of a constant candidate and its uses.
80 struct ConstantCandidate {
81   ConstantUseListType Uses;
82   // If the candidate is a ConstantExpr (currely only constant GEP expressions
83   // whose base pointers are GlobalVariables are supported), ConstInt records
84   // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
85   ConstantInt *ConstInt;
86   ConstantExpr *ConstExpr;
87   unsigned CumulativeCost = 0;
88 
89   ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr) :
90       ConstInt(ConstInt), ConstExpr(ConstExpr) {}
91 
92   /// Add the user to the use list and update the cost.
93   void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
94     CumulativeCost += Cost;
95     Uses.push_back(ConstantUser(Inst, Idx));
96   }
97 };
98 
99 /// This represents a constant that has been rebased with respect to a
100 /// base constant. The difference to the base constant is recorded in Offset.
101 struct RebasedConstantInfo {
102   ConstantUseListType Uses;
103   Constant *Offset;
104   Type *Ty;
105 
106   RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset,
107       Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {}
108 };
109 
110 using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
111 
112 /// A base constant and all its rebased constants.
113 struct ConstantInfo {
114   // If the candidate is a ConstantExpr (currely only constant GEP expressions
115   // whose base pointers are GlobalVariables are supported), ConstInt records
116   // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
117   ConstantInt *BaseInt;
118   ConstantExpr *BaseExpr;
119   RebasedConstantListType RebasedConstants;
120 };
121 
122 } // end namespace consthoist
123 
124 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
125 public:
126   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
127 
128   // Glue for old PM.
129   bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
130                BlockFrequencyInfo *BFI, BasicBlock &Entry,
131                ProfileSummaryInfo *PSI);
132 
133   void cleanup() {
134     ClonedCastMap.clear();
135     ConstIntCandVec.clear();
136     for (auto MapEntry : ConstGEPCandMap)
137       MapEntry.second.clear();
138     ConstGEPCandMap.clear();
139     ConstIntInfoVec.clear();
140     for (auto MapEntry : ConstGEPInfoMap)
141       MapEntry.second.clear();
142     ConstGEPInfoMap.clear();
143   }
144 
145 private:
146   using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>;
147   using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>;
148 
149   const TargetTransformInfo *TTI;
150   DominatorTree *DT;
151   BlockFrequencyInfo *BFI;
152   LLVMContext *Ctx;
153   const DataLayout *DL;
154   BasicBlock *Entry;
155   ProfileSummaryInfo *PSI;
156   bool OptForSize;
157 
158   /// Keeps track of constant candidates found in the function.
159   using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
160   using GVCandVecMapType = MapVector<GlobalVariable *, ConstCandVecType>;
161   ConstCandVecType ConstIntCandVec;
162   GVCandVecMapType ConstGEPCandMap;
163 
164   /// These are the final constants we decided to hoist.
165   using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>;
166   using GVInfoVecMapType = MapVector<GlobalVariable *, ConstInfoVecType>;
167   ConstInfoVecType ConstIntInfoVec;
168   GVInfoVecMapType ConstGEPInfoMap;
169 
170   /// Keep track of cast instructions we already cloned.
171   MapVector<Instruction *, Instruction *> ClonedCastMap;
172 
173   void collectMatInsertPts(
174       const consthoist::RebasedConstantListType &RebasedConstants,
175       SmallVectorImpl<Instruction *> &MatInsertPts) const;
176   Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
177   SetVector<Instruction *>
178   findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo,
179                              const ArrayRef<Instruction *> MatInsertPts) const;
180   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
181                                  Instruction *Inst, unsigned Idx,
182                                  ConstantInt *ConstInt);
183   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
184                                  Instruction *Inst, unsigned Idx,
185                                  ConstantExpr *ConstExpr);
186   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
187                                  Instruction *Inst, unsigned Idx);
188   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
189                                  Instruction *Inst);
190   void collectConstantCandidates(Function &Fn);
191   void findAndMakeBaseConstant(ConstCandVecType::iterator S,
192                                ConstCandVecType::iterator E,
193       SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec);
194   unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
195                                     ConstCandVecType::iterator E,
196                                     ConstCandVecType::iterator &MaxCostItr);
197   // If BaseGV is nullptr, find base among Constant Integer candidates;
198   // otherwise find base among constant GEPs sharing BaseGV as base pointer.
199   void findBaseConstants(GlobalVariable *BaseGV);
200 
201   /// A ConstantUser grouped with the Type and Constant adjustment. The user
202   /// will be adjusted by Offset.
203   struct UserAdjustment {
204     Constant *Offset;
205     Type *Ty;
206     Instruction *MatInsertPt;
207     const consthoist::ConstantUser User;
208     UserAdjustment(Constant *O, Type *T, Instruction *I,
209                    consthoist::ConstantUser U)
210         : Offset(O), Ty(T), MatInsertPt(I), User(U) {}
211   };
212   void emitBaseConstants(Instruction *Base, UserAdjustment *Adj);
213   // If BaseGV is nullptr, emit Constant Integer base; otherwise emit
214   // constant GEP base.
215   bool emitBaseConstants(GlobalVariable *BaseGV);
216   void deleteDeadCastInst() const;
217 };
218 
219 } // end namespace llvm
220 
221 #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
222