<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:x="urn:schemas-microsoft-com:office:excel" 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=us-ascii">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@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:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoPlainText, li.MsoPlainText, div.MsoPlainText
{mso-style-priority:99;
mso-style-link:"Plain Text Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
span.PlainTextChar
{mso-style-name:"Plain Text Char";
mso-style-priority:99;
mso-style-link:"Plain Text";
font-family:"Calibri","sans-serif";}
.MsoChpDefault
{mso-style-type:export-only;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 70.85pt 2.0cm 70.85pt;}
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="DE" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoPlainText"><span lang="EN-US">Some time ago we reported a compile-time performance regression in the LiveIntervals analysis pass (see
<a href="http://llvm.org/bugs/show_bug.cgi?id=18580">http://llvm.org/bugs/show_bug.cgi?id=18580</a>). We detected it at first after migrating from LLVM 3.1 to 3.3, but the problem persists also in 3.5. This regression is especially critical when compiling long
functions. In one of our benchmarks compile time goes from 200s (in 3.1) up to 1500s (in 3.3).
<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US">We also managed to reproduce the regression with a C++ example using clang. Here are the instructions:<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US">Generate the example C++ file with the Perl script attached to the Bug (5000 is a good size parameter to clearly see the regression):<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US"> perl create.pl example.cpp 5000<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US">Generate LLVM IR code for the C++ file (the regression is in the backend functionality, so we don't want to measure frontend compilation)<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US"> llvm31/clang++ example.cpp -c -emit-llvm -o example.ir-31<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US"> llvm35/clang++ example.cpp -c -emit-llvm -o example.ir-35<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US">Now you can run the actual performance measurements using llc:<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US"> llvm31/llc -cppgen=program -o=5000.asm example.ir-31<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US"> llvm35/llc -cppgen=program -o=5000.asm example.ir-35<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US">or you can also compile example.ir-31 with llvm3.5:<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-US"> llvm35/llc -cppgen=program -o=5000.asm example.ir-31
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Our analysis had shown that the most of time is taken for generation of live intervals for physical registers. In the biggest example, the live interval of one of the physical registers consists of about 500.000 live
ranges. Insertions in the middle of the array of live ranges cause quadratic algorithmic complexity, which is apparently the main reason for the slow-down. I changed the implementation of computeRegUnitInterval() so that it uses a set instead of the array,
and in this way managed to reduce the execution time of the computeRegUnitInterval from 1200s down to about 1s. The fix is a bit ugly, however, because I cannot completely switch to the set, since further analyses are more efficient on the array. For that
reason, I flush the contents of the set into the array at the end of computeRegUnitInterval. I also had to rewrite various operations on the live interval so that they use the set structure if it is available and the array otherwise.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">If there is an interest, I can port the patch to the dev version of llvm, but maybe someone has a better idea of how to deal with the regression.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Regards,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Vaidas<o:p></o:p></span></p>
</div>
</body>
</html>