llvm/lib/Transforms/Scalar/ConstantHoisting.cpp - toolchain/llvm-project - Gitiles

 //===- 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) override;

   const char *getPassName() const override { return "Constant Hoisting"; }

   void getAnalysisUsage(AnalysisUsage &AU) const override {
     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);
     DEBUG(dbgs() << "Collect constant " << *C << " with cost " << Cost
                  << " from " << *U << '\n');
   }
 }

 /// \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 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 = std::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(),
             [](const std::pair<ConstantInt *, ConstantCandidate> &LHS,
                const std::pair<ConstantInt *, ConstantCandidate> &RHS) {
     if (LHS.first->getType() != RHS.first->getType())
       return LHS.first->getType()->getBitWidth() <
              RHS.first->getType()->getBitWidth();
     return LHS.first->getValue().ult(RHS.first->getValue());
   });

   // Simple linear scan through the sorted constant map for viable merge
   // candidates.
   ConstantMapType::iterator MinValItr = ConstantMap.begin();
   for (ConstantMapType::iterator I = std::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 (User *UU : CE->users())
       // 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 the instruction we should insert the constant materialization
 /// before.
 static Instruction *getMatInsertPt(Instruction *I, const DominatorTree *DT) {
   if (!isa<PHINode>(I) && !isa<LandingPadInst>(I)) // Simple case.
     return I;

   // We can't insert directly before a phi node or landing pad. Insert before
   // the terminator of the dominating block.
   assert(&I->getParent()->getParent()->getEntryBlock() != I->getParent() &&
          "PHI or landing pad in entry block!");
   BasicBlock *IDom = DT->getNode(I->getParent())->getIDom()->getBlock();
   return IDom->getTerminator();
 }

 /// \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 getMatInsertPt(&Entry->front(), DT);

   while (BBs.size() >= 2) {
     BasicBlock *BB, *BB1, *BB2;
     BB1 = *BBs.begin();
     BB2 = *std::next(BBs.begin());
     BB = DT->findNearestCommonDominator(BB1, BB2);
     if (BB == Entry)
       return getMatInsertPt(&Entry->front(), DT);
     BBs.erase(BB1);
     BBs.erase(BB2);
     BBs.insert(BB);
   }
   assert((BBs.size() == 1) && "Expected only one element.");
   Instruction &FirstInst = (*BBs.begin())->front();
   return getMatInsertPt(&FirstInst, DT);
 }

 /// \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", getMatInsertPt(I, DT));

       // 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);
   SmallVector<std::pair<Instruction *, Instruction *>, 8> WorkList;
   DEBUG(dbgs() << "Visit ConstantExpr " << *CE << '\n');
   for (User *UU : CE->users()) {
     DEBUG(dbgs() << "Check user "; UU->print(dbgs()); dbgs() << '\n');
     // 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) {
         DEBUG(dbgs() << "Not in the same function - skip.\n");
         continue;
       }

       Instruction *Mat = Base;
       Instruction *InsertBefore = getMatInsertPt(I, DT);
       if (!Offset->isNullValue()) {
         Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
                                      "const_mat", InsertBefore);

         // 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(InsertBefore);

       // Use the same debug location as the instruction we are about to update.
       ICE->setDebugLoc(I->getDebugLoc());

       WorkList.push_back(std::make_pair(I, ICE));
     } else {
       DEBUG(dbgs() << "Not an instruction - skip.\n");
     }
   }
   SmallVectorImpl<std::pair<Instruction *, Instruction *> >::iterator I, E;
   for (I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
     DEBUG(dbgs() << "Create instruction: " << *I->second << '\n');
     DEBUG(dbgs() << "Update: " << *I->first << '\n');
     I->first->replaceUsesOfWith(CE, I->second);
     DEBUG(dbgs() << "To: " << *I->first << '\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->user_back()) &&
            "All uses should be instructions.");
     Base->setDebugLoc(cast<Instruction>(Base->user_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();

   // Finally hoist the base constant and emit materializating code for dependent
   // constants.
   MadeChange |= EmitBaseConstants(F);

   ConstantMap.clear();
   Constants.clear();

   return MadeChange;
 }
	//===- 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) override;

	const char *getPassName() const override { return "Constant Hoisting"; }

	void getAnalysisUsage(AnalysisUsage &AU) const override {
	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);
	DEBUG(dbgs() << "Collect constant " << *C << " with cost " << Cost
	<< " from " << *U << '\n');
	}
	}

	/// \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 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 = std::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(),
	[](const std::pair<ConstantInt *, ConstantCandidate> &LHS,
	const std::pair<ConstantInt *, ConstantCandidate> &RHS) {
	if (LHS.first->getType() != RHS.first->getType())
	return LHS.first->getType()->getBitWidth() <
	RHS.first->getType()->getBitWidth();
	return LHS.first->getValue().ult(RHS.first->getValue());
	});

	// Simple linear scan through the sorted constant map for viable merge
	// candidates.
	ConstantMapType::iterator MinValItr = ConstantMap.begin();
	for (ConstantMapType::iterator I = std::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 (User *UU : CE->users())
	// 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 the instruction we should insert the constant materialization
	/// before.
	static Instruction getMatInsertPt(Instruction I, const DominatorTree *DT) {
	if (!isa<PHINode>(I) && !isa<LandingPadInst>(I)) // Simple case.
	return I;

	// We can't insert directly before a phi node or landing pad. Insert before
	// the terminator of the dominating block.
	assert(&I->getParent()->getParent()->getEntryBlock() != I->getParent() &&
	"PHI or landing pad in entry block!");
	BasicBlock *IDom = DT->getNode(I->getParent())->getIDom()->getBlock();
	return IDom->getTerminator();
	}

	/// \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 getMatInsertPt(&Entry->front(), DT);

	while (BBs.size() >= 2) {
	BasicBlock BB, BB1, *BB2;
	BB1 = *BBs.begin();
	BB2 = *std::next(BBs.begin());
	BB = DT->findNearestCommonDominator(BB1, BB2);
	if (BB == Entry)
	return getMatInsertPt(&Entry->front(), DT);
	BBs.erase(BB1);
	BBs.erase(BB2);
	BBs.insert(BB);
	}
	assert((BBs.size() == 1) && "Expected only one element.");
	Instruction &FirstInst = (*BBs.begin())->front();
	return getMatInsertPt(&FirstInst, DT);
	}

	/// \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", getMatInsertPt(I, DT));

	// 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);
	SmallVector<std::pair<Instruction , Instruction >, 8> WorkList;
	DEBUG(dbgs() << "Visit ConstantExpr " << *CE << '\n');
	for (User *UU : CE->users()) {
	DEBUG(dbgs() << "Check user "; UU->print(dbgs()); dbgs() << '\n');
	// 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) {
	DEBUG(dbgs() << "Not in the same function - skip.\n");
	continue;
	}

	Instruction *Mat = Base;
	Instruction *InsertBefore = getMatInsertPt(I, DT);
	if (!Offset->isNullValue()) {
	Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
	"const_mat", InsertBefore);

	// 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(InsertBefore);

	// Use the same debug location as the instruction we are about to update.
	ICE->setDebugLoc(I->getDebugLoc());

	WorkList.push_back(std::make_pair(I, ICE));
	} else {
	DEBUG(dbgs() << "Not an instruction - skip.\n");
	}
	}
	SmallVectorImpl<std::pair<Instruction , Instruction > >::iterator I, E;
	for (I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
	DEBUG(dbgs() << "Create instruction: " << *I->second << '\n');
	DEBUG(dbgs() << "Update: " << *I->first << '\n');
	I->first->replaceUsesOfWith(CE, I->second);
	DEBUG(dbgs() << "To: " << *I->first << '\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->user_back()) &&
	"All uses should be instructions.");
	Base->setDebugLoc(cast<Instruction>(Base->user_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();

	// Finally hoist the base constant and emit materializating code for dependent
	// constants.
	MadeChange \|= EmitBaseConstants(F);

	ConstantMap.clear();
	Constants.clear();

	return MadeChange;
	}