[SCEVExpander] Try to create ASHR instr for expanded SCEV expr.

[fhahn]

Summary

ec54867df5e7 updated SCEV to epxand ASHR instructions to an
equivalent SCEV expression. This has the side effect that expanding
expressions based on ASHR instructions now expand to substantially
larger IR than before, which means the IndVarSimplify for example can
add a substantial amount of extra instructions when re-writing exit
conditions. This is causing ~5% regressions in some Geekbench
benchmarks.

This patch tries to match the SCEV expression created for ASHR during
expansion and emit an ASHR instruction directly. Note that currently
this pattern is not completely correct, because we have no way of
differentiating exact and non-exact UDivs in SCEV (see
the no_ashr_due_to_missing_exact_udiv test case, which generates ashr
incorrectly)! This needs to be resolved first and I'd appreciate any
feedback on the preferred direction.

Should we just add a flag to SCEVUDivExpr? Or mark UDivs as exact in a
separate table?

Note that there are other places using SCEVExpander where this likely
pessimizes the generated IR, e.g. when generating runtime checks for LV.

[nikic]

Should we just add a flag to SCEVUDivExpr? Or mark UDivs as exact in a
separate table?

Due to SCEV unification, it is not possible to transfer poison-generating flags from IR to SCEV expressions, without proving that a poison result would always cause UB in any scope for which the SCEV expression is valid. For non-addrecs this is only possible in very narrow situations (instruction in loop header, based on addrec in that loop, poison causes UB), so it's not really useful in this situation. Certainly wouldn't cover your examples.

I would recommend reverting rGec54867df5e7f20e12146e628af34f0384308bcb.

[xbolva00]

revert

+1

[fhahn]

In D100721#2697174, @nikic wrote:

Should we just add a flag to SCEVUDivExpr? Or mark UDivs as exact in a
separate table?

Due to SCEV unification, it is not possible to transfer poison-generating flags from IR to SCEV expressions, without proving that a poison result would always cause UB in any scope for which the SCEV expression is valid. For non-addrecs this is only possible in very narrow situations (instruction in loop header, based on addrec in that loop, poison causes UB), so it's not really useful in this situation. Certainly wouldn't cover your examples.

In the examples, wouldn't overflow of the ASHR be UB in all scopes, as each path from the ashr to the exit needs to go through a branch which compares the result of the ashr? (ignoring fact that branch on undef/poison is not yet considered UB by ValueTracking)

I would recommend reverting rGec54867df5e7f20e12146e628af34f0384308bcb.

That's certainly a good way forward for now IMO, as I definitely agree that the improved modeling would be a lot of work and even then it is not clear how feasible this would be for real-world cases.

@ebedev.ri Given that ec54867df5e7 can have a noticeable negative impact on performance, WDYT about a revert?

[lebedev.ri]

In D100721#2697176, @xbolva00 wrote:

revert

+1

If you don't mind me asking, i forgot when was the last time
i have seen any (coherent?) message longer than two phrases from you;
all recent comments are simply non-comments flippantly reiterating
the last point made in whatever thread.
What's up with that?

In D100721#2697197, @fhahn wrote:

In D100721#2697174, @nikic wrote:

I would recommend reverting rGec54867df5e7f20e12146e628af34f0384308bcb.

That's certainly a good way forward for now IMO, as I definitely agree that the improved modeling would be a lot of work and even then it is not clear how feasible this would be for real-world cases.

@lebedev.ri Given that ec54867df5e7 can have a noticeable negative impact on performance, WDYT about a revert?

Hmm, so the problem is that we *can't* reconstruct ashr/ashr exact from it's SCEV model:

$ ./alive-tv /tmp/test.ll --bidirectional

----------------------------------------
define i8 @src(i8 %x) {
%0:
  %r = ashr exact i8 %x, 4
  ret i8 %r
}
=>
define i8 @tgt(i8 %x) {
%0:
  %abs_x = abs i8 %x, 0
  %div = udiv exact i8 %abs_x, 16
  %t0 = smax i8 %x, 255
  %t1 = smin i8 %t0, 1
  %r = mul nsw i8 %div, %t1
  ret i8 %r
}
Transformation seems to be correct!

These functions seem to be equivalent!

$ ./alive-tv /tmp/test.ll --bidirectional

