November 2000 - Glasgow-haskell-users

Fun with GHC's optimiser
by Manuel M. T. Chakravarty 02 Nov '00

02 Nov '00

Questions over questions arise in my quest to understand GHC's code generator. In this nice little piece of STG $w$snewPArray = NO_CCS[] \r[ww w] case newIntArray# [ww realWorld#] of wild { (#,#) s2# mba# -> case -# [ww 1] of y { DEFAULT -> let { wild1 = NO_CCS I#! [ww]; } in case ># [0 y] of wild2 { True -> PArray [wild1 mba#]; False -> let { $wgo2 = NO_CCS[] \r[y1 y2] let { a = NO_CCS PArray! [wild1 mba#]; } in case w of wild3 { I# e# -> case writeIntArray# [mba# y1 e# y2] of s2#1 { DEFAULT -> case ==# [y1 y] of wild11 { True -> (#,#) [s2#1 a]; False -> case +# [y1 1] of stg_c2aL { DEFAULT -> $wgo2 stg_c2aL s2#1 }; } }; }; } in case $wgo2 0 s2# of wild3 { (#,#) ds r -> r; }; } }; }; I am wondering whether there is a particular reason why the optimiser doesn't pull the (1) a = NO_CCS PArray! [wild1 mba#]; and the (2) case w of wild3 { I# e# -> out off the $wgo2 loop - or at least push (1) down into the True branch of `case ==# [y1 y] of'. I would say that (1) in this form pointlessly allocates heap like mad, but is only using one of the many copies of `a', namely the one allocated in the final iteration and returned to the caller. As for (2), the loop would be nice and straight if that unboxing where outside of the loop - as it is, we break the pipeline once per iteration it seems (if the branch prediction isn't very clever). Or do I misunderstand something here, or is there maybe some magic after STG that gets rid of the stuff? I attach the Haskell source, which I compiled with ghc -O -c PArrays.hs -fglasgow-exts -ddump-stg (This is 4.08.1 of course.) Also if somebody is looking at the attached source, I was wondering why, when I use the commented out code in `newPArray', I get a lot worse code (the STG code is in a comment at the end of the file). In particular, the lambda abstraction is not inlined, whereas `fill' gets inlined into the code of which the dump is above. Is it because the compiler has a lot harder time with explicit recursion than with fold/build? If so, the right RULES magic should allow me to do the same for my own recursively defined combinators, shouldn't it? Cheers, Manuel PS: Otherwise, it is quite impressive what the RULES and inliner do to the foldr that produced the above code.

1 0

Quick question re RULES
by Manuel M. T. Chakravarty 02 Nov '00

02 Nov '00

PrelBase contains the appended code. Am I correct in assuming that the stuff is structured as it is, because the "map" rule first `breaks' the map `open', which exposes it to the various foldr/build rules, and if no foldr/build rule matches, the "mapList" rule `closes' it again in a later phase of optimisation - after build was inlined? If so, it seems like the whole thing depends a bit on the timing of the various optimsations (the map might be closed again before any of the foldr/build rules fires). Is this maybe the reason that build has an INLINE 2 pragma, which delays its inlining, and thus, the closing of the map? All very cunning, it seems ;-) Cheers, Manuel -=- map :: (a -> b) -> [a] -> [b] map = mapList -- Note eta expanded mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst mapFB c f x ys = c (f x) ys mapList :: (a -> b) -> [a] -> [b] mapList _ [] = [] mapList f (x:xs) = f x : mapList f xs {-# RULES "map" forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs) "mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g) "mapList" forall f. foldr (mapFB (:) f) [] = mapList f #-}

1 0

RE: ppr for Haskell Abstract Syntax
by Simon Marlow 01 Nov '00

01 Nov '00

> Hi - > I was wondering if anyone knows if there is a pretty printer > for Haskell > Abstract Syntax anywhere? I've been asking around, but > haven't located > one yet. If you know of one that I could use, it would be > really helpful! > Thanks in advance, > *Kate We have one in GHC's CVS source tree now. hslibs/hssource contains a Haskell abstract syntax, parser, and a pretty printer. It should compile on pretty much any version of GHC, but you'll probably need a recent version of Happy (1.8) for the parser. Cheers, Simon

1 0

RE: ppr for Haskell Abstract Syntax
by Simon Peyton-Jones 01 Nov '00

01 Nov '00

GHC has a pretty printer for Haskell. It's in ghc/compiler/hsSyn/*.lhs, along with the (numerous) data type declarations that define the full Haskell syntax. It would take a little work to rip it out of GHC, mind you Simon | -----Original Message----- | From: Kate S. Golder [mailto:kgolder@wellesley.edu] | Sent: 31 October 2000 21:07 | To: glasgow-haskell-users(a)haskell.org | Subject: ppr for Haskell Abstract Syntax | | | Hi - | I was wondering if anyone knows if there is a pretty printer | for Haskell | Abstract Syntax anywhere? I've been asking around, but | haven't located | one yet. If you know of one that I could use, it would be | really helpful! | Thanks in advance, | *Kate | | ********************** | Kate S. Golder | Wellesley College | Class of 2002 | | Freeman Hall | Wellesley College | Wellesley, Ma 02481 | | | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users(a)haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users |

1 0