1 #ifdef _Py_TIER2
2
3 #include "Python.h"
4
5 #include "pycore_code.h"
6 #include "pycore_frame.h"
7 #include "pycore_long.h"
8 #include "pycore_optimizer.h"
9
10 #include <stdbool.h>
11 #include <stdint.h>
12 #include <stddef.h>
13
14 /* Symbols
15 =======
16
17 See the diagram at
18 https://github.com/faster-cpython/ideas/blob/main/3.13/redundancy_eliminator.md
19
20 We represent the nodes in the diagram as follows
21 (the flag bits are only defined in optimizer_symbols.c):
22 - Top: no flag bits, typ and const_val are NULL.
23 - NULL: IS_NULL flag set, type and const_val NULL.
24 - Not NULL: NOT_NULL flag set, type and const_val NULL.
25 - None/not None: not used. (None could be represented as any other constant.)
26 - Known type: NOT_NULL flag set and typ set; const_val is NULL.
27 - Known constant: NOT_NULL flag set, type set, const_val set.
28 - Bottom: IS_NULL and NOT_NULL flags set, type and const_val NULL.
29 */
30
31 // Flags for below.
32 #define IS_NULL 1 << 0
33 #define NOT_NULL 1 << 1
34
35 #ifdef Py_DEBUG
get_lltrace(void)36 static inline int get_lltrace(void) {
37 char *uop_debug = Py_GETENV("PYTHON_OPT_DEBUG");
38 int lltrace = 0;
39 if (uop_debug != NULL && *uop_debug >= '0') {
40 lltrace = *uop_debug - '0'; // TODO: Parse an int and all that
41 }
42 return lltrace;
43 }
44 #define DPRINTF(level, ...) \
45 if (get_lltrace() >= (level)) { printf(__VA_ARGS__); }
46 #else
47 #define DPRINTF(level, ...)
48 #endif
49
50 static _Py_UopsSymbol *
sym_new(_Py_UOpsContext * ctx)51 sym_new(_Py_UOpsContext *ctx)
52 {
53 _Py_UopsSymbol *self = &ctx->t_arena.arena[ctx->t_arena.ty_curr_number];
54 if (ctx->t_arena.ty_curr_number >= ctx->t_arena.ty_max_number) {
55 OPT_STAT_INC(optimizer_failure_reason_no_memory);
56 DPRINTF(1, "out of space for symbolic expression type\n");
57 return NULL;
58 }
59 ctx->t_arena.ty_curr_number++;
60 self->flags = 0;
61 self->typ = NULL;
62 self->const_val = NULL;
63
64 return self;
65 }
66
67 static inline void
sym_set_flag(_Py_UopsSymbol * sym,int flag)68 sym_set_flag(_Py_UopsSymbol *sym, int flag)
69 {
70 sym->flags |= flag;
71 }
72
73 static inline void
sym_set_bottom(_Py_UopsSymbol * sym)74 sym_set_bottom(_Py_UopsSymbol *sym)
75 {
76 sym_set_flag(sym, IS_NULL | NOT_NULL);
77 sym->typ = NULL;
78 Py_CLEAR(sym->const_val);
79 }
80
81 bool
_Py_uop_sym_is_bottom(_Py_UopsSymbol * sym)82 _Py_uop_sym_is_bottom(_Py_UopsSymbol *sym)
83 {
84 if ((sym->flags & IS_NULL) && (sym->flags & NOT_NULL)) {
85 assert(sym->flags == (IS_NULL | NOT_NULL));
86 assert(sym->typ == NULL);
87 assert(sym->const_val == NULL);
88 return true;
89 }
90 return false;
91 }
92
93 bool
_Py_uop_sym_is_not_null(_Py_UopsSymbol * sym)94 _Py_uop_sym_is_not_null(_Py_UopsSymbol *sym)
95 {
96 return sym->flags == NOT_NULL;
97 }
98
99 bool
_Py_uop_sym_is_null(_Py_UopsSymbol * sym)100 _Py_uop_sym_is_null(_Py_UopsSymbol *sym)
101 {
102 return sym->flags == IS_NULL;
103 }
104
105 bool
_Py_uop_sym_is_const(_Py_UopsSymbol * sym)106 _Py_uop_sym_is_const(_Py_UopsSymbol *sym)
107 {
108 return sym->const_val != NULL;
109 }
110
111 PyObject *
_Py_uop_sym_get_const(_Py_UopsSymbol * sym)112 _Py_uop_sym_get_const(_Py_UopsSymbol *sym)
113 {
114 return sym->const_val;
115 }
116
117 bool
_Py_uop_sym_set_type(_Py_UopsSymbol * sym,PyTypeObject * typ)118 _Py_uop_sym_set_type(_Py_UopsSymbol *sym, PyTypeObject *typ)
119 {
120 assert(typ != NULL && PyType_Check(typ));
121 if (sym->flags & IS_NULL) {
122 sym_set_bottom(sym);
123 return false;
124 }
125 if (sym->typ != NULL) {
126 if (sym->typ != typ) {
127 sym_set_bottom(sym);
128 return false;
129 }
130 }
131 else {
132 sym_set_flag(sym, NOT_NULL);
133 sym->typ = typ;
134 }
135 return true;
136 }
137
138 bool
_Py_uop_sym_set_const(_Py_UopsSymbol * sym,PyObject * const_val)139 _Py_uop_sym_set_const(_Py_UopsSymbol *sym, PyObject *const_val)
140 {
141 assert(const_val != NULL);
142 if (sym->flags & IS_NULL) {
143 sym_set_bottom(sym);
144 return false;
145 }
146 PyTypeObject *typ = Py_TYPE(const_val);
147 if (sym->typ != NULL && sym->typ != typ) {
148 sym_set_bottom(sym);
149 return false;
150 }
151 if (sym->const_val != NULL) {
152 if (sym->const_val != const_val) {
153 // TODO: What if they're equal?
154 sym_set_bottom(sym);
155 return false;
156 }
157 }
158 else {
159 sym_set_flag(sym, NOT_NULL);
160 sym->typ = typ;
161 sym->const_val = Py_NewRef(const_val);
162 }
163 return true;
164 }
165
166 bool
_Py_uop_sym_set_null(_Py_UopsSymbol * sym)167 _Py_uop_sym_set_null(_Py_UopsSymbol *sym)
168 {
169 if (_Py_uop_sym_is_not_null(sym)) {
170 sym_set_bottom(sym);
171 return false;
172 }
173 sym_set_flag(sym, IS_NULL);
174 return true;
175 }
176
177 bool
_Py_uop_sym_set_non_null(_Py_UopsSymbol * sym)178 _Py_uop_sym_set_non_null(_Py_UopsSymbol *sym)
179 {
180 if (_Py_uop_sym_is_null(sym)) {
181 sym_set_bottom(sym);
182 return false;
183 }
184 sym_set_flag(sym, NOT_NULL);
185 return true;
186 }
187
188
189 _Py_UopsSymbol *
_Py_uop_sym_new_unknown(_Py_UOpsContext * ctx)190 _Py_uop_sym_new_unknown(_Py_UOpsContext *ctx)
191 {
192 return sym_new(ctx);
193 }
194
195 _Py_UopsSymbol *
_Py_uop_sym_new_not_null(_Py_UOpsContext * ctx)196 _Py_uop_sym_new_not_null(_Py_UOpsContext *ctx)
197 {
198 _Py_UopsSymbol *res = _Py_uop_sym_new_unknown(ctx);
199 if (res == NULL) {
200 return NULL;
201 }
202 sym_set_flag(res, NOT_NULL);
203 return res;
204 }
205
206 _Py_UopsSymbol *
_Py_uop_sym_new_type(_Py_UOpsContext * ctx,PyTypeObject * typ)207 _Py_uop_sym_new_type(_Py_UOpsContext *ctx, PyTypeObject *typ)
208 {
209 _Py_UopsSymbol *res = sym_new(ctx);
210 if (res == NULL) {
211 return NULL;
212 }
213 _Py_uop_sym_set_type(res, typ);
214 return res;
215 }
216
217 // Adds a new reference to const_val, owned by the symbol.
218 _Py_UopsSymbol *
_Py_uop_sym_new_const(_Py_UOpsContext * ctx,PyObject * const_val)219 _Py_uop_sym_new_const(_Py_UOpsContext *ctx, PyObject *const_val)
220 {
221 assert(const_val != NULL);
222 _Py_UopsSymbol *res = sym_new(ctx);
223 if (res == NULL) {
224 return NULL;
225 }
226 _Py_uop_sym_set_const(res, const_val);
227 return res;
228 }
229
230 _Py_UopsSymbol *
_Py_uop_sym_new_null(_Py_UOpsContext * ctx)231 _Py_uop_sym_new_null(_Py_UOpsContext *ctx)
232 {
233 _Py_UopsSymbol *null_sym = _Py_uop_sym_new_unknown(ctx);
234 if (null_sym == NULL) {
235 return NULL;
236 }
237 _Py_uop_sym_set_null(null_sym);
238 return null_sym;
239 }
240
241 PyTypeObject *
_Py_uop_sym_get_type(_Py_UopsSymbol * sym)242 _Py_uop_sym_get_type(_Py_UopsSymbol *sym)
243 {
244 if (_Py_uop_sym_is_bottom(sym)) {
245 return NULL;
246 }
247 return sym->typ;
248 }
249
250 bool
_Py_uop_sym_has_type(_Py_UopsSymbol * sym)251 _Py_uop_sym_has_type(_Py_UopsSymbol *sym)
252 {
253 if (_Py_uop_sym_is_bottom(sym)) {
254 return false;
255 }
256 return sym->typ != NULL;
257 }
258
259 bool
_Py_uop_sym_matches_type(_Py_UopsSymbol * sym,PyTypeObject * typ)260 _Py_uop_sym_matches_type(_Py_UopsSymbol *sym, PyTypeObject *typ)
261 {
262 assert(typ != NULL && PyType_Check(typ));
263 return _Py_uop_sym_get_type(sym) == typ;
264 }
265
266 int
_Py_uop_sym_truthiness(_Py_UopsSymbol * sym)267 _Py_uop_sym_truthiness(_Py_UopsSymbol *sym)
268 {
269 /* There are some non-constant values for
270 * which `bool(val)` always evaluates to
271 * True or False, such as tuples with known
272 * length, but unknown contents, or bound-methods.
273 * This function will need updating
274 * should we support those values.
275 */
276 if (_Py_uop_sym_is_bottom(sym)) {
277 return -1;
278 }
279 if (!_Py_uop_sym_is_const(sym)) {
280 return -1;
281 }
282 PyObject *value = _Py_uop_sym_get_const(sym);
283 if (value == Py_None) {
284 return 0;
285 }
286 /* Only handle a few known safe types */
287 PyTypeObject *tp = Py_TYPE(value);
288 if (tp == &PyLong_Type) {
289 return !_PyLong_IsZero((PyLongObject *)value);
290 }
291 if (tp == &PyUnicode_Type) {
292 return value != &_Py_STR(empty);
293 }
294 if (tp == &PyBool_Type) {
295 return value == Py_True;
296 }
297 return -1;
298 }
299
300 // 0 on success, -1 on error.
301 _Py_UOpsAbstractFrame *
_Py_uop_frame_new(_Py_UOpsContext * ctx,PyCodeObject * co,int curr_stackentries,_Py_UopsSymbol ** args,int arg_len)302 _Py_uop_frame_new(
303 _Py_UOpsContext *ctx,
304 PyCodeObject *co,
305 int curr_stackentries,
306 _Py_UopsSymbol **args,
307 int arg_len)
308 {
309 assert(ctx->curr_frame_depth < MAX_ABSTRACT_FRAME_DEPTH);
310 _Py_UOpsAbstractFrame *frame = &ctx->frames[ctx->curr_frame_depth];
311
312 frame->stack_len = co->co_stacksize;
313 frame->locals_len = co->co_nlocalsplus;
314
315 frame->locals = ctx->n_consumed;
316 frame->stack = frame->locals + co->co_nlocalsplus;
317 frame->stack_pointer = frame->stack + curr_stackentries;
318 ctx->n_consumed = ctx->n_consumed + (co->co_nlocalsplus + co->co_stacksize);
319 if (ctx->n_consumed >= ctx->limit) {
320 return NULL;
321 }
322
323 // Initialize with the initial state of all local variables
324 for (int i = 0; i < arg_len; i++) {
325 frame->locals[i] = args[i];
326 }
327
328 for (int i = arg_len; i < co->co_nlocalsplus; i++) {
329 _Py_UopsSymbol *local = _Py_uop_sym_new_unknown(ctx);
330 frame->locals[i] = local;
331 }
332
333
334 // Initialize the stack as well
335 for (int i = 0; i < curr_stackentries; i++) {
336 _Py_UopsSymbol *stackvar = _Py_uop_sym_new_unknown(ctx);
337 frame->stack[i] = stackvar;
338 }
339
340 return frame;
341 }
342
343 void
_Py_uop_abstractcontext_fini(_Py_UOpsContext * ctx)344 _Py_uop_abstractcontext_fini(_Py_UOpsContext *ctx)
345 {
346 if (ctx == NULL) {
347 return;
348 }
349 ctx->curr_frame_depth = 0;
350 int tys = ctx->t_arena.ty_curr_number;
351 for (int i = 0; i < tys; i++) {
352 Py_CLEAR(ctx->t_arena.arena[i].const_val);
353 }
354 }
355
356 int
_Py_uop_abstractcontext_init(_Py_UOpsContext * ctx)357 _Py_uop_abstractcontext_init(_Py_UOpsContext *ctx)
358 {
359 ctx->limit = ctx->locals_and_stack + MAX_ABSTRACT_INTERP_SIZE;
360 ctx->n_consumed = ctx->locals_and_stack;
361 #ifdef Py_DEBUG // Aids debugging a little. There should never be NULL in the abstract interpreter.
362 for (int i = 0 ; i < MAX_ABSTRACT_INTERP_SIZE; i++) {
363 ctx->locals_and_stack[i] = NULL;
364 }
365 #endif
366
367 // Setup the arena for sym expressions.
368 ctx->t_arena.ty_curr_number = 0;
369 ctx->t_arena.ty_max_number = TY_ARENA_SIZE;
370
371 // Frame setup
372 ctx->curr_frame_depth = 0;
373
374 return 0;
375 }
376
377 int
_Py_uop_frame_pop(_Py_UOpsContext * ctx)378 _Py_uop_frame_pop(_Py_UOpsContext *ctx)
379 {
380 _Py_UOpsAbstractFrame *frame = ctx->frame;
381 ctx->n_consumed = frame->locals;
382 ctx->curr_frame_depth--;
383 assert(ctx->curr_frame_depth >= 1);
384 ctx->frame = &ctx->frames[ctx->curr_frame_depth - 1];
385
386 return 0;
387 }
388
389 #define TEST_PREDICATE(PRED, MSG) \
390 do { \
391 if (!(PRED)) { \
392 PyErr_SetString( \
393 PyExc_AssertionError, \
394 (MSG)); \
395 goto fail; \
396 } \
397 } while (0)
398
399 static _Py_UopsSymbol *
make_bottom(_Py_UOpsContext * ctx)400 make_bottom(_Py_UOpsContext *ctx)
401 {
402 _Py_UopsSymbol *sym = _Py_uop_sym_new_unknown(ctx);
403 _Py_uop_sym_set_null(sym);
404 _Py_uop_sym_set_non_null(sym);
405 return sym;
406 }
407
408 PyObject *
_Py_uop_symbols_test(PyObject * Py_UNUSED (self),PyObject * Py_UNUSED (ignored))409 _Py_uop_symbols_test(PyObject *Py_UNUSED(self), PyObject *Py_UNUSED(ignored))
410 {
411 _Py_UOpsContext context;
412 _Py_UOpsContext *ctx = &context;
413 _Py_uop_abstractcontext_init(ctx);
414 PyObject *val_42 = NULL;
415 PyObject *val_43 = NULL;
416
417 // Use a single 'sym' variable so copy-pasting tests is easier.
418 _Py_UopsSymbol *sym = _Py_uop_sym_new_unknown(ctx);
419 if (sym == NULL) {
420 goto fail;
421 }
422 TEST_PREDICATE(!_Py_uop_sym_is_null(sym), "top is NULL");
423 TEST_PREDICATE(!_Py_uop_sym_is_not_null(sym), "top is not NULL");
424 TEST_PREDICATE(!_Py_uop_sym_matches_type(sym, &PyLong_Type), "top matches a type");
425 TEST_PREDICATE(!_Py_uop_sym_is_const(sym), "top is a constant");
426 TEST_PREDICATE(_Py_uop_sym_get_const(sym) == NULL, "top as constant is not NULL");
427 TEST_PREDICATE(!_Py_uop_sym_is_bottom(sym), "top is bottom");
428
429 sym = make_bottom(ctx);
430 if (sym == NULL) {
431 goto fail;
432 }
433 TEST_PREDICATE(!_Py_uop_sym_is_null(sym), "bottom is NULL is not false");
434 TEST_PREDICATE(!_Py_uop_sym_is_not_null(sym), "bottom is not NULL is not false");
435 TEST_PREDICATE(!_Py_uop_sym_matches_type(sym, &PyLong_Type), "bottom matches a type");
436 TEST_PREDICATE(!_Py_uop_sym_is_const(sym), "bottom is a constant is not false");
437 TEST_PREDICATE(_Py_uop_sym_get_const(sym) == NULL, "bottom as constant is not NULL");
438 TEST_PREDICATE(_Py_uop_sym_is_bottom(sym), "bottom isn't bottom");
439
440 sym = _Py_uop_sym_new_type(ctx, &PyLong_Type);
441 if (sym == NULL) {
442 goto fail;
443 }
444 TEST_PREDICATE(!_Py_uop_sym_is_null(sym), "int is NULL");
445 TEST_PREDICATE(_Py_uop_sym_is_not_null(sym), "int isn't not NULL");
446 TEST_PREDICATE(_Py_uop_sym_matches_type(sym, &PyLong_Type), "int isn't int");
447 TEST_PREDICATE(!_Py_uop_sym_matches_type(sym, &PyFloat_Type), "int matches float");
448 TEST_PREDICATE(!_Py_uop_sym_is_const(sym), "int is a constant");
449 TEST_PREDICATE(_Py_uop_sym_get_const(sym) == NULL, "int as constant is not NULL");
450
451 _Py_uop_sym_set_type(sym, &PyLong_Type); // Should be a no-op
452 TEST_PREDICATE(_Py_uop_sym_matches_type(sym, &PyLong_Type), "(int and int) isn't int");
453
454 _Py_uop_sym_set_type(sym, &PyFloat_Type); // Should make it bottom
455 TEST_PREDICATE(_Py_uop_sym_is_bottom(sym), "(int and float) isn't bottom");
456
457 val_42 = PyLong_FromLong(42);
458 assert(val_42 != NULL);
459 assert(_Py_IsImmortal(val_42));
460
461 val_43 = PyLong_FromLong(43);
462 assert(val_43 != NULL);
463 assert(_Py_IsImmortal(val_43));
464
465 sym = _Py_uop_sym_new_type(ctx, &PyLong_Type);
466 if (sym == NULL) {
467 goto fail;
468 }
469 _Py_uop_sym_set_const(sym, val_42);
470 TEST_PREDICATE(_Py_uop_sym_truthiness(sym) == 1, "bool(42) is not True");
471 TEST_PREDICATE(!_Py_uop_sym_is_null(sym), "42 is NULL");
472 TEST_PREDICATE(_Py_uop_sym_is_not_null(sym), "42 isn't not NULL");
473 TEST_PREDICATE(_Py_uop_sym_matches_type(sym, &PyLong_Type), "42 isn't an int");
474 TEST_PREDICATE(!_Py_uop_sym_matches_type(sym, &PyFloat_Type), "42 matches float");
475 TEST_PREDICATE(_Py_uop_sym_is_const(sym), "42 is not a constant");
476 TEST_PREDICATE(_Py_uop_sym_get_const(sym) != NULL, "42 as constant is NULL");
477 TEST_PREDICATE(_Py_uop_sym_get_const(sym) == val_42, "42 as constant isn't 42");
478
479 _Py_uop_sym_set_type(sym, &PyLong_Type); // Should be a no-op
480 TEST_PREDICATE(_Py_uop_sym_matches_type(sym, &PyLong_Type), "(42 and 42) isn't an int");
481 TEST_PREDICATE(_Py_uop_sym_get_const(sym) == val_42, "(42 and 42) as constant isn't 42");
482
483 _Py_uop_sym_set_type(sym, &PyFloat_Type); // Should make it bottom
484 TEST_PREDICATE(_Py_uop_sym_is_bottom(sym), "(42 and float) isn't bottom");
485
486 sym = _Py_uop_sym_new_type(ctx, &PyLong_Type);
487 if (sym == NULL) {
488 goto fail;
489 }
490 _Py_uop_sym_set_const(sym, val_42);
491 _Py_uop_sym_set_const(sym, val_43); // Should make it bottom
492 TEST_PREDICATE(_Py_uop_sym_is_bottom(sym), "(42 and 43) isn't bottom");
493
494
495 sym = _Py_uop_sym_new_const(ctx, Py_None);
496 TEST_PREDICATE(_Py_uop_sym_truthiness(sym) == 0, "bool(None) is not False");
497 sym = _Py_uop_sym_new_const(ctx, Py_False);
498 TEST_PREDICATE(_Py_uop_sym_truthiness(sym) == 0, "bool(False) is not False");
499 sym = _Py_uop_sym_new_const(ctx, PyLong_FromLong(0));
500 TEST_PREDICATE(_Py_uop_sym_truthiness(sym) == 0, "bool(0) is not False");
501
502 _Py_uop_abstractcontext_fini(ctx);
503 Py_DECREF(val_42);
504 Py_DECREF(val_43);
505 Py_RETURN_NONE;
506
507 fail:
508 _Py_uop_abstractcontext_fini(ctx);
509 Py_XDECREF(val_42);
510 Py_XDECREF(val_43);
511 return NULL;
512 }
513
514 #endif /* _Py_TIER2 */
515