From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-26.3 required=3.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, USER_AGENT_GIT,USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id DFE8EC64E7C for ; Sat, 21 Nov 2020 03:11:45 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id BDE18223FD for ; Sat, 21 Nov 2020 03:11:45 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="lsF+0iSc" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727444AbgKUDLf (ORCPT ); Fri, 20 Nov 2020 22:11:35 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37708 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727423AbgKUDLd (ORCPT ); Fri, 20 Nov 2020 22:11:33 -0500 Received: from mail-pf1-x449.google.com (mail-pf1-x449.google.com [IPv6:2607:f8b0:4864:20::449]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 566E0C061A47 for ; Fri, 20 Nov 2020 19:11:33 -0800 (PST) Received: by mail-pf1-x449.google.com with SMTP id a24so8467143pfo.3 for ; Fri, 20 Nov 2020 19:11:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=sender:date:in-reply-to:message-id:mime-version:references:subject :from:to:cc; bh=QjIzsr3Sehmkc2TdWVcrCBlT+B5+tP7u62kKjGb72rM=; b=lsF+0iSc1725jkvE+oPZQUj+/LX0xPiR3ZeN7rBFUjphKQYn9ZuCXYsDuz25+k/W3O Qh3C819RdjQBXHcf0eLtT21ZmwkKYVU8Fnesqid07QfAUmQ6Pb41u67PX6dZuUwtTOXl RT6j7SBRYW09SIloICjI8dd9w4lDIDhX7F+JnBMaLBQZPRcdn5XXh7CVQmNsQ7qA3hsp cGOIr6LPUxEOR5WfUdGsMTdMzT5l8Nbq4JTqpMgULKSwqC71/6zLvym5eOEOWg5dZpN9 ybs54xxGaBbC7Scem9ivaPhZ2xSk2vLfvtqf5YFFJBMhciY/7dXE3F5sHjbEZZCriqDM Ow7w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=QjIzsr3Sehmkc2TdWVcrCBlT+B5+tP7u62kKjGb72rM=; b=r63iOFPJHI+Gl0fZuHa84uu3CKlo63Uedx2DRzSokkJg0Kz05MrczR7tXY68WjdX2+ Vrd1CKUhmmUoTHUfipr8U/SpbvB5U025ENaPKsMbYB872UkSX2YJ4YIUASsj4MFITZc0 k/qWALlvfHqReNg8gfLUA9SuvyFD7qo2kIBplPkPLDLzcaqJvwjD2Xew1ExGnno+TqWI p+0+EPgBo1HjJEQsrcsXsnnN/3pQxzn5p7iroMzx/HvQL5ogJymVmqUYcJE5N1Pt2aiv lpsUJUkmNl8lwpBy39poyQbKaZPmE/a+zZS4RW20qyzByn5QGgq7ZfMkd1CUmc2+BF+3 CfZA== X-Gm-Message-State: AOAM531H72RqciD2FoIEp+SqWhzrd6bpteDmIo3wXeT0zURr428cqwiu J+oLgEbQkNC1zZ9IvGA/YwhN5eujwAM/ X-Google-Smtp-Source: ABdhPJzdfhj+2uKZobM6ftDJrihixmL9V+TCb5Y9sbxW521vO8iACiV5WVJAEmC4vFsSw8SIcsP7PIhXLXBt Sender: "irogers via sendgmr" X-Received: from irogers.svl.corp.google.com ([2620:15c:2cd:2:f693:9fff:fef4:4583]) (user=irogers job=sendgmr) by 2002:a63:8c7:: with SMTP id 190mr19430078pgi.366.1605928292823; Fri, 20 Nov 2020 19:11:32 -0800 (PST) Date: Fri, 20 Nov 2020 19:11:19 -0800 In-Reply-To: <20201121031119.3554769-1-irogers@google.com> Message-Id: <20201121031119.3554769-6-irogers@google.com> Mime-Version: 1.0 References: <20201121031119.3554769-1-irogers@google.com> X-Mailer: git-send-email 2.29.2.454.gaff20da3a2-goog Subject: [PATCH v3 5/5] perf metric: Don't compute unused events. From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Mark Rutland , Alexander Shishkin , Jiri Olsa , Namhyung Kim , linux-kernel@vger.kernel.org, Andi Kleen , Jin Yao , John Garry , Paul Clarke , kajoljain Cc: Stephane Eranian , Sandeep Dasgupta , linux-perf-users@vger.kernel.org, Ian Rogers Content-Type: text/plain; charset="UTF-8" Precedence: bulk List-ID: X-Mailing-List: linux-perf-users@vger.kernel.org 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/20201110100346.2527031-1-irogers@google.com/ 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), and so IDS1 or IDS2 may be discarded avoiding events from being programmed. - The ids at the end of parsing are added to the context. Signed-off-by: Ian Rogers --- tools/perf/tests/expr.c | 17 ++ tools/perf/util/expr.c | 9 +- tools/perf/util/expr.h | 1 - tools/perf/util/expr.l | 9 - tools/perf/util/expr.y | 373 ++++++++++++++++++++++++++++++++-------- 5 files changed, 319 insertions(+), 90 deletions(-) diff --git a/tools/perf/tests/expr.c b/tools/perf/tests/expr.c index 1c881bea7fca..5cab5960b257 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 #include @@ -132,6 +133,22 @@ int test__expr(struct test *t __maybe_unused, int subtest __maybe_unused) TEST_ASSERT_VAL("find ids", hashmap__find(ctx->ids, "EVENT2,param=3/", (void **)&val_ptr)); + /* Only EVENT1 or EVENT2 need be measured depending on the value of smt_on. */ + 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)); + + /* The expression is a constant 1.0 without needing to evaluate EVENT1. */ + expr__ctx_clear(ctx); + TEST_ASSERT_VAL("find ids", + expr__find_ids("1.0 if EVENT1 > 100.0 else 1.0", + NULL, ctx, 0) == 0); + TEST_ASSERT_VAL("find ids", hashmap__size(ctx->ids) == 0); expr__ctx_free(ctx); return 0; diff --git a/tools/perf/util/expr.c b/tools/perf/util/expr.c index 1adb6cd202e0..28aaa50c6c68 100644 --- a/tools/perf/util/expr.c +++ b/tools/perf/util/expr.c @@ -329,10 +329,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; @@ -352,7 +351,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); @@ -363,13 +362,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 62d3ae5ddfba..cefeb2c8d85e 100644 --- a/tools/perf/util/expr.h +++ b/tools/perf/util/expr.h @@ -26,7 +26,6 @@ struct expr_parse_ctx { 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 41c9cd4efadd..7355beafb874 100644 --- a/tools/perf/util/expr.y +++ b/tools/perf/util/expr.y @@ -1,43 +1,45 @@ /* Simple expression parser */ %{ #define YYDEBUG 1 +#include #include -#include -#include "util.h" #include "util/debug.h" -#include // strtod() +#include "smt.h" #define IN_EXPR_Y 1 #include "expr.h" -#include "smt.h" -#include - -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 not creating ids this is the value + * read from a counter, a constant or some computed value. When + * creating ids the value is either a constant or NAN. NAN is + * used as a special "set of all values" case. Consider: + * 1.0 if event1 > 50.0 else 2.0 + * The set of values {1.0, 2.0} is possible from this + * expression, but we conservatively use NAN to say any value is + * possible. By tracking constants an expression like: + * 1.0 if event1 > 50.0 else 1.0 + * can avoid computing event1. + */ + double val; + } ids; } -%token EXPR_PARSE EXPR_OTHER EXPR_ERROR -%token NUMBER -%token ID -%destructor { free ($$); } -%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 +48,16 @@ static double d_ratio(double val0, double val1) %left '-' '+' %left '*' '/' '%' %left NEG NOT -%type expr if_expr +%type NUMBER +%type ID +%destructor { free ($$); } +%type expr if_expr +%destructor { ids__free($$.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,67 +67,283 @@ 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) { + /* + * The IF expression evaluated to 0 so treat as false, take the + * ELSE and discard everything else. + */ + $$.val = $5.val; + $$.ids = $5.ids; + ids__free($1.ids); + ids__free($3.ids); + } else if (!compute_ids || isfinite($3.val)) { + /* The expression is true, NAN, etc. */ + $$.val = $1.val; + $$.ids = $1.ids; + ids__free($3.ids); + ids__free($5.ids); + } else if ($1.val == $5.val) { + /* LHS == RHS, and not NAN, so no need to evaluate expr. */ + $$.ids = ids__union($1.ids, $5.ids); + $$.val = NAN; + } else { + /* + * Value is either the LHS, RHS and we need the IF expression to + * compute it. + */ + $$.ids = ids__union(ids__union($1.ids, $3.ids), $5.ids); + $$.val = NAN; + } } -| -MIN | MAX | IF | ELSE | SMT_ON | NUMBER | '|' | '^' | '&' | '-' | '+' | '*' | '/' | '%' | '(' | ')' | ',' -| -'<' | '>' | D_RATIO +| expr +; -all_expr: if_expr { *final_val = $1; } - ; - -if_expr: - expr IF expr ELSE expr { $$ = $3 ? $1 : $5; } - | expr - ; - -expr: NUMBER - | ID { - struct expr_id_data *data; +expr: NUMBER +{ + $$.val = $1; + $$.ids = NULL; +} +| ID +{ + if (!compute_ids) { + /* + * Compute the event's value from ID. If the ID isn't known then + * it isn't used to compute the formula so set to NAN. + */ + struct expr_id_data *data; - $$ = NAN; - if (expr__resolve_id(ctx, $1, &data) == 0) - $$ = expr_id_data__value(data); + $$.val = NAN; + if (expr__resolve_id(ctx, $1, &data) == 0) + $$.val = expr_id_data__value(data); - 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 { + /* + * Set the value to NAN to show that any value is possible when + * the event is computed. Create a set of just the ID. + */ + $$.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))) { + assert($1.ids == NULL); + assert($3.ids == NULL); + $$.val = (long)$1.val | (long)$3.val; + $$.ids = NULL; + } else { + /* + * LHS or RHS needs to be computed from event IDs, consequently + * so does this expression. Set val to NAN to show that the set + * of all values is possible, the events are the union of those + * on the LHS and RHS. + */ + $$.val = NAN; + $$.ids = ids__union($1.ids, $3.ids); + } +} +| expr '&' expr +{ + if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) { + assert($1.ids == NULL); + assert($3.ids == NULL); + $$.val = (long)$1.val & (long)$3.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.val = NAN; + $$.ids = ids__union($1.ids, $3.ids); + } +} +| expr '^' expr +{ + if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) { + assert($1.ids == NULL); + assert($3.ids == NULL); + $$.val = (long)$1.val ^ (long)$3.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.val = NAN; + $$.ids = ids__union($1.ids, $3.ids); + } +} +| expr '<' expr +{ + if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) { + assert($1.ids == NULL); + assert($3.ids == NULL); + $$.val = $1.val < $3.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.val = NAN; + $$.ids = ids__union($1.ids, $3.ids); + } +} +| expr '>' expr +{ + if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) { + assert($1.ids == NULL); + assert($3.ids == NULL); + $$.val = $1.val > $3.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.val = NAN; + $$.ids = ids__union($1.ids, $3.ids); + } +} +| expr '+' expr +{ + if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) { + assert($1.ids == NULL); + assert($3.ids == NULL); + $$.val = $1.val + $3.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.val = NAN; + $$.ids = ids__union($1.ids, $3.ids); + } +} +| expr '-' expr +{ + if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) { + assert($1.ids == NULL); + assert($3.ids == NULL); + $$.val = $1.val - $3.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.val = NAN; + $$.ids = ids__union($1.ids, $3.ids); + } +} +| expr '*' expr +{ + if (!compute_ids || (isfinite($1.val) && isfinite($3.val))) { + assert($1.ids == NULL); + assert($3.ids == NULL); + $$.val = $1.val * $3.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.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))) { + assert($1.ids == NULL); + assert($3.ids == NULL); + $$.val = $1.val / $3.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.val = NAN; + $$.ids = ids__union($1.ids, $3.ids); + } +} +| D_RATIO '(' expr ',' expr ')' +{ + if (fpclassify($5.val) == FP_ZERO) { + /* + * Division by constant zero always yields zero and no events + * are necessary. + */ + assert($5.ids == NULL); + $$.val = 0.0; + $$.ids = NULL; + ids__free($3.ids); + } else if (!compute_ids || (isfinite($3.val) && isfinite($5.val))) { + assert($3.ids == NULL); + assert($5.ids == NULL); + $$.val = $3.val / $5.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.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))) { + assert($1.ids == NULL); + assert($3.ids == NULL); + $$.val = (long)$1.val % (long)$3.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.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))) { + assert($3.ids == NULL); + assert($5.ids == NULL); + $$.val = $3.val < $5.val ? $3.val : $5.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.val = NAN; + $$.ids = ids__union($3.ids, $5.ids); + } +} +| MAX '(' expr ',' expr ')' +{ + if (!compute_ids || (isfinite($3.val) && isfinite($5.val))) { + assert($3.ids == NULL); + assert($5.ids == NULL); + $$.val = $3.val > $5.val ? $3.val : $5.val; + $$.ids = NULL; + } else { + /* LHS and/or RHS need computing from event IDs so union. */ + $$.val = NAN; + $$.ids = ids__union($3.ids, $5.ids); + } +} +| SMT_ON +{ + $$.val = smt_on() > 0 ? 1.0 : 0.0; + $$.ids = NULL; +} +; %% -- 2.29.2.454.gaff20da3a2-goog