From ee3242ed0b25f1b2d53d47eabe727035f387123a Mon Sep 17 00:00:00 2001 From: Juergen Ributzka Date: Thu, 20 Mar 2014 20:17:13 +0000 Subject: Revert "[Constant Hoisting] Extend coverage of the constant hoisting pass." I will break this up into smaller pieces for review and recommit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@204393 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/TargetTransformInfo.h | 6 +- lib/Analysis/TargetTransformInfo.cpp | 16 +- lib/Target/X86/X86TargetTransformInfo.cpp | 47 +- lib/Transforms/Scalar/ConstantHoisting.cpp | 650 +++++++++++----------------- test/CodeGen/X86/lsr-interesting-step.ll | 14 +- test/CodeGen/X86/negate-add-zero.ll | 17 +- test/Transforms/ConstantHoisting/X86/phi.ll | 10 +- 7 files changed, 308 insertions(+), 452 deletions(-) diff --git a/include/llvm/Analysis/TargetTransformInfo.h b/include/llvm/Analysis/TargetTransformInfo.h index b11674898f..178d55305e 100644 --- a/include/llvm/Analysis/TargetTransformInfo.h +++ b/include/llvm/Analysis/TargetTransformInfo.h @@ -297,10 +297,10 @@ public: /// \brief Return the expected cost of materialization for the given integer /// immediate of the specified type for a given instruction. The cost can be /// zero if the immediate can be folded into the specified instruction. - virtual unsigned getIntImmCost(unsigned Opc, unsigned Idx, const APInt &Imm, + virtual unsigned getIntImmCost(unsigned Opcode, const APInt &Imm, + Type *Ty) const; + virtual unsigned getIntImmCost(Intrinsic::ID IID, const APInt &Imm, Type *Ty) const; - virtual unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, - const APInt &Imm, Type *Ty) const; /// @} /// \name Vector Target Information diff --git a/lib/Analysis/TargetTransformInfo.cpp b/lib/Analysis/TargetTransformInfo.cpp index 75d053c689..0dcdd12a40 100644 --- a/lib/Analysis/TargetTransformInfo.cpp +++ b/lib/Analysis/TargetTransformInfo.cpp @@ -148,14 +148,14 @@ unsigned TargetTransformInfo::getIntImmCost(const APInt &Imm, Type *Ty) const { return PrevTTI->getIntImmCost(Imm, Ty); } -unsigned TargetTransformInfo::getIntImmCost(unsigned Opc, unsigned Idx, - const APInt &Imm, Type *Ty) const { - return PrevTTI->getIntImmCost(Opc, Idx, Imm, Ty); +unsigned TargetTransformInfo::getIntImmCost(unsigned Opcode, const APInt &Imm, + Type *Ty) const { + return PrevTTI->getIntImmCost(Opcode, Imm, Ty); } -unsigned TargetTransformInfo::getIntImmCost(Intrinsic::ID IID, unsigned Idx, - const APInt &Imm, Type *Ty) const { - return PrevTTI->getIntImmCost(IID, Idx, Imm, Ty); +unsigned TargetTransformInfo::getIntImmCost(Intrinsic::ID IID, const APInt &Imm, + Type *Ty) const { + return PrevTTI->getIntImmCost(IID, Imm, Ty); } unsigned TargetTransformInfo::getNumberOfRegisters(bool Vector) const { @@ -539,12 +539,12 @@ struct NoTTI final : ImmutablePass, TargetTransformInfo { return TCC_Basic; } - unsigned getIntImmCost(unsigned Opcode, unsigned Idx, const APInt &Imm, + unsigned getIntImmCost(unsigned Opcode, const APInt &Imm, Type *Ty) const override { return TCC_Free; } - unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm, + unsigned getIntImmCost(Intrinsic::ID IID, const APInt &Imm, Type *Ty) const override { return TCC_Free; } diff --git a/lib/Target/X86/X86TargetTransformInfo.cpp b/lib/Target/X86/X86TargetTransformInfo.cpp index 87a5dd6536..1a0208c1a5 100644 --- a/lib/Target/X86/X86TargetTransformInfo.cpp +++ b/lib/Target/X86/X86TargetTransformInfo.cpp @@ -103,9 +103,9 @@ public: unsigned getIntImmCost(const APInt &Imm, Type *Ty) const override; - unsigned getIntImmCost(unsigned Opcode, unsigned Idx, const APInt &Imm, + unsigned getIntImmCost(unsigned Opcode, const APInt &Imm, Type *Ty) const override; - unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm, + unsigned getIntImmCost(Intrinsic::ID IID, const APInt &Imm, Type *Ty) const override; /// @} @@ -776,9 +776,6 @@ unsigned X86TTI::getIntImmCost(const APInt &Imm, Type *Ty) const { if (BitSize == 0) return ~0U; - if (Imm == 0) - return TCC_Free; - if (Imm.getBitWidth() <= 64 && (isInt<32>(Imm.getSExtValue()) || isUInt<32>(Imm.getZExtValue()))) return TCC_Basic; @@ -786,7 +783,7 @@ unsigned X86TTI::getIntImmCost(const APInt &Imm, Type *Ty) const { return 2 * TCC_Basic; } -unsigned X86TTI::getIntImmCost(unsigned Opcode, unsigned Idx, const APInt &Imm, +unsigned X86TTI::getIntImmCost(unsigned Opcode, const APInt &Imm, Type *Ty) const { assert(Ty->isIntegerTy()); @@ -794,15 +791,7 @@ unsigned X86TTI::getIntImmCost(unsigned Opcode, unsigned Idx, const APInt &Imm, if (BitSize == 0) return ~0U; - unsigned ImmIdx = ~0U; switch (Opcode) { - default: return TCC_Free; - case Instruction::GetElementPtr: - if (Idx != 0) - return TCC_Free; - case Instruction::Store: - ImmIdx = 0; - break; case Instruction::Add: case Instruction::Sub: case Instruction::Mul: @@ -817,31 +806,28 @@ unsigned X86TTI::getIntImmCost(unsigned Opcode, unsigned Idx, const APInt &Imm, case Instruction::Or: case Instruction::Xor: case Instruction::ICmp: - ImmIdx = 1; - break; + if (Imm.getBitWidth() <= 64 && isInt<32>(Imm.getSExtValue())) + return TCC_Free; + else + return X86TTI::getIntImmCost(Imm, Ty); case Instruction::Trunc: case Instruction::ZExt: case Instruction::SExt: case Instruction::IntToPtr: case Instruction::PtrToInt: case Instruction::BitCast: - case Instruction::PHI: case Instruction::Call: case Instruction::Select: case Instruction::Ret: case Instruction::Load: - break; + case Instruction::Store: + return X86TTI::getIntImmCost(Imm, Ty); } - - if ((Idx == ImmIdx) && - Imm.getBitWidth() <= 64 && isInt<32>(Imm.getSExtValue())) - return TCC_Free; - - return X86TTI::getIntImmCost(Imm, Ty); + return TargetTransformInfo::getIntImmCost(Opcode, Imm, Ty); } -unsigned X86TTI::getIntImmCost(Intrinsic::ID IID, unsigned Idx, - const APInt &Imm, Type *Ty) const { +unsigned X86TTI::getIntImmCost(Intrinsic::ID IID, const APInt &Imm, + Type *Ty) const { assert(Ty->isIntegerTy()); unsigned BitSize = Ty->getPrimitiveSizeInBits(); @@ -849,24 +835,21 @@ unsigned X86TTI::getIntImmCost(Intrinsic::ID IID, unsigned Idx, return ~0U; switch (IID) { - default: return TCC_Free; + default: return TargetTransformInfo::getIntImmCost(IID, Imm, Ty); case Intrinsic::sadd_with_overflow: case Intrinsic::uadd_with_overflow: case Intrinsic::ssub_with_overflow: case Intrinsic::usub_with_overflow: case Intrinsic::smul_with_overflow: case Intrinsic::umul_with_overflow: - if ((Idx == 1) && Imm.getBitWidth() <= 64 && isInt<32>(Imm.getSExtValue())) + if (Imm.getBitWidth() <= 64 && isInt<32>(Imm.getSExtValue())) return TCC_Free; else return X86TTI::getIntImmCost(Imm, Ty); case Intrinsic::experimental_stackmap: - if (Idx < 2) - return TCC_Free; case Intrinsic::experimental_patchpoint_void: case Intrinsic::experimental_patchpoint_i64: - if ((Idx < 4 ) || - (Imm.getBitWidth() <= 64 && isInt<64>(Imm.getSExtValue()))) + if (Imm.getBitWidth() <= 64 && isInt<64>(Imm.getSExtValue())) return TCC_Free; else return X86TTI::getIntImmCost(Imm, Ty); diff --git a/lib/Transforms/Scalar/ConstantHoisting.cpp b/lib/Transforms/Scalar/ConstantHoisting.cpp index 016f7c1711..6cfcec547d 100644 --- a/lib/Transforms/Scalar/ConstantHoisting.cpp +++ b/lib/Transforms/Scalar/ConstantHoisting.cpp @@ -35,14 +35,15 @@ #define DEBUG_TYPE "consthoist" #include "llvm/Transforms/Scalar.h" +#include "llvm/ADT/MapVector.h" #include "llvm/ADT/SmallSet.h" -#include "llvm/ADT/SmallVector.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; @@ -50,80 +51,42 @@ using namespace llvm; STATISTIC(NumConstantsHoisted, "Number of constants hoisted"); STATISTIC(NumConstantsRebased, "Number of constants rebased"); -namespace { -struct ConstantUser; -struct RebasedConstantInfo; - -typedef SmallVector ConstantUseListType; -typedef SmallVector RebasedConstantListType; - -/// \brief Keeps track of the user of a constant and the operand index where the -/// constant is used. -struct ConstantUser { - Instruction *Inst; - unsigned OpndIdx; - - ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) { } -}; -/// \brief Keeps track of a constant candidate and its usees. +namespace { +typedef SmallVector ConstantUseListType; struct ConstantCandidate { - ConstantUseListType Uses; - ConstantInt *ConstInt; unsigned CumulativeCost; - - ConstantCandidate(ConstantInt *ConstInt) - : ConstInt(ConstInt), CumulativeCost(0) { } - - /// \brief Add the user to the use list and update the cost. - void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) { - CumulativeCost += Cost; - Uses.push_back(ConstantUser(Inst, Idx)); - } -}; - -/// \brief This represents a constant that has been rebased with respect to a -/// base constant. The difference to the base constant is recorded in Offset. -struct RebasedConstantInfo { ConstantUseListType Uses; - Constant *Offset; - mutable BasicBlock *IDom; - - RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset) - : Uses(Uses), Offset(Offset), IDom(nullptr) { } }; -/// \brief A base constant and all its rebased constants. struct ConstantInfo { ConstantInt *BaseConstant; + struct RebasedConstantInfo { + ConstantInt *OriginalConstant; + Constant *Offset; + ConstantUseListType Uses; + }; + typedef SmallVector RebasedConstantListType; RebasedConstantListType RebasedConstants; }; -/// \brief The constant hoisting pass. class ConstantHoisting : public FunctionPass { - typedef DenseMap ConstCandMapType; - typedef std::vector ConstCandVecType; - const TargetTransformInfo *TTI; DominatorTree *DT; - BasicBlock *Entry; - - /// Keeps track of constant candidates found in the function. - ConstCandMapType ConstCandMap; - ConstCandVecType ConstCandVec; - /// Keep track of cast instructions we already cloned. - SmallDenseMap ClonedCastMap; + /// Keeps track of expensive constants found in the function. + typedef MapVector ConstantMapType; + ConstantMapType ConstantMap; /// These are the final constants we decided to hoist. - SmallVector ConstantVec; + SmallVector Constants; public: static char ID; // Pass identification, replacement for typeid - ConstantHoisting() : FunctionPass(ID), TTI(0), DT(0), Entry(0) { + ConstantHoisting() : FunctionPass(ID), TTI(0) { initializeConstantHoistingPass(*PassRegistry::getPassRegistry()); } - bool runOnFunction(Function &Fn) override; + bool runOnFunction(Function &F) override; const char *getPassName() const override { return "Constant Hoisting"; } @@ -134,49 +97,19 @@ public: } private: - /// \brief Initialize the pass. - void setup(Function &Fn) { - DT = &getAnalysis().getDomTree(); - TTI = &getAnalysis(); - Entry = &Fn.getEntryBlock(); - } - - /// \brief Cleanup. - void cleanup() { - ConstantVec.clear(); - ClonedCastMap.clear(); - ConstCandVec.clear(); - ConstCandMap.clear(); - - TTI = nullptr; - DT = nullptr; - Entry = nullptr; - } - - /// \brief Find the common dominator of all uses and cache the result for - /// future lookup. - BasicBlock *getIDom(const RebasedConstantInfo &RCI) const { - if (RCI.IDom) - return RCI.IDom; - RCI.IDom = findIDomOfAllUses(RCI.Uses); - assert(RCI.IDom && "Invalid IDom."); - return RCI.IDom; - } - - BasicBlock *findIDomOfAllUses(const ConstantUseListType &Uses) const; - Instruction *findMatInsertPt(Instruction *I, unsigned Idx = ~0U) const; - Instruction *findConstantInsertionPoint(const ConstantInfo &CI) const; - void collectConstantCandidates(Instruction *I, unsigned Idx, ConstantInt *C); - void collectConstantCandidates(Instruction *I); - void collectConstantCandidates(Function &Fn); - void findAndMakeBaseConstant(ConstCandVecType::iterator S, - ConstCandVecType::iterator E); - void findBaseConstants(); - void emitBaseConstants(Instruction *Base, Constant *Offset, - const ConstantUser &CU); - bool emitBaseConstants(); - void deleteDeadCastInst() const; - bool optimizeConstants(Function &F); + 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); }; } @@ -193,352 +126,297 @@ FunctionPass *llvm::createConstantHoistingPass() { } /// \brief Perform the constant hoisting optimization for the given function. -bool ConstantHoisting::runOnFunction(Function &Fn) { - DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n"); - DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n'); - - setup(Fn); - - bool MadeChange = optimizeConstants(Fn); - - if (MadeChange) { - DEBUG(dbgs() << "********** Function after Constant Hoisting: " - << Fn.getName() << '\n'); - DEBUG(dbgs() << Fn); - } - DEBUG(dbgs() << "********** End Constant Hoisting **********\n"); - - cleanup(); - - return MadeChange; -} - -/// \brief Find nearest common dominator of all uses. -/// FIXME: Replace this with NearestCommonDominator once it is in common code. -BasicBlock * -ConstantHoisting::findIDomOfAllUses(const ConstantUseListType &Uses) const { - // Collect all basic blocks. - SmallPtrSet BBs; - for (auto const &U : Uses) - BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent()); +bool ConstantHoisting::runOnFunction(Function &F) { + DEBUG(dbgs() << "********** Constant Hoisting **********\n"); + DEBUG(dbgs() << "********** Function: " << F.getName() << '\n'); - if (BBs.count(Entry)) - return Entry; + DT = &getAnalysis().getDomTree(); + TTI = &getAnalysis(); - 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 Entry; - BBs.erase(BB1); - BBs.erase(BB2); - BBs.insert(BB); - } - assert((BBs.size() == 1) && "Expected only one element."); - return *BBs.begin(); -} - -/// \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)) - return Inst; - - // We can't insert directly before a phi node or landing 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)) - return cast(Inst)->getIncomingBlock(Idx)->getTerminator(); - - BasicBlock *IDom = DT->getNode(Inst->getParent())->getIDom()->getBlock(); - return IDom->getTerminator(); -} - -/// \brief Find an insertion point that dominates all uses. -Instruction *ConstantHoisting:: -findConstantInsertionPoint(const ConstantInfo &ConstInfo) const { - assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry."); - // Collect all IDoms. - SmallPtrSet BBs; - for (auto const &RCI : ConstInfo.RebasedConstants) - BBs.insert(getIDom(RCI)); - - assert(!BBs.empty() && "No dominators!?"); - - if (BBs.count(Entry)) - return &Entry->front(); - - 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 &Entry->front(); - BBs.erase(BB1); - BBs.erase(BB2); - BBs.insert(BB); - } - assert((BBs.size() == 1) && "Expected only one element."); - Instruction &FirstInst = (*BBs.begin())->front(); - return findMatInsertPt(&FirstInst); + return OptimizeConstants(F); } - -/// \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 -/// could also be a cast instruction or a constant expression that uses the -// constant integer. -void ConstantHoisting::collectConstantCandidates(Instruction *Inst, - unsigned Idx, - ConstantInt *ConstInt) { +void ConstantHoisting::CollectConstant(User * U, unsigned Opcode, + Intrinsic::ID IID, ConstantInt *C) { unsigned Cost; - // Ask the target about the cost of materializing the constant for the given - // instruction and operand index. - if (auto IntrInst = dyn_cast(Inst)) - Cost = TTI->getIntImmCost(IntrInst->getIntrinsicID(), Idx, - ConstInt->getValue(), ConstInt->getType()); + if (Opcode) + Cost = TTI->getIntImmCost(Opcode, C->getValue(), C->getType()); else - Cost = TTI->getIntImmCost(Inst->getOpcode(), Idx, ConstInt->getValue(), - ConstInt->getType()); + Cost = TTI->getIntImmCost(IID, C->getValue(), C->getType()); - // Ignore cheap integer constants. if (Cost > TargetTransformInfo::TCC_Basic) { - ConstCandMapType::iterator Itr; - bool Inserted; - std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(ConstInt, 0)); - if (Inserted) { - ConstCandVec.push_back(ConstantCandidate(ConstInt)); - Itr->second = ConstCandVec.size() - 1; - } - ConstCandVec[Itr->second].addUser(Inst, Idx, Cost); - DEBUG(if (auto ConstInt = dyn_cast(Inst->getOperand(Idx))) - dbgs() << "Collect constant " << *ConstInt << " from " << *Inst - << " with cost " << Cost << '\n'; - else - dbgs() << "Collect constant " << *ConstInt << " indirectly from " - << *Inst << " via " << *Inst->getOperand(Idx) << " with cost " - << Cost << '\n'; - ); + 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 for expensive integer constants and record them -/// in the constant candidate vector. -void ConstantHoisting::collectConstantCandidates(Instruction *Inst) { - // Skip all cast instructions. They are visited indirectly later on. - if (Inst->isCast()) - return; - - // Can't handle inline asm. Skip it. - if (auto Call = dyn_cast(Inst)) - if (isa(Call->getCalledValue())) - return; +/// \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(I)) + IID = II->getIntrinsicID(); + else + Opcode = I->getOpcode(); // Scan all operands. - for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) { - Value *Opnd = Inst->getOperand(Idx); - - // Vist constant integers. - if (auto ConstInt = dyn_cast(Opnd)) { - collectConstantCandidates(Inst, Idx, ConstInt); + for (User::op_iterator O = I->op_begin(), E = I->op_end(); O != E; ++O) { + if (ConstantInt *C = dyn_cast(O)) { + CollectConstant(I, Opcode, IID, C); continue; } - - // Visit cast instructions that have constant integers. - if (auto CastInst = dyn_cast(Opnd)) { - // Only visit cast instructions, which have been skipped. All other - // instructions should have already been visited. - if (!CastInst->isCast()) + if (ConstantExpr *CE = dyn_cast(O)) { + // We only handle constant cast expressions. + if (!CE->isCast()) continue; - 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); + if (ConstantInt *C = dyn_cast(CE->getOperand(0))) { + // Ignore the cast expression and use the opcode of the instruction. + CollectConstant(CE, Opcode, IID, C); continue; } } - - // Visit constant expressions that have constant integers. - if (auto ConstExpr = dyn_cast(Opnd)) { - // Only visit constant cast expressions. - if (!ConstExpr->isCast()) - continue; - - 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); - continue; - } - } - } // end of for all operands + } } /// \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 I : *BB) - collectConstantCandidates(I); +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(ConstCandVecType::iterator S, - ConstCandVecType::iterator E) { - auto MaxCostItr = S; +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 (auto ConstCand = S; ConstCand != E; ++ConstCand) { - NumUses += ConstCand->Uses.size(); - if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost) - MaxCostItr = ConstCand; + 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 ConstInfo; - ConstInfo.BaseConstant = MaxCostItr->ConstInt; - Type *Ty = ConstInfo.BaseConstant->getType(); - + ConstantInfo CI; + CI.BaseConstant = MaxCostItr->first; + Type *Ty = CI.BaseConstant->getType(); // Rebase the constants with respect to the base constant. - for (auto ConstCand = S; ConstCand != E; ++ConstCand) { - APInt Diff = ConstCand->ConstInt->getValue() - - ConstInfo.BaseConstant->getValue(); - Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff); - ConstInfo.RebasedConstants.push_back( - RebasedConstantInfo(std::move(ConstCand->Uses), Offset)); + 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); } - ConstantVec.push_back(ConstInfo); + Constants.push_back(CI); } -/// \brief Finds and combines constant candidates 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(ConstCandVec.begin(), ConstCandVec.end(), - [](const ConstantCandidate &LHS, const ConstantCandidate &RHS) { - if (LHS.ConstInt->getType() != RHS.ConstInt->getType()) - return LHS.ConstInt->getType()->getBitWidth() < - RHS.ConstInt->getType()->getBitWidth(); - return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue()); - }); - - // Simple linear scan through the sorted constant candidate vector for viable - // merge candidates. - auto MinValItr = ConstCandVec.begin(); - for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end(); - CC != E; ++CC) { - if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) { +/// \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 &LHS, + const std::pair &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 = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue(); + 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, CC); + FindAndMakeBaseConstant(MinValItr, I); // Start a new base constant search. - MinValItr = CC; + MinValItr = I; } // Finalize the last base constant search. - findAndMakeBaseConstant(MinValItr, ConstCandVec.end()); + FindAndMakeBaseConstant(MinValItr, ConstantMap.end()); } -/// \brief Emit materialization code for all rebased constants and update their -/// users. -void ConstantHoisting::emitBaseConstants(Instruction *Base, Constant *Offset, - const ConstantUser &CU) { - Instruction *Mat = Base; - if (Offset) { - Instruction *InsertionPt = findMatInsertPt(CU.Inst, CU.OpndIdx); - Mat = BinaryOperator::Create(Instruction::Add, Base, Offset, - "const_mat", InsertionPt); - - DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0) - << " + " << *Offset << ") in BB " - << Mat->getParent()->getName() << '\n' << *Mat << '\n'); - Mat->setDebugLoc(CU.Inst->getDebugLoc()); - } - Value *Opnd = CU.Inst->getOperand(CU.OpndIdx); +/// \brief Records the basic block of the instruction or all basic blocks of the +/// users of the constant expression. +static void CollectBasicBlocks(SmallPtrSet &BBs, Function &F, + User *U) { + if (Instruction *I = dyn_cast(U)) + BBs.insert(I->getParent()); + else if (ConstantExpr *CE = dyn_cast(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(UU)) + if(I->getParent()->getParent() == &F) + BBs.insert(I->getParent()); +} - // Visit constant integer. - if (isa(Opnd)) { - DEBUG(dbgs() << "Update: " << *CU.Inst << '\n'); - CU.Inst->setOperand(CU.OpndIdx, Mat); - DEBUG(dbgs() << "To : " << *CU.Inst << '\n'); - return; +/// \brief Find the instruction we should insert the constant materialization +/// before. +static Instruction *getMatInsertPt(Instruction *I, const DominatorTree *DT) { + if (!isa(I) && !isa(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 BBs; + ConstantInfo::RebasedConstantListType::const_iterator RCI, RCE; + for (RCI = CI.RebasedConstants.begin(), RCE = CI.RebasedConstants.end(); + RCI != RCE; ++RCI) + for (SmallVectorImpl::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); +} - // Visit cast instruction. - if (auto CastInst = dyn_cast(Opnd)) { - assert(CastInst->isCast() && "Expected an cast instruction!"); - // Check if we already have visited this cast instruction before to avoid - // unnecessary cloning. - Instruction *&ClonedCastInst = ClonedCastMap[CastInst]; - if (!ClonedCastInst) { - ClonedCastInst = CastInst->clone(); - ClonedCastInst->setOperand(0, Mat); - 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'); +/// \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(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: " << *CU.Inst << '\n'); - CU.Inst->setOperand(CU.OpndIdx, ClonedCastInst); - DEBUG(dbgs() << "To : " << *CU.Inst << '\n'); + DEBUG(dbgs() << "Update: " << *I << '\n'); + I->replaceUsesOfWith(OriginalConstant, Mat); + DEBUG(dbgs() << "To: " << *I << '\n'); return; } + assert(isa(U) && "Expected a ConstantExpr."); + ConstantExpr *CE = cast(U); + SmallVector, 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(UU)) { + // Only update constant expressions in the current function. + if (I->getParent()->getParent() != &F) { + DEBUG(dbgs() << "Not in the same function - skip.\n"); + continue; + } - // Visit constant expression. - if (auto ConstExpr = dyn_cast(Opnd)) { - Instruction *ConstExprInst = ConstExpr->getAsInstruction(); - ConstExprInst->setOperand(0, Mat); - ConstExprInst->insertBefore(findMatInsertPt(CU.Inst, CU.OpndIdx)); + 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. - ConstExprInst->setDebugLoc(CU.Inst->getDebugLoc()); + // Use the same debug location as the instruction we are about to + // update. + Mat->setDebugLoc(I->getDebugLoc()); - DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n' - << "From : " << *ConstExpr << '\n'); - DEBUG(dbgs() << "Update: " << *CU.Inst << '\n'); - CU.Inst->setOperand(CU.OpndIdx, ConstExprInst); - DEBUG(dbgs() << "To : " << *CU.Inst << '\n'); - return; + 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 >::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() { +bool ConstantHoisting::EmitBaseConstants(Function &F) { bool MadeChange = false; - for (auto const &ConstInfo : ConstantVec) { + SmallVectorImpl::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(ConstInfo); - IntegerType *Ty = ConstInfo.BaseConstant->getType(); - Instruction *Base = - new BitCastInst(ConstInfo.BaseConstant, Ty, "const", IP); - DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseConstant << ") to BB " - << IP->getParent()->getName() << '\n' << *Base << '\n'); + 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. - for (auto const &RCI : ConstInfo.RebasedConstants) { + ConstantInfo::RebasedConstantListType::iterator RCI, RCE; + for (RCI = CI->RebasedConstants.begin(), RCE = CI->RebasedConstants.end(); + RCI != RCE; ++RCI) { NumConstantsRebased++; - for (auto const &U : RCI.Uses) - emitBaseConstants(Base, RCI.Offset, U); + for (SmallVectorImpl::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. @@ -554,37 +432,27 @@ bool ConstantHoisting::emitBaseConstants() { return MadeChange; } -/// \brief Check all cast instructions we made a copy of and remove them if they -/// have no more users. -void ConstantHoisting::deleteDeadCastInst() const { - for (auto const &I : ClonedCastMap) - if (I.first->use_empty()) - I.first->removeFromParent(); -} - /// \brief Optimize expensive integer constants in the given function. -bool ConstantHoisting::optimizeConstants(Function &Fn) { +bool ConstantHoisting::OptimizeConstants(Function &F) { + bool MadeChange = false; + // Collect all constant candidates. - collectConstantCandidates(Fn); + CollectConstants(F); - // There are no constant candidates to worry about. - if (ConstCandVec.empty()) - return false; + // 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(); - - // There are no constants to emit. - if (ConstantVec.empty()) - return false; + FindBaseConstants(); // Finally hoist the base constant and emit materializating code for dependent // constants. - bool MadeChange = emitBaseConstants(); + MadeChange |= EmitBaseConstants(F); - // Cleanup dead instructions. - deleteDeadCastInst(); + ConstantMap.clear(); + Constants.clear(); return MadeChange; } diff --git a/test/CodeGen/X86/lsr-interesting-step.ll b/test/CodeGen/X86/lsr-interesting-step.ll index 8ea3c53de4..d4a7ac7da1 100644 --- a/test/CodeGen/X86/lsr-interesting-step.ll +++ b/test/CodeGen/X86/lsr-interesting-step.ll @@ -3,24 +3,26 @@ ; The inner loop should require only one add (and no leas either). ; rdar://8100380 -; CHECK: BB0_2: -; CHECK-NEXT: movb $0, flags(%rcx) -; CHECK-NEXT: addq %rax, %rcx -; CHECK-NEXT: cmpq $8192, %rcx +; CHECK: BB0_3: +; CHECK-NEXT: movb $0, flags(%rdx) +; CHECK-NEXT: addq %rax, %rdx +; CHECK-NEXT: cmpq $8192, %rdx ; CHECK-NEXT: jl @flags = external global [8192 x i8], align 16 ; <[8192 x i8]*> [#uses=1] define void @foo() nounwind { entry: - br label %bb + %tmp = icmp slt i64 2, 8192 ; [#uses=1] + br i1 %tmp, label %bb, label %bb21 bb: ; preds = %entry br label %bb7 bb7: ; preds = %bb, %bb17 %tmp8 = phi i64 [ %tmp18, %bb17 ], [ 2, %bb ] ; [#uses=2] - br label %bb10 + %tmp9 = icmp slt i64 2, 8192 ; [#uses=1] + br i1 %tmp9, label %bb10, label %bb17 bb10: ; preds = %bb7 br label %bb11 diff --git a/test/CodeGen/X86/negate-add-zero.ll b/test/CodeGen/X86/negate-add-zero.ll index c961bd091b..92850f22ea 100644 --- a/test/CodeGen/X86/negate-add-zero.ll +++ b/test/CodeGen/X86/negate-add-zero.ll @@ -827,7 +827,9 @@ declare void @_ZN11MatrixTools9transposeI11FixedMatrixIdLi6ELi6ELi0ELi0EEEENT_13 declare void @_ZN21HNodeTranslateRotate311toCartesianEv(%struct.HNodeTranslateRotate3*) define linkonce void @_ZN21HNodeTranslateRotate36setVelERK9CDSVectorIdLi1EN3CDS12DefaultAllocEE(%struct.HNodeTranslateRotate3* %this, %"struct.CDSVector"* %velv) { - %1 = getelementptr double* null, i32 -1 ; [#uses=1] +entry: + %0 = add i32 0, -1 ; [#uses=1] + %1 = getelementptr double* null, i32 %0 ; [#uses=1] %2 = load double* %1, align 8 ; [#uses=1] %3 = load double* null, align 8 ; [#uses=2] %4 = load double* null, align 8 ; [#uses=2] @@ -888,12 +890,13 @@ define linkonce void @_ZN21HNodeTranslateRotate36setVelERK9CDSVectorIdLi1EN3CDS1 store double %52, double* %55, align 8 %56 = getelementptr %struct.HNodeTranslateRotate3* %this, i32 0, i32 0, i32 10, i32 0, i32 0, i32 2 ; [#uses=1] store double %53, double* %56, align 8 - %57 = getelementptr %"struct.SubVector >"* null, i32 0, i32 0 ; <%"struct.CDSVector"**> [#uses=1] - store %"struct.CDSVector"* %velv, %"struct.CDSVector"** %57, align 8 - %58 = getelementptr %"struct.SubVector >"* null, i32 0, i32 1 ; [#uses=1] - store i32 4, i32* %58, align 4 - %59 = getelementptr %"struct.SubVector >"* null, i32 0, i32 2 ; [#uses=1] - store i32 3, i32* %59, align 8 + %57 = add i32 0, 4 ; [#uses=1] + %58 = getelementptr %"struct.SubVector >"* null, i32 0, i32 0 ; <%"struct.CDSVector"**> [#uses=1] + store %"struct.CDSVector"* %velv, %"struct.CDSVector"** %58, align 8 + %59 = getelementptr %"struct.SubVector >"* null, i32 0, i32 1 ; [#uses=1] + store i32 %57, i32* %59, align 4 + %60 = getelementptr %"struct.SubVector >"* null, i32 0, i32 2 ; [#uses=1] + store i32 3, i32* %60, align 8 unreachable } diff --git a/test/Transforms/ConstantHoisting/X86/phi.ll b/test/Transforms/ConstantHoisting/X86/phi.ll index 7134723f61..cc2fdda40e 100644 --- a/test/Transforms/ConstantHoisting/X86/phi.ll +++ b/test/Transforms/ConstantHoisting/X86/phi.ll @@ -19,11 +19,11 @@ return: ret i8* %retval.0 ; CHECK-LABEL: @test1 -; CHECK: if.end: -; CHECK: %2 = inttoptr i64 %const to i8* -; CHECK-NEXT: br -; CHECK: return: -; CHECK-NEXT: %retval.0 = phi i8* [ null, %entry ], [ %2, %if.end ] +; CHECK: entry: +; CHECK: %const_mat = add i64 %const, 1 +; CHECK-NEXT: %1 = inttoptr i64 %const_mat to i8* +; CHECK-NEXT: br i1 %cmp +; CHECK: %retval.0 = phi i8* [ null, %entry ], [ %1, %if.end ] } define void @test2(i1 %cmp, i64** %tmp) { -- cgit v1.2.3