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

Subversion Repositories openrisc

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

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

Line No. Rev Author Line
1 684 jeremybenn
/* Hooks for cfg representation specific functions.
2
   Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010
3
   Free Software Foundation, Inc.
4
   Contributed by Sebastian Pop <s.pop@laposte.net>
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify
9
it under the terms of the GNU General Public License as published by
10
the Free Software Foundation; either version 3, or (at your option)
11
any later version.
12
 
13
GCC is distributed in the hope that it will be useful,
14
but WITHOUT ANY WARRANTY; without even the implied warranty of
15
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16
GNU General Public License for more details.
17
 
18
You should have received a copy of the GNU General Public License
19
along with GCC; see the file COPYING3.  If not see
20
<http://www.gnu.org/licenses/>.  */
21
 
22
#include "config.h"
23
#include "system.h"
24
#include "coretypes.h"
25
#include "tm.h"
26
#include "tree.h"
27
#include "rtl.h"
28
#include "basic-block.h"
29
#include "tree-flow.h"
30
#include "timevar.h"
31
#include "diagnostic-core.h"
32
#include "cfgloop.h"
33
 
34
/* A pointer to one of the hooks containers.  */
35
static struct cfg_hooks *cfg_hooks;
36
 
37
/* Initialization of functions specific to the rtl IR.  */
38
void
39
rtl_register_cfg_hooks (void)
40
{
41
  cfg_hooks = &rtl_cfg_hooks;
42
}
43
 
44
/* Initialization of functions specific to the rtl IR.  */
45
void
46
cfg_layout_rtl_register_cfg_hooks (void)
47
{
48
  cfg_hooks = &cfg_layout_rtl_cfg_hooks;
49
}
50
 
51
/* Initialization of functions specific to the tree IR.  */
52
 
53
void
54
gimple_register_cfg_hooks (void)
55
{
56
  cfg_hooks = &gimple_cfg_hooks;
57
}
58
 
59
struct cfg_hooks
60
get_cfg_hooks (void)
61
{
62
  return *cfg_hooks;
63
}
64
 
65
void
66
set_cfg_hooks (struct cfg_hooks new_cfg_hooks)
67
{
68
  *cfg_hooks = new_cfg_hooks;
69
}
70
 
71
/* Returns current ir type.  */
72
 
73
enum ir_type
74
current_ir_type (void)
75
{
76
  if (cfg_hooks == &gimple_cfg_hooks)
77
    return IR_GIMPLE;
78
  else if (cfg_hooks == &rtl_cfg_hooks)
79
    return IR_RTL_CFGRTL;
80
  else if (cfg_hooks == &cfg_layout_rtl_cfg_hooks)
81
    return IR_RTL_CFGLAYOUT;
82
  else
83
    gcc_unreachable ();
84
}
85
 
86
/* Verify the CFG consistency.
87
 
88
   Currently it does following: checks edge and basic block list correctness
89
   and calls into IL dependent checking then.  */
90
 
