Reducing opcode permutations

[Sandro Magi-2]

I'm currently writing a C library around Lightning so I can use it in
an FFI, but defining all of the permutations for type x operation x
register or immediate is cumbersome.

I have a way to reduce the permutations, but I'm not sure whether the
underlying assumption is sound, so hopefully someone here can clarify.
The idea is basically that any register-register operations don't need
a type qualifier. This assumption seemed sound for integer operations,
but floating point makes me pause; single vs double floating point may
actually involve different instructions. Now I'm not sure about
integer ops either.

The idea is:

addr_c
addr_uc
addr_i
addr_ui
addr_l
addr_ul
addr_p

Would all be collapsed down to simply: addr, since addr is a
register-register operation, the actual widths shouldn't really
matter. The widths only matter when we're writing to the register from
memory, or reading from the register to memory. This the applies to
all the other register-register instructions which significantly
reduces the permutations needed.

Is this assumption sound?

Sandro


_______________________________________________
Lightning mailing list
Lightning@...
http://lists.gnu.org/mailman/listinfo/lightning

[Paolo Bonzini-2]

> addr_c
> addr_uc
> addr_i
> addr_ui
> addr_l
> addr_ul
> addr_p
>
> Would all be collapsed down to simply: addr, since addr is a
> register-register operation

I don't think I have that many redundant operations in lightning; search
for "synonyms" in the porting manual, there are very few unnecessary
_c/_uc/_s/_us operations.  For example, I included all cases for
load/store operations, but adds only work at the word level.  _l/_ul are
always included for portability to 64-bit systems, _p is too and
sometimes provides additional support for patching forward references.

Paolo


_______________________________________________
Lightning mailing list
Lightning@...
http://lists.gnu.org/mailman/listinfo/lightning

[Sandro Magi-2]

On Wed, Mar 26, 2008 at 2:46 AM, Paolo Bonzini <bonzini@...> wrote:

>
>  > addr_c
>  > addr_uc
>  > addr_i
>  > addr_ui
>  > addr_l
>  > addr_ul
>  > addr_p
>  >
>  > Would all be collapsed down to simply: addr, since addr is a
>  > register-register operation
>
>  I don't think I have that many redundant operations in lightning; search
>  for "synonyms" in the porting manual, there are very few unnecessary
>  _c/_uc/_s/_us operations.

Sorry, tiredness and assembly-level reasoning don't go well together. :-)

I'm looking at a "Synonyms" section now, and it says this:

  For example, adding two unsigned integers is exactly the same as
  adding two signed integers (assuming a two's complement
  representation of negative numbers); yet, gnu lightning provides
  both jit_addr_i and jit_addr_ui macros.

Two points:

1. This is the type of duplication I'd like to avoid, as it adds
unnecessary bloat to the C library (and to my cramped fingers!). This
isn't a problem for Lightning because macros have no runtime footprint
for unused instructions. The "Synonyms—don't define them" section is
quite long.

2. Something doesn't seem right about the above description. For
instance, a signed 32-bit number overflows at 2^31, not 2^32, so
addc_i and addc_ui should have different semantics. Also, 64-bit
systems which define a 32-bit int, but a 64-bit long int, similarly
overflow at different values for addc. Is this the actual behaviour?

The approach I was taking was to make 'register' its own type, with
its own operations (or perhaps a 'word' type). The _c/_uc/_i/... only
have immediate forms, and the register forms which take only register
arguments are appended with _r. So to keep things portable:

typedef unsigned ireg_t; //register number

// modular addition
// a0 = a1 + i
void sadd_i(ireg_t a0, ireg_t a1, int i); //signed
void sadd_l(ireg_t a0, ireg_t a1, long i);
void uadd_ui(ireg_t a0, ireg_t a1, uint i); //unsigned
void uadd_ul(ireg_t a0, ireg_t a1, ulong i);

// modular addition
// a0 = a1 + a2
void sadd_r(ireg_t a0, ireg_t a1, ireg_t a2); //overflow at 2^(word_size-1)
void uadd_r(ireg_t a0, ireg_t a1, ireg_t a2); //overflow at 2^word_size

Signed and unsigned forms handle the different overflow boundaries.
This eliminates all register-register operations on types smaller than
a register/word size. I was wondering whether these operations
actually perform overflow checking on the smaller types though, as
that negates my whole assumption.

>  For example, I included all cases for
>  load/store operations, but adds only work at the word level.

Are you saying load always fetches a full word, then &'s the register
with a bitmask for the appropriate type?

>  _l/_ul are
>  always included for portability to 64-bit systems, _p is too and
>  sometimes provides additional support for patching forward references.

Haven't gotten that far yet, but I do maintain a distinct 'pointer'
type with only its specific immediate operations. Again,
register-register operations are removed.

Sandro


_______________________________________________
Lightning mailing list
Lightning@...
http://lists.gnu.org/mailman/listinfo/lightning

