1 

     2 /* Execute compiled code */

     3 

     4 /* XXX TO DO:

     5    XXX speed up searching for keywords by using a dictionary

     6    XXX document it!

     7    */

     8 

     9 /* enable more aggressive intra-module optimizations, where available */

    10 #define PY_LOCAL_AGGRESSIVE

    11 

    12 #include "Python.h"

    13 

    14 #include "code.h"

    15 #include "frameobject.h"

    16 #include "eval.h"

    17 #include "opcode.h"

    18 #include "structmember.h"

    19 

    20 #include <ctype.h>

    21 

    22 #ifndef WITH_TSC

    23 

    24 #define READ_TIMESTAMP(var)

    25 

    26 #else

    27 

    28 typedef unsigned long long uint64;

    29 

    30 #if defined(__ppc__) /* <- Don't know if this is the correct symbol; this

    31 			   section should work for GCC on any PowerPC

    32 			   platform, irrespective of OS.

    33 			   POWER?  Who knows :-) */

    34 

    35 #define READ_TIMESTAMP(var) ppc_getcounter(&var)

    36 

    37 static void

    38 ppc_getcounter(uint64 *v)

    39 {

    40 	register unsigned long tbu, tb, tbu2;

    41 

    42   loop:

    43 	asm volatile ("mftbu %0" : "=r" (tbu) );

    44 	asm volatile ("mftb  %0" : "=r" (tb)  );

    45 	asm volatile ("mftbu %0" : "=r" (tbu2));

    46 	if (__builtin_expect(tbu != tbu2, 0)) goto loop;

    47 

    48 	/* The slightly peculiar way of writing the next lines is

    49 	   compiled better by GCC than any other way I tried. */

    50 	((long*)(v))[0] = tbu;

    51 	((long*)(v))[1] = tb;

    52 }

    53 

    54 #else /* this is for linux/x86 (and probably any other GCC/x86 combo) */

    55 

    56 #define READ_TIMESTAMP(val) \

    57      __asm__ __volatile__("rdtsc" : "=A" (val))

    58 

    59 #endif

    60 

    61 void dump_tsc(int opcode, int ticked, uint64 inst0, uint64 inst1,

    62 	      uint64 loop0, uint64 loop1, uint64 intr0, uint64 intr1)

    63 {

    64 	uint64 intr, inst, loop;

    65 	PyThreadState *tstate = PyThreadState_Get();

    66 	if (!tstate->interp->tscdump)

    67 		return;

    68 	intr = intr1 - intr0;

    69 	inst = inst1 - inst0 - intr;

    70 	loop = loop1 - loop0 - intr;

    71 	fprintf(stderr, "opcode=%03d t=%d inst=%06lld loop=%06lld\n",

    72 		opcode, ticked, inst, loop);

    73 }

    74 

    75 #endif

    76 

    77 /* Turn this on if your compiler chokes on the big switch: */

    78 /* #define CASE_TOO_BIG 1 */

    79 

    80 #ifdef Py_DEBUG

    81 /* For debugging the interpreter: */

    82 #define LLTRACE  1	/* Low-level trace feature */

    83 #define CHECKEXC 1	/* Double-check exception checking */

    84 #endif

    85 

    86 typedef PyObject *(*callproc)(PyObject *, PyObject *, PyObject *);

    87 

    88 /* Forward declarations */

    89 #ifdef WITH_TSC

    90 static PyObject * call_function(PyObject ***, int, uint64*, uint64*);

    91 #else

    92 static PyObject * call_function(PyObject ***, int);

    93 #endif

    94 static PyObject * fast_function(PyObject *, PyObject ***, int, int, int);

    95 static PyObject * do_call(PyObject *, PyObject ***, int, int);

    96 static PyObject * ext_do_call(PyObject *, PyObject ***, int, int, int);

    97 static PyObject * update_keyword_args(PyObject *, int, PyObject ***,

    98 				      PyObject *);

    99 static PyObject * update_star_args(int, int, PyObject *, PyObject ***);

   100 static PyObject * load_args(PyObject ***, int);

   101 #define CALL_FLAG_VAR 1

   102 #define CALL_FLAG_KW 2

   103 

   104 #ifdef LLTRACE

   105 static int lltrace;

   106 static int prtrace(PyObject *, char *);

   107 #endif

   108 static int call_trace(Py_tracefunc, PyObject *, PyFrameObject *,

   109 		      int, PyObject *);

   110 static int call_trace_protected(Py_tracefunc, PyObject *,

   111 				 PyFrameObject *, int, PyObject *);

   112 static void call_exc_trace(Py_tracefunc, PyObject *, PyFrameObject *);

   113 static int maybe_call_line_trace(Py_tracefunc, PyObject *,

   114 				  PyFrameObject *, int *, int *, int *);

   115 

   116 static PyObject * apply_slice(PyObject *, PyObject *, PyObject *);

   117 static int assign_slice(PyObject *, PyObject *,

   118 			PyObject *, PyObject *);

   119 static PyObject * cmp_outcome(int, PyObject *, PyObject *);

   120 static PyObject * import_from(PyObject *, PyObject *);

   121 static int import_all_from(PyObject *, PyObject *);

   122 static PyObject * build_class(PyObject *, PyObject *, PyObject *);

   123 static int exec_statement(PyFrameObject *,

   124 			  PyObject *, PyObject *, PyObject *);

   125 static void set_exc_info(PyThreadState *, PyObject *, PyObject *, PyObject *);

   126 static void reset_exc_info(PyThreadState *);

   127 static void format_exc_check_arg(PyObject *, char *, PyObject *);

   128 static PyObject * string_concatenate(PyObject *, PyObject *,

   129 				    PyFrameObject *, unsigned char *);

   130 

   131 #define NAME_ERROR_MSG \

   132 	"name '%.200s' is not defined"

   133 #define GLOBAL_NAME_ERROR_MSG \

   134 	"global name '%.200s' is not defined"

   135 #define UNBOUNDLOCAL_ERROR_MSG \

   136 	"local variable '%.200s' referenced before assignment"

   137 #define UNBOUNDFREE_ERROR_MSG \

   138 	"free variable '%.200s' referenced before assignment" \

   139         " in enclosing scope"

   140 

   141 /* Dynamic execution profile */

   142 #ifdef DYNAMIC_EXECUTION_PROFILE

   143 #ifdef DXPAIRS

   144 static long dxpairs[257][256];

   145 #define dxp dxpairs[256]

   146 #else

   147 static long dxp[256];

   148 #endif

   149 #endif

   150 

   151 /* Function call profile */

   152 #ifdef CALL_PROFILE

   153 #define PCALL_NUM 11

   154 static int pcall[PCALL_NUM];

   155 

   156 #define PCALL_ALL 0

   157 #define PCALL_FUNCTION 1

   158 #define PCALL_FAST_FUNCTION 2

   159 #define PCALL_FASTER_FUNCTION 3

   160 #define PCALL_METHOD 4

   161 #define PCALL_BOUND_METHOD 5

   162 #define PCALL_CFUNCTION 6

   163 #define PCALL_TYPE 7

   164 #define PCALL_GENERATOR 8

   165 #define PCALL_OTHER 9

   166 #define PCALL_POP 10

   167 

   168 /* Notes about the statistics

   169 

   170    PCALL_FAST stats

   171 

   172    FAST_FUNCTION means no argument tuple needs to be created.

   173    FASTER_FUNCTION means that the fast-path frame setup code is used.

   174 

   175    If there is a method call where the call can be optimized by changing

   176    the argument tuple and calling the function directly, it gets recorded

   177    twice.

   178 

   179    As a result, the relationship among the statistics appears to be

   180    PCALL_ALL == PCALL_FUNCTION + PCALL_METHOD - PCALL_BOUND_METHOD +

   181                 PCALL_CFUNCTION + PCALL_TYPE + PCALL_GENERATOR + PCALL_OTHER

   182    PCALL_FUNCTION > PCALL_FAST_FUNCTION > PCALL_FASTER_FUNCTION

   183    PCALL_METHOD > PCALL_BOUND_METHOD

   184 */

   185 

   186 #define PCALL(POS) pcall[POS]++

   187 

   188 PyObject *

   189 PyEval_GetCallStats(PyObject *self)

   190 {

   191 	return Py_BuildValue("iiiiiiiiiii",

   192 			     pcall[0], pcall[1], pcall[2], pcall[3],

   193 			     pcall[4], pcall[5], pcall[6], pcall[7],

   194 			     pcall[8], pcall[9], pcall[10]);

   195 }

   196 #else

   197 #define PCALL(O)

   198 

   199 PyObject *

   200 PyEval_GetCallStats(PyObject *self)

   201 {

   202 	Py_INCREF(Py_None);

   203 	return Py_None;

   204 }

   205 #endif

   206 

   207 

   208 #ifdef WITH_THREAD

   209 

   210 #ifdef HAVE_ERRNO_H

   211 #include <errno.h>

   212 #endif

   213 #include "pythread.h"

   214 

   215 static PyThread_type_lock interpreter_lock = 0; /* This is the GIL */

   216 static long main_thread = 0;

   217 

   218 int

   219 PyEval_ThreadsInitialized(void)

   220 {

   221 	return interpreter_lock != 0;

   222 }

   223 

   224 void

   225 PyEval_InitThreads(void)

   226 {

   227 	if (interpreter_lock)

   228 		return;

   229 	interpreter_lock = PyThread_allocate_lock();

   230 	PyThread_acquire_lock(interpreter_lock, 1);

   231 	main_thread = PyThread_get_thread_ident();

   232 }

   233 

   234 void

   235 PyEval_AcquireLock(void)

   236 {

   237 	PyThread_acquire_lock(interpreter_lock, 1);

   238 }

   239 

   240 void

   241 PyEval_ReleaseLock(void)

   242 {

   243 	PyThread_release_lock(interpreter_lock);

   244 }

   245 

   246 void

   247 PyEval_AcquireThread(PyThreadState *tstate)

   248 {

   249 	if (tstate == NULL)

   250 		Py_FatalError("PyEval_AcquireThread: NULL new thread state");

   251 	/* Check someone has called PyEval_InitThreads() to create the lock */

   252 	assert(interpreter_lock);

   253 	PyThread_acquire_lock(interpreter_lock, 1);

   254 	if (PyThreadState_Swap(tstate) != NULL)

   255 		Py_FatalError(

   256 			"PyEval_AcquireThread: non-NULL old thread state");

   257 }

   258 

   259 void

   260 PyEval_ReleaseThread(PyThreadState *tstate)

   261 {

   262 	if (tstate == NULL)

   263 		Py_FatalError("PyEval_ReleaseThread: NULL thread state");

   264 	if (PyThreadState_Swap(NULL) != tstate)

   265 		Py_FatalError("PyEval_ReleaseThread: wrong thread state");

   266 	PyThread_release_lock(interpreter_lock);

   267 }

   268 

   269 /* This function is called from PyOS_AfterFork to ensure that newly

   270    created child processes don't hold locks referring to threads which

   271    are not running in the child process.  (This could also be done using

   272    pthread_atfork mechanism, at least for the pthreads implementation.) */

   273 

   274 void

   275 PyEval_ReInitThreads(void)

   276 {

   277 	PyObject *threading, *result;

   278 	PyThreadState *tstate;

   279 

   280 	if (!interpreter_lock)

   281 		return;

   282 	/*XXX Can't use PyThread_free_lock here because it does too

   283 	  much error-checking.  Doing this cleanly would require

   284 	  adding a new function to each thread_*.h.  Instead, just

   285 	  create a new lock and waste a little bit of memory */

   286 	interpreter_lock = PyThread_allocate_lock();

   287 	PyThread_acquire_lock(interpreter_lock, 1);

   288 	main_thread = PyThread_get_thread_ident();

   289 

   290 	/* Update the threading module with the new state.

   291 	 */

   292 	tstate = PyThreadState_GET();

   293 	threading = PyMapping_GetItemString(tstate->interp->modules,

   294 					    "threading");

   295 	if (threading == NULL) {

   296 		/* threading not imported */

   297 		PyErr_Clear();

   298 		return;

   299 	}

   300 	result = PyObject_CallMethod(threading, "_after_fork", NULL);

   301 	if (result == NULL)

   302 		PyErr_WriteUnraisable(threading);

   303 	else

   304 		Py_DECREF(result);

   305 	Py_DECREF(threading);

   306 }

   307 #endif

   308 

   309 /* Functions save_thread and restore_thread are always defined so

   310    dynamically loaded modules needn't be compiled separately for use

   311    with and without threads: */

   312 

   313 PyThreadState *

   314 PyEval_SaveThread(void)

   315 {

   316 	PyThreadState *tstate = PyThreadState_Swap(NULL);

   317 	if (tstate == NULL)

   318 		Py_FatalError("PyEval_SaveThread: NULL tstate");

   319 #ifdef WITH_THREAD

   320 	if (interpreter_lock)

   321 		PyThread_release_lock(interpreter_lock);

   322 #endif

   323 	return tstate;

   324 }

   325 

   326 void

   327 PyEval_RestoreThread(PyThreadState *tstate)

   328 {

   329 	if (tstate == NULL)

   330 		Py_FatalError("PyEval_RestoreThread: NULL tstate");

   331 #ifdef WITH_THREAD

   332 	if (interpreter_lock) {

   333 		int err = errno;

   334 		PyThread_acquire_lock(interpreter_lock, 1);

   335 		errno = err;

   336 	}

   337 #endif

   338 	PyThreadState_Swap(tstate);

   339 }

   340 

   341 

   342 /* Mechanism whereby asynchronously executing callbacks (e.g. UNIX

   343    signal handlers or Mac I/O completion routines) can schedule calls

   344    to a function to be called synchronously.

   345    The synchronous function is called with one void* argument.

   346    It should return 0 for success or -1 for failure -- failure should

   347    be accompanied by an exception.

   348 

   349    If registry succeeds, the registry function returns 0; if it fails

   350    (e.g. due to too many pending calls) it returns -1 (without setting

   351    an exception condition).

   352 

   353    Note that because registry may occur from within signal handlers,

   354    or other asynchronous events, calling malloc() is unsafe!

   355 

   356 #ifdef WITH_THREAD

   357    Any thread can schedule pending calls, but only the main thread

   358    will execute them.

   359 #endif

   360 

   361    XXX WARNING!  ASYNCHRONOUSLY EXECUTING CODE!

   362    There are two possible race conditions:

   363    (1) nested asynchronous registry calls;

   364    (2) registry calls made while pending calls are being processed.

   365    While (1) is very unlikely, (2) is a real possibility.

   366    The current code is safe against (2), but not against (1).

   367    The safety against (2) is derived from the fact that only one

   368    thread (the main thread) ever takes things out of the queue.

   369 

   370    XXX Darn!  With the advent of thread state, we should have an array

   371    of pending calls per thread in the thread state!  Later...

   372 */

   373 

   374 #define NPENDINGCALLS 32

   375 static struct {

   376 	int (*func)(void *);

   377 	void *arg;

   378 } pendingcalls[NPENDINGCALLS];

   379 static volatile int pendingfirst = 0;

   380 static volatile int pendinglast = 0;

   381 static volatile int things_to_do = 0;

   382 

   383 int

   384 Py_AddPendingCall(int (*func)(void *), void *arg)

   385 {

   386 	static volatile int busy = 0;

   387 	int i, j;

   388 	/* XXX Begin critical section */

   389 	/* XXX If you want this to be safe against nested

   390 	   XXX asynchronous calls, you'll have to work harder! */

   391 	if (busy)

   392 		return -1;

   393 	busy = 1;

   394 	i = pendinglast;

   395 	j = (i + 1) % NPENDINGCALLS;

   396 	if (j == pendingfirst) {

   397 		busy = 0;

   398 		return -1; /* Queue full */

   399 	}

   400 	pendingcalls[i].func = func;

   401 	pendingcalls[i].arg = arg;

   402 	pendinglast = j;

   403 

   404 	_Py_Ticker = 0;

   405 	things_to_do = 1; /* Signal main loop */

   406 	busy = 0;

   407 	/* XXX End critical section */

   408 	return 0;

   409 }

   410 

   411 int

   412 Py_MakePendingCalls(void)

   413 {

   414 	static int busy = 0;

   415 #ifdef WITH_THREAD

   416 	if (main_thread && PyThread_get_thread_ident() != main_thread)

   417 		return 0;

   418 #endif

   419 	if (busy)

   420 		return 0;

   421 	busy = 1;

   422 	things_to_do = 0;

   423 	for (;;) {

   424 		int i;

   425 		int (*func)(void *);

   426 		void *arg;

   427 		i = pendingfirst;

   428 		if (i == pendinglast)

   429 			break; /* Queue empty */

   430 		func = pendingcalls[i].func;

   431 		arg = pendingcalls[i].arg;

   432 		pendingfirst = (i + 1) % NPENDINGCALLS;

   433 		if (func(arg) < 0) {

   434 			busy = 0;

   435 			things_to_do = 1; /* We're not done yet */

   436 			return -1;

   437 		}

   438 	}

   439 	busy = 0;

   440 	return 0;

   441 }

   442 

   443 

   444 /* The interpreter's recursion limit */

   445 

   446 #ifndef Py_DEFAULT_RECURSION_LIMIT

   447 #define Py_DEFAULT_RECURSION_LIMIT 1000

   448 #endif

   449 static int recursion_limit = Py_DEFAULT_RECURSION_LIMIT;

   450 int _Py_CheckRecursionLimit = Py_DEFAULT_RECURSION_LIMIT;

   451 

   452 int

   453 Py_GetRecursionLimit(void)

   454 {

   455 	return recursion_limit;

   456 }

   457 

   458 void

   459 Py_SetRecursionLimit(int new_limit)

   460 {

   461 	recursion_limit = new_limit;

   462 	_Py_CheckRecursionLimit = recursion_limit;

   463 }

   464 

   465 /* the macro Py_EnterRecursiveCall() only calls _Py_CheckRecursiveCall()

   466    if the recursion_depth reaches _Py_CheckRecursionLimit.

   467    If USE_STACKCHECK, the macro decrements _Py_CheckRecursionLimit

   468    to guarantee that _Py_CheckRecursiveCall() is regularly called.

   469    Without USE_STACKCHECK, there is no need for this. */

   470 int

   471 _Py_CheckRecursiveCall(char *where)

   472 {

   473 	PyThreadState *tstate = PyThreadState_GET();

   474 

   475 #ifdef USE_STACKCHECK

   476 	if (PyOS_CheckStack()) {

   477 		--tstate->recursion_depth;

   478 		PyErr_SetString(PyExc_MemoryError, "Stack overflow");

   479 		return -1;

   480 	}

   481 #endif

   482 	if (tstate->recursion_depth > recursion_limit) {

   483 		--tstate->recursion_depth;

   484 		PyErr_Format(PyExc_RuntimeError,

   485 			     "maximum recursion depth exceeded%s",

   486 			     where);

   487 		return -1;

   488 	}

   489 	_Py_CheckRecursionLimit = recursion_limit;

   490 	return 0;

   491 }

   492 

   493 /* Status code for main loop (reason for stack unwind) */

   494 enum why_code {

   495 		WHY_NOT =	0x0001,	/* No error */

   496 		WHY_EXCEPTION = 0x0002,	/* Exception occurred */

   497 		WHY_RERAISE =	0x0004,	/* Exception re-raised by 'finally' */

   498 		WHY_RETURN =	0x0008,	/* 'return' statement */

   499 		WHY_BREAK =	0x0010,	/* 'break' statement */

   500 		WHY_CONTINUE =	0x0020,	/* 'continue' statement */

   501 		WHY_YIELD =	0x0040	/* 'yield' operator */

   502 };

   503 

   504 static enum why_code do_raise(PyObject *, PyObject *, PyObject *);

   505 static int unpack_iterable(PyObject *, int, PyObject **);

   506 

   507 /* for manipulating the thread switch and periodic "stuff" - used to be

   508    per thread, now just a pair o' globals */

   509 int _Py_CheckInterval = 100;

   510 volatile int _Py_Ticker = 100;

   511 

   512 PyObject *

   513 PyEval_EvalCode(PyCodeObject *co, PyObject *globals, PyObject *locals)

   514 {

   515 	return PyEval_EvalCodeEx(co,

   516 			  globals, locals,

   517 			  (PyObject **)NULL, 0,

   518 			  (PyObject **)NULL, 0,

   519 			  (PyObject **)NULL, 0,

   520 			  NULL);

   521 }

   522 

   523 

   524 /* Interpreter main loop */

   525 

   526 PyObject *

   527 PyEval_EvalFrame(PyFrameObject *f) {

   528 	/* This is for backward compatibility with extension modules that

   529            used this API; core interpreter code should call

   530            PyEval_EvalFrameEx() */

   531 	return PyEval_EvalFrameEx(f, 0);

   532 }

   533 

   534 PyObject *

   535 PyEval_EvalFrameEx(PyFrameObject *f, int throwflag)

   536 {

   537 #ifdef DXPAIRS

   538 	int lastopcode = 0;

   539 #endif

   540 	register PyObject **stack_pointer;  /* Next free slot in value stack */

   541 	register unsigned char *next_instr;

   542 	register int opcode;	/* Current opcode */

   543 	register int oparg;	/* Current opcode argument, if any */

   544 	register enum why_code why; /* Reason for block stack unwind */

   545 	register int err;	/* Error status -- nonzero if error */

   546 	register PyObject *x;	/* Result object -- NULL if error */

   547 	register PyObject *v;	/* Temporary objects popped off stack */

   548 	register PyObject *w;

   549 	register PyObject *u;

   550 	register PyObject *t;

   551 	register PyObject *stream = NULL;    /* for PRINT opcodes */

   552 	register PyObject **fastlocals, **freevars;

   553 	PyObject *retval = NULL;	/* Return value */

   554 	PyThreadState *tstate = PyThreadState_GET();

   555 	PyCodeObject *co;

   556 

   557 	/* when tracing we set things up so that

   558 

   559                not (instr_lb <= current_bytecode_offset < instr_ub)

   560 

   561 	   is true when the line being executed has changed.  The

   562            initial values are such as to make this false the first

   563            time it is tested. */

   564 	int instr_ub = -1, instr_lb = 0, instr_prev = -1;

   565 

   566 	unsigned char *first_instr;

   567 	PyObject *names;

   568 	PyObject *consts;

   569 #if defined(Py_DEBUG) || defined(LLTRACE)

   570 	/* Make it easier to find out where we are with a debugger */

   571 	char *filename;

   572 #endif

   573 

   574 /* Tuple access macros */

   575 

   576 #ifndef Py_DEBUG

   577 #define GETITEM(v, i) PyTuple_GET_ITEM((PyTupleObject *)(v), (i))

   578 #else

   579 #define GETITEM(v, i) PyTuple_GetItem((v), (i))

   580 #endif

   581 

   582 #ifdef WITH_TSC

   583 /* Use Pentium timestamp counter to mark certain events:

   584    inst0 -- beginning of switch statement for opcode dispatch

   585    inst1 -- end of switch statement (may be skipped)

   586    loop0 -- the top of the mainloop

   587    loop1 -- place where control returns again to top of mainloop

   588             (may be skipped)

   589    intr1 -- beginning of long interruption

   590    intr2 -- end of long interruption

   591 

   592    Many opcodes call out to helper C functions.  In some cases, the

   593    time in those functions should be counted towards the time for the

   594    opcode, but not in all cases.  For example, a CALL_FUNCTION opcode

   595    calls another Python function; there's no point in charge all the

   596    bytecode executed by the called function to the caller.

   597 

   598    It's hard to make a useful judgement statically.  In the presence

   599    of operator overloading, it's impossible to tell if a call will

   600    execute new Python code or not.

   601 

   602    It's a case-by-case judgement.  I'll use intr1 for the following

   603    cases:

   604 

   605    EXEC_STMT

   606    IMPORT_STAR

   607    IMPORT_FROM

   608    CALL_FUNCTION (and friends)

   609 

   610  */

   611 	uint64 inst0, inst1, loop0, loop1, intr0 = 0, intr1 = 0;

   612 	int ticked = 0;

   613 

   614 	READ_TIMESTAMP(inst0);

   615 	READ_TIMESTAMP(inst1);

   616 	READ_TIMESTAMP(loop0);

   617 	READ_TIMESTAMP(loop1);

   618 

   619 	/* shut up the compiler */

   620 	opcode = 0;

   621 #endif

   622 

   623 /* Code access macros */

   624 

   625 #define INSTR_OFFSET()	((int)(next_instr - first_instr))

   626 #define NEXTOP()	(*next_instr++)

   627 #define NEXTARG()	(next_instr += 2, (next_instr[-1]<<8) + next_instr[-2])

   628 #define PEEKARG()	((next_instr[2]<<8) + next_instr[1])

   629 #define JUMPTO(x)	(next_instr = first_instr + (x))

   630 #define JUMPBY(x)	(next_instr += (x))

   631 

   632 /* OpCode prediction macros

   633 	Some opcodes tend to come in pairs thus making it possible to

   634 	predict the second code when the first is run.  For example,

   635 	COMPARE_OP is often followed by JUMP_IF_FALSE or JUMP_IF_TRUE.  And,

   636 	those opcodes are often followed by a POP_TOP.

   637 

   638 	Verifying the prediction costs a single high-speed test of a register

   639 	variable against a constant.  If the pairing was good, then the

   640 	processor's own internal branch predication has a high likelihood of

   641 	success, resulting in a nearly zero-overhead transition to the

   642 	next opcode.  A successful prediction saves a trip through the eval-loop

   643 	including its two unpredictable branches, the HAS_ARG test and the

   644 	switch-case.  Combined with the processor's internal branch prediction,

   645 	a successful PREDICT has the effect of making the two opcodes run as if

   646 	they were a single new opcode with the bodies combined.

   647 

   648     If collecting opcode statistics, your choices are to either keep the

   649 	predictions turned-on and interpret the results as if some opcodes

   650 	had been combined or turn-off predictions so that the opcode frequency

   651 	counter updates for both opcodes.

   652 */

   653 

   654 #ifdef DYNAMIC_EXECUTION_PROFILE

   655 #define PREDICT(op)		if (0) goto PRED_##op

   656 #else

   657 #define PREDICT(op)		if (*next_instr == op) goto PRED_##op

   658 #endif

   659 

   660 #define PREDICTED(op)		PRED_##op: next_instr++

   661 #define PREDICTED_WITH_ARG(op)	PRED_##op: oparg = PEEKARG(); next_instr += 3

   662 

   663 /* Stack manipulation macros */

   664 

   665 /* The stack can grow at most MAXINT deep, as co_nlocals and

   666    co_stacksize are ints. */

   667 #define STACK_LEVEL()	((int)(stack_pointer - f->f_valuestack))

   668 #define EMPTY()		(STACK_LEVEL() == 0)

   669 #define TOP()		(stack_pointer[-1])

   670 #define SECOND()	(stack_pointer[-2])

   671 #define THIRD() 	(stack_pointer[-3])

   672 #define FOURTH()	(stack_pointer[-4])

   673 #define SET_TOP(v)	(stack_pointer[-1] = (v))

   674 #define SET_SECOND(v)	(stack_pointer[-2] = (v))

   675 #define SET_THIRD(v)	(stack_pointer[-3] = (v))

   676 #define SET_FOURTH(v)	(stack_pointer[-4] = (v))

   677 #define BASIC_STACKADJ(n)	(stack_pointer += n)

   678 #define BASIC_PUSH(v)	(*stack_pointer++ = (v))

   679 #define BASIC_POP()	(*--stack_pointer)

   680 

   681 #ifdef LLTRACE

   682 #define PUSH(v)		{ (void)(BASIC_PUSH(v), \

   683                                lltrace && prtrace(TOP(), "push")); \

   684                                assert(STACK_LEVEL() <= co->co_stacksize); }

   685 #define POP()		((void)(lltrace && prtrace(TOP(), "pop")), \

   686 			 BASIC_POP())

   687 #define STACKADJ(n)	{ (void)(BASIC_STACKADJ(n), \

   688                                lltrace && prtrace(TOP(), "stackadj")); \

   689                                assert(STACK_LEVEL() <= co->co_stacksize); }

   690 #define EXT_POP(STACK_POINTER) ((void)(lltrace && \

   691 				prtrace((STACK_POINTER)[-1], "ext_pop")), \

   692 				*--(STACK_POINTER))

   693 #else

   694 #define PUSH(v)		BASIC_PUSH(v)

   695 #define POP()		BASIC_POP()

   696 #define STACKADJ(n)	BASIC_STACKADJ(n)

   697 #define EXT_POP(STACK_POINTER) (*--(STACK_POINTER))

   698 #endif

   699 

   700 /* Local variable macros */

   701 

   702 #define GETLOCAL(i)	(fastlocals[i])

   703 

   704 /* The SETLOCAL() macro must not DECREF the local variable in-place and

   705    then store the new value; it must copy the old value to a temporary

   706    value, then store the new value, and then DECREF the temporary value.

   707    This is because it is possible that during the DECREF the frame is

   708    accessed by other code (e.g. a __del__ method or gc.collect()) and the

   709    variable would be pointing to already-freed memory. */

   710 #define SETLOCAL(i, value)	do { PyObject *tmp = GETLOCAL(i); \

   711 				     GETLOCAL(i) = value; \

   712                                      Py_XDECREF(tmp); } while (0)

   713 

   714 /* Start of code */

   715 

   716 	if (f == NULL)

   717 		return NULL;

   718 

   719 	/* push frame */

   720 	if (Py_EnterRecursiveCall(""))

   721 		return NULL;

   722 

   723 	tstate->frame = f;

   724 

   725 	if (tstate->use_tracing) {

   726 		if (tstate->c_tracefunc != NULL) {

   727 			/* tstate->c_tracefunc, if defined, is a

   728 			   function that will be called on *every* entry

   729 			   to a code block.  Its return value, if not

   730 			   None, is a function that will be called at

   731 			   the start of each executed line of code.

   732 			   (Actually, the function must return itself

   733 			   in order to continue tracing.)  The trace

   734 			   functions are called with three arguments:

   735 			   a pointer to the current frame, a string

   736 			   indicating why the function is called, and

   737 			   an argument which depends on the situation.

   738 			   The global trace function is also called

   739 			   whenever an exception is detected. */

   740 			if (call_trace_protected(tstate->c_tracefunc,

   741 						 tstate->c_traceobj,

   742 						 f, PyTrace_CALL, Py_None)) {

   743 				/* Trace function raised an error */

   744 				goto exit_eval_frame;

   745 			}

   746 		}

   747 		if (tstate->c_profilefunc != NULL) {

   748 			/* Similar for c_profilefunc, except it needn't

   749 			   return itself and isn't called for "line" events */

   750 			if (call_trace_protected(tstate->c_profilefunc,

   751 						 tstate->c_profileobj,

   752 						 f, PyTrace_CALL, Py_None)) {

   753 				/* Profile function raised an error */

   754 				goto exit_eval_frame;

   755 			}

   756 		}

   757 	}

   758 

   759 	co = f->f_code;

   760 	names = co->co_names;

   761 	consts = co->co_consts;

   762 	fastlocals = f->f_localsplus;

   763 	freevars = f->f_localsplus + co->co_nlocals;

   764 	first_instr = (unsigned char*) PyString_AS_STRING(co->co_code);

   765 	/* An explanation is in order for the next line.

   766 

   767 	   f->f_lasti now refers to the index of the last instruction

   768 	   executed.  You might think this was obvious from the name, but

   769 	   this wasn't always true before 2.3!  PyFrame_New now sets

   770 	   f->f_lasti to -1 (i.e. the index *before* the first instruction)

   771 	   and YIELD_VALUE doesn't fiddle with f_lasti any more.  So this

   772 	   does work.  Promise.

   773 

   774 	   When the PREDICT() macros are enabled, some opcode pairs follow in

   775            direct succession without updating f->f_lasti.  A successful

   776            prediction effectively links the two codes together as if they

   777            were a single new opcode; accordingly,f->f_lasti will point to

   778            the first code in the pair (for instance, GET_ITER followed by

   779            FOR_ITER is effectively a single opcode and f->f_lasti will point

   780            at to the beginning of the combined pair.)

   781 	*/

   782 	next_instr = first_instr + f->f_lasti + 1;

   783 	stack_pointer = f->f_stacktop;

   784 	assert(stack_pointer != NULL);

   785 	f->f_stacktop = NULL;	/* remains NULL unless yield suspends frame */

   786 

   787 #ifdef LLTRACE

   788 	lltrace = PyDict_GetItemString(f->f_globals, "__lltrace__") != NULL;

   789 #endif

   790 #if defined(Py_DEBUG) || defined(LLTRACE)

   791 	filename = PyString_AsString(co->co_filename);

   792 #endif

   793 

   794 	why = WHY_NOT;

   795 	err = 0;

   796 	x = Py_None;	/* Not a reference, just anything non-NULL */

   797 	w = NULL;

   798 

   799 	if (throwflag) { /* support for generator.throw() */

   800 		why = WHY_EXCEPTION;

   801 		goto on_error;

   802 	}

   803 

   804 	for (;;) {

   805 #ifdef WITH_TSC

   806 		if (inst1 == 0) {

   807 			/* Almost surely, the opcode executed a break

   808 			   or a continue, preventing inst1 from being set

   809 			   on the way out of the loop.

   810 			*/

   811 			READ_TIMESTAMP(inst1);

   812 			loop1 = inst1;

   813 		}

   814 		dump_tsc(opcode, ticked, inst0, inst1, loop0, loop1,

   815 			 intr0, intr1);

   816 		ticked = 0;

   817 		inst1 = 0;

   818 		intr0 = 0;

   819 		intr1 = 0;

   820 		READ_TIMESTAMP(loop0);

   821 #endif

   822 		assert(stack_pointer >= f->f_valuestack); /* else underflow */

   823 		assert(STACK_LEVEL() <= co->co_stacksize);  /* else overflow */

   824 

   825 		/* Do periodic things.  Doing this every time through

   826 		   the loop would add too much overhead, so we do it

   827 		   only every Nth instruction.  We also do it if

   828 		   ``things_to_do'' is set, i.e. when an asynchronous

   829 		   event needs attention (e.g. a signal handler or

   830 		   async I/O handler); see Py_AddPendingCall() and

   831 		   Py_MakePendingCalls() above. */

   832 

   833 		if (--_Py_Ticker < 0) {

   834 			if (*next_instr == SETUP_FINALLY) {

   835 				/* Make the last opcode before

   836 				   a try: finally: block uninterruptable. */

   837 				goto fast_next_opcode;

   838 			}

   839 			_Py_Ticker = _Py_CheckInterval;

   840 			tstate->tick_counter++;

   841 #ifdef WITH_TSC

   842 			ticked = 1;

   843 #endif

   844 			if (things_to_do) {

   845 				if (Py_MakePendingCalls() < 0) {

   846 					why = WHY_EXCEPTION;

   847 					goto on_error;

   848 				}

   849 				if (things_to_do)

   850 					/* MakePendingCalls() didn't succeed.

   851 					   Force early re-execution of this

   852 					   "periodic" code, possibly after

   853 					   a thread switch */

   854 					_Py_Ticker = 0;

   855 			}

   856 #ifdef WITH_THREAD

   857 			if (interpreter_lock) {

   858 				/* Give another thread a chance */

   859 

   860 				if (PyThreadState_Swap(NULL) != tstate)

   861 					Py_FatalError("ceval: tstate mix-up");

   862 				PyThread_release_lock(interpreter_lock);

   863 

   864 				/* Other threads may run now */

   865 

   866 				PyThread_acquire_lock(interpreter_lock, 1);

   867 				if (PyThreadState_Swap(tstate) != NULL)

   868 					Py_FatalError("ceval: orphan tstate");

   869 

   870 				/* Check for thread interrupts */

   871 

   872 				if (tstate->async_exc != NULL) {

   873 					x = tstate->async_exc;

   874 					tstate->async_exc = NULL;

   875 					PyErr_SetNone(x);

   876 					Py_DECREF(x);

   877 					why = WHY_EXCEPTION;

   878 					goto on_error;

   879 				}

   880 			}

   881 #endif

   882 		}

   883 

   884 	fast_next_opcode:

   885 		f->f_lasti = INSTR_OFFSET();

   886 

   887 		/* line-by-line tracing support */

   888 

   889 		if (tstate->c_tracefunc != NULL && !tstate->tracing) {

   890 			/* see maybe_call_line_trace

   891 			   for expository comments */

   892 			f->f_stacktop = stack_pointer;

   893 

   894 			err = maybe_call_line_trace(tstate->c_tracefunc,

   895 						    tstate->c_traceobj,

   896 						    f, &instr_lb, &instr_ub,

   897 						    &instr_prev);

   898 			/* Reload possibly changed frame fields */

   899 			JUMPTO(f->f_lasti);

   900 			if (f->f_stacktop != NULL) {

   901 				stack_pointer = f->f_stacktop;

   902 				f->f_stacktop = NULL;

   903 			}

   904 			if (err) {

   905 				/* trace function raised an exception */

   906 				goto on_error;

   907 			}

   908 		}

   909 

   910 		/* Extract opcode and argument */

   911 

   912 		opcode = NEXTOP();

   913 		oparg = 0;   /* allows oparg to be stored in a register because

   914 			it doesn't have to be remembered across a full loop */

   915 		if (HAS_ARG(opcode))

   916 			oparg = NEXTARG();

   917 	  dispatch_opcode:

   918 #ifdef DYNAMIC_EXECUTION_PROFILE

   919 #ifdef DXPAIRS

   920 		dxpairs[lastopcode][opcode]++;

   921 		lastopcode = opcode;

   922 #endif

   923 		dxp[opcode]++;

   924 #endif

   925 

   926 #ifdef LLTRACE

   927 		/* Instruction tracing */

   928 

   929 		if (lltrace) {

   930 			if (HAS_ARG(opcode)) {

   931 				printf("%d: %d, %d\n",

   932 				       f->f_lasti, opcode, oparg);

   933 			}

   934 			else {

   935 				printf("%d: %d\n",

   936 				       f->f_lasti, opcode);

   937 			}

   938 		}

   939 #endif

   940 

   941 		/* Main switch on opcode */

   942 		READ_TIMESTAMP(inst0);

   943 

   944 		switch (opcode) {

   945 

   946 		/* BEWARE!

   947 		   It is essential that any operation that fails sets either

   948 		   x to NULL, err to nonzero, or why to anything but WHY_NOT,

   949 		   and that no operation that succeeds does this! */

   950 

   951 		/* case STOP_CODE: this is an error! */

   952 

   953 		case NOP:

   954 			goto fast_next_opcode;

   955 

   956 		case LOAD_FAST:

   957 			x = GETLOCAL(oparg);

   958 			if (x != NULL) {

   959 				Py_INCREF(x);

   960 				PUSH(x);

   961 				goto fast_next_opcode;

   962 			}

   963 			format_exc_check_arg(PyExc_UnboundLocalError,

   964 				UNBOUNDLOCAL_ERROR_MSG,

   965 				PyTuple_GetItem(co->co_varnames, oparg));

   966 			break;

   967 

   968 		case LOAD_CONST:

   969 			x = GETITEM(consts, oparg);

   970 			Py_INCREF(x);

   971 			PUSH(x);

   972 			goto fast_next_opcode;

   973 

   974 		PREDICTED_WITH_ARG(STORE_FAST);

   975 		case STORE_FAST:

   976 			v = POP();

   977 			SETLOCAL(oparg, v);

   978 			goto fast_next_opcode;

   979 

   980 		PREDICTED(POP_TOP);

   981 		case POP_TOP:

   982 			v = POP();

   983 			Py_DECREF(v);

   984 			goto fast_next_opcode;

   985 

   986 		case ROT_TWO:

   987 			v = TOP();

   988 			w = SECOND();

   989 			SET_TOP(w);

   990 			SET_SECOND(v);

   991 			goto fast_next_opcode;

   992 

   993 		case ROT_THREE:

   994 			v = TOP();

   995 			w = SECOND();

   996 			x = THIRD();

   997 			SET_TOP(w);

   998 			SET_SECOND(x);

   999 			SET_THIRD(v);

  1000 			goto fast_next_opcode;

  1001 

  1002 		case ROT_FOUR:

  1003 			u = TOP();

  1004 			v = SECOND();

  1005 			w = THIRD();

  1006 			x = FOURTH();

  1007 			SET_TOP(v);

  1008 			SET_SECOND(w);

  1009 			SET_THIRD(x);

  1010 			SET_FOURTH(u);

  1011 			goto fast_next_opcode;

  1012 

  1013 		case DUP_TOP:

  1014 			v = TOP();

  1015 			Py_INCREF(v);

  1016 			PUSH(v);

  1017 			goto fast_next_opcode;

  1018 

  1019 		case DUP_TOPX:

  1020 			if (oparg == 2) {

  1021 				x = TOP();

  1022 				Py_INCREF(x);

  1023 				w = SECOND();

  1024 				Py_INCREF(w);

  1025 				STACKADJ(2);

  1026 				SET_TOP(x);

  1027 				SET_SECOND(w);

  1028 				goto fast_next_opcode;

  1029 			} else if (oparg == 3) {

  1030 				x = TOP();

  1031 				Py_INCREF(x);

  1032 				w = SECOND();

  1033 				Py_INCREF(w);

  1034 				v = THIRD();

  1035 				Py_INCREF(v);

  1036 				STACKADJ(3);

  1037 				SET_TOP(x);

  1038 				SET_SECOND(w);

  1039 				SET_THIRD(v);

  1040 				goto fast_next_opcode;

  1041 			}

  1042 			Py_FatalError("invalid argument to DUP_TOPX"

  1043 				      " (bytecode corruption?)");

  1044 			break;

  1045 

  1046 		case UNARY_POSITIVE:

  1047 			v = TOP();

  1048 			x = PyNumber_Positive(v);

  1049 			Py_DECREF(v);

  1050 			SET_TOP(x);

  1051 			if (x != NULL) continue;

  1052 			break;

  1053 

  1054 		case UNARY_NEGATIVE:

  1055 			v = TOP();

  1056 			x = PyNumber_Negative(v);

  1057 			Py_DECREF(v);

  1058 			SET_TOP(x);

  1059 			if (x != NULL) continue;

  1060 			break;

  1061 

  1062 		case UNARY_NOT:

  1063 			v = TOP();

  1064 			err = PyObject_IsTrue(v);

  1065 			Py_DECREF(v);

  1066 			if (err == 0) {

  1067 				Py_INCREF(Py_True);

  1068 				SET_TOP(Py_True);

  1069 				continue;

  1070 			}

  1071 			else if (err > 0) {

  1072 				Py_INCREF(Py_False);

  1073 				SET_TOP(Py_False);

  1074 				err = 0;

  1075 				continue;

  1076 			}

  1077 			STACKADJ(-1);

  1078 			break;

  1079 

  1080 		case UNARY_CONVERT:

  1081 			v = TOP();

  1082 			x = PyObject_Repr(v);

  1083 			Py_DECREF(v);

  1084 			SET_TOP(x);

  1085 			if (x != NULL) continue;

  1086 			break;

  1087 

  1088 		case UNARY_INVERT:

  1089 			v = TOP();

  1090 			x = PyNumber_Invert(v);

  1091 			Py_DECREF(v);

  1092 			SET_TOP(x);

  1093 			if (x != NULL) continue;

  1094 			break;

  1095 

  1096 		case BINARY_POWER:

  1097 			w = POP();

  1098 			v = TOP();

  1099 			x = PyNumber_Power(v, w, Py_None);

  1100 			Py_DECREF(v);

  1101 			Py_DECREF(w);

  1102 			SET_TOP(x);

  1103 			if (x != NULL) continue;

  1104 			break;

  1105 

  1106 		case BINARY_MULTIPLY:

  1107 			w = POP();

  1108 			v = TOP();

  1109 			x = PyNumber_Multiply(v, w);

  1110 			Py_DECREF(v);

  1111 			Py_DECREF(w);

  1112 			SET_TOP(x);

  1113 			if (x != NULL) continue;

  1114 			break;

  1115 

  1116 		case BINARY_DIVIDE:

  1117 			if (!_Py_QnewFlag) {

  1118 				w = POP();

  1119 				v = TOP();

  1120 				x = PyNumber_Divide(v, w);

  1121 				Py_DECREF(v);

  1122 				Py_DECREF(w);

  1123 				SET_TOP(x);

  1124 				if (x != NULL) continue;

  1125 				break;

  1126 			}

  1127 			/* -Qnew is in effect:	fall through to

  1128 			   BINARY_TRUE_DIVIDE */

  1129 		case BINARY_TRUE_DIVIDE:

  1130 			w = POP();

  1131 			v = TOP();

  1132 			x = PyNumber_TrueDivide(v, w);

  1133 			Py_DECREF(v);

  1134 			Py_DECREF(w);

  1135 			SET_TOP(x);