Page MenuHomePhabricator

[LangRef] Make @llvm.sqrt(x) return undef, rather than have UB, for negative x.
ClosedPublic

Authored by jlebar on Jan 17 2017, 12:15 AM.

Details

Summary

Some frontends emit a speculate-and-select idiom for sqrt, wherein they compute
sqrt(x), check if x is negative, and select NaN if it is:

%cmp = fcmp olt double %a, -0.000000e+00
%sqrt = call double @llvm.sqrt.f64(double %a)
%ret = select i1 %cmp, double 0x7FF8000000000000, double %sqrt

This is technically UB as the LangRef is written today if %a is ever less than
-0. But emitting code that's compliant with the current definition of sqrt
would require a branch, which would then prevent us from matching this idiom in
SelectionDAG (which we do today -- ISD::FSQRT has defined behavior on negative
inputs), because SelectionDAG looks at one BB at a time.

Nothing in LLVM takes advantage of this undefined behavior, as far as we can
tell, and the fact that llvm.sqrt has UB dates from its initial addition to the
LangRef.

Diff Detail

Repository
rL LLVM

Event Timeline

jlebar created this revision.Jan 17 2017, 12:15 AM
mehdi_amini accepted this revision.Jan 17 2017, 8:13 AM

LGTM.
Maybe sanity check with Sanjoy?

