flowanalysis.cs

C#编译器源代码。Micorsoft开放源代码

//
// flowanalyis.cs: The control flow analysis code
//
// Author:
//   Martin Baulig ([e-mail])
//
// (C) 2001, 2002, 2003 Ximian, Inc.
//

using System;
using System.Text;
using System.Collections;
using System.Reflection;
using System.Reflection.Emit;
using System.Diagnostics;

namespace Mono.CSharp
{
	// <summary>
	//   A new instance of this class is created every time a new block is resolved
	//   and if there's branching in the block's control flow.
	// </summary>
	public abstract class FlowBranching
	{
		// <summary>
		//   The type of a FlowBranching.
		// </summary>
		public enum BranchingType : byte {
			// Normal (conditional or toplevel) block.
			Block,

			// Conditional.
			Conditional,

			// A loop block.
			Loop,

			// Try/Catch block.
			Exception,

			// Switch block.
			Switch,

			// Switch section.
			SwitchSection
		}

		// <summary>
		//   The type of one sibling of a branching.
		// </summary>
		public enum SiblingType : byte {
			Block,
			Conditional,
			SwitchSection,
			Try,
			Catch,
			Finally
		}

		// <summary>
		//   This is used in the control flow analysis code to specify whether the
		//   current code block may return to its enclosing block before reaching
		//   its end.
		// </summary>
		public enum FlowReturns : byte {
			Undefined = 0,

			// It can never return.
			Never,

			// This means that the block contains a conditional return statement
			// somewhere.
			Sometimes,

			// The code always returns, ie. there's an unconditional return / break
			// statement in it.
			Always
		}

		public sealed class Reachability
		{
			FlowReturns returns, breaks, throws, barrier;

			public FlowReturns Returns {
				get { return returns; }
			}
			public FlowReturns Breaks {
				get { return breaks; }
			}
			public FlowReturns Throws {
				get { return throws; }
			}
			public FlowReturns Barrier {
				get { return barrier; }
			}
			public Reachability (FlowReturns returns, FlowReturns breaks,
					     FlowReturns throws, FlowReturns barrier)
			{
				this.returns = returns;
				this.breaks = breaks;
				this.throws = throws;
				this.barrier = barrier;
			}

			public Reachability Clone ()
			{
				return new Reachability (returns, breaks, throws, barrier);
			}

			// <summary>
			//   Performs an `And' operation on the FlowReturns status
			//   (for instance, a block only returns Always if all its siblings
			//   always return).
			// </summary>
			public static FlowReturns AndFlowReturns (FlowReturns a, FlowReturns b)
			{
				if (a == FlowReturns.Undefined)
					return b;

				switch (a) {
				case FlowReturns.Never:
					if (b == FlowReturns.Never)
						return FlowReturns.Never;
					else
						return FlowReturns.Sometimes;

				case FlowReturns.Sometimes:
					return FlowReturns.Sometimes;

				case FlowReturns.Always:
					if (b == FlowReturns.Always)
						return FlowReturns.Always;
					else
						return FlowReturns.Sometimes;

				default:
					throw new ArgumentException ();
				}
			}

			public static FlowReturns OrFlowReturns (FlowReturns a, FlowReturns b)
			{
				if (a == FlowReturns.Undefined)
					return b;

				switch (a) {
				case FlowReturns.Never:
					return b;

				case FlowReturns.Sometimes:
					if (b == FlowReturns.Always)
						return FlowReturns.Always;
					else
						return FlowReturns.Sometimes;

				case FlowReturns.Always:
					return FlowReturns.Always;

				default:
					throw new ArgumentException ();
				}
			}

			public static void And (ref Reachability a, Reachability b, bool do_break)
			{
				if (a == null) {
					a = b.Clone ();
					return;
				}

				a.And (b, do_break);
			}

			public void And (Reachability b, bool do_break)
			{
				//
				// `break' does not "break" in a Switch or a LoopBlock
				//
				bool a_breaks = do_break && AlwaysBreaks;
				bool b_breaks = do_break && b.AlwaysBreaks;

				bool a_has_barrier, b_has_barrier;
				if (do_break) {
					//
					// This is the normal case: the code following a barrier
					// cannot be reached.
					//
					a_has_barrier = AlwaysHasBarrier;
					b_has_barrier = b.AlwaysHasBarrier;
				} else {
					//
					// Special case for Switch and LoopBlocks: we can reach the
					// code after the barrier via the `break'.
					//
					a_has_barrier = !AlwaysBreaks && AlwaysHasBarrier;
					b_has_barrier = !b.AlwaysBreaks && b.AlwaysHasBarrier;
				}

				bool a_unreachable = a_breaks || AlwaysThrows || a_has_barrier;
				bool b_unreachable = b_breaks || b.AlwaysThrows || b_has_barrier;

				//
				// Do all code paths always return ?
				//
				if (AlwaysReturns) {
					if (b.AlwaysReturns || b_unreachable)
						returns = FlowReturns.Always;
					else
						returns = FlowReturns.Sometimes;
				} else if (b.AlwaysReturns) {
					if (AlwaysReturns || a_unreachable)
						returns = FlowReturns.Always;
					else
						returns = FlowReturns.Sometimes;
				} else if (!MayReturn) {
					if (b.MayReturn)
						returns = FlowReturns.Sometimes;
					else
						returns = FlowReturns.Never;
				} else if (!b.MayReturn) {
					if (MayReturn)
						returns = FlowReturns.Sometimes;
					else
						returns = FlowReturns.Never;
				}

				breaks = AndFlowReturns (breaks, b.breaks);
				throws = AndFlowReturns (throws, b.throws);
				barrier = AndFlowReturns (barrier, b.barrier);

				if (a_unreachable && b_unreachable)
					barrier = FlowReturns.Always;
				else if (a_unreachable || b_unreachable)
					barrier = FlowReturns.Sometimes;
				else
					barrier = FlowReturns.Never;
			}

			public void Or (Reachability b)
			{
				returns = OrFlowReturns (returns, b.returns);
				breaks = OrFlowReturns (breaks, b.breaks);
				throws = OrFlowReturns (throws, b.throws);
				barrier = OrFlowReturns (barrier, b.barrier);
			}

			public static Reachability Never ()
			{
				return new Reachability (
					FlowReturns.Never, FlowReturns.Never,
					FlowReturns.Never, FlowReturns.Never);
			}

			public FlowReturns Reachable {
				get {
					if ((returns == FlowReturns.Always) ||
					    (breaks == FlowReturns.Always) ||
					    (throws == FlowReturns.Always) ||
					    (barrier == FlowReturns.Always))
						return FlowReturns.Never;
					else if ((returns == FlowReturns.Never) &&
						 (breaks == FlowReturns.Never) &&
						 (throws == FlowReturns.Never) &&
						 (barrier == FlowReturns.Never))
						return FlowReturns.Always;
					else
						return FlowReturns.Sometimes;
				}
			}

			public bool AlwaysBreaks {
				get { return breaks == FlowReturns.Always; }
			}

			public bool MayBreak {
				get { return breaks != FlowReturns.Never; }
			}

			public bool AlwaysReturns {
				get { return returns == FlowReturns.Always; }
			}

			public bool MayReturn {
				get { return returns != FlowReturns.Never; }
			}

			public bool AlwaysThrows {
				get { return throws == FlowReturns.Always; }
			}

			public bool MayThrow {
				get { return throws != FlowReturns.Never; }
			}

			public bool AlwaysHasBarrier {
				get { return barrier == FlowReturns.Always; }
			}

			public bool MayHaveBarrier {
				get { return barrier != FlowReturns.Never; }
			}

			public bool IsUnreachable {
				get { return Reachable == FlowReturns.Never; }
			}

			public void SetReturns ()
			{
				returns = FlowReturns.Always;
			}

			public void SetReturnsSometimes ()
			{
				returns = FlowReturns.Sometimes;
			}

			public void SetBreaks ()
			{
				breaks = FlowReturns.Always;
			}

			public void ResetBreaks ()
			{
				breaks = FlowReturns.Never;
			}

			public void SetThrows ()
			{
				throws = FlowReturns.Always;
			}

			public void SetThrowsSometimes ()
			{
				throws = FlowReturns.Sometimes;
			}

			public void SetBarrier ()
			{
				barrier = FlowReturns.Always;
			}

			public void ResetBarrier ()
			{
				barrier = FlowReturns.Never;
			}

			static string ShortName (FlowReturns returns)
			{
				switch (returns) {
				case FlowReturns.Never:
					return "N";
				case FlowReturns.Sometimes:
					return "S";
				default:
					return "A";
				}
			}

			public override string ToString ()
			{
				return String.Format ("[{0}:{1}:{2}:{3}:{4}]",
						      ShortName (returns), ShortName (breaks),
						      ShortName (throws), ShortName (barrier),
						      ShortName (Reachable));
			}
		}

		public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
		{
			switch (type) {
			case BranchingType.Exception:
				throw new InvalidOperationException ();

			case BranchingType.Switch:
				return new FlowBranchingSwitch (parent, block, loc);

			case BranchingType.SwitchSection:
				return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);

			case BranchingType.Block:
				return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);

			case BranchingType.Loop:
				return new FlowBranchingLoop (parent, block, loc);

