projects/linux·blob master · refs

391 lines · 8.8 KiB

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"
13int 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 AGGR_NR 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%{
60static 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? */
76static bool is_const(double val)
77{
78 return isfinite(val);
79}
80
81static 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
90enum expr_id_kind {
91 EXPR_ID_KIND__VALUE,
92 EXPR_ID_KIND__SOURCE_COUNT,
93 EXPR_ID_KIND__AGGR_NR,
94};
95
96static struct ids handle_id(struct expr_parse_ctx *ctx, char *id,
97 bool compute_ids, enum expr_id_kind kind)
98{
99 struct ids result;
100
101 if (!compute_ids) {
102 /*
103 * Compute the event's value from ID. If the ID isn't known then
104 * it isn't used to compute the formula so set to NAN.
105 */
106 struct expr_id_data *data;
107
108 result.val = NAN;
109 if (expr__resolve_id(ctx, id, &data) == 0) {
110 if (kind == EXPR_ID_KIND__SOURCE_COUNT)
111 result.val = expr_id_data__source_count(data);
112 else if (kind == EXPR_ID_KIND__AGGR_NR)
113 result.val = expr_id_data__aggr_nr(data);
114 else
115 result.val = expr_id_data__value(data);
116 }
117 result.ids = NULL;
118 free(id);
119 } else {
120 /*
121 * Set the value to BOTTOM to show that any value is possible
122 * when the event is computed. Create a set of just the ID.
123 */
124 result.val = BOTTOM;
125 result.ids = ids__new();
126 if (!result.ids || ids__insert(result.ids, id)) {
127 pr_err("Error creating IDs for '%s'", id);
128 free(id);
129 }
130 }
131 return result;
132}
133
134/*
135 * If we're not computing ids or $1 and $3 are constants, compute the new
136 * constant value using OP. Its invariant that there are no ids. If computing
137 * ids for non-constants union the set of IDs that must be computed.
138 */
139#define BINARY_OP(RESULT, OP, LHS, RHS) \
140 if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \
141 assert(LHS.ids == NULL); \
142 assert(RHS.ids == NULL); \
143 if (isnan(LHS.val) || isnan(RHS.val)) { \
144 RESULT.val = NAN; \
145 } else { \
146 RESULT.val = LHS.val OP RHS.val; \
147 } \
148 RESULT.ids = NULL; \
149 } else { \
150 RESULT = union_expr(LHS, RHS); \
151 }
152
153%}
154%%
155
156start: if_expr
157{
158 if (compute_ids)
159 ctx->ids = ids__union($1.ids, ctx->ids);
160
161 if (final_val)
162 *final_val = $1.val;
163}
164;
165
166if_expr: expr IF expr ELSE if_expr
167{
168 if (fpclassify($3.val) == FP_ZERO) {
169 /*
170 * The IF expression evaluated to 0 so treat as false, take the
171 * ELSE and discard everything else.
172 */
173 $$.val = $5.val;
174 $$.ids = $5.ids;
175 ids__free($1.ids);
176 ids__free($3.ids);
177 } else if (!compute_ids || is_const($3.val)) {
178 /*
179 * If ids aren't computed then treat the expression as true. If
180 * ids are being computed and the IF expr is a non-zero
181 * constant, then also evaluate the true case.
182 */
183 $$.val = $1.val;
184 $$.ids = $1.ids;
185 ids__free($3.ids);
186 ids__free($5.ids);
187 } else if ($1.val == $5.val) {
188 /*
189 * LHS == RHS, so both are an identical constant. No need to
190 * evaluate any events.
191 */
192 $$.val = $1.val;
193 $$.ids = NULL;
194 ids__free($1.ids);
195 ids__free($3.ids);
196 ids__free($5.ids);
197 } else {
198 /*
199 * Value is either the LHS or RHS and we need the IF expression
200 * to compute it.
201 */
202 $$ = union_expr($1, union_expr($3, $5));
203 }
204}
205| expr
206;
207
208expr: NUMBER
209{
210 $$.val = $1;
211 $$.ids = NULL;
212}
213| ID { $$ = handle_id(ctx, $1, compute_ids, EXPR_ID_KIND__VALUE); }
214| SOURCE_COUNT '(' ID ')' { $$ = handle_id(ctx, $3, compute_ids, EXPR_ID_KIND__SOURCE_COUNT); }
215| AGGR_NR '(' ID ')' { $$ = handle_id(ctx, $3, compute_ids, EXPR_ID_KIND__AGGR_NR); }
216| HAS_EVENT '(' ID ')'
217{
218 $$.val = expr__has_event(ctx, compute_ids, $3);
219 $$.ids = NULL;
220 free($3);
221}
222| STRCMP_CPUID_STR '(' ID ')'
223{
224 $$.val = expr__strcmp_cpuid_str(ctx, compute_ids, $3);
225 $$.ids = NULL;
226 free($3);
227}
228| expr '|' expr
229{
230 if (is_const($1.val) && is_const($3.val)) {
231 assert($1.ids == NULL);
232 assert($3.ids == NULL);
233 $$.ids = NULL;
234 $$.val = (fpclassify($1.val) == FP_ZERO && fpclassify($3.val) == FP_ZERO) ? 0 : 1;
235 } else if (is_const($1.val)) {
236 assert($1.ids == NULL);
237 if (fpclassify($1.val) == FP_ZERO) {
238 $$ = $3;
239 } else {
240 $$.val = 1;
241 $$.ids = NULL;
242 ids__free($3.ids);
243 }
244 } else if (is_const($3.val)) {
245 assert($3.ids == NULL);
246 if (fpclassify($3.val) == FP_ZERO) {
247 $$ = $1;
248 } else {
249 $$.val = 1;
250 $$.ids = NULL;
251 ids__free($1.ids);
252 }
253 } else {
254 $$ = union_expr($1, $3);
255 }
256}
257| expr '&' expr
258{
259 if (is_const($1.val) && is_const($3.val)) {
260 assert($1.ids == NULL);
261 assert($3.ids == NULL);
262 $$.val = (fpclassify($1.val) != FP_ZERO && fpclassify($3.val) != FP_ZERO) ? 1 : 0;
263 $$.ids = NULL;
264 } else if (is_const($1.val)) {
265 assert($1.ids == NULL);
266 if (fpclassify($1.val) != FP_ZERO) {
267 $$ = $3;
268 } else {
269 $$.val = 0;
270 $$.ids = NULL;
271 ids__free($3.ids);
272 }
273 } else if (is_const($3.val)) {
274 assert($3.ids == NULL);
275 if (fpclassify($3.val) != FP_ZERO) {
276 $$ = $1;
277 } else {
278 $$.val = 0;
279 $$.ids = NULL;
280 ids__free($1.ids);
281 }
282 } else {
283 $$ = union_expr($1, $3);
284 }
285}
286| expr '^' expr
287{
288 if (is_const($1.val) && is_const($3.val)) {
289 assert($1.ids == NULL);
290 assert($3.ids == NULL);
291 $$.val = (fpclassify($1.val) == FP_ZERO) != (fpclassify($3.val) == FP_ZERO) ? 1 : 0;
292 $$.ids = NULL;
293 } else {
294 $$ = union_expr($1, $3);
295 }
296}
297| expr '<' expr { BINARY_OP($$, <, $1, $3); }
298| expr '>' expr { BINARY_OP($$, >, $1, $3); }
299| expr '+' expr { BINARY_OP($$, +, $1, $3); }
300| expr '-' expr { BINARY_OP($$, -, $1, $3); }
301| expr '*' expr { BINARY_OP($$, *, $1, $3); }
302| expr '/' expr
303{
304 if (fpclassify($3.val) == FP_ZERO) {
305 pr_debug("division by zero\n");
306 assert($3.ids == NULL);
307 if (compute_ids)
308 ids__free($1.ids);
309 $$.val = NAN;
310 $$.ids = NULL;
311 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
312 assert($1.ids == NULL);
313 assert($3.ids == NULL);
314 $$.val = $1.val / $3.val;
315 $$.ids = NULL;
316 } else {
317 /* LHS and/or RHS need computing from event IDs so union. */
318 $$ = union_expr($1, $3);
319 }
320}
321| expr '%' expr
322{
323 if (fpclassify($3.val) == FP_ZERO) {
324 pr_debug("division by zero\n");
325 YYABORT;
326 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
327 assert($1.ids == NULL);
328 assert($3.ids == NULL);
329 $$.val = (long)$1.val % (long)$3.val;
330 $$.ids = NULL;
331 } else {
332 /* LHS and/or RHS need computing from event IDs so union. */
333 $$ = union_expr($1, $3);
334 }
335}
336| D_RATIO '(' expr ',' expr ')'
337{
338 if (fpclassify($5.val) == FP_ZERO) {
339 /*
340 * Division by constant zero always yields zero and no events
341 * are necessary.
342 */
343 assert($5.ids == NULL);
344 $$.val = 0.0;
345 $$.ids = NULL;
346 ids__free($3.ids);
347 } else if (!compute_ids || (is_const($3.val) && is_const($5.val))) {
348 assert($3.ids == NULL);
349 assert($5.ids == NULL);
350 $$.val = $3.val / $5.val;
351 $$.ids = NULL;
352 } else {
353 /* LHS and/or RHS need computing from event IDs so union. */
354 $$ = union_expr($3, $5);
355 }
356}
357| '-' expr %prec NEG
358{
359 $$.val = -$2.val;
360 $$.ids = $2.ids;
361}
362| '(' if_expr ')'
363{
364 $$ = $2;
365}
366| MIN '(' expr ',' expr ')'
367{
368 if (!compute_ids) {
369 $$.val = $3.val < $5.val ? $3.val : $5.val;
370 $$.ids = NULL;
371 } else {
372 $$ = union_expr($3, $5);
373 }
374}
375| MAX '(' expr ',' expr ')'
376{
377 if (!compute_ids) {
378 $$.val = $3.val > $5.val ? $3.val : $5.val;
379 $$.ids = NULL;
380 } else {
381 $$ = union_expr($3, $5);
382 }
383}
384| LITERAL
385{
386 $$.val = $1;
387 $$.ids = NULL;
388}
389;
390
391%%