Matching block params to allocations

[digama0]

Currently, checker.rs has to perform a dataflow analysis to derive the mapping from block params to allocations, but the block params are an input and conceivably the register allocator could provide this information as part of its output. In my compiler, I need this information as part of regular compilation, and while I could do a similar dataflow analysis, I imagine that the register allocator could provide this information more efficiently than if I were to reconstruct it.

The API I am thinking of is something like:

• Output contains a field block_params: Vec<Allocation> and block_param_offsets: Vec<u32>, encoding a list of slices similar to instructions
• The [Allocation] slice for a given block bl is parallel to f.block_params(bl)
• The Allocation for a given block parameter is either None, or a Reg or Stack value according to where it happens to be stored at the moment.

This would enable an alternative non-fixpoint implementation of checker.rs, where the checker state is initialized directly from the block params: each mapping of vreg -> alloc (where alloc is not None) implies an entry alloc -> CheckerValue::Reg(vreg, reftyped(vreg)) in the initial state. There is no distinction between Unknown and Conflicted here, but the constraint is that at the bottom of each basic block, the state at the successor blocks is obtained from this state by setting some allocations to None. Unlike the fixpoint algorithm this does not require that the output of the checker is a least fixpoint, only a fixpoint, but it is a witness of correctness either way.

Thoughts? I imagine that some compilers don't want this information and/or don't want to pay for constructing this output data, so it can be behind a flag (a runtime flag would be useful for applications like the checker, and the cost should be minimal if the flag is off, since it's just two more empty vectors in Output, but it could also be a compile time flag). But for some applications this data is quite relevant for connecting pre-regalloc data to post-regalloc data when generating auxiliary information about the code (or even the code itself, if the ISA requires some kind of capabilities for the used registers, although this seems unlikely).

[Amanieu]

You can get this information by adding a dummy instruction at the start of the block which uses all block parameters with the Any constraint. You can then get the allocations for block parameters by reading the Allocations from the dummy instruction.

[digama0]

I thought of that, but doesn't this also constrain the register allocator? For example, it might want to put some block parameters in spills, but the dummy instruction would force it to load them into registers first. In fact the parameters might even be dead, so the dummy instruction might increase register pressure by making the values live longer than necesary.

EDIT: I didn't know about the Any constraint. That addresses the problem where the parameter is on the stack, but not when it is dead (or does the allocator not have a concept of this?)

[Amanieu]

In my own compiler I have a liveness pass that eliminates dead block parameters when lowering, so I haven't considered this. I don't think regalloc2 will eliminate dead block parameters on its own.

However there is another situation where a block parameter could be without an allocation: if the value is rematerializable then it could have an allocation of None when it is passed as a block parameter since it will be rematerialized later. See #8 for more discussion on future rematerialization support.

[digama0]

(I also have such a pass, but since there are micro optimizations all over the place I would not be too surprised if regalloc found some dead stuff anyway.)

I wasn't expecting it to eliminate dead block parameters per se, only set them to None like you would expect for other variables after their last use in a block. If the current architecture doesn't ever do that, then it's fine I guess, I just didn't want to change the answer by querying it.

[digama0]

This is fixed by #27 .