interp

package
v0.0.0-...-984a488 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 28, 2019 License: BSD-3-Clause Imports: 4 Imported by: 0

README

Partial evaluation of initialization code in Go

For several reasons related to code size and memory consumption (see below), it is best to try to evaluate as much initialization code at compile time as possible and only run unknown expressions (e.g. external calls) at runtime. This is in practice a partial evaluator of the runtime.initAll function, which calls each package initializer.

It works by directly interpreting LLVM IR:

  • Almost all operations work directly on constants, and are implemented using the llvm.Const* set of functions that are evaluated directly.
  • External function calls and some other operations (inline assembly, volatile load, volatile store) are seen as having limited side effects. Limited in the sense that it is known at compile time which globals it affects, which then are marked 'dirty' (meaning, further operations on it must be done at runtime). These operations are emitted directly in the runtime.initAll function. Return values are also considered 'dirty'.
  • Such 'dirty' objects and local values must be executed at runtime instead of at compile time. This dirtyness propagates further through the IR, for example storing a dirty local value to a global also makes the global dirty, meaning that the global may not be read or written at compile time as it's contents at that point during interpretation is unknown.
  • There are some heuristics in place to avoid doing too much with dirty values. For example, a branch based on a dirty local marks the whole function itself as having side effect (as if it is an external function). However, all globals it touches are still taken into account and when a call is inserted in runtime.initAll, all globals it references are also marked dirty.
  • Heap allocation (runtime.alloc) is emulated by creating new objects. The value in the allocation is the initializer of the global, the zero value is the zero initializer.
  • Stack allocation (alloca) is often emulated using a fake alloca object, until the address of the alloca is taken in which case it is also created as a real alloca in runtime.initAll and marked dirty. This may be necessary when calling an external function with the given alloca as paramter.

Why is this necessary?

A partial evaluator is hard to get right, so why go through all the trouble of writing one?

The main reason is that the previous attempt wasn't complete and wasn't sound. It simply tried to evaluate Go SSA directly, which was good but more difficult than necessary. An IR based interpreter needs to understand fewer instructions as the LLVM IR simply has less (complex) instructions than Go SSA. Also, LLVM provides some useful tools like easily getting all uses of a function or global, which Go SSA does not provide.

But why is it necessary at all? The answer is that globals with initializers are much easier to optimize by LLVM than initialization code. Also, there are a few other benefits:

  • Dead globals are trivial to optimize away.
  • Constant globals are easier to detect. Remember that Go does not have global constants in the same sense as that C has them. Constants are useful because they can be propagated and provide some opportunities for other optimizations (like dead code elimination when branching on the contents of a global).
  • Constants are much more efficent on microcontrollers, as they can be allocated in flash instead of RAM.

For more details, see this section of the documentation.

Documentation

Overview

Package interp interprets Go package initializers as much as possible. This avoid running them at runtime, improving code size and making other optimizations possible.

Index

Constants

This section is empty.

Variables

View Source 
var ErrUnreachable = errors.New("interp: unreachable executed")

Functions

func Run 

func Run(mod llvm.Module, targetData llvm.TargetData, debug bool) error

Run evaluates the function with the given name and then eliminates all callers.

Types

type AllocaValue 

type AllocaValue struct {
	Eval       *Eval
	Underlying llvm.Value // the constant value itself if not dirty, otherwise the alloca instruction
	Dirty      bool       // this value must be evaluated at runtime
}

An alloca represents a local alloca, which is a stack allocated variable. It is emulated by storing the constant of the alloca.

func (*AllocaValue) GetElementPtr 

func (v *AllocaValue) GetElementPtr(indices []uint32) Value

GetElementPtr returns a value (a *GetElementPtrValue) that keeps a reference to this alloca, so that Load() and Store() continue to work.

func (*AllocaValue) IsConstant 

func (v *AllocaValue) IsConstant() bool

func (*AllocaValue) Load 

func (v *AllocaValue) Load() llvm.Value

