1 --

2 -- Copyright (c) 2014 Joachim Breitner

3 --

5 module CallArity

6 ( callArityAnalProgram

10 import VarSet

11 import VarEnv

14 import BasicTypes

15 import CoreSyn

16 import Id

19 --import Outputable

20 import UnVarGraph

25 {-

26 %************************************************************************

27 %* *

28 Call Arity Analyis

29 %* *

30 %************************************************************************

32 Note [Call Arity: The goal]

33 ~~~~~~~~~~~~~~~~~~~~~~~~~~~

35 The goal of this analysis is to find out if we can eta-expand a local function,

36 based on how it is being called. The motivating example is code this this,

37 which comes up when we implement foldl using foldr, and do list fusion:

39 let go = \x -> let d = case ... of

40 False -> go (x+1)

41 True -> id

42 in \z -> d (x + z)

43 in go 1 0

45 If we do not eta-expand `go` to have arity 2, we are going to allocate a lot of

46 partial function applications, which would be bad.

48 The function `go` has a type of arity two, but only one lambda is manifest.

49 Further more, an analysis that only looks at the RHS of go cannot be sufficient

50 to eta-expand go: If `go` is ever called with one argument (and the result used

51 multiple times), we would be doing the work in `...` multiple times.

53 So `callArityAnalProgram` looks at the whole let expression to figure out if

54 all calls are nice, i.e. have a high enough arity. It then stores the result in

55 the `calledArity` field of the `IdInfo` of `go`, which the next simplifier

56 phase will eta-expand.

58 The specification of the `calledArity` field is:

60 No work will be lost if you eta-expand me to the arity in `calledArity`.

62 What we want to know for a variable

63 -----------------------------------

65 For every let-bound variable we'd like to know:

66 1. A lower bound on the arity of all calls to the variable, and

67 2. whether the variable is being called at most once or possible multiple

68 times.

70 It is always ok to lower the arity, or pretend that there are multiple calls.

71 In particular, "Minimum arity 0 and possible called multiple times" is always

72 correct.

75 What we want to know from an expression

76 ---------------------------------------

78 In order to obtain that information for variables, we analyize expression and

79 obtain bits of information:

81 I. The arity analysis:

82 For every variable, whether it is absent, or called,

83 and if called, which what arity.

85 II. The Co-Called analysis:

86 For every two variables, whether there is a possibility that both are being

87 called.

88 We obtain as a special case: For every variables, whether there is a

89 possibility that it is being called twice.

91 For efficiency reasons, we gather this information only for a set of

92 *interesting variables*, to avoid spending time on, e.g., variables from pattern matches.

94 The two analysis are not completely independent, as a higher arity can improve

95 the information about what variables are being called once or multiple times.

97 Note [Analysis I: The arity analyis]

98 ------------------------------------

100 The arity analysis is quite straight forward: The information about an

101 expression is an

102 VarEnv Arity

103 where absent variables are bound to Nothing and otherwise to a lower bound to

104 their arity.

106 When we analyize an expression, we analyize it with a given context arity.

107 Lambdas decrease and applications increase the incoming arity. Analysizing a

108 variable will put that arity in the environment. In lets or cases all the

109 results from the various subexpressions are lubed, which takes the point-wise

110 minimum (considering Nothing an infinity).

113 Note [Analysis II: The Co-Called analysis]

114 ------------------------------------------

116 The second part is more sophisticated. For reasons explained below, it is not

117 sufficient to simply know how often an expression evalutes a variable. Instead

118 we need to know which variables are possibly called together.

120 The data structure here is an undirected graph of variables, which is provided

121 by the abstract

122 UnVarGraph

124 It is safe to return a larger graph, i.e. one with more edges. The worst case

125 (i.e. the least useful and always correct result) is the complete graph on all

126 free variables, which means that anything can be called together with anything

127 (including itself).

129 Notation for the following:

130 C(e) is the co-called result for e.

131 G₁∪G₂ is the union of two graphs

132 fv is the set of free variables (conveniently the domain of the arity analysis result)

133 S₁×S₂ is the complete bipartite graph { {a,b} | a ∈ S₁, b ∈ S₂ }

134 S² is the complete graph on the set of variables S, S² = S×S

135 C'(e) is a variant for bound expression:

136 If e is called at most once, or it is and stays a thunk (after the analysis),

137 it is simply C(e). Otherwise, the expression can be called multiple times

138 and we return (fv e)²

140 The interesting cases of the analysis:

141 * Var v:

142 No other variables are being called.

143 Return {} (the empty graph)

144 * Lambda v e, under arity 0:

145 This means that e can be evaluated many times and we cannot get

146 any useful co-call information.

147 Return (fv e)²

148 * Case alternatives alt₁,alt₂,...:

149 Only one can be execuded, so

150 Return (alt₁ ∪ alt₂ ∪...)

151 * App e₁ e₂ (and analogously Case scrut alts):

152 We get the results from both sides. Additionally, anything called by e₁ can

153 possibly called with anything from e₂.

154 Return: C(e₁) ∪ C(e₂) ∪ (fv e₁) × (fv e₂)

155 * Let v = rhs in body:

156 In addition to the results from the subexpressions, add all co-calls from

157 everything that the body calls together with v to everthing that is called

158 by v.

159 Return: C'(rhs) ∪ C(body) ∪ (fv rhs) × {v'| {v,v'} ∈ C(body)}

160 * Letrec v₁ = rhs₁ ... vₙ = rhsₙ in body

161 Tricky.

162 We assume that it is really mutually recursive, i.e. that every variable

163 calls one of the others, and that this is strongly connected (otherwise we

164 return an over-approximation, so that's ok), see note [Recursion and fixpointing].

166 Let V = {v₁,...vₙ}.

167 Assume that the vs have been analysed with an incoming demand and

168 cardinality consistent with the final result (this is the fixed-pointing).

169 Again we can use the results from all subexpressions.

170 In addition, for every variable vᵢ, we need to find out what it is called

171 with (call this set Sᵢ). There are two cases:

172 * If vᵢ is a function, we need to go through all right-hand-sides and bodies,

173 and collect every variable that is called together with any variable from V:

174 Sᵢ = {v' | j ∈ {1,...,n}, {v',vⱼ} ∈ C'(rhs₁) ∪ ... ∪ C'(rhsₙ) ∪ C(body) }

175 * If vᵢ is a thunk, then its rhs is evaluated only once, so we need to

176 exclude it from this set:

177 Sᵢ = {v' | j ∈ {1,...,n}, j≠i, {v',vⱼ} ∈ C'(rhs₁) ∪ ... ∪ C'(rhsₙ) ∪ C(body) }

178 Finally, combine all this:

179 Return: C(body) ∪

180 C'(rhs₁) ∪ ... ∪ C'(rhsₙ) ∪

181 (fv rhs₁) × S₁) ∪ ... ∪ (fv rhsₙ) × Sₙ)

