ok@quintus.UUCP (Richard A. O'Keefe) (03/02/88)
In article <7276@sol.ARPA>, crowl@cs.rochester.edu (Lawrence Crowl) writes: > In article <7649@pur-ee.UUCP> hankd@pur-ee.UUCP (Hank Dietz) writes: > >For example, a multiply by 7 (not a nice power of 2) is really shift to > >multiply by 8 and then subtract the original number. > > If you use this method for multiplication by 7, and you do not provide for > a double width result, using subtraction will lose the overflow information. One big difference between IEEE floating-point arithmetic and older approaches is that it lets you delay overflow checks to the end of a calculation, instead of requiring the hardware to trap (which should permit a simpler pipeline, shouldn't it?) or forcing an overflow check after each FP instruction. This works because overflow is sticky: any calculation involving a NaN or Infinity yields a NaN or Infinity. (BTW: does anyone know if the MC 68881 has a trap-now-if-NaN-or-Infinity instruction?) How about something like this for integer arithmetic? Suppose there were two flavours of load/move instruction (one to clear the overflow bit, one to leave it alone), and that integer arithmetic instructions were to set the overflow bit, but not clear it. Then this argument against shift-and- subtract would go away. Are there any machines which use this approach? What are its disadvantages?
crowl@cs.rochester.edu (Lawrence Crowl) (03/03/88)
In article <718@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: )In article <7276@sol.ARPA>, crowl@cs.rochester.edu (Lawrence Crowl) writes: )> In article <7649@pur-ee.UUCP> hankd@pur-ee.UUCP (Hank Dietz) writes: )> >For example, a multiply by 7 (not a nice power of 2) is really shift to )> >multiply by 8 and then subtract the original number. )> )> If you use this method for multiplication by 7, and you do not provide for )> a double width result, using subtraction will lose the overflow information. )> ... [crucial text deleted] ... ) )Suppose there were two flavours of load/move instruction (one to clear the )overflow bit, one to leave it alone), and that integer arithmetic )instructions were to set the overflow bit, but not clear it. Then this )argument against shift-and-subtract would go away. You have missed the point. There are two situations in shift-and-subtract where an overflow may occur. In the first case, n*8-n causes an overflow at the shift, but n*7 does not cause an overflow. In the second case, n*7 also causes an overflow. This first case is a spurious overflow, and the second is a real overflow. I see no immediate (i.e. cheap) way of determining if an overflow is real or spurious. This implies that in order to only generate real overflows, compilers must limit themselves to the shift-and-add method. -- Lawrence Crowl 716-275-9499 University of Rochester crowl@cs.rochester.edu Computer Science Department ...!{allegra,decvax,rutgers}!rochester!crowl Rochester, New York, 14627
hansen@mips.COM (Craig Hansen) (03/03/88)
In article <718@cresswell.quintus.UUCP>, ok@quintus.UUCP (Richard A. O'Keefe) writes: > How about something like this for integer arithmetic? Suppose there were > two flavours of load/move instruction (one to clear the overflow bit, one > to leave it alone), and that integer arithmetic instructions were to set > the overflow bit, but not clear it. Then this argument against shift-and- > subtract would go away. > > Are there any machines which use this approach? > What are its disadvantages? It doesn't work for the multiply-by-seven case, because the multiply-by-eight might overflow (and set the overflow bit) even though the final result is OK. It's not that big a deal (doesn't justify having much extra stuff), as you can do a multiply by 7 with full overflow check with 4 instructions: addo r2 <- r1 + r1 ; *2 addo r2 <- r2 + r1 ; *3 addo r2 <- r2 + r2 ; *6 addo r2 <- r2 + r1 ; *7 ...and in fact, shift-and-add is just two instructions: sh2addo r2 <- r1 << 2 + r1 ; *5 sh1addo r2 <- r1 << 1 + r2 ; *7 If you want to get shift-and-subtract with overflow checking, you can easily keep one extra bit of precision after the shift, so that you properly check overflow after the subtract. With such a well-defined primitive (that only overflows if the result of the operation, not the intermediate result, overflows), you can safely use shift-and-subtract instructions so long as the intermediate products you put in registers aren't larger than the final result. -- Craig Hansen Manager, Architecture Development MIPS Computer Systems, Inc. ...{ames,decwrl,prls}!mips!hansen or hansen@mips.com 408-991-0234
ok@quintus.UUCP (Richard A. O'Keefe) (03/03/88)
In article <7310@sol.ARPA>, crowl@cs.rochester.edu (Lawrence Crowl) writes: > In article <718@cresswell.quintus.UUCP> ok@quintus.UUCP > (Richard A. O'Keefe) writes: > )Suppose there were two flavours of load/move instruction (one to clear the > )overflow bit, one to leave it alone), and that integer arithmetic > )instructions were to set the overflow bit, but not clear it. Then this > )argument against shift-and-subtract would go away. > > You have missed the point. I'm afraid Lawrence Crowl missed my point entirely. I couldn't care less about multiplication by 7 or any other specific operation. I just used that (which was already being discussed) as a lead-in. Suppose I have a Pascal or ADA program which does K := (some hairy great complicated integer expression); There seem to be three approaches in current use: (1) have an integer overflow interrupt, which is enabled for Pascal and ADA, but disabled for C. (2) have a non-sticky overflow bit, which has to be tested after each instruction which the compiler is unable to prove will not overflow. Again, Pascal and ADA would keep testing this flag, C would never test it. (3) Ignore the problem and hope it will go away. Very popular for Pascal, normally illegal for ADA. With a sticky-overflow bit, (1) you don't have to switch modes when calling C from ADA or vice versa (2) you only have to test just before stores and compares (3) one 'trapv' per assignment or comparison is a sufficiently low cost that going to sea without a life jacket might seem less attractive. In the Good Old Days I used to use a B6700, and since that I have never been able to regard quiet overflow as a good idea. Sticky overflow seems like such an obvious idea (I stole it from IEEE floating point). Why is it not used, or is it?
davidsen@steinmetz.steinmetz.UUCP (William E. Davidsen Jr) (03/03/88)
In article <7310@sol.ARPA> crowl@cs.rochester.edu (Lawrence Crowl) writes: | You have missed the point. There are two situations in shift-and-subtract | where an overflow may occur. In the first case, n*8-n causes an overflow at | the shift, but n*7 does not cause an overflow. In the second case, n*7 also | causes an overflow. This first case is a spurious overflow, and the second | is a real overflow. From my old GE-600 manual, ca 1960, "An overflow is detected when the XOR of the sign bit and the most significant bit changes." Sounds pretty good to me. Then you could make it sticky, if you wnated. I suspect that the decision to interrupt or not on overflow is best controlled as a condition in a flag register, and set by a smart compiler (or programmer). In the case where a long series of operations is taking place, the cost of doing an exception processing would be lower than the cost of doing useless calculation. If the calculation was short, some form of "test and branch" at the end would be faster. -- bill davidsen (wedu@ge-crd.arpa) {uunet | philabs | seismo}!steinmetz!crdos1!davidsen "Stupidity, like virtue, is its own reward" -me
hansen@mips.COM (Craig Hansen) (03/04/88)
In article <724@cresswell.quintus.UUCP>, ok@quintus.UUCP (Richard A. O'Keefe) writes: > There seem to be three approaches in current use: > (1) have an integer overflow interrupt, which is enabled for Pascal > and ADA, but disabled for C. > (2) have a non-sticky overflow bit, which has to be tested after each > instruction which the compiler is unable to prove will not overflow. > Again, Pascal and ADA would keep testing this flag, C would never test it. > (3) Ignore the problem and hope it will go away. > Very popular for Pascal, normally illegal for ADA. (4) have instructions that check for and trap on overflow in their operation, and have other instructions that don't check for overflow. The former kind are used in Pascal and ADA code, the latter kind are used in C code. It's better than #1, because C code and Pascal code can often be mixed in a single program, and #1 would require some extra code to enable/disable the interrupt when crossing between C & Pascal code. #2, adding explicit instructions to check for an overflow, even a sticky one, isn't a really hot idea, as the overflow doesn't happen often, (usually no more than once per program invocation), so it's a shame to waste a cycle each time it doesn't happen. That's what exceptions/traps are for - to efficiently check for events that are statistically rare. -- Craig Hansen Manager, Architecture Development MIPS Computer Systems, Inc. ...{ames,decwrl,prls}!mips!hansen or hansen@mips.com 408-991-0234
ok@quintus.UUCP (Richard A. O'Keefe) (03/05/88)
In article <1755@mips.mips.COM>, hansen@mips.COM (Craig Hansen) writes: > In article <718@cresswell.quintus.UUCP>, ok@quintus.UUCP (Richard A. O'Keefe) writes: > > How about something like this for integer arithmetic? Suppose there were > > two flavours of load/move instruction (one to clear the overflow bit, one > > to leave it alone), and that integer arithmetic instructions were to set > > the overflow bit, but not clear it. Then this argument against shift-and- > > subtract would go away. > It doesn't work for the multiply-by-seven case, because the > multiply-by-eight might overflow (and set the overflow bit) even > though the final result is OK. > Multiply-by-seven was just a lead-in. What happens if the *PROGRAMMER* wrote (X*8)-8? I don't give a ----- about multiplies as such. I'm sick and tired of programming languages which completely ignore overflows in integer arithmetic, and I'm looking for a cheap method which will let a compiler generate efficient code that *does* check for overflow and efficient code that *doesn't* without requiring two complete sets of instructions and without having to continually flip PSW bits. The original RISC approach had two sets of instructions: with a particular bit set in an instruction the condition codes are affected, with the bit in the opposite state the condition codes are not affected. This lets a compiler generate checking or non-checking code as appropriate, but still requires a test after every instruction which might set the codes. I would like to write a Pascal statement like i := (i div 10)*256 + (i mod 10); which has four operations, and have the overflow test cost at most one instruction (TRAPV equivalent). To be perfectly frank, I don't mind too much if the compiler handles multiplication by a constant in a way that reports overflow a few times too many. What I *do* mind, and mind very much, is not being told about overflow at all. What good is an "efficient" program that silently yieds incorrect answers?
baum@apple.UUCP (Allen J. Baum) (03/08/88)
-------- [] >In article <718@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >How about something like this for integer arithmetic? Suppose there were >two flavours of load/move instruction (one to clear the overflow bit, one >to leave it alone), and that integer arithmetic instructions were to set >the overflow bit, but not clear it. Then this argument against shift-and- >subtract would go away. > >Are there any machines which use this approach? >What are its disadvantages? The ATT CRISP does this. Both Carry and Overflow are sticky. I don't recall if there are trap instructions for them, but the are at least special branch instructions. I also don't know if there is a special reset-overflow inst., but branching on overflow will clear the overflow bit. -- {decwrl,hplabs,ihnp4}!nsc!apple!baum (408)973-3385
davidg@eleazar.Dartmouth.EDU (David Gelhar) (03/14/88)
The Honeywell 6000 series and relatives (such as DPS 8's), have a 'sticky' overflow bit. Various integer arithmetic instructions set the overflow indicator; it's cleared by the "transfer on overflow" instruction (or by loading the indicators). Another indicator bit (or condition code, if you like to call them that) controls whether or not overflows should cause a fault. Wise-ass programmers sometimes clear the overflow bit with what looks like an infinite loop: TOV * "clear overflow indicator This works great for addition & subtraction, but unfortunately the integer multiply instruction is defined to multiply two one-word quantities together and produce a TWO-word result; you get no indication from the hardware if the result is too large for a single word. This means you're left with a choice between adding a couple of instructions after every multiply to check for overflow (Pascal does this), or having integer overflows on multiplication go undetected (PL/I and C).
aglew@ccvaxa.UUCP (03/18/88)
..> Sticky overflow bits in Honeywell machines
A class I am taking (High Performance Processor Design) is currently
discussing techniques for providing precise interrupts with out of
order instruction scheduling - checkpoint/restore, history buffers,
past register sets, etc.
This mention of sticky overflow bits causes me to wonder if it might
not be advantageous to let the DETECTION of an exception condition
(trap or pagefault, not an asynchronous event like an external interrupt)
be done by software checking sticky flags, and making the return to
checkpointed state under software control.
Andy "Krazy" Glew. Gould CSD-Urbana. 1101 E. University, Urbana, IL 61801
aglew@gould.com - preferred, if you have MX records
aglew@xenurus.gould.com - if you don't
...!ihnp4!uiucuxc!ccvaxa!aglew - paths may still be the only way
My opinions are my own, and are not the opinions of my employer, or any
other organisation. I indicate my company only so that the reader may
account for any possible bias I may have towards our products.