performance/unused_result.bend
bend-lint-rules@0.1.0.0 · 191 lines · 0 definitions
1# performance/unused_result: a value that a loop binds and never uses, and that is data, not a number: a
2# lambda's parameter or a let's name, in a definition that calls itself. Bend computes every value it
3# binds, so this one is built, and then walked to be freed, on every step.
4# Heuristics: measured on llama.bend (SmolLM2-135M, CPU): its generation loop binds each layer's
5# activations and never uses them; building them empty made each token 19% to 25% faster, with the same
6# tokens. The cost grows with the value: a small one costs little to ignore. It reads how often the
7# checker found each binder used, and the type it gave it; numbers, and records of numbers only, are
8# those of performance/gpu_fit, and cost nothing to drop. An erased binder holds nothing at run time,
9# and a step of a `do` block (`x : T <- m`, a call of a bind) gets its value from the monad, used or not.
10import Base
11import bend-lint-api@0.1.0.0/linter/lint.bend as Lint
12import bend-lint-api@0.1.0.0/shared/lists.bend as Lists
13import bend-lint-rules@0.1.0.0/performance/gpu_fit.bend as GpuFit
14
15# Types
16# =====
17
18# A binder a loop never uses: where it is written, its name, the loop's name, and the type the checker gave it.
19type Unused is Data:
20 Unused{span: Lint.Span, name: String, loop: String, ty: Lint.TypeRef}
21
22# What judging the binders of one definition reads: whether it is a loop (it calls itself), and its name as written.
23type Owner is Data:
24 Owner{loop: Bool, name: String}
25
26# Functions
27# =========
28def message(+name: String, loop: String) -> String:
29 name
30 ++ " is never used, but Bend computes every value it binds: "
31 ++ name
32 ++ " is built, then walked to be freed, on every step of "
33 ++ loop
34 ++ ". All lanes. Measured on the CPU, in llama.bend: not building the activations that its generation loop never used made each token 19% to 25% faster. Confidence: medium, as the cost grows with the value. Have the code that makes "
35 ++ name
36 ++ " skip it, such as a variant that does not build it. If it is small, expect this finding."
37
38def loop.visit(+u: Unit, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Unit>:
39 Bool.pick(List<&2, Unit>, Lint.is_recursive(path, node), [Unit{}], [])
40
41# Whether a lambda below `path` is the rest of a step of a `do` block (`x : T <- m`, the last argument of a call of a
42# bind): its value comes from the monad, which makes it whether it is used or not.
43def is_step(path: List<&2, Lint.Above>) -> Bool:
44 match path:
45 case Con{
46 Lint.Above{
47 Lint.Node{
48 Lint.Application{},
49 n,
50 s,
51 Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, args},
52 f
53 },
54 at
55 },
56 rest
57 }:
58 String.ends_with(t, ".bind")
59 case _:
60 False{}
61
62# Whether a node of this kind, below `path`, binds a value at run time: a lambda's parameter (not a `do` step's), or a
63# let's name (a binding, or the one pattern variable of a let), not erased.
64def is_binder(syntax: Lint.Syntax, path: List<&2, Lint.Above>) -> Bool:
65 match syntax path:
66 case Lint.Lambda{b, Some{Lint.Erased{}}} _:
67 False{}
68 case Lint.Lambda{b, q} _:
69 Bool.not(is_step(path))
70 case Lint.Binding{b, Lint.Erased{}} _:
71 False{}
72 case Lint.Binding{b, q} _:
73 True{}
74 case Lint.PatternVariable{b, Lint.Erased{}} _:
75 False{}
76 case Lint.PatternVariable{
77 b,
78 q
79 } Con{Lint.Above{Lint.Node{Lint.Destructure{d}, n, s, k, f}, at}, rest}:
80 True{}
81 case _ _:
82 False{}
83
84# The type of a binder its facts say is never used, if they do.
85def unused(facts: List<&2, Lint.Fact>) -> Maybe<&2, Lint.TypeRef>:
86 match facts:
87 case Nil{}:
88 None{}
89 case Con{Lint.Fact{Lint.OfBinder{}, q, Some{Lint.Erased{}}, t}, rest}:
90 Some{t}
91 case Con{f, rest}:
92 unused(rest)
93
94def unused.of(
95 binder: Bool,
96 ty: Maybe<&2, Lint.TypeRef>,
97 span: Lint.Span,
98 name: String,
99 loop: String
100) -> List<&2, Unused>:
101 match binder ty:
102 case True{} Some{t}:
103 [Unused{span, name, loop, t}]
104 case _ _:
105 []
106
107def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Unused>:
108 match owner node:
109 case Owner{True{}, loop} Lint.Node{syntax, name, Some{span}, k, facts}:
110 unused.of(is_binder(syntax, path), unused(facts), span, name, loop)
111 case _ _:
112 []
113
114# The binders that the loops among `nodes` never use, onto `out` (last first).
115def defs(nodes: List<&2, Lint.Node>, out: List<&2, Unused>) -> List<&2, Unused>:
116 match nodes:
117 case Nil{}:
118 out
119 case Con{Lint.Node{Lint.Definition{t, u}, +n, s, k, f}, rest}:
120 +owner = {Lint.Node{Lint.Definition{t, u}, n, s, k, f}: Lint.Node}
121 defs(
122 rest,
123 Lists.onto(
124 &2,
125 Unused,
126 List.reverse(
127 &2,
128 Unused,
129 Lint.visit(
130 ~Owner,
131 ~Unused,
132 ~visit,
133 Owner{
134 Bool.not(
135 List.is_empty(&2, Unit, Lint.visit(~Unit, ~Unit, ~loop.visit, Unit{}, [owner]))
136 ),
137 n
138 },
139 [owner]
140 )
141 ),
142 out
143 )
144 )
145 case Con{node, rest}:
146 defs(rest, out)
147
148def types(found: List<&2, Unused>, out: List<&2, Lint.TypeRef>) -> List<&2, Lint.TypeRef>:
149 match found:
150 case Nil{}:
151 List.reverse(&2, Lint.TypeRef, out)
152 case Con{Unused{s, n, l, t}, rest}:
153 types(rest, t <> out)
154
155# The findings about the unused binders whose types, as shown, are data: not numbers, nor records of numbers only.
156def judged(
157 found: List<&2, Unused>,
158 shown: List<&2, String>,
159 +slots: List<&2, GpuFit.Slot>,
160 out: List<&2, Lint.Finding>
161) -> List<&2, Lint.Finding>:
162 match found shown:
163 case Con{Unused{span, name, loop, t}, rest} Con{ty, more}:
164 judged(
165 rest,
166 more,
167 slots,
168 Lists.onto(
169 &2,
170 Lint.Finding,
171 Lint.finding(
172 Lint.Information{},
173 Bool.not(GpuFit.is_flat(64n, Some{[ty]}, slots)),
174 Some{span},
175 message(name, loop)
176 ),
177 out
178 )
179 )
180 case _ _:
181 List.reverse(&2, Lint.Finding, out)
182
183def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
184 +found = List.reverse(&2, Unused, defs(Lint.Here.nodes(here), []))
185 slots = GpuFit.program.slots(Lint.Here.sources(here), [])
186 do Lint.Ask<List<&2, Lint.Finding>>:
187 shown: List<&2, String> <- Lint.show_all(types(found, []))
188 return judged(found, shown, slots, [])
189
190def rule() -> Lint.Rule:
191 Lint.Rule{Lint.Needs{True{}, False{}}, [], Lint.OnFile{run}}