peephole.c 18.7 KB
Newer Older
1
/* Peephole optimizations for bytecode compiler. */
2 3 4 5 6 7 8 9 10 11 12 13 14 15

#include "Python.h"

#include "Python-ast.h"
#include "node.h"
#include "pyarena.h"
#include "ast.h"
#include "code.h"
#include "compile.h"
#include "symtable.h"
#include "opcode.h"

#define GETARG(arr, i) ((int)((arr[i+2]<<8) + arr[i+1]))
#define UNCONDITIONAL_JUMP(op)	(op==JUMP_ABSOLUTE || op==JUMP_FORWARD)
16 17 18 19 20 21
#define CONDITIONAL_JUMP(op) (op==POP_JUMP_IF_FALSE || op==POP_JUMP_IF_TRUE \
	|| op==JUMP_IF_FALSE_OR_POP || op==JUMP_IF_TRUE_OR_POP)
#define ABSOLUTE_JUMP(op) (op==JUMP_ABSOLUTE || op==CONTINUE_LOOP \
	|| op==POP_JUMP_IF_FALSE || op==POP_JUMP_IF_TRUE \
	|| op==JUMP_IF_FALSE_OR_POP || op==JUMP_IF_TRUE_OR_POP)
#define JUMPS_ON_TRUE(op) (op==POP_JUMP_IF_TRUE || op==JUMP_IF_TRUE_OR_POP)
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
#define GETJUMPTGT(arr, i) (GETARG(arr,i) + (ABSOLUTE_JUMP(arr[i]) ? 0 : i+3))
#define SETARG(arr, i, val) arr[i+2] = val>>8; arr[i+1] = val & 255
#define CODESIZE(op)  (HAS_ARG(op) ? 3 : 1)
#define ISBASICBLOCK(blocks, start, bytes) \
	(blocks[start]==blocks[start+bytes-1])

/* Replace LOAD_CONST c1. LOAD_CONST c2 ... LOAD_CONST cn BUILD_TUPLE n
   with	   LOAD_CONST (c1, c2, ... cn).
   The consts table must still be in list form so that the
   new constant (c1, c2, ... cn) can be appended.
   Called with codestr pointing to the first LOAD_CONST.
   Bails out with no change if one or more of the LOAD_CONSTs is missing. 
   Also works for BUILD_LIST when followed by an "in" or "not in" test.
*/
static int
Christian Heimes's avatar
Christian Heimes committed
37
tuple_of_constants(unsigned char *codestr, Py_ssize_t n, PyObject *consts)
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199
{
	PyObject *newconst, *constant;
	Py_ssize_t i, arg, len_consts;

	/* Pre-conditions */
	assert(PyList_CheckExact(consts));
	assert(codestr[n*3] == BUILD_TUPLE || codestr[n*3] == BUILD_LIST);
	assert(GETARG(codestr, (n*3)) == n);
	for (i=0 ; i<n ; i++)
		assert(codestr[i*3] == LOAD_CONST);

	/* Buildup new tuple of constants */
	newconst = PyTuple_New(n);
	if (newconst == NULL)
		return 0;
	len_consts = PyList_GET_SIZE(consts);
	for (i=0 ; i<n ; i++) {
		arg = GETARG(codestr, (i*3));
		assert(arg < len_consts);
		constant = PyList_GET_ITEM(consts, arg);
		Py_INCREF(constant);
		PyTuple_SET_ITEM(newconst, i, constant);
	}

	/* Append folded constant onto consts */
	if (PyList_Append(consts, newconst)) {
		Py_DECREF(newconst);
		return 0;
	}
	Py_DECREF(newconst);

	/* Write NOPs over old LOAD_CONSTS and
	   add a new LOAD_CONST newconst on top of the BUILD_TUPLE n */
	memset(codestr, NOP, n*3);
	codestr[n*3] = LOAD_CONST;
	SETARG(codestr, (n*3), len_consts);
	return 1;
}

/* Replace LOAD_CONST c1. LOAD_CONST c2 BINOP
   with	   LOAD_CONST binop(c1,c2)
   The consts table must still be in list form so that the
   new constant can be appended.
   Called with codestr pointing to the first LOAD_CONST. 
   Abandons the transformation if the folding fails (i.e.  1+'a').  
   If the new constant is a sequence, only folds when the size
   is below a threshold value.	That keeps pyc files from
   becoming large in the presence of code like:	 (None,)*1000.
*/
static int
fold_binops_on_constants(unsigned char *codestr, PyObject *consts)
{
	PyObject *newconst, *v, *w;
	Py_ssize_t len_consts, size;
	int opcode;

	/* Pre-conditions */
	assert(PyList_CheckExact(consts));
	assert(codestr[0] == LOAD_CONST);
	assert(codestr[3] == LOAD_CONST);

	/* Create new constant */
	v = PyList_GET_ITEM(consts, GETARG(codestr, 0));
	w = PyList_GET_ITEM(consts, GETARG(codestr, 3));
	opcode = codestr[6];
	switch (opcode) {
		case BINARY_POWER:
			newconst = PyNumber_Power(v, w, Py_None);
			break;
		case BINARY_MULTIPLY:
			newconst = PyNumber_Multiply(v, w);
			break;
		case BINARY_TRUE_DIVIDE:
			newconst = PyNumber_TrueDivide(v, w);
			break;
		case BINARY_FLOOR_DIVIDE:
			newconst = PyNumber_FloorDivide(v, w);
			break;
		case BINARY_MODULO:
			newconst = PyNumber_Remainder(v, w);
			break;
		case BINARY_ADD:
			newconst = PyNumber_Add(v, w);
			break;
		case BINARY_SUBTRACT:
			newconst = PyNumber_Subtract(v, w);
			break;
		case BINARY_SUBSCR:
			newconst = PyObject_GetItem(v, w);
			break;
		case BINARY_LSHIFT:
			newconst = PyNumber_Lshift(v, w);
			break;
		case BINARY_RSHIFT:
			newconst = PyNumber_Rshift(v, w);
			break;
		case BINARY_AND:
			newconst = PyNumber_And(v, w);
			break;
		case BINARY_XOR:
			newconst = PyNumber_Xor(v, w);
			break;
		case BINARY_OR:
			newconst = PyNumber_Or(v, w);
			break;
		default:
			/* Called with an unknown opcode */
			PyErr_Format(PyExc_SystemError,
			     "unexpected binary operation %d on a constant",
				     opcode);
			return 0;
	}
	if (newconst == NULL) {
		PyErr_Clear();
		return 0;
	}
	size = PyObject_Size(newconst);
	if (size == -1)
		PyErr_Clear();
	else if (size > 20) {
		Py_DECREF(newconst);
		return 0;
	}

	/* Append folded constant into consts table */
	len_consts = PyList_GET_SIZE(consts);
	if (PyList_Append(consts, newconst)) {
		Py_DECREF(newconst);
		return 0;
	}
	Py_DECREF(newconst);

	/* Write NOP NOP NOP NOP LOAD_CONST newconst */
	memset(codestr, NOP, 4);
	codestr[4] = LOAD_CONST;
	SETARG(codestr, 4, len_consts);
	return 1;
}

