Print this page
11972 resync smatch
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/smatch_ranges.c
+++ new/usr/src/tools/smatch/src/smatch_ranges.c
1 1 /*
2 2 * Copyright (C) 2009 Dan Carpenter.
3 3 *
4 4 * This program is free software; you can redistribute it and/or
5 5 * modify it under the terms of the GNU General Public License
6 6 * as published by the Free Software Foundation; either version 2
7 7 * of the License, or (at your option) any later version.
8 8 *
9 9 * This program is distributed in the hope that it will be useful,
10 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 12 * GNU General Public License for more details.
13 13 *
14 14 * You should have received a copy of the GNU General Public License
15 15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 16 */
17 17
18 18 #include "parse.h"
|
↓ open down ↓ |
18 lines elided |
↑ open up ↑ |
19 19 #include "smatch.h"
20 20 #include "smatch_extra.h"
21 21 #include "smatch_slist.h"
22 22
23 23 ALLOCATOR(data_info, "smatch extra data");
24 24 ALLOCATOR(data_range, "data range");
25 25 __DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
26 26 "permanent ranges", perm_data_range);
27 27 __DECLARE_ALLOCATOR(struct ptr_list, rl_ptrlist);
28 28
29 -static bool is_err_ptr(sval_t sval)
29 +bool is_err_ptr(sval_t sval)
30 30 {
31 31 if (option_project != PROJ_KERNEL)
32 32 return false;
33 33 if (!type_is_ptr(sval.type))
34 34 return false;
35 35 if (sval.uvalue < -4095ULL)
36 36 return false;
37 37 return true;
38 38 }
39 39
40 40 static char *get_err_pointer_str(struct data_range *drange)
41 41 {
42 42 static char buf[20];
43 43
44 44 /*
45 45 * The kernel has error pointers where you do essentially:
46 46 *
47 47 * return (void *)(unsigned long)-12;
48 48 *
49 49 * But what I want here is to print -12 instead of the unsigned version
50 50 * of that.
51 51 *
52 52 */
53 53 if (!is_err_ptr(drange->min))
54 54 return NULL;
55 55
56 56 if (drange->min.value == drange->max.value)
57 57 snprintf(buf, sizeof(buf), "(%lld)", drange->min.value);
58 58 else
59 59 snprintf(buf, sizeof(buf), "(%lld)-(%lld)", drange->min.value, drange->max.value);
60 60 return buf;
61 61 }
62 62
63 63 char *show_rl(struct range_list *list)
64 64 {
65 65 struct data_range *prev_drange = NULL;
66 66 struct data_range *tmp;
67 67 char full[255];
68 68 char *p = full;
69 69 char *prev = full;
70 70 char *err_ptr;
71 71 int remain;
72 72 int i = 0;
73 73
74 74 full[0] = '\0';
75 75
76 76 FOR_EACH_PTR(list, tmp) {
77 77 remain = full + sizeof(full) - p;
78 78 if (remain < 48) {
79 79 snprintf(prev, full + sizeof(full) - prev, ",%s-%s",
80 80 sval_to_str(prev_drange->min),
81 81 sval_to_str(sval_type_max(prev_drange->min.type)));
82 82 break;
83 83 }
84 84 prev_drange = tmp;
85 85 prev = p;
86 86
87 87 err_ptr = get_err_pointer_str(tmp);
88 88 if (err_ptr) {
89 89 p += snprintf(p, remain, "%s%s", i++ ? "," : "", err_ptr);
90 90 } else if (sval_cmp(tmp->min, tmp->max) == 0) {
91 91 p += snprintf(p, remain, "%s%s", i++ ? "," : "",
92 92 sval_to_str(tmp->min));
93 93 } else {
94 94 p += snprintf(p, remain, "%s%s-%s", i++ ? "," : "",
95 95 sval_to_str(tmp->min),
96 96 sval_to_str(tmp->max));
97 97 }
98 98 } END_FOR_EACH_PTR(tmp);
99 99
100 100 return alloc_sname(full);
101 101 }
102 102
103 103 void free_all_rl(void)
104 104 {
105 105 clear_rl_ptrlist_alloc();
106 106 }
107 107
108 108 static int sval_too_big(struct symbol *type, sval_t sval)
109 109 {
110 110 if (type_bits(type) >= 32 &&
111 111 type_bits(sval.type) <= type_bits(type))
112 112 return 0;
113 113 if (sval.uvalue <= ((1ULL << type_bits(type)) - 1))
114 114 return 0;
115 115 if (type_signed(sval.type)) {
116 116 if (type_unsigned(type)) {
117 117 unsigned long long neg = ~sval.uvalue;
118 118 if (neg <= sval_type_max(type).uvalue)
119 119 return 0;
120 120 }
121 121 if (sval.value < sval_type_min(type).value)
122 122 return 1;
123 123 if (sval.value > sval_type_max(type).value)
124 124 return 1;
125 125 return 0;
126 126 }
127 127 if (sval.uvalue > sval_type_max(type).uvalue)
128 128 return 1;
129 129 return 0;
130 130 }
131 131
132 132 static int truncates_nicely(struct symbol *type, sval_t min, sval_t max)
133 133 {
134 134 unsigned long long mask;
135 135 int bits = type_bits(type);
136 136
137 137 if (bits >= type_bits(min.type))
138 138 return 0;
139 139
140 140 mask = -1ULL << bits;
141 141 return (min.uvalue & mask) == (max.uvalue & mask);
142 142 }
143 143
144 144 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
145 145 {
146 146 /* If we're just adding a number, cast it and add it */
147 147 if (sval_cmp(min, max) == 0) {
148 148 add_range(rl, sval_cast(type, min), sval_cast(type, max));
149 149 return;
150 150 }
151 151
152 152 /* If the range is within the type range then add it */
153 153 if (sval_fits(type, min) && sval_fits(type, max)) {
154 154 add_range(rl, sval_cast(type, min), sval_cast(type, max));
155 155 return;
156 156 }
157 157
158 158 if (truncates_nicely(type, min, max)) {
159 159 add_range(rl, sval_cast(type, min), sval_cast(type, max));
160 160 return;
161 161 }
162 162
163 163 /*
164 164 * If the range we are adding has more bits than the range type then
165 165 * add the whole range type. Eg:
166 166 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
167 167 *
168 168 */
169 169 if (sval_too_big(type, min) || sval_too_big(type, max)) {
170 170 add_range(rl, sval_type_min(type), sval_type_max(type));
171 171 return;
172 172 }
173 173
174 174 /* Cast negative values to high positive values */
175 175 if (sval_is_negative(min) && type_unsigned(type)) {
176 176 if (sval_is_positive(max)) {
177 177 if (sval_too_high(type, max)) {
178 178 add_range(rl, sval_type_min(type), sval_type_max(type));
179 179 return;
180 180 }
181 181 add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
182 182 max = sval_type_max(type);
183 183 } else {
184 184 max = sval_cast(type, max);
185 185 }
186 186 min = sval_cast(type, min);
187 187 add_range(rl, min, max);
188 188 }
189 189
190 190 /* Cast high positive numbers to negative */
191 191 if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
192 192 if (!sval_is_negative(sval_cast(type, min))) {
193 193 add_range(rl, sval_cast(type, min), sval_type_max(type));
194 194 min = sval_type_min(type);
195 195 } else {
196 196 min = sval_cast(type, min);
197 197 }
198 198 max = sval_cast(type, max);
199 199 add_range(rl, min, max);
200 200 }
201 201
202 202 add_range(rl, sval_cast(type, min), sval_cast(type, max));
203 203 return;
204 204 }
205 205
206 206 static int str_to_comparison_arg_helper(const char *str,
207 207 struct expression *call, int *comparison,
208 208 struct expression **arg, const char **endp)
209 209 {
210 210 int param;
211 211 const char *c = str;
212 212
213 213 if (*c != '[')
214 214 return 0;
215 215 c++;
216 216
217 217 if (*c == '<') {
218 218 c++;
219 219 if (*c == '=') {
220 220 *comparison = SPECIAL_LTE;
221 221 c++;
222 222 } else {
223 223 *comparison = '<';
224 224 }
225 225 } else if (*c == '=') {
226 226 c++;
227 227 c++;
228 228 *comparison = SPECIAL_EQUAL;
229 229 } else if (*c == '>') {
230 230 c++;
231 231 if (*c == '=') {
232 232 *comparison = SPECIAL_GTE;
233 233 c++;
234 234 } else {
235 235 *comparison = '>';
236 236 }
237 237 } else if (*c == '!') {
238 238 c++;
239 239 c++;
240 240 *comparison = SPECIAL_NOTEQUAL;
241 241 } else if (*c == '$') {
|
↓ open down ↓ |
202 lines elided |
↑ open up ↑ |
242 242 *comparison = SPECIAL_EQUAL;
243 243 } else {
244 244 return 0;
245 245 }
246 246
247 247 if (*c != '$')
248 248 return 0;
249 249 c++;
250 250
251 251 param = strtoll(c, (char **)&c, 10);
252 + /*
253 + * FIXME: handle parameter math. [==$1 + 100]
254 + *
255 + */
256 + if (*c == ' ')
257 + return 0;
258 +
252 259 if (*c == ',' || *c == ']')
253 260 c++; /* skip the ']' character */
254 261 if (endp)
255 262 *endp = (char *)c;
256 263
257 264 if (!call)
258 265 return 0;
259 266 *arg = get_argument_from_call_expr(call->args, param);
260 267 if (!*arg)
261 268 return 0;
262 269 if (*c == '-' && *(c + 1) == '>') {
263 270 char buf[256];
264 271 int n;
265 272
266 273 n = snprintf(buf, sizeof(buf), "$%s", c);
267 274 if (n >= sizeof(buf))
268 275 return 0;
269 276 if (buf[n - 1] == ']')
270 277 buf[n - 1] = '\0';
271 278 *arg = gen_expression_from_key(*arg, buf);
272 279 while (*c && *c != ']')
273 280 c++;
274 281 }
275 282 return 1;
276 283 }
277 284
278 285 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
279 286 {
280 287 while (1) {
281 288 if (!*str)
282 289 return 0;
283 290 if (*str == '[')
284 291 break;
285 292 str++;
286 293 }
287 294 return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
288 295 }
289 296
290 297 static int get_val_from_key(int use_max, struct symbol *type, const char *c, struct expression *call, const char **endp, sval_t *sval)
291 298 {
292 299 struct expression *arg;
293 300 int comparison;
294 301 sval_t ret, tmp;
295 302
296 303 if (use_max)
297 304 ret = sval_type_max(type);
298 305 else
299 306 ret = sval_type_min(type);
300 307
301 308 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp)) {
302 309 *sval = ret;
303 310 return 0;
304 311 }
305 312
306 313 if (use_max && get_implied_max(arg, &tmp)) {
307 314 ret = tmp;
308 315 if (comparison == '<') {
309 316 tmp.value = 1;
310 317 ret = sval_binop(ret, '-', tmp);
311 318 }
312 319 }
313 320 if (!use_max && get_implied_min(arg, &tmp)) {
314 321 ret = tmp;
315 322 if (comparison == '>') {
316 323 tmp.value = 1;
317 324 ret = sval_binop(ret, '+', tmp);
318 325 }
319 326 }
320 327
321 328 *sval = ret;
322 329 return 1;
323 330 }
324 331
325 332 static sval_t add_one(sval_t sval)
326 333 {
327 334 sval.value++;
328 335 return sval;
329 336 }
330 337
331 338 static sval_t sub_one(sval_t sval)
332 339 {
333 340 sval.value--;
334 341 return sval;
|
↓ open down ↓ |
73 lines elided |
↑ open up ↑ |
335 342 }
336 343
337 344 void filter_by_comparison(struct range_list **rl, int comparison, struct range_list *right)
338 345 {
339 346 struct range_list *left_orig = *rl;
340 347 struct range_list *right_orig = right;
341 348 struct range_list *ret_rl = *rl;
342 349 struct symbol *cast_type;
343 350 sval_t min, max;
344 351
352 + if (comparison == UNKNOWN_COMPARISON)
353 + return;
354 +
345 355 cast_type = rl_type(left_orig);
346 356 if (sval_type_max(rl_type(left_orig)).uvalue < sval_type_max(rl_type(right_orig)).uvalue)
347 357 cast_type = rl_type(right_orig);
348 358 if (sval_type_max(cast_type).uvalue < INT_MAX)
349 359 cast_type = &int_ctype;
350 360
351 361 min = sval_type_min(cast_type);
352 362 max = sval_type_max(cast_type);
353 363 left_orig = cast_rl(cast_type, left_orig);
354 364 right_orig = cast_rl(cast_type, right_orig);
355 365
356 366 switch (comparison) {
357 367 case '<':
358 368 case SPECIAL_UNSIGNED_LT:
359 369 ret_rl = remove_range(left_orig, rl_max(right_orig), max);
360 370 break;
361 371 case SPECIAL_LTE:
362 372 case SPECIAL_UNSIGNED_LTE:
363 373 if (!sval_is_max(rl_max(right_orig)))
364 374 ret_rl = remove_range(left_orig, add_one(rl_max(right_orig)), max);
365 375 break;
366 376 case SPECIAL_EQUAL:
367 377 ret_rl = rl_intersection(left_orig, right_orig);
368 378 break;
369 379 case SPECIAL_GTE:
370 380 case SPECIAL_UNSIGNED_GTE:
371 381 if (!sval_is_min(rl_min(right_orig)))
372 382 ret_rl = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
373 383 break;
374 384 case '>':
375 385 case SPECIAL_UNSIGNED_GT:
376 386 ret_rl = remove_range(left_orig, min, rl_min(right_orig));
377 387 break;
378 388 case SPECIAL_NOTEQUAL:
379 389 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
380 390 ret_rl = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
381 391 break;
382 392 default:
383 393 sm_perror("unhandled comparison %s", show_special(comparison));
384 394 return;
385 395 }
386 396
|
↓ open down ↓ |
32 lines elided |
↑ open up ↑ |
387 397 *rl = cast_rl(rl_type(*rl), ret_rl);
388 398 }
389 399
390 400 static struct range_list *filter_by_comparison_call(const char *c, struct expression *call, const char **endp, struct range_list *start_rl)
391 401 {
392 402 struct symbol *type;
393 403 struct expression *arg;
394 404 struct range_list *casted_start, *right_orig;
395 405 int comparison;
396 406
407 + /* For when we have a function that takes a function pointer. */
408 + if (!call || call->type != EXPR_CALL)
409 + return start_rl;
410 +
397 411 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
398 412 return start_rl;
399 413
400 414 if (!get_implied_rl(arg, &right_orig))
401 415 return start_rl;
402 416
403 417 type = &int_ctype;
404 418 if (type_positive_bits(rl_type(start_rl)) > type_positive_bits(type))
405 419 type = rl_type(start_rl);
406 420 if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
407 421 type = rl_type(right_orig);
408 422
409 423 casted_start = cast_rl(type, start_rl);
410 424 right_orig = cast_rl(type, right_orig);
411 425
412 426 filter_by_comparison(&casted_start, comparison, right_orig);
413 427 return cast_rl(rl_type(start_rl), casted_start);
414 428 }
415 429
416 430 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, const char *c, const char **endp)
417 431 {
418 432 const char *start = c;
419 433 sval_t ret;
420 434
421 435 if (!strncmp(start, "max", 3)) {
422 436 ret = sval_type_max(type);
423 437 c += 3;
424 438 } else if (!strncmp(start, "u64max", 6)) {
425 439 ret = sval_type_val(type, ULLONG_MAX);
426 440 c += 6;
427 441 } else if (!strncmp(start, "s64max", 6)) {
428 442 ret = sval_type_val(type, LLONG_MAX);
429 443 c += 6;
430 444 } else if (!strncmp(start, "u32max", 6)) {
431 445 ret = sval_type_val(type, UINT_MAX);
432 446 c += 6;
433 447 } else if (!strncmp(start, "s32max", 6)) {
434 448 ret = sval_type_val(type, INT_MAX);
435 449 c += 6;
436 450 } else if (!strncmp(start, "u16max", 6)) {
437 451 ret = sval_type_val(type, USHRT_MAX);
438 452 c += 6;
439 453 } else if (!strncmp(start, "s16max", 6)) {
440 454 ret = sval_type_val(type, SHRT_MAX);
441 455 c += 6;
442 456 } else if (!strncmp(start, "min", 3)) {
443 457 ret = sval_type_min(type);
444 458 c += 3;
445 459 } else if (!strncmp(start, "s64min", 6)) {
446 460 ret = sval_type_val(type, LLONG_MIN);
447 461 c += 6;
448 462 } else if (!strncmp(start, "s32min", 6)) {
449 463 ret = sval_type_val(type, INT_MIN);
450 464 c += 6;
451 465 } else if (!strncmp(start, "s16min", 6)) {
452 466 ret = sval_type_val(type, SHRT_MIN);
453 467 c += 6;
454 468 } else if (!strncmp(start, "long_min", 8)) {
455 469 ret = sval_type_val(type, LONG_MIN);
456 470 c += 8;
457 471 } else if (!strncmp(start, "long_max", 8)) {
458 472 ret = sval_type_val(type, LONG_MAX);
459 473 c += 8;
460 474 } else if (!strncmp(start, "ulong_max", 9)) {
461 475 ret = sval_type_val(type, ULONG_MAX);
462 476 c += 9;
463 477 } else if (!strncmp(start, "ptr_max", 7)) {
464 478 ret = sval_type_val(type, valid_ptr_max);
465 479 c += 7;
466 480 } else if (start[0] == '[') {
467 481 /* this parses [==p0] comparisons */
468 482 get_val_from_key(1, type, start, call, &c, &ret);
469 483 } else if (type_positive_bits(type) == 64) {
470 484 ret = sval_type_val(type, strtoull(start, (char **)&c, 0));
471 485 } else {
472 486 ret = sval_type_val(type, strtoll(start, (char **)&c, 0));
473 487 }
474 488 *endp = c;
475 489 return ret;
476 490 }
477 491
478 492 static const char *jump_to_call_math(const char *value)
479 493 {
480 494 const char *c = value;
481 495
482 496 while (*c && *c != '[')
483 497 c++;
|
↓ open down ↓ |
77 lines elided |
↑ open up ↑ |
484 498
485 499 if (!*c)
486 500 return NULL;
487 501 c++;
488 502 if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
489 503 return NULL;
490 504
491 505 return c;
492 506 }
493 507
508 +static struct range_list *get_param_return_rl(struct expression *call, const char *call_math)
509 +{
510 + struct expression *arg;
511 + int param;
512 +
513 + call_math += 3;
514 + param = atoi(call_math);
515 +
516 + arg = get_argument_from_call_expr(call->args, param);
517 + if (!arg)
518 + return NULL;
519 +
520 + return db_return_vals_no_args(arg);
521 +}
522 +
494 523 static void str_to_rl_helper(struct expression *call, struct symbol *type, const char *str, const char **endp, struct range_list **rl)
495 524 {
496 525 struct range_list *rl_tmp = NULL;
497 526 sval_t prev_min, min, max;
498 527 const char *c;
499 528
500 529 prev_min = sval_type_min(type);
501 530 min = sval_type_min(type);
502 531 max = sval_type_max(type);
503 532 c = str;
504 533 while (*c != '\0' && *c != '[') {
505 534 if (*c == '+') {
506 535 if (sval_cmp(min, sval_type_min(type)) != 0)
507 536 min = max;
508 537 max = sval_type_max(type);
509 538 add_range_t(type, &rl_tmp, min, max);
510 539 break;
511 540 }
512 541 if (*c == '(')
513 542 c++;
514 543 min = parse_val(0, call, type, c, &c);
515 544 if (!sval_fits(type, min))
516 545 min = sval_type_min(type);
517 546 max = min;
518 547 if (*c == ')')
519 548 c++;
520 549 if (*c == '\0' || *c == '[') {
521 550 add_range_t(type, &rl_tmp, min, min);
522 551 break;
523 552 }
524 553 if (*c == ',') {
525 554 add_range_t(type, &rl_tmp, min, min);
526 555 c++;
527 556 continue;
528 557 }
529 558 if (*c == '+') {
530 559 min = prev_min;
531 560 max = sval_type_max(type);
532 561 add_range_t(type, &rl_tmp, min, max);
533 562 c++;
534 563 if (*c == '[' || *c == '\0')
535 564 break;
536 565 }
537 566 if (*c != '-') {
538 567 sm_msg("debug XXX: trouble parsing %s c = %s", str, c);
539 568 break;
540 569 }
541 570 c++;
542 571 if (*c == '(')
543 572 c++;
544 573 max = parse_val(1, call, type, c, &c);
545 574 if (!sval_fits(type, max))
546 575 max = sval_type_max(type);
547 576 if (*c == '+') {
548 577 max = sval_type_max(type);
549 578 add_range_t(type, &rl_tmp, min, max);
550 579 c++;
551 580 if (*c == '[' || *c == '\0')
552 581 break;
553 582 }
554 583 prev_min = max;
555 584 add_range_t(type, &rl_tmp, min, max);
556 585 if (*c == ')')
557 586 c++;
558 587 if (*c == ',')
559 588 c++;
560 589 }
561 590
562 591 *rl = rl_tmp;
563 592 *endp = c;
564 593 }
565 594
566 595 static void str_to_dinfo(struct expression *call, struct symbol *type, const char *value, struct data_info *dinfo)
567 596 {
568 597 struct range_list *math_rl;
569 598 const char *call_math;
570 599 const char *c;
571 600 struct range_list *rl = NULL;
572 601
573 602 if (!type)
574 603 type = &llong_ctype;
575 604
576 605 if (strcmp(value, "empty") == 0)
577 606 return;
578 607
579 608 if (strncmp(value, "[==$", 4) == 0) {
580 609 struct expression *arg;
581 610 int comparison;
582 611
583 612 if (!str_to_comparison_arg(value, call, &comparison, &arg))
584 613 return;
|
↓ open down ↓ |
81 lines elided |
↑ open up ↑ |
585 614 if (!get_implied_rl(arg, &rl))
586 615 return;
587 616 goto cast;
588 617 }
589 618
590 619 str_to_rl_helper(call, type, value, &c, &rl);
591 620 if (*c == '\0')
592 621 goto cast;
593 622
594 623 call_math = jump_to_call_math(value);
624 + if (call_math && call_math[0] == 'r') {
625 + math_rl = get_param_return_rl(call, call_math);
626 + if (math_rl)
627 + rl = rl_intersection(rl, math_rl);
628 + goto cast;
629 + }
595 630 if (call_math && parse_call_math_rl(call, call_math, &math_rl)) {
596 631 rl = rl_intersection(rl, math_rl);
597 632 goto cast;
598 633 }
599 634
600 635 /*
601 636 * For now if we already tried to handle the call math and couldn't
602 637 * figure it out then bail.
603 638 */
604 639 if (jump_to_call_math(c) == c + 1)
605 640 goto cast;
606 641
607 642 rl = filter_by_comparison_call(c, call, &c, rl);
608 643
609 644 cast:
610 645 rl = cast_rl(type, rl);
611 646 dinfo->value_ranges = rl;
612 647 }
613 648
614 649 static int rl_is_sane(struct range_list *rl)
615 650 {
616 651 struct data_range *tmp;
617 652 struct symbol *type;
618 653
619 654 type = rl_type(rl);
620 655 FOR_EACH_PTR(rl, tmp) {
621 656 if (!sval_fits(type, tmp->min))
622 657 return 0;
623 658 if (!sval_fits(type, tmp->max))
624 659 return 0;
625 660 if (sval_cmp(tmp->min, tmp->max) > 0)
626 661 return 0;
627 662 } END_FOR_EACH_PTR(tmp);
628 663
629 664 return 1;
630 665 }
631 666
632 667 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
633 668 {
634 669 struct data_info dinfo = {};
635 670
636 671 str_to_dinfo(NULL, type, value, &dinfo);
637 672 if (!rl_is_sane(dinfo.value_ranges))
638 673 dinfo.value_ranges = alloc_whole_rl(type);
639 674 *rl = dinfo.value_ranges;
640 675 }
641 676
642 677 void call_results_to_rl(struct expression *expr, struct symbol *type, const char *value, struct range_list **rl)
643 678 {
|
↓ open down ↓ |
39 lines elided |
↑ open up ↑ |
644 679 struct data_info dinfo = {};
645 680
646 681 str_to_dinfo(strip_expr(expr), type, value, &dinfo);
647 682 *rl = dinfo.value_ranges;
648 683 }
649 684
650 685 int is_whole_rl(struct range_list *rl)
651 686 {
652 687 struct data_range *drange;
653 688
654 - if (ptr_list_empty(rl))
689 + if (ptr_list_empty((struct ptr_list *)rl))
655 690 return 0;
656 691 drange = first_ptr_list((struct ptr_list *)rl);
657 692 if (sval_is_min(drange->min) && sval_is_max(drange->max))
658 693 return 1;
659 694 return 0;
660 695 }
661 696
662 697 int is_unknown_ptr(struct range_list *rl)
663 698 {
664 699 struct data_range *drange;
665 700 int cnt = 0;
666 701
667 702 if (is_whole_rl(rl))
668 703 return 1;
669 704
670 705 FOR_EACH_PTR(rl, drange) {
671 706 if (++cnt >= 3)
672 707 return 0;
673 708 if (sval_cmp(drange->min, valid_ptr_min_sval) == 0 &&
674 709 sval_cmp(drange->max, valid_ptr_max_sval) == 0)
|
↓ open down ↓ |
10 lines elided |
↑ open up ↑ |
675 710 return 1;
676 711 } END_FOR_EACH_PTR(drange);
677 712
678 713 return 0;
679 714 }
680 715
681 716 int is_whole_rl_non_zero(struct range_list *rl)
682 717 {
683 718 struct data_range *drange;
684 719
685 - if (ptr_list_empty(rl))
720 + if (ptr_list_empty((struct ptr_list *)rl))
686 721 return 0;
687 722 drange = first_ptr_list((struct ptr_list *)rl);
688 723 if (sval_unsigned(drange->min) &&
689 724 drange->min.value == 1 &&
690 725 sval_is_max(drange->max))
691 726 return 1;
692 727 if (!sval_is_min(drange->min) || drange->max.value != -1)
693 728 return 0;
694 729 drange = last_ptr_list((struct ptr_list *)rl);
695 730 if (drange->min.value != 1 || !sval_is_max(drange->max))
696 731 return 0;
|
↓ open down ↓ |
1 lines elided |
↑ open up ↑ |
697 732 return 1;
698 733 }
699 734
700 735 sval_t rl_min(struct range_list *rl)
701 736 {
702 737 struct data_range *drange;
703 738 sval_t ret;
704 739
705 740 ret.type = &llong_ctype;
706 741 ret.value = LLONG_MIN;
707 - if (ptr_list_empty(rl))
742 + if (ptr_list_empty((struct ptr_list *)rl))
708 743 return ret;
709 744 drange = first_ptr_list((struct ptr_list *)rl);
710 745 return drange->min;
711 746 }
712 747
713 748 sval_t rl_max(struct range_list *rl)
714 749 {
715 750 struct data_range *drange;
716 751 sval_t ret;
717 752
718 753 ret.type = &llong_ctype;
719 754 ret.value = LLONG_MAX;
720 - if (ptr_list_empty(rl))
755 + if (ptr_list_empty((struct ptr_list *)rl))
721 756 return ret;
722 757 drange = last_ptr_list((struct ptr_list *)rl);
723 758 return drange->max;
724 759 }
725 760
726 761 int rl_to_sval(struct range_list *rl, sval_t *sval)
727 762 {
728 763 sval_t min, max;
729 764
730 765 if (!rl)
731 766 return 0;
732 767
733 768 min = rl_min(rl);
734 769 max = rl_max(rl);
735 770 if (sval_cmp(min, max) != 0)
736 771 return 0;
737 772 *sval = min;
738 773 return 1;
739 774 }
740 775
741 776 struct symbol *rl_type(struct range_list *rl)
742 777 {
743 778 if (!rl)
744 779 return NULL;
745 780 return rl_min(rl).type;
746 781 }
747 782
748 783 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
749 784 {
750 785 struct data_range *ret;
751 786
752 787 if (perm)
753 788 ret = __alloc_perm_data_range(0);
754 789 else
755 790 ret = __alloc_data_range(0);
756 791 ret->min = min;
757 792 ret->max = max;
758 793 return ret;
759 794 }
760 795
761 796 struct data_range *alloc_range(sval_t min, sval_t max)
762 797 {
763 798 return alloc_range_helper_sval(min, max, 0);
764 799 }
765 800
766 801 struct data_range *alloc_range_perm(sval_t min, sval_t max)
767 802 {
768 803 return alloc_range_helper_sval(min, max, 1);
769 804 }
770 805
771 806 struct range_list *alloc_rl(sval_t min, sval_t max)
772 807 {
773 808 struct range_list *rl = NULL;
774 809
775 810 if (sval_cmp(min, max) > 0)
776 811 return alloc_whole_rl(min.type);
777 812
778 813 add_range(&rl, min, max);
779 814 return rl;
780 815 }
781 816
782 817 struct range_list *alloc_whole_rl(struct symbol *type)
783 818 {
784 819 if (!type || type_positive_bits(type) < 0)
785 820 type = &llong_ctype;
786 821 if (type->type == SYM_ARRAY)
787 822 type = &ptr_ctype;
788 823
789 824 return alloc_rl(sval_type_min(type), sval_type_max(type));
790 825 }
791 826
792 827 static bool collapse_pointer_rl(struct range_list **rl, sval_t min, sval_t max)
793 828 {
794 829 struct range_list *new_rl = NULL;
795 830 struct data_range *tmp;
796 831 static bool recurse;
797 832 bool ret = false;
798 833 int cnt = 0;
799 834
800 835 /*
801 836 * With the mtag work, then we end up getting huge lists of mtags.
802 837 * That seems cool, but the problem is that we can only store about
803 838 * 8-10 mtags in the DB before we truncate the list. Also the mtags
804 839 * aren't really used at all so it's a waste of resources for now...
805 840 * In the future, we maybe will revisit this code.
806 841 *
807 842 */
808 843
809 844 if (recurse)
810 845 return false;
811 846 recurse = true;
812 847 if (!type_is_ptr(min.type))
813 848 goto out;
814 849
815 850 if (ptr_list_size((struct ptr_list *)*rl) < 8)
816 851 goto out;
817 852 FOR_EACH_PTR(*rl, tmp) {
818 853 if (!is_err_ptr(tmp->min))
819 854 cnt++;
820 855 } END_FOR_EACH_PTR(tmp);
821 856 if (cnt < 8)
822 857 goto out;
823 858
824 859 FOR_EACH_PTR(*rl, tmp) {
825 860 if (sval_cmp(tmp->min, valid_ptr_min_sval) >= 0 &&
826 861 sval_cmp(tmp->max, valid_ptr_max_sval) <= 0)
827 862 add_range(&new_rl, valid_ptr_min_sval, valid_ptr_max_sval);
828 863 else
829 864 add_range(&new_rl, tmp->min, tmp->max);
830 865 } END_FOR_EACH_PTR(tmp);
831 866
832 867 add_range(&new_rl, min, max);
833 868
834 869 *rl = new_rl;
835 870 ret = true;
836 871 out:
837 872 recurse = false;
838 873 return ret;
839 874 }
840 875
841 876 extern int rl_ptrlist_hack;
842 877 void add_range(struct range_list **list, sval_t min, sval_t max)
843 878 {
844 879 struct data_range *tmp;
845 880 struct data_range *new = NULL;
846 881 int check_next = 0;
847 882
848 883 /*
849 884 * There is at least on valid reason why the types might be confusing
850 885 * and that's when you have a void pointer and on some paths you treat
851 886 * it as a u8 pointer and on other paths you treat it as a u16 pointer.
852 887 * This case is hard to deal with.
853 888 *
854 889 * There are other cases where we probably should be more specific about
855 890 * the types than we are. For example, we end up merging a lot of ulong
856 891 * with pointers and I have not figured out why we do that.
857 892 *
858 893 * But this hack works for both cases, I think. We cast it to pointers
859 894 * or we use the bigger size.
860 895 *
861 896 */
862 897 if (*list && rl_type(*list) != min.type) {
863 898 if (rl_type(*list)->type == SYM_PTR) {
864 899 min = sval_cast(rl_type(*list), min);
865 900 max = sval_cast(rl_type(*list), max);
866 901 } else if (min.type->type == SYM_PTR) {
867 902 *list = cast_rl(min.type, *list);
868 903 } else if (type_bits(rl_type(*list)) >= type_bits(min.type)) {
869 904 min = sval_cast(rl_type(*list), min);
870 905 max = sval_cast(rl_type(*list), max);
871 906 } else {
872 907 *list = cast_rl(min.type, *list);
873 908 }
874 909 }
875 910
876 911 if (sval_cmp(min, max) > 0) {
877 912 min = sval_type_min(min.type);
878 913 max = sval_type_max(min.type);
879 914 }
880 915
881 916 if (collapse_pointer_rl(list, min, max))
882 917 return;
883 918
884 919 /*
885 920 * FIXME: This has a problem merging a range_list like: min-0,3-max
886 921 * with a range like 1-2. You end up with min-2,3-max instead of
887 922 * just min-max.
888 923 */
889 924 FOR_EACH_PTR(*list, tmp) {
890 925 if (check_next) {
891 926 /* Sometimes we overlap with more than one range
892 927 so we have to delete or modify the next range. */
893 928 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
894 929 /* join 2 ranges here */
895 930 new->max = tmp->max;
896 931 DELETE_CURRENT_PTR(tmp);
897 932 return;
898 933 }
899 934
900 935 /* Doesn't overlap with the next one. */
901 936 if (sval_cmp(max, tmp->min) < 0)
902 937 return;
903 938
904 939 if (sval_cmp(max, tmp->max) <= 0) {
905 940 /* Partially overlaps the next one. */
906 941 new->max = tmp->max;
907 942 DELETE_CURRENT_PTR(tmp);
908 943 return;
909 944 } else {
910 945 /* Completely overlaps the next one. */
911 946 DELETE_CURRENT_PTR(tmp);
912 947 /* there could be more ranges to delete */
913 948 continue;
914 949 }
915 950 }
916 951 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
917 952 /* join 2 ranges into a big range */
918 953 new = alloc_range(min, tmp->max);
919 954 REPLACE_CURRENT_PTR(tmp, new);
920 955 return;
921 956 }
922 957 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
923 958 new = alloc_range(min, max);
924 959 INSERT_CURRENT(new, tmp);
925 960 return;
926 961 }
927 962 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
928 963 if (sval_cmp(max, tmp->max) < 0)
929 964 max = tmp->max;
930 965 else
931 966 check_next = 1;
932 967 new = alloc_range(min, max);
933 968 REPLACE_CURRENT_PTR(tmp, new);
934 969 if (!check_next)
935 970 return;
936 971 continue;
937 972 }
938 973 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
939 974 return;
940 975 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
941 976 min = tmp->min;
942 977 new = alloc_range(min, max);
943 978 REPLACE_CURRENT_PTR(tmp, new);
944 979 check_next = 1;
945 980 continue;
946 981 }
947 982 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
948 983 /* join 2 ranges into a big range */
949 984 new = alloc_range(tmp->min, max);
950 985 REPLACE_CURRENT_PTR(tmp, new);
951 986 check_next = 1;
952 987 continue;
953 988 }
954 989 /* the new range is entirely above the existing ranges */
955 990 } END_FOR_EACH_PTR(tmp);
956 991 if (check_next)
957 992 return;
958 993 new = alloc_range(min, max);
959 994
960 995 rl_ptrlist_hack = 1;
961 996 add_ptr_list(list, new);
962 997 rl_ptrlist_hack = 0;
963 998 }
964 999
965 1000 struct range_list *clone_rl(struct range_list *list)
966 1001 {
967 1002 struct data_range *tmp;
968 1003 struct range_list *ret = NULL;
969 1004
970 1005 FOR_EACH_PTR(list, tmp) {
971 1006 add_ptr_list(&ret, tmp);
972 1007 } END_FOR_EACH_PTR(tmp);
973 1008 return ret;
974 1009 }
975 1010
976 1011 struct range_list *clone_rl_permanent(struct range_list *list)
977 1012 {
978 1013 struct data_range *tmp;
979 1014 struct data_range *new;
980 1015 struct range_list *ret = NULL;
981 1016
982 1017 FOR_EACH_PTR(list, tmp) {
983 1018 new = alloc_range_perm(tmp->min, tmp->max);
984 1019 add_ptr_list(&ret, new);
985 1020 } END_FOR_EACH_PTR(tmp);
986 1021 return ret;
987 1022 }
988 1023
989 1024 struct range_list *rl_union(struct range_list *one, struct range_list *two)
990 1025 {
991 1026 struct data_range *tmp;
992 1027 struct range_list *ret = NULL;
993 1028
994 1029 FOR_EACH_PTR(one, tmp) {
995 1030 add_range(&ret, tmp->min, tmp->max);
996 1031 } END_FOR_EACH_PTR(tmp);
997 1032 FOR_EACH_PTR(two, tmp) {
998 1033 add_range(&ret, tmp->min, tmp->max);
999 1034 } END_FOR_EACH_PTR(tmp);
1000 1035 return ret;
1001 1036 }
1002 1037
1003 1038 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
1004 1039 {
1005 1040 struct data_range *tmp;
1006 1041 struct range_list *ret = NULL;
1007 1042
1008 1043 if (!list)
1009 1044 return NULL;
1010 1045
1011 1046 min = sval_cast(rl_type(list), min);
1012 1047 max = sval_cast(rl_type(list), max);
1013 1048 if (sval_cmp(min, max) > 0) {
1014 1049 sval_t tmp = min;
1015 1050 min = max;
1016 1051 max = tmp;
1017 1052 }
1018 1053
1019 1054 FOR_EACH_PTR(list, tmp) {
1020 1055 if (sval_cmp(tmp->max, min) < 0) {
1021 1056 add_range(&ret, tmp->min, tmp->max);
1022 1057 continue;
1023 1058 }
1024 1059 if (sval_cmp(tmp->min, max) > 0) {
1025 1060 add_range(&ret, tmp->min, tmp->max);
1026 1061 continue;
1027 1062 }
1028 1063 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
1029 1064 continue;
1030 1065 if (sval_cmp(tmp->min, min) >= 0) {
1031 1066 max.value++;
1032 1067 add_range(&ret, max, tmp->max);
1033 1068 } else if (sval_cmp(tmp->max, max) <= 0) {
1034 1069 min.value--;
1035 1070 add_range(&ret, tmp->min, min);
1036 1071 } else {
1037 1072 min.value--;
1038 1073 max.value++;
1039 1074 add_range(&ret, tmp->min, min);
1040 1075 add_range(&ret, max, tmp->max);
1041 1076 }
1042 1077 } END_FOR_EACH_PTR(tmp);
1043 1078 return ret;
1044 1079 }
1045 1080
1046 1081 int ranges_equiv(struct data_range *one, struct data_range *two)
1047 1082 {
1048 1083 if (!one && !two)
1049 1084 return 1;
1050 1085 if (!one || !two)
1051 1086 return 0;
1052 1087 if (sval_cmp(one->min, two->min) != 0)
1053 1088 return 0;
1054 1089 if (sval_cmp(one->max, two->max) != 0)
1055 1090 return 0;
1056 1091 return 1;
1057 1092 }
1058 1093
1059 1094 int rl_equiv(struct range_list *one, struct range_list *two)
1060 1095 {
1061 1096 struct data_range *one_range;
1062 1097 struct data_range *two_range;
1063 1098
1064 1099 if (one == two)
1065 1100 return 1;
1066 1101
1067 1102 PREPARE_PTR_LIST(one, one_range);
1068 1103 PREPARE_PTR_LIST(two, two_range);
1069 1104 for (;;) {
1070 1105 if (!one_range && !two_range)
1071 1106 return 1;
1072 1107 if (!ranges_equiv(one_range, two_range))
1073 1108 return 0;
1074 1109 NEXT_PTR_LIST(one_range);
1075 1110 NEXT_PTR_LIST(two_range);
1076 1111 }
1077 1112 FINISH_PTR_LIST(two_range);
1078 1113 FINISH_PTR_LIST(one_range);
1079 1114
1080 1115 return 1;
1081 1116 }
1082 1117
1083 1118 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
1084 1119 {
1085 1120 switch (comparison) {
1086 1121 case '<':
1087 1122 case SPECIAL_UNSIGNED_LT:
1088 1123 if (sval_cmp(left->min, right->max) < 0)
1089 1124 return 1;
1090 1125 return 0;
1091 1126 case SPECIAL_UNSIGNED_LTE:
1092 1127 case SPECIAL_LTE:
1093 1128 if (sval_cmp(left->min, right->max) <= 0)
1094 1129 return 1;
1095 1130 return 0;
1096 1131 case SPECIAL_EQUAL:
1097 1132 if (sval_cmp(left->max, right->min) < 0)
1098 1133 return 0;
1099 1134 if (sval_cmp(left->min, right->max) > 0)
1100 1135 return 0;
1101 1136 return 1;
1102 1137 case SPECIAL_UNSIGNED_GTE:
1103 1138 case SPECIAL_GTE:
1104 1139 if (sval_cmp(left->max, right->min) >= 0)
1105 1140 return 1;
1106 1141 return 0;
1107 1142 case '>':
1108 1143 case SPECIAL_UNSIGNED_GT:
1109 1144 if (sval_cmp(left->max, right->min) > 0)
1110 1145 return 1;
1111 1146 return 0;
1112 1147 case SPECIAL_NOTEQUAL:
1113 1148 if (sval_cmp(left->min, left->max) != 0)
1114 1149 return 1;
1115 1150 if (sval_cmp(right->min, right->max) != 0)
1116 1151 return 1;
1117 1152 if (sval_cmp(left->min, right->min) != 0)
1118 1153 return 1;
1119 1154 return 0;
1120 1155 default:
1121 1156 sm_perror("unhandled comparison %d", comparison);
1122 1157 return 0;
1123 1158 }
1124 1159 return 0;
1125 1160 }
1126 1161
1127 1162 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1128 1163 {
1129 1164 if (left)
1130 1165 return true_comparison_range(var, comparison, val);
1131 1166 else
1132 1167 return true_comparison_range(val, comparison, var);
1133 1168 }
1134 1169
1135 1170 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
1136 1171 {
1137 1172 switch (comparison) {
1138 1173 case '<':
1139 1174 case SPECIAL_UNSIGNED_LT:
1140 1175 if (sval_cmp(left->max, right->min) >= 0)
1141 1176 return 1;
1142 1177 return 0;
1143 1178 case SPECIAL_UNSIGNED_LTE:
1144 1179 case SPECIAL_LTE:
1145 1180 if (sval_cmp(left->max, right->min) > 0)
1146 1181 return 1;
1147 1182 return 0;
1148 1183 case SPECIAL_EQUAL:
1149 1184 if (sval_cmp(left->min, left->max) != 0)
1150 1185 return 1;
1151 1186 if (sval_cmp(right->min, right->max) != 0)
1152 1187 return 1;
1153 1188 if (sval_cmp(left->min, right->min) != 0)
1154 1189 return 1;
1155 1190 return 0;
1156 1191 case SPECIAL_UNSIGNED_GTE:
1157 1192 case SPECIAL_GTE:
1158 1193 if (sval_cmp(left->min, right->max) < 0)
1159 1194 return 1;
1160 1195 return 0;
1161 1196 case '>':
1162 1197 case SPECIAL_UNSIGNED_GT:
1163 1198 if (sval_cmp(left->min, right->max) <= 0)
1164 1199 return 1;
1165 1200 return 0;
1166 1201 case SPECIAL_NOTEQUAL:
1167 1202 if (sval_cmp(left->max, right->min) < 0)
1168 1203 return 0;
1169 1204 if (sval_cmp(left->min, right->max) > 0)
1170 1205 return 0;
1171 1206 return 1;
1172 1207 default:
1173 1208 sm_perror("unhandled comparison %d", comparison);
1174 1209 return 0;
1175 1210 }
1176 1211 return 0;
1177 1212 }
1178 1213
1179 1214 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1180 1215 {
1181 1216 if (left)
1182 1217 return false_comparison_range_sval(var, comparison, val);
|
↓ open down ↓ |
452 lines elided |
↑ open up ↑ |
1183 1218 else
1184 1219 return false_comparison_range_sval(val, comparison, var);
1185 1220 }
1186 1221
1187 1222 int possibly_true(struct expression *left, int comparison, struct expression *right)
1188 1223 {
1189 1224 struct range_list *rl_left, *rl_right;
1190 1225 struct data_range *tmp_left, *tmp_right;
1191 1226 struct symbol *type;
1192 1227
1228 + if (comparison == UNKNOWN_COMPARISON)
1229 + return 1;
1193 1230 if (!get_implied_rl(left, &rl_left))
1194 1231 return 1;
1195 1232 if (!get_implied_rl(right, &rl_right))
1196 1233 return 1;
1197 1234
1198 1235 type = rl_type(rl_left);
1199 1236 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1200 1237 type = rl_type(rl_right);
1201 1238 if (type_positive_bits(type) < 31)
1202 1239 type = &int_ctype;
1203 1240
1204 1241 rl_left = cast_rl(type, rl_left);
1205 1242 rl_right = cast_rl(type, rl_right);
1206 1243
1207 1244 FOR_EACH_PTR(rl_left, tmp_left) {
1208 1245 FOR_EACH_PTR(rl_right, tmp_right) {
1209 1246 if (true_comparison_range(tmp_left, comparison, tmp_right))
1210 1247 return 1;
1211 1248 } END_FOR_EACH_PTR(tmp_right);
1212 1249 } END_FOR_EACH_PTR(tmp_left);
1213 1250 return 0;
1214 1251 }
1215 1252
1216 1253 int possibly_false(struct expression *left, int comparison, struct expression *right)
1217 1254 {
1218 1255 struct range_list *rl_left, *rl_right;
1219 1256 struct data_range *tmp_left, *tmp_right;
1220 1257 struct symbol *type;
1221 1258
1222 1259 if (!get_implied_rl(left, &rl_left))
1223 1260 return 1;
1224 1261 if (!get_implied_rl(right, &rl_right))
1225 1262 return 1;
1226 1263
1227 1264 type = rl_type(rl_left);
1228 1265 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1229 1266 type = rl_type(rl_right);
1230 1267 if (type_positive_bits(type) < 31)
1231 1268 type = &int_ctype;
1232 1269
1233 1270 rl_left = cast_rl(type, rl_left);
1234 1271 rl_right = cast_rl(type, rl_right);
1235 1272
1236 1273 FOR_EACH_PTR(rl_left, tmp_left) {
1237 1274 FOR_EACH_PTR(rl_right, tmp_right) {
1238 1275 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
1239 1276 return 1;
|
↓ open down ↓ |
37 lines elided |
↑ open up ↑ |
1240 1277 } END_FOR_EACH_PTR(tmp_right);
1241 1278 } END_FOR_EACH_PTR(tmp_left);
1242 1279 return 0;
1243 1280 }
1244 1281
1245 1282 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1246 1283 {
1247 1284 struct data_range *left_tmp, *right_tmp;
1248 1285 struct symbol *type;
1249 1286
1250 - if (!left_ranges || !right_ranges)
1287 + if (!left_ranges || !right_ranges || comparison == UNKNOWN_COMPARISON)
1251 1288 return 1;
1252 1289
1253 1290 type = rl_type(left_ranges);
1254 1291 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1255 1292 type = rl_type(right_ranges);
1256 1293 if (type_positive_bits(type) < 31)
1257 1294 type = &int_ctype;
1258 1295
1259 1296 left_ranges = cast_rl(type, left_ranges);
1260 1297 right_ranges = cast_rl(type, right_ranges);
1261 1298
1262 1299 FOR_EACH_PTR(left_ranges, left_tmp) {
1263 1300 FOR_EACH_PTR(right_ranges, right_tmp) {
1264 1301 if (true_comparison_range(left_tmp, comparison, right_tmp))
1265 1302 return 1;
|
↓ open down ↓ |
5 lines elided |
↑ open up ↑ |
1266 1303 } END_FOR_EACH_PTR(right_tmp);
1267 1304 } END_FOR_EACH_PTR(left_tmp);
1268 1305 return 0;
1269 1306 }
1270 1307
1271 1308 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1272 1309 {
1273 1310 struct data_range *left_tmp, *right_tmp;
1274 1311 struct symbol *type;
1275 1312
1276 - if (!left_ranges || !right_ranges)
1313 + if (!left_ranges || !right_ranges || comparison == UNKNOWN_COMPARISON)
1277 1314 return 1;
1278 1315
1279 1316 type = rl_type(left_ranges);
1280 1317 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1281 1318 type = rl_type(right_ranges);
1282 1319 if (type_positive_bits(type) < 31)
1283 1320 type = &int_ctype;
1284 1321
1285 1322 left_ranges = cast_rl(type, left_ranges);
1286 1323 right_ranges = cast_rl(type, right_ranges);
1287 1324
1288 1325 FOR_EACH_PTR(left_ranges, left_tmp) {
1289 1326 FOR_EACH_PTR(right_ranges, right_tmp) {
1290 1327 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
1291 1328 return 1;
1292 1329 } END_FOR_EACH_PTR(right_tmp);
1293 1330 } END_FOR_EACH_PTR(left_tmp);
1294 1331 return 0;
1295 1332 }
1296 1333
1297 1334 /* FIXME: the _rl here stands for right left so really it should be _lr */
1298 1335 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1299 1336 {
1300 1337 if (left)
1301 1338 return possibly_true_rl(a, comparison, b);
1302 1339 else
1303 1340 return possibly_true_rl(b, comparison, a);
1304 1341 }
1305 1342
1306 1343 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1307 1344 {
1308 1345 if (left)
1309 1346 return possibly_false_rl(a, comparison, b);
1310 1347 else
1311 1348 return possibly_false_rl(b, comparison, a);
1312 1349 }
1313 1350
1314 1351 int rl_has_sval(struct range_list *rl, sval_t sval)
1315 1352 {
1316 1353 struct data_range *tmp;
1317 1354
1318 1355 FOR_EACH_PTR(rl, tmp) {
1319 1356 if (sval_cmp(tmp->min, sval) <= 0 &&
1320 1357 sval_cmp(tmp->max, sval) >= 0)
1321 1358 return 1;
1322 1359 } END_FOR_EACH_PTR(tmp);
1323 1360 return 0;
1324 1361 }
1325 1362
1326 1363 void tack_on(struct range_list **list, struct data_range *drange)
1327 1364 {
1328 1365 add_ptr_list(list, drange);
1329 1366 }
1330 1367
1331 1368 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
1332 1369 {
1333 1370 add_ptr_list(rl_stack, rl);
1334 1371 }
1335 1372
1336 1373 struct range_list *pop_rl(struct range_list_stack **rl_stack)
1337 1374 {
1338 1375 struct range_list *rl;
1339 1376
1340 1377 rl = last_ptr_list((struct ptr_list *)*rl_stack);
1341 1378 delete_ptr_list_last((struct ptr_list **)rl_stack);
1342 1379 return rl;
1343 1380 }
1344 1381
1345 1382 struct range_list *top_rl(struct range_list_stack *rl_stack)
1346 1383 {
1347 1384 struct range_list *rl;
1348 1385
1349 1386 rl = last_ptr_list((struct ptr_list *)rl_stack);
1350 1387 return rl;
1351 1388 }
1352 1389
1353 1390 void filter_top_rl(struct range_list_stack **rl_stack, struct range_list *filter)
1354 1391 {
1355 1392 struct range_list *rl;
1356 1393
1357 1394 rl = pop_rl(rl_stack);
1358 1395 rl = rl_filter(rl, filter);
1359 1396 push_rl(rl_stack, rl);
1360 1397 }
1361 1398
1362 1399 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1363 1400 {
1364 1401 struct data_range *tmp;
1365 1402 struct range_list *ret = NULL;
1366 1403 sval_t min, max;
1367 1404
1368 1405 if (!rl)
1369 1406 return NULL;
1370 1407
1371 1408 if (!type || type == rl_type(rl))
1372 1409 return rl;
1373 1410
1374 1411 FOR_EACH_PTR(rl, tmp) {
1375 1412 min = tmp->min;
1376 1413 max = tmp->max;
1377 1414 if (type_bits(type) < type_bits(rl_type(rl))) {
1378 1415 min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1379 1416 max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1380 1417 }
1381 1418 if (sval_cmp(min, max) > 0) {
1382 1419 min = sval_cast(type, min);
1383 1420 max = sval_cast(type, max);
1384 1421 }
1385 1422 add_range_t(type, &ret, min, max);
1386 1423 } END_FOR_EACH_PTR(tmp);
1387 1424
1388 1425 return ret;
1389 1426 }
1390 1427
1391 1428 int rl_fits_in_type(struct range_list *rl, struct symbol *type)
1392 1429 {
1393 1430 if (type_bits(rl_type(rl)) <= type_bits(type))
1394 1431 return 1;
1395 1432 if (sval_cmp(rl_max(rl), sval_type_max(type)) > 0)
1396 1433 return 0;
1397 1434 if (sval_is_negative(rl_min(rl)) &&
1398 1435 sval_cmp(rl_min(rl), sval_type_min(type)) < 0)
1399 1436 return 0;
1400 1437 return 1;
1401 1438 }
1402 1439
1403 1440 static int rl_type_consistent(struct range_list *rl)
1404 1441 {
1405 1442 struct data_range *tmp;
1406 1443 struct symbol *type;
1407 1444
1408 1445 type = rl_type(rl);
1409 1446 FOR_EACH_PTR(rl, tmp) {
1410 1447 if (type != tmp->min.type || type != tmp->max.type)
1411 1448 return 0;
1412 1449 } END_FOR_EACH_PTR(tmp);
1413 1450 return 1;
1414 1451 }
1415 1452
1416 1453 static struct range_list *cast_to_bool(struct range_list *rl)
1417 1454 {
1418 1455 struct data_range *tmp;
1419 1456 struct range_list *ret = NULL;
1420 1457 int has_one = 0;
1421 1458 int has_zero = 0;
1422 1459 sval_t min = { .type = &bool_ctype };
1423 1460 sval_t max = { .type = &bool_ctype };
1424 1461
1425 1462 FOR_EACH_PTR(rl, tmp) {
1426 1463 if (tmp->min.value || tmp->max.value)
1427 1464 has_one = 1;
1428 1465 if (sval_is_negative(tmp->min) &&
1429 1466 sval_is_negative(tmp->max))
1430 1467 continue;
1431 1468 if (tmp->min.value == 0 ||
1432 1469 tmp->max.value == 0)
1433 1470 has_zero = 1;
1434 1471 if (sval_is_negative(tmp->min) &&
1435 1472 tmp->max.value > 0)
1436 1473 has_zero = 1;
1437 1474 } END_FOR_EACH_PTR(tmp);
1438 1475
1439 1476 if (!has_zero)
1440 1477 min.value = 1;
1441 1478 if (has_one)
1442 1479 max.value = 1;
1443 1480
1444 1481 add_range(&ret, min, max);
1445 1482 return ret;
1446 1483 }
1447 1484
1448 1485 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1449 1486 {
1450 1487 struct data_range *tmp;
1451 1488 struct range_list *ret = NULL;
1452 1489
1453 1490 if (!rl)
1454 1491 return NULL;
1455 1492
1456 1493 if (!type)
1457 1494 return rl;
1458 1495 if (!rl_is_sane(rl))
1459 1496 return alloc_whole_rl(type);
1460 1497 if (type == rl_type(rl) && rl_type_consistent(rl))
1461 1498 return rl;
1462 1499
1463 1500 if (type == &bool_ctype)
1464 1501 return cast_to_bool(rl);
1465 1502
1466 1503 FOR_EACH_PTR(rl, tmp) {
1467 1504 add_range_t(type, &ret, tmp->min, tmp->max);
1468 1505 } END_FOR_EACH_PTR(tmp);
1469 1506
1470 1507 if (!ret)
1471 1508 return alloc_whole_rl(type);
1472 1509
1473 1510 return ret;
1474 1511 }
1475 1512
1476 1513 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1477 1514 {
1478 1515 struct data_range *tmp;
1479 1516
1480 1517 FOR_EACH_PTR(filter, tmp) {
1481 1518 rl = remove_range(rl, tmp->min, tmp->max);
1482 1519 } END_FOR_EACH_PTR(tmp);
1483 1520
1484 1521 return rl;
1485 1522 }
1486 1523
1487 1524 struct range_list *do_intersection(struct range_list *one_rl, struct range_list *two_rl)
1488 1525 {
1489 1526 struct data_range *one, *two;
1490 1527 struct range_list *ret = NULL;
1491 1528
1492 1529
1493 1530 PREPARE_PTR_LIST(one_rl, one);
1494 1531 PREPARE_PTR_LIST(two_rl, two);
1495 1532
1496 1533 while (true) {
1497 1534 if (!one || !two)
1498 1535 break;
1499 1536 if (sval_cmp(one->max, two->min) < 0) {
1500 1537 NEXT_PTR_LIST(one);
1501 1538 continue;
1502 1539 }
1503 1540 if (sval_cmp(one->min, two->min) < 0 && sval_cmp(one->max, two->max) <= 0) {
1504 1541 add_range(&ret, two->min, one->max);
1505 1542 NEXT_PTR_LIST(one);
1506 1543 continue;
1507 1544 }
1508 1545 if (sval_cmp(one->min, two->min) >= 0 && sval_cmp(one->max, two->max) <= 0) {
1509 1546 add_range(&ret, one->min, one->max);
1510 1547 NEXT_PTR_LIST(one);
1511 1548 continue;
1512 1549 }
1513 1550 if (sval_cmp(one->min, two->min) < 0 && sval_cmp(one->max, two->max) > 0) {
1514 1551 add_range(&ret, two->min, two->max);
1515 1552 NEXT_PTR_LIST(two);
1516 1553 continue;
1517 1554 }
1518 1555 if (sval_cmp(one->min, two->max) <= 0 && sval_cmp(one->max, two->max) > 0) {
1519 1556 add_range(&ret, one->min, two->max);
1520 1557 NEXT_PTR_LIST(two);
1521 1558 continue;
1522 1559 }
1523 1560 if (sval_cmp(one->min, two->max) <= 0) {
1524 1561 sm_fatal("error calculating intersection of '%s' and '%s'", show_rl(one_rl), show_rl(two_rl));
1525 1562 return NULL;
1526 1563 }
1527 1564 NEXT_PTR_LIST(two);
1528 1565 }
1529 1566
1530 1567 FINISH_PTR_LIST(two);
1531 1568 FINISH_PTR_LIST(one);
1532 1569
1533 1570 return ret;
1534 1571 }
1535 1572
1536 1573 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1537 1574 {
1538 1575 struct range_list *ret;
1539 1576 struct symbol *ret_type;
1540 1577 struct symbol *small_type;
1541 1578 struct symbol *large_type;
1542 1579
1543 1580 if (!one || !two)
1544 1581 return NULL;
1545 1582
1546 1583 ret_type = rl_type(one);
1547 1584 small_type = rl_type(one);
1548 1585 large_type = rl_type(two);
1549 1586
1550 1587 if (type_bits(rl_type(two)) < type_bits(small_type)) {
1551 1588 small_type = rl_type(two);
1552 1589 large_type = rl_type(one);
1553 1590 }
1554 1591
1555 1592 one = cast_rl(large_type, one);
1556 1593 two = cast_rl(large_type, two);
1557 1594
1558 1595 ret = do_intersection(one, two);
1559 1596 return cast_rl(ret_type, ret);
1560 1597 }
1561 1598
1562 1599 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1563 1600 {
1564 1601 sval_t zero;
1565 1602 sval_t max;
1566 1603
1567 1604 max = rl_max(right);
1568 1605 if (sval_is_max(max))
1569 1606 return left;
1570 1607 if (max.value == 0)
1571 1608 return NULL;
1572 1609 max.value--;
1573 1610 if (sval_is_negative(max))
1574 1611 return NULL;
1575 1612 if (sval_cmp(rl_max(left), max) < 0)
1576 1613 return left;
1577 1614 zero = max;
1578 1615 zero.value = 0;
1579 1616 return alloc_rl(zero, max);
1580 1617 }
1581 1618
1582 1619 static struct range_list *get_neg_rl(struct range_list *rl)
1583 1620 {
1584 1621 struct data_range *tmp;
1585 1622 struct data_range *new;
1586 1623 struct range_list *ret = NULL;
1587 1624
1588 1625 if (!rl)
1589 1626 return NULL;
1590 1627 if (sval_is_positive(rl_min(rl)))
1591 1628 return NULL;
1592 1629
1593 1630 FOR_EACH_PTR(rl, tmp) {
1594 1631 if (sval_is_positive(tmp->min))
1595 1632 break;
1596 1633 if (sval_is_positive(tmp->max)) {
1597 1634 new = alloc_range(tmp->min, tmp->max);
1598 1635 new->max.value = -1;
1599 1636 add_range(&ret, new->min, new->max);
1600 1637 break;
1601 1638 }
1602 1639 add_range(&ret, tmp->min, tmp->max);
1603 1640 } END_FOR_EACH_PTR(tmp);
1604 1641
1605 1642 return ret;
1606 1643 }
1607 1644
1608 1645 static struct range_list *get_pos_rl(struct range_list *rl)
1609 1646 {
1610 1647 struct data_range *tmp;
1611 1648 struct data_range *new;
1612 1649 struct range_list *ret = NULL;
1613 1650
1614 1651 if (!rl)
1615 1652 return NULL;
1616 1653 if (sval_is_negative(rl_max(rl)))
1617 1654 return NULL;
1618 1655
1619 1656 FOR_EACH_PTR(rl, tmp) {
1620 1657 if (sval_is_negative(tmp->max))
1621 1658 continue;
1622 1659 if (sval_is_positive(tmp->min)) {
1623 1660 add_range(&ret, tmp->min, tmp->max);
1624 1661 continue;
1625 1662 }
1626 1663 new = alloc_range(tmp->min, tmp->max);
1627 1664 new->min.value = 0;
1628 1665 add_range(&ret, new->min, new->max);
1629 1666 } END_FOR_EACH_PTR(tmp);
1630 1667
1631 1668 return ret;
1632 1669 }
1633 1670
1634 1671 static struct range_list *divide_rl_helper(struct range_list *left, struct range_list *right)
1635 1672 {
1636 1673 sval_t right_min, right_max;
1637 1674 sval_t min, max;
1638 1675
1639 1676 if (!left || !right)
1640 1677 return NULL;
1641 1678
1642 1679 /* let's assume we never divide by zero */
1643 1680 right_min = rl_min(right);
1644 1681 right_max = rl_max(right);
1645 1682 if (right_min.value == 0 && right_max.value == 0)
1646 1683 return NULL;
1647 1684 if (right_min.value == 0)
1648 1685 right_min.value = 1;
1649 1686 if (right_max.value == 0)
1650 1687 right_max.value = -1;
1651 1688
1652 1689 max = sval_binop(rl_max(left), '/', right_min);
1653 1690 min = sval_binop(rl_min(left), '/', right_max);
1654 1691
1655 1692 return alloc_rl(min, max);
1656 1693 }
1657 1694
1658 1695 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1659 1696 {
1660 1697 struct range_list *left_neg, *left_pos, *right_neg, *right_pos;
1661 1698 struct range_list *neg_neg, *neg_pos, *pos_neg, *pos_pos;
1662 1699 struct range_list *ret;
1663 1700
1664 1701 if (is_whole_rl(right))
1665 1702 return NULL;
1666 1703
1667 1704 left_neg = get_neg_rl(left);
1668 1705 left_pos = get_pos_rl(left);
1669 1706 right_neg = get_neg_rl(right);
1670 1707 right_pos = get_pos_rl(right);
1671 1708
1672 1709 neg_neg = divide_rl_helper(left_neg, right_neg);
1673 1710 neg_pos = divide_rl_helper(left_neg, right_pos);
1674 1711 pos_neg = divide_rl_helper(left_pos, right_neg);
1675 1712 pos_pos = divide_rl_helper(left_pos, right_pos);
1676 1713
1677 1714 ret = rl_union(neg_neg, neg_pos);
1678 1715 ret = rl_union(ret, pos_neg);
1679 1716 return rl_union(ret, pos_pos);
1680 1717 }
1681 1718
1682 1719 static struct range_list *ptr_add_mult(struct range_list *left, int op, struct range_list *right)
1683 1720 {
1684 1721 struct range_list *ret;
1685 1722 sval_t l_sval, r_sval, res;
1686 1723
1687 1724 /*
1688 1725 * This function is sort of the wrong API because it takes two pointer
1689 1726 * and adds them together. The caller is expected to figure out
1690 1727 * alignment. Neither of those are the correct things to do.
1691 1728 *
1692 1729 * Really this function is quite bogus...
1693 1730 */
1694 1731
1695 1732 if (rl_to_sval(left, &l_sval) && rl_to_sval(right, &r_sval)) {
1696 1733 res = sval_binop(l_sval, op, r_sval);
1697 1734 return alloc_rl(res, res);
1698 1735 }
1699 1736
1700 1737 if (rl_min(left).value != 0 || rl_max(right).value != 0) {
1701 1738 ret = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
1702 1739 return cast_rl(rl_type(left), ret);
1703 1740 }
1704 1741
1705 1742 return alloc_whole_rl(rl_type(left));
1706 1743 }
1707 1744
1708 1745 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1709 1746 {
1710 1747 sval_t min, max;
1711 1748
1712 1749 if (type_is_ptr(rl_type(left)) || type_is_ptr(rl_type(right)))
1713 1750 return ptr_add_mult(left, op, right);
1714 1751
1715 1752 if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1716 1753 return NULL;
1717 1754 min = sval_binop(rl_min(left), op, rl_min(right));
1718 1755
1719 1756 if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1720 1757 return NULL;
1721 1758 max = sval_binop(rl_max(left), op, rl_max(right));
1722 1759
1723 1760 return alloc_rl(min, max);
1724 1761 }
1725 1762
1726 1763 static struct range_list *handle_sub_rl(struct range_list *left_orig, struct range_list *right_orig)
1727 1764 {
1728 1765 struct range_list *left_rl, *right_rl;
1729 1766 struct symbol *type;
1730 1767 sval_t min, max;
1731 1768 sval_t min_ll, max_ll, res_ll;
1732 1769 sval_t tmp;
1733 1770
1734 1771 /* TODO: These things should totally be using dranges where possible */
1735 1772
1736 1773 if (!left_orig || !right_orig)
1737 1774 return NULL;
1738 1775
1739 1776 type = &int_ctype;
1740 1777 if (type_positive_bits(rl_type(left_orig)) > type_positive_bits(type))
1741 1778 type = rl_type(left_orig);
1742 1779 if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
1743 1780 type = rl_type(right_orig);
1744 1781
1745 1782 left_rl = cast_rl(type, left_orig);
1746 1783 right_rl = cast_rl(type, right_orig);
1747 1784
1748 1785 max = rl_max(left_rl);
1749 1786 min = sval_type_min(type);
1750 1787
1751 1788 min_ll = rl_min(left_rl);
1752 1789 min_ll.type = &llong_ctype;
1753 1790 max_ll = rl_max(right_rl);
1754 1791 max_ll.type = &llong_ctype;
1755 1792 res_ll = min_ll;
1756 1793 res_ll.value = min_ll.value - max_ll.value;
1757 1794
1758 1795 if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
1759 1796 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
1760 1797 if (sval_cmp(tmp, min) > 0)
1761 1798 min = tmp;
1762 1799 } else if (type_positive_bits(type) < 63 &&
1763 1800 !sval_binop_overflows(min_ll, '-', max_ll) &&
1764 1801 (min.value != 0 && sval_cmp(res_ll, min) >= 0)) {
1765 1802 struct range_list *left_casted, *right_casted, *result;
1766 1803
1767 1804 left_casted = cast_rl(&llong_ctype, left_orig);
1768 1805 right_casted = cast_rl(&llong_ctype, right_orig);
1769 1806 result = handle_sub_rl(left_casted, right_casted);
1770 1807 return cast_rl(type, result);
1771 1808 }
1772 1809
1773 1810 if (!sval_is_max(rl_max(left_rl))) {
1774 1811 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
1775 1812 if (sval_cmp(tmp, max) < 0)
1776 1813 max = tmp;
1777 1814 }
1778 1815
1779 1816 if (sval_is_min(min) && sval_is_max(max))
1780 1817 return NULL;
1781 1818
1782 1819 return alloc_rl(min, max);
1783 1820 }
1784 1821
1785 1822 static unsigned long long rl_bits_always_set(struct range_list *rl)
1786 1823 {
1787 1824 return sval_fls_mask(rl_min(rl));
1788 1825 }
1789 1826
1790 1827 static unsigned long long rl_bits_maybe_set(struct range_list *rl)
1791 1828 {
1792 1829 return sval_fls_mask(rl_max(rl));
1793 1830 }
1794 1831
1795 1832 static struct range_list *handle_OR_rl(struct range_list *left, struct range_list *right)
1796 1833 {
1797 1834 unsigned long long left_min, left_max, right_min, right_max;
1798 1835 sval_t min, max;
1799 1836 sval_t sval;
1800 1837
1801 1838 if ((rl_to_sval(left, &sval) || rl_to_sval(right, &sval)) &&
1802 1839 !sval_binop_overflows(rl_max(left), '+', rl_max(right)))
1803 1840 return rl_binop(left, '+', right);
1804 1841
1805 1842 left_min = rl_bits_always_set(left);
1806 1843 left_max = rl_bits_maybe_set(left);
1807 1844 right_min = rl_bits_always_set(right);
1808 1845 right_max = rl_bits_maybe_set(right);
1809 1846
1810 1847 min.type = max.type = &ullong_ctype;
1811 1848 min.uvalue = left_min | right_min;
1812 1849 max.uvalue = left_max | right_max;
1813 1850
1814 1851 return cast_rl(rl_type(left), alloc_rl(min, max));
1815 1852 }
1816 1853
1817 1854 static struct range_list *handle_XOR_rl(struct range_list *left, struct range_list *right)
1818 1855 {
1819 1856 unsigned long long left_set, left_maybe;
1820 1857 unsigned long long right_set, right_maybe;
1821 1858 sval_t zero, max;
1822 1859
1823 1860 left_set = rl_bits_always_set(left);
1824 1861 left_maybe = rl_bits_maybe_set(left);
1825 1862
1826 1863 right_set = rl_bits_always_set(right);
1827 1864 right_maybe = rl_bits_maybe_set(right);
1828 1865
1829 1866 zero = max = rl_min(left);
1830 1867 zero.uvalue = 0;
1831 1868 max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1832 1869
1833 1870 return cast_rl(rl_type(left), alloc_rl(zero, max));
1834 1871 }
1835 1872
1836 1873 static sval_t sval_lowest_set_bit(sval_t sval)
1837 1874 {
1838 1875 sval_t ret = { .type = sval.type };
1839 1876 int i;
|
↓ open down ↓ |
553 lines elided |
↑ open up ↑ |
1840 1877
1841 1878 for (i = 0; i < 64; i++) {
1842 1879 if (sval.uvalue & 1ULL << i) {
1843 1880 ret.uvalue = (1ULL << i);
1844 1881 return ret;
1845 1882 }
1846 1883 }
1847 1884 return ret;
1848 1885 }
1849 1886
1850 -static struct range_list *handle_AND_rl_sval(struct range_list *rl, sval_t sval)
1851 -{
1852 - struct range_list *known_rl;
1853 - sval_t zero = { 0 };
1854 - sval_t min;
1855 -
1856 - zero.type = sval.type;
1857 - zero.value = 0;
1858 -
1859 - if (sm_fls64(rl_max(rl).uvalue) < find_first_zero_bit(sval.uvalue) &&
1860 - sm_fls64(rl_min(rl).uvalue) < find_first_zero_bit(sval.uvalue))
1861 - return rl;
1862 -
1863 - min = sval_lowest_set_bit(sval);
1864 -
1865 - if (min.value != 0) {
1866 - sval_t max, mod;
1867 -
1868 - max = rl_max(rl);
1869 - mod = sval_binop(max, '%', min);
1870 - if (mod.value) {
1871 - max = sval_binop(max, '-', mod);
1872 - max.value++;
1873 - if (max.value > 0 && sval_cmp(max, rl_max(rl)) < 0)
1874 - rl = remove_range(rl, max, rl_max(rl));
1875 - }
1876 - }
1877 -
1878 - known_rl = alloc_rl(min, sval);
1879 -
1880 - rl = rl_intersection(rl, known_rl);
1881 - zero = rl_min(rl);
1882 - zero.value = 0;
1883 - add_range(&rl, zero, zero);
1884 -
1885 - return rl;
1886 -}
1887 -
1888 -static struct range_list *fudge_AND_rl(struct range_list *rl)
1889 -{
1890 - struct range_list *ret;
1891 - sval_t min;
1892 -
1893 - min = sval_lowest_set_bit(rl_min(rl));
1894 - ret = clone_rl(rl);
1895 - add_range(&ret, min, rl_min(rl));
1896 -
1897 - return ret;
1898 -}
1899 -
1900 1887 static struct range_list *handle_AND_rl(struct range_list *left, struct range_list *right)
1901 1888 {
1902 - sval_t sval, zero;
1889 + struct bit_info *one, *two;
1903 1890 struct range_list *rl;
1891 + sval_t min, max, zero;
1892 + unsigned long long bits;
1904 1893
1905 - if (rl_to_sval(left, &sval))
1906 - return handle_AND_rl_sval(right, sval);
1907 - if (rl_to_sval(right, &sval))
1908 - return handle_AND_rl_sval(left, sval);
1894 + one = rl_to_binfo(left);
1895 + two = rl_to_binfo(right);
1896 + bits = one->possible & two->possible;
1909 1897
1910 - left = fudge_AND_rl(left);
1911 - right = fudge_AND_rl(right);
1898 + max = rl_max(left);
1899 + max.uvalue = bits;
1900 + min = sval_lowest_set_bit(max);
1912 1901
1913 - rl = rl_intersection(left, right);
1902 + rl = alloc_rl(min, max);
1903 +
1914 1904 zero = rl_min(rl);
1915 1905 zero.value = 0;
1916 1906 add_range(&rl, zero, zero);
1917 1907
1918 1908 return rl;
1919 1909 }
1920 1910
1921 1911 static struct range_list *handle_lshift(struct range_list *left_orig, struct range_list *right_orig)
1922 1912 {
1923 1913 struct range_list *left;
1924 1914 struct data_range *tmp;
1925 1915 struct range_list *ret = NULL;
1926 1916 sval_t zero = { .type = rl_type(left_orig), };
1927 1917 sval_t shift, min, max;
1928 1918 bool add_zero = false;
1929 1919
1930 1920 if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
1931 1921 return NULL;
1932 1922 if (shift.value == 0)
1933 1923 return left_orig;
1934 1924
1935 1925 /* Cast to unsigned for easier left shift math */
1936 1926 if (type_positive_bits(rl_type(left_orig)) < 32)
1937 1927 left = cast_rl(&uint_ctype, left_orig);
1938 1928 else if(type_positive_bits(rl_type(left_orig)) == 63)
1939 1929 left = cast_rl(&ullong_ctype, left_orig);
1940 1930 else
1941 1931 left = left_orig;
1942 1932
1943 1933 FOR_EACH_PTR(left, tmp) {
1944 1934 min = tmp->min;
1945 1935 max = tmp->max;
1946 1936
1947 1937 if (min.value == 0 || max.value > sval_type_max(max.type).uvalue >> shift.uvalue)
1948 1938 add_zero = true;
1949 1939 if (min.value == 0 && max.value == 0)
1950 1940 continue;
1951 1941 if (min.value == 0)
1952 1942 min.value = 1;
1953 1943 min = sval_binop(min, SPECIAL_LEFTSHIFT, shift);
1954 1944 max = sval_binop(max, SPECIAL_LEFTSHIFT, shift);
1955 1945 add_range(&ret, min, max);
1956 1946 } END_FOR_EACH_PTR(tmp);
1957 1947
1958 1948 if (!rl_fits_in_type(ret, rl_type(left_orig)))
1959 1949 add_zero = true;
1960 1950 ret = cast_rl(rl_type(left_orig), ret);
1961 1951 if (add_zero)
1962 1952 add_range(&ret, zero, zero);
1963 1953
1964 1954 return ret;
1965 1955 }
1966 1956
1967 1957 static struct range_list *handle_rshift(struct range_list *left_orig, struct range_list *right_orig)
1968 1958 {
1969 1959 struct data_range *tmp;
1970 1960 struct range_list *ret = NULL;
1971 1961 sval_t shift, min, max;
1972 1962
1973 1963 if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
1974 1964 return NULL;
1975 1965 if (shift.value == 0)
1976 1966 return left_orig;
1977 1967
1978 1968 FOR_EACH_PTR(left_orig, tmp) {
1979 1969 min = sval_binop(tmp->min, SPECIAL_RIGHTSHIFT, shift);
1980 1970 max = sval_binop(tmp->max, SPECIAL_RIGHTSHIFT, shift);
1981 1971 add_range(&ret, min, max);
1982 1972 } END_FOR_EACH_PTR(tmp);
1983 1973
1984 1974 return ret;
1985 1975 }
1986 1976
1987 1977 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1988 1978 {
1989 1979 struct symbol *cast_type;
1990 1980 sval_t left_sval, right_sval;
1991 1981 struct range_list *ret = NULL;
1992 1982
1993 1983 cast_type = rl_type(left);
1994 1984 if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
1995 1985 cast_type = rl_type(right);
1996 1986 if (sval_type_max(cast_type).uvalue < INT_MAX)
1997 1987 cast_type = &int_ctype;
1998 1988
1999 1989 left = cast_rl(cast_type, left);
2000 1990 right = cast_rl(cast_type, right);
2001 1991
2002 1992 if (!left && !right)
2003 1993 return NULL;
2004 1994
2005 1995 if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
2006 1996 sval_t val = sval_binop(left_sval, op, right_sval);
2007 1997 return alloc_rl(val, val);
2008 1998 }
2009 1999
2010 2000 switch (op) {
2011 2001 case '%':
2012 2002 ret = handle_mod_rl(left, right);
2013 2003 break;
2014 2004 case '/':
2015 2005 ret = handle_divide_rl(left, right);
2016 2006 break;
2017 2007 case '*':
2018 2008 case '+':
2019 2009 ret = handle_add_mult_rl(left, op, right);
2020 2010 break;
2021 2011 case '|':
2022 2012 ret = handle_OR_rl(left, right);
2023 2013 break;
2024 2014 case '^':
2025 2015 ret = handle_XOR_rl(left, right);
2026 2016 break;
2027 2017 case '&':
2028 2018 ret = handle_AND_rl(left, right);
2029 2019 break;
2030 2020 case '-':
2031 2021 ret = handle_sub_rl(left, right);
2032 2022 break;
2033 2023 case SPECIAL_RIGHTSHIFT:
2034 2024 return handle_rshift(left, right);
2035 2025 case SPECIAL_LEFTSHIFT:
2036 2026 return handle_lshift(left, right);
2037 2027 }
2038 2028
2039 2029 return ret;
2040 2030 }
2041 2031
2042 2032 void free_data_info_allocs(void)
2043 2033 {
2044 2034 struct allocator_struct *desc = &data_info_allocator;
2045 2035 struct allocation_blob *blob = desc->blobs;
2046 2036
2047 2037 free_all_rl();
2048 2038 clear_math_cache();
2049 2039
2050 2040 desc->blobs = NULL;
2051 2041 desc->allocations = 0;
2052 2042 desc->total_bytes = 0;
2053 2043 desc->useful_bytes = 0;
2054 2044 desc->freelist = NULL;
2055 2045 while (blob) {
2056 2046 struct allocation_blob *next = blob->next;
2057 2047 blob_free(blob, desc->chunking);
2058 2048 blob = next;
2059 2049 }
2060 2050 clear_data_range_alloc();
2061 2051 }
2062 2052
2063 2053 void split_comparison_rl(struct range_list *left_orig, int op, struct range_list *right_orig,
2064 2054 struct range_list **left_true_rl, struct range_list **left_false_rl,
2065 2055 struct range_list **right_true_rl, struct range_list **right_false_rl)
2066 2056 {
2067 2057 struct range_list *left_true, *left_false;
2068 2058 struct range_list *right_true, *right_false;
2069 2059 sval_t min, max;
2070 2060
2071 2061 min = sval_type_min(rl_type(left_orig));
2072 2062 max = sval_type_max(rl_type(left_orig));
2073 2063
2074 2064 left_true = clone_rl(left_orig);
2075 2065 left_false = clone_rl(left_orig);
2076 2066 right_true = clone_rl(right_orig);
2077 2067 right_false = clone_rl(right_orig);
2078 2068
2079 2069 switch (op) {
2080 2070 case '<':
2081 2071 case SPECIAL_UNSIGNED_LT:
2082 2072 left_true = remove_range(left_orig, rl_max(right_orig), max);
2083 2073 if (!sval_is_min(rl_min(right_orig))) {
2084 2074 left_false = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
2085 2075 }
2086 2076
2087 2077 right_true = remove_range(right_orig, min, rl_min(left_orig));
2088 2078 if (!sval_is_max(rl_max(left_orig)))
2089 2079 right_false = remove_range(right_orig, add_one(rl_max(left_orig)), max);
2090 2080 break;
2091 2081 case SPECIAL_UNSIGNED_LTE:
2092 2082 case SPECIAL_LTE:
2093 2083 if (!sval_is_max(rl_max(right_orig)))
2094 2084 left_true = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2095 2085 left_false = remove_range(left_orig, min, rl_min(right_orig));
2096 2086
2097 2087 if (!sval_is_min(rl_min(left_orig)))
2098 2088 right_true = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2099 2089 right_false = remove_range(right_orig, rl_max(left_orig), max);
2100 2090
2101 2091 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
2102 2092 left_false = remove_range(left_false, rl_min(left_orig), rl_min(left_orig));
2103 2093 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
2104 2094 right_false = remove_range(right_false, rl_max(left_orig), rl_max(left_orig));
2105 2095 break;
2106 2096 case SPECIAL_EQUAL:
2107 2097 left_true = rl_intersection(left_orig, right_orig);
2108 2098 right_true = clone_rl(left_true);
2109 2099
2110 2100 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2111 2101 left_false = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2112 2102 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2113 2103 right_false = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2114 2104 break;
2115 2105 case SPECIAL_UNSIGNED_GTE:
2116 2106 case SPECIAL_GTE:
2117 2107 if (!sval_is_min(rl_min(right_orig)))
2118 2108 left_true = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
2119 2109 left_false = remove_range(left_orig, rl_max(right_orig), max);
2120 2110
2121 2111 if (!sval_is_max(rl_max(left_orig)))
2122 2112 right_true = remove_range(right_orig, add_one(rl_max(left_orig)), max);
2123 2113 right_false = remove_range(right_orig, min, rl_min(left_orig));
2124 2114
2125 2115 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
2126 2116 right_false = remove_range(right_false, rl_min(left_orig), rl_min(left_orig));
2127 2117 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
2128 2118 left_false = remove_range(left_false, rl_max(left_orig), rl_max(left_orig));
2129 2119 break;
2130 2120 case '>':
2131 2121 case SPECIAL_UNSIGNED_GT:
2132 2122 left_true = remove_range(left_orig, min, rl_min(right_orig));
2133 2123 if (!sval_is_max(rl_max(right_orig)))
2134 2124 left_false = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2135 2125
2136 2126 right_true = remove_range(right_orig, rl_max(left_orig), max);
2137 2127 if (!sval_is_min(rl_min(left_orig)))
2138 2128 right_false = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2139 2129 break;
2140 2130 case SPECIAL_NOTEQUAL:
|
↓ open down ↓ |
217 lines elided |
↑ open up ↑ |
2141 2131 left_false = rl_intersection(left_orig, right_orig);
2142 2132 right_false = clone_rl(left_false);
2143 2133
2144 2134 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2145 2135 left_true = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2146 2136 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2147 2137 right_true = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2148 2138 break;
2149 2139 default:
2150 2140 sm_perror(" unhandled comparison %d", op);
2151 - return;
2152 2141 }
2153 2142
2154 2143 if (left_true_rl) {
2155 2144 *left_true_rl = left_true;
2156 2145 *left_false_rl = left_false;
2157 2146 }
2158 2147 if (right_true_rl) {
2159 2148 *right_true_rl = right_true;
2160 2149 *right_false_rl = right_false;
2161 2150 }
2162 2151 }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX