SDCC: Algumas considerações sobre o Z80…

Escrevendo o artigo nostálgico sobre Z80 e 6502 testei o SDCC (Small Devices C Compiler) criando pequenos códigos. Eu pretendia mostrar como um código simples (checksum ou obter o maior valor contido num array) ficariam, para esses processadores. Minha surpresa é que o SDCC cria código ineficiente.

A primeira coisa a fazer aqui é determinar qual é a convenção de chamada usada pelo SDCC. Para isso vou compilar funções simples:

char f(void)   { return '0'; }
char g(char c) { return c + '0'; }
int  h(void)   { return -1; }
int  i(int x)  { return x - 1; }

Isso cria código como mostrado abaixo:

_f:
  ld  l,#0x30       ; L = '0'.
  ret

_g:
  ld  hl, #2
  add hl, sp        ; HL = SP+2
  ld  a, (hl)       ; A = c
  add a, #0x30      ; A += '0'
  ld  l,a
  ret

_h:
  ld  hl,#0xFFFF    ; HL = -1
  ret

_i:
  ld  hl, #2
  add hl, sp        ; HL aponta para x, na pilha.

  ld  e, (hl)       ; DE = (HL).
  inc hl
  ld  d, (hl)

  dec de            ; HL = DE - 1
  ex  de,hl
  ret

Ao que parece, os valores de retorno são sempre feito em L ou no par HL e o acumulador, bem como o par DE, podem ser modificados à vontade (não precisam ser preservados entre chamadas). E, também, os argumentos da função são sempre passados pela pilha.

Para determinar melhor a convenção de chamadas, devemos lidar com rotinas mais complexas, para observar a alocação dos registradores e, se necessário, como as variáveis locais são alocadas na própria pilha. Por exemplo, uma rotina mais elaborada, checksum, poderia ser útil:

#include <stdint.h>
#include <stdlib.h>

uint16_t cksum(uint8_t *p, size_t size)
{
  uint16_t sum;

  for (sum = 0; size--; )
    sum += *p++;

  return sum;
}

E, eis o código que o SDCC cria:

_cksum:
  push  ix        ; Salva IX para usá-lo como
  ld    ix,#0     ; ponteiro auxiliar para a pilha.
  add   ix,sp

  push  af        ; Cria espaço para cópia do ponteiro p.

  ld    de,#0     ; DE é 'sum'.

  ; Copia 'p' para variável local, na pilha.
  ld    a,(ix+4)
  ld    (ix-2),a
  ld    a,(ix+5)
  ld    (ix-1),a

  ; BC contém 'size'
  ld    c,(ix+6)
  ld    b,(ix+7)

00103$:
  ld    h,c       ; HL <- BC
  ld    l,b
  dec   bc        ; size--;

  ; size == 0?
  ld    a,l
  or    a,h
  jr    Z,00101$   ; Se 'size==0', sai da rotina.

  pop   hl        ; Recupera 'p' da pilha.
  push  hl

  ld    l,(hl)    ; L <- *p

  ; Incrementa p (na pilha)
  inc   (ix-2)
  jr    NZ,00116$
  inc   (ix-1)

  ; sum += *p;
00116$:
  ld    h,#0x00
  add   hl,de
  ex    de,hl
  jr    00103$

  ; Coloca DE em HL, recupera SP, limpa a pilha e sai.
00101$:
  ex    de,hl
  ld    sp, ix
  pop   ix
  ret

Aqui podemos extrapolar que AF e BC também não são preservados. Aliás, ao que parece, apenas os registradores de índice IX e IY (se usado) e o SP (por motivos óbvios) devem ser preservados… Lembrando que os retornos são feitos em L ou HL. E, mesmo no caso de retornos de tipos de 8 bits, o registrador H não precisa ser preservado (como pode ser visto na função g, lá em cima).

Uma coisa estranha no código criado pelo SDCC é que ele preferiu manter uma cópia do ponteiro ‘p’ na pilha, ao invés da variável local ‘sum’… E a rotina ficou maior do que poderia ser, respeitando os critérios do compilador. Eis como eu a implementaria, se fosse o compilador:

_cksum:
  push ix
  ld   ix,#0
  add  ix,sp

  ld   h,(ix+4)   ; HL <- p
  ld   l,(ix+5)
  ld   b,(ix+6)   ; BC <- size
  ld   c,(ix+7)

  ld   de,#0      ; DE <- 0

.loop:
  ld   a,b        ; if (BC == 0) goto .exit;
  or   c
  jr   z,.exit

  dec  bc         ; BC--;

  ld   a,e        ; DE += *p;
  add  a,(hl)
  ld   e,a
  ld   a,d
  adc  a,#0
  ld   d,a

  inc  hl         ; p++;

  jr   .loop

.exit:
  ex   de,hl      ; HL <- DE.
  pop  ix
  ret

Não há necessidade de variáveis locais alocadas na pilha e a rotina acima é 6 instruções menor que a anterior. Ainda, o loop principal é mais curto!

Claro que o SDCC foi esperto ao usar o par HL, com H zerado, para acumular, em DE, o checksum, mas não foi muito esperto ao usar uma variável local, na pilha, para manter a cópia do ponteiro p. Outro fato interessante é que eu não confio que (IX-2) será calculado corretamente, já que as instruções que usam IX dessa maneira indireta adicionam um byte ao registrador de 16 bits. Ou seja, -2 é 0xFE e não 0xFFFE… Isso é uma desconfiança minha e é bem possível que essa adição seja feita considerando o sinal do offset (é provável que seja assim).

Deixe-me lembrá-lo que o processador Z80, assim como outros de 8 bits, não possuem cache (nem de dados, nem de código). Não possuem “reordenador” de instruções, não possuem arquitetura superescalar, não possuem “branch prediction”, etc… Cada instrução e cada acesso à memória adicional conta. A regra para otimização de código para esses processadores é: Menos instruções e menos acessos à memória, além, é claro, de bons algoritmos.

Anúncios

Processadores de 8 bits: MOS Tech 6502 e Zilog Z80

O primeiro processador que estudei, e no qual consegui colocar minhas mãos, foi o Zilog Z80. Ele foi concebido para ter compatibilidade binária com o 8080 da Intel, mas sofreu diversos avanços significativos. Um exemplo foi a criação do sinal de “interrupção não mascarável” (que só veio a estar disponível nos processadores de Intel à partir do 8085). Outras modificações foram um instruction set mais rico e a adição de dois registradores de índice de 16 bits cada (IX e IY)… O Z80 também tinha dois conjuntos de registradores de uso geral que podiam ser chaveados (nunca usados “ao mesmo tempo”). Isso era útil em rotinas de tratamento de interrupção, já que o conjunto original podia ser preservado facilmente.

