For a metric like:
EVENT1 if #smt_on else EVENT2
currently EVENT1 and EVENT2 will be measured and then when the metric
is reported EVENT1 or EVENT2 will be printed depending on the value
from smt_on() during the expr parsing. Computing both events is
unnecessary and can lead to multiplexing as discussed in this thread:
https://lore.kernel.org/lkml/[email protected]/
This change modifies expression parsing so that constants are
considered when building the set of ids (events) and only events not
contributing to a constant value are measured.
Ian Rogers (5):
perf metric: Restructure struct expr_parse_ctx.
perf metric: Use NAN for missing event IDs.
perf metric: Rename expr__find_other.
perf metric: Add utilities to work on ids map.
perf metric: Don't compute unused events.
tools/perf/tests/expr.c | 148 ++++++++++-----
tools/perf/tests/pmu-events.c | 42 +++--
tools/perf/util/expr.c | 136 ++++++++++++--
tools/perf/util/expr.h | 17 +-
tools/perf/util/expr.l | 9 -
tools/perf/util/expr.y | 343 +++++++++++++++++++++++++++-------
tools/perf/util/metricgroup.c | 44 +++--
tools/perf/util/stat-shadow.c | 54 ++++--
8 files changed, 586 insertions(+), 207 deletions(-)
--
2.29.2.299.gdc1121823c-goog
For a metric like:
EVENT1 if #smt_on else EVENT2
currently EVENT1 and EVENT2 will be measured and then when the metric is
reported EVENT1 or EVENT2 will be printed depending on the value from
smt_on() during the expr parsing. Computing both events is unnecessary and
can lead to multiplexing as discussed in this thread:
https://lore.kernel.org/lkml/[email protected]/
This change modifies the expression parsing code by:
- getting rid of the "other" parsing and introducing a boolean argument
to say whether ids should be computed or not.
- expressions are changed so that a pair of value and ids are returned.
- when computing the metric value the ids are unused.
- when computing the ids, constant values and smt_on are assigned to
the value.
- If the value is from an event ID then the event is added to the ids
hashmap and the value set to NAN.
- Typically operators union IDs for their inputs and set the value to
NAN, however, if the inputs are constant then these are computed and
propagated as the value.
- If the input is constant to certain operators like:
IDS1 if CONST else IDS2
then the result will be either IDS1 or IDS2 depending on CONST which
may be evaluated from an entire expression.
- The ids at the end of parsing are added to the context.
Signed-off-by: Ian Rogers <[email protected]>
---
tools/perf/tests/expr.c | 10 ++
tools/perf/util/expr.c | 9 +-
tools/perf/util/expr.h | 1 -
tools/perf/util/expr.l | 9 --
tools/perf/util/expr.y | 341 +++++++++++++++++++++++++++++++---------
5 files changed, 284 insertions(+), 86 deletions(-)
diff --git a/tools/perf/tests/expr.c b/tools/perf/tests/expr.c
index 7c2a01cf0650..94ddd01b29fc 100644
--- a/tools/perf/tests/expr.c
+++ b/tools/perf/tests/expr.c
@@ -1,6 +1,7 @@
// SPDX-License-Identifier: GPL-2.0
#include "util/debug.h"
#include "util/expr.h"
+#include "util/smt.h"
#include "tests.h"
#include <stdlib.h>
#include <string.h>
@@ -132,6 +133,15 @@ int test__expr(struct test *t __maybe_unused, int subtest __maybe_unused)
TEST_ASSERT_VAL("find other", hashmap__find(ctx->ids, "EVENT2,param=3/",
(void **)&val_ptr));
+ expr__ctx_clear(ctx);
+ TEST_ASSERT_VAL("find ids",
+ expr__find_ids("EVENT1 if #smt_on else EVENT2",
+ NULL, ctx, 0) == 0);
+ TEST_ASSERT_VAL("find ids", hashmap__size(ctx->ids) == 1);
+ TEST_ASSERT_VAL("find ids", hashmap__find(ctx->ids,
+ smt_on() ? "EVENT1" : "EVENT2",
+ (void **)&val_ptr));
+
expr__ctx_free(ctx);
return 0;
diff --git a/tools/perf/util/expr.c b/tools/perf/util/expr.c
index d4e83439c965..8c62a6c83b00 100644
--- a/tools/perf/util/expr.c
+++ b/tools/perf/util/expr.c
@@ -293,10 +293,9 @@ void expr__ctx_free(struct expr_parse_ctx *ctx)
static int
__expr__parse(double *val, struct expr_parse_ctx *ctx, const char *expr,
- int start, int runtime)
+ bool compute_ids, int runtime)
{
struct expr_scanner_ctx scanner_ctx = {
- .start_token = start,
.runtime = runtime,
};
YY_BUFFER_STATE buffer;
@@ -316,7 +315,7 @@ __expr__parse(double *val, struct expr_parse_ctx *ctx, const char *expr,
expr_set_debug(1, scanner);
#endif
- ret = expr_parse(val, ctx, scanner);
+ ret = expr_parse(val, ctx, compute_ids, scanner);
expr__flush_buffer(buffer, scanner);
expr__delete_buffer(buffer, scanner);
@@ -327,13 +326,13 @@ __expr__parse(double *val, struct expr_parse_ctx *ctx, const char *expr,
int expr__parse(double *final_val, struct expr_parse_ctx *ctx,
const char *expr, int runtime)
{
- return __expr__parse(final_val, ctx, expr, EXPR_PARSE, runtime) ? -1 : 0;
+ return __expr__parse(final_val, ctx, expr, /*compute_ids=*/false, runtime) ? -1 : 0;
}
int expr__find_ids(const char *expr, const char *one,
struct expr_parse_ctx *ctx, int runtime)
{
- int ret = __expr__parse(NULL, ctx, expr, EXPR_OTHER, runtime);
+ int ret = __expr__parse(NULL, ctx, expr, /*compute_ids=*/true, runtime);
if (one)
expr__del_id(ctx, one);
diff --git a/tools/perf/util/expr.h b/tools/perf/util/expr.h
index 398b2629beee..4e77b43ce94c 100644
--- a/tools/perf/util/expr.h
+++ b/tools/perf/util/expr.h
@@ -38,7 +38,6 @@ struct expr_id_data {
};
struct expr_scanner_ctx {
- int start_token;
int runtime;
};
diff --git a/tools/perf/util/expr.l b/tools/perf/util/expr.l
index 13e5e3c75f56..702fdf6456ca 100644
--- a/tools/perf/util/expr.l
+++ b/tools/perf/util/expr.l
@@ -91,15 +91,6 @@ symbol ({spec}|{sym})+
%%
struct expr_scanner_ctx *sctx = expr_get_extra(yyscanner);
- {
- int start_token = sctx->start_token;
-
- if (sctx->start_token) {
- sctx->start_token = 0;
- return start_token;
- }
- }
-
d_ratio { return D_RATIO; }
max { return MAX; }
min { return MIN; }
diff --git a/tools/perf/util/expr.y b/tools/perf/util/expr.y
index 4ce76adeb337..05b865413389 100644
--- a/tools/perf/util/expr.y
+++ b/tools/perf/util/expr.y
@@ -10,34 +10,29 @@
#include "expr.h"
#include "smt.h"
#include <string.h>
-
-static double d_ratio(double val0, double val1)
-{
- if (val1 == 0) {
- return 0;
- }
- return val0 / val1;
-}
-
%}
%define api.pure full
%parse-param { double *final_val }
%parse-param { struct expr_parse_ctx *ctx }
+%parse-param { bool compute_ids }
%parse-param {void *scanner}
%lex-param {void* scanner}
%union {
double num;
char *str;
+ struct ids {
+ /* When creating ids, holds the working set of event ids. */
+ struct hashmap *ids;
+ /* The metric value. When computing ids NAN is used to indicate
+ * that all event ids are necessary. */
+ double val;
+ } ids;
}
-%token EXPR_PARSE EXPR_OTHER EXPR_ERROR
-%token <num> NUMBER
-%token <str> ID
-%destructor { free ($$); } <str>
-%token MIN MAX IF ELSE SMT_ON D_RATIO
+%token ID NUMBER MIN MAX IF ELSE SMT_ON D_RATIO EXPR_ERROR
%left MIN MAX IF
%left '|'
%left '^'
@@ -46,11 +41,16 @@ static double d_ratio(double val0, double val1)
%left '-' '+'
%left '*' '/' '%'
%left NEG NOT
-%type <num> expr if_expr
+%type <num> NUMBER
+%type <str> ID
+%destructor { free ($$); } <str>
+%type <ids> expr if_expr
+%destructor { ids__free($$.ids); } <ids>
%{
static void expr_error(double *final_val __maybe_unused,
struct expr_parse_ctx *ctx __maybe_unused,
+ bool compute_ids __maybe_unused,
void *scanner,
const char *s)
{
@@ -60,68 +60,267 @@ static void expr_error(double *final_val __maybe_unused,
%}
%%
-start:
-EXPR_PARSE all_expr
-|
-EXPR_OTHER all_other
+start: if_expr
+{
+ if (compute_ids)
+ ctx->ids = ids__union($1.ids, ctx->ids);
-all_other: all_other other
-|
+ if (final_val)
+ *final_val = $1.val;
+}
+;
-other: ID
+if_expr: expr IF expr ELSE expr
{
- expr__add_id(ctx, $1);
+ if (fpclassify($3.val) == FP_ZERO) {
+ $$.val = $5.val;
+ $$.ids = $5.ids;
+ ids__free($1.ids);
+ ids__free($3.ids);
+ } else if (isfinite($3.val)) {
+ $$.val = $1.val;
+ $$.ids = $1.ids;
+ ids__free($3.ids);
+ ids__free($5.ids);
+ } else if (!compute_ids) {
+ $$.val = $5.val;
+ $$.ids = NULL;
+ } else {
+ $$.ids = ids__union(ids__union($1.ids, $3.ids), $5.ids);
+ $$.val = NAN;
+ }
}
-|
-MIN | MAX | IF | ELSE | SMT_ON | NUMBER | '|' | '^' | '&' | '-' | '+' | '*' | '/' | '%' | '(' | ')' | ','
-|
-'<' | '>' | D_RATIO
-
-all_expr: if_expr { *final_val = $1; }
- ;
-
-if_expr:
- expr IF expr ELSE expr { $$ = $3 ? $1 : $5; }
- | expr
- ;
+| expr
+;
-expr: NUMBER
- | ID {
- struct expr_id_data *data;
+expr: NUMBER
+{
+ $$.val = $1;
+ $$.ids = NULL;
+}
+| ID
+{
+ if (!compute_ids) {
+ struct expr_id_data *data;
- if (expr__resolve_id(ctx, $1, &data)) {
- $$ = NAN;
- }
+ $$.val = NAN;
+ if (expr__resolve_id(ctx, $1, &data) == 0)
+ $$.val = data->val;
- $$ = data->val;
- free($1);
- }
- | expr '|' expr { $$ = (long)$1 | (long)$3; }
- | expr '&' expr { $$ = (long)$1 & (long)$3; }
- | expr '^' expr { $$ = (long)$1 ^ (long)$3; }
- | expr '<' expr { $$ = $1 < $3; }
- | expr '>' expr { $$ = $1 > $3; }
- | expr '+' expr { $$ = $1 + $3; }
- | expr '-' expr { $$ = $1 - $3; }
- | expr '*' expr { $$ = $1 * $3; }
- | expr '/' expr { if ($3 == 0) {
- pr_debug("division by zero\n");
- YYABORT;
- }
- $$ = $1 / $3;
- }
- | expr '%' expr { if ((long)$3 == 0) {
- pr_debug("division by zero\n");
- YYABORT;
- }
- $$ = (long)$1 % (long)$3;
- }
- | '-' expr %prec NEG { $$ = -$2; }
- | '(' if_expr ')' { $$ = $2; }
- | MIN '(' expr ',' expr ')' { $$ = $3 < $5 ? $3 : $5; }
- | MAX '(' expr ',' expr ')' { $$ = $3 > $5 ? $3 : $5; }
- | SMT_ON { $$ = smt_on() > 0; }
- | D_RATIO '(' expr ',' expr ')' { $$ = d_ratio($3,$5); }
- ;
+ $$.ids = NULL;
+ free($1);
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__new();
+ if (!$$.ids || ids__insert($$.ids, $1, ctx->parent))
+ YYABORT;
+ }
+}
+| expr '|' expr
+{
+ if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) {
+ $$.val = (long)$1.val | (long)$3.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($1.ids);
+ ids__free($3.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($1.ids, $3.ids);
+ }
+}
+| expr '&' expr
+{
+ if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) {
+ $$.val = (long)$1.val & (long)$3.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($1.ids);
+ ids__free($3.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($1.ids, $3.ids);
+ }
+}
+| expr '^' expr
+{
+ if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) {
+ $$.val = (long)$1.val ^ (long)$3.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($1.ids);
+ ids__free($3.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($1.ids, $3.ids);
+ }
+}
+| expr '<' expr
+{
+ if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) {
+ $$.val = $1.val < $3.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($1.ids);
+ ids__free($3.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($1.ids, $3.ids);
+ }
+}
+| expr '>' expr
+{
+ if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) {
+ $$.val = $1.val > $3.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($1.ids);
+ ids__free($3.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($1.ids, $3.ids);
+ }
+}
+| expr '+' expr
+{
+ if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) {
+ $$.val = $1.val + $3.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($1.ids);
+ ids__free($3.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($1.ids, $3.ids);
+ }
+}
+| expr '-' expr
+{
+ if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) {
+ $$.val = $1.val - $3.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($1.ids);
+ ids__free($3.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($1.ids, $3.ids);
+ }
+}
+| expr '*' expr
+{
+ if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) {
+ $$.val = $1.val * $3.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($1.ids);
+ ids__free($3.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($1.ids, $3.ids);
+ }
+}
+| expr '/' expr
+{
+ if (fpclassify($3.val) == FP_ZERO) {
+ pr_debug("division by zero\n");
+ YYABORT;
+ } else if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) {
+ $$.val = $1.val / $3.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($1.ids);
+ ids__free($3.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($1.ids, $3.ids);
+ }
+}
+| D_RATIO '(' expr ',' expr ')'
+{
+ if (fpclassify($5.val) == FP_ZERO) {
+ $$.val = 0.0;
+ $$.ids = NULL;
+ ids__free($3.ids);
+ ids__free($5.ids);
+ } else if (!compute_ids || (isfinite($3.val) && isfinite($5.val))) {
+ $$.val = $3.val / $5.val;
+ $$.ids = NULL;
+ ids__free($3.ids);
+ ids__free($5.ids);
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($3.ids, $5.ids);
+ }
+}
+| expr '%' expr
+{
+ if (fpclassify($3.val) == FP_ZERO) {
+ pr_debug("division by zero\n");
+ YYABORT;
+ } else if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) {
+ $$.val = (long)$1.val % (long)$3.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($1.ids);
+ ids__free($3.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($1.ids, $3.ids);
+ }
+}
+| '-' expr %prec NEG
+{
+ $$.val = -$2.val;
+ $$.ids = $2.ids;
+}
+| '(' if_expr ')'
+{
+ $$ = $2;
+}
+| MIN '(' expr ',' expr ')'
+{
+ if (!compute_ids || (isfinite($3.val) && isfinite($5.val))) {
+ $$.val = $3.val < $5.val ? $3.val : $5.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($3.ids);
+ ids__free($5.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($3.ids, $5.ids);
+ }
+}
+| MAX '(' expr ',' expr ')'
+{
+ if (!compute_ids || (isfinite($3.val) && isfinite($5.val))) {
+ $$.val = $3.val > $5.val ? $3.val : $5.val;
+ $$.ids = NULL;
+ if (compute_ids) {
+ ids__free($3.ids);
+ ids__free($5.ids);
+ }
+ } else {
+ $$.val = NAN;
+ $$.ids = ids__union($3.ids, $5.ids);
+ }
+}
+| SMT_ON
+{
+ $$.val = smt_on() > 0 ? 1.0 : 0.0;
+ $$.ids = NULL;
+}
+;
%%
--
2.29.2.299.gdc1121823c-goog
The patch does a lot of stuff and is hard to review.
The earlier patches all look good to me.
>
> static int
> __expr__parse(double *val, struct expr_parse_ctx *ctx, const char *expr,
> - int start, int runtime)
> + bool compute_ids, int runtime)
> {
> struct expr_scanner_ctx scanner_ctx = {
> - .start_token = start,
Okay so why do we not need that anymore?
This should probably be a separate change.
I'm not sure about the NaN handling. Why can't you use some
other value (perhaps 0 with some special case for division)
After all the computed values of the dead branch shouldn't
be used anyways, so I don't think we need the extra NaN
ceremony everywhere.
The only thing that really matters is to track that the event
is not added and not resolved.
I think it would be a lot simpler if we changed the IF syntax.
The problem right now is that the condition is after the first
expression, so you can't use global state with an early reduction
to track if the if branch is dead or not.
If we used the C style cond ? a : b it could be
cond { set flag } '?' expr { reset flag } : expr { reset flag }
scanner checks flag and ignores the event if false
This would need changing the JSON files but that should be easy enough
with a script.
Or maybe at some point need to bite the bullet and build
an AST, but for now we probably can get away of not doing it.
-Andi