dependencygraph

package
v1.2.1 Latest Latest
Warning

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

 Go to latest Published: Nov 8, 2018 License: Apache-2.0 Imports: 13 Imported by: 2

Documentation

Index

Constants

View Source 
const NotInFootprint = uint64(0xFFFFFFFFFFFFFFFF)
View Source 
const NullStateAddress = StateAddress(0)

Variables

This section is empty.

Functions

This section is empty.

Types

type Behavior added in v0.6.0 

type Behavior struct {
	Index     uint64
	DependsOn map[*Behavior]struct{}
	Owner     api.SubCmdIdx
	Alive     bool
	Aborted   bool
}

Behavior contains a set of read and write operations as side effect of executing the command to whom it belongs. Behavior also contains a reference to the back-propagation machine which should be used to process the Behavior to determine its liveness for dead code elimination.

func NewBehavior added in v0.6.0 

func NewBehavior(fullCommandIndex api.SubCmdIdx) *Behavior

NewBehavior creates a new Behavior which belongs to the command indexed by the given SubCmdIdx. Returns a pointer to the created Behavior.

func (*Behavior) Modify added in v0.6.0 

func (b *Behavior) Modify(c DefUseVariable)

Modify records a read and a write operation of the given DefUseVariable to the Behavior

func (*Behavior) Read added in v0.6.0 

func (b *Behavior) Read(c DefUseVariable)

Read records a dependency that the current Behavior depends on the behavior which writes to the given DefUseVariable fore.

func (*Behavior) Write added in v0.6.0 

func (b *Behavior) Write(c DefUseVariable)

Write labels the given DefUseVariable written by the Behavior

type BehaviourProvider 

type BehaviourProvider interface {
	GetBehaviourForCommand(context.Context, *api.GlobalState, api.CmdID, api.Cmd, *DependencyGraph) CmdBehaviour
}

type CmdBehaviour added in v1.2.0 

type CmdBehaviour struct {
	Reads     []StateAddress // States read by a command.
	Modifies  []StateAddress // States read and written by a command.
	Writes    []StateAddress // States written by a command.
	Roots     []StateAddress // States labeled as root by a command.
	KeepAlive bool           // Force the command to be live.
	Aborted   bool           // Mutation of this command aborts.
}

func (*CmdBehaviour) Modify added in v1.2.0 

func (b *CmdBehaviour) Modify(g *DependencyGraph, state StateKey)

func (*CmdBehaviour) Read added in v1.2.0 

func (b *CmdBehaviour) Read(g *DependencyGraph, state StateKey)

func (*CmdBehaviour) Write added in v1.2.0 

func (b *CmdBehaviour) Write(g *DependencyGraph, state StateKey)

type CommandIndicesSet added in v1.2.0 

type CommandIndicesSet struct {
	api.SubCmdIdxTrie
	// contains filtered or unexported fields
}

CommandIndicesSet holds a set of unique command indices.

func (*CommandIndicesSet) Contains added in v1.2.0 

func (s *CommandIndicesSet) Contains(fci api.SubCmdIdx) bool

Contains returns true if fci is part of the set.

func (*CommandIndicesSet) Insert added in v1.2.0 

func (s *CommandIndicesSet) Insert(fci api.SubCmdIdx)

Insert adds the command index fci to the set.

type DCE added in v1.2.0 

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

DCE Contains an execution footprint built from a list of commands, and a list of requested command indices. It drives the back-propagation to drop commands which are not contributing to the final state at the requested commands.

func NewDCE added in v1.2.0 

func NewDCE(ctx context.Context, footprint *Footprint) *DCE

NewDCE constructs a new DCE instance and returns a pointer to the created DCE instance.

func (*DCE) BackPropagate added in v1.2.0 

func (t *DCE) BackPropagate(ctx context.Context) ([]bool, *CommandIndicesSet)

BackPropagate calculates and returns the liveness of the commands using back propagation. BackPropagate is automatically called by Flush() and is only public so it can be tested.

