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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-object-size.c] - Blame information for rev 841

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

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

powered by: WebSVN 2.1.0

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