unconstrained-region.rs hits a codegen bug

[thestinger]

This hits a segmentation fault on Linux x86_64. It's currently xfail'ed.

[thestinger]

Confirmed that this segfaults on OS X too, removing the A-linux tag.

[thestinger]

[109813.326976] traps: out[17264] trap invalid opcode ip:400a39 sp:23f1fc0 error:0 in out[400000+1000]
[109966.893044] traps: out[17294] trap invalid opcode ip:400a39 sp:f6dfc0 error:0 in out[400000+1000]
[109976.437905] traps: out[17317] trap invalid opcode ip:400a39 sp:10c4fc0 error:0 in out[400000+1000]

consistently dies in the same place, but there's no instruction there?

  400a32:   00 00 00 
  400a35:   49 bb 00 00 00 00 00    movabs $0x0,%r11
  400a3c:   00 00 00 
  400a3f:   e8 60 02 00 00          callq  400ca4 <__morestack>

Are we aligning functions wrong or making closure pointers wrong?

[Aatch]

This may be related to an LLVM bug, but we seem to be putting out something that slips through LLVM's linter. Using opt to output IR between each pass (just using the standard -O2 here, doesn't make a difference), I unearth this gem:

;*** IR Dump After Simplify the CFG ***
; Function Attrs: uwtable
define internal fastcc void @_ZN4main16_d7d397690bb61803_00E() #1 {
static_allocas:
%0 = alloca {}, align 8
%1 = bitcast {}* %0 to i8*
call void @llvm.lifetime.start(i64 0, i8* %1)
%2 = load i64** undef, align 8
store i64 1, i64* %2, align 8
call void @llvm.lifetime.end(i64 0, i8* %1)
ret void
}
;*** IR Dump After Combine redundant instructions ***
; Function Attrs: uwtable
define internal fastcc void @_ZN4main16_d7d397690bb61803_00E() #1 {
static_allocas:
store i64* undef, i64** null, align 536870912 ; (536870912 = 0x20000000)
store i64 1, i64* undef, align 8
ret void
}
;*** IR Dump After Tail Call Elimination ***
; Function Attrs: uwtable
define internal fastcc void @_ZN4main16_d7d397690bb61803_00E() #1 {
static_allocas:
store i64* undef, i64** null, align 536870912
store i64 1, i64* undef, align 8
ret void
}
;*** IR Dump After Simplify the CFG ***
; Function Attrs: uwtable
define internal fastcc void @_ZN4main16_d7d397690bb61803_00E() #1 {
static_allocas:
call void @llvm.trap()
unreachable
}

Technically, there is nothing wrong with doing a 512MiB-aligned store of undef to null, but it seems that somewhere along the line, we have introduced undefined behaviour that it really doesn't like, but isn't picked up by the linter.

[thestinger]

Nominating for production ready.

[Aatch]

Ok, more trawling through IR turned up this:

*** IR Dump After Deduce function attributes ***
; Function Attrs: uwtable
define internal fastcc void @_ZN4main16_d7d397690bb61803_00E() #1 {
static_allocas:
  %tmp.i4 = alloca {}, align 8
  %tmp.i = alloca { i64, %tydesc*, {}*, {}*, { i64** } }, align 8
  %0 = bitcast { i64, %tydesc*, {}*, {}*, { i64** } }* %tmp.i to i8*
  call void @llvm.lifetime.start(i64 40, i8* %0)
  %tmp6.i = bitcast { i64, %tydesc*, {}*, {}*, { i64** } }* %tmp.i to { i64, %tydesc*, i8*, i8*, i8 }*
  call void @llvm.lifetime.end(i64 40, i8* %0)
  %1 = bitcast {}* %tmp.i4 to i8*
  call void @llvm.lifetime.start(i64 0, i8* %1)
  %tmp2.i = getelementptr inbounds { i64, %tydesc*, i8*, i8*, i8 }* %tmp6.i, i64 0, i32 4
  %tmp3.i = bitcast i8* %tmp2.i to i64***
  %tmp4.i = load i64*** %tmp3.i, align 8
  %tmp5.i = load i64** %tmp4.i, align 8
  %tmp6.i5 = load i64* %tmp5.i, align 8
  %tmp7.i = add i64 %tmp6.i5, 1
  store i64 %tmp7.i, i64* %tmp5.i, align 8
  %tmp8.i = load {}* %tmp.i4, align 8
  %2 = bitcast {}* %tmp.i4 to i8*
  call void @llvm.lifetime.end(i64 0, i8* %2)
  ret void
}
*** IR Dump After SROA ***
; Function Attrs: uwtable
define internal fastcc void @_ZN4main16_d7d397690bb61803_00E() #1 {
static_allocas:
  %tmp.i4 = alloca {}, align 8
  %0 = bitcast {}* %tmp.i4 to i8*
  call void @llvm.lifetime.start(i64 0, i8* %0)
  %tmp5.i = load i64** undef, align 8
  %tmp6.i5 = load i64* %tmp5.i, align 8
  %tmp7.i = add i64 %tmp6.i5, 1
  store i64 %tmp7.i, i64* %tmp5.i, align 8
  %tmp8.i = load {}* %tmp.i4, align 8
  %1 = bitcast {}* %tmp.i4 to i8*
  call void @llvm.lifetime.end(i64 0, i8* %1)
  ret void
}

