|
// Copyright (c) .NET Foundation and contributors. All rights reserved.
// Licensed under the MIT license. See LICENSE file in the project root for full license information.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
// This is needed due to NativeAOT which doesn't enable nullable globally yet
#nullable enable
namespace ILLink.Shared.DataFlow
{
// A generic implementation of a forward dataflow analysis. Forward means that it flows facts
// across code in the order of execution, starting from the beginning of a method,
// and merging values from predecessors.
public abstract class ForwardDataFlowAnalysis<TValue, TState, TLattice, TBlock, TRegion, TControlFlowGraph, TTransfer, TConditionValue>
where TValue : struct, IEquatable<TValue>
where TState : class, IDataFlowState<TValue, TLattice>, new()
where TLattice : ILattice<TValue>
where TTransfer : ITransfer<TBlock, TValue, TState, TLattice, TConditionValue>
where TBlock : struct, IBlock<TBlock>
where TRegion : IRegion<TRegion>
where TControlFlowGraph : IControlFlowGraph<TBlock, TRegion>
where TConditionValue : struct, INegate<TConditionValue>
{
// Data structure to store dataflow states for every basic block in the control flow graph,
// keeping the exception states shared across different basic blocks owned by the same try or catch region.
internal struct ControlFlowGraphState
{
// Dataflow states for each basic block
private readonly Dictionary<IControlFlowGraph<TBlock, TRegion>.ControlFlowBranch, TState> branchInput;
// The control flow graph doesn't contain edges for exceptional control flow:
// - From any point in a try region to the start of any catch or finally
// - From any point in a catch region to the start of a finally or the end of a try-catch block
// These implicit edges are handled by tracking an auxiliary state for each try and catch region,
// which the transfer functions are expected to update (in addition to the normal state updates)
// when visiting operations inside of a try or catch region.
// Dataflow states for exceptions propagating out of try or catch regions
private readonly Dictionary<TRegion, Box<TValue>> exceptionState;
// Control may flow through a finally region when an exception is thrown from anywhere in the corresponding
// try or catch regions, or as part of non-exceptional control flow out of a try or catch.
// We track a separate finally state for the exceptional case. Only the normal (non-exceptional) state is
// propagated out of the finally.
// Dataflow states for finally blocks when exception propagate through the finally region
private readonly Dictionary<IControlFlowGraph<TBlock, TRegion>.ControlFlowBranch, TValue> exceptionFinallyState;
// Finally regions may be reached (along non-exceptional paths)
// from multiple branches. This gets updated to track the normal finally input
// states from all of these branches (which aren't represented explicitly in the CFG).
private readonly Dictionary<TRegion, TValue> finallyInputState;
private readonly TControlFlowGraph cfg;
private readonly TLattice lattice;
public ControlFlowGraphState (TControlFlowGraph cfg, TLattice lattice, TValue entryValue)
{
branchInput = new ();
exceptionState = new ();
exceptionFinallyState = new ();
finallyInputState = new ();
this.cfg = cfg;
this.lattice = lattice;
IControlFlowGraph<TBlock, TRegion>.ControlFlowBranch? entryOut = cfg.GetSuccessors (cfg.Entry).SingleOrDefault ();
Debug.Assert (entryOut != null);
if (entryOut == null)
return;
branchInput[entryOut.Value] = new TState () {
Lattice = lattice,
Current = entryValue,
Exception = null
};
}
public Box<TValue> GetExceptionState (TRegion tryOrCatchOrFilterRegion)
{
if (tryOrCatchOrFilterRegion.Kind is not (RegionKind.Try or RegionKind.Catch or RegionKind.Filter))
throw new ArgumentException (null, nameof (tryOrCatchOrFilterRegion));
if (!exceptionState.TryGetValue (tryOrCatchOrFilterRegion, out Box<TValue>? state)) {
state = new Box<TValue> (lattice.Top);
exceptionState.Add (tryOrCatchOrFilterRegion, state);
}
return state;
}
public bool TryGetExceptionState (TBlock block, out Box<TValue>? state)
{
state = null;
if (!cfg.TryGetEnclosingTryOrCatchOrFilter (block, out TRegion? tryOrCatchOrFilterRegion))
return false;
state = GetExceptionState (tryOrCatchOrFilterRegion);
return true;
}
public TValue GetFinallyInputState (TRegion finallyRegion)
{
if (finallyRegion.Kind is not RegionKind.Finally)
throw new ArgumentException (null, nameof (finallyRegion));
if (!finallyInputState.TryGetValue (finallyRegion, out TValue state)) {
state = lattice.Top;
finallyInputState.Add (finallyRegion, state);
}
return state;
}
public void SetFinallyInputState (TRegion finallyRegion, TValue state)
{
if (finallyRegion.Kind is not RegionKind.Finally)
throw new ArgumentException (null, nameof (finallyRegion));
finallyInputState[finallyRegion] = state;
}
public bool TryGetExceptionFinallyState (IControlFlowGraph<TBlock, TRegion>.ControlFlowBranch branch, out TValue state)
{
state = default;
if (!cfg.TryGetEnclosingFinally (branch.Source, out _))
return false;
if (!exceptionFinallyState.TryGetValue (branch, out state)) {
state = lattice.Top;
exceptionFinallyState.Add (branch, state);
}
return true;
}
public void SetExceptionFinallyState (IControlFlowGraph<TBlock, TRegion>.ControlFlowBranch branch, TValue state)
{
if (!cfg.TryGetEnclosingFinally (branch.Source, out _))
throw new InvalidOperationException ();
exceptionFinallyState[branch] = state;
}
public TState Get (IControlFlowGraph<TBlock, TRegion>.ControlFlowBranch branch)
{
if (!branchInput.TryGetValue (branch, out TState? state)) {
TryGetExceptionState (branch.Source, out Box<TValue>? exceptionState);
state = new TState () {
Lattice = lattice,
Current = lattice.Top,
Exception = exceptionState
};
branchInput.Add (branch, state);
}
return state;
}
}
[Conditional ("DEBUG")]
public virtual void TraceStart (TControlFlowGraph cfg) { }
[Conditional ("DEBUG")]
public virtual void TraceVisitBlock (TBlock block) { }
[Conditional ("DEBUG")]
public virtual void TraceEdgeInput (IControlFlowGraph<TBlock, TRegion>.ControlFlowBranch branch, TValue state) { }
[Conditional ("DEBUG")]
public virtual void TraceBlockInput (TValue normalState, TValue? exceptionState, TValue? exceptionFinallyState) { }
[Conditional ("DEBUG")]
public virtual void TraceBlockOutput (TValue normalState, TValue? exceptionState, TValue? exceptionFinallyState) { }
protected readonly TLattice lattice;
private readonly TValue entryValue;
protected ForwardDataFlowAnalysis (TLattice lattice, TValue entryValue)
{
this.lattice = lattice;
this.entryValue = entryValue;
}
void TransferOut (TTransfer transfer, TControlFlowGraph cfg, TBlock block, TState state,
Action<IControlFlowGraph<TBlock, TRegion>.ControlFlowBranch, TValue> updateState
)
{
TConditionValue? conditionValue = transfer.Transfer (block, state);
foreach (var successor in cfg.GetSuccessors (block)) {
// Duplicate the state so that it's not shared between branches.
TValue branchState = lattice.Meet (lattice.Top, state.Current);
if (conditionValue != null) {
Debug.Assert (successor.ConditionKind is ConditionKind.WhenTrue or ConditionKind.WhenFalse);
transfer.ApplyCondition (
// ConditionKind 'WhenTrue' means the condition is true in this branch.
successor.ConditionKind is ConditionKind.WhenTrue
? conditionValue.Value
: conditionValue.Value.Negate (),
ref branchState);
}
updateState (successor, branchState);
}
}
// This just runs a dataflow algorithm until convergence. It doesn't cache any results,
// allowing each particular kind of analysis to decide what is worth saving.
public void Fixpoint (TControlFlowGraph cfg, TTransfer transfer)
{
TraceStart (cfg);
// Initialize output of each block to the Top value of the lattice
var cfgState = new ControlFlowGraphState (cfg, lattice, entryValue);
// For now, the actual dataflow algorithm is the simplest possible version.
// It is written to be obviously correct, but has not been optimized for performance
// at all. As written it will almost always perform unnecessary passes over the entire
// control flow graph. The core abstractions shouldn't need to change even when we write
// an optimized version of this algorithm - ideally any optimizations will be generic,
// not specific to a particular analysis.
// Allocate some objects which will be reused to hold the current dataflow state,
// to avoid allocatons in the inner loop below.
var state = new TState () {
Lattice = lattice,
Current = lattice.Top,
Exception = null
};
var finallyState = new TState () {
Lattice = lattice,
Current = lattice.Top,
Exception = null
};
bool changed = true;
while (changed) {
changed = false;
foreach (var block in cfg.Blocks) {
TraceVisitBlock (block);
if (block.Equals (cfg.Entry))
continue;
bool isTryOrCatchOrFilterBlock = cfg.TryGetEnclosingTryOrCatchOrFilter (block, out TRegion? tryOrCatchOrFilterRegion);
bool isTryBlock = isTryOrCatchOrFilterBlock && tryOrCatchOrFilterRegion!.Kind == RegionKind.Try;
bool isTryStart = isTryBlock && block.Equals (cfg.FirstBlock (tryOrCatchOrFilterRegion!));
bool isCatchBlock = isTryOrCatchOrFilterBlock && tryOrCatchOrFilterRegion!.Kind == RegionKind.Catch;
bool isCatchStartWithoutFilter = isCatchBlock && block.Equals (cfg.FirstBlock (tryOrCatchOrFilterRegion!)) && !cfg.HasFilter (tryOrCatchOrFilterRegion!);
bool isFilterBlock = isTryOrCatchOrFilterBlock && tryOrCatchOrFilterRegion!.Kind == RegionKind.Filter;
bool isFilterStart = isFilterBlock && block.Equals (cfg.FirstBlock (tryOrCatchOrFilterRegion!));
bool isCatchOrFilterStart = isCatchStartWithoutFilter || isFilterStart;
bool isFinallyBlock = cfg.TryGetEnclosingFinally (block, out TRegion? finallyRegion);
bool isFinallyStart = isFinallyBlock && block.Equals (cfg.FirstBlock (finallyRegion!));
//
// Meet over predecessors to get the new value at the start of this block.
//
// Compute the dataflow state at the beginning of this block.
TValue currentState = lattice.Top;
foreach (var predecessor in cfg.GetPredecessors (block)) {
TValue predecessorState = cfgState.Get (predecessor).Current;
FlowStateThroughExitedFinallys (predecessor, ref predecessorState);
TraceEdgeInput (predecessor, predecessorState);
currentState = lattice.Meet (currentState, predecessorState);
}
// State at start of a catch also includes the exceptional state from
// try -> catch exceptional control flow.
if (isCatchOrFilterStart) {
TRegion correspondingTry = cfg.GetCorrespondingTry (tryOrCatchOrFilterRegion!);
Box<TValue> tryExceptionState = cfgState.GetExceptionState (correspondingTry);
currentState = lattice.Meet (currentState, tryExceptionState.Value);
// A catch or filter can also be reached from a previous filter.
foreach (TRegion previousFilter in cfg.GetPreviousFilters (tryOrCatchOrFilterRegion!)) {
// Control may flow from the last block of a previous filter region to this catch or filter region.
// Exceptions may also propagate from anywhere in a filter region to this catch or filter region.
// This covers both cases since the exceptional state is a superset of the normal state.
Box<TValue> previousFilterExceptionState = cfgState.GetExceptionState (previousFilter);
currentState = lattice.Meet (currentState, previousFilterExceptionState.Value);
}
}
if (isFinallyStart) {
TValue finallyInputState = cfgState.GetFinallyInputState (finallyRegion!);
currentState = lattice.Meet (currentState, finallyInputState);
}
// Compute the independent exceptional finally state at beginning of a finally.
TValue? exceptionFinallyState = null;
if (isFinallyBlock) {
// Inside finally regions, must compute the parallel meet state for unhandled exceptions.
// Using predecessors in the finally. But not from outside the finally.
exceptionFinallyState = lattice.Top;
foreach (var predecessor in cfg.GetPredecessors (block)) {
var isPredecessorInFinally = cfgState.TryGetExceptionFinallyState (predecessor, out TValue predecessorState);
Debug.Assert (isPredecessorInFinally);
FlowStateThroughExitedFinallys (predecessor, ref predecessorState);
exceptionFinallyState = lattice.Meet (exceptionFinallyState.Value, predecessorState);
}
// For first block, also initialize it from the try or catch blocks.
if (isFinallyStart) {
// Note that try+catch+finally is represented in the region hierarchy like a
// try/finally where the try block contains a try/catch.
// So including the corresponding try exception state will also take care of the
// corresponding catch exception state.
TRegion correspondingTry = cfg.GetCorrespondingTry (finallyRegion!);
Box<TValue> tryExceptionState = cfgState.GetExceptionState (correspondingTry);
exceptionFinallyState = lattice.Meet (exceptionFinallyState.Value, tryExceptionState.Value);
}
}
// Initialize the exception state at the start of try/catch regions. Control flow edges from predecessors
// within the same try or catch region don't need to be handled here because the transfer functions update
// the exception state to reflect every operation in the region.
cfgState.TryGetExceptionState (block, out Box<TValue>? exceptionState);
TValue? oldExceptionState = exceptionState?.Value;
if (isTryStart || isCatchOrFilterStart) {
// Catch/filter regions get the initial state from the exception state of the corresponding try region.
// This is already accounted for in the non-exceptional control flow state of the catch block above,
// so we can just use the state we already computed, for both try and catch regions.
exceptionState!.Value = lattice.Meet (exceptionState!.Value, currentState);
if (isFinallyBlock) {
// Exceptions could also be thrown from inside a finally that was entered due to a previous exception.
// So the exception state must also include values from the exceptional finally state (computed above).
exceptionState!.Value = lattice.Meet (exceptionState!.Value, exceptionFinallyState!.Value);
}
}
TraceBlockInput (currentState, exceptionState?.Value, exceptionFinallyState);
//
// Apply transfer functions to the met input to get an output value for this block.
//
state.Current = currentState;
state.Exception = exceptionState;
TransferOut (transfer, cfg, block, state,
updateState: (branch, newValue) => {
TState state = cfgState.Get (branch);
if (!changed && !newValue.Equals (state.Current))
changed = true;
state.Current = newValue;
}
);
if (isFinallyBlock) {
// Independently apply transfer functions for the exception finally state in finally regions.
finallyState.Current = exceptionFinallyState!.Value;
finallyState.Exception = exceptionState;
TransferOut (transfer, cfg, block, finallyState,
updateState: (branch, newValue) => {
bool result = cfgState.TryGetExceptionFinallyState (branch, out TValue value);
Debug.Assert (result);
if (!changed && !newValue.Equals (value))
changed = true;
cfgState.SetExceptionFinallyState (branch, newValue);
}
);
}
// Either the normal transfer or the finally transfer might change
// the try/catch state, so this check should happen after both transfers.
if (exceptionState?.Value.Equals (oldExceptionState!.Value) == false) {
Debug.Assert (exceptionState != null);
Debug.Assert (oldExceptionState != null);
changed = true;
// Bubble up the changed exception state to the next enclosing try or catch exception state.
while (cfg.TryGetEnclosingTryOrCatchOrFilter (tryOrCatchOrFilterRegion!, out TRegion? enclosingTryOrCatch)) {
// Filters can't contain try/catch/filters.
Debug.Assert (enclosingTryOrCatch.Kind != RegionKind.Filter);
Box<TValue> tryOrCatchExceptionState = cfgState.GetExceptionState (enclosingTryOrCatch);
tryOrCatchExceptionState.Value = lattice.Meet (tryOrCatchExceptionState!.Value, exceptionState!.Value);
tryOrCatchOrFilterRegion = enclosingTryOrCatch;
}
}
TraceBlockOutput (state.Current, exceptionState?.Value, exceptionFinallyState);
}
}
void FlowStateThroughExitedFinallys (
IControlFlowGraph<TBlock, TRegion>.ControlFlowBranch predecessor,
ref TValue predecessorState)
{
foreach (var exitedFinally in predecessor.FinallyRegions) {
TValue oldFinallyInputState = cfgState.GetFinallyInputState (exitedFinally);
TValue finallyInputState = lattice.Meet (oldFinallyInputState, predecessorState);
cfgState.SetFinallyInputState (exitedFinally, finallyInputState);
// Note: the current approach here is inefficient for long chains of finally regions because
// the states will not converge until we have visited each block along the chain
// and propagated the new states along this path.
if (!changed && !finallyInputState.Equals (oldFinallyInputState))
changed = true;
TBlock lastFinallyBlock = cfg.LastBlock (exitedFinally);
IControlFlowGraph<TBlock, TRegion>.ControlFlowBranch? finallyExit = cfg.GetSuccessors (lastFinallyBlock).SingleOrDefault ();
Debug.Assert (finallyExit != null);
if (finallyExit == null)
continue;
Debug.Assert (finallyExit.Value.ConditionKind == ConditionKind.Unconditional);
predecessorState = cfgState.Get (finallyExit.Value).Current;
}
}
}
}
}
|