1	# performance/deep_call_in_fork: a fork that calls a definition that calls itself outside a tail
2	# position. A value of a parallel let (`a b = f(x) g(y)`), or of a let just before it, calls a definition
3	# of the file whose call of itself is not the last thing it does.
4	# Heuristics: Bend gives a call of itself that is not a tail call a frame per call ("bend guide
5	# shaders"). In bend-lint's benchmark (Bend 2.0.36, on the CPU), such a call at each fork cut the speedup
6	# from 10x to 1.9x; the same definition with a tail call kept the 10x. In a raytracer that splits its
7	# rows that way at each of 9 fork levels, tail-recursive splits made it 4% to 8% faster on the CPU; in
8	# Bend's slash boss demo, the same change changed no timing, as its list was short. The JS lane is not
9	# measured. A tail position is the body of a definition, a case, or the rest of a block after its lets,
10	# through annotations. A definition with a parallel let is a fork tree: its calls of itself are the
11	# values of its forks, not frames, and it is not reported (Bend's matrix and Merkle benchmarks call such
12	# trees in their forks).
13	import Base
14	import bend-lint-api@0.1.0.0/linter/lint.bend as Lint
15	import bend-lint-api@0.1.0.0/shared/lists.bend as Lists
16	import ./gpu_fit.bend as GpuFit
17	
18	# Types
19	# =====
20	
21	# What judging the calls in one definition reads: the definitions of the file that call themselves outside a tail
22	# position (as the check names them), and the definition, by the name the check gives it and as written.
23	type Owner is Data:
24	  Owner{deeps: List<&2, String>, target: String, name: String}
25	
26	# Functions
27	# =========
28	
29	# Whether `at` is the place of the last of `nodes`.
30	def is_last(nodes: List<&2, Lint.Node>, at: U32) -> Bool:
31	  U32.is_eq((at + 1: U32), U32.from_nat(Lists.length(&2, Lint.Node, nodes)))
32	
33	# Whether the node below `path` is in a tail position, if it ends the node above it (`ends`): the body of a definition
34	# or a case, or the rest of a block after its lets, through annotations.
35	def is_tail(path: List<&2, Lint.Above>, ends: Bool) -> Bool:
36	  match path ends:
37	    case _ False{}:
38	      False{}
39	    case Con{Lint.Above{Lint.Node{Lint.Body{}, n, s, k, f}, at}, rest} True{}:
40	      True{}
41	    case Con{Lint.Above{Lint.Node{Lint.Case{}, n, s, k, f}, at}, rest} True{}:
42	      is_tail(rest, True{})
43	    case Con{Lint.Above{Lint.Node{Lint.Match{}, n, s, k, f}, at}, rest} True{}:
44	      is_tail(rest, True{})
45	    case Con{Lint.Above{Lint.Node{Lint.Annotation{}, n, s, k, f}, at}, rest} True{}:
46	      is_tail(rest, True{})
47	    case Con{Lint.Above{Lint.Node{Lint.Destructure{q}, n, s, kids, f}, at}, rest} True{}:
48	      is_tail(rest, is_last(kids, at))
49	    case Con{Lint.Above{Lint.Node{Lint.Let{}, n, s, kids, f}, at}, rest} True{}:
50	      is_tail(rest, is_last(kids, at))
51	    case _ _:
52	      False{}
53	
54	# Whether a call of its definition to itself below `path` is outside a tail position.
55	def deep.of(recursive: Bool, path: List<&2, Lint.Above>) -> List<&2, Bool>:
56	  match recursive:
57	    case True{}:
58	      [Bool.not(is_tail(path, True{}))]
59	    case False{}:
60	      []
61	
62	def deep.visit(+u: Unit, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Bool>:
63	  deep.of(Lint.is_recursive(path, node), path)
64	
65	# The definitions among `nodes` that call themselves outside a tail position, as the check names them, onto `out`;
66	# with `forking` false, not those with a parallel let, whose such calls are the values of their forks.
67	def deep(nodes: List<&2, Lint.Node>, +forking: Bool, out: List<&2, String>) -> List<&2, String>:
68	  match nodes:
69	    case Nil{}:
70	      out
71	    case Con{Lint.Node{Lint.Definition{+t, u}, n, s, +k, f}, rest}:
72	      deep(
73	        rest,
74	        forking,
75	        Lists.push(
76	          String,
77	          Lists.when(
78	            String,
79	            List.contains(
80	              ~Bool,
81	              ~Bool.and,
82	              Lint.visit(
83	                ~Unit,
84	                ~Bool,
85	                ~deep.visit,
86	                Unit{},
87	                [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
88	              ),
89	              True{}
90	            )
91	              && (forking || Bool.not(GpuFit.forks(k, False{}))),
92	            t
93	          ),
94	          out
95	        )
96	      )
97	    case Con{node, rest}:
98	      deep(rest, forking, out)
99	
100	def is_pattern(syntax: Lint.Syntax) -> Bool:
101	  match syntax:
102	    case Lint.PatternVariable{b, q}:
103	      True{}
104	    case Lint.PatternConstructor{t}:
105	      True{}
106	    case _:
107	      False{}
108	
109	def binders(nodes: List<&2, Lint.Node>, n: Nat) -> Nat:
110	  match nodes:
111	    case Nil{}:
112	      n
113	    case Con{Lint.Node{Lint.PatternVariable{b, q}, nm, s, k, f}, rest}:
114	      binders(rest, 1n+n)
115	    case Con{node, rest}:
116	      binders(rest, n)
117	
118	# Whether a let leads to a fork: it is one (it binds `many` names), or it binds one (`one`), and the last of `nodes`,
119	# the rest of its block, is a let that leads to one. The values of these lets are what a fork runs, or what runs just
120	# before it.
121	def leads(nodes: List<&2, Lint.Node>, many: Bool, one: Bool) -> Bool:
122	  match nodes many one:
123	    case _ True{} _:
124	      True{}
125	    case _ False{} False{}:
126	      False{}
127	    case Con{Lint.Node{Lint.Destructure{q}, n, s, +kids, f}, Nil{}} False{} True{}:
128	      +count = binders(kids, 0n)
129	      leads(kids, Nat.is_gt(count, 1n), Nat.is_eq(count, 1n))
130	    case Con{x, Nil{}} False{} True{}:
131	      False{}
132	    case Con{x, rest} False{} True{}:
133	      leads(rest, False{}, True{})
134	    case Nil{} False{} True{}:
135	      False{}
136	
137	# Whether `x`, the node at `at` under `parent`, is a value of a fork, or of a let just before one: not a binder, nor the
138	# rest of the block.
139	def is_value(x: Lint.Node, +parent: Lint.Node, at: U32) -> Bool:
140	  match x parent:
141	    case Lint.Node{s, n, sp, k, f} Lint.Node{ps, pn, psp, +kids, pf}:
142	      leads([parent], False{}, Bool.not(is_pattern(s)) && Bool.not(is_last(kids, at)))
143	
144	# Whether `x`, below `path`, or a node above it, is a value of a fork, or `found`.
145	def is_inside(path: List<&2, Lint.Above>, x: Lint.Node, found: Bool) -> Bool:
146	  match path found:
147	    case _ True{}:
148	      True{}
149	    case Nil{} False{}:
150	      False{}
151	    case Con{Lint.Above{+p, at}, rest} False{}:
152	      is_inside(rest, p, is_value(x, p, at))
153	
154	def message(+callee: String, loop: String) -> String:
155	  callee
156	    ++ " calls itself outside a tail position, so Bend gives each of its calls a frame, and "
157	    ++ loop
158	    ++ " calls it in a fork (a value of its parallel let, or of a let just before it). CPU: measured 4% to 8% faster for a raytracer after the fix; in a benchmark, such a call at each fork cut a 10x speedup to 1.9x. GPU: such a recursion in a `!` made a draw 2.3x slower (\"bend guide shaders\"). JS: not measured. Confidence: medium, as the cost grows with the depth of the recursion. Make "
159	    ++ callee
160	    ++ " tail-recursive with an accumulator, compute its value with native operations (such as U32.shln), or compute it once and pass it down as a parameter. If its input is short, expect this finding."
161	
162	# The finding about a call of a deep definition (if `deep`), when the call is in a fork.
163	def judge.deep(
164	  deep: Bool,
165	  path: List<&2, Lint.Above>,
166	  +node: Lint.Node,
167	  callee: String,
168	  name: String
169	) -> List<&2, Lint.Finding>:
170	  match deep:
171	    case True{}:
172	      Lint.finding(
173	        Lint.Information{},
174	        is_inside(path, node, False{}),
175	        Lint.Node.span(Some{node}),
176	        message(callee, name)
177	      )
178	    case False{}:
179	      []
180	
181	def judge.call(
182	  +owner: Owner,
183	  path: List<&2, Lint.Above>,
184	  node: Lint.Node,
185	  callee: String,
186	  +called: String
187	) -> List<&2, Lint.Finding>:
188	  match owner:
189	    case Owner{deeps, target, name}:
190	      judge.deep(
191	        List.contains(~String, ~String.eq, deeps, called) && Bool.not(String.eq(called, target)),
192	        path,
193	        node,
194	        callee,
195	        name
196	      )
197	
198	def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
199	  match node:
200	    case Lint.Node{
201	      Lint.Application{},
202	      n,
203	      s,
204	      Con{Lint.Node{Lint.Reference{called}, callee, rs, rk, rf}, args},
205	      f
206	    }:
207	      judge.call(owner, path, node, callee, called)
208	    case _:
209	      []
210	
211	def defs(
212	  nodes: List<&2, Lint.Node>,
213	  +deeps: List<&2, String>,
214	  out: List<&2, Lint.Finding>
215	) -> List<&2, Lint.Finding>:
216	  match nodes:
217	    case Nil{}:
218	      List.reverse(&2, Lint.Finding, out)
219	    case Con{Lint.Node{Lint.Definition{+t, u}, +n, s, k, f}, rest}:
220	      defs(
221	        rest,
222	        deeps,
223	        Lists.onto(
224	          &2,
225	          Lint.Finding,
226	          Lint.visit(
227	            ~Owner,
228	            ~Lint.Finding,
229	            ~visit,
230	            Owner{deeps, t, n},
231	            [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
232	          ),
233	          out
234	        )
235	      )
236	    case Con{node, rest}:
237	      defs(rest, deeps, out)
238	
239	def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
240	  +nodes = Lint.Here.nodes(here)
241	  Lint.done(defs(nodes, deep(nodes, False{}, []), []))
242	
243	def rule() -> Lint.Rule:
244	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}