<div dir="ltr"><div class="markdown-here-wrapper" style=""><p style="margin:1.2em 0px!important">Hello all,</p>
<p style="margin:1.2em 0px!important">I would like to propose a large change to LLVM that I would be happy to implement.</p>
<p style="margin:1.2em 0px!important">The instruction selection legalizer knows of three different ways to legalize an action (ignoring an already legal action).</p>
<ul style="margin:1.2em 0px;padding-left:2em">
<li style="margin:0.5em 0px">Expansion</li>
<li style="margin:0.5em 0px">Promotion</li>
<li style="margin:0.5em 0px">Custom</li>
</ul>
<p style="margin:1.2em 0px!important">Expanding a node will lead to one of two things - the operation will be split into several equivalent smaller operations (i.e. 64-bit mul => two 32-bit multiplications), or it will be expanded into a different operation(s) (i.e. <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">SDIVREM</code> => <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">SDIV</code> + <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">SREM</code> or a runtime library call).</p>
<p style="margin:1.2em 0px!important">This can be ambiguous - should a 128-bit <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">SDIVREM</code> be expanded into two 64-bit <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">SDIVREM</code>s or a 128-bit libcall.</p>
<p style="margin:1.2em 0px!important">It would be useful for LLVM to distinguish between these two operations - i.e. instead of <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">LegalizeAction::Expand</code>, we have <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">LegalizeAction::Expand</code> and <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">LegalizeAction::Split</code>.</p>
<ul style="margin:1.2em 0px;padding-left:2em">
<li style="margin:0.5em 0px"><p style="margin:1.2em 0px!important;margin:0.5em 0px!important"><code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">Expand</code> should always expand the node into a different pattern (such as <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">MULHU</code> expanding to <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">MUL</code> and a copy of the top half).</p>
</li>
<li style="margin:0.5em 0px"><p style="margin:1.2em 0px!important;margin:0.5em 0px!important"><code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">Split</code> will always split an operation into several smaller, operations (such as 128-bit addition being split into a 64-bit addition and a 64-bit addition with carry)</p>
</li>
</ul>
<p style="margin:1.2em 0px!important">Full disclosure: I’m working on a backend on which the pointer type is illegal (Atmel AVR : 8-bit microcontroller with 16-bit pointers). The problem with the ambiguity with expand today is that LLVM implicitly assumes that as a 16-bit register class exists, then 16-bit addition/subtraction should exist and there is no point splitting into two 8-bit operations.</p>
<p style="margin:1.2em 0px!important">Currently we work around this by defining 16-bit pseudo instructions for every instruction which is not properly supported. This gives us very sub-optimal code and introduces many bugs. More detail about the problem can be found in the old mailing list <a href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-June/087277.html">archives</a>.</p>
<p style="margin:1.2em 0px!important">I’m not sure if this requires an RFC? It would be a very large breaking change. Perhaps a less drastic solution can be found, like leaving <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">Expand</code> as it is, but also adding <code style="font-size:0.85em;font-family:Consolas,Inconsolata,Courier,monospace;margin:0px 0.15em;padding:0px 0.3em;white-space:pre-wrap;border:1px solid rgb(234,234,234);border-radius:3px;display:inline;background-color:rgb(248,248,248)">LegalizeAction::Split</code> which must expand only using smaller operations.</p>
<p style="margin:1.2em 0px!important">Again, I would be happy to work on this.</p>
<p style="margin:1.2em 0px!important">Cheers,<br>Dylan McKay</p>
<div title="MDH:SGVsbG8gYWxsLDxkaXY+PGJyPjwvZGl2PjxkaXY+SSB3b3VsZCBsaWtlIHRvIHByb3Bvc2UgYSBs
YXJnZSBjaGFuZ2UgdG8gTExWTSB0aGF0IEkgd291bGQgYmUgaGFwcHkgdG8gaW1wbGVtZW50Ljwv
ZGl2PjxkaXY+PGJyPjwvZGl2PjxkaXY+VGhlIGluc3RydWN0aW9uIHNlbGVjdGlvbiBsZWdhbGl6
ZXIga25vd3Mgb2YgdGhyZWUgZGlmZmVyZW50IHdheXMgdG8gbGVnYWxpemUgYW4gYWN0aW9uIChp
Z25vcmluZyBhbiBhbHJlYWR5IGxlZ2FsIGFjdGlvbikuPC9kaXY+PGRpdj48YnI+PC9kaXY+PGRp
dj4qIEV4cGFuc2lvbjwvZGl2PjxkaXY+KiBQcm9tb3Rpb248L2Rpdj48ZGl2PiogQ3VzdG9tPC9k
aXY+PGRpdj48YnI+PC9kaXY+PGRpdj5FeHBhbmRpbmcgYSBub2RlIHdpbGwgbGVhZCB0byBvbmUg
b2YgdHdvIHRoaW5ncyAtIHRoZSBvcGVyYXRpb24gd2lsbCBiZSBzcGxpdCBpbnRvIHNldmVyYWwg
ZXF1aXZhbGVudCBzbWFsbGVyIG9wZXJhdGlvbnMgKGkuZS4gNjQtYml0IG11bCA9Jmd0OyB0d28g
MzItYml0IG11bHRpcGxpY2F0aW9ucyksIG9yIGl0IHdpbGwgYmUgZXhwYW5kZWQgaW50byBhIGRp
ZmZlcmVudCBvcGVyYXRpb24ocykgKGkuZS4gYFNESVZSRU1gID0mZ3Q7IGBTRElWYCArIGBTUkVN
YCBvciBhIHJ1bnRpbWUgbGlicmFyeSBjYWxsKS48L2Rpdj48ZGl2Pjxicj48L2Rpdj48ZGl2PlRo
aXMgY2FuIGJlIGFtYmlndW91cyAtIHNob3VsZCBhIDEyOC1iaXQgYFNESVZSRU1gIGJlIGV4cGFu
ZGVkIGludG8gdHdvIDY0LWJpdCBgU0RJVlJFTWBzIG9yIGEgMTI4LWJpdCBsaWJjYWxsLjwvZGl2
PjxkaXY+PGJyPjwvZGl2PjxkaXY+SXQgd291bGQgYmUgdXNlZnVsIGZvciBMTFZNIHRvIGRpc3Rp
bmd1aXNoIGJldHdlZW4gdGhlc2UgdHdvIG9wZXJhdGlvbnMgLSBpLmUuIGluc3RlYWQgb2YgYExl
Z2FsaXplQWN0aW9uOjpFeHBhbmRgLCB3ZSBoYXZlIGBMZWdhbGl6ZUFjdGlvbjo6RXhwYW5kYCBh
bmQgYExlZ2FsaXplQWN0aW9uOjpTcGxpdGAuPC9kaXY+PGRpdj48YnI+PC9kaXY+PGRpdj4qIGBF
eHBhbmRgIHNob3VsZCBhbHdheXMgZXhwYW5kIHRoZSBub2RlIGludG8gYSBkaWZmZXJlbnQgcGF0
dGVybiAoc3VjaCBhcyBgTVVMSFVgIGV4cGFuZGluZyB0byBgTVVMYCBhbmQgYSBjb3B5IG9mIHRo
ZSB0b3AgaGFsZikuPC9kaXY+PGRpdj48YnI+PC9kaXY+PGRpdj4qIGBTcGxpdGAgd2lsbCBhbHdh
eXMgc3BsaXQgYW4gb3BlcmF0aW9uIGludG8gc2V2ZXJhbCBzbWFsbGVyLCBvcGVyYXRpb25zIChz
dWNoIGFzIDEyOC1iaXQgYWRkaXRpb24gYmVpbmcgc3BsaXQgaW50byBhIDY0LWJpdCBhZGRpdGlv
biBhbmQgYSA2NC1iaXQgYWRkaXRpb24gd2l0aCBjYXJyeSk8L2Rpdj48ZGl2Pjxicj48L2Rpdj48
ZGl2PkZ1bGwgZGlzY2xvc3VyZTogSSdtIHdvcmtpbmcgb24gYSBiYWNrZW5kIG9uIHdoaWNoIHRo
ZSBwb2ludGVyIHR5cGUgaXMgaWxsZWdhbCAoQXRtZWwgQVZSIDogOC1iaXQgbWljcm9jb250cm9s
bGVyIHdpdGggMTYtYml0IHBvaW50ZXJzKS4gVGhlIHByb2JsZW0gd2l0aCB0aGUgYW1iaWd1aXR5
IHdpdGggZXhwYW5kIHRvZGF5IGlzIHRoYXQgTExWTSBpbXBsaWNpdGx5IGFzc3VtZXMgdGhhdCBh
cyBhIDE2LWJpdCByZWdpc3RlciBjbGFzcyBleGlzdHMsIHRoZW4gMTYtYml0IGFkZGl0aW9uL3N1
YnRyYWN0aW9uIHNob3VsZCBleGlzdCBhbmQgdGhlcmUgaXMgbm8gcG9pbnQgc3BsaXR0aW5nIGlu
dG8gdHdvIDgtYml0IG9wZXJhdGlvbnMuPC9kaXY+PGRpdj48YnI+PC9kaXY+PGRpdj5DdXJyZW50
bHkgd2Ugd29yayBhcm91bmQgdGhpcyBieSBkZWZpbmluZyAxNi1iaXQgcHNldWRvIGluc3RydWN0
aW9ucyBmb3IgZXZlcnkgaW5zdHJ1Y3Rpb24gd2hpY2ggaXMgbm90IHByb3Blcmx5IHN1cHBvcnRl
ZC4gVGhpcyBnaXZlcyB1cyB2ZXJ5IHN1Yi1vcHRpbWFsIGNvZGUgYW5kIGludHJvZHVjZXMgbWFu
eSBidWdzLiBNb3JlIGRldGFpbCBhYm91dCB0aGUgcHJvYmxlbSBjYW4gYmUgZm91bmQgaW4gdGhl
IG9sZCBtYWlsaW5nIGxpc3QgW2FyY2hpdmVzXShodHRwOi8vbGlzdHMuY3MudWl1Yy5lZHUvcGlw
ZXJtYWlsL2xsdm1kZXYvMjAxNS1KdW5lLzA4NzI3Ny5odG1sKS48L2Rpdj48ZGl2Pjxicj48L2Rp
dj48ZGl2PkknbSBub3Qgc3VyZSBpZiB0aGlzIHJlcXVpcmVzIGFuIFJGQz8gSXQgd291bGQgYmUg
YSB2ZXJ5IGxhcmdlIGJyZWFraW5nIGNoYW5nZS4gUGVyaGFwcyBhIGxlc3MgZHJhc3RpYyBzb2x1
dGlvbiBjYW4gYmUgZm91bmQsIGxpa2UgbGVhdmluZyBgRXhwYW5kYCBhcyBpdCBpcywgYnV0IGFs
c28gYWRkaW5nIGBMZWdhbGl6ZUFjdGlvbjo6U3BsaXRgIHdoaWNoIG11c3QgZXhwYW5kIG9ubHkg
dXNpbmcgc21hbGxlciBvcGVyYXRpb25zLjwvZGl2PjxkaXY+PGJyPjwvZGl2PjxkaXY+QWdhaW4s
IEkgd291bGQgYmUgaGFwcHkgdG8gd29yayBvbiB0aGlzLjwvZGl2PjxkaXY+PGJyPjwvZGl2Pjxk
aXY+Q2hlZXJzLDwvZGl2PjxkaXY+RHlsYW4gTWNLYXk8L2Rpdj4=" style="height:0;width:0;max-height:0;max-width:0;overflow:hidden;font-size:0em;padding:0;margin:0">​</div></div></div>