optimisation breaks AES code from MySQL

[llvmbot]

Bugzilla Link	4210
Resolution	FIXED
Resolved on	May 15, 2009 05:30
Version	unspecified
OS	MacOS X
Attachments	standalone test case
Reporter	LLVM Bugzilla Contributor
CC	@asl,@sunfishcode,@nlewycky

Extended Description

When building MySQL 5.0 with clang (at least for a Mac OS X x86_64 target), turning on optimisation (-O1 or above) breaks AES encryption/decryption functionality as compared to a build without optimisation (-O0).

The attached standalone test case was extracted from the MySQL 5.0 code base. I'm sorry that it is still quite large, I've not had much luck with extracting the individual bit that is optimised badly, but I have reduced it to one code path in one function that shows the problem.

To compile:

clang -o rijndael_test_O0 rijndael_bug.c -O0
clang -o rijndael_test_O1 rijndael_bug.c -O0
clang -o rijndael_test_O1V rijndael_bug.c -O0 -DVOLATILE=volatile

The output of rijndael_test_O0 is as follows:

39 25 cc 14 d7 5 ef 4e e9 c7 fb cd 40 22 ed 29

The output of rijndael_test_O1 is as follows:

39 25 cc 14 d7 5 ef 4e e9 c7 fb d1 40 22 ed 29

Note that the 12th byte is different.

The output of rijndael_test_O1V is the same as rijndael_test_O0:

39 25 cc 14 d7 5 ef 4e e9 c7 fb cd 40 22 ed 29

The difference between O1 and O1V is that a "volatile" statement is added to the variable declaration in the rijndaelEncrypt function. In fact it seems to be sufficient to declare one of these variables volatile to make the problem go away.

I have inserted one comment into the source:
/* Value of t1 will be different depending on optimisation */

At this location, a value t1 is computed as follows:
t1= (Te0[(s1 >> 24) ] ^
Te1[(s2 >> 16) & 0xff] ^
Te2[(s3 >> 8) & 0xff] ^
Te3[(s0 ) & 0xff] ^
rk[5]);

The result of this calculation is different when optimisation is turned on. I wasn't able to reproduce this with the snippet on its own.

The full version of the rijndaelEncrypt function in the MySQL code base has an alternate code path that can be enabled with -DFULL_UNROLL. I removed this codepath from the test case because it does not exhibit the problem.

[lattner]

Daniel, can you take a look at this? Does the test valgrind clean?

[llvmbot]

AES is also part of OpenSSL. Does it built correctly with clang?

[llvmbot]

The first "for" loop in main goes stomping off the end of rk; sizeof is measured in bytes, not words. However, this isn't the cause of the problem, and I assume it was introduced during test reduction?

[llvmbot]

pre-globalopt.ll
Testcase before running globalopt.

[llvmbot]

post-globalopt.ll
Testcase after running globalopt.

[llvmbot]

I tracked the diff down to globalopt, and I've attached the before/after .ll files.

[llvmbot]

The first "for" loop in main goes stomping off the end of rk; sizeof is
measured in bytes, not words. However, this isn't the cause of the problem,
and I assume it was introduced during test reduction?

With this patched, it now fails for me in x86-32, but not in x86-64. Owen, you are running unpatched 64-bit, right?

Patch:
for(i=0; i<sizeof(rk)/sizeof(unsigned int); ++i) rk[i] = i;

[lattner]

Globalopt is fine:

$ llvm-as < before.ll | opt -globalopt | llvm-dis > after.ll
$ llvm-as < before.ll | opt -globalopt -debug | llvm-dis > after.ll
MARKING CONSTANT: @​pt = internal global [16 x i8] c"ABCDEFGHIJKLMNOP", align 16 ; <[16 x i8]*> [#uses=16]
*** Marking constant allowed us to simplify all users and delete global!
$ sdiff -w240 before.ll after.ll |& less

The only difference here is that globalopt has (correctly) promoted 16 loads from a constant global into the loaded values. globalopt must be exposing a codegen bug.

[lattner]

Oh yeah, also make sure to use:
llvm-as < aes2.ll.txt | opt -instnamer | llvm-dis > before.ll

otherwise the diff is meaningless.

[llvmbot]

I tested on 64-bit Linux.

[llvmbot]

I've read through the assembly and unfortunately can't see the bug. I'll have to try stepping through at runtime. I can say removing either -relocation-model=pic or -disable-fp-elim makes it go away, which points strongly to register allocation.

[llvmbot]

I see it now. The code inside the loop is OK, the problem occurs in the code after the loop that packs things into ct. Let me make sure it is the register allocator, sure looks like it.

[llvmbot]

OK, the wrong instruction is indicated below. Evan, I think you're going to have to look at this, unless you want to back out patches until it works:). The fragment shown is the code for the computation of s2 at the end of the big function, after the loop. The t1 value is in reg1136, the dump going into the RA looks correct, and a couple of references earlier in the block are getting it from the right place,
-16(%ebp). I will attach a .bc file.

    andl    $4278190080, -32(%ebp)  ; t2
    shrl    $22, -32(%ebp)
movl    $4278190080, %eax
    movl    -32(%ebp), %ebx
    andl    _Te4-"L1$pb"(%esi,%ebx), %eax
movl    -28(%ebp), %ebx    ; t3
shrl    $14, %ebx
    andl    $1020, %ebx
    movl    $16711680, %edx
    andl    _Te4-"L1$pb"(%esi,%ebx), %edx
orl     %eax, %edx
    movzbl  %ch, %eax    ; t0 (in %ecx)
movl    $65280, %ebx
andl    _Te4-"L1$pb"(%esi,%eax,4), %ebx
orl     %edx, %ebx
movzbl  %al, %edx    ; should be t1, WRONG
movzbl  _Te4-"L1$pb"(%esi,%edx,4), %edx
orl     %ebx, %edx
movl    8(%ebp), %ebx
movl    -64(%ebp), %eax
xorl    8(%ebx,%eax), %edx  ; rk[2]
movl    %edx, %eax    ; splitting result
shrl    $24, %eax     ; into bytes and
movb    %al, 8(%edi)  ; storing to ct[8..11]
    movl    %edx, %eax
    shrl    $16, %eax
    movb    %al, 9(%edi)
    movb    %dh, 10(%edi)
    movb    %dl, 11(%edi)

[llvmbot]

Feed into llc -disable-fp-elim -relocation-model=pic

[llvmbot]

You can run with different options and see the differing 12th byte if you like. The byte values are entirely different than shown above, perhaps because of the buffer overflow.