n est négatif, positif ou nul? retourne 1, 2 ou 4

Question

Je suis en train de construire un PowerPC interprète, et il fonctionne très bien. Dans la Puissance de l'architecture de la condition registre CR0 (EFLAGS sur x86) est mis à jour sur presque toute instruction. Il est défini comme ceci. La valeur de CR0 est 1, si le dernier résultat a été négatif, 2 si le dernier résultat a été positif, 4 sinon.

Ma première méthode naïve pour interpréter c'est:

if (n < 0)
    cr0 = 1
else if (n > 0)
    cr0 = 2;
else
    cr0 = 4;

Cependant je comprends que toutes ces branches ne sera pas optimale, en cours d'exécution des millions de fois par seconde. J'ai vu un peu sur le piratage, mais aucun ne semble adeguate. Par exemple, j'ai trouvé de nombreux exemples de convertir un certain nombre de -1, 0 ou 1 en fonction de la signer ou de 0. Mais comment faire -1 = 1, 1 = 2, 0 = 4? Je sollicite l'aide du Bit, des Pirates...

Merci d'avance

Mise à jour: Tout d'abord: merci les gars, vous avez été formidable. Je vais tester toutes vos codes avec soin pour la vitesse, et vous serez le premier à savoir qui est le gagnant.

@jalf.com: vos premiers conseils, je n'ai pas fait le calcul CR0 sur chaque instruction. J'étais plutôt en gardant un lastResult variable, et quand (et si) les instructions suivantes demandé pour un drapeau, faire la comparaison. Les trois principales motivations m'ont ramené à "chaque fois" mise à jour:

1. Sur PPC, vous n'êtes pas obligés de mettre à jour CR0 comme sur x86 (où AJOUTER toujours changer EFLAGS, même si pas nécessaire), vous avez deux saveurs d'AJOUTER, une mise à jour. Si le compilateur choisit d'utiliser la mise à jour de l'un, cela signifie qu'il va utiliser le CR0 à un certain point, il n'ya donc pas de point à retarder...
2. Il est particulièrement douloureux de l'instruction appelée mtcrf, qui vous permet de changer le CR0 arbitrarly. Vous pouvez même le mettre à 7, pas de l'arithmétique sens... Ce juste détruit la possibilité de garder un "lastResult" à la variable.

Answer 1

Tout d'abord, si cette variable est mise à jour après (presque) toutes les instructions, ce qui est évident morceau de conseil est le suivant:

ne pas

Mettre à jour uniquement lorsque les instructions ultérieures besoin de sa valeur. À tout autre moment, il ne sert à rien de le mettre à jour.

Mais de toute façon, quand nous la mettre à jour, ce que nous voulons, c'est ce comportement:

R < 0  => CR0 == 0b001 
R > 0  => CR0 == 0b010
R == 0 => CR0 == 0b100

Idéalement, nous n'avons pas besoin de la direction générale à tous. Voici une démarche possible:

1. Ensemble CR0 à la valeur 1. (si vous voulez vraiment de la vitesse, de déterminer si cela peut être fait sans l'extraction de la constante de la mémoire. Même si vous avez à dépenser quelques instructions sur lui, il peut bien être la peine)
2. Si R >= 0, décalage à gauche d'un bit.
3. Si R == 0, décalage à gauche d'un bit

Lorsque les étapes 2 et 3 peuvent être transformés de façon à éliminer le "si" de la partie

CR0 <<= (R >= 0);
CR0 <<= (R == 0);

Est-ce plus rapide? Je ne sais pas. Comme toujours, si vous êtes inquiet au sujet de la performance, vous avez besoin de mesurer, mesurer, mesurer.

Cependant, je peux voir quelques avantages de cette approche:

1. nous évitons les branches complètement
2. nous évitons la mémoire des charges et les magasins.
3. les instructions nous comptons sur (décalage de bits et de comparaison) doit avoir une faible latence, ce qui n'est pas toujours le cas de la multiplication, par exemple.

L'inconvénient est que nous avons une chaîne de dépendances entre les trois lignes: Chaque modifie CR0, qui est ensuite utilisé dans la ligne suivante. Cela limite l'instruction au niveau de parallélisme quelque peu.

Pour réduire cette dépendance de la chaîne, on pourrait faire quelque chose comme ceci à la place:

CR0 <<= ((R >= 0) + (R == 0));

donc, nous n'avons qu'à modifier CR0 une fois, après son initialisation.

Ou, à tout faire en une seule ligne:

CR0 = 1 << ((R >= 0) + (R == 0));

Bien sûr, il ya beaucoup de variations possibles de ce thème, donc aller de l'avant et de l'expérience.

Answer 2

Beaucoup de réponses qui sont à peu près "n'est pas" déjà, comme d'habitude :) Vous voulez que le bit hack? Vous l'obtiendrez. Alors n'hésitez pas à l'utiliser ou non que vous voyez l'ajustement.

Vous pouvez utiliser cette cartographie de -1, 0 et 1 (sign), puis:

return 7 & (0x241 >> ((sign(x) + 1) * 4));

Qui est essentiellement à l'aide d'une minuscule table de recherche.

Ou le "naïf bithack":

int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
return (~(-y >> 31) & 4) | y;

La première ligne de cartes x < 0 1, x > 0 2 et x == 0 à 0. La deuxième ligne puis maps y == 0 à 4 et y != 0 y est.

---

Et bien sûr, il a un sournois cas limite pour x = 0x80000000 qui est mappé à 3. Oups. Eh bien nous allons corriger cela:

int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
y &= 1 | ~(y << 1);  // remove the 2 if odd
return (~(-y >> 31) & 4) | y;

Answer 3

L'expression suivante est un peu énigmatique, mais pas de façon excessive, et ce qu'il ressemble à quelque chose, le compilateur peut optimiser assez facilement:

cr0 = 4 >> ((2 * (n < 0)) + (n > 0));

Voici ce que GCC 4.6.1 pour un x86 cible compile avec -O2:

xor ecx, ecx
mov eax, edx
sar eax, 31
and eax, 2
test    edx, edx
setg    cl
add ecx, eax
mov eax, 4
sar eax, cl

Et VC 2010 avec /Ox ressemble assez:

xor ecx, ecx
test eax, eax
sets cl
xor edx, edx
test eax, eax
setg dl
mov eax, 4
lea ecx, DWORD PTR [edx+ecx*2]
sar eax, cl

La version à l'aide d' if tests compile à l'assemblée qui utilise des sauts avec l'une de ces compilateurs. Bien sûr, vous ne serez jamais vraiment être sûr de ce que tout particulier, le compilateur va faire avec tout ce bit particulier de code que vous choisissez, à moins que vous fait examiner la sortie. Mon expression est assez cryptique que si elle était vraiment une critique pour les performances bout de code, je pourrais toujours aller avec des avec des if compte de résultat. Puisque vous avez besoin de définir le registre CR0 souvent, je pense qu'il pourrait être intéressant de mesurer si cette expression permet à tous les.

Answer 4

Je travaillais sur celui-ci quand mon ordinateur est tombé en panne.

 int cr0 = (-(n | n-1) >> 31) & 6;
cr0 |= (n >> 31) & 5;
cr0 ^= 4;
 

Voici l'assemblage résultant (pour Intel x86):

 PUBLIC  ?tricky@@YAHH@Z                                 ; tricky
; Function compile flags: /Ogtpy
_TEXT   SEGMENT
_n$ = 8                                                 ; size = 4
?tricky@@YAHH@Z PROC                                    ; tricky
; Line 18
        mov     ecx, DWORD PTR _n$[esp-4]
        lea     eax, DWORD PTR [ecx-1]
        or      eax, ecx
        neg     eax
        sar     eax, 31                                 ; 0000001fH
; Line 19
        sar     ecx, 31                                 ; 0000001fH
        and     eax, 6
        and     ecx, 5
        or      eax, ecx
; Line 20
        xor     eax, 4
; Line 22
        ret     0
?tricky@@YAHH@Z ENDP                                    ; tricky
 

Et un test exhaustif complet qui convient également raisonnablement à l'analyse comparative:

 #include <limits.h>

int direct(int n)
{
    int cr0;
    if (n < 0)
        cr0 = 1;
    else if (n > 0)
        cr0 = 2;
    else
        cr0 = 4;
    return cr0;
}

const int shift_count = sizeof(int) * CHAR_BIT - 1;
int tricky(int n)
{
    int cr0 = (-(n | n-1) >> shift_count) & 6;
    cr0 |= (n >> shift_count) & 5;
    cr0 ^= 4;
    return cr0;
}

#include <iostream>
#include <iomanip>
int main(void)
{
    int i = 0;
    do {
        if (direct(i) != tricky(i)) {
            std::cerr << std::hex << i << std::endl;
            return i;
        }
    } while (++i);
    return 0;
}
 

Answer 5

gcc sans optimisation

         movl    %eax, 24(%esp)  ; eax has result of reading n
        cmpl    $0, 24(%esp)
        jns     .L2
        movl    $1, 28(%esp)
        jmp     .L3
.L2:
        cmpl    $0, 24(%esp)
        jle     .L4
        movl    $2, 28(%esp)
        jmp     .L3
.L4:
        movl    $4, 28(%esp)
.L3:
 

Avec -O2:

         movl    $1, %edx       ; edx = 1
        cmpl    $0, %eax
        jl      .L2            ; n < 0
        cmpl    $1, %eax       ; n < 1
        sbbl    %edx, %edx     ; edx = 0 or -1
        andl    $2, %edx       ; now 0 or 2
        addl    $2, %edx       ; now 2 or 4
.L2:
        movl    %edx, 4(%esp)
 

Je ne pense pas que vous ferez beaucoup mieux