Remove null value from Opcode

[stoklund]

After the Rust language designers carefully removed nulls from the language, I went and added my own. It turns out that Option<T> is often larger than T, and tables with 32-bit or smaller entries can double in size when using Option<T>.

C-like Opcodeenum

The Opcode enum in the generated opcodes.rs file contains an explicit null value:

pub enum Opcode {
    /// An invalid opcode.
    NotAnOpcode,
    /// `jump EBB, args`. (Jump)
    Jump,
    /// `brz c, EBB, args`. (Branch)
    /// Type inferred from `c`.
    Brz,
    ...
}

With the current opcodes, Opcode is a single byte, but Option<Opcode> is two bytes. We use the explicit null to indicate the empty slots in a precomputed hash table:

const OPCODE_HASH_TABLE: [Opcode; 128] = [
    Opcode::Imul,
    Opcode::Fsub,
    Opcode::IconcatLohi,
    Opcode::Sshr,
    Opcode::Fmaxnum,
    Opcode::NotAnOpcode,
    Opcode::Nearest,
    ...
}

This table would double in size if we used Option<Opcode>. Since this table is only used by the parser when mapping strings to opcodes, perhaps we should just bite the bullet and use an Option<Opcode> here. Hopefully, the Rust compiler will soon learn how to represent this sum type efficiently. It's one of the easier nested enum optimizations.

Encoding tables also use NotAnOpcode currently. These tables are more critical to keep small, but there may be an alternative representation of the empty slots.

[eddyb]

cc rust-lang/rfcs#1230 (comment) - I now know what steps should be taken and I'm willing to mentor someone, but I can't take it onto myself for a while.

There was one hack added, in rust-lang/rust#37224, which means you can mark your first legitimate entry with = 1 and, at least in nightly, Option<Opcode> shouldn't take more than a byte or whatever.

[angusholder]

I'd like to have a go at this if that's ok? I think I understand what needs doing

[stoklund]

@angusholder That would be great!

[stoklund]

This was fixed by @angusholder!