Re: Register allocation with shadowed locals at same level

[Richard Hundt <richardhundt@...>]

Rob Kendrick wrote:
> Hi,
>
> I find myself writing code that looks a lot like this quite often:
>
> 	local foo, err = make_foo()
> 	if not foo then return nil, err end
>
> 	local bar, err = make_err()
> 	if not bar then return nil, err end
>
> Looking at the output of luac -l, it looks as if this wastes a register
> because Lua doesn't reuse the register allocated to the first local
> definition containing an "err" for the second, even though the first is
> no longer accessible, and never (I think) will become accessible again.
> Two questions:
> 	1) Is there some reason I've missed why it is essential that 
> 	   Lua behaves this way?

I don't think it's essential, but rather a consequence of a design 
choice (a sensible one, I think).

Lua expects some instructions (OP_CALL, OP_RETURN, OP_SETLIST, 
OP_CONCAT, etc.) to have their arguments in consecutive registers so 
that 3 operand instructions can cover all these cases; the operands just 
need to know the base register and the count to say "do something with 
this range of registers".

If the Lua compiler did [insert favourite algorithm] register 
allocation, you'd end up reusing registers lower down the stack, and 
when an instruction were encountered which wanted to operate on a list 
of values, then they'd need to be moved into consecutive registers, some 
of which would then need to be allocated anyway.

So let's say the first `err' in this case were $R2, then the final 
return might conceptually turn into something like:

OP_RETURN ($R3, $R2)

which would mean that you'd either need to encode the particular offsets 
of the registers into the return instruction (perhaps by storing 
signatures as constants and then decoding them as the Parrot VM does, 
and bloat the bytecode and VM footprint by doing so), or move them into 
position, in which case you'd end up allocating $R4 to hold $R2 for the 
return instruction anyway and waste move instructions.

There are other ways of slicing this problem, but I think that the way 
Lua does it is simple and keeps it fast, and nested lexical scopes are 
frequent enough that complex functions can yield code with surprisingly 
small stacks, so you really don't gain much by using aggressive register 
allocation.

> 	2) Am I right in thinking that the value stored in the first err
> 	   will not be garbage collected until the scope containing both
> 	   errs is left?

Here I'm not 100% sure, my GC Fu is limited, but I think that it's not 
just until the scope containing both has left, but more specifically 
that all the values held by the registers at any point in the function 
are considered reachable, so if you're seeing a register not being 
reused in the scope of the containing function, then it would still have 
it's previous value (like the first `err' in this case), and therefore 
wouldn't be eligible for collection.

Consider:

function foo()
   local a = { }
   do
      local b, c = { }, { }
   end
   local d = { } -- the register for `b' is reused, `b' can be collected
   -- at this point `c' isn't collectible although its scope has exited
   ...
end

The distinction here would be that although a scope is introduced, 
there's no guarantee that registers allocated to locals inside are going 
to be overwritten with new values later on after the end of the block, 
thereby making their previous values collectible (all this would require 
would be that there were more locals declared inside the block than 
outside it), so registers can remain reachable after their scope has 
exited, but not after the function to which they're bound has exited 
(barring upvalues, of course).

Anyway, I think that's the deal, but I'm open to correction.

Cheers,
Richard Hundt