TM025 Array Optimization

Motivation

Our current method to ANF raw array is very inefficient: we have an ANF variable for each element in the array. Then, at the final step, we put every ANF'ed elements together in an array. This results in unnecessary storing/loading these values to/from Pyret's stack frame and a very bloated generated code. The optimization solves these problems.

An example of the current generated code (pseudocode):

if (isActivationRecord) {
    anf_array_val$1 = ...
    anf_array_val$2 = ...
    ...
    anf_array_val$1000 = ...
    ...
}

try {

switch($step) {
case 0:
    anf_array_val$1 = ... // for simplicity, intermediate steps between each case are ignored
case 1:
    anf_array_val$2 = ...
case ...:
    ...
case 999:
    anf_array_val$1000 = ...
case 1000:
    anf_array = [anf_array_val$1, anf_array_val$2, ..., anf_array_val$1000]
...
}

} catch {
    frame = makeActivationRecord([anf_array_val$1, anf_array_val$2, ..., anf_array_val$1000, ...])
    ...
}

Proposal

The proposed optimization is to create an array to hold ANF'ed elements in the first step. Then, we can continuously put each ANF'ed element to the array.

An example of the proposed generated code (pseudocode):

if (isActivationRecord) {
    anf_array = ...
    ...
}

try {

switch($step) {
case 0:
    anf_array = new Array(1000)
case 1:
    anf_array[0] = ...
case 2:
    anf_array[1] = ...
case ...
    ...
case 1000:
    anf_array[999] = ...
...
}

} catch {
    frame = makeActivationRecord([anf_array, ...])
    ...
}

Concretely, we introduce a new ANF expression called a-arr-let which acts like a-let but uses an array cell instead of a normal variable. And when ANF'ing a raw array, we use this new a-arr-let instead.

Soundness

The optimization is sound:

1. It eventually gives the desired array. That is

   anf_array_val$1 = ...
   anf_array_val$2 = ...
   ...
   anf_array_val$1000 = ...
   anf_array = [anf_array_val$1, anf_array_val$2, ..., anf_array_val$1000]
   

   produces the same value as

   anf_array = new Array(1000)
   anf_array[0] = ...
   anf_array[1] = ...
   ...
   anf_array[999] = ...
   

   Other part of the code cannot alter the array while it's building up due to the Pyret's scope. That is, anf_array is not in the LHS of any other expressions except when it gets loaded from Pyret's stack frame.

2. It's impossible to access the array while it's supposed to be inaccessible

   Other part of the code cannot interact with the array while it's building up due to the Pyret's scope. That is, anf_array is not in the RHS of any expressions except when it gets stored to $ans and when it gets stored to Pyret's stack frame.

Result

Currently, the following code:

fun f(x): x end
[list: f(1), f(2), ..., f(3000)]

take 5 minutes to compile and then crash afterwards. The proposal should solve the problem and drastically boost the running time.