OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [tree-object-size.c] - Blame information for rev 859

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.