Skip to content

Commit

Permalink
Merge pull request icsharpcode#205 - Decompilation of lifted operators
Browse files Browse the repository at this point in the history 
This decompiles the C# generated code for lifted operators back to the original short form.
This can result in a significant improvement to the readability of the resulting code in some more complex functions because C# generates 2 temporary locals for lifted operators that can now be inlined.

As a byproduct the following improvements are also included: more thorough boolean logic decompilation; various project/solution file improvements; Ldloca support for variable splitting; simplified shift operators (already in icsharpcode branch); significant performance improvement for stack analysis of variables to offset the added complexity from ldloca support; decompilation of compound assignment with overloaded operators; some type analysis refactoring.
  • Loading branch information
@dgrunwald
dgrunwald committed Sep 18, 2011
2 parents 6d22ff9 + 41e71ea commit 25237a1
Show file tree
Hide file tree
Showing 27 changed files with 1,769 additions and 156 deletions.
5 changes: 2 additions & 3 deletions AvalonEdit/ICSharpCode.AvalonEdit/ICSharpCode.AvalonEdit.csproj
View file
Original file line number Diff line number Diff line change
Expand Up @@ -33,7 +33,7 @@
<DefineConstants>DEBUG;TRACE;DOTNET4</DefineConstants>
</PropertyGroup>
<PropertyGroup Condition=" '$(Configuration)' == 'Release' ">
<DebugSymbols>false</DebugSymbols>
<DebugSymbols>true</DebugSymbols>
<DebugType>PdbOnly</DebugType>
<Optimize>True</Optimize>
<CheckForOverflowUnderflow>False</CheckForOverflowUnderflow>
Expand All @@ -42,9 +42,8 @@
<PropertyGroup Condition=" '$(Platform)' == 'AnyCPU' ">
<RegisterForComInterop>False</RegisterForComInterop>
<GenerateSerializationAssemblies>Auto</GenerateSerializationAssemblies>
<BaseAddress>4194304</BaseAddress>
<BaseAddress>452984832</BaseAddress>
<PlatformTarget>AnyCPU</PlatformTarget>
<FileAlignment>4096</FileAlignment>
</PropertyGroup>
<Import Project="$(MSBuildBinPath)\Microsoft.CSharp.Targets" />
<ItemGroup>
Expand Down
30 changes: 24 additions & 6 deletions ICSharpCode.Decompiler/Ast/AstMethodBodyBuilder.cs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -421,7 +421,13 @@ AstNode TransformByteCode(ILExpression byteCode)
case ILCode.CompoundAssignment:
{
CastExpression cast = arg1 as CastExpression;
BinaryOperatorExpression boe = (BinaryOperatorExpression)(cast != null ? cast.Expression : arg1);
var boe = cast != null ? (BinaryOperatorExpression)cast.Expression : arg1 as BinaryOperatorExpression;
// AssignmentExpression doesn't support overloaded operators so they have to be processed to BinaryOperatorExpression
if (boe == null) {
var tmp = new ParenthesizedExpression(arg1);
ReplaceMethodCallsWithOperators.ProcessInvocationExpression((InvocationExpression)arg1);
boe = (BinaryOperatorExpression)tmp.Expression;
}
var assignment = new Ast.AssignmentExpression {
Left = boe.Left.Detach(),
Operator = ReplaceMethodCallsWithOperators.GetAssignmentOperatorForBinaryOperator(boe.Operator),
Expand All @@ -440,17 +446,25 @@ AstNode TransformByteCode(ILExpression byteCode)
#endregion
#region Comparison
case ILCode.Ceq: return new Ast.BinaryOperatorExpression(arg1, BinaryOperatorType.Equality, arg2);
case ILCode.Cne: return new Ast.BinaryOperatorExpression(arg1, BinaryOperatorType.InEquality, arg2);
case ILCode.Cgt: return new Ast.BinaryOperatorExpression(arg1, BinaryOperatorType.GreaterThan, arg2);
case ILCode.Cgt_Un: {
// can also mean Inequality, when used with object references
TypeReference arg1Type = byteCode.Arguments[0].InferredType;
if (arg1Type != null && !arg1Type.IsValueType)
return new Ast.BinaryOperatorExpression(arg1, BinaryOperatorType.InEquality, arg2);
else
return new Ast.BinaryOperatorExpression(arg1, BinaryOperatorType.GreaterThan, arg2);
if (arg1Type != null && !arg1Type.IsValueType) goto case ILCode.Cne;
goto case ILCode.Cgt;
}
case ILCode.Cle_Un: {
// can also mean Equality, when used with object references
TypeReference arg1Type = byteCode.Arguments[0].InferredType;
if (arg1Type != null && !arg1Type.IsValueType) goto case ILCode.Ceq;
goto case ILCode.Cle;
}
case ILCode.Cle: return new Ast.BinaryOperatorExpression(arg1, BinaryOperatorType.LessThanOrEqual, arg2);
case ILCode.Cge_Un:
case ILCode.Cge: return new Ast.BinaryOperatorExpression(arg1, BinaryOperatorType.GreaterThanOrEqual, arg2);
case ILCode.Clt_Un:
case ILCode.Clt: return new Ast.BinaryOperatorExpression(arg1, BinaryOperatorType.LessThan, arg2);
case ILCode.Clt_Un: return new Ast.BinaryOperatorExpression(arg1, BinaryOperatorType.LessThan, arg2);
#endregion
#region Logical
case ILCode.LogicNot: return new Ast.UnaryOperatorExpression(UnaryOperatorType.Not, arg1);
Expand Down Expand Up @@ -792,8 +806,12 @@ AstNode TransformByteCode(ILExpression byteCode)
}
case ILCode.InitializedObject:
return new InitializedObjectExpression();
case ILCode.Wrap:
return arg1.WithAnnotation(PushNegation.LiftedOperatorAnnotation);
case ILCode.AddressOf:
return MakeRef(arg1);
case ILCode.NullableOf:
case ILCode.ValueOf: return arg1;
default:
throw new Exception("Unknown OpCode: " + byteCode.Code);
}
Expand Down
4 changes: 4 additions & 0 deletions ICSharpCode.Decompiler/Ast/NameVariables.cs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -175,6 +175,10 @@ string GenerateNameForVariable(ILVariable variable, ILBlock methodBody)
case ILCode.Clt_Un:
case ILCode.Cgt:
case ILCode.Cgt_Un:
case ILCode.Cle:
case ILCode.Cle_Un:
case ILCode.Cge:
case ILCode.Cge_Un:
ILVariable loadVar;
if (expr.Arguments[0].Match(ILCode.Ldloc, out loadVar) && loadVar == variable) {
isLoopCounter = true;
Expand Down
14 changes: 14 additions & 0 deletions ICSharpCode.Decompiler/Ast/Transforms/PushNegation.cs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -26,8 +26,18 @@ namespace ICSharpCode.Decompiler.Ast.Transforms
{
public class PushNegation: DepthFirstAstVisitor<object, object>, IAstTransform
{
sealed class LiftedOperator { }
/// <summary>
/// Annotation for lifted operators that cannot be transformed by PushNegation
/// </summary>
public static readonly object LiftedOperatorAnnotation = new LiftedOperator();

public override object VisitUnaryOperatorExpression(UnaryOperatorExpression unary, object data)
{
// lifted operators can't be transformed
if (unary.Annotation<LiftedOperator>() != null || unary.Expression.Annotation<LiftedOperator>() != null)
return base.VisitUnaryOperatorExpression(unary, data);

// Remove double negation
// !!a
if (unary.Operator == UnaryOperatorType.Not &&
Expand Down Expand Up @@ -108,6 +118,10 @@ unary.Expression is UnaryOperatorExpression &&

public override object VisitBinaryOperatorExpression(BinaryOperatorExpression binaryOperatorExpression, object data)
{
// lifted operators can't be transformed
if (binaryOperatorExpression.Annotation<LiftedOperator>() != null)
return base.VisitBinaryOperatorExpression(binaryOperatorExpression, data);

BinaryOperatorType op = binaryOperatorExpression.Operator;
bool? rightOperand = null;
if (binaryOperatorExpression.Right is PrimitiveExpression)
Expand Down
11 changes: 8 additions & 3 deletions ICSharpCode.Decompiler/Ast/Transforms/ReplaceMethodCallsWithOperators.cs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -51,6 +51,11 @@ public override object VisitInvocationExpression(InvocationExpression invocation
{
base.VisitInvocationExpression(invocationExpression, data);

return ProcessInvocationExpression(invocationExpression);
}

internal static object ProcessInvocationExpression(InvocationExpression invocationExpression)
{
MethodReference methodRef = invocationExpression.Annotation<MethodReference>();
if (methodRef == null)
return null;
Expand Down Expand Up @@ -115,7 +120,7 @@ public override object VisitInvocationExpression(InvocationExpression invocation
return null;
}

BinaryOperatorType? GetBinaryOperatorTypeFromMetadataName(string name)
static BinaryOperatorType? GetBinaryOperatorTypeFromMetadataName(string name)
{
switch (name) {
case "op_Addition":
Expand All @@ -132,7 +137,7 @@ public override object VisitInvocationExpression(InvocationExpression invocation
return BinaryOperatorType.BitwiseAnd;
case "op_BitwiseOr":
return BinaryOperatorType.BitwiseOr;
case "op_ExlusiveOr":
case "op_ExclusiveOr":
return BinaryOperatorType.ExclusiveOr;
case "op_LeftShift":
return BinaryOperatorType.ShiftLeft;
Expand All @@ -155,7 +160,7 @@ public override object VisitInvocationExpression(InvocationExpression invocation
}
}

UnaryOperatorType? GetUnaryOperatorTypeFromMetadataName(string name)
static UnaryOperatorType? GetUnaryOperatorTypeFromMetadataName(string name)
{
switch (name) {
case "op_LogicalNot":
Expand Down
8 changes: 4 additions & 4 deletions ICSharpCode.Decompiler/ICSharpCode.Decompiler.csproj
View file
Original file line number Diff line number Diff line change
Expand Up @@ -19,8 +19,7 @@
<PlatformTarget>AnyCPU</PlatformTarget>
<RegisterForComInterop>False</RegisterForComInterop>
<GenerateSerializationAssemblies>Auto</GenerateSerializationAssemblies>
<BaseAddress>4194304</BaseAddress>
<FileAlignment>4096</FileAlignment>
<BaseAddress>448462848</BaseAddress>
</PropertyGroup>
<PropertyGroup Condition=" '$(Configuration)' == 'Debug' ">
<OutputPath>bin\Debug\</OutputPath>
Expand All @@ -32,8 +31,8 @@
</PropertyGroup>
<PropertyGroup Condition=" '$(Configuration)' == 'Release' ">
<OutputPath>bin\Release\</OutputPath>
<DebugSymbols>False</DebugSymbols>
<DebugType>None</DebugType>
<DebugSymbols>true</DebugSymbols>
<DebugType>PdbOnly</DebugType>
<Optimize>True</Optimize>
<CheckForOverflowUnderflow>False</CheckForOverflowUnderflow>
<DefineConstants>TRACE</DefineConstants>
Expand Down Expand Up @@ -96,6 +95,7 @@
<Compile Include="FlowAnalysis\SsaOptimization.cs" />
<Compile Include="FlowAnalysis\SsaVariable.cs" />
<Compile Include="FlowAnalysis\TransformToSsa.cs" />
<Compile Include="ILAst\LiftedOperators.cs" />
<Compile Include="ILAst\InitializerPeepholeTransforms.cs" />
<Compile Include="ILAst\DefaultDictionary.cs" />
<Compile Include="ILAst\GotoRemoval.cs" />
Expand Down
50 changes: 40 additions & 10 deletions ICSharpCode.Decompiler/ILAst/ILAstBuilder.cs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -339,9 +339,10 @@ List<ByteCode> StackAnalysis(MethodDefinition methodDef)

// Calculate new variable state
VariableSlot[] newVariableState = VariableSlot.CloneVariableState(byteCode.VariablesBefore);
if (byteCode.Code == ILCode.Stloc) {
if (byteCode.Code == ILCode.Stloc || byteCode.Code == ILCode.Ldloca) {
int varIndex = ((VariableReference)byteCode.Operand).Index;
newVariableState[varIndex] = new VariableSlot(byteCode);
newVariableState[varIndex] = byteCode.Code == ILCode.Stloc || byteCode.Next.Code == ILCode.Initobj ?
new VariableSlot(byteCode) : new VariableSlot(newVariableState[varIndex].StoredBy.Union(byteCode), false);
}

// After the leave, finally block might have touched the variables
Expand Down Expand Up @@ -523,17 +524,20 @@ void ConvertLocalVariables(List<ByteCode> body)

for(int variableIndex = 0; variableIndex < varCount; variableIndex++) {
// Find all stores and loads for this variable
List<ByteCode> stores = body.Where(b => b.Code == ILCode.Stloc && b.Operand is VariableDefinition && b.OperandAsVariable.Index == variableIndex).ToList();
List<ByteCode> loads = body.Where(b => (b.Code == ILCode.Ldloc || b.Code == ILCode.Ldloca) && b.Operand is VariableDefinition && b.OperandAsVariable.Index == variableIndex).ToList();
var stores = body.Where(b => (b.Code == ILCode.Stloc || b.Code == ILCode.Ldloca) && b.Operand is VariableDefinition && b.OperandAsVariable.Index == variableIndex).ToList();
// ldloca on an uninitialized variable or followed by initobj isn't considered a load
var loads = body.Where(b =>
(b.Code == ILCode.Ldloc || (b.Code == ILCode.Ldloca && b.Next.Code != ILCode.Initobj &&
(b.VariablesBefore[variableIndex].StoredBy.Length != 0 || b.VariablesBefore[variableIndex].StoredByAll)))
&& b.Operand is VariableDefinition && b.OperandAsVariable.Index == variableIndex).ToList();
TypeReference varType = methodDef.Body.Variables[variableIndex].VariableType;

List<VariableInfo> newVars;

bool isPinned = methodDef.Body.Variables[variableIndex].IsPinned;
// If the variable is pinned, use single variable.
// If any of the loads is from "all", use single variable
// If any of the loads is ldloca, fallback to single variable as well
if (isPinned || loads.Any(b => b.VariablesBefore[variableIndex].StoredByAll || b.Code == ILCode.Ldloca)) {
if (isPinned || loads.Any(b => b.VariablesBefore[variableIndex].StoredByAll)) {
newVars = new List<VariableInfo>(1) { new VariableInfo() {
Variable = new ILVariable() {
Name = "var_" + variableIndex,
Expand All @@ -545,7 +549,12 @@ void ConvertLocalVariables(List<ByteCode> body)
}};
} else {
// Create a new variable for each store
newVars = stores.Select(st => new VariableInfo() {
newVars = stores.Where(st =>
{
if (st.Code == ILCode.Stloc || st.Next.Code == ILCode.Initobj) return true;
var storedBy = st.VariablesBefore[variableIndex].StoredBy;
return storedBy.Length == 0 || storedBy[0] == st;
}).Select(st => new VariableInfo() {
Variable = new ILVariable() {
Name = "var_" + variableIndex + "_" + st.Offset.ToString("X2"),
Type = varType,
Expand Down Expand Up @@ -582,14 +591,16 @@ void ConvertLocalVariables(List<ByteCode> body)
} else if (storedBy.Length == 1) {
VariableInfo newVar = newVars.Single(v => v.Stores.Contains(storedBy[0]));
newVar.Loads.Add(load);
if (load.Code == ILCode.Ldloca) newVar.Stores.Add(load);
} else {
List<VariableInfo> mergeVars = newVars.Where(v => v.Stores.Union(storedBy).Any()).ToList();
List<VariableInfo> mergeVars = newVars.Where(v => v.Stores.Intersect(storedBy).Any()).ToList();
VariableInfo mergedVar = new VariableInfo() {
Variable = mergeVars[0].Variable,
Stores = mergeVars.SelectMany(v => v.Stores).ToList(),
Loads = mergeVars.SelectMany(v => v.Loads).ToList()
};
mergedVar.Loads.Add(load);
if (load.Code == ILCode.Ldloca) mergedVar.Stores.Add(load);
newVars = newVars.Except(mergeVars).ToList();
newVars.Add(mergedVar);
}
Expand Down Expand Up @@ -819,15 +830,34 @@ public static List<T> CutRange<T>(this List<T> list, int start, int count)
list.RemoveRange(start, count);
return ret;
}

public static T[] Union<T>(this T[] a, T b)
{
if (a.Length == 0)
return new[] { b };
if (Array.IndexOf(a, b) >= 0)
return a;
var res = new T[a.Length + 1];
Array.Copy(a, res, a.Length);
res[res.Length - 1] = b;
return res;
}

public static T[] Union<T>(this T[] a, T[] b)
{
if (a == b)
return a;
if (a.Length == 0)
return b;
if (b.Length == 0)
return a;
if (a.Length == 1 && b.Length == 1 && a[0].Equals(b[0]))
return a;
if (a.Length == 1) {
if (b.Length == 1)
return a[0].Equals(b[0]) ? a : new[] { a[0], b[0] };
return b.Union(a[0]);
}
if (b.Length == 1)
return a.Union(b[0]);
return Enumerable.Union(a, b).ToArray();
}
}
Expand Down
36 changes: 24 additions & 12 deletions ICSharpCode.Decompiler/ILAst/ILAstOptimizer.cs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -42,10 +42,12 @@ public enum ILAstOptimizationStep
SimplifyTernaryOperator,
SimplifyNullCoalescing,
JoinBasicBlocks,
SimplifyLogicNot,
SimplifyShiftOperators,
TransformDecimalCtorToConstant,
SimplifyLdObjAndStObj,
SimplifyCustomShortCircuit,
SimplifyLiftedOperators,
TransformArrayInitializers,
TransformMultidimensionalArrayInitializers,
TransformObjectInitializers,
Expand Down Expand Up @@ -134,6 +136,9 @@ public void Optimize(DecompilerContext context, ILBlock method, ILAstOptimizatio
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);

Expand All @@ -146,6 +151,9 @@ public void Optimize(DecompilerContext context, ILBlock method, ILAstOptimizatio

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);
Expand Down Expand Up @@ -307,27 +315,30 @@ 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: block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, new ILExpression(ILCode.LogicNot, null, expr.Arguments.Single())); break;
case ILCode.__Beq: block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, new ILExpression(ILCode.Ceq, null, expr.Arguments)); break;
case ILCode.__Bne_Un: block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, new ILExpression(ILCode.LogicNot, null, new ILExpression(ILCode.Ceq, null, expr.Arguments))); break;
case ILCode.__Bgt: block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, new ILExpression(ILCode.Cgt, null, expr.Arguments)); break;
case ILCode.__Bgt_Un: block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, new ILExpression(ILCode.Cgt_Un, null, expr.Arguments)); break;
case ILCode.__Ble: block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, new ILExpression(ILCode.LogicNot, null, new ILExpression(ILCode.Cgt, null, expr.Arguments))); break;
case ILCode.__Ble_Un: block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, new ILExpression(ILCode.LogicNot, null, new ILExpression(ILCode.Cgt_Un, null, expr.Arguments))); break;
case ILCode.__Blt: block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, new ILExpression(ILCode.Clt, null, expr.Arguments)); break;
case ILCode.__Blt_Un: block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, new ILExpression(ILCode.Clt_Un, null, expr.Arguments)); break;
case ILCode.__Bge: block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, new ILExpression(ILCode.LogicNot, null, new ILExpression(ILCode.Clt, null, expr.Arguments))); break;
case ILCode.__Bge_Un: block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, new ILExpression(ILCode.LogicNot, null, new ILExpression(ILCode.Clt_Un, null, expr.Arguments))); break;
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;
}
((ILExpression)block.Body[i]).Arguments.Single().ILRanges.AddRange(expr.ILRanges);
var newExpr = new ILExpression(op, null, expr.Arguments);
block.Body[i] = new ILExpression(ILCode.Brtrue, expr.Operand, newExpr);
newExpr.ILRanges = expr.ILRanges;
}
}
}
Expand Down Expand Up @@ -721,6 +732,7 @@ public static bool HasNoSideEffects(this ILExpression expr)
case ILCode.Ldc_I8:
case ILCode.Ldc_R4:
case ILCode.Ldc_R8:
case ILCode.Ldc_Decimal:
return true;
default:
return false;
Expand Down
Loading

0 comments on commit 25237a1

Please sign in to comment.