transform

Documentation

Overview

Package transform contains transformation passes for the TinyGo compiler. These transformation passes may be optimization passes or lowering passes.

Optimization passes transform the IR in such a way that they increase the performance of the generated code and/or help the LLVM optimizer better do its job by simplifying the IR. This usually means that certain TinyGo-specific runtime calls are removed or replaced with something simpler if that is a valid operation.

Lowering passes are usually required to run. One example is the interface lowering pass, which replaces stub runtime calls to get an interface method with the method implementation (either a direct call or a thunk).

Index

• func AddGlobalsBitmap(mod llvm.Module) bool
• func ApplyFunctionSections(mod llvm.Module)
• func CreateStackSizeLoads(mod llvm.Module, config *compileopts.Config) []string
• func DisableTailCalls(mod llvm.Module)
• func ExternalInt64AsPtr(mod llvm.Module) error
• func LowerCoroutines(mod llvm.Module, needStackSlots bool) error
• func LowerFuncValues(mod llvm.Module)
• func LowerInterfaces(mod llvm.Module, sizeLevel int) error
• func LowerInterrupts(mod llvm.Module, sizeLevel int) []error
• func LowerReflect(mod llvm.Module)
• func MakeGCStackSlots(mod llvm.Module) bool
• func Optimize(mod llvm.Module, config *compileopts.Config, optLevel, sizeLevel int, ...) []error
• func OptimizeAllocs(mod llvm.Module, printAllocs *regexp.Regexp, ...)
• func OptimizeMaps(mod llvm.Module)
• func OptimizeReflectImplements(mod llvm.Module)
• func OptimizeStringEqual(mod llvm.Module)
• func OptimizeStringToBytes(mod llvm.Module)
• func ReplacePanicsWithTrap(mod llvm.Module)
• type CoroutinesError
  • func (err CoroutinesError) Error() string
• type CoroutinesErrorLine
• type ErrMissingIntrinsic
  • func (err ErrMissingIntrinsic) Error() string

Functions

func AddGlobalsBitmap

func AddGlobalsBitmap(mod llvm.Module) bool

AddGlobalsBitmap performs a few related functions. It is needed for scanning globals on platforms where the .data/.bss section is not easily accessible by the GC, and thus all globals that contain pointers must be made reachable by the GC in some other way.

First, it scans all globals, and bundles all globals that contain a pointer into one large global (updating all uses in the process). Then it creates a bitmap (bit vector) to locate all the pointers in this large global. This bitmap allows the GC to know in advance where exactly all the pointers live in the large globals bundle, to avoid false positives.

func ApplyFunctionSections

func ApplyFunctionSections(mod llvm.Module)

ApplyFunctionSections puts every function in a separate section. This makes it possible for the linker to remove dead code. It is the equivalent of passing -ffunction-sections to a C compiler.

func CreateStackSizeLoads

func CreateStackSizeLoads(mod llvm.Module, config *compileopts.Config) []string

CreateStackSizeLoads replaces internal/task.getGoroutineStackSize calls with loads from internal/task.stackSizes that will be updated after linking. This way the stack sizes are loaded from a separate section and can easily be modified after linking.

func DisableTailCalls

func DisableTailCalls(mod llvm.Module)

DisableTailCalls adds the "disable-tail-calls"="true" function attribute to all functions. This may be necessary, in particular to avoid an error with WebAssembly in LLVM 11.

func ExternalInt64AsPtr

func ExternalInt64AsPtr(mod llvm.Module) error

ExternalInt64AsPtr converts i64 parameters in externally-visible functions to values passed by reference (*i64), to work around the lack of 64-bit integers in JavaScript (commonly used together with WebAssembly). Once that's resolved, this pass may be avoided. For more details: https://github.com/WebAssembly/design/issues/1172

This pass can be enabled/disabled with the -wasm-abi flag, and is enabled by default as of december 2019.

func LowerCoroutines

func LowerCoroutines(mod llvm.Module, needStackSlots bool) error

LowerCoroutines turns async functions into coroutines. This must be run with the coroutines scheduler.

Before this pass, goroutine starts are expressed as a call to an intrinsic called "internal/task.start". This intrinsic accepts the function pointer and a pointer to a struct containing the function's arguments.

Before this pass, an intrinsic called "internal/task.Pause" is used to express suspensions of the current goroutine.

This pass first accumulates a list of blocking functions. A function is considered "blocking" if it calls "internal/task.Pause" or any other blocking function.

Blocking calls are implemented by turning blocking functions into a coroutine. The body of each blocking function is modified to start a new coroutine, and to return after the first suspend. After calling a blocking function, the caller coroutine suspends. The caller also provides a buffer to store the return value into. When a blocking function returns, the return value is written into this buffer and then the caller is queued to run.

Goroutine starts which invoke non-blocking functions are implemented as direct calls. Goroutine starts are replaced with the creation of a new task data structure followed by a call to the start of the blocking function. The task structure is populated with a "noop" coroutine before invoking the blocking function. When the blocking function returns, it resumes this "noop" coroutine which does nothing. The goroutine starter is able to continue after the first suspend of the started goroutine.

The transformation of a function to a coroutine is accomplished using LLVM's coroutines system (https://llvm.org/docs/Coroutines.html). The simplest implementation of a coroutine inserts a suspend point after every blocking call.

Transforming blocking functions into coroutines and calls into suspend points is extremely expensive. In many cases, a blocking call is followed immediately by a function terminator (a return or an "unreachable" instruction). This is a blocking "tail call". In a non-returning tail call (call to a non-returning function, such as an infinite loop), the coroutine can exit without any extra work. In a returning tail call, the returned value must either be the return of the call or a value known before the call. If the return value of the caller is the return of the callee, the coroutine can exit without any extra work and the tailed call will instead return to the caller of the caller. If the return value is known in advance, this result can be stored into the parent's return buffer before the call so that a suspend is unnecessary. If the callee returns an unnecessary value, a return buffer can be allocated on the heap so that it will outlive the coroutine.

