doug@terak.UUCP (Doug Pardee) (08/30/85)
> ... since comparison is merely done by subtraction (a > compare instruction is usually just a subtract instruction that doesn't > store the result anywhere)... Compiler writers note -- a comparison is not "just a subtract". For example: #define NBITS 16 /* NBITS is number of bits in an integer */ int a, b; a = 3 << (NBITS-3); /* 24576 for NBITS=16 */ b = -a; if (a>b) printf("Comparison was done by bit-wise comparison\n"); else printf("Comparison was done by subtraction\n"); /* WRONG */ Compiler users note -- if your compiler gives the wrong results, the compiler writer might not be completely at fault. Many early CPU chips (8080A, Z80, 6502, etc.) did comparison by subtraction, and a compiler would have had to generate extra code to test for Overflow in order to get the correct result. -- Doug Pardee -- CalComp -- {seismo!noao,decvax!noao,ihnp4}!terak!doug
bright@dataio.UUCP (Walter Bright) (09/03/85)
In article <693@terak.UUCP> doug@terak.UUCP (Doug Pardee) writes: >Compiler writers note -- a comparison is not "just a subtract". >For example: > >#define NBITS 16 >/* NBITS is number of bits in an integer */ > int a, b; > a = 3 << (NBITS-3); /* 24576 for NBITS=16 */ > b = -a; > if (a>b) > printf("Comparison was done by bit-wise comparison\n"); > else > printf("Comparison was done by subtraction\n"); /* WRONG */ >A compiler would have had to generate extra code to test for Overflow >in order to get the correct result. I disagree. A comparison is a subtract with the result thrown away. The trick is to select the correct conditional branch instruction afterwards, depending on whether a signed or unsigned comparison was done. The case you labeled as WRONG is wrong, a compiler that did that would have a bug, but not for the reasons you mentioned. If a or b was declared as unsigned, that case would be correct. No additional code is required to test for Overflow, that is handled by using the correct conditional branch, even if a subtract instruction was generated.
peter@graffiti.UUCP (Peter da Silva) (09/03/85)
> Compiler users note -- if your compiler gives the wrong results, the > compiler writer might not be completely at fault. Many early CPU > chips (8080A, Z80, 6502, etc.) did comparison by subtraction, and a > compiler would have had to generate extra code to test for Overflow > in order to get the correct result. Most chips that I know of handle compare by doing a subtraction, setting the bits, and throwing away the results. Since most chips also allow a single instruction to test any number of flags no extra code need be generated to differentiate between the two. Maybe you're thinking of FORTH which generally does what you just described... Anyway, in Z80, 6502, 8080, 6809, PDP-11, and so on the scenario I just described takes place. the BLT <xxx> instruction tests for N bit xor V bit (I think I've got that right). Or does it test for a nice light sandwich made with bacon, lettuce, and tomato? I don't remember. It's too early.
ark@alice.UucP (Andrew Koenig) (09/03/85)
> I disagree. A comparison is a subtract with the result thrown away. The > trick is to select the correct conditional branch instruction afterwards, > depending on whether a signed or unsigned comparison was done. Don't try that trick in floating point, or you'll get spurious overflow traps when comparing perfectly legitimate numbers.
garys@bunker.UUCP (Gary M. Samuelson) (09/10/85)
> Most chips that I know of handle compare by doing a subtraction, setting the > bits, and throwing away the results. Since most chips also allow a single > instruction to test any number of flags no extra code need be generated to > differentiate between the two. What chips *are* you talking about? > Anyway, in Z80, 6502, 8080, 6809, PDP-11, and so on the scenario I just > described takes place. the BLT <xxx> instruction tests for N bit xor V bit The Z80 and 8080 have no such instruction -- there are four testable flags (carry, zero, parity/overflow, and sign); each conditional branch tests the state of exactly one of these flags. Gary Samuelson ittatc!bunker!garys
wls@astrovax.UUCP (William L. Sebok) (09/11/85)
>> Compiler users note -- if your compiler gives the wrong results, the >> compiler writer might not be completely at fault. Many early CPU >> chips (8080A, Z80, 6502, etc.) did comparison by subtraction, and a >> compiler would have had to generate extra code to test for Overflow >> in order to get the correct result. > >Most chips that I know of handle compare by doing a subtraction, setting the >bits, and throwing away the results. Since most chips also allow a single >instruction to test any number of flags no extra code need be generated to >differentiate between the two. Maybe you're thinking of FORTH which generally >does what you just described... Some FORTH implementations used to (or still do) implement the integer compare operations this way. However those FORTH's are buggy as it is possible to do it right. In both the FORTH-79 and FORTH-83 standards it is demanded that the comparison work even in the presence of overflow. Unfortunately they specify overflow of a 16 bit word, but that is another matter. -- Bill Sebok Princeton University, Astrophysics {allegra,akgua,cbosgd,decvax,ihnp4,noao,philabs,princeton,vax135}!astrovax!wls
rcd@opus.UUCP (Dick Dunn) (09/18/85)
> > Compiler users note -- if your compiler gives the wrong results, the > > compiler writer might not be completely at fault. Many early CPU > > chips (8080A, Z80, 6502, etc.) did comparison by subtraction, and a > > compiler would have had to generate extra code to test for Overflow > > in order to get the correct result. Oomph! Point of philosophy, yer honner--it is NOT the job of the compiler writer to transmit shortcomings of the processor into language problems. If the chip does the comparison "wrong" (in some cheap way), the compiler writer needs to sort it out so that the language implementation gives the right answer. I once complained about the implementation of certain comparison operations in a well-known language on a well-known processor--the problem was that it was possible to find values a, b, c such that all of a<b, b<c, and c<a were true! The response I received, from the well-known designer of this well-known language (and no, obviously this wasn't C!) was something to the effect that "we decided not to implement [the correct comparison code] thereby trying to correct the unprofessional design of the computer by an inefficient implementation. Whether this decision was right, I do not know." Well, he didn't know, but I did (and do). If it ain't right, it's wrong (except in quantum mechanics and politics), no matter how efficient it is. -- Dick Dunn {hao,ucbvax,allegra}!nbires!rcd (303)444-5710 x3086 ...Lately it occurs to me what a long, strange trip it's been.
doug@terak.UUCP (Doug Pardee) (09/20/85)
> I disagree. A comparison is a subtract with the result thrown away. The > trick is to select the correct conditional branch instruction afterwards, > depending on whether a signed or unsigned comparison was done. Watch my lips! A signed comparison is *not* a subtract with the result thrown away. Write that down so you don't forget it. I offer another example... take an 8-bit machine, both for simplicity and because the 8080A/Z80/6502 all did compares via subtraction. If you compare the A register with a decimal 40 on any of those CPUs, you will get the following results: A=+41: Ovf=0 N=0 C=no borrow (1 on 6502, 0 on 8080A/Z80) A=+39: Ovf=0 N=1 C=borrow A=-40: Ovf=0 N=1 C=no borrow A=-90: Ovf=1 N=0 C=no borrow The situation is even worse if you don't know whether the comparison value (40 in this example) is positive or negative. > No additional code is required to test for > Overflow, that is handled by using the correct conditional branch, even > if a subtract instruction was generated. There is *no* conditional branch on those CPUs which will reliably select high versus low on a signed comparison. The only way to handle this is with a network of branches, which do normal branching if no Overflow, and opposite branching if the Overflow bit is set. Lord knows I've written enough of 'em. Fortunately, the more modern CPU chips are designed with a proper compare instruction which does bit-wise comparison instead of subtraction. All I ask is that the compiler writers *use* those instructions the way they were intended, instead of substituting a subtraction. <Fortunately, the NS32000 CPUs don't provide status bits (except carry) on subtraction, so the compiler writer is forced to use the bit-wise compare instruction>. -- Doug Pardee -- CalComp -- {calcom1,savax,seismo,decvax,ihnp4}!terak!doug
chris@umcp-cs.UUCP (Chris Torek) (09/21/85)
>> I disagree. A comparison is a subtract with the result thrown away. The >> trick is to select the correct conditional branch instruction afterwards, >> depending on whether a signed or unsigned comparison was done. > Watch my lips! A signed comparison is *not* a subtract with the result > thrown away. Write that down so you don't forget it. > I offer another example... take an 8-bit machine, both for simplicity > and because the 8080A/Z80/6502 all did compares via subtraction. Watch my fingers! A signed comparison is a subtract with the result thrown away. I offer another example. Take a 32 bit machine---the Vax---both for simplicity and because the Vax does compares via subtraction. But I will use a byte instruction: cmpb r1,$40 blss label # branch if less than If you wish to do an unsigned comparison: cmpb r1,$40 blssu label # branch if less than unsigned Can we lay this to rest? How the compiler implements comparison is machine dependent. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 4251) UUCP: seismo!umcp-cs!chris CSNet: chris@umcp-cs ARPA: chris@maryland
franka@mmintl.UUCP (Frank Adams) (09/24/85)
[Not food] In article <726@terak.UUCP> doug@terak.UUCP (Doug Pardee) writes: >Fortunately, the more modern CPU chips are designed with a proper >compare instruction which does bit-wise comparison instead of >subtraction. All I ask is that the compiler writers *use* those >instructions the way they were intended, instead of substituting a >subtraction. <Fortunately, the NS32000 CPUs don't provide status bits >(except carry) on subtraction, so the compiler writer is forced to use >the bit-wise compare instruction>. Many (most?) of those chips set the flags the same way after a subtract as after a compare. For that class of chips, a compare is a subtract with the correct flags set. Architectures where a branch cannot be taken based on a comparison of two signed numbers with two instructions (maybe three) are brain-damaged. It doesn't matter (much) whether the first instruction is a subtract or a compare. Compilers should generate a correct branch even on brain-damaged machines. Compilers for a machine where a compare and branch works, but a subtract and branch doesn't, but which use a subtract and branch, are *really* brain-damaged. Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
ken@turtlevax.UUCP (Ken Turkowski) (09/25/85)
In article <726@terak.UUCP> doug@terak.UUCP (Doug Pardee) writes: > ... >Fortunately, the more modern CPU chips are designed with a proper >compare instruction which does bit-wise comparison instead of >subtraction. What a bunch of BS! A compare is simply a subtract with the result thrown away. You imply that a compare does an exclusive-OR, which will compare only for equality, but not for ordering. The conditions used for the branch will determine how the operands are to be compared: whether as signed integers or unsigned integers. A subtraction sets 4 bits: negative (N), zero (Z), carry (C), and overflow (V). They are combined to indicate ordering relationships as follows: signed < N ^ V signed <= (N ^ V) | Z signed > !(N ^ V) & !Z signed >= !(N ^ V) unsigned < !C unsigned <= !C | Z unsigned > C & !Z unsigned >= C == Z != !Z Note that some machines generate a borrow (B) rather than a carry after subtraction. Just substitute a !B for C above. -- Ken Turkowski @ CADLINC, Menlo Park, CA UUCP: {amd,decwrl,hplabs,seismo,spar}!turtlevax!ken ARPA: turtlevax!ken@DECWRL.ARPA
rdp@teddy.UUCP (09/26/85)
In article <688@mmintl.UUCP> franka@mmintl.UUCP (Frank Adams) writes: > >Architectures where a branch cannot be taken based on a comparison of two >signed numbers with two instructions (maybe three) are brain-damaged. > >Compilers should generate a correct branch even on brain-damaged machines. >Compilers for a machine where a compare and branch works, but a subtract >and branch doesn't, but which use a subtract and branch, are *really* >brain-damaged. > While this reply was inspired by this particular posting, it is not a flame at the poster, but rather to the network in general. Over a number of years, members of my family have been involved in the care and education of retarded and brain-damaged people. Recently, I myself married and gained a 14-year old son with epilepsy. The cavalier use of the term "brain-damaged" is both innappropriate and, in some cases, downright offensive. The use of the term seems to be limited to net.lang.c, which may or may not be testimony to the level of courtesy of the people inclined to communicate in this forum. The attitude exemplified above seems to give this person the impression that matters of incontrovertable physical law are being questioned ("architectures ... ARE brain-damaged:, as opposed to "architectures ... I find deficient"). The opinoins expressed on this net are just that. Frankly, letters like the above I find to be the output of human architectures which are socially-damaged. Flames in reply are not solicited, welcome, or accepted. Thank you Dick Pierce
doug@terak.UUCP (Doug Pardee) (09/26/85)
me >Fortunately, the more modern CPU chips are designed with a proper me >compare instruction which does bit-wise comparison instead of me >subtraction. > What a bunch of BS! A compare is simply a subtract with the result > thrown away. You imply that a compare does an exclusive-OR, which will > compare only for equality, but not for ordering. Not so; my apologies for not having been clear enough. A proper compare consists of determining the most significant bit which differs between the two words, if any, and setting the result accordingly. If it is the Most Significant Bit that differs, then the result is inverted for signed comparisons. A usable approximation is to do a subtraction, but for signed comparisons also do a sign-bit test. If the sign bits do not match, then the result is not equal, and the positive number is larger, regardless of the result of the subtraction. > The conditions used for the branch will determine how the operands are > to be compared: whether as signed integers or unsigned integers. A > subtraction sets 4 bits: negative (N), zero (Z), carry (C), and > overflow (V). They are combined to indicate ordering relationships as > follows: > > signed < N ^ V This is great for CPUs such as the AMD bit-slice stuff which does provide a "Negative XOR Overflow" status. But for garden-variety single-chip CPUs, this isn't the case. On a Z-80, one must code JP PE,OFLOWD JP N,LT JP GE OFLOWD: JP N,GE JP Z,GE JP LT You don't get a choice on the Z-80. But why subject yourself to this on say, a 68000 when you could use CMP instead of SUB? -- Doug Pardee -- CalComp -- {calcom1,savax,seismo,decvax,ihnp4}!terak!doug
arc@myriasb.UUCP (Alan Covington) (09/27/85)
Chris Torek writes > I offer another example. Take a 32 bit machine---the Vax---both for > simplicity and because the Vax does compares via subtraction. But I > will use a byte instruction: The VAX cmp and sub instructions set the condition codes differently. Thus, the cmp is not just a "subtract" with the result thrown away. An easy example is comparing 0x80000000 and 1 results in the N bit of the condition codes being set, whereas subtracting 1 from 0x80000000 results in the overflow bit being set. The VAX may use a subtract as part of the cmp instruction, but it doesn't do signed comparison as Chris claims. > A signed comparison is a subtract with the result > thrown away. Alan Covington ...!alberta!myrias!arc
marv@ISM780.UUCP (09/28/85)
>What a bunch of BS! A compare is simply a subtract with the result >thrown away. You imply that a compare does an exclusive-OR, which will >compare only for equality, but not for ordering. Not true for all machines! There is a rather famous machine made by that Itty Bitty Machine manufacturer that produces a condition code that is a number in the range 0..2 (excuse a Pascal idiom in this form). Quoting from the Princples of Operation for the machine: Compare Resulting condition code --------- --------- ---- 0 Operands are equal 1 First operand is low 2 First operand is high 3 -- Subtract Resulting condition code --------- --------- ---- 0 Operands are equal 1 First operand is low 2 First operand is high 3 Overflow The important point is that the compiler for this machine must generate more code to compare two numbers if is uses a Subract instead of a Compare. Because if (a-b) overflows the information about which operand is larger is not preserved in the resulting condition code. I just had to fix a bug in our C complier because it generated a Subtract followed by a Branch Low (in the implementation of unsigned divide). And in a rather obscure case the subtraction caused an overflow. Marv Rubinstein -- Interactive Systems
ken@turtlevax.UUCP (Ken Turkowski) (10/02/85)
In article <30000015@ISM780.UUCP> marv@ISM780.UUCP writes: > >>What a bunch of BS! A compare is simply a subtract with the result >>thrown away. You imply that a compare does an exclusive-OR, which will >>compare only for equality, but not for ordering. > >Not true for all machines! There is a rather famous machine made by that >Itty Bitty Machine manufacturer that produces a condition code that is a >number in the range 0..2 (excuse a Pascal idiom in this form). > >Quoting from the Princples of Operation for the machine: > > Compare > > Resulting condition code > --------- --------- ---- > 0 Operands are equal > 1 First operand is low > 2 First operand is high > 3 -- > > Subtract > > Resulting condition code > --------- --------- ---- > 0 Operands are equal > 1 First operand is low > 2 First operand is high > 3 Overflow This implies that the compare instruction should be used for unsigned comparisons, and that the subtract as well as a conditional compare is needed for signed numbers. >The important point is that the compiler for this machine must generate more >code to compare two numbers if is uses a Subract instead of a Compare. Because >if (a-b) overflows the information about which operand is larger is not >preserved in the resulting condition code. It is not an arbitrary choice between using one or the other for this machine. You must use the appropriate method of comparison, depending on the type of the instruction. -- Ken Turkowski @ CADLINC, Menlo Park, CA UUCP: {amd,decwrl,hplabs,seismo,spar}!turtlevax!ken ARPA: turtlevax!ken@DECWRL.ARPA