performance/unused_result.bend

bend-lint-rules@0.2.0.0 · 191 lines · 14 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.2.0.0/linter/lint.bend as Lint
12import bend-lint-api@0.2.0.0/shared/lists.bend as Lists
13import bend-lint-rules@0.2.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}}