[llvm-dev] RFC: Complex in LLVM

Finkel, Hal J. via llvm-dev llvm-dev at lists.llvm.org
Tue Jul 2 10:16:29 PDT 2019


On 7/2/19 10:39 AM, David Greene via llvm-dev wrote:
> 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.


IIRC, a Fortran compiler must use a numerically-stable division 
algorithm or else the LAPACK regression tests won't pass. I think that 
we'll want a non-naive division lowering (e.g., Smith's algorithm, 
something along the lines of the one in 
https://github.com/llvm-flang/flang-old/blob/master/lib/CodeGen/CGExprComplex.cpp).


>
> As for FMAs, I think that could also be tied to pragmas and compiler
> flags.


I agree. This should be tied to the existing fast-math flags (contract 
for FMAs, for example).

  -Hal

>
>                       -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
> _______________________________________________
> 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