91
DEBUG_FUNCTION void
92
verify_flow_info (void)
93
{
94
  size_t *edge_checksum;
95
  int err = 0;
96
  basic_block bb, last_bb_seen;
97
  basic_block *last_visited;
98
 
99
  timevar_push (TV_CFG_VERIFY);
100
  last_visited = XCNEWVEC (basic_block, last_basic_block);
101
  edge_checksum = XCNEWVEC (size_t, last_basic_block);
102
 
103
  /* Check bb chain & numbers.  */
104
  last_bb_seen = ENTRY_BLOCK_PTR;
105
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
106
    {
107
      if (bb != EXIT_BLOCK_PTR
108
          && bb != BASIC_BLOCK (bb->index))
109
        {
110
          error ("bb %d on wrong place", bb->index);
111
          err = 1;
112
        }
113
 
114
      if (bb->prev_bb != last_bb_seen)
115
        {
116
          error ("prev_bb of %d should be %d, not %d",
117
                 bb->index, last_bb_seen->index, bb->prev_bb->index);
118
          err = 1;
119
        }
120
 
121
      last_bb_seen = bb;
122
    }
123
 
124
  /* Now check the basic blocks (boundaries etc.) */
125
  FOR_EACH_BB_REVERSE (bb)
126
    {
127
      int n_fallthru = 0;
128
      edge e;
129
      edge_iterator ei;
130
 
131
      if (bb->loop_father != NULL && current_loops == NULL)
132
        {
133
          error ("verify_flow_info: Block %i has loop_father, but there are no loops",
134
                 bb->index);
135
          err = 1;
136
        }
137
      if (bb->loop_father == NULL && current_loops != NULL)
138
        {
139
          error ("verify_flow_info: Block %i lacks loop_father", bb->index);
140
          err = 1;
141
        }
142
 
143
      if (bb->count < 0)
144
        {
145
          error ("verify_flow_info: Wrong count of block %i %i",
146
                 bb->index, (int)bb->count);
147
          err = 1;
148
        }
149
      if (bb->frequency < 0)
150
        {
151
          error ("verify_flow_info: Wrong frequency of block %i %i",
152
                 bb->index, bb->frequency);
153
          err = 1;
154
        }
155
      FOR_EACH_EDGE (e, ei, bb->succs)
156
        {
157
          if (last_visited [e->dest->index] == bb)
158
            {
159
              error ("verify_flow_info: Duplicate edge %i->%i",
160
                     e->src->index, e->dest->index);
161
              err = 1;
162
            }
163
          if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
164
            {
165
              error ("verify_flow_info: Wrong probability of edge %i->%i %i",
166
                     e->src->index, e->dest->index, e->probability);
167
              err = 1;
168
            }
169
          if (e->count < 0)
170
            {
171
              error ("verify_flow_info: Wrong count of edge %i->%i %i",
172
                     e->src->index, e->dest->index, (int)e->count);
173
              err = 1;
174
            }
175
 
176
          last_visited [e->dest->index] = bb;
177
 
178
          if (e->flags & EDGE_FALLTHRU)
179
            n_fallthru++;
180
 
181
          if (e->src != bb)
182
            {
183
              error ("verify_flow_info: Basic block %d succ edge is corrupted",
184
                     bb->index);
185
              fprintf (stderr, "Predecessor: ");
186
              dump_edge_info (stderr, e, 0);
187
              fprintf (stderr, "\nSuccessor: ");
188
              dump_edge_info (stderr, e, 1);
189
              fprintf (stderr, "\n");
190
              err = 1;
191
            }
192
 
193
          edge_checksum[e->dest->index] += (size_t) e;
194
        }
195
      if (n_fallthru > 1)
196
        {
197
          error ("wrong amount of branch edges after unconditional jump %i", bb->index);
198
          err = 1;
199
        }
200
 
201
      FOR_EACH_EDGE (e, ei, bb->preds)
202
        {
203
          if (e->dest != bb)
204
            {
205
              error ("basic block %d pred edge is corrupted", bb->index);
206
              fputs ("Predecessor: ", stderr);
207
              dump_edge_info (stderr, e, 0);
208
              fputs ("\nSuccessor: ", stderr);
209
              dump_edge_info (stderr, e, 1);
210
              fputc ('\n', stderr);
211
              err = 1;
212
            }
213
 
214
          if (ei.index != e->dest_idx)
215
            {
216
              error ("basic block %d pred edge is corrupted", bb->index);
217
              error ("its dest_idx should be %d, not %d",
218
                     ei.index, e->dest_idx);
219
              fputs ("Predecessor: ", stderr);
220
              dump_edge_info (stderr, e, 0);
221
              fputs ("\nSuccessor: ", stderr);
222
              dump_edge_info (stderr, e, 1);
223
              fputc ('\n', stderr);
224
              err = 1;
225
            }
226
 
227
          edge_checksum[e->dest->index] -= (size_t) e;
228
        }
229
    }
230
 
231
  /* Complete edge checksumming for ENTRY and EXIT.  */
232
  {
233
    edge e;
234
    edge_iterator ei;
235
 
236
    FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
237
      edge_checksum[e->dest->index] += (size_t) e;
238
 
239
    FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
240
      edge_checksum[e->dest->index] -= (size_t) e;
241
  }
242
 
243
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
244
    if (edge_checksum[bb->index])
245
      {
246
        error ("basic block %i edge lists are corrupted", bb->index);
247
        err = 1;
248
      }
249
 
250
  last_bb_seen = ENTRY_BLOCK_PTR;
251
 
252
  /* Clean up.  */
253
  free (last_visited);
254
  free (edge_checksum);
255
 
256
  if (cfg_hooks->verify_flow_info)
257
    err |= cfg_hooks->verify_flow_info ();
258
  if (err)
259
    internal_error ("verify_flow_info failed");
260
  timevar_pop (TV_CFG_VERIFY);
261
}
262
 
263
/* Print out one basic block.  This function takes care of the purely
264
   graph related information.  The cfg hook for the active representation
265
   should dump representation-specific information.  */
266
 
