tools/perf/util/expr.y

   1 /* Simple expression parser */
   2 %{
   3 #define YYDEBUG 1
   4 #include <assert.h>
   5 #include <math.h>
   6 #include <stdlib.h>
   7 #include "util/debug.h"
   8 #define IN_EXPR_Y 1
   9 #include "expr.h"
  10 %}
  11
  12 %define api.pure full
  13
  14 %parse-param { double *final_val }
  15 %parse-param { struct expr_parse_ctx *ctx }
  16 %parse-param { bool compute_ids }
  17 %parse-param {void *scanner}
  18 %lex-param {void* scanner}
  19
  20 %union {
  21         double   num;
  22         char    *str;
  23         struct ids {
  24                 /*
  25                  * When creating ids, holds the working set of event ids. NULL
  26                  * implies the set is empty.
  27                  */
  28                 struct hashmap *ids;
  29                 /*
  30                  * The metric value. When not creating ids this is the value
  31                  * read from a counter, a constant or some computed value. When
  32                  * creating ids the value is either a constant or BOTTOM. NAN is
  33                  * used as the special BOTTOM value, representing a "set of all
  34                  * values" case.
  35                  */
  36                 double val;
  37         } ids;
  38 }
  39
  40 %token ID NUMBER MIN MAX IF ELSE LITERAL D_RATIO SOURCE_COUNT EXPR_ERROR
  41 %left MIN MAX IF
  42 %left '|'
  43 %left '^'
  44 %left '&'
  45 %left '<' '>'
  46 %left '-' '+'
  47 %left '*' '/' '%'
  48 %left NEG NOT
  49 %type <num> NUMBER LITERAL
  50 %type <str> ID
  51 %destructor { free ($$); } <str>
  52 %type <ids> expr if_expr
  53 %destructor { ids__free($$.ids); } <ids>
  54
  55 %{
  56 static void expr_error(double *final_val __maybe_unused,
  57                        struct expr_parse_ctx *ctx __maybe_unused,
  58                        bool compute_ids __maybe_unused,
  59                        void *scanner,
  60                        const char *s)
  61 {
  62         pr_debug("%s\n", s);
  63 }
  64
  65 /*
  66  * During compute ids, the special "bottom" value uses NAN to represent the set
  67  * of all values. NAN is selected as it isn't a useful constant value.
  68  */
  69 #define BOTTOM NAN
  70
  71 /* During computing ids, does val represent a constant (non-BOTTOM) value? */
  72 static bool is_const(double val)
  73 {
  74         return isfinite(val);
  75 }
  76
  77 static struct ids union_expr(struct ids ids1, struct ids ids2)
  78 {
  79         struct ids result = {
  80                 .val = BOTTOM,
  81                 .ids = ids__union(ids1.ids, ids2.ids),
  82         };
  83         return result;
  84 }
  85
  86 static struct ids handle_id(struct expr_parse_ctx *ctx, char *id,
  87                             bool compute_ids, bool source_count)
  88 {
  89         struct ids result;
  90
  91         if (!compute_ids) {
  92                 /*
  93                  * Compute the event's value from ID. If the ID isn't known then
  94                  * it isn't used to compute the formula so set to NAN.
  95                  */
  96                 struct expr_id_data *data;
  97
  98                 result.val = NAN;
  99                 if (expr__resolve_id(ctx, id, &data) == 0) {
 100                         result.val = source_count
 101                                 ? expr_id_data__source_count(data)
 102                                 : expr_id_data__value(data);
 103                 }
 104                 result.ids = NULL;
 105                 free(id);
 106         } else {
 107                 /*
 108                  * Set the value to BOTTOM to show that any value is possible
 109                  * when the event is computed. Create a set of just the ID.
 110                  */
 111                 result.val = BOTTOM;
 112                 result.ids = ids__new();
 113                 if (!result.ids || ids__insert(result.ids, id)) {
 114                         pr_err("Error creating IDs for '%s'", id);
 115                         free(id);
 116                 }
 117         }
 118         return result;
 119 }
 120
 121 /*
 122  * If we're not computing ids or $1 and $3 are constants, compute the new
 123  * constant value using OP. Its invariant that there are no ids.  If computing
 124  * ids for non-constants union the set of IDs that must be computed.
 125  */
 126 #define BINARY_LONG_OP(RESULT, OP, LHS, RHS)                            \
 127         if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \
 128                 assert(LHS.ids == NULL);                                \
 129                 assert(RHS.ids == NULL);                                \
 130                 RESULT.val = (long)LHS.val OP (long)RHS.val;            \
 131                 RESULT.ids = NULL;                                      \
 132         } else {                                                        \
 133                 RESULT = union_expr(LHS, RHS);                          \
 134         }
 135
 136 #define BINARY_OP(RESULT, OP, LHS, RHS)                                 \
 137         if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \
 138                 assert(LHS.ids == NULL);                                \
 139                 assert(RHS.ids == NULL);                                \
 140                 RESULT.val = LHS.val OP RHS.val;                        \
 141                 RESULT.ids = NULL;                                      \
 142         } else {                                                        \
 143                 RESULT = union_expr(LHS, RHS);                          \
 144         }
 145
 146 %}
 147 %%
 148
 149 start: if_expr
 150 {
 151         if (compute_ids)
 152                 ctx->ids = ids__union($1.ids, ctx->ids);
 153
 154         if (final_val)
 155                 *final_val = $1.val;
 156 }
 157 ;
 158
 159 if_expr: expr IF expr ELSE if_expr
 160 {
 161         if (fpclassify($3.val) == FP_ZERO) {
 162                 /*
 163                  * The IF expression evaluated to 0 so treat as false, take the
 164                  * ELSE and discard everything else.
 165                  */
 166                 $$.val = $5.val;
 167                 $$.ids = $5.ids;
 168                 ids__free($1.ids);
 169                 ids__free($3.ids);
 170         } else if (!compute_ids || is_const($3.val)) {
 171                 /*
 172                  * If ids aren't computed then treat the expression as true. If
 173                  * ids are being computed and the IF expr is a non-zero
 174                  * constant, then also evaluate the true case.
 175                  */
 176                 $$.val = $1.val;
 177                 $$.ids = $1.ids;
 178                 ids__free($3.ids);
 179                 ids__free($5.ids);
 180         } else if ($1.val == $5.val) {
 181                 /*
 182                  * LHS == RHS, so both are an identical constant. No need to
 183                  * evaluate any events.
 184                  */
 185                 $$.val = $1.val;
 186                 $$.ids = NULL;
 187                 ids__free($1.ids);
 188                 ids__free($3.ids);
 189                 ids__free($5.ids);
 190         } else {
 191                 /*
 192                  * Value is either the LHS or RHS and we need the IF expression
 193                  * to compute it.
 194                  */
 195                 $$ = union_expr($1, union_expr($3, $5));
 196         }
 197 }
 198 | expr
 199 ;
 200
 201 expr: NUMBER
 202 {
 203         $$.val = $1;
 204         $$.ids = NULL;
 205 }
 206 | ID                            { $$ = handle_id(ctx, $1, compute_ids, /*source_count=*/false); }
 207 | SOURCE_COUNT '(' ID ')'       { $$ = handle_id(ctx, $3, compute_ids, /*source_count=*/true); }
 208 | expr '|' expr { BINARY_LONG_OP($$, |, $1, $3); }
 209 | expr '&' expr { BINARY_LONG_OP($$, &, $1, $3); }
 210 | expr '^' expr { BINARY_LONG_OP($$, ^, $1, $3); }
 211 | expr '<' expr { BINARY_OP($$, <, $1, $3); }
 212 | expr '>' expr { BINARY_OP($$, >, $1, $3); }
 213 | expr '+' expr { BINARY_OP($$, +, $1, $3); }
 214 | expr '-' expr { BINARY_OP($$, -, $1, $3); }
 215 | expr '*' expr { BINARY_OP($$, *, $1, $3); }
 216 | expr '/' expr
 217 {
 218         if (fpclassify($3.val) == FP_ZERO) {
 219                 pr_debug("division by zero\n");
 220                 YYABORT;
 221         } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
 222                 assert($1.ids == NULL);
 223                 assert($3.ids == NULL);
 224                 $$.val = $1.val / $3.val;
 225                 $$.ids = NULL;
 226         } else {
 227                 /* LHS and/or RHS need computing from event IDs so union. */
 228                 $$ = union_expr($1, $3);
 229         }
 230 }
 231 | expr '%' expr
 232 {
 233         if (fpclassify($3.val) == FP_ZERO) {
 234                 pr_debug("division by zero\n");
 235                 YYABORT;
 236         } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
 237                 assert($1.ids == NULL);
 238                 assert($3.ids == NULL);
 239                 $$.val = (long)$1.val % (long)$3.val;
 240                 $$.ids = NULL;
 241         } else {
 242                 /* LHS and/or RHS need computing from event IDs so union. */
 243                 $$ = union_expr($1, $3);
 244         }
 245 }
 246 | D_RATIO '(' expr ',' expr ')'
 247 {
 248         if (fpclassify($5.val) == FP_ZERO) {
 249                 /*
 250                  * Division by constant zero always yields zero and no events
 251                  * are necessary.
 252                  */
 253                 assert($5.ids == NULL);
 254                 $$.val = 0.0;
 255                 $$.ids = NULL;
 256                 ids__free($3.ids);
 257         } else if (!compute_ids || (is_const($3.val) && is_const($5.val))) {
 258                 assert($3.ids == NULL);
 259                 assert($5.ids == NULL);
 260                 $$.val = $3.val / $5.val;
 261                 $$.ids = NULL;
 262         } else {
 263                 /* LHS and/or RHS need computing from event IDs so union. */
 264                 $$ = union_expr($3, $5);
 265         }
 266 }
 267 | '-' expr %prec NEG
 268 {
 269         $$.val = -$2.val;
 270         $$.ids = $2.ids;
 271 }
 272 | '(' if_expr ')'
 273 {
 274         $$ = $2;
 275 }
 276 | MIN '(' expr ',' expr ')'
 277 {
 278         if (!compute_ids) {
 279                 $$.val = $3.val < $5.val ? $3.val : $5.val;
 280                 $$.ids = NULL;
 281         } else {
 282                 $$ = union_expr($3, $5);
 283         }
 284 }
 285 | MAX '(' expr ',' expr ')'
 286 {
 287         if (!compute_ids) {
 288                 $$.val = $3.val > $5.val ? $3.val : $5.val;
 289                 $$.ids = NULL;
 290         } else {
 291                 $$ = union_expr($3, $5);
 292         }
 293 }
 294 | LITERAL
 295 {
 296         $$.val = $1;
 297         $$.ids = NULL;
 298 }
 299 ;
 300
 301 %%