!standard RM-3.5.4 (07) 99-08-31 AI95-00095/03
!standard RM-3.5.4 (27)
!class ramification 95-09-29
!status Corrigendum 2000 99-05-25
!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
!qualifier Clarification
!subject Modular types on one's complement machines.
!summary
Implementation Permission: On a one's complement machine, the
implementation may support non-binary modulii above
System.Max_Nonbinary_Modulus.
!question
How should an implementation on a one's complement machine implement
modular types intended to use all the bits of a full word?
!response
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.
!corrigendum 3.05.04(27)
@dinsa
For a one's complement machine, the high bound of the base range of a
modular type whose modulus is one less than a power of 2 may be equal to the
modulus, rather than one less than the modulus. It is implementation defined
for which powers of 2, if any, this permission is exercised.
@dinst
For a one's complement machine, modulus values which are not powers of
2 greater than System.Max_Nonbinary_Modulus may be allowed. It is
implementation defined which values greater than System.Max_Nonbinary_Modulus,
if any, are allowed.
!ACATS test
The implementation permissions are not testable, as there is no way to determine
the value involved. In addition, most machines are 2's complement, so any tests
would be of little value.
!appendix
!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?
****************************************************************