smatch_math.c

   1 /*
   2  * smatch/smatch_math.c
   3  *
   4  * Copyright (C) 2010 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include "smatch.h"
  11 #include "smatch_slist.h"
  12 #include "smatch_extra.h"
  13
  14 static long long _get_implied_value(struct expression *expr, int *undefined, int implied);
  15 static long long _get_value(struct expression *expr, int *undefined, int implied);
  16
  17 #define BOGUS 12345
  18
  19 #define NOTIMPLIED  0
  20 #define IMPLIED     1
  21 #define IMPLIED_MIN 2
  22 #define IMPLIED_MAX 3
  23 #define FUZZYMAX    4
  24 #define FUZZYMIN    5
  25
  26 static long long cast_to_type(struct expression *expr, long long val)
  27 {
  28         struct symbol *type = get_type(expr);
  29
  30         if (!type)
  31                 return val;
  32
  33         switch (type->bit_size) {
  34         case 8:
  35                 if (type->ctype.modifiers & MOD_UNSIGNED)
  36                         val = (long long)(unsigned char) val;
  37                 else
  38                         val = (long long)(char) val;
  39                 break;
  40         case 16:
  41                 if (type->ctype.modifiers & MOD_UNSIGNED)
  42                         val = (long long)(unsigned short) val;
  43                 else
  44                         val = (long long)(short) val;
  45                 break;
  46         case 32:
  47                 if (type->ctype.modifiers & MOD_UNSIGNED)
  48                         val = (long long)(unsigned int) val;
  49                 else
  50                         val = (long long)(int) val;
  51                 break;
  52         }
  53         return val;
  54 }
  55
  56 static int opposite_implied(int implied)
  57 {
  58         if (implied == IMPLIED_MIN)
  59                 return IMPLIED_MAX;
  60         if (implied == IMPLIED_MAX)
  61                 return IMPLIED_MIN;
  62         return implied;
  63 }
  64
  65 static int last_stmt_val(struct statement *stmt, long long *val)
  66 {
  67         struct expression *expr;
  68
  69         if (!stmt)
  70                 return 0;
  71
  72         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
  73         if (stmt->type != STMT_EXPRESSION)
  74                 return 0;
  75         expr = stmt->expression;
  76         return get_value(expr, val);
  77 }
  78
  79 static long long handle_expression_statement(struct expression *expr, int *undefined, int implied)
  80 {
  81         struct statement *stmt;
  82         long long tmp;
  83
  84         stmt = get_expression_statement(expr);
  85         if (last_stmt_val(stmt, &tmp))
  86                 return tmp;
  87
  88         *undefined = 1;
  89         return BOGUS;
  90 }
  91
  92 static long long handle_ampersand(int *undefined, int implied)
  93 {
  94         if (implied == IMPLIED_MIN || implied == FUZZYMIN)
  95                 return valid_ptr_min;
  96         if (implied == IMPLIED_MAX || implied == FUZZYMAX)
  97                 return valid_ptr_max;
  98
  99         *undefined = 1;
 100         return BOGUS;
 101 }
 102
 103 static long long handle_preop(struct expression *expr, int *undefined, int implied)
 104 {
 105         long long ret = BOGUS;
 106
 107         switch (expr->op) {
 108         case '&':
 109                 ret = handle_ampersand(undefined, implied);
 110                 break;
 111         case '!':
 112                 ret = !_get_value(expr->unop, undefined, implied);
 113                 break;
 114         case '~':
 115                 ret = ~_get_value(expr->unop, undefined, implied);
 116                 ret = cast_to_type(expr->unop, ret);
 117                 break;
 118         case '-':
 119                 ret = -_get_value(expr->unop, undefined, implied);
 120                 break;
 121         case '*':
 122                 ret = _get_implied_value(expr, undefined, implied);
 123                 break;
 124         case '(':
 125                 ret = handle_expression_statement(expr, undefined, implied);
 126                 break;
 127         default:
 128                 *undefined = 1;
 129         }
 130         return ret;
 131 }
 132
 133 static long long handle_divide(struct expression *expr, int *undefined, int implied)
 134 {
 135         long long left;
 136         long long right;
 137         long long ret = BOGUS;
 138
 139         left = _get_value(expr->left, undefined, implied);
 140         right = _get_value(expr->right, undefined, opposite_implied(implied));
 141
 142         if (right == 0)
 143                 *undefined = 1;
 144         else
 145                 ret = left / right;
 146
 147         return ret;
 148 }
 149
 150 static long long handle_subtract(struct expression *expr, int *undefined, int implied)
 151 {
 152         long long left;
 153         long long right;
 154
 155         left = _get_value(expr->left, undefined, implied);
 156         right = _get_value(expr->right, undefined, opposite_implied(implied));
 157
 158         return left - right;
 159 }
 160
 161 static long long handle_binop(struct expression *expr, int *undefined, int implied)
 162 {
 163         long long left;
 164         long long right;
 165         long long ret = BOGUS;
 166
 167         if (expr->type != EXPR_BINOP) {
 168                 *undefined = 1;
 169                 return ret;
 170         }
 171
 172         left = _get_value(expr->left, undefined, implied);
 173         right = _get_value(expr->right, undefined, implied);
 174
 175         switch (expr->op) {
 176         case '*':
 177                 ret =  left * right;
 178                 break;
 179         case '/':
 180                 ret = handle_divide(expr, undefined, implied);
 181                 break;
 182         case '+':
 183                 ret = left + right;
 184                 break;
 185         case '-':
 186                 ret = handle_subtract(expr, undefined, implied);
 187                 break;
 188         case '%':
 189                 if (right == 0)
 190                         *undefined = 1;
 191                 else
 192                         ret = left % right;
 193                 break;
 194         case '|':
 195                 ret = left | right;
 196                 break;
 197         case '&':
 198                 ret = left & right;
 199                 break;
 200         case SPECIAL_RIGHTSHIFT:
 201                 ret = left >> right;
 202                 break;
 203         case SPECIAL_LEFTSHIFT:
 204                 ret = left << right;
 205                 break;
 206         case '^':
 207                 ret = left ^ right;
 208                 break;
 209         default:
 210                 *undefined = 1;
 211         }
 212         return ret;
 213 }
 214
 215 static int do_comparison(struct expression *expr)
 216 {
 217         struct range_list *left_ranges = NULL;
 218         struct range_list *right_ranges = NULL;
 219         int poss_true, poss_false;
 220
 221         get_implied_range_list(expr->left, &left_ranges);
 222         get_implied_range_list(expr->right, &right_ranges);
 223
 224         poss_true = possibly_true_range_lists(left_ranges, expr->op, right_ranges);
 225         poss_false = possibly_false_range_lists(left_ranges, expr->op, right_ranges);
 226
 227         free_range_list(&left_ranges);
 228         free_range_list(&right_ranges);
 229
 230         if (!poss_true && !poss_false)
 231                 return 0;
 232         if (poss_true && !poss_false)
 233                 return 1;
 234         if (!poss_true && poss_false)
 235                 return 2;
 236         return 3;
 237 }
 238
 239 static long long handle_comparison(struct expression *expr, int *undefined, int implied)
 240 {
 241         long long left, right;
 242         int res;
 243
 244         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 245                 struct data_range tmp_left, tmp_right;
 246
 247                 tmp_left.min = left;
 248                 tmp_left.max = left;
 249                 tmp_right.min = right;
 250                 tmp_right.max = right;
 251                 return true_comparison_range(&tmp_left, expr->op, &tmp_right);
 252         }
 253
 254         if (implied == NOTIMPLIED) {
 255                 *undefined = 1;
 256                 return BOGUS;
 257         }
 258
 259         res = do_comparison(expr);
 260         if (res == 1)
 261                 return 1;
 262         if (res == 2)
 263                 return 0;
 264
 265         if (implied == IMPLIED_MIN || implied == FUZZYMIN)
 266                 return 0;
 267         if (implied == IMPLIED_MAX || implied == FUZZYMAX)
 268                 return 1;
 269
 270         *undefined = 1;
 271         return BOGUS;
 272 }
 273
 274 static long long handle_logical(struct expression *expr, int *undefined, int implied)
 275 {
 276         long long left_val, right_val;
 277
 278         if ((implied == NOTIMPLIED && get_value(expr->left, &left_val) &&
 279                                       get_value(expr->right, &right_val)) ||
 280             (implied != NOTIMPLIED && get_implied_value(expr->left, &left_val) &&
 281                                       get_implied_value(expr->right, &right_val))) {
 282                 switch (expr->op) {
 283                 case SPECIAL_LOGICAL_OR:
 284                         return left_val || right_val;
 285                 case SPECIAL_LOGICAL_AND:
 286                         return left_val && right_val;
 287                 default:
 288                         *undefined = 1;
 289                         return BOGUS;
 290                 }
 291         }
 292
 293         if (implied == IMPLIED_MIN || implied == FUZZYMIN)
 294                 return 0;
 295         if (implied == IMPLIED_MAX || implied == FUZZYMAX)
 296                 return 1;
 297
 298         *undefined = 1;
 299         return BOGUS;
 300 }
 301
 302 static long long handle_conditional(struct expression *expr, int *undefined, int implied)
 303 {
 304         if (known_condition_true(expr->conditional))
 305                 return _get_value(expr->cond_true, undefined, implied);
 306         if (known_condition_false(expr->conditional))
 307                 return _get_value(expr->cond_false, undefined, implied);
 308
 309         if (implied == NOTIMPLIED) {
 310                 *undefined = 1;
 311                 return BOGUS;
 312         }
 313
 314         if (implied_condition_true(expr->conditional))
 315                 return _get_value(expr->cond_true, undefined, implied);
 316         if (implied_condition_false(expr->conditional))
 317                 return _get_value(expr->cond_false, undefined, implied);
 318
 319         *undefined = 1;
 320         return BOGUS;
 321 }
 322
 323 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
 324 {
 325         struct smatch_state *state;
 326         struct symbol *sym;
 327         char *name;
 328
 329         expr = strip_expr(expr);
 330
 331         if (get_value(expr, val))
 332                 return 1;
 333
 334         name = get_variable_from_expr(expr, &sym);
 335         if (!name)
 336                 return 0;
 337         state = get_state(SMATCH_EXTRA, name, sym);
 338         free_string(name);
 339         if (!state || !state->data)
 340                 return 0;
 341         if (what == IMPLIED)
 342                 return estate_get_single_value(state, val);
 343         if (what == IMPLIED_MAX) {
 344                 *val = estate_max(state);
 345                 if (*val == whole_range.max) /* this means just guessing */
 346                         return 0;
 347                 return 1;
 348         }
 349         *val = estate_min(state);
 350         if (*val == whole_range.min)
 351                 return 0;
 352         return 1;
 353 }
 354
 355 static int get_fuzzy_max_helper(struct expression *expr, long long *max)
 356 {
 357         struct sm_state *sm;
 358         struct sm_state *tmp;
 359
 360         if (get_implied_max(expr, max))
 361                 return 1;
 362
 363         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 364         if (!sm)
 365                 return 0;
 366
 367         *max = whole_range.min;
 368         FOR_EACH_PTR(sm->possible, tmp) {
 369                 long long new_min;
 370
 371                 new_min = estate_min(tmp->state);
 372                 if (new_min > *max)
 373                         *max = new_min;
 374         } END_FOR_EACH_PTR(tmp);
 375
 376         if (*max > whole_range.min)
 377                 return 1;
 378         return 0;
 379 }
 380
 381 static int get_fuzzy_min_helper(struct expression *expr, long long *min)
 382 {
 383         struct sm_state *sm;
 384         struct sm_state *tmp;
 385
 386         if (get_implied_min(expr, min))
 387                 return 1;
 388
 389         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 390         if (!sm)
 391                 return 0;
 392
 393         *min = whole_range.max;
 394         FOR_EACH_PTR(sm->possible, tmp) {
 395                 long long new_max;
 396
 397                 new_max = estate_max(tmp->state);
 398                 if (new_max < *min)
 399                         *min = new_max;
 400         } END_FOR_EACH_PTR(tmp);
 401
 402         if (*min < whole_range.max)
 403                 return 1;
 404         return 0;
 405 }
 406
 407 static long long _get_implied_value(struct expression *expr, int *undefined, int implied)
 408 {
 409         long long ret = BOGUS;
 410
 411         switch (implied) {
 412         case IMPLIED:
 413         case IMPLIED_MAX:
 414         case IMPLIED_MIN:
 415                 if (!get_implied_value_helper(expr, &ret, implied))
 416                         *undefined = 1;
 417                 break;
 418         case FUZZYMAX:
 419                 if (!get_fuzzy_max_helper(expr, &ret))
 420                         *undefined = 1;
 421                 break;
 422         case FUZZYMIN:
 423                 if (!get_fuzzy_min_helper(expr, &ret))
 424                         *undefined = 1;
 425                 break;
 426         default:
 427                 *undefined = 1;
 428         }
 429         return ret;
 430 }
 431
 432 static int get_const_value(struct expression *expr, long long *val)
 433 {
 434         struct symbol *sym;
 435
 436         sym = expr->symbol;
 437         if (!sym)
 438                 return 0;
 439         if (!(sym->ctype.modifiers & MOD_CONST))
 440                 return 0;
 441         if (get_value(sym->initializer, val))
 442                 return 1;
 443         return 0;
 444 }
 445
 446 static long long _get_value(struct expression *expr, int *undefined, int implied)
 447 {
 448         long long ret = BOGUS;
 449
 450         if (!expr) {
 451                 *undefined = 1;
 452                 return BOGUS;
 453         }
 454         if (*undefined)
 455                 return BOGUS;
 456
 457         expr = strip_parens(expr);
 458
 459         switch (expr->type) {
 460         case EXPR_VALUE:
 461                 ret = expr->value;
 462                 ret = cast_to_type(expr, ret);
 463                 break;
 464         case EXPR_PREOP:
 465                 ret = handle_preop(expr, undefined, implied);
 466                 break;
 467         case EXPR_POSTOP:
 468                 ret = _get_value(expr->unop, undefined, implied);
 469                 break;
 470         case EXPR_CAST:
 471         case EXPR_FORCE_CAST:
 472         case EXPR_IMPLIED_CAST:
 473                 ret = _get_value(expr->cast_expression, undefined, implied);
 474                 return cast_to_type(expr, ret);
 475         case EXPR_BINOP:
 476                 ret = handle_binop(expr, undefined, implied);
 477                 break;
 478         case EXPR_COMPARE:
 479                 ret = handle_comparison(expr, undefined, implied);
 480                 break;
 481         case EXPR_LOGICAL:
 482                 ret = handle_logical(expr, undefined, implied);
 483                 break;
 484         case EXPR_PTRSIZEOF:
 485         case EXPR_SIZEOF:
 486                 ret = get_expression_value_nomod(expr);
 487                 break;
 488         case EXPR_SYMBOL:
 489                 if (get_const_value(expr, &ret))
 490                         break;
 491                 ret = _get_implied_value(expr, undefined, implied);
 492                 break;
 493         case EXPR_SELECT:
 494         case EXPR_CONDITIONAL:
 495                 ret = handle_conditional(expr, undefined, implied);
 496                 break;
 497         default:
 498                 ret = _get_implied_value(expr, undefined, implied);
 499         }
 500         if (*undefined)
 501                 return BOGUS;
 502         return ret;
 503 }
 504
 505 /* returns 1 if it can get a value literal or else returns 0 */
 506 int get_value(struct expression *expr, long long *val)
 507 {
 508         int undefined = 0;
 509
 510         *val = _get_value(expr, &undefined, NOTIMPLIED);
 511         if (undefined)
 512                 return 0;
 513         return 1;
 514 }
 515
 516 int get_implied_value(struct expression *expr, long long *val)
 517 {
 518         int undefined = 0;
 519
 520         *val =  _get_value(expr, &undefined, IMPLIED);
 521         return !undefined;
 522 }
 523
 524 int get_implied_min(struct expression *expr, long long *val)
 525 {
 526         int undefined = 0;
 527
 528         *val =  _get_value(expr, &undefined, IMPLIED_MIN);
 529         return !undefined;
 530 }
 531
 532 int get_implied_max(struct expression *expr, long long *val)
 533 {
 534         int undefined = 0;
 535
 536         *val =  _get_value(expr, &undefined, IMPLIED_MAX);
 537         return !undefined;
 538 }
 539
 540 int get_fuzzy_min(struct expression *expr, long long *val)
 541 {
 542         int undefined = 0;
 543
 544         *val =  _get_value(expr, &undefined, FUZZYMIN);
 545         return !undefined;
 546 }
 547
 548 int get_fuzzy_max(struct expression *expr, long long *val)
 549 {
 550         int undefined = 0;
 551
 552         *val =  _get_value(expr, &undefined, FUZZYMAX);
 553         return !undefined;
 554 }
 555
 556 int get_absolute_min(struct expression *expr, long long *val)
 557 {
 558         struct symbol *type;
 559         long long min;
 560
 561         type = get_type(expr);
 562         if (!type) {
 563                 if (get_value(expr, val))
 564                         return 1;
 565                 return 0;
 566         }
 567         min = type_min(type);
 568         if (!get_implied_min(expr, val) || *val < min)
 569                 *val = min;
 570         return 1;
 571 }
 572
 573 int get_absolute_max(struct expression *expr, long long *val)
 574 {
 575         struct symbol *type;
 576         long long max;
 577
 578         type = get_type(expr);
 579         if (!type) {
 580                 if (get_value(expr, val))
 581                         return 1;
 582                 return 0;
 583         }
 584         max = type_max(type);
 585         if (!get_implied_max(expr, val) || *val > max)
 586                 *val = max;
 587         if (*val < type_min(type))
 588                 *val = max;
 589         return 1;
 590 }
 591
 592 int known_condition_true(struct expression *expr)
 593 {
 594         long long tmp;
 595
 596         if (!expr)
 597                 return 0;
 598
 599         if (get_value(expr, &tmp) && tmp)
 600                 return 1;
 601
 602         return 0;
 603 }
 604
 605 int known_condition_false(struct expression *expr)
 606 {
 607         if (!expr)
 608                 return 0;
 609
 610         if (is_zero(expr))
 611                 return 1;
 612
 613         if (expr->type == EXPR_CALL) {
 614                 if (sym_name_is("__builtin_constant_p", expr->fn))
 615                         return 1;
 616         }
 617         return 0;
 618 }
 619
 620 int implied_condition_true(struct expression *expr)
 621 {
 622         long long tmp;
 623
 624         if (!expr)
 625                 return 0;
 626
 627         if (known_condition_true(expr))
 628                 return 1;
 629         if (get_implied_value(expr, &tmp) && tmp)
 630                 return 1;
 631
 632         if (expr->type == EXPR_POSTOP)
 633                 return implied_condition_true(expr->unop);
 634
 635         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 636                 return implied_not_equal(expr->unop, 1);
 637         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 638                 return implied_not_equal(expr->unop, -1);
 639
 640         expr = strip_expr(expr);
 641         switch (expr->type) {
 642         case EXPR_COMPARE:
 643                 if (do_comparison(expr) == 1)
 644                         return 1;
 645                 break;
 646         case EXPR_PREOP:
 647                 if (expr->op == '!') {
 648                         if (implied_condition_false(expr->unop))
 649                                 return 1;
 650                         break;
 651                 }
 652                 break;
 653         default:
 654                 if (implied_not_equal(expr, 0) == 1)
 655                         return 1;
 656                 break;
 657         }
 658         return 0;
 659 }
 660
 661 int implied_condition_false(struct expression *expr)
 662 {
 663         struct expression *tmp;
 664         long long val;
 665
 666         if (!expr)
 667                 return 0;
 668
 669         if (known_condition_false(expr))
 670                 return 1;
 671
 672         switch (expr->type) {
 673         case EXPR_COMPARE:
 674                 if (do_comparison(expr) == 2)
 675                         return 1;
 676         case EXPR_PREOP:
 677                 if (expr->op == '!') {
 678                         if (implied_condition_true(expr->unop))
 679                                 return 1;
 680                         break;
 681                 }
 682                 tmp = strip_expr(expr);
 683                 if (tmp != expr)
 684                         return implied_condition_false(tmp);
 685                 break;
 686         default:
 687                 if (get_implied_value(expr, &val) && val == 0)
 688                         return 1;
 689                 break;
 690         }
 691         return 0;
 692 }