Canonicalize pass can break control-dependency-as-data-dependency chains

[mkustermann]

For this code:

import 'dart:typed_data';

@pragma('vm:never-inline')
void callWith<T>(void Function(T arg) fun, T arg) {
  fun(arg);
}

void main() {
  callWith<Uint8List>((Uint8List list) {
    if (list[0] != 0) throw 'a';
  }, Uint8List(10));
}

Before Canonicalize:

*** BEGIN CFG
Before Canonicalize
==== file:///usr/local/google/home/kustermann/repositories/sdk-gclient4/sdk/xx.dart_::_main_<anonymous closure> (ClosureFunction)
B0[graph]:0 {
      v0 <- Constant(#null) T{Null?}
      v1 <- Constant(#<optimized out>)
      v4 <- Constant(#2) T{_Smi}
      v13 <- Constant(#Type: Uint8List*) T{_Type}
      v18 <- Constant(#0) T{_Smi}
      v23 <- Constant(#true) T{bool}
      v24 <- Constant(#a) T{_OneByteString}
}
B1[function entry]:2 {
      v27 <- Parameter(0) T{*?}
      v28 <- Parameter(1) T{*?}
}
    goto:38 B5
B6[function entry]:40 {
      v2 <- Parameter(0) T{*?}
      v3 <- Parameter(1) T{Uint8List?}
}
    goto:42 B5
B5[join]:36 pred(B1, B6) {
      v5 <- phi(v27, v2) alive T{*?}
      v7 <- phi(v28, v3) alive T{*?}
      v9 <- phi(v18, v4) alive T{_Smi}
}
    v11 <- LoadField(v5 . Closure.context {final})
    goto:6 B2
B2[join]:4 pred(B5)
    CheckStackOverflow:8(stack=0, loop=0)
    DebugStepCheck:10()
    Branch if StrictCompare:44(===, v9, v4) goto (7, 8)
B7[target]:48
    v25 <- Redefinition(v7 ^ T{Uint8List?}) T{Uint8List?}
    goto:56 B9
B8[target]:50
    v14 <- AssertAssignable:12(v7, v13, 'list', instantiator_type_args(v0), function_type_args(v0)) T{Uint8List?}
    goto:54 B9
B9[join]:52 pred(B7, B8) {
      v16 <- phi(v25, v14) alive T{Uint8List?}
}
    v19 <- InstanceCall:14( []<0>, v16, v18 IC[0: ], result_type = T{_Smi}) T{_Smi}
    v21 <- EqualityCompare(v19 == v18) T{bool}
    AssertBoolean:18(v21)
    Branch if StrictCompare:20(!==, v21 T{bool}, v23) goto (3, 4)
B3[target]:24
    DebugStepCheck:26()
    Throw:28(v24)
B4[target]:30
    DebugStepCheck:32()
    Return:34(v0)
*** END CFG

After canonicalize:

After Canonicalize
==== file:///usr/local/google/home/kustermann/repositories/sdk-gclient4/sdk/xx.dart_::_main_<anonymous closure> (ClosureFunction)
B0[graph]:0 {
      v0 <- Constant(#null) T{Null?}
      v1 <- Constant(#<optimized out>)
      v4 <- Constant(#2) T{_Smi}
      v13 <- Constant(#Type: Uint8List*) T{_Type}
      v18 <- Constant(#0) T{_Smi}
      v23 <- Constant(#true) T{bool}
      v24 <- Constant(#a) T{_OneByteString}
}
B1[function entry]:2 {
      v27 <- Parameter(0) T{*?}
      v28 <- Parameter(1) T{*?}
}
    goto:38 B5
B6[function entry]:40 {
      v2 <- Parameter(0) T{*?}
      v3 <- Parameter(1) T{Uint8List?}
}
    goto:42 B5
B5[join]:36 pred(B1, B6) {
      v5 <- phi(v27, v2) alive T{*?}
      v7 <- phi(v28, v3) alive T{*?}
      v9 <- phi(v18, v4) alive T{_Smi}
}
    v11 <- LoadField(v5 . Closure.context {final})
    goto:6 B2
B2[join]:4 pred(B5)
    CheckStackOverflow:8(stack=0, loop=0)
    Branch if StrictCompare:44(===, v9, v4) goto (7, 8)
B7[target]:48
    v25 <- Redefinition(v7 ^ T{Uint8List?}) T{Uint8List?}
    goto:56 B9
B8[target]:50
    v14 <- AssertAssignable:12(v7, v13, 'list', instantiator_type_args(v0), function_type_args(v0)) T{Uint8List?}
    goto:54 B9
B9[join]:52 pred(B7, B8) {
}
    v19 <- InstanceCall:14( []<0>, v7 T{Uint8List?}, v18 IC[0: ], result_type = T{_Smi}) T{_Smi}
    v21 <- EqualityCompare(v19 == v18) T{bool}
    Branch if StrictCompare:20(!==, v21 T{bool}, v23) goto (3, 4)
B3[target]:24
    Throw:28(v24)
B4[target]:30
    Return:34(v0

As we can see the canonicalize pass has removed v16 <- phi(v25, v14) alive T{Uint8List?} and made the instance call use v7.

This can be an issue if further optimization passes inline the instance call and move instructions above the AssertAssignable. (e.g. lower InstanceCall to LoadField/GenericCheckBound/AccessBytes and move LoadField before the AssertAssignable).

/cc @mraleph @alexmarkov Do you agree that we should avoid breaking such control-dependency-as-data-dependency chains during optimization?

[mraleph]

Yeah I think it might be a problem. I think when removing a Phi which has data dependency definitions as it's inputs we should consider replacing this phi with a redefinition instead of just dropping it.

[alexmarkov]

@mraleph That's a good idea - we can insert Redefinition into the beginning of the basic block when removing Phi if flow_graph->is_licm_allowed() and phi is replaced with a value which bypassed at least one redefinition.

Maybe we can also implement a pass (like FlowGraph::RenameUsesDominatedByRedefinitions) which would run immediately before LICM and would restore/establish dependencies where we lost them during graph transformations. This would make maintaining control dependencies less fragile.