Returned integer type check of branch conditions, removed test TODOs, removed null TTI with non-null DT which looks extremely fishy.

Per underlying patch change

Per underlying patch change

Reworked using InstSimplify. It's good enough for my case. Let's hope that at least this has acceptable CT overhead.

Then trying InstSimplify...

:(

Oh, thanks! Didn't notice that. I'll now try to prototype an alternative solution with InstSimplify. But honestly, I'd be super surprised if SCEV's non-recursive prove is more expensive than this (and clearly SCEV's canonicalization is more powerful).

This is surprising to me -- why does this require changes to InstSimplify?

InstSimplify does not provide public API for this:

const SCEV *LHSS = getSCEVOnFirstIteration(LHS, L, SE, FirstIterSCEV);
const SCEV *RHSS = getSCEVOnFirstIteration(RHS, L, SE, FirstIterSCEV);
S = SE.getAddExpr(LHSS, RHSS);

It has SimplifyAddInst that works with custom arguments, but it's currently static within the cpp file. I'd need to expose all of them. At least this, maybe more.

Cut down to non-recursive reasoning. @nikic could you please check the CT impact? If it's now, then it's all about complex recursive rules of proof, and this is where we can seek to simplify SCEV's reasoning.

@reames

One thing I'm wondering about is whether we're invalidating SCEV too aggressively in one of the existing transforms. I don't have strong evidence of this, but computing SCEVs for a loop isn't *that* expensive, and given a properly structured loop pipeline should happen approximately once. I'd be tempted to instrument the various "forgetX" calls and run one of the worst offenders compile time wise. Do all of the invalidation make sense? Just based on a quick skim of the code, I see a couple call sites in LoopSimplifyCFG and IndVarSimplify which look likely to invalidate far more than is required. In particular, if we were invalidating multiple times in a loop nest, that could cause degenerate compile time.

+1 to what Eli said.

P.S. and as for SCCP - that's a good point I didn't think of. Need to make some experiments to see if it helps.

Reducing my whole suggestion to absurd, if I win 0.2% CT somewhere else in SCEV, can we go with this?

Thanks Nikita, I think I have some arguments for this philosophical debate. :)

Looks fine, but agreed with Eli. Please don't land it for some more days to find and fix miscompiles from underlying patches (if any).

LGTM, but I think we can remove more copy-paste (see comment). Can go as follow-up.

I'm a bit surprised that it wasn't reverted. The default policy is revert whatever is broken and then fix it. We have numerous internal failures & broken CI cycles because of this, and the fix is not merged yet (and not clear when it will be merged). @Carrot could you please revert this and return back along with fix?

Please add tests for this this exit doesn't dominate the latch.

So it's not a singleton, it's something that is cached inside of GCModuleInfo. And this patch preserves this behavior. You can as well say that SCEV constant 1 of type i32 is a singleton, but it's not: it is something that is cached within a particular instance of ScalarEvolution.

Good point, I was not aware that the flags need to apply for any order of evaluation

For nuw it should be fine. LGTM!

I confirm that the initial miscompile we found gets fixed by this patch. I can't approve the patch because I'm not familiar with the component though.

As far as I understand what is a nsw for multi-argument add, it means that there should be no wrap in between if we add the operands one by one in any order. Imagine the case when a = c = SINT_MIN and b = d = SINT_MAX. We can say that a+b has <nsw>, c+d has <nsw>, and (a+b) + (c+d) also has nsw. But if we say that getAddExpr(getAddExpr(a, b, nsw), getAddExpr(c, d, nsw), nsw) = getAddExpr(a, b, c, d, nsw), it's not true if we compute the latter as a + c + b + d. It will overflow on a + c already. Is my understanding wrong here?

In D101970#2805039, @lebedev.ri wrote:

In D101970#2804705, @mkazantsev wrote:

We are still observing a miscompile caused by the newer version of this patch. I'll try to provide you a repro.

Surely you can provide the .ll after middle-end optimizations?

Filed https://bugs.llvm.org/show_bug.cgi?id=50615. The original repro is in Java, but I hope the logs there are enough to figure out what's going on. The log shows that the described transform did apply.

We are still observing a miscompile caused by the newer version of this patch. I'll try to provide you a repro.

SCEV is much more powerful in terms of simplification. Imagine the situation when some Phi takes value of a + b + c on the 1st iteration (and unknown on all others), then gets subtracted by a, then by b, and then by c, and then the result is compared against zero. If we want InstSimplify to do something like this, we will need to re-implement recrusive expression aggregation, simplification, in summary - we will need to re-invent SCEV.

My fuzzer didn't reveal any new failures, so there is a chance it's working as expected. :) LGTM with some nits.

I'm getting incline towards accepting this, but the fact that you keep finding bugs worries me. Please give me some time, I will run a corpus of Fuzzer tests with this pass locally to see if something breaks. If yes, I will try to give you a reproducer.

Fine by me if you add a unit test which shows that it works as expected with volatile load.

Can we go ahead and merge it, or you want to further reduce the CT impact?

All failures so far were related to irreducible CFG (which made RPOT meaningless), which is now completely ruled out. @stefanp could you please check that this version works ok with PowerPC?

Looking much better now. Few more nits & a question regarding ne, which is a potential correctness concern.

Looks ok by me, but please make sure you address Philip's concerns.

Could you please mark it as "changes planned" until the underlying patch is ready or merged?

Looks legit, thanks!

In D102615#2790558, @xbolva00 wrote:

In D102615#2790544, @mkazantsev wrote:

In D102615#2790190, @xbolva00 wrote:

In D102615#2789636, @mkazantsev wrote:

In D102615#2788964, @xbolva00 wrote:

What are the latest compile time data for this patch?

There have been several separate follow-ups to address the compile time, but I believe we never measured it all together.

Could we get new data? @nikic? I am not sure if followups were not reverted as well so if follow up patches can recommited as NFC(I) patches, it would be great.

The followups were all reverted and integrated into this one. I see no point in merging them separately, unless we want more pain with reverts (if it is needed again). They are just part of the algorithm.

Nice, so only this patch needs to tested for compile time. But if less than +0.5%, it should be acceptable. There were many improvements in ct, so I do think there is some space for less cheap optimizations.

In D102615#2790546, @mkazantsev wrote:

In D102615#2790191, @xbolva00 wrote:

In D102615#2778811, @xbolva00 wrote:

Can this patch optimize code from comment #4 in https://bugs.llvm.org/show_bug.cgi?id=47491 ?

Btw, any comment?

Let me check.

In D102615#2790191, @xbolva00 wrote:

In D102615#2778811, @xbolva00 wrote:

Can this patch optimize code from comment #4 in https://bugs.llvm.org/show_bug.cgi?id=47491 ?

Btw, any comment?

In D102615#2790190, @xbolva00 wrote:

In D102615#2789636, @mkazantsev wrote:

In D102615#2788964, @xbolva00 wrote:

What are the latest compile time data for this patch?

There have been several separate follow-ups to address the compile time, but I believe we never measured it all together.

Could we get new data? @nikic? I am not sure if followups were not reverted as well so if follow up patches can recommited as NFC(I) patches, it would be great.

Did you try a lightweight (and absolutely NFCish) approach of dropping SCEV 1 time instead of 2? Like

if (!BO->hasNoUnsignedWrap() &&
    willNotOverflow(SE, BO->getOpcode(), /* Signed */ false, LHS, RHS)) {
  BO->setHasNoUnsignedWrap();
  Changed = true;
}

Root cause: another case of irreducible CFG I didn't filter out. As result, RPOT makes no sense. Checked in failing unit test as https://reviews.llvm.org/rG4ef47eaed952. Added an assert decting this.

Thanks, I was able to reproduce the failure locally. Investigating.

In D102615#2788964, @xbolva00 wrote:

What are the latest compile time data for this patch?

Oh I see... That's nasty. In this case, could you please help me to reproduce it? I wasn't able to find the sources of this test in LLVM repository. IR dump before Loop Deletion would work too.

So far it seems that all problems are caused by compile time increase. There is already no room for shrinking the scope, so I'm returning this with option (turned off by default).

The last failure also looks like a timeout, I don't see any indication of miscompile:

FAIL: test-suite :: MultiSource/Benchmarks/MallocBench/gs/gs.test (73 of 2021)
******************** TEST 'test-suite :: MultiSource/Benchmarks/MallocBench/gs/gs.test' FAILED ********************

Reviewing the failures, I see several issues that might be relevant:

Thanks for the revert! I'll see into what's happening.

@nikic could you please run this one too? I think it can be useful in real cases with countable loops.

Added one more early bailout:

commit 7d418dadf6b1e6fd9bcccf7c5b5e1db74992ee70 (HEAD -> main, origin/main)
Author: Max Kazantsev <mkazantsev@azul.com>
Date:   Thu May 27 15:18:30 2021 +0700

Thanks! I'll see what else can be done. Though, I think the right solution is to speed up SCEV queries in general and not try to cripple particular opts.

@nikic could you please evaluate impact of 2 patches above? They should do a great deal of decreasing SCEV usage.

This should also help:

commit 51d334a845a082338735b0fdfc620a4b15fa26fe (HEAD -> main, origin/main)
Author: Max Kazantsev <mkazantsev@azul.com>
Date:   Thu May 27 13:20:57 2021 +0700

One step to improve the situation:

commit b0b2bf3b5da950679db1431aae431a6dedea2245 (HEAD -> main, origin/main)
Author: Max Kazantsev <mkazantsev@azul.com>
Date:   Thu May 27 11:47:30 2021 +0700

The best solution I can come up with (and it is something I even started to do at some point) is to replace two queries to isKnownPredicate with one which returns Optional<bool>, that should give up to 2x CT improvement. I'll think if we can get some minor CT wins here.

LGTM, but mind that maybe we'll have to downgrade isKnownPredicateAt to isKnownPredicate if it harms the CT.

Commited fixed version (this time right one). Let's see how it goes.

Yes, the point is, RPOT (or any other traversal) is undefined for any cycles, should they be inner loops or contained non-loop cycles. I think the best is not to deal with them at all. It never ended well for any opt. :)

Correctness of Loop RPOT is crucial for the correctness of this transform. If it's broken, its user is also broken. I see no good reason why RPOT for this loop is (bb2, bb12, bb4) and not (bb2, bb4, bb12). If someone has an idea, please let me know.

@uabelho you are right. The problem is loop RPOT processes blocks in order (bb2, bb12, bb4), which is not correct. The expected order is (bb2, bb4, bb12). No clue why this happened, investigating.

In D102615#2781346, @uabelho wrote:

In D102615#2781330, @mkazantsev wrote:

@uabelho Looking into your example, I don't think enough evidence it's a miscompile. Your test has non-side-effecting infinite loop, which has undefined behavior. So it's legal to make the replacement. Can you construct the example without an infinite loop?

Hm, is it really? For input 1, 1, 0 I think it terminates and return the value 20 after executing this path:

entry -> if.end -> bb2 -> bb4 -> bb12 -> bb2 -> bb4 ->bb13 -> ret

?