gcc/tree-object-size.c

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