File: src\tools\illink\src\ILLink.Shared\DataFlow\ForwardDataFlowAnalysis.cs
Web Access
Project: src\src\tools\illink\src\ILLink.RoslynAnalyzer\ILLink.RoslynAnalyzer.csproj (ILLink.RoslynAnalyzer)
// 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;
				}
			}
		}
	}
}