contrib/llvm/lib/Transforms/Scalar/ConstantHoisting.cpp

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