search

ykjit / yk

yk packages
https://ykjit.github.io/yk/
Other
29 stars 7 forks source link

Better spill heuristic #1313

Closed ltratt closed 2 months ago

ltratt commented 2 months ago

At some point every register allocator runs out of registers, and then we have to decide which unfortunate register to spill and reuse. Previously we semi-randomly picked a register (which, mostly, would end up being R15) and spilt it.

This PR uses a common heuristic in linear scan register allocators: spill the register whose value is last used furthest away. The idea here is that we already know when a value is last used, and the later a value is used, the more likely it is that it's not used soon. In other words, this is a rough proxy for "find the value which is least likely to be used soon and spill that".

Pleasingly, crude and simple though this is, it leads to noticeably less spills overall: big_loop.lua speeds up by a consistent 5.5%.

jacob-hughes commented 2 months ago

This LGTM, and the reasoning sounds sensible. I'm happy to merge, unless you want someone more familiar with this area of yk to take a look too?

ltratt commented 2 months ago

@jacob-hughes You're the sole reviewer, so as long as you're comfortable, it's yours to merge!

ltratt commented 2 months ago

OK, that's a totally unrelated change to this PR. Fixed in https://github.com/ykjit/yk/pull/1314.