diff options
author | Jason Smith <jason.smith@xamarin.com> | 2016-03-22 13:02:25 -0700 |
---|---|---|
committer | Jason Smith <jason.smith@xamarin.com> | 2016-03-22 16:13:41 -0700 |
commit | 17fdde66d94155fc62a034fa6658995bef6fd6e5 (patch) | |
tree | b5e5073a2a7b15cdbe826faa5c763e270a505729 /ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs | |
download | xamarin-forms-17fdde66d94155fc62a034fa6658995bef6fd6e5.tar.gz xamarin-forms-17fdde66d94155fc62a034fa6658995bef6fd6e5.tar.bz2 xamarin-forms-17fdde66d94155fc62a034fa6658995bef6fd6e5.zip |
Initial import
Diffstat (limited to 'ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs')
-rw-r--r-- | ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs | 257 |
1 files changed, 257 insertions, 0 deletions
diff --git a/ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs b/ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs new file mode 100644 index 00000000..c7c86a57 --- /dev/null +++ b/ICSharpCode.Decompiler/FlowAnalysis/SsaFormBuilder.cs @@ -0,0 +1,257 @@ +// Copyright (c) 2010 Daniel Grunwald +// +// Permission is hereby granted, free of charge, to any person obtaining a copy of this +// software and associated documentation files (the "Software"), to deal in the Software +// without restriction, including without limitation the rights to use, copy, modify, merge, +// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons +// to whom the Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in all copies or +// substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, +// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR +// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE +// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR +// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +// DEALINGS IN THE SOFTWARE. + +using System; +using System.Collections.Generic; +using System.Diagnostics; + +using Mono.Cecil; +using Mono.Cecil.Cil; + +namespace ICSharpCode.Decompiler.FlowAnalysis +{ + /// <summary> + /// Constructs "SsaForm" graph for a CFG. + /// This class transforms the method from stack-based IL to a register-based IL language. + /// Then it calls into TransformToSsa to convert the resulting graph to static single assignment form. + /// </summary> + public sealed class SsaFormBuilder + { + public static SsaForm Build(MethodDefinition method) + { + if (method == null) + throw new ArgumentNullException("method"); + var cfg = ControlFlowGraphBuilder.Build(method.Body); + cfg.ComputeDominance(); + cfg.ComputeDominanceFrontier(); + var ssa = BuildRegisterIL(method, cfg); + TransformToSsa.Transform(cfg, ssa); + return ssa; + } + + public static SsaForm BuildRegisterIL(MethodDefinition method, ControlFlowGraph cfg) + { + if (method == null) + throw new ArgumentNullException("method"); + if (cfg == null) + throw new ArgumentNullException("cfg"); + return new SsaFormBuilder(method, cfg).Build(); + } + + readonly MethodDefinition method; + readonly ControlFlowGraph cfg; + + readonly SsaBlock[] blocks; // array index = block index + readonly int[] stackSizeAtBlockStart; // array index = block index + + readonly SsaVariable[] parameters; // array index = parameter number + readonly SsaVariable[] locals; // array index = local number + readonly SsaVariable[] stackLocations; // array index = position on the IL evaluation stack + SsaForm ssaForm; + + SsaFormBuilder(MethodDefinition method, ControlFlowGraph cfg) + { + this.method = method; + this.cfg = cfg; + + blocks = new SsaBlock[cfg.Nodes.Count]; + stackSizeAtBlockStart = new int[cfg.Nodes.Count]; + for (int i = 0; i < stackSizeAtBlockStart.Length; i++) { + stackSizeAtBlockStart[i] = -1; + } + stackSizeAtBlockStart[cfg.EntryPoint.BlockIndex] = 0; + + parameters = new SsaVariable[method.Parameters.Count + (method.HasThis ? 1 : 0)]; + if (method.HasThis) + parameters[0] = new SsaVariable(method.Body.ThisParameter); + for (int i = 0; i < method.Parameters.Count; i++) + parameters[i + (method.HasThis ? 1 : 0)] = new SsaVariable(method.Parameters[i]); + + locals = new SsaVariable[method.Body.Variables.Count]; + for (int i = 0; i < locals.Length; i++) + locals[i] = new SsaVariable(method.Body.Variables[i]); + + stackLocations = new SsaVariable[method.Body.MaxStackSize]; + for (int i = 0; i < stackLocations.Length; i++) { + stackLocations[i] = new SsaVariable(i); + } + } + + internal SsaForm Build() + { + CreateGraphStructure(); + ssaForm = new SsaForm(blocks, parameters, locals, stackLocations, method.HasThis); + CreateInstructions(cfg.EntryPoint.BlockIndex); + CreateSpecialInstructions(); + return ssaForm; + } + + void CreateGraphStructure() + { + for (int i = 0; i < blocks.Length; i++) { + blocks[i] = new SsaBlock(cfg.Nodes[i]); + } + for (int i = 0; i < blocks.Length; i++) { + foreach (ControlFlowNode node in cfg.Nodes[i].Successors) { + blocks[i].Successors.Add(blocks[node.BlockIndex]); + blocks[node.BlockIndex].Predecessors.Add(blocks[i]); + } + } + } + + void CreateInstructions(int blockIndex) + { + ControlFlowNode cfgNode = cfg.Nodes[blockIndex]; + SsaBlock block = blocks[blockIndex]; + + int stackSize = stackSizeAtBlockStart[blockIndex]; + Debug.Assert(stackSize >= 0); + + List<Instruction> prefixes = new List<Instruction>(); + foreach (Instruction inst in cfgNode.Instructions) { + if (inst.OpCode.OpCodeType == OpCodeType.Prefix) { + prefixes.Add(inst); + continue; + } + + int popCount = inst.GetPopDelta(method) ?? stackSize; + stackSize -= popCount; + if (stackSize < 0) + throw new InvalidProgramException("IL stack underflow"); + + int pushCount = inst.GetPushDelta(); + if (stackSize + pushCount > stackLocations.Length) + throw new InvalidProgramException("IL stack overflow"); + + SsaVariable target; + SsaVariable[] operands; + DetermineOperands(stackSize, inst, popCount, pushCount, out target, out operands); + + Instruction[] prefixArray = prefixes.Count > 0 ? prefixes.ToArray() : null; + prefixes.Clear(); + + // ignore NOP instructions + if (!(inst.OpCode == OpCodes.Nop || inst.OpCode == OpCodes.Pop)) { + block.Instructions.Add(new SsaInstruction(block, inst, target, operands, prefixArray)); + } + stackSize += pushCount; + } + + foreach (ControlFlowEdge edge in cfgNode.Outgoing) { + int newStackSize; + switch (edge.Type) { + case JumpType.Normal: + newStackSize = stackSize; + break; + case JumpType.EndFinally: + if (stackSize != 0) + throw new NotSupportedException("stacksize must be 0 in endfinally edge"); + newStackSize = 0; + break; + case JumpType.JumpToExceptionHandler: + switch (edge.Target.NodeType) { + case ControlFlowNodeType.FinallyOrFaultHandler: + newStackSize = 0; + break; + case ControlFlowNodeType.ExceptionalExit: + case ControlFlowNodeType.CatchHandler: + newStackSize = 1; + break; + default: + throw new NotSupportedException("unsupported target node type: " + edge.Target.NodeType); + } + break; + default: + throw new NotSupportedException("unsupported jump type: " + edge.Type); + } + + int nextStackSize = stackSizeAtBlockStart[edge.Target.BlockIndex]; + if (nextStackSize == -1) { + stackSizeAtBlockStart[edge.Target.BlockIndex] = newStackSize; + CreateInstructions(edge.Target.BlockIndex); + } else if (nextStackSize != newStackSize) { + throw new InvalidProgramException("Stack size doesn't match"); + } + } + } + + void DetermineOperands(int stackSize, Instruction inst, int popCount, int pushCount, out SsaVariable target, out SsaVariable[] operands) + { + switch (inst.OpCode.Code) { + case Code.Ldarg: + operands = new SsaVariable[] { ssaForm.GetOriginalVariable((ParameterReference)inst.Operand) }; + target = stackLocations[stackSize]; + break; + case Code.Starg: + operands = new SsaVariable[] { stackLocations[stackSize] }; + target = ssaForm.GetOriginalVariable((ParameterReference)inst.Operand); + break; + case Code.Ldloc: + operands = new SsaVariable[] { ssaForm.GetOriginalVariable((VariableReference)inst.Operand) }; + target = stackLocations[stackSize]; + break; + case Code.Stloc: + operands = new SsaVariable[] { stackLocations[stackSize] }; + target = ssaForm.GetOriginalVariable((VariableReference)inst.Operand); + break; + case Code.Dup: + operands = new SsaVariable[] { stackLocations[stackSize] }; + target = stackLocations[stackSize + 1]; + break; + default: + operands = new SsaVariable[popCount]; + for (int i = 0; i < popCount; i++) { + operands[i] = stackLocations[stackSize + i]; + } + + switch (pushCount) { + case 0: + target = null; + break; + case 1: + target = stackLocations[stackSize]; + break; + default: + throw new NotSupportedException("unsupported pushCount=" + pushCount); + } + break; + } + } + + void CreateSpecialInstructions() + { + // Everything needs an initial write for the SSA transformation to work correctly. + foreach (SsaVariable v in parameters) { + ssaForm.EntryPoint.Instructions.Add(new SsaInstruction(ssaForm.EntryPoint, null, v, null, specialOpCode: SpecialOpCode.Parameter)); + } + foreach (SsaVariable v in locals) { + ssaForm.EntryPoint.Instructions.Add(new SsaInstruction(ssaForm.EntryPoint, null, v, null, specialOpCode: SpecialOpCode.Uninitialized)); + } + foreach (SsaVariable v in stackLocations) { + ssaForm.EntryPoint.Instructions.Add(new SsaInstruction(ssaForm.EntryPoint, null, v, null, specialOpCode: SpecialOpCode.Uninitialized)); + } + foreach (SsaBlock b in blocks) { + if (b.NodeType == ControlFlowNodeType.CatchHandler) { + b.Instructions.Add(new SsaInstruction(b, null, stackLocations[0], null, + specialOpCode: SpecialOpCode.Exception, + typeOperand: cfg.Nodes[b.BlockIndex].ExceptionHandler.CatchType)); + } + } + } + } +} |