u64 calculation incorrect on ARMv5

[returntoreality]

I've built a cross rust compiler for armv5tel-unknown-linux-gnueabi and using this target json

{
    "arch": "arm",
    "cpu": "generic",
    "llvm-target": "armv5tel-unknown-linux-gnu",
    "os": "linux",
    "vendor": "unknown",
    "relocation-model": "pic",
    "target-endian": "little",
    "target-pointer-width": "32",
    "exe-allocation-crate": "alloc_system",
    "lib-allocation-crate": "alloc_system",
    "linker": "armv5tel-unknown-linux-gnueabi-gcc",
    "ar": "armv5tel-unknown-linux-ar",
    "dynamic-linking": true,
    "executables": true,
    "features": "+v5te,+soft-float",

    "c-compiler": "armv5tel-unknown-linux-gnueabi-gcc",
    "c-flags": "-Wall -g -fPIC -O2",
    "c-link-flags": "-shared -fPIC -g",
    "c-triple": "armv5tel-linux-gnueabi"
}

and this mk/cfg/armv5tel-unknown-linux-gnueabi.mk:

# armv5tel-unknown-linux-gnueabi configuration
CROSS_PREFIX_armv5tel-unknown-linux-gnueabi=armv5tel-unknown-linux-gnueabi-
CC_armv5tel-unknown-linux-gnueabi=gcc
CXX_armv5tel-unknown-linux-gnueabi=g++
CPP_armv5tel-unknown-linux-gnueabi=gcc -E
AR_armv5tel-unknown-linux-gnueabi=ar
CFG_LIB_NAME_armv5tel-unknown-linux-gnueabi=lib$(1).so
CFG_STATIC_LIB_NAME_armv5tel-unknown-linux-gnueabi=lib$(1).a
CFG_LIB_GLOB_armv5tel-unknown-linux-gnueabi=lib$(1)-*.so
CFG_LIB_DSYM_GLOB_armv5tel-unknown-linux-gnueabi=lib$(1)-*.dylib.dSYM
CFG_JEMALLOC_CFLAGS_armv5tel-unknown-linux-gnueabi := -D__arm__ -mfloat-abi=soft -march=armv5te $(CFLAGS)
CFG_GCCISH_CFLAGS_armv5tel-unknown-linux-gnueabi := -Wall -g -fPIC -D__arm__ -mfloat-abi=soft -march=armv5te $(CFLAGS)
CFG_GCCISH_CXXFLAGS_armv5tel-unknown-linux-gnueabi := -fno-rtti $(CXXFLAGS)
CFG_GCCISH_LINK_FLAGS_armv5tel-unknown-linux-gnueabi := -shared -fPIC -g
CFG_GCCISH_DEF_FLAG_armv5tel-unknown-linux-gnueabi := -Wl,--export-dynamic,--dynamic-list=
CFG_LLC_FLAGS_armv5tel-unknown-linux-gnueabi :=
CFG_INSTALL_NAME_armv5tel-unknown-linux-gnueabi =
CFG_EXE_SUFFIX_armv5tel-unknown-linux-gnueabi :=
CFG_WINDOWSY_armv5tel-unknown-linux-gnueabi :=
CFG_UNIXY_armv5tel-unknown-linux-gnueabi := 1
CFG_LDPATH_armv5tel-unknown-linux-gnueabi :=
CFG_RUN_armv5tel-unknown-linux-gnueabi=$(2)
CFG_RUN_TARG_armv5tel-unknown-linux-gnueabi=$(call CFG_RUN_armv5tel-unknown-linux-gnueabi,,$(2))
RUSTC_FLAGS_armv5tel-unknown-linux-gnueabi :=
RUSTC_CROSS_FLAGS_armv5tel-unknown-linux-gnueabi :=
CFG_GNU_TRIPLE_armv5tel-unknown-linux-gnueabi := armv5tel-unknown-linux-gnueabi

