dependencygraph

Documentation

Index

• Constants
• type AtomBehaviour
  • func (b *AtomBehaviour) Modify(g *DependencyGraph, state StateKey)
  • func (b *AtomBehaviour) Read(g *DependencyGraph, state StateKey)
  • func (b *AtomBehaviour) Write(g *DependencyGraph, state StateKey)
• type BackPropagationMachine
• type Behavior
  • func NewBehavior(fullCommandIndex api.SubCmdIdx, m BackPropagationMachine) *Behavior
  • func (b *Behavior) Modify(c DefUseVariable)
  • func (b *Behavior) Read(c DefUseVariable)
  • func (b *Behavior) Write(c DefUseVariable)
• type BehaviourProvider
• type DefUseVariable
• type DependencyGraph
  • func GetDependencyGraph(ctx context.Context) (*DependencyGraph, error)
  • func (g *DependencyGraph) GetCmdID(cmdIndex int) api.CmdID
  • func (g *DependencyGraph) GetHierarchyStateMap() map[StateAddress]StateAddress
  • func (g *DependencyGraph) GetStateAddressOf(key StateKey) StateAddress
  • func (g *DependencyGraph) Print(ctx context.Context, b *AtomBehaviour)
  • func (g *DependencyGraph) SetRoot(key StateKey)
• type DependencyGraphBehaviourProvider
• type Footprint
  • func GetFootprint(ctx context.Context) (*Footprint, error)
  • func NewEmptyFootprint(ctx context.Context) *Footprint
  • func NewFootprint(ctx context.Context, cmds []api.Cmd) *Footprint
  • func (f *Footprint) AddBehavior(ctx context.Context, b *Behavior) bool
  • func (f *Footprint) BehaviorIndex(ctx context.Context, fci api.SubCmdIdx) uint64
• type FootprintBuilder
• type FootprintBuilderProvider
• type StateAddress
• type StateKey

Constants

const NullStateAddress = StateAddress(0)

Types

type AtomBehaviour

type AtomBehaviour 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 (*AtomBehaviour) Modify

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

func (*AtomBehaviour) Read

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

func (*AtomBehaviour) Write

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

type BackPropagationMachine

type BackPropagationMachine interface {
	// IsAlive checks whether a given behavior, which is specified by its index
	// and the footprint to which it belongs, should be kept alive. It should
	// takes the written DefUseVariable of the given behavior, check every of
	// them with its internal state to determine the liveness of the Behavior.
	// Returns true if the behavior should be kept alive, otherwise returns
	// false.
	IsAlive(behaviorIndex uint64, ft *Footprint) bool
	// RecordBehaviorEffects records the read/write operations of the given
	// behavior specified by its index in the given footprint, and returns the
	// indices of the alive behaviors that should be kept alive due to recording
	// of the given behavior.
	RecordBehaviorEffects(behaviorIndex uint64, ft *Footprint) []uint64
	// Clear clears the internal state of the BackPropagationMachine.
	Clear()
	// FramebufferRequest finds the framebuffer data at the given command index
	// and records a read to the framebuffer data, so the dependencies of the
	// data will be kept alive for backpropagation.
	FramebufferRequest(id api.CmdID, ft *Footprint)
}

BackPropagationMachine determines the liveness of Behaviors along the back propagation of the operations recorded in Footprint's Behaviors.

type Behavior

type Behavior struct {
	Reads   []DefUseVariable
	Writes  []DefUseVariable
	Owner   api.SubCmdIdx
	Alive   bool
	Aborted bool
	Machine BackPropagationMachine
}

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

func NewBehavior(fullCommandIndex api.SubCmdIdx, m BackPropagationMachine) *Behavior

NewBehavior creates a new Behavior which belongs to the command indexed by the given SubCmdIdx and shall be process by the given back-propagation machine. Returns a pointer to the created Behavior.

func (*Behavior) Modify

func (b *Behavior) Modify(c DefUseVariable)

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

func (*Behavior) Read

func (b *Behavior) Read(c DefUseVariable)

Read records a read operation of the given DefUseVariable to the Behavior

func (*Behavior) Write

func (b *Behavior) Write(c DefUseVariable)

Write records a write operation of the given DefUseVariable to the Behavior

type BehaviourProvider

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

type DefUseVariable

type DefUseVariable interface {
	DefUseVariable()
}

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. But eventually those DefUseVariables wiil be handed in the BackPropagationMachine, which is referred in the Behavior that records read or write operations of the DefUseVariables. So the corresponding BackPropagationMachine must be able to handle the concrete type of those DefUseVariables.

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 []AtomBehaviour       // 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) (*DependencyGraph, error)

func (*DependencyGraph) GetCmdID

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 *AtomBehaviour)

func (*DependencyGraph) SetRoot

func (g *DependencyGraph) SetRoot(key StateKey)

type DependencyGraphBehaviourProvider

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

type Footprint

type Footprint struct {
	Commands        []api.Cmd
	Behaviors       []*Behavior
	BehaviorIndices map[*Behavior]uint64
	// 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

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

GetFootprint returns a pointer to the resolved Footprint.

func NewEmptyFootprint

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

func NewFootprint(ctx context.Context, cmds []api.Cmd) *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

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

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

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

FootprintBuilder incrementally builds Footprint one command by one command.

type FootprintBuilderProvider

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

FootprintBuilderProvider provides FootprintBuilder

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).