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