Una rama 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 instrucciones en orden. [a] Ramificar (o bifurcar , ramificar ) también puede referirse al acto de cambiar la ejecución a una secuencia de instrucciones diferente como resultado de ejecutar una instrucción de bifurcación. Las instrucciones de bifurcación se utilizan para implementar el flujo de control en bucles y condicionales del programa (es decir, ejecutar una secuencia particular de instrucciones sólo si se cumplen ciertas condiciones).
Una instrucción de bifurcación puede ser una bifurcación incondicional , que siempre resulta en 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 "destino"), 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 de destino, o especifica dónde se encuentra el destino. se va a encontrar una dirección (por ejemplo, un registro o una ubicación de memoria), o especifica la diferencia entre las direcciones actual y de destino.
Las instrucciones de rama pueden alterar el contenido del contador de programas de la CPU (o PC) (o puntero de instrucciones en los microprocesadores Intel). La PC mantiene la dirección de memoria de la siguiente instrucción de la máquina que se recuperará y ejecutará. Por lo tanto, una rama, 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 planeado por el programador.
Un tipo de rama a nivel de máquina es la instrucción de salto . Esto puede o no dar como resultado que la PC se cargue o modifique con algún valor nuevo y diferente al que normalmente habría sido (incrementándose más allá de la instrucción actual para apuntar a la siguiente instrucción). Los saltos suelen tener formas incondicionales y condicionales donde este último se puede realizar o no (el PC se modifica o no) dependiendo de 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, una dirección de retorno se guarda en un lugar seguro de la memoria (generalmente en una estructura de datos residente en la memoria llamada pila ). Al finalizar la subrutina, esta dirección de retorno se restablece en la PC y, por lo tanto, se reanuda la ejecución del programa 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 . Esto "saca" una dirección de retorno de la pila y la carga en el registro de la PC, devolviendo así el control a la rutina de llamada. Las instrucciones de devolución 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 así redirigir la ejecución del programa de muchas maneras diferentes.
Dependiendo del procesador, las instrucciones de salto y llamada pueden alterar el contenido del registro de la PC de diferentes maneras. Se puede cargar una dirección absoluta, o el contenido actual de la PC puede tener algún valor (o desplazamiento) agregado o restado 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 incrustado dentro de la instrucción, o el contenido de un registro del procesador o ubicación de memoria, o el contenido de alguna ubicación agregada a un valor de índice.
El término rama también puede utilizarse cuando se hace referencia a programas en lenguajes de programación de alto nivel . En estas ramas suelen tomar la forma de declaraciones condicionales de diversas formas que encapsulan la secuencia de instrucciones que se ejecutarán si se cumplen las condiciones. Las instrucciones de salto incondicionales como GOTO se utilizan para saltar incondicionalmente a una secuencia de instrucciones diferente. Si el algoritmo requiere una rama condicional, GOTO (o llamada a subrutina GOSUB) está precedida por una declaración IF-THEN que especifica las condiciones. 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 consideran instrucciones de bifurcación. A nivel de máquina, los bucles se implementan como saltos condicionales ordinarios que redirigen la ejecución al código repetido.
En las CPU con registros de bandera , una instrucción anterior establece una condición en el registro de bandera. La instrucción anterior puede ser aritmética o lógica . A menudo está cerca de la sucursal, aunque no necesariamente es la instrucción inmediatamente anterior a la sucursal. La condición almacenada luego se usa en una rama como jump if overflow-flag set . Esta información temporal suele almacenarse en un registro de banderas, pero también puede estar ubicada en otro lugar. El diseño de un registro de bandera es simple en computadoras simples y más lentas. En computadoras rápidas, un registro de bandera puede suponer un cuello de botella en la velocidad, porque las instrucciones que de otro modo podrían operar en paralelo (en varias unidades de ejecución ) necesitan establecer los bits de bandera 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 la rama <label> si el registro X es negativo . En diseños de computadora simples, las ramas de comparación ejecutan más aritmética y pueden usar más energía que las ramas de registro de bandera. En diseños de computadoras rápidas, las ramas de comparación pueden ejecutarse más rápido que las ramas de registro de bandera, porque las ramas de comparación pueden acceder a los registros con más paralelismo, utilizando los mismos mecanismos de CPU como cálculo.
Es posible que algunas arquitecturas de CPU tempranas y simples, que todavía se encuentran en microcontroladores, no implementen un salto condicional, sino solo una operación condicional de "omitir la siguiente instrucción". Un salto o llamada condicional se implementa así como un salto condicional de una instrucción de salto o llamada incondicional.
Dependiendo de la arquitectura de la computadora , el mnemónico del lenguaje ensamblador para una instrucción de salto suele ser alguna forma abreviada de la palabra salto o la palabra 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 de compensación) o un modo de direccionamiento especial que debe usarse para localizar la compensación efectiva real.
Esta tabla enumera las instrucciones de salto o rama 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 señalar el préstamo y lo borran para indicar que no hay préstamo . 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 por ( * ), es decir, pedir prestado= no acarrear en algunas partes de la tabla, pero si no se indica lo contrario, pedir prestado≡acarrar. Sin embargo, la mayoría de las arquitecturas manejan las operaciones aditivas de la misma manera.
Para lograr un alto rendimiento, se están canalizando procesadores modernos . Constan de varias partes, cada una de las cuales procesa parcialmente una instrucción, envía sus resultados a la siguiente etapa del proceso y comienza a trabajar en la siguiente instrucción del programa. Este diseño espera que las instrucciones se ejecuten en una secuencia particular e invariable. Las instrucciones de rama condicional hacen imposible conocer esta secuencia. Por lo tanto, las bifurcaciones condicionales pueden provocar "bloqueos" en los que la canalización debe reiniciarse en una parte diferente del programa.
Varias técnicas mejoran la velocidad al reducir las pérdidas en las ramas condicionales.
Históricamente, la predicción de ramas tomaba estadísticas y usaba el resultado para optimizar el código. Un programador compilaría una versión de prueba de un programa y la ejecutaría con datos de prueba. El código de prueba contó cómo se tomaron realmente las ramas. Luego, el compilador utilizó las estadísticas del código de prueba para optimizar las ramas del código publicado. La optimización haría que la dirección de rama más rápida (tomada o no) siempre fuera la ruta de flujo de control tomada con más frecuencia. Para permitir esto, las CPU deben diseñarse con (o al menos tener) tiempos de bifurcación predecibles. Algunas CPU tienen conjuntos de instrucciones (como Power ISA ) que fueron diseñadas con "sugerencias de rama" para que un compilador pueda decirle a una CPU cómo se debe tomar cada rama.
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 rama de hardware trasladaron las estadísticas a la electrónica. Los predictores de bifurcación son partes de un procesador que adivinan el resultado de una bifurcación condicional. Luego, la lógica del procesador apuesta por las conjeturas y comienza a ejecutar el flujo de instrucciones esperado. Un ejemplo de un esquema simple de predicción de bifurcaciones de hardware es asumir que todas las bifurcaciones hacia atrás (es decir, a un contador de programa más pequeño) se toman (porque son parte de un bucle) y todas las bifurcaciones hacia adelante (a un contador de programa más grande) no se toman. (porque dejan un bucle). Se desarrollan y validan estadísticamente mejores predictores de ramas ejecutándolos en simulación en una variedad de programas de prueba. Los buenos predictores suelen contar los resultados de ejecuciones anteriores de una rama. Las computadoras más rápidas y caras pueden funcionar más rápido invirtiendo en mejores dispositivos electrónicos de predicción de sucursales. En una CPU con predicción de rama de hardware, las sugerencias de rama permiten que la predicción de rama presumiblemente superior del compilador anule la predicción de rama más simplista del hardware.
Parte de la lógica se puede escribir sin ramas o con menos ramas. A menudo es posible utilizar operaciones bit a bit , movimientos condicionales u otras predicaciones en lugar de ramas. [1] [2] De hecho, el código sin sucursales es imprescindible para la criptografía debido a los ataques de sincronización . [3]
Otra técnica es una ranura de retardo de rama . En este enfoque, siempre se ejecuta al menos una instrucción que sigue a 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, ya sea que su tubería se detenga 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).