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