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