[SCEV] Relax abnormal exit check in isAddRecNeverPoison.

[fhahn]

Summary

Currently isAddRecNeverPoison fails if there are any abnormal exits in a
loop, like function calls that may throw.

This check can be a bit relaxed however: if the instruction we are
looking at is in the latch block and guaranteed to transfer execution
to the successor, then the instruction can never yield poison (if the
latch is control dependent on it), as the branch is always executed when
the instruction is executed.

[fhahn]

Actually check all instructions between I and the end of the block.

[efriedma]

Despite the fact that this takes an "Instruction*", it's not really trying to compute some property of users of that instruction; it's trying compute some property of users of the equivalent SCEV expression. So any computation based on the position of the instruction in the loop is not going to give the result you want: even if users of the given instruction can be assumed to be never poison, you can't generalize that property to all equivalent values in the loop.

I think there might be another way to handle the testcase, though. If the input instruction is a PHI node, we can use PHI-specific reasoning. In this context, we don't care if the base value is poison, I think; we're trying to compute a property of the increment. And the "add nsw" can't be poison because it's also used by the loop latch of the previous iteration: if it's poison, we can't reach the current iteration, regardless of whether the loop has other exits.

llvm/lib/Analysis/ScalarEvolution.cpp

6180

You're not checking "all instructions between I and the end of the block".

[fhahn]

In D79746#2030380, @efriedma wrote:

Despite the fact that this takes an "Instruction*", it's not really trying to compute some property of users of that instruction; it's trying compute some property of users of the equivalent SCEV expression. So any computation based on the position of the instruction in the loop is not going to give the result you want: even if users of the given instruction can be assumed to be never poison, you can't generalize that property to all equivalent values in the loop.

Thanks Eli! I missed that the instruction here is indeed not suitable for position based inference. It seems a bit unfortunate to me that we fail to make use of that information, until we actually construct a equivalent expression for which it does not hold :( Not sure how worthwhile/feasible it would be to try to invalidate the information. Do you know if something like that was explored previously?

I think there might be another way to handle the testcase, though. If the input instruction is a PHI node, we can use PHI-specific reasoning. In this context, we don't care if the base value is poison, I think; we're trying to compute a property of the increment. And the "add nsw" can't be poison because it's also used by the loop latch of the previous iteration: if it's poison, we can't reach the current iteration, regardless of whether the loop has other exits.

Sounds good! I also explored something similar earlier, but somehow thought the current version of the patch seemed a bit more direct (but I missed the bit about not being able to use the location here). I'll update the patch tomorrow.

[efriedma]

Not sure how worthwhile/feasible it would be to try to invalidate the information. Do you know if something like that was explored previously?

I don't think that's something anyone has looked at. I have no idea how it would work.

On a more general topic, there's been some interest in changing the way poison flags on SCEV expressions work, so it's possible to have both a poison and non-poison SCEV computing the same value. But nobody has actually tried to implement it, I think.

[fhahn]

In D79746#2032220, @fhahn wrote:

In D79746#2030380, @efriedma wrote:

I think there might be another way to handle the testcase, though. If the input instruction is a PHI node, we can use PHI-specific reasoning. In this context, we don't care if the base value is poison, I think; we're trying to compute a property of the increment. And the "add nsw" can't be poison because it's also used by the loop latch of the previous iteration: if it's poison, we can't reach the current iteration, regardless of whether the loop has other exits.

Sounds good! I also explored something similar earlier, but somehow thought the current version of the patch seemed a bit more direct (but I missed the bit about not being able to use the location here). I'll update the patch tomorrow.

Hm I think the reasoning does not really help here unfortunately, as isAddRecNeverPoison takes the increment instruction of the AddRec I think .

IIUC the problematic case is if the have an %iv.next = add nsw %iv, 1, we know that %iv cannot be poison (and %iv.next from the previous iteration also cannot be poison). But %iv.next could overflow in the current iteration and then take an abnormal exit, hence we cannot assume the AddRec never overflows.

In D79746#2032381, @efriedma wrote:

On a more general topic, there's been some interest in changing the way poison flags on SCEV expressions work, so it's possible to have both a poison and non-poison SCEV computing the same value. But nobody has actually tried to implement it, I think.

Would the idea here be allowing to use overflow flags for expressions depending on where an expression is evaluated/used? (for example the latch branch for the trip count computation)

[efriedma]

Would the idea here be allowing to use overflow flags for expressions depending on where an expression is evaluated/used? (for example the latch branch for the trip count computation)

I guess it could vary based on that. The discussion has mostly centered around making the overflow flags vary depending on whether the IR instruction is marked nsw/nuw, but that isn't the only possible input.

[fhahn]

In D79746#2038953, @efriedma wrote:

Would the idea here be allowing to use overflow flags for expressions depending on where an expression is evaluated/used? (for example the latch branch for the trip count computation)

I guess it could vary based on that. The discussion has mostly centered around making the overflow flags vary depending on whether the IR instruction is marked nsw/nuw, but that isn't the only possible input.

Thanks for clarifying! IIUC the idea would be to de-couple overflow flags from directly storing them in the expressions and have a way to pass them in depending on the context. I'll try to look into that when I have a bit more time.

llvm/lib/Analysis/ScalarEvolution.cpp

for (auto *PoisonUser : Poison->users()) {
         if (BI->getParent() == LatchBB) {
           LatchControlDependentOnPoison = true;
           break;
         }
       }
     }
   }
 
-  return LatchControlDependentOnPoison && loopHasNoAbnormalExits(L);
+  if (LatchControlDependentOnPoison) {
+    if (LatchBB == I->getParent())
+      // If I is in the latch and all instructions between I and the end of the
+      // block are guaranteed to execute, I cannot be poison.
+      return all_of(make_range(I->getIterator(), I->getParent()->end()),
+                    [](const Instruction &I) {
+                      return isGuaranteedToTransferExecutionToSuccessor(&I);
+                    });
+    return loopHasNoAbnormalExits(L);
+  }
+
+  return false;
 }
 
 ScalarEvolution::LoopProperties
 ScalarEvolution::getLoopProperties(const Loop *L) {
   using LoopProperties = ScalarEvolution::LoopProperties;
 
   auto Itr = LoopPropertiesCache.find(L);
   if (Itr == LoopPropertiesCache.end()) {

llvm/test/Transforms/LoopStrengthReduce/X86/2008-08-14-ShadowIV.ll

bb:   ; preds = %bb, %entry
   %tmp4 = tail call i32 (...) @nn( ) nounwind    ; <i32>:4 [#uses=1]
   %exitcond = icmp ugt i32 %tmp4, %indvar.next    ; <i1>:5 [#uses=1]
   br i1 %exitcond, label %bb, label %return
 
 return:   ; preds = %bb, %entry
   ret void
 }
 
-; Unable to eliminate cast due to overflow.
+; We can eliminate the cast, as all instructions between %indvar.next and the
+; branch are guaranteed to execute and branching on poison is undef. Hence
+; %indvar.next cannot overflow and neither can %i.03.
 define void @foobar4() nounwind {
 
 ; CHECK-LABEL:  foobar4(
-; CHECK-NOT:    phi double
-; CHECK-NOT:    phi float
+; CHECK:    phi double
 
 entry:
   br label %bb.nph
 
 bb.nph:   ; preds = %entry
   br label %bb
 
 bb:   ; preds = %bb, %bb.nph