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