OSDN Git Service

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