gcc/tree-object-size.c

   1 /* __builtin_object_size (ptr, object_size_type) computation
   2    Copyright (C) 2004, 2005, 2006 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 unsigned int 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 = fold_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 = XCNEWVEC (unsigned int, num_ssa_names);
 390                   osi.stack = XNEWVEC (unsigned int, num_ssa_names);
 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 (op0, 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       gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR);
 692       stmt = TREE_OPERAND (stmt, 0);
 693       /* FALLTHRU  */
 694
 695     case MODIFY_EXPR:
 696       {
 697         tree rhs = TREE_OPERAND (stmt, 1), arg;
 698         STRIP_NOPS (rhs);
 699
 700         if (TREE_CODE (rhs) == CALL_EXPR)
 701           {
 702             arg = pass_through_call (rhs);
 703             if (arg)
 704               rhs = arg;
 705           }
 706
 707         if (TREE_CODE (rhs) == SSA_NAME
 708             && POINTER_TYPE_P (TREE_TYPE (rhs)))
 709           reexamine = merge_object_sizes (osi, var, rhs, 0);
 710
 711         else if (TREE_CODE (rhs) == PLUS_EXPR)
 712           reexamine = plus_expr_object_size (osi, var, rhs);
 713
 714         else
 715           expr_object_size (osi, var, rhs);
 716         break;
 717       }
 718
 719     case ASM_EXPR:
 720       /* Pointers defined by __asm__ statements can point anywhere.  */
 721       object_sizes[object_size_type][varno] = unknown[object_size_type];
 722       break;
 723
 724     case NOP_EXPR:
 725       {
 726         tree decl = SSA_NAME_VAR (var);
 727
 728         gcc_assert (IS_EMPTY_STMT (stmt));
 729
 730         if (TREE_CODE (decl) != PARM_DECL && DECL_INITIAL (decl))
 731           expr_object_size (osi, var, DECL_INITIAL (decl));
 732         else
 733           expr_object_size (osi, var, decl);
 734       }
 735       break;
 736
 737     case PHI_NODE:
 738       {
 739         int i;
 740
 741         for (i = 0; i < PHI_NUM_ARGS (stmt); i++)
 742           {
 743             tree rhs = PHI_ARG_DEF (stmt, i);
 744
 745             if (object_sizes[object_size_type][varno]
 746                 == unknown[object_size_type])
 747               break;
 748
 749             if (TREE_CODE (rhs) == SSA_NAME)
 750               reexamine |= merge_object_sizes (osi, var, rhs, 0);
 751             else if (osi->pass == 0)
 752               expr_object_size (osi, var, rhs);
 753           }
 754         break;
 755       }
 756     default:
 757       gcc_unreachable ();
 758     }
 759
 760   if (! reexamine
 761       || object_sizes[object_size_type][varno] == unknown[object_size_type])
 762     {
 763       bitmap_set_bit (computed[object_size_type], varno);
 764       bitmap_clear_bit (osi->reexamine, varno);
 765     }
 766   else
 767     {
 768       bitmap_set_bit (osi->reexamine, varno);
 769       if (dump_file && (dump_flags & TDF_DETAILS))
 770         {
 771           fprintf (dump_file, "Need to reexamine ");
 772           print_generic_expr (dump_file, var, dump_flags);
 773           fprintf (dump_file, "\n");
 774         }
 775     }
 776 }
 777
 778
 779 /* Helper function for check_for_plus_in_loops.  Called recursively
 780    to detect loops.  */
 781
 782 static void
 783 check_for_plus_in_loops_1 (struct object_size_info *osi, tree var,
 784                            unsigned int depth)
 785 {
 786   tree stmt = SSA_NAME_DEF_STMT (var);
 787   unsigned int varno = SSA_NAME_VERSION (var);
 788
 789   if (osi->depths[varno])
 790     {
 791       if (osi->depths[varno] != depth)
 792         {
 793           unsigned int *sp;
 794
 795           /* Found a loop involving pointer addition.  */
 796           for (sp = osi->tos; sp > osi->stack; )
 797             {
 798               --sp;
 799               bitmap_clear_bit (osi->reexamine, *sp);
 800               bitmap_set_bit (computed[osi->object_size_type], *sp);
 801               object_sizes[osi->object_size_type][*sp] = 0;
 802               if (*sp == varno)
 803                 break;
 804             }
 805         }
 806       return;
 807     }
 808   else if (! bitmap_bit_p (osi->reexamine, varno))
 809     return;
 810
 811   osi->depths[varno] = depth;
 812   *osi->tos++ = varno;
 813
 814   switch (TREE_CODE (stmt))
 815     {
 816     case RETURN_EXPR:
 817       gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR);
 818       stmt = TREE_OPERAND (stmt, 0);
 819       /* FALLTHRU  */
 820
 821     case MODIFY_EXPR:
 822       {
 823         tree rhs = TREE_OPERAND (stmt, 1), arg;
 824         STRIP_NOPS (rhs);
 825
 826         if (TREE_CODE (rhs) == CALL_EXPR)
 827           {
 828             arg = pass_through_call (rhs);
 829             if (arg)
 830               rhs = arg;
 831           }
 832
 833         if (TREE_CODE (rhs) == SSA_NAME)
 834           check_for_plus_in_loops_1 (osi, rhs, depth);
 835         else if (TREE_CODE (rhs) == PLUS_EXPR)
 836           {
 837             tree op0 = TREE_OPERAND (rhs, 0);
 838             tree op1 = TREE_OPERAND (rhs, 1);
 839             tree cst, basevar;
 840
 841             if (TREE_CODE (op0) == SSA_NAME)
 842               {
 843                 basevar = op0;
 844                 cst = op1;
 845               }
 846             else
 847               {
 848                 basevar = op1;
 849                 cst = op0;
 850                 gcc_assert (TREE_CODE (basevar) == SSA_NAME);
 851               }
 852             gcc_assert (TREE_CODE (cst) == INTEGER_CST);
 853
 854             check_for_plus_in_loops_1 (osi, basevar,
 855                                        depth + !integer_zerop (cst));
 856           }
 857         else
 858           gcc_unreachable ();
 859         break;
 860       }
 861     case PHI_NODE:
 862       {
 863         int i;
 864
 865         for (i = 0; i < PHI_NUM_ARGS (stmt); i++)
 866           {
 867             tree rhs = PHI_ARG_DEF (stmt, i);
 868
 869             if (TREE_CODE (rhs) == SSA_NAME)
 870               check_for_plus_in_loops_1 (osi, rhs, depth);
 871           }
 872         break;
 873       }
 874     default:
 875       gcc_unreachable ();
 876     }
 877
 878   osi->depths[varno] = 0;
 879   osi->tos--;
 880 }
 881
 882
 883 /* Check if some pointer we are computing object size of is being increased
 884    within a loop.  If yes, assume all the SSA variables participating in
 885    that loop have minimum object sizes 0.  */
 886
 887 static void
 888 check_for_plus_in_loops (struct object_size_info *osi, tree var)
 889 {
 890   tree stmt = SSA_NAME_DEF_STMT (var);
 891
 892   switch (TREE_CODE (stmt))
 893     {
 894     case RETURN_EXPR:
 895       gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR);
 896       stmt = TREE_OPERAND (stmt, 0);
 897       /* FALLTHRU  */
 898
 899     case MODIFY_EXPR:
 900       {
 901         tree rhs = TREE_OPERAND (stmt, 1), arg;
 902         STRIP_NOPS (rhs);
 903
 904         if (TREE_CODE (rhs) == CALL_EXPR)
 905           {
 906             arg = pass_through_call (rhs);
 907             if (arg)
 908               rhs = arg;
 909           }
 910
 911         if (TREE_CODE (rhs) == PLUS_EXPR)
 912           {
 913             tree op0 = TREE_OPERAND (rhs, 0);
 914             tree op1 = TREE_OPERAND (rhs, 1);
 915             tree cst, basevar;
 916
 917             if (TREE_CODE (op0) == SSA_NAME)
 918               {
 919                 basevar = op0;
 920                 cst = op1;
 921               }
 922             else
 923               {
 924                 basevar = op1;
 925                 cst = op0;
 926                 gcc_assert (TREE_CODE (basevar) == SSA_NAME);
 927               }
 928             gcc_assert (TREE_CODE (cst) == INTEGER_CST);
 929
 930             if (integer_zerop (cst))
 931               break;
 932
 933             osi->depths[SSA_NAME_VERSION (basevar)] = 1;
 934             *osi->tos++ = SSA_NAME_VERSION (basevar);
 935             check_for_plus_in_loops_1 (osi, var, 2);
 936             osi->depths[SSA_NAME_VERSION (basevar)] = 0;
 937             osi->tos--;
 938           }
 939         break;
 940       }
 941     default:
 942       break;
 943     }
 944 }
 945
 946
 947 /* Initialize data structures for the object size computation.  */
 948
 949 void
 950 init_object_sizes (void)
 951 {
 952   int object_size_type;
 953
 954   if (object_sizes[0])
 955     return;
 956
 957   for (object_size_type = 0; object_size_type <= 3; object_size_type++)
 958     {
 959       object_sizes[object_size_type] = XNEWVEC (unsigned HOST_WIDE_INT, num_ssa_names);
 960       computed[object_size_type] = BITMAP_ALLOC (NULL);
 961     }
 962
 963   init_offset_limit ();
 964 }
 965
 966
 967 /* Destroy data structures after the object size computation.  */
 968
 969 void
 970 fini_object_sizes (void)
 971 {
 972   int object_size_type;
 973
 974   for (object_size_type = 0; object_size_type <= 3; object_size_type++)
 975     {
 976       free (object_sizes[object_size_type]);
 977       BITMAP_FREE (computed[object_size_type]);
 978       object_sizes[object_size_type] = NULL;
 979     }
 980 }
 981
 982
 983 /* Simple pass to optimize all __builtin_object_size () builtins.  */
 984
 985 static unsigned int
 986 compute_object_sizes (void)
 987 {
 988   basic_block bb;
 989   FOR_EACH_BB (bb)
 990     {
 991       block_stmt_iterator i;
 992       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 993         {
 994           tree *stmtp = bsi_stmt_ptr (i);
 995           tree call = get_rhs (*stmtp);
 996           tree callee, result;
 997
 998           if (!call || TREE_CODE (call) != CALL_EXPR)
 999             continue;
1000
1001           callee = get_callee_fndecl (call);
1002           if (!callee
1003               || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
1004               || DECL_FUNCTION_CODE (callee) != BUILT_IN_OBJECT_SIZE)
1005             continue;
1006
1007           init_object_sizes ();
1008           result = fold_builtin (callee, TREE_OPERAND (call, 1), false);
1009           if (!result)
1010             {
1011               tree arglist = TREE_OPERAND (call, 1);
1012
1013               if (arglist != NULL
1014                   && POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arglist)))
1015                   && TREE_CHAIN (arglist) != NULL
1016                   && TREE_CHAIN (TREE_CHAIN (arglist)) == NULL)
1017                 {
1018                   tree ost = TREE_VALUE (TREE_CHAIN (arglist));
1019
1020                   if (host_integerp (ost, 1))
1021                     {
1022                       unsigned HOST_WIDE_INT object_size_type
1023                         = tree_low_cst (ost, 1);
1024
1025                       if (object_size_type < 2)
1026                         result = fold_convert (size_type_node,
1027                                                integer_minus_one_node);
1028                       else if (object_size_type < 4)
1029                         result = size_zero_node;
1030                     }
1031                 }
1032
1033               if (!result)
1034                 continue;
1035             }
1036
1037           if (dump_file && (dump_flags & TDF_DETAILS))
1038             {
1039               fprintf (dump_file, "Simplified\n  ");
1040               print_generic_stmt (dump_file, *stmtp, dump_flags);
1041             }
1042
1043           if (!set_rhs (stmtp, result))
1044             gcc_unreachable ();
1045           update_stmt (*stmtp);
1046
1047           if (dump_file && (dump_flags & TDF_DETAILS))
1048             {
1049               fprintf (dump_file, "to\n  ");
1050               print_generic_stmt (dump_file, *stmtp, dump_flags);
1051               fprintf (dump_file, "\n");
1052             }
1053         }
1054     }
1055
1056   fini_object_sizes ();
1057   return 0;
1058 }
1059
1060 struct tree_opt_pass pass_object_sizes =
1061 {
1062   "objsz",                              /* name */
1063   NULL,                                 /* gate */
1064   compute_object_sizes,                 /* execute */
1065   NULL,                                 /* sub */
1066   NULL,                                 /* next */
1067   0,                                    /* static_pass_number */
1068   0,                                    /* tv_id */
1069   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1070   0,                                    /* properties_provided */
1071   0,                                    /* properties_destroyed */
1072   0,                                    /* todo_flags_start */
1073   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
1074   0                                     /* letter */
1075 };