static int
fold_unaryops_on_constants(unsigned char *codestr, PyObject *consts)
{
	PyObject *newconst=NULL, *v;
	Py_ssize_t len_consts;
	int opcode;

	/* Pre-conditions */
	assert(PyList_CheckExact(consts));
	assert(codestr[0] == LOAD_CONST);

	/* Create new constant */
	v = PyList_GET_ITEM(consts, GETARG(codestr, 0));
	opcode = codestr[3];
	switch (opcode) {
		case UNARY_NEGATIVE:
			/* Preserve the sign of -0.0 */
			if (PyObject_IsTrue(v) == 1)
				newconst = PyNumber_Negative(v);
			break;
		case UNARY_INVERT:
			newconst = PyNumber_Invert(v);
			break;
200 201 202
		case UNARY_POSITIVE:
			newconst = PyNumber_Positive(v);
			break;
203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
		default:
			/* Called with an unknown opcode */
			PyErr_Format(PyExc_SystemError,
			     "unexpected unary operation %d on a constant",
				     opcode);
			return 0;
	}
	if (newconst == NULL) {
		PyErr_Clear();
		return 0;
	}

	/* Append folded constant into consts table */
	len_consts = PyList_GET_SIZE(consts);
	if (PyList_Append(consts, newconst)) {
		Py_DECREF(newconst);
		return 0;
	}
	Py_DECREF(newconst);

	/* Write NOP LOAD_CONST newconst */
	codestr[0] = NOP;
	codestr[1] = LOAD_CONST;
	SETARG(codestr, 1, len_consts);
	return 1;
}

static unsigned int *
Christian Heimes's avatar
Christian Heimes committed
231
markblocks(unsigned char *code, Py_ssize_t len)
232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247
{
	unsigned int *blocks = (unsigned int *)PyMem_Malloc(len*sizeof(int));
	int i,j, opcode, blockcnt = 0;

	if (blocks == NULL) {
		PyErr_NoMemory();
		return NULL;
	}
	memset(blocks, 0, len*sizeof(int));

	/* Mark labels in the first pass */
	for (i=0 ; i<len ; i+=CODESIZE(opcode)) {
		opcode = code[i];
		switch (opcode) {
			case FOR_ITER:
			case JUMP_FORWARD:
248 249 250 251
			case JUMP_IF_FALSE_OR_POP:
			case JUMP_IF_TRUE_OR_POP:
			case POP_JUMP_IF_FALSE:
			case POP_JUMP_IF_TRUE:
252 253 254 255 256
			case JUMP_ABSOLUTE:
			case CONTINUE_LOOP:
			case SETUP_LOOP:
			case SETUP_EXCEPT:
			case SETUP_FINALLY:
257
			case SETUP_WITH:
258 259 260 261 262 263 264 265 266 267 268 269 270
				j = GETJUMPTGT(code, i);
				blocks[j] = 1;
				break;
		}
	}
	/* Build block numbers in the second pass */
	for (i=0 ; i<len ; i++) {
		blockcnt += blocks[i];	/* increment blockcnt over labels */
		blocks[i] = blockcnt;
	}
	return blocks;
}

271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301
/* Helper to replace LOAD_NAME None/True/False with LOAD_CONST
   Returns: 0 if no change, 1 if change, -1 if error */
static int
load_global(unsigned char *codestr, Py_ssize_t i, char *name, PyObject *consts)
{
	Py_ssize_t j;
	PyObject *obj;
	if (name == NULL)
		return 0;
	if (strcmp(name, "None") == 0)
		obj = Py_None;
	else if (strcmp(name, "True") == 0)
		obj = Py_True;
	else if (strcmp(name, "False") == 0)
		obj = Py_False;
	else
		return 0;
	for (j = 0; j < PyList_GET_SIZE(consts); j++) {
		if (PyList_GET_ITEM(consts, j) == obj)
			break;
	}
	if (j == PyList_GET_SIZE(consts)) {
		if (PyList_Append(consts, obj) < 0)
			return -1;
	}
	assert(PyList_GET_ITEM(consts, j) == obj);
	codestr[i] = LOAD_CONST;
	SETARG(codestr, i, j);
	return 1;
}

