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