An Original Scope Record is referenced, in the [[Definition]] of a Generated Range Record, by an index into the pre-order sequence of the scope tree. The encoded order is the pre-order by construction. The use of unsigned offsets enforces that nested scopes are emitted in order and before the end of the parent. This is a nice property...
...but the pre-order index presents a problem for the generator.
- When encoding a range, the scope index is needed.
- The scope index is determined by which other scopes are referenced from some other range.
The implication is that the generator needs a multi-pass algorithm to resolve this dependency cycle. For example, the ranges might have an initial pass to mark the 'live' scopes, the scopes are then encoded and assigned indexes, and then the ranges have a second pass to be encoded using the finalized scope indexes. The problem, in this example, is that a compiler needs to keep all the ranges around in some form, adding to memory pressure. An optimizing compiler that generates wasm bytecodes for functions one at a time does not otherwise need to retain the ranges in decoded form for each function, or the scopes for generated functions that were never inlined.
it would be helpful to the generator if scopes could be emitted in a less constrained order, more like how names are encoded, where indexes can be assigned 'online'.
One way to do this would be to encode the parent index rather than the children scopes (the parent scope is encoded first). The children can be reconstructed after decoding. (It is not clear to me that we need the children at all, since an original source position can be mapped to an innermost scope by sorting scopes to pre-order, and sorting can be deferred until the mapping is requested.)
The delta encoding might be less efficient since the scopes may be encoded in an order that jumps around.
An Original Scope Record is referenced, in the [[Definition]] of a Generated Range Record, by an index into the pre-order sequence of the scope tree. The encoded order is the pre-order by construction. The use of unsigned offsets enforces that nested scopes are emitted in order and before the end of the parent. This is a nice property...
...but the pre-order index presents a problem for the generator.
The implication is that the generator needs a multi-pass algorithm to resolve this dependency cycle. For example, the ranges might have an initial pass to mark the 'live' scopes, the scopes are then encoded and assigned indexes, and then the ranges have a second pass to be encoded using the finalized scope indexes. The problem, in this example, is that a compiler needs to keep all the ranges around in some form, adding to memory pressure. An optimizing compiler that generates wasm bytecodes for functions one at a time does not otherwise need to retain the ranges in decoded form for each function, or the scopes for generated functions that were never inlined.
it would be helpful to the generator if scopes could be emitted in a less constrained order, more like how names are encoded, where indexes can be assigned 'online'.
One way to do this would be to encode the parent index rather than the children scopes (the parent scope is encoded first). The children can be reconstructed after decoding. (It is not clear to me that we need the children at all, since an original source position can be mapped to an innermost scope by sorting scopes to pre-order, and sorting can be deferred until the mapping is requested.)
The delta encoding might be less efficient since the scopes may be encoded in an order that jumps around.