[vm/aot] Bad code motion with `@pragma('vm:unsafe:no-bounds-checks')`

[rakudrama]

In both foo1 and foo2 generate code that crashes:

===== CRASH =====
si_signo=Segmentation fault(11), si_code=SEGV_MAPERR(1), si_addr=0x7f68355141e0
Aborted

@pragma('vm:unsafe:no-bounds-checks')
@pragma('vm:never-inline')
int foo1(String s) {
  int sum = 0;
  for (int i = 0; i < s.length; i++) {
    if (s.codeUnitAt(i) == 0) {
      sum += s.codeUnitAt(1_000_000_000);
    }
  }
  return sum; 
}

@pragma('vm:unsafe:no-bounds-checks')
@pragma('vm:never-inline')
int foo2(String s) {
  int sum = 0;
  for (int i = 1; i < s.length; i++) {
      sum += s.codeUnitAt(1_000_000_000);
  }
  return sum; 
}


main() {
  print(foo1(''));
  print(foo1('x'));
  print(foo2(''));
  print(foo2('x'));
}

The problem is that the position of the memory access is no longer constrained by the bounds check, which can throw, so is hoisted out of the loop. The programmer, even one with a licence to use the unsafe pragma, probably does not expect this result.

I worry that there are more subtle versions of this problem. For example, a bounds check would prevent partial redundancy elimination from moving a load a[i] at the top of the loop into the continue block when the same load a[0] occurs before the loop.

After bounds checks are removed there needs to be a mechanism to prevent subsequent unsound code motion. I'm not sure how this is currently done. One mechanism might be to arrange phase ordering so that there are no code motion phases after bounds check elimination optimization. If phase-ordering is mechanism, it implies that bounds check elimination cannot have been done on inlining candidates. We might know that a bounds check is safe, but it cannot be removed early.

One remedy might be to split bounds check elimination into two phases. The first, which can be run at any time, marks bounds checks as to-be-removed, but still considers them capable of throwing. This keeps the loads constrained. The second phase, after all code motion, does cleanup to remove the bounds checks and any pure transitive inputs. Inlining heuristics could discount the size of to-be-removed bounds checks. The unsafe annotation would generate the bounds check with the to-be-removed flag already set. Perhaps there could a vestigial form of the bound check without a length input to release the non-index inputs early.

[a-siva]

//cc @alexmarkov

[alexmarkov]

@mraleph Do we need to insert Redefinition instead of bounds check when they are disabled by pragma?

[mraleph]

FWIW we have the same problem with FFI where we are performing aggressive hoisting for accesses through Pointer:

@pragma('vm:never-inline')
int foo(bool v, Pointer<Int8> p) {
  var x = 0;
  for (var i = 0; i < 2; i++) {
    x ^= i;
    if (v) {
      x ^= p.value;
    }
  }
  return x;
}

void main(List<String> args) {
  foo(args.contains("should-crash"), nullptr);
}

For the pragma I like @rakudrama's suggestion to just mark bounds checks as ephemeral because that would permit hoisting if bounds check is eliminated through other means.

However for FFI we should probably just mark corresponding LoadIndexedInstr as immovable... We might really want to invest into rewriting our hoisting so that we could hoist invariants which are always executed if the body is executed and guard them by loop condition.

[rakudrama]

I'm going to attempt to fix the unwanted motion of the indexed load by keeping the check in place until EliminateRedundantBoundsChecks.