TypeSwitchNode, that's a hairy yak to shave, if you ask me

[Garcia Gutierrez Miguel Alfredo]

Another attempt at understanding Graal, this time devising candidate additions to ConditionalEliminationPhase's functionality.

Before getting to the "candidate additions", please check the following assumptions about TypeSwitchNode (read: corrections are welcome)



Assumptions (about TypeSwitchNode's structure)
----------------------------------------------

TypeSwitchNode:
  - lists zero or more non-default branches, and one default branch
  - each non-default branch is associated with a (non-abstract-class or array) type E (as opposed to interface type)
  - all such Es are pairwise distinct
  - different branches may share the same successor.
  - the order of the branches is not relevant (granted, different branches have in general different frequencies)

Corollaries:

  (i) if a non-default branch B points to the default case,
      then B can be elided (a form of canonicalization).

 (ii) a TypeSwitchNode consisting only of the default case
      can be reduced to just that successor.



Assumptions (about TypeSwitchNode's behavior)
---------------------------------------------

TypeSwitchNode evaluates an scrutinee at runtime.

!!! A (rather fundamental) question: can the scrutinee be null? (For now assuming it can be null). !!!

If the scrutinee is null then the TSN's default branch is taken
Otherwise, the (exact) runtime-type S of the scrutinee is compared against each of the TSN's non-default branches:
  - an exact match (ie instanceof isn't enough) on a branch B results in taking that branch
  - otherwise the default branch is taken.

The successor of each (default or non-default) branch of a TSN can only be reached via the TSN node (ie we can rely on the scrutinee fulfilling the type-check implied by the branch or branches leading there, in particular for the default case where such property reads "the scrutinee is either null, or its exact type is none of the Es (listed in the non-default branches)").



Additional simplifications for TypeSwitchNodes (during ConditionalEliminationPhase)
-----------------------------------------------------------------------------------

With the information tracked by ConditionalEliminationPhase for each program point, "in theory" the following simplifications could be performed (caveat: assumptions OK, "implementation details" postponed to the next section).

(1) if the scrutinee is known to be null
     then the TSN's only viable successor is the default branch

otherwise

(2) if the scrutinee is known to be non-null,
    and moreover its tracked-type S (ie tracked by ConditionalPhaseElimination, not the stamp)
                 is either a final-class or is array,
    then a single surviving branch can be determined statically
      (the default-branch if S doesn't match any of the branches' types, one particular branch otherwise)

otherwise

(3) if the scrutinee is known to be non-null,
       and its tracked-type is S (ie the scrutinee must be instanceof S)
    then
      for each non-default branch (whose exact-type is E)
      check if the tracked-type of the scrutinee (S) is not assignable from E
      in that case, the branch can't be taken, and can be elided.

The idea is to check (1) to (3) in sequence, ie (1) is more specific than (2), and (2) more specific than (3).



Pruning TypeSwitchNode, "Implementation details"
------------------------------------------------

The previous section talks about removing one or more TSN branches, as if ConditionalEliminationPhase could do that all by itself. Perhaps it can, at the cost of duplicating the functionality of TypeSwitchNode.simplify(). To avoid that duplication, could the following be pulled off?

(a) Once ConditionalEliminationPhase has determined a more specific tracked-type for the scrutinee (ie more specific than its stamp, in particular more specific because of inferred nullness-status),

How about replacing the usages of the scrutinee with a PiNode? That way, TypeSwitchNode.simplify() will pick up the additional type-information, and simplify the TSN's branches accordingly.

Actually, right now, TypeSwitchNode.simplify() wouldn't pick up the "additional type information" that a PiNode conveys, because currently TypeSwitchNode.simplify() bases its decisions on ConstantNode or the stamp of LoadHubNode, only. Perhaps something can be done about that?



Narrowing the scrutinee's type to an exact type in (some) non-default branches of a TypeSwitchNode
--------------------------------------------------------------------------------------------------

Question: Is there some way to identify all usages of a scrutinee within a non-default branch B of a TypeSwitchNode (and only in that branch)?. I have no idea whether this is being done already, but:
  - under the condition that none of the other TSN's branches  shares the same successor with B,
  - (looks like) a PiNode could be inserted on entry to B's successor, thus potentially triggering further type-specialization down the road.



cheers,


Miguel
http://magarciaepfl.github.io/scala/



--
Miguel Garcia
Swiss Federal Institute of Technology
EPFL - IC - LAMP1 - INR 328 - Station 14
CH-1015 Lausanne - Switzerland
http://lamp.epfl.ch/~magarcia/