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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [cfg.c] - Blame information for rev 684

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* Control flow graph manipulation code for GNU compiler.
2
   Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3
   1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4
   Free Software Foundation, Inc.
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify it under
9
the terms of the GNU General Public License as published by the Free
10
Software Foundation; either version 3, or (at your option) any later
11
version.
12
 
13
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14
WARRANTY; without even the implied warranty of MERCHANTABILITY or
15
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16
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
/* This file contains low level functions to manipulate the CFG and
23
   analyze it.  All other modules should not transform the data structure
24
   directly and use abstraction instead.  The file is supposed to be
25
   ordered bottom-up and should not contain any code dependent on a
26
   particular intermediate language (RTL or trees).
27
 
28
   Available functionality:
29
     - Initialization/deallocation
30
         init_flow, clear_edges
31
     - Low level basic block manipulation
32
         alloc_block, expunge_block
33
     - Edge manipulation
34
         make_edge, make_single_succ_edge, cached_make_edge, remove_edge
35
         - Low level edge redirection (without updating instruction chain)
36
             redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
37
     - Dumping and debugging
38
         dump_flow_info, debug_flow_info, dump_edge_info
39
     - Allocation of AUX fields for basic blocks
40
         alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
41
     - clear_bb_flags
42
     - Consistency checking
43
         verify_flow_info
44
     - Dumping and debugging
45
         print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
46
 */
47
 
48
#include "config.h"
49
#include "system.h"
50
#include "coretypes.h"
51
#include "tm.h"
52
#include "tree.h"
53
#include "rtl.h"
54
#include "hard-reg-set.h"
55
#include "regs.h"
56
#include "flags.h"
57
#include "output.h"
58
#include "function.h"
59
#include "except.h"
60
#include "diagnostic-core.h"
61
#include "tm_p.h"
62
#include "obstack.h"
63
#include "timevar.h"
64
#include "tree-pass.h"
65
#include "ggc.h"
66
#include "hashtab.h"
67
#include "alloc-pool.h"
68
#include "df.h"
69
#include "cfgloop.h"
70
#include "tree-flow.h"
71
 
72
/* The obstack on which the flow graph components are allocated.  */
73
 
74
struct bitmap_obstack reg_obstack;
75
 
76
void debug_flow_info (void);
77
static void free_edge (edge);
78
 
79
#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
80
 
81
/* Called once at initialization time.  */
82
 
83
void
84
init_flow (struct function *the_fun)
85
{
86
  if (!the_fun->cfg)
87
    the_fun->cfg = ggc_alloc_cleared_control_flow_graph ();
88
  n_edges_for_function (the_fun) = 0;
89
  ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)
90
    = ggc_alloc_cleared_basic_block_def ();
91
  ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = ENTRY_BLOCK;
92
  EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)
93
    = ggc_alloc_cleared_basic_block_def ();
94
  EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = EXIT_BLOCK;
95
  ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->next_bb
96
    = EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun);
97
  EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->prev_bb
98
    = ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun);
99
}
100
 
101
/* Helper function for remove_edge and clear_edges.  Frees edge structure
102
   without actually unlinking it from the pred/succ lists.  */
103
 
104
static void
105
free_edge (edge e ATTRIBUTE_UNUSED)
106
{
107
  n_edges--;
108
  ggc_free (e);
109
}
110
 
111
/* Free the memory associated with the edge structures.  */
112
 
113
void
114
clear_edges (void)
115
{
116
  basic_block bb;
117
  edge e;
118
  edge_iterator ei;
119
 
120
  FOR_EACH_BB (bb)
121
    {
122
      FOR_EACH_EDGE (e, ei, bb->succs)
123
        free_edge (e);
124
      VEC_truncate (edge, bb->succs, 0);
125
      VEC_truncate (edge, bb->preds, 0);
126
    }
127
 
128
  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
129
    free_edge (e);
130
  VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0);
131
  VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0);
132
 
133
  gcc_assert (!n_edges);
134
}
135
 
136
/* Allocate memory for basic_block.  */
137
 
138
basic_block
139
alloc_block (void)
140
{
141
  basic_block bb;
142
  bb = ggc_alloc_cleared_basic_block_def ();
143
  return bb;
144
}
145
 
146
/* Link block B to chain after AFTER.  */
147
void
148
link_block (basic_block b, basic_block after)
149
{
150
  b->next_bb = after->next_bb;
151
  b->prev_bb = after;
152
  after->next_bb = b;
153
  b->next_bb->prev_bb = b;
154
}
155
 
156
/* Unlink block B from chain.  */
157
void
158
unlink_block (basic_block b)
159
{
160
  b->next_bb->prev_bb = b->prev_bb;
161
  b->prev_bb->next_bb = b->next_bb;
162
  b->prev_bb = NULL;
163
  b->next_bb = NULL;
164
}
165
 
166
/* Sequentially order blocks and compact the arrays.  */
167
void
168
compact_blocks (void)
169
{
170
  int i;
171
 
172
  SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
173
  SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
174
 
175
  if (df)
176
    df_compact_blocks ();
177
  else
178
    {
179
      basic_block bb;
180
 
181
      i = NUM_FIXED_BLOCKS;
182
      FOR_EACH_BB (bb)
183
        {
184
          SET_BASIC_BLOCK (i, bb);
185
          bb->index = i;
186
          i++;
187
        }
188
      gcc_assert (i == n_basic_blocks);
189
 
190
      for (; i < last_basic_block; i++)
191
        SET_BASIC_BLOCK (i, NULL);
192
    }
193
  last_basic_block = n_basic_blocks;
194
}
195
 
