Author Topic: Tail Call Elimination  (Read 4537 times)

habran

  • Member
  • *****
  • Posts: 1225
    • uasm
Tail Call Elimination
« on: July 10, 2014, 04:12:35 PM »
Some functions in x64 can be finished with JMP instead of RET
that would eliminate the overhead of setting up the stack frame
however, we have to be careful when doing it and check what assembler produced

Here is one example:
this is writen as a normal function


Code: [Select]
DoFileNew PROC FRAME
 .if (nMDI)
   invoke CreateFrameWindow,0
 .else
   invoke CloseDocument,0
 .endif
 ret
DoFileNew ENDP
JWasm produces this code:
Code: [Select]
DoFileNew PROC FRAME
000000013F4C6373 48 83 EC 28          sub         rsp,28h ;allocate a shadow space (20h) + alignment (8)
 .if (nMDI)
000000013F4C6377 83 3D 86 7C 07 00 00 cmp         dword ptr [nMDI (013F53E004h)],0 
000000013F4C637E 74 0E                je          DoFileNew+1Bh (013F4C638Eh) 
   invoke CreateFrameWindow,0
000000013F4C6380 48 C7 C1 00 00 00 00 mov         rcx,0 
000000013F4C6387 E8 4D EE FF FF       call        CreateFrameWindow (013F4C51D9h) 
 .else
000000013F4C638C EB 0A                jmp         DoFileNew+25h (013F4C6398h) 
   invoke CloseDocument,0
000000013F4C638E B9 00 00 00 00       mov         ecx,0 
000000013F4C6393 E8 26 FF FF FF       call        CloseDocument (013F4C62BEh) 
 .endif
 ret
000000013F4C6398 48 83 C4 28          add         rsp,28h 
000000013F4C639C C3                   ret 
DoFileNew ENDP

if we change INVOKE to JMP :
Code: [Select]
DoFileNew PROC FRAME
 xor ecx,ecx
 .if (nMDI)
   jmp CreateFrameWindow
 .else
   jmp CloseDocument
 .endif
DoFileNew ENDP
which eliminate overhead and reduces number of bytes
Code: [Select]
DoFileNew PROC FRAME
 xor ecx,ecx
000000013FC86373 33 C9                xor         ecx,ecx 
 .if (nMDI)
000000013FC86375 83 3D 88 6C 07 00 00 cmp         dword ptr [nMDI (013FCFD004h)],0 
000000013FC8637C 74 07                je          DoFileNew+12h (013FC86385h) 
   jmp CreateFrameWindow
000000013FC8637E E9 56 EE FF FF       jmp         CreateFrameWindow (013FC851D9h) 
 .else
000000013FC86383 EB 05                jmp         EnumThreadWindowsProc (013FC8638Ah) ;this will never happen
   jmp CloseDocument                                      ;but produces 2 unnecessary byte more
000000013FC86385 E9 34 FF FF FF       jmp         CloseDocument (013FC862BEh) 
 .endif
DoFileNew ENDP
;;;;;;;//--------------------------------------------------------------------------
EnumThreadWindowsProc PROC FRAME USES rbx hwnd:HWND,lParam:LPARAM
000000013FC8638A 48 89 4C 24 08       mov         qword ptr [rsp+8],rcx 
000000013FC8638F 53                   push        rbx 
000000013FC86390 48 83 EC 20          sub         rsp,20h 
to make it right we have to change the source a little bit to this:
Code: [Select]
DoFileNew PROC FRAME
 xor ecx,ecx
 .if (nMDI)
   jmp CreateFrameWindow
 .endif
 jmp CloseDocument
DoFileNew ENDP
and now we got proper code:
Code: [Select]
DoFileNew PROC FRAME
 xor ecx,ecx
000000013F456373 33 C9                xor         ecx,ecx 
 .if (nMDI)
000000013F456375 83 3D 88 6C 07 00 00 cmp         dword ptr [nMDI (013F4CD004h)],0 
000000013F45637C 74 05                je          DoFileNew+10h (013F456383h) 
   jmp CreateFrameWindow
000000013F45637E E9 56 EE FF FF       jmp         CreateFrameWindow (013F4551D9h) 
 .endif
 jmp CloseDocument
000000013F456383 E9 36 FF FF FF       jmp         CloseDocument (013F4562BEh) 
DoFileNew ENDP





Cod-Father

Gunther

  • Member
  • *****
  • Posts: 3585
  • Forgive your enemies, but never forget their names
Re: Tail Call Elimination
« Reply #1 on: July 10, 2014, 07:30:24 PM »
Hi habran,

long time not seen, now you're back.  :t

Some functions in x64 can be finished with JMP instead of RET
that would eliminate the overhead of setting up the stack frame
however, we have to be careful when doing it and check what assembler produced

Yes, that's an old trick. Thank you for the recollection. Some younger coders will find that interesting.

Gunther
Get your facts first, and then you can distort them.

habran

  • Member
  • *****
  • Posts: 1225
    • uasm
Re: Tail Call Elimination
« Reply #2 on: July 10, 2014, 07:45:49 PM »
thanks Gunther :biggrin:
I read regularly posts but I intervene only if necessary ;)

I have posted this tread because I want more people to realize the advantage of 64 bit programming

I am warning programmers when use the Tail Call Elimination to make sure that they clearly understand
what they are doing 8)   
Cod-Father

Gunther

  • Member
  • *****
  • Posts: 3585
  • Forgive your enemies, but never forget their names
Re: Tail Call Elimination
« Reply #3 on: July 11, 2014, 12:08:54 AM »
Hi habran,

I read regularly posts but I intervene only if necessary ;)

good to know.

I have posted this tread because I want more people to realize the advantage of 64 bit programming

I am warning programmers when use the Tail Call Elimination to make sure that they clearly understand
what they are doing 8)   

That's an important point.  :t

Gunther
Get your facts first, and then you can distort them.

habran

  • Member
  • *****
  • Posts: 1225
    • uasm
Re: Tail Call Elimination
« Reply #4 on: July 11, 2014, 05:49:56 AM »
Hi  Gunther
I wish I knew you personally because you must be very nice bloke
your students are the lucky one
however, when you say  'good to know' I have filling that you are teasing me :biggrin:
are you?
Cod-Father

Gunther

  • Member
  • *****
  • Posts: 3585
  • Forgive your enemies, but never forget their names
Re: Tail Call Elimination
« Reply #5 on: July 11, 2014, 08:05:22 AM »
however, when you say  'good to know' I have filling that you are teasing me :biggrin:
are you?

Definitely not. It comes from the heart.

Gunther
Get your facts first, and then you can distort them.

habran

  • Member
  • *****
  • Posts: 1225
    • uasm
Re: Tail Call Elimination
« Reply #6 on: July 11, 2014, 09:19:04 AM »
good to know :bgrin:
Cod-Father

Gunther

  • Member
  • *****
  • Posts: 3585
  • Forgive your enemies, but never forget their names
Re: Tail Call Elimination
« Reply #7 on: July 11, 2014, 08:05:24 PM »
Hi habran,

on the other hand, we've in 64-bit Windows a parameter passing on a register basis. That makes things faster and sometimes a stack frame isn't necessary.

Gunther
Get your facts first, and then you can distort them.

habran

  • Member
  • *****
  • Posts: 1225
    • uasm
Re: Tail Call Elimination
« Reply #8 on: July 11, 2014, 11:24:41 PM »
Certanly :biggrin:
Cod-Father