Alternative code motion algorithm and tests for it.

[jankner]

Less efficient than it could be (rebuild is quadratic at the moment), and shares too many subexpressions, which I'm going to fix when I have time.

[pjonsson]

Cool! Is codeMotion2 supposed to be a drop-in replacement for the existing codeMotion in SimpleCodeMotion?

Can you add CodeMotion2 as one of the exposed modules in syntactic.cabal?

[pjonsson]

If codeMotion2 is supposed to be a drop-in replacement for codeMotion there's a couple of things that fail in Feldspar right now. This:

fut1 :: Future (Data IntN) -> Future (Data IntN)
fut1 x  = forLoop 20 x (\_ e -> future $ force $ await e)

gives:

*Main> printExpr fut1
*** Exception: rebuild: lost node

And this:

topLevelConsts :: Data Index -> Data Index -> Data Index
topLevelConsts a b = condition (a<5) (d ! (b+5)) (c ! (b+5))
  where
    c = value [1,2,3,4,5] :: Data [Index]
    d = value [2,3,4,5,6] :: Data [Index]

with the SICS target gives:

*Main> printExprWith defaultFeldOpts { targets = [SICS]} topLevelConsts 
*** Exception: optimizeFeat: can't get size of free variable: v1

The latter might be a bug in Feldspar-language though, but it's losing track of variables just like the first example.

[jankner]

Yup, it's supposed to be a drop-in replacement. I will have to take a look at what's going on with those errors. I would guess that in the first one has to do with the hoistOver functionality, since the NanoFeldspar doesn't test that, and I think future is one of the things that can't be hoisted out of.

Apparently a couple of files didn't make it into the first commit, so I've commited them now.

[emwap]

Note that the tests fail for GHC 7.4. Could you look into that.

[pjonsson]

I had a look at this but can't spend more time on it at the moment. Here's the notes so far--smaller test case:

add'' :: Data Bool -> Data Bool
add'' x = not x

combined with "const (const False)" for isHoistable in Feldspar-language is sufficient for triggering the bug with the lost node. "gm" at line 204 in CodeMotion2.hs has the same content regardless of whether isHoistable is true or false, so the bug appears to be in rebuild. Tweaking the heuristics can mask the bug as well. If everything is treated as a variable (or not a variable, I don't recall which one) the bug is masked.

@jankner: given the small test case and the 100% repeatability--can you take a quick look and see if it's something obvious that is wrong?

[jankner]

I assume you meant "gm" in codeMotion2. That means there's a bug in "gather". I looked and did find a bug. It didn't correctly record it when when a expression was a direct sub-expression of a non-hoistOver expression. This seems to have fixed the problem.

[jankner]

@pjonsson I guess I have to do this for you to get a notification.

[emilaxelsson]

Thanks for the patch Johan, and the rest of you for the review! Since it doesn't change any existing code, I'll merge it as it is. I will have a closer look when I can find the time.

[jankner]

The algorithm is still quadratic, and it introduces some unnecessary let-bindings. I would like to fix both those problems and make the implementation a bit nicer some time when I don't have exams to study for.

[pjonsson]

I seem to be subscribed to issues that I've commented on, so I got the notification.

I'm not too worried about the algorithmic complexity at this stage, most our programs are small and a working algorithm is worth a lot to us. With the latest fixes from Emil's repository I still get the same errors with dropped nodes on fut1/add''/topLevelConsts in Feldspar. The diff I'm using on Feldspar is this to Frontend.hs:

-    <=< codeMotion (simpleMatch (const . hoistOver)) prjDict (mkId opts)
+    <=< codeMotion2 (simpleMatch (const . (const False))) prjDict (mkId opts)

The reason for const . (const False) is because it provokes the bug on smaller test cases. One interesting observation is that the unoptimized expression in Feldspar is literally identical to the result we expect from the CSE (sorry about the name, I started manual shrinking from something that included an addition):

*Main> printExprUnOpt add''
(\var0 -> (not var0))
*Main> printExpr add''
*** Exception: rebuild: lost node