			default:
				return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
			}
		}

		// <summary>
		//   The type of this flow branching.
		// </summary>
		public readonly BranchingType Type;

		// <summary>
		//   The block this branching is contained in.  This may be null if it's not
		//   a top-level block and it doesn't declare any local variables.
		// </summary>
		public readonly Block Block;

		// <summary>
		//   The parent of this branching or null if this is the top-block.
		// </summary>
		public readonly FlowBranching Parent;

		// <summary>
		//   Start-Location of this flow branching.
		// </summary>
		public readonly Location Location;

		// <summary>
		//   If this is an infinite loop.
		// </summary>
		public bool Infinite;

		//
		// Private
		//
		VariableMap param_map, local_map;

		static int next_id = 0;
		int id;

		// <summary>
		//   The vector contains a BitArray with information about which local variables
		//   and parameters are already initialized at the current code position.
		// </summary>
		public class UsageVector {
			// <summary>
			//   The type of this branching.
			// </summary>
			public readonly SiblingType Type;

			// <summary>
			//   Start location of this branching.
			// </summary>
			public readonly Location Location;

			// <summary>
			//   This is only valid for SwitchSection, Try, Catch and Finally.
			// </summary>
			public readonly Block Block;

			// <summary>
			//   If this is true, then the usage vector has been modified and must be
			//   merged when we're done with this branching.
			// </summary>
			public bool IsDirty;

			// <summary>
			//   The number of parameters in this block.
			// </summary>
			public readonly int CountParameters;

			// <summary>
			//   The number of locals in this block.
			// </summary>
			public readonly int CountLocals;

			// <summary>
			//   If not null, then we inherit our state from this vector and do a
			//   copy-on-write.  If null, then we're the first sibling in a top-level
			//   block and inherit from the empty vector.
			// </summary>
			public readonly UsageVector InheritsFrom;

			// <summary>
			//   This is used to construct a list of UsageVector's.
			// </summary>
			public UsageVector Next;

			//
			// Private.
			//
			MyBitVector locals, parameters;
			Reachability reachability;

			static int next_id = 0;
			int id;

			//
			// Normally, you should not use any of these constructors.
			//
			public UsageVector (SiblingType type, UsageVector parent,
					    Block block, Location loc,
					    int num_params, int num_locals)
			{
				this.Type = type;
				this.Block = block;
				this.Location = loc;
				this.InheritsFrom = parent;
				this.CountParameters = num_params;
				this.CountLocals = num_locals;

				if (parent != null) {
					if (num_locals > 0)
						locals = new MyBitVector (parent.locals, CountLocals);
					
					if (num_params > 0)
						parameters = new MyBitVector (parent.parameters, num_params);

					reachability = parent.Reachability.Clone ();
				} else {
					if (num_locals > 0)
						locals = new MyBitVector (null, CountLocals);
					
					if (num_params > 0)
						parameters = new MyBitVector (null, num_params);

					reachability = Reachability.Never ();
				}

				id = ++next_id;
			}

			public UsageVector (SiblingType type, UsageVector parent,
					    Block block, Location loc)
				: this (type, parent, block, loc,
					parent.CountParameters, parent.CountLocals)
			{ }

			public UsageVector (MyBitVector parameters, MyBitVector locals,
					    Reachability reachability, Block block,
					    Location loc)
			{
				this.Type = SiblingType.Block;
				this.Location = loc;
				this.Block = block;

				this.reachability = reachability;
				this.parameters = parameters;
				this.locals = locals;

				id = ++next_id;
			}

			// <summary>
			//   This does a deep copy of the usage vector.
			// </summary>
			public UsageVector Clone ()
			{
				UsageVector retval = new UsageVector (
					Type, null, Block, Location,
					CountParameters, CountLocals);

				if (retval.locals != null)
					retval.locals = locals.Clone ();
				
				if (parameters != null)
					retval.parameters = parameters.Clone ();
				
				retval.reachability = reachability.Clone ();

				return retval;
			}

			public bool IsAssigned (VariableInfo var)
			{
				if (!var.IsParameter && Reachability.IsUnreachable)
					return true;

				return var.IsAssigned (var.IsParameter ? parameters : locals);
			}

			public void SetAssigned (VariableInfo var)
			{
				if (!var.IsParameter && Reachability.IsUnreachable)
					return;

				IsDirty = true;
				var.SetAssigned (var.IsParameter ? parameters : locals);
			}

			public bool IsFieldAssigned (VariableInfo var, string name)
			{
				if (!var.IsParameter && Reachability.IsUnreachable)
					return true;

				return var.IsFieldAssigned (var.IsParameter ? parameters : locals, name);
			}