← Back to branch summary

~ubuntu-branches/ubuntu/maverick/python3.1/maverick

« back to all changes in this revision

Viewing changes to Python/peephole.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2009-03-23 00:01:27 UTC
  • Revision ID: james.westby@ubuntu.com-20090323000127-5fstfxju4ufrhthq
Tags: upstream-3.1~a1+20090322
Import upstream version 3.1~a1+20090322

Show diffs side-by-side

added added

removed removed

Lines of Context:
Python/peephole.c
 
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 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])
 
27
 
 
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.
 
35
*/
 
36
static int
 
37
tuple_of_constants(unsigned char *codestr, Py_ssize_t n, PyObject *consts)
 
38
{
 
39
        PyObject *newconst, *constant;
 
40
        Py_ssize_t i, arg, len_consts;
 
41
 
 
42
        /* Pre-conditions */
 
43
        assert(PyList_CheckExact(consts));
 
44
        assert(codestr[n*3] == BUILD_TUPLE || codestr[n*3] == BUILD_LIST);
 
45
        assert(GETARG(codestr, (n*3)) == n);
 
46
        for (i=0 ; i<n ; i++)
 
47
                assert(codestr[i*3] == LOAD_CONST);
 
48
 
 
49
        /* Buildup new tuple of constants */
 
50
        newconst = PyTuple_New(n);
 
51
        if (newconst == NULL)
 
52
                return 0;
 
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);
 
58
                Py_INCREF(constant);
 
59
                PyTuple_SET_ITEM(newconst, i, constant);
 
60
        }
 
61
 
 
62
        /* Append folded constant onto consts */
 
63
        if (PyList_Append(consts, newconst)) {
 
64
                Py_DECREF(newconst);
 
65
                return 0;
 
66
        }
 
67
        Py_DECREF(newconst);
 
68
 
 
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);
 
74
        return 1;
 
75
}
 
76
 
 
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.
 
86
*/
 
87
static int
 
88
fold_binops_on_constants(unsigned char *codestr, PyObject *consts)
 
89
{
 
90
        PyObject *newconst, *v, *w;
 
91
        Py_ssize_t len_consts, size;
 
92
        int opcode;
 
93
 
 
94
        /* Pre-conditions */
 
95
        assert(PyList_CheckExact(consts));
 
96
        assert(codestr[0] == LOAD_CONST);
 
97
        assert(codestr[3] == LOAD_CONST);
 
98
 
 
99
        /* Create new constant */
 
100
        v = PyList_GET_ITEM(consts, GETARG(codestr, 0));
 
101
        w = PyList_GET_ITEM(consts, GETARG(codestr, 3));
 
102
        opcode = codestr[6];
 
103
        switch (opcode) {
 
104
                case BINARY_POWER:
 
105
                        newconst = PyNumber_Power(v, w, Py_None);
 
106
                        break;
 
107
                case BINARY_MULTIPLY:
 
108
                        newconst = PyNumber_Multiply(v, w);
 
109
                        break;
 
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
 
 
177
static int
 
178
fold_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_INVERT:
 
198
                        newconst = PyNumber_Invert(v);
 
199
                        break;
 
200
                default:
 
201
                        /* Called with an unknown opcode */
 
202
                        PyErr_Format(PyExc_SystemError,
 
203
                             "unexpected unary operation %d on a constant",
 
204
                                     opcode);
 
205
                        return 0;
 
206
        }
 
207
        if (newconst == NULL) {
 
208
                PyErr_Clear();
 
209
                return 0;
 
210
        }
 
211
 
 
212
        /* Append folded constant into consts table */
 
213
        len_consts = PyList_GET_SIZE(consts);
 
214
        if (PyList_Append(consts, newconst)) {
 
215
                Py_DECREF(newconst);
 
216
                return 0;
 
217
        }
 
218
        Py_DECREF(newconst);
 
219
 
 
220
        /* Write NOP LOAD_CONST newconst */
 
221
        codestr[0] = NOP;
 
222
        codestr[1] = LOAD_CONST;
 
223
        SETARG(codestr, 1, len_consts);
 
224
        return 1;
 
225
}
 
226
 
 
227
static unsigned int *
 
228
markblocks(unsigned char *code, Py_ssize_t len)
 
