gcc/df-scan.c

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