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