llvm/lib/Transforms/Scalar/ConstantHoisting.cpp

   1 //===- ConstantHoisting.cpp - Prepare code for expensive constants --------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This pass identifies expensive constants to hoist and coalesces them to
  10 // better prepare it for SelectionDAG-based code generation. This works around
  11 // the limitations of the basic-block-at-a-time approach.
  12 //
  13 // First it scans all instructions for integer constants and calculates its
  14 // cost. If the constant can be folded into the instruction (the cost is
  15 // TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
  16 // consider it expensive and leave it alone. This is the default behavior and
  17 // the default implementation of getIntImmCostInst will always return TCC_Free.
  18 //
  19 // If the cost is more than TCC_BASIC, then the integer constant can't be folded
  20 // into the instruction and it might be beneficial to hoist the constant.
  21 // Similar constants are coalesced to reduce register pressure and
  22 // materialization code.
  23 //
  24 // When a constant is hoisted, it is also hidden behind a bitcast to force it to
  25 // be live-out of the basic block. Otherwise the constant would be just
  26 // duplicated and each basic block would have its own copy in the SelectionDAG.
  27 // The SelectionDAG recognizes such constants as opaque and doesn't perform
  28 // certain transformations on them, which would create a new expensive constant.
  29 //
  30 // This optimization is only applied to integer constants in instructions and
  31 // simple (this means not nested) constant cast expressions. For example:
  32 // %0 = load i64* inttoptr (i64 big_constant to i64*)
  33 //===----------------------------------------------------------------------===//
  34
  35 #include "llvm/Transforms/Scalar/ConstantHoisting.h"
  36 #include "llvm/ADT/APInt.h"
  37 #include "llvm/ADT/DenseMap.h"
  38 #include "llvm/ADT/SmallPtrSet.h"
  39 #include "llvm/ADT/SmallVector.h"
  40 #include "llvm/ADT/Statistic.h"
  41 #include "llvm/Analysis/BlockFrequencyInfo.h"
  42 #include "llvm/Analysis/ProfileSummaryInfo.h"
  43 #include "llvm/Analysis/TargetTransformInfo.h"
  44 #include "llvm/IR/BasicBlock.h"
  45 #include "llvm/IR/Constants.h"
  46 #include "llvm/IR/DataLayout.h"
  47 #include "llvm/IR/DebugInfoMetadata.h"
  48 #include "llvm/IR/Dominators.h"
  49 #include "llvm/IR/Function.h"
  50 #include "llvm/IR/InstrTypes.h"
  51 #include "llvm/IR/Instruction.h"
  52 #include "llvm/IR/Instructions.h"
  53 #include "llvm/IR/IntrinsicInst.h"
  54 #include "llvm/IR/Operator.h"
  55 #include "llvm/IR/Value.h"
  56 #include "llvm/InitializePasses.h"
  57 #include "llvm/Pass.h"
  58 #include "llvm/Support/BlockFrequency.h"
  59 #include "llvm/Support/Casting.h"
  60 #include "llvm/Support/CommandLine.h"
  61 #include "llvm/Support/Debug.h"
  62 #include "llvm/Support/raw_ostream.h"
  63 #include "llvm/Transforms/Scalar.h"
  64 #include "llvm/Transforms/Utils/Local.h"
  65 #include "llvm/Transforms/Utils/SizeOpts.h"
  66 #include <cassert>
  67 #include <iterator>
  68 #include <tuple>
  69 #include <utility>
  70
  71 using namespace llvm;
  72 using namespace consthoist;
  73
  74 #define DEBUG_TYPE "consthoist"
  75
  76 STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
  77 STATISTIC(NumConstantsRebased, "Number of constants rebased");
  78
  79 static cl::opt<bool> ConstHoistWithBlockFrequency(
  80     "consthoist-with-block-frequency", cl::init(true), cl::Hidden,
  81     cl::desc("Enable the use of the block frequency analysis to reduce the "
  82              "chance to execute const materialization more frequently than "
  83              "without hoisting."));
  84
  85 static cl::opt<bool> ConstHoistGEP(
  86     "consthoist-gep", cl::init(false), cl::Hidden,
  87     cl::desc("Try hoisting constant gep expressions"));
  88
  89 static cl::opt<unsigned>
  90 MinNumOfDependentToRebase("consthoist-min-num-to-rebase",
  91     cl::desc("Do not rebase if number of dependent constants of a Base is less "
  92              "than this number."),
  93     cl::init(0), cl::Hidden);
  94
  95 namespace {
  96
  97 /// The constant hoisting pass.
  98 class ConstantHoistingLegacyPass : public FunctionPass {
  99 public:
 100   static char ID; // Pass identification, replacement for typeid
 101
 102   ConstantHoistingLegacyPass() : FunctionPass(ID) {
 103     initializeConstantHoistingLegacyPassPass(*PassRegistry::getPassRegistry());
 104   }
 105
 106   bool runOnFunction(Function &Fn) override;
 107
 108   StringRef getPassName() const override { return "Constant Hoisting"; }
 109
 110   void getAnalysisUsage(AnalysisUsage &AU) const override {
 111     AU.setPreservesCFG();
 112     if (ConstHoistWithBlockFrequency)
 113       AU.addRequired<BlockFrequencyInfoWrapperPass>();
 114     AU.addRequired<DominatorTreeWrapperPass>();
 115     AU.addRequired<ProfileSummaryInfoWrapperPass>();
 116     AU.addRequired<TargetTransformInfoWrapperPass>();
 117   }
 118
 119 private:
 120   ConstantHoistingPass Impl;
 121 };
 122
 123 } // end anonymous namespace
 124
 125 char ConstantHoistingLegacyPass::ID = 0;
 126
 127 INITIALIZE_PASS_BEGIN(ConstantHoistingLegacyPass, "consthoist",
 128                       "Constant Hoisting", false, false)
 129 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 130 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 131 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
 132 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 133 INITIALIZE_PASS_END(ConstantHoistingLegacyPass, "consthoist",
 134                     "Constant Hoisting", false, false)
 135
 136 FunctionPass *llvm::createConstantHoistingPass() {
 137   return new ConstantHoistingLegacyPass();
 138 }
 139
 140 /// Perform the constant hoisting optimization for the given function.
 141 bool ConstantHoistingLegacyPass::runOnFunction(Function &Fn) {
 142   if (skipFunction(Fn))
 143     return false;
 144
 145   LLVM_DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
 146   LLVM_DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');
 147
 148   bool MadeChange =
 149       Impl.runImpl(Fn, getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn),
 150                    getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
 151                    ConstHoistWithBlockFrequency
 152                        ? &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI()
 153                        : nullptr,
 154                    Fn.getEntryBlock(),
 155                    &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
 156
 157   LLVM_DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
 158
 159   return MadeChange;
 160 }
 161
 162 void ConstantHoistingPass::collectMatInsertPts(
 163     const RebasedConstantListType &RebasedConstants,
 164     SmallVectorImpl<BasicBlock::iterator> &MatInsertPts) const {
 165   for (const RebasedConstantInfo &RCI : RebasedConstants)
 166     for (const ConstantUser &U : RCI.Uses)
 167       MatInsertPts.emplace_back(findMatInsertPt(U.Inst, U.OpndIdx));
 168 }
 169
 170 /// Find the constant materialization insertion point.
 171 BasicBlock::iterator ConstantHoistingPass::findMatInsertPt(Instruction *Inst,
 172                                                            unsigned Idx) const {
 173   // If the operand is a cast instruction, then we have to materialize the
 174   // constant before the cast instruction.
 175   if (Idx != ~0U) {
 176     Value *Opnd = Inst->getOperand(Idx);
 177     if (auto CastInst = dyn_cast<Instruction>(Opnd))
 178       if (CastInst->isCast())
 179         return CastInst->getIterator();
 180   }
 181
 182   // The simple and common case. This also includes constant expressions.
 183   if (!isa<PHINode>(Inst) && !Inst->isEHPad())
 184     return Inst->getIterator();
 185
 186   // We can't insert directly before a phi node or an eh pad. Insert before
 187   // the terminator of the incoming or dominating block.
 188   assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!");
 189   BasicBlock *InsertionBlock = nullptr;
 190   if (Idx != ~0U && isa<PHINode>(Inst)) {
 191     InsertionBlock = cast<PHINode>(Inst)->getIncomingBlock(Idx);
 192     if (!InsertionBlock->isEHPad()) {
 193       return InsertionBlock->getTerminator()->getIterator();
 194     }
 195   } else {
 196     InsertionBlock = Inst->getParent();
 197   }
 198
 199   // This must be an EH pad. Iterate over immediate dominators until we find a
 200   // non-EH pad. We need to skip over catchswitch blocks, which are both EH pads
 201   // and terminators.
 202   auto *IDom = DT->getNode(InsertionBlock)->getIDom();
 203   while (IDom->getBlock()->isEHPad()) {
 204     assert(Entry != IDom->getBlock() && "eh pad in entry block");
 205     IDom = IDom->getIDom();
 206   }
 207
 208   return IDom->getBlock()->getTerminator()->getIterator();
 209 }
 210
 211 /// Given \p BBs as input, find another set of BBs which collectively
 212 /// dominates \p BBs and have the minimal sum of frequencies. Return the BB
 213 /// set found in \p BBs.
 214 static void findBestInsertionSet(DominatorTree &DT, BlockFrequencyInfo &BFI,
 215                                  BasicBlock *Entry,
 216                                  SetVector<BasicBlock *> &BBs) {
 217   assert(!BBs.count(Entry) && "Assume Entry is not in BBs");
 218   // Nodes on the current path to the root.
 219   SmallPtrSet<BasicBlock *, 8> Path;
 220   // Candidates includes any block 'BB' in set 'BBs' that is not strictly
 221   // dominated by any other blocks in set 'BBs', and all nodes in the path
 222   // in the dominator tree from Entry to 'BB'.
 223   SmallPtrSet<BasicBlock *, 16> Candidates;
 224   for (auto *BB : BBs) {
 225     // Ignore unreachable basic blocks.
 226     if (!DT.isReachableFromEntry(BB))
 227       continue;
 228     Path.clear();
 229     // Walk up the dominator tree until Entry or another BB in BBs
 230     // is reached. Insert the nodes on the way to the Path.
 231     BasicBlock *Node = BB;
 232     // The "Path" is a candidate path to be added into Candidates set.
 233     bool isCandidate = false;
 234     do {
 235       Path.insert(Node);
 236       if (Node == Entry || Candidates.count(Node)) {
 237         isCandidate = true;
 238         break;
 239       }
 240       assert(DT.getNode(Node)->getIDom() &&
 241              "Entry doens't dominate current Node");
 242       Node = DT.getNode(Node)->getIDom()->getBlock();
 243     } while (!BBs.count(Node));
 244
 245     // If isCandidate is false, Node is another Block in BBs dominating
 246     // current 'BB'. Drop the nodes on the Path.
 247     if (!isCandidate)
 248       continue;
 249
 250     // Add nodes on the Path into Candidates.
 251     Candidates.insert(Path.begin(), Path.end());
 252   }
 253
 254   // Sort the nodes in Candidates in top-down order and save the nodes
 255   // in Orders.
 256   unsigned Idx = 0;
 257   SmallVector<BasicBlock *, 16> Orders;
 258   Orders.push_back(Entry);
 259   while (Idx != Orders.size()) {
 260     BasicBlock *Node = Orders[Idx++];
 261     for (auto *ChildDomNode : DT.getNode(Node)->children()) {
 262       if (Candidates.count(ChildDomNode->getBlock()))
 263         Orders.push_back(ChildDomNode->getBlock());
 264     }
 265   }
 266
 267   // Visit Orders in bottom-up order.
 268   using InsertPtsCostPair =
 269       std::pair<SetVector<BasicBlock *>, BlockFrequency>;
 270
 271   // InsertPtsMap is a map from a BB to the best insertion points for the
 272   // subtree of BB (subtree not including the BB itself).
 273   DenseMap<BasicBlock *, InsertPtsCostPair> InsertPtsMap;
 274   InsertPtsMap.reserve(Orders.size() + 1);
 275   for (BasicBlock *Node : llvm::reverse(Orders)) {
 276     bool NodeInBBs = BBs.count(Node);
 277     auto &InsertPts = InsertPtsMap[Node].first;
 278     BlockFrequency &InsertPtsFreq = InsertPtsMap[Node].second;
 279
 280     // Return the optimal insert points in BBs.
 281     if (Node == Entry) {
 282       BBs.clear();
 283       if (InsertPtsFreq > BFI.getBlockFreq(Node) ||
 284           (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1))
 285         BBs.insert(Entry);
 286       else
 287         BBs.insert(InsertPts.begin(), InsertPts.end());
 288       break;
 289     }
 290
 291     BasicBlock *Parent = DT.getNode(Node)->getIDom()->getBlock();
 292     // Initially, ParentInsertPts is empty and ParentPtsFreq is 0. Every child
 293     // will update its parent's ParentInsertPts and ParentPtsFreq.
 294     auto &ParentInsertPts = InsertPtsMap[Parent].first;
 295     BlockFrequency &ParentPtsFreq = InsertPtsMap[Parent].second;
 296     // Choose to insert in Node or in subtree of Node.
 297     // Don't hoist to EHPad because we may not find a proper place to insert
 298     // in EHPad.
 299     // If the total frequency of InsertPts is the same as the frequency of the
 300     // target Node, and InsertPts contains more than one nodes, choose hoisting
 301     // to reduce code size.
 302     if (NodeInBBs ||
 303         (!Node->isEHPad() &&
 304          (InsertPtsFreq > BFI.getBlockFreq(Node) ||
 305           (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1)))) {
 306       ParentInsertPts.insert(Node);
 307       ParentPtsFreq += BFI.getBlockFreq(Node);
 308     } else {
 309       ParentInsertPts.insert(InsertPts.begin(), InsertPts.end());
 310       ParentPtsFreq += InsertPtsFreq;
 311     }
 312   }
 313 }
 314
 315 /// Find an insertion point that dominates all uses.
 316 SetVector<BasicBlock::iterator>
 317 ConstantHoistingPass::findConstantInsertionPoint(
 318     const ConstantInfo &ConstInfo,
 319     const ArrayRef<BasicBlock::iterator> MatInsertPts) const {
 320   assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
 321   // Collect all basic blocks.
 322   SetVector<BasicBlock *> BBs;
 323   SetVector<BasicBlock::iterator> InsertPts;
 324
 325   for (BasicBlock::iterator MatInsertPt : MatInsertPts)
 326     BBs.insert(MatInsertPt->getParent());
 327
 328   if (BBs.count(Entry)) {
 329     InsertPts.insert(Entry->begin());
 330     return InsertPts;
 331   }
 332
 333   if (BFI) {
 334     findBestInsertionSet(*DT, *BFI, Entry, BBs);
 335     for (BasicBlock *BB : BBs)
 336       InsertPts.insert(BB->getFirstInsertionPt());
 337     return InsertPts;
 338   }
 339
 340   while (BBs.size() >= 2) {
 341     BasicBlock *BB, *BB1, *BB2;
 342     BB1 = BBs.pop_back_val();
 343     BB2 = BBs.pop_back_val();
 344     BB = DT->findNearestCommonDominator(BB1, BB2);
 345     if (BB == Entry) {
 346       InsertPts.insert(Entry->begin());
 347       return InsertPts;
 348     }
 349     BBs.insert(BB);
 350   }
 351   assert((BBs.size() == 1) && "Expected only one element.");
 352   Instruction &FirstInst = (*BBs.begin())->front();
 353   InsertPts.insert(findMatInsertPt(&FirstInst));
 354   return InsertPts;
 355 }
 356
 357 /// Record constant integer ConstInt for instruction Inst at operand
 358 /// index Idx.
 359 ///
 360 /// The operand at index Idx is not necessarily the constant integer itself. It
 361 /// could also be a cast instruction or a constant expression that uses the
 362 /// constant integer.
 363 void ConstantHoistingPass::collectConstantCandidates(
 364     ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
 365     ConstantInt *ConstInt) {
 366   if (ConstInt->getType()->isVectorTy())
 367     return;
 368
 369   InstructionCost Cost;
 370   // Ask the target about the cost of materializing the constant for the given
 371   // instruction and operand index.
 372   if (auto IntrInst = dyn_cast<IntrinsicInst>(Inst))
 373     Cost = TTI->getIntImmCostIntrin(IntrInst->getIntrinsicID(), Idx,
 374                                     ConstInt->getValue(), ConstInt->getType(),
 375                                     TargetTransformInfo::TCK_SizeAndLatency);
 376   else
 377     Cost = TTI->getIntImmCostInst(
 378         Inst->getOpcode(), Idx, ConstInt->getValue(), ConstInt->getType(),
 379         TargetTransformInfo::TCK_SizeAndLatency, Inst);
 380
 381   // Ignore cheap integer constants.
 382   if (Cost > TargetTransformInfo::TCC_Basic) {
 383     ConstCandMapType::iterator Itr;
 384     bool Inserted;
 385     ConstPtrUnionType Cand = ConstInt;
 386     std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
 387     if (Inserted) {
 388       ConstIntCandVec.push_back(ConstantCandidate(ConstInt));
 389       Itr->second = ConstIntCandVec.size() - 1;
 390     }
 391     ConstIntCandVec[Itr->second].addUser(Inst, Idx, *Cost.getValue());
 392     LLVM_DEBUG(if (isa<ConstantInt>(Inst->getOperand(Idx))) dbgs()
 393                    << "Collect constant " << *ConstInt << " from " << *Inst
 394                    << " with cost " << Cost << '\n';
 395                else dbgs() << "Collect constant " << *ConstInt
 396                            << " indirectly from " << *Inst << " via "
 397                            << *Inst->getOperand(Idx) << " with cost " << Cost
 398                            << '\n';);
 399   }
 400 }
 401
 402 /// Record constant GEP expression for instruction Inst at operand index Idx.
 403 void ConstantHoistingPass::collectConstantCandidates(
 404     ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
 405     ConstantExpr *ConstExpr) {
 406   // TODO: Handle vector GEPs
 407   if (ConstExpr->getType()->isVectorTy())
 408     return;
 409
 410   GlobalVariable *BaseGV = dyn_cast<GlobalVariable>(ConstExpr->getOperand(0));
 411   if (!BaseGV)
 412     return;
 413
 414   // Get offset from the base GV.
 415   PointerType *GVPtrTy = cast<PointerType>(BaseGV->getType());
 416   IntegerType *OffsetTy = DL->getIndexType(*Ctx, GVPtrTy->getAddressSpace());
 417   APInt Offset(DL->getTypeSizeInBits(OffsetTy), /*val*/ 0, /*isSigned*/ true);
 418   auto *GEPO = cast<GEPOperator>(ConstExpr);
 419
 420   // TODO: If we have a mix of inbounds and non-inbounds GEPs, then basing a
 421   // non-inbounds GEP on an inbounds GEP is potentially incorrect. Restrict to
 422   // inbounds GEP for now -- alternatively, we could drop inbounds from the
 423   // constant expression,
 424   if (!GEPO->isInBounds())
 425     return;
 426
 427   if (!GEPO->accumulateConstantOffset(*DL, Offset))
 428     return;
 429
 430   if (!Offset.isIntN(32))
 431     return;
 432
 433   // A constant GEP expression that has a GlobalVariable as base pointer is
 434   // usually lowered to a load from constant pool. Such operation is unlikely
 435   // to be cheaper than compute it by <Base + Offset>, which can be lowered to
 436   // an ADD instruction or folded into Load/Store instruction.
 437   InstructionCost Cost =
 438       TTI->getIntImmCostInst(Instruction::Add, 1, Offset, OffsetTy,
 439                              TargetTransformInfo::TCK_SizeAndLatency, Inst);
 440   ConstCandVecType &ExprCandVec = ConstGEPCandMap[BaseGV];
 441   ConstCandMapType::iterator Itr;
 442   bool Inserted;
 443   ConstPtrUnionType Cand = ConstExpr;
 444   std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
 445   if (Inserted) {
 446     ExprCandVec.push_back(ConstantCandidate(
 447         ConstantInt::get(Type::getInt32Ty(*Ctx), Offset.getLimitedValue()),
 448         ConstExpr));
 449     Itr->second = ExprCandVec.size() - 1;
 450   }
 451   ExprCandVec[Itr->second].addUser(Inst, Idx, *Cost.getValue());
 452 }
 453
 454 /// Check the operand for instruction Inst at index Idx.
 455 void ConstantHoistingPass::collectConstantCandidates(
 456     ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx) {
 457   Value *Opnd = Inst->getOperand(Idx);
 458
 459   // Visit constant integers.
 460   if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
 461     collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
 462     return;
 463   }
 464
 465   // Visit cast instructions that have constant integers.
 466   if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
 467     // Only visit cast instructions, which have been skipped. All other
 468     // instructions should have already been visited.
 469     if (!CastInst->isCast())
 470       return;
 471
 472     if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
 473       // Pretend the constant is directly used by the instruction and ignore
 474       // the cast instruction.
 475       collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
 476       return;
 477     }
 478   }
 479
 480   // Visit constant expressions that have constant integers.
 481   if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
 482     // Handle constant gep expressions.
 483     if (ConstHoistGEP && isa<GEPOperator>(ConstExpr))
 484       collectConstantCandidates(ConstCandMap, Inst, Idx, ConstExpr);
 485
 486     // Only visit constant cast expressions.
 487     if (!ConstExpr->isCast())
 488       return;
 489
 490     if (auto ConstInt = dyn_cast<ConstantInt>(ConstExpr->getOperand(0))) {
 491       // Pretend the constant is directly used by the instruction and ignore
 492       // the constant expression.
 493       collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
 494       return;
 495     }
 496   }
 497 }
 498
 499 /// Scan the instruction for expensive integer constants and record them
 500 /// in the constant candidate vector.
 501 void ConstantHoistingPass::collectConstantCandidates(
 502     ConstCandMapType &ConstCandMap, Instruction *Inst) {
 503   // Skip all cast instructions. They are visited indirectly later on.
 504   if (Inst->isCast())
 505     return;
 506
 507   // Scan all operands.
 508   for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
 509     // The cost of materializing the constants (defined in
 510     // `TargetTransformInfo::getIntImmCostInst`) for instructions which only
 511     // take constant variables is lower than `TargetTransformInfo::TCC_Basic`.
 512     // So it's safe for us to collect constant candidates from all
 513     // IntrinsicInsts.
 514     if (canReplaceOperandWithVariable(Inst, Idx)) {
 515       collectConstantCandidates(ConstCandMap, Inst, Idx);
 516     }
 517   } // end of for all operands
 518 }
 519
 520 /// Collect all integer constants in the function that cannot be folded
 521 /// into an instruction itself.
 522 void ConstantHoistingPass::collectConstantCandidates(Function &Fn) {
 523   ConstCandMapType ConstCandMap;
 524   for (BasicBlock &BB : Fn) {
 525     // Ignore unreachable basic blocks.
 526     if (!DT->isReachableFromEntry(&BB))
 527       continue;
 528     for (Instruction &Inst : BB)
 529       if (!TTI->preferToKeepConstantsAttached(Inst, Fn))
 530         collectConstantCandidates(ConstCandMap, &Inst);
 531   }
 532 }
 533
 534 // From a list of constants, one needs to picked as the base and the other
 535 // constants will be transformed into an offset from that base constant. The
 536 // question is which we can pick best? For example, consider these constants
 537 // and their number of uses:
 538 //
 539 //  Constants| 2 | 4 | 12 | 42 |
 540 //  NumUses  | 3 | 2 |  8 |  7 |
 541 //
 542 // Selecting constant 12 because it has the most uses will generate negative
 543 // offsets for constants 2 and 4 (i.e. -10 and -8 respectively). If negative
 544 // offsets lead to less optimal code generation, then there might be better
 545 // solutions. Suppose immediates in the range of 0..35 are most optimally
 546 // supported by the architecture, then selecting constant 2 is most optimal
 547 // because this will generate offsets: 0, 2, 10, 40. Offsets 0, 2 and 10 are in
 548 // range 0..35, and thus 3 + 2 + 8 = 13 uses are in range. Selecting 12 would
 549 // have only 8 uses in range, so choosing 2 as a base is more optimal. Thus, in
 550 // selecting the base constant the range of the offsets is a very important
 551 // factor too that we take into account here. This algorithm calculates a total
 552 // costs for selecting a constant as the base and substract the costs if
 553 // immediates are out of range. It has quadratic complexity, so we call this
 554 // function only when we're optimising for size and there are less than 100
 555 // constants, we fall back to the straightforward algorithm otherwise
 556 // which does not do all the offset calculations.
 557 unsigned
 558 ConstantHoistingPass::maximizeConstantsInRange(ConstCandVecType::iterator S,
 559                                            ConstCandVecType::iterator E,
 560                                            ConstCandVecType::iterator &MaxCostItr) {
 561   unsigned NumUses = 0;
 562
 563   if (!OptForSize || std::distance(S,E) > 100) {
 564     for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
 565       NumUses += ConstCand->Uses.size();
 566       if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
 567         MaxCostItr = ConstCand;
 568     }
 569     return NumUses;
 570   }
 571
 572   LLVM_DEBUG(dbgs() << "== Maximize constants in range ==\n");
 573   InstructionCost MaxCost = -1;
 574   for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
 575     auto Value = ConstCand->ConstInt->getValue();
 576     Type *Ty = ConstCand->ConstInt->getType();
 577     InstructionCost Cost = 0;
 578     NumUses += ConstCand->Uses.size();
 579     LLVM_DEBUG(dbgs() << "= Constant: " << ConstCand->ConstInt->getValue()
 580                       << "\n");
 581
 582     for (auto User : ConstCand->Uses) {
 583       unsigned Opcode = User.Inst->getOpcode();
 584       unsigned OpndIdx = User.OpndIdx;
 585       Cost += TTI->getIntImmCostInst(Opcode, OpndIdx, Value, Ty,
 586                                      TargetTransformInfo::TCK_SizeAndLatency);
 587       LLVM_DEBUG(dbgs() << "Cost: " << Cost << "\n");
 588
 589       for (auto C2 = S; C2 != E; ++C2) {
 590         APInt Diff = C2->ConstInt->getValue() - ConstCand->ConstInt->getValue();
 591         const InstructionCost ImmCosts =
 592             TTI->getIntImmCodeSizeCost(Opcode, OpndIdx, Diff, Ty);
 593         Cost -= ImmCosts;
 594         LLVM_DEBUG(dbgs() << "Offset " << Diff << " "
 595                           << "has penalty: " << ImmCosts << "\n"
 596                           << "Adjusted cost: " << Cost << "\n");
 597       }
 598     }
 599     LLVM_DEBUG(dbgs() << "Cumulative cost: " << Cost << "\n");
 600     if (Cost > MaxCost) {
 601       MaxCost = Cost;
 602       MaxCostItr = ConstCand;
 603       LLVM_DEBUG(dbgs() << "New candidate: " << MaxCostItr->ConstInt->getValue()
 604                         << "\n");
 605     }
 606   }
 607   return NumUses;
 608 }
 609
 610 /// Find the base constant within the given range and rebase all other
 611 /// constants with respect to the base constant.
 612 void ConstantHoistingPass::findAndMakeBaseConstant(
 613     ConstCandVecType::iterator S, ConstCandVecType::iterator E,
 614     SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec) {
 615   auto MaxCostItr = S;
 616   unsigned NumUses = maximizeConstantsInRange(S, E, MaxCostItr);
 617
 618   // Don't hoist constants that have only one use.
 619   if (NumUses <= 1)
 620     return;
 621
 622   ConstantInt *ConstInt = MaxCostItr->ConstInt;
 623   ConstantExpr *ConstExpr = MaxCostItr->ConstExpr;
 624   ConstantInfo ConstInfo;
 625   ConstInfo.BaseInt = ConstInt;
 626   ConstInfo.BaseExpr = ConstExpr;
 627   Type *Ty = ConstInt->getType();
 628
 629   // Rebase the constants with respect to the base constant.
 630   for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
 631     APInt Diff = ConstCand->ConstInt->getValue() - ConstInt->getValue();
 632     Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff);
 633     Type *ConstTy =
 634         ConstCand->ConstExpr ? ConstCand->ConstExpr->getType() : nullptr;
 635     ConstInfo.RebasedConstants.push_back(
 636       RebasedConstantInfo(std::move(ConstCand->Uses), Offset, ConstTy));
 637   }
 638   ConstInfoVec.push_back(std::move(ConstInfo));
 639 }
 640
 641 /// Finds and combines constant candidates that can be easily
 642 /// rematerialized with an add from a common base constant.
 643 void ConstantHoistingPass::findBaseConstants(GlobalVariable *BaseGV) {
 644   // If BaseGV is nullptr, find base among candidate constant integers;
 645   // Otherwise find base among constant GEPs that share the same BaseGV.
 646   ConstCandVecType &ConstCandVec = BaseGV ?
 647       ConstGEPCandMap[BaseGV] : ConstIntCandVec;
 648   ConstInfoVecType &ConstInfoVec = BaseGV ?
 649       ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
 650
 651   // Sort the constants by value and type. This invalidates the mapping!
 652   llvm::stable_sort(ConstCandVec, [](const ConstantCandidate &LHS,
 653                                      const ConstantCandidate &RHS) {
 654     if (LHS.ConstInt->getType() != RHS.ConstInt->getType())
 655       return LHS.ConstInt->getBitWidth() < RHS.ConstInt->getBitWidth();
 656     return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue());
 657   });
 658
 659   // Simple linear scan through the sorted constant candidate vector for viable
 660   // merge candidates.
 661   auto MinValItr = ConstCandVec.begin();
 662   for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end();
 663        CC != E; ++CC) {
 664     if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
 665       Type *MemUseValTy = nullptr;
 666       for (auto &U : CC->Uses) {
 667         auto *UI = U.Inst;
 668         if (LoadInst *LI = dyn_cast<LoadInst>(UI)) {
 669           MemUseValTy = LI->getType();
 670           break;
 671         } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
 672           // Make sure the constant is used as pointer operand of the StoreInst.
 673           if (SI->getPointerOperand() == SI->getOperand(U.OpndIdx)) {
 674             MemUseValTy = SI->getValueOperand()->getType();
 675             break;
 676           }
 677         }
 678       }
 679
 680       // Check if the constant is in range of an add with immediate.
 681       APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue();
 682       if ((Diff.getBitWidth() <= 64) &&
 683           TTI->isLegalAddImmediate(Diff.getSExtValue()) &&
 684           // Check if Diff can be used as offset in addressing mode of the user
 685           // memory instruction.
 686           (!MemUseValTy || TTI->isLegalAddressingMode(MemUseValTy,
 687            /*BaseGV*/nullptr, /*BaseOffset*/Diff.getSExtValue(),
 688            /*HasBaseReg*/true, /*Scale*/0)))
 689         continue;
 690     }
 691     // We either have now a different constant type or the constant is not in
 692     // range of an add with immediate anymore.
 693     findAndMakeBaseConstant(MinValItr, CC, ConstInfoVec);
 694     // Start a new base constant search.
 695     MinValItr = CC;
 696   }
 697   // Finalize the last base constant search.
 698   findAndMakeBaseConstant(MinValItr, ConstCandVec.end(), ConstInfoVec);
 699 }
 700
 701 /// Updates the operand at Idx in instruction Inst with the result of
 702 ///        instruction Mat. If the instruction is a PHI node then special
 703 ///        handling for duplicate values from the same incoming basic block is
 704 ///        required.
 705 /// \return The update will always succeed, but the return value indicated if
 706 ///         Mat was used for the update or not.
 707 static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) {
 708   if (auto PHI = dyn_cast<PHINode>(Inst)) {
 709     // Check if any previous operand of the PHI node has the same incoming basic
 710     // block. This is a very odd case that happens when the incoming basic block
 711     // has a switch statement. In this case use the same value as the previous
 712     // operand(s), otherwise we will fail verification due to different values.
 713     // The values are actually the same, but the variable names are different
 714     // and the verifier doesn't like that.
 715     BasicBlock *IncomingBB = PHI->getIncomingBlock(Idx);
 716     for (unsigned i = 0; i < Idx; ++i) {
 717       if (PHI->getIncomingBlock(i) == IncomingBB) {
 718         Value *IncomingVal = PHI->getIncomingValue(i);
 719         Inst->setOperand(Idx, IncomingVal);
 720         return false;
 721       }
 722     }
 723   }
 724
 725   Inst->setOperand(Idx, Mat);
 726   return true;
 727 }
 728
 729 /// Emit materialization code for all rebased constants and update their
 730 /// users.
 731 void ConstantHoistingPass::emitBaseConstants(Instruction *Base,
 732                                              UserAdjustment *Adj) {
 733   Instruction *Mat = Base;
 734
 735   // The same offset can be dereferenced to different types in nested struct.
 736   if (!Adj->Offset && Adj->Ty && Adj->Ty != Base->getType())
 737     Adj->Offset = ConstantInt::get(Type::getInt32Ty(*Ctx), 0);
 738
 739   if (Adj->Offset) {
 740     if (Adj->Ty) {
 741       // Constant being rebased is a ConstantExpr.
 742       Mat = GetElementPtrInst::Create(Type::getInt8Ty(*Ctx), Base, Adj->Offset,
 743                                       "mat_gep", Adj->MatInsertPt);
 744       // Hide it behind a bitcast.
 745       Mat = new BitCastInst(Mat, Adj->Ty, "mat_bitcast",
 746                             Adj->MatInsertPt->getIterator());
 747     } else
 748       // Constant being rebased is a ConstantInt.
 749       Mat =
 750           BinaryOperator::Create(Instruction::Add, Base, Adj->Offset,
 751                                  "const_mat", Adj->MatInsertPt->getIterator());
 752
 753     LLVM_DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
 754                       << " + " << *Adj->Offset << ") in BB "
 755                       << Mat->getParent()->getName() << '\n'
 756                       << *Mat << '\n');
 757     Mat->setDebugLoc(Adj->User.Inst->getDebugLoc());
 758   }
 759   Value *Opnd = Adj->User.Inst->getOperand(Adj->User.OpndIdx);
 760
 761   // Visit constant integer.
 762   if (isa<ConstantInt>(Opnd)) {
 763     LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
 764     if (!updateOperand(Adj->User.Inst, Adj->User.OpndIdx, Mat) && Adj->Offset)
 765       Mat->eraseFromParent();
 766     LLVM_DEBUG(dbgs() << "To    : " << *Adj->User.Inst << '\n');
 767     return;
 768   }
 769
 770   // Visit cast instruction.
 771   if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
 772     assert(CastInst->isCast() && "Expected an cast instruction!");
 773     // Check if we already have visited this cast instruction before to avoid
 774     // unnecessary cloning.
 775     Instruction *&ClonedCastInst = ClonedCastMap[CastInst];
 776     if (!ClonedCastInst) {
 777       ClonedCastInst = CastInst->clone();
 778       ClonedCastInst->setOperand(0, Mat);
 779       ClonedCastInst->insertAfter(CastInst);
 780       // Use the same debug location as the original cast instruction.
 781       ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
 782       LLVM_DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
 783                         << "To               : " << *ClonedCastInst << '\n');
 784     }
 785
 786     LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
 787     updateOperand(Adj->User.Inst, Adj->User.OpndIdx, ClonedCastInst);
 788     LLVM_DEBUG(dbgs() << "To    : " << *Adj->User.Inst << '\n');
 789     return;
 790   }
 791
 792   // Visit constant expression.
 793   if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
 794     if (isa<GEPOperator>(ConstExpr)) {
 795       // Operand is a ConstantGEP, replace it.
 796       updateOperand(Adj->User.Inst, Adj->User.OpndIdx, Mat);
 797       return;
 798     }
 799
 800     // Aside from constant GEPs, only constant cast expressions are collected.
 801     assert(ConstExpr->isCast() && "ConstExpr should be a cast");
 802     Instruction *ConstExprInst = ConstExpr->getAsInstruction();
 803     ConstExprInst->insertBefore(Adj->MatInsertPt);
 804     ConstExprInst->setOperand(0, Mat);
 805
 806     // Use the same debug location as the instruction we are about to update.
 807     ConstExprInst->setDebugLoc(Adj->User.Inst->getDebugLoc());
 808
 809     LLVM_DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
 810                       << "From              : " << *ConstExpr << '\n');
 811     LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
 812     if (!updateOperand(Adj->User.Inst, Adj->User.OpndIdx, ConstExprInst)) {
 813       ConstExprInst->eraseFromParent();
 814       if (Adj->Offset)
 815         Mat->eraseFromParent();
 816     }
 817     LLVM_DEBUG(dbgs() << "To    : " << *Adj->User.Inst << '\n');
 818     return;
 819   }
 820 }
 821
 822 /// Hoist and hide the base constant behind a bitcast and emit
 823 /// materialization code for derived constants.
 824 bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
 825   bool MadeChange = false;
 826   SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec =
 827       BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
 828   for (const consthoist::ConstantInfo &ConstInfo : ConstInfoVec) {
 829     SmallVector<BasicBlock::iterator, 4> MatInsertPts;
 830     collectMatInsertPts(ConstInfo.RebasedConstants, MatInsertPts);
 831     SetVector<BasicBlock::iterator> IPSet =
 832         findConstantInsertionPoint(ConstInfo, MatInsertPts);
 833     // We can have an empty set if the function contains unreachable blocks.
 834     if (IPSet.empty())
 835       continue;
 836
 837     unsigned UsesNum = 0;
 838     unsigned ReBasesNum = 0;
 839     unsigned NotRebasedNum = 0;
 840     for (const BasicBlock::iterator &IP : IPSet) {
 841       // First, collect constants depending on this IP of the base.
 842       UsesNum = 0;
 843       SmallVector<UserAdjustment, 4> ToBeRebased;
 844       unsigned MatCtr = 0;
 845       for (auto const &RCI : ConstInfo.RebasedConstants) {
 846         UsesNum += RCI.Uses.size();
 847         for (auto const &U : RCI.Uses) {
 848           const BasicBlock::iterator &MatInsertPt = MatInsertPts[MatCtr++];
 849           BasicBlock *OrigMatInsertBB = MatInsertPt->getParent();
 850           // If Base constant is to be inserted in multiple places,
 851           // generate rebase for U using the Base dominating U.
 852           if (IPSet.size() == 1 ||
 853               DT->dominates(IP->getParent(), OrigMatInsertBB))
 854             ToBeRebased.emplace_back(RCI.Offset, RCI.Ty, MatInsertPt, U);
 855         }
 856       }
 857
 858       // If only few constants depend on this IP of base, skip rebasing,
 859       // assuming the base and the rebased have the same materialization cost.
 860       if (ToBeRebased.size() < MinNumOfDependentToRebase) {
 861         NotRebasedNum += ToBeRebased.size();
 862         continue;
 863       }
 864
 865       // Emit an instance of the base at this IP.
 866       Instruction *Base = nullptr;
 867       // Hoist and hide the base constant behind a bitcast.
 868       if (ConstInfo.BaseExpr) {
 869         assert(BaseGV && "A base constant expression must have an base GV");
 870         Type *Ty = ConstInfo.BaseExpr->getType();
 871         Base = new BitCastInst(ConstInfo.BaseExpr, Ty, "const", IP);
 872       } else {
 873         IntegerType *Ty = ConstInfo.BaseInt->getIntegerType();
 874         Base = new BitCastInst(ConstInfo.BaseInt, Ty, "const", IP);
 875       }
 876
 877       Base->setDebugLoc(IP->getDebugLoc());
 878
 879       LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseInt
 880                         << ") to BB " << IP->getParent()->getName() << '\n'
 881                         << *Base << '\n');
 882
 883       // Emit materialization code for rebased constants depending on this IP.
 884       for (UserAdjustment &R : ToBeRebased) {
 885         emitBaseConstants(Base, &R);
 886         ReBasesNum++;
 887         // Use the same debug location as the last user of the constant.
 888         Base->setDebugLoc(DILocation::getMergedLocation(
 889             Base->getDebugLoc(), R.User.Inst->getDebugLoc()));
 890       }
 891       assert(!Base->use_empty() && "The use list is empty!?");
 892       assert(isa<Instruction>(Base->user_back()) &&
 893              "All uses should be instructions.");
 894     }
 895     (void)UsesNum;
 896     (void)ReBasesNum;
 897     (void)NotRebasedNum;
 898     // Expect all uses are rebased after rebase is done.
 899     assert(UsesNum == (ReBasesNum + NotRebasedNum) &&
 900            "Not all uses are rebased");
 901
 902     NumConstantsHoisted++;
 903
 904     // Base constant is also included in ConstInfo.RebasedConstants, so
 905     // deduct 1 from ConstInfo.RebasedConstants.size().
 906     NumConstantsRebased += ConstInfo.RebasedConstants.size() - 1;
 907
 908     MadeChange = true;
 909   }
 910   return MadeChange;
 911 }
 912
 913 /// Check all cast instructions we made a copy of and remove them if they
 914 /// have no more users.
 915 void ConstantHoistingPass::deleteDeadCastInst() const {
 916   for (auto const &I : ClonedCastMap)
 917     if (I.first->use_empty())
 918       I.first->eraseFromParent();
 919 }
 920
 921 /// Optimize expensive integer constants in the given function.
 922 bool ConstantHoistingPass::runImpl(Function &Fn, TargetTransformInfo &TTI,
 923                                    DominatorTree &DT, BlockFrequencyInfo *BFI,
 924                                    BasicBlock &Entry, ProfileSummaryInfo *PSI) {
 925   this->TTI = &TTI;
 926   this->DT = &DT;
 927   this->BFI = BFI;
 928   this->DL = &Fn.getDataLayout();
 929   this->Ctx = &Fn.getContext();
 930   this->Entry = &Entry;
 931   this->PSI = PSI;
 932   this->OptForSize = llvm::shouldOptimizeForSize(Entry.getParent(), PSI, BFI,
 933                                                  PGSOQueryType::IRPass);
 934
 935   // Collect all constant candidates.
 936   collectConstantCandidates(Fn);
 937
 938   // Combine constants that can be easily materialized with an add from a common
 939   // base constant.
 940   if (!ConstIntCandVec.empty())
 941     findBaseConstants(nullptr);
 942   for (const auto &MapEntry : ConstGEPCandMap)
 943     if (!MapEntry.second.empty())
 944       findBaseConstants(MapEntry.first);
 945
 946   // Finally hoist the base constant and emit materialization code for dependent
 947   // constants.
 948   bool MadeChange = false;
 949   if (!ConstIntInfoVec.empty())
 950     MadeChange = emitBaseConstants(nullptr);
 951   for (const auto &MapEntry : ConstGEPInfoMap)
 952     if (!MapEntry.second.empty())
 953       MadeChange |= emitBaseConstants(MapEntry.first);
 954
 955
 956   // Cleanup dead instructions.
 957   deleteDeadCastInst();
 958
 959   cleanup();
 960
 961   return MadeChange;
 962 }
 963
 964 PreservedAnalyses ConstantHoistingPass::run(Function &F,
 965                                             FunctionAnalysisManager &AM) {
 966   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 967   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
 968   auto BFI = ConstHoistWithBlockFrequency
 969                  ? &AM.getResult<BlockFrequencyAnalysis>(F)
 970                  : nullptr;
 971   auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
 972   auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
 973   if (!runImpl(F, TTI, DT, BFI, F.getEntryBlock(), PSI))
 974     return PreservedAnalyses::all();
 975
 976   PreservedAnalyses PA;
 977   PA.preserveSet<CFGAnalyses>();
 978   return PA;
 979 }