183 Using the result: Eta-Expansion

184 -------------------------------

186 We use the result of these two analyses to decide whether we can eta-expand the

187 rhs of a let-bound variable.

189 If the variable is already a function (exprIsHNF), and all calls to the

190 variables have a higher arity than the current manifest arity (i.e. the number

191 of lambdas), expand.

193 If the variable is a thunk we must be careful: Eta-Expansion will prevent

194 sharing of work, so this is only safe if there is at most one call to the

195 function. Therefore, we check whether {v,v} ∈ G.

197 Example:

199 let n = case .. of .. -- A thunk!

200 in n 0 + n 1

202 vs.

204 let n = case .. of ..

205 in case .. of T -> n 0

206 F -> n 1

208 We are only allowed to eta-expand `n` if it is going to be called at most

209 once in the body of the outer let. So we need to know, for each variable

210 individually, that it is going to be called at most once.

213 Why the co-call graph?

214 ----------------------

216 Why is it not sufficient to simply remember which variables are called once and

217 which are called multiple times? It would be in the previous example, but consider

219 let n = case .. of ..

220 in case .. of

221 True -> let go = \y -> case .. of

222 True -> go (y + n 1)

223 False > n

224 in go 1

225 False -> n

227 vs.

229 let n = case .. of ..

230 in case .. of

231 True -> let go = \y -> case .. of

232 True -> go (y+1)

233 False > n

234 in go 1

235 False -> n

237 In both cases, the body and the rhs of the inner let call n at most once.

238 But only in the second case that holds for the whole expression! The

239 crucial difference is that in the first case, the rhs of `go` can call

240 *both* `go` and `n`, and hence can call `n` multiple times as it recurses,

