Re: [PATCH v3 5/5] perf metric: Don't compute unused events.

[Andi Kleen]

> +| 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);
> + }


Sorry, still not a fan of the having this nan code all over. It's just ugly.

If you don't want to do the syntax change to still do it in one pass,
and given building an AST would be a little complicated.

The original parser I based this code on actually had a byte code version too
(see attachment). With that one the lazy evaluation could be done on the byte 
code
level. Originally I didn't include it because it wasn't really
needed for perf, but presumably if we want to do more complicated
things it might be useful. 

In theory it could speed up performance slightly when an expression needs
to be computed multiple times in interval mode.

-Andi
#include 
#include 
#include 
#include 

#include "code.h"
#include "sym.h"
#include "error.h"

static unsigned char *bufs;
static unsigned bufl;
static unsigned char *bufp;

static void overflow(void)
{
yyerror("expression exceeds execution buffer");
}

void put_op(enum ops op)
{
if (bufp >= bufs + bufl)
overflow();
*bufp++ = op;
}

void put_long(enum ops op, long arg)
{
if (bufp + sizeof(long) + 1 >= bufs + bufl)
overflow();
*bufp++ = op;
memcpy(bufp, &arg, sizeof(long));
bufp += sizeof(long);
}

void put_ptr(enum ops op, void * arg)
{
if (bufp + sizeof(void *) + 1 >= bufs + bufl)
overflow();
*bufp++ = op;
memcpy(bufp, &arg, sizeof(void *));
bufp += sizeof(void *);
}

void start_def(struct symbol *s)
{
if (!s->undef)
yyerror("symbol %s redefined", s->name);
}

void end_def(struct symbol *s)
{
int len;

put_op(OP_RET);
len = bufp - bufs;
s->code = malloc(len);
memcpy(s->code, bufs, len);
bufp = bufs;
s->undef = 0;
}

static void execerror(char const *msg)
{
fprintf(stderr, "expression execution error: %s\n", msg);
exit(1);
}

#define STACKSIZE 16
#define CSTACKSIZE 16

long execute(unsigned char *bufp)
{
static void *target[] = {
[OP_END]= &&end,
[OP_EVENT]  = NULL,
[OP_NUMBER] = &&number,
[OP_PLUS]   = &&plus,
[OP_MINUS]  = &&minus,
[OP_MUL]= &&mul,
[OP_DIV]= &&div,
[OP_MOD]= &&mod,
[OP_NEGATE] = &&negate,
[OP_CALL]   = &&call,
[OP_RET]= &&ret,
[OP_XOR]= &&xor,
[OP_OR] = &&or,
[OP_NOT]= &¬,
[OP_AND]= &&and,
[OP_SHL]= &&shl,
[OP_SHR]= &&shr,
};
long a, b;
long stack[STACKSIZE];
int stackp = 0;
unsigned char *callstack[CSTACKSIZE];
int callstackp = 0;

#define getop(x) memcpy(&(x), bufp, sizeof(x)); bufp += sizeof(x)
#define push(x)  stack[stackp++] = (x)
#define pop()stack[--stackp]
#define next()   goto *target[(int)*bufp++]

next();

number:
if (stackp == STACKSIZE)
execerror("expression stack overflow");
getop(a);
push(a);
next();

#define OP(op) \
b = pop();  \
a = pop();  \
push(a op b);   \
next()

plus:   OP(+);
minus:  OP(-);
mul:OP(*);

div:
b = pop();
if (b == 0)
execerror("division by 0");
a = pop();
push(a / b);
next();

mod:
b = pop();
if (b == 0)
execerror("modulo by 0");
a = pop();
push(a % b);
next();

negate:
a = pop();
push(-a);
next();

and:OP(&);
or: OP(|);
xor:OP(^);
shl:OP(<<);
shr:OP(>>);

not:
a = pop();
push(~a);
next();

call:   {
struct symbol *s;
getop(s);
if (callstackp == CSTACKSIZE)
execerror("call stack overflow");
callstack[callstackp++] = bufp;
bufp = s->code;
next();
}

ret:
bufp = callstack[--callstackp];
next();

end:
assert(bufp == bufs || stackp == 1);
assert(callstackp == 0);
return stack[0];
}

#undef next
#unde

[PATCH v3 5/5] perf metric: Don't compute unused events.

[Ian Rogers]

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-irog...@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/per