Segfault on loop with implicit type conversion on late variable

[Ludonope]

> dart --version
Dart SDK version: 2.13.0 (stable) (Wed May 12 12:45:49 2021 +0200) on "macos_x64"

This particular piece of code is causing a segfault for some reason:

final values = List.filled(100, 0.0);

double? fn(double day) {
  double? last;
  late int lastDay;

  int i = 0;
  print('day = $day len = ${values.length}');
  print('$i < ${values.length} = ${i < values.length}');
  while (i < values.length) {
    print('while loop i = $i');
    final t = values[i];
    if (i >= day) {
      if (last == null) return t;
      return last - lastDay;
    }
    last = t;
    lastDay = i;
    i++;
  }
  return last;
}

void main() {
  for (int i = 0; i < values.length; i++) {
    fn(i.toDouble());
  }
}

The segfault occurs on when reaching the while line when the parameter day reached the value of 89.
The last logs are the following:

...
while loop i = 86
while loop i = 87
while loop i = 88
day = 89.0 len = 100
0 < 100 = true
../../third_party/dart/runtime/vm/deopt_instructions.cc: 940: error: unreachable code
version=2.13.0 (stable) (Wed May 12 12:45:49 2021 +0200) on "macos_x64"
pid=71513, thread=6151, isolate_group=main(0x7fa78f01c800), isolate=main(0x7fa78f031600)
isolate_instructions=10b7e4580, vm_instructions=10b7e4580
Stack dump aborted because GetAndValidateThreadStackBounds failed.
/Users/ludonope/Code/flutter/bin/internal/shared.sh: line 224: 71513 Abort trap: 6           "$DART" "$@"

The error is not on the comparison since the 0 < 100 = true is printed, but the following while loop i = 0 is never reached.

Interestingly, replacing the line late int lastDay; by int lastDay = 0; fixes the issue.
Also replacing return last - lastDay; by return last - lastDay.toDouble(); fixes it.

I am not sure what the exact error is, but there are some shenanigans going on down there :)

[a-siva]

/cc @alexmarkov

[a-siva]

I see this stacktrace

  pc 0x00005598917cbc6c fp 0x00007f570f07de40 dart::Profiler::DumpStackTrace(void*)+0x7c
  pc 0x00005598913dbaf4 fp 0x00007f570f07df20 dart::Assert::Fail(char const*, ...)+0x84
  pc 0x0000559891bad0c2 fp 0x00007f570f07dfa0 dart::UnboxInstr::EmitNativeCode(dart::FlowGraphCompiler*)+0x1a2
  pc 0x0000559891b80fb7 fp 0x00007f570f07e120 dart::FlowGraphCompiler::VisitBlocks()+0x4f7
  pc 0x0000559891b8f914 fp 0x00007f570f07e150 dart::FlowGraphCompiler::CompileGraph()+0x34
  pc 0x00005598918ad46b fp 0x00007f570f07e890 dart::CompileParsedFunctionHelper::Compile(dart::CompilationPipeline*)+0x85b
  pc 0x00005598918ae472 fp 0x00007f570f07eae0 out/DebugX64/dart+0x2356472
  pc 0x00005598918af011 fp 0x00007f570f07eb70 dart::Compiler::CompileOptimizedFunction(dart::Thread*, dart::Function const&, long)+0x121
  pc 0x00005598918afe28 fp 0x00007f570f07ec30 dart::BackgroundCompiler::Run()+0x178

[alexmarkov]

Flow graph before a3767f7:

