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
The optimization to skip cloning the destination object on partial
stores when the buffer is already owned by the current memory view
mutated obj.buffer.buf in place. The previous v.buf clone only handled
the case where the store value itself aliased that buffer; it did not
cover the more common case where an earlier partial load had returned
a slice into the same buffer. The in-place store would then corrupt
the previously loaded value, breaking code such as cloudflare/bn256
where the gfP arithmetic loads, computes, and stores within the same
global during package initialization.
Fix this in load instead: when the source object is owned by the
current memory view, copy the loaded slice so the returned value is
independent of the live buffer. The v.buf clone in store is no longer
needed and is removed.
Updates the regression test added in the previous commit to reflect
the corrected behavior.
Adds a third init function to the store testdata: an initial partial
store puts the buffer into the current memory view, then a partial load
is followed by another partial store at the same offset, and finally the
loaded value is written to a separate global.
The expected output captures the current (incorrect) behavior of the
in-place partial store optimization: the loaded value gets corrupted by
the subsequent in-place store. The next commit fixes this.
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.
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.
This switches the Espressif fork from LLVM 19 to LLVM 20, so we can use
the improvements made between those LLVM versions. It also better aligns
with the system-LLVM build method, which currently also defaults to LLVM
20.
Note that this disables the machine outliner for RISC-V. It appears
there's a bug in there somewhere, with the machine outliner enabled the
crypto/elliptic package tests fail with -target=riscv-qemu.
This should ideally be investigated and reported upstream.
getelementptr offsets are signed, not unsigned. Yet they were used as
unsigned integers in interp.
Somehow this worked most of the time, until finally there was some code
that did a getelementptr with a negative index.
This was bug https://github.com/tinygo-org/tinygo/issues/3890.
See the diff for details. Essentially, it means that `copy` in the
interpreter was copying data that wasn't known yet, or copying data into
a slice that could be read externally after the interp pass.
This is a big commit that changes the way runtime type information is stored in
the binary. Instead of compressing it and storing it in a number of sidetables,
it is stored similar to how the Go compiler toolchain stores it (but still more
compactly).
This has a number of advantages:
* It is much easier to add new features to reflect support. They can simply
be added to these structs without requiring massive changes (especially in
the reflect lowering pass).
* It removes the reflect lowering pass, which was a large amount of hard to
understand and debug code.
* The reflect lowering pass also required merging all LLVM IR into one
module, which is terrible for performance especially when compiling large
amounts of code. See issue 2870 for details.
* It is (probably!) easier to reason about for the compiler.
The downside is that it increases code size a bit, especially when reflect is
involved. I hope to fix some of that in later patches.
This makes it much easier to read the value at runtime, as pointer
indices are naturally little endian. It should not affect anything else
in the program.
These instructions sometimes pop up in LLVM 15, but they never occured
in LLVM 14. Implementing them is relatively straightforward: simply
generalize the code that already exists for llvm.ICmp interpreting.
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.
Switch over to LLVM 14 for static builds. Keep using LLVM 13 for regular
builds for now.
This uses a branch of the upstream Espressif branch to fix an issue,
see: https://github.com/espressif/llvm-project/pull/59
Previously, a type assertion on a nil interface would result in an out-of-bounds operand access, as we assumed it was a ptrtoint.
This would usually result in an undefined value which happens not to have the same name as the asserted type (and therefore the assertion fails as expected).
However, with an LLVM build with asserts, LLVM throws an assertion error:
```
interp.test: /home/niaow/go/src/github.com/tinygo-org/tinygo/llvm-project/llvm/include/llvm/IR/User.h:170: llvm::Value* llvm::User::getOperand(unsigned int) const: Assertion `i < NumUserOperands && "getOperand() out of range!"' failed.
```
This change handles a type code of 0 specially.
This removes the parentHandle argument from the internal calling convention.
It was formerly used to implment coroutines.
Now that coroutines have been removed, it is no longer necessary.
Constant globals can't have been modified, even if a pointer is passed
externally. Therefore, don't treat it as such in hasExternalStore.
In addition, it doesn't make sense to update values of constant globals
after the interp pass is finished. So don't do this.
TODO: track whether objects are actually modified and only update the
globals if this is the case.
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.
Instead of doing lots of complicated calculations to get the shortest
GEP, I'll just cast it to i8*, do the GEP, and optionally cast to the
requested type.
This currently produces ugly constant expressions, but once LLVM
switches to opaque pointer types all of this shouldn't matter anymore.
This is uncommon, but it does happen if the source pointer is a bitcast
of a global. For example, if a struct is cast to an i8*, it's possible
to index beyond what would appear to be the size of the pointer (i8*).
This layout parameter is currently always nil and ignored, but will
eventually contain a pointer to a memory layout.
This commit also adds module verification to the transform tests, as I
found out that it didn't (and therefore didn't initially catch all
bugs).
Make sure that if a package initializer cannot be run, later package
initializers won't try to access any global variables touched by the
uninterpretable package initializer.
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 markExternal function is used when a global (function or global
variable) is somehow run at runtime. All the other globals it refers to
are from then on no longer known at compile time, so can't be used by
the interp package anymore.
This can also include inline assembly. While it is possible to modify
globals that way, it is only possible to modify exported globals:
similar to calling an undefined function (in C for example).
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.
A switch statement is not normally emitted by the compiler package, but
LLVM function passes may convert a series of if/else pairs to a switch
statement. A future change will run function passes in the package
compile phase, so the interp package (which is also run after all
modules are merged together) will need to deal with these new switch
statements.
Sometimes, LLVM may rename named structs when merging modules.
Therefore, we can't rely on typecodeID structs to retain their struct
names.
This commit changes the interface lowering pass to not rely on these
names. The interp package does however still rely on this name, but I
hope to fix that in the future.
Previously there was code to avoid impossible type asserts but it wasn't
great and in fact was too aggressive when combined with reflection.
This commit improves this by checking all types that exist in the
program that may appear in an interface (even struct fields and the
like) but without creating runtime.typecodeID objects with the type
assert. This has two advantages:
* As mentioned, it optimizes impossible type asserts away.
* It allows methods on types that were only asserted on (in
runtime.typeAssert) but never used in an interface to be optimized
away using GlobalDCE. This may have a cascading effect so that other
parts of the code can be further optimized.
This sometimes massively improves code size and mostly negates the code
size regression of the previous commit.
This distinction was useful before when reflect wasn't properly
supported. Back then it made sense to only include method sets that were
actually used in an interface. But now that it is possible to get to
other values (for example, by extracting fields from structs) and it is
possible to turn them back into interfaces, it is necessary to preserve
all method sets that can possibly be used in the program in a type
assert, interface assert or interface method call.
In the future, this logic will need to be revisited again when
reflect.New or reflect.Zero gets implemented.
Code size increases a bit in some cases, but usually in a very limited
way (except for one outlier in the drivers smoke tests). The next commit
will improve the situation significantly.
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 teaches the interp scanner that supported interface
operations (type assertions, interface assertions) are supported.
This fixes a problem with math/rand in Go 1.14.
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.
Some mapassign operations cannot (yet) be done by the interp package.
Implement a fallback mechanism so that these operations can still be
performed at runtime.
This kind of code might be generated by the switch implementation of
func values. The func value is represented as a ptrtoint, and before
calling it, it is compared against 0.
This is really just a simple workaround. When such an instruction is
encountered, it will just fall back to marking the entire function as
having side effects. Ideally it should trace all affected instructions
and check if they would have any side effects, but this at least fixes a
number of compile errors.
This commit gets the following packages to compile:
* context
* database/sql/driver
* image/jpeg
* image/png
Declarations would enter an infinite loop when trying to loop over basic
blocks. That was probably an undefined operation, but still somehow
didn't crash the compiler.
Make sure that scanning declarations works as expected.
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)
iamrajiv
Jake Bailey
Nia Waldvogel
Ayke van Laethem
Elliott Sales de Andrade