compiler/coreSyn/CoreFVs.lhs

   1 %
   2 % (c) The University of Glasgow 2006
   3 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
   4 %
   5 Taken quite directly from the Peyton Jones/Lester paper.
   6
   7 \begin{code}
   8 {-# OPTIONS -fno-warn-incomplete-patterns #-}
   9 -- The above warning supression flag is a temporary kludge.
  10 -- While working on this module you are encouraged to remove it and fix
  11 -- any warnings in the module. See
  12 --     http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#Warnings
  13 -- for details
  14
  15 -- | A module concerned with finding the free variables of an expression.
  16 module CoreFVs (
  17         -- * Free variables of expressions and binding groups
  18         exprFreeVars,   -- CoreExpr   -> VarSet -- Find all locally-defined free Ids or tyvars
  19         exprFreeIds,    -- CoreExpr   -> IdSet  -- Find all locally-defined free Ids
  20         exprsFreeVars,  -- [CoreExpr] -> VarSet
  21         bindFreeVars,   -- CoreBind   -> VarSet
  22
  23         -- * Selective free variables of expressions
  24         InterestingVarFun,
  25         exprSomeFreeVars, exprsSomeFreeVars,
  26         exprFreeNames, exprsFreeNames,
  27
  28         -- * Free variables of Rules, Vars and Ids
  29         varTypeTyVars, varTypeTcTyVars,
  30         idUnfoldingVars, idFreeVars, idRuleAndUnfoldingVars,
  31         idRuleVars, idRuleRhsVars,
  32         ruleRhsFreeVars, rulesFreeVars,
  33         ruleLhsFreeNames, ruleLhsFreeIds,
  34
  35         -- * Core syntax tree annotation with free variables
  36         CoreExprWithFVs,        -- = AnnExpr Id VarSet
  37         CoreBindWithFVs,        -- = AnnBind Id VarSet
  38         freeVars,               -- CoreExpr -> CoreExprWithFVs
  39         freeVarsOf              -- CoreExprWithFVs -> IdSet
  40     ) where
  41
  42 #include "HsVersions.h"
  43
  44 import CoreSyn
  45 import Id
  46 import IdInfo
  47 import NameSet
  48 import UniqFM
  49 import Name
  50 import VarSet
  51 import Var
  52 import TcType
  53 import Util
  54 import Outputable
  55 \end{code}
  56
  57
  58 %************************************************************************
  59 %*                                                                      *
  60 \section{Finding the free variables of an expression}
  61 %*                                                                      *
  62 %************************************************************************
  63
  64 This function simply finds the free variables of an expression.
  65 So far as type variables are concerned, it only finds tyvars that are
  66
  67         * free in type arguments,
  68         * free in the type of a binder,
  69
  70 but not those that are free in the type of variable occurrence.
  71
  72 \begin{code}
  73 -- | Find all locally-defined free Ids or type variables in an expression
  74 exprFreeVars :: CoreExpr -> VarSet
  75 exprFreeVars = exprSomeFreeVars isLocalVar
  76
  77 -- | Find all locally-defined free Ids in an expression
  78 exprFreeIds :: CoreExpr -> IdSet        -- Find all locally-defined free Ids
  79 exprFreeIds = exprSomeFreeVars isLocalId
  80
  81 -- | Find all locally-defined free Ids or type variables in several expressions
  82 exprsFreeVars :: [CoreExpr] -> VarSet
  83 exprsFreeVars = foldr (unionVarSet . exprFreeVars) emptyVarSet
  84
  85 -- | Find all locally defined free Ids in a binding group
  86 bindFreeVars :: CoreBind -> VarSet
  87 bindFreeVars (NonRec _ r) = exprFreeVars r
  88 bindFreeVars (Rec prs)    = addBndrs (map fst prs)
  89                                      (foldr (union . rhs_fvs) noVars prs)
  90                                      isLocalVar emptyVarSet
  91
  92 -- | Finds free variables in an expression selected by a predicate
  93 exprSomeFreeVars :: InterestingVarFun   -- ^ Says which 'Var's are interesting
  94                  -> CoreExpr
  95                  -> VarSet
  96 exprSomeFreeVars fv_cand e = expr_fvs e fv_cand emptyVarSet
  97
  98 -- | Finds free variables in several expressions selected by a predicate
  99 exprsSomeFreeVars :: InterestingVarFun  -- Says which 'Var's are interesting
 100                   -> [CoreExpr]
 101                   -> VarSet
 102 exprsSomeFreeVars fv_cand = foldr (unionVarSet . exprSomeFreeVars fv_cand) emptyVarSet
 103
 104 -- | Predicate on possible free variables: returns @True@ iff the variable is interesting
 105 type InterestingVarFun = Var -> Bool
 106 \end{code}
 107
 108
 109 \begin{code}
 110 type FV = InterestingVarFun
 111         -> VarSet               -- In scope
 112         -> VarSet               -- Free vars
 113
 114 union :: FV -> FV -> FV
 115 union fv1 fv2 fv_cand in_scope = fv1 fv_cand in_scope `unionVarSet` fv2 fv_cand in_scope
 116
 117 noVars :: FV
 118 noVars _ _ = emptyVarSet
 119
 120 --      Comment about obselete code
 121 -- We used to gather the free variables the RULES at a variable occurrence
 122 -- with the following cryptic comment:
 123 --     "At a variable occurrence, add in any free variables of its rule rhss
 124 --     Curiously, we gather the Id's free *type* variables from its binding
 125 --     site, but its free *rule-rhs* variables from its usage sites.  This
 126 --     is a little weird.  The reason is that the former is more efficient,
 127 --     but the latter is more fine grained, and a makes a difference when
 128 --     a variable mentions itself one of its own rule RHSs"
 129 -- Not only is this "weird", but it's also pretty bad because it can make
 130 -- a function seem more recursive than it is.  Suppose
 131 --      f  = ...g...
 132 --      g  = ...
 133 --         RULE g x = ...f...
 134 -- Then f is not mentioned in its own RHS, and needn't be a loop breaker
 135 -- (though g may be).  But if we collect the rule fvs from g's occurrence,
 136 -- it looks as if f mentions itself.  (This bites in the eftInt/eftIntFB
 137 -- code in GHC.Enum.)
 138 --
 139 -- Anyway, it seems plain wrong.  The RULE is like an extra RHS for the
 140 -- function, so its free variables belong at the definition site.
 141 --
 142 -- Deleted code looked like
 143 --     foldVarSet add_rule_var var_itself_set (idRuleVars var)
 144 --     add_rule_var var set | keep_it fv_cand in_scope var = extendVarSet set var
 145 --                          | otherwise                    = set
 146 --      SLPJ Feb06
 147
 148 oneVar :: Id -> FV
 149 oneVar var fv_cand in_scope
 150   = ASSERT( isId var )
 151     if keep_it fv_cand in_scope var
 152     then unitVarSet var
 153     else emptyVarSet
 154
 155 someVars :: VarSet -> FV
 156 someVars vars fv_cand in_scope
 157   = filterVarSet (keep_it fv_cand in_scope) vars
 158
 159 keep_it :: InterestingVarFun -> VarSet -> Var -> Bool
 160 keep_it fv_cand in_scope var
 161   | var `elemVarSet` in_scope = False
 162   | fv_cand var               = True
 163   | otherwise                 = False
 164
 165
 166 addBndr :: CoreBndr -> FV -> FV
 167 addBndr bndr fv fv_cand in_scope
 168   = someVars (varTypeTyVars bndr) fv_cand in_scope
 169         -- Include type varibles in the binder's type
 170         --      (not just Ids; coercion variables too!)
 171     `unionVarSet`  fv fv_cand (in_scope `extendVarSet` bndr)
 172
 173 addBndrs :: [CoreBndr] -> FV -> FV
 174 addBndrs bndrs fv = foldr addBndr fv bndrs
 175 \end{code}
 176
 177
 178 \begin{code}
 179 expr_fvs :: CoreExpr -> FV
 180
 181 expr_fvs (Type ty)       = someVars (tyVarsOfType ty)
 182 expr_fvs (Var var)       = oneVar var
 183 expr_fvs (Lit _)         = noVars
 184 expr_fvs (Note _ expr)   = expr_fvs expr
 185 expr_fvs (App fun arg)   = expr_fvs fun `union` expr_fvs arg
 186 expr_fvs (Lam bndr body) = addBndr bndr (expr_fvs body)
 187 expr_fvs (Cast expr co)  = expr_fvs expr `union` someVars (tyVarsOfType co)
 188
 189 expr_fvs (Case scrut bndr ty alts)
 190   = expr_fvs scrut `union` someVars (tyVarsOfType ty) `union` addBndr bndr
 191       (foldr (union . alt_fvs) noVars alts)
 192   where
 193     alt_fvs (_, bndrs, rhs) = addBndrs bndrs (expr_fvs rhs)
 194
 195 expr_fvs (Let (NonRec bndr rhs) body)
 196   = rhs_fvs (bndr, rhs) `union` addBndr bndr (expr_fvs body)
 197
 198 expr_fvs (Let (Rec pairs) body)
 199   = addBndrs (map fst pairs)
 200              (foldr (union . rhs_fvs) (expr_fvs body) pairs)
 201
 202 ---------
 203 rhs_fvs :: (Id,CoreExpr) -> FV
 204 rhs_fvs (bndr, rhs) = expr_fvs rhs `union`
 205                       someVars (bndrRuleAndUnfoldingVars bndr)
 206         -- Treat any RULES as extra RHSs of the binding
 207
 208 ---------
 209 exprs_fvs :: [CoreExpr] -> FV
 210 exprs_fvs exprs = foldr (union . expr_fvs) noVars exprs
 211 \end{code}
 212
 213
 214 %************************************************************************
 215 %*                                                                      *
 216 \section{Free names}
 217 %*                                                                      *
 218 %************************************************************************
 219
 220 \begin{code}
 221 -- | Similar to 'exprFreeNames'. However, this is used when deciding whether
 222 -- a rule is an orphan.  In particular, suppose that T is defined in this
 223 -- module; we want to avoid declaring that a rule like:
 224 --
 225 -- > fromIntegral T = fromIntegral_T
 226 --
 227 -- is an orphan. Of course it isn't, and declaring it an orphan would
 228 -- make the whole module an orphan module, which is bad.
 229 ruleLhsFreeNames :: CoreRule -> NameSet
 230 ruleLhsFreeNames (BuiltinRule { ru_fn = fn }) = unitNameSet fn
 231 ruleLhsFreeNames (Rule { ru_fn = fn, ru_args = tpl_args })
 232   = addOneToNameSet (exprsFreeNames tpl_args) fn
 233
 234 -- | Finds the free /external/ names of an expression, notably
 235 -- including the names of type constructors (which of course do not show
 236 -- up in 'exprFreeVars').
 237 exprFreeNames :: CoreExpr -> NameSet
 238 -- There's no need to delete local binders, because they will all
 239 -- be /internal/ names.
 240 exprFreeNames e
 241   = go e
 242   where
 243     go (Var v)
 244       | isExternalName n    = unitNameSet n
 245       | otherwise           = emptyNameSet
 246       where n = idName v
 247     go (Lit _)              = emptyNameSet
 248     go (Type ty)            = tyClsNamesOfType ty       -- Don't need free tyvars
 249     go (App e1 e2)          = go e1 `unionNameSets` go e2
 250     go (Lam v e)            = go e `delFromNameSet` idName v
 251     go (Note _ e)           = go e
 252     go (Cast e co)          = go e `unionNameSets` tyClsNamesOfType co
 253     go (Let (NonRec _ r) e) = go e `unionNameSets` go r
 254     go (Let (Rec prs) e)    = exprsFreeNames (map snd prs) `unionNameSets` go e
 255     go (Case e _ ty as)     = go e `unionNameSets` tyClsNamesOfType ty
 256                               `unionNameSets` unionManyNameSets (map go_alt as)
 257
 258     go_alt (_,_,r) = go r
 259
 260 -- | Finds the free /external/ names of several expressions: see 'exprFreeNames' for details
 261 exprsFreeNames :: [CoreExpr] -> NameSet
 262 exprsFreeNames es = foldr (unionNameSets . exprFreeNames) emptyNameSet es
 263 \end{code}
 264
 265 %************************************************************************
 266 %*                                                                      *
 267 \section[freevars-everywhere]{Attaching free variables to every sub-expression}
 268 %*                                                                      *
 269 %************************************************************************
 270
 271 \begin{code}
 272 -- | Those variables free in the right hand side of a rule
 273 ruleRhsFreeVars :: CoreRule -> VarSet
 274 ruleRhsFreeVars (BuiltinRule {}) = noFVs
 275 ruleRhsFreeVars (Rule { ru_fn = fn, ru_bndrs = bndrs, ru_rhs = rhs })
 276   = delFromUFM fvs fn    -- Note [Rule free var hack]
 277   where
 278     fvs = addBndrs bndrs (expr_fvs rhs) isLocalVar emptyVarSet
 279
 280 -- | Those variables free in the both the left right hand sides of a rule
 281 ruleFreeVars :: CoreRule -> VarSet
 282 ruleFreeVars (BuiltinRule {}) = noFVs
 283 ruleFreeVars (Rule { ru_fn = fn, ru_bndrs = bndrs, ru_rhs = rhs, ru_args = args })
 284   = delFromUFM fvs fn   -- Note [Rule free var hack]
 285   where
 286     fvs = addBndrs bndrs (exprs_fvs (rhs:args)) isLocalVar emptyVarSet
 287
 288 -- | Those variables free in the right hand side of several rules
 289 rulesFreeVars :: [CoreRule] -> VarSet
 290 rulesFreeVars rules = foldr (unionVarSet . ruleFreeVars) emptyVarSet rules
 291
 292 ruleLhsFreeIds :: CoreRule -> VarSet
 293 -- ^ This finds all locally-defined free Ids on the left hand side of a rule
 294 ruleLhsFreeIds (BuiltinRule {}) = noFVs
 295 ruleLhsFreeIds (Rule { ru_bndrs = bndrs, ru_args = args })
 296   = addBndrs bndrs (exprs_fvs args) isLocalId emptyVarSet
 297 \end{code}
 298
 299 Note [Rule free var hack]
 300 ~~~~~~~~~~~~~~~~~~~~~~~~~
 301 Don't include the Id in its own rhs free-var set.
 302 Otherwise the occurrence analyser makes bindings recursive
 303 that shoudn't be.  E.g.
 304         RULE:  f (f x y) z  ==>  f x (f y z)
 305
 306 Also since rule_fn is a Name, not a Var, we have to use the grungy delUFM.
 307
 308 %************************************************************************
 309 %*                                                                      *
 310 \section[freevars-everywhere]{Attaching free variables to every sub-expression}
 311 %*                                                                      *
 312 %************************************************************************
 313
 314 The free variable pass annotates every node in the expression with its
 315 NON-GLOBAL free variables and type variables.
 316
 317 \begin{code}
 318 -- | Every node in a binding group annotated with its
 319 -- (non-global) free variables, both Ids and TyVars
 320 type CoreBindWithFVs = AnnBind Id VarSet
 321 -- | Every node in an expression annotated with its
 322 -- (non-global) free variables, both Ids and TyVars
 323 type CoreExprWithFVs = AnnExpr Id VarSet
 324
 325 freeVarsOf :: CoreExprWithFVs -> IdSet
 326 -- ^ Inverse function to 'freeVars'
 327 freeVarsOf (free_vars, _) = free_vars
 328
 329 noFVs :: VarSet
 330 noFVs    = emptyVarSet
 331
 332 aFreeVar :: Var -> VarSet
 333 aFreeVar = unitVarSet
 334
 335 unionFVs :: VarSet -> VarSet -> VarSet
 336 unionFVs = unionVarSet
 337
 338 delBindersFV :: [Var] -> VarSet -> VarSet
 339 delBindersFV bs fvs = foldr delBinderFV fvs bs
 340
 341 delBinderFV :: Var -> VarSet -> VarSet
 342 -- This way round, so we can do it multiple times using foldr
 343
 344 -- (b `delBinderFV` s) removes the binder b from the free variable set s,
 345 -- but *adds* to s
 346 --
 347 --      the free variables of b's type
 348 --
 349 -- This is really important for some lambdas:
 350 --      In (\x::a -> x) the only mention of "a" is in the binder.
 351 --
 352 -- Also in
 353 --      let x::a = b in ...
 354 -- we should really note that "a" is free in this expression.
 355 -- It'll be pinned inside the /\a by the binding for b, but
 356 -- it seems cleaner to make sure that a is in the free-var set
 357 -- when it is mentioned.
 358 --
 359 -- This also shows up in recursive bindings.  Consider:
 360 --      /\a -> letrec x::a = x in E
 361 -- Now, there are no explicit free type variables in the RHS of x,
 362 -- but nevertheless "a" is free in its definition.  So we add in
 363 -- the free tyvars of the types of the binders, and include these in the
 364 -- free vars of the group, attached to the top level of each RHS.
 365 --
 366 -- This actually happened in the defn of errorIO in IOBase.lhs:
 367 --      errorIO (ST io) = case (errorIO# io) of
 368 --                          _ -> bottom
 369 --                        where
 370 --                          bottom = bottom -- Never evaluated
 371
 372 delBinderFV b s = (s `delVarSet` b) `unionFVs` varTypeTyVars b
 373         -- Include coercion variables too!
 374
 375 varTypeTyVars :: Var -> TyVarSet
 376 -- Find the type variables free in the type of the variable
 377 -- Remember, coercion variables can mention type variables...
 378 varTypeTyVars var
 379   | isLocalId var || isCoVar var = tyVarsOfType (idType var)
 380   | otherwise = emptyVarSet     -- Global Ids and non-coercion TyVars
 381
 382 varTypeTcTyVars :: Var -> TyVarSet
 383 -- Find the type variables free in the type of the variable
 384 -- Remember, coercion variables can mention type variables...
 385 varTypeTcTyVars var
 386   | isLocalId var || isCoVar var = tcTyVarsOfType (idType var)
 387   | otherwise = emptyVarSet     -- Global Ids and non-coercion TyVars
 388
 389 idFreeVars :: Id -> VarSet
 390 -- Type variables, rule variables, and inline variables
 391 idFreeVars id = ASSERT( isId id)
 392                 varTypeTyVars id `unionVarSet`
 393                 idRuleAndUnfoldingVars id
 394
 395 bndrRuleAndUnfoldingVars ::Var -> VarSet
 396 -- A 'let' can bind a type variable, and idRuleVars assumes
 397 -- it's seeing an Id. This function tests first.
 398 bndrRuleAndUnfoldingVars v | isTyCoVar v = emptyVarSet
 399                            | otherwise = idRuleAndUnfoldingVars v
 400
 401 idRuleAndUnfoldingVars :: Id -> VarSet
 402 idRuleAndUnfoldingVars id = ASSERT( isId id)
 403                             idRuleVars id    `unionVarSet`
 404                             idUnfoldingVars id
 405
 406 idRuleVars ::Id -> VarSet  -- Does *not* include CoreUnfolding vars
 407 idRuleVars id = ASSERT( isId id) specInfoFreeVars (idSpecialisation id)
 408
 409 idRuleRhsVars :: Id -> VarSet    -- Does *not* include the CoreUnfolding vars
 410 -- Just the variables free on the *rhs* of a rule
 411 -- See Note [Choosing loop breakers] in Simplify.lhs
 412 idRuleRhsVars id = foldr (unionVarSet . ruleRhsFreeVars)
 413                          emptyVarSet
 414                          (idCoreRules id)
 415
 416 idUnfoldingVars :: Id -> VarSet
 417 -- Produce free vars for an unfolding, but NOT for an ordinary
 418 -- (non-inline) unfolding, since it is a dup of the rhs
 419 -- and we'll get exponential behaviour if we look at both unf and rhs!
 420 -- But do look at the *real* unfolding, even for loop breakers, else
 421 -- we might get out-of-scope variables
 422 idUnfoldingVars id
 423   = case realIdUnfolding id of
 424       CoreUnfolding { uf_tmpl = rhs, uf_src = src }
 425                              | isStableSource src
 426                              -> exprFreeVars rhs
 427       DFunUnfolding _ _ args -> exprsFreeVars args
 428       _                      -> emptyVarSet
 429 \end{code}
 430
 431
 432 %************************************************************************
 433 %*                                                                      *
 434 \subsection{Free variables (and types)}
 435 %*                                                                      *
 436 %************************************************************************
 437
 438 \begin{code}
 439 freeVars :: CoreExpr -> CoreExprWithFVs
 440 -- ^ Annotate a 'CoreExpr' with its (non-global) free type and value variables at every tree node
 441 freeVars (Var v)
 442   = (fvs, AnnVar v)
 443   where
 444         -- ToDo: insert motivating example for why we *need*
 445         -- to include the idSpecVars in the FV list.
 446         --      Actually [June 98] I don't think it's necessary
 447         -- fvs = fvs_v `unionVarSet` idSpecVars v
 448
 449     fvs | isLocalVar v = aFreeVar v
 450         | otherwise    = noFVs
 451
 452 freeVars (Lit lit) = (noFVs, AnnLit lit)
 453 freeVars (Lam b body)
 454   = (b `delBinderFV` freeVarsOf body', AnnLam b body')
 455   where
 456     body' = freeVars body
 457
 458 freeVars (App fun arg)
 459   = (freeVarsOf fun2 `unionFVs` freeVarsOf arg2, AnnApp fun2 arg2)
 460   where
 461     fun2 = freeVars fun
 462     arg2 = freeVars arg
 463
 464 freeVars (Case scrut bndr ty alts)
 465   = ((bndr `delBinderFV` alts_fvs) `unionFVs` freeVarsOf scrut2 `unionFVs` tyVarsOfType ty,
 466      AnnCase scrut2 bndr ty alts2)
 467   where
 468     scrut2 = freeVars scrut
 469
 470     (alts_fvs_s, alts2) = mapAndUnzip fv_alt alts
 471     alts_fvs            = foldr1 unionFVs alts_fvs_s
 472
 473     fv_alt (con,args,rhs) = (delBindersFV args (freeVarsOf rhs2),
 474                              (con, args, rhs2))
 475                           where
 476                              rhs2 = freeVars rhs
 477
 478 freeVars (Let (NonRec binder rhs) body)
 479   = (freeVarsOf rhs2
 480        `unionFVs` body_fvs
 481        `unionFVs` bndrRuleAndUnfoldingVars binder,
 482                 -- Remember any rules; cf rhs_fvs above
 483      AnnLet (AnnNonRec binder rhs2) body2)
 484   where
 485     rhs2     = freeVars rhs
 486     body2    = freeVars body
 487     body_fvs = binder `delBinderFV` freeVarsOf body2
 488
 489 freeVars (Let (Rec binds) body)
 490   = (delBindersFV binders all_fvs,
 491      AnnLet (AnnRec (binders `zip` rhss2)) body2)
 492   where
 493     (binders, rhss) = unzip binds
 494
 495     rhss2     = map freeVars rhss
 496     rhs_body_fvs = foldr (unionFVs . freeVarsOf) body_fvs rhss2
 497     all_fvs      = foldr (unionFVs . idRuleAndUnfoldingVars) rhs_body_fvs binders
 498         -- The "delBinderFV" happens after adding the idSpecVars,
 499         -- since the latter may add some of the binders as fvs
 500
 501     body2     = freeVars body
 502     body_fvs  = freeVarsOf body2
 503
 504
 505 freeVars (Cast expr co)
 506   = (freeVarsOf expr2 `unionFVs` cfvs, AnnCast expr2 co)
 507   where
 508     expr2 = freeVars expr
 509     cfvs  = tyVarsOfType co
 510
 511 freeVars (Note other_note expr)
 512   = (freeVarsOf expr2, AnnNote other_note expr2)
 513   where
 514     expr2 = freeVars expr
 515
 516 freeVars (Type ty) = (tyVarsOfType ty, AnnType ty)
 517 \end{code}
 518