From 37ed9c199ca639565f6ce88105f9e39e898d82d0 Mon Sep 17 00:00:00 2001 From: Stephen Hines Date: Mon, 1 Dec 2014 14:51:49 -0800 Subject: Update aosp/master LLVM for rebase to r222494. Change-Id: Ic787f5e0124df789bd26f3f24680f45e678eef2d --- lib/CodeGen/CodeGenPrepare.cpp | 795 ++++++++++++++++++++++++++++++++--------- 1 file changed, 634 insertions(+), 161 deletions(-) (limited to 'lib/CodeGen/CodeGenPrepare.cpp') diff --git a/lib/CodeGen/CodeGenPrepare.cpp b/lib/CodeGen/CodeGenPrepare.cpp index ccac40c..8d20848 100644 --- a/lib/CodeGen/CodeGenPrepare.cpp +++ b/lib/CodeGen/CodeGenPrepare.cpp @@ -18,6 +18,7 @@ #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" @@ -63,6 +64,7 @@ STATISTIC(NumRetsDup, "Number of return instructions duplicated"); STATISTIC(NumDbgValueMoved, "Number of debug value instructions moved"); STATISTIC(NumSelectsExpanded, "Number of selects turned into branches"); STATISTIC(NumAndCmpsMoved, "Number of and/cmp's pushed into branches"); +STATISTIC(NumStoreExtractExposed, "Number of store(extractelement) exposed"); static cl::opt DisableBranchOpts( "disable-cgp-branch-opts", cl::Hidden, cl::init(false), @@ -80,15 +82,29 @@ static cl::opt EnableAndCmpSinking( "enable-andcmp-sinking", cl::Hidden, cl::init(true), cl::desc("Enable sinkinig and/cmp into branches.")); +static cl::opt DisableStoreExtract( + "disable-cgp-store-extract", cl::Hidden, cl::init(false), + cl::desc("Disable store(extract) optimizations in CodeGenPrepare")); + +static cl::opt StressStoreExtract( + "stress-cgp-store-extract", cl::Hidden, cl::init(false), + cl::desc("Stress test store(extract) optimizations in CodeGenPrepare")); + namespace { typedef SmallPtrSet SetOfInstrs; -typedef DenseMap InstrToOrigTy; +struct TypeIsSExt { + Type *Ty; + bool IsSExt; + TypeIsSExt(Type *Ty, bool IsSExt) : Ty(Ty), IsSExt(IsSExt) {} +}; +typedef DenseMap InstrToOrigTy; class CodeGenPrepare : public FunctionPass { /// TLI - Keep a pointer of a TargetLowering to consult for determining /// transformation profitability. const TargetMachine *TM; const TargetLowering *TLI; + const TargetTransformInfo *TTI; const TargetLibraryInfo *TLInfo; DominatorTree *DT; @@ -118,7 +134,7 @@ typedef DenseMap InstrToOrigTy; public: static char ID; // Pass identification, replacement for typeid explicit CodeGenPrepare(const TargetMachine *TM = nullptr) - : FunctionPass(ID), TM(TM), TLI(nullptr) { + : FunctionPass(ID), TM(TM), TLI(nullptr), TTI(nullptr) { initializeCodeGenPreparePass(*PassRegistry::getPassRegistry()); } bool runOnFunction(Function &F) override; @@ -128,6 +144,7 @@ typedef DenseMap InstrToOrigTy; void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addPreserved(); AU.addRequired(); + AU.addRequired(); } private: @@ -144,6 +161,7 @@ typedef DenseMap InstrToOrigTy; bool OptimizeExtUses(Instruction *I); bool OptimizeSelectInst(SelectInst *SI); bool OptimizeShuffleVectorInst(ShuffleVectorInst *SI); + bool OptimizeExtractElementInst(Instruction *Inst); bool DupRetToEnableTailCallOpts(BasicBlock *BB); bool PlaceDbgValues(Function &F); bool sinkAndCmp(Function &F); @@ -168,8 +186,10 @@ bool CodeGenPrepare::runOnFunction(Function &F) { PromotedInsts.clear(); ModifiedDT = false; - if (TM) TLI = TM->getTargetLowering(); + if (TM) + TLI = TM->getSubtargetImpl()->getTargetLowering(); TLInfo = &getAnalysis(); + TTI = &getAnalysis(); DominatorTreeWrapperPass *DTWP = getAnalysisIfAvailable(); DT = DTWP ? &DTWP->getDomTree() : nullptr; @@ -662,10 +682,13 @@ SinkShiftAndTruncate(BinaryOperator *ShiftI, Instruction *User, ConstantInt *CI, if (!ISDOpcode) continue; - // If the use is actually a legal node, there will not be an implicit - // truncate. - if (TLI.isOperationLegalOrCustom(ISDOpcode, - EVT::getEVT(TruncUser->getType()))) + // If the use is actually a legal node, there will not be an + // implicit truncate. + // FIXME: always querying the result type is just an + // approximation; some nodes' legality is determined by the + // operand or other means. There's no good way to find out though. + if (TLI.isOperationLegalOrCustom( + ISDOpcode, TLI.getValueType(TruncUser->getType(), true))) continue; // Don't bother for PHI nodes. @@ -978,7 +1001,7 @@ bool CodeGenPrepare::DupRetToEnableTailCallOpts(BasicBlock *BB) { } else { SmallPtrSet VisitedBBs; for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { - if (!VisitedBBs.insert(*PI)) + if (!VisitedBBs.insert(*PI).second) continue; BasicBlock::InstListType &InstList = (*PI)->getInstList(); @@ -1250,46 +1273,75 @@ class TypePromotionTransaction { /// \brief Build a truncate instruction. class TruncBuilder : public TypePromotionAction { + Value *Val; public: /// \brief Build a truncate instruction of \p Opnd producing a \p Ty /// result. /// trunc Opnd to Ty. TruncBuilder(Instruction *Opnd, Type *Ty) : TypePromotionAction(Opnd) { IRBuilder<> Builder(Opnd); - Inst = cast(Builder.CreateTrunc(Opnd, Ty, "promoted")); - DEBUG(dbgs() << "Do: TruncBuilder: " << *Inst << "\n"); + Val = Builder.CreateTrunc(Opnd, Ty, "promoted"); + DEBUG(dbgs() << "Do: TruncBuilder: " << *Val << "\n"); } - /// \brief Get the built instruction. - Instruction *getBuiltInstruction() { return Inst; } + /// \brief Get the built value. + Value *getBuiltValue() { return Val; } /// \brief Remove the built instruction. void undo() override { - DEBUG(dbgs() << "Undo: TruncBuilder: " << *Inst << "\n"); - Inst->eraseFromParent(); + DEBUG(dbgs() << "Undo: TruncBuilder: " << *Val << "\n"); + if (Instruction *IVal = dyn_cast(Val)) + IVal->eraseFromParent(); } }; /// \brief Build a sign extension instruction. class SExtBuilder : public TypePromotionAction { + Value *Val; public: /// \brief Build a sign extension instruction of \p Opnd producing a \p Ty /// result. /// sext Opnd to Ty. SExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty) - : TypePromotionAction(Inst) { + : TypePromotionAction(InsertPt) { + IRBuilder<> Builder(InsertPt); + Val = Builder.CreateSExt(Opnd, Ty, "promoted"); + DEBUG(dbgs() << "Do: SExtBuilder: " << *Val << "\n"); + } + + /// \brief Get the built value. + Value *getBuiltValue() { return Val; } + + /// \brief Remove the built instruction. + void undo() override { + DEBUG(dbgs() << "Undo: SExtBuilder: " << *Val << "\n"); + if (Instruction *IVal = dyn_cast(Val)) + IVal->eraseFromParent(); + } + }; + + /// \brief Build a zero extension instruction. + class ZExtBuilder : public TypePromotionAction { + Value *Val; + public: + /// \brief Build a zero extension instruction of \p Opnd producing a \p Ty + /// result. + /// zext Opnd to Ty. + ZExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty) + : TypePromotionAction(InsertPt) { IRBuilder<> Builder(InsertPt); - Inst = cast(Builder.CreateSExt(Opnd, Ty, "promoted")); - DEBUG(dbgs() << "Do: SExtBuilder: " << *Inst << "\n"); + Val = Builder.CreateZExt(Opnd, Ty, "promoted"); + DEBUG(dbgs() << "Do: ZExtBuilder: " << *Val << "\n"); } - /// \brief Get the built instruction. - Instruction *getBuiltInstruction() { return Inst; } + /// \brief Get the built value. + Value *getBuiltValue() { return Val; } /// \brief Remove the built instruction. void undo() override { - DEBUG(dbgs() << "Undo: SExtBuilder: " << *Inst << "\n"); - Inst->eraseFromParent(); + DEBUG(dbgs() << "Undo: ZExtBuilder: " << *Val << "\n"); + if (Instruction *IVal = dyn_cast(Val)) + IVal->eraseFromParent(); } }; @@ -1418,9 +1470,11 @@ public: /// Same as Value::mutateType. void mutateType(Instruction *Inst, Type *NewTy); /// Same as IRBuilder::createTrunc. - Instruction *createTrunc(Instruction *Opnd, Type *Ty); + Value *createTrunc(Instruction *Opnd, Type *Ty); /// Same as IRBuilder::createSExt. - Instruction *createSExt(Instruction *Inst, Value *Opnd, Type *Ty); + Value *createSExt(Instruction *Inst, Value *Opnd, Type *Ty); + /// Same as IRBuilder::createZExt. + Value *createZExt(Instruction *Inst, Value *Opnd, Type *Ty); /// Same as Instruction::moveBefore. void moveBefore(Instruction *Inst, Instruction *Before); /// @} @@ -1452,20 +1506,28 @@ void TypePromotionTransaction::mutateType(Instruction *Inst, Type *NewTy) { Actions.push_back(make_unique(Inst, NewTy)); } -Instruction *TypePromotionTransaction::createTrunc(Instruction *Opnd, - Type *Ty) { +Value *TypePromotionTransaction::createTrunc(Instruction *Opnd, + Type *Ty) { std::unique_ptr Ptr(new TruncBuilder(Opnd, Ty)); - Instruction *I = Ptr->getBuiltInstruction(); + Value *Val = Ptr->getBuiltValue(); Actions.push_back(std::move(Ptr)); - return I; + return Val; } -Instruction *TypePromotionTransaction::createSExt(Instruction *Inst, - Value *Opnd, Type *Ty) { +Value *TypePromotionTransaction::createSExt(Instruction *Inst, + Value *Opnd, Type *Ty) { std::unique_ptr Ptr(new SExtBuilder(Inst, Opnd, Ty)); - Instruction *I = Ptr->getBuiltInstruction(); + Value *Val = Ptr->getBuiltValue(); + Actions.push_back(std::move(Ptr)); + return Val; +} + +Value *TypePromotionTransaction::createZExt(Instruction *Inst, + Value *Opnd, Type *Ty) { + std::unique_ptr Ptr(new ZExtBuilder(Inst, Opnd, Ty)); + Value *Val = Ptr->getBuiltValue(); Actions.push_back(std::move(Ptr)); - return I; + return Val; } void TypePromotionTransaction::moveBefore(Instruction *Inst, @@ -1658,58 +1720,75 @@ static bool MightBeFoldableInst(Instruction *I) { /// \brief Hepler class to perform type promotion. class TypePromotionHelper { - /// \brief Utility function to check whether or not a sign extension of - /// \p Inst with \p ConsideredSExtType can be moved through \p Inst by either - /// using the operands of \p Inst or promoting \p Inst. + /// \brief Utility function to check whether or not a sign or zero extension + /// of \p Inst with \p ConsideredExtType can be moved through \p Inst by + /// either using the operands of \p Inst or promoting \p Inst. + /// The type of the extension is defined by \p IsSExt. /// In other words, check if: - /// sext (Ty Inst opnd1 opnd2 ... opndN) to ConsideredSExtType. + /// ext (Ty Inst opnd1 opnd2 ... opndN) to ConsideredExtType. /// #1 Promotion applies: - /// ConsideredSExtType Inst (sext opnd1 to ConsideredSExtType, ...). + /// ConsideredExtType Inst (ext opnd1 to ConsideredExtType, ...). /// #2 Operand reuses: - /// sext opnd1 to ConsideredSExtType. + /// ext opnd1 to ConsideredExtType. /// \p PromotedInsts maps the instructions to their type before promotion. - static bool canGetThrough(const Instruction *Inst, Type *ConsideredSExtType, - const InstrToOrigTy &PromotedInsts); + static bool canGetThrough(const Instruction *Inst, Type *ConsideredExtType, + const InstrToOrigTy &PromotedInsts, bool IsSExt); /// \brief Utility function to determine if \p OpIdx should be promoted when /// promoting \p Inst. - static bool shouldSExtOperand(const Instruction *Inst, int OpIdx) { + static bool shouldExtOperand(const Instruction *Inst, int OpIdx) { if (isa(Inst) && OpIdx == 0) return false; return true; } - /// \brief Utility function to promote the operand of \p SExt when this - /// operand is a promotable trunc or sext. + /// \brief Utility function to promote the operand of \p Ext when this + /// operand is a promotable trunc or sext or zext. /// \p PromotedInsts maps the instructions to their type before promotion. /// \p CreatedInsts[out] contains how many non-free instructions have been - /// created to promote the operand of SExt. + /// created to promote the operand of Ext. /// Should never be called directly. - /// \return The promoted value which is used instead of SExt. - static Value *promoteOperandForTruncAndSExt(Instruction *SExt, - TypePromotionTransaction &TPT, - InstrToOrigTy &PromotedInsts, - unsigned &CreatedInsts); + /// \return The promoted value which is used instead of Ext. + static Value *promoteOperandForTruncAndAnyExt(Instruction *Ext, + TypePromotionTransaction &TPT, + InstrToOrigTy &PromotedInsts, + unsigned &CreatedInsts); - /// \brief Utility function to promote the operand of \p SExt when this + /// \brief Utility function to promote the operand of \p Ext when this /// operand is promotable and is not a supported trunc or sext. /// \p PromotedInsts maps the instructions to their type before promotion. /// \p CreatedInsts[out] contains how many non-free instructions have been - /// created to promote the operand of SExt. + /// created to promote the operand of Ext. /// Should never be called directly. - /// \return The promoted value which is used instead of SExt. - static Value *promoteOperandForOther(Instruction *SExt, + /// \return The promoted value which is used instead of Ext. + static Value *promoteOperandForOther(Instruction *Ext, TypePromotionTransaction &TPT, InstrToOrigTy &PromotedInsts, - unsigned &CreatedInsts); + unsigned &CreatedInsts, bool IsSExt); + + /// \see promoteOperandForOther. + static Value *signExtendOperandForOther(Instruction *Ext, + TypePromotionTransaction &TPT, + InstrToOrigTy &PromotedInsts, + unsigned &CreatedInsts) { + return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInsts, true); + } + + /// \see promoteOperandForOther. + static Value *zeroExtendOperandForOther(Instruction *Ext, + TypePromotionTransaction &TPT, + InstrToOrigTy &PromotedInsts, + unsigned &CreatedInsts) { + return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInsts, false); + } public: - /// Type for the utility function that promotes the operand of SExt. - typedef Value *(*Action)(Instruction *SExt, TypePromotionTransaction &TPT, + /// Type for the utility function that promotes the operand of Ext. + typedef Value *(*Action)(Instruction *Ext, TypePromotionTransaction &TPT, InstrToOrigTy &PromotedInsts, unsigned &CreatedInsts); - /// \brief Given a sign extend instruction \p SExt, return the approriate - /// action to promote the operand of \p SExt instead of using SExt. + /// \brief Given a sign/zero extend instruction \p Ext, return the approriate + /// action to promote the operand of \p Ext instead of using Ext. /// \return NULL if no promotable action is possible with the current /// sign extension. /// \p InsertedTruncs keeps track of all the truncate instructions inserted by @@ -1717,36 +1796,42 @@ public: /// because we do not want to promote these instructions as CodeGenPrepare /// will reinsert them later. Thus creating an infinite loop: create/remove. /// \p PromotedInsts maps the instructions to their type before promotion. - static Action getAction(Instruction *SExt, const SetOfInstrs &InsertedTruncs, + static Action getAction(Instruction *Ext, const SetOfInstrs &InsertedTruncs, const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts); }; bool TypePromotionHelper::canGetThrough(const Instruction *Inst, - Type *ConsideredSExtType, - const InstrToOrigTy &PromotedInsts) { - // We can always get through sext. - if (isa(Inst)) + Type *ConsideredExtType, + const InstrToOrigTy &PromotedInsts, + bool IsSExt) { + // We can always get through zext. + if (isa(Inst)) + return true; + + // sext(sext) is ok too. + if (IsSExt && isa(Inst)) return true; // We can get through binary operator, if it is legal. In other words, the // binary operator must have a nuw or nsw flag. const BinaryOperator *BinOp = dyn_cast(Inst); if (BinOp && isa(BinOp) && - (BinOp->hasNoUnsignedWrap() || BinOp->hasNoSignedWrap())) + ((!IsSExt && BinOp->hasNoUnsignedWrap()) || + (IsSExt && BinOp->hasNoSignedWrap()))) return true; // Check if we can do the following simplification. - // sext(trunc(sext)) --> sext + // ext(trunc(opnd)) --> ext(opnd) if (!isa(Inst)) return false; Value *OpndVal = Inst->getOperand(0); - // Check if we can use this operand in the sext. - // If the type is larger than the result type of the sign extension, + // Check if we can use this operand in the extension. + // If the type is larger than the result type of the extension, // we cannot. if (OpndVal->getType()->getIntegerBitWidth() > - ConsideredSExtType->getIntegerBitWidth()) + ConsideredExtType->getIntegerBitWidth()) return false; // If the operand of the truncate is not an instruction, we will not have @@ -1757,18 +1842,19 @@ bool TypePromotionHelper::canGetThrough(const Instruction *Inst, return false; // Check if the source of the type is narrow enough. - // I.e., check that trunc just drops sign extended bits. - // #1 get the type of the operand. + // I.e., check that trunc just drops extended bits of the same kind of + // the extension. + // #1 get the type of the operand and check the kind of the extended bits. const Type *OpndType; InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd); - if (It != PromotedInsts.end()) - OpndType = It->second; - else if (isa(Opnd)) - OpndType = cast(Opnd)->getOperand(0)->getType(); + if (It != PromotedInsts.end() && It->second.IsSExt == IsSExt) + OpndType = It->second.Ty; + else if ((IsSExt && isa(Opnd)) || (!IsSExt && isa(Opnd))) + OpndType = Opnd->getOperand(0)->getType(); else return false; - // #2 check that the truncate just drop sign extended bits. + // #2 check that the truncate just drop extended bits. if (Inst->getType()->getIntegerBitWidth() >= OpndType->getIntegerBitWidth()) return true; @@ -1776,149 +1862,167 @@ bool TypePromotionHelper::canGetThrough(const Instruction *Inst, } TypePromotionHelper::Action TypePromotionHelper::getAction( - Instruction *SExt, const SetOfInstrs &InsertedTruncs, + Instruction *Ext, const SetOfInstrs &InsertedTruncs, const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts) { - Instruction *SExtOpnd = dyn_cast(SExt->getOperand(0)); - Type *SExtTy = SExt->getType(); - // If the operand of the sign extension is not an instruction, we cannot + assert((isa(Ext) || isa(Ext)) && + "Unexpected instruction type"); + Instruction *ExtOpnd = dyn_cast(Ext->getOperand(0)); + Type *ExtTy = Ext->getType(); + bool IsSExt = isa(Ext); + // If the operand of the extension is not an instruction, we cannot // get through. // If it, check we can get through. - if (!SExtOpnd || !canGetThrough(SExtOpnd, SExtTy, PromotedInsts)) + if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt)) return nullptr; // Do not promote if the operand has been added by codegenprepare. // Otherwise, it means we are undoing an optimization that is likely to be // redone, thus causing potential infinite loop. - if (isa(SExtOpnd) && InsertedTruncs.count(SExtOpnd)) + if (isa(ExtOpnd) && InsertedTruncs.count(ExtOpnd)) return nullptr; // SExt or Trunc instructions. // Return the related handler. - if (isa(SExtOpnd) || isa(SExtOpnd)) - return promoteOperandForTruncAndSExt; + if (isa(ExtOpnd) || isa(ExtOpnd) || + isa(ExtOpnd)) + return promoteOperandForTruncAndAnyExt; // Regular instruction. // Abort early if we will have to insert non-free instructions. - if (!SExtOpnd->hasOneUse() && - !TLI.isTruncateFree(SExtTy, SExtOpnd->getType())) + if (!ExtOpnd->hasOneUse() && !TLI.isTruncateFree(ExtTy, ExtOpnd->getType())) return nullptr; - return promoteOperandForOther; + return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther; } -Value *TypePromotionHelper::promoteOperandForTruncAndSExt( +Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt( llvm::Instruction *SExt, TypePromotionTransaction &TPT, InstrToOrigTy &PromotedInsts, unsigned &CreatedInsts) { // By construction, the operand of SExt is an instruction. Otherwise we cannot // get through it and this method should not be called. Instruction *SExtOpnd = cast(SExt->getOperand(0)); - // Replace sext(trunc(opnd)) or sext(sext(opnd)) - // => sext(opnd). - TPT.setOperand(SExt, 0, SExtOpnd->getOperand(0)); + Value *ExtVal = SExt; + if (isa(SExtOpnd)) { + // Replace s|zext(zext(opnd)) + // => zext(opnd). + Value *ZExt = + TPT.createZExt(SExt, SExtOpnd->getOperand(0), SExt->getType()); + TPT.replaceAllUsesWith(SExt, ZExt); + TPT.eraseInstruction(SExt); + ExtVal = ZExt; + } else { + // Replace z|sext(trunc(opnd)) or sext(sext(opnd)) + // => z|sext(opnd). + TPT.setOperand(SExt, 0, SExtOpnd->getOperand(0)); + } CreatedInsts = 0; // Remove dead code. if (SExtOpnd->use_empty()) TPT.eraseInstruction(SExtOpnd); - // Check if the sext is still needed. - if (SExt->getType() != SExt->getOperand(0)->getType()) - return SExt; + // Check if the extension is still needed. + Instruction *ExtInst = dyn_cast(ExtVal); + if (!ExtInst || ExtInst->getType() != ExtInst->getOperand(0)->getType()) + return ExtVal; - // At this point we have: sext ty opnd to ty. - // Reassign the uses of SExt to the opnd and remove SExt. - Value *NextVal = SExt->getOperand(0); - TPT.eraseInstruction(SExt, NextVal); + // At this point we have: ext ty opnd to ty. + // Reassign the uses of ExtInst to the opnd and remove ExtInst. + Value *NextVal = ExtInst->getOperand(0); + TPT.eraseInstruction(ExtInst, NextVal); return NextVal; } -Value * -TypePromotionHelper::promoteOperandForOther(Instruction *SExt, - TypePromotionTransaction &TPT, - InstrToOrigTy &PromotedInsts, - unsigned &CreatedInsts) { - // By construction, the operand of SExt is an instruction. Otherwise we cannot +Value *TypePromotionHelper::promoteOperandForOther( + Instruction *Ext, TypePromotionTransaction &TPT, + InstrToOrigTy &PromotedInsts, unsigned &CreatedInsts, bool IsSExt) { + // By construction, the operand of Ext is an instruction. Otherwise we cannot // get through it and this method should not be called. - Instruction *SExtOpnd = cast(SExt->getOperand(0)); + Instruction *ExtOpnd = cast(Ext->getOperand(0)); CreatedInsts = 0; - if (!SExtOpnd->hasOneUse()) { - // SExtOpnd will be promoted. - // All its uses, but SExt, will need to use a truncated value of the + if (!ExtOpnd->hasOneUse()) { + // ExtOpnd will be promoted. + // All its uses, but Ext, will need to use a truncated value of the // promoted version. // Create the truncate now. - Instruction *Trunc = TPT.createTrunc(SExt, SExtOpnd->getType()); - Trunc->removeFromParent(); - // Insert it just after the definition. - Trunc->insertAfter(SExtOpnd); + Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->getType()); + if (Instruction *ITrunc = dyn_cast(Trunc)) { + ITrunc->removeFromParent(); + // Insert it just after the definition. + ITrunc->insertAfter(ExtOpnd); + } - TPT.replaceAllUsesWith(SExtOpnd, Trunc); - // Restore the operand of SExt (which has been replace by the previous call + TPT.replaceAllUsesWith(ExtOpnd, Trunc); + // Restore the operand of Ext (which has been replace by the previous call // to replaceAllUsesWith) to avoid creating a cycle trunc <-> sext. - TPT.setOperand(SExt, 0, SExtOpnd); + TPT.setOperand(Ext, 0, ExtOpnd); } // Get through the Instruction: // 1. Update its type. - // 2. Replace the uses of SExt by Inst. - // 3. Sign extend each operand that needs to be sign extended. + // 2. Replace the uses of Ext by Inst. + // 3. Extend each operand that needs to be extended. // Remember the original type of the instruction before promotion. // This is useful to know that the high bits are sign extended bits. - PromotedInsts.insert( - std::pair(SExtOpnd, SExtOpnd->getType())); + PromotedInsts.insert(std::pair( + ExtOpnd, TypeIsSExt(ExtOpnd->getType(), IsSExt))); // Step #1. - TPT.mutateType(SExtOpnd, SExt->getType()); + TPT.mutateType(ExtOpnd, Ext->getType()); // Step #2. - TPT.replaceAllUsesWith(SExt, SExtOpnd); + TPT.replaceAllUsesWith(Ext, ExtOpnd); // Step #3. - Instruction *SExtForOpnd = SExt; + Instruction *ExtForOpnd = Ext; - DEBUG(dbgs() << "Propagate SExt to operands\n"); - for (int OpIdx = 0, EndOpIdx = SExtOpnd->getNumOperands(); OpIdx != EndOpIdx; + DEBUG(dbgs() << "Propagate Ext to operands\n"); + for (int OpIdx = 0, EndOpIdx = ExtOpnd->getNumOperands(); OpIdx != EndOpIdx; ++OpIdx) { - DEBUG(dbgs() << "Operand:\n" << *(SExtOpnd->getOperand(OpIdx)) << '\n'); - if (SExtOpnd->getOperand(OpIdx)->getType() == SExt->getType() || - !shouldSExtOperand(SExtOpnd, OpIdx)) { + DEBUG(dbgs() << "Operand:\n" << *(ExtOpnd->getOperand(OpIdx)) << '\n'); + if (ExtOpnd->getOperand(OpIdx)->getType() == Ext->getType() || + !shouldExtOperand(ExtOpnd, OpIdx)) { DEBUG(dbgs() << "No need to propagate\n"); continue; } - // Check if we can statically sign extend the operand. - Value *Opnd = SExtOpnd->getOperand(OpIdx); + // Check if we can statically extend the operand. + Value *Opnd = ExtOpnd->getOperand(OpIdx); if (const ConstantInt *Cst = dyn_cast(Opnd)) { - DEBUG(dbgs() << "Statically sign extend\n"); - TPT.setOperand( - SExtOpnd, OpIdx, - ConstantInt::getSigned(SExt->getType(), Cst->getSExtValue())); + DEBUG(dbgs() << "Statically extend\n"); + unsigned BitWidth = Ext->getType()->getIntegerBitWidth(); + APInt CstVal = IsSExt ? Cst->getValue().sext(BitWidth) + : Cst->getValue().zext(BitWidth); + TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(Ext->getType(), CstVal)); continue; } // UndefValue are typed, so we have to statically sign extend them. if (isa(Opnd)) { - DEBUG(dbgs() << "Statically sign extend\n"); - TPT.setOperand(SExtOpnd, OpIdx, UndefValue::get(SExt->getType())); + DEBUG(dbgs() << "Statically extend\n"); + TPT.setOperand(ExtOpnd, OpIdx, UndefValue::get(Ext->getType())); continue; } // Otherwise we have to explicity sign extend the operand. - // Check if SExt was reused to sign extend an operand. - if (!SExtForOpnd) { + // Check if Ext was reused to extend an operand. + if (!ExtForOpnd) { // If yes, create a new one. - DEBUG(dbgs() << "More operands to sext\n"); - SExtForOpnd = TPT.createSExt(SExt, Opnd, SExt->getType()); + DEBUG(dbgs() << "More operands to ext\n"); + ExtForOpnd = + cast(IsSExt ? TPT.createSExt(Ext, Opnd, Ext->getType()) + : TPT.createZExt(Ext, Opnd, Ext->getType())); ++CreatedInsts; } - TPT.setOperand(SExtForOpnd, 0, Opnd); + TPT.setOperand(ExtForOpnd, 0, Opnd); // Move the sign extension before the insertion point. - TPT.moveBefore(SExtForOpnd, SExtOpnd); - TPT.setOperand(SExtOpnd, OpIdx, SExtForOpnd); + TPT.moveBefore(ExtForOpnd, ExtOpnd); + TPT.setOperand(ExtOpnd, OpIdx, ExtForOpnd); // If more sext are required, new instructions will have to be created. - SExtForOpnd = nullptr; + ExtForOpnd = nullptr; } - if (SExtForOpnd == SExt) { - DEBUG(dbgs() << "Sign extension is useless now\n"); - TPT.eraseInstruction(SExt); + if (ExtForOpnd == Ext) { + DEBUG(dbgs() << "Extension is useless now\n"); + TPT.eraseInstruction(Ext); } - return SExtOpnd; + return ExtOpnd; } /// IsPromotionProfitable - Check whether or not promoting an instruction @@ -1951,8 +2055,8 @@ AddressingModeMatcher::IsPromotionProfitable(unsigned MatchedSize, if (!ISDOpcode) return true; // Otherwise, check if the promoted instruction is legal or not. - return TLI.isOperationLegalOrCustom(ISDOpcode, - EVT::getEVT(PromotedInst->getType())); + return TLI.isOperationLegalOrCustom( + ISDOpcode, TLI.getValueType(PromotedInst->getType())); } /// MatchOperationAddr - Given an instruction or constant expr, see if we can @@ -2036,7 +2140,8 @@ bool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode, case Instruction::Shl: { // Can only handle X*C and X << C. ConstantInt *RHS = dyn_cast(AddrInst->getOperand(1)); - if (!RHS) return false; + if (!RHS) + return false; int64_t Scale = RHS->getSExtValue(); if (Opcode == Instruction::Shl) Scale = 1LL << Scale; @@ -2129,28 +2234,32 @@ bool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode, return true; } - case Instruction::SExt: { - // Try to move this sext out of the way of the addressing mode. - Instruction *SExt = cast(AddrInst); + case Instruction::SExt: + case Instruction::ZExt: { + Instruction *Ext = dyn_cast(AddrInst); + if (!Ext) + return false; + + // Try to move this ext out of the way of the addressing mode. // Ask for a method for doing so. - TypePromotionHelper::Action TPH = TypePromotionHelper::getAction( - SExt, InsertedTruncs, TLI, PromotedInsts); + TypePromotionHelper::Action TPH = + TypePromotionHelper::getAction(Ext, InsertedTruncs, TLI, PromotedInsts); if (!TPH) return false; TypePromotionTransaction::ConstRestorationPt LastKnownGood = TPT.getRestorationPoint(); unsigned CreatedInsts = 0; - Value *PromotedOperand = TPH(SExt, TPT, PromotedInsts, CreatedInsts); + Value *PromotedOperand = TPH(Ext, TPT, PromotedInsts, CreatedInsts); // SExt has been moved away. // Thus either it will be rematched later in the recursive calls or it is // gone. Anyway, we must not fold it into the addressing mode at this point. // E.g., // op = add opnd, 1 - // idx = sext op + // idx = ext op // addr = gep base, idx // is now: - // promotedOpnd = sext opnd <- no match here + // promotedOpnd = ext opnd <- no match here // op = promoted_add promotedOpnd, 1 <- match (later in recursive calls) // addr = gep base, op <- match if (MovedAway) @@ -2289,10 +2398,10 @@ static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal, /// Add the ultimately found memory instructions to MemoryUses. static bool FindAllMemoryUses(Instruction *I, SmallVectorImpl > &MemoryUses, - SmallPtrSet &ConsideredInsts, + SmallPtrSetImpl &ConsideredInsts, const TargetLowering &TLI) { // If we already considered this instruction, we're done. - if (!ConsideredInsts.insert(I)) + if (!ConsideredInsts.insert(I).second) return false; // If this is an obviously unfoldable instruction, bail out. @@ -2506,7 +2615,7 @@ bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, worklist.pop_back(); // Break use-def graph loops. - if (!Visited.insert(V)) { + if (!Visited.insert(V).second) { Consensus = nullptr; break; } @@ -2696,8 +2805,8 @@ bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, if (AddrMode.BaseOffs) { Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); if (ResultIndex) { - // We need to add this separately from the scale above to help with - // SDAG consecutive load/store merging. + // We need to add this separately from the scale above to help with + // SDAG consecutive load/store merging. if (ResultPtr->getType() != I8PtrTy) ResultPtr = Builder.CreateBitCast(ResultPtr, I8PtrTy); ResultPtr = Builder.CreateGEP(ResultPtr, ResultIndex, "sunkaddr"); @@ -3105,6 +3214,367 @@ bool CodeGenPrepare::OptimizeShuffleVectorInst(ShuffleVectorInst *SVI) { return MadeChange; } +namespace { +/// \brief Helper class to promote a scalar operation to a vector one. +/// This class is used to move downward extractelement transition. +/// E.g., +/// a = vector_op <2 x i32> +/// b = extractelement <2 x i32> a, i32 0 +/// c = scalar_op b +/// store c +/// +/// => +/// a = vector_op <2 x i32> +/// c = vector_op a (equivalent to scalar_op on the related lane) +/// * d = extractelement <2 x i32> c, i32 0 +/// * store d +/// Assuming both extractelement and store can be combine, we get rid of the +/// transition. +class VectorPromoteHelper { + /// Used to perform some checks on the legality of vector operations. + const TargetLowering &TLI; + + /// Used to estimated the cost of the promoted chain. + const TargetTransformInfo &TTI; + + /// The transition being moved downwards. + Instruction *Transition; + /// The sequence of instructions to be promoted. + SmallVector InstsToBePromoted; + /// Cost of combining a store and an extract. + unsigned StoreExtractCombineCost; + /// Instruction that will be combined with the transition. + Instruction *CombineInst; + + /// \brief The instruction that represents the current end of the transition. + /// Since we are faking the promotion until we reach the end of the chain + /// of computation, we need a way to get the current end of the transition. + Instruction *getEndOfTransition() const { + if (InstsToBePromoted.empty()) + return Transition; + return InstsToBePromoted.back(); + } + + /// \brief Return the index of the original value in the transition. + /// E.g., for "extractelement <2 x i32> c, i32 1" the original value, + /// c, is at index 0. + unsigned getTransitionOriginalValueIdx() const { + assert(isa(Transition) && + "Other kind of transitions are not supported yet"); + return 0; + } + + /// \brief Return the index of the index in the transition. + /// E.g., for "extractelement <2 x i32> c, i32 0" the index + /// is at index 1. + unsigned getTransitionIdx() const { + assert(isa(Transition) && + "Other kind of transitions are not supported yet"); + return 1; + } + + /// \brief Get the type of the transition. + /// This is the type of the original value. + /// E.g., for "extractelement <2 x i32> c, i32 1" the type of the + /// transition is <2 x i32>. + Type *getTransitionType() const { + return Transition->getOperand(getTransitionOriginalValueIdx())->getType(); + } + + /// \brief Promote \p ToBePromoted by moving \p Def downward through. + /// I.e., we have the following sequence: + /// Def = Transition a to + /// b = ToBePromoted Def, ... + /// => + /// b = ToBePromoted a, ... + /// Def = Transition ToBePromoted to + void promoteImpl(Instruction *ToBePromoted); + + /// \brief Check whether or not it is profitable to promote all the + /// instructions enqueued to be promoted. + bool isProfitableToPromote() { + Value *ValIdx = Transition->getOperand(getTransitionOriginalValueIdx()); + unsigned Index = isa(ValIdx) + ? cast(ValIdx)->getZExtValue() + : -1; + Type *PromotedType = getTransitionType(); + + StoreInst *ST = cast(CombineInst); + unsigned AS = ST->getPointerAddressSpace(); + unsigned Align = ST->getAlignment(); + // Check if this store is supported. + if (!TLI.allowsMisalignedMemoryAccesses( + TLI.getValueType(ST->getValueOperand()->getType()), AS, Align)) { + // If this is not supported, there is no way we can combine + // the extract with the store. + return false; + } + + // The scalar chain of computation has to pay for the transition + // scalar to vector. + // The vector chain has to account for the combining cost. + uint64_t ScalarCost = + TTI.getVectorInstrCost(Transition->getOpcode(), PromotedType, Index); + uint64_t VectorCost = StoreExtractCombineCost; + for (const auto &Inst : InstsToBePromoted) { + // Compute the cost. + // By construction, all instructions being promoted are arithmetic ones. + // Moreover, one argument is a constant that can be viewed as a splat + // constant. + Value *Arg0 = Inst->getOperand(0); + bool IsArg0Constant = isa(Arg0) || isa(Arg0) || + isa(Arg0); + TargetTransformInfo::OperandValueKind Arg0OVK = + IsArg0Constant ? TargetTransformInfo::OK_UniformConstantValue + : TargetTransformInfo::OK_AnyValue; + TargetTransformInfo::OperandValueKind Arg1OVK = + !IsArg0Constant ? TargetTransformInfo::OK_UniformConstantValue + : TargetTransformInfo::OK_AnyValue; + ScalarCost += TTI.getArithmeticInstrCost( + Inst->getOpcode(), Inst->getType(), Arg0OVK, Arg1OVK); + VectorCost += TTI.getArithmeticInstrCost(Inst->getOpcode(), PromotedType, + Arg0OVK, Arg1OVK); + } + DEBUG(dbgs() << "Estimated cost of computation to be promoted:\nScalar: " + << ScalarCost << "\nVector: " << VectorCost << '\n'); + return ScalarCost > VectorCost; + } + + /// \brief Generate a constant vector with \p Val with the same + /// number of elements as the transition. + /// \p UseSplat defines whether or not \p Val should be replicated + /// accross the whole vector. + /// In other words, if UseSplat == true, we generate , + /// otherwise we generate a vector with as many undef as possible: + /// where \p Val is only + /// used at the index of the extract. + Value *getConstantVector(Constant *Val, bool UseSplat) const { + unsigned ExtractIdx = UINT_MAX; + if (!UseSplat) { + // If we cannot determine where the constant must be, we have to + // use a splat constant. + Value *ValExtractIdx = Transition->getOperand(getTransitionIdx()); + if (ConstantInt *CstVal = dyn_cast(ValExtractIdx)) + ExtractIdx = CstVal->getSExtValue(); + else + UseSplat = true; + } + + unsigned End = getTransitionType()->getVectorNumElements(); + if (UseSplat) + return ConstantVector::getSplat(End, Val); + + SmallVector ConstVec; + UndefValue *UndefVal = UndefValue::get(Val->getType()); + for (unsigned Idx = 0; Idx != End; ++Idx) { + if (Idx == ExtractIdx) + ConstVec.push_back(Val); + else + ConstVec.push_back(UndefVal); + } + return ConstantVector::get(ConstVec); + } + + /// \brief Check if promoting to a vector type an operand at \p OperandIdx + /// in \p Use can trigger undefined behavior. + static bool canCauseUndefinedBehavior(const Instruction *Use, + unsigned OperandIdx) { + // This is not safe to introduce undef when the operand is on + // the right hand side of a division-like instruction. + if (OperandIdx != 1) + return false; + switch (Use->getOpcode()) { + default: + return false; + case Instruction::SDiv: + case Instruction::UDiv: + case Instruction::SRem: + case Instruction::URem: + return true; + case Instruction::FDiv: + case Instruction::FRem: + return !Use->hasNoNaNs(); + } + llvm_unreachable(nullptr); + } + +public: + VectorPromoteHelper(const TargetLowering &TLI, const TargetTransformInfo &TTI, + Instruction *Transition, unsigned CombineCost) + : TLI(TLI), TTI(TTI), Transition(Transition), + StoreExtractCombineCost(CombineCost), CombineInst(nullptr) { + assert(Transition && "Do not know how to promote null"); + } + + /// \brief Check if we can promote \p ToBePromoted to \p Type. + bool canPromote(const Instruction *ToBePromoted) const { + // We could support CastInst too. + return isa(ToBePromoted); + } + + /// \brief Check if it is profitable to promote \p ToBePromoted + /// by moving downward the transition through. + bool shouldPromote(const Instruction *ToBePromoted) const { + // Promote only if all the operands can be statically expanded. + // Indeed, we do not want to introduce any new kind of transitions. + for (const Use &U : ToBePromoted->operands()) { + const Value *Val = U.get(); + if (Val == getEndOfTransition()) { + // If the use is a division and the transition is on the rhs, + // we cannot promote the operation, otherwise we may create a + // division by zero. + if (canCauseUndefinedBehavior(ToBePromoted, U.getOperandNo())) + return false; + continue; + } + if (!isa(Val) && !isa(Val) && + !isa(Val)) + return false; + } + // Check that the resulting operation is legal. + int ISDOpcode = TLI.InstructionOpcodeToISD(ToBePromoted->getOpcode()); + if (!ISDOpcode) + return false; + return StressStoreExtract || + TLI.isOperationLegalOrCustom( + ISDOpcode, TLI.getValueType(getTransitionType(), true)); + } + + /// \brief Check whether or not \p Use can be combined + /// with the transition. + /// I.e., is it possible to do Use(Transition) => AnotherUse? + bool canCombine(const Instruction *Use) { return isa(Use); } + + /// \brief Record \p ToBePromoted as part of the chain to be promoted. + void enqueueForPromotion(Instruction *ToBePromoted) { + InstsToBePromoted.push_back(ToBePromoted); + } + + /// \brief Set the instruction that will be combined with the transition. + void recordCombineInstruction(Instruction *ToBeCombined) { + assert(canCombine(ToBeCombined) && "Unsupported instruction to combine"); + CombineInst = ToBeCombined; + } + + /// \brief Promote all the instructions enqueued for promotion if it is + /// is profitable. + /// \return True if the promotion happened, false otherwise. + bool promote() { + // Check if there is something to promote. + // Right now, if we do not have anything to combine with, + // we assume the promotion is not profitable. + if (InstsToBePromoted.empty() || !CombineInst) + return false; + + // Check cost. + if (!StressStoreExtract && !isProfitableToPromote()) + return false; + + // Promote. + for (auto &ToBePromoted : InstsToBePromoted) + promoteImpl(ToBePromoted); + InstsToBePromoted.clear(); + return true; + } +}; +} // End of anonymous namespace. + +void VectorPromoteHelper::promoteImpl(Instruction *ToBePromoted) { + // At this point, we know that all the operands of ToBePromoted but Def + // can be statically promoted. + // For Def, we need to use its parameter in ToBePromoted: + // b = ToBePromoted ty1 a + // Def = Transition ty1 b to ty2 + // Move the transition down. + // 1. Replace all uses of the promoted operation by the transition. + // = ... b => = ... Def. + assert(ToBePromoted->getType() == Transition->getType() && + "The type of the result of the transition does not match " + "the final type"); + ToBePromoted->replaceAllUsesWith(Transition); + // 2. Update the type of the uses. + // b = ToBePromoted ty2 Def => b = ToBePromoted ty1 Def. + Type *TransitionTy = getTransitionType(); + ToBePromoted->mutateType(TransitionTy); + // 3. Update all the operands of the promoted operation with promoted + // operands. + // b = ToBePromoted ty1 Def => b = ToBePromoted ty1 a. + for (Use &U : ToBePromoted->operands()) { + Value *Val = U.get(); + Value *NewVal = nullptr; + if (Val == Transition) + NewVal = Transition->getOperand(getTransitionOriginalValueIdx()); + else if (isa(Val) || isa(Val) || + isa(Val)) { + // Use a splat constant if it is not safe to use undef. + NewVal = getConstantVector( + cast(Val), + isa(Val) || + canCauseUndefinedBehavior(ToBePromoted, U.getOperandNo())); + } else + assert(0 && "Did you modified shouldPromote and forgot to update this?"); + ToBePromoted->setOperand(U.getOperandNo(), NewVal); + } + Transition->removeFromParent(); + Transition->insertAfter(ToBePromoted); + Transition->setOperand(getTransitionOriginalValueIdx(), ToBePromoted); +} + +/// Some targets can do store(extractelement) with one instruction. +/// Try to push the extractelement towards the stores when the target +/// has this feature and this is profitable. +bool CodeGenPrepare::OptimizeExtractElementInst(Instruction *Inst) { + unsigned CombineCost = UINT_MAX; + if (DisableStoreExtract || !TLI || + (!StressStoreExtract && + !TLI->canCombineStoreAndExtract(Inst->getOperand(0)->getType(), + Inst->getOperand(1), CombineCost))) + return false; + + // At this point we know that Inst is a vector to scalar transition. + // Try to move it down the def-use chain, until: + // - We can combine the transition with its single use + // => we got rid of the transition. + // - We escape the current basic block + // => we would need to check that we are moving it at a cheaper place and + // we do not do that for now. + BasicBlock *Parent = Inst->getParent(); + DEBUG(dbgs() << "Found an interesting transition: " << *Inst << '\n'); + VectorPromoteHelper VPH(*TLI, *TTI, Inst, CombineCost); + // If the transition has more than one use, assume this is not going to be + // beneficial. + while (Inst->hasOneUse()) { + Instruction *ToBePromoted = cast(*Inst->user_begin()); + DEBUG(dbgs() << "Use: " << *ToBePromoted << '\n'); + + if (ToBePromoted->getParent() != Parent) { + DEBUG(dbgs() << "Instruction to promote is in a different block (" + << ToBePromoted->getParent()->getName() + << ") than the transition (" << Parent->getName() << ").\n"); + return false; + } + + if (VPH.canCombine(ToBePromoted)) { + DEBUG(dbgs() << "Assume " << *Inst << '\n' + << "will be combined with: " << *ToBePromoted << '\n'); + VPH.recordCombineInstruction(ToBePromoted); + bool Changed = VPH.promote(); + NumStoreExtractExposed += Changed; + return Changed; + } + + DEBUG(dbgs() << "Try promoting.\n"); + if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted)) + return false; + + DEBUG(dbgs() << "Promoting is possible... Enqueue for promotion!\n"); + + VPH.enqueueForPromotion(ToBePromoted); + Inst = ToBePromoted; + } + return false; +} + bool CodeGenPrepare::OptimizeInst(Instruction *I) { if (PHINode *P = dyn_cast(I)) { // It is possible for very late stage optimizations (such as SimplifyCFG) @@ -3199,6 +3669,9 @@ bool CodeGenPrepare::OptimizeInst(Instruction *I) { if (ShuffleVectorInst *SVI = dyn_cast(I)) return OptimizeShuffleVectorInst(SVI); + if (isa(I)) + return OptimizeExtractElementInst(I); + return false; } -- cgit v1.1