229
{
 
230
        unsigned int *blocks = (unsigned int *)PyMem_Malloc(len*sizeof(int));
 
231
        int i,j, opcode, blockcnt = 0;
 
232
 
 
233
        if (blocks == NULL) {
 
234
                PyErr_NoMemory();
 
235
                return NULL;
 
236
        }
 
237
        memset(blocks, 0, len*sizeof(int));
 
238
 
 
239
        /* Mark labels in the first pass */
 
240
        for (i=0 ; i<len ; i+=CODESIZE(opcode)) {
 
241
                opcode = code[i];
 
242
                switch (opcode) {
 
243
                        case FOR_ITER:
 
244
                        case JUMP_FORWARD:
 
245
                        case JUMP_IF_FALSE_OR_POP:
 
246
                        case JUMP_IF_TRUE_OR_POP:
 
247
                        case POP_JUMP_IF_FALSE:
 
248
                        case POP_JUMP_IF_TRUE:
 
249
                        case JUMP_ABSOLUTE:
 
250
                        case CONTINUE_LOOP:
 
251
                        case SETUP_LOOP:
 
252
                        case SETUP_EXCEPT:
 
253
                        case SETUP_FINALLY:
 
254
                                j = GETJUMPTGT(code, i);
 
255
                                blocks[j] = 1;
 
256
                                break;
 
257
                }
 
258
        }
 
259
        /* Build block numbers in the second pass */
 
260
        for (i=0 ; i<len ; i++) {
 
261
                blockcnt += blocks[i];  /* increment blockcnt over labels */
 
262
                blocks[i] = blockcnt;
 
263
        }
 
264
        return blocks;
 
265
}
 
266
 
 
267
/* Helper to replace LOAD_NAME None/True/False with LOAD_CONST
 
268
   Returns: 0 if no change, 1 if change, -1 if error */
 
269
static int
 
270
load_global(unsigned char *codestr, Py_ssize_t i, char *name, PyObject *consts)
 
271
{
 
272
        Py_ssize_t j;
 
273
        PyObject *obj;
 
274
        if (name == NULL)
 
275
                return 0;
 
276
        if (strcmp(name, "None") == 0)
 
277
                obj = Py_None;
 
278
        else if (strcmp(name, "True") == 0)
 
279
                obj = Py_True;
 
280
        else if (strcmp(name, "False") == 0)
 
281
                obj = Py_False;
 
282
        else
 
283
                return 0;
 
284
        for (j = 0; j < PyList_GET_SIZE(consts); j++) {
 
285
                if (PyList_GET_ITEM(consts, j) == obj)
 
286
                        break;
 
287
        }
 
288
        if (j == PyList_GET_SIZE(consts)) {
 
289
                if (PyList_Append(consts, obj) < 0)
 
290
                        return -1;
 
291
        }
 
292
        assert(PyList_GET_ITEM(consts, j) == obj);
 
293
        codestr[i] = LOAD_CONST;
 
294
        SETARG(codestr, i, j);
 
295
        return 1;
 
296
}
 
297
 
 
298
/* Perform basic peephole optimizations to components of a code object.
 
299
   The consts object should still be in list form to allow new constants 
 
300
   to be appended.
 
301
 
 
302
   To keep the optimizer simple, it bails out (does nothing) for code that
 
303
   has a length over 32,700, and does not calculate extended arguments. 
 
304
   That allows us to avoid overflow and sign issues. Likewise, it bails when
 
305
   the lineno table has complex encoding for gaps >= 255. EXTENDED_ARG can
 
306
   appear before MAKE_FUNCTION; in this case both opcodes are skipped.
 
307
   EXTENDED_ARG preceding any other opcode causes the optimizer to bail.
 
308
 
 
309
   Optimizations are restricted to simple transformations occuring within a
 
310
   single basic block.  All transformations keep the code size the same or 
 
311
   smaller.  For those that reduce size, the gaps are initially filled with 
 
312
   NOPs.  Later those NOPs are removed and the jump addresses retargeted in 
 
313
   a single pass.  Line numbering is adjusted accordingly. */
 
314
 
 
315
PyObject *
 
316
PyCode_Optimize(PyObject *code, PyObject* consts, PyObject *names,
 
317
                PyObject *lineno_obj)
 
