dependencygraph2

package
v1.7.0-dev-20191004 Latest Latest
Warning

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

Go to latest
Published: Oct 3, 2019 License: Apache-2.0 Imports: 19 Imported by: 21

Documentation

Index

Constants

View Source
const NodeNoID = NodeID(math.MaxUint32)

Variables

This section is empty.

Functions

func DCECapture

func DCECapture(ctx context.Context, name string, p *path.Capture, requestedCmds []*path.Command) (*path.Capture, error)

DCECapture returns a new capture containing only the requested commands and their dependencies.

func NewForwardWatcher added in v1.3.1

func NewForwardWatcher() *forwardWatcher

func NewFragWatcher added in v1.3.1

func NewFragWatcher() *fragWatcher

func NewGraphBuilder added in v1.3.1

func NewGraphBuilder(ctx context.Context, config DependencyGraphConfig,
	c *capture.GraphicsCapture, initialCmds []api.Cmd, state *api.GlobalState) *graphBuilder

func NewMemWatcher added in v1.3.1

func NewMemWatcher() *memWatcher

Types

type AccessMode added in v1.3.1

type AccessMode uint
const (
	ACCESS_READ       AccessMode = 1 << 0
	ACCESS_WRITE      AccessMode = 1 << 1
	ACCESS_READ_WRITE AccessMode = ACCESS_READ | ACCESS_WRITE
)

type Accesses

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

type CloseForwardDependencyEffect

type CloseForwardDependencyEffect struct {
	NodeID       NodeID
	DependencyID interface{}
}

CloseForwardDependencyEffect is a record of the *closing* of a forward dependency. See OpenForwardDependencyEffect above.

func (CloseForwardDependencyEffect) GetNodeID

func (e CloseForwardDependencyEffect) GetNodeID() NodeID

GetNodeID returns the dependency graph node associated with this effect

type CmdContext added in v1.3.1

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

type CmdNode

type CmdNode struct {
	Index    api.SubCmdIdx
	CmdFlags api.CmdFlags
}

CmdNode is a dependency node corresponding to an API call

type DCEBuilder

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

DCEBuilder tracks the data necessary to perform dead-command-eliminition on a capture

func NewDCEBuilder

func NewDCEBuilder(graph DependencyGraph) *DCEBuilder

NewDCEBuilder creates a new DCEBuiler using the specified dependency graph

func (*DCEBuilder) Build

func (b *DCEBuilder) Build(ctx context.Context) error

Build runs the dead-code-elimination. The subcommands specified in cmds are marked alive, along with their transitive dependencies.

func (*DCEBuilder) Flush

func (b *DCEBuilder) Flush(ctx context.Context, out transform.Writer)

Flush is to comform the interface of Transformer. Flush performs DCE, and sends the live commands to the writer

func (*DCEBuilder) LiveCmdID

func (b *DCEBuilder) LiveCmdID(oldCmdID api.CmdID) api.CmdID

LiveCmdID maps CmdIDs from the original capture to CmdIDs in within the live commands. If the old CmdID refers to a dead command, the returned command will refer to the next live command; if there is no next live command, api.CmdNoID is returned.

func (*DCEBuilder) LiveCmds

func (b *DCEBuilder) LiveCmds() []api.Cmd

LiveCmds returns the live commands

func (*DCEBuilder) LogStats

func (b *DCEBuilder) LogStats(ctx context.Context)

func (*DCEBuilder) NumLiveInitCmds

func (b *DCEBuilder) NumLiveInitCmds() int

NumLiveInitiCmds returns the number of live commands which are initial commands. (Initial commands are generated commands to recreate the initial state).

func (*DCEBuilder) OriginalCmdID

func (b *DCEBuilder) OriginalCmdID(liveCmdID api.CmdID) api.CmdID

OriginalCmdIDs maps a live CmdID to the CmdID of the corresponding command in the original capture

func (*DCEBuilder) PostLoop

