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