gcc/tree-object-size.c

   1 /* __builtin_object_size (ptr, object_size_type) computation
   2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
   3    Contributed by Jakub Jelinek <jakub@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "diagnostic.h"
  28 #include "tree-flow.h"
  29 #include "tree-pass.h"
  30 #include "tree-ssa-propagate.h"
  31
  32 struct object_size_info
  33 {
  34   int object_size_type;
  35   bitmap visited, reexamine;
  36   int pass;
  37   bool changed;
  38   unsigned int *depths;
  39   unsigned int *stack, *tos;
  40 };
  41
  42 static unsigned HOST_WIDE_INT unknown[4] = { -1, -1, 0, 0 };
  43
  44 static tree compute_object_offset (tree, tree);
  45 static unsigned HOST_WIDE_INT addr_object_size (tree, int);
  46 static unsigned HOST_WIDE_INT alloc_object_size (tree, int);
  47 static tree pass_through_call (tree);
  48 static void collect_object_sizes_for (struct object_size_info *, tree);
  49 static void expr_object_size (struct object_size_info *, tree, tree);
  50 static bool merge_object_sizes (struct object_size_info *, tree, tree,
  51                                 unsigned HOST_WIDE_INT);
  52 static bool plus_expr_object_size (struct object_size_info *, tree, tree);
  53 static void compute_object_sizes (void);
  54 static void init_offset_limit (void);
  55 static void check_for_plus_in_loops (struct object_size_info *, tree);
  56 static void check_for_plus_in_loops_1 (struct object_size_info *, tree,
  57                                        unsigned int);
  58
  59 /* object_sizes[0] is upper bound for number of bytes till the end of
  60    the object.
  61    object_sizes[1] is upper bound for number of bytes till the end of
  62    the subobject (innermost array or field with address taken).
  63    object_sizes[2] is lower bound for number of bytes till the end of
  64    the object and object_sizes[3] lower bound for subobject.  */
  65 static unsigned HOST_WIDE_INT *object_sizes[4];
  66
  67 /* Bitmaps what object sizes have been computed already.  */
  68 static bitmap computed[4];
  69
  70 /* Maximum value of offset we consider to be addition.  */
  71 static unsigned HOST_WIDE_INT offset_limit;
  72
  73
  74 /* Initialize OFFSET_LIMIT variable.  */
  75 static void
  76 init_offset_limit (void)
  77 {
  78   if (host_integerp (TYPE_MAX_VALUE (sizetype), 1))
  79     offset_limit = tree_low_cst (TYPE_MAX_VALUE (sizetype), 1);
  80   else
  81     offset_limit = -1;
  82   offset_limit /= 2;
  83 }
  84
  85
  86 /* Compute offset of EXPR within VAR.  Return error_mark_node
  87    if unknown.  */
  88
  89 static tree
  90 compute_object_offset (tree expr, tree var)
  91 {
  92   enum tree_code code = PLUS_EXPR;
  93   tree base, off, t;
  94
  95   if (expr == var)
  96     return size_zero_node;
  97
  98   switch (TREE_CODE (expr))
  99     {
 100     case COMPONENT_REF:
 101       base = compute_object_offset (TREE_OPERAND (expr, 0), var);
 102       if (base == error_mark_node)
 103         return base;
 104
 105       t = TREE_OPERAND (expr, 1);
 106       off = size_binop (PLUS_EXPR, DECL_FIELD_OFFSET (t),
 107                         size_int (tree_low_cst (DECL_FIELD_BIT_OFFSET (t), 1)
 108                                   / BITS_PER_UNIT));
 109       break;
 110
 111     case REALPART_EXPR:
 112     case NOP_EXPR:
 113     case CONVERT_EXPR:
 114     case VIEW_CONVERT_EXPR:
 115     case NON_LVALUE_EXPR:
 116       return compute_object_offset (TREE_OPERAND (expr, 0), var);
 117
 118     case IMAGPART_EXPR:
 119       base = compute_object_offset (TREE_OPERAND (expr, 0), var);
 120       if (base == error_mark_node)
 121         return base;
 122
 123       off = TYPE_SIZE_UNIT (TREE_TYPE (expr));
 124       break;
 125
 126     case ARRAY_REF:
 127       base = compute_object_offset (TREE_OPERAND (expr, 0), var);
 128       if (base == error_mark_node)
 129         return base;
 130
 131       t = TREE_OPERAND (expr, 1);
 132       if (TREE_CODE (t) == INTEGER_CST && tree_int_cst_sgn (t) < 0)
 133         {
 134           code = MINUS_EXPR;
 135           t = fold_build1 (NEGATE_EXPR, TREE_TYPE (t), t);
 136         }
 137       t = convert (sizetype, t);
 138       off = size_binop (MULT_EXPR, TYPE_SIZE_UNIT (TREE_TYPE (expr)), t);
 139       break;
 140
 141     default:
 142       return error_mark_node;
 143     }
 144
 145   return size_binop (code, base, off);
 146 }
 147
 148
 149 /* Compute __builtin_object_size for PTR, which is a ADDR_EXPR.
 150    OBJECT_SIZE_TYPE is the second argument from __builtin_object_size.
 151    If unknown, return unknown[object_size_type].  */
 152
 153 static unsigned HOST_WIDE_INT
 154 addr_object_size (tree ptr, int object_size_type)
 155 {
 156   tree pt_var;
 157
 158   gcc_assert (TREE_CODE (ptr) == ADDR_EXPR);
 159
 160   pt_var = TREE_OPERAND (ptr, 0);
 161   if (REFERENCE_CLASS_P (pt_var))
 162     pt_var = get_base_address (pt_var);
 163
 164   if (pt_var
 165       && (SSA_VAR_P (pt_var) || TREE_CODE (pt_var) == STRING_CST)
 166       && TYPE_SIZE_UNIT (TREE_TYPE (pt_var))
 167       && host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)), 1)
 168       && (unsigned HOST_WIDE_INT)
 169          tree_low_cst (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)), 1) < offset_limit)
 170     {
 171       tree bytes;
 172
 173       if (pt_var != TREE_OPERAND (ptr, 0))
 174         {
 175           tree var;
 176
 177           if (object_size_type & 1)
 178             {
 179               var = TREE_OPERAND (ptr, 0);
 180
 181               while (var != pt_var
 182                       && TREE_CODE (var) != BIT_FIELD_REF
 183                       && TREE_CODE (var) != COMPONENT_REF
 184                       && TREE_CODE (var) != ARRAY_REF
 185                       && TREE_CODE (var) != ARRAY_RANGE_REF
 186                       && TREE_CODE (var) != REALPART_EXPR
 187                       && TREE_CODE (var) != IMAGPART_EXPR)
 188                 var = TREE_OPERAND (var, 0);
 189               if (var != pt_var && TREE_CODE (var) == ARRAY_REF)
 190                 var = TREE_OPERAND (var, 0);
 191               if (! TYPE_SIZE_UNIT (TREE_TYPE (var))
 192                   || ! host_integerp (TYPE_SIZE_UNIT (TREE_TYPE (var)), 1)
 193                   || tree_int_cst_lt (TYPE_SIZE_UNIT (TREE_TYPE (pt_var)),
 194                                       TYPE_SIZE_UNIT (TREE_TYPE (var))))
 195                 var = pt_var;
 196             }
 197           else
 198             var = pt_var;
 199
 200           bytes = compute_object_offset (TREE_OPERAND (ptr, 0), var);
 201           if (bytes != error_mark_node)
 202             {
 203               if (TREE_CODE (bytes) == INTEGER_CST
 204                   && tree_int_cst_lt (TYPE_SIZE_UNIT (TREE_TYPE (var)), bytes))
 205                 bytes = size_zero_node;
 206               else
 207                 bytes = size_binop (MINUS_EXPR,
 208                                     TYPE_SIZE_UNIT (TREE_TYPE (var)), bytes);
 209             }
 210         }
 211       else
 212         bytes = TYPE_SIZE_UNIT (TREE_TYPE (pt_var));
 213
 214       if (host_integerp (bytes, 1))
 215         return tree_low_cst (bytes, 1);
 216     }
 217
 218   return unknown[object_size_type];
 219 }
 220
 221
 222 /* Compute __builtin_object_size for CALL, which is a CALL_EXPR.
 223    Handles various allocation calls.  OBJECT_SIZE_TYPE is the second
 224    argument from __builtin_object_size.  If unknown, return
 225    unknown[object_size_type].  */
 226
 227 static unsigned HOST_WIDE_INT
 228 alloc_object_size (tree call, int object_size_type)
 229 {
 230   tree callee, arglist, a, bytes = NULL_TREE;
 231   unsigned int arg_mask = 0;
 232
 233   gcc_assert (TREE_CODE (call) == CALL_EXPR);
 234
 235   callee = get_callee_fndecl (call);
 236   arglist = TREE_OPERAND (call, 1);
 237   if (callee
 238       && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
 239     switch (DECL_FUNCTION_CODE (callee))
 240       {
 241       case BUILT_IN_MALLOC:
 242       case BUILT_IN_ALLOCA:
 243         arg_mask = 1;
 244         break;
 245       /*
 246       case BUILT_IN_REALLOC:
 247         arg_mask = 2;
 248         break;
 249         */
 250       case BUILT_IN_CALLOC:
 251         arg_mask = 3;
 252         break;
 253       default:
 254         break;
 255       }
 256
 257   for (a = arglist; arg_mask && a; arg_mask >>= 1, a = TREE_CHAIN (a))
 258     if (arg_mask & 1)
 259       {
 260         tree arg = TREE_VALUE (a);
 261
 262         if (TREE_CODE (arg) != INTEGER_CST)
 263           break;
 264
 265         if (! bytes)
 266           bytes = fold_convert (sizetype, arg);
 267         else
 268           bytes = size_binop (MULT_EXPR, bytes,
 269                               fold_convert (sizetype, arg));
 270       }
 271
 272   if (! arg_mask && bytes && host_integerp (bytes, 1))
 273     return tree_low_cst (bytes, 1);
 274
 275   return unknown[object_size_type];
 276 }
 277
 278
 279 /* If object size is propagated from one of function's arguments directly
 280    to its return value, return that argument for CALL_EXPR CALL.
 281    Otherwise return NULL.  */
 282
 283 static tree
 284 pass_through_call (tree call)
 285 {
 286   tree callee = get_callee_fndecl (call);
 287   tree arglist = TREE_OPERAND (call, 1);
 288
 289   if (callee
 290       && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
 291     switch (DECL_FUNCTION_CODE (callee))
 292       {
 293       case BUILT_IN_MEMCPY:
 294       case BUILT_IN_MEMMOVE:
 295       case BUILT_IN_MEMSET:
 296       case BUILT_IN_STRCPY:
 297       case BUILT_IN_STRNCPY:
 298       case BUILT_IN_STRCAT:
 299       case BUILT_IN_STRNCAT:
 300       case BUILT_IN_MEMCPY_CHK:
 301       case BUILT_IN_MEMMOVE_CHK:
 302       case BUILT_IN_MEMSET_CHK:
 303       case BUILT_IN_STRCPY_CHK:
 304       case BUILT_IN_STRNCPY_CHK:
 305       case BUILT_IN_STRCAT_CHK:
 306       case BUILT_IN_STRNCAT_CHK:
 307         if (arglist)
 308           return TREE_VALUE (arglist);
 309         break;
 310       default:
 311         break;
 312       }
 313
 314   return NULL_TREE;
 315 }
 316
 317
 318 /* Compute __builtin_object_size value for PTR.  OBJECT_SIZE_TYPE is the
 319    second argument from __builtin_object_size.  */
 320
 321 unsigned HOST_WIDE_INT
 322 compute_builtin_object_size (tree ptr, int object_size_type)
 323 {
 324   gcc_assert (object_size_type >= 0 && object_size_type <= 3);
 325
 326   if (! offset_limit)
 327     init_offset_limit ();
 328
 329   if (TREE_CODE (ptr) == ADDR_EXPR)
 330     return addr_object_size (ptr, object_size_type);
 331   else if (TREE_CODE (ptr) == CALL_EXPR)
 332     {
 333       tree arg = pass_through_call (ptr);
 334
 335       if (arg)
 336         return compute_builtin_object_size (arg, object_size_type);
 337       else
 338         return alloc_object_size (ptr, object_size_type);
 339     }
 340   else if (TREE_CODE (ptr) == SSA_NAME
 341            && POINTER_TYPE_P (TREE_TYPE (ptr))
 342            && object_sizes[object_size_type] != NULL)
 343     {
 344       if (!bitmap_bit_p (computed[object_size_type], SSA_NAME_VERSION (ptr)))
 345         {
 346           struct object_size_info osi;
 347           bitmap_iterator bi;
 348           unsigned int i;
 349
 350           if (dump_file)
 351             {
 352               fprintf (dump_file, "Computing %s %sobject size for ",
 353                        (object_size_type & 2) ? "minimum" : "maximum",
 354                        (object_size_type & 1) ? "sub" : "");
 355               print_generic_expr (dump_file, ptr, dump_flags);
 356               fprintf (dump_file, ":\n");
 357             }
 358
 359           osi.visited = BITMAP_ALLOC (NULL);
 360           osi.reexamine = BITMAP_ALLOC (NULL);
 361           osi.object_size_type = object_size_type;
 362           osi.depths = NULL;
 363           osi.stack = NULL;
 364           osi.tos = NULL;
 365
 366           /* First pass: walk UD chains, compute object sizes that
 367              can be computed.  osi.reexamine bitmap at the end will
 368              contain what variables were found in dependency cycles
 369              and therefore need to be reexamined.  */
 370           osi.pass = 0;
 371           osi.changed = false;
 372           collect_object_sizes_for (&osi, ptr);
 373
 374           /* Second pass: keep recomputing object sizes of variables
 375              that need reexamination, until no object sizes are
 376              increased or all object sizes are computed.  */
 377           if (! bitmap_empty_p (osi.reexamine))
 378             {
 379               bitmap reexamine = BITMAP_ALLOC (NULL);
 380
 381               /* If looking for minimum instead of maximum object size,
 382                  detect cases where a pointer is increased in a loop.
 383                  Although even without this detection pass 2 would eventually
 384                  terminate, it could take a long time.  If a pointer is
 385                  increasing this way, we need to assume 0 object size.
 386                  E.g. p = &buf[0]; while (cond) p = p + 4;  */
 387               if (object_size_type & 2)
 388                 {
 389                   osi.depths = xcalloc (num_ssa_names, sizeof (unsigned int));
 390                   osi.stack = xmalloc (num_ssa_names * sizeof (unsigned int));
 391                   osi.tos = osi.stack;
 392                   osi.pass = 1;
 393                   /* collect_object_sizes_for is changing
 394                      osi.reexamine bitmap, so iterate over a copy.  */
 395                   bitmap_copy (reexamine, osi.reexamine);
 396                   EXECUTE_IF_SET_IN_BITMAP (reexamine, 0, i, bi)
 397                     if (bitmap_bit_p (osi.reexamine, i))
 398                       check_for_plus_in_loops (&osi, ssa_name (i));
 399
 400                   free (osi.depths);
 401                   osi.depths = NULL;
 402                   free (osi.stack);
 403                   osi.stack = NULL;
 404                   osi.tos = NULL;
 405                 }
 406
 407               do
 408                 {
 409                   osi.pass = 2;
 410                   osi.changed = false;
 411                   /* collect_object_sizes_for is changing
 412                      osi.reexamine bitmap, so iterate over a copy.  */
 413                   bitmap_copy (reexamine, osi.reexamine);
 414                   EXECUTE_IF_SET_IN_BITMAP (reexamine, 0, i, bi)
 415                     if (bitmap_bit_p (osi.reexamine, i))
 416                       {
 417                         collect_object_sizes_for (&osi, ssa_name (i));
 418                         if (dump_file && (dump_flags & TDF_DETAILS))
 419                           {
 420                             fprintf (dump_file, "Reexamining ");
 421                             print_generic_expr (dump_file, ssa_name (i),
 422                                                 dump_flags);
 423                             fprintf (dump_file, "\n");
 424                           }
 425                       }
 426                 }
 427               while (osi.changed);
 428
 429               BITMAP_FREE (reexamine);
 430             }
 431           EXECUTE_IF_SET_IN_BITMAP (osi.reexamine, 0, i, bi)
 432             bitmap_set_bit (computed[object_size_type], i);
 433
 434           /* Debugging dumps.  */
 435           if (dump_file)
 436             {
 437               EXECUTE_IF_SET_IN_BITMAP (osi.visited, 0, i, bi)
 438                 if (object_sizes[object_size_type][i]
 439                     != unknown[object_size_type])
 440                   {
 441                     print_generic_expr (dump_file, ssa_name (i),
 442                                         dump_flags);
 443                     fprintf (dump_file,
 444                              ": %s %sobject size "
 445                              HOST_WIDE_INT_PRINT_UNSIGNED "\n",
 446                              (object_size_type & 2) ? "minimum" : "maximum",
 447                              (object_size_type & 1) ? "sub" : "",
 448                              object_sizes[object_size_type][i]);
 449                   }
 450             }
 451
 452           BITMAP_FREE (osi.reexamine);
 453           BITMAP_FREE (osi.visited);
 454         }
 455
 456       return object_sizes[object_size_type][SSA_NAME_VERSION (ptr)];
 457     }
 458
 459   return unknown[object_size_type];
 460 }
 461
 462
 463 /* Compute object_sizes for PTR, defined to VALUE, which is not
 464    a SSA_NAME.  */
 465
 466 static void
 467 expr_object_size (struct object_size_info *osi, tree ptr, tree value)
 468 {
 469   int object_size_type = osi->object_size_type;
 470   unsigned int varno = SSA_NAME_VERSION (ptr);
 471   unsigned HOST_WIDE_INT bytes;
 472
 473   gcc_assert (object_sizes[object_size_type][varno]
 474               != unknown[object_size_type]);
 475   gcc_assert (osi->pass == 0);
 476
 477   if (TREE_CODE (value) == WITH_SIZE_EXPR)
 478     value = TREE_OPERAND (value, 0);
 479
 480   /* Pointer variables should have been handled by merge_object_sizes.  */
 481   gcc_assert (TREE_CODE (value) != SSA_NAME
 482               || !POINTER_TYPE_P (TREE_TYPE (value)));
 483
 484   if (TREE_CODE (value) == ADDR_EXPR)
 485     bytes = addr_object_size (value, object_size_type);
 486   else if (TREE_CODE (value) == CALL_EXPR)
 487     bytes = alloc_object_size (value, object_size_type);
 488   else
 489     bytes = unknown[object_size_type];
 490
 491   if ((object_size_type & 2) == 0)
 492     {
 493       if (object_sizes[object_size_type][varno] < bytes)
 494         object_sizes[object_size_type][varno] = bytes;
 495     }
 496   else
 497     {
 498       if (object_sizes[object_size_type][varno] > bytes)
 499         object_sizes[object_size_type][varno] = bytes;
 500     }
 501 }
 502
 503
 504 /* Merge object sizes of ORIG + OFFSET into DEST.  Return true if
 505    the object size might need reexamination later.  */
 506
 507 static bool
 508 merge_object_sizes (struct object_size_info *osi, tree dest, tree orig,
 509                     unsigned HOST_WIDE_INT offset)
 510 {
 511   int object_size_type = osi->object_size_type;
 512   unsigned int varno = SSA_NAME_VERSION (dest);
 513   unsigned HOST_WIDE_INT orig_bytes;
 514
 515   if (object_sizes[object_size_type][varno] == unknown[object_size_type])
 516     return false;
 517   if (offset >= offset_limit)
 518     {
 519       object_sizes[object_size_type][varno] = unknown[object_size_type];
 520       return false;
 521     }
 522
 523   if (osi->pass == 0)
 524     collect_object_sizes_for (osi, orig);
 525
 526   orig_bytes = object_sizes[object_size_type][SSA_NAME_VERSION (orig)];
 527   if (orig_bytes != unknown[object_size_type])
 528     orig_bytes = (offset > orig_bytes)
 529                  ? (unsigned HOST_WIDE_INT) 0 : orig_bytes - offset;
 530
 531   if ((object_size_type & 2) == 0)
 532     {
 533       if (object_sizes[object_size_type][varno] < orig_bytes)
 534         {
 535           object_sizes[object_size_type][varno] = orig_bytes;
 536           osi->changed = true;
 537         }
 538     }
 539   else
 540     {
 541       if (object_sizes[object_size_type][varno] > orig_bytes)
 542         {
 543           object_sizes[object_size_type][varno] = orig_bytes;
 544           osi->changed = true;
 545         }
 546     }
 547   return bitmap_bit_p (osi->reexamine, SSA_NAME_VERSION (orig));
 548 }
 549
 550
 551 /* Compute object_sizes for PTR, defined to VALUE, which is
 552    a PLUS_EXPR.  Return true if the object size might need reexamination
 553    later.  */
 554
 555 static bool
 556 plus_expr_object_size (struct object_size_info *osi, tree var, tree value)
 557 {
 558   tree op0 = TREE_OPERAND (value, 0);
 559   tree op1 = TREE_OPERAND (value, 1);
 560   bool ptr1_p = POINTER_TYPE_P (TREE_TYPE (op0))
 561                 && TREE_CODE (op0) != INTEGER_CST;
 562   bool ptr2_p = POINTER_TYPE_P (TREE_TYPE (op1))
 563                 && TREE_CODE (op1) != INTEGER_CST;
 564   int object_size_type = osi->object_size_type;
 565   unsigned int varno = SSA_NAME_VERSION (var);
 566   unsigned HOST_WIDE_INT bytes;
 567
 568   gcc_assert (TREE_CODE (value) == PLUS_EXPR);
 569
 570   if (object_sizes[object_size_type][varno] == unknown[object_size_type])
 571     return false;
 572
 573   /* Swap operands if needed.  */
 574   if (ptr2_p && !ptr1_p)
 575     {
 576       tree tem = op0;
 577       op0 = op1;
 578       op1 = tem;
 579       ptr1_p = true;
 580       ptr2_p = false;
 581     }
 582
 583   /* Handle PTR + OFFSET here.  */
 584   if (ptr1_p
 585       && !ptr2_p
 586       && TREE_CODE (op1) == INTEGER_CST
 587       && (TREE_CODE (op0) == SSA_NAME
 588           || TREE_CODE (op0) == ADDR_EXPR))
 589     {
 590       if (! host_integerp (op1, 1))
 591         bytes = unknown[object_size_type];
 592       else if (TREE_CODE (op0) == SSA_NAME)
 593         return merge_object_sizes (osi, var, op0, tree_low_cst (op1, 1));
 594       else
 595         {
 596           unsigned HOST_WIDE_INT off = tree_low_cst (op1, 1);
 597
 598           bytes = compute_builtin_object_size (value, object_size_type);
 599           if (off > offset_limit)
 600             bytes = unknown[object_size_type];
 601           else if (off > bytes)
 602             bytes = 0;
 603           else
 604             bytes -= off;
 605         }
 606     }
 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   return false;
 621 }
 622
 623
 624 /* Compute object sizes for VAR.
 625    For ADDR_EXPR an object size is the number of remaining bytes
 626    to the end of the object (where what is considered an object depends on
 627    OSI->object_size_type).
 628    For allocation CALL_EXPR like malloc or calloc object size is the size
 629    of the allocation.
 630    For pointer PLUS_EXPR where second operand is a constant integer,
 631    object size is object size of the first operand minus the constant.
 632    If the constant is bigger than the number of remaining bytes until the
 633    end of the object, object size is 0, but if it is instead a pointer
 634    subtraction, object size is unknown[object_size_type].
 635    To differentiate addition from subtraction, ADDR_EXPR returns
 636    unknown[object_size_type] for all objects bigger than half of the address
 637    space, and constants less than half of the address space are considered
 638    addition, while bigger constants subtraction.
 639    For a memcpy like CALL_EXPR that always returns one of its arguments, the
 640    object size is object size of that argument.
 641    Otherwise, object size is the maximum of object sizes of variables
 642    that it might be set to.  */
 643
 644 static void
 645 collect_object_sizes_for (struct object_size_info *osi, tree var)
 646 {
 647   int object_size_type = osi->object_size_type;
 648   unsigned int varno = SSA_NAME_VERSION (var);
 649   tree stmt;
 650   bool reexamine;
 651
 652   if (bitmap_bit_p (computed[object_size_type], varno))
 653     return;
 654
 655   if (osi->pass == 0)
 656     {
 657       if (! bitmap_bit_p (osi->visited, varno))
 658         {
 659           bitmap_set_bit (osi->visited, varno);
 660           object_sizes[object_size_type][varno]
 661             = (object_size_type & 2) ? -1 : 0;
 662         }
 663       else
 664         {
 665           /* Found a dependency loop.  Mark the variable for later
 666              re-examination.  */
 667           bitmap_set_bit (osi->reexamine, varno);
 668           if (dump_file && (dump_flags & TDF_DETAILS))
 669             {
 670               fprintf (dump_file, "Found a dependency loop at ");
 671               print_generic_expr (dump_file, var, dump_flags);
 672               fprintf (dump_file, "\n");
 673             }
 674           return;
 675         }
 676     }
 677
 678   if (dump_file && (dump_flags & TDF_DETAILS))
 679     {
 680       fprintf (dump_file, "Visiting use-def links for ");
 681       print_generic_expr (dump_file, var, dump_flags);
 682       fprintf (dump_file, "\n");
 683     }
 684
 685   stmt = SSA_NAME_DEF_STMT (var);
 686   reexamine = false;
 687
 688   switch (TREE_CODE (stmt))
 689     {
 690     case RETURN_EXPR:
 691       if (TREE_CODE (TREE_OPERAND (stmt, 0)) != MODIFY_EXPR)
 692         abort ();
 693       stmt = TREE_OPERAND (stmt, 0);
 694       /* FALLTHRU  */
 695
 696     case MODIFY_EXPR:
 697       {
 698         tree rhs = TREE_OPERAND (stmt, 1), arg;
 699         STRIP_NOPS (rhs);
 700
 701         if (TREE_CODE (rhs) == CALL_EXPR)
 702           {
 703             arg = pass_through_call (rhs);
 704             if (arg)
 705               rhs = arg;
 706           }
 707
 708         if (TREE_CODE (rhs) == SSA_NAME
 709             && POINTER_TYPE_P (TREE_TYPE (rhs)))
 710           reexamine = merge_object_sizes (osi, var, rhs, 0);
 711
 712         else if (TREE_CODE (rhs) == PLUS_EXPR)
 713           reexamine = plus_expr_object_size (osi, var, rhs);
 714
 715         else
 716           expr_object_size (osi, var, rhs);
 717         break;
 718       }
 719
 720     case ASM_EXPR:
 721       /* Pointers defined by __asm__ statements can point anywhere.  */
 722       object_sizes[object_size_type][varno] = unknown[object_size_type];
 723       break;
 724
 725     case NOP_EXPR:
 726       {
 727         tree decl = SSA_NAME_VAR (var);
 728
 729         gcc_assert (IS_EMPTY_STMT (stmt));
 730
 731         if (TREE_CODE (decl) != PARM_DECL && DECL_INITIAL (decl))
 732           expr_object_size (osi, var, DECL_INITIAL (decl));
 733         else
 734           expr_object_size (osi, var, decl);
 735       }
 736       break;
 737
 738     case PHI_NODE:
 739       {
 740         int i;
 741
 742         for (i = 0; i < PHI_NUM_ARGS (stmt); i++)
 743           {
 744             tree rhs = PHI_ARG_DEF (stmt, i);
 745
 746             if (object_sizes[object_size_type][varno]
 747                 == unknown[object_size_type])
 748               break;
 749
 750             if (TREE_CODE (rhs) == SSA_NAME)
 751               reexamine |= merge_object_sizes (osi, var, rhs, 0);
 752             else if (osi->pass == 0)
 753               expr_object_size (osi, var, rhs);
 754           }
 755         break;
 756       }
 757     default:
 758       gcc_unreachable ();
 759     }
 760
 761   if (! reexamine
 762       || object_sizes[object_size_type][varno] == unknown[object_size_type])
 763     {
 764       bitmap_set_bit (computed[object_size_type], varno);
 765       bitmap_clear_bit (osi->reexamine, varno);
 766     }
 767   else
 768     {
 769       bitmap_set_bit (osi->reexamine, varno);
 770       if (dump_file && (dump_flags & TDF_DETAILS))
 771         {
 772           fprintf (dump_file, "Need to reexamine ");
 773           print_generic_expr (dump_file, var, dump_flags);
 774           fprintf (dump_file, "\n");
 775         }
 776     }
 777 }
 778
 779
 780 /* Helper function for check_for_plus_in_loops.  Called recursively
 781    to detect loops.  */
 782
 783 static void
 784 check_for_plus_in_loops_1 (struct object_size_info *osi, tree var,
 785                            unsigned int depth)
 786 {
 787   tree stmt = SSA_NAME_DEF_STMT (var);
 788   unsigned int varno = SSA_NAME_VERSION (var);
 789
 790   if (osi->depths[varno])
 791     {
 792       if (osi->depths[varno] != depth)
 793         {
 794           unsigned int *sp;
 795
 796           /* Found a loop involving pointer addition.  */
 797           for (sp = osi->tos; sp > osi->stack; )
 798             {
 799               --sp;
 800               bitmap_clear_bit (osi->reexamine, *sp);
 801               bitmap_set_bit (computed[osi->object_size_type], *sp);
 802               object_sizes[osi->object_size_type][*sp] = 0;
 803               if (*sp == varno)
 804                 break;
 805             }
 806         }
 807       return;
 808     }
 809   else if (! bitmap_bit_p (osi->reexamine, varno))
 810     return;
 811
 812   osi->depths[varno] = depth;
 813   *osi->tos++ = varno;
 814
 815   switch (TREE_CODE (stmt))
 816     {
 817     case RETURN_EXPR:
 818       if (TREE_CODE (TREE_OPERAND (stmt, 0)) != MODIFY_EXPR)
 819         abort ();
 820       stmt = TREE_OPERAND (stmt, 0);
 821       /* FALLTHRU  */
 822
 823     case MODIFY_EXPR:
 824       {
 825         tree rhs = TREE_OPERAND (stmt, 1), arg;
 826         STRIP_NOPS (rhs);
 827
 828         if (TREE_CODE (rhs) == CALL_EXPR)
 829           {
 830             arg = pass_through_call (rhs);
 831             if (arg)
 832               rhs = arg;
 833           }
 834
 835         if (TREE_CODE (rhs) == SSA_NAME)
 836           check_for_plus_in_loops_1 (osi, rhs, depth);
 837         else if (TREE_CODE (rhs) == PLUS_EXPR)
 838           {
 839             tree op0 = TREE_OPERAND (rhs, 0);
 840             tree op1 = TREE_OPERAND (rhs, 1);
 841             tree cst, basevar;
 842
 843             if (TREE_CODE (op0) == SSA_NAME)
 844               {
 845                 basevar = op0;
 846                 cst = op1;
 847               }
 848             else
 849               {
 850                 basevar = op1;
 851                 cst = op0;
 852                 gcc_assert (TREE_CODE (basevar) == SSA_NAME);
 853               }
 854             gcc_assert (TREE_CODE (cst) == INTEGER_CST);
 855
 856             check_for_plus_in_loops_1 (osi, basevar,
 857                                        depth + !integer_zerop (cst));
 858           }
 859         else
 860           gcc_unreachable ();
 861         break;
 862       }
 863     case PHI_NODE:
 864       {
 865         int i;
 866
 867         for (i = 0; i < PHI_NUM_ARGS (stmt); i++)
 868           {
 869             tree rhs = PHI_ARG_DEF (stmt, i);
 870
 871             if (TREE_CODE (rhs) == SSA_NAME)
 872               check_for_plus_in_loops_1 (osi, rhs, depth);
 873           }
 874         break;
 875       }
 876     default:
 877       gcc_unreachable ();
 878     }
 879
 880   osi->depths[varno] = 0;
 881   osi->tos--;
 882 }
 883
 884
 885 /* Check if some pointer we are computing object size of is being increased
 886    within a loop.  If yes, assume all the SSA variables participating in
 887    that loop have minimum object sizes 0.  */
 888
 889 static void
 890 check_for_plus_in_loops (struct object_size_info *osi, tree var)
 891 {
 892   tree stmt = SSA_NAME_DEF_STMT (var);
 893
 894   switch (TREE_CODE (stmt))
 895     {
 896     case RETURN_EXPR:
 897       if (TREE_CODE (TREE_OPERAND (stmt, 0)) != MODIFY_EXPR)
 898         abort ();
 899       stmt = TREE_OPERAND (stmt, 0);
 900       /* FALLTHRU  */
 901
 902     case MODIFY_EXPR:
 903       {
 904         tree rhs = TREE_OPERAND (stmt, 1), arg;
 905         STRIP_NOPS (rhs);
 906
 907         if (TREE_CODE (rhs) == CALL_EXPR)
 908           {
 909             arg = pass_through_call (rhs);
 910             if (arg)
 911               rhs = arg;
 912           }
 913
 914         if (TREE_CODE (rhs) == PLUS_EXPR)
 915           {
 916             tree op0 = TREE_OPERAND (rhs, 0);
 917             tree op1 = TREE_OPERAND (rhs, 1);
 918             tree cst, basevar;
 919
 920             if (TREE_CODE (op0) == SSA_NAME)
 921               {
 922                 basevar = op0;
 923                 cst = op1;
 924               }
 925             else
 926               {
 927                 basevar = op1;
 928                 cst = op0;
 929                 gcc_assert (TREE_CODE (basevar) == SSA_NAME);
 930               }
 931             gcc_assert (TREE_CODE (cst) == INTEGER_CST);
 932
 933             if (integer_zerop (cst))
 934               break;
 935
 936             osi->depths[SSA_NAME_VERSION (basevar)] = 1;
 937             *osi->tos++ = SSA_NAME_VERSION (basevar);
 938             check_for_plus_in_loops_1 (osi, var, 2);
 939             osi->depths[SSA_NAME_VERSION (basevar)] = 0;
 940             osi->tos--;
 941           }
 942         break;
 943       }
 944     default:
 945       break;
 946     }
 947 }
 948
 949
 950 /* Initialize data structures for the object size computation.  */
 951
 952 void
 953 init_object_sizes (void)
 954 {
 955   int object_size_type;
 956
 957   if (object_sizes[0])
 958     return;
 959
 960   for (object_size_type = 0; object_size_type <= 3; object_size_type++)
 961     {
 962       object_sizes[object_size_type]
 963         = xmalloc (num_ssa_names * sizeof (HOST_WIDE_INT));
 964       computed[object_size_type] = BITMAP_ALLOC (NULL);
 965     }
 966
 967   init_offset_limit ();
 968 }
 969
 970
 971 /* Destroy data structures after the object size computation.  */
 972
 973 void
 974 fini_object_sizes (void)
 975 {
 976   int object_size_type;
 977
 978   for (object_size_type = 0; object_size_type <= 3; object_size_type++)
 979     {
 980       free (object_sizes[object_size_type]);
 981       BITMAP_FREE (computed[object_size_type]);
 982       object_sizes[object_size_type] = NULL;
 983     }
 984 }
 985
 986
 987 /* Simple pass to optimize all __builtin_object_size () builtins.  */
 988
 989 static void
 990 compute_object_sizes (void)
 991 {
 992   basic_block bb;
 993   FOR_EACH_BB (bb)
 994     {
 995       block_stmt_iterator i;
 996       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 997         {
 998           tree *stmtp = bsi_stmt_ptr (i);
 999           tree call = get_rhs (*stmtp);
1000           tree callee, result;
1001
1002           if (!call || TREE_CODE (call) != CALL_EXPR)
1003             continue;
1004
1005           callee = get_callee_fndecl (call);
1006           if (!callee
1007               || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
1008               || DECL_FUNCTION_CODE (callee) != BUILT_IN_OBJECT_SIZE)
1009             continue;
1010
1011           init_object_sizes ();
1012           result = fold_builtin (callee, TREE_OPERAND (call, 1), false);
1013           if (!result)
1014             {
1015               tree arglist = TREE_OPERAND (call, 1);
1016
1017               if (arglist != NULL
1018                   && POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arglist)))
1019                   && TREE_CHAIN (arglist) != NULL
1020                   && TREE_CHAIN (TREE_CHAIN (arglist)) == NULL)
1021                 {
1022                   tree ost = TREE_VALUE (TREE_CHAIN (arglist));
1023
1024                   if (host_integerp (ost, 1))
1025                     {
1026                       unsigned HOST_WIDE_INT object_size_type
1027                         = tree_low_cst (ost, 1);
1028
1029                       if (object_size_type < 2)
1030                         result = fold_convert (size_type_node,
1031                                                integer_minus_one_node);
1032                       else if (object_size_type < 4)
1033                         result = size_zero_node;
1034                     }
1035                 }
1036
1037               if (!result)
1038                 continue;
1039             }
1040
1041           if (dump_file && (dump_flags & TDF_DETAILS))
1042             {
1043               fprintf (dump_file, "Simplified\n  ");
1044               print_generic_stmt (dump_file, *stmtp, dump_flags);
1045             }
1046
1047           if (!set_rhs (stmtp, result))
1048             abort ();
1049           update_stmt (*stmtp);
1050
1051           if (dump_file && (dump_flags & TDF_DETAILS))
1052             {
1053               fprintf (dump_file, "to\n  ");
1054               print_generic_stmt (dump_file, *stmtp, dump_flags);
1055               fprintf (dump_file, "\n");
1056             }
1057         }
1058     }
1059
1060   fini_object_sizes ();
1061 }
1062
1063 struct tree_opt_pass pass_object_sizes =
1064 {
1065   "objsz",                              /* name */
1066   NULL,                                 /* gate */
1067   compute_object_sizes,                 /* execute */
1068   NULL,                                 /* sub */
1069   NULL,                                 /* next */
1070   0,                                    /* static_pass_number */
1071   0,                                    /* tv_id */
1072   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1073   0,                                    /* properties_provided */
1074   0,                                    /* properties_destroyed */
1075   0,                                    /* todo_flags_start */
1076   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1077   0                                     /* letter */
1078 };