Class LatticeAnalysis<TCell>

A base class for flow-sensitive data analyses that assign analysis results to values by repeatedly computing lattice meet operations.

Inheritance

System.Object

LatticeAnalysis<TCell>

Implements

IFlowGraphAnalysis<LatticeAnalysisResult<TCell>>

Inherited Members

System.Object.ToString()

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

Namespace: Flame.Compiler.Analysis

Assembly: Flame.Compiler.dll

Syntax

public abstract class LatticeAnalysis<TCell> : IFlowGraphAnalysis<LatticeAnalysisResult<TCell>>

Type Parameters

Name	Description
TCell	The type of a lattice cell. These are the cells of the bounded lattice on which a meet operation is defined. The analysis produces a mapping of values to lattice cells.

Properties

Bottom

Gets the bottom cell of the bounded lattice. The top cell is the least permissive lattice cell that can be assigned to a value: computing the meet of the bottom cell and any other cell produces the former.

Declaration

public abstract TCell Bottom { get; }

Property Value

Type	Description
TCell	The bottom cell of the bounded lattice.

Top

Gets the top cell of the bounded lattice. The top cell is the most permissive lattice cell that can be assigned to a value: computing the meet of the top cell and any other cell produces the latter.

Declaration

public abstract TCell Top { get; }

Property Value

Type	Description
TCell	The top cell of the bounded lattice.

Methods

Analyze(FlowGraph)

Declaration

public LatticeAnalysisResult<TCell> Analyze(FlowGraph graph)

Parameters

Type	Name	Description
FlowGraph	graph

Returns

Type	Description
LatticeAnalysisResult<TCell>

AnalyzeWithUpdates(FlowGraph, LatticeAnalysisResult<TCell>, IReadOnlyList<FlowGraphUpdate>)

Declaration

public LatticeAnalysisResult<TCell> AnalyzeWithUpdates(FlowGraph graph, LatticeAnalysisResult<TCell> previousResult, IReadOnlyList<FlowGraphUpdate> updates)

Parameters

Type	Name	Description
FlowGraph	graph
LatticeAnalysisResult<TCell>	previousResult
System.Collections.Generic.IReadOnlyList<FlowGraphUpdate>	updates

Returns

Type	Description
LatticeAnalysisResult<TCell>

Evaluate(NamedInstruction, IReadOnlyDictionary<ValueTag, TCell>)

Evaluates an instruction to a lattice cell, given the values other cells evaluate to.

Declaration

public abstract TCell Evaluate(NamedInstruction instruction, IReadOnlyDictionary<ValueTag, TCell> cells)

Parameters

Type	Name	Description
NamedInstruction	instruction	The instruction to evaluate.
System.Collections.Generic.IReadOnlyDictionary<ValueTag, TCell>	cells	The lattice cells currently assigned to values in the graph.

Returns

Type	Description
TCell	A lattice cell.

GetLiveBranches(BlockFlow, IReadOnlyDictionary<ValueTag, TCell>, FlowGraph)

Given block flow, computes its live branches given the cells to which values evaluate.

Declaration

public virtual IEnumerable<Branch> GetLiveBranches(BlockFlow flow, IReadOnlyDictionary<ValueTag, TCell> cells, FlowGraph graph)

Parameters

Type	Name	Description
BlockFlow	flow	The block flow to consider.
System.Collections.Generic.IReadOnlyDictionary<ValueTag, TCell>	cells	The lattice cells currently assigned to values in the graph.
FlowGraph	graph	The control-flow graph that defines flow.

Returns

Type	Description
System.Collections.Generic.IEnumerable<Branch>	A sequence of live branches.

Meet(TCell, TCell)

Computes the meet of two lattice cells.

Declaration

public abstract TCell Meet(TCell first, TCell second)

Parameters

Type	Name	Description
TCell	first	A lattice cell.
TCell	second	Another lattice cell.

Returns

Type	Description
TCell	A new lattice cell.

Remarks

The meet operator must adhere to a number of axioms; otherwise, the analysis might report incorrect results or end up in an infinite loop. See Wikipedia for the minutiae. https://en.wikipedia.org/wiki/Lattice_(order)#Lattices_as_algebraic_structures

These axioms are always satisfied if the meet operator corresponds to the max on a total order, i.e., there are finitely many lattice cells E_1, E_2, ..., E_n and E_1 < E_2 < ... < E_n.

Implements

IFlowGraphAnalysis<T>