#108985 optimization doesn't remove strlen like loop body in some cases

[delcypher]

In #108985 an optimization was added that tries to replace strlen like coding idioms with a call to strlen.

We ran into problems with this when this is optimization is used in -fbounds-safety.

For a test case like:

**NOTE: requires building the swift fork of llvm-project on the next branch.

// compile with -fbounds-safety
#include <ptrcheck.h>
int *__indexable convert_null_terminated_to_bounded_ptr(int *__null_terminated p) {
    return __unsafe_terminated_by_to_indexable(p);
}

the unoptimized IR looks like:

; Function Attrs: noinline nounwind optnone ssp uwtable(sync)
define [2 x i64] @convert_null_terminated_to_bounded_ptr(ptr noundef %p) #0 {
entry:
  %retval = alloca %"__bounds_safety::wide_ptr.indexable", align 8
  %p.addr = alloca ptr, align 8
  %terminated_by.len = alloca i64, align 8
  store ptr %p, ptr %p.addr, align 8
  %0 = load ptr, ptr %p.addr, align 8
  store i64 0, ptr %terminated_by.len, align 8
  br label %terminated_by.loop_cond

terminated_by.loop_cond:                          ; preds = %terminated_by.loop_cont, %entry
  %terminated_by.len1 = load i64, ptr %terminated_by.len, align 8
  %1 = getelementptr inbounds i32, ptr %0, i64 %terminated_by.len1
  %terminated_by.elem = load i32, ptr %1, align 4
  %terminted_by.check_terminator = icmp eq i32 %terminated_by.elem, 0
  br i1 %terminted_by.check_terminator, label %terminated_by.loop_end, label %terminated_by.loop_cont

terminated_by.loop_cont:                          ; preds = %terminated_by.loop_cond
  %terminated_by.new_len = add i64 %terminated_by.len1, 1
  store i64 %terminated_by.new_len, ptr %terminated_by.len, align 8
  br label %terminated_by.loop_cond

terminated_by.loop_end:                           ; preds = %terminated_by.loop_cond
  %2 = load i64, ptr %terminated_by.len, align 8
  %3 = add i64 %2, 1
  %terminated_by.upper = getelementptr inbounds i32, ptr %0, i64 %3
  %4 = getelementptr inbounds nuw %"__bounds_safety::wide_ptr.indexable", ptr %retval, i32 0, i32 0
  store ptr %0, ptr %4, align 8
  %5 = getelementptr inbounds nuw %"__bounds_safety::wide_ptr.indexable", ptr %retval, i32 0, i32 1
  store ptr %terminated_by.upper, ptr %5, align 8
  %6 = load [2 x i64], ptr %retval, align 8
  ret [2 x i64] %6
}

If we optimize this with -mllvm -disable-loop-idiom-wcslen the IR looks like

define [2 x i64] @convert_null_terminated_to_bounded_ptr(ptr noundef %p) local_unnamed_addr #0 {
entry:
  br label %terminated_by.loop_cond

terminated_by.loop_cond:                          ; preds = %terminated_by.loop_cond, %entry
  %terminated_by.len.0 = phi i64 [ 0, %entry ], [ %terminated_by.new_len, %terminated_by.loop_cond ]
  %0 = getelementptr inbounds i32, ptr %p, i64 %terminated_by.len.0
  %terminated_by.elem = load i32, ptr %0, align 4
  %terminted_by.check_terminator = icmp eq i32 %terminated_by.elem, 0
  %terminated_by.new_len = add i64 %terminated_by.len.0, 1
  br i1 %terminted_by.check_terminator, label %terminated_by.loop_end, label %terminated_by.loop_cond

terminated_by.loop_end:                           ; preds = %terminated_by.loop_cond
  %1 = getelementptr inbounds i32, ptr %p, i64 %terminated_by.len.0
  %terminated_by.upper = getelementptr i8, ptr %1, i64 4
  %2 = ptrtoint ptr %p to i64
  %.fca.0.insert = insertvalue [2 x i64] poison, i64 %2, 0
  %3 = ptrtoint ptr %terminated_by.upper to i64
  %.fca.1.insert = insertvalue [2 x i64] %.fca.0.insert, i64 %3, 1
  ret [2 x i64] %.fca.1.insert
}

Now if we optimize with the pass enabled the result looks like

; Function Attrs: nofree nounwind ssp memory(argmem: read) uwtable(sync)
define [2 x i64] @convert_null_terminated_to_bounded_ptr(ptr noundef %p) local_unnamed_addr #0 {
entry:
  %wcslen = tail call i64 @wcslen(ptr %p)
  br label %terminated_by.loop_cond

