Hey all, I volunteered to put together a proposal regard complex in LLVM. Consider the following to be a strawman meant to spark discussion. It's based on real-world experience with complex but is not expected to cover all use-cases. Proposal to Support Complex Operations in LLVM ---------------------------------------------- Abstract Several vendors and individuals have proposed first-class complex support in LLVM. Goals of this proposal include better optimization, diagnostics and general user experience. Introduction and Motivation Recently the topic of complex numbers arose on llvm-dev with several developers expressing a desire for first-class IR support for complex [1] [2]. Interest in complex numbers in LLVM goes back much further [3]. Currently clang chooses to represent standard types like "double complex" and "std::complex<float>" as structure types containing two scalar fields, for example {double, double}. Consequently, arrays of complex type are represented as, for example, [8 x {double, double}]. This has consequences for how clang converts complex operations to LLVM IR. In general, clang emits loads of the individual real and imaginary parts and feeds them into arithmetic operations. Vectorization results in many shufflevector operations to massage the data into sequences suitable for vector arithmetic. All of the real/imaginary data manipulation obscures the underlying arithmetic. It makes it difficult to reason about the algebraic properties of expressions. For expressiveness and optimization ability, it will be nice to have a higher-level representation for complex in LLVM IR. In general, it is desirable to defer lowering of complex until the optimizer has had a reasonable chance to exploit its properties. First-class support for complex can also improve the user experience. Diagnostics could express concepts in the complex domain instead of referring to expressions containing shuffles and other low-level data manipulation. Users that wish to examine IR directly will see much less gobbbledygook and can more easily reason about the IR. Types This proposal introduces new Single Value types to represent complex numbers. c32 - like float complex or std::complex<float> c64 - like double complex or std::complex<double> We defer a c128 type (like std::complex<long double>) for a future RFC. Note that the references to C and C++ types above are simply explanatory. Nothing in this proposal assumes any particular high-level language type will map to the above LLVM types. The sizes of the types are 64 and 128 bits, respectively (this is assumed by the ValueTypes given below) and the real part of the complex will appear first in the layout of the types. The format of the real and imaginary parts is the same as for float and double, respectively. This should map to most common data representations of complex in various languages. These types are *not* considered floating point types for the purposes of Type::isFloatTy and friends, llvm_anyfloat_ty, etc. in order to limit surprises when introducing these types. New APIs will allow querying and creation of complex types: bool Type::isComplexTy() const; bool Type::isComplex32Ty() const; bool Type::isComplex64Ty() const; Analogous ValueTypes will be used by intrinsics. def c32 : ValueType<64, xxx> def c64 : ValueType<128, yyy> def llvm_anycomplex_ty : LLVMType<Any>; def llvm_c32_ty : LLVMType<c32>; def llvm_c64_ty : LLVMType<c64>; The numbering of the ValueTypes will be determined after discussion. It may be desirable to insert them before the existing vector types, grouping them with the other scalar types or we may want to put them somewhere else. Operations This proposal overloads existing floating point instructions for complex types in order to leverage existing expression optimizations: c64 %res = fadd c64 %a, c64 %b v8c64 %res = fsub v8c64 %a, v8c64 %b c32 %res = fmul c64 %a, c64 %b v4c32 %res = fdiv v4c64 %a, v4c64 %b The only valid comparisons of complex values will be equality: i1 %res = eq c32 %a, c32 %b i8 %res = eq v8c32 %a, v8c32 %b i1 %res = ne c64 %a, c64 %b i8 %res = ne v8c64 %a, v8c64 %b select is defined for complex: c32 = select i1 %cmp, c32 %a, c32 %b v4c64 = select i4 %cmp, v4c64 %a, v4c64 %b Complex values may be casted to other complex types: c32 %res = fptrunc c64 %a to c32 c64 %res = fpext c32 %a to c64 We may also overload existing intrinsics. declare c32 @llvm.sqrt.c32(c32 %Val) declare c64 @llvm.sqrt.c64(c64 %Val) declare c32 @llvm.pow.c32(c32 %Val, c32 %Power) declare c64 @llvm.pow.c64(c64 %Val, c64 %Power) declare c32 @llvm.sin.c32(c32 %Val) declare c64 @llvm.sin.c64(c64 %Val) declare c32 @llvm.cos.c32(c32 %Val) declare c64 @llvm.cos.c64(c64 %Val) declare c32 @llvm.log.c32(c32 %Val) declare c64 @llvm.log.c64(c64 %Val) declare float @llvm.fabs.c32(c32 %Val) declare double @llvm.fabs.c64(c64 %Val) In addition, new intrinsics will be used for complex-specific operations: llvm.creal.* - Overloaded intrinsic to extract the real part of a complex value declare float @llvm.creal.c32(c32 %Val) declare double @llvm.creal.c64(c64 %Val) llvm.cimag.* - Overloaded intrinsic to extract the imaginary part of a complex value declare float @llvm.cimag.c32(c32 %Val) declare double @llvm.cimag.c64(c64 %Val) llvm.cconj.* - Overloaded intrinsic to compute the conjugate of a complex value declare c32 @llvm.cconj.c32(c32 %Val) declare c64 @llvm.cconj.c64(c64 %Val) Summary This proposal introduced new complex types: c32 and c64. The proposal overloads existing floating point instructions and intrinsics for common complex operations and introduces new intrinsics for complex-specific operations. Goals of this work include better reasoning about complex operations within LLVM, leading to better optimization, reporting and overall user experience. This is an early draft and subject to change. [1] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131516.html [2] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131523.html [3] http://lists.llvm.org/pipermail/llvm-dev/2010-December/037072.html
Hi David — What do you intend the semantics of the fmul and fdiv operations to be for these types? Do them implement the C semantics (avoid spurious overflow/underflow)? The naive arithmetic (some fortran implementations)? Is FMA licensed in their evaluation? – Steve> On Jul 1, 2019, at 2:56 PM, David Greene via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > Hey all, > > I volunteered to put together a proposal regard complex in LLVM. > Consider the following to be a strawman meant to spark discussion. It's > based on real-world experience with complex but is not expected to cover > all use-cases. > > Proposal to Support Complex Operations in LLVM > ---------------------------------------------- > > Abstract > > Several vendors and individuals have proposed first-class complex > support in LLVM. Goals of this proposal include better optimization, > diagnostics and general user experience. > > Introduction and Motivation > > Recently the topic of complex numbers arose on llvm-dev with several > developers expressing a desire for first-class IR support for complex > [1] [2]. Interest in complex numbers in LLVM goes back much further > [3]. > > Currently clang chooses to represent standard types like "double > complex" and "std::complex<float>" as structure types containing two > scalar fields, for example {double, double}. Consequently, arrays of > complex type are represented as, for example, [8 x {double, double}]. > This has consequences for how clang converts complex operations to LLVM > IR. In general, clang emits loads of the individual real and imaginary > parts and feeds them into arithmetic operations. Vectorization results > in many shufflevector operations to massage the data into sequences > suitable for vector arithmetic. > > All of the real/imaginary data manipulation obscures the underlying > arithmetic. It makes it difficult to reason about the algebraic > properties of expressions. For expressiveness and optimization ability, > it will be nice to have a higher-level representation for complex in > LLVM IR. In general, it is desirable to defer lowering of complex until > the optimizer has had a reasonable chance to exploit its properties. > > First-class support for complex can also improve the user experience. > Diagnostics could express concepts in the complex domain instead of > referring to expressions containing shuffles and other low-level data > manipulation. Users that wish to examine IR directly will see much less > gobbbledygook and can more easily reason about the IR. > > Types > > This proposal introduces new Single Value types to represent complex > numbers. > > c32 - like float complex or std::complex<float> > c64 - like double complex or std::complex<double> > > We defer a c128 type (like std::complex<long double>) for a future > RFC. > > Note that the references to C and C++ types above are simply > explanatory. Nothing in this proposal assumes any particular high-level > language type will map to the above LLVM types. > > The sizes of the types are 64 and 128 bits, respectively (this is > assumed by the ValueTypes given below) and the real part of the complex > will appear first in the layout of the types. The format of the real > and imaginary parts is the same as for float and double, respectively. > This should map to most common data representations of complex in > various languages. > > These types are *not* considered floating point types for the purposes > of Type::isFloatTy and friends, llvm_anyfloat_ty, etc. in order to limit > surprises when introducing these types. New APIs will allow querying > and creation of complex types: > > bool Type::isComplexTy() const; > bool Type::isComplex32Ty() const; > bool Type::isComplex64Ty() const; > > Analogous ValueTypes will be used by intrinsics. > > def c32 : ValueType<64, xxx> > def c64 : ValueType<128, yyy> > > def llvm_anycomplex_ty : LLVMType<Any>; > def llvm_c32_ty : LLVMType<c32>; > def llvm_c64_ty : LLVMType<c64>; > > The numbering of the ValueTypes will be determined after discussion. It > may be desirable to insert them before the existing vector types, > grouping them with the other scalar types or we may want to put them > somewhere else. > > Operations > > This proposal overloads existing floating point instructions for complex > types in order to leverage existing expression optimizations: > > c64 %res = fadd c64 %a, c64 %b > v8c64 %res = fsub v8c64 %a, v8c64 %b > c32 %res = fmul c64 %a, c64 %b > v4c32 %res = fdiv v4c64 %a, v4c64 %b > > The only valid comparisons of complex values will be equality: > > i1 %res = eq c32 %a, c32 %b > i8 %res = eq v8c32 %a, v8c32 %b > i1 %res = ne c64 %a, c64 %b > i8 %res = ne v8c64 %a, v8c64 %b > > select is defined for complex: > > c32 = select i1 %cmp, c32 %a, c32 %b > > v4c64 = select i4 %cmp, v4c64 %a, v4c64 %b > > Complex values may be casted to other complex types: > > c32 %res = fptrunc c64 %a to c32 > c64 %res = fpext c32 %a to c64 > > We may also overload existing intrinsics. > > declare c32 @llvm.sqrt.c32(c32 %Val) > declare c64 @llvm.sqrt.c64(c64 %Val) > > declare c32 @llvm.pow.c32(c32 %Val, c32 %Power) > declare c64 @llvm.pow.c64(c64 %Val, c64 %Power) > > declare c32 @llvm.sin.c32(c32 %Val) > declare c64 @llvm.sin.c64(c64 %Val) > > declare c32 @llvm.cos.c32(c32 %Val) > declare c64 @llvm.cos.c64(c64 %Val) > > declare c32 @llvm.log.c32(c32 %Val) > declare c64 @llvm.log.c64(c64 %Val) > > declare float @llvm.fabs.c32(c32 %Val) > declare double @llvm.fabs.c64(c64 %Val) > > In addition, new intrinsics will be used for complex-specific > operations: > > llvm.creal.* - Overloaded intrinsic to extract the real part of a > complex value > declare float @llvm.creal.c32(c32 %Val) > declare double @llvm.creal.c64(c64 %Val) > > llvm.cimag.* - Overloaded intrinsic to extract the imaginary part of a > complex value > declare float @llvm.cimag.c32(c32 %Val) > declare double @llvm.cimag.c64(c64 %Val) > > llvm.cconj.* - Overloaded intrinsic to compute the conjugate of a > complex value > declare c32 @llvm.cconj.c32(c32 %Val) > declare c64 @llvm.cconj.c64(c64 %Val) > > Summary > > This proposal introduced new complex types: c32 and c64. The proposal > overloads existing floating point instructions and intrinsics for common > complex operations and introduces new intrinsics for complex-specific > operations. > > Goals of this work include better reasoning about complex operations > within LLVM, leading to better optimization, reporting and overall user > experience. > > This is an early draft and subject to change. > > [1] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131516.html > [2] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131523.html > [3] http://lists.llvm.org/pipermail/llvm-dev/2010-December/037072.html > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Hi David, IIUC your proposal preserves the current ABI? Thanks, JF> On Jul 1, 2019, at 11:56 AM, David Greene via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > Hey all, > > I volunteered to put together a proposal regard complex in LLVM. > Consider the following to be a strawman meant to spark discussion. It's > based on real-world experience with complex but is not expected to cover > all use-cases. > > Proposal to Support Complex Operations in LLVM > ---------------------------------------------- > > Abstract > > Several vendors and individuals have proposed first-class complex > support in LLVM. Goals of this proposal include better optimization, > diagnostics and general user experience. > > Introduction and Motivation > > Recently the topic of complex numbers arose on llvm-dev with several > developers expressing a desire for first-class IR support for complex > [1] [2]. Interest in complex numbers in LLVM goes back much further > [3]. > > Currently clang chooses to represent standard types like "double > complex" and "std::complex<float>" as structure types containing two > scalar fields, for example {double, double}. Consequently, arrays of > complex type are represented as, for example, [8 x {double, double}]. > This has consequences for how clang converts complex operations to LLVM > IR. In general, clang emits loads of the individual real and imaginary > parts and feeds them into arithmetic operations. Vectorization results > in many shufflevector operations to massage the data into sequences > suitable for vector arithmetic. > > All of the real/imaginary data manipulation obscures the underlying > arithmetic. It makes it difficult to reason about the algebraic > properties of expressions. For expressiveness and optimization ability, > it will be nice to have a higher-level representation for complex in > LLVM IR. In general, it is desirable to defer lowering of complex until > the optimizer has had a reasonable chance to exploit its properties. > > First-class support for complex can also improve the user experience. > Diagnostics could express concepts in the complex domain instead of > referring to expressions containing shuffles and other low-level data > manipulation. Users that wish to examine IR directly will see much less > gobbbledygook and can more easily reason about the IR. > > Types > > This proposal introduces new Single Value types to represent complex > numbers. > > c32 - like float complex or std::complex<float> > c64 - like double complex or std::complex<double> > > We defer a c128 type (like std::complex<long double>) for a future > RFC. > > Note that the references to C and C++ types above are simply > explanatory. Nothing in this proposal assumes any particular high-level > language type will map to the above LLVM types. > > The sizes of the types are 64 and 128 bits, respectively (this is > assumed by the ValueTypes given below) and the real part of the complex > will appear first in the layout of the types. The format of the real > and imaginary parts is the same as for float and double, respectively. > This should map to most common data representations of complex in > various languages. > > These types are *not* considered floating point types for the purposes > of Type::isFloatTy and friends, llvm_anyfloat_ty, etc. in order to limit > surprises when introducing these types. New APIs will allow querying > and creation of complex types: > > bool Type::isComplexTy() const; > bool Type::isComplex32Ty() const; > bool Type::isComplex64Ty() const; > > Analogous ValueTypes will be used by intrinsics. > > def c32 : ValueType<64, xxx> > def c64 : ValueType<128, yyy> > > def llvm_anycomplex_ty : LLVMType<Any>; > def llvm_c32_ty : LLVMType<c32>; > def llvm_c64_ty : LLVMType<c64>; > > The numbering of the ValueTypes will be determined after discussion. It > may be desirable to insert them before the existing vector types, > grouping them with the other scalar types or we may want to put them > somewhere else. > > Operations > > This proposal overloads existing floating point instructions for complex > types in order to leverage existing expression optimizations: > > c64 %res = fadd c64 %a, c64 %b > v8c64 %res = fsub v8c64 %a, v8c64 %b > c32 %res = fmul c64 %a, c64 %b > v4c32 %res = fdiv v4c64 %a, v4c64 %b > > The only valid comparisons of complex values will be equality: > > i1 %res = eq c32 %a, c32 %b > i8 %res = eq v8c32 %a, v8c32 %b > i1 %res = ne c64 %a, c64 %b > i8 %res = ne v8c64 %a, v8c64 %b > > select is defined for complex: > > c32 = select i1 %cmp, c32 %a, c32 %b > > v4c64 = select i4 %cmp, v4c64 %a, v4c64 %b > > Complex values may be casted to other complex types: > > c32 %res = fptrunc c64 %a to c32 > c64 %res = fpext c32 %a to c64 > > We may also overload existing intrinsics. > > declare c32 @llvm.sqrt.c32(c32 %Val) > declare c64 @llvm.sqrt.c64(c64 %Val) > > declare c32 @llvm.pow.c32(c32 %Val, c32 %Power) > declare c64 @llvm.pow.c64(c64 %Val, c64 %Power) > > declare c32 @llvm.sin.c32(c32 %Val) > declare c64 @llvm.sin.c64(c64 %Val) > > declare c32 @llvm.cos.c32(c32 %Val) > declare c64 @llvm.cos.c64(c64 %Val) > > declare c32 @llvm.log.c32(c32 %Val) > declare c64 @llvm.log.c64(c64 %Val) > > declare float @llvm.fabs.c32(c32 %Val) > declare double @llvm.fabs.c64(c64 %Val) > > In addition, new intrinsics will be used for complex-specific > operations: > > llvm.creal.* - Overloaded intrinsic to extract the real part of a > complex value > declare float @llvm.creal.c32(c32 %Val) > declare double @llvm.creal.c64(c64 %Val) > > llvm.cimag.* - Overloaded intrinsic to extract the imaginary part of a > complex value > declare float @llvm.cimag.c32(c32 %Val) > declare double @llvm.cimag.c64(c64 %Val) > > llvm.cconj.* - Overloaded intrinsic to compute the conjugate of a > complex value > declare c32 @llvm.cconj.c32(c32 %Val) > declare c64 @llvm.cconj.c64(c64 %Val) > > Summary > > This proposal introduced new complex types: c32 and c64. The proposal > overloads existing floating point instructions and intrinsics for common > complex operations and introduces new intrinsics for complex-specific > operations. > > Goals of this work include better reasoning about complex operations > within LLVM, leading to better optimization, reporting and overall user > experience. > > This is an early draft and subject to change. > > [1] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131516.html > [2] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131523.html > [3] http://lists.llvm.org/pipermail/llvm-dev/2010-December/037072.html > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
On 7/1/19 1:56 PM, David Greene via llvm-dev wrote:> Hey all, > > I volunteered to put together a proposal regard complex in LLVM. > Consider the following to be a strawman meant to spark discussion. It's > based on real-world experience with complex but is not expected to cover > all use-cases. > > Proposal to Support Complex Operations in LLVM > ---------------------------------------------- > > Abstract > > Several vendors and individuals have proposed first-class complex > support in LLVM. Goals of this proposal include better optimization, > diagnostics and general user experience. > > Introduction and Motivation > > Recently the topic of complex numbers arose on llvm-dev with several > developers expressing a desire for first-class IR support for complex > [1] [2]. Interest in complex numbers in LLVM goes back much further > [3]. > > Currently clang chooses to represent standard types like "double > complex" and "std::complex<float>" as structure types containing two > scalar fields, for example {double, double}.To supplement this, on some ABIs (e.g., PPC64 ELFv2), Clang represents complex numbers as two-element arrays. This makes backend pattern matching even more fragile because the representation is different for different ABIs. Having an IR type would resolve this issue and making writing IR-level transformations that operate on complex numbers more robust.> Consequently, arrays of > complex type are represented as, for example, [8 x {double, double}]. > This has consequences for how clang converts complex operations to LLVM > IR. In general, clang emits loads of the individual real and imaginary > parts and feeds them into arithmetic operations. Vectorization results > in many shufflevector operations to massage the data into sequences > suitable for vector arithmetic. > > All of the real/imaginary data manipulation obscures the underlying > arithmetic. It makes it difficult to reason about the algebraic > properties of expressions. For expressiveness and optimization ability, > it will be nice to have a higher-level representation for complex in > LLVM IR. In general, it is desirable to defer lowering of complex until > the optimizer has had a reasonable chance to exploit its properties.I think that it's really important that we're specific about the goals here. Exactly what kinds of optimizations are we aiming to (more-easily) enable? There certainly exists hardware with instructions that help vectorize complex multiplication, for example, and having a builtin complex type would make writing patterns for those instructions easier (as opposed to trying to build matching into the SLP vectorizer or elsewhere). This probably makes constant-folding calls to complex libm functions easier. Does this make loop vectorization easier or harder? Do you expect the vectorizer to form vectors of these complex types?> > First-class support for complex can also improve the user experience. > Diagnostics could express concepts in the complex domain instead of > referring to expressions containing shuffles and other low-level data > manipulation. Users that wish to examine IR directly will see much less > gobbbledygook and can more easily reason about the IR. > > Types > > This proposal introduces new Single Value types to represent complex > numbers. > > c32 - like float complex or std::complex<float> > c64 - like double complex or std::complex<double> > > We defer a c128 type (like std::complex<long double>) for a future > RFC.Why? I'd prefer we avoid introducing even more special cases. Is there any reason why we should not define "complex <scalar type>", or to be more restrictive, "complex <floating-point type>"? I really don't like the idea of excluding 128-bit complex types, and I think that we can have a generic facility. -Hal> > Note that the references to C and C++ types above are simply > explanatory. Nothing in this proposal assumes any particular high-level > language type will map to the above LLVM types. > > The sizes of the types are 64 and 128 bits, respectively (this is > assumed by the ValueTypes given below) and the real part of the complex > will appear first in the layout of the types. The format of the real > and imaginary parts is the same as for float and double, respectively. > This should map to most common data representations of complex in > various languages. > > These types are *not* considered floating point types for the purposes > of Type::isFloatTy and friends, llvm_anyfloat_ty, etc. in order to limit > surprises when introducing these types. New APIs will allow querying > and creation of complex types: > > bool Type::isComplexTy() const; > bool Type::isComplex32Ty() const; > bool Type::isComplex64Ty() const; > > Analogous ValueTypes will be used by intrinsics. > > def c32 : ValueType<64, xxx> > def c64 : ValueType<128, yyy> > > def llvm_anycomplex_ty : LLVMType<Any>; > def llvm_c32_ty : LLVMType<c32>; > def llvm_c64_ty : LLVMType<c64>; > > The numbering of the ValueTypes will be determined after discussion. It > may be desirable to insert them before the existing vector types, > grouping them with the other scalar types or we may want to put them > somewhere else. > > Operations > > This proposal overloads existing floating point instructions for complex > types in order to leverage existing expression optimizations: > > c64 %res = fadd c64 %a, c64 %b > v8c64 %res = fsub v8c64 %a, v8c64 %b > c32 %res = fmul c64 %a, c64 %b > v4c32 %res = fdiv v4c64 %a, v4c64 %b > > The only valid comparisons of complex values will be equality: > > i1 %res = eq c32 %a, c32 %b > i8 %res = eq v8c32 %a, v8c32 %b > i1 %res = ne c64 %a, c64 %b > i8 %res = ne v8c64 %a, v8c64 %b > > select is defined for complex: > > c32 = select i1 %cmp, c32 %a, c32 %b > > v4c64 = select i4 %cmp, v4c64 %a, v4c64 %b > > Complex values may be casted to other complex types: > > c32 %res = fptrunc c64 %a to c32 > c64 %res = fpext c32 %a to c64 > > We may also overload existing intrinsics. > > declare c32 @llvm.sqrt.c32(c32 %Val) > declare c64 @llvm.sqrt.c64(c64 %Val) > > declare c32 @llvm.pow.c32(c32 %Val, c32 %Power) > declare c64 @llvm.pow.c64(c64 %Val, c64 %Power) > > declare c32 @llvm.sin.c32(c32 %Val) > declare c64 @llvm.sin.c64(c64 %Val) > > declare c32 @llvm.cos.c32(c32 %Val) > declare c64 @llvm.cos.c64(c64 %Val) > > declare c32 @llvm.log.c32(c32 %Val) > declare c64 @llvm.log.c64(c64 %Val) > > declare float @llvm.fabs.c32(c32 %Val) > declare double @llvm.fabs.c64(c64 %Val) > > In addition, new intrinsics will be used for complex-specific > operations: > > llvm.creal.* - Overloaded intrinsic to extract the real part of a > complex value > declare float @llvm.creal.c32(c32 %Val) > declare double @llvm.creal.c64(c64 %Val) > > llvm.cimag.* - Overloaded intrinsic to extract the imaginary part of a > complex value > declare float @llvm.cimag.c32(c32 %Val) > declare double @llvm.cimag.c64(c64 %Val) > > llvm.cconj.* - Overloaded intrinsic to compute the conjugate of a > complex value > declare c32 @llvm.cconj.c32(c32 %Val) > declare c64 @llvm.cconj.c64(c64 %Val) > > Summary > > This proposal introduced new complex types: c32 and c64. The proposal > overloads existing floating point instructions and intrinsics for common > complex operations and introduces new intrinsics for complex-specific > operations. > > Goals of this work include better reasoning about complex operations > within LLVM, leading to better optimization, reporting and overall user > experience. > > This is an early draft and subject to change. > > [1] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131516.html > [2] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131523.html > [3] http://lists.llvm.org/pipermail/llvm-dev/2010-December/037072.html > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory
> Why? I'd prefer we avoid introducing even more special cases. Is there > any reason why we should not define "complex <scalar type>", or to be > more restrictive, "complex <floating-point type>"? I really don't like > the idea of excluding 128-bit complex types, and I think that we can > have a generic facility.Hal, we had 128-bit complex in an earlier draft of David's proposal, but thought it to be an unnecessary distraction from our main interest, which is complex composed of 32-bit and 64-bit FP. I'll take responsibility for having prodded him to remove it. :) We're most interested in seeing complex supported in LLVM to help with compiling complex types in C and C++, where there is general understanding of complex when it's commonly composed of a pair of floats or doubles. Once you get beyond 32-bit and 64-bit FP as the constituent type though, you're in "complex long double" territory, and that introduces confusion. Many expect complex long double to have 128-bit parts, but long double can mean 80-bit FP. Although we personally haven't seen much practical use of a complex type composed of 80-bit FP, we thought that proposing complex for 128-bit FP might require also covering the 80-bit FP case. What long double means is, after all, a Clang issue and not an LLVM issue, but we figured that proposing more types would have a harder path to success than proposing fewer types. Do you think it's best to have the full set (c32, c64, c80, c128) or just (c32, c64, c128)? -Troy
On Mon, 1 Jul 2019 at 19:56, David Greene via llvm-dev <llvm-dev at lists.llvm.org> wrote:> llvm.creal.* - Overloaded intrinsic to extract the real part of a > complex value > declare float @llvm.creal.c32(c32 %Val) > declare double @llvm.creal.c64(c64 %Val)What are your plans for the reverse? I assume we don't want the only way to materialize a complex to be via memory so an insertvalue equivalent (or maybe using insertvalue/extractvalue directly?) and a literal value would probably be useful. Cheers. Tim.
That's the intent. I'm only really familiar with the X86 and AArch64 ABIs so feedback on whether this is sufficient for other targets is welcome! -David JF Bastien <jfbastien at apple.com> writes:> Hi David, > > IIUC your proposal preserves the current ABI? > > Thanks, > > JF > >> On Jul 1, 2019, at 11:56 AM, David Greene via llvm-dev <llvm-dev at lists.llvm.org> wrote: >> >> Hey all, >> >> I volunteered to put together a proposal regard complex in LLVM. >> Consider the following to be a strawman meant to spark discussion. It's >> based on real-world experience with complex but is not expected to cover >> all use-cases. >> >> Proposal to Support Complex Operations in LLVM >> ---------------------------------------------- >> >> Abstract >> >> Several vendors and individuals have proposed first-class complex >> support in LLVM. Goals of this proposal include better optimization, >> diagnostics and general user experience. >> >> Introduction and Motivation >> >> Recently the topic of complex numbers arose on llvm-dev with several >> developers expressing a desire for first-class IR support for complex >> [1] [2]. Interest in complex numbers in LLVM goes back much further >> [3]. >> >> Currently clang chooses to represent standard types like "double >> complex" and "std::complex<float>" as structure types containing two >> scalar fields, for example {double, double}. Consequently, arrays of >> complex type are represented as, for example, [8 x {double, double}]. >> This has consequences for how clang converts complex operations to LLVM >> IR. In general, clang emits loads of the individual real and imaginary >> parts and feeds them into arithmetic operations. Vectorization results >> in many shufflevector operations to massage the data into sequences >> suitable for vector arithmetic. >> >> All of the real/imaginary data manipulation obscures the underlying >> arithmetic. It makes it difficult to reason about the algebraic >> properties of expressions. For expressiveness and optimization ability, >> it will be nice to have a higher-level representation for complex in >> LLVM IR. In general, it is desirable to defer lowering of complex until >> the optimizer has had a reasonable chance to exploit its properties. >> >> First-class support for complex can also improve the user experience. >> Diagnostics could express concepts in the complex domain instead of >> referring to expressions containing shuffles and other low-level data >> manipulation. Users that wish to examine IR directly will see much less >> gobbbledygook and can more easily reason about the IR. >> >> Types >> >> This proposal introduces new Single Value types to represent complex >> numbers. >> >> c32 - like float complex or std::complex<float> >> c64 - like double complex or std::complex<double> >> >> We defer a c128 type (like std::complex<long double>) for a future >> RFC. >> >> Note that the references to C and C++ types above are simply >> explanatory. Nothing in this proposal assumes any particular high-level >> language type will map to the above LLVM types. >> >> The sizes of the types are 64 and 128 bits, respectively (this is >> assumed by the ValueTypes given below) and the real part of the complex >> will appear first in the layout of the types. The format of the real >> and imaginary parts is the same as for float and double, respectively. >> This should map to most common data representations of complex in >> various languages. >> >> These types are *not* considered floating point types for the purposes >> of Type::isFloatTy and friends, llvm_anyfloat_ty, etc. in order to limit >> surprises when introducing these types. New APIs will allow querying >> and creation of complex types: >> >> bool Type::isComplexTy() const; >> bool Type::isComplex32Ty() const; >> bool Type::isComplex64Ty() const; >> >> Analogous ValueTypes will be used by intrinsics. >> >> def c32 : ValueType<64, xxx> >> def c64 : ValueType<128, yyy> >> >> def llvm_anycomplex_ty : LLVMType<Any>; >> def llvm_c32_ty : LLVMType<c32>; >> def llvm_c64_ty : LLVMType<c64>; >> >> The numbering of the ValueTypes will be determined after discussion. It >> may be desirable to insert them before the existing vector types, >> grouping them with the other scalar types or we may want to put them >> somewhere else. >> >> Operations >> >> This proposal overloads existing floating point instructions for complex >> types in order to leverage existing expression optimizations: >> >> c64 %res = fadd c64 %a, c64 %b >> v8c64 %res = fsub v8c64 %a, v8c64 %b >> c32 %res = fmul c64 %a, c64 %b >> v4c32 %res = fdiv v4c64 %a, v4c64 %b >> >> The only valid comparisons of complex values will be equality: >> >> i1 %res = eq c32 %a, c32 %b >> i8 %res = eq v8c32 %a, v8c32 %b >> i1 %res = ne c64 %a, c64 %b >> i8 %res = ne v8c64 %a, v8c64 %b >> >> select is defined for complex: >> >> c32 = select i1 %cmp, c32 %a, c32 %b >> >> v4c64 = select i4 %cmp, v4c64 %a, v4c64 %b >> >> Complex values may be casted to other complex types: >> >> c32 %res = fptrunc c64 %a to c32 >> c64 %res = fpext c32 %a to c64 >> >> We may also overload existing intrinsics. >> >> declare c32 @llvm.sqrt.c32(c32 %Val) >> declare c64 @llvm.sqrt.c64(c64 %Val) >> >> declare c32 @llvm.pow.c32(c32 %Val, c32 %Power) >> declare c64 @llvm.pow.c64(c64 %Val, c64 %Power) >> >> declare c32 @llvm.sin.c32(c32 %Val) >> declare c64 @llvm.sin.c64(c64 %Val) >> >> declare c32 @llvm.cos.c32(c32 %Val) >> declare c64 @llvm.cos.c64(c64 %Val) >> >> declare c32 @llvm.log.c32(c32 %Val) >> declare c64 @llvm.log.c64(c64 %Val) >> >> declare float @llvm.fabs.c32(c32 %Val) >> declare double @llvm.fabs.c64(c64 %Val) >> >> In addition, new intrinsics will be used for complex-specific >> operations: >> >> llvm.creal.* - Overloaded intrinsic to extract the real part of a >> complex value >> declare float @llvm.creal.c32(c32 %Val) >> declare double @llvm.creal.c64(c64 %Val) >> >> llvm.cimag.* - Overloaded intrinsic to extract the imaginary part of a >> complex value >> declare float @llvm.cimag.c32(c32 %Val) >> declare double @llvm.cimag.c64(c64 %Val) >> >> llvm.cconj.* - Overloaded intrinsic to compute the conjugate of a >> complex value >> declare c32 @llvm.cconj.c32(c32 %Val) >> declare c64 @llvm.cconj.c64(c64 %Val) >> >> Summary >> >> This proposal introduced new complex types: c32 and c64. The proposal >> overloads existing floating point instructions and intrinsics for common >> complex operations and introduces new intrinsics for complex-specific >> operations. >> >> Goals of this work include better reasoning about complex operations >> within LLVM, leading to better optimization, reporting and overall user >> experience. >> >> This is an early draft and subject to change. >> >> [1] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131516.html> [2] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131523.html> [3] http://lists.llvm.org/pipermail/llvm-dev/2010-December/037072.html> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
I think they should probably implement the C standard semantics and various pragmas or compiler flags could allow different algorithms. The intent would be to preserve the current behavior of clang. That should be fine for Fortran as well. I don't know about other languages like go that have LLVM frontends. As for FMAs, I think that could also be tied to pragmas and compiler flags. -David Stephen Canon <scanon at apple.com> writes:> Hi David — > > What do you intend the semantics of the fmul and fdiv operations to be > for these types? Do them implement the C semantics (avoid spurious > overflow/underflow)? The naive arithmetic (some fortran > implementations)? Is FMA licensed in their evaluation? > > – Steve > >> On Jul 1, 2019, at 2:56 PM, David Greene via llvm-dev <llvm-dev at lists.llvm.org> wrote: >> >> Hey all, >> >> I volunteered to put together a proposal regard complex in LLVM. >> Consider the following to be a strawman meant to spark discussion. It's >> based on real-world experience with complex but is not expected to cover >> all use-cases. >> >> Proposal to Support Complex Operations in LLVM >> ---------------------------------------------- >> >> Abstract >> >> Several vendors and individuals have proposed first-class complex >> support in LLVM. Goals of this proposal include better optimization, >> diagnostics and general user experience. >> >> Introduction and Motivation >> >> Recently the topic of complex numbers arose on llvm-dev with several >> developers expressing a desire for first-class IR support for complex >> [1] [2]. Interest in complex numbers in LLVM goes back much further >> [3]. >> >> Currently clang chooses to represent standard types like "double >> complex" and "std::complex<float>" as structure types containing two >> scalar fields, for example {double, double}. Consequently, arrays of >> complex type are represented as, for example, [8 x {double, double}]. >> This has consequences for how clang converts complex operations to LLVM >> IR. In general, clang emits loads of the individual real and imaginary >> parts and feeds them into arithmetic operations. Vectorization results >> in many shufflevector operations to massage the data into sequences >> suitable for vector arithmetic. >> >> All of the real/imaginary data manipulation obscures the underlying >> arithmetic. It makes it difficult to reason about the algebraic >> properties of expressions. For expressiveness and optimization ability, >> it will be nice to have a higher-level representation for complex in >> LLVM IR. In general, it is desirable to defer lowering of complex until >> the optimizer has had a reasonable chance to exploit its properties. >> >> First-class support for complex can also improve the user experience. >> Diagnostics could express concepts in the complex domain instead of >> referring to expressions containing shuffles and other low-level data >> manipulation. Users that wish to examine IR directly will see much less >> gobbbledygook and can more easily reason about the IR. >> >> Types >> >> This proposal introduces new Single Value types to represent complex >> numbers. >> >> c32 - like float complex or std::complex<float> >> c64 - like double complex or std::complex<double> >> >> We defer a c128 type (like std::complex<long double>) for a future >> RFC. >> >> Note that the references to C and C++ types above are simply >> explanatory. Nothing in this proposal assumes any particular high-level >> language type will map to the above LLVM types. >> >> The sizes of the types are 64 and 128 bits, respectively (this is >> assumed by the ValueTypes given below) and the real part of the complex >> will appear first in the layout of the types. The format of the real >> and imaginary parts is the same as for float and double, respectively. >> This should map to most common data representations of complex in >> various languages. >> >> These types are *not* considered floating point types for the purposes >> of Type::isFloatTy and friends, llvm_anyfloat_ty, etc. in order to limit >> surprises when introducing these types. New APIs will allow querying >> and creation of complex types: >> >> bool Type::isComplexTy() const; >> bool Type::isComplex32Ty() const; >> bool Type::isComplex64Ty() const; >> >> Analogous ValueTypes will be used by intrinsics. >> >> def c32 : ValueType<64, xxx> >> def c64 : ValueType<128, yyy> >> >> def llvm_anycomplex_ty : LLVMType<Any>; >> def llvm_c32_ty : LLVMType<c32>; >> def llvm_c64_ty : LLVMType<c64>; >> >> The numbering of the ValueTypes will be determined after discussion. It >> may be desirable to insert them before the existing vector types, >> grouping them with the other scalar types or we may want to put them >> somewhere else. >> >> Operations >> >> This proposal overloads existing floating point instructions for complex >> types in order to leverage existing expression optimizations: >> >> c64 %res = fadd c64 %a, c64 %b >> v8c64 %res = fsub v8c64 %a, v8c64 %b >> c32 %res = fmul c64 %a, c64 %b >> v4c32 %res = fdiv v4c64 %a, v4c64 %b >> >> The only valid comparisons of complex values will be equality: >> >> i1 %res = eq c32 %a, c32 %b >> i8 %res = eq v8c32 %a, v8c32 %b >> i1 %res = ne c64 %a, c64 %b >> i8 %res = ne v8c64 %a, v8c64 %b >> >> select is defined for complex: >> >> c32 = select i1 %cmp, c32 %a, c32 %b >> >> v4c64 = select i4 %cmp, v4c64 %a, v4c64 %b >> >> Complex values may be casted to other complex types: >> >> c32 %res = fptrunc c64 %a to c32 >> c64 %res = fpext c32 %a to c64 >> >> We may also overload existing intrinsics. >> >> declare c32 @llvm.sqrt.c32(c32 %Val) >> declare c64 @llvm.sqrt.c64(c64 %Val) >> >> declare c32 @llvm.pow.c32(c32 %Val, c32 %Power) >> declare c64 @llvm.pow.c64(c64 %Val, c64 %Power) >> >> declare c32 @llvm.sin.c32(c32 %Val) >> declare c64 @llvm.sin.c64(c64 %Val) >> >> declare c32 @llvm.cos.c32(c32 %Val) >> declare c64 @llvm.cos.c64(c64 %Val) >> >> declare c32 @llvm.log.c32(c32 %Val) >> declare c64 @llvm.log.c64(c64 %Val) >> >> declare float @llvm.fabs.c32(c32 %Val) >> declare double @llvm.fabs.c64(c64 %Val) >> >> In addition, new intrinsics will be used for complex-specific >> operations: >> >> llvm.creal.* - Overloaded intrinsic to extract the real part of a >> complex value >> declare float @llvm.creal.c32(c32 %Val) >> declare double @llvm.creal.c64(c64 %Val) >> >> llvm.cimag.* - Overloaded intrinsic to extract the imaginary part of a >> complex value >> declare float @llvm.cimag.c32(c32 %Val) >> declare double @llvm.cimag.c64(c64 %Val) >> >> llvm.cconj.* - Overloaded intrinsic to compute the conjugate of a >> complex value >> declare c32 @llvm.cconj.c32(c32 %Val) >> declare c64 @llvm.cconj.c64(c64 %Val) >> >> Summary >> >> This proposal introduced new complex types: c32 and c64. The proposal >> overloads existing floating point instructions and intrinsics for common >> complex operations and introduces new intrinsics for complex-specific >> operations. >> >> Goals of this work include better reasoning about complex operations >> within LLVM, leading to better optimization, reporting and overall user >> experience. >> >> This is an early draft and subject to change. >> >> [1] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131516.html> [2] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131523.html> [3] http://lists.llvm.org/pipermail/llvm-dev/2010-December/037072.html> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
"Finkel, Hal J." <hfinkel at anl.gov> writes:> I think that it's really important that we're specific about the goals > here. Exactly what kinds of optimizations are we aiming to (more-easily) > enable? There certainly exists hardware with instructions that help > vectorize complex multiplication, for example, and having a builtin > complex type would make writing patterns for those instructions easier > (as opposed to trying to build matching into the SLP vectorizer or > elsewhere). This probably makes constant-folding calls to complex libm > functions easier.Yes, all of that. Plus things like instcombine, expression rewrites/simplification and so on.> Does this make loop vectorization easier or harder? Do you expect the > vectorizer to form vectors of these complex types?I expect the vectorizer to form vectors of complex types, yes. I suspect having a first-class complex type will make vectorization easier.>> We defer a c128 type (like std::complex<long double>) for a future >> RFC. > > > Why? I'd prefer we avoid introducing even more special cases. Is there > any reason why we should not define "complex <scalar type>", or to be > more restrictive, "complex <floating-point type>"? I really don't like > the idea of excluding 128-bit complex types, and I think that we can > have a generic facility.Troy already addressed this but I'm very happy to re-add c128. I think complex <floating-point-type> would be fine. Of course some floating-point-types only make sense on certain targets. How would we legalize a c24 on a target that doesn't support it natively? Calls into compiler-rt? We had quite a bit of discussion around naming here. If we're expanding this to allow general floating point types, is c<bit-width> still a good name? -David
Tim Northover <t.p.northover at gmail.com> writes:> On Mon, 1 Jul 2019 at 19:56, David Greene via llvm-dev > <llvm-dev at lists.llvm.org> wrote: >> llvm.creal.* - Overloaded intrinsic to extract the real part of a >> complex value >> declare float @llvm.creal.c32(c32 %Val) >> declare double @llvm.creal.c64(c64 %Val) > > What are your plans for the reverse? I assume we don't want the only > way to materialize a complex to be via memory so an insertvalue > equivalent (or maybe using insertvalue/extractvalue directly?) and a > literal value would probably be useful.Good points. Originally I put the creal/cimag intrinsics in the proposal when the layout of the complex type was left unspecified. After internal feedback, I changed it to an explicitly-specified layout (real followed by imaginary). Maybe creal/cimag should go away. Then we wouldn't have to teach the optimizer about them and it already understands insertvalue/extractvalue. Of course it might have to be taught about insertvalue/extractvalue on a complex type anyway. So I dunno, is there a strong preference one way or the other? -David
-----Original Message----- From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of David Greene via llvm-dev Sent: Monday, July 1, 2019 1:56 PM To: llvm-dev at lists.llvm.org Subject: [EXT] [llvm-dev] RFC: Complex in LLVM> [...] > > Vectorization results in many shufflevector operations to massage the data into sequences suitable for vector arithmetic. > > [...]This is the important part, and there is nothing in this RFC that helps alleviate it. Vectorization must know the data layout: whether we have vectors (r1, i1, r2, i2...) or (r1, r2, ...), (i1, i2, ...). These two approaches are not compatible. If you have vector registers that can hold 8 floats, with the first approach you can load 4 complex numbers in a single instruction, then multiply by another 4 numbers, and store. With the second approach, the minimum unit of work is 8 numbers, and each input to the multiplication has to be loaded in two instructions, loading real and imaginary parts from two separate locations. On most architectures the second approach would be vastly superior, but the v4c32 type mentioned in the RFC suggests the first one. In addition to that, we shouldn't limit complex types to floating point only. What we care about is keeping the "ac-bd" together, not what type a,b,c,d are. -Krzysztof
On 2019-07-01 20:56, David Greene via llvm-dev wrote:> [...] > > All of the real/imaginary data manipulation obscures the underlying > arithmetic. It makes it difficult to reason about the algebraic > properties of expressions. For expressiveness and optimization > ability, > it will be nice to have a higher-level representation for complex in > LLVM IR. In general, it is desirable to defer lowering of complex > until > the optimizer has had a reasonable chance to exploit its properties.Do you have a concrete example where having a high-level complex type would make the optimizer's job easier?> [...]-Manuel
Krzysztof Parzyszek via llvm-dev <llvm-dev at lists.llvm.org> writes:> Vectorization must know the data layout: whether we have vectors (r1, > i1, r2, i2...) or (r1, r2, ...), (i1, i2, ...). These two approaches > are not compatible. If you have vector registers that can hold 8 > floats, with the first approach you can load 4 complex numbers in a > single instruction, then multiply by another 4 numbers, and store. > With the second approach, the minimum unit of work is 8 numbers, and > each input to the multiplication has to be loaded in two instructions, > loading real and imaginary parts from two separate locations. On most > architectures the second approach would be vastly superior, but the > v4c32 type mentioned in the RFC suggests the first one.That's true. I was assuming that if the vectorizer wants to extract reals from a vector of complex, we'd need an operation to do that that results in a different vector type (say, two v4c32 -> one v8f32). It's a special kind of shufflevector. The reverse operation is also useful.> In addition to that, we shouldn't limit complex types to floating > point only. What we care about is keeping the "ac-bd" together, not > what type a,b,c,d are.Can you give some examples of non-FP types where a higher-level representation would be useful? -David
When would the complex operations be lowered to floating-point operations? I assume it would be the backends for targets that support complex instructions (GlobalISel?), but in other cases there might be potential for more IR-level optimizations after lowering. Michael Am Mo., 1. Juli 2019 um 13:56 Uhr schrieb David Greene via llvm-dev <llvm-dev at lists.llvm.org>:> > Hey all, > > I volunteered to put together a proposal regard complex in LLVM. > Consider the following to be a strawman meant to spark discussion. It's > based on real-world experience with complex but is not expected to cover > all use-cases. > > Proposal to Support Complex Operations in LLVM > ---------------------------------------------- > > Abstract > > Several vendors and individuals have proposed first-class complex > support in LLVM. Goals of this proposal include better optimization, > diagnostics and general user experience. > > Introduction and Motivation > > Recently the topic of complex numbers arose on llvm-dev with several > developers expressing a desire for first-class IR support for complex > [1] [2]. Interest in complex numbers in LLVM goes back much further > [3]. > > Currently clang chooses to represent standard types like "double > complex" and "std::complex<float>" as structure types containing two > scalar fields, for example {double, double}. Consequently, arrays of > complex type are represented as, for example, [8 x {double, double}]. > This has consequences for how clang converts complex operations to LLVM > IR. In general, clang emits loads of the individual real and imaginary > parts and feeds them into arithmetic operations. Vectorization results > in many shufflevector operations to massage the data into sequences > suitable for vector arithmetic. > > All of the real/imaginary data manipulation obscures the underlying > arithmetic. It makes it difficult to reason about the algebraic > properties of expressions. For expressiveness and optimization ability, > it will be nice to have a higher-level representation for complex in > LLVM IR. In general, it is desirable to defer lowering of complex until > the optimizer has had a reasonable chance to exploit its properties. > > First-class support for complex can also improve the user experience. > Diagnostics could express concepts in the complex domain instead of > referring to expressions containing shuffles and other low-level data > manipulation. Users that wish to examine IR directly will see much less > gobbbledygook and can more easily reason about the IR. > > Types > > This proposal introduces new Single Value types to represent complex > numbers. > > c32 - like float complex or std::complex<float> > c64 - like double complex or std::complex<double> > > We defer a c128 type (like std::complex<long double>) for a future > RFC. > > Note that the references to C and C++ types above are simply > explanatory. Nothing in this proposal assumes any particular high-level > language type will map to the above LLVM types. > > The sizes of the types are 64 and 128 bits, respectively (this is > assumed by the ValueTypes given below) and the real part of the complex > will appear first in the layout of the types. The format of the real > and imaginary parts is the same as for float and double, respectively. > This should map to most common data representations of complex in > various languages. > > These types are *not* considered floating point types for the purposes > of Type::isFloatTy and friends, llvm_anyfloat_ty, etc. in order to limit > surprises when introducing these types. New APIs will allow querying > and creation of complex types: > > bool Type::isComplexTy() const; > bool Type::isComplex32Ty() const; > bool Type::isComplex64Ty() const; > > Analogous ValueTypes will be used by intrinsics. > > def c32 : ValueType<64, xxx> > def c64 : ValueType<128, yyy> > > def llvm_anycomplex_ty : LLVMType<Any>; > def llvm_c32_ty : LLVMType<c32>; > def llvm_c64_ty : LLVMType<c64>; > > The numbering of the ValueTypes will be determined after discussion. It > may be desirable to insert them before the existing vector types, > grouping them with the other scalar types or we may want to put them > somewhere else. > > Operations > > This proposal overloads existing floating point instructions for complex > types in order to leverage existing expression optimizations: > > c64 %res = fadd c64 %a, c64 %b > v8c64 %res = fsub v8c64 %a, v8c64 %b > c32 %res = fmul c64 %a, c64 %b > v4c32 %res = fdiv v4c64 %a, v4c64 %b > > The only valid comparisons of complex values will be equality: > > i1 %res = eq c32 %a, c32 %b > i8 %res = eq v8c32 %a, v8c32 %b > i1 %res = ne c64 %a, c64 %b > i8 %res = ne v8c64 %a, v8c64 %b > > select is defined for complex: > > c32 = select i1 %cmp, c32 %a, c32 %b > > v4c64 = select i4 %cmp, v4c64 %a, v4c64 %b > > Complex values may be casted to other complex types: > > c32 %res = fptrunc c64 %a to c32 > c64 %res = fpext c32 %a to c64 > > We may also overload existing intrinsics. > > declare c32 @llvm.sqrt.c32(c32 %Val) > declare c64 @llvm.sqrt.c64(c64 %Val) > > declare c32 @llvm.pow.c32(c32 %Val, c32 %Power) > declare c64 @llvm.pow.c64(c64 %Val, c64 %Power) > > declare c32 @llvm.sin.c32(c32 %Val) > declare c64 @llvm.sin.c64(c64 %Val) > > declare c32 @llvm.cos.c32(c32 %Val) > declare c64 @llvm.cos.c64(c64 %Val) > > declare c32 @llvm.log.c32(c32 %Val) > declare c64 @llvm.log.c64(c64 %Val) > > declare float @llvm.fabs.c32(c32 %Val) > declare double @llvm.fabs.c64(c64 %Val) > > In addition, new intrinsics will be used for complex-specific > operations: > > llvm.creal.* - Overloaded intrinsic to extract the real part of a > complex value > declare float @llvm.creal.c32(c32 %Val) > declare double @llvm.creal.c64(c64 %Val) > > llvm.cimag.* - Overloaded intrinsic to extract the imaginary part of a > complex value > declare float @llvm.cimag.c32(c32 %Val) > declare double @llvm.cimag.c64(c64 %Val) > > llvm.cconj.* - Overloaded intrinsic to compute the conjugate of a > complex value > declare c32 @llvm.cconj.c32(c32 %Val) > declare c64 @llvm.cconj.c64(c64 %Val) > > Summary > > This proposal introduced new complex types: c32 and c64. The proposal > overloads existing floating point instructions and intrinsics for common > complex operations and introduces new intrinsics for complex-specific > operations. > > Goals of this work include better reasoning about complex operations > within LLVM, leading to better optimization, reporting and overall user > experience. > > This is an early draft and subject to change. > > [1] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131516.html > [2] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131523.html > [3] http://lists.llvm.org/pipermail/llvm-dev/2010-December/037072.html > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
It's not completely clear to me how this should work. I certainly agree that lowering complex to floating point IR can benefit targets that don't have direct support for complex operations. One idea would be to have a lowering pass that lowers to generic IR for most targets and to target-specific intrinsics for targets that have hardware support. TTI could convey whether such operations are available. It'd be great to get the wisdom of the community on how best to handle this. -David Michael Kruse via llvm-dev <llvm-dev at lists.llvm.org> writes:> When would the complex operations be lowered to floating-point > operations? I assume it would be the backends for targets that support > complex instructions (GlobalISel?), but in other cases there might be > potential for more IR-level optimizations after lowering. > > Michael > > Am Mo., 1. Juli 2019 um 13:56 Uhr schrieb David Greene via llvm-dev > <llvm-dev at lists.llvm.org>: >> >> Hey all, >> >> I volunteered to put together a proposal regard complex in LLVM. >> Consider the following to be a strawman meant to spark discussion. It's >> based on real-world experience with complex but is not expected to cover >> all use-cases. >> >> Proposal to Support Complex Operations in LLVM >> ---------------------------------------------- >> >> Abstract >> >> Several vendors and individuals have proposed first-class complex >> support in LLVM. Goals of this proposal include better optimization, >> diagnostics and general user experience. >> >> Introduction and Motivation >> >> Recently the topic of complex numbers arose on llvm-dev with several >> developers expressing a desire for first-class IR support for complex >> [1] [2]. Interest in complex numbers in LLVM goes back much further >> [3]. >> >> Currently clang chooses to represent standard types like "double >> complex" and "std::complex<float>" as structure types containing two >> scalar fields, for example {double, double}. Consequently, arrays of >> complex type are represented as, for example, [8 x {double, double}]. >> This has consequences for how clang converts complex operations to LLVM >> IR. In general, clang emits loads of the individual real and imaginary >> parts and feeds them into arithmetic operations. Vectorization results >> in many shufflevector operations to massage the data into sequences >> suitable for vector arithmetic. >> >> All of the real/imaginary data manipulation obscures the underlying >> arithmetic. It makes it difficult to reason about the algebraic >> properties of expressions. For expressiveness and optimization ability, >> it will be nice to have a higher-level representation for complex in >> LLVM IR. In general, it is desirable to defer lowering of complex until >> the optimizer has had a reasonable chance to exploit its properties. >> >> First-class support for complex can also improve the user experience. >> Diagnostics could express concepts in the complex domain instead of >> referring to expressions containing shuffles and other low-level data >> manipulation. Users that wish to examine IR directly will see much less >> gobbbledygook and can more easily reason about the IR. >> >> Types >> >> This proposal introduces new Single Value types to represent complex >> numbers. >> >> c32 - like float complex or std::complex<float> >> c64 - like double complex or std::complex<double> >> >> We defer a c128 type (like std::complex<long double>) for a future >> RFC. >> >> Note that the references to C and C++ types above are simply >> explanatory. Nothing in this proposal assumes any particular high-level >> language type will map to the above LLVM types. >> >> The sizes of the types are 64 and 128 bits, respectively (this is >> assumed by the ValueTypes given below) and the real part of the complex >> will appear first in the layout of the types. The format of the real >> and imaginary parts is the same as for float and double, respectively. >> This should map to most common data representations of complex in >> various languages. >> >> These types are *not* considered floating point types for the purposes >> of Type::isFloatTy and friends, llvm_anyfloat_ty, etc. in order to limit >> surprises when introducing these types. New APIs will allow querying >> and creation of complex types: >> >> bool Type::isComplexTy() const; >> bool Type::isComplex32Ty() const; >> bool Type::isComplex64Ty() const; >> >> Analogous ValueTypes will be used by intrinsics. >> >> def c32 : ValueType<64, xxx> >> def c64 : ValueType<128, yyy> >> >> def llvm_anycomplex_ty : LLVMType<Any>; >> def llvm_c32_ty : LLVMType<c32>; >> def llvm_c64_ty : LLVMType<c64>; >> >> The numbering of the ValueTypes will be determined after discussion. It >> may be desirable to insert them before the existing vector types, >> grouping them with the other scalar types or we may want to put them >> somewhere else. >> >> Operations >> >> This proposal overloads existing floating point instructions for complex >> types in order to leverage existing expression optimizations: >> >> c64 %res = fadd c64 %a, c64 %b >> v8c64 %res = fsub v8c64 %a, v8c64 %b >> c32 %res = fmul c64 %a, c64 %b >> v4c32 %res = fdiv v4c64 %a, v4c64 %b >> >> The only valid comparisons of complex values will be equality: >> >> i1 %res = eq c32 %a, c32 %b >> i8 %res = eq v8c32 %a, v8c32 %b >> i1 %res = ne c64 %a, c64 %b >> i8 %res = ne v8c64 %a, v8c64 %b >> >> select is defined for complex: >> >> c32 = select i1 %cmp, c32 %a, c32 %b >> >> v4c64 = select i4 %cmp, v4c64 %a, v4c64 %b >> >> Complex values may be casted to other complex types: >> >> c32 %res = fptrunc c64 %a to c32 >> c64 %res = fpext c32 %a to c64 >> >> We may also overload existing intrinsics. >> >> declare c32 @llvm.sqrt.c32(c32 %Val) >> declare c64 @llvm.sqrt.c64(c64 %Val) >> >> declare c32 @llvm.pow.c32(c32 %Val, c32 %Power) >> declare c64 @llvm.pow.c64(c64 %Val, c64 %Power) >> >> declare c32 @llvm.sin.c32(c32 %Val) >> declare c64 @llvm.sin.c64(c64 %Val) >> >> declare c32 @llvm.cos.c32(c32 %Val) >> declare c64 @llvm.cos.c64(c64 %Val) >> >> declare c32 @llvm.log.c32(c32 %Val) >> declare c64 @llvm.log.c64(c64 %Val) >> >> declare float @llvm.fabs.c32(c32 %Val) >> declare double @llvm.fabs.c64(c64 %Val) >> >> In addition, new intrinsics will be used for complex-specific >> operations: >> >> llvm.creal.* - Overloaded intrinsic to extract the real part of a >> complex value >> declare float @llvm.creal.c32(c32 %Val) >> declare double @llvm.creal.c64(c64 %Val) >> >> llvm.cimag.* - Overloaded intrinsic to extract the imaginary part of a >> complex value >> declare float @llvm.cimag.c32(c32 %Val) >> declare double @llvm.cimag.c64(c64 %Val) >> >> llvm.cconj.* - Overloaded intrinsic to compute the conjugate of a >> complex value >> declare c32 @llvm.cconj.c32(c32 %Val) >> declare c64 @llvm.cconj.c64(c64 %Val) >> >> Summary >> >> This proposal introduced new complex types: c32 and c64. The proposal >> overloads existing floating point instructions and intrinsics for common >> complex operations and introduces new intrinsics for complex-specific >> operations. >> >> Goals of this work include better reasoning about complex operations >> within LLVM, leading to better optimization, reporting and overall user >> experience. >> >> This is an early draft and subject to change. >> >> [1] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131516.html> [2] http://lists.llvm.org/pipermail/llvm-dev/2019-April/131523.html> [3] http://lists.llvm.org/pipermail/llvm-dev/2010-December/037072.html> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev_______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev