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
49using namespace llvm;
50
51#define DEBUG_TYPE "consthoist"
52
53STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
54STATISTIC(NumConstantsRebased, "Number of constants rebased");
55
56namespace {
57struct ConstantUser;
58struct RebasedConstantInfo;
59
60typedef SmallVector<ConstantUser, 8> ConstantUseListType;
61typedef 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.
65struct ConstantUser {
66  Instruction *Inst;
67  unsigned OpndIdx;
68
69  ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) { }
70};
71
72/// \brief Keeps track of a constant candidate and its uses.
73struct ConstantCandidate {
74  ConstantUseListType Uses;
75  ConstantInt *ConstInt;
76  unsigned CumulativeCost;
77
78  ConstantCandidate(ConstantInt *ConstInt)
79    : ConstInt(ConstInt), CumulativeCost(0) { }
80
81  /// \brief Add the user to the use list and update the cost.
82  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.
90struct RebasedConstantInfo {
91  ConstantUseListType Uses;
92  Constant *Offset;
93
94  RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
95    : Uses(std::move(Uses)), Offset(Offset) { }
96};
97
98/// \brief A base constant and all its rebased constants.
99struct ConstantInfo {
100  ConstantInt *BaseConstant;
101  RebasedConstantListType RebasedConstants;
102};
103
104/// \brief The constant hoisting pass.
105class 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;
121public:
122  static char ID; // Pass identification, replacement for typeid
123  ConstantHoisting() : FunctionPass(ID), TTI(nullptr), DT(nullptr),
124                       Entry(nullptr) {
125    initializeConstantHoistingPass(*PassRegistry::getPassRegistry());
126  }
127
128  bool runOnFunction(Function &Fn) override;
129
130  const char *getPassName() const override { return "Constant Hoisting"; }
131
132  void getAnalysisUsage(AnalysisUsage &AU) const override {
133    AU.setPreservesCFG();
134    AU.addRequired<DominatorTreeWrapperPass>();
135    AU.addRequired<TargetTransformInfoWrapperPass>();
136  }
137
138private:
139  /// \brief Initialize the pass.
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.
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
176char ConstantHoisting::ID = 0;
177INITIALIZE_PASS_BEGIN(ConstantHoisting, "consthoist", "Constant Hoisting",
178                      false, false)
179INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
180INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
181INITIALIZE_PASS_END(ConstantHoisting, "consthoist", "Constant Hoisting",
182                    false, false)
183
184FunctionPass *llvm::createConstantHoistingPass() {
185  return new ConstantHoisting();
186}
187
188/// \brief Perform the constant hoisting optimization for the given function.
189bool 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.
214Instruction *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.
240Instruction *ConstantHoisting::
241findConstantInsertionPoint(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.
275void 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.
312void 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.
366void 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.
375void 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.
407void 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.
445static 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.
469void 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.
541bool 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.
575void 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.
582bool 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