SCEVExpander::expandAddRecExprLiterally(): check before casting as Instruction

[lebedev.ri]

Summary

An alternative to D48597.
Fixes PR37936.

The problem is as follows:

1. indvars marks %dec as NUW.
2. loop-instsimplify runs instsimplify, which constant-folds %dec to -1 (D47908)
3. loop-reduce tries to do some further modification, but crashes with an type assertion in cast, because %dec is no longer an Instruction,

If the runline is split into two, i.e. you first run -indvars -loop-instsimplify,
store that into a file, and then run -loop-reduce, there is no crash.

So it looks like the problem is due to -loop-instsimplify not discarding SCEV.
But in this case we can just not crash if it's not an Instruction.
This is just a local fix, unlike D48597, so there may very well be other problems.

[evstupac]

lib/Analysis/ScalarEvolutionExpander.cpp

1172–1175 ↗

(On Diff #152916)

It looks very similar to dyn_cast:

Instruction *TempIncV =
    dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
if (!TempIncV)
  continue;

[lebedev.ri]

Simplify code via dyn_cast<>().

[lebedev.ri]

In D48597#1143719, @sanjoy wrote:

In D48597#1143657, @lebedev.ri wrote:

In D48597#1143645, @sanjoy wrote:

IMO this doesn't seem like an invalidation bug -- SCEV Expander needs to be smarter about dealing with these kinds of simplifications.

Does this sound better?

Yes -- that seems better to me.

BTW i think this is a wrong fix.
In this case, after -loop-reduce we still end up with the same output as the input, just slightly renamed, still with %dec.
So we can be doing -indvars -loop-instsimplify -loop-reduce any number of times, in an endless loop...

[uabelho]

This change indeed makes the crash go away but I have no idea if this is the right solution or if https://reviews.llvm.org/D48597 is better.

[mkazantsev]

Frankly, I don't understand why we want it to be an instruction at all. Can these methods (i.e. hoistIVInc and isNormalAddRecExprPHI) be taught to work with values? For example, if it is not an instruction then we just consider it already hoisted.

[mkazantsev]

lib/Analysis/ScalarEvolutionExpander.cpp

1172 ↗

(On Diff #152922)

Naming here is also confusing. V assumes that it should be a value. If there is no strong reason to keep it an instruction, I'd suggest reworking this code to deal with values.

[lebedev.ri]

lib/Analysis/ScalarEvolutionExpander.cpp

1172 ↗

(On Diff #152922)

I'm afraid i have no knowledge of this code to do anything like that.
So the crash can either stay, or this band-aid can land, and a bug
about possibility to rework this code to work with Value be filled.

[mkazantsev]

LGTM once a TODO comment is added.

lib/Analysis/ScalarEvolutionExpander.cpp

1172 ↗

(On Diff #152922)

Ok, I'm actually OK with the current solution. Just add a TODO comment that this possibly can be reworked to avoid this cast at all.

[lebedev.ri]

In D48599#1147514, @mkazantsev wrote:

LGTM once a TODO comment is added.

Thank you for the review!

[lebedev.ri]

This comment has been deleted.

lib/Analysis/ScalarEvolutionExpander.cpp

1172 ↗

(On Diff #152922)

Ok, great, thank you.

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

for (PHINode &PN : L->getHeader()->phis()) {
 
       bool IsMatchingSCEV = PhiSCEV == Normalized;
       // We only handle truncation and inversion of phi recurrences for the
       // expanded expression if the expanded expression's loop dominates the
       // loop we insert to. Check now, so we can bail out early.
       if (!IsMatchingSCEV && !TryNonMatchingSCEV)
           continue;
 
+      // TODO: this possibly can be reworked to avoid this cast at all.
       Instruction *TempIncV =
-          cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
+          dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
+      if (!TempIncV)
+        continue;
 
       // Check whether we can reuse this PHI node.
       if (LSRMode) {
         if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
           continue;
         if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos))
           continue;
       } else {

llvm/trunk/test/Transforms/LoopStrengthReduce/scev-after-loopinstsimplify.ll

+; RUN: opt %s -indvars -loop-instsimplify -loop-reduce
+; We are only checking that there is no crash!
+
+; https://bugs.llvm.org/show_bug.cgi?id=37936
+
+; The problem is as follows:
+; 1. indvars marks %dec as NUW.
+; 2. loop-instsimplify runs instsimplify, which constant-folds %dec to -1
+; 3. loop-reduce tries to do some further modification, but crashes
+;    with an type assertion in cast, because %dec is no longer an Instruction,
+;    even though the SCEV data indicated it was.
+
+; If the runline is split into two, i.e. -indvars -loop-instsimplify first, that
+; stored into a file, and then -loop-reduce is run on that, there is no crash.
+; So it looks like the problem is due to -loop-instsimplify not discarding SCEV.
+
+target datalayout = "n16"
+
+@a = external global i16, align 1
+
+define void @f1() {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %land.end, %entry
+  %c.0 = phi i16 [ 0, %entry ], [ %dec, %land.end ]
+  br i1 undef, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  ret void
+
+for.body:                                         ; preds = %for.cond
+  %0 = load i16, i16* @a, align 1
+  %cmp = icmp sgt i16 %0, %c.0
+  br i1 %cmp, label %land.rhs, label %land.end
+
+land.rhs:                                         ; preds = %for.body
+  unreachable
+
+land.end:                                         ; preds = %for.body
+  %dec = add nsw i16 %c.0, -1
+  br label %for.cond
+}