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