267
void
268
dump_bb (basic_block bb, FILE *outf, int indent)
269
{
270
  edge e;
271
  edge_iterator ei;
272
  char *s_indent;
273
 
274
  s_indent = (char *) alloca ((size_t) indent + 1);
275
  memset (s_indent, ' ', (size_t) indent);
276
  s_indent[indent] = '\0';
277
 
278
  fprintf (outf, ";;%s basic block %d, loop depth %d, count ",
279
           s_indent, bb->index, bb->loop_depth);
280
  fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
281
  putc ('\n', outf);
282
 
283
  fprintf (outf, ";;%s prev block ", s_indent);
284
  if (bb->prev_bb)
285
    fprintf (outf, "%d, ", bb->prev_bb->index);
286
  else
287
    fprintf (outf, "(nil), ");
288
  fprintf (outf, "next block ");
289
  if (bb->next_bb)
290
    fprintf (outf, "%d", bb->next_bb->index);
291
  else
292
    fprintf (outf, "(nil)");
293
  putc ('\n', outf);
294
 
295
  fprintf (outf, ";;%s pred:      ", s_indent);
296
  FOR_EACH_EDGE (e, ei, bb->preds)
297
    dump_edge_info (outf, e, 0);
298
  putc ('\n', outf);
299
 
300
  fprintf (outf, ";;%s succ:      ", s_indent);
301
  FOR_EACH_EDGE (e, ei, bb->succs)
302
    dump_edge_info (outf, e, 1);
303
  putc ('\n', outf);
304
 
305
  if (cfg_hooks->dump_bb)
306
    cfg_hooks->dump_bb (bb, outf, indent, 0);
307
}
308
 
309
/* Redirect edge E to the given basic block DEST and update underlying program
310
   representation.  Returns edge representing redirected branch (that may not
311
   be equivalent to E in the case of duplicate edges being removed) or NULL
312
   if edge is not easily redirectable for whatever reason.  */
313
 
314
edge
315
redirect_edge_and_branch (edge e, basic_block dest)
316
{
317
  edge ret;
318
 
319
  if (!cfg_hooks->redirect_edge_and_branch)
320
    internal_error ("%s does not support redirect_edge_and_branch",
321
                    cfg_hooks->name);
322
 
323
  ret = cfg_hooks->redirect_edge_and_branch (e, dest);
324
 
325
  /* If RET != E, then either the redirection failed, or the edge E
326
     was removed since RET already lead to the same destination.  */
327
  if (current_loops != NULL && ret == e)
328
    rescan_loop_exit (e, false, false);
329
 
330
  return ret;
331
}
332
 
333
/* Returns true if it is possible to remove the edge E by redirecting it
334
   to the destination of the other edge going from its source.  */
335
 
336
bool
337
can_remove_branch_p (const_edge e)
338
{
339
  if (!cfg_hooks->can_remove_branch_p)
340
    internal_error ("%s does not support can_remove_branch_p",
341
                    cfg_hooks->name);
342
 
343
  if (EDGE_COUNT (e->src->succs) != 2)
344
    return false;
345
 
346
  return cfg_hooks->can_remove_branch_p (e);
347
}
348
 
349
/* Removes E, by redirecting it to the destination of the other edge going
350
   from its source.  Can_remove_branch_p must be true for E, hence this
351
   operation cannot fail.  */
352
 
353
void
354
remove_branch (edge e)
355
{
356
  edge other;
357
  basic_block src = e->src;
358
  int irr;
359
 
360
  gcc_assert (EDGE_COUNT (e->src->succs) == 2);
361
 
362
  other = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
363
  irr = other->flags & EDGE_IRREDUCIBLE_LOOP;
364
 
365
  e = redirect_edge_and_branch (e, other->dest);
366
  gcc_assert (e != NULL);
367
 
368
  e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
369
  e->flags |= irr;
370
}
371
 
372
/* Removes edge E from cfg.  Unlike remove_branch, it does not update IL.  */
373
 
374
void
375
remove_edge (edge e)
376
{
377
  if (current_loops != NULL)
378
    rescan_loop_exit (e, false, true);
379
 
380
  remove_edge_raw (e);
381
}
382
 
383
/* Redirect the edge E to basic block DEST even if it requires creating
384
   of a new basic block; then it returns the newly created basic block.
385
   Aborts when redirection is impossible.  */
386
 
387
basic_block
388
redirect_edge_and_branch_force (edge e, basic_block dest)
389
{
390
  basic_block ret, src = e->src;
391
 
392
  if (!cfg_hooks->redirect_edge_and_branch_force)
393
    internal_error ("%s does not support redirect_edge_and_branch_force",
394
                    cfg_hooks->name);
395
 
396
  if (current_loops != NULL)
397
    rescan_loop_exit (e, false, true);
398
 
399
  ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
400
 
401
  if (ret != NULL && dom_info_available_p (CDI_DOMINATORS))
402
    set_immediate_dominator (CDI_DOMINATORS, ret, src);
403
 
404
  if (current_loops != NULL)
405
    {
406
      if (ret != NULL)
407
        {
408
          struct loop *loop
409
            = find_common_loop (single_pred (ret)->loop_father,
410
                                single_succ (ret)->loop_father);
411
          add_bb_to_loop (ret, loop);
412
        }
413
      else if (find_edge (src, dest) == e)
414
        rescan_loop_exit (e, true, false);
415
    }
416
 
417
  return ret;
418
}
419
 
