never executed always true always false
1 {-
2 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
3
4 \section[CoreRules]{Rewrite rules}
5 -}
6
7
8 -- | Functions for collecting together and applying rewrite rules to a module.
9 -- The 'CoreRule' datatype itself is declared elsewhere.
10 module GHC.Core.Rules (
11 -- ** Constructing
12 emptyRuleBase, mkRuleBase, extendRuleBaseList,
13 unionRuleBase, pprRuleBase,
14
15 -- ** Checking rule applications
16 ruleCheckProgram,
17
18 -- ** Manipulating 'RuleInfo' rules
19 extendRuleInfo, addRuleInfo,
20 addIdSpecialisations,
21
22 -- * Misc. CoreRule helpers
23 rulesOfBinds, getRules, pprRulesForUser,
24
25 lookupRule, mkRule, roughTopNames, initRuleOpts
26 ) where
27
28 import GHC.Prelude
29
30 import GHC.Driver.Session ( DynFlags, gopt, targetPlatform, homeUnitId_ )
31 import GHC.Driver.Flags
32
33 import GHC.Unit.Types ( primUnitId, bignumUnitId )
34 import GHC.Unit.Module ( Module )
35 import GHC.Unit.Module.Env
36
37 import GHC.Core -- All of it
38 import GHC.Core.Subst
39 import GHC.Core.SimpleOpt ( exprIsLambda_maybe )
40 import GHC.Core.FVs ( exprFreeVars, exprsFreeVars, bindFreeVars
41 , rulesFreeVarsDSet, exprsOrphNames, exprFreeVarsList )
42 import GHC.Core.Utils ( exprType, eqExpr, mkTick, mkTicks
43 , stripTicksTopT, stripTicksTopE
44 , isJoinBind )
45 import GHC.Core.Ppr ( pprRules )
46 import GHC.Core.Unify as Unify ( ruleMatchTyKiX )
47 import GHC.Core.Type as Type
48 ( Type, TCvSubst, extendTvSubst, extendCvSubst
49 , mkEmptyTCvSubst, substTy )
50 import GHC.Core.Coercion as Coercion
51 import GHC.Core.Tidy ( tidyRules )
52
53 import GHC.Tc.Utils.TcType ( tcSplitTyConApp_maybe )
54 import GHC.Builtin.Types ( anyTypeOfKind )
55
56 import GHC.Types.Id
57 import GHC.Types.Id.Info ( RuleInfo( RuleInfo ) )
58 import GHC.Types.Var
59 import GHC.Types.Var.Env
60 import GHC.Types.Var.Set
61 import GHC.Types.Name ( Name, NamedThing(..), nameIsLocalOrFrom )
62 import GHC.Types.Name.Set
63 import GHC.Types.Name.Env
64 import GHC.Types.Unique.FM
65 import GHC.Types.Tickish
66 import GHC.Types.Basic
67
68 import GHC.Data.FastString
69 import GHC.Data.Maybe
70 import GHC.Data.Bag
71
72 import GHC.Utils.Misc as Utils
73 import GHC.Utils.Trace
74 import GHC.Utils.Outputable
75 import GHC.Utils.Panic
76 import GHC.Utils.Constants (debugIsOn)
77
78 import Data.List (sortBy, mapAccumL, isPrefixOf)
79 import Data.Function ( on )
80 import Control.Monad ( guard )
81
82 {-
83 Note [Overall plumbing for rules]
84 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
85 * After the desugarer:
86 - The ModGuts initially contains mg_rules :: [CoreRule] of
87 locally-declared rules for imported Ids.
88 - Locally-declared rules for locally-declared Ids are attached to
89 the IdInfo for that Id. See Note [Attach rules to local ids] in
90 GHC.HsToCore.Binds
91
92 * GHC.Iface.Tidy strips off all the rules from local Ids and adds them to
93 mg_rules, so that the ModGuts has *all* the locally-declared rules.
94
95 * The HomePackageTable contains a ModDetails for each home package
96 module. Each contains md_rules :: [CoreRule] of rules declared in
97 that module. The HomePackageTable grows as ghc --make does its
98 up-sweep. In batch mode (ghc -c), the HPT is empty; all imported modules
99 are treated by the "external" route, discussed next, regardless of
100 which package they come from.
101
102 * The ExternalPackageState has a single eps_rule_base :: RuleBase for
103 Ids in other packages. This RuleBase simply grow monotonically, as
104 ghc --make compiles one module after another.
105
106 During simplification, interface files may get demand-loaded,
107 as the simplifier explores the unfoldings for Ids it has in
108 its hand. (Via an unsafePerformIO; the EPS is really a cache.)
109 That in turn may make the EPS rule-base grow. In contrast, the
110 HPT never grows in this way.
111
112 * The result of all this is that during Core-to-Core optimisation
113 there are four sources of rules:
114
115 (a) Rules in the IdInfo of the Id they are a rule for. These are
116 easy: fast to look up, and if you apply a substitution then
117 it'll be applied to the IdInfo as a matter of course.
118
119 (b) Rules declared in this module for imported Ids, kept in the
120 ModGuts. If you do a substitution, you'd better apply the
121 substitution to these. There are seldom many of these.
122
123 (c) Rules declared in the HomePackageTable. These never change.
124
125 (d) Rules in the ExternalPackageTable. These can grow in response
126 to lazy demand-loading of interfaces.
127
128 * At the moment (c) is carried in a reader-monad way by the GHC.Core.Opt.Monad.
129 The HomePackageTable doesn't have a single RuleBase because technically
130 we should only be able to "see" rules "below" this module; so we
131 generate a RuleBase for (c) by combing rules from all the modules
132 "below" us. That's why we can't just select the home-package RuleBase
133 from HscEnv.
134
135 [NB: we are inconsistent here. We should do the same for external
136 packages, but we don't. Same for type-class instances.]
137
138 * So in the outer simplifier loop, we combine (b-d) into a single
139 RuleBase, reading
140 (b) from the ModGuts,
141 (c) from the GHC.Core.Opt.Monad, and
142 (d) from its mutable variable
143 [Of course this means that we won't see new EPS rules that come in
144 during a single simplifier iteration, but that probably does not
145 matter.]
146
147
148 ************************************************************************
149 * *
150 \subsection[specialisation-IdInfo]{Specialisation info about an @Id@}
151 * *
152 ************************************************************************
153
154 A @CoreRule@ holds details of one rule for an @Id@, which
155 includes its specialisations.
156
157 For example, if a rule for @f@ contains the mapping:
158 \begin{verbatim}
159 forall a b d. [Type (List a), Type b, Var d] ===> f' a b
160 \end{verbatim}
161 then when we find an application of f to matching types, we simply replace
162 it by the matching RHS:
163 \begin{verbatim}
164 f (List Int) Bool dict ===> f' Int Bool
165 \end{verbatim}
166 All the stuff about how many dictionaries to discard, and what types
167 to apply the specialised function to, are handled by the fact that the
168 Rule contains a template for the result of the specialisation.
169
170 There is one more exciting case, which is dealt with in exactly the same
171 way. If the specialised value is unboxed then it is lifted at its
172 definition site and unlifted at its uses. For example:
173
174 pi :: forall a. Num a => a
175
176 might have a specialisation
177
178 [Int#] ===> (case pi' of Lift pi# -> pi#)
179
180 where pi' :: Lift Int# is the specialised version of pi.
181 -}
182
183 mkRule :: Module -> Bool -> Bool -> RuleName -> Activation
184 -> Name -> [CoreBndr] -> [CoreExpr] -> CoreExpr -> CoreRule
185 -- ^ Used to make 'CoreRule' for an 'Id' defined in the module being
186 -- compiled. See also 'GHC.Core.CoreRule'
187 mkRule this_mod is_auto is_local name act fn bndrs args rhs
188 = Rule { ru_name = name, ru_fn = fn, ru_act = act,
189 ru_bndrs = bndrs, ru_args = args,
190 ru_rhs = rhs,
191 ru_rough = roughTopNames args,
192 ru_origin = this_mod,
193 ru_orphan = orph,
194 ru_auto = is_auto, ru_local = is_local }
195 where
196 -- Compute orphanhood. See Note [Orphans] in GHC.Core.InstEnv
197 -- A rule is an orphan only if none of the variables
198 -- mentioned on its left-hand side are locally defined
199 lhs_names = extendNameSet (exprsOrphNames args) fn
200
201 -- Since rules get eventually attached to one of the free names
202 -- from the definition when compiling the ABI hash, we should make
203 -- it deterministic. This chooses the one with minimal OccName
204 -- as opposed to uniq value.
205 local_lhs_names = filterNameSet (nameIsLocalOrFrom this_mod) lhs_names
206 orph = chooseOrphanAnchor local_lhs_names
207
208 --------------
209 roughTopNames :: [CoreExpr] -> [Maybe Name]
210 -- ^ Find the \"top\" free names of several expressions.
211 -- Such names are either:
212 --
213 -- 1. The function finally being applied to in an application chain
214 -- (if that name is a GlobalId: see "GHC.Types.Var#globalvslocal"), or
215 --
216 -- 2. The 'TyCon' if the expression is a 'Type'
217 --
218 -- This is used for the fast-match-check for rules;
219 -- if the top names don't match, the rest can't
220 roughTopNames args = map roughTopName args
221
222 roughTopName :: CoreExpr -> Maybe Name
223 roughTopName (Type ty) = case tcSplitTyConApp_maybe ty of
224 Just (tc,_) -> Just (getName tc)
225 Nothing -> Nothing
226 roughTopName (Coercion _) = Nothing
227 roughTopName (App f _) = roughTopName f
228 roughTopName (Var f) | isGlobalId f -- Note [Care with roughTopName]
229 , isDataConWorkId f || idArity f > 0
230 = Just (idName f)
231 roughTopName (Tick t e) | tickishFloatable t
232 = roughTopName e
233 roughTopName _ = Nothing
234
235 ruleCantMatch :: [Maybe Name] -> [Maybe Name] -> Bool
236 -- ^ @ruleCantMatch tpl actual@ returns True only if @actual@
237 -- definitely can't match @tpl@ by instantiating @tpl@.
238 -- It's only a one-way match; unlike instance matching we
239 -- don't consider unification.
240 --
241 -- Notice that [_$_]
242 -- @ruleCantMatch [Nothing] [Just n2] = False@
243 -- Reason: a template variable can be instantiated by a constant
244 -- Also:
245 -- @ruleCantMatch [Just n1] [Nothing] = False@
246 -- Reason: a local variable @v@ in the actuals might [_$_]
247
248 ruleCantMatch (Just n1 : ts) (Just n2 : as) = n1 /= n2 || ruleCantMatch ts as
249 ruleCantMatch (_ : ts) (_ : as) = ruleCantMatch ts as
250 ruleCantMatch _ _ = False
251
252 {-
253 Note [Care with roughTopName]
254 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
255 Consider this
256 module M where { x = a:b }
257 module N where { ...f x...
258 RULE f (p:q) = ... }
259 You'd expect the rule to match, because the matcher can
260 look through the unfolding of 'x'. So we must avoid roughTopName
261 returning 'M.x' for the call (f x), or else it'll say "can't match"
262 and we won't even try!!
263
264 However, suppose we have
265 RULE g (M.h x) = ...
266 foo = ...(g (M.k v))....
267 where k is a *function* exported by M. We never really match
268 functions (lambdas) except by name, so in this case it seems like
269 a good idea to treat 'M.k' as a roughTopName of the call.
270 -}
271
272 pprRulesForUser :: [CoreRule] -> SDoc
273 -- (a) tidy the rules
274 -- (b) sort them into order based on the rule name
275 -- (c) suppress uniques (unless -dppr-debug is on)
276 -- This combination makes the output stable so we can use in testing
277 -- It's here rather than in GHC.Core.Ppr because it calls tidyRules
278 pprRulesForUser rules
279 = withPprStyle defaultUserStyle $
280 pprRules $
281 sortBy (lexicalCompareFS `on` ruleName) $
282 tidyRules emptyTidyEnv rules
283
284 {-
285 ************************************************************************
286 * *
287 RuleInfo: the rules in an IdInfo
288 * *
289 ************************************************************************
290 -}
291
292 extendRuleInfo :: RuleInfo -> [CoreRule] -> RuleInfo
293 extendRuleInfo (RuleInfo rs1 fvs1) rs2
294 = RuleInfo (rs2 ++ rs1) (rulesFreeVarsDSet rs2 `unionDVarSet` fvs1)
295
296 addRuleInfo :: RuleInfo -> RuleInfo -> RuleInfo
297 addRuleInfo (RuleInfo rs1 fvs1) (RuleInfo rs2 fvs2)
298 = RuleInfo (rs1 ++ rs2) (fvs1 `unionDVarSet` fvs2)
299
300 addIdSpecialisations :: Id -> [CoreRule] -> Id
301 addIdSpecialisations id rules
302 | null rules
303 = id
304 | otherwise
305 = setIdSpecialisation id $
306 extendRuleInfo (idSpecialisation id) rules
307
308 -- | Gather all the rules for locally bound identifiers from the supplied bindings
309 rulesOfBinds :: [CoreBind] -> [CoreRule]
310 rulesOfBinds binds = concatMap (concatMap idCoreRules . bindersOf) binds
311
312 getRules :: RuleEnv -> Id -> [CoreRule]
313 -- See Note [Where rules are found]
314 getRules (RuleEnv { re_base = rule_base, re_visible_orphs = orphs }) fn
315 = idCoreRules fn ++ filter (ruleIsVisible orphs) imp_rules
316 where
317 imp_rules = lookupNameEnv rule_base (idName fn) `orElse` []
318
319 ruleIsVisible :: ModuleSet -> CoreRule -> Bool
320 ruleIsVisible _ BuiltinRule{} = True
321 ruleIsVisible vis_orphs Rule { ru_orphan = orph, ru_origin = origin }
322 = notOrphan orph || origin `elemModuleSet` vis_orphs
323
324 {- Note [Where rules are found]
325 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
326 The rules for an Id come from two places:
327 (a) the ones it is born with, stored inside the Id itself (idCoreRules fn),
328 (b) rules added in other modules, stored in the global RuleBase (imp_rules)
329
330 It's tempting to think that
331 - LocalIds have only (a)
332 - non-LocalIds have only (b)
333
334 but that isn't quite right:
335
336 - PrimOps and ClassOps are born with a bunch of rules inside the Id,
337 even when they are imported
338
339 - The rules in GHC.Core.Opt.ConstantFold.builtinRules should be active even
340 in the module defining the Id (when it's a LocalId), but
341 the rules are kept in the global RuleBase
342
343
344 ************************************************************************
345 * *
346 RuleBase
347 * *
348 ************************************************************************
349 -}
350
351 -- RuleBase itself is defined in GHC.Core, along with CoreRule
352
353 emptyRuleBase :: RuleBase
354 emptyRuleBase = emptyNameEnv
355
356 mkRuleBase :: [CoreRule] -> RuleBase
357 mkRuleBase rules = extendRuleBaseList emptyRuleBase rules
358
359 extendRuleBaseList :: RuleBase -> [CoreRule] -> RuleBase
360 extendRuleBaseList rule_base new_guys
361 = foldl' extendRuleBase rule_base new_guys
362
363 unionRuleBase :: RuleBase -> RuleBase -> RuleBase
364 unionRuleBase rb1 rb2 = plusNameEnv_C (++) rb1 rb2
365
366 extendRuleBase :: RuleBase -> CoreRule -> RuleBase
367 extendRuleBase rule_base rule
368 = extendNameEnv_Acc (:) Utils.singleton rule_base (ruleIdName rule) rule
369
370 pprRuleBase :: RuleBase -> SDoc
371 pprRuleBase rules = pprUFM rules $ \rss ->
372 vcat [ pprRules (tidyRules emptyTidyEnv rs)
373 | rs <- rss ]
374
375 {-
376 ************************************************************************
377 * *
378 Matching
379 * *
380 ************************************************************************
381 -}
382
383 -- | The main rule matching function. Attempts to apply all (active)
384 -- supplied rules to this instance of an application in a given
385 -- context, returning the rule applied and the resulting expression if
386 -- successful.
387 lookupRule :: RuleOpts -> InScopeEnv
388 -> (Activation -> Bool) -- When rule is active
389 -> Id -> [CoreExpr]
390 -> [CoreRule] -> Maybe (CoreRule, CoreExpr)
391
392 -- See Note [Extra args in rule matching]
393 -- See comments on matchRule
394 lookupRule opts rule_env@(in_scope,_) is_active fn args rules
395 = -- pprTrace "matchRules" (ppr fn <+> ppr args $$ ppr rules ) $
396 case go [] rules of
397 [] -> Nothing
398 (m:ms) -> Just (findBest in_scope (fn,args') m ms)
399 where
400 rough_args = map roughTopName args
401
402 -- Strip ticks from arguments, see note [Tick annotations in RULE
403 -- matching]. We only collect ticks if a rule actually matches -
404 -- this matters for performance tests.
405 args' = map (stripTicksTopE tickishFloatable) args
406 ticks = concatMap (stripTicksTopT tickishFloatable) args
407
408 go :: [(CoreRule,CoreExpr)] -> [CoreRule] -> [(CoreRule,CoreExpr)]
409 go ms [] = ms
410 go ms (r:rs)
411 | Just e <- matchRule opts rule_env is_active fn args' rough_args r
412 = go ((r,mkTicks ticks e):ms) rs
413 | otherwise
414 = -- pprTrace "match failed" (ppr r $$ ppr args $$
415 -- ppr [ (arg_id, unfoldingTemplate unf)
416 -- | Var arg_id <- args
417 -- , let unf = idUnfolding arg_id
418 -- , isCheapUnfolding unf] )
419 go ms rs
420
421 findBest :: InScopeSet -> (Id, [CoreExpr])
422 -> (CoreRule,CoreExpr) -> [(CoreRule,CoreExpr)] -> (CoreRule,CoreExpr)
423 -- All these pairs matched the expression
424 -- Return the pair the most specific rule
425 -- The (fn,args) is just for overlap reporting
426
427 findBest _ _ (rule,ans) [] = (rule,ans)
428 findBest in_scope target (rule1,ans1) ((rule2,ans2):prs)
429 | isMoreSpecific in_scope rule1 rule2 = findBest in_scope target (rule1,ans1) prs
430 | isMoreSpecific in_scope rule2 rule1 = findBest in_scope target (rule2,ans2) prs
431 | debugIsOn = let pp_rule rule
432 = ifPprDebug (ppr rule)
433 (doubleQuotes (ftext (ruleName rule)))
434 in pprTrace "Rules.findBest: rule overlap (Rule 1 wins)"
435 (vcat [ whenPprDebug $
436 text "Expression to match:" <+> ppr fn
437 <+> sep (map ppr args)
438 , text "Rule 1:" <+> pp_rule rule1
439 , text "Rule 2:" <+> pp_rule rule2]) $
440 findBest in_scope target (rule1,ans1) prs
441 | otherwise = findBest in_scope target (rule1,ans1) prs
442 where
443 (fn,args) = target
444
445 isMoreSpecific :: InScopeSet -> CoreRule -> CoreRule -> Bool
446 -- This tests if one rule is more specific than another
447 -- We take the view that a BuiltinRule is less specific than
448 -- anything else, because we want user-define rules to "win"
449 -- In particular, class ops have a built-in rule, but we
450 -- any user-specific rules to win
451 -- eg (#4397)
452 -- truncate :: (RealFrac a, Integral b) => a -> b
453 -- {-# RULES "truncate/Double->Int" truncate = double2Int #-}
454 -- double2Int :: Double -> Int
455 -- We want the specific RULE to beat the built-in class-op rule
456 isMoreSpecific _ (BuiltinRule {}) _ = False
457 isMoreSpecific _ (Rule {}) (BuiltinRule {}) = True
458 isMoreSpecific in_scope (Rule { ru_bndrs = bndrs1, ru_args = args1 })
459 (Rule { ru_bndrs = bndrs2, ru_args = args2
460 , ru_name = rule_name2, ru_rhs = rhs2 })
461 = isJust (matchN (full_in_scope, id_unfolding_fun)
462 rule_name2 bndrs2 args2 args1 rhs2)
463 where
464 id_unfolding_fun _ = NoUnfolding -- Don't expand in templates
465 full_in_scope = in_scope `extendInScopeSetList` bndrs1
466
467 noBlackList :: Activation -> Bool
468 noBlackList _ = False -- Nothing is black listed
469
470 {-
471 Note [Extra args in rule matching]
472 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
473 If we find a matching rule, we return (Just (rule, rhs)),
474 but the rule firing has only consumed as many of the input args
475 as the ruleArity says. It's up to the caller to keep track
476 of any left-over args. E.g. if you call
477 lookupRule ... f [e1, e2, e3]
478 and it returns Just (r, rhs), where r has ruleArity 2
479 then the real rewrite is
480 f e1 e2 e3 ==> rhs e3
481
482 You might think it'd be cleaner for lookupRule to deal with the
483 leftover arguments, by applying 'rhs' to them, but the main call
484 in the Simplifier works better as it is. Reason: the 'args' passed
485 to lookupRule are the result of a lazy substitution
486 -}
487
488 ------------------------------------
489 matchRule :: RuleOpts -> InScopeEnv -> (Activation -> Bool)
490 -> Id -> [CoreExpr] -> [Maybe Name]
491 -> CoreRule -> Maybe CoreExpr
492
493 -- If (matchRule rule args) returns Just (name,rhs)
494 -- then (f args) matches the rule, and the corresponding
495 -- rewritten RHS is rhs
496 --
497 -- The returned expression is occurrence-analysed
498 --
499 -- Example
500 --
501 -- The rule
502 -- forall f g x. map f (map g x) ==> map (f . g) x
503 -- is stored
504 -- CoreRule "map/map"
505 -- [f,g,x] -- tpl_vars
506 -- [f,map g x] -- tpl_args
507 -- map (f.g) x) -- rhs
508 --
509 -- Then the call: matchRule the_rule [e1,map e2 e3]
510 -- = Just ("map/map", (\f,g,x -> rhs) e1 e2 e3)
511 --
512 -- Any 'surplus' arguments in the input are simply put on the end
513 -- of the output.
514
515 matchRule opts rule_env _is_active fn args _rough_args
516 (BuiltinRule { ru_try = match_fn })
517 -- Built-in rules can't be switched off, it seems
518 = case match_fn opts rule_env fn args of
519 Nothing -> Nothing
520 Just expr -> Just expr
521
522 matchRule _ rule_env is_active _ args rough_args
523 (Rule { ru_name = rule_name, ru_act = act, ru_rough = tpl_tops
524 , ru_bndrs = tpl_vars, ru_args = tpl_args, ru_rhs = rhs })
525 | not (is_active act) = Nothing
526 | ruleCantMatch tpl_tops rough_args = Nothing
527 | otherwise = matchN rule_env rule_name tpl_vars tpl_args args rhs
528
529
530 -- | Initialize RuleOpts from DynFlags
531 initRuleOpts :: DynFlags -> RuleOpts
532 initRuleOpts dflags = RuleOpts
533 { roPlatform = targetPlatform dflags
534 , roNumConstantFolding = gopt Opt_NumConstantFolding dflags
535 , roExcessRationalPrecision = gopt Opt_ExcessPrecision dflags
536 -- disable bignum rules in ghc-prim and ghc-bignum itself
537 , roBignumRules = homeUnitId_ dflags /= primUnitId
538 && homeUnitId_ dflags /= bignumUnitId
539 }
540
541
542 ---------------------------------------
543 matchN :: InScopeEnv
544 -> RuleName -> [Var] -> [CoreExpr]
545 -> [CoreExpr] -> CoreExpr -- ^ Target; can have more elements than the template
546 -> Maybe CoreExpr
547 -- For a given match template and context, find bindings to wrap around
548 -- the entire result and what should be substituted for each template variable.
549 -- Fail if there are two few actual arguments from the target to match the template
550
551 matchN (in_scope, id_unf) rule_name tmpl_vars tmpl_es target_es rhs
552 = do { rule_subst <- go init_menv emptyRuleSubst tmpl_es target_es
553 ; let (_, matched_es) = mapAccumL (lookup_tmpl rule_subst)
554 (mkEmptyTCvSubst in_scope) $
555 tmpl_vars `zip` tmpl_vars1
556 bind_wrapper = rs_binds rule_subst
557 -- Floated bindings; see Note [Matching lets]
558 ; return (bind_wrapper $
559 mkLams tmpl_vars rhs `mkApps` matched_es) }
560 where
561 (init_rn_env, tmpl_vars1) = mapAccumL rnBndrL (mkRnEnv2 in_scope) tmpl_vars
562 -- See Note [Cloning the template binders]
563
564 init_menv = RV { rv_tmpls = mkVarSet tmpl_vars1
565 , rv_lcl = init_rn_env
566 , rv_fltR = mkEmptySubst (rnInScopeSet init_rn_env)
567 , rv_unf = id_unf }
568
569 go _ subst [] _ = Just subst
570 go _ _ _ [] = Nothing -- Fail if too few actual args
571 go menv subst (t:ts) (e:es) = do { subst1 <- match menv subst t e
572 ; go menv subst1 ts es }
573
574 lookup_tmpl :: RuleSubst -> TCvSubst -> (InVar,OutVar) -> (TCvSubst, CoreExpr)
575 -- Need to return a RuleSubst solely for the benefit of mk_fake_ty
576 lookup_tmpl (RS { rs_tv_subst = tv_subst, rs_id_subst = id_subst })
577 tcv_subst (tmpl_var, tmpl_var1)
578 | isId tmpl_var1
579 = case lookupVarEnv id_subst tmpl_var1 of
580 Just e | Coercion co <- e
581 -> (Type.extendCvSubst tcv_subst tmpl_var1 co, Coercion co)
582 | otherwise
583 -> (tcv_subst, e)
584 Nothing | Just refl_co <- isReflCoVar_maybe tmpl_var1
585 , let co = Coercion.substCo tcv_subst refl_co
586 -> -- See Note [Unbound RULE binders]
587 (Type.extendCvSubst tcv_subst tmpl_var1 co, Coercion co)
588 | otherwise
589 -> unbound tmpl_var
590
591 | otherwise
592 = (Type.extendTvSubst tcv_subst tmpl_var1 ty', Type ty')
593 where
594 ty' = case lookupVarEnv tv_subst tmpl_var1 of
595 Just ty -> ty
596 Nothing -> fake_ty -- See Note [Unbound RULE binders]
597 fake_ty = anyTypeOfKind (Type.substTy tcv_subst (tyVarKind tmpl_var1))
598 -- This substitution is the sole reason we accumulate
599 -- TCvSubst in lookup_tmpl
600
601 unbound tmpl_var
602 = pprPanic "Template variable unbound in rewrite rule" $
603 vcat [ text "Variable:" <+> ppr tmpl_var <+> dcolon <+> ppr (varType tmpl_var)
604 , text "Rule" <+> pprRuleName rule_name
605 , text "Rule bndrs:" <+> ppr tmpl_vars
606 , text "LHS args:" <+> ppr tmpl_es
607 , text "Actual args:" <+> ppr target_es ]
608
609
610 {- Note [Unbound RULE binders]
611 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
612 It can be the case that the binder in a rule is not actually
613 bound on the LHS:
614
615 * Type variables. Type synonyms with phantom args can give rise to
616 unbound template type variables. Consider this (#10689,
617 simplCore/should_compile/T10689):
618
619 type Foo a b = b
620
621 f :: Eq a => a -> Bool
622 f x = x==x
623
624 {-# RULES "foo" forall (x :: Foo a Char). f x = True #-}
625 finkle = f 'c'
626
627 The rule looks like
628 forall (a::*) (d::Eq Char) (x :: Foo a Char).
629 f (Foo a Char) d x = True
630
631 Matching the rule won't bind 'a', and legitimately so. We fudge by
632 pretending that 'a' is bound to (Any :: *).
633
634 * Coercion variables. On the LHS of a RULE for a local binder
635 we might have
636 RULE forall (c :: a~b). f (x |> c) = e
637 Now, if that binding is inlined, so that a=b=Int, we'd get
638 RULE forall (c :: Int~Int). f (x |> c) = e
639 and now when we simplify the LHS (Simplify.simplRule) we
640 optCoercion (look at the CoVarCo case) will turn that 'c' into Refl:
641 RULE forall (c :: Int~Int). f (x |> <Int>) = e
642 and then perhaps drop it altogether. Now 'c' is unbound.
643
644 It's tricky to be sure this never happens, so instead I
645 say it's OK to have an unbound coercion binder in a RULE
646 provided its type is (c :: t~t). Then, when the RULE
647 fires we can substitute <t> for c.
648
649 This actually happened (in a RULE for a local function)
650 in #13410, and also in test T10602.
651
652 Note [Cloning the template binders]
653 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
654 Consider the following match (example 1):
655 Template: forall x. f x
656 Target: f (x+1)
657 This should succeed, because the template variable 'x' has nothing to
658 do with the 'x' in the target.
659
660 Likewise this one (example 2):
661 Template: forall x. f (\x.x)
662 Target: f (\y.y)
663
664 We achieve this simply by using rnBndrL to clone the template
665 binders if they are already in scope.
666
667 ------ Historical note -------
668 At one point I tried simply adding the template binders to the
669 in-scope set /without/ cloning them, but that failed in a horribly
670 obscure way in #14777. Problem was that during matching we look
671 up target-term variables in the in-scope set (see Note [Lookup
672 in-scope]). If a target-term variable happens to name-clash with a
673 template variable, that lookup will find the template variable, which
674 is /utterly/ bogus. In #14777, this transformed a term variable
675 into a type variable, and then crashed when we wanted its idInfo.
676 ------ End of historical note -------
677
678
679 ************************************************************************
680 * *
681 The main matcher
682 * *
683 ********************************************************************* -}
684
685 -- * The domain of the TvSubstEnv and IdSubstEnv are the template
686 -- variables passed into the match.
687 --
688 -- * The BindWrapper in a RuleSubst are the bindings floated out
689 -- from nested matches; see the Let case of match, below
690 --
691 data RuleMatchEnv
692 = RV { rv_lcl :: RnEnv2 -- Renamings for *local bindings*
693 -- (lambda/case)
694 , rv_tmpls :: VarSet -- Template variables
695 -- (after applying envL of rv_lcl)
696 , rv_fltR :: Subst -- Renamings for floated let-bindings
697 -- (domain disjoint from envR of rv_lcl)
698 -- See Note [Matching lets]
699 , rv_unf :: IdUnfoldingFun
700 }
701
702 rvInScopeEnv :: RuleMatchEnv -> InScopeEnv
703 rvInScopeEnv renv = (rnInScopeSet (rv_lcl renv), rv_unf renv)
704
705 data RuleSubst = RS { rs_tv_subst :: TvSubstEnv -- Range is the
706 , rs_id_subst :: IdSubstEnv -- template variables
707 , rs_binds :: BindWrapper -- Floated bindings
708 , rs_bndrs :: [Var] -- Variables bound by floated lets
709 }
710
711 type BindWrapper = CoreExpr -> CoreExpr
712 -- See Notes [Matching lets] and [Matching cases]
713 -- we represent the floated bindings as a core-to-core function
714
715 emptyRuleSubst :: RuleSubst
716 emptyRuleSubst = RS { rs_tv_subst = emptyVarEnv, rs_id_subst = emptyVarEnv
717 , rs_binds = \e -> e, rs_bndrs = [] }
718
719 -- At one stage I tried to match even if there are more
720 -- template args than real args.
721
722 -- I now think this is probably a bad idea.
723 -- Should the template (map f xs) match (map g)? I think not.
724 -- For a start, in general eta expansion wastes work.
725 -- SLPJ July 99
726
727 match :: RuleMatchEnv
728 -> RuleSubst
729 -> CoreExpr -- Template
730 -> CoreExpr -- Target
731 -> Maybe RuleSubst
732
733 -- We look through certain ticks. See Note [Tick annotations in RULE matching]
734 match renv subst e1 (Tick t e2)
735 | tickishFloatable t
736 = match renv subst' e1 e2
737 where subst' = subst { rs_binds = rs_binds subst . mkTick t }
738 match renv subst (Tick t e1) e2
739 -- Ignore ticks in rule template.
740 | tickishFloatable t
741 = match renv subst e1 e2
742 match _ _ e@Tick{} _
743 = pprPanic "Tick in rule" (ppr e)
744
745 -- See the notes with Unify.match, which matches types
746 -- Everything is very similar for terms
747
748 -- Interesting examples:
749 -- Consider matching
750 -- \x->f against \f->f
751 -- When we meet the lambdas we must remember to rename f to f' in the
752 -- second expression. The RnEnv2 does that.
753 --
754 -- Consider matching
755 -- forall a. \b->b against \a->3
756 -- We must rename the \a. Otherwise when we meet the lambdas we
757 -- might substitute [a/b] in the template, and then erroneously
758 -- succeed in matching what looks like the template variable 'a' against 3.
759
760 -- The Var case follows closely what happens in GHC.Core.Unify.match
761 match renv subst (Var v1) e2
762 = match_var renv subst v1 e2
763
764 match renv subst e1 (Var v2) -- Note [Expanding variables]
765 | not (inRnEnvR rn_env v2) -- Note [Do not expand locally-bound variables]
766 , Just e2' <- expandUnfolding_maybe (rv_unf renv v2')
767 = match (renv { rv_lcl = nukeRnEnvR rn_env }) subst e1 e2'
768 where
769 v2' = lookupRnInScope rn_env v2
770 rn_env = rv_lcl renv
771 -- Notice that we look up v2 in the in-scope set
772 -- See Note [Lookup in-scope]
773 -- No need to apply any renaming first (hence no rnOccR)
774 -- because of the not-inRnEnvR
775
776 match renv subst e1 (Let bind e2)
777 | -- pprTrace "match:Let" (vcat [ppr bind, ppr $ okToFloat (rv_lcl renv) (bindFreeVars bind)]) $
778 not (isJoinBind bind) -- can't float join point out of argument position
779 , okToFloat (rv_lcl renv) (bindFreeVars bind) -- See Note [Matching lets]
780 = match (renv { rv_fltR = flt_subst'
781 , rv_lcl = rv_lcl renv `extendRnInScopeSetList` new_bndrs })
782 -- We are floating the let-binding out, as if it had enclosed
783 -- the entire target from Day 1. So we must add its binders to
784 -- the in-scope set (#20200)
785 (subst { rs_binds = rs_binds subst . Let bind'
786 , rs_bndrs = new_bndrs ++ rs_bndrs subst })
787 e1 e2
788 | otherwise
789 = Nothing
790 where
791 (flt_subst', bind') = substBind (rv_fltR renv) bind
792 new_bndrs = bindersOf bind'
793
794 {- Disabled: see Note [Matching cases] below
795 match renv (tv_subst, id_subst, binds) e1
796 (Case scrut case_bndr ty [(con, alt_bndrs, rhs)])
797 | exprOkForSpeculation scrut -- See Note [Matching cases]
798 , okToFloat rn_env bndrs (exprFreeVars scrut)
799 = match (renv { me_env = rn_env' })
800 (tv_subst, id_subst, binds . case_wrap)
801 e1 rhs
802 where
803 rn_env = me_env renv
804 rn_env' = extendRnInScopeList rn_env bndrs
805 bndrs = case_bndr : alt_bndrs
806 case_wrap rhs' = Case scrut case_bndr ty [(con, alt_bndrs, rhs')]
807 -}
808
809 match _ subst (Lit lit1) (Lit lit2)
810 | lit1 == lit2
811 = Just subst
812
813 match renv subst (App f1 a1) (App f2 a2)
814 = do { subst' <- match renv subst f1 f2
815 ; match renv subst' a1 a2 }
816
817 match renv subst (Lam x1 e1) e2
818 | Just (x2, e2, ts) <- exprIsLambda_maybe (rvInScopeEnv renv) e2
819 = let renv' = rnMatchBndr2 renv x1 x2
820 subst' = subst { rs_binds = rs_binds subst . flip (foldr mkTick) ts }
821 in match renv' subst' e1 e2
822
823 match renv subst (Case e1 x1 ty1 alts1) (Case e2 x2 ty2 alts2)
824 = do { subst1 <- match_ty renv subst ty1 ty2
825 ; subst2 <- match renv subst1 e1 e2
826 ; let renv' = rnMatchBndr2 renv x1 x2
827 ; match_alts renv' subst2 alts1 alts2 -- Alts are both sorted
828 }
829
830 match renv subst (Type ty1) (Type ty2)
831 = match_ty renv subst ty1 ty2
832 match renv subst (Coercion co1) (Coercion co2)
833 = match_co renv subst co1 co2
834
835 match renv subst (Cast e1 co1) (Cast e2 co2)
836 = do { subst1 <- match_co renv subst co1 co2
837 ; match renv subst1 e1 e2 }
838
839 -- Everything else fails
840 match _ _ _e1 _e2 = -- pprTrace "Failing at" ((text "e1:" <+> ppr _e1) $$ (text "e2:" <+> ppr _e2)) $
841 Nothing
842
843 -------------
844 match_co :: RuleMatchEnv
845 -> RuleSubst
846 -> Coercion
847 -> Coercion
848 -> Maybe RuleSubst
849 match_co renv subst co1 co2
850 | Just cv <- getCoVar_maybe co1
851 = match_var renv subst cv (Coercion co2)
852 | Just (ty1, r1) <- isReflCo_maybe co1
853 = do { (ty2, r2) <- isReflCo_maybe co2
854 ; guard (r1 == r2)
855 ; match_ty renv subst ty1 ty2 }
856 match_co renv subst co1 co2
857 | Just (tc1, cos1) <- splitTyConAppCo_maybe co1
858 = case splitTyConAppCo_maybe co2 of
859 Just (tc2, cos2)
860 | tc1 == tc2
861 -> match_cos renv subst cos1 cos2
862 _ -> Nothing
863 match_co renv subst co1 co2
864 | Just (arg1, res1) <- splitFunCo_maybe co1
865 = case splitFunCo_maybe co2 of
866 Just (arg2, res2)
867 -> match_cos renv subst [arg1, res1] [arg2, res2]
868 _ -> Nothing
869 match_co _ _ co1 co2
870 -- Currently just deals with CoVarCo, TyConAppCo and Refl
871 | debugIsOn
872 = pprTrace "match_co: needs more cases" (ppr co1 $$ ppr co2) Nothing
873 | otherwise
874 = Nothing
875
876 match_cos :: RuleMatchEnv
877 -> RuleSubst
878 -> [Coercion]
879 -> [Coercion]
880 -> Maybe RuleSubst
881 match_cos renv subst (co1:cos1) (co2:cos2) =
882 do { subst' <- match_co renv subst co1 co2
883 ; match_cos renv subst' cos1 cos2 }
884 match_cos _ subst [] [] = Just subst
885 match_cos _ _ cos1 cos2 = pprTrace "match_cos: not same length" (ppr cos1 $$ ppr cos2) Nothing
886
887 -------------
888 rnMatchBndr2 :: RuleMatchEnv -> Var -> Var -> RuleMatchEnv
889 rnMatchBndr2 renv x1 x2
890 = renv { rv_lcl = rnBndr2 (rv_lcl renv) x1 x2
891 , rv_fltR = delBndr (rv_fltR renv) x2 }
892
893
894 ------------------------------------------
895 match_alts :: RuleMatchEnv
896 -> RuleSubst
897 -> [CoreAlt] -- Template
898 -> [CoreAlt] -- Target
899 -> Maybe RuleSubst
900 match_alts _ subst [] []
901 = return subst
902 match_alts renv subst (Alt c1 vs1 r1:alts1) (Alt c2 vs2 r2:alts2)
903 | c1 == c2
904 = do { subst1 <- match renv' subst r1 r2
905 ; match_alts renv subst1 alts1 alts2 }
906 where
907 renv' = foldl' mb renv (vs1 `zip` vs2)
908 mb renv (v1,v2) = rnMatchBndr2 renv v1 v2
909
910 match_alts _ _ _ _
911 = Nothing
912
913 ------------------------------------------
914 okToFloat :: RnEnv2 -> VarSet -> Bool
915 okToFloat rn_env bind_fvs
916 = allVarSet not_captured bind_fvs
917 where
918 not_captured fv = not (inRnEnvR rn_env fv)
919
920 ------------------------------------------
921 match_var :: RuleMatchEnv
922 -> RuleSubst
923 -> Var -- Template
924 -> CoreExpr -- Target
925 -> Maybe RuleSubst
926 match_var renv@(RV { rv_tmpls = tmpls, rv_lcl = rn_env, rv_fltR = flt_env })
927 subst v1 e2
928 | v1' `elemVarSet` tmpls
929 = match_tmpl_var renv subst v1' e2
930
931 | otherwise -- v1' is not a template variable; check for an exact match with e2
932 = case e2 of -- Remember, envR of rn_env is disjoint from rv_fltR
933 Var v2 | Just v2' <- rnOccR_maybe rn_env v2
934 -> -- v2 was bound by a nested lambda or case
935 if v1' == v2' then Just subst
936 else Nothing
937
938 -- v2 is not bound nestedly; it is free
939 -- in the whole expression being matched
940 -- So it will be in the InScopeSet for flt_env (#20200)
941 | Var v2' <- lookupIdSubst flt_env v2
942 , v1' == v2'
943 -> Just subst
944 | otherwise
945 -> Nothing
946
947 _ -> Nothing
948
949 where
950 v1' = rnOccL rn_env v1
951 -- If the template is
952 -- forall x. f x (\x -> x) = ...
953 -- Then the x inside the lambda isn't the
954 -- template x, so we must rename first!
955
956 ------------------------------------------
957 match_tmpl_var :: RuleMatchEnv
958 -> RuleSubst
959 -> Var -- Template
960 -> CoreExpr -- Target
961 -> Maybe RuleSubst
962
963 match_tmpl_var renv@(RV { rv_lcl = rn_env, rv_fltR = flt_env })
964 subst@(RS { rs_id_subst = id_subst, rs_bndrs = let_bndrs })
965 v1' e2
966 | any (inRnEnvR rn_env) (exprFreeVarsList e2)
967 = Nothing -- Occurs check failure
968 -- e.g. match forall a. (\x-> a x) against (\y. y y)
969
970 | Just e1' <- lookupVarEnv id_subst v1'
971 = if eqExpr (rnInScopeSet rn_env) e1' e2'
972 then Just subst
973 else Nothing
974
975 | otherwise
976 = -- Note [Matching variable types]
977 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
978 -- However, we must match the *types*; e.g.
979 -- forall (c::Char->Int) (x::Char).
980 -- f (c x) = "RULE FIRED"
981 -- We must only match on args that have the right type
982 -- It's actually quite difficult to come up with an example that shows
983 -- you need type matching, esp since matching is left-to-right, so type
984 -- args get matched first. But it's possible (e.g. simplrun008) and
985 -- this is the Right Thing to do
986 do { subst' <- match_ty renv subst (idType v1') (exprType e2)
987 ; return (subst' { rs_id_subst = id_subst' }) }
988 where
989 -- e2' is the result of applying flt_env to e2
990 e2' | null let_bndrs = e2
991 | otherwise = substExpr flt_env e2
992
993 id_subst' = extendVarEnv (rs_id_subst subst) v1' e2'
994 -- No further renaming to do on e2',
995 -- because no free var of e2' is in the rnEnvR of the envt
996
997 ------------------------------------------
998 match_ty :: RuleMatchEnv
999 -> RuleSubst
1000 -> Type -- Template
1001 -> Type -- Target
1002 -> Maybe RuleSubst
1003 -- Matching Core types: use the matcher in GHC.Tc.Utils.TcType.
1004 -- Notice that we treat newtypes as opaque. For example, suppose
1005 -- we have a specialised version of a function at a newtype, say
1006 -- newtype T = MkT Int
1007 -- We only want to replace (f T) with f', not (f Int).
1008
1009 match_ty renv subst ty1 ty2
1010 = do { tv_subst'
1011 <- Unify.ruleMatchTyKiX (rv_tmpls renv) (rv_lcl renv) tv_subst ty1 ty2
1012 ; return (subst { rs_tv_subst = tv_subst' }) }
1013 where
1014 tv_subst = rs_tv_subst subst
1015
1016 {-
1017 Note [Expanding variables]
1018 ~~~~~~~~~~~~~~~~~~~~~~~~~~
1019 Here is another Very Important rule: if the term being matched is a
1020 variable, we expand it so long as its unfolding is "expandable". (Its
1021 occurrence information is not necessarily up to date, so we don't use
1022 it.) By "expandable" we mean a WHNF or a "constructor-like" application.
1023 This is the key reason for "constructor-like" Ids. If we have
1024 {-# NOINLINE [1] CONLIKE g #-}
1025 {-# RULE f (g x) = h x #-}
1026 then in the term
1027 let v = g 3 in ....(f v)....
1028 we want to make the rule fire, to replace (f v) with (h 3).
1029
1030 Note [Do not expand locally-bound variables]
1031 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1032 Do *not* expand locally-bound variables, else there's a worry that the
1033 unfolding might mention variables that are themselves renamed.
1034 Example
1035 case x of y { (p,q) -> ...y... }
1036 Don't expand 'y' to (p,q) because p,q might themselves have been
1037 renamed. Essentially we only expand unfoldings that are "outside"
1038 the entire match.
1039
1040 Hence, (a) the guard (not (isLocallyBoundR v2))
1041 (b) when we expand we nuke the renaming envt (nukeRnEnvR).
1042
1043 Note [Tick annotations in RULE matching]
1044 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1045
1046 We used to unconditionally look through ticks in both template and
1047 expression being matched. This is actually illegal for counting or
1048 cost-centre-scoped ticks, because we have no place to put them without
1049 changing entry counts and/or costs. So now we just fail the match in
1050 these cases.
1051
1052 On the other hand, where we are allowed to insert new cost into the
1053 tick scope, we can float them upwards to the rule application site.
1054
1055 Moreover, we may encounter ticks in the template of a rule. There are a few
1056 ways in which these may be introduced (e.g. #18162, #17619). Such ticks are
1057 ignored by the matcher. See Note [Simplifying rules] in
1058 GHC.Core.Opt.Simplify.Utils for details.
1059
1060 cf Note [Tick annotations in call patterns] in GHC.Core.Opt.SpecConstr
1061
1062 Note [Matching lets]
1063 ~~~~~~~~~~~~~~~~~~~~
1064 Matching a let-expression. Consider
1065 RULE forall x. f (g x) = <rhs>
1066 and target expression
1067 f (let { w=R } in g E))
1068 Then we'd like the rule to match, to generate
1069 let { w=R } in (\x. <rhs>) E
1070 In effect, we want to float the let-binding outward, to enable
1071 the match to happen. This is the WHOLE REASON for accumulating
1072 bindings in the RuleSubst
1073
1074 We can only do this if the free variables of R are not bound by the
1075 part of the target expression outside the let binding; e.g.
1076 f (\v. let w = v+1 in g E)
1077 Here we obviously cannot float the let-binding for w. Hence the
1078 use of okToFloat.
1079
1080 There are a couple of tricky points.
1081 (a) What if floating the binding captures a variable?
1082 f (let v = x+1 in v) v
1083 --> NOT!
1084 let v = x+1 in f (x+1) v
1085
1086 (b) What if two non-nested let bindings bind the same variable?
1087 f (let v = e1 in b1) (let v = e2 in b2)
1088 --> NOT!
1089 let v = e1 in let v = e2 in (f b2 b2)
1090 See testsuite test "RuleFloatLet".
1091
1092 Our cunning plan is this:
1093 * Along with the growing substitution for template variables
1094 we maintain a growing set of floated let-bindings (rs_binds)
1095 plus the set of variables thus bound (rs_bndrs).
1096
1097 * The RnEnv2 in the MatchEnv binds only the local binders
1098 in the term (lambdas, case), not the floated let-bndrs.
1099
1100 * When we encounter a let in the term to be matched, we use
1101 okToFloat check that does not mention any locally bound (lambda,
1102 case) variables. If so we fail.
1103
1104 * We use GHC.Core.Subst.substBind to freshen the binding, using an
1105 in-scope set that is the original in-scope variables plus the
1106 rs_bndrs (currently floated let-bindings). So in (a) above
1107 we'll freshen the 'v' binding; in (b) above we'll freshen
1108 the *second* 'v' binding.
1109
1110 * We apply that freshening substitution, in a lexically-scoped
1111 way to the term, although lazily; this is the rv_fltR field.
1112
1113
1114 Note [Matching cases]
1115 ~~~~~~~~~~~~~~~~~~~~~
1116 {- NOTE: This idea is currently disabled. It really only works if
1117 the primops involved are OkForSpeculation, and, since
1118 they have side effects readIntOfAddr and touch are not.
1119 Maybe we'll get back to this later . -}
1120
1121 Consider
1122 f (case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) ->
1123 case touch# fp s# of { _ ->
1124 I# n# } } )
1125 This happened in a tight loop generated by stream fusion that
1126 Roman encountered. We'd like to treat this just like the let
1127 case, because the primops concerned are ok-for-speculation.
1128 That is, we'd like to behave as if it had been
1129 case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) ->
1130 case touch# fp s# of { _ ->
1131 f (I# n# } } )
1132
1133 Note [Lookup in-scope]
1134 ~~~~~~~~~~~~~~~~~~~~~~
1135 Consider this example
1136 foo :: Int -> Maybe Int -> Int
1137 foo 0 (Just n) = n
1138 foo m (Just n) = foo (m-n) (Just n)
1139
1140 SpecConstr sees this fragment:
1141
1142 case w_smT of wild_Xf [Just A] {
1143 Data.Maybe.Nothing -> lvl_smf;
1144 Data.Maybe.Just n_acT [Just S(L)] ->
1145 case n_acT of wild1_ams [Just A] { GHC.Base.I# y_amr [Just L] ->
1146 $wfoo_smW (GHC.Prim.-# ds_Xmb y_amr) wild_Xf
1147 }};
1148
1149 and correctly generates the rule
1150
1151 RULES: "SC:$wfoo1" [0] __forall {y_amr [Just L] :: GHC.Prim.Int#
1152 sc_snn :: GHC.Prim.Int#}
1153 $wfoo_smW sc_snn (Data.Maybe.Just @ GHC.Base.Int (GHC.Base.I# y_amr))
1154 = $s$wfoo_sno y_amr sc_snn ;]
1155
1156 BUT we must ensure that this rule matches in the original function!
1157 Note that the call to $wfoo is
1158 $wfoo_smW (GHC.Prim.-# ds_Xmb y_amr) wild_Xf
1159
1160 During matching we expand wild_Xf to (Just n_acT). But then we must also
1161 expand n_acT to (I# y_amr). And we can only do that if we look up n_acT
1162 in the in-scope set, because in wild_Xf's unfolding it won't have an unfolding
1163 at all.
1164
1165 That is why the 'lookupRnInScope' call in the (Var v2) case of 'match'
1166 is so important.
1167
1168
1169 ************************************************************************
1170 * *
1171 Rule-check the program
1172 * *
1173 ************************************************************************
1174
1175 We want to know what sites have rules that could have fired but didn't.
1176 This pass runs over the tree (without changing it) and reports such.
1177 -}
1178
1179 -- | Report partial matches for rules beginning with the specified
1180 -- string for the purposes of error reporting
1181 ruleCheckProgram :: RuleOpts -- ^ Rule options
1182 -> CompilerPhase -- ^ Rule activation test
1183 -> String -- ^ Rule pattern
1184 -> (Id -> [CoreRule]) -- ^ Rules for an Id
1185 -> CoreProgram -- ^ Bindings to check in
1186 -> SDoc -- ^ Resulting check message
1187 ruleCheckProgram ropts phase rule_pat rules binds
1188 | isEmptyBag results
1189 = text "Rule check results: no rule application sites"
1190 | otherwise
1191 = vcat [text "Rule check results:",
1192 line,
1193 vcat [ p $$ line | p <- bagToList results ]
1194 ]
1195 where
1196 env = RuleCheckEnv { rc_is_active = isActive phase
1197 , rc_id_unf = idUnfolding -- Not quite right
1198 -- Should use activeUnfolding
1199 , rc_pattern = rule_pat
1200 , rc_rules = rules
1201 , rc_ropts = ropts
1202 }
1203 results = unionManyBags (map (ruleCheckBind env) binds)
1204 line = text (replicate 20 '-')
1205
1206 data RuleCheckEnv = RuleCheckEnv {
1207 rc_is_active :: Activation -> Bool,
1208 rc_id_unf :: IdUnfoldingFun,
1209 rc_pattern :: String,
1210 rc_rules :: Id -> [CoreRule],
1211 rc_ropts :: RuleOpts
1212 }
1213
1214 ruleCheckBind :: RuleCheckEnv -> CoreBind -> Bag SDoc
1215 -- The Bag returned has one SDoc for each call site found
1216 ruleCheckBind env (NonRec _ r) = ruleCheck env r
1217 ruleCheckBind env (Rec prs) = unionManyBags [ruleCheck env r | (_,r) <- prs]
1218
1219 ruleCheck :: RuleCheckEnv -> CoreExpr -> Bag SDoc
1220 ruleCheck _ (Var _) = emptyBag
1221 ruleCheck _ (Lit _) = emptyBag
1222 ruleCheck _ (Type _) = emptyBag
1223 ruleCheck _ (Coercion _) = emptyBag
1224 ruleCheck env (App f a) = ruleCheckApp env (App f a) []
1225 ruleCheck env (Tick _ e) = ruleCheck env e
1226 ruleCheck env (Cast e _) = ruleCheck env e
1227 ruleCheck env (Let bd e) = ruleCheckBind env bd `unionBags` ruleCheck env e
1228 ruleCheck env (Lam _ e) = ruleCheck env e
1229 ruleCheck env (Case e _ _ as) = ruleCheck env e `unionBags`
1230 unionManyBags [ruleCheck env r | Alt _ _ r <- as]
1231
1232 ruleCheckApp :: RuleCheckEnv -> Expr CoreBndr -> [Arg CoreBndr] -> Bag SDoc
1233 ruleCheckApp env (App f a) as = ruleCheck env a `unionBags` ruleCheckApp env f (a:as)
1234 ruleCheckApp env (Var f) as = ruleCheckFun env f as
1235 ruleCheckApp env other _ = ruleCheck env other
1236
1237 ruleCheckFun :: RuleCheckEnv -> Id -> [CoreExpr] -> Bag SDoc
1238 -- Produce a report for all rules matching the predicate
1239 -- saying why it doesn't match the specified application
1240
1241 ruleCheckFun env fn args
1242 | null name_match_rules = emptyBag
1243 | otherwise = unitBag (ruleAppCheck_help env fn args name_match_rules)
1244 where
1245 name_match_rules = filter match (rc_rules env fn)
1246 match rule = (rc_pattern env) `isPrefixOf` unpackFS (ruleName rule)
1247
1248 ruleAppCheck_help :: RuleCheckEnv -> Id -> [CoreExpr] -> [CoreRule] -> SDoc
1249 ruleAppCheck_help env fn args rules
1250 = -- The rules match the pattern, so we want to print something
1251 vcat [text "Expression:" <+> ppr (mkApps (Var fn) args),
1252 vcat (map check_rule rules)]
1253 where
1254 n_args = length args
1255 i_args = args `zip` [1::Int ..]
1256 rough_args = map roughTopName args
1257
1258 check_rule rule = rule_herald rule <> colon <+> rule_info (rc_ropts env) rule
1259
1260 rule_herald (BuiltinRule { ru_name = name })
1261 = text "Builtin rule" <+> doubleQuotes (ftext name)
1262 rule_herald (Rule { ru_name = name })
1263 = text "Rule" <+> doubleQuotes (ftext name)
1264
1265 rule_info opts rule
1266 | Just _ <- matchRule opts (emptyInScopeSet, rc_id_unf env)
1267 noBlackList fn args rough_args rule
1268 = text "matches (which is very peculiar!)"
1269
1270 rule_info _ (BuiltinRule {}) = text "does not match"
1271
1272 rule_info _ (Rule { ru_act = act,
1273 ru_bndrs = rule_bndrs, ru_args = rule_args})
1274 | not (rc_is_active env act) = text "active only in later phase"
1275 | n_args < n_rule_args = text "too few arguments"
1276 | n_mismatches == n_rule_args = text "no arguments match"
1277 | n_mismatches == 0 = text "all arguments match (considered individually), but rule as a whole does not"
1278 | otherwise = text "arguments" <+> ppr mismatches <+> text "do not match (1-indexing)"
1279 where
1280 n_rule_args = length rule_args
1281 n_mismatches = length mismatches
1282 mismatches = [i | (rule_arg, (arg,i)) <- rule_args `zip` i_args,
1283 not (isJust (match_fn rule_arg arg))]
1284
1285 lhs_fvs = exprsFreeVars rule_args -- Includes template tyvars
1286 match_fn rule_arg arg = match renv emptyRuleSubst rule_arg arg
1287 where
1288 in_scope = mkInScopeSet (lhs_fvs `unionVarSet` exprFreeVars arg)
1289 renv = RV { rv_lcl = mkRnEnv2 in_scope
1290 , rv_tmpls = mkVarSet rule_bndrs
1291 , rv_fltR = mkEmptySubst in_scope
1292 , rv_unf = rc_id_unf env }