196
/* Remove block B from the basic block array.  */
197
 
198
void
199
expunge_block (basic_block b)
200
{
201
  unlink_block (b);
202
  SET_BASIC_BLOCK (b->index, NULL);
203
  n_basic_blocks--;
204
  /* We should be able to ggc_free here, but we are not.
205
     The dead SSA_NAMES are left pointing to dead statements that are pointing
206
     to dead basic blocks making garbage collector to die.
207
     We should be able to release all dead SSA_NAMES and at the same time we should
208
     clear out BB pointer of dead statements consistently.  */
209
}
210
 
211
/* Connect E to E->src.  */
212
 
213
static inline void
214
connect_src (edge e)
215
{
216
  VEC_safe_push (edge, gc, e->src->succs, e);
217
  df_mark_solutions_dirty ();
218
}
219
 
220
/* Connect E to E->dest.  */
221
 
222
static inline void
223
connect_dest (edge e)
224
{
225
  basic_block dest = e->dest;
226
  VEC_safe_push (edge, gc, dest->preds, e);
227
  e->dest_idx = EDGE_COUNT (dest->preds) - 1;
228
  df_mark_solutions_dirty ();
229
}
230
 
231
/* Disconnect edge E from E->src.  */
232
 
233
static inline void
234
disconnect_src (edge e)
235
{
236
  basic_block src = e->src;
237
  edge_iterator ei;
238
  edge tmp;
239
 
240
  for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
241
    {
242
      if (tmp == e)
243
        {
244
          VEC_unordered_remove (edge, src->succs, ei.index);
245
          return;
246
        }
247
      else
248
        ei_next (&ei);
249
    }
250
 
251
  df_mark_solutions_dirty ();
252
  gcc_unreachable ();
253
}
254
 
255
/* Disconnect edge E from E->dest.  */
256
 
257
static inline void
258
disconnect_dest (edge e)
259
{
260
  basic_block dest = e->dest;
261
  unsigned int dest_idx = e->dest_idx;
262
 
263
  VEC_unordered_remove (edge, dest->preds, dest_idx);
264
 
265
  /* If we removed an edge in the middle of the edge vector, we need
266
     to update dest_idx of the edge that moved into the "hole".  */
267
  if (dest_idx < EDGE_COUNT (dest->preds))
268
    EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
269
  df_mark_solutions_dirty ();
270
}
271
 
272
/* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
273
   created edge.  Use this only if you are sure that this edge can't
274
   possibly already exist.  */
275
 
276
edge
277
unchecked_make_edge (basic_block src, basic_block dst, int flags)
278
{
279
  edge e;
280
  e = ggc_alloc_cleared_edge_def ();
281
  n_edges++;
282
 
283
  e->src = src;
284
  e->dest = dst;
285
  e->flags = flags;
286
 
287
  connect_src (e);
288
  connect_dest (e);
289
 
290
  execute_on_growing_pred (e);
291
  return e;
292
}
293
 
294
/* Create an edge connecting SRC and DST with FLAGS optionally using
295
   edge cache CACHE.  Return the new edge, NULL if already exist.  */
296
 
297
edge
298
cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
299
{
300
  if (edge_cache == NULL
301
      || src == ENTRY_BLOCK_PTR
302
      || dst == EXIT_BLOCK_PTR)
303
    return make_edge (src, dst, flags);
304
 
305
  /* Does the requested edge already exist?  */
306
  if (! TEST_BIT (edge_cache, dst->index))
307
    {
308
      /* The edge does not exist.  Create one and update the
309
         cache.  */
310
      SET_BIT (edge_cache, dst->index);
311
      return unchecked_make_edge (src, dst, flags);
312
    }
313
 
314
  /* At this point, we know that the requested edge exists.  Adjust
315
     flags if necessary.  */
316
  if (flags)
317
    {
318
      edge e = find_edge (src, dst);
319
      e->flags |= flags;
320
    }
321
 
322
  return NULL;
323
}
324
 
325
/* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
326
   created edge or NULL if already exist.  */
327
 
328
edge
329
make_edge (basic_block src, basic_block dest, int flags)
330
{
331
  edge e = find_edge (src, dest);
332
 
333
  /* Make sure we don't add duplicate edges.  */
334
  if (e)
335
    {
336
      e->flags |= flags;
337
      return NULL;
338
    }
339
 
340
  return unchecked_make_edge (src, dest, flags);
341
}
342
 
343
/* Create an edge connecting SRC to DEST and set probability by knowing
344
   that it is the single edge leaving SRC.  */
345
 
346
edge
347
make_single_succ_edge (basic_block src, basic_block dest, int flags)
348
{
349
  edge e = make_edge (src, dest, flags);
350
 
351
  e->probability = REG_BR_PROB_BASE;
352
  e->count = src->count;
353
  return e;
354
}
355
 
356
/* This function will remove an edge from the flow graph.  */
357
 
358
void
359
remove_edge_raw (edge e)
360
{
361
  remove_predictions_associated_with_edge (e);
362
  execute_on_shrinking_pred (e);
363
 
364
  disconnect_src (e);
365
  disconnect_dest (e);
366
 
367
  /* This is probably not needed, but it doesn't hurt.  */
368
  redirect_edge_var_map_clear (e);
369
 
370
  free_edge (e);
371
}
372
 