----------------------------------------
define i8 @src(i8 %x) {
%0:
  %abs_x = abs i8 %x, 0
  %div = udiv i8 %abs_x, 16
  %t0 = smax i8 %x, 255
  %t1 = smin i8 %t0, 1
  %r = mul nsw i8 %div, %t1
  ret i8 %r
}
=>
define i8 @tgt(i8 %x) {
%0:
  %r = ashr i8 %x, 4
  ret i8 %r
}
Transformation doesn't verify!

ERROR: Value mismatch

Example:
i8 %x = #xc8 (200, -56)

Source:
i8 %abs_x = #x38 (56)
i8 %div = #x03 (3)
i8 %t0 = #xff (255, -1)
i8 %t1 = #xff (255, -1)
i8 %r = #xfd (253, -3)

Target:
i8 %r = #xfc (252, -4)
Source value: #xfd (253, -3)
Target value: #xfc (252, -4)

I don't recall my thoughts on that back then, but it's clearly bad.
That being said we really should model ashr exact in SCEV,
that comes up all the time you want to compute the distance between to pointers e.g.

So i'll revert for now, thanks!

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

828–829

i think this matcher should be ,

[xbolva00]

If you don't mind me asking, i forgot when was the last time
i have seen any (coherent?) message longer than two phrases from you;

1. Here I just agree with Florian and Nikita. Florian shared good motivation for revert (regressions and pessimized IR) and I think the revert is reasonable solution (as the problem is not so easy to solve other way), so my "+1".

2. Please avoid words like these. Really. Last warning.

I would accept if you said "hey, you wrote +1 but why do you think so? Same concerns like florian or nikita or something else?" as a productive criticism but now it looks like an aggressive tone from you.

• We have a freedom of speech and my comment "+1" cannot offend you.

all recent comments are simply non-comments flippantly reiterating the last point made in whatever thread.

Stop lying - https://reviews.llvm.org/p/xbolva00/.

Bluh, and are you stalking me and checking all my comments? Do you count number of sentences in my messages on phab? Why do you even judge my messages on Phab?

I dont think my comments are somehow bad or inappropriate, others can check them:
https://reviews.llvm.org/p/xbolva00/

[lebedev.ri]

Casual reminder that english isn't everyone's native language,
and tone/intent doesn't translate well.

In D100721#2697234, @xbolva00 wrote:

If you don't mind me asking, i forgot when was the last time
i have seen any (coherent?) message longer than two phrases from you;

1. Here I just agree with Florian and Nikita. Florian shared good motivation for revert (regressions and pessimized IR) and I think the revert is reasonable solution (as the problem is not so easy to solve other way), so my "+1".

2. Please avoid words like these. Really. Last warning.

I would accept if you said "hey, you wrote +1 but why do you think so? Same concerns like florian or nikita or something else?" as a productive criticism but now it looks like an aggressive tone from you.

Hm, how was that aggressive? I may be missing context here.

• We have a freedom of speech and my comment "+1" cannot offend you.

Please do not tell other what can and what can not offend them.

• And are you stalking me? Do you count number of sentences in my messages on phab? Why do you judge my messages on Phab?

*You*? Nope.
All mails to -commits/-dev - yep, absolutely, simply because i read those emails.

I guess we may have different definitions for the word "judge" here,
because i'm not casting a judgment on *you*, the person,
i'm only being a bit vary of the review feedback posted.

all recent comments are simply non-comments flippantly reiterating the last point made in whatever thread.

Stop lying - https://reviews.llvm.org/p/xbolva00/.

Again, i haven't actually gone and reread every comment,
i'm simply voicing my potentially-faulty observation from the reviews i have seen.

Bluh, and are you stalking me and checking all my comments? Do you count number of sentences in my messages on phab? Why do you even judge my messages on Phab?

I dont think my comments are somehow bad or inappropriate, others can check it:
https://reviews.llvm.org/p/xbolva00/

Again, i never said that. I only said that they mostly only reiterate the last point made, but not frequently make a new point.

[xbolva00]

Again, i never said that. I only said that they mostly only reiterate the last point made, but not frequently make a new point.

Sorry, but.... is it wrong? Am I breaking some community rules? If so, tell me, if not, then ... :)

Is it bad to respond on new comments or new patch revisions? No, I consider it OK. Is there any problem that I do "not frequently make a new point"? I dont think so. I comment what I want. I can ask (nobody is obligatory to answer me), I can request some change in a patch and also it is fine to thank if my feedback was addressed. I can send one patch per day and also I can send one patch per year - OK too. We do (and some of us in our free time) what we can to improve this project.

