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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.2.2/] [gcc/] [cfg.c] - Blame information for rev 193

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

Line No. Rev Author Line
1 38 julius
/* 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, 2007
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 "toplev.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
 
69
/* The obstack on which the flow graph components are allocated.  */
70
 
71
struct bitmap_obstack reg_obstack;
72
 
73
void debug_flow_info (void);
74
static void free_edge (edge);
75
 
76
#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
77
 
78
/* Called once at initialization time.  */
79
 
80
void
81
init_flow (void)
82
{
83
  if (!cfun->cfg)
84
    cfun->cfg = ggc_alloc_cleared (sizeof (struct control_flow_graph));
85
  n_edges = 0;
86
  ENTRY_BLOCK_PTR = ggc_alloc_cleared (sizeof (struct basic_block_def));
87
  ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
88
  EXIT_BLOCK_PTR = ggc_alloc_cleared (sizeof (struct basic_block_def));
89
  EXIT_BLOCK_PTR->index = EXIT_BLOCK;
90
  ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
91
  EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
92
}
93
 
94
/* Helper function for remove_edge and clear_edges.  Frees edge structure
95
   without actually unlinking it from the pred/succ lists.  */
96
 
97
static void
98
free_edge (edge e ATTRIBUTE_UNUSED)
99
{
100
  n_edges--;
101
  ggc_free (e);
102
}
103
 
104
/* Free the memory associated with the edge structures.  */
105
 
106
void
107
clear_edges (void)
108
{
109
  basic_block bb;
110
  edge e;
111
  edge_iterator ei;
112
 
113
  FOR_EACH_BB (bb)
114
    {
115
      FOR_EACH_EDGE (e, ei, bb->succs)
116
        free_edge (e);
117
      VEC_truncate (edge, bb->succs, 0);
118
      VEC_truncate (edge, bb->preds, 0);
119
    }
120
 
121
  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
122
    free_edge (e);
123
  VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0);
124
  VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0);
125
 
126
  gcc_assert (!n_edges);
127
}
128
 
129
/* Allocate memory for basic_block.  */
130
 
131
basic_block
132
alloc_block (void)
133
{
134
  basic_block bb;
135
  bb = ggc_alloc_cleared (sizeof (*bb));
136
  return bb;
137
}
138
 
139
/* Link block B to chain after AFTER.  */
140
void
141
link_block (basic_block b, basic_block after)
142
{
143
  b->next_bb = after->next_bb;
144
  b->prev_bb = after;
145
  after->next_bb = b;
146
  b->next_bb->prev_bb = b;
147
}
148
 
149
/* Unlink block B from chain.  */
150
void
151
unlink_block (basic_block b)
152
{
153
  b->next_bb->prev_bb = b->prev_bb;
154
  b->prev_bb->next_bb = b->next_bb;
155
  b->prev_bb = NULL;
156
  b->next_bb = NULL;
157
}
158
 
159
/* Sequentially order blocks and compact the arrays.  */
160
void
161
compact_blocks (void)
162
{
163
  int i;
164
  basic_block bb;
165
 
166
  SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
167
  SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
168
 
169
  i = NUM_FIXED_BLOCKS;
170
  FOR_EACH_BB (bb)
171
    {
172
      SET_BASIC_BLOCK (i, bb);
173
      bb->index = i;
174
      i++;
175
    }
176
 
177
  gcc_assert (i == n_basic_blocks);
178
 
179
  for (; i < last_basic_block; i++)
180
    SET_BASIC_BLOCK (i, NULL);
181
 
182
  last_basic_block = n_basic_blocks;
183
}
184
 
185
/* Remove block B from the basic block array.  */
186
 
187
void
188
expunge_block (basic_block b)
189
{
190
  unlink_block (b);
191
  SET_BASIC_BLOCK (b->index, NULL);
192
  n_basic_blocks--;
193
  /* We should be able to ggc_free here, but we are not.
194
     The dead SSA_NAMES are left pointing to dead statements that are pointing
195
     to dead basic blocks making garbage collector to die.
196
     We should be able to release all dead SSA_NAMES and at the same time we should
197
     clear out BB pointer of dead statements consistently.  */
198
}
199
 
200
/* Connect E to E->src.  */
201
 
202
static inline void
203
connect_src (edge e)
204
{
205
  VEC_safe_push (edge, gc, e->src->succs, e);
206
}
207
 
208
/* Connect E to E->dest.  */
209
 
