[llvm-dev] RFC: Complex in LLVM
Finkel, Hal J. via llvm-dev
llvm-dev at lists.llvm.org
Mon Jul 1 17:27:58 PDT 2019
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
More information about the llvm-dev
mailing list