Hm, how was that aggressive?

I took it something like "Your comments are well.. to be honest a trash. Usually few words/sentences, nothing new, just reaction on the last point on phab reviews. I cant remember anything good/new points from you".

[xbolva00]

Example of regression:

uint64_t sum(std::vector<uint64_t>& data){
    uint64_t total = 0;
    for (size_t i = 0, e = data.size(); i < e; i++) {
        total += data.at(i);
    }
    return total;
}

https://godbolt.org/z/zTMfazoao

[fhahn]

I'm dropping this for a bit, as the commit introducing the perf regression has been reverted for now.

[mkazantsev]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

813

I think there is a bug here for Abs->getOperand(0) == Abs->getOperand(1) == SINT_MIN.

[reames]

Pending action by author, please request review once ready for more discussion. Just getting this off my active review queue.

[fhahn]

I'm dropping this for a bit, as the commit introducing the perf regression has been reverted for now.

Abandoning for now.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) {
   }
 
   return Sum;
 }
 
 Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
 
+  auto IsSignumExpr = [](const SCEV *E, const SCEV *&X) {
+    auto *SMin = dyn_cast<SCEVSMinExpr>(E);
+    if (!SMin || !SMin->getOperand(0)->isOne())
+      return false;
+    auto SMax = dyn_cast<SCEVSMaxExpr>(SMin->getOperand(1));
+    if (!SMax)
+      return false;
+
+    auto *C = dyn_cast<SCEVConstant>(SMax->getOperand(0));
+    if (!C || !C->getValue()->isMinusOne())
+      return false;
+
+    X = SMax->getOperand(1);
+    return true;
+  };
+  auto IsDivAbs = [this](const SCEV *E, const SCEV *&X, int32_t &Amount) {
+    // FIXME: We need to match for `UDIV exact`, but that's not possible at
+    // the moment!
+    auto *Div = dyn_cast<SCEVUDivExpr>(E);
+    if (!Div)
+      return false;
+
+    auto *Abs = dyn_cast<SCEVSMaxExpr>(Div->getOperand(0));
+    if (!Abs || Abs->getOperand(0) != SE.getNegativeSCEV(Abs->getOperand(1)))
+      return false;
+    auto *AmtShifted = dyn_cast<SCEVConstant>(Div->getOperand(1));
+    if (!AmtShifted || !AmtShifted->getAPInt().isPowerOf2())
+      return false;
+    X = Abs->getOperand(1);
+    Amount = AmtShifted->getAPInt().exactLogBase2();
+    return true;
+  };
+  const SCEV *X1;
+  const SCEV *X2;
+  int32_t Amount;
+  // ASHR instructions are decomposed into a multiplication of a divide and
+  // signum expression, because there is no dedicated ASHR SCEV expression. Try
+  // to match the pattern and emit a ASHR instruction directly.
+  if (IsSignumExpr(S->getOperand(1), X1) &&
+      IsDivAbs(S->getOperand(0), X2, Amount) && X1 == X2)
+    return Builder.CreateAShr(expandCodeForImpl(X1, Ty, false),
+                              ConstantInt::get(Ty, Amount), "", true);
+
   // Collect all the mul operands in a loop, along with their associated loops.
   // Iterate in reverse so that constants are emitted last, all else equal.
   SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
   for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()),
        E(S->op_begin()); I != E; ++I)
     OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
 
   // Sort by loop. Use a stable sort so that constants follow non-constants.

llvm/test/Transforms/IndVarSimplify/ashr-expansion.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -indvars -S %s | FileCheck %s
 
 target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
 
 define float @ashr_expansion_valid(i64 %x, float* %ptr) {
 ; CHECK-LABEL: @ashr_expansion_valid(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[X:%.*]], i64 -1)
-; CHECK-NEXT:    [[SMIN:%.*]] = call i64 @llvm.smin.i64(i64 [[SMAX]], i64 1)
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i64 0, [[X]]
-; CHECK-NEXT:    [[SMAX1:%.*]] = call i64 @llvm.smax.i64(i64 [[X]], i64 [[TMP0]])
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[SMAX1]], 4
-; CHECK-NEXT:    [[TMP2:%.*]] = mul nsw i64 [[SMIN]], [[TMP1]]
-; CHECK-NEXT:    [[UMAX:%.*]] = call i64 @llvm.umax.i64(i64 [[TMP2]], i64 1)
+; CHECK-NEXT:    [[TMP0:%.*]] = ashr exact i64 [[X:%.*]], 4
+; CHECK-NEXT:    [[UMAX:%.*]] = call i64 @llvm.umax.i64(i64 [[TMP0]], i64 1)
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[RED:%.*]] = phi float [ 0.000000e+00, [[ENTRY]] ], [ [[RED_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr float, float* [[PTR:%.*]], i64 [[IV]]
 ; CHECK-NEXT:    [[LV:%.*]] = load float, float* [[GEP]], align 4
 ; CHECK-NEXT:    [[RED_NEXT]] = fadd float [[LV]], [[RED]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw i64 [[IV]], 1
exit:                                             ; preds = %bb135
   %lcssa.red.next = phi float [ %red.next, %loop ]
   ret float %lcssa.red.next
 }
 
 ; No explicit ashr, but a chain of operations that can be replaced by ashr.
 define float @ashr_equivalent_expansion(i64 %x, float* %ptr) {
 ; CHECK-LABEL: @ashr_equivalent_expansion(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[ABS_X:%.*]] = call i64 @llvm.abs.i64(i64 [[X:%.*]], i1 false)
-; CHECK-NEXT:    [[T0:%.*]] = call i64 @llvm.smax.i64(i64 [[X]], i64 -1)
-; CHECK-NEXT:    [[T1:%.*]] = call i64 @llvm.smin.i64(i64 [[T0]], i64 1)
-; CHECK-NEXT:    [[TMP0:%.*]] = lshr i64 [[ABS_X]], 4
-; CHECK-NEXT:    [[TMP1:%.*]] = mul i64 [[T1]], [[TMP0]]
-; CHECK-NEXT:    [[UMAX:%.*]] = call i64 @llvm.umax.i64(i64 [[TMP1]], i64 1)
+; CHECK-NEXT:    [[TMP0:%.*]] = ashr exact i64 [[X:%.*]], 4
+; CHECK-NEXT:    [[UMAX:%.*]] = call i64 @llvm.umax.i64(i64 [[TMP0]], i64 1)
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[RED:%.*]] = phi float [ 0.000000e+00, [[ENTRY]] ], [ [[RED_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr float, float* [[PTR:%.*]], i64 [[IV]]
 ; CHECK-NEXT:    [[LV:%.*]] = load float, float* [[GEP]], align 4
 ; CHECK-NEXT:    [[RED_NEXT]] = fadd float [[LV]], [[RED]]
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw i64 [[IV]], 1
exit:                                             ; preds = %bb135
   ret float %lcssa.red.next
 }
 
 ; Chain of operations that *cannot* be replaced by ashr, because the udiv is
 ; missing exact.
 define float @no_ashr_due_to_missing_exact_udiv(i64 %x, float* %ptr) {
 ; CHECK-LABEL: @no_ashr_due_to_missing_exact_udiv(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[ABS_X:%.*]] = call i64 @llvm.abs.i64(i64 [[X:%.*]], i1 false)
-; CHECK-NEXT:    [[DIV:%.*]] = udiv i64 [[ABS_X]], 16
-; CHECK-NEXT:    [[T0:%.*]] = call i64 @llvm.smax.i64(i64 [[X]], i64 -1)
-; CHECK-NEXT:    [[T1:%.*]] = call i64 @llvm.smin.i64(i64 [[T0]], i64 1)
-; CHECK-NEXT:    [[TMP0:%.*]] = mul i64 [[T1]], [[DIV]]
+; CHECK-NEXT:    [[TMP0:%.*]] = ashr exact i64 [[X:%.*]], 4
 ; CHECK-NEXT:    [[UMAX:%.*]] = call i64 @llvm.umax.i64(i64 [[TMP0]], i64 1)
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[RED:%.*]] = phi float [ 0.000000e+00, [[ENTRY]] ], [ [[RED_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr float, float* [[PTR:%.*]], i64 [[IV]]
 ; CHECK-NEXT:    [[LV:%.*]] = load float, float* [[GEP]], align 4
 ; CHECK-NEXT:    [[RED_NEXT]] = fadd float [[LV]], [[RED]]