Branch (ciência da computação) - Branch (computer science)

Para outros usos, veja Ramificação (desambiguação) .
Código da máquina
Conceitos gerais
Instruções

Uma ramificação é uma instrução em um programa de computador que pode fazer com que um computador comece a executar uma sequência de instruções diferente e, portanto, desvie de seu comportamento padrão de execução de instruções em ordem. Ramificação (ou ramificação , ramificada ) também pode se referir ao ato de alternar a execução para uma sequência de instrução diferente como resultado da execução de uma instrução de ramificação. As instruções de desvio são usadas para implementar o fluxo de controle em loops de programa e condicionais (ou seja, executar uma sequência particular de instruções somente se certas condições forem satisfeitas).

Uma instrução de desvio pode ser um desvio incondicional , que sempre resulta em desvio, ou um desvio condicional , que pode ou não causar desvio, dependendo de alguma condição. Além disso, dependendo de como especifica o endereço da nova sequência de instrução (o endereço de "destino"), uma instrução de desvio é geralmente classificada como direta , indireta ou relativa , o que significa que a instrução contém o endereço de destino ou especifica onde o destino o endereço deve ser encontrado (por exemplo, um registro ou localização na memória) ou especifica a diferença entre os endereços atual e de destino.

Implementação

Mecanicamente, uma instrução de desvio pode alterar o contador de programa (PC) de uma CPU . O contador do programa armazena o endereço de memória da próxima instrução a ser executada. Portanto, uma ramificação pode fazer com que a CPU comece a buscar suas instruções em uma sequência diferente de células de memória.

As instruções de ramificação no nível da máquina às vezes são chamadas de instruções de salto . As instruções de salto no nível da máquina normalmente têm formas incondicionais e condicionais , em que a última pode ser assumida ou não, dependendo de alguma condição. Normalmente, existem formas distintas para saltos unilaterais, frequentemente chamados de salto e invocações de sub-rotina conhecidas como chamada, que salvam automaticamente o endereço de origem como um endereço de retorno na pilha, permitindo que uma única sub-rotina seja chamada de vários locais no código.

Quando um desvio é obtido , o contador do programa da CPU é definido como o argumento da instrução de salto. Portanto, a próxima instrução se torna a instrução naquele endereço na memória . Portanto, o fluxo de controle muda.

Quando uma ramificação não é obtida , o contador do programa da CPU permanece inalterado. Portanto, a próxima instrução executada é a instrução após a instrução de desvio. Portanto, o fluxo de controle permanece inalterado.

O termo branch pode ser usado quando se refere a programas em linguagens de alto nível, bem como a programas escritos em código de máquina ou linguagem assembly . Em linguagens de programação de alto nível , os desvios geralmente assumem a forma de declarações condicionais de várias formas que encapsulam a sequência de instruções que será executada se as condições forem satisfeitas. Instruções de desvio incondicional, como GOTO, são usadas para "pular" incondicionalmente para (iniciar a execução de) uma seqüência de instrução diferente.

Em CPUs com registradores de sinalização , uma instrução anterior define uma condição no registrador de sinalização. A instrução anterior pode ser aritmética ou uma instrução lógica . Muitas vezes está perto do branch, embora não necessariamente a instrução imediatamente antes do branch. A condição armazenada é então usada em uma ramificação, como jump if overflow-flag set . Essas informações temporárias geralmente são armazenadas em um registro de sinalização, mas também podem estar localizadas em outro lugar. Um projeto de registro de bandeira é simples em computadores simples e lentos. Em computadores rápidos, um registrador de sinalizador pode colocar um gargalo na velocidade, porque as instruções que poderiam operar em paralelo (em várias unidades de execução ) precisam definir os bits de sinalizador em uma sequência particular.

Existem também máquinas (ou instruções particulares) onde a condição pode ser verificada pela própria instrução de salto, como o branch <label> se o registrador X for negativo . Em projetos de computador simples, os ramos de comparação executam mais aritmética e podem usar mais potência do que os ramos de registro de flag. Em projetos de computador rápidos, os ramos de comparação podem ser executados mais rapidamente do que os ramos de registro de sinalização, porque os ramos de comparação podem acessar os registros com mais paralelismo, usando os mesmos mecanismos de CPU como cálculo.

Algumas arquiteturas de CPU antigas e simples, ainda encontradas em microcontroladores, podem não implementar um salto condicional, mas apenas uma operação condicional de "pular a próxima instrução". Um salto condicional ou chamada é então implementado como um salto condicional de um salto incondicional ou instrução de chamada.

Exemplos

Dependendo da arquitetura do computador , o mnemônico em linguagem assembly para uma instrução de salto é normalmente alguma forma abreviada da palavra salto ou ramo da palavra , geralmente junto com outras letras informativas (ou um parâmetro extra) que representam a condição. Às vezes, outros detalhes também são incluídos, como o intervalo do salto (o tamanho do deslocamento) ou um modo de endereçamento especial que deve ser usado para localizar o deslocamento efetivo real.

Esta tabela lista as instruções de ramificação ou salto no nível da máquina encontradas em várias arquiteturas conhecidas:

