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