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