gcc/tree-object-size.c

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