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   }
 152 }
 153
 154 /// \brief Scan the instruction or constant expression for expensive integer
 155 /// constants and record them in the constant map.
 156 void ConstantHoisting::CollectConstants(Instruction *I) {
 157   unsigned Opcode = 0;
 158   Intrinsic::ID IID = Intrinsic::not_intrinsic;
 159   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
 160     IID = II->getIntrinsicID();
 161   else
 162     Opcode = I->getOpcode();
 163
 164   // Scan all operands.
 165   for (User::op_iterator O = I->op_begin(), E = I->op_end(); O != E; ++O) {
 166     if (ConstantInt *C = dyn_cast<ConstantInt>(O)) {
 167       CollectConstant(I, Opcode, IID, C);
 168       continue;
 169     }
 170     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(O)) {
 171       // We only handle constant cast expressions.
 172       if (!CE->isCast())
 173         continue;
 174
 175       if (ConstantInt *C = dyn_cast<ConstantInt>(CE->getOperand(0))) {
 176         // Ignore the cast expression and use the opcode of the instruction.
 177         CollectConstant(CE, Opcode, IID, C);
 178         continue;
 179       }
 180     }
 181   }
 182 }
 183
 184 /// \brief Collect all integer constants in the function that cannot be folded
 185 /// into an instruction itself.
 186 void ConstantHoisting::CollectConstants(Function &F) {
 187   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 188     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 189       CollectConstants(I);
 190 }
 191
 192 /// \brief Compare function for sorting integer constants by type and by value
 193 /// within a type in ConstantMaps.
 194 static bool
 195 ConstantMapLessThan(const std::pair<ConstantInt *, ConstantCandidate> &LHS,
 196                     const std::pair<ConstantInt *, ConstantCandidate> &RHS) {
 197   if (LHS.first->getType() == RHS.first->getType())
 198     return LHS.first->getValue().ult(RHS.first->getValue());
 199   else
 200     return LHS.first->getType()->getBitWidth() <
 201            RHS.first->getType()->getBitWidth();
 202 }
 203
 204 /// \brief Find the base constant within the given range and rebase all other
 205 /// constants with respect to the base constant.
 206 void ConstantHoisting::FindAndMakeBaseConstant(ConstantMapType::iterator S,
 207                                                ConstantMapType::iterator E) {
 208   ConstantMapType::iterator MaxCostItr = S;
 209   unsigned NumUses = 0;
 210   // Use the constant that has the maximum cost as base constant.
 211   for (ConstantMapType::iterator I = S; I != E; ++I) {
 212     NumUses += I->second.Uses.size();
 213     if (I->second.CumulativeCost > MaxCostItr->second.CumulativeCost)
 214       MaxCostItr = I;
 215   }
 216
 217   // Don't hoist constants that have only one use.
 218   if (NumUses <= 1)
 219     return;
 220
 221   ConstantInfo CI;
 222   CI.BaseConstant = MaxCostItr->first;
 223   Type *Ty = CI.BaseConstant->getType();
 224   // Rebase the constants with respect to the base constant.
 225   for (ConstantMapType::iterator I = S; I != E; ++I) {
 226     APInt Diff = I->first->getValue() - CI.BaseConstant->getValue();
 227     ConstantInfo::RebasedConstantInfo RCI;
 228     RCI.OriginalConstant = I->first;
 229     RCI.Offset = ConstantInt::get(Ty, Diff);
 230     RCI.Uses = llvm_move(I->second.Uses);
 231     CI.RebasedConstants.push_back(RCI);
 232   }
 233   Constants.push_back(CI);
 234 }
 235
 236 /// \brief Finds and combines constants that can be easily rematerialized with
 237 /// an add from a common base constant.
 238 void ConstantHoisting::FindBaseConstants() {
 239   // Sort the constants by value and type. This invalidates the mapping.
 240   std::sort(ConstantMap.begin(), ConstantMap.end(), ConstantMapLessThan);
 241
 242   // Simple linear scan through the sorted constant map for viable merge
 243   // candidates.
 244   ConstantMapType::iterator MinValItr = ConstantMap.begin();
 245   for (ConstantMapType::iterator I = llvm::next(ConstantMap.begin()),
 246        E = ConstantMap.end(); I != E; ++I) {
 247     if (MinValItr->first->getType() == I->first->getType()) {
 248       // Check if the constant is in range of an add with immediate.
 249       APInt Diff = I->first->getValue() - MinValItr->first->getValue();
 250       if ((Diff.getBitWidth() <= 64) &&
 251           TTI->isLegalAddImmediate(Diff.getSExtValue()))
 252         continue;
 253     }
 254     // We either have now a different constant type or the constant is not in
 255     // range of an add with immediate anymore.
 256     FindAndMakeBaseConstant(MinValItr, I);
 257     // Start a new base constant search.
 258     MinValItr = I;
 259   }
 260   // Finalize the last base constant search.
 261   FindAndMakeBaseConstant(MinValItr, ConstantMap.end());
 262 }
 263
 264 /// \brief Records the basic block of the instruction or all basic blocks of the
 265 /// users of the constant expression.
 266 static void CollectBasicBlocks(SmallPtrSet<BasicBlock *, 4> &BBs, Function &F,
 267                                User *U) {
 268   if (Instruction *I = dyn_cast<Instruction>(U))
 269     BBs.insert(I->getParent());
 270   else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U))
 271     // Find all users of this constant expression.
 272     for (Value::use_iterator UU = CE->use_begin(), E = CE->use_end();
 273          UU != E; ++UU)
 274       // Only record users that are instructions. We don't want to go down a
 275       // nested constant expression chain. Also check if the instruction is even
 276       // in the current function.
 277       if (Instruction *I = dyn_cast<Instruction>(*UU))
 278         if(I->getParent()->getParent() == &F)
 279           BBs.insert(I->getParent());
 280 }
 281
 282 /// \brief Find an insertion point that dominates all uses.
 283 Instruction *ConstantHoisting::
 284 FindConstantInsertionPoint(Function &F, const ConstantInfo &CI) const {
 285   BasicBlock *Entry = &F.getEntryBlock();
 286
 287   // Collect all basic blocks.
 288   SmallPtrSet<BasicBlock *, 4> BBs;
 289   ConstantInfo::RebasedConstantListType::const_iterator RCI, RCE;
 290   for (RCI = CI.RebasedConstants.begin(), RCE = CI.RebasedConstants.end();
 291        RCI != RCE; ++RCI)
 292     for (SmallVectorImpl<User *>::const_iterator U = RCI->Uses.begin(),
 293          E = RCI->Uses.end(); U != E; ++U)
 294         CollectBasicBlocks(BBs, F, *U);
 295
 296   if (BBs.count(Entry))
 297     return Entry->getFirstInsertionPt();
 298
 299   while (BBs.size() >= 2) {
 300     BasicBlock *BB, *BB1, *BB2;
 301     BB1 = *BBs.begin();
 302     BB2 = *llvm::next(BBs.begin());
 303     BB = DT->findNearestCommonDominator(BB1, BB2);
 304     if (BB == Entry)
 305       return Entry->getFirstInsertionPt();
 306     BBs.erase(BB1);
 307     BBs.erase(BB2);
 308     BBs.insert(BB);
 309   }
 310   assert((BBs.size() == 1) && "Expected only one element.");
 311   return (*BBs.begin())->getFirstInsertionPt();
 312 }
 313
 314 /// \brief Emit materialization code for all rebased constants and update their
 315 /// users.
 316 void ConstantHoisting::EmitBaseConstants(Function &F, User *U,
 317                                          Instruction *Base, Constant *Offset,
 318                                          ConstantInt *OriginalConstant) {
 319   if (Instruction *I = dyn_cast<Instruction>(U)) {
 320     Instruction *Mat = Base;
 321     if (!Offset->isNullValue()) {
 322       Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
 323                                    "const_mat", I);
 324
 325       // Use the same debug location as the instruction we are about to update.
 326       Mat->setDebugLoc(I->getDebugLoc());
 327
 328       DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
 329                    << " + " << *Offset << ") in BB "
 330                    << I->getParent()->getName() << '\n' << *Mat << '\n');
 331     }
 332     DEBUG(dbgs() << "Update: " << *I << '\n');
 333     I->replaceUsesOfWith(OriginalConstant, Mat);
 334     DEBUG(dbgs() << "To: " << *I << '\n');
 335     return;
 336   }
 337   assert(isa<ConstantExpr>(U) && "Expected a ConstantExpr.");
 338   ConstantExpr *CE = cast<ConstantExpr>(U);
 339   for (Value::use_iterator UU = CE->use_begin(), E = CE->use_end();
 340        UU != E; ++UU) {
 341     // We only handel instructions here and won't walk down a ConstantExpr chain
 342     // to replace all ConstExpr with instructions.
 343     if (Instruction *I = dyn_cast<Instruction>(*UU)) {
 344       // Only update constant expressions in the current function.
 345       if (I->getParent()->getParent() != &F)
 346         continue;
 347
 348       Instruction *Mat = Base;
 349       if (!Offset->isNullValue()) {
 350         Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
 351                                      "const_mat", I);
 352
 353         // Use the same debug location as the instruction we are about to
 354         // update.
 355         Mat->setDebugLoc(I->getDebugLoc());
 356
 357         DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
 358                      << " + " << *Offset << ") in BB "
 359                      << I->getParent()->getName() << '\n' << *Mat << '\n');
 360       }
 361       Instruction *ICE = CE->getAsInstruction();
 362       ICE->replaceUsesOfWith(OriginalConstant, Mat);
 363       ICE->insertBefore(I);
 364
 365       // Use the same debug location as the instruction we are about to update.
 366       ICE->setDebugLoc(I->getDebugLoc());
 367
 368       DEBUG(dbgs() << "Create instruction: " << *ICE << '\n');
 369       DEBUG(dbgs() << "Update: " << *I << '\n');
 370       I->replaceUsesOfWith(CE, ICE);
 371       DEBUG(dbgs() << "To: " << *I << '\n');
 372     }
 373   }
 374 }
 375
 376 /// \brief Hoist and hide the base constant behind a bitcast and emit
 377 /// materialization code for derived constants.
 378 bool ConstantHoisting::EmitBaseConstants(Function &F) {
 379   bool MadeChange = false;
 380   SmallVectorImpl<ConstantInfo>::iterator CI, CE;
 381   for (CI = Constants.begin(), CE = Constants.end(); CI != CE; ++CI) {
 382     // Hoist and hide the base constant behind a bitcast.
 383     Instruction *IP = FindConstantInsertionPoint(F, *CI);
 384     IntegerType *Ty = CI->BaseConstant->getType();
 385     Instruction *Base = new BitCastInst(CI->BaseConstant, Ty, "const", IP);
 386     DEBUG(dbgs() << "Hoist constant (" << *CI->BaseConstant << ") to BB "
 387                  << IP->getParent()->getName() << '\n');
 388     NumConstantsHoisted++;
 389
 390     // Emit materialization code for all rebased constants.
 391     ConstantInfo::RebasedConstantListType::iterator RCI, RCE;
 392     for (RCI = CI->RebasedConstants.begin(), RCE = CI->RebasedConstants.end();
 393          RCI != RCE; ++RCI) {
 394       NumConstantsRebased++;
 395       for (SmallVectorImpl<User *>::iterator U = RCI->Uses.begin(),
 396            E = RCI->Uses.end(); U != E; ++U)
 397         EmitBaseConstants(F, *U, Base, RCI->Offset, RCI->OriginalConstant);
 398     }
 399
 400     // Use the same debug location as the last user of the constant.
 401     assert(!Base->use_empty() && "The use list is empty!?");
 402     assert(isa<Instruction>(Base->use_back()) &&
 403            "All uses should be instructions.");
 404     Base->setDebugLoc(cast<Instruction>(Base->use_back())->getDebugLoc());
 405
 406     // Correct for base constant, which we counted above too.
 407     NumConstantsRebased--;
 408     MadeChange = true;
 409   }
 410   return MadeChange;
 411 }
 412
 413 /// \brief Optimize expensive integer constants in the given function.
 414 bool ConstantHoisting::OptimizeConstants(Function &F) {
 415   bool MadeChange = false;
 416
 417   // Collect all constant candidates.
 418   CollectConstants(F);
 419
 420   // There are no constants to worry about.
 421   if (ConstantMap.empty())
 422     return MadeChange;
 423
 424   // Combine constants that can be easily materialized with an add from a common
 425   // base constant.
 426   FindBaseConstants();
 427
 428   // Finaly hoist the base constant and emit materializating code for dependent
 429   // constants.
 430   MadeChange |= EmitBaseConstants(F);
 431
 432   ConstantMap.clear();
 433   Constants.clear();
 434
 435   return MadeChange;
 436 }