Manejo del entero con valores> 2 ^ 32 en Sparc 32 bits

assembly long-integer

Question

Codifiqué un pequeño programa que mide el tiempo invertido en un bucle (a través de un fragmento de código de ensamblaje Sparc en línea).

Todo está bien hasta que establezca el número de iteraciones por encima de aproximadamente 4.0 + 9 (por encima de 2 ^ 32).

Aquí está el fragmento de código:

#include <stdio.h>
#include <sys/time.h>
#include <unistd.h>
#include <math.h>
#include <stdint.h>
int main (int argc, char *argv[])
{
// For indices
int i;
// Set the number of executions
int nRunning = atoi(argv[1]);
// Set the sums
double avgSum = 0.0;
double stdSum = 0.0;
// Average of execution time
double averageRuntime = 0.0;
// Standard deviation of execution time
double deviationRuntime = 0.0;
// Init sum
unsigned long long int sum = 0;
// Number of iterations
unsigned long long int nLoop = 4000000000ULL;
//uint64_t nLoop = 4000000000;
// DEBUG
printf("sizeof(unsigned long long int) = %zu/n",sizeof(unsigned long long int));
printf("sizeof(unsigned long int) = %zu/n",sizeof(unsigned long int));
// Time intervals
struct timeval tv1, tv2;
double diff;
// Loop for multiple executions
for (i=0; i<nRunning; i++)
{
// Start time
gettimeofday (&tv1, NULL);
// Loop with Sparc assembly into C source
asm volatile ("clr %%g1/n/t"
"clr %%g2/n/t"
"mov %1, %%g1/n" // %1 = input parameter
"loop:/n/t"
"add %%g2, 1, %%g2/n/t"
"subcc %%g1, 1, %%g1/n/t"
"bne loop/n/t"
"nop/n/t"
"mov %%g2, %0/n" // %0 = output parameter
: "=r" (sum) // output
: "r" (nLoop) // input
: "g1", "g2"); // clobbers
// End time
gettimeofday (&tv2, NULL);
// Compute runtime for loop
diff = (tv2.tv_sec - tv1.tv_sec) * 1000000ULL + (tv2.tv_usec - tv1.tv_usec);
// Summing diff time
avgSum += diff;
stdSum += (diff*diff);
// DEBUG
printf("diff = %e/n", diff);
printf("avgSum = %e/n", avgSum);
}
// Compute final averageRuntime
averageRuntime = avgSum/nRunning;
// Compute standard deviation
deviationRuntime = sqrt(stdSum/nRunning-averageRuntime*averageRuntime);
// Print results
printf("(Average Elapsed time, Standard deviation) = %e usec %e usec/n", averageRuntime, deviationRuntime);
// Print sum from assembly loop
printf("Sum = %llu/n", sum);

Por ejemplo, con nLoop <2 ^ 32, obtengo los valores correctos para diff , avgSum y stdSum . De hecho, el printf , con nLoop = 4.0e+9 , da:

sizeof(unsigned long long int) = 8
sizeof(unsigned long int) = 4
diff = 9.617167e+06
avgSum = 9.617167e+06
diff = 9.499878e+06
avgSum = 1.911704e+07
(Average Elapsed time, Standard deviation) = 9.558522e+06 usec 5.864450e+04 usec
Sum = 4000000000

El código se compila en Debian Sparc 32 bits Etch con gcc 4.1.2 .

Desafortunadamente, si tomo por ejemplo nLoop = 5.0e+9 , obtengo valores pequeños e incorrectos para los tiempos medidos; aquí está la salida de printf en este caso:

sizeof(unsigned long long int) = 8
sizeof(unsigned long int) = 4
diff = 5.800000e+01
avgSum = 5.800000e+01
diff = 4.000000e+00
avgSum = 6.200000e+01
(Average Elapsed time, Standard deviation) = 3.100000e+01 usec 2.700000e+01 usec
Sum = 5000000000

No sé de dónde podría venir el problema. He realizado otras pruebas usando uint64_t pero sin éxito.

Quizás el problema es que manejo large integers (> 2^32) con 32 bits OS o puede ser el código ensamblado en línea que no admite 8 bytes enteros.

Si alguien pudiera darme algunas pistas para corregir este error,

Saludos

ACTUALIZACIÓN 1 :

Siguiendo el consejo de @Andrew Henle , tomé el mismo código, pero en lugar del fragmento de ensamblaje Sparc en línea, acabo de poner un simple bucle.

Aquí está el programa con el bucle simple que tiene nLoop = 5.0e+9 (vea la línea " unsigned long long int nLoop = 5000000000ULL; ", entonces por encima del limit 2^32-1 :

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <unistd.h>
#include <math.h>
#include <stdint.h>
int main (int argc, char *argv[])
{
// For indices of nRunning
int i;
// For indices of nRunning
unsigned long long int j;
// Set the number of executions
int nRunning = atoi(argv[1]);
// Set the sums
unsigned long long int avgSum = 0;
unsigned long long int stdSum = 0;
// Average of execution time
double averageRuntime = 0.0;
// Standard deviation of execution time
double deviationRuntime = 0.0;
// Init sum
unsigned long long int sum;
// Number of iterations
unsigned long long int nLoop = 5000000000ULL;
// DEBUG
printf("sizeof(unsigned long long int) = %zu/n",sizeof(unsigned long long int));
printf("sizeof(unsigned long int) = %zu/n",sizeof(unsigned long int));
// Time intervals
struct timeval tv1, tv2;
unsigned long long int diff;
// Loop for multiple executions
for (i=0; i<nRunning; i++)
{
// Reset sum
sum = 0;
// Start time
gettimeofday (&tv1, NULL);
// Loop with Sparc assembly into C source
/* asm volatile ("clr %%g1/n/t"
"clr %%g2/n/t"
"mov %1, %%g1/n" // %1 = input parameter
"loop:/n/t"
"add %%g2, 1, %%g2/n/t"
"subcc %%g1, 1, %%g1/n/t"
"bne loop/n/t"
"nop/n/t"
"mov %%g2, %0/n" // %0 = output parameter
: "=r" (sum) // output
: "r" (nLoop) // input
: "g1", "g2"); // clobbers
*/
// Classic loop
for (j=0; j<nLoop; j++)
sum ++;
// End time
gettimeofday (&tv2, NULL);
// Compute runtime for loop
diff = (unsigned long long int) ((tv2.tv_sec - tv1.tv_sec) * 1000000 + (tv2.tv_usec - tv1.tv_usec));
// Summing diff time
avgSum += diff;
stdSum += (diff*diff);
// DEBUG
printf("diff = %llu/n", diff);
printf("avgSum = %llu/n", avgSum);
printf("stdSum = %llu/n", stdSum);
// Print sum from assembly loop
printf("Sum = %llu/n", sum);
}
// Compute final averageRuntime
averageRuntime = avgSum/nRunning;
// Compute standard deviation
deviationRuntime = sqrt(stdSum/nRunning-averageRuntime*averageRuntime);
// Print results
printf("(Average Elapsed time, Standard deviation) = %e usec %e usec/n", averageRuntime, deviationRuntime);
return 0;
}

Este fragmento de código funciona correctamente, es decir, la sum variable se imprime como (ver " printf("Sum = %llu/n", sum) ";):

Sum = 5000000000

Entonces, el problema proviene de la versión con el bloque de ensamblaje Sparc.

Sospecho, en este código de ensamblaje, la línea "mov %1, %%g1/n" // %1 = input parameter para almacenar nLoop en el %g1 register (creo que %g1 es un registro de 32 bits, por lo que puede no almacena valores por encima de 2^32-1 ).

Sin embargo, el parámetro de salida ( sum variable) en la línea:

"mov %%g2, %0/n" // %0 = output parameter

está por encima del límite ya que es igual a 5000000000.

Adjunto el vimdiff entre la versión con el ciclo de ensamblaje y sin él:

A la izquierda, programa con ensamblaje, a la derecha, sin ensamblaje (solo un simple lazo en su lugar)

Le recuerdo que mi problema es que, para nLoop> 2 ^ 32-1 y con asamblea, obtengo un parámetro de sum válido al final de la ejecución, pero no es válido (demasiado corto) el average y standard deviation tiempos de standard deviation (gastados en el ciclo); aquí hay un ejemplo de salida con nLoop = 5000000000ULL :

sizeof(unsigned long long int) = 8
sizeof(unsigned long int) = 4
diff = 17
avgSum = 17
stdSum = 289
Sum = 5000000000
diff = 4
avgSum = 21
stdSum = 305
Sum = 5000000000
(Average Elapsed time, Standard deviation) = 1.000000e+01 usec 7.211103e+00 usec

Con tomar nLoop = 4.0e+9 , es decir, nLoop = 4000000000ULL , no hay problema, los valores de tiempo son válidos.

ACTUALIZACIÓN 2:

Estoy buscando más profundamente al generar código de ensamblaje. La versión con nLoop = 4000000000 (4.0e+9) está debajo:

 .file "loop-WITH-asm-inline-4-Billions.c"
.section ".rodata"
.align 8
.LLC1:
.asciz "sizeof(unsigned long long int) = %zu/n"
.align 8
.LLC2:
.asciz "sizeof(unsigned long int) = %zu/n"
.align 8
.LLC3:
.asciz "diff = %llu/n"
.align 8
.LLC4:
.asciz "avgSum = %llu/n"
.align 8
.LLC5:
.asciz "stdSum = %llu/n"
.align 8
.LLC6:
.asciz "Sum = %llu/n"
.global __udivdi3
.global __cmpdi2
.global __floatdidf
.align 8
.LLC7:
.asciz "(Average Elapsed time, Standard deviation) = %e usec %e usec/n"
.align 8
.LLC0:
.long 0
.long 0
.section ".text"
.align 4
.global main
.type main, #function
.proc 04
main:
save %sp, -248, %sp
st %i0, [%fp+68]
st %i1, [%fp+72]
ld [%fp+72], %g1
add %g1, 4, %g1
ld [%g1], %g1
mov %g1, %o0
call atoi, 0
nop
mov %o0, %g1
st %g1, [%fp-68]
st %g0, [%fp-64]
st %g0, [%fp-60]
st %g0, [%fp-56]
st %g0, [%fp-52]
sethi %hi(.LLC0), %g1
or %g1, %lo(.LLC0), %g1
ldd [%g1], %f8
std %f8, [%fp-48]
sethi %hi(.LLC0), %g1
or %g1, %lo(.LLC0), %g1
ldd [%g1], %f8
std %f8, [%fp-40]
mov 0, %g2
sethi %hi(4000000000), %g3
std %g2, [%fp-24]
sethi %hi(.LLC1), %g1
or %g1, %lo(.LLC1), %o0
mov 8, %o1
call printf, 0
nop
sethi %hi(.LLC2), %g1
or %g1, %lo(.LLC2), %o0
mov 4, %o1
call printf, 0
nop
st %g0, [%fp-84]
b .LL2
nop
.LL3:
st %g0, [%fp-32]
st %g0, [%fp-28]
add %fp, -92, %g1
mov %g1, %o0
mov 0, %o1
call gettimeofday, 0
nop
ldd [%fp-24], %o4
clr %g1
clr %g2
mov %o4, %g1
loop:
add %g2, 1, %g2
subcc %g1, 1, %g1
bne loop
nop
mov %g2, %o4
std %o4, [%fp-32]
add %fp, -100, %g1
mov %g1, %o0
mov 0, %o1
call gettimeofday, 0
nop
ld [%fp-100], %g2
ld [%fp-92], %g1
sub %g2, %g1, %g2
sethi %hi(999424), %g1
or %g1, 576, %g1
smul %g2, %g1, %g3
ld [%fp-96], %g2
ld [%fp-88], %g1
sub %g2, %g1, %g1
add %g3, %g1, %g1
st %g1, [%fp-12]
sra %g1, 31, %g1
st %g1, [%fp-16]
ldd [%fp-64], %o4
ldd [%fp-16], %g2
addcc %o5, %g3, %g3
addx %o4, %g2, %g2
std %g2, [%fp-64]
ld [%fp-16], %g2
ld [%fp-12], %g1
smul %g2, %g1, %g4
ld [%fp-16], %g2
ld [%fp-12], %g1
smul %g2, %g1, %g1
add %g4, %g1, %g4
ld [%fp-12], %g2
ld [%fp-12], %g1
umul %g2, %g1, %g3
rd %y, %g2
add %g4, %g2, %g4
mov %g4, %g2
ldd [%fp-56], %o4
addcc %o5, %g3, %g3
addx %o4, %g2, %g2
std %g2, [%fp-56]
sethi %hi(.LLC3), %g1
or %g1, %lo(.LLC3), %o0
ld [%fp-16], %o1
ld [%fp-12], %o2
call printf, 0
nop
sethi %hi(.LLC4), %g1
or %g1, %lo(.LLC4), %o0
ld [%fp-64], %o1
ld [%fp-60], %o2
call printf, 0
nop
sethi %hi(.LLC5), %g1
or %g1, %lo(.LLC5), %o0
ld [%fp-56], %o1
ld [%fp-52], %o2
call printf, 0
nop
sethi %hi(.LLC6), %g1
or %g1, %lo(.LLC6), %o0
ld [%fp-32], %o1
ld [%fp-28], %o2
call printf, 0
nop
ld [%fp-84], %g1
add %g1, 1, %g1
st %g1, [%fp-84]
.LL2:
ld [%fp-84], %g2
ld [%fp-68], %g1
cmp %g2, %g1
bl .LL3
nop
ld [%fp-68], %g1
sra %g1, 31, %g1
ld [%fp-68], %g3
mov %g1, %g2
ldd [%fp-64], %o0
mov %g2, %o2
mov %g3, %o3
call __udivdi3, 0
nop
mov %o0, %g2
mov %o1, %g3
std %g2, [%fp-136]
ldd [%fp-136], %o0
mov 0, %o2
mov 0, %o3
call __cmpdi2, 0
nop
mov %o0, %g1
cmp %g1, 1
bl .LL6
nop
ldd [%fp-136], %o0
call __floatdidf, 0
nop
std %f0, [%fp-144]
b .LL5
nop
.LL6:
ldd [%fp-136], %o4
and %o4, 0, %g2
and %o5, 1, %g3
ld [%fp-136], %o5
sll %o5, 31, %g1
ld [%fp-132], %g4
srl %g4, 1, %o5
or %o5, %g1, %o5
ld [%fp-136], %g1
srl %g1, 1, %o4
or %g2, %o4, %g2
or %g3, %o5, %g3
mov %g2, %o0
mov %g3, %o1
call __floatdidf, 0
nop
std %f0, [%fp-144]
ldd [%fp-144], %f8
ldd [%fp-144], %f10
faddd %f8, %f10, %f8
std %f8, [%fp-144]
.LL5:
ldd [%fp-144], %f8
std %f8, [%fp-48]
ld [%fp-68], %g1
sra %g1, 31, %g1
ld [%fp-68], %g3
mov %g1, %g2
ldd [%fp-56], %o0
mov %g2, %o2
mov %g3, %o3
call __udivdi3, 0
nop
mov %o0, %g2
mov %o1, %g3
std %g2, [%fp-128]
ldd [%fp-128], %o0
mov 0, %o2
mov 0, %o3
call __cmpdi2, 0
nop
mov %o0, %g1
cmp %g1, 1
bl .LL8
nop
ldd [%fp-128], %o0
call __floatdidf, 0
nop
std %f0, [%fp-120]
b .LL7
nop
.LL8:
ldd [%fp-128], %o4
and %o4, 0, %g2
and %o5, 1, %g3
ld [%fp-128], %o5
sll %o5, 31, %g1
ld [%fp-124], %g4
srl %g4, 1, %o5
or %o5, %g1, %o5
ld [%fp-128], %g1
srl %g1, 1, %o4
or %g2, %o4, %g2
or %g3, %o5, %g3
mov %g2, %o0
mov %g3, %o1
call __floatdidf, 0
nop
std %f0, [%fp-120]
ldd [%fp-120], %f8
ldd [%fp-120], %f10
faddd %f8, %f10, %f8
std %f8, [%fp-120]
.LL7:
ldd [%fp-48], %f8
ldd [%fp-48], %f10
fmuld %f8, %f10, %f8
ldd [%fp-120], %f10
fsubd %f10, %f8, %f8
std %f8, [%fp-112]
ldd [%fp-112], %f8
fsqrtd %f8, %f8
std %f8, [%fp-152]
ldd [%fp-152], %f10
ldd [%fp-152], %f8
fcmpd %f10, %f8
nop
fbe .LL9
nop
ldd [%fp-112], %o0
call sqrt, 0
nop
std %f0, [%fp-152]
.LL9:
ldd [%fp-152], %f8
std %f8, [%fp-40]
sethi %hi(.LLC7), %g1
or %g1, %lo(.LLC7), %o0
ld [%fp-48], %o1
ld [%fp-44], %o2
ld [%fp-40], %o3
ld [%fp-36], %o4
call printf, 0
nop
mov 0, %g1
mov %g1, %i0
restore
jmp %o7+8
nop
.size main, .-main
.ident "GCC: (GNU) 4.1.2 20061115 (prerelease) (Debian 4.1.1-21)"
.section ".note.GNU-stack"

Cuando genero la versión de código de ensamblado con nLoop = 5000000000 (5.0e+9) , las diferencias se ilustran en la siguiente figura (con vimdiff ):

el bloque de la versión "4 Billions":

mov 0, %g2
sethi %hi(4000000000), %g3

es reemplazado en la versión "5 Billions" por:

 mov 1, %g2
sethi %hi(705032192), %g3
or %g3, 512, %g3 

Puedo ver que 5.0+e9 no se puede codificar en 32 bits, ya que la instrucción

sethi %hi(705032192), %g3

Paradójicamente, cuando compilo el código de ensamblado de la versión "5 Billions", la sum parámetro de salida se calcula bien, es decir, es igual a 5 Billions , y no puedo explicarlo.

Cualquier ayuda o comentario es bienvenido, gracias.

Answer 1

Mucho depende de qué versión de sparc y qué ABI estés usando. Si está utilizando sparc v8 o anterior, tiene modo de 32 bits con solo registros de 32 bits. En cuyo caso, cuando intenta cargar 5000000000 en un registro de 32 bits, falla y carga 5000000000 mod 2 ^{32 en su} lugar (que es 705032704). Esto es lo que parece estar sucediendo.

Si, por otro lado, tiene un procesador Sparc de 64 bits ejecutándose en modo de 32 bits (lo que generalmente se llama v8plus), entonces puede usar registros de 64 bits, así que esto funcionaría.

Answer 2

Parece que está haciendo operaciones de 32 bits en la mitad de un valor de 64 bits

A partir del código generado, aquí es donde nLoop es una carga doble en %o4 y %o5 (ya que es un valor long long 64 bits):

 ldd [%fp-24], %o4
clr %g1
clr %g2

Y luego solo trabajas con %o4 :

 mov %o4, %g1 ; <---- what about %o5????
loop:
add %g2, 1, %g2
subcc %g1, 1, %g1
bne loop
nop
mov %g2, %o4

Para que esto funcione, vuelva a escribir su código de ensamblado para tratar %o4 + %o5 juntos como un valor de 64 bits.