<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Thu, 11 Oct 2018 at 18:29, Adam Nemet via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space"><div><blockquote type="cite"><div>On Oct 11, 2018, at 3:42 PM, Richard Smith <<a href="mailto:richard@metafoo.co.uk" target="_blank">richard@metafoo.co.uk</a>> wrote:</div><br class="m_-4430073118430631162Apple-interchange-newline"><div><div dir="ltr" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Wed, 10 Oct 2018 at 23:10, Adam Nemet via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div><div dir="auto">Hi,<div><br></div><div>We are proposing first-class type support for a new matrix type.  This is a natural extension of the current vector type with an extra dimension.<br>For example, this is what the IR for a matrix multiply would look like for a 4x4 matrix with element type float:<br><br><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>%0 = load <4 x 4 x float>, <4 x 4 x float>* %a, align 16</div><div>%1 = load <4 x 4 x float>, <4 x 4 x float>* %b, align 16</div><div>%2 = call <4 x 4 x float> @llvm.matrix.multiply.m4_4f32.m4_4f32.m4_4f32(<4 x 4 x float> %0, <4 x 4 x float> %1)</div><div>store <4 x 4 x float> %2, <4 x 4 x float>* %c, align 16</div></blockquote><div><br>Currently we support element-wise binary operations, matrix multiply, matrix-scalar multiply, matrix transpose, extract/insert of an element.  Besides the regular full-matrix load and store, we also support loading and storing a matrix as a submatrix of a larger matrix in memory.  We are also planning to implement vector-extract/insert and matrix-vector multiply.<br><br>All of these are currently implemented as intrinsics.  Where applicable we also plan to support these operations with native IR instructions (e.g. add/fadd).<br><br>These are exposed in clang via builtins.  E.g. the above operations looks like this in C/C++:<br><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>typedef float mf4x4_t __attribute__((matrix_type(4, 4)));</div><div><br></div><div>mf4x4_t add(mf4x4_t a, mf4x4_t b) {</div><div> <span class="m_-4430073118430631162Apple-converted-space"> </span>return __builtin_matrix_multiply(a, b);</div><div>}</div></blockquote></div></div></div></blockquote><div><br></div><div>This seems to me to be proposing two distinct things -- built-in matrix support in the frontend as a language extension, and support for matrices in LLVM IR -- and I think it makes sense to discuss them at least somewhat separately.</div><div><br></div><div><br></div><div>On the Clang side: our general policy for frontend language extensions is described here: <a href="http://clang.llvm.org/get_involved.html" target="_blank">http://clang.llvm.org/get_involved.html</a></div><div><br></div><div>I'm totally happy to assume that you can cover most of those points, but point 4 seems likely to be a potential sticking point. Have you talked to WG14 about adding a matrix extension to C? (I'd note that they don't even have a vector language extension yet, but as noted on that page, we should be driving the relevant standards, not diverging from them, so perhaps we should be pushing for that too). Have you talked to the people working on adding vector types to C++ about this (in particular, Matthias Kretz and Tim Shen; see<span class="m_-4430073118430631162Apple-converted-space"> </span><a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0214r9.pdf" target="_blank">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0214r9.pdf</a><span class="m_-4430073118430631162Apple-converted-space"> </span>and<span class="m_-4430073118430631162Apple-converted-space"> </span><a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4454.pdf" target="_blank">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4454.pdf</a><span class="m_-4430073118430631162Apple-converted-space"> </span>for current / prior work in this area)?</div></div></div></div></div></div></div></blockquote><div><br></div><div>Yes, we’re certainly interested pushing this into the appropriate language standards.  As I was saying in the proposal, right now this is experimental.  We see great performance improvement with this but we’d like to get feedback and data from the wider community and also continue to improve the implementation.  Also the surface area for this extension is pretty minimal and piggybacks vector.  As you’ve seen in the thread there is a diverse set of people from GPU to CPU expressing interests and preferences.  My goal was to put this out there and have people collaborate and then propose what’s actually working.  Obviously ABI is a big consideration here and I don’t want to design in a vacuum.  Would this model work for you?</div></div></div></blockquote><div><br></div><div>Yes, I think that's OK, but I also think you should start talking to the relevant people from WG14 and WG21 early (ie, right now) so that they can provide feedback to you and vice versa about the needs of the most likely eventual language model and of the optimizer. We don't want to find in a year or two that this somehow fundamentally fails to satisfy the frontend language needs, or conversely that WG21 has standardized something that's problematic to lower to our optimizable primitives.</div><div><br></div><div>If you've not done so already, it'd be a good idea to also talk to the Eigen folks to make sure that what you're adding is something they could use in the cases where it's applicable.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space"><div><div>I also strongly believe that the right approach for good matrix performance is gradual lowering rather than lowering all the way to loops and then trying to recover the original intent of the program which is what the above approach takes.</div><br><blockquote type="cite"><div><div dir="ltr" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div>On the LLVM IR side, I'm personally unconvinced that we should model matrices in the IR directly as a new first-class type, unless there's some target out there that has matrix operations in hardware / matrix registers, but IR is not really my area of expertise so give that opinion as much or little weight as you see fit.</div></div></div></div></div></div></div></blockquote><div><br></div><div>Since people already spoke up about direct HW needs, you’re probably satisfied here</div></div></div></blockquote><div><br></div><div>Yes, I am.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space"><div><div>but as I said there are other benefits.  For a chain of matrix operations it is very beneficial to fuse the operations and then have it operate on tiles of the matrices at a time.  You don’t need to go to very large matrices at all to start to hit this.</div></div></div></blockquote><div><br></div><div>Well, modern C++ matrix libraries deal with similar issues using expression templates, but such an approach is certainly not without drawbacks.</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space"><div><blockquote type="cite"><div><div dir="ltr" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div> However, I do wonder: how is this different from, say, complex numbers, for which we don't have a native IR representation? (Maybe the answer is that we should have native IR support for complex numbers too.)</div></div></div></div></div></div></div></blockquote><div><br></div><div>That’s hard for me to answer as I didn’t look at complex-number performance.  </div><br><blockquote type="cite"><div><div dir="ltr" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div> How would you expect the frontend to lower (eg) matrix multiplication for matrices of complex numbers?</div></div></div></div></div></div></div></blockquote><div><br></div><div>As you say, complex numbers are not a first-class type so this is not supported just like it’s not for vectors, i.e. you’d have to use an array of complex numbers.  That said this may tip the scales to introduce complex numbers as well.</div></div></div></blockquote><div><br></div><div>This seems worth thinking about early, even if you choose to defer implementing anything in this space.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space"><div><div>Adam</div><div><br></div><blockquote type="cite"><div><div dir="ltr" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div><div dir="auto"><div><div>** Benefits **<br><br>Having matrices represented as IR values allows for the usual algebraic and redundancy optimizations.  But most importantly, by lifting memory aliasing concerns, we can guarantee vectorization to target-specific vectors.  Having a matrix-multiply intrinsic also allows using FMA regardless of the optimization level which is the usual sticking point with adopting FP-contraction.<br><br>Adding a new dedicated first-class type has several advantages over mapping them directly to existing IR types like vectors in the front end.  Matrices have the unique requirement that both rows and columns need to be accessed efficiently.  By retaining the original type, we can analyze entire chains of operations (after inlining) and determine the most efficient <b>intermediate layout</b> for the matrix values between ABI observable points (calls, memory operations).<br><br>The resulting intermediate layout could be something like a single vector spanning the entire matrix or a set of vectors and scalars representing individual rows/columns.  This is beneficial for example because rows/columns would be aligned to the HW vector boundary (e.g. for a 3x3 matrix).</div><div><br></div><div>The layout could also be made up of tiles/submatrices of the matrix.  This is an important case for us to fight register pressure.  Rather than loading entire matrices into registers it lets us load only parts of the input matrix at a time in order to compute some part of the output matrix.  Since this transformation reorders memory operations, we may also need to emit run-time alias checks.<br><br>Having a dedicated first-class type also allows for dedicated target-specific <b>ABIs</b> for matrixes.  This is a pretty rich area for matrices.  It includes whether the matrix is stored row-major or column-major order.  Whether there is padding between rows/columns.  When and how matrices are passed in argument registers.  Providing flexibility on the ABI side was critical for the adoption of the new type at Apple.<br><br>Having all this knowledge at the IR level means that <b>front-ends</b> are able to share the complexities of the implementation.  They just map their matrix type to the IR type and the builtins to intrinsics.<br><br>At Apple, we also need to support <b>interoperability</b> between row-major and column-major layout.  Since conversion between the two layouts is costly, they should be separate types requiring explicit instructions to convert between them.  Extending the new type to include the order makes tracking the format easy and allows finding optimal conversion points.<br><br>** ABI **<br><br>We currently default to column-major order with no padding between the columns in memory.  We have plans to also support row-major order and we would probably have to support padding at some point for targets where unaligned accesses are slow.  In order to make the IR self-contained I am planning to make the defaults explicit in the DataLayout string.<br><br>For function parameters and return values, matrices are currently placed in memory.  Moving forward, we should pass small matrices in vector registers.  Treating matrices as structures of vectors seems a natural default.   This works well for AArch64, since Homogenous Short-Vector Aggregates (HVA) can use all 8 SIMD argument registers.  Thus we could pass for example two 4 x 4 x float matrices in registers.  However on X86, we can only pass “four eightbytes”, thus limiting us to two 2 x 2 x float matrices.<br><br>Alternatively, we could treat a matrix as if its rows/columns were passed as separate vector arguments.  This would allow using all 8 vector argument registers on X86 too.</div><div><br></div><div>Alignment of the matrix type is the same as the alignment of its first row/column vector.  <br><br>** Flow **<br><br>Clang at this point mostly just forwards everything to LLVM.  Then in LLVM, we have an IR function pass that lowers the matrices to target-supported vectors.  As with vectors, matrices can be of any static size with any of the primitive types as the element type.</div><div><br></div><div>After the lowering pass, we only have matrix function arguments and instructions building up and splitting matrix values from and to vectors.  CodeGen then lowers the arguments and forwards the vector values.  CodeGen is already capable of further lowering vectors of any size to scalars if the target does not support vectors.</div><div><br></div><div>The lowering pass is also run at -O0 rather than legitimizing the matrix type during CodeGen like it’s done for structure values or invalid vectors.  I don’t really see a big value of duplicating this logic across the IR and CodeGen.  We just need a lighter mode in the pass at -O0.</div><div><br></div><div>** Roll-out and Maintenance **<br><br>Since this will be experimental for some time, I am planning to put this behind a flag: -fenable-experimental-matrix-type.  ABI and intrinsic compatibility won’t be guaranteed initially until we lift the experimental status.</div><div><br></div><div>We are obviously interested in maintaining and improving this code in the future.</div><div><br></div><div>Looking forward to comments and suggestions.</div><div><br></div><div>Thanks,</div><div>Adam</div></div></div></div>_______________________________________________<br>cfe-dev mailing list<br><a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a></blockquote></div></div></div></div></div></div></blockquote></div><br></div>_______________________________________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a><br>
</blockquote></div></div>