Estouro assinado em C ++ e comportamento indefinido (UB)

Eu estou pensando sobre o uso de código como o seguinte

int result = 0;
int factor = 1;
for (...) {
    result = ...
    factor *= 10;
}
return result;

Se o loop for iterado ao longo do ntempo, factorserá multiplicado 10exatamente pelo ntempo. No entanto, factorsó é usado depois de multiplicado pelo 10total de n-1vezes. Se assumirmos que factornunca estouramos, exceto na última iteração do loop, mas podemos estourar na última iteração do loop, esse código deve ser aceitável? Nesse caso, o valor de factorprovavelmente nunca seria usado após o estouro.

Estou discutindo se códigos como esse devem ser aceitos. Seria possível colocar a multiplicação dentro de uma instrução if e simplesmente não fazer a multiplicação na última iteração do loop, quando ele pode transbordar. A desvantagem é que ele atrapalha o código e adiciona uma ramificação desnecessária que precisaria verificar todas as iterações anteriores do loop. Eu também poderia iterar o loop menos uma vez e replicar o corpo do loop uma vez após o loop, novamente, isso complica o código.

O código real em questão é usado em um loop interno rígido que consome grande parte do tempo total da CPU em um aplicativo gráfico em tempo real.

Compiladores assumem que um programa C ++ válido não contém UB. Considere, por exemplo:

if (x == nullptr) {
    *x = 3;
} else {
    *x = 5;
}

Se, x == nullptrentão, derreferenciá-lo e atribuir um valor é UB. Portanto, a única maneira de isso terminar em um programa válido é quando x == nullptrnunca produzirá true e o compilador pode assumir a regra como se, o acima é equivalente a:

*x = 5;

Agora no seu código

int result = 0;
int factor = 1;
for (...) {      // Loop until factor overflows but not more
   result = ...
   factor *= 10;
}
return result;

A última multiplicação de factornão pode acontecer em um programa válido (o estouro assinado é indefinido). Daí também a tarefa de resultnão poder acontecer. Como não há como ramificar antes da última iteração, a iteração anterior também não pode acontecer. Eventualmente, a parte do código correta (ou seja, nenhum comportamento indefinido acontece) é:

// nothing :(

O comportamento do intestouro é indefinido.

Não importa se você lê factorfora do corpo do loop; se ele estourou até então, o comportamento do seu código foi depois, e um tanto paradoxalmente, antes que o estouro seja indefinido.

Um problema que pode surgir para manter esse código é que os compiladores estão ficando cada vez mais agressivos quando se trata de otimização. Em particular, eles estão desenvolvendo um hábito em que assumem que um comportamento indefinido nunca acontece. Para que isso aconteça, eles podem remover o forloop completamente.

Você não pode usar um unsignedtipo para factorembora então você precisa se preocupar com a conversão indesejada de intque unsignedem expressões contendo tanto?

Pode ser interessante considerar otimizadores do mundo real. Desenrolar o loop é uma técnica conhecida. A idéia básica de desenrolar o loop op é que

for (int i = 0; i != 3; ++i)
    foo()

pode ser melhor implementado nos bastidores como

 foo()
 foo()
 foo()

Este é o caso fácil, com um limite fixo. Mas os compiladores modernos também podem fazer isso por limites variáveis:

for (int i = 0; i != N; ++i)
   foo();

torna-se

__RELATIVE_JUMP(3-N)
foo();
foo();
foo();

Obviamente isso só funciona se o compilador souber que N <= 3. E é aí que voltamos à pergunta original. Como o compilador sabe que o estouro assinado não ocorre , ele sabe que o loop pode executar no máximo 9 vezes em arquiteturas de 32 bits. 10^10 > 2^32. Portanto, ele pode fazer um loop de 9 iterações. Mas o máximo pretendido foi de 10 iterações! .

O que pode acontecer é que você obtenha um salto relativo em uma instrução de montagem (9-N) com N = 10, portanto, um deslocamento de -1, que é a própria instrução de salto. Opa Essa é uma otimização de loop perfeitamente válida para C ++ bem definido, mas o exemplo dado se transforma em um loop infinito apertado.

Qualquer excesso de número inteiro assinado resulta em comportamento indefinido, independentemente de o valor excedido ser ou não lido ou não.

Talvez no seu caso de uso você possa tirar a primeira iteração do loop, transformando isso

int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
    result += n + factor;
    factor *= 10;
}
// factor "is" 10^10 > INT_MAX, UB

nisso

int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
    factor *= 10;
    result += n + factor;
}
// factor is 10^9 < INT_MAX