373
/* Redirect an edge's successor from one block to another.  */
374
 
375
void
376
redirect_edge_succ (edge e, basic_block new_succ)
377
{
378
  execute_on_shrinking_pred (e);
379
 
380
  disconnect_dest (e);
381
 
382
  e->dest = new_succ;
383
 
384
  /* Reconnect the edge to the new successor block.  */
385
  connect_dest (e);
386
 
387
  execute_on_growing_pred (e);
388
}
389
 
390
/* Like previous but avoid possible duplicate edge.  */
391
 
392
edge
393
redirect_edge_succ_nodup (edge e, basic_block new_succ)
394
{
395
  edge s;
396
 
397
  s = find_edge (e->src, new_succ);
398
  if (s && s != e)
399
    {
400
      s->flags |= e->flags;
401
      s->probability += e->probability;
402
      if (s->probability > REG_BR_PROB_BASE)
403
        s->probability = REG_BR_PROB_BASE;
404
      s->count += e->count;
405
      redirect_edge_var_map_dup (s, e);
406
      remove_edge (e);
407
      e = s;
408
    }
409
  else
410
    redirect_edge_succ (e, new_succ);
411
 
412
  return e;
413
}
414
 
415
/* Redirect an edge's predecessor from one block to another.  */
416
 
417
void
418
redirect_edge_pred (edge e, basic_block new_pred)
419
{
420
  disconnect_src (e);
421
 
422
  e->src = new_pred;
423
 
424
  /* Reconnect the edge to the new predecessor block.  */
425
  connect_src (e);
426
}
427
 
428
/* Clear all basic block flags, with the exception of partitioning and
429
   setjmp_target.  */
430
void
431
clear_bb_flags (void)
432
{
433
  basic_block bb;
434
 
435
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
436
    bb->flags = (BB_PARTITION (bb)
437
                 | (bb->flags & (BB_DISABLE_SCHEDULE + BB_RTL + BB_NON_LOCAL_GOTO_TARGET)));
438
}
439
 
440
/* Check the consistency of profile information.  We can't do that
441
   in verify_flow_info, as the counts may get invalid for incompletely
442
   solved graphs, later eliminating of conditionals or roundoff errors.
443
   It is still practical to have them reported for debugging of simple
444
   testcases.  */
445
void
446
check_bb_profile (basic_block bb, FILE * file)
447
{
448
  edge e;
449
  int sum = 0;
450
  gcov_type lsum;
451
  edge_iterator ei;
452
 
453
  if (profile_status == PROFILE_ABSENT)
454
    return;
455
 
456
  if (bb != EXIT_BLOCK_PTR)
457
    {
458
      FOR_EACH_EDGE (e, ei, bb->succs)
459
        sum += e->probability;
460
      if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
461
        fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
462
                 sum * 100.0 / REG_BR_PROB_BASE);
463
      lsum = 0;
464
      FOR_EACH_EDGE (e, ei, bb->succs)
465
        lsum += e->count;
466
      if (EDGE_COUNT (bb->succs)
467
          && (lsum - bb->count > 100 || lsum - bb->count < -100))
468
        fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
469
                 (int) lsum, (int) bb->count);
470
    }
471
  if (bb != ENTRY_BLOCK_PTR)
472
    {
473
      sum = 0;
474
      FOR_EACH_EDGE (e, ei, bb->preds)
475
        sum += EDGE_FREQUENCY (e);
476
      if (abs (sum - bb->frequency) > 100)
477
        fprintf (file,
478
                 "Invalid sum of incoming frequencies %i, should be %i\n",
479
                 sum, bb->frequency);
480
      lsum = 0;
481
      FOR_EACH_EDGE (e, ei, bb->preds)
482
        lsum += e->count;
483
      if (lsum - bb->count > 100 || lsum - bb->count < -100)
484
        fprintf (file, "Invalid sum of incoming counts %i, should be %i\n",
485
                 (int) lsum, (int) bb->count);
486
    }
487
}
488
 
489
/* Write information about registers and basic blocks into FILE.
490
   This is part of making a debugging dump.  */
491
 
492
void
493
dump_regset (regset r, FILE *outf)
494
{
495
  unsigned i;
496
  reg_set_iterator rsi;
497
 
498
  if (r == NULL)
499
    {
500
      fputs (" (nil)", outf);
501
      return;
502
    }
503
 
504
  EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi)
505
    {
506
      fprintf (outf, " %d", i);
507
      if (i < FIRST_PSEUDO_REGISTER)
508
        fprintf (outf, " [%s]",
509
                 reg_names[i]);
510
    }
511
}
512
 
513
/* Print a human-readable representation of R on the standard error
514
   stream.  This function is designed to be used from within the
515
   debugger.  */
516
 
517
DEBUG_FUNCTION void
518
debug_regset (regset r)
519
{
520
  dump_regset (r, stderr);
521
  putc ('\n', stderr);
522
}
523
 
524
/* Emit basic block information for BB.  HEADER is true if the user wants
525
   the generic information and the predecessors, FOOTER is true if they want
526
   the successors.  FLAGS is the dump flags of interest; TDF_DETAILS emit
527
   global register liveness information.  PREFIX is put in front of every
528
   line.  The output is emitted to FILE.  */
