gcc/tree-object-size.c

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