Page MenuHomePhabricator

[ConstraintElimination] Decompose or instruction if the constant operand < 2^known_zero_bits of the first operand.

Authored by zjaffal on Jan 25 2023, 7:40 AM.



The or operation can be represented as an add instruction.

Diff Detail

Event Timeline

zjaffal created this revision.Jan 25 2023, 7:40 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 25 2023, 7:40 AM
zjaffal requested review of this revision.Jan 25 2023, 7:40 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 25 2023, 7:40 AM
nikic added a subscriber: nikic.Jan 26 2023, 12:38 AM
nikic added inline comments.

You're looking for haveNoCommonBitsSet().

zjaffal added inline comments.Jan 26 2023, 3:23 AM

I tried the following snippet

if (match(V, m_Or(m_Value(Op0), m_ConstantInt(CI)))) {
  if (haveNoCommonBitsSet(Op0, CI, DL))
    return MergeResults(Op0, CI, IsSigned);

it works for most of the cases but for the following test define void @test.not.uge.ule

%start.4 = or i8 %start, 4
%t.4 = icmp ule i8 %start.4, %high
call void @use(i1 %t.4)

%t.4 is not replaced with true

nikic added inline comments.Jan 26 2023, 3:31 AM

Isn't that the expected behavior? It's the same with your current patch.

goldstein.w.n added inline comments.

Is it more useful to have an add than an or?

nikic added inline comments.Jan 27 2023, 12:59 AM

For this pass, yes, as it only handles adds. If this was a more generic question: We currently canonicalize add -> or if no common bits, and then undo that in various places. It's hard to say whether switching to the reverse direction or -> add would be more beneficial. We have both many or folds and many add folds. I've never tried it, though I did wonder about it in the past.

fhahn added a comment.Feb 6 2023, 2:20 PM

Looks like the patch needs updating.

zjaffal updated this revision to Diff 498854.EditedMon, Feb 20, 7:40 AM

The new change uses haveNoCommonBitsSet instead

zjaffal marked 4 inline comments as done.Mon, Feb 20, 8:04 AM
zjaffal added inline comments.

This transformation should be true

hasNoCommonBits doesn't optimise it while the original implementation did


this check should be false

fhahn added inline comments.Tue, Feb 21, 5:39 AM

Could you add a comment indicating what this code does, i.e. treat or as an Add if no common bits are set?


nit: merge with previous if


It's fine if the current version doesn't catch all possible cases we could optimize. Further improvements can be landed as follow-ups

fhahn accepted this revision.Tue, Mar 7, 5:57 AM

LGTM with the suggestions addressed before landing.

This revision is now accepted and ready to land.Tue, Mar 7, 5:57 AM
zjaffal updated this revision to Diff 503016.Tue, Mar 7, 6:11 AM
zjaffal marked 3 inline comments as done.
  • Add comment to explain that the operation is being treated as an add
  • Address nit comments
This revision was landed with ongoing or failed builds.Tue, Mar 7, 6:11 AM
This revision was automatically updated to reflect the committed changes.