I've run into problems with the regex crate, where an assertion ( assert!(start <= end); ByteClassSet::set_range(&mut self, start: u8, end: u8) in src/compile.rs ) failed when compiling a regex, which worked fine on x86_64. I saw the hash function that is implemented near the assertion, so I wanted to see if the u64 calculations are correct (the armv5 is 32bit). Here is the original function:

    fn hash(&self, suffix: &SuffixCacheKey) -> usize {
        // Basic FNV-1a hash as described:
        // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
        const FNV_PRIME: u64 = 1099511628211;
        let mut h = 14695981039346656037;
        h = (h ^ (suffix.from_inst as u64)).wrapping_mul(FNV_PRIME);
        h = (h ^ (suffix.start as u64)).wrapping_mul(FNV_PRIME);
        h = (h ^ (suffix.end as u64)).wrapping_mul(FNV_PRIME);
        (h as usize) % self.table.len()
    }

I tried this code:

fn main() {
    const FNV_PRIME: u64 = 1099511628211;
    let mut h = 14695981039346656037;
    h = (h ^ (10 as u64)).wrapping_mul(FNV_PRIME);
    h = (h ^ (50 as u64)).wrapping_mul(FNV_PRIME);
    h = (h ^ (60 as u64)).wrapping_mul(FNV_PRIME);
    println!("Hello, world! {}", h);
}

Which has different results on x86_64 and armv5
x86_64:
Hello, world! 3470322685770408467
armv5:
Hello, world! 3642012766597943866

I used clang on the armv5 device to compile this simple C program which does the same calculations:
Code:

#include <stdint.h>
#include <stdio.h>
int main () {
    const uint64_t FNV_PRIME = 1099511628211;
    uint64_t h = 14695981039346656037u;
    h = (h ^ (10))*(FNV_PRIME);
    h = (h ^ (50))*(FNV_PRIME);
    h = (h ^ (60))*(FNV_PRIME);
    printf("Hello, world! %llu \n", h);
}

Result:
Hello, world! 3470322685770408467

Meta

rustc 1.8.0-dev (15611f7 2016-02-19)
binary: rustc
commit-hash: 15611f7
commit-date: 2016-02-19
host: x86_64-unknown-linux-gnu
release: 1.8.0-dev

[MagaTailor]

You could try emitting IR and then use your ARM system's llc to produce a binary. (looking at IR from rustc and clang might reveal the problem too)

[returntoreality]

I tried using llc on the llvm ir, but it failed:
llc: u64_test.ll:410:80: error: missing required field 'tag'
!203 = !DILocalVariable(name: "h", scope: !202, file: !169, line: 4, type: !179)

These are the respective llvm-irs:
rust_u64.ll.txt
clang_u64.ll.txt

[MagaTailor]

I think it could be related to the datalayout; my armv7 rustc and your armv5 clang have:

"e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
"e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"

which produces correct results, whereas the custom target's
"e-m:e-p:32:32-f64:32:64-v64:32:64-v128:32:128-a:0:32-n32-S32" doesn't.

Should the different alignment values lead to this error? You could try putting clang's datalayout in your json file to see if it helps.

[returntoreality]

I've recompiled rust and the test program with the "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64" datalayout, unfortunately with the same result.

[MagaTailor]

I've compiled your rust IR file with a compatible llc:

./llc -march=arm -float-abi=soft -mattr=+v5te,+soft-float rust_u64.ll

If you don't see any problems with that command line, you can try the following on your ARM system:

$ as rust_u64.s -o rust_u64.o
$ gcc rust_u64.o -L path_to_your_libstd-*.so -o rust_u64
$ ./rust_u64

rust_u64.s.txt

[returntoreality]

It was a bit trickier, but I managed to get it to link and run and it reports
Hello, world! 3470322685770408467
This suggests that this is a llvm problem. I could probably build correct binaries using "your" llvm. What version/setup do you have?
Thanks for your help!

[MagaTailor]

Haven't we just exonerated llvm and implicated your cross-toolchain?

I simply used llvm 3.8 from my last Rust build to match your built-in stuff. (it ends up in llvm/Release/bin)

[returntoreality]

What I meant was that we showed that the llvm-ir created by my rust is valid, but the binary is not, so the error is somewhere between llvm-ir and binary on my setup. I thought it is probably llvm, since llvm is responsible for that part. I was able to create the exact same assembler output using the llvm from my rust build. This would suggest that my cross-toolchain setup is indeed wrong in some way. Since the llvm in my rust build can create correct binaries, I think that this is probably an error in my target json. What do you think?
I saw in the llvm-ir from the clang on the armv5, that it uses "armv4t-unknown-linux-gnueabi" as arch and "arm7tdmi" as cpu. I will test if that fixes the problem.

[returntoreality]

Unfortunately using "armv4t-unknown-linux-gnueabi" as llvm-target and arm7tdmi as processor had the same results

[MagaTailor]

Yeah, the llvm target is fine. Have you tried dumping assembly instead?
If it doesn't differ from what my llc produced, then maybe llvm-as is to blame? (were you using GNU as on your ARM system, BTW?)
There's the -C no-integrated-as option to force using e.g. gas during rust compilations.

The bundled llvm source was recently updated - as a last resort you could try building rust against an older local version (or even use a 1.6 source tarball) to see if the problem lies outside of llvm and rust.

[MagaTailor]

Any news on this?

@joerg-krause You were having trouble with your armv5 target, any ideas where this could be coming from?

[returntoreality]

So to test if the assembler is the problem I used the llc with "-filetype=obj" and used the cross-toolchain gcc on my x86_64 to link this file. This generates the correct result.
I also used the emit=asm option on my rustc, copied the result to the target machine and assembled(gas)/linked it there, which also produces the correct result.

[MagaTailor]

Provided you do have a cross gas on x86_64, could you try doing it in one go, with:
-C no-integrated-as --emit asm ?

On the other hand, if you could reproduce the bug by manually assembling with llvm-as on x86_64 that would definitely point to an upstream bug.

[returntoreality]

Compiling it with using -C no-integrated-as seems to work (although gcc is given the wrong path to the .o file during linking. I fixed that using a symlink)

[MagaTailor]

Ok, so it really looks like the the built-in assembler was to blame. I advise showing the material you've gathered to LLVM devs at https://llvm.org/bugs/

[returntoreality]

Well I was able to use the llc compiler with -filetype=obj to generate a binary that was correct or does llc use an external as?

[MagaTailor]

llvm-as is about generating llvm bitcode which can then be passed to llc for creating object files. So normally we wouldn't be talking about assembling human readable files with gas.

That's why my guess was llvm bitcode generation could be wrong as we've already proven going through intermediate steps of llvm-ir and asm works.

[joerg-krause]

I can confirm this issue with my custom armv5te-unknown-linux-musl.json target:

$ rustc -V
rustc 1.9.0-nightly (c9629d61c 2016-03-10)
$ cargo build --target=armv5te-unknown-linux-musl --release
   Compiling hello v0.1.0 (file:///home/joerg/rust-cross-libs/hello)
$ cargo build --release
   Compiling hello v0.1.0 (file:///home/joerg/rust-cross-libs/hello)

Output on ARMv5: Hello, world! 3642012766597943866
Output on x86_64: Hello, world! 3470322685770408467

@petevine Can you post the necessary commands to get the llvm bitcode, please. I'm not very experienced with LLVM.

[MagaTailor]

Sure, to get .bc pass the --emit llvm-bc flag, then use llc to create an object file, then link it against libstd (and maybe other libs too)

Or even --emit obj directly, so that only linking has to be done manually but that doesn't sound like it could be any different.

[joerg-krause]

Somehow, this does not work:

$ rustc --target=armv5te-unknown-linux-musl --emit llvm-bc src/main.rs
$ llc main.bc -o main.s
error: Invalid ID

I guess I'm doing it in the wrong way...

[MagaTailor]

Nope, it's probably just using your system's llc which seems incompatible for some reason. However, if you're going to try again maybe use llc -filetype=obj right away.

Do you still have the llvm/Release directory from the time you built the cross-compiler? The tools are there, in the bin directory.

[joerg-krause]

Do you still have the llvm/Release directory from the time you built the cross-compiler? The tools are there, in the bin directory.

No. Bootstraping the Rust cross-compiler for ARMv5 was to time-consuming, so I am cross-compiling the Rust libraries only. Does Rust hacks LLVM in a special way or can I just use the system ones?

I update my system LLVM to: LLVM version 3.9.0svn-r263337 and now I am able to compile from bytecode:

$ rm main main.bc main.o main.s
$ rustc src/main.rs --target=armv5te-unknown-linux-musl --emit llvm-bc
$ llc main.bc -o main.s -march=arm -float-abi=soft -mattr=+v5te,+soft-float
$ arm-linux-as main.s -o main.o
$ $HOME/arm-unknown-linux-musl-sysroot "-Wl,--as-needed" "-L" "$LD_LIBRARY_PATH/rustlib/armv5te-unknown-linux-musl/lib" "main.o" "-o" "main" "-Wl,--gc-sections" "-fPIC" "-Wl,-O1" "-nodefaultlibs" "-L" "$LD_LIBRARY_PATH/rustlib/armv5te-unknown-linux-musl/lib" "-Wl,-Bstatic" "-Wl,-Bdynamic" "$LD_LIBRARY_PATH/rustlib/armv5te-unknown-linux-musl/lib/libstd-18402db3.rlib" "$LD_LIBRARY_PATH/rustlib/armv5te-unknown-linux-musl/lib/libcollections-18402db3.rlib" "$LD_LIBRARY_PATH/rustlib/armv5te-unknown-linux-musl/lib/librustc_unicode-18402db3.rlib" "$LD_LIBRARY_PATH/rustlib/armv5te-unknown-linux-musl/lib/librand-18402db3.rlib" "$LD_LIBRARY_PATH/rustlib/armv5te-unknown-linux-musl/lib/liballoc-18402db3.rlib" "$LD_LIBRARY_PATH/rustlib/armv5te-unknown-linux-musl/lib/liballoc_system-18402db3.rlib" "$LD_LIBRARY_PATH/rustlib/armv5te-unknown-linux-musl/lib/liblibc-18402db3.rlib" "$LD_LIBRARY_PATH/rustlib/armv5te-unknown-linux-musl/lib/libcore-18402db3.rlib" "-l" "gcc_s" "-l" "c"
$ file main
main: ELF 32-bit LSB executable, ARM, EABI5 version 1 (SYSV), dynamically linked, interpreter /lib/ld-musl-arm.so.1, not stripped

Running main on the ARMv5 target: Hello, world! 3642012766597943866

Is rust generating wrong bytecode?

[joerg-krause]

I compiled the main.c from above (without "Hello world") with Clang:

$ clang -target armv5te-unknown-linux-musl -mcpu=arm926ej-s -mfloat-abi=soft --sysroot=$HOME/arm-buildroot-linux-musleabi/sysroot -Os -S -emit-llvm main.c -o main_clang.ll

And I compiled the main.rs from above (without "Hello world") with Rust:

rustc src/main.rs --target=armv5te-unknown-linux-musl --emit llvm-ir -O

The generated IR shows that Rust calculates the right value: store i64 3470322685770408467, i64* %h, align 8.

[MagaTailor]

Thanks so much for persevering @joerg-krause ! I believe you've clearly demonstrated generating asm from bitcode differs from the one emitted directly or via IR. So yeah, it seems it does!

May we have a look at both versions side by side? These two .s files must be llvm bug material, surely.

[joerg-krause]

I adapted the example to:

fn main() {
    const FNV_PRIME: u64 = 1099511628211;
    let mut h = 14695981039346656037;
    h = (h ^ (10 as u64)).wrapping_mul(FNV_PRIME);
    h = (h ^ (50 as u64)).wrapping_mul(FNV_PRIME);
    h = (h ^ (60 as u64)).wrapping_mul(FNV_PRIME);
    println!("{}", h == 3470322685770408467);
}

Cross-compiling:

$ cargo build --target=armv5te-unknown-linux-musl --release

Running on ARMv5 target:

# ./main
true

So, the calculation is correct. However, the correct result is not displayed.

[MagaTailor]

OK, so it's a different bug than we'd thought but still, it should be evident in the two assembly versions.

[joerg-krause]

May we have a look at both versions side by side? These two .s files must be llvm bug material, surely.

Please have a look: bc and asm.

For the record:

bc:

$ rustc --target=armv5te-unknown-linux-musl --emit llvm-bc src/main.rs
$ llc main.bc -o main.s -march=arm -float-abi=soft -mattr=+v5te,+soft-float -O2

asm:

$ rustc --target=armv5te-unknown-linux-musl --emit asm src/main.rs

EDIT: Re-run compilation steps...

[MagaTailor]

To clarify, clang.s is supposed to be the equivalent of rust's --emit asm and rustc.s is the stuff you got from bitcode? Cause that's what we should be comparing.

EDIT:
In that case, no, there won't be a difference, as ascertained earlier.

[MagaTailor]

To recap, after emitting the following:

• IR -> asm -> obj, works
• asm -> obj, works
• bc -> asm -> obj, doesn't work

assembling with gas every time.

[joerg-krause]

I've re-run the compilation step (see above) and updated the previous gist files.

[MagaTailor]

You need to ditch clang, and rerun the .bc to asm conversion with llc. That should be the 2nd line.

[joerg-krause]

Sorry, I'm afraid I do not understand what you want me to do. Can you provide the command, please?

I've re-run the test with a simpler main.rs:

fn main() {
    let h = 10;
    println!("h:{} h==10:{}", h, h==10);
}

Compiling with cargo:

$ cargo build --target=armv5te-unknown-linux-musl --release

Running on target:

# ./main
h:91 h==10:true

Weird!

[MagaTailor]

I'm talking about the first experiment you already conducted today.
rustc --emit llvm-bc followed by llc'ing the output to asm.

You then proceeded to assemble and link the binary which printed the wrong result.
However, doing the same on directly emitted asm, produced correct binaries according to @returntoreality

[joerg-krause]

Printing a loop:

fn main() {
    for x in 0..255 {
        println!("{}", x); // x: i32
    }
}

0
1
2
3
4
5
6
7
8
9
91
01
11
21
31
41
51
61
71
81
92
02
12
22
32
42
[...]

Looks like data alignment or byte ordering is messed up...

[MagaTailor]

Indeed, nice demonstration - that doesn't happen with gas though.

[joerg-krause]

I'm talking about the first experiment you already conducted today.
rustc --emit llvm-bc followed by llc'ing the output to asm.

I see! I re-run the compilation steps. Please have a look at my previous comment #31796 (comment).

EDIT:
Compiling with as from the asm emitted by rustc does not produce the correct result for me.

[MagaTailor]

Darn! I thought we were getting somewhere but it seems I was comparing the results from two different people :) Are you sure your target is equivalent to @returntoreality 's?

If you look at this comment, it worked for him:
#31796 (comment)

[joerg-krause]

-C no-integrated-as does not produce the correct result for me, too.

[MagaTailor]

Yeah, you already tried that manually. Either your json target is slightly different or your cross-gas is to blame.
@returntoreality confirmed that natively assembling and linking the emitted asm worked too.

I've run out of ideas - if you have a working armv5 native toolset you could try the above as well.

Or maybe it's tangentially related to issue #32049 (comment) ? At least the alignment values differ too...

[MagaTailor]

@returntoreality I've just remembered you rebuilt your armv5 cross-compiler with clang's datalayout - were you using it ever since or rather the original?

[joerg-krause]

I was able to fix this issue by adding +strict-align to the features field in the JSON config file. Now, running the example produces the correct result.

@petevine Many thanks for all your help!

[MagaTailor]

Well, you found the culprit so the thanks should go to you! Anyway, this probably means armv5 is fit to become the default target of arm-unknown-linux-gnueabi...

[returntoreality]

@petevine I used the "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64" datalayout, which was used by the armv5 systems clang and your armv7 toolchain.

[returntoreality]

I just tested adding +strict-align, which sadly did not fix it.

[returntoreality]

Okay I had to rebuild rustlib aswell, now it works! Thank you @petevine and @joerg-krause !

[MagaTailor]

Cool, it was starting to look really crazy otherwise :) Time to close, eh?

[returntoreality]

Yeah. You can close it then.

[MagaTailor]

It's your issue, I don't possess any special powers.

[joerg-krause]

The datalayout is not necessary anymore in the custom target, at least in Rust nightly. And yes, you have rebuild the rustlibs. Glad we figured this out!