implemented jump tables for single transitionsragel-6-barracuda

Generating jump tables for lists of singles that are longer than 4 items.
Results in a minor speedup in strings2 test case. Bettter than tables, but
still not close to G2 + O3 (1.6 speedup over asm). refs #15

2 files changed, 61 insertions, 4 deletions

diff --git a/ragel/asm.cpp b/ragel/asm.cpp
index d35dd6e0..a2737248 100644
--- a/ragel/asm.cpp
+++ b/ragel/asm.cpp
@@ -869,7 +869,7 @@ std::ostream &AsmCodeGen::ACTION_SWITCH()
 	return out;
 }
 
-void AsmCodeGen::emitSingleSwitch( RedStateAp *state )
+void AsmCodeGen::emitSingleIfElseIf( RedStateAp *state )
 {
 	/* Load up the singles. */
 	int numSingles = state->outSingle.length();
@@ -886,6 +886,54 @@ void AsmCodeGen::emitSingleSwitch( RedStateAp *state )
 	}
 }
 
+void AsmCodeGen::emitSingleJumpTable( RedStateAp *state, string def )
+{
+	static int l = 1;
+	int table = l++;
+	int failed = l++;
+	int numSingles = state->outSingle.length();
+	RedTransEl *data = state->outSingle.data;
+
+	long long low = data[0].lowKey.getVal();
+	long long high = data[numSingles-1].lowKey.getVal();
+
+	if ( def.size() == 0 ) {
+		std::stringstream s;
+		s << ".L_sjt_" << failed;
+		def = s.str();
+	}
+
+	out <<
+		"	cmpb	$" << low << ", %r14b\n"
+		"	jl	" << def << "\n"
+		"	cmpb	$" << high << ", %r14b\n"
+		"	jg	" << def << "\n"
+		"	movzbq	%r14b, %rax\n"
+		"	subq	$" << low << ", %rax\n"
+		"	jmp	*.L_sjt_" << table << "(,%rax,8)\n"
+		"	.section .rodata\n"
+		"	.align 8\n"
+		".L_sjt_" << table << ":\n";
+
+	for ( long long j = 0; j < numSingles; j++ ) {
+		/* Fill in gap between prev and this. */
+		if ( j > 0 ){
+			long long span = keyOps->span( data[j-1].lowKey, data[j].lowKey ) - 2;
+			for ( long long k = 0; k < span; k++ ) {
+				out <<
+					"	.quad	" << def << "\n";
+			}
+		}
+
+		out <<
+			"	.quad	" << TRANS_GOTO_TARG( data[j].value ) << "\n";
+	}
+
+	out <<
+		"	.text\n"
+		".L_sjt_" << failed << ":\n";
+}
+
 
 void AsmCodeGen::emitRangeBSearch( RedStateAp *state, int level, int low, int high )
 {
@@ -1223,8 +1271,16 @@ std::ostream &AsmCodeGen::STATE_GOTOS()
 				out << "	movb	(%r12), %r14b\n";
 
 			/* Try singles. */
-			if ( st->outSingle.length() > 0 )
-				emitSingleSwitch( st );
+			if ( st->outSingle.length() > 0 ) {
+				if ( st->outSingle.length() <= 4 )
+					emitSingleIfElseIf( st );
+				else {
+					string def;
+					if ( st->outRange.length() == 0 )
+						def = TRANS_GOTO_TARG( st->defTrans );
+					emitSingleJumpTable( st, def );
+				}
+			}
 
 			/* Default case is to binary search for the ranges, if that fails then */
 			if ( st->outRange.length() > 0 )
diff --git a/ragel/asm.h b/ragel/asm.h
index 7688e9af..51b925ca 100644
--- a/ragel/asm.h
+++ b/ragel/asm.h
@@ -231,7 +231,8 @@ public:
 	std::ostream &STATE_GOTOS();
 
 	void emitCondBSearch( RedStateAp *state, int level, int low, int high );
-	void emitSingleSwitch( RedStateAp *state );
+	void emitSingleIfElseIf( RedStateAp *state );
+	void emitSingleJumpTable( RedStateAp *state, std::string def );
 	void emitRangeBSearch( RedStateAp *state, int level, int low, int high );
 
 	/* Set up labelNeeded flag for each state. */