1 /* Simple expression parser */ 1 /* Simple expression parser */
2 %{ 2 %{
3 #ifndef NDEBUG !! 3 #include "util.h"
4 #define YYDEBUG 1 <<
5 #endif <<
6 #include <assert.h> <<
7 #include <math.h> <<
8 #include <stdlib.h> <<
9 #include "util/debug.h" 4 #include "util/debug.h"
>> 5 #include <stdlib.h> // strtod()
10 #define IN_EXPR_Y 1 6 #define IN_EXPR_Y 1
11 #include "expr.h" 7 #include "expr.h"
12 #include "expr-bison.h" !! 8 #include "smt.h"
13 int expr_lex(YYSTYPE * yylval_param , void *yy !! 9 #include <assert.h>
14 %} !! 10 #include <string.h>
15 11
16 %define api.pure full !! 12 #define MAXIDLEN 256
>> 13 %}
17 14
>> 15 %pure-parser
18 %parse-param { double *final_val } 16 %parse-param { double *final_val }
19 %parse-param { struct expr_parse_ctx *ctx } !! 17 %parse-param { struct parse_ctx *ctx }
20 %parse-param { bool compute_ids } !! 18 %parse-param { const char **pp }
21 %parse-param {void *scanner} !! 19 %lex-param { const char **pp }
22 %lex-param {void* scanner} <<
23 20
24 %union { 21 %union {
25 double num; !! 22 double num;
26 char *str; !! 23 char id[MAXIDLEN+1];
27 struct ids { <<
28 /* <<
29 * When creating ids, holds th <<
30 * implies the set is empty. <<
31 */ <<
32 struct hashmap *ids; <<
33 /* <<
34 * The metric value. When not <<
35 * read from a counter, a cons <<
36 * creating ids the value is e <<
37 * used as the special BOTTOM <<
38 * values" case. <<
39 */ <<
40 double val; <<
41 } ids; <<
42 } 24 }
43 25
44 %token ID NUMBER MIN MAX IF ELSE LITERAL D_RAT !! 26 %token <num> NUMBER
>> 27 %token <id> ID
>> 28 %token MIN MAX IF ELSE SMT_ON
45 %left MIN MAX IF 29 %left MIN MAX IF
46 %left '|' 30 %left '|'
47 %left '^' 31 %left '^'
48 %left '&' 32 %left '&'
49 %left '<' '>' <<
50 %left '-' '+' 33 %left '-' '+'
51 %left '*' '/' '%' 34 %left '*' '/' '%'
52 %left NEG NOT 35 %left NEG NOT
53 %type <num> NUMBER LITERAL !! 36 %type <num> expr if_expr
54 %type <str> ID <<
55 %destructor { free ($$); } <str> <<
56 %type <ids> expr if_expr <<
57 %destructor { ids__free($$.ids); } <ids> <<
58 37
59 %{ 38 %{
60 static void expr_error(double *final_val __may !! 39 static int expr__lex(YYSTYPE *res, const char **pp);
61 struct expr_parse_ctx * !! 40
62 bool compute_ids __mayb !! 41 static void expr__error(double *final_val __maybe_unused,
63 void *scanner __maybe_u !! 42 struct parse_ctx *ctx __maybe_unused,
>> 43 const char **pp __maybe_unused,
64 const char *s) 44 const char *s)
65 { 45 {
66 pr_debug("%s\n", s); 46 pr_debug("%s\n", s);
67 } 47 }
68 48
69 /* !! 49 static int lookup_id(struct parse_ctx *ctx, char *id, double *val)
70 * During compute ids, the special "bottom" va <<
71 * of all values. NAN is selected as it isn't <<
72 */ <<
73 #define BOTTOM NAN <<
74 <<
75 /* During computing ids, does val represent a <<
76 static bool is_const(double val) <<
77 { 50 {
78 return isfinite(val); !! 51 int i;
79 } <<
80 52
81 static struct ids union_expr(struct ids ids1, !! 53 for (i = 0; i < ctx->num_ids; i++) {
82 { !! 54 if (!strcasecmp(ctx->ids[i].name, id)) {
83 struct ids result = { !! 55 *val = ctx->ids[i].val;
84 .val = BOTTOM, !! 56 return 0;
85 .ids = ids__union(ids1.ids, id <<
86 }; <<
87 return result; <<
88 } <<
89 <<
90 static struct ids handle_id(struct expr_parse_ <<
91 bool compute_ids, <<
92 { <<
93 struct ids result; <<
94 <<
95 if (!compute_ids) { <<
96 /* <<
97 * Compute the event's value f <<
98 * it isn't used to compute th <<
99 */ <<
100 struct expr_id_data *data; <<
101 <<
102 result.val = NAN; <<
103 if (expr__resolve_id(ctx, id, <<
104 result.val = source_co <<
105 ? expr_id_data <<
106 : expr_id_data <<
107 } <<
108 result.ids = NULL; <<
109 free(id); <<
110 } else { <<
111 /* <<
112 * Set the value to BOTTOM to <<
113 * when the event is computed. <<
114 */ <<
115 result.val = BOTTOM; <<
116 result.ids = ids__new(); <<
117 if (!result.ids || ids__insert <<
118 pr_err("Error creating <<
119 free(id); <<
120 } 57 }
121 } 58 }
122 return result; !! 59 return -1;
123 } 60 }
124 61
125 /* <<
126 * If we're not computing ids or $1 and $3 are <<
127 * constant value using OP. Its invariant that <<
128 * ids for non-constants union the set of IDs <<
129 */ <<
130 #define BINARY_OP(RESULT, OP, LHS, RHS) <<
131 if (!compute_ids || (is_const(LHS.val) <<
132 assert(LHS.ids == NULL); <<
133 assert(RHS.ids == NULL); <<
134 if (isnan(LHS.val) || isnan(RH <<
135 RESULT.val = NAN; <<
136 } else { <<
137 RESULT.val = LHS.val O <<
138 } <<
139 RESULT.ids = NULL; <<
140 } else { <<
141 RESULT = union_expr(LHS, RHS); <<
142 } <<
143 <<
144 %} 62 %}
145 %% 63 %%
146 64
147 start: if_expr !! 65 all_expr: if_expr { *final_val = $1; }
148 { !! 66 ;
149 if (compute_ids) <<
150 ctx->ids = ids__union($1.ids, <<
151 67
152 if (final_val) !! 68 if_expr:
153 *final_val = $1.val; !! 69 expr IF expr ELSE expr { $$ = $3 ? $1 : $5; }
154 } !! 70 | expr
155 ; !! 71 ;
>> 72
>> 73 expr: NUMBER
>> 74 | ID { if (lookup_id(ctx, $1, &$$) < 0) {
>> 75 pr_debug("%s not found\n", $1);
>> 76 YYABORT;
>> 77 }
>> 78 }
>> 79 | expr '|' expr { $$ = (long)$1 | (long)$3; }
>> 80 | expr '&' expr { $$ = (long)$1 & (long)$3; }
>> 81 | expr '^' expr { $$ = (long)$1 ^ (long)$3; }
>> 82 | expr '+' expr { $$ = $1 + $3; }
>> 83 | expr '-' expr { $$ = $1 - $3; }
>> 84 | expr '*' expr { $$ = $1 * $3; }
>> 85 | expr '/' expr { if ($3 == 0) YYABORT; $$ = $1 / $3; }
>> 86 | expr '%' expr { if ((long)$3 == 0) YYABORT; $$ = (long)$1 % (long)$3; }
>> 87 | '-' expr %prec NEG { $$ = -$2; }
>> 88 | '(' if_expr ')' { $$ = $2; }
>> 89 | MIN '(' expr ',' expr ')' { $$ = $3 < $5 ? $3 : $5; }
>> 90 | MAX '(' expr ',' expr ')' { $$ = $3 > $5 ? $3 : $5; }
>> 91 | SMT_ON { $$ = smt_on() > 0; }
>> 92 ;
156 93
157 if_expr: expr IF expr ELSE if_expr !! 94 %%
158 { <<
159 if (fpclassify($3.val) == FP_ZERO) { <<
160 /* <<
161 * The IF expression evaluated <<
162 * ELSE and discard everything <<
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 <<
169 /* <<
170 * If ids aren't computed then <<
171 * ids are being computed and <<
172 * constant, then also evaluat <<
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 <<
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 <<
191 * to compute it. <<
192 */ <<
193 $$ = union_expr($1, union_expr <<
194 } <<
195 } <<
196 | expr <<
197 ; <<
198 95
199 expr: NUMBER !! 96 static int expr__symbol(YYSTYPE *res, const char *p, const char **pp)
200 { 97 {
201 $$.val = $1; !! 98 char *dst = res->id;
202 $$.ids = NULL; !! 99 const char *s = p;
203 } !! 100
204 | ID { $$ = handle_ !! 101 if (*p == '#')
205 | SOURCE_COUNT '(' ID ')' { $$ = handle_ !! 102 *dst++ = *p++;
206 | HAS_EVENT '(' ID ')' !! 103
207 { !! 104 while (isalnum(*p) || *p == '_' || *p == '.' || *p == ':' || *p == '@' || *p == '\\') {
208 $$.val = expr__has_event(ctx, compute_ !! 105 if (p - s >= MAXIDLEN)
209 $$.ids = NULL; !! 106 return -1;
210 free($3); !! 107 /*
211 } !! 108 * Allow @ instead of / to be able to specify pmu/event/ without
212 | STRCMP_CPUID_STR '(' ID ')' !! 109 * conflicts with normal division.
213 { !! 110 */
214 $$.val = expr__strcmp_cpuid_str(ctx, c !! 111 if (*p == '@')
215 $$.ids = NULL; !! 112 *dst++ = '/';
216 free($3); !! 113 else if (*p == '\\')
217 } !! 114 *dst++ = *++p;
218 | expr '|' expr !! 115 else
219 { !! 116 *dst++ = *p;
220 if (is_const($1.val) && is_const($3.va !! 117 p++;
221 assert($1.ids == NULL); !! 118 }
222 assert($3.ids == NULL); !! 119 *dst = 0;
223 $$.ids = NULL; !! 120 *pp = p;
224 $$.val = (fpclassify($1.val) = !! 121 dst = res->id;
225 } else if (is_const($1.val)) { !! 122 switch (dst[0]) {
226 assert($1.ids == NULL); !! 123 case 'm':
227 if (fpclassify($1.val) == FP_Z !! 124 if (!strcmp(dst, "min"))
228 $$ = $3; !! 125 return MIN;
229 } else { !! 126 if (!strcmp(dst, "max"))
230 $$.val = 1; !! 127 return MAX;
231 $$.ids = NULL; !! 128 break;
232 ids__free($3.ids); !! 129 case 'i':
233 } !! 130 if (!strcmp(dst, "if"))
234 } else if (is_const($3.val)) { !! 131 return IF;
235 assert($3.ids == NULL); !! 132 break;
236 if (fpclassify($3.val) == FP_Z !! 133 case 'e':
237 $$ = $1; !! 134 if (!strcmp(dst, "else"))
238 } else { !! 135 return ELSE;
239 $$.val = 1; !! 136 break;
240 $$.ids = NULL; !! 137 case '#':
241 ids__free($1.ids); !! 138 if (!strcasecmp(dst, "#smt_on"))
242 } !! 139 return SMT_ON;
243 } else { !! 140 break;
244 $$ = union_expr($1, $3); !! 141 }
245 } !! 142 return ID;
246 } !! 143 }
247 | expr '&' expr !! 144
248 { !! 145 static int expr__lex(YYSTYPE *res, const char **pp)
249 if (is_const($1.val) && is_const($3.va !! 146 {
250 assert($1.ids == NULL); !! 147 int tok;
251 assert($3.ids == NULL); !! 148 const char *s;
252 $$.val = (fpclassify($1.val) ! !! 149 const char *p = *pp;
253 $$.ids = NULL; !! 150
254 } else if (is_const($1.val)) { !! 151 while (isspace(*p))
255 assert($1.ids == NULL); !! 152 p++;
256 if (fpclassify($1.val) != FP_Z !! 153 s = p;
257 $$ = $3; !! 154 switch (*p++) {
258 } else { !! 155 case '#':
259 $$.val = 0; !! 156 case 'a' ... 'z':
260 $$.ids = NULL; !! 157 case 'A' ... 'Z':
261 ids__free($3.ids); !! 158 return expr__symbol(res, p - 1, pp);
262 } !! 159 case '0' ... '9': case '.':
263 } else if (is_const($3.val)) { !! 160 res->num = strtod(s, (char **)&p);
264 assert($3.ids == NULL); !! 161 tok = NUMBER;
265 if (fpclassify($3.val) != FP_Z !! 162 break;
266 $$ = $1; !! 163 default:
267 } else { !! 164 tok = *s;
268 $$.val = 0; !! 165 break;
269 $$.ids = NULL; !! 166 }
270 ids__free($1.ids); !! 167 *pp = p;
271 } !! 168 return tok;
272 } else { !! 169 }
273 $$ = union_expr($1, $3); !! 170
274 } !! 171 /* Caller must make sure id is allocated */
275 } !! 172 void expr__add_id(struct parse_ctx *ctx, const char *name, double val)
276 | expr '^' expr !! 173 {
277 { !! 174 int idx;
278 if (is_const($1.val) && is_const($3.va !! 175 assert(ctx->num_ids < MAX_PARSE_ID);
279 assert($1.ids == NULL); !! 176 idx = ctx->num_ids++;
280 assert($3.ids == NULL); !! 177 ctx->ids[idx].name = name;
281 $$.val = (fpclassify($1.val) = !! 178 ctx->ids[idx].val = val;
282 $$.ids = NULL; !! 179 }
283 } else { !! 180
284 $$ = union_expr($1, $3); !! 181 void expr__ctx_init(struct parse_ctx *ctx)
285 } !! 182 {
286 } !! 183 ctx->num_ids = 0;
287 | expr '<' expr { BINARY_OP($$, <, $1, $3); } !! 184 }
288 | expr '>' expr { BINARY_OP($$, >, $1, $3); } !! 185
289 | expr '+' expr { BINARY_OP($$, +, $1, $3); } !! 186 static bool already_seen(const char *val, const char *one, const char **other,
290 | expr '-' expr { BINARY_OP($$, -, $1, $3); } !! 187 int num_other)
291 | expr '*' expr { BINARY_OP($$, *, $1, $3); } !! 188 {
292 | expr '/' expr !! 189 int i;
293 { !! 190
294 if (fpclassify($3.val) == FP_ZERO) { !! 191 if (one && !strcasecmp(one, val))
295 pr_debug("division by zero\n") !! 192 return true;
296 assert($3.ids == NULL); !! 193 for (i = 0; i < num_other; i++)
297 if (compute_ids) !! 194 if (!strcasecmp(other[i], val))
298 ids__free($1.ids); !! 195 return true;
299 $$.val = NAN; !! 196 return false;
300 $$.ids = NULL; !! 197 }
301 } else if (!compute_ids || (is_const($ !! 198
302 assert($1.ids == NULL); !! 199 int expr__find_other(const char *p, const char *one, const char ***other,
303 assert($3.ids == NULL); !! 200 int *num_otherp)
304 $$.val = $1.val / $3.val; !! 201 {
305 $$.ids = NULL; !! 202 const char *orig = p;
306 } else { !! 203 int err = -1;
307 /* LHS and/or RHS need computi !! 204 int num_other;
308 $$ = union_expr($1, $3); !! 205
309 } !! 206 *other = malloc((EXPR_MAX_OTHER + 1) * sizeof(char *));
310 } !! 207 if (!*other)
311 | expr '%' expr !! 208 return -1;
312 { !! 209
313 if (fpclassify($3.val) == FP_ZERO) { !! 210 num_other = 0;
314 pr_debug("division by zero\n") !! 211 for (;;) {
315 YYABORT; !! 212 YYSTYPE val;
316 } else if (!compute_ids || (is_const($ !! 213 int tok = expr__lex(&val, &p);
317 assert($1.ids == NULL); !! 214 if (tok == 0) {
318 assert($3.ids == NULL); !! 215 err = 0;
319 $$.val = (long)$1.val % (long) !! 216 break;
320 $$.ids = NULL; !! 217 }
321 } else { !! 218 if (tok == ID && !already_seen(val.id, one, *other, num_other)) {
322 /* LHS and/or RHS need computi !! 219 if (num_other >= EXPR_MAX_OTHER - 1) {
323 $$ = union_expr($1, $3); !! 220 pr_debug("Too many extra events in %s\n", orig);
324 } !! 221 break;
325 } !! 222 }
326 | D_RATIO '(' expr ',' expr ')' !! 223 (*other)[num_other] = strdup(val.id);
327 { !! 224 if (!(*other)[num_other])
328 if (fpclassify($5.val) == FP_ZERO) { !! 225 return -1;
329 /* !! 226 num_other++;
330 * Division by constant zero a !! 227 }
331 * are necessary. !! 228 }
332 */ !! 229 (*other)[num_other] = NULL;
333 assert($5.ids == NULL); !! 230 *num_otherp = num_other;
334 $$.val = 0.0; !! 231 if (err) {
335 $$.ids = NULL; !! 232 *num_otherp = 0;
336 ids__free($3.ids); !! 233 free(*other);
337 } else if (!compute_ids || (is_const($ !! 234 *other = NULL;
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 computi <<
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. <<
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. <<
369 $$.ids = NULL; <<
370 } else { <<
371 $$ = union_expr($3, $5); <<
372 } 235 }
>> 236 return err;
373 } 237 }
374 | LITERAL <<
375 { <<
376 $$.val = $1; <<
377 $$.ids = NULL; <<
378 } <<
379 ; <<
380 <<
381 %% <<
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.