<div dir="ltr"><span id="gmail-docs-internal-guid-e7b5499c-7fff-22b9-d56e-1ed4307b8701"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:10pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">[RFC] MLGO for Regalloc: learned eviction policy for regalloc</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:10pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">alphabetical list of authors: Eugene Brevdo, David Li, Yundi Qian, Mircea Trofin</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:10pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">Summary: continuing from our experience with the </span><a href="https://lists.llvm.org/pipermail/llvm-dev/2020-April/140763.html" style="text-decoration-line:none"><span style="font-size:11pt;font-family:"Courier New";background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;text-decoration-line:underline;vertical-align:baseline;white-space:pre-wrap">inliner for size</span></a><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">, we were able to learn live range eviction for the ‘greedy’ register allocator, with measurable, positive results on some datacenter-type applications (from 0.3% up to 1.5% improvement in QPS (query per second) on selected internal ThinLTO + FDO apps). </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:10pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">Just like in the inliner case, and salient to our approach, opting in to the learned policy maintains critical compiler invariants, like determinism and timeliness, and does not add new runtime dependencies.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:10pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">Details:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:10pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">The proposed changes are:</span></p><ul style="margin-top:0px;margin-bottom:0px"><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:10pt" role="presentation"><span style="font-size:11pt;background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">the main change (<a href="https://reviews.llvm.org/D113525">https://reviews.llvm.org/D113525</a>)</span><span style="font-size:11pt;background-color:transparent;font-weight:700;font-style:italic;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-size:11pt;background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">is a NFC - factoring eviction as an ImmutablePass, </span><span style="font-size:11pt;background-color:transparent;font-style:italic;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">RegAllocEvictionAdvisorAnalysis</span><span style="font-size:11pt;background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">. It can be queried for an implementation of </span><span style="font-size:11pt;background-color:transparent;font-style:italic;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">RegAllocEvictionAdvisor</span><span style="font-size:11pt;background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">. By default, that implementation is today’s behavior.</span></p></li></ul><p dir="ltr" style="line-height:1.38;margin-left:36pt;margin-top:0pt;margin-bottom:10pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">This design is similar to what we did for the inliner with </span><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-style:italic;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">InlineAdvisor</span><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">. We expect the factoring to create opportunities for other initiatives, just like it did in the inliner case (see @modimo’s inline replay work, for example).</span></p><ul style="margin-top:0px;margin-bottom:0px"><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:10pt" role="presentation"><span style="font-size:11pt;background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">all the ML stuff is an alternative implementation of </span><span style="font-size:11pt;background-color:transparent;font-style:italic;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">RegAllocEvictionAdvisor</span><span style="font-size:11pt;background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">, and needs to be opted in. Size of change - wise, the ML support will be relatively small, as we are leveraging the existing infrastructure we have already introduced with the inliner work (including leveraging the same build bots)</span></p></li></ul><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:10pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">MLGO-specific details:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:10pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">We plan to first introduce ‘development mode’, i.e. the support for training a policy, then ‘release mode’, i.e. the way in which a pre-trained policy is meant to be leveraged in production. This greatly simplifies integration on our side, and should also allow anyone wishing to train a policy with their training algorithm to do so. Separately, we have been upstreaming the training infrastructure pertinent to the regalloc work to </span><a href="http://github.com/google/ml-compiler-opt" style="text-decoration-line:none"><span style="font-size:11pt;font-family:"Courier New";background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;text-decoration-line:underline;vertical-align:baseline;white-space:pre-wrap">github.com/google/ml-compiler-opt</span></a><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">.</span></p></span><br class="gmail-Apple-interchange-newline"></div>