OSDN Git Service

043cf38398ff4147f7017187e404025e649b4785
[pf3gnuchains/gcc-fork.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 = xrealloc (dflow->block_info, 
113                                     new_size *sizeof (void*));
114       memset (dflow->block_info + dflow->block_info_size, 0,
115               (new_size - dflow->block_info_size) *sizeof (void *));
116       dflow->block_info_size = new_size;
117     }
118 }
119
120 /* Dump a def-use or use-def chain for REF to FILE.  */
121
122 void
123 df_chain_dump (struct df_link *link, FILE *file)
124 {
125   fprintf (file, "{ ");
126   for (; link; link = link->next)
127     {
128       fprintf (file, "%c%d(bb %d insn %d) ",
129                DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
130                DF_REF_ID (link->ref),
131                DF_REF_BBNO (link->ref),
132                DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
133     }
134   fprintf (file, "}");
135 }
136
137
138 /* Print some basic block info as part of df_dump.  */
139
140 void 
141 df_print_bb_index (basic_block bb, FILE *file)
142 {
143   edge e;
144   edge_iterator ei;
145
146   fprintf (file, "\n( ");
147     FOR_EACH_EDGE (e, ei, bb->preds)
148     {
149       basic_block pred = e->src;
150       fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
151     } 
152   fprintf (file, ")->[%d]->( ", bb->index);
153   FOR_EACH_EDGE (e, ei, bb->succs)
154     {
155       basic_block succ = e->dest;
156       fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
157     } 
158   fprintf (file, ")\n");
159 }
160
161
162
163 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
164    up correctly. */
165
166 static void
167 df_set_seen (void)
168 {
169   seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
170   seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
171 }
172
173
174 static void
175 df_unset_seen (void)
176 {
177   BITMAP_FREE (seen_in_block);
178   BITMAP_FREE (seen_in_insn);
179 }
180
181
182 \f
183 /*----------------------------------------------------------------------------
184    REACHING DEFINITIONS
185
186    Find the locations in the function where each definition site for a
187    pseudo reaches.  In and out bitvectors are built for each basic
188    block.  The id field in the ref is used to index into these sets.
189    See df.h for details.
190    ----------------------------------------------------------------------------*/
191
192 /* This problem plays a large number of games for the sake of
193    efficiency.  
194    
195    1) The order of the bits in the bitvectors.  After the scanning
196    phase, all of the defs are sorted.  All of the defs for the reg 0
197    are first, followed by all defs for reg 1 and so on.
198    
199    2) There are two kill sets, one if the number of defs is less or
200    equal to DF_SPARSE_THRESHOLD and another if the number of defs is
201    greater.
202
203    <= : Data is built directly in the kill set.
204
205    > : One level of indirection is used to keep from generating long
206    strings of 1 bits in the kill sets.  Bitvectors that are indexed
207    by the regnum are used to represent that there is a killing def
208    for the register.  The confluence and transfer functions use
209    these along with the bitmap_clear_range call to remove ranges of
210    bits without actually generating a knockout vector.
211
212    The kill and sparse_kill and the dense_invalidated_by_call and
213    sparse_invalidated_by_call both play this game.  */
214
215 /* Private data used to compute the solution for this problem.  These
216    data structures are not accessible outside of this module.  */
217 struct df_rd_problem_data
218 {
219   /* The set of defs to regs invalidated by call.  */
220   bitmap sparse_invalidated_by_call;  
221   /* The set of defs to regs invalidate by call for rd.  */  
222   bitmap dense_invalidated_by_call;
223   /* An obstack for the bitmaps we need for this problem.  */
224   bitmap_obstack rd_bitmaps;
225 };
226
227 /* Set basic block info.  */
228
229 static void
230 df_rd_set_bb_info (unsigned int index, 
231                    struct df_rd_bb_info *bb_info)
232 {
233   gcc_assert (df_rd);
234   gcc_assert (index < df_rd->block_info_size);
235   df_rd->block_info[index] = bb_info;
236 }
237
238
239 /* Free basic block info.  */
240
241 static void
242 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
243                     void *vbb_info)
244 {
245   struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
246   if (bb_info)
247     {
248       BITMAP_FREE (bb_info->kill);
249       BITMAP_FREE (bb_info->sparse_kill);
250       BITMAP_FREE (bb_info->gen);
251       BITMAP_FREE (bb_info->in);
252       BITMAP_FREE (bb_info->out);
253       pool_free (df_rd->block_pool, bb_info);
254     }
255 }
256
257
258 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
259    not touched unless the block is new.  */
260
261 static void 
262 df_rd_alloc (bitmap all_blocks)
263 {
264   unsigned int bb_index;
265   bitmap_iterator bi;
266   struct df_rd_problem_data *problem_data;
267
268   if (!df_rd->block_pool)
269     df_rd->block_pool = create_alloc_pool ("df_rd_block pool", 
270                                            sizeof (struct df_rd_bb_info), 50);
271
272   if (df_rd->problem_data)
273     {
274       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
275       bitmap_clear (problem_data->sparse_invalidated_by_call);
276       bitmap_clear (problem_data->dense_invalidated_by_call);
277     }
278   else 
279     {
280       problem_data = XNEW (struct df_rd_problem_data);
281       df_rd->problem_data = problem_data;
282
283       bitmap_obstack_initialize (&problem_data->rd_bitmaps);
284       problem_data->sparse_invalidated_by_call
285         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
286       problem_data->dense_invalidated_by_call
287         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
288     }
289
290   df_grow_bb_info (df_rd);
291
292   /* Because of the clustering of all use sites for the same pseudo,
293      we have to process all of the blocks before doing the
294      analysis.  */
295
296   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
297     {
298       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
299       if (bb_info)
300         { 
301           bitmap_clear (bb_info->kill);
302           bitmap_clear (bb_info->sparse_kill);
303           bitmap_clear (bb_info->gen);
304         }
305       else
306         { 
307           bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
308           df_rd_set_bb_info (bb_index, bb_info);
309           bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
310           bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
311           bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
312           bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
313           bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
314         }
315     }
316   df_rd->optional_p = true;
317 }
318
319
320 /* Process a list of DEFs for df_rd_bb_local_compute.  */
321
322 static void
323 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info, 
324                                     struct df_ref **def_rec,
325                                     enum df_ref_flags top_flag)
326 {
327   while (*def_rec)
328     {
329       struct df_ref *def = *def_rec;
330       if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
331         {
332           unsigned int regno = DF_REF_REGNO (def);
333           unsigned int begin = DF_DEFS_BEGIN (regno);
334           unsigned int n_defs = DF_DEFS_COUNT (regno);
335           
336           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
337               || (regno >= FIRST_PSEUDO_REGISTER))
338             {
339               /* Only the last def(s) for a regno in the block has any
340                  effect.  */ 
341               if (!bitmap_bit_p (seen_in_block, regno))
342                 {
343                   /* The first def for regno in insn gets to knock out the
344                      defs from other instructions.  */
345                   if ((!bitmap_bit_p (seen_in_insn, regno))
346                       /* If the def is to only part of the reg, it does
347                          not kill the other defs that reach here.  */
348                       && (!(DF_REF_FLAGS (def) & 
349                             (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
350                     {
351                       if (n_defs > DF_SPARSE_THRESHOLD)
352                         {
353                           bitmap_set_bit (bb_info->sparse_kill, regno);
354                           bitmap_clear_range(bb_info->gen, begin, n_defs);
355                         }
356                       else
357                         {
358                           bitmap_set_range (bb_info->kill, begin, n_defs);
359                           bitmap_clear_range (bb_info->gen, begin, n_defs);
360                         }
361                     }
362                   
363                   bitmap_set_bit (seen_in_insn, regno);
364                   /* All defs for regno in the instruction may be put into
365                      the gen set.  */
366                   if (!(DF_REF_FLAGS (def) 
367                         & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
368                     bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
369                 }
370             }
371         }
372       def_rec++;
373     }
374 }
375
376 /* Compute local reaching def info for basic block BB.  */
377
378 static void
379 df_rd_bb_local_compute (unsigned int bb_index)
380 {
381   basic_block bb = BASIC_BLOCK (bb_index);
382   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
383   rtx insn;
384
385   bitmap_clear (seen_in_block);
386   bitmap_clear (seen_in_insn);
387
388   /* Artificials are only hard regs.  */
389   if (!(df->changeable_flags & DF_NO_HARD_REGS))
390     df_rd_bb_local_compute_process_def (bb_info, 
391                                         df_get_artificial_defs (bb_index),
392                                         0);
393
394   FOR_BB_INSNS_REVERSE (bb, insn)
395     {
396       unsigned int uid = INSN_UID (insn);
397
398       if (!INSN_P (insn))
399         continue;
400
401       df_rd_bb_local_compute_process_def (bb_info, 
402                                           DF_INSN_UID_DEFS (uid), 0);
403
404       /* This complex dance with the two bitmaps is required because
405          instructions can assign twice to the same pseudo.  This
406          generally happens with calls that will have one def for the
407          result and another def for the clobber.  If only one vector
408          is used and the clobber goes first, the result will be
409          lost.  */
410       bitmap_ior_into (seen_in_block, seen_in_insn);
411       bitmap_clear (seen_in_insn);
412     }
413
414   /* Process the artificial defs at the top of the block last since we
415      are going backwards through the block and these are logically at
416      the start.  */
417   if (!(df->changeable_flags & DF_NO_HARD_REGS))
418     df_rd_bb_local_compute_process_def (bb_info, 
419                                         df_get_artificial_defs (bb_index),
420                                         DF_REF_AT_TOP);
421 }
422
423
424 /* Compute local reaching def info for each basic block within BLOCKS.  */
425
426 static void
427 df_rd_local_compute (bitmap all_blocks)
428 {
429   unsigned int bb_index;
430   bitmap_iterator bi;
431   unsigned int regno;
432   struct df_rd_problem_data *problem_data
433     = (struct df_rd_problem_data *) df_rd->problem_data;
434   bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
435   bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
436
437   df_set_seen ();
438
439   df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
440
441   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
442     {
443       df_rd_bb_local_compute (bb_index);
444     }
445   
446   /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
447   EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
448     {
449       if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
450         bitmap_set_bit (sparse_invalidated, regno);
451       else
452         bitmap_set_range (dense_invalidated, 
453                           DF_DEFS_BEGIN (regno), 
454                           DF_DEFS_COUNT (regno));
455     }
456   df_unset_seen ();
457 }
458
459
460 /* Initialize the solution bit vectors for problem.  */
461
462 static void 
463 df_rd_init_solution (bitmap all_blocks)
464 {
465   unsigned int bb_index;
466   bitmap_iterator bi;
467
468   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
469     {
470       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
471       
472       bitmap_copy (bb_info->out, bb_info->gen);
473       bitmap_clear (bb_info->in);
474     }
475 }
476
477 /* In of target gets or of out of source.  */
478
479 static void
480 df_rd_confluence_n (edge e)
481 {
482   bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
483   bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
484
485   if (e->flags & EDGE_FAKE) 
486     return;
487
488   if (e->flags & EDGE_EH)
489     {
490       struct df_rd_problem_data *problem_data
491         = (struct df_rd_problem_data *) df_rd->problem_data;
492       bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
493       bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
494       bitmap_iterator bi;
495       unsigned int regno;
496       bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
497
498       bitmap_copy (tmp, op2);
499       bitmap_and_compl_into (tmp, dense_invalidated);
500
501       EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
502         {
503           bitmap_clear_range (tmp, 
504                               DF_DEFS_BEGIN (regno), 
505                               DF_DEFS_COUNT (regno));
506         }
507       bitmap_ior_into (op1, tmp);
508       BITMAP_FREE (tmp);
509     }
510   else
511     bitmap_ior_into (op1, op2);
512 }
513
514
515 /* Transfer function.  */
516
517 static bool
518 df_rd_transfer_function (int bb_index)
519 {
520   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
521   unsigned int regno;
522   bitmap_iterator bi;
523   bitmap in = bb_info->in;
524   bitmap out = bb_info->out;
525   bitmap gen = bb_info->gen;
526   bitmap kill = bb_info->kill;
527   bitmap sparse_kill = bb_info->sparse_kill;
528
529   if (bitmap_empty_p (sparse_kill))
530     return  bitmap_ior_and_compl (out, gen, in, kill);
531   else 
532     {
533       struct df_rd_problem_data *problem_data;
534       bool changed = false;
535       bitmap tmp;
536
537       /* Note that TMP is _not_ a temporary bitmap if we end up replacing
538          OUT with TMP.  Therefore, allocate TMP in the RD bitmaps obstack.  */
539       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
540       tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
541
542       bitmap_copy (tmp, in);
543       EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
544         {
545           bitmap_clear_range (tmp, 
546                               DF_DEFS_BEGIN (regno), 
547                               DF_DEFS_COUNT (regno));
548         }
549       bitmap_and_compl_into (tmp, kill);
550       bitmap_ior_into (tmp, gen);
551       changed = !bitmap_equal_p (tmp, out);
552       if (changed)
553         {
554           BITMAP_FREE (out);
555           bb_info->out = tmp;
556         }
557       else 
558           BITMAP_FREE (tmp);
559       return changed;
560     }
561 }
562
563
564 /* Free all storage associated with the problem.  */
565
566 static void
567 df_rd_free (void)
568 {
569   struct df_rd_problem_data *problem_data
570     = (struct df_rd_problem_data *) df_rd->problem_data;
571
572   if (problem_data)
573     {
574       free_alloc_pool (df_rd->block_pool);
575       bitmap_obstack_release (&problem_data->rd_bitmaps);
576       
577       df_rd->block_info_size = 0;
578       free (df_rd->block_info);
579       free (df_rd->problem_data);
580     }
581   free (df_rd);
582 }
583
584
585 /* Debugging info.  */
586
587 static void
588 df_rd_start_dump (FILE *file)
589 {
590   struct df_rd_problem_data *problem_data
591     = (struct df_rd_problem_data *) df_rd->problem_data;
592   unsigned int m = DF_REG_SIZE(df);
593   unsigned int regno;
594   
595   if (!df_rd->block_info) 
596     return;
597
598   fprintf (file, ";; Reaching defs:\n\n");
599
600   fprintf (file, "  sparse invalidated \t");
601   dump_bitmap (file, problem_data->sparse_invalidated_by_call);
602   fprintf (file, "  dense invalidated \t");
603   dump_bitmap (file, problem_data->dense_invalidated_by_call);
604
605   for (regno = 0; regno < m; regno++)
606     if (DF_DEFS_COUNT (regno))
607       fprintf (file, "%d[%d,%d] ", regno, 
608                DF_DEFS_BEGIN (regno), 
609                DF_DEFS_COUNT (regno));
610   fprintf (file, "\n");
611
612 }
613
614
615 /* Debugging info at top of bb.  */
616
617 static void
618 df_rd_top_dump (basic_block bb, FILE *file)
619 {
620   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
621   if (!bb_info || !bb_info->in)
622     return;
623   
624   fprintf (file, ";; rd  in  \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
625   dump_bitmap (file, bb_info->in);
626   fprintf (file, ";; rd  gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
627   dump_bitmap (file, bb_info->gen);
628   fprintf (file, ";; rd  kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
629   dump_bitmap (file, bb_info->kill);
630 }
631
632
633 /* Debugging info at top of bb.  */
634
635 static void
636 df_rd_bottom_dump (basic_block bb, FILE *file)
637 {
638   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
639   if (!bb_info || !bb_info->out)
640     return;
641   
642   fprintf (file, ";; rd  out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
643   dump_bitmap (file, bb_info->out);
644 }
645
646 /* All of the information associated with every instance of the problem.  */
647
648 static struct df_problem problem_RD =
649 {
650   DF_RD,                      /* Problem id.  */
651   DF_FORWARD,                 /* Direction.  */
652   df_rd_alloc,                /* Allocate the problem specific data.  */
653   NULL,                       /* Reset global information.  */
654   df_rd_free_bb_info,         /* Free basic block info.  */
655   df_rd_local_compute,        /* Local compute function.  */
656   df_rd_init_solution,        /* Init the solution specific data.  */
657   df_worklist_dataflow,       /* Worklist solver.  */
658   NULL,                       /* Confluence operator 0.  */ 
659   df_rd_confluence_n,         /* Confluence operator n.  */ 
660   df_rd_transfer_function,    /* Transfer function.  */
661   NULL,                       /* Finalize function.  */
662   df_rd_free,                 /* Free all of the problem information.  */
663   df_rd_free,                 /* Remove this problem from the stack of dataflow problems.  */
664   df_rd_start_dump,           /* Debugging.  */
665   df_rd_top_dump,             /* Debugging start block.  */
666   df_rd_bottom_dump,          /* Debugging end block.  */
667   NULL,                       /* Incremental solution verify start.  */
668   NULL,                       /* Incremental solution verify end.  */
669   NULL,                       /* Dependent problem.  */
670   TV_DF_RD,                   /* Timing variable.  */ 
671   true                        /* Reset blocks on dropping out of blocks_to_analyze.  */
672 };
673
674
675
676 /* Create a new DATAFLOW instance and add it to an existing instance
677    of DF.  The returned structure is what is used to get at the
678    solution.  */
679
680 void
681 df_rd_add_problem (void)
682 {
683   df_add_problem (&problem_RD);
684 }
685
686
687 \f
688 /*----------------------------------------------------------------------------
689    LIVE REGISTERS
690
691    Find the locations in the function where any use of a pseudo can
692    reach in the backwards direction.  In and out bitvectors are built
693    for each basic block.  The regno is used to index into these sets.
694    See df.h for details.
695    ----------------------------------------------------------------------------*/
696
697 /* Private data used to verify the solution for this problem.  */
698 struct df_lr_problem_data
699 {
700   bitmap *in;
701   bitmap *out;
702 };
703
704
705 /* Set basic block info.  */
706
707 static void
708 df_lr_set_bb_info (unsigned int index, 
709                    struct df_lr_bb_info *bb_info)
710 {
711   gcc_assert (df_lr);
712   gcc_assert (index < df_lr->block_info_size);
713   df_lr->block_info[index] = bb_info;
714 }
715
716  
717 /* Free basic block info.  */
718
719 static void
720 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
721                     void *vbb_info)
722 {
723   struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
724   if (bb_info)
725     {
726       BITMAP_FREE (bb_info->use);
727       BITMAP_FREE (bb_info->def);
728       BITMAP_FREE (bb_info->in);
729       BITMAP_FREE (bb_info->out);
730       pool_free (df_lr->block_pool, bb_info);
731     }
732 }
733
734
735 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
736    not touched unless the block is new.  */
737
738 static void 
739 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
740 {
741   unsigned int bb_index;
742   bitmap_iterator bi;
743
744   if (!df_lr->block_pool)
745     df_lr->block_pool = create_alloc_pool ("df_lr_block pool", 
746                                            sizeof (struct df_lr_bb_info), 50);
747
748   df_grow_bb_info (df_lr);
749
750   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
751     {
752       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
753       if (bb_info)
754         { 
755           bitmap_clear (bb_info->def);
756           bitmap_clear (bb_info->use);
757         }
758       else
759         { 
760           bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
761           df_lr_set_bb_info (bb_index, bb_info);
762           bb_info->use = BITMAP_ALLOC (NULL);
763           bb_info->def = BITMAP_ALLOC (NULL);
764           bb_info->in = BITMAP_ALLOC (NULL);
765           bb_info->out = BITMAP_ALLOC (NULL);
766         }
767     }
768
769   df_lr->optional_p = false;
770 }
771
772
773 /* Reset the global solution for recalculation.  */
774
775 static void 
776 df_lr_reset (bitmap all_blocks)
777 {
778   unsigned int bb_index;
779   bitmap_iterator bi;
780
781   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
782     {
783       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
784       gcc_assert (bb_info);
785       bitmap_clear (bb_info->in);
786       bitmap_clear (bb_info->out);
787     }
788 }
789
790
791 /* Compute local live register info for basic block BB.  */
792
793 static void
794 df_lr_bb_local_compute (unsigned int bb_index)
795 {
796   basic_block bb = BASIC_BLOCK (bb_index);
797   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
798   rtx insn;
799   struct df_ref **def_rec;
800   struct df_ref **use_rec;
801
802   /* Process the registers set in an exception handler.  */
803   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
804     {
805       struct df_ref *def = *def_rec;
806       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
807         {
808           unsigned int dregno = DF_REF_REGNO (def);
809           bitmap_set_bit (bb_info->def, dregno);
810           bitmap_clear_bit (bb_info->use, dregno);
811         }
812     }
813
814   /* Process the hardware registers that are always live.  */
815   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
816     {
817       struct df_ref *use = *use_rec;
818       /* Add use to set of uses in this BB.  */
819       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
820         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
821     }
822
823   FOR_BB_INSNS_REVERSE (bb, insn)
824     {
825       unsigned int uid = INSN_UID (insn);
826
827       if (!INSN_P (insn))
828         continue;       
829
830       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
831         {
832           struct df_ref *def = *def_rec;
833           /* If the def is to only part of the reg, it does
834              not kill the other defs that reach here.  */
835           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
836             {
837               unsigned int dregno = DF_REF_REGNO (def);
838               bitmap_set_bit (bb_info->def, dregno);
839               bitmap_clear_bit (bb_info->use, dregno);
840             }
841         }
842
843       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
844         {
845           struct df_ref *use = *use_rec;
846           /* Add use to set of uses in this BB.  */
847           bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
848         }
849     }
850
851   /* Process the registers set in an exception handler or the hard
852      frame pointer if this block is the target of a non local
853      goto.  */
854   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
855     {
856       struct df_ref *def = *def_rec;
857       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
858         {
859           unsigned int dregno = DF_REF_REGNO (def);
860           bitmap_set_bit (bb_info->def, dregno);
861           bitmap_clear_bit (bb_info->use, dregno);
862         }
863     }
864   
865 #ifdef EH_USES
866   /* Process the uses that are live into an exception handler.  */
867   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
868     {
869       struct df_ref *use = *use_rec;
870       /* Add use to set of uses in this BB.  */
871       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
872         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
873     }
874 #endif
875
876   /* If the df_live problem is not defined, such as at -O0 and -O1, we
877      still need to keep the luids up to date.  This is normally done
878      in the df_live problem since this problem has a forwards
879      scan.  */
880   if (!df_live)
881     df_recompute_luids (bb);
882 }
883
884
885 /* Compute local live register info for each basic block within BLOCKS.  */
886
887 static void
888 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
889 {
890   unsigned int bb_index;
891   bitmap_iterator bi;
892     
893   bitmap_clear (df->hardware_regs_used);
894   
895   /* The all-important stack pointer must always be live.  */
896   bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
897   
898   /* Before reload, there are a few registers that must be forced
899      live everywhere -- which might not already be the case for
900      blocks within infinite loops.  */
901   if (!reload_completed)
902     {
903       /* Any reference to any pseudo before reload is a potential
904          reference of the frame pointer.  */
905       bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
906       
907 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
908       /* Pseudos with argument area equivalences may require
909          reloading via the argument pointer.  */
910       if (fixed_regs[ARG_POINTER_REGNUM])
911         bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
912 #endif
913       
914       /* Any constant, or pseudo with constant equivalences, may
915          require reloading from memory using the pic register.  */
916       if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
917           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
918         bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
919     }
920   
921   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
922     {
923       if (bb_index == EXIT_BLOCK)
924         {
925           /* The exit block is special for this problem and its bits are
926              computed from thin air.  */
927           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
928           bitmap_copy (bb_info->use, df->exit_block_uses);
929         }
930       else
931         df_lr_bb_local_compute (bb_index);
932     }
933
934   bitmap_clear (df_lr->out_of_date_transfer_functions);
935 }
936
937
938 /* Initialize the solution vectors.  */
939
940 static void 
941 df_lr_init (bitmap all_blocks)
942 {
943   unsigned int bb_index;
944   bitmap_iterator bi;
945
946   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
947     {
948       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
949       bitmap_copy (bb_info->in, bb_info->use);
950       bitmap_clear (bb_info->out);
951     }
952 }
953
954
955 /* Confluence function that processes infinite loops.  This might be a
956    noreturn function that throws.  And even if it isn't, getting the
957    unwind info right helps debugging.  */
958 static void
959 df_lr_confluence_0 (basic_block bb)
960 {
961   bitmap op1 = df_lr_get_bb_info (bb->index)->out;
962   if (bb != EXIT_BLOCK_PTR)
963     bitmap_copy (op1, df->hardware_regs_used);
964
965
966
967 /* Confluence function that ignores fake edges.  */
968
969 static void
970 df_lr_confluence_n (edge e)
971 {
972   bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
973   bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
974  
975   /* Call-clobbered registers die across exception and call edges.  */
976   /* ??? Abnormal call edges ignored for the moment, as this gets
977      confused by sibling call edges, which crashes reg-stack.  */
978   if (e->flags & EDGE_EH)
979     bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
980   else
981     bitmap_ior_into (op1, op2);
982
983   bitmap_ior_into (op1, df->hardware_regs_used);
984
985
986
987 /* Transfer function.  */
988
989 static bool
990 df_lr_transfer_function (int bb_index)
991 {
992   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
993   bitmap in = bb_info->in;
994   bitmap out = bb_info->out;
995   bitmap use = bb_info->use;
996   bitmap def = bb_info->def;
997
998   return bitmap_ior_and_compl (in, use, out, def);
999 }
1000
1001
1002 /* Run the fast dce as a side effect of building LR.  */
1003
1004 static void
1005 df_lr_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
1006 {
1007   if (df->changeable_flags & DF_LR_RUN_DCE)
1008     {
1009       run_fast_df_dce ();
1010       if (df_lr->problem_data && df_lr->solutions_dirty)
1011         {
1012           /* If we are here, then it is because we are both verifying
1013           the solution and the dce changed the function.  In that case
1014           the verification info built will be wrong.  So we leave the
1015           dirty flag true so that the verifier will skip the checking
1016           part and just clean up.*/
1017           df_lr->solutions_dirty = true;
1018         }
1019       else
1020         df_lr->solutions_dirty = false;
1021     }
1022   else
1023     df_lr->solutions_dirty = false;
1024 }
1025
1026
1027 /* Free all storage associated with the problem.  */
1028
1029 static void
1030 df_lr_free (void)
1031 {
1032   if (df_lr->block_info)
1033     {
1034       unsigned int i;
1035       for (i = 0; i < df_lr->block_info_size; i++)
1036         {
1037           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
1038           if (bb_info)
1039             {
1040               BITMAP_FREE (bb_info->use);
1041               BITMAP_FREE (bb_info->def);
1042               BITMAP_FREE (bb_info->in);
1043               BITMAP_FREE (bb_info->out);
1044             }
1045         }
1046       free_alloc_pool (df_lr->block_pool);
1047       
1048       df_lr->block_info_size = 0;
1049       free (df_lr->block_info);
1050     }
1051
1052   BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1053   free (df_lr);
1054 }
1055
1056
1057 /* Debugging info at top of bb.  */
1058
1059 static void
1060 df_lr_top_dump (basic_block bb, FILE *file)
1061 {
1062   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1063   struct df_lr_problem_data *problem_data;
1064   if (!bb_info || !bb_info->in)
1065     return;
1066       
1067   fprintf (file, ";; lr  in  \t");
1068   df_print_regset (file, bb_info->in);
1069   if (df_lr->problem_data)
1070     {
1071       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1072       fprintf (file, ";;  old in  \t");
1073       df_print_regset (file, problem_data->in[bb->index]);
1074     }
1075   fprintf (file, ";; lr  use \t");
1076   df_print_regset (file, bb_info->use);
1077   fprintf (file, ";; lr  def \t");
1078   df_print_regset (file, bb_info->def);
1079 }  
1080
1081
1082 /* Debugging info at bottom of bb.  */
1083
1084 static void
1085 df_lr_bottom_dump (basic_block bb, FILE *file)
1086 {
1087   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1088   struct df_lr_problem_data *problem_data;
1089   if (!bb_info || !bb_info->out)
1090     return;
1091   
1092   fprintf (file, ";; lr  out \t");
1093   df_print_regset (file, bb_info->out);
1094   if (df_lr->problem_data)
1095     {
1096       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1097       fprintf (file, ";;  old out  \t");
1098       df_print_regset (file, problem_data->out[bb->index]);
1099     }
1100 }  
1101
1102
1103 /* Build the datastructure to verify that the solution to the dataflow
1104    equations is not dirty.  */
1105
1106 static void
1107 df_lr_verify_solution_start (void)
1108 {
1109   basic_block bb;
1110   struct df_lr_problem_data *problem_data;
1111   if (df_lr->solutions_dirty)
1112     {
1113       df_lr->problem_data = NULL;
1114       return;
1115     }
1116
1117   /* Set it true so that the solution is recomputed.  */ 
1118   df_lr->solutions_dirty = true;
1119
1120   problem_data = XNEW (struct df_lr_problem_data);
1121   df_lr->problem_data = problem_data;
1122   problem_data->in = XNEWVEC (bitmap, last_basic_block);
1123   problem_data->out = XNEWVEC (bitmap, last_basic_block);
1124
1125   FOR_ALL_BB (bb)
1126     {
1127       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1128       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1129       bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1130       bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1131     }
1132 }
1133
1134
1135 /* Compare the saved datastructure and the new solution to the dataflow
1136    equations.  */
1137
1138 static void
1139 df_lr_verify_solution_end (void)
1140 {
1141   struct df_lr_problem_data *problem_data;
1142   basic_block bb;
1143
1144   if (df_lr->problem_data == NULL)
1145     return;
1146
1147   problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1148
1149   if (df_lr->solutions_dirty)
1150     /* Do not check if the solution is still dirty.  See the comment
1151        in df_lr_finalize for details.  */
1152     df_lr->solutions_dirty = false;
1153   else
1154     FOR_ALL_BB (bb)
1155       {
1156         if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1157             || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1158           {
1159             /*df_dump (stderr);*/
1160             gcc_unreachable ();
1161           }
1162       }
1163
1164   /* Cannot delete them immediately because you may want to dump them
1165      if the comparison fails.  */
1166   FOR_ALL_BB (bb)
1167     {
1168       BITMAP_FREE (problem_data->in[bb->index]);
1169       BITMAP_FREE (problem_data->out[bb->index]);
1170     }
1171
1172   free (problem_data->in);
1173   free (problem_data->out);
1174   free (problem_data);
1175   df_lr->problem_data = NULL;
1176 }
1177
1178
1179 /* All of the information associated with every instance of the problem.  */
1180
1181 static struct df_problem problem_LR =
1182 {
1183   DF_LR,                      /* Problem id.  */
1184   DF_BACKWARD,                /* Direction.  */
1185   df_lr_alloc,                /* Allocate the problem specific data.  */
1186   df_lr_reset,                /* Reset global information.  */
1187   df_lr_free_bb_info,         /* Free basic block info.  */
1188   df_lr_local_compute,        /* Local compute function.  */
1189   df_lr_init,                 /* Init the solution specific data.  */
1190   df_worklist_dataflow,       /* Worklist solver.  */
1191   df_lr_confluence_0,         /* Confluence operator 0.  */ 
1192   df_lr_confluence_n,         /* Confluence operator n.  */ 
1193   df_lr_transfer_function,    /* Transfer function.  */
1194   df_lr_finalize,             /* Finalize function.  */
1195   df_lr_free,                 /* Free all of the problem information.  */
1196   NULL,                       /* Remove this problem from the stack of dataflow problems.  */
1197   NULL,                       /* Debugging.  */
1198   df_lr_top_dump,             /* Debugging start block.  */
1199   df_lr_bottom_dump,          /* Debugging end block.  */
1200   df_lr_verify_solution_start,/* Incremental solution verify start.  */
1201   df_lr_verify_solution_end,  /* Incremental solution verify end.  */
1202   NULL,                       /* Dependent problem.  */
1203   TV_DF_LR,                   /* Timing variable.  */ 
1204   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
1205 };
1206
1207
1208 /* Create a new DATAFLOW instance and add it to an existing instance
1209    of DF.  The returned structure is what is used to get at the
1210    solution.  */
1211
1212 void
1213 df_lr_add_problem (void)
1214 {
1215   df_add_problem (&problem_LR);
1216   /* These will be initialized when df_scan_blocks processes each
1217      block.  */
1218   df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1219 }
1220
1221
1222 /* Verify that all of the lr related info is consistent and
1223    correct.  */
1224
1225 void
1226 df_lr_verify_transfer_functions (void)
1227 {
1228   basic_block bb;
1229   bitmap saved_def;
1230   bitmap saved_use;
1231   bitmap saved_adef;
1232   bitmap saved_ause;
1233   bitmap all_blocks;
1234
1235   if (!df)
1236     return;
1237
1238   saved_def = BITMAP_ALLOC (NULL);
1239   saved_use = BITMAP_ALLOC (NULL);
1240   saved_adef = BITMAP_ALLOC (NULL);
1241   saved_ause = BITMAP_ALLOC (NULL);
1242   all_blocks = BITMAP_ALLOC (NULL);
1243
1244   FOR_ALL_BB (bb)
1245     {
1246       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1247       bitmap_set_bit (all_blocks, bb->index);
1248
1249       if (bb_info)
1250         {
1251           /* Make a copy of the transfer functions and then compute
1252              new ones to see if the transfer functions have
1253              changed.  */
1254           if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions, 
1255                              bb->index))
1256             {
1257               bitmap_copy (saved_def, bb_info->def);
1258               bitmap_copy (saved_use, bb_info->use);
1259               bitmap_clear (bb_info->def);
1260               bitmap_clear (bb_info->use);
1261
1262               df_lr_bb_local_compute (bb->index);
1263               gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1264               gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
1265             }
1266         }
1267       else
1268         {
1269           /* If we do not have basic block info, the block must be in
1270              the list of dirty blocks or else some one has added a
1271              block behind our backs. */
1272           gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions, 
1273                                     bb->index));
1274         }
1275       /* Make sure no one created a block without following
1276          procedures.  */
1277       gcc_assert (df_scan_get_bb_info (bb->index));
1278     }
1279
1280   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1281   gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions, 
1282                                          all_blocks)); 
1283
1284   BITMAP_FREE (saved_def);
1285   BITMAP_FREE (saved_use);
1286   BITMAP_FREE (saved_adef);
1287   BITMAP_FREE (saved_ause);
1288   BITMAP_FREE (all_blocks);
1289 }
1290
1291
1292 \f
1293 /*----------------------------------------------------------------------------
1294    LIVE AND MUST-INITIALIZED REGISTERS.
1295
1296    This problem first computes the IN and OUT bitvectors for the
1297    must-initialized registers problems, which is a forward problem.
1298    It gives the set of registers for which we MUST have an available
1299    definition on any path from the entry block to the entry/exit of
1300    a basic block.  Sets generate a definition, while clobbers kill
1301    a definition.
1302
1303    In and out bitvectors are built for each basic block and are indexed by
1304    regnum (see df.h for details).  In and out bitvectors in struct
1305    df_live_bb_info actually refers to the must-initialized problem;
1306
1307    Then, the in and out sets for the LIVE problem itself are computed.
1308    These are the logical AND of the IN and OUT sets from the LR problem
1309    and the must-initialized problem. 
1310 ----------------------------------------------------------------------------*/
1311
1312 /* Private data used to verify the solution for this problem.  */
1313 struct df_live_problem_data
1314 {
1315   bitmap *in;
1316   bitmap *out;
1317 };
1318
1319 /* Scratch var used by transfer functions.  This is used to implement
1320    an optimization to reduce the amount of space used to compute the
1321    combined lr and live analysis.  */
1322 static bitmap df_live_scratch;
1323
1324 /* Set basic block info.  */
1325
1326 static void
1327 df_live_set_bb_info (unsigned int index, 
1328                    struct df_live_bb_info *bb_info)
1329 {
1330   gcc_assert (df_live);
1331   gcc_assert (index < df_live->block_info_size);
1332   df_live->block_info[index] = bb_info;
1333 }
1334
1335
1336 /* Free basic block info.  */
1337
1338 static void
1339 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
1340                     void *vbb_info)
1341 {
1342   struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1343   if (bb_info)
1344     {
1345       BITMAP_FREE (bb_info->gen);
1346       BITMAP_FREE (bb_info->kill);
1347       BITMAP_FREE (bb_info->in);
1348       BITMAP_FREE (bb_info->out);
1349       pool_free (df_live->block_pool, bb_info);
1350     }
1351 }
1352
1353
1354 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1355    not touched unless the block is new.  */
1356
1357 static void 
1358 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1359 {
1360   unsigned int bb_index;
1361   bitmap_iterator bi;
1362
1363   if (!df_live->block_pool)
1364     df_live->block_pool = create_alloc_pool ("df_live_block pool", 
1365                                            sizeof (struct df_live_bb_info), 100);
1366   if (!df_live_scratch)
1367     df_live_scratch = BITMAP_ALLOC (NULL);
1368
1369   df_grow_bb_info (df_live);
1370
1371   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1372     {
1373       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1374       if (bb_info)
1375         { 
1376           bitmap_clear (bb_info->kill);
1377           bitmap_clear (bb_info->gen);
1378         }
1379       else
1380         { 
1381           bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1382           df_live_set_bb_info (bb_index, bb_info);
1383           bb_info->kill = BITMAP_ALLOC (NULL);
1384           bb_info->gen = BITMAP_ALLOC (NULL);
1385           bb_info->in = BITMAP_ALLOC (NULL);
1386           bb_info->out = BITMAP_ALLOC (NULL);
1387         }
1388     }
1389   df_live->optional_p = (optimize <= 1);
1390 }
1391
1392
1393 /* Reset the global solution for recalculation.  */
1394
1395 static void 
1396 df_live_reset (bitmap all_blocks)
1397 {
1398   unsigned int bb_index;
1399   bitmap_iterator bi;
1400
1401   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1402     {
1403       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1404       gcc_assert (bb_info);
1405       bitmap_clear (bb_info->in);
1406       bitmap_clear (bb_info->out);
1407     }
1408 }
1409
1410
1411 /* Compute local uninitialized register info for basic block BB.  */
1412
1413 static void
1414 df_live_bb_local_compute (unsigned int bb_index)
1415 {
1416   basic_block bb = BASIC_BLOCK (bb_index);
1417   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1418   rtx insn;
1419   struct df_ref **def_rec;
1420   int luid = 0;
1421
1422   FOR_BB_INSNS (bb, insn)
1423     {
1424       unsigned int uid = INSN_UID (insn);
1425       struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1426
1427       /* Inserting labels does not always trigger the incremental
1428          rescanning.  */
1429       if (!insn_info)
1430         {
1431           gcc_assert (!INSN_P (insn));
1432           df_insn_create_insn_record (insn);
1433         }
1434
1435       DF_INSN_LUID (insn) = luid;
1436       if (!INSN_P (insn))
1437         continue;
1438
1439       luid++;
1440       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1441         {
1442           struct df_ref *def = *def_rec;
1443           unsigned int regno = DF_REF_REGNO (def);
1444
1445           if (DF_REF_FLAGS_IS_SET (def,
1446                                    DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1447             /* All partial or conditional def
1448                seen are included in the gen set. */
1449             bitmap_set_bit (bb_info->gen, regno);
1450           else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1451             /* Only must clobbers for the entire reg destroy the
1452                value.  */
1453             bitmap_set_bit (bb_info->kill, regno);
1454           else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1455             bitmap_set_bit (bb_info->gen, regno);
1456         }
1457     }
1458
1459   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1460     {
1461       struct df_ref *def = *def_rec;
1462       bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
1463     }
1464 }
1465
1466
1467 /* Compute local uninitialized register info.  */
1468
1469 static void
1470 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1471 {
1472   unsigned int bb_index;
1473   bitmap_iterator bi;
1474
1475   df_grow_insn_info ();
1476
1477   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 
1478                             0, bb_index, bi)
1479     {
1480       df_live_bb_local_compute (bb_index);
1481     }
1482
1483   bitmap_clear (df_live->out_of_date_transfer_functions);
1484 }
1485
1486
1487 /* Initialize the solution vectors.  */
1488
1489 static void 
1490 df_live_init (bitmap all_blocks)
1491 {
1492   unsigned int bb_index;
1493   bitmap_iterator bi;
1494
1495   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1496     {
1497       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1498       struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1499
1500       /* No register may reach a location where it is not used.  Thus
1501          we trim the rr result to the places where it is used.  */
1502       bitmap_and (bb_info->out, bb_info->gen, bb_lr_info->out);
1503       bitmap_clear (bb_info->in);
1504     }
1505 }
1506
1507 /* Forward confluence function that ignores fake edges.  */
1508
1509 static void
1510 df_live_confluence_n (edge e)
1511 {
1512   bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
1513   bitmap op2 = df_live_get_bb_info (e->src->index)->out;
1514  
1515   if (e->flags & EDGE_FAKE) 
1516     return;
1517
1518   bitmap_ior_into (op1, op2);
1519
1520
1521
1522 /* Transfer function for the forwards must-initialized problem.  */
1523
1524 static bool
1525 df_live_transfer_function (int bb_index)
1526 {
1527   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1528   struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1529   bitmap in = bb_info->in;
1530   bitmap out = bb_info->out;
1531   bitmap gen = bb_info->gen;
1532   bitmap kill = bb_info->kill;
1533
1534   /* We need to use a scratch set here so that the value returned from
1535      this function invocation properly reflects if the sets changed in
1536      a significant way; i.e. not just because the lr set was anded
1537      in.  */
1538   bitmap_and (df_live_scratch, gen, bb_lr_info->out);
1539   /* No register may reach a location where it is not used.  Thus
1540      we trim the rr result to the places where it is used.  */
1541   bitmap_and_into (in, bb_lr_info->in);
1542
1543   return bitmap_ior_and_compl (out, df_live_scratch, in, kill);
1544 }
1545
1546
1547 /* And the LR info with the must-initialized registers, to produce the LIVE info.  */
1548
1549 static void
1550 df_live_finalize (bitmap all_blocks)
1551 {
1552
1553   if (df_live->solutions_dirty)
1554     {
1555       bitmap_iterator bi;
1556       unsigned int bb_index;
1557
1558       EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1559         {
1560           struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1561           struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1562   
1563           /* No register may reach a location where it is not used.  Thus
1564              we trim the rr result to the places where it is used.  */
1565           bitmap_and_into (bb_live_info->in, bb_lr_info->in);
1566           bitmap_and_into (bb_live_info->out, bb_lr_info->out);
1567         }
1568       
1569       df_live->solutions_dirty = false;
1570     }
1571 }
1572
1573
1574 /* Free all storage associated with the problem.  */
1575
1576 static void
1577 df_live_free (void)
1578 {
1579   if (df_live->block_info)
1580     {
1581       unsigned int i;
1582       
1583       for (i = 0; i < df_live->block_info_size; i++)
1584         {
1585           struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
1586           if (bb_info)
1587             {
1588               BITMAP_FREE (bb_info->gen);
1589               BITMAP_FREE (bb_info->kill);
1590               BITMAP_FREE (bb_info->in);
1591               BITMAP_FREE (bb_info->out);
1592             }
1593         }
1594       
1595       free_alloc_pool (df_live->block_pool);
1596       df_live->block_info_size = 0;
1597       free (df_live->block_info);
1598
1599       if (df_live_scratch)
1600         BITMAP_FREE (df_live_scratch);
1601     }
1602   BITMAP_FREE (df_live->out_of_date_transfer_functions);
1603   free (df_live);
1604 }
1605
1606
1607 /* Debugging info at top of bb.  */
1608
1609 static void
1610 df_live_top_dump (basic_block bb, FILE *file)
1611 {
1612   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1613   struct df_live_problem_data *problem_data;
1614
1615   if (!bb_info || !bb_info->in)
1616     return;
1617       
1618   fprintf (file, ";; live  in  \t");
1619   df_print_regset (file, bb_info->in);
1620   if (df_live->problem_data)
1621     {
1622       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1623       fprintf (file, ";;  old in  \t");
1624       df_print_regset (file, problem_data->in[bb->index]);
1625     }
1626   fprintf (file, ";; live  gen \t");
1627   df_print_regset (file, bb_info->gen);
1628   fprintf (file, ";; live  kill\t");
1629   df_print_regset (file, bb_info->kill);
1630 }
1631
1632
1633 /* Debugging info at bottom of bb.  */
1634
1635 static void
1636 df_live_bottom_dump (basic_block bb, FILE *file)
1637 {
1638   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1639   struct df_live_problem_data *problem_data;
1640
1641   if (!bb_info || !bb_info->out)
1642     return;
1643       
1644   fprintf (file, ";; live  out \t");
1645   df_print_regset (file, bb_info->out);
1646   if (df_live->problem_data)
1647     {
1648       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1649       fprintf (file, ";;  old out  \t");
1650       df_print_regset (file, problem_data->out[bb->index]);
1651     }
1652 }
1653
1654
1655 /* Build the datastructure to verify that the solution to the dataflow
1656    equations is not dirty.  */
1657
1658 static void
1659 df_live_verify_solution_start (void)
1660 {
1661   basic_block bb;
1662   struct df_live_problem_data *problem_data;
1663   if (df_live->solutions_dirty)
1664     {
1665       df_live->problem_data = NULL;
1666       return;
1667     }
1668
1669   /* Set it true so that the solution is recomputed.  */ 
1670   df_live->solutions_dirty = true;
1671
1672   problem_data = XNEW (struct df_live_problem_data);
1673   df_live->problem_data = problem_data;
1674   problem_data->in = XNEWVEC (bitmap, last_basic_block);
1675   problem_data->out = XNEWVEC (bitmap, last_basic_block);
1676
1677   FOR_ALL_BB (bb)
1678     {
1679       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1680       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1681       bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
1682       bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
1683     }
1684 }
1685
1686
1687 /* Compare the saved datastructure and the new solution to the dataflow
1688    equations.  */
1689
1690 static void
1691 df_live_verify_solution_end (void)
1692 {
1693   struct df_live_problem_data *problem_data;
1694   basic_block bb;
1695
1696   if (df_live->problem_data == NULL)
1697     return;
1698
1699   problem_data = (struct df_live_problem_data *)df_live->problem_data;
1700
1701   FOR_ALL_BB (bb)
1702     {
1703       if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
1704           || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1705         {
1706           /*df_dump (stderr);*/
1707           gcc_unreachable ();
1708         }
1709     }
1710
1711   /* Cannot delete them immediately because you may want to dump them
1712      if the comparison fails.  */
1713   FOR_ALL_BB (bb)
1714     {
1715       BITMAP_FREE (problem_data->in[bb->index]);
1716       BITMAP_FREE (problem_data->out[bb->index]);
1717     }
1718
1719   free (problem_data->in);
1720   free (problem_data->out);
1721   free (problem_data);
1722   df_live->problem_data = NULL;
1723 }
1724
1725
1726 /* All of the information associated with every instance of the problem.  */
1727
1728 static struct df_problem problem_LIVE =
1729 {
1730   DF_LIVE,                      /* Problem id.  */
1731   DF_FORWARD,                   /* Direction.  */
1732   df_live_alloc,                /* Allocate the problem specific data.  */
1733   df_live_reset,                /* Reset global information.  */
1734   df_live_free_bb_info,         /* Free basic block info.  */
1735   df_live_local_compute,        /* Local compute function.  */
1736   df_live_init,                 /* Init the solution specific data.  */
1737   df_worklist_dataflow,         /* Worklist solver.  */
1738   NULL,                         /* Confluence operator 0.  */ 
1739   df_live_confluence_n,         /* Confluence operator n.  */ 
1740   df_live_transfer_function,    /* Transfer function.  */
1741   df_live_finalize,             /* Finalize function.  */
1742   df_live_free,                 /* Free all of the problem information.  */
1743   df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
1744   NULL,                         /* Debugging.  */
1745   df_live_top_dump,             /* Debugging start block.  */
1746   df_live_bottom_dump,          /* Debugging end block.  */
1747   df_live_verify_solution_start,/* Incremental solution verify start.  */
1748   df_live_verify_solution_end,  /* Incremental solution verify end.  */
1749   &problem_LR,                  /* Dependent problem.  */
1750   TV_DF_LIVE,                   /* Timing variable.  */
1751   false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
1752 };
1753
1754
1755 /* Create a new DATAFLOW instance and add it to an existing instance
1756    of DF.  The returned structure is what is used to get at the
1757    solution.  */
1758
1759 void
1760 df_live_add_problem (void)
1761 {
1762   df_add_problem (&problem_LIVE);
1763   /* These will be initialized when df_scan_blocks processes each
1764      block.  */
1765   df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1766 }
1767
1768
1769 /* Set all of the blocks as dirty.  This needs to be done if this
1770    problem is added after all of the insns have been scanned.  */
1771
1772 void
1773 df_live_set_all_dirty (void)
1774 {
1775   basic_block bb;
1776   FOR_ALL_BB (bb)
1777     bitmap_set_bit (df_live->out_of_date_transfer_functions, 
1778                     bb->index);
1779 }
1780
1781
1782 /* Verify that all of the lr related info is consistent and
1783    correct.  */
1784
1785 void
1786 df_live_verify_transfer_functions (void)
1787 {
1788   basic_block bb;
1789   bitmap saved_gen;
1790   bitmap saved_kill;
1791   bitmap all_blocks;
1792
1793   if (!df)
1794     return;
1795
1796   saved_gen = BITMAP_ALLOC (NULL);
1797   saved_kill = BITMAP_ALLOC (NULL);
1798   all_blocks = BITMAP_ALLOC (NULL);
1799
1800   df_grow_insn_info ();
1801
1802   FOR_ALL_BB (bb)
1803     {
1804       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1805       bitmap_set_bit (all_blocks, bb->index);
1806
1807       if (bb_info)
1808         {
1809           /* Make a copy of the transfer functions and then compute
1810              new ones to see if the transfer functions have
1811              changed.  */
1812           if (!bitmap_bit_p (df_live->out_of_date_transfer_functions, 
1813                              bb->index))
1814             {
1815               bitmap_copy (saved_gen, bb_info->gen);
1816               bitmap_copy (saved_kill, bb_info->kill);
1817               bitmap_clear (bb_info->gen);
1818               bitmap_clear (bb_info->kill);
1819
1820               df_live_bb_local_compute (bb->index);
1821               gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
1822               gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
1823             }
1824         }
1825       else
1826         {
1827           /* If we do not have basic block info, the block must be in
1828              the list of dirty blocks or else some one has added a
1829              block behind our backs. */
1830           gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions, 
1831                                     bb->index));
1832         }
1833       /* Make sure no one created a block without following
1834          procedures.  */
1835       gcc_assert (df_scan_get_bb_info (bb->index));
1836     }
1837
1838   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1839   gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions, 
1840                                          all_blocks)); 
1841   BITMAP_FREE (saved_gen);
1842   BITMAP_FREE (saved_kill);
1843   BITMAP_FREE (all_blocks);
1844 }
1845 \f
1846 /*----------------------------------------------------------------------------
1847    CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1848
1849    Link either the defs to the uses and / or the uses to the defs.
1850
1851    These problems are set up like the other dataflow problems so that
1852    they nicely fit into the framework.  They are much simpler and only
1853    involve a single traversal of instructions and an examination of
1854    the reaching defs information (the dependent problem).
1855 ----------------------------------------------------------------------------*/
1856
1857 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1858
1859 /* Create a du or ud chain from SRC to DST and link it into SRC.   */
1860
1861 struct df_link *
1862 df_chain_create (struct df_ref *src, struct df_ref *dst)
1863 {
1864   struct df_link *head = DF_REF_CHAIN (src);
1865   struct df_link *link = pool_alloc (df_chain->block_pool);
1866   
1867   DF_REF_CHAIN (src) = link;
1868   link->next = head;
1869   link->ref = dst;
1870   return link;
1871 }
1872
1873
1874 /* Delete any du or ud chains that start at REF and point to
1875    TARGET.  */ 
1876 static void
1877 df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
1878 {
1879   struct df_link *chain = DF_REF_CHAIN (ref);
1880   struct df_link *prev = NULL;
1881
1882   while (chain)
1883     {
1884       if (chain->ref == target)
1885         {
1886           if (prev)
1887             prev->next = chain->next;
1888           else
1889             DF_REF_CHAIN (ref) = chain->next;
1890           pool_free (df_chain->block_pool, chain);
1891           return;
1892         }
1893       prev = chain;
1894       chain = chain->next;
1895     }
1896 }
1897
1898
1899 /* Delete a du or ud chain that leave or point to REF.  */
1900
1901 void
1902 df_chain_unlink (struct df_ref *ref)
1903 {
1904   struct df_link *chain = DF_REF_CHAIN (ref);
1905   while (chain)
1906     {
1907       struct df_link *next = chain->next;
1908       /* Delete the other side if it exists.  */
1909       df_chain_unlink_1 (chain->ref, ref);
1910       pool_free (df_chain->block_pool, chain);
1911       chain = next;
1912     }
1913   DF_REF_CHAIN (ref) = NULL;
1914 }
1915
1916
1917 /* Copy the du or ud chain starting at FROM_REF and attach it to
1918    TO_REF.  */ 
1919
1920 void 
1921 df_chain_copy (struct df_ref *to_ref, 
1922                struct df_link *from_ref)
1923 {
1924   while (from_ref)
1925     {
1926       df_chain_create (to_ref, from_ref->ref);
1927       from_ref = from_ref->next;
1928     }
1929 }
1930
1931
1932 /* Remove this problem from the stack of dataflow problems.  */
1933
1934 static void
1935 df_chain_remove_problem (void)
1936 {
1937   bitmap_iterator bi;
1938   unsigned int bb_index;
1939
1940   /* Wholesale destruction of the old chains.  */ 
1941   if (df_chain->block_pool)
1942     free_alloc_pool (df_chain->block_pool);
1943
1944   EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1945     {
1946       rtx insn;
1947       struct df_ref **def_rec;
1948       struct df_ref **use_rec;
1949       basic_block bb = BASIC_BLOCK (bb_index);
1950
1951       if (df_chain_problem_p (DF_DU_CHAIN))
1952         for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1953           DF_REF_CHAIN (*def_rec) = NULL;
1954       if (df_chain_problem_p (DF_UD_CHAIN))
1955         for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
1956           DF_REF_CHAIN (*use_rec) = NULL;
1957       
1958       FOR_BB_INSNS (bb, insn)
1959         {
1960           unsigned int uid = INSN_UID (insn);
1961           
1962           if (INSN_P (insn))
1963             {
1964               if (df_chain_problem_p (DF_DU_CHAIN))
1965                 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1966                   DF_REF_CHAIN (*def_rec) = NULL;
1967               if (df_chain_problem_p (DF_UD_CHAIN))
1968                 {
1969                   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1970                     DF_REF_CHAIN (*use_rec) = NULL;
1971                   for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1972                     DF_REF_CHAIN (*use_rec) = NULL;
1973                 }
1974             }
1975         }
1976     }
1977
1978   bitmap_clear (df_chain->out_of_date_transfer_functions);
1979   df_chain->block_pool = NULL;
1980 }
1981
1982
1983 /* Remove the chain problem completely.  */
1984
1985 static void
1986 df_chain_fully_remove_problem (void)
1987 {
1988   df_chain_remove_problem ();
1989   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
1990   free (df_chain);
1991 }
1992
1993
1994 /* Create def-use or use-def chains.  */
1995
1996 static void  
1997 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1998 {
1999   df_chain_remove_problem ();
2000   df_chain->block_pool = create_alloc_pool ("df_chain_block pool", 
2001                                          sizeof (struct df_link), 50);
2002   df_chain->optional_p = true;
2003 }
2004
2005
2006 /* Reset all of the chains when the set of basic blocks changes.  */
2007
2008 static void
2009 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2010 {
2011   df_chain_remove_problem ();
2012 }
2013
2014
2015 /* Create the chains for a list of USEs.  */
2016
2017 static void
2018 df_chain_create_bb_process_use (bitmap local_rd,
2019                                 struct df_ref **use_rec,
2020                                 enum df_ref_flags top_flag)
2021 {
2022   bitmap_iterator bi;
2023   unsigned int def_index;
2024   
2025   while (*use_rec)
2026     {
2027       struct df_ref *use = *use_rec;
2028       unsigned int uregno = DF_REF_REGNO (use);
2029       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2030           || (uregno >= FIRST_PSEUDO_REGISTER))
2031         {
2032           /* Do not want to go through this for an uninitialized var.  */
2033           int count = DF_DEFS_COUNT (uregno);
2034           if (count)
2035             {
2036               if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2037                 {
2038                   unsigned int first_index = DF_DEFS_BEGIN (uregno);
2039                   unsigned int last_index = first_index + count - 1;
2040                   
2041                   EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2042                     {
2043                       struct df_ref *def;
2044                       if (def_index > last_index) 
2045                         break;
2046                       
2047                       def = DF_DEFS_GET (def_index);
2048                       if (df_chain_problem_p (DF_DU_CHAIN))
2049                         df_chain_create (def, use);
2050                       if (df_chain_problem_p (DF_UD_CHAIN))
2051                         df_chain_create (use, def);
2052                     }
2053                 }
2054             }
2055         }
2056
2057       use_rec++;
2058     }
2059 }
2060
2061
2062 /* Create chains from reaching defs bitmaps for basic block BB.  */
2063
2064 static void
2065 df_chain_create_bb (unsigned int bb_index)
2066 {
2067   basic_block bb = BASIC_BLOCK (bb_index);
2068   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2069   rtx insn;
2070   bitmap cpy = BITMAP_ALLOC (NULL);
2071   struct df_ref **def_rec;
2072
2073   bitmap_copy (cpy, bb_info->in);
2074   bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2075
2076   /* Since we are going forwards, process the artificial uses first
2077      then the artificial defs second.  */
2078
2079 #ifdef EH_USES
2080   /* Create the chains for the artificial uses from the EH_USES at the
2081      beginning of the block.  */
2082   
2083   /* Artificials are only hard regs.  */
2084   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2085     df_chain_create_bb_process_use (cpy,
2086                                     df_get_artificial_uses (bb->index), 
2087                                     DF_REF_AT_TOP);
2088 #endif
2089
2090   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2091     {
2092       struct df_ref *def = *def_rec;
2093       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2094         {
2095           unsigned int dregno = DF_REF_REGNO (def);
2096           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2097             bitmap_clear_range (cpy, 
2098                                 DF_DEFS_BEGIN (dregno), 
2099                                 DF_DEFS_COUNT (dregno));
2100           bitmap_set_bit (cpy, DF_REF_ID (def));
2101         }
2102     }
2103   
2104   /* Process the regular instructions next.  */
2105   FOR_BB_INSNS (bb, insn)
2106     {
2107       struct df_ref **def_rec;
2108       unsigned int uid = INSN_UID (insn);
2109
2110       if (!INSN_P (insn))
2111         continue;
2112
2113       /* Now scan the uses and link them up with the defs that remain
2114          in the cpy vector.  */
2115       
2116       df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
2117
2118       if (df->changeable_flags & DF_EQ_NOTES)
2119         df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
2120
2121
2122       /* Since we are going forwards, process the defs second.  This
2123          pass only changes the bits in cpy.  */
2124       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2125         {
2126           struct df_ref *def = *def_rec;
2127           unsigned int dregno = DF_REF_REGNO (def);
2128           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2129               || (dregno >= FIRST_PSEUDO_REGISTER))
2130             {
2131               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2132                 bitmap_clear_range (cpy, 
2133                                     DF_DEFS_BEGIN (dregno), 
2134                                     DF_DEFS_COUNT (dregno));
2135               if (!(DF_REF_FLAGS (def) 
2136                     & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
2137                 bitmap_set_bit (cpy, DF_REF_ID (def));
2138             }
2139         }
2140     }
2141
2142   /* Create the chains for the artificial uses of the hard registers
2143      at the end of the block.  */
2144   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2145     df_chain_create_bb_process_use (cpy,
2146                                     df_get_artificial_uses (bb->index), 
2147                                     0);
2148
2149   BITMAP_FREE (cpy);
2150 }
2151
2152 /* Create def-use chains from reaching use bitmaps for basic blocks
2153    in BLOCKS.  */
2154
2155 static void
2156 df_chain_finalize (bitmap all_blocks)
2157 {
2158   unsigned int bb_index;
2159   bitmap_iterator bi;
2160   
2161   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2162     {
2163       df_chain_create_bb (bb_index);
2164     }
2165 }
2166
2167
2168 /* Free all storage associated with the problem.  */
2169
2170 static void
2171 df_chain_free (void)
2172 {
2173   free_alloc_pool (df_chain->block_pool);
2174   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2175   free (df_chain);
2176 }
2177
2178
2179 /* Debugging info.  */
2180
2181 static void
2182 df_chain_top_dump (basic_block bb, FILE *file)
2183 {
2184   if (df_chain_problem_p (DF_DU_CHAIN))
2185     {
2186       rtx insn;
2187       struct df_ref **def_rec = df_get_artificial_defs (bb->index);
2188       if (*def_rec)
2189         {
2190           
2191           fprintf (file, ";;  DU chains for artificial defs\n");
2192           while (*def_rec)
2193             {
2194               struct df_ref *def = *def_rec;
2195               fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
2196               df_chain_dump (DF_REF_CHAIN (def), file);
2197               fprintf (file, "\n");
2198               def_rec++;
2199             }
2200         }      
2201
2202       FOR_BB_INSNS (bb, insn)
2203         {
2204           unsigned int uid = INSN_UID (insn);
2205           if (INSN_P (insn))
2206             {
2207               def_rec = DF_INSN_UID_DEFS (uid);
2208               if (*def_rec)
2209                 {
2210                   fprintf (file, ";;   DU chains for insn luid %d uid %d\n", 
2211                            DF_INSN_LUID (insn), uid);
2212                   
2213                   while (*def_rec)
2214                     {
2215                       struct df_ref *def = *def_rec;
2216                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
2217                       if (def->flags & DF_REF_READ_WRITE)
2218                         fprintf (file, "read/write ");
2219                       df_chain_dump (DF_REF_CHAIN (def), file);
2220                       fprintf (file, "\n");
2221                       def_rec++;
2222                     }
2223                 }
2224             }
2225         }
2226     }
2227 }
2228
2229
2230 static void
2231 df_chain_bottom_dump (basic_block bb, FILE *file)
2232 {
2233   if (df_chain_problem_p (DF_UD_CHAIN))
2234     {
2235       rtx insn;
2236       struct df_ref **use_rec = df_get_artificial_uses (bb->index);
2237
2238       if (*use_rec)
2239         {
2240           fprintf (file, ";;  UD chains for artificial uses\n");
2241           while (*use_rec)
2242             {
2243               struct df_ref *use = *use_rec;
2244               fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
2245               df_chain_dump (DF_REF_CHAIN (use), file);
2246               fprintf (file, "\n");
2247               use_rec++;
2248             }
2249         }      
2250
2251       FOR_BB_INSNS (bb, insn)
2252         {
2253           unsigned int uid = INSN_UID (insn);
2254           if (INSN_P (insn))
2255             {
2256               struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid);
2257               use_rec = DF_INSN_UID_USES (uid);
2258               if (*use_rec || *eq_use_rec)
2259                 {
2260                   fprintf (file, ";;   UD chains for insn luid %d uid %d\n", 
2261                            DF_INSN_LUID (insn), uid);
2262                   
2263                   while (*use_rec)
2264                     {
2265                       struct df_ref *use = *use_rec;
2266                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
2267                       if (use->flags & DF_REF_READ_WRITE)
2268                         fprintf (file, "read/write ");
2269                       df_chain_dump (DF_REF_CHAIN (use), file);
2270                       fprintf (file, "\n");
2271                       use_rec++;
2272                     }
2273                   while (*eq_use_rec)
2274                     {
2275                       struct df_ref *use = *eq_use_rec;
2276                       fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
2277                       df_chain_dump (DF_REF_CHAIN (use), file);
2278                       fprintf (file, "\n");
2279                       eq_use_rec++;
2280                     }
2281                 }
2282             }
2283         }
2284     }
2285 }
2286
2287
2288 static struct df_problem problem_CHAIN =
2289 {
2290   DF_CHAIN,                   /* Problem id.  */
2291   DF_NONE,                    /* Direction.  */
2292   df_chain_alloc,             /* Allocate the problem specific data.  */
2293   df_chain_reset,             /* Reset global information.  */
2294   NULL,                       /* Free basic block info.  */
2295   NULL,                       /* Local compute function.  */
2296   NULL,                       /* Init the solution specific data.  */
2297   NULL,                       /* Iterative solver.  */
2298   NULL,                       /* Confluence operator 0.  */ 
2299   NULL,                       /* Confluence operator n.  */ 
2300   NULL,                       /* Transfer function.  */
2301   df_chain_finalize,          /* Finalize function.  */
2302   df_chain_free,              /* Free all of the problem information.  */
2303   df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
2304   NULL,                       /* Debugging.  */
2305   df_chain_top_dump,          /* Debugging start block.  */
2306   df_chain_bottom_dump,       /* Debugging end block.  */
2307   NULL,                       /* Incremental solution verify start.  */
2308   NULL,                       /* Incremental solution verify end.  */
2309   &problem_RD,                /* Dependent problem.  */
2310   TV_DF_CHAIN,                /* Timing variable.  */
2311   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2312 };
2313
2314
2315 /* Create a new DATAFLOW instance and add it to an existing instance
2316    of DF.  The returned structure is what is used to get at the
2317    solution.  */
2318
2319 void
2320 df_chain_add_problem (enum df_chain_flags chain_flags)
2321 {
2322   df_add_problem (&problem_CHAIN);
2323   df_chain->local_flags = (unsigned int)chain_flags;
2324   df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2325 }
2326
2327 #undef df_chain_problem_p
2328
2329 \f
2330 /*----------------------------------------------------------------------------
2331    BYTE LEVEL LIVE REGISTERS
2332
2333    Find the locations in the function where any use of a pseudo can
2334    reach in the backwards direction.  In and out bitvectors are built
2335    for each basic block.  There are two mapping functions,
2336    df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are
2337    used to map regnos into bit vector positions.
2338
2339    This problem differs from the regular df_lr function in the way
2340    that subregs, *_extracts and strict_low_parts are handled. In lr
2341    these are consider partial kills, here, the exact set of bytes is
2342    modeled.  Note that any reg that has none of these operations is
2343    only modeled with a single bit since all operations access the
2344    entire register.
2345
2346    This problem is more brittle that the regular lr.  It currently can
2347    be used in dce incrementally, but cannot be used in an environment
2348    where insns are created or modified.  The problem is that the
2349    mapping of regnos to bitmap positions is relatively compact, in
2350    that if a pseudo does not do any of the byte wise operations, only
2351    one slot is allocated, rather than a slot for each byte.  If insn
2352    are created, where a subreg is used for a reg that had no subregs,
2353    the mapping would be wrong.  Likewise, there are no checks to see
2354    that new pseudos have been added.  These issues could be addressed
2355    by adding a problem specific flag to not use the compact mapping,
2356    if there was a need to do so.
2357
2358    ----------------------------------------------------------------------------*/
2359
2360 /* Private data used to verify the solution for this problem.  */
2361 struct df_byte_lr_problem_data
2362 {
2363   /* Expanded versions of bitvectors used in lr.  */
2364   bitmap invalidated_by_call;
2365   bitmap hardware_regs_used;
2366
2367   /* Indexed by regno, this is true if there are subregs, extracts or
2368      strict_low_parts for this regno.  */
2369   bitmap needs_expansion;
2370
2371   /* The start position and len for each regno in the various bit
2372      vectors.  */ 
2373   unsigned int* regno_start;  
2374   unsigned int* regno_len;
2375   /* An obstack for the bitmaps we need for this problem.  */
2376   bitmap_obstack byte_lr_bitmaps;
2377 };
2378
2379
2380 /* Get the starting location for REGNO in the df_byte_lr bitmaps.  */
2381
2382 int 
2383 df_byte_lr_get_regno_start (unsigned int regno)
2384 {
2385   struct df_byte_lr_problem_data *problem_data 
2386     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2387   return problem_data->regno_start[regno];
2388 }
2389
2390
2391 /* Get the len for REGNO in the df_byte_lr bitmaps.  */
2392
2393 int 
2394 df_byte_lr_get_regno_len (unsigned int regno)
2395 {  
2396   struct df_byte_lr_problem_data *problem_data 
2397     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2398   return problem_data->regno_len[regno];
2399 }
2400
2401
2402 /* Set basic block info.  */
2403
2404 static void
2405 df_byte_lr_set_bb_info (unsigned int index, 
2406                         struct df_byte_lr_bb_info *bb_info)
2407 {
2408   gcc_assert (df_byte_lr);
2409   gcc_assert (index < df_byte_lr->block_info_size);
2410   df_byte_lr->block_info[index] = bb_info;
2411 }
2412
2413  
2414 /* Free basic block info.  */
2415
2416 static void
2417 df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
2418                          void *vbb_info)
2419 {
2420   struct df_byte_lr_bb_info *bb_info = (struct df_byte_lr_bb_info *) vbb_info;
2421   if (bb_info)
2422     {
2423       BITMAP_FREE (bb_info->use);
2424       BITMAP_FREE (bb_info->def);
2425       BITMAP_FREE (bb_info->in);
2426       BITMAP_FREE (bb_info->out);
2427       pool_free (df_byte_lr->block_pool, bb_info);
2428     }
2429 }
2430
2431
2432 /* Check all of the refs in REF_REC to see if any of them are
2433    extracts, subregs or strict_low_parts.  */
2434
2435 static void
2436 df_byte_lr_check_regs (struct df_ref **ref_rec)
2437 {
2438   struct df_byte_lr_problem_data *problem_data 
2439     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2440
2441   for (; *ref_rec; ref_rec++)
2442     {
2443       struct df_ref *ref = *ref_rec;
2444       if (DF_REF_FLAGS_IS_SET (ref, DF_REF_SIGN_EXTRACT 
2445                                | DF_REF_ZERO_EXTRACT 
2446                                | DF_REF_STRICT_LOW_PART)
2447           || GET_CODE (DF_REF_REG (ref)) == SUBREG)
2448         bitmap_set_bit (problem_data->needs_expansion, DF_REF_REGNO (ref));
2449     }
2450 }
2451
2452
2453 /* Expand bitmap SRC which is indexed by regno to DEST which is indexed by 
2454    regno_start and regno_len.  */
2455
2456 static void
2457 df_byte_lr_expand_bitmap (bitmap dest, bitmap src)
2458 {
2459   struct df_byte_lr_problem_data *problem_data 
2460     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2461   bitmap_iterator bi;
2462   unsigned int i;
2463
2464   bitmap_clear (dest);
2465   EXECUTE_IF_SET_IN_BITMAP (src, 0, i, bi)
2466     {
2467       bitmap_set_range (dest, problem_data->regno_start[i], 
2468                         problem_data->regno_len[i]);
2469     }
2470 }
2471
2472
2473 /* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are
2474    not touched unless the block is new.  */
2475
2476 static void 
2477 df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2478 {
2479   unsigned int bb_index;
2480   bitmap_iterator bi;
2481   basic_block bb;
2482   unsigned int regno;
2483   unsigned int index = 0;
2484   unsigned int max_reg = max_reg_num();
2485   struct df_byte_lr_problem_data *problem_data 
2486     = problem_data = XNEW (struct df_byte_lr_problem_data);
2487
2488   df_byte_lr->problem_data = problem_data;
2489
2490   if (!df_byte_lr->block_pool)
2491     df_byte_lr->block_pool = create_alloc_pool ("df_byte_lr_block pool", 
2492                                            sizeof (struct df_byte_lr_bb_info), 50);
2493
2494   df_grow_bb_info (df_byte_lr);
2495
2496   /* Create the mapping from regnos to slots. This does not change
2497      unless the problem is destroyed and recreated.  In particular, if
2498      we end up deleting the only insn that used a subreg, we do not
2499      want to redo the mapping because this would invalidate everything
2500      else.  */
2501
2502   bitmap_obstack_initialize (&problem_data->byte_lr_bitmaps);
2503   problem_data->regno_start = XNEWVEC (unsigned int, max_reg);
2504   problem_data->regno_len = XNEWVEC (unsigned int, max_reg);
2505   problem_data->hardware_regs_used = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2506   problem_data->invalidated_by_call = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2507   problem_data->needs_expansion = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2508   
2509   /* Discover which regno's use subregs, extracts or
2510      strict_low_parts.  */
2511   FOR_EACH_BB (bb)
2512     {
2513       rtx insn;
2514       FOR_BB_INSNS (bb, insn)
2515         {
2516           if (INSN_P (insn))
2517             {
2518               df_byte_lr_check_regs (DF_INSN_DEFS (insn));
2519               df_byte_lr_check_regs (DF_INSN_USES (insn));
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                             df_invalidated_by_call);
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   struct df_ref **def_rec;
2599   struct 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       struct 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       struct 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           struct 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           struct 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       struct 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       struct 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   struct 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       struct 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   struct 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       struct 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   struct df_ref **def_rec;
2984 #ifdef EH_USES
2985   struct 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       struct 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       struct 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   struct df_ref **def_rec;
3026   struct 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       struct 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       struct 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 this = old;
3174   rtx prev = NULL;
3175
3176   while (this)
3177     if (XEXP (this, 0) == reg)
3178       {
3179         if (prev)
3180           XEXP (prev, 1) = XEXP (this, 1);
3181         else
3182           old = XEXP (this, 1);
3183         XEXP (this, 1) = REG_NOTES (insn);
3184         REG_NOTES (insn) = this;
3185         return old;
3186       }
3187     else
3188       {
3189         prev = this;
3190         this = XEXP (this, 1);
3191       }
3192   
3193   /* Did not find the note.  */
3194   REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
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, struct 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   struct df_ref **def_rec;
3395   struct 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       struct 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       struct 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 ((mws->type == DF_REF_REG_DEF) 
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               struct 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 (mws->type == DF_REF_REG_DEF)
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               struct 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 ((mws->type != DF_REF_REG_DEF)  
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           struct 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   struct 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       struct 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   struct 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       struct 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   struct 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       struct 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_artificial_refs_at_end should be called first with a
3763    bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT.  Then
3764    df_simulate_one_insn should be called for each insn in the block,
3765    starting with the last on.  Finally,
3766    df_simulate_artificial_refs_at_top can be called to get a new value
3767    of the sets at the top of the block (this is rarely used).
3768
3769    It would be not be difficult to define a similar set of functions
3770    that work in the forwards direction.  In that case the functions
3771    would ignore the use sets and look for the REG_DEAD and REG_UNUSED
3772    notes.
3773 ----------------------------------------------------------------------------*/
3774
3775 /* Apply the artificial uses and defs at the end of BB in a backwards
3776    direction.  */
3777
3778 void 
3779 df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3780 {
3781   struct df_ref **def_rec;
3782   struct df_ref **use_rec;
3783   int bb_index = bb->index;
3784   
3785   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3786     {
3787       struct df_ref *def = *def_rec;
3788       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3789         bitmap_clear_bit (live, DF_REF_REGNO (def));
3790     }
3791
3792   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3793     {
3794       struct df_ref *use = *use_rec;
3795       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3796         bitmap_set_bit (live, DF_REF_REGNO (use));
3797     }
3798 }
3799
3800
3801 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3802
3803 void 
3804 df_simulate_one_insn (basic_block bb, rtx insn, bitmap live)
3805 {
3806   if (! INSN_P (insn))
3807     return;     
3808   
3809   df_simulate_defs (insn, live);
3810   df_simulate_uses (insn, live);
3811   df_simulate_fixup_sets (bb, live);
3812 }
3813
3814
3815 /* Apply the artificial uses and defs at the top of BB in a backwards
3816    direction.  */
3817
3818 void 
3819 df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
3820 {
3821   struct df_ref **def_rec;
3822 #ifdef EH_USES
3823   struct df_ref **use_rec;
3824 #endif
3825   int bb_index = bb->index;
3826   
3827   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3828     {
3829       struct df_ref *def = *def_rec;
3830       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3831         bitmap_clear_bit (live, DF_REF_REGNO (def));
3832     }
3833
3834 #ifdef EH_USES
3835   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3836     {
3837       struct df_ref *use = *use_rec;
3838       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3839         bitmap_set_bit (live, DF_REF_REGNO (use));
3840     }
3841 #endif
3842 }