318
{
 
319
        Py_ssize_t i, j, codelen;
 
320
        int nops, h, adj;
 
321
        int tgt, tgttgt, opcode;
 
322
        unsigned char *codestr = NULL;
 
323
        unsigned char *lineno;
 
324
        int *addrmap = NULL;
 
325
        int new_line, cum_orig_line, last_line, tabsiz;
 
326
        int cumlc=0, lastlc=0;  /* Count runs of consecutive LOAD_CONSTs */
 
327
        unsigned int *blocks = NULL;
 
328
        char *name;
 
329
 
 
330
        /* Bail out if an exception is set */
 
331
        if (PyErr_Occurred())
 
332
                goto exitUnchanged;
 
333
 
 
334
        /* Bypass optimization when the lineno table is too complex */
 
335
        assert(PyBytes_Check(lineno_obj));
 
336
        lineno = (unsigned char*)PyBytes_AS_STRING(lineno_obj);
 
337
        tabsiz = PyBytes_GET_SIZE(lineno_obj);
 
338
        if (memchr(lineno, 255, tabsiz) != NULL)
 
339
                goto exitUnchanged;
 
340
 
 
341
        /* Avoid situations where jump retargeting could overflow */
 
342
        assert(PyBytes_Check(code));
 
343
        codelen = PyBytes_GET_SIZE(code);
 
344
        if (codelen > 32700)
 
345
                goto exitUnchanged;
 
346
 
 
347
        /* Make a modifiable copy of the code string */
 
348
        codestr = (unsigned char *)PyMem_Malloc(codelen);
 
349
        if (codestr == NULL)
 
350
                goto exitUnchanged;
 
351
        codestr = (unsigned char *)memcpy(codestr, 
 
352
                                          PyBytes_AS_STRING(code), codelen);
 
353
 
 
354
        /* Verify that RETURN_VALUE terminates the codestring.  This allows
 
355
           the various transformation patterns to look ahead several
 
356
           instructions without additional checks to make sure they are not
 
357
           looking beyond the end of the code string.
 
358
        */
 
359
        if (codestr[codelen-1] != RETURN_VALUE)
 
360
                goto exitUnchanged;
 
361
 
 
362
        /* Mapping to new jump targets after NOPs are removed */
 
363
        addrmap = (int *)PyMem_Malloc(codelen * sizeof(int));
 
364
        if (addrmap == NULL)
 
365
                goto exitUnchanged;
 
366
 
 
367
        blocks = markblocks(codestr, codelen);
 
368
        if (blocks == NULL)
 
369
                goto exitUnchanged;
 
370
        assert(PyList_Check(consts));
 
371
 
 
372
        for (i=0 ; i<codelen ; i += CODESIZE(codestr[i])) {
 
373
          reoptimize_current:
 
374
                opcode = codestr[i];
 
375
 
 
376
                lastlc = cumlc;
 
377
                cumlc = 0;
 
378
 
 
379
                switch (opcode) {
 
380
                        /* Replace UNARY_NOT POP_JUMP_IF_FALSE 
 
381
                           with    POP_JUMP_IF_TRUE */
 
382
                        case UNARY_NOT:
 
383
                                if (codestr[i+1] != POP_JUMP_IF_FALSE
 
384
                                    || !ISBASICBLOCK(blocks,i,4))
 
385
                                        continue;
 
386
                                j = GETARG(codestr, i+1);
 
387
                                codestr[i] = POP_JUMP_IF_TRUE;
 
388
                                SETARG(codestr, i, j);
 
389
                                codestr[i+3] = NOP;
 
390
                                goto reoptimize_current;
 
391
 
 
392
                                /* not a is b -->  a is not b
 
393
                                   not a in b -->  a not in b
 
394
                                   not a is not b -->  a is b
 
395
                                   not a not in b -->  a in b
 
396
                                */
 
397
                        case COMPARE_OP:
 
398
                                j = GETARG(codestr, i);
 
399
                                if (j < 6  ||  j > 9  ||
 
400
                                    codestr[i+3] != UNARY_NOT  || 
 
401
                                    !ISBASICBLOCK(blocks,i,4))
 
402
                                        continue;
 
403
                                SETARG(codestr, i, (j^1));
 
404
                                codestr[i+3] = NOP;
 
405
                                break;
 
406
 
 
407
                                /* Replace LOAD_GLOBAL/LOAD_NAME None/True/False
 
408
                                   with LOAD_CONST None/True/False */
 
409
                        case LOAD_NAME:
 
410
                        case LOAD_GLOBAL:
 
411
                                j = GETARG(codestr, i);
 
412
                                name = _PyUnicode_AsString(PyTuple_GET_ITEM(names, j));
 
413
                                h = load_global(codestr, i, name, consts);
 
414
                                if (h < 0)
 
415
                                        goto exitUnchanged;
 
416
                                else if (h == 0)
 
417
                                        continue;
 
418
                                cumlc = lastlc + 1;
 
419
                                break;
 
420
 
 
421
                                /* Skip over LOAD_CONST trueconst
 
422
                                   POP_JUMP_IF_FALSE xx. This improves
 
423
                                   "while 1" performance. */
 
424
                        case LOAD_CONST:
 
425
                                cumlc = lastlc + 1;
 
426
                                j = GETARG(codestr, i);
 
427
                                if (codestr[i+3] != POP_JUMP_IF_FALSE  ||
 
428
                                    !ISBASICBLOCK(blocks,i,6)  ||
 
429
                                    !PyObject_IsTrue(PyList_GET_ITEM(consts, j)))
 
430
                                        continue;
 
431
                                memset(codestr+i, NOP, 6);
 
432
                                cumlc = 0;
 
433
                                break;
 
434
 
 
435
                                /* Try to fold tuples of constants (includes a case for lists
 
436
                                   which are only used for "in" and "not in" tests).
 
437
                                   Skip over BUILD_SEQN 1 UNPACK_SEQN 1.
 
438
                                   Replace BUILD_SEQN 2 UNPACK_SEQN 2 with ROT2.
 
439
                                   Replace BUILD_SEQN 3 UNPACK_SEQN 3 with ROT3 ROT2. */
 
440
                        case BUILD_TUPLE:
 
441
                        case BUILD_LIST:
 
442
                                j = GETARG(codestr, i);
 
443
                                h = i - 3 * j;
 
444
                                if (h >= 0  &&
 
445
                                    j <= lastlc  &&
 
446
                                    ((opcode == BUILD_TUPLE && 
 
447
                                      ISBASICBLOCK(blocks, h, 3*(j+1))) ||
 
448
                                     (opcode == BUILD_LIST && 
 
449
                                      codestr[i+3]==COMPARE_OP && 
 
450
                                      ISBASICBLOCK(blocks, h, 3*(j+2)) &&
 
451
                                      (GETARG(codestr,i+3)==6 ||
 
452
                                       GETARG(codestr,i+3)==7))) &&
 
453
                                    tuple_of_constants(&codestr[h], j, consts)) {
 
454
                                        assert(codestr[i] == LOAD_CONST);
 
455
                                        cumlc = 1;
 
456
                                        break;
 
457
                                }
 
458
                                if (codestr[i+3] != UNPACK_SEQUENCE  ||
 
459
                                    !ISBASICBLOCK(blocks,i,6) ||
 
460
                                    j != GETARG(codestr, i+3))
 
461
                                        continue;
 
462
                                if (j == 1) {
 
463
                                        memset(codestr+i, NOP, 6);
 
464
                                } else if (j == 2) {
 
465
                                        codestr[i] = ROT_TWO;
 
466
                                        memset(codestr+i+1, NOP, 5);
 
467
                                } else if (j == 3) {
 
468
                                        codestr[i] = ROT_THREE;
 
469
                                        codestr[i+1] = ROT_TWO;
 
470
                                        memset(codestr+i+2, NOP, 4);
 
471
                                }
 
472
                                break;
 
473
 
 
474
                                /* Fold binary ops on constants.
 
475
                                   LOAD_CONST c1 LOAD_CONST c2 BINOP -->  LOAD_CONST binop(c1,c2) */
 
476
                        case BINARY_POWER:
 
477
                        case BINARY_MULTIPLY:
 
478
                        case BINARY_TRUE_DIVIDE:
 
479
                        case BINARY_FLOOR_DIVIDE:
 
480
                        case BINARY_MODULO:
 
481
                        case BINARY_ADD:
 
482
                        case BINARY_SUBTRACT:
 
483
                        case BINARY_SUBSCR:
 
484
                        case BINARY_LSHIFT:
 
485
                        case BINARY_RSHIFT:
 
486
                        case BINARY_AND:
 
487
                        case BINARY_XOR:
 
488
                        case BINARY_OR:
 
489
                                if (lastlc >= 2  &&
 
490
                                    ISBASICBLOCK(blocks, i-6, 7)  &&
 
491
                                    fold_binops_on_constants(&codestr[i-6], consts)) {
 
492
                                        i -= 2;
 
493
                                        assert(codestr[i] == LOAD_CONST);
 
494
                                        cumlc = 1;
 
495
                                }
 
496
                                break;
 
497
 
 
498
                                /* Fold unary ops on constants.
 
499
                                   LOAD_CONST c1  UNARY_OP -->  LOAD_CONST unary_op(c) */
 
500
                        case UNARY_NEGATIVE:
 
501
                        case UNARY_INVERT:
 
502
                                if (lastlc >= 1  &&
 
503
                                    ISBASICBLOCK(blocks, i-3, 4)  &&
 
504
                                    fold_unaryops_on_constants(&codestr[i-3], consts))  {
 
505
                                        i -= 2;
 
506
                                        assert(codestr[i] == LOAD_CONST);
 
507
                                        cumlc = 1;
 
508
                                }
 
509
                                break;
 
510
 
 
511
                                /* Simplify conditional jump to conditional jump where the
 
512
                                   result of the first test implies the success of a similar
 
513
                                   test or the failure of the opposite test.
 
514
                                   Arises in code like:
 
515
                                   "if a and b:"
 
516
                                   "if a or b:"
 
517
                                   "a and b or c"
 
518
                                   "(a and b) and c"
 
519
                                   x:JUMP_IF_FALSE_OR_POP y   y:JUMP_IF_FALSE_OR_POP z
 
520
                                      -->  x:JUMP_IF_FALSE_OR_POP z
 
521
                                   x:JUMP_IF_FALSE_OR_POP y   y:JUMP_IF_TRUE_OR_POP z
 
522
                                      -->  x:POP_JUMP_IF_FALSE y+3
 
523
                                   where y+3 is the instruction following the second test.
 
524
                                */
 
525
                        case JUMP_IF_FALSE_OR_POP:
 
526
                        case JUMP_IF_TRUE_OR_POP:
 
527
                                tgt = GETJUMPTGT(codestr, i);
 
528
                                j = codestr[tgt];
 
529
                                if (CONDITIONAL_JUMP(j)) {
 
530
                                        /* NOTE: all possible jumps here are
 
531
                                           absolute! */
 
532
                                        if (JUMPS_ON_TRUE(j) == JUMPS_ON_TRUE(opcode)) {
 
533
                                                /* The second jump will be
 
534
                                                   taken iff the first is. */
 
535
                                                tgttgt = GETJUMPTGT(codestr, tgt);
 
536
                                                /* The current opcode inherits
 
537
                                                   its target's stack behaviour */
 
538
                                                codestr[i] = j;
 
539
                                                SETARG(codestr, i, tgttgt);
 
540
                                                goto reoptimize_current;
 
541
                                        } else {
 
542
                                                /* The second jump is not taken
 
543
                                                   if the first is (so jump past
 
544
                                                   it), and all conditional
 
545
                                                   jumps pop their argument when
 
546
                                                   they're not taken (so change
 
547
                                                   the first jump to pop its
 
548
                                                   argument when it's taken). */
 
549
                                                if (JUMPS_ON_TRUE(opcode))
 
550
                                                        codestr[i] = POP_JUMP_IF_TRUE;
 
551
                                                else
 
552
                                                        codestr[i] = POP_JUMP_IF_FALSE;
 
553
                                                SETARG(codestr, i, (tgt + 3));
 
554
                                                goto reoptimize_current;
 
555
                                        }
 
556
                                }
 
557
                                /* Intentional fallthrough */
 
558
 
 
559
                                /* Replace jumps to unconditional jumps */
 
560
                        case POP_JUMP_IF_FALSE:
 
561
                        case POP_JUMP_IF_TRUE:
 
562
                        case FOR_ITER:
 
563
                        case JUMP_FORWARD:
 
564
                        case JUMP_ABSOLUTE:
 
565
                        case CONTINUE_LOOP:
 
566
                        case SETUP_LOOP:
 
567
                        case SETUP_EXCEPT:
 
568
                        case SETUP_FINALLY:
 
569
                                tgt = GETJUMPTGT(codestr, i);
 
570
                                /* Replace JUMP_* to a RETURN into just a RETURN */
 
571
                                if (UNCONDITIONAL_JUMP(opcode) &&
 
572
                                    codestr[tgt] == RETURN_VALUE) {
 
573
                                        codestr[i] = RETURN_VALUE;
 
574
                                        memset(codestr+i+1, NOP, 2);
 
575
                                        continue;
 
576
                                }
 
577
                                if (!UNCONDITIONAL_JUMP(codestr[tgt]))
 
578
                                        continue;
 
579
                                tgttgt = GETJUMPTGT(codestr, tgt);
 
580
                                if (opcode == JUMP_FORWARD) /* JMP_ABS can go backwards */
 
581
                                        opcode = JUMP_ABSOLUTE;
 
582
                                if (!ABSOLUTE_JUMP(opcode))
 
583
                                        tgttgt -= i + 3;     /* Calc relative jump addr */
 
584
                                if (tgttgt < 0)           /* No backward relative jumps */
 
585
                                        continue;
 
586
                                codestr[i] = opcode;
 
587
                                SETARG(codestr, i, tgttgt);
 
588
                                break;
 
589
 
 
590
                        case EXTENDED_ARG:
 
591
                                if (codestr[i+3] != MAKE_FUNCTION)
 
592
                                        goto exitUnchanged;
 
593
                                /* don't visit MAKE_FUNCTION as GETARG will be wrong */
 
594
                                i += 3;
 
595
                                break;
 
596
 
 
597
                                /* Replace RETURN LOAD_CONST None RETURN with just RETURN */
 
598
                                /* Remove unreachable JUMPs after RETURN */
 
599
                        case RETURN_VALUE:
 
600
                                if (i+4 >= codelen)
 
601
                                        continue;
 
602
                                if (codestr[i+4] == RETURN_VALUE &&
 
603
                                    ISBASICBLOCK(blocks,i,5))
 
604
                                        memset(codestr+i+1, NOP, 4);
 
605
                                else if (UNCONDITIONAL_JUMP(codestr[i+1]) &&
 
606
                                         ISBASICBLOCK(blocks,i,4))
 
607
                                        memset(codestr+i+1, NOP, 3);
 
608
                                break;
 
609
                }
 
610
        }
 
611
 
 
612
        /* Fixup linenotab */
 
613
        for (i=0, nops=0 ; i<codelen ; i += CODESIZE(codestr[i])) {
 
614
                addrmap[i] = i - nops;
 
615
                if (codestr[i] == NOP)
 
616
                        nops++;
 
617
        }
 
618
        cum_orig_line = 0;
 
619
        last_line = 0;
 
620
        for (i=0 ; i < tabsiz ; i+=2) {
 
621
                cum_orig_line += lineno[i];
 
622
                new_line = addrmap[cum_orig_line];
 
623
                assert (new_line - last_line < 255);
 
624
                lineno[i] =((unsigned char)(new_line - last_line));
 
625
                last_line = new_line;
 
626
        }
 
627
 
 
628
        /* Remove NOPs and fixup jump targets */
 
629
        for (i=0, h=0 ; i<codelen ; ) {
 
630
                opcode = codestr[i];
 
631
                switch (opcode) {
 
632
                        case NOP:
 
633
                                i++;
 
634
                                continue;
 
635
 
 
636
                        case JUMP_ABSOLUTE:
 
637
                        case CONTINUE_LOOP:
 
638
                        case POP_JUMP_IF_FALSE:
 
639
                        case POP_JUMP_IF_TRUE:
 
640
                        case JUMP_IF_FALSE_OR_POP:
 
641
                        case JUMP_IF_TRUE_OR_POP:
 
642
                                j = addrmap[GETARG(codestr, i)];
 
643
                                SETARG(codestr, i, j);
 
644
                                break;
 
645
 
 
646
                        case FOR_ITER:
 
647
                        case JUMP_FORWARD:
 
648
                        case SETUP_LOOP:
 
649
                        case SETUP_EXCEPT:
 
650
                        case SETUP_FINALLY:
 
651
                                j = addrmap[GETARG(codestr, i) + i + 3] - addrmap[i] - 3;
 
652
                                SETARG(codestr, i, j);
 
653
                                break;
 
654
                }
 
655
                adj = CODESIZE(opcode);
 
656
                while (adj--)
 
657
                        codestr[h++] = codestr[i++];
 
658
        }
 
659
        assert(h + nops == codelen);
 
660
 
 
661
        code = PyBytes_FromStringAndSize((char *)codestr, h);
 
662
        PyMem_Free(addrmap);
 
663
        PyMem_Free(codestr);
 
664
        PyMem_Free(blocks);
 
665
        return code;
 
666
 
 
667
 exitUnchanged:
 
668
        if (blocks != NULL)
 
669
                PyMem_Free(blocks);
 
670
        if (addrmap != NULL)
 
671
                PyMem_Free(addrmap);
 
672
        if (codestr != NULL)
 
673
                PyMem_Free(codestr);
 
674
        Py_INCREF(code);
 
675
        return code;
 
676
}