SROA is scalar replacement of aggregates, so in this particular instance, the aggregate is the alloca'd box. The value of the box just after the alloca (%tmp.i) is undef. Since this is an opaque box, we get a pointer to the placeholder i8, and cast it to an i64***. Now, both pointers here are defined, they point to the stack. However, when we load from the pointer, we're back into undef territory. Since we then follow this undef pointer, we keep being undef. When we do something with the i64 at the end, that is still undef. A later pass ("Combine redundant instructions") to be precise, sees all this adjacent undef optations and combines them down to some undef stores to null. That is replaced with a call to @llvm.trap shortly afterwards.

This is a fair way through the pipeline though, so I'm not sure how it relates to the original code exactly yet. Thought I'd share my findings so far.

[Aatch]

Ok, getting closer, tracing back a bit more, I find this:

; Function Attrs: uwtable
define internal fastcc void @_ZN4main16_d7d397690bb61803_00E() #1 {
static_allocas:
  %tmp.i = alloca { i64, %tydesc*, {}*, {}*, { i64* } }, align 8
  %state.i = alloca i64, align 8
  %0 = bitcast i64* %state.i to i8*
  call void @llvm.lifetime.start(i64 8, i8* %0)
  store i64 543210, i64* %state.i, align 8
  %1 = bitcast { i64, %tydesc*, {}*, {}*, { i64* } }* %tmp.i to i8*
  call void @llvm.lifetime.start(i64 40, i8* %1)
  %tmp7.i = bitcast { i64, %tydesc*, {}*, {}*, { i64* } }* %tmp.i to { i64, %tydesc*, i8*, i8*, i8 }*
  %tmp8.i = getelementptr inbounds { i64, %tydesc*, {}*, {}*, { i64* } }* %tmp.i, i64 0, i32 0
  store i64 305419896, i64* %tmp8.i, align 8
  %tmp9.i = getelementptr inbounds { i64, %tydesc*, {}*, {}*, { i64* } }* %tmp.i, i64 0, i32 4, i32 0
  store i64* %state.i, i64** %tmp9.i, align 8
  call void @llvm.lifetime.end(i64 40, i8* %1)
  %tmp18.i = call {} @_ZN4test4anon4anon12expr_fn_2956E({ i64, %tydesc*, i8*, i8*, i8 }* %tmp7.i)
  call void @llvm.lifetime.end(i64 8, i8* %0)
  ret void
}
*** IR Dump After Dead Store Elimination ***
; Function Attrs: uwtable
define internal fastcc void @_ZN4main16_d7d397690bb61803_00E() #1 {
static_allocas:
  %tmp.i = alloca { i64, %tydesc*, {}*, {}*, { i64* } }, align 8
  %state.i = alloca i64, align 8
  %0 = bitcast i64* %state.i to i8*
  call void @llvm.lifetime.start(i64 8, i8* %0)
  %1 = bitcast { i64, %tydesc*, {}*, {}*, { i64* } }* %tmp.i to i8*
  call void @llvm.lifetime.start(i64 40, i8* %1)
  %tmp7.i = bitcast { i64, %tydesc*, {}*, {}*, { i64* } }* %tmp.i to { i64, %tydesc*, i8*, i8*, i8 }*
  call void @llvm.lifetime.end(i64 40, i8* %1)
  %tmp18.i = call {} @_ZN4test4anon4anon12expr_fn_2956E({ i64, %tydesc*, i8*, i8*, i8 }* %tmp7.i)
  call void @llvm.lifetime.end(i64 8, i8* %0)
  ret void
}

