# 2020-08-04

## More sexp-grammar

I managed to continue writing up instances of `SexpIso`

. The results are here,
but I think I'll let it rest for a bit now. I should really focus on getting my
interference graph working.

## Interference

Let's get back into this a little bit.

First off, let's try to remember, and document, what `analyseStm`

is supposed to
do. The first thing to remember, is that we're only keeping track of memory
blocks. We only ever interact with them when they are *created* or *last used*,
though they can be last used in multiple places (like two branches of an
`if`

-expression. This means that we can simplify our algorithm quite a bit. We
only ever need to consider bodies of code where there are statements in, since
statements are the only places where a memory block can be introduced (through
the pattern) or last used (through the `LastUseMap`

). For instance, when
analysing an `if`

-expression, we don't care about the conditional (since it's
just a `SubExp`

or the decorations, but only about the two branches.

Now, the result of the big case on the statement expression inside `analyseStm`

is supposed to return three things: `inuse`

is the set of memory blocks that are
inuse at the end of any code bodies inside the expression. `lus`

is the set of
all memory blocks that have reached their last use in any code bodies inside the
expression. `graph`

is the interference graph computed for any code – bodies
inside the expression. Note that we only really care about nested
statements. Everything else is handled by `new_mems`

and `last_use_mems`

inside
`analyseStm`

.

Okay, so I've actually finished my interference algorithm for now. The next step
is to do some graph colouring, and actually integrate it with the
`ReuseAllocations`

pass.

## Back to sexp-grammar

We have a problem: `Assert`

relies on `SrcLoc`

, which doesn't implement
`Generic`

, and doesn't have an obvious isomorphism. What do? It does implement
`Monoid`

, so if we could just pass it `mempty`

, maybe that would work?

Yes, it seems to work with the following isomorphism for the Apply case:

1: With (. Sexp.list (Sexp.el (Sexp.sym "assert") >>> 2: Sexp.el sexpIso >>> 3: Sexp.el sexpIso >>> 4: Sexp.el (iso (\_ -> mempty) (T.pack . show) . sexpIso)))

where the last line takes care of the isomorphism for `SrcLoc`

.

Next problem: Stms.

Oh, that turned out to be easy as well:

1: instance Decorations lore => SexpIso (Stms lore) where 2: sexpIso = iso stmsFromList stmsToList . sexpIso

Some nasty stuff is happening as soon as we touch `ExpT`

. Because of the type
system magic in `Op`

, we need to make `Decorations lore`

require `SexpIso`

for
the type families inside. It seems to work though.

Here's the progress so far:

https://github.com/diku-dk/futhark/commit/454000219f3cd2c296e968f8076a68f8ad7ecc12