Minor fix to Note [Trimming arity]
[ghc.git] / compiler / simplCore / CallArity.hs
1 --
2 -- Copyright (c) 2014 Joachim Breitner
3 --
4
5 module CallArity
6 ( callArityAnalProgram
7 , callArityRHS -- for testing
8 ) where
9
10 import VarSet
11 import VarEnv
12 import DynFlags ( DynFlags )
13
14 import BasicTypes
15 import CoreSyn
16 import Id
17 import CoreArity ( typeArity )
18 import CoreUtils ( exprIsHNF )
19 --import Outputable
20 import UnVarGraph
21 import Demand
22
23 import Control.Arrow ( first, second )
24
25
26 {-
27 %************************************************************************
28 %* *
29 Call Arity Analyis
30 %* *
31 %************************************************************************
32
33 Note [Call Arity: The goal]
34 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
35
36 The goal of this analysis is to find out if we can eta-expand a local function,
37 based on how it is being called. The motivating example is this code,
38 which comes up when we implement foldl using foldr, and do list fusion:
39
40 let go = \x -> let d = case ... of
41 False -> go (x+1)
42 True -> id
43 in \z -> d (x + z)
44 in go 1 0
45
46 If we do not eta-expand `go` to have arity 2, we are going to allocate a lot of
47 partial function applications, which would be bad.
48
49 The function `go` has a type of arity two, but only one lambda is manifest.
50 Furthermore, an analysis that only looks at the RHS of go cannot be sufficient
51 to eta-expand go: If `go` is ever called with one argument (and the result used
52 multiple times), we would be doing the work in `...` multiple times.
53
54 So `callArityAnalProgram` looks at the whole let expression to figure out if
55 all calls are nice, i.e. have a high enough arity. It then stores the result in
56 the `calledArity` field of the `IdInfo` of `go`, which the next simplifier
57 phase will eta-expand.
58
59 The specification of the `calledArity` field is:
60
61 No work will be lost if you eta-expand me to the arity in `calledArity`.
62
63 What we want to know for a variable
64 -----------------------------------
65
66 For every let-bound variable we'd like to know:
67 1. A lower bound on the arity of all calls to the variable, and
68 2. whether the variable is being called at most once or possible multiple
69 times.
70
71 It is always ok to lower the arity, or pretend that there are multiple calls.
72 In particular, "Minimum arity 0 and possible called multiple times" is always
73 correct.
74
75
76 What we want to know from an expression
77 ---------------------------------------
78
79 In order to obtain that information for variables, we analyize expression and
80 obtain bits of information:
81
82 I. The arity analysis:
83 For every variable, whether it is absent, or called,
84 and if called, which what arity.
85
86 II. The Co-Called analysis:
87 For every two variables, whether there is a possibility that both are being
88 called.
89 We obtain as a special case: For every variables, whether there is a
90 possibility that it is being called twice.
91
92 For efficiency reasons, we gather this information only for a set of
93 *interesting variables*, to avoid spending time on, e.g., variables from pattern matches.
94
95 The two analysis are not completely independent, as a higher arity can improve
96 the information about what variables are being called once or multiple times.
97
98 Note [Analysis I: The arity analyis]
99 ------------------------------------
100
101 The arity analysis is quite straight forward: The information about an
102 expression is an
103 VarEnv Arity
104 where absent variables are bound to Nothing and otherwise to a lower bound to
105 their arity.
106
107 When we analyize an expression, we analyize it with a given context arity.
108 Lambdas decrease and applications increase the incoming arity. Analysizing a
109 variable will put that arity in the environment. In lets or cases all the
110 results from the various subexpressions are lubed, which takes the point-wise
111 minimum (considering Nothing an infinity).
112
113
114 Note [Analysis II: The Co-Called analysis]
115 ------------------------------------------
116
117 The second part is more sophisticated. For reasons explained below, it is not
118 sufficient to simply know how often an expression evalutes a variable. Instead
119 we need to know which variables are possibly called together.
120
121 The data structure here is an undirected graph of variables, which is provided
122 by the abstract
123 UnVarGraph
124
125 It is safe to return a larger graph, i.e. one with more edges. The worst case
126 (i.e. the least useful and always correct result) is the complete graph on all
127 free variables, which means that anything can be called together with anything
128 (including itself).
129
130 Notation for the following:
131 C(e) is the co-called result for e.
132 G₁∪G₂ is the union of two graphs
133 fv is the set of free variables (conveniently the domain of the arity analysis result)
134 S₁×S₂ is the complete bipartite graph { {a,b} | a ∈ S₁, b ∈ S₂ }
135 S² is the complete graph on the set of variables S, S² = S×S
136 C'(e) is a variant for bound expression:
137 If e is called at most once, or it is and stays a thunk (after the analysis),
138 it is simply C(e). Otherwise, the expression can be called multiple times
139 and we return (fv e)²
140
141 The interesting cases of the analysis:
142 * Var v:
143 No other variables are being called.
144 Return {} (the empty graph)
145 * Lambda v e, under arity 0:
146 This means that e can be evaluated many times and we cannot get
147 any useful co-call information.
148 Return (fv e)²
149 * Case alternatives alt₁,alt₂,...:
150 Only one can be execuded, so
151 Return (alt₁ ∪ alt₂ ∪...)
152 * App e₁ e₂ (and analogously Case scrut alts):
153 We get the results from both sides. Additionally, anything called by e₁ can
154 possibly be called with anything from e₂.
155 Return: C(e₁) ∪ C(e₂) ∪ (fv e₁) × (fv e₂)
156 * Let v = rhs in body:
157 In addition to the results from the subexpressions, add all co-calls from
158 everything that the body calls together with v to everthing that is called
159 by v.
160 Return: C'(rhs) ∪ C(body) ∪ (fv rhs) × {v'| {v,v'} ∈ C(body)}
161 * Letrec v₁ = rhs₁ ... vₙ = rhsₙ in body
162 Tricky.
163 We assume that it is really mutually recursive, i.e. that every variable
164 calls one of the others, and that this is strongly connected (otherwise we
165 return an over-approximation, so that's ok), see note [Recursion and fixpointing].
166
167 Let V = {v₁,...vₙ}.
168 Assume that the vs have been analysed with an incoming demand and
169 cardinality consistent with the final result (this is the fixed-pointing).
170 Again we can use the results from all subexpressions.
171 In addition, for every variable vᵢ, we need to find out what it is called
172 with (call this set Sᵢ). There are two cases:
173 * If vᵢ is a function, we need to go through all right-hand-sides and bodies,
174 and collect every variable that is called together with any variable from V:
175 Sᵢ = {v' | j ∈ {1,...,n}, {v',vⱼ} ∈ C'(rhs₁) ∪ ... ∪ C'(rhsₙ) ∪ C(body) }
176 * If vᵢ is a thunk, then its rhs is evaluated only once, so we need to
177 exclude it from this set:
178 Sᵢ = {v' | j ∈ {1,...,n}, j≠i, {v',vⱼ} ∈ C'(rhs₁) ∪ ... ∪ C'(rhsₙ) ∪ C(body) }
179 Finally, combine all this:
180 Return: C(body) ∪
181 C'(rhs₁) ∪ ... ∪ C'(rhsₙ) ∪
182 (fv rhs₁) × S₁) ∪ ... ∪ (fv rhsₙ) × Sₙ)
183
184 Using the result: Eta-Expansion
185 -------------------------------
186
187 We use the result of these two analyses to decide whether we can eta-expand the
188 rhs of a let-bound variable.
189
190 If the variable is already a function (exprIsHNF), and all calls to the
191 variables have a higher arity than the current manifest arity (i.e. the number
192 of lambdas), expand.
193
194 If the variable is a thunk we must be careful: Eta-Expansion will prevent
195 sharing of work, so this is only safe if there is at most one call to the
196 function. Therefore, we check whether {v,v} ∈ G.
197
198 Example:
199
200 let n = case .. of .. -- A thunk!
201 in n 0 + n 1
202
203 vs.
204
205 let n = case .. of ..
206 in case .. of T -> n 0
207 F -> n 1
208
209 We are only allowed to eta-expand `n` if it is going to be called at most
210 once in the body of the outer let. So we need to know, for each variable
211 individually, that it is going to be called at most once.
212
213
214 Why the co-call graph?
215 ----------------------
216
217 Why is it not sufficient to simply remember which variables are called once and
218 which are called multiple times? It would be in the previous example, but consider
219
220 let n = case .. of ..
221 in case .. of
222 True -> let go = \y -> case .. of
223 True -> go (y + n 1)
224 False > n
225 in go 1
226 False -> n
227
228 vs.
229
230 let n = case .. of ..
231 in case .. of
232 True -> let go = \y -> case .. of
233 True -> go (y+1)
234 False > n
235 in go 1
236 False -> n
237
238 In both cases, the body and the rhs of the inner let call n at most once.
239 But only in the second case that holds for the whole expression! The
240 crucial difference is that in the first case, the rhs of `go` can call
241 *both* `go` and `n`, and hence can call `n` multiple times as it recurses,
242 while in the second case find out that `go` and `n` are not called together.
243
244
245 Why co-call information for functions?
246 --------------------------------------
247
248 Although for eta-expansion we need the information only for thunks, we still
249 need to know whether functions are being called once or multiple times, and
250 together with what other functions.
251
252 Example:
253
254 let n = case .. of ..
255 f x = n (x+1)
256 in f 1 + f 2
257
258 vs.
259
260 let n = case .. of ..
261 f x = n (x+1)
262 in case .. of T -> f 0
263 F -> f 1
264
265 Here, the body of f calls n exactly once, but f itself is being called
266 multiple times, so eta-expansion is not allowed.
267
268
269 Note [Analysis type signature]
270 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
271
272 The work-hourse of the analysis is the function `callArityAnal`, with the
273 following type:
274
275 type CallArityRes = (UnVarGraph, VarEnv Arity)
276 callArityAnal ::
277 Arity -> -- The arity this expression is called with
278 VarSet -> -- The set of interesting variables
279 CoreExpr -> -- The expression to analyse
280 (CallArityRes, CoreExpr)
281
282 and the following specification:
283
284 ((coCalls, callArityEnv), expr') = callArityEnv arity interestingIds expr
285
286 <=>
287
288 Assume the expression `expr` is being passed `arity` arguments. Then it holds that
289 * The domain of `callArityEnv` is a subset of `interestingIds`.
290 * Any variable from `interestingIds` that is not mentioned in the `callArityEnv`
291 is absent, i.e. not called at all.
292 * Every call from `expr` to a variable bound to n in `callArityEnv` has at
293 least n value arguments.
294 * For two interesting variables `v1` and `v2`, they are not adjacent in `coCalls`,
295 then in no execution of `expr` both are being called.
296 Furthermore, expr' is expr with the callArity field of the `IdInfo` updated.
297
298
299 Note [Which variables are interesting]
300 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
301
302 The analysis would quickly become prohibitive expensive if we would analyse all
303 variables; for most variables we simply do not care about how often they are
304 called, i.e. variables bound in a pattern match. So interesting are variables that are
305 * top-level or let bound
306 * and possibly functions (typeArity > 0)
307
308 Note [Information about boring variables]
309 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
310
311 If we decide that the variable bound in `let x = e1 in e2` is not interesting,
312 the analysis of `e2` will not report anything about `x`. To ensure that
313 `callArityBind` does still do the right thing we have to extend the result from
314 `e2` with a safe approximation.
315
316 This is done using `fakeBoringCalls` and has the effect of analysing
317 x `seq` x `seq` e2
318 instead, i.e. with `both` the result from `e2` with the most conservative
319 result about the uninteresting value.
320
321 Note [Recursion and fixpointing]
322 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
323
324 For a mutually recursive let, we begin by
325 1. analysing the body, using the same incoming arity as for the whole expression.
326 2. Then we iterate, memoizing for each of the bound variables the last
327 analysis call, i.e. incoming arity, whether it is called once, and the CallArityRes.
328 3. We combine the analysis result from the body and the memoized results for
329 the arguments (if already present).
330 4. For each variable, we find out the incoming arity and whether it is called
331 once, based on the the current analysis result. If this differs from the
332 memoized results, we re-analyse the rhs and update the memoized table.
333 5. If nothing had to be reanalized, we are done.
334 Otherwise, repeat from step 3.
335
336
337 Note [Thunks in recursive groups]
338 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
339
340 We never eta-expand a thunk in a recursive group, on the grounds that if it is
341 part of a recursive group, then it will be called multipe times.
342
343 This is not necessarily true, e.g. it would be safe to eta-expand t2 (but not
344 t1) in the follwing code:
345
346 let go x = t1
347 t1 = if ... then t2 else ...
348 t2 = if ... then go 1 else ...
349 in go 0
350
351 Detecting this would require finding out what variables are only ever called
352 from thunks. While this is certainly possible, we yet have to see this to be
353 relevant in the wild.
354
355
356 Note [Analysing top-level binds]
357 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
358
359 We can eta-expand top-level-binds if they are not exported, as we see all calls
360 to them. The plan is as follows: Treat the top-level binds as nested lets around
361 a body representing “all external calls”, which returns a pessimistic
362 CallArityRes (the co-call graph is the complete graph, all arityies 0).
363
364 Note [Trimming arity]
365 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
366
367 In the Call Arity papers, we are working on an untyped lambda calculus with no
368 other id annotations, where eta-expansion is always possible. But this is not
369 the case for Core!
370 1. We need to ensure the invariant
371 callArity e <= typeArity (exprType e)
372 for the same reasons that exprArity needs this invariant (see Note
373 [exprArity invariant] in CoreArity).
374
375 If we are not doing that, a too-high arity annotation will be stored with
376 the id, confusing the simplifier later on.
377
378 2. Eta-expanding a right hand side might invalidate existing annotations. In
379 particular, if an id has a strictness annotation of <...><...>b, then
380 passing two arguments to it will definitely bottom out, so the simplifier
381 will throw away additional parameters. This conflicts with Call Arity! So
382 we ensure that we never eta-expand such a value beyond the number of
383 arguments mentioned in the strictness signature.
384 See #10176 for a real-world-example.
385
386 -}
387
388 -- Main entry point
389
390 callArityAnalProgram :: DynFlags -> CoreProgram -> CoreProgram
391 callArityAnalProgram _dflags binds = binds'
392 where
393 (_, binds') = callArityTopLvl [] emptyVarSet binds
394
395 -- See Note [Analysing top-level-binds]
396 callArityTopLvl :: [Var] -> VarSet -> [CoreBind] -> (CallArityRes, [CoreBind])
397 callArityTopLvl exported _ []
398 = ( calledMultipleTimes $ (emptyUnVarGraph, mkVarEnv $ [(v, 0) | v <- exported])
399 , [] )
400 callArityTopLvl exported int1 (b:bs)
401 = (ae2, b':bs')
402 where
403 int2 = bindersOf b
404 exported' = filter isExportedId int2 ++ exported
405 int' = int1 `addInterestingBinds` b
406 (ae1, bs') = callArityTopLvl exported' int' bs
407 ae1' = fakeBoringCalls int' b ae1 -- See Note [Information about boring variables]
408 (ae2, b') = callArityBind ae1' int1 b
409
410
411 callArityRHS :: CoreExpr -> CoreExpr
412 callArityRHS = snd . callArityAnal 0 emptyVarSet
413
414 -- The main analysis function. See Note [Analysis type signature]
415 callArityAnal ::
416 Arity -> -- The arity this expression is called with
417 VarSet -> -- The set of interesting variables
418 CoreExpr -> -- The expression to analyse
419 (CallArityRes, CoreExpr)
420 -- How this expression uses its interesting variables
421 -- and the expression with IdInfo updated
422
423 -- The trivial base cases
424 callArityAnal _ _ e@(Lit _)
425 = (emptyArityRes, e)
426 callArityAnal _ _ e@(Type _)
427 = (emptyArityRes, e)
428 callArityAnal _ _ e@(Coercion _)
429 = (emptyArityRes, e)
430 -- The transparent cases
431 callArityAnal arity int (Tick t e)
432 = second (Tick t) $ callArityAnal arity int e
433 callArityAnal arity int (Cast e co)
434 = second (\e -> Cast e co) $ callArityAnal arity int e
435
436 -- The interesting case: Variables, Lambdas, Lets, Applications, Cases
437 callArityAnal arity int e@(Var v)
438 | v `elemVarSet` int
439 = (unitArityRes v arity, e)
440 | otherwise
441 = (emptyArityRes, e)
442
443 -- Non-value lambdas are ignored
444 callArityAnal arity int (Lam v e) | not (isId v)
445 = second (Lam v) $ callArityAnal arity (int `delVarSet` v) e
446
447 -- We have a lambda that may be called multiple times, so its free variables
448 -- can all be co-called.
449 callArityAnal 0 int (Lam v e)
450 = (ae', Lam v e')
451 where
452 (ae, e') = callArityAnal 0 (int `delVarSet` v) e
453 ae' = calledMultipleTimes ae
454 -- We have a lambda that we are calling. decrease arity.
455 callArityAnal arity int (Lam v e)
456 = (ae, Lam v e')
457 where
458 (ae, e') = callArityAnal (arity - 1) (int `delVarSet` v) e
459
460 -- Application. Increase arity for the called expresion, nothing to know about
461 -- the second
462 callArityAnal arity int (App e (Type t))
463 = second (\e -> App e (Type t)) $ callArityAnal arity int e
464 callArityAnal arity int (App e1 e2)
465 = (final_ae, App e1' e2')
466 where
467 (ae1, e1') = callArityAnal (arity + 1) int e1
468 (ae2, e2') = callArityAnal 0 int e2
469 final_ae = ae1 `both` ae2
470
471 -- Case expression.
472 callArityAnal arity int (Case scrut bndr ty alts)
473 = -- pprTrace "callArityAnal:Case"
474 -- (vcat [ppr scrut, ppr final_ae])
475 (final_ae, Case scrut' bndr ty alts')
476 where
477 (alt_aes, alts') = unzip $ map go alts
478 go (dc, bndrs, e) = let (ae, e') = callArityAnal arity int e
479 in (ae, (dc, bndrs, e'))
480 alt_ae = lubRess alt_aes
481 (scrut_ae, scrut') = callArityAnal 0 int scrut
482 final_ae = scrut_ae `both` alt_ae
483
484 -- For lets, use callArityBind
485 callArityAnal arity int (Let bind e)
486 = -- pprTrace "callArityAnal:Let"
487 -- (vcat [ppr v, ppr arity, ppr n, ppr final_ae ])
488 (final_ae, Let bind' e')
489 where
490 int_body = int `addInterestingBinds` bind
491 (ae_body, e') = callArityAnal arity int_body e
492 ae_body' = fakeBoringCalls int_body bind ae_body -- See Note [Information about boring variables]
493 (final_ae, bind') = callArityBind ae_body' int bind
494
495 -- Which bindings should we look at?
496 -- See Note [Which variables are interesting]
497 interestingBinds :: CoreBind -> [Var]
498 interestingBinds = filter go . bindersOf
499 where go v = 0 < length (typeArity (idType v))
500
501 addInterestingBinds :: VarSet -> CoreBind -> VarSet
502 addInterestingBinds int bind
503 = int `delVarSetList` bindersOf bind -- Possible shadowing
504 `extendVarSetList` interestingBinds bind
505
506 -- For every boring variable in the binder, add a safe approximation
507 -- See Note [Information about boring variables]
508 fakeBoringCalls :: VarSet -> CoreBind -> CallArityRes -> CallArityRes
509 fakeBoringCalls int bind res = boring `both` res
510 where
511 boring = calledMultipleTimes $
512 ( emptyUnVarGraph
513 , mkVarEnv [ (v, 0) | v <- bindersOf bind, not (v `elemVarSet` int)])
514
515
516 -- Used for both local and top-level binds
517 -- First argument is the demand from the body
518 callArityBind :: CallArityRes -> VarSet -> CoreBind -> (CallArityRes, CoreBind)
519 -- Non-recursive let
520 callArityBind ae_body int (NonRec v rhs)
521 | otherwise
522 = -- pprTrace "callArityBind:NonRec"
523 -- (vcat [ppr v, ppr ae_body, ppr int, ppr ae_rhs, ppr safe_arity])
524 (final_ae, NonRec v' rhs')
525 where
526 is_thunk = not (exprIsHNF rhs)
527
528 (arity, called_once) = lookupCallArityRes ae_body v
529 safe_arity | called_once = arity
530 | is_thunk = 0 -- A thunk! Do not eta-expand
531 | otherwise = arity
532
533 -- See Note [Trimming arity]
534 trimmed_arity = trimArity v safe_arity
535
536 (ae_rhs, rhs') = callArityAnal trimmed_arity int rhs
537
538
539 ae_rhs'| called_once = ae_rhs
540 | safe_arity == 0 = ae_rhs -- If it is not a function, its body is evaluated only once
541 | otherwise = calledMultipleTimes ae_rhs
542
543 final_ae = callArityNonRecEnv v ae_rhs' ae_body
544 v' = v `setIdCallArity` trimmed_arity
545
546
547 -- Recursive let. See Note [Recursion and fixpointing]
548 callArityBind ae_body int b@(Rec binds)
549 = -- pprTrace "callArityBind:Rec"
550 -- (vcat [ppr (Rec binds'), ppr ae_body, ppr int, ppr ae_rhs]) $
551 (final_ae, Rec binds')
552 where
553 int_body = int `addInterestingBinds` b
554 (ae_rhs, binds') = fix initial_binds
555 final_ae = bindersOf b `resDelList` ae_rhs
556
557 initial_binds = [(i,Nothing,e) | (i,e) <- binds]
558
559 fix :: [(Id, Maybe (Bool, Arity, CallArityRes), CoreExpr)] -> (CallArityRes, [(Id, CoreExpr)])
560 fix ann_binds
561 | -- pprTrace "callArityBind:fix" (vcat [ppr ann_binds, ppr any_change, ppr ae]) $
562 any_change
563 = fix ann_binds'
564 | otherwise
565 = (ae, map (\(i, _, e) -> (i, e)) ann_binds')
566 where
567 aes_old = [ (i,ae) | (i, Just (_,_,ae), _) <- ann_binds ]
568 ae = callArityRecEnv aes_old ae_body
569
570 rerun (i, mbLastRun, rhs)
571 | i `elemVarSet` int_body && not (i `elemUnVarSet` domRes ae)
572 -- No call to this yet, so do nothing
573 = (False, (i, Nothing, rhs))
574
575 | Just (old_called_once, old_arity, _) <- mbLastRun
576 , called_once == old_called_once
577 , new_arity == old_arity
578 -- No change, no need to re-analize
579 = (False, (i, mbLastRun, rhs))
580
581 | otherwise
582 -- We previously analized this with a different arity (or not at all)
583 = let is_thunk = not (exprIsHNF rhs)
584
585 safe_arity | is_thunk = 0 -- See Note [Thunks in recursive groups]
586 | otherwise = new_arity
587
588 -- See Note [Trimming arity]
589 trimmed_arity = trimArity i safe_arity
590
591 (ae_rhs, rhs') = callArityAnal trimmed_arity int_body rhs
592
593 ae_rhs' | called_once = ae_rhs
594 | safe_arity == 0 = ae_rhs -- If it is not a function, its body is evaluated only once
595 | otherwise = calledMultipleTimes ae_rhs
596
597 in (True, (i `setIdCallArity` trimmed_arity, Just (called_once, new_arity, ae_rhs'), rhs'))
598 where
599 (new_arity, called_once) = lookupCallArityRes ae i
600
601 (changes, ann_binds') = unzip $ map rerun ann_binds
602 any_change = or changes
603
604 -- See Note [Trimming arity]
605 trimArity :: Id -> Arity -> Arity
606 trimArity v a = minimum [a, max_arity_by_type, max_arity_by_strsig]
607 where
608 max_arity_by_type = length (typeArity (idType v))
609 max_arity_by_strsig
610 | isBotRes result_info = length demands
611 | otherwise = a
612
613 (demands, result_info) = splitStrictSig (idStrictness v)
614
615 -- Combining the results from body and rhs, non-recursive case
616 -- See Note [Analysis II: The Co-Called analysis]
617 callArityNonRecEnv :: Var -> CallArityRes -> CallArityRes -> CallArityRes
618 callArityNonRecEnv v ae_rhs ae_body
619 = addCrossCoCalls called_by_v called_with_v $ ae_rhs `lubRes` resDel v ae_body
620 where
621 called_by_v = domRes ae_rhs
622 called_with_v = calledWith ae_body v `delUnVarSet` v
623
624 -- Combining the results from body and rhs, (mutually) recursive case
625 -- See Note [Analysis II: The Co-Called analysis]
626 callArityRecEnv :: [(Var, CallArityRes)] -> CallArityRes -> CallArityRes
627 callArityRecEnv ae_rhss ae_body
628 = -- pprTrace "callArityRecEnv" (vcat [ppr ae_rhss, ppr ae_body, ppr ae_new])
629 ae_new
630 where
631 vars = map fst ae_rhss
632
633 ae_combined = lubRess (map snd ae_rhss) `lubRes` ae_body
634
635 cross_calls = unionUnVarGraphs $ map cross_call ae_rhss
636 cross_call (v, ae_rhs) = completeBipartiteGraph called_by_v called_with_v
637 where
638 is_thunk = idCallArity v == 0
639 -- What rhs are relevant as happening before (or after) calling v?
640 -- If v is a thunk, everything from all the _other_ variables
641 -- If v is not a thunk, everything can happen.
642 ae_before_v | is_thunk = lubRess (map snd $ filter ((/= v) . fst) ae_rhss) `lubRes` ae_body
643 | otherwise = ae_combined
644 -- What do we want to know from these?
645 -- Which calls can happen next to any recursive call.
646 called_with_v
647 = unionUnVarSets $ map (calledWith ae_before_v) vars
648 called_by_v = domRes ae_rhs
649
650 ae_new = first (cross_calls `unionUnVarGraph`) ae_combined
651
652 ---------------------------------------
653 -- Functions related to CallArityRes --
654 ---------------------------------------
655
656 -- Result type for the two analyses.
657 -- See Note [Analysis I: The arity analyis]
658 -- and Note [Analysis II: The Co-Called analysis]
659 type CallArityRes = (UnVarGraph, VarEnv Arity)
660
661 emptyArityRes :: CallArityRes
662 emptyArityRes = (emptyUnVarGraph, emptyVarEnv)
663
664 unitArityRes :: Var -> Arity -> CallArityRes
665 unitArityRes v arity = (emptyUnVarGraph, unitVarEnv v arity)
666
667 resDelList :: [Var] -> CallArityRes -> CallArityRes
668 resDelList vs ae = foldr resDel ae vs
669
670 resDel :: Var -> CallArityRes -> CallArityRes
671 resDel v (g, ae) = (g `delNode` v, ae `delVarEnv` v)
672
673 domRes :: CallArityRes -> UnVarSet
674 domRes (_, ae) = varEnvDom ae
675
676 -- In the result, find out the minimum arity and whether the variable is called
677 -- at most once.
678 lookupCallArityRes :: CallArityRes -> Var -> (Arity, Bool)
679 lookupCallArityRes (g, ae) v
680 = case lookupVarEnv ae v of
681 Just a -> (a, not (v `elemUnVarSet` (neighbors g v)))
682 Nothing -> (0, False)
683
684 calledWith :: CallArityRes -> Var -> UnVarSet
685 calledWith (g, _) v = neighbors g v
686
687 addCrossCoCalls :: UnVarSet -> UnVarSet -> CallArityRes -> CallArityRes
688 addCrossCoCalls set1 set2 = first (completeBipartiteGraph set1 set2 `unionUnVarGraph`)
689
690 -- Replaces the co-call graph by a complete graph (i.e. no information)
691 calledMultipleTimes :: CallArityRes -> CallArityRes
692 calledMultipleTimes res = first (const (completeGraph (domRes res))) res
693
694 -- Used for application and cases
695 both :: CallArityRes -> CallArityRes -> CallArityRes
696 both r1 r2 = addCrossCoCalls (domRes r1) (domRes r2) $ r1 `lubRes` r2
697
698 -- Used when combining results from alternative cases; take the minimum
699 lubRes :: CallArityRes -> CallArityRes -> CallArityRes
700 lubRes (g1, ae1) (g2, ae2) = (g1 `unionUnVarGraph` g2, ae1 `lubArityEnv` ae2)
701
702 lubArityEnv :: VarEnv Arity -> VarEnv Arity -> VarEnv Arity
703 lubArityEnv = plusVarEnv_C min
704
705 lubRess :: [CallArityRes] -> CallArityRes
706 lubRess = foldl lubRes emptyArityRes