<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal">This is another proposal about introducing complex types into LLVM. Following on from
<a href="https://lists.llvm.org/pipermail/llvm-dev/2019-October/136100.html">https://lists.llvm.org/pipermail/llvm-dev/2019-October/136100.html</a>, this is different in that it doesn’t propose complex types directly but instead proposes representing complex
numbers as vectors and using intrinsics. See also Florian’s proposal to do this (starting with complex multiply) here:
<a href="https://lists.llvm.org/pipermail/llvm-dev/2020-November/146568.html">https://lists.llvm.org/pipermail/llvm-dev/2020-November/146568.html</a>.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Representation of complex types<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The proposal is to represent complex numbers as vectors of 2N floating-point types. For example, <2 x float> would represent a scalar complex number. <4 x float> would represent a vector of 2 complex floating-point numbers, with the first
complex number living in lanes 0 and 1, and the second living in lanes 2 and 3. This representation of complex types matches the vector form in x86.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The basic arithmetic operations are mapped as follows:<o:p></o:p></p>
<p class="MsoNormal">+ or -: fadd or fsub <2 x float> %a, %b<o:p></o:p></p>
<p class="MsoNormal">*: call <2 x float> @llvm.complex.multiply(<2 x float> %a, <2 x float> %b)<o:p></o:p></p>
<p class="MsoNormal">/: call <2 x float> @llvm.complex.divide(<2 x float> %a, <2 x float> %b)<o:p></o:p></p>
<p class="MsoNormal">Building complex values, creal, cimag: existing extractvalue, insertvalue, and shufflevector instructions as appropriate<br>
cabs: call float @llvm.complex.abs(<2 x float> %val)<br>
cconj: call <2 x float> @llvm.complex.conj(<2 x float> %val)<br>
<br>
<o:p></o:p></p>
<p class="MsoNormal">One complexity that hasn’t been covered in prior proposals is what complex multiplication actually means. Among our major source languages (C/C++/Fortran), there is some variance as to the definition of multiplication, division, and complex
absolute values. This variation is most acute when looking at division. The naïve expansion of computing (a + bi)/(c + di) is<o:p></o:p></p>
<p class="MsoNormal">denom = c * c + d * d<br>
real = (a * c + b * d) / denom<br>
imag = (b * c - a * d) / denom<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">If you use Fortran, there is a requirement that the division operation be scaled to prevent overflow in computing denom (at the very least, this is how I’ve seen existing Fortran compilers implement it). If you use C, there is an additional
requirement that the resulting complex number be recomputed to infinity for certain cases where real and imaginary are both NaN (see Annex G of the C standard). Using the CX_LIMITED_RANGE pragma, or equivalent command-line option, lifts both of these requirements.
Additionally, gcc provides a -fcx-fortran-rules that lifts only the latter requirement. My understanding is that all hardware implementations of complex multiply implement CX_LIMITED_RANGE rules.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">My proposal is to distinguish between these situations using a mixture of existing fast-math flags and call-site attributes. Without any flags or call-site attributes, these intrinsics would expand to their compiler-rt equivalents of __mulsc3,
__divsc3, etc., which is to say they would have full C requirements (both NaN checking and scaling). The “complex-limited-range” call-site attribute would disable both of these requirements. The “complex-no-scale” call-site attribute would disable the specific
scaling requirement but retain the NaN checking behavior. Additionally, fast math flags can be used to generate behavior: nnan or ninf would trigger the dropping of the NaN checking code by itself.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Implementation experience<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I have been able to implement patches that pattern-match for complex multiply and divide (in the CX_LIMITED_RANGE cases) early in InstCombine, and haven’t seen issues with that. Doing codegen for the non-CX_LIMITED_RANGE case, requiring
a call to __mulsc3, is difficult because that function returns a C _Complex number, and the C ABIs for complex numbers tend to be inconsistent even among different floating-point types within the same architecture. The truly evil case is the i386 ABI for float,
which is returned as edx:eax (or i64, as generated by clang).<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">If you want to talk more about this, I have a roundtable tomorrow, Friday, at 14:45 Eastern or 11:45 Pacific.<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:9.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:9.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:9.0pt">-- <o:p></o:p></span></p>
<p class="MsoNormal"><i><span style="font-size:9.0pt">Joshua Cranmer<o:p></o:p></span></i></p>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>