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);
  90
  91   const char *getPassName() const { return "Constant Hoisting"; }
  92
  93   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  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 Compare function for sorting integer constants by type and by value
 195 /// within a type in ConstantMaps.
 196 static bool
 197 ConstantMapLessThan(const std::pair<ConstantInt *, ConstantCandidate> &LHS,
 198                     const std::pair<ConstantInt *, ConstantCandidate> &RHS) {
 199   if (LHS.first->getType() == RHS.first->getType())
 200     return LHS.first->getValue().ult(RHS.first->getValue());
 201   else
 202     return LHS.first->getType()->getBitWidth() <
 203            RHS.first->getType()->getBitWidth();
 204 }
 205
 206 /// \brief Find the base constant within the given range and rebase all other
 207 /// constants with respect to the base constant.
 208 void ConstantHoisting::FindAndMakeBaseConstant(ConstantMapType::iterator S,
 209                                                ConstantMapType::iterator E) {
 210   ConstantMapType::iterator MaxCostItr = S;
 211   unsigned NumUses = 0;
 212   // Use the constant that has the maximum cost as base constant.
 213   for (ConstantMapType::iterator I = S; I != E; ++I) {
 214     NumUses += I->second.Uses.size();
 215     if (I->second.CumulativeCost > MaxCostItr->second.CumulativeCost)
 216       MaxCostItr = I;
 217   }
 218
 219   // Don't hoist constants that have only one use.
 220   if (NumUses <= 1)
 221     return;
 222
 223   ConstantInfo CI;
 224   CI.BaseConstant = MaxCostItr->first;
 225   Type *Ty = CI.BaseConstant->getType();
 226   // Rebase the constants with respect to the base constant.
 227   for (ConstantMapType::iterator I = S; I != E; ++I) {
 228     APInt Diff = I->first->getValue() - CI.BaseConstant->getValue();
 229     ConstantInfo::RebasedConstantInfo RCI;
 230     RCI.OriginalConstant = I->first;
 231     RCI.Offset = ConstantInt::get(Ty, Diff);
 232     RCI.Uses = llvm_move(I->second.Uses);
 233     CI.RebasedConstants.push_back(RCI);
 234   }
 235   Constants.push_back(CI);
 236 }
 237
 238 /// \brief Finds and combines constants that can be easily rematerialized with
 239 /// an add from a common base constant.
 240 void ConstantHoisting::FindBaseConstants() {
 241   // Sort the constants by value and type. This invalidates the mapping.
 242   std::sort(ConstantMap.begin(), ConstantMap.end(), ConstantMapLessThan);
 243
 244   // Simple linear scan through the sorted constant map for viable merge
 245   // candidates.
 246   ConstantMapType::iterator MinValItr = ConstantMap.begin();
 247   for (ConstantMapType::iterator I = llvm::next(ConstantMap.begin()),
 248        E = ConstantMap.end(); I != E; ++I) {
 249     if (MinValItr->first->getType() == I->first->getType()) {
 250       // Check if the constant is in range of an add with immediate.
 251       APInt Diff = I->first->getValue() - MinValItr->first->getValue();
 252       if ((Diff.getBitWidth() <= 64) &&
 253           TTI->isLegalAddImmediate(Diff.getSExtValue()))
 254         continue;
 255     }
 256     // We either have now a different constant type or the constant is not in
 257     // range of an add with immediate anymore.
 258     FindAndMakeBaseConstant(MinValItr, I);
 259     // Start a new base constant search.
 260     MinValItr = I;
 261   }
 262   // Finalize the last base constant search.
 263   FindAndMakeBaseConstant(MinValItr, ConstantMap.end());
 264 }
 265
 266 /// \brief Records the basic block of the instruction or all basic blocks of the
 267 /// users of the constant expression.
 268 static void CollectBasicBlocks(SmallPtrSet<BasicBlock *, 4> &BBs, Function &F,
 269                                User *U) {
 270   if (Instruction *I = dyn_cast<Instruction>(U))
 271     BBs.insert(I->getParent());
 272   else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U))
 273     // Find all users of this constant expression.
 274     for (Value::use_iterator UU = CE->use_begin(), E = CE->use_end();
 275          UU != E; ++UU)
 276       // Only record users that are instructions. We don't want to go down a
 277       // nested constant expression chain. Also check if the instruction is even
 278       // in the current function.
 279       if (Instruction *I = dyn_cast<Instruction>(*UU))
 280         if(I->getParent()->getParent() == &F)
 281           BBs.insert(I->getParent());
 282 }
 283
 284 /// \brief Find the instruction we should insert the constant materialization
 285 /// before.
 286 static Instruction *getMatInsertPt(Instruction *I, const DominatorTree *DT) {
 287   if (!isa<PHINode>(I) && !isa<LandingPadInst>(I)) // Simple case.
 288     return I;
 289
 290   // We can't insert directly before a phi node or landing pad. Insert before
 291   // the terminator of the dominating block.
 292   assert(&I->getParent()->getParent()->getEntryBlock() != I->getParent() &&
 293          "PHI or landing pad in entry block!");
 294   BasicBlock *IDom = DT->getNode(I->getParent())->getIDom()->getBlock();
 295   return IDom->getTerminator();
 296 }
 297
 298 /// \brief Find an insertion point that dominates all uses.
 299 Instruction *ConstantHoisting::
 300 FindConstantInsertionPoint(Function &F, const ConstantInfo &CI) const {
 301   BasicBlock *Entry = &F.getEntryBlock();
 302
 303   // Collect all basic blocks.
 304   SmallPtrSet<BasicBlock *, 4> BBs;
 305   ConstantInfo::RebasedConstantListType::const_iterator RCI, RCE;
 306   for (RCI = CI.RebasedConstants.begin(), RCE = CI.RebasedConstants.end();
 307        RCI != RCE; ++RCI)
 308     for (SmallVectorImpl<User *>::const_iterator U = RCI->Uses.begin(),
 309          E = RCI->Uses.end(); U != E; ++U)
 310       CollectBasicBlocks(BBs, F, *U);
 311
 312   if (BBs.count(Entry))
 313     return getMatInsertPt(&Entry->front(), DT);
 314
 315   while (BBs.size() >= 2) {
 316     BasicBlock *BB, *BB1, *BB2;
 317     BB1 = *BBs.begin();
 318     BB2 = *llvm::next(BBs.begin());
 319     BB = DT->findNearestCommonDominator(BB1, BB2);
 320     if (BB == Entry)
 321       return getMatInsertPt(&Entry->front(), DT);
 322     BBs.erase(BB1);
 323     BBs.erase(BB2);
 324     BBs.insert(BB);
 325   }
 326   assert((BBs.size() == 1) && "Expected only one element.");
 327   Instruction &FirstInst = (*BBs.begin())->front();
 328   return getMatInsertPt(&FirstInst, DT);
 329 }
 330
 331 /// \brief Emit materialization code for all rebased constants and update their
 332 /// users.
 333 void ConstantHoisting::EmitBaseConstants(Function &F, User *U,
 334                                          Instruction *Base, Constant *Offset,
 335                                          ConstantInt *OriginalConstant) {
 336   if (Instruction *I = dyn_cast<Instruction>(U)) {
 337     Instruction *Mat = Base;
 338     if (!Offset->isNullValue()) {
 339       Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
 340                                    "const_mat", getMatInsertPt(I, DT));
 341
 342       // Use the same debug location as the instruction we are about to update.
 343       Mat->setDebugLoc(I->getDebugLoc());
 344
 345       DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
 346                    << " + " << *Offset << ") in BB "
 347                    << I->getParent()->getName() << '\n' << *Mat << '\n');
 348     }
 349     DEBUG(dbgs() << "Update: " << *I << '\n');
 350     I->replaceUsesOfWith(OriginalConstant, Mat);
 351     DEBUG(dbgs() << "To: " << *I << '\n');
 352     return;
 353   }
 354   assert(isa<ConstantExpr>(U) && "Expected a ConstantExpr.");
 355   ConstantExpr *CE = cast<ConstantExpr>(U);
 356   SmallVector<std::pair<Instruction *, Instruction *>, 8> WorkList;
 357   DEBUG(dbgs() << "Visit ConstantExpr " << *CE << '\n');
 358   for (Value::use_iterator UU = CE->use_begin(), E = CE->use_end();
 359        UU != E; ++UU) {
 360     DEBUG(dbgs() << "Check user "; UU->print(dbgs()); dbgs() << '\n');
 361     // We only handel instructions here and won't walk down a ConstantExpr chain
 362     // to replace all ConstExpr with instructions.
 363     if (Instruction *I = dyn_cast<Instruction>(*UU)) {
 364       // Only update constant expressions in the current function.
 365       if (I->getParent()->getParent() != &F) {
 366         DEBUG(dbgs() << "Not in the same function - skip.\n");
 367         continue;
 368       }
 369
 370       Instruction *Mat = Base;
 371       Instruction *InsertBefore = getMatInsertPt(I, DT);
 372       if (!Offset->isNullValue()) {
 373         Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
 374                                      "const_mat", InsertBefore);
 375
 376         // Use the same debug location as the instruction we are about to
 377         // update.
 378         Mat->setDebugLoc(I->getDebugLoc());
 379
 380         DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
 381                      << " + " << *Offset << ") in BB "
 382                      << I->getParent()->getName() << '\n' << *Mat << '\n');
 383       }
 384       Instruction *ICE = CE->getAsInstruction();
 385       ICE->replaceUsesOfWith(OriginalConstant, Mat);
 386       ICE->insertBefore(InsertBefore);
 387
 388       // Use the same debug location as the instruction we are about to update.
 389       ICE->setDebugLoc(I->getDebugLoc());
 390
 391       WorkList.push_back(std::make_pair(I, ICE));
 392     } else {
 393       DEBUG(dbgs() << "Not an instruction - skip.\n");
 394     }
 395   }
 396   SmallVectorImpl<std::pair<Instruction *, Instruction *> >::iterator I, E;
 397   for (I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
 398     DEBUG(dbgs() << "Create instruction: " << *I->second << '\n');
 399     DEBUG(dbgs() << "Update: " << *I->first << '\n');
 400     I->first->replaceUsesOfWith(CE, I->second);
 401     DEBUG(dbgs() << "To: " << *I->first << '\n');
 402   }
 403 }
 404
 405 /// \brief Hoist and hide the base constant behind a bitcast and emit
 406 /// materialization code for derived constants.
 407 bool ConstantHoisting::EmitBaseConstants(Function &F) {
 408   bool MadeChange = false;
 409   SmallVectorImpl<ConstantInfo>::iterator CI, CE;
 410   for (CI = Constants.begin(), CE = Constants.end(); CI != CE; ++CI) {
 411     // Hoist and hide the base constant behind a bitcast.
 412     Instruction *IP = FindConstantInsertionPoint(F, *CI);
 413     IntegerType *Ty = CI->BaseConstant->getType();
 414     Instruction *Base = new BitCastInst(CI->BaseConstant, Ty, "const", IP);
 415     DEBUG(dbgs() << "Hoist constant (" << *CI->BaseConstant << ") to BB "
 416                  << IP->getParent()->getName() << '\n');
 417     NumConstantsHoisted++;
 418
 419     // Emit materialization code for all rebased constants.
 420     ConstantInfo::RebasedConstantListType::iterator RCI, RCE;
 421     for (RCI = CI->RebasedConstants.begin(), RCE = CI->RebasedConstants.end();
 422          RCI != RCE; ++RCI) {
 423       NumConstantsRebased++;
 424       for (SmallVectorImpl<User *>::iterator U = RCI->Uses.begin(),
 425            E = RCI->Uses.end(); U != E; ++U)
 426         EmitBaseConstants(F, *U, Base, RCI->Offset, RCI->OriginalConstant);
 427     }
 428
 429     // Use the same debug location as the last user of the constant.
 430     assert(!Base->use_empty() && "The use list is empty!?");
 431     assert(isa<Instruction>(Base->use_back()) &&
 432            "All uses should be instructions.");
 433     Base->setDebugLoc(cast<Instruction>(Base->use_back())->getDebugLoc());
 434
 435     // Correct for base constant, which we counted above too.
 436     NumConstantsRebased--;
 437     MadeChange = true;
 438   }
 439   return MadeChange;
 440 }
 441
 442 /// \brief Optimize expensive integer constants in the given function.
 443 bool ConstantHoisting::OptimizeConstants(Function &F) {
 444   bool MadeChange = false;
 445
 446   // Collect all constant candidates.
 447   CollectConstants(F);
 448
 449   // There are no constants to worry about.
 450   if (ConstantMap.empty())
 451     return MadeChange;
 452
 453   // Combine constants that can be easily materialized with an add from a common
 454   // base constant.
 455   FindBaseConstants();
 456
 457   // Finally hoist the base constant and emit materializating code for dependent
 458   // constants.
 459   MadeChange |= EmitBaseConstants(F);
 460
 461   ConstantMap.clear();
 462   Constants.clear();
 463
 464   return MadeChange;
 465 }