Com a otimização ativada, o compilador pode desenrolar o segundo loop acima em um salto condicional.

Este é UB; em termos de ISO C ++, todo o comportamento de todo o programa é completamente não especificado para uma execução que eventualmente atinge o UB. O exemplo clássico é que, na medida em que o padrão C ++ se importa, ele pode fazer com que os demônios voem do seu nariz. (Eu recomendo não usar uma implementação em que os demônios nasais são uma possibilidade real). Veja outras respostas para mais detalhes.

Os compiladores podem "causar problemas" em tempo de compilação para os caminhos de execução que eles podem ver levando a UB visível em tempo de compilação, por exemplo, suponha que esses blocos básicos nunca sejam atingidos.

Consulte também O que todo programador C deve saber sobre comportamento indefinido (blog do LLVM). Conforme explicado lá, o UB de estouro assinado permite que os compiladores provem que os for(... i <= n ...)loops não são infinitos, mesmo para desconhecidos n. Ele também permite que eles "promovam" contadores de loop int para a largura do ponteiro, em vez de refazer a extensão do sinal. (Portanto, a conseqüência do UB nesse caso poderia ser acessar fora dos elementos baixos de 64k ou 4G de uma matriz, se você estivesse esperando uma quebra automática assinada iem seu intervalo de valores.)

Em alguns casos, os compiladores emitem uma instrução ilegal como x86 ud2para um bloco que provavelmente causa o UB, se alguma vez for executado. (Observe que uma função nem sempre pode ser chamada, portanto, em geral, os compiladores não podem ficar furiosos e interromper outras funções, ou mesmo caminhos possíveis através de uma função que não atinge UB. todas as entradas que não levam ao UB.)

Provavelmente, a solução mais eficiente é descascar manualmente a última iteração para factor*=10evitar o desnecessário .

int result = 0;
int factor = 1;
for (... i < n-1) {   // stop 1 iteration early
    result = ...
    factor *= 10;
}
 result = ...      // another copy of the loop body, using the last factor
 //   factor *= 10;    // and optimize away this dead operation.
return result;

Ou se o corpo do loop for grande, considere simplesmente usar um tipo não assinado para factor. Em seguida, você pode deixar o multiplicador sem sinal estourar e ele fará um empacotamento bem definido com uma potência de 2 (o número de bits de valor no tipo não assinado).

Isso é bom mesmo se você usá-lo com tipos assinados, especialmente se sua conversão não assinada-> nunca exceder.

A conversão entre o complemento não assinado e o do 2 assinado é livre (o mesmo padrão de bits para todos os valores); o módulo para int -> unsigned especificado pelo padrão C ++ simplifica o uso do mesmo padrão de bits, diferente do complemento ou sinal / magnitude.

E não assinado-> assinado é igualmente trivial, embora seja definido pela implementação para valores maiores que INT_MAX. Se você não estiver usando o enorme resultado não assinado da última iteração, não terá com que se preocupar. Mas, se estiver, consulte A conversão de não assinado em assinado é indefinida? . O caso do valor não se encaixa é definido pela implementação , o que significa que uma implementação deve escolher algum comportamento; os sãos apenas truncam (se necessário) o padrão de bits não assinado e o usam como assinado, porque isso funciona para valores dentro do intervalo da mesma maneira, sem trabalho extra. E definitivamente não é UB. Assim, grandes valores não assinados podem se tornar inteiros com sinal negativo. por exemplo, depois de int x = u; gcc e clang não otimizarx>=0como sempre sendo verdade, mesmo sem -fwrapv, porque eles definiram o comportamento.

Se você puder tolerar algumas instruções adicionais de montagem no loop, em vez de

int factor = 1;
for (int j = 0; j < n; ++j) {
    ...
    factor *= 10;
}

você pode escrever:

int factor = 0;
for (...) {
    factor = 10 * factor + !factor;
    ...
}

para evitar a última multiplicação. !factornão introduzirá um ramo:

    xor     ebx, ebx
L1:                       
    xor     eax, eax              
    test    ebx, ebx              
    lea     edx, [rbx+rbx*4]      
    sete    al    
    add     ebp, 1                
    lea     ebx, [rax+rdx*2]      
    mov     edi, ebx              
    call    consume(int)          
    cmp     r12d, ebp             
    jne     .L1                   

Este código

int factor = 0;
for (...) {
    factor = factor ? 10 * factor : 1;
    ...
}

também resulta em montagem sem ramificação após a otimização:

    mov     ebx, 1
    jmp     .L1                   
