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
 104 static long long handle_preop(struct expression *expr, int *undefined, int implied)
 105 {
 106         long long ret = BOGUS;
 107
 108         switch (expr->op) {
 109         case '&':
 110                 ret = handle_ampersand(undefined, implied);
 111                 break;
 112         case '!':
 113                 ret = !_get_value(expr->unop, undefined, implied);
 114                 break;
 115         case '~':
 116                 ret = ~_get_value(expr->unop, undefined, implied);
 117                 ret = cast_to_type(expr->unop, ret);
 118                 break;
 119         case '-':
 120                 ret = -_get_value(expr->unop, undefined, implied);
 121                 break;
 122         case '*':
 123                 ret = _get_implied_value(expr, undefined, implied);
 124                 break;
 125         case '(':
 126                 ret = handle_expression_statement(expr, undefined, implied);
 127                 break;
 128         default:
 129                 *undefined = 1;
 130         }
 131         return ret;
 132 }
 133
 134 static long long handle_divide(struct expression *expr, int *undefined, int implied)
 135 {
 136         long long left;
 137         long long right;
 138         long long ret = BOGUS;
 139
 140         left = _get_value(expr->left, undefined, implied);
 141         right = _get_value(expr->right, undefined, opposite_implied(implied));
 142
 143         if (right == 0)
 144                 *undefined = 1;
 145         else
 146                 ret = left / right;
 147
 148         return ret;
 149 }
 150
 151 static long long handle_subtract(struct expression *expr, int *undefined, int implied)
 152 {
 153         long long left;
 154         long long right;
 155
 156         left = _get_value(expr->left, undefined, implied);
 157         right = _get_value(expr->right, undefined, opposite_implied(implied));
 158
 159         return left - right;
 160 }
 161
 162 static long long handle_binop(struct expression *expr, int *undefined, int implied)
 163 {
 164         long long left;
 165         long long right;
 166         long long ret = BOGUS;
 167
 168         if (expr->type != EXPR_BINOP) {
 169                 *undefined = 1;
 170                 return ret;
 171         }
 172
 173         left = _get_value(expr->left, undefined, implied);
 174         right = _get_value(expr->right, undefined, implied);
 175
 176         switch (expr->op) {
 177         case '*':
 178                 ret =  left * right;
 179                 break;
 180         case '/':
 181                 ret = handle_divide(expr, undefined, implied);
 182                 break;
 183         case '+':
 184                 ret = left + right;
 185                 break;
 186         case '-':
 187                 ret = handle_subtract(expr, undefined, implied);
 188                 break;
 189         case '%':
 190                 if (right == 0)
 191                         *undefined = 1;
 192                 else
 193                         ret = left % right;
 194                 break;
 195         case '|':
 196                 ret = left | right;
 197                 break;
 198         case '&':
 199                 ret = left & right;
 200                 break;
 201         case SPECIAL_RIGHTSHIFT:
 202                 ret = left >> right;
 203                 break;
 204         case SPECIAL_LEFTSHIFT:
 205                 ret = left << right;
 206                 break;
 207         case '^':
 208                 ret = left ^ right;
 209                 break;
 210         default:
 211                 *undefined = 1;
 212         }
 213         return ret;
 214 }
 215
 216 static int do_comparison(struct expression *expr)
 217 {
 218         struct range_list *left_ranges = NULL;
 219         struct range_list *right_ranges = NULL;
 220         int poss_true, poss_false;
 221
 222         get_implied_range_list(expr->left, &left_ranges);
 223         get_implied_range_list(expr->right, &right_ranges);
 224
 225         poss_true = possibly_true_range_lists(left_ranges, expr->op, right_ranges);
 226         poss_false = possibly_false_range_lists(left_ranges, expr->op, right_ranges);
 227
 228         free_range_list(&left_ranges);
 229         free_range_list(&right_ranges);
 230
 231         if (!poss_true && !poss_false)
 232                 return 0;
 233         if (poss_true && !poss_false)
 234                 return 1;
 235         if (!poss_true && poss_false)
 236                 return 2;
 237         return 3;
 238 }
 239
 240 static long long handle_comparison(struct expression *expr, int *undefined, int implied)
 241 {
 242         int res;
 243
 244         /* TODO: we should be able to handle this...  */
 245         if (implied == NOTIMPLIED) {
 246                 *undefined = 1;
 247                 return BOGUS;
 248         }
 249
 250         res = do_comparison(expr);
 251         if (res == 1)
 252                 return 1;
 253         if (res == 2)
 254                 return 0;
 255
 256         if (implied == IMPLIED_MIN || implied == FUZZYMIN)
 257                 return 0;
 258         if (implied == IMPLIED_MAX || implied == FUZZYMAX)
 259                 return 1;
 260
 261         *undefined = 1;
 262         return BOGUS;
 263 }
 264
 265 static long long handle_logical(struct expression *expr, int *undefined, int implied)
 266 {
 267         long long left_val, right_val;
 268
 269         /* TODO: we should be able to handle this...  */
 270         if (implied == NOTIMPLIED) {
 271                 *undefined = 1;
 272                 return BOGUS;
 273         }
 274
 275         if (get_implied_value(expr->left, &left_val) &&
 276                         get_implied_value(expr->right, &right_val)) {
 277                 switch (expr->op) {
 278                 case SPECIAL_LOGICAL_OR:
 279                         return left_val || right_val;
 280                 case SPECIAL_LOGICAL_AND:
 281                         return left_val && right_val;
 282                 default:
 283                         *undefined = 1;
 284                         return BOGUS;
 285                 }
 286         }
 287
 288         if (implied == IMPLIED_MIN || implied == FUZZYMIN)
 289                 return 0;
 290         if (implied == IMPLIED_MAX || implied == FUZZYMAX)
 291                 return 1;
 292
 293         *undefined = 1;
 294         return BOGUS;
 295 }
 296
 297 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
 298 {
 299         struct smatch_state *state;
 300         struct symbol *sym;
 301         char *name;
 302
 303         if (get_value(expr, val))
 304                 return 1;
 305
 306         name = get_variable_from_expr(expr, &sym);
 307         if (!name)
 308                 return 0;
 309         state = get_state(SMATCH_EXTRA, name, sym);
 310         free_string(name);
 311         if (!state || !state->data)
 312                 return 0;
 313         if (what == IMPLIED)
 314                 return estate_get_single_value(state, val);
 315         if (what == IMPLIED_MAX) {
 316                 *val = estate_max(state);
 317                 if (*val == whole_range.max) /* this means just guessing */
 318                         return 0;
 319                 return 1;
 320         }
 321         *val = estate_min(state);
 322         if (*val == whole_range.min)
 323                 return 0;
 324         return 1;
 325 }
 326
 327 static int get_fuzzy_max_helper(struct expression *expr, long long *max)
 328 {
 329         struct sm_state *sm;
 330         struct sm_state *tmp;
 331
 332         if (get_implied_max(expr, max))
 333                 return 1;
 334
 335         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 336         if (!sm)
 337                 return 0;
 338
 339         *max = whole_range.min;
 340         FOR_EACH_PTR(sm->possible, tmp) {
 341                 long long new_min;
 342
 343                 new_min = estate_min(tmp->state);
 344                 if (new_min > *max)
 345                         *max = new_min;
 346         } END_FOR_EACH_PTR(tmp);
 347
 348         if (*max > whole_range.min)
 349                 return 1;
 350         return 0;
 351 }
 352
 353 static int get_fuzzy_min_helper(struct expression *expr, long long *min)
 354 {
 355         struct sm_state *sm;
 356         struct sm_state *tmp;
 357
 358         if (get_implied_min(expr, min))
 359                 return 1;
 360
 361         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 362         if (!sm)
 363                 return 0;
 364
 365         *min = whole_range.max;
 366         FOR_EACH_PTR(sm->possible, tmp) {
 367                 long long new_max;
 368
 369                 new_max = estate_max(tmp->state);
 370                 if (new_max < *min)
 371                         *min = new_max;
 372         } END_FOR_EACH_PTR(tmp);
 373
 374         if (*min < whole_range.max)
 375                 return 1;
 376         return 0;
 377 }
 378
 379 static long long _get_implied_value(struct expression *expr, int *undefined, int implied)
 380 {
 381         long long ret = BOGUS;
 382
 383         switch (implied) {
 384         case IMPLIED:
 385         case IMPLIED_MAX:
 386         case IMPLIED_MIN:
 387                 if (!get_implied_value_helper(expr, &ret, implied))
 388                         *undefined = 1;
 389                 break;
 390         case FUZZYMAX:
 391                 if (!get_fuzzy_max_helper(expr, &ret))
 392                         *undefined = 1;
 393                 break;
 394         case FUZZYMIN:
 395                 if (!get_fuzzy_min_helper(expr, &ret))
 396                         *undefined = 1;
 397                 break;
 398         default:
 399                 *undefined = 1;
 400         }
 401         return ret;
 402 }
 403
 404 static int get_const_value(struct expression *expr, long long *val)
 405 {
 406         struct symbol *sym;
 407
 408         sym = expr->symbol;
 409         if (!sym)
 410                 return 0;
 411         if (!(sym->ctype.modifiers & MOD_CONST))
 412                 return 0;
 413         if (get_value(sym->initializer, val))
 414                 return 1;
 415         return 0;
 416 }
 417
 418 static long long _get_value(struct expression *expr, int *undefined, int implied)
 419 {
 420         long long ret = BOGUS;
 421
 422         if (!expr) {
 423                 *undefined = 1;
 424                 return BOGUS;
 425         }
 426         if (*undefined)
 427                 return BOGUS;
 428
 429         expr = strip_parens(expr);
 430
 431         switch (expr->type) {
 432         case EXPR_VALUE:
 433                 ret = expr->value;
 434                 ret = cast_to_type(expr, ret);
 435                 break;
 436         case EXPR_PREOP:
 437                 ret = handle_preop(expr, undefined, implied);
 438                 break;
 439         case EXPR_POSTOP:
 440                 ret = _get_value(expr->unop, undefined, implied);
 441                 break;
 442         case EXPR_CAST:
 443         case EXPR_FORCE_CAST:
 444         case EXPR_IMPLIED_CAST:
 445                 ret = _get_value(expr->cast_expression, undefined, implied);
 446                 return cast_to_type(expr, ret);
 447         case EXPR_BINOP:
 448                 ret = handle_binop(expr, undefined, implied);
 449                 break;
 450         case EXPR_COMPARE:
 451                 ret = handle_comparison(expr, undefined, implied);
 452                 break;
 453         case EXPR_LOGICAL:
 454                 ret = handle_logical(expr, undefined, implied);
 455                 break;
 456         case EXPR_PTRSIZEOF:
 457         case EXPR_SIZEOF:
 458                 ret = get_expression_value_nomod(expr);
 459                 break;
 460         case EXPR_SYMBOL:
 461                 if (get_const_value(expr, &ret))
 462                         break;
 463         default:
 464                 ret = _get_implied_value(expr, undefined, implied);
 465         }
 466         if (*undefined)
 467                 return BOGUS;
 468         return ret;
 469 }
 470
 471 /* returns 1 if it can get a value literal or else returns 0 */
 472 int get_value(struct expression *expr, long long *val)
 473 {
 474         int undefined = 0;
 475
 476         *val = _get_value(expr, &undefined, NOTIMPLIED);
 477         if (undefined)
 478                 return 0;
 479         return 1;
 480 }
 481
 482 int get_implied_value(struct expression *expr, long long *val)
 483 {
 484         int undefined = 0;
 485
 486         *val =  _get_value(expr, &undefined, IMPLIED);
 487         return !undefined;
 488 }
 489
 490 int get_implied_min(struct expression *expr, long long *val)
 491 {
 492         int undefined = 0;
 493
 494         *val =  _get_value(expr, &undefined, IMPLIED_MIN);
 495         return !undefined;
 496 }
 497
 498 int get_implied_max(struct expression *expr, long long *val)
 499 {
 500         int undefined = 0;
 501
 502         *val =  _get_value(expr, &undefined, IMPLIED_MAX);
 503         return !undefined;
 504 }
 505
 506 int get_fuzzy_min(struct expression *expr, long long *val)
 507 {
 508         int undefined = 0;
 509
 510         *val =  _get_value(expr, &undefined, FUZZYMIN);
 511         return !undefined;
 512 }
 513
 514 int get_fuzzy_max(struct expression *expr, long long *val)
 515 {
 516         int undefined = 0;
 517
 518         *val =  _get_value(expr, &undefined, FUZZYMAX);
 519         return !undefined;
 520 }
 521
 522 int get_absolute_min(struct expression *expr, long long *val)
 523 {
 524         struct symbol *type;
 525         long long min;
 526
 527         type = get_type(expr);
 528         if (!type) {
 529                 if (get_value(expr, val))
 530                         return 1;
 531                 return 0;
 532         }
 533         min = type_min(type);
 534         if (!get_implied_min(expr, val) || *val < min)
 535                 *val = min;
 536         return 1;
 537 }
 538
 539 int get_absolute_max(struct expression *expr, long long *val)
 540 {
 541         struct symbol *type;
 542         long long max;
 543
 544         type = get_type(expr);
 545         if (!type) {
 546                 if (get_value(expr, val))
 547                         return 1;
 548                 return 0;
 549         }
 550         max = type_max(type);
 551         if (!get_implied_max(expr, val) || *val > max)
 552                 *val = max;
 553         if (*val < type_min(type))
 554                 *val = max;
 555         return 1;
 556 }
 557
 558 int known_condition_true(struct expression *expr)
 559 {
 560         long long tmp;
 561
 562         if (!expr)
 563                 return 0;
 564
 565         if (get_value(expr, &tmp) && tmp)
 566                 return 1;
 567
 568         return 0;
 569 }
 570
 571 int known_condition_false(struct expression *expr)
 572 {
 573         if (!expr)
 574                 return 0;
 575
 576         if (is_zero(expr))
 577                 return 1;
 578
 579         if (expr->type == EXPR_CALL) {
 580                 if (sym_name_is("__builtin_constant_p", expr->fn))
 581                         return 1;
 582         }
 583         return 0;
 584 }
 585
 586 int implied_condition_true(struct expression *expr)
 587 {
 588         long long tmp;
 589
 590         if (!expr)
 591                 return 0;
 592
 593         if (known_condition_true(expr))
 594                 return 1;
 595         if (get_implied_value(expr, &tmp) && tmp)
 596                 return 1;
 597
 598         if (expr->type == EXPR_POSTOP)
 599                 return implied_condition_true(expr->unop);
 600
 601         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 602                 return implied_not_equal(expr->unop, 1);
 603         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 604                 return implied_not_equal(expr->unop, -1);
 605
 606         expr = strip_expr(expr);
 607         switch (expr->type) {
 608         case EXPR_COMPARE:
 609                 if (do_comparison(expr) == 1)
 610                         return 1;
 611                 break;
 612         case EXPR_PREOP:
 613                 if (expr->op == '!') {
 614                         if (implied_condition_false(expr->unop))
 615                                 return 1;
 616                         break;
 617                 }
 618                 break;
 619         default:
 620                 if (implied_not_equal(expr, 0) == 1)
 621                         return 1;
 622                 break;
 623         }
 624         return 0;
 625 }
 626
 627 int implied_condition_false(struct expression *expr)
 628 {
 629         struct expression *tmp;
 630         long long val;
 631
 632         if (!expr)
 633                 return 0;
 634
 635         if (known_condition_false(expr))
 636                 return 1;
 637
 638         switch (expr->type) {
 639         case EXPR_COMPARE:
 640                 if (do_comparison(expr) == 2)
 641                         return 1;
 642         case EXPR_PREOP:
 643                 if (expr->op == '!') {
 644                         if (implied_condition_true(expr->unop))
 645                                 return 1;
 646                         break;
 647                 }
 648                 tmp = strip_expr(expr);
 649                 if (tmp != expr)
 650                         return implied_condition_false(tmp);
 651                 break;
 652         default:
 653                 if (get_implied_value(expr, &val) && val == 0)
 654                         return 1;
 655                 break;
 656         }
 657         return 0;
 658 }