VM: MegamorphicLookup #3: large hierarchy with single target

[rakudrama]

This issue is split out from https://github.com/dart-lang/sdk/issues/26017

Data taken from running dart2js on a large app.

The HInstruction hierarchy (pkg/compiler/lib/src/ssa/nodes.dart) has 91 classes (17 abstract). The base class declares next and previous fields which are not shadowed. These field accessses are always megamorphic.

Consider the HInstructionList.detach method below. Each of the .previous and .next field access is megamorphic.

Looking at the cids, it appears that a range check might be an adequate test. With such a large number of classes, it is likely that some kind of CHA is necessary to discover the range and to avoid deopts as rare classes are instantiated.

abstract class HInstruction implements Spannable {
  ...
  HInstruction previous = null;
  HInstruction next = null;
}

class HInstructionList {
  HInstruction first = null;
  HInstruction last = null;

  void detach(HInstruction instruction) {
    if (instruction.previous == null) {
      first = instruction.next;
    } else {
      instruction.previous.next = instruction.next;
    }
    if (instruction.next == null) {
      last = instruction.previous;
    } else {
      instruction.next.previous = instruction.previous;
    }
    instruction.previous = null;
    instruction.next = null;
  }
}

class HBasicBlock extends HInstructionList {
 ...
}

[bwilkerson]

This also, not surprisingly, impacts analyzer. The class AstNodeImpl defines the method _becomeParentOf(AstNodeImpl node). Although there are a large number of subclasses of AstNodeImpl, there is only one implementation of this method. Unfortunately, this becomes a megamorphic lookup. A fix for this issue would significantly help our performance.