gcc/tree-object-size.c

   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)
 175         sz = compute_builtin_object_size (TREE_OPERAND (pt_var, 0),
 176                                           object_size_type);
 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 };