529
void
530
dump_bb_info (basic_block bb, bool header, bool footer, int flags,
531
              const char *prefix, FILE *file)
532
{
533
  edge e;
534
  edge_iterator ei;
535
 
536
  if (header)
537
    {
538
      fprintf (file, "\n%sBasic block %d ", prefix, bb->index);
539
      if (bb->prev_bb)
540
        fprintf (file, ", prev %d", bb->prev_bb->index);
541
      if (bb->next_bb)
542
        fprintf (file, ", next %d", bb->next_bb->index);
543
      fprintf (file, ", loop_depth %d, count ", bb->loop_depth);
544
      fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
545
      fprintf (file, ", freq %i", bb->frequency);
546
      /* Both maybe_hot_bb_p & probably_never_executed_bb_p functions
547
         crash without cfun. */
548
      if (cfun && maybe_hot_bb_p (bb))
549
        fputs (", maybe hot", file);
550
      if (cfun && probably_never_executed_bb_p (bb))
551
        fputs (", probably never executed", file);
552
      if (bb->flags)
553
        {
554
          static const char * const bits[] = {
555
            "new", "reachable", "irr_loop", "superblock", "disable_sched",
556
            "hot_partition", "cold_partition", "duplicated",
557
            "non_local_goto_target", "rtl", "forwarder", "nonthreadable",
558
            "modified"
559
          };
560
          unsigned int flags;
561
 
562
          fputs (", flags:", file);
563
          for (flags = bb->flags; flags ; flags &= flags - 1)
564
            {
565
              unsigned i = ctz_hwi (flags);
566
              if (i < ARRAY_SIZE (bits))
567
                fprintf (file, " %s", bits[i]);
568
              else
569
                fprintf (file, " <%d>", i);
570
            }
571
        }
572
      fputs (".\n", file);
573
 
574
      fprintf (file, "%sPredecessors: ", prefix);
575
      FOR_EACH_EDGE (e, ei, bb->preds)
576
        dump_edge_info (file, e, 0);
577
 
578
      if ((flags & TDF_DETAILS)
579
          && (bb->flags & BB_RTL)
580
          && df)
581
        {
582
          putc ('\n', file);
583
          df_dump_top (bb, file);
584
        }
585
   }
586
 
587
  if (footer)
588
    {
589
      fprintf (file, "\n%sSuccessors: ", prefix);
590
      FOR_EACH_EDGE (e, ei, bb->succs)
591
        dump_edge_info (file, e, 1);
592
 
593
      if ((flags & TDF_DETAILS)
594
          && (bb->flags & BB_RTL)
595
          && df)
596
        {
597
          putc ('\n', file);
598
          df_dump_bottom (bb, file);
599
        }
600
   }
601
 
602
  putc ('\n', file);
603
}
604
 
605
/* Dump the register info to FILE.  */
606
 