func (*DCE) Flush added in v1.2.0 

func (t *DCE) Flush(ctx context.Context, out transform.Writer)

Flush is to comform the interface of Transformer. Flush starts the back propagation of the behaviors recorded in the footprint from the last requested command (the one with largest SubCmdIdx, not the one added the last in the order of time) to get a list of alive commands. Then it sends the alive commands to the following transforms to mutate them and write them to build instructions for replay.

func (*DCE) Request added in v1.2.0 

func (t *DCE) Request(ctx context.Context, fci api.SubCmdIdx)

Request added a requsted command or subcommand, represented by its full command index, to the DCE.

func (*DCE) Transform added in v1.2.0 

func (t *DCE) Transform(ctx context.Context, id api.CmdID, c api.Cmd,
	out transform.Writer)

Transform is to comform the interface of Transformer, but does not accept any input.

type DeadCodeElimination added in v1.2.0 

type DeadCodeElimination struct {
	KeepAllAlive bool
	// contains filtered or unexported fields
}

DeadCodeElimination is an implementation of Transformer that outputs live commands. That is, all commands which do not affect the requested output are omitted. It is named after the standard compiler optimization. (state is like memory and commands are instructions which read/write it). Construct with NewDeadCodeElimination, do not build directly.

func NewDeadCodeElimination added in v1.2.0 

func NewDeadCodeElimination(ctx context.Context, depGraph *DependencyGraph) *DeadCodeElimination

NewDeadCodeElimination constructs and returns a new DeadCodeElimination transform.

The transform generates commands from the given depGraph, it does not take inputs.

func (*DeadCodeElimination) Flush added in v1.2.0 

func (t *DeadCodeElimination) Flush(ctx context.Context, out transform.Writer)

func (*DeadCodeElimination) Request added in v1.2.0 

func (t *DeadCodeElimination) Request(id api.CmdID)

Request ensures that we keep alive all commands needed to render framebuffer at the given point.

func (*DeadCodeElimination) Transform added in v1.2.0 

func (t *DeadCodeElimination) Transform(ctx context.Context, id api.CmdID, c api.Cmd, out transform.Writer)

type DefUseVariable added in v0.6.0 

type DefUseVariable interface {
	GetDefBehavior() *Behavior
	SetDefBehavior(*Behavior)
}

