I'm interested in this because these linearized tree representations lend themselves well to processing on GPU. We use them in Vello for representing clip and blend groups, with quite deep nesting level allowed. By contrast, the traditional pointer chasing approach to ASTs limits parallelism and has poor utilization of memory bandwidth.
"Linear, pointer-free IR: The typed IR is SSA-based and highly orthogonal. An instruction takes up only 64 bits. It has up to two operands which are 16 bit references. It's implemented with a bidirectionally growable array. No trees, no pointers, no cry. Heavily optimized for minimal D-cache impact, too." [0]
If you are replacing pointer chasing with arbitrary indexes into arrays, you are likely going to make it orders of magnitude slower for large arrays. (It's barely worth it even if the array fits in L1)
It's counterintuitive because pointers have been optimized on hardware for about 50 years, and array indices are just pointers that your hardware doesn't know about.
The main things that go wrong are hardware prefetching and compiler optimizations taking advantage of alias analysis.
Considering all of that, I'm really not convinced that plain pointers will beat indices. I also don't see what alias analysis has to do with it in this case, sounds like a compiler could easily do alias analysis on A being accessed only as a T by virtue of A having the type Array<T,N>.
That's what compiler backend and hardware optimizes for.
Blindly replacing pointers with random indexes into large arrays doesn't pan out.
> Skip-list chains: The IR is threaded with segregated, per-opcode skip-list chains. The links are stored in a multi-purpose 16 bit field in the instruction. This facilitates low-overhead lookup for CSE, DSE and alias analysis. Back-linking enables short-cut searches (average overhead is less than 1 lookup). Incremental build-up is trivial. No hashes, no sets, no complex updates.
Seems like there is more going on than just replacing pointers with arrays 1:1.
1. An array index is just as suitable as a pointer for dereferencing. 2. What matters is how many dereferences are needed and their locality. 3. Data structure density is important to get high cache utilization.
References show a lot of locality: 40% of all IR operands reference the previous node. 70% reference the previous 10 nodes. A linear IR is the best cache-optimized data structure for this.
That said, dereferencing of an operand happens less often than one might think. Most of the time, one really needs the operand index itself, e.g. for hashes or comparisons. Again, indexes have many advantages over pointers here.
What paid off the most was to use a fixed size IR instruction format (only 64 bit!) with 2 operands and 16 bit indexes. The restriction to 2 operands is actually beneficial, since it helps with commoning and makes you think about IR design. The 16 bit index range is not a limitation in practice (split IR chunks, if you need to). The high orthogonality of the IR avoids many iterations and unpredictable branches in the compiler itself.
The 16 bit indexes also enable the use of tagged references in the compiler code (not in the IR). The tag caches node properties: type, flags, constness. This avoids even more dereferences. LuaJIT uses this in the front pipeline for fast type checks and on-the-fly folding.