func (b *DCEBuilder) PostLoop(ctx context.Context, out transform.Writer)

func (*DCEBuilder) PreLoop

func (b *DCEBuilder) PreLoop(ctx context.Context, out transform.Writer)

func (*DCEBuilder) Request

func (b *DCEBuilder) Request(ctx context.Context, fci api.SubCmdIdx) error

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

func (*DCEBuilder) Transform

func (*DCEBuilder) 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 DependencyGraph

type DependencyGraph interface {

	// NumNodes returns the number of nodes in the graph
	NumNodes() int

	// NumDependencies returns the number of dependencies (edges) in the graph
	NumDependencies() uint64

	// GetNode returns the node data associated with the given NodeID
	GetNode(NodeID) Node

	// GetNodeID returns the NodeID associated with given node data
	GetCmdNodeID(api.CmdID, api.SubCmdIdx) NodeID

	// GetCmdAncestorNodeIDs returns the NodeIDs associated with the ancestors of the
	// given subcommand.
	GetCmdAncestorNodeIDs(api.CmdID, api.SubCmdIdx) []NodeID

	// ForeachCmd iterates over all API calls in the graph.
	// If IncludeInitialCommands is true, this includes the initial commands
	// which reconstruct the initial state.
	// CmdIDs for initial commands are:
	//   CmdID(0).Derived(), CmdID(1).Derived(), ...
	// Whether or not IncludeInitialCommands is true, the CmdIDs for captured
	// commands are: 0, 1, 2, ...
	ForeachCmd(ctx context.Context,
		cb func(context.Context, api.CmdID, api.Cmd) error) error

	// ForeachNode iterates over all nodes in the graph in chronological order.
	// I.e., the following order:
	//   * For each initial command
	//     * Read observation nodes for this command
	//     * command node
	//     * Write observation nodes for this command
	//   * For each (non-initial) command
	//     * Read observation nodes for this command
	//     * command node
	//     * Write observation nodes for this command
	ForeachNode(cb func(NodeID, Node) error) error

	// ForeachDependency iterates over all pairs (src, tgt), where src depends on tgt
	ForeachDependency(cb func(NodeID, NodeID) error) error

	// ForeachDependencyFrom iterates over all the nodes tgt, where src depends on tgt
	ForeachDependencyFrom(src NodeID, cb func(NodeID) error) error

	// ForeachDependencyTo iterates over all the nodes src, where src depends on tgt.
	// If Config().ReverseDependencies is false, this will return an error.
	ForeachDependencyTo(tgt NodeID, cb func(NodeID) error) error

	// Capture returns the capture whose dependencies are stored in this graph
	Capture() *capture.GraphicsCapture

	// GetUnopenedForwardDependencies returns the commands that have dependencies that
	// are not part of the capture.
	GetUnopenedForwardDependencies() []api.CmdID

	// GetCommand returns the command identified by the given CmdID
	GetCommand(api.CmdID) api.Cmd

	// NumInitialCommands returns the number of initial commands
	// (the commands needed to reconstruct the initial state before the
	// first command in the capture)
	NumInitialCommands() int

	GetNodeAccesses(NodeID) NodeAccesses

	// Config returns the config used to create this graph
	Config() DependencyGraphConfig
}

DependencyGraph stores the dependencies among api calls and memory observations,

func BuildDependencyGraph

func BuildDependencyGraph(ctx context.Context, config DependencyGraphConfig,
	c *capture.GraphicsCapture, initialCmds []api.Cmd, initialRanges interval.U64RangeList) (DependencyGraph, error)

func GetDependencyGraph

func GetDependencyGraph(ctx context.Context, c *path.Capture, config DependencyGraphConfig) (DependencyGraph, error)

func TryGetDependencyGraph added in v1.3.1

func TryGetDependencyGraph(ctx context.Context, c *path.Capture, config DependencyGraphConfig) (DependencyGraph, error)

type DependencyGraphConfig

