LLVM compiler optimization bug or what?

Question

I stumbled inside a funny problem that I'm not able to understand.

Background is:

• LLVM 4.2 Compiler on XCode
• compiled with c++11 support
• compiled with -Os
• compiled for armv7/armv7s architecture

Now I realized there is a problem with some code that is present just when compiling with optimizations enabled.

The code is, verbatim:

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;
}

Now, by going with LLDB I stepped code to track down a strange bug, and this lead me to realize that the first branch of the if is taken with input

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

(these values are taken from directly from the locals table in XCode, I'm not able to query lldb about vs because I guess it gets optimized.)

The first branch is then if (648 < 120 && ... so there should be no way to take it but it actually happens. If I compile with -O0 then the bug just disappears.

An additional funny thing is the fact that for sx = 647 and tx = 648 the bug doesn't occur.

Now, things are two: or I'm missing something so obvious that 10 hours of debugging forbid me to see or there is a sort of bug in an optimization.

Any clues?

Some more background, this is the ASM generated:

    .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

If I place a print, eg printf("%d < %d - %d",sx,vs*2,sx < vs*2) before the if clause then the bug disappear.

This simple test case exibits the problem:

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

I managed to reproduce the bug in a stand alone program, I just created an empty iOS project, then I defined the function twice, once in the AppDelegate.mm to be called directly from the same file and another one in a separate file:

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;
}

...

OUTPUT

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

As you can see, the behavior for the function that is defined inside the file from which is called is correct, but the same thing doesn't apply for the other one, which shows the same bug. If I force not to inline the inner function with __attribute__ ((noinline)) then both functions fail. I'm really groping into the dark.

Answer 1

Firstly, your test-case implies that it's actually erroneously taking the else if branch.

But I take it back; there does seem to be a bug in the resulting ASM.^*

Here is a formatted/annotated version of your ASM for the failing test:

% 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

Conditionals (3) and (4) are supposed to work together to achieve a logical-AND of the two sub-expressions. In theory, block (4) is only executed if block (3) is executed and the subsequent comparison sets the appropriate status flags.^**

However, this is implemented incorrectly. Comparison (3) sets Z, which means that condition (3) is not triggered (it requires N!=V), so condition (4) is not executed. Fine so far. But it is sufficient to trigger condition (4) (it requires (Z==1) || (N!=V)), resulting in the problem you see.

To summarise, there are four possibilities here:

1. There really is a bug in the LLVM backend targeting ARM7.
2. The C code you provided isn't really the code you're compiling.
3. You have some invalid C code elsewhere that's triggering undefined behaviour, resulting in nonsense ASM being generated as a side-effect.
4. My analysis above is incorrect!

---

_{* Although it's 12:40am right now, so I may be mistaken...}

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