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