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