Grant Report - MoarVM JIT Compiler Expression Backend - February 2019

1 Comment

Brrt (Bart Wiegmans) reports that February was busy and short, but that he did some research on other implementations of register allocation that he can apply to MoarVM JIT.

He notes the following conundrum that he has been thinking about. Maybe a reader can advise:

I've also encountered a limitation in the optimization of the IR, which I'm trying to resolve. The issue is this, if I have a bunch of code like:

  int x = 3, y;
  if (table[x] > 0) {
      y = x * 3;
  } else {
     y = x * 6;
  }

Then under the current IR and compiler, with the new optimizer we may be able to make the reference to x in table[x]. Because the assignment to x isn't strictly ordered, this means that it is moved (implicitly) to the next use, which is:

  int x, y;
  if (table[x] > 0) {
      x = 3;
      y  = x * 3;
  } else {
      y = x * 6;
  }

And that obviously doesn't work, since x is uninitialized in the else branch. So in order to do effective optimizations, we need to be able to resolve this case correctly, either by copying the definition of 'x', or by moving the definition to an earlier point in the program.

MAJ

1 Comment

A) Insider jargon makes this a bit opaque. “optimization of the IR” where “IR” is what? Plz spell out first time referenced.

B) “we may be able to make the reference to x in table[x]” - meaning uncertain here. Do you mean ‘re-use the reference to x we develop in expression ‘table[x]’?

C) In any case, how far ahead is this optimizer looking? In the given example

int x = 3, y;
if (table[x] > 0) {
y = x * 3;
} else {
y = x * 6;
}

C1) Neither variable x or y bring external information at entry in to this code section.

C2) The variable ‘x’ is never used as a Left Hand Side (LHS) in other than the initial assignment.

C3) There is no indication that x is subject to async value changes.

Thus I suggest the optimization here is simple constant propagation (https://en.wikipedia.org/wiki/Constant_folding) giving the following re-write avoiding a register allocation for variable x within conditional code entirely:

int y;
if( table[ 3 ] > 0 ) {
# known at compile time
y = 3 * 3 ; # further re-write as y = 9 ;
} else {
# known at compile time
y = 3 * 6; # further re-write as y = 18 ;
}
int x ;
x = 3 ; # Only needed if value of x assigned here is used downstream as an Right Hand Side (RHS)

OTOH, if the code example is:

int x = some_earlier_or_outer_scope_type_cast_compatible_variable_FOO, y;
if (table[x] > 0) {
y = x * 3;
} else {
y = x * 6;
}

Then x is no longer a locally known constant at compile time so constant propagation is out. The next question then is the initialization of x a typecast on FOO? If FOO is defined as int FOO, then no, so since variable x is never locally used as a RHS then variable x is locally pointless and there may be advantage in re-writing as:

int y;
if (table[ FOO ] > 0) {
y = FOO * 3;
} else {
y = FOO * 6;
}
int x ;
# Only needed if value of x assigned here is used downstream as an Right Hand Side (RHS)
x = some_earlier_or_outer_scope_type_cast_compatible_variable_FOO;

If the assignment x = FOO IS as typecast, then for safety variable x or some object in that role must have allocated storage (register or otherwise) and be initialized per the “int x = FOO” assignment prior to entry in to the “table[ x ]” expression. Inverting this logic, from an optimization POV, entry in to the expression “table[ x ]” should be recognized as an optimizer barrier on object “x”, meaning regardless of how variable x is used after expression “table[ x ]”, variable x must be fully realized as a variable RHS value in some way prior to expression “table[ x ]”.

Leave a comment

About TPF

The Perl Foundation - supporting the Perl community since 2000. Find out more at www.perlfoundation.org.

About this Entry

This page contains a single entry by Mark A Jensen published on March 9, 2019 3:49 PM.

Rakudo Perl 6 performance analysis tooling - Grant Report #8 was the previous entry in this blog.

Grant Extension Request: Maintaining the Perl 5 Core (Tony Cook) is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.

Pages

OpenID accepted here Learn more about OpenID
Powered by Movable Type 6.2.2