gcc/tree-object-size.c

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