[llvm-dev] RFC: Complex in LLVM

[David Greene via llvm-dev]

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