LLVM API Documentation
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 }