I committed and reverted the patch since it fails x86 sanitizer check. The reason is that after the patch, the variable LoopExit becomes unused.

Removed the variable LoopExit.

In D98475#2672443, @bmahjour wrote:

Thanks for fixing this problem. I just have some comments about the tests, otherwise LGTM.

All comments addressed.

Removed unnecessary code, simplified the logic.

gentle ping @fhahn @Whitney @bmahjour

In D98263#2644895, @Whitney wrote:

I am fine with this change now, but in the future we should try to

1. Use utilities in LoopNest as much as possible
2. Loosen the definition perfect loop nest in LoopNest
3. Make the transformation more generic to handle more cases, e.g. the newly added test interchange_07.

Updated the patch according to the comments.

gentle ping @fhahn @Whitney

gentle ping @fhahn @Whitney

gentle ping @fhahn @Whitney

gentle ping @fhahn @Whitney

In D98263#2618403, @TaWeiTu wrote:

Hi @congzhe, thanks for the fix!

I think it'd probably be better to keep the LoopNest::checkLoopsStructure and add the additional checks of branch instructions for now.
By doing so, future changes to LoopNest will also apply in LoopInterchange, which is what we are trying to achieve I think (by making the definition of perfectly-nested loop in sync).
The check can be removed in the future, when LoopNest is eventually taught to correctly identify guard branches (singleSucc is currently considered to be the guard branch of the inner loop, but the loops should only be considered perfectly-nested if the guard branch corresponds to the one added by LoopRotate IMO, which is not true in this case).

What do you think?

In D98263#2617162, @TaWeiTu wrote:

In D98263#2617156, @Whitney wrote:

The patch now revert part of https://reviews.llvm.org/rGdf9158c9a45a6902c2b0394f9bd6512e3e441f31, which leave some changes behind.
Given that the change cause a test case crash, @TaWeiTu can you please revert the change?

Sure, reverted.

Updated the patch based on the latest trunk code.

In D98263#2616699, @Whitney wrote:

Thanks for fixing it. Is the crashing test case an existing test case, or will be added in D96708 or D91682? If not, can you please also include that test case in this patch?

Updated the patch.

An update: the current trunk code (without this patch) fails the following test (crashes as follows):

In D96708#2605502, @masakazu.ueno wrote:

I added some comments to the source code.

In D93065#2475022, @aqjune wrote:

Okay, I think the remaining optimizations (other than opened patches) are:

• LoopUnswitch.cpp: I can address this
• PredicateInfo.cpp: I'm not sure whether a local change will be enough, because the relevant classes in PredicateInfo.h are exposed to other optimizations.
• SimpleLoopUnswitch.cpp, LoopPredication.cpp, InductiveRangeCheckElimination.cpp: have no idea

After LoopUnswitch and PredicateInfo is updated & the select -> and/or is conditionally allowed, we can try performance evaluation again and see whether there still exists regression. What do you think? @nikic @congzhe

In D93272#2466125, @spatel wrote:

LGTM

In D93065#2463069, @nlopes wrote:

In D93065#2461517, @congzhe wrote:

In D93065#2461196, @nlopes wrote:

Using freeze loses information (if some of the inputs was poison). Plus It requires an extra op.
If we canonicalize around select there's no loss of information and it's just 1 instruction.

The disadvantage is that then we have 2 ways or doing boolean ANDs/ORs. Though most analyses can be patched easily, as most LLVM analyses' results are of the form "x has property foo unless it's poison". So for those analyses using and/or or select is the same (as the only difference between these is propagation of poison).
Other analyses/optimization can learn about select as needed.

Thank you for raising up the good point! I understand that we lose information by preventing poison values from propagation using freeze. But I'm unclear what would be the side effect or problem with that? I'd appreciate it if you could clarify a bit, thanks!

In practice, probably not a lot. But it may have implications for loop optimization, like:

for (i=0; some_bool && i < limit; ++i) {
...
}