type DependencyGraphConfig struct {
	// MergeSubCmdNodes indicates whether the graph should have one node per
	// command (true), or a separate node for each subcommand (false)
	MergeSubCmdNodes bool

	// IncludeInitialCommands indicates whether nodes should be created for
	// the initial (state rebuild) commands
	IncludeInitialCommands bool

	// ReverseDependencies indicates whether reverse edges should be created
	ReverseDependencies bool

	SaveNodeAccesses bool
}

Information about what sort of data to store in a dependency graph

type Distribution added in v1.3.1

type Distribution struct {
	SmallBins []uint64
	LargeBins map[uint64]uint64
}

func (Distribution) Add added in v1.3.1

func (d Distribution) Add(x uint64)

type Effect

type Effect interface {
	// GetNodeID returns the dependency graph node associated with this effect
	GetNodeID() NodeID
	// contains filtered or unexported methods
}

Effect is a record of a read or write of a piece of state.

type ForwardAccess added in v1.3.1

type ForwardAccess struct {
	Nodes        *ForwardNodes
	DependencyID interface{}
	Mode         ForwardAccessMode
}

type ForwardAccessMode added in v1.3.1

type ForwardAccessMode uint
const (
	FORWARD_OPEN ForwardAccessMode = iota + 1
	FORWARD_CLOSE
	FORWARD_DROP
)

type ForwardNodes added in v1.3.1

type ForwardNodes struct {
	Open  NodeID
	Close NodeID
	Drop  NodeID
}

type ForwardWatcher added in v1.3.1

type ForwardWatcher interface {
	OpenForwardDependency(ctx context.Context, cmdCtx CmdContext, dependencyID interface{})
	CloseForwardDependency(ctx context.Context, cmdCtx CmdContext, dependencyID interface{})
	DropForwardDependency(ctx context.Context, cmdCtx CmdContext, dependencyID interface{})
	OnBeginCmd(ctx context.Context, cmdCtx CmdContext)
	OnEndCmd(ctx context.Context, cmdCtx CmdContext) Accesses
	OnBeginSubCmd(ctx context.Context, cmdCtx CmdContext, subCmdCtx CmdContext)
	OnEndSubCmd(ctx context.Context, cmdCtx CmdContext)
}

type FragWatcher added in v1.3.1

type FragWatcher interface {
	OnReadFrag(ctx context.Context, cmdCtx CmdContext, owner api.RefObject, f api.Fragment, v api.RefObject, track bool)
	OnWriteFrag(ctx context.Context, cmdCtx CmdContext, owner api.RefObject, f api.Fragment, old api.RefObject, new api.RefObject, track bool)
	OnBeginCmd(ctx context.Context, cmdCtx CmdContext)
	OnEndCmd(ctx context.Context, cmdCtx CmdContext) map[NodeID][]FragmentAccess
	OnBeginSubCmd(ctx context.Context, cmdCtx CmdContext, subCmdCtx CmdContext)
	OnEndSubCmd(ctx context.Context, cmdCtx CmdContext)
	GetStateRefs() map[api.RefID]RefFrag
}

type FragmentAccess added in v1.3.1

type FragmentAccess struct {
	Node     NodeID
	Ref      api.RefID
	Fragment api.Fragment
	Mode     AccessMode
	Deps     []NodeID
}

type FragmentEffect

type FragmentEffect interface {
	Effect
	// GetFragment returns the Fragment which is read or written by this effect
	GetFragment() api.Fragment
}

type GraphBuilder added in v1.3.1

