Added test for combination of these options.

This is awesome. And scary. This is scarily awesome. :)

Please reduce the test or give an elaborate explanation of the problem. So far it's not clear to me what was the problem and why it fixed this way.

LGTM

That could go without review. LGTM.

I added tests for signed and for ne predicate, but currently they fail even before they reach this code. Can be enabled in follow-ups.

Previous version was better, but still not good enough. Tried another version that removes two instances of isKnownViaNonRecuriveReasoning from the path.

Maybe it's because isKnownPredicateAt makes an extra call to isKnownPredicate which we don't really need. Let's try more lightweight version with isBasicBlockEntryGuardedByCond. This should not introduce extra overhead.

Already present in isBasicBlockEntryGuardedByCond.

Strange. I'll revert it for now and investigate.

Rebased, fixed '.wide name.

My understanding of this situation is that, whenever we delete an instruction that may be referenced by SCEV, we should call forgetValue for it. SCEV that contains references on deleted instructions is invalid. Faling to forget deleted values is a bug. I don't understand why llvm.dbg.value is somehow special about it. This patch tries to hide the consequences of the bug instead of fixing it.

Actually, it only means that isLoopBackedgeGuardedByCond should directly call isKnownPredicateAt(Latch->getTerminator()) as the last resort. I will follow-up with this improvement adding relevant test.

Eeek. I found a test where isKnownPredicateAt is more powerful. Need to use both then.

Do we know at which point LSR deletes the code? To me it looks like we just forgot to call forgetLoop or smth like this somewhere.

In D91525#2412162, @aeubanks wrote:

I'm not super familiar with this, do you know why this only affects the new PM? (the code looks fine, I'd just like to understand what's going on better)

Yes, I ran 4077 fuzz tests checking this assumption, and it seems better in every case there. There can theoretically be cases where isLoopBackedgeGuardedBy is weaker, but it's only the reason to improve it.

Please move the test out of MIPS-specific into general test directory if it's possible. Otherwise, LGTM.

The idea of having SCEV pointing to deleted instructions scares me. Imagine what if we had SCEVAddRecs referencing the loops we've already deleted. There is a vast field for nasty bugs caused by UB and memory corruption. I'd rather expect that we fail some assertion if we try to optimize with SCEV in that state.

The change looks very reasonable, though I don't know what motivation was behind the current ordering. There might have been some (arcane) reasons behind it. Fine by me, but please have someone else to take a look.

This was completely illegal. Need to find a way to revert it now.

Roll back to older code concept (without generatization into DomTree). It seems unreasonably difficult to check in code there.

Let's go with 3. The idea was to share this code if someone might need it. I'm totally fine if it's written every time in different places whenever someone needs this logic.

Fixed check (as expected, dominates fails for two Phis from the same block).

Added expensive asserts;
Renamed Insns->Instructions

I see the deep API problem here now. Current dominates(Value *, Instruction *) should not be called like that (at least because it returns false for dominates(X, X)). It has a different semantics, and should be called something like "canBeUserOf".

In D91767#2410454, @kuhar wrote:

In D91767#2410450, @mkazantsev wrote:

You can find the planned user in dependencies stack: https://reviews.llvm.org/D90456

I need the common dom to find the latest context where we can prove predicate so that it's also true for all given instructions.

What do you think about defining and implementing bool dominates(Inst, Inst) at the same time (or before) findNCDInst?

You can find the planned user in dependencies stack: https://reviews.llvm.org/D90456

In D91767#2408334, @kuhar wrote:

As an alternative implementation, have you considered teaching DomTree::findNCD to work with multiple basic blocks first, and then using this to implement the multi-instruction findNCD?
The algorithm would be like this: create a vector VBB of BB of all instructions, find its NCD, case split on the NCD and VBB being the same block or not.