This is much more expensive than when I tested this the last time on August 2nd, 2021: https://llvm-compile-time-tracker.com/compare.php?from=380b8a603c6e8997819726b15a76b8f6c94aa21a&to=abb759c879725b7bc09a466e92c9b9eca7f8f483&stat=instructions:u At that time, the pass was pretty cheap, and as such a reasonable tradeoff. Now this doesn't seem to be the case anymore.

LGTM. I have looked at the code here, but before that we have discussed the approach here and also alternatives with Alex. Since we haven't received any comments from other reviewers, I suggest we merge it.

In D123400#3443913, @bmahjour wrote:

I explained my reasoning for needing a different approach in D122776. I just figured it would be a lot easier to show what I mean by posting a new patch instead of trying to describe it as a change request on top of D122776. I'm happy to continue further discussion on this wherever seems more appropriate to you or other reviewers.

Hi Bardia

Alex and I have discussed this in detail. This testcase can also be investigated for potentially extending the algorithm. While we are confident that with the existing information (the paths that we gather during analysis phase) it is not possible to jump thread the switch statement, it may be possible to jump thread it if we gather more information (gathering a set of longer paths in the analysis phase). But at this point it does not seem worthwhile to explore this path, and the most reasonable solution is to add this new condition to make the case illegal. Alex have also compared with gcc, and they do not jump thread this switch statement.

In D99205#2923056, @SjoerdMeijer wrote:

Just a heads up. I have benchmarked this version against our downstream implementation of jump threading and see some regressions:

       Regression
core1  0.4%
core2  0.28%
core3  2.7%
core4  0.24%
core5  1.12%

Especially for the more capable cores "core3" and "core5" the difference is quite big, so we do leave some performance on the table.

I will probably add a reproducer as a regression test and raise a ticket for this, so that we can look into this.

A couple of comments/clarifications about irreducible CFG that came up in earlier comments: This pass does not generate irreducible CFG for coremark. It does generate irreducible CFG for https://bugs.llvm.org/show_bug.cgi?id=42313. We also checked gcc and it seems that gcc also generate irreducible CFG for PR42313.

@sebpop Do you mind reviewing this patch? This is jump threading for finite state machine. You may remember we had a discussion about it back in 2018 and 2019 llvm dev meeting....We didn't follow up as quickly as I hoped but recently we got the opportunity to improve the code and post it here. As you can see some review has been done, but currently it is waiting for further review or green light to merge.

In D88307#2597214, @dnsampaio wrote:

Hey @eastig and @amehsan, thanks for working on this. Do you have any idea when this work is going to be resumed?

In D88307#2518321, @xbolva00 wrote:

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

Please check if this pass can handle it.

This is the remaining of the algorithm that I mentioned above. (Step (3) of the algorithm). Please see the previous comment first. There should be enough details here to make the algorithm clear. Let me know if something is missing. Our work on revising the code has been suspended for a while. Will try to resume that soon. We are currently running some experiments to find similar code patterns so we can check generalizability of the algorithm beyond coremark.

I think it is generalizable, and I will try to clarify generalization opportunities.

There are three main components in the algorithm.

1- Choosing a SSA variable in the loop that is interesting. (“the variable” hereafter)
2- Proving the branches that depend on the value of the variable has opportunity for jump threading.
3- Deciding on which blocks needs to be replicated, how much code increase we will have and which branches we can remove.

Sorry for delay. I will describe the algorithm (that I mentioned in an earlier comment) in two steps. In step 1 (This comment) I describe the high level and main steps of the algorithm. In the next step I will go into details that are missing here. I’d be glad to get some feedback and know what people think about the approach.

I am not sure whether our approach can be integrated, with this patch. The approaches are completely different. But I can write a summary of our algorithm and we can discuss the algorithm first. We are working on rewriting the code and we can post it when it is ready. Since @eastig has also switched to a similar approach (analyze-then-transform), it will be interesting to have a discussion about different algorithms.

@alexey.zhikhar and I had a look at your patch. Some findings that might be interesting:

Our pipeline has some differences with the default pass pipeline. The problem was exposed when playing with the pipeline. As Jimmy mentioned it is in one of the smaller benchmarks in the test suite. Overall impact is small, but on the other hand, we are not adding any compile time or any other kind of cost. So I don't see an issue. The remaining question is functional stability. The code looks quite correct to me. You have also looked into it in the past so I think on that issue we are fine. There is always a chance that we expose some other bug somewhere else. We have not observed that issue and given limited impact of the patch it is not very likely. Anyways, I think overall this should be fine to be merged. Still I wait a little more to see if any of the reviewers has any concern in the next couple of days.

Is there any concern about this patch? We have reviewed this internally and it looks good to me. It has been also tested extensively. The condition on the load instruction does not seem to have any role in correctness of the transformations and seems to be a completely arbitrary condition. I accept the patch for now, but I will wait and prefer to hear from one of the other reviewers before committing it.

Committed
https://reviews.llvm.org/rG53b95a3cb6a7

committed
https://reviews.llvm.org/rG61e54fd60c43

In D69059#1767016, @c-rhodes wrote:

@mgudim I've created a patch (D70909) also implementing these intrinsics but I was unaware of this patch, sorry about that. Can this be merged now? I can update D70909 to only add the SVE2 intrinsics .

committed
https://reviews.llvm.org/rGe55b536d7d81

Merged the patch https://reviews.llvm.org/rGed7bcb2cb157

LGTM. @sdesmalen @huntergr please let us know if you have any concern

Committed in https://reviews.llvm.org/rG1e9de0215f04

In D68476#1717715, @huntergr wrote:

Hi, thanks for waiting a bit. LGTM.

This looks straighforward. So LGTM. Since this is @mgudim's first patch, I will commit it for him. But I will wait a bit more (before committing) just in case @huntergr has any comments.

Committed.

In D68098#1687669, @huntergr wrote:

LGTM.

You can add the extra multiclass for ftsmul if you wish, but it's not needed until someone implements a matching pattern for that instruction. We only match it against an ACLE intrinsic downstream, not common SDag nodes.

@huntergr Updated according to your comment. Please check. Thanks!

Thanks @huntergr. Will update the patch. Once I am sure we got this one right, we can look into others.

Committed in rL350931

In D55264#1345253, @brzycki wrote:

@amehsan gentle ping. Have you resolved your push access?

Thanks @brzycki for careful review. I need to revive my commit access (not used it for two years now), then I will commit this.

Thanks @brzycki. I believe I have addressed all your comments. Will upload the modified patch shortly.

In D32888#771149, @wenbos wrote:

Hi Hal, can you commit it since I have no commit access?

@echristo explicitly approved this in his last comment, but I think he forgot to change the action box. So I accept just for easier book-keeping. (Eric is in vacation, AFAIK)

https://reviews.llvm.org/rL287872

https://reviews.llvm.org/rL290102

This patch, as is, is incorrect and requires some changes to proceed. Abandoning.

rL289813

Ping

In D25200#610857, @spatel wrote:

In D25200#610847, @amehsan wrote:

You are right (I just tried it :-) If that is the only concern is it possible to approve this and I will remove that line from the switch stmt. (I think it does not hurt to leave the testcases though) and commit.

Yes, it's good to keep the tests to make sure the underlying assumption doesn't break.
LGTM - although I don't think we need a switch for just 2 cases. :)

In D25200#610628, @spatel wrote:

In D25200#610626, @spatel wrote:

Can you just assert that the predicate is not 'ugt' in isAnyBitSet() and simplify that a bit more? Ie, we don't need a switch if we know that eq/ne are the only predicate possibilities for this transform.

"assert" is probably too strong...I've made that mistake before. :)
But I think it's still safe to ignore the 'ugt' case and assume that InstCombine will churn that away sooner or later.

Added the clean up step that we discussed. Also, made some changes in the comments in the code.

Will shortly update the patch.

In D25200#600208, @amehsan wrote:

@spatel @eli.friedman Could one of you please look at this patch? @majnemer said he is busy and will be even busier next week.

@spatel @eli.friedman Could one of you please look at this patch? @majnemer said he is busy and will be even busier next week.

https://reviews.llvm.org/rL287329

https://reviews.llvm.org/rL287334 (fixed the comment in a followup commit though).

Could someone take a look at this?

I actually wanted to check some surrounding guards.

more context?

In D25482#585513, @amehsan wrote:

In D25482#585510, @MatzeB wrote:

In D25482#585491, @amehsan wrote:

In D25482#585490, @MatzeB wrote:

In D25482#585479, @amehsan wrote:

2- targetSchedulesPostRAScheduling

This seems redundant to me as soon as 1) is implemented.

Maybe I am missing something, but this seems different from (1). Note that addPostRASched is called from addMachinePasses which is not typically overriden by targets. SystemZ has a usecase for targetSchedulesPostRAScheduling which cannot be covered by (1).

Overriding addPostRASched() with an empty function has the same effect as returning true in targetSchedulesPostRAScheduling(), hasn't it?

Correct :)

So we can remove targetSchedulesPostRAScheduling() and replace it with the empty function overload after adding addPostRASched().

That's a reasonable change for this patch. I'll wait to see Eric's comments well, before updating the patch though. Just to save time.

I put this back in review as Eric wanted to take a look.

now fully tested with test-suite.

Just finished lnt test and there are some failures. I will update when my investigation of the failures is done.