dart2js: optimization: path sensitive dominators for type propagation and GVN

[rakudrama]

dart2js should generate better code branches dependent on && and || conditions. There is a loss of useful information.

void update(String s) {
  if (s != null && s.trim().isNotEmpty) {
    print(s.trim().toUpperCase());
  }
}

main() {
  update(null);
  update(' five');
  update('  ');
}

The generated code for update has an interceptor call to s.trim():

    update: function(s) {
      var t1;
      if (s != null && C.JSString_methods.trim$0(s).length !== 0) {
        t1 = J.trim$0$s(s);
        H.printString(t1.toUpperCase());
      }
    },
  ...
  J.trim$0$s = function(receiver) {
    return J.getInterceptor$s(receiver).trim$0(receiver);
  };

Notice that the first call to trim is via a constant interceptor (J.JSString_methods). s is inferred to be String or Null (this would also be true from strong mode or --trust-type-annotations). The s != null check allows the type to be refined to non-null-String. The second call is compiled to J.trim$0$s(s) because this information is lost. The ssa block structure makes every expression, including the && expression, a single-entry-single-exit region, so the condition of the if-statement is a phi-node. The insertion of HTypeKnown removing Null from the possible types of s is only inserted in the condition rest of the condition:

  if (s != null) {
    A: cond = s.trim().isNotEmpty;   // s known not null here
  } else {
    cond = false;
  }
  if (cond) {  // the phi-node
    B: print(s.trim().toUpperCase());  // but not here
  }

One way to fix this is to generate the CFG for if (a && b) S; as if (a) if (b) S;.

Another way to fix this is to have an extended idea of domination, path sensitive dominators. The statement at B is only reachable if A was reached. Any effect-insensitive facts known at A are also true at B. When we insert HTypeKnown nodes at A, we can also insert them at B.
This is better than the first fix (if-if) since it works with code that did not originate as && syntactically in an if-expression, for example, an inlined function.

The second optimization we could do is a variant of GVN that introduces single-def variables to carry values from one dominated region to another. String.trim() is pure so we could transform the code to

  if (s != null) {
    A:
     s_trim = s.trim();
     cond = s_trim.isNotEmpty;
  } else {
    cond = false;
  }
  if (cont) {
    B: print(s_trim.toUpperCase());
  }

Discovering the path-sensitive dominators requires limited form of path-sensitive analysis. This would be more efficient after load-elimination and an initial pass of GVN to reduce the number of potentially tracked values. We would be path-sensitive only to values that flow via x != null, phi- and not-nodes to if-conditions, and are used in the controlled regions of the if. Perhaps a domain of 2^{True, False, Null, Other} would be adequate.