v3 <- Constant(#sentinel) T{Never}
v162 <- UnboxInt64([guard-inputs], v3) [-9223372036854775808, 9223372036854775807] T{int}
v38 <- phi(v162 T{Never}, v174 T{_Smi}) alive [-9223372036854775808, 9223372036854775807] int64 T{_Smi}

Similarly to flutter/flutter#83094, crash happens because speculative UnboxInt64 instruction for Phi was inserted without environment so CanDeoptimize() is false, but it takes input of incompatible type. However, the reason for an incompatible type is different: it takes sentinel constant of type Never, which is used to indicate uninitialized state of late variables.

Flow graph after a3767f7 which converted UnboxInt64 to non-speculative:

v3 <- Constant(#sentinel) T{Never}
v162 <- UnboxInt64([non-speculative], v3) [-9223372036854775808, 9223372036854775807] T{int}
v38 <- phi(v162 T{Never}, v174 T{_Smi}) alive [-9223372036854775808, 9223372036854775807] int64 T{_Smi}

While this example no longer crashes after a3767f7, it still doesn't look correct as sentinel value cannot be unboxed to int.

The following slightly modified example should throw LateInitializationError, but it prints garbage instead (after a3767f7):

final values = List.filled(100, 0.0);

double? fn(double day) {
  double? last;
  late int lastDay;

  int i = 0;
  while (i < values.length) {
    final t = values[i];
    if (day > 95) {
      print(lastDay);
      break;
    }
    last = t;
    lastDay = i;
    i++;
  }
  return last;
}

void main() {
  for (int i = 0; i < values.length; i++) {
    fn(i.toDouble());
  }
}

I think we shouldn't unbox Phi which may take sentinel value at all. In this case Phi is unboxed because of its type by this code:

sdk/runtime/vm/compiler/backend/flow_graph.cc

Lines 2057 to 2065 in f81de15

	#if defined(TARGET_ARCH_IS_64_BIT)
	// In AOT mode on 64-bit platforms always unbox integer typed phis (similar
	// to how we treat doubles and other boxed numeric types).
	// In JIT mode only unbox phis which are not fully known to be Smi.
	if ((unboxed == kTagged) && phi->Type()->IsInt() &&
	(is_aot || phi->Type()->ToCid() != kSmiCid)) {
	unboxed = kUnboxedInt64;
	}
	#endif

For late local variables we always check if value is a sentinel before using it, so I think this problem only affects phis.

I see the following options for fixing this:

1. We can change phi unboxing code to follow inputs recursively and check if any of them are sentinel.
2. We can also extend CompileType to have can_be_uninitialized flag in addition to is_nullable, set/propagate that flag and check it when unboxing phi.
3. Another option is to lower late local variables into 2 separate variables (initialized flag and value) and avoid using sentinel for late local variables.

@mraleph @rmacnak-google @mkustermann What do you think?

[mraleph]

I think the real problem here is that sentinel has type Never - I feel like we have discussed this before - this really violates the type system. Never is supposed to be a subtype of all types and uninhabited (e.g. function returning Never is guaranteed to never actually return normally because you can't produce a value of type Never). If we want want to work with sentinels in IL, I think we should definitely move away from typing them as Never (at least make sure that their CompileType does not behave as Never in Union operation). In that sense moving to some sort of union types (option 2 on your list) make sense: e.g. if you have a late variable of type X it has CompileType equivalent to Sentinel|X. I like this because it actually reflects how things work. int is unboxable, sentinel|int is not unboxable.

[alexmarkov]

Sentinel value is actually assignable to any Dart static type (as late variable of any type can be initialized with sentinel). The only type which has this property across all modes is Never, so it is a reasonable choice to make sentinel a value of type Never. If running in unsound mode null value is assignable to Never, so Never is not necessarily uninhabited even without this extension. So, extending Dart type Never to have an additional sentinel value doesn't really violate type system.

Having said that, I agree that it would be cleaner to reflect the extension of Dart type system with sentinel explicitly in CompileType. However, I'm thinking about this extension not as a union type, but as a more precise information about a set of values, similarly to is_nullable flag (which can be false even if null is assignable to Dart static type X and this effectively means X \ Null type). So can_be_uninitialized == false would mean X \ sentinel for a static type X.

I'll go ahead and try this approach (extending CompileType / option 2).

[mraleph]

So, extending Dart type Never to have an additional sentinel value doesn't really violate type system.

I strongly disagree with this. Never (ignoring the case when Never behaves like Null) is supposed to be uninhabited from the Dart program perspective. If there are actually values of type Never - then they can appear in any variable, which breaks things considerably e.g. an arbitrary int variable can then contain not only numbers but also this "never" values. This is obviously not the case and even though we permit sentinel values to appear in some fields and variables (more specifically lazy initialised ones), we don't allow these sentinels to flow in arbitrary ways through Dart program and be observed. They are just an implementation detail - and that's why I think it is more faithful to think about this as a union type rather than additional information about the type.

I'd like to contrast this with is_nullable flag - because that indeed is an additional information (constraint) on the otherwise Dart type. If you look at CompileType of a Definition and take its associated abstract type T and then in runtime a value produce by the definition would always be assignable to T (as described by Dart specification). e.g. if T=int? then value would always be an instance of _Smi, _Mint or null. Notice how I can just ignore is_nullable.

The story with sentinels is different because it departs from normal Dart semantics somewhat. We could ignore this somewhat in pre-NNDB world because sentinels were hiding in the Null space, but I think we ought to reconsider this in post-NNDB world.

It is somewhat unclear to me why sentinels have to be instances of Never to begin with. They should not be stored into objects using normal stores or even seen by type checks... Do you know why we decided to do that? What exactly breaks if we give them special class and start modeling CompileType of fields that can contain sentinels using a more faithful union type approach?

[alexmarkov]

ignoring the case when Never behaves like Null

Why? This is still a part of Dart language.

If there are actually values of type Never - then they can appear in any variable, which breaks things considerably e.g. an arbitrary int variable can then contain not only numbers but also this "never" values.

Sentinel can appear in a variable of any Dart type, if that variable is declared late. So, sentinel value should be assignable to any Dart type.

They are just an implementation detail <...>

That is true. Sentinel is an implementation detail, and so is the extension of Dart type system used in the compiler. I think we're just discussing how exactly the type system should be extended - either with an extra value of type Never or with union types Sentinel|X. Note that Sentinel|X compiler type should still be assignable to Dart type X. Also, the extension of Dart type system with sentinel is needed not only for compiler, but also for the runtime system which may see sentinel values when accessing objects on the heap, during hot reload, deoptimization etc.

They should not be stored into objects using normal stores <...>

They are stored using StoreInstanceField and StoreLocal, loaded with LoadLocal, may flow through Phi etc. All the real uses beyond data flow are guarded.

Do you know why we decided to do that?

I changed type of sentinel from Null to Never as Null type stopped being a bottom type since null safety was added, and assigning sentinel of Null type to variables of non-nullable types broke things. Not sure why sentinel had Null type and not a separate type before null safety.

What exactly breaks if we give them special class and start modeling CompileType of fields that can contain sentinels using a more faithful union type approach?

We can try that. I expect that making a separate VM class for sentinel would require special casing it in an unknown number of extra places. This may introduce some instability into the VM until we find all such places and fix them.

I'm leaning towards a more cautious approach of extending CompileType with explicit can_be_sentinel flag first. That can be done without affecting the rest of the VM, and it is a prerequisite for changing type of sentinel anyway.