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
 181       bb->succ = NULL;
 182       bb->pred = NULL;
 183     }
 184
 185   e = ENTRY_BLOCK_PTR->succ;
 186   while (e)
 187     {
 188       edge next = e->succ_next;
 189
 190       free_edge (e);
 191       e = next;
 192     }
 193
 194   EXIT_BLOCK_PTR->pred = NULL;
 195   ENTRY_BLOCK_PTR->succ = NULL;
 196
 197   if (n_edges)
 198     abort ();
 199 }
 200 \f
 201 /* Allocate memory for basic_block.  */
 202
 203 basic_block
 204 alloc_block ()
 205 {
 206   basic_block bb;
 207
 208   if (first_deleted_block)
 209     {
 210       bb = first_deleted_block;
 211       first_deleted_block = (basic_block) bb->succ;
 212       bb->succ = NULL;
 213     }
 214   else
 215     {
 216       bb = (basic_block) obstack_alloc (&flow_obstack, sizeof *bb);
 217       memset (bb, 0, sizeof *bb);
 218     }
 219   return bb;
 220 }
 221
 222 /* Remove block B from the basic block array and compact behind it.  */
 223
 224 void
 225 expunge_block (b)
 226      basic_block b;
 227 {
 228   int i, n = n_basic_blocks;
 229
 230   for (i = b->index; i + 1 < n; ++i)
 231     {
 232       basic_block x = BASIC_BLOCK (i + 1);
 233       BASIC_BLOCK (i) = x;
 234       x->index = i;
 235     }
 236
 237   /* Invalidate data to make bughunting easier.  */
 238   memset (b, 0, sizeof *b);
 239   b->index = -3;
 240   basic_block_info->num_elements--;
 241   n_basic_blocks--;
 242   b->succ = (edge) first_deleted_block;
 243   first_deleted_block = (basic_block) b;
 244 }
 245 \f
 246 /* Create an edge connecting SRC and DST with FLAGS optionally using
 247    edge cache CACHE.  Return the new edge, NULL if already exist.  */
 248
 249 edge
 250 cached_make_edge (edge_cache, src, dst, flags)
 251      sbitmap *edge_cache;
 252      basic_block src, dst;
 253      int flags;
 254 {
 255   int use_edge_cache;
 256   edge e;
 257
 258   /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
 259      many edges to them, or we didn't allocate memory for it.  */
 260   use_edge_cache = (edge_cache
 261                     && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR);
 262
 263   /* Make sure we don't add duplicate edges.  */
 264   switch (use_edge_cache)
 265     {
 266     default:
 267       /* Quick test for non-existence of the edge.  */
 268       if (! TEST_BIT (edge_cache[src->index], dst->index))
 269         break;
 270
 271       /* The edge exists; early exit if no work to do.  */
 272       if (flags == 0)
 273         return NULL;
 274
 275       /* FALLTHRU */
 276     case 0:
 277       for (e = src->succ; e; e = e->succ_next)
 278         if (e->dest == dst)
 279           {
 280             e->flags |= flags;
 281             return NULL;
 282           }
 283       break;
 284     }
 285
 286   if (first_deleted_edge)
 287     {
 288       e = first_deleted_edge;
 289       first_deleted_edge = e->succ_next;
 290     }
 291   else
 292     {
 293       e = (edge) obstack_alloc (&flow_obstack, sizeof *e);
 294       memset (e, 0, sizeof *e);
 295     }
 296   n_edges++;
 297
 298   e->succ_next = src->succ;
 299   e->pred_next = dst->pred;
 300   e->src = src;
 301   e->dest = dst;
 302   e->flags = flags;
 303
 304   src->succ = e;
 305   dst->pred = e;
 306
 307   if (use_edge_cache)
 308     SET_BIT (edge_cache[src->index], dst->index);
 309
 310   return e;
 311 }
 312
 313 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 314    created edge or NULL if already exist.  */
 315
 316 edge
 317 make_edge (src, dest, flags)
 318      basic_block src, dest;
 319      int flags;
 320 {
 321   return cached_make_edge (NULL, src, dest, flags);
 322 }
 323
 324 /* Create an edge connecting SRC to DEST and set probability by knowing
 325    that it is the single edge leaving SRC.  */
 326
 327 edge
 328 make_single_succ_edge (src, dest, flags)
 329      basic_block src, dest;
 330      int flags;
 331 {
 332   edge e = make_edge (src, dest, flags);
 333
 334   e->probability = REG_BR_PROB_BASE;
 335   e->count = src->count;
 336   return e;
 337 }
 338
 339 /* This function will remove an edge from the flow graph.  */
 340
 341 void
 342 remove_edge (e)
 343      edge e;
 344 {
 345   edge last_pred = NULL;
 346   edge last_succ = NULL;
 347   edge tmp;
 348   basic_block src, dest;
 349
 350   src = e->src;
 351   dest = e->dest;
 352   for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
 353     last_succ = tmp;
 354
 355   if (!tmp)
 356     abort ();
 357   if (last_succ)
 358     last_succ->succ_next = e->succ_next;
 359   else
 360     src->succ = e->succ_next;
 361
 362   for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
 363     last_pred = tmp;
 364
 365   if (!tmp)
 366     abort ();
 367   if (last_pred)
 368     last_pred->pred_next = e->pred_next;
 369   else
 370     dest->pred = e->pred_next;
 371
 372   free_edge (e);
 373 }
 374
 375 /* Redirect an edge's successor from one block to another.  */
 376
 377 void
 378 redirect_edge_succ (e, new_succ)
 379      edge e;
 380      basic_block new_succ;
 381 {
 382   edge *pe;
 383
 384   /* Disconnect the edge from the old successor block.  */
 385   for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next)
 386     continue;
 387   *pe = (*pe)->pred_next;
 388
 389   /* Reconnect the edge to the new successor block.  */
 390   e->pred_next = new_succ->pred;
 391   new_succ->pred = e;
 392   e->dest = new_succ;
 393 }
 394
 395 /* Like previous but avoid possible duplicate edge.  */
 396
 397 edge
 398 redirect_edge_succ_nodup (e, new_succ)
 399      edge e;
 400      basic_block new_succ;
 401 {
 402   edge s;
 403
 404   /* Check whether the edge is already present.  */
 405   for (s = e->src->succ; s; s = s->succ_next)
 406     if (s->dest == new_succ && s != e)
 407       break;
 408
 409   if (s)
 410     {
 411       s->flags |= e->flags;
 412       s->probability += e->probability;
 413       s->count += e->count;
 414       remove_edge (e);
 415       e = s;
 416     }
 417   else
 418     redirect_edge_succ (e, new_succ);
 419
 420   return e;
 421 }
 422
 423 /* Redirect an edge's predecessor from one block to another.  */
 424
 425 void
 426 redirect_edge_pred (e, new_pred)
 427      edge e;
 428      basic_block new_pred;
 429 {
 430   edge *pe;
 431
 432   /* Disconnect the edge from the old predecessor block.  */
 433   for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next)
 434     continue;
 435
 436   *pe = (*pe)->succ_next;
 437
 438   /* Reconnect the edge to the new predecessor block.  */
 439   e->succ_next = new_pred->succ;
 440   new_pred->succ = e;
 441   e->src = new_pred;
 442 }
 443 \f
 444 void
 445 dump_flow_info (file)
 446      FILE *file;
 447 {
 448   int i;
 449   static const char * const reg_class_names[] = REG_CLASS_NAMES;
 450
 451   fprintf (file, "%d registers.\n", max_regno);
 452   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 453     if (REG_N_REFS (i))
 454       {
 455         enum reg_class class, altclass;
 456
 457         fprintf (file, "\nRegister %d used %d times across %d insns",
 458                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
 459         if (REG_BASIC_BLOCK (i) >= 0)
 460           fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
 461         if (REG_N_SETS (i))
 462           fprintf (file, "; set %d time%s", REG_N_SETS (i),
 463                    (REG_N_SETS (i) == 1) ? "" : "s");
 464         if (REG_USERVAR_P (regno_reg_rtx[i]))
 465           fprintf (file, "; user var");
 466         if (REG_N_DEATHS (i) != 1)
 467           fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
 468         if (REG_N_CALLS_CROSSED (i) == 1)
 469           fprintf (file, "; crosses 1 call");
 470         else if (REG_N_CALLS_CROSSED (i))
 471           fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
 472         if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
 473           fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
 474
 475         class = reg_preferred_class (i);
 476         altclass = reg_alternate_class (i);
 477         if (class != GENERAL_REGS || altclass != ALL_REGS)
 478           {
 479             if (altclass == ALL_REGS || class == ALL_REGS)
 480               fprintf (file, "; pref %s", reg_class_names[(int) class]);
 481             else if (altclass == NO_REGS)
 482               fprintf (file, "; %s or none", reg_class_names[(int) class]);
 483             else
 484               fprintf (file, "; pref %s, else %s",
 485                        reg_class_names[(int) class],
 486                        reg_class_names[(int) altclass]);
 487           }
 488
 489         if (REG_POINTER (regno_reg_rtx[i]))
 490           fprintf (file, "; pointer");
 491         fprintf (file, ".\n");
 492       }
 493
 494   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
 495   for (i = 0; i < n_basic_blocks; i++)
 496     {
 497       basic_block bb = BASIC_BLOCK (i);
 498       edge e;
 499
 500       fprintf (file, "\nBasic block %d: first insn %d, last %d, ",
 501                i, INSN_UID (bb->head), INSN_UID (bb->end));
 502       fprintf (file, "loop_depth %d, count ", bb->loop_depth);
 503       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 504       fprintf (file, ", freq %i.\n", bb->frequency);
 505
 506       fprintf (file, "Predecessors: ");
 507       for (e = bb->pred; e; e = e->pred_next)
 508         dump_edge_info (file, e, 0);
 509
 510       fprintf (file, "\nSuccessors: ");
 511       for (e = bb->succ; e; e = e->succ_next)
 512         dump_edge_info (file, e, 1);
 513
 514       fprintf (file, "\nRegisters live at start:");
 515       dump_regset (bb->global_live_at_start, file);
 516
 517       fprintf (file, "\nRegisters live at end:");
 518       dump_regset (bb->global_live_at_end, file);
 519
 520       putc ('\n', file);
 521     }
 522
 523   putc ('\n', file);
 524 }
 525
 526 void
 527 debug_flow_info ()
 528 {
 529   dump_flow_info (stderr);
 530 }
 531
 532 void
 533 dump_edge_info (file, e, do_succ)
 534      FILE *file;
 535      edge e;
 536      int do_succ;
 537 {
 538   basic_block side = (do_succ ? e->dest : e->src);
 539
 540   if (side == ENTRY_BLOCK_PTR)
 541     fputs (" ENTRY", file);
 542   else if (side == EXIT_BLOCK_PTR)
 543     fputs (" EXIT", file);
 544   else
 545     fprintf (file, " %d", side->index);
 546
 547   if (e->probability)
 548     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 549
 550   if (e->count)
 551     {
 552       fprintf (file, " count:");
 553       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 554     }
 555
 556   if (e->flags)
 557     {
 558       static const char * const bitnames[]
 559         = {"fallthru", "ab", "abcall", "eh", "fake", "dfs_back"};
 560       int comma = 0;
 561       int i, flags = e->flags;
 562
 563       fputs (" (", file);
 564       for (i = 0; flags; i++)
 565         if (flags & (1 << i))
 566           {
 567             flags &= ~(1 << i);
 568
 569             if (comma)
 570               fputc (',', file);
 571             if (i < (int) ARRAY_SIZE (bitnames))
 572               fputs (bitnames[i], file);
 573             else
 574               fprintf (file, "%d", i);
 575             comma = 1;
 576           }
 577
 578       fputc (')', file);
 579     }
 580 }
 581 \f
 582 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 583
 584 static struct obstack block_aux_obstack;
 585 static void *first_block_aux_obj = 0;
 586 static struct obstack edge_aux_obstack;
 587 static void *first_edge_aux_obj = 0;
 588
 589 /* Allocate an memory block of SIZE as BB->aux.  The obstack must
 590    be first initialized by alloc_aux_for_blocks.  */
 591
 592 inline void
 593 alloc_aux_for_block (bb, size)
 594      basic_block bb;
 595      int size;
 596 {
 597   /* Verify that aux field is clear.  */
 598   if (bb->aux || !first_block_aux_obj)
 599     abort ();
 600   bb->aux = obstack_alloc (&block_aux_obstack, size);
 601   memset (bb->aux, 0, size);
 602 }
 603
 604 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 605    alloc_aux_for_block for each basic block.  */
 606
 607 void
 608 alloc_aux_for_blocks (size)
 609      int size;
 610 {
 611   static int initialized;
 612
 613   if (!initialized)
 614     {
 615       gcc_obstack_init (&block_aux_obstack);
 616       initialized = 1;
 617     }
 618
 619   /* Check whether AUX data are still allocated.  */
 620   else if (first_block_aux_obj)
 621     abort ();
 622   first_block_aux_obj = (char *) obstack_alloc (&block_aux_obstack, 0);
 623   if (size)
 624     {
 625       int i;
 626
 627       for (i = 0; i < n_basic_blocks; i++)
 628         alloc_aux_for_block (BASIC_BLOCK (i), size);
 629
 630       alloc_aux_for_block (ENTRY_BLOCK_PTR, size);
 631       alloc_aux_for_block (EXIT_BLOCK_PTR, size);
 632     }
 633 }
 634
 635 /* Clear AUX pointers of all blocks.  */
 636
 637 void
 638 clear_aux_for_blocks ()
 639 {
 640   int i;
 641
 642   for (i = 0; i < n_basic_blocks; i++)
 643     BASIC_BLOCK (i)->aux = NULL;
 644
 645   ENTRY_BLOCK_PTR->aux = NULL;
 646   EXIT_BLOCK_PTR->aux = NULL;
 647 }
 648
 649 /* Free data allocated in block_aux_obstack and clear AUX pointers
 650    of all blocks.  */
 651
 652 void
 653 free_aux_for_blocks ()
 654 {
 655   if (!first_block_aux_obj)
 656     abort ();
 657   obstack_free (&block_aux_obstack, first_block_aux_obj);
 658   first_block_aux_obj = NULL;
 659
 660   clear_aux_for_blocks ();
 661 }
 662
 663 /* Allocate an memory edge of SIZE as BB->aux.  The obstack must
 664    be first initialized by alloc_aux_for_edges.  */
 665
 666 inline void
 667 alloc_aux_for_edge (e, size)
 668      edge e;
 669      int size;
 670 {
 671   /* Verify that aux field is clear.  */
 672   if (e->aux || !first_edge_aux_obj)
 673     abort ();
 674   e->aux = obstack_alloc (&edge_aux_obstack, size);
 675   memset (e->aux, 0, size);
 676 }
 677
 678 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 679    alloc_aux_for_edge for each basic edge.  */
 680
 681 void
 682 alloc_aux_for_edges (size)
 683      int size;
 684 {
 685   static int initialized;
 686
 687   if (!initialized)
 688     {
 689       gcc_obstack_init (&edge_aux_obstack);
 690       initialized = 1;
 691     }
 692
 693   /* Check whether AUX data are still allocated.  */
 694   else if (first_edge_aux_obj)
 695     abort ();
 696
 697   first_edge_aux_obj = (char *) obstack_alloc (&edge_aux_obstack, 0);
 698   if (size)
 699     {
 700       int i;
 701       for (i = -1; i < n_basic_blocks; i++)
 702         {
 703           basic_block bb;
 704           edge e;
 705
 706           if (i >= 0)
 707             bb = BASIC_BLOCK (i);
 708           else
 709             bb = ENTRY_BLOCK_PTR;
 710
 711           for (e = bb->succ; e; e = e->succ_next)
 712             alloc_aux_for_edge (e, size);
 713         }
 714     }
 715 }
 716
 717 /* Clear AUX pointers of all edges.  */
 718
 719 void
 720 clear_aux_for_edges ()
 721 {
 722   int i;
 723
 724   for (i = -1; i < n_basic_blocks; i++)
 725     {
 726       basic_block bb;
 727       edge e;
 728
 729       if (i >= 0)
 730         bb = BASIC_BLOCK (i);
 731       else
 732         bb = ENTRY_BLOCK_PTR;
 733
 734       for (e = bb->succ; e; e = e->succ_next)
 735         e->aux = NULL;
 736     }
 737 }
 738
 739 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 740    of all edges.  */
 741
 742 void
 743 free_aux_for_edges ()
 744 {
 745   if (!first_edge_aux_obj)
 746     abort ();
 747   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 748   first_edge_aux_obj = NULL;
 749
 750   clear_aux_for_edges ();
 751 }