<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal">Sure. I wouldn’t think that 4% of increase in the table size would have a significant impact on performance, but yes, the final decision would need to take that into account.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Consolas">-- </span>
<span style="font-size:9.0pt;font-family:Consolas"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:8.0pt;font-family:Consolas">Krzysztof Parzyszek
<a href="mailto:kparzysz@quicinc.com"><span style="color:#0563C1">kparzysz@quicinc.com</span></a> AI tools development<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> Jay Foad <jay.foad@gmail.com> <br>
<b>Sent:</b> Friday, November 13, 2020 4:46 AM<br>
<b>To:</b> Krzysztof Parzyszek <kparzysz@quicinc.com><br>
<b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> [EXT] Re: [llvm-dev] Musings on the TableGen -emit-dag-isel backend<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">I wouldn't want to be too hasty about simply removing the relaxation algorithm. The size and speed of the compiler affects all users, but the time to compile the compiler "only" affects us compiler developers. And I speak as a developer
who is heavily affected by the time to compile the AMDGPU backend.<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">One off-the-cuff idea (I haven't even looked at the code yet): could we pass in a null output stream while doing the relaxation phase, and use that to skip most of the actual textual formatting, followed by a final pass with a real output
stream once the offset has been determined?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Jay.<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">On Thu, 12 Nov 2020 at 16:43, Krzysztof Parzyszek via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">This is great! Thanks Paul!<br>
<br>
I think that the 9x reduction in compile-time is well worth the 4% size increase. TableGen's run-time has been a sore point and a source of complaints for quite some time.<br>
<br>
--<br>
Krzysztof Parzyszek <a href="mailto:kparzysz@quicinc.com" target="_blank">kparzysz@quicinc.com</a> AI tools development<br>
<br>
-----Original Message-----<br>
From: llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@lists.llvm.org</a>> On Behalf Of Paul C. Anagnostopoulos via llvm-dev<br>
Sent: Thursday, November 12, 2020 10:23 AM<br>
To: <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
Subject: [EXT] [llvm-dev] Musings on the TableGen -emit-dag-isel backend<br>
<br>
A rather notorious aspect of TableGen is the time required to run the -emit-dag-isel backend on some targets, including AMDGPU and X86. I added a timing feature to TableGen and timed the AMDGPU run.<br>
<br>
===-------------------------------------------------------------------------===<br>
TableGen Phase Timing ===-------------------------------------------------------------------------===<br>
Total Execution Time: 733.6103 seconds (733.8740 wall clock)<br>
<br>
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---<br>
645.0017 ( 87.9%) 0.2340 (100.0%) 645.2357 ( 88.0%) 645.2709 ( 87.9%) Emit matcher table<br>
70.4501 ( 9.6%) 0.0000 ( 0.0%) 70.4501 ( 9.6%) 70.5510 ( 9.6%) Convert to matchers<br>
14.6329 ( 2.0%) 0.0000 ( 0.0%) 14.6329 ( 2.0%) 14.7638 ( 2.0%) Parse, build records<br>
2.1996 ( 0.3%) 0.0000 ( 0.0%) 2.1996 ( 0.3%) 2.1871 ( 0.3%) Sort patterns<br>
1.0920 ( 0.1%) 0.0000 ( 0.0%) 1.0920 ( 0.1%) 1.0961 ( 0.1%) Optimize matchers<br>
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0050 ( 0.0%) Write output<br>
733.3763 (100.0%) 0.2340 (100.0%) 733.6103 (100.0%) 733.8740 (100.0%) Total<br>
<br>
As you can see, most of the time is spent emitting the C++ code. A simple step toward reducing the time is to use the --omit-comments option. However, I am informed that trying to debug the pattern matching table without comments is a hopeless task.<br>
<br>
===-------------------------------------------------------------------------===<br>
TableGen Phase Timing ===-------------------------------------------------------------------------===<br>
Total Execution Time: 162.9274 seconds (162.9173 wall clock)<br>
<br>
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---<br>
75.0833 ( 46.1%) 0.0468 ( 42.9%) 75.1301 ( 46.1%) 75.1313 ( 46.1%) Emit matcher table<br>
69.7948 ( 42.9%) 0.0000 ( 0.0%) 69.7948 ( 42.8%) 69.8050 ( 42.8%) Convert to matchers<br>
14.6173 ( 9.0%) 0.0468 ( 42.9%) 14.6641 ( 9.0%) 14.6668 ( 9.0%) Parse, build records<br>
2.2308 ( 1.4%) 0.0000 ( 0.0%) 2.2308 ( 1.4%) 2.2191 ( 1.4%) Sort patterns<br>
1.0920 ( 0.7%) 0.0000 ( 0.0%) 1.0920 ( 0.7%) 1.0921 ( 0.7%) Optimize matchers<br>
0.0000 ( 0.0%) 0.0156 ( 14.3%) 0.0156 ( 0.0%) 0.0030 ( 0.0%) Write output<br>
162.8182 (100.0%) 0.1092 (100.0%) 162.9274 (100.0%) 162.9173 (100.0%) Total<br>
<br>
Emitting the C++ code for most pattern operators is straightforward.<br>
However, three operators are more time-consuming: Matcher::Scope, SwitchOpcode, and SwitchType. These operators take a list of child patterns, each of which is emitted as a 1- to 3-byte size followed by the child's pattern bytes. The size is coded as a variable-length
sequence of bytes, as is every integer in the matcher table. (Just for interest, the average number of children per Scope operator is about 2.7.)<br>
<br>
In order to minimize the length of the size, the backend performs a sort of relaxation algorithm, where it first tries a 1-byte size. If that fails, it tries the actual required number of bytes. Trying involves calculating the offset in the table for the child
and then recursively generating the entire child, passing it a string buffer as its output stream. When the size is finally determined, that string buffer is appended to the actual buffer passed to the generation function.<br>
<br>
Why does the number of bytes in the size matter to the child? Because the offset of the child is determined by that size, and the offset is passed to the child and then included in many comments emitted by the child. If the size is wrong, then the offset is
wrong, and then the comments are wrong.<br>
<br>
So it's clear that repetitive code generating is done because of the relaxation algorithm. How bad is it? It turns out that the algorithm is about O(1.7^(n-1)), where n is the depth of the pattern matching tree. The depth of the AMDGPU tree is 13. Here are
some interesting statistics:<br>
<br>
Number of pattern operators at depth 11: 35,000<br>
Number of times those operators are regenerated: 20 million<br>
<br>
I think we have found the problem. So what can be done? I tried a quick and dirty experiment. I forced all the child sizes to occupy a 3-byte length, so that the relaxation algorithm was no longer necesseary. The results are shown here.<br>
<br>
===-------------------------------------------------------------------------===<br>
TableGen Phase Timing ===-------------------------------------------------------------------------===<br>
Total Execution Time: 90.7302 seconds (90.8242 wall clock)<br>
<br>
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---<br>
69.7324 ( 76.9%) 0.0000 ( 0.0%) 69.7324 ( 76.9%) 69.7320 ( 76.8%) Convert to matchers<br>
14.5705 ( 16.1%) 0.0312 ( 33.3%) 14.6017 ( 16.1%) 14.6958 ( 16.2%) Parse, build records<br>
3.0576 ( 3.4%) 0.0624 ( 66.7%) 3.1200 ( 3.4%) 3.1192 ( 3.4%) Emit matcher table<br>
2.1840 ( 2.4%) 0.0000 ( 0.0%) 2.1840 ( 2.4%) 2.1891 ( 2.4%) Sort patterns<br>
1.0920 ( 1.2%) 0.0000 ( 0.0%) 1.0920 ( 1.2%) 1.0831 ( 1.2%) Optimize matchers<br>
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0050 ( 0.0%) Write output<br>
90.6366 (100.0%) 0.0936 (100.0%) 90.7302 (100.0%) 90.8242 (100.0%) Total<br>
<br>
Now the matcher emitter phase is insignificant! Unfortunately, the size of the matchter table increases from 451,430 bytes to 469,612 bytes, an increase of 18,182 bytes or 4%.<br>
<br>
So one solution is not to care about the 4% increase and always use 3-byte child sizes. A second solution is to add an option that specifies the starting number of child size bytes and retains the relaxation algorithm.<br>
When building the system, we would specify --child-size-bytes=1. When building for debugging, you could specify --child-size-bytes=3.<br>
<br>
Comments and suggestion gratefully accepted.<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p>
</blockquote>
</div>
</div>
</body>
</html>