* 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
Go 1.26 changed Darwin's rawSyscall/Syscall from assembly stubs to Go
wrappers that call variadic rawsyscalln/syscalln. When the interp tries
to evaluate syscall.init() at compile time (which calls Getrlimit →
rawSyscall → rawsyscalln), it encounters a ptrtoint of a function
pointer and fails with 'ptrtoint integer size does not equal pointer
size'.
Make this a recoverable error so the interp reverts the init
interpretation and defers it to runtime, matching the behavior for other
uninterpretable init functions.
The old traceback would look like this:
# internal/godebug
/usr/local/go/src/internal/godebug/godebug.go:101:11: interp: test
call <2> 0 <3> 0
traceback:
/usr/local/go/src/internal/godebug/godebug.go:101:11:
call <2> 0 <3> 0
/usr/local/go/src/internal/godebug:
call <1> 0
With this patch, it looks like this:
# io/fs
/usr/local/go/src/io/fs/fs.go:144:45: interp: test
%0 = load %runtime._interface, ptr @"internal/oserror.ErrInvalid", align 8, !dbg !316
traceback:
/usr/local/go/src/io/fs/fs.go:144:45:
%0 = load %runtime._interface, ptr @"internal/oserror.ErrInvalid", align 8, !dbg !316
/usr/local/go/src/io/fs/fs.go:137:28:
%0 = call %runtime._interface @"io/fs.errInvalid"(ptr undef), !dbg !317
For developers (like me) who are familiar with LLVM, this is probably
easier to read. For users, I'm not sure: the instructions have quite a
lot of distracting fluff in them. But at least it contains the function
names that are called (which are not currently present in the old
traceback).
...that said, having the LLVM instructions in a bug report is probably
going to be easier for people who are familar with LLVM.
This change triggers a revert whenever a basic block runs instructions at runtime twice.
As a result, a loop body with runtime-only instructions will no longer be unrolled.
This should help some extreme cases where loops can be expanded into hundreds or thousands of instructions.
This results in a significant speedup in some cases. For example, this
runs over twice as fast with a warm cache:
tinygo build -o test.elf ./testdata/stdlib.go
This should help a lot with edit-compile-test cycles, that typically
only modify a single package.
This required some changes to the interp package to deal with globals
created in a previous run of the interp package and to deal with
external globals (that can't be loaded from or stored to).
GetElementPtr would not work on values that weren't pointers. Because
fixed addresses (often used in memory-mapped I/O) are integers rather
than pointers in interp, it would return an error.
This resulted in the teensy40 target not compiling correctly since the
interp package rewrite. This commit should fix that.
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 commit replaces most panics in interp/frame.go and interp/scan.go
with real error messages. The remaining ones are panics that should not
happen when working with valid IR.
This commit improves error reporting in several ways:
* Location information is read from the intruction that causes the
error, as far as that's available.
* The package that is being interpreted is included in the error
message. This may be the most useful part of the improvements.
* The hashmap update intrinsics now doesn't panic, instead it logs a
clear error (with location information, as in the above two bullet
points).
This is possible thanks to improvements in LLVM 9. This means that after
this change, TinyGo will depend on LLVM 9.
This interpreter currently complements the Go SSA level interpreter. It
may stay complementary or may be the only interpreter in the future.
This interpreter is experimental and not yet finished (there are known
bugs!) so it is disabled by default. It can be enabled by passing the
-initinterp flag.
The goal is to be able to run all initializations at compile time except
for the ones having side effects. This mostly works except perhaps for a
few edge cases.
In the future, this interpeter may be used to actually run regular Go
code, perhaps in a shell.
Jake Bailey
deadprogram
Ayke van Laethem
Kenneth Bell
Nia Waldvogel