DefUseVariable is a tag to data that should be considered as the logical representation of a variable in liveness analysis(https://en.wikipedia.org/wiki/Live_variable_analysis). All sorts data to be tracked in the def-use chain(https://en.wikipedia.org/wiki/Use-define_chain), which is to be used for the liveness analysis, should be tagged as DefUseVariable. In the context of GAPID, any pieces of the whole API state can be tagged as DefUseVariable, e.g. a piece of memory, a handle, an object state, etc. Each DefUseVariable can be defined by a behavior. To set and get the defining behavior, SetDefBehavior() and GetDefBehavior() can be used.

type DependencyGraph 

type DependencyGraph struct {
	// Number of generated commands in 'Commands' which build the initial state.
	NumInitialCommands int

	Commands   []api.Cmd             // Command list which this graph was build for.
	Behaviours []CmdBehaviour        // State reads/writes for each command (graph edges).
	Roots      map[StateAddress]bool // State to mark live at requested commands.
	// contains filtered or unexported fields
}

func GetDependencyGraph 

func GetDependencyGraph(ctx context.Context, device *path.Device) (*DependencyGraph, error)

func (*DependencyGraph) GetCmdID added in v0.9.6 

func (g *DependencyGraph) GetCmdID(cmdIndex int) api.CmdID

GetCmdID returns the CmdID for given element in the Commands slice.

func (*DependencyGraph) GetHierarchyStateMap 

func (g *DependencyGraph) GetHierarchyStateMap() map[StateAddress]StateAddress

func (*DependencyGraph) GetStateAddressOf 

func (g *DependencyGraph) GetStateAddressOf(key StateKey) StateAddress

func (*DependencyGraph) Print 

func (g *DependencyGraph) Print(ctx context.Context, b *CmdBehaviour)

func (*DependencyGraph) SetRoot 

func (g *DependencyGraph) SetRoot(key StateKey)

type DependencyGraphBehaviourProvider 

type DependencyGraphBehaviourProvider interface {
	GetDependencyGraphBehaviourProvider(ctx context.Context) BehaviourProvider
}

type Footprint added in v0.6.0 

type Footprint struct {
	Commands           []api.Cmd
	NumInitialCommands int
	Behaviors          []*Behavior
	// contains filtered or unexported fields
}

Footprint contains a list of command and a list of Behaviors which describes the side effect of executing the commands in that list.

func GetFootprint added in v0.6.0 

func GetFootprint(ctx context.Context, c *path.Capture) (*Footprint, error)

GetFootprint returns a pointer to the resolved Footprint.

func NewEmptyFootprint added in v0.6.0 

func NewEmptyFootprint(ctx context.Context) *Footprint

NewEmptyFootprint creates a new Footprint with an empty command list, and returns a pointer to that Footprint.

func NewFootprint added in v0.6.0 

func NewFootprint(ctx context.Context, cmds []api.Cmd, numInitialCommands int) *Footprint

NewFootprint takes a list of commands and creates a new Footprint with that list of commands, and returns a pointer to that Footprint.

func (*Footprint) AddBehavior added in v0.6.0 

func (f *Footprint) AddBehavior(ctx context.Context, b *Behavior) bool

AddBehavior adds the given Behavior to the Footprint and updates the internal mapping from SubCmdIdx to the last Behavior that belongs to that command or subcommand.

func (*Footprint) BehaviorIndex added in v0.6.0 

func (f *Footprint) BehaviorIndex(ctx context.Context,
	fci api.SubCmdIdx) uint64

BehaviorIndex returns the index of the last Behavior in the Footprint which belongs to the command or subcomand indexed by the given SubCmdIdx. In case the SubCmdIdx is invalid or a valid Behavior index is not found, error will be logged and uint64(0) will be returned.

type FootprintBuilder added in v0.6.0 

type FootprintBuilder interface {
	BuildFootprint(context.Context, *api.GlobalState, *Footprint, api.CmdID, api.Cmd)
}

FootprintBuilder incrementally builds Footprint one command by one command.

type FootprintBuilderProvider added in v0.6.0 

type FootprintBuilderProvider interface {
	FootprintBuilder(context.Context) FootprintBuilder
}

FootprintBuilderProvider provides FootprintBuilder

type LivenessTree added in v1.2.0 

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

LivenessTree assigns boolean value to each state (live or dead). Think of each node as memory range, with children being sub-ranges.

func NewLivenessTree added in v1.2.0 

func NewLivenessTree(parents map[StateAddress]StateAddress) LivenessTree

NewLivenessTree creates a new tree. The parent map defines parent for each node, and it must be continuous with no gaps.

func (*LivenessTree) IsLive added in v1.2.0 

func (l *LivenessTree) IsLive(address StateAddress) bool

IsLive returns true if the state, or any of its descendants, are live.

func (*LivenessTree) MarkDead added in v1.2.0 

func (l *LivenessTree) MarkDead(address StateAddress)

MarkDead makes the given state, and all of its descendants, dead.

func (*LivenessTree) MarkLive added in v1.2.0 

func (l *LivenessTree) MarkLive(address StateAddress)

MarkLive makes the given state, and all of its descendants, live.

type StateAddress 

type StateAddress uint32

type StateKey 

type StateKey interface {
	// Parent returns enclosing state (and this state is strict subset of it).
	// This allows efficient implementation of operations which access a lot state.
	Parent() StateKey
}

StateKey uniquely represents part of the GL state. Think of it as memory range (which stores the state data).

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.