607
void
608
dump_reg_info (FILE *file)
609
{
610
  unsigned int i, max = max_reg_num ();
611
  if (reload_completed)
612
    return;
613
 
614
  if (reg_info_p_size < max)
615
    max = reg_info_p_size;
616
 
617
  fprintf (file, "%d registers.\n", max);
618
  for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
619
    {
620
      enum reg_class rclass, altclass;
621
 
622
      if (regstat_n_sets_and_refs)
623
        fprintf (file, "\nRegister %d used %d times across %d insns",
624
                 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
625
      else if (df)
626
        fprintf (file, "\nRegister %d used %d times across %d insns",
627
                 i, DF_REG_USE_COUNT (i) + DF_REG_DEF_COUNT (i), REG_LIVE_LENGTH (i));
628
 
629
      if (REG_BASIC_BLOCK (i) >= NUM_FIXED_BLOCKS)
630
        fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
631
      if (regstat_n_sets_and_refs)
632
        fprintf (file, "; set %d time%s", REG_N_SETS (i),
633
                 (REG_N_SETS (i) == 1) ? "" : "s");
634
      else if (df)
635
        fprintf (file, "; set %d time%s", DF_REG_DEF_COUNT (i),
636
                 (DF_REG_DEF_COUNT (i) == 1) ? "" : "s");
637
      if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
638
        fputs ("; user var", file);
639
      if (REG_N_DEATHS (i) != 1)
640
        fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
641
      if (REG_N_CALLS_CROSSED (i) == 1)
642
        fputs ("; crosses 1 call", file);
643
      else if (REG_N_CALLS_CROSSED (i))
644
        fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
645
      if (REG_FREQ_CALLS_CROSSED (i))
646
        fprintf (file, "; crosses call with %d frequency", REG_FREQ_CALLS_CROSSED (i));
647
      if (regno_reg_rtx[i] != NULL
648
          && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
649
        fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
650
 
651
      rclass = reg_preferred_class (i);
652
      altclass = reg_alternate_class (i);
653
      if (rclass != GENERAL_REGS || altclass != ALL_REGS)
654
        {
655
          if (altclass == ALL_REGS || rclass == ALL_REGS)
656
            fprintf (file, "; pref %s", reg_class_names[(int) rclass]);
657
          else if (altclass == NO_REGS)
658
            fprintf (file, "; %s or none", reg_class_names[(int) rclass]);
659
          else
660
            fprintf (file, "; pref %s, else %s",
661
                     reg_class_names[(int) rclass],
662
                     reg_class_names[(int) altclass]);
663
        }
664
 
665
      if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
666
        fputs ("; pointer", file);
667
      fputs (".\n", file);
668
    }
669
}
670
 
671
 
672
void
673
dump_flow_info (FILE *file, int flags)
674
{
675
  basic_block bb;
676
 
677
  /* There are no pseudo registers after reload.  Don't dump them.  */
678
  if (reg_info_p_size && (flags & TDF_DETAILS) != 0)
679
    dump_reg_info (file);
680
 
681
  fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
682
  FOR_ALL_BB (bb)
683
    {
684
      dump_bb_info (bb, true, true, flags, "", file);
685
      check_bb_profile (bb, file);
686
    }
687
 
688
  putc ('\n', file);
689
}
690
 
691
DEBUG_FUNCTION void
692
debug_flow_info (void)
693
{
694
  dump_flow_info (stderr, TDF_DETAILS);
695
}
696
 
697
void
698
dump_edge_info (FILE *file, edge e, int do_succ)
699
{
700
  basic_block side = (do_succ ? e->dest : e->src);
701
  /* both ENTRY_BLOCK_PTR & EXIT_BLOCK_PTR depend upon cfun. */
702
  if (cfun && side == ENTRY_BLOCK_PTR)
703
    fputs (" ENTRY", file);
704
  else if (cfun && side == EXIT_BLOCK_PTR)
705
    fputs (" EXIT", file);
706
  else
707
    fprintf (file, " %d", side->index);
708
 
709
  if (e->probability)
710
    fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
711
 
712
  if (e->count)
713
    {
714
      fputs (" count:", file);
715
      fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
716
    }
717
 
718
  if (e->flags)
719
    {
720
      static const char * const bitnames[] = {
721
        "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
722
        "can_fallthru", "irreducible", "sibcall", "loop_exit",
723
        "true", "false", "exec", "crossing", "preserve"
724
      };
725
      int comma = 0;
726
      int i, flags = e->flags;
727
 
728
      fputs (" (", file);
729
      for (i = 0; flags; i++)
730
        if (flags & (1 << i))
731
          {
732
            flags &= ~(1 << i);
733
 
734
            if (comma)
735
              fputc (',', file);
736
            if (i < (int) ARRAY_SIZE (bitnames))
737
              fputs (bitnames[i], file);
738
            else
739
              fprintf (file, "%d", i);
740
            comma = 1;
741
          }
742
 
743
      fputc (')', file);
744
    }
745
}
746
 
747
/* Simple routines to easily allocate AUX fields of basic blocks.  */
748
 
749
static struct obstack block_aux_obstack;
750
static void *first_block_aux_obj = 0;
751
static struct obstack edge_aux_obstack;
752
static void *first_edge_aux_obj = 0;
753
 
754
/* Allocate a memory block of SIZE as BB->aux.  The obstack must
755
   be first initialized by alloc_aux_for_blocks.  */
756
 
757
static void
758
alloc_aux_for_block (basic_block bb, int size)
759
{
760
  /* Verify that aux field is clear.  */
761
  gcc_assert (!bb->aux && first_block_aux_obj);
762
  bb->aux = obstack_alloc (&block_aux_obstack, size);
763
  memset (bb->aux, 0, size);
764
}
765
 
766
/* Initialize the block_aux_obstack and if SIZE is nonzero, call
767
   alloc_aux_for_block for each basic block.  */
768
 
769
void
770
alloc_aux_for_blocks (int size)
771
{
772
  static int initialized;
773
 
774
  if (!initialized)
775
    {
776
      gcc_obstack_init (&block_aux_obstack);
777
      initialized = 1;
778
    }
779
  else
780
    /* Check whether AUX data are still allocated.  */
781
    gcc_assert (!first_block_aux_obj);
782
 
783
  first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
784
  if (size)
785
    {
786
      basic_block bb;
787
 
788
      FOR_ALL_BB (bb)
789
        alloc_aux_for_block (bb, size);
790
    }
791
}
792
 
793
/* Clear AUX pointers of all blocks.  */
794
 
795
void
796
clear_aux_for_blocks (void)
797
{
798
  basic_block bb;
799
 
800
  FOR_ALL_BB (bb)
801
    bb->aux = NULL;
802
}
803
 
804
/* Free data allocated in block_aux_obstack and clear AUX pointers
805
   of all blocks.  */
806
 
807
void
808
free_aux_for_blocks (void)
809
{
810
  gcc_assert (first_block_aux_obj);
811
  obstack_free (&block_aux_obstack, first_block_aux_obj);
812
  first_block_aux_obj = NULL;
813
 
814
  clear_aux_for_blocks ();
815
}
816
 
817
/* Allocate a memory edge of SIZE as BB->aux.  The obstack must
818
   be first initialized by alloc_aux_for_edges.  */
819
 
820
static void
821
alloc_aux_for_edge (edge e, int size)
822
{
823
  /* Verify that aux field is clear.  */
824
  gcc_assert (!e->aux && first_edge_aux_obj);
825
  e->aux = obstack_alloc (&edge_aux_obstack, size);
826
  memset (e->aux, 0, size);
827
}
828
 
829
/* Initialize the edge_aux_obstack and if SIZE is nonzero, call
830
   alloc_aux_for_edge for each basic edge.  */
831
 
832
void
833
alloc_aux_for_edges (int size)
834
{
835
  static int initialized;
836
 
837
  if (!initialized)
838
    {
839
      gcc_obstack_init (&edge_aux_obstack);
840
      initialized = 1;
841
    }
842
  else
843
    /* Check whether AUX data are still allocated.  */
844
    gcc_assert (!first_edge_aux_obj);
845
 
846
  first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
847
  if (size)
848
    {
849
      basic_block bb;
850
 
851
      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
852
        {
853
          edge e;
854
          edge_iterator ei;
855
 
856
          FOR_EACH_EDGE (e, ei, bb->succs)
857
            alloc_aux_for_edge (e, size);
858
        }
859
    }
860
}
861
 
862
/* Clear AUX pointers of all edges.  */
863
 
864
void
865
clear_aux_for_edges (void)
866
{
867
  basic_block bb;
868
  edge e;
869
 
870
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
871
    {
872
      edge_iterator ei;
873
      FOR_EACH_EDGE (e, ei, bb->succs)
874
        e->aux = NULL;
875
    }
876
}
877
 
878
/* Free data allocated in edge_aux_obstack and clear AUX pointers
879
   of all edges.  */
880
 
881
void
882
free_aux_for_edges (void)
883
{
884
  gcc_assert (first_edge_aux_obj);
885
  obstack_free (&edge_aux_obstack, first_edge_aux_obj);
886
  first_edge_aux_obj = NULL;
887
 
888
  clear_aux_for_edges ();
889
}
890
 
891
DEBUG_FUNCTION void
892
debug_bb (basic_block bb)
893
{
894
  dump_bb (bb, stderr, 0);
895
}
896
 
897
DEBUG_FUNCTION basic_block
898
debug_bb_n (int n)
899
{
900
  basic_block bb = BASIC_BLOCK (n);
901
  dump_bb (bb, stderr, 0);
902
  return bb;
903
}
904
 
905
/* Dumps cfg related information about basic block BB to FILE.  */
906
 
907
static void
908
dump_cfg_bb_info (FILE *file, basic_block bb)
909
{
910
  unsigned i;
911
  edge_iterator ei;
912
  bool first = true;
913
  static const char * const bb_bitnames[] =
914
    {
915
      "new", "reachable", "irreducible_loop", "superblock",
916
      "nosched", "hot", "cold", "dup", "xlabel", "rtl",
917
      "fwdr", "nothrd"
918
    };
919
  const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
920
  edge e;
921
 
922
  fprintf (file, "Basic block %d", bb->index);
923
  for (i = 0; i < n_bitnames; i++)
924
    if (bb->flags & (1 << i))
925
      {
926
        if (first)
927
          fputs (" (", file);
928
        else
929
          fputs (", ", file);
930
        first = false;
931
        fputs (bb_bitnames[i], file);
932
      }
933
  if (!first)
934
    putc (')', file);
935
  putc ('\n', file);
936
 
937
  fputs ("Predecessors: ", file);
938
  FOR_EACH_EDGE (e, ei, bb->preds)
939
    dump_edge_info (file, e, 0);
940
 
941
  fprintf (file, "\nSuccessors: ");
942
  FOR_EACH_EDGE (e, ei, bb->succs)
943
    dump_edge_info (file, e, 1);
944
  fputs ("\n\n", file);
945
}
946
 
947
/* Dumps a brief description of cfg to FILE.  */
948
 
949
void
950
brief_dump_cfg (FILE *file)
951
{
952
  basic_block bb;
953
 
954
  FOR_EACH_BB (bb)
955
    {
956
      dump_cfg_bb_info (file, bb);
957
    }
958
}
959
 
960
/* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
961
   leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
962
   redirected to destination of TAKEN_EDGE.
963
 
964
   This function may leave the profile inconsistent in the case TAKEN_EDGE
965
   frequency or count is believed to be lower than FREQUENCY or COUNT
966
   respectively.  */
967
void
968
update_bb_profile_for_threading (basic_block bb, int edge_frequency,
969
                                 gcov_type count, edge taken_edge)
970
{
971
  edge c;
972
  int prob;
973
  edge_iterator ei;
974
 
975
  bb->count -= count;
976
  if (bb->count < 0)
977
    {
978
      if (dump_file)
979
        fprintf (dump_file, "bb %i count became negative after threading",
980
                 bb->index);
981
      bb->count = 0;
982
    }
983
 
984
  /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
985
     Watch for overflows.  */
986
  if (bb->frequency)
987
    prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
988
  else
989
    prob = 0;
990
  if (prob > taken_edge->probability)
991
    {
992
      if (dump_file)
993
        fprintf (dump_file, "Jump threading proved probability of edge "
994
                 "%i->%i too small (it is %i, should be %i).\n",
995
                 taken_edge->src->index, taken_edge->dest->index,
996
                 taken_edge->probability, prob);
997
      prob = taken_edge->probability;
998
    }
999
 
1000
  /* Now rescale the probabilities.  */
1001
  taken_edge->probability -= prob;
1002
  prob = REG_BR_PROB_BASE - prob;
1003
  bb->frequency -= edge_frequency;
1004
  if (bb->frequency < 0)
1005
    bb->frequency = 0;
1006
  if (prob <= 0)
1007
    {
1008
      if (dump_file)
1009
        fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
1010
                 "frequency of block should end up being 0, it is %i\n",
1011
                 bb->index, bb->frequency);
1012
      EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
1013
      ei = ei_start (bb->succs);
1014
      ei_next (&ei);
1015
      for (; (c = ei_safe_edge (ei)); ei_next (&ei))
1016
        c->probability = 0;
1017
    }
1018
  else if (prob != REG_BR_PROB_BASE)
1019
    {
1020
      int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
1021
 
1022
      FOR_EACH_EDGE (c, ei, bb->succs)
1023
        {
1024
          /* Protect from overflow due to additional scaling.  */
1025
          if (c->probability > prob)
1026
            c->probability = REG_BR_PROB_BASE;
1027
          else
1028
            {
1029
              c->probability = RDIV (c->probability * scale, 65536);
1030
              if (c->probability > REG_BR_PROB_BASE)
1031
                c->probability = REG_BR_PROB_BASE;
1032
            }
1033
        }
1034
    }
1035
 
1036
  gcc_assert (bb == taken_edge->src);
1037
  taken_edge->count -= count;
1038
  if (taken_edge->count < 0)
1039
    {
1040
      if (dump_file)
1041
        fprintf (dump_file, "edge %i->%i count became negative after threading",
1042
                 taken_edge->src->index, taken_edge->dest->index);
1043
      taken_edge->count = 0;
1044
    }
1045
}
1046
 
1047
/* Multiply all frequencies of basic blocks in array BBS of length NBBS
1048
   by NUM/DEN, in int arithmetic.  May lose some accuracy.  */
1049
void
1050
scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
1051
{
1052
  int i;
1053
  edge e;
1054
  if (num < 0)
1055
    num = 0;
1056
 
1057
  /* Scale NUM and DEN to avoid overflows.  Frequencies are in order of
1058
     10^4, if we make DEN <= 10^3, we can afford to upscale by 100
1059
     and still safely fit in int during calculations.  */
1060
  if (den > 1000)
1061
    {
1062
      if (num > 1000000)
1063
        return;
1064
 
1065
      num = RDIV (1000 * num, den);
1066
      den = 1000;
1067
    }
1068
  if (num > 100 * den)
1069
    return;
1070
 
1071
  for (i = 0; i < nbbs; i++)
1072
    {
1073
      edge_iterator ei;
1074
      bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1075
      /* Make sure the frequencies do not grow over BB_FREQ_MAX.  */
1076
      if (bbs[i]->frequency > BB_FREQ_MAX)
1077
        bbs[i]->frequency = BB_FREQ_MAX;
1078
      bbs[i]->count = RDIV (bbs[i]->count * num, den);
1079
      FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1080
        e->count = RDIV (e->count * num, den);
1081
    }
1082
}
1083
 
1084
/* numbers smaller than this value are safe to multiply without getting
1085
   64bit overflow.  */
1086
#define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
1087
 
1088
/* Multiply all frequencies of basic blocks in array BBS of length NBBS
1089
   by NUM/DEN, in gcov_type arithmetic.  More accurate than previous
1090
   function but considerably slower.  */
1091
void
1092
scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
1093
                                 gcov_type den)
1094
{
1095
  int i;
1096
  edge e;
1097
  gcov_type fraction = RDIV (num * 65536, den);
1098
 
1099
  gcc_assert (fraction >= 0);
1100
 
1101
  if (num < MAX_SAFE_MULTIPLIER)
1102
    for (i = 0; i < nbbs; i++)
1103
      {
1104
        edge_iterator ei;
1105
        bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1106
        if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1107
          bbs[i]->count = RDIV (bbs[i]->count * num, den);
1108
        else
1109
          bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1110
        FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1111
          if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1112
            e->count = RDIV (e->count * num, den);
1113
          else
1114
            e->count = RDIV (e->count * fraction, 65536);
1115
      }
1116
   else
1117
    for (i = 0; i < nbbs; i++)
1118
      {
1119
        edge_iterator ei;
1120
        if (sizeof (gcov_type) > sizeof (int))
1121
          bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1122
        else
1123
          bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
1124
        bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1125
        FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1126
          e->count = RDIV (e->count * fraction, 65536);
1127
      }
1128
}
1129
 
1130
/* Data structures used to maintain mapping between basic blocks and
1131
   copies.  */
1132
static htab_t bb_original;
1133
static htab_t bb_copy;
1134
 
1135
/* And between loops and copies.  */
1136
static htab_t loop_copy;
1137
static alloc_pool original_copy_bb_pool;
1138
 
1139
struct htab_bb_copy_original_entry
1140
{
1141
  /* Block we are attaching info to.  */
1142
  int index1;
1143
  /* Index of original or copy (depending on the hashtable) */
1144
  int index2;
1145
};
1146
 
1147
static hashval_t
1148
bb_copy_original_hash (const void *p)
1149
{
1150
  const struct htab_bb_copy_original_entry *data
1151
    = ((const struct htab_bb_copy_original_entry *)p);
1152
 
1153
  return data->index1;
1154
}
1155
static int
1156
bb_copy_original_eq (const void *p, const void *q)
1157
{
1158
  const struct htab_bb_copy_original_entry *data
1159
    = ((const struct htab_bb_copy_original_entry *)p);
1160
  const struct htab_bb_copy_original_entry *data2
1161
    = ((const struct htab_bb_copy_original_entry *)q);
1162
 
1163
  return data->index1 == data2->index1;
1164
}
1165
 
1166
/* Initialize the data structures to maintain mapping between blocks
1167
   and its copies.  */
1168
void
1169
initialize_original_copy_tables (void)
1170
{
1171
  gcc_assert (!original_copy_bb_pool);
1172
  original_copy_bb_pool
1173
    = create_alloc_pool ("original_copy",
1174
                         sizeof (struct htab_bb_copy_original_entry), 10);
1175
  bb_original = htab_create (10, bb_copy_original_hash,
1176
                             bb_copy_original_eq, NULL);
1177
  bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1178
  loop_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1179
}
1180
 
1181
/* Free the data structures to maintain mapping between blocks and
1182
   its copies.  */
1183
void
1184
free_original_copy_tables (void)
1185
{
1186
  gcc_assert (original_copy_bb_pool);
1187
  htab_delete (bb_copy);
1188
  htab_delete (bb_original);
1189
  htab_delete (loop_copy);
1190
  free_alloc_pool (original_copy_bb_pool);
1191
  bb_copy = NULL;
1192
  bb_original = NULL;
1193
  loop_copy = NULL;
1194
  original_copy_bb_pool = NULL;
1195
}
1196
 
1197
/* Removes the value associated with OBJ from table TAB.  */
1198
 
1199
static void
1200
copy_original_table_clear (htab_t tab, unsigned obj)
1201
{
1202
  void **slot;
1203
  struct htab_bb_copy_original_entry key, *elt;
1204
 
1205
  if (!original_copy_bb_pool)
1206
    return;
1207
 
1208
  key.index1 = obj;
1209
  slot = htab_find_slot (tab, &key, NO_INSERT);
1210
  if (!slot)
1211
    return;
1212
 
1213
  elt = (struct htab_bb_copy_original_entry *) *slot;
1214
  htab_clear_slot (tab, slot);
1215
  pool_free (original_copy_bb_pool, elt);
1216
}
1217
 
1218
/* Sets the value associated with OBJ in table TAB to VAL.
1219
   Do nothing when data structures are not initialized.  */
1220
 
1221
static void
1222
copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
1223
{
1224
  struct htab_bb_copy_original_entry **slot;
1225
  struct htab_bb_copy_original_entry key;
1226
 
1227
  if (!original_copy_bb_pool)
1228
    return;
1229
 
1230
  key.index1 = obj;
1231
  slot = (struct htab_bb_copy_original_entry **)
1232
                htab_find_slot (tab, &key, INSERT);
1233
  if (!*slot)
1234
    {
1235
      *slot = (struct htab_bb_copy_original_entry *)
1236
                pool_alloc (original_copy_bb_pool);
1237
      (*slot)->index1 = obj;
1238
    }
1239
  (*slot)->index2 = val;
1240
}
1241
 
1242
/* Set original for basic block.  Do nothing when data structures are not
1243
   initialized so passes not needing this don't need to care.  */
1244
void
1245
set_bb_original (basic_block bb, basic_block original)
1246
{
1247
  copy_original_table_set (bb_original, bb->index, original->index);
1248
}
1249
 
1250
/* Get the original basic block.  */
1251
basic_block
1252
get_bb_original (basic_block bb)
1253
{
1254
  struct htab_bb_copy_original_entry *entry;
1255
  struct htab_bb_copy_original_entry key;
1256
 
1257
  gcc_assert (original_copy_bb_pool);
1258
 
1259
  key.index1 = bb->index;
1260
  entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
1261
  if (entry)
1262
    return BASIC_BLOCK (entry->index2);
1263
  else
1264
    return NULL;
1265
}
1266
 
1267
/* Set copy for basic block.  Do nothing when data structures are not
1268
   initialized so passes not needing this don't need to care.  */
1269
void
1270
set_bb_copy (basic_block bb, basic_block copy)
1271
{
1272
  copy_original_table_set (bb_copy, bb->index, copy->index);
1273
}
1274
 
1275
/* Get the copy of basic block.  */
1276
basic_block
1277
get_bb_copy (basic_block bb)
1278
{
1279
  struct htab_bb_copy_original_entry *entry;
1280
  struct htab_bb_copy_original_entry key;
1281
 
1282
  gcc_assert (original_copy_bb_pool);
1283
 
1284
  key.index1 = bb->index;
1285
  entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
1286
  if (entry)
1287
    return BASIC_BLOCK (entry->index2);
1288
  else
1289
    return NULL;
1290
}
1291
 
1292
/* Set copy for LOOP to COPY.  Do nothing when data structures are not
1293
   initialized so passes not needing this don't need to care.  */
1294
 
1295
void
1296
set_loop_copy (struct loop *loop, struct loop *copy)
1297
{
1298
  if (!copy)
1299
    copy_original_table_clear (loop_copy, loop->num);
1300
  else
1301
    copy_original_table_set (loop_copy, loop->num, copy->num);
1302
}
1303
 
1304
/* Get the copy of LOOP.  */
1305
 
1306
struct loop *
1307
get_loop_copy (struct loop *loop)
1308
{
1309
  struct htab_bb_copy_original_entry *entry;
1310
  struct htab_bb_copy_original_entry key;
1311
 
1312
  gcc_assert (original_copy_bb_pool);
1313
 
1314
  key.index1 = loop->num;
1315
  entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
1316
  if (entry)
1317
    return get_loop (entry->index2);
1318
  else
1319
    return NULL;
1320
}

powered by: WebSVN 2.1.0

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