Table de branche - Branch table

En programmation informatique , une table de branchement ou table de saut est une méthode de transfert de contrôle de programme ( branchement ) vers une autre partie d'un programme (ou un programme différent qui peut avoir été chargé dynamiquement) en utilisant une table d' instructions de branchement ou de saut . C'est une forme de branche multi - voies . La construction de table de branchement est couramment utilisée lors de la programmation en langage assembleur, mais peut également être générée par des compilateurs , en particulier lors de l'implémentation d' instructions de commutation optimisées dont les valeurs sont densément regroupées.

Implémentation typique

Une table de branchement consiste en une liste en série d' instructions de branchement inconditionnelles qui est branchée en utilisant un décalage créé en multipliant un index séquentiel par la longueur de l'instruction (le nombre d'octets en mémoire occupés par chaque instruction de branchement). Il repose sur le fait que les instructions de code machine pour le branchement ont une longueur fixe et peuvent être exécutées de manière extrêmement efficace par la plupart du matériel, et est particulièrement utile lorsqu'il s'agit de valeurs de données brutes qui peuvent être facilement converties en valeurs d'index séquentielles . Compte tenu de ces données, une table de branche peut être extrêmement efficace. Il comprend généralement les 3 étapes suivantes:

éventuellement valider les données d'entrée pour s'assurer qu'elles sont acceptables (cela peut se produire sans frais dans le cadre de l'étape suivante, si l'entrée est d'un seul octet et qu'une table de conversion de 256 octets est utilisée pour obtenir directement le décalage ci-dessous). En outre, s'il n'y a aucun doute sur les valeurs de l'entrée, cette étape peut être omise.
transformer les données en un offset dans la table de branche. Cela implique généralement de le multiplier ou de le déplacer (multipliant effectivement par une puissance de 2) pour prendre en compte la longueur de l'instruction. Si une table de traduction statique est utilisée, cette multiplication peut être effectuée manuellement ou par le compilateur, sans aucun coût d'exécution.
branchement à une adresse composée de l'adresse de base de la table de branchement plus le décalage qui vient d'être généré. Cela implique parfois une addition du décalage sur le registre du compteur de programme (à moins que, dans certains jeux d'instructions , l'instruction de branchement autorise un registre d'index supplémentaire). Cette adresse finale pointe généralement vers l'une d'une séquence d'instructions de branchement inconditionnelles, ou l'instruction immédiatement au-delà (sauvegarde d'une entrée dans le tableau).

Le pseudocode suivant illustre le concept

 ... validate x                    /* transform x to 0 (invalid) or 1,2,3, according to value..)    */
       y = x * 4;                  /* multiply by branch instruction length (e.g. 4 )               */
       goto next + y;              /* branch into 'table' of branch instructions                    */
 /* start of branch table */
 next: goto codebad;               /* x= 0  (invalid)                                               */
       goto codeone;               /* x= 1                                                          */
       goto codetwo;               /* x= 2                                                          */
 ... rest of branch table
 codebad:                          /* deal with invalid input                                       */

Implémentation alternative utilisant des adresses

Une autre méthode d'implémentation d'une table de branches consiste à utiliser un tableau de pointeurs à partir duquel l' adresse de la fonction requise est récupérée. Cette méthode est également connue plus récemment sous des noms aussi différents que " table de distribution " ou " table de méthode virtuelle " mais remplissant essentiellement exactement le même but. Cette méthode de fonction de pointeur peut entraîner la sauvegarde d'une instruction machine et évite le saut indirect (vers l'une des instructions de branchement).

La liste résultante de pointeurs vers des fonctions est presque identique au code threadé direct et est conceptuellement similaire à une table de contrôle .

La méthode réelle utilisée pour implémenter une table de branches est généralement basée sur:

l'architecture du processeur sur lequel le code doit être exécuté,
s'il s'agit d'un langage compilé ou interprété et
s'il s'agit d'une liaison tardive ou non.

Histoire

L'utilisation de tables de branches et d'autres encodages de données brutes était courante dans les premiers jours de l'informatique lorsque la mémoire était chère, les processeurs étaient plus lents et la représentation compacte des données et le choix efficace des alternatives étaient importants. De nos jours, ils sont encore couramment utilisés dans:

programmation embarquée
développement du système d'exploitation . Dans de nombreux systèmes d'exploitation, les appels système et les fonctions de bibliothèque peuvent être référencés par un index entier dans une table de branche.
certaines architectures informatiques telles qu'IBM / 360 utilisent des tables de branche pour distribuer les interruptions

Avantages

Les avantages des tables de branchement comprennent:

structure de code compacte (malgré des opcodes de branche répétés)
déclarations sources réduites (par rapport aux If déclarations répétitives )
exigence réduite de tester les codes de retour individuellement (si utilisé sur le site d'appel pour déterminer le flux de programme ultérieur )
Efficacité de l' algorithmique et du code (les données ne doivent être codées qu'une seule fois et le code de la table de branchement est généralement compact), et possibilité d'atteindre des taux de compression de données élevés. Par exemple, lors de la compression des noms de pays en codes de pays, une chaîne telle que "République centrafricaine" peut être compressée en un seul index, ce qui se traduit par d'importantes économies, en particulier lorsque la chaîne apparaît plusieurs fois. De plus, ce même index peut être utilisé pour accéder aux données associées dans des tables séparées, ce qui réduit davantage les besoins de stockage.

Pour les fonctions de bibliothèque , où elles peuvent être référencées par un entier :

améliorer la compatibilité avec les versions logicielles ultérieures. Si le code d'une fonction et l'adresse de son point d'entrée sont modifiés, seule l'instruction de branchement dans la table de branchement doit être ajustée; le logiciel d'application compilé avec la bibliothèque ou pour le système d'exploitation n'a pas besoin de modification.

De plus, l'appel de fonctions par numéro (l'index dans le tableau) peut parfois être utile dans certains cas dans la programmation d'application normale.

Désavantages

Niveau supplémentaire d' indirection , ce qui entraîne un faible impact sur les performances.
Restrictions dans certains langages de programmation, bien qu'il existe généralement des moyens alternatifs d'implémenter le concept de base du branchement multi-voies.

Exemple

Voici un exemple simple d'utilisation de table de branchement dans le langage d'assemblage Microchip PIC 8 bits :

     movf    INDEX,W     ; Move the index value into the W (working) register from memory
     addwf   PCL,F       ; add it to the program counter. Each PIC instruction is one byte
                         ; so there is no need to perform any multiplication. 
                         ; Most architectures will transform the index in some way before 
                         ; adding it to the program counter.

 table                   ; The branch table begins here with this label
     goto    index_zero  ; each of these goto instructions is an unconditional branch
     goto    index_one   ; of code.
     goto    index_two
     goto    index_three

 index_zero
     ; Code is added here to perform whatever action is required when INDEX = zero
     return

 index_one
 ...

Remarque: ce code fonctionnera uniquement si PCL <(table + index_last). Pour garantir cette condition, nous pouvons utiliser une directive "org". Et si GOTO (PIC18F par exemple) est de 2 octets, cela limite le nombre d'entrées de table à moins de 128.

Exemple de table de saut en C

Un autre exemple simple, qui montre cette fois une table de saut plutôt qu'une simple table de branche. Cela permet d'appeler des blocs de programme en dehors de la procédure / fonction actuellement active:

#include <stdio.h>
#include <stdlib.h>

typedef void (*Handler)(void);    /* A pointer to a handler function */

/* The functions */
void func3 (void) { printf( "3\n" ); }
void func2 (void) { printf( "2\n" ); }
void func1 (void) { printf( "1\n" ); }
void func0 (void) { printf( "0\n" ); }

Handler jump_table[4] = {func0, func1, func2, func3};

int main (int argc, char **argv) {
    int value;

    /* Convert first argument to 0-3 integer (modulus) */
    value = atoi(argv[1]) % 4;

    /* Call appropriate function (func0 thru func3) */
    jump_table[value]();

    return 0;
}

Exemple de table de saut en PL / I

PL / I implémente une table de sauts en tant que tableau de variables d'étiquette . Celles-ci peuvent être initialisées de manière inhabituelle en utilisant une étiquette d'instruction en indice. Les variables d'étiquette PL / I ne sont pas simplement l'adresse de l'instruction, mais contiennent généralement des informations supplémentaires sur l'état du bloc de code auquel elles appartiennent. Sans l'initialisation inhabituelle, cela pourrait également être codé avec des appels et un tableau de variables d'entrée.

    declare lab (10) label;
    declare x fixed binary;
    goto lab(x);
  lab(1): /* code for choice 1 */ ;
    ...
  lab(2): /* code for choice 2 */ ;
    ...

Tables de branches générées par le compilateur

Les programmeurs laissent souvent la décision de créer ou non une table de branches au compilateur, estimant qu'il est parfaitement capable de faire le bon choix à partir des clés de recherche connues. Cela peut être vrai pour l'optimisation des compilateurs pour des cas relativement simples où la plage de clés de recherche est limitée. Cependant, les compilateurs ne sont pas aussi intelligents que les humains et ne peuvent pas avoir une connaissance approfondie du `` contexte '', estimant qu'une gamme de valeurs entières de clé de recherche possibles telles que 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 & 1000 généreraient une table de branche avec un nombre excessivement grand d'entrées vides (900+) pour très peu d'avantages. Un bon compilateur d'optimisation peut alors pré-trier les valeurs et générer du code pour une recherche de hachage binaire , comme une «deuxième meilleure option». En fait, l'application peut être très «critique en termes de temps» et les besoins en mémoire peuvent ne pas vraiment être un problème.

Cependant, un peu de `` bon sens '' peut transformer ce cas particulier, et de nombreux autres cas similaires, en un simple processus en deux étapes avec de très grandes économies potentielles, tout en laissant finalement le choix ultime au compilateur, mais `` l'aidant à sa décision '' considérablement:

Tout d'abord, testez la clé de recherche = 1000 et effectuez une branche appropriée.
Permettez au compilateur de «choisir» pour générer une table de branche sur les clés de recherche restantes (1-50).

Des variations le long de lignes similaires peuvent être utilisées dans les cas où il existe deux ensembles de plages courtes avec un grand écart entre les plages.

GoTo calculé

Alors que la technique est maintenant connue sous le nom de «tables de branches», les premiers utilisateurs du compilateur ont appelé l'implémentation « computed GoTo », en référence à l'instruction trouvée dans la série de compilateurs Fortran. L'instruction a finalement été déconseillée dans Fortran 90 (en faveur des instructions SELECT & CASE au niveau source).

Création de l'index pour la table de branche

Lorsqu'aucune valeur entière évidente n'est disponible pour une table de branche, elle peut néanmoins être créée à partir d'une clé de recherche (ou d'une partie d'une clé de recherche) par une forme de transformation arithmétique, ou pourrait simplement être le numéro de ligne d'une base de données ou le numéro d'entrée dans un tableau contenant la clé de recherche trouvée lors de la validation précédente de la clé.

Une table de hachage peut être nécessaire pour former l'index dans certains cas. Cependant, pour les valeurs d'entrée à un octet telles que AZ (ou le premier octet d'une clé plus longue), le contenu de l'octet lui-même ( données brutes ) peut être utilisé dans un processus en deux étapes, " fonction de hachage triviale ", pour obtenir un index final pour une table de branche avec zéro intervalle.

Convertit le caractère de données brutes en son équivalent numérique (exemple ASCII 'A' ==> 65 décimal, 0x41 hexadécimal)
Utilisez la valeur entière numérique comme index dans un tableau de 256 octets, pour obtenir un deuxième index (entrées non valides 0; représentant des espaces, sinon 1, 2, 3 etc.)

Le tableau ne serait pas plus grand que (256 x 2) octets - pour contenir tous les entiers non signés (courts) de 16 bits possibles. Si aucune validation n'est requise et que seules des majuscules sont utilisées, la taille du tableau peut être aussi petite que (26 x 2) = 52 octets.

Autres utilisations de la technique

Bien que la technique de branchement à l'aide d'une table de branchement soit le plus souvent utilisée uniquement dans le but de modifier le flux du programme - pour passer à une étiquette de programme qui est une branche inconditionnelle - la même technique peut être utilisée à d'autres fins. Par exemple, il peut être utilisé pour sélectionner un point de départ dans une séquence d'instructions répétées où la suppression est la norme et intentionnelle. Cela peut être utilisé par exemple en optimisant des compilateurs ou des compilateurs JIT dans le déroulement de boucles .

Voir également

Dispatch table une table de branche par un autre nom utilisé pour la liaison tardive
Tableaux de pointeurs de fonction d'adresses vers des fonctions utilisées dans les tables de branche
Succursale indirecte
Table de consultation un tableau d'éléments à mettre en correspondance, contenant parfois des résultats pré-calculés
Instruction Switch une instruction conditionnelle de langage de haut niveau qui peut générer une table de branche
Table de méthode virtuelle une table de branche par un autre nom avec des pointeurs affectés dynamiquement pour la répartition (voir la table de répartition)

Les références

Liens externes

[1] Exemple de table de branches dans Wikibooks pour IBM S / 360
[2] Exemples et arguments pour Jump Tables via des tableaux de pointeurs de fonction en C / C ++
[3] Exemple de code généré par la table de branche 'Switch / Case' en C, versus IF / ELSE.
[4] Exemple de code généré pour l'indexation de tableau si la taille de la structure est divisible par des puissances de 2 ou autrement.
[5] "Tableaux de pointeurs vers des fonctions" par Nigel Jones

Languages

In other projects