Hacker News Reader

Comment by rayiner | Hacker News Reader

The issue addressed in the article with pointer tagging applies whether you use array indexing or pointers. Both are converted to pointer operations under the hood, which on X86 are some form of ADDR = BASE + SCALE*INDEX + OFFSET. Such an operation is still considered a pointer dereference (of BASE) from the view of the hardware, and will trap if tags are stored in the unused upper bits of the pointer.

Depending on the size of the array elements, you won't even be able to use the built-in index addressing mode, because the index can only be up to 8 bytes. For that reason, LLVM doesn't even have array indexing. Loads/stores can only be done against pointers, and pointers to items in arrays must be expressly computed using a get-element-pointer instruction: https://llvm.org/docs/GetElementPtr.html.

View on HN

Thanks for the insightful reply. I didn't realize array indexing gets converted to pointers in the CPU. I expected the array indexing assembly instructions to be plumbed all the way down without converting to pointers until the very end.

LLVM not supporting array indexing means all those instructions go unused, on both x86 and arm? How about gcc or other compilers?

They don’t go unused. Typically the separate address calculation and load will get merged back together during instruction selection is there is an applicable instruction. (Although that may not happen either—the compiler might transform the code to get rid of the array indexing. Keeping around the base pointer takes an additional register.)

But on x86 and ARM these instructions are limited. On x86, a load instruction can have a prefix that treats one operand as the array base pointer, and another operand as the index. But the size of the array element is limited to 8 bytes so if your array elements are say 16 byte structs, you can’t use those instructions. As to ARM, I think it doesn’t have an array indexing instruction at all, just base + offset.

This is less about "array indexing" and more about arrays being located at a specific memory address. At some point you're going to have a buffer at address 0x1000 and want to access the 42nd element, and you can't just use a tagged address (e.g. 0x1000000001000) and 42 together without stripping the tag somewhere.

The compiler can convert small known-size known-offset array accesses into registers or direct static stores and loads, but array indexing is usually on large chunks through a dynamic index via a ref or pointer, which will be via pointer math.

Reply on news.ycombinator.com