OSDN Git Service

e9da8b626fa794cfd41bd3bbfefdfec0a60ae481
[pf3gnuchains/gcc-fork.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 both at the beginning and ends of blocks.
209
210      For blocks that area at the destination of eh edges, the
211      artificial uses and defs occur at the beginning.  The defs relate
212      to the registers specified in EH_RETURN_DATA_REGNO and the uses
213      relate to the registers specified in ED_USES.  Logically these
214      defs and uses should really occur along the eh edge, but there is
215      no convenient way to do this.  Artificial edges that occur at the
216      beginning of the block have the DF_REF_AT_TOP flag set.
217
218      Artificial uses occur at the end of all blocks.  These arise from
219      the hard registers that are always live, such as the stack
220      register and are put there to keep the code from forgetting about
221      them.
222
223      Artifical defs occur at the end of the entry block.  These arise
224      from registers that are live at entry to the function.
225
226 2) All of the uses and defs associated with each pseudo or hard
227    register are linked in a bidirectional chain.  These are called
228    reg-use or reg_def chains.
229
230    The first use (or def) for a register can be obtained using the
231    DF_REG_USE_GET macro (or DF_REG_DEF_GET macro).  Subsequent uses
232    for the same regno can be obtained by following the next_reg field
233    of the ref.
234
235    In previous versions of this code, these chains were ordered.  It
236    has not been practical to continue this practice.
237
238 3) If def-use or use-def chains are built, these can be traversed to
239    get to other refs.
240
241 4) An array of all of the uses (and an array of all of the defs) can
242    be built.  These arrays are indexed by the value in the id
243    structure.  These arrays are only lazily kept up to date, and that
244    process can be expensive.  To have these arrays built, call
245    df_reorganize_refs.   Note that the values in the id field of a ref
246    may change across calls to df_analyze or df_reorganize refs.
247
248    If the only use of this array is to find all of the refs, it is
249    better to traverse all of the registers and then traverse all of
250    reg-use or reg-def chains.
251
252
253
254 NOTES:
255  
256 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
257 both a use and a def.  These are both marked read/write to show that they
258 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
259 will generate a use of reg 42 followed by a def of reg 42 (both marked
260 read/write).  Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
261 generates a use of reg 41 then a def of reg 41 (both marked read/write),
262 even though reg 41 is decremented before it is used for the memory
263 address in this second example.
264
265 A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
266 for which the number of word_mode units covered by the outer mode is
267 smaller than that covered by the inner mode, invokes a read-modify-write.
268 operation.  We generate both a use and a def and again mark them
269 read/write.
270
271 Paradoxical subreg writes do not leave a trace of the old content, so they
272 are write-only operations.  
273 */
274
275
276 #include "config.h"
277 #include "system.h"
278 #include "coretypes.h"
279 #include "tm.h"
280 #include "rtl.h"
281 #include "tm_p.h"
282 #include "insn-config.h"
283 #include "recog.h"
284 #include "function.h"
285 #include "regs.h"
286 #include "output.h"
287 #include "alloc-pool.h"
288 #include "flags.h"
289 #include "hard-reg-set.h"
290 #include "basic-block.h"
291 #include "sbitmap.h"
292 #include "bitmap.h"
293 #include "timevar.h"
294 #include "df.h"
295 #include "tree-pass.h"
296
297 static struct df *ddf = NULL;
298 struct df *shared_df = NULL;
299
300 static void * df_get_bb_info (struct dataflow *, unsigned int);
301 static void df_set_bb_info (struct dataflow *, unsigned int, void *);
302 /*----------------------------------------------------------------------------
303   Functions to create, destroy and manipulate an instance of df.
304 ----------------------------------------------------------------------------*/
305
306
307 /* Initialize dataflow analysis and allocate and initialize dataflow
308    memory.  */
309
310 struct df *
311 df_init (int flags)
312 {
313   struct df *df = XCNEW (struct df);
314   df->flags = flags;
315
316   /* This is executed once per compilation to initialize platform
317      specific data structures. */
318   df_hard_reg_init ();
319   
320   /* All df instance must define the scanning problem.  */
321   df_scan_add_problem (df);
322   ddf = df;
323   return df;
324 }
325
326 /* Add PROBLEM to the DF instance.  */
327
328 struct dataflow *
329 df_add_problem (struct df *df, struct df_problem *problem)
330 {
331   struct dataflow *dflow;
332
333   /* First try to add the dependent problem. */
334   if (problem->dependent_problem)
335     df_add_problem (df, problem->dependent_problem);
336
337   /* Check to see if this problem has already been defined.  If it
338      has, just return that instance, if not, add it to the end of the
339      vector.  */
340   dflow = df->problems_by_index[problem->id];
341   if (dflow)
342     return dflow;
343
344   /* Make a new one and add it to the end.  */
345   dflow = XCNEW (struct dataflow);
346   dflow->df = df;
347   dflow->problem = problem;
348   df->problems_in_order[df->num_problems_defined++] = dflow;
349   df->problems_by_index[dflow->problem->id] = dflow;
350
351   return dflow;
352 }
353
354
355 /* Set the blocks that are to be considered for analysis.  If this is
356    not called or is called with null, the entire function in
357    analyzed.  */
358
359 void 
360 df_set_blocks (struct df *df, bitmap blocks)
361 {
362   if (blocks)
363     {
364       if (df->blocks_to_analyze)
365         {
366           int p;
367           bitmap diff = BITMAP_ALLOC (NULL);
368           bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
369           for (p = df->num_problems_defined - 1; p >= 0 ;p--)
370             {
371               struct dataflow *dflow = df->problems_in_order[p];
372               if (dflow->problem->reset_fun)
373                 dflow->problem->reset_fun (dflow, df->blocks_to_analyze);
374               else if (dflow->problem->free_bb_fun)
375                 {
376                   bitmap_iterator bi;
377                   unsigned int bb_index;
378                   
379                   EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
380                     {
381                       basic_block bb = BASIC_BLOCK (bb_index);
382                       if (bb)
383                         {
384                           dflow->problem->free_bb_fun
385                             (dflow, bb, df_get_bb_info (dflow, bb_index));
386                           df_set_bb_info (dflow, bb_index, NULL); 
387                         }
388                     }
389                 }
390             }
391
392           BITMAP_FREE (diff);
393         }
394       else
395         {
396           /* If we have not actually run scanning before, do not try
397              to clear anything.  */
398           struct dataflow *scan_dflow = df->problems_by_index [DF_SCAN];
399           if (scan_dflow->problem_data)
400             {
401               bitmap blocks_to_reset = NULL;
402               int p;
403               for (p = df->num_problems_defined - 1; p >= 0 ;p--)
404                 {
405                   struct dataflow *dflow = df->problems_in_order[p];
406                   if (dflow->problem->reset_fun)
407                     {
408                       if (!blocks_to_reset)
409                         {
410                           basic_block bb;
411                           blocks_to_reset = BITMAP_ALLOC (NULL);
412                           FOR_ALL_BB(bb)
413                             {
414                               bitmap_set_bit (blocks_to_reset, bb->index); 
415                             }
416                         }
417                       dflow->problem->reset_fun (dflow, blocks_to_reset);
418                     }
419                 }
420               if (blocks_to_reset)
421                 BITMAP_FREE (blocks_to_reset);
422             }
423           df->blocks_to_analyze = BITMAP_ALLOC (NULL);
424         }
425       bitmap_copy (df->blocks_to_analyze, blocks);
426     }
427   else
428     {
429       if (df->blocks_to_analyze)
430         {
431           BITMAP_FREE (df->blocks_to_analyze);
432           df->blocks_to_analyze = NULL;
433         }
434     }
435 }
436
437
438 /* Free all the dataflow info and the DF structure.  This should be
439    called from the df_finish macro which also NULLs the parm.  */
440
441 void
442 df_finish1 (struct df *df)
443 {
444   int i;
445
446   for (i = 0; i < df->num_problems_defined; i++)
447     df->problems_in_order[i]->problem->free_fun (df->problems_in_order[i]); 
448
449   free (df);
450 }
451
452 \f
453 /*----------------------------------------------------------------------------
454    The general data flow analysis engine.
455 ----------------------------------------------------------------------------*/
456
457
458 /* Hybrid search algorithm from "Implementation Techniques for
459    Efficient Data-Flow Analysis of Large Programs".  */
460
461 static void
462 df_hybrid_search_forward (basic_block bb, 
463                           struct dataflow *dataflow,
464                           bool single_pass)
465 {
466   int result_changed;
467   int i = bb->index;
468   edge e;
469   edge_iterator ei;
470
471   SET_BIT (dataflow->visited, bb->index);
472   gcc_assert (TEST_BIT (dataflow->pending, bb->index));
473   RESET_BIT (dataflow->pending, i);
474
475   /*  Calculate <conf_op> of predecessor_outs.  */
476   if (EDGE_COUNT (bb->preds) > 0)
477     FOR_EACH_EDGE (e, ei, bb->preds)
478       {
479         if (!TEST_BIT (dataflow->considered, e->src->index))
480           continue;
481         
482         dataflow->problem->con_fun_n (dataflow, e);
483       }
484   else if (dataflow->problem->con_fun_0)
485     dataflow->problem->con_fun_0 (dataflow, bb);
486   
487   result_changed = dataflow->problem->trans_fun (dataflow, i);
488   
489   if (!result_changed || single_pass)
490     return;
491   
492   FOR_EACH_EDGE (e, ei, bb->succs)
493     {
494       if (e->dest->index == i)
495         continue;
496       if (!TEST_BIT (dataflow->considered, e->dest->index))
497         continue;
498       SET_BIT (dataflow->pending, e->dest->index);
499     }
500   
501   FOR_EACH_EDGE (e, ei, bb->succs)
502     {
503       if (e->dest->index == i)
504         continue;
505       
506       if (!TEST_BIT (dataflow->considered, e->dest->index))
507         continue;
508       if (!TEST_BIT (dataflow->visited, e->dest->index))
509         df_hybrid_search_forward (e->dest, dataflow, single_pass);
510     }
511 }
512
513 static void
514 df_hybrid_search_backward (basic_block bb,
515                            struct dataflow *dataflow,
516                            bool single_pass)
517 {
518   int result_changed;
519   int i = bb->index;
520   edge e;
521   edge_iterator ei;
522   
523   SET_BIT (dataflow->visited, bb->index);
524   gcc_assert (TEST_BIT (dataflow->pending, bb->index));
525   RESET_BIT (dataflow->pending, i);
526
527   /*  Calculate <conf_op> of predecessor_outs.  */
528   if (EDGE_COUNT (bb->succs) > 0)
529     FOR_EACH_EDGE (e, ei, bb->succs)                                    
530       {                                                         
531         if (!TEST_BIT (dataflow->considered, e->dest->index))           
532           continue;                                                     
533         
534         dataflow->problem->con_fun_n (dataflow, e);
535       }                                                         
536   else if (dataflow->problem->con_fun_0)
537     dataflow->problem->con_fun_0 (dataflow, bb);
538
539   result_changed = dataflow->problem->trans_fun (dataflow, i);
540   
541   if (!result_changed || single_pass)
542     return;
543   
544   FOR_EACH_EDGE (e, ei, bb->preds)
545     {                                                           
546       if (e->src->index == i)
547         continue;
548       
549       if (!TEST_BIT (dataflow->considered, e->src->index))
550         continue;
551
552       SET_BIT (dataflow->pending, e->src->index);
553     }                                                           
554   
555   FOR_EACH_EDGE (e, ei, bb->preds)
556     {
557       if (e->src->index == i)
558         continue;
559
560       if (!TEST_BIT (dataflow->considered, e->src->index))
561         continue;
562       
563       if (!TEST_BIT (dataflow->visited, e->src->index))
564         df_hybrid_search_backward (e->src, dataflow, single_pass);
565     }
566 }
567
568
569 /* This function will perform iterative bitvector dataflow described
570    by DATAFLOW, producing the in and out sets.  Only the part of the
571    cfg induced by blocks in DATAFLOW->order is taken into account.
572
573    SINGLE_PASS is true if you just want to make one pass over the
574    blocks.  */
575
576 void
577 df_iterative_dataflow (struct dataflow *dataflow,
578                        bitmap blocks_to_consider, bitmap blocks_to_init, 
579                        int *blocks_in_postorder, int n_blocks, 
580                        bool single_pass)
581 {
582   unsigned int idx;
583   int i;
584   sbitmap visited = sbitmap_alloc (last_basic_block);
585   sbitmap pending = sbitmap_alloc (last_basic_block);
586   sbitmap considered = sbitmap_alloc (last_basic_block);
587   bitmap_iterator bi;
588
589   dataflow->visited = visited;
590   dataflow->pending = pending;
591   dataflow->considered = considered;
592
593   sbitmap_zero (visited);
594   sbitmap_zero (pending);
595   sbitmap_zero (considered);
596
597   EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi)
598     {
599       SET_BIT (considered, idx);
600     }
601
602   for (i = 0; i < n_blocks; i++)
603     {
604       idx = blocks_in_postorder[i];
605       SET_BIT (pending, idx);
606     };
607
608   dataflow->problem->init_fun (dataflow, blocks_to_init);
609
610   while (1)
611     {
612
613       /* For forward problems, you want to pass in reverse postorder
614          and for backward problems you want postorder.  This has been
615          shown to be as good as you can do by several people, the
616          first being Mathew Hecht in his phd dissertation.
617
618          The nodes are passed into this function in postorder.  */
619
620       if (dataflow->problem->dir == DF_FORWARD)
621         {
622           for (i = n_blocks - 1 ; i >= 0 ; i--)
623             {
624               idx = blocks_in_postorder[i];
625               
626               if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
627                 df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass);
628             }
629         }
630       else
631         {
632           for (i = 0; i < n_blocks; i++)
633             {
634               idx = blocks_in_postorder[i];
635               
636               if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
637                 df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass);
638             }
639         }
640
641       if (sbitmap_first_set_bit (pending) == -1)
642         break;
643
644       sbitmap_zero (visited);
645     }
646
647   sbitmap_free (pending);
648   sbitmap_free (visited);
649   sbitmap_free (considered);
650 }
651
652
653 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
654    the order of the remaining entries.  Returns the length of the resulting
655    list.  */
656
657 static unsigned
658 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
659 {
660   unsigned act, last;
661
662   for (act = 0, last = 0; act < len; act++)
663     if (bitmap_bit_p (blocks, list[act]))
664       list[last++] = list[act];
665
666   return last;
667 }
668
669
670 /* Execute dataflow analysis on a single dataflow problem. 
671
672    There are three sets of blocks passed in: 
673
674    BLOCKS_TO_CONSIDER are the blocks whose solution can either be
675    examined or will be computed.  For calls from DF_ANALYZE, this is
676    the set of blocks that has been passed to DF_SET_BLOCKS.  For calls
677    from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of
678    blocks in the fringe (the set of blocks passed in plus the set of
679    immed preds and succs of those blocks).
680
681    BLOCKS_TO_INIT are the blocks whose solution will be changed by
682    this iteration.  For calls from DF_ANALYZE, this is the set of
683    blocks that has been passed to DF_SET_BLOCKS.  For calls from
684    DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks
685    passed in.
686
687    BLOCKS_TO_SCAN are the set of blocks that need to be rescanned.
688    For calls from DF_ANALYZE, this is the accumulated set of blocks
689    that has been passed to DF_RESCAN_BLOCKS since the last call to
690    DF_ANALYZE.  For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS,
691    this is the set of blocks passed in.
692  
693                    blocks_to_consider    blocks_to_init    blocks_to_scan
694    full redo       all                   all               all
695    partial redo    all                   all               sub
696    small fixup     fringe                sub               sub
697 */
698
699 static void
700 df_analyze_problem (struct dataflow *dflow, 
701                     bitmap blocks_to_consider, 
702                     bitmap blocks_to_init,
703                     bitmap blocks_to_scan,
704                     int *postorder, int n_blocks, bool single_pass)
705 {
706   /* (Re)Allocate the datastructures necessary to solve the problem.  */ 
707   if (dflow->problem->alloc_fun)
708     dflow->problem->alloc_fun (dflow, blocks_to_scan);
709
710   /* Set up the problem and compute the local information.  This
711      function is passed both the blocks_to_consider and the
712      blocks_to_scan because the RD and RU problems require the entire
713      function to be rescanned if they are going to be updated.  */
714   if (dflow->problem->local_compute_fun)
715     dflow->problem->local_compute_fun (dflow, blocks_to_consider, blocks_to_scan);
716
717   /* Solve the equations.  */
718   if (dflow->problem->dataflow_fun)
719     dflow->problem->dataflow_fun (dflow, blocks_to_consider, blocks_to_init,
720                                   postorder, n_blocks, single_pass);
721
722   /* Massage the solution.  */
723   if (dflow->problem->finalize_fun)
724     dflow->problem->finalize_fun (dflow, blocks_to_consider);
725 }
726
727
728 /* Analyze dataflow info for the basic blocks specified by the bitmap
729    BLOCKS, or for the whole CFG if BLOCKS is zero.  */
730
731 void
732 df_analyze (struct df *df)
733 {
734   int *postorder = XNEWVEC (int, last_basic_block);
735   bitmap current_all_blocks = BITMAP_ALLOC (NULL);
736   int n_blocks;
737   int i;
738   bool everything;
739
740   n_blocks = post_order_compute (postorder, true);
741
742   if (n_blocks != n_basic_blocks)
743     delete_unreachable_blocks ();
744
745   for (i = 0; i < n_blocks; i++)
746     bitmap_set_bit (current_all_blocks, postorder[i]);
747
748   /* No one called df_rescan_blocks, so do it.  */
749   if (!df->blocks_to_scan)
750     df_rescan_blocks (df, NULL);
751
752   /* Make sure that we have pruned any unreachable blocks from these
753      sets.  */
754   bitmap_and_into (df->blocks_to_scan, current_all_blocks);
755
756   if (df->blocks_to_analyze)
757     {
758       everything = false;
759       bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
760       n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze);
761       BITMAP_FREE (current_all_blocks);
762     }
763   else
764     {
765       everything = true;
766       df->blocks_to_analyze = current_all_blocks;
767       current_all_blocks = NULL;
768     }
769
770   /* Skip over the DF_SCAN problem. */
771   for (i = 1; i < df->num_problems_defined; i++)
772     df_analyze_problem (df->problems_in_order[i], 
773                         df->blocks_to_analyze, df->blocks_to_analyze, 
774                         df->blocks_to_scan,
775                         postorder, n_blocks, false);
776
777   if (everything)
778     {
779       BITMAP_FREE (df->blocks_to_analyze);
780       df->blocks_to_analyze = NULL;
781     }
782
783   BITMAP_FREE (df->blocks_to_scan);
784   df->blocks_to_scan = NULL;
785   free (postorder);
786 }
787
788
789 \f
790 /*----------------------------------------------------------------------------
791    Functions to support limited incremental change.
792 ----------------------------------------------------------------------------*/
793
794
795 /* Get basic block info.  */
796
797 static void *
798 df_get_bb_info (struct dataflow *dflow, unsigned int index)
799 {
800   return (struct df_scan_bb_info *) dflow->block_info[index];
801 }
802
803
804 /* Set basic block info.  */
805
806 static void
807 df_set_bb_info (struct dataflow *dflow, unsigned int index, 
808                 void *bb_info)
809 {
810   dflow->block_info[index] = bb_info;
811 }
812
813
814 /* Called from the rtl_compact_blocks to reorganize the problems basic
815    block info.  */
816
817 void 
818 df_compact_blocks (struct df *df)
819 {
820   int i, p;
821   basic_block bb;
822   void **problem_temps;
823   int size = last_basic_block *sizeof (void *);
824   problem_temps = xmalloc (size);
825
826   for (p = 0; p < df->num_problems_defined; p++)
827     {
828       struct dataflow *dflow = df->problems_in_order[p];
829       if (dflow->problem->free_bb_fun)
830         {
831           df_grow_bb_info (dflow);
832           memcpy (problem_temps, dflow->block_info, size);
833
834           /* Copy the bb info from the problem tmps to the proper
835              place in the block_info vector.  Null out the copied
836              item.  */
837           i = NUM_FIXED_BLOCKS;
838           FOR_EACH_BB (bb) 
839             {
840               df_set_bb_info (dflow, i, problem_temps[bb->index]);
841               problem_temps[bb->index] = NULL;
842               i++;
843             }
844           memset (dflow->block_info + i, 0, 
845                   (last_basic_block - i) *sizeof (void *));
846
847           /* Free any block infos that were not copied (and NULLed).
848              These are from orphaned blocks.  */
849           for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
850             {
851               basic_block bb = BASIC_BLOCK (i); 
852               if (problem_temps[i] && bb)
853                 dflow->problem->free_bb_fun
854                   (dflow, bb, problem_temps[i]);
855             }
856         }
857     }
858
859   free (problem_temps);
860
861   i = NUM_FIXED_BLOCKS;
862   FOR_EACH_BB (bb) 
863     {
864       SET_BASIC_BLOCK (i, bb);
865       bb->index = i;
866       i++;
867     }
868
869   gcc_assert (i == n_basic_blocks);
870
871   for (; i < last_basic_block; i++)
872     SET_BASIC_BLOCK (i, NULL);
873 }
874
875
876 /* Shove NEW_BLOCK in at OLD_INDEX.  Called from if-cvt to hack a
877    block.  There is no excuse for people to do this kind of thing.  */
878
879 void 
880 df_bb_replace (struct df *df, int old_index, basic_block new_block)
881 {
882   int p;
883
884   for (p = 0; p < df->num_problems_defined; p++)
885     {
886       struct dataflow *dflow = df->problems_in_order[p];
887       if (dflow->block_info)
888         {
889           void *temp;
890
891           df_grow_bb_info (dflow);
892
893           /* The old switcheroo.  */
894
895           temp = df_get_bb_info (dflow, old_index);
896           df_set_bb_info (dflow, old_index, 
897                           df_get_bb_info (dflow, new_block->index));
898           df_set_bb_info (dflow, new_block->index, temp);
899         }
900     }
901
902   SET_BASIC_BLOCK (old_index, new_block);
903   new_block->index = old_index;
904 }
905
906 /*----------------------------------------------------------------------------
907    PUBLIC INTERFACES TO QUERY INFORMATION.
908 ----------------------------------------------------------------------------*/
909
910
911 /* Return last use of REGNO within BB.  */
912
913 struct df_ref *
914 df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
915 {
916   rtx insn;
917   struct df_ref *use;
918
919   FOR_BB_INSNS_REVERSE (bb, insn)
920     {
921       unsigned int uid = INSN_UID (insn);
922       for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
923         if (DF_REF_REGNO (use) == regno)
924           return use;
925     }
926   return NULL;
927 }
928
929
930 /* Return first def of REGNO within BB.  */
931
932 struct df_ref *
933 df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
934 {
935   rtx insn;
936   struct df_ref *def;
937
938   FOR_BB_INSNS (bb, insn)
939     {
940       unsigned int uid = INSN_UID (insn);
941       for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
942         if (DF_REF_REGNO (def) == regno)
943           return def;
944     }
945   return NULL;
946 }
947
948
949 /* Return last def of REGNO within BB.  */
950
951 struct df_ref *
952 df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
953 {
954   rtx insn;
955   struct df_ref *def;
956
957   FOR_BB_INSNS_REVERSE (bb, insn)
958     {
959       unsigned int uid = INSN_UID (insn);
960
961       for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
962         if (DF_REF_REGNO (def) == regno)
963           return def;
964     }
965
966   return NULL;
967 }
968
969 /* Return true if INSN defines REGNO.  */
970
971 bool
972 df_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno)
973 {
974   unsigned int uid;
975   struct df_ref *def;
976
977   uid = INSN_UID (insn);
978   for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
979     if (DF_REF_REGNO (def) == regno)
980       return true;
981   
982   return false;
983 }
984
985
986 /* Finds the reference corresponding to the definition of REG in INSN.
987    DF is the dataflow object.  */
988
989 struct df_ref *
990 df_find_def (struct df *df, rtx insn, rtx reg)
991 {
992   unsigned int uid;
993   struct df_ref *def;
994
995   if (GET_CODE (reg) == SUBREG)
996     reg = SUBREG_REG (reg);
997   gcc_assert (REG_P (reg));
998
999   uid = INSN_UID (insn);
1000   for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
1001     if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
1002       return def;
1003
1004   return NULL;
1005 }
1006
1007
1008 /* Return true if REG is defined in INSN, zero otherwise.  */ 
1009
1010 bool
1011 df_reg_defined (struct df *df, rtx insn, rtx reg)
1012 {
1013   return df_find_def (df, insn, reg) != NULL;
1014 }
1015   
1016
1017 /* Finds the reference corresponding to the use of REG in INSN.
1018    DF is the dataflow object.  */
1019   
1020 struct df_ref *
1021 df_find_use (struct df *df, rtx insn, rtx reg)
1022 {
1023   unsigned int uid;
1024   struct df_ref *use;
1025
1026   if (GET_CODE (reg) == SUBREG)
1027     reg = SUBREG_REG (reg);
1028   gcc_assert (REG_P (reg));
1029
1030   uid = INSN_UID (insn);
1031   for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
1032     if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1033       return use; 
1034
1035   return NULL;
1036 }
1037
1038
1039 /* Return true if REG is referenced in INSN, zero otherwise.  */ 
1040
1041 bool
1042 df_reg_used (struct df *df, rtx insn, rtx reg)
1043 {
1044   return df_find_use (df, insn, reg) != NULL;
1045 }
1046   
1047 \f
1048 /*----------------------------------------------------------------------------
1049    Debugging and printing functions.
1050 ----------------------------------------------------------------------------*/
1051
1052 /* Dump dataflow info.  */
1053 void
1054 df_dump (struct df *df, FILE *file)
1055 {
1056   int i;
1057
1058   if (! df || ! file)
1059     return;
1060
1061   fprintf (file, "\n\n%s\n", current_function_name ());
1062   fprintf (file, "\nDataflow summary:\n");
1063   fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n",
1064            df->def_info.bitmap_size, df->use_info.bitmap_size);
1065
1066   for (i = 0; i < df->num_problems_defined; i++)
1067     df->problems_in_order[i]->problem->dump_fun (df->problems_in_order[i], file); 
1068
1069   fprintf (file, "\n");
1070 }
1071
1072
1073 void
1074 df_refs_chain_dump (struct df *df, struct df_ref *ref, 
1075                    bool follow_chain, FILE *file)
1076 {
1077   fprintf (file, "{ ");
1078   while (ref)
1079     {
1080       fprintf (file, "%c%d(%d) ",
1081                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1082                DF_REF_ID (ref),
1083                DF_REF_REGNO (ref));
1084       if (follow_chain)
1085         df_chain_dump (df, DF_REF_CHAIN (ref), file);
1086       ref = ref->next_ref;
1087     }
1088   fprintf (file, "}");
1089 }
1090
1091
1092 /* Dump either a ref-def or reg-use chain.  */
1093
1094 void
1095 df_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref,  FILE *file)
1096 {
1097   fprintf (file, "{ ");
1098   while (ref)
1099     {
1100       fprintf (file, "%c%d(%d) ",
1101                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1102                DF_REF_ID (ref),
1103                DF_REF_REGNO (ref));
1104       ref = ref->next_reg;
1105     }
1106   fprintf (file, "}");
1107 }
1108
1109
1110 void
1111 df_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file)
1112 {
1113   unsigned int uid;
1114   int bbi;
1115
1116   uid = INSN_UID (insn);
1117
1118   if (DF_INSN_UID_DEFS (df, uid))
1119     bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1120   else if (DF_INSN_UID_USES(df, uid))
1121     bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1122   else
1123     bbi = -1;
1124
1125   fprintf (file, "insn %d bb %d luid %d defs ",
1126            uid, bbi, DF_INSN_LUID (df, insn));
1127
1128   df_refs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), follow_chain, file);
1129   fprintf (file, " defs ");
1130   df_refs_chain_dump (df, DF_INSN_UID_USES (df, uid), follow_chain, file);
1131   fprintf (file, "\n");
1132 }
1133
1134 void
1135 df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
1136 {
1137   unsigned int uid;
1138   int bbi;
1139
1140   uid = INSN_UID (insn);
1141   if (DF_INSN_UID_DEFS (df, uid))
1142     bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1143   else if (DF_INSN_UID_USES(df, uid))
1144     bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1145   else
1146     bbi = -1;
1147
1148   fprintf (file, "insn %d bb %d luid %d defs ",
1149            uid, bbi, DF_INSN_LUID (df, insn));
1150   df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file);
1151     
1152   fprintf (file, " uses ");
1153   df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file);
1154   fprintf (file, "\n");
1155 }
1156
1157 void
1158 df_regno_debug (struct df *df, unsigned int regno, FILE *file)
1159 {
1160   fprintf (file, "reg %d defs ", regno);
1161   df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file);
1162   fprintf (file, " uses ");
1163   df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file);
1164   fprintf (file, "\n");
1165 }
1166
1167
1168 void
1169 df_ref_debug (struct df *df, struct df_ref *ref, FILE *file)
1170 {
1171   fprintf (file, "%c%d ",
1172            DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1173            DF_REF_ID (ref));
1174   fprintf (file, "reg %d bb %d luid %d insn %d chain ",
1175            DF_REF_REGNO (ref),
1176            DF_REF_BBNO (ref),
1177            DF_REF_INSN (ref) ? DF_INSN_LUID (df, DF_REF_INSN (ref)) : -1,
1178            DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1);
1179   df_chain_dump (df, DF_REF_CHAIN (ref), file);
1180   fprintf (file, "\n");
1181 }
1182 \f
1183 /* Functions for debugging from GDB.  */
1184
1185 void
1186 debug_df_insn (rtx insn)
1187 {
1188   df_insn_debug (ddf, insn, true, stderr);
1189   debug_rtx (insn);
1190 }
1191
1192
1193 void
1194 debug_df_reg (rtx reg)
1195 {
1196   df_regno_debug (ddf, REGNO (reg), stderr);
1197 }
1198
1199
1200 void
1201 debug_df_regno (unsigned int regno)
1202 {
1203   df_regno_debug (ddf, regno, stderr);
1204 }
1205
1206
1207 void
1208 debug_df_ref (struct df_ref *ref)
1209 {
1210   df_ref_debug (ddf, ref, stderr);
1211 }
1212
1213
1214 void
1215 debug_df_defno (unsigned int defno)
1216 {
1217   df_ref_debug (ddf, DF_DEFS_GET (ddf, defno), stderr);
1218 }
1219
1220
1221 void
1222 debug_df_useno (unsigned int defno)
1223 {
1224   df_ref_debug (ddf, DF_USES_GET (ddf, defno), stderr);
1225 }
1226
1227
1228 void
1229 debug_df_chain (struct df_link *link)
1230 {
1231   df_chain_dump (ddf, link, stderr);
1232   fputc ('\n', stderr);
1233 }