Code with goto is 3x faster than code with continue

[gbaraldi]

While debugging JuliaLang/julia#47542 I managed to reproduce the same slowdown with C code, https://godbolt.org/z/789GdG3bE.

The code is

__attribute__((noinline)) size_t foo(int64_t *arr, size_t len) {
    size_t i = 0;
    foo:
    while (i < len) {
        if (arr[i] == 0) {
            i += 1;
            goto foo;
        }
        i += 2;
    }
    return i;
}

__attribute__((noinline)) size_t bar(int64_t *arr, size_t len) {
    size_t i = 0;
    while (i < len) {
        if (arr[i] == 0) {
            i += 1;
            continue;
        }
        i += 2;
    }
    return i;
}

The difference is that code with continue gets compiled to a select where the goto keeps the branch. I imagine this is a choice done in SimplifyCFG but I imagine that branch prediction/speculation on this is good enough that the conditional increment done on the continue case is much worse. Goto was faster on everything I tested (2 aarch64 cpus and 2 x86 cpus)

define dso_local i64 @foo(ptr nocapture noundef readonly %0, i64 noundef %1) local_unnamed_addr #0 {
  %3 = icmp eq i64 %1, 0
  br i1 %3, label %17, label %4

4:
  %5 = phi i64 [ %16, %15 ], [ 0, %2 ]
  %6 = getelementptr inbounds nuw i64, ptr %0, i64 %5
  %7 = load i64, ptr %6, align 8
  %8 = icmp eq i64 %7, 0
  br i1 %8, label %9, label %12

9:
  %10 = add nuw i64 %5, 1
  %11 = icmp ult i64 %10, %1
  br i1 %11, label %15, label %17

12:
  %13 = add i64 %5, 2
  %14 = icmp ult i64 %13, %1
  br i1 %14, label %15, label %17

15:
  %16 = phi i64 [ %13, %12 ], [ %10, %9 ]
  br label %4

17:
  %18 = phi i64 [ 0, %2 ], [ %10, %9 ], [ %13, %12 ]
  ret i64 %18
}

define dso_local i64 @bar(ptr nocapture noundef readonly %0, i64 noundef %1) local_unnamed_addr #0 {
  %3 = icmp eq i64 %1, 0
  br i1 %3, label %12, label %4

4:
  %5 = phi i64 [ %10, %4 ], [ 0, %2 ]
  %6 = getelementptr inbounds nuw i64, ptr %0, i64 %5
  %7 = load i64, ptr %6, align 8
  %8 = icmp eq i64 %7, 0
  %9 = select i1 %8, i64 1, i64 2
  %10 = add i64 %5, %9
  %11 = icmp ult i64 %10, %1
  br i1 %11, label %4, label %12

12:
  %13 = phi i64 [ 0, %2 ], [ %10, %4 ]
  ret i64 %13
}

[firewave]

Unlikely to be related but I encountered a case where a redundant continue leads to profoundly different (and worse) code: #64221.

[dzaima]

Note that this depends on the distribution of the input array. Changing the arr[i] = i % 2; to arr[i] = rand() % 2; results in bar becoming faster.

Adding __builtin_expect(x, 0) or __builtin_expect(x, 1) around arr[i] == 0 makes the continue version fast for the original input also. I suppose what would be desired here is a __builtin_predictable as opposed to __builtin_unpredictable, but that doesn't exist. (and __builtin_unpredictable doesn't do anything when applied to foo)

[gbaraldi]

Yeah, I guess that's fair. Though one thing that's still maybe odd is why does one piece of code decide to go for select while the other goes for a branch. Do we assign a default weight to continue vs goto?