[Mesa-dev] [PATCH 11/12] glcpp: Create fast path hand-written scanner
Vladislav Egorov
vegorov180 at gmail.com
Sat Jan 7 19:02:12 UTC 2017
At this point up to ~80% of preprocessing time is spent in generated
parser/lexer functions, so it's not possible to improve speed further
without making changes to lexer and parser. In most of the cases all
complex machinery of tokenizing, parsing and printing is completely
unnecessary. On most of the shaders preprocessor works more like a
fancy memcpy, removing comments, most of the shaders use preprocessor
in very limited way.
Create handwritten scanner that bypasses ordinary flex->bison->printing
path on text lines. It avoids tokenization and copies as large
fragments of text as possible. When it encounters something it can't
process (e.g. all directives or macros), it bailouts to ordinary slow
path with tokenization.
It solves multiple performance problems at once - slow Flex lexing,
slow Bison parsing, printing in token-by-token way, generation of
huge amount of fat tokens (memory pressure), strduping every single
encountered identifier. On my shader-db it improves preprocessing
time from 10.52s to 2.46s.
Technically it's implemented via injection into glcpp_lex() (request
for the next token). Fast path does its job and only then lets
flex lexer go its ordinary way.
---
src/compiler/glsl/glcpp/glcpp-lex.l | 354 ++++++++++++++++++++++++++++++++++
src/compiler/glsl/glcpp/glcpp-parse.y | 11 +-
src/compiler/glsl/glcpp/glcpp.h | 1 +
3 files changed, 364 insertions(+), 2 deletions(-)
diff --git a/src/compiler/glsl/glcpp/glcpp-lex.l b/src/compiler/glsl/glcpp/glcpp-lex.l
index 93e5cb3..8e916a2 100644
--- a/src/compiler/glsl/glcpp/glcpp-lex.l
+++ b/src/compiler/glsl/glcpp/glcpp-lex.l
@@ -33,6 +33,7 @@
* static. Let's declare them here. */
int glcpp_get_column (yyscan_t yyscanner);
void glcpp_set_column (int column_no , yyscan_t yyscanner);
+struct yyguts_t;
#ifdef _MSC_VER
#define YY_NO_UNISTD_H
@@ -158,6 +159,8 @@ glcpp_lex_update_state_per_token (glcpp_parser_t *parser, int token)
}
}
+static void
+glcpp_fast_process_line(glcpp_parser_t *parser, struct yyguts_t *yyg);
%}
@@ -256,6 +259,30 @@ HEXADECIMAL_INTEGER 0[xX][0-9a-fA-F]+[uU]?
parser->skipping = 0;
}
+ /* Launch fast path, direct copying from input to output without
+ * intermediate step of tokenization. Few conditions to start it:
+ *
+ * 1. We should be at the start of the line.
+ * 2. The version should be already set, let the slow path do it.
+ * 3. We should be in non-skipping mode.
+ * 4. We should be outside of directives.
+ * 5. dont_use_fast_path flag should be unset.
+ */
+ if (YY_START == INITIAL &&
+ !parser->dont_use_fast_path &&
+ !parser->skipping &&
+ !parser->lexing_directive &&
+ parser->version_set &&
+ yycolumn == 0) {
+ /* If the parser updated line number, change it */
+ if (parser->has_new_line_number) {
+ yylineno = parser->new_line_number;
+ parser->has_new_line_number = 0;
+ }
+ *yyg->yy_c_buf_p = yyg->yy_hold_char;
+ glcpp_fast_process_line(parser, yyg);
+ }
+
/* Single-line comments */
<INITIAL,DEFINE,HASH>"//"[^\r\n]* {
}
@@ -582,6 +609,333 @@ HEXADECIMAL_INTEGER 0[xX][0-9a-fA-F]+[uU]?
%%
+static void
+glcpp_fast_skip_singleline_comment (glcpp_parser_t *parser, char **input)
+{
+ /* Skip // */
+ char *buf = *input + 2;
+
+ while (true) {
+ char ch = *buf;
+ if (ch == '\r' || ch == '\n' || ch == '\0')
+ break;
+ buf++;
+ }
+
+ *input = buf;
+}
+
+static bool
+glcpp_fast_skip_multiline_comment (glcpp_parser_t *parser,
+ char **input,
+ char **last_newline,
+ int *newline_count,
+ struct string_buffer *output)
+{
+ /* Skip the leading '/' and '*' */
+ char *buf = *input + 2;
+ int newlines = 0;
+
+ while (true) {
+ char ch = buf[0], ch1 = buf[1];
+
+ /* Don't do anything. Fallback to slow path to print error. */
+ if (ch == '\0') {
+ parser->dont_use_fast_path = true;
+ return false;
+ }
+
+ if (ch == '\r' || ch == '\n') {
+ char ch1 = buf[1];
+ /* Skip "\r\n" and "\n\r", but not "\n\n" or "\r\r" */
+ if (unlikely((ch1 == '\r' || ch1 == '\n') && (ch1 != ch)))
+ buf++;
+ buf++;
+ *last_newline = buf;
+ newlines++;
+ } else if (ch == '*' && ch1 == '/') {
+ buf += 2;
+ break;
+ } else {
+ buf++;
+ }
+ }
+
+ if (output != NULL) {
+ /* Print newlines if any */
+ if (newlines > 0) {
+ glcpp_strbuffer_ensure_capacity(parser, output, newlines);
+ memset(output->buf + output->length, '\n', newlines);
+ output->length += newlines;
+ *newline_count += newlines;
+ } else {
+ /* Print a single space */
+ if (output->length > 0 && output->buf[output->length - 1] != ' ')
+ glcpp_append_char(parser, output, ' ');
+ }
+ }
+
+ *input = buf;
+ return true;
+}
+
+static inline
+bool glcpp_is_alphanum(char ch) {
+ return (ch >= 'A' && ch <= 'Z') ||
+ (ch >= 'a' && ch <= 'z') ||
+ (ch >= '0' && ch <= '9') ||
+ ch == '_';
+}
+
+static void
+glcpp_fast_skip_number(char **input)
+{
+ /* The first digit was already matched */
+ char *buf = *input + 1;
+
+ /* Matching rule is the following: [.]?[0-9]([._a-zA-Z0-9]|[eEpP][-+])* */
+ while (true) {
+ char ch = buf[0], ch1 = buf[1];
+ if (!(glcpp_is_alphanum(ch) || ch == '.'))
+ break;
+ if ((ch == 'E' || ch == 'e' || ch == 'P' || ch == 'p') &&
+ (ch1 == '+' || ch1 == '-'))
+ buf++;
+ buf++;
+ }
+
+ *input = buf;
+}
+
+static void
+glcpp_fast_flush(glcpp_parser_t *parser, struct string_buffer *out,
+ char *input, char **last_printed)
+{
+ if (input > *last_printed)
+ glcpp_append_length(parser, out, *last_printed, input - *last_printed);
+ *last_printed = input;
+}
+
+static bool
+glcpp_fast_process_identifier(glcpp_parser_t *parser,
+ struct string_buffer *out,
+ struct yyguts_t *yyg,
+ char **input,
+ char **last_printed,
+ int newline_count)
+{
+ char *id_start = *input;
+ char *buf = id_start;
+ char id_two_chars[2];
+ char ch_last;
+ bool success = true;
+
+ /* Scan to the end of the identifier. We already know that the first char
+ * belongs to the id.
+ */
+ do {
+ buf++;
+ ch_last = *buf;
+ } while (glcpp_is_alphanum(ch_last));
+
+ /* Prepare two first chars of the id for the Bloom filter */
+ id_two_chars[0] = id_start[0];
+ id_two_chars[1] = (buf - id_start) > 1 ? id_start[1] : '\0';
+
+ if (GLCPP_DEFINES_BLOOM_GET(parser, id_two_chars)) {
+ /* Null-terminate the identifier right in the buffer, and then restore
+ * it back. That's what flex is doing too. The buffer is exclusively
+ * owned by lexer's thread, so it can be freely messed with.
+ */
+ *buf = '\0';
+ /* __LINE__ and __FILE__ are not in the hash-table */
+ if (!strcmp(id_start, "__LINE__")) {
+ glcpp_fast_flush(parser, out, id_start, last_printed);
+ glcpp_printf(parser, out, "%" PRIiMAX, yylineno + newline_count);
+ *last_printed = buf;
+ *buf = ch_last;
+ } else if (!strcmp(id_start, "__FILE__")) {
+ glcpp_fast_flush(parser, out, id_start, last_printed);
+ glcpp_printf(parser, out, "%" PRIiMAX, parser->new_source_number);
+ *last_printed = buf;
+ *buf = ch_last;
+ } else {
+ struct hash_entry *entry = _mesa_hash_table_search(parser->defines,
+ id_start);
+ *buf = ch_last;
+
+ /* If the identifier points to some function-like macro, we can't
+ * process it in the fast path. Fallback to tokenization.
+ */
+ if (entry) {
+ parser->dont_use_fast_path = true;
+ glcpp_fast_flush(parser, out, id_start, last_printed);
+ buf = id_start;
+ success = false;
+ *last_printed = id_start;
+ }
+ }
+ }
+
+ *input = buf;
+ return success;
+}
+
+void
+glcpp_fast_process_line(glcpp_parser_t *parser, struct yyguts_t *yyg)
+{
+ struct string_buffer *out = &parser->output;
+ char *initial_input = yyg->yy_c_buf_p;
+ char *input = initial_input;
+ char *last_printed = initial_input;
+ char *last_newline = NULL;
+ char *before_last_newline = NULL;
+ size_t before_last_newline_len = 0;
+ size_t initial_len = out->length;
+ bool prev_was_space = false;
+ int newline_count = 0;
+
+ /* Emit NEWLINE token, if we start at newline, the parser needs it */
+ if (*initial_input == '\n' || *initial_input == '\r')
+ return;
+
+ /* Process input. Copy (flush) to the output as rarely as possible, in big
+ * chunks. For example, in line "a + abc + .123 + MACRO(x)", substring
+ * "a + abc + .123 + " can be copied to the output at once without any
+ * modifications, while the rest should be processed by tokenizer.
+ */
+ while (true) {
+ /* The input buffer has at least 2 null-terminators at the end,
+ * the next char can be accessed safely.
+ */
+ char ch = input[0], ch1 = input[1];
+
+ /* GCC generates some reasonable mostly branch-free code here, it seems
+ * there is no urgent need to use bit tricks and low-level optimizations.
+ */
+ bool is_alpha = (ch >= 'A' && ch <= 'Z') ||
+ (ch >= 'a' && ch <= 'z') ||
+ ch == '_';
+ bool is_number = ch >= '0' && ch <= '9';
+ bool is_unusual_space = ch == '\v' || ch == '\t' || ch == '\f';
+ bool is_space = ch == ' ' || is_unusual_space;
+
+ if (is_alpha) {
+ /* An identifier starts here, try to consume it. If it refers to
+ * a macro, fallback to tokenization.
+ */
+ if (!glcpp_fast_process_identifier(parser, out, yyg, &input,
+ &last_printed, newline_count))
+ goto _done;
+ prev_was_space = false;
+ } else if ((ch == ' ' && prev_was_space) || is_unusual_space) {
+ /* If there is a single space, do nothing. It will be copied 1:1
+ * later, during flushing. Multiple spaces or other space characters
+ * should be processed, though.
+ */
+ glcpp_fast_flush(parser, out, input, &last_printed);
+ do {
+ input++;
+ ch = *input;
+ } while (ch == ' ' || ch == '\v' || ch == '\t' || ch == '\f');
+
+ /* Collapse multiple spaces into one */
+ if (!prev_was_space)
+ glcpp_append_char(parser, out, ' ');
+
+ prev_was_space = true;
+ last_printed = input;
+ } else if (ch == '\r' || ch == '\n') {
+ /* Newlines */
+ glcpp_fast_flush(parser, out, input, &last_printed);
+
+ /* Trim trailing whitespace */
+ while (out->length > 0 && out->buf[out->length - 1] == ' ')
+ out->length--;
+
+ /* Save the last position right on the last newline.
+ * Backtrack to newline, when # will be encountered.
+ */
+ before_last_newline = input;
+ before_last_newline_len = out->length;
+
+ if ((ch1 == '\r' || ch1 == '\n') && ch1 != ch)
+ input++;
+
+ glcpp_append_char(parser, out, '\n');
+ input++;
+ newline_count++;
+ last_newline = input;
+ last_printed = input;
+ prev_was_space = false;
+ } else if (ch == '/') {
+ /* Single-line and multiline comments */
+ if (ch1 == '/') {
+ glcpp_fast_flush(parser, out, input, &last_printed);
+ glcpp_fast_skip_singleline_comment(parser, &input);
+ last_printed = input;
+ prev_was_space = false;
+ } else if (ch1 == '*') {
+ glcpp_fast_flush(parser, out, input, &last_printed);
+ if (!glcpp_fast_skip_multiline_comment(parser, &input,
+ &last_newline,
+ &newline_count, out)) {
+ /* Error. We've achieved end of buffer too early. Fallback to
+ * slow path to show an error about non-terminated comment.
+ */
+ goto _done;
+ }
+ last_printed = input;
+ prev_was_space = true;
+ } else {
+ input++;
+ prev_was_space = false;
+ }
+ } else if (is_number || (ch == '.' && ch1 >= '0' && ch1 <= '9')) {
+ /* A number. Just skip it. */
+ glcpp_fast_skip_number(&input);
+ prev_was_space = false;
+ } else if (ch == '#') {
+ /* Looks like a control line. Backtrack to the last new line and
+ * fallback to tokenization.
+ */
+ if (last_newline != NULL) {
+ last_printed = input = before_last_newline;
+ out->length = before_last_newline_len;
+ newline_count--;
+ glcpp_fast_flush(parser, out, input, &last_printed);
+ } else {
+ last_printed = input = initial_input;
+ out->length = initial_len;
+ }
+ parser->dont_use_fast_path = true;
+ goto _done;
+ } else if (ch == '\0') {
+ /* If the end of the buffer was encountered here, we can terminate. */
+ parser->dont_use_fast_path = true;
+ goto _done;
+ } else {
+ /* Any other character. Skip it */
+ prev_was_space = is_space;
+ input++;
+ }
+ }
+
+_done:
+ glcpp_fast_flush(parser, out, input, &last_printed);
+
+ /* Update Flex's state, if we actually printed something */
+ if (last_printed > initial_input) {
+ yyg->yy_hold_char = *input;
+ yyg->yy_c_buf_p = input;
+ yylineno += newline_count;
+ if (last_newline != NULL)
+ yycolumn = last_printed - last_newline;
+ else
+ yycolumn += last_printed - initial_input;
+ }
+}
+
void
glcpp_lex_set_source_string(glcpp_parser_t *parser, const char *shader)
{
diff --git a/src/compiler/glsl/glcpp/glcpp-parse.y b/src/compiler/glsl/glcpp/glcpp-parse.y
index 438ca51..b5adc8d 100644
--- a/src/compiler/glsl/glcpp/glcpp-parse.y
+++ b/src/compiler/glsl/glcpp/glcpp-parse.y
@@ -205,11 +205,16 @@ input:
;
line:
- control_line
-| SPACE control_line
+ control_line {
+ parser->dont_use_fast_path = false;
+ }
+| SPACE control_line {
+ parser->dont_use_fast_path = false;
+ }
| text_line {
_glcpp_parser_print_expanded_token_list (parser, $1);
glcpp_append_char (parser, &parser->output, '\n');
+ parser->dont_use_fast_path = false;
}
| expanded_line
;
@@ -1363,6 +1368,8 @@ glcpp_parser_create(glcpp_extension_iterator extensions, void *state, gl_api api
parser->paren_count = 0;
parser->commented_newlines = 0;
+ parser->dont_use_fast_path = false;
+
parser->skip_stack = NULL;
parser->skipping = 0;
diff --git a/src/compiler/glsl/glcpp/glcpp.h b/src/compiler/glsl/glcpp/glcpp.h
index 34f8b66..8e8543c 100644
--- a/src/compiler/glsl/glcpp/glcpp.h
+++ b/src/compiler/glsl/glcpp/glcpp.h
@@ -204,6 +204,7 @@ struct glcpp_parser {
active_list_t *active;
int lexing_directive;
int lexing_version_directive;
+ bool dont_use_fast_path;
int space_tokens;
int last_token_was_newline;
int last_token_was_space;
--
2.7.4
More information about the mesa-dev
mailing list