Revision: 18769
Author: [email protected]
Date: Thu Jan 23 10:16:42 2014 UTC
Log: Experimental parser: perform inlining in python
[email protected]
BUG=
Review URL: https://codereview.chromium.org/145583002
http://code.google.com/p/v8/source/detail?r=18769
Modified:
/branches/experimental/parser/tools/lexer_generator/code_generator.jinja
/branches/experimental/parser/tools/lexer_generator/code_generator.py
=======================================
---
/branches/experimental/parser/tools/lexer_generator/code_generator.jinja
Wed Jan 22 14:19:09 2014 UTC
+++
/branches/experimental/parser/tools/lexer_generator/code_generator.jinja
Thu Jan 23 10:16:42 2014 UTC
@@ -196,11 +196,10 @@
{%- endmacro -%}
-{%- macro write_label(label_name, node_number_chain) %}
- {%- set node_number = node_number_chain|first -%}
+{%- macro write_label(label_name, node_number) %}
{%- set state = dfa_states[node_number] -%}
{%- set used = state['entry_points'][label_name] -%}
- {%- set long_label = label_name + '_' + node_number_chain|join('_') -%}
+ {%- set long_label = label_name ~ '_' ~ node_number -%}
{% if used -%}
{{long_label}}:
{%- else -%}
@@ -209,12 +208,11 @@
{% endmacro -%}
-{%- macro do_dfa_state(node_number_chain) -%}
+{%- macro do_dfa_state(node_number) -%}
- {%- set node_number = node_number_chain|first -%}
{%- set state = dfa_states[node_number] -%}
- {{ write_label('state_entry', node_number_chain) }}
+ {{ write_label('state_entry', node_number) }}
{% if not state['can_elide_read'] -%}
READ_CURSOR();
@@ -232,7 +230,7 @@
{{ dispatch_entry_action(entry_action[0], entry_action[1]) }}
{%- endif %}
- {{ write_label('after_entry_code', node_number_chain) }}
+ {{ write_label('after_entry_code', node_number) }}
{%- if debug_print %}
fprintf(stderr, "char at hand is %c (%d)\n", primary_char,
primary_char);
@@ -240,10 +238,10 @@
{%- macro do_transition(jump_id) -%}
{%- set transition_state_id = jump_table[jump_id][0] -%}
- {%- set inline_transition =
dfa_states[transition_state_id]['inline'] %}
+ {%- set inline_transition = jump_table[jump_id][1] == 'inline' %}
FORWARD();
{%- if inline_transition %}
- {{ do_dfa_state([transition_state_id] + node_number_chain) }}
+ {{ do_dfa_state(transition_state_id) }}
{% else %}
{{ jump(jump_id) }}
{% endif %}
@@ -344,7 +342,7 @@
{# first node is start node #}
{% for dfa_state in dfa_states -%}
{%- if not dfa_state['inline'] %}
- {{ do_dfa_state([dfa_state['node_number']]) }}
+ {{ do_dfa_state(dfa_state['node_number']) }}
{%- endif -%}
{%- endfor %}
=======================================
--- /branches/experimental/parser/tools/lexer_generator/code_generator.py
Wed Jan 22 14:19:09 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/code_generator.py
Thu Jan 23 10:16:42 2014 UTC
@@ -28,6 +28,7 @@
import os
import sys
import jinja2
+from copy import deepcopy
from dfa import Dfa
from transition_keys import TransitionKey
@@ -100,6 +101,7 @@
'can_elide_read' : len(transitions) == 0,
'is_eos_handler' : False,
'inline' : None,
+ 'must_not_inline' : False,
# transitions for code generator
'if_transitions' : [],
'switch_transitions' : [],
@@ -118,8 +120,9 @@
}
def __register_jump(self, node_id, label):
- assert label in CodeGenerator.__jump_labels
- state = self.__dfa_states[node_id]['entry_points'][label] = True
+ if label != 'inline':
+ assert label in CodeGenerator.__jump_labels
+ state = self.__dfa_states[node_id]['entry_points'][label] = True
self.__jump_table.append((node_id, label))
return len(self.__jump_table) - 1
@@ -127,7 +130,9 @@
assert state['inline'] == None
inline = False
# inline terminal states
- if not state['transitions']:
+ if state['must_not_inline']:
+ inline = False
+ elif not state['transitions']:
inline = True
# inline next to terminal states with 1 or 2 transitions
elif state['distinct_keys'] < 3 and state['class_keys'] == 0:
@@ -290,6 +295,7 @@
if action in mapped_actions:
value = state['match_action'][1]
target_id = goto_map[value[-1]]
+ states[target_id]['must_not_inline'] = True
if action != 'goto_start':
state['can_elide_read'] = False
label = 'after_entry_code'
@@ -299,27 +305,61 @@
jump_label = self.__register_jump(target_id, label)
state['match_action'] = (action, tuple(list(value[:-1]) +
[jump_label]))
- def __rewrite_transitions_to_jumps(self):
+ def __inlined_state(self, target_id):
+ state = deepcopy(self.__dfa_states[target_id])
+ state['node_number'] = len(self.__dfa_states)
+ self.__dfa_states.append(state)
+ # mark inline as none, to be correctly handled below
+ state['inline'] = None
+ # clear transitions, they shouldn't be used anymore
+ state['transitions'] = []
+ # clear entry points
+ state['entry_points'] = {k : False for k in
CodeGenerator.__jump_labels}
+ return state['node_number']
+
+ def __rewrite_transitions_to_jumps(self, start_id, count,
inline_mapping_in):
+ # order here should match the order of code generation
transition_names = [
- 'if_transitions',
'switch_transitions',
- 'deferred_transitions',
- 'long_char_transitions']
- def f((key, target_id)):
- return (key, self.__register_jump(target_id, 'state_entry'))
- for state in self.__dfa_states:
+ 'if_transitions',
+ 'long_char_transitions',
+ 'deferred_transitions']
+ end_offset = start_id + count
+ assert len(self.__dfa_states) == end_offset
+ total_nodes_created = 0
+ for state_id in range(start_id, end_offset):
+ state = self.__dfa_states[state_id]
+ # this will be ignored during code generation,
+ # and it's needed as a template, so don't rewrite
+ if state['inline'] == True:
+ continue
+ # these is a new inline state, now mark as inline and rewrite
+ if state['inline'] == None:
+ state['inline'] = True
+ inline_mapping = inline_mapping_in.copy()
+ def generate_jump((key, target_id)):
+ jump_type = 'state_entry'
+ if self.__dfa_states[target_id]['inline']:
+ # generate at most one inline state for all transitions
+ if not target_id in inline_mapping:
+ inline_mapping[target_id] = self.__inlined_state(target_id)
+ jump_type = 'inline'
+ target_id = inline_mapping[target_id]
+ else:
+ assert not target_id in inline_mapping
+ return (key, self.__register_jump(target_id, jump_type))
for name in transition_names:
- state[name] = map(f, state[name])
-
- def __mark_entry_points(self):
- # mark the entry point in case there are implicit jumps to it
- self.__dfa_states[0]['entry_points']['state_entry'] = True
- # inlined states can write no labels
- for state in self.__dfa_states:
- entry_points = state['entry_points']
- if state['inline']:
- for k in entry_points.keys():
- entry_points[k] = False
+ state[name] = map(generate_jump, state[name])
+ # now rewrite all nodes created
+ nodes_created = len(inline_mapping) - len(inline_mapping_in)
+ assert len(self.__dfa_states) == (
+ end_offset + total_nodes_created + nodes_created)
+ if nodes_created == 0:
+ continue
+ created = self.__rewrite_transitions_to_jumps(
+ end_offset + total_nodes_created, nodes_created, inline_mapping)
+ total_nodes_created += nodes_created + created
+ return total_nodes_created
def process(self):
@@ -334,17 +374,17 @@
self.__rewrite_deferred_transitions(state)
# rewrite gotos
self.__rewrite_gotos()
- # rewrite transitions to use jumps
- self.__rewrite_transitions_to_jumps()
# set nodes to inline
if self.__inline:
inlined = reduce(self.__set_inline, dfa_states, 0)
if self.__log:
print "%s states inlined" % inlined
- elif self.__log:
- print "no inlining"
- # mark all the entry points that will be used
- self.__mark_entry_points()
+ # rewrite transitions to use jumps
+ inlined_nodes = self.__rewrite_transitions_to_jumps(0,
len(dfa_states), {})
+ if self.__log:
+ print "%s inlined nodes created" % inlined_nodes
+ # mark the entry point in case there are implicit jumps to it
+ self.__dfa_states[0]['entry_points']['state_entry'] = True
default_action = self.__default_action
assert(default_action and default_action.match_action())
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
