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, 0 insertions, 2893 deletions
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowEdge.cs b/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowEdge.cs deleted file mode 100644 index 98bd4399..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowEdge.cs +++ /dev/null @@ -1,78 +0,0 @@ -// 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 deleted file mode 100644 index 7cc815a6..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraph.cs +++ /dev/null @@ -1,191 +0,0 @@ -// 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 deleted file mode 100644 index 7570884a..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowGraphBuilder.cs +++ /dev/null @@ -1,439 +0,0 @@ -// 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 deleted file mode 100644 index 83294fd9..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/ControlFlowNode.cs +++ /dev/null @@ -1,305 +0,0 @@ -// 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 deleted file mode 100644 index b7b77e07..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/ControlStructureDetector.cs +++ /dev/null @@ -1,241 +0,0 @@ -// 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 deleted file mode 100644 index e0dc724f..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/OpCodeInfo.cs +++ /dev/null @@ -1,312 +0,0 @@ -// 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 deleted file mode 100644 index 42c30914..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/SimplifyByRefCalls.cs +++ /dev/null @@ -1,174 +0,0 @@ -// 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 deleted file mode 100644 index b1767b9b..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/SsaBlock.cs +++ /dev/null @@ -1,60 +0,0 @@ -// 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 deleted file mode 100644 index baf520eb..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/SsaForm.cs +++ /dev/null @@ -1,162 +0,0 @@ -// 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 deleted file mode 100644 index c7c86a57..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs +++ /dev/null @@ -1,257 +0,0 @@ -// 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 deleted file mode 100644 index c9375852..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/SsaInstruction.cs +++ /dev/null @@ -1,191 +0,0 @@ -// 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 deleted file mode 100644 index 71696992..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/SsaOptimization.cs +++ /dev/null @@ -1,138 +0,0 @@ -// 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 deleted file mode 100644 index 902b7002..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/SsaVariable.cs +++ /dev/null @@ -1,91 +0,0 @@ -// 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 deleted file mode 100644 index 47ff7bff..00000000 --- a/ICSharpCode.Decompiler/FlowAnalysis/TransformToSsa.cs +++ /dev/null @@ -1,254 +0,0 @@ -// 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 - } -} |