diff options
Diffstat (limited to 'ICSharpCode.Decompiler/ILAst/SimpleControlFlow.cs')
-rw-r--r-- | ICSharpCode.Decompiler/ILAst/SimpleControlFlow.cs | 376 |
1 files changed, 376 insertions, 0 deletions
diff --git a/ICSharpCode.Decompiler/ILAst/SimpleControlFlow.cs b/ICSharpCode.Decompiler/ILAst/SimpleControlFlow.cs new file mode 100644 index 00000000..d3a74a37 --- /dev/null +++ b/ICSharpCode.Decompiler/ILAst/SimpleControlFlow.cs @@ -0,0 +1,376 @@ +// 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; + +namespace ICSharpCode.Decompiler.ILAst +{ + public class SimpleControlFlow + { + Dictionary<ILLabel, int> labelGlobalRefCount = new Dictionary<ILLabel, int>(); + Dictionary<ILLabel, ILBasicBlock> labelToBasicBlock = new Dictionary<ILLabel, ILBasicBlock>(); + + DecompilerContext context; + TypeSystem typeSystem; + + public SimpleControlFlow(DecompilerContext context, ILBlock method) + { + this.context = context; + typeSystem = context.CurrentMethod.Module.TypeSystem; + + foreach(ILLabel target in method.GetSelfAndChildrenRecursive<ILExpression>(e => e.IsBranch()).SelectMany(e => e.GetBranchTargets())) { + labelGlobalRefCount[target] = labelGlobalRefCount.GetOrDefault(target) + 1; + } + foreach(ILBasicBlock bb in method.GetSelfAndChildrenRecursive<ILBasicBlock>()) { + foreach(ILLabel label in bb.GetChildren().OfType<ILLabel>()) { + labelToBasicBlock[label] = bb; + } + } + } + + public bool SimplifyTernaryOperator(List<ILNode> body, ILBasicBlock head, int pos) + { + Debug.Assert(body.Contains(head)); + + ILExpression condExpr; + ILLabel trueLabel; + ILLabel falseLabel; + ILVariable trueLocVar = null; + ILExpression trueExpr; + ILLabel trueFall; + ILVariable falseLocVar = null; + ILExpression falseExpr; + ILLabel falseFall; + object unused; + + if (head.MatchLastAndBr(ILCode.Brtrue, out trueLabel, out condExpr, out falseLabel) && + labelGlobalRefCount[trueLabel] == 1 && + labelGlobalRefCount[falseLabel] == 1 && + ((labelToBasicBlock[trueLabel].MatchSingleAndBr(ILCode.Stloc, out trueLocVar, out trueExpr, out trueFall) && + labelToBasicBlock[falseLabel].MatchSingleAndBr(ILCode.Stloc, out falseLocVar, out falseExpr, out falseFall) && + trueLocVar == falseLocVar && trueFall == falseFall) || + (labelToBasicBlock[trueLabel].MatchSingle(ILCode.Ret, out unused, out trueExpr) && + labelToBasicBlock[falseLabel].MatchSingle(ILCode.Ret, out unused, out falseExpr))) && + body.Contains(labelToBasicBlock[trueLabel]) && + body.Contains(labelToBasicBlock[falseLabel]) + ) + { + bool isStloc = trueLocVar != null; + ILCode opCode = isStloc ? ILCode.Stloc : ILCode.Ret; + TypeReference retType = isStloc ? trueLocVar.Type : context.CurrentMethod.ReturnType; + bool retTypeIsBoolean = TypeAnalysis.IsBoolean(retType); + int leftBoolVal; + int rightBoolVal; + ILExpression newExpr; + // a ? true:false is equivalent to a + // a ? false:true is equivalent to !a + // a ? true : b is equivalent to a || b + // a ? b : true is equivalent to !a || b + // a ? b : false is equivalent to a && b + // a ? false : b is equivalent to !a && b + if (retTypeIsBoolean && + trueExpr.Match(ILCode.Ldc_I4, out leftBoolVal) && + falseExpr.Match(ILCode.Ldc_I4, out rightBoolVal) && + ((leftBoolVal != 0 && rightBoolVal == 0) || (leftBoolVal == 0 && rightBoolVal != 0)) + ) + { + // It can be expressed as trivilal expression + if (leftBoolVal != 0) { + newExpr = condExpr; + } else { + newExpr = new ILExpression(ILCode.LogicNot, null, condExpr) { InferredType = typeSystem.Boolean }; + } + } else if ((retTypeIsBoolean || TypeAnalysis.IsBoolean(falseExpr.InferredType)) && trueExpr.Match(ILCode.Ldc_I4, out leftBoolVal) && (leftBoolVal == 0 || leftBoolVal == 1)) { + // It can be expressed as logical expression + if (leftBoolVal != 0) { + newExpr = MakeLeftAssociativeShortCircuit(ILCode.LogicOr, condExpr, falseExpr); + } else { + newExpr = MakeLeftAssociativeShortCircuit(ILCode.LogicAnd, new ILExpression(ILCode.LogicNot, null, condExpr), falseExpr); + } + } else if ((retTypeIsBoolean || TypeAnalysis.IsBoolean(trueExpr.InferredType)) && falseExpr.Match(ILCode.Ldc_I4, out rightBoolVal) && (rightBoolVal == 0 || rightBoolVal == 1)) { + // It can be expressed as logical expression + if (rightBoolVal != 0) { + newExpr = MakeLeftAssociativeShortCircuit(ILCode.LogicOr, new ILExpression(ILCode.LogicNot, null, condExpr), trueExpr); + } else { + newExpr = MakeLeftAssociativeShortCircuit(ILCode.LogicAnd, condExpr, trueExpr); + } + } else { + // Ternary operator tends to create long complicated return statements + if (opCode == ILCode.Ret) + return false; + + // Only simplify generated variables + if (opCode == ILCode.Stloc && !trueLocVar.IsGenerated) + return false; + + // Create ternary expression + newExpr = new ILExpression(ILCode.TernaryOp, null, condExpr, trueExpr, falseExpr); + } + + head.Body.RemoveTail(ILCode.Brtrue, ILCode.Br); + head.Body.Add(new ILExpression(opCode, trueLocVar, newExpr)); + if (isStloc) + head.Body.Add(new ILExpression(ILCode.Br, trueFall)); + + // Remove the old basic blocks + body.RemoveOrThrow(labelToBasicBlock[trueLabel]); + body.RemoveOrThrow(labelToBasicBlock[falseLabel]); + + return true; + } + return false; + } + + public bool SimplifyNullCoalescing(List<ILNode> body, ILBasicBlock head, int pos) + { + // ... + // v = ldloc(leftVar) + // brtrue(endBBLabel, ldloc(leftVar)) + // br(rightBBLabel) + // + // rightBBLabel: + // v = rightExpr + // br(endBBLabel) + // ... + // => + // ... + // v = NullCoalescing(ldloc(leftVar), rightExpr) + // br(endBBLabel) + + ILVariable v, v2; + ILExpression leftExpr, leftExpr2; + ILVariable leftVar; + ILLabel endBBLabel, endBBLabel2; + ILLabel rightBBLabel; + ILBasicBlock rightBB; + ILExpression rightExpr; + if (head.Body.Count >= 3 && + head.Body[head.Body.Count - 3].Match(ILCode.Stloc, out v, out leftExpr) && + leftExpr.Match(ILCode.Ldloc, out leftVar) && + head.MatchLastAndBr(ILCode.Brtrue, out endBBLabel, out leftExpr2, out rightBBLabel) && + leftExpr2.MatchLdloc(leftVar) && + labelToBasicBlock.TryGetValue(rightBBLabel, out rightBB) && + rightBB.MatchSingleAndBr(ILCode.Stloc, out v2, out rightExpr, out endBBLabel2) && + v == v2 && + endBBLabel == endBBLabel2 && + labelGlobalRefCount.GetOrDefault(rightBBLabel) == 1 && + body.Contains(rightBB) + ) + { + head.Body.RemoveTail(ILCode.Stloc, ILCode.Brtrue, ILCode.Br); + head.Body.Add(new ILExpression(ILCode.Stloc, v, new ILExpression(ILCode.NullCoalescing, null, leftExpr, rightExpr))); + head.Body.Add(new ILExpression(ILCode.Br, endBBLabel)); + + body.RemoveOrThrow(labelToBasicBlock[rightBBLabel]); + return true; + } + return false; + } + + public bool SimplifyShortCircuit(List<ILNode> body, ILBasicBlock head, int pos) + { + Debug.Assert(body.Contains(head)); + + ILExpression condExpr; + ILLabel trueLabel; + ILLabel falseLabel; + if(head.MatchLastAndBr(ILCode.Brtrue, out trueLabel, out condExpr, out falseLabel)) { + for (int pass = 0; pass < 2; pass++) { + + // On the second pass, swap labels and negate expression of the first branch + // It is slightly ugly, but much better then copy-pasting this whole block + ILLabel nextLabel = (pass == 0) ? trueLabel : falseLabel; + ILLabel otherLablel = (pass == 0) ? falseLabel : trueLabel; + bool negate = (pass == 1); + + ILBasicBlock nextBasicBlock = labelToBasicBlock[nextLabel]; + ILExpression nextCondExpr; + ILLabel nextTrueLablel; + ILLabel nextFalseLabel; + if (body.Contains(nextBasicBlock) && + nextBasicBlock != head && + labelGlobalRefCount[(ILLabel)nextBasicBlock.Body.First()] == 1 && + nextBasicBlock.MatchSingleAndBr(ILCode.Brtrue, out nextTrueLablel, out nextCondExpr, out nextFalseLabel) && + (otherLablel == nextFalseLabel || otherLablel == nextTrueLablel)) + { + // Create short cicuit branch + ILExpression logicExpr; + if (otherLablel == nextFalseLabel) { + logicExpr = MakeLeftAssociativeShortCircuit(ILCode.LogicAnd, negate ? new ILExpression(ILCode.LogicNot, null, condExpr) : condExpr, nextCondExpr); + } else { + logicExpr = MakeLeftAssociativeShortCircuit(ILCode.LogicOr, negate ? condExpr : new ILExpression(ILCode.LogicNot, null, condExpr), nextCondExpr); + } + head.Body.RemoveTail(ILCode.Brtrue, ILCode.Br); + head.Body.Add(new ILExpression(ILCode.Brtrue, nextTrueLablel, logicExpr)); + head.Body.Add(new ILExpression(ILCode.Br, nextFalseLabel)); + + // Remove the inlined branch from scope + body.RemoveOrThrow(nextBasicBlock); + + return true; + } + } + } + return false; + } + + public bool SimplifyCustomShortCircuit(List<ILNode> body, ILBasicBlock head, int pos) + { + Debug.Assert(body.Contains(head)); + + // --- looking for the following pattern --- + // stloc(targetVar, leftVar) + // brtrue(exitLabel, call(op_False, leftVar) + // br(followingBlock) + // + // FollowingBlock: + // stloc(targetVar, call(op_BitwiseAnd, leftVar, rightExpression)) + // br(exitLabel) + // --- + + if (head.Body.Count < 3) + return false; + + // looking for: + // stloc(targetVar, leftVar) + ILVariable targetVar; + ILExpression targetVarInitExpr; + if (!head.Body[head.Body.Count - 3].Match(ILCode.Stloc, out targetVar, out targetVarInitExpr)) + return false; + + ILVariable leftVar; + if (!targetVarInitExpr.Match(ILCode.Ldloc, out leftVar)) + return false; + + // looking for: + // brtrue(exitLabel, call(op_False, leftVar) + // br(followingBlock) + ILExpression callExpr; + ILLabel exitLabel; + ILLabel followingBlock; + if(!head.MatchLastAndBr(ILCode.Brtrue, out exitLabel, out callExpr, out followingBlock)) + return false; + + if (labelGlobalRefCount[followingBlock] > 1) + return false; + + MethodReference opFalse; + ILExpression opFalseArg; + if (!callExpr.Match(ILCode.Call, out opFalse, out opFalseArg)) + return false; + + // ignore operators other than op_False and op_True + if (opFalse.Name != "op_False" && opFalse.Name != "op_True") + return false; + + if (!opFalseArg.MatchLdloc(leftVar)) + return false; + + ILBasicBlock followingBasicBlock = labelToBasicBlock[followingBlock]; + + // FollowingBlock: + // stloc(targetVar, call(op_BitwiseAnd, leftVar, rightExpression)) + // br(exitLabel) + ILVariable _targetVar; + ILExpression opBitwiseCallExpr; + ILLabel _exitLabel; + if (!followingBasicBlock.MatchSingleAndBr(ILCode.Stloc, out _targetVar, out opBitwiseCallExpr, out _exitLabel)) + return false; + + if (_targetVar != targetVar || exitLabel != _exitLabel) + return false; + + MethodReference opBitwise; + ILExpression leftVarExpression; + ILExpression rightExpression; + if (!opBitwiseCallExpr.Match(ILCode.Call, out opBitwise, out leftVarExpression, out rightExpression)) + return false; + + if (!leftVarExpression.MatchLdloc(leftVar)) + return false; + + // ignore operators other than op_BitwiseAnd and op_BitwiseOr + if (opBitwise.Name != "op_BitwiseAnd" && opBitwise.Name != "op_BitwiseOr") + return false; + + // insert: + // stloc(targetVar, LogicAnd(C::op_BitwiseAnd, leftVar, rightExpression) + // br(exitLabel) + ILCode op = opBitwise.Name == "op_BitwiseAnd" ? ILCode.LogicAnd : ILCode.LogicOr; + + if (op == ILCode.LogicAnd && opFalse.Name != "op_False") + return false; + + if (op == ILCode.LogicOr && opFalse.Name != "op_True") + return false; + + ILExpression shortCircuitExpr = MakeLeftAssociativeShortCircuit(op, opFalseArg, rightExpression); + shortCircuitExpr.Operand = opBitwise; + + head.Body.RemoveTail(ILCode.Stloc, ILCode.Brtrue, ILCode.Br); + head.Body.Add(new ILExpression(ILCode.Stloc, targetVar, shortCircuitExpr)); + head.Body.Add(new ILExpression(ILCode.Br, exitLabel)); + body.Remove(followingBasicBlock); + + return true; + } + + ILExpression MakeLeftAssociativeShortCircuit(ILCode code, ILExpression left, ILExpression right) + { + // Assuming that the inputs are already left associative + if (right.Match(code)) { + // Find the leftmost logical expression + ILExpression current = right; + while(current.Arguments[0].Match(code)) + current = current.Arguments[0]; + current.Arguments[0] = new ILExpression(code, null, left, current.Arguments[0]) { InferredType = typeSystem.Boolean }; + return right; + } else { + return new ILExpression(code, null, left, right) { InferredType = typeSystem.Boolean }; + } + } + + public bool JoinBasicBlocks(List<ILNode> body, ILBasicBlock head, int pos) + { + ILLabel nextLabel; + ILBasicBlock nextBB; + if (!head.Body.ElementAtOrDefault(head.Body.Count - 2).IsConditionalControlFlow() && + head.Body.Last().Match(ILCode.Br, out nextLabel) && + labelGlobalRefCount[nextLabel] == 1 && + labelToBasicBlock.TryGetValue(nextLabel, out nextBB) && + body.Contains(nextBB) && + nextBB.Body.First() == nextLabel && + !nextBB.Body.OfType<ILTryCatchBlock>().Any() + ) + { + head.Body.RemoveTail(ILCode.Br); + nextBB.Body.RemoveAt(0); // Remove label + head.Body.AddRange(nextBB.Body); + + body.RemoveOrThrow(nextBB); + return true; + } + return false; + } + } +} |