Debian Codegraph @

Tools/cases_generator/analyzer.py

raw
1 from dataclasses import dataclass
2 import itertools
3 import lexer
4 import parser
5 import re
6 from typing import Optional, Callable
7
8 from parser import Stmt, SimpleStmt, BlockStmt, IfStmt, WhileStmt
9
10 @dataclass
11 class EscapingCall:
12 stmt: SimpleStmt
13 call: lexer.Token
14 kills: lexer.Token | None
15
16 @dataclass
17 class Properties:
18 escaping_calls: dict[SimpleStmt, EscapingCall]
19 escapes: bool
20 error_with_pop: bool
21 error_without_pop: bool
22 deopts: bool
23 oparg: bool
24 jumps: bool
25 eval_breaker: bool
26 needs_this: bool
27 always_exits: bool
28 stores_sp: bool
29 uses_co_consts: bool
30 uses_co_names: bool
31 uses_locals: bool
32 has_free: bool
33 side_exit: bool
34 pure: bool
35 uses_opcode: bool
36 tier: int | None = None
37 const_oparg: int = -1
38 needs_prev: bool = False
39 no_save_ip: bool = False
40
41 def dump(self, indent: str) -> None:
42 simple_properties = self.__dict__.copy()
43 del simple_properties["escaping_calls"]
44 text = "escaping_calls:\n"
45 for tkns in self.escaping_calls.values():
46 text += f"{indent} {tkns}\n"
47 text += ", ".join([f"{key}: {value}" for (key, value) in simple_properties.items()])
48 print(indent, text, sep="")
49
50 @staticmethod
51 def from_list(properties: list["Properties"]) -> "Properties":
52 escaping_calls: dict[SimpleStmt, EscapingCall] = {}
53 for p in properties:
54 escaping_calls.update(p.escaping_calls)
55 return Properties(
56 escaping_calls=escaping_calls,
57 escapes = any(p.escapes for p in properties),
58 error_with_pop=any(p.error_with_pop for p in properties),
59 error_without_pop=any(p.error_without_pop for p in properties),
60 deopts=any(p.deopts for p in properties),
61 oparg=any(p.oparg for p in properties),
62 jumps=any(p.jumps for p in properties),
63 eval_breaker=any(p.eval_breaker for p in properties),
64 needs_this=any(p.needs_this for p in properties),
65 always_exits=any(p.always_exits for p in properties),
66 stores_sp=any(p.stores_sp for p in properties),
67 uses_co_consts=any(p.uses_co_consts for p in properties),
68 uses_co_names=any(p.uses_co_names for p in properties),
69 uses_locals=any(p.uses_locals for p in properties),
70 uses_opcode=any(p.uses_opcode for p in properties),
71 has_free=any(p.has_free for p in properties),
72 side_exit=any(p.side_exit for p in properties),
73 pure=all(p.pure for p in properties),
74 needs_prev=any(p.needs_prev for p in properties),
75 no_save_ip=all(p.no_save_ip for p in properties),
76 )
77
78 @property
79 def infallible(self) -> bool:
80 return not self.error_with_pop and not self.error_without_pop
81
82 SKIP_PROPERTIES = Properties(
83 escaping_calls={},
84 escapes=False,
85 error_with_pop=False,
86 error_without_pop=False,
87 deopts=False,
88 oparg=False,
89 jumps=False,
90 eval_breaker=False,
91 needs_this=False,
92 always_exits=False,
93 stores_sp=False,
94 uses_co_consts=False,
95 uses_co_names=False,
96 uses_locals=False,
97 uses_opcode=False,
98 has_free=False,
99 side_exit=False,
100 pure=True,
101 no_save_ip=False,
102 )
103
104
105 @dataclass
106 class Skip:
107 "Unused cache entry"
108 size: int
109
110 @property
111 def name(self) -> str:
112 return f"unused/{self.size}"
113
114 @property
115 def properties(self) -> Properties:
116 return SKIP_PROPERTIES
117
118
119 class Flush:
120 @property
121 def properties(self) -> Properties:
122 return SKIP_PROPERTIES
123
124 @property
125 def name(self) -> str:
126 return "flush"
127
128 @property
129 def size(self) -> int:
130 return 0
131
132
133
134
135 @dataclass
136 class StackItem:
137 name: str
138 type: str | None
139 size: str
140 peek: bool = False
141 used: bool = False
142
143 def __str__(self) -> str:
144 size = f"[{self.size}]" if self.size else ""
145 type = "" if self.type is None else f"{self.type} "
146 return f"{type}{self.name}{size} {self.peek}"
147
148 def is_array(self) -> bool:
149 return self.size != ""
150
151 def get_size(self) -> str:
152 return self.size if self.size else "1"
153
154
155 @dataclass
156 class StackEffect:
157 inputs: list[StackItem]
158 outputs: list[StackItem]
159
160 def __str__(self) -> str:
161 return f"({', '.join([str(i) for i in self.inputs])} -- {', '.join([str(i) for i in self.outputs])})"
162
163
164 @dataclass
165 class CacheEntry:
166 name: str
167 size: int
168
169 def __str__(self) -> str:
170 return f"{self.name}/{self.size}"
171
172
173 @dataclass
174 class Uop:
175 name: str
176 context: parser.Context | None
177 annotations: list[str]
178 stack: StackEffect
179 caches: list[CacheEntry]
180 local_stores: list[lexer.Token]
181 body: BlockStmt
182 properties: Properties
183 _size: int = -1
184 implicitly_created: bool = False
185 replicated = 0
186 replicates: "Uop | None" = None
187 # Size of the instruction(s), only set for uops containing the INSTRUCTION_SIZE macro
188 instruction_size: int | None = None
189
190 def dump(self, indent: str) -> None:
191 print(
192 indent, self.name, ", ".join(self.annotations) if self.annotations else ""
193 )
194 print(indent, self.stack, ", ".join([str(c) for c in self.caches]))
195 self.properties.dump(" " + indent)
196
197 @property
198 def size(self) -> int:
199 if self._size < 0:
200 self._size = sum(c.size for c in self.caches)
201 return self._size
202
203 def why_not_viable(self) -> str | None:
204 if self.name == "_SAVE_RETURN_OFFSET":
205 return None # Adjusts next_instr, but only in tier 1 code
206 if "INSTRUMENTED" in self.name:
207 return "is instrumented"
208 if "replaced" in self.annotations:
209 return "is replaced"
210 if self.name in ("INTERPRETER_EXIT", "JUMP_BACKWARD"):
211 return "has tier 1 control flow"
212 if self.properties.needs_this:
213 return "uses the 'this_instr' variable"
214 if len([c for c in self.caches if c.name != "unused"]) > 2:
215 return "has too many cache entries"
216 if self.properties.error_with_pop and self.properties.error_without_pop:
217 return "has both popping and not-popping errors"
218 return None
219
220 def is_viable(self) -> bool:
221 return self.why_not_viable() is None
222
223 def is_super(self) -> bool:
224 for tkn in self.body.tokens():
225 if tkn.kind == "IDENTIFIER" and tkn.text == "oparg1":
226 return True
227 return False
228
229
230 class Label:
231
232 def __init__(self, name: str, spilled: bool, body: BlockStmt, properties: Properties):
233 self.name = name
234 self.spilled = spilled
235 self.body = body
236 self.properties = properties
237
238 size:int = 0
239 local_stores: list[lexer.Token] = []
240 instruction_size = None
241
242 def __str__(self) -> str:
243 return f"label({self.name})"
244
245
246 Part = Uop | Skip | Flush
247 CodeSection = Uop | Label
248
249
250 @dataclass
251 class Instruction:
252 where: lexer.Token
253 name: str
254 parts: list[Part]
255 _properties: Properties | None
256 is_target: bool = False
257 family: Optional["Family"] = None
258 opcode: int = -1
259
260 @property
261 def properties(self) -> Properties:
262 if self._properties is None:
263 self._properties = self._compute_properties()
264 return self._properties
265
266 def _compute_properties(self) -> Properties:
267 return Properties.from_list([part.properties for part in self.parts])
268
269 def dump(self, indent: str) -> None:
270 print(indent, self.name, "=", ", ".join([part.name for part in self.parts]))
271 self.properties.dump(" " + indent)
272
273 @property
274 def size(self) -> int:
275 return 1 + sum(part.size for part in self.parts)
276
277 def is_super(self) -> bool:
278 if len(self.parts) != 1:
279 return False
280 uop = self.parts[0]
281 if isinstance(uop, Uop):
282 return uop.is_super()
283 else:
284 return False
285
286
287 @dataclass
288 class PseudoInstruction:
289 name: str
290 stack: StackEffect
291 targets: list[Instruction]
292 as_sequence: bool
293 flags: list[str]
294 opcode: int = -1
295
296 def dump(self, indent: str) -> None:
297 print(indent, self.name, "->", " or ".join([t.name for t in self.targets]))
298
299 @property
300 def properties(self) -> Properties:
301 return Properties.from_list([i.properties for i in self.targets])
302
303
304 @dataclass
305 class Family:
306 name: str
307 size: str
308 members: list[Instruction]
309
310 def dump(self, indent: str) -> None:
311 print(indent, self.name, "= ", ", ".join([m.name for m in self.members]))
312
313
314 @dataclass
315 class Analysis:
316 instructions: dict[str, Instruction]
317 uops: dict[str, Uop]
318 families: dict[str, Family]
319 pseudos: dict[str, PseudoInstruction]
320 labels: dict[str, Label]
321 opmap: dict[str, int]
322 have_arg: int
323 min_instrumented: int
324
325
326 def analysis_error(message: str, tkn: lexer.Token) -> SyntaxError:
327 # To do -- support file and line output
328 # Construct a SyntaxError instance from message and token
329 return lexer.make_syntax_error(message, tkn.filename, tkn.line, tkn.column, "")
330
331
332 def override_error(
333 name: str,
334 context: parser.Context | None,
335 prev_context: parser.Context | None,
336 token: lexer.Token,
337 ) -> SyntaxError:
338 return analysis_error(
339 f"Duplicate definition of '{name}' @ {context} "
340 f"previous definition @ {prev_context}",
341 token,
342 )
343
344
345 def convert_stack_item(
346 item: parser.StackEffect, replace_op_arg_1: str | None
347 ) -> StackItem:
348 return StackItem(item.name, item.type, item.size)
349
350 def check_unused(stack: list[StackItem], input_names: dict[str, lexer.Token]) -> None:
351 "Unused items cannot be on the stack above used, non-peek items"
352 seen_unused = False
353 for item in reversed(stack):
354 if item.name == "unused":
355 seen_unused = True
356 elif item.peek:
357 break
358 elif seen_unused:
359 raise analysis_error(f"Cannot have used input '{item.name}' below an unused value on the stack", input_names[item.name])
360
361
362 def analyze_stack(
363 op: parser.InstDef | parser.Pseudo, replace_op_arg_1: str | None = None
364 ) -> StackEffect:
365 inputs: list[StackItem] = [
366 convert_stack_item(i, replace_op_arg_1)
367 for i in op.inputs
368 if isinstance(i, parser.StackEffect)
369 ]
370 outputs: list[StackItem] = [
371 convert_stack_item(i, replace_op_arg_1) for i in op.outputs
372 ]
373 # Mark variables with matching names at the base of the stack as "peek"
374 modified = False
375 input_names: dict[str, lexer.Token] = { i.name : i.first_token for i in op.inputs if i.name != "unused" }
376 for input, output in itertools.zip_longest(inputs, outputs):
377 if output is None:
378 pass
379 elif input is None:
380 if output.name in input_names:
381 raise analysis_error(
382 f"Reuse of variable '{output.name}' at different stack location",
383 input_names[output.name])
384 elif input.name == output.name:
385 if not modified:
386 input.peek = output.peek = True
387 else:
388 modified = True
389 if output.name in input_names:
390 raise analysis_error(
391 f"Reuse of variable '{output.name}' at different stack location",
392 input_names[output.name])
393 if isinstance(op, parser.InstDef):
394 output_names = [out.name for out in outputs]
395 for input in inputs:
396 if (
397 variable_used(op, input.name)
398 or variable_used(op, "DECREF_INPUTS")
399 or (not input.peek and input.name in output_names)
400 ):
401 input.used = True
402 for output in outputs:
403 if variable_used(op, output.name):
404 output.used = True
405 check_unused(inputs, input_names)
406 return StackEffect(inputs, outputs)
407
408
409 def analyze_caches(inputs: list[parser.InputEffect]) -> list[CacheEntry]:
410 caches: list[parser.CacheEffect] = [
411 i for i in inputs if isinstance(i, parser.CacheEffect)
412 ]
413 if caches:
414 # Middle entries are allowed to be unused. Check first and last caches.
415 for index in (0, -1):
416 cache = caches[index]
417 if cache.name == "unused":
418 position = "First" if index == 0 else "Last"
419 msg = f"{position} cache entry in op is unused. Move to enclosing macro."
420 raise analysis_error(msg, cache.tokens[0])
421 return [CacheEntry(i.name, int(i.size)) for i in caches]
422
423
424 def find_variable_stores(node: parser.InstDef) -> list[lexer.Token]:
425 res: list[lexer.Token] = []
426 outnames = { out.name for out in node.outputs }
427 innames = { out.name for out in node.inputs }
428
429 def find_stores_in_tokens(tokens: list[lexer.Token], callback: Callable[[lexer.Token], None]) -> None:
430 while tokens and tokens[0].kind == "COMMENT":
431 tokens = tokens[1:]
432 if len(tokens) < 4:
433 return
434 if tokens[1].kind == "EQUALS":
435 if tokens[0].kind == "IDENTIFIER":
436 name = tokens[0].text
437 if name in outnames or name in innames:
438 callback(tokens[0])
439 #Passing the address of a local is also a definition
440 for idx, tkn in enumerate(tokens):
441 if tkn.kind == "AND":
442 name_tkn = tokens[idx+1]
443 if name_tkn.text in outnames:
444 callback(name_tkn)
445
446 def visit(stmt: Stmt) -> None:
447 if isinstance(stmt, IfStmt):
448 def error(tkn: lexer.Token) -> None:
449 raise analysis_error("Cannot define variable in 'if' condition", tkn)
450 find_stores_in_tokens(stmt.condition, error)
451 elif isinstance(stmt, SimpleStmt):
452 find_stores_in_tokens(stmt.contents, res.append)
453
454 node.block.accept(visit)
455 return res
456
457
458 #def analyze_deferred_refs(node: parser.InstDef) -> dict[lexer.Token, str | None]:
459 #"""Look for PyStackRef_FromPyObjectNew() calls"""
460
461 #def in_frame_push(idx: int) -> bool:
462 #for tkn in reversed(node.block.tokens[: idx - 1]):
463 #if tkn.kind in {"SEMI", "LBRACE", "RBRACE"}:
464 #return False
465 #if tkn.kind == "IDENTIFIER" and tkn.text == "_PyFrame_PushUnchecked":
466 #return True
467 #return False
468
469 #refs: dict[lexer.Token, str | None] = {}
470 #for idx, tkn in enumerate(node.block.tokens):
471 #if tkn.kind != "IDENTIFIER" or tkn.text != "PyStackRef_FromPyObjectNew":
472 #continue
473
474 #if idx == 0 or node.block.tokens[idx - 1].kind != "EQUALS":
475 #if in_frame_push(idx):
476 ## PyStackRef_FromPyObjectNew() is called in _PyFrame_PushUnchecked()
477 #refs[tkn] = None
478 #continue
479 #raise analysis_error("Expected '=' before PyStackRef_FromPyObjectNew", tkn)
480
481 #lhs = find_assignment_target(node, idx - 1)
482 #if len(lhs) == 0:
483 #raise analysis_error(
484 #"PyStackRef_FromPyObjectNew() must be assigned to an output", tkn
485 #)
486
487 #if lhs[0].kind == "TIMES" or any(
488 #t.kind == "ARROW" or t.kind == "LBRACKET" for t in lhs[1:]
489 #):
490 ## Don't handle: *ptr = ..., ptr->field = ..., or ptr[field] = ...
491 ## Assume that they are visible to the GC.
492 #refs[tkn] = None
493 #continue
494
495 #if len(lhs) != 1 or lhs[0].kind != "IDENTIFIER":
496 #raise analysis_error(
497 #"PyStackRef_FromPyObjectNew() must be assigned to an output", tkn
498 #)
499
500 #name = lhs[0].text
501 #match = (
502 #any(var.name == name for var in node.inputs)
503 #or any(var.name == name for var in node.outputs)
504 #)
505 #if not match:
506 #raise analysis_error(
507 #f"PyStackRef_FromPyObjectNew() must be assigned to an input or output, not '{name}'",
508 #tkn,
509 #)
510
511 #refs[tkn] = name
512
513 #return refs
514
515
516 def variable_used(node: parser.CodeDef, name: str) -> bool:
517 """Determine whether a variable with a given name is used in a node."""
518 return any(
519 token.kind == "IDENTIFIER" and token.text == name for token in node.block.tokens()
520 )
521
522
523 def oparg_used(node: parser.CodeDef) -> bool:
524 """Determine whether `oparg` is used in a node."""
525 return any(
526 token.kind == "IDENTIFIER" and token.text == "oparg" for token in node.tokens
527 )
528
529
530 def tier_variable(node: parser.CodeDef) -> int | None:
531 """Determine whether a tier variable is used in a node."""
532 if isinstance(node, parser.LabelDef):
533 return None
534 for token in node.tokens:
535 if token.kind == "ANNOTATION":
536 if token.text == "specializing":
537 return 1
538 if re.fullmatch(r"tier\d", token.text):
539 return int(token.text[-1])
540 return None
541
542
543 def has_error_with_pop(op: parser.CodeDef) -> bool:
544 return (
545 variable_used(op, "ERROR_IF")
546 or variable_used(op, "exception_unwind")
547 )
548
549
550 def has_error_without_pop(op: parser.CodeDef) -> bool:
551 return (
552 variable_used(op, "ERROR_NO_POP")
553 or variable_used(op, "exception_unwind")
554 )
555
556
557 NON_ESCAPING_FUNCTIONS = (
558 "PyCFunction_GET_FLAGS",
559 "PyCFunction_GET_FUNCTION",
560 "PyCFunction_GET_SELF",
561 "PyCell_GetRef",
562 "PyCell_New",
563 "PyCell_SwapTakeRef",
564 "PyExceptionInstance_Class",
565 "PyException_GetCause",
566 "PyException_GetContext",
567 "PyException_GetTraceback",
568 "PyFloat_AS_DOUBLE",
569 "PyFloat_FromDouble",
570 "PyFunction_GET_CODE",
571 "PyFunction_GET_GLOBALS",
572 "PyList_GET_ITEM",
573 "PyList_GET_SIZE",
574 "PyList_SET_ITEM",
575 "PyLong_AsLong",
576 "PyLong_FromLong",
577 "PyLong_FromSsize_t",
578 "PySlice_New",
579 "PyStackRef_AsPyObjectBorrow",
580 "PyStackRef_AsPyObjectNew",
581 "PyStackRef_FromPyObjectNewMortal",
582 "PyStackRef_AsPyObjectSteal",
583 "PyStackRef_Borrow",
584 "PyStackRef_CLEAR",
585 "PyStackRef_CLOSE_SPECIALIZED",
586 "PyStackRef_DUP",
587 "PyStackRef_False",
588 "PyStackRef_FromPyObjectImmortal",
589 "PyStackRef_FromPyObjectNew",
590 "PyStackRef_FromPyObjectSteal",
591 "PyStackRef_IsExactly",
592 "PyStackRef_FromPyObjectStealMortal",
593 "PyStackRef_IsNone",
594 "PyStackRef_Is",
595 "PyStackRef_IsHeapSafe",
596 "PyStackRef_IsTrue",
597 "PyStackRef_IsFalse",
598 "PyStackRef_IsNull",
599 "PyStackRef_MakeHeapSafe",
600 "PyStackRef_None",
601 "PyStackRef_TYPE",
602 "PyStackRef_True",
603 "PyTuple_GET_ITEM",
604 "PyTuple_GET_SIZE",
605 "PyType_HasFeature",
606 "PyUnicode_Concat",
607 "PyUnicode_GET_LENGTH",
608 "PyUnicode_READ_CHAR",
609 "Py_ARRAY_LENGTH",
610 "Py_FatalError",
611 "Py_INCREF",
612 "Py_IS_TYPE",
613 "Py_NewRef",
614 "Py_REFCNT",
615 "Py_SIZE",
616 "Py_TYPE",
617 "Py_UNREACHABLE",
618 "Py_Unicode_GET_LENGTH",
619 "_PyCode_CODE",
620 "_PyDictValues_AddToInsertionOrder",
621 "_PyErr_Occurred",
622 "_PyFloat_FromDouble_ConsumeInputs",
623 "_PyFrame_GetBytecode",
624 "_PyFrame_GetCode",
625 "_PyFrame_IsIncomplete",
626 "_PyFrame_PushUnchecked",
627 "_PyFrame_SetStackPointer",
628 "_PyFrame_StackPush",
629 "_PyFunction_SetVersion",
630 "_PyGen_GetGeneratorFromFrame",
631 "_PyInterpreterState_GET",
632 "_PyList_AppendTakeRef",
633 "_PyList_ITEMS",
634 "_PyLong_CompactValue",
635 "_PyLong_DigitCount",
636 "_PyLong_IsCompact",
637 "_PyLong_IsNegative",
638 "_PyLong_IsNonNegativeCompact",
639 "_PyLong_IsZero",
640 "_PyManagedDictPointer_IsValues",
641 "_PyObject_GC_IS_SHARED",
642 "_PyObject_GC_IS_TRACKED",
643 "_PyObject_GC_MAY_BE_TRACKED",
644 "_PyObject_GC_TRACK",
645 "_PyObject_GetManagedDict",
646 "_PyObject_InlineValues",
647 "_PyObject_IsUniquelyReferenced",
648 "_PyObject_ManagedDictPointer",
649 "_PyThreadState_HasStackSpace",
650 "_PyTuple_FromStackRefStealOnSuccess",
651 "_PyTuple_ITEMS",
652 "_PyType_HasFeature",
653 "_PyType_NewManagedObject",
654 "_PyUnicode_Equal",
655 "_PyUnicode_JoinArray",
656 "_Py_CHECK_EMSCRIPTEN_SIGNALS_PERIODICALLY",
657 "_Py_DECREF_NO_DEALLOC",
658 "_Py_ID",
659 "_Py_IsImmortal",
660 "_Py_IsOwnedByCurrentThread",
661 "_Py_LeaveRecursiveCallPy",
662 "_Py_LeaveRecursiveCallTstate",
663 "_Py_NewRef",
664 "_Py_SINGLETON",
665 "_Py_STR",
666 "_Py_TryIncrefCompare",
667 "_Py_TryIncrefCompareStackRef",
668 "_Py_atomic_compare_exchange_uint8",
669 "_Py_atomic_load_ptr_acquire",
670 "_Py_atomic_load_uintptr_relaxed",
671 "_Py_set_eval_breaker_bit",
672 "advance_backoff_counter",
673 "assert",
674 "backoff_counter_triggers",
675 "initial_temperature_backoff_counter",
676 "JUMP_TO_LABEL",
677 "restart_backoff_counter",
678 "_Py_ReachedRecursionLimit",
679 "PyStackRef_IsTaggedInt",
680 "PyStackRef_TagInt",
681 "PyStackRef_UntagInt",
682 )
683
684 def check_escaping_calls(instr: parser.CodeDef, escapes: dict[SimpleStmt, EscapingCall]) -> None:
685 error: lexer.Token | None = None
686 calls = {e.call for e in escapes.values()}
687
688 def visit(stmt: Stmt) -> None:
689 nonlocal error
690 if isinstance(stmt, IfStmt) or isinstance(stmt, WhileStmt):
691 for tkn in stmt.condition:
692 if tkn in calls:
693 error = tkn
694 elif isinstance(stmt, SimpleStmt):
695 in_if = 0
696 tkn_iter = iter(stmt.contents)
697 for tkn in tkn_iter:
698 if tkn.kind == "IDENTIFIER" and tkn.text in ("DEOPT_IF", "ERROR_IF", "EXIT_IF"):
699 in_if = 1
700 next(tkn_iter)
701 elif tkn.kind == "LPAREN":
702 if in_if:
703 in_if += 1
704 elif tkn.kind == "RPAREN":
705 if in_if:
706 in_if -= 1
707 elif tkn in calls and in_if:
708 error = tkn
709
710
711 instr.block.accept(visit)
712 if error is not None:
713 raise analysis_error(f"Escaping call '{error.text} in condition", error)
714
715 def find_escaping_api_calls(instr: parser.CodeDef) -> dict[SimpleStmt, EscapingCall]:
716 result: dict[SimpleStmt, EscapingCall] = {}
717
718 def visit(stmt: Stmt) -> None:
719 if not isinstance(stmt, SimpleStmt):
720 return
721 tokens = stmt.contents
722 for idx, tkn in enumerate(tokens):
723 try:
724 next_tkn = tokens[idx+1]
725 except IndexError:
726 break
727 if next_tkn.kind != lexer.LPAREN:
728 continue
729 if tkn.kind == lexer.IDENTIFIER:
730 if tkn.text.upper() == tkn.text:
731 # simple macro
732 continue
733 #if not tkn.text.startswith(("Py", "_Py", "monitor")):
734 # continue
735 if tkn.text.startswith(("sym_", "optimize_")):
736 # Optimize functions
737 continue
738 if tkn.text.endswith("Check"):
739 continue
740 if tkn.text.startswith("Py_Is"):
741 continue
742 if tkn.text.endswith("CheckExact"):
743 continue
744 if tkn.text in NON_ESCAPING_FUNCTIONS:
745 continue
746 elif tkn.kind == "RPAREN":
747 prev = tokens[idx-1]
748 if prev.text.endswith("_t") or prev.text == "*" or prev.text == "int":
749 #cast
750 continue
751 elif tkn.kind != "RBRACKET":
752 continue
753 if tkn.text in ("PyStackRef_CLOSE", "PyStackRef_XCLOSE"):
754 if len(tokens) <= idx+2:
755 raise analysis_error("Unexpected end of file", next_tkn)
756 kills = tokens[idx+2]
757 if kills.kind != "IDENTIFIER":
758 raise analysis_error(f"Expected identifier, got '{kills.text}'", kills)
759 else:
760 kills = None
761 result[stmt] = EscapingCall(stmt, tkn, kills)
762
763 instr.block.accept(visit)
764 check_escaping_calls(instr, result)
765 return result
766
767
768 EXITS = {
769 "DISPATCH",
770 "Py_UNREACHABLE",
771 "DISPATCH_INLINED",
772 "DISPATCH_GOTO",
773 }
774
775
776 def always_exits(op: parser.CodeDef) -> bool:
777 depth = 0
778 tkn_iter = iter(op.tokens)
779 for tkn in tkn_iter:
780 if tkn.kind == "LBRACE":
781 depth += 1
782 elif tkn.kind == "RBRACE":
783 depth -= 1
784 elif depth > 1:
785 continue
786 elif tkn.kind == "GOTO" or tkn.kind == "RETURN":
787 return True
788 elif tkn.kind == "KEYWORD":
789 if tkn.text in EXITS:
790 return True
791 elif tkn.kind == "IDENTIFIER":
792 if tkn.text in EXITS:
793 return True
794 if tkn.text == "DEOPT_IF" or tkn.text == "ERROR_IF":
795 next(tkn_iter) # '('
796 t = next(tkn_iter)
797 if t.text in ("true", "1"):
798 return True
799 return False
800
801
802 def stack_effect_only_peeks(instr: parser.InstDef) -> bool:
803 stack_inputs = [s for s in instr.inputs if not isinstance(s, parser.CacheEffect)]
804 if len(stack_inputs) != len(instr.outputs):
805 return False
806 if len(stack_inputs) == 0:
807 return False
808 return all(
809 (s.name == other.name and s.type == other.type and s.size == other.size)
810 for s, other in zip(stack_inputs, instr.outputs)
811 )
812
813
814 def compute_properties(op: parser.CodeDef) -> Properties:
815 escaping_calls = find_escaping_api_calls(op)
816 has_free = (
817 variable_used(op, "PyCell_New")
818 or variable_used(op, "PyCell_GetRef")
819 or variable_used(op, "PyCell_SetTakeRef")
820 or variable_used(op, "PyCell_SwapTakeRef")
821 )
822 deopts_if = variable_used(op, "DEOPT_IF")
823 exits_if = variable_used(op, "EXIT_IF")
824 if deopts_if and exits_if:
825 tkn = op.tokens[0]
826 raise lexer.make_syntax_error(
827 "Op cannot contain both EXIT_IF and DEOPT_IF",
828 tkn.filename,
829 tkn.line,
830 tkn.column,
831 op.name,
832 )
833 error_with_pop = has_error_with_pop(op)
834 error_without_pop = has_error_without_pop(op)
835 escapes = bool(escaping_calls)
836 pure = False if isinstance(op, parser.LabelDef) else "pure" in op.annotations
837 no_save_ip = False if isinstance(op, parser.LabelDef) else "no_save_ip" in op.annotations
838 return Properties(
839 escaping_calls=escaping_calls,
840 escapes=escapes,
841 error_with_pop=error_with_pop,
842 error_without_pop=error_without_pop,
843 deopts=deopts_if,
844 side_exit=exits_if,
845 oparg=oparg_used(op),
846 jumps=variable_used(op, "JUMPBY"),
847 eval_breaker="CHECK_PERIODIC" in op.name,
848 needs_this=variable_used(op, "this_instr"),
849 always_exits=always_exits(op),
850 stores_sp=variable_used(op, "SYNC_SP"),
851 uses_co_consts=variable_used(op, "FRAME_CO_CONSTS"),
852 uses_co_names=variable_used(op, "FRAME_CO_NAMES"),
853 uses_locals=variable_used(op, "GETLOCAL") and not has_free,
854 uses_opcode=variable_used(op, "opcode"),
855 has_free=has_free,
856 pure=pure,
857 no_save_ip=no_save_ip,
858 tier=tier_variable(op),
859 needs_prev=variable_used(op, "prev_instr"),
860 )
861
862
863 def make_uop(
864 name: str,
865 op: parser.InstDef,
866 inputs: list[parser.InputEffect],
867 uops: dict[str, Uop],
868 ) -> Uop:
869 result = Uop(
870 name=name,
871 context=op.context,
872 annotations=op.annotations,
873 stack=analyze_stack(op),
874 caches=analyze_caches(inputs),
875 local_stores=find_variable_stores(op),
876 body=op.block,
877 properties=compute_properties(op),
878 )
879 for anno in op.annotations:
880 if anno.startswith("replicate"):
881 result.replicated = int(anno[10:-1])
882 break
883 else:
884 return result
885 for oparg in range(result.replicated):
886 name_x = name + "_" + str(oparg)
887 properties = compute_properties(op)
888 properties.oparg = False
889 properties.const_oparg = oparg
890 rep = Uop(
891 name=name_x,
892 context=op.context,
893 annotations=op.annotations,
894 stack=analyze_stack(op),
895 caches=analyze_caches(inputs),
896 local_stores=find_variable_stores(op),
897 body=op.block,
898 properties=properties,
899 )
900 rep.replicates = result
901 uops[name_x] = rep
902
903 return result
904
905
906 def add_op(op: parser.InstDef, uops: dict[str, Uop]) -> None:
907 assert op.kind == "op"
908 if op.name in uops:
909 if "override" not in op.annotations:
910 raise override_error(
911 op.name, op.context, uops[op.name].context, op.tokens[0]
912 )
913 uops[op.name] = make_uop(op.name, op, op.inputs, uops)
914
915
916 def add_instruction(
917 where: lexer.Token,
918 name: str,
919 parts: list[Part],
920 instructions: dict[str, Instruction],
921 ) -> None:
922 instructions[name] = Instruction(where, name, parts, None)
923
924
925 def desugar_inst(
926 inst: parser.InstDef, instructions: dict[str, Instruction], uops: dict[str, Uop]
927 ) -> None:
928 assert inst.kind == "inst"
929 name = inst.name
930 op_inputs: list[parser.InputEffect] = []
931 parts: list[Part] = []
932 uop_index = -1
933 # Move unused cache entries to the Instruction, removing them from the Uop.
934 for input in inst.inputs:
935 if isinstance(input, parser.CacheEffect) and input.name == "unused":
936 parts.append(Skip(input.size))
937 else:
938 op_inputs.append(input)
939 if uop_index < 0:
940 uop_index = len(parts)
941 # Place holder for the uop.
942 parts.append(Skip(0))
943 uop = make_uop("_" + inst.name, inst, op_inputs, uops)
944 uop.implicitly_created = True
945 uops[inst.name] = uop
946 if uop_index < 0:
947 parts.append(uop)
948 else:
949 parts[uop_index] = uop
950 add_instruction(inst.first_token, name, parts, instructions)
951
952
953 def add_macro(
954 macro: parser.Macro, instructions: dict[str, Instruction], uops: dict[str, Uop]
955 ) -> None:
956 parts: list[Part] = []
957 for part in macro.uops:
958 match part:
959 case parser.OpName():
960 if part.name == "flush":
961 parts.append(Flush())
962 else:
963 if part.name not in uops:
964 raise analysis_error(
965 f"No Uop named {part.name}", macro.tokens[0]
966 )
967 parts.append(uops[part.name])
968 case parser.CacheEffect():
969 parts.append(Skip(part.size))
970 case _:
971 assert False
972 assert parts
973 add_instruction(macro.first_token, macro.name, parts, instructions)
974
975
976 def add_family(
977 pfamily: parser.Family,
978 instructions: dict[str, Instruction],
979 families: dict[str, Family],
980 ) -> None:
981 family = Family(
982 pfamily.name,
983 pfamily.size,
984 [instructions[member_name] for member_name in pfamily.members],
985 )
986 for member in family.members:
987 member.family = family
988 # The head of the family is an implicit jump target for DEOPTs
989 instructions[family.name].is_target = True
990 families[family.name] = family
991
992
993 def add_pseudo(
994 pseudo: parser.Pseudo,
995 instructions: dict[str, Instruction],
996 pseudos: dict[str, PseudoInstruction],
997 ) -> None:
998 pseudos[pseudo.name] = PseudoInstruction(
999 pseudo.name,
1000 analyze_stack(pseudo),
1001 [instructions[target] for target in pseudo.targets],
1002 pseudo.as_sequence,
1003 pseudo.flags,
1004 )
1005
1006
1007 def add_label(
1008 label: parser.LabelDef,
1009 labels: dict[str, Label],
1010 ) -> None:
1011 properties = compute_properties(label)
1012 labels[label.name] = Label(label.name, label.spilled, label.block, properties)
1013
1014
1015 def assign_opcodes(
1016 instructions: dict[str, Instruction],
1017 families: dict[str, Family],
1018 pseudos: dict[str, PseudoInstruction],
1019 ) -> tuple[dict[str, int], int, int]:
1020 """Assigns opcodes, then returns the opmap,
1021 have_arg and min_instrumented values"""
1022 instmap: dict[str, int] = {}
1023
1024 # 0 is reserved for cache entries. This helps debugging.
1025 instmap["CACHE"] = 0
1026
1027 # 17 is reserved as it is the initial value for the specializing counter.
1028 # This helps catch cases where we attempt to execute a cache.
1029 instmap["RESERVED"] = 17
1030
1031 # 128 is RESUME - it is hard coded as such in Tools/build/deepfreeze.py
1032 instmap["RESUME"] = 128
1033
1034 # This is an historical oddity.
1035 instmap["BINARY_OP_INPLACE_ADD_UNICODE"] = 3
1036
1037 instmap["INSTRUMENTED_LINE"] = 254
1038 instmap["ENTER_EXECUTOR"] = 255
1039
1040 instrumented = [name for name in instructions if name.startswith("INSTRUMENTED")]
1041
1042 specialized: set[str] = set()
1043 no_arg: list[str] = []
1044 has_arg: list[str] = []
1045
1046 for family in families.values():
1047 specialized.update(inst.name for inst in family.members)
1048
1049 for inst in instructions.values():
1050 name = inst.name
1051 if name in specialized:
1052 continue
1053 if name in instrumented:
1054 continue
1055 if inst.properties.oparg:
1056 has_arg.append(name)
1057 else:
1058 no_arg.append(name)
1059
1060 # Specialized ops appear in their own section
1061 # Instrumented opcodes are at the end of the valid range
1062 min_internal = instmap["RESUME"] + 1
1063 min_instrumented = 254 - (len(instrumented) - 1)
1064 assert min_internal + len(specialized) < min_instrumented
1065
1066 next_opcode = 1
1067
1068 def add_instruction(name: str) -> None:
1069 nonlocal next_opcode
1070 if name in instmap:
1071 return # Pre-defined name
1072 while next_opcode in instmap.values():
1073 next_opcode += 1
1074 instmap[name] = next_opcode
1075 next_opcode += 1
1076
1077 for name in sorted(no_arg):
1078 add_instruction(name)
1079 for name in sorted(has_arg):
1080 add_instruction(name)
1081 # For compatibility
1082 next_opcode = min_internal
1083 for name in sorted(specialized):
1084 add_instruction(name)
1085 next_opcode = min_instrumented
1086 for name in instrumented:
1087 add_instruction(name)
1088
1089 for name in instructions:
1090 instructions[name].opcode = instmap[name]
1091
1092 for op, name in enumerate(sorted(pseudos), 256):
1093 instmap[name] = op
1094 pseudos[name].opcode = op
1095
1096 return instmap, len(no_arg), min_instrumented
1097
1098
1099 def get_instruction_size_for_uop(instructions: dict[str, Instruction], uop: Uop) -> int | None:
1100 """Return the size of the instruction that contains the given uop or
1101 `None` if the uop does not contains the `INSTRUCTION_SIZE` macro.
1102
1103 If there is more than one instruction that contains the uop,
1104 ensure that they all have the same size.
1105 """
1106 for tkn in uop.body.tokens():
1107 if tkn.text == "INSTRUCTION_SIZE":
1108 break
1109 else:
1110 return None
1111
1112 size = None
1113 for inst in instructions.values():
1114 if uop in inst.parts:
1115 if size is None:
1116 size = inst.size
1117 if size != inst.size:
1118 raise analysis_error(
1119 "All instructions containing a uop with the `INSTRUCTION_SIZE` macro "
1120 f"must have the same size: {size} != {inst.size}",
1121 tkn
1122 )
1123 if size is None:
1124 raise analysis_error(f"No instruction containing the uop '{uop.name}' was found", tkn)
1125 return size
1126
1127
1128 def analyze_forest(forest: list[parser.AstNode]) -> Analysis:
1129 instructions: dict[str, Instruction] = {}
1130 uops: dict[str, Uop] = {}
1131 families: dict[str, Family] = {}
1132 pseudos: dict[str, PseudoInstruction] = {}
1133 labels: dict[str, Label] = {}
1134 for node in forest:
1135 match node:
1136 case parser.InstDef(name):
1137 if node.kind == "inst":
1138 desugar_inst(node, instructions, uops)
1139 else:
1140 assert node.kind == "op"
1141 add_op(node, uops)
1142 case parser.Macro():
1143 pass
1144 case parser.Family():
1145 pass
1146 case parser.Pseudo():
1147 pass
1148 case parser.LabelDef():
1149 pass
1150 case _:
1151 assert False
1152 for node in forest:
1153 if isinstance(node, parser.Macro):
1154 add_macro(node, instructions, uops)
1155 for node in forest:
1156 match node:
1157 case parser.Family():
1158 add_family(node, instructions, families)
1159 case parser.Pseudo():
1160 add_pseudo(node, instructions, pseudos)
1161 case parser.LabelDef():
1162 add_label(node, labels)
1163 case _:
1164 pass
1165 for uop in uops.values():
1166 uop.instruction_size = get_instruction_size_for_uop(instructions, uop)
1167 # Special case BINARY_OP_INPLACE_ADD_UNICODE
1168 # BINARY_OP_INPLACE_ADD_UNICODE is not a normal family member,
1169 # as it is the wrong size, but we need it to maintain an
1170 # historical optimization.
1171 if "BINARY_OP_INPLACE_ADD_UNICODE" in instructions:
1172 inst = instructions["BINARY_OP_INPLACE_ADD_UNICODE"]
1173 inst.family = families["BINARY_OP"]
1174 families["BINARY_OP"].members.append(inst)
1175 opmap, first_arg, min_instrumented = assign_opcodes(instructions, families, pseudos)
1176 return Analysis(
1177 instructions, uops, families, pseudos, labels, opmap, first_arg, min_instrumented
1178 )
1179
1180
1181 def analyze_files(filenames: list[str]) -> Analysis:
1182 return analyze_forest(parser.parse_files(filenames))
1183
1184
1185 def dump_analysis(analysis: Analysis) -> None:
1186 print("Uops:")
1187 for u in analysis.uops.values():
1188 u.dump(" ")
1189 print("Instructions:")
1190 for i in analysis.instructions.values():
1191 i.dump(" ")
1192 print("Families:")
1193 for f in analysis.families.values():
1194 f.dump(" ")
1195 print("Pseudos:")
1196 for p in analysis.pseudos.values():
1197 p.dump(" ")
1198
1199
1200 if __name__ == "__main__":
1201 import sys
1202
1203 if len(sys.argv) < 2:
1204 print("No input")
1205 else:
1206 filenames = sys.argv[1:]
1207 dump_analysis(analyze_files(filenames))