Opened 8 years ago

Closed 6 years ago

Last modified 6 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: Difficulty: Unknown
Test Case: Blocked By:
Blocking: Related Tickets:

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
		 where
		   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 8 years ago by simonpj

  • Description modified (diff)

Fix formmatting only

comment:2 Changed 8 years ago by simonmar

See also #707

comment:3 Changed 8 years ago by simonpj

  • Milestone 6.6 deleted
  • Priority changed from normal to low

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.

Simon

comment:4 Changed 8 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
+[_^I_][_^I_][_^I_][_$_]
+
+type RulesOnly = Bool	-- See Note [RulesOnly]

comment:5 Changed 8 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

cf http://hackage.haskell.org/trac/ghc/ticket/683

Simon

| -----Original Message-----
| From: Roman Leshchinskiy [mailto:rl@cse.unsw.edu.au]
| 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 8 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.

Simon

comment:7 Changed 7 years ago by igloo

  • Milestone set to 6.8

comment:8 Changed 6 years ago by igloo

  • Milestone changed from 6.8 branch to _|_

comment:9 Changed 6 years ago by simonpj

  • Resolution set to fixed
  • Status changed from new to closed

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.

Simon

comment:10 Changed 6 years ago by simonmar

  • Architecture changed from Unknown to Unknown/Multiple

comment:11 Changed 6 years ago by simonmar

  • Operating System changed from Unknown to Unknown/Multiple
Note: See TracTickets for help on using tickets.