ping

Will reopen when I get time to return to this. Closing in the meantime to get off review queues.

Will reopen when I get time to return to this. Closing in the meantime to get off review queues.

Address a couple of minor review comments.

Heading in the right direction.

In D112895#3151903, @apilipenko wrote:

Do you mind if I put this change under an on by default cl::opt flag? This way we can temporarily turn it off downstream.

Seems reasonable to me.

In D112895#3149487, @apilipenko wrote:

Any suggestions for the best place to handle it?

Urgh, this is an annoying case. We need a mixture of dominating facts relating two variables, and range facts about those same variables. We don't really have any single place which has both.

Ran the test suite. Surprisingly, this appears to be nearly performance neutral.

Further simplify - despite structure of existing code, shouldFullUnroll doesn't modify it's UP param.

In D111806#3079379, @modimo wrote:

To keep the conversation coherent I'll talk about the same feedback for D87551 here:

In D111806#3067256, @reames wrote:

If we were being presented with hard cases to undo with a cost based transform, I might be willing to entertain the notion that LICM should be non-canonical. As it stands, I don't see such examples.

The original change that prompted adding this from @wenlei is a more complicated situation https://reviews.llvm.org/D65060#1596899. Specifically, once the values are hoisted out of the 200 switch arms there's not longer a dominating use block to sink them back into. In addition, the block frequency information at that point no longer indicates that there's an issue from the hoisting. Getting MachineLICM to handle that case is complicated and I suspect fragile.

FYI, I find this very unconvincing. First, the motivating test case appears to have been discussed, but never shared. Second, as discussed, we appeared to have something along the lines of a switch mapping to address offsets, which is then loaded from. We can and do pull such geps down through the phi, and that optimization should probably have triggered on the discussed example. In general, a missing optimization is a *bad* motivation for disabling a canonicalization.

In D114185#3143327, @nikic wrote:

I'm really uncomfortable with removing things from UniqueSCEVs. If I understood correctly, your motivation here is that getZeroExtendExpr will not try folds if it has already memoized that the fact that this expression doesn't fold. I think we'd be better off adding a parameter to skip that check for this use-site.

Fair enough, that's why I asked. Will restructure.

In D108848#3138354, @xbolva00 wrote:

Not NFC?

https://bugs.llvm.org/show_bug.cgi?id=52535

Took a quick look at this. No obvious relation, I'd guess some type of pass ordering and/or analysis invalidation. If you can reduce me something which changes behavior with this pass, I'll take another look.

Ok, let me describe back to you what you're trying to do. Give a case like:

loop {
  a = *g;
  if (a) break;
  *g = a + 1
}

Where g is some loop invariant address, you want to produce a form which looks like this:

a0 = *g
loop {
  a1 = phi (a0, a2)
  if (a1) break;
  a2 = a1 + 1
  *g = a2;
}

@nikic I don't see anything obvious here, and don't consider the reported issue worthy of revert. Given that, I'm going to stop look into this. If you want to file a standalone bug with a reproducer, I can take a further look, but at the moment, the amount of information shared so far is not really easily actionable.

In D114325#3146783, @dblaikie wrote:

Generally seems like a good direction to go in, if it's feasible - but it seems like a pretty big step up in resource expectations than the past/current buildbots/workers, so I'm not sure how feasible it is to get those resources.

Er, no. This is very much documenting current status. While we have a bunch of batch builders, we also have a bunch which do build every commit.

Note - original patch has landed. Reopening with revisited wording to address suggestions brought up review to avoid fragmenting discussion. This seems like the least confusing option, let me know if you'd rather I do this with a separate review.

I went ahead and landed this as is, but plan to do a second pass (with separate review/discussion where appropriate) to incorporate @rengolin additional comments.

In D103991#3143636, @nikic wrote:

Looking at callgrind profiles for one test case, the main additional cost is when simplifying IVs after unrolling, during the willOverflow check that zext/sext both operands. In getZeroExtendExpr we seem to spend more times in various proveNoWrapByXYZ() methods. It's not obvious to me how this change would cause that, I'd more expect the reverse effect (less need to infer additional flags because we added more here).

All I can think of is that maybe we figure out the trip count for some loop, unroll it, and then spend time analyzing the newly introduced IVs? That's really the only interaction I can find.

In D103991#3142766, @nikic wrote:

Also no difference. I suspect that we're seeing some kind of second order effect here, not an issue in the code itself.

I agree and am going to revert the two speculative changes as they just complicate the code.

In D103991#3141328, @nikic wrote:

Nope, this didn't make any measurable difference.

How about 734abbad7?

In D103991#3141134, @nikic wrote:

I don't immediately see what could cause this.

Does 1a5666acb help? That's the only thing I could vaguely see causing this.

In D103991#3140961, @nikic wrote:

Looks like this caused an unexpected compile-time regression: https://llvm-compile-time-tracker.com/compare.php?from=7a14244cc645bbbcbf5056e7a00fadbb339e92ed&to=ea12c2cb9c4221095abfb2af7148140783040734&stat=instructions +1.5% on mafft.

Your right, that is unexpected. I don't really see anything in this code likely to be slow, do you see anything obvious? If not, I may need help testing a few variants to see what we see.

Address review comments

LGTM

This update reworks the patch, and hopefully makes it a lot more obviously correct. The patch is restructured to purely pull code up from howManyLessThans into the caller so that it handles all condition codes. This does reduce the scope slightly, but I've included planned extensions in the review description which should cover all cases.

Next action item here is mine. (Rebase needed, tests can be landed, etc..)

In D114112#3138506, @efriedma wrote:

In D114112#3138447, @reames wrote:

In D114112#3138430, @efriedma wrote:

Do we have some documentation that indicates what we expect alias() to return in the case where instructionCouldExistWitthOperands fails?

Not quite sure what you're asking. If we have two pointers, the conservative result should always be MayAlias. Is that what you meant?

I mean, if we do an alias query with a pair of Instruction* that don't have a common scope, are all AA implementations required to always return MayAlias? Call llvm_unreachable? Or can we perform some sort of approximation of the possible values produced by the Instruction? If we do approximate the value, what are the rules for that?

Ah, this is a question about the alias interface on AliasAnalysis. It doesn't appear to address this question. I'm honestly not sure if we could return anything other than MayAlias, and very deliberately tried not to open that can of worms. :)

In D114112#3138430, @efriedma wrote:

Do we have some documentation that indicates what we expect alias() to return in the case where instructionCouldExistWitthOperands fails?

Not quite sure what you're asking. If we have two pointers, the conservative result should always be MayAlias. Is that what you meant?

Abandoning this in favor of https://reviews.llvm.org/D114112.

Still no reported issues with the original patch. Abandoning for now, will return if warranted.

This needs much clearer motivation - specifically a clear explanation of what you're trying to achieve and why. Please consider that motivation blocking for further review.

What prevents:
base = some alloc
%iv = {0, +, 1} as i8
%gep = getelementptr i32, i32 *%base, i8 %iv

In D113835#3132720, @fwolff wrote:

Thanks for the review @reames! I've added another test to cover the edge cases. Can you commit this for me?

Sure. To confirm, this is code you intend to contribute to llvm under the terms of the relevant licenses and agreements, and have the authority to agree to same?

Spent some time educating myself on AArch64 frame lowering. I'm mostly relying on the diagram at the top of AArch64FrameLowering.cpp. Review guidance is about specializing the case where the variable sized regions are empty.

This is a bit outside my expertise so I'm not thrilled about being the sole reviewer for this, but given no one else has responded and this looks reasonable, I'm approving this to unblock progress.

LGTM with required changes made.

In D26149#3131756, @spatel wrote:

In D26149#3130357, @Joshua-401 wrote:

Did you consider doing the load combine at IR level? I'm now trying to combine loads at IR level during the InstCombine process, so I'm wondering why you didn't do that.

There was an IR load combine pass (see D3580 - although never enabled by default AFAIK), but it was removed because it could interfere with other passes like GVN.
https://lists.llvm.org/pipermail/llvm-dev/2016-September/105291.html
https://lists.llvm.org/pipermail/llvm-dev/2019-September/135052.html

LGTM. We can revisit more complicate heuristics when we have evidence it matters.

@nikic ping on previous question. It's been a month, and this has been LGTMed. Without response, I plan to land this.

Thanks for the rebase, much easier to understand.

Surely this causes some test diff in the existing test corpus? It looks like the review is incomplete. (Or I'm simply very surprised.)

This generally looks very reasonable.

LGTM as well. Amusingly, I'd stumbled into a variant of this as well just yesterday. :)

In D110527#3121915, @bjope wrote:

The IR part can often be eliminated from a MIR based test case. But sure, one could argue that when running llvm-reduce it could be mandatory to add an IR section in the .mir file first (but then I think one needs to also add the function prototype).

I can maybe see this as an argument for allowing override of the triple, but not as an argument for not defaulting to the triple if present. Frankly, I find even the override case unconvincing.

In D110527#3121844, @aeubanks wrote:

In D110527#3121812, @reames wrote:

I'm looking at using this functionality, and ran into a question on the design. I'm not clear why you exposed an mtriple command line argument on llvm-reduce. It appears you're using this to derive a default data layout, and as an input to parsing the machine function. However, LLVM IR allows specifying both data layout and triple in IR. As a result, we should be able to have the parsing derive the appropriate target directly from the test case. Is there something I'm missing here?

I believe it's only used in the MIR case, not the IR case. This could definitely be made clearer in the cl::opt help.

I don't think it's necessary even for the MIR case. MIR includes the full IR module, and is as a result, is also fully self describing. (If the optional datalayout and triple fields are present.)