Load returns the value this alloca contains, which may be evaluated at runtime.

func (*AllocaValue) Store 

func (v *AllocaValue) Store(value llvm.Value)

Store updates the value of this alloca.

func (*AllocaValue) String 

func (v *AllocaValue) String() string

func (*AllocaValue) Type 

func (v *AllocaValue) Type() llvm.Type

Type returns the type of this alloca, which is always a pointer.

func (*AllocaValue) Value 

func (v *AllocaValue) Value() llvm.Value

Value turns this alloca into a runtime alloca instead of a compile-time constant (if not already converted), and returns the alloca itself.

type Eval 

type Eval struct {
	Mod        llvm.Module
	TargetData llvm.TargetData
	Debug      bool
	// contains filtered or unexported fields
}

func (*Eval) Function 

func (e *Eval) Function(fn llvm.Value, params []Value, pkgName string) (Value, error)

type GetElementPtrValue 

type GetElementPtrValue struct {
	Alloca  *AllocaValue
	Indices []uint32
}

GetElementPtrValue wraps an alloca, keeping track of what the GEP points to so it can be used as a pointer value (with Load() and Store()).

func (*GetElementPtrValue) GetElementPtr 

func (v *GetElementPtrValue) GetElementPtr(indices []uint32) Value

func (*GetElementPtrValue) IsConstant 

func (v *GetElementPtrValue) IsConstant() bool

func (*GetElementPtrValue) Load 

func (v *GetElementPtrValue) Load() llvm.Value

Load deferences the pointer this GEP points to. For a constant GEP, it extracts the value from the underlying alloca.

func (*GetElementPtrValue) Store 

func (v *GetElementPtrValue) Store(value llvm.Value)

Store stores to the pointer this GEP points to. For a constant GEP, it updates the underlying allloca.

func (*GetElementPtrValue) String 

func (v *GetElementPtrValue) String() string

func (*GetElementPtrValue) Type 

func (v *GetElementPtrValue) Type() llvm.Type

Type returns the type of this GEP, which is always of type pointer.

func (*GetElementPtrValue) Value 

func (v *GetElementPtrValue) Value() llvm.Value

Value creates the LLVM GEP instruction of this GetElementPtrValue wrapper and returns it.

type GlobalValue 

type GlobalValue struct {
	Eval       *Eval
	Underlying llvm.Value
}

GlobalValue wraps a LLVM global variable.

func (*GlobalValue) GetElementPtr 

func (v *GlobalValue) GetElementPtr(indices []uint32) Value

GetElementPtr returns a constant GEP on this global, which can be used in load and store instructions.

func (*GlobalValue) IsConstant 

func (v *GlobalValue) IsConstant() bool

IsConstant returns true if this global is not dirty, false otherwise.

func (*GlobalValue) Load 

func (v *GlobalValue) Load() llvm.Value

Load returns the initializer of the global variable.

func (*GlobalValue) MarkDirty 

func (v *GlobalValue) MarkDirty()

MarkDirty marks this global as dirty, meaning that every load from and store to this global (from now on) must be performed at runtime.

func (*GlobalValue) Store 

func (v *GlobalValue) Store(value llvm.Value)

Store sets the initializer of the global variable.

func (*GlobalValue) String 

func (v *GlobalValue) String() string

func (*GlobalValue) Type 

func (v *GlobalValue) Type() llvm.Type

Type returns the type of this global variable, which is a pointer type. Use Type().ElementType() to get the actual global variable type.

func (*GlobalValue) Value 

func (v *GlobalValue) Value() llvm.Value

Value returns the initializer for this global variable.

type LocalValue 

type LocalValue struct {
	Eval       *Eval
	Underlying llvm.Value
}

A type that simply wraps a LLVM constant value.

func (*LocalValue) GetElementPtr 

func (v *LocalValue) GetElementPtr(indices []uint32) Value

GetElementPtr returns a constant GEP when the underlying value is also a constant GEP. It panics when the underlying value is not a constant GEP: getting the pointer to a constant is not possible.

