Written entirely by Claude (Anthropic's Claude Code), at the request of
and under the direction of dgryski, on the dgryski/llvm23 branch (LLVM
22 support, in preparation for the eventual LLVM 23 release; the
corresponding go-llvm branch of the same name adds the matching
binding support this depends on).
Found while running real-world Go test suites through a tinygo built
against LLVM 22 (as a smoke test of the earlier captures(none)/
nocapture and lifetime-intrinsic fixes on this branch): `tinygo test`
on github.com/dgryski/go-rc5 panicked at compile time with "unknown
value" inside interp.(*runner).getValue, while compiling
(*sync.Once).Do. Bisecting against LLVM 21 (unaffected) narrowed it to
a change introduced in LLVM 22 specifically, unrelated to the earlier
captures/lifetime work.
Root cause: LLVM 22 stopped exposing switch-instruction case values as
regular instruction operands -- only the condition and
destination-block operands remain. interp/compiler.go's `case
llvm.Switch:` handling walked raw operands assuming the old
alternating (value, label) layout, so under LLVM 22 it read a
destination *block* where it expected an integer case value,
eventually panicking deep inside a getValue call it couldn't resolve.
This only manifested on functions actually compiled by the interp
package (TinyGo's compile-time evaluator for global initializers) that
happen to reach a switch-based dispatch, such as sync.Once's
defer-based Do method -- hence it needed a real, moderately complex
package (crypto/cipher via go-rc5) to surface, and never showed up in
smaller smoke tests.
Fix: use the new version-independent Value.SuccessorsCount()/
Value.Successor(i) and Value.GetSwitchCaseValue(i) helpers just added
to go-llvm, instead of raw Operand() indexing.
Also applies the same captures(none)/nocapture golden-IR normalization
already used in transform/transform_test.go and compiler/compiler_test.go
to interp/interp_test.go's separate copy of the same comparator helper,
which was missed in the earlier pass and started failing two of its
subtests once actually run against LLVM 22.
Verified: `tinygo test` on go-rc5 now passes reliably (repeated runs)
against both LLVM 20 (default) and LLVM 22; full transform/compiler/
interp/cgo/goenv test suites pass on both versions. The `builder`
package has pre-existing, environment-related test failures (stale
GOROOT cache, local clang/target-feature drift) confirmed identical
against an unmodified LLVM 20 build, so unrelated to this change.
When the interpreter encountered a load that was out of bounds of the
object, it panicked with "interp: load out of bounds", crashing the
compiler. This can happen for valid Go programs, for example when
dereferencing the pointer returned by unsafe.SliceData on a
zero-capacity slice, which points to a zero-sized object:
package main
import "unsafe"
var p = unsafe.SliceData([]int{})
var v = *p
func main() {}
Return nil for an out-of-bounds load, the same as for an external
global, so the caller defers the load to runtime instead of crashing.
This matches what regular Go does, where the load reads from the
runtime zero-base at runtime.
Fixes#4214
memoryView.store cloned the entire destination object on every partial
store. Compiling a program that pulls in golang.org/x/text/collate hit
this hard: its generated tables are initialized one element at a time,
and each element store copied the whole global, making interp quadratic
in the table size.
Switch to copy-on-first-write per memory view: clone the object the
first time this view writes to it, then mutate that private copy in
place on later partial stores. Rollback is unaffected because revert
still discards the view's objects wholesale.
Two extra safety tweaks fall out of this:
- Full overwrites now clone the incoming value, so the stored buffer
can never alias state held by the caller.
- Partial in-place stores snapshot the source buffer, so a store
whose source is a load from the same object (overlapping or not)
still sees the pre-store bytes.
Add an interp golden test exercising both the overlapping load/store
case and a cross-object aliased load/store case.
* interp: bail out of loops that iterate too many times
The existing loop guard (errLoopUnrolled) only fires when a loop body
emits runtime instructions. Loops that are fully evaluable at compile
time, such as inserting thousands of entries into a map, were not
caught and could hang the compiler.
Add a per-basic-block iteration counter that triggers a recoverable
error (errLoopTooLong) when any block is entered more than 1000 times
in a single function call. This defers the init function to runtime,
which is the same behavior as other interp bailouts.
Profiling showed that 83% of CPU time was spent in GC, caused by
allocation pressure from the interp memory cloning on each map
mutation. The iteration limit avoids this entirely by bailing out
before the quadratic cost becomes significant.
Performance on the reproducer from #2090 (map init with strconv.Itoa):
entries before after
5,000 7.4s 2.1s
10,000 17.5s 2.1s
20,000 48.0s 2.8s
65,536 >180s (OOM) 3.2s
* Add -interp-loop-limit
The compiler now implements the copy builtin directly instead of calling sliceCopy.
The length is calculated with the llvm.umax.* intrinsics, and the move is performed by llvm.memmove.*.
Both of these operations are easily understood by LLVM's optimization passes.
The type's alignment is also provided to llvm.memmove.*, which is useful when rewriting the move.
Interp no longer needs to reimplement sliceCopy.
Some edge case handling was implemented by sliceCopy but not llvm.memmove.*/llvm.memcpy.*.
I copied this over, so copies of external slices should work now.
Volatile moves/copies are now run at runtime by interp.
There is a 4-byte size increase due to some confusing length logic in sendUSBPacket.
I will look at sendUSBPacket in a future PR.
The old LLVM pass manager is deprecated and should not be used anymore.
Moreover, the pass manager builder (which we used to set up a pass
pipeline) is actually removed from LLVM entirely in LLVM 17:
https://reviews.llvm.org/D145387https://reviews.llvm.org/D145835
The new pass manager does change the binary size in many cases: both
growing and shrinking it. However, on average the binary size remains
more or less the same.
This is needed as a preparation for LLVM 17.
This commit will use the memory layout information for heap allocations
added in the previous commit to determine LLVM types, instead of
guessing their types based on the content. This fixes a bug in which
recursive data structures (such as doubly linked lists) would result in
a compiler stack overflow due to infinite recursion.
Not all heap allocations have a memory layout yet, but this can be
incrementally fixed in the future. So far, this commit should fix
(almost?) all cases of this stack overflow issue.
Previously, a package initializer that could not be reverted correctly
would be called at runtime. But the initializer would be called in the
wrong order: after later packages are initialized.
This commit fixes this oversight and adds a test to verify the new
behavior.
The interp package is in many cases able to execute map functions in the
runtime directly. This is probably slower than adding special support
for them in the interp package and also doesn't cover all cases (most
importantly, map keys that contain pointers) but removing this code also
removes a large amount of code that needs to be maintained and is
susceptible to hard-to-find bugs.
As a side effect, this resulted in different output of the
testdata/map.go test because the test relied on the existing iteration
order of TinyGo maps. I've updated the test to not rely on this test,
making the output compatible with what the Go toolchain would output.
I've discovered a bug in the implementation of the PHI instruction in
the interp package. This commit fixes the bug.
I've found this issue while investigating an issue with maps after
running interp per package.
For a full explanation, see interp/README.md. In short, this rewrite is
a redesign of the partial evaluator which improves it over the previous
partial evaluator. The main functional difference is that when
interpreting a function, the interpretation can be rolled back when an
unsupported instruction is encountered (for example, an actual unknown
instruction or a branch on a value that's only known at runtime). This
also means that it is no longer necessary to scan functions to see
whether they can be interpreted: instead, this package now just tries to
interpret it and reverts when it can't go further.
This new design has several benefits:
* Most errors coming from the interp package are avoided, as it can
simply skip the code it can't handle. This has long been an issue.
* The memory model has been improved, which means some packages now
pass all tests that previously didn't pass them.
* Because of a better design, it is in fact a bit faster than the
previous version.
This means the following packages now pass tests with `tinygo test`:
* hash/adler32: previously it would hang in an infinite loop
* math/cmplx: previously it resulted in errors
This also means that the math/big package can be imported. It would
previously fail with a "interp: branch on a non-constant" error.
This can be useful to test improvements in LLVM master and to make it
possible to support LLVM 11 for the most part already before the next
release. That also allows catching LLVM bugs early to fix them upstream.
Note that tests do not yet pass for this LLVM version, but the TinyGo
compiler can be built with the binaries from apt.llvm.org (at the time
of making this commit).
Non-constant type asserts are not yet implemented, but should be
relatively easy to add at a later time. They should result in a clear
error message for now.
This implements the copy() built-in function. It may not work in all
cases, but should work in most cases.
This commit gets the following 3 packages to compile, according to
tinygo-site/imports/main.go:
* encoding/base32
* encoding/base64
* encoding/pem (was blocked by encoding/base64)
Damian Gryski
Jake Bailey
iamrajiv
Nia Waldvogel
Ayke van Laethem
Kenneth Bell
Elliott Sales de Andrade