[IndVarSimplify] Reduce nondeterministic behaviour in visitIVCast.

[sdesmalen]

Summary

rGf39978b84f1d3a1da6c32db48f64c8daae64b3ad led to and/or exposed
an issue with IndVarSimplification for a loop where a i32 phi node is
no longer replaced by a widened (i64) phi node, because the SCEVs of a
sign-extend no longer folded the same way. I'm unsure how to properly
explain this because it's all rather complicated, but in short: SCEVs
don't fold as nicely as they used to and this caused a difference.

While investigating this, I found that IndVarSimplify can actually
optimise the case in the way we want to if it chooses the widened IV to
be 'signed' (the i32 IV is both sign and zero-extended). Oddly enough,
there is some level of indeterminism in the way the algorithm works,
it just picks the sign of the 'first' zext/sext user, where the order of
the users-iterator is not guaranteed to be the same on each invocation
of the pass (e.g. shown by first running loop-rotate, which puts the
users in a different order).

While I think the fix is valid in the sense that consistently picking
_any_ order is better than having an nondeterministic order, I can
use a bit of advice from people more familiar in this area of the
code-base.

For example, I'm not sure if this fix is hiding another issue where the
IndVarSimplify pass could actually draw the same conclusions (i.e. that
it only needs an i64 phi node) if it does a bit more work, regardless
of whether it chooses the induction variable to be signed or unsigned.

I'm also not sure if choosing signed is better than unsigned, or whether
that just happens to be beneficial only in this individual case.

Any feedback would be much appreciated!

[mkazantsev]

If I understand your proposal correctly, you propose to replace scheme "take signedness from 1st user which is non-deterministically selected" with scheme "if at least one user of widest type is signed cast, widen as signed; otherwize widen as unsigned"?

In general, it makes sense to me and it also seems to solve the non-determinism you are describing. The only concern I have is, you use signed widening as default (and unsigned is possible under stricter conditions). On the other hand, IV tries hard to turn all icmp's to unsigned predicate form, preferring unsigned as default. This creates some discord between different parts of it.

Is it possible to use unsigned widening as break-even? In terms of your patch it would be replacing

WI.IsSigned |= IsSigned;

with

WI.IsSigned &= IsSigned;

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

560

Do you mean if (!WI.IsSigned && IsSigned) ? I guess it's an equivalent check. And it is also equivalent to unconditional

WI.IsSigned |= IsSigned;

[sdesmalen]

Hi @mkazantsev, thanks for having a look at this patch!

In D112573#3099600, @mkazantsev wrote:

If I understand your proposal correctly, you propose to replace scheme "take signedness from 1st user which is non-deterministically selected" with scheme "if at least one user of widest type is signed cast, widen as signed; otherwize widen as unsigned"?

Yes, that's right, I figured that consistently choosing one over the other at least removes the non-determinism.

In general, it makes sense to me and it also seems to solve the non-determinism you are describing. The only concern I have is, you use signed widening as default (and unsigned is possible under stricter conditions). On the other hand, IV tries hard to turn all icmp's to unsigned predicate form, preferring unsigned as default. This creates some discord between different parts of it.

I guess it's possible to favour unsigned as the default, but the specific example in the test doesn't optimise as well when choosing unsigned, because we end up with 2 induction variables in the loop instead of 1. For one critical loop that I investigated, this led to multiple redundant sign-extends.
This code is not very familiar to me though, so if you can give me some hints on how to make IndVarSimplify handle the unsigned case, I'd be happy to look into that!

[mkazantsev]

This is strange. From what I'm seeing, your IV starts from 1 and is just trivially positive, so there should not be any troubles with using zext. Could you please post a separate review with the unsigned version & its generated checks for this test?

[sdesmalen]

Removed control flow in favor of WI.IsSigned |= IsSigned;

[sdesmalen]

In D112573#3117336, @mkazantsev wrote:

This is strange. From what I'm seeing, your IV starts from 1 and is just trivially positive, so there should not be any troubles with using zext. Could you please post a separate review with the unsigned version & its generated checks for this test?

I've posted the unsigned version in D113516.

[reames]

Surely this causes some test diff in the existing test corpus? It looks like the review is incomplete. (Or I'm simply very surprised.)

Under the assumption the diff is incomplete, I'd suggest a slightly more complicate heuristic. Pick signed or unsigned based on which we see more of. Simply keep two counters, pick the larger, and tie break when equal towards sign.

If there actually no other diffs, you can ignore previous. I just find that slightly hard to believe. :)

[sdesmalen]

In D112573#3127843, @reames wrote:

