optimize main state machine transitions with tail calls

* On newer GCC (>= 15) and Clang (>= 13) versions we can tail call
  at the end of input_cb() implementations to the next state's input_cb(),
  which will be optimized to jumps (often direct jumps).
  That is, the compilers always optimized tail calls, but we can
  guarantee tail calls with the __attribute__((musttail)) statement
  attribute.
* Every `return &teco_state_xxx` has to be replaced with
  `TECO_RETURN(ctx, &teco_state_xxx, error)`.
* This speeds up `-O2 -flto` builds by 18%
  (e.g. tested on grosciteco for sciteco(7)).
  Part of the speed up could also be because of inlining through
  TECO_RETURN().
* The other state machines (stringbuilding and q-reg spec) cannot
  currently be optimized the same way since they get their characters
  passed in from the "main" state machine.
* All loops around callbacks could be optimized the same way.
  E.g. the undo token runner could also tail call into the next runner,
  but it's probably not important to optimize undo token executions.

6 files changed, 130 insertions, 50 deletions

diff --git a/src/core-commands.c b/src/core-commands.c
index db3ae9d..8f84224 100644
--- a/src/core-commands.c
+++ b/src/core-commands.c
@@ -765,7 +765,7 @@ teco_state_start_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 			teco_error_modifier_set(error, cmd);
 			return NULL;
 		}
-		return &teco_state_start;
+		TECO_RETURN(ctx, &teco_state_start, error);
 	}
 
 	switch (chr) {
@@ -794,7 +794,7 @@ teco_state_start_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 		}
 		if (ctx->flags.mode == TECO_MODE_NORMAL)
 			teco_expressions_add_digit(chr, ctx->qreg_table_locals->radix);
-		return &teco_state_start;
+		TECO_RETURN(ctx, &teco_state_start, error);
 
 	case '*':
 		/*
@@ -806,7 +806,7 @@ teco_state_start_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 		 */
 		if (teco_cmdline_ssm(SCI_GETCURRENTPOS, 0, 0) == 1 &&
 		    teco_cmdline_ssm(SCI_GETCHARAT, 0, 0) == '*')
-			return &teco_state_save_cmdline;
+			TECO_RETURN(ctx, &teco_state_save_cmdline, error);
 		/* treat as an operator */
 		break;
 
@@ -821,7 +821,7 @@ teco_state_start_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 		if (ctx->parent.must_undo)
 			teco_undo_gint(ctx->nest_level);
 		ctx->nest_level++;
-		return &teco_state_start;
+		TECO_RETURN(ctx, &teco_state_start, error);
 
 	case '>':
 		if (ctx->flags.modifier_at) {
@@ -840,7 +840,7 @@ teco_state_start_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 				teco_undo_gint(ctx->nest_level);
 			ctx->nest_level--;
 		}
-		return &teco_state_start;
+		TECO_RETURN(ctx, &teco_state_start, error);
 
 	/*
 	 * Control Structures (conditionals)
@@ -858,9 +858,9 @@ teco_state_start_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 		else if (ctx->flags.mode == TECO_MODE_NORMAL)
 			/* skip to end of conditional; skip ELSE-part */
 			ctx->flags.mode = TECO_MODE_PARSE_ONLY_COND;
-		return &teco_state_start;
+		TECO_RETURN(ctx, &teco_state_start, error);
 
-	case '\'': return teco_state_endcond(ctx, "'", error);
+	case '\'': TECO_RETURN(ctx, teco_state_endcond(ctx, "'", error), error);
 
 	/*
 	 * Word movement and deletion commands.
@@ -873,13 +873,13 @@ teco_state_start_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 	 * but should accept only one colon modifier.
 	 */
 	case 'w':
-	case 'W': return teco_state_start_words(ctx, "W", 1, error);
+	case 'W': TECO_RETURN(ctx, teco_state_start_words(ctx, "W", 1, error), error);
 	case 'p':
-	case 'P': return teco_state_start_words(ctx, "P", -1, error);
+	case 'P': TECO_RETURN(ctx, teco_state_start_words(ctx, "P", -1, error), error);
 	case 'v':
-	case 'V': return teco_state_start_delete_words(ctx, "V", 1, error);
+	case 'V': TECO_RETURN(ctx, teco_state_start_delete_words(ctx, "V", 1, error), error);
 	case 'y':
