tools/perf/util/expr.y

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