never executed always true always false
1 {-
2 (c) Bartosz Nitka, Facebook 2015
3
4 -}
5
6 {-# LANGUAGE BangPatterns #-}
7
8 -- | Utilities for efficiently and deterministically computing free variables.
9 module GHC.Utils.FV (
10 -- * Deterministic free vars computations
11 FV, InterestingVarFun,
12
13 -- * Running the computations
14 fvVarList, fvVarSet, fvDVarSet,
15
16 -- ** Manipulating those computations
17 unitFV,
18 emptyFV,
19 mkFVs,
20 unionFV,
21 unionsFV,
22 delFV,
23 delFVs,
24 filterFV,
25 mapUnionFV,
26 ) where
27
28 import GHC.Prelude
29
30 import GHC.Types.Var
31 import GHC.Types.Var.Set
32
33 -- | Predicate on possible free variables: returns @True@ iff the variable is
34 -- interesting
35 type InterestingVarFun = Var -> Bool
36
37 -- Note [Deterministic FV]
38 -- ~~~~~~~~~~~~~~~~~~~~~~~
39 -- When computing free variables, the order in which you get them affects
40 -- the results of floating and specialization. If you use UniqFM to collect
41 -- them and then turn that into a list, you get them in nondeterministic
42 -- order as described in Note [Deterministic UniqFM] in GHC.Types.Unique.DFM.
43
44 -- A naive algorithm for free variables relies on merging sets of variables.
45 -- Merging costs O(n+m) for UniqFM and for UniqDFM there's an additional log
46 -- factor. It's cheaper to incrementally add to a list and use a set to check
47 -- for duplicates.
48 type FV = InterestingVarFun -- Used for filtering sets as we build them
49 -> VarSet -- Locally bound variables
50 -> VarAcc -- Accumulator
51 -> VarAcc
52
53 type VarAcc = ([Var], VarSet) -- List to preserve ordering and set to check for membership,
54 -- so that the list doesn't have duplicates
55 -- For explanation of why using `VarSet` is not deterministic see
56 -- Note [Deterministic UniqFM] in GHC.Types.Unique.DFM.
57
58 -- Note [FV naming conventions]
59 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
60 -- To get the performance and determinism that FV provides, FV computations
61 -- need to built up from smaller FV computations and then evaluated with
62 -- one of `fvVarList`, `fvDVarSet` That means the functions
63 -- returning FV need to be exported.
64 --
65 -- The conventions are:
66 --
67 -- a) non-deterministic functions:
68 -- * a function that returns VarSet
69 -- e.g. `tyVarsOfType`
70 -- b) deterministic functions:
71 -- * a worker that returns FV
72 -- e.g. `tyFVsOfType`
73 -- * a function that returns [Var]
74 -- e.g. `tyVarsOfTypeList`
75 -- * a function that returns DVarSet
76 -- e.g. `tyVarsOfTypeDSet`
77 --
78 -- Where tyVarsOfType, tyVarsOfTypeList, tyVarsOfTypeDSet are implemented
79 -- in terms of the worker evaluated with fvVarSet, fvVarList, fvDVarSet
80 -- respectively.
81
82 -- | Run a free variable computation, returning a list of distinct free
83 -- variables in deterministic order and a non-deterministic set containing
84 -- those variables.
85 fvVarAcc :: FV -> ([Var], VarSet)
86 fvVarAcc fv = fv (const True) emptyVarSet ([], emptyVarSet)
87
88 -- | Run a free variable computation, returning a list of distinct free
89 -- variables in deterministic order.
90 fvVarList :: FV -> [Var]
91 fvVarList = fst . fvVarAcc
92
93 -- | Run a free variable computation, returning a deterministic set of free
94 -- variables. Note that this is just a wrapper around the version that
95 -- returns a deterministic list. If you need a list you should use
96 -- `fvVarList`.
97 fvDVarSet :: FV -> DVarSet
98 fvDVarSet = mkDVarSet . fvVarList
99
100 -- | Run a free variable computation, returning a non-deterministic set of
101 -- free variables. Don't use if the set will be later converted to a list
102 -- and the order of that list will impact the generated code.
103 fvVarSet :: FV -> VarSet
104 fvVarSet = snd . fvVarAcc
105
106 -- Note [FV eta expansion]
107 -- ~~~~~~~~~~~~~~~~~~~~~~~
108 -- Let's consider an eta-reduced implementation of freeVarsOf using FV:
109 --
110 -- freeVarsOf (App a b) = freeVarsOf a `unionFV` freeVarsOf b
111 --
112 -- If GHC doesn't eta-expand it, after inlining unionFV we end up with
113 --
114 -- freeVarsOf = \x ->
115 -- case x of
116 -- App a b -> \fv_cand in_scope acc ->
117 -- freeVarsOf a fv_cand in_scope $! freeVarsOf b fv_cand in_scope $! acc
118 --
119 -- which has to create a thunk, resulting in more allocations.
120 --
121 -- On the other hand if it is eta-expanded:
122 --
123 -- freeVarsOf (App a b) fv_cand in_scope acc =
124 -- (freeVarsOf a `unionFV` freeVarsOf b) fv_cand in_scope acc
125 --
126 -- after inlining unionFV we have:
127 --
128 -- freeVarsOf = \x fv_cand in_scope acc ->
129 -- case x of
130 -- App a b ->
131 -- freeVarsOf a fv_cand in_scope $! freeVarsOf b fv_cand in_scope $! acc
132 --
133 -- which saves allocations.
134 --
135 -- GHC when presented with knowledge about all the call sites, correctly
136 -- eta-expands in this case. Unfortunately due to the fact that freeVarsOf gets
137 -- exported to be composed with other functions, GHC doesn't have that
138 -- information and has to be more conservative here.
139 --
140 -- Hence functions that get exported and return FV need to be manually
141 -- eta-expanded. See also #11146.
142
143 -- | Add a variable - when free, to the returned free variables.
144 -- Ignores duplicates and respects the filtering function.
145 unitFV :: Id -> FV
146 unitFV var fv_cand in_scope acc@(have, haveSet)
147 | var `elemVarSet` in_scope = acc
148 | var `elemVarSet` haveSet = acc
149 | fv_cand var = (var:have, extendVarSet haveSet var)
150 | otherwise = acc
151 {-# INLINE unitFV #-}
152
153 -- | Return no free variables.
154 emptyFV :: FV
155 emptyFV _ _ acc = acc
156 {-# INLINE emptyFV #-}
157
158 -- | Union two free variable computations.
159 unionFV :: FV -> FV -> FV
160 unionFV fv1 fv2 fv_cand in_scope acc =
161 fv1 fv_cand in_scope $! fv2 fv_cand in_scope $! acc
162 {-# INLINE unionFV #-}
163
164 -- | Mark the variable as not free by putting it in scope.
165 delFV :: Var -> FV -> FV
166 delFV var fv fv_cand !in_scope acc =
167 fv fv_cand (extendVarSet in_scope var) acc
168 {-# INLINE delFV #-}
169
170 -- | Mark many free variables as not free.
171 delFVs :: VarSet -> FV -> FV
172 delFVs vars fv fv_cand !in_scope acc =
173 fv fv_cand (in_scope `unionVarSet` vars) acc
174 {-# INLINE delFVs #-}
175
176 -- | Filter a free variable computation.
177 filterFV :: InterestingVarFun -> FV -> FV
178 filterFV fv_cand2 fv fv_cand1 in_scope acc =
179 fv (\v -> fv_cand1 v && fv_cand2 v) in_scope acc
180 {-# INLINE filterFV #-}
181
182 -- | Map a free variable computation over a list and union the results.
183 mapUnionFV :: (a -> FV) -> [a] -> FV
184 mapUnionFV _f [] _fv_cand _in_scope acc = acc
185 mapUnionFV f (a:as) fv_cand in_scope acc =
186 mapUnionFV f as fv_cand in_scope $! f a fv_cand in_scope $! acc
187 {-# INLINABLE mapUnionFV #-}
188
189 -- | Union many free variable computations.
190 unionsFV :: [FV] -> FV
191 unionsFV fvs fv_cand in_scope acc = mapUnionFV id fvs fv_cand in_scope acc
192 {-# INLINE unionsFV #-}
193
194 -- | Add multiple variables - when free, to the returned free variables.
195 -- Ignores duplicates and respects the filtering function.
196 mkFVs :: [Var] -> FV
197 mkFVs vars fv_cand in_scope acc =
198 mapUnionFV unitFV vars fv_cand in_scope acc
199 {-# INLINE mkFVs #-}