<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Oct 9, 2014, at 12:34 PM, Andrew Trick <<a href="mailto:atrick@apple.com">atrick@apple.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><blockquote type="cite" class=""><div class=""><br class="Apple-interchange-newline">On Oct 9, 2014, at 9:17 AM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" class="">hfinkel@anl.gov</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><span class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">----- Original Message -----</span><br class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><blockquote type="cite" class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">From: "Vaidas Gasiunas" <<a href="mailto:vaidas.gasiunas@sap.com" class="">vaidas.gasiunas@sap.com</a>><br class="">To: "LLVM Dev (<a href="mailto:llvmdev@cs.uiuc.edu" class="">llvmdev@cs.uiuc.edu</a>)" <<a href="mailto:llvmdev@cs.uiuc.edu" class="">llvmdev@cs.uiuc.edu</a>><br class="">Sent: Thursday, October 9, 2014 4:37:39 AM<br class="">Subject: [LLVMdev] Performance regression in the LiveIntevals phase<br class=""><br class="">Some time ago we reported a compile-time performance regression in<br class="">the LiveIntervals analysis pass (see<br class=""><a href="http://llvm.org/bugs/show_bug.cgi?id=18580" class="">http://llvm.org/bugs/show_bug.cgi?id=18580</a><span class="Apple-converted-space"> </span>). We detected it at<br class="">first after migrating from LLVM 3.1 to 3.3, but the problem persists<br class="">also in 3.5. This regression is especially critical when compiling<br class="">long functions. In one of our benchmarks compile time goes from 200s<br class="">(in 3.1) up to 1500s (in 3.3).<br class=""><br class=""><br class=""><br class="">We also managed to reproduce the regression with a C++ example using<br class="">clang. Here are the instructions:<br class=""><br class=""><br class=""><br class="">Generate the example C++ file with the Perl script attached to the<br class="">Bug (5000 is a good size parameter to clearly see the regression):<br class=""><br class="">perl create.pl example.cpp 5000<br class=""><br class="">Generate LLVM IR code for the C++ file (the regression is in the<br class="">backend functionality, so we don't want to measure frontend<br class="">compilation)<br class=""><br class="">llvm31/clang++ example.cpp -c -emit-llvm -o example.ir-31<br class=""><br class="">llvm35/clang++ example.cpp -c -emit-llvm -o example.ir-35<br class=""><br class=""><br class=""><br class="">Now you can run the actual performance measurements using llc:<br class=""><br class="">llvm31/llc -cppgen=program -o=5000.asm example.ir-31<br class=""><br class="">llvm35/llc -cppgen=program -o=5000.asm example.ir-35<br class=""><br class="">or you can also compile example.ir-31 with llvm3.5:<br class=""><br class="">llvm35/llc -cppgen=program -o=5000.asm example.ir-31<br class=""><br class=""><br class=""><br class="">Our analysis had shown that the most of time is taken for generation<br class="">of live intervals for physical registers. In the biggest example,<br class="">the live interval of one of the physical registers consists of about<br class="">500.000 live ranges. Insertions in the middle of the array of live<br class="">ranges cause quadratic algorithmic complexity, which is apparently<br class="">the main reason for the slow-down. I changed the implementation of<br class="">computeRegUnitInterval() so that it uses a set instead of the array,<br class="">and in this way managed to reduce the execution time of the<br class="">computeRegUnitInterval from 1200s down to about 1s. The fix is a bit<br class="">ugly, however, because I cannot completely switch to the set, since<br class="">further analyses are more efficient on the array. For that reason, I<br class="">flush the contents of the set into the array at the end of<br class="">computeRegUnitInterval. I also had to rewrite various operations on<br class="">the live interval so that they use the set structure if it is<br class="">available and the array otherwise.<br class=""><br class="">If there is an interest, I can port the patch to the dev version of<br class="">llvm, but maybe someone has a better idea of how to deal with the<br class="">regression.<br class=""></blockquote><br class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">I think this would be interesting, please do. There are a few places in LLVM where we currently keep dual data structures, and needing another one is not necessarily bad (we have SetVector, for example).</span><br class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"></div></blockquote></div><br class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">Yes, it would be good to get a fix for this behavior in LLVM trunk even if it isn’t pretty. I’ve also seen extendToUses showing up on profiles. Your description of the fix sounds reasonable.</div></blockquote><div><br></div><div>+1. Please send the patch for review.</div><div><br></div><div>Thanks,</div><div>-Quentin</div><br><blockquote type="cite"><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br class=""></div><div class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">-Andy</div><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">_______________________________________________</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">LLVM Developers mailing list</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><a href="mailto:LLVMdev@cs.uiuc.edu" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">LLVMdev@cs.uiuc.edu</a><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;"><span class="Apple-converted-space"> </span> </span><a href="http://llvm.cs.uiuc.edu/" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">http://llvm.cs.uiuc.edu</a><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></blockquote></div><br></body></html>