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 (Value::use_iterator UU = CE->use_begin(), E = CE->use_end();
 270          UU != E; ++UU)
 271       // Only record users that are instructions. We don't want to go down a
 272       // nested constant expression chain. Also check if the instruction is even
 273       // in the current function.
 274       if (Instruction *I = dyn_cast<Instruction>(*UU))
 275         if(I->getParent()->getParent() == &F)
 276           BBs.insert(I->getParent());
 277 }
 278
 279 /// \brief Find the instruction we should insert the constant materialization
 280 /// before.
 281 static Instruction *getMatInsertPt(Instruction *I, const DominatorTree *DT) {
 282   if (!isa<PHINode>(I) && !isa<LandingPadInst>(I)) // Simple case.
 283     return I;
 284
 285   // We can't insert directly before a phi node or landing pad. Insert before
 286   // the terminator of the dominating block.
 287   assert(&I->getParent()->getParent()->getEntryBlock() != I->getParent() &&
 288          "PHI or landing pad in entry block!");
 289   BasicBlock *IDom = DT->getNode(I->getParent())->getIDom()->getBlock();
 290   return IDom->getTerminator();
 291 }
 292
 293 /// \brief Find an insertion point that dominates all uses.
 294 Instruction *ConstantHoisting::
 295 FindConstantInsertionPoint(Function &F, const ConstantInfo &CI) const {
 296   BasicBlock *Entry = &F.getEntryBlock();
 297
 298   // Collect all basic blocks.
 299   SmallPtrSet<BasicBlock *, 4> BBs;
 300   ConstantInfo::RebasedConstantListType::const_iterator RCI, RCE;
 301   for (RCI = CI.RebasedConstants.begin(), RCE = CI.RebasedConstants.end();
 302        RCI != RCE; ++RCI)
 303     for (SmallVectorImpl<User *>::const_iterator U = RCI->Uses.begin(),
 304          E = RCI->Uses.end(); U != E; ++U)
 305       CollectBasicBlocks(BBs, F, *U);
 306
 307   if (BBs.count(Entry))
 308     return getMatInsertPt(&Entry->front(), DT);
 309
 310   while (BBs.size() >= 2) {
 311     BasicBlock *BB, *BB1, *BB2;
 312     BB1 = *BBs.begin();
 313     BB2 = *std::next(BBs.begin());
 314     BB = DT->findNearestCommonDominator(BB1, BB2);
 315     if (BB == Entry)
 316       return getMatInsertPt(&Entry->front(), DT);
 317     BBs.erase(BB1);
 318     BBs.erase(BB2);
 319     BBs.insert(BB);
 320   }
 321   assert((BBs.size() == 1) && "Expected only one element.");
 322   Instruction &FirstInst = (*BBs.begin())->front();
 323   return getMatInsertPt(&FirstInst, DT);
 324 }
 325
 326 /// \brief Emit materialization code for all rebased constants and update their
 327 /// users.
 328 void ConstantHoisting::EmitBaseConstants(Function &F, User *U,
 329                                          Instruction *Base, Constant *Offset,
 330                                          ConstantInt *OriginalConstant) {
 331   if (Instruction *I = dyn_cast<Instruction>(U)) {
 332     Instruction *Mat = Base;
 333     if (!Offset->isNullValue()) {
 334       Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
 335                                    "const_mat", getMatInsertPt(I, DT));
 336
 337       // Use the same debug location as the instruction we are about to update.
 338       Mat->setDebugLoc(I->getDebugLoc());
 339
 340       DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
 341                    << " + " << *Offset << ") in BB "
 342                    << I->getParent()->getName() << '\n' << *Mat << '\n');
 343     }
 344     DEBUG(dbgs() << "Update: " << *I << '\n');
 345     I->replaceUsesOfWith(OriginalConstant, Mat);
 346     DEBUG(dbgs() << "To: " << *I << '\n');
 347     return;
 348   }
 349   assert(isa<ConstantExpr>(U) && "Expected a ConstantExpr.");
 350   ConstantExpr *CE = cast<ConstantExpr>(U);
 351   SmallVector<std::pair<Instruction *, Instruction *>, 8> WorkList;
 352   DEBUG(dbgs() << "Visit ConstantExpr " << *CE << '\n');
 353   for (Value::use_iterator UU = CE->use_begin(), E = CE->use_end();
 354        UU != E; ++UU) {
 355     DEBUG(dbgs() << "Check user "; UU->print(dbgs()); dbgs() << '\n');
 356     // We only handel instructions here and won't walk down a ConstantExpr chain
 357     // to replace all ConstExpr with instructions.
 358     if (Instruction *I = dyn_cast<Instruction>(*UU)) {
 359       // Only update constant expressions in the current function.
 360       if (I->getParent()->getParent() != &F) {
 361         DEBUG(dbgs() << "Not in the same function - skip.\n");
 362         continue;
 363       }
 364
 365       Instruction *Mat = Base;
 366       Instruction *InsertBefore = getMatInsertPt(I, DT);
 367       if (!Offset->isNullValue()) {
 368         Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
 369                                      "const_mat", InsertBefore);
 370
 371         // Use the same debug location as the instruction we are about to
 372         // update.
 373         Mat->setDebugLoc(I->getDebugLoc());
 374
 375         DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
 376                      << " + " << *Offset << ") in BB "
 377                      << I->getParent()->getName() << '\n' << *Mat << '\n');
 378       }
 379       Instruction *ICE = CE->getAsInstruction();
 380       ICE->replaceUsesOfWith(OriginalConstant, Mat);
 381       ICE->insertBefore(InsertBefore);
 382
 383       // Use the same debug location as the instruction we are about to update.
 384       ICE->setDebugLoc(I->getDebugLoc());
 385
 386       WorkList.push_back(std::make_pair(I, ICE));
 387     } else {
 388       DEBUG(dbgs() << "Not an instruction - skip.\n");
 389     }
 390   }
 391   SmallVectorImpl<std::pair<Instruction *, Instruction *> >::iterator I, E;
 392   for (I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
 393     DEBUG(dbgs() << "Create instruction: " << *I->second << '\n');
 394     DEBUG(dbgs() << "Update: " << *I->first << '\n');
 395     I->first->replaceUsesOfWith(CE, I->second);
 396     DEBUG(dbgs() << "To: " << *I->first << '\n');
 397   }
 398 }
 399
 400 /// \brief Hoist and hide the base constant behind a bitcast and emit
 401 /// materialization code for derived constants.
 402 bool ConstantHoisting::EmitBaseConstants(Function &F) {
 403   bool MadeChange = false;
 404   SmallVectorImpl<ConstantInfo>::iterator CI, CE;
 405   for (CI = Constants.begin(), CE = Constants.end(); CI != CE; ++CI) {
 406     // Hoist and hide the base constant behind a bitcast.
 407     Instruction *IP = FindConstantInsertionPoint(F, *CI);
 408     IntegerType *Ty = CI->BaseConstant->getType();
 409     Instruction *Base = new BitCastInst(CI->BaseConstant, Ty, "const", IP);
 410     DEBUG(dbgs() << "Hoist constant (" << *CI->BaseConstant << ") to BB "
 411                  << IP->getParent()->getName() << '\n');
 412     NumConstantsHoisted++;
 413
 414     // Emit materialization code for all rebased constants.
 415     ConstantInfo::RebasedConstantListType::iterator RCI, RCE;
 416     for (RCI = CI->RebasedConstants.begin(), RCE = CI->RebasedConstants.end();
 417          RCI != RCE; ++RCI) {
 418       NumConstantsRebased++;
 419       for (SmallVectorImpl<User *>::iterator U = RCI->Uses.begin(),
 420            E = RCI->Uses.end(); U != E; ++U)
 421         EmitBaseConstants(F, *U, Base, RCI->Offset, RCI->OriginalConstant);
 422     }
 423
 424     // Use the same debug location as the last user of the constant.
 425     assert(!Base->use_empty() && "The use list is empty!?");
 426     assert(isa<Instruction>(Base->use_back()) &&
 427            "All uses should be instructions.");
 428     Base->setDebugLoc(cast<Instruction>(Base->use_back())->getDebugLoc());
 429
 430     // Correct for base constant, which we counted above too.
 431     NumConstantsRebased--;
 432     MadeChange = true;
 433   }
 434   return MadeChange;
 435 }
 436
 437 /// \brief Optimize expensive integer constants in the given function.
 438 bool ConstantHoisting::OptimizeConstants(Function &F) {
 439   bool MadeChange = false;
 440
 441   // Collect all constant candidates.
 442   CollectConstants(F);
 443
 444   // There are no constants to worry about.
 445   if (ConstantMap.empty())
 446     return MadeChange;
 447
 448   // Combine constants that can be easily materialized with an add from a common
 449   // base constant.
 450   FindBaseConstants();
 451
 452   // Finally hoist the base constant and emit materializating code for dependent
 453   // constants.
 454   MadeChange |= EmitBaseConstants(F);
 455
 456   ConstantMap.clear();
 457   Constants.clear();
 458
 459   return MadeChange;
 460 }