op3

Documentation

Index

• func AliasCorrect(p *ast.Program, aliases [][]ast.Variable, outputs []ast.Variable, ...) *ast.Program
• func InputSet(p *ast.Program) map[ast.Variable]bool
• func Inputs(p *ast.Program) []ast.Variable
• func IsPrimitive(p *ast.Program) bool
• func IsPrimitiveExpression(expr ast.Expression) bool
• func IsSSA(p *ast.Program) bool
• func Lower(p *ast.Program) (*ast.Program, error)
• func Pare(p *ast.Program, outputs []ast.Variable) (*ast.Program, error)
• func ReadOnly(p *ast.Program, v ast.Variable) bool
• func RenameVariables(p *ast.Program, replacements map[ast.Variable]ast.Variable) *ast.Program
• func SortedVariables(vs []ast.Variable) []ast.Variable
• func VariableSet(vs []ast.Variable) map[ast.Variable]bool
• func Variables(p *ast.Program) []ast.Variable
• type InterferenceGraph
  • func BuildInterferenceGraph(p *ast.Program, outputs []ast.Variable) *InterferenceGraph
  • func NewInterferenceGraph() *InterferenceGraph
  • func (g *InterferenceGraph) AddInterference(x, y ast.Variable)
  • func (g *InterferenceGraph) Interfere(x, y ast.Variable) bool
• type LiveSet
  • func NewLiveSet() LiveSet
  • func (l LiveSet) MarkLive(vs ...ast.Variable)
  • func (l LiveSet) Update(a ast.Assignment)

Functions

func AliasCorrect

func AliasCorrect(p *ast.Program, aliases [][]ast.Variable, outputs []ast.Variable, vars name.UniqueSequence) *ast.Program

AliasCorrect ensures that the program p will compute the same result if the given variables are aliased. Aliased variables are pointers to the same memory location. If the program is already robust to the given alias sets, no changes will be made. Otherwise the program will be modified with additional temporaries.

func InputSet

func InputSet(p *ast.Program) map[ast.Variable]bool

InputSet returns the set of input variables for the given program.

func Inputs

func Inputs(p *ast.Program) []ast.Variable

Inputs returns input variables for the given program.

func IsPrimitive

func IsPrimitive(p *ast.Program) bool

IsPrimitive reports whether p consists of only primitive operations.

func IsPrimitiveExpression

func IsPrimitiveExpression(expr ast.Expression) bool

IsPrimitiveExpression reports whether expr is a primitive operation. By "primitive", we mean that the operation directly translates to an efficient field operation.

1. Powers other than square are not considered primitive. They must be decomposed into multiplies and squares.

2. Constant multiplies are not primitive. Although they could be executed as multiplies, they are typically best replaced with additions.

func IsSSA

func IsSSA(p *ast.Program) bool

IsSSA reports whether every variable is written once.

func Lower

func Lower(p *ast.Program) (*ast.Program, error)

Lower p to primitive expressions.

func Pare

func Pare(p *ast.Program, outputs []ast.Variable) (*ast.Program, error)

Pare down the given program to only the operations required to produce given outputs.

func ReadOnly

func ReadOnly(p *ast.Program, v ast.Variable) bool

ReadOnly reports whether v is a read-only variable in the program p.

func RenameVariables

func RenameVariables(p *ast.Program, replacements map[ast.Variable]ast.Variable) *ast.Program

RenameVariables applies the given variable replacements to the program p.

func SortedVariables

func SortedVariables(vs []ast.Variable) []ast.Variable

SortedVariables returns the variables vs sorted in string order.

func VariableSet

func VariableSet(vs []ast.Variable) map[ast.Variable]bool

VariableSet builds a set from a list of variables.

func Variables

func Variables(p *ast.Program) []ast.Variable

Variables returns all variables used in the program.

Types

type InterferenceGraph

type InterferenceGraph struct {
	// contains filtered or unexported fields
}

InterferenceGraph records which variables interfere with each other.

func BuildInterferenceGraph

func BuildInterferenceGraph(p *ast.Program, outputs []ast.Variable) *InterferenceGraph

BuildInterferenceGraph builds the interference graph for variables in p, given that the provided outputs are required.

func NewInterferenceGraph

func NewInterferenceGraph() *InterferenceGraph

NewInterferenceGraph builds an empty interference graph.

func (*InterferenceGraph) AddInterference

func (g *InterferenceGraph) AddInterference(x, y ast.Variable)

AddInterference records that x and y interfere.

func (*InterferenceGraph) Interfere

func (g *InterferenceGraph) Interfere(x, y ast.Variable) bool

Interfere reports whether x and y interfere.

type LiveSet

type LiveSet map[ast.Variable]bool

LiveSet maintains a set of live variables.

func NewLiveSet

func NewLiveSet() LiveSet

NewLiveSet constructs an empty set of live variables.

func (LiveSet) MarkLive

func (l LiveSet) MarkLive(vs ...ast.Variable)

MarkLive records all variables in vs as live.

func (LiveSet) Update

func (l LiveSet) Update(a ast.Assignment)

Update the live set based on the assignment. In liveness analysis, program assignments should be processed in reverse.