dfa

package
v1.2.23 Latest Latest
Warning

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

 Go to latest Published: Jul 22, 2026 License: Apache-2.0 Imports: 7 Imported by: 0

Documentation

Overview

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Branch 

type Branch struct {
	Condition BranchCondition
}

Branch adapts a branch condition to be an instance of State.

func (Branch) Join 

func (p Branch) Join(st Branch) Branch

Join implementation for State interface

func (Branch) String 

func (p Branch) String(mapping register.Map) string

String implementation for State interface

type BranchCondition 

type BranchCondition = logical.Proposition[BranchId, BranchEquality]

BranchCondition abstracts the possible conditions under which a given branch is taken. 

var FALSE BranchCondition = logical.Truth[BranchId, BranchEquality](false)

FALSE represents an unreachable path 

var TRUE BranchCondition = logical.Truth[BranchId, BranchEquality](true)

TRUE represents an path which is always reached

type BranchConjunction 

type BranchConjunction = logical.Conjunction[BranchId, BranchEquality]

BranchConjunction represents the conjunction of two paths

type BranchEquality 

type BranchEquality = logical.Equality[BranchId]

BranchEquality represents an atomic branch equality

type BranchId 

type BranchId struct {
	// First underlying register in group
	Id register.Id
	// Number of registers in group
	Width uint
	// Indication of whether Forwarding is active or not.
	Forwarding bool
}

BranchId represents a set of one or more registers which can additionally indicate whether forwarding is active or not. Forwarding indicates that the register(s) were previously assigned in the given instruction and, hence, need to be "forwarded" to the point where they are used.

func NewBranchId 

func NewBranchId(forwarding bool, regs ...register.Id) BranchId

NewBranchId constructs a new branch id from a group of one (or more) consecutively assigned registers.

func (BranchId) Cmp 

func (p BranchId) Cmp(o BranchId) int

Cmp implementation of the logical.Variable interface

func (BranchId) Get 

func (p BranchId) Get(i uint) BranchId

Get the ith id in this group as a (singleton) group.

func (BranchId) Registers 

func (p BranchId) Registers() []register.Id

Registers returns the set of registers in this group.

func (BranchId) String 

func (p BranchId) String() string

String implementation of the logical.Variable interface

type BranchTransferFunction 

type BranchTransferFunction[I any] func(offset uint, code I, state Branch) []Transfer[Branch]

BranchTransferFunction represents a transfer function over branch state.

type Path added in v1.2.22 

type Path[W util.BigInter] struct {
	// contains filtered or unexported fields
}

Path adapts a branch condition to be an instance of State.

func EntryPoint added in v1.2.22 

func EntryPoint[W util.BigInter]() Path[W]

EntryPoint constructs a path representing the entry point of a function.

func (Path[W]) Condition added in v1.2.22 

func (p Path[W]) Condition() BranchCondition

Condition returns the underlying branch condition

func (Path[W]) Equals added in v1.2.22 

func (p Path[W]) Equals(lhs, rhs BranchId) Path[W]

Equals extends the current path with a new constraint that two variables are equal.

func (Path[W]) EqualsConst added in v1.2.22 

func (p Path[W]) EqualsConst(lhs BranchId, rhs W) Path[W]

EqualsConst extends the current path with a new constraint that a given variable equals a given constant.

func (Path[W]) Join added in v1.2.22 

func (p Path[W]) Join(st Path[W]) Path[W]

Join implementation for State interface

func (Path[W]) NotEquals added in v1.2.22 

func (p Path[W]) NotEquals(lhs, rhs BranchId) Path[W]

NotEquals extends the current path with a new constraint that two variables are not equal.

func (Path[W]) NotEqualsConst added in v1.2.22 

func (p Path[W]) NotEqualsConst(lhs BranchId, rhs W) Path[W]

NotEqualsConst extends the current path with a new constraint that a given variable does not equal a given constant.

func (Path[W]) String added in v1.2.22 

func (p Path[W]) String(mapping register.Map) string

String implementation for State interface

type PathTransferFunction added in v1.2.22 

type PathTransferFunction[W util.BigInter, I any] func(offset uint, code I, state Path[W]) []Transfer[Path[W]]

PathTransferFunction represents a transfer function over branch state.

type Result 

type Result[T State[T]] struct {
	// contains filtered or unexported fields
}

Result provides a mapping from micro-codes to dfa states. In essence, it represents the output of the flow analysis.

func Construct 

func Construct[T State[T], C any](initial T, codes []C, transfer func(uint, C, T) []Transfer[T]) Result[T]

Construct performs the data-flow analysis over a given kind of state using a given transfer function, producing some results.

func (*Result[T]) JoinInto 

func (p *Result[T]) JoinInto(i uint, st T)

JoinInto updates the write state for a given micro-code to include that from another branch.

func (*Result[T]) StateOf 

func (p *Result[T]) StateOf(i uint) T

StateOf returns the current state on entry to the given micro-code.

func (*Result[T]) String 

func (p *Result[T]) String(rmap register.Map) string

type State 

type State[T any] interface {
	// String representation (primarily used for debugging)
	String(register.Map) string
	// Join combines two states together to produce a state representing both.
	// Typically, this happens when two paths converge on the same location and
	// the states from them are combined.
	Join(other T) T
}

State represents an abstract data-flow state. The purpose of doing this is to simplify the construction of different data-flow analyses over micro instructions.

type Transfer 

type Transfer[T any] struct {
	// contains filtered or unexported fields
}

Transfer is essentially a pair identifying where a given state should be propagated during a dataflow analysis.

func NewTransfer 

func NewTransfer[T any](state T, target uint) Transfer[T]

NewTransfer constructs a new transfer arc to join a given state into a given target.

type Writes 

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

Writes identifies, for a set of registers, whether each may have been written (i.e. maybe assigned) and, furthermore, whether it has definitely been written (i.e. definitely assigned). Observe that definitely assigned registers are also always maybe assigned registers. This is used to provide information about writes occurring within the micro instruction. This is necessary, for example, to determine when forwarding should be applied. Specifically, on entry to each micro-code, this identifies which variables may have been written at the given point. Furthermore, it allows us to distinguish between those which may have been written and those which have definitely been written.

func (Writes) Clone 

func (p Writes) Clone() Writes

Clone this write state producing an otherwise identical but physically disjoint state.

func (Writes) DefinitelyAssigned 

func (p Writes) DefinitelyAssigned(reg register.Id) bool

DefinitelyAssigned determines whether or not a give register has definitely been assigned. Observe that, for any register r, it follows that DefinitelyAssigned(r) implies MaybeAssigned(r).

func (Writes) Join 

func (p Writes) Join(q Writes) Writes

Join combines two write states together.

func (Writes) MayAnybeAssigned 

func (p Writes) MayAnybeAssigned(regs ...register.Id) bool

MayAnybeAssigned determines whether or not any of the given registers may have been assigned.

func (Writes) MaybeAssigned 

func (p Writes) MaybeAssigned(reg register.Id) bool

MaybeAssigned determines whether or not a give register may have been assigned.

func (Writes) String 

func (p Writes) String(rmap register.Map) string

func (Writes) Write 

func (p Writes) Write(regs ...register.Id) Writes

Write constructs a write state representing the give state after a set of writes have occurred.

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.