-	case 'Y': return teco_state_start_delete_words(ctx, "Y", -1, error);
+	case 'Y': TECO_RETURN(ctx, teco_state_start_delete_words(ctx, "Y", -1, error), error);
 
 	/*
 	 * Modifiers
@@ -898,11 +898,11 @@ teco_state_start_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 		if (ctx->parent.must_undo)
 			teco_undo_flags(ctx->flags);
 		ctx->flags.modifier_at = TRUE;
-		return &teco_state_start;
+		TECO_RETURN(ctx, &teco_state_start, error);
 
 	case ':':
 		if (ctx->flags.mode > TECO_MODE_NORMAL)
-			return &teco_state_start;
+			TECO_RETURN(ctx, &teco_state_start, error);
 		if (ctx->flags.modifier_colon >= 2) {
 			teco_error_modifier_set(error, ":");
 			return NULL;
@@ -910,18 +910,21 @@ teco_state_start_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 		if (ctx->parent.must_undo)
 			teco_undo_flags(ctx->flags);
 		ctx->flags.modifier_colon++;
-		return &teco_state_start;
+		TECO_RETURN(ctx, &teco_state_start, error);
 
 	default:
 		/*
 		 * <CTRL/x> commands implemented in teco_state_control
 		 */
-		if (TECO_IS_CTL(chr))
-			return teco_state_control_input(ctx, TECO_CTL_ECHO(chr), error);
+		if (TECO_IS_CTL(chr)) {
+			teco_state_t *next = teco_state_control_input(ctx, TECO_CTL_ECHO(chr), error);
+			TECO_RETURN(ctx, next, error);
+		}
 	}
 