420
/* Splits basic block BB after the specified instruction I (but at least after
421
   the labels).  If I is NULL, splits just after labels.  The newly created edge
422
   is returned.  The new basic block is created just after the old one.  */
423
 
424
edge
425
split_block (basic_block bb, void *i)
426
{
427
  basic_block new_bb;
428
  edge res;
429
 
430
  if (!cfg_hooks->split_block)
431
    internal_error ("%s does not support split_block", cfg_hooks->name);
432
 
433
  new_bb = cfg_hooks->split_block (bb, i);
434
  if (!new_bb)
435
    return NULL;
436
 
437
  new_bb->count = bb->count;
438
  new_bb->frequency = bb->frequency;
439
  new_bb->loop_depth = bb->loop_depth;
440
  new_bb->discriminator = bb->discriminator;
441
 
442
  if (dom_info_available_p (CDI_DOMINATORS))
443
    {
444
      redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
445
      set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
446
    }
447
 
448
  if (current_loops != NULL)
449
    {
450
      add_bb_to_loop (new_bb, bb->loop_father);
451
      if (bb->loop_father->latch == bb)
452
        bb->loop_father->latch = new_bb;
453
    }
454
 
455
  res = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
456
 
457
  if (bb->flags & BB_IRREDUCIBLE_LOOP)
458
    {
459
      new_bb->flags |= BB_IRREDUCIBLE_LOOP;
460
      res->flags |= EDGE_IRREDUCIBLE_LOOP;
461
    }
462
 
463
  return res;
464
}
465
 
466
/* Splits block BB just after labels.  The newly created edge is returned.  */
467
 
468
edge
469
split_block_after_labels (basic_block bb)
470
{
471
  return split_block (bb, NULL);
472
}
473
 
474
/* Moves block BB immediately after block AFTER.  Returns false if the
475
   movement was impossible.  */
476
 
477
bool
478
move_block_after (basic_block bb, basic_block after)
479
{
480
  bool ret;
481
 
482
  if (!cfg_hooks->move_block_after)
483
    internal_error ("%s does not support move_block_after", cfg_hooks->name);
484
 
485
  ret = cfg_hooks->move_block_after (bb, after);
486
 
487
  return ret;
488
}
489
 
490
/* Deletes the basic block BB.  */
491
 
492
void
493
delete_basic_block (basic_block bb)
494
{
495
  if (!cfg_hooks->delete_basic_block)
496
    internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
497
 
498
  cfg_hooks->delete_basic_block (bb);
499
 
500
  if (current_loops != NULL)
501
    {
502
      struct loop *loop = bb->loop_father;
503
 
504
      /* If we remove the header or the latch of a loop, mark the loop for
505
         removal by setting its header and latch to NULL.  */
506
      if (loop->latch == bb
507
          || loop->header == bb)
508
        {
509
          loop->header = NULL;
510
          loop->latch = NULL;
511
        }
512
 
513
      remove_bb_from_loops (bb);
514
    }
515
 
516
  /* Remove the edges into and out of this block.  Note that there may
517
     indeed be edges in, if we are removing an unreachable loop.  */
518
  while (EDGE_COUNT (bb->preds) != 0)
519
    remove_edge (EDGE_PRED (bb, 0));
520
  while (EDGE_COUNT (bb->succs) != 0)
521
    remove_edge (EDGE_SUCC (bb, 0));
522
 
523
  if (dom_info_available_p (CDI_DOMINATORS))
524
    delete_from_dominance_info (CDI_DOMINATORS, bb);
525
  if (dom_info_available_p (CDI_POST_DOMINATORS))
526
    delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
527
 
528
  /* Remove the basic block from the array.  */
529
  expunge_block (bb);
530
}
531
 
532
/* Splits edge E and returns the newly created basic block.  */
533
 
534
basic_block
535
split_edge (edge e)
536
{
537
  basic_block ret;
538
  gcov_type count = e->count;
539
  int freq = EDGE_FREQUENCY (e);
540
  edge f;
541
  bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
542
  struct loop *loop;
543
  basic_block src = e->src, dest = e->dest;
544
 
545
  if (!cfg_hooks->split_edge)
546
    internal_error ("%s does not support split_edge", cfg_hooks->name);
547
 
548
  if (current_loops != NULL)
549
    rescan_loop_exit (e, false, true);
550
 
551
  ret = cfg_hooks->split_edge (e);
552
  ret->count = count;
553
  ret->frequency = freq;
554
  single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
555
  single_succ_edge (ret)->count = count;
556
 
557
  if (irr)
558
    {
559
      ret->flags |= BB_IRREDUCIBLE_LOOP;
560
      single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
561
      single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
562
    }
563
 
564
  if (dom_info_available_p (CDI_DOMINATORS))
565
    set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
566
 
567
  if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
568
    {
569
      /* There are two cases:
570
 
571
         If the immediate dominator of e->dest is not e->src, it
572
         remains unchanged.
573
 
574
         If immediate dominator of e->dest is e->src, it may become
575
         ret, provided that all other predecessors of e->dest are
576
         dominated by e->dest.  */
577
 
578
      if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
579
          == single_pred (ret))
580
        {
581
          edge_iterator ei;
582
          FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
583
            {
584
              if (f == single_succ_edge (ret))
585
                continue;
586
 
587
              if (!dominated_by_p (CDI_DOMINATORS, f->src,
588
                                   single_succ (ret)))
589
                break;
590
            }
591
 
592
          if (!f)
593
            set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
594
        }
595
    }