302 303 304 305
/* Perform basic peephole optimizations to components of a code object.
   The consts object should still be in list form to allow new constants 
   to be appended.

306 307 308 309 310 311
   To keep the optimizer simple, it bails out (does nothing) for code that
   has a length over 32,700, and does not calculate extended arguments. 
   That allows us to avoid overflow and sign issues. Likewise, it bails when
   the lineno table has complex encoding for gaps >= 255. EXTENDED_ARG can
   appear before MAKE_FUNCTION; in this case both opcodes are skipped.
   EXTENDED_ARG preceding any other opcode causes the optimizer to bail.
312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335

   Optimizations are restricted to simple transformations occuring within a
   single basic block.	All transformations keep the code size the same or 
   smaller.  For those that reduce size, the gaps are initially filled with 
   NOPs.  Later those NOPs are removed and the jump addresses retargeted in 
   a single pass.  Line numbering is adjusted accordingly. */

PyObject *
PyCode_Optimize(PyObject *code, PyObject* consts, PyObject *names,
                PyObject *lineno_obj)
{
	Py_ssize_t i, j, codelen;
	int nops, h, adj;
	int tgt, tgttgt, opcode;
	unsigned char *codestr = NULL;
	unsigned char *lineno;
	int *addrmap = NULL;
	int new_line, cum_orig_line, last_line, tabsiz;
	int cumlc=0, lastlc=0;	/* Count runs of consecutive LOAD_CONSTs */
	unsigned int *blocks = NULL;
	char *name;

	/* Bail out if an exception is set */
	if (PyErr_Occurred())
336
		goto exitError;
337 338

	/* Bypass optimization when the lineno table is too complex */
339 340 341
	assert(PyBytes_Check(lineno_obj));
	lineno = (unsigned char*)PyBytes_AS_STRING(lineno_obj);
	tabsiz = PyBytes_GET_SIZE(lineno_obj);
342 343 344 345
	if (memchr(lineno, 255, tabsiz) != NULL)
		goto exitUnchanged;

	/* Avoid situations where jump retargeting could overflow */
346 347
	assert(PyBytes_Check(code));
	codelen = PyBytes_GET_SIZE(code);
348 349 350 351 352 353
	if (codelen > 32700)
		goto exitUnchanged;

	/* Make a modifiable copy of the code string */
	codestr = (unsigned char *)PyMem_Malloc(codelen);
	if (codestr == NULL)
354
		goto exitError;
355
	codestr = (unsigned char *)memcpy(codestr, 
356
					  PyBytes_AS_STRING(code), codelen);
357 358 359 360 361 362 363 364 365 366 367 368

	/* Verify that RETURN_VALUE terminates the codestring.	This allows
	   the various transformation patterns to look ahead several
	   instructions without additional checks to make sure they are not
	   looking beyond the end of the code string.
	*/
	if (codestr[codelen-1] != RETURN_VALUE)
		goto exitUnchanged;

	/* Mapping to new jump targets after NOPs are removed */
	addrmap = (int *)PyMem_Malloc(codelen * sizeof(int));
	if (addrmap == NULL)
369
		goto exitError;
370 371 372

	blocks = markblocks(codestr, codelen);
	if (blocks == NULL)
373
		goto exitError;
374 375 376
	assert(PyList_Check(consts));

	for (i=0 ; i<codelen ; i += CODESIZE(codestr[i])) {
377
	  reoptimize_current:
378 379 380 381 382 383
		opcode = codestr[i];

		lastlc = cumlc;
		cumlc = 0;

		switch (opcode) {
384 385
			/* Replace UNARY_NOT POP_JUMP_IF_FALSE 
			   with    POP_JUMP_IF_TRUE */
386
			case UNARY_NOT:
387 388
				if (codestr[i+1] != POP_JUMP_IF_FALSE
				    || !ISBASICBLOCK(blocks,i,4))
389
					continue;
390 391
				j = GETARG(codestr, i+1);
				codestr[i] = POP_JUMP_IF_TRUE;
392
				SETARG(codestr, i, j);
393 394
				codestr[i+3] = NOP;
				goto reoptimize_current;
395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410

				/* not a is b -->  a is not b
				   not a in b -->  a not in b
				   not a is not b -->  a is b
				   not a not in b -->  a in b
				*/
			case COMPARE_OP:
				j = GETARG(codestr, i);
				if (j < 6  ||  j > 9  ||
				    codestr[i+3] != UNARY_NOT  || 
				    !ISBASICBLOCK(blocks,i,4))
					continue;
				SETARG(codestr, i, (j^1));
				codestr[i+3] = NOP;
				break;

411 412
				/* Replace LOAD_GLOBAL/LOAD_NAME None/True/False
                                   with LOAD_CONST None/True/False */
413 414 415
			case LOAD_NAME:
			case LOAD_GLOBAL:
				j = GETARG(codestr, i);
416
				name = _PyUnicode_AsString(PyTuple_GET_ITEM(names, j));
417 418
				h = load_global(codestr, i, name, consts);
				if (h < 0)
419
					goto exitError;
420
				else if (h == 0)
421
					continue;
422
				cumlc = lastlc + 1;
423 424 425
				break;

				/* Skip over LOAD_CONST trueconst
426 427
				   POP_JUMP_IF_FALSE xx. This improves
				   "while 1" performance. */
428 429 430
			case LOAD_CONST:
				cumlc = lastlc + 1;
				j = GETARG(codestr, i);
431
				if (codestr[i+3] != POP_JUMP_IF_FALSE  ||
432
				    !ISBASICBLOCK(blocks,i,6)  ||
433 434
				    !PyObject_IsTrue(PyList_GET_ITEM(consts, j)))
					continue;
435
				memset(codestr+i, NOP, 6);
436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505
				cumlc = 0;
				break;

				/* Try to fold tuples of constants (includes a case for lists
				   which are only used for "in" and "not in" tests).
				   Skip over BUILD_SEQN 1 UNPACK_SEQN 1.
				   Replace BUILD_SEQN 2 UNPACK_SEQN 2 with ROT2.
				   Replace BUILD_SEQN 3 UNPACK_SEQN 3 with ROT3 ROT2. */
			case BUILD_TUPLE:
			case BUILD_LIST:
				j = GETARG(codestr, i);
				h = i - 3 * j;
				if (h >= 0  &&
				    j <= lastlc	 &&
				    ((opcode == BUILD_TUPLE && 
				      ISBASICBLOCK(blocks, h, 3*(j+1))) ||
				     (opcode == BUILD_LIST && 
				      codestr[i+3]==COMPARE_OP && 
				      ISBASICBLOCK(blocks, h, 3*(j+2)) &&
				      (GETARG(codestr,i+3)==6 ||
				       GETARG(codestr,i+3)==7))) &&
				    tuple_of_constants(&codestr[h], j, consts)) {
					assert(codestr[i] == LOAD_CONST);
					cumlc = 1;
					break;
				}
				if (codestr[i+3] != UNPACK_SEQUENCE  ||
				    !ISBASICBLOCK(blocks,i,6) ||
				    j != GETARG(codestr, i+3))
					continue;
				if (j == 1) {
					memset(codestr+i, NOP, 6);
				} else if (j == 2) {
					codestr[i] = ROT_TWO;
					memset(codestr+i+1, NOP, 5);
				} else if (j == 3) {
					codestr[i] = ROT_THREE;
					codestr[i+1] = ROT_TWO;
					memset(codestr+i+2, NOP, 4);
				}
				break;

				/* Fold binary ops on constants.
				   LOAD_CONST c1 LOAD_CONST c2 BINOP -->  LOAD_CONST binop(c1,c2) */
			case BINARY_POWER:
			case BINARY_MULTIPLY:
			case BINARY_TRUE_DIVIDE:
			case BINARY_FLOOR_DIVIDE:
			case BINARY_MODULO:
			case BINARY_ADD:
			case BINARY_SUBTRACT:
			case BINARY_SUBSCR:
			case BINARY_LSHIFT:
			case BINARY_RSHIFT:
			case BINARY_AND:
			case BINARY_XOR:
			case BINARY_OR:
				if (lastlc >= 2	 &&
				    ISBASICBLOCK(blocks, i-6, 7)  &&
				    fold_binops_on_constants(&codestr[i-6], consts)) {
					i -= 2;
					assert(codestr[i] == LOAD_CONST);
					cumlc = 1;
				}
				break;

				/* Fold unary ops on constants.
				   LOAD_CONST c1  UNARY_OP -->	LOAD_CONST unary_op(c) */
			case UNARY_NEGATIVE:
			case UNARY_INVERT:
506
			case UNARY_POSITIVE:
507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523
				if (lastlc >= 1	 &&
				    ISBASICBLOCK(blocks, i-3, 4)  &&
				    fold_unaryops_on_constants(&codestr[i-3], consts))	{
					i -= 2;
					assert(codestr[i] == LOAD_CONST);
					cumlc = 1;
				}
				break;

				/* Simplify conditional jump to conditional jump where the
				   result of the first test implies the success of a similar
				   test or the failure of the opposite test.
				   Arises in code like:
				   "if a and b:"
				   "if a or b:"
				   "a and b or c"
				   "(a and b) and c"
524 525 526 527
				   x:JUMP_IF_FALSE_OR_POP y   y:JUMP_IF_FALSE_OR_POP z
				      -->  x:JUMP_IF_FALSE_OR_POP z
				   x:JUMP_IF_FALSE_OR_POP y   y:JUMP_IF_TRUE_OR_POP z
				      -->  x:POP_JUMP_IF_FALSE y+3
528 529
				   where y+3 is the instruction following the second test.
				*/
530 531
			case JUMP_IF_FALSE_OR_POP:
			case JUMP_IF_TRUE_OR_POP:
532 533
				tgt = GETJUMPTGT(codestr, i);
				j = codestr[tgt];
534 535 536 537 538 539 540 541 542 543
				if (CONDITIONAL_JUMP(j)) {
					/* NOTE: all possible jumps here are
					   absolute! */
					if (JUMPS_ON_TRUE(j) == JUMPS_ON_TRUE(opcode)) {
						/* The second jump will be
						   taken iff the first is. */
						tgttgt = GETJUMPTGT(codestr, tgt);
						/* The current opcode inherits
						   its target's stack behaviour */
						codestr[i] = j;
544
						SETARG(codestr, i, tgttgt);
545
						goto reoptimize_current;
546
					} else {
547 548 549 550 551 552 553 554 555 556 557 558 559
						/* The second jump is not taken
						   if the first is (so jump past
						   it), and all conditional
						   jumps pop their argument when
						   they're not taken (so change
						   the first jump to pop its
						   argument when it's taken). */
						if (JUMPS_ON_TRUE(opcode))
							codestr[i] = POP_JUMP_IF_TRUE;
						else
							codestr[i] = POP_JUMP_IF_FALSE;
						SETARG(codestr, i, (tgt + 3));
						goto reoptimize_current;
560 561
					}
				}
562
				/* Intentional fallthrough */
563 564

				/* Replace jumps to unconditional jumps */
565 566
			case POP_JUMP_IF_FALSE:
			case POP_JUMP_IF_TRUE:
567 568 569 570 571 572 573
			case FOR_ITER:
			case JUMP_FORWARD:
			case JUMP_ABSOLUTE:
			case CONTINUE_LOOP:
			case SETUP_LOOP:
			case SETUP_EXCEPT:
			case SETUP_FINALLY:
574
			case SETUP_WITH:
575
				tgt = GETJUMPTGT(codestr, i);
576 577 578 579 580 581 582
				/* Replace JUMP_* to a RETURN into just a RETURN */
				if (UNCONDITIONAL_JUMP(opcode) &&
				    codestr[tgt] == RETURN_VALUE) {
					codestr[i] = RETURN_VALUE;
					memset(codestr+i+1, NOP, 2);
					continue;
				}
583 584 585 586 587 588 589 590 591 592 593 594 595 596
				if (!UNCONDITIONAL_JUMP(codestr[tgt]))
					continue;
				tgttgt = GETJUMPTGT(codestr, tgt);
				if (opcode == JUMP_FORWARD) /* JMP_ABS can go backwards */
					opcode = JUMP_ABSOLUTE;
				if (!ABSOLUTE_JUMP(opcode))
					tgttgt -= i + 3;     /* Calc relative jump addr */
				if (tgttgt < 0)		  /* No backward relative jumps */
					continue;
				codestr[i] = opcode;
				SETARG(codestr, i, tgttgt);
				break;

			case EXTENDED_ARG:
597 598 599 600 601
				if (codestr[i+3] != MAKE_FUNCTION)
					goto exitUnchanged;
				/* don't visit MAKE_FUNCTION as GETARG will be wrong */
				i += 3;
				break;
602 603

				/* Replace RETURN LOAD_CONST None RETURN with just RETURN */
604
				/* Remove unreachable JUMPs after RETURN */
605
			case RETURN_VALUE:
606
				if (i+4 >= codelen)
607
					continue;
608 609 610 611 612 613
				if (codestr[i+4] == RETURN_VALUE &&
				    ISBASICBLOCK(blocks,i,5))
					memset(codestr+i+1, NOP, 4);
				else if (UNCONDITIONAL_JUMP(codestr[i+1]) &&
				         ISBASICBLOCK(blocks,i,4))
					memset(codestr+i+1, NOP, 3);
614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643
				break;
		}
	}

	/* Fixup linenotab */
	for (i=0, nops=0 ; i<codelen ; i += CODESIZE(codestr[i])) {
		addrmap[i] = i - nops;
		if (codestr[i] == NOP)
			nops++;
	}
	cum_orig_line = 0;
	last_line = 0;
	for (i=0 ; i < tabsiz ; i+=2) {
		cum_orig_line += lineno[i];
		new_line = addrmap[cum_orig_line];
		assert (new_line - last_line < 255);
		lineno[i] =((unsigned char)(new_line - last_line));
		last_line = new_line;
	}

	/* Remove NOPs and fixup jump targets */
	for (i=0, h=0 ; i<codelen ; ) {
		opcode = codestr[i];
		switch (opcode) {
			case NOP:
				i++;
				continue;

			case JUMP_ABSOLUTE:
			case CONTINUE_LOOP:
644 645 646 647
			case POP_JUMP_IF_FALSE:
			case POP_JUMP_IF_TRUE:
			case JUMP_IF_FALSE_OR_POP:
			case JUMP_IF_TRUE_OR_POP:
648 649 650 651 652 653 654 655 656
				j = addrmap[GETARG(codestr, i)];
				SETARG(codestr, i, j);
				break;

			case FOR_ITER:
			case JUMP_FORWARD:
			case SETUP_LOOP:
			case SETUP_EXCEPT:
			case SETUP_FINALLY:
657
			case SETUP_WITH:
658 659 660 661 662 663 664 665 666 667
				j = addrmap[GETARG(codestr, i) + i + 3] - addrmap[i] - 3;
				SETARG(codestr, i, j);
				break;
		}
		adj = CODESIZE(opcode);
		while (adj--)
			codestr[h++] = codestr[i++];
	}
	assert(h + nops == codelen);

668
	code = PyBytes_FromStringAndSize((char *)codestr, h);
669 670 671 672 673
	PyMem_Free(addrmap);
	PyMem_Free(codestr);
	PyMem_Free(blocks);
	return code;

674 675 676
 exitError:
	code = NULL;

677 678 679 680 681 682 683
 exitUnchanged:
	if (blocks != NULL)
		PyMem_Free(blocks);
	if (addrmap != NULL)
		PyMem_Free(addrmap);
	if (codestr != NULL)
		PyMem_Free(codestr);
684
	Py_XINCREF(code);
685 686
	return code;
}