!standard RM-3.5.4 (07) 96-11-16 AI95-00095/02 !class ramification 95-09-29 !status WG9 approved 96-12-07 !status ARG Approved 6-0-5 96-10-07 !status work item 95-09-29 !status received 95-09-29 !priority High !difficulty Medium !subject Modular types on one's complement machines. !summary 95-09-29 Implementation Permission: On a one's complement machine, the implementation may support non-binary modulii above System.Max_Nonbinary_Modulus. !question 95-09-29 How should an implementation on a one's complement machine implement modular types intended to use all the bits of a full word? !response 95-09-29 Consider a 36-bit one's complement machine. One should be able to declare a 36-bit modular type. For logical operations to make sense, the all-ones bit pattern ought to be allowed, and should compare not equal to zero, and greater than every other bit pattern. The Implementation Permission in 3.5.4(27) is intended to allow this. On a 36-bit two's complement machine, one would declare: type T is mod 2**36; and T'Modulus would be 2**36, and the base range of T would be 0..2**36-1. If one says: type T is mod 2**36-1; T'Modulus is 2**36-1, and the base range of T is 0..2**36-2. The implementation permission says that the base range of T can be 0..2**36-1. This means that the all-ones bit pattern is a valid value of the type, and is not reduced via the modulus. !appendix 96-11-16 !section RM-3.5.4(07) !subject Modular types on 1's complement machines. !reference RM95-3.5.4(7) !reference RM95-3.5.4(27) !reference AARM95-3.5.4(29.b) !reference AARM95-3.5.4(29.c) !reference RM95-1.1.6(6) !from Randy Brukardt 95-09-13 !reference as: 95-5292.a rbrukardt@BIX.com 95-9-14>> !discussion The two AARM notes 3.5.4(29.b) and 3.5.4(29.c), imply that either an Ada compiler for a 1's complement machine must not support a full-size modular type, or it must suffer an unreasonable implementation burden. However, a full range modular type is necessary to implement some of the predefined packages (Interfaces and Interfaces.C come to mind), so in actuality such an implementation must suffer an unreasonable implementation burden. 1's complement compilers should be able to support some (usually one) additional non-binary modulii above System.Max_Nonbinary_Modulus, in order to avoid the problem. Some argument based on 1.1.3(6) (the old AI-325) probably can be used here, but I have no idea what it would be. Additional background is given below. ------ 3.5.4(27) gives permission for a compiler for a 1's complement machine to bend the rules, allowing an additional value. It is not clear to me exactly what is meant here. I think the intent is to allow negative 0 as a legal value. However, the permission states that the extra value "is the high bound of the base range". Whether that is true would depend on what operations are being used, in what order, and possibly where the operations are used. For instance, the presence of an extra value would eliminate the need to check for overflow on add operations. However, an occurrence of such a value would probably compare as a zero, meaning its presence could not be detected. I think this means that code using a modulus which took advantage of the permission would not be portable to or from a 1's complement machine. For an implementation using generic sharing, it is likely that the code sequence for a modular operation will be different inside a generic from outside. In this case, different results could result depending on whether the operation was in a generic. Is the intent of this permission that all operations produce and compare this extra value properly? If so, there is not much need for the permission. OTOH, if the intent is to let implementions do what they want, full range unsigned types will not be very portable. ------ Background: We are working with Unisys on an Ada 95 implementation for the 2200 series machines. Those machines are 36-bit, 1's complement machines. Originally, we did not think there was a problem here. After all, the C compiler supports a full 36-bit unsigned type. We would just copy that implementation. However, on further inspection, that turns out not to be so easy. The C compiler had major problems with the unsigned type. Ultimately, two versions of the C compiler were built, one to pass the C validation tests, and one to actually use. To pass the C validation tests, Unisys built a compiler which emulated 2's complement math for this machine! That was done by doing all operations as 72 bit operations, and then reducing the result. Obviously, they did not want to use that implementation for production use. We looked at the difficulty of implementing a true full range type. Most of the arithmetic operations are no problem. The logical operations are also no problem. The problem would come with the subtract operations (which would mistreat the largest value) and with the comparison (likewise). If need be, we could write expensive versions of these operations which would work properly. We would like to match the actual C compiler by supporting modulii up to 2**35-1 (Integer'Last) and 2**36-1. (2**35 does not pose any particular problem, and we probably will support that, too.) Of course, this does not fit into the model given in 3.5.4. We are not sure whether we should be using the permission given in 3.5.4(27). If the permission is read to allow generating the extra value, or not, depending on the actual sequence of operations, then we would prefer to use it. Otherwise, it is of no particular value (the only real problem with implementing a modulus of 2**36 being the subtract/compare operations, which would have to be emulated in either case). **************************************************************** !section RM-3.5.4(07) !subject Modular types on 1's complement machines. !reference RM95-3.5.4(7) !reference RM95-3.5.4(27) !reference AARM95-3.5.4(29.b) !reference AARM95-3.5.4(29.c) !reference RM95-1.1.6(6) !reference 95-5292.a Randy Brukardt 95-09-13 !from Tucker Taft 95-09-13 !reference as: 95-5293.a Tucker Taft 95-9-14>> !discussion > ... > 1's complement compilers should be able to support some (usually one) > additional non-binary modulii above System.Max_Nonbinary_Modulus, in order > to avoid the problem. Agreed. The implementation permission for 1's complement machines should have allowed the set of nonbinary-modulus types to have a gap in supported moduli between Integer'Last and Max_Nonbinary_Modulus. Alternatively, you can just consider it a "nonstandard" integer type, defined in package Interfaces, and only available by deriving from the type declared in package Interfaces (that is, you can't declare one by using a "type U is mod 2**N-1;", but only by using "type U is new Interfaces.Unsigned_N;"). Either is probably OK. > ... > 3.5.4(27) gives permission for a compiler for a 1's complement machine to > bend the rules, allowing an additional value. It is not clear to me exactly > what is meant here. I think the intent is to allow negative 0 as a legal > value. However, the permission states that the extra value "is the high > bound of the base range". Whether that is true would depend on > what operations are being used, in what order, and possibly where the > operations are used. > > For instance, the presence of an extra value would eliminate the need to > check for overflow on add operations. However, an occurrence of such a > value would probably compare as a zero, meaning its presence could not > be detected. I think this means that code using a modulus which took > advantage of the permission would not be portable to or from a 1's > complement machine. Let's call "negative 0" "all ones" to avoid thinking of it as a negative number. It is just an all-ones bit pattern. It is essential that the all-ones bit pattern *not* compare equal to the all-zeros bit pattern for modular types. I would hope that there is some way of doing a comparison that makes the distinction. Perhaps the "xor" operation could be used rather than the "eq" operation. > For an implementation using generic sharing, it is likely that the code > sequence for a modular operation will be different inside a generic from > outside. In this case, different results could result depending on whether > the operation was in a generic. No comment on this one. Thunks may be your only solution here. > Is the intent of this permission that all operations produce and compare > this extra value properly? If so, there is not much need for the permission. > OTOH, if the intent is to let implementions do what they want, full range > unsigned types will not be very portable. The intent is that all-ones is a distinct value, greater than any other value (corresponding to 2**N-1), but when an operation would "logically" produce a value that is outside the base range (greater than 2**N-1, or less than zero), the result is "reduced" modulo 2**N-1 (hopefully by the hardware!). Hence 2**N-1 + 1 will give 1, not zero. Similarly, 0 - 1 will give 2**N-2, rather than 2**N-1. This is the intent of 3.5.4(19). It is hoped that this semantics will be portable, though portability between one's complement machines for this "funny" modular type is not a very high priority, in my mind. > ------ > > Background: > > We are working with Unisys on an Ada 95 implementation for the 2200 series > machines. Those machines are 36-bit, 1's complement machines. > > ... > We looked at the difficulty of implementing a true full range type. Most of > the arithmetic operations are no problem. The logical operations are also > no problem. The problem would come with the subtract operations (which would > mistreat the largest value) and with the comparison (likewise). If need > be, we could write expensive versions of these operations which would work > properly. Why do you think subtraction would mistreat the largest value? My understanding of the hardware is that it would do the right thing. Comparison is a different matter. You need to do an unsigned/logical comparison. I would hope that an unsigned/logical comparison would not treat all-zeros and all-ones as the same value. If so, it is pretty hard to do meaningful and-ing and or-ing. -Tuck **************************************************************** !section RM-3.5.4(07) !subject Modular types on 1's complement machines. !reference RM95-3.5.4(7) !reference RM95-3.5.4(27) !reference AARM95-3.5.4(29.b) !reference AARM95-3.5.4(29.c) !reference RM95-1.1.6(6) !reference 95-5292.a Randy Brukardt 95-09-13 !reference 95-5293.a Tucker Taft 95-9-14 !from Randy Brukardt 95-09-19 !reference as: 95-5301.a rbrukardt@BIX.com 95-9-19>> !discussion >> ... >> 1's complement compilers should be able to support some (usually one) >> additional non-binary modulii above System.Max_Nonbinary_Modulus, in order >> to avoid the problem. > >Agreed. The implementation permission for 1's complement machines >should have allowed the set of nonbinary-modulus types to have >a gap in supported moduli between Integer'Last and Max_Nonbinary_Modulus. >Alternatively, you can just consider it a "nonstandard" integer type, >defined in package Interfaces, and only available by deriving from >the type declared in package Interfaces (that is, you can't declare >one by using a "type U is mod 2**N-1;", but only by using "type U is new >Interfaces.Unsigned_N;"). >Either is probably OK. A non-standard type is not OK, because it cannot be used in generics, particularly Text_IO.Modular_IO. I doubt users would be happy about having no way to do I/O on the largest Modular type. (A user-defined child of Text_IO could be provided, but would make us even less portable and standard. Keeping the type declaration as the only item which needs to be changed when porting is a common goal). >> For instance, the presence of an extra value would eliminate the need to >> check for overflow on add operations. However, an occurrence of such a >> value would probably compare as a zero, meaning its presence could not >> be detected. I think this means that code using a modulus which took >> advantage of the permission would not be portable to or from a 1's >> complement machine. >Let's call "negative 0" "all ones" to avoid thinking of it as a negative >number. It is just an all-ones bit pattern. It is essential >that the all-ones bit pattern *not* compare equal to the all-zeros >bit pattern for modular types. I would hope that there is some way >of doing a comparison that makes the distinction. Perhaps the "xor" >operation could be used rather than the "eq" operation. When I was thinking of compare, I was thinking of the ">=" and "<=" operations. Equality itself is probably not a problem. >>.... >> Is the intent of this permission that all operations produce and compare >> this extra value properly? If so, there is not much need for the permission. >> OTOH, if the intent is to let implementions do what they want, full range >> unsigned types will not be very portable. >The intent is that all-ones is a distinct value, greater than >any other value (corresponding to 2**N-1), but when an operation >would "logically" produce a value that is outside the base range >(greater than 2**N-1, or less than zero), the result is "reduced" >modulo 2**N-1 (hopefully by the hardware!). >Hence 2**N-1 + 1 will give 1, not zero. Similarly, 0 - 1 will give >2**N-2, rather than 2**N-1. This is the intent of 3.5.4(19). >It is hoped that this semantics will be portable, though portability >between one's complement machines for this "funny" modular type is not >a very high priority, in my mind. OK, I think I understand the intent here. However, I'm not sure why we need a permission at all here. If the operations can never produce the value, then it does not differ at all from any other modular type. For instance, a Mod 7 type has a bit pattern corresponding to 7 (and probably has one for 99 and 100 and many other values too), but the language does not feel a need to comment on that. I guess that is where I'm confused. It seems that the permission is vacuous, since it doesn't allow the direct use of all of the hardware operations. The natural versions of some operations (OR, for instance) clearly will produce the all-ones bit pattern. [I'll get into the hardware specific issues in a moment.] >> Background: >> >> We are working with Unisys on an Ada 95 implementation for the 2200 series >> machines. Those machines are 36-bit, 1's complement machines. >> >> ... >> We looked at the difficulty of implementing a true full range type. Most of >> the arithmetic operations are no problem. The logical operations are also >> no problem. The problem would come with the subtract operations (which would >> mistreat the largest value) and with the comparison (likewise). If need >> be, we could write expensive versions of these operations which would work >> properly. > >Why do you think subtraction would mistreat the largest value? My >understanding of the hardware is that it would do the right thing. When I meant "full-range", I meant with a modulus of 2**36, not using the permissions to make it 2**36-1. The failure of add and subtract to behave properly is the main reason for using 2**36-1. >Comparison is a different matter. You need to do an unsigned/logical >comparison. I would hope that an unsigned/logical comparison would >not treat all-zeros and all-ones as the same value. If so, it is >pretty hard to do meaningful and-ing and or-ing. As I understand this, equality comparision is not a particular problem. However, magnitude comparison (">", ">=", "<=", "<") has to be accomplished using the subtract operation and checking the carry and zero flags afterwards. This will of course compare the all-one's and all-zero's pattern as the same. Of course, if nothing can ever produce the all-one's pattern, the issue is moot. What happens with that bit pattern if produced through an unchecked_conversion is irrelevant; the value is invalid. That means that the direct hardware OR, XOR, and NOT operations cannot be used, since they could produce the all-ones value. That is OK, as that is in fact what would naturally happen with such a modulus (and they do not have the overflow problems that add and subtract have with large modulii). We would only have to special case Add and Subtract in generics. I've ignored multiply, for the simple reason that no one yet has been able to tell me exactly what it would do. Once we've decided on a model, I'll revisit that. **************************************************************** !section 3.5.4(07) !subject One's complement modular type paper !reference RM95-3.5.4(07) !reference AI95-00095 !from Bob Duff !reference 96-5716.a Robert A Duff 96-10-3>> !discussion I'm forwarding this on behalf of Randy Brukardt. - Bob ---------------- Bob and Ben: Here is the draft of the one's complement math paper. Please comment ASAP, as I know time is short before the meeting. Bob, you can post this on Ada comment if you think it is OK; or I'll be happy to do it Monday. If you have any questions, please ask. Randy Brukardt. --------------------- Revised comments on AI-95 - One's complement modular types. I've gotten a lot more information of the problems of one's complement modular types. The result is that more problems with the standard have turned up. I'll start with a summary of our recommendations, then discuss all of the issues. Finally, I've attached a detailed summary of the behavior of the U2200 machine and code generators, synthesized from a series of E-Mail notes from Ben Hackner at Unisys. I've trimmed the E-Mail to eliminate redunancies, Unisys proprietary information, discussion of compiler bugs, and irrelevant chatter. I am (not Ben) responsible for any errors therin. Summary: Should the modulus of the full word modular type on a N bit one's complement machine be 2**N or 2**N-1? (2**N-1) If the above answer is 2**N-1, Does that imply that MAX_NONBINARY_MODULUS has to be 2**N-1? (No) Can arithmetic operations produce the so-called negative 0 (the all one's) value? (No - really don't care) Can logical operations produce the negative 0 value? (Yes) Should "not" for the full-word type use the hardware operation, rather than the definition in 4.5.6(5)? (Yes) "-" and "not" are defined by the standard to produce results differing by 1. This is natural for 2's complement. However, for 1's complement, these return the same value. Should these operations follow the hardware or the standard definition? (The standard, except for full word types, which ought to follow the hardware operation) Discussion: The discussion of one's complement modular types in the standard is rather confused. Rather than starting from that, we'll motivate the permissions from the actual requirements on a real 1's complement machine, the Unisys 2200 series. The 2200 uses 36 bit, 1's complement math. (No, this discussion is not academic; we're currently building an Ada 95 compiler for the 2200 platform.) Most of the interesting cases appear for the full word modular type. Types with smaller modulii are less interesting, so we will concentrate on the full word type. (Note that we assume that the full word type is intended to be supported by the standard, although its strict wording would practically prevent that on a one's complement machine. It would be easy, but not useful to users, to simply say that the full word type is not supported at all.) The first thing that must be decided is whether the modulus for the full word type is 2**36 or 2**36-1. The 2200's addition and subtraction instructions cannot produce the -0 value (indeed, adding zero is how 2200 code eliminates -0 results from other instructions). This means that the largest value if the modulus is 2**36 cannot be produced by the hardware instructions. Obviously, this cannot be the case, so 2**36-1 must be chosen. Now, once the modulus of 2**36-1 is chosen, the standard says that Max_NonBinary_Modulus has to have the value 2**36-1. Of course, modulii like 2**36-2 would then have to be supported, and this would be difficult. The reason that Max_Binary_Modulus and Max_NonBinary_Modulus are different is to avoid the implementation burden of large nonbinary modulii on the (2's complement) compiler implementor. It would be unfair, at least, to require that burden on implementors whose hardware happens to be 1's complement. Therefore, 1's complement machines should have a permission to support (one?) value(s) greater than Max_NonBinary_Modulus for the purpose of supporting the full word type. We have chosen Max_Binary_Modulus := 2**35, and Max_Nonbinary_Modulus := 2**35-1. Note that 13.7(24) and 13.7(25) can be read to support this intepretation (they do not appear to prohibit larger modulus values). However, 3.5.4(7) does prohibit it, so this change requires a binding intrepretation. Now that we've chosen a modulus of 2**36-1 (and asked for permission to actually use that value), we can turn to the effects of the operations on the type. What we'd like to have is that the operations closely mimic the hardware operations of the target, and even more importantly, mimic the similar operation's in the machine's C compiler. We've already discussed "+" and "-". "*" also generates a result without the -0 value. "/","Rem", and "Mod" always generate values smaller than their dividend, so they cannot produce a 2**36-1 result (which would be represented as -0). The actual divide instruction can produce -0, but this can easily be eliminated. "-" and "not" generate the same hardware instruction for signed integers on a one's complement machine. However, the definitions of these operators in the standard (4.5.6(5) and 4.5.4(3) (a note, no less!)) prevent them from having the same value. For less than full word types, this has no real effect -- indeed, there is no run-time advantage to the 1's complement version of "-" compared to the 4.5.4(3) definition. We do not believe there is any advantage to ignoring 4.5.4(3) for the 2200. For a full word type, however, we must be careful. The load negative instruction easily generates -0 from a zero value. This must be eliminated (since it is an incorrect result). Comparisons also pose no special problems. If presented a -0 (all ones) value, they produce a sensible result. Equality does not treat 0 and -0 as the same, and ordering comparisons use the carry flag, so they also produce the correct result for -0 operands. So far, the operations haven't presented any real problem. However, the logical operations do provide problems. The easiest case is And; if the the operands aren't -0, then the result cannot be either. For Or and Xor, however, the instructions can produce the -0 (all ones value) with any number of combinations of operands. It is easy to eliminate the -0 produced, and generate the correct answer for the modulus of 2**36-1. However, this would not be a useful result for the full word type. Since the machine operations can produce the -0 (all ones value), and this can be useful, they should be allowed to manipulate them. The C compiler for the 2200 does indeed allow using logical operations on the full word. The permission given in 3.5.4(27) can be useful here, if it was clear exactly what it meant. The first time I asked the question, Tucker responded with an answer which essentially stated that no operation could produce the -0 (all ones) value. That is not helpful to the user of the 2200 machine, who will want to access ALL of the bits of their values, in ANY combination. Intrepreting 3.5.4(27) is easy compared to the last problem: "Not" has altogether the wrong definition for a full word 1's complement type. Since the modulus of the full word type is 2**36-1, "not" is defined as 2**36-2 - X, which provides the wrong answer. Obviously, we would want to use the hardware operation for the "not". As with "-", "not" X could produce the -0 (all ones) value, but unlike "-", we would want to produce that as a result -- both for compatibility with other languages, and for predictability (it is what the user would expect). Therefore, we recommend that the permission of 3.5.4(27) be intrepreted to provide for logical operations which return values with a "logical modulus" of 'Modulus + 1. This would provide the arithmetic and logical operations that the user is expecting, without unduly comprimising the standard. ---------------------------------------------------------------- From: Ben Hackner, Unisys Date: 8/21/96 Notes on unsigned behavior on the U2200. Comparisons using mod 2**36-1: Notes on eliminating negative zero. According to Mark: For UAda, we eliminated -0 for the *, /, and unary -. Then we didn't have to worry about -0 and +0 on the comparisons. But for SX Ada 95, for signed, we don't eliminate -0 for *, /, and unary -. Then we have to make sure the compares test -0 and +0 as equal. The code for signed integer compare for SX Ada 95: b1 := i1=i2; L (load) AN (add negative) JZ (jump zero - where +0 and =0 are the same for this instruction) Similarly, the code in an IF for signed integer compare for SX Ada 95: if i1 = i2 L AN JNZ (jump not zero - again +0 and -0 are the same for this instruction) The code that is generated for unsigned integer for SX Ada 95: b1 := i1 = i2; L TE (test equal, where +0 is not equal to -0). The unsigned skeletons for C (that we are using for SX Ada 95) seem to assume that the illegal value of all one bits (-0) will not be stored to a variable. -0 can arise from: - 0 * negative number (which could, of course, be a large positive number) - 0 / negative number - unary minus - OR - XOR The UAda skeletons for multiply, divide, and unary minus all added 0 for signed integer. I think to be safe, we may have to eliminate -0 for certain cases for unsigned. (This is discussed below.) Otherwise, the comparisons won't always work. * * * * * Add with mod 2**36-1 Add instruction (can't generate -0). Subtract with mod 2**36-1 Subtract instruction (can't generate -0). Multiply with mod 2**36-1 Multiply instruction (single * single -> single), with an add of zero to eliminate -0. Apparently the add of zero (after the single precision multiply instruction MSI; the add eliminates -0) comes from the C skeleton for unsigned. So multiply seems to be OK for this case. * * * * * Divide with mod 2**36-1. Divide instruction (double via a shift / single -> single). There is no add of zero in the skeleton, after the divide. We need such an add of zero, in order that 0 / Large_Value does not produce a -0. I suppose I should change the skeletons in the back-end (like for UAda, I believe). * * * * * Unary minus with mod 2**36-1 We originally generated a load negative instruction for this. This generates a -0 output (illegal unsigned value, of course) for 0 input. We now are generating: temp := X; if temp /= 0 then temp := -temp; end if; Y := temp; which avoids the -0 (at the cost of a couple extra instructions). * * * * * AND mod 2**36-1, mod 7, and mod 16 AND instruction. -0 is not possible from And (unless one of the operands was -0). v2 or v3: OR instruction. No add of zero. I think we decided that it is necessary. However, the user is doing the bitwise operation, and I have got opinions from people here that we should NOT add zero to eliminate -0. (I.e., since it is a bitwise operation, leave the bits as is.) No checks. * * * * * OR & XOR with mod 2**36-1 OR (or XOR) instruction. No add of zero. These can generate a -0 from operands which are not -0. I have had discussions with people here in Roseville on our problems with OR and XOR possibly returning -0. We decided that it doesn't make much sense to flip -0 to +0, since the user is probably looking at the result as a mask, with individual T/F bits. Flipping all of the True bits to False would not work in this case, and the user's logic would fall apart. Of course, -0 is an illegal value, unless we change the permissions to allow the extra value. If there is no permission for the extra value, -0 has to be eliminated by adding zero. * * * * * NOT with mod 2**36-1 Load negative instruction. The load negative can generate a -0. There is no add of zero. If we decide that there is no permission for the extra value, we must either test for a zero input (in text), or change the skeleton to add zero (in the back-end). (Randy's note: "Not" and unary "-" generate the same instruction, which is of course correct on a one's complement machine.) * * * * * ">" with mod 2**36-1 Our generated code does the following: b1 := v1 > v2; L A5,v2 . load v2 L,U A0,1 . load True ANA A5,v1 . subtract v1 from v2 JNC $+2 . skip next instruction if no carry L,U A0,0 . load False So if there is no carry on v2 + (-v1) in the hardware, False is returned. Note that there is no test equal (where +0 /= -0). Also, note the use of the carry operation instead of the test greater in the hardware (where negative numbers are of course less than positive numbers). Examples: v1 := 0; v2 := 2**36-2; -- octal 777 777 777 775 v2 + (-v1) = 777 777 777 775 + 777 777 777 777, which of course has a carry. So False is returned. v1 := 0; v2 := (-0); -- octal 777 777 777 777 -> say that somehow we got all one bits (illegal value) v2 + (-v1) = 777 777 777 777 + 777 777 777 777, which has a carry, so False is returned. v1 := (-0); v2 := 0; v2 + (-v1) = 0 + 0, which has no carry, so True is returned. * * * * * Addition with mod 7 type m2 is mod 7; q1, q2, q3: m2; q1 := q2 + q3; The code that gets generated looks like the following: temp := q2 + q3; if temp >= 7 then temp := temp - 7; end if; q1 := Range_Check(temp); (Randy's note: the Range_Check would be eliminated if checking optimizations are on.) * * * * * Subtraction with mod 7 For mod 7 subtract q2-q3, the text/code is: * Subtract to get intermediate result (to determine if q2>=q3). * If q2 >= q3 (i.e., no borrow on subtract, i.e., carry bit set), result is q2-q3. * If q2 < q3 (i.e., borrow on subtract, i.e., carry bit not set), result is 7-(q3-q2). * * * * * OR & XOR with mod 7 The code is similar to addition, above. * * * * * REM for mod 2**36-1 and mod 7 Mod_Opr: The code is a divide (DI), with the remainder as the result. * * * * * MOD for mod 2**36-1 and mod 7 Modulo_Opr: q2 mod q3. The code is a divide. If the remainder is 0, return 0. If the result is positive, return the remainder. If the result is negative, return remainder + q3. * * * * * Mod 16 tests follow q2+q3 Result: (q2+q3) AND 15. * * * * * q2-q3 Result: (q2-q3) AND 15. * * * * * q2*q3 Result: ((q2*q3) + 0) AND 15. The add of zero is the standard elimination of -0 inside the multiply skeleton. * * * * * q2/q3 Result: q2/q3. No add of zero. No AND. * * * * * -q2 Result: (16-q2). (Randy's note: Note that this is cheaper than some sort of mask. Also note this does not work out the same as a one's complement "-", which is the same as "not". 4.5.4(3) implies this is correct.) * * * * * q2=q3 TE (test equal) instruction. No checks for +0 or -0. * * * * * q2 AND q3 Result: q2 AND q3. * * * * * q2 OR q3 Result: (q2 OR q3) AND 15. * * * * * q2 XOR q3 Result: (q2 XOR q3) AND 15. * * * * * NOT q2 Result: 15 - q2. * * * * * q2 REM q3 Result: Remainder of the divide q2/q3. * * * * * q2 MOD q3 Result: Modulo_Opr described above. The code is a divide. If the remainder is 0, return 0. If the result is positive, return the remainder. If the result is negative, return remainder + q3. * * * * * One weird thing I ran across is section 4.5.1(5) in the standard. It almost seems to be saying that the result of a logical operation is zero or one. (I assume they mean that you do a bit by bit operation on zero or one bits, and that the result is any possible unsigned value in the range.) Can you clarify this paragraph? **************************************************************** !section 3.5.4(07) !subject One's complement modular type paper !reference RM95-3.5.4(07) !reference AI95-00095 !from Bob Duff !reference 96-5716.a Robert A Duff 96-10-3>> !discussion I'm forwarding this on behalf of Randy Brukardt. - Bob ---------------- Bob and Ben: Here is the draft of the one's complement math paper. Please comment ASAP, as I know time is short before the meeting. Bob, you can post this on Ada comment if you think it is OK; or I'll be happy to do it Monday. If you have any questions, please ask. Randy Brukardt. --------------------- Revised comments on AI-95 - One's complement modular types. I've gotten a lot more information of the problems of one's complement modular types. The result is that more problems with the standard have turned up. I'll start with a summary of our recommendations, then discuss all of the issues. Finally, I've attached a detailed summary of the behavior of the U2200 machine and code generators, synthesized from a series of E-Mail notes from Ben Hackner at Unisys. I've trimmed the E-Mail to eliminate redunancies, Unisys proprietary information, discussion of compiler bugs, and irrelevant chatter. I am (not Ben) responsible for any errors therin. Summary: Should the modulus of the full word modular type on a N bit one's complement machine be 2**N or 2**N-1? (2**N-1) If the above answer is 2**N-1, Does that imply that MAX_NONBINARY_MODULUS has to be 2**N-1? (No) Can arithmetic operations produce the so-called negative 0 (the all one's) value? (No - really don't care) Can logical operations produce the negative 0 value? (Yes) Should "not" for the full-word type use the hardware operation, rather than the definition in 4.5.6(5)? (Yes) "-" and "not" are defined by the standard to produce results differing by 1. This is natural for 2's complement. However, for 1's complement, these return the same value. Should these operations follow the hardware or the standard definition? (The standard, except for full word types, which ought to follow the hardware operation) Discussion: The discussion of one's complement modular types in the standard is rather confused. Rather than starting from that, we'll motivate the permissions from the actual requirements on a real 1's complement machine, the Unisys 2200 series. The 2200 uses 36 bit, 1's complement math. (No, this discussion is not academic; we're currently building an Ada 95 compiler for the 2200 platform.) Most of the interesting cases appear for the full word modular type. Types with smaller modulii are less interesting, so we will concentrate on the full word type. (Note that we assume that the full word type is intended to be supported by the standard, although its strict wording would practically prevent that on a one's complement machine. It would be easy, but not useful to users, to simply say that the full word type is not supported at all.) The first thing that must be decided is whether the modulus for the full word type is 2**36 or 2**36-1. The 2200's addition and subtraction instructions cannot produce the -0 value (indeed, adding zero is how 2200 code eliminates -0 results from other instructions). This means that the largest value if the modulus is 2**36 cannot be produced by the hardware instructions. Obviously, this cannot be the case, so 2**36-1 must be chosen. Now, once the modulus of 2**36-1 is chosen, the standard says that Max_NonBinary_Modulus has to have the value 2**36-1. Of course, modulii like 2**36-2 would then have to be supported, and this would be difficult. The reason that Max_Binary_Modulus and Max_NonBinary_Modulus are different is to avoid the implementation burden of large nonbinary modulii on the (2's complement) compiler implementor. It would be unfair, at least, to require that burden on implementors whose hardware happens to be 1's complement. Therefore, 1's complement machines should have a permission to support (one?) value(s) greater than Max_NonBinary_Modulus for the purpose of supporting the full word type. We have chosen Max_Binary_Modulus := 2**35, and Max_Nonbinary_Modulus := 2**35-1. Note that 13.7(24) and 13.7(25) can be read to support this intepretation (they do not appear to prohibit larger modulus values). However, 3.5.4(7) does prohibit it, so this change requires a binding intrepretation. Now that we've chosen a modulus of 2**36-1 (and asked for permission to actually use that value), we can turn to the effects of the operations on the type. What we'd like to have is that the operations closely mimic the hardware operations of the target, and even more importantly, mimic the similar operation's in the machine's C compiler. We've already discussed "+" and "-". "*" also generates a result without the -0 value. "/","Rem", and "Mod" always generate values smaller than their dividend, so they cannot produce a 2**36-1 result (which would be represented as -0). The actual divide instruction can produce -0, but this can easily be eliminated. "-" and "not" generate the same hardware instruction for signed integers on a one's complement machine. However, the definitions of these operators in the standard (4.5.6(5) and 4.5.4(3) (a note, no less!)) prevent them from having the same value. For less than full word types, this has no real effect -- indeed, there is no run-time advantage to the 1's complement version of "-" compared to the 4.5.4(3) definition. We do not believe there is any advantage to ignoring 4.5.4(3) for the 2200. For a full word type, however, we must be careful. The load negative instruction easily generates -0 from a zero value. This must be eliminated (since it is an incorrect result). Comparisons also pose no special problems. If presented a -0 (all ones) value, they produce a sensible result. Equality does not treat 0 and -0 as the same, and ordering comparisons use the carry flag, so they also produce the correct result for -0 operands. So far, the operations haven't presented any real problem. However, the logical operations do provide problems. The easiest case is And; if the the operands aren't -0, then the result cannot be either. For Or and Xor, however, the instructions can produce the -0 (all ones value) with any number of combinations of operands. It is easy to eliminate the -0 produced, and generate the correct answer for the modulus of 2**36-1. However, this would not be a useful result for the full word type. Since the machine operations can produce the -0 (all ones value), and this can be useful, they should be allowed to manipulate them. The C compiler for the 2200 does indeed allow using logical operations on the full word. The permission given in 3.5.4(27) can be useful here, if it was clear exactly what it meant. The first time I asked the question, Tucker responded with an answer which essentially stated that no operation could produce the -0 (all ones) value. That is not helpful to the user of the 2200 machine, who will want to access ALL of the bits of their values, in ANY combination. Intrepreting 3.5.4(27) is easy compared to the last problem: "Not" has altogether the wrong definition for a full word 1's complement type. Since the modulus of the full word type is 2**36-1, "not" is defined as 2**36-2 - X, which provides the wrong answer. Obviously, we would want to use the hardware operation for the "not". As with "-", "not" X could produce the -0 (all ones) value, but unlike "-", we would want to produce that as a result -- both for compatibility with other languages, and for predictability (it is what the user would expect). Therefore, we recommend that the permission of 3.5.4(27) be intrepreted to provide for logical operations which return values with a "logical modulus" of 'Modulus + 1. This would provide the arithmetic and logical operations that the user is expecting, without unduly comprimising the standard. ---------------------------------------------------------------- From: Ben Hackner, Unisys Date: 8/21/96 Notes on unsigned behavior on the U2200. Comparisons using mod 2**36-1: Notes on eliminating negative zero. According to Mark: For UAda, we eliminated -0 for the *, /, and unary -. Then we didn't have to worry about -0 and +0 on the comparisons. But for SX Ada 95, for signed, we don't eliminate -0 for *, /, and unary -. Then we have to make sure the compares test -0 and +0 as equal. The code for signed integer compare for SX Ada 95: b1 := i1=i2; L (load) AN (add negative) JZ (jump zero - where +0 and =0 are the same for this instruction) Similarly, the code in an IF for signed integer compare for SX Ada 95: if i1 = i2 L AN JNZ (jump not zero - again +0 and -0 are the same for this instruction) The code that is generated for unsigned integer for SX Ada 95: b1 := i1 = i2; L TE (test equal, where +0 is not equal to -0). The unsigned skeletons for C (that we are using for SX Ada 95) seem to assume that the illegal value of all one bits (-0) will not be stored to a variable. -0 can arise from: - 0 * negative number (which could, of course, be a large positive number) - 0 / negative number - unary minus - OR - XOR The UAda skeletons for multiply, divide, and unary minus all added 0 for signed integer. I think to be safe, we may have to eliminate -0 for certain cases for unsigned. (This is discussed below.) Otherwise, the comparisons won't always work. * * * * * Add with mod 2**36-1 Add instruction (can't generate -0). Subtract with mod 2**36-1 Subtract instruction (can't generate -0). Multiply with mod 2**36-1 Multiply instruction (single * single -> single), with an add of zero to eliminate -0. Apparently the add of zero (after the single precision multiply instruction MSI; the add eliminates -0) comes from the C skeleton for unsigned. So multiply seems to be OK for this case. * * * * * Divide with mod 2**36-1. Divide instruction (double via a shift / single -> single). There is no add of zero in the skeleton, after the divide. We need such an add of zero, in order that 0 / Large_Value does not produce a -0. I suppose I should change the skeletons in the back-end (like for UAda, I believe). * * * * * Unary minus with mod 2**36-1 We originally generated a load negative instruction for this. This generates a -0 output (illegal unsigned value, of course) for 0 input. We now are generating: temp := X; if temp /= 0 then temp := -temp; end if; Y := temp; which avoids the -0 (at the cost of a couple extra instructions). * * * * * AND mod 2**36-1, mod 7, and mod 16 AND instruction. -0 is not possible from And (unless one of the operands was -0). v2 or v3: OR instruction. No add of zero. I think we decided that it is necessary. However, the user is doing the bitwise operation, and I have got opinions from people here that we should NOT add zero to eliminate -0. (I.e., since it is a bitwise operation, leave the bits as is.) No checks. * * * * * OR & XOR with mod 2**36-1 OR (or XOR) instruction. No add of zero. These can generate a -0 from operands which are not -0. I have had discussions with people here in Roseville on our problems with OR and XOR possibly returning -0. We decided that it doesn't make much sense to flip -0 to +0, since the user is probably looking at the result as a mask, with individual T/F bits. Flipping all of the True bits to False would not work in this case, and the user's logic would fall apart. Of course, -0 is an illegal value, unless we change the permissions to allow the extra value. If there is no permission for the extra value, -0 has to be eliminated by adding zero. * * * * * NOT with mod 2**36-1 Load negative instruction. The load negative can generate a -0. There is no add of zero. If we decide that there is no permission for the extra value, we must either test for a zero input (in text), or change the skeleton to add zero (in the back-end). (Randy's note: "Not" and unary "-" generate the same instruction, which is of course correct on a one's complement machine.) * * * * * ">" with mod 2**36-1 Our generated code does the following: b1 := v1 > v2; L A5,v2 . load v2 L,U A0,1 . load True ANA A5,v1 . subtract v1 from v2 JNC $+2 . skip next instruction if no carry L,U A0,0 . load False So if there is no carry on v2 + (-v1) in the hardware, False is returned. Note that there is no test equal (where +0 /= -0). Also, note the use of the carry operation instead of the test greater in the hardware (where negative numbers are of course less than positive numbers). Examples: v1 := 0; v2 := 2**36-2; -- octal 777 777 777 775 v2 + (-v1) = 777 777 777 775 + 777 777 777 777, which of course has a carry. So False is returned. v1 := 0; v2 := (-0); -- octal 777 777 777 777 -> say that somehow we got all one bits (illegal value) v2 + (-v1) = 777 777 777 777 + 777 777 777 777, which has a carry, so False is returned. v1 := (-0); v2 := 0; v2 + (-v1) = 0 + 0, which has no carry, so True is returned. * * * * * Addition with mod 7 type m2 is mod 7; q1, q2, q3: m2; q1 := q2 + q3; The code that gets generated looks like the following: temp := q2 + q3; if temp >= 7 then temp := temp - 7; end if; q1 := Range_Check(temp); (Randy's note: the Range_Check would be eliminated if checking optimizations are on.) * * * * * Subtraction with mod 7 For mod 7 subtract q2-q3, the text/code is: * Subtract to get intermediate result (to determine if q2>=q3). * If q2 >= q3 (i.e., no borrow on subtract, i.e., carry bit set), result is q2-q3. * If q2 < q3 (i.e., borrow on subtract, i.e., carry bit not set), result is 7-(q3-q2). * * * * * OR & XOR with mod 7 The code is similar to addition, above. * * * * * REM for mod 2**36-1 and mod 7 Mod_Opr: The code is a divide (DI), with the remainder as the result. * * * * * MOD for mod 2**36-1 and mod 7 Modulo_Opr: q2 mod q3. The code is a divide. If the remainder is 0, return 0. If the result is positive, return the remainder. If the result is negative, return remainder + q3. * * * * * Mod 16 tests follow q2+q3 Result: (q2+q3) AND 15. * * * * * q2-q3 Result: (q2-q3) AND 15. * * * * * q2*q3 Result: ((q2*q3) + 0) AND 15. The add of zero is the standard elimination of -0 inside the multiply skeleton. * * * * * q2/q3 Result: q2/q3. No add of zero. No AND. * * * * * -q2 Result: (16-q2). (Randy's note: Note that this is cheaper than some sort of mask. Also note this does not work out the same as a one's complement "-", which is the same as "not". 4.5.4(3) implies this is correct.) * * * * * q2=q3 TE (test equal) instruction. No checks for +0 or -0. * * * * * q2 AND q3 Result: q2 AND q3. * * * * * q2 OR q3 Result: (q2 OR q3) AND 15. * * * * * q2 XOR q3 Result: (q2 XOR q3) AND 15. * * * * * NOT q2 Result: 15 - q2. * * * * * q2 REM q3 Result: Remainder of the divide q2/q3. * * * * * q2 MOD q3 Result: Modulo_Opr described above. The code is a divide. If the remainder is 0, return 0. If the result is positive, return the remainder. If the result is negative, return remainder + q3. * * * * * One weird thing I ran across is section 4.5.1(5) in the standard. It almost seems to be saying that the result of a logical operation is zero or one. (I assume they mean that you do a bit by bit operation on zero or one bits, and that the result is any possible unsigned value in the range.) Can you clarify this paragraph? ****************************************************************