Jb Evain wrote:
> Hey Daniel,
>
> On 10/18/07, Jb Evain <[EMAIL PROTECTED]> wrote:
>
>> Thanks for the test case, queuing that!
>>
>
> That should be fixed in SVN.
>
> But tell me, how did you manage to get such code?
>
>
I had read the CLI specification on the evaluation stack because I had
to track it on my own for another optimization I was implementing (to
know which variable gets copied where).
To check how my optimizer works, I disassembled both the non-optimized
and the optimized assembly and looked at the diff between the files.
There I was seeing that Cecil nearly always overestimated .maxstack, so
I took a look at the implementation and saw that it didn't handle
branches like my variable tracking implementation had to. Then I created
that test case manually to show that Cecil's calculation is not correct.
I just patched Cecil to calculate .maxstack exactly (using the
GetPushDelta/GetPopDelta methods from Cecil.FlowAnalysis), the patch is
attached.
Now the stack count is reduced correctly for StackBehaviour.Varpop based
on the number of parameters the called method has.
It also "follows" branches to get my test case right, and it also works
correct on the attached new test case (there it's tricky to see that
.maxstack 1 is sufficient).
"Following" branches is limited to forward branches, because that's
sufficient according to the CLI specification:
"In order for the JIT compilers to efficiently track the data types
stored on the stack, the stack shall
normally be empty at the instruction following an unconditional control
transfer instruction (br,
br.s, ret, jmp, throw, endfilter, endfault, or endfinally). The stack
shall be non-empty at such
an instruction only if at some earlier location within the method there
has been a forward branch
to that instruction. "
Note that my patch uses Debug.Assert to detect invalid IL, and might
throw a NotImplementedException if it encounters an instruction where it
cannot determine the PushDelta/PopDelta.
That said, I finally managed to use my optimizer on SharpDevelop's
ICSharpCode.NRefactory - and all unit tests still pass. (I had to fix
several optimization bugs until that was the case)
It is now capable of inlining delegate calls if the target method is
known. It also can remove dead code and unused variables. This code:
static bool Exists(IEnumerable<int> input, Predicate<int> pred)
{
if (pred == null) {
throw new ArgumentNullException("pred");
}
foreach (int i in input) {
if (pred(i))
return true;
}
return false;
}
static bool ExistsTest(int divisor)
{
return Exists(someArray, i => i % divisor == 0);
}
currently is optimized to:
internal static bool ExistsTest(int divisor)
{
<>c__DisplayClass1 class2 = new <>c__DisplayClass1();
class2.divisor = divisor;
<>c__DisplayClass1 class3 = class2;
IEnumerable<int> input = someArray;
foreach (int num in input)
{
int num2 = num;
<>c__DisplayClass1 class4 = class3;
if ((num2 % class4.divisor) == 0)
{
return true;
}
}
return false;
}
As you can see, the "throw ArgumentNullException" has been removed
because the delegate could not be null; and then the delegate was
completely removed.
Now I just need to get rid of those additional local variables
introduced by the inlining and then I can convert the captured variable
<>c__DisplayClass1.divisor back into a normal local variable.
After that <>c__DisplayClass1 is unused and should be completely removed
by the optimizer.
BTW: I'm using method.Body.Simplify() so that I do not have to deal with
short forms in the optimizer (especially since inlining might increase
the relative distance between instructions so that a br.s must be
converted into a br). However, I could not find an easy way to do the
reverse direction after the optimizer has done its work (how do I know
the distance between two instructions in bytes? Offset is not set until
I save the assembly).
Short forms can make a significant difference in assembly size, so can
we get a simply MethodBody.ToShortForms() method that automatically
takes care when short forms are valid?
Daniel
--~--~---------~--~----~------------~-------~--~----~
--
mono-cecil
-~----------~----~----~----~------~----~------~--~---
Index: CodeWriter.cs
===================================================================
--- CodeWriter.cs (revision 87802)
+++ CodeWriter.cs (working copy)
@@ -417,46 +417,145 @@
static void ComputeMaxStack (InstructionCollection instructions)
{
- InstructionCollection ehs = new InstructionCollection
(null);
+ int current = 0;
+ int max = 0;
+ Hashtable knownStackSizes = new Hashtable();
+
foreach (ExceptionHandler eh in
instructions.Container.ExceptionHandlers) {
switch (eh.Type) {
case ExceptionHandlerType.Catch :
- ehs.Add (eh.HandlerStart);
- break;
case ExceptionHandlerType.Filter :
- ehs.Add (eh.FilterStart);
+ knownStackSizes[eh.HandlerStart] = 1;
+ max = 1;
break;
}
}
- int max = 0;
foreach (Instruction instr in instructions) {
- if (ehs.Contains (instr))
- max++;
+ object savedSize = knownStackSizes[instr];
+ if (savedSize != null) {
+ // if this is not true, the IL is
invalid (maybe introduce an InvalidILException?)
+ System.Diagnostics.Debug.Assert(current
== 0 || current == (int)savedSize);
+
+ current = (int)savedSize;
+ }
+
+ current -= GetPopDelta(current, instr,
instructions.Container.Method);
+ System.Diagnostics.Debug.Assert(current >= 0);
+ current += GetPushDelta(instr);
+
+ if (current > max)
+ max = current;
+
+ // for forward branches, copy the stack size
for the instruction that is being branched to
+ switch (instr.OpCode.OperandType) {
+ case OperandType.InlineBrTarget:
+ case OperandType.ShortInlineBrTarget:
+ knownStackSizes[instr.Operand]
= current;
+ break;
+ case OperandType.InlineSwitch:
+ foreach (Instruction target in
(Instruction[])instr.Operand)
+ knownStackSizes[target]
= current;
+ break;
+ }
+
+ switch (instr.OpCode.FlowControl) {
+ case FlowControl.Branch:
+ case FlowControl.Throw:
+ case FlowControl.Return:
+ // next statement is not
reachable from this statement, so reset the stack depth to 0
+ current = 0;
+ break;
+ }
+ }
- switch (instr.OpCode.StackBehaviourPush) {
+ instructions.Container.MaxStack = max;
+ }
+
+ public static int GetPushDelta (Instruction instruction)
+ {
+ OpCode code = instruction.OpCode;
+ switch (code.StackBehaviourPush) {
+ case StackBehaviour.Push0:
+ return 0;
+
case StackBehaviour.Push1:
case StackBehaviour.Pushi:
case StackBehaviour.Pushi8:
case StackBehaviour.Pushr4:
case StackBehaviour.Pushr8:
case StackBehaviour.Pushref:
+ return 1;
+
+ case StackBehaviour.Push1_push1:
+ return 2;
+
case StackBehaviour.Varpush:
- max++;
+ if (code.FlowControl ==
FlowControl.Call) {
+ MethodReference method =
(MethodReference)instruction.Operand;
+ return IsVoid
(method.ReturnType.ReturnType)
+ ? 0
+ : 1;
+ }
break;
- case StackBehaviour.Push1_push1:
- max += 2;
+ }
+ throw new NotImplementedException();
+ }
+
+ public static int GetPopDelta (int stackHeight, Instruction
instruction, MethodDefinition currentMethod)
+ {
+ OpCode code = instruction.OpCode;
+ switch (code.StackBehaviourPop) {
+ case StackBehaviour.Pop0:
+ return 0;
+ case StackBehaviour.Popi:
+ case StackBehaviour.Popref:
+ case StackBehaviour.Pop1:
+ return 1;
+
+ case StackBehaviour.Pop1_pop1:
+ case StackBehaviour.Popi_pop1:
+ case StackBehaviour.Popi_popi:
+ case StackBehaviour.Popi_popi8:
+ case StackBehaviour.Popi_popr4:
+ case StackBehaviour.Popi_popr8:
+ case StackBehaviour.Popref_pop1:
+ case StackBehaviour.Popref_popi:
+ return 2;
+
+ case StackBehaviour.Popi_popi_popi:
+ case StackBehaviour.Popref_popi_popi:
+ case StackBehaviour.Popref_popi_popi8:
+ case StackBehaviour.Popref_popi_popr4:
+ case StackBehaviour.Popref_popi_popr8:
+ case StackBehaviour.Popref_popi_popref:
+ return 3;
+
+ case StackBehaviour.PopAll:
+ return stackHeight;
+
+ case StackBehaviour.Varpop:
+ if (code.FlowControl ==
FlowControl.Call) {
+ MethodReference method =
(MethodReference)instruction.Operand;
+ int count =
method.Parameters.Count;
+ if (method.HasThis &&
OpCodes.Newobj.Value != code.Value) {
+ ++count;
+ }
+ return count;
+ }
+ if (code.Value == OpCodes.Ret.Value) {
+ return
IsVoid(currentMethod.ReturnType.ReturnType)
+ ? 0
+ : 1;
+ }
break;
- }
-
- if (instr.OpCode.OperandType ==
OperandType.InlineMethod) {
- IMethodSignature signature =
instr.Operand as IMethodSignature;
- if (signature != null &&
signature.ReturnType.ReturnType.FullName != Constants.Void)
- max++;
- }
}
-
- instructions.Container.MaxStack = max;
+ throw new NotImplementedException();
}
+
+ static bool IsVoid (TypeReference type)
+ {
+ return type.FullName == Constants.Void;
+ }
}
}
// Metadata version: v2.0.50727
.assembly extern mscorlib
{
.publickeytoken = (B7 7A 5C 56 19 34 E0 89 ) //
.z\V.4..
.ver 2:0:0:0
}
.assembly TestApp
{
.hash algorithm 0x00008004
.ver 1:0:2847:23628
}
.module TestApp.exe
// =============== CLASS MEMBERS DECLARATION ===================
.class private auto ansi sealed beforefieldinit TestApp.Program
extends [mscorlib]System.Object
{
.method private hidebysig static void Test() cil managed noinlining
{
.entrypoint
// Code size 46 (0x2e)
.maxstack 1
.locals init (class TestApp.Program V_0)
ldc.i4.1
br label2
label1:
ldc.i4.2
pop
ret
label2:
pop
br label1
} // end of method Program::Test
} // end of class TestApp.Program
