Add Constant Hoisting Pass

This pass identifies expensive constants to hoist and coalesces them to
better prepare it for SelectionDAG-based code generation. This works around the
limitations of the basic-block-at-a-time approach.

First it scans all instructions for integer constants and calculates its
cost. If the constant can be folded into the instruction (the cost is
TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
consider it expensive and leave it alone. This is the default behavior and
the default implementation of getIntImmCost will always return TCC_Free.

If the cost is more than TCC_BASIC, then the integer constant can't be folded
into the instruction and it might be beneficial to hoist the constant.
Similar constants are coalesced to reduce register pressure and
materialization code.

When a constant is hoisted, it is also hidden behind a bitcast to force it to
be live-out of the basic block. Otherwise the constant would be just
duplicated and each basic block would have its own copy in the SelectionDAG.
The SelectionDAG recognizes such constants as opaque and doesn't perform
certain transformations on them, which would create a new expensive constant.

This optimization is only applied to integer constants in instructions and
simple (this means not nested) constant cast experessions. For example:
%0 = load i64* inttoptr (i64 big_constant to i64*)

Reviewed by Eric

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@200022 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 433 insertions, 2 deletions

diff --git a/lib/Transforms/Scalar/CMakeLists.txt b/lib/Transforms/Scalar/CMakeLists.txt
index 0b2928677c..8a29b0c48c 100644
--- a/lib/Transforms/Scalar/CMakeLists.txt
+++ b/lib/Transforms/Scalar/CMakeLists.txt
@@ -1,6 +1,7 @@
 add_llvm_library(LLVMScalarOpts
   ADCE.cpp
   CodeGenPrepare.cpp
+  ConstantHoisting.cpp
   ConstantProp.cpp
   CorrelatedValuePropagation.cpp
   DCE.cpp
diff --git a/lib/Transforms/Scalar/CodeGenPrepare.cpp b/lib/Transforms/Scalar/CodeGenPrepare.cpp
index 38f587b2cc..6acbd5eaa1 100644
--- a/lib/Transforms/Scalar/CodeGenPrepare.cpp
+++ b/lib/Transforms/Scalar/CodeGenPrepare.cpp
@@ -240,7 +240,7 @@ bool CodeGenPrepare::runOnFunction(Function &F) {
 bool CodeGenPrepare::EliminateFallThrough(Function &F) {
   bool Changed = false;
   // Scan all of the blocks in the function, except for the entry block.
-  for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) {
+  for (Function::iterator I = llvm::next(F.begin()), E = F.end(); I != E; ) {
     BasicBlock *BB = I++;
     // If the destination block has a single pred, then this is a trivial
     // edge, just collapse it.
@@ -276,7 +276,7 @@ bool CodeGenPrepare::EliminateFallThrough(Function &F) {
 bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) {
   bool MadeChange = false;
   // Note that this intentionally skips the entry block.
-  for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) {
+  for (Function::iterator I = llvm::next(F.begin()), E = F.end(); I != E; ) {
     BasicBlock *BB = I++;
 
     // If this block doesn't end with an uncond branch, ignore it.
diff --git a/lib/Transforms/Scalar/ConstantHoisting.cpp b/lib/Transforms/Scalar/ConstantHoisting.cpp
new file mode 100644
index 0000000000..b6191bbfbf
--- /dev/null
+++ b/lib/Transforms/Scalar/ConstantHoisting.cpp
@@ -0,0 +1,429 @@
+//===- ConstantHoisting.cpp - Prepare code for expensive constants --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass identifies expensive constants to hoist and coalesces them to
+// better prepare it for SelectionDAG-based code generation. This works around
+// the limitations of the basic-block-at-a-time approach.
+//
+// First it scans all instructions for integer constants and calculates its
+// cost. If the constant can be folded into the instruction (the cost is
+// TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
+// consider it expensive and leave it alone. This is the default behavior and
+// the default implementation of getIntImmCost will always return TCC_Free.
+//
+// If the cost is more than TCC_BASIC, then the integer constant can't be folded
+// into the instruction and it might be beneficial to hoist the constant.
+// Similar constants are coalesced to reduce register pressure and
+// materialization code.
+//
+// When a constant is hoisted, it is also hidden behind a bitcast to force it to
+// be live-out of the basic block. Otherwise the constant would be just
+// duplicated and each basic block would have its own copy in the SelectionDAG.
+// The SelectionDAG recognizes such constants as opaque and doesn't perform
+// certain transformations on them, which would create a new expensive constant.
+//
+// This optimization is only applied to integer constants in instructions and
+// simple (this means not nested) constant cast experessions. For example:
+// %0 = load i64* inttoptr (i64 big_constant to i64*)
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "consthoist"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+
+STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
+STATISTIC(NumConstantsRebased, "Number of constants rebased");
+
+
+namespace {
+typedef SmallVector<User *, 4> ConstantUseListType;
+struct ConstantCandidate {
+  unsigned CumulativeCost;
+  ConstantUseListType Uses;
+};
+
+struct ConstantInfo {
+  ConstantInt *BaseConstant;
+  struct RebasedConstantInfo {
+    ConstantInt *OriginalConstant;
+    Constant *Offset;
+    ConstantUseListType Uses;
+  };
+  typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType;
+  RebasedConstantListType RebasedConstants;
+};
+
+class ConstantHoisting : public FunctionPass {
+  const TargetTransformInfo *TTI;
+  DominatorTree *DT;
+
+  /// Keeps track of expensive constants found in the function.
+  typedef MapVector<ConstantInt *, ConstantCandidate> ConstantMapType;
+  ConstantMapType ConstantMap;
+
+  /// These are the final constants we decided to hoist.
+  SmallVector<ConstantInfo, 4> Constants;
+public:
+  static char ID; // Pass identification, replacement for typeid
+  ConstantHoisting() : FunctionPass(ID), TTI(0) {
+    initializeConstantHoistingPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F);
+
+  const char *getPassName() const { return "Constant Hoisting"; }
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesCFG();
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<TargetTransformInfo>();
+  }
+
+private:
+  void CollectConstant(User *U, unsigned Opcode, Intrinsic::ID IID,
+                        ConstantInt *C);
+  void CollectConstants(Instruction *I);
+  void CollectConstants(Function &F);
+  void FindAndMakeBaseConstant(ConstantMapType::iterator S,
+                               ConstantMapType::iterator E);
+  void FindBaseConstants();
+  Instruction *FindConstantInsertionPoint(Function &F,
+                                          const ConstantInfo &CI) const;
+  void EmitBaseConstants(Function &F, User *U, Instruction *Base,
+                         Constant *Offset, ConstantInt *OriginalConstant);
+  bool EmitBaseConstants(Function &F);
+  bool OptimizeConstants(Function &F);
+};
+}
+
+char ConstantHoisting::ID = 0;
+INITIALIZE_PASS_BEGIN(ConstantHoisting, "consthoist", "Constant Hoisting",
+                      false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
+INITIALIZE_PASS_END(ConstantHoisting, "consthoist", "Constant Hoisting",
+                    false, false)
+
+FunctionPass *llvm::createConstantHoistingPass() {
+  return new ConstantHoisting();
+}
+
+/// \brief Perform the constant hoisting optimization for the given function.
+bool ConstantHoisting::runOnFunction(Function &F) {
+  DEBUG(dbgs() << "********** Constant Hoisting **********\n");
+  DEBUG(dbgs() << "********** Function: " << F.getName() << '\n');
+
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  TTI = &getAnalysis<TargetTransformInfo>();
+
+  return OptimizeConstants(F);
+}
+
+void ConstantHoisting::CollectConstant(User * U, unsigned Opcode,
+                                       Intrinsic::ID IID, ConstantInt *C) {
+  unsigned Cost;
+  if (Opcode)
+    Cost = TTI->getIntImmCost(Opcode, C->getValue(), C->getType());
+  else
+    Cost = TTI->getIntImmCost(IID, C->getValue(), C->getType());
+
+  if (Cost > TargetTransformInfo::TCC_Basic) {
+    ConstantCandidate &CC = ConstantMap[C];
+    CC.CumulativeCost += Cost;
+    CC.Uses.push_back(U);
+  }
+}
+
+/// \brief Scan the instruction or constant expression for expensive integer
+/// constants and record them in the constant map.
+void ConstantHoisting::CollectConstants(Instruction *I) {
+  unsigned Opcode = 0;
+  Intrinsic::ID IID = Intrinsic::not_intrinsic;
+  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
+    IID = II->getIntrinsicID();
+  else
+    Opcode = I->getOpcode();
+
+  // Scan all operands.
+  for (User::op_iterator O = I->op_begin(), E = I->op_end(); O != E; ++O) {
+    if (ConstantInt *C = dyn_cast<ConstantInt>(O)) {
+      CollectConstant(I, Opcode, IID, C);
+      continue;
+    }
+    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(O)) {
+      // We only handle constant cast expressions.
+      if (!CE->isCast())
+        continue;
+
+      if (ConstantInt *C = dyn_cast<ConstantInt>(CE->getOperand(0))) {
+        // Ignore the cast expression and use the opcode of the instruction.
+        CollectConstant(CE, Opcode, IID, C);
+        continue;
+      }
+    }
+  }
+}
+
+/// \brief Collect all integer constants in the function that cannot be folded
+/// into an instruction itself.
+void ConstantHoisting::CollectConstants(Function &F) {
+  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
+    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
+      CollectConstants(I);
+}
+
+/// \brief Compare function for sorting integer constants by type and by value
+/// within a type in ConstantMaps.
+static bool
+ConstantMapLessThan(const std::pair<ConstantInt *, ConstantCandidate> &LHS,
+                    const std::pair<ConstantInt *, ConstantCandidate> &RHS) {
+  if (LHS.first->getType() == RHS.first->getType())
+    return LHS.first->getValue().ult(RHS.first->getValue());
+  else
+    return LHS.first->getType()->getBitWidth() <
+           RHS.first->getType()->getBitWidth();
+}
+
+/// \brief Find the base constant within the given range and rebase all other
+/// constants with respect to the base constant.
+void ConstantHoisting::FindAndMakeBaseConstant(ConstantMapType::iterator S,
+                                               ConstantMapType::iterator E) {
+  ConstantMapType::iterator MaxCostItr = S;
+  unsigned NumUses = 0;
+  // Use the constant that has the maximum cost as base constant.
+  for (ConstantMapType::iterator I = S; I != E; ++I) {
+    NumUses += I->second.Uses.size();
+    if (I->second.CumulativeCost > MaxCostItr->second.CumulativeCost)
+      MaxCostItr = I;
+  }
+
+  // Don't hoist constants that have only one use.
+  if (NumUses <= 1)
+    return;
+
+  ConstantInfo CI;
+  CI.BaseConstant = MaxCostItr->first;
+  Type *Ty = CI.BaseConstant->getType();
+  // Rebase the constants with respect to the base constant.
+  for (ConstantMapType::iterator I = S; I != E; ++I) {
+    APInt Diff = I->first->getValue() - CI.BaseConstant->getValue();
+    ConstantInfo::RebasedConstantInfo RCI;
+    RCI.OriginalConstant = I->first;
+    RCI.Offset = ConstantInt::get(Ty, Diff);
+    RCI.Uses = llvm_move(I->second.Uses);
+    CI.RebasedConstants.push_back(RCI);
+  }
+  Constants.push_back(CI);
+}
+
+/// \brief Finds and combines constants that can be easily rematerialized with
+/// an add from a common base constant.
+void ConstantHoisting::FindBaseConstants() {
+  // Sort the constants by value and type. This invalidates the mapping.
+  std::sort(ConstantMap.begin(), ConstantMap.end(), ConstantMapLessThan);
+
+  // Simple linear scan through the sorted constant map for viable merge
+  // candidates.
+  ConstantMapType::iterator MinValItr = ConstantMap.begin();
+  for (ConstantMapType::iterator I = llvm::next(ConstantMap.begin()),
+       E = ConstantMap.end(); I != E; ++I) {
+    if (MinValItr->first->getType() == I->first->getType()) {
+      // Check if the constant is in range of an add with immediate.
+      APInt Diff = I->first->getValue() - MinValItr->first->getValue();
+      if ((Diff.getBitWidth() <= 64) &&
+          TTI->isLegalAddImmediate(Diff.getSExtValue()))
+        continue;
+    }
+    // We either have now a different constant type or the constant is not in
+    // range of an add with immediate anymore.
+    FindAndMakeBaseConstant(MinValItr, I);
+    // Start a new base constant search.
+    MinValItr = I;
+  }
+  // Finalize the last base constant search.
+  FindAndMakeBaseConstant(MinValItr, ConstantMap.end());
+}
+
+/// \brief Records the basic block of the instruction or all basic blocks of the
+/// users of the constant expression.
+static void CollectBasicBlocks(SmallPtrSet<BasicBlock *, 4> &BBs, User *U) {
+  if (Instruction *I = dyn_cast<Instruction>(U))
+    BBs.insert(I->getParent());
+  else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U))
+    // Find all users of this constant expression.
+    for (Value::use_iterator UU = CE->use_begin(), E = CE->use_end();
+         UU != E; ++UU)
+      // Only record users that are instructions. We don't want to go down a
+      // nested constant expression chain.
+      if (Instruction *I = dyn_cast<Instruction>(*UU))
+        BBs.insert(I->getParent());
+}
+
+/// \brief Find an insertion point that dominates all uses.
+Instruction *ConstantHoisting::
+FindConstantInsertionPoint(Function &F, const ConstantInfo &CI) const {
+  BasicBlock *Entry = &F.getEntryBlock();
+
+  // Collect all basic blocks.
+  SmallPtrSet<BasicBlock *, 4> BBs;
+  ConstantInfo::RebasedConstantListType::const_iterator RCI, RCE;
+  for (RCI = CI.RebasedConstants.begin(), RCE = CI.RebasedConstants.end();
+       RCI != RCE; ++RCI)
+    for (SmallVectorImpl<User *>::const_iterator U = RCI->Uses.begin(),
+         E = RCI->Uses.end(); U != E; ++U)
+        CollectBasicBlocks(BBs, *U);
+
+  if (BBs.count(Entry))
+    return Entry->getFirstInsertionPt();
+
+  while (BBs.size() >= 2) {
+    BasicBlock *BB, *BB1, *BB2;
+    BB1 = *BBs.begin();
+    BB2 = *llvm::next(BBs.begin());
+    BB = DT->findNearestCommonDominator(BB1, BB2);
+    if (BB == Entry)
+      return Entry->getFirstInsertionPt();
+    BBs.erase(BB1);
+    BBs.erase(BB2);
+    BBs.insert(BB);
+  }
+  assert((BBs.size() == 1) && "Expected only one element.");
+  return (*BBs.begin())->getFirstInsertionPt();
+}
+
+/// \brief Emit materialization code for all rebased constants and update their
+/// users.
+void ConstantHoisting::EmitBaseConstants(Function &F, User *U,
+                                         Instruction *Base, Constant *Offset,
+                                         ConstantInt *OriginalConstant) {
+  if (Instruction *I = dyn_cast<Instruction>(U)) {
+    Instruction *Mat = Base;
+    if (!Offset->isNullValue()) {
+      Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
+                                   "const_mat", I);
+
+      // Use the same debug location as the instruction we are about to update.
+      Mat->setDebugLoc(I->getDebugLoc());
+
+      DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
+                   << " + " << *Offset << ") in BB "
+                   << I->getParent()->getName() << '\n' << *Mat << '\n');
+    }
+    DEBUG(dbgs() << "Update: " << *I << '\n');
+    I->replaceUsesOfWith(OriginalConstant, Mat);
+    DEBUG(dbgs() << "To: " << *I << '\n');
+    return;
+  }
+  assert(isa<ConstantExpr>(U) && "Expected a ConstantExpr.");
+  ConstantExpr *CE = cast<ConstantExpr>(U);
+  for (Value::use_iterator UU = CE->use_begin(), E = CE->use_end();
+       UU != E; ++UU) {
+    // We only handel instructions here and won't walk down a ConstantExpr chain
+    // to replace all ConstExpr with instructions.
+    if (Instruction *I = dyn_cast<Instruction>(*UU)) {
+      Instruction *Mat = Base;
+      if (!Offset->isNullValue()) {
+        Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
+                                     "const_mat", I);
+
+        // Use the same debug location as the instruction we are about to
+        // update.
+        Mat->setDebugLoc(I->getDebugLoc());
+
+        DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
+                     << " + " << *Offset << ") in BB "
+                     << I->getParent()->getName() << '\n' << *Mat << '\n');
+      }
+      Instruction *ICE = CE->getAsInstruction();
+      ICE->replaceUsesOfWith(OriginalConstant, Mat);
+      ICE->insertBefore(I);
+
+      // Use the same debug location as the instruction we are about to update.
+      ICE->setDebugLoc(I->getDebugLoc());
+
+      DEBUG(dbgs() << "Create instruction: " << *ICE << '\n');
+      DEBUG(dbgs() << "Update: " << *I << '\n');
+      I->replaceUsesOfWith(CE, ICE);
+      DEBUG(dbgs() << "To: " << *I << '\n');
+    }
+  }
+}
+
+/// \brief Hoist and hide the base constant behind a bitcast and emit
+/// materialization code for derived constants.
+bool ConstantHoisting::EmitBaseConstants(Function &F) {
+  bool MadeChange = false;
+  SmallVectorImpl<ConstantInfo>::iterator CI, CE;
+  for (CI = Constants.begin(), CE = Constants.end(); CI != CE; ++CI) {
+    // Hoist and hide the base constant behind a bitcast.
+    Instruction *IP = FindConstantInsertionPoint(F, *CI);
+    IntegerType *Ty = CI->BaseConstant->getType();
+    Instruction *Base = new BitCastInst(CI->BaseConstant, Ty, "const", IP);
+    DEBUG(dbgs() << "Hoist constant (" << *CI->BaseConstant << ") to BB "
+                 << IP->getParent()->getName() << '\n');
+    NumConstantsHoisted++;
+
+    // Emit materialization code for all rebased constants.
+    ConstantInfo::RebasedConstantListType::iterator RCI, RCE;
+    for (RCI = CI->RebasedConstants.begin(), RCE = CI->RebasedConstants.end();
+         RCI != RCE; ++RCI) {
+      NumConstantsRebased++;
+      for (SmallVectorImpl<User *>::iterator U = RCI->Uses.begin(),
+           E = RCI->Uses.end(); U != E; ++U)
+        EmitBaseConstants(F, *U, Base, RCI->Offset, RCI->OriginalConstant);
+    }
+
+    // Use the same debug location as the last user of the constant.
+    assert(!Base->use_empty() && "The use list is empty!?");
+    assert(isa<Instruction>(Base->use_back()) &&
+           "All uses should be instructions.");
+    Base->setDebugLoc(cast<Instruction>(Base->use_back())->getDebugLoc());
+
+    // Correct for base constant, which we counted above too.
+    NumConstantsRebased--;
+    MadeChange = true;
+  }
+  return MadeChange;
+}
+
+/// \brief Optimize expensive integer constants in the given function.
+bool ConstantHoisting::OptimizeConstants(Function &F) {
+  bool MadeChange = false;
+
+  // Collect all constant candidates.
+  CollectConstants(F);
+
+  // There are no constants to worry about.
+  if (ConstantMap.empty())
+    return MadeChange;
+
+  // Combine constants that can be easily materialized with an add from a common
+  // base constant.
+  FindBaseConstants();
+
+  // Finaly hoist the base constant and emit materializating code for dependent
+  // constants.
+  MadeChange |= EmitBaseConstants(F);
+
+  ConstantMap.clear();
+  Constants.clear();
+
+  return MadeChange;
+}
diff --git a/lib/Transforms/Scalar/Scalar.cpp b/lib/Transforms/Scalar/Scalar.cpp
index 6983d06b68..f774874cb4 100644
--- a/lib/Transforms/Scalar/Scalar.cpp
+++ b/lib/Transforms/Scalar/Scalar.cpp
@@ -30,6 +30,7 @@ void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeADCEPass(Registry);
   initializeSampleProfileLoaderPass(Registry);
   initializeCodeGenPreparePass(Registry);
+  initializeConstantHoistingPass(Registry);
   initializeConstantPropagationPass(Registry);
   initializeCorrelatedValuePropagationPass(Registry);
   initializeDCEPass(Registry);