Bug di ottimizzazione del compilatore LLVM o cosa?

Question

Mi sono imbattuto in un problema divertente che non sono in grado di capire.

sfondo è:

• LLVM 4,2 compilatore su XCode
• compilato con C++ 11 supporto
• compilato con -Os
• elaborate per ARMv7/armv7s architettura

Ora Mi sono reso conto che c'è un problema con un codice che è presente solo quando si compila con le ottimizzazioni abilitate.

Il codice è, testualmente:

static int foo(int tx, int sx, int w) 
{ 
    int vs = 60; 

    if (sx < vs*2 && tx > w - vs*2) 
    return (sx + w - tx); 
    else if (sx > w - vs*2 && tx < vs*2) 
    return -(w - sx + tx); 
    else 
    return sx - tx; 
} 

Ora, andando con LLDB ho fatto un passo il codice per rintracciare uno strano bug, e questo mi ha portato a capire che il primo ramo del caso è presa con l'ingresso

sx = 648 
tx = 649 
w = 768 
vs = 60 

(questi valori sono presi dal direttamente dalla tabella gente del posto in XCode, io non sono in grado di interrogare lldb su vs perché credo che venga ottimizzato.)

Il primo ramo è quindi if (648 < 120 && ... quindi non ci dovrebbe essere modo di prenderlo ma in realtà accade. Se compilo con -O0 il bug scompare.

Un'ulteriore cosa divertente è il fatto che per sx = 647 e tx = 648 il bug non si verifica.

Ora, le cose sono due: o mi manca qualcosa di così ovvio che 10 ore di debug mi impediscono di vedere o c'è una specie di bug in un'ottimizzazione.

Eventuali indizi?

Alcuni più di fondo, questa è l'ASM ha generato:

.private_extern __ZN5Utils12wrapDistanceEiii 
    .globl __ZN5Utils12wrapDistanceEiii 
    .align 2 
    .code 16      @ @_ZN5Utils12wrapDistanceEiii 
    .thumb_func __ZN5Utils12wrapDistanceEiii 
__ZN5Utils12wrapDistanceEiii: 
    .cfi_startproc 
Lfunc_begin9: 
@ BB#0: 
    @DEBUG_VALUE: wrapDistance:tx <- R0+0 
    @DEBUG_VALUE: wrapDistance:sx <- R1+0 
    @DEBUG_VALUE: wrapDistance:w <- R2+0 
    @DEBUG_VALUE: vs <- 60+0 
    sub.w r3, r2, #120 
    cmp r1, #119 
    @DEBUG_VALUE: wrapDistance:tx <- R0+0 
    @DEBUG_VALUE: wrapDistance:sx <- R1+0 
    @DEBUG_VALUE: wrapDistance:w <- R2+0 
    it le 
    cmple r3, r0 
Ltmp42: 
    @DEBUG_VALUE: wrapDistance:tx <- R0+0 
    @DEBUG_VALUE: wrapDistance:sx <- R1+0 
    @DEBUG_VALUE: wrapDistance:w <- R2+0 
    ittt lt 
    sublt r0, r1, r0 
Ltmp43: 
    addlt r0, r2 
    @DEBUG_VALUE: vs <- 60+0 
    bxlt lr 
Ltmp44: 
    @DEBUG_VALUE: wrapDistance:tx <- R0+0 
    @DEBUG_VALUE: wrapDistance:sx <- R1+0 
    @DEBUG_VALUE: wrapDistance:w <- R2+0 
    @DEBUG_VALUE: vs <- 60+0 
    cmp r3, r1 
    @DEBUG_VALUE: wrapDistance:tx <- R0+0 
    @DEBUG_VALUE: wrapDistance:sx <- R1+0 
    @DEBUG_VALUE: wrapDistance:w <- R2+0 
    it lt 
    cmplt r0, #119 
Ltmp45: 
    @DEBUG_VALUE: wrapDistance:tx <- R0+0 
    @DEBUG_VALUE: wrapDistance:sx <- R1+0 
    @DEBUG_VALUE: wrapDistance:w <- R2+0 
    itttt le 
    suble r1, r2, r1 
Ltmp46: 
    addle r0, r1 
Ltmp47: 
    rsble r0, r0, #0 
    @DEBUG_VALUE: vs <- 60+0 
    bxle lr 
Ltmp48: 
    @DEBUG_VALUE: wrapDistance:tx <- R0+0 
    @DEBUG_VALUE: wrapDistance:sx <- R1+0 
    @DEBUG_VALUE: vs <- 60+0 
    subs r0, r1, r0 
Ltmp49: 
    @DEBUG_VALUE: vs <- 60+0 
    bx lr 
Ltmp50: 
Lfunc_end9: 
    .cfi_endproc 

Se pongo una stampa, ad esempio printf("%d < %d - %d",sx,vs*2,sx < vs*2) prima che la clausola if poi il bug scompare.

Questo semplice test case exibits il problema:

for (int i = 0; i < 767; ++i) 
{ 
    printf("test: %d, %d, %d",i,i+1,Utils::wrapDistance(i+1, i, 768)) 
} 

... 
test: 641, 642, -1 
test: 642, 643, -1 
test: 643, 644, -1 
test: 644, 645, -1 
test: 645, 646, -1 
test: 646, 647, -1 
test: 647, 648, -1 
test: 648, 649, -769 
test: 649, 650, -1 
test: 650, 651, -1 
test: 651, 652, -1 
test: 652, 653, -1 
test: 653, 654, -1 
test: 654, 655, -1 
... 

EDIT2

sono riuscito a riprodurre il bug in un programma stand-alone, ho appena creato un progetto vuoto iOS, quindi ho definito il funzione due volte, una volta in AppDelegate.mm per essere chiamato direttamente dallo stesso file e un altro in un file separato:

Test.h

#ifndef TEST_H_ 
#define TEST_H_ 

class Utils 
{ 
    public: 
    static int wrapDistance(int tx, int sx, int w); 
}; 

#endif 

Test.cpp

#include "Test.h" 

int Utils::wrapDistance(int tx, int sx, int w) 
{ 
    int vs = 60; 

    if (sx < vs*2 && tx > w - vs*2) 
    return (sx + w - tx); 
    else if (sx > w - vs*2 && tx < vs*2) 
    return -(w - sx + tx); 
    else 
    return sx - tx; 
} 

AppDelegate.mm

#import "AppDelegate.h" 
#include "Test.h" 

int wrapDistance(int tx, int sx, int w) 
{ 
    int vs = 60; 

    if (sx < vs*2 && tx > w - vs*2) 
    return (sx + w - tx); 
    else if (sx > w - vs*2 && tx < vs*2) 
    return -(w - sx + tx); 
    else 
    return sx - tx; 
} 

@implementation AppDelegate 

- (BOOL)application:(UIApplication *)application didFinishLaunchingWithOptions:(NSDictionary *)launchOptions 
{ 
    ... 

    for (int i = 0; i < 767; ++i) 
    { 
    NSLog(@"test inside: %d, %d, %d",i,i+1,wrapDistance(i+1, i, 768)); 
    NSLog(@"test outside: %d, %d, %d",i,i+1,Utils::wrapDistance(i+1, i, 768)); 
    } 

    return YES; 
} 

... 

USCITA

test inside: 644, 645, -1 
test outside: 644, 645, -1 
test inside: 645, 646, -1 
test outside: 645, 646, -1 
test inside: 646, 647, -1 
test outside: 646, 647, -1 
test inside: 647, 648, -1 
test outside: 647, 648, -1 
test inside: 648, 649, -1 
test outside: 648, 649, -769 
test inside: 649, 650, -1 
test outside: 649, 650, -1 
test inside: 650, 651, -1 
test outside: 650, 651, -1 
test inside: 651, 652, -1 
test outside: 651, 652, -1 

Come si può vedere, il comportamento per la funzione definita all'interno del file da cui è chiamato è corretto, ma la stessa cosa non si applica per l'altro, che mostra th Lo stesso bug Se impongo di non allineare la funzione interna con __attribute__ ((noinline)), entrambe le funzioni falliscono. Sto davvero brancolando nel buio.

Answer 1

In primo luogo, il vostro caso di test implica che in realtà sta prendendo erroneamente il ramo else if.

Ma io riprendo; sembra esserci un bug nell'ASM risultante. ^*

Ecco una/versione annotata formattata del vostro ASM per il test non aver:

% r0 = tx = 649 
% r1 = sx = 648 
% r2 = w = 768 

% w - vs*2 
sub.w r3, r2, #120   % r3 = 648 

% if (sx < vs*2) 
cmp r1, #119 
it le      % (1) Not taken 
    % if ((w - vs*2) < tx) 
    cmple r3, r0 
ittt lt     % (2) Not taken 
    % return (sx + w - tx) 
    sublt r0, r1, r0 
    addlt r0, r2 
    bxlt lr 

% if ((w - vs*2) < sx) 
cmp r3, r1 
it lt      % (3) Not taken 
    % if (tx < vs*2) 
    cmplt r0, #119 
itttt le     % (4) Taken! <<<<<<<<<<<<< 
    % return -(w - sx + tx) 
    suble r1, r2, r1 
    addle r0, r1 
    rsble r0, r0, #0 
    bxle lr 

% return sx - tx 
subs r0, r1, r0 
bx lr 

condizionali (3) e si suppone (4) di lavorare insieme per raggiungere un logico-E del due sotto-espressioni. In teoria, il blocco (4) viene eseguito solo se il blocco (3) viene eseguito e il confronto successivo imposta i flag di stato appropriati. ^**

Tuttavia, questo è implementato in modo errato. Comparison (3) imposta Z, il che significa che la condizione (3) non viene attivata (richiede N!=V), quindi la condizione (4) non viene eseguita. Bene finora. Ma lo è sufficiente per attivare la condizione (4) (richiede (Z==1) || (N!=V)), causando il problema che si vede.

In sintesi, ci sono quattro possibilità:

1. c'è davvero un bug nel backend LLVM mira ARM7.
2. Il codice C che hai fornito non è realmente il codice che stai compilando.
3. Si ha qualche codice C non valido che sta attivando un comportamento non definito, causando un ASM senza senso che viene generato come un effetto collaterale.
4. Le mie analisi di cui sopra non sono corrette!

---

_{* Anche se è 12:40 in questo momento, così ho può essere scambiato ...}

_{** http://blogs.arm.com/software-enablement/206-condition-codes-1-condition-flags-and-codes/}