210
static inline void
211
connect_dest (edge e)
212
{
213
  basic_block dest = e->dest;
214
  VEC_safe_push (edge, gc, dest->preds, e);
215
  e->dest_idx = EDGE_COUNT (dest->preds) - 1;
216
}
217
 
218
/* Disconnect edge E from E->src.  */
219
 
220
static inline void
221
disconnect_src (edge e)
222
{
223
  basic_block src = e->src;
224
  edge_iterator ei;
225
  edge tmp;
226
 
227
  for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
228
    {
229
      if (tmp == e)
230
        {
231
          VEC_unordered_remove (edge, src->succs, ei.index);
232
          return;
233
        }
234
      else
235
        ei_next (&ei);
236
    }
237
 
238
  gcc_unreachable ();
239
}
240
 
241
/* Disconnect edge E from E->dest.  */
242
 
243
static inline void
244
disconnect_dest (edge e)
245
{
246
  basic_block dest = e->dest;
247
  unsigned int dest_idx = e->dest_idx;
248
 
249
  VEC_unordered_remove (edge, dest->preds, dest_idx);
250
 
251
  /* If we removed an edge in the middle of the edge vector, we need
252
     to update dest_idx of the edge that moved into the "hole".  */
253
  if (dest_idx < EDGE_COUNT (dest->preds))
254
    EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
255
}
256
 
257
/* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
258
   created edge.  Use this only if you are sure that this edge can't
259
   possibly already exist.  */
260
 
261
edge
262
unchecked_make_edge (basic_block src, basic_block dst, int flags)
263
{
264
  edge e;
265
  e = ggc_alloc_cleared (sizeof (*e));
266
  n_edges++;
267
 
268
  e->src = src;
269
  e->dest = dst;
270
  e->flags = flags;
271
 
272
  connect_src (e);
273
  connect_dest (e);
274
 
275
  execute_on_growing_pred (e);
276
 
277
  return e;
278
}
279
 
280
/* Create an edge connecting SRC and DST with FLAGS optionally using
281
   edge cache CACHE.  Return the new edge, NULL if already exist.  */
282
 
283
edge
284
cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
285
{
286
  if (edge_cache == NULL
287
      || src == ENTRY_BLOCK_PTR
288
      || dst == EXIT_BLOCK_PTR)
289
    return make_edge (src, dst, flags);
290
 
291
  /* Does the requested edge already exist?  */
292
  if (! TEST_BIT (edge_cache, dst->index))
293
    {
294
      /* The edge does not exist.  Create one and update the
295
         cache.  */
296
      SET_BIT (edge_cache, dst->index);
297
      return unchecked_make_edge (src, dst, flags);
298
    }
299
 
300
  /* At this point, we know that the requested edge exists.  Adjust
301
     flags if necessary.  */
302
  if (flags)
303
    {
304
      edge e = find_edge (src, dst);
305
      e->flags |= flags;
306
    }
307
 
308
  return NULL;
309
}
310
 
311
/* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
312
   created edge or NULL if already exist.  */
313
 
314
edge
315
make_edge (basic_block src, basic_block dest, int flags)
316
{
317
  edge e = find_edge (src, dest);
318
 
319
  /* Make sure we don't add duplicate edges.  */
320
  if (e)
321
    {
322
      e->flags |= flags;
323
      return NULL;
324
    }
325
 
326
  return unchecked_make_edge (src, dest, flags);
327
}
328
 
329
/* Create an edge connecting SRC to DEST and set probability by knowing
330
   that it is the single edge leaving SRC.  */
331
 
332
edge
333
make_single_succ_edge (basic_block src, basic_block dest, int flags)
334
{
335
  edge e = make_edge (src, dest, flags);
336
 
337
  e->probability = REG_BR_PROB_BASE;
338
  e->count = src->count;
339
  return e;
340
}
341
 
342
/* This function will remove an edge from the flow graph.  */
343
 
344
void
345
remove_edge (edge e)
346
{
347
  remove_predictions_associated_with_edge (e);
348
  execute_on_shrinking_pred (e);
349
 
350
  disconnect_src (e);
351
  disconnect_dest (e);
352
 
353
  free_edge (e);
354
}
355
 
356
/* Redirect an edge's successor from one block to another.  */
357
 
358
void
359
redirect_edge_succ (edge e, basic_block new_succ)
360
{
361
  execute_on_shrinking_pred (e);
362
 
363
  disconnect_dest (e);
364
 
365
  e->dest = new_succ;
366
 
367
  /* Reconnect the edge to the new successor block.  */
368
  connect_dest (e);
369
 
370
  execute_on_growing_pred (e);
371
}
372
 
373
/* Like previous but avoid possible duplicate edge.  */
374
 
375
edge
376
redirect_edge_succ_nodup (edge e, basic_block new_succ)
377
{
378
  edge s;
379
 
380
  s = find_edge (e->src, new_succ);
381
  if (s && s != e)
382
    {
383
      s->flags |= e->flags;
384
      s->probability += e->probability;
385
      if (s->probability > REG_BR_PROB_BASE)
386
        s->probability = REG_BR_PROB_BASE;
387
      s->count += e->count;
388
      remove_edge (e);
389
      e = s;
390
    }
391
  else
392
    redirect_edge_succ (e, new_succ);
393
 
394
  return e;
395
}
396
 
397
/* Redirect an edge's predecessor from one block to another.  */
398
 
399
void
400
redirect_edge_pred (edge e, basic_block new_pred)
401
{
402
  disconnect_src (e);
403
 
404
  e->src = new_pred;
405
 
406
  /* Reconnect the edge to the new predecessor block.  */
407
  connect_src (e);
408
}
409
 
410
/* Clear all basic block flags, with the exception of partitioning.  */
411
void
412
clear_bb_flags (void)
413
{
414
  basic_block bb;
415
 
416
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
417
    bb->flags = (BB_PARTITION (bb)  | (bb->flags & BB_DISABLE_SCHEDULE)
418
                 | (bb->flags & BB_RTL));
419
}
420
 
421
/* Check the consistency of profile information.  We can't do that
422
   in verify_flow_info, as the counts may get invalid for incompletely
423
   solved graphs, later eliminating of conditionals or roundoff errors.
424
   It is still practical to have them reported for debugging of simple
425
   testcases.  */
426
void
427
check_bb_profile (basic_block bb, FILE * file)
428
{
429
  edge e;
430
  int sum = 0;
431
  gcov_type lsum;
432
  edge_iterator ei;
433
 
434
  if (profile_status == PROFILE_ABSENT)
435
    return;
436
 
437
  if (bb != EXIT_BLOCK_PTR)
438
    {
439
      FOR_EACH_EDGE (e, ei, bb->succs)
440
        sum += e->probability;
441
      if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
442
        fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
443
                 sum * 100.0 / REG_BR_PROB_BASE);
444
      lsum = 0;
445
      FOR_EACH_EDGE (e, ei, bb->succs)
446
        lsum += e->count;
447
      if (EDGE_COUNT (bb->succs)
448
          && (lsum - bb->count > 100 || lsum - bb->count < -100))
449
        fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
450
                 (int) lsum, (int) bb->count);
451
    }
452
  if (bb != ENTRY_BLOCK_PTR)
453
    {
454
      sum = 0;
455
      FOR_EACH_EDGE (e, ei, bb->preds)
456
        sum += EDGE_FREQUENCY (e);
457
      if (abs (sum - bb->frequency) > 100)
458
        fprintf (file,
459
                 "Invalid sum of incoming frequencies %i, should be %i\n",
460
                 sum, bb->frequency);
461
      lsum = 0;
462
      FOR_EACH_EDGE (e, ei, bb->preds)
463
        lsum += e->count;
464
      if (lsum - bb->count > 100 || lsum - bb->count < -100)
465
        fprintf (file, "Invalid sum of incoming counts %i, should be %i\n",
466
                 (int) lsum, (int) bb->count);
467
    }
468
}
469
 
470
/* Emit basic block information for BB.  HEADER is true if the user wants
471
   the generic information and the predecessors, FOOTER is true if they want
472
   the successors.  FLAGS is the dump flags of interest; TDF_DETAILS emit
473
   global register liveness information.  PREFIX is put in front of every
474
   line.  The output is emitted to FILE.  */
475
void
476
dump_bb_info (basic_block bb, bool header, bool footer, int flags,
477
              const char *prefix, FILE *file)