596
 
597
  if (current_loops != NULL)
598
    {
599
      loop = find_common_loop (src->loop_father, dest->loop_father);
600
      add_bb_to_loop (ret, loop);
601
 
602
      if (loop->latch == src)
603
        loop->latch = ret;
604
    }
605
 
606
  return ret;
607
}
608
 
609
/* Creates a new basic block just after the basic block AFTER.
610
   HEAD and END are the first and the last statement belonging
611
   to the block.  If both are NULL, an empty block is created.  */
612
 
613
basic_block
614
create_basic_block (void *head, void *end, basic_block after)
615
{
616
  basic_block ret;
617
 
618
  if (!cfg_hooks->create_basic_block)
619
    internal_error ("%s does not support create_basic_block", cfg_hooks->name);
620
 
621
  ret = cfg_hooks->create_basic_block (head, end, after);
622
 
623
  if (dom_info_available_p (CDI_DOMINATORS))
624
    add_to_dominance_info (CDI_DOMINATORS, ret);
625
  if (dom_info_available_p (CDI_POST_DOMINATORS))
626
    add_to_dominance_info (CDI_POST_DOMINATORS, ret);
627
 
628
  return ret;
629
}
630
 
631
/* Creates an empty basic block just after basic block AFTER.  */
632
 
633
basic_block
634
create_empty_bb (basic_block after)
635
{
636
  return create_basic_block (NULL, NULL, after);
637
}
638
 
639
/* Checks whether we may merge blocks BB1 and BB2.  */
640
 
641
bool
642
can_merge_blocks_p (basic_block bb1, basic_block bb2)
643
{
644
  bool ret;
645
 
646
  if (!cfg_hooks->can_merge_blocks_p)
647
    internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
648
 
649
  ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
650
 
651
  return ret;
652
}
653
 
654
void
655
predict_edge (edge e, enum br_predictor predictor, int probability)
656
{
657
  if (!cfg_hooks->predict_edge)
658
    internal_error ("%s does not support predict_edge", cfg_hooks->name);
659
 
660
  cfg_hooks->predict_edge (e, predictor, probability);
661
}
662
 
663
bool
664
predicted_by_p (const_basic_block bb, enum br_predictor predictor)
665
{
666
  if (!cfg_hooks->predict_edge)
667
    internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
668
 
669
  return cfg_hooks->predicted_by_p (bb, predictor);
670
}
671
 
672
/* Merges basic block B into basic block A.  */
673
 
674
void
675
merge_blocks (basic_block a, basic_block b)
676
{
677
  edge e;
678
  edge_iterator ei;
679
 
680
  if (!cfg_hooks->merge_blocks)
681
    internal_error ("%s does not support merge_blocks", cfg_hooks->name);
682
 
683
  cfg_hooks->merge_blocks (a, b);
684
 
685
  if (current_loops != NULL)
686
    remove_bb_from_loops (b);
687
 
688
  /* Normally there should only be one successor of A and that is B, but
689
     partway though the merge of blocks for conditional_execution we'll
690
     be merging a TEST block with THEN and ELSE successors.  Free the
691
     whole lot of them and hope the caller knows what they're doing.  */
692
 
693
  while (EDGE_COUNT (a->succs) != 0)
694
    remove_edge (EDGE_SUCC (a, 0));
695
 
696
  /* Adjust the edges out of B for the new owner.  */
697
  FOR_EACH_EDGE (e, ei, b->succs)
698
    {
699
      e->src = a;
700
      if (current_loops != NULL)
701
        rescan_loop_exit (e, true, false);
702
    }
703
  a->succs = b->succs;
704
  a->flags |= b->flags;
705
 
706
  /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
707
  b->preds = b->succs = NULL;
708
 
709
  if (dom_info_available_p (CDI_DOMINATORS))
710
    redirect_immediate_dominators (CDI_DOMINATORS, b, a);
711
 
712
  if (dom_info_available_p (CDI_DOMINATORS))
713
    delete_from_dominance_info (CDI_DOMINATORS, b);
714
  if (dom_info_available_p (CDI_POST_DOMINATORS))
715
    delete_from_dominance_info (CDI_POST_DOMINATORS, b);
716
 
717
  expunge_block (b);
718
}
719
 
