gcc/cfg.c

   1 /* Control flow graph manipulation code for GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 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 the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This file contains low level functions to manipulate the CFG and
  23    analyze it.  All other modules should not transform the datastructure
  24    directly and use abstraction instead.  The file is supposed to be
  25    ordered bottom-up and should not contain any code dependent on a
  26    particular intermediate language (RTL or trees).
  27
  28    Available functionality:
  29      - Initialization/deallocation
  30          init_flow, clear_edges
  31      - Low level basic block manipulation
  32          alloc_block, expunge_block
  33      - Edge manipulation
  34          make_edge, make_single_succ_edge, cached_make_edge, remove_edge
  35          - Low level edge redirection (without updating instruction chain)
  36              redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
  37      - Dumping and debugging
  38          dump_flow_info, debug_flow_info, dump_edge_info
  39      - Allocation of AUX fields for basic blocks
  40          alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
  41  */
  42 \f
  43 #include "config.h"
  44 #include "system.h"
  45 #include "tree.h"
  46 #include "rtl.h"
  47 #include "hard-reg-set.h"
  48 #include "basic-block.h"
  49 #include "regs.h"
  50 #include "flags.h"
  51 #include "output.h"
  52 #include "function.h"
  53 #include "except.h"
  54 #include "toplev.h"
  55 #include "tm_p.h"
  56 #include "obstack.h"
  57
  58 /* The obstack on which the flow graph components are allocated.  */
  59
  60 struct obstack flow_obstack;
  61 static char *flow_firstobj;
  62
  63 /* Number of basic blocks in the current function.  */
  64
  65 int n_basic_blocks;
  66
  67 /* Number of edges in the current function.  */
  68
  69 int n_edges;
  70
  71 /* First edge in the deleted edges chain.  */
  72
  73 edge first_deleted_edge;
  74 static basic_block first_deleted_block;
  75
  76 /* The basic block array.  */
  77
  78 varray_type basic_block_info;
  79
  80 /* The special entry and exit blocks.  */
  81
  82 struct basic_block_def entry_exit_blocks[2]
  83 = {{NULL,                       /* head */
  84     NULL,                       /* end */
  85     NULL,                       /* head_tree */
  86     NULL,                       /* end_tree */
  87     NULL,                       /* pred */
  88     NULL,                       /* succ */
  89     NULL,                       /* local_set */
  90     NULL,                       /* cond_local_set */
  91     NULL,                       /* global_live_at_start */
  92     NULL,                       /* global_live_at_end */
  93     NULL,                       /* aux */
  94     ENTRY_BLOCK,                /* index */
  95     0,                          /* loop_depth */
  96     0,                          /* count */
  97     0,                          /* frequency */
  98     0                           /* flags */
  99   },
 100   {
 101     NULL,                       /* head */
 102     NULL,                       /* end */
 103     NULL,                       /* head_tree */
 104     NULL,                       /* end_tree */
 105     NULL,                       /* pred */
 106     NULL,                       /* succ */
 107     NULL,                       /* local_set */
 108     NULL,                       /* cond_local_set */
 109     NULL,                       /* global_live_at_start */
 110     NULL,                       /* global_live_at_end */
 111     NULL,                       /* aux */
 112     EXIT_BLOCK,                 /* index */
 113     0,                          /* loop_depth */
 114     0,                          /* count */
 115     0,                          /* frequency */
 116     0                           /* flags */
 117   }
 118 };
 119
 120 void debug_flow_info                    PARAMS ((void));
 121 static void free_edge                   PARAMS ((edge));
 122 \f
 123 /* Called once at initialization time.  */
 124
 125 void
 126 init_flow ()
 127 {
 128   static int initialized;
 129
 130   first_deleted_edge = 0;
 131   first_deleted_block = 0;
 132   n_edges = 0;
 133
 134   if (!initialized)
 135     {
 136       gcc_obstack_init (&flow_obstack);
 137       flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
 138       initialized = 1;
 139     }
 140   else
 141     {
 142       obstack_free (&flow_obstack, flow_firstobj);
 143       flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
 144     }
 145 }
 146 \f
 147 /* Helper function for remove_edge and clear_edges.  Frees edge structure
 148    without actually unlinking it from the pred/succ lists.  */
 149
 150 static void
 151 free_edge (e)
 152      edge e;
 153 {
 154   n_edges--;
 155   memset (e, 0, sizeof (*e));
 156   e->succ_next = first_deleted_edge;
 157   first_deleted_edge = e;
 158 }
 159
 160 /* Free the memory associated with the edge structures.  */
 161
 162 void
 163 clear_edges ()
 164 {
 165   int i;
 166   edge e;
 167
 168   for (i = 0; i < n_basic_blocks; ++i)
 169     {
 170       basic_block bb = BASIC_BLOCK (i);
 171       edge e = bb->succ;
 172
 173       while (e)
 174         {
 175           edge next = e->succ_next;
 176
 177           free_edge (e);
 178           e = next;
 179         }
 180       bb->succ = NULL;
 181       bb->pred = NULL;
 182     }
 183
 184   e = ENTRY_BLOCK_PTR->succ;
 185   while (e)
 186     {
 187       edge next = e->succ_next;
 188
 189       free_edge (e);
 190       e = next;
 191     }
 192   EXIT_BLOCK_PTR->pred = NULL;
 193   ENTRY_BLOCK_PTR->succ = NULL;
 194
 195   if (n_edges)
 196     abort ();
 197 }
 198 \f
 199 /* Allocate memory for basic_block.  */
 200
 201 basic_block
 202 alloc_block ()
 203 {
 204   basic_block bb;
 205
 206   if (first_deleted_block)
 207     {
 208       bb = first_deleted_block;
 209       first_deleted_block = (basic_block) bb->succ;
 210       bb->succ = NULL;
 211     }
 212   else
 213     {
 214       bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*bb));
 215       memset (bb, 0, sizeof (*bb));
 216     }
 217   return bb;
 218 }
 219
 220 /* Remove block B from the basic block array and compact behind it.  */
 221
 222 void
 223 expunge_block (b)
 224      basic_block b;
 225 {
 226   int i, n = n_basic_blocks;
 227
 228   for (i = b->index; i + 1 < n; ++i)
 229     {
 230       basic_block x = BASIC_BLOCK (i + 1);
 231       BASIC_BLOCK (i) = x;
 232       x->index = i;
 233     }
 234
 235   /* Invalidate data to make bughunting easier.  */
 236   memset (b, 0, sizeof (*b));
 237   b->index = -3;
 238   basic_block_info->num_elements--;
 239   n_basic_blocks--;
 240   b->succ = (edge) first_deleted_block;
 241   first_deleted_block = (basic_block) b;
 242 }
 243 \f
 244 /* Create an edge connecting SRC and DST with FLAGS optionally using
 245    edge cache CACHE.  Return the new edge, NULL if already exist.  */
 246
 247 edge
 248 cached_make_edge (edge_cache, src, dst, flags)
 249      sbitmap *edge_cache;
 250      basic_block src, dst;
 251      int flags;
 252 {
 253   int use_edge_cache;
 254   edge e;
 255
 256   /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
 257      many edges to them, and we didn't allocate memory for it.  */
 258   use_edge_cache = (edge_cache
 259                     && src != ENTRY_BLOCK_PTR
 260                     && dst != EXIT_BLOCK_PTR);
 261
 262   /* Make sure we don't add duplicate edges.  */
 263   switch (use_edge_cache)
 264     {
 265     default:
 266       /* Quick test for non-existence of the edge.  */
 267       if (! TEST_BIT (edge_cache[src->index], dst->index))
 268         break;
 269
 270       /* The edge exists; early exit if no work to do.  */
 271       if (flags == 0)
 272         return NULL;
 273
 274       /* FALLTHRU */
 275     case 0:
 276       for (e = src->succ; e; e = e->succ_next)
 277         if (e->dest == dst)
 278           {
 279             e->flags |= flags;
 280             return NULL;
 281           }
 282       break;
 283     }
 284
 285   if (first_deleted_edge)
 286     {
 287       e = first_deleted_edge;
 288       first_deleted_edge = e->succ_next;
 289     }
 290   else
 291     {
 292       e = (edge) obstack_alloc (&flow_obstack, sizeof (*e));
 293       memset (e, 0, sizeof (*e));
 294     }
 295   n_edges++;
 296
 297   e->succ_next = src->succ;
 298   e->pred_next = dst->pred;
 299   e->src = src;
 300   e->dest = dst;
 301   e->flags = flags;
 302
 303   src->succ = e;
 304   dst->pred = e;
 305
 306   if (use_edge_cache)
 307     SET_BIT (edge_cache[src->index], dst->index);
 308
 309   return e;
 310 }
 311
 312 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 313    created edge or NULL if already exist.  */
 314
 315 edge
 316 make_edge (src, dest, flags)
 317      basic_block src, dest;
 318      int flags;
 319 {
 320   return cached_make_edge (NULL, src, dest, flags);
 321 }
 322
 323 /* Create an edge connecting SRC to DEST and set probability by knowing
 324    that it is the single edge leaving SRC.  */
 325
 326 edge
 327 make_single_succ_edge (src, dest, flags)
 328      basic_block src, dest;
 329      int flags;
 330 {
 331   edge e = make_edge (src, dest, flags);
 332
 333   e->probability = REG_BR_PROB_BASE;
 334   e->count = src->count;
 335   return e;
 336 }
 337
 338 /* This function will remove an edge from the flow graph.  */
 339
 340 void
 341 remove_edge (e)
 342      edge e;
 343 {
 344   edge last_pred = NULL;
 345   edge last_succ = NULL;
 346   edge tmp;
 347   basic_block src, dest;
 348   src = e->src;
 349   dest = e->dest;
 350   for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
 351     last_succ = tmp;
 352
 353   if (!tmp)
 354     abort ();
 355   if (last_succ)
 356     last_succ->succ_next = e->succ_next;
 357   else
 358     src->succ = e->succ_next;
 359
 360   for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
 361     last_pred = tmp;
 362
 363   if (!tmp)
 364     abort ();
 365   if (last_pred)
 366     last_pred->pred_next = e->pred_next;
 367   else
 368     dest->pred = e->pred_next;
 369
 370   free_edge (e);
 371 }
 372
 373 /* Redirect an edge's successor from one block to another.  */
 374
 375 void
 376 redirect_edge_succ (e, new_succ)
 377      edge e;
 378      basic_block new_succ;
 379 {
 380   edge *pe;
 381
 382   /* Disconnect the edge from the old successor block.  */
 383   for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next)
 384     continue;
 385   *pe = (*pe)->pred_next;
 386
 387   /* Reconnect the edge to the new successor block.  */
 388   e->pred_next = new_succ->pred;
 389   new_succ->pred = e;
 390   e->dest = new_succ;
 391 }
 392
 393 /* Like previous but avoid possible duplicate edge.  */
 394
 395 edge
 396 redirect_edge_succ_nodup (e, new_succ)
 397      edge e;
 398      basic_block new_succ;
 399 {
 400   edge s;
 401   /* Check whether the edge is already present.  */
 402   for (s = e->src->succ; s; s = s->succ_next)
 403     if (s->dest == new_succ && s != e)
 404       break;
 405   if (s)
 406     {
 407       s->flags |= e->flags;
 408       s->probability += e->probability;
 409       s->count += e->count;
 410       remove_edge (e);
 411       e = s;
 412     }
 413   else
 414     redirect_edge_succ (e, new_succ);
 415   return e;
 416 }
 417
 418 /* Redirect an edge's predecessor from one block to another.  */
 419
 420 void
 421 redirect_edge_pred (e, new_pred)
 422      edge e;
 423      basic_block new_pred;
 424 {
 425   edge *pe;
 426
 427   /* Disconnect the edge from the old predecessor block.  */
 428   for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next)
 429     continue;
 430   *pe = (*pe)->succ_next;
 431
 432   /* Reconnect the edge to the new predecessor block.  */
 433   e->succ_next = new_pred->succ;
 434   new_pred->succ = e;
 435   e->src = new_pred;
 436 }
 437 \f
 438 void
 439 dump_flow_info (file)
 440      FILE *file;
 441 {
 442   int i;
 443   static const char * const reg_class_names[] = REG_CLASS_NAMES;
 444
 445   fprintf (file, "%d registers.\n", max_regno);
 446   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 447     if (REG_N_REFS (i))
 448       {
 449         enum reg_class class, altclass;
 450         fprintf (file, "\nRegister %d used %d times across %d insns",
 451                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
 452         if (REG_BASIC_BLOCK (i) >= 0)
 453           fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
 454         if (REG_N_SETS (i))
 455           fprintf (file, "; set %d time%s", REG_N_SETS (i),
 456                    (REG_N_SETS (i) == 1) ? "" : "s");
 457         if (REG_USERVAR_P (regno_reg_rtx[i]))
 458           fprintf (file, "; user var");
 459         if (REG_N_DEATHS (i) != 1)
 460           fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
 461         if (REG_N_CALLS_CROSSED (i) == 1)
 462           fprintf (file, "; crosses 1 call");
 463         else if (REG_N_CALLS_CROSSED (i))
 464           fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
 465         if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
 466           fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
 467         class = reg_preferred_class (i);
 468         altclass = reg_alternate_class (i);
 469         if (class != GENERAL_REGS || altclass != ALL_REGS)
 470           {
 471             if (altclass == ALL_REGS || class == ALL_REGS)
 472               fprintf (file, "; pref %s", reg_class_names[(int) class]);
 473             else if (altclass == NO_REGS)
 474               fprintf (file, "; %s or none", reg_class_names[(int) class]);
 475             else
 476               fprintf (file, "; pref %s, else %s",
 477                        reg_class_names[(int) class],
 478                        reg_class_names[(int) altclass]);
 479           }
 480         if (REG_POINTER (regno_reg_rtx[i]))
 481           fprintf (file, "; pointer");
 482         fprintf (file, ".\n");
 483       }
 484
 485   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
 486   for (i = 0; i < n_basic_blocks; i++)
 487     {
 488       basic_block bb = BASIC_BLOCK (i);
 489       edge e;
 490
 491       fprintf (file, "\nBasic block %d: first insn %d, last %d, loop_depth %d, count ",
 492                i, INSN_UID (bb->head), INSN_UID (bb->end), bb->loop_depth);
 493       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
 494       fprintf (file, ", freq %i.\n", bb->frequency);
 495
 496       fprintf (file, "Predecessors: ");
 497       for (e = bb->pred; e; e = e->pred_next)
 498         dump_edge_info (file, e, 0);
 499
 500       fprintf (file, "\nSuccessors: ");
 501       for (e = bb->succ; e; e = e->succ_next)
 502         dump_edge_info (file, e, 1);
 503
 504       fprintf (file, "\nRegisters live at start:");
 505       dump_regset (bb->global_live_at_start, file);
 506
 507       fprintf (file, "\nRegisters live at end:");
 508       dump_regset (bb->global_live_at_end, file);
 509
 510       putc ('\n', file);
 511     }
 512
 513   putc ('\n', file);
 514 }
 515
 516 void
 517 debug_flow_info ()
 518 {
 519   dump_flow_info (stderr);
 520 }
 521
 522 void
 523 dump_edge_info (file, e, do_succ)
 524      FILE *file;
 525      edge e;
 526      int do_succ;
 527 {
 528   basic_block side = (do_succ ? e->dest : e->src);
 529
 530   if (side == ENTRY_BLOCK_PTR)
 531     fputs (" ENTRY", file);
 532   else if (side == EXIT_BLOCK_PTR)
 533     fputs (" EXIT", file);
 534   else
 535     fprintf (file, " %d", side->index);
 536
 537   if (e->probability)
 538     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 539
 540   if (e->count)
 541     {
 542       fprintf (file, " count:");
 543       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) e->count);
 544     }
 545
 546   if (e->flags)
 547     {
 548       static const char * const bitnames[] = {
 549         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back"
 550       };
 551       int comma = 0;
 552       int i, flags = e->flags;
 553
 554       fputc (' ', file);
 555       fputc ('(', file);
 556       for (i = 0; flags; i++)
 557         if (flags & (1 << i))
 558           {
 559             flags &= ~(1 << i);
 560
 561             if (comma)
 562               fputc (',', file);
 563             if (i < (int) ARRAY_SIZE (bitnames))
 564               fputs (bitnames[i], file);
 565             else
 566               fprintf (file, "%d", i);
 567             comma = 1;
 568           }
 569       fputc (')', file);
 570     }
 571 }
 572 \f
 573 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 574 static struct obstack block_aux_obstack;
 575 static void *first_block_aux_obj = 0;
 576 static struct obstack edge_aux_obstack;
 577 static void *first_edge_aux_obj = 0;
 578
 579 /* Allocate an memory block of SIZE as BB->aux.  The obstack must
 580    be first initialized by alloc_aux_for_blocks.  */
 581
 582 inline void
 583 alloc_aux_for_block (bb, size)
 584      basic_block bb;
 585      int size;
 586 {
 587   /* Verify that aux field is clear.  */
 588   if (bb->aux || !first_block_aux_obj)
 589     abort ();
 590   bb->aux = obstack_alloc (&block_aux_obstack, size);
 591   memset (bb->aux, 0, size);
 592 }
 593
 594 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 595    alloc_aux_for_block for each basic block.  */
 596
 597 void
 598 alloc_aux_for_blocks (size)
 599      int size;
 600 {
 601   static int initialized;
 602
 603   if (!initialized)
 604     {
 605       gcc_obstack_init (&block_aux_obstack);
 606       initialized = 1;
 607     }
 608   /* Check whether AUX data are still allocated.  */
 609   else if (first_block_aux_obj)
 610     abort ();
 611   first_block_aux_obj = (char *) obstack_alloc (&block_aux_obstack, 0);
 612   if (size)
 613     {
 614       int i;
 615       for (i = 0; i < n_basic_blocks; i++)
 616         alloc_aux_for_block (BASIC_BLOCK (i), size);
 617       alloc_aux_for_block (ENTRY_BLOCK_PTR, size);
 618       alloc_aux_for_block (EXIT_BLOCK_PTR, size);
 619     }
 620 }
 621
 622 /* Clear AUX pointers of all blocks.  */
 623
 624 void
 625 clear_aux_for_blocks ()
 626 {
 627   int i;
 628
 629   for (i = 0; i < n_basic_blocks; i++)
 630     BASIC_BLOCK (i)->aux = NULL;
 631   ENTRY_BLOCK_PTR->aux = NULL;
 632   EXIT_BLOCK_PTR->aux = NULL;
 633 }
 634
 635 /* Free data allocated in block_aux_obstack and clear AUX pointers
 636    of all blocks.  */
 637
 638 void
 639 free_aux_for_blocks ()
 640 {
 641   if (!first_block_aux_obj)
 642     abort ();
 643   obstack_free (&block_aux_obstack, first_block_aux_obj);
 644   first_block_aux_obj = NULL;
 645
 646   clear_aux_for_blocks ();
 647 }
 648
 649 /* Allocate an memory edge of SIZE as BB->aux.  The obstack must
 650    be first initialized by alloc_aux_for_edges.  */
 651
 652 inline void
 653 alloc_aux_for_edge (e, size)
 654      edge e;
 655      int size;
 656 {
 657   /* Verify that aux field is clear.  */
 658   if (e->aux || !first_edge_aux_obj)
 659     abort ();
 660   e->aux = obstack_alloc (&edge_aux_obstack, size);
 661   memset (e->aux, 0, size);
 662 }
 663
 664 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 665    alloc_aux_for_edge for each basic edge.  */
 666
 667 void
 668 alloc_aux_for_edges (size)
 669      int size;
 670 {
 671   static int initialized;
 672
 673   if (!initialized)
 674     {
 675       gcc_obstack_init (&edge_aux_obstack);
 676       initialized = 1;
 677     }
 678   /* Check whether AUX data are still allocated.  */
 679   else if (first_edge_aux_obj)
 680     abort ();
 681   first_edge_aux_obj = (char *) obstack_alloc (&edge_aux_obstack, 0);
 682   if (size)
 683     {
 684       int i;
 685       for (i = -1; i < n_basic_blocks; i++)
 686         {
 687           basic_block bb;
 688           edge e;
 689
 690           if (i >= 0)
 691             bb = BASIC_BLOCK (i);
 692           else
 693             bb = ENTRY_BLOCK_PTR;
 694           for (e = bb->succ; e; e = e->succ_next)
 695             alloc_aux_for_edge (e, size);
 696         }
 697     }
 698 }
 699
 700 /* Clear AUX pointers of all edges.  */
 701
 702 void
 703 clear_aux_for_edges ()
 704 {
 705   int i;
 706
 707   for (i = -1; i < n_basic_blocks; i++)
 708     {
 709       basic_block bb;
 710       edge e;
 711
 712       if (i >= 0)
 713         bb = BASIC_BLOCK (i);
 714       else
 715         bb = ENTRY_BLOCK_PTR;
 716       for (e = bb->succ; e; e = e->succ_next)
 717         e->aux = NULL;
 718     }
 719 }
 720
 721 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 722    of all edges.  */
 723
 724 void
 725 free_aux_for_edges ()
 726 {
 727   if (!first_edge_aux_obj)
 728     abort ();
 729   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 730   first_edge_aux_obj = NULL;
 731
 732   clear_aux_for_edges ();
 733 }