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 experessions. For example:
  33 // %0 = load i64* inttoptr (i64 big_constant to i64*)
  34 //===----------------------------------------------------------------------===//
  35
  36 #define DEBUG_TYPE "consthoist"
  37 #include "llvm/Transforms/Scalar.h"
  38 #include "llvm/ADT/MapVector.h"
  39 #include "llvm/ADT/SmallSet.h"
  40 #include "llvm/ADT/Statistic.h"
  41 #include "llvm/Analysis/TargetTransformInfo.h"
  42 #include "llvm/IR/Constants.h"
  43 #include "llvm/IR/Dominators.h"
  44 #include "llvm/IR/IntrinsicInst.h"
  45 #include "llvm/Pass.h"
  46 #include "llvm/Support/CommandLine.h"
  47 #include "llvm/Support/Debug.h"
  48
  49 using namespace llvm;
  50
  51 STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
  52 STATISTIC(NumConstantsRebased, "Number of constants rebased");
  53
  54
  55 namespace {
  56 typedef SmallVector<User *, 4> ConstantUseListType;
  57 struct ConstantCandidate {
  58   unsigned CumulativeCost;
  59   ConstantUseListType Uses;
  60 };
  61
  62 struct ConstantInfo {
  63   ConstantInt *BaseConstant;
  64   struct RebasedConstantInfo {
  65     ConstantInt *OriginalConstant;
  66     Constant *Offset;
  67     ConstantUseListType Uses;
  68   };
  69   typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType;
  70   RebasedConstantListType RebasedConstants;
  71 };
  72
  73 class ConstantHoisting : public FunctionPass {
  74   const TargetTransformInfo *TTI;
  75   DominatorTree *DT;
  76
  77   /// Keeps track of expensive constants found in the function.
  78   typedef MapVector<ConstantInt *, ConstantCandidate> ConstantMapType;
  79   ConstantMapType ConstantMap;
  80
  81   /// These are the final constants we decided to hoist.
  82   SmallVector<ConstantInfo, 4> Constants;
  83 public:
  84   static char ID; // Pass identification, replacement for typeid
  85   ConstantHoisting() : FunctionPass(ID), TTI(0) {
  86     initializeConstantHoistingPass(*PassRegistry::getPassRegistry());
  87   }
  88
  89   bool runOnFunction(Function &F) override;
  90
  91   const char *getPassName() const override { return "Constant Hoisting"; }
  92
  93   void getAnalysisUsage(AnalysisUsage &AU) const override {
  94     AU.setPreservesCFG();
  95     AU.addRequired<DominatorTreeWrapperPass>();
  96     AU.addRequired<TargetTransformInfo>();
  97   }
  98
  99 private:
 100   void CollectConstant(User *U, unsigned Opcode, Intrinsic::ID IID,
 101                         ConstantInt *C);
 102   void CollectConstants(Instruction *I);
 103   void CollectConstants(Function &F);
 104   void FindAndMakeBaseConstant(ConstantMapType::iterator S,
 105                                ConstantMapType::iterator E);
 106   void FindBaseConstants();
 107   Instruction *FindConstantInsertionPoint(Function &F,
 108                                           const ConstantInfo &CI) const;
 109   void EmitBaseConstants(Function &F, User *U, Instruction *Base,
 110                          Constant *Offset, ConstantInt *OriginalConstant);
 111   bool EmitBaseConstants(Function &F);
 112   bool OptimizeConstants(Function &F);
 113 };
 114 }
 115
 116 char ConstantHoisting::ID = 0;
 117 INITIALIZE_PASS_BEGIN(ConstantHoisting, "consthoist", "Constant Hoisting",
 118                       false, false)
 119 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 120 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
 121 INITIALIZE_PASS_END(ConstantHoisting, "consthoist", "Constant Hoisting",
 122                     false, false)
 123
 124 FunctionPass *llvm::createConstantHoistingPass() {
 125   return new ConstantHoisting();
 126 }
 127
 128 /// \brief Perform the constant hoisting optimization for the given function.
 129 bool ConstantHoisting::runOnFunction(Function &F) {
 130   DEBUG(dbgs() << "********** Constant Hoisting **********\n");
 131   DEBUG(dbgs() << "********** Function: " << F.getName() << '\n');
 132
 133   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 134   TTI = &getAnalysis<TargetTransformInfo>();
 135
 136   return OptimizeConstants(F);
 137 }
 138
 139 void ConstantHoisting::CollectConstant(User * U, unsigned Opcode,
 140                                        Intrinsic::ID IID, ConstantInt *C) {
 141   unsigned Cost;
 142   if (Opcode)
 143     Cost = TTI->getIntImmCost(Opcode, C->getValue(), C->getType());
 144   else
 145     Cost = TTI->getIntImmCost(IID, C->getValue(), C->getType());
 146
 147   if (Cost > TargetTransformInfo::TCC_Basic) {
 148     ConstantCandidate &CC = ConstantMap[C];
 149     CC.CumulativeCost += Cost;
 150     CC.Uses.push_back(U);
 151     DEBUG(dbgs() << "Collect constant " << *C << " with cost " << Cost
 152                  << " from " << *U << '\n');
 153   }
 154 }
 155
 156 /// \brief Scan the instruction or constant expression for expensive integer
 157 /// constants and record them in the constant map.
 158 void ConstantHoisting::CollectConstants(Instruction *I) {
 159   unsigned Opcode = 0;
 160   Intrinsic::ID IID = Intrinsic::not_intrinsic;
 161   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
 162     IID = II->getIntrinsicID();
 163   else
 164     Opcode = I->getOpcode();
 165
 166   // Scan all operands.
 167   for (User::op_iterator O = I->op_begin(), E = I->op_end(); O != E; ++O) {
 168     if (ConstantInt *C = dyn_cast<ConstantInt>(O)) {
 169       CollectConstant(I, Opcode, IID, C);
 170       continue;
 171     }
 172     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(O)) {
 173       // We only handle constant cast expressions.
 174       if (!CE->isCast())
 175         continue;
 176
 177       if (ConstantInt *C = dyn_cast<ConstantInt>(CE->getOperand(0))) {
 178         // Ignore the cast expression and use the opcode of the instruction.
 179         CollectConstant(CE, Opcode, IID, C);
 180         continue;
 181       }
 182     }
 183   }
 184 }
 185
 186 /// \brief Collect all integer constants in the function that cannot be folded
 187 /// into an instruction itself.
 188 void ConstantHoisting::CollectConstants(Function &F) {
 189   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 190     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 191       CollectConstants(I);
 192 }
 193
 194 /// \brief Find the base constant within the given range and rebase all other
 195 /// constants with respect to the base constant.
 196 void ConstantHoisting::FindAndMakeBaseConstant(ConstantMapType::iterator S,
 197                                                ConstantMapType::iterator E) {
 198   ConstantMapType::iterator MaxCostItr = S;
 199   unsigned NumUses = 0;
 200   // Use the constant that has the maximum cost as base constant.
 201   for (ConstantMapType::iterator I = S; I != E; ++I) {
 202     NumUses += I->second.Uses.size();
 203     if (I->second.CumulativeCost > MaxCostItr->second.CumulativeCost)
 204       MaxCostItr = I;
 205   }
 206
 207   // Don't hoist constants that have only one use.
 208   if (NumUses <= 1)
 209     return;
 210
 211   ConstantInfo CI;
 212   CI.BaseConstant = MaxCostItr->first;
 213   Type *Ty = CI.BaseConstant->getType();
 214   // Rebase the constants with respect to the base constant.
 215   for (ConstantMapType::iterator I = S; I != E; ++I) {
 216     APInt Diff = I->first->getValue() - CI.BaseConstant->getValue();
 217     ConstantInfo::RebasedConstantInfo RCI;
 218     RCI.OriginalConstant = I->first;
 219     RCI.Offset = ConstantInt::get(Ty, Diff);
 220     RCI.Uses = std::move(I->second.Uses);
 221     CI.RebasedConstants.push_back(RCI);
 222   }
 223   Constants.push_back(CI);
 224 }
 225
 226 /// \brief Finds and combines constants that can be easily rematerialized with
 227 /// an add from a common base constant.
 228 void ConstantHoisting::FindBaseConstants() {
 229   // Sort the constants by value and type. This invalidates the mapping.
 230   std::sort(ConstantMap.begin(), ConstantMap.end(),
 231             [](const std::pair<ConstantInt *, ConstantCandidate> &LHS,
 232                const std::pair<ConstantInt *, ConstantCandidate> &RHS) {
 233     if (LHS.first->getType() != RHS.first->getType())
 234       return LHS.first->getType()->getBitWidth() <
 235              RHS.first->getType()->getBitWidth();
 236     return LHS.first->getValue().ult(RHS.first->getValue());
 237   });
 238
 239   // Simple linear scan through the sorted constant map for viable merge
 240   // candidates.
 241   ConstantMapType::iterator MinValItr = ConstantMap.begin();
 242   for (ConstantMapType::iterator I = std::next(ConstantMap.begin()),
 243        E = ConstantMap.end(); I != E; ++I) {
 244     if (MinValItr->first->getType() == I->first->getType()) {
 245       // Check if the constant is in range of an add with immediate.
 246       APInt Diff = I->first->getValue() - MinValItr->first->getValue();
 247       if ((Diff.getBitWidth() <= 64) &&
 248           TTI->isLegalAddImmediate(Diff.getSExtValue()))
 249         continue;
 250     }
 251     // We either have now a different constant type or the constant is not in
 252     // range of an add with immediate anymore.
 253     FindAndMakeBaseConstant(MinValItr, I);
 254     // Start a new base constant search.
 255     MinValItr = I;
 256   }
 257   // Finalize the last base constant search.
 258   FindAndMakeBaseConstant(MinValItr, ConstantMap.end());
 259 }
 260
 261 /// \brief Records the basic block of the instruction or all basic blocks of the
 262 /// users of the constant expression.
 263 static void CollectBasicBlocks(SmallPtrSet<BasicBlock *, 4> &BBs, Function &F,
 264                                User *U) {
 265   if (Instruction *I = dyn_cast<Instruction>(U))
 266     BBs.insert(I->getParent());
 267   else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U))
 268     // Find all users of this constant expression.
 269     for (User *UU : CE->users())
 270       // Only record users that are instructions. We don't want to go down a
 271       // nested constant expression chain. Also check if the instruction is even
 272       // in the current function.
 273       if (Instruction *I = dyn_cast<Instruction>(UU))
 274         if(I->getParent()->getParent() == &F)
 275           BBs.insert(I->getParent());
 276 }
 277
 278 /// \brief Find the instruction we should insert the constant materialization
 279 /// before.
 280 static Instruction *getMatInsertPt(Instruction *I, const DominatorTree *DT) {
 281   if (!isa<PHINode>(I) && !isa<LandingPadInst>(I)) // Simple case.
 282     return I;
 283
 284   // We can't insert directly before a phi node or landing pad. Insert before
 285   // the terminator of the dominating block.
 286   assert(&I->getParent()->getParent()->getEntryBlock() != I->getParent() &&
 287          "PHI or landing pad in entry block!");
 288   BasicBlock *IDom = DT->getNode(I->getParent())->getIDom()->getBlock();
 289   return IDom->getTerminator();
 290 }
 291
 292 /// \brief Find an insertion point that dominates all uses.
 293 Instruction *ConstantHoisting::
 294 FindConstantInsertionPoint(Function &F, const ConstantInfo &CI) const {
 295   BasicBlock *Entry = &F.getEntryBlock();
 296
 297   // Collect all basic blocks.
 298   SmallPtrSet<BasicBlock *, 4> BBs;
 299   ConstantInfo::RebasedConstantListType::const_iterator RCI, RCE;
 300   for (RCI = CI.RebasedConstants.begin(), RCE = CI.RebasedConstants.end();
 301        RCI != RCE; ++RCI)
 302     for (SmallVectorImpl<User *>::const_iterator U = RCI->Uses.begin(),
 303          E = RCI->Uses.end(); U != E; ++U)
 304       CollectBasicBlocks(BBs, F, *U);
 305
 306   if (BBs.count(Entry))
 307     return getMatInsertPt(&Entry->front(), DT);
 308
 309   while (BBs.size() >= 2) {
 310     BasicBlock *BB, *BB1, *BB2;
 311     BB1 = *BBs.begin();
 312     BB2 = *std::next(BBs.begin());
 313     BB = DT->findNearestCommonDominator(BB1, BB2);
 314     if (BB == Entry)
 315       return getMatInsertPt(&Entry->front(), DT);
 316     BBs.erase(BB1);
 317     BBs.erase(BB2);
 318     BBs.insert(BB);
 319   }
 320   assert((BBs.size() == 1) && "Expected only one element.");
 321   Instruction &FirstInst = (*BBs.begin())->front();
 322   return getMatInsertPt(&FirstInst, DT);
 323 }
 324
 325 /// \brief Emit materialization code for all rebased constants and update their
 326 /// users.
 327 void ConstantHoisting::EmitBaseConstants(Function &F, User *U,
 328                                          Instruction *Base, Constant *Offset,
 329                                          ConstantInt *OriginalConstant) {
 330   if (Instruction *I = dyn_cast<Instruction>(U)) {
 331     Instruction *Mat = Base;
 332     if (!Offset->isNullValue()) {
 333       Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
 334                                    "const_mat", getMatInsertPt(I, DT));
 335
 336       // Use the same debug location as the instruction we are about to update.
 337       Mat->setDebugLoc(I->getDebugLoc());
 338
 339       DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
 340                    << " + " << *Offset << ") in BB "
 341                    << I->getParent()->getName() << '\n' << *Mat << '\n');
 342     }
 343     DEBUG(dbgs() << "Update: " << *I << '\n');
 344     I->replaceUsesOfWith(OriginalConstant, Mat);
 345     DEBUG(dbgs() << "To: " << *I << '\n');
 346     return;
 347   }
 348   assert(isa<ConstantExpr>(U) && "Expected a ConstantExpr.");
 349   ConstantExpr *CE = cast<ConstantExpr>(U);
 350   SmallVector<std::pair<Instruction *, Instruction *>, 8> WorkList;
 351   DEBUG(dbgs() << "Visit ConstantExpr " << *CE << '\n');
 352   for (User *UU : CE->users()) {
 353     DEBUG(dbgs() << "Check user "; UU->print(dbgs()); dbgs() << '\n');
 354     // We only handel instructions here and won't walk down a ConstantExpr chain
 355     // to replace all ConstExpr with instructions.
 356     if (Instruction *I = dyn_cast<Instruction>(UU)) {
 357       // Only update constant expressions in the current function.
 358       if (I->getParent()->getParent() != &F) {
 359         DEBUG(dbgs() << "Not in the same function - skip.\n");
 360         continue;
 361       }
 362
 363       Instruction *Mat = Base;
 364       Instruction *InsertBefore = getMatInsertPt(I, DT);
 365       if (!Offset->isNullValue()) {
 366         Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
 367                                      "const_mat", InsertBefore);
 368
 369         // Use the same debug location as the instruction we are about to
 370         // update.
 371         Mat->setDebugLoc(I->getDebugLoc());
 372
 373         DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
 374                      << " + " << *Offset << ") in BB "
 375                      << I->getParent()->getName() << '\n' << *Mat << '\n');
 376       }
 377       Instruction *ICE = CE->getAsInstruction();
 378       ICE->replaceUsesOfWith(OriginalConstant, Mat);
 379       ICE->insertBefore(InsertBefore);
 380
 381       // Use the same debug location as the instruction we are about to update.
 382       ICE->setDebugLoc(I->getDebugLoc());
 383
 384       WorkList.push_back(std::make_pair(I, ICE));
 385     } else {
 386       DEBUG(dbgs() << "Not an instruction - skip.\n");
 387     }
 388   }
 389   SmallVectorImpl<std::pair<Instruction *, Instruction *> >::iterator I, E;
 390   for (I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
 391     DEBUG(dbgs() << "Create instruction: " << *I->second << '\n');
 392     DEBUG(dbgs() << "Update: " << *I->first << '\n');
 393     I->first->replaceUsesOfWith(CE, I->second);
 394     DEBUG(dbgs() << "To: " << *I->first << '\n');
 395   }
 396 }
 397
 398 /// \brief Hoist and hide the base constant behind a bitcast and emit
 399 /// materialization code for derived constants.
 400 bool ConstantHoisting::EmitBaseConstants(Function &F) {
 401   bool MadeChange = false;
 402   SmallVectorImpl<ConstantInfo>::iterator CI, CE;
 403   for (CI = Constants.begin(), CE = Constants.end(); CI != CE; ++CI) {
 404     // Hoist and hide the base constant behind a bitcast.
 405     Instruction *IP = FindConstantInsertionPoint(F, *CI);
 406     IntegerType *Ty = CI->BaseConstant->getType();
 407     Instruction *Base = new BitCastInst(CI->BaseConstant, Ty, "const", IP);
 408     DEBUG(dbgs() << "Hoist constant (" << *CI->BaseConstant << ") to BB "
 409                  << IP->getParent()->getName() << '\n');
 410     NumConstantsHoisted++;
 411
 412     // Emit materialization code for all rebased constants.
 413     ConstantInfo::RebasedConstantListType::iterator RCI, RCE;
 414     for (RCI = CI->RebasedConstants.begin(), RCE = CI->RebasedConstants.end();
 415          RCI != RCE; ++RCI) {
 416       NumConstantsRebased++;
 417       for (SmallVectorImpl<User *>::iterator U = RCI->Uses.begin(),
 418            E = RCI->Uses.end(); U != E; ++U)
 419         EmitBaseConstants(F, *U, Base, RCI->Offset, RCI->OriginalConstant);
 420     }
 421
 422     // Use the same debug location as the last user of the constant.
 423     assert(!Base->use_empty() && "The use list is empty!?");
 424     assert(isa<Instruction>(Base->user_back()) &&
 425            "All uses should be instructions.");
 426     Base->setDebugLoc(cast<Instruction>(Base->user_back())->getDebugLoc());
 427
 428     // Correct for base constant, which we counted above too.
 429     NumConstantsRebased--;
 430     MadeChange = true;
 431   }
 432   return MadeChange;
 433 }
 434
 435 /// \brief Optimize expensive integer constants in the given function.
 436 bool ConstantHoisting::OptimizeConstants(Function &F) {
 437   bool MadeChange = false;
 438
 439   // Collect all constant candidates.
 440   CollectConstants(F);
 441
 442   // There are no constants to worry about.
 443   if (ConstantMap.empty())
 444     return MadeChange;
 445
 446   // Combine constants that can be easily materialized with an add from a common
 447   // base constant.
 448   FindBaseConstants();
 449
 450   // Finally hoist the base constant and emit materializating code for dependent
 451   // constants.
 452   MadeChange |= EmitBaseConstants(F);
 453
 454   ConstantMap.clear();
 455   Constants.clear();
 456
 457   return MadeChange;
 458 }