performance/loop_invariant_call.bend
bend-lint-rules@0.2.2.0 · 299 lines · 0 definitions
1# performance/loop_invariant_call: a call that gets the same arguments on every step of a loop, so it
2# computes the same value each time: in a definition that calls itself, a call of a definition of the
3# file that loops too, in the branch that repeats (the one with the loop's call of itself), whose
4# arguments are literals, or parameters that the loop passes unchanged to each call of itself.
5# Heuristics: clang hoists plain arithmetic out of a loop (and folds constants), but not a call of a
6# definition that loops: Bend runs it through its own calls. Compute it once, before the loop, and pass
7# it as a parameter. A definition that does not call itself is cheap, and not reported. A proof (a
8# definition that fills a law, or returns an equality) does not run, and is skipped. A loop that repeats
9# work on purpose, such as a benchmark's, is the case to expect.
10import Base
11import bend-lint-api@0.2.2.0/linter/lint.bend as Lint
12import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
13
14# Types
15# =====
16
17# What judging the calls of one definition reads: the definitions of the file that call themselves (as the check
18# names them), the definition (as the check names it, and as written), and its parameters that it passes unchanged
19# to each call of itself, by binder.
20type Owner is Data:
21 Owner{loops: List<&2, String>, target: String, name: String, fixed: List<&2, U32>}
22
23# Functions
24# =========
25def message(callee: String, loop: String) -> String:
26 callee
27 ++ " gets the same arguments on every step of "
28 ++ loop
29 ++ ", so it computes the same value each time: clang hoists plain arithmetic out of a loop, but not a call of a definition that loops. All lanes. Confidence: medium, as the gain is what the call costs. Compute it once before the loop, and pass it as a parameter. If the call is cheap, or the loop repeats it on purpose (a benchmark), expect this finding."
30
31def loop.visit(+u: Unit, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Unit>:
32 Bool.pick(List<&2, Unit>, Lint.is_recursive(path, node), [Unit{}], [])
33
34# The definitions among `nodes` that call themselves, as the check names them, onto `out`.
35def loops(nodes: List<&2, Lint.Node>, out: List<&2, String>) -> List<&2, String>:
36 match nodes:
37 case Nil{}:
38 out
39 case Con{Lint.Node{Lint.Definition{+t, u}, n, s, k, f}, rest}:
40 loops(
41 rest,
42 Lists.push(
43 String,
44 Lists.when(
45 String,
46 Bool.not(
47 List.is_empty(
48 &2,
49 Unit,
50 Lint.visit(
51 ~Unit,
52 ~Unit,
53 ~loop.visit,
54 Unit{},
55 [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
56 )
57 )
58 ),
59 t
60 ),
61 out
62 )
63 )
64 case Con{node, rest}:
65 loops(rest, out)
66
67# The arguments of each call of the definition below `path` to itself.
68def self.visit(
69 +u: Unit,
70 +path: List<&2, Lint.Above>,
71 +node: Lint.Node
72) -> List<&2, List<&2, Lint.Node>>:
73 match node:
74 case Lint.Node{Lint.Application{}, n, s, Con{f, args}, fs}:
75 Bool.pick(List<&2, List<&2, Lint.Node>>, Lint.is_recursive(path, node), [args], [])
76 case _:
77 []
78
79def passed.at(arg: Maybe<&2, Lint.Node>, b: U32) -> Bool:
80 match arg:
81 case Some{Lint.Node{Lint.Variable{v}, n, s, k, f}}:
82 U32.is_eq(v, b)
83 case _:
84 False{}
85
86# Whether the argument at `at` of each of `calls` is the variable of `b`.
87def passed(calls: List<&2, List<&2, Lint.Node>>, +at: Nat, +b: U32, ok: Bool) -> Bool:
88 match calls ok:
89 case _ False{}:
90 False{}
91 case Nil{} True{}:
92 True{}
93 case Con{args, rest} True{}:
94 passed(rest, at, b, passed.at(List.get(&2, Lint.Node, args, at), b))
95
96# The runtime parameters among a definition's nodes that it passes unchanged to each of `calls` (its calls of itself),
97# by binder; `at` counts the runtime parameters, as the calls' arguments do.
98def fixed(
99 nodes: List<&2, Lint.Node>,
100 +calls: List<&2, List<&2, Lint.Node>>,
101 +at: Nat,
102 out: List<&2, U32>
103) -> List<&2, U32>:
104 match nodes:
105 case Nil{}:
106 out
107 case Con{Lint.Node{Lint.Parameter{+b, q}, n, s, k, f}, rest}:
108 fixed(
109 rest,
110 calls,
111 1n+at,
112 Lists.push(U32, Lists.when(U32, passed(calls, at, b, True{}), b), out)
113 )
114 case Con{node, rest}:
115 fixed(rest, calls, at, out)
116
117# What judging the calls of the definition `node` reads, with `loops`, the definitions of the file that call themselves.
118def Owner.of(loops: List<&2, String>, +node: Lint.Node) -> Owner:
119 match node:
120 case Lint.Node{Lint.Definition{+t, u}, +n, s, +k, f}:
121 Owner{
122 loops,
123 t,
124 n,
125 fixed(
126 k,
127 Lint.visit(
128 ~Unit,
129 ~List<&2, Lint.Node>,
130 ~self.visit,
131 Unit{},
132 [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
133 ),
134 0n,
135 []
136 )
137 }
138 case _:
139 Owner{loops, "", "", []}
140
141# Whether `nodes`, the arguments of a call, are the same on every step: literals, the variables of `fixed`, and calls,
142# annotations or constructions of those alone; `fuel` bounds the depth.
143def invariant(+fuel: Nat, nodes: List<&2, Lint.Node>, +fixed: List<&2, U32>, ok: Bool) -> Bool:
144 match fuel nodes ok:
145 case _ _ False{}:
146 False{}
147 case _ Nil{} True{}:
148 True{}
149 case 0n _ True{}:
150 False{}
151 case 1n+f Con{Lint.Node{Lint.Literal{t}, n, s, k, fs}, rest} True{}:
152 invariant(f, rest, fixed, True{})
153 case 1n+f Con{Lint.Node{Lint.Variable{v}, n, s, k, fs}, rest} True{}:
154 invariant(f, rest, fixed, List.contains(~U32, ~U32.is_eq, fixed, v))
155 case 1n+f Con{Lint.Node{Lint.Application{}, n, s, Con{h, args}, fs}, rest} True{}:
156 invariant(f, rest, fixed, invariant(f, args, fixed, True{}))
157 case 1n+f Con{Lint.Node{Lint.Annotation{}, n, s, Con{x, ts}, fs}, rest} True{}:
158 invariant(f, rest, fixed, invariant(f, [x], fixed, True{}))
159 case 1n+f Con{Lint.Node{Lint.Construction{t}, n, s, k, fs}, rest} True{}:
160 invariant(f, rest, fixed, invariant(f, k, fixed, True{}))
161 case 1n+f Con{x, rest} True{}:
162 False{}
163
164# Whether a call of `target` is among `nodes` or under them, or `found`.
165def has_call(nodes: List<&2, Lint.Node>, +target: String, found: Bool) -> Bool:
166 match nodes found:
167 case _ True{}:
168 True{}
169 case Nil{} False{}:
170 False{}
171 case Con{
172 Lint.Node{
173 Lint.Application{},
174 n,
175 s,
176 Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, args},
177 f
178 },
179 rest
180 } False{}:
181 has_call(rest, target, has_call(args, target, String.eq(t, target)))
182 case Con{Lint.Node{syntax, n, s, kids, f}, rest} False{}:
183 has_call(rest, target, has_call(kids, target, False{}))
184
185# The branch a node below `path` is in: the innermost case above it, or the definition's body (the last of `path`).
186def branch(path: List<&2, Lint.Above>, last: Maybe<&2, Lint.Node>) -> Maybe<&2, Lint.Node>:
187 match path:
188 case Nil{}:
189 last
190 case Con{Lint.Above{Lint.Node{Lint.Case{}, n, s, k, f}, at}, rest}:
191 Some{Lint.Node{Lint.Case{}, n, s, k, f}}
192 case Con{Lint.Above{p, at}, rest}:
193 branch(rest, Some{p})
194
195def repeats(b: Maybe<&2, Lint.Node>, target: String) -> Bool:
196 match b:
197 case Some{node}:
198 has_call([node], target, False{})
199 case None{}:
200 False{}
201
202# Whether the branch a node below `path` is in calls `target` again, if `found`.
203def repeats.if(found: Bool, path: List<&2, Lint.Above>, target: String) -> Bool:
204 match found:
205 case True{}:
206 repeats(branch(path, None{}), target)
207 case False{}:
208 False{}
209
210def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
211 match owner node:
212 case Owner{
213 loops,
214 +target,
215 name,
216 fixed
217 } Lint.Node{
218 Lint.Application{},
219 n,
220 span,
221 Con{Lint.Node{Lint.Reference{+t}, callee, rs, rk, rf}, args},
222 facts
223 }:
224 Lint.finding(
225 Lint.Information{},
226 repeats.if(
227 invariant(
228 64n,
229 args,
230 fixed,
231 Bool.not(String.eq(t, target)) && List.contains(~String, ~String.eq, loops, t)
232 )
233 && Lint.is_live(path),
234 path,
235 target
236 ),
237 span,
238 message(callee, name)
239 )
240 case _ _:
241 []
242
243# Whether a definition's nodes say it is a proof: it has no return type written (it fills a law), or it returns an
244# equality.
245def is_proof(nodes: List<&2, Lint.Node>) -> Bool:
246 match nodes:
247 case Nil{}:
248 True{}
249 case Con{
250 Lint.Node{Lint.Returns{}, n, s, Con{Lint.Node{Lint.Equality{}, en, es, ek, ef}, k}, f},
251 rest
252 }:
253 True{}
254 case Con{Lint.Node{Lint.Returns{}, n, s, k, f}, rest}:
255 False{}
256 case Con{node, rest}:
257 is_proof(rest)
258
259# The findings in the definition `owner`, unless it is `skipped`.
260def defs.if(skipped: Bool, loops: List<&2, String>, +owner: Lint.Node) -> List<&2, Lint.Finding>:
261 match skipped:
262 case True{}:
263 []
264 case False{}:
265 Lint.visit(~Owner, ~Lint.Finding, ~visit, Owner.of(loops, owner), [owner])
266
267def defs(
268 nodes: List<&2, Lint.Node>,
269 +loops: List<&2, String>,
270 out: List<&2, Lint.Finding>
271) -> List<&2, Lint.Finding>:
272 match nodes:
273 case Nil{}:
274 List.reverse(&2, Lint.Finding, out)
275 case Con{Lint.Node{Lint.Definition{+t, u}, n, s, +k, f}, rest}:
276 owner = {Lint.Node{Lint.Definition{t, u}, n, s, k, f}: Lint.Node}
277 defs(
278 rest,
279 loops,
280 Lists.onto(
281 &2,
282 Lint.Finding,
283 defs.if(
284 Bool.not(List.contains(~String, ~String.eq, loops, t)) || is_proof(k),
285 loops,
286 owner
287 ),
288 out
289 )
290 )
291 case Con{node, rest}:
292 defs(rest, loops, out)
293
294def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
295 +nodes = Lint.Here.nodes(here)
296 Lint.done(defs(nodes, loops(nodes, []), []))
297
298def rule() -> Lint.Rule:
299 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}