mcdonald@uxe.cso.uiuc.edu (06/19/89)
>I remember a review of Microsoft's C compiler for MS-DOS that stated it >produced no-conditional-jump-abs-code. The function to convert an integer >to a positive integer was performed without a conditional jump (i.e. JS or >something). I'm very interested in this piece of code, so if someone >who does have a Microsoft C-compiler could try something like > main() > { int a,b; > a=-10; > b=abs(a); > } Here is the result of cl -c -Ox -Fa test.c, excluding the header and trailer: ; a = -10 mov WORD PTR [bp-2],-10 ;a ; b = abs(a) mov ax,-10 cwd xor ax,dx sub ax,dx mov WORD PTR [bp-4],ax ;b So your review was correct! I assume that they do this odd thing in order to not empty instruction prefetch queues???????????????? Doug McDonald
cliff@ficc.uu.net (cliff click) (06/20/89)
In article <1202@draken.nada.kth.se>, d88-eli@nada.kth.se (Erik Liljencrantz) writes: > I remember a review of Microsoft's C compiler for MS-DOS that stated it > produced no-conditional-jump-abs-code. The function to convert an integer > to a positive integer was performed without a conditional jump (i.e. JS or > something). I read an article somewhere (my apologizes to the author) of a fellow that built a "super-optimizer". It would try every combination of 68000 instructions possible, looking for the shortest sequence to do some specific function. Needless to say it was very slow. However, the fellow did find a sequence to perform an absolute value without any jumps, and several other interesting sequences. His code would find the shortest number of instructions to shift and add in order to multiple by a constant. I think he had a very short square root function out of this too. I'm pretty sure he got a "printf" function minus floating point handling in 500 bytes (he used library calls for "fputc", but he parsed, "atoi"'d and copied it all in under 500 bytes). I would be interested to here if anybody else out there has experimented with this concept of "super-optimization". Thanks -- Cliff Click, Software Contractor at Large Business: uunet.uu.net!ficc!cliff, cliff@ficc.uu.net, +1 713 274 5368 (w). Disclaimer: lost in the vortices of nilspace... +1 713 568 3460 (h).
dik@cwi.nl (Dik T. Winter) (06/20/89)
In article <225800188@uxe.cso.uiuc.edu> mcdonald@uxe.cso.uiuc.edu writes: > ; b = abs(a) ... > cwd > xor ax,dx > sub ax,dx ... > So your review was correct! I assume that they do this odd thing in > order to not empty instruction prefetch queues???????????????? > No, it is faster; just count clock cycles and compare to: jns lab neg ax lab: On many machines jumps are not cheap, so it may be better to avoid them. (There are machines where if(a >= 0 && b >= 0) is cheaper if && is not short-circuited.) -- dik t. winter, cwi, amsterdam, nederland INTERNET : dik@cwi.nl BITNET/EARN: dik@mcvax
awd@dbase.UUCP (Alastair Dallas) (06/21/89)
In article <1202@draken.nada.kth.se>, d88-eli@nada.kth.se (Erik Liljencrantz) writes: > I remember a review of Microsoft's C compiler for MS-DOS that stated it > produced no-conditional-jump-abs-code. The function to convert an integer > to a positive integer was performed without a conditional jump (i.e. JS or > something). I'm very interested in this piece of code, so if someone > who does have a Microsoft C-compiler could try something like > main() > { int a,b; > a=-10; > b=abs(a); > } > and take a close look at the assembly code generated, I would appreciate > that. This kind of reversed engineering (or what is it?) can't be illegal > as it actually was published in a magazine some time ago (maybe two years > so it must have been Microsoft C version 4.00 that was reviewed...) This code, using Microsoft C v5.1, produces: ... mov ax,FFF6 push ax call _abs() ... The abs() function uses conditional jumps. As for reverse engineering not being illegal, I think you are probably mistaken. If I were to broadcast here the code for the abs() function (which is trivial) so that people who had not bought MSC could take and use (read: steal) it, it would be wrong. On the other hand, if there were some trick code for doing this on an Intel processor, and if it were in Microsoft (or any other) C, I would bet the trick did not originate with the C vendor's compiler team. There's a difference between research and various nastier terms. /alastair/ Disclaimer: I speak for myself, only.
meissner@tiktok.dg.com (Michael Meissner) (06/27/89)
In article <1202@draken.nada.kth.se> d88-eli@nada.kth.se (Erik Liljencrantz) writes: | I remember a review of Microsoft's C compiler for MS-DOS that stated it | produced no-conditional-jump-abs-code. The function to convert an integer | to a positive integer was performed without a conditional jump (i.e. JS or | something). I'm very interested in this piece of code, so if someone | who does have a Microsoft C-compiler could try something like | main() | { int a,b; | a=-10; | b=abs(a); | } I don't know beans about what Microsoft does, but doing an absolute value without doing a just is fairly easy, if you have either an arithmetic right shift (one that propigates the sign), or an extract bit instruction that does sign extension. The trick is make a register temp that every bit is a copy of the sign bit of the value you want to take the absolute value of (ie, -1 if the number is negative, 0 if it's zero or positive). This can be done via shifting by shifting right N-1 bits (where N is the number of bits in the value, typically 16 or 32). You XOR the original value with 0/-1, if the temp is 0, the value will be the same, if the value is -1, then the original value is complemented. You finish by subtracting the temp from the result of the XOR. For example, here is the output of the GNU 88000 compiler, which I just recently had modified to use this method: file "abs3.c" ; Cc1 arguments: ; -mdelay-slot -fomit-frame-pointer -quiet -dumpbase -O -o text align 4 global _func _func: or.u r13,r0,hi16(_i2) ld r2,r13,lo16(_i2) ext r3,r2,0<31> xor r2,r2,r3 subu r2,r2,r3 or.u r13,r0,hi16(_i1) st r2,r13,lo16(_i1) jmp r1 data comm _i2,4 comm _i1,4 -- Michael Meissner, Data General. Uucp: ...!mcnc!rti!xyzzy!meissner If compiles were much Internet: meissner@dg-rtp.DG.COM faster, when would we Old Internet: meissner%dg-rtp.DG.COM@relay.cs.net have time for netnews?
ath@helios.prosys.se (Anders Thulin) (06/29/89)
In article <1202@draken.nada.kth.se> d88-eli@nada.kth.se (Erik Liljencrantz) writes: | I remember a review of Microsoft's C compiler for MS-DOS that stated it | produced no-conditional-jump-abs-code. The function to convert an integer | to a positive integer was performed without a conditional jump (i.e. JS or | something). I'm very interested in this piece of code, so if someone | who does have a Microsoft C-compiler could try something like | main() | { int a,b; | a=-10; | b=abs(a); | } I expect it would look something like: (x in d0) move.l d0,d1 add.l d1,d1 subx.l d1,d1 eor.l d1,d0 sub.l d1,d0 (abs(x) in d0) This is very likely the optimal sequence of instructions for 8086. Whether it is faster than the traditional test-jump if positive-negate I cannot judge. Copied from the article 'Superoptimizer -- A Look at the Smallest Program' by Henry Massalin, in 2nd Int. Conf. Arch. Support for Prog. Lang. and Operating Sys. (ASPLOS II) -- Anders Thulin INET : ath@prosys.se Programsystem AB UUCP : ...!{uunet,mcvax}!sunic!prosys!ath Teknikringen 2A PHONE: +46 (0)13 21 40 40 S-583 30 Linkoping, Sweden FAX : +46 (0)13 21 36 35
d88-eli@nada.kth.se (Erik Liljencrantz) (07/23/89)
I remember a review of Microsoft's C compiler for MS-DOS that stated it
produced no-conditional-jump-abs-code. The function to convert an integer
to a positive integer was performed without a conditional jump (i.e. JS or
something). I'm very interested in this piece of code, so if someone
who does have a Microsoft C-compiler could try something like
main()
{ int a,b;
a=-10;
b=abs(a);
}
and take a close look at the assembly code generated, I would appreciate
that. This kind of reversed engineering (or what is it?) can't be illegal
as it actually was published in a magazine some time ago (maybe two years
so it must have been Microsoft C version 4.00 that was reviewed...)
By the way, is there a forum for assembly language on Intel processors?
Thanks in advance,
Erik Liljencrantz
d88-eli@nada.kth.se <= Answer by mail and I'll summarize...bright@Data-IO.COM (Walter Bright) (08/03/89)
In article <1202@draken.nada.kth.se> d88-eli@nada.kth.se (Erik Liljencrantz) writes: >The function to convert an integer >to a positive integer was performed without a conditional jump (i.e. JS or >something). I'm very interested in this piece of code, This is a well-known trick: ;;;;;;;;;;;;;;;;;;;;;;;;; ; Take absolute value of integer. c_public abs func abs push BP mov BP,SP mov AX,P[BP] cwd xor AX,DX ;look, ma, no jumps! sub AX,DX pop BP ret c_endp abs