http://bugs.python.org/issue2459 -- speed up loops

Python/compile.c

 /*
  * This file compiles an abstract syntax tree (AST) into Python bytecode.
  *
  * The primary entry point is PyAST_Compile(), which returns a
  * PyCodeObject.  The compiler makes several passes to build the code
  * object:
  *   1. Checks for future statements.  See future.c
  *   2. Builds a symbol table.  See symtable.c.
  *   3. Generate code for basic blocks.  See compiler_mod() in this file.
  *   4. Assemble the basic blocks into final code.  See assemble() in
@@ skipping 1587 matching lines @@
         assert(s->kind == If_kind);
         end = compiler_new_block(c);
         if (end == NULL)
                 return 0;
         
         constant = expr_constant(s->v.If.test);
         /* constant = 0: "if 0"
          * constant = 1: "if 1", "if 2", ...
          * constant = -1: rest */
         if (constant == 0) {
-                if (s->v.If.orelse)
+                if (asdl_seq_LEN(s->v.If.orelse))
                         VISIT_SEQ(c, stmt, s->v.If.orelse);
         } else if (constant == 1) {
                 VISIT_SEQ(c, stmt, s->v.If.body);
         } else {
-                if (s->v.If.orelse) {
+                if (asdl_seq_LEN(s->v.If.orelse)) {
                         next = compiler_new_block(c);
                         if (next == NULL)
                             return 0;
                 }
                 else
                         next = end;
                 VISIT(c, expr, s->v.If.test);
                 ADDOP_JABS(c, POP_JUMP_IF_FALSE, next);
                 VISIT_SEQ(c, stmt, s->v.If.body);
-                ADDOP_JREL(c, JUMP_FORWARD, end);
-                if (s->v.If.orelse) {
+                if (asdl_seq_LEN(s->v.If.orelse)) {
+                        ADDOP_JREL(c, JUMP_FORWARD, end);
                         compiler_use_next_block(c, next);
                         VISIT_SEQ(c, stmt, s->v.If.orelse);
                 }
         }
         compiler_use_next_block(c, end);
         return 1;
 }
 
 static int
 compiler_for(struct compiler *c, stmt_ty s)
 {
-        basicblock *start, *cleanup, *end;
+        basicblock *start, *body, *tail, *cleanup, *end;
+        int for_lineno;
 
         start = compiler_new_block(c);
+        body = compiler_new_block(c);
+        tail = compiler_new_block(c);
         cleanup = compiler_new_block(c);
         end = compiler_new_block(c);
-        if (start == NULL || end == NULL || cleanup == NULL)
+        if (start == NULL || body == NULL || tail == NULL
+                || end == NULL || cleanup == NULL)
                 return 0;
         ADDOP_JREL(c, SETUP_LOOP, end);
         if (!compiler_push_fblock(c, LOOP, start))
                 return 0;
         VISIT(c, expr, s->v.For.iter);
+        for_lineno = c->u->u_lineno;
         ADDOP(c, GET_ITER);
         compiler_use_next_block(c, start);
+        ADDOP_JREL(c, JUMP_FORWARD, tail);
+        compiler_use_next_block(c, body);
+        VISIT(c, expr, s->v.For.target);
+        VISIT_SEQ(c, stmt, s->v.For.body);
+        compiler_use_next_block(c, tail);
         /* for expressions must be traced on each iteration,
            so we need to set an extra line number. */
         c->u->u_lineno_set = false;
-        ADDOP_JREL(c, FOR_ITER, cleanup);
-        VISIT(c, expr, s->v.For.target);
-        VISIT_SEQ(c, stmt, s->v.For.body);
-        ADDOP_JABS(c, JUMP_ABSOLUTE, start);
+        c->u->u_lineno = for_lineno;
+        ADDOP_JABS(c, FOR_ITER, body);
         compiler_use_next_block(c, cleanup);
         ADDOP(c, POP_BLOCK);
         compiler_pop_fblock(c, LOOP, start);
         VISIT_SEQ(c, stmt, s->v.For.orelse);
         compiler_use_next_block(c, end);
         return 1;
 }
 
 static int
 compiler_while(struct compiler *c, stmt_ty s)
 {
-        basicblock *loop, *orelse, *end, *anchor = NULL;
+        basicblock *loop, *orelse, *end;
+        /* These are unused if the condition is optimized into a constant */
+        basicblock *body = NULL, *tail = NULL, *anchor = NULL;
         int constant = expr_constant(s->v.While.test);
+        int while_lineno;
 
         if (constant == 0) {
                 if (s->v.While.orelse)
                         VISIT_SEQ(c, stmt, s->v.While.orelse);
                 return 1;
         }
         loop = compiler_new_block(c);
         end = compiler_new_block(c);
         if (constant == -1) {
+                body = compiler_new_block(c);
+                tail = compiler_new_block(c);
                 anchor = compiler_new_block(c);
-                if (anchor == NULL)
+                if (body == NULL || tail == NULL || anchor == NULL)
                         return 0;
         }
         if (loop == NULL || end == NULL)
                 return 0;
-        if (s->v.While.orelse) {
+        if (asdl_seq_LEN(s->v.While.orelse)) {
                 orelse = compiler_new_block(c);
                 if (orelse == NULL)
                         return 0;
         }
         else
                 orelse = NULL;
 
         ADDOP_JREL(c, SETUP_LOOP, end);
+        while_lineno = c->u->u_lineno;
         compiler_use_next_block(c, loop);
         if (!compiler_push_fblock(c, LOOP, loop))
                 return 0;
         if (constant == -1) {
+                ADDOP_JREL(c, JUMP_FORWARD, tail);
+                compiler_use_next_block(c, body);
+        }
+        VISIT_SEQ(c, stmt, s->v.While.body);
+        if (constant == -1) {
+                compiler_use_next_block(c, tail);
                 /* while expressions must be traced on each iteration,
                    so we need to set an extra line number. */
                 c->u->u_lineno_set = false;
+                c->u->u_lineno = while_lineno;
                 VISIT(c, expr, s->v.While.test);
-                ADDOP_JABS(c, POP_JUMP_IF_FALSE, anchor);
+                ADDOP_JABS(c, POP_JUMP_IF_TRUE, body);
         }
-        VISIT_SEQ(c, stmt, s->v.While.body);
-        ADDOP_JABS(c, JUMP_ABSOLUTE, loop);
+        else {
+                ADDOP_JABS(c, JUMP_ABSOLUTE, loop);
+        }
 
         /* XXX should the two POP instructions be in a separate block
            if there is no else clause ?
         */
 
         if (constant == -1) {
                 compiler_use_next_block(c, anchor);
                 ADDOP(c, POP_BLOCK);
         }
         compiler_pop_fblock(c, LOOP, loop);
@@ skipping 882 matching lines @@
 }
 
 static int
 compiler_listcomp_generator(struct compiler *c, asdl_seq *generators,
                             int gen_index, expr_ty elt)
 {
         /* generate code for the iterator, then each of the ifs,
            and then write to the element */
 
         comprehension_ty l;
-        basicblock *start, *anchor, *skip, *if_cleanup;
+        basicblock *start, *body, *tail, *anchor;
         int i, n;
 
         start = compiler_new_block(c);
-        skip = compiler_new_block(c);
-        if_cleanup = compiler_new_block(c);
+        body = compiler_new_block(c);
+        tail = compiler_new_block(c);
         anchor = compiler_new_block(c);
 
-        if (start == NULL || skip == NULL || if_cleanup == NULL ||
-                anchor == NULL)
+        if (start == NULL || body == NULL || tail == NULL || anchor == NULL)
             return 0;
 
         l = (comprehension_ty)asdl_seq_GET(generators, gen_index);
         VISIT(c, expr, l->iter);
         ADDOP(c, GET_ITER);
         compiler_use_next_block(c, start);
-        ADDOP_JREL(c, FOR_ITER, anchor);
-        NEXT_BLOCK(c);
+        ADDOP_JREL(c, JUMP_FORWARD, tail);
+        compiler_use_next_block(c, body);
         VISIT(c, expr, l->target);
 
         /* XXX this needs to be cleaned up...a lot! */
         n = asdl_seq_LEN(l->ifs);
         for (i = 0; i < n; i++) {
                 expr_ty e = (expr_ty)asdl_seq_GET(l->ifs, i);
                 VISIT(c, expr, e);
-                ADDOP_JABS(c, POP_JUMP_IF_FALSE, if_cleanup);
+                ADDOP_JABS(c, POP_JUMP_IF_FALSE, tail);
                 NEXT_BLOCK(c);
         } 
 
         if (++gen_index < asdl_seq_LEN(generators))
             if (!compiler_listcomp_generator(c, generators, gen_index, elt))
                 return 0;
 
         /* only append after the last for generator */
         if (gen_index >= asdl_seq_LEN(generators)) {
             VISIT(c, expr, elt);
             ADDOP_I(c, LIST_APPEND, gen_index+1);
+        }
+        compiler_use_next_block(c, tail);
+        ADDOP_JABS(c, FOR_ITER, body);
+        compiler_use_next_block(c, anchor);
 
-            compiler_use_next_block(c, skip);
-        }
-        compiler_use_next_block(c, if_cleanup);
-        ADDOP_JABS(c, JUMP_ABSOLUTE, start);
-        compiler_use_next_block(c, anchor);
-        
         return 1;
 }
 
 static int
 compiler_listcomp(struct compiler *c, expr_ty e)
 {
         assert(e->kind == ListComp_kind);
         ADDOP_I(c, BUILD_LIST, 0);
         return compiler_listcomp_generator(c, e->v.ListComp.generators, 0,
                                            e->v.ListComp.elt);
 }
 
 static int
 compiler_genexp_generator(struct compiler *c,
                           asdl_seq *generators, int gen_index, 
                           expr_ty elt)
 {
         /* generate code for the iterator, then each of the ifs,
            and then write to the element */
 
         comprehension_ty ge;
-        basicblock *start, *anchor, *skip, *if_cleanup, *end;
+        basicblock *start, *body, *tail, *end;
         int i, n;
 
         start = compiler_new_block(c);
-        skip = compiler_new_block(c);
-        if_cleanup = compiler_new_block(c);
-        anchor = compiler_new_block(c);
+        body = compiler_new_block(c);
+        tail = compiler_new_block(c);
         end = compiler_new_block(c);
 
-        if (start == NULL || skip == NULL || if_cleanup == NULL ||
-            anchor == NULL || end == NULL)
+        if (start == NULL || body == NULL || tail == NULL || end == NULL)
                 return 0;
 
         ge = (comprehension_ty)asdl_seq_GET(generators, gen_index);
         ADDOP_JREL(c, SETUP_LOOP, end);
         if (!compiler_push_fblock(c, LOOP, start))
                 return 0;
 
         if (gen_index == 0) {
                 /* Receive outermost iter as an implicit argument */
                 c->u->u_argcount = 1;
                 ADDOP_I(c, LOAD_FAST, 0);
         }
         else {
                 /* Sub-iter - calculate on the fly */
                 VISIT(c, expr, ge->iter);
                 ADDOP(c, GET_ITER);
         }
         compiler_use_next_block(c, start);
-        ADDOP_JREL(c, FOR_ITER, anchor);
-        NEXT_BLOCK(c);
+        ADDOP_JREL(c, JUMP_FORWARD, tail);
+        compiler_use_next_block(c, body);
         VISIT(c, expr, ge->target);
 
         /* XXX this needs to be cleaned up...a lot! */
         n = asdl_seq_LEN(ge->ifs);
         for (i = 0; i < n; i++) {
                 expr_ty e = (expr_ty)asdl_seq_GET(ge->ifs, i);
                 VISIT(c, expr, e);
-                ADDOP_JABS(c, POP_JUMP_IF_FALSE, if_cleanup);
+                ADDOP_JABS(c, POP_JUMP_IF_FALSE, tail);
                 NEXT_BLOCK(c);
         }
 
         if (++gen_index < asdl_seq_LEN(generators))
                 if (!compiler_genexp_generator(c, generators, gen_index, elt))
                         return 0;
 
         /* only append after the last 'for' generator */
         if (gen_index >= asdl_seq_LEN(generators)) {
                 VISIT(c, expr, elt);
                 ADDOP(c, YIELD_VALUE);
                 ADDOP(c, POP_TOP);
-
-                compiler_use_next_block(c, skip);
         }
-        compiler_use_next_block(c, if_cleanup);
-        ADDOP_JABS(c, JUMP_ABSOLUTE, start);
-        compiler_use_next_block(c, anchor);
+        compiler_use_next_block(c, tail);
+        ADDOP_JABS(c, FOR_ITER, body);
         ADDOP(c, POP_BLOCK);
         compiler_pop_fblock(c, LOOP, start);
         compiler_use_next_block(c, end);
 
         return 1;
 }
 
 static int
 compiler_genexp(struct compiler *c, expr_ty e)
 {
@@ skipping 749 matching lines @@
         int i;
         int size = 0;
 
         for (i = 0; i < b->b_iused; i++)
                 size += instrsize(&b->b_instr[i]);
         return size;
 }
 
 /* All about a_lnotab.
 
-c_lnotab is an array of unsigned bytes disguised as a Python string.
-It is used to map bytecode offsets to source code line #s (when needed
-for tracebacks).
+c_lnotab is an array of bytes disguised as a Python string. It is used
+to map bytecode offsets to source code line #s (when needed for tracebacks).
 
 The array is conceptually a list of
-    (bytecode offset increment, line number increment)
+    (unsigned bytecode offset increment, signed line number increment)
 pairs.  The details are important and delicate, best illustrated by example:
 
     byte code offset    source code line number
         0                   1
         6                   2
        50                   7
       350                 307
       361                 308
 
 The first trick is that these numbers aren't stored, only the increments
 from one row to the next (this doesn't really work, but it's a start):
 
     0, 1,  6, 1,  44, 5,  300, 300,  11, 1
 
-The second trick is that an unsigned byte can't hold negative values, or
-values larger than 255, so (a) there's a deep assumption that byte code
-offsets and their corresponding line #s both increase monotonically, and (b)
-if at least one column jumps by more than 255 from one row to the next, more
-than one pair is written to the table. In case #b, there's no way to know
-from looking at the table later how many were written.  That's the delicate
-part.  A user of c_lnotab desiring to find the source line number
-corresponding to a bytecode address A should do something like this
+The second trick is that while bytecode offset increments are unsigned
+bytes (byte code offsets are assumed to increase monotonically), line
+number increments can be negative as well as positive (this is necessary
+to evaluate a loop's condition at the end of the loop, saving an
+unconditional jump). Thus, if either the bytecode increment jumps by more
+than 255, or the line number increment jumps by more than 127 or less than
+-127, more than one pair is written to the table. In this case there's no
+way to know from looking at the table later how many were written.  That's
+the delicate part. A user of c_lnotab desiring to find the source line
+number corresponding to a bytecode address A should do something like
+this:
 
     lineno = addr = 0
     for addr_incr, line_incr in c_lnotab:
         addr += addr_incr
         if addr > A:
             return lineno
         lineno += line_incr
 
 In order for this to work, when the addr field increments by more than 255,
 the line # increment in each pair generated must be 0 until the remaining addr
 increment is < 256.  So, in the example above, assemble_lnotab (it used
 to be called com_set_lineno) should not (as was actually done until 2.2)
-expand 300, 300 to 255, 255, 45, 45, 
-            but to 255,   0, 45, 255, 0, 45.
+expand 300, 300 to 255, 255, 45, 45,
+            but to 255,   0, 45, 127, 0, 127, 0, 46.
 */
+
+#define MAX_LINENO 127
+#define MAX_BYTECODE 255
 
 static int
 assemble_lnotab(struct assembler *a, struct instr *i)
 {
-        int d_bytecode, d_lineno;
+        int d_bytecode, d_lineno, d_abs_lineno, d_lineno_sign;
         int len;
         unsigned char *lnotab;
 
         d_bytecode = a->a_offset - a->a_lineno_off;
         d_lineno = i->i_lineno - a->a_lineno;
+        d_abs_lineno = abs(d_lineno);
+        d_lineno_sign = (d_lineno >= 0) ? 1 : -1;
 
         assert(d_bytecode >= 0);
-        assert(d_lineno >= 0);
+        assert(d_abs_lineno >= 0);
 
-        if(d_bytecode == 0 && d_lineno == 0)
+        if (d_bytecode == 0 && d_lineno == 0)
                 return 1;
 
-        if (d_bytecode > 255) {
-                int j, nbytes, ncodes = d_bytecode / 255;
+        if (d_bytecode > MAX_BYTECODE) {
+                int j, nbytes, ncodes = d_bytecode / MAX_BYTECODE;
                 nbytes = a->a_lnotab_off + 2 * ncodes;
                 len = PyString_GET_SIZE(a->a_lnotab);
                 if (nbytes >= len) {
                         if ((len <= INT_MAX / 2) && (len * 2 < nbytes))
                                 len = nbytes;
                         else if (len <= INT_MAX / 2)
                                 len *= 2;
                         else {
                                 PyErr_NoMemory();
                                 return 0;
                         }
                         if (_PyString_Resize(&a->a_lnotab, len) < 0)
                                 return 0;
                 }
                 lnotab = (unsigned char *)
                            PyString_AS_STRING(a->a_lnotab) + a->a_lnotab_off;
                 for (j = 0; j < ncodes; j++) {
-                        *lnotab++ = 255;
+                        *lnotab++ = MAX_BYTECODE;
                         *lnotab++ = 0;
                 }
-                d_bytecode -= ncodes * 255;
+                d_bytecode -= ncodes * MAX_BYTECODE;
                 a->a_lnotab_off += ncodes * 2;
         }
-        assert(d_bytecode <= 255);
-        if (d_lineno > 255) {
-                int j, nbytes, ncodes = d_lineno / 255;
+        assert(d_bytecode <= MAX_BYTECODE);
+        if (d_abs_lineno > MAX_LINENO) {
+                int j, nbytes, ncodes = d_abs_lineno / MAX_LINENO;
                 nbytes = a->a_lnotab_off + 2 * ncodes;
                 len = PyString_GET_SIZE(a->a_lnotab);
                 if (nbytes >= len) {
                         if ((len <= INT_MAX / 2) && len * 2 < nbytes)
                                 len = nbytes;
                         else if (len <= INT_MAX / 2)
                                 len *= 2;
                         else {
                                 PyErr_NoMemory();
                                 return 0;
                         }
                         if (_PyString_Resize(&a->a_lnotab, len) < 0)
                                 return 0;
                 }
                 lnotab = (unsigned char *)
                            PyString_AS_STRING(a->a_lnotab) + a->a_lnotab_off;
                 *lnotab++ = d_bytecode;
-                *lnotab++ = 255;
+                *lnotab++ = MAX_LINENO * d_lineno_sign;
                 d_bytecode = 0;
                 for (j = 1; j < ncodes; j++) {
                         *lnotab++ = 0;
-                        *lnotab++ = 255;
+                        *lnotab++ = MAX_LINENO * d_lineno_sign;
                 }
-                d_lineno -= ncodes * 255;
+                d_abs_lineno -= ncodes * MAX_LINENO;
                 a->a_lnotab_off += ncodes * 2;
         }
 
         len = PyString_GET_SIZE(a->a_lnotab);
         if (a->a_lnotab_off + 2 >= len) {
                 if (_PyString_Resize(&a->a_lnotab, len * 2) < 0)
                         return 0;
         }
         lnotab = (unsigned char *)
                         PyString_AS_STRING(a->a_lnotab) + a->a_lnotab_off;
 
         a->a_lnotab_off += 2;
         if (d_bytecode) {
                 *lnotab++ = d_bytecode;
-                *lnotab++ = d_lineno;
+                *lnotab++ = d_abs_lineno * d_lineno_sign;
         }
         else {  /* First line of a block; def stmt, etc. */
                 *lnotab++ = 0;
-                *lnotab++ = d_lineno;
+                *lnotab++ = d_abs_lineno * d_lineno_sign;
         }
         a->a_lineno = i->i_lineno;
         a->a_lineno_off = a->a_offset;
         return 1;
 }
 
 /* assemble_emit()
    Extend the bytecode with a new instruction.
    Update lnotab if necessary.
 */
@@ skipping 314 matching lines @@
         if (_PyString_Resize(&a.a_lnotab, a.a_lnotab_off) < 0)
                 goto error;
         if (_PyString_Resize(&a.a_bytecode, a.a_offset) < 0)
                 goto error;
 
         co = makecode(c, &a);
  error:
         assemble_free(&a);
         return co;
 }