LG. Note that umin/smin support is also missing from GetMinTrailingZerosImpl.

The implementation looks correct to me. As @lebedev.ri mentioned we usually add exhaustive tests for ConstantRange methods nowadays. I'm not totally sure what should be tested here... I guess we should test a) conservative correctness (no wrong results produced) and b) tight bounds if the input sets are non-wrapping/non-sign-wrapping.

Can you please split off the ConstantRange addition into a separate revision?

@atrick That invariant doesn't exist currently. If a SmallDenseMap with less than InlineBuckets elements is compacted, it will change to the large rep (with an allocation). After this change it will instead stay in the small rep (without an allocation).

ConstantRange has (efficient) overflow detection for most cases now, but signedMulMayOverflow() is still missing. We could add that and then replace makeGNWR uses.

@lebedev.ri Thanks! The problem here is that for these test cases CVP will convert the with.overflow intrinsic to a simple add/sub/mul together with insertvalue instructions. LVI can't see through extractvalue of insertvalue, which is why the followup optimization on the condition does not trigger (it would only happen on the next run). I'll look into fixing this.

IMHO this should land as-is, and setcc folds can be implemented additionally if there are other places where they would be useful. My rationale would be that it is better to directly perform a simpler lowering than a complex lowering that then gets optimized. (Basically: If you can reduce the size of the implementing code and get a better result, then I think we should always be doing that.)

@lebedev.ri I believe I implemented something equivalent in the meantime, see https://github.com/llvm/llvm-project/blob/688183ec54482666e4faa6b6e1a83fe3ccc9372d/llvm/lib/Analysis/LazyValueInfo.cpp#L1099-L1105.

LGTM

As mentioned on the previous review, do we need to handle getelementptr inbounds {}, {}* %p, i32 %idx? That is, an inbounds GEP on a zero-sized type, which may be null for a non-zero index. It looks like this case is not handled in the existing code either though, so possibly this construction isn't legal (though I don't see anything to that effect in langref)?

makeGuaranteedNoWrapRegion() cannot be used to constrain input ranges. E.g. consider that the RHS is [UINT_MAX-1, UINT_MAX]. Then the GWNR is just [0, 0], even though 1 would be a legal value for LHS (assuming the RHS is UINT_MAX-1).

@lebedev.ri CVP can already determine that the condition is always true:

This documentation should probably be combined with the introduction of the requires_forward_progress attribute. The current codebase in not consistent in this regard (e.g. we have code in LoopDeletion specifically assuming no forward-progress requirement). It would be better to condition that kind of code on an attribute rather than drop it entirely and add it back later.

LGTM as a starting point.

Clarify that any synthetic side-effect is sufficient. Add llvm.sideeffect to infinite loop in phi example.

LGTM

In D65718#1613947, @lebedev.ri wrote:

I was under impression that the exact opposite was the status,
even if it wasn't consistently followed everywhere.

As we only have a handful of SPF_ABS uses, it might make sense to introduce a separate abs flavor for the nsw case (which would also allow to handle the x-y case more accurately). SPF_PABS? SPF_ABS_NSW?

Generate check lines.

I've reduced the test case to a more reasonable size now...

Also mark tTBB_JT and tTBH_JT as not duplicable.

Simplify testcase.

Remove isAssumeLikeIntrinsic handling, this is now handled by willreturn attributes on intrinsics.

LGTM

I'm not sure I understand the design/purpose of this utility. As far as I can see, the main benefit this has over a standard guaranteed-to-transfer loop is that it will be able to continue into a unique successor BB. As most must-exec uses I've seen (including your ArgPromotion example, as well as attribute deduction uses) are interested in instructions that must-exec from entry, this will not happen for non-degenerate CFGs (where BBs have not been merged).

I think this is something of a recurring pattern (not so much the and/or forms, but the original phi/select form), where we have select (x != C1), y, C2, where it turns out that y[x = C1] == C2 and thus the whole expression reduces to y (same with phi's). We might want to invest in a general solution to this problem. Something along the lines of finding this kind of pattern, then checking y backwards for uses of x (to a small depth) and if we find them, replace x with C1, run InstSimplify over it and see if it reduces to C2 in the end.

LGTM

LGTM

There's some code related to this in GVN: https://github.com/llvm-mirror/llvm/blob/6c33c8991a6740ed8c87d5d3980a6469b415628d/lib/Transforms/Scalar/GVN.cpp#L333-L342 However it only works if an appropriate extractelement already exists.

Maybe this could be put behind a flag and only used in the few instances where it is needed?

I'm not sure I see the value in this change in either implementation. Changing block names seem to be a pretty niche issue (haven't ever run into this myself) and I don't think handling them in update_test_checks is worth the churn it will cause.

Rebase over baseline tests.

In the meantime additional users of isAssumeLikeIntrinsic() have been added, so I've switched this to call isAssumeLikeIntrinsic() from isGuaranteedToTransferExecutionToSuccessor() instead. Does this still look good?

Rebase.

Looks like this never landed...

These tests are already present higher up in the file. The transform you have in mind is unsound due to undef, see D63060.

In D64523#1583624, @vporpo wrote:

I guess it would be better if it visited all the BBs. You could traverse the VectorizableTree once and collect the BBs to be visited before you walk through them. Btw the TreeEntries now have operands, which can help you collect the BBs in the right order.

LGTM