2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4 \section[CoreRules]{Transformation rules}
8 RuleBase, prepareRuleBase, lookupRule,
10 ProtoCoreRule(..), pprProtoCoreRule,
14 #include "HsVersions.h"
16 import CoreSyn -- All of it
17 import OccurAnal ( occurAnalyseExpr, tagBinders, UsageDetails )
18 import BinderInfo ( markMany )
19 import CoreFVs ( exprFreeVars, idRuleVars, ruleSomeLhsFreeVars )
20 import CoreUnfold ( Unfolding(..) )
21 import CoreUtils ( whnfOrBottom, eqExpr )
22 import PprCore ( pprCoreRule )
23 import Subst ( Subst, InScopeSet, substBndr, lookupSubst, extendSubst,
24 mkSubst, substEnv, setSubstEnv,
25 unBindSubst, bindSubstList, unBindSubstList,
27 import Id ( Id, getIdUnfolding,
28 getIdSpecialisation, setIdSpecialisation,
29 setIdNoDiscard, maybeModifyIdInfo, modifyIdInfo
31 import IdInfo ( zapLamIdInfo, setSpecInfo, specInfo )
32 import Name ( Name, isLocallyDefined )
33 import Var ( isTyVar, isId )
36 import Type ( mkTyVarTy, getTyVar_maybe )
37 import qualified Unify ( match )
38 import CmdLineOpts ( opt_D_dump_simpl, opt_D_verbose_core2core )
41 import ErrUtils ( dumpIfSet )
43 import Maybes ( maybeToBool )
44 import List ( partition )
45 import Util ( sortLt )
49 %************************************************************************
51 \subsection[specialisation-IdInfo]{Specialisation info about an @Id@}
53 %************************************************************************
55 A @CoreRule@ holds details of one rule for an @Id@, which
56 includes its specialisations.
58 For example, if a rule for @f@ contains the mapping:
60 forall a b d. [Type (List a), Type b, Var d] ===> f' a b
62 then when we find an application of f to matching types, we simply replace
63 it by the matching RHS:
65 f (List Int) Bool dict ===> f' Int Bool
67 All the stuff about how many dictionaries to discard, and what types
68 to apply the specialised function to, are handled by the fact that the
69 Rule contains a template for the result of the specialisation.
71 There is one more exciting case, which is dealt with in exactly the same
72 way. If the specialised value is unboxed then it is lifted at its
73 definition site and unlifted at its uses. For example:
75 pi :: forall a. Num a => a
77 might have a specialisation
79 [Int#] ===> (case pi' of Lift pi# -> pi#)
81 where pi' :: Lift Int# is the specialised version of pi.
84 %************************************************************************
88 %************************************************************************
91 matchRules :: InScopeSet -> [CoreRule] -> [CoreExpr] -> Maybe (FAST_STRING, CoreExpr, [CoreExpr])
92 -- See comments on matchRule
93 matchRules in_scope [] args = Nothing
94 matchRules in_scope (rule:rules) args
95 = case matchRule in_scope rule args of
96 Just result -> Just result
97 Nothing -> matchRules in_scope rules args
100 matchRule :: InScopeSet -> CoreRule -> [CoreExpr] -> Maybe (FAST_STRING, CoreExpr, [CoreExpr])
102 -- If (matchRule rule args) returns Just (name,rhs,args')
103 -- then (f args) matches the rule, and the corresponding
104 -- rewritten RHS is (rhs args').
106 -- The bndrs and rhs is occurrence-analysed
111 -- forall f g x. map f (map g x) ==> map (f . g) x
113 -- CoreRule "map/map"
114 -- [f,g,x] -- tpl_vars
115 -- [f,map g x] -- tpl_args
116 -- map (f.g) x) -- rhs
118 -- Then the call: matchRule the_rule [e1,map e2 e3]
119 -- = Just ("map/map", \f,g,x -> rhs, [e1,e2,e3])
121 -- Any 'surplus' arguments in the input are simply put on the end
125 -- No variable free in the template is bound in the target
127 matchRule in_scope (Rule rn tpl_vars tpl_args rhs) args
128 = go tpl_args args (mkSubst in_scope emptySubstEnv)
130 tpl_var_set = mkVarSet tpl_vars
132 -----------------------
134 go (tpl_arg:tpl_args) (arg:args) subst = match tpl_arg arg tpl_var_set (go tpl_args args) subst
136 -- Two easy ways to terminate
137 go [] [] subst = Just (rn, mkLams tpl_vars rhs, mk_result_args subst tpl_vars)
138 go [] args subst = Just (rn, mkLams tpl_vars rhs, mk_result_args subst tpl_vars ++ args)
140 -- One tiresome way to terminate: check for excess unmatched
141 -- template arguments
143 = case eta_complete tpl_args (mkVarSet leftovers) of
144 Just leftovers' -> Just (rn, mkLams done (mkLams leftovers' rhs),
145 mk_result_args subst done)
146 Nothing -> Nothing -- Failure
148 (done, leftovers) = partition (\v -> maybeToBool (lookupSubstEnv subst_env v))
149 (map zapOccInfo tpl_vars)
151 subst_env = substEnv subst
153 -----------------------
154 eta_complete [] vars = ASSERT( isEmptyVarSet vars )
156 eta_complete (Type ty:tpl_args) vars
157 = case getTyVar_maybe ty of
158 Just tv | tv `elemVarSet` vars
159 -> case eta_complete tpl_args (vars `delVarSet` tv) of
160 Just vars' -> Just (tv:vars')
164 eta_complete (Var v:tpl_args) vars
165 | v `elemVarSet` vars
166 = case eta_complete tpl_args (vars `delVarSet` v) of
167 Just vars' -> Just (v:vars')
170 eta_complete other vars = Nothing
172 -----------------------
173 mk_result_args subst vs = map go vs
175 senv = substEnv subst
176 go v = case lookupSubstEnv senv v of
177 Just (DoneEx ex) -> ex
178 Just (DoneTy ty) -> Type ty
179 -- Substitution should bind them all!
181 zapOccInfo bndr | isTyVar bndr = bndr
182 | otherwise = maybeModifyIdInfo zapLamIdInfo bndr
186 type Matcher result = IdOrTyVarSet -- Template variables
187 -> (Subst -> Maybe result) -- Continuation if success
188 -> Subst -> Maybe result -- Substitution so far -> result
189 -- The *SubstEnv* in these Substs apply to the TEMPLATE only
191 -- The *InScopeSet* in these Substs gives a superset of the free vars
192 -- in the term being matched. This set can get augmented, for example
193 -- when matching against a lambda:
194 -- (\x.M) ~ N iff M ~ N x
195 -- but we must clone x if it's already free in N
197 match :: CoreExpr -- Template
198 -> CoreExpr -- Target
203 match (Var v1) e2 tpl_vars kont subst
204 = case lookupSubst subst v1 of
205 Nothing | v1 `elemVarSet` tpl_vars -> kont (extendSubst subst v1 (DoneEx e2))
206 -- v1 is a template variables
208 | eqExpr (Var v1) e2 -> kont subst
209 -- v1 is not a template variable, so it must be a global constant
211 Just (DoneEx e2') | eqExpr e2' e2 -> kont subst
215 match (Con c1 es1) (Con c2 es2) tpl_vars kont subst
217 = matches es1 es2 tpl_vars kont subst
219 match (App f1 a1) (App f2 a2) tpl_vars kont subst
220 = match f1 f2 tpl_vars (match a1 a2 tpl_vars kont) subst
222 match (Lam x1 e1) (Lam x2 e2) tpl_vars kont subst
223 = bind [x1] [x2] (match e1 e2) tpl_vars kont subst
225 {- THESE EQUATIONS ARE BOGUS. SLPJ 19 May 99
226 -- This rule does eta expansion
227 -- (\x.M) ~ N iff M ~ N x
228 -- We must clone the binder in case it's already in scope in N
229 match (Lam x1 e1) e2 tpl_vars kont subst
230 = match e1 (App e2 (mkVarArg x1')) tpl_vars kont' subst'
232 (subst', x1') = substBndr subst x1
233 kont' subst = kont (unBindSubst subst x1 x1')
235 -- Eta expansion the other way
236 -- M ~ (\y.N) iff \y.M y ~ \y.N
238 -- Remembering that by (A), y can't be free in M, we get this
239 match e1 (Lam x2 e2) tpl_vars kont subst
240 = match (App e1 (mkVarArg x2)) e2 tpl_vars kont subst
243 match (Case e1 x1 alts1) (Case e2 x2 alts2) tpl_vars kont subst
244 = match e1 e2 tpl_vars case_kont subst
246 case_kont subst = bind [x1] [x2] (match_alts alts1 (sortLt lt_alt alts2))
249 match (Type ty1) (Type ty2) tpl_vars kont subst
250 = match_ty ty1 ty2 tpl_vars kont subst
252 match (Note (Coerce to1 from1) e1) (Note (Coerce to2 from2) e2)
254 = (match_ty to1 to2 tpl_vars $
255 match_ty from1 from2 tpl_vars $
256 match e1 e2 tpl_vars kont) subst
259 {- I don't buy this let-rule any more
260 The let rule fails on matching
261 forall f,x,xs. f (x:xs)
263 f (let y = e in (y:[]))
264 because we just get x->y, which is bogus.
266 -- This is an interesting rule: we simply ignore lets in the
267 -- term being matched against! The unfolding inside it is (by assumption)
268 -- already inside any occurrences of the bound variables, so we'll expand
269 -- them when we encounter them. Meanwhile, we can't get false matches because
270 -- (also by assumption) the term being matched has no shadowing.
271 match e1 (Let bind e2) tpl_vars kont subst
272 = match e1 e2 tpl_vars kont subst
275 -- Here is another important rule: if the term being matched is a
276 -- variable, we expand it so long as its unfolding is a WHNF
277 -- (Its occurrence information is not necessarily up to date,
278 -- so we don't use it.)
279 match e1 (Var v2) tpl_vars kont subst
280 = case getIdUnfolding v2 of
281 CoreUnfolding form guidance unfolding
283 -> match e1 unfolding tpl_vars kont subst
287 -- We can't cope with lets in the template
289 match e1 e2 tpl_vars kont subst = match_fail
292 ------------------------------------------
293 match_alts [] [] tpl_vars kont subst
295 match_alts ((c1,vs1,r1):alts1) ((c2,vs2,r2):alts2) tpl_vars kont subst
297 = bind vs1 vs2 (match r1 r2) tpl_vars
298 (match_alts alts1 alts2 tpl_vars kont)
300 match_alts alts1 alts2 tpl_vars kont subst = match_fail
302 lt_alt (con1, _, _) (con2, _, _) = con1 < con2
304 ----------------------------------------
305 bind :: [CoreBndr] -- Template binders
306 -> [CoreBndr] -- Target binders
309 -- This makes uses of assumption (A) above. For example,
311 -- Template: (\x.y) (y is free)
312 -- Target : (\y.y) (y is bound)
313 -- We rename x to y in the template... but then erroneously
314 -- match y against y. But this can't happen because of (A)
315 bind vs1 vs2 matcher tpl_vars kont subst
316 = ASSERT( all not_in_subst vs1)
317 matcher tpl_vars kont' subst'
319 kont' subst'' = kont (unBindSubstList subst'' vs1 vs2)
320 subst' = bindSubstList subst vs1 vs2
322 -- The unBindSubst relies on no shadowing in the template
323 not_in_subst v = not (maybeToBool (lookupSubst subst v))
325 ----------------------------------------
326 match_ty ty1 ty2 tpl_vars kont subst
327 = case Unify.match ty1 ty2 tpl_vars Just (substEnv subst) of
328 Nothing -> match_fail
329 Just senv' -> kont (setSubstEnv subst senv')
331 ----------------------------------------
332 matches [] [] tpl_vars kont subst
334 matches (e:es) (e':es') tpl_vars kont subst
335 = match e e' tpl_vars (matches es es' tpl_vars kont) subst
336 matches es es' tpl_vars kont subst
339 ----------------------------------------
340 mkVarArg :: CoreBndr -> CoreArg
341 mkVarArg v | isId v = Var v
342 | otherwise = Type (mkTyVarTy v)
345 %************************************************************************
347 \subsection{Adding a new rule}
349 %************************************************************************
352 addRule :: Id -> CoreRules -> CoreRule -> CoreRules
354 -- Insert the new rule just before a rule that is *less specific*
355 -- than the new one; or at the end if there isn't such a one.
356 -- In this way we make sure that when looking up, the first match
357 -- is the most specific.
359 -- We make no check for rules that unify without one dominating
360 -- the other. Arguably this would be a bug.
362 addRule id (Rules rules rhs_fvs) (Rule str tpl_vars tpl_args rhs)
363 = Rules (insert rules) (rhs_fvs `unionVarSet` new_rhs_fvs)
365 new_rule = Rule str tpl_vars' tpl_args rhs'
366 -- Add occ info to tpl_vars, rhs
368 (rhs_uds, rhs') = occurAnalyseExpr isLocallyDefined rhs
369 (rhs_uds1, tpl_vars') = tagBinders rhs_uds tpl_vars
371 insert [] = [new_rule]
372 insert (rule:rules) | new_is_more_specific rule = (new_rule:rule:rules)
373 | otherwise = rule : insert rules
375 new_is_more_specific rule = maybeToBool (matchRule tpl_var_set rule tpl_args)
377 tpl_var_set = mkVarSet tpl_vars'
378 -- Actually we should probably include the free vars of tpl_args,
379 -- but I can't be bothered
381 new_rhs_fvs = (exprFreeVars rhs' `minusVarSet` tpl_var_set) `delVarSet` id
383 -- Don't include the Id in its own rhs free-var set.
384 -- Otherwise the occurrence analyser makes bindings recursive
385 -- that shoudn't be. E.g.
386 -- RULE: f (f x y) z ==> f x (f y z)
388 addIdSpecialisations :: Id -> [([CoreBndr], [CoreExpr], CoreExpr)] -> Id
389 addIdSpecialisations id spec_stuff
390 = setIdSpecialisation id new_rules
392 rule_name = _PK_ ("SPEC " ++ showSDoc (ppr id))
393 new_rules = foldr add (getIdSpecialisation id) spec_stuff
394 add (vars, args, rhs) rules = addRule id rules (Rule rule_name vars args rhs)
398 %************************************************************************
400 \subsection{Preparing the rule base
402 %************************************************************************
407 Bool -- True <=> this rule was defined in this module,
408 Id -- What Id is it for
409 CoreRule -- The rule itself
412 pprProtoCoreRule (ProtoCoreRule _ fn rule) = pprCoreRule (Just fn) rule
414 lookupRule :: InScopeSet -> Id -> [CoreExpr] -> Maybe (FAST_STRING, CoreExpr, [CoreExpr])
415 lookupRule in_scope fn args
416 = case getIdSpecialisation fn of
417 Rules rules _ -> matchRules in_scope rules args
419 orphanRule :: ProtoCoreRule -> Bool
420 -- An "orphan rule" is one that is defined in this
421 -- module, but of ran *imported* function. We need
422 -- to track these separately when generating the interface file
423 orphanRule (ProtoCoreRule local fn _)
424 = local && not (isLocallyDefined fn)
428 %************************************************************************
430 \subsection{Getting the rules ready}
432 %************************************************************************
435 type RuleBase = (IdSet, -- Imported Ids that have rules attached
436 IdSet) -- Ids (whether local or imported) mentioned on
437 -- LHS of some rule; these should be black listed
439 -- The rule Ids and LHS Ids are black-listed; that is, they aren't inlined
440 -- so that the opportunity to apply the rule isn't lost too soon
442 prepareRuleBase :: [CoreBind] -> [ProtoCoreRule] -> ([CoreBind], RuleBase)
443 prepareRuleBase binds rules
444 = (map zap_bind binds, (imported_rule_ids, rule_lhs_fvs))
446 (rule_ids, rule_lhs_fvs) = foldr add_rule (emptyVarSet, emptyVarSet) rules
447 imported_rule_ids = filterVarSet (not . isLocallyDefined) rule_ids
449 -- rule_fvs is the set of all variables mentioned in rules
450 rule_fvs = foldVarSet (unionVarSet . idRuleVars) rule_lhs_fvs rule_ids
452 -- Attach the rules for each locally-defined Id to that Id.
453 -- - This makes the rules easier to look up
454 -- - It means that transformation rules and specialisations for
455 -- locally defined Ids are handled uniformly
456 -- - It keeps alive things that are referred to only from a rule
457 -- (the occurrence analyser knows about rules attached to Ids)
458 -- - It makes sure that, when we apply a rule, the free vars
459 -- of the RHS are more likely to be in scope
461 -- The LHS and RHS Ids are marked 'no-discard'.
462 -- This means that the binding won't be discarded EVEN if the binding
463 -- ends up being trivial (v = w) -- the simplifier would usually just
464 -- substitute w for v throughout, but we don't apply the substitution to
465 -- the rules (maybe we should?), so this substitution would make the rule
467 zap_bind (NonRec b r) = NonRec (zap_bndr b) r
468 zap_bind (Rec prs) = Rec [(zap_bndr b, r) | (b,r) <- prs]
470 zap_bndr bndr = case lookupVarSet rule_ids bndr of
471 Just bndr' -> setIdNoDiscard bndr'
472 Nothing | bndr `elemVarSet` rule_fvs -> setIdNoDiscard bndr
475 add_rule (ProtoCoreRule _ id rule)
476 (rule_id_set, rule_fvs)
477 = (rule_id_set `extendVarSet` new_id,
478 rule_fvs `unionVarSet` extendVarSet lhs_fvs id)
480 new_id = case lookupVarSet rule_id_set id of
481 Just id' -> addRuleToId id' rule
482 Nothing -> addRuleToId id rule
483 lhs_fvs = ruleSomeLhsFreeVars isId rule
484 -- Find *all* the free Ids of the LHS, not just
485 -- locally defined ones!!
487 addRuleToId id rule = setIdSpecialisation id (addRule id (getIdSpecialisation id) rule)