LGTM

LGTM

The patch fails the following test:

One of my fuzz tests has failed with the following assertion:

I have some minor comment, only the one that is related to SafetyInfo worries me (yet it just needs using utility function instead of just moveBefore). All other things are non-functional nits.
I'll take some time running fuzz tests with this patch because it's big. :) Please wait few hours, I will either give you approval (under condition that my comments will be addressed) or give you a failing test example.

It seems that the initial design of this algorithm wasn't intended to make 2 recursive calls from 1 place. The interesting bit is that we only can have an exponential explosion here:

Added lambda for printing;
Reworked to make it clear that we are doing it for non-dead loops;
Simplified logic in constantFoldTerminators

Rebased. I will wait a bit if we will find any bugs in underlying LICM changes and if it's OK, I will merge it by the end of week.

I don't think I'll ever have time for this.

Fixed typo bug, added LI and DT verification, changed FoldingCandidates to vector to keep deterministic order of updates, updated tests with decline messages to make sure that we exercise all possible scenarios in our test file.

Needs rebase.

Needs rebase.

Making a separate NFC which checks analyzes behavior doesn't sound because I am using sets to store blocks status, and printing out the contents of sets is non-deterministic.

Ping?

Missing Changed update and LI sanitizing should be added.

Unfortunately I am not familiar enough with AliasSetTracker to answer that question. We should maybe wait for @reames to clarify it.

LGTM

As for the test: I have commited all related tests I am planning to support in this pass in the file test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll. It has all situations with dead blocks, live blocks, dead loops etc, please take a look and tell me if some important case is missing. My plan is to support folding in all these cases incrementally.

Fix typo in dump()

BTW this test is invalid, it has a load from nullptr and therefore contains UB.

Updated test/CodeGen/AMDGPU/build-vector-insert-elt-infloop.ll

Rebased

Addressed comments.

https://reviews.llvm.org/rL345814

I generally like what this patch is doing, but the size of code and its complexity overwhelms me. Is it possible to separate the patch into smaller pieces so that it would be easier to review them in isolation? If yes, I'd appreciate that a lot.

I expect compile time impact to be zero for majority of cases. It should only affect corner cases at which we reach limit depth during simplifications. For them, depending on simplifications complexity, we save O(N) time simplifying. I don't think it will really be observable on anything other than corner-cases.

Is it possible to write a test on that?

Added the new exit block to the vector. Though it was pretty straightforward, I will re-run my fuzz testing to make sure everything is fine now.

Rebased on top of https://reviews.llvm.org/D53747. Now we know for sure that we have a point after which the unswitching will succeed, and we don't need to worry about turning guard into a branch and then failing to unswitch.