New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Possible codegen bug flagged by valgrind #11710

Closed
alexcrichton opened this Issue Jan 21, 2014 · 6 comments

Comments

Projects
None yet
3 participants
@alexcrichton
Member

alexcrichton commented Jan 21, 2014

I'm not sure if this is a false positive, a codegen bug, or an LLVM bug.

fn main() { do spawn {} }

That will generate a warning in valgrind about a jump based on an uninitialized value.

I've simplified it to:

use std::util;                                                     
enum Option<T> {                                                   
  None,                                                            
  Some(T),                                                         
}                                                                  
#[inline(never)]                                                   
fn function(slot: &mut Option<proc(proc()) -> proc()>, f: proc()) {
  let a = util::replace(slot, None);                               
  let a = match a {                                                
    Some(a) => bar(a, f),                                          
    None => f,                                                     
  };                                                               
  foo(a);                                                          
}                                                                  

#[inline(never)]                                                   
fn bar(f: proc(proc()) -> proc(), g: proc()) -> proc() {           
  f(g)                                                             
}                                                                  

#[inline(never)]                                                   
fn foo(_f: proc()) {                                               
}                                                                  

#[start]                                                           
fn main(_: int, _: **u8) -> int {                                  
  let mut slot = None;                                             
  function(&mut slot, proc() {});                                  
  0                                                                
}                                                                  

I tried to make this test case have as little dependence on libstd as possible, but it didn't really help much with the output IR. The function function is the one that has the valgrind warning inside it, but I can't quite figure out where.

The output assembly is https://gist.github.com/alexcrichton/8549277 and the suspicious instruction is 0x405235

@alexcrichton

This comment has been minimized.

Show comment
Hide comment
@alexcrichton

alexcrichton Jan 21, 2014

Member

Ah, I should also note that the valgrind warning only shows up when building with optimizations.

Member

alexcrichton commented Jan 21, 2014

Ah, I should also note that the valgrind warning only shows up when building with optimizations.

@dotdash

This comment has been minimized.

Show comment
Hide comment
@dotdash

dotdash Jan 25, 2014

Contributor

Slightly simpler code (IMHO):

use std::util;
enum Option<T> {
    None,
    Some(T),
}

#[inline(never)]
fn function<T>(slot: &mut Option<T>, f: T) {
    let a = util::replace(slot, None);
    let _breaker = match a {
        Some(_) => bar(f),
        None => f,
    };
}

#[inline(never)]
fn bar<T>(g: T) -> T {
    g
}

#[start]
fn main(_: int, _: **u8) -> int {
    let mut slot = None;
    function(&mut slot, proc() {});
    0
}

The rest of the code seems to be required. Or at least various attempts to simplify it further made the problem disappear.

What I figured out so far is that the problem is in the cleanup path for slot. And the test that relies on the uninitialised value is apparently for the case that slot is not None. The test for None comes right after this one, which is wrong.

Contributor

dotdash commented Jan 25, 2014

Slightly simpler code (IMHO):

use std::util;
enum Option<T> {
    None,
    Some(T),
}

#[inline(never)]
fn function<T>(slot: &mut Option<T>, f: T) {
    let a = util::replace(slot, None);
    let _breaker = match a {
        Some(_) => bar(f),
        None => f,
    };
}

#[inline(never)]
fn bar<T>(g: T) -> T {
    g
}

#[start]
fn main(_: int, _: **u8) -> int {
    let mut slot = None;
    function(&mut slot, proc() {});
    0
}

The rest of the code seems to be required. Or at least various attempts to simplify it further made the problem disappear.

What I figured out so far is that the problem is in the cleanup path for slot. And the test that relies on the uninitialised value is apparently for the case that slot is not None. The test for None comes right after this one, which is wrong.

@dotdash

This comment has been minimized.

Show comment
Hide comment
@dotdash

dotdash Jan 25, 2014

Contributor

OK, so at some point LLVM moved the loads not only for the discriminator, but also for the proc contained in slot to the beginning of function:

