diff options
Diffstat (limited to 'llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp')
| -rw-r--r-- | llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp | 662 |
1 files changed, 465 insertions, 197 deletions
diff --git a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 654f0d2a03a8..9959e408e2e2 100644 --- a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -78,6 +78,7 @@ #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/BinaryFormat/Dwarf.h" #include "llvm/Config/llvm-config.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Constant.h" @@ -91,9 +92,7 @@ #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" -#include "llvm/IR/Intrinsics.h" #include "llvm/IR/Module.h" -#include "llvm/IR/OperandTraits.h" #include "llvm/IR/Operator.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/Type.h" @@ -114,12 +113,12 @@ #include "llvm/Transforms/Utils.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/LoopUtils.h" #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" #include <algorithm> #include <cassert> #include <cstddef> #include <cstdint> -#include <cstdlib> #include <iterator> #include <limits> #include <map> @@ -142,10 +141,7 @@ static const unsigned MaxIVUsers = 200; /// the salvaging is not too expensive for the compiler. static const unsigned MaxSCEVSalvageExpressionSize = 64; -// Temporary flag to cleanup congruent phis after LSR phi expansion. -// It's currently disabled until we can determine whether it's truly useful or -// not. The flag should be removed after the v3.0 release. -// This is now needed for ivchains. +// Cleanup congruent phis after LSR phi expansion. static cl::opt<bool> EnablePhiElim( "enable-lsr-phielim", cl::Hidden, cl::init(true), cl::desc("Enable LSR phi elimination")); @@ -481,6 +477,12 @@ void Formula::initialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE) { canonicalize(*L); } +static bool containsAddRecDependentOnLoop(const SCEV *S, const Loop &L) { + return SCEVExprContains(S, [&L](const SCEV *S) { + return isa<SCEVAddRecExpr>(S) && (cast<SCEVAddRecExpr>(S)->getLoop() == &L); + }); +} + /// Check whether or not this formula satisfies the canonical /// representation. /// \see Formula::BaseRegs. @@ -494,18 +496,15 @@ bool Formula::isCanonical(const Loop &L) const { if (Scale == 1 && BaseRegs.empty()) return false; - const SCEVAddRecExpr *SAR = dyn_cast<const SCEVAddRecExpr>(ScaledReg); - if (SAR && SAR->getLoop() == &L) + if (containsAddRecDependentOnLoop(ScaledReg, L)) return true; // If ScaledReg is not a recurrent expr, or it is but its loop is not current // loop, meanwhile BaseRegs contains a recurrent expr reg related with current // loop, we want to swap the reg in BaseRegs with ScaledReg. - auto I = find_if(BaseRegs, [&](const SCEV *S) { - return isa<const SCEVAddRecExpr>(S) && - (cast<SCEVAddRecExpr>(S)->getLoop() == &L); + return none_of(BaseRegs, [&L](const SCEV *S) { + return containsAddRecDependentOnLoop(S, L); }); - return I == BaseRegs.end(); } /// Helper method to morph a formula into its canonical representation. @@ -537,11 +536,9 @@ void Formula::canonicalize(const Loop &L) { // If ScaledReg is an invariant with respect to L, find the reg from // BaseRegs containing the recurrent expr related with Loop L. Swap the // reg with ScaledReg. - const SCEVAddRecExpr *SAR = dyn_cast<const SCEVAddRecExpr>(ScaledReg); - if (!SAR || SAR->getLoop() != &L) { - auto I = find_if(BaseRegs, [&](const SCEV *S) { - return isa<const SCEVAddRecExpr>(S) && - (cast<SCEVAddRecExpr>(S)->getLoop() == &L); + if (!containsAddRecDependentOnLoop(ScaledReg, L)) { + auto I = find_if(BaseRegs, [&L](const SCEV *S) { + return containsAddRecDependentOnLoop(S, L); }); if (I != BaseRegs.end()) std::swap(ScaledReg, *I); @@ -1070,7 +1067,7 @@ public: C.ScaleCost = 0; } - bool isLess(Cost &Other); + bool isLess(const Cost &Other); void Lose(); @@ -1358,6 +1355,8 @@ void Cost::RateFormula(const Formula &F, const DenseSet<const SCEV *> &VisitedRegs, const LSRUse &LU, SmallPtrSetImpl<const SCEV *> *LoserRegs) { + if (isLoser()) + return; assert(F.isCanonical(*L) && "Cost is accurate only for canonical formula"); // Tally up the registers. unsigned PrevAddRecCost = C.AddRecCost; @@ -1467,7 +1466,7 @@ void Cost::Lose() { } /// Choose the lower cost. -bool Cost::isLess(Cost &Other) { +bool Cost::isLess(const Cost &Other) { if (InsnsCost.getNumOccurrences() > 0 && InsnsCost && C.Insns != Other.C.Insns) return C.Insns < Other.C.Insns; @@ -4081,23 +4080,24 @@ void LSRInstance::GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base) { continue; // Divide out the factor, ignoring high bits, since we'll be // scaling the value back up in the end. - if (const SCEV *Quotient = getExactSDiv(AR, FactorS, SE, true)) { - // TODO: This could be optimized to avoid all the copying. - Formula F = Base; - F.ScaledReg = Quotient; - F.deleteBaseReg(F.BaseRegs[i]); - // The canonical representation of 1*reg is reg, which is already in - // Base. In that case, do not try to insert the formula, it will be - // rejected anyway. - if (F.Scale == 1 && (F.BaseRegs.empty() || - (AR->getLoop() != L && LU.AllFixupsOutsideLoop))) - continue; - // If AllFixupsOutsideLoop is true and F.Scale is 1, we may generate - // non canonical Formula with ScaledReg's loop not being L. - if (F.Scale == 1 && LU.AllFixupsOutsideLoop) - F.canonicalize(*L); - (void)InsertFormula(LU, LUIdx, F); - } + if (const SCEV *Quotient = getExactSDiv(AR, FactorS, SE, true)) + if (!Quotient->isZero()) { + // TODO: This could be optimized to avoid all the copying. + Formula F = Base; + F.ScaledReg = Quotient; + F.deleteBaseReg(F.BaseRegs[i]); + // The canonical representation of 1*reg is reg, which is already in + // Base. In that case, do not try to insert the formula, it will be + // rejected anyway. + if (F.Scale == 1 && (F.BaseRegs.empty() || + (AR->getLoop() != L && LU.AllFixupsOutsideLoop))) + continue; + // If AllFixupsOutsideLoop is true and F.Scale is 1, we may generate + // non canonical Formula with ScaledReg's loop not being L. + if (F.Scale == 1 && LU.AllFixupsOutsideLoop) + F.canonicalize(*L); + (void)InsertFormula(LU, LUIdx, F); + } } } } @@ -5601,6 +5601,27 @@ void LSRInstance::Rewrite(const LSRUse &LU, const LSRFixup &LF, DeadInsts.emplace_back(OperandIsInstr); } +// Check if there are any loop exit values which are only used once within the +// loop which may potentially be optimized with a call to rewriteLoopExitValue. +static bool LoopExitValHasSingleUse(Loop *L) { + BasicBlock *ExitBB = L->getExitBlock(); + if (!ExitBB) + return false; + + for (PHINode &ExitPhi : ExitBB->phis()) { + if (ExitPhi.getNumIncomingValues() != 1) + break; + + BasicBlock *Pred = ExitPhi.getIncomingBlock(0); + Value *IVNext = ExitPhi.getIncomingValueForBlock(Pred); + // One use would be the exit phi node, and there should be only one other + // use for this to be considered. + if (IVNext->getNumUses() == 2) + return true; + } + return false; +} + /// Rewrite all the fixup locations with new values, following the chosen /// solution. void LSRInstance::ImplementSolution( @@ -5894,40 +5915,57 @@ void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const { } namespace { + +/// Enables more convenient iteration over a DWARF expression vector. +static iterator_range<llvm::DIExpression::expr_op_iterator> +ToDwarfOpIter(SmallVectorImpl<uint64_t> &Expr) { + llvm::DIExpression::expr_op_iterator Begin = + llvm::DIExpression::expr_op_iterator(Expr.begin()); + llvm::DIExpression::expr_op_iterator End = + llvm::DIExpression::expr_op_iterator(Expr.end()); + return {Begin, End}; +} + struct SCEVDbgValueBuilder { SCEVDbgValueBuilder() = default; - SCEVDbgValueBuilder(const SCEVDbgValueBuilder &Base) { - Values = Base.Values; + SCEVDbgValueBuilder(const SCEVDbgValueBuilder &Base) { clone(Base); } + + void clone(const SCEVDbgValueBuilder &Base) { + LocationOps = Base.LocationOps; Expr = Base.Expr; } + void clear() { + LocationOps.clear(); + Expr.clear(); + } + /// The DIExpression as we translate the SCEV. SmallVector<uint64_t, 6> Expr; /// The location ops of the DIExpression. - SmallVector<llvm::ValueAsMetadata *, 2> Values; + SmallVector<Value *, 2> LocationOps; void pushOperator(uint64_t Op) { Expr.push_back(Op); } void pushUInt(uint64_t Operand) { Expr.push_back(Operand); } /// Add a DW_OP_LLVM_arg to the expression, followed by the index of the value /// in the set of values referenced by the expression. - void pushValue(llvm::Value *V) { + void pushLocation(llvm::Value *V) { Expr.push_back(llvm::dwarf::DW_OP_LLVM_arg); - auto *It = - std::find(Values.begin(), Values.end(), llvm::ValueAsMetadata::get(V)); + auto *It = std::find(LocationOps.begin(), LocationOps.end(), V); unsigned ArgIndex = 0; - if (It != Values.end()) { - ArgIndex = std::distance(Values.begin(), It); + if (It != LocationOps.end()) { + ArgIndex = std::distance(LocationOps.begin(), It); } else { - ArgIndex = Values.size(); - Values.push_back(llvm::ValueAsMetadata::get(V)); + ArgIndex = LocationOps.size(); + LocationOps.push_back(V); } Expr.push_back(ArgIndex); } void pushValue(const SCEVUnknown *U) { llvm::Value *V = cast<SCEVUnknown>(U)->getValue(); - pushValue(V); + pushLocation(V); } bool pushConst(const SCEVConstant *C) { @@ -5938,6 +5976,12 @@ struct SCEVDbgValueBuilder { return true; } + // Iterating the expression as DWARF ops is convenient when updating + // DWARF_OP_LLVM_args. + iterator_range<llvm::DIExpression::expr_op_iterator> expr_ops() { + return ToDwarfOpIter(Expr); + } + /// Several SCEV types are sequences of the same arithmetic operator applied /// to constants and values that may be extended or truncated. bool pushArithmeticExpr(const llvm::SCEVCommutativeExpr *CommExpr, @@ -5979,7 +6023,7 @@ struct SCEVDbgValueBuilder { } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { if (!U->getValue()) return false; - pushValue(U->getValue()); + pushLocation(U->getValue()); } else if (const SCEVMulExpr *MulRec = dyn_cast<SCEVMulExpr>(S)) { Success &= pushArithmeticExpr(MulRec, llvm::dwarf::DW_OP_mul); @@ -6010,52 +6054,6 @@ struct SCEVDbgValueBuilder { return Success; } - void setFinalExpression(llvm::DbgValueInst &DI, const DIExpression *OldExpr) { - // Re-state assumption that this dbg.value is not variadic. Any remaining - // opcodes in its expression operate on a single value already on the - // expression stack. Prepend our operations, which will re-compute and - // place that value on the expression stack. - assert(!DI.hasArgList()); - auto *NewExpr = - DIExpression::prependOpcodes(OldExpr, Expr, /*StackValue*/ true); - DI.setExpression(NewExpr); - - auto ValArrayRef = llvm::ArrayRef<llvm::ValueAsMetadata *>(Values); - DI.setRawLocation(llvm::DIArgList::get(DI.getContext(), ValArrayRef)); - } - - /// If a DVI can be emitted without a DIArgList, omit DW_OP_llvm_arg and the - /// location op index 0. - void setShortFinalExpression(llvm::DbgValueInst &DI, - const DIExpression *OldExpr) { - assert((Expr[0] == llvm::dwarf::DW_OP_LLVM_arg && Expr[1] == 0) && - "Expected DW_OP_llvm_arg and 0."); - DI.replaceVariableLocationOp( - 0u, llvm::MetadataAsValue::get(DI.getContext(), Values[0])); - - // See setFinalExpression: prepend our opcodes on the start of any old - // expression opcodes. - assert(!DI.hasArgList()); - llvm::SmallVector<uint64_t, 6> FinalExpr(llvm::drop_begin(Expr, 2)); - auto *NewExpr = - DIExpression::prependOpcodes(OldExpr, FinalExpr, /*StackValue*/ true); - DI.setExpression(NewExpr); - } - - /// Once the IV and variable SCEV translation is complete, write it to the - /// source DVI. - void applyExprToDbgValue(llvm::DbgValueInst &DI, - const DIExpression *OldExpr) { - assert(!Expr.empty() && "Unexpected empty expression."); - // Emit a simpler form if only a single location is referenced. - if (Values.size() == 1 && Expr[0] == llvm::dwarf::DW_OP_LLVM_arg && - Expr[1] == 0) { - setShortFinalExpression(DI, OldExpr); - } else { - setFinalExpression(DI, OldExpr); - } - } - /// Return true if the combination of arithmetic operator and underlying /// SCEV constant value is an identity function. bool isIdentityFunction(uint64_t Op, const SCEV *S) { @@ -6104,6 +6102,48 @@ struct SCEVDbgValueBuilder { return true; } + /// Create an expression that is an offset from a value (usually the IV). + void createOffsetExpr(int64_t Offset, Value *OffsetValue) { + pushLocation(OffsetValue); + DIExpression::appendOffset(Expr, Offset); + LLVM_DEBUG( + dbgs() << "scev-salvage: Generated IV offset expression. Offset: " + << std::to_string(Offset) << "\n"); + } + + /// Combine a translation of the SCEV and the IV to create an expression that + /// recovers a location's value. + /// returns true if an expression was created. + bool createIterCountExpr(const SCEV *S, + const SCEVDbgValueBuilder &IterationCount, + ScalarEvolution &SE) { + // SCEVs for SSA values are most frquently of the form + // {start,+,stride}, but sometimes they are ({start,+,stride} + %a + ..). + // This is because %a is a PHI node that is not the IV. However, these + // SCEVs have not been observed to result in debuginfo-lossy optimisations, + // so its not expected this point will be reached. + if (!isa<SCEVAddRecExpr>(S)) + return false; + + LLVM_DEBUG(dbgs() << "scev-salvage: Location to salvage SCEV: " << *S + << '\n'); + + const auto *Rec = cast<SCEVAddRecExpr>(S); + if (!Rec->isAffine()) + return false; + + if (S->getExpressionSize() > MaxSCEVSalvageExpressionSize) + return false; + + // Initialise a new builder with the iteration count expression. In + // combination with the value's SCEV this enables recovery. + clone(IterationCount); + if (!SCEVToValueExpr(*Rec, SE)) + return false; + + return true; + } + /// Convert a SCEV of a value to a DIExpression that is pushed onto the /// builder's expression stack. The stack should already contain an /// expression for the iteration count, so that it can be multiplied by @@ -6133,74 +6173,294 @@ struct SCEVDbgValueBuilder { } return true; } + + // Append the current expression and locations to a location list and an + // expression list. Modify the DW_OP_LLVM_arg indexes to account for + // the locations already present in the destination list. + void appendToVectors(SmallVectorImpl<uint64_t> &DestExpr, + SmallVectorImpl<Value *> &DestLocations) { + assert(!DestLocations.empty() && + "Expected the locations vector to contain the IV"); + // The DWARF_OP_LLVM_arg arguments of the expression being appended must be + // modified to account for the locations already in the destination vector. + // All builders contain the IV as the first location op. + assert(!LocationOps.empty() && + "Expected the location ops to contain the IV."); + // DestIndexMap[n] contains the index in DestLocations for the nth + // location in this SCEVDbgValueBuilder. + SmallVector<uint64_t, 2> DestIndexMap; + for (const auto &Op : LocationOps) { + auto It = find(DestLocations, Op); + if (It != DestLocations.end()) { + // Location already exists in DestLocations, reuse existing ArgIndex. + DestIndexMap.push_back(std::distance(DestLocations.begin(), It)); + continue; + } + // Location is not in DestLocations, add it. + DestIndexMap.push_back(DestLocations.size()); + DestLocations.push_back(Op); + } + + for (const auto &Op : expr_ops()) { + if (Op.getOp() != dwarf::DW_OP_LLVM_arg) { + Op.appendToVector(DestExpr); + continue; + } + + DestExpr.push_back(dwarf::DW_OP_LLVM_arg); + // `DW_OP_LLVM_arg n` represents the nth LocationOp in this SCEV, + // DestIndexMap[n] contains its new index in DestLocations. + uint64_t NewIndex = DestIndexMap[Op.getArg(0)]; + DestExpr.push_back(NewIndex); + } + } }; +/// Holds all the required data to salvage a dbg.value using the pre-LSR SCEVs +/// and DIExpression. struct DVIRecoveryRec { + DVIRecoveryRec(DbgValueInst *DbgValue) + : DVI(DbgValue), Expr(DbgValue->getExpression()), + HadLocationArgList(false) {} + DbgValueInst *DVI; DIExpression *Expr; - Metadata *LocationOp; - const llvm::SCEV *SCEV; + bool HadLocationArgList; + SmallVector<WeakVH, 2> LocationOps; + SmallVector<const llvm::SCEV *, 2> SCEVs; + SmallVector<std::unique_ptr<SCEVDbgValueBuilder>, 2> RecoveryExprs; + + void clear() { + for (auto &RE : RecoveryExprs) + RE.reset(); + RecoveryExprs.clear(); + } + + ~DVIRecoveryRec() { clear(); } }; } // namespace -static void RewriteDVIUsingIterCount(DVIRecoveryRec CachedDVI, - const SCEVDbgValueBuilder &IterationCount, - ScalarEvolution &SE) { - // LSR may add locations to previously single location-op DVIs which - // are currently not supported. - if (CachedDVI.DVI->getNumVariableLocationOps() != 1) - return; +/// Returns the total number of DW_OP_llvm_arg operands in the expression. +/// This helps in determining if a DIArglist is necessary or can be omitted from +/// the dbg.value. +static unsigned numLLVMArgOps(SmallVectorImpl<uint64_t> &Expr) { + auto expr_ops = ToDwarfOpIter(Expr); + unsigned Count = 0; + for (auto Op : expr_ops) + if (Op.getOp() == dwarf::DW_OP_LLVM_arg) + Count++; + return Count; +} - // SCEVs for SSA values are most frquently of the form - // {start,+,stride}, but sometimes they are ({start,+,stride} + %a + ..). - // This is because %a is a PHI node that is not the IV. However, these - // SCEVs have not been observed to result in debuginfo-lossy optimisations, - // so its not expected this point will be reached. - if (!isa<SCEVAddRecExpr>(CachedDVI.SCEV)) - return; +/// Overwrites DVI with the location and Ops as the DIExpression. This will +/// create an invalid expression if Ops has any dwarf::DW_OP_llvm_arg operands, +/// because a DIArglist is not created for the first argument of the dbg.value. +static void updateDVIWithLocation(DbgValueInst &DVI, Value *Location, + SmallVectorImpl<uint64_t> &Ops) { + assert( + numLLVMArgOps(Ops) == 0 && + "Expected expression that does not contain any DW_OP_llvm_arg operands."); + DVI.setRawLocation(ValueAsMetadata::get(Location)); + DVI.setExpression(DIExpression::get(DVI.getContext(), Ops)); +} - LLVM_DEBUG(dbgs() << "scev-salvage: Value to salvage SCEV: " - << *CachedDVI.SCEV << '\n'); +/// Overwrite DVI with locations placed into a DIArglist. +static void updateDVIWithLocations(DbgValueInst &DVI, + SmallVectorImpl<Value *> &Locations, + SmallVectorImpl<uint64_t> &Ops) { + assert(numLLVMArgOps(Ops) != 0 && + "Expected expression that references DIArglist locations using " + "DW_OP_llvm_arg operands."); + SmallVector<ValueAsMetadata *, 3> MetadataLocs; + for (Value *V : Locations) + MetadataLocs.push_back(ValueAsMetadata::get(V)); + auto ValArrayRef = llvm::ArrayRef<llvm::ValueAsMetadata *>(MetadataLocs); + DVI.setRawLocation(llvm::DIArgList::get(DVI.getContext(), ValArrayRef)); + DVI.setExpression(DIExpression::get(DVI.getContext(), Ops)); +} - const auto *Rec = cast<SCEVAddRecExpr>(CachedDVI.SCEV); - if (!Rec->isAffine()) - return; +/// Write the new expression and new location ops for the dbg.value. If possible +/// reduce the szie of the dbg.value intrinsic by omitting DIArglist. This +/// can be omitted if: +/// 1. There is only a single location, refenced by a single DW_OP_llvm_arg. +/// 2. The DW_OP_LLVM_arg is the first operand in the expression. +static void UpdateDbgValueInst(DVIRecoveryRec &DVIRec, + SmallVectorImpl<Value *> &NewLocationOps, + SmallVectorImpl<uint64_t> &NewExpr) { + unsigned NumLLVMArgs = numLLVMArgOps(NewExpr); + if (NumLLVMArgs == 0) { + // Location assumed to be on the stack. + updateDVIWithLocation(*DVIRec.DVI, NewLocationOps[0], NewExpr); + } else if (NumLLVMArgs == 1 && NewExpr[0] == dwarf::DW_OP_LLVM_arg) { + // There is only a single DW_OP_llvm_arg at the start of the expression, + // so it can be omitted along with DIArglist. + assert(NewExpr[1] == 0 && + "Lone LLVM_arg in a DIExpression should refer to location-op 0."); + llvm::SmallVector<uint64_t, 6> ShortenedOps(llvm::drop_begin(NewExpr, 2)); + updateDVIWithLocation(*DVIRec.DVI, NewLocationOps[0], ShortenedOps); + } else { + // Multiple DW_OP_llvm_arg, so DIArgList is strictly necessary. + updateDVIWithLocations(*DVIRec.DVI, NewLocationOps, NewExpr); + } - if (CachedDVI.SCEV->getExpressionSize() > MaxSCEVSalvageExpressionSize) - return; + // If the DIExpression was previously empty then add the stack terminator. + // Non-empty expressions have only had elements inserted into them and so the + // terminator should already be present e.g. stack_value or fragment. + DIExpression *SalvageExpr = DVIRec.DVI->getExpression(); + if (!DVIRec.Expr->isComplex() && SalvageExpr->isComplex()) { + SalvageExpr = DIExpression::append(SalvageExpr, {dwarf::DW_OP_stack_value}); + DVIRec.DVI->setExpression(SalvageExpr); + } +} - // Initialise a new builder with the iteration count expression. In - // combination with the value's SCEV this enables recovery. - SCEVDbgValueBuilder RecoverValue(IterationCount); - if (!RecoverValue.SCEVToValueExpr(*Rec, SE)) - return; +/// Cached location ops may be erased during LSR, in which case an undef is +/// required when restoring from the cache. The type of that location is no +/// longer available, so just use int8. The undef will be replaced by one or +/// more locations later when a SCEVDbgValueBuilder selects alternative +/// locations to use for the salvage. +static Value *getValueOrUndef(WeakVH &VH, LLVMContext &C) { + return (VH) ? VH : UndefValue::get(llvm::Type::getInt8Ty(C)); +} + +/// Restore the DVI's pre-LSR arguments. Substitute undef for any erased values. +static void restorePreTransformState(DVIRecoveryRec &DVIRec) { + LLVM_DEBUG(dbgs() << "scev-salvage: restore dbg.value to pre-LSR state\n" + << "scev-salvage: post-LSR: " << *DVIRec.DVI << '\n'); + assert(DVIRec.Expr && "Expected an expression"); + DVIRec.DVI->setExpression(DVIRec.Expr); - LLVM_DEBUG(dbgs() << "scev-salvage: Updating: " << *CachedDVI.DVI << '\n'); - RecoverValue.applyExprToDbgValue(*CachedDVI.DVI, CachedDVI.Expr); - LLVM_DEBUG(dbgs() << "scev-salvage: to: " << *CachedDVI.DVI << '\n'); + // Even a single location-op may be inside a DIArgList and referenced with + // DW_OP_LLVM_arg, which is valid only with a DIArgList. + if (!DVIRec.HadLocationArgList) { + assert(DVIRec.LocationOps.size() == 1 && + "Unexpected number of location ops."); + // LSR's unsuccessful salvage attempt may have added DIArgList, which in + // this case was not present before, so force the location back to a single + // uncontained Value. + Value *CachedValue = + getValueOrUndef(DVIRec.LocationOps[0], DVIRec.DVI->getContext()); + DVIRec.DVI->setRawLocation(ValueAsMetadata::get(CachedValue)); + } else { + SmallVector<ValueAsMetadata *, 3> MetadataLocs; + for (WeakVH VH : DVIRec.LocationOps) { + Value *CachedValue = getValueOrUndef(VH, DVIRec.DVI->getContext()); + MetadataLocs.push_back(ValueAsMetadata::get(CachedValue)); + } + auto ValArrayRef = llvm::ArrayRef<llvm::ValueAsMetadata *>(MetadataLocs); + DVIRec.DVI->setRawLocation( + llvm::DIArgList::get(DVIRec.DVI->getContext(), ValArrayRef)); + } + LLVM_DEBUG(dbgs() << "scev-salvage: pre-LSR: " << *DVIRec.DVI << '\n'); } -static void RewriteDVIUsingOffset(DVIRecoveryRec &DVIRec, llvm::PHINode &IV, - int64_t Offset) { - assert(!DVIRec.DVI->hasArgList() && "Expected single location-op dbg.value."); - DbgValueInst *DVI = DVIRec.DVI; - SmallVector<uint64_t, 8> Ops; - DIExpression::appendOffset(Ops, Offset); - DIExpression *Expr = DIExpression::prependOpcodes(DVIRec.Expr, Ops, true); - LLVM_DEBUG(dbgs() << "scev-salvage: Updating: " << *DVIRec.DVI << '\n'); - DVI->setExpression(Expr); - llvm::Value *ValIV = dyn_cast<llvm::Value>(&IV); - DVI->replaceVariableLocationOp( - 0u, llvm::MetadataAsValue::get(DVI->getContext(), - llvm::ValueAsMetadata::get(ValIV))); - LLVM_DEBUG(dbgs() << "scev-salvage: updated with offset to IV: " - << *DVIRec.DVI << '\n'); +static bool SalvageDVI(llvm::Loop *L, ScalarEvolution &SE, + llvm::PHINode *LSRInductionVar, DVIRecoveryRec &DVIRec, + const SCEV *SCEVInductionVar, + SCEVDbgValueBuilder IterCountExpr) { + if (!DVIRec.DVI->isUndef()) + return false; + + // LSR may have caused several changes to the dbg.value in the failed salvage + // attempt. So restore the DIExpression, the location ops and also the + // location ops format, which is always DIArglist for multiple ops, but only + // sometimes for a single op. + restorePreTransformState(DVIRec); + + // LocationOpIndexMap[i] will store the post-LSR location index of + // the non-optimised out location at pre-LSR index i. + SmallVector<int64_t, 2> LocationOpIndexMap; + LocationOpIndexMap.assign(DVIRec.LocationOps.size(), -1); + SmallVector<Value *, 2> NewLocationOps; + NewLocationOps.push_back(LSRInductionVar); + + for (unsigned i = 0; i < DVIRec.LocationOps.size(); i++) { + WeakVH VH = DVIRec.LocationOps[i]; + // Place the locations not optimised out in the list first, avoiding + // inserts later. The map is used to update the DIExpression's + // DW_OP_LLVM_arg arguments as the expression is updated. + if (VH && !isa<UndefValue>(VH)) { + NewLocationOps.push_back(VH); + LocationOpIndexMap[i] = NewLocationOps.size() - 1; + LLVM_DEBUG(dbgs() << "scev-salvage: Location index " << i + << " now at index " << LocationOpIndexMap[i] << "\n"); + continue; + } + + // It's possible that a value referred to in the SCEV may have been + // optimised out by LSR. + if (SE.containsErasedValue(DVIRec.SCEVs[i]) || + SE.containsUndefs(DVIRec.SCEVs[i])) { + LLVM_DEBUG(dbgs() << "scev-salvage: SCEV for location at index: " << i + << " refers to a location that is now undef or erased. " + "Salvage abandoned.\n"); + return false; + } + + LLVM_DEBUG(dbgs() << "scev-salvage: salvaging location at index " << i + << " with SCEV: " << *DVIRec.SCEVs[i] << "\n"); + + DVIRec.RecoveryExprs[i] = std::make_unique<SCEVDbgValueBuilder>(); + SCEVDbgValueBuilder *SalvageExpr = DVIRec.RecoveryExprs[i].get(); + + // Create an offset-based salvage expression if possible, as it requires + // less DWARF ops than an iteration count-based expression. + if (Optional<APInt> Offset = + SE.computeConstantDifference(DVIRec.SCEVs[i], SCEVInductionVar)) { + if (Offset.getValue().getMinSignedBits() <= 64) + SalvageExpr->createOffsetExpr(Offset.getValue().getSExtValue(), + LSRInductionVar); + } else if (!SalvageExpr->createIterCountExpr(DVIRec.SCEVs[i], IterCountExpr, + SE)) + return false; + } + + // Merge the DbgValueBuilder generated expressions and the original + // DIExpression, place the result into an new vector. + SmallVector<uint64_t, 3> NewExpr; + if (DVIRec.Expr->getNumElements() == 0) { + assert(DVIRec.RecoveryExprs.size() == 1 && + "Expected only a single recovery expression for an empty " + "DIExpression."); + assert(DVIRec.RecoveryExprs[0] && + "Expected a SCEVDbgSalvageBuilder for location 0"); + SCEVDbgValueBuilder *B = DVIRec.RecoveryExprs[0].get(); + B->appendToVectors(NewExpr, NewLocationOps); + } + for (const auto &Op : DVIRec.Expr->expr_ops()) { + // Most Ops needn't be updated. + if (Op.getOp() != dwarf::DW_OP_LLVM_arg) { + Op.appendToVector(NewExpr); + continue; + } + + uint64_t LocationArgIndex = Op.getArg(0); + SCEVDbgValueBuilder *DbgBuilder = + DVIRec.RecoveryExprs[LocationArgIndex].get(); + // The location doesn't have s SCEVDbgValueBuilder, so LSR did not + // optimise it away. So just translate the argument to the updated + // location index. + if (!DbgBuilder) { + NewExpr.push_back(dwarf::DW_OP_LLVM_arg); + assert(LocationOpIndexMap[Op.getArg(0)] != -1 && + "Expected a positive index for the location-op position."); + NewExpr.push_back(LocationOpIndexMap[Op.getArg(0)]); + continue; + } + // The location has a recovery expression. + DbgBuilder->appendToVectors(NewExpr, NewLocationOps); + } + + UpdateDbgValueInst(DVIRec, NewLocationOps, NewExpr); + LLVM_DEBUG(dbgs() << "scev-salvage: Updated DVI: " << *DVIRec.DVI << "\n"); + return true; } +/// Obtain an expression for the iteration count, then attempt to salvage the +/// dbg.value intrinsics. static void DbgRewriteSalvageableDVIs(llvm::Loop *L, ScalarEvolution &SE, llvm::PHINode *LSRInductionVar, - SmallVector<DVIRecoveryRec, 2> &DVIToUpdate) { + SmallVector<std::unique_ptr<DVIRecoveryRec>, 2> &DVIToUpdate) { if (DVIToUpdate.empty()) return; @@ -6213,49 +6473,22 @@ DbgRewriteSalvageableDVIs(llvm::Loop *L, ScalarEvolution &SE, if (!IVAddRec->isAffine()) return; + // Prevent translation using excessive resources. if (IVAddRec->getExpressionSize() > MaxSCEVSalvageExpressionSize) return; // The iteration count is required to recover location values. SCEVDbgValueBuilder IterCountExpr; - IterCountExpr.pushValue(LSRInductionVar); + IterCountExpr.pushLocation(LSRInductionVar); if (!IterCountExpr.SCEVToIterCountExpr(*IVAddRec, SE)) return; LLVM_DEBUG(dbgs() << "scev-salvage: IV SCEV: " << *SCEVInductionVar << '\n'); - // Needn't salvage if the location op hasn't been undef'd by LSR. for (auto &DVIRec : DVIToUpdate) { - if (!DVIRec.DVI->isUndef()) - continue; - - // Some DVIs that were single location-op when cached are now multi-op, - // due to LSR optimisations. However, multi-op salvaging is not yet - // supported by SCEV salvaging. But, we can attempt a salvage by restoring - // the pre-LSR single-op expression. - if (DVIRec.DVI->hasArgList()) { - if (!DVIRec.DVI->getVariableLocationOp(0)) - continue; - llvm::Type *Ty = DVIRec.DVI->getVariableLocationOp(0)->getType(); - DVIRec.DVI->setRawLocation( - llvm::ValueAsMetadata::get(UndefValue::get(Ty))); - DVIRec.DVI->setExpression(DVIRec.Expr); - } - - LLVM_DEBUG(dbgs() << "scev-salvage: value to recover SCEV: " - << *DVIRec.SCEV << '\n'); - - // Create a simple expression if the IV and value to salvage SCEVs - // start values differ by only a constant value. - if (Optional<APInt> Offset = - SE.computeConstantDifference(DVIRec.SCEV, SCEVInductionVar)) { - if (Offset.getValue().getMinSignedBits() <= 64) - RewriteDVIUsingOffset(DVIRec, *LSRInductionVar, - Offset.getValue().getSExtValue()); - } else { - RewriteDVIUsingIterCount(DVIRec, IterCountExpr, SE); - } + SalvageDVI(L, SE, LSRInductionVar, *DVIRec, SCEVInductionVar, + IterCountExpr); } } } @@ -6263,39 +6496,53 @@ DbgRewriteSalvageableDVIs(llvm::Loop *L, ScalarEvolution &SE, /// Identify and cache salvageable DVI locations and expressions along with the /// corresponding SCEV(s). Also ensure that the DVI is not deleted between /// cacheing and salvaging. -static void -DbgGatherSalvagableDVI(Loop *L, ScalarEvolution &SE, - SmallVector<DVIRecoveryRec, 2> &SalvageableDVISCEVs, - SmallSet<AssertingVH<DbgValueInst>, 2> &DVIHandles) { +static void DbgGatherSalvagableDVI( + Loop *L, ScalarEvolution &SE, + SmallVector<std::unique_ptr<DVIRecoveryRec>, 2> &SalvageableDVISCEVs, + SmallSet<AssertingVH<DbgValueInst>, 2> &DVIHandles) { for (auto &B : L->getBlocks()) { for (auto &I : *B) { auto DVI = dyn_cast<DbgValueInst>(&I); if (!DVI) continue; - + // Ensure that if any location op is undef that the dbg.vlue is not + // cached. if (DVI->isUndef()) continue; - if (DVI->hasArgList()) - continue; + // Check that the location op SCEVs are suitable for translation to + // DIExpression. + const auto &HasTranslatableLocationOps = + [&](const DbgValueInst *DVI) -> bool { + for (const auto LocOp : DVI->location_ops()) { + if (!LocOp) + return false; - if (!DVI->getVariableLocationOp(0) || - !SE.isSCEVable(DVI->getVariableLocationOp(0)->getType())) - continue; + if (!SE.isSCEVable(LocOp->getType())) + return false; - // SCEVUnknown wraps an llvm::Value, it does not have a start and stride. - // Therefore no translation to DIExpression is performed. - const SCEV *S = SE.getSCEV(DVI->getVariableLocationOp(0)); - if (isa<SCEVUnknown>(S)) - continue; + const SCEV *S = SE.getSCEV(LocOp); + if (SE.containsUndefs(S)) + return false; + } + return true; + }; - // Avoid wasting resources generating an expression containing undef. - if (SE.containsUndefs(S)) + if (!HasTranslatableLocationOps(DVI)) continue; - SalvageableDVISCEVs.push_back( - {DVI, DVI->getExpression(), DVI->getRawLocation(), - SE.getSCEV(DVI->getVariableLocationOp(0))}); + std::unique_ptr<DVIRecoveryRec> NewRec = + std::make_unique<DVIRecoveryRec>(DVI); + // Each location Op may need a SCEVDbgValueBuilder in order to recover it. + // Pre-allocating a vector will enable quick lookups of the builder later + // during the salvage. + NewRec->RecoveryExprs.resize(DVI->getNumVariableLocationOps()); + for (const auto LocOp : DVI->location_ops()) { + NewRec->SCEVs.push_back(SE.getSCEV(LocOp)); + NewRec->LocationOps.push_back(LocOp); + NewRec->HadLocationArgList = DVI->hasArgList(); + } + SalvageableDVISCEVs.push_back(std::move(NewRec)); DVIHandles.insert(DVI); } } @@ -6344,9 +6591,9 @@ static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE, // Debug preservation - before we start removing anything identify which DVI // meet the salvageable criteria and store their DIExpression and SCEVs. - SmallVector<DVIRecoveryRec, 2> SalvageableDVI; + SmallVector<std::unique_ptr<DVIRecoveryRec>, 2> SalvageableDVIRecords; SmallSet<AssertingVH<DbgValueInst>, 2> DVIHandles; - DbgGatherSalvagableDVI(L, SE, SalvageableDVI, DVIHandles); + DbgGatherSalvagableDVI(L, SE, SalvageableDVIRecords, DVIHandles); bool Changed = false; std::unique_ptr<MemorySSAUpdater> MSSAU; @@ -6375,8 +6622,26 @@ static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE, DeleteDeadPHIs(L->getHeader(), &TLI, MSSAU.get()); } } + // LSR may at times remove all uses of an induction variable from a loop. + // The only remaining use is the PHI in the exit block. + // When this is the case, if the exit value of the IV can be calculated using + // SCEV, we can replace the exit block PHI with the final value of the IV and + // skip the updates in each loop iteration. + if (L->isRecursivelyLCSSAForm(DT, LI) && LoopExitValHasSingleUse(L)) { + SmallVector<WeakTrackingVH, 16> DeadInsts; + const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); + SCEVExpander Rewriter(SE, DL, "lsr", false); + int Rewrites = rewriteLoopExitValues(L, &LI, &TLI, &SE, &TTI, Rewriter, &DT, + OnlyCheapRepl, DeadInsts); + if (Rewrites) { + Changed = true; + RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts, &TLI, + MSSAU.get()); + DeleteDeadPHIs(L->getHeader(), &TLI, MSSAU.get()); + } + } - if (SalvageableDVI.empty()) + if (SalvageableDVIRecords.empty()) return Changed; // Obtain relevant IVs and attempt to rewrite the salvageable DVIs with @@ -6384,13 +6649,16 @@ static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE, // TODO: Allow for multiple IV references for nested AddRecSCEVs for (auto &L : LI) { if (llvm::PHINode *IV = GetInductionVariable(*L, SE, Reducer)) - DbgRewriteSalvageableDVIs(L, SE, IV, SalvageableDVI); + DbgRewriteSalvageableDVIs(L, SE, IV, SalvageableDVIRecords); else { LLVM_DEBUG(dbgs() << "scev-salvage: SCEV salvaging not possible. An IV " "could not be identified.\n"); } } + for (auto &Rec : SalvageableDVIRecords) + Rec->clear(); + SalvageableDVIRecords.clear(); DVIHandles.clear(); return Changed; } |