Root/
Source at commit cdde9cf73945d547acd3e96f9508c79e84ad0bf1 created 12 years 9 months ago. By Maarten ter Huurne, MMC: JZ4740: Added support for CPU frequency changing | |
---|---|
1 | /* |
2 | * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org> |
3 | * Released under the terms of the GNU GPL v2.0. |
4 | */ |
5 | |
6 | #include <stdio.h> |
7 | #include <stdlib.h> |
8 | #include <string.h> |
9 | |
10 | #include "lkc.h" |
11 | |
12 | #define DEBUG_EXPR 0 |
13 | |
14 | struct expr *expr_alloc_symbol(struct symbol *sym) |
15 | { |
16 | struct expr *e = calloc(1, sizeof(*e)); |
17 | e->type = E_SYMBOL; |
18 | e->left.sym = sym; |
19 | return e; |
20 | } |
21 | |
22 | struct expr *expr_alloc_one(enum expr_type type, struct expr *ce) |
23 | { |
24 | struct expr *e = calloc(1, sizeof(*e)); |
25 | e->type = type; |
26 | e->left.expr = ce; |
27 | return e; |
28 | } |
29 | |
30 | struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2) |
31 | { |
32 | struct expr *e = calloc(1, sizeof(*e)); |
33 | e->type = type; |
34 | e->left.expr = e1; |
35 | e->right.expr = e2; |
36 | return e; |
37 | } |
38 | |
39 | struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2) |
40 | { |
41 | struct expr *e = calloc(1, sizeof(*e)); |
42 | e->type = type; |
43 | e->left.sym = s1; |
44 | e->right.sym = s2; |
45 | return e; |
46 | } |
47 | |
48 | struct expr *expr_alloc_and(struct expr *e1, struct expr *e2) |
49 | { |
50 | if (!e1) |
51 | return e2; |
52 | return e2 ? expr_alloc_two(E_AND, e1, e2) : e1; |
53 | } |
54 | |
55 | struct expr *expr_alloc_or(struct expr *e1, struct expr *e2) |
56 | { |
57 | if (!e1) |
58 | return e2; |
59 | return e2 ? expr_alloc_two(E_OR, e1, e2) : e1; |
60 | } |
61 | |
62 | struct expr *expr_copy(const struct expr *org) |
63 | { |
64 | struct expr *e; |
65 | |
66 | if (!org) |
67 | return NULL; |
68 | |
69 | e = malloc(sizeof(*org)); |
70 | memcpy(e, org, sizeof(*org)); |
71 | switch (org->type) { |
72 | case E_SYMBOL: |
73 | e->left = org->left; |
74 | break; |
75 | case E_NOT: |
76 | e->left.expr = expr_copy(org->left.expr); |
77 | break; |
78 | case E_EQUAL: |
79 | case E_UNEQUAL: |
80 | e->left.sym = org->left.sym; |
81 | e->right.sym = org->right.sym; |
82 | break; |
83 | case E_AND: |
84 | case E_OR: |
85 | case E_LIST: |
86 | e->left.expr = expr_copy(org->left.expr); |
87 | e->right.expr = expr_copy(org->right.expr); |
88 | break; |
89 | default: |
90 | printf("can't copy type %d\n", e->type); |
91 | free(e); |
92 | e = NULL; |
93 | break; |
94 | } |
95 | |
96 | return e; |
97 | } |
98 | |
99 | void expr_free(struct expr *e) |
100 | { |
101 | if (!e) |
102 | return; |
103 | |
104 | switch (e->type) { |
105 | case E_SYMBOL: |
106 | break; |
107 | case E_NOT: |
108 | expr_free(e->left.expr); |
109 | return; |
110 | case E_EQUAL: |
111 | case E_UNEQUAL: |
112 | break; |
113 | case E_OR: |
114 | case E_AND: |
115 | expr_free(e->left.expr); |
116 | expr_free(e->right.expr); |
117 | break; |
118 | default: |
119 | printf("how to free type %d?\n", e->type); |
120 | break; |
121 | } |
122 | free(e); |
123 | } |
124 | |
125 | static int trans_count; |
126 | |
127 | #define e1 (*ep1) |
128 | #define e2 (*ep2) |
129 | |
130 | static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2) |
131 | { |
132 | if (e1->type == type) { |
133 | __expr_eliminate_eq(type, &e1->left.expr, &e2); |
134 | __expr_eliminate_eq(type, &e1->right.expr, &e2); |
135 | return; |
136 | } |
137 | if (e2->type == type) { |
138 | __expr_eliminate_eq(type, &e1, &e2->left.expr); |
139 | __expr_eliminate_eq(type, &e1, &e2->right.expr); |
140 | return; |
141 | } |
142 | if (e1->type == E_SYMBOL && e2->type == E_SYMBOL && |
143 | e1->left.sym == e2->left.sym && |
144 | (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no)) |
145 | return; |
146 | if (!expr_eq(e1, e2)) |
147 | return; |
148 | trans_count++; |
149 | expr_free(e1); expr_free(e2); |
150 | switch (type) { |
151 | case E_OR: |
152 | e1 = expr_alloc_symbol(&symbol_no); |
153 | e2 = expr_alloc_symbol(&symbol_no); |
154 | break; |
155 | case E_AND: |
156 | e1 = expr_alloc_symbol(&symbol_yes); |
157 | e2 = expr_alloc_symbol(&symbol_yes); |
158 | break; |
159 | default: |
160 | ; |
161 | } |
162 | } |
163 | |
164 | void expr_eliminate_eq(struct expr **ep1, struct expr **ep2) |
165 | { |
166 | if (!e1 || !e2) |
167 | return; |
168 | switch (e1->type) { |
169 | case E_OR: |
170 | case E_AND: |
171 | __expr_eliminate_eq(e1->type, ep1, ep2); |
172 | default: |
173 | ; |
174 | } |
175 | if (e1->type != e2->type) switch (e2->type) { |
176 | case E_OR: |
177 | case E_AND: |
178 | __expr_eliminate_eq(e2->type, ep1, ep2); |
179 | default: |
180 | ; |
181 | } |
182 | e1 = expr_eliminate_yn(e1); |
183 | e2 = expr_eliminate_yn(e2); |
184 | } |
185 | |
186 | #undef e1 |
187 | #undef e2 |
188 | |
189 | int expr_eq(struct expr *e1, struct expr *e2) |
190 | { |
191 | int res, old_count; |
192 | |
193 | if (e1->type != e2->type) |
194 | return 0; |
195 | switch (e1->type) { |
196 | case E_EQUAL: |
197 | case E_UNEQUAL: |
198 | return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym; |
199 | case E_SYMBOL: |
200 | return e1->left.sym == e2->left.sym; |
201 | case E_NOT: |
202 | return expr_eq(e1->left.expr, e2->left.expr); |
203 | case E_AND: |
204 | case E_OR: |
205 | e1 = expr_copy(e1); |
206 | e2 = expr_copy(e2); |
207 | old_count = trans_count; |
208 | expr_eliminate_eq(&e1, &e2); |
209 | res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL && |
210 | e1->left.sym == e2->left.sym); |
211 | expr_free(e1); |
212 | expr_free(e2); |
213 | trans_count = old_count; |
214 | return res; |
215 | case E_LIST: |
216 | case E_RANGE: |
217 | case E_NONE: |
218 | /* panic */; |
219 | } |
220 | |
221 | if (DEBUG_EXPR) { |
222 | expr_fprint(e1, stdout); |
223 | printf(" = "); |
224 | expr_fprint(e2, stdout); |
225 | printf(" ?\n"); |
226 | } |
227 | |
228 | return 0; |
229 | } |
230 | |
231 | struct expr *expr_eliminate_yn(struct expr *e) |
232 | { |
233 | struct expr *tmp; |
234 | |
235 | if (e) switch (e->type) { |
236 | case E_AND: |
237 | e->left.expr = expr_eliminate_yn(e->left.expr); |
238 | e->right.expr = expr_eliminate_yn(e->right.expr); |
239 | if (e->left.expr->type == E_SYMBOL) { |
240 | if (e->left.expr->left.sym == &symbol_no) { |
241 | expr_free(e->left.expr); |
242 | expr_free(e->right.expr); |
243 | e->type = E_SYMBOL; |
244 | e->left.sym = &symbol_no; |
245 | e->right.expr = NULL; |
246 | return e; |
247 | } else if (e->left.expr->left.sym == &symbol_yes) { |
248 | free(e->left.expr); |
249 | tmp = e->right.expr; |
250 | *e = *(e->right.expr); |
251 | free(tmp); |
252 | return e; |
253 | } |
254 | } |
255 | if (e->right.expr->type == E_SYMBOL) { |
256 | if (e->right.expr->left.sym == &symbol_no) { |
257 | expr_free(e->left.expr); |
258 | expr_free(e->right.expr); |
259 | e->type = E_SYMBOL; |
260 | e->left.sym = &symbol_no; |
261 | e->right.expr = NULL; |
262 | return e; |
263 | } else if (e->right.expr->left.sym == &symbol_yes) { |
264 | free(e->right.expr); |
265 | tmp = e->left.expr; |
266 | *e = *(e->left.expr); |
267 | free(tmp); |
268 | return e; |
269 | } |
270 | } |
271 | break; |
272 | case E_OR: |
273 | e->left.expr = expr_eliminate_yn(e->left.expr); |
274 | e->right.expr = expr_eliminate_yn(e->right.expr); |
275 | if (e->left.expr->type == E_SYMBOL) { |
276 | if (e->left.expr->left.sym == &symbol_no) { |
277 | free(e->left.expr); |
278 | tmp = e->right.expr; |
279 | *e = *(e->right.expr); |
280 | free(tmp); |
281 | return e; |
282 | } else if (e->left.expr->left.sym == &symbol_yes) { |
283 | expr_free(e->left.expr); |
284 | expr_free(e->right.expr); |
285 | e->type = E_SYMBOL; |
286 | e->left.sym = &symbol_yes; |
287 | e->right.expr = NULL; |
288 | return e; |
289 | } |
290 | } |
291 | if (e->right.expr->type == E_SYMBOL) { |
292 | if (e->right.expr->left.sym == &symbol_no) { |
293 | free(e->right.expr); |
294 | tmp = e->left.expr; |
295 | *e = *(e->left.expr); |
296 | free(tmp); |
297 | return e; |
298 | } else if (e->right.expr->left.sym == &symbol_yes) { |
299 | expr_free(e->left.expr); |
300 | expr_free(e->right.expr); |
301 | e->type = E_SYMBOL; |
302 | e->left.sym = &symbol_yes; |
303 | e->right.expr = NULL; |
304 | return e; |
305 | } |
306 | } |
307 | break; |
308 | default: |
309 | ; |
310 | } |
311 | return e; |
312 | } |
313 | |
314 | /* |
315 | * bool FOO!=n => FOO |
316 | */ |
317 | struct expr *expr_trans_bool(struct expr *e) |
318 | { |
319 | if (!e) |
320 | return NULL; |
321 | switch (e->type) { |
322 | case E_AND: |
323 | case E_OR: |
324 | case E_NOT: |
325 | e->left.expr = expr_trans_bool(e->left.expr); |
326 | e->right.expr = expr_trans_bool(e->right.expr); |
327 | break; |
328 | case E_UNEQUAL: |
329 | // FOO!=n -> FOO |
330 | if (e->left.sym->type == S_TRISTATE) { |
331 | if (e->right.sym == &symbol_no) { |
332 | e->type = E_SYMBOL; |
333 | e->right.sym = NULL; |
334 | } |
335 | } |
336 | break; |
337 | default: |
338 | ; |
339 | } |
340 | return e; |
341 | } |
342 | |
343 | /* |
344 | * e1 || e2 -> ? |
345 | */ |
346 | static struct expr *expr_join_or(struct expr *e1, struct expr *e2) |
347 | { |
348 | struct expr *tmp; |
349 | struct symbol *sym1, *sym2; |
350 | |
351 | if (expr_eq(e1, e2)) |
352 | return expr_copy(e1); |
353 | if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) |
354 | return NULL; |
355 | if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) |
356 | return NULL; |
357 | if (e1->type == E_NOT) { |
358 | tmp = e1->left.expr; |
359 | if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) |
360 | return NULL; |
361 | sym1 = tmp->left.sym; |
362 | } else |
363 | sym1 = e1->left.sym; |
364 | if (e2->type == E_NOT) { |
365 | if (e2->left.expr->type != E_SYMBOL) |
366 | return NULL; |
367 | sym2 = e2->left.expr->left.sym; |
368 | } else |
369 | sym2 = e2->left.sym; |
370 | if (sym1 != sym2) |
371 | return NULL; |
372 | if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) |
373 | return NULL; |
374 | if (sym1->type == S_TRISTATE) { |
375 | if (e1->type == E_EQUAL && e2->type == E_EQUAL && |
376 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) || |
377 | (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) { |
378 | // (a='y') || (a='m') -> (a!='n') |
379 | return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no); |
380 | } |
381 | if (e1->type == E_EQUAL && e2->type == E_EQUAL && |
382 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) || |
383 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) { |
384 | // (a='y') || (a='n') -> (a!='m') |
385 | return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod); |
386 | } |
387 | if (e1->type == E_EQUAL && e2->type == E_EQUAL && |
388 | ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) || |
389 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) { |
390 | // (a='m') || (a='n') -> (a!='y') |
391 | return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes); |
392 | } |
393 | } |
394 | if (sym1->type == S_BOOLEAN && sym1 == sym2) { |
395 | if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) || |
396 | (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL)) |
397 | return expr_alloc_symbol(&symbol_yes); |
398 | } |
399 | |
400 | if (DEBUG_EXPR) { |
401 | printf("optimize ("); |
402 | expr_fprint(e1, stdout); |
403 | printf(") || ("); |
404 | expr_fprint(e2, stdout); |
405 | printf(")?\n"); |
406 | } |
407 | return NULL; |
408 | } |
409 | |
410 | static struct expr *expr_join_and(struct expr *e1, struct expr *e2) |
411 | { |
412 | struct expr *tmp; |
413 | struct symbol *sym1, *sym2; |
414 | |
415 | if (expr_eq(e1, e2)) |
416 | return expr_copy(e1); |
417 | if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) |
418 | return NULL; |
419 | if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) |
420 | return NULL; |
421 | if (e1->type == E_NOT) { |
422 | tmp = e1->left.expr; |
423 | if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) |
424 | return NULL; |
425 | sym1 = tmp->left.sym; |
426 | } else |
427 | sym1 = e1->left.sym; |
428 | if (e2->type == E_NOT) { |
429 | if (e2->left.expr->type != E_SYMBOL) |
430 | return NULL; |
431 | sym2 = e2->left.expr->left.sym; |
432 | } else |
433 | sym2 = e2->left.sym; |
434 | if (sym1 != sym2) |
435 | return NULL; |
436 | if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) |
437 | return NULL; |
438 | |
439 | if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) || |
440 | (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes)) |
441 | // (a) && (a='y') -> (a='y') |
442 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); |
443 | |
444 | if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) || |
445 | (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no)) |
446 | // (a) && (a!='n') -> (a) |
447 | return expr_alloc_symbol(sym1); |
448 | |
449 | if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) || |
450 | (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod)) |
451 | // (a) && (a!='m') -> (a='y') |
452 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); |
453 | |
454 | if (sym1->type == S_TRISTATE) { |
455 | if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) { |
456 | // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b' |
457 | sym2 = e1->right.sym; |
458 | if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST)) |
459 | return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2) |
460 | : expr_alloc_symbol(&symbol_no); |
461 | } |
462 | if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) { |
463 | // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b' |
464 | sym2 = e2->right.sym; |
465 | if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST)) |
466 | return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2) |
467 | : expr_alloc_symbol(&symbol_no); |
468 | } |
469 | if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && |
470 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) || |
471 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) |
472 | // (a!='y') && (a!='n') -> (a='m') |
473 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod); |
474 | |
475 | if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && |
476 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) || |
477 | (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) |
478 | // (a!='y') && (a!='m') -> (a='n') |
479 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_no); |
480 | |
481 | if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && |
482 | ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) || |
483 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) |
484 | // (a!='m') && (a!='n') -> (a='m') |
485 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); |
486 | |
487 | if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) || |
488 | (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) || |
489 | (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) || |
490 | (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes)) |
491 | return NULL; |
492 | } |
493 | |
494 | if (DEBUG_EXPR) { |
495 | printf("optimize ("); |
496 | expr_fprint(e1, stdout); |
497 | printf(") && ("); |
498 | expr_fprint(e2, stdout); |
499 | printf(")?\n"); |
500 | } |
501 | return NULL; |
502 | } |
503 | |
504 | static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2) |
505 | { |
506 | #define e1 (*ep1) |
507 | #define e2 (*ep2) |
508 | struct expr *tmp; |
509 | |
510 | if (e1->type == type) { |
511 | expr_eliminate_dups1(type, &e1->left.expr, &e2); |
512 | expr_eliminate_dups1(type, &e1->right.expr, &e2); |
513 | return; |
514 | } |
515 | if (e2->type == type) { |
516 | expr_eliminate_dups1(type, &e1, &e2->left.expr); |
517 | expr_eliminate_dups1(type, &e1, &e2->right.expr); |
518 | return; |
519 | } |
520 | if (e1 == e2) |
521 | return; |
522 | |
523 | switch (e1->type) { |
524 | case E_OR: case E_AND: |
525 | expr_eliminate_dups1(e1->type, &e1, &e1); |
526 | default: |
527 | ; |
528 | } |
529 | |
530 | switch (type) { |
531 | case E_OR: |
532 | tmp = expr_join_or(e1, e2); |
533 | if (tmp) { |
534 | expr_free(e1); expr_free(e2); |
535 | e1 = expr_alloc_symbol(&symbol_no); |
536 | e2 = tmp; |
537 | trans_count++; |
538 | } |
539 | break; |
540 | case E_AND: |
541 | tmp = expr_join_and(e1, e2); |
542 | if (tmp) { |
543 | expr_free(e1); expr_free(e2); |
544 | e1 = expr_alloc_symbol(&symbol_yes); |
545 | e2 = tmp; |
546 | trans_count++; |
547 | } |
548 | break; |
549 | default: |
550 | ; |
551 | } |
552 | #undef e1 |
553 | #undef e2 |
554 | } |
555 | |
556 | static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2) |
557 | { |
558 | #define e1 (*ep1) |
559 | #define e2 (*ep2) |
560 | struct expr *tmp, *tmp1, *tmp2; |
561 | |
562 | if (e1->type == type) { |
563 | expr_eliminate_dups2(type, &e1->left.expr, &e2); |
564 | expr_eliminate_dups2(type, &e1->right.expr, &e2); |
565 | return; |
566 | } |
567 | if (e2->type == type) { |
568 | expr_eliminate_dups2(type, &e1, &e2->left.expr); |
569 | expr_eliminate_dups2(type, &e1, &e2->right.expr); |
570 | } |
571 | if (e1 == e2) |
572 | return; |
573 | |
574 | switch (e1->type) { |
575 | case E_OR: |
576 | expr_eliminate_dups2(e1->type, &e1, &e1); |
577 | // (FOO || BAR) && (!FOO && !BAR) -> n |
578 | tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1))); |
579 | tmp2 = expr_copy(e2); |
580 | tmp = expr_extract_eq_and(&tmp1, &tmp2); |
581 | if (expr_is_yes(tmp1)) { |
582 | expr_free(e1); |
583 | e1 = expr_alloc_symbol(&symbol_no); |
584 | trans_count++; |
585 | } |
586 | expr_free(tmp2); |
587 | expr_free(tmp1); |
588 | expr_free(tmp); |
589 | break; |
590 | case E_AND: |
591 | expr_eliminate_dups2(e1->type, &e1, &e1); |
592 | // (FOO && BAR) || (!FOO || !BAR) -> y |
593 | tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1))); |
594 | tmp2 = expr_copy(e2); |
595 | tmp = expr_extract_eq_or(&tmp1, &tmp2); |
596 | if (expr_is_no(tmp1)) { |
597 | expr_free(e1); |
598 | e1 = expr_alloc_symbol(&symbol_yes); |
599 | trans_count++; |
600 | } |
601 | expr_free(tmp2); |
602 | expr_free(tmp1); |
603 | expr_free(tmp); |
604 | break; |
605 | default: |
606 | ; |
607 | } |
608 | #undef e1 |
609 | #undef e2 |
610 | } |
611 | |
612 | struct expr *expr_eliminate_dups(struct expr *e) |
613 | { |
614 | int oldcount; |
615 | if (!e) |
616 | return e; |
617 | |
618 | oldcount = trans_count; |
619 | while (1) { |
620 | trans_count = 0; |
621 | switch (e->type) { |
622 | case E_OR: case E_AND: |
623 | expr_eliminate_dups1(e->type, &e, &e); |
624 | expr_eliminate_dups2(e->type, &e, &e); |
625 | default: |
626 | ; |
627 | } |
628 | if (!trans_count) |
629 | break; |
630 | e = expr_eliminate_yn(e); |
631 | } |
632 | trans_count = oldcount; |
633 | return e; |
634 | } |
635 | |
636 | struct expr *expr_transform(struct expr *e) |
637 | { |
638 | struct expr *tmp; |
639 | |
640 | if (!e) |
641 | return NULL; |
642 | switch (e->type) { |
643 | case E_EQUAL: |
644 | case E_UNEQUAL: |
645 | case E_SYMBOL: |
646 | case E_LIST: |
647 | break; |
648 | default: |
649 | e->left.expr = expr_transform(e->left.expr); |
650 | e->right.expr = expr_transform(e->right.expr); |
651 | } |
652 | |
653 | switch (e->type) { |
654 | case E_EQUAL: |
655 | if (e->left.sym->type != S_BOOLEAN) |
656 | break; |
657 | if (e->right.sym == &symbol_no) { |
658 | e->type = E_NOT; |
659 | e->left.expr = expr_alloc_symbol(e->left.sym); |
660 | e->right.sym = NULL; |
661 | break; |
662 | } |
663 | if (e->right.sym == &symbol_mod) { |
664 | printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name); |
665 | e->type = E_SYMBOL; |
666 | e->left.sym = &symbol_no; |
667 | e->right.sym = NULL; |
668 | break; |
669 | } |
670 | if (e->right.sym == &symbol_yes) { |
671 | e->type = E_SYMBOL; |
672 | e->right.sym = NULL; |
673 | break; |
674 | } |
675 | break; |
676 | case E_UNEQUAL: |
677 | if (e->left.sym->type != S_BOOLEAN) |
678 | break; |
679 | if (e->right.sym == &symbol_no) { |
680 | e->type = E_SYMBOL; |
681 | e->right.sym = NULL; |
682 | break; |
683 | } |
684 | if (e->right.sym == &symbol_mod) { |
685 | printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name); |
686 | e->type = E_SYMBOL; |
687 | e->left.sym = &symbol_yes; |
688 | e->right.sym = NULL; |
689 | break; |
690 | } |
691 | if (e->right.sym == &symbol_yes) { |
692 | e->type = E_NOT; |
693 | e->left.expr = expr_alloc_symbol(e->left.sym); |
694 | e->right.sym = NULL; |
695 | break; |
696 | } |
697 | break; |
698 | case E_NOT: |
699 | switch (e->left.expr->type) { |
700 | case E_NOT: |
701 | // !!a -> a |
702 | tmp = e->left.expr->left.expr; |
703 | free(e->left.expr); |
704 | free(e); |
705 | e = tmp; |
706 | e = expr_transform(e); |
707 | break; |
708 | case E_EQUAL: |
709 | case E_UNEQUAL: |
710 | // !a='x' -> a!='x' |
711 | tmp = e->left.expr; |
712 | free(e); |
713 | e = tmp; |
714 | e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL; |
715 | break; |
716 | case E_OR: |
717 | // !(a || b) -> !a && !b |
718 | tmp = e->left.expr; |
719 | e->type = E_AND; |
720 | e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); |
721 | tmp->type = E_NOT; |
722 | tmp->right.expr = NULL; |
723 | e = expr_transform(e); |
724 | break; |
725 | case E_AND: |
726 | // !(a && b) -> !a || !b |
727 | tmp = e->left.expr; |
728 | e->type = E_OR; |
729 | e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); |
730 | tmp->type = E_NOT; |
731 | tmp->right.expr = NULL; |
732 | e = expr_transform(e); |
733 | break; |
734 | case E_SYMBOL: |
735 | if (e->left.expr->left.sym == &symbol_yes) { |
736 | // !'y' -> 'n' |
737 | tmp = e->left.expr; |
738 | free(e); |
739 | e = tmp; |
740 | e->type = E_SYMBOL; |
741 | e->left.sym = &symbol_no; |
742 | break; |
743 | } |
744 | if (e->left.expr->left.sym == &symbol_mod) { |
745 | // !'m' -> 'm' |
746 | tmp = e->left.expr; |
747 | free(e); |
748 | e = tmp; |
749 | e->type = E_SYMBOL; |
750 | e->left.sym = &symbol_mod; |
751 | break; |
752 | } |
753 | if (e->left.expr->left.sym == &symbol_no) { |
754 | // !'n' -> 'y' |
755 | tmp = e->left.expr; |
756 | free(e); |
757 | e = tmp; |
758 | e->type = E_SYMBOL; |
759 | e->left.sym = &symbol_yes; |
760 | break; |
761 | } |
762 | break; |
763 | default: |
764 | ; |
765 | } |
766 | break; |
767 | default: |
768 | ; |
769 | } |
770 | return e; |
771 | } |
772 | |
773 | int expr_contains_symbol(struct expr *dep, struct symbol *sym) |
774 | { |
775 | if (!dep) |
776 | return 0; |
777 | |
778 | switch (dep->type) { |
779 | case E_AND: |
780 | case E_OR: |
781 | return expr_contains_symbol(dep->left.expr, sym) || |
782 | expr_contains_symbol(dep->right.expr, sym); |
783 | case E_SYMBOL: |
784 | return dep->left.sym == sym; |
785 | case E_EQUAL: |
786 | case E_UNEQUAL: |
787 | return dep->left.sym == sym || |
788 | dep->right.sym == sym; |
789 | case E_NOT: |
790 | return expr_contains_symbol(dep->left.expr, sym); |
791 | default: |
792 | ; |
793 | } |
794 | return 0; |
795 | } |
796 | |
797 | bool expr_depends_symbol(struct expr *dep, struct symbol *sym) |
798 | { |
799 | if (!dep) |
800 | return false; |
801 | |
802 | switch (dep->type) { |
803 | case E_AND: |
804 | return expr_depends_symbol(dep->left.expr, sym) || |
805 | expr_depends_symbol(dep->right.expr, sym); |
806 | case E_SYMBOL: |
807 | return dep->left.sym == sym; |
808 | case E_EQUAL: |
809 | if (dep->left.sym == sym) { |
810 | if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod) |
811 | return true; |
812 | } |
813 | break; |
814 | case E_UNEQUAL: |
815 | if (dep->left.sym == sym) { |
816 | if (dep->right.sym == &symbol_no) |
817 | return true; |
818 | } |
819 | break; |
820 | default: |
821 | ; |
822 | } |
823 | return false; |
824 | } |
825 | |
826 | struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2) |
827 | { |
828 | struct expr *tmp = NULL; |
829 | expr_extract_eq(E_AND, &tmp, ep1, ep2); |
830 | if (tmp) { |
831 | *ep1 = expr_eliminate_yn(*ep1); |
832 | *ep2 = expr_eliminate_yn(*ep2); |
833 | } |
834 | return tmp; |
835 | } |
836 | |
837 | struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2) |
838 | { |
839 | struct expr *tmp = NULL; |
840 | expr_extract_eq(E_OR, &tmp, ep1, ep2); |
841 | if (tmp) { |
842 | *ep1 = expr_eliminate_yn(*ep1); |
843 | *ep2 = expr_eliminate_yn(*ep2); |
844 | } |
845 | return tmp; |
846 | } |
847 | |
848 | void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2) |
849 | { |
850 | #define e1 (*ep1) |
851 | #define e2 (*ep2) |
852 | if (e1->type == type) { |
853 | expr_extract_eq(type, ep, &e1->left.expr, &e2); |
854 | expr_extract_eq(type, ep, &e1->right.expr, &e2); |
855 | return; |
856 | } |
857 | if (e2->type == type) { |
858 | expr_extract_eq(type, ep, ep1, &e2->left.expr); |
859 | expr_extract_eq(type, ep, ep1, &e2->right.expr); |
860 | return; |
861 | } |
862 | if (expr_eq(e1, e2)) { |
863 | *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1; |
864 | expr_free(e2); |
865 | if (type == E_AND) { |
866 | e1 = expr_alloc_symbol(&symbol_yes); |
867 | e2 = expr_alloc_symbol(&symbol_yes); |
868 | } else if (type == E_OR) { |
869 | e1 = expr_alloc_symbol(&symbol_no); |
870 | e2 = expr_alloc_symbol(&symbol_no); |
871 | } |
872 | } |
873 | #undef e1 |
874 | #undef e2 |
875 | } |
876 | |
877 | struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym) |
878 | { |
879 | struct expr *e1, *e2; |
880 | |
881 | if (!e) { |
882 | e = expr_alloc_symbol(sym); |
883 | if (type == E_UNEQUAL) |
884 | e = expr_alloc_one(E_NOT, e); |
885 | return e; |
886 | } |
887 | switch (e->type) { |
888 | case E_AND: |
889 | e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); |
890 | e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); |
891 | if (sym == &symbol_yes) |
892 | e = expr_alloc_two(E_AND, e1, e2); |
893 | if (sym == &symbol_no) |
894 | e = expr_alloc_two(E_OR, e1, e2); |
895 | if (type == E_UNEQUAL) |
896 | e = expr_alloc_one(E_NOT, e); |
897 | return e; |
898 | case E_OR: |
899 | e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); |
900 | e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); |
901 | if (sym == &symbol_yes) |
902 | e = expr_alloc_two(E_OR, e1, e2); |
903 | if (sym == &symbol_no) |
904 | e = expr_alloc_two(E_AND, e1, e2); |
905 | if (type == E_UNEQUAL) |
906 | e = expr_alloc_one(E_NOT, e); |
907 | return e; |
908 | case E_NOT: |
909 | return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym); |
910 | case E_UNEQUAL: |
911 | case E_EQUAL: |
912 | if (type == E_EQUAL) { |
913 | if (sym == &symbol_yes) |
914 | return expr_copy(e); |
915 | if (sym == &symbol_mod) |
916 | return expr_alloc_symbol(&symbol_no); |
917 | if (sym == &symbol_no) |
918 | return expr_alloc_one(E_NOT, expr_copy(e)); |
919 | } else { |
920 | if (sym == &symbol_yes) |
921 | return expr_alloc_one(E_NOT, expr_copy(e)); |
922 | if (sym == &symbol_mod) |
923 | return expr_alloc_symbol(&symbol_yes); |
924 | if (sym == &symbol_no) |
925 | return expr_copy(e); |
926 | } |
927 | break; |
928 | case E_SYMBOL: |
929 | return expr_alloc_comp(type, e->left.sym, sym); |
930 | case E_LIST: |
931 | case E_RANGE: |
932 | case E_NONE: |
933 | /* panic */; |
934 | } |
935 | return NULL; |
936 | } |
937 | |
938 | tristate expr_calc_value(struct expr *e) |
939 | { |
940 | tristate val1, val2; |
941 | const char *str1, *str2; |
942 | |
943 | if (!e) |
944 | return yes; |
945 | |
946 | switch (e->type) { |
947 | case E_SYMBOL: |
948 | sym_calc_value(e->left.sym); |
949 | return e->left.sym->curr.tri; |
950 | case E_AND: |
951 | val1 = expr_calc_value(e->left.expr); |
952 | val2 = expr_calc_value(e->right.expr); |
953 | return EXPR_AND(val1, val2); |
954 | case E_OR: |
955 | val1 = expr_calc_value(e->left.expr); |
956 | val2 = expr_calc_value(e->right.expr); |
957 | return EXPR_OR(val1, val2); |
958 | case E_NOT: |
959 | val1 = expr_calc_value(e->left.expr); |
960 | return EXPR_NOT(val1); |
961 | case E_EQUAL: |
962 | sym_calc_value(e->left.sym); |
963 | sym_calc_value(e->right.sym); |
964 | str1 = sym_get_string_value(e->left.sym); |
965 | str2 = sym_get_string_value(e->right.sym); |
966 | return !strcmp(str1, str2) ? yes : no; |
967 | case E_UNEQUAL: |
968 | sym_calc_value(e->left.sym); |
969 | sym_calc_value(e->right.sym); |
970 | str1 = sym_get_string_value(e->left.sym); |
971 | str2 = sym_get_string_value(e->right.sym); |
972 | return !strcmp(str1, str2) ? no : yes; |
973 | default: |
974 | printf("expr_calc_value: %d?\n", e->type); |
975 | return no; |
976 | } |
977 | } |
978 | |
979 | int expr_compare_type(enum expr_type t1, enum expr_type t2) |
980 | { |
981 | #if 0 |
982 | return 1; |
983 | #else |
984 | if (t1 == t2) |
985 | return 0; |
986 | switch (t1) { |
987 | case E_EQUAL: |
988 | case E_UNEQUAL: |
989 | if (t2 == E_NOT) |
990 | return 1; |
991 | case E_NOT: |
992 | if (t2 == E_AND) |
993 | return 1; |
994 | case E_AND: |
995 | if (t2 == E_OR) |
996 | return 1; |
997 | case E_OR: |
998 | if (t2 == E_LIST) |
999 | return 1; |
1000 | case E_LIST: |
1001 | if (t2 == 0) |
1002 | return 1; |
1003 | default: |
1004 | return -1; |
1005 | } |
1006 | printf("[%dgt%d?]", t1, t2); |
1007 | return 0; |
1008 | #endif |
1009 | } |
1010 | |
1011 | static inline struct expr * |
1012 | expr_get_leftmost_symbol(const struct expr *e) |
1013 | { |
1014 | |
1015 | if (e == NULL) |
1016 | return NULL; |
1017 | |
1018 | while (e->type != E_SYMBOL) |
1019 | e = e->left.expr; |
1020 | |
1021 | return expr_copy(e); |
1022 | } |
1023 | |
1024 | /* |
1025 | * Given expression `e1' and `e2', returns the leaf of the longest |
1026 | * sub-expression of `e1' not containing 'e2. |
1027 | */ |
1028 | struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2) |
1029 | { |
1030 | struct expr *ret; |
1031 | |
1032 | switch (e1->type) { |
1033 | case E_OR: |
1034 | return expr_alloc_and( |
1035 | expr_simplify_unmet_dep(e1->left.expr, e2), |
1036 | expr_simplify_unmet_dep(e1->right.expr, e2)); |
1037 | case E_AND: { |
1038 | struct expr *e; |
1039 | e = expr_alloc_and(expr_copy(e1), expr_copy(e2)); |
1040 | e = expr_eliminate_dups(e); |
1041 | ret = (!expr_eq(e, e1)) ? e1 : NULL; |
1042 | expr_free(e); |
1043 | break; |
1044 | } |
1045 | default: |
1046 | ret = e1; |
1047 | break; |
1048 | } |
1049 | |
1050 | return expr_get_leftmost_symbol(ret); |
1051 | } |
1052 | |
1053 | void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken) |
1054 | { |
1055 | if (!e) { |
1056 | fn(data, NULL, "y"); |
1057 | return; |
1058 | } |
1059 | |
1060 | if (expr_compare_type(prevtoken, e->type) > 0) |
1061 | fn(data, NULL, "("); |
1062 | switch (e->type) { |
1063 | case E_SYMBOL: |
1064 | if (e->left.sym->name) |
1065 | fn(data, e->left.sym, e->left.sym->name); |
1066 | else |
1067 | fn(data, NULL, "<choice>"); |
1068 | break; |
1069 | case E_NOT: |
1070 | fn(data, NULL, "!"); |
1071 | expr_print(e->left.expr, fn, data, E_NOT); |
1072 | break; |
1073 | case E_EQUAL: |
1074 | if (e->left.sym->name) |
1075 | fn(data, e->left.sym, e->left.sym->name); |
1076 | else |
1077 | fn(data, NULL, "<choice>"); |
1078 | fn(data, NULL, "="); |
1079 | fn(data, e->right.sym, e->right.sym->name); |
1080 | break; |
1081 | case E_UNEQUAL: |
1082 | if (e->left.sym->name) |
1083 | fn(data, e->left.sym, e->left.sym->name); |
1084 | else |
1085 | fn(data, NULL, "<choice>"); |
1086 | fn(data, NULL, "!="); |
1087 | fn(data, e->right.sym, e->right.sym->name); |
1088 | break; |
1089 | case E_OR: |
1090 | expr_print(e->left.expr, fn, data, E_OR); |
1091 | fn(data, NULL, " || "); |
1092 | expr_print(e->right.expr, fn, data, E_OR); |
1093 | break; |
1094 | case E_AND: |
1095 | expr_print(e->left.expr, fn, data, E_AND); |
1096 | fn(data, NULL, " && "); |
1097 | expr_print(e->right.expr, fn, data, E_AND); |
1098 | break; |
1099 | case E_LIST: |
1100 | fn(data, e->right.sym, e->right.sym->name); |
1101 | if (e->left.expr) { |
1102 | fn(data, NULL, " ^ "); |
1103 | expr_print(e->left.expr, fn, data, E_LIST); |
1104 | } |
1105 | break; |
1106 | case E_RANGE: |
1107 | fn(data, NULL, "["); |
1108 | fn(data, e->left.sym, e->left.sym->name); |
1109 | fn(data, NULL, " "); |
1110 | fn(data, e->right.sym, e->right.sym->name); |
1111 | fn(data, NULL, "]"); |
1112 | break; |
1113 | default: |
1114 | { |
1115 | char buf[32]; |
1116 | sprintf(buf, "<unknown type %d>", e->type); |
1117 | fn(data, NULL, buf); |
1118 | break; |
1119 | } |
1120 | } |
1121 | if (expr_compare_type(prevtoken, e->type) > 0) |
1122 | fn(data, NULL, ")"); |
1123 | } |
1124 | |
1125 | static void expr_print_file_helper(void *data, struct symbol *sym, const char *str) |
1126 | { |
1127 | xfwrite(str, strlen(str), 1, data); |
1128 | } |
1129 | |
1130 | void expr_fprint(struct expr *e, FILE *out) |
1131 | { |
1132 | expr_print(e, expr_print_file_helper, out, E_NONE); |
1133 | } |
1134 | |
1135 | static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str) |
1136 | { |
1137 | struct gstr *gs = (struct gstr*)data; |
1138 | const char *sym_str = NULL; |
1139 | |
1140 | if (sym) |
1141 | sym_str = sym_get_string_value(sym); |
1142 | |
1143 | if (gs->max_width) { |
1144 | unsigned extra_length = strlen(str); |
1145 | const char *last_cr = strrchr(gs->s, '\n'); |
1146 | unsigned last_line_length; |
1147 | |
1148 | if (sym_str) |
1149 | extra_length += 4 + strlen(sym_str); |
1150 | |
1151 | if (!last_cr) |
1152 | last_cr = gs->s; |
1153 | |
1154 | last_line_length = strlen(gs->s) - (last_cr - gs->s); |
1155 | |
1156 | if ((last_line_length + extra_length) > gs->max_width) |
1157 | str_append(gs, "\\\n"); |
1158 | } |
1159 | |
1160 | str_append(gs, str); |
1161 | if (sym && sym->type != S_UNKNOWN) |
1162 | str_printf(gs, " [=%s]", sym_str); |
1163 | } |
1164 | |
1165 | void expr_gstr_print(struct expr *e, struct gstr *gs) |
1166 | { |
1167 | expr_print(e, expr_print_gstr_helper, gs, E_NONE); |
1168 | } |
1169 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9