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