Cranmer, Joshua via llvm-dev
2021-Nov-18 21:03 UTC
[llvm-dev] Complex intrinsics proposal and roundtable
This is another proposal about introducing complex types into LLVM. Following on from https://lists.llvm.org/pipermail/llvm-dev/2019-October/136100.html, this is different in that it doesn't propose complex types directly but instead proposes representing complex numbers as vectors and using intrinsics. See also Florian's proposal to do this (starting with complex multiply) here: https://lists.llvm.org/pipermail/llvm-dev/2020-November/146568.html. Representation of complex types The proposal is to represent complex numbers as vectors of 2N floating-point types. For example, <2 x float> would represent a scalar complex number. <4 x float> would represent a vector of 2 complex floating-point numbers, with the first complex number living in lanes 0 and 1, and the second living in lanes 2 and 3. This representation of complex types matches the vector form in x86. The basic arithmetic operations are mapped as follows: + or -: fadd or fsub <2 x float> %a, %b *: call <2 x float> @llvm.complex.multiply(<2 x float> %a, <2 x float> %b) /: call <2 x float> @llvm.complex.divide(<2 x float> %a, <2 x float> %b) Building complex values, creal, cimag: existing extractvalue, insertvalue, and shufflevector instructions as appropriate cabs: call float @llvm.complex.abs(<2 x float> %val) cconj: call <2 x float> @llvm.complex.conj(<2 x float> %val) One complexity that hasn't been covered in prior proposals is what complex multiplication actually means. Among our major source languages (C/C++/Fortran), there is some variance as to the definition of multiplication, division, and complex absolute values. This variation is most acute when looking at division. The naïve expansion of computing (a + bi)/(c + di) is denom = c * c + d * d real = (a * c + b * d) / denom imag = (b * c - a * d) / denom If you use Fortran, there is a requirement that the division operation be scaled to prevent overflow in computing denom (at the very least, this is how I've seen existing Fortran compilers implement it). If you use C, there is an additional requirement that the resulting complex number be recomputed to infinity for certain cases where real and imaginary are both NaN (see Annex G of the C standard). Using the CX_LIMITED_RANGE pragma, or equivalent command-line option, lifts both of these requirements. Additionally, gcc provides a -fcx-fortran-rules that lifts only the latter requirement. My understanding is that all hardware implementations of complex multiply implement CX_LIMITED_RANGE rules. My proposal is to distinguish between these situations using a mixture of existing fast-math flags and call-site attributes. Without any flags or call-site attributes, these intrinsics would expand to their compiler-rt equivalents of __mulsc3, __divsc3, etc., which is to say they would have full C requirements (both NaN checking and scaling). The "complex-limited-range" call-site attribute would disable both of these requirements. The "complex-no-scale" call-site attribute would disable the specific scaling requirement but retain the NaN checking behavior. Additionally, fast math flags can be used to generate behavior: nnan or ninf would trigger the dropping of the NaN checking code by itself. Implementation experience I have been able to implement patches that pattern-match for complex multiply and divide (in the CX_LIMITED_RANGE cases) early in InstCombine, and haven't seen issues with that. Doing codegen for the non-CX_LIMITED_RANGE case, requiring a call to __mulsc3, is difficult because that function returns a C _Complex number, and the C ABIs for complex numbers tend to be inconsistent even among different floating-point types within the same architecture. The truly evil case is the i386 ABI for float, which is returned as edx:eax (or i64, as generated by clang). If you want to talk more about this, I have a roundtable tomorrow, Friday, at 14:45 Eastern or 11:45 Pacific. -- Joshua Cranmer -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20211118/ba6f0f66/attachment.html>
Sjoerd Meijer via llvm-dev
2021-Nov-19 07:31 UTC
[llvm-dev] Complex intrinsics proposal and roundtable
FYI, Nick just uploaded this protytype: https://reviews.llvm.org/D114174 ________________________________ From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Cranmer, Joshua via llvm-dev <llvm-dev at lists.llvm.org> Sent: 18 November 2021 21:03 To: llvm-dev at lists.llvm.org <llvm-dev at lists.llvm.org> Subject: [llvm-dev] Complex intrinsics proposal and roundtable This is another proposal about introducing complex types into LLVM. Following on from https://lists.llvm.org/pipermail/llvm-dev/2019-October/136100.html, this is different in that it doesn’t propose complex types directly but instead proposes representing complex numbers as vectors and using intrinsics. See also Florian’s proposal to do this (starting with complex multiply) here: https://lists.llvm.org/pipermail/llvm-dev/2020-November/146568.html. Representation of complex types The proposal is to represent complex numbers as vectors of 2N floating-point types. For example, <2 x float> would represent a scalar complex number. <4 x float> would represent a vector of 2 complex floating-point numbers, with the first complex number living in lanes 0 and 1, and the second living in lanes 2 and 3. This representation of complex types matches the vector form in x86. The basic arithmetic operations are mapped as follows: + or -: fadd or fsub <2 x float> %a, %b *: call <2 x float> @llvm.complex.multiply(<2 x float> %a, <2 x float> %b) /: call <2 x float> @llvm.complex.divide(<2 x float> %a, <2 x float> %b) Building complex values, creal, cimag: existing extractvalue, insertvalue, and shufflevector instructions as appropriate cabs: call float @llvm.complex.abs(<2 x float> %val) cconj: call <2 x float> @llvm.complex.conj(<2 x float> %val) One complexity that hasn’t been covered in prior proposals is what complex multiplication actually means. Among our major source languages (C/C++/Fortran), there is some variance as to the definition of multiplication, division, and complex absolute values. This variation is most acute when looking at division. The naïve expansion of computing (a + bi)/(c + di) is denom = c * c + d * d real = (a * c + b * d) / denom imag = (b * c - a * d) / denom If you use Fortran, there is a requirement that the division operation be scaled to prevent overflow in computing denom (at the very least, this is how I’ve seen existing Fortran compilers implement it). If you use C, there is an additional requirement that the resulting complex number be recomputed to infinity for certain cases where real and imaginary are both NaN (see Annex G of the C standard). Using the CX_LIMITED_RANGE pragma, or equivalent command-line option, lifts both of these requirements. Additionally, gcc provides a -fcx-fortran-rules that lifts only the latter requirement. My understanding is that all hardware implementations of complex multiply implement CX_LIMITED_RANGE rules. My proposal is to distinguish between these situations using a mixture of existing fast-math flags and call-site attributes. Without any flags or call-site attributes, these intrinsics would expand to their compiler-rt equivalents of __mulsc3, __divsc3, etc., which is to say they would have full C requirements (both NaN checking and scaling). The “complex-limited-range” call-site attribute would disable both of these requirements. The “complex-no-scale” call-site attribute would disable the specific scaling requirement but retain the NaN checking behavior. Additionally, fast math flags can be used to generate behavior: nnan or ninf would trigger the dropping of the NaN checking code by itself. Implementation experience I have been able to implement patches that pattern-match for complex multiply and divide (in the CX_LIMITED_RANGE cases) early in InstCombine, and haven’t seen issues with that. Doing codegen for the non-CX_LIMITED_RANGE case, requiring a call to __mulsc3, is difficult because that function returns a C _Complex number, and the C ABIs for complex numbers tend to be inconsistent even among different floating-point types within the same architecture. The truly evil case is the i386 ABI for float, which is returned as edx:eax (or i64, as generated by clang). If you want to talk more about this, I have a roundtable tomorrow, Friday, at 14:45 Eastern or 11:45 Pacific. -- Joshua Cranmer -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20211119/284ecd32/attachment.html>
Chris Lattner via llvm-dev
2021-Nov-23 07:51 UTC
[llvm-dev] Complex intrinsics proposal and roundtable
Hi Joshua, I think that using 2x elements is a much more promising direction. Question though: how much value is there in making these be target independent intrinsics? Are these actually general portable enough (across architectures) to be worth abstracting for a frontend? If the frontend has to handle all the complexity anyway (e.g. your point about multiply and divide are on point), there is little benefit to adding these. Separately, do you plan to handle complex integers? Do you plan to support arbitrary bit width elements, and what is the legalization scheme for these? -Chris> On Nov 18, 2021, at 11:03 AM, Cranmer, Joshua via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > This is another proposal about introducing complex types into LLVM. Following on from https://lists.llvm.org/pipermail/llvm-dev/2019-October/136100.html <https://lists.llvm.org/pipermail/llvm-dev/2019-October/136100.html>, this is different in that it doesn’t propose complex types directly but instead proposes representing complex numbers as vectors and using intrinsics. See also Florian’s proposal to do this (starting with complex multiply) here: https://lists.llvm.org/pipermail/llvm-dev/2020-November/146568.html <https://lists.llvm.org/pipermail/llvm-dev/2020-November/146568.html>. > > Representation of complex types > > The proposal is to represent complex numbers as vectors of 2N floating-point types. For example, <2 x float> would represent a scalar complex number. <4 x float> would represent a vector of 2 complex floating-point numbers, with the first complex number living in lanes 0 and 1, and the second living in lanes 2 and 3. This representation of complex types matches the vector form in x86. > > The basic arithmetic operations are mapped as follows: > + or -: fadd or fsub <2 x float> %a, %b > *: call <2 x float> @llvm.complex.multiply(<2 x float> %a, <2 x float> %b) > /: call <2 x float> @llvm.complex.divide(<2 x float> %a, <2 x float> %b) > Building complex values, creal, cimag: existing extractvalue, insertvalue, and shufflevector instructions as appropriate > cabs: call float @llvm.complex.abs(<2 x float> %val) > cconj: call <2 x float> @llvm.complex.conj(<2 x float> %val) > > One complexity that hasn’t been covered in prior proposals is what complex multiplication actually means. Among our major source languages (C/C++/Fortran), there is some variance as to the definition of multiplication, division, and complex absolute values. This variation is most acute when looking at division. The naïve expansion of computing (a + bi)/(c + di) is > denom = c * c + d * d > real = (a * c + b * d) / denom > imag = (b * c - a * d) / denom > > If you use Fortran, there is a requirement that the division operation be scaled to prevent overflow in computing denom (at the very least, this is how I’ve seen existing Fortran compilers implement it). If you use C, there is an additional requirement that the resulting complex number be recomputed to infinity for certain cases where real and imaginary are both NaN (see Annex G of the C standard). Using the CX_LIMITED_RANGE pragma, or equivalent command-line option, lifts both of these requirements. Additionally, gcc provides a -fcx-fortran-rules that lifts only the latter requirement. My understanding is that all hardware implementations of complex multiply implement CX_LIMITED_RANGE rules. > > My proposal is to distinguish between these situations using a mixture of existing fast-math flags and call-site attributes. Without any flags or call-site attributes, these intrinsics would expand to their compiler-rt equivalents of __mulsc3, __divsc3, etc., which is to say they would have full C requirements (both NaN checking and scaling). The “complex-limited-range” call-site attribute would disable both of these requirements. The “complex-no-scale” call-site attribute would disable the specific scaling requirement but retain the NaN checking behavior. Additionally, fast math flags can be used to generate behavior: nnan or ninf would trigger the dropping of the NaN checking code by itself. > > Implementation experience > > I have been able to implement patches that pattern-match for complex multiply and divide (in the CX_LIMITED_RANGE cases) early in InstCombine, and haven’t seen issues with that. Doing codegen for the non-CX_LIMITED_RANGE case, requiring a call to __mulsc3, is difficult because that function returns a C _Complex number, and the C ABIs for complex numbers tend to be inconsistent even among different floating-point types within the same architecture. The truly evil case is the i386 ABI for float, which is returned as edx:eax (or i64, as generated by clang). > > If you want to talk more about this, I have a roundtable tomorrow, Friday, at 14:45 Eastern or 11:45 Pacific. > > > -- > Joshua Cranmer > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20211122/ed1d5d44/attachment.html>