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