Any thoughts on the approach here? Is the !isOpaque() ? getElementType() : nullptr pattern something we should add a helper function for? Not sure how common this is going to be outside these cast transforms.

Use getWithSamePointeeType().

@efriedma LICM still uses AST for scalar promotion.

In D104652#2830796, @aeubanks wrote:

lgtm

what about GEP constants? do we need to do something special for those in ValueEnumerator?

LGTM

Update comment.

LGTM, but please drop the "use poison instead of undef" comments -- I don't think using poison instead of undef for dead code requires any explicit justification.

Remove outdated comment.

Remove obsolete unroll count clamp.

I have a general policy question here: Do we care about miscompiles that are caused by undef, but not poison? This makes a difference for transforms like these, e.g. no freeze is required if the condition is first in a logical or (or at any position in bitwise or) if we only care about poison.

Rebase, and only consider TripCount for all exits, leave TripMultiple alone for now to minimize impact.

No longer needed, UnrollLoop() is no longer passed TripCount/TripMultiple for a specific exit.

What do you think about this variant? It prints information for all exits as debug output, but keeps optimization remarks basic.

In D104482#2827398, @reames wrote:

I think I would prefer to see the information for each exit as opposed to removing it entirely. When understanding why unrolling happened in a particular way, having the detailed information is often very helpful. Not a strong preference, I'm willing to LGTM this if you really object.

Not seeing any compile-time impact, and rebased versions still looks good.

LGTM

Compile-time with the reference invalidation issue fixed: https://llvm-compile-time-tracker.com/compare.php?from=b5c4fc0f232b6368bbd7cd8681a6931f2c30ad02&to=9bb9b602fd58e6fdd353cdfedec56980a40230c1&stat=instructions Impact is small and without outliers. I think this is as cheap as it gets :)

Still crashing, here's the backtrace:

