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.
16	import Base
17	import bend-lint-api@0.2.2.0/linter/lint.bend as Lint
18	import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
19	import bend-lint-api@0.2.2.0/shared/names.bend as Names
20	import ./deep_call_in_fork.bend as Deep
21	import ./gpu_fit.bend as GpuFit
22	import ./loop_invariant_call.bend as Invariant
23	import ./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).
30	type 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.
36	type Scope is Data:
37	  Scope{owner: Invariant.Owner, defs: Map<&2, Maybe<&2, Lint.Def>>}
38	
39	# Functions
40	# =========
41	def Call.target(c: Call) -> String:
42	  match c:
43	    case Call{t, callee, args, span, b}:
44	      t
45	
46	def Call.callee(c: Call) -> String:
47	  match c:
48	    case Call{t, callee, args, span, b}:
49	      callee
50	
51	def Call.args(c: Call) -> List<&2, Lint.Node>:
52	  match c:
53	    case Call{t, callee, args, span, b}:
54	      args
55	
56	def Call.span(c: Call) -> Lint.Span:
57	  match c:
58	    case Call{t, callee, args, span, b}:
59	      span
60	
61	def Call.branch(c: Call) -> U32:
62	  match c:
63	    case Call{t, callee, args, span, b}:
64	      b
65	
66	def 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.
74	def 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.
90	def 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.
102	def 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.
110	def returns_number(info: Maybe<&2, Lint.Def>) -> Bool:
111	  match info:
112	    case Some{Lint.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.
118	def 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.
126	def 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(Lint.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).
162	def 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.
180	def 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.
199	def 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`.
218	def 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.
246	def calls.of(
247	  proof: Bool,
248	  loops: List<&2, String>,
249	  defs: Map<&2, Maybe<&2, Lint.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	
258	def defs(
259	  nodes: List<&2, Lint.Node>,
260	  +loops: List<&2, String>,
261	  +program: Map<&2, Maybe<&2, Lint.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	
287	def 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	      Lint.Program.defs(Lint.Here.sources(here), Map.new(&2, Maybe<&2, Lint.Def>)),
294	      []
295	    )
296	  )
297	
298	def rule() -> Lint.Rule:
299	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}