type GraphBuilder interface {
	AddDependencies(context.Context,
		map[NodeID][]FragmentAccess,
		map[NodeID][]MemoryAccess,
		map[NodeID][]ForwardAccess,
		bool)
	BuildReverseDependencies()
	GetCmdNodeID(api.CmdID, api.SubCmdIdx) NodeID
	GetOrCreateCmdNodeID(context.Context, api.CmdID, api.SubCmdIdx, api.Cmd) NodeID
	GetObsNodeIDs(api.CmdID, []api.CmdObservation, bool) []NodeID
	GetCmdContext(context.Context, api.CmdID, api.Cmd) CmdContext
	GetSubCmdContext(api.CmdID, api.SubCmdIdx) CmdContext
	GetNodeStats(NodeID) *NodeStats
	GetStats() *GraphBuilderStats
	GetGraph() *dependencyGraph
	OnBeginCmd(ctx context.Context, cmdCtx CmdContext)
	OnBeginSubCmd(ctx context.Context, cmdCtx CmdContext, subCmdCtx CmdContext, recordIdx api.RecordIdx)
	OnRecordSubCmd(ctx context.Context, cmdCtx CmdContext, recordIdx api.RecordIdx)
}

type GraphBuilderStats added in v1.3.1

type GraphBuilderStats struct {
	UniqueFragReads     uint64
	UniqueFragWrites    uint64
	UniqueMemReads      uint64
	UniqueMemWrites     uint64
	UniqueDeps          uint64
	NumDeps             uint64
	NumFragDeps         uint64
	NumCompleteFragDeps uint64
	NumMemDeps          uint64
	NumCmdNodes         uint64
	NumObsNodes         uint64
	DepDist             Distribution
}

type MemWatcher added in v1.3.1

type MemWatcher interface {
	OnWriteSlice(ctx context.Context, cmdCtx CmdContext, s memory.Slice)
	OnReadSlice(ctx context.Context, cmdCtx CmdContext, s memory.Slice)
	OnWriteObs(ctx context.Context, cmdCtx CmdContext, obs []api.CmdObservation, nodes []NodeID)
	OnReadObs(ctx context.Context, cmdCtx CmdContext, obs []api.CmdObservation, nodes []NodeID)
	OnBeginCmd(ctx context.Context, cmdCtx CmdContext)
	OnEndCmd(ctx context.Context, cmdCtx CmdContext) map[NodeID][]MemoryAccess
	OnBeginSubCmd(ctx context.Context, cmdCtx CmdContext, subCmdCtx CmdContext)
	OnEndSubCmd(ctx context.Context, cmdCtx CmdContext)
}

type MemoryAccess added in v1.3.1

type MemoryAccess struct {
	Node NodeID
	Pool memory.PoolID
	Span interval.U64Span
	Mode AccessMode
	Deps []NodeID
}

type Node

type Node interface {
	// contains filtered or unexported methods
}

Node represents a node in the dependency graph, and holds data about the associated command or memory observation.

type NodeAccesses added in v1.3.1

type NodeAccesses struct {
	FragmentAccesses []FragmentAccess
	MemoryAccesses   []MemoryAccess
	ForwardAccesses  []ForwardAccess
	ParentNode       NodeID
	InitCmdNodes     []NodeID
}

type NodeID

type NodeID uint32

NodeID identifies a node in a dependency graph

type NodeIDSorter

type NodeIDSorter struct {
	Nodes []NodeID
}

NodeIDSorter is a structure to use for sorting NodeIDs in the sort package

func (*NodeIDSorter) Len

func (s *NodeIDSorter) Len() int

Len returns the length of the node list

func (*NodeIDSorter) Less

func (s *NodeIDSorter) Less(i, j int) bool

Less returns trus if the elements at index i are less than j

func (*NodeIDSorter) Swap

func (s *NodeIDSorter) Swap(i, j int)

Swap swaps the locations of 2 nodes in the list

type NodeStats added in v1.3.1

type NodeStats struct {
	NumFragReads        uint64
	NumFragWrites       uint64
	NumMemReads         uint64
	NumMemWrites        uint64
	NumForwardDepOpens  uint64
	NumForwardDepCloses uint64
	NumForwardDepDrops  uint64
	NumDeps             uint64
	NumFragDeps         uint64
	NumCompleteFragDeps uint64
	NumMemDeps          uint64
	UniqueFragReads     uint64
	UniqueFragWrites    uint64
	UniqueMemReads      uint64
	UniqueMemWrites     uint64
	UniqueDeps          uint64
}

