Rebased.

Addressed comments.

In D103700#2813906, @reames wrote:

@Ayal If I'm understanding you even partially correctly, it sounds like you're raising a code quality issue. That is, we may generate a dead epilogue loop (e.g. with a condition statically known to result in the epilogue being untaken, but emitted as a condition) when we didn't need to. Is that correct?

In D100257#2761910, @fhahn wrote:

@gilr I think your comments should be addressed and I am planning land this in the next few days, unless there are any additional comments :)

Thanks, I updated the code to turn VPUser in a virtual base class and added s subclass for the uses in VPBlockBase. WDYT?

Very nice step forward!!

In D100257#2726688, @fhahn wrote:

In D100257#2725036, @Ayal wrote:

In D100257#2725020, @fhahn wrote:

In D100257#2718728, @Ayal wrote:

Non-recipe "other" VPUsers are quite exceptional ... would it suffice to have (native) VPlan hold all 'dangling' non-recipe VPUsers of its VPBasicBlocks, as an alternative, until these are cleaned up?

The blocks need to use the VPUsers to access the current value they hold I think, so I am not sure how the VPlan holding the VPUsers would look like unfortunately. It would be great if you could elaborate in a bit more detail, in case I am missing something.

The blocks will still have their VPUsers (in native; until this gets cleaned up). The thought is that whoever needs to distinguish between a block'd VPUser and a recipe'd one, would do so by consulting VPlan, rather than isa-ing the VPUser.

Oh I see what you mean now, thanks! That sounds like a viable alternative.

IIUC we will have non-recipe users in the future (e.g. live-outs) so I think we need to be able to make this distinction in the future as well, once the current VPUsers in the native path get cleaned up. If that's true, I think having to consult a VPlan to check what type of user we are dealing with seems a bit clunky in the long term (and breaks with the common pattern used for other VP* classes and other places in LLVM). Unless we anticipate a more fine-grained distinction between VPUsers in the future, we could also just use a boolean flag instead of the enum, to make it less appealing to add new VPUser types.

If we don't anticipate having to distinguish between recipe and non-recipe VPUsers in the future, then I think using a map in the plan directly makes a lot of sense (and in that case we might want to get rid of the separate VPUser class completely?)

LGTM, thanks!

In D95383#2570973, @fhahn wrote:

ping :)

LGTM, thanks!

LGTM with a nit. Thanks!

Addressed comments.

In D95521#2533644, @fhahn wrote:

In D95521#2533414, @fhahn wrote:

I did some testing and it appears this exposes a crash in matchURem. I'm taking a look at that now, I think it would be good to wait with landing the change until this is resolved.

Should be fixed by f1e8136115ac

Addressed comments.

Rebased

Trying to apply Florian's suggestion in D95521 (only for powers of 2 as a first step). This handles the power-of-two case added by PR47904.

In D94088#2519311, @lebedev.ri wrote:

I would expect that the SCEV change could be testable with just the scev itselfs (-analyze -scalar-evolution), is it not?

ping

LGTM, with a nit. Thanks!

Should the (final) goal be to move the whole phi-trunc-cast logic from code-gen to vplanning phase?

In D93974#2494331, @jdoerfert wrote:

Oh.. this is bad. That happens if you mix two logically differnet things into a single instruction pointer.
I put it on the list of things that need to fixed wrt. assumes ... :(

In D93974#2493723, @jdoerfert wrote:

In D93974#2493646, @gilr wrote:

Yes, if isaAssumeIntrinsic stands for "is an assume or an ephemeral of an assume".

Why is anything but an llvm.assume a problem? (Sorry I have so many questions)

In D93974#2493403, @jdoerfert wrote:

In D93974#2493287, @gilr wrote:

In D93974#2492979, @jdoerfert wrote:

The idea is that you can always do what you do here in isValidAssumeForContext (and friends). I just checked and we seem to do so already. Could you explain to me why we need to go for the Last instruction in this patch at all? What would happen if you simply pick the first in the entry block, which is trivially correct. (Note: You can skip llvm.assume to make some weird problems go away).

The patch indeed defaults to the first instruction in the entry. Scanning to the end at safeCxtI() was an optimization for cases where the first instruction is an ephemeral value of an assume (which seems quite likely for assumes about arguments) that would get the assume discarded by the isEphemeralValueOf(Inv, CxtI) check. At isValidAssumeForContext() we can't distinguish between a context given only as a control-flow marker and a context that also guards against simplifying an ephemeral so we can't try to improve it there, but since any context safeCxtI() provides for a null CxtI is just a control-flow marker anyway we might as well choose one that's not an ephemeral of any assume in the entry block. Does that make sense?

Yes. But your code does "more" than that. All you want is this pseudo-code, right?

auto &It = EntryBlock.begin();
while (isaAssumeIntrinsic(*It)) ++It;
return *It;

In D93974#2492979, @jdoerfert wrote:

Ping :)

In D93974#2489195, @jdoerfert wrote:

FWIW, I agree with @nikic, we should not put this logic here. There are two problems:

1. We compute something we might not need.
2. We do it only in value tracking.

LGTM!

LGTM, with a nit.
(Seems reduction might be worth splitting widenPhiInstruction() and its own Recipe, but that's beyond the scope of this patch)
Thanks!

Rebased on top of 7ddbe0cb905ec62d37b284a2e8daf54887a35f94 (merge ..-assume-divisible-TC.ll into ..-divisible-TC.ll)

Addressed comments.

In D93974#2480270, @nikic wrote:

In D93974#2479403, @gilr wrote:

Sorry for the delay @nikic.

In D93974#2476165, @nikic wrote:

Am I understanding correctly that this tries to use the last instruction in the entry block rather than the first one to avoid triggering the ephemeral value check, in case the first instruction is part of an assumption?

Yes, the first instruction is fine except for an assume which appears (along with its ephemeral values) as the first thing in the function, which in case of an argument seems quite likely.

In any case, I don't think it's appropriate to perform a full block scan to determine the context instruction. safeCxtI() should be cheap (as in O(1)).

An unbounded scan of the entry block might indeed be too much even if applied only to arguments. The scan can perhaps be limited to some small number of instructions (5 seems like the minimum to cover most patterns in computeKnownBits()) which gets reset if an assume is encountered.

Another possibility would be to leave the context instruction at nullptr, and instead adjust isValidAssumeForContext to accept a nullptr CxtI in which case only instructions that are must-exec from the function entry are considered. Advantage is that it only incurs a cost if there is a potentially relevant assume.

I wonder if the code from fixReductions() could be moved (almost as-is) to widenPHIInstruction() as a first step?

Sorry for the delay @nikic.

Limit trailing-zeros check to SCEVUnknowns and only while depth limit is not reached.

Addressed comments.

LGTM, thanks!

Add a test for a constant TC with IC=3.

LGTM!

LGTM, tx!

How is the new test related to this change?

LGTM, tx!

LGTM, tx!

LGTM, tx!

In D80220#2078460, @fhahn wrote:

In D80220#2078222, @gilr wrote:

We still use GEP->clone() for the case where the GEP is loop invariant. It would probably be best to do that in a follow-on patch. Same for perhaps storing InBounds directly in the recipe as well.

The patch LGTM, any reason not to include the base pointer?

LGTM with a nit. Thanks!

Thanks for looking into this, Florian (and sorry for taking so long).
LGTM, except VPInterleaveRecipe::print() is missing here.
The patch stands by itself as a standardization of printing, similar to how the multi-line Function and Module print. If meant as a first step, would be good to elaborate on the full picture.

LGTM (with that missing comment nit), thanks!