720
/* Split BB into entry part and the rest (the rest is the newly created block).
721
   Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
722
   part.  Returns the edge connecting the entry part to the rest.  */
723
 
724
edge
725
make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
726
                      void (*new_bb_cbk) (basic_block))
727
{
728
  edge e, fallthru;
729
  edge_iterator ei;
730
  basic_block dummy, jump;
731
  struct loop *loop, *ploop, *cloop;
732
 
733
  if (!cfg_hooks->make_forwarder_block)
734
    internal_error ("%s does not support make_forwarder_block",
735
                    cfg_hooks->name);
736
 
737
  fallthru = split_block_after_labels (bb);
738
  dummy = fallthru->src;
739
  bb = fallthru->dest;
740
 
741
  /* Redirect back edges we want to keep.  */
742
  for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
743
    {
744
      basic_block e_src;
745
 
746
      if (redirect_edge_p (e))
747
        {
748
          ei_next (&ei);
749
          continue;
750
        }
751
 
752
      dummy->frequency -= EDGE_FREQUENCY (e);
753
      dummy->count -= e->count;
754
      if (dummy->frequency < 0)
755
        dummy->frequency = 0;
756
      if (dummy->count < 0)
757
        dummy->count = 0;
758
      fallthru->count -= e->count;
759
      if (fallthru->count < 0)
760
        fallthru->count = 0;
761
 
762
      e_src = e->src;
763
      jump = redirect_edge_and_branch_force (e, bb);
764
      if (jump != NULL)
765
        {
766
          /* If we redirected the loop latch edge, the JUMP block now acts like
767
             the new latch of the loop.  */
768
          if (current_loops != NULL
769
              && dummy->loop_father != NULL
770
              && dummy->loop_father->header == dummy
771
              && dummy->loop_father->latch == e_src)
772
            dummy->loop_father->latch = jump;
773
 
774
          if (new_bb_cbk != NULL)
775
            new_bb_cbk (jump);
776
        }
777
    }
778
 
779
  if (dom_info_available_p (CDI_DOMINATORS))
780
    {
781
      VEC (basic_block, heap) *doms_to_fix = VEC_alloc (basic_block, heap, 2);
782
      VEC_quick_push (basic_block, doms_to_fix, dummy);
783
      VEC_quick_push (basic_block, doms_to_fix, bb);
784
      iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
785
      VEC_free (basic_block, heap, doms_to_fix);
786
    }
787
 
788
  if (current_loops != NULL)
789
    {
790
      /* If we do not split a loop header, then both blocks belong to the
791
         same loop.  In case we split loop header and do not redirect the
792
         latch edge to DUMMY, then DUMMY belongs to the outer loop, and
793
         BB becomes the new header.  If latch is not recorded for the loop,
794
         we leave this updating on the caller (this may only happen during
795
         loop analysis).  */
796
      loop = dummy->loop_father;
797
      if (loop->header == dummy
798
          && loop->latch != NULL
799
          && find_edge (loop->latch, dummy) == NULL)
800
        {
801
          remove_bb_from_loops (dummy);
802
          loop->header = bb;
803
 
804
          cloop = loop;
805
          FOR_EACH_EDGE (e, ei, dummy->preds)
806
            {
807
              cloop = find_common_loop (cloop, e->src->loop_father);
808
            }
809
          add_bb_to_loop (dummy, cloop);
810
        }
811
 
812
      /* In case we split loop latch, update it.  */
813
      for (ploop = loop; ploop; ploop = loop_outer (ploop))
814
        if (ploop->latch == dummy)
815
          ploop->latch = bb;
816
    }
817
 
818
  cfg_hooks->make_forwarder_block (fallthru);
819
 
820
  return fallthru;
821
}
822
 
823
/* Try to make the edge fallthru.  */
824
 
825
void
826
tidy_fallthru_edge (edge e)
827
{
828
  if (cfg_hooks->tidy_fallthru_edge)
829
    cfg_hooks->tidy_fallthru_edge (e);
830
}
831
 
832
/* Fix up edges that now fall through, or rather should now fall through
833
   but previously required a jump around now deleted blocks.  Simplify
834
   the search by only examining blocks numerically adjacent, since this
835
   is how they were created.
836
 
837
   ??? This routine is currently RTL specific.  */
838
 
