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