Una bifurcación , salto o transferencia es una instrucción en un programa de computadora que puede hacer que una computadora comience a ejecutar una secuencia de instrucciones diferente y, por lo tanto, se desvíe de su comportamiento predeterminado de ejecutar las instrucciones en orden. [a] La bifurcación (o ramificación , ramificado ) también puede referirse al acto de cambiar la ejecución a una secuencia de instrucciones diferente como resultado de la ejecución de una instrucción de bifurcación. Las instrucciones de bifurcación se utilizan para implementar el flujo de control en bucles y condicionales de programas (es decir, ejecutar una secuencia particular de instrucciones solo si se cumplen ciertas condiciones).
Una instrucción de bifurcación puede ser una bifurcación incondicional , que siempre da como resultado una bifurcación, o una bifurcación condicional , que puede o no causar una bifurcación dependiendo de alguna condición. Además, dependiendo de cómo especifica la dirección de la nueva secuencia de instrucciones (la dirección "objetivo"), una instrucción de bifurcación generalmente se clasifica como directa , indirecta o relativa , lo que significa que la instrucción contiene la dirección objetivo, o especifica dónde se debe encontrar la dirección objetivo (por ejemplo, un registro o una ubicación de memoria), o especifica la diferencia entre las direcciones actual y objetivo.
Las instrucciones de bifurcación pueden alterar el contenido del contador de programa (o PC) de la CPU (o puntero de instrucción en los microprocesadores Intel). El PC mantiene la dirección de memoria de la siguiente instrucción de máquina que se buscará y ejecutará. Por lo tanto, una bifurcación, si se ejecuta, hace que la CPU ejecute código desde una nueva dirección de memoria, cambiando la lógica del programa de acuerdo con el algoritmo planificado por el programador.
Un tipo de bifurcación a nivel de máquina es la instrucción de salto . Estas pueden o no dar como resultado que la PC se cargue o modifique con algún valor nuevo y diferente del que hubiera sido normalmente (se incrementa más allá de la instrucción actual para apuntar a la siguiente instrucción). Los saltos suelen tener formas incondicionales y condicionales , donde la última puede tomarse o no (la PC se modifica o no) según alguna condición.
El segundo tipo de rama a nivel de máquina es la instrucción de llamada que se utiliza para implementar subrutinas . Al igual que las instrucciones de salto, las llamadas pueden modificar o no la PC según los códigos de condición; sin embargo, además, se guarda una dirección de retorno en un lugar seguro de la memoria (normalmente en una estructura de datos residente en la memoria denominada pila ). Al finalizar la subrutina, esta dirección de retorno se restaura a la PC y, por lo tanto, la ejecución del programa se reanuda con la instrucción que sigue a la instrucción de llamada.
El tercer tipo de rama a nivel de máquina es la instrucción de retorno . Esta "extrae" una dirección de retorno de la pila y la carga en el registro de la PC, devolviendo así el control a la rutina que la llamó. Las instrucciones de retorno también pueden ejecutarse condicionalmente. Esta descripción pertenece a la práctica ordinaria; sin embargo, el programador de la máquina tiene poderes considerables para manipular la dirección de retorno en la pila y, por lo tanto, redirigir la ejecución del programa de diversas maneras.
Dependiendo del procesador, las instrucciones de salto y llamada pueden alterar el contenido del registro de PC de diferentes maneras. Se puede cargar una dirección absoluta, o se puede agregar o restar algún valor (o desplazamiento) al contenido actual de PC de su valor actual, haciendo que la dirección de destino sea relativa al lugar actual en el programa. La fuente del valor de desplazamiento puede variar, como un valor inmediato incorporado dentro de la instrucción, o el contenido de un registro de procesador o una ubicación de memoria, o el contenido de alguna ubicación agregada a un valor de índice.
El término ramificación también se puede utilizar al referirse a programas en lenguajes de programación de alto nivel . En estos, las ramificaciones suelen adoptar la forma de instrucciones condicionales de diversas formas que encapsulan la secuencia de instrucciones que se ejecutará si se cumplen las condiciones. Las instrucciones de ramificación incondicional, como GOTO , se utilizan para saltar incondicionalmente a una secuencia de instrucciones diferente. Si el algoritmo requiere una ramificación condicional, la llamada a la subrutina GOTO (o GOSUB) va precedida de una instrucción IF-THEN que especifica la(s) condición(es). Todos los lenguajes de alto nivel admiten algoritmos que pueden reutilizar el código como un bucle , una estructura de control que repite una secuencia de instrucciones hasta que se cumple alguna condición que hace que el bucle termine. Los bucles también se califican como instrucciones de ramificación. A nivel de máquina, los bucles se implementan como saltos condicionales ordinarios que redirigen la ejecución al código que se repite.
En las CPU con registros de indicadores , una instrucción anterior establece una condición en el registro de indicadores. La instrucción anterior puede ser aritmética o una instrucción lógica . A menudo está cerca de la bifurcación, aunque no necesariamente la instrucción inmediatamente anterior a la bifurcación. La condición almacenada se utiliza entonces en una bifurcación como jump if overflow-flag set . Esta información temporal a menudo se almacena en un registro de indicadores, pero también puede estar ubicada en otro lugar. Un diseño de registro de indicadores es simple en computadoras más lentas y simples. En computadoras rápidas, un registro de indicadores puede suponer un cuello de botella en la velocidad, porque las instrucciones que de otro modo podrían funcionar en paralelo (en varias unidades de ejecución ) necesitan establecer los bits de los indicadores en una secuencia particular.
También hay máquinas (o instrucciones particulares) donde la condición puede ser verificada por la propia instrucción de salto, como branch <label> if register X negative . En diseños de computadoras simples, las ramas de comparación ejecutan más aritmética y pueden usar más energía que las ramas de registro de banderas. En diseños de computadoras rápidas, las ramas de comparación pueden ejecutarse más rápido que las ramas de registro de banderas, porque las ramas de comparación pueden acceder a los registros con más paralelismo, usando los mismos mecanismos de CPU como un cálculo.
Algunas arquitecturas de CPU simples y tempranas, que todavía se encuentran en los microcontroladores, pueden no implementar un salto condicional, sino solo una operación condicional de "saltar la siguiente instrucción". Por lo tanto, un salto o una llamada condicional se implementan como un salto condicional de una instrucción de salto o llamada incondicional.
Dependiendo de la arquitectura de la computadora , la mnemotecnia del lenguaje ensamblador para una instrucción de salto es típicamente una forma abreviada de la palabra jump (saltar ) o de la palabra branch (rama) , a menudo junto con otras letras informativas (o un parámetro adicional) que representan la condición. A veces también se incluyen otros detalles, como el rango del salto (el tamaño del desplazamiento) o un modo de direccionamiento especial que se debe utilizar para localizar el desplazamiento efectivo real.
Esta tabla enumera las instrucciones de salto o ramificación a nivel de máquina que se encuentran en varias arquitecturas conocidas:
* x86, PDP-11, VAX y algunos otros, configuran el indicador de acarreo para indicar que se debe pedir prestado y lo borran para indicar que no se debe pedir prestado . ARM, 6502 , PIC y algunos otros hacen lo contrario para las operaciones sustractivas. Esta función invertida del indicador de acarreo para ciertas instrucciones está marcada con ( * ), es decir, pedir prestado= no pedir prestado en algunas partes de la tabla, pero si no se indica lo contrario, pedir prestado≡pedir prestado. Sin embargo, la mayoría de las arquitecturas manejan el mismo modo las operaciones aditivas de acarreo.
Para lograr un alto rendimiento, los procesadores modernos están segmentados . Consisten en múltiples partes que procesan parcialmente una instrucción, envían sus resultados a la siguiente etapa de la segmentación y comienzan a trabajar en la siguiente instrucción del programa. Este diseño espera que las instrucciones se ejecuten en una secuencia particular invariable. Las instrucciones de bifurcación condicional hacen imposible conocer esta secuencia. Por lo tanto, las bifurcaciones condicionales pueden causar "bloqueos" en los que la segmentación debe reiniciarse en una parte diferente del programa.
Varias técnicas mejoran la velocidad al reducir los bloqueos en las ramas condicionales.
Históricamente, la predicción de ramificaciones tomaba estadísticas y utilizaba el resultado para optimizar el código. Un programador compilaba una versión de prueba de un programa y la ejecutaba con datos de prueba. El código de prueba contaba cómo se tomaban realmente las ramificaciones. Luego, el compilador utilizaba las estadísticas del código de prueba para optimizar las ramificaciones del código publicado. La optimización dispondría que la dirección de ramificación más rápida (tomada o no) siempre fuera la ruta de flujo de control tomada con mayor frecuencia. Para permitir esto, las CPU deben diseñarse con (o al menos tener) tiempos de ramificación predecibles. Algunas CPU tienen conjuntos de instrucciones (como Power ISA ) que se diseñaron con "pistas de ramificación" para que un compilador pueda indicarle a la CPU cómo se debe tomar cada ramificación.
El problema con la predicción de ramas de software es que requiere un proceso de desarrollo de software complejo.
Para ejecutar cualquier software, los predictores de saltos de hardware trasladaban las estadísticas a la electrónica. Los predictores de saltos son partes de un procesador que adivinan el resultado de un salto condicional. Luego, la lógica del procesador apuesta por el resultado y comienza a ejecutar el flujo de instrucciones esperado. Un ejemplo de un esquema simple de predicción de saltos de hardware es suponer que se han tomado todos los saltos hacia atrás (es decir, a un contador de programa más pequeño) (porque son parte de un bucle) y que no se han tomado todos los saltos hacia adelante (a un contador de programa más grande) (porque abandonan un bucle). Se desarrollan y validan estadísticamente mejores predictores de saltos al ejecutarlos en simulación en una variedad de programas de prueba. Los buenos predictores suelen contar los resultados de ejecuciones anteriores de un salto. Las computadoras más rápidas y más caras pueden funcionar más rápido si se invierte en una mejor electrónica de predicción de saltos. En una CPU con predicción de saltos de hardware, las sugerencias de saltos permiten que la predicción de saltos presumiblemente superior del compilador anule la predicción de saltos más simplista del hardware.
Algunas lógicas se pueden escribir sin ramificaciones o con menos ramificaciones. A menudo es posible utilizar operaciones bit a bit , movimientos condicionales u otras predicciones en lugar de ramificaciones. [1] [2] De hecho, el código sin ramificaciones es imprescindible para la criptografía debido a los ataques de temporización . [3]
Otra técnica es la ranura de retardo de bifurcación . En este enfoque, siempre se ejecuta al menos una instrucción después de una bifurcación, con algunas excepciones, como la instrucción de bifurcación probable/improbable de la arquitectura MIPS heredada . Por lo tanto, la computadora puede usar esta instrucción para realizar un trabajo útil independientemente de si su canalización se detiene o no. Este enfoque fue históricamente popular en las computadoras RISC . En una familia de CPU compatibles, complica las CPU multiciclo (sin canalización), las CPU más rápidas con canalizaciones más largas de lo esperado y las CPU superescalares (que pueden ejecutar instrucciones fuera de orden).