Page MenuHomePhabricator

[ValueTracking] Don't assume we can speculate shifts
AbandonedPublic

Authored by mkuper on Oct 20 2016, 3:59 PM.

Details

Summary

Shifts are only isSafeToSpeculativelyExecute if we know the amount we're shifting by is smaller than the bitwidth of the shifted value.

This fixes PR30708

Diff Detail

Event Timeline

mkuper updated this revision to Diff 75362.Oct 20 2016, 3:59 PM
mkuper retitled this revision from to [ValueTracking] Don't assume we can speculate shifts.
mkuper updated this object.
mkuper added reviewers: davide, hfinkel, majnemer.
mkuper added a subscriber: llvm-commits.
davide edited edge metadata.Oct 20 2016, 4:02 PM

LGTM, modulo nit. This was a little bit painful.

lib/Analysis/ValueTracking.cpp
3217

Nit: I think the LLVM spelling is FIXME

davide accepted this revision.Oct 20 2016, 4:02 PM
davide edited edge metadata.
This revision is now accepted and ready to land.Oct 20 2016, 4:02 PM
efriedma requested changes to this revision.Oct 20 2016, 4:07 PM
efriedma added a reviewer: efriedma.
efriedma added a subscriber: efriedma.

"A shift is undefined if the second operand is equal or larger than the number of bits in the first operand."

Yes... but that's not undefined behavior. LangRef just says "the result is undefined".

This revision now requires changes to proceed.Oct 20 2016, 4:07 PM
mkuper added inline comments.Oct 20 2016, 4:09 PM
lib/Analysis/ValueTracking.cpp
3217

This is really inconsistent, both are used.

lib$ grep -R "// TODO" | wc -l
984
lib$ grep -R "// FIXME" | wc -l
2213

We do consistently have a space after the // , though.
I'll change to "// FIXME:" to match the leading style. :-)

"A shift is undefined if the second operand is equal or larger than the number of bits in the first operand."

Yes... but that's not undefined behavior. LangRef just says "the result is undefined".

hmm, does this change the fact that we don't want to speculate in this case or you're commenting on the wording?

sanjoy added a subscriber: sanjoy.Oct 20 2016, 4:20 PM

This looks wrong -- shifts should always be safe to speculate. I wasn't following PR30708 closely, but can you describe why you think shift speculation is the root cause for PR30708?

In LangRef "the result is undefined" essentially means "returns undef", like a load from uninitialized memory. There isn't any reason we can't speculate a shift, as long as the result isn't actually used for anything.

I would guess that we're performing a transformation which assumes that "lshr i32 1, %n" returns either 1 or 0, which isn't correct for n >= 32.

I think you're right, I misread the LangRef. Back to the drawing board.

This looks wrong -- shifts should always be safe to speculate. I wasn't following PR30708 closely, but can you describe why you think shift speculation is the root cause for PR30708?

Because of this comment on PR30708:

This instruction:

%shr.i.us21 = lshr i32 1, 53

has UB as we're trying to shift right > 32

But, as Eli pointed out (thanks!), this isn't true.

This looks wrong -- shifts should always be safe to speculate. I wasn't following PR30708 closely, but can you describe why you think shift speculation is the root cause for PR30708?

Because of this comment on PR30708:

This instruction:

%shr.i.us21 = lshr i32 1, 53

has UB as we're trying to shift right > 32

But, as Eli pointed out (thanks!), this isn't true.

Oh, sorry, this is entirely my fault. I misread result undefined == undefined behaviour, that's where the confusion started. Sorry again!

mkuper abandoned this revision.Oct 20 2016, 4:34 PM

Nah, I've read the same text (several times, for each type of shift) and didn't catch it either. :-)
Sorry for the noise.