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

Python/compile.c

Index: Python/compile.c
===================================================================
--- Python/compile.c	(revision 70087)
+++ Python/compile.c	(working copy)
@@ -1605,12 +1605,12 @@
 	 * 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;
@@ -1620,8 +1620,8 @@
 		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);
 		}
@@ -1633,26 +1633,34 @@
 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);
@@ -1664,8 +1672,11 @@
 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)
@@ -1675,13 +1686,15 @@
 	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;
@@ -1690,18 +1703,27 @@
 		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);
+	}
+	else {
+		ADDOP_JABS(c, JUMP_ABSOLUTE, loop);
 	}
-	VISIT_SEQ(c, stmt, s->v.While.body);
-	ADDOP_JABS(c, JUMP_ABSOLUTE, loop);
 
 	/* XXX should the two POP instructions be in a separate block
 	   if there is no else clause ?
@@ -2604,24 +2626,23 @@
 	   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! */
@@ -2629,7 +2650,7 @@
 	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);
 	} 
 
@@ -2641,13 +2662,11 @@
 	if (gen_index >= asdl_seq_LEN(generators)) {
 	    VISIT(c, expr, elt);
 	    ADDOP_I(c, LIST_APPEND, gen_index+1);
-
-	    compiler_use_next_block(c, skip);
 	}
-	compiler_use_next_block(c, if_cleanup);
-	ADDOP_JABS(c, JUMP_ABSOLUTE, start);
+	compiler_use_next_block(c, tail);
+	ADDOP_JABS(c, FOR_ITER, body);
 	compiler_use_next_block(c, anchor);
-	
+
 	return 1;
 }
 
@@ -2669,17 +2688,15 @@
 	   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);
@@ -2698,8 +2715,8 @@
 		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! */
@@ -2707,7 +2724,7 @@
 	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);
 	}
 
@@ -2720,12 +2737,9 @@
 		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);
@@ -3495,12 +3509,11 @@
 
 /* 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
@@ -3515,14 +3528,17 @@
 
     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:
@@ -3535,28 +3551,33 @@
 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) {
@@ -3574,15 +3595,15 @@
 		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) {
@@ -3600,13 +3621,13 @@
 		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;
 	}
 
@@ -3621,11 +3642,11 @@
 	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;