1/* __builtin_object_size (ptr, object_size_type) computation 2 Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. 3 Contributed by Jakub Jelinek <jakub@redhat.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to 19the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20Boston, MA 02110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "tree.h" 27#include "diagnostic.h" 28#include "tree-flow.h" 29#include "tree-pass.h" 30#include "tree-ssa-propagate.h" 31 32struct object_size_info 33{ 34 int object_size_type; 35 bitmap visited, reexamine; 36 int pass; 37 bool changed; 38 unsigned int *depths; 39 unsigned int *stack, *tos; 40}; 41 42static unsigned HOST_WIDE_INT unknown[4] = { -1, -1, 0, 0 }; 43 44static tree compute_object_offset (tree, tree); 45static unsigned HOST_WIDE_INT addr_object_size (tree, int); 46static unsigned HOST_WIDE_INT alloc_object_size (tree, int); 47static tree pass_through_call (tree); 48static void collect_object_sizes_for (struct object_size_info *, tree); 49static void expr_object_size (struct object_size_info *, tree, tree); 50static bool merge_object_sizes (struct object_size_info *, tree, tree, 51 unsigned HOST_WIDE_INT); 52static bool plus_expr_object_size (struct object_size_info *, tree, tree); 53static unsigned int compute_object_sizes (void); 54static void init_offset_limit (void); 55static void check_for_plus_in_loops (struct object_size_info *, tree); 56static void check_for_plus_in_loops_1 (struct object_size_info *, tree, 57 unsigned int); 58 59/* object_sizes[0] is upper bound for number of bytes till the end of 60 the object. 61 object_sizes[1] is upper bound for number of bytes till the end of 62 the subobject (innermost array or field with address taken). 63 object_sizes[2] is lower bound for number of bytes till the end of 64 the object and object_sizes[3] lower bound for subobject. */ 65static unsigned HOST_WIDE_INT *object_sizes[4]; 66 67/* Bitmaps what object sizes have been computed already. */ 68static bitmap computed[4]; 69 70/* Maximum value of offset we consider to be addition. */ 71static unsigned HOST_WIDE_INT offset_limit; 72 73 74/* Initialize OFFSET_LIMIT variable. */ 75static void 76init_offset_limit (void) 77{ 78 if (host_integerp (TYPE_MAX_VALUE (sizetype), 1)) 79 offset_limit = tree_low_cst (TYPE_MAX_VALUE (sizetype), 1); 80 else 81 offset_limit = -1; 82 offset_limit /= 2; 83} 84 85 86/* Compute offset of EXPR within VAR. Return error_mark_node 87 if unknown. */ 88 89static tree 90compute_object_offset (tree expr, tree var) 91{ 92 enum tree_code code = PLUS_EXPR; 93 tree base, off, t; 94 95 if (expr == var) 96 return size_zero_node; 97 98 switch (TREE_CODE (expr)) 99 { 100 case COMPONENT_REF: 101 base = compute_object_offset (TREE_OPERAND (expr, 0), var); 102 if (base == error_mark_node) 103 return base; 104 105 t = TREE_OPERAND (expr, 1); 106 off = size_binop (PLUS_EXPR, DECL_FIELD_OFFSET (t), 107 size_int (tree_low_cst (DECL_FIELD_BIT_OFFSET (t), 1) 108 / BITS_PER_UNIT)); 109 break; 110 111 case REALPART_EXPR: 112 case NOP_EXPR: 113 case CONVERT_EXPR: 114 case VIEW_CONVERT_EXPR: 115 case NON_LVALUE_EXPR: 116 return compute_object_offset (TREE_OPERAND (expr, 0), var); 117 118 case IMAGPART_EXPR: 119 base = compute_object_offset (TREE_OPERAND (expr, 0), var); 120 if (base == error_mark_node) 121 return base; 122 123 off = TYPE_SIZE_UNIT (TREE_TYPE (expr)); 124 break; 125 126 case ARRAY_REF: 127 base = compute_object_offset (TREE_OPERAND (expr, 0), var); 128 if (base == error_mark_node) 129 return base; 130 131 t = TREE_OPERAND (expr, 1); 132 if (TREE_CODE (t) == INTEGER_CST && tree_int_cst_sgn (t) < 0) 133 { 134 code = MINUS_EXPR; 135 t = fold_build1 (NEGATE_EXPR, TREE_TYPE (t), t); 136 } 137 t = fold_convert (sizetype, t); 138 off = size_binop (MULT_EXPR, TYPE_SIZE_UNIT (TREE_TYPE (expr)), t); 139 break; 140 141 default: 142 return error_mark_node; 143 } 144 145 return size_binop (code, base, off); 146} 147 148 149/* Compute __builtin_object_size for PTR, which is a ADDR_EXPR. 150 OBJECT_SIZE_TYPE is the second argument from __builtin_object_size. 151 If unknown, return unknown[object_size_type]. */ 152 153static unsigned HOST_WIDE_INT 154addr_object_size (tree ptr, int object_size_type) 155{ 156 tree pt_var; 157 158 gcc_assert (TREE_CODE (ptr) == ADDR_EXPR); 159 160 pt_var = TREE_OPERAND (ptr, 0); 161 if (REFERENCE_CLASS_P (pt_var)) 162 pt_var = get_base_address (pt_var); 163 164 if (pt_var 165 && (SSA_VAR_P (pt_var) || TREE_CODE (pt_var) == STRING_CST) 166 && TYPE_SIZE_UNIT (TREE_TYPE (pt_var)) 167 && host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)), 1) 168 && (unsigned HOST_WIDE_INT) 169 tree_low_cst (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)), 1) < offset_limit) 170 { 171 tree bytes; 172 173 if (pt_var != TREE_OPERAND (ptr, 0)) 174 { 175 tree var; 176 177 if (object_size_type & 1) 178 { 179 var = TREE_OPERAND (ptr, 0); 180 181 while (var != pt_var 182 && TREE_CODE (var) != BIT_FIELD_REF 183 && TREE_CODE (var) != COMPONENT_REF 184 && TREE_CODE (var) != ARRAY_REF 185 && TREE_CODE (var) != ARRAY_RANGE_REF 186 && TREE_CODE (var) != REALPART_EXPR 187 && TREE_CODE (var) != IMAGPART_EXPR) 188 var = TREE_OPERAND (var, 0); 189 if (var != pt_var && TREE_CODE (var) == ARRAY_REF) 190 var = TREE_OPERAND (var, 0); 191 if (! TYPE_SIZE_UNIT (TREE_TYPE (var)) 192 || ! host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (var)), 1) 193 || tree_int_cst_lt (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)), 194 TYPE_SIZE_UNIT (TREE_TYPE (var)))) 195 var = pt_var; 196 } 197 else 198 var = pt_var; 199 200 bytes = compute_object_offset (TREE_OPERAND (ptr, 0), var); 201 if (bytes != error_mark_node) 202 { 203 if (TREE_CODE (bytes) == INTEGER_CST 204 && tree_int_cst_lt (TYPE_SIZE_UNIT (TREE_TYPE (var)), bytes)) 205 bytes = size_zero_node; 206 else 207 bytes = size_binop (MINUS_EXPR, 208 TYPE_SIZE_UNIT (TREE_TYPE (var)), bytes); 209 } 210 } 211 else 212 bytes = TYPE_SIZE_UNIT (TREE_TYPE (pt_var)); 213 214 if (host_integerp (bytes, 1)) 215 return tree_low_cst (bytes, 1); 216 } 217 218 return unknown[object_size_type]; 219} 220 221 222/* Compute __builtin_object_size for CALL, which is a CALL_EXPR. 223 Handles various allocation calls. OBJECT_SIZE_TYPE is the second 224 argument from __builtin_object_size. If unknown, return 225 unknown[object_size_type]. */ 226 227static unsigned HOST_WIDE_INT 228alloc_object_size (tree call, int object_size_type) 229{ 230 tree callee, arglist, a, bytes = NULL_TREE; 231 unsigned int arg_mask = 0; 232 233 gcc_assert (TREE_CODE (call) == CALL_EXPR); 234 235 callee = get_callee_fndecl (call); 236 arglist = TREE_OPERAND (call, 1); 237 if (callee 238 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) 239 switch (DECL_FUNCTION_CODE (callee)) 240 { 241 case BUILT_IN_MALLOC: 242 case BUILT_IN_ALLOCA: 243 arg_mask = 1; 244 break; 245 /* 246 case BUILT_IN_REALLOC: 247 arg_mask = 2; 248 break; 249 */ 250 case BUILT_IN_CALLOC: 251 arg_mask = 3; 252 break; 253 default: 254 break; 255 } 256 257 for (a = arglist; arg_mask && a; arg_mask >>= 1, a = TREE_CHAIN (a)) 258 if (arg_mask & 1) 259 { 260 tree arg = TREE_VALUE (a); 261 262 if (TREE_CODE (arg) != INTEGER_CST) 263 break; 264 265 if (! bytes) 266 bytes = fold_convert (sizetype, arg); 267 else 268 bytes = size_binop (MULT_EXPR, bytes, 269 fold_convert (sizetype, arg)); 270 } 271 272 if (! arg_mask && bytes && host_integerp (bytes, 1)) 273 return tree_low_cst (bytes, 1); 274 275 return unknown[object_size_type]; 276} 277 278 279/* If object size is propagated from one of function's arguments directly 280 to its return value, return that argument for CALL_EXPR CALL. 281 Otherwise return NULL. */ 282 283static tree 284pass_through_call (tree call) 285{ 286 tree callee = get_callee_fndecl (call); 287 tree arglist = TREE_OPERAND (call, 1); 288 289 if (callee 290 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) 291 switch (DECL_FUNCTION_CODE (callee)) 292 { 293 case BUILT_IN_MEMCPY: 294 case BUILT_IN_MEMMOVE: 295 case BUILT_IN_MEMSET: 296 case BUILT_IN_STRCPY: 297 case BUILT_IN_STRNCPY: 298 case BUILT_IN_STRCAT: 299 case BUILT_IN_STRNCAT: 300 case BUILT_IN_MEMCPY_CHK: 301 case BUILT_IN_MEMMOVE_CHK: 302 case BUILT_IN_MEMSET_CHK: 303 case BUILT_IN_STRCPY_CHK: 304 case BUILT_IN_STRNCPY_CHK: 305 case BUILT_IN_STRCAT_CHK: 306 case BUILT_IN_STRNCAT_CHK: 307 if (arglist) 308 return TREE_VALUE (arglist); 309 break; 310 default: 311 break; 312 } 313 314 return NULL_TREE; 315} 316 317 318/* Compute __builtin_object_size value for PTR. OBJECT_SIZE_TYPE is the 319 second argument from __builtin_object_size. */ 320 321unsigned HOST_WIDE_INT 322compute_builtin_object_size (tree ptr, int object_size_type) 323{ 324 gcc_assert (object_size_type >= 0 && object_size_type <= 3); 325 326 if (! offset_limit) 327 init_offset_limit (); 328 329 if (TREE_CODE (ptr) == ADDR_EXPR) 330 return addr_object_size (ptr, object_size_type); 331 else if (TREE_CODE (ptr) == CALL_EXPR) 332 { 333 tree arg = pass_through_call (ptr); 334 335 if (arg) 336 return compute_builtin_object_size (arg, object_size_type); 337 else 338 return alloc_object_size (ptr, object_size_type); 339 } 340 else if (TREE_CODE (ptr) == SSA_NAME 341 && POINTER_TYPE_P (TREE_TYPE (ptr)) 342 && object_sizes[object_size_type] != NULL) 343 { 344 if (!bitmap_bit_p (computed[object_size_type], SSA_NAME_VERSION (ptr))) 345 { 346 struct object_size_info osi; 347 bitmap_iterator bi; 348 unsigned int i; 349 350 if (dump_file) 351 { 352 fprintf (dump_file, "Computing %s %sobject size for ", 353 (object_size_type & 2) ? "minimum" : "maximum", 354 (object_size_type & 1) ? "sub" : ""); 355 print_generic_expr (dump_file, ptr, dump_flags); 356 fprintf (dump_file, ":\n"); 357 } 358 359 osi.visited = BITMAP_ALLOC (NULL); 360 osi.reexamine = BITMAP_ALLOC (NULL); 361 osi.object_size_type = object_size_type; 362 osi.depths = NULL; 363 osi.stack = NULL; 364 osi.tos = NULL; 365 366 /* First pass: walk UD chains, compute object sizes that 367 can be computed. osi.reexamine bitmap at the end will 368 contain what variables were found in dependency cycles 369 and therefore need to be reexamined. */ 370 osi.pass = 0; 371 osi.changed = false; 372 collect_object_sizes_for (&osi, ptr); 373 374 /* Second pass: keep recomputing object sizes of variables 375 that need reexamination, until no object sizes are 376 increased or all object sizes are computed. */ 377 if (! bitmap_empty_p (osi.reexamine)) 378 { 379 bitmap reexamine = BITMAP_ALLOC (NULL); 380 381 /* If looking for minimum instead of maximum object size, 382 detect cases where a pointer is increased in a loop. 383 Although even without this detection pass 2 would eventually 384 terminate, it could take a long time. If a pointer is 385 increasing this way, we need to assume 0 object size. 386 E.g. p = &buf[0]; while (cond) p = p + 4; */ 387 if (object_size_type & 2) 388 { 389 osi.depths = XCNEWVEC (unsigned int, num_ssa_names); 390 osi.stack = XNEWVEC (unsigned int, num_ssa_names); 391 osi.tos = osi.stack; 392 osi.pass = 1; 393 /* collect_object_sizes_for is changing 394 osi.reexamine bitmap, so iterate over a copy. */ 395 bitmap_copy (reexamine, osi.reexamine); 396 EXECUTE_IF_SET_IN_BITMAP (reexamine, 0, i, bi) 397 if (bitmap_bit_p (osi.reexamine, i)) 398 check_for_plus_in_loops (&osi, ssa_name (i)); 399 400 free (osi.depths); 401 osi.depths = NULL; 402 free (osi.stack); 403 osi.stack = NULL; 404 osi.tos = NULL; 405 } 406 407 do 408 { 409 osi.pass = 2; 410 osi.changed = false; 411 /* collect_object_sizes_for is changing 412 osi.reexamine bitmap, so iterate over a copy. */ 413 bitmap_copy (reexamine, osi.reexamine); 414 EXECUTE_IF_SET_IN_BITMAP (reexamine, 0, i, bi) 415 if (bitmap_bit_p (osi.reexamine, i)) 416 { 417 collect_object_sizes_for (&osi, ssa_name (i)); 418 if (dump_file && (dump_flags & TDF_DETAILS)) 419 { 420 fprintf (dump_file, "Reexamining "); 421 print_generic_expr (dump_file, ssa_name (i), 422 dump_flags); 423 fprintf (dump_file, "\n"); 424 } 425 } 426 } 427 while (osi.changed); 428 429 BITMAP_FREE (reexamine); 430 } 431 EXECUTE_IF_SET_IN_BITMAP (osi.reexamine, 0, i, bi) 432 bitmap_set_bit (computed[object_size_type], i); 433 434 /* Debugging dumps. */ 435 if (dump_file) 436 { 437 EXECUTE_IF_SET_IN_BITMAP (osi.visited, 0, i, bi) 438 if (object_sizes[object_size_type][i] 439 != unknown[object_size_type]) 440 { 441 print_generic_expr (dump_file, ssa_name (i), 442 dump_flags); 443 fprintf (dump_file, 444 ": %s %sobject size " 445 HOST_WIDE_INT_PRINT_UNSIGNED "\n", 446 (object_size_type & 2) ? "minimum" : "maximum", 447 (object_size_type & 1) ? "sub" : "", 448 object_sizes[object_size_type][i]); 449 } 450 } 451 452 BITMAP_FREE (osi.reexamine); 453 BITMAP_FREE (osi.visited); 454 } 455 456 return object_sizes[object_size_type][SSA_NAME_VERSION (ptr)]; 457 } 458 459 return unknown[object_size_type]; 460} 461 462 463/* Compute object_sizes for PTR, defined to VALUE, which is not 464 a SSA_NAME. */ 465 466static void 467expr_object_size (struct object_size_info *osi, tree ptr, tree value) 468{ 469 int object_size_type = osi->object_size_type; 470 unsigned int varno = SSA_NAME_VERSION (ptr); 471 unsigned HOST_WIDE_INT bytes; 472 473 gcc_assert (object_sizes[object_size_type][varno] 474 != unknown[object_size_type]); 475 gcc_assert (osi->pass == 0); 476 477 if (TREE_CODE (value) == WITH_SIZE_EXPR) 478 value = TREE_OPERAND (value, 0); 479 480 /* Pointer variables should have been handled by merge_object_sizes. */ 481 gcc_assert (TREE_CODE (value) != SSA_NAME 482 || !POINTER_TYPE_P (TREE_TYPE (value))); 483 484 if (TREE_CODE (value) == ADDR_EXPR) 485 bytes = addr_object_size (value, object_size_type); 486 else if (TREE_CODE (value) == CALL_EXPR) 487 bytes = alloc_object_size (value, object_size_type); 488 else 489 bytes = unknown[object_size_type]; 490 491 if ((object_size_type & 2) == 0) 492 { 493 if (object_sizes[object_size_type][varno] < bytes) 494 object_sizes[object_size_type][varno] = bytes; 495 } 496 else 497 { 498 if (object_sizes[object_size_type][varno] > bytes) 499 object_sizes[object_size_type][varno] = bytes; 500 } 501} 502 503 504/* Merge object sizes of ORIG + OFFSET into DEST. Return true if 505 the object size might need reexamination later. */ 506 507static bool 508merge_object_sizes (struct object_size_info *osi, tree dest, tree orig, 509 unsigned HOST_WIDE_INT offset) 510{ 511 int object_size_type = osi->object_size_type; 512 unsigned int varno = SSA_NAME_VERSION (dest); 513 unsigned HOST_WIDE_INT orig_bytes; 514 515 if (object_sizes[object_size_type][varno] == unknown[object_size_type]) 516 return false; 517 if (offset >= offset_limit) 518 { 519 object_sizes[object_size_type][varno] = unknown[object_size_type]; 520 return false; 521 } 522 523 if (osi->pass == 0) 524 collect_object_sizes_for (osi, orig); 525 526 orig_bytes = object_sizes[object_size_type][SSA_NAME_VERSION (orig)]; 527 if (orig_bytes != unknown[object_size_type]) 528 orig_bytes = (offset > orig_bytes) 529 ? (unsigned HOST_WIDE_INT) 0 : orig_bytes - offset; 530 531 if ((object_size_type & 2) == 0) 532 { 533 if (object_sizes[object_size_type][varno] < orig_bytes) 534 { 535 object_sizes[object_size_type][varno] = orig_bytes; 536 osi->changed = true; 537 } 538 } 539 else 540 { 541 if (object_sizes[object_size_type][varno] > orig_bytes) 542 { 543 object_sizes[object_size_type][varno] = orig_bytes; 544 osi->changed = true; 545 } 546 } 547 return bitmap_bit_p (osi->reexamine, SSA_NAME_VERSION (orig)); 548} 549 550 551/* Compute object_sizes for PTR, defined to VALUE, which is 552 a PLUS_EXPR. Return true if the object size might need reexamination 553 later. */ 554 555static bool 556plus_expr_object_size (struct object_size_info *osi, tree var, tree value) 557{ 558 tree op0 = TREE_OPERAND (value, 0); 559 tree op1 = TREE_OPERAND (value, 1); 560 bool ptr1_p = POINTER_TYPE_P (TREE_TYPE (op0)) 561 && TREE_CODE (op0) != INTEGER_CST; 562 bool ptr2_p = POINTER_TYPE_P (TREE_TYPE (op1)) 563 && TREE_CODE (op1) != INTEGER_CST; 564 int object_size_type = osi->object_size_type; 565 unsigned int varno = SSA_NAME_VERSION (var); 566 unsigned HOST_WIDE_INT bytes; 567 568 gcc_assert (TREE_CODE (value) == PLUS_EXPR); 569 570 if (object_sizes[object_size_type][varno] == unknown[object_size_type]) 571 return false; 572 573 /* Swap operands if needed. */ 574 if (ptr2_p && !ptr1_p) 575 { 576 tree tem = op0; 577 op0 = op1; 578 op1 = tem; 579 ptr1_p = true; 580 ptr2_p = false; 581 } 582 583 /* Handle PTR + OFFSET here. */ 584 if (ptr1_p 585 && !ptr2_p 586 && TREE_CODE (op1) == INTEGER_CST 587 && (TREE_CODE (op0) == SSA_NAME 588 || TREE_CODE (op0) == ADDR_EXPR)) 589 { 590 if (! host_integerp (op1, 1)) 591 bytes = unknown[object_size_type]; 592 else if (TREE_CODE (op0) == SSA_NAME) 593 return merge_object_sizes (osi, var, op0, tree_low_cst (op1, 1)); 594 else 595 { 596 unsigned HOST_WIDE_INT off = tree_low_cst (op1, 1); 597 598 bytes = compute_builtin_object_size (op0, object_size_type); 599 if (off > offset_limit) 600 bytes = unknown[object_size_type]; 601 else if (off > bytes) 602 bytes = 0; 603 else 604 bytes -= off; 605 } 606 } 607 else 608 bytes = unknown[object_size_type]; 609 610 if ((object_size_type & 2) == 0) 611 { 612 if (object_sizes[object_size_type][varno] < bytes) 613 object_sizes[object_size_type][varno] = bytes; 614 } 615 else 616 { 617 if (object_sizes[object_size_type][varno] > bytes) 618 object_sizes[object_size_type][varno] = bytes; 619 } 620 return false; 621} 622 623 624/* Compute object sizes for VAR. 625 For ADDR_EXPR an object size is the number of remaining bytes 626 to the end of the object (where what is considered an object depends on 627 OSI->object_size_type). 628 For allocation CALL_EXPR like malloc or calloc object size is the size 629 of the allocation. 630 For pointer PLUS_EXPR where second operand is a constant integer, 631 object size is object size of the first operand minus the constant. 632 If the constant is bigger than the number of remaining bytes until the 633 end of the object, object size is 0, but if it is instead a pointer 634 subtraction, object size is unknown[object_size_type]. 635 To differentiate addition from subtraction, ADDR_EXPR returns 636 unknown[object_size_type] for all objects bigger than half of the address 637 space, and constants less than half of the address space are considered 638 addition, while bigger constants subtraction. 639 For a memcpy like CALL_EXPR that always returns one of its arguments, the 640 object size is object size of that argument. 641 Otherwise, object size is the maximum of object sizes of variables 642 that it might be set to. */ 643 644static void 645collect_object_sizes_for (struct object_size_info *osi, tree var) 646{ 647 int object_size_type = osi->object_size_type; 648 unsigned int varno = SSA_NAME_VERSION (var); 649 tree stmt; 650 bool reexamine; 651 652 if (bitmap_bit_p (computed[object_size_type], varno)) 653 return; 654 655 if (osi->pass == 0) 656 { 657 if (! bitmap_bit_p (osi->visited, varno)) 658 { 659 bitmap_set_bit (osi->visited, varno); 660 object_sizes[object_size_type][varno] 661 = (object_size_type & 2) ? -1 : 0; 662 } 663 else 664 { 665 /* Found a dependency loop. Mark the variable for later 666 re-examination. */ 667 bitmap_set_bit (osi->reexamine, varno); 668 if (dump_file && (dump_flags & TDF_DETAILS)) 669 { 670 fprintf (dump_file, "Found a dependency loop at "); 671 print_generic_expr (dump_file, var, dump_flags); 672 fprintf (dump_file, "\n"); 673 } 674 return; 675 } 676 } 677 678 if (dump_file && (dump_flags & TDF_DETAILS)) 679 { 680 fprintf (dump_file, "Visiting use-def links for "); 681 print_generic_expr (dump_file, var, dump_flags); 682 fprintf (dump_file, "\n"); 683 } 684 685 stmt = SSA_NAME_DEF_STMT (var); 686 reexamine = false; 687 688 switch (TREE_CODE (stmt)) 689 { 690 case RETURN_EXPR: 691 gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR); 692 stmt = TREE_OPERAND (stmt, 0); 693 /* FALLTHRU */ 694 695 case MODIFY_EXPR: 696 { 697 tree rhs = TREE_OPERAND (stmt, 1), arg; 698 STRIP_NOPS (rhs); 699 700 if (TREE_CODE (rhs) == CALL_EXPR) 701 { 702 arg = pass_through_call (rhs); 703 if (arg) 704 rhs = arg; 705 } 706 707 if (TREE_CODE (rhs) == SSA_NAME 708 && POINTER_TYPE_P (TREE_TYPE (rhs))) 709 reexamine = merge_object_sizes (osi, var, rhs, 0); 710 711 else if (TREE_CODE (rhs) == PLUS_EXPR) 712 reexamine = plus_expr_object_size (osi, var, rhs); 713 714 else 715 expr_object_size (osi, var, rhs); 716 break; 717 } 718 719 case ASM_EXPR: 720 /* Pointers defined by __asm__ statements can point anywhere. */ 721 object_sizes[object_size_type][varno] = unknown[object_size_type]; 722 break; 723 724 case NOP_EXPR: 725 { 726 tree decl = SSA_NAME_VAR (var); 727 728 gcc_assert (IS_EMPTY_STMT (stmt)); 729 730 if (TREE_CODE (decl) != PARM_DECL && DECL_INITIAL (decl)) 731 expr_object_size (osi, var, DECL_INITIAL (decl)); 732 else 733 expr_object_size (osi, var, decl); 734 } 735 break; 736 737 case PHI_NODE: 738 { 739 int i; 740 741 for (i = 0; i < PHI_NUM_ARGS (stmt); i++) 742 { 743 tree rhs = PHI_ARG_DEF (stmt, i); 744 745 if (object_sizes[object_size_type][varno] 746 == unknown[object_size_type]) 747 break; 748 749 if (TREE_CODE (rhs) == SSA_NAME) 750 reexamine |= merge_object_sizes (osi, var, rhs, 0); 751 else if (osi->pass == 0) 752 expr_object_size (osi, var, rhs); 753 } 754 break; 755 } 756 default: 757 gcc_unreachable (); 758 } 759 760 if (! reexamine 761 || object_sizes[object_size_type][varno] == unknown[object_size_type]) 762 { 763 bitmap_set_bit (computed[object_size_type], varno); 764 bitmap_clear_bit (osi->reexamine, varno); 765 } 766 else 767 { 768 bitmap_set_bit (osi->reexamine, varno); 769 if (dump_file && (dump_flags & TDF_DETAILS)) 770 { 771 fprintf (dump_file, "Need to reexamine "); 772 print_generic_expr (dump_file, var, dump_flags); 773 fprintf (dump_file, "\n"); 774 } 775 } 776} 777 778 779/* Helper function for check_for_plus_in_loops. Called recursively 780 to detect loops. */ 781 782static void 783check_for_plus_in_loops_1 (struct object_size_info *osi, tree var, 784 unsigned int depth) 785{ 786 tree stmt = SSA_NAME_DEF_STMT (var); 787 unsigned int varno = SSA_NAME_VERSION (var); 788 789 if (osi->depths[varno]) 790 { 791 if (osi->depths[varno] != depth) 792 { 793 unsigned int *sp; 794 795 /* Found a loop involving pointer addition. */ 796 for (sp = osi->tos; sp > osi->stack; ) 797 { 798 --sp; 799 bitmap_clear_bit (osi->reexamine, *sp); 800 bitmap_set_bit (computed[osi->object_size_type], *sp); 801 object_sizes[osi->object_size_type][*sp] = 0; 802 if (*sp == varno) 803 break; 804 } 805 } 806 return; 807 } 808 else if (! bitmap_bit_p (osi->reexamine, varno)) 809 return; 810 811 osi->depths[varno] = depth; 812 *osi->tos++ = varno; 813 814 switch (TREE_CODE (stmt)) 815 { 816 case RETURN_EXPR: 817 gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR); 818 stmt = TREE_OPERAND (stmt, 0); 819 /* FALLTHRU */ 820 821 case MODIFY_EXPR: 822 { 823 tree rhs = TREE_OPERAND (stmt, 1), arg; 824 STRIP_NOPS (rhs); 825 826 if (TREE_CODE (rhs) == CALL_EXPR) 827 { 828 arg = pass_through_call (rhs); 829 if (arg) 830 rhs = arg; 831 } 832 833 if (TREE_CODE (rhs) == SSA_NAME) 834 check_for_plus_in_loops_1 (osi, rhs, depth); 835 else if (TREE_CODE (rhs) == PLUS_EXPR) 836 { 837 tree op0 = TREE_OPERAND (rhs, 0); 838 tree op1 = TREE_OPERAND (rhs, 1); 839 tree cst, basevar; 840 841 if (TREE_CODE (op0) == SSA_NAME) 842 { 843 basevar = op0; 844 cst = op1; 845 } 846 else 847 { 848 basevar = op1; 849 cst = op0; 850 gcc_assert (TREE_CODE (basevar) == SSA_NAME); 851 } 852 gcc_assert (TREE_CODE (cst) == INTEGER_CST); 853 854 check_for_plus_in_loops_1 (osi, basevar, 855 depth + !integer_zerop (cst)); 856 } 857 else 858 gcc_unreachable (); 859 break; 860 } 861 case PHI_NODE: 862 { 863 int i; 864 865 for (i = 0; i < PHI_NUM_ARGS (stmt); i++) 866 { 867 tree rhs = PHI_ARG_DEF (stmt, i); 868 869 if (TREE_CODE (rhs) == SSA_NAME) 870 check_for_plus_in_loops_1 (osi, rhs, depth); 871 } 872 break; 873 } 874 default: 875 gcc_unreachable (); 876 } 877 878 osi->depths[varno] = 0; 879 osi->tos--; 880} 881 882 883/* Check if some pointer we are computing object size of is being increased 884 within a loop. If yes, assume all the SSA variables participating in 885 that loop have minimum object sizes 0. */ 886 887static void 888check_for_plus_in_loops (struct object_size_info *osi, tree var) 889{ 890 tree stmt = SSA_NAME_DEF_STMT (var); 891 892 switch (TREE_CODE (stmt)) 893 { 894 case RETURN_EXPR: 895 gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR); 896 stmt = TREE_OPERAND (stmt, 0); 897 /* FALLTHRU */ 898 899 case MODIFY_EXPR: 900 { 901 tree rhs = TREE_OPERAND (stmt, 1), arg; 902 STRIP_NOPS (rhs); 903 904 if (TREE_CODE (rhs) == CALL_EXPR) 905 { 906 arg = pass_through_call (rhs); 907 if (arg) 908 rhs = arg; 909 } 910 911 if (TREE_CODE (rhs) == PLUS_EXPR) 912 { 913 tree op0 = TREE_OPERAND (rhs, 0); 914 tree op1 = TREE_OPERAND (rhs, 1); 915 tree cst, basevar; 916 917 if (TREE_CODE (op0) == SSA_NAME) 918 { 919 basevar = op0; 920 cst = op1; 921 } 922 else 923 { 924 basevar = op1; 925 cst = op0; 926 gcc_assert (TREE_CODE (basevar) == SSA_NAME); 927 } 928 gcc_assert (TREE_CODE (cst) == INTEGER_CST); 929 930 if (integer_zerop (cst)) 931 break; 932 933 osi->depths[SSA_NAME_VERSION (basevar)] = 1; 934 *osi->tos++ = SSA_NAME_VERSION (basevar); 935 check_for_plus_in_loops_1 (osi, var, 2); 936 osi->depths[SSA_NAME_VERSION (basevar)] = 0; 937 osi->tos--; 938 } 939 break; 940 } 941 default: 942 break; 943 } 944} 945 946 947/* Initialize data structures for the object size computation. */ 948 949void 950init_object_sizes (void) 951{ 952 int object_size_type; 953 954 if (object_sizes[0]) 955 return; 956 957 for (object_size_type = 0; object_size_type <= 3; object_size_type++) 958 { 959 object_sizes[object_size_type] = XNEWVEC (unsigned HOST_WIDE_INT, num_ssa_names); 960 computed[object_size_type] = BITMAP_ALLOC (NULL); 961 } 962 963 init_offset_limit (); 964} 965 966 967/* Destroy data structures after the object size computation. */ 968 969void 970fini_object_sizes (void) 971{ 972 int object_size_type; 973 974 for (object_size_type = 0; object_size_type <= 3; object_size_type++) 975 { 976 free (object_sizes[object_size_type]); 977 BITMAP_FREE (computed[object_size_type]); 978 object_sizes[object_size_type] = NULL; 979 } 980} 981 982 983/* Simple pass to optimize all __builtin_object_size () builtins. */ 984 985static unsigned int 986compute_object_sizes (void) 987{ 988 basic_block bb; 989 FOR_EACH_BB (bb) 990 { 991 block_stmt_iterator i; 992 for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) 993 { 994 tree *stmtp = bsi_stmt_ptr (i); 995 tree call = get_rhs (*stmtp); 996 tree callee, result; 997 998 if (!call || TREE_CODE (call) != CALL_EXPR) 999 continue; 1000 1001 callee = get_callee_fndecl (call); 1002 if (!callee 1003 || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL 1004 || DECL_FUNCTION_CODE (callee) != BUILT_IN_OBJECT_SIZE) 1005 continue; 1006 1007 init_object_sizes (); 1008 result = fold_builtin (callee, TREE_OPERAND (call, 1), false); 1009 if (!result) 1010 { 1011 tree arglist = TREE_OPERAND (call, 1); 1012 1013 if (arglist != NULL 1014 && POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arglist))) 1015 && TREE_CHAIN (arglist) != NULL 1016 && TREE_CHAIN (TREE_CHAIN (arglist)) == NULL) 1017 { 1018 tree ost = TREE_VALUE (TREE_CHAIN (arglist)); 1019 1020 if (host_integerp (ost, 1)) 1021 { 1022 unsigned HOST_WIDE_INT object_size_type 1023 = tree_low_cst (ost, 1); 1024 1025 if (object_size_type < 2) 1026 result = fold_convert (size_type_node, 1027 integer_minus_one_node); 1028 else if (object_size_type < 4) 1029 result = size_zero_node; 1030 } 1031 } 1032 1033 if (!result) 1034 continue; 1035 } 1036 1037 if (dump_file && (dump_flags & TDF_DETAILS)) 1038 { 1039 fprintf (dump_file, "Simplified\n "); 1040 print_generic_stmt (dump_file, *stmtp, dump_flags); 1041 } 1042 1043 if (!set_rhs (stmtp, result)) 1044 gcc_unreachable (); 1045 update_stmt (*stmtp); 1046 1047 if (dump_file && (dump_flags & TDF_DETAILS)) 1048 { 1049 fprintf (dump_file, "to\n "); 1050 print_generic_stmt (dump_file, *stmtp, dump_flags); 1051 fprintf (dump_file, "\n"); 1052 } 1053 } 1054 } 1055 1056 fini_object_sizes (); 1057 return 0; 1058} 1059 1060struct tree_opt_pass pass_object_sizes = 1061{ 1062 "objsz", /* name */ 1063 NULL, /* gate */ 1064 compute_object_sizes, /* execute */ 1065 NULL, /* sub */ 1066 NULL, /* next */ 1067 0, /* static_pass_number */ 1068 0, /* tv_id */ 1069 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1070 0, /* properties_provided */ 1071 0, /* properties_destroyed */ 1072 0, /* todo_flags_start */ 1073 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ 1074 0 /* letter */ 1075}; 1076