performance/repeated_call.bend
bend-lint-rules@0.1.1.0 · 299 lines · 0 definitions
1# performance/repeated_call: a call made again, with the same arguments, on one path of a definition: a
2# second call of a definition of the file that loops and returns a number, with its arguments written the
3# same way, in the same branch (the innermost case around both, or the definition's body).
4# Heuristics: clang does not merge two calls of a definition that loops: Bend runs each through its own
5# calls. Measured on the CPU, pow2(30) written `Nat.add(pow2(q), pow2(q))` took 3.4 s; with the two calls
6# forked (a parallel let), 0.6 s; computed once (`+h = pow2(q)`), 0.1 s, the program's start. In
7# eldergrove-faire and in llama.bend's tokenizer, computing such calls once changed nothing measurable:
8# they walk short lists. Arguments are the same when written the same way: the same variables, literals,
9# and calls or constructions of them. Calls in a lambda, in a type, in a proof, or in the values of
10# Bool.pick, `&&` or `||` (which performance/eager_branch judges) do not count, nor do the values of one
11# parallel let: copies made in parallel on purpose, as benchmarks do. A call that
12# performance/loop_invariant_call reports is left to it: computing it once before the loop also ends the
13# repeat. Only a number is sure to be shareable at no cost: data may be affine (an Array), so that it
14# must be built twice, and sharing it counts references; it is skipped. Numbers are those of
15# performance/gpu_fit, as the callee's return type is written.
16import Base
17import bend-lint-api@0.1.1.0/linter/lint.bend as Lint
18import bend-lint-api@0.1.1.0/shared/lists.bend as Lists
19import bend-lint-api@0.1.1.0/shared/names.bend as Names
20import bend-lint-rules@0.1.1.0/performance/deep_call_in_fork.bend as Deep
21import bend-lint-rules@0.1.1.0/performance/gpu_fit.bend as GpuFit
22import bend-lint-rules@0.1.1.0/performance/loop_invariant_call.bend as Invariant
23import bend-lint-rules@0.1.1.0/performance/missed_fork.bend as Fork
24
25# Types
26# =====
27
28# A call of a definition that loops: the definition (as the check names it, and as written), its arguments, where it
29# is written, and where its branch starts (0 for a definition's body).
30type Call is Data:
31 Call{target: String, callee: String, args: List<&2, Lint.Node>, span: Lint.Span, branch: U32}
32
33# What finding the calls of one definition reads: what performance/loop_invariant_call reads to judge them, with the
34# definitions of the file that call themselves (as the check names them), and the program's definitions, by the name
35# the check gives them.
36type Scope is Data:
37 Scope{owner: Invariant.Owner, defs: Map<&2, Maybe<&2, GpuFit.Def>>}
38
39# Functions
40# =========
41def Call.target(c: Call) -> String:
42 match c:
43 case Call{t, callee, args, span, b}:
44 t
45
46def Call.callee(c: Call) -> String:
47 match c:
48 case Call{t, callee, args, span, b}:
49 callee
50
51def Call.args(c: Call) -> List<&2, Lint.Node>:
52 match c:
53 case Call{t, callee, args, span, b}:
54 args
55
56def Call.span(c: Call) -> Lint.Span:
57 match c:
58 case Call{t, callee, args, span, b}:
59 span
60
61def Call.branch(c: Call) -> U32:
62 match c:
63 case Call{t, callee, args, span, b}:
64 b
65
66def message(callee: String, loop: String) -> String:
67 callee
68 ++ " is called again here, with the same arguments, on this path of "
69 ++ loop
70 ++ ", so Bend computes it twice: clang does not merge calls of a definition that loops. All lanes. Measured on the CPU: pow2(30) written `Nat.add(pow2(q), pow2(q))` took 3.4 s, against 0.1 s after the fix; in eldergrove-faire and in llama.bend's tokenizer, the fix changed nothing measurable, as those calls walk short lists. Confidence: medium, as the gain is what the call costs. Bind its value once, with `+` if it is used twice, and use that name. If the call is cheap, such as a walk of a short list, expect this finding."
71
72# Whether a node below `path` may not run on the path of its branch, or runs as a copy made on purpose: under a lambda,
73# a value of a choice (Bool.pick, Bool.and, Bool.or), or a value of a parallel let.
74def is_guarded(path: List<&2, Lint.Above>, found: Bool) -> Bool:
75 match path found:
76 case _ True{}:
77 True{}
78 case Nil{} False{}:
79 False{}
80 case Con{Lint.Above{Lint.Node{Lint.Lambda{b, q}, n, s, k, f}, at}, rest} False{}:
81 True{}
82 case Con{Lint.Above{Lint.Node{Lint.Application{}, n, s, +kids, f}, at}, rest} False{}:
83 is_guarded(rest, Fork.is_choice(kids))
84 case Con{Lint.Above{Lint.Node{Lint.Destructure{q}, n, s, +kids, f}, at}, rest} False{}:
85 is_guarded(rest, Nat.is_gt(Deep.binders(kids, 0n), 1n) && Bool.not(Deep.is_last(kids, at)))
86 case Con{a, rest} False{}:
87 is_guarded(rest, False{})
88
89# Where the first of `nodes`, or a node under it, that has a place starts.
90def first_beg(+fuel: Nat, nodes: List<&2, Lint.Node>) -> U32:
91 match fuel nodes:
92 case 0n _:
93 0
94 case _ Nil{}:
95 0
96 case 1n+f Con{Lint.Node{syntax, n, Some{Lint.Span{p, beg, end}}, k, fs}, rest}:
97 beg
98 case 1n+f Con{Lint.Node{syntax, n, None{}, k, fs}, rest}:
99 first_beg(f, List.append(&2, Lint.Node, k, rest))
100
101# Where a branch starts (a case has no place of its own: its first node with one), or 0 for a definition's body.
102def branch.at(b: Maybe<&2, Lint.Node>) -> U32:
103 match b:
104 case Some{node}:
105 first_beg(64n, [node])
106 case None{}:
107 0
108
109# Whether a definition of the program says it returns a number.
110def returns_number(info: Maybe<&2, GpuFit.Def>) -> Bool:
111 match info:
112 case Some{GpuFit.Def{t, ps, fk, cs, r}}:
113 GpuFit.is_scalar(r)
114 case None{}:
115 False{}
116
117# Whether a call that counts so far (if `ok`) still counts: not if performance/loop_invariant_call reports it.
118def is_kept(ok: Bool, owner: Invariant.Owner, path: List<&2, Lint.Above>, node: Lint.Node) -> Bool:
119 match ok:
120 case True{}:
121 List.is_empty(&2, Lint.Finding, Invariant.visit(owner, path, node))
122 case False{}:
123 False{}
124
125# The call of a definition that loops at an application below `path`, if it counts.
126def visit(+scope: Scope, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Call>:
127 match scope node:
128 case Scope{
129 Invariant.Owner{+loops, target, name, fixed},
130 defs
131 } Lint.Node{
132 Lint.Application{},
133 n,
134 Some{span},
135 Con{Lint.Node{Lint.Reference{+t}, callee, rs, rk, rf}, args},
136 f
137 }:
138 Bool.pick(
139 List<&2, Call>,
140 is_kept(
141 List.contains(
142 ~String,
143 ~String.eq,
144 loops,
145 t
146 )
147 && returns_number(Names.find(GpuFit.Def, defs, t))
148 && Lint.is_live(path)
149 && Bool.not(is_guarded(path, False{})),
150 Invariant.Owner{loops, target, name, fixed},
151 path,
152 node
153 ),
154 [Call{t, callee, args, span, branch.at(Invariant.branch(path, None{}))}],
155 []
156 )
157 case _ _:
158 []
159
160# Whether two nodes, as written, are the same at their top: the same variable, literal or reference, or the same kind
161# of application, annotation or construction (their nodes below are compared next).
162def is_shallow(x: Lint.Node, y: Lint.Node) -> Bool:
163 match x y:
164 case Lint.Node{Lint.Variable{a}, n, s, k, f} Lint.Node{Lint.Variable{b}, m, r, j, g}:
165 U32.is_eq(a, b)
166 case Lint.Node{Lint.Literal{a}, n, s, k, f} Lint.Node{Lint.Literal{b}, m, r, j, g}:
167 String.eq(a, b) && String.eq(n, m)
168 case Lint.Node{Lint.Reference{a}, n, s, k, f} Lint.Node{Lint.Reference{b}, m, r, j, g}:
169 String.eq(a, b)
170 case Lint.Node{Lint.Application{}, n, s, k, f} Lint.Node{Lint.Application{}, m, r, j, g}:
171 True{}
172 case Lint.Node{Lint.Annotation{}, n, s, k, f} Lint.Node{Lint.Annotation{}, m, r, j, g}:
173 True{}
174 case Lint.Node{Lint.Construction{a}, n, s, k, f} Lint.Node{Lint.Construction{b}, m, r, j, g}:
175 String.eq(a, b)
176 case _ _:
177 False{}
178
179# Whether `xs` and `ys` are written the same way, node by node and below (if `ok`); `fuel` bounds the nodes compared.
180def is_same(+fuel: Nat, xs: List<&2, Lint.Node>, ys: List<&2, Lint.Node>, ok: Bool) -> Bool:
181 match fuel xs ys ok:
182 case _ _ _ False{}:
183 False{}
184 case _ Nil{} Nil{} True{}:
185 True{}
186 case 0n _ _ True{}:
187 False{}
188 case 1n+f Con{+x, xt} Con{+y, yt} True{}:
189 is_same(
190 f,
191 List.append(&2, Lint.Node, Lint.Node.kids(x), xt),
192 List.append(&2, Lint.Node, Lint.Node.kids(y), yt),
193 is_shallow(x, y)
194 )
195 case _ _ _ True{}:
196 False{}
197
198# Whether `c` repeats a call of `seen`: the same definition, in the same branch, with arguments written the same way.
199def repeats(seen: List<&2, Call>, +c: Call, found: Bool) -> Bool:
200 match seen found:
201 case _ True{}:
202 True{}
203 case Nil{} False{}:
204 False{}
205 case Con{Call{t, callee, args, span, b}, rest} False{}:
206 repeats(
207 rest,
208 c,
209 is_same(
210 256n,
211 args,
212 Call.args(c),
213 String.eq(t, Call.target(c)) && U32.is_eq(b, Call.branch(c))
214 )
215 )
216
217# The findings about the calls of one definition (`loop`, as written) that repeat an earlier one, onto `out`.
218def judged(
219 calls: List<&2, Call>,
220 +seen: List<&2, Call>,
221 +loop: String,
222 out: List<&2, Lint.Finding>
223) -> List<&2, Lint.Finding>:
224 match calls:
225 case Nil{}:
226 out
227 case Con{+c, rest}:
228 judged(
229 rest,
230 c <> seen,
231 loop,
232 Lists.onto(
233 &2,
234 Lint.Finding,
235 Lint.finding(
236 Lint.Information{},
237 repeats(seen, c, False{}),
238 Some{Call.span(c)},
239 message(Call.callee(c), loop)
240 ),
241 out
242 )
243 )
244
245# The calls of a definition (`node`) that count, unless it is a proof.
246def calls.of(
247 proof: Bool,
248 loops: List<&2, String>,
249 defs: Map<&2, Maybe<&2, GpuFit.Def>>,
250 +node: Lint.Node
251) -> List<&2, Call>:
252 match proof:
253 case True{}:
254 []
255 case False{}:
256 Lint.visit(~Scope, ~Call, ~visit, Scope{Invariant.Owner.of(loops, node), defs}, [node])
257
258def defs(
259 nodes: List<&2, Lint.Node>,
260 +loops: List<&2, String>,
261 +program: Map<&2, Maybe<&2, GpuFit.Def>>,
262 out: List<&2, Lint.Finding>
263) -> List<&2, Lint.Finding>:
264 match nodes:
265 case Nil{}:
266 List.reverse(&2, Lint.Finding, out)
267 case Con{Lint.Node{Lint.Definition{t, u}, +n, s, +k, f}, rest}:
268 defs(
269 rest,
270 loops,
271 program,
272 judged(
273 calls.of(
274 Invariant.is_proof(k),
275 loops,
276 program,
277 Lint.Node{Lint.Definition{t, u}, n, s, k, f}
278 ),
279 [],
280 n,
281 out
282 )
283 )
284 case Con{node, rest}:
285 defs(rest, loops, program, out)
286
287def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
288 +nodes = Lint.Here.nodes(here)
289 Lint.done(
290 defs(
291 nodes,
292 Invariant.loops(nodes, []),
293 GpuFit.program.defs(Lint.Here.sources(here), Map.new(&2, Maybe<&2, GpuFit.Def>)),
294 []
295 )
296 )
297
298def rule() -> Lint.Rule:
299 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}