df-scan.c (df_scan_free_bb_info): Added basic block parameter to be able to clean...
[platform/upstream/gcc.git] / gcc / df-core.c
1 /* Allocation for dataflow support routines.
2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
3    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 2, 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 COPYING.  If not, write to the Free
23 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 02110-1301, USA.  
25 */
26
27 /*
28 OVERVIEW:
29
30 The files in this collection (df*.c,df.h) provide a general framework
31 for solving dataflow problems.  The global dataflow is performed using
32 a good implementation of iterative dataflow analysis.
33
34 The file df-problems.c provides problem instance for the most common
35 dataflow problems: reaching defs, upward exposed uses, live variables,
36 uninitialized variables, def-use chains, and use-def chains.  However,
37 the interface allows other dataflow problems to be defined as well.
38
39
40 USAGE:
41
42 Here is an example of using the dataflow routines.
43
44       struct df *df;
45
46       df = df_init (init_flags);
47       
48       df_add_problem (df, problem);
49
50       df_set_blocks (df, blocks);
51
52       df_rescan_blocks (df, blocks);
53
54       df_analyze (df);
55
56       df_dump (df, stderr);
57
58       df_finish (df);
59
60
61
62 DF_INIT simply creates a poor man's object (df) that needs to be
63 passed to all the dataflow routines.  df_finish destroys this object
64 and frees up any allocated memory.
65
66 There are two flags that can be passed to df_init:
67
68 DF_NO_SCAN means that no scanning of the rtl code is performed.  This
69 is used if the problem instance is to do it's own scanning.
70
71 DF_HARD_REGS means that the scanning is to build information about
72 both pseudo registers and hardware registers.  Without this
73 information, the problems will be solved only on pseudo registers.
74
75
76
77 DF_ADD_PROBLEM adds a problem, defined by an instance to struct
78 df_problem, to the set of problems solved in this instance of df.  All
79 calls to add a problem for a given instance of df must occur before
80 the first call to DF_RESCAN_BLOCKS or DF_ANALYZE.
81
82 For all of the problems defined in df-problems.c, there are
83 convienence functions named DF_*_ADD_PROBLEM.
84
85
86 Problems can be dependent on other problems.  For instance, solving
87 def-use or use-def chains is dependant on solving reaching
88 definitions. As long as these dependancies are listed in the problem
89 definition, the order of adding the problems is not material.
90 Otherwise, the problems will be solved in the order of calls to
91 df_add_problem.  Note that it is not necessary to have a problem.  In
92 that case, df will just be used to do the scanning.
93
94
95
96 DF_SET_BLOCKS is an optional call used to define a region of the
97 function on which the analysis will be performed.  The normal case is
98 to analyze the entire function and no call to df_set_blocks is made.
99
100 When a subset is given, the analysis behaves as if the function only
101 contains those blocks and any edges that occur directly between the
102 blocks in the set.  Care should be taken to call df_set_blocks right
103 before the call to analyze in order to eliminate the possiblity that
104 optimizations that reorder blocks invalidate the bitvector.
105
106
107
108 DF_RESCAN_BLOCKS is an optional call that causes the scanner to be
109  (re)run over the set of blocks passed in.  If blocks is NULL, the entire
110 function (or all of the blocks defined in df_set_blocks) is rescanned.
111 If blocks contains blocks that were not defined in the call to
112 df_set_blocks, these blocks are added to the set of blocks.
113
114
115 DF_ANALYZE causes all of the defined problems to be (re)solved.  It
116 does not cause blocks to be (re)scanned at the rtl level unless no
117 prior call is made to df_rescan_blocks.
118
119
120 DF_DUMP can then be called to dump the information produce to some
121 file.
122
123
124
125 DF_FINISH causes all of the datastructures to be cleaned up and freed.
126 The df_instance is also freed and its pointer should be NULLed.
127
128
129
130
131 Scanning produces a `struct df_ref' data structure (ref) is allocated
132 for every register reference (def or use) and this records the insn
133 and bb the ref is found within.  The refs are linked together in
134 chains of uses and defs for each insn and for each register.  Each ref
135 also has a chain field that links all the use refs for a def or all
136 the def refs for a use.  This is used to create use-def or def-use
137 chains.
138
139 Different optimizations have different needs.  Ultimately, only
140 register allocation and schedulers should be using the bitmaps
141 produced for the live register and uninitialized register problems.
142 The rest of the backend should be upgraded to using and maintaining
143 the linked information such as def use or use def chains.
144
145
146
147 PHILOSOPHY:
148
149 While incremental bitmaps are not worthwhile to maintain, incremental
150 chains may be perfectly reasonable.  The fastest way to build chains
151 from scratch or after significant modifications is to build reaching
152 definitions (RD) and build the chains from this.
153
154 However, general algorithms for maintaining use-def or def-use chains
155 are not practical.  The amount of work to recompute the chain any
156 chain after an arbitrary change is large.  However, with a modest
157 amount of work it is generally possible to have the application that
158 uses the chains keep them up to date.  The high level knowledge of
159 what is really happening is essential to crafting efficient
160 incremental algorithms.
161
162 As for the bit vector problems, there is no interface to give a set of
163 blocks over with to resolve the iteration.  In general, restarting a
164 dataflow iteration is difficult and expensive.  Again, the best way to
165 keep the dataflow infomation up to data (if this is really what is
166 needed) it to formulate a problem specific solution.
167
168 There are fine grained calls for creating and deleting references from
169 instructions in df-scan.c.  However, these are not currently connected
170 to the engine that resolves the dataflow equations.
171
172
173 DATA STRUCTURES:
174
175 The basic object is a DF_REF (reference) and this may either be a 
176 DEF (definition) or a USE of a register.
177
178 These are linked into a variety of lists; namely reg-def, reg-use,
179 insn-def, insn-use, def-use, and use-def lists.  For example, the
180 reg-def lists contain all the locations that define a given register
181 while the insn-use lists contain all the locations that use a
182 register.
183
184 Note that the reg-def and reg-use chains are generally short for
185 pseudos and long for the hard registers.
186
187 ACCESSING REFS:
188
189 There are 4 ways to obtain access to refs:
190
191 1) References are divided into two categories, REAL and ARTIFICIAL.
192
193    REAL refs are associated with instructions.  They are linked into
194    either in the insn's defs list (accessed by the DF_INSN_DEFS or
195    DF_INSN_UID_DEFS macros) or the insn's uses list (accessed by the
196    DF_INSN_USES or DF_INSN_UID_USES macros).  These macros produce a
197    ref (or NULL), the rest of the list can be obtained by traversal of
198    the NEXT_REF field (accessed by the DF_REF_NEXT_REF macro.)  There
199    is no significance to the ordering of the uses or refs in an
200    instruction.
201
202    ARTIFICIAL refs are associated with basic blocks.  The heads of
203    these lists can be accessed by calling get_artificial_defs or
204    get_artificial_uses for the particular basic block.  Artificial
205    defs and uses are only there if DF_HARD_REGS was specified when the
206    df instance was created.
207  
208    Artificial defs and uses occur at the beginning blocks that are the
209    destination of eh edges.  The defs come from the registers
210    specified in EH_RETURN_DATA_REGNO and the uses come from the
211    registers specified in ED_USES.  Logically these defs and uses
212    should really occur along the eh edge, but there is no convienent
213    way to do this.  Artificial edges that occur at the beginning of
214    the block have the DF_REF_AT_TOP flag set.
215    
216    Artificial uses also occur at the end of all blocks.  These arise
217    from the hard registers that are always live, such as the stack
218    register and are put there to keep the code from forgetting about
219    them.
220
221 2) All of the uses and defs associated with each pseudo or hard
222    register are linked in a bidirectional chain.  These are called
223    reg-use or reg_def chains.
224
225    The first use (or def) for a register can be obtained using the
226    DF_REG_USE_GET macro (or DF_REG_DEF_GET macro).  Subsequent uses
227    for the same regno can be obtained by following the next_reg field
228    of the ref.
229
230    In previous versions of this code, these chains were ordered.  It
231    has not been practical to continue this practice.
232
233 3) If def-use or use-def chains are built, these can be traversed to
234    get to other refs.
235
236 4) An array of all of the uses (and an array of all of the defs) can
237    be built.  These arrays are indexed by the value in the id
238    structure.  These arrays are only lazily kept up to date, and that
239    process can be expensive.  To have these arrays built, call
240    df_reorganize_refs.   Note that the values in the id field of a ref
241    may change across calls to df_analyze or df_reorganize refs.
242
243    If the only use of this array is to find all of the refs, it is
244    better to traverse all of the registers and then traverse all of
245    reg-use or reg-def chains.
246
247
248
249 NOTES:
250  
251 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
252 both a use and a def.  These are both marked read/write to show that they
253 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
254 will generate a use of reg 42 followed by a def of reg 42 (both marked
255 read/write).  Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
256 generates a use of reg 41 then a def of reg 41 (both marked read/write),
257 even though reg 41 is decremented before it is used for the memory
258 address in this second example.
259
260 A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
261 for which the number of word_mode units covered by the outer mode is
262 smaller than that covered by the inner mode, invokes a read-modify-write.
263 operation.  We generate both a use and a def and again mark them
264 read/write.
265
266 Paradoxical subreg writes do not leave a trace of the old content, so they
267 are write-only operations.  
268 */
269
270
271 #include "config.h"
272 #include "system.h"
273 #include "coretypes.h"
274 #include "tm.h"
275 #include "rtl.h"
276 #include "tm_p.h"
277 #include "insn-config.h"
278 #include "recog.h"
279 #include "function.h"
280 #include "regs.h"
281 #include "output.h"
282 #include "alloc-pool.h"
283 #include "flags.h"
284 #include "hard-reg-set.h"
285 #include "basic-block.h"
286 #include "sbitmap.h"
287 #include "bitmap.h"
288 #include "timevar.h"
289 #include "df.h"
290 #include "tree-pass.h"
291
292 static struct df *ddf = NULL;
293 struct df *shared_df = NULL;
294
295 /*----------------------------------------------------------------------------
296   Functions to create, destroy and manipulate an instance of df.
297 ----------------------------------------------------------------------------*/
298
299
300 /* Initialize dataflow analysis and allocate and initialize dataflow
301    memory.  */
302
303 struct df *
304 df_init (int flags)
305 {
306   struct df *df = xcalloc (1, sizeof (struct df));
307   df->flags = flags;
308
309   /* This is executed once per compilation to initialize platform
310      specific data structures. */
311   df_hard_reg_init ();
312   
313   /* All df instance must define the scanning problem.  */
314   df_scan_add_problem (df);
315   ddf = df;
316   return df;
317 }
318
319 /* Add PROBLEM to the DF instance.  */
320
321 struct dataflow *
322 df_add_problem (struct df *df, struct df_problem *problem)
323 {
324   struct dataflow *dflow;
325
326   /* First try to add the dependent problem. */
327   if (problem->dependent_problem)
328     df_add_problem (df, problem->dependent_problem);
329
330   /* Check to see if this problem has already been defined.  If it
331      has, just return that instance, if not, add it to the end of the
332      vector.  */
333   dflow = df->problems_by_index[problem->id];
334   if (dflow)
335     return dflow;
336
337   /* Make a new one and add it to the end.  */
338   dflow = xcalloc (1, sizeof (struct dataflow));
339   dflow->df = df;
340   dflow->problem = problem;
341   df->problems_in_order[df->num_problems_defined++] = dflow;
342   df->problems_by_index[dflow->problem->id] = dflow;
343
344   return dflow;
345 }
346
347
348 /* Set the blocks that are to be considered for analysis.  If this is
349    not called or is called with null, the entire function in
350    analyzed.  */
351
352 void 
353 df_set_blocks (struct df *df, bitmap blocks)
354 {
355   if (blocks)
356     {
357       if (df->blocks_to_analyze)
358         {
359           int p;
360           bitmap diff = BITMAP_ALLOC (NULL);
361           bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
362           for (p = 0; p < df->num_problems_defined; p++)
363             {
364               struct dataflow *dflow = df->problems_in_order[p];
365               if (*dflow->problem->free_bb_fun)
366                 {
367                   bitmap_iterator bi;
368                   unsigned int bb_index;
369                   
370                   EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
371                     {
372                       basic_block bb = BASIC_BLOCK (bb_index);
373                       (*dflow->problem->free_bb_fun) (dflow, bb, diff);
374                     }
375                 }
376             }
377
378           BITMAP_FREE (diff);
379         }
380       else
381         df->blocks_to_analyze = BITMAP_ALLOC (NULL);
382       bitmap_copy (df->blocks_to_analyze, blocks);
383     }
384   else
385     {
386       if (df->blocks_to_analyze)
387         {
388           BITMAP_FREE (df->blocks_to_analyze);
389           df->blocks_to_analyze = NULL;
390         }
391     }
392 }
393
394
395 /* Free all the dataflow info and the DF structure.  This should be
396    called from the df_finish macro which also NULLs the parm.  */
397
398 void
399 df_finish1 (struct df *df)
400 {
401   int i;
402
403   for (i = 0; i < df->num_problems_defined; i++)
404     (*df->problems_in_order[i]->problem->free_fun) (df->problems_in_order[i]); 
405
406   free (df);
407 }
408
409 \f
410 /*----------------------------------------------------------------------------
411    The general data flow analysis engine.
412 ----------------------------------------------------------------------------*/
413
414
415 /* Hybrid search algorithm from "Implementation Techniques for
416    Efficient Data-Flow Analysis of Large Programs".  */
417
418 static void
419 df_hybrid_search_forward (basic_block bb, 
420                           struct dataflow *dataflow,
421                           bool single_pass)
422 {
423   int result_changed;
424   int i = bb->index;
425   edge e;
426   edge_iterator ei;
427
428   SET_BIT (dataflow->visited, bb->index);
429   gcc_assert (TEST_BIT (dataflow->pending, bb->index));
430   RESET_BIT (dataflow->pending, i);
431
432   /*  Calculate <conf_op> of predecessor_outs.  */
433   if (EDGE_COUNT (bb->preds) > 0)
434     FOR_EACH_EDGE (e, ei, bb->preds)
435       {
436         if (!TEST_BIT (dataflow->considered, e->src->index))
437           continue;
438         
439         (*dataflow->problem->con_fun_n) (dataflow, e);
440       }
441   else if (*dataflow->problem->con_fun_0)
442     (*dataflow->problem->con_fun_0) (dataflow, bb);
443   
444   result_changed = (*dataflow->problem->trans_fun) (dataflow, i);
445   
446   if (!result_changed || single_pass)
447     return;
448   
449   FOR_EACH_EDGE (e, ei, bb->succs)
450     {
451       if (e->dest->index == i)
452         continue;
453       if (!TEST_BIT (dataflow->considered, e->dest->index))
454         continue;
455       SET_BIT (dataflow->pending, e->dest->index);
456     }
457   
458   FOR_EACH_EDGE (e, ei, bb->succs)
459     {
460       if (e->dest->index == i)
461         continue;
462       
463       if (!TEST_BIT (dataflow->considered, e->dest->index))
464         continue;
465       if (!TEST_BIT (dataflow->visited, e->dest->index))
466         df_hybrid_search_forward (e->dest, dataflow, single_pass);
467     }
468 }
469
470 static void
471 df_hybrid_search_backward (basic_block bb,
472                            struct dataflow *dataflow,
473                            bool single_pass)
474 {
475   int result_changed;
476   int i = bb->index;
477   edge e;
478   edge_iterator ei;
479   
480   SET_BIT (dataflow->visited, bb->index);
481   gcc_assert (TEST_BIT (dataflow->pending, bb->index));
482   RESET_BIT (dataflow->pending, i);
483
484   /*  Calculate <conf_op> of predecessor_outs.  */
485   if (EDGE_COUNT (bb->succs) > 0)
486     FOR_EACH_EDGE (e, ei, bb->succs)                                    
487       {                                                         
488         if (!TEST_BIT (dataflow->considered, e->dest->index))           
489           continue;                                                     
490         
491         (*dataflow->problem->con_fun_n) (dataflow, e);
492       }                                                         
493   else if (*dataflow->problem->con_fun_0)
494     (*dataflow->problem->con_fun_0) (dataflow, bb);
495
496   result_changed = (*dataflow->problem->trans_fun) (dataflow, i);
497   
498   if (!result_changed || single_pass)
499     return;
500   
501   FOR_EACH_EDGE (e, ei, bb->preds)
502     {                                                           
503       if (e->src->index == i)
504         continue;
505       
506       if (!TEST_BIT (dataflow->considered, e->src->index))
507         continue;
508
509       SET_BIT (dataflow->pending, e->src->index);
510     }                                                           
511   
512   FOR_EACH_EDGE (e, ei, bb->preds)
513     {
514       if (e->src->index == i)
515         continue;
516
517       if (!TEST_BIT (dataflow->considered, e->src->index))
518         continue;
519       
520       if (!TEST_BIT (dataflow->visited, e->src->index))
521         df_hybrid_search_backward (e->src, dataflow, single_pass);
522     }
523 }
524
525
526 /* This function will perform iterative bitvector dataflow described
527    by DATAFLOW, producing the in and out sets.  Only the part of the
528    cfg induced by blocks in DATAFLOW->order is taken into account.
529
530    SINGLE_PASS is true if you just want to make one pass over the
531    blocks.  */
532
533 void
534 df_iterative_dataflow (struct dataflow *dataflow,
535                        bitmap blocks_to_consider, bitmap blocks_to_init, 
536                        int *blocks_in_postorder, int n_blocks, 
537                        bool single_pass)
538 {
539   unsigned int idx;
540   int i;
541   sbitmap visited = sbitmap_alloc (last_basic_block);
542   sbitmap pending = sbitmap_alloc (last_basic_block);
543   sbitmap considered = sbitmap_alloc (last_basic_block);
544   bitmap_iterator bi;
545
546   dataflow->visited = visited;
547   dataflow->pending = pending;
548   dataflow->considered = considered;
549
550   sbitmap_zero (visited);
551   sbitmap_zero (pending);
552   sbitmap_zero (considered);
553
554   EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi)
555     {
556       SET_BIT (considered, idx);
557     }
558
559   for (i = 0; i < n_blocks; i++)
560     {
561       idx = blocks_in_postorder[i];
562       SET_BIT (pending, idx);
563     };
564
565   (*dataflow->problem->init_fun) (dataflow, blocks_to_init);
566
567   while (1)
568     {
569
570       /* For forward problems, you want to pass in reverse postorder
571          and for backward problems you want postorder.  This has been
572          shown to be as good as you can do by several people, the
573          first being Mathew Hecht in his phd dissertation.
574
575          The nodes are passed into this function in postorder.  */
576
577       if (dataflow->problem->dir == DF_FORWARD)
578         {
579           for (i = n_blocks - 1 ; i >= 0 ; i--)
580             {
581               idx = blocks_in_postorder[i];
582               
583               if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
584                 df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass);
585             }
586         }
587       else
588         {
589           for (i = 0; i < n_blocks; i++)
590             {
591               idx = blocks_in_postorder[i];
592               
593               if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
594                 df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass);
595             }
596         }
597
598       if (sbitmap_first_set_bit (pending) == -1)
599         break;
600
601       sbitmap_zero (visited);
602     }
603
604   sbitmap_free (pending);
605   sbitmap_free (visited);
606   sbitmap_free (considered);
607 }
608
609
610 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
611    the order of the remaining entries.  Returns the length of the resulting
612    list.  */
613
614 static unsigned
615 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
616 {
617   unsigned act, last;
618
619   for (act = 0, last = 0; act < len; act++)
620     if (bitmap_bit_p (blocks, list[act]))
621       list[last++] = list[act];
622
623   return last;
624 }
625
626
627 /* Execute dataflow analysis on a single dataflow problem. 
628
629    There are three sets of blocks passed in: 
630
631    BLOCKS_TO_CONSIDER are the blocks whose solution can either be
632    examined or will be computed.  For calls from DF_ANALYZE, this is
633    the set of blocks that has been passed to DF_SET_BLOCKS.  For calls
634    from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of
635    blocks in the fringe (the set of blocks passed in plus the set of
636    immed preds and succs of those blocks).
637
638    BLOCKS_TO_INIT are the blocks whose solution will be changed by
639    this iteration.  For calls from DF_ANALYZE, this is the set of
640    blocks that has been passed to DF_SET_BLOCKS.  For calls from
641    DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks
642    passed in.
643
644    BLOCKS_TO_SCAN are the set of blocks that need to be rescanned.
645    For calls from DF_ANALYZE, this is the accumulated set of blocks
646    that has been passed to DF_RESCAN_BLOCKS since the last call to
647    DF_ANALYZE.  For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS,
648    this is the set of blocks passed in.
649  
650                    blocks_to_consider    blocks_to_init    blocks_to_scan
651    full redo       all                   all               all
652    partial redo    all                   all               sub
653    small fixup     fringe                sub               sub
654 */
655
656 static void
657 df_analyze_problem (struct dataflow *dflow, 
658                     bitmap blocks_to_consider, 
659                     bitmap blocks_to_init,
660                     bitmap blocks_to_scan,
661                     int *postorder, int n_blocks, bool single_pass)
662 {
663   /* (Re)Allocate the datastructures necessary to solve the problem.  */ 
664   if (*dflow->problem->alloc_fun)
665     (*dflow->problem->alloc_fun) (dflow, blocks_to_scan);
666
667   /* Set up the problem and compute the local information.  This
668      function is passed both the blocks_to_consider and the
669      blocks_to_scan because the RD and RU problems require the entire
670      function to be rescanned if they are going to be updated.  */
671   if (*dflow->problem->local_compute_fun)
672     (*dflow->problem->local_compute_fun) (dflow, blocks_to_consider, blocks_to_scan);
673
674   /* Solve the equations.  */
675   if (*dflow->problem->dataflow_fun)
676     (*dflow->problem->dataflow_fun) (dflow, blocks_to_consider, blocks_to_init,
677                                     postorder, n_blocks, single_pass);
678
679   /* Massage the solution.  */
680   if (*dflow->problem->finalize_fun)
681     (*dflow->problem->finalize_fun) (dflow, blocks_to_consider);
682 }
683
684
685 /* Analyze dataflow info for the basic blocks specified by the bitmap
686    BLOCKS, or for the whole CFG if BLOCKS is zero.  */
687
688 void
689 df_analyze (struct df *df)
690 {
691   int *postorder = xmalloc (sizeof (int) *last_basic_block);
692   bitmap current_all_blocks = BITMAP_ALLOC (NULL);
693   int n_blocks;
694   int i;
695   bool everything;
696
697   n_blocks = post_order_compute (postorder, true);
698
699   if (n_blocks != n_basic_blocks)
700     delete_unreachable_blocks ();
701
702   for (i = 0; i < n_blocks; i++)
703     bitmap_set_bit (current_all_blocks, postorder[i]);
704
705   /* No one called df_rescan_blocks, so do it.  */
706   if (!df->blocks_to_scan)
707     df_rescan_blocks (df, NULL);
708
709   /* Make sure that we have pruned any unreachable blocks from these
710      sets.  */
711   bitmap_and_into (df->blocks_to_scan, current_all_blocks);
712
713   if (df->blocks_to_analyze)
714     {
715       everything = false;
716       bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
717       n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze);
718       BITMAP_FREE (current_all_blocks);
719     }
720   else
721     {
722       everything = true;
723       df->blocks_to_analyze = current_all_blocks;
724       current_all_blocks = NULL;
725     }
726
727   /* Skip over the DF_SCAN problem. */
728   for (i = 1; i < df->num_problems_defined; i++)
729     df_analyze_problem (df->problems_in_order[i], 
730                         df->blocks_to_analyze, df->blocks_to_analyze, 
731                         df->blocks_to_scan,
732                         postorder, n_blocks, false);
733
734   if (everything)
735     {
736       BITMAP_FREE (df->blocks_to_analyze);
737       df->blocks_to_analyze = NULL;
738     }
739
740   BITMAP_FREE (df->blocks_to_scan);
741   df->blocks_to_scan = NULL;
742 }
743
744
745 \f
746 /*----------------------------------------------------------------------------
747    Functions to support limited incremental change.
748 ----------------------------------------------------------------------------*/
749
750
751 /* Get basic block info.  */
752
753 static void *
754 df_get_bb_info (struct dataflow *dflow, unsigned int index)
755 {
756   return (struct df_scan_bb_info *) dflow->block_info[index];
757 }
758
759
760 /* Set basic block info.  */
761
762 static void
763 df_set_bb_info (struct dataflow *dflow, unsigned int index, 
764                 void *bb_info)
765 {
766   dflow->block_info[index] = bb_info;
767 }
768
769
770 /* Called from the rtl_compact_blocks to reorganize the problems basic
771    block info.  */
772
773 void 
774 df_compact_blocks (struct df *df)
775 {
776   int i, p;
777   basic_block bb;
778   void **problem_temps;
779   int size = last_basic_block *sizeof (void *);
780   problem_temps = xmalloc (size);
781
782   for (p = 0; p < df->num_problems_defined; p++)
783     {
784       struct dataflow *dflow = df->problems_in_order[p];
785       if (*dflow->problem->free_bb_fun)
786         {
787           df_grow_bb_info (dflow);
788           memcpy (problem_temps, dflow->block_info, size);
789
790           /* Copy the bb info from the problem tmps to the proper
791              place in the block_info vector.  Null out the copied
792              item.  */
793           i = NUM_FIXED_BLOCKS;
794           FOR_EACH_BB (bb) 
795             {
796               df_set_bb_info (dflow, i, problem_temps[bb->index]);
797               problem_temps[bb->index] = NULL;
798               i++;
799             }
800           memset (dflow->block_info + i, 0, 
801                   (last_basic_block - i) *sizeof (void *));
802
803           /* Free any block infos that were not copied (and NULLed).
804              These are from orphaned blocks.  */
805           for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
806             {
807               basic_block bb = BASIC_BLOCK (i); 
808               if (problem_temps[i] && bb)
809                 (*dflow->problem->free_bb_fun) 
810                   (dflow, bb, problem_temps[i]);
811             }
812         }
813     }
814
815   free (problem_temps);
816
817   i = NUM_FIXED_BLOCKS;
818   FOR_EACH_BB (bb) 
819     {
820       SET_BASIC_BLOCK (i, bb);
821       bb->index = i;
822       i++;
823     }
824
825   gcc_assert (i == n_basic_blocks);
826
827   for (; i < last_basic_block; i++)
828     SET_BASIC_BLOCK (i, NULL);
829 }
830
831
832 /* Shove NEW_BLOCK in at OLD_INDEX.  Called from if-cvt to hack a
833    block.  There is no excuse for people to do this kind of thing.  */
834
835 void 
836 df_bb_replace (struct df *df, int old_index, basic_block new_block)
837 {
838   int p;
839
840   for (p = 0; p < df->num_problems_defined; p++)
841     {
842       struct dataflow *dflow = df->problems_in_order[p];
843       if (dflow->block_info)
844         {
845           void *temp;
846
847           df_grow_bb_info (dflow);
848
849           /* The old switcheroo.  */
850
851           temp = df_get_bb_info (dflow, old_index);
852           df_set_bb_info (dflow, old_index, 
853                           df_get_bb_info (dflow, new_block->index));
854           df_set_bb_info (dflow, new_block->index, temp);
855         }
856     }
857
858   SET_BASIC_BLOCK (old_index, new_block);
859   new_block->index = old_index;
860 }
861
862 /*----------------------------------------------------------------------------
863    PUBLIC INTERFACES TO QUERY INFORMATION.
864 ----------------------------------------------------------------------------*/
865
866
867 /* Return last use of REGNO within BB.  */
868
869 struct df_ref *
870 df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
871 {
872   rtx insn;
873   struct df_ref *use;
874
875   FOR_BB_INSNS_REVERSE (bb, insn)
876     {
877       unsigned int uid = INSN_UID (insn);
878       for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
879         if (DF_REF_REGNO (use) == regno)
880           return use;
881     }
882   return NULL;
883 }
884
885
886 /* Return first def of REGNO within BB.  */
887
888 struct df_ref *
889 df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
890 {
891   rtx insn;
892   struct df_ref *def;
893
894   FOR_BB_INSNS (bb, insn)
895     {
896       unsigned int uid = INSN_UID (insn);
897       for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
898         if (DF_REF_REGNO (def) == regno)
899           return def;
900     }
901   return NULL;
902 }
903
904
905 /* Return last def of REGNO within BB.  */
906
907 struct df_ref *
908 df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
909 {
910   rtx insn;
911   struct df_ref *def;
912
913   FOR_BB_INSNS_REVERSE (bb, insn)
914     {
915       unsigned int uid = INSN_UID (insn);
916
917       for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
918         if (DF_REF_REGNO (def) == regno)
919           return def;
920     }
921
922   return NULL;
923 }
924
925 /* Return true if INSN defines REGNO.  */
926
927 bool
928 df_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno)
929 {
930   unsigned int uid;
931   struct df_ref *def;
932
933   uid = INSN_UID (insn);
934   for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
935     if (DF_REF_REGNO (def) == regno)
936       return true;
937   
938   return false;
939 }
940
941
942 /* Finds the reference corresponding to the definition of REG in INSN.
943    DF is the dataflow object.  */
944
945 struct df_ref *
946 df_find_def (struct df *df, rtx insn, rtx reg)
947 {
948   unsigned int uid;
949   struct df_ref *def;
950
951   if (GET_CODE (reg) == SUBREG)
952     reg = SUBREG_REG (reg);
953   gcc_assert (REG_P (reg));
954
955   uid = INSN_UID (insn);
956   for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
957     if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
958       return def;
959
960   return NULL;
961 }
962
963
964 /* Return true if REG is defined in INSN, zero otherwise.  */ 
965
966 bool
967 df_reg_defined (struct df *df, rtx insn, rtx reg)
968 {
969   return df_find_def (df, insn, reg) != NULL;
970 }
971   
972
973 /* Finds the reference corresponding to the use of REG in INSN.
974    DF is the dataflow object.  */
975   
976 struct df_ref *
977 df_find_use (struct df *df, rtx insn, rtx reg)
978 {
979   unsigned int uid;
980   struct df_ref *use;
981
982   if (GET_CODE (reg) == SUBREG)
983     reg = SUBREG_REG (reg);
984   gcc_assert (REG_P (reg));
985
986   uid = INSN_UID (insn);
987   for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
988     if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
989       return use; 
990
991   return NULL;
992 }
993
994
995 /* Return true if REG is referenced in INSN, zero otherwise.  */ 
996
997 bool
998 df_reg_used (struct df *df, rtx insn, rtx reg)
999 {
1000   return df_find_use (df, insn, reg) != NULL;
1001 }
1002   
1003 \f
1004 /*----------------------------------------------------------------------------
1005    Debugging and printing functions.
1006 ----------------------------------------------------------------------------*/
1007
1008 /* Dump dataflow info.  */
1009 void
1010 df_dump (struct df *df, FILE *file)
1011 {
1012   int i;
1013
1014   if (! df || ! file)
1015     return;
1016
1017   fprintf (file, "\n\n%s\n", current_function_name ());
1018   fprintf (file, "\nDataflow summary:\n");
1019   fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n",
1020            df->def_info.bitmap_size, df->use_info.bitmap_size);
1021
1022   for (i = 0; i < df->num_problems_defined; i++)
1023     (*df->problems_in_order[i]->problem->dump_fun) (df->problems_in_order[i], file); 
1024
1025   fprintf (file, "\n");
1026 }
1027
1028
1029 void
1030 df_refs_chain_dump (struct df *df, struct df_ref *ref, 
1031                    bool follow_chain, FILE *file)
1032 {
1033   fprintf (file, "{ ");
1034   while (ref)
1035     {
1036       fprintf (file, "%c%d(%d) ",
1037                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1038                DF_REF_ID (ref),
1039                DF_REF_REGNO (ref));
1040       if (follow_chain)
1041         df_chain_dump (df, DF_REF_CHAIN (ref), file);
1042       ref = ref->next_ref;
1043     }
1044   fprintf (file, "}");
1045 }
1046
1047
1048 /* Dump either a ref-def or reg-use chain.  */
1049
1050 void
1051 df_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref,  FILE *file)
1052 {
1053   fprintf (file, "{ ");
1054   while (ref)
1055     {
1056       fprintf (file, "%c%d(%d) ",
1057                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1058                DF_REF_ID (ref),
1059                DF_REF_REGNO (ref));
1060       ref = ref->next_reg;
1061     }
1062   fprintf (file, "}");
1063 }
1064
1065
1066 void
1067 df_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file)
1068 {
1069   unsigned int uid;
1070   int bbi;
1071
1072   uid = INSN_UID (insn);
1073
1074   if (DF_INSN_UID_DEFS (df, uid))
1075     bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1076   else if (DF_INSN_UID_USES(df, uid))
1077     bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1078   else
1079     bbi = -1;
1080
1081   fprintf (file, "insn %d bb %d luid %d defs ",
1082            uid, bbi, DF_INSN_LUID (df, insn));
1083
1084   df_refs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), follow_chain, file);
1085   fprintf (file, " defs ");
1086   df_refs_chain_dump (df, DF_INSN_UID_USES (df, uid), follow_chain, file);
1087   fprintf (file, "\n");
1088 }
1089
1090 void
1091 df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
1092 {
1093   unsigned int uid;
1094   int bbi;
1095
1096   uid = INSN_UID (insn);
1097   if (DF_INSN_UID_DEFS (df, uid))
1098     bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1099   else if (DF_INSN_UID_USES(df, uid))
1100     bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1101   else
1102     bbi = -1;
1103
1104   fprintf (file, "insn %d bb %d luid %d defs ",
1105            uid, bbi, DF_INSN_LUID (df, insn));
1106   df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file);
1107     
1108   fprintf (file, " uses ");
1109   df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file);
1110   fprintf (file, "\n");
1111 }
1112
1113 void
1114 df_regno_debug (struct df *df, unsigned int regno, FILE *file)
1115 {
1116   fprintf (file, "reg %d defs ", regno);
1117   df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file);
1118   fprintf (file, " uses ");
1119   df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file);
1120   fprintf (file, "\n");
1121 }
1122
1123
1124 void
1125 df_ref_debug (struct df *df, struct df_ref *ref, FILE *file)
1126 {
1127   fprintf (file, "%c%d ",
1128            DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1129            DF_REF_ID (ref));
1130   fprintf (file, "reg %d bb %d luid %d insn %d chain ",
1131            DF_REF_REGNO (ref),
1132            DF_REF_BBNO (ref),
1133            DF_REF_INSN (ref) ? DF_INSN_LUID (df, DF_REF_INSN (ref)) : -1,
1134            DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1);
1135   df_chain_dump (df, DF_REF_CHAIN (ref), file);
1136   fprintf (file, "\n");
1137 }
1138 \f
1139 /* Functions for debugging from GDB.  */
1140
1141 void
1142 debug_df_insn (rtx insn)
1143 {
1144   df_insn_debug (ddf, insn, true, stderr);
1145   debug_rtx (insn);
1146 }
1147
1148
1149 void
1150 debug_df_reg (rtx reg)
1151 {
1152   df_regno_debug (ddf, REGNO (reg), stderr);
1153 }
1154
1155
1156 void
1157 debug_df_regno (unsigned int regno)
1158 {
1159   df_regno_debug (ddf, regno, stderr);
1160 }
1161
1162
1163 void
1164 debug_df_ref (struct df_ref *ref)
1165 {
1166   df_ref_debug (ddf, ref, stderr);
1167 }
1168
1169
1170 void
1171 debug_df_defno (unsigned int defno)
1172 {
1173   df_ref_debug (ddf, DF_DEFS_GET (ddf, defno), stderr);
1174 }
1175
1176
1177 void
1178 debug_df_useno (unsigned int defno)
1179 {
1180   df_ref_debug (ddf, DF_USES_GET (ddf, defno), stderr);
1181 }
1182
1183
1184 void
1185 debug_df_chain (struct df_link *link)
1186 {
1187   df_chain_dump (ddf, link, stderr);
1188   fputc ('\n', stderr);
1189 }