Opened 12 years ago

Closed 10 years ago

Last modified 9 years ago

#683 closed bug (fixed)

RULES for recursive functions don't work properly

Reported by: simonpj Owned by: simonpj
Priority: low Milestone:
Component: Compiler Version: 6.4.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by simonpj)

someone mentioned to me that this expression:

mapM_ action [n..m]

isn't being optimised properly, so I thought I'd look into it. Sure enough, we don't get down to a simple loop like we should, although the F/B transformation is happening (see ~simonmar/scratch/mapm.hs). The problem is that GHC.Enum.eftIntFB isn't being inlined, it's defined like this:

{-# INLINE [0] eftIntFB #-}
eftIntFB :: (Int -> r -> r) -> r -> Int# -> Int# -> r
eftIntFB c n x y | x ># y    = n	
		 | otherwise = go x
		   go x = I# x `c` if x ==# y then n else go (x +# 1#)

but, strangely, the inlining doesn't appear in the interface:

eftIntFB :: (GHC.Base.Int -> r -> r) -> r -> GHC.Prim.Int# -> GHC.Prim.Int# -> r
  {- Arity: 4 HasNoCafRefs Strictness: LLLL -}

This is becuase the RULE make eftIntFB look recursive, so its inlining isnt' exposed. Bad, bad.

Change History (11)

comment:1 Changed 12 years ago by simonpj

Description: modified (diff)

Fix formmatting only

comment:2 Changed 12 years ago by simonmar

See also #707

comment:3 Changed 11 years ago by simonpj

Milestone: 6.6
Priority: normallow

Currently the example seems to work fine. I'm still not 100% sure that the recursive-rules thing is as wonderful as it might be, but at least it's no longer a pressing issue.

So I'm downgrading this to low-priority, and taking it off the 6.6 milestone.


comment:4 Changed 11 years ago by simonpj

Before I forget, here's the beginning of a modification to address the original problem. It's not implemented, but I thought I'd leave the notes here in case it pops up as an issue again.

hunk ./compiler/basicTypes/BasicTypes.lhs 329
+Note [RulesOnly]
+The RulesOnly boolean is True if the only reason the Id is a
+loop-breaker only because of recursion through a RULE. In that case,
+we can ignore the loop-breaker-ness for inlining purposes.  Example
+(from GHC.Enum):
+  eftInt :: Int# -> Int# -> [Int]
+  eftInt x y = ...(non-recursive)...
+  {-# INLINE [0] eftIntFB #-}
+  eftIntFB :: (Int -> r -> r) -> r -> Int# -> Int# -> r
+  eftIntFB c n x y = ...(non-recursive)...
+  {-# RULES
+  "eftInt"  [~1] forall x y. eftInt x y = build (\ c n -> eftIntFB c n x y)
+  "eftIntList"  [1] eftIntFB  (:) [] = eftInt
+   #-}
+The two look mutually recursive only because of their RULES;
+we don't want that to inhibit inlining!
hunk ./compiler/basicTypes/BasicTypes.lhs 364
-			-- in a group of recursive definitions
+	!RulesOnly	--   in a group of recursive definitions
+type RulesOnly = Bool	-- See Note [RulesOnly]

comment:5 Changed 11 years ago 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



| -----Original Message-----
| From: Roman Leshchinskiy []
| 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)) -}

comment:6 Changed 11 years ago by simonpj

I commited a patch "Make recursion and RULES interact better" (3 Oct) that fixes this problem. Not very thoroughly tested, so I'm leaving the bug oopen for now.


comment:7 Changed 11 years ago by igloo

Milestone: 6.8

comment:8 Changed 10 years ago by igloo

Milestone: 6.8 branch_|_

comment:9 Changed 10 years ago by simonpj

Resolution: fixed
Status: newclosed

The HEAD contains a much better treatment of recursion involving rewrite rules; see Note [Loop breaking and RULES] in OccAnal.

I just checked that mapM_ action [n..m] fuses nicely (it does), and Roman's example above has the inlining for bar.

So this one seems to be done. As is often the case with performance bugs, we don't have a good way to add a regression test. So I'm just closing it.


comment:10 Changed 9 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:11 Changed 9 years ago by simonmar

Operating System: UnknownUnknown/Multiple
Note: See TracTickets for help on using tickets.