Index: llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/include/llvm/Analysis/ScalarEvolution.h +++ llvm/include/llvm/Analysis/ScalarEvolution.h @@ -537,6 +537,9 @@ std::pair getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO); + /// Return true if the SCEV expression contains an undef value; + bool containsUndefs(const SCEV *S) const; + /// Return a SCEV expression for the full generality of the specified /// expression. const SCEV *getSCEV(Value *V); Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -12277,7 +12277,7 @@ } // Return true when S contains at least an undef value. -static inline bool containsUndefs(const SCEV *S) { +bool ScalarEvolution::containsUndefs(const SCEV *S) const { return SCEVExprContains(S, [](const SCEV *S) { if (const auto *SU = dyn_cast(S)) return isa(SU->getValue()); Index: llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -6235,6 +6235,12 @@ DVIRec.DVI->setExpression(DVIRec.Expr); } + // A SCEVUknown type is an entirely unknown SCEV value, represented only + // as an llvm value. At this point if the value hasn't been optimised away + // a salvage is unnecessary. If it has been then no progress can be made. + if(isa(DVIRec.SCEV)) + continue; + LLVM_DEBUG(dbgs() << "scev-salvage: value to recover SCEV: " << *DVIRec.SCEV << '\n'); @@ -6274,6 +6280,16 @@ !SE.isSCEVable(DVI->getVariableLocationOp(0)->getType())) continue; + const SCEV *S = SE.getSCEV(DVI->getVariableLocationOp(0)); + // SCEVUnknown can only be represented by an llvm Value, so no scev-based + // salvaging is possible. + // if(isa(S)) + // continue; + + // Avoid wasting resources generating an expression containing undef. + if(SE.containsUndefs(S)) + continue; + SalvageableDVISCEVs.push_back( {DVI, DVI->getExpression(), DVI->getRawLocation(), SE.getSCEV(DVI->getVariableLocationOp(0))}); @@ -6287,33 +6303,33 @@ /// surviving subsequent transforms. static llvm::PHINode *GetInductionVariable(const Loop &L, ScalarEvolution &SE, const LSRInstance &LSR) { - // For now, just pick the first IV generated and inserted. Ideally pick an IV - // that is unlikely to be optimised away by subsequent transforms. + + auto IsSuitableIV = [&](PHINode *P) { + if (!SE.isSCEVable(P->getType())) + return false; + if(const SCEVAddRecExpr *Rec = dyn_cast(SE.getSCEV(P))) + return Rec->isAffine() && !SE.containsUndefs(SE.getSCEV(P)); + return false; + }; + + // For now, just pick the first IV that was generated and inserted by + // ScalarEvolution. Ideally pick an IV that is unlikely to be optimised away + // by subsequent transforms. for (const WeakVH &IV : LSR.getScalarEvolutionIVs()) { if (!IV) continue; - assert(isa(&*IV) && "Expected PhI node."); - if (SE.isSCEVable((*IV).getType())) { - PHINode *Phi = dyn_cast(&*IV); - LLVM_DEBUG(dbgs() << "scev-salvage: IV : " << *IV - << "with SCEV: " << *SE.getSCEV(Phi) << "\n"); - return Phi; - } - } - - for (PHINode &Phi : L.getHeader()->phis()) { - if (!SE.isSCEVable(Phi.getType())) + PHINode *P = dyn_cast(&*IV); + if (!P) continue; - const llvm::SCEV *PhiSCEV = SE.getSCEV(&Phi); - if (const llvm::SCEVAddRecExpr *Rec = dyn_cast(PhiSCEV)) - if (!Rec->isAffine()) - continue; + if (IsSuitableIV(P)) + return P; + } - LLVM_DEBUG(dbgs() << "scev-salvage: Selected IV from loop header: " << Phi - << " with SCEV: " << *PhiSCEV << "\n"); - return Φ + for (PHINode &P : L.getHeader()->phis()) { + if (IsSuitableIV(&P)) + return &P; } return nullptr; } Index: llvm/test/Transforms/LoopStrengthReduce/pr52161.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LoopStrengthReduce/pr52161.ll @@ -0,0 +1,57 @@ +; RUN: opt -debug -S -loop-reduce %s 2>&1 | FileCheck %s + +; Ensure that scev-based salvaging in LSR does not select an IV containing +; an 'undef' element. + +; CHECK-NOT: scev-salvage: IV SCEV: {undef,+,-1} +; CHECK: scev-salvage: SCEV salvaging not possible. An IV could not be identified. +; CHECK: scev-salvage: SCEV salvaging not possible. An IV could not be identified. + +target triple = "x86_64-unknown-linux-gnu" + +define i16 @n() !dbg !8 { +entry: + br i1 undef, label %m, label %for.body + +for.body: ; preds = %for.body, %entry + %iv = phi i16 [ %ivdec, %for.body ], [ undef, %entry ] + %ivdec = sub i16 %iv, 1 + call void @llvm.dbg.value(metadata i16 %iv, metadata !21, metadata !DIExpression()), !dbg !19 + br label %for.body + +m: ; preds = %m, %entry + %0 = phi i16 [ 3, %m ], [ 6, %entry ] + ; CHECK: call void @llvm.dbg.value(metadata i16 undef, metadata !{{[0-9]+}}, metadata !DIExpression()), + call void @llvm.dbg.value(metadata i16 %0, metadata !14, metadata !DIExpression()), !dbg !19 + br label %m +} + +; Function Attrs: nofree nosync nounwind readnone speculatable willreturn +declare void @llvm.dbg.value(metadata, metadata, metadata) + +!llvm.dbg.cu = !{!0} +!llvm.module.flags = !{!3, !4, !5, !6} +!llvm.ident = !{!7} + +!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 14.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, globals: !2, splitDebugInlining: false, nameTableKind: None) +!1 = !DIFile(filename: "reduced.c", directory: "/") +!2 = !{} +!3 = !{i32 7, !"Dwarf Version", i32 4} +!4 = !{i32 2, !"Debug Info Version", i32 3} +!5 = !{i32 1, !"wchar_size", i32 1} +!6 = !{i32 7, !"frame-pointer", i32 2} +!7 = !{!"clang version 14.0.0"} +!8 = distinct !DISubprogram(name: "n", scope: !1, file: !1, line: 18, type: !9, scopeLine: 18, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !12) +!9 = !DISubroutineType(types: !10) +!10 = !{!11} +!11 = !DIBasicType(name: "int", size: 16, encoding: DW_ATE_signed) +!12 = !{!13} +!13 = !DILabel(scope: !8, name: "m", file: !1, line: 22) +!14 = !DILocalVariable(name: "k", arg: 2, scope: !15, file: !1, line: 9, type: !11) +!15 = distinct !DISubprogram(name: "i", scope: !1, file: !1, line: 9, type: !16, scopeLine: 9, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !18) +!16 = !DISubroutineType(types: !17) +!17 = !{!11, !11, !11} +!18 = !{!14} +!19 = !DILocation(line: 0, scope: !15, inlinedAt: !20) +!20 = distinct !DILocation(line: 23, scope: !8) +!21 = !DILocalVariable(name: "x", arg: 2, scope: !15, file: !1, line: 1, type: !11)