[rtems-central commit] validation: Optimize transition map
Sebastian Huber
sebh at rtems.org
Fri Mar 19 14:24:30 UTC 2021
Module: rtems-central
Branch: master
Commit: 4481ff1ad9f2d5fa2eae803e848b6d480496d7c7
Changeset: http://git.rtems.org/rtems-central/commit/?id=4481ff1ad9f2d5fa2eae803e848b6d480496d7c7
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Fri Mar 19 08:58:11 2021 +0100
validation: Optimize transition map
Further reduce the source code and read-only data size through one level
of indirection.
---
rtemsspec/tests/test_validation.py | 144 ++++++++++++++----------------------
rtemsspec/validation.py | 146 +++++++++++++++++++++----------------
2 files changed, 139 insertions(+), 151 deletions(-)
diff --git a/rtemsspec/tests/test_validation.py b/rtemsspec/tests/test_validation.py
index 35ae847..a487374 100644
--- a/rtemsspec/tests/test_validation.py
+++ b/rtemsspec/tests/test_validation.py
@@ -622,62 +622,24 @@ typedef struct {
uint16_t Post_Id : 3;
} Directive_Entry;
-#define E( x0, x1, x2, x3, x4, x5) { x0, x1, x2, x3, \\
- Directive_Post_Status_##x4, Directive_Post_Id_##x5 }
-
-#define EZ( x0, x1) { 0, 0, 0, 0, Directive_Post_Status_##x0, \\
- Directive_Post_Id_##x1 }
-
static const Directive_Entry
-Directive_Map[] = {
- EZ( InvAddr, NullPtr ),
- EZ( InvName, Nop ),
- EZ( InvAddr, NullPtr ),
- EZ( InvName, Nop ),
- EZ( InvAddr, NullPtr ),
- EZ( InvName, Nop ),
- EZ( InvAddr, NullPtr ),
- EZ( InvName, Nop ),
- EZ( InvAddr, NullPtr ),
- EZ( InvName, Nop ),
- EZ( InvAddr, NullPtr ),
- EZ( InvName, Nop ),
- EZ( InvAddr, NullPtr ),
- EZ( Ok, Self ),
- EZ( InvAddr, NullPtr ),
- EZ( Ok, Self ),
- EZ( InvAddr, NullPtr ),
- EZ( Ok, Self ),
- EZ( InvAddr, NullPtr ),
- EZ( Ok, Self ),
- EZ( InvAddr, NullPtr ),
- EZ( Ok, Self ),
- EZ( InvAddr, NullPtr ),
- EZ( Ok, Self ),
- EZ( InvAddr, NullPtr ),
- EZ( Ok, LocalTask ),
- EZ( InvAddr, NullPtr ),
-#if defined(RTEMS_MULTIPROCESSING)
- EZ( Ok, RemoteTask ),
-#else
- EZ( InvName, Nop ),
-#endif
- EZ( InvAddr, NullPtr ),
- EZ( InvName, Nop ),
- EZ( InvAddr, NullPtr ),
- EZ( Ok, LocalTask ),
- EZ( InvAddr, NullPtr ),
+Directive_Entries[] = {
+ { 0, 0, 0, 0, Directive_Post_Status_InvAddr, Directive_Post_Id_NullPtr },
+ { 0, 0, 0, 0, Directive_Post_Status_InvName, Directive_Post_Id_Nop },
+ { 0, 0, 0, 0, Directive_Post_Status_Ok, Directive_Post_Id_Self },
+ { 0, 0, 0, 0, Directive_Post_Status_Ok, Directive_Post_Id_LocalTask },
#if defined(RTEMS_MULTIPROCESSING)
- EZ( Ok, RemoteTask ),
+ { 0, 0, 0, 0, Directive_Post_Status_Ok, Directive_Post_Id_RemoteTask }
#else
- EZ( InvName, Nop ),
+ { 0, 0, 0, 0, Directive_Post_Status_InvName, Directive_Post_Id_Nop }
#endif
- EZ( InvAddr, NullPtr ),
- EZ( Ok, LocalTask )
};
-#undef E
-#undef EZ
+static const uint8_t
+Directive_Map[] = {
+ 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 3,
+ 0, 4, 0, 1, 0, 3, 0, 4, 0, 3
+};
static size_t Directive_Scope( void *arg, char *buf, size_t n )
{
@@ -700,12 +662,20 @@ static T_fixture Directive_Fixture = {
.initial_context = &Directive_Instance
};
+static inline Directive_Entry Directive_GetEntry( size_t index )
+{
+ return Directive_Entries[
+ Directive_Map[ index ]
+ ];
+}
+
/**
* @fn void T_case_body_Directive( void )
*/
T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture )
{
Directive_Context *ctx;
+ Directive_Entry entry;
size_t index;
ctx = T_fixture_context();
@@ -717,7 +687,9 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture )
ctx->pcs[ 0 ] < Directive_Pre_Name_NA;
++ctx->pcs[ 0 ]
) {
- if ( Directive_Map[ index ].Pre_Name_NA ) {
+ entry = Directive_GetEntry( index );
+
+ if ( entry.Pre_Name_NA ) {
ctx->pcs[ 0 ] = Directive_Pre_Name_NA;
index += ( Directive_Pre_Name_NA - 1 )
* Directive_Pre_Node_NA
@@ -729,7 +701,9 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture )
ctx->pcs[ 1 ] < Directive_Pre_Node_NA;
++ctx->pcs[ 1 ]
) {
- if ( Directive_Map[ index ].Pre_Node_NA ) {
+ entry = Directive_GetEntry( index );
+
+ if ( entry.Pre_Node_NA ) {
ctx->pcs[ 1 ] = Directive_Pre_Node_NA;
index += ( Directive_Pre_Node_NA - 1 )
* Directive_Pre_Id_NA;
@@ -740,14 +714,14 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture )
ctx->pcs[ 2 ] < Directive_Pre_Id_NA;
++ctx->pcs[ 2 ]
) {
- Directive_Entry entry;
+ entry = Directive_GetEntry( index );
- if ( Directive_Map[ index ].Pre_Id_NA ) {
+ if ( entry.Pre_Id_NA ) {
ctx->pcs[ 2 ] = Directive_Pre_Id_NA;
index += ( Directive_Pre_Id_NA - 1 );
}
- if ( Directive_Map[ index ].Skip ) {
+ if ( entry.Skip ) {
++index;
continue;
}
@@ -756,7 +730,6 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture )
Directive_Pre_Node_Prepare( ctx, ctx->pcs[ 1 ] );
Directive_Pre_Id_Prepare( ctx, ctx->pcs[ 2 ] );
Directive_Action( ctx );
- entry = Directive_Map[ index ];
Directive_Post_Status_Check( ctx, entry.Post_Status );
Directive_Post_Id_Check( ctx, entry.Post_Id );
++index;
@@ -2125,35 +2098,19 @@ typedef struct {
uint16_t Post_B : 2;
} Action2_Entry;
-#define E( x0, x1, x2, x3, x4, x5) { x0, x1, x2, x3, Action2_Post_A_##x4, \\
- Action2_Post_B_##x5 }
-
-#define EZ( x0, x1) { 0, 0, 0, 0, Action2_Post_A_##x0, Action2_Post_B_##x1 }
-
static const Action2_Entry
-Action2_Map[] = {
- EZ( A1, B0 ),
- EZ( A1, B0 ),
- EZ( A1, B0 ),
- E( 0, 1, 0, 0, A1, NA ),
- E( 0, 1, 0, 0, A1, NA ),
- E( 0, 1, 0, 0, A1, NA ),
- EZ( A2, B0 ),
- EZ( A2, B0 ),
- EZ( A2, B0 ),
- EZ( A2, B0 ),
- EZ( A2, B0 ),
- EZ( A3, B0 ),
- E( 0, 1, 0, 0, A1, NA ),
- E( 0, 1, 0, 0, A1, NA ),
- E( 0, 1, 0, 0, A1, NA ),
- E( 1, 0, 0, 0, NA, NA ),
- E( 1, 0, 0, 0, NA, NA ),
- E( 1, 0, 0, 0, NA, NA )
+Action2_Entries[] = {
+ { 0, 1, 0, 0, Action2_Post_A_A1, Action2_Post_B_NA },
+ { 0, 0, 0, 0, Action2_Post_A_A2, Action2_Post_B_B0 },
+ { 0, 0, 0, 0, Action2_Post_A_A1, Action2_Post_B_B0 },
+ { 1, 0, 0, 0, Action2_Post_A_NA, Action2_Post_B_NA },
+ { 0, 0, 0, 0, Action2_Post_A_A3, Action2_Post_B_B0 }
};
-#undef E
-#undef EZ
+static const uint8_t
+Action2_Map[] = {
+ 2, 2, 2, 0, 0, 0, 1, 1, 1, 1, 1, 4, 0, 0, 0, 3, 3, 3
+};
static size_t Action2_Scope( void *arg, char *buf, size_t n )
{
@@ -2176,11 +2133,19 @@ static T_fixture Action2_Fixture = {
.initial_context = &Action2_Instance
};
+static inline Action2_Entry Action2_GetEntry( size_t index )
+{
+ return Action2_Entries[
+ Action2_Map[ index ]
+ ];
+}
+
static T_fixture_node Action2_Node;
void Action2_Run( int *a, int b, int *c )
{
Action2_Context *ctx;
+ Action2_Entry entry;
size_t index;
ctx = T_push_fixture( &Action2_Node, &Action2_Fixture );
@@ -2196,7 +2161,9 @@ void Action2_Run( int *a, int b, int *c )
ctx->pcs[ 0 ] < Action2_Pre_A_NA;
++ctx->pcs[ 0 ]
) {
- if ( Action2_Map[ index ].Pre_A_NA ) {
+ entry = Action2_GetEntry( index );
+
+ if ( entry.Pre_A_NA ) {
ctx->pcs[ 0 ] = Action2_Pre_A_NA;
index += ( Action2_Pre_A_NA - 1 )
* Action2_Pre_B_NA
@@ -2208,7 +2175,9 @@ void Action2_Run( int *a, int b, int *c )
ctx->pcs[ 1 ] < Action2_Pre_B_NA;
++ctx->pcs[ 1 ]
) {
- if ( Action2_Map[ index ].Pre_B_NA ) {
+ entry = Action2_GetEntry( index );
+
+ if ( entry.Pre_B_NA ) {
ctx->pcs[ 1 ] = Action2_Pre_B_NA;
index += ( Action2_Pre_B_NA - 1 )
* Action2_Pre_C_NA;
@@ -2219,14 +2188,14 @@ void Action2_Run( int *a, int b, int *c )
ctx->pcs[ 2 ] < Action2_Pre_C_NA;
++ctx->pcs[ 2 ]
) {
- Action2_Entry entry;
+ entry = Action2_GetEntry( index );
- if ( Action2_Map[ index ].Pre_C_NA ) {
+ if ( entry.Pre_C_NA ) {
ctx->pcs[ 2 ] = Action2_Pre_C_NA;
index += ( Action2_Pre_C_NA - 1 );
}
- if ( Action2_Map[ index ].Skip ) {
+ if ( entry.Skip ) {
++index;
continue;
}
@@ -2236,7 +2205,6 @@ void Action2_Run( int *a, int b, int *c )
Action2_Pre_B_Prepare( ctx, ctx->pcs[ 1 ] );
Action2_Pre_C_Prepare( ctx, ctx->pcs[ 2 ] );
Action2_Action( ctx );
- entry = Action2_Map[ index ];
Action2_Post_A_Check( ctx, entry.Post_A );
Action2_Post_B_Check( ctx, entry.Post_B );
Action2_Cleanup( ctx );
diff --git a/rtemsspec/validation.py b/rtemsspec/validation.py
index c3034f8..e75aff9 100644
--- a/rtemsspec/validation.py
+++ b/rtemsspec/validation.py
@@ -467,8 +467,31 @@ class Transition(NamedTuple):
post_cond: Tuple[int, ...]
+class _TransitionEntry:
+ def __init__(self):
+ self.key = ""
+ self.variants = [] # type: List[Transition]
+
+ def __bool__(self):
+ return bool(self.variants)
+
+ def __getitem__(self, key):
+ return self.variants[key]
+
+ def __len__(self):
+ return len(self.variants)
+
+ def add(self, variant: Transition) -> None:
+ """ Adds the variant to the transitions of the entry. """
+ self.key += "".join(
+ (enabled_by_to_exp(variant.enabled_by,
+ ExpressionMapper()), str(variant.skip),
+ str(variant.pre_cond_na), str(variant.post_cond)))
+ self.variants.append(variant)
+
+
_IdxToX = Tuple[Tuple[str, ...], ...]
-_TransitionMap = List[List[Transition]]
+_TransitionMap = List[_TransitionEntry]
def _to_st_idx(conditions: List[Any]) -> Tuple[Dict[str, int], ...]:
@@ -619,8 +642,9 @@ class TransitionMap:
self._post_co_idx_to_co_name = dict(
(co_idx, condition["name"])
for co_idx, condition in enumerate(item["post-conditions"]))
+ self._entries = {} # type: Dict[str, List[Any]]
self._map = self._build_map()
- self._check_completeness()
+ self._post_process()
def __getitem__(self, key: str):
return self._item[key]
@@ -628,7 +652,7 @@ class TransitionMap:
def __iter__(self):
yield from self._map
- def _check_completeness(self) -> None:
+ def _post_process(self) -> None:
for map_idx, transitions in enumerate(self):
if not transitions or not isinstance(
transitions[0].enabled_by,
@@ -637,6 +661,14 @@ class TransitionMap:
f"transition map of {self._item.spec} contains no default "
"entry for pre-condition set "
f"{{{self._map_index_to_pre_conditions(map_idx)}}}")
+ entry = self._entries.get(transitions.key, [0, 0, transitions])
+ entry[0] += 1
+ self._entries[transitions.key] = entry
+ for index, entry in enumerate(
+ sorted(self._entries.values(),
+ key=lambda x: x[0],
+ reverse=True)):
+ entry[1] = index
def _map_index_to_pre_conditions(self, map_idx: int) -> str:
conditions = []
@@ -776,7 +808,7 @@ class TransitionMap:
f"{self._item.spec} is the first variant for "
f"{{{self._map_index_to_pre_conditions(map_idx)}}} "
"and it is not enabled by default")
- transition_map[map_idx].append(
+ transition_map[map_idx].add(
Transition(desc_idx, enabled_by, skip_post_cond[0],
pre_cond_na, post_cond))
@@ -786,7 +818,7 @@ class TransitionMap:
enabled_by = desc["enabled-by"]
for map_idx, transition in enumerate(transition_map):
if not transition:
- transition.append(
+ transition.add(
Transition(
desc_idx, enabled_by, skip_post_cond[0],
(0, ) * self._pre_co_count,
@@ -807,8 +839,7 @@ class TransitionMap:
raise ValueError(f"pre-condition '{condition['name']}' of "
f"{self._item.spec} has no states")
transition_count *= state_count
- transition_map = [list() for _ in range(transition_count)
- ] # type: _TransitionMap
+ transition_map = [_TransitionEntry() for _ in range(transition_count)]
for desc_idx, desc in enumerate(self["transition-map"]):
if isinstance(desc["post-conditions"], dict):
try:
@@ -833,25 +864,17 @@ class TransitionMap:
skip_post_cond)
return transition_map
- def _get_entry(self, variant: Transition) -> str:
- skip_pre_cond_na = (variant.skip, ) + variant.pre_cond_na
- for value in skip_pre_cond_na:
- if value != 0:
- text = "E( " + ", ".join(
- itertools.chain(
- map(str, skip_pre_cond_na),
- (self._post_co_idx_st_idx_to_st_name[co_idx][st_idx]
- for co_idx, st_idx in enumerate(variant.post_cond))))
- break
- else:
- text = "EZ( " + ", ".join(
- self._post_co_idx_st_idx_to_st_name[co_idx][st_idx]
- for co_idx, st_idx in enumerate(variant.post_cond))
+ def _get_entry(self, ident: str, variant: Transition) -> str:
+ text = "{ " + ", ".join(
+ itertools.chain(map(str, (variant.skip, ) + variant.pre_cond_na), (
+ (f"{ident}_Post_{self._post_co_idx_to_co_name[co_idx]}"
+ f"_{self._post_co_idx_st_idx_to_st_name[co_idx][st_idx]}")
+ for co_idx, st_idx in enumerate(variant.post_cond))))
wrapper = textwrap.TextWrapper()
wrapper.initial_indent = " "
- wrapper.subsequent_indent = " "
- wrapper.width = 75
- return "\n".join(wrapper.wrap(text)) + " ),"
+ wrapper.subsequent_indent = " "
+ wrapper.width = 79
+ return "\n".join(wrapper.wrap(text)) + " },"
def _get_entry_bits(self) -> int:
bits = self._pre_co_count + 1
@@ -859,42 +882,24 @@ class TransitionMap:
bits += math.ceil(math.log2(len(st_idx_to_st_name)))
return 2**max(math.ceil(math.log2(bits)), 3)
- def _add_entry_macro(self, content: CContent, ident: str, name: str,
- pre_count_0: int, pre_count_1: int) -> None:
- # pylint: disable=too-many-arguments
- entry = f"#define {name}( "
- entry += ", ".join(
- f"x{index}" for index in range(pre_count_0 + self._post_co_count))
- entry += ") { "
- entry += ", ".join(
- itertools.chain(
- (f"x{index}" for index in range(pre_count_0)),
- ("0" for index in range(pre_count_1)),
- (f"{ident}_Post_{condition['name']}_##x{pre_count_0 + co_idx}"
- for co_idx, condition in enumerate(self["post-conditions"]))))
- wrapper = textwrap.TextWrapper()
- wrapper.initial_indent = ""
- wrapper.subsequent_indent = " "
- wrapper.width = 77
- content.add(" \\\n".join(wrapper.wrap(entry)) + " }")
-
def add_map(self, content: CContent, ident: str) -> None:
""" Adds the transition map definitions to the content. """
entries = []
mapper = ExpressionMapper()
- for transistions in self._map:
- if len(transistions) == 1:
- entries.append(self._get_entry(transistions[0]))
+ for entry in sorted(self._entries.values(), key=lambda x: x[1]):
+ transitions = entry[2]
+ if len(transitions) == 1:
+ entries.append(self._get_entry(ident, transitions[0]))
else:
ifelse = "#if "
enumerators = [] # type: List[str]
- for variant in transistions[1:]:
+ for variant in transitions[1:]:
enumerators.append(
ifelse + enabled_by_to_exp(variant.enabled_by, mapper))
- enumerators.append(self._get_entry(variant))
+ enumerators.append(self._get_entry(ident, variant))
ifelse = "#elif "
enumerators.append("#else")
- enumerators.append(self._get_entry(transistions[0]))
+ enumerators.append(self._get_entry(ident, transitions[0]))
enumerators.append("#endif")
entries.append("\n".join(enumerators))
bits = self._get_entry_bits()
@@ -908,13 +913,21 @@ class TransitionMap:
content.append(
f"uint{bits}_t Post_{condition['name']} : {state_bits};")
content.add(f"}} {ident}_Entry;")
- pre_count = 1 + self._pre_co_count
- self._add_entry_macro(content, ident, "E", pre_count, 0)
- self._add_entry_macro(content, ident, "EZ", 0, pre_count)
- content.add([f"static const {ident}_Entry", f"{ident}_Map[] = {{"])
- entries[-1] = entries[-1].replace("),", ")")
+ content.add([f"static const {ident}_Entry", f"{ident}_Entries[] = {{"])
+ entries[-1] = entries[-1].replace("},", "}")
content.append(entries)
- content.append(["};", "", "#undef E", "#undef EZ"])
+ bits = math.ceil(math.log2(len(self._entries)) / 8) * 8
+ content.append(
+ ["};", "", f"static const uint{bits}_t", f"{ident}_Map[] = {{"])
+ text = ", ".join(
+ str(self._entries[transitions.key][1])
+ for transitions in self._map)
+ wrapper = textwrap.TextWrapper()
+ wrapper.initial_indent = " "
+ wrapper.subsequent_indent = " "
+ wrapper.width = 79
+ content.append(wrapper.wrap(text))
+ content.append("};")
def get_post_entry_member(self, co_idx: int) -> str:
"""
@@ -996,7 +1009,7 @@ class _ActionRequirementTestItem(_TestItem):
def _add_loop_body(self, content: CContent,
transition_map: TransitionMap) -> None:
- with content.condition(f"{self.ident}_Map[ index ].Skip"):
+ with content.condition("entry.Skip"):
content.append(["++index;", "continue;"])
content.add_blank_line()
self._add_call(content, "test-prepare", "Prepare")
@@ -1005,7 +1018,6 @@ class _ActionRequirementTestItem(_TestItem):
content.call_function(None, f"{enum[0]}_Prepare",
["ctx", f"ctx->pcs[ {index} ]"])
self._add_call(content, "test-action", "Action")
- content.append(f"entry = {self.ident}_Map[ index ];")
for index, enum in enumerate(self._post_co_idx_to_enum):
content.gap = False
content.call_function(None, f"{enum[0]}_Check", [
@@ -1022,11 +1034,10 @@ class _ActionRequirementTestItem(_TestItem):
end = self._pre_co_idx_to_enum[index][-1]
with content.for_loop(f"{var} = {begin}", f"{var} < {end}",
f"++{var}"):
- if index + 1 == self._pre_co_count:
- content.add(f"{self.ident}_Entry entry;")
name = self._item['pre-conditions'][index]["name"]
- pre_na = f"{self.ident}_Map[ index ].Pre_{name}_NA"
- with content.condition(pre_na):
+ content.call_function("entry =", f"{self.ident}_GetEntry",
+ ["index"])
+ with content.condition(f"entry.Pre_{name}_NA"):
content.append(f"{var} = {end};")
content.append(f"index += ( {end} - 1 )")
for index_2 in range(index + 1, self._pre_co_count):
@@ -1040,6 +1051,15 @@ class _ActionRequirementTestItem(_TestItem):
def _add_test_case(self, content: CContent, transition_map: TransitionMap,
header: Dict[str, Any]) -> None:
+ ret = f"static inline {self.ident}_Entry"
+ name = f"{self.ident}_GetEntry"
+ params = ["size_t index"]
+ with content.function(ret, name, params, align=True):
+ content.add([
+ f"return {self.ident}_Entries[",
+ f" {self.ident}_Map[ index ]", "];"
+ ])
+ entry = f"{self.ident}_Entry entry;"
fixture = f"{self.ident}_Fixture"
prologue = CContent()
epilogue = CContent()
@@ -1048,7 +1068,7 @@ class _ActionRequirementTestItem(_TestItem):
ret = "void"
name = f"{self.ident}_Run"
params = self._get_run_params(header)
- prologue.add([f"{self.context} *ctx;", "size_t index;"])
+ prologue.add([f"{self.context} *ctx;", entry, "size_t index;"])
prologue.call_function("ctx =", "T_push_fixture",
[f"&{self.ident}_Node", f"&{fixture}"])
prologue.add([
@@ -1066,7 +1086,7 @@ class _ActionRequirementTestItem(_TestItem):
name = "T_TEST_CASE_FIXTURE"
params = [f"{self.ident}", f"&{fixture}"]
prologue.add([
- f"{self.context} *ctx;", "size_t index;", "",
+ f"{self.context} *ctx;", entry, "size_t index;", "",
"ctx = T_fixture_context();", "ctx->in_action_loop = true;",
"index = 0;"
])
More information about the vc
mailing list