LGTM w/ description fix.

Pls change patch description into smth more verbose, like

Make Verifier recognize undef tokens as correct IR

Pls add test with side effect that we've discussed offline.

I didn't quite get what's the problem with 2nd example and logical and, but the first example is more than enough to admit it's a bug.

Well, using bug IDs in test names is a common practice, and the idea is to refer the bug that this patch fixes.

Generally LGTM, but please think of examples I've provided, maybe there is a better solution.

I was thinking of smth like

define void @test_chceks_in_loop(i32* nocapture %a, i64 %i, i64 %N) {
entry:
  br label loop

Will it still work if c1 and c2 are checked in the loop? To me it looks like there is some piece of logic is missing in isImpliedCondition.

Looks good, but please regenerate checks here. It's not clear at all what this test is trying to ensure (e.g. what is wide.chk).

Hi @ABataev, this patch is still causing miscompile, see https://github.com/llvm/llvm-project/issues/55688 for details.

That looks much safer now! Thanks. LGTM.

Withdrawing LGTM until asserts are added. I also think you should shortcut through cached method, unless there are reasons not to.

Pls assert that you don't overwrite values in your cache.

LGTM with nit.

It looks like all you want BaseDefiningValueResult for is simply keeping one boolean for each Value you know the answer for. To me it looks like you simply need a map Value -> bool, and isKnownBaseResult should just return result from this map. After that, we don't need the structure BaseDefiningValueResult at all.

Looks nice, but I'd suggest some restructuring.

General questions: there are multiple places where we call eraseFromParent. Is there a guarantee that after this the cache is valid? Any way to verify this?

LGTM w/ nit.

Addressed comments.

My measurements are tad noisy, but they show ~10% JumpThreading CT saving on a big method.

This causes the following failure: https://github.com/llvm/llvm-project/issues/54976

Will this patch handle the following example:

LGTM with nits.

Yup, I agree with that. To me the initial formula

reg((-1 * {0,+,8}<nuw><nsw><%bb2>)<nsw>) + 1*reg((8 * (%arg /u 8))<nuw>)

isn't canonical too, but because of wrong check (which simply checks that base reg isa SCEVAddRec) multiplication by minus one obfuscates this.

Could you please elaborate what kind of crash do you see? Is it simply an assertion that something must be canonical and it's not, or something more sophisticated?

LGTM

Why can't we just give up verification of unreachable loops/blocks?

When something is already erased from uniqueSCEVs, but is still in use, I'm pretty sure verify() should break somewhere on this situation. Is this something that is happening in reality?