.L2:                               
    lea     ebx, [rbx+rbx*4]       
    add     ebx, ebx
.L1:
    mov     edi, ebx
    add     ebp, 1
    call    consume(int)
    cmp     r12d, ebp
    jne     .L2

(Compilado com o GCC 8.3.0 -O3)

Você não mostrou o que está entre parênteses da fordeclaração, mas vou assumir que é algo como isto:

for (int n = 0; n < 10; ++n) {
    result = ...
    factor *= 10;
}

Você pode simplesmente mover a verificação do incremento do contador e da terminação do loop para o corpo:

for (int n = 0; ; ) {
    result = ...
    if (++n >= 10) break;
    factor *= 10;
}

O número de instruções de montagem no loop permanecerá o mesmo.

Inspirado na apresentação de Andrei Alexandrescu "A velocidade é encontrada nas mentes das pessoas".

Considere a função:

unsigned mul_mod_65536(unsigned short a, unsigned short b)
{
  return (a*b) & 0xFFFFu;
}

De acordo com a Justificativa publicado, os autores do padrão teria esperado que, se esta função foi chamado em (por exemplo) um computador de 32 bits comum com argumentos de 0xC000 e 0xC000, promovendo os operandos de *que signed intfaria com que a computação para produzir -0x10000000 , que quando convertidos em unsignedproduziriam 0x90000000u- a mesma resposta como se eles tivessem unsigned shortpromovido a unsigned. No entanto, o gcc às vezes otimiza essa função de maneiras que se comportariam sem sentido se ocorrer um estouro. Qualquer código em que alguma combinação de entradas possa causar um estouro deve ser processado com a -fwrapvopção, a menos que seja aceitável permitir que criadores de entrada malformada deliberadamente executem código arbitrário de sua escolha.

Por que não isso:

int result = 0;
int factor = 10;
for (...) {
    factor *= 10;
    result = ...
}
return result;

Existem muitas faces diferentes do comportamento indefinido e o aceitável depende do uso.

loop interno apertado que consome grande parte do tempo total da CPU em um aplicativo gráfico em tempo real

Isso, por si só, é um pouco incomum, mas, seja como for ... se esse for realmente o caso, o UB provavelmente estará dentro do domínio "permitido, aceitável" . A programação gráfica é notória por hacks e coisas feias. Desde que "funcione" e não demore mais que 16,6 ms para produzir um quadro, geralmente ninguém se importa. Mas, esteja ciente do que significa invocar o UB.

Primeiro, existe o padrão. Desse ponto de vista, não há nada para discutir e nenhuma maneira de justificar, seu código é simplesmente inválido. Não há ifs ou whens, apenas não é um código válido. Você também pode dizer que está com o dedo do meio levantado do seu ponto de vista e, em 95-99% das vezes, é bom que você vá.

Em seguida, há o lado do hardware. Existem algumas arquiteturas incomuns e estranhas , onde isso é um problema. Estou dizendo "incomum, estranho" porque, na única arquitetura que compõe 80% de todos os computadores (ou nas duas arquiteturas que juntas compõem 95% de todos os computadores), o estouro é um "sim, tanto faz, não importa" coisa no nível do hardware. Você com certeza consegue um resultado de lixo (embora ainda previsível), mas nada de ruim acontece.
Isso não éEm todas as arquiteturas, é bem possível que você fique preso em excesso (embora, vendo como você fala de um aplicativo gráfico, as chances de estar em uma arquitetura tão estranha sejam bastante pequenas). A portabilidade é um problema? Se for, você pode querer se abster.

Por último, existe o lado do compilador / otimizador. Uma razão pela qual o estouro é indefinido é que simplesmente deixá-lo como era mais fácil lidar com o hardware era uma vez. Mas outro motivo é que, por exemplo, x+1é garantido que sempre será maior que x, e o compilador / otimizador pode explorar esse conhecimento. Agora, no caso mencionado anteriormente, é sabido que os compiladores agem dessa maneira e simplesmente eliminam os blocos completos (existia uma exploração do Linux há alguns anos atrás, que se baseava no fato de o compilador ter retirado completamente algum código de validação por causa disso).
No seu caso, duvido seriamente que o compilador faça algumas otimizações especiais e ímpares. No entanto, o que você sabe, o que eu sei. Em caso de dúvida, experimente. Se funcionar, você está pronto para ir.

(E, finalmente, é claro que existe uma auditoria de código, você pode ter que perder seu tempo discutindo isso com um auditor, se tiver azar.)