241 while in the second case find out that `go` and `n` are not called together.

244 Why co-call information for functions?

245 --------------------------------------

247 Although for eta-expansion we need the information only for thunks, we still

248 need to know whether functions are being called once or multiple times, and

249 together with what other functions.

251 Example:

253 let n = case .. of ..

254 f x = n (x+1)

255 in f 1 + f 2

257 vs.

259 let n = case .. of ..

260 f x = n (x+1)

261 in case .. of T -> f 0

262 F -> f 1

264 Here, the body of f calls n exactly once, but f itself is being called

265 multiple times, so eta-expansion is not allowed.

268 Note [Analysis type signature]

269 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

271 The work-hourse of the analysis is the function `callArityAnal`, with the

272 following type:

274 type CallArityRes = (UnVarGraph, VarEnv Arity)

275 callArityAnal ::

276 Arity -> -- The arity this expression is called with

277 VarSet -> -- The set of interesting variables

278 CoreExpr -> -- The expression to analyse

279 (CallArityRes, CoreExpr)

281 and the following specification:

283 ((coCalls, callArityEnv), expr') = callArityEnv arity interestingIds expr

285 <=>

287 Assume the expression `expr` is being passed `arity` arguments. Then it holds that

288 * The domain of `callArityEnv` is a subset of `interestingIds`.

289 * Any variable from `interestingIds` that is not mentioned in the `callArityEnv`

290 is absent, i.e. not called at all.

291 * Every call from `expr` to a variable bound to n in `callArityEnv` has at

292 least n value arguments.

293 * For two interesting variables `v1` and `v2`, they are not adjacent in `coCalls`,

294 then in no execution of `expr` both are being called.

295 Furthermore, expr' is expr with the callArity field of the `IdInfo` updated.

298 Note [Which variables are interesting]

299 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

301 The analysis would quickly become prohibitive expensive if we would analyse all

302 variables; for most variables we simply do not care about how often they are

303 called, i.e. variables bound in a pattern match. So interesting are variables that are

304 * top-level or let bound

305 * and possibly functions (typeArity > 0)

307 Note [Information about boring variables]

308 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

310 If we decide that the variable bound in `let x = e1 in e2` is not interesting,

311 the analysis of `e2` will not report anything about `x`. To ensure that

312 `callArityBind` does still do the right thing we have to extend the result from

313 `e2` with a safe approximation.

315 This is done using `fakeBoringCalls` and has the effect of analysing

316 x `seq` x `seq` e2

317 instead, i.e. with `both` the result from `e2` with the most conservative

318 result about the uninteresting value.

320 Note [Recursion and fixpointing]

321 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

323 For a mutually recursive let, we begin by

324 1. analysing the body, using the same incoming arity as for the whole expression.

325 2. Then we iterate, memoizing for each of the bound variables the last

326 analysis call, i.e. incoming arity, whether it is called once, and the CallArityRes.

327 3. We combine the analysis result from the body and the memoized results for

328 the arguments (if already present).

329 4. For each variable, we find out the incoming arity and whether it is called

330 once, based on the the current analysis result. If this differs from the

331 memoized results, we re-analyse the rhs and update the memoized table.

332 5. If nothing had to be reanalized, we are done.

333 Otherwise, repeat from step 3.

336 Note [Thunks in recursive groups]

337 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

339 We never eta-expand a thunk in a recursive group, on the grounds that if it is

340 part of a recursive group, then it will be called multipe times.

342 This is not necessarily true, e.g. it would be safe to eta-expand t2 (but not

343 t1) in the follwing code:

345 let go x = t1

346 t1 = if ... then t2 else ...

347 t2 = if ... then go 1 else ...

348 in go 0

350 Detecting this would reqiure finding out what variables are only ever called

351 from thunks. While this is certainly possible, we yet have to see this to be

352 relevant in the wild.

355 Note [Analysing top-level binds]

356 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

358 We can eta-expand top-level-binds if they are not exported, as we see all calls

359 to them. The plan is as follows: Treat the top-level binds as nested lets around

360 a body representing “all external calls”, which returns a pessimistic

361 CallArityRes (the co-call graph is the complete graph, all arityies 0).

363 -}

365 -- Main entry point

369 where

372 -- See Note [Analysing top-level-binds]

374 callArityTopLvl exported _ []

