]>
git.proxmox.com Git - mirror_edk2.git/blob - AppPkg/Applications/Python/Python-2.7.10/Python/peephole.c
1 /* Peephole optimizations for bytecode compiler. */
5 #include "Python-ast.h"
14 #define GETARG(arr, i) ((int)((arr[i+2]<<8) + arr[i+1]))
15 #define UNCONDITIONAL_JUMP(op) (op==JUMP_ABSOLUTE || op==JUMP_FORWARD)
16 #define CONDITIONAL_JUMP(op) (op==POP_JUMP_IF_FALSE || op==POP_JUMP_IF_TRUE \
17 || op==JUMP_IF_FALSE_OR_POP || op==JUMP_IF_TRUE_OR_POP)
18 #define ABSOLUTE_JUMP(op) (op==JUMP_ABSOLUTE || op==CONTINUE_LOOP \
19 || op==POP_JUMP_IF_FALSE || op==POP_JUMP_IF_TRUE \
20 || op==JUMP_IF_FALSE_OR_POP || op==JUMP_IF_TRUE_OR_POP)
21 #define JUMPS_ON_TRUE(op) (op==POP_JUMP_IF_TRUE || op==JUMP_IF_TRUE_OR_POP)
22 #define GETJUMPTGT(arr, i) (GETARG(arr,i) + (ABSOLUTE_JUMP(arr[i]) ? 0 : i+3))
23 #define SETARG(arr, i, val) arr[i+2] = val>>8; arr[i+1] = val & 255
24 #define CODESIZE(op) (HAS_ARG(op) ? 3 : 1)
25 #define ISBASICBLOCK(blocks, start, bytes) \
26 (blocks[start]==blocks[start+bytes-1])
28 /* Replace LOAD_CONST c1. LOAD_CONST c2 ... LOAD_CONST cn BUILD_TUPLE n
29 with LOAD_CONST (c1, c2, ... cn).
30 The consts table must still be in list form so that the
31 new constant (c1, c2, ... cn) can be appended.
32 Called with codestr pointing to the first LOAD_CONST.
33 Bails out with no change if one or more of the LOAD_CONSTs is missing.
34 Also works for BUILD_LIST when followed by an "in" or "not in" test.
37 tuple_of_constants(unsigned char *codestr
, Py_ssize_t n
, PyObject
*consts
)
39 PyObject
*newconst
, *constant
;
40 Py_ssize_t i
, arg
, len_consts
;
43 assert(PyList_CheckExact(consts
));
44 assert(codestr
[n
*3] == BUILD_TUPLE
|| codestr
[n
*3] == BUILD_LIST
);
45 assert(GETARG(codestr
, (n
*3)) == n
);
47 assert(codestr
[i
*3] == LOAD_CONST
);
49 /* Buildup new tuple of constants */
50 newconst
= PyTuple_New(n
);
53 len_consts
= PyList_GET_SIZE(consts
);
54 for (i
=0 ; i
<n
; i
++) {
55 arg
= GETARG(codestr
, (i
*3));
56 assert(arg
< len_consts
);
57 constant
= PyList_GET_ITEM(consts
, arg
);
59 PyTuple_SET_ITEM(newconst
, i
, constant
);
62 /* Append folded constant onto consts */
63 if (PyList_Append(consts
, newconst
)) {
69 /* Write NOPs over old LOAD_CONSTS and
70 add a new LOAD_CONST newconst on top of the BUILD_TUPLE n */
71 memset(codestr
, NOP
, n
*3);
72 codestr
[n
*3] = LOAD_CONST
;
73 SETARG(codestr
, (n
*3), len_consts
);
77 /* Replace LOAD_CONST c1. LOAD_CONST c2 BINOP
78 with LOAD_CONST binop(c1,c2)
79 The consts table must still be in list form so that the
80 new constant can be appended.
81 Called with codestr pointing to the first LOAD_CONST.
82 Abandons the transformation if the folding fails (i.e. 1+'a').
83 If the new constant is a sequence, only folds when the size
84 is below a threshold value. That keeps pyc files from
85 becoming large in the presence of code like: (None,)*1000.
88 fold_binops_on_constants(unsigned char *codestr
, PyObject
*consts
)
90 PyObject
*newconst
, *v
, *w
;
91 Py_ssize_t len_consts
, size
;
95 assert(PyList_CheckExact(consts
));
96 assert(codestr
[0] == LOAD_CONST
);
97 assert(codestr
[3] == LOAD_CONST
);
99 /* Create new constant */
100 v
= PyList_GET_ITEM(consts
, GETARG(codestr
, 0));
101 w
= PyList_GET_ITEM(consts
, GETARG(codestr
, 3));
105 newconst
= PyNumber_Power(v
, w
, Py_None
);
107 case BINARY_MULTIPLY
:
108 newconst
= PyNumber_Multiply(v
, w
);
111 /* Cannot fold this operation statically since
112 the result can depend on the run-time presence
115 case BINARY_TRUE_DIVIDE
:
116 newconst
= PyNumber_TrueDivide(v
, w
);
118 case BINARY_FLOOR_DIVIDE
:
119 newconst
= PyNumber_FloorDivide(v
, w
);
122 newconst
= PyNumber_Remainder(v
, w
);
125 newconst
= PyNumber_Add(v
, w
);
127 case BINARY_SUBTRACT
:
128 newconst
= PyNumber_Subtract(v
, w
);
131 /* #5057: if v is unicode, there might be differences between
132 wide and narrow builds in cases like '\U00012345'[0] or
133 '\U00012345abcdef'[3], so it's better to skip the optimization
134 in order to produce compatible pycs.
136 if (PyUnicode_Check(v
))
138 newconst
= PyObject_GetItem(v
, w
);
141 newconst
= PyNumber_Lshift(v
, w
);
144 newconst
= PyNumber_Rshift(v
, w
);
147 newconst
= PyNumber_And(v
, w
);
150 newconst
= PyNumber_Xor(v
, w
);
153 newconst
= PyNumber_Or(v
, w
);
156 /* Called with an unknown opcode */
157 PyErr_Format(PyExc_SystemError
,
158 "unexpected binary operation %d on a constant",
162 if (newconst
== NULL
) {
166 size
= PyObject_Size(newconst
);
169 else if (size
> 20) {
174 /* Append folded constant into consts table */
175 len_consts
= PyList_GET_SIZE(consts
);
176 if (PyList_Append(consts
, newconst
)) {
182 /* Write NOP NOP NOP NOP LOAD_CONST newconst */
183 memset(codestr
, NOP
, 4);
184 codestr
[4] = LOAD_CONST
;
185 SETARG(codestr
, 4, len_consts
);
190 fold_unaryops_on_constants(unsigned char *codestr
, PyObject
*consts
)
192 PyObject
*newconst
=NULL
, *v
;
193 Py_ssize_t len_consts
;
197 assert(PyList_CheckExact(consts
));
198 assert(codestr
[0] == LOAD_CONST
);
200 /* Create new constant */
201 v
= PyList_GET_ITEM(consts
, GETARG(codestr
, 0));
205 /* Preserve the sign of -0.0 */
206 if (PyObject_IsTrue(v
) == 1)
207 newconst
= PyNumber_Negative(v
);
210 newconst
= PyObject_Repr(v
);
213 newconst
= PyNumber_Invert(v
);
216 /* Called with an unknown opcode */
217 PyErr_Format(PyExc_SystemError
,
218 "unexpected unary operation %d on a constant",
222 if (newconst
== NULL
) {
227 /* Append folded constant into consts table */
228 len_consts
= PyList_GET_SIZE(consts
);
229 if (PyList_Append(consts
, newconst
)) {
235 /* Write NOP LOAD_CONST newconst */
237 codestr
[1] = LOAD_CONST
;
238 SETARG(codestr
, 1, len_consts
);
242 static unsigned int *
243 markblocks(unsigned char *code
, Py_ssize_t len
)
245 unsigned int *blocks
= PyMem_New(unsigned int, len
);
246 int i
,j
, opcode
, blockcnt
= 0;
248 if (blocks
== NULL
) {
252 memset(blocks
, 0, len
*sizeof(int));
254 /* Mark labels in the first pass */
255 for (i
=0 ; i
<len
; i
+=CODESIZE(opcode
)) {
260 case JUMP_IF_FALSE_OR_POP
:
261 case JUMP_IF_TRUE_OR_POP
:
262 case POP_JUMP_IF_FALSE
:
263 case POP_JUMP_IF_TRUE
:
270 j
= GETJUMPTGT(code
, i
);
275 /* Build block numbers in the second pass */
276 for (i
=0 ; i
<len
; i
++) {
277 blockcnt
+= blocks
[i
]; /* increment blockcnt over labels */
278 blocks
[i
] = blockcnt
;
283 /* Perform basic peephole optimizations to components of a code object.
284 The consts object should still be in list form to allow new constants
287 To keep the optimizer simple, it bails out (does nothing) for code
288 containing extended arguments or that has a length over 32,700. That
289 allows us to avoid overflow and sign issues. Likewise, it bails when
290 the lineno table has complex encoding for gaps >= 255.
292 Optimizations are restricted to simple transformations occuring within a
293 single basic block. All transformations keep the code size the same or
294 smaller. For those that reduce size, the gaps are initially filled with
295 NOPs. Later those NOPs are removed and the jump addresses retargeted in
296 a single pass. Line numbering is adjusted accordingly. */
299 PyCode_Optimize(PyObject
*code
, PyObject
* consts
, PyObject
*names
,
300 PyObject
*lineno_obj
)
302 Py_ssize_t i
, j
, codelen
;
304 int tgt
, tgttgt
, opcode
;
305 unsigned char *codestr
= NULL
;
306 unsigned char *lineno
;
308 int new_line
, cum_orig_line
, last_line
, tabsiz
;
309 int cumlc
=0, lastlc
=0; /* Count runs of consecutive LOAD_CONSTs */
310 unsigned int *blocks
= NULL
;
313 /* Bail out if an exception is set */
314 if (PyErr_Occurred())
317 /* Bypass optimization when the lineno table is too complex */
318 assert(PyString_Check(lineno_obj
));
319 lineno
= (unsigned char*)PyString_AS_STRING(lineno_obj
);
320 tabsiz
= PyString_GET_SIZE(lineno_obj
);
321 if (memchr(lineno
, 255, tabsiz
) != NULL
)
324 /* Avoid situations where jump retargeting could overflow */
325 assert(PyString_Check(code
));
326 codelen
= PyString_GET_SIZE(code
);
330 /* Make a modifiable copy of the code string */
331 codestr
= (unsigned char *)PyMem_Malloc(codelen
);
334 codestr
= (unsigned char *)memcpy(codestr
,
335 PyString_AS_STRING(code
), codelen
);
337 /* Verify that RETURN_VALUE terminates the codestring. This allows
338 the various transformation patterns to look ahead several
339 instructions without additional checks to make sure they are not
340 looking beyond the end of the code string.
342 if (codestr
[codelen
-1] != RETURN_VALUE
)
345 /* Mapping to new jump targets after NOPs are removed */
346 addrmap
= PyMem_New(int, codelen
);
347 if (addrmap
== NULL
) {
352 blocks
= markblocks(codestr
, codelen
);
355 assert(PyList_Check(consts
));
357 for (i
=0 ; i
<codelen
; i
+= CODESIZE(codestr
[i
])) {
365 /* Replace UNARY_NOT POP_JUMP_IF_FALSE
366 with POP_JUMP_IF_TRUE */
368 if (codestr
[i
+1] != POP_JUMP_IF_FALSE
369 || !ISBASICBLOCK(blocks
,i
,4))
371 j
= GETARG(codestr
, i
+1);
372 codestr
[i
] = POP_JUMP_IF_TRUE
;
373 SETARG(codestr
, i
, j
);
375 goto reoptimize_current
;
377 /* not a is b --> a is not b
378 not a in b --> a not in b
379 not a is not b --> a is b
380 not a not in b --> a in b
383 j
= GETARG(codestr
, i
);
384 if (j
< 6 || j
> 9 ||
385 codestr
[i
+3] != UNARY_NOT
||
386 !ISBASICBLOCK(blocks
,i
,4))
388 SETARG(codestr
, i
, (j
^1));
392 /* Replace LOAD_GLOBAL/LOAD_NAME None
393 with LOAD_CONST None */
396 j
= GETARG(codestr
, i
);
397 name
= PyString_AsString(PyTuple_GET_ITEM(names
, j
));
398 if (name
== NULL
|| strcmp(name
, "None") != 0)
400 for (j
=0 ; j
< PyList_GET_SIZE(consts
) ; j
++) {
401 if (PyList_GET_ITEM(consts
, j
) == Py_None
)
404 if (j
== PyList_GET_SIZE(consts
)) {
405 if (PyList_Append(consts
, Py_None
) == -1)
408 assert(PyList_GET_ITEM(consts
, j
) == Py_None
);
409 codestr
[i
] = LOAD_CONST
;
410 SETARG(codestr
, i
, j
);
414 /* Skip over LOAD_CONST trueconst
415 POP_JUMP_IF_FALSE xx. This improves
416 "while 1" performance. */
419 j
= GETARG(codestr
, i
);
420 if (codestr
[i
+3] != POP_JUMP_IF_FALSE
||
421 !ISBASICBLOCK(blocks
,i
,6) ||
422 !PyObject_IsTrue(PyList_GET_ITEM(consts
, j
)))
424 memset(codestr
+i
, NOP
, 6);
428 /* Try to fold tuples of constants (includes a case for lists
429 which are only used for "in" and "not in" tests).
430 Skip over BUILD_SEQN 1 UNPACK_SEQN 1.
431 Replace BUILD_SEQN 2 UNPACK_SEQN 2 with ROT2.
432 Replace BUILD_SEQN 3 UNPACK_SEQN 3 with ROT3 ROT2. */
435 j
= GETARG(codestr
, i
);
439 ((opcode
== BUILD_TUPLE
&&
440 ISBASICBLOCK(blocks
, h
, 3*(j
+1))) ||
441 (opcode
== BUILD_LIST
&&
442 codestr
[i
+3]==COMPARE_OP
&&
443 ISBASICBLOCK(blocks
, h
, 3*(j
+2)) &&
444 (GETARG(codestr
,i
+3)==6 ||
445 GETARG(codestr
,i
+3)==7))) &&
446 tuple_of_constants(&codestr
[h
], j
, consts
)) {
447 assert(codestr
[i
] == LOAD_CONST
);
451 if (codestr
[i
+3] != UNPACK_SEQUENCE
||
452 !ISBASICBLOCK(blocks
,i
,6) ||
453 j
!= GETARG(codestr
, i
+3))
456 memset(codestr
+i
, NOP
, 6);
458 codestr
[i
] = ROT_TWO
;
459 memset(codestr
+i
+1, NOP
, 5);
461 codestr
[i
] = ROT_THREE
;
462 codestr
[i
+1] = ROT_TWO
;
463 memset(codestr
+i
+2, NOP
, 4);
467 /* Fold binary ops on constants.
468 LOAD_CONST c1 LOAD_CONST c2 BINOP --> LOAD_CONST binop(c1,c2) */
470 case BINARY_MULTIPLY
:
471 case BINARY_TRUE_DIVIDE
:
472 case BINARY_FLOOR_DIVIDE
:
475 case BINARY_SUBTRACT
:
483 ISBASICBLOCK(blocks
, i
-6, 7) &&
484 fold_binops_on_constants(&codestr
[i
-6], consts
)) {
486 assert(codestr
[i
] == LOAD_CONST
);
491 /* Fold unary ops on constants.
492 LOAD_CONST c1 UNARY_OP --> LOAD_CONST unary_op(c) */
497 ISBASICBLOCK(blocks
, i
-3, 4) &&
498 fold_unaryops_on_constants(&codestr
[i
-3], consts
)) {
500 assert(codestr
[i
] == LOAD_CONST
);
505 /* Simplify conditional jump to conditional jump where the
506 result of the first test implies the success of a similar
507 test or the failure of the opposite test.
513 x:JUMP_IF_FALSE_OR_POP y y:JUMP_IF_FALSE_OR_POP z
514 --> x:JUMP_IF_FALSE_OR_POP z
515 x:JUMP_IF_FALSE_OR_POP y y:JUMP_IF_TRUE_OR_POP z
516 --> x:POP_JUMP_IF_FALSE y+3
517 where y+3 is the instruction following the second test.
519 case JUMP_IF_FALSE_OR_POP
:
520 case JUMP_IF_TRUE_OR_POP
:
521 tgt
= GETJUMPTGT(codestr
, i
);
523 if (CONDITIONAL_JUMP(j
)) {
524 /* NOTE: all possible jumps here are absolute! */
525 if (JUMPS_ON_TRUE(j
) == JUMPS_ON_TRUE(opcode
)) {
526 /* The second jump will be
527 taken iff the first is. */
528 tgttgt
= GETJUMPTGT(codestr
, tgt
);
529 /* The current opcode inherits
530 its target's stack behaviour */
532 SETARG(codestr
, i
, tgttgt
);
533 goto reoptimize_current
;
535 /* The second jump is not taken if the first is (so
536 jump past it), and all conditional jumps pop their
537 argument when they're not taken (so change the
538 first jump to pop its argument when it's taken). */
539 if (JUMPS_ON_TRUE(opcode
))
540 codestr
[i
] = POP_JUMP_IF_TRUE
;
542 codestr
[i
] = POP_JUMP_IF_FALSE
;
543 SETARG(codestr
, i
, (tgt
+ 3));
544 goto reoptimize_current
;
547 /* Intentional fallthrough */
549 /* Replace jumps to unconditional jumps */
550 case POP_JUMP_IF_FALSE
:
551 case POP_JUMP_IF_TRUE
:
560 tgt
= GETJUMPTGT(codestr
, i
);
561 /* Replace JUMP_* to a RETURN into just a RETURN */
562 if (UNCONDITIONAL_JUMP(opcode
) &&
563 codestr
[tgt
] == RETURN_VALUE
) {
564 codestr
[i
] = RETURN_VALUE
;
565 memset(codestr
+i
+1, NOP
, 2);
568 if (!UNCONDITIONAL_JUMP(codestr
[tgt
]))
570 tgttgt
= GETJUMPTGT(codestr
, tgt
);
571 if (opcode
== JUMP_FORWARD
) /* JMP_ABS can go backwards */
572 opcode
= JUMP_ABSOLUTE
;
573 if (!ABSOLUTE_JUMP(opcode
))
574 tgttgt
-= i
+ 3; /* Calc relative jump addr */
575 if (tgttgt
< 0) /* No backward relative jumps */
578 SETARG(codestr
, i
, tgttgt
);
584 /* Replace RETURN LOAD_CONST None RETURN with just RETURN */
585 /* Remove unreachable JUMPs after RETURN */
589 if (codestr
[i
+4] == RETURN_VALUE
&&
590 ISBASICBLOCK(blocks
,i
,5))
591 memset(codestr
+i
+1, NOP
, 4);
592 else if (UNCONDITIONAL_JUMP(codestr
[i
+1]) &&
593 ISBASICBLOCK(blocks
,i
,4))
594 memset(codestr
+i
+1, NOP
, 3);
599 /* Fixup linenotab */
600 for (i
=0, nops
=0 ; i
<codelen
; i
+= CODESIZE(codestr
[i
])) {
601 addrmap
[i
] = i
- nops
;
602 if (codestr
[i
] == NOP
)
607 for (i
=0 ; i
< tabsiz
; i
+=2) {
608 cum_orig_line
+= lineno
[i
];
609 new_line
= addrmap
[cum_orig_line
];
610 assert (new_line
- last_line
< 255);
611 lineno
[i
] =((unsigned char)(new_line
- last_line
));
612 last_line
= new_line
;
615 /* Remove NOPs and fixup jump targets */
616 for (i
=0, h
=0 ; i
<codelen
; ) {
625 case POP_JUMP_IF_FALSE
:
626 case POP_JUMP_IF_TRUE
:
627 case JUMP_IF_FALSE_OR_POP
:
628 case JUMP_IF_TRUE_OR_POP
:
629 j
= addrmap
[GETARG(codestr
, i
)];
630 SETARG(codestr
, i
, j
);
639 j
= addrmap
[GETARG(codestr
, i
) + i
+ 3] - addrmap
[i
] - 3;
640 SETARG(codestr
, i
, j
);
643 adj
= CODESIZE(opcode
);
645 codestr
[h
++] = codestr
[i
++];
647 assert(h
+ nops
== codelen
);
649 code
= PyString_FromStringAndSize((char *)codestr
, h
);