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