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 HAS_EVENT 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_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                 if (isnan(LHS.val) || isnan(RHS.val)) {                 \
 131                         RESULT.val = NAN;                               \
 132                 } else {                                                \
 133                         RESULT.val = LHS.val OP RHS.val;                \
 134                 }                                                       \
 135                 RESULT.ids = NULL;                                      \
 136         } else {                                                        \
 137                 RESULT = union_expr(LHS, RHS);                          \
 138         }
 139
 140 %}
 141 %%
 142
 143 start: if_expr
 144 {
 145         if (compute_ids)
 146                 ctx->ids = ids__union($1.ids, ctx->ids);
 147
 148         if (final_val)
 149                 *final_val = $1.val;
 150 }
 151 ;
 152
 153 if_expr: expr IF expr ELSE if_expr
 154 {
 155         if (fpclassify($3.val) == FP_ZERO) {
 156                 /*
 157                  * The IF expression evaluated to 0 so treat as false, take the
 158                  * ELSE and discard everything else.
 159                  */
 160                 $$.val = $5.val;
 161                 $$.ids = $5.ids;
 162                 ids__free($1.ids);
 163                 ids__free($3.ids);
 164         } else if (!compute_ids || is_const($3.val)) {
 165                 /*
 166                  * If ids aren't computed then treat the expression as true. If
 167                  * ids are being computed and the IF expr is a non-zero
 168                  * constant, then also evaluate the true case.
 169                  */
 170                 $$.val = $1.val;
 171                 $$.ids = $1.ids;
 172                 ids__free($3.ids);
 173                 ids__free($5.ids);
 174         } else if ($1.val == $5.val) {
 175                 /*
 176                  * LHS == RHS, so both are an identical constant. No need to
 177                  * evaluate any events.
 178                  */
 179                 $$.val = $1.val;
 180                 $$.ids = NULL;
 181                 ids__free($1.ids);
 182                 ids__free($3.ids);
 183                 ids__free($5.ids);
 184         } else {
 185                 /*
 186                  * Value is either the LHS or RHS and we need the IF expression
 187                  * to compute it.
 188                  */
 189                 $$ = union_expr($1, union_expr($3, $5));
 190         }
 191 }
 192 | expr
 193 ;
 194
 195 expr: NUMBER
 196 {
 197         $$.val = $1;
 198         $$.ids = NULL;
 199 }
 200 | ID                            { $$ = handle_id(ctx, $1, compute_ids, /*source_count=*/false); }
 201 | SOURCE_COUNT '(' ID ')'       { $$ = handle_id(ctx, $3, compute_ids, /*source_count=*/true); }
 202 | HAS_EVENT '(' ID ')'
 203 {
 204         $$.val = expr__has_event(ctx, compute_ids, $3);
 205         $$.ids = NULL;
 206         free($3);
 207 }
 208 | expr '|' expr
 209 {
 210         if (is_const($1.val) && is_const($3.val)) {
 211                 assert($1.ids == NULL);
 212                 assert($3.ids == NULL);
 213                 $$.ids = NULL;
 214                 $$.val = (fpclassify($1.val) == FP_ZERO && fpclassify($3.val) == FP_ZERO) ? 0 : 1;
 215         } else if (is_const($1.val)) {
 216                 assert($1.ids == NULL);
 217                 if (fpclassify($1.val) == FP_ZERO) {
 218                         $$ = $3;
 219                 } else {
 220                         $$.val = 1;
 221                         $$.ids = NULL;
 222                         ids__free($3.ids);
 223                 }
 224         } else if (is_const($3.val)) {
 225                 assert($3.ids == NULL);
 226                 if (fpclassify($3.val) == FP_ZERO) {
 227                         $$ = $1;
 228                 } else {
 229                         $$.val = 1;
 230                         $$.ids = NULL;
 231                         ids__free($1.ids);
 232                 }
 233         } else {
 234                 $$ = union_expr($1, $3);
 235         }
 236 }
 237 | expr '&' expr
 238 {
 239         if (is_const($1.val) && is_const($3.val)) {
 240                 assert($1.ids == NULL);
 241                 assert($3.ids == NULL);
 242                 $$.val = (fpclassify($1.val) != FP_ZERO && fpclassify($3.val) != FP_ZERO) ? 1 : 0;
 243                 $$.ids = NULL;
 244         } else if (is_const($1.val)) {
 245                 assert($1.ids == NULL);
 246                 if (fpclassify($1.val) != FP_ZERO) {
 247                         $$ = $3;
 248                 } else {
 249                         $$.val = 0;
 250                         $$.ids = NULL;
 251                         ids__free($3.ids);
 252                 }
 253         } else if (is_const($3.val)) {
 254                 assert($3.ids == NULL);
 255                 if (fpclassify($3.val) != FP_ZERO) {
 256                         $$ = $1;
 257                 } else {
 258                         $$.val = 0;
 259                         $$.ids = NULL;
 260                         ids__free($1.ids);
 261                 }
 262         } else {
 263                 $$ = union_expr($1, $3);
 264         }
 265 }
 266 | expr '^' expr
 267 {
 268         if (is_const($1.val) && is_const($3.val)) {
 269                 assert($1.ids == NULL);
 270                 assert($3.ids == NULL);
 271                 $$.val = (fpclassify($1.val) == FP_ZERO) != (fpclassify($3.val) == FP_ZERO) ? 1 : 0;
 272                 $$.ids = NULL;
 273         } else {
 274                 $$ = union_expr($1, $3);
 275         }
 276 }
 277 | expr '<' expr { BINARY_OP($$, <, $1, $3); }
 278 | expr '>' expr { BINARY_OP($$, >, $1, $3); }
 279 | expr '+' expr { BINARY_OP($$, +, $1, $3); }
 280 | expr '-' expr { BINARY_OP($$, -, $1, $3); }
 281 | expr '*' expr { BINARY_OP($$, *, $1, $3); }
 282 | expr '/' expr
 283 {
 284         if (fpclassify($3.val) == FP_ZERO) {
 285                 pr_debug("division by zero\n");
 286                 assert($3.ids == NULL);
 287                 if (compute_ids)
 288                         ids__free($1.ids);
 289                 $$.val = NAN;
 290                 $$.ids = NULL;
 291         } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
 292                 assert($1.ids == NULL);
 293                 assert($3.ids == NULL);
 294                 $$.val = $1.val / $3.val;
 295                 $$.ids = NULL;
 296         } else {
 297                 /* LHS and/or RHS need computing from event IDs so union. */
 298                 $$ = union_expr($1, $3);
 299         }
 300 }
 301 | expr '%' expr
 302 {
 303         if (fpclassify($3.val) == FP_ZERO) {
 304                 pr_debug("division by zero\n");
 305                 YYABORT;
 306         } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
 307                 assert($1.ids == NULL);
 308                 assert($3.ids == NULL);
 309                 $$.val = (long)$1.val % (long)$3.val;
 310                 $$.ids = NULL;
 311         } else {
 312                 /* LHS and/or RHS need computing from event IDs so union. */
 313                 $$ = union_expr($1, $3);
 314         }
 315 }
 316 | D_RATIO '(' expr ',' expr ')'
 317 {
 318         if (fpclassify($5.val) == FP_ZERO) {
 319                 /*
 320                  * Division by constant zero always yields zero and no events
 321                  * are necessary.
 322                  */
 323                 assert($5.ids == NULL);
 324                 $$.val = 0.0;
 325                 $$.ids = NULL;
 326                 ids__free($3.ids);
 327         } else if (!compute_ids || (is_const($3.val) && is_const($5.val))) {
 328                 assert($3.ids == NULL);
 329                 assert($5.ids == NULL);
 330                 $$.val = $3.val / $5.val;
 331                 $$.ids = NULL;
 332         } else {
 333                 /* LHS and/or RHS need computing from event IDs so union. */
 334                 $$ = union_expr($3, $5);
 335         }
 336 }
 337 | '-' expr %prec NEG
 338 {
 339         $$.val = -$2.val;
 340         $$.ids = $2.ids;
 341 }
 342 | '(' if_expr ')'
 343 {
 344         $$ = $2;
 345 }
 346 | MIN '(' expr ',' expr ')'
 347 {
 348         if (!compute_ids) {
 349                 $$.val = $3.val < $5.val ? $3.val : $5.val;
 350                 $$.ids = NULL;
 351         } else {
 352                 $$ = union_expr($3, $5);
 353         }
 354 }
 355 | MAX '(' expr ',' expr ')'
 356 {
 357         if (!compute_ids) {
 358                 $$.val = $3.val > $5.val ? $3.val : $5.val;
 359                 $$.ids = NULL;
 360         } else {
 361                 $$ = union_expr($3, $5);
 362         }
 363 }
 364 | LITERAL
 365 {
 366         $$.val = $1;
 367         $$.ids = NULL;
 368 }
 369 ;
 370
 371 %%