gcc/df-problems.c

   1 /* Standard problems for dataflow support routines.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
   3    Free Software Foundation, Inc.
   4    Originally contributed by Michael P. Hayes
   5              (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
   6    Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
   7              and Kenneth Zadeck (zadeck@naturalbridge.com).
   8
   9 This file is part of GCC.
  10
  11 GCC is free software; you can redistribute it and/or modify it under
  12 the terms of the GNU General Public License as published by the Free
  13 Software Foundation; either version 3, or (at your option) any later
  14 version.
  15
  16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19 for more details.
  20
  21 You should have received a copy of the GNU General Public License
  22 along with GCC; see the file COPYING3.  If not see
  23 <http://www.gnu.org/licenses/>.  */
  24
  25 #include "config.h"
  26 #include "system.h"
  27 #include "coretypes.h"
  28 #include "tm.h"
  29 #include "rtl.h"
  30 #include "tm_p.h"
  31 #include "insn-config.h"
  32 #include "recog.h"
  33 #include "function.h"
  34 #include "regs.h"
  35 #include "output.h"
  36 #include "alloc-pool.h"
  37 #include "flags.h"
  38 #include "hard-reg-set.h"
  39 #include "basic-block.h"
  40 #include "sbitmap.h"
  41 #include "bitmap.h"
  42 #include "timevar.h"
  43 #include "df.h"
  44 #include "except.h"
  45 #include "dce.h"
  46 #include "vecprim.h"
  47
  48 /* Note that turning REG_DEAD_DEBUGGING on will cause
  49    gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
  50    addresses in the dumps.  */
  51 #if 0
  52 #define REG_DEAD_DEBUGGING
  53 #endif
  54
  55 #define DF_SPARSE_THRESHOLD 32
  56
  57 static bitmap seen_in_block = NULL;
  58 static bitmap seen_in_insn = NULL;
  59
  60 \f
  61 /*----------------------------------------------------------------------------
  62    Public functions access functions for the dataflow problems.
  63 ----------------------------------------------------------------------------*/
  64 /* Get the live at out set for BB no matter what problem happens to be
  65    defined.  This function is used by the register allocators who
  66    choose different dataflow problems depending on the optimization
  67    level.  */
  68
  69 bitmap
  70 df_get_live_out (basic_block bb)
  71 {
  72   gcc_assert (df_lr);
  73
  74   if (df_urec)
  75     return DF_RA_LIVE_OUT (bb);
  76   else if (df_live)
  77     return DF_LIVE_OUT (bb);
  78   else
  79     return DF_LR_OUT (bb);
  80 }
  81
  82 /* Get the live at in set for BB no matter what problem happens to be
  83    defined.  This function is used by the register allocators who
  84    choose different dataflow problems depending on the optimization
  85    level.  */
  86
  87 bitmap
  88 df_get_live_in (basic_block bb)
  89 {
  90   gcc_assert (df_lr);
  91
  92   if (df_urec)
  93     return DF_RA_LIVE_IN (bb);
  94   else if (df_live)
  95     return DF_LIVE_IN (bb);
  96   else
  97     return DF_LR_IN (bb);
  98 }
  99
 100 /* Get the live at top set for BB no matter what problem happens to be
 101    defined.  This function is used by the register allocators who
 102    choose different dataflow problems depending on the optimization
 103    level.  */
 104
 105 bitmap
 106 df_get_live_top (basic_block bb)
 107 {
 108   gcc_assert (df_lr);
 109
 110   if (df_urec)
 111     return DF_RA_LIVE_TOP (bb);
 112   else
 113     return DF_LR_TOP (bb);
 114 }
 115
 116
 117 /*----------------------------------------------------------------------------
 118    Utility functions.
 119 ----------------------------------------------------------------------------*/
 120
 121 /* Generic versions to get the void* version of the block info.  Only
 122    used inside the problem instance vectors.  */
 123
 124 /* Grow the bb_info array.  */
 125
 126 void
 127 df_grow_bb_info (struct dataflow *dflow)
 128 {
 129   unsigned int new_size = last_basic_block + 1;
 130   if (dflow->block_info_size < new_size)
 131     {
 132       new_size += new_size / 4;
 133       dflow->block_info = xrealloc (dflow->block_info,
 134                                     new_size *sizeof (void*));
 135       memset (dflow->block_info + dflow->block_info_size, 0,
 136               (new_size - dflow->block_info_size) *sizeof (void *));
 137       dflow->block_info_size = new_size;
 138     }
 139 }
 140
 141 /* Dump a def-use or use-def chain for REF to FILE.  */
 142
 143 void
 144 df_chain_dump (struct df_link *link, FILE *file)
 145 {
 146   fprintf (file, "{ ");
 147   for (; link; link = link->next)
 148     {
 149       fprintf (file, "%c%d(bb %d insn %d) ",
 150                DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
 151                DF_REF_ID (link->ref),
 152                DF_REF_BBNO (link->ref),
 153                DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
 154     }
 155   fprintf (file, "}");
 156 }
 157
 158
 159 /* Print some basic block info as part of df_dump.  */
 160
 161 void
 162 df_print_bb_index (basic_block bb, FILE *file)
 163 {
 164   edge e;
 165   edge_iterator ei;
 166
 167   fprintf (file, "\n( ");
 168     FOR_EACH_EDGE (e, ei, bb->preds)
 169     {
 170       basic_block pred = e->src;
 171       fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
 172     }
 173   fprintf (file, ")->[%d]->( ", bb->index);
 174   FOR_EACH_EDGE (e, ei, bb->succs)
 175     {
 176       basic_block succ = e->dest;
 177       fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
 178     }
 179   fprintf (file, ")\n");
 180 }
 181
 182
 183
 184 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
 185    up correctly. */
 186
 187 static void
 188 df_set_seen (void)
 189 {
 190   seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
 191   seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
 192 }
 193
 194
 195 static void
 196 df_unset_seen (void)
 197 {
 198   BITMAP_FREE (seen_in_block);
 199   BITMAP_FREE (seen_in_insn);
 200 }
 201
 202
 203 \f
 204 /*----------------------------------------------------------------------------
 205    REACHING DEFINITIONS
 206
 207    Find the locations in the function where each definition site for a
 208    pseudo reaches.  In and out bitvectors are built for each basic
 209    block.  The id field in the ref is used to index into these sets.
 210    See df.h for details.
 211    ----------------------------------------------------------------------------*/
 212
 213 /* See the comment at the top of the Reaching Uses problem for how the
 214    uses are represented in the kill sets. The same games are played
 215    here for the defs.  */
 216
 217 /* Private data used to compute the solution for this problem.  These
 218    data structures are not accessible outside of this module.  */
 219 struct df_rd_problem_data
 220 {
 221   /* The set of defs to regs invalidated by call.  */
 222   bitmap sparse_invalidated_by_call;
 223   /* The set of defs to regs invalidate by call for rd.  */
 224   bitmap dense_invalidated_by_call;
 225   /* An obstack for the bitmaps we need for this problem.  */
 226   bitmap_obstack rd_bitmaps;
 227 };
 228
 229 /* Set basic block info.  */
 230
 231 static void
 232 df_rd_set_bb_info (unsigned int index,
 233                    struct df_rd_bb_info *bb_info)
 234 {
 235   gcc_assert (df_rd);
 236   gcc_assert (index < df_rd->block_info_size);
 237   df_rd->block_info[index] = bb_info;
 238 }
 239
 240
 241 /* Free basic block info.  */
 242
 243 static void
 244 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
 245                     void *vbb_info)
 246 {
 247   struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
 248   if (bb_info)
 249     {
 250       BITMAP_FREE (bb_info->kill);
 251       BITMAP_FREE (bb_info->sparse_kill);
 252       BITMAP_FREE (bb_info->gen);
 253       BITMAP_FREE (bb_info->in);
 254       BITMAP_FREE (bb_info->out);
 255       pool_free (df_rd->block_pool, bb_info);
 256     }
 257 }
 258
 259
 260 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
 261    not touched unless the block is new.  */
 262
 263 static void
 264 df_rd_alloc (bitmap all_blocks)
 265 {
 266   unsigned int bb_index;
 267   bitmap_iterator bi;
 268   struct df_rd_problem_data *problem_data;
 269
 270   if (!df_rd->block_pool)
 271     df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
 272                                            sizeof (struct df_rd_bb_info), 50);
 273
 274   if (df_rd->problem_data)
 275     {
 276       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
 277       bitmap_clear (problem_data->sparse_invalidated_by_call);
 278       bitmap_clear (problem_data->dense_invalidated_by_call);
 279     }
 280   else
 281     {
 282       problem_data = XNEW (struct df_rd_problem_data);
 283       df_rd->problem_data = problem_data;
 284
 285       bitmap_obstack_initialize (&problem_data->rd_bitmaps);
 286       problem_data->sparse_invalidated_by_call
 287         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 288       problem_data->dense_invalidated_by_call
 289         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 290     }
 291
 292   df_grow_bb_info (df_rd);
 293
 294   /* Because of the clustering of all use sites for the same pseudo,
 295      we have to process all of the blocks before doing the
 296      analysis.  */
 297
 298   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 299     {
 300       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 301       if (bb_info)
 302         {
 303           bitmap_clear (bb_info->kill);
 304           bitmap_clear (bb_info->sparse_kill);
 305           bitmap_clear (bb_info->gen);
 306         }
 307       else
 308         {
 309           bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
 310           df_rd_set_bb_info (bb_index, bb_info);
 311           bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 312           bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 313           bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 314           bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 315           bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 316         }
 317     }
 318   df_rd->optional_p = true;
 319 }
 320
 321
 322 /* Process a list of DEFs for df_rd_bb_local_compute.  */
 323
 324 static void
 325 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
 326                                     struct df_ref **def_rec,
 327                                     enum df_ref_flags top_flag)
 328 {
 329   while (*def_rec)
 330     {
 331       struct df_ref *def = *def_rec;
 332       if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
 333         {
 334           unsigned int regno = DF_REF_REGNO (def);
 335           unsigned int begin = DF_DEFS_BEGIN (regno);
 336           unsigned int n_defs = DF_DEFS_COUNT (regno);
 337
 338           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
 339               || (regno >= FIRST_PSEUDO_REGISTER))
 340             {
 341               /* Only the last def(s) for a regno in the block has any
 342                  effect.  */
 343               if (!bitmap_bit_p (seen_in_block, regno))
 344                 {
 345                   /* The first def for regno in insn gets to knock out the
 346                      defs from other instructions.  */
 347                   if ((!bitmap_bit_p (seen_in_insn, regno))
 348                       /* If the def is to only part of the reg, it does
 349                          not kill the other defs that reach here.  */
 350                       && (!(DF_REF_FLAGS (def) &
 351                             (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
 352                     {
 353                       if (n_defs > DF_SPARSE_THRESHOLD)
 354                         {
 355                           bitmap_set_bit (bb_info->sparse_kill, regno);
 356                           bitmap_clear_range(bb_info->gen, begin, n_defs);
 357                         }
 358                       else
 359                         {
 360                           bitmap_set_range (bb_info->kill, begin, n_defs);
 361                           bitmap_clear_range (bb_info->gen, begin, n_defs);
 362                         }
 363                     }
 364
 365                   bitmap_set_bit (seen_in_insn, regno);
 366                   /* All defs for regno in the instruction may be put into
 367                      the gen set.  */
 368                   if (!(DF_REF_FLAGS (def)
 369                         & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
 370                     bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
 371                 }
 372             }
 373         }
 374       def_rec++;
 375     }
 376 }
 377
 378 /* Compute local reaching def info for basic block BB.  */
 379
 380 static void
 381 df_rd_bb_local_compute (unsigned int bb_index)
 382 {
 383   basic_block bb = BASIC_BLOCK (bb_index);
 384   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 385   rtx insn;
 386
 387   bitmap_clear (seen_in_block);
 388   bitmap_clear (seen_in_insn);
 389
 390   /* Artificials are only hard regs.  */
 391   if (!(df->changeable_flags & DF_NO_HARD_REGS))
 392     df_rd_bb_local_compute_process_def (bb_info,
 393                                         df_get_artificial_defs (bb_index),
 394                                         0);
 395
 396   FOR_BB_INSNS_REVERSE (bb, insn)
 397     {
 398       unsigned int uid = INSN_UID (insn);
 399
 400       if (!INSN_P (insn))
 401         continue;
 402
 403       df_rd_bb_local_compute_process_def (bb_info,
 404                                           DF_INSN_UID_DEFS (uid), 0);
 405
 406       /* This complex dance with the two bitmaps is required because
 407          instructions can assign twice to the same pseudo.  This
 408          generally happens with calls that will have one def for the
 409          result and another def for the clobber.  If only one vector
 410          is used and the clobber goes first, the result will be
 411          lost.  */
 412       bitmap_ior_into (seen_in_block, seen_in_insn);
 413       bitmap_clear (seen_in_insn);
 414     }
 415
 416   /* Process the artificial defs at the top of the block last since we
 417      are going backwards through the block and these are logically at
 418      the start.  */
 419   if (!(df->changeable_flags & DF_NO_HARD_REGS))
 420     df_rd_bb_local_compute_process_def (bb_info,
 421                                         df_get_artificial_defs (bb_index),
 422                                         DF_REF_AT_TOP);
 423 }
 424
 425
 426 /* Compute local reaching def info for each basic block within BLOCKS.  */
 427
 428 static void
 429 df_rd_local_compute (bitmap all_blocks)
 430 {
 431   unsigned int bb_index;
 432   bitmap_iterator bi;
 433   unsigned int regno;
 434   struct df_rd_problem_data *problem_data
 435     = (struct df_rd_problem_data *) df_rd->problem_data;
 436   bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
 437   bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
 438
 439   df_set_seen ();
 440
 441   df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
 442
 443   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 444     {
 445       df_rd_bb_local_compute (bb_index);
 446     }
 447
 448   /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
 449   EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
 450     {
 451       if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
 452         bitmap_set_bit (sparse_invalidated, regno);
 453       else
 454         bitmap_set_range (dense_invalidated,
 455                           DF_DEFS_BEGIN (regno),
 456                           DF_DEFS_COUNT (regno));
 457     }
 458   df_unset_seen ();
 459 }
 460
 461
 462 /* Initialize the solution bit vectors for problem.  */
 463
 464 static void
 465 df_rd_init_solution (bitmap all_blocks)
 466 {
 467   unsigned int bb_index;
 468   bitmap_iterator bi;
 469
 470   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 471     {
 472       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 473
 474       bitmap_copy (bb_info->out, bb_info->gen);
 475       bitmap_clear (bb_info->in);
 476     }
 477 }
 478
 479 /* In of target gets or of out of source.  */
 480
 481 static void
 482 df_rd_confluence_n (edge e)
 483 {
 484   bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
 485   bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
 486
 487   if (e->flags & EDGE_EH)
 488     {
 489       struct df_rd_problem_data *problem_data
 490         = (struct df_rd_problem_data *) df_rd->problem_data;
 491       bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
 492       bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
 493       bitmap_iterator bi;
 494       unsigned int regno;
 495       bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
 496
 497       bitmap_copy (tmp, op2);
 498       bitmap_and_compl_into (tmp, dense_invalidated);
 499
 500       EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
 501         {
 502           bitmap_clear_range (tmp,
 503                               DF_DEFS_BEGIN (regno),
 504                               DF_DEFS_COUNT (regno));
 505         }
 506       bitmap_ior_into (op1, tmp);
 507       BITMAP_FREE (tmp);
 508     }
 509   else
 510     bitmap_ior_into (op1, op2);
 511 }
 512
 513
 514 /* Transfer function.  */
 515
 516 static bool
 517 df_rd_transfer_function (int bb_index)
 518 {
 519   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 520   unsigned int regno;
 521   bitmap_iterator bi;
 522   bitmap in = bb_info->in;
 523   bitmap out = bb_info->out;
 524   bitmap gen = bb_info->gen;
 525   bitmap kill = bb_info->kill;
 526   bitmap sparse_kill = bb_info->sparse_kill;
 527
 528   if (bitmap_empty_p (sparse_kill))
 529     return  bitmap_ior_and_compl (out, gen, in, kill);
 530   else
 531     {
 532       struct df_rd_problem_data *problem_data;
 533       bool changed = false;
 534       bitmap tmp;
 535
 536       /* Note that TMP is _not_ a temporary bitmap if we end up replacing
 537          OUT with TMP.  Therefore, allocate TMP in the RD bitmaps obstack.  */
 538       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
 539       tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 540
 541       bitmap_copy (tmp, in);
 542       EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
 543         {
 544           bitmap_clear_range (tmp,
 545                               DF_DEFS_BEGIN (regno),
 546                               DF_DEFS_COUNT (regno));
 547         }
 548       bitmap_and_compl_into (tmp, kill);
 549       bitmap_ior_into (tmp, gen);
 550       changed = !bitmap_equal_p (tmp, out);
 551       if (changed)
 552         {
 553           BITMAP_FREE (out);
 554           bb_info->out = tmp;
 555         }
 556       else
 557           BITMAP_FREE (tmp);
 558       return changed;
 559     }
 560 }
 561
 562
 563 /* Free all storage associated with the problem.  */
 564
 565 static void
 566 df_rd_free (void)
 567 {
 568   unsigned int i;
 569   struct df_rd_problem_data *problem_data
 570     = (struct df_rd_problem_data *) df_rd->problem_data;
 571
 572   if (problem_data)
 573     {
 574       for (i = 0; i < df_rd->block_info_size; i++)
 575         {
 576           struct df_rd_bb_info *bb_info = df_rd_get_bb_info (i);
 577           if (bb_info)
 578             {
 579               BITMAP_FREE (bb_info->kill);
 580               BITMAP_FREE (bb_info->sparse_kill);
 581               BITMAP_FREE (bb_info->gen);
 582               BITMAP_FREE (bb_info->in);
 583               BITMAP_FREE (bb_info->out);
 584             }
 585         }
 586
 587       free_alloc_pool (df_rd->block_pool);
 588       BITMAP_FREE (problem_data->sparse_invalidated_by_call);
 589       BITMAP_FREE (problem_data->dense_invalidated_by_call);
 590       bitmap_obstack_release (&problem_data->rd_bitmaps);
 591
 592       df_rd->block_info_size = 0;
 593       free (df_rd->block_info);
 594       free (df_rd->problem_data);
 595     }
 596   free (df_rd);
 597 }
 598
 599
 600 /* Debugging info.  */
 601
 602 static void
 603 df_rd_start_dump (FILE *file)
 604 {
 605   struct df_rd_problem_data *problem_data
 606     = (struct df_rd_problem_data *) df_rd->problem_data;
 607   unsigned int m = DF_REG_SIZE(df);
 608   unsigned int regno;
 609
 610   if (!df_rd->block_info)
 611     return;
 612
 613   fprintf (file, ";; Reaching defs:\n\n");
 614
 615   fprintf (file, "  sparse invalidated \t");
 616   dump_bitmap (file, problem_data->sparse_invalidated_by_call);
 617   fprintf (file, "  dense invalidated \t");
 618   dump_bitmap (file, problem_data->dense_invalidated_by_call);
 619
 620   for (regno = 0; regno < m; regno++)
 621     if (DF_DEFS_COUNT (regno))
 622       fprintf (file, "%d[%d,%d] ", regno,
 623                DF_DEFS_BEGIN (regno),
 624                DF_DEFS_COUNT (regno));
 625   fprintf (file, "\n");
 626
 627 }
 628
 629
 630 /* Debugging info at top of bb.  */
 631
 632 static void
 633 df_rd_top_dump (basic_block bb, FILE *file)
 634 {
 635   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
 636   if (!bb_info || !bb_info->in)
 637     return;
 638
 639   fprintf (file, ";; rd  in  \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
 640   dump_bitmap (file, bb_info->in);
 641   fprintf (file, ";; rd  gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
 642   dump_bitmap (file, bb_info->gen);
 643   fprintf (file, ";; rd  kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
 644   dump_bitmap (file, bb_info->kill);
 645 }
 646
 647
 648 /* Debugging info at top of bb.  */
 649
 650 static void
 651 df_rd_bottom_dump (basic_block bb, FILE *file)
 652 {
 653   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
 654   if (!bb_info || !bb_info->out)
 655     return;
 656
 657   fprintf (file, ";; rd  out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
 658   dump_bitmap (file, bb_info->out);
 659 }
 660
 661 /* All of the information associated with every instance of the problem.  */
 662
 663 static struct df_problem problem_RD =
 664 {
 665   DF_RD,                      /* Problem id.  */
 666   DF_FORWARD,                 /* Direction.  */
 667   df_rd_alloc,                /* Allocate the problem specific data.  */
 668   NULL,                       /* Reset global information.  */
 669   df_rd_free_bb_info,         /* Free basic block info.  */
 670   df_rd_local_compute,        /* Local compute function.  */
 671   df_rd_init_solution,        /* Init the solution specific data.  */
 672   df_worklist_dataflow,       /* Worklist solver.  */
 673   NULL,                       /* Confluence operator 0.  */
 674   df_rd_confluence_n,         /* Confluence operator n.  */
 675   df_rd_transfer_function,    /* Transfer function.  */
 676   NULL,                       /* Finalize function.  */
 677   df_rd_free,                 /* Free all of the problem information.  */
 678   df_rd_free,                 /* Remove this problem from the stack of dataflow problems.  */
 679   df_rd_start_dump,           /* Debugging.  */
 680   df_rd_top_dump,             /* Debugging start block.  */
 681   df_rd_bottom_dump,          /* Debugging end block.  */
 682   NULL,                       /* Incremental solution verify start.  */
 683   NULL,                       /* Incremental solution verify end.  */
 684   NULL,                       /* Dependent problem.  */
 685   TV_DF_RD,                   /* Timing variable.  */
 686   true                        /* Reset blocks on dropping out of blocks_to_analyze.  */
 687 };
 688
 689
 690
 691 /* Create a new DATAFLOW instance and add it to an existing instance
 692    of DF.  The returned structure is what is used to get at the
 693    solution.  */
 694
 695 void
 696 df_rd_add_problem (void)
 697 {
 698   df_add_problem (&problem_RD);
 699 }
 700
 701
 702 \f
 703 /*----------------------------------------------------------------------------
 704    LIVE REGISTERS
 705
 706    Find the locations in the function where any use of a pseudo can
 707    reach in the backwards direction.  In and out bitvectors are built
 708    for each basic block.  The regnum is used to index into these sets.
 709    See df.h for details.
 710    ----------------------------------------------------------------------------*/
 711
 712 /* Private data used to verify the solution for this problem.  */
 713 struct df_lr_problem_data
 714 {
 715   bitmap *in;
 716   bitmap *out;
 717 };
 718
 719
 720 /* Set basic block info.  */
 721
 722 static void
 723 df_lr_set_bb_info (unsigned int index,
 724                    struct df_lr_bb_info *bb_info)
 725 {
 726   gcc_assert (df_lr);
 727   gcc_assert (index < df_lr->block_info_size);
 728   df_lr->block_info[index] = bb_info;
 729 }
 730
 731
 732 /* Free basic block info.  */
 733
 734 static void
 735 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
 736                     void *vbb_info)
 737 {
 738   struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
 739   if (bb_info)
 740     {
 741       BITMAP_FREE (bb_info->use);
 742       BITMAP_FREE (bb_info->def);
 743       if (bb_info->in == bb_info->top)
 744         bb_info->top = NULL;
 745       else
 746         {
 747           BITMAP_FREE (bb_info->top);
 748           BITMAP_FREE (bb_info->ause);
 749           BITMAP_FREE (bb_info->adef);
 750         }
 751       BITMAP_FREE (bb_info->in);
 752       BITMAP_FREE (bb_info->out);
 753       pool_free (df_lr->block_pool, bb_info);
 754     }
 755 }
 756
 757
 758 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
 759    not touched unless the block is new.  */
 760
 761 static void
 762 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
 763 {
 764   unsigned int bb_index;
 765   bitmap_iterator bi;
 766
 767   if (!df_lr->block_pool)
 768     df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
 769                                            sizeof (struct df_lr_bb_info), 50);
 770
 771   df_grow_bb_info (df_lr);
 772
 773   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
 774     {
 775       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 776       if (bb_info)
 777         {
 778           bitmap_clear (bb_info->def);
 779           bitmap_clear (bb_info->use);
 780           if (bb_info->adef)
 781             {
 782               bitmap_clear (bb_info->adef);
 783               bitmap_clear (bb_info->ause);
 784             }
 785         }
 786       else
 787         {
 788           bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
 789           df_lr_set_bb_info (bb_index, bb_info);
 790           bb_info->use = BITMAP_ALLOC (NULL);
 791           bb_info->def = BITMAP_ALLOC (NULL);
 792           bb_info->in = BITMAP_ALLOC (NULL);
 793           bb_info->out = BITMAP_ALLOC (NULL);
 794           bb_info->top = bb_info->in;
 795           bb_info->adef = NULL;
 796           bb_info->ause = NULL;
 797         }
 798     }
 799
 800   df_lr->optional_p = false;
 801 }
 802
 803
 804 /* Reset the global solution for recalculation.  */
 805
 806 static void
 807 df_lr_reset (bitmap all_blocks)
 808 {
 809   unsigned int bb_index;
 810   bitmap_iterator bi;
 811
 812   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 813     {
 814       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 815       gcc_assert (bb_info);
 816       bitmap_clear (bb_info->in);
 817       bitmap_clear (bb_info->out);
 818       bitmap_clear (bb_info->top);
 819     }
 820 }
 821
 822
 823 /* Compute local live register info for basic block BB.  */
 824
 825 static void
 826 df_lr_bb_local_compute (unsigned int bb_index)
 827 {
 828   basic_block bb = BASIC_BLOCK (bb_index);
 829   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 830   rtx insn;
 831   struct df_ref **def_rec;
 832   struct df_ref **use_rec;
 833
 834   /* Process the registers set in an exception handler.  */
 835   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 836     {
 837       struct df_ref *def = *def_rec;
 838       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 839         {
 840           unsigned int dregno = DF_REF_REGNO (def);
 841           bitmap_set_bit (bb_info->def, dregno);
 842           bitmap_clear_bit (bb_info->use, dregno);
 843         }
 844     }
 845
 846   /* Process the hardware registers that are always live.  */
 847   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 848     {
 849       struct df_ref *use = *use_rec;
 850       /* Add use to set of uses in this BB.  */
 851       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 852         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
 853     }
 854
 855   FOR_BB_INSNS_REVERSE (bb, insn)
 856     {
 857       unsigned int uid = INSN_UID (insn);
 858
 859       if (!INSN_P (insn))
 860         continue;
 861
 862       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 863         {
 864           struct df_ref *def = *def_rec;
 865           /* If the def is to only part of the reg, it does
 866              not kill the other defs that reach here.  */
 867           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 868             {
 869               unsigned int dregno = DF_REF_REGNO (def);
 870               bitmap_set_bit (bb_info->def, dregno);
 871               bitmap_clear_bit (bb_info->use, dregno);
 872             }
 873         }
 874
 875       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 876         {
 877           struct df_ref *use = *use_rec;
 878           /* Add use to set of uses in this BB.  */
 879           bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
 880         }
 881     }
 882   /* Process the registers set in an exception handler.  */
 883   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 884     {
 885       struct df_ref *def = *def_rec;
 886       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP)
 887           && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
 888         {
 889           unsigned int dregno = DF_REF_REGNO (def);
 890           if (bb_info->adef == NULL)
 891             {
 892               gcc_assert (bb_info->ause == NULL);
 893               gcc_assert (bb_info->top == bb_info->in);
 894               bb_info->adef = BITMAP_ALLOC (NULL);
 895               bb_info->ause = BITMAP_ALLOC (NULL);
 896               bb_info->top = BITMAP_ALLOC (NULL);
 897             }
 898           bitmap_set_bit (bb_info->adef, dregno);
 899         }
 900     }
 901
 902 #ifdef EH_USES
 903   /* Process the uses that are live into an exception handler.  */
 904   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 905     {
 906       struct df_ref *use = *use_rec;
 907       /* Add use to set of uses in this BB.  */
 908       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
 909         {
 910           if (bb_info->adef == NULL)
 911             {
 912               gcc_assert (bb_info->ause == NULL);
 913               gcc_assert (bb_info->top == bb_info->in);
 914               bb_info->adef = BITMAP_ALLOC (NULL);
 915               bb_info->ause = BITMAP_ALLOC (NULL);
 916               bb_info->top = BITMAP_ALLOC (NULL);
 917             }
 918           bitmap_set_bit (bb_info->ause, DF_REF_REGNO (use));
 919         }
 920     }
 921 #endif
 922
 923   /* If the df_live problem is not defined, such as at -O0 and -O1, we
 924      still need to keep the luids up to date.  This is normally done
 925      in the df_live problem since this problem has a forwards
 926      scan.  */
 927   if (!df_live)
 928     df_recompute_luids (bb);
 929 }
 930
 931
 932 /* Compute local live register info for each basic block within BLOCKS.  */
 933
 934 static void
 935 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
 936 {
 937   unsigned int bb_index;
 938   bitmap_iterator bi;
 939
 940   bitmap_clear (df->hardware_regs_used);
 941
 942   /* The all-important stack pointer must always be live.  */
 943   bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
 944
 945   /* Before reload, there are a few registers that must be forced
 946      live everywhere -- which might not already be the case for
 947      blocks within infinite loops.  */
 948   if (!reload_completed)
 949     {
 950       /* Any reference to any pseudo before reload is a potential
 951          reference of the frame pointer.  */
 952       bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
 953
 954 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
 955       /* Pseudos with argument area equivalences may require
 956          reloading via the argument pointer.  */
 957       if (fixed_regs[ARG_POINTER_REGNUM])
 958         bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
 959 #endif
 960
 961       /* Any constant, or pseudo with constant equivalences, may
 962          require reloading from memory using the pic register.  */
 963       if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
 964           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
 965         bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
 966     }
 967
 968   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
 969     {
 970       if (bb_index == EXIT_BLOCK)
 971         {
 972           /* The exit block is special for this problem and its bits are
 973              computed from thin air.  */
 974           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
 975           bitmap_copy (bb_info->use, df->exit_block_uses);
 976         }
 977       else
 978         df_lr_bb_local_compute (bb_index);
 979     }
 980
 981   bitmap_clear (df_lr->out_of_date_transfer_functions);
 982 }
 983
 984
 985 /* Initialize the solution vectors.  */
 986
 987 static void
 988 df_lr_init (bitmap all_blocks)
 989 {
 990   unsigned int bb_index;
 991   bitmap_iterator bi;
 992
 993   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 994     {
 995       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 996       bitmap_copy (bb_info->in, bb_info->use);
 997       bitmap_clear (bb_info->out);
 998     }
 999 }
1000
1001
1002 /* Confluence function that processes infinite loops.  This might be a
1003    noreturn function that throws.  And even if it isn't, getting the
1004    unwind info right helps debugging.  */
1005 static void
1006 df_lr_confluence_0 (basic_block bb)
1007 {
1008   bitmap op1 = df_lr_get_bb_info (bb->index)->out;
1009   if (bb != EXIT_BLOCK_PTR)
1010     bitmap_copy (op1, df->hardware_regs_used);
1011 }
1012
1013
1014 /* Confluence function that ignores fake edges.  */
1015
1016 static void
1017 df_lr_confluence_n (edge e)
1018 {
1019   bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
1020   bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
1021
1022   /* Call-clobbered registers die across exception and call edges.  */
1023   /* ??? Abnormal call edges ignored for the moment, as this gets
1024      confused by sibling call edges, which crashes reg-stack.  */
1025   if (e->flags & EDGE_EH)
1026     bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
1027   else
1028     bitmap_ior_into (op1, op2);
1029
1030   bitmap_ior_into (op1, df->hardware_regs_used);
1031 }
1032
1033
1034 /* Transfer function.  */
1035
1036 static bool
1037 df_lr_transfer_function (int bb_index)
1038 {
1039   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1040   bitmap in = bb_info->in;
1041   bitmap out = bb_info->out;
1042   bitmap use = bb_info->use;
1043   bitmap def = bb_info->def;
1044   bitmap top = bb_info->top;
1045   bitmap ause = bb_info->ause;
1046   bitmap adef = bb_info->adef;
1047   bool changed;
1048
1049   changed = bitmap_ior_and_compl (top, use, out, def);
1050   if (in != top)
1051     {
1052       gcc_assert (ause && adef);
1053       changed |= bitmap_ior_and_compl (in, ause, top, adef);
1054     }
1055
1056   return changed;
1057 }
1058
1059
1060 /* Run the fast dce as a side effect of building LR.  */
1061
1062 static void
1063 df_lr_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
1064 {
1065   if (df->changeable_flags & DF_LR_RUN_DCE)
1066     {
1067       run_fast_df_dce ();
1068       if (df_lr->problem_data && df_lr->solutions_dirty)
1069         {
1070           /* If we are here, then it is because we are both verifying
1071           the solution and the dce changed the function.  In that case
1072           the verification info built will be wrong.  So we leave the
1073           dirty flag true so that the verifier will skip the checking
1074           part and just clean up.*/
1075           df_lr->solutions_dirty = true;
1076         }
1077       else
1078         df_lr->solutions_dirty = false;
1079     }
1080   else
1081     df_lr->solutions_dirty = false;
1082 }
1083
1084
1085 /* Free all storage associated with the problem.  */
1086
1087 static void
1088 df_lr_free (void)
1089 {
1090   if (df_lr->block_info)
1091     {
1092       unsigned int i;
1093       for (i = 0; i < df_lr->block_info_size; i++)
1094         {
1095           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
1096           if (bb_info)
1097             {
1098               BITMAP_FREE (bb_info->use);
1099               BITMAP_FREE (bb_info->def);
1100               if (bb_info->in == bb_info->top)
1101                 bb_info->top = NULL;
1102               else
1103                 {
1104                   BITMAP_FREE (bb_info->top);
1105                   BITMAP_FREE (bb_info->ause);
1106                   BITMAP_FREE (bb_info->adef);
1107                 }
1108               BITMAP_FREE (bb_info->in);
1109               BITMAP_FREE (bb_info->out);
1110             }
1111         }
1112       free_alloc_pool (df_lr->block_pool);
1113
1114       df_lr->block_info_size = 0;
1115       free (df_lr->block_info);
1116     }
1117
1118   BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1119   free (df_lr);
1120 }
1121
1122
1123 /* Debugging info at top of bb.  */
1124
1125 static void
1126 df_lr_top_dump (basic_block bb, FILE *file)
1127 {
1128   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1129   struct df_lr_problem_data *problem_data;
1130   if (!bb_info || !bb_info->in)
1131     return;
1132
1133   fprintf (file, ";; lr  in  \t");
1134   df_print_regset (file, bb_info->in);
1135   if (df_lr->problem_data)
1136     {
1137       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1138       fprintf (file, ";;  old in  \t");
1139       df_print_regset (file, problem_data->in[bb->index]);
1140     }
1141   fprintf (file, ";; lr  use \t");
1142   df_print_regset (file, bb_info->use);
1143   fprintf (file, ";; lr  def \t");
1144   df_print_regset (file, bb_info->def);
1145 }
1146
1147
1148 /* Debugging info at bottom of bb.  */
1149
1150 static void
1151 df_lr_bottom_dump (basic_block bb, FILE *file)
1152 {
1153   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1154   struct df_lr_problem_data *problem_data;
1155   if (!bb_info || !bb_info->out)
1156     return;
1157
1158   fprintf (file, ";; lr  out \t");
1159   df_print_regset (file, bb_info->out);
1160   if (df_lr->problem_data)
1161     {
1162       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1163       fprintf (file, ";;  old out  \t");
1164       df_print_regset (file, problem_data->out[bb->index]);
1165     }
1166 }
1167
1168
1169 /* Build the datastructure to verify that the solution to the dataflow
1170    equations is not dirty.  */
1171
1172 static void
1173 df_lr_verify_solution_start (void)
1174 {
1175   basic_block bb;
1176   struct df_lr_problem_data *problem_data;
1177   if (df_lr->solutions_dirty)
1178     {
1179       df_lr->problem_data = NULL;
1180       return;
1181     }
1182
1183   /* Set it true so that the solution is recomputed.  */
1184   df_lr->solutions_dirty = true;
1185
1186   problem_data = XNEW (struct df_lr_problem_data);
1187   df_lr->problem_data = problem_data;
1188   problem_data->in = XNEWVEC (bitmap, last_basic_block);
1189   problem_data->out = XNEWVEC (bitmap, last_basic_block);
1190
1191   FOR_ALL_BB (bb)
1192     {
1193       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1194       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1195       bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1196       bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1197     }
1198 }
1199
1200
1201 /* Compare the saved datastructure and the new solution to the dataflow
1202    equations.  */
1203
1204 static void
1205 df_lr_verify_solution_end (void)
1206 {
1207   struct df_lr_problem_data *problem_data;
1208   basic_block bb;
1209
1210   if (df_lr->problem_data == NULL)
1211     return;
1212
1213   problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1214
1215   if (df_lr->solutions_dirty)
1216     /* Do not check if the solution is still dirty.  See the comment
1217        in df_lr_local_finalize for details.  */
1218     df_lr->solutions_dirty = false;
1219   else
1220     FOR_ALL_BB (bb)
1221       {
1222         if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1223             || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1224           {
1225             /*df_dump (stderr);*/
1226             gcc_unreachable ();
1227           }
1228       }
1229
1230   /* Cannot delete them immediately because you may want to dump them
1231      if the comparison fails.  */
1232   FOR_ALL_BB (bb)
1233     {
1234       BITMAP_FREE (problem_data->in[bb->index]);
1235       BITMAP_FREE (problem_data->out[bb->index]);
1236     }
1237
1238   free (problem_data->in);
1239   free (problem_data->out);
1240   free (problem_data);
1241   df_lr->problem_data = NULL;
1242 }
1243
1244
1245 /* All of the information associated with every instance of the problem.  */
1246
1247 static struct df_problem problem_LR =
1248 {
1249   DF_LR,                      /* Problem id.  */
1250   DF_BACKWARD,                /* Direction.  */
1251   df_lr_alloc,                /* Allocate the problem specific data.  */
1252   df_lr_reset,                /* Reset global information.  */
1253   df_lr_free_bb_info,         /* Free basic block info.  */
1254   df_lr_local_compute,        /* Local compute function.  */
1255   df_lr_init,                 /* Init the solution specific data.  */
1256   df_worklist_dataflow,       /* Worklist solver.  */
1257   df_lr_confluence_0,         /* Confluence operator 0.  */
1258   df_lr_confluence_n,         /* Confluence operator n.  */
1259   df_lr_transfer_function,    /* Transfer function.  */
1260   df_lr_local_finalize,       /* Finalize function.  */
1261   df_lr_free,                 /* Free all of the problem information.  */
1262   NULL,                       /* Remove this problem from the stack of dataflow problems.  */
1263   NULL,                       /* Debugging.  */
1264   df_lr_top_dump,             /* Debugging start block.  */
1265   df_lr_bottom_dump,          /* Debugging end block.  */
1266   df_lr_verify_solution_start,/* Incremental solution verify start.  */
1267   df_lr_verify_solution_end,  /* Incremental solution verify end.  */
1268   NULL,                       /* Dependent problem.  */
1269   TV_DF_LR,                   /* Timing variable.  */
1270   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
1271 };
1272
1273
1274 /* Create a new DATAFLOW instance and add it to an existing instance
1275    of DF.  The returned structure is what is used to get at the
1276    solution.  */
1277
1278 void
1279 df_lr_add_problem (void)
1280 {
1281   df_add_problem (&problem_LR);
1282   /* These will be initialized when df_scan_blocks processes each
1283      block.  */
1284   df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1285 }
1286
1287
1288 /* Verify that all of the lr related info is consistent and
1289    correct.  */
1290
1291 void
1292 df_lr_verify_transfer_functions (void)
1293 {
1294   basic_block bb;
1295   bitmap saved_def;
1296   bitmap saved_use;
1297   bitmap saved_adef;
1298   bitmap saved_ause;
1299   bitmap all_blocks;
1300   bool need_as;
1301
1302   if (!df)
1303     return;
1304
1305   saved_def = BITMAP_ALLOC (NULL);
1306   saved_use = BITMAP_ALLOC (NULL);
1307   saved_adef = BITMAP_ALLOC (NULL);
1308   saved_ause = BITMAP_ALLOC (NULL);
1309   all_blocks = BITMAP_ALLOC (NULL);
1310
1311   FOR_ALL_BB (bb)
1312     {
1313       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1314       bitmap_set_bit (all_blocks, bb->index);
1315
1316       if (bb_info)
1317         {
1318           /* Make a copy of the transfer functions and then compute
1319              new ones to see if the transfer functions have
1320              changed.  */
1321           if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1322                              bb->index))
1323             {
1324               bitmap_copy (saved_def, bb_info->def);
1325               bitmap_copy (saved_use, bb_info->use);
1326               bitmap_clear (bb_info->def);
1327               bitmap_clear (bb_info->use);
1328
1329               if (bb_info->adef)
1330                 {
1331                   need_as = true;
1332                   bitmap_copy (saved_adef, bb_info->adef);
1333                   bitmap_copy (saved_ause, bb_info->ause);
1334                   bitmap_clear (bb_info->adef);
1335                   bitmap_clear (bb_info->ause);
1336                 }
1337               else
1338                 need_as = false;
1339
1340               df_lr_bb_local_compute (bb->index);
1341               gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1342               gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
1343
1344               if (need_as)
1345                 {
1346                   gcc_assert (bb_info->adef);
1347                   gcc_assert (bb_info->ause);
1348                   gcc_assert (bitmap_equal_p (saved_adef, bb_info->adef));
1349                   gcc_assert (bitmap_equal_p (saved_ause, bb_info->ause));
1350                 }
1351               else
1352                 {
1353                   gcc_assert (!bb_info->adef);
1354                   gcc_assert (!bb_info->ause);
1355                 }
1356             }
1357         }
1358       else
1359         {
1360           /* If we do not have basic block info, the block must be in
1361              the list of dirty blocks or else some one has added a
1362              block behind our backs. */
1363           gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1364                                     bb->index));
1365         }
1366       /* Make sure no one created a block without following
1367          procedures.  */
1368       gcc_assert (df_scan_get_bb_info (bb->index));
1369     }
1370
1371   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1372   gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1373                                          all_blocks));
1374
1375   BITMAP_FREE (saved_def);
1376   BITMAP_FREE (saved_use);
1377   BITMAP_FREE (saved_adef);
1378   BITMAP_FREE (saved_ause);
1379   BITMAP_FREE (all_blocks);
1380 }
1381
1382
1383 \f
1384 /*----------------------------------------------------------------------------
1385    COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
1386
1387    First find the set of uses for registers that are reachable from
1388    the entry block without passing thru a definition.  In and out
1389    bitvectors are built for each basic block.  The regnum is used to
1390    index into these sets.  See df.h for details.
1391
1392    Then the in and out sets here are the anded results of the in and
1393    out sets from the lr and ur
1394    problems.
1395 ----------------------------------------------------------------------------*/
1396
1397 /* Private data used to verify the solution for this problem.  */
1398 struct df_live_problem_data
1399 {
1400   bitmap *in;
1401   bitmap *out;
1402 };
1403
1404
1405 /* Set basic block info.  */
1406
1407 static void
1408 df_live_set_bb_info (unsigned int index,
1409                    struct df_live_bb_info *bb_info)
1410 {
1411   gcc_assert (df_live);
1412   gcc_assert (index < df_live->block_info_size);
1413   df_live->block_info[index] = bb_info;
1414 }
1415
1416
1417 /* Free basic block info.  */
1418
1419 static void
1420 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1421                     void *vbb_info)
1422 {
1423   struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1424   if (bb_info)
1425     {
1426       BITMAP_FREE (bb_info->gen);
1427       BITMAP_FREE (bb_info->kill);
1428       BITMAP_FREE (bb_info->in);
1429       BITMAP_FREE (bb_info->out);
1430       pool_free (df_live->block_pool, bb_info);
1431     }
1432 }
1433
1434
1435 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1436    not touched unless the block is new.  */
1437
1438 static void
1439 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1440 {
1441   unsigned int bb_index;
1442   bitmap_iterator bi;
1443
1444   if (!df_live->block_pool)
1445     df_live->block_pool = create_alloc_pool ("df_live_block pool",
1446                                            sizeof (struct df_live_bb_info), 100);
1447
1448   df_grow_bb_info (df_live);
1449
1450   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1451     {
1452       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1453       if (bb_info)
1454         {
1455           bitmap_clear (bb_info->kill);
1456           bitmap_clear (bb_info->gen);
1457         }
1458       else
1459         {
1460           bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1461           df_live_set_bb_info (bb_index, bb_info);
1462           bb_info->kill = BITMAP_ALLOC (NULL);
1463           bb_info->gen = BITMAP_ALLOC (NULL);
1464           bb_info->in = BITMAP_ALLOC (NULL);
1465           bb_info->out = BITMAP_ALLOC (NULL);
1466         }
1467     }
1468   df_live->optional_p = (optimize <= 1);
1469 }
1470
1471
1472 /* Reset the global solution for recalculation.  */
1473
1474 static void
1475 df_live_reset (bitmap all_blocks)
1476 {
1477   unsigned int bb_index;
1478   bitmap_iterator bi;
1479
1480   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1481     {
1482       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1483       gcc_assert (bb_info);
1484       bitmap_clear (bb_info->in);
1485       bitmap_clear (bb_info->out);
1486     }
1487 }
1488
1489
1490 /* Compute local uninitialized register info for basic block BB.  */
1491
1492 static void
1493 df_live_bb_local_compute (unsigned int bb_index)
1494 {
1495   basic_block bb = BASIC_BLOCK (bb_index);
1496   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1497   rtx insn;
1498   struct df_ref **def_rec;
1499   int luid = 0;
1500
1501   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1502     {
1503       struct df_ref *def = *def_rec;
1504       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1505         bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
1506     }
1507
1508   FOR_BB_INSNS (bb, insn)
1509     {
1510       unsigned int uid = INSN_UID (insn);
1511       struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1512
1513       /* Inserting labels does not always trigger the incremental
1514          rescanning.  */
1515       if (!insn_info)
1516         {
1517           gcc_assert (!INSN_P (insn));
1518           df_insn_create_insn_record (insn);
1519         }
1520
1521       DF_INSN_LUID (insn) = luid;
1522       if (!INSN_P (insn))
1523         continue;
1524
1525       luid++;
1526       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1527         {
1528           struct df_ref *def = *def_rec;
1529           unsigned int regno = DF_REF_REGNO (def);
1530
1531           if (DF_REF_FLAGS_IS_SET (def,
1532                                    DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1533             /* All partial or conditional def
1534                seen are included in the gen set. */
1535             bitmap_set_bit (bb_info->gen, regno);
1536           else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1537             /* Only must clobbers for the entire reg destroy the
1538                value.  */
1539             bitmap_set_bit (bb_info->kill, regno);
1540           else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1541             bitmap_set_bit (bb_info->gen, regno);
1542         }
1543     }
1544
1545   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1546     {
1547       struct df_ref *def = *def_rec;
1548       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
1549         bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
1550     }
1551 }
1552
1553
1554 /* Compute local uninitialized register info.  */
1555
1556 static void
1557 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1558 {
1559   unsigned int bb_index;
1560   bitmap_iterator bi;
1561
1562   df_grow_insn_info ();
1563
1564   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1565                             0, bb_index, bi)
1566     {
1567       df_live_bb_local_compute (bb_index);
1568     }
1569
1570   bitmap_clear (df_live->out_of_date_transfer_functions);
1571 }
1572
1573
1574 /* Initialize the solution vectors.  */
1575
1576 static void
1577 df_live_init (bitmap all_blocks)
1578 {
1579   unsigned int bb_index;
1580   bitmap_iterator bi;
1581
1582   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1583     {
1584       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1585
1586       bitmap_copy (bb_info->out, bb_info->gen);
1587       bitmap_clear (bb_info->in);
1588     }
1589 }
1590
1591 /* Confluence function that ignores fake edges.  */
1592
1593 static void
1594 df_live_confluence_n (edge e)
1595 {
1596   bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
1597   bitmap op2 = df_live_get_bb_info (e->src->index)->out;
1598
1599   if (e->flags & EDGE_FAKE)
1600     return;
1601
1602   bitmap_ior_into (op1, op2);
1603 }
1604
1605
1606 /* Transfer function.  */
1607
1608 static bool
1609 df_live_transfer_function (int bb_index)
1610 {
1611   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1612   bitmap in = bb_info->in;
1613   bitmap out = bb_info->out;
1614   bitmap gen = bb_info->gen;
1615   bitmap kill = bb_info->kill;
1616
1617   return bitmap_ior_and_compl (out, gen, in, kill);
1618 }
1619
1620
1621 /* And the LR and UR info to produce the LIVE info.  */
1622
1623 static void
1624 df_live_local_finalize (bitmap all_blocks)
1625 {
1626
1627   if (df_live->solutions_dirty)
1628     {
1629       bitmap_iterator bi;
1630       unsigned int bb_index;
1631
1632       EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1633         {
1634           struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1635           struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1636
1637           /* No register may reach a location where it is not used.  Thus
1638              we trim the rr result to the places where it is used.  */
1639           bitmap_and_into (bb_live_info->in, bb_lr_info->in);
1640           bitmap_and_into (bb_live_info->out, bb_lr_info->out);
1641         }
1642
1643       df_live->solutions_dirty = false;
1644     }
1645 }
1646
1647
1648 /* Free all storage associated with the problem.  */
1649
1650 static void
1651 df_live_free (void)
1652 {
1653   if (df_live->block_info)
1654     {
1655       unsigned int i;
1656
1657       for (i = 0; i < df_live->block_info_size; i++)
1658         {
1659           struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
1660           if (bb_info)
1661             {
1662               BITMAP_FREE (bb_info->gen);
1663               BITMAP_FREE (bb_info->kill);
1664               BITMAP_FREE (bb_info->in);
1665               BITMAP_FREE (bb_info->out);
1666             }
1667         }
1668
1669       free_alloc_pool (df_live->block_pool);
1670       df_live->block_info_size = 0;
1671       free (df_live->block_info);
1672     }
1673   BITMAP_FREE (df_live->out_of_date_transfer_functions);
1674   free (df_live);
1675 }
1676
1677
1678 /* Debugging info at top of bb.  */
1679
1680 static void
1681 df_live_top_dump (basic_block bb, FILE *file)
1682 {
1683   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1684   struct df_live_problem_data *problem_data;
1685
1686   if (!bb_info || !bb_info->in)
1687     return;
1688
1689   fprintf (file, ";; live  in  \t");
1690   df_print_regset (file, bb_info->in);
1691   if (df_live->problem_data)
1692     {
1693       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1694       fprintf (file, ";;  old in  \t");
1695       df_print_regset (file, problem_data->in[bb->index]);
1696     }
1697   fprintf (file, ";; live  gen \t");
1698   df_print_regset (file, bb_info->gen);
1699   fprintf (file, ";; live  kill\t");
1700   df_print_regset (file, bb_info->kill);
1701 }
1702
1703
1704 /* Debugging info at bottom of bb.  */
1705
1706 static void
1707 df_live_bottom_dump (basic_block bb, FILE *file)
1708 {
1709   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1710   struct df_live_problem_data *problem_data;
1711
1712   if (!bb_info || !bb_info->out)
1713     return;
1714
1715   fprintf (file, ";; live  out \t");
1716   df_print_regset (file, bb_info->out);
1717   if (df_live->problem_data)
1718     {
1719       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1720       fprintf (file, ";;  old out  \t");
1721       df_print_regset (file, problem_data->out[bb->index]);
1722     }
1723 }
1724
1725
1726 /* Build the datastructure to verify that the solution to the dataflow
1727    equations is not dirty.  */
1728
1729 static void
1730 df_live_verify_solution_start (void)
1731 {
1732   basic_block bb;
1733   struct df_live_problem_data *problem_data;
1734   if (df_live->solutions_dirty)
1735     {
1736       df_live->problem_data = NULL;
1737       return;
1738     }
1739
1740   /* Set it true so that the solution is recomputed.  */
1741   df_live->solutions_dirty = true;
1742
1743   problem_data = XNEW (struct df_live_problem_data);
1744   df_live->problem_data = problem_data;
1745   problem_data->in = XNEWVEC (bitmap, last_basic_block);
1746   problem_data->out = XNEWVEC (bitmap, last_basic_block);
1747
1748   FOR_ALL_BB (bb)
1749     {
1750       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1751       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1752       bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
1753       bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
1754     }
1755 }
1756
1757
1758 /* Compare the saved datastructure and the new solution to the dataflow
1759    equations.  */
1760
1761 static void
1762 df_live_verify_solution_end (void)
1763 {
1764   struct df_live_problem_data *problem_data;
1765   basic_block bb;
1766
1767   if (df_live->problem_data == NULL)
1768     return;
1769
1770   problem_data = (struct df_live_problem_data *)df_live->problem_data;
1771
1772   FOR_ALL_BB (bb)
1773     {
1774       if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
1775           || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1776         {
1777           /*df_dump (stderr);*/
1778           gcc_unreachable ();
1779         }
1780     }
1781
1782   /* Cannot delete them immediately because you may want to dump them
1783      if the comparison fails.  */
1784   FOR_ALL_BB (bb)
1785     {
1786       BITMAP_FREE (problem_data->in[bb->index]);
1787       BITMAP_FREE (problem_data->out[bb->index]);
1788     }
1789
1790   free (problem_data->in);
1791   free (problem_data->out);
1792   free (problem_data);
1793   df_live->problem_data = NULL;
1794 }
1795
1796
1797 /* All of the information associated with every instance of the problem.  */
1798
1799 static struct df_problem problem_LIVE =
1800 {
1801   DF_LIVE,                      /* Problem id.  */
1802   DF_FORWARD,                   /* Direction.  */
1803   df_live_alloc,                /* Allocate the problem specific data.  */
1804   df_live_reset,                /* Reset global information.  */
1805   df_live_free_bb_info,         /* Free basic block info.  */
1806   df_live_local_compute,        /* Local compute function.  */
1807   df_live_init,                 /* Init the solution specific data.  */
1808   df_worklist_dataflow,         /* Worklist solver.  */
1809   NULL,                         /* Confluence operator 0.  */
1810   df_live_confluence_n,         /* Confluence operator n.  */
1811   df_live_transfer_function,    /* Transfer function.  */
1812   df_live_local_finalize,       /* Finalize function.  */
1813   df_live_free,                 /* Free all of the problem information.  */
1814   df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
1815   NULL,                         /* Debugging.  */
1816   df_live_top_dump,             /* Debugging start block.  */
1817   df_live_bottom_dump,          /* Debugging end block.  */
1818   df_live_verify_solution_start,/* Incremental solution verify start.  */
1819   df_live_verify_solution_end,  /* Incremental solution verify end.  */
1820   &problem_LR,                  /* Dependent problem.  */
1821   TV_DF_LIVE,                   /* Timing variable.  */
1822   false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
1823 };
1824
1825
1826 /* Create a new DATAFLOW instance and add it to an existing instance
1827    of DF.  The returned structure is what is used to get at the
1828    solution.  */
1829
1830 void
1831 df_live_add_problem (void)
1832 {
1833   df_add_problem (&problem_LIVE);
1834   /* These will be initialized when df_scan_blocks processes each
1835      block.  */
1836   df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1837 }
1838
1839
1840 /* Set all of the blocks as dirty.  This needs to be done if this
1841    problem is added after all of the insns have been scanned.  */
1842
1843 void
1844 df_live_set_all_dirty (void)
1845 {
1846   basic_block bb;
1847   FOR_ALL_BB (bb)
1848     bitmap_set_bit (df_live->out_of_date_transfer_functions,
1849                     bb->index);
1850 }
1851
1852
1853 /* Verify that all of the lr related info is consistent and
1854    correct.  */
1855
1856 void
1857 df_live_verify_transfer_functions (void)
1858 {
1859   basic_block bb;
1860   bitmap saved_gen;
1861   bitmap saved_kill;
1862   bitmap all_blocks;
1863
1864   if (!df)
1865     return;
1866
1867   saved_gen = BITMAP_ALLOC (NULL);
1868   saved_kill = BITMAP_ALLOC (NULL);
1869   all_blocks = BITMAP_ALLOC (NULL);
1870
1871   df_grow_insn_info ();
1872
1873   FOR_ALL_BB (bb)
1874     {
1875       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1876       bitmap_set_bit (all_blocks, bb->index);
1877
1878       if (bb_info)
1879         {
1880           /* Make a copy of the transfer functions and then compute
1881              new ones to see if the transfer functions have
1882              changed.  */
1883           if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1884                              bb->index))
1885             {
1886               bitmap_copy (saved_gen, bb_info->gen);
1887               bitmap_copy (saved_kill, bb_info->kill);
1888               bitmap_clear (bb_info->gen);
1889               bitmap_clear (bb_info->kill);
1890
1891               df_live_bb_local_compute (bb->index);
1892               gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
1893               gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
1894             }
1895         }
1896       else
1897         {
1898           /* If we do not have basic block info, the block must be in
1899              the list of dirty blocks or else some one has added a
1900              block behind our backs. */
1901           gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1902                                     bb->index));
1903         }
1904       /* Make sure no one created a block without following
1905          procedures.  */
1906       gcc_assert (df_scan_get_bb_info (bb->index));
1907     }
1908
1909   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1910   gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1911                                          all_blocks));
1912   BITMAP_FREE (saved_gen);
1913   BITMAP_FREE (saved_kill);
1914   BITMAP_FREE (all_blocks);
1915 }
1916
1917
1918 \f
1919 /*----------------------------------------------------------------------------
1920    UNINITIALIZED REGISTERS WITH EARLYCLOBBER
1921
1922    Find the set of uses for registers that are reachable from the entry
1923    block without passing thru a definition.  In and out bitvectors are built
1924    for each basic block.  The regnum is used to index into these sets.
1925    See df.h for details.
1926
1927    This is a variant of the UR problem above that has a lot of special
1928    features just for the register allocation phase.  This problem
1929    should go away if someone would fix the interference graph.
1930
1931    ----------------------------------------------------------------------------*/
1932
1933 /* Private data used to compute the solution for this problem.  These
1934    data structures are not accessible outside of this module.  */
1935 struct df_urec_problem_data
1936 {
1937   bool earlyclobbers_found;     /* True if any instruction contains an
1938                                    earlyclobber.  */
1939 #ifdef STACK_REGS
1940   bitmap stack_regs;            /* Registers that may be allocated to a STACK_REGS.  */
1941 #endif
1942 };
1943
1944
1945 /* Set basic block info.  */
1946
1947 static void
1948 df_urec_set_bb_info (unsigned int index,
1949                      struct df_urec_bb_info *bb_info)
1950 {
1951   gcc_assert (df_urec);
1952   gcc_assert (index < df_urec->block_info_size);
1953   df_urec->block_info[index] = bb_info;
1954 }
1955
1956
1957 /* Free basic block info.  */
1958
1959 static void
1960 df_urec_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1961                       void *vbb_info)
1962 {
1963   struct df_urec_bb_info *bb_info = (struct df_urec_bb_info *) vbb_info;
1964   if (bb_info)
1965     {
1966       BITMAP_FREE (bb_info->gen);
1967       BITMAP_FREE (bb_info->kill);
1968       BITMAP_FREE (bb_info->in);
1969       BITMAP_FREE (bb_info->out);
1970       BITMAP_FREE (bb_info->earlyclobber);
1971       pool_free (df_urec->block_pool, bb_info);
1972     }
1973 }
1974
1975
1976 /* Allocate or reset bitmaps for DF_UREC blocks. The solution bits are
1977    not touched unless the block is new.  */
1978
1979 static void
1980 df_urec_alloc (bitmap all_blocks)
1981
1982 {
1983   unsigned int bb_index;
1984   bitmap_iterator bi;
1985   struct df_urec_problem_data *problem_data
1986     = (struct df_urec_problem_data *) df_urec->problem_data;
1987
1988   if (!df_urec->block_pool)
1989     df_urec->block_pool = create_alloc_pool ("df_urec_block pool",
1990                                            sizeof (struct df_urec_bb_info), 50);
1991
1992   if (!df_urec->problem_data)
1993     {
1994       problem_data = XNEW (struct df_urec_problem_data);
1995       df_urec->problem_data = problem_data;
1996     }
1997   problem_data->earlyclobbers_found = false;
1998
1999   df_grow_bb_info (df_urec);
2000
2001   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2002     {
2003       struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2004       if (bb_info)
2005         {
2006           bitmap_clear (bb_info->kill);
2007           bitmap_clear (bb_info->gen);
2008           bitmap_clear (bb_info->earlyclobber);
2009         }
2010       else
2011         {
2012           bb_info = (struct df_urec_bb_info *) pool_alloc (df_urec->block_pool);
2013           df_urec_set_bb_info (bb_index, bb_info);
2014           bb_info->kill = BITMAP_ALLOC (NULL);
2015           bb_info->gen = BITMAP_ALLOC (NULL);
2016           bb_info->in = BITMAP_ALLOC (NULL);
2017           bb_info->out = BITMAP_ALLOC (NULL);
2018           bb_info->top = BITMAP_ALLOC (NULL);
2019           bb_info->earlyclobber = BITMAP_ALLOC (NULL);
2020         }
2021     }
2022   df_urec->optional_p = true;
2023 }
2024
2025
2026 /* The function modifies local info for register REG being changed in
2027    SETTER.  DATA is used to pass the current basic block info.  */
2028
2029 static void
2030 df_urec_mark_reg_change (rtx reg, const_rtx setter, void *data)
2031 {
2032   int regno;
2033   int endregno;
2034   int i;
2035   struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
2036
2037   if (GET_CODE (reg) == SUBREG)
2038     reg = SUBREG_REG (reg);
2039
2040   if (!REG_P (reg))
2041     return;
2042
2043   regno = REGNO (reg);
2044   if (regno < FIRST_PSEUDO_REGISTER)
2045     {
2046       endregno = END_HARD_REGNO (reg);
2047       for (i = regno; i < endregno; i++)
2048         {
2049           bitmap_set_bit (bb_info->kill, i);
2050
2051           if (GET_CODE (setter) != CLOBBER)
2052             bitmap_set_bit (bb_info->gen, i);
2053           else
2054             bitmap_clear_bit (bb_info->gen, i);
2055         }
2056     }
2057   else
2058     {
2059       bitmap_set_bit (bb_info->kill, regno);
2060
2061       if (GET_CODE (setter) != CLOBBER)
2062         bitmap_set_bit (bb_info->gen, regno);
2063       else
2064         bitmap_clear_bit (bb_info->gen, regno);
2065     }
2066 }
2067 /* Classes of registers which could be early clobbered in the current
2068    insn.  */
2069
2070 static VEC(int,heap) *earlyclobber_regclass;
2071
2072 /* This function finds and stores register classes that could be early
2073    clobbered in INSN.  If any earlyclobber classes are found, the function
2074    returns TRUE, in all other cases it returns FALSE.  */
2075
2076 static bool
2077 df_urec_check_earlyclobber (rtx insn)
2078 {
2079   int opno;
2080   bool found = false;
2081
2082   extract_insn (insn);
2083
2084   VEC_truncate (int, earlyclobber_regclass, 0);
2085   for (opno = 0; opno < recog_data.n_operands; opno++)
2086     {
2087       char c;
2088       bool amp_p;
2089       int i;
2090       enum reg_class class;
2091       const char *p = recog_data.constraints[opno];
2092
2093       class = NO_REGS;
2094       amp_p = false;
2095       for (;;)
2096         {
2097           c = *p;
2098           switch (c)
2099             {
2100             case '=':  case '+':  case '?':
2101             case '#':  case '!':
2102             case '*':  case '%':
2103             case 'm':  case '<':  case '>':  case 'V':  case 'o':
2104             case 'E':  case 'F':  case 'G':  case 'H':
2105             case 's':  case 'i':  case 'n':
2106             case 'I':  case 'J':  case 'K':  case 'L':
2107             case 'M':  case 'N':  case 'O':  case 'P':
2108             case 'X':
2109             case '0': case '1':  case '2':  case '3':  case '4':
2110             case '5': case '6':  case '7':  case '8':  case '9':
2111               /* These don't say anything we care about.  */
2112               break;
2113
2114             case '&':
2115               amp_p = true;
2116               break;
2117             case '\0':
2118             case ',':
2119               if (amp_p && class != NO_REGS)
2120                 {
2121                   int rc;
2122
2123                   found = true;
2124                   for (i = 0;
2125                        VEC_iterate (int, earlyclobber_regclass, i, rc);
2126                        i++)
2127                     {
2128                       if (rc == (int) class)
2129                         goto found_rc;
2130                     }
2131
2132                   /* We use VEC_quick_push here because
2133                      earlyclobber_regclass holds no more than
2134                      N_REG_CLASSES elements. */
2135                   VEC_quick_push (int, earlyclobber_regclass, (int) class);
2136                 found_rc:
2137                   ;
2138                 }
2139
2140               amp_p = false;
2141               class = NO_REGS;
2142               break;
2143
2144             case 'r':
2145               class = GENERAL_REGS;
2146               break;
2147
2148             default:
2149               class = REG_CLASS_FROM_CONSTRAINT (c, p);
2150               break;
2151             }
2152           if (c == '\0')
2153             break;
2154           p += CONSTRAINT_LEN (c, p);
2155         }
2156     }
2157
2158   return found;
2159 }
2160
2161 /* The function checks that pseudo-register *X has a class
2162    intersecting with the class of pseudo-register could be early
2163    clobbered in the same insn.
2164
2165    This function is a no-op if earlyclobber_regclass is empty.
2166
2167    Reload can assign the same hard register to uninitialized
2168    pseudo-register and early clobbered pseudo-register in an insn if
2169    the pseudo-register is used first time in given BB and not lived at
2170    the BB start.  To prevent this we don't change life information for
2171    such pseudo-registers.  */
2172
2173 static int
2174 df_urec_mark_reg_use_for_earlyclobber (rtx *x, void *data)
2175 {
2176   enum reg_class pref_class, alt_class;
2177   int i, regno;
2178   struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
2179
2180   if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER)
2181     {
2182       int rc;
2183
2184       regno = REGNO (*x);
2185       if (bitmap_bit_p (bb_info->kill, regno)
2186           || bitmap_bit_p (bb_info->gen, regno))
2187         return 0;
2188       pref_class = reg_preferred_class (regno);
2189       alt_class = reg_alternate_class (regno);
2190       for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++)
2191         {
2192           if (reg_classes_intersect_p (rc, pref_class)
2193               || (rc != NO_REGS
2194                   && reg_classes_intersect_p (rc, alt_class)))
2195             {
2196               bitmap_set_bit (bb_info->earlyclobber, regno);
2197               break;
2198             }
2199         }
2200     }
2201   return 0;
2202 }
2203
2204 /* The function processes all pseudo-registers in *X with the aid of
2205    previous function.  */
2206
2207 static void
2208 df_urec_mark_reg_use_for_earlyclobber_1 (rtx *x, void *data)
2209 {
2210   for_each_rtx (x, df_urec_mark_reg_use_for_earlyclobber, data);
2211 }
2212
2213
2214 /* Compute local uninitialized register info for basic block BB.  */
2215
2216 static void
2217 df_urec_bb_local_compute (unsigned int bb_index)
2218 {
2219   basic_block bb = BASIC_BLOCK (bb_index);
2220   struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2221   rtx insn;
2222   struct df_ref **def_rec;
2223
2224   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2225     {
2226       struct df_ref *def = *def_rec;
2227       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2228         {
2229           unsigned int regno = DF_REF_REGNO (def);
2230           bitmap_set_bit (bb_info->gen, regno);
2231         }
2232     }
2233
2234   FOR_BB_INSNS (bb, insn)
2235     {
2236       if (INSN_P (insn))
2237         {
2238           note_stores (PATTERN (insn), df_urec_mark_reg_change, bb_info);
2239           if (df_urec_check_earlyclobber (insn))
2240             {
2241               struct df_urec_problem_data *problem_data
2242                 = (struct df_urec_problem_data *) df_urec->problem_data;
2243               problem_data->earlyclobbers_found = true;
2244               note_uses (&PATTERN (insn),
2245                          df_urec_mark_reg_use_for_earlyclobber_1, bb_info);
2246             }
2247         }
2248     }
2249
2250   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2251     {
2252       struct df_ref *def = *def_rec;
2253       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2254         {
2255           unsigned int regno = DF_REF_REGNO (def);
2256           bitmap_set_bit (bb_info->gen, regno);
2257         }
2258     }
2259 }
2260
2261
2262 /* Compute local uninitialized register info.  */
2263
2264 static void
2265 df_urec_local_compute (bitmap all_blocks)
2266 {
2267   unsigned int bb_index;
2268   bitmap_iterator bi;
2269 #ifdef STACK_REGS
2270   int i;
2271   HARD_REG_SET stack_hard_regs, used;
2272   struct df_urec_problem_data *problem_data
2273     = (struct df_urec_problem_data *) df_urec->problem_data;
2274
2275   /* Any register that MAY be allocated to a register stack (like the
2276      387) is treated poorly.  Each such register is marked as being
2277      live everywhere.  This keeps the register allocator and the
2278      subsequent passes from doing anything useful with these values.
2279
2280      FIXME: This seems like an incredibly poor idea.  */
2281
2282   CLEAR_HARD_REG_SET (stack_hard_regs);
2283   for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
2284     SET_HARD_REG_BIT (stack_hard_regs, i);
2285   problem_data->stack_regs = BITMAP_ALLOC (NULL);
2286   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2287     {
2288       COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]);
2289       IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]);
2290       AND_HARD_REG_SET (used, stack_hard_regs);
2291       if (!hard_reg_set_empty_p (used))
2292         bitmap_set_bit (problem_data->stack_regs, i);
2293     }
2294 #endif
2295
2296   /* We know that earlyclobber_regclass holds no more than
2297     N_REG_CLASSES elements.  See df_urec_check_earlyclobber.  */
2298   earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES);
2299
2300   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2301     {
2302       df_urec_bb_local_compute (bb_index);
2303     }
2304
2305   VEC_free (int, heap, earlyclobber_regclass);
2306 }
2307
2308
2309 /* Initialize the solution vectors.  */
2310
2311 static void
2312 df_urec_init (bitmap all_blocks)
2313 {
2314   unsigned int bb_index;
2315   bitmap_iterator bi;
2316
2317   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2318     {
2319       struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2320
2321       bitmap_copy (bb_info->out, bb_info->gen);
2322       bitmap_clear (bb_info->in);
2323     }
2324 }
2325
2326
2327 /* Or in the stack regs, hard regs and early clobber regs into the
2328    urec_in sets of all of the blocks.  */
2329
2330
2331 static void
2332 df_urec_local_finalize (bitmap all_blocks)
2333 {
2334   bitmap tmp = BITMAP_ALLOC (NULL);
2335   bitmap_iterator bi;
2336   unsigned int bb_index;
2337   struct df_urec_problem_data *problem_data
2338     = (struct df_urec_problem_data *) df_urec->problem_data;
2339
2340   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2341     {
2342       struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2343       struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
2344
2345       if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK)
2346         {
2347           if (problem_data->earlyclobbers_found)
2348             bitmap_ior_into (bb_info->in, bb_info->earlyclobber);
2349
2350 #ifdef STACK_REGS
2351           /* We can not use the same stack register for uninitialized
2352              pseudo-register and another living pseudo-register
2353              because if the uninitialized pseudo-register dies,
2354              subsequent pass reg-stack will be confused (it will
2355              believe that the other register dies).  */
2356           bitmap_ior_into (bb_info->in, problem_data->stack_regs);
2357           bitmap_ior_into (bb_info->out, problem_data->stack_regs);
2358 #endif
2359         }
2360
2361       /* No register may reach a location where it is not used.  Thus
2362          we trim the rr result to the places where it is used.  */
2363       bitmap_and_into (bb_info->in, bb_lr_info->in);
2364       bitmap_and_into (bb_info->out, bb_lr_info->out);
2365       bitmap_copy (bb_info->top, bb_info->in);
2366       if (bb_lr_info->adef)
2367         bitmap_ior_into (bb_info->top, bb_lr_info->adef);
2368       bitmap_and_into (bb_info->top, bb_lr_info->top);
2369 #if 0
2370       /* Hard registers may still stick in the ur_out set, but not
2371          be in the ur_in set, if their only mention was in a call
2372          in this block.  This is because a call kills in the lr
2373          problem but does not kill in the rr problem.  To clean
2374          this up, we execute the transfer function on the lr_in
2375          set and then use that to knock bits out of ur_out.  */
2376       bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in,
2377                             bb_info->kill);
2378       bitmap_and_into (bb_info->out, tmp);
2379 #endif
2380     }
2381
2382 #ifdef STACK_REGS
2383   BITMAP_FREE (problem_data->stack_regs);
2384 #endif
2385   BITMAP_FREE (tmp);
2386 }
2387
2388
2389 /* Confluence function that ignores fake edges.  */
2390
2391 static void
2392 df_urec_confluence_n (edge e)
2393 {
2394   bitmap op1 = df_urec_get_bb_info (e->dest->index)->in;
2395   bitmap op2 = df_urec_get_bb_info (e->src->index)->out;
2396
2397   if (e->flags & EDGE_FAKE)
2398     return;
2399
2400   bitmap_ior_into (op1, op2);
2401 }
2402
2403
2404 /* Transfer function.  */
2405
2406 static bool
2407 df_urec_transfer_function (int bb_index)
2408 {
2409   struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2410   bitmap in = bb_info->in;
2411   bitmap out = bb_info->out;
2412   bitmap gen = bb_info->gen;
2413   bitmap kill = bb_info->kill;
2414
2415   return bitmap_ior_and_compl (out, gen, in, kill);
2416 }
2417
2418
2419 /* Free all storage associated with the problem.  */
2420
2421 static void
2422 df_urec_free (void)
2423 {
2424   if (df_urec->block_info)
2425     {
2426       unsigned int i;
2427
2428       for (i = 0; i < df_urec->block_info_size; i++)
2429         {
2430           struct df_urec_bb_info *bb_info = df_urec_get_bb_info (i);
2431           if (bb_info)
2432             {
2433               BITMAP_FREE (bb_info->gen);
2434               BITMAP_FREE (bb_info->kill);
2435               BITMAP_FREE (bb_info->in);
2436               BITMAP_FREE (bb_info->out);
2437               BITMAP_FREE (bb_info->earlyclobber);
2438               BITMAP_FREE (bb_info->top);
2439             }
2440         }
2441
2442       free_alloc_pool (df_urec->block_pool);
2443
2444       df_urec->block_info_size = 0;
2445       free (df_urec->block_info);
2446       free (df_urec->problem_data);
2447     }
2448   free (df_urec);
2449 }
2450
2451
2452 /* Debugging info at top of bb.  */
2453
2454 static void
2455 df_urec_top_dump (basic_block bb, FILE *file)
2456 {
2457   struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
2458   if (!bb_info || !bb_info->in)
2459     return;
2460
2461   fprintf (file, ";; urec  in  \t");
2462   df_print_regset (file, bb_info->in);
2463   fprintf (file, ";; urec  gen \t");
2464   df_print_regset (file, bb_info->gen);
2465   fprintf (file, ";; urec  kill\t");
2466   df_print_regset (file, bb_info->kill);
2467   fprintf (file, ";; urec  ec\t");
2468   df_print_regset (file, bb_info->earlyclobber);
2469 }
2470
2471
2472 /* Debugging info at bottom of bb.  */
2473
2474 static void
2475 df_urec_bottom_dump (basic_block bb, FILE *file)
2476 {
2477   struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
2478   if (!bb_info || !bb_info->out)
2479     return;
2480   fprintf (file, ";; urec  out \t");
2481   df_print_regset (file, bb_info->out);
2482 }
2483
2484
2485 /* All of the information associated with every instance of the problem.  */
2486
2487 static struct df_problem problem_UREC =
2488 {
2489   DF_UREC,                    /* Problem id.  */
2490   DF_FORWARD,                 /* Direction.  */
2491   df_urec_alloc,              /* Allocate the problem specific data.  */
2492   NULL,                       /* Reset global information.  */
2493   df_urec_free_bb_info,       /* Free basic block info.  */
2494   df_urec_local_compute,      /* Local compute function.  */
2495   df_urec_init,               /* Init the solution specific data.  */
2496   df_worklist_dataflow,       /* Worklist solver.  */
2497   NULL,                       /* Confluence operator 0.  */
2498   df_urec_confluence_n,       /* Confluence operator n.  */
2499   df_urec_transfer_function,  /* Transfer function.  */
2500   df_urec_local_finalize,     /* Finalize function.  */
2501   df_urec_free,               /* Free all of the problem information.  */
2502   df_urec_free,               /* Remove this problem from the stack of dataflow problems.  */
2503   NULL,                       /* Debugging.  */
2504   df_urec_top_dump,           /* Debugging start block.  */
2505   df_urec_bottom_dump,        /* Debugging end block.  */
2506   NULL,                       /* Incremental solution verify start.  */
2507   NULL,                       /* Incremental solution verify end.  */
2508   &problem_LR,                /* Dependent problem.  */
2509   TV_DF_UREC,                 /* Timing variable.  */
2510   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2511 };
2512
2513
2514 /* Create a new DATAFLOW instance and add it to an existing instance
2515    of DF.  The returned structure is what is used to get at the
2516    solution.  */
2517
2518 void
2519 df_urec_add_problem (void)
2520 {
2521   df_add_problem (&problem_UREC);
2522 }
2523
2524
2525 \f
2526 /*----------------------------------------------------------------------------
2527    CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
2528
2529    Link either the defs to the uses and / or the uses to the defs.
2530
2531    These problems are set up like the other dataflow problems so that
2532    they nicely fit into the framework.  They are much simpler and only
2533    involve a single traversal of instructions and an examination of
2534    the reaching defs information (the dependent problem).
2535 ----------------------------------------------------------------------------*/
2536
2537 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
2538
2539 /* Create a du or ud chain from SRC to DST and link it into SRC.   */
2540
2541 struct df_link *
2542 df_chain_create (struct df_ref *src, struct df_ref *dst)
2543 {
2544   struct df_link *head = DF_REF_CHAIN (src);
2545   struct df_link *link = pool_alloc (df_chain->block_pool);;
2546
2547   DF_REF_CHAIN (src) = link;
2548   link->next = head;
2549   link->ref = dst;
2550   return link;
2551 }
2552
2553
2554 /* Delete any du or ud chains that start at REF and point to
2555    TARGET.  */
2556 static void
2557 df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
2558 {
2559   struct df_link *chain = DF_REF_CHAIN (ref);
2560   struct df_link *prev = NULL;
2561
2562   while (chain)
2563     {
2564       if (chain->ref == target)
2565         {
2566           if (prev)
2567             prev->next = chain->next;
2568           else
2569             DF_REF_CHAIN (ref) = chain->next;
2570           pool_free (df_chain->block_pool, chain);
2571           return;
2572         }
2573       prev = chain;
2574       chain = chain->next;
2575     }
2576 }
2577
2578
2579 /* Delete a du or ud chain that leave or point to REF.  */
2580
2581 void
2582 df_chain_unlink (struct df_ref *ref)
2583 {
2584   struct df_link *chain = DF_REF_CHAIN (ref);
2585   while (chain)
2586     {
2587       struct df_link *next = chain->next;
2588       /* Delete the other side if it exists.  */
2589       df_chain_unlink_1 (chain->ref, ref);
2590       pool_free (df_chain->block_pool, chain);
2591       chain = next;
2592     }
2593   DF_REF_CHAIN (ref) = NULL;
2594 }
2595
2596
2597 /* Copy the du or ud chain starting at FROM_REF and attach it to
2598    TO_REF.  */
2599
2600 void
2601 df_chain_copy (struct df_ref *to_ref,
2602                struct df_link *from_ref)
2603 {
2604   while (from_ref)
2605     {
2606       df_chain_create (to_ref, from_ref->ref);
2607       from_ref = from_ref->next;
2608     }
2609 }
2610
2611
2612 /* Remove this problem from the stack of dataflow problems.  */
2613
2614 static void
2615 df_chain_remove_problem (void)
2616 {
2617   bitmap_iterator bi;
2618   unsigned int bb_index;
2619
2620   /* Wholesale destruction of the old chains.  */
2621   if (df_chain->block_pool)
2622     free_alloc_pool (df_chain->block_pool);
2623
2624   EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
2625     {
2626       rtx insn;
2627       struct df_ref **def_rec;
2628       struct df_ref **use_rec;
2629       basic_block bb = BASIC_BLOCK (bb_index);
2630
2631       if (df_chain_problem_p (DF_DU_CHAIN))
2632         for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
2633           DF_REF_CHAIN (*def_rec) = NULL;
2634       if (df_chain_problem_p (DF_UD_CHAIN))
2635         for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
2636           DF_REF_CHAIN (*use_rec) = NULL;
2637
2638       FOR_BB_INSNS (bb, insn)
2639         {
2640           unsigned int uid = INSN_UID (insn);
2641
2642           if (INSN_P (insn))
2643             {
2644               if (df_chain_problem_p (DF_DU_CHAIN))
2645                 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2646                   DF_REF_CHAIN (*def_rec) = NULL;
2647               if (df_chain_problem_p (DF_UD_CHAIN))
2648                 {
2649                   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2650                     DF_REF_CHAIN (*use_rec) = NULL;
2651                   for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
2652                     DF_REF_CHAIN (*use_rec) = NULL;
2653                 }
2654             }
2655         }
2656     }
2657
2658   bitmap_clear (df_chain->out_of_date_transfer_functions);
2659   df_chain->block_pool = NULL;
2660 }
2661
2662
2663 /* Remove the chain problem completely.  */
2664
2665 static void
2666 df_chain_fully_remove_problem (void)
2667 {
2668   df_chain_remove_problem ();
2669   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2670   free (df_chain);
2671 }
2672
2673
2674 /* Create def-use or use-def chains.  */
2675
2676 static void
2677 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2678 {
2679   df_chain_remove_problem ();
2680   df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
2681                                          sizeof (struct df_link), 50);
2682   df_chain->optional_p = true;
2683 }
2684
2685
2686 /* Reset all of the chains when the set of basic blocks changes.  */
2687
2688 static void
2689 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2690 {
2691   df_chain_remove_problem ();
2692 }
2693
2694
2695 /* Create the chains for a list of USEs.  */
2696
2697 static void
2698 df_chain_create_bb_process_use (bitmap local_rd,
2699                                 struct df_ref **use_rec,
2700                                 enum df_ref_flags top_flag)
2701 {
2702   bitmap_iterator bi;
2703   unsigned int def_index;
2704
2705   while (*use_rec)
2706     {
2707       struct df_ref *use = *use_rec;
2708       unsigned int uregno = DF_REF_REGNO (use);
2709       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2710           || (uregno >= FIRST_PSEUDO_REGISTER))
2711         {
2712           /* Do not want to go through this for an uninitialized var.  */
2713           int count = DF_DEFS_COUNT (uregno);
2714           if (count)
2715             {
2716               if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2717                 {
2718                   unsigned int first_index = DF_DEFS_BEGIN (uregno);
2719                   unsigned int last_index = first_index + count - 1;
2720
2721                   EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2722                     {
2723                       struct df_ref *def;
2724                       if (def_index > last_index)
2725                         break;
2726
2727                       def = DF_DEFS_GET (def_index);
2728                       if (df_chain_problem_p (DF_DU_CHAIN))
2729                         df_chain_create (def, use);
2730                       if (df_chain_problem_p (DF_UD_CHAIN))
2731                         df_chain_create (use, def);
2732                     }
2733                 }
2734             }
2735         }
2736
2737       use_rec++;
2738     }
2739 }
2740
2741
2742 /* Create chains from reaching defs bitmaps for basic block BB.  */
2743
2744 static void
2745 df_chain_create_bb (unsigned int bb_index)
2746 {
2747   basic_block bb = BASIC_BLOCK (bb_index);
2748   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2749   rtx insn;
2750   bitmap cpy = BITMAP_ALLOC (NULL);
2751   struct df_ref **def_rec;
2752
2753   bitmap_copy (cpy, bb_info->in);
2754   bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2755
2756   /* Since we are going forwards, process the artificial uses first
2757      then the artificial defs second.  */
2758
2759 #ifdef EH_USES
2760   /* Create the chains for the artificial uses from the EH_USES at the
2761      beginning of the block.  */
2762
2763   /* Artificials are only hard regs.  */
2764   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2765     df_chain_create_bb_process_use (cpy,
2766                                     df_get_artificial_uses (bb->index),
2767                                     DF_REF_AT_TOP);
2768 #endif
2769
2770   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2771     {
2772       struct df_ref *def = *def_rec;
2773       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2774         {
2775           unsigned int dregno = DF_REF_REGNO (def);
2776           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2777             bitmap_clear_range (cpy,
2778                                 DF_DEFS_BEGIN (dregno),
2779                                 DF_DEFS_COUNT (dregno));
2780           bitmap_set_bit (cpy, DF_REF_ID (def));
2781         }
2782     }
2783
2784   /* Process the regular instructions next.  */
2785   FOR_BB_INSNS (bb, insn)
2786     {
2787       struct df_ref **def_rec;
2788       unsigned int uid = INSN_UID (insn);
2789
2790       if (!INSN_P (insn))
2791         continue;
2792
2793       /* Now scan the uses and link them up with the defs that remain
2794          in the cpy vector.  */
2795
2796       df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
2797
2798       if (df->changeable_flags & DF_EQ_NOTES)
2799         df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
2800
2801
2802       /* Since we are going forwards, process the defs second.  This
2803          pass only changes the bits in cpy.  */
2804       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2805         {
2806           struct df_ref *def = *def_rec;
2807           unsigned int dregno = DF_REF_REGNO (def);
2808           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2809               || (dregno >= FIRST_PSEUDO_REGISTER))
2810             {
2811               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2812                 bitmap_clear_range (cpy,
2813                                     DF_DEFS_BEGIN (dregno),
2814                                     DF_DEFS_COUNT (dregno));
2815               if (!(DF_REF_FLAGS (def)
2816                     & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
2817                 bitmap_set_bit (cpy, DF_REF_ID (def));
2818             }
2819         }
2820     }
2821
2822   /* Create the chains for the artificial uses of the hard registers
2823      at the end of the block.  */
2824   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2825     df_chain_create_bb_process_use (cpy,
2826                                     df_get_artificial_uses (bb->index),
2827                                     0);
2828
2829   BITMAP_FREE (cpy);
2830 }
2831
2832 /* Create def-use chains from reaching use bitmaps for basic blocks
2833    in BLOCKS.  */
2834
2835 static void
2836 df_chain_finalize (bitmap all_blocks)
2837 {
2838   unsigned int bb_index;
2839   bitmap_iterator bi;
2840
2841   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2842     {
2843       df_chain_create_bb (bb_index);
2844     }
2845 }
2846
2847
2848 /* Free all storage associated with the problem.  */
2849
2850 static void
2851 df_chain_free (void)
2852 {
2853   free_alloc_pool (df_chain->block_pool);
2854   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2855   free (df_chain);
2856 }
2857
2858
2859 /* Debugging info.  */
2860
2861 static void
2862 df_chain_top_dump (basic_block bb, FILE *file)
2863 {
2864   if (df_chain_problem_p (DF_DU_CHAIN))
2865     {
2866       rtx insn;
2867       struct df_ref **def_rec = df_get_artificial_defs (bb->index);
2868       if (*def_rec)
2869         {
2870
2871           fprintf (file, ";;  DU chains for artificial defs\n");
2872           while (*def_rec)
2873             {
2874               struct df_ref *def = *def_rec;
2875               fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
2876               df_chain_dump (DF_REF_CHAIN (def), file);
2877               fprintf (file, "\n");
2878               def_rec++;
2879             }
2880         }
2881
2882       FOR_BB_INSNS (bb, insn)
2883         {
2884           unsigned int uid = INSN_UID (insn);
2885           if (INSN_P (insn))
2886             {
2887               def_rec = DF_INSN_UID_DEFS (uid);
2888               if (*def_rec)
2889                 {
2890                   fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
2891                            DF_INSN_LUID (insn), uid);
2892
2893                   while (*def_rec)
2894                     {
2895                       struct df_ref *def = *def_rec;
2896                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
2897                       if (def->flags & DF_REF_READ_WRITE)
2898                         fprintf (file, "read/write ");
2899                       df_chain_dump (DF_REF_CHAIN (def), file);
2900                       fprintf (file, "\n");
2901                       def_rec++;
2902                     }
2903                 }
2904             }
2905         }
2906     }
2907 }
2908
2909
2910 static void
2911 df_chain_bottom_dump (basic_block bb, FILE *file)
2912 {
2913   if (df_chain_problem_p (DF_UD_CHAIN))
2914     {
2915       rtx insn;
2916       struct df_ref **use_rec = df_get_artificial_uses (bb->index);
2917
2918       if (*use_rec)
2919         {
2920           fprintf (file, ";;  UD chains for artificial uses\n");
2921           while (*use_rec)
2922             {
2923               struct df_ref *use = *use_rec;
2924               fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
2925               df_chain_dump (DF_REF_CHAIN (use), file);
2926               fprintf (file, "\n");
2927               use_rec++;
2928             }
2929         }
2930
2931       FOR_BB_INSNS (bb, insn)
2932         {
2933           unsigned int uid = INSN_UID (insn);
2934           if (INSN_P (insn))
2935             {
2936               struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid);
2937               use_rec = DF_INSN_UID_USES (uid);
2938               if (*use_rec || *eq_use_rec)
2939                 {
2940                   fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
2941                            DF_INSN_LUID (insn), uid);
2942
2943                   while (*use_rec)
2944                     {
2945                       struct df_ref *use = *use_rec;
2946                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
2947                       if (use->flags & DF_REF_READ_WRITE)
2948                         fprintf (file, "read/write ");
2949                       df_chain_dump (DF_REF_CHAIN (use), file);
2950                       fprintf (file, "\n");
2951                       use_rec++;
2952                     }
2953                   while (*eq_use_rec)
2954                     {
2955                       struct df_ref *use = *eq_use_rec;
2956                       fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
2957                       df_chain_dump (DF_REF_CHAIN (use), file);
2958                       fprintf (file, "\n");
2959                       eq_use_rec++;
2960                     }
2961                 }
2962             }
2963         }
2964     }
2965 }
2966
2967
2968 static struct df_problem problem_CHAIN =
2969 {
2970   DF_CHAIN,                   /* Problem id.  */
2971   DF_NONE,                    /* Direction.  */
2972   df_chain_alloc,             /* Allocate the problem specific data.  */
2973   df_chain_reset,             /* Reset global information.  */
2974   NULL,                       /* Free basic block info.  */
2975   NULL,                       /* Local compute function.  */
2976   NULL,                       /* Init the solution specific data.  */
2977   NULL,                       /* Iterative solver.  */
2978   NULL,                       /* Confluence operator 0.  */
2979   NULL,                       /* Confluence operator n.  */
2980   NULL,                       /* Transfer function.  */
2981   df_chain_finalize,          /* Finalize function.  */
2982   df_chain_free,              /* Free all of the problem information.  */
2983   df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
2984   NULL,                       /* Debugging.  */
2985   df_chain_top_dump,          /* Debugging start block.  */
2986   df_chain_bottom_dump,       /* Debugging end block.  */
2987   NULL,                       /* Incremental solution verify start.  */
2988   NULL,                       /* Incremental solution verify end.  */
2989   &problem_RD,                /* Dependent problem.  */
2990   TV_DF_CHAIN,                /* Timing variable.  */
2991   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2992 };
2993
2994
2995 /* Create a new DATAFLOW instance and add it to an existing instance
2996    of DF.  The returned structure is what is used to get at the
2997    solution.  */
2998
2999 void
3000 df_chain_add_problem (enum df_chain_flags chain_flags)
3001 {
3002   df_add_problem (&problem_CHAIN);
3003   df_chain->local_flags = (unsigned int)chain_flags;
3004   df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
3005 }
3006
3007 #undef df_chain_problem_p
3008
3009 \f
3010 /*----------------------------------------------------------------------------
3011    This pass computes REG_DEAD and REG_UNUSED notes.
3012    ----------------------------------------------------------------------------*/
3013
3014 static void
3015 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3016 {
3017   df_note->optional_p = true;
3018 }
3019
3020 #ifdef REG_DEAD_DEBUGGING
3021 static void
3022 df_print_note (const char *prefix, rtx insn, rtx note)
3023 {
3024   if (dump_file)
3025     {
3026       fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3027       print_rtl (dump_file, note);
3028       fprintf (dump_file, "\n");
3029     }
3030 }
3031 #endif
3032
3033
3034 /* After reg-stack, the x86 floating point stack regs are difficult to
3035    analyze because of all of the pushes, pops and rotations.  Thus, we
3036    just leave the notes alone. */
3037
3038 #ifdef STACK_REGS
3039 static inline bool
3040 df_ignore_stack_reg (int regno)
3041 {
3042   return regstack_completed
3043     && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3044 }
3045 #else
3046 static inline bool
3047 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3048 {
3049   return false;
3050 }
3051 #endif
3052
3053
3054 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3055    them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES.  */
3056
3057 static void
3058 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
3059 {
3060   rtx *pprev = &REG_NOTES (insn);
3061   rtx link = *pprev;
3062   rtx dead = NULL;
3063   rtx unused = NULL;
3064
3065   while (link)
3066     {
3067       switch (REG_NOTE_KIND (link))
3068         {
3069         case REG_DEAD:
3070           /* After reg-stack, we need to ignore any unused notes
3071              for the stack registers.  */
3072           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3073             {
3074               pprev = &XEXP (link, 1);
3075               link = *pprev;
3076             }
3077           else
3078             {
3079               rtx next = XEXP (link, 1);
3080 #ifdef REG_DEAD_DEBUGGING
3081               df_print_note ("deleting: ", insn, link);
3082 #endif
3083               XEXP (link, 1) = dead;
3084               dead = link;
3085               *pprev = link = next;
3086             }
3087           break;
3088
3089         case REG_UNUSED:
3090           /* After reg-stack, we need to ignore any unused notes
3091              for the stack registers.  */
3092           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3093             {
3094               pprev = &XEXP (link, 1);
3095               link = *pprev;
3096             }
3097           else
3098             {
3099               rtx next = XEXP (link, 1);
3100 #ifdef REG_DEAD_DEBUGGING
3101               df_print_note ("deleting: ", insn, link);
3102 #endif
3103               XEXP (link, 1) = unused;
3104               unused = link;
3105               *pprev = link = next;
3106             }
3107           break;
3108
3109         default:
3110           pprev = &XEXP (link, 1);
3111           link = *pprev;
3112           break;
3113         }
3114     }
3115
3116   *old_dead_notes = dead;
3117   *old_unused_notes = unused;
3118 }
3119
3120
3121 /* Set a NOTE_TYPE note for REG in INSN.  Try to pull it from the OLD
3122    list, otherwise create a new one.  */
3123
3124 static inline rtx
3125 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
3126 {
3127   rtx this = old;
3128   rtx prev = NULL;
3129
3130   while (this)
3131     if (XEXP (this, 0) == reg)
3132       {
3133         if (prev)
3134           XEXP (prev, 1) = XEXP (this, 1);
3135         else
3136           old = XEXP (this, 1);
3137         XEXP (this, 1) = REG_NOTES (insn);
3138         REG_NOTES (insn) = this;
3139         return old;
3140       }
3141     else
3142       {
3143         prev = this;
3144         this = XEXP (this, 1);
3145       }
3146
3147   /* Did not find the note.  */
3148   REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
3149   return old;
3150 }
3151
3152 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3153    arguments.  Return true if the register value described by MWS's
3154    mw_reg is known to be completely unused, and if mw_reg can therefore
3155    be used in a REG_UNUSED note.  */
3156
3157 static bool
3158 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3159                           bitmap live, bitmap artificial_uses)
3160 {
3161   unsigned int r;
3162
3163   /* If MWS describes a partial reference, create REG_UNUSED notes for
3164      individual hard registers.  */
3165   if (mws->flags & DF_REF_PARTIAL)
3166     return false;
3167
3168   /* Likewise if some part of the register is used.  */
3169   for (r = mws->start_regno; r <= mws->end_regno; r++)
3170     if (bitmap_bit_p (live, r)
3171         || bitmap_bit_p (artificial_uses, r))
3172       return false;
3173
3174   gcc_assert (REG_P (mws->mw_reg));
3175   return true;
3176 }
3177
3178 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3179    based on the bits in LIVE.  Do not generate notes for registers in
3180    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
3181    not generated if the reg is both read and written by the
3182    instruction.
3183 */
3184
3185 static rtx
3186 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3187                             bitmap live, bitmap do_not_gen,
3188                             bitmap artificial_uses)
3189 {
3190   unsigned int r;
3191
3192 #ifdef REG_DEAD_DEBUGGING
3193   if (dump_file)
3194     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3195              mws->start_regno, mws->end_regno);
3196 #endif
3197
3198   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3199     {
3200       unsigned int regno = mws->start_regno;
3201       old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
3202
3203 #ifdef REG_DEAD_DEBUGGING
3204       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3205 #endif
3206       bitmap_set_bit (do_not_gen, regno);
3207       /* Only do this if the value is totally dead.  */
3208     }
3209   else
3210     for (r = mws->start_regno; r <= mws->end_regno; r++)
3211       {
3212         if (!bitmap_bit_p (live, r)
3213             && !bitmap_bit_p (artificial_uses, r))
3214           {
3215             old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3216 #ifdef REG_DEAD_DEBUGGING
3217             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3218 #endif
3219           }
3220         bitmap_set_bit (do_not_gen, r);
3221       }
3222   return old;
3223 }
3224
3225
3226 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3227    arguments.  Return true if the register value described by MWS's
3228    mw_reg is known to be completely dead, and if mw_reg can therefore
3229    be used in a REG_DEAD note.  */
3230
3231 static bool
3232 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3233                         bitmap live, bitmap artificial_uses,
3234                         bitmap do_not_gen)
3235 {
3236   unsigned int r;
3237
3238   /* If MWS describes a partial reference, create REG_DEAD notes for
3239      individual hard registers.  */
3240   if (mws->flags & DF_REF_PARTIAL)
3241     return false;
3242
3243   /* Likewise if some part of the register is not dead.  */
3244   for (r = mws->start_regno; r <= mws->end_regno; r++)
3245     if (bitmap_bit_p (live, r)
3246         || bitmap_bit_p (artificial_uses, r)
3247         || bitmap_bit_p (do_not_gen, r))
3248       return false;
3249
3250   gcc_assert (REG_P (mws->mw_reg));
3251   return true;
3252 }
3253
3254 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3255    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
3256    from being set if the instruction both reads and writes the
3257    register.  */
3258
3259 static rtx
3260 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3261                           bitmap live, bitmap do_not_gen,
3262                           bitmap artificial_uses)
3263 {
3264   unsigned int r;
3265
3266 #ifdef REG_DEAD_DEBUGGING
3267   if (dump_file)
3268     {
3269       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
3270                mws->start_regno, mws->end_regno);
3271       df_print_regset (dump_file, do_not_gen);
3272       fprintf (dump_file, "  live =");
3273       df_print_regset (dump_file, live);
3274       fprintf (dump_file, "  artificial uses =");
3275       df_print_regset (dump_file, artificial_uses);
3276     }
3277 #endif
3278
3279   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3280     {
3281       /* Add a dead note for the entire multi word register.  */
3282       old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
3283 #ifdef REG_DEAD_DEBUGGING
3284       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3285 #endif
3286     }
3287   else
3288     {
3289       for (r = mws->start_regno; r <= mws->end_regno; r++)
3290         if (!bitmap_bit_p (live, r)
3291             && !bitmap_bit_p (artificial_uses, r)
3292             && !bitmap_bit_p (do_not_gen, r))
3293           {
3294             old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3295 #ifdef REG_DEAD_DEBUGGING
3296             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3297 #endif
3298           }
3299     }
3300   return old;
3301 }
3302
3303
3304 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3305    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
3306
3307 static rtx
3308 df_create_unused_note (rtx insn, rtx old, struct df_ref *def,
3309                        bitmap live, bitmap artificial_uses)
3310 {
3311   unsigned int dregno = DF_REF_REGNO (def);
3312
3313 #ifdef REG_DEAD_DEBUGGING
3314   if (dump_file)
3315     {
3316       fprintf (dump_file, "  regular looking at def ");
3317       df_ref_debug (def, dump_file);
3318     }
3319 #endif
3320
3321   if (!(bitmap_bit_p (live, dregno)
3322         || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3323         || bitmap_bit_p (artificial_uses, dregno)
3324         || df_ignore_stack_reg (dregno)))
3325     {
3326       rtx reg = (DF_REF_LOC (def))
3327                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3328       old = df_set_note (REG_UNUSED, insn, old, reg);
3329 #ifdef REG_DEAD_DEBUGGING
3330       df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3331 #endif
3332     }
3333
3334   return old;
3335 }
3336
3337
3338 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3339    info: lifetime, bb, and number of defs and uses for basic block
3340    BB.  The three bitvectors are scratch regs used here.  */
3341
3342 static void
3343 df_note_bb_compute (unsigned int bb_index,
3344                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3345 {
3346   basic_block bb = BASIC_BLOCK (bb_index);
3347   rtx insn;
3348   struct df_ref **def_rec;
3349   struct df_ref **use_rec;
3350
3351   bitmap_copy (live, df_get_live_out (bb));
3352   bitmap_clear (artificial_uses);
3353
3354 #ifdef REG_DEAD_DEBUGGING
3355   if (dump_file)
3356     {
3357       fprintf (dump_file, "live at bottom ");
3358       df_print_regset (dump_file, live);
3359     }
3360 #endif
3361
3362   /* Process the artificial defs and uses at the bottom of the block
3363      to begin processing.  */
3364   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3365     {
3366       struct df_ref *def = *def_rec;
3367 #ifdef REG_DEAD_DEBUGGING
3368       if (dump_file)
3369         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3370 #endif
3371
3372       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3373         bitmap_clear_bit (live, DF_REF_REGNO (def));
3374     }
3375
3376   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3377     {
3378       struct df_ref *use = *use_rec;
3379       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3380         {
3381           unsigned int regno = DF_REF_REGNO (use);
3382           bitmap_set_bit (live, regno);
3383
3384           /* Notes are not generated for any of the artificial registers
3385              at the bottom of the block.  */
3386           bitmap_set_bit (artificial_uses, regno);
3387         }
3388     }
3389
3390 #ifdef REG_DEAD_DEBUGGING
3391   if (dump_file)
3392     {
3393       fprintf (dump_file, "live before artificials out ");
3394       df_print_regset (dump_file, live);
3395     }
3396 #endif
3397
3398   FOR_BB_INSNS_REVERSE (bb, insn)
3399     {
3400       unsigned int uid = INSN_UID (insn);
3401       struct df_mw_hardreg **mws_rec;
3402       rtx old_dead_notes;
3403       rtx old_unused_notes;
3404
3405       if (!INSN_P (insn))
3406         continue;
3407
3408       bitmap_clear (do_not_gen);
3409       df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3410
3411       /* Process the defs.  */
3412       if (CALL_P (insn))
3413         {
3414 #ifdef REG_DEAD_DEBUGGING
3415           if (dump_file)
3416             {
3417               fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
3418               df_print_regset (dump_file, live);
3419             }
3420 #endif
3421           /* We only care about real sets for calls.  Clobbers cannot
3422              be depended on to really die.  */
3423           mws_rec = DF_INSN_UID_MWS (uid);
3424           while (*mws_rec)
3425             {
3426               struct df_mw_hardreg *mws = *mws_rec;
3427               if ((mws->type == DF_REF_REG_DEF)
3428                   && !df_ignore_stack_reg (mws->start_regno))
3429                 old_unused_notes
3430                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
3431                                                 mws, live, do_not_gen,
3432                                                 artificial_uses);
3433               mws_rec++;
3434             }
3435
3436           /* All of the defs except the return value are some sort of
3437              clobber.  This code is for the return.  */
3438           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3439             {
3440               struct df_ref *def = *def_rec;
3441               unsigned int dregno = DF_REF_REGNO (def);
3442               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3443                 {
3444                   old_unused_notes
3445                     = df_create_unused_note (insn, old_unused_notes,
3446                                              def, live, artificial_uses);
3447                   bitmap_set_bit (do_not_gen, dregno);
3448                 }
3449
3450               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3451                 bitmap_clear_bit (live, dregno);
3452             }
3453         }
3454       else
3455         {
3456           /* Regular insn.  */
3457           mws_rec = DF_INSN_UID_MWS (uid);
3458           while (*mws_rec)
3459             {
3460               struct df_mw_hardreg *mws = *mws_rec;
3461               if (mws->type == DF_REF_REG_DEF)
3462                 old_unused_notes
3463                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
3464                                                 mws, live, do_not_gen,
3465                                                 artificial_uses);
3466               mws_rec++;
3467             }
3468
3469           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3470             {
3471               struct df_ref *def = *def_rec;
3472               unsigned int dregno = DF_REF_REGNO (def);
3473               old_unused_notes
3474                 = df_create_unused_note (insn, old_unused_notes,
3475                                          def, live, artificial_uses);
3476
3477               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3478                 bitmap_set_bit (do_not_gen, dregno);
3479
3480               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3481                 bitmap_clear_bit (live, dregno);
3482             }
3483         }
3484
3485       /* Process the uses.  */
3486       mws_rec = DF_INSN_UID_MWS (uid);
3487       while (*mws_rec)
3488         {
3489           struct df_mw_hardreg *mws = *mws_rec;
3490           if ((mws->type != DF_REF_REG_DEF)
3491               && !df_ignore_stack_reg (mws->start_regno))
3492             old_dead_notes
3493               = df_set_dead_notes_for_mw (insn, old_dead_notes,
3494                                           mws, live, do_not_gen,
3495                                           artificial_uses);
3496           mws_rec++;
3497         }
3498
3499       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3500         {
3501           struct df_ref *use = *use_rec;
3502           unsigned int uregno = DF_REF_REGNO (use);
3503
3504 #ifdef REG_DEAD_DEBUGGING
3505           if (dump_file)
3506             {
3507               fprintf (dump_file, "  regular looking at use ");
3508               df_ref_debug (use, dump_file);
3509             }
3510 #endif
3511           if (!bitmap_bit_p (live, uregno))
3512             {
3513               if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
3514                    && (!bitmap_bit_p (do_not_gen, uregno))
3515                    && (!bitmap_bit_p (artificial_uses, uregno))
3516                    && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
3517                    && (!df_ignore_stack_reg (uregno)))
3518                 {
3519                   rtx reg = (DF_REF_LOC (use))
3520                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3521                   old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
3522
3523 #ifdef REG_DEAD_DEBUGGING
3524                   df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3525 #endif
3526                 }
3527               /* This register is now live.  */
3528               bitmap_set_bit (live, uregno);
3529             }
3530         }
3531
3532       while (old_unused_notes)
3533         {
3534           rtx next = XEXP (old_unused_notes, 1);
3535           free_EXPR_LIST_node (old_unused_notes);
3536           old_unused_notes = next;
3537         }
3538       while (old_dead_notes)
3539         {
3540           rtx next = XEXP (old_dead_notes, 1);
3541           free_EXPR_LIST_node (old_dead_notes);
3542           old_dead_notes = next;
3543         }
3544     }
3545 }
3546
3547
3548 /* Compute register info: lifetime, bb, and number of defs and uses.  */
3549 static void
3550 df_note_compute (bitmap all_blocks)
3551 {
3552   unsigned int bb_index;
3553   bitmap_iterator bi;
3554   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
3555   bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
3556   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
3557
3558 #ifdef REG_DEAD_DEBUGGING
3559   if (dump_file)
3560     print_rtl_with_bb (dump_file, get_insns());
3561 #endif
3562
3563   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3564   {
3565     df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
3566   }
3567
3568   BITMAP_FREE (live);
3569   BITMAP_FREE (do_not_gen);
3570   BITMAP_FREE (artificial_uses);
3571 }
3572
3573
3574 /* Free all storage associated with the problem.  */
3575
3576 static void
3577 df_note_free (void)
3578 {
3579   free (df_note);
3580 }
3581
3582
3583 /* All of the information associated every instance of the problem.  */
3584
3585 static struct df_problem problem_NOTE =
3586 {
3587   DF_NOTE,                    /* Problem id.  */
3588   DF_NONE,                    /* Direction.  */
3589   df_note_alloc,              /* Allocate the problem specific data.  */
3590   NULL,                       /* Reset global information.  */
3591   NULL,                       /* Free basic block info.  */
3592   df_note_compute,            /* Local compute function.  */
3593   NULL,                       /* Init the solution specific data.  */
3594   NULL,                       /* Iterative solver.  */
3595   NULL,                       /* Confluence operator 0.  */
3596   NULL,                       /* Confluence operator n.  */
3597   NULL,                       /* Transfer function.  */
3598   NULL,                       /* Finalize function.  */
3599   df_note_free,               /* Free all of the problem information.  */
3600   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
3601   NULL,                       /* Debugging.  */
3602   NULL,                       /* Debugging start block.  */
3603   NULL,                       /* Debugging end block.  */
3604   NULL,                       /* Incremental solution verify start.  */
3605   NULL,                       /* Incremental solution verify end.  */
3606
3607   /* Technically this is only dependent on the live registers problem
3608      but it will produce information if built one of uninitialized
3609      register problems (UR, UREC) is also run.  */
3610   &problem_LR,                /* Dependent problem.  */
3611   TV_DF_NOTE,                 /* Timing variable.  */
3612   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
3613 };
3614
3615
3616 /* Create a new DATAFLOW instance and add it to an existing instance
3617    of DF.  The returned structure is what is used to get at the
3618    solution.  */
3619
3620 void
3621 df_note_add_problem (void)
3622 {
3623   df_add_problem (&problem_NOTE);
3624 }
3625
3626
3627
3628 \f
3629 /*----------------------------------------------------------------------------
3630    Functions for simulating the effects of single insns.
3631
3632    You can either simulate in the forwards direction, starting from
3633    the top of a block or the backwards direction from the end of the
3634    block.  The main difference is that if you go forwards, the uses
3635    are examined first then the defs, and if you go backwards, the defs
3636    are examined first then the uses.
3637
3638    If you start at the top of the block, use one of DF_LIVE_IN or
3639    DF_LR_IN.  If you start at the bottom of the block use one of
3640    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
3641    THEY WILL BE DESTROYED.
3642
3643 ----------------------------------------------------------------------------*/
3644
3645
3646 /* Find the set of DEFs for INSN.  */
3647
3648 void
3649 df_simulate_find_defs (rtx insn, bitmap defs)
3650 {
3651   struct df_ref **def_rec;
3652   unsigned int uid = INSN_UID (insn);
3653
3654   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3655     {
3656       struct df_ref *def = *def_rec;
3657       /* If the def is to only part of the reg, it does
3658          not kill the other defs that reach here.  */
3659       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3660         bitmap_set_bit (defs, DF_REF_REGNO (def));
3661     }
3662 }
3663
3664
3665 /* Simulate the effects of the defs of INSN on LIVE.  */
3666
3667 void
3668 df_simulate_defs (rtx insn, bitmap live)
3669 {
3670   struct df_ref **def_rec;
3671   unsigned int uid = INSN_UID (insn);
3672
3673   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3674     {
3675       struct df_ref *def = *def_rec;
3676       unsigned int dregno = DF_REF_REGNO (def);
3677
3678       /* If the def is to only part of the reg, it does
3679          not kill the other defs that reach here.  */
3680       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3681         bitmap_clear_bit (live, dregno);
3682     }
3683 }
3684
3685
3686 /* Simulate the effects of the uses of INSN on LIVE.  */
3687
3688 void
3689 df_simulate_uses (rtx insn, bitmap live)
3690 {
3691   struct df_ref **use_rec;
3692   unsigned int uid = INSN_UID (insn);
3693
3694   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3695     {
3696       struct df_ref *use = *use_rec;
3697       /* Add use to set of uses in this BB.  */
3698       bitmap_set_bit (live, DF_REF_REGNO (use));
3699     }
3700 }
3701
3702
3703 /* Add back the always live regs in BB to LIVE.  */
3704
3705 static inline void
3706 df_simulate_fixup_sets (basic_block bb, bitmap live)
3707 {
3708   /* These regs are considered always live so if they end up dying
3709      because of some def, we need to bring the back again.  */
3710   if (df_has_eh_preds (bb))
3711     bitmap_ior_into (live, df->eh_block_artificial_uses);
3712   else
3713     bitmap_ior_into (live, df->regular_block_artificial_uses);
3714 }
3715
3716
3717 /* Apply the artificial uses and defs at the top of BB in a forwards
3718    direction.  */
3719
3720 void
3721 df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
3722 {
3723   struct df_ref **def_rec;
3724   struct df_ref **use_rec;
3725   int bb_index = bb->index;
3726
3727   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3728     {
3729       struct df_ref *use = *use_rec;
3730       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3731         bitmap_set_bit (live, DF_REF_REGNO (use));
3732     }
3733
3734   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3735     {
3736       struct df_ref *def = *def_rec;
3737       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3738         bitmap_clear_bit (live, DF_REF_REGNO (def));
3739     }
3740 }
3741
3742
3743 /* Simulate the forwards effects of INSN on the bitmap LIVE.  */
3744
3745 void
3746 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
3747 {
3748   if (! INSN_P (insn))
3749     return;
3750
3751   df_simulate_uses (insn, live);
3752   df_simulate_defs (insn, live);
3753   df_simulate_fixup_sets (bb, live);
3754 }
3755
3756
3757 /* Apply the artificial uses and defs at the end of BB in a backwards
3758    direction.  */
3759
3760 void
3761 df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3762 {
3763   struct df_ref **def_rec;
3764   struct df_ref **use_rec;
3765   int bb_index = bb->index;
3766
3767   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3768     {
3769       struct df_ref *def = *def_rec;
3770       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3771         bitmap_clear_bit (live, DF_REF_REGNO (def));
3772     }
3773
3774   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3775     {
3776       struct df_ref *use = *use_rec;
3777       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3778         bitmap_set_bit (live, DF_REF_REGNO (use));
3779     }
3780 }
3781
3782
3783 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3784
3785 void
3786 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
3787 {
3788   if (! INSN_P (insn))
3789     return;
3790
3791   df_simulate_defs (insn, live);
3792   df_simulate_uses (insn, live);
3793   df_simulate_fixup_sets (bb, live);
3794 }
3795
3796