JM currently syncs and discards all information before jumping or at points with incoming jumps. To carry values in registers better, we should precompute a register allocation state at basic block boundaries, along with which constants/copies must hold there, and sync against that. This bug is for integrating a constant/copy propagation analysis into the first pass of jsanalyze, and to add a second backwards pass which computes a crude regalloc (consisting of things which are live; will use the one in bug 557407). Another bug will get JM to actually use this information. This approach is nice because JM's behavior within basic blocks will not change much; code around jumps/joins needs to use the new info, and when pushing values or writing to locals JM can use the regalloc as hints to avoid register swapping at the end of the block. This bug and followups will go into the Jaegermonkey branch, at least initially.

Is this register allocation going to require type inference, or can it be used independently?

Register allocation doesn't require type inference, but they are not quite independent. Two areas of interaction: - Allocating registers for types tags. For simplicity, this bug will only allocate registers for payloads. Since JM doesn't use the regalloc within basic blocks except as a hint, this shouldn't change things too much. One possible issue is how many registers to carry across branches/joins --- carrying type tags in registers within basic blocks increases register pressure and would cause more loads to happen when syncing against the branch/join regalloc (kind of defeating the purpose). - Allocating registers for floating point values. I don't really know floating point registers at all, but if there is a set of registers that can be used as GPRs for 64-bit floats then FP registers could be allocated for variables and stack slots whose type has been inferred as int|float.

(In reply to comment #2) > Register allocation doesn't require type inference, but they are not quite > independent. Two areas of interaction: > > - Allocating registers for types tags. For simplicity, this bug will only > allocate registers for payloads. Since JM doesn't use the regalloc within > basic blocks except as a hint, this shouldn't change things too much. One > possible issue is how many registers to carry across branches/joins --- > carrying type tags in registers within basic blocks increases register > pressure and would cause more loads to happen when syncing against the > branch/join regalloc (kind of defeating the purpose). Payload only seems like a good place to start; we know Opera does that in general. Maybe it's because type tags are used mostly for branches, and it doesn't matter so much as long as the branches are predictable? It would be nice to learn more about this issue at some point. > - Allocating registers for floating point values. I don't really know > floating point registers at all, but if there is a set of registers that can > be used as GPRs for 64-bit floats then FP registers could be allocated for > variables and stack slots whose type has been inferred as int|float. Back when we designed the current register allocator, we concluded that it would be fairly hard to hold values in FP regs across ops without type inference. I think it might be doable without type inference, by tracking "type reg, data reg if not fp, data reg if fp" for ops, but I'm sure that starts getting ugly with PICs and control flow and such, so it seems like a winner only if doing some kind of type specialization (whether statically or dynamically informed). dvander also says all FP regs are volatile, so using them in the presence of slow calls gets hard in similar ways. And again, I think only type specialization really gets around that.

This modifies the first pass of jsanalyze to do constant and copy propagation around across branches and around loops. Adds 2ms of analysis time to SS, 3ms to V8. Across V8 and SS about 400 copies/constants are found to hold at join points. I don't know yet how much these buy; should investigate but also decouple from regalloc so that neither analysis depends on the other. The regalloc in 557407 assigns registers to stack slots so needs to know which are copies/constants; alternatively, the regalloc could pay attention only to locals, which should work fine as the FrameState will be handling registers inside basic blocks.

This adds a backwards liveness pass picking out good variables to keep in registers at branch and join points. Won't really be able to tell how good this information is until it's integrated with JM, but questions of correctness don't come into play (these are just hints for the compiler) and there is plenty of room for more heuristics or more complicated analysis if it ends up being needed. Analysis time is about .5ms on the V8 benchmarks, less on SS.

JM was removed.