
<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Oct 5, 2015, at 19:41, Preston Briggs via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><span style="font-size:13px" class="">I'm working on generating code for a machine that has a register set kind of like the 68000.</span><div style="font-size:13px" class=""><br class=""><div class="">For those who don't recall, the 68K has 8 Data registers that can be used for ordinary integer</div><div class="">instructions like add, subtract, multiply, shift, etc., and 8 Address registers that can be use for</div><div class="">integer addition and a few other things, especially base registers for addressing modes.</div></div><div style="font-size:13px" class="">The Data register, on the other hand, cannot be used as base registers.</div></div></div></blockquote><div><br class=""></div><div>[…]</div><div><br class=""></div><div><blockquote type="cite" class=""><div dir="ltr" class=""><div class="" style="font-size: 13px;">So, finally, my question: Is there any similar scheme in LLVM's code generator?</div><div class="" style="font-size: 13px;">What I'm looking for is a way to select the one of the two available integer addition</div><div class="" style="font-size: 13px;">instructions (add using Address registers or add using Data registers) so as to</div><div class="" style="font-size: 13px;">minimize the number of Address-Data copies.</div></div></blockquote><div class=""><div dir="ltr" class=""><div class="" style="font-size: 13px;"><br class=""></div></div></div></div><div>Hi Preston,</div><div><br class=""></div><div>Short answer: No, LLVM can’t do that, and you have to roll your own pass to select add instructions.</div><div><br class=""></div><div>There is some support implemented for what you describe: Tablegen and the register allocator understand overlapping register classes. Tablegen will create a function to compute the intersection of two register classes, and it will create synthetic register classes to ensure that there is always an exact answer, no matter how you defined your register classes in the XXXRegisters.td file. See TargetRegisterInfo::getCommonSubClass().</div><div><br class=""></div><div>The instruction selector computes a register class for each live range by intersecting the requirements of each use-instruction like you describe. It also knows to insert copies when the intersection becomes empty. It doesn’t do this intelligently, but it does generate legal code.</div><div><br class=""></div><div>When live ranges are split during register allocation, the register class of the fragments is recomputed in case it becomes possible to use a larger register class. See MachineRegisterInfo::recomputeRegClass().</div><div><br class=""></div><div>We don’t compute an interference graph, but you could use getCommonSubClass() to test if two register classes are overlapping.</div><div><br class=""></div><div>I think LLVM’s instruction selection would be improved for many targets if it supported a generalization of your problem. It’s what I called “register bank selection” here: <a href="http://www.2pi.dk/llvm/global-isel.html" class="">http://www.2pi.dk/llvm/global-isel.html</a> The current instruction selector design uses a fixed mapping from IR types to register banks.</div><div><br class=""></div><div>It seems to me that the problem of optimal register bank selection could be expressed in similar terms as the problem of optimal global live range splitting, and I suspect that the algorithm in SpillPlacement.cpp could be generalized.</div><div><br class=""></div><div>Thanks,</div><div>/jakob</div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div style="font-size:13px" class=""><br class=""></div><div style="font-size:13px" class="">So, neither is more general than the other. We can use either for integer addition,</div><div style="font-size:13px" class="">but only Address registers as base registers and only Data registers for integer</div><div style="font-size:13px" class="">multiplication, etc. (I may have a few details wrong, but since this is only an example,</div><div style="font-size:13px" class="">I don't think they're too important.)</div><div style="font-size:13px" class=""><br class=""></div><div style="font-size:13px" class="">Back when, I defined 3 register classes: Address, Data, and General,</div><div style="font-size:13px" class="">where Address = 1, Data = 2, and General = 3.</div><div style="font-size:13px" class="">My approach was to begin by defining every symbolic register (aka live range)</div><div style="font-size:13px" class="">as General. Then I'd walk through all the instructions, intersecting the requirements</div><div style="font-size:13px" class="">for the particular instruction to yield a perhaps less general register class.</div><div style="font-size:13px" class=""><br class=""></div><div style="font-size:13px" class="">For example, an Add instruction would require and produce General registers (since we</div><div style="font-size:13px" class="">have add instructions for both Address and Data registers). But an addressing mode</div><div style="font-size:13px" class="">would require an Address register, so when we notice a General register being used in</div><div style="font-size:13px" class="">an addressing mode, intersection the Addressing requirement (= 1) with the General</div><div style="font-size:13px" class="">register (= 3) yields 1, implying the register needs to be an Address register.</div><div style="font-size:13px" class=""><br class=""></div><div style="font-size:13px" class="">When building the interference graph and noting that 2 live ranges were simultaneously live,</div><div style="font-size:13px" class="">if the intersection of their classes was non-zero, I'd add an interference to the IG.</div><div style="font-size:13px" class="">Similarly, I'd make symbolic registers of Address class interfere with all the machine's</div><div style="font-size:13px" class="">Data registers and vice versa. In this fashion, since live ranges that are more restricted</div><div style="font-size:13px" class="">(have higher degree) tend to be colored first, live ranges that must be Address or</div><div style="font-size:13px" class="">must be Data will end up in the right place, with the coloring algorithm naturally</div><div style="font-size:13px" class="">balancing everyone's requirements.</div><div style="font-size:13px" class=""><br class=""></div><div style="font-size:13px" class="">Care is required when a live range ends up with class = 0; implies copies are required.</div><div style="font-size:13px" class=""><br class=""></div><div style="font-size:13px" class="">So, finally, my question: Is there any similar scheme in LLVM's code generator?</div><div style="font-size:13px" class="">What I'm looking for is a way to select the one of the two available integer addition</div><div style="font-size:13px" class="">instructions (add using Address registers or add using Data registers) so as to</div><div style="font-size:13px" class="">minimize the number of Address-Data copies.</div><div style="font-size:13px" class=""><br class=""></div><div style="font-size:13px" class="">Thanks,</div><div style="font-size:13px" class="">Preston</div><div style="font-size:13px" class=""><br class=""></div></div>

_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></body></html>