← Back to branch summary

~ubuntu-branches/ubuntu/trusty/python3.4/trusty-proposed

« back to all changes in this revision

Viewing changes to Python/peephole.c

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2013-11-25 09:44:27 UTC
  • Revision ID: package-import@ubuntu.com-20131125094427-lzxj8ap5w01lmo7f
Tags: upstream-3.4~b1
Import upstream version 3.4~b1

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