#683: RULES for recursive functions don't work properly
-----------------------+----------------------------------------------------
Reporter: simonpj | Owner: simonpj
Type: bug | Status: new
Priority: low | Milestone:
Component: Compiler | Version: 6.4.1
Severity: normal | Resolution:
Keywords: | Os: Unknown
Difficulty: Unknown | Architecture: Unknown
-----------------------+----------------------------------------------------
Comment (by simonpj):
Adding an email thread with Roman which is relevant
OK, so I can explain what is going on. I'm not sure the best way to fix
it.
* When two functions are mutually recursive, GHC nominates one as the
"loop breaker", and declines to inline it anywhere. That ensures that
inlining doesn't go on forever.
* The inlining of a loop breaker is not exposed in the interface file.
* GHC treats rewrite rules as "extra right-hand sides" for the function;
it's as if you had
{{{
f x = this -- The normal RHS for f
f (g y) = y -- A rule for f
}}}
So, suppose the RULE for f mentions g, and g mentions f. Then the two are
treated as mutually recursive.
* The RULEs for a loop-breaker are run (notwithstanding the loop-breaker-
ness). This is essential. A self-recursive function is a loop breaker,
but it may certainly have rules.
* However, currently the rules for a loop breaker are not "in scope" in
the bindings of the letrec that precede the binding of the variable. I
remember trying to fix this; can't remember why I failed.
* The other stupid thing is that 'bar' is marked as a loop breaker, and
hence not inlined, even though inlining it would be perfectly safe. And
that is what is happening here. 'bar' is chosen as the loop breaker, and
its inlining is not exposed.
I'm not sure how important this is to you. I'm not really sure how to fix
it. We can't simply ignore the dependencies from RULES (i.e. *not* treat
them as extra RHSs) because a RULE might be all that is preventing a
function being dead code.
Tricky one. I'm ccing Manuel in case he has bright ideas
cf http://hackage.haskell.org/trac/ghc/ticket/683
Simon
{{{
| -----Original Message-----
| From: Roman Leshchinskiy [mailto:[EMAIL PROTECTED]
| Sent: 03 October 2006 07:21
| To: Simon Peyton-Jones
| Subject: Rules and inline pragmas
|
| Hi Simon,
|
| a somewhat weird case:
|
| ------
| module Foo where
|
| bar :: [a] -> [a]
| {-# INLINE [0] bar #-}
| bar xs = xs
|
| foo1 :: [a] -> [a]
| {-# INLINE [0] foo1 #-}
| foo1 xs = xs
|
| foo2 :: [a] -> [a]
| {-# INLINE [0] foo2 #-}
| foo2 xs = xs
|
| {-# RULES
|
| "foo2->bar/foo1" [~1] forall xs.
| foo2 xs = bar (foo1 xs)
| "bar/foo1" [1] forall xs.
| bar (foo1 xs) = foo2 xs
| #-}
| ------
|
| Here, the interface file doesn't have bar's inline pragma and its
| unfolding:
|
| 13 bar :: [a] -> [a] {- Arity: 1 HasNoCafRefs Strictness: S -}
|
| But if I change the "bar/foo1" rule to
|
| bar (foo1 xs) = foo1 xs
|
| then everything works as expected:
|
| 14 bar :: [a] -> [a]
| {- Arity: 1 HasNoCafRefs Strictness: S Inline: [0]
| Unfolding: (__inline_me (\ @ a xs :: [a] -> xs)) -}
}}}
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/683>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
