crowl@cs.rochester.edu (Lawrence Crowl) (03/02/88)
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. For example, a*7 implemented as (a<<3)-a may overflow where (a<<2)+(a<<1)+a will not. If we detect an overflow with (a<<3)-a, then we cannot immediately tell whether or not a*7 would overflow. -- Lawrence Crowl 716-275-9499 University of Rochester crowl@cs.rochester.edu Computer Science Department ...!{allegra,decvax,rutgers}!rochester!crowl Rochester, New York, 14627
hankd@pur-ee.UUCP (Hank Dietz) (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. > For example, a*7 implemented as (a<<3)-a may overflow where (a<<2)+(a<<1)+a > will not. If we detect an overflow with (a<<3)-a, then we cannot immediately > tell whether or not a*7 would overflow. I suggested this for multiplies in computing offsets given an array subscript. In such cases, the compiler can trivially know whether a range error could occur since it knows the possible range of values for the subscript and hence it also knows the range of result values from the multiply. I thought this condition was obvious enough that it didn't need to be stated explicitly... I guess I was wrong. Anyway, even for an arbitrary value being multiplied by a constant, the same range information can usually be obtained by fairly simple compile-time analysis. In short, if it MIGHT overflow, then you use only shifts and adds; otherwise, subs are ok too. Even violating that rule, "a double width result" is overkill; in the example of multiply by 8 and subtract original value, you'd need at most one extra bit of precision (e.g., carry). -hankd
hansen@mips.COM (Craig Hansen) (03/03/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. > For example, a*7 implemented as (a<<3)-a may overflow where (a<<2)+(a<<1)+a > will not. If we detect an overflow with (a<<3)-a, then we cannot immediately > tell whether or not a*7 would overflow. This is true, but completely irrelevant to the issue of performing multiplications for index calculations. Such multiplications do not require overflow checks, as the index itself can be tested for the proper subrange more easily than the address of the array element. The MIPS compiler will generate shift and subtract sequences for multiplications without overflow check, but restricts the generated sequences to adds for multiplications with overflow checking. The HP Precision architecture does this in fewer cycles by checking for overflow on the shift and the add in the shift-and-add instructions (checking for overflow on shift instructions is a nice idea). -- Craig Hansen Manager, Architecture Development MIPS Computer Systems, Inc. ...{ames,decwrl,prls}!mips!hansen or hansen@mips.com 408-991-0234
hutchson@convex.UUCP (03/03/88)
The GE-600 and its successor machines had something very like this. The floating-point overflow was set (but not cleared) by floating-point arithmetic operations. An interrupt would be taken immediately upon an operation that yielded floating-point overflow IF the "floating-point overflow mask" bit in the PSW was not set. There was a conditional transfer instruction (TOV, I believe) that tested and cleared the floating-point overflow bit.