TCMC optimization doesn't apply when recursive data structures have an unexpected field order

[neon64]

I found an annoying limitation of current analysis, when we start defining recursive data structures the "unexpected way".

For example: suppose we define our list type in the reverse order, i.e.: the element comes after the tail of the list.

type revlist(T) { pub empty | some(tail: revlist(T), elem: T) }

Then the following append proc isn't eligible for TCMC optimization under the current implementation.

append > (2 calls)
0: reverse_append.append<0>
append(front##0:reverse_append.revlist(wybe.int), back##0:reverse_append.revlist(wybe.int), ?result##0:reverse_append.revlist(wybe.int))<{}; {}>:
  AliasPairs: [(back##0,result##0)]
  InterestingCallProperties: []
    foreign llvm icmp_ne(front##0:wybe.int, 0:wybe.int, ?tmp#3##0:wybe.bool)
    case ~tmp#3##0:wybe.bool of
    0:
        foreign llvm move(~back##0:reverse_append.revlist(wybe.int), ?result##0:reverse_append.revlist(wybe.int)) @reverse_append:8:14

    1:
        foreign lpvm access(front##0:reverse_append.revlist(T), 0:wybe.int, 16:wybe.int, 0:wybe.int, ?t##0:reverse_append.revlist(wybe.int)) @reverse_append:1:31
        foreign lpvm access(~front##0:reverse_append.revlist(T), 8:wybe.int, 16:wybe.int, 0:wybe.int, ?h##0:wybe.int) @reverse_append:1:31
        reverse_append.append<0>(~t##0:reverse_append.revlist(wybe.int), ~back##0:reverse_append.revlist(wybe.int), ?tail##0:reverse_append.revlist(wybe.int)) #1 @rever
se_append:5:13
        foreign lpvm alloc(16:wybe.int, ?tmp#6##0:reverse_append.revlist(T)) @reverse_append:1:31
        foreign lpvm mutate(~tmp#6##0:reverse_append.revlist(T), ?tmp#7##0:reverse_append.revlist(T), 0:wybe.int, 1:wybe.int, 16:wybe.int, 0:wybe.int, ~tail##0:reverse_
append.revlist(T)) @reverse_append:1:31
        foreign lpvm mutate(~tmp#7##0:reverse_append.revlist(T), ?result##0:reverse_append.revlist(T), 8:wybe.int, 1:wybe.int, 16:wybe.int, 0:wybe.int, ~h##0:T) @reverse_append:1:31

Here's why:

• we try to move the recursive call to reverse_append.append<0> down as far as possible, until we reach a prim which uses one of the outputs from the recursive call
• this means we move it below the alloc(), but not below the first of two mutate()s, since the first mutate uses the tail from the recursive call (rather than setting the head h)
• this means that the second mutate is left at the bottom of the proc, which renders the leaf ineligible for the next phase of the optimization
• if the list type were defined "normally", then mutate(..., ..., ..., h) would be the first mutate (since fields are initialized in order of declaration), and the recursive call would be moved below it without a problem.

Fortunately this isn't so bad in practice, since all the major data structures (lists, trees, etc...) tend to have the convention that the "value" is the first field. However in principle this is an arbitrary limitation to the optimization.

Ideally we want to realise that since the two mutates are writing to non-overlapping fields, it doesn't matter which order we do them. From analyzing the assignments/uses of variables, this is not obvious, since mutate effectively consumes a value and then emits a new one, there is an explicit ordering of variables. i.e.: mutate(tmp#6, ?tmp#7,...) must come before mutate(~tmp#7, ?result,...) since tmp#7 was created by the first mutate. However it should be possible to keep the first two args of the mutates the same, and just swap around which values are being written to which field

# recursive call can't be moved below this mutate()
foreign lpvm mutate(~tmp#6##0:reverse_append.revlist(T), ?tmp#7##0:reverse_append.revlist(T), 0:wybe.int, 1:wybe.int, 16:wybe.int, 0:wybe.int, ~tail##0:reverse_
append.revlist(T))
foreign lpvm mutate(~tmp#7##0:reverse_append.revlist(T), ?result##0:reverse_append.revlist(T), 8:wybe.int, 1:wybe.int, 16:wybe.int, 0:wybe.int, ~h##0:T)

becomes

foreign lpvm mutate(~tmp#6##0:reverse_append.revlist(T), ?tmp#7##0:reverse_append.revlist(T), 8:wybe.int, 1:wybe.int, 16:wybe.int, 0:wybe.int, ~h##0:T)
# recursive call can be safely moved down to HERE
# reverse_append.append<0>
foreign lpvm mutate(~tmp#7##0:reverse_append.revlist(T), ?result##0:reverse_append.revlist(T), 0:wybe.int, 1:wybe.int, 16:wybe.int, 0:wybe.int, ~tail##0:reverse_
append.revlist(T))

The concept of "mutate chains" (which is used internally in the implementation) already captures this idea, we just need to make tryMovePrimAfterPrims smart enough to realise that mutates within a single "chain" can be reordered.

[pschachte]

This is also an issue for compile time garbage collection.

Mutate instructions contain the size of the structure, and offset, and the size of the field being overwritten, so it is quite possible to see that the mutations do not overlap.