func (*LocalValue) IsConstant 

func (v *LocalValue) IsConstant() bool

func (*LocalValue) Load 

func (v *LocalValue) Load() llvm.Value

Load loads a constant value if this is a constant GEP, otherwise it panics.

func (*LocalValue) Store 

func (v *LocalValue) Store(value llvm.Value)

Store stores to the underlying value if the value type is a constant GEP, otherwise it panics.

func (*LocalValue) String 

func (v *LocalValue) String() string

func (*LocalValue) Type 

func (v *LocalValue) Type() llvm.Type

func (*LocalValue) Value 

func (v *LocalValue) Value() llvm.Value

Value implements Value by returning the constant value itself.

type MapValue 

type MapValue struct {
	Eval       *Eval
	PkgName    string
	Underlying llvm.Value
	Keys       []Value
	Values     []Value
	KeySize    int
	ValueSize  int
	KeyType    llvm.Type
	ValueType  llvm.Type
}

MapValue implements a Go map which is created at compile time and stored as a global variable.

func (*MapValue) GetElementPtr 

func (v *MapValue) GetElementPtr(indices []uint32) Value

GetElementPtr panics: maps are of reference type so their (interior) addresses cannot be calculated.

func (*MapValue) IsConstant 

func (v *MapValue) IsConstant() bool

func (*MapValue) Load 

func (v *MapValue) Load() llvm.Value

Load panics: maps are of reference type so cannot be dereferenced.

func (*MapValue) PutString 

func (v *MapValue) PutString(keyBuf, keyLen, valPtr Value)

PutString does a map assign operation, assuming that the map is of type map[string]T.

func (*MapValue) Store 

func (v *MapValue) Store(value llvm.Value)

Store panics: maps are of reference type so cannot be stored to.

func (*MapValue) String 

func (v *MapValue) String() string

func (*MapValue) Type 

func (v *MapValue) Type() llvm.Type

Type returns type runtime.hashmap, which is the actual hashmap type.

func (*MapValue) Value 

func (v *MapValue) Value() llvm.Value

Value returns a global variable which is a pointer to the actual hashmap.

type PointerCastValue 

type PointerCastValue struct {
	Eval       *Eval
	Underlying Value
	CastType   llvm.Type
}

PointerCastValue represents a bitcast operation on a pointer.

func (*PointerCastValue) GetElementPtr 

func (v *PointerCastValue) GetElementPtr(indices []uint32) Value

GetElementPtr panics: it is not (yet) possible to do a GEP operation on a bitcast.

func (*PointerCastValue) IsConstant 

func (v *PointerCastValue) IsConstant() bool

func (*PointerCastValue) Load 

func (v *PointerCastValue) Load() llvm.Value

Load tries to load and bitcast the given value. If this value cannot be bitcasted, Load panics.

func (*PointerCastValue) Store 

func (v *PointerCastValue) Store(value llvm.Value)

Store panics: it is not (yet) possible to store directly to a bitcast.

func (*PointerCastValue) String 

func (v *PointerCastValue) String() string

func (*PointerCastValue) Type 

func (v *PointerCastValue) Type() llvm.Type

Type returns the type this pointer has been cast to.

func (*PointerCastValue) Value 

func (v *PointerCastValue) Value() llvm.Value

Value returns a constant bitcast value.

type Unsupported 

type Unsupported struct {
	Inst llvm.Value
}

func (Unsupported) Error 

func (e Unsupported) Error() string

type Value 

type Value interface {
	Value() llvm.Value            // returns a LLVM value
	Type() llvm.Type              // equal to Value().Type()
	IsConstant() bool             // returns true if this value is a constant value
	Load() llvm.Value             // dereference a pointer
	Store(llvm.Value)             // store to a pointer
	GetElementPtr([]uint32) Value // returns an interior pointer
	String() string               // string representation, for debugging
}

A Value is a LLVM value with some extra methods attached for easier interpretation.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.