[llvm-dev] RFC: Complex in LLVM

Tue Jul 9 11:57:27 PDT 2019

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