The llvm.lifetime.* calls are inserted by LLVM during inlining. This is because all the alloca calls are hoisted to the top of the block, so LLVM uses those calls to indicate where the value is considered "live" and where it is considered "dead", between the two is essentially the body of the inlined function.

In this case (I've been making cosmetic changes in order to make it easier to follow), the lifetime of %tmp.i starts just after the store to %state.i and ends just before the call to test::anon::anon::expr_fn. Unfortunately, the value passed to that function is %tmp7.i which is a bitcast of %tmp.i, thus LLVM considers it dead at the call site. Since that's the only place a few of the stores (notably the store of the pointer to %state.i to the environment) are read, it eliminates them as dead stores.

Again, I'm not sure why it ends up like this, though I'm not going to rule out an LLVM bug at this point.

[Aatch]

Ok, I tried disabling inlining and now, instead of getting a trap, I get a segmentation fault. So we are definately producing something incorrect here.

I think it may be related to the way the closure environment works and it is possibly caused by something incorrect with the way the environment is re-captured in the inner-most closure.

Changing the state variable to an @mut doesn't fix the problem either.

Furthermore, trying to print the value of state to the terminal results in a segmentation fault as well.

cc @nikomatsakis & @pcwalton for some more knowledgable input

[Aatch]

I have now managed to reduce the test case, based on what I thought the error might be to this:

fn main() {
    let mut state = 54321;
    let a = || { 
        || { state += 1 }
    };

    a()();
}

Which exhibits the same error.

[thestinger]

Also happens with state = state + 1 so it's not related to the poor implementation of the in-place operators.

[Blei]

This is very suspicious. From rustc --passes '' --emit-llvm foo.rs:

[...]
  store i64 54321, i64* %1
[...]
  store i64 305419896, i64* %8  // in hex: 0x12345678
[...]

Looks like dummy values, but I haven't yet found out where they are inserted.

Edit: scratch that: the first one is obviously from the input program. Still interested in the second one though.

Edit2: this mystery has been solved as well: middle/trans/closure.rs:175. Sorry for the noise.

[dotdash]

Stripping passes off the end of the chain, after dropping `dse I end up with this:

; ModuleID = 'issue7336.rc'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%tydesc = type { i64, i64, void ({}*, %tydesc**, i8*)*, void ({}*, %tydesc**, i8*)*, void ({}*, %tydesc**, i8*)*, void ({}*, %tydesc**, i8*)*, i8*, i8* }

@_rust_crate_map_toplevel = global { i32, i8*, i64, [2 x i64] } { i32 1, i8* bitcast (void ({ i64, %tydesc*, i8*, i8*, i8 }*)* @_ZN7cleanup10annihilate16_82984335c95fdd56_07preE to i8*), i64 ptrtoint ([1 x { i64, i64 }]* @_rust_mod_map to i64), [2 x i64] [i64 ptrtoint (i64* @_rust_crate_map_std_0.7-pre_6c65cf4b443341b1 to i64), i64 0] }
@_rust_crate_map_std_0.7-pre_6c65cf4b443341b1 = external global i64
@_rust_mod_map = internal global [1 x { i64, i64 }] zeroinitializer
@rust_abi_version = constant i64 1

define void @_rust_main({ i64, %tydesc*, i8*, i8*, i8 }* nocapture) #0 {
static_allocas:
  ret void
}

define i64 @main(i64, i8**) {
top:
  %2 = tail call i64 @_ZN8unstable4lang5start17_76d6c774aa357c7a6_07preE({ i64, %tydesc*, i8*, i8*, i8 }* null, i8* bitcast (void ({ i64, %tydesc*, i8*, i8*, i8 }*)* @_rust_main to i8*), i64 %0, i8** %1, i8* bitcast ({ i32, i8*, i64, [2 x i64] }* @_rust_crate_map_toplevel to i8*))
  ret i64 %2
}

declare i64 @_ZN8unstable4lang5start17_76d6c774aa357c7a6_07preE({ i64, %tydesc*, i8*, i8*, i8 }*, i8*, i64, i8**, i8*)

declare void @_ZN7cleanup10annihilate16_82984335c95fdd56_07preE({ i64, %tydesc*, i8*, i8*, i8 }*)

declare void @llvm.lifetime.start(i64, i8* nocapture) #1

declare void @llvm.lifetime.end(i64, i8* nocapture) #1

attributes #0 = { readnone }
attributes #1 = { nounwind }

Adding dse back gets me:

; ModuleID = 'issue7336.rc'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%tydesc = type { i64, i64, void ({}*, %tydesc**, i8*)*, void ({}*, %tydesc**, i8*)*, void ({}*, %tydesc**, i8*)*, void ({}*, %tydesc**, i8*)*, i8*, i8* }

@_rust_crate_map_toplevel = global { i32, i8*, i64, [2 x i64] } { i32 1, i8* bitcast (void ({ i64, %tydesc*, i8*, i8*, i8 }*)* @_ZN7cleanup10annihilate16_82984335c95fdd56_07preE to i8*), i64 ptrtoint ([1 x { i64, i64 }]* @_rust_mod_map to i64), [2 x i64] [i64 ptrtoint (i64* @_rust_crate_map_std_0.7-pre_6c65cf4b443341b1 to i64), i64 0] }
@_rust_crate_map_std_0.7-pre_6c65cf4b443341b1 = external global i64
@_rust_mod_map = internal global [1 x { i64, i64 }] zeroinitializer
@rust_abi_version = constant i64 1

define void @_rust_main({ i64, %tydesc*, i8*, i8*, i8 }* nocapture) {
static_allocas:
  tail call void @llvm.trap()
  unreachable
}

define i64 @main(i64, i8**) {
top:
  %2 = tail call i64 @_ZN8unstable4lang5start17_76d6c774aa357c7a6_07preE({ i64, %tydesc*, i8*, i8*, i8 }* null, i8* bitcast (void ({ i64, %tydesc*, i8*, i8*, i8 }*)* @_rust_main to i8*), i64 %0, i8** %1, i8* bitcast ({ i32, i8*, i64, [2 x i64] }* @_rust_crate_map_toplevel to i8*))
  ret i64 %2
}

declare i64 @_ZN8unstable4lang5start17_76d6c774aa357c7a6_07preE({ i64, %tydesc*, i8*, i8*, i8 }*, i8*, i64, i8**, i8*)

declare void @_ZN7cleanup10annihilate16_82984335c95fdd56_07preE({ i64, %tydesc*, i8*, i8*, i8 }*)

declare void @llvm.lifetime.start(i64, i8* nocapture) #0

declare void @llvm.lifetime.end(i64, i8* nocapture) #0

declare void @llvm.trap() #1

attributes #0 = { nounwind }
attributes #1 = { noreturn nounwind }

This reminds me of the problem with glue inlining, which failed due to the casts on the function pointers inside the call instruction. Interestingly, there is a call to LLVMBuildPointerCast that should cast the function pointer before passing it to LLVMBuildCall, but for some reason, there's no bitcase inserted before the call.

[dotdash]

My intermediate results seem to be misleading, removing the outer closure only removes the lifetime.start/end and trap function declarations, but dse doesn't kill it anymore. Probably the lifetimes are kept internally, but aren't output anymore at the stage that I captured.

[Aatch]

Ok, I think I've finally figured it out. Stack closures capture their environment by reference, always. This makes sense since all the lifetimes are known and it's pretty much what makes most usage of stack closures usable.

Because of the way capturing works, a variable is captured all the way up the "closure chain" to where it starts life. Again, this makes sense, an outer closure must logically capture a variable if an inner closure is to use it. Another side to this is that inner closures actually capture the parents environment, not the actual captured environment. This is so everything plays nice with copying-closures, don't want an inner stack closure capturing the top environment by reference if it's nested inside a heap closure.

Essentially the code above is functionally equivalent to this:

fn main() {
    let mut state = 54321;
    let a = || {
        let statep = &mut state;
        let f = || { *statep += 1 };
        f
    };

    a()();
}

There is, however, one major difference. That code doesn't compile. Specifically it fails the borrow check. Why? Because the captured variable, statep doesn't last long enough, which is true. This means that in the original example, the closure returned from calling a() contains a pointer to inside a, which is undefined. After inlining, LLVM sees the undefined behaviour and reduces it all down.

[nikomatsakis]

So the problem is that the regionck code does not add a maximal constraint to the closure lifetime apart from the fact that they must not outlive the free variables. My first fix was to use the innermost cleanup scope but this is stricter actually stricter than necessary. It also breaks various uses of iter. The proper fix is innermost repeating scope, which is simple to compute, but more than I feel like doing tonight. I'll prepare a PR tomorrow.