Revert "Add Constant Hoisting Pass" (r200034)

This commit caused -Woverloaded-virtual warnings. The two new
TargetTransformInfo::getIntImmCost functions were only added to the superclass,
and to the X86 subclass. The other targets were not updated, and the
warning highlighted this by pointing out that e.g. ARMTTI::getIntImmCost was
hiding the two new getIntImmCost variants.

We could pacify the warning by adding "using TargetTransformInfo::getIntImmCost"
to the various subclasses, or turning it off, but I suspect that it's wrong to
leave the functions unimplemnted in those targets. The default implementations
return TCC_Free, which I don't think is right e.g. for ARM.

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

4 files changed, 2 insertions, 440 deletions

diff --git a/lib/Transforms/Scalar/CMakeLists.txt b/lib/Transforms/Scalar/CMakeLists.txt
index 8a29b0c48c..0b2928677c 100644
--- a/lib/Transforms/Scalar/CMakeLists.txt
+++ b/lib/Transforms/Scalar/CMakeLists.txt
@@ -1,7 +1,6 @@
 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 6acbd5eaa1..38f587b2cc 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 = llvm::next(F.begin()), E = F.end(); I != E; ) {
+  for (Function::iterator I = ++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 = llvm::next(F.begin()), E = F.end(); I != E; ) {
+  for (Function::iterator I = ++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
deleted file mode 100644
index 883385d377..0000000000
--- a/lib/Transforms/Scalar/ConstantHoisting.cpp
+++ /dev/null
@@ -1,436 +0,0 @@
-//===- 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, Function &F,
-                               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. Also check if the instruction is even
-      // in the current function.
-      if (Instruction *I = dyn_cast<Instruction>(*UU))
-        if(I->getParent()->getParent() == &F)
-          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, F, *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)) {
-      // Only update constant expressions in the current function.
-      if (I->getParent()->getParent() != &F)
-        continue;
-
-      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 f774874cb4..6983d06b68 100644
--- a/lib/Transforms/Scalar/Scalar.cpp
+++ b/lib/Transforms/Scalar/Scalar.cpp
@@ -30,7 +30,6 @@ void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeADCEPass(Registry);
   initializeSampleProfileLoaderPass(Registry);
   initializeCodeGenPreparePass(Registry);
-  initializeConstantHoistingPass(Registry);
   initializeConstantPropagationPass(Registry);
   initializeCorrelatedValuePropagationPass(Registry);
   initializeDCEPass(Registry);