1 files changed, 254 insertions, 0 deletions
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/TransformToSsa.cs b/ICSharpCode.Decompiler/FlowAnalysis/TransformToSsa.cs
new file mode 100644
index 00000000..47ff7bff
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/TransformToSsa.cs
@@ -0,0 +1,254 @@
+// Copyright (c) 2011 AlphaSierraPapa for the SharpDevelop Team
+// 
+// Permission is hereby granted, free of charge, to any person obtaining a copy of this
+// software and associated documentation files (the "Software"), to deal in the Software
+// without restriction, including without limitation the rights to use, copy, modify, merge,
+// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
+// to whom the Software is furnished to do so, subject to the following conditions:
+// 
+// The above copyright notice and this permission notice shall be included in all copies or
+// substantial portions of the Software.
+// 
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
+// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
+// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
+// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
+// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+// DEALINGS IN THE SOFTWARE.
+
+using System;
+using System.Collections.Generic;
+using System.Collections.ObjectModel;
+using System.Diagnostics;
+using System.Linq;
+
+using Mono.Cecil;
+using Mono.Cecil.Cil;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+	/// <summary>
+	/// Convers a method to static single assignment form.
+	/// </summary>
+	internal sealed class TransformToSsa
+	{
+		public static void Transform(ControlFlowGraph cfg, SsaForm ssa, bool optimize = true)
+		{
+			TransformToSsa transform = new TransformToSsa(cfg, ssa);
+			transform.ConvertVariablesToSsa();
+			SsaOptimization.RemoveDeadAssignments(ssa); // required so that 'MakeByRefCallsSimple' can detect more cases
+			if (SimplifyByRefCalls.MakeByRefCallsSimple(ssa)) {
+				transform.ConvertVariablesToSsa();
+			}
+			if (optimize)
+				SsaOptimization.Optimize(ssa);
+		}
+		
+		readonly ControlFlowGraph cfg;
+		readonly SsaForm ssaForm;
+		readonly List<SsaInstruction>[] writeToOriginalVariables; // array index -> SsaVariable OriginalVariableIndex
+		readonly bool[] addressTaken; // array index -> SsaVariable OriginalVariableIndex; value = whether ldloca instruction was used with variable
+
+		TransformToSsa(ControlFlowGraph cfg, SsaForm ssaForm)
+		{
+			this.cfg = cfg;
+			this.ssaForm = ssaForm;
+			writeToOriginalVariables = new List<SsaInstruction>[ssaForm.OriginalVariables.Count];
+			addressTaken = new bool[ssaForm.OriginalVariables.Count];
+		}
+		
+		#region CollectInformationAboutOriginalVariableUse
+		void CollectInformationAboutOriginalVariableUse()
+		{
+			Debug.Assert(addressTaken.Length == writeToOriginalVariables.Length);
+			for (int i = 0; i < writeToOriginalVariables.Length; i++) {
+				Debug.Assert(ssaForm.OriginalVariables[i].OriginalVariableIndex == i);
+				
+				addressTaken[i] = false;
+				// writeToOriginalVariables is only used when placing phi functions
+				// we don't need to do that anymore for variables that are already in SSA form
+				if (ssaForm.OriginalVariables[i].IsSingleAssignment)
+					writeToOriginalVariables[i] = null;
+				else
+					writeToOriginalVariables[i] = new List<SsaInstruction>();
+			}
+			foreach (SsaBlock block in ssaForm.Blocks) {
+				foreach (SsaInstruction inst in block.Instructions) {
+					if (inst.Target != null ) {
+						var list = writeToOriginalVariables[inst.Target.OriginalVariableIndex];
+						if (list != null)
+							list.Add(inst);
+					}
+					if (inst.Instruction != null) {
+						if (inst.Instruction.OpCode == OpCodes.Ldloca) {
+							addressTaken[ssaForm.GetOriginalVariable((VariableDefinition)inst.Instruction.Operand).OriginalVariableIndex] = true;
+						} else if (inst.Instruction.OpCode == OpCodes.Ldarga) {
+							addressTaken[ssaForm.GetOriginalVariable((ParameterDefinition)inst.Instruction.Operand).OriginalVariableIndex] = true;
+						}
+					}
+				}
+			}
+		}
+		#endregion
+		
+		#region ConvertToSsa
+		void ConvertVariablesToSsa()
+		{
+			CollectInformationAboutOriginalVariableUse();
+			bool[] processVariable = new bool[ssaForm.OriginalVariables.Count];
+			foreach (SsaVariable variable in ssaForm.OriginalVariables) {
+				if (!variable.IsSingleAssignment && !addressTaken[variable.OriginalVariableIndex]) {
+					PlacePhiFunctions(variable);
+					processVariable[variable.OriginalVariableIndex] = true;
+				}
+			}
+			RenameVariables(processVariable);
+			foreach (SsaVariable variable in ssaForm.OriginalVariables) {
+				if (!addressTaken[variable.OriginalVariableIndex]) {
+					Debug.Assert(variable.IsSingleAssignment && variable.Definition != null);
+				}
+			}
+			ssaForm.ComputeVariableUsage();
+		}
+		#endregion
+		
+		#region PlacePhiFunctions
+		void PlacePhiFunctions(SsaVariable variable)
+		{
+			cfg.ResetVisited();
+			HashSet<SsaBlock> blocksWithPhi = new HashSet<SsaBlock>();
+			Queue<ControlFlowNode> worklist = new Queue<ControlFlowNode>();
+			foreach (SsaInstruction writeInstruction in writeToOriginalVariables[variable.OriginalVariableIndex]) {
+				ControlFlowNode cfgNode = cfg.Nodes[writeInstruction.ParentBlock.BlockIndex];
+				if (!cfgNode.Visited) {
+					cfgNode.Visited = true;
+					worklist.Enqueue(cfgNode);
+				}
+			}
+			while (worklist.Count > 0) {
+				ControlFlowNode cfgNode = worklist.Dequeue();
+				foreach (ControlFlowNode dfNode in cfgNode.DominanceFrontier) {
+					// we don't need phi functions in the exit node
+					if (dfNode.NodeType == ControlFlowNodeType.RegularExit || dfNode.NodeType == ControlFlowNodeType.ExceptionalExit)
+						continue;
+					SsaBlock y = ssaForm.Blocks[dfNode.BlockIndex];
+					if (blocksWithPhi.Add(y)) {
+						// add a phi instruction in y
+						SsaVariable[] operands = Enumerable.Repeat(variable, dfNode.Incoming.Count).ToArray();
+						y.Instructions.Insert(0, new SsaInstruction(y, null, variable, operands, specialOpCode: SpecialOpCode.Phi));
+						if (!dfNode.Visited) {
+							dfNode.Visited = true;
+							worklist.Enqueue(dfNode);
+						}
+					}
+				}
+			}
+		}
+		#endregion
+		
+		#region RenameVariable
+		int tempVariableCounter = 1;
+		
+		void RenameVariables(bool[] processVariable)
+		{
+			VariableRenamer r = new VariableRenamer(this, processVariable);
+			r.Visit(ssaForm.EntryPoint);
+		}
+		
+		sealed class VariableRenamer
+		{
+			readonly TransformToSsa transform;
+			readonly ReadOnlyCollection<SsaVariable> inputVariables;
+			internal readonly Stack<SsaVariable>[] versionStacks;
+			int[] versionCounters; // specifies for each input variable the next version number
+			
+			// processVariable = specifies for each input variable whether we should rename it
+			public VariableRenamer(TransformToSsa transform, bool[] processVariable)
+			{
+				this.transform = transform;
+				inputVariables = transform.ssaForm.OriginalVariables;
+				Debug.Assert(inputVariables.Count == processVariable.Length);
+				versionCounters = new int[inputVariables.Count];
+				versionStacks = new Stack<SsaVariable>[inputVariables.Count];
+				for (int i = 0; i < versionStacks.Length; i++) {
+					if (processVariable[i]) {
+						Debug.Assert(inputVariables[i].IsSingleAssignment == false);
+						// only create version stacks for the variables that we need to process and that weren't already processed earlier
+						versionStacks[i] = new Stack<SsaVariable>();
+						versionStacks[i].Push(inputVariables[i]);
+					}
+				}
+			}
+			
+			SsaVariable MakeNewVersion(int variableIndex)
+			{
+				int versionCounter = ++versionCounters[variableIndex];
+				SsaVariable x = inputVariables[variableIndex];
+				if (versionCounter == 1) {
+					return x;
+				} else {
+					if (x.IsStackLocation) {
+						return new SsaVariable(x, "temp" + (transform.tempVariableCounter++));
+					} else {
+						return new SsaVariable(x, x.Name + "_" + versionCounter);
+					}
+				}
+			}
+			
+			internal void Visit(SsaBlock block)
+			{
+				// duplicate top of all stacks
+				foreach (var stack in versionStacks) {
+					if (stack != null)
+						stack.Push(stack.Peek());
+				}
+				
+				foreach (SsaInstruction s in block.Instructions) {
+					// replace all uses of variables being processed with their current version.
+					if (s.SpecialOpCode != SpecialOpCode.Phi) {
+						for (int i = 0; i < s.Operands.Length; i++) {
+							var stack = versionStacks[s.Operands[i].OriginalVariableIndex];
+							if (stack != null)
+								s.Operands[i] = stack.Peek();
+						}
+					}
+					// if we're writing to a variable we should process:
+					if (s.Target != null) {
+						int targetIndex = s.Target.OriginalVariableIndex;
+						if (versionStacks[targetIndex] != null) {
+							s.Target = MakeNewVersion(targetIndex);
+							s.Target.IsSingleAssignment = true;
+							s.Target.Definition = s;
+							
+							// we already pushed our entry for this SsaBlock at the beginning (where we duplicated all stacks),
+							// so now replace the top element
+							versionStacks[targetIndex].Pop();
+							versionStacks[targetIndex].Push(s.Target);
+						}
+					}
+				}
+				
+				foreach (SsaBlock succ in block.Successors) {
+					int j = succ.Predecessors.IndexOf(block);
+					Debug.Assert(j >= 0);
+					foreach (SsaInstruction f in succ.Instructions) {
+						if (f.SpecialOpCode == SpecialOpCode.Phi) {
+							var stack = versionStacks[f.Target.OriginalVariableIndex];
+							if (stack != null) {
+								f.Operands[j] = stack.Peek();
+							}
+						}
+					}
+				}
+				foreach (ControlFlowNode child in transform.cfg.Nodes[block.BlockIndex].DominatorTreeChildren)
+					Visit(transform.ssaForm.Blocks[child.BlockIndex]);
+				// restore stacks:
+				foreach (var stack in versionStacks) {
+					if (stack != null)
+						stack.Pop();
+				}
+			}
+		}
+		#endregion
+	}
+}