-	return teco_machine_main_transition_input(ctx, transitions, G_N_ELEMENTS(transitions),
-	                                          teco_ascii_toupper(chr), error);
+	teco_state_t *next = teco_machine_main_transition_input(ctx, transitions, G_N_ELEMENTS(transitions),
+	                                                        teco_ascii_toupper(chr), error);
+	TECO_RETURN(ctx, next, error);
 }
 
 TECO_DEFINE_STATE_START(teco_state_start,
@@ -1090,11 +1093,12 @@ teco_state_fcommand_input(teco_machine_main_t *ctx, gunichar chr, GError **error
 	};
 
 	switch (chr) {
-	case '"': return teco_state_endcond(ctx, "F\"", error);
+	case '"': TECO_RETURN(ctx, teco_state_endcond(ctx, "F\"", error), error);
 	}
 
-	return teco_machine_main_transition_input(ctx, transitions, G_N_ELEMENTS(transitions),
-	                                          teco_ascii_toupper(chr), error);
+	teco_state_t *next = teco_machine_main_transition_input(ctx, transitions, G_N_ELEMENTS(transitions),
+	                                                        teco_ascii_toupper(chr), error);
+	TECO_RETURN(ctx, next, error);
 }
 
 TECO_DEFINE_STATE_COMMAND(teco_state_fcommand,
@@ -1304,7 +1308,7 @@ teco_state_condcommand_input(teco_machine_main_t *ctx, gunichar chr, GError **er
 		ctx->flags.mode = TECO_MODE_PARSE_ONLY_COND;
 	}
 
-	return &teco_state_start;
+	TECO_RETURN(ctx, &teco_state_start, error);
 }
 
 TECO_DEFINE_STATE_COMMAND(teco_state_condcommand,
@@ -1740,8 +1744,9 @@ teco_state_control_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 	 * Currently you get error messages like 'Syntax error "F"' for ^F.
 	 * The easiest way around would be g_prefix_error(error, "Control command");
 	 */
-	return teco_machine_main_transition_input(ctx, transitions, G_N_ELEMENTS(transitions),
-	                                          teco_ascii_toupper(chr), error);
+	teco_state_t *next = teco_machine_main_transition_input(ctx, transitions, G_N_ELEMENTS(transitions),
+	                                                        teco_ascii_toupper(chr), error);
+	TECO_RETURN(ctx, next, error);
 }
 
 TECO_DEFINE_STATE_COMMAND(teco_state_control,
@@ -1754,7 +1759,7 @@ teco_state_ascii_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 	if (ctx->flags.mode == TECO_MODE_NORMAL)
 		teco_expressions_push(chr);
 
-	return &teco_state_start;
+	TECO_RETURN(ctx, &teco_state_start, error);
 }
 
 /*$ ^^ ^^c
@@ -1939,7 +1944,7 @@ teco_state_ctlc_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 {
 	switch (chr) {
 	case TECO_CTL_KEY('C'):	return teco_state_ctlc_control_input(ctx, 'C', error);
-	case '^':		return &teco_state_ctlc_control;
+	case '^':		TECO_RETURN(ctx, &teco_state_ctlc_control, error);
 	}
 
 	return ctx->flags.mode > TECO_MODE_NORMAL
@@ -1992,7 +1997,7 @@ teco_state_ctlc_control_input(teco_machine_main_t *ctx, gunichar chr, GError **e
 	 */
 	if (chr == 'c' || chr == 'C') {
 		if (ctx->flags.mode > TECO_MODE_NORMAL)
-			return &teco_state_start;
+			TECO_RETURN(ctx, &teco_state_start, error);
 
 		if (teco_undo_enabled) {
 			g_set_error_literal(error, TECO_ERROR, TECO_ERROR_FAILED,
@@ -2956,8 +2961,9 @@ teco_state_ecommand_input(teco_machine_main_t *ctx, gunichar chr, GError **error
 	/*
 	 * FIXME: Should we return a special syntax error in case of failure?
 	 */
-	return teco_machine_main_transition_input(ctx, transitions, G_N_ELEMENTS(transitions),
-	                                          teco_ascii_toupper(chr), error);
+	teco_state_t *next = teco_machine_main_transition_input(ctx, transitions, G_N_ELEMENTS(transitions),
+	                                                        teco_ascii_toupper(chr), error);
+	TECO_RETURN(ctx, next, error);
 }
 
 TECO_DEFINE_STATE_COMMAND(teco_state_ecommand,
diff --git a/src/goto-commands.c b/src/goto-commands.c
index a9ff3c2..72ac80d 100644
--- a/src/goto-commands.c
+++ b/src/goto-commands.c
@@ -61,8 +61,8 @@ teco_state_label_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 {
 	if (!ctx->goto_label.len) {
 		switch (chr) {
-		case '*': return &teco_state_blockcomment;	/* `!*` */
-		case '!': return &teco_state_eolcomment;	/* `!!` */
+		case '*': TECO_RETURN(ctx, &teco_state_blockcomment, error);	/* `!*` */
+		case '!': TECO_RETURN(ctx, &teco_state_eolcomment, error);	/* `!!` */
 		}
 	}
 
@@ -97,7 +97,7 @@ teco_state_label_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 			teco_string_clear(&ctx->goto_label);
 		memset(&ctx->goto_label, 0, sizeof(ctx->goto_label));
 
-		return &teco_state_start;
+		TECO_RETURN(ctx, &teco_state_start, error);
 	}
 
 	/*
@@ -109,7 +109,7 @@ teco_state_label_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 	if (ctx->parent.must_undo)
 		undo__teco_string_truncate(&ctx->goto_label, ctx->goto_label.len);
 	teco_string_append_wc(&ctx->goto_label, chr);
-	return &teco_state_label;
+	TECO_RETURN(ctx, &teco_state_label, error);
 }
 
 TECO_DEFINE_STATE(teco_state_label,
@@ -244,34 +244,34 @@ TECO_DEFINE_STATE_EXPECTSTRING(teco_state_goto,
 	)
 
 static teco_state_t *
-teco_state_blockcomment_star_input(teco_machine_t *ctx, gunichar chr, GError **error)
+teco_state_blockcomment_star_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 {
-	return chr == '!' ? &teco_state_start : &teco_state_blockcomment;
+	TECO_RETURN(ctx, chr == '!' ? &teco_state_start : &teco_state_blockcomment, error);
 }
 
 static TECO_DEFINE_STATE_COMMENT(teco_state_blockcomment_star,
-	.input_cb = teco_state_blockcomment_star_input
+	.input_cb = (teco_state_input_cb_t)teco_state_blockcomment_star_input
 );
 
 static teco_state_t *
-teco_state_blockcomment_input(teco_machine_t *ctx, gunichar chr, GError **error)
+teco_state_blockcomment_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 {
-	return chr == '*' ? &teco_state_blockcomment_star : &teco_state_blockcomment;
+	TECO_RETURN(ctx, chr == '*' ? &teco_state_blockcomment_star : &teco_state_blockcomment, error);
 }
 
 static TECO_DEFINE_STATE_COMMENT(teco_state_blockcomment,
-	.input_cb = teco_state_blockcomment_input
+	.input_cb = (teco_state_input_cb_t)teco_state_blockcomment_input
 );
 
 /*
  * `!!` line comments are inspired by TECO-64.
  */
 static teco_state_t *
-teco_state_eolcomment_input(teco_machine_t *ctx, gunichar chr, GError **error)
+teco_state_eolcomment_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 {
-	return chr == '\n' ? &teco_state_start : &teco_state_eolcomment;
+	TECO_RETURN(ctx, chr == '\n' ? &teco_state_start : &teco_state_eolcomment, error);
 }
 
 static TECO_DEFINE_STATE_COMMENT(teco_state_eolcomment,
-	.input_cb = teco_state_eolcomment_input
+	.input_cb = (teco_state_input_cb_t)teco_state_eolcomment_input
 );
diff --git a/src/parser.c b/src/parser.c
index 8b02764..8ec051e 100644
--- a/src/parser.c
+++ b/src/parser.c
@@ -104,6 +104,9 @@ teco_machine_main_step(teco_machine_main_t *ctx, const gchar *macro, gsize stop_
 {
 	gsize last_pc = 0;
 
+	ctx->macro = macro;
+	ctx->stop_pos = stop_pos;
+
 	while (ctx->macro_pc < stop_pos) {
 		last_pc = ctx->macro_pc;
 
@@ -1091,7 +1094,7 @@ teco_state_expectstring_input(teco_machine_main_t *ctx, gunichar chr, GError **e
 	 * as allowing whitespace escape_chars is harmful.
 	 */
 	if (ctx->flags.modifier_at && teco_is_noop(chr))
-		return current;
+		TECO_RETURN(ctx, current, error);
 
 	/*
 	 * String termination handling
@@ -1106,7 +1109,7 @@ teco_state_expectstring_input(teco_machine_main_t *ctx, gunichar chr, GError **e
 		if (ctx->parent.must_undo)
 			teco_undo_gunichar(ctx->expectstring.machine.escape_char);
 		ctx->expectstring.machine.escape_char = g_unichar_toupper(chr);
-		return current;
+		TECO_RETURN(ctx, current, error);
 	}
 
 	/*
@@ -1177,7 +1180,7 @@ teco_state_expectstring_input(teco_machine_main_t *ctx, gunichar chr, GError **e
 		if (ctx->parent.must_undo)
 			teco_undo_gsize(ctx->expectstring.insert_len);
 		ctx->expectstring.insert_len = 0;
-		return next;
+		TECO_RETURN(ctx, next, error);
 	}
 
 	/*
@@ -1213,7 +1216,7 @@ teco_state_expectstring_input(teco_machine_main_t *ctx, gunichar chr, GError **e
 		teco_undo_gsize(ctx->expectstring.insert_len);
 	ctx->expectstring.insert_len += ctx->expectstring.string.len - old_len;
 
-	return current;
+	TECO_RETURN(ctx, current, error);
 }
 
 gboolean
diff --git a/src/parser.h b/src/parser.h
index 0c389cc..75a3432 100644
--- a/src/parser.h
+++ b/src/parser.h
@@ -25,6 +25,7 @@
 #include "goto.h"
 #include "undo.h"
 #include "qreg.h"
+#include "memory.h"
 #include "lexer.h"
 
 /*
@@ -481,8 +482,12 @@ typedef enum {
 struct teco_machine_main_t {
 	teco_machine_t parent;
 
+	/** currently executed macro */
+	const gchar *macro;
 	/** Program counter, i.e. pointer to the next character in the current macro frame */
 	gsize macro_pc;
+	/** possibly preliminary end of macro */
+	gsize stop_pos;
 
 	struct teco_machine_main_flags_t {
 		teco_mode_t mode : 8;
@@ -550,6 +555,71 @@ gboolean teco_machine_main_eval_at(teco_machine_main_t *ctx);
 gboolean teco_machine_main_step(teco_machine_main_t *ctx,
                                 const gchar *macro, gsize stop_pos, GError **error);
 
+#if __has_attribute(musttail)
+
+/**
+ * Transition from a teco_machine_main input_cb() to another state.
+ *
+ * Instead of returning to the caller, this can tail call,
+ * which will often be optimized to direct jumps, turning
+ * state transitions into "threaded" code.
+ * In some macros this achieves up to 18% speedup.
+ *
+ * On the other hand, this works only from functions with
+ * compatible signatures (practically only from
+ * teco_state_t::input_cb()).
+ * When this optimization is used, other function calls
+ * may no longer be tail-call optimized.
+ *
+ * @see teco_machine_main_step
+ * @see teco_machine_input
+ */
+#define TECO_RETURN(CTX, STATE, ERROR) G_STMT_START { \
+	teco_machine_main_t *const __ctx = (CTX); \
+	teco_state_t *const __state = (STATE); \
+	GError **const __error = (ERROR); \
+	\
+	if (!__state) \
+		return NULL; \
+	\
+	if (G_UNLIKELY(teco_interface_is_interrupted())) { \
+		teco_error_interrupted_set(__error); \
+		return NULL; \
+	} \
+	\
+	if (!teco_memory_check(0, __error)) \
+		return NULL; \
+	\
+	if (__ctx->macro_pc >= __ctx->stop_pos) \
+		return __state; /* terminate tail calls */ \
+	\
+	if (__state != __ctx->parent.current) { \
+		if (__ctx->parent.must_undo) \
+			teco_undo_ptr(__ctx->parent.current); \
+		__ctx->parent.current = __state; \
+		\
+		if (__ctx->parent.current->initial_cb && \
+		    !__ctx->parent.current->initial_cb(&__ctx->parent, __error)) \
+			return NULL; \
+	} \
+	\
+	gunichar chr = g_utf8_get_char(__ctx->macro+__ctx->macro_pc); \
+	__ctx->macro_pc = g_utf8_next_char(__ctx->macro+__ctx->macro_pc) - __ctx->macro; \
+	\
+	/* the caller's signature will not line up exactly with input_cb */ \
+	typedef teco_state_t *(*caller_t)(teco_machine_main_t *, gunichar, GError **); \
+	__attribute__((musttail)) return ((caller_t)__state->input_cb)(__ctx, chr, __error); \
+} G_STMT_END
+
+#else /* __has_attribute(musttail) */
+
+/*
+ * This will effectively return into the teco_machine_main_step() loop.
+ */
+#define TECO_RETURN(CTX, STATE, ERROR) return (STATE)
+
+#endif /* !__has_attribute(musttail) */
+
 gboolean teco_execute_macro(const gchar *macro, gsize macro_len,
                             teco_qreg_table_t *qreg_table_locals, GError **error);
 gboolean teco_execute_file(const gchar *filename, teco_qreg_table_t *qreg_table_locals, GError **error);
diff --git a/src/qreg-commands.c b/src/qreg-commands.c
index a6390a1..d7b0a10 100644
--- a/src/qreg-commands.c
+++ b/src/qreg-commands.c
@@ -62,7 +62,7 @@ teco_state_expectqreg_input(teco_machine_main_t *ctx, gunichar chr, GError **err
 	case TECO_MACHINE_QREGSPEC_ERROR:
 		return NULL;
 	case TECO_MACHINE_QREGSPEC_MORE:
-		return current;
+		TECO_RETURN(ctx, current, error);
 	case TECO_MACHINE_QREGSPEC_DONE:
 		break;
 	}
@@ -72,7 +72,8 @@ teco_state_expectqreg_input(teco_machine_main_t *ctx, gunichar chr, GError **err
 	 * states. This means, it must usually be reset manually in got_register_cb() via:
 	 * teco_state_expectqreg_reset(ctx);
 	 */
-	return current->expectqreg.got_register_cb(ctx, qreg, table, error);
+	teco_state_t *next = current->expectqreg.got_register_cb(ctx, qreg, table, error);
+	TECO_RETURN(ctx, next, error);
 }
 
 static teco_state_t *
diff --git a/src/stdio-commands.c b/src/stdio-commands.c
index 34179c3..94da3c7 100644
--- a/src/stdio-commands.c
+++ b/src/stdio-commands.c
@@ -139,7 +139,7 @@ static teco_state_t *
 teco_state_print_decimal_input(teco_machine_main_t *ctx, gunichar chr, GError **error)
 {
 	if (chr == '=')
-		return &teco_state_print_octal;
+		TECO_RETURN(ctx, &teco_state_print_octal, error);
 
 	if (ctx->flags.mode == TECO_MODE_NORMAL) {
 		if (G_LIKELY(!is_executing) && !teco_print(ctx, 10, error))
@@ -197,7 +197,7 @@ teco_state_print_octal_input(teco_machine_main_t *ctx, gunichar chr, GError **er
 				return NULL;
 			teco_expressions_pop_num(0);
 		}
-		return &teco_state_start;
+		TECO_RETURN(ctx, &teco_state_start, error);
 	}
 
 	if (ctx->flags.mode == TECO_MODE_NORMAL) {