X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FConstantHoisting.cpp;h=84f7f5fff5b594b746aead66ee52810c57d6df24;hb=2027fcbfdaea79a5486db80a4da7407f50f7f4ec;hp=25fef5f500ff9d168eb4de86048744e8d247a897;hpb=8ebaf637500a6bac4bf734b1c7e8600ac9add6f7;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/ConstantHoisting.cpp b/lib/Transforms/Scalar/ConstantHoisting.cpp index 25fef5f500f..84f7f5fff5b 100644 --- a/lib/Transforms/Scalar/ConstantHoisting.cpp +++ b/lib/Transforms/Scalar/ConstantHoisting.cpp @@ -29,11 +29,10 @@ // 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: +// simple (this means not nested) constant cast expressions. For example: // %0 = load i64* inttoptr (i64 big_constant to i64*) //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "consthoist" #include "llvm/Transforms/Scalar.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" @@ -44,9 +43,13 @@ #include "llvm/IR/IntrinsicInst.h" #include "llvm/Pass.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include using namespace llvm; +#define DEBUG_TYPE "consthoist" + STATISTIC(NumConstantsHoisted, "Number of constants hoisted"); STATISTIC(NumConstantsRebased, "Number of constants rebased"); @@ -66,7 +69,7 @@ struct ConstantUser { ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) { } }; -/// \brief Keeps track of a constant candidate and its usees. +/// \brief Keeps track of a constant candidate and its uses. struct ConstantCandidate { ConstantUseListType Uses; ConstantInt *ConstInt; @@ -89,7 +92,7 @@ struct RebasedConstantInfo { Constant *Offset; RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset) - : Uses(Uses), Offset(Offset) { } + : Uses(std::move(Uses)), Offset(Offset) { } }; /// \brief A base constant and all its rebased constants. @@ -108,7 +111,6 @@ class ConstantHoisting : public FunctionPass { BasicBlock *Entry; /// Keeps track of constant candidates found in the function. - ConstCandMapType ConstCandMap; ConstCandVecType ConstCandVec; /// Keep track of cast instructions we already cloned. @@ -118,7 +120,8 @@ class ConstantHoisting : public FunctionPass { SmallVector ConstantVec; public: static char ID; // Pass identification, replacement for typeid - ConstantHoisting() : FunctionPass(ID), TTI(0), DT(0), Entry(0) { + ConstantHoisting() : FunctionPass(ID), TTI(nullptr), DT(nullptr), + Entry(nullptr) { initializeConstantHoistingPass(*PassRegistry::getPassRegistry()); } @@ -129,14 +132,14 @@ public: void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); } private: /// \brief Initialize the pass. void setup(Function &Fn) { DT = &getAnalysis().getDomTree(); - TTI = &getAnalysis(); + TTI = &getAnalysis().getTTI(Fn); Entry = &Fn.getEntryBlock(); } @@ -145,7 +148,6 @@ private: ConstantVec.clear(); ClonedCastMap.clear(); ConstCandVec.clear(); - ConstCandMap.clear(); TTI = nullptr; DT = nullptr; @@ -154,9 +156,11 @@ private: Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const; Instruction *findConstantInsertionPoint(const ConstantInfo &ConstInfo) const; - void collectConstantCandidates(Instruction *Inst, unsigned Idx, + void collectConstantCandidates(ConstCandMapType &ConstCandMap, + Instruction *Inst, unsigned Idx, ConstantInt *ConstInt); - void collectConstantCandidates(Instruction *Inst); + void collectConstantCandidates(ConstCandMapType &ConstCandMap, + Instruction *Inst); void collectConstantCandidates(Function &Fn); void findAndMakeBaseConstant(ConstCandVecType::iterator S, ConstCandVecType::iterator E); @@ -173,7 +177,7 @@ char ConstantHoisting::ID = 0; INITIALIZE_PASS_BEGIN(ConstantHoisting, "consthoist", "Constant Hoisting", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_AG_DEPENDENCY(TargetTransformInfo) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_END(ConstantHoisting, "consthoist", "Constant Hoisting", false, false) @@ -183,6 +187,9 @@ FunctionPass *llvm::createConstantHoistingPass() { /// \brief Perform the constant hoisting optimization for the given function. bool ConstantHoisting::runOnFunction(Function &Fn) { + if (skipOptnoneFunction(Fn)) + return false; + DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n"); DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n'); @@ -206,11 +213,20 @@ bool ConstantHoisting::runOnFunction(Function &Fn) { /// \brief Find the constant materialization insertion point. Instruction *ConstantHoisting::findMatInsertPt(Instruction *Inst, unsigned Idx) const { - // The simple and common case. - if (!isa(Inst) && !isa(Inst)) + // If the operand is a cast instruction, then we have to materialize the + // constant before the cast instruction. + if (Idx != ~0U) { + Value *Opnd = Inst->getOperand(Idx); + if (auto CastInst = dyn_cast(Opnd)) + if (CastInst->isCast()) + return CastInst; + } + + // The simple and common case. This also includes constant expressions. + if (!isa(Inst) && !Inst->isEHPad()) return Inst; - // We can't insert directly before a phi node or landing pad. Insert before + // We can't insert directly before a phi node or an eh pad. Insert before // the terminator of the incoming or dominating block. assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!"); if (Idx != ~0U && isa(Inst)) @@ -228,7 +244,7 @@ findConstantInsertionPoint(const ConstantInfo &ConstInfo) const { SmallPtrSet BBs; for (auto const &RCI : ConstInfo.RebasedConstants) for (auto const &U : RCI.Uses) - BBs.insert(U.Inst->getParent()); + BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent()); if (BBs.count(Entry)) return &Entry->front(); @@ -253,20 +269,21 @@ findConstantInsertionPoint(const ConstantInfo &ConstInfo) const { /// \brief Record constant integer ConstInt for instruction Inst at operand /// index Idx. /// -/// The operand at index Idx is not necessarily the constant inetger itself. It +/// The operand at index Idx is not necessarily the constant integer itself. It /// could also be a cast instruction or a constant expression that uses the // constant integer. -void ConstantHoisting::collectConstantCandidates(Instruction *Inst, +void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap, + Instruction *Inst, unsigned Idx, ConstantInt *ConstInt) { unsigned Cost; // Ask the target about the cost of materializing the constant for the given - // instruction. + // instruction and operand index. if (auto IntrInst = dyn_cast(Inst)) - Cost = TTI->getIntImmCost(IntrInst->getIntrinsicID(), + Cost = TTI->getIntImmCost(IntrInst->getIntrinsicID(), Idx, ConstInt->getValue(), ConstInt->getType()); else - Cost = TTI->getIntImmCost(Inst->getOpcode(), ConstInt->getValue(), + Cost = TTI->getIntImmCost(Inst->getOpcode(), Idx, ConstInt->getValue(), ConstInt->getType()); // Ignore cheap integer constants. @@ -292,7 +309,8 @@ void ConstantHoisting::collectConstantCandidates(Instruction *Inst, /// \brief Scan the instruction for expensive integer constants and record them /// in the constant candidate vector. -void ConstantHoisting::collectConstantCandidates(Instruction *Inst) { +void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap, + Instruction *Inst) { // Skip all cast instructions. They are visited indirectly later on. if (Inst->isCast()) return; @@ -306,9 +324,9 @@ void ConstantHoisting::collectConstantCandidates(Instruction *Inst) { for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) { Value *Opnd = Inst->getOperand(Idx); - // Vist constant integers. + // Visit constant integers. if (auto ConstInt = dyn_cast(Opnd)) { - collectConstantCandidates(Inst, Idx, ConstInt); + collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt); continue; } @@ -322,7 +340,7 @@ void ConstantHoisting::collectConstantCandidates(Instruction *Inst) { if (auto *ConstInt = dyn_cast(CastInst->getOperand(0))) { // Pretend the constant is directly used by the instruction and ignore // the cast instruction. - collectConstantCandidates(Inst, Idx, ConstInt); + collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt); continue; } } @@ -336,7 +354,7 @@ void ConstantHoisting::collectConstantCandidates(Instruction *Inst) { if (auto ConstInt = dyn_cast(ConstExpr->getOperand(0))) { // Pretend the constant is directly used by the instruction and ignore // the constant expression. - collectConstantCandidates(Inst, Idx, ConstInt); + collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt); continue; } } @@ -346,9 +364,10 @@ void ConstantHoisting::collectConstantCandidates(Instruction *Inst) { /// \brief Collect all integer constants in the function that cannot be folded /// into an instruction itself. void ConstantHoisting::collectConstantCandidates(Function &Fn) { - for (Function::iterator BB : Fn) - for (BasicBlock::iterator Inst : *BB) - collectConstantCandidates(Inst); + ConstCandMapType ConstCandMap; + for (BasicBlock &BB : Fn) + for (Instruction &Inst : BB) + collectConstantCandidates(ConstCandMap, &Inst); } /// \brief Find the base constant within the given range and rebase all other @@ -380,7 +399,7 @@ void ConstantHoisting::findAndMakeBaseConstant(ConstCandVecType::iterator S, ConstInfo.RebasedConstants.push_back( RebasedConstantInfo(std::move(ConstCand->Uses), Offset)); } - ConstantVec.push_back(ConstInfo); + ConstantVec.push_back(std::move(ConstInfo)); } /// \brief Finds and combines constant candidates that can be easily @@ -417,6 +436,34 @@ void ConstantHoisting::findBaseConstants() { findAndMakeBaseConstant(MinValItr, ConstCandVec.end()); } +/// \brief Updates the operand at Idx in instruction Inst with the result of +/// instruction Mat. If the instruction is a PHI node then special +/// handling for duplicate values form the same incomming basic block is +/// required. +/// \return The update will always succeed, but the return value indicated if +/// Mat was used for the update or not. +static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) { + if (auto PHI = dyn_cast(Inst)) { + // Check if any previous operand of the PHI node has the same incoming basic + // block. This is a very odd case that happens when the incoming basic block + // has a switch statement. In this case use the same value as the previous + // operand(s), otherwise we will fail verification due to different values. + // The values are actually the same, but the variable names are different + // and the verifier doesn't like that. + BasicBlock *IncomingBB = PHI->getIncomingBlock(Idx); + for (unsigned i = 0; i < Idx; ++i) { + if (PHI->getIncomingBlock(i) == IncomingBB) { + Value *IncomingVal = PHI->getIncomingValue(i); + Inst->setOperand(Idx, IncomingVal); + return false; + } + } + } + + Inst->setOperand(Idx, Mat); + return true; +} + /// \brief Emit materialization code for all rebased constants and update their /// users. void ConstantHoisting::emitBaseConstants(Instruction *Base, Constant *Offset, @@ -438,7 +485,8 @@ void ConstantHoisting::emitBaseConstants(Instruction *Base, Constant *Offset, // Visit constant integer. if (isa(Opnd)) { DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n'); - ConstUser.Inst->setOperand(ConstUser.OpndIdx, Mat); + if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat) && Offset) + Mat->eraseFromParent(); DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n'); return; } @@ -455,12 +503,12 @@ void ConstantHoisting::emitBaseConstants(Instruction *Base, Constant *Offset, ClonedCastInst->insertAfter(CastInst); // Use the same debug location as the original cast instruction. ClonedCastInst->setDebugLoc(CastInst->getDebugLoc()); - DEBUG(dbgs() << "Clone instruction: " << *ClonedCastInst << '\n' - << "To : " << *CastInst << '\n'); + DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n' + << "To : " << *ClonedCastInst << '\n'); } DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n'); - ConstUser.Inst->setOperand(ConstUser.OpndIdx, ClonedCastInst); + updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst); DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n'); return; } @@ -478,7 +526,11 @@ void ConstantHoisting::emitBaseConstants(Instruction *Base, Constant *Offset, DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n' << "From : " << *ConstExpr << '\n'); DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n'); - ConstUser.Inst->setOperand(ConstUser.OpndIdx, ConstExprInst); + if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ConstExprInst)) { + ConstExprInst->eraseFromParent(); + if (Offset) + Mat->eraseFromParent(); + } DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n'); return; } @@ -523,7 +575,7 @@ bool ConstantHoisting::emitBaseConstants() { void ConstantHoisting::deleteDeadCastInst() const { for (auto const &I : ClonedCastMap) if (I.first->use_empty()) - I.first->removeFromParent(); + I.first->eraseFromParent(); } /// \brief Optimize expensive integer constants in the given function. @@ -543,7 +595,7 @@ bool ConstantHoisting::optimizeConstants(Function &Fn) { if (ConstantVec.empty()) return false; - // Finally hoist the base constant and emit materializating code for dependent + // Finally hoist the base constant and emit materialization code for dependent // constants. bool MadeChange = emitBaseConstants();