ld: /home/nikic/llvm-project/llvm/include/llvm/Support/Casting.h:104: static bool llvm::isa_impl_cl<To, const From*>::doit(const From*) [with To = llvm::Constant; From = llvm::Value]: Assertion `Val && "isa<> used on a null pointer"' failed.

Fix comment typos.

It looks like the new implementation causes a segfault while building 7zip using the ReleaseLTO-g configuration: https://llvm-compile-time-tracker.com/show_error.php?commit=77e65ca9acb9db4de64a1ff8002f1d53470a0de3

In D102615#2824088, @mkazantsev wrote:

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.

In D102615#2824097, @mkazantsev wrote:

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.

In D102615#2824000, @mkazantsev wrote:

Currently scheming a prototype to see if it works. My speculation is InstSimplify might be enough for my motivating example. However, this will require massive refactoring of InstSimplify itself (some of its static functions will need to be made publicly available). It's a lot of work just to duplicate a part of what SCEV does out of box.

In D102615#2818742, @mkazantsev wrote:

As for SCEV impact, some points.

1. Yes, I agree that we should try to reduce impact on compile time when we can;
2. We already have passes (IV simplify, IRCE, LSR...) where we already use SCEV. I'm absoultely certain that in reality, most things they do they could handle with InstSimplify-like instructions. But for some reason, we don't mind against the toll that SCEV takes there (and it should be HUGE in IV simplify) just because we started tracking compile time *after* these things were already there.
3. It's pretty clear to me that the problem is not in loop deletion that is slow with SCEV. The problem is that the SCEV is slow. And it's much slower than 0.2% that we see here. Holding away future optimizations just because SCEV is, and always has been, slow, doesn't seem right to me.

In D104203#2820498, @reames wrote:

I think there's a problem with this code, but I'm surprised the existing test didn't catch it. Have you run this with explicit dom tree and loop info validation enabled?

Here's the problem I think I see. If we have an exit block which exits only on iteration X, and we unroll by count Y where Y > X, I believe we'll end up making the exit block unreachable. (This can't happen if there's only a single exit since that exit must be reached.) The problem with an unreachable exit is that there can be arbitrarily complicated loops reachable only through that path, and updating loop info in that case is hard. Am I missing something here?

As a drive-by note, it would be great if you could expand LangRef on non-integral pointers a bit. It made sense to me when it specified that you can't use ptrtoint on a non-integral pointer, but without that limitation, it's not really clear to me what the actual difference between a non-integral pointer and a normal one is. What transforms are you not allowed to perform on a non-integral pointer that you can perform on a normal one?

@bjope This SimplifyCFG patch allows us to remove the assume dropping code in CGP subsequently.

LGTM

In D102615#2804481, @mkazantsev wrote:

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.

I'm also sceptical about the approach that we are following (cripple the opts to save compile time). I'd rather prefer it to be isKnownPredicateAt, maybe under a flag, to use as much power as it can.

If the SCEV's CT impact is still unacceptable, we can cripple it even further to use isKnownViaNonRecursiveReasoning, but basically in this case we can just go with -O0 and stay happy about the results.

LGTM, thanks!

Looks like phase ordering tests need an update.

There's a minor compile-time impact for this refactoring: https://llvm-compile-time-tracker.com/compare.php?from=57006d2f6d96d8a6836ae901218ed615071b3b8e&to=eca6ad2e31d754420fb114872bfc4060a698155e&stat=instructions It's okay, but you might want to cut down on the number of repeated/redundant getNotSCEV operations you perform. (They're not cached and known to be somewhat expensive.)

It seems like the addition of this patch has been somewhat botched by adding it only to the NewPM pipeline -- for no clear reason I can discern. This was at a time where barely anyone (outside Google) was using the NewPM, which means that this received very little evaluation from other parties. Now people are hitting this as part of the LegacyPM -> NewPM migration instead, which really shouldn't be the case.

In D103834#2810908, @bjope wrote:

Sorry, I used wrong example in the link. I've changed it to something where I do "i += n" instead of "i += n/2".

Is perhaps the problem that "i += n" might overflow (UB) and thereby we can't guarantee "must progress"?

In D103834#2810849, @bjope wrote:

One thing that might cause problems here is that it seems like getting the MustProgress attribute on a Function is quite hard. It is basically inferred by having WillReturn on the Function, and afaict the WillReturn attribute is never inferred if the Functions contain loops.

In the godbolt example above the Function has no MustProgress attribute, however the loop has a MustProgress attribute. So maybe loopIsFiniteByAssumption should check if the loop has MustProgress as well?

LGTM

LGTM

It looks like a different fix is being pursued, so marking this as changes requested to move it off the review queue.

While it may make sense to address this in JumpThreading in addition, I believe InstSimplify is intended to be robust against unreachable code. As InstSimplify can thread over phis, I don't think it's even possible for a caller to reliably prevent unreachable code from reaching InstSimplify.

In D101722#2806912, @efriedma wrote:

If I'm understanding correctly, the issue you're describing is that if %len is ULONG_MAX in the following loop, on trunk LLVM, the backedge-taken count comes out to zero.

Per above comment

LGTM

Okay, I think the change is not right after all. In particular, if we have an exit count like ((1 + %len) /u 2) that does represent the right exit count in arbitrary precision (via either exit or executed UB), but the expression for calculating the exit count itself may still overflow. If %len is UINT_MAX then the resulting exit count would be 0, while it should be UINT_MAX/2 (which is the iteration at which UB occurs). That's clearly not right.

LGTM

After looking through the tests, why does this need to use SCEV at all? As far as I can tell, simply using InstSimplify would be sufficient to prove all these cases (or just ConstFold for that matter). Without isKnownPredicateAt(), where symbolic reasoning is necessary, SCEV doesn't seem to provide much value here, or at least it's not obvious from the tests. (Of course, there will be cases where it can do more, but the converse also holds -- in particular, InstSimplify/ConstFold support arbitrary instructions, no need to special-case a limited set of them.)

LGTM. I was going to suggest that you add a direct AA test, but apparently there is no way to write an empty phi in textual LLVM IR, at least not that I can see. Weird limitation.