type ObsNode

type ObsNode struct {
	CmdObservation api.CmdObservation
	CmdID          api.CmdID
	IsWrite        bool
	Index          int
}

ObsNode is a dependency node corresponding to a memory observation

type OpenForwardDependencyEffect

type OpenForwardDependencyEffect struct {
	NodeID       NodeID
	DependencyID interface{}
}

OpenForwardDependencyEffect is a record of the *opening* of a forward dependency. The opening effect must occur before the corresponding *closing* effect (represented by CloseForwardDependencyEffect); the opening node associated with the opening of the foward dependency will depend on the node associated with the closing. E.g. vkAcquireNextImageKHR opens a foward dependency, which is closed by the corresponding vkQueuePresentKHR call.

func (OpenForwardDependencyEffect) GetNodeID

func (e OpenForwardDependencyEffect) GetNodeID() NodeID

GetNodeID returns the dependency graph node associated with this effect

type ReadEffect

type ReadEffect interface {
	Effect
	// contains filtered or unexported methods
}

ReadEffect is a record of a read of a piece of state.

type ReadFragmentEffect

type ReadFragmentEffect struct {
	NodeID   NodeID
	Fragment api.Fragment
}

ReadFragmentEffect is a record of a read of a piece of state in the state graph (as opposed to a memory range)

func (ReadFragmentEffect) GetFragment

func (e ReadFragmentEffect) GetFragment() api.Fragment

GetFragment returns the Fragment which is read or written by this effect

func (ReadFragmentEffect) GetNodeID

func (e ReadFragmentEffect) GetNodeID() NodeID

GetNodeID returns the dependency graph node associated with this effect

type ReadMemEffect

type ReadMemEffect struct {
	NodeID NodeID
	Slice  memory.Slice
}

ReadMemEffect is a record of a read of a memory range (either application or device memory)

func (ReadMemEffect) GetNodeID

func (e ReadMemEffect) GetNodeID() NodeID

GetNodeID returns the dependency graph node associated with this effect

type RecordNodeTrie added in v1.3.1

type RecordNodeTrie struct {
	api.SubCmdIdxTrie
}

func (*RecordNodeTrie) GetRecordNode added in v1.3.1

func (t *RecordNodeTrie) GetRecordNode(recordIdx api.RecordIdx) NodeID

func (*RecordNodeTrie) SetRecordNode added in v1.3.1

func (t *RecordNodeTrie) SetRecordNode(recordIdx api.RecordIdx, nodeID NodeID)

type RefFrag added in v1.3.1

type RefFrag struct {
	RefID api.RefID
	Frag  api.Fragment
}

type ReverseEffect

type ReverseEffect interface {
	Effect
	// contains filtered or unexported methods
}

ReverseEffect is a record of an effect whose dependency goes in both directions (read <-> write)

type WriteEffect

type WriteEffect interface {
	Effect
	// contains filtered or unexported methods
}

WriteEffect is a record of a write of a piece of state.

type WriteFragmentEffect

type WriteFragmentEffect struct {
	NodeID   NodeID
	Fragment api.Fragment
}

WriteFragmentEffect is a record of a write to a piece of state in the state graph (as opposed to a memory range)

func (WriteFragmentEffect) GetFragment

func (e WriteFragmentEffect) GetFragment() api.Fragment

GetFragment returns the Fragment which is read or written by this effect

func (WriteFragmentEffect) GetNodeID

func (e WriteFragmentEffect) GetNodeID() NodeID

GetNodeID returns the dependency graph node associated with this effect

type WriteMemEffect

type WriteMemEffect struct {
	NodeID NodeID
	Slice  memory.Slice
}

WriteMemEffect is a record of a write to a memory range (either application or device memory)

func (WriteMemEffect) GetNodeID

func (e WriteMemEffect) GetNodeID() NodeID

GetNodeID returns the dependency graph node associated with this effect

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL