1169689Skan/* __builtin_object_size (ptr, object_size_type) computation 2169689Skan Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. 3169689Skan Contributed by Jakub Jelinek <jakub@redhat.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify 8169689Skanit under the terms of the GNU General Public License as published by 9169689Skanthe Free Software Foundation; either version 2, or (at your option) 10169689Skanany later version. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, 13169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169689SkanGNU General Public License for more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21169689Skan 22169689Skan#include "config.h" 23169689Skan#include "system.h" 24169689Skan#include "coretypes.h" 25169689Skan#include "tm.h" 26169689Skan#include "tree.h" 27169689Skan#include "diagnostic.h" 28169689Skan#include "tree-flow.h" 29169689Skan#include "tree-pass.h" 30169689Skan#include "tree-ssa-propagate.h" 31169689Skan 32169689Skanstruct object_size_info 33169689Skan{ 34169689Skan int object_size_type; 35169689Skan bitmap visited, reexamine; 36169689Skan int pass; 37169689Skan bool changed; 38169689Skan unsigned int *depths; 39169689Skan unsigned int *stack, *tos; 40169689Skan}; 41169689Skan 42169689Skanstatic unsigned HOST_WIDE_INT unknown[4] = { -1, -1, 0, 0 }; 43169689Skan 44169689Skanstatic tree compute_object_offset (tree, tree); 45169689Skanstatic unsigned HOST_WIDE_INT addr_object_size (tree, int); 46169689Skanstatic unsigned HOST_WIDE_INT alloc_object_size (tree, int); 47169689Skanstatic tree pass_through_call (tree); 48169689Skanstatic void collect_object_sizes_for (struct object_size_info *, tree); 49169689Skanstatic void expr_object_size (struct object_size_info *, tree, tree); 50169689Skanstatic bool merge_object_sizes (struct object_size_info *, tree, tree, 51169689Skan unsigned HOST_WIDE_INT); 52169689Skanstatic bool plus_expr_object_size (struct object_size_info *, tree, tree); 53169689Skanstatic unsigned int compute_object_sizes (void); 54169689Skanstatic void init_offset_limit (void); 55169689Skanstatic void check_for_plus_in_loops (struct object_size_info *, tree); 56169689Skanstatic void check_for_plus_in_loops_1 (struct object_size_info *, tree, 57169689Skan unsigned int); 58169689Skan 59169689Skan/* object_sizes[0] is upper bound for number of bytes till the end of 60169689Skan the object. 61169689Skan object_sizes[1] is upper bound for number of bytes till the end of 62169689Skan the subobject (innermost array or field with address taken). 63169689Skan object_sizes[2] is lower bound for number of bytes till the end of 64169689Skan the object and object_sizes[3] lower bound for subobject. */ 65169689Skanstatic unsigned HOST_WIDE_INT *object_sizes[4]; 66169689Skan 67169689Skan/* Bitmaps what object sizes have been computed already. */ 68169689Skanstatic bitmap computed[4]; 69169689Skan 70169689Skan/* Maximum value of offset we consider to be addition. */ 71169689Skanstatic unsigned HOST_WIDE_INT offset_limit; 72169689Skan 73169689Skan 74169689Skan/* Initialize OFFSET_LIMIT variable. */ 75169689Skanstatic void 76169689Skaninit_offset_limit (void) 77169689Skan{ 78169689Skan if (host_integerp (TYPE_MAX_VALUE (sizetype), 1)) 79169689Skan offset_limit = tree_low_cst (TYPE_MAX_VALUE (sizetype), 1); 80169689Skan else 81169689Skan offset_limit = -1; 82169689Skan offset_limit /= 2; 83169689Skan} 84169689Skan 85169689Skan 86169689Skan/* Compute offset of EXPR within VAR. Return error_mark_node 87169689Skan if unknown. */ 88169689Skan 89169689Skanstatic tree 90169689Skancompute_object_offset (tree expr, tree var) 91169689Skan{ 92169689Skan enum tree_code code = PLUS_EXPR; 93169689Skan tree base, off, t; 94169689Skan 95169689Skan if (expr == var) 96169689Skan return size_zero_node; 97169689Skan 98169689Skan switch (TREE_CODE (expr)) 99169689Skan { 100169689Skan case COMPONENT_REF: 101169689Skan base = compute_object_offset (TREE_OPERAND (expr, 0), var); 102169689Skan if (base == error_mark_node) 103169689Skan return base; 104169689Skan 105169689Skan t = TREE_OPERAND (expr, 1); 106169689Skan off = size_binop (PLUS_EXPR, DECL_FIELD_OFFSET (t), 107169689Skan size_int (tree_low_cst (DECL_FIELD_BIT_OFFSET (t), 1) 108169689Skan / BITS_PER_UNIT)); 109169689Skan break; 110169689Skan 111169689Skan case REALPART_EXPR: 112169689Skan case NOP_EXPR: 113169689Skan case CONVERT_EXPR: 114169689Skan case VIEW_CONVERT_EXPR: 115169689Skan case NON_LVALUE_EXPR: 116169689Skan return compute_object_offset (TREE_OPERAND (expr, 0), var); 117169689Skan 118169689Skan case IMAGPART_EXPR: 119169689Skan base = compute_object_offset (TREE_OPERAND (expr, 0), var); 120169689Skan if (base == error_mark_node) 121169689Skan return base; 122169689Skan 123169689Skan off = TYPE_SIZE_UNIT (TREE_TYPE (expr)); 124169689Skan break; 125169689Skan 126169689Skan case ARRAY_REF: 127169689Skan base = compute_object_offset (TREE_OPERAND (expr, 0), var); 128169689Skan if (base == error_mark_node) 129169689Skan return base; 130169689Skan 131169689Skan t = TREE_OPERAND (expr, 1); 132169689Skan if (TREE_CODE (t) == INTEGER_CST && tree_int_cst_sgn (t) < 0) 133169689Skan { 134169689Skan code = MINUS_EXPR; 135169689Skan t = fold_build1 (NEGATE_EXPR, TREE_TYPE (t), t); 136169689Skan } 137169689Skan t = fold_convert (sizetype, t); 138169689Skan off = size_binop (MULT_EXPR, TYPE_SIZE_UNIT (TREE_TYPE (expr)), t); 139169689Skan break; 140169689Skan 141169689Skan default: 142169689Skan return error_mark_node; 143169689Skan } 144169689Skan 145169689Skan return size_binop (code, base, off); 146169689Skan} 147169689Skan 148169689Skan 149169689Skan/* Compute __builtin_object_size for PTR, which is a ADDR_EXPR. 150169689Skan OBJECT_SIZE_TYPE is the second argument from __builtin_object_size. 151169689Skan If unknown, return unknown[object_size_type]. */ 152169689Skan 153169689Skanstatic unsigned HOST_WIDE_INT 154169689Skanaddr_object_size (tree ptr, int object_size_type) 155169689Skan{ 156169689Skan tree pt_var; 157169689Skan 158169689Skan gcc_assert (TREE_CODE (ptr) == ADDR_EXPR); 159169689Skan 160169689Skan pt_var = TREE_OPERAND (ptr, 0); 161169689Skan if (REFERENCE_CLASS_P (pt_var)) 162169689Skan pt_var = get_base_address (pt_var); 163169689Skan 164169689Skan if (pt_var 165169689Skan && (SSA_VAR_P (pt_var) || TREE_CODE (pt_var) == STRING_CST) 166169689Skan && TYPE_SIZE_UNIT (TREE_TYPE (pt_var)) 167169689Skan && host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)), 1) 168169689Skan && (unsigned HOST_WIDE_INT) 169169689Skan tree_low_cst (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)), 1) < offset_limit) 170169689Skan { 171169689Skan tree bytes; 172169689Skan 173169689Skan if (pt_var != TREE_OPERAND (ptr, 0)) 174169689Skan { 175169689Skan tree var; 176169689Skan 177169689Skan if (object_size_type & 1) 178169689Skan { 179169689Skan var = TREE_OPERAND (ptr, 0); 180169689Skan 181169689Skan while (var != pt_var 182169689Skan && TREE_CODE (var) != BIT_FIELD_REF 183169689Skan && TREE_CODE (var) != COMPONENT_REF 184169689Skan && TREE_CODE (var) != ARRAY_REF 185169689Skan && TREE_CODE (var) != ARRAY_RANGE_REF 186169689Skan && TREE_CODE (var) != REALPART_EXPR 187169689Skan && TREE_CODE (var) != IMAGPART_EXPR) 188169689Skan var = TREE_OPERAND (var, 0); 189169689Skan if (var != pt_var && TREE_CODE (var) == ARRAY_REF) 190169689Skan var = TREE_OPERAND (var, 0); 191169689Skan if (! TYPE_SIZE_UNIT (TREE_TYPE (var)) 192169689Skan || ! host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (var)), 1) 193169689Skan || tree_int_cst_lt (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)), 194169689Skan TYPE_SIZE_UNIT (TREE_TYPE (var)))) 195169689Skan var = pt_var; 196169689Skan } 197169689Skan else 198169689Skan var = pt_var; 199169689Skan 200169689Skan bytes = compute_object_offset (TREE_OPERAND (ptr, 0), var); 201169689Skan if (bytes != error_mark_node) 202169689Skan { 203169689Skan if (TREE_CODE (bytes) == INTEGER_CST 204169689Skan && tree_int_cst_lt (TYPE_SIZE_UNIT (TREE_TYPE (var)), bytes)) 205169689Skan bytes = size_zero_node; 206169689Skan else 207169689Skan bytes = size_binop (MINUS_EXPR, 208169689Skan TYPE_SIZE_UNIT (TREE_TYPE (var)), bytes); 209169689Skan } 210169689Skan } 211169689Skan else 212169689Skan bytes = TYPE_SIZE_UNIT (TREE_TYPE (pt_var)); 213169689Skan 214169689Skan if (host_integerp (bytes, 1)) 215169689Skan return tree_low_cst (bytes, 1); 216169689Skan } 217169689Skan 218169689Skan return unknown[object_size_type]; 219169689Skan} 220169689Skan 221169689Skan 222169689Skan/* Compute __builtin_object_size for CALL, which is a CALL_EXPR. 223169689Skan Handles various allocation calls. OBJECT_SIZE_TYPE is the second 224169689Skan argument from __builtin_object_size. If unknown, return 225169689Skan unknown[object_size_type]. */ 226169689Skan 227169689Skanstatic unsigned HOST_WIDE_INT 228169689Skanalloc_object_size (tree call, int object_size_type) 229169689Skan{ 230169689Skan tree callee, arglist, a, bytes = NULL_TREE; 231169689Skan unsigned int arg_mask = 0; 232169689Skan 233169689Skan gcc_assert (TREE_CODE (call) == CALL_EXPR); 234169689Skan 235169689Skan callee = get_callee_fndecl (call); 236169689Skan arglist = TREE_OPERAND (call, 1); 237169689Skan if (callee 238169689Skan && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) 239169689Skan switch (DECL_FUNCTION_CODE (callee)) 240169689Skan { 241169689Skan case BUILT_IN_MALLOC: 242169689Skan case BUILT_IN_ALLOCA: 243169689Skan arg_mask = 1; 244169689Skan break; 245169689Skan /* 246169689Skan case BUILT_IN_REALLOC: 247169689Skan arg_mask = 2; 248169689Skan break; 249169689Skan */ 250169689Skan case BUILT_IN_CALLOC: 251169689Skan arg_mask = 3; 252169689Skan break; 253169689Skan default: 254169689Skan break; 255169689Skan } 256169689Skan 257169689Skan for (a = arglist; arg_mask && a; arg_mask >>= 1, a = TREE_CHAIN (a)) 258169689Skan if (arg_mask & 1) 259169689Skan { 260169689Skan tree arg = TREE_VALUE (a); 261169689Skan 262169689Skan if (TREE_CODE (arg) != INTEGER_CST) 263169689Skan break; 264169689Skan 265169689Skan if (! bytes) 266169689Skan bytes = fold_convert (sizetype, arg); 267169689Skan else 268169689Skan bytes = size_binop (MULT_EXPR, bytes, 269169689Skan fold_convert (sizetype, arg)); 270169689Skan } 271169689Skan 272169689Skan if (! arg_mask && bytes && host_integerp (bytes, 1)) 273169689Skan return tree_low_cst (bytes, 1); 274169689Skan 275169689Skan return unknown[object_size_type]; 276169689Skan} 277169689Skan 278169689Skan 279169689Skan/* If object size is propagated from one of function's arguments directly 280169689Skan to its return value, return that argument for CALL_EXPR CALL. 281169689Skan Otherwise return NULL. */ 282169689Skan 283169689Skanstatic tree 284169689Skanpass_through_call (tree call) 285169689Skan{ 286169689Skan tree callee = get_callee_fndecl (call); 287169689Skan tree arglist = TREE_OPERAND (call, 1); 288169689Skan 289169689Skan if (callee 290169689Skan && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) 291169689Skan switch (DECL_FUNCTION_CODE (callee)) 292169689Skan { 293169689Skan case BUILT_IN_MEMCPY: 294169689Skan case BUILT_IN_MEMMOVE: 295169689Skan case BUILT_IN_MEMSET: 296169689Skan case BUILT_IN_STRCPY: 297169689Skan case BUILT_IN_STRNCPY: 298169689Skan case BUILT_IN_STRCAT: 299169689Skan case BUILT_IN_STRNCAT: 300169689Skan case BUILT_IN_MEMCPY_CHK: 301169689Skan case BUILT_IN_MEMMOVE_CHK: 302169689Skan case BUILT_IN_MEMSET_CHK: 303169689Skan case BUILT_IN_STRCPY_CHK: 304169689Skan case BUILT_IN_STRNCPY_CHK: 305169689Skan case BUILT_IN_STRCAT_CHK: 306169689Skan case BUILT_IN_STRNCAT_CHK: 307169689Skan if (arglist) 308169689Skan return TREE_VALUE (arglist); 309169689Skan break; 310169689Skan default: 311169689Skan break; 312169689Skan } 313169689Skan 314169689Skan return NULL_TREE; 315169689Skan} 316169689Skan 317169689Skan 318169689Skan/* Compute __builtin_object_size value for PTR. OBJECT_SIZE_TYPE is the 319169689Skan second argument from __builtin_object_size. */ 320169689Skan 321169689Skanunsigned HOST_WIDE_INT 322169689Skancompute_builtin_object_size (tree ptr, int object_size_type) 323169689Skan{ 324169689Skan gcc_assert (object_size_type >= 0 && object_size_type <= 3); 325169689Skan 326169689Skan if (! offset_limit) 327169689Skan init_offset_limit (); 328169689Skan 329169689Skan if (TREE_CODE (ptr) == ADDR_EXPR) 330169689Skan return addr_object_size (ptr, object_size_type); 331169689Skan else if (TREE_CODE (ptr) == CALL_EXPR) 332169689Skan { 333169689Skan tree arg = pass_through_call (ptr); 334169689Skan 335169689Skan if (arg) 336169689Skan return compute_builtin_object_size (arg, object_size_type); 337169689Skan else 338169689Skan return alloc_object_size (ptr, object_size_type); 339169689Skan } 340169689Skan else if (TREE_CODE (ptr) == SSA_NAME 341169689Skan && POINTER_TYPE_P (TREE_TYPE (ptr)) 342169689Skan && object_sizes[object_size_type] != NULL) 343169689Skan { 344169689Skan if (!bitmap_bit_p (computed[object_size_type], SSA_NAME_VERSION (ptr))) 345169689Skan { 346169689Skan struct object_size_info osi; 347169689Skan bitmap_iterator bi; 348169689Skan unsigned int i; 349169689Skan 350169689Skan if (dump_file) 351169689Skan { 352169689Skan fprintf (dump_file, "Computing %s %sobject size for ", 353169689Skan (object_size_type & 2) ? "minimum" : "maximum", 354169689Skan (object_size_type & 1) ? "sub" : ""); 355169689Skan print_generic_expr (dump_file, ptr, dump_flags); 356169689Skan fprintf (dump_file, ":\n"); 357169689Skan } 358169689Skan 359169689Skan osi.visited = BITMAP_ALLOC (NULL); 360169689Skan osi.reexamine = BITMAP_ALLOC (NULL); 361169689Skan osi.object_size_type = object_size_type; 362169689Skan osi.depths = NULL; 363169689Skan osi.stack = NULL; 364169689Skan osi.tos = NULL; 365169689Skan 366169689Skan /* First pass: walk UD chains, compute object sizes that 367169689Skan can be computed. osi.reexamine bitmap at the end will 368169689Skan contain what variables were found in dependency cycles 369169689Skan and therefore need to be reexamined. */ 370169689Skan osi.pass = 0; 371169689Skan osi.changed = false; 372169689Skan collect_object_sizes_for (&osi, ptr); 373169689Skan 374169689Skan /* Second pass: keep recomputing object sizes of variables 375169689Skan that need reexamination, until no object sizes are 376169689Skan increased or all object sizes are computed. */ 377169689Skan if (! bitmap_empty_p (osi.reexamine)) 378169689Skan { 379169689Skan bitmap reexamine = BITMAP_ALLOC (NULL); 380169689Skan 381169689Skan /* If looking for minimum instead of maximum object size, 382169689Skan detect cases where a pointer is increased in a loop. 383169689Skan Although even without this detection pass 2 would eventually 384169689Skan terminate, it could take a long time. If a pointer is 385169689Skan increasing this way, we need to assume 0 object size. 386169689Skan E.g. p = &buf[0]; while (cond) p = p + 4; */ 387169689Skan if (object_size_type & 2) 388169689Skan { 389169689Skan osi.depths = XCNEWVEC (unsigned int, num_ssa_names); 390169689Skan osi.stack = XNEWVEC (unsigned int, num_ssa_names); 391169689Skan osi.tos = osi.stack; 392169689Skan osi.pass = 1; 393169689Skan /* collect_object_sizes_for is changing 394169689Skan osi.reexamine bitmap, so iterate over a copy. */ 395169689Skan bitmap_copy (reexamine, osi.reexamine); 396169689Skan EXECUTE_IF_SET_IN_BITMAP (reexamine, 0, i, bi) 397169689Skan if (bitmap_bit_p (osi.reexamine, i)) 398169689Skan check_for_plus_in_loops (&osi, ssa_name (i)); 399169689Skan 400169689Skan free (osi.depths); 401169689Skan osi.depths = NULL; 402169689Skan free (osi.stack); 403169689Skan osi.stack = NULL; 404169689Skan osi.tos = NULL; 405169689Skan } 406169689Skan 407169689Skan do 408169689Skan { 409169689Skan osi.pass = 2; 410169689Skan osi.changed = false; 411169689Skan /* collect_object_sizes_for is changing 412169689Skan osi.reexamine bitmap, so iterate over a copy. */ 413169689Skan bitmap_copy (reexamine, osi.reexamine); 414169689Skan EXECUTE_IF_SET_IN_BITMAP (reexamine, 0, i, bi) 415169689Skan if (bitmap_bit_p (osi.reexamine, i)) 416169689Skan { 417169689Skan collect_object_sizes_for (&osi, ssa_name (i)); 418169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 419169689Skan { 420169689Skan fprintf (dump_file, "Reexamining "); 421169689Skan print_generic_expr (dump_file, ssa_name (i), 422169689Skan dump_flags); 423169689Skan fprintf (dump_file, "\n"); 424169689Skan } 425169689Skan } 426169689Skan } 427169689Skan while (osi.changed); 428169689Skan 429169689Skan BITMAP_FREE (reexamine); 430169689Skan } 431169689Skan EXECUTE_IF_SET_IN_BITMAP (osi.reexamine, 0, i, bi) 432169689Skan bitmap_set_bit (computed[object_size_type], i); 433169689Skan 434169689Skan /* Debugging dumps. */ 435169689Skan if (dump_file) 436169689Skan { 437169689Skan EXECUTE_IF_SET_IN_BITMAP (osi.visited, 0, i, bi) 438169689Skan if (object_sizes[object_size_type][i] 439169689Skan != unknown[object_size_type]) 440169689Skan { 441169689Skan print_generic_expr (dump_file, ssa_name (i), 442169689Skan dump_flags); 443169689Skan fprintf (dump_file, 444169689Skan ": %s %sobject size " 445169689Skan HOST_WIDE_INT_PRINT_UNSIGNED "\n", 446169689Skan (object_size_type & 2) ? "minimum" : "maximum", 447169689Skan (object_size_type & 1) ? "sub" : "", 448169689Skan object_sizes[object_size_type][i]); 449169689Skan } 450169689Skan } 451169689Skan 452169689Skan BITMAP_FREE (osi.reexamine); 453169689Skan BITMAP_FREE (osi.visited); 454169689Skan } 455169689Skan 456169689Skan return object_sizes[object_size_type][SSA_NAME_VERSION (ptr)]; 457169689Skan } 458169689Skan 459169689Skan return unknown[object_size_type]; 460169689Skan} 461169689Skan 462169689Skan 463169689Skan/* Compute object_sizes for PTR, defined to VALUE, which is not 464169689Skan a SSA_NAME. */ 465169689Skan 466169689Skanstatic void 467169689Skanexpr_object_size (struct object_size_info *osi, tree ptr, tree value) 468169689Skan{ 469169689Skan int object_size_type = osi->object_size_type; 470169689Skan unsigned int varno = SSA_NAME_VERSION (ptr); 471169689Skan unsigned HOST_WIDE_INT bytes; 472169689Skan 473169689Skan gcc_assert (object_sizes[object_size_type][varno] 474169689Skan != unknown[object_size_type]); 475169689Skan gcc_assert (osi->pass == 0); 476169689Skan 477169689Skan if (TREE_CODE (value) == WITH_SIZE_EXPR) 478169689Skan value = TREE_OPERAND (value, 0); 479169689Skan 480169689Skan /* Pointer variables should have been handled by merge_object_sizes. */ 481169689Skan gcc_assert (TREE_CODE (value) != SSA_NAME 482169689Skan || !POINTER_TYPE_P (TREE_TYPE (value))); 483169689Skan 484169689Skan if (TREE_CODE (value) == ADDR_EXPR) 485169689Skan bytes = addr_object_size (value, object_size_type); 486169689Skan else if (TREE_CODE (value) == CALL_EXPR) 487169689Skan bytes = alloc_object_size (value, object_size_type); 488169689Skan else 489169689Skan bytes = unknown[object_size_type]; 490169689Skan 491169689Skan if ((object_size_type & 2) == 0) 492169689Skan { 493169689Skan if (object_sizes[object_size_type][varno] < bytes) 494169689Skan object_sizes[object_size_type][varno] = bytes; 495169689Skan } 496169689Skan else 497169689Skan { 498169689Skan if (object_sizes[object_size_type][varno] > bytes) 499169689Skan object_sizes[object_size_type][varno] = bytes; 500169689Skan } 501169689Skan} 502169689Skan 503169689Skan 504169689Skan/* Merge object sizes of ORIG + OFFSET into DEST. Return true if 505169689Skan the object size might need reexamination later. */ 506169689Skan 507169689Skanstatic bool 508169689Skanmerge_object_sizes (struct object_size_info *osi, tree dest, tree orig, 509169689Skan unsigned HOST_WIDE_INT offset) 510169689Skan{ 511169689Skan int object_size_type = osi->object_size_type; 512169689Skan unsigned int varno = SSA_NAME_VERSION (dest); 513169689Skan unsigned HOST_WIDE_INT orig_bytes; 514169689Skan 515169689Skan if (object_sizes[object_size_type][varno] == unknown[object_size_type]) 516169689Skan return false; 517169689Skan if (offset >= offset_limit) 518169689Skan { 519169689Skan object_sizes[object_size_type][varno] = unknown[object_size_type]; 520169689Skan return false; 521169689Skan } 522169689Skan 523169689Skan if (osi->pass == 0) 524169689Skan collect_object_sizes_for (osi, orig); 525169689Skan 526169689Skan orig_bytes = object_sizes[object_size_type][SSA_NAME_VERSION (orig)]; 527169689Skan if (orig_bytes != unknown[object_size_type]) 528169689Skan orig_bytes = (offset > orig_bytes) 529169689Skan ? (unsigned HOST_WIDE_INT) 0 : orig_bytes - offset; 530169689Skan 531169689Skan if ((object_size_type & 2) == 0) 532169689Skan { 533169689Skan if (object_sizes[object_size_type][varno] < orig_bytes) 534169689Skan { 535169689Skan object_sizes[object_size_type][varno] = orig_bytes; 536169689Skan osi->changed = true; 537169689Skan } 538169689Skan } 539169689Skan else 540169689Skan { 541169689Skan if (object_sizes[object_size_type][varno] > orig_bytes) 542169689Skan { 543169689Skan object_sizes[object_size_type][varno] = orig_bytes; 544169689Skan osi->changed = true; 545169689Skan } 546169689Skan } 547169689Skan return bitmap_bit_p (osi->reexamine, SSA_NAME_VERSION (orig)); 548169689Skan} 549169689Skan 550169689Skan 551169689Skan/* Compute object_sizes for PTR, defined to VALUE, which is 552169689Skan a PLUS_EXPR. Return true if the object size might need reexamination 553169689Skan later. */ 554169689Skan 555169689Skanstatic bool 556169689Skanplus_expr_object_size (struct object_size_info *osi, tree var, tree value) 557169689Skan{ 558169689Skan tree op0 = TREE_OPERAND (value, 0); 559169689Skan tree op1 = TREE_OPERAND (value, 1); 560169689Skan bool ptr1_p = POINTER_TYPE_P (TREE_TYPE (op0)) 561169689Skan && TREE_CODE (op0) != INTEGER_CST; 562169689Skan bool ptr2_p = POINTER_TYPE_P (TREE_TYPE (op1)) 563169689Skan && TREE_CODE (op1) != INTEGER_CST; 564169689Skan int object_size_type = osi->object_size_type; 565169689Skan unsigned int varno = SSA_NAME_VERSION (var); 566169689Skan unsigned HOST_WIDE_INT bytes; 567169689Skan 568169689Skan gcc_assert (TREE_CODE (value) == PLUS_EXPR); 569169689Skan 570169689Skan if (object_sizes[object_size_type][varno] == unknown[object_size_type]) 571169689Skan return false; 572169689Skan 573169689Skan /* Swap operands if needed. */ 574169689Skan if (ptr2_p && !ptr1_p) 575169689Skan { 576169689Skan tree tem = op0; 577169689Skan op0 = op1; 578169689Skan op1 = tem; 579169689Skan ptr1_p = true; 580169689Skan ptr2_p = false; 581169689Skan } 582169689Skan 583169689Skan /* Handle PTR + OFFSET here. */ 584169689Skan if (ptr1_p 585169689Skan && !ptr2_p 586169689Skan && TREE_CODE (op1) == INTEGER_CST 587169689Skan && (TREE_CODE (op0) == SSA_NAME 588169689Skan || TREE_CODE (op0) == ADDR_EXPR)) 589169689Skan { 590169689Skan if (! host_integerp (op1, 1)) 591169689Skan bytes = unknown[object_size_type]; 592169689Skan else if (TREE_CODE (op0) == SSA_NAME) 593169689Skan return merge_object_sizes (osi, var, op0, tree_low_cst (op1, 1)); 594169689Skan else 595169689Skan { 596169689Skan unsigned HOST_WIDE_INT off = tree_low_cst (op1, 1); 597169689Skan 598169689Skan bytes = compute_builtin_object_size (op0, object_size_type); 599169689Skan if (off > offset_limit) 600169689Skan bytes = unknown[object_size_type]; 601169689Skan else if (off > bytes) 602169689Skan bytes = 0; 603169689Skan else 604169689Skan bytes -= off; 605169689Skan } 606169689Skan } 607169689Skan else 608169689Skan bytes = unknown[object_size_type]; 609169689Skan 610169689Skan if ((object_size_type & 2) == 0) 611169689Skan { 612169689Skan if (object_sizes[object_size_type][varno] < bytes) 613169689Skan object_sizes[object_size_type][varno] = bytes; 614169689Skan } 615169689Skan else 616169689Skan { 617169689Skan if (object_sizes[object_size_type][varno] > bytes) 618169689Skan object_sizes[object_size_type][varno] = bytes; 619169689Skan } 620169689Skan return false; 621169689Skan} 622169689Skan 623169689Skan 624169689Skan/* Compute object sizes for VAR. 625169689Skan For ADDR_EXPR an object size is the number of remaining bytes 626169689Skan to the end of the object (where what is considered an object depends on 627169689Skan OSI->object_size_type). 628169689Skan For allocation CALL_EXPR like malloc or calloc object size is the size 629169689Skan of the allocation. 630169689Skan For pointer PLUS_EXPR where second operand is a constant integer, 631169689Skan object size is object size of the first operand minus the constant. 632169689Skan If the constant is bigger than the number of remaining bytes until the 633169689Skan end of the object, object size is 0, but if it is instead a pointer 634169689Skan subtraction, object size is unknown[object_size_type]. 635169689Skan To differentiate addition from subtraction, ADDR_EXPR returns 636169689Skan unknown[object_size_type] for all objects bigger than half of the address 637169689Skan space, and constants less than half of the address space are considered 638169689Skan addition, while bigger constants subtraction. 639169689Skan For a memcpy like CALL_EXPR that always returns one of its arguments, the 640169689Skan object size is object size of that argument. 641169689Skan Otherwise, object size is the maximum of object sizes of variables 642169689Skan that it might be set to. */ 643169689Skan 644169689Skanstatic void 645169689Skancollect_object_sizes_for (struct object_size_info *osi, tree var) 646169689Skan{ 647169689Skan int object_size_type = osi->object_size_type; 648169689Skan unsigned int varno = SSA_NAME_VERSION (var); 649169689Skan tree stmt; 650169689Skan bool reexamine; 651169689Skan 652169689Skan if (bitmap_bit_p (computed[object_size_type], varno)) 653169689Skan return; 654169689Skan 655169689Skan if (osi->pass == 0) 656169689Skan { 657169689Skan if (! bitmap_bit_p (osi->visited, varno)) 658169689Skan { 659169689Skan bitmap_set_bit (osi->visited, varno); 660169689Skan object_sizes[object_size_type][varno] 661169689Skan = (object_size_type & 2) ? -1 : 0; 662169689Skan } 663169689Skan else 664169689Skan { 665169689Skan /* Found a dependency loop. Mark the variable for later 666169689Skan re-examination. */ 667169689Skan bitmap_set_bit (osi->reexamine, varno); 668169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 669169689Skan { 670169689Skan fprintf (dump_file, "Found a dependency loop at "); 671169689Skan print_generic_expr (dump_file, var, dump_flags); 672169689Skan fprintf (dump_file, "\n"); 673169689Skan } 674169689Skan return; 675169689Skan } 676169689Skan } 677169689Skan 678169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 679169689Skan { 680169689Skan fprintf (dump_file, "Visiting use-def links for "); 681169689Skan print_generic_expr (dump_file, var, dump_flags); 682169689Skan fprintf (dump_file, "\n"); 683169689Skan } 684169689Skan 685169689Skan stmt = SSA_NAME_DEF_STMT (var); 686169689Skan reexamine = false; 687169689Skan 688169689Skan switch (TREE_CODE (stmt)) 689169689Skan { 690169689Skan case RETURN_EXPR: 691169689Skan gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR); 692169689Skan stmt = TREE_OPERAND (stmt, 0); 693169689Skan /* FALLTHRU */ 694169689Skan 695169689Skan case MODIFY_EXPR: 696169689Skan { 697169689Skan tree rhs = TREE_OPERAND (stmt, 1), arg; 698169689Skan STRIP_NOPS (rhs); 699169689Skan 700169689Skan if (TREE_CODE (rhs) == CALL_EXPR) 701169689Skan { 702169689Skan arg = pass_through_call (rhs); 703169689Skan if (arg) 704169689Skan rhs = arg; 705169689Skan } 706169689Skan 707169689Skan if (TREE_CODE (rhs) == SSA_NAME 708169689Skan && POINTER_TYPE_P (TREE_TYPE (rhs))) 709169689Skan reexamine = merge_object_sizes (osi, var, rhs, 0); 710169689Skan 711169689Skan else if (TREE_CODE (rhs) == PLUS_EXPR) 712169689Skan reexamine = plus_expr_object_size (osi, var, rhs); 713169689Skan 714169689Skan else 715169689Skan expr_object_size (osi, var, rhs); 716169689Skan break; 717169689Skan } 718169689Skan 719169689Skan case ASM_EXPR: 720169689Skan /* Pointers defined by __asm__ statements can point anywhere. */ 721169689Skan object_sizes[object_size_type][varno] = unknown[object_size_type]; 722169689Skan break; 723169689Skan 724169689Skan case NOP_EXPR: 725169689Skan { 726169689Skan tree decl = SSA_NAME_VAR (var); 727169689Skan 728169689Skan gcc_assert (IS_EMPTY_STMT (stmt)); 729169689Skan 730169689Skan if (TREE_CODE (decl) != PARM_DECL && DECL_INITIAL (decl)) 731169689Skan expr_object_size (osi, var, DECL_INITIAL (decl)); 732169689Skan else 733169689Skan expr_object_size (osi, var, decl); 734169689Skan } 735169689Skan break; 736169689Skan 737169689Skan case PHI_NODE: 738169689Skan { 739169689Skan int i; 740169689Skan 741169689Skan for (i = 0; i < PHI_NUM_ARGS (stmt); i++) 742169689Skan { 743169689Skan tree rhs = PHI_ARG_DEF (stmt, i); 744169689Skan 745169689Skan if (object_sizes[object_size_type][varno] 746169689Skan == unknown[object_size_type]) 747169689Skan break; 748169689Skan 749169689Skan if (TREE_CODE (rhs) == SSA_NAME) 750169689Skan reexamine |= merge_object_sizes (osi, var, rhs, 0); 751169689Skan else if (osi->pass == 0) 752169689Skan expr_object_size (osi, var, rhs); 753169689Skan } 754169689Skan break; 755169689Skan } 756169689Skan default: 757169689Skan gcc_unreachable (); 758169689Skan } 759169689Skan 760169689Skan if (! reexamine 761169689Skan || object_sizes[object_size_type][varno] == unknown[object_size_type]) 762169689Skan { 763169689Skan bitmap_set_bit (computed[object_size_type], varno); 764169689Skan bitmap_clear_bit (osi->reexamine, varno); 765169689Skan } 766169689Skan else 767169689Skan { 768169689Skan bitmap_set_bit (osi->reexamine, varno); 769169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 770169689Skan { 771169689Skan fprintf (dump_file, "Need to reexamine "); 772169689Skan print_generic_expr (dump_file, var, dump_flags); 773169689Skan fprintf (dump_file, "\n"); 774169689Skan } 775169689Skan } 776169689Skan} 777169689Skan 778169689Skan 779169689Skan/* Helper function for check_for_plus_in_loops. Called recursively 780169689Skan to detect loops. */ 781169689Skan 782169689Skanstatic void 783169689Skancheck_for_plus_in_loops_1 (struct object_size_info *osi, tree var, 784169689Skan unsigned int depth) 785169689Skan{ 786169689Skan tree stmt = SSA_NAME_DEF_STMT (var); 787169689Skan unsigned int varno = SSA_NAME_VERSION (var); 788169689Skan 789169689Skan if (osi->depths[varno]) 790169689Skan { 791169689Skan if (osi->depths[varno] != depth) 792169689Skan { 793169689Skan unsigned int *sp; 794169689Skan 795169689Skan /* Found a loop involving pointer addition. */ 796169689Skan for (sp = osi->tos; sp > osi->stack; ) 797169689Skan { 798169689Skan --sp; 799169689Skan bitmap_clear_bit (osi->reexamine, *sp); 800169689Skan bitmap_set_bit (computed[osi->object_size_type], *sp); 801169689Skan object_sizes[osi->object_size_type][*sp] = 0; 802169689Skan if (*sp == varno) 803169689Skan break; 804169689Skan } 805169689Skan } 806169689Skan return; 807169689Skan } 808169689Skan else if (! bitmap_bit_p (osi->reexamine, varno)) 809169689Skan return; 810169689Skan 811169689Skan osi->depths[varno] = depth; 812169689Skan *osi->tos++ = varno; 813169689Skan 814169689Skan switch (TREE_CODE (stmt)) 815169689Skan { 816169689Skan case RETURN_EXPR: 817169689Skan gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR); 818169689Skan stmt = TREE_OPERAND (stmt, 0); 819169689Skan /* FALLTHRU */ 820169689Skan 821169689Skan case MODIFY_EXPR: 822169689Skan { 823169689Skan tree rhs = TREE_OPERAND (stmt, 1), arg; 824169689Skan STRIP_NOPS (rhs); 825169689Skan 826169689Skan if (TREE_CODE (rhs) == CALL_EXPR) 827169689Skan { 828169689Skan arg = pass_through_call (rhs); 829169689Skan if (arg) 830169689Skan rhs = arg; 831169689Skan } 832169689Skan 833169689Skan if (TREE_CODE (rhs) == SSA_NAME) 834169689Skan check_for_plus_in_loops_1 (osi, rhs, depth); 835169689Skan else if (TREE_CODE (rhs) == PLUS_EXPR) 836169689Skan { 837169689Skan tree op0 = TREE_OPERAND (rhs, 0); 838169689Skan tree op1 = TREE_OPERAND (rhs, 1); 839169689Skan tree cst, basevar; 840169689Skan 841169689Skan if (TREE_CODE (op0) == SSA_NAME) 842169689Skan { 843169689Skan basevar = op0; 844169689Skan cst = op1; 845169689Skan } 846169689Skan else 847169689Skan { 848169689Skan basevar = op1; 849169689Skan cst = op0; 850169689Skan gcc_assert (TREE_CODE (basevar) == SSA_NAME); 851169689Skan } 852169689Skan gcc_assert (TREE_CODE (cst) == INTEGER_CST); 853169689Skan 854169689Skan check_for_plus_in_loops_1 (osi, basevar, 855169689Skan depth + !integer_zerop (cst)); 856169689Skan } 857169689Skan else 858169689Skan gcc_unreachable (); 859169689Skan break; 860169689Skan } 861169689Skan case PHI_NODE: 862169689Skan { 863169689Skan int i; 864169689Skan 865169689Skan for (i = 0; i < PHI_NUM_ARGS (stmt); i++) 866169689Skan { 867169689Skan tree rhs = PHI_ARG_DEF (stmt, i); 868169689Skan 869169689Skan if (TREE_CODE (rhs) == SSA_NAME) 870169689Skan check_for_plus_in_loops_1 (osi, rhs, depth); 871169689Skan } 872169689Skan break; 873169689Skan } 874169689Skan default: 875169689Skan gcc_unreachable (); 876169689Skan } 877169689Skan 878169689Skan osi->depths[varno] = 0; 879169689Skan osi->tos--; 880169689Skan} 881169689Skan 882169689Skan 883169689Skan/* Check if some pointer we are computing object size of is being increased 884169689Skan within a loop. If yes, assume all the SSA variables participating in 885169689Skan that loop have minimum object sizes 0. */ 886169689Skan 887169689Skanstatic void 888169689Skancheck_for_plus_in_loops (struct object_size_info *osi, tree var) 889169689Skan{ 890169689Skan tree stmt = SSA_NAME_DEF_STMT (var); 891169689Skan 892169689Skan switch (TREE_CODE (stmt)) 893169689Skan { 894169689Skan case RETURN_EXPR: 895169689Skan gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR); 896169689Skan stmt = TREE_OPERAND (stmt, 0); 897169689Skan /* FALLTHRU */ 898169689Skan 899169689Skan case MODIFY_EXPR: 900169689Skan { 901169689Skan tree rhs = TREE_OPERAND (stmt, 1), arg; 902169689Skan STRIP_NOPS (rhs); 903169689Skan 904169689Skan if (TREE_CODE (rhs) == CALL_EXPR) 905169689Skan { 906169689Skan arg = pass_through_call (rhs); 907169689Skan if (arg) 908169689Skan rhs = arg; 909169689Skan } 910169689Skan 911169689Skan if (TREE_CODE (rhs) == PLUS_EXPR) 912169689Skan { 913169689Skan tree op0 = TREE_OPERAND (rhs, 0); 914169689Skan tree op1 = TREE_OPERAND (rhs, 1); 915169689Skan tree cst, basevar; 916169689Skan 917169689Skan if (TREE_CODE (op0) == SSA_NAME) 918169689Skan { 919169689Skan basevar = op0; 920169689Skan cst = op1; 921169689Skan } 922169689Skan else 923169689Skan { 924169689Skan basevar = op1; 925169689Skan cst = op0; 926169689Skan gcc_assert (TREE_CODE (basevar) == SSA_NAME); 927169689Skan } 928169689Skan gcc_assert (TREE_CODE (cst) == INTEGER_CST); 929169689Skan 930169689Skan if (integer_zerop (cst)) 931169689Skan break; 932169689Skan 933169689Skan osi->depths[SSA_NAME_VERSION (basevar)] = 1; 934169689Skan *osi->tos++ = SSA_NAME_VERSION (basevar); 935169689Skan check_for_plus_in_loops_1 (osi, var, 2); 936169689Skan osi->depths[SSA_NAME_VERSION (basevar)] = 0; 937169689Skan osi->tos--; 938169689Skan } 939169689Skan break; 940169689Skan } 941169689Skan default: 942169689Skan break; 943169689Skan } 944169689Skan} 945169689Skan 946169689Skan 947169689Skan/* Initialize data structures for the object size computation. */ 948169689Skan 949169689Skanvoid 950169689Skaninit_object_sizes (void) 951169689Skan{ 952169689Skan int object_size_type; 953169689Skan 954169689Skan if (object_sizes[0]) 955169689Skan return; 956169689Skan 957169689Skan for (object_size_type = 0; object_size_type <= 3; object_size_type++) 958169689Skan { 959169689Skan object_sizes[object_size_type] = XNEWVEC (unsigned HOST_WIDE_INT, num_ssa_names); 960169689Skan computed[object_size_type] = BITMAP_ALLOC (NULL); 961169689Skan } 962169689Skan 963169689Skan init_offset_limit (); 964169689Skan} 965169689Skan 966169689Skan 967169689Skan/* Destroy data structures after the object size computation. */ 968169689Skan 969169689Skanvoid 970169689Skanfini_object_sizes (void) 971169689Skan{ 972169689Skan int object_size_type; 973169689Skan 974169689Skan for (object_size_type = 0; object_size_type <= 3; object_size_type++) 975169689Skan { 976169689Skan free (object_sizes[object_size_type]); 977169689Skan BITMAP_FREE (computed[object_size_type]); 978169689Skan object_sizes[object_size_type] = NULL; 979169689Skan } 980169689Skan} 981169689Skan 982169689Skan 983169689Skan/* Simple pass to optimize all __builtin_object_size () builtins. */ 984169689Skan 985169689Skanstatic unsigned int 986169689Skancompute_object_sizes (void) 987169689Skan{ 988169689Skan basic_block bb; 989169689Skan FOR_EACH_BB (bb) 990169689Skan { 991169689Skan block_stmt_iterator i; 992169689Skan for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) 993169689Skan { 994169689Skan tree *stmtp = bsi_stmt_ptr (i); 995169689Skan tree call = get_rhs (*stmtp); 996169689Skan tree callee, result; 997169689Skan 998169689Skan if (!call || TREE_CODE (call) != CALL_EXPR) 999169689Skan continue; 1000169689Skan 1001169689Skan callee = get_callee_fndecl (call); 1002169689Skan if (!callee 1003169689Skan || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL 1004169689Skan || DECL_FUNCTION_CODE (callee) != BUILT_IN_OBJECT_SIZE) 1005169689Skan continue; 1006169689Skan 1007169689Skan init_object_sizes (); 1008169689Skan result = fold_builtin (callee, TREE_OPERAND (call, 1), false); 1009169689Skan if (!result) 1010169689Skan { 1011169689Skan tree arglist = TREE_OPERAND (call, 1); 1012169689Skan 1013169689Skan if (arglist != NULL 1014169689Skan && POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arglist))) 1015169689Skan && TREE_CHAIN (arglist) != NULL 1016169689Skan && TREE_CHAIN (TREE_CHAIN (arglist)) == NULL) 1017169689Skan { 1018169689Skan tree ost = TREE_VALUE (TREE_CHAIN (arglist)); 1019169689Skan 1020169689Skan if (host_integerp (ost, 1)) 1021169689Skan { 1022169689Skan unsigned HOST_WIDE_INT object_size_type 1023169689Skan = tree_low_cst (ost, 1); 1024169689Skan 1025169689Skan if (object_size_type < 2) 1026169689Skan result = fold_convert (size_type_node, 1027169689Skan integer_minus_one_node); 1028169689Skan else if (object_size_type < 4) 1029169689Skan result = size_zero_node; 1030169689Skan } 1031169689Skan } 1032169689Skan 1033169689Skan if (!result) 1034169689Skan continue; 1035169689Skan } 1036169689Skan 1037169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1038169689Skan { 1039169689Skan fprintf (dump_file, "Simplified\n "); 1040169689Skan print_generic_stmt (dump_file, *stmtp, dump_flags); 1041169689Skan } 1042169689Skan 1043169689Skan if (!set_rhs (stmtp, result)) 1044169689Skan gcc_unreachable (); 1045169689Skan update_stmt (*stmtp); 1046169689Skan 1047169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1048169689Skan { 1049169689Skan fprintf (dump_file, "to\n "); 1050169689Skan print_generic_stmt (dump_file, *stmtp, dump_flags); 1051169689Skan fprintf (dump_file, "\n"); 1052169689Skan } 1053169689Skan } 1054169689Skan } 1055169689Skan 1056169689Skan fini_object_sizes (); 1057169689Skan return 0; 1058169689Skan} 1059169689Skan 1060169689Skanstruct tree_opt_pass pass_object_sizes = 1061169689Skan{ 1062169689Skan "objsz", /* name */ 1063169689Skan NULL, /* gate */ 1064169689Skan compute_object_sizes, /* execute */ 1065169689Skan NULL, /* sub */ 1066169689Skan NULL, /* next */ 1067169689Skan 0, /* static_pass_number */ 1068169689Skan 0, /* tv_id */ 1069169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1070169689Skan 0, /* properties_provided */ 1071169689Skan 0, /* properties_destroyed */ 1072169689Skan 0, /* todo_flags_start */ 1073169689Skan TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ 1074169689Skan 0 /* letter */ 1075169689Skan}; 1076