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_DIVIDE:
 111             /* Cannot fold this operation statically since
 112                the result can depend on the run-time presence
 113                of the -Qnew flag */
 114             return 0;
 115         case BINARY_TRUE_DIVIDE:
 116             newconst = PyNumber_TrueDivide(v, w);
 117             break;
 118         case BINARY_FLOOR_DIVIDE:
 119             newconst = PyNumber_FloorDivide(v, w);
 120             break;
 121         case BINARY_MODULO:
 122             newconst = PyNumber_Remainder(v, w);
 123             break;
 124         case BINARY_ADD:
 125             newconst = PyNumber_Add(v, w);
 126             break;
 127         case BINARY_SUBTRACT:
 128             newconst = PyNumber_Subtract(v, w);
 129             break;
 130         case BINARY_SUBSCR:
 131             newconst = PyObject_GetItem(v, w);
 132             break;
 133         case BINARY_LSHIFT:
 134             newconst = PyNumber_Lshift(v, w);
 135             break;
 136         case BINARY_RSHIFT:
 137             newconst = PyNumber_Rshift(v, w);
 138             break;
 139         case BINARY_AND:
 140             newconst = PyNumber_And(v, w);
 141             break;
 142         case BINARY_XOR:
 143             newconst = PyNumber_Xor(v, w);
 144             break;
 145         case BINARY_OR:
 146             newconst = PyNumber_Or(v, w);
 147             break;
 148         default:
 149             /* Called with an unknown opcode */
 150             PyErr_Format(PyExc_SystemError,
 151                  "unexpected binary operation %d on a constant",
 152                      opcode);
 153             return 0;
 154     }
 155     if (newconst == NULL) {
 156         PyErr_Clear();
 157         return 0;
 158     }
 159     size = PyObject_Size(newconst);
 160     if (size == -1)
 161         PyErr_Clear();
 162     else if (size > 20) {
 163         Py_DECREF(newconst);
 164         return 0;
 165     }
 166
 167     /* Append folded constant into consts table */
 168     len_consts = PyList_GET_SIZE(consts);
 169     if (PyList_Append(consts, newconst)) {
 170         Py_DECREF(newconst);
 171         return 0;
 172     }
 173     Py_DECREF(newconst);
 174
 175     /* Write NOP NOP NOP NOP LOAD_CONST newconst */
 176     memset(codestr, NOP, 4);
 177     codestr[4] = LOAD_CONST;
 178     SETARG(codestr, 4, len_consts);
 179     return 1;
 180 }
 181
 182 static int
 183 fold_unaryops_on_constants(unsigned char *codestr, PyObject *consts)
 184 {
 185     PyObject *newconst=NULL, *v;
 186     Py_ssize_t len_consts;
 187     int opcode;
 188
 189     /* Pre-conditions */
 190     assert(PyList_CheckExact(consts));
 191     assert(codestr[0] == LOAD_CONST);
 192
 193     /* Create new constant */
 194     v = PyList_GET_ITEM(consts, GETARG(codestr, 0));
 195     opcode = codestr[3];
 196     switch (opcode) {
 197         case UNARY_NEGATIVE:
 198             /* Preserve the sign of -0.0 */
 199             if (PyObject_IsTrue(v) == 1)
 200                 newconst = PyNumber_Negative(v);
 201             break;
 202         case UNARY_CONVERT:
 203             newconst = PyObject_Repr(v);
 204             break;
 205         case UNARY_INVERT:
 206             newconst = PyNumber_Invert(v);
 207             break;
 208         default:
 209             /* Called with an unknown opcode */
 210             PyErr_Format(PyExc_SystemError,
 211                  "unexpected unary operation %d on a constant",
 212                      opcode);
 213             return 0;
 214     }
 215     if (newconst == NULL) {
 216         PyErr_Clear();
 217         return 0;
 218     }
 219
 220     /* Append folded constant into consts table */
 221     len_consts = PyList_GET_SIZE(consts);
 222     if (PyList_Append(consts, newconst)) {
 223         Py_DECREF(newconst);
 224         return 0;
 225     }
 226     Py_DECREF(newconst);
 227
 228     /* Write NOP LOAD_CONST newconst */
 229     codestr[0] = NOP;
 230     codestr[1] = LOAD_CONST;
 231     SETARG(codestr, 1, len_consts);
 232     return 1;
 233 }
 234
 235 static unsigned int *
 236 markblocks(unsigned char *code, Py_ssize_t len)
 237 {
 238     unsigned int *blocks = (unsigned int *)PyMem_Malloc(len*sizeof(int));
 239     int i,j, opcode, blockcnt = 0;
 240
 241     if (blocks == NULL) {
 242         PyErr_NoMemory();
 243         return NULL;
 244     }
 245     memset(blocks, 0, len*sizeof(int));
 246
 247     /* Mark labels in the first pass */
 248     for (i=0 ; i<len ; i+=CODESIZE(opcode)) {
 249         opcode = code[i];
 250         switch (opcode) {
 251             case FOR_ITER:
 252             case JUMP_FORWARD:
 253             case JUMP_IF_FALSE_OR_POP:
 254             case JUMP_IF_TRUE_OR_POP:
 255             case POP_JUMP_IF_FALSE:
 256             case POP_JUMP_IF_TRUE:
 257             case JUMP_ABSOLUTE:
 258             case CONTINUE_LOOP:
 259             case SETUP_LOOP:
 260             case SETUP_EXCEPT:
 261             case SETUP_FINALLY:
 262             case SETUP_WITH:
 263                 j = GETJUMPTGT(code, i);
 264                 blocks[j] = 1;
 265                 break;
 266         }
 267     }
 268     /* Build block numbers in the second pass */
 269     for (i=0 ; i<len ; i++) {
 270         blockcnt += blocks[i];          /* increment blockcnt over labels */
 271         blocks[i] = blockcnt;
 272     }
 273     return blocks;
 274 }
 275
 276 /* Perform basic peephole optimizations to components of a code object.
 277    The consts object should still be in list form to allow new constants
 278    to be appended.
 279
 280    To keep the optimizer simple, it bails out (does nothing) for code
 281    containing extended arguments or that has a length over 32,700.  That
 282    allows us to avoid overflow and sign issues.  Likewise, it bails when
 283    the lineno table has complex encoding for gaps >= 255.
 284
 285    Optimizations are restricted to simple transformations occuring within a
 286    single basic block.  All transformations keep the code size the same or
 287    smaller.  For those that reduce size, the gaps are initially filled with
 288    NOPs.  Later those NOPs are removed and the jump addresses retargeted in
 289    a single pass.  Line numbering is adjusted accordingly. */
 290
 291 PyObject *
 292 PyCode_Optimize(PyObject *code, PyObject* consts, PyObject *names,
 293                 PyObject *lineno_obj)
 294 {
 295     Py_ssize_t i, j, codelen;
 296     int nops, h, adj;
 297     int tgt, tgttgt, opcode;
 298     unsigned char *codestr = NULL;
 299     unsigned char *lineno;
 300     int *addrmap = NULL;
 301     int new_line, cum_orig_line, last_line, tabsiz;
 302     int cumlc=0, lastlc=0;      /* Count runs of consecutive LOAD_CONSTs */
 303     unsigned int *blocks = NULL;
 304     char *name;
 305
 306     /* Bail out if an exception is set */
 307     if (PyErr_Occurred())
 308         goto exitError;
 309
 310     /* Bypass optimization when the lineno table is too complex */
 311     assert(PyString_Check(lineno_obj));
 312     lineno = (unsigned char*)PyString_AS_STRING(lineno_obj);
 313     tabsiz = PyString_GET_SIZE(lineno_obj);
 314     if (memchr(lineno, 255, tabsiz) != NULL)
 315         goto exitUnchanged;
 316
 317     /* Avoid situations where jump retargeting could overflow */
 318     assert(PyString_Check(code));
 319     codelen = PyString_GET_SIZE(code);
 320     if (codelen > 32700)
 321         goto exitUnchanged;
 322
 323     /* Make a modifiable copy of the code string */
 324     codestr = (unsigned char *)PyMem_Malloc(codelen);
 325     if (codestr == NULL)
 326         goto exitError;
 327     codestr = (unsigned char *)memcpy(codestr,
 328                                       PyString_AS_STRING(code), codelen);
 329
 330     /* Verify that RETURN_VALUE terminates the codestring.      This allows
 331        the various transformation patterns to look ahead several
 332        instructions without additional checks to make sure they are not
 333        looking beyond the end of the code string.
 334     */
 335     if (codestr[codelen-1] != RETURN_VALUE)
 336         goto exitUnchanged;
 337
 338     /* Mapping to new jump targets after NOPs are removed */
 339     addrmap = (int *)PyMem_Malloc(codelen * sizeof(int));
 340     if (addrmap == NULL)
 341         goto exitError;
 342
 343     blocks = markblocks(codestr, codelen);
 344     if (blocks == NULL)
 345         goto exitError;
 346     assert(PyList_Check(consts));
 347
 348     for (i=0 ; i<codelen ; i += CODESIZE(codestr[i])) {
 349       reoptimize_current:
 350         opcode = codestr[i];
 351
 352         lastlc = cumlc;
 353         cumlc = 0;
 354
 355         switch (opcode) {
 356             /* Replace UNARY_NOT POP_JUMP_IF_FALSE
 357                with    POP_JUMP_IF_TRUE */
 358             case UNARY_NOT:
 359                 if (codestr[i+1] != POP_JUMP_IF_FALSE
 360                     || !ISBASICBLOCK(blocks,i,4))
 361                     continue;
 362                 j = GETARG(codestr, i+1);
 363                 codestr[i] = POP_JUMP_IF_TRUE;
 364                 SETARG(codestr, i, j);
 365                 codestr[i+3] = NOP;
 366                 goto reoptimize_current;
 367
 368                 /* not a is b -->  a is not b
 369                    not a in b -->  a not in b
 370                    not a is not b -->  a is b
 371                    not a not in b -->  a in b
 372                 */
 373             case COMPARE_OP:
 374                 j = GETARG(codestr, i);
 375                 if (j < 6  ||  j > 9  ||
 376                     codestr[i+3] != UNARY_NOT  ||
 377                     !ISBASICBLOCK(blocks,i,4))
 378                     continue;
 379                 SETARG(codestr, i, (j^1));
 380                 codestr[i+3] = NOP;
 381                 break;
 382
 383                 /* Replace LOAD_GLOBAL/LOAD_NAME None
 384                    with LOAD_CONST None */
 385             case LOAD_NAME:
 386             case LOAD_GLOBAL:
 387                 j = GETARG(codestr, i);
 388                 name = PyString_AsString(PyTuple_GET_ITEM(names, j));
 389                 if (name == NULL  ||  strcmp(name, "None") != 0)
 390                     continue;
 391                 for (j=0 ; j < PyList_GET_SIZE(consts) ; j++) {
 392                     if (PyList_GET_ITEM(consts, j) == Py_None)
 393                         break;
 394                 }
 395                 if (j == PyList_GET_SIZE(consts)) {
 396                     if (PyList_Append(consts, Py_None) == -1)
 397                         goto exitError;
 398                 }
 399                 assert(PyList_GET_ITEM(consts, j) == Py_None);
 400                 codestr[i] = LOAD_CONST;
 401                 SETARG(codestr, i, j);
 402                 cumlc = lastlc + 1;
 403                 break;
 404
 405                 /* Skip over LOAD_CONST trueconst
 406                    POP_JUMP_IF_FALSE xx. This improves
 407                    "while 1" performance. */
 408             case LOAD_CONST:
 409                 cumlc = lastlc + 1;
 410                 j = GETARG(codestr, i);
 411                 if (codestr[i+3] != POP_JUMP_IF_FALSE  ||
 412                     !ISBASICBLOCK(blocks,i,6)  ||
 413                     !PyObject_IsTrue(PyList_GET_ITEM(consts, j)))
 414                     continue;
 415                 memset(codestr+i, NOP, 6);
 416                 cumlc = 0;
 417                 break;
 418
 419                 /* Try to fold tuples of constants (includes a case for lists
 420                    which are only used for "in" and "not in" tests).
 421                    Skip over BUILD_SEQN 1 UNPACK_SEQN 1.
 422                    Replace BUILD_SEQN 2 UNPACK_SEQN 2 with ROT2.
 423                    Replace BUILD_SEQN 3 UNPACK_SEQN 3 with ROT3 ROT2. */
 424             case BUILD_TUPLE:
 425             case BUILD_LIST:
 426                 j = GETARG(codestr, i);
 427                 h = i - 3 * j;
 428                 if (h >= 0  &&
 429                     j <= lastlc                  &&
 430                     ((opcode == BUILD_TUPLE &&
 431                       ISBASICBLOCK(blocks, h, 3*(j+1))) ||
 432                      (opcode == BUILD_LIST &&
 433                       codestr[i+3]==COMPARE_OP &&
 434                       ISBASICBLOCK(blocks, h, 3*(j+2)) &&
 435                       (GETARG(codestr,i+3)==6 ||
 436                        GETARG(codestr,i+3)==7))) &&
 437                     tuple_of_constants(&codestr[h], j, consts)) {
 438                     assert(codestr[i] == LOAD_CONST);
 439                     cumlc = 1;
 440                     break;
 441                 }
 442                 if (codestr[i+3] != UNPACK_SEQUENCE  ||
 443                     !ISBASICBLOCK(blocks,i,6) ||
 444                     j != GETARG(codestr, i+3))
 445                     continue;
 446                 if (j == 1) {
 447                     memset(codestr+i, NOP, 6);
 448                 } else if (j == 2) {
 449                     codestr[i] = ROT_TWO;
 450                     memset(codestr+i+1, NOP, 5);
 451                 } else if (j == 3) {
 452                     codestr[i] = ROT_THREE;
 453                     codestr[i+1] = ROT_TWO;
 454                     memset(codestr+i+2, NOP, 4);
 455                 }
 456                 break;
 457
 458                 /* Fold binary ops on constants.
 459                    LOAD_CONST c1 LOAD_CONST c2 BINOP -->  LOAD_CONST binop(c1,c2) */
 460             case BINARY_POWER:
 461             case BINARY_MULTIPLY:
 462             case BINARY_TRUE_DIVIDE:
 463             case BINARY_FLOOR_DIVIDE:
 464             case BINARY_MODULO:
 465             case BINARY_ADD:
 466             case BINARY_SUBTRACT:
 467             case BINARY_SUBSCR:
 468             case BINARY_LSHIFT:
 469             case BINARY_RSHIFT:
 470             case BINARY_AND:
 471             case BINARY_XOR:
 472             case BINARY_OR:
 473                 if (lastlc >= 2                  &&
 474                     ISBASICBLOCK(blocks, i-6, 7)  &&
 475                     fold_binops_on_constants(&codestr[i-6], consts)) {
 476                     i -= 2;
 477                     assert(codestr[i] == LOAD_CONST);
 478                     cumlc = 1;
 479                 }
 480                 break;
 481
 482                 /* Fold unary ops on constants.
 483                    LOAD_CONST c1  UNARY_OP -->                  LOAD_CONST unary_op(c) */
 484             case UNARY_NEGATIVE:
 485             case UNARY_CONVERT:
 486             case UNARY_INVERT:
 487                 if (lastlc >= 1                  &&
 488                     ISBASICBLOCK(blocks, i-3, 4)  &&
 489                     fold_unaryops_on_constants(&codestr[i-3], consts))                  {
 490                     i -= 2;
 491                     assert(codestr[i] == LOAD_CONST);
 492                     cumlc = 1;
 493                 }
 494                 break;
 495
 496                 /* Simplify conditional jump to conditional jump where the
 497                    result of the first test implies the success of a similar
 498                    test or the failure of the opposite test.
 499                    Arises in code like:
 500                    "if a and b:"
 501                    "if a or b:"
 502                    "a and b or c"
 503                    "(a and b) and c"
 504                    x:JUMP_IF_FALSE_OR_POP y   y:JUMP_IF_FALSE_OR_POP z
 505                       -->  x:JUMP_IF_FALSE_OR_POP z
 506                    x:JUMP_IF_FALSE_OR_POP y   y:JUMP_IF_TRUE_OR_POP z
 507                       -->  x:POP_JUMP_IF_FALSE y+3
 508                    where y+3 is the instruction following the second test.
 509                 */
 510             case JUMP_IF_FALSE_OR_POP:
 511             case JUMP_IF_TRUE_OR_POP:
 512                 tgt = GETJUMPTGT(codestr, i);
 513                 j = codestr[tgt];
 514                 if (CONDITIONAL_JUMP(j)) {
 515                     /* NOTE: all possible jumps here are
 516                        absolute! */
 517                     if (JUMPS_ON_TRUE(j) == JUMPS_ON_TRUE(opcode)) {
 518                         /* The second jump will be
 519                            taken iff the first is. */
 520                         tgttgt = GETJUMPTGT(codestr, tgt);
 521                         /* The current opcode inherits
 522                            its target's stack behaviour */
 523                         codestr[i] = j;
 524                         SETARG(codestr, i, tgttgt);
 525                         goto reoptimize_current;
 526                     } else {
 527                         /* The second jump is not taken
 528                            if the first is (so jump past
 529                            it), and all conditional
 530                            jumps pop their argument when
 531                            they're not taken (so change
 532                            the first jump to pop its
 533                            argument when it's taken). */
 534                         if (JUMPS_ON_TRUE(opcode))
 535                             codestr[i] = POP_JUMP_IF_TRUE;
 536                         else
 537                             codestr[i] = POP_JUMP_IF_FALSE;
 538                         SETARG(codestr, i, (tgt + 3));
 539                         goto reoptimize_current;
 540                     }
 541                 }
 542                 /* Intentional fallthrough */
 543
 544                 /* Replace jumps to unconditional jumps */
 545             case POP_JUMP_IF_FALSE:
 546             case POP_JUMP_IF_TRUE:
 547             case FOR_ITER:
 548             case JUMP_FORWARD:
 549             case JUMP_ABSOLUTE:
 550             case CONTINUE_LOOP:
 551             case SETUP_LOOP:
 552             case SETUP_EXCEPT:
 553             case SETUP_FINALLY:
 554             case SETUP_WITH:
 555                 tgt = GETJUMPTGT(codestr, i);
 556                 /* Replace JUMP_* to a RETURN into just a RETURN */
 557                 if (UNCONDITIONAL_JUMP(opcode) &&
 558                     codestr[tgt] == RETURN_VALUE) {
 559                     codestr[i] = RETURN_VALUE;
 560                     memset(codestr+i+1, NOP, 2);
 561                     continue;
 562                 }
 563                 if (!UNCONDITIONAL_JUMP(codestr[tgt]))
 564                     continue;
 565                 tgttgt = GETJUMPTGT(codestr, tgt);
 566                 if (opcode == JUMP_FORWARD) /* JMP_ABS can go backwards */
 567                     opcode = JUMP_ABSOLUTE;
 568                 if (!ABSOLUTE_JUMP(opcode))
 569                     tgttgt -= i + 3;     /* Calc relative jump addr */
 570                 if (tgttgt < 0)                           /* No backward relative jumps */
 571                     continue;
 572                 codestr[i] = opcode;
 573                 SETARG(codestr, i, tgttgt);
 574                 break;
 575
 576             case EXTENDED_ARG:
 577                 goto exitUnchanged;
 578
 579                 /* Replace RETURN LOAD_CONST None RETURN with just RETURN */
 580                 /* Remove unreachable JUMPs after RETURN */
 581             case RETURN_VALUE:
 582                 if (i+4 >= codelen)
 583                     continue;
 584                 if (codestr[i+4] == RETURN_VALUE &&
 585                     ISBASICBLOCK(blocks,i,5))
 586                     memset(codestr+i+1, NOP, 4);
 587                 else if (UNCONDITIONAL_JUMP(codestr[i+1]) &&
 588                          ISBASICBLOCK(blocks,i,4))
 589                     memset(codestr+i+1, NOP, 3);
 590                 break;
 591         }
 592     }
 593
 594     /* Fixup linenotab */
 595     for (i=0, nops=0 ; i<codelen ; i += CODESIZE(codestr[i])) {
 596         addrmap[i] = i - nops;
 597         if (codestr[i] == NOP)
 598             nops++;
 599     }
 600     cum_orig_line = 0;
 601     last_line = 0;
 602     for (i=0 ; i < tabsiz ; i+=2) {
 603         cum_orig_line += lineno[i];
 604         new_line = addrmap[cum_orig_line];
 605         assert (new_line - last_line < 255);
 606         lineno[i] =((unsigned char)(new_line - last_line));
 607         last_line = new_line;
 608     }
 609
 610     /* Remove NOPs and fixup jump targets */
 611     for (i=0, h=0 ; i<codelen ; ) {
 612         opcode = codestr[i];
 613         switch (opcode) {
 614             case NOP:
 615                 i++;
 616                 continue;
 617
 618             case JUMP_ABSOLUTE:
 619             case CONTINUE_LOOP:
 620             case POP_JUMP_IF_FALSE:
 621             case POP_JUMP_IF_TRUE:
 622             case JUMP_IF_FALSE_OR_POP:
 623             case JUMP_IF_TRUE_OR_POP:
 624                 j = addrmap[GETARG(codestr, i)];
 625                 SETARG(codestr, i, j);
 626                 break;
 627
 628             case FOR_ITER:
 629             case JUMP_FORWARD:
 630             case SETUP_LOOP:
 631             case SETUP_EXCEPT:
 632             case SETUP_FINALLY:
 633             case SETUP_WITH:
 634                 j = addrmap[GETARG(codestr, i) + i + 3] - addrmap[i] - 3;
 635                 SETARG(codestr, i, j);
 636                 break;
 637         }
 638         adj = CODESIZE(opcode);
 639         while (adj--)
 640             codestr[h++] = codestr[i++];
 641     }
 642     assert(h + nops == codelen);
 643
 644     code = PyString_FromStringAndSize((char *)codestr, h);
 645     PyMem_Free(addrmap);
 646     PyMem_Free(codestr);
 647     PyMem_Free(blocks);
 648     return code;
 649
 650  exitError:
 651     code = NULL;
 652
 653  exitUnchanged:
 654     if (blocks != NULL)
 655         PyMem_Free(blocks);
 656     if (addrmap != NULL)
 657         PyMem_Free(addrmap);
 658     if (codestr != NULL)
 659         PyMem_Free(codestr);
 660     Py_XINCREF(code);
 661     return code;
 662 }