* df-scan.c (persistent_obstack, df_invalidated_by_call): Remove.
[people/mcb30/gcc/.git] / gcc / df-problems.c
1 /* Standard problems for dataflow support routines.
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 "df.h"
44 #include "except.h"
45 #include "dce.h"
46 #include "vecprim.h"
47
48 /* Note that turning REG_DEAD_DEBUGGING on will cause
49    gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
50    addresses in the dumps.  */  
51 #if 0
52 #define REG_DEAD_DEBUGGING
53 #endif
54
55 #define DF_SPARSE_THRESHOLD 32
56
57 static bitmap seen_in_block = NULL;
58 static bitmap seen_in_insn = NULL;
59
60 \f
61 /*----------------------------------------------------------------------------
62    Public functions access functions for the dataflow problems.
63 ----------------------------------------------------------------------------*/
64 /* Get the live at out set for BB no matter what problem happens to be
65    defined.  This function is used by the register allocators who
66    choose different dataflow problems depending on the optimization
67    level.  */
68
69 bitmap
70 df_get_live_out (basic_block bb)
71 {
72   gcc_assert (df_lr);
73
74   if (df_live)
75     return DF_LIVE_OUT (bb);
76   else 
77     return DF_LR_OUT (bb);
78 }
79
80 /* Get the live at in set for BB no matter what problem happens to be
81    defined.  This function is used by the register allocators who
82    choose different dataflow problems depending on the optimization
83    level.  */
84
85 bitmap
86 df_get_live_in (basic_block bb)
87 {
88   gcc_assert (df_lr);
89
90   if (df_live)
91     return DF_LIVE_IN (bb);
92   else 
93     return DF_LR_IN (bb);
94 }
95
96 /*----------------------------------------------------------------------------
97    Utility functions.
98 ----------------------------------------------------------------------------*/
99
100 /* Generic versions to get the void* version of the block info.  Only
101    used inside the problem instance vectors.  */
102
103 /* Grow the bb_info array.  */
104
105 void
106 df_grow_bb_info (struct dataflow *dflow)
107 {
108   unsigned int new_size = last_basic_block + 1;
109   if (dflow->block_info_size < new_size)
110     {
111       new_size += new_size / 4;
112       dflow->block_info = XRESIZEVEC (void *, dflow->block_info, new_size);
113       memset (dflow->block_info + dflow->block_info_size, 0,
114               (new_size - dflow->block_info_size) *sizeof (void *));
115       dflow->block_info_size = new_size;
116     }
117 }
118
119 /* Dump a def-use or use-def chain for REF to FILE.  */
120
121 void
122 df_chain_dump (struct df_link *link, FILE *file)
123 {
124   fprintf (file, "{ ");
125   for (; link; link = link->next)
126     {
127       fprintf (file, "%c%d(bb %d insn %d) ",
128                DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
129                DF_REF_ID (link->ref),
130                DF_REF_BBNO (link->ref),
131                DF_REF_IS_ARTIFICIAL (link->ref) ? -1 : DF_REF_INSN_UID (link->ref));
132     }
133   fprintf (file, "}");
134 }
135
136
137 /* Print some basic block info as part of df_dump.  */
138
139 void 
140 df_print_bb_index (basic_block bb, FILE *file)
141 {
142   edge e;
143   edge_iterator ei;
144
145   fprintf (file, "\n( ");
146     FOR_EACH_EDGE (e, ei, bb->preds)
147     {
148       basic_block pred = e->src;
149       fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
150     } 
151   fprintf (file, ")->[%d]->( ", bb->index);
152   FOR_EACH_EDGE (e, ei, bb->succs)
153     {
154       basic_block succ = e->dest;
155       fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
156     } 
157   fprintf (file, ")\n");
158 }
159
160
161
162 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
163    up correctly. */
164
165 static void
166 df_set_seen (void)
167 {
168   seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
169   seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
170 }
171
172
173 static void
174 df_unset_seen (void)
175 {
176   BITMAP_FREE (seen_in_block);
177   BITMAP_FREE (seen_in_insn);
178 }
179
180
181 \f
182 /*----------------------------------------------------------------------------
183    REACHING DEFINITIONS
184
185    Find the locations in the function where each definition site for a
186    pseudo reaches.  In and out bitvectors are built for each basic
187    block.  The id field in the ref is used to index into these sets.
188    See df.h for details.
189    ----------------------------------------------------------------------------*/
190
191 /* This problem plays a large number of games for the sake of
192    efficiency.  
193    
194    1) The order of the bits in the bitvectors.  After the scanning
195    phase, all of the defs are sorted.  All of the defs for the reg 0
196    are first, followed by all defs for reg 1 and so on.
197    
198    2) There are two kill sets, one if the number of defs is less or
199    equal to DF_SPARSE_THRESHOLD and another if the number of defs is
200    greater.
201
202    <= : Data is built directly in the kill set.
203
204    > : One level of indirection is used to keep from generating long
205    strings of 1 bits in the kill sets.  Bitvectors that are indexed
206    by the regnum are used to represent that there is a killing def
207    for the register.  The confluence and transfer functions use
208    these along with the bitmap_clear_range call to remove ranges of
209    bits without actually generating a knockout vector.
210
211    The kill and sparse_kill and the dense_invalidated_by_call and
212    sparse_invalidated_by_call both play this game.  */
213
214 /* Private data used to compute the solution for this problem.  These
215    data structures are not accessible outside of this module.  */
216 struct df_rd_problem_data
217 {
218   /* The set of defs to regs invalidated by call.  */
219   bitmap sparse_invalidated_by_call;  
220   /* The set of defs to regs invalidate by call for rd.  */  
221   bitmap dense_invalidated_by_call;
222   /* An obstack for the bitmaps we need for this problem.  */
223   bitmap_obstack rd_bitmaps;
224 };
225
226 /* Set basic block info.  */
227
228 static void
229 df_rd_set_bb_info (unsigned int index, 
230                    struct df_rd_bb_info *bb_info)
231 {
232   gcc_assert (df_rd);
233   gcc_assert (index < df_rd->block_info_size);
234   df_rd->block_info[index] = bb_info;
235 }
236
237
238 /* Free basic block info.  */
239
240 static void
241 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
242                     void *vbb_info)
243 {
244   struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
245   if (bb_info)
246     {
247       BITMAP_FREE (bb_info->kill);
248       BITMAP_FREE (bb_info->sparse_kill);
249       BITMAP_FREE (bb_info->gen);
250       BITMAP_FREE (bb_info->in);
251       BITMAP_FREE (bb_info->out);
252       pool_free (df_rd->block_pool, bb_info);
253     }
254 }
255
256
257 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
258    not touched unless the block is new.  */
259
260 static void 
261 df_rd_alloc (bitmap all_blocks)
262 {
263   unsigned int bb_index;
264   bitmap_iterator bi;
265   struct df_rd_problem_data *problem_data;
266
267   if (!df_rd->block_pool)
268     df_rd->block_pool = create_alloc_pool ("df_rd_block pool", 
269                                            sizeof (struct df_rd_bb_info), 50);
270
271   if (df_rd->problem_data)
272     {
273       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
274       bitmap_clear (problem_data->sparse_invalidated_by_call);
275       bitmap_clear (problem_data->dense_invalidated_by_call);
276     }
277   else 
278     {
279       problem_data = XNEW (struct df_rd_problem_data);
280       df_rd->problem_data = problem_data;
281
282       bitmap_obstack_initialize (&problem_data->rd_bitmaps);
283       problem_data->sparse_invalidated_by_call
284         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
285       problem_data->dense_invalidated_by_call
286         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
287     }
288
289   df_grow_bb_info (df_rd);
290
291   /* Because of the clustering of all use sites for the same pseudo,
292      we have to process all of the blocks before doing the
293      analysis.  */
294
295   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
296     {
297       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
298       if (bb_info)
299         { 
300           bitmap_clear (bb_info->kill);
301           bitmap_clear (bb_info->sparse_kill);
302           bitmap_clear (bb_info->gen);
303         }
304       else
305         { 
306           bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
307           df_rd_set_bb_info (bb_index, bb_info);
308           bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
309           bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
310           bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
311           bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
312           bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
313         }
314     }
315   df_rd->optional_p = true;
316 }
317
318
319 /* Process a list of DEFs for df_rd_bb_local_compute.  */
320
321 static void
322 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info, 
323                                     df_ref *def_rec,
324                                     enum df_ref_flags top_flag)
325 {
326   while (*def_rec)
327     {
328       df_ref def = *def_rec;
329       if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
330         {
331           unsigned int regno = DF_REF_REGNO (def);
332           unsigned int begin = DF_DEFS_BEGIN (regno);
333           unsigned int n_defs = DF_DEFS_COUNT (regno);
334           
335           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
336               || (regno >= FIRST_PSEUDO_REGISTER))
337             {
338               /* Only the last def(s) for a regno in the block has any
339                  effect.  */ 
340               if (!bitmap_bit_p (seen_in_block, regno))
341                 {
342                   /* The first def for regno in insn gets to knock out the
343                      defs from other instructions.  */
344                   if ((!bitmap_bit_p (seen_in_insn, regno))
345                       /* If the def is to only part of the reg, it does
346                          not kill the other defs that reach here.  */
347                       && (!(DF_REF_FLAGS (def) & 
348                             (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
349                     {
350                       if (n_defs > DF_SPARSE_THRESHOLD)
351                         {
352                           bitmap_set_bit (bb_info->sparse_kill, regno);
353                           bitmap_clear_range(bb_info->gen, begin, n_defs);
354                         }
355                       else
356                         {
357                           bitmap_set_range (bb_info->kill, begin, n_defs);
358                           bitmap_clear_range (bb_info->gen, begin, n_defs);
359                         }
360                     }
361                   
362                   bitmap_set_bit (seen_in_insn, regno);
363                   /* All defs for regno in the instruction may be put into
364                      the gen set.  */
365                   if (!(DF_REF_FLAGS (def) 
366                         & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
367                     bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
368                 }
369             }
370         }
371       def_rec++;
372     }
373 }
374
375 /* Compute local reaching def info for basic block BB.  */
376
377 static void
378 df_rd_bb_local_compute (unsigned int bb_index)
379 {
380   basic_block bb = BASIC_BLOCK (bb_index);
381   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
382   rtx insn;
383
384   bitmap_clear (seen_in_block);
385   bitmap_clear (seen_in_insn);
386
387   /* Artificials are only hard regs.  */
388   if (!(df->changeable_flags & DF_NO_HARD_REGS))
389     df_rd_bb_local_compute_process_def (bb_info, 
390                                         df_get_artificial_defs (bb_index),
391                                         0);
392
393   FOR_BB_INSNS_REVERSE (bb, insn)
394     {
395       unsigned int uid = INSN_UID (insn);
396
397       if (!INSN_P (insn))
398         continue;
399
400       df_rd_bb_local_compute_process_def (bb_info, 
401                                           DF_INSN_UID_DEFS (uid), 0);
402
403       /* This complex dance with the two bitmaps is required because
404          instructions can assign twice to the same pseudo.  This
405          generally happens with calls that will have one def for the
406          result and another def for the clobber.  If only one vector
407          is used and the clobber goes first, the result will be
408          lost.  */
409       bitmap_ior_into (seen_in_block, seen_in_insn);
410       bitmap_clear (seen_in_insn);
411     }
412
413   /* Process the artificial defs at the top of the block last since we
414      are going backwards through the block and these are logically at
415      the start.  */
416   if (!(df->changeable_flags & DF_NO_HARD_REGS))
417     df_rd_bb_local_compute_process_def (bb_info, 
418                                         df_get_artificial_defs (bb_index),
419                                         DF_REF_AT_TOP);
420 }
421
422
423 /* Compute local reaching def info for each basic block within BLOCKS.  */
424
425 static void
426 df_rd_local_compute (bitmap all_blocks)
427 {
428   unsigned int bb_index;
429   bitmap_iterator bi;
430   unsigned int regno;
431   struct df_rd_problem_data *problem_data
432     = (struct df_rd_problem_data *) df_rd->problem_data;
433   bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
434   bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
435
436   df_set_seen ();
437
438   df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
439
440   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
441     {
442       df_rd_bb_local_compute (bb_index);
443     }
444   
445   /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
446   EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi)
447     {
448       if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
449         bitmap_set_bit (sparse_invalidated, regno);
450       else
451         bitmap_set_range (dense_invalidated, 
452                           DF_DEFS_BEGIN (regno), 
453                           DF_DEFS_COUNT (regno));
454     }
455   df_unset_seen ();
456 }
457
458
459 /* Initialize the solution bit vectors for problem.  */
460
461 static void 
462 df_rd_init_solution (bitmap all_blocks)
463 {
464   unsigned int bb_index;
465   bitmap_iterator bi;
466
467   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
468     {
469       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
470       
471       bitmap_copy (bb_info->out, bb_info->gen);
472       bitmap_clear (bb_info->in);
473     }
474 }
475
476 /* In of target gets or of out of source.  */
477
478 static void
479 df_rd_confluence_n (edge e)
480 {
481   bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
482   bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
483
484   if (e->flags & EDGE_FAKE) 
485     return;
486
487   if (e->flags & EDGE_EH)
488     {
489       struct df_rd_problem_data *problem_data
490         = (struct df_rd_problem_data *) df_rd->problem_data;
491       bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
492       bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
493       bitmap_iterator bi;
494       unsigned int regno;
495       bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
496
497       bitmap_copy (tmp, op2);
498       bitmap_and_compl_into (tmp, dense_invalidated);
499
500       EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
501         {
502           bitmap_clear_range (tmp, 
503                               DF_DEFS_BEGIN (regno), 
504                               DF_DEFS_COUNT (regno));
505         }
506       bitmap_ior_into (op1, tmp);
507       BITMAP_FREE (tmp);
508     }
509   else
510     bitmap_ior_into (op1, op2);
511 }
512
513
514 /* Transfer function.  */
515
516 static bool
517 df_rd_transfer_function (int bb_index)
518 {
519   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
520   unsigned int regno;
521   bitmap_iterator bi;
522   bitmap in = bb_info->in;
523   bitmap out = bb_info->out;
524   bitmap gen = bb_info->gen;
525   bitmap kill = bb_info->kill;
526   bitmap sparse_kill = bb_info->sparse_kill;
527
528   if (bitmap_empty_p (sparse_kill))
529     return  bitmap_ior_and_compl (out, gen, in, kill);
530   else 
531     {
532       struct df_rd_problem_data *problem_data;
533       bool changed = false;
534       bitmap tmp;
535
536       /* Note that TMP is _not_ a temporary bitmap if we end up replacing
537          OUT with TMP.  Therefore, allocate TMP in the RD bitmaps obstack.  */
538       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
539       tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
540
541       bitmap_copy (tmp, in);
542       EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
543         {
544           bitmap_clear_range (tmp, 
545                               DF_DEFS_BEGIN (regno), 
546                               DF_DEFS_COUNT (regno));
547         }
548       bitmap_and_compl_into (tmp, kill);
549       bitmap_ior_into (tmp, gen);
550       changed = !bitmap_equal_p (tmp, out);
551       if (changed)
552         {
553           BITMAP_FREE (out);
554           bb_info->out = tmp;
555         }
556       else 
557           BITMAP_FREE (tmp);
558       return changed;
559     }
560 }
561
562
563 /* Free all storage associated with the problem.  */
564
565 static void
566 df_rd_free (void)
567 {
568   struct df_rd_problem_data *problem_data
569     = (struct df_rd_problem_data *) df_rd->problem_data;
570
571   if (problem_data)
572     {
573       free_alloc_pool (df_rd->block_pool);
574       bitmap_obstack_release (&problem_data->rd_bitmaps);
575       
576       df_rd->block_info_size = 0;
577       free (df_rd->block_info);
578       free (df_rd->problem_data);
579     }
580   free (df_rd);
581 }
582
583
584 /* Debugging info.  */
585
586 static void
587 df_rd_start_dump (FILE *file)
588 {
589   struct df_rd_problem_data *problem_data
590     = (struct df_rd_problem_data *) df_rd->problem_data;
591   unsigned int m = DF_REG_SIZE(df);
592   unsigned int regno;
593   
594   if (!df_rd->block_info) 
595     return;
596
597   fprintf (file, ";; Reaching defs:\n\n");
598
599   fprintf (file, "  sparse invalidated \t");
600   dump_bitmap (file, problem_data->sparse_invalidated_by_call);
601   fprintf (file, "  dense invalidated \t");
602   dump_bitmap (file, problem_data->dense_invalidated_by_call);
603
604   for (regno = 0; regno < m; regno++)
605     if (DF_DEFS_COUNT (regno))
606       fprintf (file, "%d[%d,%d] ", regno, 
607                DF_DEFS_BEGIN (regno), 
608                DF_DEFS_COUNT (regno));
609   fprintf (file, "\n");
610
611 }
612
613
614 /* Debugging info at top of bb.  */
615
616 static void
617 df_rd_top_dump (basic_block bb, FILE *file)
618 {
619   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
620   if (!bb_info || !bb_info->in)
621     return;
622   
623   fprintf (file, ";; rd  in  \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
624   dump_bitmap (file, bb_info->in);
625   fprintf (file, ";; rd  gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
626   dump_bitmap (file, bb_info->gen);
627   fprintf (file, ";; rd  kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
628   dump_bitmap (file, bb_info->kill);
629 }
630
631
632 /* Debugging info at top of bb.  */
633
634 static void
635 df_rd_bottom_dump (basic_block bb, FILE *file)
636 {
637   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
638   if (!bb_info || !bb_info->out)
639     return;
640   
641   fprintf (file, ";; rd  out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
642   dump_bitmap (file, bb_info->out);
643 }
644
645 /* All of the information associated with every instance of the problem.  */
646
647 static struct df_problem problem_RD =
648 {
649   DF_RD,                      /* Problem id.  */
650   DF_FORWARD,                 /* Direction.  */
651   df_rd_alloc,                /* Allocate the problem specific data.  */
652   NULL,                       /* Reset global information.  */
653   df_rd_free_bb_info,         /* Free basic block info.  */
654   df_rd_local_compute,        /* Local compute function.  */
655   df_rd_init_solution,        /* Init the solution specific data.  */
656   df_worklist_dataflow,       /* Worklist solver.  */
657   NULL,                       /* Confluence operator 0.  */ 
658   df_rd_confluence_n,         /* Confluence operator n.  */ 
659   df_rd_transfer_function,    /* Transfer function.  */
660   NULL,                       /* Finalize function.  */
661   df_rd_free,                 /* Free all of the problem information.  */
662   df_rd_free,                 /* Remove this problem from the stack of dataflow problems.  */
663   df_rd_start_dump,           /* Debugging.  */
664   df_rd_top_dump,             /* Debugging start block.  */
665   df_rd_bottom_dump,          /* Debugging end block.  */
666   NULL,                       /* Incremental solution verify start.  */
667   NULL,                       /* Incremental solution verify end.  */
668   NULL,                       /* Dependent problem.  */
669   TV_DF_RD,                   /* Timing variable.  */ 
670   true                        /* Reset blocks on dropping out of blocks_to_analyze.  */
671 };
672
673
674
675 /* Create a new DATAFLOW instance and add it to an existing instance
676    of DF.  The returned structure is what is used to get at the
677    solution.  */
678
679 void
680 df_rd_add_problem (void)
681 {
682   df_add_problem (&problem_RD);
683 }
684
685
686 \f
687 /*----------------------------------------------------------------------------
688    LIVE REGISTERS
689
690    Find the locations in the function where any use of a pseudo can
691    reach in the backwards direction.  In and out bitvectors are built
692    for each basic block.  The regno is used to index into these sets.
693    See df.h for details.
694    ----------------------------------------------------------------------------*/
695
696 /* Private data used to verify the solution for this problem.  */
697 struct df_lr_problem_data
698 {
699   bitmap *in;
700   bitmap *out;
701 };
702
703
704 /* Set basic block info.  */
705
706 static void
707 df_lr_set_bb_info (unsigned int index, 
708                    struct df_lr_bb_info *bb_info)
709 {
710   gcc_assert (df_lr);
711   gcc_assert (index < df_lr->block_info_size);
712   df_lr->block_info[index] = bb_info;
713 }
714
715  
716 /* Free basic block info.  */
717
718 static void
719 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
720                     void *vbb_info)
721 {
722   struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
723   if (bb_info)
724     {
725       BITMAP_FREE (bb_info->use);
726       BITMAP_FREE (bb_info->def);
727       BITMAP_FREE (bb_info->in);
728       BITMAP_FREE (bb_info->out);
729       pool_free (df_lr->block_pool, bb_info);
730     }
731 }
732
733
734 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
735    not touched unless the block is new.  */
736
737 static void 
738 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
739 {
740   unsigned int bb_index;
741   bitmap_iterator bi;
742
743   if (!df_lr->block_pool)
744     df_lr->block_pool = create_alloc_pool ("df_lr_block pool", 
745                                            sizeof (struct df_lr_bb_info), 50);
746
747   df_grow_bb_info (df_lr);
748
749   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
750     {
751       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
752       if (bb_info)
753         { 
754           bitmap_clear (bb_info->def);
755           bitmap_clear (bb_info->use);
756         }
757       else
758         { 
759           bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
760           df_lr_set_bb_info (bb_index, bb_info);
761           bb_info->use = BITMAP_ALLOC (NULL);
762           bb_info->def = BITMAP_ALLOC (NULL);
763           bb_info->in = BITMAP_ALLOC (NULL);
764           bb_info->out = BITMAP_ALLOC (NULL);
765         }
766     }
767
768   df_lr->optional_p = false;
769 }
770
771
772 /* Reset the global solution for recalculation.  */
773
774 static void 
775 df_lr_reset (bitmap all_blocks)
776 {
777   unsigned int bb_index;
778   bitmap_iterator bi;
779
780   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
781     {
782       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
783       gcc_assert (bb_info);
784       bitmap_clear (bb_info->in);
785       bitmap_clear (bb_info->out);
786     }
787 }
788
789
790 /* Compute local live register info for basic block BB.  */
791
792 static void
793 df_lr_bb_local_compute (unsigned int bb_index)
794 {
795   basic_block bb = BASIC_BLOCK (bb_index);
796   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
797   rtx insn;
798   df_ref *def_rec;
799   df_ref *use_rec;
800
801   /* Process the registers set in an exception handler.  */
802   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
803     {
804       df_ref def = *def_rec;
805       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
806         {
807           unsigned int dregno = DF_REF_REGNO (def);
808           bitmap_set_bit (bb_info->def, dregno);
809           bitmap_clear_bit (bb_info->use, dregno);
810         }
811     }
812
813   /* Process the hardware registers that are always live.  */
814   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
815     {
816       df_ref use = *use_rec;
817       /* Add use to set of uses in this BB.  */
818       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
819         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
820     }
821
822   FOR_BB_INSNS_REVERSE (bb, insn)
823     {
824       unsigned int uid = INSN_UID (insn);
825
826       if (!INSN_P (insn))
827         continue;       
828
829       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
830         {
831           df_ref def = *def_rec;
832           /* If the def is to only part of the reg, it does
833              not kill the other defs that reach here.  */
834           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
835             {
836               unsigned int dregno = DF_REF_REGNO (def);
837               bitmap_set_bit (bb_info->def, dregno);
838               bitmap_clear_bit (bb_info->use, dregno);
839             }
840         }
841
842       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
843         {
844           df_ref use = *use_rec;
845           /* Add use to set of uses in this BB.  */
846           bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
847         }
848     }
849
850   /* Process the registers set in an exception handler or the hard
851      frame pointer if this block is the target of a non local
852      goto.  */
853   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
854     {
855       df_ref def = *def_rec;
856       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
857         {
858           unsigned int dregno = DF_REF_REGNO (def);
859           bitmap_set_bit (bb_info->def, dregno);
860           bitmap_clear_bit (bb_info->use, dregno);
861         }
862     }
863   
864 #ifdef EH_USES
865   /* Process the uses that are live into an exception handler.  */
866   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
867     {
868       df_ref use = *use_rec;
869       /* Add use to set of uses in this BB.  */
870       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
871         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
872     }
873 #endif
874
875   /* If the df_live problem is not defined, such as at -O0 and -O1, we
876      still need to keep the luids up to date.  This is normally done
877      in the df_live problem since this problem has a forwards
878      scan.  */
879   if (!df_live)
880     df_recompute_luids (bb);
881 }
882
883
884 /* Compute local live register info for each basic block within BLOCKS.  */
885
886 static void
887 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
888 {
889   unsigned int bb_index;
890   bitmap_iterator bi;
891     
892   bitmap_clear (df->hardware_regs_used);
893   
894   /* The all-important stack pointer must always be live.  */
895   bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
896   
897   /* Before reload, there are a few registers that must be forced
898      live everywhere -- which might not already be the case for
899      blocks within infinite loops.  */
900   if (!reload_completed)
901     {
902       /* Any reference to any pseudo before reload is a potential
903          reference of the frame pointer.  */
904       bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
905       
906 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
907       /* Pseudos with argument area equivalences may require
908          reloading via the argument pointer.  */
909       if (fixed_regs[ARG_POINTER_REGNUM])
910         bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
911 #endif
912       
913       /* Any constant, or pseudo with constant equivalences, may
914          require reloading from memory using the pic register.  */
915       if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
916           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
917         bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
918     }
919   
920   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
921     {
922       if (bb_index == EXIT_BLOCK)
923         {
924           /* The exit block is special for this problem and its bits are
925              computed from thin air.  */
926           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
927           bitmap_copy (bb_info->use, df->exit_block_uses);
928         }
929       else
930         df_lr_bb_local_compute (bb_index);
931     }
932
933   bitmap_clear (df_lr->out_of_date_transfer_functions);
934 }
935
936
937 /* Initialize the solution vectors.  */
938
939 static void 
940 df_lr_init (bitmap all_blocks)
941 {
942   unsigned int bb_index;
943   bitmap_iterator bi;
944
945   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
946     {
947       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
948       bitmap_copy (bb_info->in, bb_info->use);
949       bitmap_clear (bb_info->out);
950     }
951 }
952
953
954 /* Confluence function that processes infinite loops.  This might be a
955    noreturn function that throws.  And even if it isn't, getting the
956    unwind info right helps debugging.  */
957 static void
958 df_lr_confluence_0 (basic_block bb)
959 {
960   bitmap op1 = df_lr_get_bb_info (bb->index)->out;
961   if (bb != EXIT_BLOCK_PTR)
962     bitmap_copy (op1, df->hardware_regs_used);
963
964
965
966 /* Confluence function that ignores fake edges.  */
967
968 static void
969 df_lr_confluence_n (edge e)
970 {
971   bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
972   bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
973  
974   /* Call-clobbered registers die across exception and call edges.  */
975   /* ??? Abnormal call edges ignored for the moment, as this gets
976      confused by sibling call edges, which crashes reg-stack.  */
977   if (e->flags & EDGE_EH)
978     bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
979   else
980     bitmap_ior_into (op1, op2);
981
982   bitmap_ior_into (op1, df->hardware_regs_used);
983
984
985
986 /* Transfer function.  */
987
988 static bool
989 df_lr_transfer_function (int bb_index)
990 {
991   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
992   bitmap in = bb_info->in;
993   bitmap out = bb_info->out;
994   bitmap use = bb_info->use;
995   bitmap def = bb_info->def;
996
997   return bitmap_ior_and_compl (in, use, out, def);
998 }
999
1000
1001 /* Run the fast dce as a side effect of building LR.  */
1002
1003 static void
1004 df_lr_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
1005 {
1006   if (df->changeable_flags & DF_LR_RUN_DCE)
1007     {
1008       run_fast_df_dce ();
1009       if (df_lr->problem_data && df_lr->solutions_dirty)
1010         {
1011           /* If we are here, then it is because we are both verifying
1012           the solution and the dce changed the function.  In that case
1013           the verification info built will be wrong.  So we leave the
1014           dirty flag true so that the verifier will skip the checking
1015           part and just clean up.*/
1016           df_lr->solutions_dirty = true;
1017         }
1018       else
1019         df_lr->solutions_dirty = false;
1020     }
1021   else
1022     df_lr->solutions_dirty = false;
1023 }
1024
1025
1026 /* Free all storage associated with the problem.  */
1027
1028 static void
1029 df_lr_free (void)
1030 {
1031   if (df_lr->block_info)
1032     {
1033       unsigned int i;
1034       for (i = 0; i < df_lr->block_info_size; i++)
1035         {
1036           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
1037           if (bb_info)
1038             {
1039               BITMAP_FREE (bb_info->use);
1040               BITMAP_FREE (bb_info->def);
1041               BITMAP_FREE (bb_info->in);
1042               BITMAP_FREE (bb_info->out);
1043             }
1044         }
1045       free_alloc_pool (df_lr->block_pool);
1046       
1047       df_lr->block_info_size = 0;
1048       free (df_lr->block_info);
1049     }
1050
1051   BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1052   free (df_lr);
1053 }
1054
1055
1056 /* Debugging info at top of bb.  */
1057
1058 static void
1059 df_lr_top_dump (basic_block bb, FILE *file)
1060 {
1061   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1062   struct df_lr_problem_data *problem_data;
1063   if (!bb_info || !bb_info->in)
1064     return;
1065       
1066   fprintf (file, ";; lr  in  \t");
1067   df_print_regset (file, bb_info->in);
1068   if (df_lr->problem_data)
1069     {
1070       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1071       fprintf (file, ";;  old in  \t");
1072       df_print_regset (file, problem_data->in[bb->index]);
1073     }
1074   fprintf (file, ";; lr  use \t");
1075   df_print_regset (file, bb_info->use);
1076   fprintf (file, ";; lr  def \t");
1077   df_print_regset (file, bb_info->def);
1078 }  
1079
1080
1081 /* Debugging info at bottom of bb.  */
1082
1083 static void
1084 df_lr_bottom_dump (basic_block bb, FILE *file)
1085 {
1086   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1087   struct df_lr_problem_data *problem_data;
1088   if (!bb_info || !bb_info->out)
1089     return;
1090   
1091   fprintf (file, ";; lr  out \t");
1092   df_print_regset (file, bb_info->out);
1093   if (df_lr->problem_data)
1094     {
1095       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1096       fprintf (file, ";;  old out  \t");
1097       df_print_regset (file, problem_data->out[bb->index]);
1098     }
1099 }  
1100
1101
1102 /* Build the datastructure to verify that the solution to the dataflow
1103    equations is not dirty.  */
1104
1105 static void
1106 df_lr_verify_solution_start (void)
1107 {
1108   basic_block bb;
1109   struct df_lr_problem_data *problem_data;
1110   if (df_lr->solutions_dirty)
1111     {
1112       df_lr->problem_data = NULL;
1113       return;
1114     }
1115
1116   /* Set it true so that the solution is recomputed.  */ 
1117   df_lr->solutions_dirty = true;
1118
1119   problem_data = XNEW (struct df_lr_problem_data);
1120   df_lr->problem_data = problem_data;
1121   problem_data->in = XNEWVEC (bitmap, last_basic_block);
1122   problem_data->out = XNEWVEC (bitmap, last_basic_block);
1123
1124   FOR_ALL_BB (bb)
1125     {
1126       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1127       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1128       bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1129       bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1130     }
1131 }
1132
1133
1134 /* Compare the saved datastructure and the new solution to the dataflow
1135    equations.  */
1136
1137 static void
1138 df_lr_verify_solution_end (void)
1139 {
1140   struct df_lr_problem_data *problem_data;
1141   basic_block bb;
1142
1143   if (df_lr->problem_data == NULL)
1144     return;
1145
1146   problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1147
1148   if (df_lr->solutions_dirty)
1149     /* Do not check if the solution is still dirty.  See the comment
1150        in df_lr_finalize for details.  */
1151     df_lr->solutions_dirty = false;
1152   else
1153     FOR_ALL_BB (bb)
1154       {
1155         if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1156             || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1157           {
1158             /*df_dump (stderr);*/
1159             gcc_unreachable ();
1160           }
1161       }
1162
1163   /* Cannot delete them immediately because you may want to dump them
1164      if the comparison fails.  */
1165   FOR_ALL_BB (bb)
1166     {
1167       BITMAP_FREE (problem_data->in[bb->index]);
1168       BITMAP_FREE (problem_data->out[bb->index]);
1169     }
1170
1171   free (problem_data->in);
1172   free (problem_data->out);
1173   free (problem_data);
1174   df_lr->problem_data = NULL;
1175 }
1176
1177
1178 /* All of the information associated with every instance of the problem.  */
1179
1180 static struct df_problem problem_LR =
1181 {
1182   DF_LR,                      /* Problem id.  */
1183   DF_BACKWARD,                /* Direction.  */
1184   df_lr_alloc,                /* Allocate the problem specific data.  */
1185   df_lr_reset,                /* Reset global information.  */
1186   df_lr_free_bb_info,         /* Free basic block info.  */
1187   df_lr_local_compute,        /* Local compute function.  */
1188   df_lr_init,                 /* Init the solution specific data.  */
1189   df_worklist_dataflow,       /* Worklist solver.  */
1190   df_lr_confluence_0,         /* Confluence operator 0.  */ 
1191   df_lr_confluence_n,         /* Confluence operator n.  */ 
1192   df_lr_transfer_function,    /* Transfer function.  */
1193   df_lr_finalize,             /* Finalize function.  */
1194   df_lr_free,                 /* Free all of the problem information.  */
1195   NULL,                       /* Remove this problem from the stack of dataflow problems.  */
1196   NULL,                       /* Debugging.  */
1197   df_lr_top_dump,             /* Debugging start block.  */
1198   df_lr_bottom_dump,          /* Debugging end block.  */
1199   df_lr_verify_solution_start,/* Incremental solution verify start.  */
1200   df_lr_verify_solution_end,  /* Incremental solution verify end.  */
1201   NULL,                       /* Dependent problem.  */
1202   TV_DF_LR,                   /* Timing variable.  */ 
1203   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
1204 };
1205
1206
1207 /* Create a new DATAFLOW instance and add it to an existing instance
1208    of DF.  The returned structure is what is used to get at the
1209    solution.  */
1210
1211 void
1212 df_lr_add_problem (void)
1213 {
1214   df_add_problem (&problem_LR);
1215   /* These will be initialized when df_scan_blocks processes each
1216      block.  */
1217   df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1218 }
1219
1220
1221 /* Verify that all of the lr related info is consistent and
1222    correct.  */
1223
1224 void
1225 df_lr_verify_transfer_functions (void)
1226 {
1227   basic_block bb;
1228   bitmap saved_def;
1229   bitmap saved_use;
1230   bitmap saved_adef;
1231   bitmap saved_ause;
1232   bitmap all_blocks;
1233
1234   if (!df)
1235     return;
1236
1237   saved_def = BITMAP_ALLOC (NULL);
1238   saved_use = BITMAP_ALLOC (NULL);
1239   saved_adef = BITMAP_ALLOC (NULL);
1240   saved_ause = BITMAP_ALLOC (NULL);
1241   all_blocks = BITMAP_ALLOC (NULL);
1242
1243   FOR_ALL_BB (bb)
1244     {
1245       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1246       bitmap_set_bit (all_blocks, bb->index);
1247
1248       if (bb_info)
1249         {
1250           /* Make a copy of the transfer functions and then compute
1251              new ones to see if the transfer functions have
1252              changed.  */
1253           if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions, 
1254                              bb->index))
1255             {
1256               bitmap_copy (saved_def, bb_info->def);
1257               bitmap_copy (saved_use, bb_info->use);
1258               bitmap_clear (bb_info->def);
1259               bitmap_clear (bb_info->use);
1260
1261               df_lr_bb_local_compute (bb->index);
1262               gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1263               gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
1264             }
1265         }
1266       else
1267         {
1268           /* If we do not have basic block info, the block must be in
1269              the list of dirty blocks or else some one has added a
1270              block behind our backs. */
1271           gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions, 
1272                                     bb->index));
1273         }
1274       /* Make sure no one created a block without following
1275          procedures.  */
1276       gcc_assert (df_scan_get_bb_info (bb->index));
1277     }
1278
1279   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1280   gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions, 
1281                                          all_blocks)); 
1282
1283   BITMAP_FREE (saved_def);
1284   BITMAP_FREE (saved_use);
1285   BITMAP_FREE (saved_adef);
1286   BITMAP_FREE (saved_ause);
1287   BITMAP_FREE (all_blocks);
1288 }
1289
1290
1291 \f
1292 /*----------------------------------------------------------------------------
1293    LIVE AND MUST-INITIALIZED REGISTERS.
1294
1295    This problem first computes the IN and OUT bitvectors for the
1296    must-initialized registers problems, which is a forward problem.
1297    It gives the set of registers for which we MUST have an available
1298    definition on any path from the entry block to the entry/exit of
1299    a basic block.  Sets generate a definition, while clobbers kill
1300    a definition.
1301
1302    In and out bitvectors are built for each basic block and are indexed by
1303    regnum (see df.h for details).  In and out bitvectors in struct
1304    df_live_bb_info actually refers to the must-initialized problem;
1305
1306    Then, the in and out sets for the LIVE problem itself are computed.
1307    These are the logical AND of the IN and OUT sets from the LR problem
1308    and the must-initialized problem. 
1309 ----------------------------------------------------------------------------*/
1310
1311 /* Private data used to verify the solution for this problem.  */
1312 struct df_live_problem_data
1313 {
1314   bitmap *in;
1315   bitmap *out;
1316 };
1317
1318 /* Scratch var used by transfer functions.  This is used to implement
1319    an optimization to reduce the amount of space used to compute the
1320    combined lr and live analysis.  */
1321 static bitmap df_live_scratch;
1322
1323 /* Set basic block info.  */
1324
1325 static void
1326 df_live_set_bb_info (unsigned int index, 
1327                    struct df_live_bb_info *bb_info)
1328 {
1329   gcc_assert (df_live);
1330   gcc_assert (index < df_live->block_info_size);
1331   df_live->block_info[index] = bb_info;
1332 }
1333
1334
1335 /* Free basic block info.  */
1336
1337 static void
1338 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
1339                     void *vbb_info)
1340 {
1341   struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1342   if (bb_info)
1343     {
1344       BITMAP_FREE (bb_info->gen);
1345       BITMAP_FREE (bb_info->kill);
1346       BITMAP_FREE (bb_info->in);
1347       BITMAP_FREE (bb_info->out);
1348       pool_free (df_live->block_pool, bb_info);
1349     }
1350 }
1351
1352
1353 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1354    not touched unless the block is new.  */
1355
1356 static void 
1357 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1358 {
1359   unsigned int bb_index;
1360   bitmap_iterator bi;
1361
1362   if (!df_live->block_pool)
1363     df_live->block_pool = create_alloc_pool ("df_live_block pool", 
1364                                            sizeof (struct df_live_bb_info), 100);
1365   if (!df_live_scratch)
1366     df_live_scratch = BITMAP_ALLOC (NULL);
1367
1368   df_grow_bb_info (df_live);
1369
1370   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1371     {
1372       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1373       if (bb_info)
1374         { 
1375           bitmap_clear (bb_info->kill);
1376           bitmap_clear (bb_info->gen);
1377         }
1378       else
1379         { 
1380           bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1381           df_live_set_bb_info (bb_index, bb_info);
1382           bb_info->kill = BITMAP_ALLOC (NULL);
1383           bb_info->gen = BITMAP_ALLOC (NULL);
1384           bb_info->in = BITMAP_ALLOC (NULL);
1385           bb_info->out = BITMAP_ALLOC (NULL);
1386         }
1387     }
1388   df_live->optional_p = (optimize <= 1);
1389 }
1390
1391
1392 /* Reset the global solution for recalculation.  */
1393
1394 static void 
1395 df_live_reset (bitmap all_blocks)
1396 {
1397   unsigned int bb_index;
1398   bitmap_iterator bi;
1399
1400   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1401     {
1402       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1403       gcc_assert (bb_info);
1404       bitmap_clear (bb_info->in);
1405       bitmap_clear (bb_info->out);
1406     }
1407 }
1408
1409
1410 /* Compute local uninitialized register info for basic block BB.  */
1411
1412 static void
1413 df_live_bb_local_compute (unsigned int bb_index)
1414 {
1415   basic_block bb = BASIC_BLOCK (bb_index);
1416   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1417   rtx insn;
1418   df_ref *def_rec;
1419   int luid = 0;
1420
1421   FOR_BB_INSNS (bb, insn)
1422     {
1423       unsigned int uid = INSN_UID (insn);
1424       struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1425
1426       /* Inserting labels does not always trigger the incremental
1427          rescanning.  */
1428       if (!insn_info)
1429         {
1430           gcc_assert (!INSN_P (insn));
1431           insn_info = df_insn_create_insn_record (insn);
1432         }
1433
1434       DF_INSN_INFO_LUID (insn_info) = luid;
1435       if (!INSN_P (insn))
1436         continue;
1437
1438       luid++;
1439       for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)
1440         {
1441           df_ref def = *def_rec;
1442           unsigned int regno = DF_REF_REGNO (def);
1443
1444           if (DF_REF_FLAGS_IS_SET (def,
1445                                    DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1446             /* All partial or conditional def
1447                seen are included in the gen set. */
1448             bitmap_set_bit (bb_info->gen, regno);
1449           else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1450             /* Only must clobbers for the entire reg destroy the
1451                value.  */
1452             bitmap_set_bit (bb_info->kill, regno);
1453           else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1454             bitmap_set_bit (bb_info->gen, regno);
1455         }
1456     }
1457
1458   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1459     {
1460       df_ref def = *def_rec;
1461       bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
1462     }
1463 }
1464
1465
1466 /* Compute local uninitialized register info.  */
1467
1468 static void
1469 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1470 {
1471   unsigned int bb_index;
1472   bitmap_iterator bi;
1473
1474   df_grow_insn_info ();
1475
1476   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 
1477                             0, bb_index, bi)
1478     {
1479       df_live_bb_local_compute (bb_index);
1480     }
1481
1482   bitmap_clear (df_live->out_of_date_transfer_functions);
1483 }
1484
1485
1486 /* Initialize the solution vectors.  */
1487
1488 static void 
1489 df_live_init (bitmap all_blocks)
1490 {
1491   unsigned int bb_index;
1492   bitmap_iterator bi;
1493
1494   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1495     {
1496       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1497       struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1498
1499       /* No register may reach a location where it is not used.  Thus
1500          we trim the rr result to the places where it is used.  */
1501       bitmap_and (bb_info->out, bb_info->gen, bb_lr_info->out);
1502       bitmap_clear (bb_info->in);
1503     }
1504 }
1505
1506 /* Forward confluence function that ignores fake edges.  */
1507
1508 static void
1509 df_live_confluence_n (edge e)
1510 {
1511   bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
1512   bitmap op2 = df_live_get_bb_info (e->src->index)->out;
1513  
1514   if (e->flags & EDGE_FAKE) 
1515     return;
1516
1517   bitmap_ior_into (op1, op2);
1518
1519
1520
1521 /* Transfer function for the forwards must-initialized problem.  */
1522
1523 static bool
1524 df_live_transfer_function (int bb_index)
1525 {
1526   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1527   struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1528   bitmap in = bb_info->in;
1529   bitmap out = bb_info->out;
1530   bitmap gen = bb_info->gen;
1531   bitmap kill = bb_info->kill;
1532
1533   /* We need to use a scratch set here so that the value returned from
1534      this function invocation properly reflects if the sets changed in
1535      a significant way; i.e. not just because the lr set was anded
1536      in.  */
1537   bitmap_and (df_live_scratch, gen, bb_lr_info->out);
1538   /* No register may reach a location where it is not used.  Thus
1539      we trim the rr result to the places where it is used.  */
1540   bitmap_and_into (in, bb_lr_info->in);
1541
1542   return bitmap_ior_and_compl (out, df_live_scratch, in, kill);
1543 }
1544
1545
1546 /* And the LR info with the must-initialized registers, to produce the LIVE info.  */
1547
1548 static void
1549 df_live_finalize (bitmap all_blocks)
1550 {
1551
1552   if (df_live->solutions_dirty)
1553     {
1554       bitmap_iterator bi;
1555       unsigned int bb_index;
1556
1557       EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1558         {
1559           struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1560           struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1561   
1562           /* No register may reach a location where it is not used.  Thus
1563              we trim the rr result to the places where it is used.  */
1564           bitmap_and_into (bb_live_info->in, bb_lr_info->in);
1565           bitmap_and_into (bb_live_info->out, bb_lr_info->out);
1566         }
1567       
1568       df_live->solutions_dirty = false;
1569     }
1570 }
1571
1572
1573 /* Free all storage associated with the problem.  */
1574
1575 static void
1576 df_live_free (void)
1577 {
1578   if (df_live->block_info)
1579     {
1580       unsigned int i;
1581       
1582       for (i = 0; i < df_live->block_info_size; i++)
1583         {
1584           struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
1585           if (bb_info)
1586             {
1587               BITMAP_FREE (bb_info->gen);
1588               BITMAP_FREE (bb_info->kill);
1589               BITMAP_FREE (bb_info->in);
1590               BITMAP_FREE (bb_info->out);
1591             }
1592         }
1593       
1594       free_alloc_pool (df_live->block_pool);
1595       df_live->block_info_size = 0;
1596       free (df_live->block_info);
1597
1598       if (df_live_scratch)
1599         BITMAP_FREE (df_live_scratch);
1600     }
1601   BITMAP_FREE (df_live->out_of_date_transfer_functions);
1602   free (df_live);
1603 }
1604
1605
1606 /* Debugging info at top of bb.  */
1607
1608 static void
1609 df_live_top_dump (basic_block bb, FILE *file)
1610 {
1611   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1612   struct df_live_problem_data *problem_data;
1613
1614   if (!bb_info || !bb_info->in)
1615     return;
1616       
1617   fprintf (file, ";; live  in  \t");
1618   df_print_regset (file, bb_info->in);
1619   if (df_live->problem_data)
1620     {
1621       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1622       fprintf (file, ";;  old in  \t");
1623       df_print_regset (file, problem_data->in[bb->index]);
1624     }
1625   fprintf (file, ";; live  gen \t");
1626   df_print_regset (file, bb_info->gen);
1627   fprintf (file, ";; live  kill\t");
1628   df_print_regset (file, bb_info->kill);
1629 }
1630
1631
1632 /* Debugging info at bottom of bb.  */
1633
1634 static void
1635 df_live_bottom_dump (basic_block bb, FILE *file)
1636 {
1637   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1638   struct df_live_problem_data *problem_data;
1639
1640   if (!bb_info || !bb_info->out)
1641     return;
1642       
1643   fprintf (file, ";; live  out \t");
1644   df_print_regset (file, bb_info->out);
1645   if (df_live->problem_data)
1646     {
1647       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1648       fprintf (file, ";;  old out  \t");
1649       df_print_regset (file, problem_data->out[bb->index]);
1650     }
1651 }
1652
1653
1654 /* Build the datastructure to verify that the solution to the dataflow
1655    equations is not dirty.  */
1656
1657 static void
1658 df_live_verify_solution_start (void)
1659 {
1660   basic_block bb;
1661   struct df_live_problem_data *problem_data;
1662   if (df_live->solutions_dirty)
1663     {
1664       df_live->problem_data = NULL;
1665       return;
1666     }
1667
1668   /* Set it true so that the solution is recomputed.  */ 
1669   df_live->solutions_dirty = true;
1670
1671   problem_data = XNEW (struct df_live_problem_data);
1672   df_live->problem_data = problem_data;
1673   problem_data->in = XNEWVEC (bitmap, last_basic_block);
1674   problem_data->out = XNEWVEC (bitmap, last_basic_block);
1675
1676   FOR_ALL_BB (bb)
1677     {
1678       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1679       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1680       bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
1681       bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
1682     }
1683 }
1684
1685
1686 /* Compare the saved datastructure and the new solution to the dataflow
1687    equations.  */
1688
1689 static void
1690 df_live_verify_solution_end (void)
1691 {
1692   struct df_live_problem_data *problem_data;
1693   basic_block bb;
1694
1695   if (df_live->problem_data == NULL)
1696     return;
1697
1698   problem_data = (struct df_live_problem_data *)df_live->problem_data;
1699
1700   FOR_ALL_BB (bb)
1701     {
1702       if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
1703           || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1704         {
1705           /*df_dump (stderr);*/
1706           gcc_unreachable ();
1707         }
1708     }
1709
1710   /* Cannot delete them immediately because you may want to dump them
1711      if the comparison fails.  */
1712   FOR_ALL_BB (bb)
1713     {
1714       BITMAP_FREE (problem_data->in[bb->index]);
1715       BITMAP_FREE (problem_data->out[bb->index]);
1716     }
1717
1718   free (problem_data->in);
1719   free (problem_data->out);
1720   free (problem_data);
1721   df_live->problem_data = NULL;
1722 }
1723
1724
1725 /* All of the information associated with every instance of the problem.  */
1726
1727 static struct df_problem problem_LIVE =
1728 {
1729   DF_LIVE,                      /* Problem id.  */
1730   DF_FORWARD,                   /* Direction.  */
1731   df_live_alloc,                /* Allocate the problem specific data.  */
1732   df_live_reset,                /* Reset global information.  */
1733   df_live_free_bb_info,         /* Free basic block info.  */
1734   df_live_local_compute,        /* Local compute function.  */
1735   df_live_init,                 /* Init the solution specific data.  */
1736   df_worklist_dataflow,         /* Worklist solver.  */
1737   NULL,                         /* Confluence operator 0.  */ 
1738   df_live_confluence_n,         /* Confluence operator n.  */ 
1739   df_live_transfer_function,    /* Transfer function.  */
1740   df_live_finalize,             /* Finalize function.  */
1741   df_live_free,                 /* Free all of the problem information.  */
1742   df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
1743   NULL,                         /* Debugging.  */
1744   df_live_top_dump,             /* Debugging start block.  */
1745   df_live_bottom_dump,          /* Debugging end block.  */
1746   df_live_verify_solution_start,/* Incremental solution verify start.  */
1747   df_live_verify_solution_end,  /* Incremental solution verify end.  */
1748   &problem_LR,                  /* Dependent problem.  */
1749   TV_DF_LIVE,                   /* Timing variable.  */
1750   false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
1751 };
1752
1753
1754 /* Create a new DATAFLOW instance and add it to an existing instance
1755    of DF.  The returned structure is what is used to get at the
1756    solution.  */
1757
1758 void
1759 df_live_add_problem (void)
1760 {
1761   df_add_problem (&problem_LIVE);
1762   /* These will be initialized when df_scan_blocks processes each
1763      block.  */
1764   df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1765 }
1766
1767
1768 /* Set all of the blocks as dirty.  This needs to be done if this
1769    problem is added after all of the insns have been scanned.  */
1770
1771 void
1772 df_live_set_all_dirty (void)
1773 {
1774   basic_block bb;
1775   FOR_ALL_BB (bb)
1776     bitmap_set_bit (df_live->out_of_date_transfer_functions, 
1777                     bb->index);
1778 }
1779
1780
1781 /* Verify that all of the lr related info is consistent and
1782    correct.  */
1783
1784 void
1785 df_live_verify_transfer_functions (void)
1786 {
1787   basic_block bb;
1788   bitmap saved_gen;
1789   bitmap saved_kill;
1790   bitmap all_blocks;
1791
1792   if (!df)
1793     return;
1794
1795   saved_gen = BITMAP_ALLOC (NULL);
1796   saved_kill = BITMAP_ALLOC (NULL);
1797   all_blocks = BITMAP_ALLOC (NULL);
1798
1799   df_grow_insn_info ();
1800
1801   FOR_ALL_BB (bb)
1802     {
1803       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1804       bitmap_set_bit (all_blocks, bb->index);
1805
1806       if (bb_info)
1807         {
1808           /* Make a copy of the transfer functions and then compute
1809              new ones to see if the transfer functions have
1810              changed.  */
1811           if (!bitmap_bit_p (df_live->out_of_date_transfer_functions, 
1812                              bb->index))
1813             {
1814               bitmap_copy (saved_gen, bb_info->gen);
1815               bitmap_copy (saved_kill, bb_info->kill);
1816               bitmap_clear (bb_info->gen);
1817               bitmap_clear (bb_info->kill);
1818
1819               df_live_bb_local_compute (bb->index);
1820               gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
1821               gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
1822             }
1823         }
1824       else
1825         {
1826           /* If we do not have basic block info, the block must be in
1827              the list of dirty blocks or else some one has added a
1828              block behind our backs. */
1829           gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions, 
1830                                     bb->index));
1831         }
1832       /* Make sure no one created a block without following
1833          procedures.  */
1834       gcc_assert (df_scan_get_bb_info (bb->index));
1835     }
1836
1837   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1838   gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions, 
1839                                          all_blocks)); 
1840   BITMAP_FREE (saved_gen);
1841   BITMAP_FREE (saved_kill);
1842   BITMAP_FREE (all_blocks);
1843 }
1844 \f
1845 /*----------------------------------------------------------------------------
1846    CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1847
1848    Link either the defs to the uses and / or the uses to the defs.
1849
1850    These problems are set up like the other dataflow problems so that
1851    they nicely fit into the framework.  They are much simpler and only
1852    involve a single traversal of instructions and an examination of
1853    the reaching defs information (the dependent problem).
1854 ----------------------------------------------------------------------------*/
1855
1856 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1857
1858 /* Create a du or ud chain from SRC to DST and link it into SRC.   */
1859
1860 struct df_link *
1861 df_chain_create (df_ref src, df_ref dst)
1862 {
1863   struct df_link *head = DF_REF_CHAIN (src);
1864   struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool);
1865   
1866   DF_REF_CHAIN (src) = link;
1867   link->next = head;
1868   link->ref = dst;
1869   return link;
1870 }
1871
1872
1873 /* Delete any du or ud chains that start at REF and point to
1874    TARGET.  */ 
1875 static void
1876 df_chain_unlink_1 (df_ref ref, df_ref target)
1877 {
1878   struct df_link *chain = DF_REF_CHAIN (ref);
1879   struct df_link *prev = NULL;
1880
1881   while (chain)
1882     {
1883       if (chain->ref == target)
1884         {
1885           if (prev)
1886             prev->next = chain->next;
1887           else
1888             DF_REF_CHAIN (ref) = chain->next;
1889           pool_free (df_chain->block_pool, chain);
1890           return;
1891         }
1892       prev = chain;
1893       chain = chain->next;
1894     }
1895 }
1896
1897
1898 /* Delete a du or ud chain that leave or point to REF.  */
1899
1900 void
1901 df_chain_unlink (df_ref ref)
1902 {
1903   struct df_link *chain = DF_REF_CHAIN (ref);
1904   while (chain)
1905     {
1906       struct df_link *next = chain->next;
1907       /* Delete the other side if it exists.  */
1908       df_chain_unlink_1 (chain->ref, ref);
1909       pool_free (df_chain->block_pool, chain);
1910       chain = next;
1911     }
1912   DF_REF_CHAIN (ref) = NULL;
1913 }
1914
1915
1916 /* Copy the du or ud chain starting at FROM_REF and attach it to
1917    TO_REF.  */ 
1918
1919 void 
1920 df_chain_copy (df_ref to_ref, 
1921                struct df_link *from_ref)
1922 {
1923   while (from_ref)
1924     {
1925       df_chain_create (to_ref, from_ref->ref);
1926       from_ref = from_ref->next;
1927     }
1928 }
1929
1930
1931 /* Remove this problem from the stack of dataflow problems.  */
1932
1933 static void
1934 df_chain_remove_problem (void)
1935 {
1936   bitmap_iterator bi;
1937   unsigned int bb_index;
1938
1939   /* Wholesale destruction of the old chains.  */ 
1940   if (df_chain->block_pool)
1941     free_alloc_pool (df_chain->block_pool);
1942
1943   EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1944     {
1945       rtx insn;
1946       df_ref *def_rec;
1947       df_ref *use_rec;
1948       basic_block bb = BASIC_BLOCK (bb_index);
1949
1950       if (df_chain_problem_p (DF_DU_CHAIN))
1951         for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1952           DF_REF_CHAIN (*def_rec) = NULL;
1953       if (df_chain_problem_p (DF_UD_CHAIN))
1954         for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
1955           DF_REF_CHAIN (*use_rec) = NULL;
1956       
1957       FOR_BB_INSNS (bb, insn)
1958         {
1959           unsigned int uid = INSN_UID (insn);
1960           
1961           if (INSN_P (insn))
1962             {
1963               if (df_chain_problem_p (DF_DU_CHAIN))
1964                 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1965                   DF_REF_CHAIN (*def_rec) = NULL;
1966               if (df_chain_problem_p (DF_UD_CHAIN))
1967                 {
1968                   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1969                     DF_REF_CHAIN (*use_rec) = NULL;
1970                   for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1971                     DF_REF_CHAIN (*use_rec) = NULL;
1972                 }
1973             }
1974         }
1975     }
1976
1977   bitmap_clear (df_chain->out_of_date_transfer_functions);
1978   df_chain->block_pool = NULL;
1979 }
1980
1981
1982 /* Remove the chain problem completely.  */
1983
1984 static void
1985 df_chain_fully_remove_problem (void)
1986 {
1987   df_chain_remove_problem ();
1988   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
1989   free (df_chain);
1990 }
1991
1992
1993 /* Create def-use or use-def chains.  */
1994
1995 static void  
1996 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1997 {
1998   df_chain_remove_problem ();
1999   df_chain->block_pool = create_alloc_pool ("df_chain_block pool", 
2000                                          sizeof (struct df_link), 50);
2001   df_chain->optional_p = true;
2002 }
2003
2004
2005 /* Reset all of the chains when the set of basic blocks changes.  */
2006
2007 static void
2008 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2009 {
2010   df_chain_remove_problem ();
2011 }
2012
2013
2014 /* Create the chains for a list of USEs.  */
2015
2016 static void
2017 df_chain_create_bb_process_use (bitmap local_rd,
2018                                 df_ref *use_rec,
2019                                 enum df_ref_flags top_flag)
2020 {
2021   bitmap_iterator bi;
2022   unsigned int def_index;
2023   
2024   while (*use_rec)
2025     {
2026       df_ref use = *use_rec;
2027       unsigned int uregno = DF_REF_REGNO (use);
2028       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2029           || (uregno >= FIRST_PSEUDO_REGISTER))
2030         {
2031           /* Do not want to go through this for an uninitialized var.  */
2032           int count = DF_DEFS_COUNT (uregno);
2033           if (count)
2034             {
2035               if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2036                 {
2037                   unsigned int first_index = DF_DEFS_BEGIN (uregno);
2038                   unsigned int last_index = first_index + count - 1;
2039                   
2040                   EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2041                     {
2042                       df_ref def;
2043                       if (def_index > last_index) 
2044                         break;
2045                       
2046                       def = DF_DEFS_GET (def_index);
2047                       if (df_chain_problem_p (DF_DU_CHAIN))
2048                         df_chain_create (def, use);
2049                       if (df_chain_problem_p (DF_UD_CHAIN))
2050                         df_chain_create (use, def);
2051                     }
2052                 }
2053             }
2054         }
2055
2056       use_rec++;
2057     }
2058 }
2059
2060
2061 /* Create chains from reaching defs bitmaps for basic block BB.  */
2062
2063 static void
2064 df_chain_create_bb (unsigned int bb_index)
2065 {
2066   basic_block bb = BASIC_BLOCK (bb_index);
2067   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2068   rtx insn;
2069   bitmap cpy = BITMAP_ALLOC (NULL);
2070   df_ref *def_rec;
2071
2072   bitmap_copy (cpy, bb_info->in);
2073   bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2074
2075   /* Since we are going forwards, process the artificial uses first
2076      then the artificial defs second.  */
2077
2078 #ifdef EH_USES
2079   /* Create the chains for the artificial uses from the EH_USES at the
2080      beginning of the block.  */
2081   
2082   /* Artificials are only hard regs.  */
2083   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2084     df_chain_create_bb_process_use (cpy,
2085                                     df_get_artificial_uses (bb->index), 
2086                                     DF_REF_AT_TOP);
2087 #endif
2088
2089   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2090     {
2091       df_ref def = *def_rec;
2092       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2093         {
2094           unsigned int dregno = DF_REF_REGNO (def);
2095           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2096             bitmap_clear_range (cpy, 
2097                                 DF_DEFS_BEGIN (dregno), 
2098                                 DF_DEFS_COUNT (dregno));
2099           bitmap_set_bit (cpy, DF_REF_ID (def));
2100         }
2101     }
2102   
2103   /* Process the regular instructions next.  */
2104   FOR_BB_INSNS (bb, insn)
2105     {
2106       df_ref *def_rec;
2107       unsigned int uid = INSN_UID (insn);
2108
2109       if (!INSN_P (insn))
2110         continue;
2111
2112       /* Now scan the uses and link them up with the defs that remain
2113          in the cpy vector.  */
2114       
2115       df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
2116
2117       if (df->changeable_flags & DF_EQ_NOTES)
2118         df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
2119
2120
2121       /* Since we are going forwards, process the defs second.  This
2122          pass only changes the bits in cpy.  */
2123       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2124         {
2125           df_ref def = *def_rec;
2126           unsigned int dregno = DF_REF_REGNO (def);
2127           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2128               || (dregno >= FIRST_PSEUDO_REGISTER))
2129             {
2130               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2131                 bitmap_clear_range (cpy, 
2132                                     DF_DEFS_BEGIN (dregno), 
2133                                     DF_DEFS_COUNT (dregno));
2134               if (!(DF_REF_FLAGS (def) 
2135                     & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
2136                 bitmap_set_bit (cpy, DF_REF_ID (def));
2137             }
2138         }
2139     }
2140
2141   /* Create the chains for the artificial uses of the hard registers
2142      at the end of the block.  */
2143   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2144     df_chain_create_bb_process_use (cpy,
2145                                     df_get_artificial_uses (bb->index), 
2146                                     0);
2147
2148   BITMAP_FREE (cpy);
2149 }
2150
2151 /* Create def-use chains from reaching use bitmaps for basic blocks
2152    in BLOCKS.  */
2153
2154 static void
2155 df_chain_finalize (bitmap all_blocks)
2156 {
2157   unsigned int bb_index;
2158   bitmap_iterator bi;
2159   
2160   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2161     {
2162       df_chain_create_bb (bb_index);
2163     }
2164 }
2165
2166
2167 /* Free all storage associated with the problem.  */
2168
2169 static void
2170 df_chain_free (void)
2171 {
2172   free_alloc_pool (df_chain->block_pool);
2173   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2174   free (df_chain);
2175 }
2176
2177
2178 /* Debugging info.  */
2179
2180 static void
2181 df_chain_top_dump (basic_block bb, FILE *file)
2182 {
2183   if (df_chain_problem_p (DF_DU_CHAIN))
2184     {
2185       rtx insn;
2186       df_ref *def_rec = df_get_artificial_defs (bb->index);
2187       if (*def_rec)
2188         {
2189           
2190           fprintf (file, ";;  DU chains for artificial defs\n");
2191           while (*def_rec)
2192             {
2193               df_ref def = *def_rec;
2194               fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
2195               df_chain_dump (DF_REF_CHAIN (def), file);
2196               fprintf (file, "\n");
2197               def_rec++;
2198             }
2199         }      
2200
2201       FOR_BB_INSNS (bb, insn)
2202         {
2203           if (INSN_P (insn))
2204             {
2205               struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2206               def_rec = DF_INSN_INFO_DEFS (insn_info);
2207               if (*def_rec)
2208                 {
2209                   fprintf (file, ";;   DU chains for insn luid %d uid %d\n", 
2210                            DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2211                   
2212                   while (*def_rec)
2213                     {
2214                       df_ref def = *def_rec;
2215                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
2216                       if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2217                         fprintf (file, "read/write ");
2218                       df_chain_dump (DF_REF_CHAIN (def), file);
2219                       fprintf (file, "\n");
2220                       def_rec++;
2221                     }
2222                 }
2223             }
2224         }
2225     }
2226 }
2227
2228
2229 static void
2230 df_chain_bottom_dump (basic_block bb, FILE *file)
2231 {
2232   if (df_chain_problem_p (DF_UD_CHAIN))
2233     {
2234       rtx insn;
2235       df_ref *use_rec = df_get_artificial_uses (bb->index);
2236
2237       if (*use_rec)
2238         {
2239           fprintf (file, ";;  UD chains for artificial uses\n");
2240           while (*use_rec)
2241             {
2242               df_ref use = *use_rec;
2243               fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
2244               df_chain_dump (DF_REF_CHAIN (use), file);
2245               fprintf (file, "\n");
2246               use_rec++;
2247             }
2248         }      
2249
2250       FOR_BB_INSNS (bb, insn)
2251         {
2252           if (INSN_P (insn))
2253             {
2254               struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2255               df_ref *eq_use_rec = DF_INSN_INFO_EQ_USES (insn_info);
2256               use_rec = DF_INSN_INFO_USES (insn_info);
2257               if (*use_rec || *eq_use_rec)
2258                 {
2259                   fprintf (file, ";;   UD chains for insn luid %d uid %d\n", 
2260                            DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2261                   
2262                   while (*use_rec)
2263                     {
2264                       df_ref use = *use_rec;
2265                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
2266                       if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2267                         fprintf (file, "read/write ");
2268                       df_chain_dump (DF_REF_CHAIN (use), file);
2269                       fprintf (file, "\n");
2270                       use_rec++;
2271                     }
2272                   while (*eq_use_rec)
2273                     {
2274                       df_ref use = *eq_use_rec;
2275                       fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
2276                       df_chain_dump (DF_REF_CHAIN (use), file);
2277                       fprintf (file, "\n");
2278                       eq_use_rec++;
2279                     }
2280                 }
2281             }
2282         }
2283     }
2284 }
2285
2286
2287 static struct df_problem problem_CHAIN =
2288 {
2289   DF_CHAIN,                   /* Problem id.  */
2290   DF_NONE,                    /* Direction.  */
2291   df_chain_alloc,             /* Allocate the problem specific data.  */
2292   df_chain_reset,             /* Reset global information.  */
2293   NULL,                       /* Free basic block info.  */
2294   NULL,                       /* Local compute function.  */
2295   NULL,                       /* Init the solution specific data.  */
2296   NULL,                       /* Iterative solver.  */
2297   NULL,                       /* Confluence operator 0.  */ 
2298   NULL,                       /* Confluence operator n.  */ 
2299   NULL,                       /* Transfer function.  */
2300   df_chain_finalize,          /* Finalize function.  */
2301   df_chain_free,              /* Free all of the problem information.  */
2302   df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
2303   NULL,                       /* Debugging.  */
2304   df_chain_top_dump,          /* Debugging start block.  */
2305   df_chain_bottom_dump,       /* Debugging end block.  */
2306   NULL,                       /* Incremental solution verify start.  */
2307   NULL,                       /* Incremental solution verify end.  */
2308   &problem_RD,                /* Dependent problem.  */
2309   TV_DF_CHAIN,                /* Timing variable.  */
2310   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2311 };
2312
2313
2314 /* Create a new DATAFLOW instance and add it to an existing instance
2315    of DF.  The returned structure is what is used to get at the
2316    solution.  */
2317
2318 void
2319 df_chain_add_problem (enum df_chain_flags chain_flags)
2320 {
2321   df_add_problem (&problem_CHAIN);
2322   df_chain->local_flags = (unsigned int)chain_flags;
2323   df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2324 }
2325
2326 #undef df_chain_problem_p
2327
2328 \f
2329 /*----------------------------------------------------------------------------
2330    BYTE LEVEL LIVE REGISTERS
2331
2332    Find the locations in the function where any use of a pseudo can
2333    reach in the backwards direction.  In and out bitvectors are built
2334    for each basic block.  There are two mapping functions,
2335    df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are
2336    used to map regnos into bit vector positions.
2337
2338    This problem differs from the regular df_lr function in the way
2339    that subregs, *_extracts and strict_low_parts are handled. In lr
2340    these are consider partial kills, here, the exact set of bytes is
2341    modeled.  Note that any reg that has none of these operations is
2342    only modeled with a single bit since all operations access the
2343    entire register.
2344
2345    This problem is more brittle that the regular lr.  It currently can
2346    be used in dce incrementally, but cannot be used in an environment
2347    where insns are created or modified.  The problem is that the
2348    mapping of regnos to bitmap positions is relatively compact, in
2349    that if a pseudo does not do any of the byte wise operations, only
2350    one slot is allocated, rather than a slot for each byte.  If insn
2351    are created, where a subreg is used for a reg that had no subregs,
2352    the mapping would be wrong.  Likewise, there are no checks to see
2353    that new pseudos have been added.  These issues could be addressed
2354    by adding a problem specific flag to not use the compact mapping,
2355    if there was a need to do so.
2356
2357    ----------------------------------------------------------------------------*/
2358
2359 /* Private data used to verify the solution for this problem.  */
2360 struct df_byte_lr_problem_data
2361 {
2362   /* Expanded versions of bitvectors used in lr.  */
2363   bitmap invalidated_by_call;
2364   bitmap hardware_regs_used;
2365
2366   /* Indexed by regno, this is true if there are subregs, extracts or
2367      strict_low_parts for this regno.  */
2368   bitmap needs_expansion;
2369
2370   /* The start position and len for each regno in the various bit
2371      vectors.  */ 
2372   unsigned int* regno_start;  
2373   unsigned int* regno_len;
2374   /* An obstack for the bitmaps we need for this problem.  */
2375   bitmap_obstack byte_lr_bitmaps;
2376 };
2377
2378
2379 /* Get the starting location for REGNO in the df_byte_lr bitmaps.  */
2380
2381 int 
2382 df_byte_lr_get_regno_start (unsigned int regno)
2383 {
2384   struct df_byte_lr_problem_data *problem_data 
2385     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2386   return problem_data->regno_start[regno];
2387 }
2388
2389
2390 /* Get the len for REGNO in the df_byte_lr bitmaps.  */
2391
2392 int 
2393 df_byte_lr_get_regno_len (unsigned int regno)
2394 {  
2395   struct df_byte_lr_problem_data *problem_data 
2396     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2397   return problem_data->regno_len[regno];
2398 }
2399
2400
2401 /* Set basic block info.  */
2402
2403 static void
2404 df_byte_lr_set_bb_info (unsigned int index, 
2405                         struct df_byte_lr_bb_info *bb_info)
2406 {
2407   gcc_assert (df_byte_lr);
2408   gcc_assert (index < df_byte_lr->block_info_size);
2409   df_byte_lr->block_info[index] = bb_info;
2410 }
2411
2412  
2413 /* Free basic block info.  */
2414
2415 static void
2416 df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
2417                          void *vbb_info)
2418 {
2419   struct df_byte_lr_bb_info *bb_info = (struct df_byte_lr_bb_info *) vbb_info;
2420   if (bb_info)
2421     {
2422       BITMAP_FREE (bb_info->use);
2423       BITMAP_FREE (bb_info->def);
2424       BITMAP_FREE (bb_info->in);
2425       BITMAP_FREE (bb_info->out);
2426       pool_free (df_byte_lr->block_pool, bb_info);
2427     }
2428 }
2429
2430
2431 /* Check all of the refs in REF_REC to see if any of them are
2432    extracts, subregs or strict_low_parts.  */
2433
2434 static void
2435 df_byte_lr_check_regs (df_ref *ref_rec)
2436 {
2437   struct df_byte_lr_problem_data *problem_data 
2438     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2439
2440   for (; *ref_rec; ref_rec++)
2441     {
2442       df_ref ref = *ref_rec;
2443       if (DF_REF_FLAGS_IS_SET (ref, DF_REF_SIGN_EXTRACT 
2444                                | DF_REF_ZERO_EXTRACT 
2445                                | DF_REF_STRICT_LOW_PART)
2446           || GET_CODE (DF_REF_REG (ref)) == SUBREG)
2447         bitmap_set_bit (problem_data->needs_expansion, DF_REF_REGNO (ref));
2448     }
2449 }
2450
2451
2452 /* Expand bitmap SRC which is indexed by regno to DEST which is indexed by 
2453    regno_start and regno_len.  */
2454
2455 static void
2456 df_byte_lr_expand_bitmap (bitmap dest, bitmap src)
2457 {
2458   struct df_byte_lr_problem_data *problem_data 
2459     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2460   bitmap_iterator bi;
2461   unsigned int i;
2462
2463   bitmap_clear (dest);
2464   EXECUTE_IF_SET_IN_BITMAP (src, 0, i, bi)
2465     {
2466       bitmap_set_range (dest, problem_data->regno_start[i], 
2467                         problem_data->regno_len[i]);
2468     }
2469 }
2470
2471
2472 /* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are
2473    not touched unless the block is new.  */
2474
2475 static void 
2476 df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2477 {
2478   unsigned int bb_index;
2479   bitmap_iterator bi;
2480   basic_block bb;
2481   unsigned int regno;
2482   unsigned int index = 0;
2483   unsigned int max_reg = max_reg_num();
2484   struct df_byte_lr_problem_data *problem_data 
2485     = problem_data = XNEW (struct df_byte_lr_problem_data);
2486
2487   df_byte_lr->problem_data = problem_data;
2488
2489   if (!df_byte_lr->block_pool)
2490     df_byte_lr->block_pool = create_alloc_pool ("df_byte_lr_block pool", 
2491                                            sizeof (struct df_byte_lr_bb_info), 50);
2492
2493   df_grow_bb_info (df_byte_lr);
2494
2495   /* Create the mapping from regnos to slots. This does not change
2496      unless the problem is destroyed and recreated.  In particular, if
2497      we end up deleting the only insn that used a subreg, we do not
2498      want to redo the mapping because this would invalidate everything
2499      else.  */
2500
2501   bitmap_obstack_initialize (&problem_data->byte_lr_bitmaps);
2502   problem_data->regno_start = XNEWVEC (unsigned int, max_reg);
2503   problem_data->regno_len = XNEWVEC (unsigned int, max_reg);
2504   problem_data->hardware_regs_used = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2505   problem_data->invalidated_by_call = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2506   problem_data->needs_expansion = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2507   
2508   /* Discover which regno's use subregs, extracts or
2509      strict_low_parts.  */
2510   FOR_EACH_BB (bb)
2511     {
2512       rtx insn;
2513       FOR_BB_INSNS (bb, insn)
2514         {
2515           if (INSN_P (insn))
2516             {
2517               struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2518               df_byte_lr_check_regs (DF_INSN_INFO_DEFS (insn_info));
2519               df_byte_lr_check_regs (DF_INSN_INFO_USES (insn_info));
2520             }
2521         }
2522       bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, bb->index);
2523     }
2524
2525   bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2526   bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2527   
2528   /* Allocate the slots for each regno.  */
2529   for (regno = 0; regno < max_reg; regno++)
2530     {
2531       int len;
2532       problem_data->regno_start[regno] = index;
2533       if (bitmap_bit_p (problem_data->needs_expansion, regno))
2534         len = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
2535       else 
2536         len = 1;
2537       
2538       problem_data->regno_len[regno] = len;
2539       index += len;
2540     }
2541
2542   df_byte_lr_expand_bitmap (problem_data->hardware_regs_used, 
2543                             df->hardware_regs_used);
2544   df_byte_lr_expand_bitmap (problem_data->invalidated_by_call, 
2545                             regs_invalidated_by_call_regset);
2546
2547   EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2548     {
2549       struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2550       if (bb_info)
2551         { 
2552           bitmap_clear (bb_info->def);
2553           bitmap_clear (bb_info->use);
2554         }
2555       else
2556         { 
2557           bb_info = (struct df_byte_lr_bb_info *) pool_alloc (df_byte_lr->block_pool);
2558           df_byte_lr_set_bb_info (bb_index, bb_info);
2559           bb_info->use = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2560           bb_info->def = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2561           bb_info->in = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2562           bb_info->out = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2563         }
2564     }
2565   
2566   df_byte_lr->optional_p = true;
2567 }
2568
2569
2570 /* Reset the global solution for recalculation.  */
2571
2572 static void 
2573 df_byte_lr_reset (bitmap all_blocks)
2574 {
2575   unsigned int bb_index;
2576   bitmap_iterator bi;
2577
2578   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2579     {
2580       struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2581       gcc_assert (bb_info);
2582       bitmap_clear (bb_info->in);
2583       bitmap_clear (bb_info->out);
2584     }
2585 }
2586
2587
2588 /* Compute local live register info for basic block BB.  */
2589
2590 static void
2591 df_byte_lr_bb_local_compute (unsigned int bb_index)
2592 {
2593   struct df_byte_lr_problem_data *problem_data 
2594     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2595   basic_block bb = BASIC_BLOCK (bb_index);
2596   struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2597   rtx insn;
2598   df_ref *def_rec;
2599   df_ref *use_rec;
2600
2601   /* Process the registers set in an exception handler.  */
2602   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2603     {
2604       df_ref def = *def_rec;
2605       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2606         {
2607           unsigned int dregno = DF_REF_REGNO (def);
2608           unsigned int start = problem_data->regno_start[dregno];
2609           unsigned int len = problem_data->regno_len[dregno];
2610           bitmap_set_range (bb_info->def, start, len);
2611           bitmap_clear_range (bb_info->use, start, len);
2612         }
2613     }
2614
2615   /* Process the hardware registers that are always live.  */
2616   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2617     {
2618       df_ref use = *use_rec;
2619       /* Add use to set of uses in this BB.  */
2620       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
2621         {
2622           unsigned int uregno = DF_REF_REGNO (use);
2623           unsigned int start = problem_data->regno_start[uregno];
2624           unsigned int len = problem_data->regno_len[uregno];
2625           bitmap_set_range (bb_info->use, start, len);
2626         }
2627     }
2628
2629   FOR_BB_INSNS_REVERSE (bb, insn)
2630     {
2631       unsigned int uid = INSN_UID (insn);
2632
2633       if (!INSN_P (insn))
2634         continue;       
2635
2636       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2637         {
2638           df_ref def = *def_rec;
2639           /* If the def is to only part of the reg, it does
2640              not kill the other defs that reach here.  */
2641           if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2642             {
2643               unsigned int dregno = DF_REF_REGNO (def);
2644               unsigned int start = problem_data->regno_start[dregno];
2645               unsigned int len = problem_data->regno_len[dregno];
2646               unsigned int sb;
2647               unsigned int lb;
2648               if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2649                 {
2650                   start += sb;
2651                   len = lb - sb;
2652                 }
2653               if (len)
2654                 {
2655                   bitmap_set_range (bb_info->def, start, len);
2656                   bitmap_clear_range (bb_info->use, start, len);
2657                 }
2658             }
2659         }
2660
2661       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2662         {
2663           df_ref use = *use_rec;
2664           unsigned int uregno = DF_REF_REGNO (use);
2665           unsigned int start = problem_data->regno_start[uregno];
2666           unsigned int len = problem_data->regno_len[uregno];
2667           unsigned int sb;
2668           unsigned int lb;
2669           if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2670             {
2671               start += sb;
2672               len = lb - sb;
2673             }
2674           /* Add use to set of uses in this BB.  */
2675           if (len)
2676             bitmap_set_range (bb_info->use, start, len);
2677         }
2678     }
2679
2680   /* Process the registers set in an exception handler or the hard
2681      frame pointer if this block is the target of a non local
2682      goto.  */
2683   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2684     {
2685       df_ref def = *def_rec;
2686       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2687         {
2688           unsigned int dregno = DF_REF_REGNO (def);
2689           unsigned int start = problem_data->regno_start[dregno];
2690           unsigned int len = problem_data->regno_len[dregno];
2691           bitmap_set_range (bb_info->def, start, len);
2692           bitmap_clear_range (bb_info->use, start, len);
2693         }
2694     }
2695   
2696 #ifdef EH_USES
2697   /* Process the uses that are live into an exception handler.  */
2698   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2699     {
2700       df_ref use = *use_rec;
2701       /* Add use to set of uses in this BB.  */
2702       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
2703         {
2704           unsigned int uregno = DF_REF_REGNO (use);
2705           unsigned int start = problem_data->regno_start[uregno];
2706           unsigned int len = problem_data->regno_len[uregno];
2707           bitmap_set_range (bb_info->use, start, len);
2708         }
2709     }
2710 #endif
2711 }
2712
2713
2714 /* Compute local live register info for each basic block within BLOCKS.  */
2715
2716 static void
2717 df_byte_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2718 {
2719   unsigned int bb_index;
2720   bitmap_iterator bi;
2721
2722   EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2723     {
2724       if (bb_index == EXIT_BLOCK)
2725         {
2726           /* The exit block is special for this problem and its bits are
2727              computed from thin air.  */
2728           struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (EXIT_BLOCK);
2729           df_byte_lr_expand_bitmap (bb_info->use, df->exit_block_uses);
2730         }
2731       else
2732         df_byte_lr_bb_local_compute (bb_index);
2733     }
2734
2735   bitmap_clear (df_byte_lr->out_of_date_transfer_functions);
2736 }
2737
2738
2739 /* Initialize the solution vectors.  */
2740
2741 static void 
2742 df_byte_lr_init (bitmap all_blocks)
2743 {
2744   unsigned int bb_index;
2745   bitmap_iterator bi;
2746
2747   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2748     {
2749       struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2750       bitmap_copy (bb_info->in, bb_info->use);
2751       bitmap_clear (bb_info->out);
2752     }
2753 }
2754
2755
2756 /* Confluence function that processes infinite loops.  This might be a
2757    noreturn function that throws.  And even if it isn't, getting the
2758    unwind info right helps debugging.  */
2759 static void
2760 df_byte_lr_confluence_0 (basic_block bb)
2761 {
2762   struct df_byte_lr_problem_data *problem_data 
2763     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2764   bitmap op1 = df_byte_lr_get_bb_info (bb->index)->out;
2765   if (bb != EXIT_BLOCK_PTR)
2766     bitmap_copy (op1, problem_data->hardware_regs_used);
2767
2768
2769
2770 /* Confluence function that ignores fake edges.  */
2771
2772 static void
2773 df_byte_lr_confluence_n (edge e)
2774 {
2775   struct df_byte_lr_problem_data *problem_data 
2776     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2777   bitmap op1 = df_byte_lr_get_bb_info (e->src->index)->out;
2778   bitmap op2 = df_byte_lr_get_bb_info (e->dest->index)->in;
2779  
2780   /* Call-clobbered registers die across exception and call edges.  */
2781   /* ??? Abnormal call edges ignored for the moment, as this gets
2782      confused by sibling call edges, which crashes reg-stack.  */
2783   if (e->flags & EDGE_EH)
2784     bitmap_ior_and_compl_into (op1, op2, problem_data->invalidated_by_call);
2785   else
2786     bitmap_ior_into (op1, op2);
2787
2788   bitmap_ior_into (op1, problem_data->hardware_regs_used);
2789
2790
2791
2792 /* Transfer function.  */
2793
2794 static bool
2795 df_byte_lr_transfer_function (int bb_index)
2796 {
2797   struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2798   bitmap in = bb_info->in;
2799   bitmap out = bb_info->out;
2800   bitmap use = bb_info->use;
2801   bitmap def = bb_info->def;
2802
2803   return bitmap_ior_and_compl (in, use, out, def);
2804 }
2805
2806
2807 /* Free all storage associated with the problem.  */
2808
2809 static void
2810 df_byte_lr_free (void)
2811 {
2812   struct df_byte_lr_problem_data *problem_data
2813     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2814
2815
2816   if (df_byte_lr->block_info)
2817     {
2818       free_alloc_pool (df_byte_lr->block_pool);
2819       df_byte_lr->block_info_size = 0;
2820       free (df_byte_lr->block_info);
2821     }
2822
2823   BITMAP_FREE (df_byte_lr->out_of_date_transfer_functions);
2824   bitmap_obstack_release (&problem_data->byte_lr_bitmaps);
2825   free (problem_data->regno_start);
2826   free (problem_data->regno_len);
2827   free (problem_data);
2828   free (df_byte_lr);
2829 }
2830
2831
2832 /* Debugging info at top of bb.  */
2833
2834 static void
2835 df_byte_lr_top_dump (basic_block bb, FILE *file)
2836 {
2837   struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2838   if (!bb_info || !bb_info->in)
2839     return;
2840       
2841   fprintf (file, ";; blr  in  \t");
2842   df_print_byte_regset (file, bb_info->in);
2843   fprintf (file, ";; blr  use \t");
2844   df_print_byte_regset (file, bb_info->use);
2845   fprintf (file, ";; blr  def \t");
2846   df_print_byte_regset (file, bb_info->def);
2847 }  
2848
2849
2850 /* Debugging info at bottom of bb.  */
2851
2852 static void
2853 df_byte_lr_bottom_dump (basic_block bb, FILE *file)
2854 {
2855   struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2856   if (!bb_info || !bb_info->out)
2857     return;
2858   
2859   fprintf (file, ";; blr  out \t");
2860   df_print_byte_regset (file, bb_info->out);
2861 }  
2862
2863
2864 /* All of the information associated with every instance of the problem.  */
2865
2866 static struct df_problem problem_BYTE_LR =
2867 {
2868   DF_BYTE_LR,                      /* Problem id.  */
2869   DF_BACKWARD,                     /* Direction.  */
2870   df_byte_lr_alloc,                /* Allocate the problem specific data.  */
2871   df_byte_lr_reset,                /* Reset global information.  */
2872   df_byte_lr_free_bb_info,         /* Free basic block info.  */
2873   df_byte_lr_local_compute,        /* Local compute function.  */
2874   df_byte_lr_init,                 /* Init the solution specific data.  */
2875   df_worklist_dataflow,            /* Worklist solver.  */
2876   df_byte_lr_confluence_0,         /* Confluence operator 0.  */ 
2877   df_byte_lr_confluence_n,         /* Confluence operator n.  */ 
2878   df_byte_lr_transfer_function,    /* Transfer function.  */
2879   NULL,                            /* Finalize function.  */
2880   df_byte_lr_free,                 /* Free all of the problem information.  */
2881   df_byte_lr_free,                 /* Remove this problem from the stack of dataflow problems.  */
2882   NULL,                            /* Debugging.  */
2883   df_byte_lr_top_dump,             /* Debugging start block.  */
2884   df_byte_lr_bottom_dump,          /* Debugging end block.  */
2885   NULL,                            /* Incremental solution verify start.  */
2886   NULL,                            /* Incremental solution verify end.  */
2887   NULL,                            /* Dependent problem.  */
2888   TV_DF_BYTE_LR,                   /* Timing variable.  */ 
2889   false                            /* Reset blocks on dropping out of blocks_to_analyze.  */
2890 };
2891
2892
2893 /* Create a new DATAFLOW instance and add it to an existing instance
2894    of DF.  The returned structure is what is used to get at the
2895    solution.  */
2896
2897 void
2898 df_byte_lr_add_problem (void)
2899 {
2900   df_add_problem (&problem_BYTE_LR);
2901   /* These will be initialized when df_scan_blocks processes each
2902      block.  */
2903   df_byte_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2904 }
2905
2906
2907 /* Simulate the effects of the defs of INSN on LIVE.  */
2908
2909 void
2910 df_byte_lr_simulate_defs (rtx insn, bitmap live)
2911 {
2912   struct df_byte_lr_problem_data *problem_data 
2913     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2914   df_ref *def_rec;
2915   unsigned int uid = INSN_UID (insn);
2916
2917   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2918     {
2919       df_ref def = *def_rec;
2920
2921       /* If the def is to only part of the reg, it does
2922          not kill the other defs that reach here.  */
2923       if (!(DF_REF_FLAGS (def) & DF_REF_CONDITIONAL))
2924         {
2925           unsigned int dregno = DF_REF_REGNO (def);
2926           unsigned int start = problem_data->regno_start[dregno];
2927           unsigned int len = problem_data->regno_len[dregno];
2928           unsigned int sb;
2929           unsigned int lb;
2930           if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2931             {
2932               start += sb;
2933               len = lb - sb;
2934             }
2935
2936           if (len)
2937             bitmap_clear_range (live, start, len);
2938         }
2939     }
2940 }  
2941
2942
2943 /* Simulate the effects of the uses of INSN on LIVE.  */
2944
2945 void 
2946 df_byte_lr_simulate_uses (rtx insn, bitmap live)
2947 {
2948   struct df_byte_lr_problem_data *problem_data 
2949     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2950   df_ref *use_rec;
2951   unsigned int uid = INSN_UID (insn);
2952
2953   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2954     {
2955       df_ref use = *use_rec;
2956       unsigned int uregno = DF_REF_REGNO (use);
2957       unsigned int start = problem_data->regno_start[uregno];
2958       unsigned int len = problem_data->regno_len[uregno];
2959       unsigned int sb;
2960       unsigned int lb;
2961       
2962       if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2963         {
2964           start += sb;
2965           len = lb - sb;
2966         }
2967       
2968       /* Add use to set of uses in this BB.  */
2969       if (len)
2970         bitmap_set_range (live, start, len);
2971     }
2972 }
2973
2974
2975 /* Apply the artificial uses and defs at the top of BB in a forwards
2976    direction.  */
2977
2978 void 
2979 df_byte_lr_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
2980 {
2981   struct df_byte_lr_problem_data *problem_data 
2982     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2983   df_ref *def_rec;
2984 #ifdef EH_USES
2985   df_ref *use_rec;
2986 #endif
2987   int bb_index = bb->index;
2988   
2989 #ifdef EH_USES
2990   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2991     {
2992       df_ref use = *use_rec;
2993       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
2994         {
2995           unsigned int uregno = DF_REF_REGNO (use);
2996           unsigned int start = problem_data->regno_start[uregno];
2997           unsigned int len = problem_data->regno_len[uregno];
2998           bitmap_set_range (live, start, len);
2999         }
3000     }
3001 #endif
3002
3003   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3004     {
3005       df_ref def = *def_rec;
3006       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3007         {      
3008           unsigned int dregno = DF_REF_REGNO (def);
3009           unsigned int start = problem_data->regno_start[dregno];
3010           unsigned int len = problem_data->regno_len[dregno];
3011           bitmap_clear_range (live, start, len);
3012         }
3013     }
3014 }
3015
3016
3017 /* Apply the artificial uses and defs at the end of BB in a backwards
3018    direction.  */
3019
3020 void 
3021 df_byte_lr_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3022 {
3023   struct df_byte_lr_problem_data *problem_data 
3024     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
3025   df_ref *def_rec;
3026   df_ref *use_rec;
3027   int bb_index = bb->index;
3028   
3029   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3030     {
3031       df_ref def = *def_rec;
3032       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3033         {
3034           unsigned int dregno = DF_REF_REGNO (def);
3035           unsigned int start = problem_data->regno_start[dregno];
3036           unsigned int len = problem_data->regno_len[dregno];
3037           bitmap_clear_range (live, start, len);
3038         }
3039     }
3040
3041   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3042     {
3043       df_ref use = *use_rec;
3044       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3045         {
3046           unsigned int uregno = DF_REF_REGNO (use);
3047           unsigned int start = problem_data->regno_start[uregno];
3048           unsigned int len = problem_data->regno_len[uregno];
3049           bitmap_set_range (live, start, len);
3050         }
3051     }
3052 }
3053
3054
3055 \f
3056 /*----------------------------------------------------------------------------
3057    This problem computes REG_DEAD and REG_UNUSED notes.
3058    ----------------------------------------------------------------------------*/
3059
3060 static void 
3061 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3062 {
3063   df_note->optional_p = true;
3064 }
3065
3066 #ifdef REG_DEAD_DEBUGGING
3067 static void 
3068 df_print_note (const char *prefix, rtx insn, rtx note)
3069 {
3070   if (dump_file)
3071     {
3072       fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3073       print_rtl (dump_file, note);
3074       fprintf (dump_file, "\n");
3075     }
3076 }
3077 #endif
3078
3079
3080 /* After reg-stack, the x86 floating point stack regs are difficult to
3081    analyze because of all of the pushes, pops and rotations.  Thus, we
3082    just leave the notes alone. */
3083
3084 #ifdef STACK_REGS
3085 static inline bool 
3086 df_ignore_stack_reg (int regno)
3087 {
3088   return regstack_completed
3089     && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3090 }
3091 #else
3092 static inline bool 
3093 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3094 {
3095   return false;
3096 }
3097 #endif
3098
3099
3100 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3101    them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES.  */
3102
3103 static void
3104 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
3105 {
3106   rtx *pprev = &REG_NOTES (insn);
3107   rtx link = *pprev;
3108   rtx dead = NULL;
3109   rtx unused = NULL;
3110
3111   while (link)
3112     {
3113       switch (REG_NOTE_KIND (link))
3114         {
3115         case REG_DEAD:
3116           /* After reg-stack, we need to ignore any unused notes 
3117              for the stack registers.  */
3118           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3119             {
3120               pprev = &XEXP (link, 1);
3121               link = *pprev;
3122             }
3123           else
3124             {
3125               rtx next = XEXP (link, 1);
3126 #ifdef REG_DEAD_DEBUGGING
3127               df_print_note ("deleting: ", insn, link);
3128 #endif
3129               XEXP (link, 1) = dead;
3130               dead = link;
3131               *pprev = link = next;
3132             }
3133           break;
3134
3135         case REG_UNUSED:
3136           /* After reg-stack, we need to ignore any unused notes 
3137              for the stack registers.  */
3138           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3139             {
3140               pprev = &XEXP (link, 1);
3141               link = *pprev;
3142             }
3143           else
3144             {
3145               rtx next = XEXP (link, 1);
3146 #ifdef REG_DEAD_DEBUGGING
3147               df_print_note ("deleting: ", insn, link);
3148 #endif
3149               XEXP (link, 1) = unused;
3150               unused = link;
3151               *pprev = link = next;
3152             }
3153           break;
3154           
3155         default:
3156           pprev = &XEXP (link, 1);
3157           link = *pprev;
3158           break;
3159         }
3160     }
3161
3162   *old_dead_notes = dead;
3163   *old_unused_notes = unused;
3164 }
3165
3166
3167 /* Set a NOTE_TYPE note for REG in INSN.  Try to pull it from the OLD
3168    list, otherwise create a new one.  */
3169
3170 static inline rtx
3171 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
3172 {
3173   rtx curr = old;
3174   rtx prev = NULL;
3175
3176   while (curr)
3177     if (XEXP (curr, 0) == reg)
3178       {
3179         if (prev)
3180           XEXP (prev, 1) = XEXP (curr, 1);
3181         else
3182           old = XEXP (curr, 1);
3183         XEXP (curr, 1) = REG_NOTES (insn);
3184         REG_NOTES (insn) = curr;
3185         return old;
3186       }
3187     else
3188       {
3189         prev = curr;
3190         curr = XEXP (curr, 1);
3191       }
3192   
3193   /* Did not find the note.  */
3194   add_reg_note (insn, note_type, reg);
3195   return old;
3196 }
3197
3198 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3199    arguments.  Return true if the register value described by MWS's
3200    mw_reg is known to be completely unused, and if mw_reg can therefore
3201    be used in a REG_UNUSED note.  */
3202
3203 static bool
3204 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3205                           bitmap live, bitmap artificial_uses)
3206 {
3207   unsigned int r;
3208
3209   /* If MWS describes a partial reference, create REG_UNUSED notes for
3210      individual hard registers.  */
3211   if (mws->flags & DF_REF_PARTIAL)
3212     return false;
3213
3214   /* Likewise if some part of the register is used.  */
3215   for (r = mws->start_regno; r <= mws->end_regno; r++)
3216     if (bitmap_bit_p (live, r)
3217         || bitmap_bit_p (artificial_uses, r))
3218       return false;
3219
3220   gcc_assert (REG_P (mws->mw_reg));
3221   return true;
3222 }
3223
3224 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3225    based on the bits in LIVE.  Do not generate notes for registers in
3226    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
3227    not generated if the reg is both read and written by the
3228    instruction.
3229 */
3230
3231 static rtx
3232 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3233                             bitmap live, bitmap do_not_gen, 
3234                             bitmap artificial_uses)
3235 {
3236   unsigned int r;
3237   
3238 #ifdef REG_DEAD_DEBUGGING
3239   if (dump_file)
3240     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n", 
3241              mws->start_regno, mws->end_regno);
3242 #endif
3243
3244   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3245     {
3246       unsigned int regno = mws->start_regno;
3247       old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
3248
3249 #ifdef REG_DEAD_DEBUGGING
3250       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3251 #endif
3252       bitmap_set_bit (do_not_gen, regno);
3253       /* Only do this if the value is totally dead.  */
3254     }
3255   else
3256     for (r = mws->start_regno; r <= mws->end_regno; r++)
3257       {
3258         if (!bitmap_bit_p (live, r)
3259             && !bitmap_bit_p (artificial_uses, r))
3260           {
3261             old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3262 #ifdef REG_DEAD_DEBUGGING
3263             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3264 #endif
3265           }
3266         bitmap_set_bit (do_not_gen, r);
3267       }
3268   return old;
3269 }
3270
3271
3272 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3273    arguments.  Return true if the register value described by MWS's
3274    mw_reg is known to be completely dead, and if mw_reg can therefore
3275    be used in a REG_DEAD note.  */
3276
3277 static bool
3278 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3279                         bitmap live, bitmap artificial_uses,
3280                         bitmap do_not_gen)
3281 {
3282   unsigned int r;
3283
3284   /* If MWS describes a partial reference, create REG_DEAD notes for
3285      individual hard registers.  */
3286   if (mws->flags & DF_REF_PARTIAL)
3287     return false;
3288
3289   /* Likewise if some part of the register is not dead.  */
3290   for (r = mws->start_regno; r <= mws->end_regno; r++)
3291     if (bitmap_bit_p (live, r)
3292         || bitmap_bit_p (artificial_uses, r)
3293         || bitmap_bit_p (do_not_gen, r))
3294       return false;
3295
3296   gcc_assert (REG_P (mws->mw_reg));
3297   return true;
3298 }
3299
3300 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3301    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
3302    from being set if the instruction both reads and writes the
3303    register.  */
3304
3305 static rtx
3306 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3307                           bitmap live, bitmap do_not_gen,
3308                           bitmap artificial_uses)
3309 {
3310   unsigned int r;
3311   
3312 #ifdef REG_DEAD_DEBUGGING
3313   if (dump_file)
3314     {
3315       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =", 
3316                mws->start_regno, mws->end_regno);
3317       df_print_regset (dump_file, do_not_gen);
3318       fprintf (dump_file, "  live =");
3319       df_print_regset (dump_file, live);
3320       fprintf (dump_file, "  artificial uses =");
3321       df_print_regset (dump_file, artificial_uses);
3322     }
3323 #endif
3324
3325   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3326     {
3327       /* Add a dead note for the entire multi word register.  */
3328       old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
3329 #ifdef REG_DEAD_DEBUGGING
3330       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3331 #endif
3332     }
3333   else
3334     {
3335       for (r = mws->start_regno; r <= mws->end_regno; r++)
3336         if (!bitmap_bit_p (live, r)
3337             && !bitmap_bit_p (artificial_uses, r)
3338             && !bitmap_bit_p (do_not_gen, r))
3339           {
3340             old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3341 #ifdef REG_DEAD_DEBUGGING
3342             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3343 #endif
3344           }
3345     }
3346   return old;
3347 }
3348
3349
3350 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3351    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
3352
3353 static rtx
3354 df_create_unused_note (rtx insn, rtx old, df_ref def, 
3355                        bitmap live, bitmap artificial_uses)
3356 {
3357   unsigned int dregno = DF_REF_REGNO (def);
3358   
3359 #ifdef REG_DEAD_DEBUGGING
3360   if (dump_file)
3361     {
3362       fprintf (dump_file, "  regular looking at def ");
3363       df_ref_debug (def, dump_file);
3364     }
3365 #endif
3366
3367   if (!(bitmap_bit_p (live, dregno)
3368         || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3369         || bitmap_bit_p (artificial_uses, dregno)
3370         || df_ignore_stack_reg (dregno)))
3371     {
3372       rtx reg = (DF_REF_LOC (def)) 
3373                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3374       old = df_set_note (REG_UNUSED, insn, old, reg);
3375 #ifdef REG_DEAD_DEBUGGING
3376       df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3377 #endif
3378     }
3379   
3380   return old;
3381 }
3382
3383
3384 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3385    info: lifetime, bb, and number of defs and uses for basic block
3386    BB.  The three bitvectors are scratch regs used here.  */
3387
3388 static void
3389 df_note_bb_compute (unsigned int bb_index, 
3390                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3391 {
3392   basic_block bb = BASIC_BLOCK (bb_index);
3393   rtx insn;
3394   df_ref *def_rec;
3395   df_ref *use_rec;
3396
3397   bitmap_copy (live, df_get_live_out (bb));
3398   bitmap_clear (artificial_uses);
3399
3400 #ifdef REG_DEAD_DEBUGGING
3401   if (dump_file)
3402     {
3403       fprintf (dump_file, "live at bottom ");
3404       df_print_regset (dump_file, live);
3405     }
3406 #endif
3407
3408   /* Process the artificial defs and uses at the bottom of the block
3409      to begin processing.  */
3410   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3411     {
3412       df_ref def = *def_rec;
3413 #ifdef REG_DEAD_DEBUGGING
3414       if (dump_file)
3415         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3416 #endif
3417
3418       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3419         bitmap_clear_bit (live, DF_REF_REGNO (def));
3420     }
3421
3422   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3423     {
3424       df_ref use = *use_rec;
3425       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3426         {
3427           unsigned int regno = DF_REF_REGNO (use);
3428           bitmap_set_bit (live, regno);
3429           
3430           /* Notes are not generated for any of the artificial registers
3431              at the bottom of the block.  */
3432           bitmap_set_bit (artificial_uses, regno);
3433         }
3434     }
3435   
3436 #ifdef REG_DEAD_DEBUGGING
3437   if (dump_file)
3438     {
3439       fprintf (dump_file, "live before artificials out ");
3440       df_print_regset (dump_file, live);
3441     }
3442 #endif
3443
3444   FOR_BB_INSNS_REVERSE (bb, insn)
3445     {
3446       unsigned int uid = INSN_UID (insn);
3447       struct df_mw_hardreg **mws_rec;
3448       rtx old_dead_notes;
3449       rtx old_unused_notes;
3450  
3451       if (!INSN_P (insn))
3452         continue;
3453
3454       bitmap_clear (do_not_gen);
3455       df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3456
3457       /* Process the defs.  */
3458       if (CALL_P (insn))
3459         {
3460 #ifdef REG_DEAD_DEBUGGING
3461           if (dump_file)
3462             {
3463               fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
3464               df_print_regset (dump_file, live);
3465             }
3466 #endif
3467           /* We only care about real sets for calls.  Clobbers cannot
3468              be depended on to really die.  */
3469           mws_rec = DF_INSN_UID_MWS (uid);
3470           while (*mws_rec)
3471             {
3472               struct df_mw_hardreg *mws = *mws_rec; 
3473               if ((DF_MWS_REG_DEF_P (mws)) 
3474                   && !df_ignore_stack_reg (mws->start_regno))
3475                 old_unused_notes 
3476                   = df_set_unused_notes_for_mw (insn, old_unused_notes, 
3477                                                 mws, live, do_not_gen, 
3478                                                 artificial_uses);
3479               mws_rec++;
3480             }
3481
3482           /* All of the defs except the return value are some sort of
3483              clobber.  This code is for the return.  */
3484           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3485             {
3486               df_ref def = *def_rec;
3487               unsigned int dregno = DF_REF_REGNO (def);
3488               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3489                 {
3490                   old_unused_notes
3491                     = df_create_unused_note (insn, old_unused_notes, 
3492                                              def, live, artificial_uses);
3493                   bitmap_set_bit (do_not_gen, dregno);
3494                 }
3495
3496               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3497                 bitmap_clear_bit (live, dregno);
3498             }
3499         }
3500       else
3501         {
3502           /* Regular insn.  */
3503           mws_rec = DF_INSN_UID_MWS (uid);
3504           while (*mws_rec)
3505             {
3506               struct df_mw_hardreg *mws = *mws_rec; 
3507               if (DF_MWS_REG_DEF_P (mws))
3508                 old_unused_notes
3509                   = df_set_unused_notes_for_mw (insn, old_unused_notes, 
3510                                                 mws, live, do_not_gen, 
3511                                                 artificial_uses);
3512               mws_rec++;
3513             }
3514
3515           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3516             {
3517               df_ref def = *def_rec;
3518               unsigned int dregno = DF_REF_REGNO (def);
3519               old_unused_notes
3520                 = df_create_unused_note (insn, old_unused_notes, 
3521                                          def, live, artificial_uses);
3522
3523               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3524                 bitmap_set_bit (do_not_gen, dregno);
3525
3526               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3527                 bitmap_clear_bit (live, dregno);
3528             }
3529         }
3530       
3531       /* Process the uses.  */
3532       mws_rec = DF_INSN_UID_MWS (uid);
3533       while (*mws_rec)
3534         {
3535           struct df_mw_hardreg *mws = *mws_rec; 
3536           if ((DF_MWS_REG_DEF_P (mws))  
3537               && !df_ignore_stack_reg (mws->start_regno))
3538             old_dead_notes
3539               = df_set_dead_notes_for_mw (insn, old_dead_notes, 
3540                                           mws, live, do_not_gen,
3541                                           artificial_uses);
3542           mws_rec++;
3543         }
3544
3545       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3546         {
3547           df_ref use = *use_rec;
3548           unsigned int uregno = DF_REF_REGNO (use);
3549
3550 #ifdef REG_DEAD_DEBUGGING
3551           if (dump_file)
3552             {
3553               fprintf (dump_file, "  regular looking at use ");
3554               df_ref_debug (use, dump_file);
3555             }
3556 #endif
3557           if (!bitmap_bit_p (live, uregno))
3558             {
3559               if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
3560                    && (!bitmap_bit_p (do_not_gen, uregno))
3561                    && (!bitmap_bit_p (artificial_uses, uregno))
3562                    && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
3563                    && (!df_ignore_stack_reg (uregno)))
3564                 {
3565                   rtx reg = (DF_REF_LOC (use)) 
3566                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3567                   old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
3568
3569 #ifdef REG_DEAD_DEBUGGING
3570                   df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3571 #endif
3572                 }
3573               /* This register is now live.  */
3574               bitmap_set_bit (live, uregno);
3575             }
3576         }
3577
3578       while (old_unused_notes)
3579         {
3580           rtx next = XEXP (old_unused_notes, 1);
3581           free_EXPR_LIST_node (old_unused_notes);
3582           old_unused_notes = next;
3583         }
3584       while (old_dead_notes)
3585         {
3586           rtx next = XEXP (old_dead_notes, 1);
3587           free_EXPR_LIST_node (old_dead_notes);
3588           old_dead_notes = next;
3589         }
3590     }
3591 }
3592
3593
3594 /* Compute register info: lifetime, bb, and number of defs and uses.  */
3595 static void
3596 df_note_compute (bitmap all_blocks)
3597 {
3598   unsigned int bb_index;
3599   bitmap_iterator bi;
3600   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
3601   bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
3602   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
3603
3604 #ifdef REG_DEAD_DEBUGGING
3605   if (dump_file)
3606     print_rtl_with_bb (dump_file, get_insns());
3607 #endif
3608
3609   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3610   {
3611     df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
3612   }
3613
3614   BITMAP_FREE (live);
3615   BITMAP_FREE (do_not_gen);
3616   BITMAP_FREE (artificial_uses);
3617 }
3618
3619
3620 /* Free all storage associated with the problem.  */
3621
3622 static void
3623 df_note_free (void)
3624 {
3625   free (df_note);
3626 }
3627
3628
3629 /* All of the information associated every instance of the problem.  */
3630
3631 static struct df_problem problem_NOTE =
3632 {
3633   DF_NOTE,                    /* Problem id.  */
3634   DF_NONE,                    /* Direction.  */
3635   df_note_alloc,              /* Allocate the problem specific data.  */
3636   NULL,                       /* Reset global information.  */
3637   NULL,                       /* Free basic block info.  */
3638   df_note_compute,            /* Local compute function.  */
3639   NULL,                       /* Init the solution specific data.  */
3640   NULL,                       /* Iterative solver.  */
3641   NULL,                       /* Confluence operator 0.  */ 
3642   NULL,                       /* Confluence operator n.  */ 
3643   NULL,                       /* Transfer function.  */
3644   NULL,                       /* Finalize function.  */
3645   df_note_free,               /* Free all of the problem information.  */
3646   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
3647   NULL,                       /* Debugging.  */
3648   NULL,                       /* Debugging start block.  */
3649   NULL,                       /* Debugging end block.  */
3650   NULL,                       /* Incremental solution verify start.  */
3651   NULL,                       /* Incremental solution verify end.  */
3652   &problem_LR,                /* Dependent problem.  */
3653   TV_DF_NOTE,                 /* Timing variable.  */
3654   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
3655 };
3656
3657
3658 /* Create a new DATAFLOW instance and add it to an existing instance
3659    of DF.  The returned structure is what is used to get at the
3660    solution.  */
3661
3662 void
3663 df_note_add_problem (void)
3664 {
3665   df_add_problem (&problem_NOTE);
3666 }
3667
3668
3669
3670 \f
3671 /*----------------------------------------------------------------------------
3672    Functions for simulating the effects of single insns.  
3673
3674    You can either simulate in the forwards direction, starting from
3675    the top of a block or the backwards direction from the end of the
3676    block.  The main difference is that if you go forwards, the uses
3677    are examined first then the defs, and if you go backwards, the defs
3678    are examined first then the uses.
3679
3680    If you start at the top of the block, use one of DF_LIVE_IN or
3681    DF_LR_IN.  If you start at the bottom of the block use one of
3682    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
3683    THEY WILL BE DESTROYED.
3684 ----------------------------------------------------------------------------*/
3685
3686
3687 /* Find the set of DEFs for INSN.  */
3688
3689 void
3690 df_simulate_find_defs (rtx insn, bitmap defs)
3691 {
3692   df_ref *def_rec;
3693   unsigned int uid = INSN_UID (insn);
3694
3695   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3696     {
3697       df_ref def = *def_rec;
3698       /* If the def is to only part of the reg, it does
3699          not kill the other defs that reach here.  */
3700       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3701         bitmap_set_bit (defs, DF_REF_REGNO (def));
3702     }
3703 }
3704
3705
3706 /* Simulate the effects of the defs of INSN on LIVE.  */
3707
3708 void
3709 df_simulate_defs (rtx insn, bitmap live)
3710 {
3711   df_ref *def_rec;
3712   unsigned int uid = INSN_UID (insn);
3713
3714   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3715     {
3716       df_ref def = *def_rec;
3717       unsigned int dregno = DF_REF_REGNO (def);
3718
3719       /* If the def is to only part of the reg, it does
3720          not kill the other defs that reach here.  */
3721       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3722         bitmap_clear_bit (live, dregno);
3723     }
3724 }  
3725
3726
3727 /* Simulate the effects of the uses of INSN on LIVE.  */
3728
3729 void 
3730 df_simulate_uses (rtx insn, bitmap live)
3731 {
3732   df_ref *use_rec;
3733   unsigned int uid = INSN_UID (insn);
3734
3735   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3736     {
3737       df_ref use = *use_rec;
3738       /* Add use to set of uses in this BB.  */
3739       bitmap_set_bit (live, DF_REF_REGNO (use));
3740     }
3741 }
3742
3743
3744 /* Add back the always live regs in BB to LIVE.  */
3745
3746 static inline void
3747 df_simulate_fixup_sets (basic_block bb, bitmap live)
3748 {
3749   /* These regs are considered always live so if they end up dying
3750      because of some def, we need to bring the back again.  */
3751   if (bb_has_eh_pred (bb))
3752     bitmap_ior_into (live, df->eh_block_artificial_uses);
3753   else
3754     bitmap_ior_into (live, df->regular_block_artificial_uses);
3755 }
3756
3757
3758 /*----------------------------------------------------------------------------
3759    The following three functions are used only for BACKWARDS scanning:
3760    i.e. they process the defs before the uses.
3761
3762    df_simulate_initialize_backwards should be called first with a
3763    bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT.  Then
3764    df_simulate_one_insn_backwards should be called for each insn in
3765    the block, starting with the last on.  Finally,
3766    df_simulate_finalize_backwards can be called to get a new value
3767    of the sets at the top of the block (this is rarely used).
3768    ----------------------------------------------------------------------------*/
3769
3770 /* Apply the artificial uses and defs at the end of BB in a backwards
3771    direction.  */
3772
3773 void 
3774 df_simulate_initialize_backwards (basic_block bb, bitmap live)
3775 {
3776   df_ref *def_rec;
3777   df_ref *use_rec;
3778   int bb_index = bb->index;
3779   
3780   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3781     {
3782       df_ref def = *def_rec;
3783       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3784         bitmap_clear_bit (live, DF_REF_REGNO (def));
3785     }
3786
3787   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3788     {
3789       df_ref use = *use_rec;
3790       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3791         bitmap_set_bit (live, DF_REF_REGNO (use));
3792     }
3793 }
3794
3795
3796 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3797
3798 void 
3799 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
3800 {
3801   if (! INSN_P (insn))
3802     return;     
3803   
3804   df_simulate_defs (insn, live);
3805   df_simulate_uses (insn, live);
3806   df_simulate_fixup_sets (bb, live);
3807 }
3808
3809
3810 /* Apply the artificial uses and defs at the top of BB in a backwards
3811    direction.  */
3812
3813 void 
3814 df_simulate_finalize_backwards (basic_block bb, bitmap live)
3815 {
3816   df_ref *def_rec;
3817 #ifdef EH_USES
3818   df_ref *use_rec;
3819 #endif
3820   int bb_index = bb->index;
3821   
3822   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3823     {
3824       df_ref def = *def_rec;
3825       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3826         bitmap_clear_bit (live, DF_REF_REGNO (def));
3827     }
3828
3829 #ifdef EH_USES
3830   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3831     {
3832       df_ref use = *use_rec;
3833       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3834         bitmap_set_bit (live, DF_REF_REGNO (use));
3835     }
3836 #endif
3837 }
3838 /*----------------------------------------------------------------------------
3839    The following three functions are used only for FORWARDS scanning:
3840    i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3841    Thus it is important to add the DF_NOTES problem to the stack of 
3842    problems computed before using these functions.
3843
3844    df_simulate_initialize_forwards should be called first with a
3845    bitvector copyied from the DF_LIVE_IN or DF_LR_IN.  Then
3846    df_simulate_one_insn_forwards should be called for each insn in
3847    the block, starting with the last on.  Finally,
3848    df_simulate_finalize_forwards can be called to get a new value
3849    of the sets at the bottom of the block (this is rarely used).
3850    ----------------------------------------------------------------------------*/
3851
3852 /* Apply the artificial uses and defs at the top of BB in a backwards
3853    direction.  */
3854
3855 void 
3856 df_simulate_initialize_forwards (basic_block bb, bitmap live)
3857 {
3858   df_ref *def_rec;
3859   int bb_index = bb->index;
3860   
3861   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3862     {
3863       df_ref def = *def_rec;
3864       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3865         bitmap_clear_bit (live, DF_REF_REGNO (def));
3866     }
3867 }
3868
3869 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3870
3871 void 
3872 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
3873 {
3874   rtx link;
3875   if (! INSN_P (insn))
3876     return;     
3877
3878   /* Make sure that the DF_NOTES really is an active df problem.  */ 
3879   gcc_assert (df_note);
3880
3881   df_simulate_defs (insn, live);
3882
3883   /* Clear all of the registers that go dead.  */
3884   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3885     {
3886       switch (REG_NOTE_KIND (link))
3887         case REG_DEAD:
3888         case REG_UNUSED:
3889         {
3890           rtx reg = XEXP (link, 0);
3891           int regno = REGNO (reg);
3892           if (regno < FIRST_PSEUDO_REGISTER)
3893             {
3894               int n = hard_regno_nregs[regno][GET_MODE (reg)];
3895               while (--n >= 0)
3896                 bitmap_clear_bit (live, regno + n);
3897             }
3898           else 
3899             bitmap_clear_bit (live, regno);
3900           break;
3901         default:
3902           break;
3903         }
3904     }
3905   df_simulate_fixup_sets (bb, live);
3906 }
3907
3908
3909 /* Apply the artificial uses and defs at the end of BB in a backwards
3910    direction.  */
3911
3912 void 
3913 df_simulate_finalize_forwards (basic_block bb, bitmap live)
3914 {
3915   df_ref *def_rec;
3916   int bb_index = bb->index;
3917   
3918   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3919     {
3920       df_ref def = *def_rec;
3921       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3922         bitmap_clear_bit (live, DF_REF_REGNO (def));
3923     }
3924 }
3925
3926