gcc/cfghooks.c

   1 /* Hooks for cfg representation specific functions.
   2    Copyright (C) 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <s.pop@laposte.net>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  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 "timevar.h"
  30 #include "toplev.h"
  31
  32 /* A pointer to one of the hooks containers.  */
  33 static struct cfg_hooks *cfg_hooks;
  34
  35 /* Initialization of functions specific to the rtl IR.  */
  36 void
  37 rtl_register_cfg_hooks (void)
  38 {
  39   cfg_hooks = &rtl_cfg_hooks;
  40 }
  41
  42 /* Initialization of functions specific to the rtl IR.  */
  43 void
  44 cfg_layout_rtl_register_cfg_hooks (void)
  45 {
  46   cfg_hooks = &cfg_layout_rtl_cfg_hooks;
  47 }
  48
  49 /* Verify the CFG consistency.
  50
  51    Currently it does following: checks edge and basic block list correctness
  52    and calls into IL dependent checking then.  */
  53
  54 void
  55 verify_flow_info (void)
  56 {
  57   size_t *edge_checksum;
  58   int num_bb_notes, err = 0;
  59   basic_block bb, last_bb_seen;
  60   basic_block *last_visited;
  61
  62   timevar_push (TV_CFG_VERIFY);
  63   last_visited = xcalloc (last_basic_block + 2, sizeof (basic_block));
  64   edge_checksum = xcalloc (last_basic_block + 2, sizeof (size_t));
  65
  66   /* Check bb chain & numbers.  */
  67   last_bb_seen = ENTRY_BLOCK_PTR;
  68   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
  69     {
  70       if (bb != EXIT_BLOCK_PTR
  71           && bb != BASIC_BLOCK (bb->index))
  72         {
  73           error ("bb %d on wrong place", bb->index);
  74           err = 1;
  75         }
  76
  77       if (bb->prev_bb != last_bb_seen)
  78         {
  79           error ("prev_bb of %d should be %d, not %d",
  80                  bb->index, last_bb_seen->index, bb->prev_bb->index);
  81           err = 1;
  82         }
  83
  84       last_bb_seen = bb;
  85     }
  86
  87   /* Now check the basic blocks (boundaries etc.) */
  88   FOR_EACH_BB_REVERSE (bb)
  89     {
  90       int n_fallthru = 0;
  91       edge e;
  92
  93       if (bb->count < 0)
  94         {
  95           error ("verify_flow_info: Wrong count of block %i %i",
  96                  bb->index, (int)bb->count);
  97           err = 1;
  98         }
  99       if (bb->frequency < 0)
 100         {
 101           error ("verify_flow_info: Wrong frequency of block %i %i",
 102                  bb->index, bb->frequency);
 103           err = 1;
 104         }
 105       for (e = bb->succ; e; e = e->succ_next)
 106         {
 107           if (last_visited [e->dest->index + 2] == bb)
 108             {
 109               error ("verify_flow_info: Duplicate edge %i->%i",
 110                      e->src->index, e->dest->index);
 111               err = 1;
 112             }
 113           if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
 114             {
 115               error ("verify_flow_info: Wrong probability of edge %i->%i %i",
 116                      e->src->index, e->dest->index, e->probability);
 117               err = 1;
 118             }
 119           if (e->count < 0)
 120             {
 121               error ("verify_flow_info: Wrong count of edge %i->%i %i",
 122                      e->src->index, e->dest->index, (int)e->count);
 123               err = 1;
 124             }
 125
 126           last_visited [e->dest->index + 2] = bb;
 127
 128           if (e->flags & EDGE_FALLTHRU)
 129             n_fallthru++;
 130
 131           if (e->src != bb)
 132             {
 133               error ("verify_flow_info: Basic block %d succ edge is corrupted",
 134                      bb->index);
 135               fprintf (stderr, "Predecessor: ");
 136               dump_edge_info (stderr, e, 0);
 137               fprintf (stderr, "\nSuccessor: ");
 138               dump_edge_info (stderr, e, 1);
 139               fprintf (stderr, "\n");
 140               err = 1;
 141             }
 142
 143           edge_checksum[e->dest->index + 2] += (size_t) e;
 144         }
 145       if (n_fallthru > 1)
 146         {
 147           error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
 148           err = 1;
 149         }
 150
 151       for (e = bb->pred; e; e = e->pred_next)
 152         {
 153           if (e->dest != bb)
 154             {
 155               error ("basic block %d pred edge is corrupted", bb->index);
 156               fputs ("Predecessor: ", stderr);
 157               dump_edge_info (stderr, e, 0);
 158               fputs ("\nSuccessor: ", stderr);
 159               dump_edge_info (stderr, e, 1);
 160               fputc ('\n', stderr);
 161               err = 1;
 162             }
 163           edge_checksum[e->dest->index + 2] -= (size_t) e;
 164         }
 165     }
 166
 167   /* Complete edge checksumming for ENTRY and EXIT.  */
 168   {
 169     edge e;
 170
 171     for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
 172       edge_checksum[e->dest->index + 2] += (size_t) e;
 173
 174     for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
 175       edge_checksum[e->dest->index + 2] -= (size_t) e;
 176   }
 177
 178   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 179     if (edge_checksum[bb->index + 2])
 180       {
 181         error ("basic block %i edge lists are corrupted", bb->index);
 182         err = 1;
 183       }
 184
 185   num_bb_notes = 0;
 186   last_bb_seen = ENTRY_BLOCK_PTR;
 187
 188   /* Clean up.  */
 189   free (last_visited);
 190   free (edge_checksum);
 191
 192   if (cfg_hooks->verify_flow_info)
 193     err |= cfg_hooks->verify_flow_info ();
 194   if (err)
 195     internal_error ("verify_flow_info failed");
 196   timevar_pop (TV_CFG_VERIFY);
 197 }
 198
 199 /* Print out one basic block.  This function takes care of the purely
 200    graph related information.  The cfg hook for the active representation
 201    should dump representation-specific information.  */
 202
 203 void
 204 dump_bb (basic_block bb, FILE *outf, int indent)
 205 {
 206   edge e;
 207   char *s_indent;
 208
 209   s_indent = (char *) alloca ((size_t) indent + 1);
 210   memset ((void *) s_indent, ' ', (size_t) indent);
 211   s_indent[indent] = '\0';
 212
 213   fprintf (outf, ";;%s basic block %d, loop depth %d, count ",
 214            s_indent, bb->index, bb->loop_depth);
 215   fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
 216   putc ('\n', outf);
 217
 218   fprintf (outf, ";;%s prev block ", s_indent);
 219   if (bb->prev_bb)
 220     fprintf (outf, "%d, ", bb->prev_bb->index);
 221   else
 222     fprintf (outf, "(nil), ");
 223   fprintf (outf, "next block ");
 224   if (bb->next_bb)
 225     fprintf (outf, "%d", bb->next_bb->index);
 226   else
 227     fprintf (outf, "(nil)");
 228   putc ('\n', outf);
 229
 230   fprintf (outf, ";;%s pred:      ", s_indent);
 231   for (e = bb->pred; e; e = e->pred_next)
 232     dump_edge_info (outf, e, 0);
 233   putc ('\n', outf);
 234
 235   fprintf (outf, ";;%s succ:      ", s_indent);
 236   for (e = bb->succ; e; e = e->succ_next)
 237     dump_edge_info (outf, e, 1);
 238   putc ('\n', outf);
 239
 240   if (cfg_hooks->dump_bb)
 241     cfg_hooks->dump_bb (bb, outf, indent);
 242 }
 243
 244 /* Redirect edge E to the given basic block DEST and update underlying program
 245    representation.  Returns edge representing redirected branch (that may not
 246    be equivalent to E in the case of duplicate edges being removed) or NULL
 247    if edge is not easily redirectable for whatever reason.  */
 248
 249 bool
 250 redirect_edge_and_branch (edge e, basic_block dest)
 251 {
 252   bool ret;
 253
 254   if (!cfg_hooks->redirect_edge_and_branch)
 255     internal_error ("%s does not support redirect_edge_and_branch.",
 256                     cfg_hooks->name);
 257
 258   ret = cfg_hooks->redirect_edge_and_branch (e, dest);
 259
 260   return ret;
 261 }
 262
 263 /* Redirect the edge E to basic block DEST even if it requires creating
 264    of a new basic block; then it returns the newly created basic block.
 265    Aborts when redirection is impossible.  */
 266
 267 basic_block
 268 redirect_edge_and_branch_force (edge e, basic_block dest)
 269 {
 270   basic_block ret;
 271
 272   if (!cfg_hooks->redirect_edge_and_branch_force)
 273     internal_error ("%s does not support redirect_edge_and_branch_force.",
 274                     cfg_hooks->name);
 275
 276   ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
 277
 278   return ret;
 279 }
 280
 281 /* Splits basic block BB after the specified instruction I (but at least after
 282    the labels).  If I is NULL, splits just after labels.  The newly created edge
 283    is returned.  The new basic block is created just after the old one.  */
 284
 285 edge
 286 split_block (basic_block bb, void *i)
 287 {
 288   basic_block new_bb;
 289   edge e;
 290
 291   if (!cfg_hooks->split_block)
 292     internal_error ("%s does not support split_block.", cfg_hooks->name);
 293
 294   new_bb = cfg_hooks->split_block (bb, i);
 295   if (!new_bb)
 296     return NULL;
 297
 298   new_bb->count = bb->count;
 299   new_bb->frequency = bb->frequency;
 300   new_bb->loop_depth = bb->loop_depth;
 301
 302   if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
 303     {
 304       redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
 305       set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
 306     }
 307
 308   e = make_edge (bb, new_bb, EDGE_FALLTHRU);
 309   e->probability = REG_BR_PROB_BASE;
 310   e->count = bb->count;
 311
 312   return e;
 313 }
 314
 315 /* Splits block BB just after labels.  The newly created edge is returned.  */
 316
 317 edge
 318 split_block_after_labels (basic_block bb)
 319 {
 320   return split_block (bb, NULL);
 321 }
 322
 323 /* Moves block BB immediatelly after block AFTER.  Returns false if the
 324    movement was impossible.  */
 325
 326 bool
 327 move_block_after (basic_block bb, basic_block after)
 328 {
 329   bool ret;
 330
 331   if (!cfg_hooks->move_block_after)
 332     internal_error ("%s does not support move_block_after.", cfg_hooks->name);
 333
 334   ret = cfg_hooks->move_block_after (bb, after);
 335
 336   return ret;
 337 }
 338
 339 /* Deletes the basic block BB.  */
 340
 341 void
 342 delete_basic_block (basic_block bb)
 343 {
 344   if (!cfg_hooks->delete_basic_block)
 345     internal_error ("%s does not support delete_basic_block.", cfg_hooks->name);
 346
 347   cfg_hooks->delete_basic_block (bb);
 348
 349   /* Remove the edges into and out of this block.  Note that there may
 350      indeed be edges in, if we are removing an unreachable loop.  */
 351   while (bb->pred != NULL)
 352     remove_edge (bb->pred);
 353   while (bb->succ != NULL)
 354     remove_edge (bb->succ);
 355
 356   bb->pred = NULL;
 357   bb->succ = NULL;
 358
 359   if (dom_computed[CDI_DOMINATORS])
 360     delete_from_dominance_info (CDI_DOMINATORS, bb);
 361   if (dom_computed[CDI_POST_DOMINATORS])
 362     delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
 363
 364   /* Remove the basic block from the array.  */
 365   expunge_block (bb);
 366 }
 367
 368 /* Splits edge E and returns the newly created basic block.  */
 369
 370 basic_block
 371 split_edge (edge e)
 372 {
 373   basic_block ret;
 374   gcov_type count = e->count;
 375   int freq = EDGE_FREQUENCY (e);
 376
 377   if (!cfg_hooks->split_edge)
 378     internal_error ("%s does not support split_edge.", cfg_hooks->name);
 379
 380   ret = cfg_hooks->split_edge (e);
 381   ret->count = count;
 382   ret->frequency = freq;
 383   ret->succ->probability = REG_BR_PROB_BASE;
 384   ret->succ->count = count;
 385
 386   if (dom_computed[CDI_DOMINATORS])
 387     set_immediate_dominator (CDI_DOMINATORS, ret, ret->pred->src);
 388
 389   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
 390     set_immediate_dominator (CDI_DOMINATORS, ret->succ->dest,
 391                              recount_dominator (CDI_DOMINATORS,
 392                                                 ret->succ->dest));
 393
 394   return ret;
 395 }
 396
 397 /* Creates a new basic block just after the basic block AFTER.
 398    HEAD and END are the first and the last statement belonging
 399    to the block.  If both are NULL, an empty block is created.  */
 400
 401 basic_block
 402 create_basic_block (void *head, void *end, basic_block after)
 403 {
 404   basic_block ret;
 405
 406   if (!cfg_hooks->create_basic_block)
 407     internal_error ("%s does not support create_basic_block.", cfg_hooks->name);
 408
 409   ret = cfg_hooks->create_basic_block (head, end, after);
 410
 411   if (dom_computed[CDI_DOMINATORS])
 412     add_to_dominance_info (CDI_DOMINATORS, ret);
 413   if (dom_computed[CDI_POST_DOMINATORS])
 414     add_to_dominance_info (CDI_POST_DOMINATORS, ret);
 415
 416   return ret;
 417 }
 418
 419 /* Creates an empty basic block just after basic block AFTER.  */
 420
 421 basic_block
 422 create_empty_bb (basic_block after)
 423 {
 424   return create_basic_block (NULL, NULL, after);
 425 }
 426
 427 /* Checks whether we may merge blocks BB1 and BB2.  */
 428
 429 bool
 430 can_merge_blocks_p (basic_block bb1, basic_block bb2)
 431 {
 432   bool ret;
 433
 434   if (!cfg_hooks->can_merge_blocks_p)
 435     internal_error ("%s does not support can_merge_blocks_p.", cfg_hooks->name);
 436
 437   ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
 438
 439   return ret;
 440 }
 441
 442 /* Merges basic block B into basic block A.  */
 443
 444 void
 445 merge_blocks (basic_block a, basic_block b)
 446 {
 447   edge e;
 448
 449   if (!cfg_hooks->merge_blocks)
 450     internal_error ("%s does not support merge_blocks.", cfg_hooks->name);
 451
 452   cfg_hooks->merge_blocks (a, b);
 453
 454   /* Normally there should only be one successor of A and that is B, but
 455      partway though the merge of blocks for conditional_execution we'll
 456      be merging a TEST block with THEN and ELSE successors.  Free the
 457      whole lot of them and hope the caller knows what they're doing.  */
 458   while (a->succ)
 459     remove_edge (a->succ);
 460
 461   /* Adjust the edges out of B for the new owner.  */
 462   for (e = b->succ; e; e = e->succ_next)
 463     e->src = a;
 464   a->succ = b->succ;
 465   a->flags |= b->flags;
 466
 467   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
 468   b->pred = b->succ = NULL;
 469   a->global_live_at_end = b->global_live_at_end;
 470
 471   if (dom_computed[CDI_DOMINATORS])
 472     redirect_immediate_dominators (CDI_DOMINATORS, b, a);
 473
 474   if (dom_computed[CDI_DOMINATORS])
 475     delete_from_dominance_info (CDI_DOMINATORS, b);
 476   if (dom_computed[CDI_POST_DOMINATORS])
 477     delete_from_dominance_info (CDI_POST_DOMINATORS, b);
 478
 479   expunge_block (b);
 480 }
 481
 482 /* Split BB into entry part and the rest (the rest is the newly created block).
 483    Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
 484    part.  Returns the edge connecting the entry part to the rest.  */
 485
 486 edge
 487 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
 488                       void (*new_bb_cbk) (basic_block))
 489 {
 490   edge e, next_e, fallthru;
 491   basic_block dummy, jump;
 492
 493   if (!cfg_hooks->make_forwarder_block)
 494     internal_error ("%s does not support make_forwarder_block.",
 495                     cfg_hooks->name);
 496
 497   fallthru = split_block_after_labels (bb);
 498   dummy = fallthru->src;
 499   bb = fallthru->dest;
 500
 501   /* Redirect back edges we want to keep.  */
 502   for (e = dummy->pred; e; e = next_e)
 503     {
 504       next_e = e->pred_next;
 505       if (redirect_edge_p (e))
 506         continue;
 507
 508       dummy->frequency -= EDGE_FREQUENCY (e);
 509       dummy->count -= e->count;
 510       if (dummy->frequency < 0)
 511         dummy->frequency = 0;
 512       if (dummy->count < 0)
 513         dummy->count = 0;
 514
 515       jump = redirect_edge_and_branch_force (e, bb);
 516       if (jump)
 517         new_bb_cbk (jump);
 518     }
 519
 520   if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
 521     {
 522       basic_block doms_to_fix[2];
 523
 524       doms_to_fix[0] = dummy;
 525       doms_to_fix[1] = bb;
 526       iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2);
 527     }
 528
 529   cfg_hooks->make_forwarder_block (fallthru);
 530
 531   return fallthru;
 532 }
 533
 534 void
 535 tidy_fallthru_edge (edge e)
 536 {
 537   if (cfg_hooks->tidy_fallthru_edge)
 538     cfg_hooks->tidy_fallthru_edge (e);
 539 }
 540
 541 /* Fix up edges that now fall through, or rather should now fall through
 542    but previously required a jump around now deleted blocks.  Simplify
 543    the search by only examining blocks numerically adjacent, since this
 544    is how find_basic_blocks created them.  */
 545
 546 void
 547 tidy_fallthru_edges (void)
 548 {
 549   basic_block b, c;
 550
 551   if (!cfg_hooks->tidy_fallthru_edge)
 552     return;
 553
 554   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
 555     return;
 556
 557   FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
 558     {
 559       edge s;
 560
 561       c = b->next_bb;
 562
 563       /* We care about simple conditional or unconditional jumps with
 564          a single successor.
 565
 566          If we had a conditional branch to the next instruction when
 567          find_basic_blocks was called, then there will only be one
 568          out edge for the block which ended with the conditional
 569          branch (since we do not create duplicate edges).
 570
 571          Furthermore, the edge will be marked as a fallthru because we
 572          merge the flags for the duplicate edges.  So we do not want to
 573          check that the edge is not a FALLTHRU edge.  */
 574
 575       if ((s = b->succ) != NULL
 576           && ! (s->flags & EDGE_COMPLEX)
 577           && s->succ_next == NULL
 578           && s->dest == c)
 579         tidy_fallthru_edge (s);
 580     }
 581 }