In the implementation of time.Sleep, the current task is pushed onto a timer queue and then suspended. Since the only suspend point is a call to "internal/task.Pause" followed by a return, there is no need to transform this into a coroutine. This generalizes to all blocking functions in which all suspend points can be elided. This optimization saves a substantial amount of binary size.

func LowerFuncValues

func LowerFuncValues(mod llvm.Module)

LowerFuncValues lowers the runtime.funcValueWithSignature type and runtime.getFuncPtr function to their final form.

func LowerInterfaces

func LowerInterfaces(mod llvm.Module, sizeLevel int) error

LowerInterfaces lowers all intermediate interface calls and globals that are emitted by the compiler as higher-level intrinsics. They need some lowering before LLVM can work on them. This is done so that a few cleanup passes can run before assigning the final type codes.

func LowerInterrupts

func LowerInterrupts(mod llvm.Module, sizeLevel int) []error

LowerInterrupts creates interrupt handlers for the interrupts created by runtime/interrupt.New.

The operation is as follows. The compiler creates the following during IR generation:

• calls to runtime/interrupt.Register that map interrupt IDs to ISR names.
• runtime/interrupt.handle objects that store the (constant) interrupt ID and interrupt handler func value.

This pass then creates the specially named interrupt handler names that simply call the registered handlers. This might seem like it causes extra overhead, but in fact inlining and const propagation will eliminate most if not all of that.

func LowerReflect

func LowerReflect(mod llvm.Module)

LowerReflect is used to assign a type code to each type in the program that is ever stored in an interface. It tries to use the smallest possible numbers to make the code that works with interfaces as small as possible.

func MakeGCStackSlots

func MakeGCStackSlots(mod llvm.Module) bool

MakeGCStackSlots converts all calls to runtime.trackPointer to explicit stores to stack slots that are scannable by the GC.

func Optimize

func Optimize(mod llvm.Module, config *compileopts.Config, optLevel, sizeLevel int, inlinerThreshold uint) []error

Optimize runs a number of optimization and transformation passes over the given module. Some passes are specific to TinyGo, others are generic LLVM passes. You can set a preferred performance (0-3) and size (0-2) level and control the limits of the inliner (higher numbers mean more inlining, set it to 0 to disable entirely).

Please note that some optimizations are not optional, thus Optimize must alwasy be run before emitting machine code. Set all controls (optLevel, sizeLevel, inlinerThreshold) to 0 to reduce the number of optimizations to a minimum.

func OptimizeAllocs

func OptimizeAllocs(mod llvm.Module, printAllocs *regexp.Regexp, logger func(token.Position, string))

OptimizeAllocs tries to replace heap allocations with stack allocations whenever possible. It relies on the LLVM 'nocapture' flag for interprocedural escape analysis, and within a function looks whether an allocation can escape to the heap. If printAllocs is non-nil, it indicates the regexp of functions for which a heap allocation explanation should be printed (why the object can't be stack allocated).

func OptimizeMaps

func OptimizeMaps(mod llvm.Module)

OptimizeMaps eliminates created but unused maps.

In the future, this should statically allocate created but never modified maps. This has not yet been implemented, however.

func OptimizeReflectImplements

func OptimizeReflectImplements(mod llvm.Module)

OptimizeReflectImplements optimizes the following code:

implements := someType.Implements(someInterfaceType)

where someType is an arbitrary reflect.Type and someInterfaceType is a reflect.Type of interface kind, to the following code:

_, implements := someType.(interfaceType)

if the interface type is known at compile time (that is, someInterfaceType is a LLVM constant aggregate). This optimization is especially important for the encoding/json package, which uses this method.

As of this writing, the (reflect.Type).Interface method has not yet been implemented so this optimization is critical for the encoding/json package.

func OptimizeStringEqual

func OptimizeStringEqual(mod llvm.Module)

OptimizeStringEqual transforms runtime.stringEqual(...) calls into simple integer comparisons if at least one of the sides of the comparison is zero. Ths converts str == "" into len(str) == 0 and "" == "" into false.

func OptimizeStringToBytes

func OptimizeStringToBytes(mod llvm.Module)

OptimizeStringToBytes transforms runtime.stringToBytes(...) calls into const []byte slices whenever possible. This optimizes the following pattern:

w.Write([]byte("foo"))

where Write does not store to the slice.

func ReplacePanicsWithTrap

func ReplacePanicsWithTrap(mod llvm.Module)

ReplacePanicsWithTrap replaces each call to panic (or similar functions) with calls to llvm.trap, to reduce code size. This is the -panic=trap command-line option.

Types

type CoroutinesError

type CoroutinesError struct {
	Msg       string
	Pos       token.Position
	Traceback []CoroutinesErrorLine
}

CoroutinesError is an error returned when coroutine lowering failed, for example because an async function is exported.

func (CoroutinesError) Error

func (err CoroutinesError) Error() string

Error implements the error interface by returning a simple error message without the stack.

type CoroutinesErrorLine

type CoroutinesErrorLine struct {
	Name     string         // function name
	Position token.Position // position in the function
}

CoroutinesErrorLine is a single line of a CoroutinesError traceback.

type ErrMissingIntrinsic

type ErrMissingIntrinsic struct {
	Name string
}

ErrMissingIntrinsic is an error indicating that a required intrinsic was not found in the module.

func (ErrMissingIntrinsic) Error

func (err ErrMissingIntrinsic) Error() string