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