Page MenuHomePhabricator

[InstCombine] foldSelectRotate - generalize to foldSelectFunnelShift
ClosedPublic

Authored by RKSimon on Oct 29 2020, 4:25 AM.

Details

Summary

This is the last of the rotate->funnel shift InstCombine generalizations for PR46896

We still have foldGuardedRotateToFunnelShift to deal with in AggressiveInstCombine

Diff Detail

Event Timeline

RKSimon created this revision.Oct 29 2020, 4:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 29 2020, 4:25 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
RKSimon requested review of this revision.Oct 29 2020, 4:25 AM
nikic accepted this revision.Oct 31 2020, 5:00 AM

LGTM

This revision is now accepted and ready to land.Oct 31 2020, 5:00 AM
This revision was landed with ongoing or failed builds.Oct 31 2020, 5:34 AM
This revision was automatically updated to reflect the committed changes.
nlopes added a subscriber: nlopes.Nov 5 2020, 4:19 AM

Alive2 says this test is incorrect (because select blocks poison and funnel shift doesn't):

define i8 @fshr_select(i8 %x, i8 %y, i8 %shamt) {
%0:
  %cmp = icmp eq i8 %shamt, 0
  %sub = sub i8 8, %shamt
  %shr = lshr i8 %y, %shamt
  %shl = shl i8 %x, %sub
  %or = or i8 %shl, %shr
  %r = select i1 %cmp, i8 %y, i8 %or
  ret i8 %r
}
=>
define i8 @fshr_select(i8 %x, i8 %y, i8 %shamt) {
%0:
  %r = fshr i8 %x, i8 %y, i8 %shamt
  ret i8 %r
}
Transformation doesn't verify!
ERROR: Target is more poisonous than source

Example:
i8 %x = poison
i8 %y = any
i8 %shamt = #x00 (0)

Source:
i1 %cmp = #x1 (1)
i8 %sub = #x08 (8)
i8 %shr = any
i8 %shl = poison
i8 %or = poison
i8 %r = any

Target:
i8 %r = poison
Source value: any
Target value: poison

https://web.ist.utl.pt/nuno.lopes/alive2/index.php?hash=bdd9860ccefdbd55&test=Transforms%2FInstCombine%2Ffunnel.ll

nikic added a comment.Nov 5 2020, 5:14 AM

@nlopes I think we should adjust the funnel shift definition to say that it blocks poison on one operand if the shift amount is zero. Basically the poison semantics should be "as if" the funnel shift were expanded, which does include an explicit select for the zero shift amount case.

Thanks @nlopes - I assume a suitably positioned isGuaranteedNotToBeUndefOrPoison guard should be enough to help with this?

nlopes added a comment.Nov 5 2020, 5:32 AM

@nlopes I think we should adjust the funnel shift definition to say that it blocks poison on one operand if the shift amount is zero. Basically the poison semantics should be "as if" the funnel shift were expanded, which does include an explicit select for the zero shift amount case.

The issue with having instructions block poison is that then you can't remove those instruction. Right now only select and freeze block poison. So I would try to stay away of making funnel shift block poison.

Thanks @nlopes - I assume a suitably positioned isGuaranteedNotToBeUndefOrPoison guard should be enough to help with this?

Right. Or use freeze if the transformation is quite important for your benchmarks.

nikic added a comment.Nov 5 2020, 5:44 AM

@nlopes I think we should adjust the funnel shift definition to say that it blocks poison on one operand if the shift amount is zero. Basically the poison semantics should be "as if" the funnel shift were expanded, which does include an explicit select for the zero shift amount case.

The issue with having instructions block poison is that then you can't remove those instruction. Right now only select and freeze block poison. So I would try to stay away of making funnel shift block poison.

That only applies to basic instructions. Here we're talking about a function call. The poison semantics of the call depend on the implementation of the called function. If we implemented llvm.fshr.i8 in LLVM IR, it would look something like...

define i8 @llvm.fshr.i8(i8 %x, i8 %y, i8 %shamt) {
  %xyz = ...
  %ret = select i1 %cmp, i8 %y, i8 %xyz
  ret i8 %ret
}

... and would have corresponding poison semantics. Now, because it is an intrinsic, we have the technical capability of giving it different semantics, but I don't see why we should go out of the way to specify something non-standard here.

Note that we currently don't do any special modelling of poison wrt calls (apart from noundef attributes), so we are currently not making use of the fact that for most intrinsics "poison in poison out" holds.