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.
10	import Base
11	import bend-lint-api@0.2.1.0/linter/lint.bend as Lint
12	import bend-lint-api@0.2.1.0/shared/lists.bend as Lists
13	import ./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.
19	type 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.
23	type Owner is Data:
24	  Owner{loop: Bool, name: String}
25	
26	# Functions
27	# =========
28	def 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	
38	def 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.
43	def 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.
64	def 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.
85	def 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	
94	def 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	
107	def 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).
115	def 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	
148	def 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.
156	def 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	
183	def 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	
190	def rule() -> Lint.Rule:
191	  Lint.Rule{Lint.Needs{True{}, False{}}, [], Lint.OnFile{run}}