diff options
Diffstat (limited to 'ICSharpCode.Decompiler/FlowAnalysis')
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/ControlFlowEdge.cs | 78 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraph.cs | 191 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraphBuilder.cs | 439 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/ControlFlowNode.cs | 305 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/ControlStructureDetector.cs | 241 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/OpCodeInfo.cs | 312 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/SimplifyByRefCalls.cs | 174 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/SsaBlock.cs | 60 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/SsaForm.cs | 162 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs | 257 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/SsaInstruction.cs | 191 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/SsaOptimization.cs | 138 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/SsaVariable.cs | 91 | ||||
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/TransformToSsa.cs | 254 |
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 + } +} |