summaryrefslogtreecommitdiff
path: root/ICSharpCode.Decompiler/FlowAnalysis
diff options
context:
space:
mode:
Diffstat (limited to 'ICSharpCode.Decompiler/FlowAnalysis')
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/ControlFlowEdge.cs78
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraph.cs191
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraphBuilder.cs439
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/ControlFlowNode.cs305
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/ControlStructureDetector.cs241
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/OpCodeInfo.cs312
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/SimplifyByRefCalls.cs174
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/SsaBlock.cs60
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/SsaForm.cs162
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs257
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/SsaInstruction.cs191
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/SsaOptimization.cs138
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/SsaVariable.cs91
-rw-r--r--ICSharpCode.Decompiler/FlowAnalysis/TransformToSsa.cs254
14 files changed, 2893 insertions, 0 deletions
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowEdge.cs b/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowEdge.cs
new file mode 100644
index 00000000..98bd4399
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowEdge.cs
@@ -0,0 +1,78 @@
+// 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;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// Describes the type of a control flow egde.
+ /// </summary>
+ public enum JumpType
+ {
+ /// <summary>
+ /// A regular control flow edge.
+ /// </summary>
+ Normal,
+ /// <summary>
+ /// Jump to exception handler (an exception occurred)
+ /// </summary>
+ JumpToExceptionHandler,
+ /// <summary>
+ /// Jump from try block to leave target:
+ /// This is not a real jump, as the finally handler is executed first!
+ /// </summary>
+ LeaveTry,
+ /// <summary>
+ /// Jump at endfinally (to any of the potential leave targets).
+ /// For any leave-instruction, control flow enters the finally block - the edge to the leave target (LeaveTry) is not a real control flow edge.
+ /// EndFinally edges are inserted at the end of the finally block, jumping to any of the targets of the leave instruction.
+ /// This edge type is only used when copying of finally blocks is disabled (with copying, a normal deterministic edge is used at each copy of the endfinally node).
+ /// </summary>
+ EndFinally
+ }
+
+ /// <summary>
+ /// Represents an edge in the control flow graph, pointing from Source to Target.
+ /// </summary>
+ public sealed class ControlFlowEdge
+ {
+ public readonly ControlFlowNode Source;
+ public readonly ControlFlowNode Target;
+ public readonly JumpType Type;
+
+ public ControlFlowEdge(ControlFlowNode source, ControlFlowNode target, JumpType type)
+ {
+ Source = source;
+ Target = target;
+ Type = type;
+ }
+
+ public override string ToString()
+ {
+ switch (Type) {
+ case JumpType.Normal:
+ return "#" + Target.BlockIndex;
+ case JumpType.JumpToExceptionHandler:
+ return "e:#" + Target.BlockIndex;
+ default:
+ return Type.ToString() + ":#" + Target.BlockIndex;
+ }
+ }
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraph.cs b/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraph.cs
new file mode 100644
index 00000000..7cc815a6
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraph.cs
@@ -0,0 +1,191 @@
+// 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 System.Threading;
+
+using ICSharpCode.NRefactory.Utils;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// Contains the control flow graph.
+ /// </summary>
+ /// <remarks>Use ControlFlowGraph builder to create instances of the ControlFlowGraph.</remarks>
+ public sealed class ControlFlowGraph
+ {
+ readonly ReadOnlyCollection<ControlFlowNode> nodes;
+
+ public ControlFlowNode EntryPoint {
+ get { return nodes[0]; }
+ }
+
+ public ControlFlowNode RegularExit {
+ get { return nodes[1]; }
+ }
+
+ public ControlFlowNode ExceptionalExit {
+ get { return nodes[2]; }
+ }
+
+ public ReadOnlyCollection<ControlFlowNode> Nodes {
+ get { return nodes; }
+ }
+
+ internal ControlFlowGraph(ControlFlowNode[] nodes)
+ {
+ this.nodes = new ReadOnlyCollection<ControlFlowNode>(nodes);
+ Debug.Assert(EntryPoint.NodeType == ControlFlowNodeType.EntryPoint);
+ Debug.Assert(RegularExit.NodeType == ControlFlowNodeType.RegularExit);
+ Debug.Assert(ExceptionalExit.NodeType == ControlFlowNodeType.ExceptionalExit);
+ }
+
+ public GraphVizGraph ExportGraph()
+ {
+ GraphVizGraph graph = new GraphVizGraph();
+ foreach (ControlFlowNode node in nodes) {
+ graph.AddNode(new GraphVizNode(node.BlockIndex) { label = node.ToString(), shape = "box" });
+ }
+ foreach (ControlFlowNode node in nodes) {
+ foreach (ControlFlowEdge edge in node.Outgoing) {
+ GraphVizEdge e = new GraphVizEdge(edge.Source.BlockIndex, edge.Target.BlockIndex);
+ switch (edge.Type) {
+ case JumpType.Normal:
+ break;
+ case JumpType.LeaveTry:
+ case JumpType.EndFinally:
+ e.color = "red";
+ break;
+ default:
+ e.color = "gray";
+ //e.constraint = false;
+ break;
+ }
+ graph.AddEdge(e);
+ }
+ if (node.ImmediateDominator != null) {
+ graph.AddEdge(new GraphVizEdge(node.ImmediateDominator.BlockIndex, node.BlockIndex) { color = "green", constraint = false });
+ }
+ }
+ return graph;
+ }
+
+ /// <summary>
+ /// Resets "Visited" to false for all nodes in this graph.
+ /// </summary>
+ public void ResetVisited()
+ {
+ foreach (ControlFlowNode node in nodes) {
+ node.Visited = false;
+ }
+ }
+
+ /// <summary>
+ /// Computes the dominator tree.
+ /// </summary>
+ public void ComputeDominance(CancellationToken cancellationToken = default(CancellationToken))
+ {
+ // A Simple, Fast Dominance Algorithm
+ // Keith D. Cooper, Timothy J. Harvey and Ken Kennedy
+
+ EntryPoint.ImmediateDominator = EntryPoint;
+ bool changed = true;
+ while (changed) {
+ changed = false;
+ ResetVisited();
+
+ cancellationToken.ThrowIfCancellationRequested();
+
+ // for all nodes b except the entry point
+ EntryPoint.TraversePreOrder(
+ b => b.Successors,
+ b => {
+ if (b != EntryPoint) {
+ ControlFlowNode newIdom = b.Predecessors.First(block => block.Visited && block != b);
+ // for all other predecessors p of b
+ foreach (ControlFlowNode p in b.Predecessors) {
+ if (p != b && p.ImmediateDominator != null) {
+ newIdom = FindCommonDominator(p, newIdom);
+ }
+ }
+ if (b.ImmediateDominator != newIdom) {
+ b.ImmediateDominator = newIdom;
+ changed = true;
+ }
+ }
+ });
+ }
+ EntryPoint.ImmediateDominator = null;
+ foreach (ControlFlowNode node in nodes) {
+ if (node.ImmediateDominator != null)
+ node.ImmediateDominator.DominatorTreeChildren.Add(node);
+ }
+ }
+
+ static ControlFlowNode FindCommonDominator(ControlFlowNode b1, ControlFlowNode b2)
+ {
+ // Here we could use the postorder numbers to get rid of the hashset, see "A Simple, Fast Dominance Algorithm"
+ HashSet<ControlFlowNode> path1 = new HashSet<ControlFlowNode>();
+ while (b1 != null && path1.Add(b1))
+ b1 = b1.ImmediateDominator;
+ while (b2 != null) {
+ if (path1.Contains(b2))
+ return b2;
+ else
+ b2 = b2.ImmediateDominator;
+ }
+ throw new Exception("No common dominator found!");
+ }
+
+ /// <summary>
+ /// Computes dominance frontiers.
+ /// This method requires that the dominator tree is already computed!
+ /// </summary>
+ public void ComputeDominanceFrontier()
+ {
+ ResetVisited();
+
+ EntryPoint.TraversePostOrder(
+ b => b.DominatorTreeChildren,
+ n => {
+ //logger.WriteLine("Calculating dominance frontier for " + n.Name);
+ n.DominanceFrontier = new HashSet<ControlFlowNode>();
+ // DF_local computation
+ foreach (ControlFlowNode succ in n.Successors) {
+ if (succ.ImmediateDominator != n) {
+ //logger.WriteLine(" local: " + succ.Name);
+ n.DominanceFrontier.Add(succ);
+ }
+ }
+ // DF_up computation
+ foreach (ControlFlowNode child in n.DominatorTreeChildren) {
+ foreach (ControlFlowNode p in child.DominanceFrontier) {
+ if (p.ImmediateDominator != n) {
+ //logger.WriteLine(" DF_up: " + p.Name + " (child=" + child.Name);
+ n.DominanceFrontier.Add(p);
+ }
+ }
+ }
+ });
+ }
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraphBuilder.cs b/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraphBuilder.cs
new file mode 100644
index 00000000..7570884a
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraphBuilder.cs
@@ -0,0 +1,439 @@
+// 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.Diagnostics;
+using System.Linq;
+
+using Mono.Cecil.Cil;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// Constructs the Control Flow Graph from a Cecil method body.
+ /// </summary>
+ public sealed class ControlFlowGraphBuilder
+ {
+ public static ControlFlowGraph Build(MethodBody methodBody)
+ {
+ return new ControlFlowGraphBuilder(methodBody).Build();
+ }
+
+ // This option controls how finally blocks are handled:
+ // false means that the endfinally instruction will jump to any of the leave targets (EndFinally edge type).
+ // true means that a copy of the whole finally block is created for each leave target. In this case, each endfinally node will be connected with the leave
+ // target using a normal edge.
+ bool copyFinallyBlocks = false;
+
+ MethodBody methodBody;
+ int[] offsets; // array index = instruction index; value = IL offset
+ bool[] hasIncomingJumps; // array index = instruction index
+ List<ControlFlowNode> nodes = new List<ControlFlowNode>();
+ ControlFlowNode entryPoint;
+ ControlFlowNode regularExit;
+ ControlFlowNode exceptionalExit;
+
+ ControlFlowGraphBuilder(MethodBody methodBody)
+ {
+ this.methodBody = methodBody;
+ offsets = methodBody.Instructions.Select(i => i.Offset).ToArray();
+ hasIncomingJumps = new bool[methodBody.Instructions.Count];
+
+ entryPoint = new ControlFlowNode(0, 0, ControlFlowNodeType.EntryPoint);
+ nodes.Add(entryPoint);
+ regularExit = new ControlFlowNode(1, -1, ControlFlowNodeType.RegularExit);
+ nodes.Add(regularExit);
+ exceptionalExit = new ControlFlowNode(2, -1, ControlFlowNodeType.ExceptionalExit);
+ nodes.Add(exceptionalExit);
+ Debug.Assert(nodes.Count == 3);
+ }
+
+ /// <summary>
+ /// Determines the index of the instruction (for use with the hasIncomingJumps array)
+ /// </summary>
+ int GetInstructionIndex(Instruction inst)
+ {
+ int index = Array.BinarySearch(offsets, inst.Offset);
+ Debug.Assert(index >= 0);
+ return index;
+ }
+
+ /// <summary>
+ /// Builds the ControlFlowGraph.
+ /// </summary>
+ public ControlFlowGraph Build()
+ {
+ CalculateHasIncomingJumps();
+ CreateNodes();
+ CreateRegularControlFlow();
+ CreateExceptionalControlFlow();
+ if (copyFinallyBlocks)
+ CopyFinallyBlocksIntoLeaveEdges();
+ else
+ TransformLeaveEdges();
+ return new ControlFlowGraph(nodes.ToArray());
+ }
+
+ #region Step 1: calculate which instructions are the targets of jump instructions.
+ void CalculateHasIncomingJumps()
+ {
+ foreach (Instruction inst in methodBody.Instructions) {
+ if (inst.OpCode.OperandType == OperandType.InlineBrTarget || inst.OpCode.OperandType == OperandType.ShortInlineBrTarget) {
+ hasIncomingJumps[GetInstructionIndex((Instruction)inst.Operand)] = true;
+ } else if (inst.OpCode.OperandType == OperandType.InlineSwitch) {
+ foreach (Instruction i in (Instruction[])inst.Operand)
+ hasIncomingJumps[GetInstructionIndex(i)] = true;
+ }
+ }
+ foreach (ExceptionHandler eh in methodBody.ExceptionHandlers) {
+ if (eh.FilterStart != null) {
+ hasIncomingJumps[GetInstructionIndex(eh.FilterStart)] = true;
+ }
+ hasIncomingJumps[GetInstructionIndex(eh.HandlerStart)] = true;
+ }
+ }
+ #endregion
+
+ #region Step 2: create nodes
+ void CreateNodes()
+ {
+ // Step 2a: find basic blocks and create nodes for them
+ for (int i = 0; i < methodBody.Instructions.Count; i++) {
+ Instruction blockStart = methodBody.Instructions[i];
+ ExceptionHandler blockStartEH = FindInnermostExceptionHandler(blockStart.Offset);
+ // try and see how big we can make that block:
+ for (; i + 1 < methodBody.Instructions.Count; i++) {
+ Instruction inst = methodBody.Instructions[i];
+ if (IsBranch(inst.OpCode) || CanThrowException(inst.OpCode))
+ break;
+ if (hasIncomingJumps[i + 1])
+ break;
+ if (inst.Next != null) {
+ // ensure that blocks never contain instructions from different try blocks
+ ExceptionHandler instEH = FindInnermostExceptionHandler(inst.Next.Offset);
+ if (instEH != blockStartEH)
+ break;
+ }
+ }
+
+ nodes.Add(new ControlFlowNode(nodes.Count, blockStart, methodBody.Instructions[i]));
+ }
+ // Step 2b: Create special nodes for the exception handling constructs
+ foreach (ExceptionHandler handler in methodBody.ExceptionHandlers) {
+ if (handler.HandlerType == ExceptionHandlerType.Filter)
+ throw new NotSupportedException();
+ ControlFlowNode endFinallyOrFaultNode = null;
+ if (handler.HandlerType == ExceptionHandlerType.Finally || handler.HandlerType == ExceptionHandlerType.Fault) {
+ endFinallyOrFaultNode = new ControlFlowNode(nodes.Count, handler.HandlerEnd.Offset, ControlFlowNodeType.EndFinallyOrFault);
+ nodes.Add(endFinallyOrFaultNode);
+ }
+ nodes.Add(new ControlFlowNode(nodes.Count, handler, endFinallyOrFaultNode));
+ }
+ }
+ #endregion
+
+ #region Step 3: create edges for the normal flow of control (assuming no exceptions thrown)
+ void CreateRegularControlFlow()
+ {
+ CreateEdge(entryPoint, methodBody.Instructions[0], JumpType.Normal);
+ foreach (ControlFlowNode node in nodes) {
+ if (node.End != null) {
+ // create normal edges from one instruction to the next
+ if (!OpCodeInfo.IsUnconditionalBranch(node.End.OpCode))
+ CreateEdge(node, node.End.Next, JumpType.Normal);
+
+ // create edges for branch instructions
+ if (node.End.OpCode.OperandType == OperandType.InlineBrTarget || node.End.OpCode.OperandType == OperandType.ShortInlineBrTarget) {
+ if (node.End.OpCode == OpCodes.Leave || node.End.OpCode == OpCodes.Leave_S) {
+ var handlerBlock = FindInnermostHandlerBlock(node.End.Offset);
+ if (handlerBlock.NodeType == ControlFlowNodeType.FinallyOrFaultHandler)
+ CreateEdge(node, (Instruction)node.End.Operand, JumpType.LeaveTry);
+ else
+ CreateEdge(node, (Instruction)node.End.Operand, JumpType.Normal);
+ } else {
+ CreateEdge(node, (Instruction)node.End.Operand, JumpType.Normal);
+ }
+ } else if (node.End.OpCode.OperandType == OperandType.InlineSwitch) {
+ foreach (Instruction i in (Instruction[])node.End.Operand)
+ CreateEdge(node, i, JumpType.Normal);
+ }
+
+ // create edges for return instructions
+ if (node.End.OpCode.FlowControl == FlowControl.Return) {
+ switch (node.End.OpCode.Code) {
+ case Code.Ret:
+ CreateEdge(node, regularExit, JumpType.Normal);
+ break;
+ case Code.Endfinally:
+ ControlFlowNode handlerBlock = FindInnermostHandlerBlock(node.End.Offset);
+ if (handlerBlock.EndFinallyOrFaultNode == null)
+ throw new InvalidProgramException("Found endfinally in block " + handlerBlock);
+ CreateEdge(node, handlerBlock.EndFinallyOrFaultNode, JumpType.Normal);
+ break;
+ default:
+ throw new NotSupportedException(node.End.OpCode.ToString());
+ }
+ }
+ }
+ }
+ }
+ #endregion
+
+ #region Step 4: create edges for the exceptional control flow (from instructions that might throw, to the innermost containing exception handler)
+ void CreateExceptionalControlFlow()
+ {
+ foreach (ControlFlowNode node in nodes) {
+ if (node.End != null && CanThrowException(node.End.OpCode)) {
+ CreateEdge(node, FindInnermostExceptionHandlerNode(node.End.Offset), JumpType.JumpToExceptionHandler);
+ }
+ if (node.ExceptionHandler != null) {
+ if (node.EndFinallyOrFaultNode != null) {
+ // For Fault and Finally blocks, create edge from "EndFinally" to next exception handler.
+ // This represents the exception bubbling up after finally block was executed.
+ CreateEdge(node.EndFinallyOrFaultNode, FindParentExceptionHandlerNode(node), JumpType.JumpToExceptionHandler);
+ } else {
+ // For Catch blocks, create edge from "CatchHandler" block (at beginning) to next exception handler.
+ // This represents the exception bubbling up because it did not match the type of the catch block.
+ CreateEdge(node, FindParentExceptionHandlerNode(node), JumpType.JumpToExceptionHandler);
+ }
+ CreateEdge(node, node.ExceptionHandler.HandlerStart, JumpType.Normal);
+ }
+ }
+ }
+
+ ExceptionHandler FindInnermostExceptionHandler(int instructionOffsetInTryBlock)
+ {
+ foreach (ExceptionHandler h in methodBody.ExceptionHandlers) {
+ if (h.TryStart.Offset <= instructionOffsetInTryBlock && instructionOffsetInTryBlock < h.TryEnd.Offset) {
+ return h;
+ }
+ }
+ return null;
+ }
+
+ ControlFlowNode FindInnermostExceptionHandlerNode(int instructionOffsetInTryBlock)
+ {
+ ExceptionHandler h = FindInnermostExceptionHandler(instructionOffsetInTryBlock);
+ if (h != null)
+ return nodes.Single(n => n.ExceptionHandler == h && n.CopyFrom == null);
+ else
+ return exceptionalExit;
+ }
+
+ ControlFlowNode FindInnermostHandlerBlock(int instructionOffset)
+ {
+ foreach (ExceptionHandler h in methodBody.ExceptionHandlers) {
+ if (h.TryStart.Offset <= instructionOffset && instructionOffset < h.TryEnd.Offset
+ || h.HandlerStart.Offset <= instructionOffset && instructionOffset < h.HandlerEnd.Offset)
+ {
+ return nodes.Single(n => n.ExceptionHandler == h && n.CopyFrom == null);
+ }
+ }
+ return exceptionalExit;
+ }
+
+ ControlFlowNode FindParentExceptionHandlerNode(ControlFlowNode exceptionHandler)
+ {
+ Debug.Assert(exceptionHandler.NodeType == ControlFlowNodeType.CatchHandler
+ || exceptionHandler.NodeType == ControlFlowNodeType.FinallyOrFaultHandler);
+ int offset = exceptionHandler.ExceptionHandler.TryStart.Offset;
+ for (int i = exceptionHandler.BlockIndex + 1; i < nodes.Count; i++) {
+ ExceptionHandler h = nodes[i].ExceptionHandler;
+ if (h != null && h.TryStart.Offset <= offset && offset < h.TryEnd.Offset)
+ return nodes[i];
+ }
+ return exceptionalExit;
+ }
+ #endregion
+
+ #region Step 5a: replace LeaveTry edges with EndFinally edges
+ // this is used only for copyFinallyBlocks==false; see Step 5b otherwise
+ void TransformLeaveEdges()
+ {
+ for (int i = nodes.Count - 1; i >= 0; i--) {
+ ControlFlowNode node = nodes[i];
+ if (node.End != null && node.Outgoing.Count == 1 && node.Outgoing[0].Type == JumpType.LeaveTry) {
+ Debug.Assert(node.End.OpCode == OpCodes.Leave || node.End.OpCode == OpCodes.Leave_S);
+
+ ControlFlowNode target = node.Outgoing[0].Target;
+ // remove the edge
+ target.Incoming.Remove(node.Outgoing[0]);
+ node.Outgoing.Clear();
+
+ ControlFlowNode handler = FindInnermostExceptionHandlerNode(node.End.Offset);
+ Debug.Assert(handler.NodeType == ControlFlowNodeType.FinallyOrFaultHandler);
+
+ CreateEdge(node, handler, JumpType.Normal);
+ CreateEdge(handler.EndFinallyOrFaultNode, target, JumpType.EndFinally);
+ }
+ }
+ }
+ #endregion
+
+ #region Step 5b: copy finally blocks into the LeaveTry edges
+ void CopyFinallyBlocksIntoLeaveEdges()
+ {
+ // We need to process try-finally blocks inside-out.
+ // We'll do that by going through all instructions in reverse order
+ for (int i = nodes.Count - 1; i >= 0; i--) {
+ ControlFlowNode node = nodes[i];
+ if (node.End != null && node.Outgoing.Count == 1 && node.Outgoing[0].Type == JumpType.LeaveTry) {
+ Debug.Assert(node.End.OpCode == OpCodes.Leave || node.End.OpCode == OpCodes.Leave_S);
+
+ ControlFlowNode target = node.Outgoing[0].Target;
+ // remove the edge
+ target.Incoming.Remove(node.Outgoing[0]);
+ node.Outgoing.Clear();
+
+ ControlFlowNode handler = FindInnermostExceptionHandlerNode(node.End.Offset);
+ Debug.Assert(handler.NodeType == ControlFlowNodeType.FinallyOrFaultHandler);
+
+ ControlFlowNode copy = CopyFinallySubGraph(handler, handler.EndFinallyOrFaultNode, target);
+ CreateEdge(node, copy, JumpType.Normal);
+ }
+ }
+ }
+
+ /// <summary>
+ /// Creates a copy of all nodes pointing to 'end' and replaces those references with references to 'newEnd'.
+ /// Nodes pointing to the copied node are copied recursively to update those references, too.
+ /// This recursion stops at 'start'. The modified version of start is returned.
+ /// </summary>
+ ControlFlowNode CopyFinallySubGraph(ControlFlowNode start, ControlFlowNode end, ControlFlowNode newEnd)
+ {
+ return new CopyFinallySubGraphLogic(this, start, end, newEnd).CopyFinallySubGraph();
+ }
+
+ class CopyFinallySubGraphLogic
+ {
+ readonly ControlFlowGraphBuilder builder;
+ readonly Dictionary<ControlFlowNode, ControlFlowNode> oldToNew = new Dictionary<ControlFlowNode, ControlFlowNode>();
+ readonly ControlFlowNode start;
+ readonly ControlFlowNode end;
+ readonly ControlFlowNode newEnd;
+
+ public CopyFinallySubGraphLogic(ControlFlowGraphBuilder builder, ControlFlowNode start, ControlFlowNode end, ControlFlowNode newEnd)
+ {
+ this.builder = builder;
+ this.start = start;
+ this.end = end;
+ this.newEnd = newEnd;
+ }
+
+ internal ControlFlowNode CopyFinallySubGraph()
+ {
+ foreach (ControlFlowNode n in end.Predecessors) {
+ CollectNodes(n);
+ }
+ foreach (var pair in oldToNew)
+ ReconstructEdges(pair.Key, pair.Value);
+ return GetNew(start);
+ }
+
+ void CollectNodes(ControlFlowNode node)
+ {
+ if (node == end || node == newEnd)
+ throw new InvalidOperationException("unexpected cycle involving finally construct");
+ if (!oldToNew.ContainsKey(node)) {
+ int newBlockIndex = builder.nodes.Count;
+ ControlFlowNode copy;
+ switch (node.NodeType) {
+ case ControlFlowNodeType.Normal:
+ copy = new ControlFlowNode(newBlockIndex, node.Start, node.End);
+ break;
+ case ControlFlowNodeType.FinallyOrFaultHandler:
+ copy = new ControlFlowNode(newBlockIndex, node.ExceptionHandler, node.EndFinallyOrFaultNode);
+ break;
+ default:
+ // other nodes shouldn't occur when copying finally blocks
+ throw new NotSupportedException(node.NodeType.ToString());
+ }
+ copy.CopyFrom = node;
+ builder.nodes.Add(copy);
+ oldToNew.Add(node, copy);
+
+ if (node != start) {
+ foreach (ControlFlowNode n in node.Predecessors) {
+ CollectNodes(n);
+ }
+ }
+ }
+ }
+
+ void ReconstructEdges(ControlFlowNode oldNode, ControlFlowNode newNode)
+ {
+ foreach (ControlFlowEdge oldEdge in oldNode.Outgoing) {
+ builder.CreateEdge(newNode, GetNew(oldEdge.Target), oldEdge.Type);
+ }
+ }
+
+ ControlFlowNode GetNew(ControlFlowNode oldNode)
+ {
+ if (oldNode == end)
+ return newEnd;
+ ControlFlowNode newNode;
+ if (oldToNew.TryGetValue(oldNode, out newNode))
+ return newNode;
+ return oldNode;
+ }
+ }
+ #endregion
+
+ #region CreateEdge methods
+ void CreateEdge(ControlFlowNode fromNode, Instruction toInstruction, JumpType type)
+ {
+ CreateEdge(fromNode, nodes.Single(n => n.Start == toInstruction), type);
+ }
+
+ void CreateEdge(ControlFlowNode fromNode, ControlFlowNode toNode, JumpType type)
+ {
+ ControlFlowEdge edge = new ControlFlowEdge(fromNode, toNode, type);
+ fromNode.Outgoing.Add(edge);
+ toNode.Incoming.Add(edge);
+ }
+ #endregion
+
+ #region OpCode info
+ static bool CanThrowException(OpCode opcode)
+ {
+ if (opcode.OpCodeType == OpCodeType.Prefix)
+ return false;
+ return OpCodeInfo.Get(opcode).CanThrow;
+ }
+
+ static bool IsBranch(OpCode opcode)
+ {
+ if (opcode.OpCodeType == OpCodeType.Prefix)
+ return false;
+ switch (opcode.FlowControl) {
+ case FlowControl.Cond_Branch:
+ case FlowControl.Branch:
+ case FlowControl.Throw:
+ case FlowControl.Return:
+ return true;
+ case FlowControl.Next:
+ case FlowControl.Call:
+ return false;
+ default:
+ throw new NotSupportedException(opcode.FlowControl.ToString());
+ }
+ }
+ #endregion
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowNode.cs b/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowNode.cs
new file mode 100644
index 00000000..83294fd9
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowNode.cs
@@ -0,0 +1,305 @@
+// 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.Diagnostics;
+using System.IO;
+using System.Linq;
+
+using ICSharpCode.Decompiler.Disassembler;
+using Mono.Cecil.Cil;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// Type of the control flow node
+ /// </summary>
+ public enum ControlFlowNodeType
+ {
+ /// <summary>
+ /// A normal node represents a basic block.
+ /// </summary>
+ Normal,
+ /// <summary>
+ /// The entry point of the method.
+ /// </summary>
+ EntryPoint,
+ /// <summary>
+ /// The exit point of the method (every ret instruction branches to this node)
+ /// </summary>
+ RegularExit,
+ /// <summary>
+ /// This node represents leaving a method irregularly by throwing an exception.
+ /// </summary>
+ ExceptionalExit,
+ /// <summary>
+ /// This node is used as a header for exception handler blocks.
+ /// </summary>
+ CatchHandler,
+ /// <summary>
+ /// This node is used as a header for finally blocks and fault blocks.
+ /// Every leave instruction in the try block leads to the handler of the containing finally block;
+ /// and exceptional control flow also leads to this handler.
+ /// </summary>
+ FinallyOrFaultHandler,
+ /// <summary>
+ /// This node is used as footer for finally blocks and fault blocks.
+ /// Depending on the "copyFinallyBlocks" option used when creating the graph, it is connected with all leave targets using
+ /// EndFinally edges (when not copying); or with a specific leave target using a normal edge (when copying).
+ /// For fault blocks, an exception edge is used to represent the "re-throwing" of the exception.
+ /// </summary>
+ EndFinallyOrFault
+ }
+
+ /// <summary>
+ /// Represents a block in the control flow graph.
+ /// </summary>
+ public sealed class ControlFlowNode
+ {
+ /// <summary>
+ /// Index of this node in the ControlFlowGraph.Nodes collection.
+ /// </summary>
+ public readonly int BlockIndex;
+
+ /// <summary>
+ /// Gets the IL offset of this node.
+ /// </summary>
+ public readonly int Offset;
+
+ /// <summary>
+ /// Type of the node.
+ /// </summary>
+ public readonly ControlFlowNodeType NodeType;
+
+ /// <summary>
+ /// If this node is a FinallyOrFaultHandler node, this field points to the corresponding EndFinallyOrFault node.
+ /// Otherwise, this field is null.
+ /// </summary>
+ public readonly ControlFlowNode EndFinallyOrFaultNode;
+
+ /// <summary>
+ /// Visited flag, used in various algorithms.
+ /// Before using it in your algorithm, reset it to false by calling ControlFlowGraph.ResetVisited();
+ /// </summary>
+ public bool Visited;
+
+ /// <summary>
+ /// Gets whether this node is reachable. Requires that dominance is computed!
+ /// </summary>
+ public bool IsReachable {
+ get { return ImmediateDominator != null || NodeType == ControlFlowNodeType.EntryPoint; }
+ }
+
+ /// <summary>
+ /// Signalizes that this node is a copy of another node.
+ /// </summary>
+ public ControlFlowNode CopyFrom { get; internal set; }
+
+ /// <summary>
+ /// Gets the immediate dominator (the parent in the dominator tree).
+ /// Null if dominance has not been calculated; or if the node is unreachable.
+ /// </summary>
+ public ControlFlowNode ImmediateDominator { get; internal set; }
+
+ /// <summary>
+ /// List of children in the dominator tree.
+ /// </summary>
+ public readonly List<ControlFlowNode> DominatorTreeChildren = new List<ControlFlowNode>();
+
+ /// <summary>
+ /// The dominance frontier of this node.
+ /// This is the set of nodes for which this node dominates a predecessor, but which are not strictly dominated by this node.
+ /// </summary>
+ /// <remarks>
+ /// b.DominanceFrontier = { y in CFG; (exists p in predecessors(y): b dominates p) and not (b strictly dominates y)}
+ /// </remarks>
+ public HashSet<ControlFlowNode> DominanceFrontier;
+
+ /// <summary>
+ /// Start of code block represented by this node. Only set for nodetype == Normal.
+ /// </summary>
+ public readonly Instruction Start;
+
+ /// <summary>
+ /// End of the code block represented by this node. Only set for nodetype == Normal.
+ /// The end is exclusive, the end instruction itself does not belong to this block.
+ /// </summary>
+ public readonly Instruction End;
+
+ /// <summary>
+ /// Gets the exception handler associated with this node.
+ /// Only set for nodetype == CatchHandler or nodetype == FinallyOrFaultHandler.
+ /// </summary>
+ public readonly ExceptionHandler ExceptionHandler;
+
+ /// <summary>
+ /// List of incoming control flow edges.
+ /// </summary>
+ public readonly List<ControlFlowEdge> Incoming = new List<ControlFlowEdge>();
+
+ /// <summary>
+ /// List of outgoing control flow edges.
+ /// </summary>
+ public readonly List<ControlFlowEdge> Outgoing = new List<ControlFlowEdge>();
+
+ /// <summary>
+ /// Any user data
+ /// </summary>
+ public object UserData;
+
+ internal ControlFlowNode(int blockIndex, int offset, ControlFlowNodeType nodeType)
+ {
+ BlockIndex = blockIndex;
+ Offset = offset;
+ NodeType = nodeType;
+ }
+
+ internal ControlFlowNode(int blockIndex, Instruction start, Instruction end)
+ {
+ if (start == null)
+ throw new ArgumentNullException("start");
+ if (end == null)
+ throw new ArgumentNullException("end");
+ BlockIndex = blockIndex;
+ NodeType = ControlFlowNodeType.Normal;
+ Start = start;
+ End = end;
+ Offset = start.Offset;
+ }
+
+ internal ControlFlowNode(int blockIndex, ExceptionHandler exceptionHandler, ControlFlowNode endFinallyOrFaultNode)
+ {
+ BlockIndex = blockIndex;
+ NodeType = endFinallyOrFaultNode != null ? ControlFlowNodeType.FinallyOrFaultHandler : ControlFlowNodeType.CatchHandler;
+ ExceptionHandler = exceptionHandler;
+ EndFinallyOrFaultNode = endFinallyOrFaultNode;
+ Debug.Assert((exceptionHandler.HandlerType == ExceptionHandlerType.Finally || exceptionHandler.HandlerType == ExceptionHandlerType.Fault) == (endFinallyOrFaultNode != null));
+ Offset = exceptionHandler.HandlerStart.Offset;
+ }
+
+ /// <summary>
+ /// Gets all predecessors (=sources of incoming edges)
+ /// </summary>
+ public IEnumerable<ControlFlowNode> Predecessors {
+ get {
+ return Incoming.Select(e => e.Source);
+ }
+ }
+
+ /// <summary>
+ /// Gets all successors (=targets of outgoing edges)
+ /// </summary>
+ public IEnumerable<ControlFlowNode> Successors {
+ get {
+ return Outgoing.Select(e => e.Target);
+ }
+ }
+
+ /// <summary>
+ /// Gets all instructions in this node.
+ /// Returns an empty list for special nodes that don't have any instructions.
+ /// </summary>
+ public IEnumerable<Instruction> Instructions {
+ get {
+ Instruction inst = Start;
+ if (inst != null) {
+ yield return inst;
+ while (inst != End) {
+ inst = inst.Next;
+ yield return inst;
+ }
+ }
+ }
+ }
+
+ public void TraversePreOrder(Func<ControlFlowNode, IEnumerable<ControlFlowNode>> children, Action<ControlFlowNode> visitAction)
+ {
+ if (Visited)
+ return;
+ Visited = true;
+ visitAction(this);
+ foreach (ControlFlowNode t in children(this))
+ t.TraversePreOrder(children, visitAction);
+ }
+
+ public void TraversePostOrder(Func<ControlFlowNode, IEnumerable<ControlFlowNode>> children, Action<ControlFlowNode> visitAction)
+ {
+ if (Visited)
+ return;
+ Visited = true;
+ foreach (ControlFlowNode t in children(this))
+ t.TraversePostOrder(children, visitAction);
+ visitAction(this);
+ }
+
+ public override string ToString()
+ {
+ StringWriter writer = new StringWriter();
+ switch (NodeType) {
+ case ControlFlowNodeType.Normal:
+ writer.Write("Block #{0}", BlockIndex);
+ if (Start != null)
+ writer.Write(": IL_{0:x4}", Start.Offset);
+ if (End != null)
+ writer.Write(" to IL_{0:x4}", End.GetEndOffset());
+ break;
+ case ControlFlowNodeType.CatchHandler:
+ case ControlFlowNodeType.FinallyOrFaultHandler:
+ writer.Write("Block #{0}: {1}: ", BlockIndex, NodeType);
+ DisassemblerHelpers.WriteTo(ExceptionHandler, new PlainTextOutput(writer));
+ break;
+ default:
+ writer.Write("Block #{0}: {1}", BlockIndex, NodeType);
+ break;
+ }
+// if (ImmediateDominator != null) {
+// writer.WriteLine();
+// writer.Write("ImmediateDominator: #{0}", ImmediateDominator.BlockIndex);
+// }
+ if (DominanceFrontier != null && DominanceFrontier.Any()) {
+ writer.WriteLine();
+ writer.Write("DominanceFrontier: " + string.Join(",", DominanceFrontier.OrderBy(d => d.BlockIndex).Select(d => d.BlockIndex.ToString())));
+ }
+ foreach (Instruction inst in Instructions) {
+ writer.WriteLine();
+ DisassemblerHelpers.WriteTo(inst, new PlainTextOutput(writer));
+ }
+ if (UserData != null) {
+ writer.WriteLine();
+ writer.Write(UserData.ToString());
+ }
+ return writer.ToString();
+ }
+
+ /// <summary>
+ /// Gets whether <c>this</c> dominates <paramref name="node"/>.
+ /// </summary>
+ public bool Dominates(ControlFlowNode node)
+ {
+ // TODO: this can be made O(1) by numbering the dominator tree
+ ControlFlowNode tmp = node;
+ while (tmp != null) {
+ if (tmp == this)
+ return true;
+ tmp = tmp.ImmediateDominator;
+ }
+ return false;
+ }
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/ControlStructureDetector.cs b/ICSharpCode.Decompiler/FlowAnalysis/ControlStructureDetector.cs
new file mode 100644
index 00000000..b7b77e07
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/ControlStructureDetector.cs
@@ -0,0 +1,241 @@
+// 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.Diagnostics;
+using System.Linq;
+using System.Threading;
+using Mono.Cecil.Cil;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// Detects the structure of the control flow (exception blocks and loops).
+ /// </summary>
+ public class ControlStructureDetector
+ {
+ public static ControlStructure DetectStructure(ControlFlowGraph g, IEnumerable<ExceptionHandler> exceptionHandlers, CancellationToken cancellationToken)
+ {
+ ControlStructure root = new ControlStructure(new HashSet<ControlFlowNode>(g.Nodes), g.EntryPoint, ControlStructureType.Root);
+ // First build a structure tree out of the exception table
+ DetectExceptionHandling(root, g, exceptionHandlers);
+ // Then run the loop detection.
+ DetectLoops(g, root, cancellationToken);
+ return root;
+ }
+
+ #region Exception Handling
+ static void DetectExceptionHandling(ControlStructure current, ControlFlowGraph g, IEnumerable<ExceptionHandler> exceptionHandlers)
+ {
+ // We rely on the fact that the exception handlers are sorted so that the innermost come first.
+ // For each exception handler, we determine the nodes and substructures inside that handler, and move them into a new substructure.
+ // This is always possible because exception handlers are guaranteed (by the CLR spec) to be properly nested and non-overlapping;
+ // so they directly form the tree that we need.
+ foreach (ExceptionHandler eh in exceptionHandlers) {
+ var tryNodes = FindNodes(current, eh.TryStart, eh.TryEnd);
+ current.Nodes.ExceptWith(tryNodes);
+ ControlStructure tryBlock = new ControlStructure(
+ tryNodes,
+ g.Nodes.Single(n => n.Start == eh.TryStart),
+ ControlStructureType.Try);
+ tryBlock.ExceptionHandler = eh;
+ MoveControlStructures(current, tryBlock, eh.TryStart, eh.TryEnd);
+ current.Children.Add(tryBlock);
+
+ if (eh.FilterStart != null) {
+ throw new NotSupportedException();
+ }
+
+ var handlerNodes = FindNodes(current, eh.HandlerStart, eh.HandlerEnd);
+ var handlerNode = current.Nodes.Single(n => n.ExceptionHandler == eh);
+ handlerNodes.Add(handlerNode);
+ if (handlerNode.EndFinallyOrFaultNode != null)
+ handlerNodes.Add(handlerNode.EndFinallyOrFaultNode);
+ current.Nodes.ExceptWith(handlerNodes);
+ ControlStructure handlerBlock = new ControlStructure(
+ handlerNodes, handlerNode, ControlStructureType.Handler);
+ handlerBlock.ExceptionHandler = eh;
+ MoveControlStructures(current, handlerBlock, eh.HandlerStart, eh.HandlerEnd);
+ current.Children.Add(handlerBlock);
+ }
+ }
+
+ /// <summary>
+ /// Removes all nodes from start to end (exclusive) from this ControlStructure and moves them to the target structure.
+ /// </summary>
+ static HashSet<ControlFlowNode> FindNodes(ControlStructure current, Instruction startInst, Instruction endInst)
+ {
+ HashSet<ControlFlowNode> result = new HashSet<ControlFlowNode>();
+ int start = startInst.Offset;
+ int end = endInst.Offset;
+ foreach (var node in current.Nodes.ToArray()) {
+ if (node.Start != null && start <= node.Start.Offset && node.Start.Offset < end) {
+ result.Add(node);
+ }
+ }
+ return result;
+ }
+
+ static void MoveControlStructures(ControlStructure current, ControlStructure target, Instruction startInst, Instruction endInst)
+ {
+ for (int i = 0; i < current.Children.Count; i++) {
+ var child = current.Children[i];
+ if (startInst.Offset <= child.EntryPoint.Offset && child.EntryPoint.Offset < endInst.Offset) {
+ current.Children.RemoveAt(i--);
+ target.Children.Add(child);
+ target.AllNodes.UnionWith(child.AllNodes);
+ }
+ }
+ }
+ #endregion
+
+ #region Loop Detection
+ // Loop detection works like this:
+ // We find a top-level loop by looking for its entry point, which is characterized by a node dominating its own predecessor.
+ // Then we determine all other nodes that belong to such a loop (all nodes which lead to the entry point, and are dominated by it).
+ // Finally, we check whether our result conforms with potential existing exception structures, and create the substructure for the loop if successful.
+
+ // This algorithm is applied recursively for any substructures (both detected loops and exception blocks)
+
+ // But maybe we should get rid of this complex stuff and instead treat every backward jump as a loop?
+ // That should still work with the IL produced by compilers, and has the advantage that the detected loop bodies are consecutive IL regions.
+
+ static void DetectLoops(ControlFlowGraph g, ControlStructure current, CancellationToken cancellationToken)
+ {
+ if (!current.EntryPoint.IsReachable)
+ return;
+ g.ResetVisited();
+ cancellationToken.ThrowIfCancellationRequested();
+ FindLoops(current, current.EntryPoint);
+ foreach (ControlStructure loop in current.Children)
+ DetectLoops(g, loop, cancellationToken);
+ }
+
+ static void FindLoops(ControlStructure current, ControlFlowNode node)
+ {
+ if (node.Visited)
+ return;
+ node.Visited = true;
+ if (current.Nodes.Contains(node)
+ && node.DominanceFrontier.Contains(node)
+ && !(node == current.EntryPoint && current.Type == ControlStructureType.Loop))
+ {
+ HashSet<ControlFlowNode> loopContents = new HashSet<ControlFlowNode>();
+ FindLoopContents(current, loopContents, node, node);
+ List<ControlStructure> containedChildStructures = new List<ControlStructure>();
+ bool invalidNesting = false;
+ foreach (ControlStructure childStructure in current.Children) {
+ if (childStructure.AllNodes.IsSubsetOf(loopContents)) {
+ containedChildStructures.Add(childStructure);
+ } else if (childStructure.AllNodes.Intersect(loopContents).Any()) {
+ invalidNesting = true;
+ }
+ }
+ if (!invalidNesting) {
+ current.Nodes.ExceptWith(loopContents);
+ ControlStructure ctl = new ControlStructure(loopContents, node, ControlStructureType.Loop);
+ foreach (ControlStructure childStructure in containedChildStructures) {
+ ctl.Children.Add(childStructure);
+ current.Children.Remove(childStructure);
+ ctl.Nodes.ExceptWith(childStructure.AllNodes);
+ }
+ current.Children.Add(ctl);
+ }
+ }
+ foreach (var edge in node.Outgoing) {
+ FindLoops(current, edge.Target);
+ }
+ }
+
+ static void FindLoopContents(ControlStructure current, HashSet<ControlFlowNode> loopContents, ControlFlowNode loopHead, ControlFlowNode node)
+ {
+ if (current.AllNodes.Contains(node) && loopHead.Dominates(node) && loopContents.Add(node)) {
+ foreach (var edge in node.Incoming) {
+ FindLoopContents(current, loopContents, loopHead, edge.Source);
+ }
+ }
+ }
+ #endregion
+ }
+
+ public enum ControlStructureType
+ {
+ /// <summary>
+ /// The root block of the method
+ /// </summary>
+ Root,
+ /// <summary>
+ /// A nested control structure representing a loop.
+ /// </summary>
+ Loop,
+ /// <summary>
+ /// A nested control structure representing a try block.
+ /// </summary>
+ Try,
+ /// <summary>
+ /// A nested control structure representing a catch, finally, or fault block.
+ /// </summary>
+ Handler,
+ /// <summary>
+ /// A nested control structure representing an exception filter block.
+ /// </summary>
+ Filter
+ }
+
+ /// <summary>
+ /// Represents the structure detected by the <see cref="ControlStructureDetector"/>.
+ ///
+ /// This is a tree of ControlStructure nodes. Each node contains a set of CFG nodes, and every CFG node is contained in exactly one ControlStructure node.
+ /// </summary>
+ public class ControlStructure
+ {
+ public readonly ControlStructureType Type;
+ public readonly List<ControlStructure> Children = new List<ControlStructure>();
+
+ /// <summary>
+ /// The nodes in this control structure.
+ /// </summary>
+ public readonly HashSet<ControlFlowNode> Nodes;
+
+ /// <summary>
+ /// The nodes in this control structure and in all child control structures.
+ /// </summary>
+ public readonly HashSet<ControlFlowNode> AllNodes;
+
+ /// <summary>
+ /// The entry point of this control structure.
+ /// </summary>
+ public readonly ControlFlowNode EntryPoint;
+
+ /// <summary>
+ /// The exception handler associated with this Try,Handler or Finally structure.
+ /// </summary>
+ public ExceptionHandler ExceptionHandler;
+
+ public ControlStructure(HashSet<ControlFlowNode> nodes, ControlFlowNode entryPoint, ControlStructureType type)
+ {
+ if (nodes == null)
+ throw new ArgumentNullException("nodes");
+ Nodes = nodes;
+ EntryPoint = entryPoint;
+ Type = type;
+ AllNodes = new HashSet<ControlFlowNode>(nodes);
+ }
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/OpCodeInfo.cs b/ICSharpCode.Decompiler/FlowAnalysis/OpCodeInfo.cs
new file mode 100644
index 00000000..e0dc724f
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/OpCodeInfo.cs
@@ -0,0 +1,312 @@
+// 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.Linq;
+
+using Mono.Cecil.Cil;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// Additional info about opcodes.
+ /// </summary>
+ internal sealed class OpCodeInfo
+ {
+ public static bool IsUnconditionalBranch(OpCode opcode)
+ {
+ if (opcode.OpCodeType == OpCodeType.Prefix)
+ return false;
+ switch (opcode.FlowControl) {
+ case FlowControl.Branch:
+ case FlowControl.Throw:
+ case FlowControl.Return:
+ return true;
+ case FlowControl.Next:
+ case FlowControl.Call:
+ case FlowControl.Cond_Branch:
+ return false;
+ default:
+ throw new NotSupportedException(opcode.FlowControl.ToString());
+ }
+ }
+
+ static readonly OpCodeInfo[] knownOpCodes = {
+ #region Base Instructions
+ new OpCodeInfo(OpCodes.Add) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Add_Ovf) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Add_Ovf_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.And) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Arglist) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Beq) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Beq_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Bge) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Bge_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Bge_Un) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Bge_Un_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Bgt) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Bgt_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Bgt_Un) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Bgt_Un_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ble) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ble_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ble_Un) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ble_Un_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Blt) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Blt_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Blt_Un) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Blt_Un_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Bne_Un) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Bne_Un_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Br) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Br_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Break) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Brfalse) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Brfalse_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Brtrue) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Brtrue_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Call) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Calli) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ceq) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Cgt) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Cgt_Un) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ckfinite) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Clt) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Clt_Un) { CanThrow = false },
+ // conv.<to type>
+ new OpCodeInfo(OpCodes.Conv_I1) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_I2) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_I4) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_I8) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_R4) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_R8) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_U1) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_U2) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_U4) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_U8) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_I) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_U) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Conv_R_Un) { CanThrow = false },
+ // conv.ovf.<to type>
+ new OpCodeInfo(OpCodes.Conv_Ovf_I1) { CanThrow = true},
+ new OpCodeInfo(OpCodes.Conv_Ovf_I2) { CanThrow = true},
+ new OpCodeInfo(OpCodes.Conv_Ovf_I4) { CanThrow = true},
+ new OpCodeInfo(OpCodes.Conv_Ovf_I8) { CanThrow = true},
+ new OpCodeInfo(OpCodes.Conv_Ovf_U1) { CanThrow = true},
+ new OpCodeInfo(OpCodes.Conv_Ovf_U2) { CanThrow = true},
+ new OpCodeInfo(OpCodes.Conv_Ovf_U4) { CanThrow = true},
+ new OpCodeInfo(OpCodes.Conv_Ovf_U8) { CanThrow = true},
+ new OpCodeInfo(OpCodes.Conv_Ovf_I) { CanThrow = true},
+ new OpCodeInfo(OpCodes.Conv_Ovf_U) { CanThrow = true},
+ // conv.ovf.<to type>.un
+ new OpCodeInfo(OpCodes.Conv_Ovf_I1_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Conv_Ovf_I2_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Conv_Ovf_I4_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Conv_Ovf_I8_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Conv_Ovf_U1_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Conv_Ovf_U2_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Conv_Ovf_U4_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Conv_Ovf_U8_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Conv_Ovf_I_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Conv_Ovf_U_Un) { CanThrow = true },
+
+ //new OpCodeInfo(OpCodes.Cpblk) { CanThrow = true }, - no idea whether this might cause trouble for the type system, C# shouldn't use it so I'll disable it
+ new OpCodeInfo(OpCodes.Div) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Div_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Dup) { CanThrow = true, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Endfilter) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Endfinally) { CanThrow = false },
+ //new OpCodeInfo(OpCodes.Initblk) { CanThrow = true }, - no idea whether this might cause trouble for the type system, C# shouldn't use it so I'll disable it
+ //new OpCodeInfo(OpCodes.Jmp) { CanThrow = true } - We don't support non-local control transfers.
+ new OpCodeInfo(OpCodes.Ldarg) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldarg_0) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldarg_1) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldarg_2) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldarg_3) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldarg_S) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldarga) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldarga_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4_M1) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4_0) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4_1) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4_2) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4_3) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4_4) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4_5) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4_6) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4_7) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4_8) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I4_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_I8) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_R4) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldc_R8) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldftn) { CanThrow = false },
+ // ldind.<type>
+ new OpCodeInfo(OpCodes.Ldind_I1) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ldind_I2) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ldind_I4) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ldind_I8) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ldind_U1) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ldind_U2) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ldind_U4) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ldind_R4) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ldind_R8) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ldind_I) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ldind_Ref) { CanThrow = true },
+ // the ldloc exceptions described in the spec can only occur on methods without .localsinit - but csc always sets that flag
+ new OpCodeInfo(OpCodes.Ldloc) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldloc_0) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldloc_1) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldloc_2) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldloc_3) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldloc_S) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Ldloca) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldloca_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldnull) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Leave) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Leave_S) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Localloc) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Mul) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Mul_Ovf) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Mul_Ovf_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Neg) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Nop) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Not) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Or) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Pop) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Rem) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Rem_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Ret) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Shl) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Shr) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Shr_Un) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Starg) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Starg_S) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Stind_I1) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Stind_I2) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Stind_I4) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Stind_I8) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Stind_R4) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Stind_R8) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Stind_I) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Stind_Ref) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Stloc) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Stloc_0) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Stloc_1) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Stloc_2) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Stloc_3) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Stloc_S) { CanThrow = false, IsMoveInstruction = true },
+ new OpCodeInfo(OpCodes.Sub) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Sub_Ovf) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Sub_Ovf_Un) { CanThrow = true },
+ new OpCodeInfo(OpCodes.Switch) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Xor) { CanThrow = false },
+ #endregion
+ #region Object model instructions
+ // CanThrow is true by default - most OO instructions can throw, so we don't specify CanThrow all of the time
+ new OpCodeInfo(OpCodes.Box),
+ new OpCodeInfo(OpCodes.Callvirt),
+ new OpCodeInfo(OpCodes.Castclass),
+ new OpCodeInfo(OpCodes.Cpobj),
+ new OpCodeInfo(OpCodes.Initobj) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Isinst) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldelem_Any),
+ // ldelem.<type>
+ new OpCodeInfo(OpCodes.Ldelem_I) ,
+ new OpCodeInfo(OpCodes.Ldelem_I1),
+ new OpCodeInfo(OpCodes.Ldelem_I2),
+ new OpCodeInfo(OpCodes.Ldelem_I4),
+ new OpCodeInfo(OpCodes.Ldelem_I8),
+ new OpCodeInfo(OpCodes.Ldelem_R4),
+ new OpCodeInfo(OpCodes.Ldelem_R8),
+ new OpCodeInfo(OpCodes.Ldelem_Ref),
+ new OpCodeInfo(OpCodes.Ldelem_U1),
+ new OpCodeInfo(OpCodes.Ldelem_U2),
+ new OpCodeInfo(OpCodes.Ldelem_U4),
+ new OpCodeInfo(OpCodes.Ldelema) ,
+ new OpCodeInfo(OpCodes.Ldfld) ,
+ new OpCodeInfo(OpCodes.Ldflda),
+ new OpCodeInfo(OpCodes.Ldlen) ,
+ new OpCodeInfo(OpCodes.Ldobj) ,
+ new OpCodeInfo(OpCodes.Ldsfld),
+ new OpCodeInfo(OpCodes.Ldsflda),
+ new OpCodeInfo(OpCodes.Ldstr) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldtoken) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Ldvirtftn),
+ new OpCodeInfo(OpCodes.Mkrefany),
+ new OpCodeInfo(OpCodes.Newarr),
+ new OpCodeInfo(OpCodes.Newobj),
+ new OpCodeInfo(OpCodes.Refanytype) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Refanyval),
+ new OpCodeInfo(OpCodes.Rethrow),
+ new OpCodeInfo(OpCodes.Sizeof) { CanThrow = false },
+ new OpCodeInfo(OpCodes.Stelem_Any),
+ new OpCodeInfo(OpCodes.Stelem_I1),
+ new OpCodeInfo(OpCodes.Stelem_I2),
+ new OpCodeInfo(OpCodes.Stelem_I4),
+ new OpCodeInfo(OpCodes.Stelem_I8),
+ new OpCodeInfo(OpCodes.Stelem_R4),
+ new OpCodeInfo(OpCodes.Stelem_R8),
+ new OpCodeInfo(OpCodes.Stelem_Ref),
+ new OpCodeInfo(OpCodes.Stfld),
+ new OpCodeInfo(OpCodes.Stobj),
+ new OpCodeInfo(OpCodes.Stsfld),
+ new OpCodeInfo(OpCodes.Throw),
+ new OpCodeInfo(OpCodes.Unbox),
+ new OpCodeInfo(OpCodes.Unbox_Any),
+ #endregion
+ };
+ static readonly Dictionary<Code, OpCodeInfo> knownOpCodeDict = knownOpCodes.ToDictionary(info => info.OpCode.Code);
+
+ public static OpCodeInfo Get(OpCode opCode)
+ {
+ return Get(opCode.Code);
+ }
+
+ public static OpCodeInfo Get(Code code)
+ {
+ OpCodeInfo info;
+ if (knownOpCodeDict.TryGetValue(code, out info))
+ return info;
+ else
+ throw new NotSupportedException(code.ToString());
+ }
+
+ OpCode opcode;
+
+ OpCodeInfo(OpCode opcode)
+ {
+ this.opcode = opcode;
+ CanThrow = true;
+ }
+
+ public OpCode OpCode { get { return opcode; } }
+
+ /// <summary>
+ /// 'Move' kind of instructions have one input (may be stack or local variable) and copy that value to all outputs (again stack or local variable).
+ /// </summary>
+ public bool IsMoveInstruction { get; private set; }
+
+ /// <summary>
+ /// Specifies whether this opcode is capable of throwing exceptions.
+ /// </summary>
+ public bool CanThrow { get; private set; }
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/SimplifyByRefCalls.cs b/ICSharpCode.Decompiler/FlowAnalysis/SimplifyByRefCalls.cs
new file mode 100644
index 00000000..42c30914
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/SimplifyByRefCalls.cs
@@ -0,0 +1,174 @@
+// 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.Diagnostics;
+
+using Mono.Cecil;
+using Mono.Cecil.Cil;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// This is a transformation working on SSA form.
+ /// It removes ldloca instructions and replaces them with SpecialOpCode.PrepareByOutCall or SpecialOpCode.PrepareByRefCall.
+ /// This then allows the variable that had its address taken to also be transformed into SSA.
+ /// </summary>
+ internal sealed class SimplifyByRefCalls
+ {
+ public static bool MakeByRefCallsSimple(SsaForm ssaForm)
+ {
+ SimplifyByRefCalls instance = new SimplifyByRefCalls(ssaForm);
+ foreach (SsaBlock block in ssaForm.Blocks) {
+ for (int i = 0; i < block.Instructions.Count; i++) {
+ SsaInstruction inst = block.Instructions[i];
+ if (inst.Instruction != null) {
+ switch (inst.Instruction.OpCode.Code) {
+ case Code.Call:
+ case Code.Callvirt:
+ instance.MakeByRefCallSimple(block, ref i, (IMethodSignature)inst.Instruction.Operand);
+ break;
+ case Code.Initobj:
+ instance.MakeInitObjCallSimple(block, ref i);
+ break;
+ case Code.Ldfld:
+ instance.MakeLoadFieldCallSimple(block, ref i);
+ break;
+ }
+ }
+ }
+ }
+ instance.RemoveRedundantInstructions();
+ if (instance.couldSimplifySomething)
+ ssaForm.ComputeVariableUsage();
+ return instance.couldSimplifySomething;
+ }
+
+ readonly SsaForm ssaForm;
+
+ bool couldSimplifySomething;
+
+ // the list of ldloca instructions we will remove
+ readonly List<SsaInstruction> redundantLoadAddressInstructions = new List<SsaInstruction>();
+
+ SimplifyByRefCalls(SsaForm ssaForm)
+ {
+ this.ssaForm = ssaForm;
+ }
+
+ void MakeByRefCallSimple(SsaBlock block, ref int instructionIndexInBlock, IMethodSignature targetMethod)
+ {
+ SsaInstruction inst = block.Instructions[instructionIndexInBlock];
+ for (int i = 0; i < inst.Operands.Length; i++) {
+ SsaVariable operand = inst.Operands[i];
+ if (operand.IsSingleAssignment && operand.Usage.Count == 1 && IsLoadAddress(operand.Definition)) {
+ // address is used for this method call only
+
+ Instruction loadAddressInstruction = operand.Definition.Instruction;
+
+ // find target parameter type:
+ bool isOut;
+ if (i == 0 && targetMethod.HasThis) {
+ isOut = false;
+ } else {
+ ParameterDefinition parameter = targetMethod.Parameters[i - (targetMethod.HasThis ? 1 : 0)];
+ isOut = parameter.IsOut;
+ }
+
+ SsaVariable addressTakenOf = GetVariableFromLoadAddressInstruction(loadAddressInstruction);
+
+ // insert "Prepare" instruction on front
+ SpecialOpCode loadOpCode = isOut ? SpecialOpCode.PrepareByOutCall : SpecialOpCode.PrepareByRefCall;
+ block.Instructions.Insert(instructionIndexInBlock++, new SsaInstruction(
+ block, null, operand, new SsaVariable[] { addressTakenOf }, specialOpCode: loadOpCode));
+
+ // insert "WriteAfterByRefOrOutCall" instruction after call
+ block.Instructions.Insert(instructionIndexInBlock + 1, new SsaInstruction(
+ block, null, addressTakenOf, new SsaVariable[] { operand }, specialOpCode: SpecialOpCode.WriteAfterByRefOrOutCall));
+
+ couldSimplifySomething = true;
+
+ // remove the loadAddressInstruction later
+ // (later because it might be defined in the current block and we don't want instructionIndex to become invalid)
+ redundantLoadAddressInstructions.Add(operand.Definition);
+ }
+ }
+ }
+
+ SsaVariable GetVariableFromLoadAddressInstruction(Instruction loadAddressInstruction)
+ {
+ if (loadAddressInstruction.OpCode == OpCodes.Ldloca) {
+ return ssaForm.GetOriginalVariable((VariableReference)loadAddressInstruction.Operand);
+ } else {
+ Debug.Assert(loadAddressInstruction.OpCode == OpCodes.Ldarga);
+ return ssaForm.GetOriginalVariable((ParameterReference)loadAddressInstruction.Operand);
+ }
+ }
+
+ static bool IsLoadAddress(SsaInstruction inst)
+ {
+ return inst.Instruction != null && (inst.Instruction.OpCode == OpCodes.Ldloca || inst.Instruction.OpCode == OpCodes.Ldarga);
+ }
+
+ void MakeInitObjCallSimple(SsaBlock block, ref int instructionIndexInBlock)
+ {
+ SsaInstruction inst = block.Instructions[instructionIndexInBlock];
+ Debug.Assert(inst.Operands.Length == 1);
+ SsaVariable operand = inst.Operands[0];
+ if (operand.IsSingleAssignment && operand.Usage.Count == 1 && IsLoadAddress(operand.Definition)) {
+ // replace instruction with special "InitObj" instruction
+ block.Instructions[instructionIndexInBlock] = new SsaInstruction(
+ inst.ParentBlock, null, GetVariableFromLoadAddressInstruction(operand.Definition.Instruction), null,
+ specialOpCode: SpecialOpCode.InitObj,
+ typeOperand: (TypeReference)inst.Instruction.Operand);
+
+ couldSimplifySomething = true;
+
+ // remove the loadAddressInstruction later
+ redundantLoadAddressInstructions.Add(operand.Definition);
+ }
+ }
+
+ void MakeLoadFieldCallSimple(SsaBlock block, ref int instructionIndexInBlock)
+ {
+ SsaInstruction inst = block.Instructions[instructionIndexInBlock];
+ Debug.Assert(inst.Operands.Length == 1);
+ SsaVariable operand = inst.Operands[0];
+ if (operand.IsSingleAssignment && operand.Usage.Count == 1 && IsLoadAddress(operand.Definition)) {
+ // insert special "PrepareForFieldAccess" instruction in front
+ block.Instructions.Insert(instructionIndexInBlock++, new SsaInstruction(
+ inst.ParentBlock, null, operand,
+ new SsaVariable[] { GetVariableFromLoadAddressInstruction(operand.Definition.Instruction) },
+ specialOpCode: SpecialOpCode.PrepareForFieldAccess));
+
+ couldSimplifySomething = true;
+
+ // remove the loadAddressInstruction later
+ redundantLoadAddressInstructions.Add(operand.Definition);
+ }
+ }
+
+ void RemoveRedundantInstructions()
+ {
+ foreach (SsaInstruction inst in redundantLoadAddressInstructions) {
+ inst.ParentBlock.Instructions.Remove(inst);
+ }
+ }
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/SsaBlock.cs b/ICSharpCode.Decompiler/FlowAnalysis/SsaBlock.cs
new file mode 100644
index 00000000..b1767b9b
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/SsaBlock.cs
@@ -0,0 +1,60 @@
+// 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.IO;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// A block in a control flow graph; with instructions represented by "SsaInstructions" (instructions use variables, no evaluation stack).
+ /// Usually these variables are in SSA form to make analysis easier.
+ /// </summary>
+ public sealed class SsaBlock
+ {
+ public readonly List<SsaBlock> Successors = new List<SsaBlock>();
+ public readonly List<SsaBlock> Predecessors = new List<SsaBlock>();
+ public readonly ControlFlowNodeType NodeType;
+ public readonly List<SsaInstruction> Instructions = new List<SsaInstruction>();
+
+ /// <summary>
+ /// The block index in the control flow graph.
+ /// This correspons to the node index in ControlFlowGraph.Nodes, so it can be used to retrieve the original CFG node and look
+ /// up additional information (e.g. dominance).
+ /// </summary>
+ public readonly int BlockIndex;
+
+ internal SsaBlock(ControlFlowNode node)
+ {
+ NodeType = node.NodeType;
+ BlockIndex = node.BlockIndex;
+ }
+
+ public override string ToString()
+ {
+ StringWriter writer = new StringWriter();
+ writer.Write("Block #{0} ({1})", BlockIndex, NodeType);
+ foreach (SsaInstruction inst in Instructions) {
+ writer.WriteLine();
+ inst.WriteTo(writer);
+ }
+ return writer.ToString();
+ }
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/SsaForm.cs b/ICSharpCode.Decompiler/FlowAnalysis/SsaForm.cs
new file mode 100644
index 00000000..baf520eb
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/SsaForm.cs
@@ -0,0 +1,162 @@
+// Copyright (c) 2010 Daniel Grunwald
+//
+// 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 ICSharpCode.NRefactory.Utils;
+using Mono.Cecil;
+using Mono.Cecil.Cil;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// Represents a graph of SsaBlocks.
+ /// </summary>
+ public sealed class SsaForm
+ {
+ readonly SsaVariable[] parameters;
+ readonly SsaVariable[] locals;
+ public readonly ReadOnlyCollection<SsaVariable> OriginalVariables;
+ public readonly ReadOnlyCollection<SsaBlock> Blocks;
+ readonly bool methodHasThis;
+
+ public SsaBlock EntryPoint {
+ get { return Blocks[0]; }
+ }
+
+ public SsaBlock RegularExit {
+ get { return Blocks[1]; }
+ }
+
+ public SsaBlock ExceptionalExit {
+ get { return Blocks[2]; }
+ }
+
+ internal SsaForm(SsaBlock[] blocks, SsaVariable[] parameters, SsaVariable[] locals, SsaVariable[] stackLocations, bool methodHasThis)
+ {
+ this.parameters = parameters;
+ this.locals = locals;
+ Blocks = new ReadOnlyCollection<SsaBlock>(blocks);
+ OriginalVariables = new ReadOnlyCollection<SsaVariable>(parameters.Concat(locals).Concat(stackLocations).ToList());
+ this.methodHasThis = methodHasThis;
+
+ Debug.Assert(EntryPoint.NodeType == ControlFlowNodeType.EntryPoint);
+ Debug.Assert(RegularExit.NodeType == ControlFlowNodeType.RegularExit);
+ Debug.Assert(ExceptionalExit.NodeType == ControlFlowNodeType.ExceptionalExit);
+ for (int i = 0; i < OriginalVariables.Count; i++) {
+ OriginalVariables[i].OriginalVariableIndex = i;
+ }
+ }
+
+ public GraphVizGraph ExportBlockGraph(Func<SsaBlock, string> labelProvider = null)
+ {
+ if (labelProvider == null)
+ labelProvider = b => b.ToString();
+ GraphVizGraph graph = new GraphVizGraph();
+ foreach (SsaBlock block in Blocks) {
+ graph.AddNode(new GraphVizNode(block.BlockIndex) { label = labelProvider(block), shape = "box" });
+ }
+ foreach (SsaBlock block in Blocks) {
+ foreach (SsaBlock s in block.Successors) {
+ graph.AddEdge(new GraphVizEdge(block.BlockIndex, s.BlockIndex));
+ }
+ }
+ return graph;
+ }
+
+ public GraphVizGraph ExportVariableGraph(Func<SsaVariable, string> labelProvider = null)
+ {
+ if (labelProvider == null)
+ labelProvider = v => v.ToString();
+ GraphVizGraph graph = new GraphVizGraph();
+ foreach (SsaVariable v in AllVariables) {
+ graph.AddNode(new GraphVizNode(v.Name) { label = labelProvider(v) });
+ }
+ int instructionIndex = 0;
+ foreach (SsaBlock block in Blocks) {
+ foreach (SsaInstruction inst in block.Instructions) {
+ if (inst.Operands.Length == 0 && inst.Target == null)
+ continue;
+ string id = "instruction" + (++instructionIndex);
+ graph.AddNode(new GraphVizNode(id) { label = inst.ToString(), shape = "box" });
+ foreach (SsaVariable op in inst.Operands)
+ graph.AddEdge(new GraphVizEdge(op.Name, id));
+ if (inst.Target != null)
+ graph.AddEdge(new GraphVizEdge(id, inst.Target.Name));
+ }
+ }
+ return graph;
+ }
+
+ public SsaVariable GetOriginalVariable(ParameterReference parameter)
+ {
+ if (methodHasThis)
+ return parameters[parameter.Index + 1];
+ else
+ return parameters[parameter.Index];
+ }
+
+ public SsaVariable GetOriginalVariable(VariableReference variable)
+ {
+ return locals[variable.Index];
+ }
+
+ #region ComputeVariableUsage
+ public void ComputeVariableUsage()
+ {
+ // clear data from previous runs
+ foreach (SsaBlock block in Blocks) {
+ foreach (SsaInstruction inst in block.Instructions) {
+ foreach (SsaVariable v in inst.Operands) {
+ if (v.Usage != null)
+ v.Usage.Clear();
+ }
+ if (inst.Target != null && inst.Target.Usage != null)
+ inst.Target.Usage.Clear();
+ }
+ }
+ foreach (SsaBlock block in Blocks) {
+ foreach (SsaInstruction inst in block.Instructions) {
+ foreach (SsaVariable v in inst.Operands) {
+ if (v.Usage == null)
+ v.Usage = new List<SsaInstruction>();
+ v.Usage.Add(inst);
+ }
+ if (inst.Target != null && inst.Target.Usage == null)
+ inst.Target.Usage = new List<SsaInstruction>();
+ }
+ }
+ }
+ #endregion
+
+ public IEnumerable<SsaVariable> AllVariables {
+ get {
+ return (
+ from block in Blocks
+ from instruction in block.Instructions
+ where instruction.Target != null
+ select instruction.Target
+ ).Distinct();
+ }
+ }
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs b/ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs
new file mode 100644
index 00000000..c7c86a57
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs
@@ -0,0 +1,257 @@
+// Copyright (c) 2010 Daniel Grunwald
+//
+// 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.Diagnostics;
+
+using Mono.Cecil;
+using Mono.Cecil.Cil;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// Constructs "SsaForm" graph for a CFG.
+ /// This class transforms the method from stack-based IL to a register-based IL language.
+ /// Then it calls into TransformToSsa to convert the resulting graph to static single assignment form.
+ /// </summary>
+ public sealed class SsaFormBuilder
+ {
+ public static SsaForm Build(MethodDefinition method)
+ {
+ if (method == null)
+ throw new ArgumentNullException("method");
+ var cfg = ControlFlowGraphBuilder.Build(method.Body);
+ cfg.ComputeDominance();
+ cfg.ComputeDominanceFrontier();
+ var ssa = BuildRegisterIL(method, cfg);
+ TransformToSsa.Transform(cfg, ssa);
+ return ssa;
+ }
+
+ public static SsaForm BuildRegisterIL(MethodDefinition method, ControlFlowGraph cfg)
+ {
+ if (method == null)
+ throw new ArgumentNullException("method");
+ if (cfg == null)
+ throw new ArgumentNullException("cfg");
+ return new SsaFormBuilder(method, cfg).Build();
+ }
+
+ readonly MethodDefinition method;
+ readonly ControlFlowGraph cfg;
+
+ readonly SsaBlock[] blocks; // array index = block index
+ readonly int[] stackSizeAtBlockStart; // array index = block index
+
+ readonly SsaVariable[] parameters; // array index = parameter number
+ readonly SsaVariable[] locals; // array index = local number
+ readonly SsaVariable[] stackLocations; // array index = position on the IL evaluation stack
+ SsaForm ssaForm;
+
+ SsaFormBuilder(MethodDefinition method, ControlFlowGraph cfg)
+ {
+ this.method = method;
+ this.cfg = cfg;
+
+ blocks = new SsaBlock[cfg.Nodes.Count];
+ stackSizeAtBlockStart = new int[cfg.Nodes.Count];
+ for (int i = 0; i < stackSizeAtBlockStart.Length; i++) {
+ stackSizeAtBlockStart[i] = -1;
+ }
+ stackSizeAtBlockStart[cfg.EntryPoint.BlockIndex] = 0;
+
+ parameters = new SsaVariable[method.Parameters.Count + (method.HasThis ? 1 : 0)];
+ if (method.HasThis)
+ parameters[0] = new SsaVariable(method.Body.ThisParameter);
+ for (int i = 0; i < method.Parameters.Count; i++)
+ parameters[i + (method.HasThis ? 1 : 0)] = new SsaVariable(method.Parameters[i]);
+
+ locals = new SsaVariable[method.Body.Variables.Count];
+ for (int i = 0; i < locals.Length; i++)
+ locals[i] = new SsaVariable(method.Body.Variables[i]);
+
+ stackLocations = new SsaVariable[method.Body.MaxStackSize];
+ for (int i = 0; i < stackLocations.Length; i++) {
+ stackLocations[i] = new SsaVariable(i);
+ }
+ }
+
+ internal SsaForm Build()
+ {
+ CreateGraphStructure();
+ ssaForm = new SsaForm(blocks, parameters, locals, stackLocations, method.HasThis);
+ CreateInstructions(cfg.EntryPoint.BlockIndex);
+ CreateSpecialInstructions();
+ return ssaForm;
+ }
+
+ void CreateGraphStructure()
+ {
+ for (int i = 0; i < blocks.Length; i++) {
+ blocks[i] = new SsaBlock(cfg.Nodes[i]);
+ }
+ for (int i = 0; i < blocks.Length; i++) {
+ foreach (ControlFlowNode node in cfg.Nodes[i].Successors) {
+ blocks[i].Successors.Add(blocks[node.BlockIndex]);
+ blocks[node.BlockIndex].Predecessors.Add(blocks[i]);
+ }
+ }
+ }
+
+ void CreateInstructions(int blockIndex)
+ {
+ ControlFlowNode cfgNode = cfg.Nodes[blockIndex];
+ SsaBlock block = blocks[blockIndex];
+
+ int stackSize = stackSizeAtBlockStart[blockIndex];
+ Debug.Assert(stackSize >= 0);
+
+ List<Instruction> prefixes = new List<Instruction>();
+ foreach (Instruction inst in cfgNode.Instructions) {
+ if (inst.OpCode.OpCodeType == OpCodeType.Prefix) {
+ prefixes.Add(inst);
+ continue;
+ }
+
+ int popCount = inst.GetPopDelta(method) ?? stackSize;
+ stackSize -= popCount;
+ if (stackSize < 0)
+ throw new InvalidProgramException("IL stack underflow");
+
+ int pushCount = inst.GetPushDelta();
+ if (stackSize + pushCount > stackLocations.Length)
+ throw new InvalidProgramException("IL stack overflow");
+
+ SsaVariable target;
+ SsaVariable[] operands;
+ DetermineOperands(stackSize, inst, popCount, pushCount, out target, out operands);
+
+ Instruction[] prefixArray = prefixes.Count > 0 ? prefixes.ToArray() : null;
+ prefixes.Clear();
+
+ // ignore NOP instructions
+ if (!(inst.OpCode == OpCodes.Nop || inst.OpCode == OpCodes.Pop)) {
+ block.Instructions.Add(new SsaInstruction(block, inst, target, operands, prefixArray));
+ }
+ stackSize += pushCount;
+ }
+
+ foreach (ControlFlowEdge edge in cfgNode.Outgoing) {
+ int newStackSize;
+ switch (edge.Type) {
+ case JumpType.Normal:
+ newStackSize = stackSize;
+ break;
+ case JumpType.EndFinally:
+ if (stackSize != 0)
+ throw new NotSupportedException("stacksize must be 0 in endfinally edge");
+ newStackSize = 0;
+ break;
+ case JumpType.JumpToExceptionHandler:
+ switch (edge.Target.NodeType) {
+ case ControlFlowNodeType.FinallyOrFaultHandler:
+ newStackSize = 0;
+ break;
+ case ControlFlowNodeType.ExceptionalExit:
+ case ControlFlowNodeType.CatchHandler:
+ newStackSize = 1;
+ break;
+ default:
+ throw new NotSupportedException("unsupported target node type: " + edge.Target.NodeType);
+ }
+ break;
+ default:
+ throw new NotSupportedException("unsupported jump type: " + edge.Type);
+ }
+
+ int nextStackSize = stackSizeAtBlockStart[edge.Target.BlockIndex];
+ if (nextStackSize == -1) {
+ stackSizeAtBlockStart[edge.Target.BlockIndex] = newStackSize;
+ CreateInstructions(edge.Target.BlockIndex);
+ } else if (nextStackSize != newStackSize) {
+ throw new InvalidProgramException("Stack size doesn't match");
+ }
+ }
+ }
+
+ void DetermineOperands(int stackSize, Instruction inst, int popCount, int pushCount, out SsaVariable target, out SsaVariable[] operands)
+ {
+ switch (inst.OpCode.Code) {
+ case Code.Ldarg:
+ operands = new SsaVariable[] { ssaForm.GetOriginalVariable((ParameterReference)inst.Operand) };
+ target = stackLocations[stackSize];
+ break;
+ case Code.Starg:
+ operands = new SsaVariable[] { stackLocations[stackSize] };
+ target = ssaForm.GetOriginalVariable((ParameterReference)inst.Operand);
+ break;
+ case Code.Ldloc:
+ operands = new SsaVariable[] { ssaForm.GetOriginalVariable((VariableReference)inst.Operand) };
+ target = stackLocations[stackSize];
+ break;
+ case Code.Stloc:
+ operands = new SsaVariable[] { stackLocations[stackSize] };
+ target = ssaForm.GetOriginalVariable((VariableReference)inst.Operand);
+ break;
+ case Code.Dup:
+ operands = new SsaVariable[] { stackLocations[stackSize] };
+ target = stackLocations[stackSize + 1];
+ break;
+ default:
+ operands = new SsaVariable[popCount];
+ for (int i = 0; i < popCount; i++) {
+ operands[i] = stackLocations[stackSize + i];
+ }
+
+ switch (pushCount) {
+ case 0:
+ target = null;
+ break;
+ case 1:
+ target = stackLocations[stackSize];
+ break;
+ default:
+ throw new NotSupportedException("unsupported pushCount=" + pushCount);
+ }
+ break;
+ }
+ }
+
+ void CreateSpecialInstructions()
+ {
+ // Everything needs an initial write for the SSA transformation to work correctly.
+ foreach (SsaVariable v in parameters) {
+ ssaForm.EntryPoint.Instructions.Add(new SsaInstruction(ssaForm.EntryPoint, null, v, null, specialOpCode: SpecialOpCode.Parameter));
+ }
+ foreach (SsaVariable v in locals) {
+ ssaForm.EntryPoint.Instructions.Add(new SsaInstruction(ssaForm.EntryPoint, null, v, null, specialOpCode: SpecialOpCode.Uninitialized));
+ }
+ foreach (SsaVariable v in stackLocations) {
+ ssaForm.EntryPoint.Instructions.Add(new SsaInstruction(ssaForm.EntryPoint, null, v, null, specialOpCode: SpecialOpCode.Uninitialized));
+ }
+ foreach (SsaBlock b in blocks) {
+ if (b.NodeType == ControlFlowNodeType.CatchHandler) {
+ b.Instructions.Add(new SsaInstruction(b, null, stackLocations[0], null,
+ specialOpCode: SpecialOpCode.Exception,
+ typeOperand: cfg.Nodes[b.BlockIndex].ExceptionHandler.CatchType));
+ }
+ }
+ }
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/SsaInstruction.cs b/ICSharpCode.Decompiler/FlowAnalysis/SsaInstruction.cs
new file mode 100644
index 00000000..c9375852
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/SsaInstruction.cs
@@ -0,0 +1,191 @@
+// 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.Diagnostics;
+using System.IO;
+
+using ICSharpCode.Decompiler.Disassembler;
+using Mono.Cecil;
+using Mono.Cecil.Cil;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ public enum SpecialOpCode
+ {
+ /// <summary>
+ /// No special op code: SsaInstruction has a normal IL instruction
+ /// </summary>
+ None,
+ /// <summary>
+ /// Φ function: chooses the appropriate variable based on which CFG edge was used to enter this block
+ /// </summary>
+ Phi,
+ /// <summary>
+ /// Variable is read from before passing it by ref.
+ /// This instruction constructs a managed reference to the variable.
+ /// </summary>
+ PrepareByRefCall,
+ /// <summary>
+ /// This instruction constructs a managed reference to the variable.
+ /// The variable is not really read from.
+ /// </summary>
+ PrepareByOutCall,
+ /// <summary>
+ /// This instruction constructs a managed reference to the variable.
+ /// The reference is used for a field access on a value type.
+ /// </summary>
+ PrepareForFieldAccess,
+ /// <summary>
+ /// Variable is written to after passing it by ref or out.
+ /// </summary>
+ WriteAfterByRefOrOutCall,
+ /// <summary>
+ /// Variable is not initialized.
+ /// </summary>
+ Uninitialized,
+ /// <summary>
+ /// Value is passed in as parameter
+ /// </summary>
+ Parameter,
+ /// <summary>
+ /// Value is a caught exception.
+ /// TypeOperand is set to the exception type.
+ /// </summary>
+ Exception,
+ /// <summary>
+ /// Initialize a value type. Unlike the real initobj instruction, this one does not take an address
+ /// but assigns to the target variable.
+ /// TypeOperand is set to the type being created.
+ /// </summary>
+ InitObj
+ }
+
+ public sealed class SsaInstruction
+ {
+ public readonly SsaBlock ParentBlock;
+ public readonly SpecialOpCode SpecialOpCode;
+
+ /// <summary>
+ /// The original IL instruction.
+ /// May be null for "invented" instructions (SpecialOpCode != None).
+ /// </summary>
+ public readonly Instruction Instruction;
+
+ /// <summary>
+ /// Prefixes in front of the IL instruction.
+ /// </summary>
+ public readonly Instruction[] Prefixes;
+
+ /// <summary>
+ /// Gets the type operand. This is used only in combination with some special opcodes.
+ /// </summary>
+ public readonly TypeReference TypeOperand;
+
+ public SsaVariable Target;
+ public SsaVariable[] Operands;
+
+ static readonly SsaVariable[] emptyVariableArray = {};
+ static readonly Instruction[] emptyInstructionArray = {};
+
+ public SsaInstruction(SsaBlock parentBlock, Instruction instruction, SsaVariable target, SsaVariable[] operands,
+ Instruction[] prefixes = null, SpecialOpCode specialOpCode = SpecialOpCode.None,
+ TypeReference typeOperand = null)
+ {
+ ParentBlock = parentBlock;
+ Instruction = instruction;
+ Prefixes = prefixes ?? emptyInstructionArray;
+ Target = target;
+ Operands = operands ?? emptyVariableArray;
+ SpecialOpCode = specialOpCode;
+ TypeOperand = typeOperand;
+ Debug.Assert((typeOperand != null) == (specialOpCode == SpecialOpCode.Exception || specialOpCode == SpecialOpCode.InitObj));
+ }
+
+ /// <summary>
+ /// Gets whether this instruction is a simple assignment from one variable to another.
+ /// </summary>
+ public bool IsMoveInstruction {
+ get {
+ return Target != null && Operands.Length == 1 && Instruction != null && OpCodeInfo.Get(Instruction.OpCode).IsMoveInstruction;
+ }
+ }
+
+ public void ReplaceVariableInOperands(SsaVariable oldVar, SsaVariable newVar)
+ {
+ for (int i = 0; i < Operands.Length; i++) {
+ if (Operands[i] == oldVar)
+ Operands[i] = newVar;
+ }
+ }
+
+ public override string ToString()
+ {
+ StringWriter w = new StringWriter();
+ WriteTo(w);
+ return w.ToString();
+ }
+
+ public void WriteTo(TextWriter writer)
+ {
+ foreach (Instruction prefix in Prefixes) {
+ DisassemblerHelpers.WriteTo(prefix, new PlainTextOutput(writer));
+ writer.WriteLine();
+ }
+ if (Instruction != null && Instruction.Offset >= 0) {
+ writer.Write(CecilExtensions.OffsetToString(Instruction.Offset));
+ writer.Write(": ");
+ }
+ if (Target != null) {
+ writer.Write(Target.ToString());
+ writer.Write(" = ");
+ }
+ if (IsMoveInstruction) {
+ writer.Write(Operands[0].ToString());
+ if (Instruction != null) {
+ writer.Write(" (" + Instruction.OpCode.Name + ")");
+ }
+ } else {
+ if (Instruction == null) {
+ writer.Write(SpecialOpCode.ToString());
+ } else {
+ writer.Write(Instruction.OpCode.Name);
+ if(null != Instruction.Operand) {
+ writer.Write(' ');
+ DisassemblerHelpers.WriteOperand(new PlainTextOutput(writer), Instruction.Operand);
+ writer.Write(' ');
+ }
+ }
+ if (TypeOperand != null) {
+ writer.Write(' ');
+ writer.Write(TypeOperand.ToString());
+ writer.Write(' ');
+ }
+ if (Operands.Length > 0) {
+ writer.Write('(');
+ for (int i = 0; i < Operands.Length; i++) {
+ if (i > 0)
+ writer.Write(", ");
+ writer.Write(Operands[i].ToString());
+ }
+ writer.Write(')');
+ }
+ }
+ }
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/SsaOptimization.cs b/ICSharpCode.Decompiler/FlowAnalysis/SsaOptimization.cs
new file mode 100644
index 00000000..71696992
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/SsaOptimization.cs
@@ -0,0 +1,138 @@
+// 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.Diagnostics;
+
+using Mono.Cecil.Cil;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// Contains some very simple optimizations that work on the SSA form.
+ /// </summary>
+ internal static class SsaOptimization
+ {
+ public static void Optimize(SsaForm ssaForm)
+ {
+ DirectlyStoreToVariables(ssaForm);
+ SimpleCopyPropagation(ssaForm);
+ RemoveDeadAssignments(ssaForm);
+ }
+
+ /// <summary>
+ /// When any instructions stores its result in a stack location that's used only once in a 'stloc' or 'starg' instruction,
+ /// we optimize this to directly store in the target location.
+ /// As optimization this is redundant (does the same as copy propagation), but it'll make us keep the variables named
+ /// after locals instead of keeping the temps as using only the simple copy propagation would do.
+ /// </summary>
+ public static void DirectlyStoreToVariables(SsaForm ssaForm)
+ {
+ foreach (SsaBlock block in ssaForm.Blocks) {
+ block.Instructions.RemoveAll(
+ inst => {
+ if (inst.Instruction != null && (inst.Instruction.OpCode == OpCodes.Stloc || inst.Instruction.OpCode == OpCodes.Starg)) {
+ SsaVariable target = inst.Target;
+ SsaVariable temp = inst.Operands[0];
+ if (target.IsSingleAssignment && temp.IsSingleAssignment && temp.Usage.Count == 1 && temp.IsStackLocation) {
+ temp.Definition.Target = target;
+ return true;
+ }
+ }
+ return false;
+ });
+ }
+ ssaForm.ComputeVariableUsage(); // update usage after we modified stuff
+ }
+
+ public static void SimpleCopyPropagation(SsaForm ssaForm, bool onlyForStackLocations = true)
+ {
+ foreach (SsaBlock block in ssaForm.Blocks) {
+ foreach (SsaInstruction inst in block.Instructions) {
+ if (inst.IsMoveInstruction && inst.Target.IsSingleAssignment && inst.Operands[0].IsSingleAssignment) {
+ if (inst.Target.IsStackLocation || !onlyForStackLocations) {
+ // replace all uses of 'target' with 'operands[0]'.
+ foreach (SsaInstruction useInstruction in inst.Target.Usage) {
+ useInstruction.ReplaceVariableInOperands(inst.Target, inst.Operands[0]);
+ }
+ }
+ }
+ }
+ }
+ ssaForm.ComputeVariableUsage(); // update usage after we modified stuff
+ }
+
+ public static void RemoveDeadAssignments(SsaForm ssaForm)
+ {
+ HashSet<SsaVariable> liveVariables = new HashSet<SsaVariable>();
+ // find variables that are used directly
+ foreach (SsaBlock block in ssaForm.Blocks) {
+ foreach (SsaInstruction inst in block.Instructions) {
+ if (!CanRemoveAsDeadCode(inst)) {
+ if (inst.Target != null)
+ liveVariables.Add(inst.Target);
+ foreach (SsaVariable op in inst.Operands) {
+ liveVariables.Add(op);
+ }
+ }
+ }
+ }
+ Queue<SsaVariable> queue = new Queue<SsaVariable>(liveVariables);
+ // find variables that are used indirectly
+ while (queue.Count > 0) {
+ SsaVariable v = queue.Dequeue();
+ if (v.IsSingleAssignment) {
+ foreach (SsaVariable op in v.Definition.Operands) {
+ if (liveVariables.Add(op))
+ queue.Enqueue(op);
+ }
+ }
+ }
+ // remove assignments to all unused variables
+ foreach (SsaBlock block in ssaForm.Blocks) {
+ block.Instructions.RemoveAll(
+ inst => {
+ if (inst.Target != null && !liveVariables.Contains(inst.Target)) {
+ Debug.Assert(inst.Target.IsSingleAssignment);
+ return true;
+ }
+ return false;
+ });
+ }
+ ssaForm.ComputeVariableUsage(); // update usage after we modified stuff
+ }
+
+ static bool CanRemoveAsDeadCode(SsaInstruction inst)
+ {
+ if (inst.Target != null && !inst.Target.IsSingleAssignment)
+ return false;
+ switch (inst.SpecialOpCode) {
+ case SpecialOpCode.Phi:
+ case SpecialOpCode.Exception:
+ case SpecialOpCode.Parameter:
+ case SpecialOpCode.Uninitialized:
+ return true;
+ case SpecialOpCode.None:
+ return inst.IsMoveInstruction;
+ default:
+ return false;
+ }
+ }
+ }
+}
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/SsaVariable.cs b/ICSharpCode.Decompiler/FlowAnalysis/SsaVariable.cs
new file mode 100644
index 00000000..902b7002
--- /dev/null
+++ b/ICSharpCode.Decompiler/FlowAnalysis/SsaVariable.cs
@@ -0,0 +1,91 @@
+// 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 Mono.Cecil;
+using Mono.Cecil.Cil;
+
+namespace ICSharpCode.Decompiler.FlowAnalysis
+{
+ /// <summary>
+ /// Represents a variable used with the SsaInstruction register-based instructions.
+ /// Despite what the name suggests, the variable is not necessarily in single-assignment form - take a look at "bool IsSingleAssignment".
+ /// </summary>
+ public sealed class SsaVariable
+ {
+ public int OriginalVariableIndex;
+ public readonly string Name;
+ public readonly bool IsStackLocation;
+
+ public readonly ParameterDefinition Parameter;
+ public readonly VariableDefinition Variable;
+
+ public SsaVariable(ParameterDefinition p)
+ {
+ Name = string.IsNullOrEmpty(p.Name) ? "param" + p.Index : p.Name;
+ Parameter = p;
+ }
+
+ public SsaVariable(VariableDefinition v)
+ {
+ Name = string.IsNullOrEmpty(v.Name) ? "V_" + v.Index : v.Name;
+ Variable = v;
+ }
+
+ public SsaVariable(int stackLocation)
+ {
+ Name = "stack" + stackLocation;
+ IsStackLocation = true;
+ }
+
+ public SsaVariable(SsaVariable original, string newName)
+ {
+ Name = newName;
+ IsStackLocation = original.IsStackLocation;
+ OriginalVariableIndex = original.OriginalVariableIndex;
+ Parameter = original.Parameter;
+ Variable = original.Variable;
+ }
+
+ public override string ToString()
+ {
+ return Name;
+ }
+
+ /// <summary>
+ /// Gets whether this variable has only a single assignment.
+ /// This field is initialized in TransformToSsa step.
+ /// </summary>
+ /// <remarks>Not all variables can be transformed to single assignment form: variables that have their address taken
+ /// cannot be represented in SSA (although SimplifyByRefCalls will get rid of the address-taking instruction in almost all cases)</remarks>
+ public bool IsSingleAssignment;
+
+ /// <summary>
+ /// Gets the instruction defining the variable.
+ /// This field is initialized in TransformToSsa step. It is only set for variables with a single assignment.
+ /// </summary>
+ public SsaInstruction Definition;
+
+ /// <summary>
+ /// Gets the places where a variable is used.
+ /// If a single instruction reads a variable 2 times (e.g. adding to itself), then it must be included 2 times in this list!
+ /// </summary>
+ public List<SsaInstruction> Usage;
+ }
+}
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
+ }
+}