1 //===- ConstantHoisting.cpp - Prepare code for expensive constants --------===//
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 #include "llvm/Transforms/Scalar.h"
37 #include "llvm/ADT/SmallSet.h"
38 #include "llvm/ADT/SmallVector.h"
39 #include "llvm/ADT/Statistic.h"
40 #include "llvm/Analysis/TargetTransformInfo.h"
41 #include "llvm/IR/Constants.h"
42 #include "llvm/IR/Dominators.h"
43 #include "llvm/IR/IntrinsicInst.h"
44 #include "llvm/Pass.h"
45 #include "llvm/Support/Debug.h"
46 #include "llvm/Support/raw_ostream.h"
47 #include <tuple>
48
49 using namespace llvm;
50
51 #define DEBUG_TYPE "consthoist"
52
53 STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
54 STATISTIC(NumConstantsRebased, "Number of constants rebased");
55
56 namespace {
57 struct ConstantUser;
58 struct RebasedConstantInfo;
59
60 typedef SmallVector<ConstantUser, 8> ConstantUseListType;
61 typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType;
62
63 /// \brief Keeps track of the user of a constant and the operand index where the
64 /// constant is used.
65 struct ConstantUser {
66 Instruction *Inst;
67 unsigned OpndIdx;
68
ConstantUser__anon298d3b100111::ConstantUser69 ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) { }
70 };
71
72 /// \brief Keeps track of a constant candidate and its uses.
73 struct ConstantCandidate {
74 ConstantUseListType Uses;
75 ConstantInt *ConstInt;
76 unsigned CumulativeCost;
77
ConstantCandidate__anon298d3b100111::ConstantCandidate78 ConstantCandidate(ConstantInt *ConstInt)
79 : ConstInt(ConstInt), CumulativeCost(0) { }
80
81 /// \brief Add the user to the use list and update the cost.
addUser__anon298d3b100111::ConstantCandidate82 void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
83 CumulativeCost += Cost;
84 Uses.push_back(ConstantUser(Inst, Idx));
85 }
86 };
87
88 /// \brief This represents a constant that has been rebased with respect to a
89 /// base constant. The difference to the base constant is recorded in Offset.
90 struct RebasedConstantInfo {
91 ConstantUseListType Uses;
92 Constant *Offset;
93
RebasedConstantInfo__anon298d3b100111::RebasedConstantInfo94 RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
95 : Uses(std::move(Uses)), Offset(Offset) { }
96 };
97
98 /// \brief A base constant and all its rebased constants.
99 struct ConstantInfo {
100 ConstantInt *BaseConstant;
101 RebasedConstantListType RebasedConstants;
102 };
103
104 /// \brief The constant hoisting pass.
105 class ConstantHoisting : public FunctionPass {
106 typedef DenseMap<ConstantInt *, unsigned> ConstCandMapType;
107 typedef std::vector<ConstantCandidate> ConstCandVecType;
108
109 const TargetTransformInfo *TTI;
110 DominatorTree *DT;
111 BasicBlock *Entry;
112
113 /// Keeps track of constant candidates found in the function.
114 ConstCandVecType ConstCandVec;
115
116 /// Keep track of cast instructions we already cloned.
117 SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
118
119 /// These are the final constants we decided to hoist.
120 SmallVector<ConstantInfo, 8> ConstantVec;
121 public:
122 static char ID; // Pass identification, replacement for typeid
ConstantHoisting()123 ConstantHoisting() : FunctionPass(ID), TTI(nullptr), DT(nullptr),
124 Entry(nullptr) {
125 initializeConstantHoistingPass(*PassRegistry::getPassRegistry());
126 }
127
128 bool runOnFunction(Function &Fn) override;
129
getPassName() const130 const char *getPassName() const override { return "Constant Hoisting"; }
131
getAnalysisUsage(AnalysisUsage & AU) const132 void getAnalysisUsage(AnalysisUsage &AU) const override {
133 AU.setPreservesCFG();
134 AU.addRequired<DominatorTreeWrapperPass>();
135 AU.addRequired<TargetTransformInfoWrapperPass>();
136 }
137
138 private:
139 /// \brief Initialize the pass.
setup(Function & Fn)140 void setup(Function &Fn) {
141 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
142 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn);
143 Entry = &Fn.getEntryBlock();
144 }
145
146 /// \brief Cleanup.
cleanup()147 void cleanup() {
148 ConstantVec.clear();
149 ClonedCastMap.clear();
150 ConstCandVec.clear();
151
152 TTI = nullptr;
153 DT = nullptr;
154 Entry = nullptr;
155 }
156
157 Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
158 Instruction *findConstantInsertionPoint(const ConstantInfo &ConstInfo) const;
159 void collectConstantCandidates(ConstCandMapType &ConstCandMap,
160 Instruction *Inst, unsigned Idx,
161 ConstantInt *ConstInt);
162 void collectConstantCandidates(ConstCandMapType &ConstCandMap,
163 Instruction *Inst);
164 void collectConstantCandidates(Function &Fn);
165 void findAndMakeBaseConstant(ConstCandVecType::iterator S,
166 ConstCandVecType::iterator E);
167 void findBaseConstants();
168 void emitBaseConstants(Instruction *Base, Constant *Offset,
169 const ConstantUser &ConstUser);
170 bool emitBaseConstants();
171 void deleteDeadCastInst() const;
172 bool optimizeConstants(Function &Fn);
173 };
174 }
175
176 char ConstantHoisting::ID = 0;
177 INITIALIZE_PASS_BEGIN(ConstantHoisting, "consthoist", "Constant Hoisting",
178 false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)179 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
180 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
181 INITIALIZE_PASS_END(ConstantHoisting, "consthoist", "Constant Hoisting",
182 false, false)
183
184 FunctionPass *llvm::createConstantHoistingPass() {
185 return new ConstantHoisting();
186 }
187
188 /// \brief Perform the constant hoisting optimization for the given function.
runOnFunction(Function & Fn)189 bool ConstantHoisting::runOnFunction(Function &Fn) {
190 if (skipOptnoneFunction(Fn))
191 return false;
192
193 DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
194 DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');
195
196 setup(Fn);
197
198 bool MadeChange = optimizeConstants(Fn);
199
200 if (MadeChange) {
201 DEBUG(dbgs() << "********** Function after Constant Hoisting: "
202 << Fn.getName() << '\n');
203 DEBUG(dbgs() << Fn);
204 }
205 DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
206
207 cleanup();
208
209 return MadeChange;
210 }
211
212
213 /// \brief Find the constant materialization insertion point.
findMatInsertPt(Instruction * Inst,unsigned Idx) const214 Instruction *ConstantHoisting::findMatInsertPt(Instruction *Inst,
215 unsigned Idx) const {
216 // If the operand is a cast instruction, then we have to materialize the
217 // constant before the cast instruction.
218 if (Idx != ~0U) {
219 Value *Opnd = Inst->getOperand(Idx);
220 if (auto CastInst = dyn_cast<Instruction>(Opnd))
221 if (CastInst->isCast())
222 return CastInst;
223 }
224
225 // The simple and common case. This also includes constant expressions.
226 if (!isa<PHINode>(Inst) && !Inst->isEHPad())
227 return Inst;
228
229 // We can't insert directly before a phi node or an eh pad. Insert before
230 // the terminator of the incoming or dominating block.
231 assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!");
232 if (Idx != ~0U && isa<PHINode>(Inst))
233 return cast<PHINode>(Inst)->getIncomingBlock(Idx)->getTerminator();
234
235 BasicBlock *IDom = DT->getNode(Inst->getParent())->getIDom()->getBlock();
236 return IDom->getTerminator();
237 }
238
239 /// \brief Find an insertion point that dominates all uses.
240 Instruction *ConstantHoisting::
findConstantInsertionPoint(const ConstantInfo & ConstInfo) const241 findConstantInsertionPoint(const ConstantInfo &ConstInfo) const {
242 assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
243 // Collect all basic blocks.
244 SmallPtrSet<BasicBlock *, 8> BBs;
245 for (auto const &RCI : ConstInfo.RebasedConstants)
246 for (auto const &U : RCI.Uses)
247 BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent());
248
249 if (BBs.count(Entry))
250 return &Entry->front();
251
252 while (BBs.size() >= 2) {
253 BasicBlock *BB, *BB1, *BB2;
254 BB1 = *BBs.begin();
255 BB2 = *std::next(BBs.begin());
256 BB = DT->findNearestCommonDominator(BB1, BB2);
257 if (BB == Entry)
258 return &Entry->front();
259 BBs.erase(BB1);
260 BBs.erase(BB2);
261 BBs.insert(BB);
262 }
263 assert((BBs.size() == 1) && "Expected only one element.");
264 Instruction &FirstInst = (*BBs.begin())->front();
265 return findMatInsertPt(&FirstInst);
266 }
267
268
269 /// \brief Record constant integer ConstInt for instruction Inst at operand
270 /// index Idx.
271 ///
272 /// The operand at index Idx is not necessarily the constant integer itself. It
273 /// could also be a cast instruction or a constant expression that uses the
274 // constant integer.
collectConstantCandidates(ConstCandMapType & ConstCandMap,Instruction * Inst,unsigned Idx,ConstantInt * ConstInt)275 void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
276 Instruction *Inst,
277 unsigned Idx,
278 ConstantInt *ConstInt) {
279 unsigned Cost;
280 // Ask the target about the cost of materializing the constant for the given
281 // instruction and operand index.
282 if (auto IntrInst = dyn_cast<IntrinsicInst>(Inst))
283 Cost = TTI->getIntImmCost(IntrInst->getIntrinsicID(), Idx,
284 ConstInt->getValue(), ConstInt->getType());
285 else
286 Cost = TTI->getIntImmCost(Inst->getOpcode(), Idx, ConstInt->getValue(),
287 ConstInt->getType());
288
289 // Ignore cheap integer constants.
290 if (Cost > TargetTransformInfo::TCC_Basic) {
291 ConstCandMapType::iterator Itr;
292 bool Inserted;
293 std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(ConstInt, 0));
294 if (Inserted) {
295 ConstCandVec.push_back(ConstantCandidate(ConstInt));
296 Itr->second = ConstCandVec.size() - 1;
297 }
298 ConstCandVec[Itr->second].addUser(Inst, Idx, Cost);
299 DEBUG(if (isa<ConstantInt>(Inst->getOperand(Idx)))
300 dbgs() << "Collect constant " << *ConstInt << " from " << *Inst
301 << " with cost " << Cost << '\n';
302 else
303 dbgs() << "Collect constant " << *ConstInt << " indirectly from "
304 << *Inst << " via " << *Inst->getOperand(Idx) << " with cost "
305 << Cost << '\n';
306 );
307 }
308 }
309
310 /// \brief Scan the instruction for expensive integer constants and record them
311 /// in the constant candidate vector.
collectConstantCandidates(ConstCandMapType & ConstCandMap,Instruction * Inst)312 void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
313 Instruction *Inst) {
314 // Skip all cast instructions. They are visited indirectly later on.
315 if (Inst->isCast())
316 return;
317
318 // Can't handle inline asm. Skip it.
319 if (auto Call = dyn_cast<CallInst>(Inst))
320 if (isa<InlineAsm>(Call->getCalledValue()))
321 return;
322
323 // Scan all operands.
324 for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
325 Value *Opnd = Inst->getOperand(Idx);
326
327 // Visit constant integers.
328 if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
329 collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
330 continue;
331 }
332
333 // Visit cast instructions that have constant integers.
334 if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
335 // Only visit cast instructions, which have been skipped. All other
336 // instructions should have already been visited.
337 if (!CastInst->isCast())
338 continue;
339
340 if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
341 // Pretend the constant is directly used by the instruction and ignore
342 // the cast instruction.
343 collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
344 continue;
345 }
346 }
347
348 // Visit constant expressions that have constant integers.
349 if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
350 // Only visit constant cast expressions.
351 if (!ConstExpr->isCast())
352 continue;
353
354 if (auto ConstInt = dyn_cast<ConstantInt>(ConstExpr->getOperand(0))) {
355 // Pretend the constant is directly used by the instruction and ignore
356 // the constant expression.
357 collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
358 continue;
359 }
360 }
361 } // end of for all operands
362 }
363
364 /// \brief Collect all integer constants in the function that cannot be folded
365 /// into an instruction itself.
collectConstantCandidates(Function & Fn)366 void ConstantHoisting::collectConstantCandidates(Function &Fn) {
367 ConstCandMapType ConstCandMap;
368 for (BasicBlock &BB : Fn)
369 for (Instruction &Inst : BB)
370 collectConstantCandidates(ConstCandMap, &Inst);
371 }
372
373 /// \brief Find the base constant within the given range and rebase all other
374 /// constants with respect to the base constant.
findAndMakeBaseConstant(ConstCandVecType::iterator S,ConstCandVecType::iterator E)375 void ConstantHoisting::findAndMakeBaseConstant(ConstCandVecType::iterator S,
376 ConstCandVecType::iterator E) {
377 auto MaxCostItr = S;
378 unsigned NumUses = 0;
379 // Use the constant that has the maximum cost as base constant.
380 for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
381 NumUses += ConstCand->Uses.size();
382 if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
383 MaxCostItr = ConstCand;
384 }
385
386 // Don't hoist constants that have only one use.
387 if (NumUses <= 1)
388 return;
389
390 ConstantInfo ConstInfo;
391 ConstInfo.BaseConstant = MaxCostItr->ConstInt;
392 Type *Ty = ConstInfo.BaseConstant->getType();
393
394 // Rebase the constants with respect to the base constant.
395 for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
396 APInt Diff = ConstCand->ConstInt->getValue() -
397 ConstInfo.BaseConstant->getValue();
398 Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff);
399 ConstInfo.RebasedConstants.push_back(
400 RebasedConstantInfo(std::move(ConstCand->Uses), Offset));
401 }
402 ConstantVec.push_back(std::move(ConstInfo));
403 }
404
405 /// \brief Finds and combines constant candidates that can be easily
406 /// rematerialized with an add from a common base constant.
findBaseConstants()407 void ConstantHoisting::findBaseConstants() {
408 // Sort the constants by value and type. This invalidates the mapping!
409 std::sort(ConstCandVec.begin(), ConstCandVec.end(),
410 [](const ConstantCandidate &LHS, const ConstantCandidate &RHS) {
411 if (LHS.ConstInt->getType() != RHS.ConstInt->getType())
412 return LHS.ConstInt->getType()->getBitWidth() <
413 RHS.ConstInt->getType()->getBitWidth();
414 return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue());
415 });
416
417 // Simple linear scan through the sorted constant candidate vector for viable
418 // merge candidates.
419 auto MinValItr = ConstCandVec.begin();
420 for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end();
421 CC != E; ++CC) {
422 if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
423 // Check if the constant is in range of an add with immediate.
424 APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue();
425 if ((Diff.getBitWidth() <= 64) &&
426 TTI->isLegalAddImmediate(Diff.getSExtValue()))
427 continue;
428 }
429 // We either have now a different constant type or the constant is not in
430 // range of an add with immediate anymore.
431 findAndMakeBaseConstant(MinValItr, CC);
432 // Start a new base constant search.
433 MinValItr = CC;
434 }
435 // Finalize the last base constant search.
436 findAndMakeBaseConstant(MinValItr, ConstCandVec.end());
437 }
438
439 /// \brief Updates the operand at Idx in instruction Inst with the result of
440 /// instruction Mat. If the instruction is a PHI node then special
441 /// handling for duplicate values form the same incomming basic block is
442 /// required.
443 /// \return The update will always succeed, but the return value indicated if
444 /// Mat was used for the update or not.
updateOperand(Instruction * Inst,unsigned Idx,Instruction * Mat)445 static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) {
446 if (auto PHI = dyn_cast<PHINode>(Inst)) {
447 // Check if any previous operand of the PHI node has the same incoming basic
448 // block. This is a very odd case that happens when the incoming basic block
449 // has a switch statement. In this case use the same value as the previous
450 // operand(s), otherwise we will fail verification due to different values.
451 // The values are actually the same, but the variable names are different
452 // and the verifier doesn't like that.
453 BasicBlock *IncomingBB = PHI->getIncomingBlock(Idx);
454 for (unsigned i = 0; i < Idx; ++i) {
455 if (PHI->getIncomingBlock(i) == IncomingBB) {
456 Value *IncomingVal = PHI->getIncomingValue(i);
457 Inst->setOperand(Idx, IncomingVal);
458 return false;
459 }
460 }
461 }
462
463 Inst->setOperand(Idx, Mat);
464 return true;
465 }
466
467 /// \brief Emit materialization code for all rebased constants and update their
468 /// users.
emitBaseConstants(Instruction * Base,Constant * Offset,const ConstantUser & ConstUser)469 void ConstantHoisting::emitBaseConstants(Instruction *Base, Constant *Offset,
470 const ConstantUser &ConstUser) {
471 Instruction *Mat = Base;
472 if (Offset) {
473 Instruction *InsertionPt = findMatInsertPt(ConstUser.Inst,
474 ConstUser.OpndIdx);
475 Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
476 "const_mat", InsertionPt);
477
478 DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
479 << " + " << *Offset << ") in BB "
480 << Mat->getParent()->getName() << '\n' << *Mat << '\n');
481 Mat->setDebugLoc(ConstUser.Inst->getDebugLoc());
482 }
483 Value *Opnd = ConstUser.Inst->getOperand(ConstUser.OpndIdx);
484
485 // Visit constant integer.
486 if (isa<ConstantInt>(Opnd)) {
487 DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
488 if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat) && Offset)
489 Mat->eraseFromParent();
490 DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
491 return;
492 }
493
494 // Visit cast instruction.
495 if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
496 assert(CastInst->isCast() && "Expected an cast instruction!");
497 // Check if we already have visited this cast instruction before to avoid
498 // unnecessary cloning.
499 Instruction *&ClonedCastInst = ClonedCastMap[CastInst];
500 if (!ClonedCastInst) {
501 ClonedCastInst = CastInst->clone();
502 ClonedCastInst->setOperand(0, Mat);
503 ClonedCastInst->insertAfter(CastInst);
504 // Use the same debug location as the original cast instruction.
505 ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
506 DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
507 << "To : " << *ClonedCastInst << '\n');
508 }
509
510 DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
511 updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst);
512 DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
513 return;
514 }
515
516 // Visit constant expression.
517 if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
518 Instruction *ConstExprInst = ConstExpr->getAsInstruction();
519 ConstExprInst->setOperand(0, Mat);
520 ConstExprInst->insertBefore(findMatInsertPt(ConstUser.Inst,
521 ConstUser.OpndIdx));
522
523 // Use the same debug location as the instruction we are about to update.
524 ConstExprInst->setDebugLoc(ConstUser.Inst->getDebugLoc());
525
526 DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
527 << "From : " << *ConstExpr << '\n');
528 DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
529 if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ConstExprInst)) {
530 ConstExprInst->eraseFromParent();
531 if (Offset)
532 Mat->eraseFromParent();
533 }
534 DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
535 return;
536 }
537 }
538
539 /// \brief Hoist and hide the base constant behind a bitcast and emit
540 /// materialization code for derived constants.
emitBaseConstants()541 bool ConstantHoisting::emitBaseConstants() {
542 bool MadeChange = false;
543 for (auto const &ConstInfo : ConstantVec) {
544 // Hoist and hide the base constant behind a bitcast.
545 Instruction *IP = findConstantInsertionPoint(ConstInfo);
546 IntegerType *Ty = ConstInfo.BaseConstant->getType();
547 Instruction *Base =
548 new BitCastInst(ConstInfo.BaseConstant, Ty, "const", IP);
549 DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseConstant << ") to BB "
550 << IP->getParent()->getName() << '\n' << *Base << '\n');
551 NumConstantsHoisted++;
552
553 // Emit materialization code for all rebased constants.
554 for (auto const &RCI : ConstInfo.RebasedConstants) {
555 NumConstantsRebased++;
556 for (auto const &U : RCI.Uses)
557 emitBaseConstants(Base, RCI.Offset, U);
558 }
559
560 // Use the same debug location as the last user of the constant.
561 assert(!Base->use_empty() && "The use list is empty!?");
562 assert(isa<Instruction>(Base->user_back()) &&
563 "All uses should be instructions.");
564 Base->setDebugLoc(cast<Instruction>(Base->user_back())->getDebugLoc());
565
566 // Correct for base constant, which we counted above too.
567 NumConstantsRebased--;
568 MadeChange = true;
569 }
570 return MadeChange;
571 }
572
573 /// \brief Check all cast instructions we made a copy of and remove them if they
574 /// have no more users.
deleteDeadCastInst() const575 void ConstantHoisting::deleteDeadCastInst() const {
576 for (auto const &I : ClonedCastMap)
577 if (I.first->use_empty())
578 I.first->eraseFromParent();
579 }
580
581 /// \brief Optimize expensive integer constants in the given function.
optimizeConstants(Function & Fn)582 bool ConstantHoisting::optimizeConstants(Function &Fn) {
583 // Collect all constant candidates.
584 collectConstantCandidates(Fn);
585
586 // There are no constant candidates to worry about.
587 if (ConstCandVec.empty())
588 return false;
589
590 // Combine constants that can be easily materialized with an add from a common
591 // base constant.
592 findBaseConstants();
593
594 // There are no constants to emit.
595 if (ConstantVec.empty())
596 return false;
597
598 // Finally hoist the base constant and emit materialization code for dependent
599 // constants.
600 bool MadeChange = emitBaseConstants();
601
602 // Cleanup dead instructions.
603 deleteDeadCastInst();
604
605 return MadeChange;
606 }
607