[DebugInfo][LSR] Add more stringent checks on IV selection and cached dbg.value location-op SCEVs

[chrisjackson]

Summary

Reported in Bug PR52161, there were two issues.

1. That IVs with SCEVs containing 'undef' could be selected. This would lead to fruitless salvage attempts.
2. Sometimes dbg.value arguments were cached along with a SCEVUnknown type for the value. Effectively this SCEV is a wrapped llvm::value, so no scev-based salvaging can usefully be performed in this case.

While I was in the area I tidied up the IV selection logic a little, extracting a lambda that can be applied to the two sets of IV potentials, each of which has different types (a PHI node or a handle to a PHI).

As ScalarEvolution already contained a static method to traverse SCEVs and find undefs, I changed the visibility so that containsUndefs(SCEV*) was now a public method of ScalarEvolution.

[chrisjackson]

Applied clang-format.

[StephenTozer]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6221–6226

Should we check for an undef SCEV here as well, or is the SCEV expression guaranteed to not be undef at this point?

[Orlando]

Hi @chrisjackson, I added a couple of nits inline. Is there anyone you can add as reviewer that are more familiar with LSR/SCEV?

llvm/include/llvm/Analysis/ScalarEvolution.h

537

nit: in the comment ; -> .

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6239–6240

Could you fix this comment while you're here? (Also ensure that the DVI is not deleted before ...)

6302–6303

Is this change necessary before IV might be UndefValue? If that's the case, it may be clearer to do this:

if (isa<UndefValue>(&*IV))
    continue;
PHINode *P = cast<PHINode>(&*IV);

Or am I misunderstanding?

llvm/test/Transforms/LoopStrengthReduce/pr52161.ll

4 ↗

(On Diff #379951)

nit: missing full stop.

6–7 ↗

(On Diff #379951)

I wonder if the -debug output is necessary? As far as the IR output is concerned, we just want to see an undef dbg.value is generated but don't need to know how we arrived there. What do you think?

[chrisjackson]

Updated after reviewer comments.

• Remove double check for SCEVUknown
• Remove check of opt debug output in lit test

[chrisjackson]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6302–6303

Not exactly. The IV's SCEV may contain an undef. I don't think that is the same as the IV value being undef,

[chrisjackson]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6221–6226

This additional check was unnecessary, as DbgGatherSalvagableDVI() will prevent SCEVUknown or SCEVs containing an undef from being cached.

[chrisjackson]

llvm/test/Transforms/LoopStrengthReduce/pr52161.ll

6–7 ↗

(On Diff #379951)

Agreed, I've removed the need for -debug

[Orlando]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6302–6303

Ah ok, then - sorry if this is a silly question - why have you weakened the assert assert(isa<PHINode>(&*IV) && "Expected PhI node."); to a dyn_cast-check?

[chrisjackson]

Reinstated the assert in GetInductionVariable().

[chrisjackson]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6302–6303

This was an oversight, Thanks for the correction.

[Orlando]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6302–6303

I think you could simplify this (sorry for the continued nits), from:

assert(isa<PHINode>(&*IV) && "Expected PhI node.");
PHINode *P = dyn_cast<PHINode>(&*IV);
if (!P)
  continue;

to

PHINode *P = cast<PHINode>(&*IV);

[chrisjackson]

Amended assert and dyn_cast to cast.

[Orlando]

LGTM

[chrisjackson]

The lit test that was reviewed here was added with commit c63adfb8.

llvm/include/llvm/Analysis/ScalarEvolution.h

bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed,
                        const SCEV *LHS, const SCEV *RHS);
 
   /// Parse NSW/NUW flags from add/sub/mul IR binary operation \p Op into
   /// SCEV no-wrap flags, and deduce flag[s] that aren't known yet.
   /// Does not mutate the original instruction.
   std::pair<SCEV::NoWrapFlags, bool /*Deduced*/>
   getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO);
 
   /// Notify this ScalarEvolution that \p User directly uses SCEVs in \p Ops.
   void registerUser(const SCEV *User, ArrayRef<const SCEV *> Ops);
 
+  /// 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);
 
   const SCEV *getConstant(ConstantInt *V);
   const SCEV *getConstant(const APInt &Val);
   const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
   const SCEV *getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth = 0);

llvm/lib/Analysis/ScalarEvolution.cpp

SCEVAddRecExpr::getPostIncExpr(ScalarEvolution &SE) const {
   const SCEV *Last = getOperand(getNumOperands() - 1);
   assert(!Last->isZero() && "Recurrency with zero step?");
   Ops.push_back(Last);
   return cast<SCEVAddRecExpr>(SE.getAddRecExpr(Ops, getLoop(),
                                                SCEV::FlagAnyWrap));
 }
 
 // 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<SCEVUnknown>(S))
       return isa<UndefValue>(SU->getValue());
     return false;
   });
 }
 
 /// Return the size of an element read or written by Inst.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

for (auto &DVIRec : DVIToUpdate) {
         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);
       }
     }
   }
 }
 
 /// Identify and cache salvageable DVI locations and expressions along with the
-/// corresponding SCEV(s). Also ensure that the DVI is not deleted before
+/// 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) {
   for (auto &B : L->getBlocks()) {
     for (auto &I : *B) {
       auto DVI = dyn_cast<DbgValueInst>(&I);
       if (!DVI)
         continue;
 
       if (DVI->isUndef())
         continue;
 
       if (DVI->hasArgList())
         continue;
 
       if (!DVI->getVariableLocationOp(0) ||
           !SE.isSCEVable(DVI->getVariableLocationOp(0)->getType()))
         continue;
 
+      // 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;
+
+      // 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))});
       DVIHandles.insert(DVI);
     }
   }
 }
 
 /// Ideally pick the PHI IV inserted by ScalarEvolutionExpander. As a fallback
 /// any PHi from the loop header is usable, but may have less chance of
 /// 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<SCEVAddRecExpr>(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<PHINode>(&*IV) && "Expected PhI node.");
-    if (SE.isSCEVable((*IV).getType())) {
-      PHINode *Phi = dyn_cast<PHINode>(&*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()))
-      continue;
+    // There should only be PHI node IVs.
+    PHINode *P = cast<PHINode>(&*IV);
 
-    const llvm::SCEV *PhiSCEV = SE.getSCEV(&Phi);
-    if (const llvm::SCEVAddRecExpr *Rec = dyn_cast<SCEVAddRecExpr>(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 &Phi;
+  for (PHINode &P : L.getHeader()->phis()) {
+    if (IsSuitableIV(&P))
+      return &P;
   }
   return nullptr;
 }
 
 static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE,
                                DominatorTree &DT, LoopInfo &LI,
                                const TargetTransformInfo &TTI,
                                AssumptionCache &AC, TargetLibraryInfo &TLI,