This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] Improve non-zero tracking of `X` by also searching through `Use(X)` that imply non-zero
Needs ReviewPublic

Authored by goldstein.w.n on Jan 28 2023, 8:58 PM.

Details

Summary

We currently are able to prove X is non-zero if there are dominating
compares or assumes directly on X, but we can do a bit better and
also check uses of X s.t Use(X) != 0 implies X != 0.

For example if we have assume(X & Y != 0), we know X != 0.
Likewise if we have a dominating condition:

if(X & Y != 0)
  {
    // X is known zero here
  }

Currently implemented to track through:

Diff Detail

Event Timeline

goldstein.w.n created this revision.Jan 28 2023, 8:58 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 28 2023, 8:58 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
goldstein.w.n requested review of this revision.Jan 28 2023, 8:58 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 28 2023, 8:58 PM
StephenFan added inline comments.Jan 29 2023, 12:28 AM
llvm/lib/Analysis/ValueTracking.cpp
2380–2385

This is a repeat of the above.

2409–2410

Blank line.

2419

IIUC, Intrinsic::umin may also imply non-zero.

nikic requested changes to this revision.Jan 29 2023, 12:44 AM

We should be testing canonical IR here (use -passes=instcombine), at which point many of these should already be handled. E.g. if you have a condition abs(X) != 0, that should get canonicalized to X != 0 first, and then handled by existing code.

This revision now requires changes to proceed.Jan 29 2023, 12:44 AM
goldstein.w.n marked 2 inline comments as done.Jan 29 2023, 1:21 PM

We should be testing canonical IR here (use -passes=instcombine), at which point many of these should already be handled. E.g. if you have a condition abs(X) != 0, that should get canonicalized to X != 0 first, and then handled by existing code.

Done, my goal was to try and isolate the tests to test the added logic.

Updated to use instcombine and changed many of the compares so they don't hit the canonicalization cases.

llvm/lib/Analysis/ValueTracking.cpp
2419

IIUC, Intrinsic::umin may also imply non-zero.

Would rather make this another patch if thats okay with you.
this one is mostly to setup the infrastructure.

Updated tests, fixed some nits, rebase

xbolva00 added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
2368–2369

'Null' -> 'Zero' ?

goldstein.w.n added inline comments.Apr 9 2023, 2:40 PM
llvm/lib/Analysis/ValueTracking.cpp
2368–2369

'Null' -> 'Zero' ?

I think its best to keep the original function name the same.

ping6

@nikic if you think that change should be abandoned, can you at least make that clear?