<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="font-family: Times; "><pre></pre><blockquote type="cite"><pre>Much experience has taught me not to trust register allocation papers.
They never actually talk about performance. If I were reviewer, I
might accept a paper based on novelty of the algorithm (far too
many papers are rejected simply because they can't show a 20% speedup)
but I wouldn't give points for reducing the number of spills and
reloads.</pre></blockquote><blockquote type="cite"><pre> Those counts simply don't mean anything in the real world.
</pre></blockquote><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">Sorry to barge in on this thread, but that last sentence there caught me</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">by surprise...</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;"><br></span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">This certainly is the case with desktop CPUs, where the hardware designers</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">have gone to a lot of bother adding hardware to perform dynamic</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">rescheduling and register renaming, which effectively replace these stack</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">accesses with registers or access to fast cache.</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;"><br></span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">But, with upcoming architectures - particularly ones with a very large</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">number of cores (e.g. something along the lines of Larrabee, or Ambric,</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">and a plethora of others) - such hardware is too costly. As a result,</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">needless stack activity consumes available memory bandwidth, which</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">absolutely hammers instruction-level parallelism.</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;"><br></span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">I certainly agree that a fast default register allocator is the best</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">strategy for LLVM, considering its main use. But it would be very nice to</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">have an optional allocator that does minimise spilling, at the cost of</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">run time.</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;"><br></span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">I thought it best to raise awareness of where common assumptions (which</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">certainly came around for good reason) can break down in real-world</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">situations, so that progress can be made.</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;"><br></span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">Regards,</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;"><br></span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;">- Mark</span></font></div><div><font class="Apple-style-span" face="monospace"><span class="Apple-style-span" style="white-space: pre;"><br></span></font></div></span></body></html>