[<<][rtl][>>][..]
Thu May 16 10:24:42 EDT 2019

Escape analysis

Now for the core issue: construct a list of variables that is only
defined inside a loop.

Note that we actually have that information in the original form: we
know the return values of the form.  So it is likely safe to assume
the intermediate form will have an explicit list of arrays that will
be visible outside of its scope.

There's a problem: when two loops are fused, the outputs might no
longer escape.  So it seem that analysis needs to be performed anyway.


What does it mean for a variable to not escape?  If it is no longer
referenced after the loop has finished.

So given a loop segment, we need to isolate the segments that come
after it.

This needs to be done for each binding.

It's not entirely clear how to mix primitives and loops inside a forms
list.  So let's just start building this and see where it ends.

I'm starting to run out of steam.  This stuff is exhausting.

Ok, resume.  I do not know what to do with irregular nesting, but I do
know that the end of a loop is a splitting point.

EDIT: I'm missing an insight, an angle.  I need to let this pop up by
itself.


EDIT: Ok I tried several times.  It's not working.  I can't retain
enough context.


EDIT: Took a much longer break.  Let's create a simpler zipper.
Follow the Haskell tutorial first to refresh intuition.

So, really, it is just a stack.  I just need a stack, because only the
future matters.  It's not that I haven't done that before!


Here's just the iteration pattern, doing nothing but linearly
traversing and keeping a context.

data Ctx b = Ctx { ctxStack :: [[Form b]],
                   ctxCode  :: [Form b] }

zip_next (Ctx (fs:fss) []) = zip_next (Ctx fss fs)  -- pop context
zip_next (Ctx [] []) = () -- end
zip_next (Ctx fss ((LetPrim b):fs)) = zip_next (Ctx fss fs) -- skip
zip_next (Ctx fss ((LetLoop i fs'):fs)) = zip_next (Ctx (fs:fss) fs') -- push


Note that this does just the other part of the index generation.  So
what about changing that code to do full zipper/future annotation?

I think I understand: perform a traversal in a state monad, and
annotate each node with the zipper.

This can probably be generalized to do all kinds of things.

Ok, so generalize annotate to monadic form and remove all explicit
passing:

annotate' :: Monad m => Program b -> m (Program ((), b))
annotate' (Program fs) = fmap Program $ forms fs where
  forms fs = traverse form fs
  form (LetPrim b)    = return $ LetPrim ((), b)
  form (LetLoop i fs) = fmap (LetLoop i) $ forms fs

Now m can be made to be the state monad.

EDIT: I have it split up, but this really feels like doing double
work.  It actually is, because there is an actual recrursion and the
updating of a datatype that represents the recursion.



[Reply][About]
[<<][rtl][>>][..]