llvm/docs/LangRef.rst
10064 ↗(On Diff #84640)

I believe that usually it spells "returns undef" or "the result is undefined".

This revision is now accepted and ready to land.Jan 17 2017, 8:13 AM
sanjoy accepted this revision.Jan 17 2017, 8:44 AM
sanjoy added a subscriber: sanjoy.

This LGTM; especially since llvm::isSafeToSpeculativelyExecute already returns true for calls to llvm.sqrt (so if some place in LLVM thinks llvm.sqrt may have UB, we're already miscompiling).

efriedma requested changes to this revision.Jan 17 2017, 11:44 AM
efriedma added a subscriber: efriedma.

Nothing in LLVM takes advantage of this undefined behavior, as far as we can tell, and the fact that llvm.sqrt has UB dates from its initial addition to the LangRef.

This is false: we take advantage of this to lower @llvm.sqrt() to libm sqrt() on platforms which don't have a native sqrt instruction, and that can have side-effects. See also https://reviews.llvm.org/D28335 .

This revision now requires changes to proceed.Jan 17 2017, 11:44 AM

This is false: we take advantage of this to lower @llvm.sqrt() to libm sqrt() on platforms which don't have a native sqrt instruction, and that can have side-effects. See also https://reviews.llvm.org/D28335 .

Sigh.

We can lower it to if (x >= -0) libm_sqrt(x) else NaN? It's already broken per Sanjoy's comment.

I would like to make this langref change because I want to convert the opaque target-specific llvm.nvvm.sqrt.f intrinsic to something involving llvm.sqrt.f32 (so that all of our sqrt-optimization machinery can be brought to bear).

Nothing in LLVM takes advantage of this undefined behavior, as far as we can tell, and the fact that llvm.sqrt has UB dates from its initial addition to the LangRef.

This is false: we take advantage of this to lower @llvm.sqrt() to libm sqrt() on platforms which don't have a native sqrt instruction, and that can have side-effects. See also https://reviews.llvm.org/D28335 .

What about NaN? A NaN input is legal according to LangRef AFAICT, and errno would still be set. That would lead me to think that lowering unconditionally to libm sqrt() isn't correct.

hfinkel edited edge metadata.Jan 17 2017, 12:00 PM

Nothing in LLVM takes advantage of this undefined behavior, as far as we can tell, and the fact that llvm.sqrt has UB dates from its initial addition to the LangRef.

This is false: we take advantage of this to lower @llvm.sqrt() to libm sqrt() on platforms which don't have a native sqrt instruction, and that can have side-effects. See also https://reviews.llvm.org/D28335 .

We do, but this seems somewhat accidental. Most of the libm intrinsics have this problem, and sqrt is the only one for which we have this undefined behavior.

We can lower it to if (x >= -0) libm_sqrt(x) else NaN?

That would be correct. It's not particularly efficient, but that's not important as long as we aren't unconditionally transforming @sqrt() to @llvm.sqrt().

We do, but this seems somewhat accidental. Most of the libm intrinsics have this problem, and sqrt is the only one for which we have this undefined behavior.

Indeed. Now that I look at LegalizeDAG, I don't think it makes a lot of sense to legalize ISD::FSQRT to if (x >= -0) libm_sqrt(x) else NaN while leaving every other ExpandFPLibCall alone.

This langref change at least brings sqrt into line with the rest of the llvm math functions, and makes the legalization code as broken for it as it is for most everything else.

Indeed, one could argue that the issue in the legalization code is unrelated to this issue in the langref. ISD::FSQRT has defined behavior on negative values. The fact that we're incorrectly legalizing it to libm_sqrt arguably has nothing to do with the semantics of @llvm.sqrt.f32.

@efriedma, are you OK with this change going in, on that basis?

I'm not sure I really like the logic of "all these other intrinsics are broken, therefore we should break llvm.sqrt()", especially since we don't really use most of the intrinsics in question.

If we're going to ignore the problem, at least get rid of the "(which allows for better optimization, because there is no need to worry about errno being set)" bit.

On a mostly unrelated note, making llvm.sqrt() return undef rather than NaN for negative numbers is completely useless; we might as well just say that @llvm.sqrt is precisely the IEEE 754 squareRoot() operation minus any side-effects. We can mark a call "nnan" to indicate that the backend doesn't need to worry about negative numbers and nans.

I'm not sure I really like the logic of "all these other intrinsics are broken, therefore we should break llvm.sqrt()", especially since we don't really use most of the intrinsics in question.

If we're going to ignore the problem, at least get rid of the "(which allows for better optimization, because there is no need to worry about errno being set)" bit.

On a mostly unrelated note, making llvm.sqrt() return undef rather than NaN for negative numbers is completely useless; we might as well just say that @llvm.sqrt is precisely the IEEE 754 squareRoot() operation minus any side-effects. We can mark a call "nnan" to indicate that the backend doesn't need to worry about negative numbers and nans.

Yes! Please just remove it.

I had been under some impression that we'd have a potential problem doing this because the corresponding SDAG node inherits these undef properties, and who knows what all of the target lowering does... but it doesn't: SelectionDAGBuilder::visitCall has this:

case LibFunc::sqrt:
case LibFunc::sqrtf:
case LibFunc::sqrtl:
case LibFunc::sqrt_finite:
case LibFunc::sqrtf_finite:
case LibFunc::sqrtl_finite:
  if (visitUnaryFloatCall(I, ISD::FSQRT))
    return;
  break;

so this is just an IR issue. Let's rationalize this.

jlebar updated this revision to Diff 84744.Jan 17 2017, 2:25 PM
jlebar edited edge metadata.
jlebar marked an inline comment as done.

Update per Eli and Mehdi's comments.

jlebar added a comment.EditedJan 17 2017, 2:26 PM

I'm not sure I really like the logic of "all these other intrinsics are broken, therefore we should break llvm.sqrt()", especially since we don't really use most of the intrinsics in question.

My thinking is more along the lines of, "all of these intrinsics, including sqrt, are broken. Therefore we should at least bring the langref more in line with (a) our desired semantics and (b) the semantics that various frontends are currently using."

The reason that even sqrt is currently broken is -- at least as I understand -- the speculate-and-select IR idiom is lowered to ISD::FSQRT, which is then sometimes legalized into libm_sqrt, which may set errno. It's true that according to the langref as it exists you shouldn't write sqrt speculate-and-select, but as Sanjoy said, we mark sqrt as safe-to-speculate, so, who knows what the optimizer may do.

If we're going to ignore the problem, at least get rid of the "(which allows for better optimization, because there is no need to worry about errno being set)" bit.

Done.

Edited because phab decided to post an old version of my comment.

On a mostly unrelated note, making llvm.sqrt() return undef rather than NaN for negative numbers is completely useless; we might as well just say that @llvm.sqrt is precisely the IEEE 754 squareRoot() operation minus any side-effects. We can mark a call "nnan" to indicate that the backend doesn't need to worry about negative numbers and nans.

No response to this?

On a mostly unrelated note, making llvm.sqrt() return undef rather than NaN for negative numbers is completely useless; we might as well just say that @llvm.sqrt is precisely the IEEE 754 squareRoot() operation minus any side-effects. We can mark a call "nnan" to indicate that the backend doesn't need to worry about negative numbers and nans.

No response to this?

Discussed on IRC with Hal, he convinced me to try to make LLVM think that llvm.sqrt returns NaN for negative inputs, and then of course we can update the langref as you suggest.

No promises I'll be able to make it work. And with the changes I plan, we will continue to have the problem of legalizing llvm.sqrt to libm_sqrt, incorrectly adding side-effects to the function call, as we do for most of the other intrinsics.

efriedma accepted this revision.Jan 17 2017, 2:45 PM

Fine, I guess... I'll try to find time to fix llvm.sqrt() lowering.

This revision is now accepted and ready to land.Jan 17 2017, 2:45 PM
jlebar planned changes to this revision.Jan 17 2017, 4:07 PM

Re-requesting review on this. I've added as deps the only changes I believe we need to make in order to make our handling of llvm.sqrt as correct as our handling of the other transcendental intrinsics.

jlebar requested review of this revision.Jan 19 2017, 4:52 PM
This revision is now accepted and ready to land.Jan 19 2017, 4:52 PM

Is everyone happy with this change? I'm about to land D28928, which is the last prerequisite to this.

Hearing no objections, I'm pushing this now.

This revision was automatically updated to reflect the committed changes.