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