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