condição ou resultado x86 PDP-11, VAX ARM (parcialmente 6502) equação
zero (implica igual para sub / cmp) JZ; JNZ BEQ; BNE BEQ; BNE zero; não zero
negativo (N), sinal (S) ou menos (M) JS; JNS IMC; BPL IMC; BPL negativo; não negativo
estouro aritmético (bandeira chamada O ou V) JO; JNO BVS; BVC BVS; BVC transbordar; não transbordar
carry (de add, cmp, shift, etc.) JC; JNC BCS; BCC BCS; BCC carregar; não carrega
sem sinal abaixo (inferior) JB BLO BLO * pedir emprestado
sem sinal abaixo ou igual (menor ou igual) JBE BLOS BLS * pedir emprestado ou zero
sem sinal acima ou igual (superior ou igual) JAE BHIS BHS * não pedir emprestado
acima sem sinal (superior) JA BHI BHI * não pedir emprestado e não zero
assinado menos que JL BLT BLT sinal ≠ estouro
assinado menor ou igual JLE BLE BLE (sinal ≠ estouro) ou zero
assinado maior ou igual JGE BGE BGE sinal = estouro
assinado maior que JG BGT BGT (sinal = estouro) e não zero

* x86, o PDP-11, VAX e alguns outros, defina o sinalizador de transporte para sinalizar empréstimo e limpar o sinalizador de transporte para não sinalizar empréstimo . ARM, 6502 , o PIC e alguns outros, fazem o oposto para operações subtrativas. Esta função invertida do sinalizador de transporte para certas instruções é marcada por ( * ), ou seja, emprestar = não transportar em algumas partes da tabela, mas se não for indicado de outra forma, emprestar≡carry. No entanto, as operações aditivas continuadas são tratadas da mesma maneira pela maioria das arquiteturas.

Problemas de desempenho com instruções de filial

Para alcançar alto desempenho, processadores modernos são colocados em pipeline . Eles consistem em várias partes em que cada uma processa parcialmente uma instrução, alimenta seus resultados para o próximo estágio do pipeline e começa a trabalhar na próxima instrução do programa. Este projeto espera que as instruções sejam executadas em uma sequência imutável particular. As instruções de desvio condicional tornam impossível saber esta sequência. Portanto, os desvios condicionais podem causar "paralisações" nas quais o pipeline precisa ser reiniciado em uma parte diferente do programa.

Melhorar o desempenho reduzindo as paradas nas filiais

Diversas técnicas melhoram a velocidade reduzindo as interrupções de ramificações condicionais.

Dicas de previsão de ramos

Historicamente, a previsão de ramificação tomava estatísticas e usava o resultado para otimizar o código. Um programador compilaria uma versão de teste de um programa e executaria com dados de teste. O código de teste contou como os ramos foram realmente obtidos. As estatísticas do código de teste foram então usadas pelo compilador para otimizar as ramificações do código lançado. A otimização faria com que a direção de ramificação mais rápida (tomada ou não) fosse sempre o caminho de fluxo de controle mais frequentemente usado. Para permitir isso, as CPUs devem ser projetadas com (ou pelo menos ter) temporização de ramificação previsível. Algumas CPUs têm conjuntos de instruções (como o Power ISA ) que foram projetados com "dicas de ramificação" para que um compilador possa dizer a uma CPU como cada ramificação deve ser tomada.

O problema com a previsão de ramos de software é que ela requer um processo complexo de desenvolvimento de software.

Preditores de ramificação de hardware

Para executar qualquer software, os preditores de ramificação de hardware moviam as estatísticas para a eletrônica. Os preditores de ramificação são partes de um processador que adivinham o resultado de uma ramificação condicional. Então, a lógica do processador aposta na suposição, começando a executar o fluxo de instrução esperado. Um exemplo de um esquema simples de previsão de desvio de hardware é assumir que todos os desvios para trás (ou seja, para um contador de programa menor) são tomados (porque são parte de um loop), e todos os desvios para frente (para um contador de programa maior) não são tomados (porque eles deixam um loop). Melhores preditores de ramificação são desenvolvidos e validados estatisticamente, executando-os em simulação em uma variedade de programas de teste. Bons preditores geralmente contam os resultados de execuções anteriores de um ramo. Computadores mais rápidos e caros podem ser executados com mais rapidez, investindo em melhores componentes eletrônicos de previsão de ramos. Em uma CPU com previsão de ramificação de hardware, as dicas de ramificação permitem que a previsão de ramificação supostamente superior do compilador substitua a previsão de ramificação mais simplista do hardware.

Código livre de filial

Alguma lógica pode ser escrita sem ramificações ou com menos ramificações. Freqüentemente, é possível usar operações bit a bit , movimentos condicionais ou outra predicação em vez de desvios. Na verdade, o código sem ramificação é obrigatório para a criptografia devido a ataques de temporização .

Delay slot

Outra técnica é um slot de atraso de ramificação . Nesta abordagem, uma instrução após um desvio é sempre executada. Portanto, o computador pode usar essa instrução para fazer um trabalho útil, independentemente de o pipeline travar ou não. Essa abordagem foi historicamente popular em computadores RISC . Em uma família de CPUs compatíveis, isso complica CPUs multiciclo (sem pipeline), CPUs mais rápidas com pipelines mais longos do que o esperado e CPUs superescalares (que podem executar instruções fora de ordem).

Veja também

Notas

Referências

links externos