On 10/01/2014, at 6:17 , Adam Wick <[email protected]> wrote:
> On Jan 8, 2014, at 2:42 AM, Simon Marlow <[email protected]> wrote:
>> Neither of the register allocators reuse spill slots for variables that have
>> disjoint live ranges, so the fact that we ran out of spill slots is not
>> necessarily indicative of terrible code (but I agree that it's a strong
>> hint).
Right, I'm starting to remember more now -- it was a while ago.
There are some notes here under the section "SHA from darcs", which I assume is
the same code.
https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Backends/NCG/RegisterAllocator
The notes say the Cmm code had 30 or so live variables at a particular point,
but live ranges of 1700 instructions. I remember I had to change the heuristic
that chooses which register to spill, to select the one with the longest live
range -- instead of using the standard one from Chatin's algorithm. With the
standard heuristic the allocator was taking too long to converge.
> That’s the problem with SHA, then. The implementation (and the spec, really)
> is essentially a long combination of the form:
>
> let x_n5 = small_computation x_n1 x_n2 x_n3 x_n4
> x_n6 = small_computation x_n2 x_n3 x_n4 x_n5
> …
>
> Which has ~70 entries. The actual number of live variables alive at any time
> should be relatively small, but if slots aren’t getting reused there’s going
> to be some significant blowup. (To be honest, I had figured — and thought I
> had validated — that doing it this way would give the compiler the best
> chance at generating optimal code, but it appears I merely set myself up to
> hit this limitation several years later.)
If you really end up with 70 copies of small_computation in the object code
then that's not very friendly to the L1 instruction cache -- though perhaps it
doesn't matter if the processor will be stalled reading the input data most of
the time anyway.
The -O2 heuristics might inline small_computation by default, assuming it's
non-recursive.
Ben.
_______________________________________________
ghc-devs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/ghc-devs