376 , [] )

379 where

380 int2 = bindersOf b

382 int' = int1 `addInterestingBinds` b

391 -- The main analysis function. See Note [Analysis type signature]

392 callArityAnal ::

397 -- How this expression uses its interesting variables

398 -- and the expression with IdInfo updated

400 -- The trivial base cases

407 -- The transparent cases

413 -- The interesting case: Variables, Lambdas, Lets, Applications, Cases

415 | v `elemVarSet` int

417 | otherwise

420 -- Non-value lambdas are ignored

424 -- We have a lambda that may be called multiple times, so its free variables

425 -- can all be co-called.

428 where

430 ae' = calledMultipleTimes ae

431 -- We have a lambda that we are calling. decrease arity.

434 where

437 -- Application. Increase arity for the called expresion, nothing to know about

438 -- the second

443 where

446 -- See Note [Case and App: Which side to take?]

447 final_ae = ae1 `both` ae2

449 -- Case expression.

452 -- (vcat [ppr scrut, ppr final_ae])

454 where

458 alt_ae = lubRess alt_aes

460 -- See Note [Case and App: Which side to take?]

461 final_ae = scrut_ae `both` alt_ae

463 -- For lets, use callArityBind

466 -- (vcat [ppr v, ppr arity, ppr n, ppr final_ae ])

468 where

469 int_body = int `addInterestingBinds` bind

471 ae_body' = fakeBoringCalls int_body bind ae_body -- See Note [Information about boring variables]

474 -- Which bindings should we look at?

475 -- See Note [Which variables are interesting]

481 addInterestingBinds int bind

483 `extendVarSetList` interestingBinds bind

485 -- For every boring variable in the binder, add a safe approximation

486 -- See Note [Information about boring variables]

488 fakeBoringCalls int bind res = boring `both` res

489 where

491 ( emptyUnVarGraph

495 -- Used for both local and top-level binds

496 -- First argument is the demand from the body

498 -- Non-recursive let

500 | otherwise

502 -- (vcat [ppr v, ppr ae_body, ppr int, ppr ae_rhs, ppr safe_arity])

504 where

508 safe_arity | called_once = arity

518 v' = v `setIdCallArity` safe_arity

522 -- Recursive let. See Note [Recursion and fixpointing]

525 -- (vcat [ppr (Rec binds'), ppr ae_body, ppr int, ppr ae_rhs]) $

527 where

528 int_body = int `addInterestingBinds` b

530 final_ae = bindersOf b `resDelList` ae_rhs

535 fix ann_binds

536 | -- pprTrace "callArityBind:fix" (vcat [ppr ann_binds, ppr any_change, ppr ae]) $

537 any_change

539 | otherwise

541 where

543 ae = callArityRecEnv aes_old ae_body

547 -- No call to this yet, so do nothing

553 -- No change, no need to re-analize

556 | otherwise

557 -- We previously analized this with a different arity (or not at all)

570 where

576 -- Combining the results from body and rhs, non-recursive case

577 -- See Note [Analysis II: The Co-Called analysis]

579 callArityNonRecEnv v ae_rhs ae_body

581 where

582 called_by_v = domRes ae_rhs

583 called_with_v = calledWith ae_body v `delUnVarSet` v

585 -- Combining the results from body and rhs, (mutually) recursive case

586 -- See Note [Analysis II: The Co-Called analysis]

588 callArityRecEnv ae_rhss ae_body

590 ae_new

591 where

598 where

600 -- What rhs are relevant as happening before (or after) calling v?

601 -- If v is a thunk, everything from all the _other_ variables

602 -- If v is not a thunk, everything can happen.

605 -- What do we want to know from these?

606 -- Which calls can happen next to any recursive call.

607 called_with_v

609 called_by_v = domRes ae_rhs

613 ---------------------------------------

614 -- Functions related to CallArityRes --

615 ---------------------------------------

617 -- Result type for the two analyses.

618 -- See Note [Analysis I: The arity analyis]

619 -- and Note [Analysis II: The Co-Called analysis]

622 emptyArityRes :: CallArityRes

637 -- In the result, find out the minimum arity and whether the variable is called

638 -- at most once.

651 -- Replaces the co-call graph by a complete graph (i.e. no information)

655 -- Used for application and cases

659 -- Used when combining results from alternative cases; take the minimum