[Sandro Magi-2]

On Wed, Mar 26, 2008 at 10:07 AM, Sandro Magi <naasking@...> wrote:

>  I'm looking at a "Synonyms" section now, and it says this:
>
>   For example, adding two unsigned integers is exactly the same as
>   adding two signed integers (assuming a two's complement
>   representation of negative numbers); yet, gnu lightning provides
>   both jit_addr_i and jit_addr_ui macros.
>
>  Two points:
>
>  1. This is the type of duplication I'd like to avoid, as it adds
>  unnecessary bloat to the C library (and to my cramped fingers!). This
>  isn't a problem for Lightning because macros have no runtime footprint
>  for unused instructions. The "Synonyms—don't define them" section is
>  quite long.
>
>  2. Something doesn't seem right about the above description. For
>  instance, a signed 32-bit number overflows at 2^31, not 2^32, so
>  addc_i and addc_ui should have different semantics. Also, 64-bit
>  systems which define a 32-bit int, but a 64-bit long int, similarly
>  overflow at different values for addc. Is this the actual behaviour?

From my reading, the x86 'add' instruction provides overflow modes for
8/16/32 signed and unsigned integers [1]. Unless I'm reading it wrong,
PowerPC doesn't have the same semantics [2]. Given this instruction
sequence:

// assumptions: 1. we're working on a 32-bit machine, 2. int is 32-bits
#include <limits.h>

jit_movi_i(JIT_R1, INT_MAX)     // R1 = 2^31
jit_addci_i(JIT_R0, JIT_R1, 1)   // R0 = R1 + 1, set carry
jit_addxi_i(JIT_R2, JIT_R0, 0)   // R2 = R0 + 0 + carry

So, does R2=1, or does R2=0? When using _ui, it should be 0. If it
were really signed arithmetic, it should be 1. How does Lightning
behave when this instruction sequence is executed on x86 and PPC?

Sandro

[1] http://flint.cs.yale.edu/cs421/papers/art-of-asm/pdf/CH06.PDF
[2] http://www-01.ibm.com/chips/techlib/techlib.nsf/techdocs/852569B20050FF778525699600719DF2/$file/6xx_pem.pdf


_______________________________________________
Lightning mailing list
Lightning@...
http://lists.gnu.org/mailman/listinfo/lightning

[Paolo Bonzini-2]

> jit_movi_i(JIT_R1, INT_MAX)     // R1 = 2^31
> jit_addci_i(JIT_R0, JIT_R1, 1)   // R0 = R1 + 1, set carry
> jit_addxi_i(JIT_R2, JIT_R0, 0)   // R2 = R0 + 0 + carry

Don't confuse carry with overflow.  Carry is the same for integer and
unsigned integer.  Overflow differs, but what tests overflow is
boadd/bosub, not addc/addx.

Paolo


_______________________________________________
Lightning mailing list
Lightning@...
http://lists.gnu.org/mailman/listinfo/lightning

[Sandro Magi-2]

On Fri, Mar 28, 2008 at 12:20 PM, Paolo Bonzini <bonzini@...> wrote:
>
>  > jit_movi_i(JIT_R1, INT_MAX)     // R1 = 2^31
>  > jit_addci_i(JIT_R0, JIT_R1, 1)   // R0 = R1 + 1, set carry
>  > jit_addxi_i(JIT_R2, JIT_R0, 0)   // R2 = R0 + 0 + carry
>
>  Don't confuse carry with overflow.  Carry is the same for integer and
>  unsigned integer.  Overflow differs, but what tests overflow is
>  boadd/bosub, not addc/addx.

Ah, my mistake. So a similar instruction sequence to the above using
boadd_i would branch to the overflow address, but if I were to use
boadd_ui it would not?

Sandro


_______________________________________________
Lightning mailing list
Lightning@...
http://lists.gnu.org/mailman/listinfo/lightning

[Paolo Bonzini-2]

Sandro Magi wrote:

> On Fri, Mar 28, 2008 at 12:20 PM, Paolo Bonzini <bonzini@...> wrote:
>>  > jit_movi_i(JIT_R1, INT_MAX)     // R1 = 2^31
>>  > jit_addci_i(JIT_R0, JIT_R1, 1)   // R0 = R1 + 1, set carry
>>  > jit_addxi_i(JIT_R2, JIT_R0, 0)   // R2 = R0 + 0 + carry
>>
>>  Don't confuse carry with overflow.  Carry is the same for integer and
>>  unsigned integer.  Overflow differs, but what tests overflow is
>>  boadd/bosub, not addc/addx.
>
> Ah, my mistake. So a similar instruction sequence to the above using
> boadd_i would branch to the overflow address, but if I were to use
> boadd_ui it would not?

Yep.

Paolo


_______________________________________________
Lightning mailing list
Lightning@...
http://lists.gnu.org/mailman/listinfo/lightning