terminated_by.loop_cond:                          ; preds = %terminated_by.loop_cond, %entry
  %terminated_by.len.0 = phi i64 [ 0, %entry ], [ %terminated_by.new_len, %terminated_by.loop_cond ]
  %0 = getelementptr inbounds i32, ptr %p, i64 %terminated_by.len.0
  %terminated_by.elem = load i32, ptr %0, align 4
  %terminted_by.check_terminator = icmp eq i32 %terminated_by.elem, 0
  %terminated_by.new_len = add i64 %terminated_by.len.0, 1
  br i1 %terminted_by.check_terminator, label %terminated_by.loop_end, label %terminated_by.loop_cond

terminated_by.loop_end:                           ; preds = %terminated_by.loop_cond
  %1 = getelementptr inbounds i32, ptr %p, i64 %wcslen
  %terminated_by.upper = getelementptr i8, ptr %1, i64 4
  %2 = ptrtoint ptr %p to i64
  %.fca.0.insert = insertvalue [2 x i64] poison, i64 %2, 0
  %3 = ptrtoint ptr %terminated_by.upper to i64
  %.fca.1.insert = insertvalue [2 x i64] %.fca.0.insert, i64 %3, 1
  ret [2 x i64] %.fca.1.insert
}

This IR doesn't seem great because the call to wcslen is pointless because the loop body is still present. I would expect the perf of this code to be worse.

[delcypher]

@mustartt Is your pass supposed to eliminate the loop body is a case like this?

[delcypher]

Using this input file

bad_strlen_opt_O3_loop_idiom_disabled.txt

and running

$ bin/opt tmp/bad_strlen_opt_O3_loop_idiom_disabled.txt -S -passes=loop-idiom

seems to reproduce the problem.

[mustartt]

Thanks for letting me know. The loop idiom pass is supposed to replace all users of the loop output with the string length. Subsequent passes should be able to remove the loop body because it has no output and no observable side effects. Let me check the reproducer.

[delcypher]

Ah so the pass itself isn't responsible for removing the loop. In that case I've not given you the best reproducer. -fbounds-safety only exists the Swift fork of llvm-project right now. The next branch is continuously ingesting changes from upstream llvm-project, hence why I discovered your change changed how -fbounds-safety is codegened. If you want to reproduce this exactly as I have they you might need to use the fork.

Doing this might work in upstream llvm

$ bin/clang -O3 -S -emit-llvm tmp/bad_strlen_opt_O3_loop_idiom_disabled.ll -o - -mllvm --print-after-all

it definitely works in the fork. The call to wcslen is added but the loop body is not removed.

You'll have to rename bad_strlen_opt_O3_loop_idiom_disabled.txt to have an .ll extension (GitHub doesn't allow me to upload files ending in .ll).

[mustartt]

terminated_by.loop_end:                           ; preds = %terminated_by.loop_cond
  %1 = getelementptr inbounds i32, ptr %p, i64 %wcslen
  %terminated_by.upper = getelementptr i8, ptr %1, i64 4
  %2 = ptrtoint ptr %p to i64
  %.fca.0.insert = insertvalue [2 x i64] poison, i64 %2, 0
  %3 = ptrtoint ptr %terminated_by.upper to i64
  %.fca.1.insert = insertvalue [2 x i64] %.fca.0.insert, i64 %3, 1
  ret [2 x i64] %.fca.1.insert

In the exit block, %p, %wcslen, %1, %2, %terminated_by.upper, %3, %.fca.1.insert are not defined in the loop body. So the loop body is trivially dead, later passes like LoopDeletionPass or GVNPass should be able to remove it.

I still recall that loop-delete does not work on non-countable loops, so I wonder why gvn in this case can't remove it. Regardless, I might want to modify the loop body condition into something that loop-delete can work with so this will work more consistently.

Is there anything that this pass will inhibit for -fbound-safety>

[delcypher]

In general I don't think this optimization is profitable if the loop isn't later removed. In fact the optimization has made perf worse because now the string is walked twice, whereas before the pass it was walked once. However, knowing ahead of that time is probably tricky.

@fhahn Any suggestions on what to do here? I'm using rdar://148775324 to track this internally.

[delcypher]

@mustartt

Is there anything that this pass will inhibit for -fbound-safety>

Right now it's potentially worse performance and code size. For now we are going to modify our tests to disable the new pass and I'll discuss with my team what to do here.

[mustartt]

I will create a work item for loop idiom recognize as well to update the loop body so that subsequent passes will clean it up.