Repository navigation
Expand file tree
/
Copy pathtensor_io.py
More file actions
283 lines (272 loc) · 11.6 KB
/
Copy pathtensor_io.py
File metadata and controls
283 lines (272 loc) · 11.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
"""Bounded syntactic host/kernel edges. Never import or execute candidate code."""
import ast
import hashlib
VERSION = "direct_launch_v1"
ASSUMPTIONS = [
"Imported library names denote their usual Torch/Triton APIs;runtime rebinding is unproved."
]
UNKNOWNS = [
"Reachability,aliasing,external side effects,mask coverage and complete output initialization are unproved."
]
def analyze(source, *, path, source_sha256, entry_symbol=None, max_source=32768, max_nodes=2000):
report = dict(
status="not_applicable",
source_ref=dict(path=path, sha256=source_sha256),
relations=[],
assumptions=ASSUMPTIONS[:],
unknowns=UNKNOWNS[:],
coverage=VERSION,
acceptance_proof=False,
)
def unknown(reason):
report["unknowns"].append(reason)
if not isinstance(source, str) or len(source.encode("utf8")) > max_source:
return dict(report, status="unknown", unknowns=["source bound"])
if hashlib.sha256(source.encode("utf8")).hexdigest() != source_sha256:
return dict(report, status="unknown", unknowns=["source identity mismatch"])
try:
tree = ast.parse(source)
if sum(1 for _ in ast.walk(tree)) > max_nodes:
return dict(report, status="unknown", unknowns=["AST bound"])
except (SyntaxError, RecursionError, ValueError):
return dict(report, status="unknown", unknowns=["source not completely parseable"])
def names_bound(node):
bound = {
n.id
for n in ast.walk(node)
if isinstance(n, ast.Name) and isinstance(n.ctx, (ast.Store, ast.Del))
}
for value in ast.walk(node):
if isinstance(value, ast.Attribute) and isinstance(value.ctx, (ast.Store, ast.Del)):
base = value.value
while isinstance(base, ast.Attribute):
base = base.value
if isinstance(base, ast.Name):
bound.add(base.id)
bound.update(n.arg for n in ast.walk(node) if isinstance(n, ast.arg))
bound.update(
n.name
for n in ast.walk(node)
if isinstance(n, (ast.FunctionDef, ast.AsyncFunctionDef, ast.ClassDef))
)
bound.update(
a.asname or a.name.split(".")[0]
for n in ast.walk(node)
if isinstance(n, (ast.Import, ast.ImportFrom))
for a in n.names
)
return bound
aliases = {}
module_bindings = {}
for node in tree.body:
for name in (
names_bound(node)
if not isinstance(node, (ast.FunctionDef, ast.ClassDef))
else [node.name]
):
module_bindings[name] = module_bindings.get(name, 0) + 1
if isinstance(node, ast.Import):
for a in node.names:
if a.name in ("torch", "triton", "triton.language"):
aliases[a.asname or a.name.split(".")[0]] = (
a.name if a.asname else a.name.split(".")[0]
)
if isinstance(node, ast.ImportFrom) and node.module in (
"torch",
"triton",
"triton.language",
):
for a in node.names:
if a.name != "*":
aliases[a.asname or a.name] = node.module + "." + a.name
aliases = {k: v for k, v in aliases.items() if module_bindings.get(k) == 1}
def resolved(node, bindings):
if isinstance(node, ast.Name):
return bindings.get(node.id)
if isinstance(node, ast.Attribute):
base = resolved(node.value, bindings)
return base + "." + node.attr if base else None
return None
def local_aliases(fn):
return {k: v for k, v in aliases.items() if k not in names_bound(fn)}
kernels = {}
for fn in tree.body:
if not isinstance(fn, ast.FunctionDef) or module_bindings.get(fn.name) != 1:
continue
if len(fn.decorator_list) == 1 and resolved(fn.decorator_list[0], aliases) == "triton.jit":
kernels[fn.name] = fn
hosts = [
(n.name, n) for n in tree.body if isinstance(n, ast.FunctionDef) and n.name not in kernels
]
hosts += [
(c.name + "." + n.name, n)
for c in tree.body
if isinstance(c, ast.ClassDef)
for n in c.body
if isinstance(n, ast.FunctionDef)
]
for host_name, host in hosts[:16]:
if entry_symbol is not None and host_name != entry_symbol:
continue
imports = local_aliases(host)
host_bound = names_bound(host)
assignments = {}
for row in host.body:
if (
isinstance(row, ast.Assign)
and len(row.targets) == 1
and isinstance(row.targets[0], ast.Name)
):
assignments.setdefault(row.targets[0].id, []).append(row)
# Only direct top-level launches/returns. Branches,helpers and aliases
# never silently establish a complete write/ownership analysis.
returns = [
row
for row in host.body
if isinstance(row, ast.Return) and isinstance(row.value, ast.Name)
]
launches = [
row.value
for row in host.body
if isinstance(row, ast.Expr)
and isinstance(row.value, ast.Call)
and isinstance(row.value.func, ast.Subscript)
]
if any(
isinstance(n, (ast.If, ast.For, ast.While, ast.Try, ast.With)) for n in ast.walk(host)
):
unknown(host_name + ":control flow not modeled")
for launch in launches:
callee = launch.func.value
if (
not isinstance(callee, ast.Name)
or callee.id not in kernels
or callee.id in host_bound
):
unknown(host_name + ":unresolved or shadowed launch")
continue
kernel = kernels[callee.id]
params = kernel.args.posonlyargs + kernel.args.args
formal_names = [a.arg for a in params] + [a.arg for a in kernel.args.kwonlyargs]
if (
kernel.args.vararg
or kernel.args.kwarg
or any(isinstance(a, ast.Starred) for a in launch.args)
or any(k.arg is None for k in launch.keywords)
):
unknown(host_name + ":dynamic argument binding")
continue
if len(launch.args) > len(params):
unknown(host_name + ":invalid positional binding")
continue
binding = dict(zip([a.arg for a in params], launch.args))
valid = True
for kw in launch.keywords:
if kw.arg in binding:
valid = False
elif kw.arg in formal_names:
binding[kw.arg] = kw.value
elif kw.arg not in ("num_warps", "num_stages", "num_ctas", "enable_fp_fusion"):
valid = False
if not valid:
unknown(host_name + ":ambiguous argument binding")
continue
rebound = {
n.id
for n in ast.walk(kernel)
if isinstance(n, ast.Name) and isinstance(n.ctx, (ast.Store, ast.Del))
}
kernel_imports = local_aliases(kernel)
for store in ast.walk(kernel):
if not isinstance(store, ast.Call):
continue
if resolved(store.func, kernel_imports) != "triton.language.store":
if isinstance(store.func, ast.Attribute) and store.func.attr == "store":
unknown(host_name + ":store binding not established")
continue
pointer = (
store.args[0]
if store.args
else next((k.value for k in store.keywords if k.arg == "pointer"), None)
)
base = pointer
index_terms = []
while isinstance(base, ast.BinOp) and isinstance(base.op, ast.Add):
index_terms.append(base.right)
base = base.left
if not isinstance(base, ast.Name) or base.id not in binding or base.id in rebound:
unknown(host_name + ":unknown store pointer root or parameter reassignment")
continue
if any(
n.id in formal_names
for term in index_terms
for n in ast.walk(term)
if isinstance(n, ast.Name)
):
unknown(
host_name
+ ":index contains another formal;pointer/scalar distinction unknown"
)
continue
actual = binding[base.id]
for ret in returns[:2]:
name = ret.value.id
writes = [
n
for n in ast.walk(host)
if isinstance(n, ast.Name)
and n.id == name
and isinstance(n.ctx, (ast.Store, ast.Del))
]
allocation = assignments.get(name, [])
allocation = allocation[0] if len(allocation) == len(writes) == 1 else None
allocated = (
allocation is not None
and allocation.lineno < launch.lineno
and isinstance(allocation.value, ast.Call)
and resolved(allocation.value.func, imports)
in (
"torch.empty",
"torch.empty_like",
"torch.zeros",
"torch.zeros_like",
"torch.ones",
"torch.ones_like",
)
)
actuals = list(binding.values())
report["relations"].append(
dict(
host=host_name,
kernel=kernel.name,
store_parameter=base.id,
launch_argument=ast.unparse(actual)[:160],
returned_name=name,
return_origin="direct_allocation_call" if allocated else "unknown",
allocation_line=allocation.lineno if allocated else None,
returned_name_directly_passed=any(
isinstance(a, ast.Name) and a.id == name for a in actuals
),
source_lines=dict(
store=store.lineno, launch=launch.lineno, returned=ret.lineno
),
interpretation="Syntactic parameter/argument/return connection only;absence of a direct argument does not prove absent writes through aliases or other calls.",
)
)
if len(report["relations"]) == 4:
break
if len(report["relations"]) == 4:
break
if len(report["relations"]) == 4:
break
if len(report["relations"]) == 4:
break
report["unknowns"] = list(dict.fromkeys(report["unknowns"]))[:8]
report["status"] = (
"source_relations"
if report["relations"]
else "unknown"
if len(report["unknowns"]) > len(UNKNOWNS)
else "not_applicable"
)
return report