LLVM API Documentation

ConstantHoisting.cpp
Go to the documentation of this file.
00001 //===- ConstantHoisting.cpp - Prepare code for expensive constants --------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass identifies expensive constants to hoist and coalesces them to
00011 // better prepare it for SelectionDAG-based code generation. This works around
00012 // the limitations of the basic-block-at-a-time approach.
00013 //
00014 // First it scans all instructions for integer constants and calculates its
00015 // cost. If the constant can be folded into the instruction (the cost is
00016 // TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
00017 // consider it expensive and leave it alone. This is the default behavior and
00018 // the default implementation of getIntImmCost will always return TCC_Free.
00019 //
00020 // If the cost is more than TCC_BASIC, then the integer constant can't be folded
00021 // into the instruction and it might be beneficial to hoist the constant.
00022 // Similar constants are coalesced to reduce register pressure and
00023 // materialization code.
00024 //
00025 // When a constant is hoisted, it is also hidden behind a bitcast to force it to
00026 // be live-out of the basic block. Otherwise the constant would be just
00027 // duplicated and each basic block would have its own copy in the SelectionDAG.
00028 // The SelectionDAG recognizes such constants as opaque and doesn't perform
00029 // certain transformations on them, which would create a new expensive constant.
00030 //
00031 // This optimization is only applied to integer constants in instructions and
00032 // simple (this means not nested) constant cast expressions. For example:
00033 // %0 = load i64* inttoptr (i64 big_constant to i64*)
00034 //===----------------------------------------------------------------------===//
00035 
00036 #include "llvm/Transforms/Scalar.h"
00037 #include "llvm/ADT/SmallSet.h"
00038 #include "llvm/ADT/SmallVector.h"
00039 #include "llvm/ADT/Statistic.h"
00040 #include "llvm/Analysis/TargetTransformInfo.h"
00041 #include "llvm/IR/Constants.h"
00042 #include "llvm/IR/Dominators.h"
00043 #include "llvm/IR/IntrinsicInst.h"
00044 #include "llvm/Pass.h"
00045 #include "llvm/Support/Debug.h"
00046 #include <tuple>
00047 
00048 using namespace llvm;
00049 
00050 #define DEBUG_TYPE "consthoist"
00051 
00052 STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
00053 STATISTIC(NumConstantsRebased, "Number of constants rebased");
00054 
00055 namespace {
00056 struct ConstantUser;
00057 struct RebasedConstantInfo;
00058 
00059 typedef SmallVector<ConstantUser, 8> ConstantUseListType;
00060 typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType;
00061 
00062 /// \brief Keeps track of the user of a constant and the operand index where the
00063 /// constant is used.
00064 struct ConstantUser {
00065   Instruction *Inst;
00066   unsigned OpndIdx;
00067 
00068   ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) { }
00069 };
00070 
00071 /// \brief Keeps track of a constant candidate and its uses.
00072 struct ConstantCandidate {
00073   ConstantUseListType Uses;
00074   ConstantInt *ConstInt;
00075   unsigned CumulativeCost;
00076 
00077   ConstantCandidate(ConstantInt *ConstInt)
00078     : ConstInt(ConstInt), CumulativeCost(0) { }
00079 
00080   /// \brief Add the user to the use list and update the cost.
00081   void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
00082     CumulativeCost += Cost;
00083     Uses.push_back(ConstantUser(Inst, Idx));
00084   }
00085 };
00086 
00087 /// \brief This represents a constant that has been rebased with respect to a
00088 /// base constant. The difference to the base constant is recorded in Offset.
00089 struct RebasedConstantInfo {
00090   ConstantUseListType Uses;
00091   Constant *Offset;
00092 
00093   RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
00094     : Uses(Uses), Offset(Offset) { }
00095 };
00096 
00097 /// \brief A base constant and all its rebased constants.
00098 struct ConstantInfo {
00099   ConstantInt *BaseConstant;
00100   RebasedConstantListType RebasedConstants;
00101 };
00102 
00103 /// \brief The constant hoisting pass.
00104 class ConstantHoisting : public FunctionPass {
00105   typedef DenseMap<ConstantInt *, unsigned> ConstCandMapType;
00106   typedef std::vector<ConstantCandidate> ConstCandVecType;
00107 
00108   const TargetTransformInfo *TTI;
00109   DominatorTree *DT;
00110   BasicBlock *Entry;
00111 
00112   /// Keeps track of constant candidates found in the function.
00113   ConstCandVecType ConstCandVec;
00114 
00115   /// Keep track of cast instructions we already cloned.
00116   SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
00117 
00118   /// These are the final constants we decided to hoist.
00119   SmallVector<ConstantInfo, 8> ConstantVec;
00120 public:
00121   static char ID; // Pass identification, replacement for typeid
00122   ConstantHoisting() : FunctionPass(ID), TTI(nullptr), DT(nullptr),
00123                        Entry(nullptr) {
00124     initializeConstantHoistingPass(*PassRegistry::getPassRegistry());
00125   }
00126 
00127   bool runOnFunction(Function &Fn) override;
00128 
00129   const char *getPassName() const override { return "Constant Hoisting"; }
00130 
00131   void getAnalysisUsage(AnalysisUsage &AU) const override {
00132     AU.setPreservesCFG();
00133     AU.addRequired<DominatorTreeWrapperPass>();
00134     AU.addRequired<TargetTransformInfo>();
00135   }
00136 
00137 private:
00138   /// \brief Initialize the pass.
00139   void setup(Function &Fn) {
00140     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
00141     TTI = &getAnalysis<TargetTransformInfo>();
00142     Entry = &Fn.getEntryBlock();
00143   }
00144 
00145   /// \brief Cleanup.
00146   void cleanup() {
00147     ConstantVec.clear();
00148     ClonedCastMap.clear();
00149     ConstCandVec.clear();
00150 
00151     TTI = nullptr;
00152     DT = nullptr;
00153     Entry = nullptr;
00154   }
00155 
00156   Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
00157   Instruction *findConstantInsertionPoint(const ConstantInfo &ConstInfo) const;
00158   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
00159                                  Instruction *Inst, unsigned Idx,
00160                                  ConstantInt *ConstInt);
00161   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
00162                                  Instruction *Inst);
00163   void collectConstantCandidates(Function &Fn);
00164   void findAndMakeBaseConstant(ConstCandVecType::iterator S,
00165                                ConstCandVecType::iterator E);
00166   void findBaseConstants();
00167   void emitBaseConstants(Instruction *Base, Constant *Offset,
00168                          const ConstantUser &ConstUser);
00169   bool emitBaseConstants();
00170   void deleteDeadCastInst() const;
00171   bool optimizeConstants(Function &Fn);
00172 };
00173 }
00174 
00175 char ConstantHoisting::ID = 0;
00176 INITIALIZE_PASS_BEGIN(ConstantHoisting, "consthoist", "Constant Hoisting",
00177                       false, false)
00178 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
00179 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
00180 INITIALIZE_PASS_END(ConstantHoisting, "consthoist", "Constant Hoisting",
00181                     false, false)
00182 
00183 FunctionPass *llvm::createConstantHoistingPass() {
00184   return new ConstantHoisting();
00185 }
00186 
00187 /// \brief Perform the constant hoisting optimization for the given function.
00188 bool ConstantHoisting::runOnFunction(Function &Fn) {
00189   DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
00190   DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');
00191 
00192   setup(Fn);
00193 
00194   bool MadeChange = optimizeConstants(Fn);
00195 
00196   if (MadeChange) {
00197     DEBUG(dbgs() << "********** Function after Constant Hoisting: "
00198                  << Fn.getName() << '\n');
00199     DEBUG(dbgs() << Fn);
00200   }
00201   DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
00202 
00203   cleanup();
00204 
00205   return MadeChange;
00206 }
00207 
00208 
00209 /// \brief Find the constant materialization insertion point.
00210 Instruction *ConstantHoisting::findMatInsertPt(Instruction *Inst,
00211                                                unsigned Idx) const {
00212   // If the operand is a cast instruction, then we have to materialize the
00213   // constant before the cast instruction.
00214   if (Idx != ~0U) {
00215     Value *Opnd = Inst->getOperand(Idx);
00216     if (auto CastInst = dyn_cast<Instruction>(Opnd))
00217       if (CastInst->isCast())
00218         return CastInst;
00219   }
00220 
00221   // The simple and common case. This also includes constant expressions.
00222   if (!isa<PHINode>(Inst) && !isa<LandingPadInst>(Inst))
00223     return Inst;
00224 
00225   // We can't insert directly before a phi node or landing pad. Insert before
00226   // the terminator of the incoming or dominating block.
00227   assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!");
00228   if (Idx != ~0U && isa<PHINode>(Inst))
00229     return cast<PHINode>(Inst)->getIncomingBlock(Idx)->getTerminator();
00230 
00231   BasicBlock *IDom = DT->getNode(Inst->getParent())->getIDom()->getBlock();
00232   return IDom->getTerminator();
00233 }
00234 
00235 /// \brief Find an insertion point that dominates all uses.
00236 Instruction *ConstantHoisting::
00237 findConstantInsertionPoint(const ConstantInfo &ConstInfo) const {
00238   assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
00239   // Collect all basic blocks.
00240   SmallPtrSet<BasicBlock *, 8> BBs;
00241   for (auto const &RCI : ConstInfo.RebasedConstants)
00242     for (auto const &U : RCI.Uses)
00243       BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent());
00244 
00245   if (BBs.count(Entry))
00246     return &Entry->front();
00247 
00248   while (BBs.size() >= 2) {
00249     BasicBlock *BB, *BB1, *BB2;
00250     BB1 = *BBs.begin();
00251     BB2 = *std::next(BBs.begin());
00252     BB = DT->findNearestCommonDominator(BB1, BB2);
00253     if (BB == Entry)
00254       return &Entry->front();
00255     BBs.erase(BB1);
00256     BBs.erase(BB2);
00257     BBs.insert(BB);
00258   }
00259   assert((BBs.size() == 1) && "Expected only one element.");
00260   Instruction &FirstInst = (*BBs.begin())->front();
00261   return findMatInsertPt(&FirstInst);
00262 }
00263 
00264 
00265 /// \brief Record constant integer ConstInt for instruction Inst at operand
00266 /// index Idx.
00267 ///
00268 /// The operand at index Idx is not necessarily the constant integer itself. It
00269 /// could also be a cast instruction or a constant expression that uses the
00270 // constant integer.
00271 void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
00272                                                  Instruction *Inst,
00273                                                  unsigned Idx,
00274                                                  ConstantInt *ConstInt) {
00275   unsigned Cost;
00276   // Ask the target about the cost of materializing the constant for the given
00277   // instruction and operand index.
00278   if (auto IntrInst = dyn_cast<IntrinsicInst>(Inst))
00279     Cost = TTI->getIntImmCost(IntrInst->getIntrinsicID(), Idx,
00280                               ConstInt->getValue(), ConstInt->getType());
00281   else
00282     Cost = TTI->getIntImmCost(Inst->getOpcode(), Idx, ConstInt->getValue(),
00283                               ConstInt->getType());
00284 
00285   // Ignore cheap integer constants.
00286   if (Cost > TargetTransformInfo::TCC_Basic) {
00287     ConstCandMapType::iterator Itr;
00288     bool Inserted;
00289     std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(ConstInt, 0));
00290     if (Inserted) {
00291       ConstCandVec.push_back(ConstantCandidate(ConstInt));
00292       Itr->second = ConstCandVec.size() - 1;
00293     }
00294     ConstCandVec[Itr->second].addUser(Inst, Idx, Cost);
00295     DEBUG(if (isa<ConstantInt>(Inst->getOperand(Idx)))
00296             dbgs() << "Collect constant " << *ConstInt << " from " << *Inst
00297                    << " with cost " << Cost << '\n';
00298           else
00299           dbgs() << "Collect constant " << *ConstInt << " indirectly from "
00300                  << *Inst << " via " << *Inst->getOperand(Idx) << " with cost "
00301                  << Cost << '\n';
00302     );
00303   }
00304 }
00305 
00306 /// \brief Scan the instruction for expensive integer constants and record them
00307 /// in the constant candidate vector.
00308 void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
00309                                                  Instruction *Inst) {
00310   // Skip all cast instructions. They are visited indirectly later on.
00311   if (Inst->isCast())
00312     return;
00313 
00314   // Can't handle inline asm. Skip it.
00315   if (auto Call = dyn_cast<CallInst>(Inst))
00316     if (isa<InlineAsm>(Call->getCalledValue()))
00317       return;
00318 
00319   // Scan all operands.
00320   for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
00321     Value *Opnd = Inst->getOperand(Idx);
00322 
00323     // Visit constant integers.
00324     if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
00325       collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
00326       continue;
00327     }
00328 
00329     // Visit cast instructions that have constant integers.
00330     if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
00331       // Only visit cast instructions, which have been skipped. All other
00332       // instructions should have already been visited.
00333       if (!CastInst->isCast())
00334         continue;
00335 
00336       if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
00337         // Pretend the constant is directly used by the instruction and ignore
00338         // the cast instruction.
00339         collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
00340         continue;
00341       }
00342     }
00343 
00344     // Visit constant expressions that have constant integers.
00345     if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
00346       // Only visit constant cast expressions.
00347       if (!ConstExpr->isCast())
00348         continue;
00349 
00350       if (auto ConstInt = dyn_cast<ConstantInt>(ConstExpr->getOperand(0))) {
00351         // Pretend the constant is directly used by the instruction and ignore
00352         // the constant expression.
00353         collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
00354         continue;
00355       }
00356     }
00357   } // end of for all operands
00358 }
00359 
00360 /// \brief Collect all integer constants in the function that cannot be folded
00361 /// into an instruction itself.
00362 void ConstantHoisting::collectConstantCandidates(Function &Fn) {
00363   ConstCandMapType ConstCandMap;
00364   for (Function::iterator BB : Fn)
00365     for (BasicBlock::iterator Inst : *BB)
00366       collectConstantCandidates(ConstCandMap, Inst);
00367 }
00368 
00369 /// \brief Find the base constant within the given range and rebase all other
00370 /// constants with respect to the base constant.
00371 void ConstantHoisting::findAndMakeBaseConstant(ConstCandVecType::iterator S,
00372                                                ConstCandVecType::iterator E) {
00373   auto MaxCostItr = S;
00374   unsigned NumUses = 0;
00375   // Use the constant that has the maximum cost as base constant.
00376   for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
00377     NumUses += ConstCand->Uses.size();
00378     if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
00379       MaxCostItr = ConstCand;
00380   }
00381 
00382   // Don't hoist constants that have only one use.
00383   if (NumUses <= 1)
00384     return;
00385 
00386   ConstantInfo ConstInfo;
00387   ConstInfo.BaseConstant = MaxCostItr->ConstInt;
00388   Type *Ty = ConstInfo.BaseConstant->getType();
00389 
00390   // Rebase the constants with respect to the base constant.
00391   for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
00392     APInt Diff = ConstCand->ConstInt->getValue() -
00393                  ConstInfo.BaseConstant->getValue();
00394     Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff);
00395     ConstInfo.RebasedConstants.push_back(
00396       RebasedConstantInfo(std::move(ConstCand->Uses), Offset));
00397   }
00398   ConstantVec.push_back(ConstInfo);
00399 }
00400 
00401 /// \brief Finds and combines constant candidates that can be easily
00402 /// rematerialized with an add from a common base constant.
00403 void ConstantHoisting::findBaseConstants() {
00404   // Sort the constants by value and type. This invalidates the mapping!
00405   std::sort(ConstCandVec.begin(), ConstCandVec.end(),
00406             [](const ConstantCandidate &LHS, const ConstantCandidate &RHS) {
00407     if (LHS.ConstInt->getType() != RHS.ConstInt->getType())
00408       return LHS.ConstInt->getType()->getBitWidth() <
00409              RHS.ConstInt->getType()->getBitWidth();
00410     return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue());
00411   });
00412 
00413   // Simple linear scan through the sorted constant candidate vector for viable
00414   // merge candidates.
00415   auto MinValItr = ConstCandVec.begin();
00416   for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end();
00417        CC != E; ++CC) {
00418     if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
00419       // Check if the constant is in range of an add with immediate.
00420       APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue();
00421       if ((Diff.getBitWidth() <= 64) &&
00422           TTI->isLegalAddImmediate(Diff.getSExtValue()))
00423         continue;
00424     }
00425     // We either have now a different constant type or the constant is not in
00426     // range of an add with immediate anymore.
00427     findAndMakeBaseConstant(MinValItr, CC);
00428     // Start a new base constant search.
00429     MinValItr = CC;
00430   }
00431   // Finalize the last base constant search.
00432   findAndMakeBaseConstant(MinValItr, ConstCandVec.end());
00433 }
00434 
00435 /// \brief Updates the operand at Idx in instruction Inst with the result of
00436 ///        instruction Mat. If the instruction is a PHI node then special
00437 ///        handling for duplicate values form the same incomming basic block is
00438 ///        required.
00439 /// \return The update will always succeed, but the return value indicated if
00440 ///         Mat was used for the update or not.
00441 static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) {
00442   if (auto PHI = dyn_cast<PHINode>(Inst)) {
00443     // Check if any previous operand of the PHI node has the same incoming basic
00444     // block. This is a very odd case that happens when the incoming basic block
00445     // has a switch statement. In this case use the same value as the previous
00446     // operand(s), otherwise we will fail verification due to different values.
00447     // The values are actually the same, but the variable names are different
00448     // and the verifier doesn't like that.
00449     BasicBlock *IncomingBB = PHI->getIncomingBlock(Idx);
00450     for (unsigned i = 0; i < Idx; ++i) {
00451       if (PHI->getIncomingBlock(i) == IncomingBB) {
00452         Value *IncomingVal = PHI->getIncomingValue(i);
00453         Inst->setOperand(Idx, IncomingVal);
00454         return false;
00455       }
00456     }
00457   }
00458 
00459   Inst->setOperand(Idx, Mat);
00460   return true;
00461 }
00462 
00463 /// \brief Emit materialization code for all rebased constants and update their
00464 /// users.
00465 void ConstantHoisting::emitBaseConstants(Instruction *Base, Constant *Offset,
00466                                          const ConstantUser &ConstUser) {
00467   Instruction *Mat = Base;
00468   if (Offset) {
00469     Instruction *InsertionPt = findMatInsertPt(ConstUser.Inst,
00470                                                ConstUser.OpndIdx);
00471     Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
00472                                  "const_mat", InsertionPt);
00473 
00474     DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
00475                  << " + " << *Offset << ") in BB "
00476                  << Mat->getParent()->getName() << '\n' << *Mat << '\n');
00477     Mat->setDebugLoc(ConstUser.Inst->getDebugLoc());
00478   }
00479   Value *Opnd = ConstUser.Inst->getOperand(ConstUser.OpndIdx);
00480 
00481   // Visit constant integer.
00482   if (isa<ConstantInt>(Opnd)) {
00483     DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
00484     if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat) && Offset)
00485       Mat->eraseFromParent();
00486     DEBUG(dbgs() << "To    : " << *ConstUser.Inst << '\n');
00487     return;
00488   }
00489 
00490   // Visit cast instruction.
00491   if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
00492     assert(CastInst->isCast() && "Expected an cast instruction!");
00493     // Check if we already have visited this cast instruction before to avoid
00494     // unnecessary cloning.
00495     Instruction *&ClonedCastInst = ClonedCastMap[CastInst];
00496     if (!ClonedCastInst) {
00497       ClonedCastInst = CastInst->clone();
00498       ClonedCastInst->setOperand(0, Mat);
00499       ClonedCastInst->insertAfter(CastInst);
00500       // Use the same debug location as the original cast instruction.
00501       ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
00502       DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
00503                    << "To               : " << *ClonedCastInst << '\n');
00504     }
00505 
00506     DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
00507     updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst);
00508     DEBUG(dbgs() << "To    : " << *ConstUser.Inst << '\n');
00509     return;
00510   }
00511 
00512   // Visit constant expression.
00513   if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
00514     Instruction *ConstExprInst = ConstExpr->getAsInstruction();
00515     ConstExprInst->setOperand(0, Mat);
00516     ConstExprInst->insertBefore(findMatInsertPt(ConstUser.Inst,
00517                                                 ConstUser.OpndIdx));
00518 
00519     // Use the same debug location as the instruction we are about to update.
00520     ConstExprInst->setDebugLoc(ConstUser.Inst->getDebugLoc());
00521 
00522     DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
00523                  << "From              : " << *ConstExpr << '\n');
00524     DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
00525     if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ConstExprInst)) {
00526       ConstExprInst->eraseFromParent();
00527       if (Offset)
00528         Mat->eraseFromParent();
00529     }
00530     DEBUG(dbgs() << "To    : " << *ConstUser.Inst << '\n');
00531     return;
00532   }
00533 }
00534 
00535 /// \brief Hoist and hide the base constant behind a bitcast and emit
00536 /// materialization code for derived constants.
00537 bool ConstantHoisting::emitBaseConstants() {
00538   bool MadeChange = false;
00539   for (auto const &ConstInfo : ConstantVec) {
00540     // Hoist and hide the base constant behind a bitcast.
00541     Instruction *IP = findConstantInsertionPoint(ConstInfo);
00542     IntegerType *Ty = ConstInfo.BaseConstant->getType();
00543     Instruction *Base =
00544       new BitCastInst(ConstInfo.BaseConstant, Ty, "const", IP);
00545     DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseConstant << ") to BB "
00546                  << IP->getParent()->getName() << '\n' << *Base << '\n');
00547     NumConstantsHoisted++;
00548 
00549     // Emit materialization code for all rebased constants.
00550     for (auto const &RCI : ConstInfo.RebasedConstants) {
00551       NumConstantsRebased++;
00552       for (auto const &U : RCI.Uses)
00553         emitBaseConstants(Base, RCI.Offset, U);
00554     }
00555 
00556     // Use the same debug location as the last user of the constant.
00557     assert(!Base->use_empty() && "The use list is empty!?");
00558     assert(isa<Instruction>(Base->user_back()) &&
00559            "All uses should be instructions.");
00560     Base->setDebugLoc(cast<Instruction>(Base->user_back())->getDebugLoc());
00561 
00562     // Correct for base constant, which we counted above too.
00563     NumConstantsRebased--;
00564     MadeChange = true;
00565   }
00566   return MadeChange;
00567 }
00568 
00569 /// \brief Check all cast instructions we made a copy of and remove them if they
00570 /// have no more users.
00571 void ConstantHoisting::deleteDeadCastInst() const {
00572   for (auto const &I : ClonedCastMap)
00573     if (I.first->use_empty())
00574       I.first->eraseFromParent();
00575 }
00576 
00577 /// \brief Optimize expensive integer constants in the given function.
00578 bool ConstantHoisting::optimizeConstants(Function &Fn) {
00579   // Collect all constant candidates.
00580   collectConstantCandidates(Fn);
00581 
00582   // There are no constant candidates to worry about.
00583   if (ConstCandVec.empty())
00584     return false;
00585 
00586   // Combine constants that can be easily materialized with an add from a common
00587   // base constant.
00588   findBaseConstants();
00589 
00590   // There are no constants to emit.
00591   if (ConstantVec.empty())
00592     return false;
00593 
00594   // Finally hoist the base constant and emit materialization code for dependent
00595   // constants.
00596   bool MadeChange = emitBaseConstants();
00597 
00598   // Cleanup dead instructions.
00599   deleteDeadCastInst();
00600 
00601   return MadeChange;
00602 }