478
{
479
  edge e;
480
  edge_iterator ei;
481
 
482
  if (header)
483
    {
484
      fprintf (file, "\n%sBasic block %d ", prefix, bb->index);
485
      if (bb->prev_bb)
486
        fprintf (file, ", prev %d", bb->prev_bb->index);
487
      if (bb->next_bb)
488
        fprintf (file, ", next %d", bb->next_bb->index);
489
      fprintf (file, ", loop_depth %d, count ", bb->loop_depth);
490
      fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
491
      fprintf (file, ", freq %i", bb->frequency);
492
      if (maybe_hot_bb_p (bb))
493
        fprintf (file, ", maybe hot");
494
      if (probably_never_executed_bb_p (bb))
495
        fprintf (file, ", probably never executed");
496
      fprintf (file, ".\n");
497
 
498
      fprintf (file, "%sPredecessors: ", prefix);
499
      FOR_EACH_EDGE (e, ei, bb->preds)
500
        dump_edge_info (file, e, 0);
501
   }
502
 
503
  if (footer)
504
    {
505
      fprintf (file, "\n%sSuccessors: ", prefix);
506
      FOR_EACH_EDGE (e, ei, bb->succs)
507
        dump_edge_info (file, e, 1);
508
   }
509
 
510
  if ((flags & TDF_DETAILS)
511
      && (bb->flags & BB_RTL))
512
    {
513
      if (bb->il.rtl->global_live_at_start && header)
514
        {
515
          fprintf (file, "\n%sRegisters live at start:", prefix);
516
          dump_regset (bb->il.rtl->global_live_at_start, file);
517
        }
518
 
519
      if (bb->il.rtl->global_live_at_end && footer)
520
        {
521
          fprintf (file, "\n%sRegisters live at end:", prefix);
522
          dump_regset (bb->il.rtl->global_live_at_end, file);
523
        }
524
   }
525
 
526
  putc ('\n', file);
527
}
528
 
529
void
530
dump_flow_info (FILE *file, int flags)
531
{
532
  basic_block bb;
533
 
534
  /* There are no pseudo registers after reload.  Don't dump them.  */
535
  if (reg_n_info && !reload_completed
536
      && (flags & TDF_DETAILS) != 0)
537
    {
538
      unsigned int i, max = max_reg_num ();
539
      fprintf (file, "%d registers.\n", max);
540
      for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
541
        if (REG_N_REFS (i))
542
          {
543
            enum reg_class class, altclass;
544
 
545
            fprintf (file, "\nRegister %d used %d times across %d insns",
546
                     i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
547
            if (REG_BASIC_BLOCK (i) >= 0)
548
              fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
549
            if (REG_N_SETS (i))
550
              fprintf (file, "; set %d time%s", REG_N_SETS (i),
551
                       (REG_N_SETS (i) == 1) ? "" : "s");
552
            if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
553
              fprintf (file, "; user var");
554
            if (REG_N_DEATHS (i) != 1)
555
              fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
556
            if (REG_N_CALLS_CROSSED (i) == 1)
557
              fprintf (file, "; crosses 1 call");
558
            else if (REG_N_CALLS_CROSSED (i))
559
              fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
560
            if (regno_reg_rtx[i] != NULL
561
                && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
562
              fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
563
 
564
            class = reg_preferred_class (i);
565
            altclass = reg_alternate_class (i);
566
            if (class != GENERAL_REGS || altclass != ALL_REGS)
567
              {
568
                if (altclass == ALL_REGS || class == ALL_REGS)
569
                  fprintf (file, "; pref %s", reg_class_names[(int) class]);
570
                else if (altclass == NO_REGS)
571
                  fprintf (file, "; %s or none", reg_class_names[(int) class]);
572
                else
573
                  fprintf (file, "; pref %s, else %s",
574
                           reg_class_names[(int) class],
575
                           reg_class_names[(int) altclass]);
576
              }
577
 
578
            if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
579
              fprintf (file, "; pointer");
580
            fprintf (file, ".\n");
581
          }
582
    }
583
 
584
  fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
585
  FOR_EACH_BB (bb)
586
    {
587
      dump_bb_info (bb, true, true, flags, "", file);
588
      check_bb_profile (bb, file);
589
    }
590
 
591
  putc ('\n', file);
592
}
593
 
594
void
595
debug_flow_info (void)
596
{
597
  dump_flow_info (stderr, TDF_DETAILS);
598
}
599
 
600
void
601
dump_edge_info (FILE *file, edge e, int do_succ)
602
{
603
  basic_block side = (do_succ ? e->dest : e->src);
604
 
605
  if (side == ENTRY_BLOCK_PTR)
606
    fputs (" ENTRY", file);
607
  else if (side == EXIT_BLOCK_PTR)
608
    fputs (" EXIT", file);
609
  else
610
    fprintf (file, " %d", side->index);
611
 
612
  if (e->probability)
613
    fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
614
 
615
  if (e->count)
616
    {
617
      fprintf (file, " count:");
618
      fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
619
    }
620
 
621
  if (e->flags)
622
    {
623
      static const char * const bitnames[] = {
624
        "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
625
        "can_fallthru", "irreducible", "sibcall", "loop_exit",
626
        "true", "false", "exec"
627
      };
628
      int comma = 0;
629
      int i, flags = e->flags;
630
 
631
      fputs (" (", file);
632
      for (i = 0; flags; i++)
633
        if (flags & (1 << i))
634
          {
635
            flags &= ~(1 << i);
636
 
637
            if (comma)
638
              fputc (',', file);
639
            if (i < (int) ARRAY_SIZE (bitnames))
640
              fputs (bitnames[i], file);
641
            else
642
              fprintf (file, "%d", i);
643
            comma = 1;
644
          }
645
 
646
      fputc (')', file);
647
    }
648
}
649
 
650
/* Simple routines to easily allocate AUX fields of basic blocks.  */
651
 
652
static struct obstack block_aux_obstack;
653
static void *first_block_aux_obj = 0;
654
static struct obstack edge_aux_obstack;
655
static void *first_edge_aux_obj = 0;
656
 
657
/* Allocate a memory block of SIZE as BB->aux.  The obstack must
658
   be first initialized by alloc_aux_for_blocks.  */
659
 
660
inline void
661
alloc_aux_for_block (basic_block bb, int size)
662
{
663
  /* Verify that aux field is clear.  */
664
  gcc_assert (!bb->aux && first_block_aux_obj);
665
  bb->aux = obstack_alloc (&block_aux_obstack, size);
666
  memset (bb->aux, 0, size);
667
}
668
 
669
/* Initialize the block_aux_obstack and if SIZE is nonzero, call
670
   alloc_aux_for_block for each basic block.  */
671
 
672
void
673
alloc_aux_for_blocks (int size)
674
{
675
  static int initialized;
676
 
677
  if (!initialized)
678
    {
679
      gcc_obstack_init (&block_aux_obstack);
680
      initialized = 1;
681
    }
682
  else
683
    /* Check whether AUX data are still allocated.  */
684
    gcc_assert (!first_block_aux_obj);
685
 
686
  first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
687
  if (size)
688
    {
689
      basic_block bb;
690
 
691
      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
692
        alloc_aux_for_block (bb, size);
693
    }
694
}
695
 
696
/* Clear AUX pointers of all blocks.  */
697
 
698
void
699
clear_aux_for_blocks (void)
700
{
701
  basic_block bb;
702
 
703
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
704
    bb->aux = NULL;
705
}
706
 
707
/* Free data allocated in block_aux_obstack and clear AUX pointers
708
   of all blocks.  */
709
 
710
void
711
free_aux_for_blocks (void)
712
{
713
  gcc_assert (first_block_aux_obj);
714
  obstack_free (&block_aux_obstack, first_block_aux_obj);
715
  first_block_aux_obj = NULL;
716
 
717
  clear_aux_for_blocks ();
718
}
719
 
720
/* Allocate a memory edge of SIZE as BB->aux.  The obstack must
721
   be first initialized by alloc_aux_for_edges.  */
722
 
723
inline void
724
alloc_aux_for_edge (edge e, int size)
725
{
726
  /* Verify that aux field is clear.  */
727
  gcc_assert (!e->aux && first_edge_aux_obj);
728
  e->aux = obstack_alloc (&edge_aux_obstack, size);
729
  memset (e->aux, 0, size);
730
}
731
 
732
/* Initialize the edge_aux_obstack and if SIZE is nonzero, call
733
   alloc_aux_for_edge for each basic edge.  */
734
 
735
void
736
alloc_aux_for_edges (int size)
737
{
738
  static int initialized;
739
 
740
  if (!initialized)
741
    {
742
      gcc_obstack_init (&edge_aux_obstack);
743
      initialized = 1;
744
    }
745
  else
746
    /* Check whether AUX data are still allocated.  */
747
    gcc_assert (!first_edge_aux_obj);
748
 
749
  first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
750
  if (size)
751
    {
752
      basic_block bb;
753
 
754
      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
755
        {
756
          edge e;
757
          edge_iterator ei;
758
 
759
          FOR_EACH_EDGE (e, ei, bb->succs)
760
            alloc_aux_for_edge (e, size);
761
        }
762
    }
763
}
764
 
765
/* Clear AUX pointers of all edges.  */
766
 
767
void
768
clear_aux_for_edges (void)
769
{
770
  basic_block bb;
771
  edge e;
772
 
773
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
774
    {
775
      edge_iterator ei;
776
      FOR_EACH_EDGE (e, ei, bb->succs)
777
        e->aux = NULL;
778
    }
779
}
780
 
781
/* Free data allocated in edge_aux_obstack and clear AUX pointers
782
   of all edges.  */
783
 
784
void
785
free_aux_for_edges (void)
786
{
787
  gcc_assert (first_edge_aux_obj);
788
  obstack_free (&edge_aux_obstack, first_edge_aux_obj);
789
  first_edge_aux_obj = NULL;
790
 
791
  clear_aux_for_edges ();
792
}
793
 
794
void
795
debug_bb (basic_block bb)
796
{
797
  dump_bb (bb, stderr, 0);
798
}
799
 
800
basic_block
801
debug_bb_n (int n)
802
{
803
  basic_block bb = BASIC_BLOCK (n);
804
  dump_bb (bb, stderr, 0);
805
  return bb;
806
}
807
 
808
/* Dumps cfg related information about basic block BB to FILE.  */
809
 
810
static void
811
dump_cfg_bb_info (FILE *file, basic_block bb)
812
{
813
  unsigned i;
814
  edge_iterator ei;
815
  bool first = true;
816
  static const char * const bb_bitnames[] =
817
    {
818
      "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
819
    };
820
  const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
821
  edge e;
822
 
823
  fprintf (file, "Basic block %d", bb->index);
824
  for (i = 0; i < n_bitnames; i++)
825
    if (bb->flags & (1 << i))
826
      {
827
        if (first)
828
          fprintf (file, " (");
829
        else
830
          fprintf (file, ", ");
831
        first = false;
832
        fprintf (file, bb_bitnames[i]);
833
      }
834
  if (!first)
835
    fprintf (file, ")");
836
  fprintf (file, "\n");
837
 
838
  fprintf (file, "Predecessors: ");
839
  FOR_EACH_EDGE (e, ei, bb->preds)
840
    dump_edge_info (file, e, 0);
841
 
842
  fprintf (file, "\nSuccessors: ");
843
  FOR_EACH_EDGE (e, ei, bb->succs)
844
    dump_edge_info (file, e, 1);
845
  fprintf (file, "\n\n");
846
}
847
 
848
/* Dumps a brief description of cfg to FILE.  */
849
 
850
void
851
brief_dump_cfg (FILE *file)
852
{
853
  basic_block bb;
854
 
855
  FOR_EACH_BB (bb)
856
    {
857
      dump_cfg_bb_info (file, bb);
858
    }
859
}
860
 
861
/* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
862
   leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
863
   redirected to destination of TAKEN_EDGE.
864
 
865
   This function may leave the profile inconsistent in the case TAKEN_EDGE
866
   frequency or count is believed to be lower than FREQUENCY or COUNT
867
   respectively.  */
868
void
869
update_bb_profile_for_threading (basic_block bb, int edge_frequency,
870
                                 gcov_type count, edge taken_edge)
871
{
872
  edge c;
873
  int prob;
874
  edge_iterator ei;
875
 
876
  bb->count -= count;
877
  if (bb->count < 0)
878
    {
879
      if (dump_file)
880
        fprintf (dump_file, "bb %i count became negative after threading",
881
                 bb->index);
882
      bb->count = 0;
883
    }
884
 
885
  /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
886
     Watch for overflows.  */
887
  if (bb->frequency)
888
    prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
889
  else
890
    prob = 0;
891
  if (prob > taken_edge->probability)
892
    {
893
      if (dump_file)
894
        fprintf (dump_file, "Jump threading proved probability of edge "
895
                 "%i->%i too small (it is %i, should be %i).\n",
896
                 taken_edge->src->index, taken_edge->dest->index,
897
                 taken_edge->probability, prob);
898
      prob = taken_edge->probability;
899
    }
900
 
901
  /* Now rescale the probabilities.  */
902
  taken_edge->probability -= prob;
903
  prob = REG_BR_PROB_BASE - prob;
904
  bb->frequency -= edge_frequency;
905
  if (bb->frequency < 0)
906
    bb->frequency = 0;
907
  if (prob <= 0)
908
    {
909
      if (dump_file)
910
        fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
911
                 "frequency of block should end up being 0, it is %i\n",
912
                 bb->index, bb->frequency);
913
      EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
914
      ei = ei_start (bb->succs);
915
      ei_next (&ei);
916
      for (; (c = ei_safe_edge (ei)); ei_next (&ei))
917
        c->probability = 0;
918
    }
919
  else if (prob != REG_BR_PROB_BASE)
920
    {
921
      int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
922
 
923
      FOR_EACH_EDGE (c, ei, bb->succs)
924
        {
925
          c->probability = RDIV (c->probability * scale, 65536);
926
          if (c->probability > REG_BR_PROB_BASE)
927
            c->probability = REG_BR_PROB_BASE;
928
        }
929
    }
930
 
931
  gcc_assert (bb == taken_edge->src);
932
  taken_edge->count -= count;
933
  if (taken_edge->count < 0)
934
    {
935
      if (dump_file)
936
        fprintf (dump_file, "edge %i->%i count became negative after threading",
937
                 taken_edge->src->index, taken_edge->dest->index);
938
      taken_edge->count = 0;
939
    }
940
}
941
 
942
/* Multiply all frequencies of basic blocks in array BBS of length NBBS
943
   by NUM/DEN, in int arithmetic.  May lose some accuracy.  */
944
void
945
scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
946
{
947
  int i;
948
  edge e;
949
  if (num < 0)
950
    num = 0;
951
  if (num > den)
952
    return;
953
  /* Assume that the users are producing the fraction from frequencies
954
     that never grow far enough to risk arithmetic overflow.  */
955
  gcc_assert (num < 65536);
956
  for (i = 0; i < nbbs; i++)
957
    {
958
      edge_iterator ei;
959
      bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
960
      bbs[i]->count = RDIV (bbs[i]->count * num, den);
961
      FOR_EACH_EDGE (e, ei, bbs[i]->succs)
962
        e->count = RDIV (e->count * num, den);
963
    }
964
}
965
 
966
/* numbers smaller than this value are safe to multiply without getting
967
   64bit overflow.  */
968
#define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
969
 
970
/* Multiply all frequencies of basic blocks in array BBS of length NBBS
971
   by NUM/DEN, in gcov_type arithmetic.  More accurate than previous
972
   function but considerably slower.  */
973
void
974
scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
975
                                 gcov_type den)
976
{
977
  int i;
978
  edge e;
979
  gcov_type fraction = RDIV (num * 65536, den);
980
 
981
  gcc_assert (fraction >= 0);
982
 
983
  if (num < MAX_SAFE_MULTIPLIER)
984
    for (i = 0; i < nbbs; i++)
985
      {
986
        edge_iterator ei;
987
        bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
988
        if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
989
          bbs[i]->count = RDIV (bbs[i]->count * num, den);
990
        else
991
          bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
992
        FOR_EACH_EDGE (e, ei, bbs[i]->succs)
993
          if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
994
            e->count = RDIV (e->count * num, den);
995
          else
996
            e->count = RDIV (e->count * fraction, 65536);
997
      }
998
   else
999
    for (i = 0; i < nbbs; i++)
1000
      {
1001
        edge_iterator ei;
1002
        if (sizeof (gcov_type) > sizeof (int))
1003
          bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1004
        else
1005
          bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
1006
        bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1007
        FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1008
          e->count = RDIV (e->count * fraction, 65536);
1009
      }
1010
}
1011
 
1012
/* Data structures used to maintain mapping between basic blocks and
1013
   copies.  */
1014
static htab_t bb_original;
1015
static htab_t bb_copy;
1016
static alloc_pool original_copy_bb_pool;
1017
 
1018
struct htab_bb_copy_original_entry
1019
{
1020
  /* Block we are attaching info to.  */
1021
  int index1;
1022
  /* Index of original or copy (depending on the hashtable) */
1023
  int index2;
1024
};
1025
 
1026
static hashval_t
1027
bb_copy_original_hash (const void *p)
1028
{
1029
  struct htab_bb_copy_original_entry *data
1030
    = ((struct htab_bb_copy_original_entry *)p);
1031
 
1032
  return data->index1;
1033
}
1034
static int
1035
bb_copy_original_eq (const void *p, const void *q)
1036
{
1037
  struct htab_bb_copy_original_entry *data
1038
    = ((struct htab_bb_copy_original_entry *)p);
1039
  struct htab_bb_copy_original_entry *data2
1040
    = ((struct htab_bb_copy_original_entry *)q);
1041
 
1042
  return data->index1 == data2->index1;
1043
}
1044
 
1045
/* Initialize the data structures to maintain mapping between blocks
1046
   and its copies.  */
1047
void
1048
initialize_original_copy_tables (void)
1049
{
1050
  gcc_assert (!original_copy_bb_pool);
1051
  original_copy_bb_pool
1052
    = create_alloc_pool ("original_copy",
1053
                         sizeof (struct htab_bb_copy_original_entry), 10);
1054
  bb_original = htab_create (10, bb_copy_original_hash,
1055
                             bb_copy_original_eq, NULL);
1056
  bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1057
}
1058
 
1059
/* Free the data structures to maintain mapping between blocks and
1060
   its copies.  */
1061
void
1062
free_original_copy_tables (void)
1063
{
1064
  gcc_assert (original_copy_bb_pool);
1065
  htab_delete (bb_copy);
1066
  htab_delete (bb_original);
1067
  free_alloc_pool (original_copy_bb_pool);
1068
  bb_copy = NULL;
1069
  bb_original = NULL;
1070
  original_copy_bb_pool = NULL;
1071
}
1072
 
1073
/* Set original for basic block.  Do nothing when data structures are not
1074
   initialized so passes not needing this don't need to care.  */
1075
void
1076
set_bb_original (basic_block bb, basic_block original)
1077
{
1078
  if (original_copy_bb_pool)
1079
    {
1080
      struct htab_bb_copy_original_entry **slot;
1081
      struct htab_bb_copy_original_entry key;
1082
 
1083
      key.index1 = bb->index;
1084
      slot =
1085
        (struct htab_bb_copy_original_entry **) htab_find_slot (bb_original,
1086
                                                               &key, INSERT);
1087
      if (*slot)
1088
        (*slot)->index2 = original->index;
1089
      else
1090
        {
1091
          *slot = pool_alloc (original_copy_bb_pool);
1092
          (*slot)->index1 = bb->index;
1093
          (*slot)->index2 = original->index;
1094
        }
1095
    }
1096
}
1097
 
1098
/* Get the original basic block.  */
1099
basic_block
1100
get_bb_original (basic_block bb)
1101
{
1102
  struct htab_bb_copy_original_entry *entry;
1103
  struct htab_bb_copy_original_entry key;
1104
 
1105
  gcc_assert (original_copy_bb_pool);
1106
 
1107
  key.index1 = bb->index;
1108
  entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
1109
  if (entry)
1110
    return BASIC_BLOCK (entry->index2);
1111
  else
1112
    return NULL;
1113
}
1114
 
1115
/* Set copy for basic block.  Do nothing when data structures are not
1116
   initialized so passes not needing this don't need to care.  */
1117
void
1118
set_bb_copy (basic_block bb, basic_block copy)
1119
{
1120
  if (original_copy_bb_pool)
1121
    {
1122
      struct htab_bb_copy_original_entry **slot;
1123
      struct htab_bb_copy_original_entry key;
1124
 
1125
      key.index1 = bb->index;
1126
      slot =
1127
        (struct htab_bb_copy_original_entry **) htab_find_slot (bb_copy,
1128
                                                               &key, INSERT);
1129
      if (*slot)
1130
        (*slot)->index2 = copy->index;
1131
      else
1132
        {
1133
          *slot = pool_alloc (original_copy_bb_pool);
1134
          (*slot)->index1 = bb->index;
1135
          (*slot)->index2 = copy->index;
1136
        }
1137
    }
1138
}
1139
 
1140
/* Get the copy of basic block.  */
1141
basic_block
1142
get_bb_copy (basic_block bb)
1143
{
1144
  struct htab_bb_copy_original_entry *entry;
1145
  struct htab_bb_copy_original_entry key;
1146
 
1147
  gcc_assert (original_copy_bb_pool);
1148
 
1149
  key.index1 = bb->index;
1150
  entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
1151
  if (entry)
1152
    return BASIC_BLOCK (entry->index2);
1153
  else
1154
    return NULL;
1155
}

powered by: WebSVN 2.1.0

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