Número mínimo teórico de registros para um computador moderno?

Fiz um curso sobre compiladores em meus estudos de graduação, nos quais escrevemos um compilador que compila programas de origem em uma linguagem semelhante a Java de brinquedo a uma linguagem de montagem de brinquedos (para a qual tínhamos um intérprete). No projeto, fizemos algumas suposições sobre a máquina de destino intimamente relacionada aos executáveis nativos "reais", incluindo:

uma pilha de tempo de execução, rastreada por um registro apontador de pilha dedicado ("SP")
um heap para alocação dinâmica de objetos, rastreado por um registro dedicado de heap pointer ("HP")
um registro de contador de programa dedicado ("PC")
a máquina de destino possui 16 registros
operações em dados (em oposição a, por exemplo, saltos) são operações de registro a registro

Quando chegamos à unidade usando a alocação de registros como uma otimização, fiquei me perguntando: qual é o número mínimo teórico de registros para uma máquina dessas? Você pode ver pelas nossas suposições que usamos cinco registradores (SP, HP, PC, mais dois para armazenamento como operações binárias) em nosso compilador. Embora otimizações como a alocação de registros certamente possam fazer uso de mais registros, existe uma maneira de sobreviver com menos, mantendo estruturas como a pilha e a pilha? Suponho que, com o endereçamento de registro (operações de registro para registro), precisamos de pelo menos dois registros, mas precisamos de mais de dois?

compilers computer-architecture BlueBomber
fonte

Um "ponteiro de pilha" parece uma idéia estranha. Porque, ao contrário da pilha, a pilha não é LIFO e não se reduz à semântica push / pop. Você deve ver a alocação dinâmica de memória como chamadas para rotinas malloc / free.

Yves Daoust

Respostas:

Se você permitir o acesso direto à memória por endereço de memória, não precisará de "registros", pois poderá usar os locais de memória. Por exemplo, a memória no local 0 pode ser o contador do programa, no local 1 temos o ponteiro da pilha, etc. Mas isso é trapaça.

Portanto, para nos impedir de trapacear, suponhamos que não haja acesso direto à memória, pois poderíamos usar locais fixos de memória como registradores. Em seguida, podemos obter dois registros, um contador de programa e um ponteiro de pilha, conforme explicado no artigo da Wikipedia sobre máquinas de pilha . A pilha é acessível apenas através do ponteiro da pilha e o programa é acessível apenas através do contador de programas.

Outra possibilidade é usar máquinas de balcão. Uma máquina de dois contadores é Turing completa, ou seja, pode calcular o que a máquina Turing puder. Isso novamente é bem explicado no artigo da Wikipedia sobre máquinas de balcão .

Andrej Bauer
fonte

Obrigado pela resposta! O artigo sobre máquinas de pilha menciona, no entanto, que a máquina é capaz de acessar diretamente a memória (para executar operações nos elementos mais altos da pilha e empurrar o resultado de volta), de modo que ainda está trapaceando, certo? Quanto à máquina de balcão, li esse artigo. Também li uma prova semelhante do TC de 2 CM, mas ambos envolvem efetivamente o armazenamento de toda a RAM em dois registros, o que me parece ainda mais trapaça.

precisa saber é o seguinte

Bem, em algum momento, não está mais trapaceando. As operações de pilha não estão trapaceando, desde que não permitam o acesso direto a um local fixo na memória. Não há problema em poder, por exemplo, girar os três elementos mais altos da pilha. Sua pergunta é um pouco estranha, de qualquer forma, por isso não vale a pena ficar obcecado com o que é e não está trapaceando.

Andrej Bauer

Mais uma vez obrigado pela resposta. Sempre que o tópico se relaciona com limites teóricos, trapacear é ainda menos aceitável! Isso não significa que não seja instrutivo. O ponto em que não está trapaceando é quando, bem, não há trapaça, eu acho. Eu achei sua resposta inicial informativa, mas o problema é que nosso modelo se sobrepõe a todos os modelos de Turing Machine, Counter Machine e Stack Machine e, considerando nossas premissas (incluindo muitos registros finitos finitos e nenhum acesso direto à memória), podemos entender com apenas dois registros?

precisa saber é o seguinte

Acho a pergunta estranha, porque é difícil definir conceitos do mundo real, como processador, registro, acesso à memória, etc., mas você precisa deles para poder provar qualquer coisa. Portanto, o resultado final será que tudo o que você provar é fácil, mas depende muito de como você formaliza a pergunta (qual é a sua noção teórica de "processador", "registro", "memória" etc.).

21413 Andrej Bauer

Um livro de compilador não nos permite provar muito, pelo menos não no sentido matemático da palavra "provar". Você precisa dar um passo adiante na formalização do hardware para chegar a algo que permita a prova . De qualquer forma, estamos dividindo cabelos, e eu já te dei minha melhor resposta.

Andrej Bauer

A arquitetura PIC, introduzida pela General Instruments na década de 1970 e ainda hoje em uso, possuía os seguintes registros:

W register (not addressible)
01    Timer/Counter
02    Program Counter
03    Status
04    File-Select Register
05-07 One register for each I/O port
08-1F General-purpose registers/"memory"

Uma instrução típica lê um registro, executa uma computação usando o valor lido e W e, em seguida, armazena o resultado da computação em W ou no registro que foi lido. Um dos cálculos disponíveis gera "o valor lido, ignorando W"; outro é "pegue W, ignorando o valor lido". Os padrões de bits que corresponderiam a "leia XX, depois use W, ignorando o valor lido e armazene o resultado em W" são usados para NOP, bem como para uma variedade de instruções especiais.

Para permitir cálculos de endereços, a unidade de execução do processador observará as instruções que codificam um endereço 00 e substitui o conteúdo do Registro de Seleção de Arquivos pelo endereço.

Embora ter que alimentar todos os valores através do registro W possa ser um gargalo, a arquitetura PIC tem um conjunto de trabalho maior que outras arquiteturas, usando a mesma palavra de instrução de comprimento. No PIC16C54 (ainda hoje fabricado e muito semelhante aos PICs da década de 1970), as instruções têm 12 bits. Em muitas outras partes 16Cxx ou 16Fxx, as instruções têm 14 bits e podem acessar diretamente um espaço de endereço de 128 bytes. Se o conjunto de trabalho de um programa se encaixa bem com o conjunto de trabalho do conjunto de instruções, uma declaração como "total + = valor", em que "total" e "valor" são do tipo unsigned char, será compilada para:

movf  value,w
addwf total,f

Em algo como o ARM, mesmo que alguém tenha um registro pré-carregado com o endereço base de suas variáveis, o código seria mais como:

ldr    r0,[r7+value]
ldr    r1,[r7+total]
add    r1,r1,r0
str    r1,[r7+total]

Em muitos casos, um compilador poderia evitar fazer cargas e armazenamentos a cada operação, mas em algo como o PIC, os benefícios de um conjunto de trabalho maior às vezes superam as limitações de ter que passar por W o tempo todo.

supercat
fonte