OSDN Git Service

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