define internal fastcc void @_ZN8function19hf4c7ff781ac735e1an4v0.0E(%"enum.Option<proc:Send()>"* nocapture, { void ({ i64, %tydesc*, i8*, i8*, i8 }*)*, { i64, %tydesc*, i8*, i8*, i8 }* }* noalias nocapture readonly) unnamed_addr #1 {
normal-return:
  %.sroa.2 = alloca [15 x i8], align 1
  %_breaker = alloca { void ({ i64, %tydesc*, i8*, i8*, i8 }*)*, { i64, %tydesc*, i8*, i8*, i8 }* }, align 8
  %arg = alloca { void ({ i64, %tydesc*, i8*, i8*, i8 }*)*, { i64, %tydesc*, i8*, i8*, i8 }* }, align 8
  %f.sroa.0.0.idx = getelementptr inbounds { void ({ i64, %tydesc*, i8*, i8*, i8 }*)*, { i64, %tydesc*, i8*, i8*, i8 }* }* %1, i64 0, i32 0
  %f.sroa.0.0.copyload = load void ({ i64, %tydesc*, i8*, i8*, i8 }*)** %f.sroa.0.0.idx, align 8
  %f.sroa.5.0.idx19 = getelementptr inbounds { void ({ i64, %tydesc*, i8*, i8*, i8 }*)*, { i64, %tydesc*, i8*, i8*, i8 }* }* %1, i64 0, i32 1
  %f.sroa.5.0.copyload = load { i64, %tydesc*, i8*, i8*, i8 }** %f.sroa.5.0.idx19, align 8
  %.sroa.2.1.idx10 = getelementptr inbounds [15 x i8]* %.sroa.2, i64 0, i64 0

  ; Loads from slot occur here
  %tmp.sroa.0.0.idx6.i.i = getelementptr inbounds %"enum.Option<proc:Send()>"* %0, i64 0, i32 0

  ; Discriminator for slot
  %tmp.sroa.0.0.copyload7.i.i = load i8* %tmp.sroa.0.0.idx6.i.i, align 8
  %tmp.sroa.6.0.idx12.i.i = getelementptr inbounds %"enum.Option<proc:Send()>"* %0, i64 0, i32 1, i64 0
  %tmp.sroa.616.0.idx17.i.i = getelementptr inbounds %"enum.Option<proc:Send()>"* %0, i64 0, i32 2, i64 1
  %tmp.sroa.616.0.cast18.i.i = bitcast i64* %tmp.sroa.616.0.idx17.i.i to { i64, %tydesc*, i8*, i8*, i8 }**

  ; Env pointer for slot    
  %tmp.sroa.616.0.copyload19.i.i = load { i64, %tydesc*, i8*, i8*, i8 }** %tmp.sroa.616.0.cast18.i.i, align 8

And later on we have:

"_ZN17proc.Send$LP$$RP$9glue_drop19hd34fc795812c1ef2akE.exit5": ; preds = %join, %cond.i4
  %cond.not = xor i1 %cond, true
  %18 = icmp eq { i64, %tydesc*, i8*, i8*, i8 }* %tmp.sroa.616.0.copyload19.i.i, null
  %or.cond = or i1 %18, %cond.not
  br i1 %or.cond, label %"_ZN17proc.Send$LP$$RP$9glue_drop19hd34fc795812c1ef2akE.exit", label %cond.i.i8

%i18 is the result for checking whether the env pointer for the proc in slot is null, %cond.not is the result for checking whether slot is None. In the assembly that gets translated to the two conditional jumps, and the one for the env pointer comes first.

At the moment, I have no idea why that happens though.

Contributor

dotdash commented Jan 25, 2014

OK, so at some point LLVM moved the loads not only for the discriminator, but also for the proc contained in slot to the beginning of function:

