<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Quentin Colombet" <qcolombet@apple.com><br><b>To: </b>"Hal Finkel" <hfinkel@anl.gov><br><b>Cc: </b>"llvm-dev" <llvm-dev@lists.llvm.org><br><b>Sent: </b>Friday, January 15, 2016 1:37:50 PM<br><b>Subject: </b>Re: [llvm-dev] [GlobalISel][RFC] Value to vreg during IR to MachineInstr translation for aggregate type<br><br>
Hi Hal,<div class=""><br class=""></div><div class="">Thanks for your quick reply.</div><div class=""><br class=""><div><blockquote class=""><div class="">On Jan 14, 2016, at 4:53 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" class="" target="_blank">hfinkel@anl.gov</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class=""><hr id="zwchr"></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">From: "Quentin Colombet via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>><br class="">To: "llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>><br class="">Sent: Thursday, January 14, 2016 6:41:57 PM<br class="">Subject: [llvm-dev] [GlobalISel][RFC] Value to vreg during IR to<span class="Apple-tab-span" style="white-space: pre;"> </span>MachineInstr translation for aggregate type<br class=""><br class=""><br class="">Hi,<br class=""><br class=""><br class="">As part of the effort to bring up GlobalISel, I would like your<br class="">feedbacks on the best way to map LLVM IR values into MachineInstr<br class="">values (virtual registers), in particular when aggregate types get<br class="">involved.<br class=""><br class=""><br class="">I am looking for a long term solution.<br class="">Short term is to replicate SDAG solution.<br class=""><br class=""><br class=""><br class=""><br class="">** Context **<br class=""><br class=""><br class="">The first step of GlobalISel is to translate the LLVM IR into<br class="">MachineInstr representation. During this process we need to be able<br class="">to tell where are the different LLVM IR values with respect to their<br class="">machine representation, such that we can feed the right element to<br class="">the related machine instructions.<br class=""><br class=""><br class="">Right now, in SelectionDAG, we have a mapping from one Value* to one<br class="">SDValue. But this is not the whole story!<br class=""><br class=""><br class=""><br class=""><br class="">** Problem With Aggregate Types **<br class=""><br class=""><br class="">* Facts *<br class=""><br class=""><br class="">- Aggregate types cannot be expressed with a single EVT (Extended<br class="">Value Type)<br class="">- SDValues are typed with a single EVT.<br class=""><br class=""><br class="">Therefore, values with aggregate types need to be break apart to be<br class="">represented by a SDValue.<br class=""><br class=""><br class="">* Implications *<br class=""><br class=""><br class="">- Instructions that may accept aggregate type, e.g., load, store, and<br class="">select, must be split to handle the different component that compose<br class="">a Value. (Look for the use of ComputeValueVTs in the<br class="">SelecionDAGBuilder and the related loops this implies).<br class="">- Use of aggregate type generates a bunch of MERGE_VALUE nodes, which<br class="">sole purpose is to glue all the components that make the aggregate<br class="">type together.<br class=""><br class=""><br class="">Therefore, in practice, values with aggregate types are mapped to<br class="">several SDValue hidden in MERGE_VALUE nodes.<br class=""><br class=""><br class="">* Summary *<br class=""><br class=""><br class="">Values with aggregate type map to a list of SDValue and,<br class="">consequently, the handling of the instructions is uneven between the<br class="">ones that need to support aggregate type and the ones that do not.<br class=""><br class=""><br class=""><br class=""><br class="">** Possible Solutions **<br class=""><br class=""><br class="">* A. Replicate SDAG Solution *<br class=""><br class=""><br class="">Not much to add from the title. One can see that in the sketch of<br class="">patch for the IRTranslator (from the original GlobalISel email<br class=""><a href="http://lists.llvm.org/pipermail/llvm-dev/2015-November/092566.html" class="" target="_blank">http://lists.llvm.org/pipermail/llvm-dev/2015-November/092566.html</a><br class="">), we have a map from a Value to a list of virtual registers.<br class=""><br class=""><br class="">Pros:<br class="">- We know it worked for SDAG.<br class="">- We know backends would generate reasonable code from that.<br class=""><br class=""><br class="">Cons:<br class="">- We need to pay (compile time, memory consumption) for the extra<br class="">logic for every non-aggregate type.<br class="">- Translation is not homogeneous between, say, add and store.<br class="">- Premature splitting that need to be fixed later(?), e.g., merge<br class="">consecutive stores.<br class=""><br class=""><br class=""><br class=""><br class="">* B. Map Aggregate Type to One (Big) Virtual Register *<br class=""><br class=""><br class="">Have one big virtual register for the whole aggregate type. Only the<br class="">size of the register matters for the instructions that handle<br class="">aggregate type, so we can still use EVT for virtual registers.<br class=""><br class=""><br class="">Pros:<br class="">- Translation is fast.<br class="">- Code is easy to understand.<br class="">- No premature splitting for instance for load instructions.<br class=""><br class=""><br class="">Cons:<br class="">- Useless bits (padding) are carried around and may be hard to<br class="">eliminate.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">We could associate some metadata with the register somehow to represent the padding bits (we already do something like this for memcpy).</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""></div></blockquote><div><br class=""></div><div id="DWT9868">The problem I have with metadata is that they can be lost.</div></div></div></blockquote><br>Sorry, I meant metadata in the more-general sense (not actual IR metadata can can be dropped). Something actually associated with the vreg itself.<br><br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div class=""><div><div></div><div id="DWT9869">That being said, having a mechanism to tell the optimizer what are in a register would be useful. Right now, to get this kind of information we use the computeKnownBits analysis and I wonder how could we generalize that so that the information is cheaper to get and pass along the way.</div></div></div></blockquote><br>Agreed. Reducing the computeKnownBits cost would be a good thing. We could use caching (or an actual forward analysis), and that might help.<br><br> -Hal<br><br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div class=""><div><div></div><br class=""><blockquote class=""><div class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">- Expose weird types to legalization more often.<br class="">- Backends may not cope very well with that kind of code.<br class=""><br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Given that every backend is going to need major work to truly make this transition, I'd advise not to worry too much about your last item.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Seems like this second option is better than replicating the SDAG solution, so I recommend we pursue that.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""></div></blockquote><div><br class=""></div><div>My guts tell me that indeed the second option is better, but the lack of actual data makes me nervous.</div><div>Anyway, we don’t have to support aggregates to lay the basic pipeline. And when the basic pipeline is set, we can make actual measurements!</div><div><br class=""></div><div>I’ve filed <a href="https://llvm.org/bugs/show_bug.cgi?id=26161" class="" target="_blank">https://llvm.org/bugs/show_bug.cgi?id=26161</a> to keep track of that issue.</div><div><br class=""></div><div>Thanks,</div><div>-Quentin</div><div><br class=""></div><br class=""><blockquote class=""><div class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">-Hal</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br class="">* C. Ideas *<br class=""><br class=""><br class="">Any other ideas?<br class=""><br class=""><br class=""><br class=""><br class="">** Feedback Needed **<br class=""><br class=""><br class="">I want to have your feedbacks on how we should model aggregate types<br class="">during the IR translation with respect to the mapping to their<br class="">machine representation.<br class=""><br class=""><br class="">This is not a road blocker as, at first, I will replicate SDAG<br class="">solution, but I want we have a conversation on what is the best long<br class="">term solution.<br class=""><br class=""><br class="">I will file a PR so that we remember we would need to come back to<br class="">this part of the implementation of the prototype when we agreed on<br class="">what the solution should be and look at productizing the selector.<br class=""><br class=""><br class=""><br class=""><br class="">** Example **<br class=""><br class=""><br class="">Consider the following LLVM IR input:<br class=""><br class="">%struct.bar = type { i16, i16 }<br class=""><br class=""><br class="">define void @foo(i16 signext %a, i16 signext %b, %struct.bar*<br class="">nocapture %addr) #0 {<br class="">entry:<br class="">%tmp = insertvalue %struct.bar undef, i16 %a, 0<br class="">%tmp2 = insertvalue %struct.bar %tmp, i16 %b, 1<br class="">store %struct.bar %tmp2, %struct.bar* %addr, align 4<br class="">ret void<br class="">}<br class=""><br class=""><br class="">Which is roughly:<br class=""><br class="">struct bar {<br class="">short a;<br class="">short b;<br class="">};<br class=""><br class=""><br class="">void foo(short a, short b, struct bar *addr) {<br class="">struct bar tmp;<br class="">tmp.a = a;<br class="">tmp.b = b;<br class="">*addr = tmp;<br class="">}<br class=""><br class=""><br class="">* Solution A: Replicate SDAG *<br class=""><br class=""><br class="">Note: (#) is the size of the virtual register.<br class=""><br class=""><br class="">- Translation:<br class=""><br class=""><br class=""><br class=""><br class="">arg1(32) = copy R0<br class="">arg2(32) = copy R1<br class="">addr(32) = copy R2<br class="">a(16) = truncate arg1(32)<br class="">b(16) = truncate arg2(32)<br class="">tmp5(16), tmp6(16) = merge_value a(16), b(16)<br class="">store tmp5(16), addr(32), 0<br class="">store tmp6(16), addr(32), 4<br class=""><br class=""><br class="">- Legalization:<br class=""><br class=""><br class=""><br class="">arg1(32) = copy R0<br class="">arg2(32) = copy R1<br class="">addr(32) = copy R2<br class="">tmp5(16) = extract_subreg a(32), 0<br class=""><br class="">tmp6(16) = extract_subreg b(32), 0<br class="">store tmp5(16), addr(32), 0<br class="">store tmp6(16), addr(32), 4<br class=""><br class=""><br class=""><br class=""><br class="">* Solution B: One to one mapping Value to Vreg *<br class=""><br class=""><br class="">- Translation:<br class=""><br class=""><br class="">arg1(32) = copy R0<br class="">arg2(32) = copy R1<br class="">addr(32) = copy R2<br class="">a(16) = truncate arg1(32)<br class="">b(16) = truncate arg2(32)<br class="">tmp(32) = concat a(16), b(16)<br class="">store tmp(32), addr<br class=""><br class=""><br class="">- Legalization:<br class=""><br class=""><br class=""><br class="">arg1(32) = copy R0<br class="">arg2(32) = copy R1<br class="">addr(32) = copy R2<br class="">a(32) = and arg1(32), 0xFFFF<br class="">b(32) = and arg2(32), 0xFFFF<br class="">tmp(32) = concat a(32/16), b(32/16) ; <— although the input registers<br class="">are 32bits we are really only interested in the 16bit low part of<br class="">both a and b.<br class="">store tmp(32), addr ; <— legal<br class=""><br class=""><br class="">The problem now is how do we legalize that thing with generic code?<br class="">I.e., we’ll end up with either load/store sequences (maybe storing<br class="">i16 is not even legal) or SHIFT and OR and that may be painful to<br class="">optimize later.<br class=""><br class=""><br class="">Thanks,<br class="">-Quentin<br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a><br class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" class="" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class=""><br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">--<span class="Apple-converted-space"> </span></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Hal Finkel</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Assistant Computational Scientist</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Leadership Computing Facility</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Argonne National Laboratory</span></div></blockquote></div><br class=""></div></blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>