gcc/df-scan.c

   1 /* Scanning of rtl for dataflow analysis.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
   3    2008  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 "tree.h"
  44 #include "target.h"
  45 #include "target-def.h"
  46 #include "df.h"
  47 #include "tree-pass.h"
  48
  49 #ifndef HAVE_epilogue
  50 #define HAVE_epilogue 0
  51 #endif
  52 #ifndef HAVE_prologue
  53 #define HAVE_prologue 0
  54 #endif
  55 #ifndef HAVE_sibcall_epilogue
  56 #define HAVE_sibcall_epilogue 0
  57 #endif
  58
  59 #ifndef EPILOGUE_USES
  60 #define EPILOGUE_USES(REGNO)  0
  61 #endif
  62
  63 /* The bitmap_obstack is used to hold some static variables that
  64    should not be reset after each function is compiled.  */
  65
  66 static bitmap_obstack persistent_obstack;
  67
  68 /* The set of hard registers in eliminables[i].from. */
  69
  70 static HARD_REG_SET elim_reg_set;
  71
  72 /* This is a bitmap copy of regs_invalidated_by_call so that we can
  73    easily add it into bitmaps, etc. */
  74
  75 bitmap df_invalidated_by_call = NULL;
  76
  77 /* Initialize ur_in and ur_out as if all hard registers were partially
  78    available.  */
  79
  80 struct df_collection_rec
  81 {
  82   struct df_ref ** def_vec;
  83   unsigned int next_def;
  84   struct df_ref ** use_vec;
  85   unsigned int next_use;
  86   struct df_ref ** eq_use_vec;
  87   unsigned int next_eq_use;
  88   struct df_mw_hardreg **mw_vec;
  89   unsigned int next_mw;
  90 };
  91
  92 static struct df_ref * df_null_ref_rec[1];
  93 static struct df_mw_hardreg * df_null_mw_rec[1];
  94
  95 static void df_ref_record (struct df_collection_rec *,
  96                            rtx, rtx *,
  97                            basic_block, rtx, enum df_ref_type,
  98                            enum df_ref_flags);
  99 static void df_def_record_1 (struct df_collection_rec *,
 100                              rtx, basic_block, rtx,
 101                              enum df_ref_flags);
 102 static void df_defs_record (struct df_collection_rec *,
 103                             rtx, basic_block, rtx,
 104                             enum df_ref_flags);
 105 static void df_uses_record (struct df_collection_rec *,
 106                             rtx *, enum df_ref_type,
 107                             basic_block, rtx, enum df_ref_flags);
 108
 109 static struct df_ref *df_ref_create_structure (struct df_collection_rec *, rtx, rtx *,
 110                                                basic_block, rtx, enum df_ref_type,
 111                                                enum df_ref_flags);
 112
 113 static void df_insn_refs_collect (struct df_collection_rec*,
 114                                   basic_block, rtx);
 115 static void df_canonize_collection_rec (struct df_collection_rec *);
 116
 117 static void df_get_regular_block_artificial_uses (bitmap);
 118 static void df_get_eh_block_artificial_uses (bitmap);
 119
 120 static void df_record_entry_block_defs (bitmap);
 121 static void df_record_exit_block_uses (bitmap);
 122 static void df_get_exit_block_use_set (bitmap);
 123 static void df_get_entry_block_def_set (bitmap);
 124 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
 125 static void df_ref_chain_delete_du_chain (struct df_ref **);
 126 static void df_ref_chain_delete (struct df_ref **);
 127
 128 static void df_refs_add_to_chains (struct df_collection_rec *,
 129                                    basic_block, rtx);
 130
 131 static bool df_insn_refs_verify (struct df_collection_rec *, basic_block, rtx, bool);
 132 static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap);
 133 static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
 134 static void df_install_ref (struct df_ref *, struct df_reg_info *,
 135                             struct df_ref_info *, bool);
 136
 137 static int df_ref_compare (const void *, const void *);
 138 static int df_mw_compare (const void *, const void *);
 139
 140 /* Indexed by hardware reg number, is true if that register is ever
 141    used in the current function.
 142
 143    In df-scan.c, this is set up to record the hard regs used
 144    explicitly.  Reload adds in the hard regs used for holding pseudo
 145    regs.  Final uses it to generate the code in the function prologue
 146    and epilogue to save and restore registers as needed.  */
 147
 148 static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
 149 \f
 150 /*----------------------------------------------------------------------------
 151    SCANNING DATAFLOW PROBLEM
 152
 153    There are several ways in which scanning looks just like the other
 154    dataflow problems.  It shares the all the mechanisms for local info
 155    as well as basic block info.  Where it differs is when and how often
 156    it gets run.  It also has no need for the iterative solver.
 157 ----------------------------------------------------------------------------*/
 158
 159 /* Problem data for the scanning dataflow function.  */
 160 struct df_scan_problem_data
 161 {
 162   alloc_pool ref_pool;
 163   alloc_pool insn_pool;
 164   alloc_pool reg_pool;
 165   alloc_pool mw_reg_pool;
 166   alloc_pool mw_link_pool;
 167   bitmap_obstack reg_bitmaps;
 168   bitmap_obstack insn_bitmaps;
 169 };
 170
 171 typedef struct df_scan_bb_info *df_scan_bb_info_t;
 172
 173 static void
 174 df_scan_free_internal (void)
 175 {
 176   struct df_scan_problem_data *problem_data
 177     = (struct df_scan_problem_data *) df_scan->problem_data;
 178
 179   free (df->def_info.refs);
 180   free (df->def_info.begin);
 181   free (df->def_info.count);
 182   memset (&df->def_info, 0, (sizeof (struct df_ref_info)));
 183
 184   free (df->use_info.refs);
 185   free (df->use_info.begin);
 186   free (df->use_info.count);
 187   memset (&df->use_info, 0, (sizeof (struct df_ref_info)));
 188
 189   free (df->def_regs);
 190   df->def_regs = NULL;
 191   free (df->use_regs);
 192   df->use_regs = NULL;
 193   free (df->eq_use_regs);
 194   df->eq_use_regs = NULL;
 195   df->regs_size = 0;
 196   DF_REG_SIZE(df) = 0;
 197
 198   free (df->insns);
 199   df->insns = NULL;
 200   DF_INSN_SIZE () = 0;
 201
 202   free (df_scan->block_info);
 203   df_scan->block_info = NULL;
 204   df_scan->block_info_size = 0;
 205
 206   BITMAP_FREE (df->hardware_regs_used);
 207   BITMAP_FREE (df->regular_block_artificial_uses);
 208   BITMAP_FREE (df->eh_block_artificial_uses);
 209   BITMAP_FREE (df->entry_block_defs);
 210   BITMAP_FREE (df->exit_block_uses);
 211   BITMAP_FREE (df->insns_to_delete);
 212   BITMAP_FREE (df->insns_to_rescan);
 213   BITMAP_FREE (df->insns_to_notes_rescan);
 214
 215   free_alloc_pool (df_scan->block_pool);
 216   free_alloc_pool (problem_data->ref_pool);
 217   free_alloc_pool (problem_data->insn_pool);
 218   free_alloc_pool (problem_data->reg_pool);
 219   free_alloc_pool (problem_data->mw_reg_pool);
 220   free_alloc_pool (problem_data->mw_link_pool);
 221   bitmap_obstack_release (&problem_data->reg_bitmaps);
 222   bitmap_obstack_release (&problem_data->insn_bitmaps);
 223   free (df_scan->problem_data);
 224 }
 225
 226
 227 /* Set basic block info.  */
 228
 229 static void
 230 df_scan_set_bb_info (unsigned int index,
 231                      struct df_scan_bb_info *bb_info)
 232 {
 233   gcc_assert (df_scan);
 234   df_grow_bb_info (df_scan);
 235   df_scan->block_info[index] = (void *) bb_info;
 236 }
 237
 238
 239 /* Free basic block info.  */
 240
 241 static void
 242 df_scan_free_bb_info (basic_block bb, void *vbb_info)
 243 {
 244   struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
 245   unsigned int bb_index = bb->index;
 246   if (bb_info)
 247     {
 248       rtx insn;
 249       FOR_BB_INSNS (bb, insn)
 250         {
 251           if (INSN_P (insn))
 252             /* Record defs within INSN.  */
 253             df_insn_delete (bb, INSN_UID (insn));
 254         }
 255
 256       if (bb_index < df_scan->block_info_size)
 257         bb_info = df_scan_get_bb_info (bb_index);
 258
 259       /* Get rid of any artificial uses or defs.  */
 260       df_ref_chain_delete_du_chain (bb_info->artificial_defs);
 261       df_ref_chain_delete_du_chain (bb_info->artificial_uses);
 262       df_ref_chain_delete (bb_info->artificial_defs);
 263       df_ref_chain_delete (bb_info->artificial_uses);
 264       bb_info->artificial_defs = NULL;
 265       bb_info->artificial_uses = NULL;
 266       pool_free (df_scan->block_pool, bb_info);
 267     }
 268 }
 269
 270
 271 /* Allocate the problem data for the scanning problem.  This should be
 272    called when the problem is created or when the entire function is to
 273    be rescanned.  */
 274 void
 275 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
 276 {
 277   struct df_scan_problem_data *problem_data;
 278   unsigned int insn_num = get_max_uid () + 1;
 279   unsigned int block_size = 400;
 280   basic_block bb;
 281
 282   /* Given the number of pools, this is really faster than tearing
 283      everything apart.  */
 284   if (df_scan->problem_data)
 285     df_scan_free_internal ();
 286
 287   df_scan->block_pool
 288     = create_alloc_pool ("df_scan_block pool",
 289                          sizeof (struct df_scan_bb_info),
 290                          block_size);
 291
 292   problem_data = XNEW (struct df_scan_problem_data);
 293   df_scan->problem_data = problem_data;
 294   df_scan->computed = true;
 295
 296   problem_data->ref_pool
 297     = create_alloc_pool ("df_scan_ref pool",
 298                          sizeof (struct df_ref), block_size);
 299   problem_data->insn_pool
 300     = create_alloc_pool ("df_scan_insn pool",
 301                          sizeof (struct df_insn_info), block_size);
 302   problem_data->reg_pool
 303     = create_alloc_pool ("df_scan_reg pool",
 304                          sizeof (struct df_reg_info), block_size);
 305   problem_data->mw_reg_pool
 306     = create_alloc_pool ("df_scan_mw_reg pool",
 307                          sizeof (struct df_mw_hardreg), block_size);
 308   problem_data->mw_link_pool
 309     = create_alloc_pool ("df_scan_mw_link pool",
 310                          sizeof (struct df_link), block_size);
 311
 312   bitmap_obstack_initialize (&problem_data->reg_bitmaps);
 313   bitmap_obstack_initialize (&problem_data->insn_bitmaps);
 314
 315   insn_num += insn_num / 4;
 316   df_grow_reg_info ();
 317
 318   df_grow_insn_info ();
 319   df_grow_bb_info (df_scan);
 320
 321   FOR_ALL_BB (bb)
 322     {
 323       unsigned int bb_index = bb->index;
 324       struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
 325       if (!bb_info)
 326         {
 327           bb_info = (struct df_scan_bb_info *) pool_alloc (df_scan->block_pool);
 328           df_scan_set_bb_info (bb_index, bb_info);
 329         }
 330       bb_info->artificial_defs = NULL;
 331       bb_info->artificial_uses = NULL;
 332     }
 333
 334   df->hardware_regs_used = BITMAP_ALLOC (&problem_data->reg_bitmaps);
 335   df->regular_block_artificial_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
 336   df->eh_block_artificial_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
 337   df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
 338   df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
 339   df->insns_to_delete = BITMAP_ALLOC (&problem_data->insn_bitmaps);
 340   df->insns_to_rescan = BITMAP_ALLOC (&problem_data->insn_bitmaps);
 341   df->insns_to_notes_rescan = BITMAP_ALLOC (&problem_data->insn_bitmaps);
 342   df_scan->optional_p = false;
 343 }
 344
 345
 346 /* Free all of the data associated with the scan problem.  */
 347
 348 static void
 349 df_scan_free (void)
 350 {
 351   if (df_scan->problem_data)
 352     df_scan_free_internal ();
 353
 354   if (df->blocks_to_analyze)
 355     {
 356       BITMAP_FREE (df->blocks_to_analyze);
 357       df->blocks_to_analyze = NULL;
 358     }
 359
 360   free (df_scan);
 361 }
 362
 363 /* Dump the preamble for DF_SCAN dump. */
 364 static void
 365 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
 366 {
 367   int i;
 368
 369   fprintf (file, ";;  invalidated by call \t");
 370   df_print_regset (file, df_invalidated_by_call);
 371   fprintf (file, ";;  hardware regs used \t");
 372   df_print_regset (file, df->hardware_regs_used);
 373   fprintf (file, ";;  regular block artificial uses \t");
 374   df_print_regset (file, df->regular_block_artificial_uses);
 375   fprintf (file, ";;  eh block artificial uses \t");
 376   df_print_regset (file, df->eh_block_artificial_uses);
 377   fprintf (file, ";;  entry block defs \t");
 378   df_print_regset (file, df->entry_block_defs);
 379   fprintf (file, ";;  exit block uses \t");
 380   df_print_regset (file, df->exit_block_uses);
 381   fprintf (file, ";;  regs ever live \t");
 382   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 383     if (df_regs_ever_live_p (i))
 384       fprintf (file, " %d[%s]", i, reg_names[i]);
 385
 386   fprintf (file, "\n");
 387 }
 388
 389 /* Dump the bb_info for a given basic block. */
 390 static void
 391 df_scan_start_block (basic_block bb, FILE *file)
 392 {
 393   struct df_scan_bb_info *bb_info
 394     = df_scan_get_bb_info (bb->index);
 395
 396   if (bb_info)
 397     {
 398       fprintf (file, ";; bb %d artificial_defs: ", bb->index);
 399       df_refs_chain_dump (bb_info->artificial_defs, true, file);
 400       fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
 401       df_refs_chain_dump (bb_info->artificial_uses, true, file);
 402       fprintf (file, "\n");
 403     }
 404 #if 0
 405   {
 406     rtx insn;
 407     FOR_BB_INSNS (bb, insn)
 408       if (INSN_P (insn))
 409         df_insn_debug (insn, false, file);
 410   }
 411 #endif
 412 }
 413
 414 static struct df_problem problem_SCAN =
 415 {
 416   DF_SCAN,                    /* Problem id.  */
 417   DF_NONE,                    /* Direction.  */
 418   df_scan_alloc,              /* Allocate the problem specific data.  */
 419   NULL,                       /* Reset global information.  */
 420   df_scan_free_bb_info,       /* Free basic block info.  */
 421   NULL,                       /* Local compute function.  */
 422   NULL,                       /* Init the solution specific data.  */
 423   NULL,                       /* Iterative solver.  */
 424   NULL,                       /* Confluence operator 0.  */
 425   NULL,                       /* Confluence operator n.  */
 426   NULL,                       /* Transfer function.  */
 427   NULL,                       /* Finalize function.  */
 428   df_scan_free,               /* Free all of the problem information.  */
 429   NULL,                       /* Remove this problem from the stack of dataflow problems.  */
 430   df_scan_start_dump,         /* Debugging.  */
 431   df_scan_start_block,        /* Debugging start block.  */
 432   NULL,                       /* Debugging end block.  */
 433   NULL,                       /* Incremental solution verify start.  */
 434   NULL,                       /* Incremental solution verify end.  */
 435   NULL,                       /* Dependent problem.  */
 436   TV_DF_SCAN,                 /* Timing variable.  */
 437   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
 438 };
 439
 440
 441 /* Create a new DATAFLOW instance and add it to an existing instance
 442    of DF.  The returned structure is what is used to get at the
 443    solution.  */
 444
 445 void
 446 df_scan_add_problem (void)
 447 {
 448   df_add_problem (&problem_SCAN);
 449 }
 450
 451 \f
 452 /*----------------------------------------------------------------------------
 453    Storage Allocation Utilities
 454 ----------------------------------------------------------------------------*/
 455
 456
 457 /* First, grow the reg_info information.  If the current size is less than
 458    the number of psuedos, grow to 25% more than the number of
 459    pseudos.
 460
 461    Second, assure that all of the slots up to max_reg_num have been
 462    filled with reg_info structures.  */
 463
 464 void
 465 df_grow_reg_info (void)
 466 {
 467   unsigned int max_reg = max_reg_num ();
 468   unsigned int new_size = max_reg;
 469   struct df_scan_problem_data *problem_data
 470     = (struct df_scan_problem_data *) df_scan->problem_data;
 471   unsigned int i;
 472
 473   if (df->regs_size < new_size)
 474     {
 475       new_size += new_size / 4;
 476       df->def_regs = xrealloc (df->def_regs,
 477                                new_size *sizeof (struct df_reg_info*));
 478       df->use_regs = xrealloc (df->use_regs,
 479                                new_size *sizeof (struct df_reg_info*));
 480       df->eq_use_regs = xrealloc (df->eq_use_regs,
 481                                   new_size *sizeof (struct df_reg_info*));
 482       df->def_info.begin = xrealloc (df->def_info.begin,
 483                                       new_size *sizeof (int));
 484       df->def_info.count = xrealloc (df->def_info.count,
 485                                       new_size *sizeof (int));
 486       df->use_info.begin = xrealloc (df->use_info.begin,
 487                                       new_size *sizeof (int));
 488       df->use_info.count = xrealloc (df->use_info.count,
 489                                       new_size *sizeof (int));
 490       df->regs_size = new_size;
 491     }
 492
 493   for (i = df->regs_inited; i < max_reg; i++)
 494     {
 495       struct df_reg_info *reg_info;
 496
 497       reg_info = pool_alloc (problem_data->reg_pool);
 498       memset (reg_info, 0, sizeof (struct df_reg_info));
 499       df->def_regs[i] = reg_info;
 500       reg_info = pool_alloc (problem_data->reg_pool);
 501       memset (reg_info, 0, sizeof (struct df_reg_info));
 502       df->use_regs[i] = reg_info;
 503       reg_info = pool_alloc (problem_data->reg_pool);
 504       memset (reg_info, 0, sizeof (struct df_reg_info));
 505       df->eq_use_regs[i] = reg_info;
 506       df->def_info.begin[i] = 0;
 507       df->def_info.count[i] = 0;
 508       df->use_info.begin[i] = 0;
 509       df->use_info.count[i] = 0;
 510     }
 511
 512   df->regs_inited = max_reg;
 513 }
 514
 515
 516 /* Grow the ref information.  */
 517
 518 static void
 519 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
 520 {
 521   if (ref_info->refs_size < new_size)
 522     {
 523       ref_info->refs = xrealloc (ref_info->refs,
 524                                  new_size *sizeof (struct df_ref *));
 525       memset (ref_info->refs + ref_info->refs_size, 0,
 526               (new_size - ref_info->refs_size) *sizeof (struct df_ref *));
 527       ref_info->refs_size = new_size;
 528     }
 529 }
 530
 531
 532 /* Check and grow the ref information if necessary.  This routine
 533    guarantees total_size + BITMAP_ADDEND amount of entries in refs
 534    array.  It updates ref_info->refs_size only and does not change
 535    ref_info->total_size.  */
 536
 537 static void
 538 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
 539                             unsigned bitmap_addend)
 540 {
 541   if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
 542     {
 543       int new_size = ref_info->total_size + bitmap_addend;
 544       new_size += ref_info->total_size / 4;
 545       df_grow_ref_info (ref_info, new_size);
 546     }
 547 }
 548
 549
 550 /* Grow the ref information.  If the current size is less than the
 551    number of instructions, grow to 25% more than the number of
 552    instructions.  */
 553
 554 void
 555 df_grow_insn_info (void)
 556 {
 557   unsigned int new_size = get_max_uid () + 1;
 558   if (DF_INSN_SIZE () < new_size)
 559     {
 560       new_size += new_size / 4;
 561       df->insns = xrealloc (df->insns,
 562                             new_size *sizeof (struct df_insn_info *));
 563       memset (df->insns + df->insns_size, 0,
 564               (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
 565       DF_INSN_SIZE () = new_size;
 566     }
 567 }
 568
 569
 570
 571 \f
 572 /*----------------------------------------------------------------------------
 573    PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
 574 ----------------------------------------------------------------------------*/
 575
 576 /* Rescan all of the block_to_analyze or all of the blocks in the
 577    function if df_set_blocks if blocks_to_analyze is NULL;  */
 578
 579 void
 580 df_scan_blocks (void)
 581 {
 582   basic_block bb;
 583
 584   df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
 585   df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
 586
 587   df_get_regular_block_artificial_uses (df->regular_block_artificial_uses);
 588   df_get_eh_block_artificial_uses (df->eh_block_artificial_uses);
 589
 590   bitmap_ior_into (df->eh_block_artificial_uses,
 591                    df->regular_block_artificial_uses);
 592
 593   /* ENTRY and EXIT blocks have special defs/uses.  */
 594   df_get_entry_block_def_set (df->entry_block_defs);
 595   df_record_entry_block_defs (df->entry_block_defs);
 596   df_get_exit_block_use_set (df->exit_block_uses);
 597   df_record_exit_block_uses (df->exit_block_uses);
 598   df_set_bb_dirty (BASIC_BLOCK (ENTRY_BLOCK));
 599   df_set_bb_dirty (BASIC_BLOCK (EXIT_BLOCK));
 600
 601   /* Regular blocks */
 602   FOR_EACH_BB (bb)
 603     {
 604       unsigned int bb_index = bb->index;
 605       df_bb_refs_record (bb_index, true);
 606     }
 607 }
 608
 609
 610 /* Create a new ref of type DF_REF_TYPE for register REG at address
 611    LOC within INSN of BB.  */
 612
 613 struct df_ref *
 614 df_ref_create (rtx reg, rtx *loc, rtx insn,
 615                basic_block bb,
 616                enum df_ref_type ref_type,
 617                enum df_ref_flags ref_flags)
 618 {
 619   struct df_ref *ref;
 620   struct df_reg_info **reg_info;
 621   struct df_ref_info *ref_info;
 622   struct df_ref **ref_rec;
 623   struct df_ref ***ref_rec_ptr;
 624   unsigned int count = 0;
 625   bool add_to_table;
 626
 627   df_grow_reg_info ();
 628
 629   /* You cannot hack artificial refs.  */
 630   gcc_assert (insn);
 631   ref = df_ref_create_structure (NULL, reg, loc, bb, insn,
 632                                  ref_type, ref_flags);
 633
 634   if (DF_REF_TYPE (ref) == DF_REF_REG_DEF)
 635     {
 636       reg_info = df->def_regs;
 637       ref_info = &df->def_info;
 638       ref_rec_ptr = &DF_INSN_DEFS (insn);
 639       add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
 640     }
 641   else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
 642     {
 643       reg_info = df->eq_use_regs;
 644       ref_info = &df->use_info;
 645       ref_rec_ptr = &DF_INSN_EQ_USES (insn);
 646       switch (ref_info->ref_order)
 647         {
 648         case DF_REF_ORDER_UNORDERED_WITH_NOTES:
 649         case DF_REF_ORDER_BY_REG_WITH_NOTES:
 650         case DF_REF_ORDER_BY_INSN_WITH_NOTES:
 651           add_to_table = true;
 652           break;
 653         default:
 654           add_to_table = false;
 655           break;
 656         }
 657     }
 658   else
 659     {
 660       reg_info = df->use_regs;
 661       ref_info = &df->use_info;
 662       ref_rec_ptr = &DF_INSN_USES (insn);
 663       add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
 664     }
 665
 666   /* Do not add if ref is not in the right blocks.  */
 667   if (add_to_table && df->analyze_subset)
 668     add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
 669
 670   df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
 671
 672   if (add_to_table)
 673     switch (ref_info->ref_order)
 674       {
 675       case DF_REF_ORDER_UNORDERED_WITH_NOTES:
 676       case DF_REF_ORDER_BY_REG_WITH_NOTES:
 677       case DF_REF_ORDER_BY_INSN_WITH_NOTES:
 678         ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
 679         break;
 680       default:
 681         ref_info->ref_order = DF_REF_ORDER_UNORDERED;
 682         break;
 683       }
 684
 685   ref_rec = *ref_rec_ptr;
 686   while (*ref_rec)
 687     {
 688       count++;
 689       ref_rec++;
 690     }
 691
 692   ref_rec = *ref_rec_ptr;
 693   if (count)
 694     {
 695       ref_rec = xrealloc (ref_rec, (count+2) * sizeof (struct df_ref*));
 696       *ref_rec_ptr = ref_rec;
 697       ref_rec[count] = ref;
 698       ref_rec[count+1] = NULL;
 699       qsort (ref_rec, count + 1, sizeof (struct df_ref *), df_ref_compare);
 700     }
 701   else
 702     {
 703       struct df_ref **ref_rec = XNEWVEC (struct df_ref*, 2);
 704       ref_rec[0] = ref;
 705       ref_rec[1] = NULL;
 706       *ref_rec_ptr = ref_rec;
 707     }
 708
 709 #if 0
 710   if (dump_file)
 711     {
 712       fprintf (dump_file, "adding ref ");
 713       df_ref_debug (ref, dump_file);
 714     }
 715 #endif
 716   /* By adding the ref directly, df_insn_rescan my not find any
 717      differences even though the block will have changed.  So we need
 718      to mark the block dirty ourselves.  */
 719   df_set_bb_dirty (bb);
 720
 721   return ref;
 722 }
 723
 724
 725 \f
 726 /*----------------------------------------------------------------------------
 727    UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
 728 ----------------------------------------------------------------------------*/
 729
 730
 731 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
 732    Also delete the def-use or use-def chain if it exists.  */
 733
 734 static void
 735 df_reg_chain_unlink (struct df_ref *ref)
 736 {
 737   struct df_ref *next = DF_REF_NEXT_REG (ref);
 738   struct df_ref *prev = DF_REF_PREV_REG (ref);
 739   struct df_scan_problem_data *problem_data
 740     = (struct df_scan_problem_data *) df_scan->problem_data;
 741   int id = DF_REF_ID (ref);
 742   struct df_reg_info *reg_info;
 743   struct df_ref **refs = NULL;
 744
 745   if (DF_REF_TYPE (ref) == DF_REF_REG_DEF)
 746     {
 747       reg_info = DF_REG_DEF_GET (DF_REF_REGNO (ref));
 748       refs = df->def_info.refs;
 749     }
 750   else
 751     {
 752       if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
 753         {
 754           reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
 755           switch (df->use_info.ref_order)
 756             {
 757             case DF_REF_ORDER_UNORDERED_WITH_NOTES:
 758             case DF_REF_ORDER_BY_REG_WITH_NOTES:
 759             case DF_REF_ORDER_BY_INSN_WITH_NOTES:
 760               refs = df->use_info.refs;
 761               break;
 762             default:
 763               break;
 764             }
 765         }
 766       else
 767         {
 768           reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
 769           refs = df->use_info.refs;
 770         }
 771     }
 772
 773   if (refs)
 774     {
 775       if (df->analyze_subset)
 776         {
 777           if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BB (ref)->index))
 778             refs[id] = NULL;
 779         }
 780       else
 781         refs[id] = NULL;
 782     }
 783
 784   /* Delete any def-use or use-def chains that start here. It is
 785      possible that there is trash in this field.  This happens for
 786      insns that have been deleted when rescanning has been deferred
 787      and the chain problem has also been deleted.  The chain tear down
 788      code skips deleted insns.  */
 789   if (df_chain && DF_REF_CHAIN (ref))
 790     df_chain_unlink (ref);
 791
 792   reg_info->n_refs--;
 793   if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
 794     {
 795       gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
 796       df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
 797     }
 798
 799   /* Unlink from the reg chain.  If there is no prev, this is the
 800      first of the list.  If not, just join the next and prev.  */
 801   if (prev)
 802     DF_REF_NEXT_REG (prev) = next;
 803   else
 804     {
 805       gcc_assert (reg_info->reg_chain == ref);
 806       reg_info->reg_chain = next;
 807     }
 808   if (next)
 809     DF_REF_PREV_REG (next) = prev;
 810
 811   pool_free (problem_data->ref_pool, ref);
 812 }
 813
 814
 815 /* Remove REF from VEC.  */
 816
 817 static void
 818 df_ref_compress_rec (struct df_ref ***vec_ptr, struct df_ref *ref)
 819 {
 820   struct df_ref **vec = *vec_ptr;
 821
 822   if (vec[1])
 823     {
 824       while (*vec && *vec != ref)
 825         vec++;
 826
 827       while (*vec)
 828         {
 829           *vec = *(vec+1);
 830           vec++;
 831         }
 832     }
 833   else
 834     {
 835       free (vec);
 836       *vec_ptr = df_null_ref_rec;
 837     }
 838 }
 839
 840
 841 /* Unlink REF from all def-use/use-def chains, etc.  */
 842
 843 void
 844 df_ref_remove (struct df_ref *ref)
 845 {
 846 #if 0
 847   if (dump_file)
 848     {
 849       fprintf (dump_file, "removing ref ");
 850       df_ref_debug (ref, dump_file);
 851     }
 852 #endif
 853
 854   if (DF_REF_REG_DEF_P (ref))
 855     {
 856       if (DF_REF_IS_ARTIFICIAL (ref))
 857         {
 858           struct df_scan_bb_info *bb_info
 859             = df_scan_get_bb_info (DF_REF_BB (ref)->index);
 860           df_ref_compress_rec (&bb_info->artificial_defs, ref);
 861         }
 862       else
 863         {
 864           unsigned int uid = DF_REF_INSN_UID (ref);
 865           struct df_insn_info *insn_rec = DF_INSN_UID_GET (uid);
 866           df_ref_compress_rec (&insn_rec->defs, ref);
 867         }
 868     }
 869   else
 870     {
 871       if (DF_REF_IS_ARTIFICIAL (ref))
 872         {
 873           struct df_scan_bb_info *bb_info
 874             = df_scan_get_bb_info (DF_REF_BB (ref)->index);
 875           df_ref_compress_rec (&bb_info->artificial_uses, ref);
 876         }
 877       else
 878         {
 879           unsigned int uid = DF_REF_INSN_UID (ref);
 880           struct df_insn_info *insn_rec = DF_INSN_UID_GET (uid);
 881
 882           if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
 883             df_ref_compress_rec (&insn_rec->eq_uses, ref);
 884           else
 885             df_ref_compress_rec (&insn_rec->uses, ref);
 886         }
 887     }
 888
 889   /* By deleting the ref directly, df_insn_rescan my not find any
 890      differences even though the block will have changed.  So we need
 891      to mark the block dirty ourselves.  */
 892   df_set_bb_dirty (DF_REF_BB (ref));
 893   df_reg_chain_unlink (ref);
 894 }
 895
 896
 897 /* Create the insn record for INSN.  If there was one there, zero it
 898    out.  */
 899
 900 struct df_insn_info *
 901 df_insn_create_insn_record (rtx insn)
 902 {
 903   struct df_scan_problem_data *problem_data
 904     = (struct df_scan_problem_data *) df_scan->problem_data;
 905   struct df_insn_info *insn_rec;
 906
 907   df_grow_insn_info ();
 908   insn_rec = DF_INSN_GET (insn);
 909   if (!insn_rec)
 910     {
 911       insn_rec = pool_alloc (problem_data->insn_pool);
 912       DF_INSN_SET (insn, insn_rec);
 913     }
 914   memset (insn_rec, 0, sizeof (struct df_insn_info));
 915   insn_rec->insn = insn;
 916   return insn_rec;
 917 }
 918
 919
 920 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain.  */
 921
 922 static void
 923 df_ref_chain_delete_du_chain (struct df_ref **ref_rec)
 924 {
 925   while (*ref_rec)
 926     {
 927       struct df_ref *ref = *ref_rec;
 928       /* CHAIN is allocated by DF_CHAIN. So make sure to
 929          pass df_scan instance for the problem.  */
 930       if (DF_REF_CHAIN (ref))
 931         df_chain_unlink (ref);
 932       ref_rec++;
 933     }
 934 }
 935
 936
 937 /* Delete all refs in the ref chain.  */
 938
 939 static void
 940 df_ref_chain_delete (struct df_ref **ref_rec)
 941 {
 942   struct df_ref **start = ref_rec;
 943   while (*ref_rec)
 944     {
 945       df_reg_chain_unlink (*ref_rec);
 946       ref_rec++;
 947     }
 948
 949   /* If the list is empty, it has a special shared element that is not
 950      to be deleted.  */
 951   if (*start)
 952     free (start);
 953 }
 954
 955
 956 /* Delete the hardreg chain.  */
 957
 958 static void
 959 df_mw_hardreg_chain_delete (struct df_mw_hardreg **hardregs)
 960 {
 961   struct df_scan_problem_data *problem_data;
 962
 963   if (!hardregs)
 964     return;
 965
 966   problem_data = (struct df_scan_problem_data *) df_scan->problem_data;
 967
 968   while (*hardregs)
 969     {
 970       pool_free (problem_data->mw_reg_pool, *hardregs);
 971       hardregs++;
 972     }
 973 }
 974
 975
 976 /* Delete all of the refs information from INSN.  BB must be passed in
 977    except when called from df_process_deferred_rescans to mark the block
 978    as dirty.  */
 979
 980 void
 981 df_insn_delete (basic_block bb, unsigned int uid)
 982 {
 983   struct df_insn_info *insn_info = NULL;
 984   if (!df)
 985     return;
 986
 987   df_grow_bb_info (df_scan);
 988   df_grow_reg_info ();
 989
 990   /* The block must be marked as dirty now, rather than later as in
 991      df_insn_rescan and df_notes_rescan because it may not be there at
 992      rescanning time and the mark would blow up.  */
 993   if (bb)
 994     df_set_bb_dirty (bb);
 995
 996   insn_info = DF_INSN_UID_SAFE_GET (uid);
 997
 998   /* The client has deferred rescanning.  */
 999   if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1000     {
1001       if (insn_info)
1002         {
1003           bitmap_clear_bit (df->insns_to_rescan, uid);
1004           bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1005           bitmap_set_bit (df->insns_to_delete, uid);
1006         }
1007       if (dump_file)
1008         fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
1009       return;
1010     }
1011
1012   if (dump_file)
1013     fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
1014
1015   bitmap_clear_bit (df->insns_to_delete, uid);
1016   bitmap_clear_bit (df->insns_to_rescan, uid);
1017   bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1018   if (insn_info)
1019     {
1020       struct df_scan_problem_data *problem_data
1021         = (struct df_scan_problem_data *) df_scan->problem_data;
1022
1023       /* In general, notes do not have the insn_info fields
1024          initialized.  However, combine deletes insns by changing them
1025          to notes.  How clever.  So we cannot just check if it is a
1026          valid insn before short circuiting this code, we need to see
1027          if we actually initialized it.  */
1028       if (insn_info->defs)
1029         {
1030           df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1031
1032           if (df_chain)
1033             {
1034               df_ref_chain_delete_du_chain (insn_info->defs);
1035               df_ref_chain_delete_du_chain (insn_info->uses);
1036               df_ref_chain_delete_du_chain (insn_info->eq_uses);
1037             }
1038
1039           df_ref_chain_delete (insn_info->defs);
1040           df_ref_chain_delete (insn_info->uses);
1041           df_ref_chain_delete (insn_info->eq_uses);
1042         }
1043       pool_free (problem_data->insn_pool, insn_info);
1044       DF_INSN_UID_SET (uid, NULL);
1045     }
1046 }
1047
1048
1049 /* Free all of the refs and the mw_hardregs in COLLECTION_REC.  */
1050
1051 static void
1052 df_free_collection_rec (struct df_collection_rec *collection_rec)
1053 {
1054   struct df_scan_problem_data *problem_data
1055     = (struct df_scan_problem_data *) df_scan->problem_data;
1056   struct df_ref **ref;
1057   struct df_mw_hardreg **mw;
1058
1059   if (collection_rec->def_vec)
1060     for (ref = collection_rec->def_vec; *ref; ref++)
1061       pool_free (problem_data->ref_pool, *ref);
1062   if (collection_rec->use_vec)
1063     for (ref = collection_rec->use_vec; *ref; ref++)
1064       pool_free (problem_data->ref_pool, *ref);
1065   if (collection_rec->eq_use_vec)
1066     for (ref = collection_rec->eq_use_vec; *ref; ref++)
1067       pool_free (problem_data->ref_pool, *ref);
1068   if (collection_rec->mw_vec)
1069     for (mw = collection_rec->mw_vec; *mw; mw++)
1070       pool_free (problem_data->mw_reg_pool, *mw);
1071 }
1072
1073
1074 /* Rescan INSN.  Return TRUE if the rescanning produced any changes.  */
1075
1076 bool
1077 df_insn_rescan (rtx insn)
1078 {
1079   unsigned int uid = INSN_UID (insn);
1080   struct df_insn_info *insn_info = NULL;
1081   basic_block bb = BLOCK_FOR_INSN (insn);
1082   struct df_collection_rec collection_rec;
1083   collection_rec.def_vec = alloca (sizeof (struct df_ref*) * 1000);
1084   collection_rec.use_vec = alloca (sizeof (struct df_ref*) * 1000);
1085   collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
1086   collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 100);
1087
1088   if ((!df) || (!INSN_P (insn)))
1089     return false;
1090
1091   if (!bb)
1092     {
1093       if (dump_file)
1094         fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1095       return false;
1096     }
1097
1098   /* The client has disabled rescanning and plans to do it itself.  */
1099   if (df->changeable_flags & DF_NO_INSN_RESCAN)
1100     return false;
1101
1102   df_grow_bb_info (df_scan);
1103   df_grow_reg_info ();
1104
1105   insn_info = DF_INSN_UID_SAFE_GET (uid);
1106
1107   /* The client has deferred rescanning.  */
1108   if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1109     {
1110       if (!insn_info)
1111         {
1112           insn_info = df_insn_create_insn_record (insn);
1113           insn_info->defs = df_null_ref_rec;
1114           insn_info->uses = df_null_ref_rec;
1115           insn_info->eq_uses = df_null_ref_rec;
1116           insn_info->mw_hardregs = df_null_mw_rec;
1117         }
1118       if (dump_file)
1119         fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1120
1121       bitmap_clear_bit (df->insns_to_delete, uid);
1122       bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1123       bitmap_set_bit (df->insns_to_rescan, INSN_UID (insn));
1124       return false;
1125     }
1126
1127   bitmap_clear_bit (df->insns_to_delete, uid);
1128   bitmap_clear_bit (df->insns_to_rescan, uid);
1129   bitmap_clear_bit (df->insns_to_notes_rescan, uid);
1130   if (insn_info)
1131     {
1132       bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1133       /* If there's no change, return false. */
1134       if (the_same)
1135         {
1136           df_free_collection_rec (&collection_rec);
1137           if (dump_file)
1138             fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1139           return false;
1140         }
1141       if (dump_file)
1142         fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1143
1144       /* There's change - we need to delete the existing info. */
1145       df_insn_delete (NULL, uid);
1146       df_insn_create_insn_record (insn);
1147     }
1148   else
1149     {
1150       df_insn_create_insn_record (insn);
1151       df_insn_refs_collect (&collection_rec, bb, insn);
1152       if (dump_file)
1153         fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1154     }
1155
1156   df_refs_add_to_chains (&collection_rec, bb, insn);
1157   df_set_bb_dirty (bb);
1158   return true;
1159 }
1160
1161
1162 /* Rescan all of the insns in the function.  Note that the artificial
1163    uses and defs are not touched.  This function will destroy def-se
1164    or use-def chains.  */
1165
1166 void
1167 df_insn_rescan_all (void)
1168 {
1169   bool no_insn_rescan = false;
1170   bool defer_insn_rescan = false;
1171   basic_block bb;
1172   bitmap_iterator bi;
1173   unsigned int uid;
1174   bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
1175
1176   if (df->changeable_flags & DF_NO_INSN_RESCAN)
1177     {
1178       df_clear_flags (DF_NO_INSN_RESCAN);
1179       no_insn_rescan = true;
1180     }
1181
1182   if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1183     {
1184       df_clear_flags (DF_DEFER_INSN_RESCAN);
1185       defer_insn_rescan = true;
1186     }
1187
1188   bitmap_copy (tmp, df->insns_to_delete);
1189   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1190     {
1191       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1192       if (insn_info)
1193         df_insn_delete (NULL, uid);
1194     }
1195
1196   BITMAP_FREE (tmp);
1197   bitmap_clear (df->insns_to_delete);
1198   bitmap_clear (df->insns_to_rescan);
1199   bitmap_clear (df->insns_to_notes_rescan);
1200
1201   FOR_EACH_BB (bb)
1202     {
1203       rtx insn;
1204       FOR_BB_INSNS (bb, insn)
1205         {
1206           df_insn_rescan (insn);
1207         }
1208     }
1209
1210   if (no_insn_rescan)
1211     df_set_flags (DF_NO_INSN_RESCAN);
1212   if (defer_insn_rescan)
1213     df_set_flags (DF_DEFER_INSN_RESCAN);
1214 }
1215
1216
1217 /* Process all of the deferred rescans or deletions.  */
1218
1219 void
1220 df_process_deferred_rescans (void)
1221 {
1222   bool no_insn_rescan = false;
1223   bool defer_insn_rescan = false;
1224   bitmap_iterator bi;
1225   unsigned int uid;
1226   bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
1227
1228   if (df->changeable_flags & DF_NO_INSN_RESCAN)
1229     {
1230       df_clear_flags (DF_NO_INSN_RESCAN);
1231       no_insn_rescan = true;
1232     }
1233
1234   if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1235     {
1236       df_clear_flags (DF_DEFER_INSN_RESCAN);
1237       defer_insn_rescan = true;
1238     }
1239
1240   if (dump_file)
1241     fprintf (dump_file, "starting the processing of deferred insns\n");
1242
1243   bitmap_copy (tmp, df->insns_to_delete);
1244   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1245     {
1246       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1247       if (insn_info)
1248         df_insn_delete (NULL, uid);
1249     }
1250
1251   bitmap_copy (tmp, df->insns_to_rescan);
1252   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1253     {
1254       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1255       if (insn_info)
1256         df_insn_rescan (insn_info->insn);
1257     }
1258
1259   bitmap_copy (tmp, df->insns_to_notes_rescan);
1260   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1261     {
1262       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1263       if (insn_info)
1264         df_notes_rescan (insn_info->insn);
1265     }
1266
1267   if (dump_file)
1268     fprintf (dump_file, "ending the processing of deferred insns\n");
1269
1270   BITMAP_FREE (tmp);
1271   bitmap_clear (df->insns_to_delete);
1272   bitmap_clear (df->insns_to_rescan);
1273   bitmap_clear (df->insns_to_notes_rescan);
1274
1275   if (no_insn_rescan)
1276     df_set_flags (DF_NO_INSN_RESCAN);
1277   if (defer_insn_rescan)
1278     df_set_flags (DF_DEFER_INSN_RESCAN);
1279
1280   /* If someone changed regs_ever_live during this pass, fix up the
1281      entry and exit blocks.  */
1282   if (df->redo_entry_and_exit)
1283     {
1284       df_update_entry_exit_and_calls ();
1285       df->redo_entry_and_exit = false;
1286     }
1287 }
1288
1289
1290 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1291    the uses if INCLUDE_USES. Include the eq_uses if
1292    INCLUDE_EQ_USES.  */
1293
1294 static unsigned int
1295 df_count_refs (bool include_defs, bool include_uses,
1296                bool include_eq_uses)
1297 {
1298   unsigned int regno;
1299   int size = 0;
1300   unsigned int m = df->regs_inited;
1301
1302   for (regno = 0; regno < m; regno++)
1303     {
1304       if (include_defs)
1305         size += DF_REG_DEF_COUNT (regno);
1306       if (include_uses)
1307         size += DF_REG_USE_COUNT (regno);
1308       if (include_eq_uses)
1309         size += DF_REG_EQ_USE_COUNT (regno);
1310     }
1311   return size;
1312 }
1313
1314
1315 /* Take build ref table for either the uses or defs from the reg-use
1316    or reg-def chains.  This version processes the refs in reg order
1317    which is likely to be best if processing the whole function.  */
1318
1319 static void
1320 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1321                                   bool include_defs,
1322                                   bool include_uses,
1323                                   bool include_eq_uses)
1324 {
1325   unsigned int m = df->regs_inited;
1326   unsigned int regno;
1327   unsigned int offset = 0;
1328   unsigned int start;
1329
1330   if (df->changeable_flags & DF_NO_HARD_REGS)
1331     {
1332       start = FIRST_PSEUDO_REGISTER;
1333       memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1334       memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1335     }
1336   else
1337     start = 0;
1338
1339   ref_info->total_size
1340     = df_count_refs (include_defs, include_uses, include_eq_uses);
1341
1342   df_check_and_grow_ref_info (ref_info, 1);
1343
1344   for (regno = start; regno < m; regno++)
1345     {
1346       int count = 0;
1347       ref_info->begin[regno] = offset;
1348       if (include_defs)
1349         {
1350           struct df_ref *ref = DF_REG_DEF_CHAIN (regno);
1351           while (ref)
1352             {
1353               ref_info->refs[offset] = ref;
1354               DF_REF_ID (ref) = offset++;
1355               count++;
1356               ref = DF_REF_NEXT_REG (ref);
1357               gcc_assert (offset < ref_info->refs_size);
1358             }
1359         }
1360       if (include_uses)
1361         {
1362           struct df_ref *ref = DF_REG_USE_CHAIN (regno);
1363           while (ref)
1364             {
1365               ref_info->refs[offset] = ref;
1366               DF_REF_ID (ref) = offset++;
1367               count++;
1368               ref = DF_REF_NEXT_REG (ref);
1369               gcc_assert (offset < ref_info->refs_size);
1370             }
1371         }
1372       if (include_eq_uses)
1373         {
1374           struct df_ref *ref = DF_REG_EQ_USE_CHAIN (regno);
1375           while (ref)
1376             {
1377               ref_info->refs[offset] = ref;
1378               DF_REF_ID (ref) = offset++;
1379               count++;
1380               ref = DF_REF_NEXT_REG (ref);
1381               gcc_assert (offset < ref_info->refs_size);
1382             }
1383         }
1384       ref_info->count[regno] = count;
1385     }
1386
1387   /* The bitmap size is not decremented when refs are deleted.  So
1388      reset it now that we have squished out all of the empty
1389      slots.  */
1390   ref_info->table_size = offset;
1391 }
1392
1393
1394 /* Take build ref table for either the uses or defs from the reg-use
1395    or reg-def chains.  This version processes the refs in insn order
1396    which is likely to be best if processing some segment of the
1397    function.  */
1398
1399 static void
1400 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1401                                    bool include_defs,
1402                                    bool include_uses,
1403                                    bool include_eq_uses)
1404 {
1405   bitmap_iterator bi;
1406   unsigned int bb_index;
1407   unsigned int m = df->regs_inited;
1408   unsigned int offset = 0;
1409   unsigned int r;
1410   unsigned int start
1411     = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1412
1413   memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1414   memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1415
1416   ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1417   df_check_and_grow_ref_info (ref_info, 1);
1418
1419   EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1420     {
1421       basic_block bb = BASIC_BLOCK (bb_index);
1422       rtx insn;
1423       struct df_ref **ref_rec;
1424
1425       if (include_defs)
1426         for (ref_rec = df_get_artificial_defs (bb_index); *ref_rec; ref_rec++)
1427           {
1428             unsigned int regno = DF_REF_REGNO (*ref_rec);
1429             ref_info->count[regno]++;
1430           }
1431       if (include_uses)
1432         for (ref_rec = df_get_artificial_uses (bb_index); *ref_rec; ref_rec++)
1433           {
1434             unsigned int regno = DF_REF_REGNO (*ref_rec);
1435             ref_info->count[regno]++;
1436           }
1437
1438       FOR_BB_INSNS (bb, insn)
1439         {
1440           if (INSN_P (insn))
1441             {
1442               unsigned int uid = INSN_UID (insn);
1443
1444               if (include_defs)
1445                 for (ref_rec = DF_INSN_UID_DEFS (uid); *ref_rec; ref_rec++)
1446                   {
1447                     unsigned int regno = DF_REF_REGNO (*ref_rec);
1448                     ref_info->count[regno]++;
1449                   }
1450               if (include_uses)
1451                 for (ref_rec = DF_INSN_UID_USES (uid); *ref_rec; ref_rec++)
1452                   {
1453                     unsigned int regno = DF_REF_REGNO (*ref_rec);
1454                     ref_info->count[regno]++;
1455                   }
1456               if (include_eq_uses)
1457                 for (ref_rec = DF_INSN_UID_EQ_USES (uid); *ref_rec; ref_rec++)
1458                   {
1459                     unsigned int regno = DF_REF_REGNO (*ref_rec);
1460                     ref_info->count[regno]++;
1461                   }
1462             }
1463         }
1464     }
1465
1466   for (r = start; r < m; r++)
1467     {
1468       ref_info->begin[r] = offset;
1469       offset += ref_info->count[r];
1470       ref_info->count[r] = 0;
1471     }
1472
1473   EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1474     {
1475       basic_block bb = BASIC_BLOCK (bb_index);
1476       rtx insn;
1477       struct df_ref **ref_rec;
1478
1479       if (include_defs)
1480         for (ref_rec = df_get_artificial_defs (bb_index); *ref_rec; ref_rec++)
1481           {
1482             struct df_ref *ref = *ref_rec;
1483             unsigned int regno = DF_REF_REGNO (ref);
1484             if (regno >= start)
1485               {
1486                 unsigned int id
1487                   = ref_info->begin[regno] + ref_info->count[regno]++;
1488                 DF_REF_ID (ref) = id;
1489                 ref_info->refs[id] = ref;
1490               }
1491           }
1492       if (include_uses)
1493         for (ref_rec = df_get_artificial_uses (bb_index); *ref_rec; ref_rec++)
1494           {
1495             struct df_ref *ref = *ref_rec;
1496             unsigned int regno = DF_REF_REGNO (ref);
1497             if (regno >= start)
1498               {
1499                 unsigned int id
1500                   = ref_info->begin[regno] + ref_info->count[regno]++;
1501                 DF_REF_ID (ref) = id;
1502                 ref_info->refs[id] = ref;
1503               }
1504           }
1505
1506       FOR_BB_INSNS (bb, insn)
1507         {
1508           if (INSN_P (insn))
1509             {
1510               unsigned int uid = INSN_UID (insn);
1511
1512               if (include_defs)
1513                 for (ref_rec = DF_INSN_UID_DEFS (uid); *ref_rec; ref_rec++)
1514                   {
1515                     struct df_ref *ref = *ref_rec;
1516                     unsigned int regno = DF_REF_REGNO (ref);
1517                     if (regno >= start)
1518                       {
1519                         unsigned int id
1520                           = ref_info->begin[regno] + ref_info->count[regno]++;
1521                         DF_REF_ID (ref) = id;
1522                         ref_info->refs[id] = ref;
1523                       }
1524                   }
1525               if (include_uses)
1526                 for (ref_rec = DF_INSN_UID_USES (uid); *ref_rec; ref_rec++)
1527                   {
1528                     struct df_ref *ref = *ref_rec;
1529                     unsigned int regno = DF_REF_REGNO (ref);
1530                     if (regno >= start)
1531                       {
1532                         unsigned int id
1533                           = ref_info->begin[regno] + ref_info->count[regno]++;
1534                         DF_REF_ID (ref) = id;
1535                         ref_info->refs[id] = ref;
1536                       }
1537                   }
1538               if (include_eq_uses)
1539                 for (ref_rec = DF_INSN_UID_EQ_USES (uid); *ref_rec; ref_rec++)
1540                   {
1541                     struct df_ref *ref = *ref_rec;
1542                     unsigned int regno = DF_REF_REGNO (ref);
1543                     if (regno >= start)
1544                       {
1545                         unsigned int id
1546                           = ref_info->begin[regno] + ref_info->count[regno]++;
1547                         DF_REF_ID (ref) = id;
1548                         ref_info->refs[id] = ref;
1549                       }
1550                   }
1551             }
1552         }
1553     }
1554
1555   /* The bitmap size is not decremented when refs are deleted.  So
1556      reset it now that we have squished out all of the empty
1557      slots.  */
1558
1559   ref_info->table_size = offset;
1560 }
1561
1562 /* Take build ref table for either the uses or defs from the reg-use
1563    or reg-def chains.  */
1564
1565 static void
1566 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1567                            bool include_defs,
1568                            bool include_uses,
1569                            bool include_eq_uses)
1570 {
1571   if (df->analyze_subset)
1572     df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1573                                        include_uses, include_eq_uses);
1574   else
1575     df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1576                                        include_uses, include_eq_uses);
1577 }
1578
1579
1580 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET.  */
1581 static unsigned int
1582 df_add_refs_to_table (unsigned int offset,
1583                       struct df_ref_info *ref_info,
1584                       struct df_ref **ref_vec)
1585 {
1586   while (*ref_vec)
1587     {
1588       struct df_ref *ref = *ref_vec;
1589       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
1590           || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1591         {
1592           ref_info->refs[offset] = ref;
1593           DF_REF_ID (*ref_vec) = offset++;
1594         }
1595       ref_vec++;
1596     }
1597   return offset;
1598 }
1599
1600
1601 /* Count the number of refs in all of the insns of BB. Include the
1602    defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1603    eq_uses if INCLUDE_EQ_USES.  */
1604
1605 static unsigned int
1606 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1607                                struct df_ref_info *ref_info,
1608                                bool include_defs, bool include_uses,
1609                                bool include_eq_uses)
1610 {
1611   rtx insn;
1612
1613   if (include_defs)
1614     offset = df_add_refs_to_table (offset, ref_info,
1615                                    df_get_artificial_defs (bb->index));
1616   if (include_uses)
1617     offset = df_add_refs_to_table (offset, ref_info,
1618                                    df_get_artificial_uses (bb->index));
1619
1620   FOR_BB_INSNS (bb, insn)
1621     if (INSN_P (insn))
1622       {
1623         unsigned int uid = INSN_UID (insn);
1624         if (include_defs)
1625           offset = df_add_refs_to_table (offset, ref_info,
1626                                          DF_INSN_UID_DEFS (uid));
1627         if (include_uses)
1628           offset = df_add_refs_to_table (offset, ref_info,
1629                                          DF_INSN_UID_USES (uid));
1630         if (include_eq_uses)
1631           offset = df_add_refs_to_table (offset, ref_info,
1632                                          DF_INSN_UID_EQ_USES (uid));
1633       }
1634   return offset;
1635 }
1636
1637
1638 /* Organize the refs by insn into the table in REF_INFO.  If
1639    blocks_to_analyze is defined, use that set, otherwise the entire
1640    program.  Include the defs if INCLUDE_DEFS. Include the uses if
1641    INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES.  */
1642
1643 static void
1644 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1645                             bool include_defs, bool include_uses,
1646                             bool include_eq_uses)
1647 {
1648   basic_block bb;
1649   unsigned int offset = 0;
1650
1651   ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1652   df_check_and_grow_ref_info (ref_info, 1);
1653   if (df->blocks_to_analyze)
1654     {
1655       bitmap_iterator bi;
1656       unsigned int index;
1657
1658       EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1659         {
1660           offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK (index), offset, ref_info,
1661                                                   include_defs, include_uses,
1662                                                   include_eq_uses);
1663         }
1664
1665       ref_info->table_size = offset;
1666     }
1667   else
1668     {
1669       FOR_ALL_BB (bb)
1670         offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1671                                                 include_defs, include_uses,
1672                                                 include_eq_uses);
1673       ref_info->table_size = offset;
1674     }
1675 }
1676
1677
1678 /* If the use refs in DF are not organized, reorganize them.  */
1679
1680 void
1681 df_maybe_reorganize_use_refs (enum df_ref_order order)
1682 {
1683   if (order == df->use_info.ref_order)
1684     return;
1685
1686   switch (order)
1687     {
1688     case DF_REF_ORDER_BY_REG:
1689       df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1690       break;
1691
1692     case DF_REF_ORDER_BY_REG_WITH_NOTES:
1693       df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1694       break;
1695
1696     case DF_REF_ORDER_BY_INSN:
1697       df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1698       break;
1699
1700     case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1701       df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1702       break;
1703
1704     case DF_REF_ORDER_NO_TABLE:
1705       free (df->use_info.refs);
1706       df->use_info.refs = NULL;
1707       df->use_info.refs_size = 0;
1708       break;
1709
1710     case DF_REF_ORDER_UNORDERED:
1711     case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1712       gcc_unreachable ();
1713       break;
1714     }
1715
1716   df->use_info.ref_order = order;
1717 }
1718
1719
1720 /* If the def refs in DF are not organized, reorganize them.  */
1721
1722 void
1723 df_maybe_reorganize_def_refs (enum df_ref_order order)
1724 {
1725   if (order == df->def_info.ref_order)
1726     return;
1727
1728   switch (order)
1729     {
1730     case DF_REF_ORDER_BY_REG:
1731       df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1732       break;
1733
1734     case DF_REF_ORDER_BY_INSN:
1735       df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1736       break;
1737
1738     case DF_REF_ORDER_NO_TABLE:
1739       free (df->def_info.refs);
1740       df->def_info.refs = NULL;
1741       df->def_info.refs_size = 0;
1742       break;
1743
1744     case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1745     case DF_REF_ORDER_BY_REG_WITH_NOTES:
1746     case DF_REF_ORDER_UNORDERED:
1747     case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1748       gcc_unreachable ();
1749       break;
1750     }
1751
1752   df->def_info.ref_order = order;
1753 }
1754
1755
1756 /* Change the BB of all refs in the ref chain from OLD_BB to NEW_BB.
1757    Assumes that all refs in the chain have the same BB.  */
1758
1759 static void
1760 df_ref_chain_change_bb (struct df_ref **ref_rec,
1761                         basic_block old_bb,
1762                         basic_block new_bb)
1763 {
1764   while (*ref_rec)
1765     {
1766       struct df_ref *ref = *ref_rec;
1767
1768       gcc_assert (DF_REF_BB (ref) == old_bb);
1769       DF_REF_BB (ref) = new_bb;
1770       ref_rec++;
1771     }
1772 }
1773
1774
1775 /* Change all of the basic block references in INSN to use the insn's
1776    current basic block.  This function is called from routines that move
1777    instructions from one block to another.  */
1778
1779 void
1780 df_insn_change_bb (rtx insn, basic_block new_bb)
1781 {
1782   basic_block old_bb = BLOCK_FOR_INSN (insn);
1783   struct df_insn_info *insn_info;
1784   unsigned int uid = INSN_UID (insn);
1785
1786   if (old_bb == new_bb)
1787     return;
1788
1789   set_block_for_insn (insn, new_bb);
1790
1791   if (!df)
1792     return;
1793
1794   if (dump_file)
1795     fprintf (dump_file, "changing bb of uid %d\n", uid);
1796
1797   insn_info = DF_INSN_UID_SAFE_GET (uid);
1798   if (insn_info == NULL)
1799     {
1800       if (dump_file)
1801         fprintf (dump_file, "  unscanned insn\n");
1802       df_insn_rescan (insn);
1803       return;
1804     }
1805
1806   if (!INSN_P (insn))
1807     return;
1808
1809   df_ref_chain_change_bb (insn_info->defs, old_bb, new_bb);
1810   df_ref_chain_change_bb (insn_info->uses, old_bb, new_bb);
1811   df_ref_chain_change_bb (insn_info->eq_uses, old_bb, new_bb);
1812
1813   df_set_bb_dirty (new_bb);
1814   if (old_bb)
1815     {
1816       if (dump_file)
1817         fprintf (dump_file, "  from %d to %d\n",
1818                  old_bb->index, new_bb->index);
1819       df_set_bb_dirty (old_bb);
1820     }
1821   else
1822     if (dump_file)
1823       fprintf (dump_file, "  to %d\n", new_bb->index);
1824 }
1825
1826
1827 /* Helper function for df_ref_change_reg_with_loc.  */
1828
1829 static void
1830 df_ref_change_reg_with_loc_1 (struct df_reg_info *old, struct df_reg_info *new,
1831                               int new_regno, rtx loc)
1832 {
1833   struct df_ref *the_ref = old->reg_chain;
1834
1835   while (the_ref)
1836     {
1837       if (DF_REF_LOC(the_ref) && (*DF_REF_LOC(the_ref) == loc))
1838         {
1839           struct df_ref *next_ref = the_ref->next_reg;
1840           struct df_ref *prev_ref = the_ref->prev_reg;
1841           struct df_ref **ref_vec, **ref_vec_t;
1842           unsigned int count = 0;
1843
1844           DF_REF_REGNO (the_ref) = new_regno;
1845           DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1846
1847           /* Pull the_ref out of the old regno chain.  */
1848           if (prev_ref)
1849             prev_ref->next_reg = next_ref;
1850           else
1851             old->reg_chain = next_ref;
1852           if (next_ref)
1853             next_ref->prev_reg = prev_ref;
1854           old->n_refs--;
1855
1856           /* Put the ref into the new regno chain.  */
1857           the_ref->prev_reg = NULL;
1858           the_ref->next_reg = new->reg_chain;
1859           if (new->reg_chain)
1860             new->reg_chain->prev_reg = the_ref;
1861           new->reg_chain = the_ref;
1862           new->n_refs++;
1863           df_set_bb_dirty (DF_REF_BB (the_ref));
1864
1865           /* Need to resort the record that the ref was in because the
1866              regno is a sorting key.  First, find the right record.  */
1867           if (DF_REF_IS_ARTIFICIAL (the_ref))
1868             {
1869               unsigned int bb_index = DF_REF_BB (the_ref)->index;
1870               if (DF_REF_REG_DEF_P (the_ref))
1871                 ref_vec = df_get_artificial_defs (bb_index);
1872               else
1873                 ref_vec = df_get_artificial_uses (bb_index);
1874             }
1875           else
1876             {
1877               struct df_insn_info *insn_info
1878                 = DF_INSN_GET (DF_REF_INSN (the_ref));
1879               if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1880                 ref_vec = insn_info->eq_uses;
1881               else
1882                 ref_vec = insn_info->uses;
1883               if (dump_file)
1884                 fprintf (dump_file, "changing reg in insn %d\n",
1885                          INSN_UID (DF_REF_INSN (the_ref)));
1886             }
1887           ref_vec_t = ref_vec;
1888
1889           /* Find the length.  */
1890           while (*ref_vec_t)
1891             {
1892               count++;
1893               ref_vec_t++;
1894             }
1895           qsort (ref_vec, count, sizeof (struct df_ref *), df_ref_compare);
1896
1897           the_ref = next_ref;
1898         }
1899       else
1900         the_ref = the_ref->next_reg;
1901     }
1902 }
1903
1904
1905 /* Change the regno of all refs that contained LOC from OLD_REGNO to
1906    NEW_REGNO.  Refs that do not match LOC are not changed.  This call
1907    is to support the SET_REGNO macro. */
1908
1909 void
1910 df_ref_change_reg_with_loc (int old_regno, int new_regno, rtx loc)
1911 {
1912   if ((!df) || (old_regno == -1) || (old_regno == new_regno))
1913     return;
1914
1915   df_grow_reg_info ();
1916
1917   df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
1918                                 DF_REG_DEF_GET (new_regno), new_regno, loc);
1919   df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
1920                                 DF_REG_USE_GET (new_regno), new_regno, loc);
1921   df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
1922                                 DF_REG_EQ_USE_GET (new_regno), new_regno, loc);
1923 }
1924
1925
1926 /* Delete the mw_hardregs that point into the eq_notes.  */
1927
1928 static unsigned int
1929 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
1930 {
1931   struct df_mw_hardreg **mw_vec = insn_info->mw_hardregs;
1932   unsigned int deleted = 0;
1933   unsigned int count = 0;
1934   struct df_scan_problem_data *problem_data
1935     = (struct df_scan_problem_data *) df_scan->problem_data;
1936
1937   if (!*mw_vec)
1938     return 0;
1939
1940   while (*mw_vec)
1941     {
1942       if ((*mw_vec)->flags & DF_REF_IN_NOTE)
1943         {
1944           struct df_mw_hardreg **temp_vec = mw_vec;
1945
1946           pool_free (problem_data->mw_reg_pool, *mw_vec);
1947           temp_vec = mw_vec;
1948           /* Shove the remaining ones down one to fill the gap.  While
1949              this looks n**2, it is highly unusual to have any mw regs
1950              in eq_notes and the chances of more than one are almost
1951              non existent.  */
1952           while (*temp_vec)
1953             {
1954               *temp_vec = *(temp_vec + 1);
1955               temp_vec++;
1956             }
1957           deleted++;
1958         }
1959       else
1960         {
1961           mw_vec++;
1962           count++;
1963         }
1964     }
1965
1966   if (count == 0)
1967     {
1968       free (insn_info->mw_hardregs);
1969       insn_info->mw_hardregs = df_null_mw_rec;
1970       return 0;
1971     }
1972   return deleted;
1973 }
1974
1975
1976 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN.  */
1977
1978 void
1979 df_notes_rescan (rtx insn)
1980 {
1981   struct df_insn_info *insn_info;
1982   unsigned int uid = INSN_UID (insn);
1983
1984   if (!df)
1985     return;
1986
1987   /* The client has disabled rescanning and plans to do it itself.  */
1988   if (df->changeable_flags & DF_NO_INSN_RESCAN)
1989     return;
1990
1991   /* Do nothing if the insn hasn't been emitted yet.  */
1992   if (!BLOCK_FOR_INSN (insn))
1993     return;
1994
1995   df_grow_bb_info (df_scan);
1996   df_grow_reg_info ();
1997
1998   insn_info = DF_INSN_UID_SAFE_GET (INSN_UID(insn));
1999
2000   /* The client has deferred rescanning.  */
2001   if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
2002     {
2003       if (!insn_info)
2004         {
2005           insn_info = df_insn_create_insn_record (insn);
2006           insn_info->defs = df_null_ref_rec;
2007           insn_info->uses = df_null_ref_rec;
2008           insn_info->eq_uses = df_null_ref_rec;
2009           insn_info->mw_hardregs = df_null_mw_rec;
2010         }
2011
2012       bitmap_clear_bit (df->insns_to_delete, uid);
2013       /* If the insn is set to be rescanned, it does not need to also
2014          be notes rescanned.  */
2015       if (!bitmap_bit_p (df->insns_to_rescan, uid))
2016         bitmap_set_bit (df->insns_to_notes_rescan, INSN_UID (insn));
2017       return;
2018     }
2019
2020   bitmap_clear_bit (df->insns_to_delete, uid);
2021   bitmap_clear_bit (df->insns_to_notes_rescan, uid);
2022
2023   if (insn_info)
2024     {
2025       basic_block bb = BLOCK_FOR_INSN (insn);
2026       rtx note;
2027       struct df_collection_rec collection_rec;
2028       unsigned int num_deleted;
2029
2030       memset (&collection_rec, 0, sizeof (struct df_collection_rec));
2031       collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
2032       collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 1000);
2033
2034       num_deleted = df_mw_hardreg_chain_delete_eq_uses (insn_info);
2035       df_ref_chain_delete (insn_info->eq_uses);
2036       insn_info->eq_uses = NULL;
2037
2038       /* Process REG_EQUIV/REG_EQUAL notes */
2039       for (note = REG_NOTES (insn); note;
2040            note = XEXP (note, 1))
2041         {
2042           switch (REG_NOTE_KIND (note))
2043             {
2044             case REG_EQUIV:
2045             case REG_EQUAL:
2046               df_uses_record (&collection_rec,
2047                               &XEXP (note, 0), DF_REF_REG_USE,
2048                               bb, insn, DF_REF_IN_NOTE);
2049             default:
2050               break;
2051             }
2052         }
2053
2054       /* Find some place to put any new mw_hardregs.  */
2055       df_canonize_collection_rec (&collection_rec);
2056       if (collection_rec.next_mw)
2057         {
2058           unsigned int count = 0;
2059           struct df_mw_hardreg **mw_rec = insn_info->mw_hardregs;
2060           while (*mw_rec)
2061             {
2062               count++;
2063               mw_rec++;
2064             }
2065
2066           if (count)
2067             {
2068               /* Append to the end of the existing record after
2069                  expanding it if necessary.  */
2070               if (collection_rec.next_mw > num_deleted)
2071                 {
2072                   insn_info->mw_hardregs =
2073                     xrealloc (insn_info->mw_hardregs,
2074                               (count + 1 + collection_rec.next_mw)
2075                               * sizeof (struct df_ref*));
2076                 }
2077               memcpy (&insn_info->mw_hardregs[count], collection_rec.mw_vec,
2078                       (collection_rec.next_mw + 1) * sizeof (struct df_mw_hardreg *));
2079               qsort (insn_info->mw_hardregs, count + collection_rec.next_mw,
2080                      sizeof (struct df_mw_hardreg *), df_mw_compare);
2081             }
2082           else
2083             {
2084               /* No vector there. */
2085               insn_info->mw_hardregs
2086                 = XNEWVEC (struct df_mw_hardreg*,
2087                            count + 1 + collection_rec.next_mw);
2088               memcpy (insn_info->mw_hardregs, collection_rec.mw_vec,
2089                       (collection_rec.next_mw + 1) * sizeof (struct df_mw_hardreg *));
2090             }
2091         }
2092       /* Get rid of the mw_rec so that df_refs_add_to_chains will
2093          ignore it.  */
2094       collection_rec.mw_vec = NULL;
2095       collection_rec.next_mw = 0;
2096       df_refs_add_to_chains (&collection_rec, bb, insn);
2097     }
2098   else
2099     df_insn_rescan (insn);
2100
2101 }
2102
2103 \f
2104 /*----------------------------------------------------------------------------
2105    Hard core instruction scanning code.  No external interfaces here,
2106    just a lot of routines that look inside insns.
2107 ----------------------------------------------------------------------------*/
2108
2109
2110 /* Return true if the contents of two df_ref's are identical.
2111    It ignores DF_REF_MARKER.  */
2112
2113 static bool
2114 df_ref_equal_p (struct df_ref *ref1, struct df_ref *ref2)
2115 {
2116   if (!ref2)
2117     return false;
2118   return (ref1 == ref2) ||
2119     (DF_REF_REG (ref1) == DF_REF_REG (ref2)
2120      && DF_REF_REGNO (ref1) == DF_REF_REGNO (ref2)
2121      && DF_REF_LOC (ref1) == DF_REF_LOC (ref2)
2122      && DF_REF_INSN (ref1) == DF_REF_INSN (ref2)
2123      && DF_REF_TYPE (ref1) == DF_REF_TYPE (ref2)
2124      && ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2125          == (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2126      && DF_REF_BB (ref1) == DF_REF_BB (ref2));
2127 }
2128
2129
2130 /* Compare REF1 and REF2 for sorting.  This is only called from places
2131    where all of the refs are of the same type, in the same insn, and
2132    have the same bb.  So these fields are not checked.  */
2133
2134 static int
2135 df_ref_compare (const void *r1, const void *r2)
2136 {
2137   const struct df_ref *const ref1 = *(const struct df_ref *const*)r1;
2138   const struct df_ref *const ref2 = *(const struct df_ref *const*)r2;
2139
2140   if (ref1 == ref2)
2141     return 0;
2142
2143   if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2144     return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2145
2146   if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2147     return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2148
2149   if ((DF_REF_REG (ref1) != DF_REF_REG (ref2))
2150       || (DF_REF_LOC (ref1) != DF_REF_LOC (ref2)))
2151     return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2152
2153   if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2154     {
2155       /* If two refs are identical except that one of them has is from
2156          a mw and one is not, we need to have the one with the mw
2157          first.  */
2158       if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2159           DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2160         return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2161       else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2162         return -1;
2163       else
2164         return 1;
2165     }
2166   return 0;
2167 }
2168
2169 static void
2170 df_swap_refs (struct df_ref **ref_vec, int i, int j)
2171 {
2172   struct df_ref *tmp = ref_vec[i];
2173   ref_vec[i] = ref_vec[j];
2174   ref_vec[j] = tmp;
2175 }
2176
2177 /* Sort and compress a set of refs.  */
2178
2179 static unsigned int
2180 df_sort_and_compress_refs (struct df_ref **ref_vec, unsigned int count)
2181 {
2182   struct df_scan_problem_data *problem_data
2183     = (struct df_scan_problem_data *) df_scan->problem_data;
2184   unsigned int i;
2185   unsigned int dist = 0;
2186
2187   ref_vec[count] = NULL;
2188   /* If there are 1 or 0 elements, there is nothing to do.  */
2189   if (count < 2)
2190     return count;
2191   else if (count == 2)
2192     {
2193       if (df_ref_compare (&ref_vec[0], &ref_vec[1]) > 0)
2194         df_swap_refs (ref_vec, 0, 1);
2195     }
2196   else
2197     {
2198       for (i = 0; i < count - 1; i++)
2199         if (df_ref_compare (&ref_vec[i], &ref_vec[i+1]) >= 0)
2200           break;
2201       /* If the array is already strictly ordered,
2202          which is the most common case for large COUNT case
2203          (which happens for CALL INSNs),
2204          no need to sort and filter out duplicate.
2205          Simply return the count.
2206          Make sure DF_GET_ADD_REFS adds refs in the increasing order
2207          of DF_REF_COMPARE.  */
2208       if (i == count - 1)
2209         return count;
2210       qsort (ref_vec, count, sizeof (struct df_ref *), df_ref_compare);
2211     }
2212
2213   for (i=0; i<count-dist; i++)
2214     {
2215       /* Find the next ref that is not equal to the current ref.  */
2216       while (df_ref_equal_p (ref_vec[i], ref_vec[i + dist + 1]))
2217         {
2218           pool_free (problem_data->ref_pool, ref_vec[i + dist + 1]);
2219           dist++;
2220         }
2221       /* Copy it down to the next position.  */
2222       if (dist)
2223         ref_vec[i+1] = ref_vec[i + dist + 1];
2224     }
2225
2226   count -= dist;
2227   ref_vec[count] = NULL;
2228   return count;
2229 }
2230
2231
2232 /* Return true if the contents of two df_ref's are identical.
2233    It ignores DF_REF_MARKER.  */
2234
2235 static bool
2236 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2237 {
2238   if (!mw2)
2239     return false;
2240   return (mw1 == mw2) ||
2241     (mw1->mw_reg == mw2->mw_reg
2242      && mw1->type == mw2->type
2243      && mw1->flags == mw2->flags
2244      && mw1->start_regno == mw2->start_regno
2245      && mw1->end_regno == mw2->end_regno);
2246 }
2247
2248
2249 /* Compare MW1 and MW2 for sorting.  */
2250
2251 static int
2252 df_mw_compare (const void *m1, const void *m2)
2253 {
2254   const struct df_mw_hardreg *const mw1 = *(const struct df_mw_hardreg *const*)m1;
2255   const struct df_mw_hardreg *const mw2 = *(const struct df_mw_hardreg *const*)m2;
2256
2257   if (mw1 == mw2)
2258     return 0;
2259
2260   if (mw1->type != mw2->type)
2261     return mw1->type - mw2->type;
2262
2263   if (mw1->flags != mw2->flags)
2264     return mw1->flags - mw2->flags;
2265
2266   if (mw1->start_regno != mw2->start_regno)
2267     return mw1->start_regno - mw2->start_regno;
2268
2269   if (mw1->end_regno != mw2->end_regno)
2270     return mw1->end_regno - mw2->end_regno;
2271
2272   if (mw1->mw_reg != mw2->mw_reg)
2273     return mw1->mw_order - mw2->mw_order;
2274
2275   return 0;
2276 }
2277
2278
2279 /* Sort and compress a set of refs.  */
2280
2281 static unsigned int
2282 df_sort_and_compress_mws (struct df_mw_hardreg **mw_vec, unsigned int count)
2283 {
2284   struct df_scan_problem_data *problem_data
2285     = (struct df_scan_problem_data *) df_scan->problem_data;
2286   unsigned int i;
2287   unsigned int dist = 0;
2288   mw_vec[count] = NULL;
2289
2290   if (count < 2)
2291     return count;
2292   else if (count == 2)
2293     {
2294       if (df_mw_compare (&mw_vec[0], &mw_vec[1]) > 0)
2295         {
2296           struct df_mw_hardreg *tmp = mw_vec[0];
2297           mw_vec[0] = mw_vec[1];
2298           mw_vec[1] = tmp;
2299         }
2300     }
2301   else
2302     qsort (mw_vec, count, sizeof (struct df_mw_hardreg *), df_mw_compare);
2303
2304   for (i=0; i<count-dist; i++)
2305     {
2306       /* Find the next ref that is not equal to the current ref.  */
2307       while (df_mw_equal_p (mw_vec[i], mw_vec[i + dist + 1]))
2308         {
2309           pool_free (problem_data->mw_reg_pool, mw_vec[i + dist + 1]);
2310           dist++;
2311         }
2312       /* Copy it down to the next position.  */
2313       if (dist)
2314         mw_vec[i+1] = mw_vec[i + dist + 1];
2315     }
2316
2317   count -= dist;
2318   mw_vec[count] = NULL;
2319   return count;
2320 }
2321
2322
2323 /* Sort and remove duplicates from the COLLECTION_REC.  */
2324
2325 static void
2326 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2327 {
2328   if (collection_rec->def_vec)
2329     collection_rec->next_def
2330       = df_sort_and_compress_refs (collection_rec->def_vec,
2331                                    collection_rec->next_def);
2332   if (collection_rec->use_vec)
2333     collection_rec->next_use
2334       = df_sort_and_compress_refs (collection_rec->use_vec,
2335                                    collection_rec->next_use);
2336   if (collection_rec->eq_use_vec)
2337     collection_rec->next_eq_use
2338       = df_sort_and_compress_refs (collection_rec->eq_use_vec,
2339                                    collection_rec->next_eq_use);
2340   if (collection_rec->mw_vec)
2341     collection_rec->next_mw
2342       = df_sort_and_compress_mws (collection_rec->mw_vec,
2343                                   collection_rec->next_mw);
2344 }
2345
2346
2347 /* Add the new df_ref to appropriate reg_info/ref_info chains.  */
2348
2349 static void
2350 df_install_ref (struct df_ref *this_ref,
2351                 struct df_reg_info *reg_info,
2352                 struct df_ref_info *ref_info,
2353                 bool add_to_table)
2354 {
2355   unsigned int regno = DF_REF_REGNO (this_ref);
2356   /* Add the ref to the reg_{def,use,eq_use} chain.  */
2357   struct df_ref *head = reg_info->reg_chain;
2358
2359   reg_info->reg_chain = this_ref;
2360   reg_info->n_refs++;
2361
2362   if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2363     {
2364       gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2365       df->hard_regs_live_count[regno]++;
2366     }
2367
2368   gcc_assert (DF_REF_NEXT_REG (this_ref) == NULL);
2369   gcc_assert (DF_REF_PREV_REG (this_ref) == NULL);
2370
2371   DF_REF_NEXT_REG (this_ref) = head;
2372
2373   /* We cannot actually link to the head of the chain.  */
2374   DF_REF_PREV_REG (this_ref) = NULL;
2375
2376   if (head)
2377     DF_REF_PREV_REG (head) = this_ref;
2378
2379   if (add_to_table)
2380     {
2381       gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2382       df_check_and_grow_ref_info (ref_info, 1);
2383       DF_REF_ID (this_ref) = ref_info->table_size;
2384       /* Add the ref to the big array of defs.  */
2385       ref_info->refs[ref_info->table_size] = this_ref;
2386       ref_info->table_size++;
2387     }
2388   else
2389     DF_REF_ID (this_ref) = -1;
2390
2391   ref_info->total_size++;
2392 }
2393
2394
2395 /* This function takes one of the groups of refs (defs, uses or
2396    eq_uses) and installs the entire group into the insn.  It also adds
2397    each of these refs into the appropriate chains.  */
2398
2399 static struct df_ref **
2400 df_install_refs (basic_block bb,
2401                  struct df_ref **old_vec, unsigned int count,
2402                  struct df_reg_info **reg_info,
2403                  struct df_ref_info *ref_info,
2404                  bool is_notes)
2405 {
2406   if (count)
2407     {
2408       unsigned int i;
2409       struct df_ref **new_vec = XNEWVEC (struct df_ref*, count + 1);
2410       bool add_to_table;
2411
2412       switch (ref_info->ref_order)
2413         {
2414         case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2415         case DF_REF_ORDER_BY_REG_WITH_NOTES:
2416         case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2417           ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2418           add_to_table = true;
2419           break;
2420         case DF_REF_ORDER_UNORDERED:
2421         case DF_REF_ORDER_BY_REG:
2422         case DF_REF_ORDER_BY_INSN:
2423           ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2424           add_to_table = !is_notes;
2425           break;
2426         default:
2427           add_to_table = false;
2428           break;
2429         }
2430
2431       /* Do not add if ref is not in the right blocks.  */
2432       if (add_to_table && df->analyze_subset)
2433         add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2434
2435       for (i = 0; i < count; i++)
2436         {
2437           struct df_ref *this_ref = old_vec[i];
2438           new_vec[i] = this_ref;
2439           df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2440                           ref_info, add_to_table);
2441         }
2442
2443       new_vec[count] = NULL;
2444       return new_vec;
2445     }
2446   else
2447     return df_null_ref_rec;
2448 }
2449
2450
2451 /* This function takes the mws installs the entire group into the
2452    insn.  */
2453
2454 static struct df_mw_hardreg **
2455 df_install_mws (struct df_mw_hardreg **old_vec, unsigned int count)
2456 {
2457   if (count)
2458     {
2459       struct df_mw_hardreg **new_vec
2460         = XNEWVEC (struct df_mw_hardreg*, count + 1);
2461       memcpy (new_vec, old_vec,
2462               sizeof (struct df_mw_hardreg*) * (count + 1));
2463       return new_vec;
2464     }
2465   else
2466     return df_null_mw_rec;
2467 }
2468
2469
2470 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2471    chains and update other necessary information.  */
2472
2473 static void
2474 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2475                        basic_block bb, rtx insn)
2476 {
2477   if (insn)
2478     {
2479       struct df_insn_info *insn_rec = DF_INSN_GET (insn);
2480       /* If there is a vector in the collection rec, add it to the
2481          insn.  A null rec is a signal that the caller will handle the
2482          chain specially.  */
2483       if (collection_rec->def_vec)
2484         {
2485           if (insn_rec->defs && *insn_rec->defs)
2486             free (insn_rec->defs);
2487           insn_rec->defs
2488             = df_install_refs (bb, collection_rec->def_vec,
2489                                collection_rec->next_def,
2490                                df->def_regs,
2491                                &df->def_info, false);
2492         }
2493       if (collection_rec->use_vec)
2494         {
2495           if (insn_rec->uses && *insn_rec->uses)
2496             free (insn_rec->uses);
2497           insn_rec->uses
2498             = df_install_refs (bb, collection_rec->use_vec,
2499                                collection_rec->next_use,
2500                                df->use_regs,
2501                                &df->use_info, false);
2502         }
2503       if (collection_rec->eq_use_vec)
2504         {
2505           if (insn_rec->eq_uses && *insn_rec->eq_uses)
2506             free (insn_rec->eq_uses);
2507           insn_rec->eq_uses
2508             = df_install_refs (bb, collection_rec->eq_use_vec,
2509                                collection_rec->next_eq_use,
2510                                df->eq_use_regs,
2511                                &df->use_info, true);
2512         }
2513       if (collection_rec->mw_vec)
2514         {
2515           if (insn_rec->mw_hardregs && *insn_rec->mw_hardregs)
2516             free (insn_rec->mw_hardregs);
2517           insn_rec->mw_hardregs
2518             = df_install_mws (collection_rec->mw_vec,
2519                               collection_rec->next_mw);
2520         }
2521     }
2522   else
2523     {
2524       struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2525
2526       if (bb_info->artificial_defs && *bb_info->artificial_defs)
2527         free (bb_info->artificial_defs);
2528       bb_info->artificial_defs
2529         = df_install_refs (bb, collection_rec->def_vec,
2530                            collection_rec->next_def,
2531                            df->def_regs,
2532                            &df->def_info, false);
2533       if (bb_info->artificial_uses && *bb_info->artificial_uses)
2534         free (bb_info->artificial_uses);
2535       bb_info->artificial_uses
2536         = df_install_refs (bb, collection_rec->use_vec,
2537                            collection_rec->next_use,
2538                            df->use_regs,
2539                            &df->use_info, false);
2540     }
2541 }
2542
2543
2544 /* Allocate a ref and initialize its fields. */
2545
2546 static struct df_ref *
2547 df_ref_create_structure (struct df_collection_rec *collection_rec,
2548                          rtx reg, rtx *loc,
2549                          basic_block bb, rtx insn,
2550                          enum df_ref_type ref_type,
2551                          enum df_ref_flags ref_flags)
2552 {
2553   struct df_ref *this_ref;
2554   int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2555   struct df_scan_problem_data *problem_data
2556     = (struct df_scan_problem_data *) df_scan->problem_data;
2557
2558   this_ref = pool_alloc (problem_data->ref_pool);
2559   DF_REF_ID (this_ref) = -1;
2560   DF_REF_REG (this_ref) = reg;
2561   DF_REF_REGNO (this_ref) =  regno;
2562   DF_REF_LOC (this_ref) = loc;
2563   DF_REF_INSN (this_ref) = insn;
2564   DF_REF_CHAIN (this_ref) = NULL;
2565   DF_REF_TYPE (this_ref) = ref_type;
2566   DF_REF_FLAGS (this_ref) = ref_flags;
2567   DF_REF_BB (this_ref) = bb;
2568   DF_REF_NEXT_REG (this_ref) = NULL;
2569   DF_REF_PREV_REG (this_ref) = NULL;
2570   DF_REF_ORDER (this_ref) = df->ref_order++;
2571
2572   /* We need to clear this bit because fwprop, and in the future
2573      possibly other optimizations sometimes create new refs using ond
2574      refs as the model.  */
2575   DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2576
2577   /* See if this ref needs to have DF_HARD_REG_LIVE bit set.  */
2578   if ((regno < FIRST_PSEUDO_REGISTER)
2579       && (!DF_REF_IS_ARTIFICIAL (this_ref)))
2580     {
2581       if (DF_REF_TYPE (this_ref) == DF_REF_REG_DEF)
2582         {
2583           if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2584             DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2585         }
2586       else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2587                  && (regno == FRAME_POINTER_REGNUM
2588                      || regno == ARG_POINTER_REGNUM)))
2589         DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2590     }
2591
2592   if (collection_rec)
2593     {
2594       if (DF_REF_TYPE (this_ref) == DF_REF_REG_DEF)
2595         collection_rec->def_vec[collection_rec->next_def++] = this_ref;
2596       else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2597         collection_rec->eq_use_vec[collection_rec->next_eq_use++] = this_ref;
2598       else
2599         collection_rec->use_vec[collection_rec->next_use++] = this_ref;
2600     }
2601
2602   return this_ref;
2603 }
2604
2605
2606 /* Create new references of type DF_REF_TYPE for each part of register REG
2607    at address LOC within INSN of BB.  */
2608
2609 static void
2610 df_ref_record (struct df_collection_rec *collection_rec,
2611                rtx reg, rtx *loc,
2612                basic_block bb, rtx insn,
2613                enum df_ref_type ref_type,
2614                enum df_ref_flags ref_flags)
2615 {
2616   unsigned int regno;
2617
2618   gcc_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2619
2620   regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2621   if (regno < FIRST_PSEUDO_REGISTER)
2622     {
2623       struct df_mw_hardreg *hardreg = NULL;
2624       struct df_scan_problem_data *problem_data
2625         = (struct df_scan_problem_data *) df_scan->problem_data;
2626       unsigned int i;
2627       unsigned int endregno;
2628       struct df_ref *ref;
2629
2630       if (GET_CODE (reg) == SUBREG)
2631         {
2632           regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2633                                         SUBREG_BYTE (reg), GET_MODE (reg));
2634           endregno = regno + subreg_nregs (reg);
2635         }
2636       else
2637         endregno = END_HARD_REGNO (reg);
2638
2639       /*  If this is a multiword hardreg, we create some extra
2640           datastructures that will enable us to easily build REG_DEAD
2641           and REG_UNUSED notes.  */
2642       if ((endregno != regno + 1) && insn)
2643         {
2644           /* Sets to a subreg of a multiword register are partial.
2645              Sets to a non-subreg of a multiword register are not.  */
2646           if (GET_CODE (reg) == SUBREG)
2647             ref_flags |= DF_REF_PARTIAL;
2648           ref_flags |= DF_REF_MW_HARDREG;
2649
2650           hardreg = pool_alloc (problem_data->mw_reg_pool);
2651           hardreg->type = ref_type;
2652           hardreg->flags = ref_flags;
2653           hardreg->mw_reg = reg;
2654           hardreg->start_regno = regno;
2655           hardreg->end_regno = endregno - 1;
2656           hardreg->mw_order = df->ref_order++;
2657           collection_rec->mw_vec[collection_rec->next_mw++] = hardreg;
2658         }
2659
2660       for (i = regno; i < endregno; i++)
2661         {
2662           ref = df_ref_create_structure (collection_rec, regno_reg_rtx[i], loc,
2663                                          bb, insn, ref_type, ref_flags);
2664
2665           gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2666         }
2667     }
2668   else
2669     {
2670       struct df_ref *ref;
2671       ref = df_ref_create_structure (collection_rec, reg, loc, bb, insn,
2672                                      ref_type, ref_flags);
2673     }
2674 }
2675
2676
2677 /* A set to a non-paradoxical SUBREG for which the number of word_mode units
2678    covered by the outer mode is smaller than that covered by the inner mode,
2679    is a read-modify-write operation.
2680    This function returns true iff the SUBREG X is such a SUBREG.  */
2681
2682 bool
2683 df_read_modify_subreg_p (rtx x)
2684 {
2685   unsigned int isize, osize;
2686   if (GET_CODE (x) != SUBREG)
2687     return false;
2688   isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
2689   osize = GET_MODE_SIZE (GET_MODE (x));
2690   return isize > osize
2691          && isize > REGMODE_NATURAL_SIZE (GET_MODE (SUBREG_REG (x)));
2692 }
2693
2694
2695 /* Process all the registers defined in the rtx, X.
2696    Autoincrement/decrement definitions will be picked up by
2697    df_uses_record.  */
2698
2699 static void
2700 df_def_record_1 (struct df_collection_rec *collection_rec,
2701                  rtx x, basic_block bb, rtx insn,
2702                  enum df_ref_flags flags)
2703 {
2704   rtx *loc;
2705   rtx dst;
2706
2707  /* We may recursively call ourselves on EXPR_LIST when dealing with PARALLEL
2708      construct.  */
2709   if (GET_CODE (x) == EXPR_LIST || GET_CODE (x) == CLOBBER)
2710     loc = &XEXP (x, 0);
2711   else
2712     loc = &SET_DEST (x);
2713   dst = *loc;
2714
2715   /* It is legal to have a set destination be a parallel. */
2716   if (GET_CODE (dst) == PARALLEL)
2717     {
2718       int i;
2719
2720       for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2721         {
2722           rtx temp = XVECEXP (dst, 0, i);
2723           if (GET_CODE (temp) == EXPR_LIST || GET_CODE (temp) == CLOBBER
2724               || GET_CODE (temp) == SET)
2725             df_def_record_1 (collection_rec,
2726                              temp, bb, insn,
2727                              GET_CODE (temp) == CLOBBER
2728                              ? flags | DF_REF_MUST_CLOBBER : flags);
2729         }
2730       return;
2731     }
2732
2733   /* Maybe, we should flag the use of STRICT_LOW_PART somehow.  It might
2734      be handy for the reg allocator.  */
2735   while (GET_CODE (dst) == STRICT_LOW_PART
2736          || GET_CODE (dst) == ZERO_EXTRACT)
2737     {
2738       flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2739       if (GET_CODE (dst) == ZERO_EXTRACT)
2740         flags |= DF_REF_EXTRACT;
2741       else
2742         flags |= DF_REF_STRICT_LOWER_PART;
2743
2744       loc = &XEXP (dst, 0);
2745       dst = *loc;
2746     }
2747
2748   /* At this point if we do not have a reg or a subreg, just return.  */
2749   if (REG_P (dst))
2750     {
2751       df_ref_record (collection_rec,
2752                      dst, loc, bb, insn, DF_REF_REG_DEF, flags);
2753
2754       /* We want to keep sp alive everywhere - by making all
2755          writes to sp also use of sp. */
2756       if (REGNO (dst) == STACK_POINTER_REGNUM)
2757         df_ref_record (collection_rec,
2758                        dst, NULL, bb, insn, DF_REF_REG_USE, flags);
2759     }
2760   else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst)))
2761     {
2762       if (df_read_modify_subreg_p (dst))
2763         flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2764
2765       flags |= DF_REF_SUBREG;
2766
2767       df_ref_record (collection_rec,
2768                      dst, loc, bb, insn, DF_REF_REG_DEF, flags);
2769     }
2770 }
2771
2772
2773 /* Process all the registers defined in the pattern rtx, X.  */
2774
2775 static void
2776 df_defs_record (struct df_collection_rec *collection_rec,
2777                 rtx x, basic_block bb, rtx insn, enum df_ref_flags flags)
2778 {
2779   RTX_CODE code = GET_CODE (x);
2780
2781   if (code == SET || code == CLOBBER)
2782     {
2783       /* Mark the single def within the pattern.  */
2784       enum df_ref_flags clobber_flags = flags;
2785       clobber_flags |= (code == CLOBBER) ? DF_REF_MUST_CLOBBER : 0;
2786       df_def_record_1 (collection_rec, x, bb, insn, clobber_flags);
2787     }
2788   else if (code == COND_EXEC)
2789     {
2790       df_defs_record (collection_rec, COND_EXEC_CODE (x),
2791                       bb, insn, DF_REF_CONDITIONAL);
2792     }
2793   else if (code == PARALLEL)
2794     {
2795       int i;
2796
2797       /* Mark the multiple defs within the pattern.  */
2798       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2799         df_defs_record (collection_rec, XVECEXP (x, 0, i), bb, insn, flags);
2800     }
2801 }
2802
2803
2804 /* Process all the registers used in the rtx at address LOC.  */
2805
2806 static void
2807 df_uses_record (struct df_collection_rec *collection_rec,
2808                 rtx *loc, enum df_ref_type ref_type,
2809                 basic_block bb, rtx insn, enum df_ref_flags flags)
2810 {
2811   RTX_CODE code;
2812   rtx x;
2813
2814  retry:
2815   x = *loc;
2816   if (!x)
2817     return;
2818   code = GET_CODE (x);
2819   switch (code)
2820     {
2821     case LABEL_REF:
2822     case SYMBOL_REF:
2823     case CONST_INT:
2824     case CONST:
2825     case CONST_DOUBLE:
2826     case CONST_FIXED:
2827     case CONST_VECTOR:
2828     case PC:
2829     case CC0:
2830     case ADDR_VEC:
2831     case ADDR_DIFF_VEC:
2832       return;
2833
2834     case CLOBBER:
2835       /* If we are clobbering a MEM, mark any registers inside the address
2836          as being used.  */
2837       if (MEM_P (XEXP (x, 0)))
2838         df_uses_record (collection_rec,
2839                         &XEXP (XEXP (x, 0), 0),
2840                         DF_REF_REG_MEM_STORE, bb, insn, flags);
2841
2842       /* If we're clobbering a REG then we have a def so ignore.  */
2843       return;
2844
2845     case MEM:
2846       df_uses_record (collection_rec,
2847                       &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
2848                       bb, insn, flags & DF_REF_IN_NOTE);
2849       return;
2850
2851     case SUBREG:
2852       /* While we're here, optimize this case.  */
2853       flags |= DF_REF_PARTIAL;
2854       /* In case the SUBREG is not of a REG, do not optimize.  */
2855       if (!REG_P (SUBREG_REG (x)))
2856         {
2857           loc = &SUBREG_REG (x);
2858           df_uses_record (collection_rec, loc, ref_type, bb, insn, flags);
2859           return;
2860         }
2861       /* ... Fall through ...  */
2862
2863     case REG:
2864       df_ref_record (collection_rec,
2865                      x, loc, bb, insn, ref_type, flags);
2866       return;
2867
2868     case SET:
2869       {
2870         rtx dst = SET_DEST (x);
2871         gcc_assert (!(flags & DF_REF_IN_NOTE));
2872         df_uses_record (collection_rec,
2873                         &SET_SRC (x), DF_REF_REG_USE, bb, insn, flags);
2874
2875         switch (GET_CODE (dst))
2876           {
2877             case SUBREG:
2878               if (df_read_modify_subreg_p (dst))
2879                 {
2880                   df_uses_record (collection_rec, &SUBREG_REG (dst),
2881                                   DF_REF_REG_USE, bb, insn,
2882                                   flags | DF_REF_READ_WRITE | DF_REF_SUBREG);
2883                   break;
2884                 }
2885               /* Fall through.  */
2886             case REG:
2887             case PARALLEL:
2888             case SCRATCH:
2889             case PC:
2890             case CC0:
2891                 break;
2892             case MEM:
2893               df_uses_record (collection_rec, &XEXP (dst, 0),
2894                               DF_REF_REG_MEM_STORE, bb, insn, flags);
2895               break;
2896             case STRICT_LOW_PART:
2897               {
2898                 rtx *temp = &XEXP (dst, 0);
2899                 /* A strict_low_part uses the whole REG and not just the
2900                  SUBREG.  */
2901                 dst = XEXP (dst, 0);
2902                 df_uses_record (collection_rec,
2903                                 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
2904                                 DF_REF_REG_USE, bb, insn,
2905                                 DF_REF_READ_WRITE | DF_REF_STRICT_LOWER_PART);
2906               }
2907               break;
2908             case ZERO_EXTRACT:
2909             case SIGN_EXTRACT:
2910               df_uses_record (collection_rec, &XEXP (dst, 0),
2911                               DF_REF_REG_USE, bb, insn,
2912                               DF_REF_READ_WRITE | DF_REF_EXTRACT);
2913               df_uses_record (collection_rec, &XEXP (dst, 1),
2914                               DF_REF_REG_USE, bb, insn, flags);
2915               df_uses_record (collection_rec, &XEXP (dst, 2),
2916                               DF_REF_REG_USE, bb, insn, flags);
2917               dst = XEXP (dst, 0);
2918               break;
2919             default:
2920               gcc_unreachable ();
2921           }
2922         return;
2923       }
2924
2925     case RETURN:
2926       break;
2927
2928     case ASM_OPERANDS:
2929     case UNSPEC_VOLATILE:
2930     case TRAP_IF:
2931     case ASM_INPUT:
2932       {
2933         /* Traditional and volatile asm instructions must be
2934            considered to use and clobber all hard registers, all
2935            pseudo-registers and all of memory.  So must TRAP_IF and
2936            UNSPEC_VOLATILE operations.
2937
2938            Consider for instance a volatile asm that changes the fpu
2939            rounding mode.  An insn should not be moved across this
2940            even if it only uses pseudo-regs because it might give an
2941            incorrectly rounded result.
2942
2943            However, flow.c's liveness computation did *not* do this,
2944            giving the reasoning as " ?!? Unfortunately, marking all
2945            hard registers as live causes massive problems for the
2946            register allocator and marking all pseudos as live creates
2947            mountains of uninitialized variable warnings."
2948
2949            In order to maintain the status quo with regard to liveness
2950            and uses, we do what flow.c did and just mark any regs we
2951            can find in ASM_OPERANDS as used.  In global asm insns are
2952            scanned and regs_asm_clobbered is filled out.
2953
2954            For all ASM_OPERANDS, we must traverse the vector of input
2955            operands.  We can not just fall through here since then we
2956            would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
2957            which do not indicate traditional asms unlike their normal
2958            usage.  */
2959         if (code == ASM_OPERANDS)
2960           {
2961             int j;
2962
2963             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2964               df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j),
2965                               DF_REF_REG_USE, bb, insn, flags);
2966             return;
2967           }
2968         break;
2969       }
2970
2971     case PRE_DEC:
2972     case POST_DEC:
2973     case PRE_INC:
2974     case POST_INC:
2975     case PRE_MODIFY:
2976     case POST_MODIFY:
2977       /* Catch the def of the register being modified.  */
2978       df_ref_record (collection_rec, XEXP (x, 0), &XEXP (x, 0), bb, insn,
2979                      DF_REF_REG_DEF,
2980                      flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
2981
2982       /* ... Fall through to handle uses ...  */
2983
2984     default:
2985       break;
2986     }
2987
2988   /* Recursively scan the operands of this expression.  */
2989   {
2990     const char *fmt = GET_RTX_FORMAT (code);
2991     int i;
2992
2993     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2994       {
2995         if (fmt[i] == 'e')
2996           {
2997             /* Tail recursive case: save a function call level.  */
2998             if (i == 0)
2999               {
3000                 loc = &XEXP (x, 0);
3001                 goto retry;
3002               }
3003             df_uses_record (collection_rec, &XEXP (x, i), ref_type, bb, insn, flags);
3004           }
3005         else if (fmt[i] == 'E')
3006           {
3007             int j;
3008             for (j = 0; j < XVECLEN (x, i); j++)
3009               df_uses_record (collection_rec,
3010                               &XVECEXP (x, i, j), ref_type, bb, insn, flags);
3011           }
3012       }
3013   }
3014
3015   return;
3016 }
3017
3018
3019 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses.  */
3020
3021 static void
3022 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3023 {
3024   unsigned int i;
3025   for (i = 0; i < collection_rec->next_def; i++)
3026     {
3027       struct df_ref *ref = collection_rec->def_vec[i];
3028       if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3029         {
3030           struct df_ref *use
3031             = df_ref_create_structure (collection_rec, DF_REF_REG (ref),
3032                                        DF_REF_LOC (ref), DF_REF_BB (ref),
3033                                        DF_REF_INSN (ref), DF_REF_REG_USE,
3034                                        DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3035           DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3036         }
3037     }
3038 }
3039
3040
3041 /* Get call's extra defs and uses. */
3042
3043 static void
3044 df_get_call_refs (struct df_collection_rec * collection_rec,
3045                   basic_block bb,
3046                   rtx insn,
3047                   enum df_ref_flags flags)
3048 {
3049   rtx note;
3050   bitmap_iterator bi;
3051   unsigned int ui;
3052   bool is_sibling_call;
3053   unsigned int i;
3054   bitmap defs_generated = BITMAP_ALLOC (&df_bitmap_obstack);
3055
3056   /* Do not generate clobbers for registers that are the result of the
3057      call.  This causes ordering problems in the chain building code
3058      depending on which def is seen first.  */
3059   for (i=0; i<collection_rec->next_def; i++)
3060     {
3061       struct df_ref *def = collection_rec->def_vec[i];
3062       bitmap_set_bit (defs_generated, DF_REF_REGNO (def));
3063     }
3064
3065   /* Record the registers used to pass arguments, and explicitly
3066      noted as clobbered.  */
3067   for (note = CALL_INSN_FUNCTION_USAGE (insn); note;
3068        note = XEXP (note, 1))
3069     {
3070       if (GET_CODE (XEXP (note, 0)) == USE)
3071         df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0),
3072                         DF_REF_REG_USE, bb, insn, flags);
3073       else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3074         {
3075           if (REG_P (XEXP (XEXP (note, 0), 0)))
3076             {
3077               unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3078               if (!bitmap_bit_p (defs_generated, regno))
3079                 df_defs_record (collection_rec, XEXP (note, 0), bb,
3080                                 insn, flags);
3081             }
3082           else
3083             df_uses_record (collection_rec, &XEXP (note, 0),
3084                             DF_REF_REG_USE, bb, insn, flags);
3085         }
3086     }
3087
3088   /* The stack ptr is used (honorarily) by a CALL insn.  */
3089   df_ref_record (collection_rec, regno_reg_rtx[STACK_POINTER_REGNUM],
3090                  NULL, bb, insn, DF_REF_REG_USE, DF_REF_CALL_STACK_USAGE | flags);
3091
3092   /* Calls may also reference any of the global registers,
3093      so they are recorded as used.  */
3094   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3095     if (global_regs[i])
3096       {
3097         df_ref_record (collection_rec, regno_reg_rtx[i],
3098                        NULL, bb, insn, DF_REF_REG_USE, flags);
3099         df_ref_record (collection_rec, regno_reg_rtx[i],
3100                        NULL, bb, insn, DF_REF_REG_DEF, flags);
3101       }
3102
3103   is_sibling_call = SIBLING_CALL_P (insn);
3104   EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, ui, bi)
3105     {
3106       if (!global_regs[ui]
3107           && (!bitmap_bit_p (defs_generated, ui))
3108           && (!is_sibling_call
3109               || !bitmap_bit_p (df->exit_block_uses, ui)
3110               || refers_to_regno_p (ui, ui+1,
3111                                     current_function_return_rtx, NULL)))
3112         df_ref_record (collection_rec, regno_reg_rtx[ui],
3113                        NULL, bb, insn, DF_REF_REG_DEF, DF_REF_MAY_CLOBBER | flags);
3114     }
3115
3116   BITMAP_FREE (defs_generated);
3117   return;
3118 }
3119
3120 /* Collect all refs in the INSN. This function is free of any
3121    side-effect - it will create and return a lists of df_ref's in the
3122    COLLECTION_REC without putting those refs into existing ref chains
3123    and reg chains. */
3124
3125 static void
3126 df_insn_refs_collect (struct df_collection_rec* collection_rec,
3127                       basic_block bb, rtx insn)
3128 {
3129   rtx note;
3130   bool is_cond_exec = (GET_CODE (PATTERN (insn)) == COND_EXEC);
3131
3132   /* Clear out the collection record.  */
3133   collection_rec->next_def = 0;
3134   collection_rec->next_use = 0;
3135   collection_rec->next_eq_use = 0;
3136   collection_rec->next_mw = 0;
3137
3138   /* Record register defs.  */
3139   df_defs_record (collection_rec, PATTERN (insn), bb, insn, 0);
3140
3141   /* Process REG_EQUIV/REG_EQUAL notes */
3142   for (note = REG_NOTES (insn); note;
3143        note = XEXP (note, 1))
3144     {
3145       switch (REG_NOTE_KIND (note))
3146         {
3147         case REG_EQUIV:
3148         case REG_EQUAL:
3149           df_uses_record (collection_rec,
3150                           &XEXP (note, 0), DF_REF_REG_USE,
3151                           bb, insn, DF_REF_IN_NOTE);
3152           break;
3153         case REG_NON_LOCAL_GOTO:
3154           /* The frame ptr is used by a non-local goto.  */
3155           df_ref_record (collection_rec,
3156                          regno_reg_rtx[FRAME_POINTER_REGNUM],
3157                          NULL,
3158                          bb, insn,
3159                          DF_REF_REG_USE, 0);
3160 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3161           df_ref_record (collection_rec,
3162                          regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3163                          NULL,
3164                          bb, insn,
3165                          DF_REF_REG_USE, 0);
3166 #endif
3167           break;
3168         default:
3169           break;
3170         }
3171     }
3172
3173   if (CALL_P (insn))
3174     df_get_call_refs (collection_rec, bb, insn,
3175                       (is_cond_exec) ? DF_REF_CONDITIONAL : 0);
3176
3177   /* Record the register uses.  */
3178   df_uses_record (collection_rec,
3179                   &PATTERN (insn), DF_REF_REG_USE, bb, insn, 0);
3180
3181   /* DF_REF_CONDITIONAL needs corresponding USES. */
3182   if (is_cond_exec)
3183     df_get_conditional_uses (collection_rec);
3184
3185   df_canonize_collection_rec (collection_rec);
3186 }
3187
3188 /* Recompute the luids for the insns in BB.  */
3189
3190 void
3191 df_recompute_luids (basic_block bb)
3192 {
3193   rtx insn;
3194   int luid = 0;
3195
3196   df_grow_insn_info ();
3197
3198   /* Scan the block an insn at a time from beginning to end.  */
3199   FOR_BB_INSNS (bb, insn)
3200     {
3201       struct df_insn_info *insn_info = DF_INSN_GET (insn);
3202       /* Inserting labels does not always trigger the incremental
3203          rescanning.  */
3204       if (!insn_info)
3205         {
3206           gcc_assert (!INSN_P (insn));
3207           df_insn_create_insn_record (insn);
3208         }
3209
3210       DF_INSN_LUID (insn) = luid;
3211       if (INSN_P (insn))
3212         luid++;
3213     }
3214 }
3215
3216
3217 /* Returns true if the function entry needs to
3218    define the static chain register.  */
3219
3220 static bool
3221 df_need_static_chain_reg (struct function *fun)
3222 {
3223   tree fun_context = decl_function_context (fun->decl);
3224   return fun_context
3225          && DECL_NO_STATIC_CHAIN (fun_context) == false;
3226 }
3227
3228
3229 /* Collect all artificial refs at the block level for BB and add them
3230    to COLLECTION_REC.  */
3231
3232 static void
3233 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3234 {
3235   collection_rec->next_def = 0;
3236   collection_rec->next_use = 0;
3237   collection_rec->next_eq_use = 0;
3238   collection_rec->next_mw = 0;
3239
3240   if (bb->index == ENTRY_BLOCK)
3241     {
3242       df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3243       return;
3244     }
3245   else if (bb->index == EXIT_BLOCK)
3246     {
3247       df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3248       return;
3249     }
3250
3251 #ifdef EH_RETURN_DATA_REGNO
3252   if (bb_has_eh_pred (bb))
3253     {
3254       unsigned int i;
3255       /* Mark the registers that will contain data for the handler.  */
3256       for (i = 0; ; ++i)
3257         {
3258           unsigned regno = EH_RETURN_DATA_REGNO (i);
3259           if (regno == INVALID_REGNUM)
3260             break;
3261           df_ref_record (collection_rec, regno_reg_rtx[regno], NULL,
3262                          bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3263         }
3264     }
3265 #endif
3266
3267
3268 #ifdef EH_USES
3269   if (bb_has_eh_pred (bb))
3270     {
3271       unsigned int i;
3272       /* This code is putting in an artificial ref for the use at the
3273          TOP of the block that receives the exception.  It is too
3274          cumbersome to actually put the ref on the edge.  We could
3275          either model this at the top of the receiver block or the
3276          bottom of the sender block.
3277
3278          The bottom of the sender block is problematic because not all
3279          out-edges of the a block are eh-edges.  However, it is true
3280          that all edges into a block are either eh-edges or none of
3281          them are eh-edges.  Thus, we can model this at the top of the
3282          eh-receiver for all of the edges at once. */
3283       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3284         if (EH_USES (i))
3285           df_ref_record (collection_rec, regno_reg_rtx[i], NULL,
3286                          bb, NULL, DF_REF_REG_USE, DF_REF_AT_TOP);
3287     }
3288 #endif
3289
3290   /* Add the hard_frame_pointer if this block is the target of a
3291      non-local goto.  */
3292   if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3293     df_ref_record (collection_rec, hard_frame_pointer_rtx, NULL,
3294                    bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3295
3296   /* Add the artificial uses.  */
3297   if (bb->index >= NUM_FIXED_BLOCKS)
3298     {
3299       bitmap_iterator bi;
3300       unsigned int regno;
3301       bitmap au = bb_has_eh_pred (bb)
3302         ? df->eh_block_artificial_uses
3303         : df->regular_block_artificial_uses;
3304
3305       EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3306         {
3307           df_ref_record (collection_rec, regno_reg_rtx[regno], NULL,
3308                          bb, NULL, DF_REF_REG_USE, 0);
3309         }
3310     }
3311
3312   df_canonize_collection_rec (collection_rec);
3313 }
3314
3315
3316 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS.  */
3317
3318 void
3319 df_bb_refs_record (int bb_index, bool scan_insns)
3320 {
3321   basic_block bb = BASIC_BLOCK (bb_index);
3322   rtx insn;
3323   int luid = 0;
3324   struct df_scan_bb_info *bb_info;
3325   struct df_collection_rec collection_rec;
3326   collection_rec.def_vec = alloca (sizeof (struct df_ref*) * 1000);
3327   collection_rec.use_vec = alloca (sizeof (struct df_ref*) * 1000);
3328   collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
3329   collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 100);
3330
3331   if (!df)
3332     return;
3333
3334   bb_info = df_scan_get_bb_info (bb_index);
3335
3336   /* Need to make sure that there is a record in the basic block info. */
3337   if (!bb_info)
3338     {
3339       bb_info = (struct df_scan_bb_info *) pool_alloc (df_scan->block_pool);
3340       df_scan_set_bb_info (bb_index, bb_info);
3341       bb_info->artificial_defs = NULL;
3342       bb_info->artificial_uses = NULL;
3343     }
3344
3345   if (scan_insns)
3346     /* Scan the block an insn at a time from beginning to end.  */
3347     FOR_BB_INSNS (bb, insn)
3348       {
3349         struct df_insn_info *insn_info = DF_INSN_GET (insn);
3350         gcc_assert (!insn_info);
3351
3352         df_insn_create_insn_record (insn);
3353         if (INSN_P (insn))
3354           {
3355             /* Record refs within INSN.  */
3356             DF_INSN_LUID (insn) = luid++;
3357             df_insn_refs_collect (&collection_rec, bb, insn);
3358             df_refs_add_to_chains (&collection_rec, bb, insn);
3359           }
3360         DF_INSN_LUID (insn) = luid;
3361       }
3362
3363   /* Other block level artificial refs */
3364   df_bb_refs_collect (&collection_rec, bb);
3365   df_refs_add_to_chains (&collection_rec, bb, NULL);
3366
3367   /* Now that the block has been processed, set the block as dirty so
3368      LR and LIVE will get it processed.  */
3369   df_set_bb_dirty (bb);
3370 }
3371
3372
3373 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3374    block. */
3375
3376 static void
3377 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3378 {
3379   bitmap_clear (regular_block_artificial_uses);
3380
3381   if (reload_completed)
3382     {
3383       if (frame_pointer_needed)
3384         bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3385     }
3386   else
3387     /* Before reload, there are a few registers that must be forced
3388        live everywhere -- which might not already be the case for
3389        blocks within infinite loops.  */
3390     {
3391       /* Any reference to any pseudo before reload is a potential
3392          reference of the frame pointer.  */
3393       bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3394
3395 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3396       bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3397 #endif
3398
3399 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3400       /* Pseudos with argument area equivalences may require
3401          reloading via the argument pointer.  */
3402       if (fixed_regs[ARG_POINTER_REGNUM])
3403         bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3404 #endif
3405
3406       /* Any constant, or pseudo with constant equivalences, may
3407          require reloading from memory using the pic register.  */
3408       if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3409           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3410         bitmap_set_bit (regular_block_artificial_uses, PIC_OFFSET_TABLE_REGNUM);
3411     }
3412   /* The all-important stack pointer must always be live.  */
3413   bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3414 }
3415
3416
3417 /* Get the artificial use set for an eh block. */
3418
3419 static void
3420 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3421 {
3422   bitmap_clear (eh_block_artificial_uses);
3423
3424   /* The following code (down thru the arg_pointer setting APPEARS
3425      to be necessary because there is nothing that actually
3426      describes what the exception handling code may actually need
3427      to keep alive.  */
3428   if (reload_completed)
3429     {
3430       if (frame_pointer_needed)
3431         {
3432           bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3433 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3434           bitmap_set_bit (eh_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3435 #endif
3436         }
3437 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3438       if (fixed_regs[ARG_POINTER_REGNUM])
3439         bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3440 #endif
3441     }
3442 }
3443
3444
3445 \f
3446 /*----------------------------------------------------------------------------
3447    Specialized hard register scanning functions.
3448 ----------------------------------------------------------------------------*/
3449
3450
3451 /* Mark a register in SET.  Hard registers in large modes get all
3452    of their component registers set as well.  */
3453
3454 static void
3455 df_mark_reg (rtx reg, void *vset)
3456 {
3457   bitmap set = (bitmap) vset;
3458   int regno = REGNO (reg);
3459
3460   gcc_assert (GET_MODE (reg) != BLKmode);
3461
3462   bitmap_set_bit (set, regno);
3463   if (regno < FIRST_PSEUDO_REGISTER)
3464     {
3465       int n = hard_regno_nregs[regno][GET_MODE (reg)];
3466       while (--n > 0)
3467         bitmap_set_bit  (set, regno + n);
3468     }
3469 }
3470
3471
3472 /* Set the bit for regs that are considered being defined at the entry. */
3473
3474 static void
3475 df_get_entry_block_def_set (bitmap entry_block_defs)
3476 {
3477   rtx r;
3478   int i;
3479
3480   bitmap_clear (entry_block_defs);
3481
3482   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3483     {
3484       if (FUNCTION_ARG_REGNO_P (i))
3485 #ifdef INCOMING_REGNO
3486         bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3487 #else
3488         bitmap_set_bit (entry_block_defs, i);
3489 #endif
3490     }
3491
3492   /* Once the prologue has been generated, all of these registers
3493      should just show up in the first regular block.  */
3494   if (HAVE_prologue && epilogue_completed)
3495     {
3496       /* Defs for the callee saved registers are inserted so that the
3497          pushes have some defining location.  */
3498       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3499         if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3500           bitmap_set_bit (entry_block_defs, i);
3501     }
3502   else
3503     {
3504       /* The always important stack pointer.  */
3505       bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3506
3507       /* If STATIC_CHAIN_INCOMING_REGNUM == STATIC_CHAIN_REGNUM
3508          only STATIC_CHAIN_REGNUM is defined.  If they are different,
3509          we only care about the STATIC_CHAIN_INCOMING_REGNUM.  */
3510 #ifdef STATIC_CHAIN_INCOMING_REGNUM
3511       bitmap_set_bit (entry_block_defs, STATIC_CHAIN_INCOMING_REGNUM);
3512 #else
3513 #ifdef STATIC_CHAIN_REGNUM
3514       bitmap_set_bit (entry_block_defs, STATIC_CHAIN_REGNUM);
3515 #endif
3516 #endif
3517     }
3518
3519   r = targetm.calls.struct_value_rtx (current_function_decl, true);
3520   if (r && REG_P (r))
3521     bitmap_set_bit (entry_block_defs, REGNO (r));
3522
3523   if ((!reload_completed) || frame_pointer_needed)
3524     {
3525       /* Any reference to any pseudo before reload is a potential
3526          reference of the frame pointer.  */
3527       bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3528 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3529       /* If they are different, also mark the hard frame pointer as live.  */
3530       if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3531         bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3532 #endif
3533     }
3534
3535   /* These registers are live everywhere.  */
3536   if (!reload_completed)
3537     {
3538 #ifdef EH_USES
3539       /* The ia-64, the only machine that uses this, does not define these
3540          until after reload.  */
3541       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3542         if (EH_USES (i))
3543           {
3544             bitmap_set_bit (entry_block_defs, i);
3545           }
3546 #endif
3547
3548 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3549       /* Pseudos with argument area equivalences may require
3550          reloading via the argument pointer.  */
3551       if (fixed_regs[ARG_POINTER_REGNUM])
3552         bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3553 #endif
3554
3555 #ifdef PIC_OFFSET_TABLE_REGNUM
3556       /* Any constant, or pseudo with constant equivalences, may
3557          require reloading from memory using the pic register.  */
3558       if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3559           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3560         bitmap_set_bit (entry_block_defs, PIC_OFFSET_TABLE_REGNUM);
3561 #endif
3562     }
3563
3564 #ifdef INCOMING_RETURN_ADDR_RTX
3565   if (REG_P (INCOMING_RETURN_ADDR_RTX))
3566     bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3567 #endif
3568
3569   targetm.live_on_entry (entry_block_defs);
3570
3571   /* If the function has an incoming STATIC_CHAIN,
3572      it has to show up in the entry def set.  */
3573   if (df_need_static_chain_reg (cfun))
3574     {
3575 #ifdef STATIC_CHAIN_INCOMING_REGNUM
3576       bitmap_set_bit (entry_block_defs, STATIC_CHAIN_INCOMING_REGNUM);
3577 #else
3578 #ifdef STATIC_CHAIN_REGNUM
3579       bitmap_set_bit (entry_block_defs, STATIC_CHAIN_REGNUM);
3580 #endif
3581 #endif
3582     }
3583 }
3584
3585
3586 /* Return the (conservative) set of hard registers that are defined on
3587    entry to the function.
3588    It uses df->entry_block_defs to determine which register
3589    reference to include.  */
3590
3591 static void
3592 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3593                              bitmap entry_block_defs)
3594 {
3595   unsigned int i;
3596   bitmap_iterator bi;
3597
3598   EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3599     {
3600       df_ref_record (collection_rec, regno_reg_rtx[i], NULL,
3601                      ENTRY_BLOCK_PTR, NULL, DF_REF_REG_DEF, 0);
3602     }
3603
3604   df_canonize_collection_rec (collection_rec);
3605 }
3606
3607
3608 /* Record the (conservative) set of hard registers that are defined on
3609    entry to the function.  */
3610
3611 static void
3612 df_record_entry_block_defs (bitmap entry_block_defs)
3613 {
3614   struct df_collection_rec collection_rec;
3615   memset (&collection_rec, 0, sizeof (struct df_collection_rec));
3616   collection_rec.def_vec = alloca (sizeof (struct df_ref*) * FIRST_PSEUDO_REGISTER);
3617
3618   df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3619
3620   /* Process bb_refs chain */
3621   df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (ENTRY_BLOCK), NULL);
3622 }
3623
3624
3625 /* Update the defs in the entry block.  */
3626
3627 void
3628 df_update_entry_block_defs (void)
3629 {
3630   bitmap refs = BITMAP_ALLOC (&df_bitmap_obstack);
3631   bool changed = false;
3632
3633   df_get_entry_block_def_set (refs);
3634   if (df->entry_block_defs)
3635     {
3636       if (!bitmap_equal_p (df->entry_block_defs, refs))
3637         {
3638           struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3639           df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3640           df_ref_chain_delete (bb_info->artificial_defs);
3641           bb_info->artificial_defs = NULL;
3642           changed = true;
3643         }
3644     }
3645   else
3646     {
3647       struct df_scan_problem_data *problem_data
3648         = (struct df_scan_problem_data *) df_scan->problem_data;
3649       df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3650       changed = true;
3651     }
3652
3653   if (changed)
3654     {
3655       df_record_entry_block_defs (refs);
3656       bitmap_copy (df->entry_block_defs, refs);
3657       df_set_bb_dirty (BASIC_BLOCK (ENTRY_BLOCK));
3658     }
3659   BITMAP_FREE (refs);
3660 }
3661
3662
3663 /* Set the bit for regs that are considered being used at the exit. */
3664
3665 static void
3666 df_get_exit_block_use_set (bitmap exit_block_uses)
3667 {
3668   unsigned int i;
3669
3670   bitmap_clear (exit_block_uses);
3671
3672   /* Stack pointer is always live at the exit.  */
3673   bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3674
3675   /* Mark the frame pointer if needed at the end of the function.
3676      If we end up eliminating it, it will be removed from the live
3677      list of each basic block by reload.  */
3678
3679   if ((!reload_completed) || frame_pointer_needed)
3680     {
3681       bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3682 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3683       /* If they are different, also mark the hard frame pointer as live.  */
3684       if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3685         bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3686 #endif
3687     }
3688
3689 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3690   /* Many architectures have a GP register even without flag_pic.
3691      Assume the pic register is not in use, or will be handled by
3692      other means, if it is not fixed.  */
3693   if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3694       && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3695     bitmap_set_bit (exit_block_uses, PIC_OFFSET_TABLE_REGNUM);
3696 #endif
3697
3698   /* Mark all global registers, and all registers used by the
3699      epilogue as being live at the end of the function since they
3700      may be referenced by our caller.  */
3701   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3702     if (global_regs[i] || EPILOGUE_USES (i))
3703       bitmap_set_bit (exit_block_uses, i);
3704
3705   if (HAVE_epilogue && epilogue_completed)
3706     {
3707       /* Mark all call-saved registers that we actually used.  */
3708       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3709         if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3710             && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3711           bitmap_set_bit (exit_block_uses, i);
3712     }
3713
3714 #ifdef EH_RETURN_DATA_REGNO
3715   /* Mark the registers that will contain data for the handler.  */
3716   if (reload_completed && current_function_calls_eh_return)
3717     for (i = 0; ; ++i)
3718       {
3719         unsigned regno = EH_RETURN_DATA_REGNO (i);
3720         if (regno == INVALID_REGNUM)
3721           break;
3722         bitmap_set_bit (exit_block_uses, regno);
3723       }
3724 #endif
3725
3726 #ifdef EH_RETURN_STACKADJ_RTX
3727   if ((!HAVE_epilogue || ! epilogue_completed)
3728       && current_function_calls_eh_return)
3729     {
3730       rtx tmp = EH_RETURN_STACKADJ_RTX;
3731       if (tmp && REG_P (tmp))
3732         df_mark_reg (tmp, exit_block_uses);
3733     }
3734 #endif
3735
3736 #ifdef EH_RETURN_HANDLER_RTX
3737   if ((!HAVE_epilogue || ! epilogue_completed)
3738       && current_function_calls_eh_return)
3739     {
3740       rtx tmp = EH_RETURN_HANDLER_RTX;
3741       if (tmp && REG_P (tmp))
3742         df_mark_reg (tmp, exit_block_uses);
3743     }
3744 #endif
3745
3746   /* Mark function return value.  */
3747   diddle_return_value (df_mark_reg, (void*) exit_block_uses);
3748 }
3749
3750
3751 /* Return the refs of hard registers that are used in the exit block.
3752    It uses df->exit_block_uses to determine register to include.  */
3753
3754 static void
3755 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
3756 {
3757   unsigned int i;
3758   bitmap_iterator bi;
3759
3760   EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
3761     df_ref_record (collection_rec, regno_reg_rtx[i], NULL,
3762                    EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0);
3763
3764 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3765   /* It is deliberate that this is not put in the exit block uses but
3766      I do not know why.  */
3767   if (reload_completed
3768       && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
3769       && bb_has_eh_pred (EXIT_BLOCK_PTR)
3770       && fixed_regs[ARG_POINTER_REGNUM])
3771     df_ref_record (collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
3772                    EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0);
3773 #endif
3774
3775   df_canonize_collection_rec (collection_rec);
3776 }
3777
3778
3779 /* Record the set of hard registers that are used in the exit block.
3780    It uses df->exit_block_uses to determine which bit to include.  */
3781
3782 static void
3783 df_record_exit_block_uses (bitmap exit_block_uses)
3784 {
3785   struct df_collection_rec collection_rec;
3786   memset (&collection_rec, 0, sizeof (struct df_collection_rec));
3787   collection_rec.use_vec = alloca (sizeof (struct df_ref*) * FIRST_PSEUDO_REGISTER);
3788
3789   df_exit_block_uses_collect (&collection_rec, exit_block_uses);
3790
3791   /* Process bb_refs chain */
3792   df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (EXIT_BLOCK), NULL);
3793 }
3794
3795
3796 /* Update the uses in the exit block.  */
3797
3798 void
3799 df_update_exit_block_uses (void)
3800 {
3801   bitmap refs = BITMAP_ALLOC (&df_bitmap_obstack);
3802   bool changed = false;
3803
3804   df_get_exit_block_use_set (refs);
3805   if (df->exit_block_uses)
3806     {
3807       if (!bitmap_equal_p (df->exit_block_uses, refs))
3808         {
3809           struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
3810           df_ref_chain_delete_du_chain (bb_info->artificial_uses);
3811           df_ref_chain_delete (bb_info->artificial_uses);
3812           bb_info->artificial_uses = NULL;
3813           changed = true;
3814         }
3815     }
3816   else
3817     {
3818       struct df_scan_problem_data *problem_data
3819         = (struct df_scan_problem_data *) df_scan->problem_data;
3820       df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3821       changed = true;
3822     }
3823
3824   if (changed)
3825     {
3826       df_record_exit_block_uses (refs);
3827       bitmap_copy (df->exit_block_uses, refs);
3828       df_set_bb_dirty (BASIC_BLOCK (EXIT_BLOCK));
3829     }
3830   BITMAP_FREE (refs);
3831 }
3832
3833 static bool initialized = false;
3834
3835
3836 /* Initialize some platform specific structures.  */
3837
3838 void
3839 df_hard_reg_init (void)
3840 {
3841   int i;
3842 #ifdef ELIMINABLE_REGS
3843   static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
3844 #endif
3845   if (initialized)
3846     return;
3847
3848   bitmap_obstack_initialize (&persistent_obstack);
3849
3850   /* Record which registers will be eliminated.  We use this in
3851      mark_used_regs.  */
3852   CLEAR_HARD_REG_SET (elim_reg_set);
3853
3854 #ifdef ELIMINABLE_REGS
3855   for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3856     SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
3857 #else
3858   SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
3859 #endif
3860
3861   df_invalidated_by_call = BITMAP_ALLOC (&persistent_obstack);
3862
3863   /* Inconveniently, this is only readily available in hard reg set
3864      form.  */
3865   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
3866     if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3867       bitmap_set_bit (df_invalidated_by_call, i);
3868
3869   initialized = true;
3870 }
3871
3872
3873 /* Recompute the parts of scanning that are based on regs_ever_live
3874    because something changed in that array.  */
3875
3876 void
3877 df_update_entry_exit_and_calls (void)
3878 {
3879   basic_block bb;
3880
3881   df_update_entry_block_defs ();
3882   df_update_exit_block_uses ();
3883
3884   /* The call insns need to be rescanned because there may be changes
3885      in the set of registers clobbered across the call.  */
3886   FOR_EACH_BB (bb)
3887     {
3888       rtx insn;
3889       FOR_BB_INSNS (bb, insn)
3890         {
3891           if (INSN_P (insn) && CALL_P (insn))
3892             df_insn_rescan (insn);
3893         }
3894     }
3895 }
3896
3897
3898 /* Return true if hard REG is actually used in the some instruction.
3899    There are a fair number of conditions that affect the setting of
3900    this array.  See the comment in df.h for df->hard_regs_live_count
3901    for the conditions that this array is set. */
3902
3903 bool
3904 df_hard_reg_used_p (unsigned int reg)
3905 {
3906   gcc_assert (df);
3907   return df->hard_regs_live_count[reg] != 0;
3908 }
3909
3910
3911 /* A count of the number of times REG is actually used in the some
3912    instruction.  There are a fair number of conditions that affect the
3913    setting of this array.  See the comment in df.h for
3914    df->hard_regs_live_count for the conditions that this array is
3915    set. */
3916
3917
3918 unsigned int
3919 df_hard_reg_used_count (unsigned int reg)
3920 {
3921   gcc_assert (df);
3922   return df->hard_regs_live_count[reg];
3923 }
3924
3925
3926 /* Get the value of regs_ever_live[REGNO].  */
3927
3928 bool
3929 df_regs_ever_live_p (unsigned int regno)
3930 {
3931   return regs_ever_live[regno];
3932 }
3933
3934
3935 /* Set regs_ever_live[REGNO] to VALUE.  If this cause regs_ever_live
3936    to change, schedule that change for the next update.  */
3937
3938 void
3939 df_set_regs_ever_live (unsigned int regno, bool value)
3940 {
3941   if (regs_ever_live[regno] == value)
3942     return;
3943
3944   regs_ever_live[regno] = value;
3945   if (df)
3946     df->redo_entry_and_exit = true;
3947 }
3948
3949
3950 /* Compute "regs_ever_live" information from the underlying df
3951    information.  Set the vector to all false if RESET.  */
3952
3953 void
3954 df_compute_regs_ever_live (bool reset)
3955 {
3956   unsigned int i;
3957   bool changed = df->redo_entry_and_exit;
3958
3959   if (reset)
3960     memset (regs_ever_live, 0, sizeof (regs_ever_live));
3961
3962   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3963     if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
3964       {
3965         regs_ever_live[i] = true;
3966         changed = true;
3967       }
3968   if (changed)
3969     df_update_entry_exit_and_calls ();
3970   df->redo_entry_and_exit = false;
3971 }
3972
3973 \f
3974 /*----------------------------------------------------------------------------
3975   Dataflow ref information verification functions.
3976
3977   df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3978   df_reg_chain_verify_unmarked (refs)
3979   df_refs_verify (ref*, ref*, bool)
3980   df_mws_verify (mw*, mw*, bool)
3981   df_insn_refs_verify (collection_rec, bb, insn, bool)
3982   df_bb_refs_verify (bb, refs, bool)
3983   df_bb_verify (bb)
3984   df_exit_block_bitmap_verify (bool)
3985   df_entry_block_bitmap_verify (bool)
3986   df_scan_verify ()
3987 ----------------------------------------------------------------------------*/
3988
3989
3990 /* Mark all refs in the reg chain.  Verify that all of the registers
3991 are in the correct chain.  */
3992
3993 static unsigned int
3994 df_reg_chain_mark (struct df_ref *refs, unsigned int regno,
3995                    bool is_def, bool is_eq_use)
3996 {
3997   unsigned int count = 0;
3998   struct df_ref *ref;
3999   for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4000     {
4001       gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4002
4003       /* If there are no def-use or use-def chains, make sure that all
4004          of the chains are clear.  */
4005       if (!df_chain)
4006         gcc_assert (!DF_REF_CHAIN (ref));
4007
4008       /* Check to make sure the ref is in the correct chain.  */
4009       gcc_assert (DF_REF_REGNO (ref) == regno);
4010       if (is_def)
4011         gcc_assert (DF_REF_TYPE(ref) == DF_REF_REG_DEF);
4012       else
4013         gcc_assert (DF_REF_TYPE(ref) != DF_REF_REG_DEF);
4014
4015       if (is_eq_use)
4016         gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
4017       else
4018         gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
4019
4020       if (ref->next_reg)
4021         gcc_assert (ref->next_reg->prev_reg == ref);
4022       count++;
4023       DF_REF_REG_MARK (ref);
4024     }
4025   return count;
4026 }
4027
4028
4029 /* Verify that all of the registers in the chain are unmarked.  */
4030
4031 static void
4032 df_reg_chain_verify_unmarked (struct df_ref *refs)
4033 {
4034   struct df_ref *ref;
4035   for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4036     gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4037 }
4038
4039
4040 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4041
4042 static bool
4043 df_refs_verify (struct df_ref **new_rec, struct df_ref **old_rec,
4044                 bool abort_if_fail)
4045 {
4046   while ((*new_rec) && (*old_rec))
4047     {
4048       if (!df_ref_equal_p (*new_rec, *old_rec))
4049         {
4050           if (abort_if_fail)
4051             gcc_assert (0);
4052           else
4053             return false;
4054         }
4055
4056       /* Abort if fail is called from the function level verifier.  If
4057          that is the context, mark this reg as being seem.  */
4058       if (abort_if_fail)
4059         {
4060           gcc_assert (DF_REF_IS_REG_MARKED (*old_rec));
4061           DF_REF_REG_UNMARK (*old_rec);
4062         }
4063
4064       new_rec++;
4065       old_rec++;
4066     }
4067
4068   if (abort_if_fail)
4069     gcc_assert ((*new_rec == NULL) && (*old_rec == NULL));
4070   else
4071     return ((*new_rec == NULL) && (*old_rec == NULL));
4072   return false;
4073 }
4074
4075
4076 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4077
4078 static bool
4079 df_mws_verify (struct df_mw_hardreg **new_rec, struct df_mw_hardreg **old_rec,
4080                bool abort_if_fail)
4081 {
4082   while ((*new_rec) && (*old_rec))
4083     {
4084       if (!df_mw_equal_p (*new_rec, *old_rec))
4085         {
4086           if (abort_if_fail)
4087             gcc_assert (0);
4088           else
4089             return false;
4090         }
4091       new_rec++;
4092       old_rec++;
4093     }
4094
4095   if (abort_if_fail)
4096     gcc_assert ((*new_rec == NULL) && (*old_rec == NULL));
4097   else
4098     return ((*new_rec == NULL) && (*old_rec == NULL));
4099   return false;
4100 }
4101
4102
4103 /* Return true if the existing insn refs information is complete and
4104    correct. Otherwise (i.e. if there's any missing or extra refs),
4105    return the correct df_ref chain in REFS_RETURN.
4106
4107    If ABORT_IF_FAIL, leave the refs that are verified (already in the
4108    ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4109    verification mode instead of the whole function, so unmark
4110    everything.
4111
4112    If ABORT_IF_FAIL is set, this function never returns false.  */
4113
4114 static bool
4115 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4116                      basic_block bb,
4117                      rtx insn,
4118                      bool abort_if_fail)
4119 {
4120   bool ret1, ret2, ret3, ret4;
4121   unsigned int uid = INSN_UID (insn);
4122
4123   df_insn_refs_collect (collection_rec, bb, insn);
4124
4125   if (!DF_INSN_UID_DEFS (uid))
4126     {
4127       /* The insn_rec was created but it was never filled out.  */
4128       if (abort_if_fail)
4129         gcc_assert (0);
4130       else
4131         return false;
4132     }
4133
4134   /* Unfortunately we cannot opt out early if one of these is not
4135      right because the marks will not get cleared.  */
4136   ret1 = df_refs_verify (collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4137                          abort_if_fail);
4138   ret2 = df_refs_verify (collection_rec->use_vec, DF_INSN_UID_USES (uid),
4139                          abort_if_fail);
4140   ret3 = df_refs_verify (collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4141                          abort_if_fail);
4142   ret4 = df_mws_verify (collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4143                        abort_if_fail);
4144   return (ret1 && ret2 && ret3 && ret4);
4145 }
4146
4147
4148 /* Return true if all refs in the basic block are correct and complete.
4149    Due to df_ref_chain_verify, it will cause all refs
4150    that are verified to have DF_REF_MARK bit set.  */
4151
4152 static bool
4153 df_bb_verify (basic_block bb)
4154 {
4155   rtx insn;
4156   struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4157   struct df_collection_rec collection_rec;
4158
4159   memset (&collection_rec, 0, sizeof (struct df_collection_rec));
4160   collection_rec.def_vec = alloca (sizeof (struct df_ref*) * 1000);
4161   collection_rec.use_vec = alloca (sizeof (struct df_ref*) * 1000);
4162   collection_rec.eq_use_vec = alloca (sizeof (struct df_ref*) * 1000);
4163   collection_rec.mw_vec = alloca (sizeof (struct df_mw_hardreg*) * 100);
4164
4165   gcc_assert (bb_info);
4166
4167   /* Scan the block an insn at a time from beginning to end.  */
4168   FOR_BB_INSNS_REVERSE (bb, insn)
4169     {
4170       if (!INSN_P (insn))
4171         continue;
4172       df_insn_refs_verify (&collection_rec, bb, insn, true);
4173       df_free_collection_rec (&collection_rec);
4174     }
4175
4176   /* Do the artificial defs and uses.  */
4177   df_bb_refs_collect (&collection_rec, bb);
4178   df_refs_verify (collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4179   df_refs_verify (collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4180   df_free_collection_rec (&collection_rec);
4181
4182   return true;
4183 }
4184
4185
4186 /* Returns true if the entry block has correct and complete df_ref set.
4187    If not it either aborts if ABORT_IF_FAIL is true or returns false.  */
4188
4189 static bool
4190 df_entry_block_bitmap_verify (bool abort_if_fail)
4191 {
4192   bitmap entry_block_defs = BITMAP_ALLOC (&df_bitmap_obstack);
4193   bool is_eq;
4194
4195   df_get_entry_block_def_set (entry_block_defs);
4196
4197   is_eq = bitmap_equal_p (entry_block_defs, df->entry_block_defs);
4198
4199   if (!is_eq && abort_if_fail)
4200     {
4201       print_current_pass (stderr);
4202       fprintf (stderr, "entry_block_defs = ");
4203       df_print_regset (stderr, entry_block_defs);
4204       fprintf (stderr, "df->entry_block_defs = ");
4205       df_print_regset (stderr, df->entry_block_defs);
4206       gcc_assert (0);
4207     }
4208
4209   BITMAP_FREE (entry_block_defs);
4210
4211   return is_eq;
4212 }
4213
4214
4215 /* Returns true if the exit block has correct and complete df_ref set.
4216    If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4217
4218 static bool
4219 df_exit_block_bitmap_verify (bool abort_if_fail)
4220 {
4221   bitmap exit_block_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4222   bool is_eq;
4223
4224   df_get_exit_block_use_set (exit_block_uses);
4225
4226   is_eq = bitmap_equal_p (exit_block_uses, df->exit_block_uses);
4227
4228   if (!is_eq && abort_if_fail)
4229     {
4230       print_current_pass (stderr);
4231       fprintf (stderr, "exit_block_uses = ");
4232       df_print_regset (stderr, exit_block_uses);
4233       fprintf (stderr, "df->exit_block_uses = ");
4234       df_print_regset (stderr, df->exit_block_uses);
4235       gcc_assert (0);
4236     }
4237
4238   BITMAP_FREE (exit_block_uses);
4239
4240   return is_eq;
4241 }
4242
4243
4244 /* Return true if df_ref information for all insns in all BLOCKS are
4245    correct and complete.  If BLOCKS is null, all blocks are
4246    checked.  */
4247
4248 void
4249 df_scan_verify (void)
4250 {
4251   unsigned int i;
4252   basic_block bb;
4253   bitmap regular_block_artificial_uses;
4254   bitmap eh_block_artificial_uses;
4255
4256   if (!df)
4257     return;
4258
4259   /* Verification is a 4 step process. */
4260
4261   /* (1) All of the refs are marked by going thru the reg chains.  */
4262   for (i = 0; i < DF_REG_SIZE (df); i++)
4263     {
4264       gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4265                   == DF_REG_DEF_COUNT(i));
4266       gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4267                   == DF_REG_USE_COUNT(i));
4268       gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4269                   == DF_REG_EQ_USE_COUNT(i));
4270     }
4271
4272   /* (2) There are various bitmaps whose value may change over the
4273      course of the compilation.  This step recomputes them to make
4274      sure that they have not slipped out of date.  */
4275   regular_block_artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4276   eh_block_artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4277
4278   df_get_regular_block_artificial_uses (regular_block_artificial_uses);
4279   df_get_eh_block_artificial_uses (eh_block_artificial_uses);
4280
4281   bitmap_ior_into (eh_block_artificial_uses,
4282                    regular_block_artificial_uses);
4283
4284   /* Check artificial_uses bitmaps didn't change. */
4285   gcc_assert (bitmap_equal_p (regular_block_artificial_uses,
4286                               df->regular_block_artificial_uses));
4287   gcc_assert (bitmap_equal_p (eh_block_artificial_uses,
4288                               df->eh_block_artificial_uses));
4289
4290   BITMAP_FREE (regular_block_artificial_uses);
4291   BITMAP_FREE (eh_block_artificial_uses);
4292
4293   /* Verify entry block and exit block. These only verify the bitmaps,
4294      the refs are verified in df_bb_verify.  */
4295   df_entry_block_bitmap_verify (true);
4296   df_exit_block_bitmap_verify (true);
4297
4298   /* (3) All of the insns in all of the blocks are traversed and the
4299      marks are cleared both in the artificial refs attached to the
4300      blocks and the real refs inside the insns.  It is a failure to
4301      clear a mark that has not been set as this means that the ref in
4302      the block or insn was not in the reg chain.  */
4303
4304   FOR_ALL_BB (bb)
4305     df_bb_verify (bb);
4306
4307   /* (4) See if all reg chains are traversed a second time.  This time
4308      a check is made that the marks are clear. A set mark would be a
4309      from a reg that is not in any insn or basic block.  */
4310
4311   for (i = 0; i < DF_REG_SIZE (df); i++)
4312     {
4313       df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4314       df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4315       df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));
4316     }
4317 }