If you remove the poison from the i+1 < limit bit it may make the work of SCEV harder (or impossible; didn't think the example through carefully).

In D93065#2461196, @nlopes wrote:

Using freeze loses information (if some of the inputs was poison). Plus It requires an extra op.
If we canonicalize around select there's no loss of information and it's just 1 instruction.

The disadvantage is that then we have 2 ways or doing boolean ANDs/ORs. Though most analyses can be patched easily, as most LLVM analyses' results are of the form "x has property foo unless it's poison". So for those analyses using and/or or select is the same (as the only difference between these is propagation of poison).
Other analyses/optimization can learn about select as needed.

In D93065#2453190, @spatel wrote:

In D93065#2452949, @congzhe wrote:

In D93065#2450198, @nikic wrote:

This will require other parts of the compiler (especially anything dealing with and/or'd branch conditions, like SCEV, LVI, ValueTracking etc) to understand this new form of and/or first. I don't think most optimizations care about whether and/or is poison-blocking or not, but they need to recognize the select form if we don't canonicalize.

Thank you, I do agree with you that some infrastructures like SCEV might be impacted. Could you clarify it a bit? I am working on unit tests and perf degradation. Should the cause of any of them be those infrastructures, I will post fixes. Would that address your concern? Or something more than that is needed?"

In D93065#2450391, @spatel wrote:

Thanks Sanjay, by "perf data" I'm wondering which benchmarks does the community mostly care about? LLVM test-suite?

We would get a different answer for each person/company, but test-suite is solid common ground. I think SPEC is also widely used by a large part of the community.

As you said there's two ways to address this bug -- one is this patch, the other is inserting freezes. With this patch I do see degradations on some internal benchmarks and I'm working on the fix. Do you think it is the right track? I just would like to make sure before going too far.

The work I do is on AArch64. It may or may not impact other architectures (X86, PowerPC, etc). I'm wondering what is the typical way in the community to address performance degradations since addressing degradations for all possible architectures seems significant amount of work hence not likely?

In general, we try to address known regressions in advance. If you see a problem on AArch64, it will probably not be too different for the other CPU targets.
It is acknowledged that it is impossible to know how a change like this will affect everything, so as long as we have a plan to deal with problems, it's fine to proceed.
My suggestion is to compare the regressions between this patch vs. adding freeze on test-suite. Is there a clear winner (number and average size of regressions)?
Thank you for pushing this forward!

Current failing regression tests:

In D93065#2450198, @nikic wrote:

This will require other parts of the compiler (especially anything dealing with and/or'd branch conditions, like SCEV, LVI, ValueTracking etc) to understand this new form of and/or first. I don't think most optimizations care about whether and/or is poison-blocking or not, but they need to recognize the select form if we don't canonicalize.

In D93065#2450181, @xbolva00 wrote:

Performance data? No regressions for benchmarks?

Updated to address comments.

Thanks for all the comments, now addressed all of them @fhahn

@fhahn pinging reviewers :)
Comments are very much appreciated.

In D86906#2279815, @fhahn wrote:

oh, it might be good to slightly adjust the commit message to be a bit more compact and also mention what actual bug is fixed, e.g. something like [AArch64] Avoid paring loads with same result reg.

Further reduced the mir test case.

In D86956#2249916, @fhahn wrote:

Is it possible to add a MIR test for the issue? Also, it looks like the formatting is off a bit. Could you run clang-format-diff on the change?

Revision:

• Fixed code style
• Provided an mir test

Revision:

• Fixed code style
• Reduce the length of the test file

In D84220#2250298, @fhahn wrote:

In D84220#2250221, @congzhe wrote:

rebased and clang format-ed the code, ready to merge

great, thanks! As mentioned earlier, please let us know here if you need someone to commit this change on your behalf, with the name/email you'd like the author field set to.

rebased and clang format-ed the code, ready to merge

In D86956#2249916, @fhahn wrote:

Is it possible to add a MIR test for the issue? Also, it looks like the formatting is off a bit. Could you run clang-format-diff on the change?

@fhahn Thanks for the comments.