define internal fastcc void @_ZN8function19hf4c7ff781ac735e1an4v0.0E(%"enum.Option<proc:Send()>"* nocapture, { void ({ i64, %tydesc*, i8*, i8*, i8 }*)*, { i64, %tydesc*, i8*, i8*, i8 }* }* noalias nocapture readonly) unnamed_addr #1 {
normal-return:
  %.sroa.2 = alloca [15 x i8], align 1
  %_breaker = alloca { void ({ i64, %tydesc*, i8*, i8*, i8 }*)*, { i64, %tydesc*, i8*, i8*, i8 }* }, align 8
  %arg = alloca { void ({ i64, %tydesc*, i8*, i8*, i8 }*)*, { i64, %tydesc*, i8*, i8*, i8 }* }, align 8
  %f.sroa.0.0.idx = getelementptr inbounds { void ({ i64, %tydesc*, i8*, i8*, i8 }*)*, { i64, %tydesc*, i8*, i8*, i8 }* }* %1, i64 0, i32 0
  %f.sroa.0.0.copyload = load void ({ i64, %tydesc*, i8*, i8*, i8 }*)** %f.sroa.0.0.idx, align 8
  %f.sroa.5.0.idx19 = getelementptr inbounds { void ({ i64, %tydesc*, i8*, i8*, i8 }*)*, { i64, %tydesc*, i8*, i8*, i8 }* }* %1, i64 0, i32 1
  %f.sroa.5.0.copyload = load { i64, %tydesc*, i8*, i8*, i8 }** %f.sroa.5.0.idx19, align 8
  %.sroa.2.1.idx10 = getelementptr inbounds [15 x i8]* %.sroa.2, i64 0, i64 0

  ; Loads from slot occur here
  %tmp.sroa.0.0.idx6.i.i = getelementptr inbounds %"enum.Option<proc:Send()>"* %0, i64 0, i32 0

  ; Discriminator for slot
  %tmp.sroa.0.0.copyload7.i.i = load i8* %tmp.sroa.0.0.idx6.i.i, align 8
  %tmp.sroa.6.0.idx12.i.i = getelementptr inbounds %"enum.Option<proc:Send()>"* %0, i64 0, i32 1, i64 0
  %tmp.sroa.616.0.idx17.i.i = getelementptr inbounds %"enum.Option<proc:Send()>"* %0, i64 0, i32 2, i64 1
  %tmp.sroa.616.0.cast18.i.i = bitcast i64* %tmp.sroa.616.0.idx17.i.i to { i64, %tydesc*, i8*, i8*, i8 }**

  ; Env pointer for slot    
  %tmp.sroa.616.0.copyload19.i.i = load { i64, %tydesc*, i8*, i8*, i8 }** %tmp.sroa.616.0.cast18.i.i, align 8

And later on we have:

"_ZN17proc.Send$LP$$RP$9glue_drop19hd34fc795812c1ef2akE.exit5": ; preds = %join, %cond.i4
  %cond.not = xor i1 %cond, true
  %18 = icmp eq { i64, %tydesc*, i8*, i8*, i8 }* %tmp.sroa.616.0.copyload19.i.i, null
  %or.cond = or i1 %18, %cond.not
  br i1 %or.cond, label %"_ZN17proc.Send$LP$$RP$9glue_drop19hd34fc795812c1ef2akE.exit", label %cond.i.i8

%i18 is the result for checking whether the env pointer for the proc in slot is null, %cond.not is the result for checking whether slot is None. In the assembly that gets translated to the two conditional jumps, and the one for the env pointer comes first.

At the moment, I have no idea why that happens though.

@dotdash

This comment has been minimized.

Show comment
Hide comment
@dotdash

dotdash Jan 26, 2014

Contributor

Getting simpler :-)

struct X {
    x: ~uint,
}

#[inline(never)]
fn function(mut slot: Option<X>) {
    let a = std::util::replace(&mut slot, None);
    let _breaker = match a {
        Some(_) => ~1,
        None => ~1,
    };
}

#[start]
fn main(_: int, _: **u8) -> int {
    function(None);
    0
}
Contributor

dotdash commented Jan 26, 2014

Getting simpler :-)

struct X {
    x: ~uint,
}

#[inline(never)]
fn function(mut slot: Option<X>) {
    let a = std::util::replace(&mut slot, None);
    let _breaker = match a {
        Some(_) => ~1,
        None => ~1,
    };
}

#[start]
fn main(_: int, _: **u8) -> int {
    function(None);
    0
}
@thestinger

This comment has been minimized.

Show comment
Hide comment
@thestinger

thestinger Jan 26, 2014

Contributor

This is a known valgrind false positive and Rust already has a lot of suppressions for it. It's reported upstream on the LLVM bug tracker but is not really an LLVM issue, just a limitation of valgrind. LLVM is allowed to generate undefined reads if it can not change the program behavior.

http://llvm.org/bugs/show_bug.cgi?id=12319

Contributor

thestinger commented Jan 26, 2014

This is a known valgrind false positive and Rust already has a lot of suppressions for it. It's reported upstream on the LLVM bug tracker but is not really an LLVM issue, just a limitation of valgrind. LLVM is allowed to generate undefined reads if it can not change the program behavior.

http://llvm.org/bugs/show_bug.cgi?id=12319

@thestinger thestinger closed this Jan 26, 2014

@dotdash

This comment has been minimized.

Show comment
Hide comment
@dotdash

dotdash Jan 26, 2014

Contributor

Just for the record, the undefined read doesn't change the behaviour because it's just a check whether free should not be called, i.e. either it jumps over the free call right away, or it performs the second check.

Contributor

dotdash commented Jan 26, 2014

Just for the record, the undefined read doesn't change the behaviour because it's just a check whether free should not be called, i.e. either it jumps over the free call right away, or it performs the second check.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment