Compile bools to i1, as per Clang

[bstrie]

<strcat> aatch: well, can we just do what clang does? does it just say i1 is represented as i8?
<strcat> clang stores them as i8, passes them as i1 zeroext and treats them as i1 after a load
<strcat> lets just copy that
<strcat> that's what LLVM knows how to optimize

[bstrie]

@thestinger has been mentioning this for a long time.

Nominating for Production Ready.

[graydon]

I thought we used to do just this, and stopped because "it wasn't what clang did".

[thestinger]

@graydon: the issue before was that we were also storing them as i1

[brson]

The IRC convo is missing context. Why do we want to do this?

[thestinger]

It's mostly because our IR is resulting in poor optimization right now, because LLVM is designed to consume clang's output. The way clang handles this is to truncate down to i1 after a load, and zext to i8 before a store. Since there are range assertions output for the loads, LLVM will optimize the truncation to a no-op, resulting in it branching directly on the value in every case.

We do actually output range assertions now, but they're not triggering the relevant knowledge in LLVM.

There are also currently issues like this, because we aren't truncating to i1:

strcat | rusti: let x = 5 as bool; (x, x == true)
    -- | Notice(rusti): (true, false)

I could try to put together an isolated example where using i1 leads to better results.

[graydon]

Oh I see. Carry on then!

[catamorphism]

Just a bug, de-nominating

[eddyb]

And I found an example where it really stops optimizations:

// optimized to ret 0
fn foo(i: uint) -> uint {if i % 5 == 1 {if i % 4 == 0 {i % 4}else{0}}else{0}}
// not optimized to ret 0
fn foo(i: uint) -> uint {if i % 5 == 1 && i % 4 == 0 {i % 4}else{0}}

// optimized in clang to ret 0, but I think it does short-circuiting differently,
// so it's equivalent to the optimized rustc one
unsigned long foo(unsigned long i) {return (i % 5 == 1 && i % 4 == 0) ? i % 4 : 0;}

I realized the same thing as @thestinger by looking at the output of --emit-llvm.
By manually editing that output to get rid of the two casts to i8, and optimizing it again, I've obtained an improved version.

Update: the missing link in the optimization process is %.demorgan = and i1 %3, %5 implying %5 = icmp eq i64 %4, 0, replacing the use of %.demorgan with %5 produces ret 0.
I've tested with the LLVM version currently bundled with rust, so I believe this last step is a still unsolved LLVM issue.

// this non-short-circuiting example behaves just like the unoptimized rust one,
// with my manual bool optimization applied
unsigned long foo(unsigned long i) {return (i % 5 == 1 & i % 4 == 0) ? i % 4 : 0;}

[dotdash]

I have a patch for this, but it's currently blocked on http://llvm.org/bugs/show_bug.cgi?id=19250 -- just to make sure that nobody wastes his time on this.