Surely this causes some test diff in the existing test corpus? It looks like the review is incomplete. (Or I'm simply very surprised.)

The patch is actually complete, it's indeed very surprising that no other tests fail (I've built for all targets and ran make check-all).
Consistently choosing signed (this patch) causes no other tests to fail. Consistently choosing unsigned causes only one other test to fail (D113516).

[reames]

LGTM. We can revisit more complicate heuristics when we have evidence it matters.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

static void visitIVCast(CastInst *Cast, WideIVInfo &WI,
   // induction variable when necessary.
   if (TTI &&
       TTI->getArithmeticInstrCost(Instruction::Add, Ty) >
           TTI->getArithmeticInstrCost(Instruction::Add,
                                       Cast->getOperand(0)->getType())) {
     return;
   }
 
-  if (!WI.WidestNativeType) {
+  if (!WI.WidestNativeType ||
+      Width > SE->getTypeSizeInBits(WI.WidestNativeType)) {
     WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);
     WI.IsSigned = IsSigned;
     return;
   }
 
-  // We extend the IV to satisfy the sign of its first user, arbitrarily.
-  if (WI.IsSigned != IsSigned)
-    return;
-
-  if (Width > SE->getTypeSizeInBits(WI.WidestNativeType))
-    WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);
+  // We extend the IV to satisfy the sign of its user(s), or 'signed'
+  // if there are multiple users with both sign- and zero extensions,
+  // in order not to introduce nondeterministic behaviour based on the
+  // unspecified order of a PHI nodes' users-iterator.
+  if (WI.IsSigned != IsSigned && IsSigned)
+    WI.IsSigned = true;
 }
 
 //===----------------------------------------------------------------------===//
 //  Live IV Reduction - Minimize IVs live across the loop.
 //===----------------------------------------------------------------------===//
 
 //===----------------------------------------------------------------------===//
 //  Simplification of IV users based on SCEV evaluation.

llvm/test/Transforms/IndVarSimplify/deterministic-sign.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt "-passes=loop-rotate,indvars" -S < %s | FileCheck %s
+; RUN: opt "-passes=loop-rotate" < %s | opt "-passes=indvars" -S - | FileCheck %s
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-unknown-linux-gnu"
+
+define dso_local float @foo(float* noalias %dst, float* %src, i32 %offset, i32 %N) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 1, [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_COND_CLEANUP:%.*]]
+; CHECK:       for.body.lr.ph:
+; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[OFFSET:%.*]] to i64
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.for.cond.cleanup_crit_edge:
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret float undef
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 1, [[FOR_BODY_LR_PH]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[INDVARS_IV]], [[TMP0]]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds float, float* [[SRC:%.*]], i64 [[TMP1]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load float, float* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i64 [[TMP1]], 1
+; CHECK-NEXT:    [[ARRAYIDX3:%.*]] = getelementptr inbounds float, float* [[SRC]], i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP4:%.*]] = load float, float* [[ARRAYIDX3]], align 4
+; CHECK-NEXT:    [[ADD4:%.*]] = fadd fast float [[TMP2]], [[TMP4]]
+; CHECK-NEXT:    [[ARRAYIDX6:%.*]] = getelementptr inbounds float, float* [[DST:%.*]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store float [[ADD4]], float* [[ARRAYIDX6]], align 4
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_COND_FOR_COND_CLEANUP_CRIT_EDGE:%.*]], !llvm.loop [[LOOP0:![0-9]+]]
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %i.0 = phi i32 [ 1, %entry ], [ %inc, %for.body ]
+  %cmp = icmp slt i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  ret float undef
+
+for.body:                                         ; preds = %for.cond
+  %add = add nsw i32 %i.0, %offset
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds float, float* %src, i64 %idxprom
+  %0 = load float, float* %arrayidx, align 4
+  %add1 = add nsw i32 %add, 1
+  %idxprom2 = sext i32 %add1 to i64
+  %arrayidx3 = getelementptr inbounds float, float* %src, i64 %idxprom2
+  %1 = load float, float* %arrayidx3, align 4
+  %add4 = fadd fast float %0, %1
+  %idxprom5 = zext i32 %i.0 to i64
+  %arrayidx6 = getelementptr inbounds float, float* %dst, i64 %idxprom5
+  store float %add4, float* %arrayidx6, align 4
+  %inc = add nuw nsw i32 %i.0, 1
+  br label %for.cond, !llvm.loop !1
+}
+
+!1 = distinct !{!1, !2}
+!2 = !{!"llvm.loop.mustprogress"}