<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" style="font-size: 12pt; color: rgb(0, 0, 0); font-family: Calibri,Helvetica,sans-serif,"EmojiFont","Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;" dir="ltr">
<p>Hello,</p>
<p><br>
</p>
<p></p>
<div>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif">In a previous email, Matthias mentioned that register pressure estimates in the machine scheduler are not absolute; they only account for the registers that are used in the block.I assume that he meant that registers
that are live-through (both live-in and live-out) are not accounted for in register pressure calculations. If a register is either live-in or live-out but not both, it must be accounted for, because its live range length may be affected by the scheduling decisions
within the region. <br>
</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif"><br>
</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif">I understand that the live range of a live-through register is not affected by the scheduling decisions within the region, but unfortunately, the scheduler that we are integrating in the machine scheduler does need
to know the absolute register pressure. Our scheduler is a combinatorial scheduler with an explicit cost function. The explicit cost function is what we call the Peak Excess Register Pressure (PERP), which is basically the number of registers above the physical
limit at the highest pressure point in the schedule. If the peak pressure does not exceed the physical limit for any register type, the PERP is set to zero.
</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif"> </span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif">Our combinatorial scheduler first invokes the existing machine scheduler and computes the RP of the schedule that it produces. If that RP is within the physical limits (PERP=0), it is considered optimal and no further
action is taken. If the computed PERP is greater than zero, our scheduler performs an exhaustive search for an optimal schedule (a schedule with minimum PERP) using a branch-and-bound (B&B) approach. Without accounting for live-through registers, two bad things
can happen:</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif"> </span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif">1. A schedule whose actual peak pressure exceeds the physical limit may be considered optimal and thus will not get passed to the B&B phase. For example, if the physical limit is 10 and the peak pressure without
counting live-through registers is 7, our scheduler will think that this is optimal and will not attempt to find a better schedule. If the number of live-through registers happens to be 4 or more, this will be a bad decision.</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif"> </span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif">2. Even if a schedule is passed to the B&B phase, the B&B search may terminate with a sub-optimal schedule thinking that it is optimal. For example, if the physical limit is 10, our B&B scheduler may find a schedule
with a peak pressure of 8 and terminate thinking it is optimal, while it may not be optimal if the number of live-through registers happens to be 3 or more. Without knowing about live-through registers, our B&B scheduler
<span style="mso-spacerun:yes"></span>will not continue to search for a better schedule in this case.</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif"> </span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif">You may think that setting all the physical limits for all register types to zero may resolve this problem. This is true, but it will cause our computationally expensive scheduler to do a lot of unnecessary work.
It will be wasting a lot of time processing many small-and-trivial scheduling regions.</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif"> </span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif">So, is there an easy way to account for all registers and compute the absolute register pressure?</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif"><br>
</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif">Thanks</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif"><br>
</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif">Ghassan Shobaki<br>
Assistant Professor of Computer Science <br>
</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif">University of California, Sacramento
</span></p>
<p class="MsoNormal" style="margin-bottom:0in;margin-bottom:.0001pt;line-height:
normal">
<span style="font-family:"Arial",sans-serif"><span style="mso-spacerun:yes"> </span><span style="mso-spacerun:yes"> </span><span style="mso-spacerun:yes"> </span><span style="mso-spacerun:yes"> </span><span style="mso-spacerun:yes"> </span><span style="mso-spacerun:yes"> </span><span style="mso-spacerun:yes"> </span><span style="mso-spacerun:yes"> </span></span></p>
</div>
<br>
<p></p>
</div>
</body>
</html>