No final dos anos 80 coloquei as mãos num Apple ][+, da Microdigital. Como todo Apple ][, ele tinha o processador 6502 da MOS Technologies. Foi o primeiro processador RISC que vi. Diferente do Z80, ele tinha um conjunto realmente restrito, tanto de registradores de uso geral (somente 3, de 8 bits cada: A, X e Y) quanto de instruções… Enquanto o Z80 tinha instruções estendidas, o 6502 só suportava menos que 256 instruções (cada opcode ocupa apenas um byte, seguido do operando).

Para facilitar minha vida aqui e escrever o mínimo possível, vou falar primeiro sobre o 6502, deixando o Z80 para a segunda parte.

MOS Tech 6502:

O 6502 foi muito usado, à partir do final dos anos 70, nos primeiros vídeo games (notoriamente, o ATARI 2600) e até mesmo em arcades. Alguns microcomputadores ficaram bem famosos, como o Apple ][ e o Commodore 64. O motivo foi sua simplicidade.

Atari 2600 e Commodore 64

Existem apenas 3 registradores de uso geral de 8 bits (A, X e Y), os registradores PC (Program Counter), S (Stack pointer) e P (Processor status register) e também um conjunto pequeno de instruções. Há também alguns “atalhos” que não estão presentes em processadores derivados da arquitetura Intel 8080. Por exemplo, ao carregar um registrador os flags de zero (Z) e sinal (S) são automaticamente afetados. Nos Z80, por exemplo, uma operação lógica ou aritmética tem que ser executada para afetar flags (é assim até hoje na arquitetura x86).

As instruções são bem simples e descritivas e temos menos que 256:

opcodes do 6502 (65C02 tem mais!)

Repare como algumas instruções e/ou modos de endereçamento estão agrupados… Isso também facilitava ao desenvolvedor “decorar” os opcodes! Quando aos modos de endereçamento, instruções que exigem algum operando podem tê-lo expresso de diversas formas:

  • Valor imediato: É o caso de instruções como LDA #0, por exemplo, onde o valor 0 é colocado em A. O símbolo # é usado para denotar “imediato”. Sem esse símbolo, estaremos escrevendo um endereço de memória;
  • Página zero: Um endereço de memória no 6502 tem 16 bits de tamanho. O byte superior deste endereço é chamado de página. Podemos omitir a página de um endereço se essa for zero, como em LDA $3F. Aqui $3F é o endereço, em hexadecimal, $003F, mas a instrução só ocupará 2 bytes. Note, também, o uso de $ para denotar valores em hexadecimal;
  • Absoluto: Trata-se do endereço completo de 16 bits, como em LDA $C010.
  • Indexado: É a mesma coisa que o absoluto ou página zero, mas usa um dos registradores, X ou Y, como índice. Como em LDA $40,X ou LDA $C000,Y;
  • Indireto: O operando é um ponteiro (um endereço) de onde será lido o endereço alvo. Como em LDA ($40). Aqui, em $40 e $41 teremos 2 bytes que formam um endereço de 16 bits. Este endereço é que será usado para obter o byte que será colocado em A;
  • Indireto Indexado: Existem dois tipos, um antes e outro após a indireção. LDA ($40),X obtém o endereço lendo 16 bits à partir de $40 e depois soma a X para, só então, usar esse valor como ponteiro. Já LDA ($40,X) adiciona X à zero page $40 para obter o endereço de onde o byte será lido, como no modo indireto normal.

Existem outros argumentos, como os de saltos e chamadas. Neste caso, dependendo da instrução, o operando pode ser um endereço absoluto (16 bits) ou relativo (8 bits). Da mesma forma como acontece nos processadores da família x86, os endereços relativos são adicionados ao valor de PC.

Olhando de novo para a tabela acima temos instruções de carga e armazenamento (por exemplo, LDA carrega [load] A, STA armazena [store] A); adição e subtração sempre usando o flag carry (ADC e SBC); incrementos e decrementos (INA, INX, INY, DEA, DEX e DEY); comparações (CMP, CPX e CPY); operações lógicas (AND, ORA e EOR [mas não existe NOT, que pode ser feito com EOR #$FF!]); outras operações lógicas binárias (BIT, ASL, LSR, ROL e ROR); manipulação de pilha (PHA, PLA, PHP e PLP); manipulação de flags (CLc e SEc) e saltos (JSR, JMP, Bcc, RTS e RTI). Repare que c deverá ser substituído por um dos flags e cc pela comparação desejada: EQ (equal ou Z=1), NE (not equal ou Z=0) MI (minus ou S=1), PL (plus ou S=0), CS (carry set), CC (carry clear), VC e VS (oVerflow clear e oVerflow set). Ah, e existem também as instruções de transferência entre A, X e Y (TAX, TAY, TXA e TYA) e uma instrução especial, BRK, que gerará uma interrupção de “break” (raramente usada).

A versão mais “nova” do 6502, o 65C02, tem alguns instruções a mais, preenchendo o espaço vago na tabela acima. A maioria dos usuários brasileiros desses processadores em microcomputadores, no final dos anos 80, vai se lembrar do TK-2000, quando se fala em 65C02, mas o micro de grande sucesso da Apple que usava esse processador, na época, foi o Apple ][e.

O Apple ][e
Zilog Z80:

O processador Z80 é o primo rico distante da atual arquitetura 80×86. Ele é derivado do antigo 8080, de 8 bits, com um montão de melhorias. Dentre elas, modos de endereçamento melhorados, novas instruções e mais registradores de uso geral.

No antigo 8080 e 8085 tínhamos os registradores A, B, C, D, E, H e L, de 8 bits cada, bem como SP (Stack Pointer), Flags (F) e PC (Program Counter). O Z80 acrescentou um segundo conjunto de uso geral (A', B', C', D', E', H' e L'), bem como os registradores de índice (de 16 bits cada) IX e IY e seus “espelhos” (IX' e IY'), além do espelho dos flags (F'… No 8080 era possível emparelhar apenas os registradores H e L para formar um pseudo registrador chamado M (de “Memória”), que era usado como ponteiro, mas o Z80 permite o emparelhamento BC, DE e no caso de operações de manipulação de pilha, AF.

Não é difícil perceber que a arquitetura 80×86 aproveitou a nomenclatura usada no 8080 de A até D, embora, exceto pelo registrador A, os demais não tinham finalidades bem definidas. No Z80 isso foge um pouco à regra, já que instruções como LDI e LDD (e suas equivalentes com “repetição”), por exemplo, sugerem usos específicos para DE (DE de DEstination).

A matriz do conjunto de instruções do Z80 é grande o suficiente para que fique impraticável mostrá-la aqui de forma reduzida. Você pode vê-la neste link, se quiser.

Assim como no caso do 6502, as operações aritméticas e lógicas são todas feitas tomando como o primeiro operando o registrador A e, geralmente, essas são as únicas instruções que afetam os flags. Assim como o 6502, não existe uma operação NOT, que pode ser efetuada com o XOR contra o valor imediato 0xFF… Mas, diferente do 6502, existem muitas instruções estendidas. Por exemplo, ADD e ADC coexistem, bem como SUB e SBB (onde borrow é o inverso de carry). A quantidade de instruções relacionadas a shifts e rotações é mais rica e temos até instruções para ajustes de valores BCD (Binary Coded Decimal), assim como acontece na família 80×86, exceto no modo x86-64.

No Z80 também é possível carregar um par de registradores com um valor imediato de 16 bits, como em LD HL,0123h, ou via indireção, como em LD HL,(8000h). E, falando em indireção, já que temos um conjunto de registradores de uso geral maior e que podem ser emparelhados, a indireção é mais simples do que a do 6502. A notação entre parênteses simplesmente significa que o que encontra-se entre eles é o endereço onde um byte ou word serão lidos – o esquema de indireção dupla do 6502 é desnecessário.

Existem também instruções especializadas. DJNZ, por exemplo, realiza um salto se, depois de decrementar o registrador B, este não chegou a zero. É como se fosse:

// Equivalente de 'DJNZ addr', em C:
if (--B) goto addr;

As instruções LDI e LDD são instruções de movimentação de blocos. Elas copiam um byte que está apontado por DE para o endereço apontado por HL. A diferença é que LDI incrementa HL e DE e LDD decrementa-os… Mas, também existem LDIR e LDDR, que fazem a mesma coisa, mas usam BC como contador de repetições. Instruções de manipulação de blocos também estão associadas com CP (de ComParação), IN e OUT, na forma de CPI e CPD (e suas equivalentes terminadas em R), acontecendo o mesmo para as demais.

Exemplos de micros com o Z80, no Brasil

Z80 versus 6502:

Durante o final dos anos 70 e até meados dos anos 80 existiu uma verdadeira guerra entre entusiastas de microcomputadores baseados no 6502 (Commodore 64 e Apple ][) e Z80 (onde o maior falatório vinha da turma do TRS-80)… Do ponto de vista dos processadores, o Z80 deveria ganhar de carroçada, mas… O 6502, por ser RISC, tinha um clock reduzido (1 MHz), mas executava código tão rápido quanto o Z80… O Z80, por sua vez, aceitava clock de 4 MHz e, em teoria, poderia ter hardware associado a ele até 4 vezes mais rápido.

Dos micros que usavam o 6502 surgiram softwares sérios que são usados até hoje, pelo menos ao nível conceitual. Por exemplo, a planilha de cálculo surgiu no Apple ][ e chamava-se Visicalc (surgiu em 1979 e foi totalmente escrita em assembly para o 6502).

Essa era a cara do Visicalc.

Originalmente o Visicalc não foi desenvolvido para o Apple ][, mas para o precursor do UNIX (O Multics, mas sob o processador 6502!). Mas foi no Apple ][ que o mundo conheceu a planilha de cálculo eletrônica… Somente em 1983 surgiu uma versão para o PC: O Lotus 1-2-3.

O primeiro filesystem para microcomputadores que tenho notícia, e que suportava nomes “longos”, foi o Apple DOS. Os TRS-80 adotavam o modelo do CP/M-80, usando nomes de 8.3 caracteres (e os drives A: e B:). A diferença é que no DOS dos TRS-80 o separador entre o nome do arquivo e sua extensão era uma ‘/’ e as extensões executáveis tendiam a ser nomeadas ‘/CMD’. O programinha “Dancing Demon” da Radio Shack, se não me engano, era “DEMON/CMD”:

O padrão usado pelo CP/M-80 seguido pela IBM no PC-DOS e pela Microsoft (“criadora” do PC-DOS, que mais tarde viria a ser chamado de MS-DOS), até a criação do Windows NT e a popularização do Windows 95 (já nas versões beta, chamadas de projeto Chicago).

Outra vantagem dos micros com 6502 é que eles eram COLORIDOS. Os TRS-80 jamais foram e os PCs só vieram a sê-lo quando os monitores coloridos começaram ser popularizados. Mas, os Apple ][ e Commodores não precisavam de monitores, bastava uma TV. Eis uma comparação (Karateka, no Apple ][):

Tela de um diretório (catálogo) do Apple DOS

Não me pergunte o significado desses atributos *A, *B, *I e *T porque não me lembro mesmo!

Retornando tipos complexos

Já falei por aqui sobre as diversas convenções de chamada para os modos i386 e x86-64 e uma das coisas que disse é que, no caso do modo x86-64, o registrador RAX é sempre usado como valor de retorno. Seja para retornar um simples int, seja para retornar um ponteiro… Mas, o que acontece se quisermos retornar uma estrutura? Note bem, não um ponteiro para uma estrutura, mas toda ela? Vejamos:

struct vertice_s {
  float x, y, z, w; // Coordinate (homogeneous);
  float nx, ny, nz; // Normal vector;
  float r, g, b, a; // Color;
  float u, v;       // Texture coordinate;
};

struct vertice_s assign(void)
{
  struct vertice_s v;

  v.x = v.y = v.z =
  v.nx = v.ny = v.nz =
  v.r = v.g = v.b =
  v.u = v.v = 0.0f;
  v.w = v.a = 1.0f;

  return v;
}

void assign2(struct vertice_s *p)
{
  p->x = p->y = p->z =
  p->nx = p->ny = p->nz =
  p->r = p->g = p->b =
  p->u = p->v = 0.0f;
  p->w = p->a = 1.0f;
}

Aqui, a função assign() apaentemente retorna toda a estrutura local à função. No outro caso, na função assign2 passamos um ponteiro para uma estrutura e lidamos com ele dentro da função. Supreendentemente, ambas as funções fazem quase exatamente a mesma coisa. Isso pode ser observado obtendo a listagem em assembly:

bits 64

section .rodata
float1: dd 1.0

section .text

global assign
global assign2

assign:
  pxor  xmm0, xmm0
  mov   rax, rdi
  movss xmm1, dword [float1]
  movss dword [rdi+12], xmm1
  movss dword [rdi], xmm0
  movss dword [rdi+4], xmm0
  movss dword [rdi+8], xmm0
  movss dword [rdi+16], xmm0
  movss dword [rdi+20], xmm0
  movss dword [rdi+24], xmm0
  movss dword [rdi+28], xmm0
  movss dword [rdi+32], xmm0
  movss dword [rdi+36], xmm0
  movss dword [rdi+40], xmm1
  movss dword [rdi+44], xmm0
  movss dword [rdi+48], xmm0
  ret

assign2:
  pxor  xmm0, xmm0
  movss dword [rdi+48], xmm0
  movss dword [rdi+44], xmm0
  movss dword [rdi+36], xmm0
  movss dword [rdi+32], xmm0
  movss dword [rdi+28], xmm0
  movss dword [rdi+24], xmm0
  movss dword [rdi+20], xmm0
  movss dword [rdi+16], xmm0
  movss dword [rdi+8], xmm0
  movss dword [rdi+4], xmm0
  movss dword [rdi], xmm0
  movss xmm0, dword [float1]
  movss dword [rdi+40], xmm0
  movss dword [rdi+12], xmm0
  ret

A diferença óbvia é que assign retorna o ponteiro para a estrutura apontada por RDI em RAX, como se tivéssemos passado esse ponteiro para a função! A função gasta o mesmo tempo que a sua irmã, assign2, uma vez que, devido à reordenação automática nos processadores mais modernos (Ivy Bridge em diante, pelo menos), mov rax,rdi provavelmente não gastará ciclo algum.

Repare que o compilador é esperto o suficiente para perceber que se quisermos retornar uma estrutura por valor, ela terá que ser assinalada para algum objeto e esse objeto tem um endereço na memória. Se esse objeto estiver alocado na própria pilha (for uma variável local na função chamadora), RDI apontará para a pilha, caso contrário, para uma região no segmento de dados. Eis um exemplo:

extern struct vertice_s assign(void);

// Não nos interessa a imlpementação dessa função agora!
extern void showvertice(struct vertice_s *);

void f(void)
{
  struct vertice_s v;

  v = assign();
  showvertice(&v);
}

O que criará uma listagem mais ou menos assim:

f:
  sub  rsp,136   ; Aloca espaço para a estrutura.
  mov  rdi,rsp
  call assign
  mov  rdi,rsp
  call showvertice
  add  rsp,136   ; Dealoca o espaço.
  ret

Você obterá uma listagem um pouco maior que essa, dependendo das opções de compilação que usar, mas, em essência, é isso o que o compilador faz.

No modo i386 a coisa não é muito diferente. Lembre-se que no modo x86-64 o primeiro argumento da função é passado no registrador RDI. No caso do modo i386, este argumento é passado na pilha (na convenção cdecl), daí o endereço da estrutura estará apontada por RSP+4.

Em resumo: Não tenha medo de retornar estruturas e uniões por valor, é a mesma coisa que passar o ponteiro da estrutura no primeiro argumento. Mas, a coisa é bem diferente de passar argumentos por valor ou referência. Ao fazer:

void f(struct vertice_s v)
{
  struct vertice t;

  t = v;
  ...
}

Todo o conteúdo de v terá que ser copiado para dentro de t (embora o compilador possa decidir não fazê-lo, dependendo do resto da função!). Mas uma coisa é certa! Todo o conteúdo da estrutura terá que ser copiado para a pilha antes da chamada!

Então, tenha medo de passar argumentos por valor e prefira passá-los por referência (ponteiro)… mas, saiba que esse risco você não corre ao retornar por valor…

O problema das pizzas – Ou, o problema da ignorância da matemática elementar!?

Bem… não foi surpresa nenhuma pra mim perceber que algumas pessoas não conseguem aplicar conhecimentos fundamentais no dia a dia. Eis um problema (bem simples, que um estudando ensino fundamental deveria saber resolver, e um adulto também!) que propus, recentemente:

“Você resolveu comprar pizza para a família toda. Uma pizzaria oferece pizzas “médias” com raio de 30 cm e “grandes” com raio de 45 cm, ao preço de R$ 40,00 e R$ 50,00 cada uma, respectivamente. Você compraria duas pizzas médias ou uma grande?”

O detalhe é que o preço é irrelevante no problema. O que se quer saber é qual das duas configurações vai te dar mais pizza para comer: Duas médias ou uma grande?

Como disse, não é surpresa ver que a maioria das pessoas escolhe as duas pizzas médias, achando que terá mais pizza do que uma grande. Infelizmente a geometria plana elementar desmente isso, já que a “quantidade” de pizza é medida pela área da circunferência… Quanto a isso, obviamente o problema considera que uma pizza seja isto:

ISSO é uma pizza!

Fazendo um cálculo rápido, qualquer um pode observar que uma pizza grande, do problema proposto, é 12,5% maior que duas pizzas médias (área da pizza média. 900\pi, área da pizza grande, 2025\pi)! Isso levanta a questão: Será que estou perdendo dinheiro toda vez que compro pizzas? Quando é vantajoso comprar duas médias ao invés de uma grande? Well…

Considere r como sendo o raio da pizza média e R como sendo o raio da pizza grande. Valerá a pena comprar duas pizzas médias ao invés de uma grande se:

\displaystyle 2\pi r^2 > \pi R^2

Ou seja, \frac{R^2}{r^2} < 2 \Rightarrow R < r\sqrt{2} (estou ignorando o valor negativo que satisfaz a inequação por motivos óbvios!) . Isso quer dizer que o raio R tem que exceder menos que 41% do radio r para ser vantajoso comprar duas médias… No exemplo do problema, se a pizza grande tiver menos que 42 cm (30\sqrt{2}\approx42,4), vale à pena comprar duas médias…

Ahhh… Esse tipo de racionalização também deveria ser óbvio para qualquer pessoa que passou por uma escola…

Cuidado com as expressões…

Uma “linguagem de programação” geralmente é composta de sequências de operações, que são divididas em expressões aritméticas e operações de controle de fluxo (if..then..else, while, do…while, …). Humpf… E já ouvi gente dizendo que “programação nada tem a ver com matemática!”…

Como na aritmética e na álgebra, expressões devem ser avaliadas de acordo com a “importância” do operador. Por exemplo, ao fazermos x+y\cdot z, devemos multiplicar y e z antes de adicionarmos x. A isso damos o nome de precedência (no sentido de “o que vem antes”). Mas, como não temos apenas as 4 operações fundamentais da álgebra (+, -, × e ÷), todos os operadores têm que seguir alguma regra de precedência… Na linguagem C temos a seguinte tabela:

Ordem de precedência Operador Associatividade
1 ++, — (pós-incremento e pós-decremento)
() (chamada de função)
[]
.
->
(T){list} (composição)
E→D
2 ++, — (pré-incremento e pré-decremento)
+, – (unários)
!
~
(T) (casting)
* (indireção)
& (“endereço de”)
sizeof
_Alignof
D→E
3 *, /, % E→D
4 +, –
5 <<, >>
6 <, <=, >, >=
7 ==, !=
8 &
9 ^
10 |
11 &&
12 ||
13 ?: D→E
14 =, +=, -=, *=, /=, %=
&=, |=, ^=
<<=, >>=
15 , E→D

Quanto menor for a ordem de precedência, maior é o grau de precedência do operador, ou seja, ele será avaliado antes. Mas, como o leitor pode observar, isso não é suficiente. O termo “associatividade” significa “de que lado” devemos começar. Operadores como + e -, por exemplo, têm associatividade da esquerda para direita (E→D), significando que a sub expressão do lado esquerdo do operador deve ser avaliada antes da do lado direito.

Pôxa! Temos que decorar esses trecos de associatividade também? Não! Note que, além dos operadores de assinalamento, somente os operadores unários (que só têm um único argumento à direita) têm associatividade D→E, e isso faz todo sentido! As únicas exceções são os pós-incrementos e pós-decrementos, chamadas de função, arrays, e o pseudo-operador condicional ?:, que é problemático (às vezes) e recomendo (pela primeira vez neste texto) que seja evitado. Todos os outros operadores têm associatividade da esquerda para direita.

Note também que os operadores de assinalamento (= e seus primos) têm a mais baixa precedência de todos, exceto pelo operador vírgula e, portanto, serão avaliados por último. Por exemplo, numa expressão como:

*p = x + 1;

Temos 3 operadores: O de indireção (*), o de atribuição (=) e a adição (+). Nessa expressão o operador de indireção tem maior precedência (menor ordem), a adição tem precedência menor, mas a atribuição tem a mais baixa (maior ordem). Podemos entender a expressão acima como (*p)=(x+1). De acordo com a associatividade das operações e sabendo que o assinalamento é feito por último, a sub expressão da direita de = é resolvida primeiro e depois a expressão do lado esquerdo. Só então a atribuição é feita.

Existe, é claro, outra forma de entender isso: Uma expressão pode ser organizada numa árvore binária que pode ser percorrida de forma pós-ordenada (visita esquerda, visita direita, visita raiz). É um pouco mais complexo do que isso devido a associatividade, mas em essência, para compreensão, podemos manter essa analogia… Nessa árvore, os operadores com menor precedência são colocados no topo da árvore e os com maior, mais perto dos nós folha…

Isso parece simples, mas note o problema no fragmento de código abaixo:

int x;

x = 1 << 3 + 1

Qual será o resultado? 9 [de (1 << 3)+1] ou 16 [de 1 << (3+1)]? Vejamos: Vimos que = tem precedência mais baixa e associatividade da direita para esquerda, então a sub expressão à sua direita será resolvida primeiro, ou seja, 1 << 3 + 1. Aqui, tanto o operador << quanto + têm a mesma regra de associatividade (da esquerda para direita), mas + precede <<. Assim, a sub expressão fica (1 << (3 + 1)). O resultado é 16.

À primeira vista, pode parecer que o shift lógico tem maior prioridade que a adição ou, pelo menos, a mesma. Parece que o programador queria fazer um shift e depois somar 1. Entender como funciona o esquema precedência e associatividade é importante para evitar esse tipo de problema, senão você terá que usar parenteses em todas as suas expressões (o que não é má ideia, em caso de dúvida).

Outro exemplo está nas comparações. Note que os operadores lógicos (tanto binários [&. | e ^] quando os “lógicos” [&& e ||]) tem precedência menor que comparações (==, !=, <, , >=). Daí, ambas as construções abaixo são idênticas:

if (x == 0 && y == 0) ...
if ((x == 0) && (y == 0)) ...

Substitua == por = e temos uma inversão de precedências, ou seja, o = é feito por último… A expressão x = 0 && y = 0 fica x=((0 && y)=0), o que gerará um erro de LVALUE. Lembre-se, se && tem maior precedência que =, então ele é executado primeiro…

O que diabos é um LVALUE? Bem… operadores de atribuição esperam que o que esteja do lado esquerdo da expressão seja um objeto onde um valor possa ser armazenado. A sub expressão do lado direito criará uma atribuição do tipo 0=0 e não é possível armazenar o valor zero dentro de outro valor zero…

Ainda outro ponto de nota é que cada operador espera um conjunto de argumentos (ou operandos). Falo conjunto porque alguns operadores precisam de apenas um argumento (todos os operadores de ordem de precedência 1 e 2, na tabela acima). O restante, precisa de dois argumentos, exceto pelo operador condicional (?:), que precisa de 3… mas esse, tecnicamente, não é bem um operador e tem lá seus problemas com precedência e associatividade (recomendo evitá-lo, pela segunda vez neste texto).

Ainda falando de precedência, vale relembrar sobre os operadores de maior precedência . e ->, bem como citar o operador de indireção (*), com precedẽncia imediatamente inferior. O problema de misturar o operador de resolução de membros de estruturas (.) com o indireção (quando usamos ponteiros) é que a coisa não funciona bem como pode ser sua intenção. A expressão *p.x = 1;, sendo x um membro de uma estrutura qualquer apontada por p não faz o que se espera dela. Por ‘.’ ter precedência maior que ‘*’, a expressão pode ser entendida como *(p.x) = 1;, ou seja, estamos dizendo que o membro x é que é o ponteiro, não p. Para fazermos o que queríamos, temos que resolver esse problema de precedência com o uso de parenteses: (*p).x = 1;.

Acontece que ficará meio chato ter que fazer isso toda vez que usarmos o ponteiro p para essa (e outras) estruturas. Daí o operador ‘->’ foi criado e ele espera ter, no seu lado esquerdo, um ponteiro. O operador dereferencia o ponteiro sem a necessidade do uso do operador ‘*’. Daí, a expressão p->x = 1; é a mesma coisa que (*p).x = 1;.

Outro problema para sua consideração: Note que casting (promoção de tipo) também é um operador e tem precedência menor, por exemplo, do que um pós-incremento. Isso quer dizer que uma expressão do tipo (char *)p++ pode não fazer exatamente o que você espera… Suponha que p seja do tipo int *. A expressão ao lado vai adicionar sizeof(int) ao ponteiro e depois converter a expressão para o tipo char *. Se você quisesse adicionar sizeof(char) ao ponteiro, terá que, necessariamente, fazer: ((char *)p)++. Isso é fácil demonstrar:

/* test.c */
#include <stdio.h>

void main(void)
{
  static int x[2] = { 1, 2 };
  int *p, *q;
  char c;

  p = q = x;
  c = *(char *)p++;

  printf("(%p) %p -> 0x%02hhx\n", q, p, c);
}

Ao compilar e executar:

$ cc -o test test.c
$ ./test
(0x601038) 0x60103c -> 0x01

E, por último, nem todos os operadores lógicos tem precedência baixa. A exceção são os operadores de negação (! e ~). Isso garante que expressões como !a == b realizem a negação lógica do argumento a apenas, ao invés de toda a sub expressão à direita de !. Compare isso com expressões como a == b && b == c

Rolling back: O medidor de ciclos que uso atualmente…

Quem estiver procurando neste blog vai encontrar diversas atualizações no “medidor de ciclos de clock” que uso para medir a performance de rotinas, usando o timestamp mantido pelo processador desde o Pentium… O fato é que ele não é preciso (e mostro porquê disso em alguns artigos por aqui), mas é melhor que nada…

Eis a versão mais atual, onde obtenho melhores resultados:

#ifndef __CYCLE_COUNTING_INCLUDED__
#define __CYCLE_COUNTING_INCLUDED__

/* ==========================================
    Quick & Dirty cycle counting...

    begin_tsc() e end_tsc()

    são usadas para contar a quantidade de ciclos
    de máquina gastos num bloco de código.

    Exemplo de uso:

      uint64_t t;

      BEGIN_TSC;      
      f();
      END_TSC(t);

    É conveniente compilar o código sob teste com a
    opção -O0, já que o compilador poderá 'sumir' com
    o código, por causa da otimização. Melhor ainda
    seria compilar a função f() num módulo separado com
    a opção -O2 para obter o código otimizado.

    As macros, em si, não são "otimizáveis", por assim dizer.
   ========================================== */

#include <stdint.h>

// Mantém o timestamp inicial.
uint64_t __local_tsc;

#ifdef __x86_64__
#define REGS1 "rbx","rcx"
#define REGS2 "rcx"
#else
#ifdef __i386__
#define REGS1 "ebx","ecx"
#define REGS2 "ecx"
#else
#error cycle counting will work only on x86-64 or i386 platforms!
#endif
#endif

// Macro: Inicia a medição.
// Uso CPUID para serializar o processador aqui.
#define BEGIN_TSC do { \
  uint32_t a, d; \
\
  __asm__ __volatile__ ( \
    "xorl %%eax,%%eax\n" \
    "cpuid\n" \
    "rdtsc\n" \
    : "=a" (a), "=d" (d) :: REGS1 \
  ); \
\
  __local_tsc = ((uint64_t)d << 32) | a; \
} while (0)

// Macro: Finaliza a medição.
// NOTA: A rotina anterior usava armazenamento temporário
//       para guardar a contagem vinda de rdtscp. Ainda,
//       CPUID era usado para serialização (que parece ser inóquo!).
//       Obtive resultados melhores retirando a serialização e
//       devolvendo os constraints para EAX e EDX, salvando apenas ECX.
// PS:   rdtscp também serializa, deixando o CPUID supérfluo!
#define END_TSC(c) do { \
  uint32_t a, d; \
\
  __asm__ __volatile__ ( \
    "rdtscp\n" \
    : "=a" (a), "=d" (d) :: REGS2 \
  ); \
\
  (c) = (((uint64_t)d << 32) | a) - __local_tsc; \
} while (0)

#endif

Façam bom proveito!

Ponteiro para um array…

Eu evito algumas construções mais “esotéricas” da linguagem C, não porque não saiba o que elas signifiquem, mas em virtude da legibilidade… Recentemente me perguntaram o que significa a declaração:

int (*p)[4];

Bem… isso ai é um ponteiro para um array de 4 inteiros. O que é bem diferente de:

int *p[4];

Que é um array de 4 ponteiros para o tipo int.

O detalhe é que deixei meio de lado a utilidade da primeira declaração. Considere isso:

int a[4][4] =
  { { 1, 2, 3, 4 },
    { 5, 6, 7, 8 },
    { 9, 0, 1, 2 },
    { 3, 4, 5, 6 } };

void showarray(int a[][4])
{
  int i, j;

  for (i = 0; i < 4; i++)
  {
    for (j = 0; j < 4; j++)
      printf("%d ", a[i][j];
    putchar('\n');
  }
  putchar('\n');
}

A rotina showarray, como declarada acima, é um jeito de mostrar todos os itens de um array. Podemos chamá-la com showarray(a); e tudo funcionará perfeitamente bem… Mas, e se quiséssemos usar ponteiros ao invés de 2 índices (i e j)?

Note que, se você tem um array simples, pode usar um ponteiro para apontar para o primeiro item e incrementar o endereço contido no ponteiro para obter o próximo item, como em:

int a[] = { 1, 2, 3, 4, 5, 0 };

void showarray(int *p)
{
  for (; *p; p++)
    printf("%d ", *p);
  putchar('\n');
}

Aqui, o compilador criará código para somar 4 ao conteúdo de p a cada vez que ele for incrementado. O valor 4 é adicionado porque sizeof(int)==4. A pergunta original é: “Dá pra fazer algo semelhante com arrays bidimensionais?”. A resposta, obviamente, é: SIM!

Ao declarar um ponteiro p como int (*p)[4];, toda vez que você incrementar o ponteiro, a ele será adicionado o valor 16 (4*sizeof(int)) e podemos escrever a rotina showarray original, assim:

void showarray(int (*p)[4])
{
  int i;

  // Não é bem a rotina original, aqui considero que
  // se o primeiro item da "linha" for zero, devemos
  // encerrar o loop.
  //
  // p++ fará o ponteiro p apontar para o início da
  // próxima linha...
  for (; (*p)[0]; p++)
  {
    for (i = 0; i < 4; i++)
      printf("%d ", (*p)[i]);
    putchar('\n');
  }
  putchar('\n');
}

O array original, é claro, deverá ser definido assim, para a rotina funcionar:

int a[][4] =
  { { 1, 2, 3, 4 },
    { 5, 6, 7, 8 },
    { 9, 0, 1, 2 },
    { 3, 4, 5, 6 },
    {} };  // note: 4 zeros aqui!