diff options
Diffstat (limited to 'Notes/MIR-PackedLValue.txt')
-rw-r--r-- | Notes/MIR-PackedLValue.txt | 65 |
1 files changed, 65 insertions, 0 deletions
diff --git a/Notes/MIR-PackedLValue.txt b/Notes/MIR-PackedLValue.txt new file mode 100644 index 00000000..ce889aee --- /dev/null +++ b/Notes/MIR-PackedLValue.txt @@ -0,0 +1,65 @@ +Problem statement: +- MIR LValues are very common, and suffer from excessive indirection when + dereferences and field accesses are present +- Many MIR analysis passes care most about the inner values +- Pointer chasing ruins cache locality + +Solution: Replace the tagged union tree with a flatteded structure + +Quirk: Indexing takes two LValues to produce one BUT one of those is of a +lesser class, so doesn't need to be treated the same. + + + +Structure proposal: +---- +A LValue is made up of: +- A root value (referencing a local, argument, static, or the return value) +- And a list of wrappers (dereference, field, downcast, index) + +Root values are encoded as a packed pointer/value and tag, with the tag stored in the low 2 bits of the pointer +- This allows a 32-bit pointer to a word to be stored, using the alignment bits as tag +- Arguments and locals are encoded with the argument/local index in the "data" bits +- Return value is encoded as argument `-1` (all 1 bits in data) +- Statics are encoded as a pointer to a `::HIR::Path` + - This adds a new pointer access and allocation vs the existing LValue structure + - HIR::Path already has a bunch of pointers in it, may not hurt that much (and may help by keeping the normal size + of the LValue down) + +Wrappers are stored as a vector of words, packed in a similar way to root values +- Dereference is stored just as an entry (could pack multiple derefs into one, but that would make handling more + difficult) +- Field/Downcast is stored with the field/variant index in the "data" bits +- Indexing is stored as a pointer to a LValue + - ALTERNATIVE: Could require that indexing always uses a local, and just store the local index + - This would vastly reduce complexity in handling the Index wrapper, BUT would add a new statement in some cases + - A quick scan of the MMIR output of libstd crates, shows that the vast majority of indexing cases are with a local + directly. + - Doing so would simplify monomorph/clone/serialise (no need to clone the wrapper list, just copy it). + - Would also improve comparison times + + + +Usecase comparisons +------ +(Using 32-bit architecture) + +NOTES: +- Existing `LValue` structure is 3 words long (1 tag, plus 2 pointers for largest variant) + - WRONG. It's actually far larger due to the ::HIR::Path embedded in it (estimate at least 8 pointers, very likely + more). That should be fixed given the number of LValue-s that exist + - Fixed now, had a slight improvement in compile times (and memory usage?) +- New structure is 4 words long (root value, plus len/cap/ptr for vector) + +- Field access via `&self` + - Old: Field(Deref(Argument(0)), 0) + - 12 + 12 + 12 = 36 bytes w/ 2 pointers + - New: LValue( Argument(0), { Deref, Field(0) } ) + - 16 + 8 = 24 bytes w/ 1 pointer + +- Array stored in `&self` (common in librand) + - `(*arg0).2[var16].0` + - Old: Field( Index(Field(Deref(Argument(0)), 2), Local(16)), 0 ) + - 12 * 5 + 12 = 72 bytes 2/ 5 pointers + - New: LValue( Argument(0), { Deref, Field(2), Index(16), Field(0) } ) + - 16 + 16 = 32 bytes w/ 1 pointer |