1132718Skan/* Hooks for cfg representation specific functions.
2169689Skan   Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3132718Skan   Contributed by Sebastian Pop <s.pop@laposte.net>
4132718Skan
5132718SkanThis file is part of GCC.
6132718Skan
7132718SkanGCC is free software; you can redistribute it and/or modify
8132718Skanit under the terms of the GNU General Public License as published by
9132718Skanthe Free Software Foundation; either version 2, or (at your option)
10132718Skanany later version.
11132718Skan
12132718SkanGCC is distributed in the hope that it will be useful,
13132718Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of
14132718SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15132718SkanGNU General Public License for more details.
16132718Skan
17132718SkanYou should have received a copy of the GNU General Public License
18132718Skanalong with GCC; see the file COPYING.  If not, write to
19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor,
20169689SkanBoston, MA 02110-1301, USA.  */
21132718Skan
22132718Skan#include "config.h"
23132718Skan#include "system.h"
24132718Skan#include "coretypes.h"
25132718Skan#include "tm.h"
26132718Skan#include "tree.h"
27132718Skan#include "rtl.h"
28132718Skan#include "basic-block.h"
29169689Skan#include "tree-flow.h"
30169689Skan#include "timevar.h"
31169689Skan#include "toplev.h"
32132718Skan
33132718Skan/* A pointer to one of the hooks containers.  */
34169689Skanstatic struct cfg_hooks *cfg_hooks;
35132718Skan
36132718Skan/* Initialization of functions specific to the rtl IR.  */
37132718Skanvoid
38132718Skanrtl_register_cfg_hooks (void)
39132718Skan{
40132718Skan  cfg_hooks = &rtl_cfg_hooks;
41132718Skan}
42132718Skan
43132718Skan/* Initialization of functions specific to the rtl IR.  */
44132718Skanvoid
45132718Skancfg_layout_rtl_register_cfg_hooks (void)
46132718Skan{
47132718Skan  cfg_hooks = &cfg_layout_rtl_cfg_hooks;
48132718Skan}
49169689Skan
50169689Skan/* Initialization of functions specific to the tree IR.  */
51169689Skan
52169689Skanvoid
53169689Skantree_register_cfg_hooks (void)
54169689Skan{
55169689Skan  cfg_hooks = &tree_cfg_hooks;
56169689Skan}
57169689Skan
58169689Skan/* Returns current ir type (rtl = 0, trees = 1).  */
59169689Skan
60169689Skanint
61169689Skanir_type (void)
62169689Skan{
63169689Skan  return cfg_hooks == &tree_cfg_hooks ? 1 : 0;
64169689Skan}
65169689Skan
66169689Skan/* Verify the CFG consistency.
67169689Skan
68169689Skan   Currently it does following: checks edge and basic block list correctness
69169689Skan   and calls into IL dependent checking then.  */
70169689Skan
71169689Skanvoid
72169689Skanverify_flow_info (void)
73169689Skan{
74169689Skan  size_t *edge_checksum;
75169689Skan  int err = 0;
76169689Skan  basic_block bb, last_bb_seen;
77169689Skan  basic_block *last_visited;
78169689Skan
79169689Skan  timevar_push (TV_CFG_VERIFY);
80169689Skan  last_visited = XCNEWVEC (basic_block, last_basic_block);
81169689Skan  edge_checksum = XCNEWVEC (size_t, last_basic_block);
82169689Skan
83169689Skan  /* Check bb chain & numbers.  */
84169689Skan  last_bb_seen = ENTRY_BLOCK_PTR;
85169689Skan  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
86169689Skan    {
87169689Skan      if (bb != EXIT_BLOCK_PTR
88169689Skan	  && bb != BASIC_BLOCK (bb->index))
89169689Skan	{
90169689Skan	  error ("bb %d on wrong place", bb->index);
91169689Skan	  err = 1;
92169689Skan	}
93169689Skan
94169689Skan      if (bb->prev_bb != last_bb_seen)
95169689Skan	{
96169689Skan	  error ("prev_bb of %d should be %d, not %d",
97169689Skan		 bb->index, last_bb_seen->index, bb->prev_bb->index);
98169689Skan	  err = 1;
99169689Skan	}
100169689Skan
101169689Skan      last_bb_seen = bb;
102169689Skan    }
103169689Skan
104169689Skan  /* Now check the basic blocks (boundaries etc.) */
105169689Skan  FOR_EACH_BB_REVERSE (bb)
106169689Skan    {
107169689Skan      int n_fallthru = 0;
108169689Skan      edge e;
109169689Skan      edge_iterator ei;
110169689Skan
111169689Skan      if (bb->count < 0)
112169689Skan	{
113169689Skan	  error ("verify_flow_info: Wrong count of block %i %i",
114169689Skan		 bb->index, (int)bb->count);
115169689Skan	  err = 1;
116169689Skan	}
117169689Skan      if (bb->frequency < 0)
118169689Skan	{
119169689Skan	  error ("verify_flow_info: Wrong frequency of block %i %i",
120169689Skan		 bb->index, bb->frequency);
121169689Skan	  err = 1;
122169689Skan	}
123169689Skan      FOR_EACH_EDGE (e, ei, bb->succs)
124169689Skan	{
125169689Skan	  if (last_visited [e->dest->index] == bb)
126169689Skan	    {
127169689Skan	      error ("verify_flow_info: Duplicate edge %i->%i",
128169689Skan		     e->src->index, e->dest->index);
129169689Skan	      err = 1;
130169689Skan	    }
131169689Skan	  if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
132169689Skan	    {
133169689Skan	      error ("verify_flow_info: Wrong probability of edge %i->%i %i",
134169689Skan		     e->src->index, e->dest->index, e->probability);
135169689Skan	      err = 1;
136169689Skan	    }
137169689Skan	  if (e->count < 0)
138169689Skan	    {
139169689Skan	      error ("verify_flow_info: Wrong count of edge %i->%i %i",
140169689Skan		     e->src->index, e->dest->index, (int)e->count);
141169689Skan	      err = 1;
142169689Skan	    }
143169689Skan
144169689Skan	  last_visited [e->dest->index] = bb;
145169689Skan
146169689Skan	  if (e->flags & EDGE_FALLTHRU)
147169689Skan	    n_fallthru++;
148169689Skan
149169689Skan	  if (e->src != bb)
150169689Skan	    {
151169689Skan	      error ("verify_flow_info: Basic block %d succ edge is corrupted",
152169689Skan		     bb->index);
153169689Skan	      fprintf (stderr, "Predecessor: ");
154169689Skan	      dump_edge_info (stderr, e, 0);
155169689Skan	      fprintf (stderr, "\nSuccessor: ");
156169689Skan	      dump_edge_info (stderr, e, 1);
157169689Skan	      fprintf (stderr, "\n");
158169689Skan	      err = 1;
159169689Skan	    }
160169689Skan
161169689Skan	  edge_checksum[e->dest->index] += (size_t) e;
162169689Skan	}
163169689Skan      if (n_fallthru > 1)
164169689Skan	{
165169689Skan	  error ("wrong amount of branch edges after unconditional jump %i", bb->index);
166169689Skan	  err = 1;
167169689Skan	}
168169689Skan
169169689Skan      FOR_EACH_EDGE (e, ei, bb->preds)
170169689Skan	{
171169689Skan	  if (e->dest != bb)
172169689Skan	    {
173169689Skan	      error ("basic block %d pred edge is corrupted", bb->index);
174169689Skan	      fputs ("Predecessor: ", stderr);
175169689Skan	      dump_edge_info (stderr, e, 0);
176169689Skan	      fputs ("\nSuccessor: ", stderr);
177169689Skan	      dump_edge_info (stderr, e, 1);
178169689Skan	      fputc ('\n', stderr);
179169689Skan	      err = 1;
180169689Skan	    }
181169689Skan
182169689Skan	  if (ei.index != e->dest_idx)
183169689Skan	    {
184169689Skan	      error ("basic block %d pred edge is corrupted", bb->index);
185169689Skan	      error ("its dest_idx should be %d, not %d",
186169689Skan		     ei.index, e->dest_idx);
187169689Skan	      fputs ("Predecessor: ", stderr);
188169689Skan	      dump_edge_info (stderr, e, 0);
189169689Skan	      fputs ("\nSuccessor: ", stderr);
190169689Skan	      dump_edge_info (stderr, e, 1);
191169689Skan	      fputc ('\n', stderr);
192169689Skan	      err = 1;
193169689Skan	    }
194169689Skan
195169689Skan	  edge_checksum[e->dest->index] -= (size_t) e;
196169689Skan	}
197169689Skan    }
198169689Skan
199169689Skan  /* Complete edge checksumming for ENTRY and EXIT.  */
200169689Skan  {
201169689Skan    edge e;
202169689Skan    edge_iterator ei;
203169689Skan
204169689Skan    FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
205169689Skan      edge_checksum[e->dest->index] += (size_t) e;
206169689Skan
207169689Skan    FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
208169689Skan      edge_checksum[e->dest->index] -= (size_t) e;
209169689Skan  }
210169689Skan
211169689Skan  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
212169689Skan    if (edge_checksum[bb->index])
213169689Skan      {
214169689Skan	error ("basic block %i edge lists are corrupted", bb->index);
215169689Skan	err = 1;
216169689Skan      }
217169689Skan
218169689Skan  last_bb_seen = ENTRY_BLOCK_PTR;
219169689Skan
220169689Skan  /* Clean up.  */
221169689Skan  free (last_visited);
222169689Skan  free (edge_checksum);
223169689Skan
224169689Skan  if (cfg_hooks->verify_flow_info)
225169689Skan    err |= cfg_hooks->verify_flow_info ();
226169689Skan  if (err)
227169689Skan    internal_error ("verify_flow_info failed");
228169689Skan  timevar_pop (TV_CFG_VERIFY);
229169689Skan}
230169689Skan
231169689Skan/* Print out one basic block.  This function takes care of the purely
232169689Skan   graph related information.  The cfg hook for the active representation
233169689Skan   should dump representation-specific information.  */
234169689Skan
235169689Skanvoid
236169689Skandump_bb (basic_block bb, FILE *outf, int indent)
237169689Skan{
238169689Skan  edge e;
239169689Skan  edge_iterator ei;
240169689Skan  char *s_indent;
241169689Skan
242169689Skan  s_indent = alloca ((size_t) indent + 1);
243169689Skan  memset (s_indent, ' ', (size_t) indent);
244169689Skan  s_indent[indent] = '\0';
245169689Skan
246169689Skan  fprintf (outf, ";;%s basic block %d, loop depth %d, count ",
247169689Skan	   s_indent, bb->index, bb->loop_depth);
248169689Skan  fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
249169689Skan  putc ('\n', outf);
250169689Skan
251169689Skan  fprintf (outf, ";;%s prev block ", s_indent);
252169689Skan  if (bb->prev_bb)
253169689Skan    fprintf (outf, "%d, ", bb->prev_bb->index);
254169689Skan  else
255169689Skan    fprintf (outf, "(nil), ");
256169689Skan  fprintf (outf, "next block ");
257169689Skan  if (bb->next_bb)
258169689Skan    fprintf (outf, "%d", bb->next_bb->index);
259169689Skan  else
260169689Skan    fprintf (outf, "(nil)");
261169689Skan  putc ('\n', outf);
262169689Skan
263169689Skan  fprintf (outf, ";;%s pred:      ", s_indent);
264169689Skan  FOR_EACH_EDGE (e, ei, bb->preds)
265169689Skan    dump_edge_info (outf, e, 0);
266169689Skan  putc ('\n', outf);
267169689Skan
268169689Skan  fprintf (outf, ";;%s succ:      ", s_indent);
269169689Skan  FOR_EACH_EDGE (e, ei, bb->succs)
270169689Skan    dump_edge_info (outf, e, 1);
271169689Skan  putc ('\n', outf);
272169689Skan
273169689Skan  if (cfg_hooks->dump_bb)
274169689Skan    cfg_hooks->dump_bb (bb, outf, indent);
275169689Skan}
276169689Skan
277169689Skan/* Redirect edge E to the given basic block DEST and update underlying program
278169689Skan   representation.  Returns edge representing redirected branch (that may not
279169689Skan   be equivalent to E in the case of duplicate edges being removed) or NULL
280169689Skan   if edge is not easily redirectable for whatever reason.  */
281169689Skan
282169689Skanedge
283169689Skanredirect_edge_and_branch (edge e, basic_block dest)
284169689Skan{
285169689Skan  edge ret;
286169689Skan
287169689Skan  if (!cfg_hooks->redirect_edge_and_branch)
288169689Skan    internal_error ("%s does not support redirect_edge_and_branch",
289169689Skan		    cfg_hooks->name);
290169689Skan
291169689Skan  ret = cfg_hooks->redirect_edge_and_branch (e, dest);
292169689Skan
293169689Skan  return ret;
294169689Skan}
295169689Skan
296169689Skan/* Redirect the edge E to basic block DEST even if it requires creating
297169689Skan   of a new basic block; then it returns the newly created basic block.
298169689Skan   Aborts when redirection is impossible.  */
299169689Skan
300169689Skanbasic_block
301169689Skanredirect_edge_and_branch_force (edge e, basic_block dest)
302169689Skan{
303169689Skan  basic_block ret;
304169689Skan
305169689Skan  if (!cfg_hooks->redirect_edge_and_branch_force)
306169689Skan    internal_error ("%s does not support redirect_edge_and_branch_force",
307169689Skan		    cfg_hooks->name);
308169689Skan
309169689Skan  ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
310169689Skan
311169689Skan  return ret;
312169689Skan}
313169689Skan
314169689Skan/* Splits basic block BB after the specified instruction I (but at least after
315169689Skan   the labels).  If I is NULL, splits just after labels.  The newly created edge
316169689Skan   is returned.  The new basic block is created just after the old one.  */
317169689Skan
318169689Skanedge
319169689Skansplit_block (basic_block bb, void *i)
320169689Skan{
321169689Skan  basic_block new_bb;
322169689Skan
323169689Skan  if (!cfg_hooks->split_block)
324169689Skan    internal_error ("%s does not support split_block", cfg_hooks->name);
325169689Skan
326169689Skan  new_bb = cfg_hooks->split_block (bb, i);
327169689Skan  if (!new_bb)
328169689Skan    return NULL;
329169689Skan
330169689Skan  new_bb->count = bb->count;
331169689Skan  new_bb->frequency = bb->frequency;
332169689Skan  new_bb->loop_depth = bb->loop_depth;
333169689Skan
334169689Skan  if (dom_info_available_p (CDI_DOMINATORS))
335169689Skan    {
336169689Skan      redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
337169689Skan      set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
338169689Skan    }
339169689Skan
340169689Skan  return make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
341169689Skan}
342169689Skan
343169689Skan/* Splits block BB just after labels.  The newly created edge is returned.  */
344169689Skan
345169689Skanedge
346169689Skansplit_block_after_labels (basic_block bb)
347169689Skan{
348169689Skan  return split_block (bb, NULL);
349169689Skan}
350169689Skan
351169689Skan/* Moves block BB immediately after block AFTER.  Returns false if the
352169689Skan   movement was impossible.  */
353169689Skan
354169689Skanbool
355169689Skanmove_block_after (basic_block bb, basic_block after)
356169689Skan{
357169689Skan  bool ret;
358169689Skan
359169689Skan  if (!cfg_hooks->move_block_after)
360169689Skan    internal_error ("%s does not support move_block_after", cfg_hooks->name);
361169689Skan
362169689Skan  ret = cfg_hooks->move_block_after (bb, after);
363169689Skan
364169689Skan  return ret;
365169689Skan}
366169689Skan
367169689Skan/* Deletes the basic block BB.  */
368169689Skan
369169689Skanvoid
370169689Skandelete_basic_block (basic_block bb)
371169689Skan{
372169689Skan  if (!cfg_hooks->delete_basic_block)
373169689Skan    internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
374169689Skan
375169689Skan  cfg_hooks->delete_basic_block (bb);
376169689Skan
377169689Skan  /* Remove the edges into and out of this block.  Note that there may
378169689Skan     indeed be edges in, if we are removing an unreachable loop.  */
379169689Skan  while (EDGE_COUNT (bb->preds) != 0)
380169689Skan    remove_edge (EDGE_PRED (bb, 0));
381169689Skan  while (EDGE_COUNT (bb->succs) != 0)
382169689Skan    remove_edge (EDGE_SUCC (bb, 0));
383169689Skan
384169689Skan  if (dom_computed[CDI_DOMINATORS])
385169689Skan    delete_from_dominance_info (CDI_DOMINATORS, bb);
386169689Skan  if (dom_computed[CDI_POST_DOMINATORS])
387169689Skan    delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
388169689Skan
389169689Skan  /* Remove the basic block from the array.  */
390169689Skan  expunge_block (bb);
391169689Skan}
392169689Skan
393169689Skan/* Splits edge E and returns the newly created basic block.  */
394169689Skan
395169689Skanbasic_block
396169689Skansplit_edge (edge e)
397169689Skan{
398169689Skan  basic_block ret;
399169689Skan  gcov_type count = e->count;
400169689Skan  int freq = EDGE_FREQUENCY (e);
401169689Skan  edge f;
402169689Skan  bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
403169689Skan
404169689Skan  if (!cfg_hooks->split_edge)
405169689Skan    internal_error ("%s does not support split_edge", cfg_hooks->name);
406169689Skan
407169689Skan  ret = cfg_hooks->split_edge (e);
408169689Skan  ret->count = count;
409169689Skan  ret->frequency = freq;
410169689Skan  single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
411169689Skan  single_succ_edge (ret)->count = count;
412169689Skan
413169689Skan  if (irr)
414169689Skan    {
415169689Skan      ret->flags |= BB_IRREDUCIBLE_LOOP;
416169689Skan      single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
417169689Skan      single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
418169689Skan    }
419169689Skan
420169689Skan  if (dom_computed[CDI_DOMINATORS])
421169689Skan    set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
422169689Skan
423169689Skan  if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
424169689Skan    {
425169689Skan      /* There are two cases:
426169689Skan
427169689Skan	 If the immediate dominator of e->dest is not e->src, it
428169689Skan	 remains unchanged.
429169689Skan
430169689Skan	 If immediate dominator of e->dest is e->src, it may become
431169689Skan	 ret, provided that all other predecessors of e->dest are
432169689Skan	 dominated by e->dest.  */
433169689Skan
434169689Skan      if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
435169689Skan	  == single_pred (ret))
436169689Skan	{
437169689Skan	  edge_iterator ei;
438169689Skan	  FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
439169689Skan	    {
440169689Skan	      if (f == single_succ_edge (ret))
441169689Skan		continue;
442169689Skan
443169689Skan	      if (!dominated_by_p (CDI_DOMINATORS, f->src,
444169689Skan				   single_succ (ret)))
445169689Skan		break;
446169689Skan	    }
447169689Skan
448169689Skan	  if (!f)
449169689Skan	    set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
450169689Skan	}
451169689Skan    };
452169689Skan
453169689Skan  return ret;
454169689Skan}
455169689Skan
456169689Skan/* Creates a new basic block just after the basic block AFTER.
457169689Skan   HEAD and END are the first and the last statement belonging
458169689Skan   to the block.  If both are NULL, an empty block is created.  */
459169689Skan
460169689Skanbasic_block
461169689Skancreate_basic_block (void *head, void *end, basic_block after)
462169689Skan{
463169689Skan  basic_block ret;
464169689Skan
465169689Skan  if (!cfg_hooks->create_basic_block)
466169689Skan    internal_error ("%s does not support create_basic_block", cfg_hooks->name);
467169689Skan
468169689Skan  ret = cfg_hooks->create_basic_block (head, end, after);
469169689Skan
470169689Skan  if (dom_computed[CDI_DOMINATORS])
471169689Skan    add_to_dominance_info (CDI_DOMINATORS, ret);
472169689Skan  if (dom_computed[CDI_POST_DOMINATORS])
473169689Skan    add_to_dominance_info (CDI_POST_DOMINATORS, ret);
474169689Skan
475169689Skan  return ret;
476169689Skan}
477169689Skan
478169689Skan/* Creates an empty basic block just after basic block AFTER.  */
479169689Skan
480169689Skanbasic_block
481169689Skancreate_empty_bb (basic_block after)
482169689Skan{
483169689Skan  return create_basic_block (NULL, NULL, after);
484169689Skan}
485169689Skan
486169689Skan/* Checks whether we may merge blocks BB1 and BB2.  */
487169689Skan
488169689Skanbool
489169689Skancan_merge_blocks_p (basic_block bb1, basic_block bb2)
490169689Skan{
491169689Skan  bool ret;
492169689Skan
493169689Skan  if (!cfg_hooks->can_merge_blocks_p)
494169689Skan    internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
495169689Skan
496169689Skan  ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
497169689Skan
498169689Skan  return ret;
499169689Skan}
500169689Skan
501169689Skanvoid
502169689Skanpredict_edge (edge e, enum br_predictor predictor, int probability)
503169689Skan{
504169689Skan  if (!cfg_hooks->predict_edge)
505169689Skan    internal_error ("%s does not support predict_edge", cfg_hooks->name);
506169689Skan
507169689Skan  cfg_hooks->predict_edge (e, predictor, probability);
508169689Skan}
509169689Skan
510169689Skanbool
511169689Skanpredicted_by_p (basic_block bb, enum br_predictor predictor)
512169689Skan{
513169689Skan  if (!cfg_hooks->predict_edge)
514169689Skan    internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
515169689Skan
516169689Skan  return cfg_hooks->predicted_by_p (bb, predictor);
517169689Skan}
518169689Skan
519169689Skan/* Merges basic block B into basic block A.  */
520169689Skan
521169689Skanvoid
522169689Skanmerge_blocks (basic_block a, basic_block b)
523169689Skan{
524169689Skan  edge e;
525169689Skan  edge_iterator ei;
526169689Skan
527169689Skan  if (!cfg_hooks->merge_blocks)
528169689Skan    internal_error ("%s does not support merge_blocks", cfg_hooks->name);
529169689Skan
530169689Skan  cfg_hooks->merge_blocks (a, b);
531169689Skan
532169689Skan  /* Normally there should only be one successor of A and that is B, but
533169689Skan     partway though the merge of blocks for conditional_execution we'll
534169689Skan     be merging a TEST block with THEN and ELSE successors.  Free the
535169689Skan     whole lot of them and hope the caller knows what they're doing.  */
536169689Skan
537169689Skan  while (EDGE_COUNT (a->succs) != 0)
538169689Skan   remove_edge (EDGE_SUCC (a, 0));
539169689Skan
540169689Skan  /* Adjust the edges out of B for the new owner.  */
541169689Skan  FOR_EACH_EDGE (e, ei, b->succs)
542169689Skan    e->src = a;
543169689Skan  a->succs = b->succs;
544169689Skan  a->flags |= b->flags;
545169689Skan
546169689Skan  /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
547169689Skan  b->preds = b->succs = NULL;
548169689Skan
549169689Skan  if (dom_computed[CDI_DOMINATORS])
550169689Skan    redirect_immediate_dominators (CDI_DOMINATORS, b, a);
551169689Skan
552169689Skan  if (dom_computed[CDI_DOMINATORS])
553169689Skan    delete_from_dominance_info (CDI_DOMINATORS, b);
554169689Skan  if (dom_computed[CDI_POST_DOMINATORS])
555169689Skan    delete_from_dominance_info (CDI_POST_DOMINATORS, b);
556169689Skan
557169689Skan  expunge_block (b);
558169689Skan}
559169689Skan
560169689Skan/* Split BB into entry part and the rest (the rest is the newly created block).
561169689Skan   Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
562169689Skan   part.  Returns the edge connecting the entry part to the rest.  */
563169689Skan
564169689Skanedge
565169689Skanmake_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
566169689Skan		      void (*new_bb_cbk) (basic_block))
567169689Skan{
568169689Skan  edge e, fallthru;
569169689Skan  edge_iterator ei;
570169689Skan  basic_block dummy, jump;
571169689Skan
572169689Skan  if (!cfg_hooks->make_forwarder_block)
573169689Skan    internal_error ("%s does not support make_forwarder_block",
574169689Skan		    cfg_hooks->name);
575169689Skan
576169689Skan  fallthru = split_block_after_labels (bb);
577169689Skan  dummy = fallthru->src;
578169689Skan  bb = fallthru->dest;
579169689Skan
580169689Skan  /* Redirect back edges we want to keep.  */
581169689Skan  for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
582169689Skan    {
583169689Skan      if (redirect_edge_p (e))
584169689Skan	{
585169689Skan	  ei_next (&ei);
586169689Skan	  continue;
587169689Skan	}
588169689Skan
589169689Skan      dummy->frequency -= EDGE_FREQUENCY (e);
590169689Skan      dummy->count -= e->count;
591169689Skan      if (dummy->frequency < 0)
592169689Skan	dummy->frequency = 0;
593169689Skan      if (dummy->count < 0)
594169689Skan	dummy->count = 0;
595169689Skan      fallthru->count -= e->count;
596169689Skan      if (fallthru->count < 0)
597169689Skan	fallthru->count = 0;
598169689Skan
599169689Skan      jump = redirect_edge_and_branch_force (e, bb);
600169689Skan      if (jump)
601169689Skan	new_bb_cbk (jump);
602169689Skan    }
603169689Skan
604169689Skan  if (dom_info_available_p (CDI_DOMINATORS))
605169689Skan    {
606169689Skan      basic_block doms_to_fix[2];
607169689Skan
608169689Skan      doms_to_fix[0] = dummy;
609169689Skan      doms_to_fix[1] = bb;
610169689Skan      iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2);
611169689Skan    }
612169689Skan
613169689Skan  cfg_hooks->make_forwarder_block (fallthru);
614169689Skan
615169689Skan  return fallthru;
616169689Skan}
617169689Skan
618169689Skanvoid
619169689Skantidy_fallthru_edge (edge e)
620169689Skan{
621169689Skan  if (cfg_hooks->tidy_fallthru_edge)
622169689Skan    cfg_hooks->tidy_fallthru_edge (e);
623169689Skan}
624169689Skan
625169689Skan/* Fix up edges that now fall through, or rather should now fall through
626169689Skan   but previously required a jump around now deleted blocks.  Simplify
627169689Skan   the search by only examining blocks numerically adjacent, since this
628169689Skan   is how find_basic_blocks created them.  */
629169689Skan
630169689Skanvoid
631169689Skantidy_fallthru_edges (void)
632169689Skan{
633169689Skan  basic_block b, c;
634169689Skan
635169689Skan  if (!cfg_hooks->tidy_fallthru_edge)
636169689Skan    return;
637169689Skan
638169689Skan  if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
639169689Skan    return;
640169689Skan
641169689Skan  FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
642169689Skan    {
643169689Skan      edge s;
644169689Skan
645169689Skan      c = b->next_bb;
646169689Skan
647169689Skan      /* We care about simple conditional or unconditional jumps with
648169689Skan	 a single successor.
649169689Skan
650169689Skan	 If we had a conditional branch to the next instruction when
651169689Skan	 find_basic_blocks was called, then there will only be one
652169689Skan	 out edge for the block which ended with the conditional
653169689Skan	 branch (since we do not create duplicate edges).
654169689Skan
655169689Skan	 Furthermore, the edge will be marked as a fallthru because we
656169689Skan	 merge the flags for the duplicate edges.  So we do not want to
657169689Skan	 check that the edge is not a FALLTHRU edge.  */
658169689Skan
659169689Skan      if (single_succ_p (b))
660169689Skan	{
661169689Skan	  s = single_succ_edge (b);
662169689Skan	  if (! (s->flags & EDGE_COMPLEX)
663169689Skan	      && s->dest == c
664169689Skan	      && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
665169689Skan	    tidy_fallthru_edge (s);
666169689Skan	}
667169689Skan    }
668169689Skan}
669169689Skan
670169689Skan/* Returns true if we can duplicate basic block BB.  */
671169689Skan
672169689Skanbool
673169689Skancan_duplicate_block_p (basic_block bb)
674169689Skan{
675169689Skan  edge e;
676169689Skan
677169689Skan  if (!cfg_hooks->can_duplicate_block_p)
678169689Skan    internal_error ("%s does not support can_duplicate_block_p",
679169689Skan		    cfg_hooks->name);
680169689Skan
681169689Skan  if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
682169689Skan    return false;
683169689Skan
684169689Skan  /* Duplicating fallthru block to exit would require adding a jump
685169689Skan     and splitting the real last BB.  */
686169689Skan  e = find_edge (bb, EXIT_BLOCK_PTR);
687169689Skan  if (e && (e->flags & EDGE_FALLTHRU))
688169689Skan    return false;
689169689Skan
690169689Skan  return cfg_hooks->can_duplicate_block_p (bb);
691169689Skan}
692169689Skan
693169689Skan/* Duplicates basic block BB and redirects edge E to it.  Returns the
694169689Skan   new basic block.  The new basic block is placed after the basic block
695169689Skan   AFTER.  */
696169689Skan
697169689Skanbasic_block
698169689Skanduplicate_block (basic_block bb, edge e, basic_block after)
699169689Skan{
700169689Skan  edge s, n;
701169689Skan  basic_block new_bb;
702169689Skan  gcov_type new_count = e ? e->count : 0;
703169689Skan  edge_iterator ei;
704169689Skan
705169689Skan  if (!cfg_hooks->duplicate_block)
706169689Skan    internal_error ("%s does not support duplicate_block",
707169689Skan		    cfg_hooks->name);
708169689Skan
709169689Skan  if (bb->count < new_count)
710169689Skan    new_count = bb->count;
711169689Skan
712169689Skan#ifdef ENABLE_CHECKING
713169689Skan  gcc_assert (can_duplicate_block_p (bb));
714169689Skan#endif
715169689Skan
716169689Skan  new_bb = cfg_hooks->duplicate_block (bb);
717169689Skan  if (after)
718169689Skan    move_block_after (new_bb, after);
719169689Skan
720169689Skan  new_bb->loop_depth = bb->loop_depth;
721169689Skan  new_bb->flags = bb->flags;
722169689Skan  FOR_EACH_EDGE (s, ei, bb->succs)
723169689Skan    {
724169689Skan      /* Since we are creating edges from a new block to successors
725169689Skan	 of another block (which therefore are known to be disjoint), there
726169689Skan	 is no need to actually check for duplicated edges.  */
727169689Skan      n = unchecked_make_edge (new_bb, s->dest, s->flags);
728169689Skan      n->probability = s->probability;
729169689Skan      if (e && bb->count)
730169689Skan	{
731169689Skan	  /* Take care for overflows!  */
732169689Skan	  n->count = s->count * (new_count * 10000 / bb->count) / 10000;
733169689Skan	  s->count -= n->count;
734169689Skan	}
735169689Skan      else
736169689Skan	n->count = s->count;
737169689Skan      n->aux = s->aux;
738169689Skan    }
739169689Skan
740169689Skan  if (e)
741169689Skan    {
742169689Skan      new_bb->count = new_count;
743169689Skan      bb->count -= new_count;
744169689Skan
745169689Skan      new_bb->frequency = EDGE_FREQUENCY (e);
746169689Skan      bb->frequency -= EDGE_FREQUENCY (e);
747169689Skan
748169689Skan      redirect_edge_and_branch_force (e, new_bb);
749169689Skan
750169689Skan      if (bb->count < 0)
751169689Skan	bb->count = 0;
752169689Skan      if (bb->frequency < 0)
753169689Skan	bb->frequency = 0;
754169689Skan    }
755169689Skan  else
756169689Skan    {
757169689Skan      new_bb->count = bb->count;
758169689Skan      new_bb->frequency = bb->frequency;
759169689Skan    }
760169689Skan
761169689Skan  set_bb_original (new_bb, bb);
762169689Skan  set_bb_copy (bb, new_bb);
763169689Skan
764169689Skan  return new_bb;
765169689Skan}
766169689Skan
767169689Skan/* Return 1 if BB ends with a call, possibly followed by some
768169689Skan   instructions that must stay with the call, 0 otherwise.  */
769169689Skan
770169689Skanbool
771169689Skanblock_ends_with_call_p (basic_block bb)
772169689Skan{
773169689Skan  if (!cfg_hooks->block_ends_with_call_p)
774169689Skan    internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
775169689Skan
776169689Skan  return (cfg_hooks->block_ends_with_call_p) (bb);
777169689Skan}
778169689Skan
779169689Skan/* Return 1 if BB ends with a conditional branch, 0 otherwise.  */
780169689Skan
781169689Skanbool
782169689Skanblock_ends_with_condjump_p (basic_block bb)
783169689Skan{
784169689Skan  if (!cfg_hooks->block_ends_with_condjump_p)
785169689Skan    internal_error ("%s does not support block_ends_with_condjump_p",
786169689Skan		    cfg_hooks->name);
787169689Skan
788169689Skan  return (cfg_hooks->block_ends_with_condjump_p) (bb);
789169689Skan}
790169689Skan
791169689Skan/* Add fake edges to the function exit for any non constant and non noreturn
792169689Skan   calls, volatile inline assembly in the bitmap of blocks specified by
793169689Skan   BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
794169689Skan   that were split.
795169689Skan
796169689Skan   The goal is to expose cases in which entering a basic block does not imply
797169689Skan   that all subsequent instructions must be executed.  */
798169689Skan
799169689Skanint
800169689Skanflow_call_edges_add (sbitmap blocks)
801169689Skan{
802169689Skan  if (!cfg_hooks->flow_call_edges_add)
803169689Skan    internal_error ("%s does not support flow_call_edges_add",
804169689Skan		    cfg_hooks->name);
805169689Skan
806169689Skan  return (cfg_hooks->flow_call_edges_add) (blocks);
807169689Skan}
808169689Skan
809169689Skan/* This function is called immediately after edge E is added to the
810169689Skan   edge vector E->dest->preds.  */
811169689Skan
812169689Skanvoid
813169689Skanexecute_on_growing_pred (edge e)
814169689Skan{
815169689Skan  if (cfg_hooks->execute_on_growing_pred)
816169689Skan    cfg_hooks->execute_on_growing_pred (e);
817169689Skan}
818169689Skan
819169689Skan/* This function is called immediately before edge E is removed from
820169689Skan   the edge vector E->dest->preds.  */
821169689Skan
822169689Skanvoid
823169689Skanexecute_on_shrinking_pred (edge e)
824169689Skan{
825169689Skan  if (cfg_hooks->execute_on_shrinking_pred)
826169689Skan    cfg_hooks->execute_on_shrinking_pred (e);
827169689Skan}
828169689Skan
829169689Skan/* This is used inside loop versioning when we want to insert
830169689Skan   stmts/insns on the edges, which have a different behavior
831169689Skan   in tree's and in RTL, so we made a CFG hook.  */
832169689Skanvoid
833169689Skanlv_flush_pending_stmts (edge e)
834169689Skan{
835169689Skan  if (cfg_hooks->flush_pending_stmts)
836169689Skan    cfg_hooks->flush_pending_stmts (e);
837169689Skan}
838169689Skan
839169689Skan/* Loop versioning uses the duplicate_loop_to_header_edge to create
840169689Skan   a new version of the loop basic-blocks, the parameters here are
841169689Skan   exactly the same as in duplicate_loop_to_header_edge or
842169689Skan   tree_duplicate_loop_to_header_edge; while in tree-ssa there is
843169689Skan   additional work to maintain ssa information that's why there is
844169689Skan   a need to call the tree_duplicate_loop_to_header_edge rather
845169689Skan   than duplicate_loop_to_header_edge when we are in tree mode.  */
846169689Skanbool
847169689Skancfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
848169689Skan					struct loops *loops, unsigned int ndupl,
849169689Skan					sbitmap wont_exit, edge orig,
850169689Skan					edge *to_remove,
851169689Skan					unsigned int *n_to_remove, int flags)
852169689Skan{
853169689Skan  gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
854169689Skan  return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e, loops,
855169689Skan							    ndupl, wont_exit,
856169689Skan							    orig, to_remove,
857169689Skan							    n_to_remove, flags);
858169689Skan}
859169689Skan
860169689Skan/* Conditional jumps are represented differently in trees and RTL,
861169689Skan   this hook takes a basic block that is known to have a cond jump
862169689Skan   at its end and extracts the taken and not taken eges out of it
863169689Skan   and store it in E1 and E2 respectively.  */
864169689Skanvoid
865169689Skanextract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
866169689Skan{
867169689Skan  gcc_assert (cfg_hooks->extract_cond_bb_edges);
868169689Skan  cfg_hooks->extract_cond_bb_edges (b, e1, e2);
869169689Skan}
870169689Skan
871169689Skan/* Responsible for updating the ssa info (PHI nodes) on the
872169689Skan   new condition basic block that guards the versioned loop.  */
873169689Skanvoid
874169689Skanlv_adjust_loop_header_phi (basic_block first, basic_block second,
875169689Skan			   basic_block new, edge e)
876169689Skan{
877169689Skan  if (cfg_hooks->lv_adjust_loop_header_phi)
878169689Skan    cfg_hooks->lv_adjust_loop_header_phi (first, second, new, e);
879169689Skan}
880169689Skan
881169689Skan/* Conditions in trees and RTL are different so we need
882169689Skan   a different handling when we add the condition to the
883169689Skan   versioning code.  */
884169689Skanvoid
885169689Skanlv_add_condition_to_bb (basic_block first, basic_block second,
886169689Skan			basic_block new, void *cond)
887169689Skan{
888169689Skan  gcc_assert (cfg_hooks->lv_add_condition_to_bb);
889169689Skan  cfg_hooks->lv_add_condition_to_bb (first, second, new, cond);
890169689Skan}
891