summaryrefslogtreecommitdiff
path: root/ICSharpCode.Decompiler/ILAst/ILAstOptimizer.cs
diff options
context:
space:
mode:
authorJason Smith <jason.smith@xamarin.com>2016-03-22 13:02:25 -0700
committerJason Smith <jason.smith@xamarin.com>2016-03-22 16:13:41 -0700
commit17fdde66d94155fc62a034fa6658995bef6fd6e5 (patch)
treeb5e5073a2a7b15cdbe826faa5c763e270a505729 /ICSharpCode.Decompiler/ILAst/ILAstOptimizer.cs
downloadxamarin-forms-17fdde66d94155fc62a034fa6658995bef6fd6e5.tar.gz
xamarin-forms-17fdde66d94155fc62a034fa6658995bef6fd6e5.tar.bz2
xamarin-forms-17fdde66d94155fc62a034fa6658995bef6fd6e5.zip
Initial import
Diffstat (limited to 'ICSharpCode.Decompiler/ILAst/ILAstOptimizer.cs')
-rw-r--r--ICSharpCode.Decompiler/ILAst/ILAstOptimizer.cs988
1 files changed, 988 insertions, 0 deletions
diff --git a/ICSharpCode.Decompiler/ILAst/ILAstOptimizer.cs b/ICSharpCode.Decompiler/ILAst/ILAstOptimizer.cs
new file mode 100644
index 00000000..876718bc
--- /dev/null
+++ b/ICSharpCode.Decompiler/ILAst/ILAstOptimizer.cs
@@ -0,0 +1,988 @@
+// 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 ICSharpCode.Decompiler.FlowAnalysis;
+using ICSharpCode.NRefactory.Utils;
+using Mono.Cecil;
+using Mono.Cecil.Cil;
+using Mono.CSharp;
+
+namespace ICSharpCode.Decompiler.ILAst
+{
+ public enum ILAstOptimizationStep
+ {
+ RemoveRedundantCode,
+ ReduceBranchInstructionSet,
+ InlineVariables,
+ CopyPropagation,
+ YieldReturn,
+ AsyncAwait,
+ PropertyAccessInstructions,
+ SplitToMovableBlocks,
+ TypeInference,
+ HandlePointerArithmetic,
+ SimplifyShortCircuit,
+ SimplifyTernaryOperator,
+ SimplifyNullCoalescing,
+ JoinBasicBlocks,
+ SimplifyLogicNot,
+ SimplifyShiftOperators,
+ TypeConversionSimplifications,
+ SimplifyLdObjAndStObj,
+ SimplifyCustomShortCircuit,
+ SimplifyLiftedOperators,
+ TransformArrayInitializers,
+ TransformMultidimensionalArrayInitializers,
+ TransformObjectInitializers,
+ MakeAssignmentExpression,
+ IntroducePostIncrement,
+ InlineExpressionTreeParameterDeclarations,
+ InlineVariables2,
+ FindLoops,
+ FindConditions,
+ FlattenNestedMovableBlocks,
+ RemoveEndFinally,
+ RemoveRedundantCode2,
+ GotoRemoval,
+ DuplicateReturns,
+ GotoRemoval2,
+ ReduceIfNesting,
+ InlineVariables3,
+ CachedDelegateInitialization,
+ IntroduceFixedStatements,
+ RecombineVariables,
+ TypeInference2,
+ RemoveRedundantCode3,
+ None
+ }
+
+ public partial class ILAstOptimizer
+ {
+ int nextLabelIndex = 0;
+
+ DecompilerContext context;
+ TypeSystem typeSystem;
+ ILBlock method;
+
+ public void Optimize(DecompilerContext context, ILBlock method, ILAstOptimizationStep abortBeforeStep = ILAstOptimizationStep.None)
+ {
+ this.context = context;
+ typeSystem = context.CurrentMethod.Module.TypeSystem;
+ this.method = method;
+
+ if (abortBeforeStep == ILAstOptimizationStep.RemoveRedundantCode) return;
+ RemoveRedundantCode(method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.ReduceBranchInstructionSet) return;
+ foreach(ILBlock block in method.GetSelfAndChildrenRecursive<ILBlock>()) {
+ ReduceBranchInstructionSet(block);
+ }
+ // ReduceBranchInstructionSet runs before inlining because the non-aggressive inlining heuristic
+ // looks at which type of instruction consumes the inlined variable.
+
+ if (abortBeforeStep == ILAstOptimizationStep.InlineVariables) return;
+ // Works better after simple goto removal because of the following debug pattern: stloc X; br Next; Next:; ldloc X
+ ILInlining inlining1 = new ILInlining(method);
+ inlining1.InlineAllVariables();
+
+ if (abortBeforeStep == ILAstOptimizationStep.CopyPropagation) return;
+ inlining1.CopyPropagation();
+
+ if (abortBeforeStep == ILAstOptimizationStep.YieldReturn) return;
+ YieldReturnDecompiler.Run(context, method);
+ AsyncDecompiler.RunStep1(context, method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.AsyncAwait) return;
+ AsyncDecompiler.RunStep2(context, method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.PropertyAccessInstructions) return;
+ IntroducePropertyAccessInstructions(method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.SplitToMovableBlocks) return;
+ foreach(ILBlock block in method.GetSelfAndChildrenRecursive<ILBlock>()) {
+ SplitToBasicBlocks(block);
+ }
+
+ if (abortBeforeStep == ILAstOptimizationStep.TypeInference) return;
+ // Types are needed for the ternary operator optimization
+ TypeAnalysis.Run(context, method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.HandlePointerArithmetic) return;
+ HandlePointerArithmetic(method);
+
+ foreach(ILBlock block in method.GetSelfAndChildrenRecursive<ILBlock>()) {
+ bool modified;
+ do {
+ modified = false;
+
+ if (abortBeforeStep == ILAstOptimizationStep.SimplifyShortCircuit) return;
+ modified |= block.RunOptimization(new SimpleControlFlow(context, method).SimplifyShortCircuit);
+
+ if (abortBeforeStep == ILAstOptimizationStep.SimplifyTernaryOperator) return;
+ modified |= block.RunOptimization(new SimpleControlFlow(context, method).SimplifyTernaryOperator);
+
+ if (abortBeforeStep == ILAstOptimizationStep.SimplifyNullCoalescing) return;
+ modified |= block.RunOptimization(new SimpleControlFlow(context, method).SimplifyNullCoalescing);
+
+ if (abortBeforeStep == ILAstOptimizationStep.JoinBasicBlocks) return;
+ modified |= block.RunOptimization(new SimpleControlFlow(context, method).JoinBasicBlocks);
+
+ if (abortBeforeStep == ILAstOptimizationStep.SimplifyLogicNot) return;
+ modified |= block.RunOptimization(SimplifyLogicNot);
+
+ if (abortBeforeStep == ILAstOptimizationStep.SimplifyShiftOperators) return;
+ modified |= block.RunOptimization(SimplifyShiftOperators);
+
+ if (abortBeforeStep == ILAstOptimizationStep.TypeConversionSimplifications) return;
+ modified |= block.RunOptimization(TypeConversionSimplifications);
+
+ if (abortBeforeStep == ILAstOptimizationStep.SimplifyLdObjAndStObj) return;
+ modified |= block.RunOptimization(SimplifyLdObjAndStObj);
+
+ if (abortBeforeStep == ILAstOptimizationStep.SimplifyCustomShortCircuit) return;
+ modified |= block.RunOptimization(new SimpleControlFlow(context, method).SimplifyCustomShortCircuit);
+
+ if (abortBeforeStep == ILAstOptimizationStep.SimplifyLiftedOperators) return;
+ modified |= block.RunOptimization(SimplifyLiftedOperators);
+
+ if (abortBeforeStep == ILAstOptimizationStep.TransformArrayInitializers) return;
+ modified |= block.RunOptimization(TransformArrayInitializers);
+
+ if (abortBeforeStep == ILAstOptimizationStep.TransformMultidimensionalArrayInitializers) return;
+ modified |= block.RunOptimization(TransformMultidimensionalArrayInitializers);
+
+ if (abortBeforeStep == ILAstOptimizationStep.TransformObjectInitializers) return;
+ modified |= block.RunOptimization(TransformObjectInitializers);
+
+ if (abortBeforeStep == ILAstOptimizationStep.MakeAssignmentExpression) return;
+ if (context.Settings.MakeAssignmentExpressions) {
+ modified |= block.RunOptimization(MakeAssignmentExpression);
+ }
+ modified |= block.RunOptimization(MakeCompoundAssignments);
+
+ if (abortBeforeStep == ILAstOptimizationStep.IntroducePostIncrement) return;
+ if (context.Settings.IntroduceIncrementAndDecrement) {
+ modified |= block.RunOptimization(IntroducePostIncrement);
+ }
+
+ if (abortBeforeStep == ILAstOptimizationStep.InlineExpressionTreeParameterDeclarations) return;
+ if (context.Settings.ExpressionTrees) {
+ modified |= block.RunOptimization(InlineExpressionTreeParameterDeclarations);
+ }
+
+ if (abortBeforeStep == ILAstOptimizationStep.InlineVariables2) return;
+ modified |= new ILInlining(method).InlineAllInBlock(block);
+ new ILInlining(method).CopyPropagation();
+
+ } while(modified);
+ }
+
+ if (abortBeforeStep == ILAstOptimizationStep.FindLoops) return;
+ foreach(ILBlock block in method.GetSelfAndChildrenRecursive<ILBlock>()) {
+ new LoopsAndConditions(context).FindLoops(block);
+ }
+
+ if (abortBeforeStep == ILAstOptimizationStep.FindConditions) return;
+ foreach(ILBlock block in method.GetSelfAndChildrenRecursive<ILBlock>()) {
+ new LoopsAndConditions(context).FindConditions(block);
+ }
+
+ if (abortBeforeStep == ILAstOptimizationStep.FlattenNestedMovableBlocks) return;
+ FlattenBasicBlocks(method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.RemoveEndFinally) return;
+ RemoveEndFinally(method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.RemoveRedundantCode2) return;
+ RemoveRedundantCode(method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.GotoRemoval) return;
+ new GotoRemoval().RemoveGotos(method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.DuplicateReturns) return;
+ DuplicateReturnStatements(method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.GotoRemoval2) return;
+ new GotoRemoval().RemoveGotos(method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.ReduceIfNesting) return;
+ ReduceIfNesting(method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.InlineVariables3) return;
+ // The 2nd inlining pass is necessary because DuplicateReturns and the introduction of ternary operators
+ // open up additional inlining possibilities.
+ new ILInlining(method).InlineAllVariables();
+
+ if (abortBeforeStep == ILAstOptimizationStep.CachedDelegateInitialization) return;
+ if (context.Settings.AnonymousMethods) {
+ foreach(ILBlock block in method.GetSelfAndChildrenRecursive<ILBlock>()) {
+ for (int i = 0; i < block.Body.Count; i++) {
+ // TODO: Move before loops
+ CachedDelegateInitializationWithField(block, ref i);
+ CachedDelegateInitializationWithLocal(block, ref i);
+ }
+ }
+ }
+
+ if (abortBeforeStep == ILAstOptimizationStep.IntroduceFixedStatements) return;
+ // we need post-order traversal, not pre-order, for "fixed" to work correctly
+ foreach (ILBlock block in TreeTraversal.PostOrder<ILNode>(method, n => n.GetChildren()).OfType<ILBlock>()) {
+ for (int i = block.Body.Count - 1; i >= 0; i--) {
+ // TODO: Move before loops
+ if (i < block.Body.Count)
+ IntroduceFixedStatements(block.Body, i);
+ }
+ }
+
+ if (abortBeforeStep == ILAstOptimizationStep.RecombineVariables) return;
+ RecombineVariables(method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.TypeInference2) return;
+ TypeAnalysis.Reset(method);
+ TypeAnalysis.Run(context, method);
+
+ if (abortBeforeStep == ILAstOptimizationStep.RemoveRedundantCode3) return;
+ GotoRemoval.RemoveRedundantCode(method);
+
+ // ReportUnassignedILRanges(method);
+ }
+
+ /// <summary>
+ /// Removes redundatant Br, Nop, Dup, Pop
+ /// Ignore arguments of 'leave'
+ /// </summary>
+ /// <param name="method"></param>
+ internal static void RemoveRedundantCode(ILBlock method)
+ {
+ Dictionary<ILLabel, int> labelRefCount = new Dictionary<ILLabel, int>();
+ foreach (ILLabel target in method.GetSelfAndChildrenRecursive<ILExpression>(e => e.IsBranch()).SelectMany(e => e.GetBranchTargets())) {
+ labelRefCount[target] = labelRefCount.GetOrDefault(target) + 1;
+ }
+
+ foreach(ILBlock block in method.GetSelfAndChildrenRecursive<ILBlock>()) {
+ List<ILNode> body = block.Body;
+ List<ILNode> newBody = new List<ILNode>(body.Count);
+ for (int i = 0; i < body.Count; i++) {
+ ILLabel target;
+ ILExpression popExpr;
+ if (body[i].Match(ILCode.Br, out target) && i+1 < body.Count && body[i+1] == target) {
+ // Ignore the branch
+ if (labelRefCount[target] == 1)
+ i++; // Ignore the label as well
+ } else if (body[i].Match(ILCode.Nop)){
+ // Ignore nop
+ } else if (body[i].Match(ILCode.Pop, out popExpr)) {
+ ILVariable v;
+ if (!popExpr.Match(ILCode.Ldloc, out v))
+ throw new Exception("Pop should have just ldloc at this stage");
+ // Best effort to move the ILRange to previous statement
+ ILVariable prevVar;
+ ILExpression prevExpr;
+ if (i - 1 >= 0 && body[i - 1].Match(ILCode.Stloc, out prevVar, out prevExpr) && prevVar == v)
+ prevExpr.ILRanges.AddRange(((ILExpression)body[i]).ILRanges);
+ // Ignore pop
+ } else {
+ ILLabel label = body[i] as ILLabel;
+ if (label != null) {
+ if (labelRefCount.GetOrDefault(label) > 0)
+ newBody.Add(label);
+ } else {
+ newBody.Add(body[i]);
+ }
+ }
+ }
+ block.Body = newBody;
+ }
+
+ // Ignore arguments of 'leave'
+ foreach (ILExpression expr in method.GetSelfAndChildrenRecursive<ILExpression>(e => e.Code == ILCode.Leave)) {
+ if (expr.Arguments.Any(arg => !arg.Match(ILCode.Ldloc)))
+ throw new Exception("Leave should have just ldloc at this stage");
+ expr.Arguments.Clear();
+ }
+
+ // 'dup' removal
+ foreach (ILExpression expr in method.GetSelfAndChildrenRecursive<ILExpression>()) {
+ for (int i = 0; i < expr.Arguments.Count; i++) {
+ ILExpression child;
+ if (expr.Arguments[i].Match(ILCode.Dup, out child)) {
+ child.ILRanges.AddRange(expr.Arguments[i].ILRanges);
+ expr.Arguments[i] = child;
+ }
+ }
+ }
+ }
+
+ /// <summary>
+ /// Reduces the branch codes to just br and brtrue.
+ /// Moves ILRanges to the branch argument
+ /// </summary>
+ void ReduceBranchInstructionSet(ILBlock block)
+ {
+ for (int i = 0; i < block.Body.Count; i++) {
+ ILExpression expr = block.Body[i] as ILExpression;
+ if (expr != null && expr.Prefixes == null) {
+ ILCode op;
+ switch(expr.Code) {
+ case ILCode.Switch:
+ case ILCode.Brtrue:
+ expr.Arguments.Single().ILRanges.AddRange(expr.ILRanges);
+ expr.ILRanges.Clear();
+ continue;
+ case ILCode.__Brfalse: op = ILCode.LogicNot; break;
+ case ILCode.__Beq: op = ILCode.Ceq; break;
+ case ILCode.__Bne_Un: op = ILCode.Cne; break;
+ case ILCode.__Bgt: op = ILCode.Cgt; break;
+ case ILCode.__Bgt_Un: op = ILCode.Cgt_Un; break;
+ case ILCode.__Ble: op = ILCode.Cle; break;
+ case ILCode.__Ble_Un: op = ILCode.Cle_Un; break;
+ case ILCode.__Blt: op = ILCode.Clt; break;
+ case ILCode.__Blt_Un: op = ILCode.Clt_Un; break;
+ case ILCode.__Bge: op = ILCode.Cge; break;
+ case ILCode.__Bge_Un: op = ILCode.Cge_Un; break;
+ default:
+ continue;
+ }
+ var newExpr = new ILExpression(op, null, expr.Arguments);
+ block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, newExpr);
+ newExpr.ILRanges = expr.ILRanges;
+ }
+ }
+ }
+
+ /// <summary>
+ /// Converts call and callvirt instructions that read/write properties into CallGetter/CallSetter instructions.
+ ///
+ /// CallGetter/CallSetter is used to allow the ILAst to represent "while ((SomeProperty = value) != null)".
+ ///
+ /// Also simplifies 'newobj(SomeDelegate, target, ldvirtftn(F, target))' to 'newobj(SomeDelegate, target, ldvirtftn(F))'
+ /// </summary>
+ void IntroducePropertyAccessInstructions(ILNode node)
+ {
+ ILExpression parentExpr = node as ILExpression;
+ if (parentExpr != null) {
+ for (int i = 0; i < parentExpr.Arguments.Count; i++) {
+ ILExpression expr = parentExpr.Arguments[i];
+ IntroducePropertyAccessInstructions(expr);
+ IntroducePropertyAccessInstructions(expr, parentExpr, i);
+ }
+ } else {
+ foreach (ILNode child in node.GetChildren()) {
+ IntroducePropertyAccessInstructions(child);
+ ILExpression expr = child as ILExpression;
+ if (expr != null) {
+ IntroducePropertyAccessInstructions(expr, null, -1);
+ }
+ }
+ }
+ }
+
+ void IntroducePropertyAccessInstructions(ILExpression expr, ILExpression parentExpr, int posInParent)
+ {
+ if (expr.Code == ILCode.Call || expr.Code == ILCode.Callvirt) {
+ MethodReference cecilMethod = (MethodReference)expr.Operand;
+ if (cecilMethod.DeclaringType is ArrayType) {
+ switch (cecilMethod.Name) {
+ case "Get":
+ expr.Code = ILCode.CallGetter;
+ break;
+ case "Set":
+ expr.Code = ILCode.CallSetter;
+ break;
+ case "Address":
+ ByReferenceType brt = cecilMethod.ReturnType as ByReferenceType;
+ if (brt != null) {
+ MethodReference getMethod = new MethodReference("Get", brt.ElementType, cecilMethod.DeclaringType);
+ foreach (var p in cecilMethod.Parameters)
+ getMethod.Parameters.Add(p);
+ getMethod.HasThis = cecilMethod.HasThis;
+ expr.Operand = getMethod;
+ }
+ expr.Code = ILCode.CallGetter;
+ if (parentExpr != null) {
+ parentExpr.Arguments[posInParent] = new ILExpression(ILCode.AddressOf, null, expr);
+ }
+ break;
+ }
+ } else {
+ MethodDefinition cecilMethodDef = cecilMethod.Resolve();
+ if (cecilMethodDef != null) {
+ if (cecilMethodDef.IsGetter)
+ expr.Code = (expr.Code == ILCode.Call) ? ILCode.CallGetter : ILCode.CallvirtGetter;
+ else if (cecilMethodDef.IsSetter)
+ expr.Code = (expr.Code == ILCode.Call) ? ILCode.CallSetter : ILCode.CallvirtSetter;
+ }
+ }
+ } else if (expr.Code == ILCode.Newobj && expr.Arguments.Count == 2) {
+ // Might be 'newobj(SomeDelegate, target, ldvirtftn(F, target))'.
+ ILVariable target;
+ if (expr.Arguments[0].Match(ILCode.Ldloc, out target)
+ && expr.Arguments[1].Code == ILCode.Ldvirtftn
+ && expr.Arguments[1].Arguments.Count == 1
+ && expr.Arguments[1].Arguments[0].MatchLdloc(target))
+ {
+ // Remove the 'target' argument from the ldvirtftn instruction.
+ // It's not needed in the translation to C#, and needs to be eliminated so that the target expression
+ // can be inlined.
+ expr.Arguments[1].Arguments.Clear();
+ }
+ }
+ }
+
+ /// <summary>
+ /// Group input into a set of blocks that can be later arbitraliby schufled.
+ /// The method adds necessary branches to make control flow between blocks
+ /// explicit and thus order independent.
+ /// </summary>
+ void SplitToBasicBlocks(ILBlock block)
+ {
+ List<ILNode> basicBlocks = new List<ILNode>();
+
+ ILLabel entryLabel = block.Body.FirstOrDefault() as ILLabel ?? new ILLabel() { Name = "Block_" + (nextLabelIndex++) };
+ ILBasicBlock basicBlock = new ILBasicBlock();
+ basicBlocks.Add(basicBlock);
+ basicBlock.Body.Add(entryLabel);
+ block.EntryGoto = new ILExpression(ILCode.Br, entryLabel);
+
+ if (block.Body.Count > 0) {
+ if (block.Body[0] != entryLabel)
+ basicBlock.Body.Add(block.Body[0]);
+
+ for (int i = 1; i < block.Body.Count; i++) {
+ ILNode lastNode = block.Body[i - 1];
+ ILNode currNode = block.Body[i];
+
+ // Start a new basic block if necessary
+ if (currNode is ILLabel ||
+ currNode is ILTryCatchBlock || // Counts as label
+ lastNode.IsConditionalControlFlow() ||
+ lastNode.IsUnconditionalControlFlow())
+ {
+ // Try to reuse the label
+ ILLabel label = currNode as ILLabel ?? new ILLabel() { Name = "Block_" + (nextLabelIndex++).ToString() };
+
+ // Terminate the last block
+ if (!lastNode.IsUnconditionalControlFlow()) {
+ // Explicit branch from one block to other
+ basicBlock.Body.Add(new ILExpression(ILCode.Br, label));
+ }
+
+ // Start the new block
+ basicBlock = new ILBasicBlock();
+ basicBlocks.Add(basicBlock);
+ basicBlock.Body.Add(label);
+
+ // Add the node to the basic block
+ if (currNode != label)
+ basicBlock.Body.Add(currNode);
+ } else {
+ basicBlock.Body.Add(currNode);
+ }
+ }
+ }
+
+ block.Body = basicBlocks;
+ return;
+ }
+
+ void DuplicateReturnStatements(ILBlock method)
+ {
+ Dictionary<ILLabel, ILNode> nextSibling = new Dictionary<ILLabel, ILNode>();
+
+ // Build navigation data
+ foreach(ILBlock block in method.GetSelfAndChildrenRecursive<ILBlock>()) {
+ for (int i = 0; i < block.Body.Count - 1; i++) {
+ ILLabel curr = block.Body[i] as ILLabel;
+ if (curr != null) {
+ nextSibling[curr] = block.Body[i + 1];
+ }
+ }
+ }
+
+ // Duplicate returns
+ foreach(ILBlock block in method.GetSelfAndChildrenRecursive<ILBlock>()) {
+ for (int i = 0; i < block.Body.Count; i++) {
+ ILLabel targetLabel;
+ if (block.Body[i].Match(ILCode.Br, out targetLabel) || block.Body[i].Match(ILCode.Leave, out targetLabel)) {
+ // Skip extra labels
+ while(nextSibling.ContainsKey(targetLabel) && nextSibling[targetLabel] is ILLabel) {
+ targetLabel = (ILLabel)nextSibling[targetLabel];
+ }
+
+ // Inline return statement
+ ILNode target;
+ List<ILExpression> retArgs;
+ if (nextSibling.TryGetValue(targetLabel, out target)) {
+ if (target.Match(ILCode.Ret, out retArgs)) {
+ ILVariable locVar;
+ object constValue;
+ if (retArgs.Count == 0) {
+ block.Body[i] = new ILExpression(ILCode.Ret, null);
+ } else if (retArgs.Single().Match(ILCode.Ldloc, out locVar)) {
+ block.Body[i] = new ILExpression(ILCode.Ret, null, new ILExpression(ILCode.Ldloc, locVar));
+ } else if (retArgs.Single().Match(ILCode.Ldc_I4, out constValue)) {
+ block.Body[i] = new ILExpression(ILCode.Ret, null, new ILExpression(ILCode.Ldc_I4, constValue));
+ }
+ }
+ } else {
+ if (method.Body.Count > 0 && method.Body.Last() == targetLabel) {
+ // It exits the main method - so it is same as return;
+ block.Body[i] = new ILExpression(ILCode.Ret, null);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /// <summary>
+ /// Flattens all nested basic blocks, except the the top level 'node' argument
+ /// </summary>
+ void FlattenBasicBlocks(ILNode node)
+ {
+ ILBlock block = node as ILBlock;
+ if (block != null) {
+ List<ILNode> flatBody = new List<ILNode>();
+ foreach (ILNode child in block.GetChildren()) {
+ FlattenBasicBlocks(child);
+ ILBasicBlock childAsBB = child as ILBasicBlock;
+ if (childAsBB != null) {
+ if (!(childAsBB.Body.FirstOrDefault() is ILLabel))
+ throw new Exception("Basic block has to start with a label. \n" + childAsBB.ToString());
+ if (childAsBB.Body.LastOrDefault() is ILExpression && !childAsBB.Body.LastOrDefault().IsUnconditionalControlFlow())
+ throw new Exception("Basci block has to end with unconditional control flow. \n" + childAsBB.ToString());
+ flatBody.AddRange(childAsBB.GetChildren());
+ } else {
+ flatBody.Add(child);
+ }
+ }
+ block.EntryGoto = null;
+ block.Body = flatBody;
+ } else if (node is ILExpression) {
+ // Optimization - no need to check expressions
+ } else if (node != null) {
+ // Recursively find all ILBlocks
+ foreach(ILNode child in node.GetChildren()) {
+ FlattenBasicBlocks(child);
+ }
+ }
+ }
+
+ /// <summary>
+ /// Replace endfinally with jump to the end of the finally block
+ /// </summary>
+ void RemoveEndFinally(ILBlock method)
+ {
+ // Go thought the list in reverse so that we do the nested blocks first
+ foreach(var tryCatch in method.GetSelfAndChildrenRecursive<ILTryCatchBlock>(tc => tc.FinallyBlock != null).Reverse()) {
+ ILLabel label = new ILLabel() { Name = "EndFinally_" + nextLabelIndex++ };
+ tryCatch.FinallyBlock.Body.Add(label);
+ foreach(var block in tryCatch.FinallyBlock.GetSelfAndChildrenRecursive<ILBlock>()) {
+ for (int i = 0; i < block.Body.Count; i++) {
+ if (block.Body[i].Match(ILCode.Endfinally)) {
+ block.Body[i] = new ILExpression(ILCode.Br, label).WithILRanges(((ILExpression)block.Body[i]).ILRanges);
+ }
+ }
+ }
+ }
+ }
+
+ /// <summary>
+ /// Reduce the nesting of conditions.
+ /// It should be done on flat data that already had most gotos removed
+ /// </summary>
+ void ReduceIfNesting(ILNode node)
+ {
+ ILBlock block = node as ILBlock;
+ if (block != null) {
+ for (int i = 0; i < block.Body.Count; i++) {
+ ILCondition cond = block.Body[i] as ILCondition;
+ if (cond != null) {
+ bool trueExits = cond.TrueBlock.Body.LastOrDefault().IsUnconditionalControlFlow();
+ bool falseExits = cond.FalseBlock.Body.LastOrDefault().IsUnconditionalControlFlow();
+
+ if (trueExits) {
+ // Move the false block after the condition
+ block.Body.InsertRange(i + 1, cond.FalseBlock.GetChildren());
+ cond.FalseBlock = new ILBlock();
+ } else if (falseExits) {
+ // Move the true block after the condition
+ block.Body.InsertRange(i + 1, cond.TrueBlock.GetChildren());
+ cond.TrueBlock = new ILBlock();
+ }
+
+ // Eliminate empty true block
+ if (!cond.TrueBlock.GetChildren().Any() && cond.FalseBlock.GetChildren().Any()) {
+ // Swap bodies
+ ILBlock tmp = cond.TrueBlock;
+ cond.TrueBlock = cond.FalseBlock;
+ cond.FalseBlock = tmp;
+ cond.Condition = new ILExpression(ILCode.LogicNot, null, cond.Condition);
+ }
+ }
+ }
+ }
+
+ // We are changing the number of blocks so we use plain old recursion to get all blocks
+ foreach(ILNode child in node.GetChildren()) {
+ if (child != null && !(child is ILExpression))
+ ReduceIfNesting(child);
+ }
+ }
+
+ void RecombineVariables(ILBlock method)
+ {
+ // Recombine variables that were split when the ILAst was created
+ // This ensures that a single IL variable is a single C# variable (gets assigned only one name)
+ // The DeclareVariables transformation might then split up the C# variable again if it is used indendently in two separate scopes.
+ Dictionary<VariableDefinition, ILVariable> dict = new Dictionary<VariableDefinition, ILVariable>();
+ ReplaceVariables(
+ method,
+ delegate(ILVariable v) {
+ if (v.OriginalVariable == null)
+ return v;
+ ILVariable combinedVariable;
+ if (!dict.TryGetValue(v.OriginalVariable, out combinedVariable)) {
+ dict.Add(v.OriginalVariable, v);
+ combinedVariable = v;
+ }
+ return combinedVariable;
+ });
+ }
+
+ static void HandlePointerArithmetic(ILNode method)
+ {
+ foreach (ILExpression expr in method.GetSelfAndChildrenRecursive<ILExpression>()) {
+ List<ILExpression> args = expr.Arguments;
+ switch (expr.Code) {
+ case ILCode.Localloc:
+ args[0] = DivideBySize(args[0], ((PointerType)expr.InferredType).ElementType);
+ break;
+ case ILCode.Add:
+ case ILCode.Add_Ovf:
+ case ILCode.Add_Ovf_Un:
+ if (expr.InferredType is PointerType) {
+ if (args[0].ExpectedType is PointerType)
+ args[1] = DivideBySize(args[1], ((PointerType)expr.InferredType).ElementType);
+ else if (args[1].ExpectedType is PointerType)
+ args[0] = DivideBySize(args[0], ((PointerType)expr.InferredType).ElementType);
+ }
+ break;
+ case ILCode.Sub:
+ case ILCode.Sub_Ovf:
+ case ILCode.Sub_Ovf_Un:
+ if (expr.InferredType is PointerType) {
+ if (args[0].ExpectedType is PointerType)
+ args[1] = DivideBySize(args[1], ((PointerType)expr.InferredType).ElementType);
+ }
+ break;
+ }
+ }
+ }
+
+ static ILExpression UnwrapIntPtrCast(ILExpression expr)
+ {
+ if (expr.Code != ILCode.Conv_I && expr.Code != ILCode.Conv_U)
+ return expr;
+
+ ILExpression arg = expr.Arguments[0];
+ switch (arg.InferredType.MetadataType) {
+ case MetadataType.Byte:
+ case MetadataType.SByte:
+ case MetadataType.UInt16:
+ case MetadataType.Int16:
+ case MetadataType.UInt32:
+ case MetadataType.Int32:
+ case MetadataType.UInt64:
+ case MetadataType.Int64:
+ return arg;
+ }
+
+ return expr;
+ }
+
+ static ILExpression DivideBySize(ILExpression expr, TypeReference type)
+ {
+ expr = UnwrapIntPtrCast(expr);
+
+ ILExpression sizeOfExpression;
+ switch (TypeAnalysis.GetInformationAmount(type)) {
+ case 1:
+ case 8:
+ sizeOfExpression = new ILExpression(ILCode.Ldc_I4, 1);
+ break;
+ case 16:
+ sizeOfExpression = new ILExpression(ILCode.Ldc_I4, 2);
+ break;
+ case 32:
+ sizeOfExpression = new ILExpression(ILCode.Ldc_I4, 4);
+ break;
+ case 64:
+ sizeOfExpression = new ILExpression(ILCode.Ldc_I4, 8);
+ break;
+ default:
+ sizeOfExpression = new ILExpression(ILCode.Sizeof, type);
+ break;
+ }
+
+ if (expr.Code == ILCode.Mul || expr.Code == ILCode.Mul_Ovf || expr.Code == ILCode.Mul_Ovf_Un) {
+ ILExpression mulArg = expr.Arguments[1];
+ if (mulArg.Code == sizeOfExpression.Code && sizeOfExpression.Operand.Equals(mulArg.Operand))
+ return UnwrapIntPtrCast(expr.Arguments[0]);
+ }
+
+ if (expr.Code == sizeOfExpression.Code) {
+ if (sizeOfExpression.Operand.Equals(expr.Operand))
+ return new ILExpression(ILCode.Ldc_I4, 1);
+
+ if (expr.Code == ILCode.Ldc_I4) {
+ int offsetInBytes = (int)expr.Operand;
+ int elementSize = (int)sizeOfExpression.Operand;
+ int offsetInElements = offsetInBytes / elementSize;
+
+ // ensure integer division
+ if (offsetInElements * elementSize == offsetInBytes) {
+ expr.Operand = offsetInElements;
+ return expr;
+ }
+ }
+ }
+
+ return new ILExpression(ILCode.Div_Un, null, expr, sizeOfExpression);
+ }
+
+ public static void ReplaceVariables(ILNode node, Func<ILVariable, ILVariable> variableMapping)
+ {
+ ILExpression expr = node as ILExpression;
+ if (expr != null) {
+ ILVariable v = expr.Operand as ILVariable;
+ if (v != null)
+ expr.Operand = variableMapping(v);
+ foreach (ILExpression child in expr.Arguments)
+ ReplaceVariables(child, variableMapping);
+ } else {
+ var catchBlock = node as ILTryCatchBlock.CatchBlock;
+ if (catchBlock != null && catchBlock.ExceptionVariable != null) {
+ catchBlock.ExceptionVariable = variableMapping(catchBlock.ExceptionVariable);
+ }
+
+ foreach (ILNode child in node.GetChildren())
+ ReplaceVariables(child, variableMapping);
+ }
+ }
+
+ void ReportUnassignedILRanges(ILBlock method)
+ {
+ var unassigned = ILRange.Invert(method.GetSelfAndChildrenRecursive<ILExpression>().SelectMany(e => e.ILRanges), context.CurrentMethod.Body.CodeSize).ToList();
+ if (unassigned.Count > 0)
+ Debug.WriteLine(string.Format("Unassigned ILRanges for {0}.{1}: {2}", context.CurrentMethod.DeclaringType.Name, context.CurrentMethod.Name, string.Join(", ", unassigned.Select(r => r.ToString()))));
+ }
+ }
+
+ public static class ILAstOptimizerExtensionMethods
+ {
+ /// <summary>
+ /// Perform one pass of a given optimization on this block.
+ /// This block must consist of only basicblocks.
+ /// </summary>
+ public static bool RunOptimization(this ILBlock block, Func<List<ILNode>, ILBasicBlock, int, bool> optimization)
+ {
+ bool modified = false;
+ List<ILNode> body = block.Body;
+ for (int i = body.Count - 1; i >= 0; i--) {
+ if (i < body.Count && optimization(body, (ILBasicBlock)body[i], i)) {
+ modified = true;
+ }
+ }
+ return modified;
+ }
+
+ public static bool RunOptimization(this ILBlock block, Func<List<ILNode>, ILExpression, int, bool> optimization)
+ {
+ bool modified = false;
+ foreach (ILBasicBlock bb in block.Body) {
+ for (int i = bb.Body.Count - 1; i >= 0; i--) {
+ ILExpression expr = bb.Body.ElementAtOrDefault(i) as ILExpression;
+ if (expr != null && optimization(bb.Body, expr, i)) {
+ modified = true;
+ }
+ }
+ }
+ return modified;
+ }
+
+ public static bool IsConditionalControlFlow(this ILNode node)
+ {
+ ILExpression expr = node as ILExpression;
+ return expr != null && expr.Code.IsConditionalControlFlow();
+ }
+
+ public static bool IsUnconditionalControlFlow(this ILNode node)
+ {
+ ILExpression expr = node as ILExpression;
+ return expr != null && expr.Code.IsUnconditionalControlFlow();
+ }
+
+ /// <summary>
+ /// The expression has no effect on the program and can be removed
+ /// if its return value is not needed.
+ /// </summary>
+ public static bool HasNoSideEffects(this ILExpression expr)
+ {
+ // Remember that if expression can throw an exception, it is a side effect
+
+ switch(expr.Code) {
+ case ILCode.Ldloc:
+ case ILCode.Ldloca:
+ case ILCode.Ldstr:
+ case ILCode.Ldnull:
+ case ILCode.Ldc_I4:
+ case ILCode.Ldc_I8:
+ case ILCode.Ldc_R4:
+ case ILCode.Ldc_R8:
+ case ILCode.Ldc_Decimal:
+ return true;
+ default:
+ return false;
+ }
+ }
+
+ public static bool IsStoreToArray(this ILCode code)
+ {
+ switch (code) {
+ case ILCode.Stelem_Any:
+ case ILCode.Stelem_I:
+ case ILCode.Stelem_I1:
+ case ILCode.Stelem_I2:
+ case ILCode.Stelem_I4:
+ case ILCode.Stelem_I8:
+ case ILCode.Stelem_R4:
+ case ILCode.Stelem_R8:
+ case ILCode.Stelem_Ref:
+ return true;
+ default:
+ return false;
+ }
+ }
+
+ public static bool IsLoadFromArray(this ILCode code)
+ {
+ switch (code) {
+ case ILCode.Ldelem_Any:
+ case ILCode.Ldelem_I:
+ case ILCode.Ldelem_I1:
+ case ILCode.Ldelem_I2:
+ case ILCode.Ldelem_I4:
+ case ILCode.Ldelem_I8:
+ case ILCode.Ldelem_U1:
+ case ILCode.Ldelem_U2:
+ case ILCode.Ldelem_U4:
+ case ILCode.Ldelem_R4:
+ case ILCode.Ldelem_R8:
+ case ILCode.Ldelem_Ref:
+ return true;
+ default:
+ return false;
+ }
+ }
+
+ /// <summary>
+ /// Can the expression be used as a statement in C#?
+ /// </summary>
+ public static bool CanBeExpressionStatement(this ILExpression expr)
+ {
+ switch(expr.Code) {
+ case ILCode.Call:
+ case ILCode.Callvirt:
+ // property getters can't be expression statements, but all other method calls can be
+ MethodReference mr = (MethodReference)expr.Operand;
+ return !mr.Name.StartsWith("get_", StringComparison.Ordinal);
+ case ILCode.CallSetter:
+ case ILCode.CallvirtSetter:
+ case ILCode.Newobj:
+ case ILCode.Newarr:
+ case ILCode.Stloc:
+ case ILCode.Stobj:
+ case ILCode.Stsfld:
+ case ILCode.Stfld:
+ case ILCode.Stind_Ref:
+ case ILCode.Stelem_Any:
+ case ILCode.Stelem_I:
+ case ILCode.Stelem_I1:
+ case ILCode.Stelem_I2:
+ case ILCode.Stelem_I4:
+ case ILCode.Stelem_I8:
+ case ILCode.Stelem_R4:
+ case ILCode.Stelem_R8:
+ case ILCode.Stelem_Ref:
+ return true;
+ default:
+ return false;
+ }
+ }
+
+ public static ILExpression WithILRanges(this ILExpression expr, IEnumerable<ILRange> ilranges)
+ {
+ expr.ILRanges.AddRange(ilranges);
+ return expr;
+ }
+
+ public static void RemoveTail(this List<ILNode> body, params ILCode[] codes)
+ {
+ for (int i = 0; i < codes.Length; i++) {
+ if (((ILExpression)body[body.Count - codes.Length + i]).Code != codes[i])
+ throw new Exception("Tailing code does not match expected.");
+ }
+ body.RemoveRange(body.Count - codes.Length, codes.Length);
+ }
+
+ public static V GetOrDefault<K,V>(this Dictionary<K, V> dict, K key)
+ {
+ V ret;
+ dict.TryGetValue(key, out ret);
+ return ret;
+ }
+
+ public static void RemoveOrThrow<T>(this ICollection<T> collection, T item)
+ {
+ if (!collection.Remove(item))
+ throw new Exception("The item was not found in the collection");
+ }
+
+ public static void RemoveOrThrow<K,V>(this Dictionary<K,V> collection, K key)
+ {
+ if (!collection.Remove(key))
+ throw new Exception("The key was not found in the dictionary");
+ }
+
+ public static bool ContainsReferenceTo(this ILExpression expr, ILVariable v)
+ {
+ if (expr.Operand == v)
+ return true;
+ foreach (var arg in expr.Arguments) {
+ if (ContainsReferenceTo(arg, v))
+ return true;
+ }
+ return false;
+ }
+ }
+}