OSDN Git Service

0897b0df5653f07a050ee7a3bc04585ec3174a9f
[pf3gnuchains/gcc-fork.git] / gcc / cfghooks.c
1 /* Hooks for cfg representation specific functions.
2    Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation,
3    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 "toplev.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 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   struct loop *loop;
392
393   if (!cfg_hooks->redirect_edge_and_branch_force)
394     internal_error ("%s does not support redirect_edge_and_branch_force",
395                     cfg_hooks->name);
396
397   if (current_loops != NULL)
398     rescan_loop_exit (e, false, true);
399
400   ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
401   if (ret != NULL
402       && dom_info_available_p (CDI_DOMINATORS))
403     set_immediate_dominator (CDI_DOMINATORS, ret, src);
404
405   if (current_loops != NULL)
406     {
407       if (ret != NULL)
408         {
409           loop = 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
429   if (!cfg_hooks->split_block)
430     internal_error ("%s does not support split_block", cfg_hooks->name);
431
432   new_bb = cfg_hooks->split_block (bb, i);
433   if (!new_bb)
434     return NULL;
435
436   new_bb->count = bb->count;
437   new_bb->frequency = bb->frequency;
438   new_bb->loop_depth = bb->loop_depth;
439
440   if (dom_info_available_p (CDI_DOMINATORS))
441     {
442       redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
443       set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
444     }
445
446   if (current_loops != NULL)
447     {
448       add_bb_to_loop (new_bb, bb->loop_father);
449       if (bb->loop_father->latch == bb)
450         bb->loop_father->latch = new_bb;
451     }
452
453   return make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
454 }
455
456 /* Splits block BB just after labels.  The newly created edge is returned.  */
457
458 edge
459 split_block_after_labels (basic_block bb)
460 {
461   return split_block (bb, NULL);
462 }
463
464 /* Moves block BB immediately after block AFTER.  Returns false if the
465    movement was impossible.  */
466
467 bool
468 move_block_after (basic_block bb, basic_block after)
469 {
470   bool ret;
471
472   if (!cfg_hooks->move_block_after)
473     internal_error ("%s does not support move_block_after", cfg_hooks->name);
474
475   ret = cfg_hooks->move_block_after (bb, after);
476
477   return ret;
478 }
479
480 /* Deletes the basic block BB.  */
481
482 void
483 delete_basic_block (basic_block bb)
484 {
485   if (!cfg_hooks->delete_basic_block)
486     internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
487
488   cfg_hooks->delete_basic_block (bb);
489
490   if (current_loops != NULL)
491     {
492       struct loop *loop = bb->loop_father;
493
494       /* If we remove the header or the latch of a loop, mark the loop for
495          removal by setting its header and latch to NULL.  */
496       if (loop->latch == bb
497           || loop->header == bb)
498         {
499           loop->header = NULL;
500           loop->latch = NULL;
501         }
502
503       remove_bb_from_loops (bb);
504     }
505
506   /* Remove the edges into and out of this block.  Note that there may
507      indeed be edges in, if we are removing an unreachable loop.  */
508   while (EDGE_COUNT (bb->preds) != 0)
509     remove_edge (EDGE_PRED (bb, 0));
510   while (EDGE_COUNT (bb->succs) != 0)
511     remove_edge (EDGE_SUCC (bb, 0));
512
513   if (dom_info_available_p (CDI_DOMINATORS))
514     delete_from_dominance_info (CDI_DOMINATORS, bb);
515   if (dom_info_available_p (CDI_POST_DOMINATORS))
516     delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
517
518   /* Remove the basic block from the array.  */
519   expunge_block (bb);
520 }
521
522 /* Splits edge E and returns the newly created basic block.  */
523
524 basic_block
525 split_edge (edge e)
526 {
527   basic_block ret;
528   gcov_type count = e->count;
529   int freq = EDGE_FREQUENCY (e);
530   edge f;
531   bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
532   struct loop *loop;
533   basic_block src = e->src, dest = e->dest;
534
535   if (!cfg_hooks->split_edge)
536     internal_error ("%s does not support split_edge", cfg_hooks->name);
537
538   if (current_loops != NULL)
539     rescan_loop_exit (e, false, true);
540
541   ret = cfg_hooks->split_edge (e);
542   ret->count = count;
543   ret->frequency = freq;
544   single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
545   single_succ_edge (ret)->count = count;
546
547   if (irr)
548     {
549       ret->flags |= BB_IRREDUCIBLE_LOOP;
550       single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
551       single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
552     }
553
554   if (dom_info_available_p (CDI_DOMINATORS))
555     set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
556
557   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
558     {
559       /* There are two cases:
560
561          If the immediate dominator of e->dest is not e->src, it
562          remains unchanged.
563
564          If immediate dominator of e->dest is e->src, it may become
565          ret, provided that all other predecessors of e->dest are
566          dominated by e->dest.  */
567
568       if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
569           == single_pred (ret))
570         {
571           edge_iterator ei;
572           FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
573             {
574               if (f == single_succ_edge (ret))
575                 continue;
576
577               if (!dominated_by_p (CDI_DOMINATORS, f->src,
578                                    single_succ (ret)))
579                 break;
580             }
581
582           if (!f)
583             set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
584         }
585     }
586
587   if (current_loops != NULL)
588     {
589       loop = find_common_loop (src->loop_father, dest->loop_father);
590       add_bb_to_loop (ret, loop);
591
592       if (loop->latch == src)
593         loop->latch = ret;
594     }
595
596   return ret;
597 }
598
599 /* Creates a new basic block just after the basic block AFTER.
600    HEAD and END are the first and the last statement belonging
601    to the block.  If both are NULL, an empty block is created.  */
602
603 basic_block
604 create_basic_block (void *head, void *end, basic_block after)
605 {
606   basic_block ret;
607
608   if (!cfg_hooks->create_basic_block)
609     internal_error ("%s does not support create_basic_block", cfg_hooks->name);
610
611   ret = cfg_hooks->create_basic_block (head, end, after);
612
613   if (dom_info_available_p (CDI_DOMINATORS))
614     add_to_dominance_info (CDI_DOMINATORS, ret);
615   if (dom_info_available_p (CDI_POST_DOMINATORS))
616     add_to_dominance_info (CDI_POST_DOMINATORS, ret);
617
618   return ret;
619 }
620
621 /* Creates an empty basic block just after basic block AFTER.  */
622
623 basic_block
624 create_empty_bb (basic_block after)
625 {
626   return create_basic_block (NULL, NULL, after);
627 }
628
629 /* Checks whether we may merge blocks BB1 and BB2.  */
630
631 bool
632 can_merge_blocks_p (basic_block bb1, basic_block bb2)
633 {
634   bool ret;
635
636   if (!cfg_hooks->can_merge_blocks_p)
637     internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
638
639   ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
640
641   return ret;
642 }
643
644 void
645 predict_edge (edge e, enum br_predictor predictor, int probability)
646 {
647   if (!cfg_hooks->predict_edge)
648     internal_error ("%s does not support predict_edge", cfg_hooks->name);
649
650   cfg_hooks->predict_edge (e, predictor, probability);
651 }
652
653 bool
654 predicted_by_p (const_basic_block bb, enum br_predictor predictor)
655 {
656   if (!cfg_hooks->predict_edge)
657     internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
658
659   return cfg_hooks->predicted_by_p (bb, predictor);
660 }
661
662 /* Merges basic block B into basic block A.  */
663
664 void
665 merge_blocks (basic_block a, basic_block b)
666 {
667   edge e;
668   edge_iterator ei;
669
670   if (!cfg_hooks->merge_blocks)
671     internal_error ("%s does not support merge_blocks", cfg_hooks->name);
672
673   cfg_hooks->merge_blocks (a, b);
674
675   if (current_loops != NULL)
676     remove_bb_from_loops (b);
677
678   /* Normally there should only be one successor of A and that is B, but
679      partway though the merge of blocks for conditional_execution we'll
680      be merging a TEST block with THEN and ELSE successors.  Free the
681      whole lot of them and hope the caller knows what they're doing.  */
682
683   while (EDGE_COUNT (a->succs) != 0)
684     remove_edge (EDGE_SUCC (a, 0));
685
686   /* Adjust the edges out of B for the new owner.  */
687   FOR_EACH_EDGE (e, ei, b->succs)
688     {
689       e->src = a;
690       if (current_loops != NULL)
691         rescan_loop_exit (e, true, false);
692     }
693   a->succs = b->succs;
694   a->flags |= b->flags;
695
696   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
697   b->preds = b->succs = NULL;
698
699   if (dom_info_available_p (CDI_DOMINATORS))
700     redirect_immediate_dominators (CDI_DOMINATORS, b, a);
701
702   if (dom_info_available_p (CDI_DOMINATORS))
703     delete_from_dominance_info (CDI_DOMINATORS, b);
704   if (dom_info_available_p (CDI_POST_DOMINATORS))
705     delete_from_dominance_info (CDI_POST_DOMINATORS, b);
706
707   expunge_block (b);
708 }
709
710 /* Split BB into entry part and the rest (the rest is the newly created block).
711    Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
712    part.  Returns the edge connecting the entry part to the rest.  */
713
714 edge
715 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
716                       void (*new_bb_cbk) (basic_block))
717 {
718   edge e, fallthru;
719   edge_iterator ei;
720   basic_block dummy, jump;
721   struct loop *loop, *ploop, *cloop;
722
723   if (!cfg_hooks->make_forwarder_block)
724     internal_error ("%s does not support make_forwarder_block",
725                     cfg_hooks->name);
726
727   fallthru = split_block_after_labels (bb);
728   dummy = fallthru->src;
729   bb = fallthru->dest;
730
731   /* Redirect back edges we want to keep.  */
732   for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
733     {
734       basic_block e_src;
735
736       if (redirect_edge_p (e))
737         {
738           ei_next (&ei);
739           continue;
740         }
741
742       dummy->frequency -= EDGE_FREQUENCY (e);
743       dummy->count -= e->count;
744       if (dummy->frequency < 0)
745         dummy->frequency = 0;
746       if (dummy->count < 0)
747         dummy->count = 0;
748       fallthru->count -= e->count;
749       if (fallthru->count < 0)
750         fallthru->count = 0;
751
752       e_src = e->src;
753       jump = redirect_edge_and_branch_force (e, bb);
754       if (jump != NULL)
755         {
756           /* If we redirected the loop latch edge, the JUMP block now acts like
757              the new latch of the loop.  */
758           if (current_loops != NULL
759               && dummy->loop_father != NULL
760               && dummy->loop_father->header == dummy
761               && dummy->loop_father->latch == e_src)
762             dummy->loop_father->latch = jump;
763           
764           if (new_bb_cbk != NULL)
765             new_bb_cbk (jump);
766         }
767     }
768
769   if (dom_info_available_p (CDI_DOMINATORS))
770     {
771       VEC (basic_block, heap) *doms_to_fix = VEC_alloc (basic_block, heap, 2);
772       VEC_quick_push (basic_block, doms_to_fix, dummy);
773       VEC_quick_push (basic_block, doms_to_fix, bb);
774       iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
775       VEC_free (basic_block, heap, doms_to_fix);
776     }
777
778   if (current_loops != NULL)
779     {
780       /* If we do not split a loop header, then both blocks belong to the
781          same loop.  In case we split loop header and do not redirect the
782          latch edge to DUMMY, then DUMMY belongs to the outer loop, and
783          BB becomes the new header.  If latch is not recorded for the loop,
784          we leave this updating on the caller (this may only happen during
785          loop analysis).  */
786       loop = dummy->loop_father;
787       if (loop->header == dummy
788           && loop->latch != NULL
789           && find_edge (loop->latch, dummy) == NULL)
790         {
791           remove_bb_from_loops (dummy);
792           loop->header = bb;
793
794           cloop = loop;
795           FOR_EACH_EDGE (e, ei, dummy->preds)
796             {
797               cloop = find_common_loop (cloop, e->src->loop_father);
798             }
799           add_bb_to_loop (dummy, cloop);
800         }
801
802       /* In case we split loop latch, update it.  */
803       for (ploop = loop; ploop; ploop = loop_outer (ploop))
804         if (ploop->latch == dummy)
805           ploop->latch = bb;
806     }
807
808   cfg_hooks->make_forwarder_block (fallthru);
809
810   return fallthru;
811 }
812
813 void
814 tidy_fallthru_edge (edge e)
815 {
816   if (cfg_hooks->tidy_fallthru_edge)
817     cfg_hooks->tidy_fallthru_edge (e);
818 }
819
820 /* Fix up edges that now fall through, or rather should now fall through
821    but previously required a jump around now deleted blocks.  Simplify
822    the search by only examining blocks numerically adjacent, since this
823    is how find_basic_blocks created them.  */
824
825 void
826 tidy_fallthru_edges (void)
827 {
828   basic_block b, c;
829
830   if (!cfg_hooks->tidy_fallthru_edge)
831     return;
832
833   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
834     return;
835
836   FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
837     {
838       edge s;
839
840       c = b->next_bb;
841
842       /* We care about simple conditional or unconditional jumps with
843          a single successor.
844
845          If we had a conditional branch to the next instruction when
846          find_basic_blocks was called, then there will only be one
847          out edge for the block which ended with the conditional
848          branch (since we do not create duplicate edges).
849
850          Furthermore, the edge will be marked as a fallthru because we
851          merge the flags for the duplicate edges.  So we do not want to
852          check that the edge is not a FALLTHRU edge.  */
853
854       if (single_succ_p (b))
855         {
856           s = single_succ_edge (b);
857           if (! (s->flags & EDGE_COMPLEX)
858               && s->dest == c
859               && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
860             tidy_fallthru_edge (s);
861         }
862     }
863 }
864
865 /* Returns true if we can duplicate basic block BB.  */
866
867 bool
868 can_duplicate_block_p (const_basic_block bb)
869 {
870   if (!cfg_hooks->can_duplicate_block_p)
871     internal_error ("%s does not support can_duplicate_block_p",
872                     cfg_hooks->name);
873
874   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
875     return false;
876
877   return cfg_hooks->can_duplicate_block_p (bb);
878 }
879
880 /* Duplicates basic block BB and redirects edge E to it.  Returns the
881    new basic block.  The new basic block is placed after the basic block
882    AFTER.  */
883
884 basic_block
885 duplicate_block (basic_block bb, edge e, basic_block after)
886 {
887   edge s, n;
888   basic_block new_bb;
889   gcov_type new_count = e ? e->count : 0;
890   edge_iterator ei;
891
892   if (!cfg_hooks->duplicate_block)
893     internal_error ("%s does not support duplicate_block",
894                     cfg_hooks->name);
895
896   if (bb->count < new_count)
897     new_count = bb->count;
898
899 #ifdef ENABLE_CHECKING
900   gcc_assert (can_duplicate_block_p (bb));
901 #endif
902
903   new_bb = cfg_hooks->duplicate_block (bb);
904   if (after)
905     move_block_after (new_bb, after);
906
907   new_bb->loop_depth = bb->loop_depth;
908   new_bb->flags = bb->flags;
909   FOR_EACH_EDGE (s, ei, bb->succs)
910     {
911       /* Since we are creating edges from a new block to successors
912          of another block (which therefore are known to be disjoint), there
913          is no need to actually check for duplicated edges.  */
914       n = unchecked_make_edge (new_bb, s->dest, s->flags);
915       n->probability = s->probability;
916       if (e && bb->count)
917         {
918           /* Take care for overflows!  */
919           n->count = s->count * (new_count * 10000 / bb->count) / 10000;
920           s->count -= n->count;
921         }
922       else
923         n->count = s->count;
924       n->aux = s->aux;
925     }
926
927   if (e)
928     {
929       new_bb->count = new_count;
930       bb->count -= new_count;
931
932       new_bb->frequency = EDGE_FREQUENCY (e);
933       bb->frequency -= EDGE_FREQUENCY (e);
934
935       redirect_edge_and_branch_force (e, new_bb);
936
937       if (bb->count < 0)
938         bb->count = 0;
939       if (bb->frequency < 0)
940         bb->frequency = 0;
941     }
942   else
943     {
944       new_bb->count = bb->count;
945       new_bb->frequency = bb->frequency;
946     }
947
948   set_bb_original (new_bb, bb);
949   set_bb_copy (bb, new_bb);
950
951   /* Add the new block to the copy of the loop of BB, or directly to the loop
952      of BB if the loop is not being copied.  */
953   if (current_loops != NULL)
954     {
955       struct loop *cloop = bb->loop_father;
956       struct loop *copy = get_loop_copy (cloop);
957       add_bb_to_loop (new_bb, copy ? copy : cloop);
958     }
959
960   return new_bb;
961 }
962
963 /* Return 1 if BB ends with a call, possibly followed by some
964    instructions that must stay with the call, 0 otherwise.  */
965
966 bool
967 block_ends_with_call_p (basic_block bb)
968 {
969   if (!cfg_hooks->block_ends_with_call_p)
970     internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
971
972   return (cfg_hooks->block_ends_with_call_p) (bb);
973 }
974
975 /* Return 1 if BB ends with a conditional branch, 0 otherwise.  */
976
977 bool
978 block_ends_with_condjump_p (const_basic_block bb)
979 {
980   if (!cfg_hooks->block_ends_with_condjump_p)
981     internal_error ("%s does not support block_ends_with_condjump_p",
982                     cfg_hooks->name);
983
984   return (cfg_hooks->block_ends_with_condjump_p) (bb);
985 }
986
987 /* Add fake edges to the function exit for any non constant and non noreturn
988    calls, volatile inline assembly in the bitmap of blocks specified by
989    BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
990    that were split.
991
992    The goal is to expose cases in which entering a basic block does not imply
993    that all subsequent instructions must be executed.  */
994
995 int
996 flow_call_edges_add (sbitmap blocks)
997 {
998   if (!cfg_hooks->flow_call_edges_add)
999     internal_error ("%s does not support flow_call_edges_add",
1000                     cfg_hooks->name);
1001
1002   return (cfg_hooks->flow_call_edges_add) (blocks);
1003 }
1004
1005 /* This function is called immediately after edge E is added to the
1006    edge vector E->dest->preds.  */
1007
1008 void
1009 execute_on_growing_pred (edge e)
1010 {
1011   if (cfg_hooks->execute_on_growing_pred)
1012     cfg_hooks->execute_on_growing_pred (e);
1013 }
1014
1015 /* This function is called immediately before edge E is removed from
1016    the edge vector E->dest->preds.  */
1017
1018 void
1019 execute_on_shrinking_pred (edge e)
1020 {
1021   if (cfg_hooks->execute_on_shrinking_pred)
1022     cfg_hooks->execute_on_shrinking_pred (e);
1023 }
1024
1025 /* This is used inside loop versioning when we want to insert
1026    stmts/insns on the edges, which have a different behavior
1027    in tree's and in RTL, so we made a CFG hook.  */
1028 void
1029 lv_flush_pending_stmts (edge e)
1030 {
1031   if (cfg_hooks->flush_pending_stmts)
1032     cfg_hooks->flush_pending_stmts (e);
1033 }
1034
1035 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1036    a new version of the loop basic-blocks, the parameters here are
1037    exactly the same as in duplicate_loop_to_header_edge or
1038    tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1039    additional work to maintain ssa information that's why there is
1040    a need to call the tree_duplicate_loop_to_header_edge rather
1041    than duplicate_loop_to_header_edge when we are in tree mode.  */
1042 bool
1043 cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
1044                                         unsigned int ndupl,
1045                                         sbitmap wont_exit, edge orig,
1046                                         VEC (edge, heap) **to_remove,
1047                                         int flags)
1048 {
1049   gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
1050   return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e,
1051                                                             ndupl, wont_exit,
1052                                                             orig, to_remove,
1053                                                             flags);
1054 }
1055
1056 /* Conditional jumps are represented differently in trees and RTL,
1057    this hook takes a basic block that is known to have a cond jump
1058    at its end and extracts the taken and not taken edges out of it
1059    and store it in E1 and E2 respectively.  */
1060 void
1061 extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1062 {
1063   gcc_assert (cfg_hooks->extract_cond_bb_edges);
1064   cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1065 }
1066
1067 /* Responsible for updating the ssa info (PHI nodes) on the
1068    new condition basic block that guards the versioned loop.  */
1069 void
1070 lv_adjust_loop_header_phi (basic_block first, basic_block second,
1071                            basic_block new_block, edge e)
1072 {
1073   if (cfg_hooks->lv_adjust_loop_header_phi)
1074     cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1075 }
1076
1077 /* Conditions in trees and RTL are different so we need
1078    a different handling when we add the condition to the
1079    versioning code.  */
1080 void
1081 lv_add_condition_to_bb (basic_block first, basic_block second,
1082                         basic_block new_block, void *cond)
1083 {
1084   gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1085   cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1086 }