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