source: python/trunk/Python/peephole.c@ 281

Last change on this file since 281 was 2, checked in by Yuri Dario, 15 years ago

Initial import for vendor code.
  • Property svn:eol-style set to native
File size: 17.0 KB
Line 
1/* Peephole optimizations for bytecode compiler. */
2
3#include "Python.h"
4
5#include "Python-ast.h"
6#include "node.h"
7#include "pyarena.h"
8#include "ast.h"
9#include "code.h"
10#include "compile.h"
11#include "symtable.h"
12#include "opcode.h"
13
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 ABSOLUTE_JUMP(op) (op==JUMP_ABSOLUTE || op==CONTINUE_LOOP)
17#define GETJUMPTGT(arr, i) (GETARG(arr,i) + (ABSOLUTE_JUMP(arr[i]) ? 0 : i+3))
18#define SETARG(arr, i, val) arr[i+2] = val>>8; arr[i+1] = val & 255
19#define CODESIZE(op) (HAS_ARG(op) ? 3 : 1)
20#define ISBASICBLOCK(blocks, start, bytes) \
21 (blocks[start]==blocks[start+bytes-1])
22
23/* Replace LOAD_CONST c1. LOAD_CONST c2 ... LOAD_CONST cn BUILD_TUPLE n
24 with LOAD_CONST (c1, c2, ... cn).
25 The consts table must still be in list form so that the
26 new constant (c1, c2, ... cn) can be appended.
27 Called with codestr pointing to the first LOAD_CONST.
28 Bails out with no change if one or more of the LOAD_CONSTs is missing.
29 Also works for BUILD_LIST when followed by an "in" or "not in" test.
30*/
31static int
32tuple_of_constants(unsigned char *codestr, Py_ssize_t n, PyObject *consts)
33{
34 PyObject *newconst, *constant;
35 Py_ssize_t i, arg, len_consts;
36
37 /* Pre-conditions */
38 assert(PyList_CheckExact(consts));
39 assert(codestr[n*3] == BUILD_TUPLE || codestr[n*3] == BUILD_LIST);
40 assert(GETARG(codestr, (n*3)) == n);
41 for (i=0 ; i<n ; i++)
42 assert(codestr[i*3] == LOAD_CONST);
43
44 /* Buildup new tuple of constants */
45 newconst = PyTuple_New(n);
46 if (newconst == NULL)
47 return 0;
48 len_consts = PyList_GET_SIZE(consts);
49 for (i=0 ; i<n ; i++) {
50 arg = GETARG(codestr, (i*3));
51 assert(arg < len_consts);
52 constant = PyList_GET_ITEM(consts, arg);
53 Py_INCREF(constant);
54 PyTuple_SET_ITEM(newconst, i, constant);
55 }
56
57 /* Append folded constant onto consts */
58 if (PyList_Append(consts, newconst)) {
59 Py_DECREF(newconst);
60 return 0;
61 }
62 Py_DECREF(newconst);
63
64 /* Write NOPs over old LOAD_CONSTS and
65 add a new LOAD_CONST newconst on top of the BUILD_TUPLE n */
66 memset(codestr, NOP, n*3);
67 codestr[n*3] = LOAD_CONST;
68 SETARG(codestr, (n*3), len_consts);
69 return 1;
70}
71
72/* Replace LOAD_CONST c1. LOAD_CONST c2 BINOP
73 with LOAD_CONST binop(c1,c2)
74 The consts table must still be in list form so that the
75 new constant can be appended.
76 Called with codestr pointing to the first LOAD_CONST.
77 Abandons the transformation if the folding fails (i.e. 1+'a').
78 If the new constant is a sequence, only folds when the size
79 is below a threshold value. That keeps pyc files from
80 becoming large in the presence of code like: (None,)*1000.
81*/
82static int
83fold_binops_on_constants(unsigned char *codestr, PyObject *consts)
84{
85 PyObject *newconst, *v, *w;
86 Py_ssize_t len_consts, size;
87 int opcode;
88
89 /* Pre-conditions */
90 assert(PyList_CheckExact(consts));
91 assert(codestr[0] == LOAD_CONST);
92 assert(codestr[3] == LOAD_CONST);
93
94 /* Create new constant */
95 v = PyList_GET_ITEM(consts, GETARG(codestr, 0));
96 w = PyList_GET_ITEM(consts, GETARG(codestr, 3));
97 opcode = codestr[6];
98 switch (opcode) {
99 case BINARY_POWER:
100 newconst = PyNumber_Power(v, w, Py_None);
101 break;
102 case BINARY_MULTIPLY:
103 newconst = PyNumber_Multiply(v, w);
104 break;
105 case BINARY_DIVIDE:
106 /* Cannot fold this operation statically since
107 the result can depend on the run-time presence
108 of the -Qnew flag */
109 return 0;
110 case BINARY_TRUE_DIVIDE:
111 newconst = PyNumber_TrueDivide(v, w);
112 break;
113 case BINARY_FLOOR_DIVIDE:
114 newconst = PyNumber_FloorDivide(v, w);
115 break;
116 case BINARY_MODULO:
117 newconst = PyNumber_Remainder(v, w);
118 break;
119 case BINARY_ADD:
120 newconst = PyNumber_Add(v, w);
121 break;
122 case BINARY_SUBTRACT:
123 newconst = PyNumber_Subtract(v, w);
124 break;
125 case BINARY_SUBSCR:
126 newconst = PyObject_GetItem(v, w);
127 break;
128 case BINARY_LSHIFT:
129 newconst = PyNumber_Lshift(v, w);
130 break;
131 case BINARY_RSHIFT:
132 newconst = PyNumber_Rshift(v, w);
133 break;
134 case BINARY_AND:
135 newconst = PyNumber_And(v, w);
136 break;
137 case BINARY_XOR:
138 newconst = PyNumber_Xor(v, w);
139 break;
140 case BINARY_OR:
141 newconst = PyNumber_Or(v, w);
142 break;
143 default:
144 /* Called with an unknown opcode */
145 PyErr_Format(PyExc_SystemError,
146 "unexpected binary operation %d on a constant",
147 opcode);
148 return 0;
149 }
150 if (newconst == NULL) {
151 PyErr_Clear();
152 return 0;
153 }
154 size = PyObject_Size(newconst);
155 if (size == -1)
156 PyErr_Clear();
157 else if (size > 20) {
158 Py_DECREF(newconst);
159 return 0;
160 }
161
162 /* Append folded constant into consts table */
163 len_consts = PyList_GET_SIZE(consts);
164 if (PyList_Append(consts, newconst)) {
165 Py_DECREF(newconst);
166 return 0;
167 }
168 Py_DECREF(newconst);
169
170 /* Write NOP NOP NOP NOP LOAD_CONST newconst */
171 memset(codestr, NOP, 4);
172 codestr[4] = LOAD_CONST;
173 SETARG(codestr, 4, len_consts);
174 return 1;
175}
176
177static int
178fold_unaryops_on_constants(unsigned char *codestr, PyObject *consts)
179{
180 PyObject *newconst=NULL, *v;
181 Py_ssize_t len_consts;
182 int opcode;
183
184 /* Pre-conditions */
185 assert(PyList_CheckExact(consts));
186 assert(codestr[0] == LOAD_CONST);
187
188 /* Create new constant */
189 v = PyList_GET_ITEM(consts, GETARG(codestr, 0));
190 opcode = codestr[3];
191 switch (opcode) {
192 case UNARY_NEGATIVE:
193 /* Preserve the sign of -0.0 */
194 if (PyObject_IsTrue(v) == 1)
195 newconst = PyNumber_Negative(v);
196 break;
197 case UNARY_CONVERT:
198 newconst = PyObject_Repr(v);
199 break;
200 case UNARY_INVERT:
201 newconst = PyNumber_Invert(v);
202 break;
203 default:
204 /* Called with an unknown opcode */
205 PyErr_Format(PyExc_SystemError,
206 "unexpected unary operation %d on a constant",
207 opcode);
208 return 0;
209 }
210 if (newconst == NULL) {
211 PyErr_Clear();
212 return 0;
213 }
214
215 /* Append folded constant into consts table */
216 len_consts = PyList_GET_SIZE(consts);
217 if (PyList_Append(consts, newconst)) {
218 Py_DECREF(newconst);
219 return 0;
220 }
221 Py_DECREF(newconst);
222
223 /* Write NOP LOAD_CONST newconst */
224 codestr[0] = NOP;
225 codestr[1] = LOAD_CONST;
226 SETARG(codestr, 1, len_consts);
227 return 1;
228}
229
230static unsigned int *
231markblocks(unsigned char *code, Py_ssize_t len)
232{
233 unsigned int *blocks = (unsigned int *)PyMem_Malloc(len*sizeof(int));
234 int i,j, opcode, blockcnt = 0;
235
236 if (blocks == NULL) {
237 PyErr_NoMemory();
238 return NULL;
239 }
240 memset(blocks, 0, len*sizeof(int));
241
242 /* Mark labels in the first pass */
243 for (i=0 ; i<len ; i+=CODESIZE(opcode)) {
244 opcode = code[i];
245 switch (opcode) {
246 case FOR_ITER:
247 case JUMP_FORWARD:
248 case JUMP_IF_FALSE:
249 case JUMP_IF_TRUE:
250 case JUMP_ABSOLUTE:
251 case CONTINUE_LOOP:
252 case SETUP_LOOP:
253 case SETUP_EXCEPT:
254 case SETUP_FINALLY:
255 j = GETJUMPTGT(code, i);
256 blocks[j] = 1;
257 break;
258 }
259 }
260 /* Build block numbers in the second pass */
261 for (i=0 ; i<len ; i++) {
262 blockcnt += blocks[i]; /* increment blockcnt over labels */
263 blocks[i] = blockcnt;
264 }
265 return blocks;
266}
267
268/* Perform basic peephole optimizations to components of a code object.
269 The consts object should still be in list form to allow new constants
270 to be appended.
271
272 To keep the optimizer simple, it bails out (does nothing) for code
273 containing extended arguments or that has a length over 32,700. That
274 allows us to avoid overflow and sign issues. Likewise, it bails when
275 the lineno table has complex encoding for gaps >= 255.
276
277 Optimizations are restricted to simple transformations occuring within a
278 single basic block. All transformations keep the code size the same or
279 smaller. For those that reduce size, the gaps are initially filled with
280 NOPs. Later those NOPs are removed and the jump addresses retargeted in
281 a single pass. Line numbering is adjusted accordingly. */
282
283PyObject *
284PyCode_Optimize(PyObject *code, PyObject* consts, PyObject *names,
285 PyObject *lineno_obj)
286{
287 Py_ssize_t i, j, codelen;
288 int nops, h, adj;
289 int tgt, tgttgt, opcode;
290 unsigned char *codestr = NULL;
291 unsigned char *lineno;
292 int *addrmap = NULL;
293 int new_line, cum_orig_line, last_line, tabsiz;
294 int cumlc=0, lastlc=0; /* Count runs of consecutive LOAD_CONSTs */
295 unsigned int *blocks = NULL;
296 char *name;
297
298 /* Bail out if an exception is set */
299 if (PyErr_Occurred())
300 goto exitError;
301
302 /* Bypass optimization when the lineno table is too complex */
303 assert(PyString_Check(lineno_obj));
304 lineno = (unsigned char*)PyString_AS_STRING(lineno_obj);
305 tabsiz = PyString_GET_SIZE(lineno_obj);
306 if (memchr(lineno, 255, tabsiz) != NULL)
307 goto exitUnchanged;
308
309 /* Avoid situations where jump retargeting could overflow */
310 assert(PyString_Check(code));
311 codelen = PyString_GET_SIZE(code);
312 if (codelen > 32700)
313 goto exitUnchanged;
314
315 /* Make a modifiable copy of the code string */
316 codestr = (unsigned char *)PyMem_Malloc(codelen);
317 if (codestr == NULL)
318 goto exitError;
319 codestr = (unsigned char *)memcpy(codestr,
320 PyString_AS_STRING(code), codelen);
321
322 /* Verify that RETURN_VALUE terminates the codestring. This allows
323 the various transformation patterns to look ahead several
324 instructions without additional checks to make sure they are not
325 looking beyond the end of the code string.
326 */
327 if (codestr[codelen-1] != RETURN_VALUE)
328 goto exitUnchanged;
329
330 /* Mapping to new jump targets after NOPs are removed */
331 addrmap = (int *)PyMem_Malloc(codelen * sizeof(int));
332 if (addrmap == NULL)
333 goto exitError;
334
335 blocks = markblocks(codestr, codelen);
336 if (blocks == NULL)
337 goto exitError;
338 assert(PyList_Check(consts));
339
340 for (i=0 ; i<codelen ; i += CODESIZE(codestr[i])) {
341 opcode = codestr[i];
342
343 lastlc = cumlc;
344 cumlc = 0;
345
346 switch (opcode) {
347
348 /* Replace UNARY_NOT JUMP_IF_FALSE POP_TOP with
349 with JUMP_IF_TRUE POP_TOP */
350 case UNARY_NOT:
351 if (codestr[i+1] != JUMP_IF_FALSE ||
352 codestr[i+4] != POP_TOP ||
353 !ISBASICBLOCK(blocks,i,5))
354 continue;
355 tgt = GETJUMPTGT(codestr, (i+1));
356 if (codestr[tgt] != POP_TOP)
357 continue;
358 j = GETARG(codestr, i+1) + 1;
359 codestr[i] = JUMP_IF_TRUE;
360 SETARG(codestr, i, j);
361 codestr[i+3] = POP_TOP;
362 codestr[i+4] = NOP;
363 break;
364
365 /* not a is b --> a is not b
366 not a in b --> a not in b
367 not a is not b --> a is b
368 not a not in b --> a in b
369 */
370 case COMPARE_OP:
371 j = GETARG(codestr, i);
372 if (j < 6 || j > 9 ||
373 codestr[i+3] != UNARY_NOT ||
374 !ISBASICBLOCK(blocks,i,4))
375 continue;
376 SETARG(codestr, i, (j^1));
377 codestr[i+3] = NOP;
378 break;
379
380 /* Replace LOAD_GLOBAL/LOAD_NAME None
381 with LOAD_CONST None */
382 case LOAD_NAME:
383 case LOAD_GLOBAL:
384 j = GETARG(codestr, i);
385 name = PyString_AsString(PyTuple_GET_ITEM(names, j));
386 if (name == NULL || strcmp(name, "None") != 0)
387 continue;
388 for (j=0 ; j < PyList_GET_SIZE(consts) ; j++) {
389 if (PyList_GET_ITEM(consts, j) == Py_None)
390 break;
391 }
392 if (j == PyList_GET_SIZE(consts)) {
393 if (PyList_Append(consts, Py_None) == -1)
394 goto exitError;
395 }
396 assert(PyList_GET_ITEM(consts, j) == Py_None);
397 codestr[i] = LOAD_CONST;
398 SETARG(codestr, i, j);
399 cumlc = lastlc + 1;
400 break;
401
402 /* Skip over LOAD_CONST trueconst
403 JUMP_IF_FALSE xx POP_TOP */
404 case LOAD_CONST:
405 cumlc = lastlc + 1;
406 j = GETARG(codestr, i);
407 if (codestr[i+3] != JUMP_IF_FALSE ||
408 codestr[i+6] != POP_TOP ||
409 !ISBASICBLOCK(blocks,i,7) ||
410 !PyObject_IsTrue(PyList_GET_ITEM(consts, j)))
411 continue;
412 memset(codestr+i, NOP, 7);
413 cumlc = 0;
414 break;
415
416 /* Try to fold tuples of constants (includes a case for lists
417 which are only used for "in" and "not in" tests).
418 Skip over BUILD_SEQN 1 UNPACK_SEQN 1.
419 Replace BUILD_SEQN 2 UNPACK_SEQN 2 with ROT2.
420 Replace BUILD_SEQN 3 UNPACK_SEQN 3 with ROT3 ROT2. */
421 case BUILD_TUPLE:
422 case BUILD_LIST:
423 j = GETARG(codestr, i);
424 h = i - 3 * j;
425 if (h >= 0 &&
426 j <= lastlc &&
427 ((opcode == BUILD_TUPLE &&
428 ISBASICBLOCK(blocks, h, 3*(j+1))) ||
429 (opcode == BUILD_LIST &&
430 codestr[i+3]==COMPARE_OP &&
431 ISBASICBLOCK(blocks, h, 3*(j+2)) &&
432 (GETARG(codestr,i+3)==6 ||
433 GETARG(codestr,i+3)==7))) &&
434 tuple_of_constants(&codestr[h], j, consts)) {
435 assert(codestr[i] == LOAD_CONST);
436 cumlc = 1;
437 break;
438 }
439 if (codestr[i+3] != UNPACK_SEQUENCE ||
440 !ISBASICBLOCK(blocks,i,6) ||
441 j != GETARG(codestr, i+3))
442 continue;
443 if (j == 1) {
444 memset(codestr+i, NOP, 6);
445 } else if (j == 2) {
446 codestr[i] = ROT_TWO;
447 memset(codestr+i+1, NOP, 5);
448 } else if (j == 3) {
449 codestr[i] = ROT_THREE;
450 codestr[i+1] = ROT_TWO;
451 memset(codestr+i+2, NOP, 4);
452 }
453 break;
454
455 /* Fold binary ops on constants.
456 LOAD_CONST c1 LOAD_CONST c2 BINOP --> LOAD_CONST binop(c1,c2) */
457 case BINARY_POWER:
458 case BINARY_MULTIPLY:
459 case BINARY_TRUE_DIVIDE:
460 case BINARY_FLOOR_DIVIDE:
461 case BINARY_MODULO:
462 case BINARY_ADD:
463 case BINARY_SUBTRACT:
464 case BINARY_SUBSCR:
465 case BINARY_LSHIFT:
466 case BINARY_RSHIFT:
467 case BINARY_AND:
468 case BINARY_XOR:
469 case BINARY_OR:
470 if (lastlc >= 2 &&
471 ISBASICBLOCK(blocks, i-6, 7) &&
472 fold_binops_on_constants(&codestr[i-6], consts)) {
473 i -= 2;
474 assert(codestr[i] == LOAD_CONST);
475 cumlc = 1;
476 }
477 break;
478
479 /* Fold unary ops on constants.
480 LOAD_CONST c1 UNARY_OP --> LOAD_CONST unary_op(c) */
481 case UNARY_NEGATIVE:
482 case UNARY_CONVERT:
483 case UNARY_INVERT:
484 if (lastlc >= 1 &&
485 ISBASICBLOCK(blocks, i-3, 4) &&
486 fold_unaryops_on_constants(&codestr[i-3], consts)) {
487 i -= 2;
488 assert(codestr[i] == LOAD_CONST);
489 cumlc = 1;
490 }
491 break;
492
493 /* Simplify conditional jump to conditional jump where the
494 result of the first test implies the success of a similar
495 test or the failure of the opposite test.
496 Arises in code like:
497 "if a and b:"
498 "if a or b:"
499 "a and b or c"
500 "(a and b) and c"
501 x:JUMP_IF_FALSE y y:JUMP_IF_FALSE z --> x:JUMP_IF_FALSE z
502 x:JUMP_IF_FALSE y y:JUMP_IF_TRUE z --> x:JUMP_IF_FALSE y+3
503 where y+3 is the instruction following the second test.
504 */
505 case JUMP_IF_FALSE:
506 case JUMP_IF_TRUE:
507 tgt = GETJUMPTGT(codestr, i);
508 j = codestr[tgt];
509 if (j == JUMP_IF_FALSE || j == JUMP_IF_TRUE) {
510 if (j == opcode) {
511 tgttgt = GETJUMPTGT(codestr, tgt) - i - 3;
512 SETARG(codestr, i, tgttgt);
513 } else {
514 tgt -= i;
515 SETARG(codestr, i, tgt);
516 }
517 break;
518 }
519 /* Intentional fallthrough */
520
521 /* Replace jumps to unconditional jumps */
522 case FOR_ITER:
523 case JUMP_FORWARD:
524 case JUMP_ABSOLUTE:
525 case CONTINUE_LOOP:
526 case SETUP_LOOP:
527 case SETUP_EXCEPT:
528 case SETUP_FINALLY:
529 tgt = GETJUMPTGT(codestr, i);
530 /* Replace JUMP_* to a RETURN into just a RETURN */
531 if (UNCONDITIONAL_JUMP(opcode) &&
532 codestr[tgt] == RETURN_VALUE) {
533 codestr[i] = RETURN_VALUE;
534 memset(codestr+i+1, NOP, 2);
535 continue;
536 }
537 if (!UNCONDITIONAL_JUMP(codestr[tgt]))
538 continue;
539 tgttgt = GETJUMPTGT(codestr, tgt);
540 if (opcode == JUMP_FORWARD) /* JMP_ABS can go backwards */
541 opcode = JUMP_ABSOLUTE;
542 if (!ABSOLUTE_JUMP(opcode))
543 tgttgt -= i + 3; /* Calc relative jump addr */
544 if (tgttgt < 0) /* No backward relative jumps */
545 continue;
546 codestr[i] = opcode;
547 SETARG(codestr, i, tgttgt);
548 break;
549
550 case EXTENDED_ARG:
551 goto exitUnchanged;
552
553 /* Replace RETURN LOAD_CONST None RETURN with just RETURN */
554 /* Remove unreachable JUMPs after RETURN */
555 case RETURN_VALUE:
556 if (i+4 >= codelen)
557 continue;
558 if (codestr[i+4] == RETURN_VALUE &&
559 ISBASICBLOCK(blocks,i,5))
560 memset(codestr+i+1, NOP, 4);
561 else if (UNCONDITIONAL_JUMP(codestr[i+1]) &&
562 ISBASICBLOCK(blocks,i,4))
563 memset(codestr+i+1, NOP, 3);
564 break;
565 }
566 }
567
568 /* Fixup linenotab */
569 for (i=0, nops=0 ; i<codelen ; i += CODESIZE(codestr[i])) {
570 addrmap[i] = i - nops;
571 if (codestr[i] == NOP)
572 nops++;
573 }
574 cum_orig_line = 0;
575 last_line = 0;
576 for (i=0 ; i < tabsiz ; i+=2) {
577 cum_orig_line += lineno[i];
578 new_line = addrmap[cum_orig_line];
579 assert (new_line - last_line < 255);
580 lineno[i] =((unsigned char)(new_line - last_line));
581 last_line = new_line;
582 }
583
584 /* Remove NOPs and fixup jump targets */
585 for (i=0, h=0 ; i<codelen ; ) {
586 opcode = codestr[i];
587 switch (opcode) {
588 case NOP:
589 i++;
590 continue;
591
592 case JUMP_ABSOLUTE:
593 case CONTINUE_LOOP:
594 j = addrmap[GETARG(codestr, i)];
595 SETARG(codestr, i, j);
596 break;
597
598 case FOR_ITER:
599 case JUMP_FORWARD:
600 case JUMP_IF_FALSE:
601 case JUMP_IF_TRUE:
602 case SETUP_LOOP:
603 case SETUP_EXCEPT:
604 case SETUP_FINALLY:
605 j = addrmap[GETARG(codestr, i) + i + 3] - addrmap[i] - 3;
606 SETARG(codestr, i, j);
607 break;
608 }
609 adj = CODESIZE(opcode);
610 while (adj--)
611 codestr[h++] = codestr[i++];
612 }
613 assert(h + nops == codelen);
614
615 code = PyString_FromStringAndSize((char *)codestr, h);
616 PyMem_Free(addrmap);
617 PyMem_Free(codestr);
618 PyMem_Free(blocks);
619 return code;
620
621 exitError:
622 code = NULL;
623
624 exitUnchanged:
625 if (blocks != NULL)
626 PyMem_Free(blocks);
627 if (addrmap != NULL)
628 PyMem_Free(addrmap);
629 if (codestr != NULL)
630 PyMem_Free(codestr);
631 Py_XINCREF(code);
632 return code;
633}
Note: See TracBrowser for help on using the repository browser.