LLVM ComputeValueVTs recursively expands arrays and structs into one
value type per scalar leaf. SelectionDAG call lowering allocates data
structures proportional to this count, which makes very large values
exhaust memory or crash LLVM.
Count scalar leaves and use pointers for internal parameters and results
when the count exceeds 1024. A result pointer is the first parameter,
and aggregate parameters point to read-only memory. Exported function
types are unchanged.
Keep these SSA values in memory and copy them with memcpy when needed.
Handle calls, interfaces, maps, channels, selects, defers, goroutines,
phis, and multiple results. Update the expected compiler IR and re-enable
the native compress/flate tests.
Map, channel, index, and goroutine lowering each create allocas, store
SSA values into them, load results, and emit lifetime intrinsics.
Add helpers for these operations and use runtimeValueResult for runtime
calls that write a value and an optional comma-ok result. The generated
LLVM IR is unchanged.
Change hashmap set operations and channel send/close from
createRuntimeCall to createRuntimeInvoke. This places a setjmp
checkpoint before each call, allowing runtimePanicAt to safely
longjmp when these operations panic.
* compiler, runtime, reflect: generate type-specific hash/equal for composite map keys
For map keys that are not trivially binary-comparable, the compiler now
generates type-specific hash and equal functions as LLVM IR instead of
going through the interface+reflection path. This covers comparable
types: strings, floats, complex numbers, interfaces, channels, and
composites containing any mix of these.
Previously, maps with composite keys containing strings or floats
converted the key to interface{}, hashed via reflection, and compared
through interface equality. Now the compiler walks struct fields and
array elements directly, dispatching to the right runtime helper for
each field type and storing keys at their actual type.
Struct keys are always handled field-by-field so padding bytes do not
affect equality or hashing. Blank fields are ignored, matching Go
equality. Generated hash/equal function names use canonical underlying
type structure so structurally identical key types can share generated
functions. Padding zeroing before map operations is no longer needed
because structs no longer use the binary key path.
Also fix reflect map iteration for interface-keyed maps: MapIter.Key
returns an interface Value for map[interface{}] keys instead of
unpacking to the concrete key kind.
* compiler: generate loops for array map key hash/equal
Previously, array key hash and equal functions were unrolled at compile
time, generating one block of IR per element. For large arrays like
[1000]int inside a struct with non-binary fields, this caused code
explosion.
Now, binary-element arrays dispatch directly to hash32/memequal for the
whole array. Non-binary-element arrays generate an LLVM IR loop. The
equal loop short-circuits on the first mismatch.
Small arrays are still unrolled instead of looping, keeping the simple
cases compact.
* reflect: fix at-runtime map issues from review, and more found locally
Maps created through reflect.MakeMap need hash/equal behavior that
matches compiler-created maps. Add hashmapMakeReflect for composite key
types, using runtime closures that reconstruct interface{} values from
raw key bytes and delegate to the interface hash and equality paths.
Interface-keyed maps are already stored as interface values, so use the
existing interface hash/equal helpers directly for those. This keeps
reflect insert, lookup, delete, and compiled lookup paths consistent.
Also fix addressable small values used as interface map keys or
interface map values. loadSmallValue puts small indirect values back in
the pointer-sized interface data field the same way valueInterfaceUnsafe
does.
* compiler, interp, reflect: fix pointer map literals; remove interface fallback
Package-level map literals with pointer keys (both *T and
unsafe.Pointer) crash the compiler: the interp pass panics when trying
to hash pointer data as raw bytes, because pointer values in the interp
memory model are symbolic identities that do not fit in a byte.
Fix this by setting a recoverable error flag instead of panicking. The
interp detects the error after each instruction and defers the map
insert to runtime init code, where real addresses are available for
hashing. This matches how the interp already handles other operations
it cannot evaluate at compile time.
With this fix, unsafe.Pointer can also be classified as a binary map
key, which was the last type requiring the interface-based fallback.
Since all comparable types now use either the binary or the
compiler-generated hash/equal path, remove the interface fallback from
the compiler and reflect packages.
* compiler, transform: always pass hash/equal function pointers to hashmapMakeGeneric
The compiler now always resolves the hash and equal functions at compile
time and passes them directly to hashmapMakeGeneric, instead of passing
an algorithm enum to hashmapMake and resolving at runtime. For string
keys, the runtime hashmapStringPtrHash/hashmapStringEqual functions are
referenced directly. For binary keys, hash32/memequal are referenced.
The old hashmapMake with alg enum is retained for reflect, which still
needs runtime resolution when creating maps dynamically.
The OptimizeMaps transform pass is updated to handle both hashmapMake
and hashmapMakeGeneric, and to recognize hashmapGenericSet in addition
to hashmapBinarySet and hashmapStringSet. The now-unused
hashmapCanGenerateHashEqual helper is removed.
* runtime: store large map keys and values indirectly
When a map key or value exceeds 128 bytes, the bucket now stores a
pointer to separately allocated memory instead of the data inline. This
matches Go's MapMaxKeyBytes/MapMaxElemBytes threshold and prevents
bucket sizes from exploding for large key/value types.
For example, map[[256]byte]int previously used 2128 bytes per bucket
(16 header + 256*8 keys + 8*8 values); now it uses 144 bytes per bucket
(16 header + 8*8 pointers + 8*8 values).
The indirection is fully encapsulated in the runtime via helper
functions. Store the computed key and value slot sizes on the hashmap so
all runtime and reflect paths use the same bucket layout, including
non-indirect keys and values.
Add big-key golden coverage and benchmarks. Make the benchmark vary
enough key bytes to exercise hashing.
- Do not use make([]byte, ...) to allocate, instead call the allocator
directly with a nil (undefined) layout. This makes sure the precise
GC will scan the contents of the allocation, since C could very well
put pointers in there.
- Simplify the map to use the pointer as the key and the size as the
value, instead of storing the slices directly in the map.
Use a single package for certain constants that must be the same between
the compiler and the runtime.
While just using the same values in both places works, this is much more
obvious and harder to mess up. It also avoids the need for comments
pointing to the other location the constant is defined. And having it in
code makes it possible for IDEs to analyze the source.
In the future, more such constants and maybe algorithms can be added.
TODO: Remove the go.mod/go.sum in internal/tools once doing so doesn't break CI (e.g. once we drop support for go 1.19)
* builder/cc1as.h: fix typo found by 'make spell'
* GNUmakefile: remove exception for inbetween, fix instance now found by 'make spell'
* GNUmakefile: remove exception for programmmer, fix instance now found by 'make spell'
* go.mod: use updated misspell. GNUmakefile: add spellfix target, use it.
* ignore directories properly when invoking spellchecker.
* make spell: give internal/tools its own go.mod, as misspell requires newer go
* make lint: depend on tools and run the installed revive
(which was perhaps implied by the change that added revive to internal/tools,
but not required in GNUmakefile until we gave internal/tools its own temporary go.mod)
* .github: now that 'make spell' works well, run it from CI
* GNUmakefile: make spell now aborts if it finds misspelt words, so what it finds doesn't get lost in CI logs
* GNUmakefile: tools: avoid -C option on go generate to make test-llvm15-go119 circleci job happy, see
https://cs.opensource.google/go/go/+/2af48cbb7d85e5fdc635e75b99f949010c607786
* internal/tools/go.mod: fix format of go version to leave out patchlevel, else go complains.
This is a big change: apart from removing LLVM 14 it also removes typed
pointer support (which was only fully supported in LLVM up to version
14). This removes about 200 lines of code, but more importantly removes
a ton of special cases for LLVM 14.
Some map keys are hard to compare, such as floats. They are stored as if
the map keys are of interface type instead of the key type itself. This
makes working with them in the runtime package easier: they are compared
as regular interfaces.
Iterating over maps didn't care about this special case though. It just
returns the key, value pair as it is stored in the map. This is buggy,
and this commit fixes this bug.
This is a fairly big commit, but it actually changes very little.
getValue should really be a property of the builder (or frame), where
the previously created instructions are kept.
This implementation simply casts types without special support to an
interface, to make the implementation simpler and possibly reducing the
code size too. It will likely be slower than the canonical Go
implementation though (which builds special compare and hash functions
at compile time).
Make sure all allocas are created in the entry block and are given the
right lifetimes. This is good for code quality:
* Moving allocas to the entry block makes sure they are always
allocated statically (avoiding the need for a frame pointer) and do
not grow the stack on each new alloca instruction. This is
especially useful in loops where it could otherwise lead to a stack
overflow even though there is no recursion.
* Adding lifetime markers allows LLVM to reuse stack areas for
different allocas as long as their lifetimes do not overlap.
All in all, this reduces code size in all tested cases for the BBC
micro:bit, and reduces code size for most cases for WebAssembly.
By moving all allocas used in hashmap operations to the entry block, the
stack frame remains at a fixed size known at compile time. This avoids
stack overflows when doing map operations in loops and in general
improves code quality: the compiled size of testdata/map.go went from
3776 to 3632 in .text size.
Most of these errors are actually "todo" or "unimplemented" errors, so
the return type is known. This means that compilation can proceed (with
errors) even though the output will be incorrect. This is useful because
this way, all errors in a compilation unit can be shown together to the
user.
This commit replaces "unknown type" errors in getLLVMType with panics.
The main reason this is done is that it simplifies the code *a lot*.
Many `if err != nil` lines were there just because of type information.
Additionally, simply panicking is probably a better approach as the only
way this error can be produced is either with big new language features
or a serious compiler bug. Panicking is probably a better way to handle
this error anyway.
Jake Bailey
Ayke van Laethem
dkegel-fastly
Damian Gryski
Ron Evans
Konstantin Yegupov