contrib/gcc-5.0/gcc/df-scan.c

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