This is an archive of the discontinued LLVM Phabricator instance.

[InstSimplify] fold exact divide to poison if it is known to not divide evenly
ClosedPublic

Authored by spatel on Dec 28 2022, 11:27 AM.

Details

Summary

This is related to the discussion in D140665. I was looking over the demanded bits implementation in IR and noticed that we just bail out of a potential fold if a udiv is exact:
DemandedBits source link

Also, see tests added with 7f0c11509e8f.

Then, I saw that we could lose a fold to poison if we zap the exact with that transform, so this patch tries to catch that as a preliminary step.

Alive2 proofs:
https://alive2.llvm.org/ce/z/zCjKM7
https://alive2.llvm.org/ce/z/-tz_RK (trailing zeros must be "less-than")
https://alive2.llvm.org/ce/z/c9CMsJ (general proof and specific example)

Diff Detail

Event Timeline

spatel created this revision.Dec 28 2022, 11:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 28 2022, 11:27 AM
spatel requested review of this revision.Dec 28 2022, 11:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 28 2022, 11:27 AM
nikic added inline comments.Dec 28 2022, 11:34 AM
llvm/lib/Analysis/InstructionSimplify.cpp
1158

This is not correct, Q.CxtI can be an unrelated instruction. You need to pass the exact flag down into the function.

spatel planned changes to this revision.Dec 28 2022, 11:53 AM
spatel added inline comments.
llvm/lib/Analysis/InstructionSimplify.cpp
1158

Ah, I saw how some FMF were handled and followed that code pattern, but now I see how no-wrap is handled for other opcodes.

spatel updated this revision to Diff 485535.Dec 28 2022, 12:31 PM

Patch updated:
Pass in a bool for exact-ness from the callers instead of using the context instruction in the SimplifyQuery. Test diffs are not changed.

spatel marked an inline comment as done.Dec 28 2022, 12:33 PM

Do we do this for right-shifts already?
If not, might be easier to start with that.

llvm/lib/Analysis/InstructionSimplify.cpp
1160

I think this is a better proof:

https://alive2.llvm.org/ce/z/zCjKM7
But not: https://alive2.llvm.org/ce/z/-tz_RK
5692–5693

/*IsExact=*/

llvm/test/Transforms/InstSimplify/div.ll
380–381

Is there a non-uniform test?
https://alive2.llvm.org/ce/z/Qkz5ac

spatel marked 2 inline comments as done.Dec 29 2022, 5:32 AM

Do we do this for right-shifts already?
If not, might be easier to start with that.

There is a variation on this theme for shifts (pasted code below), so I'll put a TODO on that.
I saw the missed division first, and I think we'd be more likely to spot bugs with a botched div if this manages to uncover any broken transforms.

// The low bit cannot be shifted out of an exact shift if it is set.
if (isExact) {
  KnownBits Op0Known =
      computeKnownBits(Op0, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
  if (Op0Known.One[0])
    return Op0;
}
llvm/lib/Analysis/InstructionSimplify.cpp
1160

Do the extra function args just allow showing the TZ values/bounds more easily, or is there another benefit from writing it like that?

spatel updated this revision to Diff 485610.Dec 29 2022, 5:36 AM

Patch updated:

  1. Added non-splat vector tests.
  2. Added code comments for bool function args.
  3. Added TODO for exact shifts.
lebedev.ri added inline comments.Dec 29 2022, 5:36 AM
llvm/lib/Analysis/InstructionSimplify.cpp
1160

Do the extra function args just allow showing the TZ values/bounds more easily

Yes. That wasn't apparent to me in original test.

spatel edited the summary of this revision. (Show Details)Dec 29 2022, 5:50 AM
lebedev.ri accepted this revision.Dec 29 2022, 5:53 AM

LG, thank you.

This revision is now accepted and ready to land.Dec 29 2022, 5:53 AM
This revision was landed with ongoing or failed builds.Dec 29 2022, 7:30 AM
This revision was automatically updated to reflect the committed changes.
spatel marked an inline comment as done.