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 STRCMP_CPUID_STR 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 | STRCMP_CPUID_STR '(' ID ')'
 211 {
 212         $$.val = expr__strcmp_cpuid_str(ctx, compute_ids, $3);
 213         $$.ids = NULL;
 214         free($3);
 215 }
 216 | expr '|' expr
 217 {
 218         if (is_const($1.val) && is_const($3.val)) {
 219                 assert($1.ids == NULL);
 220                 assert($3.ids == NULL);
 221                 $$.ids = NULL;
 222                 $$.val = (fpclassify($1.val) == FP_ZERO && fpclassify($3.val) == FP_ZERO) ? 0 : 1;
 223         } else if (is_const($1.val)) {
 224                 assert($1.ids == NULL);
 225                 if (fpclassify($1.val) == FP_ZERO) {
 226                         $$ = $3;
 227                 } else {
 228                         $$.val = 1;
 229                         $$.ids = NULL;
 230                         ids__free($3.ids);
 231                 }
 232         } else if (is_const($3.val)) {
 233                 assert($3.ids == NULL);
 234                 if (fpclassify($3.val) == FP_ZERO) {
 235                         $$ = $1;
 236                 } else {
 237                         $$.val = 1;
 238                         $$.ids = NULL;
 239                         ids__free($1.ids);
 240                 }
 241         } else {
 242                 $$ = union_expr($1, $3);
 243         }
 244 }
 245 | expr '&' expr
 246 {
 247         if (is_const($1.val) && is_const($3.val)) {
 248                 assert($1.ids == NULL);
 249                 assert($3.ids == NULL);
 250                 $$.val = (fpclassify($1.val) != FP_ZERO && fpclassify($3.val) != FP_ZERO) ? 1 : 0;
 251                 $$.ids = NULL;
 252         } else if (is_const($1.val)) {
 253                 assert($1.ids == NULL);
 254                 if (fpclassify($1.val) != FP_ZERO) {
 255                         $$ = $3;
 256                 } else {
 257                         $$.val = 0;
 258                         $$.ids = NULL;
 259                         ids__free($3.ids);
 260                 }
 261         } else if (is_const($3.val)) {
 262                 assert($3.ids == NULL);
 263                 if (fpclassify($3.val) != FP_ZERO) {
 264                         $$ = $1;
 265                 } else {
 266                         $$.val = 0;
 267                         $$.ids = NULL;
 268                         ids__free($1.ids);
 269                 }
 270         } else {
 271                 $$ = union_expr($1, $3);
 272         }
 273 }
 274 | expr '^' expr
 275 {
 276         if (is_const($1.val) && is_const($3.val)) {
 277                 assert($1.ids == NULL);
 278                 assert($3.ids == NULL);
 279                 $$.val = (fpclassify($1.val) == FP_ZERO) != (fpclassify($3.val) == FP_ZERO) ? 1 : 0;
 280                 $$.ids = NULL;
 281         } else {
 282                 $$ = union_expr($1, $3);
 283         }
 284 }
 285 | expr '<' expr { BINARY_OP($$, <, $1, $3); }
 286 | expr '>' expr { BINARY_OP($$, >, $1, $3); }
 287 | expr '+' expr { BINARY_OP($$, +, $1, $3); }
 288 | expr '-' expr { BINARY_OP($$, -, $1, $3); }
 289 | expr '*' expr { BINARY_OP($$, *, $1, $3); }
 290 | expr '/' expr
 291 {
 292         if (fpclassify($3.val) == FP_ZERO) {
 293                 pr_debug("division by zero\n");
 294                 assert($3.ids == NULL);
 295                 if (compute_ids)
 296                         ids__free($1.ids);
 297                 $$.val = NAN;
 298                 $$.ids = NULL;
 299         } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
 300                 assert($1.ids == NULL);
 301                 assert($3.ids == NULL);
 302                 $$.val = $1.val / $3.val;
 303                 $$.ids = NULL;
 304         } else {
 305                 /* LHS and/or RHS need computing from event IDs so union. */
 306                 $$ = union_expr($1, $3);
 307         }
 308 }
 309 | expr '%' expr
 310 {
 311         if (fpclassify($3.val) == FP_ZERO) {
 312                 pr_debug("division by zero\n");
 313                 YYABORT;
 314         } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
 315                 assert($1.ids == NULL);
 316                 assert($3.ids == NULL);
 317                 $$.val = (long)$1.val % (long)$3.val;
 318                 $$.ids = NULL;
 319         } else {
 320                 /* LHS and/or RHS need computing from event IDs so union. */
 321                 $$ = union_expr($1, $3);
 322         }
 323 }
 324 | D_RATIO '(' expr ',' expr ')'
 325 {
 326         if (fpclassify($5.val) == FP_ZERO) {
 327                 /*
 328                  * Division by constant zero always yields zero and no events
 329                  * are necessary.
 330                  */
 331                 assert($5.ids == NULL);
 332                 $$.val = 0.0;
 333                 $$.ids = NULL;
 334                 ids__free($3.ids);
 335         } else if (!compute_ids || (is_const($3.val) && is_const($5.val))) {
 336                 assert($3.ids == NULL);
 337                 assert($5.ids == NULL);
 338                 $$.val = $3.val / $5.val;
 339                 $$.ids = NULL;
 340         } else {
 341                 /* LHS and/or RHS need computing from event IDs so union. */
 342                 $$ = union_expr($3, $5);
 343         }
 344 }
 345 | '-' expr %prec NEG
 346 {
 347         $$.val = -$2.val;
 348         $$.ids = $2.ids;
 349 }
 350 | '(' if_expr ')'
 351 {
 352         $$ = $2;
 353 }
 354 | MIN '(' expr ',' expr ')'
 355 {
 356         if (!compute_ids) {
 357                 $$.val = $3.val < $5.val ? $3.val : $5.val;
 358                 $$.ids = NULL;
 359         } else {
 360                 $$ = union_expr($3, $5);
 361         }
 362 }
 363 | MAX '(' expr ',' expr ')'
 364 {
 365         if (!compute_ids) {
 366                 $$.val = $3.val > $5.val ? $3.val : $5.val;
 367                 $$.ids = NULL;
 368         } else {
 369                 $$ = union_expr($3, $5);
 370         }
 371 }
 372 | LITERAL
 373 {
 374         $$.val = $1;
 375         $$.ids = NULL;
 376 }
 377 ;
 378
 379 %%