1 | //===- ConstantHoisting.cpp - Prepare code for expensive constants --------===// |
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 | #include "llvm/Transforms/Scalar/ConstantHoisting.h" |
36 | #include "llvm/ADT/APInt.h" |
37 | #include "llvm/ADT/DenseMap.h" |
38 | #include "llvm/ADT/SmallPtrSet.h" |
39 | #include "llvm/ADT/SmallVector.h" |
40 | #include "llvm/ADT/Statistic.h" |
41 | #include "llvm/Analysis/BlockFrequencyInfo.h" |
42 | #include "llvm/Analysis/ProfileSummaryInfo.h" |
43 | #include "llvm/Analysis/TargetTransformInfo.h" |
44 | #include "llvm/IR/BasicBlock.h" |
45 | #include "llvm/IR/Constants.h" |
46 | #include "llvm/IR/DebugInfoMetadata.h" |
47 | #include "llvm/IR/Dominators.h" |
48 | #include "llvm/IR/Function.h" |
49 | #include "llvm/IR/InstrTypes.h" |
50 | #include "llvm/IR/Instruction.h" |
51 | #include "llvm/IR/Instructions.h" |
52 | #include "llvm/IR/IntrinsicInst.h" |
53 | #include "llvm/IR/Operator.h" |
54 | #include "llvm/IR/Value.h" |
55 | #include "llvm/InitializePasses.h" |
56 | #include "llvm/Pass.h" |
57 | #include "llvm/Support/BlockFrequency.h" |
58 | #include "llvm/Support/Casting.h" |
59 | #include "llvm/Support/CommandLine.h" |
60 | #include "llvm/Support/Debug.h" |
61 | #include "llvm/Support/raw_ostream.h" |
62 | #include "llvm/Transforms/Scalar.h" |
63 | #include "llvm/Transforms/Utils/Local.h" |
64 | #include "llvm/Transforms/Utils/SizeOpts.h" |
65 | #include <algorithm> |
66 | #include <cassert> |
67 | #include <cstdint> |
68 | #include <iterator> |
69 | #include <tuple> |
70 | #include <utility> |
71 | |
72 | using namespace llvm; |
73 | using namespace consthoist; |
74 | |
75 | #define DEBUG_TYPE "consthoist" |
76 | |
77 | STATISTIC(NumConstantsHoisted, "Number of constants hoisted" ); |
78 | STATISTIC(NumConstantsRebased, "Number of constants rebased" ); |
79 | |
80 | static cl::opt<bool> ConstHoistWithBlockFrequency( |
81 | "consthoist-with-block-frequency" , cl::init(Val: true), cl::Hidden, |
82 | cl::desc("Enable the use of the block frequency analysis to reduce the " |
83 | "chance to execute const materialization more frequently than " |
84 | "without hoisting." )); |
85 | |
86 | static cl::opt<bool> ConstHoistGEP( |
87 | "consthoist-gep" , cl::init(Val: false), cl::Hidden, |
88 | cl::desc("Try hoisting constant gep expressions" )); |
89 | |
90 | static cl::opt<unsigned> |
91 | MinNumOfDependentToRebase("consthoist-min-num-to-rebase" , |
92 | cl::desc("Do not rebase if number of dependent constants of a Base is less " |
93 | "than this number." ), |
94 | cl::init(Val: 0), cl::Hidden); |
95 | |
96 | namespace { |
97 | |
98 | /// The constant hoisting pass. |
99 | class ConstantHoistingLegacyPass : public FunctionPass { |
100 | public: |
101 | static char ID; // Pass identification, replacement for typeid |
102 | |
103 | ConstantHoistingLegacyPass() : FunctionPass(ID) { |
104 | initializeConstantHoistingLegacyPassPass(*PassRegistry::getPassRegistry()); |
105 | } |
106 | |
107 | bool runOnFunction(Function &Fn) override; |
108 | |
109 | StringRef getPassName() const override { return "Constant Hoisting" ; } |
110 | |
111 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
112 | AU.setPreservesCFG(); |
113 | if (ConstHoistWithBlockFrequency) |
114 | AU.addRequired<BlockFrequencyInfoWrapperPass>(); |
115 | AU.addRequired<DominatorTreeWrapperPass>(); |
116 | AU.addRequired<ProfileSummaryInfoWrapperPass>(); |
117 | AU.addRequired<TargetTransformInfoWrapperPass>(); |
118 | } |
119 | |
120 | private: |
121 | ConstantHoistingPass Impl; |
122 | }; |
123 | |
124 | } // end anonymous namespace |
125 | |
126 | char ConstantHoistingLegacyPass::ID = 0; |
127 | |
128 | INITIALIZE_PASS_BEGIN(ConstantHoistingLegacyPass, "consthoist" , |
129 | "Constant Hoisting" , false, false) |
130 | INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) |
131 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
132 | INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) |
133 | INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) |
134 | INITIALIZE_PASS_END(ConstantHoistingLegacyPass, "consthoist" , |
135 | "Constant Hoisting" , false, false) |
136 | |
137 | FunctionPass *llvm::createConstantHoistingPass() { |
138 | return new ConstantHoistingLegacyPass(); |
139 | } |
140 | |
141 | /// Perform the constant hoisting optimization for the given function. |
142 | bool ConstantHoistingLegacyPass::runOnFunction(Function &Fn) { |
143 | if (skipFunction(F: Fn)) |
144 | return false; |
145 | |
146 | LLVM_DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n" ); |
147 | LLVM_DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n'); |
148 | |
149 | bool MadeChange = |
150 | Impl.runImpl(F&: Fn, TTI&: getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F: Fn), |
151 | DT&: getAnalysis<DominatorTreeWrapperPass>().getDomTree(), |
152 | BFI: ConstHoistWithBlockFrequency |
153 | ? &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI() |
154 | : nullptr, |
155 | Entry&: Fn.getEntryBlock(), |
156 | PSI: &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI()); |
157 | |
158 | LLVM_DEBUG(dbgs() << "********** End Constant Hoisting **********\n" ); |
159 | |
160 | return MadeChange; |
161 | } |
162 | |
163 | void ConstantHoistingPass::collectMatInsertPts( |
164 | const RebasedConstantListType &RebasedConstants, |
165 | SmallVectorImpl<BasicBlock::iterator> &MatInsertPts) const { |
166 | for (const RebasedConstantInfo &RCI : RebasedConstants) |
167 | for (const ConstantUser &U : RCI.Uses) |
168 | MatInsertPts.emplace_back(Args: findMatInsertPt(Inst: U.Inst, Idx: U.OpndIdx)); |
169 | } |
170 | |
171 | /// Find the constant materialization insertion point. |
172 | BasicBlock::iterator ConstantHoistingPass::findMatInsertPt(Instruction *Inst, |
173 | unsigned Idx) const { |
174 | // If the operand is a cast instruction, then we have to materialize the |
175 | // constant before the cast instruction. |
176 | if (Idx != ~0U) { |
177 | Value *Opnd = Inst->getOperand(i: Idx); |
178 | if (auto CastInst = dyn_cast<Instruction>(Val: Opnd)) |
179 | if (CastInst->isCast()) |
180 | return CastInst->getIterator(); |
181 | } |
182 | |
183 | // The simple and common case. This also includes constant expressions. |
184 | if (!isa<PHINode>(Val: Inst) && !Inst->isEHPad()) |
185 | return Inst->getIterator(); |
186 | |
187 | // We can't insert directly before a phi node or an eh pad. Insert before |
188 | // the terminator of the incoming or dominating block. |
189 | assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!" ); |
190 | BasicBlock *InsertionBlock = nullptr; |
191 | if (Idx != ~0U && isa<PHINode>(Val: Inst)) { |
192 | InsertionBlock = cast<PHINode>(Val: Inst)->getIncomingBlock(i: Idx); |
193 | if (!InsertionBlock->isEHPad()) { |
194 | return InsertionBlock->getTerminator()->getIterator(); |
195 | } |
196 | } else { |
197 | InsertionBlock = Inst->getParent(); |
198 | } |
199 | |
200 | // This must be an EH pad. Iterate over immediate dominators until we find a |
201 | // non-EH pad. We need to skip over catchswitch blocks, which are both EH pads |
202 | // and terminators. |
203 | auto *IDom = DT->getNode(BB: InsertionBlock)->getIDom(); |
204 | while (IDom->getBlock()->isEHPad()) { |
205 | assert(Entry != IDom->getBlock() && "eh pad in entry block" ); |
206 | IDom = IDom->getIDom(); |
207 | } |
208 | |
209 | return IDom->getBlock()->getTerminator()->getIterator(); |
210 | } |
211 | |
212 | /// Given \p BBs as input, find another set of BBs which collectively |
213 | /// dominates \p BBs and have the minimal sum of frequencies. Return the BB |
214 | /// set found in \p BBs. |
215 | static void findBestInsertionSet(DominatorTree &DT, BlockFrequencyInfo &BFI, |
216 | BasicBlock *Entry, |
217 | SetVector<BasicBlock *> &BBs) { |
218 | assert(!BBs.count(Entry) && "Assume Entry is not in BBs" ); |
219 | // Nodes on the current path to the root. |
220 | SmallPtrSet<BasicBlock *, 8> Path; |
221 | // Candidates includes any block 'BB' in set 'BBs' that is not strictly |
222 | // dominated by any other blocks in set 'BBs', and all nodes in the path |
223 | // in the dominator tree from Entry to 'BB'. |
224 | SmallPtrSet<BasicBlock *, 16> Candidates; |
225 | for (auto *BB : BBs) { |
226 | // Ignore unreachable basic blocks. |
227 | if (!DT.isReachableFromEntry(A: BB)) |
228 | continue; |
229 | Path.clear(); |
230 | // Walk up the dominator tree until Entry or another BB in BBs |
231 | // is reached. Insert the nodes on the way to the Path. |
232 | BasicBlock *Node = BB; |
233 | // The "Path" is a candidate path to be added into Candidates set. |
234 | bool isCandidate = false; |
235 | do { |
236 | Path.insert(Ptr: Node); |
237 | if (Node == Entry || Candidates.count(Ptr: Node)) { |
238 | isCandidate = true; |
239 | break; |
240 | } |
241 | assert(DT.getNode(Node)->getIDom() && |
242 | "Entry doens't dominate current Node" ); |
243 | Node = DT.getNode(BB: Node)->getIDom()->getBlock(); |
244 | } while (!BBs.count(key: Node)); |
245 | |
246 | // If isCandidate is false, Node is another Block in BBs dominating |
247 | // current 'BB'. Drop the nodes on the Path. |
248 | if (!isCandidate) |
249 | continue; |
250 | |
251 | // Add nodes on the Path into Candidates. |
252 | Candidates.insert(I: Path.begin(), E: Path.end()); |
253 | } |
254 | |
255 | // Sort the nodes in Candidates in top-down order and save the nodes |
256 | // in Orders. |
257 | unsigned Idx = 0; |
258 | SmallVector<BasicBlock *, 16> Orders; |
259 | Orders.push_back(Elt: Entry); |
260 | while (Idx != Orders.size()) { |
261 | BasicBlock *Node = Orders[Idx++]; |
262 | for (auto *ChildDomNode : DT.getNode(BB: Node)->children()) { |
263 | if (Candidates.count(Ptr: ChildDomNode->getBlock())) |
264 | Orders.push_back(Elt: ChildDomNode->getBlock()); |
265 | } |
266 | } |
267 | |
268 | // Visit Orders in bottom-up order. |
269 | using InsertPtsCostPair = |
270 | std::pair<SetVector<BasicBlock *>, BlockFrequency>; |
271 | |
272 | // InsertPtsMap is a map from a BB to the best insertion points for the |
273 | // subtree of BB (subtree not including the BB itself). |
274 | DenseMap<BasicBlock *, InsertPtsCostPair> InsertPtsMap; |
275 | InsertPtsMap.reserve(NumEntries: Orders.size() + 1); |
276 | for (BasicBlock *Node : llvm::reverse(C&: Orders)) { |
277 | bool NodeInBBs = BBs.count(key: Node); |
278 | auto &InsertPts = InsertPtsMap[Node].first; |
279 | BlockFrequency &InsertPtsFreq = InsertPtsMap[Node].second; |
280 | |
281 | // Return the optimal insert points in BBs. |
282 | if (Node == Entry) { |
283 | BBs.clear(); |
284 | if (InsertPtsFreq > BFI.getBlockFreq(BB: Node) || |
285 | (InsertPtsFreq == BFI.getBlockFreq(BB: Node) && InsertPts.size() > 1)) |
286 | BBs.insert(X: Entry); |
287 | else |
288 | BBs.insert(Start: InsertPts.begin(), End: InsertPts.end()); |
289 | break; |
290 | } |
291 | |
292 | BasicBlock *Parent = DT.getNode(BB: Node)->getIDom()->getBlock(); |
293 | // Initially, ParentInsertPts is empty and ParentPtsFreq is 0. Every child |
294 | // will update its parent's ParentInsertPts and ParentPtsFreq. |
295 | auto &ParentInsertPts = InsertPtsMap[Parent].first; |
296 | BlockFrequency &ParentPtsFreq = InsertPtsMap[Parent].second; |
297 | // Choose to insert in Node or in subtree of Node. |
298 | // Don't hoist to EHPad because we may not find a proper place to insert |
299 | // in EHPad. |
300 | // If the total frequency of InsertPts is the same as the frequency of the |
301 | // target Node, and InsertPts contains more than one nodes, choose hoisting |
302 | // to reduce code size. |
303 | if (NodeInBBs || |
304 | (!Node->isEHPad() && |
305 | (InsertPtsFreq > BFI.getBlockFreq(BB: Node) || |
306 | (InsertPtsFreq == BFI.getBlockFreq(BB: Node) && InsertPts.size() > 1)))) { |
307 | ParentInsertPts.insert(X: Node); |
308 | ParentPtsFreq += BFI.getBlockFreq(BB: Node); |
309 | } else { |
310 | ParentInsertPts.insert(Start: InsertPts.begin(), End: InsertPts.end()); |
311 | ParentPtsFreq += InsertPtsFreq; |
312 | } |
313 | } |
314 | } |
315 | |
316 | /// Find an insertion point that dominates all uses. |
317 | SetVector<BasicBlock::iterator> |
318 | ConstantHoistingPass::findConstantInsertionPoint( |
319 | const ConstantInfo &ConstInfo, |
320 | const ArrayRef<BasicBlock::iterator> MatInsertPts) const { |
321 | assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry." ); |
322 | // Collect all basic blocks. |
323 | SetVector<BasicBlock *> BBs; |
324 | SetVector<BasicBlock::iterator> InsertPts; |
325 | |
326 | for (BasicBlock::iterator MatInsertPt : MatInsertPts) |
327 | BBs.insert(X: MatInsertPt->getParent()); |
328 | |
329 | if (BBs.count(key: Entry)) { |
330 | InsertPts.insert(X: Entry->begin()); |
331 | return InsertPts; |
332 | } |
333 | |
334 | if (BFI) { |
335 | findBestInsertionSet(DT&: *DT, BFI&: *BFI, Entry, BBs); |
336 | for (BasicBlock *BB : BBs) |
337 | InsertPts.insert(X: BB->getFirstInsertionPt()); |
338 | return InsertPts; |
339 | } |
340 | |
341 | while (BBs.size() >= 2) { |
342 | BasicBlock *BB, *BB1, *BB2; |
343 | BB1 = BBs.pop_back_val(); |
344 | BB2 = BBs.pop_back_val(); |
345 | BB = DT->findNearestCommonDominator(A: BB1, B: BB2); |
346 | if (BB == Entry) { |
347 | InsertPts.insert(X: Entry->begin()); |
348 | return InsertPts; |
349 | } |
350 | BBs.insert(X: BB); |
351 | } |
352 | assert((BBs.size() == 1) && "Expected only one element." ); |
353 | Instruction &FirstInst = (*BBs.begin())->front(); |
354 | InsertPts.insert(X: findMatInsertPt(Inst: &FirstInst)); |
355 | return InsertPts; |
356 | } |
357 | |
358 | /// Record constant integer ConstInt for instruction Inst at operand |
359 | /// index Idx. |
360 | /// |
361 | /// The operand at index Idx is not necessarily the constant integer itself. It |
362 | /// could also be a cast instruction or a constant expression that uses the |
363 | /// constant integer. |
364 | void ConstantHoistingPass::collectConstantCandidates( |
365 | ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx, |
366 | ConstantInt *ConstInt) { |
367 | if (ConstInt->getType()->isVectorTy()) |
368 | return; |
369 | |
370 | InstructionCost Cost; |
371 | // Ask the target about the cost of materializing the constant for the given |
372 | // instruction and operand index. |
373 | if (auto IntrInst = dyn_cast<IntrinsicInst>(Val: Inst)) |
374 | Cost = TTI->getIntImmCostIntrin(IID: IntrInst->getIntrinsicID(), Idx, |
375 | Imm: ConstInt->getValue(), Ty: ConstInt->getType(), |
376 | CostKind: TargetTransformInfo::TCK_SizeAndLatency); |
377 | else |
378 | Cost = TTI->getIntImmCostInst( |
379 | Opc: Inst->getOpcode(), Idx, Imm: ConstInt->getValue(), Ty: ConstInt->getType(), |
380 | CostKind: TargetTransformInfo::TCK_SizeAndLatency, Inst); |
381 | |
382 | // Ignore cheap integer constants. |
383 | if (Cost > TargetTransformInfo::TCC_Basic) { |
384 | ConstCandMapType::iterator Itr; |
385 | bool Inserted; |
386 | ConstPtrUnionType Cand = ConstInt; |
387 | std::tie(args&: Itr, args&: Inserted) = ConstCandMap.insert(KV: std::make_pair(x&: Cand, y: 0)); |
388 | if (Inserted) { |
389 | ConstIntCandVec.push_back(x: ConstantCandidate(ConstInt)); |
390 | Itr->second = ConstIntCandVec.size() - 1; |
391 | } |
392 | ConstIntCandVec[Itr->second].addUser(Inst, Idx, Cost: *Cost.getValue()); |
393 | LLVM_DEBUG(if (isa<ConstantInt>(Inst->getOperand(Idx))) dbgs() |
394 | << "Collect constant " << *ConstInt << " from " << *Inst |
395 | << " with cost " << Cost << '\n'; |
396 | else dbgs() << "Collect constant " << *ConstInt |
397 | << " indirectly from " << *Inst << " via " |
398 | << *Inst->getOperand(Idx) << " with cost " << Cost |
399 | << '\n';); |
400 | } |
401 | } |
402 | |
403 | /// Record constant GEP expression for instruction Inst at operand index Idx. |
404 | void ConstantHoistingPass::collectConstantCandidates( |
405 | ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx, |
406 | ConstantExpr *ConstExpr) { |
407 | // TODO: Handle vector GEPs |
408 | if (ConstExpr->getType()->isVectorTy()) |
409 | return; |
410 | |
411 | GlobalVariable *BaseGV = dyn_cast<GlobalVariable>(Val: ConstExpr->getOperand(i_nocapture: 0)); |
412 | if (!BaseGV) |
413 | return; |
414 | |
415 | // Get offset from the base GV. |
416 | PointerType *GVPtrTy = cast<PointerType>(Val: BaseGV->getType()); |
417 | IntegerType *OffsetTy = DL->getIndexType(C&: *Ctx, AddressSpace: GVPtrTy->getAddressSpace()); |
418 | APInt Offset(DL->getTypeSizeInBits(Ty: OffsetTy), /*val*/ 0, /*isSigned*/ true); |
419 | auto *GEPO = cast<GEPOperator>(Val: ConstExpr); |
420 | |
421 | // TODO: If we have a mix of inbounds and non-inbounds GEPs, then basing a |
422 | // non-inbounds GEP on an inbounds GEP is potentially incorrect. Restrict to |
423 | // inbounds GEP for now -- alternatively, we could drop inbounds from the |
424 | // constant expression, |
425 | if (!GEPO->isInBounds()) |
426 | return; |
427 | |
428 | if (!GEPO->accumulateConstantOffset(DL: *DL, Offset)) |
429 | return; |
430 | |
431 | if (!Offset.isIntN(N: 32)) |
432 | return; |
433 | |
434 | // A constant GEP expression that has a GlobalVariable as base pointer is |
435 | // usually lowered to a load from constant pool. Such operation is unlikely |
436 | // to be cheaper than compute it by <Base + Offset>, which can be lowered to |
437 | // an ADD instruction or folded into Load/Store instruction. |
438 | InstructionCost Cost = |
439 | TTI->getIntImmCostInst(Opc: Instruction::Add, Idx: 1, Imm: Offset, Ty: OffsetTy, |
440 | CostKind: TargetTransformInfo::TCK_SizeAndLatency, Inst); |
441 | ConstCandVecType &ExprCandVec = ConstGEPCandMap[BaseGV]; |
442 | ConstCandMapType::iterator Itr; |
443 | bool Inserted; |
444 | ConstPtrUnionType Cand = ConstExpr; |
445 | std::tie(args&: Itr, args&: Inserted) = ConstCandMap.insert(KV: std::make_pair(x&: Cand, y: 0)); |
446 | if (Inserted) { |
447 | ExprCandVec.push_back(x: ConstantCandidate( |
448 | ConstantInt::get(Ty: Type::getInt32Ty(C&: *Ctx), V: Offset.getLimitedValue()), |
449 | ConstExpr)); |
450 | Itr->second = ExprCandVec.size() - 1; |
451 | } |
452 | ExprCandVec[Itr->second].addUser(Inst, Idx, Cost: *Cost.getValue()); |
453 | } |
454 | |
455 | /// Check the operand for instruction Inst at index Idx. |
456 | void ConstantHoistingPass::collectConstantCandidates( |
457 | ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx) { |
458 | Value *Opnd = Inst->getOperand(i: Idx); |
459 | |
460 | // Visit constant integers. |
461 | if (auto ConstInt = dyn_cast<ConstantInt>(Val: Opnd)) { |
462 | collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt); |
463 | return; |
464 | } |
465 | |
466 | // Visit cast instructions that have constant integers. |
467 | if (auto CastInst = dyn_cast<Instruction>(Val: Opnd)) { |
468 | // Only visit cast instructions, which have been skipped. All other |
469 | // instructions should have already been visited. |
470 | if (!CastInst->isCast()) |
471 | return; |
472 | |
473 | if (auto *ConstInt = dyn_cast<ConstantInt>(Val: CastInst->getOperand(i: 0))) { |
474 | // Pretend the constant is directly used by the instruction and ignore |
475 | // the cast instruction. |
476 | collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt); |
477 | return; |
478 | } |
479 | } |
480 | |
481 | // Visit constant expressions that have constant integers. |
482 | if (auto ConstExpr = dyn_cast<ConstantExpr>(Val: Opnd)) { |
483 | // Handle constant gep expressions. |
484 | if (ConstHoistGEP && isa<GEPOperator>(Val: ConstExpr)) |
485 | collectConstantCandidates(ConstCandMap, Inst, Idx, ConstExpr); |
486 | |
487 | // Only visit constant cast expressions. |
488 | if (!ConstExpr->isCast()) |
489 | return; |
490 | |
491 | if (auto ConstInt = dyn_cast<ConstantInt>(Val: ConstExpr->getOperand(i_nocapture: 0))) { |
492 | // Pretend the constant is directly used by the instruction and ignore |
493 | // the constant expression. |
494 | collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt); |
495 | return; |
496 | } |
497 | } |
498 | } |
499 | |
500 | /// Scan the instruction for expensive integer constants and record them |
501 | /// in the constant candidate vector. |
502 | void ConstantHoistingPass::collectConstantCandidates( |
503 | ConstCandMapType &ConstCandMap, Instruction *Inst) { |
504 | // Skip all cast instructions. They are visited indirectly later on. |
505 | if (Inst->isCast()) |
506 | return; |
507 | |
508 | // Scan all operands. |
509 | for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) { |
510 | // The cost of materializing the constants (defined in |
511 | // `TargetTransformInfo::getIntImmCostInst`) for instructions which only |
512 | // take constant variables is lower than `TargetTransformInfo::TCC_Basic`. |
513 | // So it's safe for us to collect constant candidates from all |
514 | // IntrinsicInsts. |
515 | if (canReplaceOperandWithVariable(I: Inst, OpIdx: Idx)) { |
516 | collectConstantCandidates(ConstCandMap, Inst, Idx); |
517 | } |
518 | } // end of for all operands |
519 | } |
520 | |
521 | /// Collect all integer constants in the function that cannot be folded |
522 | /// into an instruction itself. |
523 | void ConstantHoistingPass::collectConstantCandidates(Function &Fn) { |
524 | ConstCandMapType ConstCandMap; |
525 | for (BasicBlock &BB : Fn) { |
526 | // Ignore unreachable basic blocks. |
527 | if (!DT->isReachableFromEntry(A: &BB)) |
528 | continue; |
529 | for (Instruction &Inst : BB) |
530 | if (!TTI->preferToKeepConstantsAttached(Inst, Fn)) |
531 | collectConstantCandidates(ConstCandMap, Inst: &Inst); |
532 | } |
533 | } |
534 | |
535 | // This helper function is necessary to deal with values that have different |
536 | // bit widths (APInt Operator- does not like that). If the value cannot be |
537 | // represented in uint64 we return an "empty" APInt. This is then interpreted |
538 | // as the value is not in range. |
539 | static std::optional<APInt> calculateOffsetDiff(const APInt &V1, |
540 | const APInt &V2) { |
541 | std::optional<APInt> Res; |
542 | unsigned BW = V1.getBitWidth() > V2.getBitWidth() ? |
543 | V1.getBitWidth() : V2.getBitWidth(); |
544 | uint64_t LimVal1 = V1.getLimitedValue(); |
545 | uint64_t LimVal2 = V2.getLimitedValue(); |
546 | |
547 | if (LimVal1 == ~0ULL || LimVal2 == ~0ULL) |
548 | return Res; |
549 | |
550 | uint64_t Diff = LimVal1 - LimVal2; |
551 | return APInt(BW, Diff, true); |
552 | } |
553 | |
554 | // From a list of constants, one needs to picked as the base and the other |
555 | // constants will be transformed into an offset from that base constant. The |
556 | // question is which we can pick best? For example, consider these constants |
557 | // and their number of uses: |
558 | // |
559 | // Constants| 2 | 4 | 12 | 42 | |
560 | // NumUses | 3 | 2 | 8 | 7 | |
561 | // |
562 | // Selecting constant 12 because it has the most uses will generate negative |
563 | // offsets for constants 2 and 4 (i.e. -10 and -8 respectively). If negative |
564 | // offsets lead to less optimal code generation, then there might be better |
565 | // solutions. Suppose immediates in the range of 0..35 are most optimally |
566 | // supported by the architecture, then selecting constant 2 is most optimal |
567 | // because this will generate offsets: 0, 2, 10, 40. Offsets 0, 2 and 10 are in |
568 | // range 0..35, and thus 3 + 2 + 8 = 13 uses are in range. Selecting 12 would |
569 | // have only 8 uses in range, so choosing 2 as a base is more optimal. Thus, in |
570 | // selecting the base constant the range of the offsets is a very important |
571 | // factor too that we take into account here. This algorithm calculates a total |
572 | // costs for selecting a constant as the base and substract the costs if |
573 | // immediates are out of range. It has quadratic complexity, so we call this |
574 | // function only when we're optimising for size and there are less than 100 |
575 | // constants, we fall back to the straightforward algorithm otherwise |
576 | // which does not do all the offset calculations. |
577 | unsigned |
578 | ConstantHoistingPass::maximizeConstantsInRange(ConstCandVecType::iterator S, |
579 | ConstCandVecType::iterator E, |
580 | ConstCandVecType::iterator &MaxCostItr) { |
581 | unsigned NumUses = 0; |
582 | |
583 | if (!OptForSize || std::distance(first: S,last: E) > 100) { |
584 | for (auto ConstCand = S; ConstCand != E; ++ConstCand) { |
585 | NumUses += ConstCand->Uses.size(); |
586 | if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost) |
587 | MaxCostItr = ConstCand; |
588 | } |
589 | return NumUses; |
590 | } |
591 | |
592 | LLVM_DEBUG(dbgs() << "== Maximize constants in range ==\n" ); |
593 | InstructionCost MaxCost = -1; |
594 | for (auto ConstCand = S; ConstCand != E; ++ConstCand) { |
595 | auto Value = ConstCand->ConstInt->getValue(); |
596 | Type *Ty = ConstCand->ConstInt->getType(); |
597 | InstructionCost Cost = 0; |
598 | NumUses += ConstCand->Uses.size(); |
599 | LLVM_DEBUG(dbgs() << "= Constant: " << ConstCand->ConstInt->getValue() |
600 | << "\n" ); |
601 | |
602 | for (auto User : ConstCand->Uses) { |
603 | unsigned Opcode = User.Inst->getOpcode(); |
604 | unsigned OpndIdx = User.OpndIdx; |
605 | Cost += TTI->getIntImmCostInst(Opc: Opcode, Idx: OpndIdx, Imm: Value, Ty, |
606 | CostKind: TargetTransformInfo::TCK_SizeAndLatency); |
607 | LLVM_DEBUG(dbgs() << "Cost: " << Cost << "\n" ); |
608 | |
609 | for (auto C2 = S; C2 != E; ++C2) { |
610 | std::optional<APInt> Diff = calculateOffsetDiff( |
611 | V1: C2->ConstInt->getValue(), V2: ConstCand->ConstInt->getValue()); |
612 | if (Diff) { |
613 | const InstructionCost ImmCosts = |
614 | TTI->getIntImmCodeSizeCost(Opc: Opcode, Idx: OpndIdx, Imm: *Diff, Ty); |
615 | Cost -= ImmCosts; |
616 | LLVM_DEBUG(dbgs() << "Offset " << *Diff << " " |
617 | << "has penalty: " << ImmCosts << "\n" |
618 | << "Adjusted cost: " << Cost << "\n" ); |
619 | } |
620 | } |
621 | } |
622 | LLVM_DEBUG(dbgs() << "Cumulative cost: " << Cost << "\n" ); |
623 | if (Cost > MaxCost) { |
624 | MaxCost = Cost; |
625 | MaxCostItr = ConstCand; |
626 | LLVM_DEBUG(dbgs() << "New candidate: " << MaxCostItr->ConstInt->getValue() |
627 | << "\n" ); |
628 | } |
629 | } |
630 | return NumUses; |
631 | } |
632 | |
633 | /// Find the base constant within the given range and rebase all other |
634 | /// constants with respect to the base constant. |
635 | void ConstantHoistingPass::findAndMakeBaseConstant( |
636 | ConstCandVecType::iterator S, ConstCandVecType::iterator E, |
637 | SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec) { |
638 | auto MaxCostItr = S; |
639 | unsigned NumUses = maximizeConstantsInRange(S, E, MaxCostItr); |
640 | |
641 | // Don't hoist constants that have only one use. |
642 | if (NumUses <= 1) |
643 | return; |
644 | |
645 | ConstantInt *ConstInt = MaxCostItr->ConstInt; |
646 | ConstantExpr *ConstExpr = MaxCostItr->ConstExpr; |
647 | ConstantInfo ConstInfo; |
648 | ConstInfo.BaseInt = ConstInt; |
649 | ConstInfo.BaseExpr = ConstExpr; |
650 | Type *Ty = ConstInt->getType(); |
651 | |
652 | // Rebase the constants with respect to the base constant. |
653 | for (auto ConstCand = S; ConstCand != E; ++ConstCand) { |
654 | APInt Diff = ConstCand->ConstInt->getValue() - ConstInt->getValue(); |
655 | Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, V: Diff); |
656 | Type *ConstTy = |
657 | ConstCand->ConstExpr ? ConstCand->ConstExpr->getType() : nullptr; |
658 | ConstInfo.RebasedConstants.push_back( |
659 | Elt: RebasedConstantInfo(std::move(ConstCand->Uses), Offset, ConstTy)); |
660 | } |
661 | ConstInfoVec.push_back(Elt: std::move(ConstInfo)); |
662 | } |
663 | |
664 | /// Finds and combines constant candidates that can be easily |
665 | /// rematerialized with an add from a common base constant. |
666 | void ConstantHoistingPass::findBaseConstants(GlobalVariable *BaseGV) { |
667 | // If BaseGV is nullptr, find base among candidate constant integers; |
668 | // Otherwise find base among constant GEPs that share the same BaseGV. |
669 | ConstCandVecType &ConstCandVec = BaseGV ? |
670 | ConstGEPCandMap[BaseGV] : ConstIntCandVec; |
671 | ConstInfoVecType &ConstInfoVec = BaseGV ? |
672 | ConstGEPInfoMap[BaseGV] : ConstIntInfoVec; |
673 | |
674 | // Sort the constants by value and type. This invalidates the mapping! |
675 | llvm::stable_sort(Range&: ConstCandVec, C: [](const ConstantCandidate &LHS, |
676 | const ConstantCandidate &RHS) { |
677 | if (LHS.ConstInt->getType() != RHS.ConstInt->getType()) |
678 | return LHS.ConstInt->getBitWidth() < RHS.ConstInt->getBitWidth(); |
679 | return LHS.ConstInt->getValue().ult(RHS: RHS.ConstInt->getValue()); |
680 | }); |
681 | |
682 | // Simple linear scan through the sorted constant candidate vector for viable |
683 | // merge candidates. |
684 | auto MinValItr = ConstCandVec.begin(); |
685 | for (auto CC = std::next(x: ConstCandVec.begin()), E = ConstCandVec.end(); |
686 | CC != E; ++CC) { |
687 | if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) { |
688 | Type *MemUseValTy = nullptr; |
689 | for (auto &U : CC->Uses) { |
690 | auto *UI = U.Inst; |
691 | if (LoadInst *LI = dyn_cast<LoadInst>(Val: UI)) { |
692 | MemUseValTy = LI->getType(); |
693 | break; |
694 | } else if (StoreInst *SI = dyn_cast<StoreInst>(Val: UI)) { |
695 | // Make sure the constant is used as pointer operand of the StoreInst. |
696 | if (SI->getPointerOperand() == SI->getOperand(i_nocapture: U.OpndIdx)) { |
697 | MemUseValTy = SI->getValueOperand()->getType(); |
698 | break; |
699 | } |
700 | } |
701 | } |
702 | |
703 | // Check if the constant is in range of an add with immediate. |
704 | APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue(); |
705 | if ((Diff.getBitWidth() <= 64) && |
706 | TTI->isLegalAddImmediate(Imm: Diff.getSExtValue()) && |
707 | // Check if Diff can be used as offset in addressing mode of the user |
708 | // memory instruction. |
709 | (!MemUseValTy || TTI->isLegalAddressingMode(Ty: MemUseValTy, |
710 | /*BaseGV*/nullptr, /*BaseOffset*/Diff.getSExtValue(), |
711 | /*HasBaseReg*/true, /*Scale*/0))) |
712 | continue; |
713 | } |
714 | // We either have now a different constant type or the constant is not in |
715 | // range of an add with immediate anymore. |
716 | findAndMakeBaseConstant(S: MinValItr, E: CC, ConstInfoVec); |
717 | // Start a new base constant search. |
718 | MinValItr = CC; |
719 | } |
720 | // Finalize the last base constant search. |
721 | findAndMakeBaseConstant(S: MinValItr, E: ConstCandVec.end(), ConstInfoVec); |
722 | } |
723 | |
724 | /// Updates the operand at Idx in instruction Inst with the result of |
725 | /// instruction Mat. If the instruction is a PHI node then special |
726 | /// handling for duplicate values from the same incoming basic block is |
727 | /// required. |
728 | /// \return The update will always succeed, but the return value indicated if |
729 | /// Mat was used for the update or not. |
730 | static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) { |
731 | if (auto PHI = dyn_cast<PHINode>(Val: Inst)) { |
732 | // Check if any previous operand of the PHI node has the same incoming basic |
733 | // block. This is a very odd case that happens when the incoming basic block |
734 | // has a switch statement. In this case use the same value as the previous |
735 | // operand(s), otherwise we will fail verification due to different values. |
736 | // The values are actually the same, but the variable names are different |
737 | // and the verifier doesn't like that. |
738 | BasicBlock *IncomingBB = PHI->getIncomingBlock(i: Idx); |
739 | for (unsigned i = 0; i < Idx; ++i) { |
740 | if (PHI->getIncomingBlock(i) == IncomingBB) { |
741 | Value *IncomingVal = PHI->getIncomingValue(i); |
742 | Inst->setOperand(i: Idx, Val: IncomingVal); |
743 | return false; |
744 | } |
745 | } |
746 | } |
747 | |
748 | Inst->setOperand(i: Idx, Val: Mat); |
749 | return true; |
750 | } |
751 | |
752 | /// Emit materialization code for all rebased constants and update their |
753 | /// users. |
754 | void ConstantHoistingPass::emitBaseConstants(Instruction *Base, |
755 | UserAdjustment *Adj) { |
756 | Instruction *Mat = Base; |
757 | |
758 | // The same offset can be dereferenced to different types in nested struct. |
759 | if (!Adj->Offset && Adj->Ty && Adj->Ty != Base->getType()) |
760 | Adj->Offset = ConstantInt::get(Ty: Type::getInt32Ty(C&: *Ctx), V: 0); |
761 | |
762 | if (Adj->Offset) { |
763 | if (Adj->Ty) { |
764 | // Constant being rebased is a ConstantExpr. |
765 | Mat = GetElementPtrInst::Create(PointeeType: Type::getInt8Ty(C&: *Ctx), Ptr: Base, IdxList: Adj->Offset, |
766 | NameStr: "mat_gep" , InsertBefore: Adj->MatInsertPt); |
767 | // Hide it behind a bitcast. |
768 | Mat = new BitCastInst(Mat, Adj->Ty, "mat_bitcast" , |
769 | Adj->MatInsertPt->getIterator()); |
770 | } else |
771 | // Constant being rebased is a ConstantInt. |
772 | Mat = |
773 | BinaryOperator::Create(Op: Instruction::Add, S1: Base, S2: Adj->Offset, |
774 | Name: "const_mat" , InsertBefore: Adj->MatInsertPt->getIterator()); |
775 | |
776 | LLVM_DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0) |
777 | << " + " << *Adj->Offset << ") in BB " |
778 | << Mat->getParent()->getName() << '\n' |
779 | << *Mat << '\n'); |
780 | Mat->setDebugLoc(Adj->User.Inst->getDebugLoc()); |
781 | } |
782 | Value *Opnd = Adj->User.Inst->getOperand(i: Adj->User.OpndIdx); |
783 | |
784 | // Visit constant integer. |
785 | if (isa<ConstantInt>(Val: Opnd)) { |
786 | LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n'); |
787 | if (!updateOperand(Inst: Adj->User.Inst, Idx: Adj->User.OpndIdx, Mat) && Adj->Offset) |
788 | Mat->eraseFromParent(); |
789 | LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n'); |
790 | return; |
791 | } |
792 | |
793 | // Visit cast instruction. |
794 | if (auto CastInst = dyn_cast<Instruction>(Val: Opnd)) { |
795 | assert(CastInst->isCast() && "Expected an cast instruction!" ); |
796 | // Check if we already have visited this cast instruction before to avoid |
797 | // unnecessary cloning. |
798 | Instruction *&ClonedCastInst = ClonedCastMap[CastInst]; |
799 | if (!ClonedCastInst) { |
800 | ClonedCastInst = CastInst->clone(); |
801 | ClonedCastInst->setOperand(i: 0, Val: Mat); |
802 | ClonedCastInst->insertAfter(InsertPos: CastInst); |
803 | // Use the same debug location as the original cast instruction. |
804 | ClonedCastInst->setDebugLoc(CastInst->getDebugLoc()); |
805 | LLVM_DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n' |
806 | << "To : " << *ClonedCastInst << '\n'); |
807 | } |
808 | |
809 | LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n'); |
810 | updateOperand(Inst: Adj->User.Inst, Idx: Adj->User.OpndIdx, Mat: ClonedCastInst); |
811 | LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n'); |
812 | return; |
813 | } |
814 | |
815 | // Visit constant expression. |
816 | if (auto ConstExpr = dyn_cast<ConstantExpr>(Val: Opnd)) { |
817 | if (isa<GEPOperator>(Val: ConstExpr)) { |
818 | // Operand is a ConstantGEP, replace it. |
819 | updateOperand(Inst: Adj->User.Inst, Idx: Adj->User.OpndIdx, Mat); |
820 | return; |
821 | } |
822 | |
823 | // Aside from constant GEPs, only constant cast expressions are collected. |
824 | assert(ConstExpr->isCast() && "ConstExpr should be a cast" ); |
825 | Instruction *ConstExprInst = ConstExpr->getAsInstruction(); |
826 | ConstExprInst->insertBefore(InsertPos: Adj->MatInsertPt); |
827 | ConstExprInst->setOperand(i: 0, Val: Mat); |
828 | |
829 | // Use the same debug location as the instruction we are about to update. |
830 | ConstExprInst->setDebugLoc(Adj->User.Inst->getDebugLoc()); |
831 | |
832 | LLVM_DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n' |
833 | << "From : " << *ConstExpr << '\n'); |
834 | LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n'); |
835 | if (!updateOperand(Inst: Adj->User.Inst, Idx: Adj->User.OpndIdx, Mat: ConstExprInst)) { |
836 | ConstExprInst->eraseFromParent(); |
837 | if (Adj->Offset) |
838 | Mat->eraseFromParent(); |
839 | } |
840 | LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n'); |
841 | return; |
842 | } |
843 | } |
844 | |
845 | /// Hoist and hide the base constant behind a bitcast and emit |
846 | /// materialization code for derived constants. |
847 | bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) { |
848 | bool MadeChange = false; |
849 | SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec = |
850 | BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec; |
851 | for (const consthoist::ConstantInfo &ConstInfo : ConstInfoVec) { |
852 | SmallVector<BasicBlock::iterator, 4> MatInsertPts; |
853 | collectMatInsertPts(RebasedConstants: ConstInfo.RebasedConstants, MatInsertPts); |
854 | SetVector<BasicBlock::iterator> IPSet = |
855 | findConstantInsertionPoint(ConstInfo, MatInsertPts); |
856 | // We can have an empty set if the function contains unreachable blocks. |
857 | if (IPSet.empty()) |
858 | continue; |
859 | |
860 | unsigned UsesNum = 0; |
861 | unsigned ReBasesNum = 0; |
862 | unsigned NotRebasedNum = 0; |
863 | for (const BasicBlock::iterator &IP : IPSet) { |
864 | // First, collect constants depending on this IP of the base. |
865 | UsesNum = 0; |
866 | SmallVector<UserAdjustment, 4> ToBeRebased; |
867 | unsigned MatCtr = 0; |
868 | for (auto const &RCI : ConstInfo.RebasedConstants) { |
869 | UsesNum += RCI.Uses.size(); |
870 | for (auto const &U : RCI.Uses) { |
871 | const BasicBlock::iterator &MatInsertPt = MatInsertPts[MatCtr++]; |
872 | BasicBlock *OrigMatInsertBB = MatInsertPt->getParent(); |
873 | // If Base constant is to be inserted in multiple places, |
874 | // generate rebase for U using the Base dominating U. |
875 | if (IPSet.size() == 1 || |
876 | DT->dominates(A: IP->getParent(), B: OrigMatInsertBB)) |
877 | ToBeRebased.emplace_back(Args: RCI.Offset, Args: RCI.Ty, Args: MatInsertPt, Args: U); |
878 | } |
879 | } |
880 | |
881 | // If only few constants depend on this IP of base, skip rebasing, |
882 | // assuming the base and the rebased have the same materialization cost. |
883 | if (ToBeRebased.size() < MinNumOfDependentToRebase) { |
884 | NotRebasedNum += ToBeRebased.size(); |
885 | continue; |
886 | } |
887 | |
888 | // Emit an instance of the base at this IP. |
889 | Instruction *Base = nullptr; |
890 | // Hoist and hide the base constant behind a bitcast. |
891 | if (ConstInfo.BaseExpr) { |
892 | assert(BaseGV && "A base constant expression must have an base GV" ); |
893 | Type *Ty = ConstInfo.BaseExpr->getType(); |
894 | Base = new BitCastInst(ConstInfo.BaseExpr, Ty, "const" , IP); |
895 | } else { |
896 | IntegerType *Ty = ConstInfo.BaseInt->getIntegerType(); |
897 | Base = new BitCastInst(ConstInfo.BaseInt, Ty, "const" , IP); |
898 | } |
899 | |
900 | Base->setDebugLoc(IP->getDebugLoc()); |
901 | |
902 | LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseInt |
903 | << ") to BB " << IP->getParent()->getName() << '\n' |
904 | << *Base << '\n'); |
905 | |
906 | // Emit materialization code for rebased constants depending on this IP. |
907 | for (UserAdjustment &R : ToBeRebased) { |
908 | emitBaseConstants(Base, Adj: &R); |
909 | ReBasesNum++; |
910 | // Use the same debug location as the last user of the constant. |
911 | Base->setDebugLoc(DILocation::getMergedLocation( |
912 | LocA: Base->getDebugLoc(), LocB: R.User.Inst->getDebugLoc())); |
913 | } |
914 | assert(!Base->use_empty() && "The use list is empty!?" ); |
915 | assert(isa<Instruction>(Base->user_back()) && |
916 | "All uses should be instructions." ); |
917 | } |
918 | (void)UsesNum; |
919 | (void)ReBasesNum; |
920 | (void)NotRebasedNum; |
921 | // Expect all uses are rebased after rebase is done. |
922 | assert(UsesNum == (ReBasesNum + NotRebasedNum) && |
923 | "Not all uses are rebased" ); |
924 | |
925 | NumConstantsHoisted++; |
926 | |
927 | // Base constant is also included in ConstInfo.RebasedConstants, so |
928 | // deduct 1 from ConstInfo.RebasedConstants.size(). |
929 | NumConstantsRebased += ConstInfo.RebasedConstants.size() - 1; |
930 | |
931 | MadeChange = true; |
932 | } |
933 | return MadeChange; |
934 | } |
935 | |
936 | /// Check all cast instructions we made a copy of and remove them if they |
937 | /// have no more users. |
938 | void ConstantHoistingPass::deleteDeadCastInst() const { |
939 | for (auto const &I : ClonedCastMap) |
940 | if (I.first->use_empty()) |
941 | I.first->eraseFromParent(); |
942 | } |
943 | |
944 | /// Optimize expensive integer constants in the given function. |
945 | bool ConstantHoistingPass::runImpl(Function &Fn, TargetTransformInfo &TTI, |
946 | DominatorTree &DT, BlockFrequencyInfo *BFI, |
947 | BasicBlock &Entry, ProfileSummaryInfo *PSI) { |
948 | this->TTI = &TTI; |
949 | this->DT = &DT; |
950 | this->BFI = BFI; |
951 | this->DL = &Fn.getParent()->getDataLayout(); |
952 | this->Ctx = &Fn.getContext(); |
953 | this->Entry = &Entry; |
954 | this->PSI = PSI; |
955 | this->OptForSize = Entry.getParent()->hasOptSize() || |
956 | llvm::shouldOptimizeForSize(F: Entry.getParent(), PSI, BFI, |
957 | QueryType: PGSOQueryType::IRPass); |
958 | |
959 | // Collect all constant candidates. |
960 | collectConstantCandidates(Fn); |
961 | |
962 | // Combine constants that can be easily materialized with an add from a common |
963 | // base constant. |
964 | if (!ConstIntCandVec.empty()) |
965 | findBaseConstants(BaseGV: nullptr); |
966 | for (const auto &MapEntry : ConstGEPCandMap) |
967 | if (!MapEntry.second.empty()) |
968 | findBaseConstants(BaseGV: MapEntry.first); |
969 | |
970 | // Finally hoist the base constant and emit materialization code for dependent |
971 | // constants. |
972 | bool MadeChange = false; |
973 | if (!ConstIntInfoVec.empty()) |
974 | MadeChange = emitBaseConstants(BaseGV: nullptr); |
975 | for (const auto &MapEntry : ConstGEPInfoMap) |
976 | if (!MapEntry.second.empty()) |
977 | MadeChange |= emitBaseConstants(BaseGV: MapEntry.first); |
978 | |
979 | |
980 | // Cleanup dead instructions. |
981 | deleteDeadCastInst(); |
982 | |
983 | cleanup(); |
984 | |
985 | return MadeChange; |
986 | } |
987 | |
988 | PreservedAnalyses ConstantHoistingPass::run(Function &F, |
989 | FunctionAnalysisManager &AM) { |
990 | auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F); |
991 | auto &TTI = AM.getResult<TargetIRAnalysis>(IR&: F); |
992 | auto BFI = ConstHoistWithBlockFrequency |
993 | ? &AM.getResult<BlockFrequencyAnalysis>(IR&: F) |
994 | : nullptr; |
995 | auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F); |
996 | auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(IR&: *F.getParent()); |
997 | if (!runImpl(Fn&: F, TTI, DT, BFI, Entry&: F.getEntryBlock(), PSI)) |
998 | return PreservedAnalyses::all(); |
999 | |
1000 | PreservedAnalyses PA; |
1001 | PA.preserveSet<CFGAnalyses>(); |
1002 | return PA; |
1003 | } |
1004 | |