Taula de salts
En la programació d'ordinadors, una taula de branques o taula de salts és un mètode per transferir el control de programa (branding) a una altra part d'un programa (o un programa diferent que podria haver-se carregat dinàmicament) mitjançant una taula d' instruccions de branca o de salt. És una forma de branca multidireccional. La construcció de la taula de branques s'utilitza habitualment quan es programa en llenguatge ensamblador, però també pot ser generada pels compiladors, especialment quan s'implementen sentències de commutació optimitzades els valors de les quals estan densament empaquetats.[1]
Implementació típica modifica
Una taula de branca consisteix en una llista en sèrie d'instruccions de branca incondicional que es ramifica mitjançant un desplaçament creat multiplicant un índex seqüencial per la longitud de la instrucció (el nombre de bytes de memòria ocupats per cada instrucció de branca). Es basa en el fet que les instruccions de codi màquina per a la ramificació tenen una longitud fixa i poden ser executades de manera extremadament eficient per la majoria de maquinari, i és més útil quan es tracta de valors de dades en brut que es poden convertir fàcilment en valors d'índex seqüencial. Tenint en compte aquestes dades, una taula de branques pot ser extremadament eficient. Normalment consta dels 3 passos següents: [2]
- validant opcionalment les dades d'entrada per assegurar-se que són acceptables (això pot passar sense cost com a part del següent pas, si l'entrada és d'un sol byte i s'utilitza una taula de traducció de 256 bytes per obtenir directament el desplaçament a continuació). A més, si no hi ha cap dubte sobre els valors de l'entrada, aquest pas es pot ometre.
- transformar les dades en un desplaçament a la taula de branques. Normalment, això implica multiplicar-lo o desplaçar-lo (multiplicant-lo efectivament per una potència de 2) per tenir en compte la durada de la instrucció. Si s'utilitza una taula de traducció estàtica, aquesta multiplicació es pot realitzar manualment o pel compilador, sense cap cost d'execució.
- ramificació a una adreça formada per l'adreça base de la taula de branques més el desplaçament acabat de generar. Això de vegades implica una addició de l'offset al registre del comptador del programa (tret que, en alguns conjunts d'instruccions, la instrucció de branca permeti un registre d'índex addicional). Aquesta adreça final acostuma a apuntar a una d'una seqüència d'instruccions de branca incondicional, o a la instrucció immediatament posterior (desant una entrada a la taula).
... 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 */
Implementació alternativa mitjançant adreces modifica
Un altre mètode per implementar una taula de branques és amb una matriu de punters des dels quals es recupera l'adreça de la funció requerida. Conegut originalment com a vector de transferència, aquest mètode també es coneix més recentment amb noms tan diferents com " taula d'enviament " o " taula de mètodes virtuals ", però essencialment realitza exactament el mateix propòsit. Aquest mètode de funció de punter pot provocar l'estalvi d'una instrucció de màquina i evita el salt indirecte (a una de les instruccions de branca).[3]
La llista resultant de punters a funcions és gairebé idèntica al codi de fil directe i conceptualment és similar a una taula de control.
El mètode real utilitzat per implementar una taula de branques normalment es basa en:
- l'arquitectura del processador en què s'ha d'executar el codi,
- si es tracta d'un llenguatge compilat o interpretat i
- si hi ha una vinculació tardana o no.[4]
Referències modifica
- ↑ Page, Daniel. A Practical Introduction to Computer Architecture (en anglès). Springer Science & Business Media, 2009, p. 479. ISBN 9781848822559.
- ↑ «Symbol Tables and Branch Tables» (en anglès). [Consulta: 29 novembre 2023].
- ↑ «[https://people.eecs.berkeley.edu/~kubitron/courses/cs252-S11/lectures/lec09-prediction2.pdf CS252 Graduate Computer Architecture]» (en anglès). [Consulta: 29 novembre 2023].
- ↑ «Branch table» (en anglès). [Consulta: 29 novembre 2023].