839
void
840
tidy_fallthru_edges (void)
841
{
842
  basic_block b, c;
843
 
844
  if (!cfg_hooks->tidy_fallthru_edge)
845
    return;
846
 
847
  if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
848
    return;
849
 
850
  FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
851
    {
852
      edge s;
853
 
854
      c = b->next_bb;
855
 
856
      /* We care about simple conditional or unconditional jumps with
857
         a single successor.
858
 
859
         If we had a conditional branch to the next instruction when
860
         CFG was built, then there will only be one out edge for the
861
         block which ended with the conditional branch (since we do
862
         not create duplicate edges).
863
 
864
         Furthermore, the edge will be marked as a fallthru because we
865
         merge the flags for the duplicate edges.  So we do not want to
866
         check that the edge is not a FALLTHRU edge.  */
867
 
868
      if (single_succ_p (b))
869
        {
870
          s = single_succ_edge (b);
871
          if (! (s->flags & EDGE_COMPLEX)
872
              && s->dest == c
873
              && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
874
            tidy_fallthru_edge (s);
875
        }
876
    }
877
}
878
 
879
/* Edge E is assumed to be fallthru edge.  Emit needed jump instruction
880
   (and possibly create new basic block) to make edge non-fallthru.
881
   Return newly created BB or NULL if none.  */
882
 
883
basic_block
884
force_nonfallthru (edge e)
885
{
886
  basic_block ret, src = e->src;
887
 
888
  if (!cfg_hooks->force_nonfallthru)
889
    internal_error ("%s does not support force_nonfallthru",
890
                    cfg_hooks->name);
891
 
892
  ret = cfg_hooks->force_nonfallthru (e);
893
  if (ret != NULL)
894
    {
895
      if (dom_info_available_p (CDI_DOMINATORS))
896
        set_immediate_dominator (CDI_DOMINATORS, ret, src);
897
 
898
      if (current_loops != NULL)
899
        {
900
          struct loop *loop
901
            = find_common_loop (single_pred (ret)->loop_father,
902
                                single_succ (ret)->loop_father);
903
          rescan_loop_exit (e, false, true);
904
          add_bb_to_loop (ret, loop);
905
        }
906
    }
907
 
908
  return ret;
909
}
910
 
911
/* Returns true if we can duplicate basic block BB.  */
912
 
913
bool
914
can_duplicate_block_p (const_basic_block bb)
915
{
916
  if (!cfg_hooks->can_duplicate_block_p)
917
    internal_error ("%s does not support can_duplicate_block_p",
918
                    cfg_hooks->name);
919
 
920
  if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
921
    return false;
922
 
923
  return cfg_hooks->can_duplicate_block_p (bb);
924
}
925
 
926
/* Duplicates basic block BB and redirects edge E to it.  Returns the
927
   new basic block.  The new basic block is placed after the basic block
928
   AFTER.  */
929
 
930
basic_block
931
duplicate_block (basic_block bb, edge e, basic_block after)
932
{
933
  edge s, n;
934
  basic_block new_bb;
935
  gcov_type new_count = e ? e->count : 0;
936
  edge_iterator ei;
937
 
938
  if (!cfg_hooks->duplicate_block)
939
    internal_error ("%s does not support duplicate_block",
940
                    cfg_hooks->name);
941
 
942
  if (bb->count < new_count)
943
    new_count = bb->count;
944
 
945
  gcc_checking_assert (can_duplicate_block_p (bb));
946
 
947
  new_bb = cfg_hooks->duplicate_block (bb);
948
  if (after)
949
    move_block_after (new_bb, after);
950
 
951
  new_bb->loop_depth = bb->loop_depth;
952
  new_bb->flags = bb->flags;
953
  FOR_EACH_EDGE (s, ei, bb->succs)
954
    {
955
      /* Since we are creating edges from a new block to successors
956
         of another block (which therefore are known to be disjoint), there
957
         is no need to actually check for duplicated edges.  */
958
      n = unchecked_make_edge (new_bb, s->dest, s->flags);
959
      n->probability = s->probability;
960
      if (e && bb->count)
961
        {
962
          /* Take care for overflows!  */
963
          n->count = s->count * (new_count * 10000 / bb->count) / 10000;
964
          s->count -= n->count;
965
        }
966
      else
967
        n->count = s->count;
968
      n->aux = s->aux;
969
    }
970
 
971
  if (e)
972
    {
973
      new_bb->count = new_count;
974
      bb->count -= new_count;
975
 
976
      new_bb->frequency = EDGE_FREQUENCY (e);
977
      bb->frequency -= EDGE_FREQUENCY (e);
978
 
979
      redirect_edge_and_branch_force (e, new_bb);
980
 
981
      if (bb->count < 0)
982
        bb->count = 0;
983
      if (bb->frequency < 0)
984
        bb->frequency = 0;
985
    }
986
  else
987
    {
988
      new_bb->count = bb->count;
989
      new_bb->frequency = bb->frequency;
990
    }
991
 
992
  set_bb_original (new_bb, bb);
993
  set_bb_copy (bb, new_bb);
994
 
995
  /* Add the new block to the copy of the loop of BB, or directly to the loop
996
     of BB if the loop is not being copied.  */
997
  if (current_loops != NULL)
998
    {
999
      struct loop *cloop = bb->loop_father;
1000
      struct loop *copy = get_loop_copy (cloop);
1001
      add_bb_to_loop (new_bb, copy ? copy : cloop);
1002
    }
1003
 
1004
  return new_bb;
1005
}
1006
 
1007
/* Return 1 if BB ends with a call, possibly followed by some
1008
   instructions that must stay with the call, 0 otherwise.  */
1009
 
1010
bool
1011
block_ends_with_call_p (basic_block bb)
1012
{
1013
  if (!cfg_hooks->block_ends_with_call_p)
1014
    internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
1015
 
1016
  return (cfg_hooks->block_ends_with_call_p) (bb);
1017
}
1018
 
1019
/* Return 1 if BB ends with a conditional branch, 0 otherwise.  */
1020
 
1021
bool
1022
block_ends_with_condjump_p (const_basic_block bb)
1023
{
1024
  if (!cfg_hooks->block_ends_with_condjump_p)
1025
    internal_error ("%s does not support block_ends_with_condjump_p",
1026
                    cfg_hooks->name);
1027
 
1028
  return (cfg_hooks->block_ends_with_condjump_p) (bb);
1029
}
1030
 
1031
/* Add fake edges to the function exit for any non constant and non noreturn
1032
   calls, volatile inline assembly in the bitmap of blocks specified by
1033
   BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
1034
   that were split.
1035
 
1036
   The goal is to expose cases in which entering a basic block does not imply
1037
   that all subsequent instructions must be executed.  */
1038
 
1039
int
1040
flow_call_edges_add (sbitmap blocks)
1041
{
1042
  if (!cfg_hooks->flow_call_edges_add)
1043
    internal_error ("%s does not support flow_call_edges_add",
1044
                    cfg_hooks->name);
1045
 
1046
  return (cfg_hooks->flow_call_edges_add) (blocks);
1047
}
1048
 
1049
/* This function is called immediately after edge E is added to the
1050
   edge vector E->dest->preds.  */
1051
 
1052
void
1053
execute_on_growing_pred (edge e)
1054
{
1055
  if (cfg_hooks->execute_on_growing_pred)
1056
    cfg_hooks->execute_on_growing_pred (e);
1057
}
1058
 
1059
/* This function is called immediately before edge E is removed from
1060
   the edge vector E->dest->preds.  */
1061
 
1062
void
1063
execute_on_shrinking_pred (edge e)
1064
{
1065
  if (cfg_hooks->execute_on_shrinking_pred)
1066
    cfg_hooks->execute_on_shrinking_pred (e);
1067
}
1068
 
1069
/* This is used inside loop versioning when we want to insert
1070
   stmts/insns on the edges, which have a different behavior
1071
   in tree's and in RTL, so we made a CFG hook.  */
1072
void
1073
lv_flush_pending_stmts (edge e)
1074
{
1075
  if (cfg_hooks->flush_pending_stmts)
1076
    cfg_hooks->flush_pending_stmts (e);
1077
}
1078
 
1079
/* Loop versioning uses the duplicate_loop_to_header_edge to create
1080
   a new version of the loop basic-blocks, the parameters here are
1081
   exactly the same as in duplicate_loop_to_header_edge or
1082
   tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1083
   additional work to maintain ssa information that's why there is
1084
   a need to call the tree_duplicate_loop_to_header_edge rather
1085
   than duplicate_loop_to_header_edge when we are in tree mode.  */
1086
bool
1087
cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
1088
                                        unsigned int ndupl,
1089
                                        sbitmap wont_exit, edge orig,
1090
                                        VEC (edge, heap) **to_remove,
1091
                                        int flags)
