Room for optimization improvement on reference counting

[alexcrichton]

Playground

I would expect this function to be ideally optimized to a no-op:

#[inline(never)]
fn foo<T>(t: &Rc<T>) {
    drop(t.clone());  
}

However, when invoked with Rc<int>, we generate the following optimized IR

; Function Attrs: noinline nounwind uwtable
define internal fastcc void @_ZN3foo20h529f5691b0db4704gaa4v0.0E(%"struct.std::rc::Rc<int>[#1]"* nocapture readonly) unnamed_addr #3 {
entry-block:
  %1 = getelementptr inbounds %"struct.std::rc::Rc<int>[#1]"* %0, i64 0, i32 0
  %2 = load %"struct.std::rc::RcBox<int>[#1]"** %1, align 8
  %3 = getelementptr inbounds %"struct.std::rc::RcBox<int>[#1]"* %2, i64 0, i32 1
  %4 = load i64* %3, align 8
  %5 = add i64 %4, 1
  store i64 %5, i64* %3, align 8
  %6 = load %"struct.std::rc::RcBox<int>[#1]"** %1, align 8
  %7 = icmp eq %"struct.std::rc::RcBox<int>[#1]"* %6, null
  br i1 %7, label %_ZN3mem4drop20hf8ea12715443e741vda4v0.0E.exit, label %then-block-241-.i.i.i

then-block-241-.i.i.i:                            ; preds = %entry-block
  %8 = getelementptr inbounds %"struct.std::rc::RcBox<int>[#1]"* %6, i64 0, i32 1
  %9 = load i64* %8, align 8
  %10 = add i64 %9, -1
  store i64 %10, i64* %8, align 8
  %11 = icmp eq i64 %10, 0
  br i1 %11, label %then-block-262-.i.i.i, label %_ZN3mem4drop20hf8ea12715443e741vda4v0.0E.exit

then-block-262-.i.i.i:                            ; preds = %then-block-241-.i.i.i
  %12 = getelementptr inbounds %"struct.std::rc::RcBox<int>[#1]"* %6, i64 0, i32 2
  %13 = load i64* %12, align 8
  %14 = add i64 %13, -1
  store i64 %14, i64* %12, align 8
  %15 = icmp eq i64 %14, 0
  br i1 %15, label %then-block-270-.i.i.i, label %_ZN3mem4drop20hf8ea12715443e741vda4v0.0E.exit

then-block-270-.i.i.i:                            ; preds = %then-block-262-.i.i.i
  %16 = bitcast %"struct.std::rc::RcBox<int>[#1]"* %6 to i8*
  tail call void @free(i8* %16) #2
  br label %_ZN3mem4drop20hf8ea12715443e741vda4v0.0E.exit

_ZN3mem4drop20hf8ea12715443e741vda4v0.0E.exit:    ; preds = %entry-block, %then-block-241-.i.i.i, %then-block-262-.i.i.i, %then-block-270-.i.i.i
  ret void
}

I would expect that we would be able to do better.

[alexcrichton]

I think that this is partly because LLVM doesn't understand that &Rc<int> will never alias *RcBox<int>, so this may just be a "implement TBAA" bug

[thestinger]

The situation is improved with the parameter marked as noalias, but it still doesn't optimize out.

[dotdash]

With aliasing out of the way, LLVM still can't know that the refcount isn't already 0 when entering the function, so it can't remove the code.

[thestinger]

Maybe an intrinsic for doing a load with a range assertion would work.

[dotdash]

Range asserts don't help here, they're not used to optimize the icmp away.
And last time I tried to add support for that to LLVM, it affected some
other optimizations in a bad way. Leading to worse results overall. Maybe I
just messed up the implementation though
Am 20.07.2014 01:16 schrieb "Daniel Micay" notifications@github.com:

Maybe an intrinsic for doing a load with a range assertion would work.

—
Reply to this email directly or view it on GitHub
#13018 (comment).

[alexcrichton]

#21418 didn't actually land :( (had to revert)

[steveklabnik]

Triage: runnable code

use std::rc::Rc;

#[inline(never)]
fn foo<T>(t: &Rc<T>) {
    drop(t.clone());  
}

fn main() {
    let r = Rc::new(5);

    foo(&r);
}

I'm not aware of any improvements in this area, nor am I good enough with LLVM IR to tell if things have changed.

[jruderman]

LLVM still can't know that the refcount isn't already 0

Adding assume(self.strong() != 0) to the top of clone() might fix this. rc.rs already uses assume in other places so this wouldn't be unprecedented.

Even with this change, the overflow check in inc_strong might also prevent the optimization. Not sure what to do about that :/

[huonw]

@jruderman that is similar to what was tried in #21418, but was found to be a serious compilation time hit (#21418 (comment)). The assumes there currently were added in #21894.