core expression with (hopefully) improved usage information.
\begin{code}
+{-# OPTIONS -w #-}
+-- The above warning supression flag is a temporary kludge.
+-- While working on this module you are encouraged to remove it and fix
+-- any warnings in the module. See
+-- http://hackage.haskell.org/trac/ghc/wiki/CodingStyle#Warnings
+-- for details
+
module OccurAnal (
occurAnalysePgm, occurAnalyseExpr
) where
import PrelNames ( buildIdKey, foldrIdKey, runSTRepIdKey, augmentIdKey )
import Unique ( Unique )
import UniqFM ( keysUFM, intersectsUFM )
-import Util ( mapAndUnzip, mapAccumL )
+import Util ( mapAndUnzip )
import Outputable
+
+import Data.List
\end{code}
\begin{code}
occAnalBind env (Rec pairs) body_usage
- = foldr (_scc_ "occAnalBind.dofinal" do_final_bind) (body_usage, []) sccs
+ = foldr ({-# SCC "occAnalBind.dofinal" #-} do_final_bind) (body_usage, []) sccs
where
analysed_pairs :: [Details]
analysed_pairs = [ (bndr, rhs_usage, rhs')
]
sccs :: [SCC (Node Details)]
- sccs = _scc_ "occAnalBind.scc" stronglyConnCompR edges
+ sccs = {-# SCC "occAnalBind.scc" #-} stronglyConnCompR edges
---- stuff for dependency analysis of binds -------------------------------
edges :: [Node Details]
- edges = _scc_ "occAnalBind.assoc"
+ edges = {-# SCC "occAnalBind.assoc" #-}
[ (details, idUnique id, edges_from id rhs_usage)
| details@(id, rhs_usage, rhs) <- analysed_pairs
]
-- which has n**2 cost, and this meant that edges_from alone
-- consumed 10% of total runtime!
edges_from :: Id -> UsageDetails -> [Unique]
- edges_from bndr rhs_usage = _scc_ "occAnalBind.edges_from"
+ edges_from bndr rhs_usage = {-# SCC "occAnalBind.edges_from" #-}
keysUFM (addRuleUsage rhs_usage bndr)
---- Stuff to "re-constitute" bindings from dependency-analysis info ------
-- where df is the exported dictionary. Then df makes a really
-- bad choice for loop breaker
- | is_con_app rhs = 3 -- Data types help with cases
- -- This used to have a lower score than inlineCandidate, but
- -- it's *really* helpful if dictionaries get inlined fast,
- -- so I'm experimenting with giving higher priority to data-typed things
+ | idHasRules bndr = 3
+ -- Avoid things with specialisations; we'd like
+ -- to take advantage of them in the subsequent bindings
+ -- Also vital to avoid risk of divergence:
+ -- Note [Recursive rules]
| inlineCandidate bndr rhs = 2 -- Likely to be inlined
+ -- Note [Inline candidates]
- | idHasRules bndr = 1
- -- Avoid things with specialisations; we'd like
- -- to take advantage of them in the subsequent bindings
+ | is_con_app rhs = 1 -- Data types help with cases
| otherwise = 0
-- But we won't because constructor args are marked "Many".
-- Cheap and cheerful; the simplifer moves casts out of the way
+ -- The lambda case is important to spot x = /\a. C (f a)
+ -- which comes up when C is a dictionary constructor and
+ -- f is a default method.
+ -- Example: the instance for Show (ST s a) in GHC.ST
+ --
+ -- However we *also* treat (\x. C p q) as a con-app-like thing,
+ -- Note [Closure conversion]
is_con_app (Var v) = isDataConWorkId v
is_con_app (App f _) = is_con_app f
+ is_con_app (Lam b e) = is_con_app e
is_con_app (Note _ e) = is_con_app e
is_con_app other = False
rules_only = bndrs `intersectsUFM` rhs_usg
\end{code}
+Note [Inline candidates]
+~~~~~~~~~~~~~~~~~~~~~~~~
+At one point I gave is_con_app a higher score than inline-candidate,
+on the grounds that "it's *really* helpful if dictionaries get inlined fast".
+However a nofib run revealed no change if they were swapped so that
+inline-candidate has the higher score. And it's important that it does,
+else you can get a bad worker-wrapper split thus:
+ rec {
+ $wfoo x = ....foo x....
+
+ {-loop brk-} foo x = ...$wfoo x...
+ }
+But we *want* the wrapper to be inlined! If it isn't, the interface
+file sees the unfolding for $wfoo, and sees that foo is strict (and
+hence it gets an auto-generated wrapper. Result: an infinite inlining
+in the importing scope. So be a bit careful if you change this. A
+good example is Tree.repTree in nofib/spectral/minimax. If is_con_app
+has the higher score, then compiling Game.hs goes into an infinite loop.
+
+Note [Recursive rules]
+~~~~~~~~~~~~~~~~~~~~~~
+Consider this group, which is typical of what SpecConstr builds:
+
+ fs a = ....f (C a)....
+ f x = ....f (C a)....
+ {-# RULE f (C a) = fs a #-}
+
+So 'f' and 'fs' are mutually recursive. If we choose 'fs' as the loop breaker,
+all is well; the RULE is applied, and 'fs' becomes self-recursive.
+
+But if we choose 'f' as the loop breaker, we may get an infinite loop:
+ - the RULE is applied in f's RHS (see Note [Self-recursive rules] in Simplify
+ - fs is inlined (say it's small)
+ - now there's another opportunity to apply the RULE
+
+So it's very important to choose the RULE-variable as the loop breaker.
+This showed up when compiling Control.Concurrent.Chan.getChanContents.
+
+Note [Closure conversion]
+~~~~~~~~~~~~~~~~~~~~~~~~~
+We treat (\x. C p q) as a high-score candidate in the letrec scoring algorithm.
+The immediate motivation came from the result of a closure-conversion transformation
+which generated code like this:
+
+ data Clo a b = forall c. Clo (c -> a -> b) c
+
+ ($:) :: Clo a b -> a -> b
+ Clo f env $: x = f env x
+
+ rec { plus = Clo plus1 ()
+
+ ; plus1 _ n = Clo plus2 n
+
+ ; plus2 Zero n = n
+ ; plus2 (Succ m) n = Succ (plus $: m $: n) }
+
+If we inline 'plus' and 'plus1', everything unravels nicely. But if
+we choose 'plus1' as the loop breaker (which is entirely possible
+otherwise), the loop does not unravel nicely.
+
+
@occAnalRhs@ deals with the question of bindings where the Id is marked
by an INLINE pragma. For these we record that anything which occurs
in its RHS occurs many times. This pessimistically assumes that ths
projects / ghc-hetmet.git / blobdiff