1092
{
1093
  gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
1094
  return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e,
1095
                                                            ndupl, wont_exit,
1096
                                                            orig, to_remove,
1097
                                                            flags);
1098
}
1099
 
1100
/* Conditional jumps are represented differently in trees and RTL,
1101
   this hook takes a basic block that is known to have a cond jump
1102
   at its end and extracts the taken and not taken edges out of it
1103
   and store it in E1 and E2 respectively.  */
1104
void
1105
extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1106
{
1107
  gcc_assert (cfg_hooks->extract_cond_bb_edges);
1108
  cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1109
}
1110
 
1111
/* Responsible for updating the ssa info (PHI nodes) on the
1112
   new condition basic block that guards the versioned loop.  */
1113
void
1114
lv_adjust_loop_header_phi (basic_block first, basic_block second,
1115
                           basic_block new_block, edge e)
1116
{
1117
  if (cfg_hooks->lv_adjust_loop_header_phi)
1118
    cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1119
}
1120
 
1121
/* Conditions in trees and RTL are different so we need
1122
   a different handling when we add the condition to the
1123
   versioning code.  */
1124
void
1125
lv_add_condition_to_bb (basic_block first, basic_block second,
1126
                        basic_block new_block, void *cond)
1127
{
1128
  gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1129
  cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1130
}

powered by: WebSVN 2.1.0

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