<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
<div id="divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif;" dir="ltr">
<p><br>
</p>
<p>We have run an experiment in which we set all physical register limits to zero. The purpose of this experiment was estimating the potential impact of getting complete liveness info. The results of this experiment were better than the results that we got
using the real physical limits (the total number of spills in CPU2006 was reduced), but the difference was not substantial. We took this as an indicator that getting complete live-through information is unlikely to buy us much. So, we focused on investigating
other problems that could have a higher impact on the results.<br>
</p>
<p><br>
</p>
<p>Overall, we are not currently getting the expected results on Intel x86 (the reduction in spilling is not as significant as expected), and we attribute this to two major problems:</p>
<p><br>
</p>
<ol style="margin-bottom: 0px; margin-top: 0px;">
<li>There are some cases in which our scheduler reduces the register pressure but the number of spills generated by the register allocator increases. We understand that the correlation between register pressure and the amount of spilling is not perfect, because
it depends on the register allocation algorithm, which may often make bad decisions. However, across the statistically significant data set that we are using (all 900K+ regions in CPU2006), the correlation should be stronger. The weakness of the correlation
between register pressure and spilling indicates that there is something wrong with the register info (Def/Use and liveness) that we are using to compute register pressure. Will you be able to take a look at that part of the code that collects register info
and passes it to our scheduler and tell us if you spot any problems in it? </li><li>The register pressure reductions that we are getting in the machine scheduler are not as significant as the register pressure reductions that we were getting in the selection DAG scheduler. We suspect that the cause of this is that the machine-level DAGs
are more heavily constrained than the selection DAGs. So, if you are getting more spills when you enable the machine scheduler, that may be because the machine-level DAGs are more constrained not because the machine-level scheduling algorithm is weaker. In
order to test this hypothesis, we plan on enabling our combinatorial scheduler at the selection DAG level in the version that are currently using and then doing a direct comparison between selection DAG scheduling and machine scheduling in the same version
of the code. <br>
</li></ol>
<p><br>
</p>
<p>As for live-through information, we found that the machine scheduler does call initLiveThru() and here is a pointer to the code:</p>
<p><br>
</p>
<p><font style="font-family: Calibri,Helvetica,sans-serif,serif,"EmojiFont";" size="3" face="Calibri,Helvetica,sans-serif" color="black"><span style="font-size:12pt;" id="divtagdefaultwrapper"></p>
<div style="margin-top:0;margin-bottom:0;"><a href="https://gitlab.com/CSUS_LLVM/LLVM_DRAGONEGG/blob/master/Generic/llvmTip/llvm-master/lib/CodeGen/MachineScheduler.cpp#L921" target="_blank" rel="noopener noreferrer" id="LPlnk344791" previewremoved="true"><span id="LPlnk344791">https://gitlab.com/CSUS_LLVM/LLVM_DRAGONEGG/blob/master/Generic/llvmTip/llvm-master/lib/CodeGen/MachineScheduler.cpp#L921</span></a></div>
<div style="margin-top:0;margin-bottom:0;"><br>
</div>
</span></font>
<p></p>
<font style="font-family: Calibri,Helvetica,sans-serif,serif,"EmojiFont";" size="3" face="Calibri,Helvetica,sans-serif" color="black"><span style="font-size:12pt;" id="divtagdefaultwrapper"></span></font><font style="font-family: Calibri,Helvetica,sans-serif,serif,"EmojiFont";" size="3" face="Calibri,Helvetica,sans-serif" color="black"><span style="font-size:12pt;" id="divtagdefaultwrapper">
<div style="margin-top:0;margin-bottom:0;"><font face="Calibri,Helvetica,sans-serif">And here is a pointer to
</font>the function initLiveThru()</div>
</span></font><font style="font-family: Calibri,Helvetica,sans-serif,serif,"EmojiFont";" size="3" face="Calibri,Helvetica,sans-serif" color="black"><span style="font-size:12pt;" id="divtagdefaultwrapper"></span></font><font style="font-family: Calibri,Helvetica,sans-serif,serif,"EmojiFont";" size="3" face="Calibri,Helvetica,sans-serif" color="black"><span style="font-size:12pt;" id="divtagdefaultwrapper">
<div style="margin-top:0;margin-bottom:0;"><br>
</div>
<div style="margin-top:0;margin-bottom:0;"><a href="https://gitlab.com/CSUS_LLVM/LLVM_DRAGONEGG/blob/master/Generic/llvmTip/llvm-master/lib/CodeGen/RegisterPressure.cpp#L318" target="_blank" rel="noopener noreferrer" id="LPlnk459354" previewremoved="true"><span id="LPlnk459354">https://gitlab.com/CSUS_LLVM/LLVM_DRAGONEGG/blob/master/Generic/llvmTip/llvm-master/lib/CodeGen/RegisterPressure.cpp#L318</span></a></div>
</span></font>
<p><br>
</p>
<p><br>
</p>
<p>Thanks</p>
<p><br>
</p>
<p><br>
</p>
<p><font size="3" face="Calibri,Helvetica,sans-serif,EmojiFont,Apple Color Emoji,Segoe UI Emoji,NotoColorEmoji,Segoe UI Symbol,Android Emoji,EmojiSymbols" color="black"><span style="font-size:12pt;" id="divtagdefaultwrapper"></p>
<div>
<div style="margin-top:0;margin-bottom:0;"><font style="font-family: Arial,sans-serif,serif,"EmojiFont";" face="Arial,sans-serif">Ghassan Shobaki</font><font style="font-family: Arial,sans-serif,serif,"EmojiFont";" face="Arial,sans-serif"><br>
Assistant Professor of Computer Science </font><font style="font-family: Arial,sans-serif,serif,"EmojiFont";" face="Arial,sans-serif"><br>
</font></div>
<div style="margin-top:0;margin-bottom:0;"><font style="font-family: Arial,sans-serif,serif,"EmojiFont";" face="Arial,sans-serif">California State University, Sacramento
</font></div>
</div>
</span></font><span class="PersonaPaneLauncher">
<div class="_pe_d _pe_62" tabindex="-1"></div>
</span>
<p></p>
</div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> Jonas Paulsson <paulsson@linux.vnet.ibm.com><br>
<b>Sent:</b> Monday, September 11, 2017 3:15:29 AM<br>
<b>To:</b> Andrew Trick; Matthias Braun<br>
<b>Cc:</b> Shobaki, Ghassan; llvm-dev@lists.llvm.org; Kerbow, Austin Michael; ghassanshobaki@gmail.com<br>
<b>Subject:</b> Re: Register pressure calculation in the machine scheduler and live-through registers</font>
<div> </div>
</div>
<div>
<p><br>
</p>
<br>
<div class="moz-cite-prefix">On 2017-08-30 23:14, Andrew Trick wrote:<br>
</div>
<blockquote type="cite" cite="mid:78C3A9AD-8765-4AC7-90FB-2B8097F4B384@apple.com">
<br class="">
<div>
<blockquote type="cite" class="">
<div class="">On Aug 30, 2017, at 1:43 PM, Matthias Braun <<a href="mailto:matze@braunis.de" class="" moz-do-not-send="true">matze@braunis.de</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px;" class="">
That means you cannot use the code from RegisterPressure.{cpp|h} to compute this. The other liveness analysis we have in llvm codegen is LiveIntervals (LiveItnervalAnalysis) which gives you a list of liveness segments of a given vreg (the same representation
is used in most linear scan allocators even though LLVM is not using a linear scan approach any more). This representation is not optimized for register pressure queries though: If you want to know how many variables are alive at a certain point in the program
you have to check all virtual registers to see whether that point is contained in the liverange of that variable.</div>
<div style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px;" class="">
To make this efficient you probably need some form of precomputation over the whole function.</div>
</div>
</blockquote>
</div>
<br class="">
<div class="">The code in RegisterPressure.cpp is meant to work with LiveIntervals. Those queries only see within a block but are meant to be “seeded” with live-through information. That could be done be directly calling `addLiveRegs`. Alternately you can record
live-through pressure separately via `initLiveThru`. It’s just that the MachineScheduler does not bother initializing the live-through information.</div>
<div class=""><br class="">
</div>
<div class="">As Matthias said, actually determining live-through information requires a separate global liveness analysis, because LiveIntervals doesn’t tell you “what’s live at this point”.</div>
<div class=""><br class="">
</div>
<div class="">-Andy</div>
</blockquote>
Ghassan, have you managed to try this, yet? This seems interesting to me on SystemZ, as I am still seeing increased spilling when activating mischeduler for SystemZ and switching to isel source-order scheduling.
<br>
<br>
/Jonas<br>
</div>
</body>
</html>