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 = alloca ((size_t) indent + 1);
 210   memset (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 immediately 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   edge f;
 377
 378   if (!cfg_hooks->split_edge)
 379     internal_error ("%s does not support split_edge.", cfg_hooks->name);
 380
 381   ret = cfg_hooks->split_edge (e);
 382   ret->count = count;
 383   ret->frequency = freq;
 384   ret->succ->probability = REG_BR_PROB_BASE;
 385   ret->succ->count = count;
 386
 387   if (dom_computed[CDI_DOMINATORS])
 388     set_immediate_dominator (CDI_DOMINATORS, ret, ret->pred->src);
 389
 390   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
 391     {
 392       /* There are two cases:
 393
 394          If the immediate dominator of e->dest is not e->src, it
 395          remains unchanged.
 396
 397          If immediate dominator of e->dest is e->src, it may become
 398          ret, provided that all other predecessors of e->dest are
 399          dominated by e->dest.  */
 400
 401       if (get_immediate_dominator (CDI_DOMINATORS, ret->succ->dest)
 402           == ret->pred->src)
 403         {
 404           for (f = ret->succ->dest->pred; f; f = f->pred_next)
 405             {
 406               if (f == ret->succ)
 407                 continue;
 408
 409               if (!dominated_by_p (CDI_DOMINATORS, f->src,
 410                                    ret->succ->dest))
 411                 break;
 412             }
 413
 414           if (!f)
 415             set_immediate_dominator (CDI_DOMINATORS, ret->succ->dest, ret);
 416         }
 417     };
 418
 419   return ret;
 420 }
 421
 422 /* Creates a new basic block just after the basic block AFTER.
 423    HEAD and END are the first and the last statement belonging
 424    to the block.  If both are NULL, an empty block is created.  */
 425
 426 basic_block
 427 create_basic_block (void *head, void *end, basic_block after)
 428 {
 429   basic_block ret;
 430
 431   if (!cfg_hooks->create_basic_block)
 432     internal_error ("%s does not support create_basic_block.", cfg_hooks->name);
 433
 434   ret = cfg_hooks->create_basic_block (head, end, after);
 435
 436   if (dom_computed[CDI_DOMINATORS])
 437     add_to_dominance_info (CDI_DOMINATORS, ret);
 438   if (dom_computed[CDI_POST_DOMINATORS])
 439     add_to_dominance_info (CDI_POST_DOMINATORS, ret);
 440
 441   return ret;
 442 }
 443
 444 /* Creates an empty basic block just after basic block AFTER.  */
 445
 446 basic_block
 447 create_empty_bb (basic_block after)
 448 {
 449   return create_basic_block (NULL, NULL, after);
 450 }
 451
 452 /* Checks whether we may merge blocks BB1 and BB2.  */
 453
 454 bool
 455 can_merge_blocks_p (basic_block bb1, basic_block bb2)
 456 {
 457   bool ret;
 458
 459   if (!cfg_hooks->can_merge_blocks_p)
 460     internal_error ("%s does not support can_merge_blocks_p.", cfg_hooks->name);
 461
 462   ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
 463
 464   return ret;
 465 }
 466
 467 /* Merges basic block B into basic block A.  */
 468
 469 void
 470 merge_blocks (basic_block a, basic_block b)
 471 {
 472   edge e;
 473
 474   if (!cfg_hooks->merge_blocks)
 475     internal_error ("%s does not support merge_blocks.", cfg_hooks->name);
 476
 477   cfg_hooks->merge_blocks (a, b);
 478
 479   /* Normally there should only be one successor of A and that is B, but
 480      partway though the merge of blocks for conditional_execution we'll
 481      be merging a TEST block with THEN and ELSE successors.  Free the
 482      whole lot of them and hope the caller knows what they're doing.  */
 483   while (a->succ)
 484     remove_edge (a->succ);
 485
 486   /* Adjust the edges out of B for the new owner.  */
 487   for (e = b->succ; e; e = e->succ_next)
 488     e->src = a;
 489   a->succ = b->succ;
 490   a->flags |= b->flags;
 491
 492   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
 493   b->pred = b->succ = NULL;
 494   a->global_live_at_end = b->global_live_at_end;
 495
 496   if (dom_computed[CDI_DOMINATORS])
 497     redirect_immediate_dominators (CDI_DOMINATORS, b, a);
 498
 499   if (dom_computed[CDI_DOMINATORS])
 500     delete_from_dominance_info (CDI_DOMINATORS, b);
 501   if (dom_computed[CDI_POST_DOMINATORS])
 502     delete_from_dominance_info (CDI_POST_DOMINATORS, b);
 503
 504   expunge_block (b);
 505 }
 506
 507 /* Split BB into entry part and the rest (the rest is the newly created block).
 508    Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
 509    part.  Returns the edge connecting the entry part to the rest.  */
 510
 511 edge
 512 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
 513                       void (*new_bb_cbk) (basic_block))
 514 {
 515   edge e, next_e, fallthru;
 516   basic_block dummy, jump;
 517
 518   if (!cfg_hooks->make_forwarder_block)
 519     internal_error ("%s does not support make_forwarder_block.",
 520                     cfg_hooks->name);
 521
 522   fallthru = split_block_after_labels (bb);
 523   dummy = fallthru->src;
 524   bb = fallthru->dest;
 525
 526   /* Redirect back edges we want to keep.  */
 527   for (e = dummy->pred; e; e = next_e)
 528     {
 529       next_e = e->pred_next;
 530       if (redirect_edge_p (e))
 531         continue;
 532
 533       dummy->frequency -= EDGE_FREQUENCY (e);
 534       dummy->count -= e->count;
 535       if (dummy->frequency < 0)
 536         dummy->frequency = 0;
 537       if (dummy->count < 0)
 538         dummy->count = 0;
 539
 540       jump = redirect_edge_and_branch_force (e, bb);
 541       if (jump)
 542         new_bb_cbk (jump);
 543     }
 544
 545   if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
 546     {
 547       basic_block doms_to_fix[2];
 548
 549       doms_to_fix[0] = dummy;
 550       doms_to_fix[1] = bb;
 551       iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2);
 552     }
 553
 554   cfg_hooks->make_forwarder_block (fallthru);
 555
 556   return fallthru;
 557 }
 558
 559 void
 560 tidy_fallthru_edge (edge e)
 561 {
 562   if (cfg_hooks->tidy_fallthru_edge)
 563     cfg_hooks->tidy_fallthru_edge (e);
 564 }
 565
 566 /* Fix up edges that now fall through, or rather should now fall through
 567    but previously required a jump around now deleted blocks.  Simplify
 568    the search by only examining blocks numerically adjacent, since this
 569    is how find_basic_blocks created them.  */
 570
 571 void
 572 tidy_fallthru_edges (void)
 573 {
 574   basic_block b, c;
 575
 576   if (!cfg_hooks->tidy_fallthru_edge)
 577     return;
 578
 579   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
 580     return;
 581
 582   FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
 583     {
 584       edge s;
 585
 586       c = b->next_bb;
 587
 588       /* We care about simple conditional or unconditional jumps with
 589          a single successor.
 590
 591          If we had a conditional branch to the next instruction when
 592          find_basic_blocks was called, then there will only be one
 593          out edge for the block which ended with the conditional
 594          branch (since we do not create duplicate edges).
 595
 596          Furthermore, the edge will be marked as a fallthru because we
 597          merge the flags for the duplicate edges.  So we do not want to
 598          check that the edge is not a FALLTHRU edge.  */
 599
 600       if ((s = b->succ) != NULL
 601           && ! (s->flags & EDGE_COMPLEX)
 602           && s->succ_next == NULL
 603           && s->dest == c)
 604         tidy_fallthru_edge (s);
 605     }
 606 }