p4c: parser duplicated matches not optimized out
As title says, duplicated matches 0x0800 are not optimized out.
header_type h_t {
fields {
f : 16;
}
}
header h_t a;
header h_t b;
parser start {
extract(a);
return select(latest.f) {
0x0800 : parse_b;
0x0800 : parse_b;
default : ingress;
}
}
parser parse_b {
extract(b);
return ingress;
}
control ingress { }
FrontEndLast:
@name(".start") state start {
packet.extract<h_t>(hdr.a);
transition select(hdr.a.f) {
16w0x800: parse_b;
16w0x800: parse_b;
default: accept;
}
}
It would also be nice to give a warning of duplicated matches.
About this issue
- Original URL
- State: open
- Created 5 years ago
- Comments: 19 (18 by maintainers)
Commits related to this issue
- Fix: Issue #2004 parser duplicated matches not optimized out This fix contains solution for overlaping constant and range labels inside SelectExpression. For example: 3 : accept; 0x3: reject; (This... — committed to DarinkaNesovic/p4c by DarinkaNesovic 4 years ago
- Fix: Issue #2004 parser duplicated matches not optimized out This fix contains solution for overlaping constant and range labels inside SelectExpression. For example: 3 : accept; 0x3: reject; (This... — committed to DarinkaNesovic/p4c by DarinkaNesovic 4 years ago
- Fix: Issue #2004 parser duplicated matches not optimized out This fix contains solution for overlaping constant and range labels inside SelectExpression. For example: 3 : accept; 0x3: reject; (This... — committed to DarinkaNesovic/p4c by DarinkaNesovic 4 years ago
- Fix: Issue #2004 parser duplicated matches not optimized out This fix contains solution for overlaping constant and range labels inside SelectExpression. For example: 3 : accept; 0x3: reject; (This... — committed to DarinkaNesovic/p4c by DarinkaNesovic 4 years ago
- Fix: Issue #2004 parser duplicated matches not optimized out This fix contains solution for overlaping constant and range labels inside SelectExpression. For example: 3 : accept; 0x3: reject; (This... — committed to DarinkaNesovic/p4c by DarinkaNesovic 4 years ago
What do you mean by “error”? The spec allows arbitrary labels and evaluates them from top to bottom. It is fine for labels to describe overlapping sets or for labels to never be matched dynamically. Some cases could be optimized away, but as you saw in the discussion, the general problem is hard.
If you want to create a check that a single simpleKeySetExpression is a subset of any one of the preceding M-1 simpleKeySetExpression, that takes O(M) time, and checking all pairs takes O(N^2) time for a list of N simpleKeySetExpressions.
If you want to check whether a single simpleKeySetExpression is a subset of the union of the preceding M-1 simpleKeySetExpression, then you are solving SAT to do that, in general.