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   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       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.
99 struct RebasedConstantInfo {
100   ConstantUseListType Uses;
101   Constant *Offset;
102   Type *Ty;
103 
104   RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset,
105       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   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:
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
205