• BaselineCopyElimination

Baseline Copy Elimination

The baseline compiler tries to avoid move instructions by:

• Allocating local variables that act as parameters in leaf methods to the corresponding argument registers. (This eliminates copy instructions in the method prolog.)
• Coalescing temporary variables with local variables. This removes the move instruction corresponding to the LOAD or STORE instructions. The temporary variable is marked as LOCALVAR.
• Coalescing temporary variables with interface variables. This removes the move instructions at the beginning/end of the basic block. The temporary variable is marked as STACKVAR.
• Precoloring temporary variables used as arguments for calling methods. The temporary variable is marked as ARGVAR.
• Coalescing temporary variables that are copied by DUP* instructions.

Eliminating LOADs

A LOAD creates a copy edge from a local variable Li to a temporary variable Tj. The copy may be eliminated if Li and Tj do not interfere.

We assume that Tj is unmarked. Thus the LOAD is known to be the only DEF of Tj. So the only way Li and Tj could interfere is that there is a DEF Li during the livetime of Tj.

case a)
LOAD Li      DEF Tj <- USE Li
               |
               |
               X <---> DEF Li
               |
             USE Tj

Implementation: Every LOAD Li marks the created Tj as coalesced with Li (as LOCALVAR(i)). STORE Li and IINC Li remove the LOCALVAR(i) coalescing of any Tj that are alive at the point of the STORE/IINC.

Eliminating STOREs

A STORE creates a copy edge from a temporary variable Tj to a local variable Li. The copy may be eliminated if Tj and Li do not interfere.

We assume that Tj is unmarked. There are two ways Tj and Li can interfere:

• b) Tj is live at the point of a DEF Li. c) Li is live at the point of the (single) DEF Tj.

b) is rather easy to check: The liferange of Tj is a single range within the basic block. Thus we only need to check if Tj is live at the latest DEF Li (the last STORE/IINC Li). If so, Tj and Li interfere.

Case c) is a little harder to check. The STORE Li we are trying to eliminate kills Li, so case c) can only arise if there is a USE Li somewhere after the single DEF Tj but before the STORE Li.

Li may be live along exception edges. Thus we must assume interference if there is an exception edge from an instruction during the lifetime of Tj.

case b)
              DEF Tj
               |
               X <----> DEF Li
               |
               |
STORE Li      USE Tj -> DEF Li

case c)
                           |
              DEF Tj <---> X
               |           |
               |          USE Li (LOAD Li or USE LOCALVAR(i))
             R |
               |
               |
STORE Li      USE Tj -> DEF Li

We know that there is no interference if all of the following conditions are true:

• Let R denote the section of the basic block between the DEF Tj and the STORE Li.
• CHECK1: The latest DEF Li before the STORE Li occurred before the DEF Tj (see case b).
• CHECK2: The latest potential-exception-throwing instruction before the STORE Li occurred before the DEF Tj (see case c).
• CHECK3: There is no DEF LOCALVAR(i) in R (see case c). Proof that CHECK3 completes the checks for case c:
  • We know that there is no control-flow edge entering or leaving the block within R (basic block properties and CHECK2). We further know that there is no DEF Li in R (CHECK1). Assuming there was a LOAD Li in R, there would be a DEF LOCALVAR(i) at this point, because there is no DEF Li in R (CHECK1) preventing the coalescing. Thus by CHECK3 there cannot be a LOAD Li in R. Assuming there was a USE LOCALVAR(i) in R, the corresponding DEF LOCALVAR(i) would have to precede the DEF Tj (CHECK3).

    Because liferanges of temporaries are properly nested (see IntermediateRepresentation), this implies that the USE LOCALVAR(i) occurs after the USE Tj, which contradicts our assumption. XXX live-through stackslots of DUPs are a problem here! What about live-through stackslots of replacement points?

Eliminating DUPs

DUP elimination is done in the register allocator of the baseline compiler. If there is a copy from one temporary variable Ti to another Tj, and neither variable is marked as STACKVAR, LOCALVAR, or ARGVAR, then Ti and Tj can be coalesced, eliminating the copy instruction.

Since temporary variables may only have one DEF (see IntermediateRepresentation), and the DEF Tj is the copy instruction, there is no possibility of interference. (If Ti is allocated to a register, Ti and Tj must have the same value in the SAVEDVAR flag. XXX elaborate this!)

If the allocator decides to coalesce Ti and Tj, Tj is marked as STCOPY, so when the liferange of (the variable formerly known as) Tj ends, the register allocator does not free the allocation of Tj, since Ti is still alive at this point.

before:

    DEF Ti
     |
     |
DUP  |----> DEF Tj
     |       |
     |       |
     |      USE Tj
     |
     |
    USE Ti

after:

    DEF Tij
     |
     |
     |
     |
     |
    USE Tij (STCOPY -- don't free!)
     |
     |
    USE Tij