gcc/df-scan.c

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